When CAS is fooled
CAS only checks whether a value equals an expected value, not whether it ever changed. The ABA problem arises when a location holds A, changes to B, then changes back to A. A thread that read A and later does CAS expecting A succeeds, even though the world it assumed is gone. The classic trigger is a freed node being recycled to the same address.
Why it is dangerous
In a Treiber stack, a popper reads head A and its next pointer. Meanwhile other threads pop A, free it, and push it back. Head is A again, but its next now points elsewhere. The original CAS succeeds and head jumps to a stale or freed node, corrupting the structure.
Solutions
Several defenses exist:
- Tagged pointers pack a version counter beside the pointer. Each successful update increments the tag, so A with tag 5 differs from A with tag 7 and a double wide CAS rejects the stale value.
- Hazard pointers prevent the node from being freed and reused while a thread references it.
- Epoch or RCU reclamation defers reuse until no thread can hold the old reference.
- Garbage collected runtimes sidestep ABA on pointers because a referenced node is never recycled.
Key idea
The ABA problem fools CAS when a value returns to its original; tagged version counters, safe reclamation, or garbage collection prevent the stale success.