Subj : Tsigas & Zhang non-blocking concurrent shared-memory FIFO.
To   : comp.programming.threads
From : Kaz Kylheku
Date : Fri Sep 09 2005 02:54 pm

In case anyone is trying to use the algorithms described in the paper,
I think I have found a pointer recycling problem that is not taken care
of. Multiple null pointer values are used to disambiguate recycled
nulls, but the recycling of non-null pointers, the actual queue
elements, isn't addressed at all. A thread trying to dequeue a node
might punch a hole in the middle of the queue, because by the time it
tries the compare-and-swap (but after it has done the tail pointer
consistency check!) the node that it wants may be dequeued by some
other thread, and then re-queued (ABA problem). By chance, that
re-queued node might end up in exactly the same slot in the FIFO; but
that slot will likely no longer be the head of the queue. The
compare-and-swap at that memory location will succeed since the pointer
matches. Oops!

In my implementation, I fixed it by using some spare bits in the
pointer which store a copy of a per-node counter that is incremented
each time a node is enqueued. I have 2^^31 different null values, and
65536 different pointers to the same queue node.

I have lots of bits since the node pointers are really indices into an
array of node structures. In implementations where the node pointers
are actual machine addresses, a lot fewer bits will be available,
subject to the widest alignment you can get away with, or address space
restrictions you can impose.

.