This post documents my understanding on ABA problem in lockfree programming.
The wikipedia entry presents a concrete example on how ABA could occur in naive usage of CAS for lockfree programming. The step-by-step reproduce of erroneous situation is easy to follow even for those who have no prior C++ knowledge.
The intended logic for pop is to swing
top → A → B → C
However, right before the swing happens, the state of the stack is subject to change, which
pop fails to capture, resulting into that
B is pointed
by the new
top → A → C
The illegal access to collected memory could be avoided if a GC is used instead of manual memory management, but the implementation is still
problematic, for the CAS would put
B in the stack again, even though it has been popped by thread 2.
It’s a common misconception that all ABA problems go away after using GC, and the example in the wiki page is a counter example.
On the other hand, it’s always possible to write lockfree code without ABA problem with GC, using one level of redirection. See more at https://www.research.ibm.com/people/m/michael/RC23089.pdf
The following is a lockfree stack implementation in C assuming a proper GC. It is ABA immune because for each element inserted into the stack, we create a wrapping node around it, and assumed GC wouldn’t reuse a node unless it’s unreachable.
From the same author, http://dl.acm.org/citation.cfm?id=987595 presents a alternative way to GC, so that ABA problems eliminated by GC would not appear using Hazard pointers as well.