Walk through how the ABA problem corrupts a lock-free Treiber stack, and how stamping prevents it.

## The structure: a Treiber stack A **Treiber stack** is the classic lock-free stack. It keeps a single mutable field, `head`, pointing at the top node; each node has a `next` pointing at the node below. Both operations are **read-compute-CAS retry loops**: ```text push(x): loop { oldHead = head; node.next = oldHead; if CAS(head, oldHead, node) break } pop(): loop { oldHead = head; if oldHead == null return null; newHead = oldHead.next; if CAS(head, oldHead, newHead) return oldHead } ``` No locks; correctness rests entirely on CAS reliably failing when `head` changed. ## The ABA interleaving, step by step Start with the stack `head -> A -> B -> C` (A on top). 1. **Thread 1** begins `pop()`: reads `oldHead = A`, computes `newHead = A.next = B`. It is about to `CAS(head, A, B)` — then it is **preempted** (descheduled). 2. **Thread 2** runs to completion: - `pop()` removes **A**. Stack is now `head -> B -> C`. - `pop()` removes **B**. Stack is now `head -> C`. - `push(A)` puts **A** back on top (A's `next` is now set to C). Stack is now `head -> A -> C`. 3. **Thread 1** resumes and executes `CAS(head, A, B)`. The current `head` **is** A (it came back!), so the **CAS succeeds**. It sets `head = B`. ## Why that is catastrophic After step 3 the stack is `head -> B -> ???`. But **B was already popped** in step 2 — it is no longer a live stack node, and `B.next` is whatever it was when B left (it pointed at C, but C's own state may have moved on, or B may have been handed to a caller and mutated). The stack now contains a **resurrected, removed node**, and node **C is lost** (leaked / unreachable from head). Subsequent operations traverse corrupted links: you can lose elements, return already-popped nodes, or build a cycle. All of this happened even though every individual CAS 'succeeded' — the algorithm's safety invariant (a successful CAS means 'head didn't change since I read it') was **violated** because head changed *and changed back*. ## Note on memory reuse vs Java GC The nastiest classic form needs **node reuse**: a freed node A is recycled (an object pool, or `malloc/free` in C giving back the same address). Java's **garbage collector** mitigates *that* specific form — while Thread 1 holds a reference to A, A cannot be collected and reissued as a *different* object, so 'A is now a different node at the same address' can't happen in pure GC'd Java. **But the bug above needs no reuse** — A is the *same* object legitimately re-pushed. So GC reduces one variant; **logical ABA remains** and the corruption is real. ## The fix: stamp the head Replace `AtomicReference<Node> head` with `AtomicStampedReference<Node> head`. Now every successful push/pop increments a version **stamp** alongside the reference: ```java AtomicStampedReference<Node> head = new AtomicStampedReference<>(null, 0); Node pop() { int[] holder = new int[1]; while (true) { Node old = head.get(holder); int stamp = holder[0]; if (old == null) return null; Node nxt = old.next; if (head.compareAndSet(old, nxt, stamp, stamp + 1)) return old; } } ``` Replay the interleaving: Thread 1 reads `(A, stamp=10)`. Thread 2's two pops and one push bump the stamp to **13**. Thread 1 resumes and does `compareAndSet(A, B, 10, 11)`. The reference matches (head==A) but the **stamp is now 13, not 10**, so the **CAS fails**. Thread 1 loops, re-reads `(A, 13)`, recomputes `A.next` (now C), and retries correctly. The intervening change is detected precisely because the stamp **monotonically advanced** even though the reference returned to its old value. ## Cost and alternatives at scale Stamping boxes the (reference, stamp) pair into an immutable holder swapped atomically, so each successful update allocates a small object — measurable under very high contention. Production-grade lock-free reclamation often prefers schemes that avoid both ABA and that allocation: **hazard pointers** and **epoch-based reclamation** make it safe to know when a node can be reused (so the address-reuse form of ABA can't arise), and **double-width / 128-bit CAS** (where the hardware supports it) packs a counter beside the pointer for free. The principal-level takeaway: ABA is fundamentally 'CAS tests value equality, but the invariant you need is identity-over-time,' and you close the gap either by versioning (stamps), by controlling reuse (hazard pointers/epochs), or by proving the value's return is semantically harmless.