skip to content

What is the ABA problem in a CAS-based algorithm, and why can compare-and-swap miss it?

level: middleimportance: must knowfreq 62%

answer

  1. CAS compares value, not history
  2. A → B → A slips past compareAndSet
  3. Harmless for counters, harmful for reused references/nodes
  4. AtomicStampedReference = version stamp; AtomicMarkableReference = one bit
  5. Stamp must advance on every update

basics

~20 s

ABA is when a value goes A then B then back to A between a thread's read and its compare-and-swap. The CAS only checks the current value equals A, sees A, and succeeds, never noticing the change in between.

solid answer

~50 s

Compare-and-swap (CAS) updates a variable only if it still holds the value the thread last read. The ABA problem is that CAS compares values, not history: if another thread changes the value from A to B and back to A in the gap between your read and your CAS, the CAS still sees A and succeeds, as though nothing happened. For a plain counter that is harmless because A means the same thing. It becomes dangerous when the value is a reference or a node whose surrounding structure changed, for example a lock-free stack where the popped 'A' node was reused or its successor was altered. The fix is to make each successful change observable by pairing the value with a version stamp that every update advances (AtomicStampedReference), so CAS compares (value, stamp) and detects the intervening change; AtomicMarkableReference's boolean mark can flip back, so it is no general fix.

code

java · 15 lines
java
// Defeating ABA with AtomicStampedReference
AtomicStampedReference<String> ref =
    new AtomicStampedReference<>("A", 0);

int[] stampHolder = new int[1];
String current = ref.get(stampHolder); // reads value + stamp atomically
int stamp = stampHolder[0];            // value="A", stamp=0

// Another thread does A->B->A, moving the stamp each time (shown inline):
ref.compareAndSet("A", "B", 0, 1);
ref.compareAndSet("B", "A", 1, 2);     // value back to "A", stamp now 2

// Our CAS expects ("A", 0): value matches but stamp doesn't -> fails.
boolean ok = ref.compareAndSet(current, "C", stamp, stamp + 1);
System.out.println(ok); // false -> ABA detected, we must re-read and retry

go deeper

for a junior

Can state the literal A→B→A scenario and that compareAndSet only checks the current value, so it succeeds even though the value changed and changed back.

for a middle

Explains why ABA is harmless for counters but harmful for reused references, and names AtomicStampedReference as the fix that compares a version stamp alongside the value, with AtomicMarkableReference's one-bit mark as no general fix.

for a senior

Walks through a concrete lock-free stack corruption, explains GC's partial mitigation vs logical ABA, and reasons about the stamp needing to advance on every update and the cost of the boxed (ref, stamp) pair.

for a principal

Frames ABA as 'CAS compares value not identity-over-time,' discusses versioned/tagged pointers, double-width CAS in non-GC languages, hazard pointers/epoch reclamation as alternatives to stamping, and when to design the algorithm so ABA is provably benign instead of paying for stamps.

