the ABA problem
/ AY-BEE-AY /
Imagine you glance at a parking spot, see a red car, look away to do something, glance back, and again see a red car. You conclude nothing changed. But in between, that red car left and a DIFFERENT red car parked there. To your eyes it looks identical, yet the world moved. The ABA problem is exactly this trap, and it is the single most famous pitfall in lock-free programming. The name comes from a value going A, then B, then back to A.
Here is why it bites. The CAS retry loop assumes that if the value is still the old value you read, then nothing has changed since your read. But CAS only checks that the bits are equal — it cannot tell the difference between never changed and changed away and changed back. Concretely, with a lock-free stack: thread one reads head = node A and computes that the new head should be A's successor. Before its CAS runs, thread two pops A, pops B, frees B, then pushes A back — so head is A again, but A's next pointer now points at freed-and-reused memory. Thread one's CAS sees head == A, succeeds, and installs a pointer into garbage. The bits matched; the meaning did not.
The fixes all add information that the raw bits lack. A tagged or versioned pointer pairs the pointer with a counter that increments on every change, so A-version-1 and A-version-3 no longer compare equal — this usually needs a double-width CAS (compare both the pointer and the tag in one atomic step, e.g. cmpxchg16b on x86-64). LL/SC sidesteps ABA entirely because it detects the intervening write rather than the value. And the deeper cure is safe memory reclamation — hazard pointers or epochs — which guarantees node A is never freed and reused while another thread might still be looking at it, so the dangerous reuse cannot happen in the first place.
/* Timeline that fools a CAS on a lock-free stack: */ T1: read head = A; plan to set head = A->next (which is B) T2: pop A, pop B, free B, push A /* head is A again, A->next now stale */ T1: CAS(&head, A, B) succeeds /* B was freed! head now points to garbage */ /* Tagged-pointer fix: compare {ptr, counter} together */ struct tptr { Node *ptr; uintptr_t tag; }; /* CAS the whole 16-byte pair */
CAS sees A == A and succeeds, but the A it sees is a different incarnation; a version counter or hazard pointers prevent the silent reuse.
ABA is not a memory-corruption bug per se — it is CAS succeeding on bits that are equal but no longer mean the same thing. It only manifests when memory can be freed and reused, which is why safe reclamation is the deepest fix.