Re: [Algorithms] lock-free stack with hazard list performance

[Stephan R. <ke...@so...>]

On Tue, 2009-04-21 at 17:23 -0700, Nicholas "Indy" Ray wrote:
> On Tue, Apr 21, 2009 at 4:28 PM, Stephan Rose <ke...@so...> wrote:
> > 2. Remove Node A and delete it. Major crash right there when thread 1
> > now tries do it's CAS.
> 
> Here is where I am confused, shouldn't the CAS be on the head pointer
> during a dequeue so, that if the CAS is successful (assuming that
> dequeue is the only way to get a reference to an item on the list,
> which is how lock-free queues should be anyways) you know that you are
> the only thread that has access to the node?

To get a reference to an item on the list you're correct, you have to
dequeue it and then it solely belongs to the thread that dequeued it and
there are no issues. That isn't the problem.

The problem are the nodes that make up the list and the references to
them. See below for an example.

> 
> > Both problems can be solved by ensuring that Node A is not recycled nor
> > deleted until all threads release their reference to it. All lock-free
> > implementations so far I've found have been in managed languages such as
> > C# or Java for that reason so far as the GC ensures exactly that.
> 
> Again, not sure why multiple threads have reference to nodes still on the queue.

Well first off, the node declaration itself is simple:

template <typename T>
struct Node
{
  T data;
  Node* next;
}

Simple enough, nothing fancy.

Now the stack is initialized with a dummy head node that contains no
data and initially next = 0.

Now here is what happens, I'll prefix each line with the thread that's
executing it such as T1, T2, etc. Code is simplified for clarity.

T1 Wants to pop a node off the stack.

T1: Node* node;
T1: do {
T1:   node = head->next; 

Next, T1 gets preempted and it's T2's turn, it also wants to pop a node
off the stack.

T2: Node* node; 
T2: do {
T2:   node = head->next; 

Both T1 and T2 are now referencing the same node and are both trying to
pop the same node off the stack.

T2: } while(!cas(head->next, node, node->next); 

T2 is not preempted and succeeds with its CAS and now proceeds to delete
the node.

T2: delete node; 

T2 is now done, control returns to T1 which is still pointing at the
very node that was just deleted.

T1: } while(!cas(head->next, node, node->next);
T1: CRASH!

And it doesn't matter if this is running on 1 core, or multiple cores,
the above will happen when multiple threads try to pop a node from the
same stack if access to the current node is not guarded to prevent too
early deletion.

Stephan