You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by ma...@apache.org on 2010/01/04 23:08:55 UTC
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/
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( \®ister_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