1614
Subj : Re: Question for mr lockfree :)
To   : comp.programming.threads
From : Ronald Landheer-Cieslak
Date : Tue May 17 2005 03:14 pm

SenderX wrote:
>>As far as the ABA problem is concerned, I kinda like M.M. Micheal's
>>"Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
>>Reads and Writes" (PODC 2002 July 21-24, 2002), which I've implemented
>>in libmemory (http://jail-ust.sf.net/index.php?section=3&page=2). It
>>isn't very well-tested yet (mostly due to lack of time) but it should
>> work..
> It should work, and it would avoid aba 100% of the time.
> 
> However, you have to do a lot of bookkeeping IMHO, per-thread lists, bin
> sorting them, iterating them and comparing against per-thread
> hazard-pointers, tracking of the participating threads, and ( i think )the
> amount of hazards per-thread is static...
For the time being, it is. I have yet to find a "proper" way to reliably
grow the number of per-thread hazard pointers without stopping the world..

> Could a thread reference more nodes than there are hazards per-thread?
Only for nodes it has created itself and has not linked into a list,
array, vector, binomial tree, ..., yet

>> That is basically also the reason why I don't need a DCAS in libcontain
>> (for the moment) but the problem is that I have a race condition in my
>> vector implementation - which I was hoping you wouldn't have in yours..
>> I.e., you don't have the same problem because you use a realloc to
>> resize your array, which you apparently assume to be atomic.
> Yes, the Array API is NOT thread-safe in anyway, shape or form.
Right - that explains why I couldn't find that "atomic realloc
implementation" anywhere :)

>> but I'd be interested to know why using realloc on the array is not a
>> problem, in your opinion/implementation.
> I just never got around to putting the proxy gc code in there..
:)

>> I haven't had the time to look at your code in detail yet - mostly
>> because it doesn't compile /chez moi/ so I can't run the tests on it,
> You need platform sdk and vc++ 6.0. What errors/warnings do you get?
I have VC .NET. I don't remember the errors I got, but I'll have a look
when I have the time.

>> I've been pondering making a readers/writers lock and only counting
>> resize() as a writer, but that would kinda defeat the idea of being
>> lock-free..
> You can do a fast rw-lock with double-wide cas.
Would you care to elaborate that a bit?
Would that be a spinlock or would you use a couple of mutexes, split
binary semaphores, condvars or some other such lock somewhere?
(If you know of a lock-free implementation other than Joe Seigh's
rw-spinlock, I'd be interested :)

> P.S.
> 
> Here is some pseudo-code for my old collector:
> 
> 
> 
> /* Lock-Free Proxy Garbage Collector
> /**************************************
> 
> 
> struct node
> {
>     struct node *pNext;
>     struct node *pGcNext;
>     const void *pState;
>     void ( *fpDtor ) ( void* );
> };
> 
> 
> /* Must fit into double-wide cas for your specific cpu! */
> struct gc
> {
>     struct node *pTrash;
>     unsigned __int16 Proxy;
>     unsigned __int16 Aba;
> };
> 
> 
> void AddRef( struct gc *pThis )
> {
>     do
>     {
>         read old and local copys
> 
>         increment local.Proxy
>     }
> 
>     while ( ! dwide_cas( pThis, old, local ) ); // Acquire membar
> }
> 
> 
> void Collect( struct gc *pThis, struct node *pNode )
> {
>     do
>     {
>         read old and local copys
> 
>         push pNode onto old.pTrash
>     }
> 
>     while ( ! dwide_cas( pThis, old, local ) ); // Release membar
> }
> 
> 
> void Release( struct gc *pThis )
> {
>     do
>     {
>         read old and local copys
> 
>         decrement local.Proxy
>         increment local.Aba
> 
>         if ( local.Proxy == 0 )
>         {
>             local.pTrash = 0;
>         }
>     }
> 
>     while ( ! dwide_cas( pThis, old, local ) ); // Release membar
> 
>     if ( local.proxy == 0 )
>     {
>         we have hit a quiesent period! Flush the callbacks.
> 
>         iterate through the nodes and call node.fpDtor( node.pState ) for
> each.
>     }
> }
> 
> 
> 
> Then you would use it like:
> 
> 
> /* Lock-Free Stack
> /**************************************
> 
> typedef struct node lfstack;
> typedef struct gc lfstack_gc;
> 
> 
> void LockFreeStackNodeDtor( void *pNode )
> {
>     free( pNode );
> }
> 
> 
> void LockFreeStackPush( lfstack *pThis, const void *pState, )
> {
>     pNode = malloc( sizeof( *pNode ) );
> 
>     pNode->pNext = pNode->pGcNext = 0;
>     pNode->pState = pState;
>     pNode->fpDtor =  LockFreeStackNodeDtor;
> 
>     do
>     {
>         read old and local copys
> 
>         push pNode onto old
>     }
> 
>     while ( ! normal_cas( pThis, old, local ) ); // Release membar
> }
> 
> 
> void* LockFreeStackPop( lfstack *pThis,  lfstack_gc *pGc )
> {
>     AddRef( pGc );
> 
>     do
>     {
>         read old and local copys
> 
>         if empty { return 0; }
> 
>         pop front off old
>     }
> 
>     while ( ! normal_cas( pThis, old, local ) ); // Release membar
> 
>     Collect( pGc, popped_node );
> 
>     Release( pGc );
> }
> 
> 
> That's basically it, and I bet you can get it working from this pseudo-code.
> Also, notice how you don't have to use double-wide cas for the stack?
> 
> I will try to post the assembler very soon.
Thanks - I'll have a closer look at it when I have time (which I don't
really have the moment...

rlc

.

0