OrderingCAScompare-and-swapABAlock-freeretry loop

Compare-and-Swap: The Primitive Everything Is Built On

Change this value, but only if it is still what I last saw. That conditional write is what makes lock-free algorithms possible, and the trap in it — that "still the same value" is not the same as "nothing happened" — is called ABA.

▶ Run the labFollow the mechanism

Software view, hardware view

The gap between what you wrote and what the machine does is where this whole domain lives.

The question
How does compare-and-swap turn a racy read-modify-write into a safe one, and what is the failure it cannot detect?
What you wrote
I read a value, compute a new one from it, and write it back. If nobody else touched it, my update is correct.
What the hardware does
The hardware offers one indivisible operation that compares the current value against an expected one and writes only on a match, reporting whether it succeeded. Nothing detects a value that changed and changed back.
CAS is the foundation under every lock, every lock-free container and every atomic reference count. Its retry loop is where lock-free code spends its time under contention, and ABA is the defect that makes a correct-looking lock-free stack corrupt memory.
Source→Compiler→Instructions→Front End→Execution→Registers→Caches→Memory→I/O→Behavior

The operation and its loop

Compare-and-swap takes an address, an expected value and a new value. Atomically, it compares the contents against the expected value; on a match it writes the new value and reports success; otherwise it leaves memory alone and reports failure, usually returning what it actually found. As Atomic Instructions: What the Hardware Actually Guarantees describes, this is LOCK CMPXCHG on x86-64, CAS on AArch64 with LSE, and an LR/SC pair elsewhere.

The reason it matters is that it collapses check-then-act into one indivisible step. The broken pattern — read, compute, write — has a window in which another thread can update the location, and your write silently discards their change. CAS makes that window detectable: if someone updated it, your comparison fails and you know to start over with the value they left.

That "start over" is why almost all CAS use is a loop. Read the current value, compute the new one, attempt the swap, and on failure re-read and recompute. The loop terminates because a failure means someone else made progress — the algorithm as a whole advances, even though this thread had to retry, which is the formal property called lock-freedom. It is a weaker promise than it sounds: an individual thread can be starved indefinitely while the system keeps making progress.

The CAS retry loop, and the racy pattern it replaces
1// RACY: read-compute-write with a window
2int v = shared.load();
3v = expensive_transform(v);
4shared.store(v);             // silently discards any concurrent update
5 
6// CORRECT: CAS loop
7int cur = shared.load();
8int next;
9do {
10    next = expensive_transform(cur);
11    // on failure, 'cur' is updated with what was actually found
12} while (!shared.compare_exchange_weak(cur, next));
13 
14// Each failure means ANOTHER thread succeeded: the system
15// makes progress even when this thread does not. That is
16// lock-freedom -- and note it does not promise THIS thread
17// ever finishes.
18 
19// Note the cost shape: expensive_transform() runs again on
20// every retry. Heavy computation inside a CAS loop is
21// wasted work under contention.

ABA: the change CAS cannot see

CAS compares values, and a value is not a history. If another thread changes the location from A to B and back to A before your comparison runs, your CAS succeeds — the value is exactly what you expected — even though the world it referred to has been dismantled and rebuilt in between.

With a plain integer counter this is usually harmless. With a pointer it is a memory-corruption bug. The canonical case is a lock-free stack: you read the head pointer as node A and prepare to pop it by swinging head to A's successor. Before your CAS, another thread pops A, pops the node after it, frees them, allocates a new node that happens to land at A's old address, and pushes it. Your CAS sees head == A, succeeds, and sets head to a successor pointer read from a node that has been freed and reused. The stack now points into reclaimed memory.

The standard mitigations all work by making the comparison see more than the raw value. A version-tagged pointer packs a counter alongside the address so that A-with-tag-7 differs from A-with-tag-9, requiring a double-width CAS. Hazard pointers and epoch-based reclamation attack it from the other side, by preventing memory from being reused while any thread might still be looking at it. LL/SC is structurally immune, because the store-conditional fails if the reservation was cleared at all — it tracks *access*, not *value* — which is a genuine architectural advantage of that style.

