You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucy.apache.org by "Marvin Humphrey (JIRA)" <ji...@apache.org> on 2010/01/01 23:03:54 UTC
[jira] Created: (LUCY-92) Lock-free registry for VTables
Lock-free registry for VTables
------------------------------
Key: LUCY-92
URL: https://issues.apache.org/jira/browse/LUCY-92
Project: Lucy
Issue Type: Improvement
Components: Clownfish, Core - Object
Reporter: Marvin Humphrey
Assignee: Marvin Humphrey
To make Lucy's OO framework thread safe, we must change VTable_registry,
currently a Lucy::Object::Hash, over to a new class,
Lucy::Object::LockFreeRegistry.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (LUCY-92) Lock-free registry for VTables
Posted by "Marvin Humphrey (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCY-92?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marvin Humphrey resolved LUCY-92.
---------------------------------
Resolution: Fixed
Committed as r895799 and r895800.
> Lock-free registry for VTables
> ------------------------------
>
> Key: LUCY-92
> URL: https://issues.apache.org/jira/browse/LUCY-92
> Project: Lucy
> Issue Type: Improvement
> Components: Clownfish, Core - Object
> Reporter: Marvin Humphrey
> Assignee: Marvin Humphrey
> Attachments: lock_free_registry.diff, vtable_registry_hash_to_lfreg.diff
>
>
> To make Lucy's OO framework thread safe, we must change VTable_registry,
> currently a Lucy::Object::Hash, over to a new class,
> Lucy::Object::LockFreeRegistry.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (LUCY-92) Lock-free registry for VTables
Posted by "Marvin Humphrey (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCY-92?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marvin Humphrey updated LUCY-92:
--------------------------------
Attachment: vtable_registry_hash_to_lfreg.diff
lock_free_registry.diff
LockFreeRegistry is a minimalist hash table, purpose built for the needs of
the dynamic subclassing system. Keys can only be inserted once, and cannot be
removed once inserted. The insertion method, Register(), returns false if an
insertion fails because a key already exists. At present, the bucket table is
only allocated once, at startup, which means that performance will degrade if
too many dynamic classes are created. It's possible to fix this, by
introducing a thread-safe rehashing stage (and keeping around all obsolete
bucket tables), but that is left for later.
Collisions are resolved using one singly linked list per bucket. Entry nodes
are not ordered within the linked list and new nodes may only be appended by
an atomic compare and swap on the last current node's pointer. If the CAS
operation fails, the inserter must return to the head of the linked list and
traverse it again, looking for duplicate keys. The loop continues until
either the CAS succeeds and Register() returns true, or a duplicate key is
found and Register() returns false.
Using this algorithm we can guarantee that duplicate VTables for the same
class can never be registered:
{code:none}
Thread #1 Thread #2
======================================= ======================================
Failed to fetch VTable for "Foo" Failed to fetch VTable for "Foo"
from the VTable_registry. from the VTable_registry.
Create VTable for class "Foo". Create VTable for class "Foo".
Attempt to register new VTable. Attempt to register new VTable.
Traverse linked list, no dupes found. Traverse linked list, no dupes found.
Find slot. Find slot.
CAS succeeds, Register() returns true.
CAS fails.
Traverse linked list again; this time,
we find a duplicate key, so
Register() returns false.
Attempt to fetch VTable for "Foo" from
the registry once again. This
time, the attempt succeeds,
retrieving Thread #1's copy.
Discard duplicate, unreferenced "Foo"
VTable, and use the one fetched
from the registry.
{code}
When built with Perl bindings, all LockFreeRegistry objects leak, just like
all VTables leak. This is done because whenever a Perl thread exits, all
destructors get called during "global destruction" phase for that thread -- so
the destructor gets called for shared objects multiple times. We could
probably get around this problem with a little work, but since the only usages
for LockFreeRegistry are the VTable_registry itself and testing, there's no
need.
> Lock-free registry for VTables
> ------------------------------
>
> Key: LUCY-92
> URL: https://issues.apache.org/jira/browse/LUCY-92
> Project: Lucy
> Issue Type: Improvement
> Components: Clownfish, Core - Object
> Reporter: Marvin Humphrey
> Assignee: Marvin Humphrey
> Attachments: lock_free_registry.diff, vtable_registry_hash_to_lfreg.diff
>
>
> To make Lucy's OO framework thread safe, we must change VTable_registry,
> currently a Lucy::Object::Hash, over to a new class,
> Lucy::Object::LockFreeRegistry.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.