11Lock-Free Programming

In July 1997 a spacecraft on the surface of Mars began resetting itself, losing data each time. A low-priority task that gathered weather data held a lock that a high-priority task managing the information bus needed; a medium-priority task ran in between, the high-priority task missed its deadline, and a watchdog reset the machine. The fix, uploaded from Earth, switched on priority inheritance for that lock (Jones, 1997). A trading thread that shares a lock with a logger, a risk reporter or a configuration reloader has the same problem, only the deadline is a few microseconds, and the lower thread need not be preempted by anything more sinister than the operating system’s scheduler. This chapter is about sharing data between threads without locks: what the hardware guarantees about memory, what C++ and Rust let a program say about ordering, the compare-and-swap loop and its classic trap, the reclamation of memory that other threads may still be reading, and what “lock-free” actually promises.

11.1 Atomics and the memory model

Definition 11.1 (Atomic operation)

An atomic operation on a memory location is indivisible with respect to other threads: no thread observes it half done. C++ provides std::atomic<T> and Rust AtomicU64 and its siblings, with loads, stores, exchanges, fetch-and-add and compare-and-swap; on x86 each maps to one instruction for sizes up to eight bytes.

A data race (chapter 9) is undefined behaviour in C++; atomics are how a program shares a location without one. The question they leave open is order. A processor executes out of order (chapter 2), keeps stores in a buffer before they reach the cache, and a compiler reorders memory accesses that it can prove independent in one thread; another thread can therefore see a thread’s writes in a different order from the program’s.

Definition 11.2 (Memory ordering, acquire–release ordering, sequential consistency)

The memory ordering of an atomic operation states what other memory accesses it orders. In acquire–release ordering, a load with acquire that reads the value written by a store with release sees every write the storing thread made before that store: the pair publishes data. Sequential consistency, the default of C++ atomics, adds a single total order of all such operations that every thread agrees on, as if they were interleaved on one processor. A relaxed operation is atomic but orders nothing else.

The publication pattern (write the data, then store a flag with release; load the flag with acquire, then read the data) is the backbone of every ring buffer in chapter 12. Sequential consistency is needed less often and costs more; the classic case where acquire–release is not enough is the store-buffer pattern of Figure 11.1: each thread writes its own flag and reads the other’s. On x86 a store may still sit in the processor’s store buffer when the following load of another location completes, so both threads can read zero. Only a sequentially consistent store (compiled to an instruction that drains the buffer) forbids it.

11.2 Compare-and-swap loops and the ABA problem

Definition 11.3 (Compare-and-swap)

Compare-and-swap (CAS) atomically replaces the value of a location with a new value if and only if it still equals an expected value, and reports whether it did. A CAS loop reads the current value, computes a new one, and retries the CAS until no other thread has changed the location in between.

Every lock-free structure is built from CAS loops. A stack pops by reading the head node and its successor and swinging the head from the node to its successor with a CAS; the CAS fails, and the loop retries, if another thread moved the head in the meantime. The failure it cannot see is the change that was undone.

Definition 11.4 (ABA problem)

The ABA problem is the failure of a compare-and-swap to detect that a location changed from $A$ to $B$ and back to $A$ between the read and the CAS: the comparison succeeds although the state it was computed from (here, $A$’s successor) is stale.

The standard cures change what is compared. A tag (a version counter) stored next to the pointer and incremented on every update makes the three states $A$, $B$, $A$ compare as $(A,1)$, $(B,2)$, $(A,3)$. On x86-64 a pointer and a counter fit a 16-byte compare-and-swap; the tutorial’s stack avoids the wide instruction by storing nodes in a fixed array and packing a 32-bit index with a 32-bit tag into one 64-bit word. Its nodes are never freed, which removes the other half of the problem.

11.3 Safe memory reclamation

Definition 11.5 (Hazard pointer, epoch-based reclamation)

In a lock-free structure whose nodes are freed, a node removed by one thread may still be read by another that loaded its address before the removal. A hazard pointer is a per-thread published pointer to a node the thread is about to read; a node is freed only when no hazard pointer points to it (Michael, 2004). In epoch-based reclamation threads announce entering and leaving a global epoch; a node removed in epoch $e$ is freed once every thread has left $e$ (Fraser, 2004).

Both defer freeing until no reader can hold the node, and both put a cost on the read path: hazard pointers a store and a fence per node read, epochs a store on entering and leaving each operation. On a hot path the simplest reclamation is none: fixed pools whose slots are recycled but never returned to the system (chapter 6), bounded rings whose cells are reused by position (chapter 12), and the tagged indices of the tutorial. Reclamation matters for unbounded structures shared between many threads, which a hot path should not have.

