ABA Problem
The ABA problem fools a CAS-based algorithm: the value changed away and back to the expected value, so the swap succeeds even though the intermediate change invalidates the assumption.
Definition
The ABA problem arises in compare-and-swap algorithms when the observed value A is changed to B and back to A between the read and the CAS. The comparison succeeds, but the algorithm assumption — nothing changed since I read it — is false: memory was freed and reallocated, or a list node reused. Versioned pointers with tag bits and hazard pointers are the countermeasures.
Context and scope
Classic in lock-free stacks with node reuse and in memory reclamation for lock-free structures. Also bites lock-free algorithms that treat pointer equality as state equality.
Common misconceptions
- ABA only affects lock-free stacks — any CAS loop equating value equality with no-change is exposed
- Garbage collection solves ABA — GC prevents use-after-free but not logical ABA on reused values in pools or indices
- Tag bits fully solve it — bounded tags can wrap; hazard pointers and epoch reclamation address the root reclamation issue
Anti-patterns
- Building a lock-free stack over a free list that recycles nodes, reintroducing the same pointer for different content
- Comparing 32-bit sequence counters with wraparound assumptions in long-running systems
- Treating pointer equality as logical identity in algorithms over memory managed outside GC
Related concepts
Related examples
Authoritative source
What it is
CAS checks equality of a value, not absence of change. If the world went A then B then back to A, the CAS proceeds as if the world stood still. Correctness depends on what changed in between: a freed node reallocated as a different logical element makes pointer equality meaningless.
How it works
In the canonical stack pop: thread reads top A; another thread pops A, pushes B, pushes A again — the same node. The first thread CAS succeeds and links through A next pointer, which may now belong to another logical chain. Fixes: versioned pointers where tag increments on every change; hazard pointers and epoch-based reclamation defer freeing while readers hold references.
When to consider
Whenever converting a CAS success into structural conclusions about memory. Managed runtimes remove the free-and-reuse variant but pools, slots, and index reuse reproduce logical ABA.
Pitfalls
Tag widths wrap: a 16-bit tag in a very hot structure eventually revisits zero. Hazard pointers add per-reader bookkeeping cost; epochs add latency to reclamation. Prefer established libraries — hand-rolled fixes to ABA have a long history of subtle failure.