Question: Who can describe how this fixes the bug in the code from slide 21?

The bug in slide 21 is fixed as, if some other thread (thread 1) pops out contents before (thread 0) pop finishes and modifies the stack and pushes the old_top (A in slide 22) back, the pop_count must have changed and the thread 0 pop will fail.

Issue was that when pop happens, the old_stack_top->next was no longer the next node in stack, with pop counts accounted for, we ensure this.

The problem in the code in slide 21 is that the change in the stack below the top and the current size of the stack are not taken into account. The code here takes the size into account where it updates and verifies the same in a single exclusive operation using double_compare_and_swap. In such a case the problem of missing D as in slide 22 cannot happen as the size of the stack is 3 now instead of expected 2 for the thread that pops A.

@rojo. Good, except by "size" I think you meant operation counter pop_count.

We have brought about versioning here so the pop count changes had any change occurred and cuts us through

@kayvonf Yes. I meant pop_count :-). Versioning is also a good idea - maintain another entry in the node that updates the version number. But I guess this should also be updated atomically perhaps using double_compare_and_swap.

I think this would work as well if you stored top->next instead of pop_count in the stack struct?

You could do a 64 bit compare_and_swap with top and top->next and old_top and old_top->next. The advantage of using top->next is that you don't have to worry about pop_count exceeding the max int value (although you would have to make a whole lot of pops to have to start worrying about that).

I'm a little confused. What happens if I try to pop A from AB and before the operation completes, I succeed on pushing A and B so that the stack looks like ABAB. Wouldn't the pop_count still be the same and we end up with B rather than BAB?

@yuel1 a stack that looks like ABAB is not possible. Remember that the "A"s and "B"s here represent addresses, since we are doing compare and swaps on pointers to nodes.

The ABA problem happens when one thread, T1, wants to pop a node with address A, sees that the next node in the stack has address B, but before it gets to pop, some other thread T2 comes in, pops the node with address A, does some other modifications to the list, and then pushes a new node that happens to have the address A back onto the stack.

At this point, T1 comes back in to complete its pop, sees that the top of the stack is still a node with address A and assumes from that information alone that the stack has not been modified. It is unaware that the next node in the stack is no longer the node with address B and thus incorrectly sets the new top of the stack to be the node with address B.

@yuel1: As @Kapteyn rightly pointed out, a stack that looks like ABAB or BAB is not possible because A, B, C and D here are node addresses and not the values stored in the stack.

@Kapteyn: Your (old_top, new_top) compare-and-swap idea was what I thought of initially too. I think it works for the same reason that a hand-over-hand locking mechanism works. The push and pop operations only ever modify the current node and the next node.

It's worth noting that this implementation does not solve the ABA problem if the same node is allowed to be pushed onto the stack twice.

For example, if our stack looks like (top) A B C (bottom) and A is pushed on again, then our version of double_compare_and_swap with pop count would not catch the ABA problem. However, our stack implementation does not allow this to happen since A will have a self loop in this case.

@kk: I'm not sure that can happen if A, B, C ... represent addresses. If the stack is a linked list, pushing A onto the stack multiple times is the same thing as creating a loop, in which case you have bigger problems. In the case of an array-based stack, you can't have sequentially numbered pieces of memory that have identical addresses.

It is an interesting example though. I think it still applies if we're talking about an implementation where A, B, etc. aren't actually addresses.

I just came across the lock-free stack implementation in the open source .NET framework. (https://github.com/dotnet/coreclr/blob/master/src/mscorlib/src/System/Collections/Concurrent/ConcurrentStack.cs) I guess it is a good example of how lock-free data structures are implemented in production. The comment at the beginning of the source file also gives an explanation why the ABA problem is not possible in CLR.