11.4 Progress guarantees

Definition 11.6 (Lock-free, wait-free)

An algorithm is lock-free if, whatever the scheduling of the threads, some thread completes its operation in a finite number of its own steps: a thread that stalls cannot stop the others. It is wait-free if every thread completes its operation in a bounded number of its own steps, whatever the others do (Herlihy, 1991).

Definition 11.7 (Priority inversion)

Priority inversion occurs when a high-priority thread waits for a resource held by a low-priority thread that cannot run because medium-priority threads take its processor; the high-priority thread is effectively demoted below the medium ones.

The guarantees are about stalls, not speed. A lock-free algorithm’s threads can still collide and retry, and under contention a CAS loop can be slower than a lock (Figure 11.3); what it removes is the possibility that a preempted thread holding a lock stops everyone, and with it priority inversion. Many useful structures sit between the categories: the bounded multi-producer queue of the build uses one compare-and-swap per operation and no locks, yet its author notes that it is not lock-free in the official sense, because a producer stopped between claiming a cell and filling it holds up the consumers of that cell. Wait-free structures are rarer and usually slower on average; a single-producer single-consumer ring (chapter 12) is wait-free for free, and is the structure trading hot paths use most.

The counters make the chapter’s second lesson concrete. With one thread every design costs a few nanoseconds. With two or more, every design that writes one shared line pays for the line bouncing between cores (chapter 3) at each update, a CAS loop also for its retries, a mutex also for the lock’s own line; the per-thread counters, each on its own cache line, cost what they cost alone. The fastest synchronisation is the one that is not needed: give each thread its own data and combine at the end, or hand data over in one direction only.

11.5 Tutorial: a stack, a queue and a litmus test

11.6 Build: the bounded multi-producer multi-consumer queue

11.7 Exercises

Exercise 11.1 ★

From Figure 11.3, how much does a shared fetch_add cost per increment with one thread and with four? How many increments a second do four threads achieve together, shared and per-thread?

Solution

Solution of Exercise 11.1.

On the committed measurement about $4.7\,\mathrm{n}\mathrm{s}$ alone and $95\,\mathrm{n}\mathrm{s}$ with four threads; together the four threads achieve $4/95\,\mathrm{n}\mathrm{s} \approx 42$ million shared increments a second, against about 730 million with per-thread counters.

Exercise 11.2 ★

A writer stores a price, then sets a flag with release; a reader loads the flag with acquire and, if set, reads the price. Can the reader see the flag set and an old price? And if the flag store is relaxed?

Solution

Solution of Exercise 11.2.

With release on the flag and acquire on its load, no: the acquire that sees the flag sees every write before the release, including the price. With a relaxed flag, yes: nothing orders the price’s store before the flag’s, for the compiler or, on other architectures, the processor.

Exercise 11.3 ★

A tag of 32 bits is incremented at every update of the stack’s head at 100 million updates a second. How long before it wraps, and why is wrapping (almost) harmless?

Solution

Solution of Exercise 11.3.

$2^{32}/10^8 \approx 43$ seconds. A wrap causes a false match only if a thread stalls between its read and its CAS for exactly a multiple of $2^{32}$ updates and finds the same index at the same tag: possible in theory, vanishingly rare in practice, and excluded by a 64-bit tag with a 16-byte CAS if needed.

Exercise 11.4 ★★

In the store-buffer test, which outcomes $(r_1, r_2)$ are possible under sequential consistency, and which extra one does x86 allow with release–acquire? Why does the figure show it so rarely?

Solution

Solution of Exercise 11.4.

Under sequential consistency $(0,1)$, $(1,0)$ and $(1,1)$; x86 with weaker orderings also allows $(0,0)$, when both stores are still in their cores’ store buffers as the loads complete. The window is a few nanoseconds wide, while the two threads’ starts differ by far more on each trial, so they rarely overlap: tens to hundreds of times per million here.

Exercise 11.5 ★★

Why is the bounded MPMC queue not lock-free in the strict sense? Describe the stall.

Solution

Solution of Exercise 11.5.

A producer claims a position with its compare-and-swap, then writes the cell and publishes it. If it is preempted between the two, the cell’s sequence number stays unpublished: the consumer of that position finds the queue “empty” and every later position waits behind it, so one stalled thread stops the others’ progress.

Exercise 11.6 ★★

