Subj : Re: atomic operations api added to AppCore...
To   : comp.programming.threads
From : Ronald Landheer-Cieslak
Date : Tue Mar 01 2005 04:39 pm

SenderX wrote:
>>Actually, there could be ABA, but it wouldn't be a problem: if a node
>>gets enqued and dequed between the two times I look at it, it will
>>always have been valid anyway, as the associated memory is never freed..
> 
> 
> However, If aba does hit I believe it could corrupt the integrity of the 
> data-structure itself:
> 
> 
> 
> ANCHOR.A->B->C // initial freelist state
> 
> 
> thread a
> ---------
> 1. lf = ANCHOR.front;
> 2. ln = lf->next;
> 3. cas( &ANCHOR.front, lf, ln )
> 
> 
> thread b
> --------
> 1. pops A
> 2. pushes D
> 3. pushes A
This can never happen: we only push a thread'd hazard pointers when the
thread dies - and it only has one set. We only pop it when the thread
first needs them. No thread can first pop then push twice..

> Think if the execution sequence goes something like this:
> 
> a1: ( A->B->C ) lf = A
> a2: ( A->B->C ) ln = B
> b1: ( B->C )  this puts a2 in jeopardy
> b2: ( D->B->C )
> b3: ( A->D->B->C )  this puts a3 in jeopardy
> a3: ( B->C ) corrupted... oh sh^%it!

> a3 corrupts the list because its cas was successful, when it should have 
> clearly failed. I haven't looked at your code in detail so I don't know if 
> you can suffer from this race-condition. 
The current version doesn't: pushing a new node onto the queue will work
in one atomic step only if the queue is empty. Otherwise, the pushing
thread takes posession of everything on the queue (replacing the queue
with a NULL pointer), puts its own node in the queue it just took and
puts the queue back. This is split into two steps so that if, by the
time we put the queue back, some other thread put something in there, we
just put whatever we find there in the queue and start over. That should
pretty much kill the ABA problem:

> a1: ( A->B->C ) lf = A
> a2: ( A->B->C ) ln = B
> b1: ( B->C )  this puts a2 in jeopardy
> b2: ( D->B->C )
> b3: ( A->D->B->C )  this puts a3 in jeopardy
This can't happen: thread b can't push any node it hasn't popped itself
and can't pop more than one node. Once popped, the nodes are owned by
the thread that popped them (so they can't be exchanged outside of the
queue) and aren't put back in the queue until the thread dies. Nodes are
never freed either.

A pop in mid-pop will simply fail; a pop in mid-push will find an empty
queue.

rlc

BTW: Thanks for making me look at this: I did find another little bug,
     and I understand better why I did it this way and why my
     "simplification" won't work.

.