The question this answers
The CAS succeeded and the value was exactly what I expected — how can the structure still be corrupt?
A consumer popping from the lock-free stack while other consumers pop two nodes and push the first one back.
The head pointer, and the node memory it points at — including memory that may be freed and reallocated.
Every node is returned by at most one pop, and head always points at a node currently in the stack.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
A becomes B becomes A
The CAS contract is precise and narrower than it feels: it writes if the location *holds the expected value*. Programmers read it as "if nothing has changed since I looked", and those are different statements. Between your load and your CAS, the location can change any number of times and end up back where it started, and the CAS cannot tell.
For a counter that is harmless — 5 becoming 6 becoming 5 leaves a perfectly usable 5. For a pointer it is not, because the pointer is not the state; it is a *name* for state that lives elsewhere. The same address can be a different node, a freed node, or the same node in a different position in the list. The schedule below is the canonical instance, on the pop from A Lock-Free Stack, and What the Teaching Version Omits.
The step to watch is the last one. The CAS succeeds, no error is raised, and the stack now has its head pointing at a node that was already popped and handed to a caller. The next pop returns that node a second time — the same work item processed twice, which downstream looks like a duplicate charge, a duplicate email, a duplicate row.
| # | Consumer 1 | Consumer 2 | State |
|---|---|---|---|
| 1 | load head -> A; read A.next -> B | · | head=A stack=A -> B -> C C1.expected=A C1.next=B |
| 2 | · | pop A (CAS head A -> B) success; returns A to its caller | head=B stack=B -> C |
| 3 | · | pop B (CAS head B -> C) success; returns B to its caller | head=C stack=C |
| 4 | · | push A back (its work was rejected and requeued) | head=A stack=A -> C A.next=C |
| 5 | resumes; CAS(head, expected=A, desired=B) -> SUCCESS | · | head=B stack=B -> ??? ✕ head now points at B, which C2 already popped and handed to a caller. Node C is unreachable. If B was freed, head points at freed memory. |
| 6 | returns A to its caller | · | note=A is now held by two callers ✕ A was returned by C2's pop and again by C1's pop. The same work item will be processed twice. |
Why a pointer is a name, not a state
The generalisation worth carrying out of this lesson: CAS compares a value, and you are usually reasoning about the state that value refers to. Whenever the value is an index, a pointer, a slot number, a generation-less id or a recycled handle, equality of the value is not equality of the state. The gap between them is exactly the ABA problem, and it is not confined to lock-free data structures.
The same shape appears far above this layer. A worker checks that job 42 is still in state PENDING and claims it — but job 42 was completed, retried, and re-created as PENDING by a supervisor in between, so the claim succeeds against a different logical job. A cache entry is validated by key presence when the entry was evicted and repopulated. An optimistic update checks a value rather than a version. See Optimistic Concurrency Control.
Memory reuse is what makes the low-level version so easy to hit. Allocators are good at handing back the address they just freed, so a popped-and-freed node very often reappears at the same address moments later. An address is one of the least stable identities available, which is why the fixes below all amount to attaching an identity that does not get recycled.
Categories of fix, and what each one costs
There is no way to make CAS compare the world instead of the value, so every fix either makes the value carry more identity or prevents the reuse that creates the ambiguity. Those are the two families, and knowing they exist is more useful than being able to implement either from memory.
Adding identity means version-tagging: store a counter alongside the pointer and increment it on every modification, so a pointer that leaves and returns comes back with a different tag and the CAS fails. This needs an atomic wide enough to hold both — double-width CAS where available, or pointer bits stolen from an aligned address, which caps the number of versions and reintroduces the problem after wraparound. It is a real fix with real limits.
Preventing reuse means a reclamation scheme: hazard pointers, where each thread publishes what it is currently reading and reclamation skips those; epoch-based or quiescent-state reclamation, where a node is freed only once no thread could still hold a reference from a prior epoch; or RCU. A tracing garbage collector gives you the same effect for free, which is why this problem is much smaller in Java, C# and JavaScript — but note carefully that a GC removes the *use-after-free*, not ABA itself. If your algorithm can legitimately re-push the same live object, as C2 does above, the tag is still required.
| Approach | What it changes | What it costs | Where it still fails |
|---|---|---|---|
| Version-tagged pointer | CAS compares pointer + counter, so a returning pointer has a different tag | Needs double-width CAS or stolen alignment bits; the wider CAS is slower | Counter wraparound recreates ABA, just far more rarely |
| Hazard pointers | Each thread publishes what it is reading; reclamation skips published nodes | A store and a fence on every read; per-thread published slots; a scan before freeing | Bounded memory but a slower read path; complex to implement correctly |
| Epoch / quiescent-state reclamation | Nodes are freed only once every thread has passed through a quiescent point | Cheaper per operation than hazard pointers | A thread stalled inside a critical region halts reclamation — unbounded memory growth |
| RCU | Readers are free; writers publish new versions and defer reclamation | Writer-side complexity; requires a well-defined quiescent state | Read-mostly workloads only; write-heavy use defeats it |
| Tracing garbage collector | A referenced node is never reclaimed, so the address cannot be recycled underneath you | GC pauses and memory overhead; not available in C++ or Rust | Does NOT prevent ABA on a live object that is legitimately removed and re-added |
| Do not hand-write the structure | Use a reviewed library, or a mutex | A lock, and the progress guarantee you may not have needed | Nothing — this is the right answer for most code |
Key points
- CAS compares a value. It does not and cannot compare the state that value refers to.
- A pointer, index or handle is a name, not a state — and allocators eagerly reuse the address they just freed.
- The consequence in a lock-free stack is a node returned by two pops: the same work item processed twice, with no error anywhere.
- Fixes fall into two families: attach identity that does not recycle (version tags), or prevent reuse (hazard pointers, epochs, RCU, a GC).
- A garbage collector removes the use-after-free half but not ABA itself — a live object legitimately removed and re-added still defeats value equality.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • A thread loads the shared value A and reads state reachable from it, then stalls for any reason at all.
- • Other threads change the value to B, doing whatever restructuring that implies, and then change it back to A — usually because A was freed and reallocated, or because A was legitimately re-inserted.
- • The first thread resumes and performs its CAS with expected = A. The comparison succeeds because the bit pattern matches.
- • The write commits a decision computed from state that no longer exists — a stale
nextpointer, a stale index, a stale assumption about what the slot contains. - • Nothing reports an error, because from CAS's point of view nothing went wrong.
- • C1 loads head=A, next=B, stalls; C2 pops A, pops B, pushes A; C1 CAS(A -> B) succeeds; head points at the already-popped B and node C is lost.
- • Same trace with a version tag: C1 loads (A, tag=7); C2's three operations leave (A, tag=10); C1 CAS expecting (A, 7) fails and retries against the real state. Invariant holds.
- • Same trace under a tracing GC: B is not freed while C1 holds a reference, so there is no use-after-free — but head still points at a node C2 already returned, so the duplicate-pop bug survives.
- • Counter version, no pointers: v goes 5 -> 6 -> 5 and a CAS expecting 5 succeeds. Harmless, because the value *is* the state. This contrast is the whole lesson.
- • Job queue version: worker loads job 42 status PENDING; supervisor completes it and re-creates job 42 as PENDING; worker CAS-claims a logically different job. Same bug, no atomics involved.
- • Promises: the CAS compared the value you gave it against the value present, indivisibly, and wrote only on a match.
- • Does NOT promise: that the value was unchanged throughout the interval — only that it matched at the instant of the compare.
- • Does NOT promise: that anything reachable through the value is unchanged. This is the entire problem.
- • Does NOT promise: that a pointer identifies the same logical object across a free and a reallocation.
- • Version tags promise: a returning value is distinguishable — up to counter wraparound, which is a real bound and not a theoretical one on narrow tags.
- • Hazard pointers and epochs promise: no reclamation of a node a thread may still be reading. They do NOT promise freedom from ABA on objects that are legitimately re-inserted.
- • Version tags increase the width of the contended word, and a double-width CAS is more expensive per attempt than a single-width one.
- • Hazard pointers add a store and a fence to every read, which turns a previously read-only path into one that generates coherence traffic. See What a Shared Write Costs.
- • Epoch schemes concentrate contention on the epoch counter itself, which becomes a second hot location.
- • Every defence makes the operation more expensive, which is another way of saying the progress guarantee has a price you keep paying after you have bought it.
- • Duplicate processing — the same item returned by two pops, producing duplicate side effects downstream unless every consumer is idempotent.
- • Lost items — a node made unreachable by a CAS that applied a stale link, leaking silently.
- • Use-after-free — dereferencing a node reclaimed between the load and the use; usually crashes somewhere unrelated.
- • Cycle creation — a stale link applied to a restructured list producing a loop, so a subsequent traversal never terminates.
- • Silent corruption with no error path at all, which is why this is diagnosed from downstream symptoms rather than from the structure.
- • Wraparound recurrence — a 16-bit tag on a hot structure wraps in seconds under load, restoring the bug with a rarer trigger.
- • As a review question with a very high hit rate: "what happens if this value goes away and comes back?" applied to any CAS, any optimistic claim, any check-then-act on an id.
- • As the reason to prefer a monotonically increasing version over a value comparison everywhere — in memory, in a database row, in an HTTP If-Match. See Conditional Requests: ETags, 304 and 412.
- • As the argument that settles whether to hand-write a lock-free structure: if the team cannot state the reclamation scheme, the answer is no.
- • When the fear of ABA is applied to a plain counter, where the value is the state and 5 -> 6 -> 5 is genuinely fine.
- • When it motivates tag bits stolen from pointers in code that will be ported to an architecture with different alignment or pointer-authentication guarantees.
- • When it motivates a hand-rolled hazard-pointer scheme instead of a library or a mutex, which trades a rare bug for a permanent maintenance burden.
- • Count downstream duplicates against upstream enqueues. A small, load-correlated excess of processed items over produced items is the signature.
- • Run under AddressSanitizer: the use-after-free half is exactly what it detects, and it will fire close to the cause rather than at the eventual crash.
- • Add a per-node generation counter used only for assertions in debug builds — pop asserts the generation matches what it expected, and the assertion fires on the ABA path.
- • Stress with an allocator configured to reuse addresses aggressively, plus deliberate delays between the load and the CAS, since the bug needs both reuse and a wide window. See Stress Testing: A Test That Passed Once Proves Nothing.
- • Do not expect a thread sanitizer to find it. Every access here is a correctly synchronized atomic; there is no data race to report. See Race Detectors: What They Find, and What They Structurally Cannot.
- • Choosing a defence means owning a reclamation scheme with its own tuning, its own failure mode, and its own worst case.
- • A version tag makes the atomic word's layout part of the structure's contract, and it caps how many modifications can occur before the guarantee weakens.
- • The bug is undetectable by the tools teams already run, so preventing it depends entirely on someone knowing to look — which makes it a knowledge dependency rather than a tooling one.
- • Every defence slows the common path in exchange for a rare correctness case, which is a trade that needs to be stated explicitly rather than discovered in a profile.
- • A mutex. There is no ABA problem when the structure cannot be modified while you hold it. See Mutexes: What They Protect and What They Do Not.
- • A monotonically increasing version or sequence number in place of value comparison, everywhere the identity can be recycled. See Optimistic Concurrency Control.
- • A reviewed library implementation whose reclamation scheme is already correct and already tested.
- • A bounded ring over preallocated slots with monotonically increasing indices — indices that never wrap within the structure's lifetime cannot come back. See Bounded vs Unbounded Queues.
- • A garbage-collected language for this component, if the structure genuinely needs to be lock-free and the reclamation problem is the obstacle.
compare_exchange in a loop — retries, and the pointer that lied
do {
old = counter.load(); # 1 read
next = old + 1; # compute off to the side
} while (!counter.compare_exchange(old, next)); # swap only if unchanged| # | T1 — pop() via CAS | T2 — another thread | State |
|---|---|---|---|
| 1 | old ← head (= A) | · | head=A stack=A→B→C |
| 2 | · | pop() → A | head=B stack=B→C |
| 3 | · | pop() → B | head=C stack=C |
| 4 | · | push(A) | head=A stack=A→C |
| 5 | CAS(head, A, B) → SUCCESS | · | head=B stack=B→ freed ✕ head now points at B, which was popped and freed. Node C has vanished from the stack and T1 returned a node it never observed being on top. |
| 6 | return A to the caller | · | head=B stack=corrupt |
A lock-free stack, one head pointer
push(node): pop():
do { do {
t = head; t = head; if (t == null) return null;
node.next = t; n = t.next;
} while (!CAS(&head, t, node)); } while (!CAS(&head, t, n));| # | Pusher 1 — push(X) | Pusher 2 — push(Y) | Popper — pop() | State |
|---|---|---|---|---|
| 1 | t ← head (= A) | · | · | head=A stack=A→∅ |
| 2 | · | t ← head (= A) | · | head=A stack=A→∅ |
| 3 | X.next ← t (= A) | · | · | head=A stack=A→∅ |
| 4 | · | Y.next ← t (= A) | · | head=A stack=A→∅ |
The lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
What people believe, and what is true
The CAS succeeded, so nothing changed while I was away.
It means the value matched at that instant. The value can have changed arbitrarily and returned, and everything it points at can be different.
ABA only matters in lock-free data structures.
Any check-then-act on a recyclable identity has the same shape — job ids, cache keys, slot numbers, file descriptors. The lock-free stack is just where it is easiest to demonstrate.
We use a garbage-collected language, so ABA cannot happen.
The GC prevents the address from being recycled while you hold a reference, which removes the use-after-free. It does nothing about a live object being removed and re-added, which is still ABA.
Go deeper
Overview
The value you compared went away and came back. CAS saw a match and wrote, but the thing the value referred to is not what you read.
Practical
Ask of every CAS: can this value be recycled? For a counter, no — the value is the state. For a pointer, index or id, yes, and you need a version, a reclamation scheme, or a lock.
Advanced
Hazard pointers give bounded memory and a slower read path; epoch reclamation gives a fast read path and unbounded memory if any thread stalls in a critical region. That is the real trade, and it is the same latency-versus-memory decision that appears in A Lock-Free Stack, and What the Teaching Version Omits.
Internals
The problem is named for the IBM 370 compare-and-swap literature of the 1970s, where it was documented alongside the instruction itself. Tagged pointers were the original answer and remain the standard one where double-width CAS exists; hazard pointers (Michael, 2004) were the answer for platforms where it does not.