Compare-and-Swap and Why the Retry Loop Must Re-read

A single instruction that reads a location, compares it against an expected value, and stores a new value only if they match is enough to build every other synchronisation primitive. That claim is Herlihy’s consensus theorem, and the instruction that satisfies it on every mainstream architecture is compare-and-swap. The interesting part is not the instruction. It is the loop around it, which looks like a formality and is where most incorrect uses of the primitive fail.

The instruction and its two outcomes

Compare-and-swap takes three operands: an address, an expected value, and a desired value. It loads the current contents, compares them to the expected value, and if they are equal writes the desired value. In all cases it returns the value that was there before the operation. The whole sequence is indivisible with respect to other threads, so no interleaving can observe the location between the load and the conditional store.

The return value is the crux of the design. Reporting success as a boolean would be enough for the caller to know whether its write happened, but it would force a second load to find out what the location now holds, and that load could itself be stale by the time the caller acts on it. Returning the observed value folds the failure case and the observation into one operation, which is what makes a loop possible without a second, separately racy read.

On x86-64 the instruction is lock cmpxchg. Without the lock prefix it is not atomic against other cores and only works for single-threaded code and for synchronisation with signal handlers on the same core. On Armv8-A the pair is ldaxr and stlxr: the load-exclusive arms a monitor on the address, and the store-exclusive fails if any other write to the monitored region occurred. POWER has lwarx and stwcx. in the same shape. The load-linked/store-conditional form is architecturally distinct from x86’s single instruction because the reservation is a property of the core rather than the bus, and it fails on any intervening write to the reservation granule, which may be larger than the word being operated on.

Why the expected value is a claim, not a variable

The expected value passed to the instruction is the value the caller believes is present, and it is only meaningful if it was observed immediately before. This is where the classic bug lives:

/* wrong: the link is derived once, before any attempt */
node_t *expected = atomic_load(&top);
node->next = expected;
while (!atomic_compare_exchange_weak(&top, &expected, node));

The compare-exchange updates expected on every failure, so the loop keeps retrying with a fresh observation and eventually succeeds. The node it installs still has the link computed from the first load. Every node pushed by another thread between the first load and the successful attempt is now unreachable: the stack’s head points at node, and node->next skips past everything that was pushed in the interval. The compare-exchange was correct and the structure is corrupt, because the value the instruction verified and the value the body acted on had diverged.

The failure is not in the loop’s termination, which is fine, but in the assumption that state derived from the expected value stays valid across attempts. Any derived state has to be recomputed inside the loop, after the current value is known.

The correct shape recomputes everything on each attempt:

static _Atomic(node_t *) top;

void push(node_t *n)
{
    node_t *head = atomic_load_explicit(&top, memory_order_relaxed);
    do {
        n->next = head;                          /* derived from the value just observed */
    } while (!atomic_compare_exchange_weak_explicit(
                 &top, &head, n,
                 memory_order_release, memory_order_relaxed));
}

The head parameter is passed by address because the operation must be able to write the observed value into it on failure. That is the mechanism that makes the retry possible: each failed attempt leaves the caller holding a fresher observation than it started with, and the loop body recomputes its derivative state from that observation. The loop terminates only when the caller’s claim about the current value was true at the moment the instruction executed.

The comparison is by value, not by identity. For a pointer, the instruction compares the bit pattern, so a freed node whose storage has been reused for a different object at the same address compares equal to the stale pointer. That equality is exactly what the caller asserted, and the instruction has no way to know the assertion was about a different object than the one the caller meant. Versioned words exist to make the bit pattern change when the object changes, which is the only defence available at this level. The failure mode this produces in a stack is worked through in The ABA Problem in Treiber Stacks.

Weak versus strong, and spurious failure

The C and C++ standards expose two forms. The strong form fails only when the comparison genuinely fails. The weak form is permitted to fail spuriously, returning false and an unchanged observed value even though the location still held the expected value.

