Concurrency Roadmap/Memory Models & Atomics

Compare-and-Swap & the ABA Problem

Compare-and-swap is the hardware primitive underneath nearly all lock-free code, and the ABA problem — where a value goes A→B→A and fools a naive CAS into wrongly proceeding — is the sharpest illustration of why lock-free correctness is harder than it looks.

~5/5Theory: 50m
Language-specific mechanics: Concurrency Language Manual — Atomics, volatile & the Memory Model →

The primitive: compare-and-swap

Compare-and-swap (CAS) is the hardware instruction underneath almost every lock-free data structure you'll ever encounter, and its contract is small enough to state in one sentence: atomically, check whether a memory location still holds an expected value, and if so, replace it with a new value — as a single indivisible step that cannot be interleaved with any other thread's access to that location.

function CAS(location, expected, new_value) -> bool: atomically: if *location == expected: *location = new_value return true else: return false // someone else changed it first — caller must retry

That's the entire primitive. Real hardware exposes it as a single instruction (LOCK CMPXCHG on x86/x64, a load-linked/store-conditional pair — LDXR/STXR — on ARM), and every mainstream language exposes a thin wrapper around it: compareAndSet/compareAndExchange on Java's atomic classes, compare_exchange_weak/compare_exchange_strong on C++'s std::atomic, Atomics.compareExchange in JavaScript's SharedArrayBuffer API. The reason CAS specifically (rather than, say, a generic "atomic function apply") became the universal hardware building block is that it's minimal and composable: you can build every other atomic read-modify-write operation (increment, append, min/max, arbitrary functional update) out of a CAS retry loop, but you cannot build CAS itself out of anything weaker without a lock.

The CAS retry loop

Because a CAS call can fail (another thread won the race), essentially all lock-free code built on CAS follows the same shape:

loop: old = atomic_load(location) new = compute_new_value(old) // pure function of old — must not have side effects yet if CAS(location, old, new): break // success — new value is now published // else: retry, someone else moved the location; recompute from the fresh value

This "optimistic concurrency" pattern — read, compute speculatively, attempt to publish, retry on conflict — is the lock-free equivalent of "try to commit a transaction, retry if it aborts." It scales well under low-to-moderate contention (no thread ever blocks another; a failed CAS just means one wasted computation, not a suspended thread) and degrades under very high contention (many threads burn cycles retrying against each other) — this is a real, measurable trade-off, not just a theoretical one, and it's exactly why AtomicInteger-style increments outperform synchronized blocks at low contention but specialized striped counters (like Java's LongAdder) exist for high-contention counting instead of a single CAS-looped AtomicLong.

The ABA problem, precisely

Here is the subtlety that makes CAS-based code genuinely hard to get right, and the reason this is legitimately one of the hardest ideas on this whole roadmap. CAS's correctness check is "is the value still expected?" — but "still the same value" is not the same claim as "nothing has changed." A location can go A → B → A between your read and your CAS, and your CAS will see "yep, still A" and proceed — even though the state genuinely changed and changed back in a way that invalidates the assumption your speculative computation was built on.

The canonical illustration is a lock-free stack implemented as a singly linked list with an atomic head pointer, using CAS to push and pop:

  1. Thread 1 wants to pop. It reads head = A, and reads A.next = B. It's about to CAS head from A to B (the standard pop: swing head to the second node).
  2. Before Thread 1's CAS executes, Thread 1 is preempted.
  3. Thread 2 runs to completion: it pops A (stack is now B → C), then pops B (stack is now just C), then — critically — it (or an allocator reusing freed memory) pushes a new node back onto the stack that happens to be allocated at the same memory address A used to occupy (a very common outcome with allocators that reuse recently-freed blocks), with a completely different logical next pointer (say, pointing at C).
  4. Thread 1 resumes. It checks: is head still A? Yes — by pointer identity, the bit pattern matches. The CAS succeeds, and head is set to B.
  5. But B was already popped and possibly freed in step 3. The stack now points into freed/reused memory. Depending on the language and allocator, this ranges from silent data corruption to a crash — and it happened despite every individual CAS "succeeding" by its own local, correct-looking check.

The bug is not that CAS lied — it's that "the value equals A" was never actually the invariant Thread 1 needed. It needed "nothing popped and re-pushed since I last looked," and pointer equality cannot distinguish "the original A" from "a different A-shaped thing that happens to occupy the same address."