## Background: CAS **Compare-and-swap (CAS)** is a hardware-supported atomic instruction. It takes three things: a memory location, an *expected* value, and a *new* value. Atomically (as one indivisible step) it checks whether the location currently holds the expected value; if so it writes the new value and reports success; otherwise it leaves the location alone and reports failure. In Java this is exposed as `AtomicInteger.compareAndSet(expected, new)`, `AtomicReference.compareAndSet(...)`, and similar. Lock-free algorithms use CAS in a **read-modify-CAS retry loop**: read the current value, compute a new value from it, then CAS. If the CAS fails (someone else changed it), loop and try again. This avoids locks while staying correct — *as long as a failed CAS reliably tells you 'something changed.'* ## The flaw: CAS compares values, not history CAS only asks 'is the current value still equal to what I expected?' It has no memory of what happened *in between* your read and your CAS. Consider: 1. Thread 1 reads the value: it is **A**. 2. Thread 1 is paused (scheduler, GC, page fault — anything). 3. Thread 2 changes the value **A → B**, then later **B → A**. 4. Thread 1 resumes and does `compareAndSet(A, newValue)`. The current value *is* A, so the **CAS succeeds** — even though the value was modified twice while Thread 1 slept. This is the **ABA problem**: the value returned to A, so CAS cannot distinguish 'never changed' from 'changed and changed back.' ## When ABA is harmless vs harmful For a **plain numeric counter**, ABA is usually fine: the value *is* the state, and an A is an A. The classic incrementing counter has no ABA bug. ABA bites when the value is a **reference** (or pointer) and the *meaning* behind that reference changed even though the reference equals its old value. The textbook case is a **lock-free stack (Treiber stack)** built on a `head` reference: - Thread 1 reads `head = A`, plans to pop A by CAS-ing `head` from A to A.next. - Thread 2 pops A, pops A.next (B), then pushes A back. Now `head = A` again, but A.next may now point somewhere different, or, without garbage collection, A's memory may have been recycled into a different node. - Thread 1's `compareAndSet(A, oldAnext)` succeeds and sets head to a stale/dangling successor, corrupting the stack. The danger is amplified by **memory reuse** (object pools, or manual memory management in C/C++ where the same address is freed and reallocated). Java's garbage collector rules out one form: as long as Thread 1 holds a reference to A, A cannot be collected and reused as a *different* object — so ABA from recycled memory cannot happen in pure-Java GC'd code. But ABA can still occur logically whenever a reference cycles back to a prior value with different surrounding state. ## The fix: stamps and marks The cure is to make every change observable by attaching extra information that **advances with every change** (or toggles), so 'changed back' is still detectable: - **`AtomicStampedReference<V>`** pairs a reference with an `int` **stamp** (a version number). Your code passes a new stamp with every update, normally the old one plus 1; the class stores whatever stamp you pass. CAS now compares *both* (reference, stamp): `compareAndSet(expectedRef, newRef, expectedStamp, newStamp)`. Even if the reference returns to A, the stamp has advanced past the value Thread 1 read, so its CAS fails and it retries. You read both atomically via `get(int[] stampHolder)`. - **`AtomicMarkableReference<V>`** pairs a reference with a single `boolean` **mark**. It does not give a full version history — it answers 'has this been marked?' (e.g. logically deleted). It is enough for algorithms that only need one bit of extra state (like marking a node for deletion in a lock-free linked list), but a one-bit mark can itself toggle back, so it does not fully solve ABA the way an advancing stamp does. The general principle behind both is the **versioned/tagged pointer** (or 'ABA tag'): store a counter alongside the value and increment it on every write, so identical values at different times carry different tags. ## Cost and alternatives A stamp doubles the logically-atomic word. Under the hood Java boxes the (reference, stamp) pair into a small immutable holder object that is itself swapped atomically, which adds a tiny allocation per update. Alternatives include using immutable values so a returned 'A' truly is the same state, designing algorithms where ABA is provably harmless, or (on the JVM) leaning on GC to prevent address reuse. Languages without GC often use a double-width CAS, one atomic compare-and-swap over a pointer and a counter stored side by side.

  • Does Java's garbage collector eliminate the ABA problem?
    No, it rules out one variant. Because you hold a reference to node A it can't be collected and reused as a different object, so the memory-reuse ABA familiar from C/C++ cannot happen. But logical ABA still happens: a reference can cycle back to a prior value (e.g. node re-pushed onto a stack) with different surrounding state, so you still need a stamp.
  • Why is ABA usually not a problem for an AtomicInteger counter?
    Because for a counter the value IS the entire state and carries no hidden meaning — an A now is semantically identical to an A earlier, so succeeding on A is correct. ABA only matters when equal values at different times imply different surrounding state, typically with references into a mutable structure.

A hotel room key check: the desk only verifies the key opens room 204. If a guest checks out and a new guest checks into 204 with an identical key, the front desk can't tell them apart. A version sticker that increments on every check-in (the stamp) reveals the change even though the room number is unchanged.

  • Claiming CAS compares the whole history or 'sequence of changes' — it only compares the current value to the expected value.
  • Saying Java's GC makes ABA impossible — it rules out memory-reuse ABA but not logical ABA.
  • Thinking ABA affects every CAS use, including simple counters — it generally doesn't for value-only state.
  • Confusing AtomicMarkableReference (one boolean) with AtomicStampedReference (a full version counter); a stamp that every update advances detects ABA, a mark does not.

AtomicStampedReference
Java 1.5

context