ABA on a lock-free stack pop
T1 is descheduled hereaddress reusedT1 resumesstale A.next writtenT1 reads head = A, plans head := A.nextT2 pops A, then pops BT2 frees A and BT2 allocates a node reusing A's address, pushes itT1 CAS: head == A? Yes — succeedshead now points into freed memory
UserLLMAgentToolDataDecisionHumanGuardrail

When not to reach for CAS

CAS is the general primitive, which makes it tempting as the default. It is frequently the wrong default. Where the operation is a plain arithmetic update, fetch_add does it in one guaranteed-successful transaction, while a CAS loop under contention may retry many times — and each retry is a fresh coherence round trip for the line, so contention makes the loop worse in a way that fetch-and-add avoids entirely.

The comparison against a mutex is also less one-sided than lock-free advocacy suggests. As What a Mutex Actually Does describes, an uncontended mutex acquisition is itself a single atomic operation. What a mutex buys under contention is that waiters stop competing for the cache line and park; what a CAS loop does under contention is keep every thread hammering that line. Beyond a modest number of contending threads, the parking behaviour can win comfortably.

The honest decision procedure is short. Use fetch_add if the operation is expressible as one. Use a mutex if the critical section is more than a few instructions or contention is high. Reach for a CAS loop when the update is genuinely conditional, the critical section is tiny, and you have measured. And if the loop protects a pointer that can be freed, ABA is not a theoretical concern — resolve it before writing the code, not after the crash.

CAS loop for something that is not conditional
1int cur = counter.load();
2while (!counter.compare_exchange_weak(cur, cur + 1)) {
3    // retry; 'cur' refreshed with the observed value
4}
5 
6// Under contention every failed attempt is another
7// coherence round trip for the line. Throughput can
8// fall as cores are added.
Fetch-and-add: one transaction, cannot fail
1counter.fetch_add(1);
2 
3// One indivisible operation, no retry, no loop.
4// Still costs line ownership under contention --
5// but it costs it exactly once per increment.

A CAS loop pays for the ability to make the write conditional. When the write is not conditional, that is a pure loss: you get retries, wasted recomputation and extra coherence traffic in exchange for a capability the operation never used. Reach for CAS when the update genuinely depends on the observed value.

Key points

  • CAS writes only if the location still holds the expected value, which collapses check-then-act into one indivisible step.
  • Almost all CAS use is a retry loop; each failure means some other thread made progress, which is what lock-freedom guarantees — and it does not guarantee any individual thread finishes.
  • ABA: a value that changes to B and back to A defeats the comparison, because CAS compares values and not history.
  • Mitigations are version tags, hazard pointers, epoch reclamation, or LL/SC — which is immune because it tracks access rather than value.
  • Prefer fetch_add when the update is unconditional, and a mutex when the critical section is more than a few instructions.

Compare-and-Swap

Change an input and watch which number moves — and which one refuses to.

Compare-and-swap
memory
5
Try a CAS, then interfere and try again.

The whole compare-and-swap happens as one indivisible step, which is what makes it useful: nothing can slip between the compare and the write. Failure is normal, not exceptional — lock-free code is built from retry loops around it. And note what it does not give you: if the value changed to something else and back again, the compare still succeeds. That is the ABA problem.

Follow the mechanism

The path through the machine, hop by hop — and the conclusions it invites that are wrong.

  1. 1
    Thread → load: reads the current value to use as the expected operand.
  2. 2
    Thread → compute: derives the new value from what it observed, outside any atomic section.
  3. 3
    CAS → cache: the core takes the line exclusive and compares memory against the expected value indivisibly.
  4. 4
    CAS → outcome: on a match it writes and reports success; otherwise it reports failure and returns the value actually found.
  5. 5
    Failure → loop: the thread recomputes from the newly observed value and retries, paying another coherence transaction each time.