Solutions

  • Versioned / tagged pointers (the classic fix). Pair the pointer with a monotonically incrementing counter, and CAS the pair together (often packed into a double-width word — the historical reason x86 offers CMPXCHG16B for 128-bit compare-and-swap). Even if the pointer bit-pattern returns to A, the version counter has moved on, so the combined (pointer, version) value is different and the stale CAS correctly fails. This trades a small amount of memory and a wider atomic operation for a genuine fix.
  • Hazard pointers. Instead of preventing address reuse, prevent premature reclamation: before dereferencing a node, a thread publishes "I am currently using this address" in a globally visible per-thread slot; a reclaimer scans all such slots before actually freeing memory, so a node can't be freed (and thus can't be reused at the same address) while any thread might still be relying on its identity. This solves ABA by removing its precondition (address reuse while a thread still has a stale reference) rather than by making the CAS itself version-aware.
  • Garbage-collected languages sidestep the classic case, but not the general one. In Java, Python, JavaScript, or any GC'd runtime, a node cannot be reclaimed and its address reused for an unrelated object while a live reference to it still exists somewhere reachable — which eliminates the specific "freed-and-reallocated-at-the-same-address" flavor of ABA described above. It does not eliminate the logical ABA problem: if the same live object legitimately transitions from state A to B and back to A (e.g., a reference field goes from pointing at node X, to node Y, and back to the very same still-alive node X), a CAS checking "is it still X?" can succeed while missing that something meaningful happened in between. GC buys you safety from use-after-free; it does not buy you protection from "the value returned to what it was, but the world moved."

Pitfalls and interview framing

  • "CAS succeeded, so nothing changed in between" is the trap. The entire ABA problem is a counterexample to that intuition — always ask "could this value have been legitimately reused or logically round-tripped between my read and my CAS?"
  • Conflating "lock-free" with "correct by default." Lock-free code is harder to get right than a well-placed mutex, not easier — the payoff is scalability under contention and immunity to some blocking-related failure modes (a thread holding a lock and dying, priority inversion), not an easier correctness argument.
  • Ignoring memory reclamation as part of the design. In non-GC'd languages, "when is it safe to actually free this node" is as much a part of correctly implementing a lock-free structure as the CAS logic itself — treating them as separate concerns is how ABA bugs slip through code review.
  • Assuming compareAndSet/compare_exchange_weak failing is exceptional. A failed CAS in a retry loop is the expected, common case under contention, not an error path — code (and tests) that assume the first CAS attempt always succeeds will look correct in a single-threaded smoke test and fail under real concurrent load.
Reference implementations in:

The CAS Retry Loop: What incrementAndGet() Actually Does Underneath

Every atomic read-modify-write operation is built from the same shape: read, compute, attempt an atomic compare-and-swap, retry on failure. This hand-rolls that shape using only the raw compare-and-set primitive.

var value atomic.Int64 // Reimplements Add(1) by hand with CompareAndSwap — // exactly the retry-loop shape every atomic RMW is built from. func incrementManually() int64 { for { current := value.Load() next := current + 1 if value.CompareAndSwap(current, next) { return next // nobody else changed it since our read } // else: another goroutine's CAS won — retry with a fresh load } }

atomic.Int64.CompareAndSwap returns a bool, matching Java's compareAndSet. The failure path is the common case under contention, not an error — Add(1) is this loop, and the interview follow-up is why a mutex can still beat CAS when retries thrash the same cache line.

Reproducing the ABA Problem: A Naive Lock-Free Stack's Pop

A worked, heavily-commented illustration of the scenario from this subtopic's theory: A → B → C, a thread pops and reads ahead, gets preempted, and another thread's pop-pop-push sequence turns its "nothing changed" check into a wrong answer.

type node[T any] struct { value T next *node[T] } type LockFreeStack[T any] struct { head atomic.Pointer[node[T]] } func (s *LockFreeStack[T]) Push(v T) { n := &node[T]{value: v} for { old := s.head.Load() n.next = old if s.head.CompareAndSwap(old, n) { return } } } // BUG: this pop is vulnerable to ABA. func (s *LockFreeStack[T]) Pop() (T, bool) { old := s.head.Load() // (1) reads node "A" if old == nil { var zero T return zero, false } newHead := old.next // (2) preemptable here // ---- another goroutine can pop A, pop B, and re-push the same A ---- if s.head.CompareAndSwap(old, newHead) { // (3) "still A? proceed." return old.value, true // may now be structurally wrong } var zero T return zero, false // real code would retry }

atomic.Pointer[T] (Go 1.19+) is the direct analogue of Java's AtomicReference. Go is garbage-collected, so classic address-reuse ABA is unlikely, but logical ABA still happens if the same node is popped and pushed back — CAS is keyed on pointer identity, not on the stack's topology. A tagged pointer (pointer + version packed together) is the usual fix; don't assume GC makes lock-free stacks safe.

Further Resources (Optional)

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.