Expand description
§Lightweight lock-free stack implementations
It is surprisingly difficult to correctly use and implement a lock-free stack that provides the standard push/pop interface.
In particular, pop has to traverse a pointer to obtain the next node in the stack. It is possible that the target of the pointer changes in race (due to multiple concurrent stack pops), or even that the old head was popped and deallocated and then a new entry with the same address was allocated and pushed back on as the head of the stack. At this point a compare and swap of the old head with the new one would incorrectly succeed, leading to an instance of the “ABA problem.”
Naive stack algorithms suffer from the following ABA issue: It is possible for pop() to read the head pointer “A”, then be descheduled. In race, the head pointer and some other values are popped, then a node with the same memory address as A is pushed back onto the stack. The CAS will succeed, even though the current value of head is semantically distinct from the value the lambda read.
Stack avoids this by providing a pop_all method that removes everything
from the stack atomically. This guarantees read set equivalence because it
does not read anything other than the CAS bits.
NonceStack uses a nonce to ensure that no pushes have been performed
in race with pop, which probabilistically guarantees that head was not popped
then pushed back on to the stack in race with a pop.