Spurious failure is not a defect. On load-linked/store-conditional architectures the reservation can be lost for reasons unrelated to the word in question: a context switch, an interrupt, a cache eviction, or a write to a neighbouring word in the same reservation granule. Reconstructing the exact cause is not worth it, so the architecture permits the store-conditional to fail and the implementation reports that as a failed compare-exchange.

The rule that follows: use the weak form inside a loop that retries anyway, because the loop already handles failure and the strong form may be implemented as a loop internally on those architectures, so choosing strong pays twice. Use the strong form when a single attempt is all that is wanted, as in a test-and-set or a try-lock, where a spurious failure would be reported to the caller as contention that did not exist.

The failure ordering is a separate argument and is usually memory_order_relaxed. A failed compare-exchange performs no store, so the only thing it needs to do is make the observed value readable, and the load that produced it is already ordered by whatever precedes it in the loop. Passing memory_order_seq_cst as the failure ordering is legal and pointless.

Termination and the cost of contention

A compare-exchange loop is lock-free in the technical sense: if any thread is stalled, some other thread completes its operation in a bounded number of steps. It is not wait-free, because a particular thread can lose the race arbitrarily many times. The number of retries per successful operation grows with the number of threads attempting the same location, and the growth is not gentle. Every failed attempt is a cache line transfer, so contention converts a register-speed operation into a sequence of coherence transactions.

The practical consequence is that a compare-exchange loop over a location that many threads hammer is worse than a lock, because a lock at least queues the contenders while this loop makes them all fight. The mitigation is to reduce the number of threads touching the location, either by sharding the counter across per-thread slots and summing at read time, or by combining operations so that one thread performs work on behalf of several.

Termination also depends on progress by other threads being observable. A loop that recomputes its expected value correctly will succeed as soon as no other thread modifies the location between the load and the compare-exchange. If the location is being modified continuously, the loop may run for a long time, but it cannot run forever under the lock-free guarantee, because each iteration corresponds to another thread’s completed operation.

Double-width compare-exchange and the alignment requirement

Some targets provide a compare-exchange over two adjacent words. x86-64 has cmpxchg16b, which operates on a 16-byte aligned pair of 64-bit words and raises a general-protection fault if the alignment is violated. The fault is not optional, so a double-width atomic must be declared with the alignment the compiler associates with its 16-byte atomic type. Without that alignment the instruction raises an exception rather than failing gracefully, and a structure that embeds the atomic at an offset determined by surrounding fields can violate it silently until the instruction executes.

Where the double-width form exists it removes the need to pack a pointer and a version into one word, and it is the usual basis for a versioned pointer on 64-bit targets where the address space is too wide to leave room for a counter. Where it does not exist, the alternative is a single-word pointer with the version stored elsewhere, which reintroduces the ABA window the version was meant to close.

What the primitive cannot do

The atomicity is word-sized. Two independent locations cannot be updated together, so a structure that needs a consistent pair of pointers must either pack them into one word or use a different scheme. Packing works when the fields are small: a pointer plus a version counter in the high bits of a 64-bit word is the standard way to address the ABA problem, described in The ABA Problem in Treiber Stacks. Packing does not work when the fields are pointers on a target where a pointer already consumes most of the word, and it breaks entirely if the version field can wrap while a thread holds an old observation.

The instruction also has no notion of a transaction. A compare-exchange that succeeds commits exactly one word, and everything the caller did before it is only visible to other threads if the success carries release ordering. The default in the C and C++ interfaces is sequentially consistent, which supplies that ordering at a cost on weakly ordered cores; the explicit memory_order_release on success is the usual choice for a publication, with memory_order_relaxed acceptable on failure as above.

Finally, the primitive says nothing about memory safety. A compare-exchange can install a pointer into a node that another thread has already freed, and the instruction will succeed. The instruction guarantees the transition, not the lifetime, which is why the hard part of any non-blocking structure is reclamation rather than the exchange itself.