lucy-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mar...@apache.org
Subject svn commit: r895799 - in /lucene/lucy/trunk: clownfish/lib/Clownfish/Binding/ core/Lucy/Object/ core/Lucy/Test/Object/ perl/lib/ perl/lib/Lucy/ perl/lib/Lucy/Object/ perl/t/binding/ perl/t/core/ perl/xs/Lucy/Object/
Date Mon, 04 Jan 2010 22:08:55 GMT
Author: marvin
Date: Mon Jan  4 22:08:54 2010
New Revision: 895799

URL: http://svn.apache.org/viewvc?rev=895799&view=rev
Log:
Add Lucy::Object::LockFreeRegistry, a purpose-built thread-safe hash table
class for storing VTables. (lock_free_registry.diff from LUCY-92)

Added:
    lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.bp   (with props)
    lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.c   (with props)
    lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.bp   (with props)
    lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.c   (with props)
    lucene/lucy/trunk/perl/lib/Lucy/Object/LockFreeRegistry.pm   (with props)
    lucene/lucy/trunk/perl/t/binding/038-lock_free_registry.t   (with props)
    lucene/lucy/trunk/perl/t/core/038-lock_free_registry.t   (with props)
    lucene/lucy/trunk/perl/xs/Lucy/Object/LockFreeRegistry.c   (with props)
Modified:
    lucene/lucy/trunk/clownfish/lib/Clownfish/Binding/Perl.pm
    lucene/lucy/trunk/perl/lib/Lucy.pm
    lucene/lucy/trunk/perl/lib/Lucy/Test.pm

Modified: lucene/lucy/trunk/clownfish/lib/Clownfish/Binding/Perl.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/clownfish/lib/Clownfish/Binding/Perl.pm?rev=895799&r1=895798&r2=895799&view=diff
==============================================================================
--- lucene/lucy/trunk/clownfish/lib/Clownfish/Binding/Perl.pm (original)
+++ lucene/lucy/trunk/clownfish/lib/Clownfish/Binding/Perl.pm Mon Jan  4 22:08:54 2010
@@ -295,6 +295,10 @@
         my $prefix  = $class->get_prefix;
         my $PREFIX  = $class->get_PREFIX;
         my $vt_type = $PREFIX . $class->vtable_type;