A logger thread holds a mutex for $2\,\text{µ}\mathrm{s}$ per message, 100 000 times a second, and the trading thread takes the same mutex once per order. What fraction of orders find it held, and how long can one wait if the logger is preempted for a scheduler quantum of $4\,\mathrm{m}\mathrm{s}$?

Solution

Solution of Exercise 11.6.

The mutex is held 20% of the time ($100\,000 \times 2\,\text{µ}\mathrm{s}$), so about one order in five waits, a microsecond on average. If the logger is preempted while holding it, an order can wait the whole quantum, $4\,\mathrm{m}\mathrm{s}$.

Exercise 11.7 ★★★

Coding. Run the untagged stack of ll_lockfree.hpp (mode aba of the benchmark) with two threads popping and pushing back a million times each, twenty times. Is a node ever lost or duplicated? What does the result say about testing lock-free code by running it?

Solution

Solution of Exercise 11.7.

In twenty runs of two million operations no node was lost or duplicated (measured_aba.csv): the vulnerable window, between reading the successor and the compare-and-swap, lasts a few nanoseconds and the scheduler almost never preempts a thread inside it. The code is still wrong; the deterministic replay of Figure 11.2 shows the interleaving. Running lock-free code proves little; the argument must come from reasoning, model checking or tools that explore interleavings.

Exercise 11.8 ★★★

Find the flaw. “Our order-book snapshot is published with a relaxed flag; we tested it for a week on x86 and never saw a torn snapshot, so it is correct.”

Solution

Solution of Exercise 11.8.

Correctness under the C++ model is not a property of one processor: x86 happens to keep stores in order, but the compiler may reorder the snapshot’s writes after a relaxed flag store, and another architecture or compiler version may. The absence of failure in a test is not evidence. Use release on the flag and acquire on its load, or a sequence lock (chapter 12).

11.8 Problem: The Descheduled Lock Holder

Problem 11.1

Weekend problem — a lock shared with the logger

A strategy thread sends about 20 000 orders a second and, for each, takes a mutex to append the order to a log buffer that a logger thread drains. The logger holds the same mutex for $3\,\text{µ}\mathrm{s}$ each time it drains, 50 000 times a second. Once in a while the operating system preempts the logger while it holds the mutex, for a quantum of about $3\,\mathrm{m}\mathrm{s}$; suppose this happens on 0.01% of its drains.

Part I — Contention.

1. What fraction of the time does the logger hold the mutex?
2. What fraction of orders find it held, and how long do they wait on average?
3. What is the expected blocking time per second for the strategy, ignoring preemption?
4. What does Figure 11.3 say about the mutex’s own cost when two threads take it often?

Part II — Preemption.

5. How many preemptions of the lock holder happen per second?
6. What fraction of time is the mutex held by a preempted logger?
7. How many orders a second meet such a preempted holder, and how long does each wait at most?
8. Add Parts I and II: the expected blocking per second.

Part III — The redesign.

9. Replace the mutex by a single-producer single-consumer ring: what does the strategy do per order now?
10. What happens when the ring is full?
11. Which progress guarantee does the ring give the strategy?
12. Why does priority inheritance not solve the problem for a trading thread?

Part IV — The verdict.

13. State the named result: the strategy’s expected blocking time per second with the mutex, and with the ring.
14. What did the Mars Pathfinder engineers do, and why was it enough there?
15. Where else in a trading process can a lock hide?
16. What does the ABA problem require of a lock-free structure that frees memory?
17. How do the build’s tests check the queue, and what can they not prove?
18. When is a mutex the right choice in a trading system?
19. What memory ordering does the ring’s publication need?
20. In one sentence: what does lock-free buy a hot path?

Solution

Solution of Problem 11.1.

