Subj : Re: atomic operations api added to AppCore...
To   : comp.programming.threads
From : Ronald Landheer-Cieslak
Date : Wed Feb 23 2005 09:29 pm

awaken wrote:
> Hey Mr.Lockfree!
> 
> Have you ever implemented Hazard pointers and Michael's deque (based on
> CAS64 and haz.pointers)
> I'm trying to implement this algo but have poor understanding of some
> tricks with memory, and how hazard pointers work
> 
> To use CAS64 on Intel, I packed 2 32bit head and tail pointers together
> with queue status flag. it shares 2 lowest bits with one of the pointers.
I've found the algorithm (easy enough) and am implementing it now.

Basically, you need *a* memory management system for this, but you could 
do it with a 32-bit CAS and hazard pointers without too much trouble: 
the hazard pointers would be necessary only to make sure you don't 
re-use a node while you shouldn't.
The way I'm implementing it now limits the deque to 32768 (2^15) nodes, 
which should be enough for most purposes: I allocate pointers for the 
nodes when the deque is first allocated in a simple, fixed-size array 
and keep the status (l,r,s) in a 32-bit structure containing a 15-bit 
index for both the left and right node (hence the limit of 32768 nodes) 
- the index points in the array allocated in the beginning - and the 
status on two bits.
The nodes are allocated as needed and placed in the array using a first 
CAS(NULL, &new_node, nodes[n]). For freeing a node, I do an atomic_swap 
to get the node and set nodes[n] to NULL, then use SMR to free the node.

I've got deque_push_back finished for now. You can take a look at it at 
http://cvs.sourceforge.net/viewcvs.py/jail-ust/libcontain/ (should show 
up within 24 hours - you can also just check out libcontain from CVS, if 
you want).

Personally, I don't like DWCAS much so if I can avoid it, I do. This 
implementation (which, I should note, is GPL/BSD double-licensed, but 
any significant contribution gets a GPL waiver)  won't need anything 
more than a CAS...

HTH

rlc

.