Lock-free progress, CAS and ABA

3.7 Without a lock: compare-and-swap loops, ABA and progress

A lock’s worst costs come from one thread waiting for another that cannot run: a holder that has been preempted, a holder taking a page fault, a sleeper that is still waking up. Lock-free structures are built so that no thread ever waits for another in that way. This section covers what that means precisely, how such structures are built, the bug peculiar to them, and what they still cost.

Progress guarantees

Concurrent structures are classed by what they promise about progress, from weakest to strongest.

• Blocking. A thread stopped at the wrong moment can stop the others indefinitely. Every lock is blocking: a holder preempted inside its critical section stops every thread that needs the lock until it runs again.
• Obstruction-free. A thread that runs alone, with the others paused, finishes its operation in a bounded number of its own steps. Threads running together may keep undoing each other’s work.
• Lock-free. If threads continue taking steps, the system continues completing operations even if some threads stop. Individual operations have no bounded completion guarantee, and one thread may starve.
• Wait-free. Every thread finishes every operation within a bounded number of its own steps.

These are guarantees about progress, not speed. A lock-free operation can be slower than a locked one. What it cannot do is wait for a thread that is not running.

The CAS loop

Most lock-free structures are built from one pattern. Read the current value, compute a new one from it, and compare-and-swap the new one in, retrying if another thread changed the value in between. A failed CAS returns the value that beat it, so the retry starts from fresh data. A stack of free slot indices shows the shape. It is called a Treiber stack, after the 1986 IBM report that described it. head holds the index of the top slot, next[i] holds the slot below slot i, and NIL marks the bottom.

Conceptually, push writes the new slot’s link and release-CASes it into head; pop acquires head, reads its link and CASes head to that successor. This is an explanation of the algorithm, not a complete Rust implementation: the links also need safe access and a reuse/reclamation protocol, including for a reader that is delayed before a failed CAS. The stack is lock-free: a CAS fails only because some other thread’s CAS succeeded. It is not wait-free, because one thread can fail over and over.

Under contention the loop degrades. Every attempt needs the line, and a failed attempt costs a transfer and achieves nothing. With more threads, attempts collide more often. On x86 a failed lock cmpxchg still takes the line exclusively, so failures generate as much traffic as successes do. A heavily contended CAS loop can therefore be slower than a lock that puts the losers to sleep, because sleepers at least stop moving the line.

ABA

CAS compares values, not histories. It answers whether head is still A, when the question the code means is whether head has been left alone since it was read. The two questions have different answers when the value goes away and comes back.

Start with A -> B -> C. Thread 1 reads A and B, then pauses. Thread 2 pops A and B, keeps B, and pushes A back with A -> C. Thread 1’s stale CAS succeeds because head is A again. Its pop returns A, which was free, so that much is correct. But the CAS installs B as the new head, a value read before the delay, and B now belongs to thread 2: B is owned and free at the same time. C is still reachable through B’s stale next, so the list looks intact, and nothing visibly goes wrong until B is touched again. The next pop hands B to a second owner, and when either owner pushes it back, its next is rewritten under the other. With pointers in place of indices, B may also have been freed, and the head of the list then points into freed memory. This is the ABA problem: a CAS that succeeds on a value which was removed and put back, as if nothing had happened in between.

There are three families of remedy, and each has a cost. A tag packs a counter into the same word as the value, a 32-bit generation beside a 32-bit index in one AtomicU64, and every successful CAS increments it. The word cannot then come back the same unless 2³² changes happen inside one delay; pointers need two words and a double-width CAS (cmpxchg16b on x86-64, casp on AArch64). Hazard pointers have each thread publish the address it is about to use, and no thread frees or reuses an address that another has published. Epoch-based reclamation, as in the crossbeam-epoch crate, holds freed items back until every thread has passed a point after which it can no longer be holding a reference to them. The costs are wider words, extra stores on every access, and frees that happen later than they could.

Why one producer and one consumer avoid it

A ring buffer with one producer and one consumer has two indices, and each index is written by one thread only. Nothing needs a CAS: only one thread ever writes its index, so it can load it, add one and store it, with no other thread able to get in between, and no RMW at all. There is no shared-head CAS to suffer this ABA pattern. Counters still need explicit wrapping arithmetic and a capacity/occupancy invariant so wraparound remains correct; a 64-bit counter at a billion increments a second takes about 584 years to wrap. There is nothing to reclaim, because the slots are reused in an order both sides know, and the producer never writes a slot until the consumer has said it is done with it. And every operation finishes in a fixed number of steps, a push either succeeding or reporting the ring full, which places the ring in the strongest of the four progress classes, wait-free.

What it costs

Lock-free code removes waiting for a thread that is not running. It does not remove line transfers. Every word that more than one core writes moves on every write by a different core: a lock-free stack’s head, a multi-producer queue’s tail, a reference count. The cost of a lock-free operation is roughly the number of shared lines it writes, or reads after another core wrote them, times 50–100 ns, plus whatever its retries add. A free list shared by three threads moves its head line on almost every operation. A ring with one producer and one consumer moves a slot line and an index line per item, each in one direction only.

Worked example: a free list of order slots

An order gateway preallocates 4,096 order records. Two gateway threads, on cores 4 and 5, pop slot indices from a shared FreeList to build new orders, and a fill thread on core 6 pushes a slot back when its order is finished.

Gateway 4 starts a pop and reads head = 17 and next[17] = 18. Then a stray thread takes core 4 for a 2 ms time slice. In those 2 ms gateway 5 pops 17 and 18 for two immediate-or-cancel orders. Order 17 is cancelled by the exchange, and the fill thread pushes 17 back, with next[17] = 19. Gateway 4 resumes, and its CAS from 17 to 18 succeeds. Gateway 4 is handed slot 17, which was free, so its own order is sound. But head is now 18, and slot 18 still holds gateway 5’s live order. Slot 19 is reachable through slot 18’s stale next, so the list looks healthy. The next pop hands slot 18 to a new order, two live orders now share one record, and fills for either land in the record the other is using.

With a tag, the history becomes part of the value. head becomes an AtomicU64 holding a generation above the index, and push and pop both increment the generation on every success. Compare (generation, index) as one atomic value; separate atomics would reintroduce the race.

Gateway 4’s CAS now compares generation and index together, finds the generation three steps on, after two pops and a push, and fails. The tagged CAS is the same single instruction as before. What it leaves is the shared line. At 200,000 orders a second on each gateway, and as many frees, consecutive operations almost always come from different cores, so each allocation and each free waits for the head line: 50–100 ns each, and more when a burst makes CASes fail and retry.

Seeing it

A per-thread counter bumped with Relaxed on every failed CAS, divided by the successes, shows contention directly: well under 1% when operations rarely overlap, tens of per cent in a burst. perf c2c on the running process puts the head line at the top of its list, with HITMs, loads that found the line modified in another core’s cache, from every core that uses the free list. loom finds the ABA in a model with three threads and three slots and prints the interleaving above; with the tag, the same model passes. Each HITM is one transfer, 50–100 ns, and on a shared head they arrive at the rate of operations, failed ones included.