What people conclude from this — wrongly
  • • "CAS succeeded, so nothing changed" — it means the value matches, which is a weaker statement and is exactly the ABA hazard.
  • • "Lock-free means faster" — it means the system makes progress without blocking. Under heavy contention a lock that parks waiters frequently outperforms a loop that keeps hammering a cache line.
  • • "Lock-free means no thread can starve" — it means *some* thread progresses. Wait-freedom is the stronger property, and CAS loops do not provide it.
  • • "ABA is a theoretical problem" — it is a routine cause of corruption in lock-free stacks and queues over reusable memory.

Consequences, controls and cost

What it causes
  • • Lock-free structures degrade under contention rather than blocking, so the symptom is falling throughput and high cache traffic rather than threads parked in a wait state.
  • • Expensive computation inside a CAS loop is repeated on every retry, so contention multiplies the wasted work.
  • • ABA on a pointer produces memory corruption that appears long after the CAS and is extremely hard to attribute.
  • • A lock-free algorithm can starve an individual thread indefinitely while the system as a whole makes progress.
What you can do
  • • Use `fetch_add` or another dedicated atomic where the operation permits — it cannot fail and needs no loop.
  • • Keep computation outside the CAS loop where possible, so a retry re-attempts the write rather than redoing the work.
  • • Handle ABA explicitly whenever the CAS operand is a reusable pointer: version tags, hazard pointers or epoch-based reclamation.
  • • Shard or partition contended state so fewer threads compete for the same line, which removes retries rather than optimising them.
  • • Prefer a mutex unless measurement shows it is the bottleneck; an uncontended mutex is one atomic operation and parks its waiters when contended.
How to see it
  • • Instrument the retry count of the CAS loop; a mean well above one under load means contention is the dominant cost.
  • • Scale a benchmark across core counts — a CAS-based structure that flattens or regresses as cores are added is retry-bound.
  • • Compare a CAS loop against `fetch_add` for the same operation at several thread counts before choosing.
  • • Sample coherence counters for the contended line to confirm the cost is ownership transfer rather than the computation.
What it costs
  • • Lock-free avoids blocking and priority inversion at the cost of retries, wasted recomputation and heavier coherence traffic under contention.
  • • ABA mitigations cost memory and complexity: version tags need double-width CAS, hazard pointers and epochs need real reclamation infrastructure.
  • • CAS gives conditional updates; where the update is unconditional you pay for that capability and receive nothing for it.

Scope

§224 — what these claims are specific to.

What these claims are specific to
  • ISA-SPECIFICCAS is LOCK CMPXCHG on x86-64, CAS on AArch64 with LSE, and an LR/SC retry pair otherwise. LL/SC can fail spuriously and is structurally immune to ABA; single-instruction CAS is neither.
  • PLATFORM-SPECIFICDouble-width CAS for version-tagged pointers is available on common 64-bit platforms but is not universal, so tag-based ABA mitigation is not portable by default.
  • SIMPLIFIEDThe ABA walkthrough assumes an allocator that promptly reuses a freed address. Real allocator behaviour varies, which changes how often ABA is observed but never whether it is possible.

Misconceptions

Claim
“If my CAS succeeds, no other thread interfered.”
Reality
It means the value matched. Another thread may have changed it and changed it back, which is ABA, and with pointers over reusable memory that is a corruption bug rather than a curiosity.
Claim
“Lock-free algorithms are faster than lock-based ones.”
Reality
They are non-blocking, which is a progress property rather than a speed one. Under contention, retry loops generate more coherence traffic than a mutex that parks its waiters.
Claim
“A CAS loop is the general way to update shared state.”
Reality
It is the way to make a *conditional* update. For unconditional arithmetic, fetch_add is one guaranteed transaction against a loop that may retry many times.

Where the rest of this lives

Concurrency & Parallelism
Lock-freedom, wait-freedom and linearizability

This lesson covers the instruction and its hazards. The progress guarantees these algorithms provide, and how to prove a lock-free structure is linearizable, belong to concurrency.

← Atomic Instructions: What the Hardware Actually GuaranteesWhat a Mutex Actually Does →