In a lock-free algorithm built on compare-and-swap, a thread reads a shared pointer whose value is A, does some work, and its later compare-and-swap from A succeeds — yet the structure ends up corrupted. Explain what went wrong and why a successful compare-and-swap was not enough.
answer
- CAS compares values, not histories
- A -> B -> A slips past the guard
- stale `next` read before the CAS
- needs value recurrence = memory reuse
- fix: version tag, or never reuse while referenced
basics
~20 sThat is the ABA problem. Between the read and the compare-and-swap, other threads changed the value to B and back to A. Compare-and-swap only checks that the word is equal now, not that nothing happened meanwhile, so anything the thread inferred from its first read may be stale.
solid answer
~50 sCompare-and-swap answers one question: is this word still bit-equal to what I read? It cannot answer: has anything happened since I read it? If other threads move the location A to B and back to A, the comparison passes even though the world moved underneath. That is ABA. The damage comes from state the thread derived from its first read. In a Treiber-style lock-free stack, pop reads top = A, reads A.next = B, then compare-and-swaps top from A to B. If meanwhile another thread pops A, pops B, and pushes a recycled A back, top is A again but the real second node is now C. The compare-and-swap succeeds and installs B — a node already freed or owned by someone else — as the new top. That is corruption, not staleness. Two fix directions: give the compared word identity over time (a version/stamp counter), or prevent the old node from reappearing while any thread still holds a reference to it (safe memory reclamation).
code
text · 12 linesstart: top -> A -> B -> C
T1: head = top # A
T1: next = head.next # B
---- T1 preempted ----
T2: pop() -> A
T2: pop() -> B # B recycled to allocator
T2: push(A) # same address A reused
top -> A -> C
---- T1 resumes ----
T1: CAS(top, A, B) # SUCCEEDS: top is bit-equal to A
top -> B # B is freed memory; C leakedgo deeper
Be able to state the definition: the value went A to B back to A, so CAS succeeds even though the state changed. One concrete example is enough.
Walk the stack-pop trace and point at the exact stale value (the next read taken before the CAS), then name version tags as the standard fix.
Frame it as a mismatch between what CAS verifies and what the algorithm assumes, and connect it to memory reuse and therefore to reclamation policy.
Discuss when to design ABA out entirely (monotonic sequence numbers, indices that never recycle, single-producer designs) versus paying for tagging or reclamation, and how you would test for it deterministically.
## What compare-and-swap promises Compare-and-swap (CAS) is an atomic read-modify-write: if this memory word equals `expected`, store `newValue` and report success; otherwise change nothing and report failure. Lock-free algorithms use it as an optimistic guard — read shared state, compute a new state, then CAS to install it, retrying if someone else won the race. The guard is weaker than it looks. CAS compares **values at one instant**, not **histories**. A word that changed from A to B and back to A is bit-identical to one that never changed. CAS cannot tell them apart, so the algorithm's implicit assumption — "nothing I care about changed" — is not the property CAS verifies. ## The canonical failure A Treiber stack keeps a single `top` pointer; nodes chain via `next`. ``` pop(): loop: head = top # observes A if head == null: return null next = head.next # observes B if CAS(top, head, next): return head ``` The fragile part is `next`: it is read from node A's memory **before** the CAS, and is only valid if A is still the head of the same list at CAS time. ``` stack: A -> B -> C T1: reads head=A, next=B ...then is descheduled T2: pop -> A ; pop -> B ; free/reuse B ; push A again stack: A -> C (B is gone) T1: CAS(top, A, B) SUCCEEDS -> top = B stack: B -> ??? (B was freed / handed to another owner) ``` The stack now points at reclaimed memory, and C has been lost. Symptoms show up far from the cause: lost elements, cycles, use-after-free crashes, or a queue that returns an object twice. ## Why it happens ABA needs three ingredients: (1) an optimistic read whose derived data outlives the read, (2) values that can **recur** — typically because memory or slot indices are recycled, (3) a window between read and CAS in which other threads can complete a full cycle. Preemption, page faults, and hypervisor scheduling make that window arbitrarily large; "the window is tiny" is not a defence, only a way to make the bug rare and unreproducible. ## Where ABA does NOT apply If the compared value never repeats, ABA is impossible. A monotonically increasing counter, a sequence number, or a one-shot state machine that only moves forward (`PENDING -> DONE`, never back) is ABA-free by construction. ABA is also irrelevant when the CAS's success does not license any assumption beyond the word itself — e.g. a CAS on a boolean flag where you re-read all dependent state afterwards under a proper protocol. ## The two families of fix **Tag the value.** Pack a monotonically incrementing version counter alongside the pointer and CAS both together (a double-width CAS, or a stamped-reference abstraction, or spare pointer bits). A to B to A then reads as (A,7) versus (A,9): the CAS fails and the thread retries. This turns "value equality" into "value plus generation equality". **Keep A from coming back.** If node A cannot be freed or reused while any thread might still be mid-operation on it, the recurrence that ABA depends on cannot happen. That is what hazard pointers, epoch-based reclamation, and read-copy-update provide, and it is also part of why garbage-collected runtimes see fewer ABA bugs. Some hardware sidesteps the problem instead: load-linked/store-conditional fails if the cache line was written at all between the load and the store, so it detects *any* intervening write rather than comparing values. ## How to talk about it Say what CAS verifies (value equality now), name the assumption the algorithm actually needs (no intervening reuse), show the stack or free-list trace, then name both fix families. Interviewers are checking that you understand ABA as a *specification gap*, not as a rare timing fluke.
- Does the ABA problem exist if the shared word is a counter that only ever increases?No. ABA requires the compared value to recur, and a strictly monotonic counter never returns to a previous value, so a successful CAS really does prove no intervening modification. This is why version tags work: they graft monotonicity onto a value that would otherwise repeat. The counter must be wide enough that wraparound is not reachable in practice.
- Why doesn't ABA show up in tests?It requires a specific interleaving in which one thread stalls between its read and its CAS while others complete a full remove-and-reuse cycle. On a lightly loaded test machine that window is nanoseconds wide and the allocator rarely hands the same address back that fast. Production load, more cores, preemption, and memory pressure all widen the window, so the bug appears late and looks like random corruption.
You memorise a parking spot by the red car in it. You come back, see a red car, and drive off in it — but your car left and an identical one parked. The observation matched; the identity did not.
saying these in an interview costs you the question
- Calling ABA 'just a stale read' — it is a false-success that installs invalid state
- Claiming CAS proves nothing changed since the read
- Believing a short read-to-CAS window makes the algorithm correct
- Assuming ABA affects every CAS, including monotonic counters
- Confusing ABA with a lost update or a torn read