The ABA problem

The problem it solves

Compare-and-swap promises that your write only lands if nothing changed. That promise is not quite what it appears to be, and the gap is called ABA.

CAS compares values. If a location holds A, changes to B, and changes back to A while you were away, your CAS sees A — exactly what you expected — and succeeds. Two changes and no changes are indistinguishable to it. For a counter that is harmless, because a counter that returns to its old value genuinely is in its old state. For a pointer, it is a disaster: the address is the same and the object it points at has been freed, reused, or moved to a different position in a structure that has been rearranged underneath you.

This is the failure that makes lock-free programming genuinely difficult, and it is why the honest advice is to use a library. It is also a very good interview question, because the answer requires holding a sequence of events in your head rather than reciting a definition.

The mechanism

Take a lock-free stack. To pop, you read the head, read that node’s successor, and CAS the head from the node you saw to its successor.

head = load(top)
next = load(head.next)
CAS(top, head, next)

Thread 1 gets as far as reading head (node A) and next (node B), and is then descheduled. While it is away, thread 2 pops A, pops B, and pushes A back. The stack is now A → C. Node B is off the stack entirely and may already have been freed.

Thread 1 wakes and performs its CAS: is top still A? It is. The swap succeeds and sets top to B — a node that is no longer part of the stack and whose memory may belong to something else now. No operation was non-atomic, no thread misbehaved, and the structure is corrupt.

The essential point is that thread 1’s next was read from a world that no longer exists. Its CAS verified the head; nothing verified that the head’s successor was still what it had been.

What the enumeration shows

The default program is exactly that stack, with three nodes and a popped2 flag recording that node 2 has been taken off. The expectation is a property of the final state — the head is never a node that was already popped — so nothing has to be trusted to observe the bug; either the stack ends corrupt or it does not.

Eleven of 120 interleavings corrupt it. Step through one and watch the sequence: T1 reads top, T1 reads head.next, then T2 does its three operations, then T1’s CAS succeeds. The state panel shows top ending at 2 with popped2 at 1, which is the corruption stated as data.

Then switch to aba-tagged. The head is now a packed word — node id in the low digit, a counter in the rest — so pushing node 1 back produces 31 rather than 1. T1 expected 1; the CAS fails; the pop retries from a fresh read. Zero of 126 interleavings corrupt it.

That the tag lives in the same word is not a modelling convenience. An earlier version of this page CASed a separate version counter and then wrote the pointer, and it still corrupted the stack in 34 schedules — because splitting them reopened exactly the window the tag was added to close.

The numbers worth carrying

• Bare CAS on the stack head: 11 of 120 interleavings corrupt the structure.
• Tagged pointer: 0 of 126.
• A 64-bit tagged pointer typically spends 16–17 bits on the tag (using the unused high bits of a 48-bit virtual address) and wraps after ~65,000 operations on that slot. Wrapping reintroduces ABA, which is why high-throughput implementations use double-width CAS and a full 64-bit counter instead.
• ABA needs the value to return while a specific thread is between two specific instructions. It is rare per operation and certain over enough operations, which is the worst combination for testing.

Where it breaks down

Tagging fixes the detection, not the reclamation. Thread 1’s CAS now fails safely, and thread 1 still read head.next from a node that may have been freed in the meantime. On a garbage-collected runtime that read is safe because the node cannot be collected while a reference exists — which is exactly why lock-free structures are so much easier in Java or Go than in C++. Without a GC you need hazard pointers, epoch-based reclamation, or reference counting, and that machinery is larger than the algorithm it protects.

Counters wrap. A 16-bit tag makes ABA 65,536 times less likely, not impossible. Under millions of operations a second, “65,536 times less likely” is a Tuesday.

Not every ABA is a bug. For a monotonically increasing counter, or a value whose meaning does not depend on identity, returning to a previous value genuinely means being in a previous state. Knowing when you can ignore it is worth as much as knowing how to prevent it.

What people get wrong

“ABA only matters for pointers.” Mostly true and not always. It matters whenever the value is a proxy for a state rather than the state itself — an index into a slot table, a generation number, a version that recycles.

“A version counter fixes it.” Only if the version and the value are swapped together. A separate counter CASed before the write leaves a window between the two operations, and the bug survives — demonstrated above.

“Garbage collection makes lock-free code safe.” It removes use-after-free, which is the hardest part. ABA itself survives: a GC will happily hand you back the same object if it is still reachable, and it will certainly hand you back the same value.

“This is theoretical.” It is the reason AtomicStampedReference exists in the JDK, the reason Michael and Scott’s queue paper spends its length on it, and the reason the Treiber stack as usually written is unsafe without a GC.

In production

Java offers AtomicStampedReference (a reference plus an int stamp) and AtomicMarkableReference (a reference plus a bit), and both exist for precisely this. C++ has compare_exchange on a double-width type via cmpxchg16b where available. Rust’s crossbeam uses epoch-based reclamation, which sidesteps ABA by ensuring memory is not reused until no thread can be looking at it.

The three standard mitigations are worth being able to name: tagged pointers (make the word different even when the pointer is the same), hazard pointers (publish what you are about to dereference so nobody frees it), and epoch-based reclamation (defer freeing until every thread has passed a point). They solve overlapping but distinct problems, and real systems combine them.

The practical advice is unglamorous and correct: use ConcurrentLinkedQueue, crossbeam, folly::MPMCQueue or your platform’s equivalent. These are subtle enough that the people who wrote them found bugs in the published papers.

The follow-up questions

“What is the ABA problem?” — CAS compares values, not histories. Then give the stack sequence; the definition alone is not an answer.

“How do you fix it?” — Tagged pointer, and stress that the tag must be in the same word so both swap together.

“Your tag is 16 bits. Is that enough?” — It wraps. At high throughput, compute how long that takes and decide whether it is acceptable.

“You popped a node. When can you free it?” — The genuinely hard question, and the one that separates people who have written lock-free code from people who have read about it. Hazard pointers or epochs.