1. $50\,000 \times 3\,\text{µ}\mathrm{s} = 15\%$ of the time.
2. 15% of orders (arrivals see the time average), waiting half a hold on average: $1.5\,\text{µ}\mathrm{s}$.
3. $20\,000 \times 0.15 \times 1.5\,\text{µ}\mathrm{s} = 4.5\,\mathrm{m}\mathrm{s}$ a second.
4. With two threads taking it often, each acquisition costs several times its uncontended cost (the lock’s line bounces between cores): about $100\,\mathrm{n}\mathrm{s}$ against $14\,\mathrm{n}\mathrm{s}$ on the committed measurement.
5. $50\,000 \times 0.0001 = 5$ a second.
6. $5 \times 3\,\mathrm{m}\mathrm{s} = 15\,\mathrm{m}\mathrm{s}$ a second: 1.5% of the time.
7. $20\,000 \times 0.015 = 300$ orders a second, each waiting up to $3\,\mathrm{m}\mathrm{s}$, $1.5\,\mathrm{m}\mathrm{s}$ on average.
8. $300 \times 1.5\,\mathrm{m}\mathrm{s} + 4.5\,\mathrm{m}\mathrm{s} \approx 455\,\mathrm{m}\mathrm{s}$ a second: the rare preemptions dominate.
9. It writes the order into its own ring slot and publishes it with a release store: tens of nanoseconds, never waiting for the logger.
10. The strategy must decide: drop the log record (and count the drop) or overwrite, never block; the ring is sized so that it does not fill.
11. Wait-freedom: every push completes in a bounded number of its own steps.
12. Priority inheritance raises the logger’s priority while it holds the lock, but a trading thread’s deadline is microseconds; waking and running the holder takes longer than that, and preemption by the kernel itself is not a matter of priorities.
13. Named result. With the mutex the strategy is blocked about $455\,\mathrm{m}\mathrm{s}$ a second on average, almost all of it behind a preempted logger; with the ring, never.
14. They enabled priority inheritance on the mutex by uploading a patch: enough because their deadline was a bus cycle of milliseconds and the holder could finish quickly once raised.
15. In the standard library (allocators, logging, locale), in third-party libraries, in the dynamic loader, and in any shared configuration object.
16. A way to know that no thread still reads a node before it is reused: tags on reused nodes, hazard pointers or epochs on freed ones.
17. Two producers and two consumers move 300 000 items and check each arrives once, in C++ and Rust, and the C++ test runs under the thread sanitiser. They cannot prove the absence of rare interleavings.
18. Off the hot path, for state touched rarely by threads that can afford to wait (configuration, reporting), where simplicity wins.
19. Release on the store that publishes the slot and acquire on the load that consumes it.
20. It removes waiting on other threads from the hot path: no thread’s stall can stop it.

11.9 Interview questions

Interview question 11.1 ★ developer

What is the difference between memory_order_relaxed, acquire–release and sequentially consistent atomics?

Solution

Solution of Interview question 11.1.

Relaxed: atomicity only. Acquire–release: a release store publishes all earlier writes to the thread whose acquire load reads it. Sequentially consistent: additionally a single total order of all such operations, forbidding for example both threads of a store-buffer test reading zero.

What the interviewer is looking for: publication versus a global order, with an example.

Interview question 11.2 ★★ developer

Explain the ABA problem and two ways to prevent it.

Solution

Solution of Interview question 11.2.

A compare-and-swap succeeds because the value is again what it read, although it changed in between and the state computed from it is stale. Prevent it with a tag incremented on every update (compared with the pointer), or by never reusing a node while a reader may hold it (hazard pointers, epochs, or nodes that are never freed).

What the interviewer is looking for: the mechanism and two independent remedies.

Interview question 11.3 ★★ developer

Is a lock-free algorithm always faster than one with locks? Give a counterexample.

Solution

Solution of Interview question 11.3.

No. Under heavy contention on one location, a CAS loop retries and can be slower than a mutex; the chapter’s counters show a CAS loop at about $200\,\mathrm{n}\mathrm{s}$ per increment with four threads. Lock-freedom is a guarantee about stalls, not about speed.

What the interviewer is looking for: progress versus throughput.

Interview question 11.4 ★★ developer

What is priority inversion, and why does it matter in a trading system?

Solution

Solution of Interview question 11.4.

A high-priority thread waiting for a lock held by a low-priority thread that medium-priority work keeps from running. On a desk the hot thread waits for a logger or reporter that the scheduler preempted, for milliseconds.

What the interviewer is looking for: the three-thread mechanism and a trading instance.

Interview question 11.5 ★★ developer

How do you test lock-free code? What can a stress test not tell you?

Solution

Solution of Interview question 11.5.

Stress tests with checks of invariants (every item once), sanitisers, tests that perturb scheduling, model checking of the algorithm, and deterministic replays of known bad interleavings. A stress test cannot show that a rare interleaving is harmless, only that it did not happen.

What the interviewer is looking for: tools beyond running it, and the limits of testing.

Interview question 11.6 ★★★ developer

Design a counter that many threads increment and one thread reads once a second, with the lowest cost to the incrementing threads.

Solution

Solution of Interview question 11.6.

One counter per thread, each on its own cache line, incremented with a relaxed operation (or a plain write if only its owner writes and the reader tolerates a slightly stale value); the reader sums them. No line is shared between writers.

What the interviewer is looking for: sharding by thread and cache-line padding.