The risk here is that threads can complete operations in the time between saving the old state of the data structure (e.g. the target top of the stack) and the CAS succeeding. In this case, in the absence of thread 1 doing anything, thread 0 has actually computed the correct result (A popped off the stack). But thread 1 tried to push 2 items onto the stack in the middle of thread 0's pop, between the time where thread 0 decided where the next top would be and the pop actually occurring (i.e. top set to B). So our stack has lost these two pushed elements from thread 1 and we also probably leak the memory :O

The "ABA" problem arises due to the compare and swap checking for whether the top is equivalent to the address old_top: this is used to check if the stack has changed, but there is a pathological case where the stack has changed significantly but a (new) value is placed & set as the head where old_top was earlier. The solution to this involves using a mythical double_compare_and_swap for two values, which doesn't exist -- BUT, x86 does have a "double wide" 64-bit compare and swap instruction, which we could use if we ensure that the stack's count and top fields are contiguous in memory.

@ghostcow -- thanks, this explanation is really clear and we can see why it's called the "ABA" problem.

I thought that if we instead did a compare and swap of the top two values this would resolve the ABA problem, but I think that it would instead push the problem further down the stack. As it would then be possible for the top two elements to be removed and changes to happen on the stack and then the top two elements are pushed back on the stack. In which case the ABA problem occurs again.

Yeah, I think the only way around it is to have an independent piece of data that can't be the same for two different states of the data structure (even if that's just a counter of successful operations so far) since otherwise you are always just pushing the problem down the line and just making it more of an edge case rather than eliminating it.