+
+        # Ignore return value from VTable_add_to_registry, since it's OK if
+        # multiple threads contend for adding these permanent VTables and some
+        # fail.
         $registrations
             .= qq|    ${prefix}VTable_add_to_registry($PREFIX|
             . $class->vtable_var

Added: lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.bp?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.bp Mon Jan  4 22:08:54 2010
@@ -0,0 +1,43 @@
+parcel Lucy;
+
+/** Specialized lock free hash table for storing VTables.
+ */
+class Lucy::Object::LockFreeRegistry cnick LFReg extends Lucy::Object::Obj {
+
+    size_t  capacity;
+    void   *entries;
+
+    inert incremented LockFreeRegistry*
+    new(size_t capacity);
+
+    inert LockFreeRegistry*
+    init(LockFreeRegistry *self, size_t capacity);
+
+    public void
+    Destroy(LockFreeRegistry *self);
+
+    bool_t
+    Register(LockFreeRegistry *self, Obj *key, Obj *value);
+
+    Obj*
+    Fetch(LockFreeRegistry *self, Obj *key);
+    
+    void*
+    To_Host(LockFreeRegistry *self);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+

Propchange: lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.bp
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.c?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.c (added)
+++ lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.c Mon Jan  4 22:08:54 2010
@@ -0,0 +1,133 @@
+#define C_LUCY_LOCKFREEREGISTRY
+#define LUCY_USE_SHORT_NAMES
+#define CHY_USE_SHORT_NAMES
+
+#include "Lucy/Object/LockFreeRegistry.h"
+#include "Lucy/Object/Err.h"
+#include "Lucy/Object/VTable.h"
+#include "Lucy/Util/Atomic.h"
+#include "Lucy/Util/Memory.h"
+
+typedef struct lucy_LFRegEntry {
+    Obj   *key;
+    Obj   *value;
+    i32_t  hash_code;
+    struct lucy_LFRegEntry *volatile next;
+} lucy_LFRegEntry;
+#define LFRegEntry lucy_LFRegEntry
+
+LockFreeRegistry*
+LFReg_new(size_t capacity)
+{
+    LockFreeRegistry *self 
+        = (LockFreeRegistry*)VTable_Make_Obj(LOCKFREEREGISTRY);
+    return LFReg_init(self, capacity);
+}
+
+LockFreeRegistry*
+LFReg_init(LockFreeRegistry *self, size_t capacity)
+{
+    self->capacity = capacity;
+    self->entries  = CALLOCATE(capacity, sizeof(void*));
+    return self;
+}
+
+bool_t
+LFReg_register(LockFreeRegistry *self, Obj *key, Obj *value)
+{
+    LFRegEntry  *new_entry = NULL;
+    i32_t        hash_code = Obj_Hash_Code(key);
+    size_t       bucket    = (u32_t)hash_code % self->capacity;
+    LFRegEntry  *volatile *entries = (LFRegEntry*volatile*)self->entries;
+    LFRegEntry  *volatile *slot    = &(entries[bucket]);
+
+    /* Proceed through the linked list.  Bail out if the key has already been
+     * registered. */
+    FIND_END_OF_LINKED_LIST:
+    while (*slot) {
+        LFRegEntry *entry = *slot;
+        if (entry->hash_code == hash_code) {
+            if (Obj_Equals(key, entry->key)) {
+                return false;
+            }
+        }
+        slot = &(entry->next);
+    }
+
+    /* We've found an empty slot. Create the new entry. */ 
+    if (!new_entry) {
+        new_entry = (LFRegEntry*)MALLOCATE(sizeof(LFRegEntry));
+        new_entry->hash_code = hash_code;
+        new_entry->key       = INCREF(key);
+        new_entry->value     = INCREF(value);
+        new_entry->next      = NULL;
+    }
+
+    /* Attempt to append the new node onto the end of the linked list.
+     * However, if another thread filled the slot since we found it (perhaps
+     * while we were allocating that new node), the compare-and-swap will
+     * fail.  If that happens, we have to go back and find the new end of the
+     * linked list, then try again. */
+    if (!Atomic_cas_ptr((void*volatile*)slot, NULL, new_entry)) {
+        goto FIND_END_OF_LINKED_LIST;
+    }
+
+    return true;
+}
+
+Obj*
+LFReg_fetch(LockFreeRegistry *self, Obj *key)
+{
+    i32_t        hash_code = Obj_Hash_Code(key);
+    size_t       bucket    = (u32_t)hash_code % self->capacity;
+    LFRegEntry **entries   = (LFRegEntry**)self->entries;
+    LFRegEntry  *entry     = entries[bucket];
+
+    while (entry) {
+        if (entry->hash_code == hash_code) {
+            if (Obj_Equals(key, entry->key)) {
+                return entry->value;
+            }
+        }
+        entry = entry->next;
+    }
+
+    return NULL;
+}
+
+void
+LFReg_destroy(LockFreeRegistry *self)
+{
+    size_t i;
+    LFRegEntry **entries = (LFRegEntry**)self->entries;
+
+    for (i = 0; i < self->capacity; i++) {
+        LFRegEntry *entry = entries[i];
+        while (entry) {
+            LFRegEntry *next_entry = entry->next;
+            DECREF(entry->key);
+            DECREF(entry->value);
+            FREEMEM(entry);
+            entry = next_entry;
+        }
+    }
+    FREEMEM(self->entries);
+
+    SUPER_DESTROY(self, LOCKFREEREGISTRY);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+

Propchange: lucene/lucy/trunk/core/Lucy/Object/LockFreeRegistry.c
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.bp
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.bp?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.bp (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.bp Mon Jan  4 22:08:54 2010
@@ -0,0 +1,33 @@
+parcel Lucy;
+
+inert class Lucy::Test::Object::TestLockFreeRegistry cnick TestLFReg {
+    inert void
+    run_tests();
+}
+
+/** Private test-only class for stressing LockFreeRegistry. 
+ */
+class Lucy::Test::Object::StupidHashCharBuf extends Lucy::Object::CharBuf {
+    inert incremented StupidHashCharBuf*
+    new(char *text);
+
+    /** Always returns 1, guaranteeing collisions. */
+    public i32_t
+    Hash_Code(StupidHashCharBuf *self);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+

Propchange: lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.bp
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.c?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.c (added)
+++ lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.c Mon Jan  4 22:08:54 2010
@@ -0,0 +1,80 @@
+#include <string.h>
+
+#include "Lucy/Util/ToolSet.h"
+
+#include "Lucy/Test.h"
+#include "Lucy/Test/TestUtils.h"
+#include "Lucy/Test/Object/TestLockFreeRegistry.h"
+#include "Lucy/Object/LockFreeRegistry.h"
+
+StupidHashCharBuf*
+StupidHashCharBuf_new(char *text)
+{
+    return (StupidHashCharBuf*)CB_new_from_utf8(text, strlen(text));
+}
+
+i32_t
+StupidHashCharBuf_hash_code(StupidHashCharBuf *self)
+{
+    UNUSED_VAR(self);
+    return 1;
+}
+
+static void
+test_all(TestBatch *batch)
+{
+    LockFreeRegistry *registry = LFReg_new(10);
+    StupidHashCharBuf *foo = StupidHashCharBuf_new("foo");
+    StupidHashCharBuf *bar = StupidHashCharBuf_new("bar");
+    StupidHashCharBuf *baz = StupidHashCharBuf_new("baz");
+    StupidHashCharBuf *foo_dupe = StupidHashCharBuf_new("foo");
+
+    ASSERT_TRUE(batch, LFReg_Register(registry, (Obj*)foo, (Obj*)foo), 
+        "Register() returns true on success");
+    ASSERT_FALSE(batch, 
+        LFReg_Register(registry, (Obj*)foo_dupe, (Obj*)foo_dupe), 
+        "Can't Register() keys that test equal");
+
+    ASSERT_TRUE(batch, LFReg_Register(registry, (Obj*)bar, (Obj*)bar), 
+        "Register() key with the same Hash_Code but that isn't Equal");
+
+    ASSERT_TRUE(batch, LFReg_Fetch(registry, (Obj*)foo_dupe) == (Obj*)foo, 
+        "Fetch()");
+    ASSERT_TRUE(batch, LFReg_Fetch(registry, (Obj*)bar) == (Obj*)bar, 
+        "Fetch() again");
+    ASSERT_TRUE(batch, LFReg_Fetch(registry, (Obj*)baz) == NULL,
+        "Fetch() non-existent key returns NULL");
+
+    DECREF(foo_dupe);
+    DECREF(baz);
+    DECREF(bar);
+    DECREF(foo);
+    DECREF(registry);
+}
+
+void
+TestLFReg_run_tests()
+{
+    TestBatch *batch = Test_new_batch("TestLockFreeRegistry", 6, NULL);
+
+    PLAN(batch);
+    test_all(batch);
+
+    batch->destroy(batch);
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+

Propchange: lucene/lucy/trunk/core/Lucy/Test/Object/TestLockFreeRegistry.c
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: lucene/lucy/trunk/perl/lib/Lucy.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy.pm?rev=895799&r1=895798&r2=895799&view=diff
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy.pm (original)
+++ lucene/lucy/trunk/perl/lib/Lucy.pm Mon Jan  4 22:08:54 2010
@@ -115,6 +115,11 @@
 }
 
 {
+    package Lucy::Object::LockFreeRegistry;
+    sub DESTROY { }    # leak all
+}
+
+{
     package Lucy::Object::Obj;
     use Lucy::Util::ToolSet qw( to_lucy to_perl );
     sub load { return $_[0]->_load( to_lucy( $_[1] ) ) }

Added: lucene/lucy/trunk/perl/lib/Lucy/Object/LockFreeRegistry.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy/Object/LockFreeRegistry.pm?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy/Object/LockFreeRegistry.pm (added)
+++ lucene/lucy/trunk/perl/lib/Lucy/Object/LockFreeRegistry.pm Mon Jan  4 22:08:54 2010
@@ -0,0 +1,33 @@
+use Lucy;
+
+1;
+
+__END__
+
+__BINDING__
+
+Clownfish::Binding::Perl::Class->register(
+    parcel            => "Lucy",
+    class_name        => "Lucy::Object::LockFreeRegistry",
+    bind_methods      => [qw( Register Fetch )],
+    bind_constructors => ["new"],
+);
+
+__COPYRIGHT__
+
+    /**
+     * Copyright 2009 The Apache Software Foundation
+     *
+     * Licensed under the Apache License, Version 2.0 (the "License");
+     * you may not use this file except in compliance with the License.
+     * You may obtain a copy of the License at
+     *
+     *     http://www.apache.org/licenses/LICENSE-2.0
+     *
+     * Unless required by applicable law or agreed to in writing, software
+     * distributed under the License is distributed on an "AS IS" BASIS,
+     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+     * implied.  See the License for the specific language governing
+     * permissions and limitations under the License.
+     */
+

Propchange: lucene/lucy/trunk/perl/lib/Lucy/Object/LockFreeRegistry.pm
------------------------------------------------------------------------------
    svn:eol-style = native

Modified: lucene/lucy/trunk/perl/lib/Lucy/Test.pm
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/lib/Lucy/Test.pm?rev=895799&r1=895798&r2=895799&view=diff
==============================================================================
--- lucene/lucy/trunk/perl/lib/Lucy/Test.pm (original)
+++ lucene/lucy/trunk/perl/lib/Lucy/Test.pm Mon Jan  4 22:08:54 2010
@@ -34,6 +34,9 @@
     else if (strEQ(package, "TestHash")) {
         lucy_TestHash_run_tests();
     }
+    else if (strEQ(package, "TestLockFreeRegistry")) {
+        lucy_TestLFReg_run_tests();
+    }
     else if (strEQ(package, "TestI32Array")) {
         lucy_TestI32Arr_run_tests();
     }

Added: lucene/lucy/trunk/perl/t/binding/038-lock_free_registry.t
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/t/binding/038-lock_free_registry.t?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/t/binding/038-lock_free_registry.t (added)
+++ lucene/lucy/trunk/perl/t/binding/038-lock_free_registry.t Mon Jan  4 22:08:54 2010
@@ -0,0 +1,57 @@
+use strict;
+use warnings;
+
+use Config;
+use Test::More;
+BEGIN {
+    if ( $ENV{LUCY_VALGRIND} ) {
+        plan( skip_all => 'Known leaks' );
+    }
+    elsif ( $Config{usethreads} ) {
+        plan( tests => 1 );
+    }
+    else {
+        plan( skip_all => 'No thread support' );
+    }
+}
+use threads;
+use threads::shared;
+use Time::HiRes qw( time usleep );
+use List::Util qw( shuffle );
+use Lucy::Test;
+
+my $registry = Lucy::Object::LockFreeRegistry->new( capacity => 32 );
+
+sub register_many {
+    my ( $nums, $delay ) = @_;
+
+    # Encourage contention, so that all threads try to register at the same
+    # time.
+    sleep $delay;
+    threads->yield();
+
+    my $succeeded = 0;
+    for my $number (@$nums) {
+        my $obj = Lucy::Object::CharBuf->new($number);
+        $succeeded += $registry->register( key => $obj, value => $obj );
+    }
+
+    return $succeeded;
+}
+
+my @threads;
+
+my $target_time = time() + .5;
+my @num_sets = map { [ shuffle( 1 .. 10000 ) ] } 1 .. 5;
+for my $num ( 1 .. 5 ) {
+    my $delay = $target_time - time();
+    my $thread = threads->create( \&register_many, pop @num_sets, $delay );
+    push @threads, $thread;
+}
+
+my $total_succeeded = 0;
+$total_succeeded += $_->join for @threads;
+
+is( $total_succeeded, 10000,
+    "registered exactly the right number of entries across all threads" );
+

Propchange: lucene/lucy/trunk/perl/t/binding/038-lock_free_registry.t
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/lucy/trunk/perl/t/core/038-lock_free_registry.t
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/t/core/038-lock_free_registry.t?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/t/core/038-lock_free_registry.t (added)
+++ lucene/lucy/trunk/perl/t/core/038-lock_free_registry.t Mon Jan  4 22:08:54 2010
@@ -0,0 +1,6 @@
+use strict;
+use warnings;
+
+use Lucy::Test;
+Lucy::Test::run_tests("TestLockFreeRegistry");
+

Propchange: lucene/lucy/trunk/perl/t/core/038-lock_free_registry.t
------------------------------------------------------------------------------
    svn:eol-style = native

Added: lucene/lucy/trunk/perl/xs/Lucy/Object/LockFreeRegistry.c
URL: http://svn.apache.org/viewvc/lucene/lucy/trunk/perl/xs/Lucy/Object/LockFreeRegistry.c?rev=895799&view=auto
==============================================================================
--- lucene/lucy/trunk/perl/xs/Lucy/Object/LockFreeRegistry.c (added)
+++ lucene/lucy/trunk/perl/xs/Lucy/Object/LockFreeRegistry.c Mon Jan  4 22:08:54 2010
@@ -0,0 +1,35 @@
+#define C_LUCY_OBJ
+#define C_LUCY_LOCKFREEREGISTRY
+#include "xs/XSBind.h"
+
+#include "Lucy/Object/LockFreeRegistry.h"
+#include "Lucy/Object/Host.h"
+
+void*
+lucy_LFReg_to_host(lucy_LockFreeRegistry *self)
+{
+    chy_bool_t first_time = self->ref.count < 4 ? true : false;
+    lucy_LFReg_to_host_t to_host = (lucy_LFReg_to_host_t)
+        LUCY_SUPER_METHOD(LUCY_LOCKFREEREGISTRY, LFReg, To_Host);
+    SV *host_obj = (SV*)to_host(self);
+    if (first_time) {
+        SvSHARE((SV*)self->ref.host_obj);
+    }
+    return host_obj;
+}
+
+/* Copyright 2009 The Apache Software Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+

Propchange: lucene/lucy/trunk/perl/xs/Lucy/Object/LockFreeRegistry.c
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message