Lock-Free & Wait-Free Programming

1.1Waiting on a thread

Let's put the counter behind a mutex, the lock from chapter 13. Thread 1 takes the lock, reads 5, writes 6 and releases the lock. Thread 2, which asked a moment too late, waits for the release, then reads 6, writes 7 and releases. The counter ends at 7 every time, and that reliability is why a lock is the first tool everyone reaches for.

The weak spot comes from how threads are run. A machine usually has far more threads than CPU cores, so the operating system's scheduler takes a thread off its core whenever it likes, to give the core to another thread. We'll say a thread that has lost its core this way has been descheduled. The thread gets no warning and no say, so it can be descheduled in the middle of its work while it holds the lock. Two other things can pause a thread just as abruptly. A page fault happens when the thread touches memory the kernel hasn't set up for it yet, and the kernel stops the thread to sort that out. A signal handler is a function the kernel runs on a thread when a signal arrives, interrupting whatever the thread was doing at the time.

Here is the first of those going wrong for our counter:

Thread 2 was ready to work the whole time, and the only thing in its way was a thread that wasn't running.

1.2How bad is that?

?How bad is a holder that stops?

Usually the holder gets its core back soon, and the waiters pay some extra latency, meaning the time an operation takes from start to finish. Depending on how long the holder is stopped, that's anything from a few microseconds to a few milliseconds, which is annoying and rarely fatal. Two situations can't afford it at all. The first is an audio program, which has a callback: a function the sound system calls every few milliseconds, and which must hand back the next batch of samples on time. If the callback is stuck behind a lock held by a descheduled thread, the sound glitches. The second is a signal handler that asks for a lock its own thread already holds. The handler is running on top of the interrupted code, so that code can't continue to release the lock, and the thread waits for itself forever. Waiting forever like this is called a deadlock.

In both cases the trouble comes from one thing: a thread can be stopped while it holds something everyone else needs. Take away the holding and the trouble goes with it. So what could the threads use instead of a lock?

2.1Work on a private copy

Think of a shared price list kept by an office. Instead of passing one pen around, everyone copies the master list, makes their change on their own copy, and hands it in. The master accepts a copy only if nobody has changed the master since it was copied. If someone has, your copy is stale, so you copy the master again and redo the work. Nobody holds a pen while thinking, so nobody can be stuck behind a colleague who went to lunch. The price is that some work gets thrown away.

Processors offer exactly this for one word of memory, an integer of the size the processor handles in one go (8 bytes on today's 64-bit machines). The instruction is called compare-and-swap, or CAS, and you met it in chapter 13, where the lock itself was built from it. Here we'll use it on the counter directly. You give it two values: the one you expect to find (what you read earlier) and the one you want to leave behind. In a single step that no other thread can interrupt, it checks whether the word still holds the expected value, and if so, replaces it with the new one. If the word holds anything else, it changes nothing and reports the value it found. An operation that no other thread can ever see half-done is called atomic, and CAS is atomic.

Wrapped in a loop, that gives a recipe: read the counter, work out the new value privately, try the CAS, and if it fails, go round again with the value it reported. We'll call that a CAS loop. Here it is for our counter:

Compare the two ways of handling a collision side by side:

The middle row matters most, because it answers the problem from section 1. A thread that is stopped halfway through a CAS loop has only touched its own private values, so no other thread has to wait for it.

2.2Trying it: two threads, no lock

Let's run it for real. The program below starts two threads that each add 1 to a shared counter a million times, using a CAS loop, and counts how many times a thread had to go round again. Three pieces of it need explaining. std::atomic<long> is a long whose operations are atomic. compare_exchange_weak(seen, seen + 1) is the CAS: it expects the counter to hold seen and wants to leave seen + 1. It returns true if the swap happened. On failure it returns false and also writes the value it found into seen, so the loop can try again without reading the counter a second time. The weak version is allowed to fail occasionally even when the value matched. Some processors build CAS from a pair of instructions, a load and a conditional store, and the store can fail for reasons that have nothing to do with the value, such as another core touching nearby memory. A retry loop absorbs those extra failures for free. Finally, each thread counts its failures in a local variable and adds them to retries once at the end, so the counting doesn't become a second shared hot spot.

Save it as cas.cpp, build it with clang++ -std=c++20 -O2 -pthread cas.cpp -o cas, and run ./cas. First, a prediction.

#include <atomic>
#include <cstdio>
#include <thread>
 
std::atomic<long> counter{0};
std::atomic<long> retries{0};
 
void work(long n) {
    long failed = 0;
    for (long i = 0; i < n; i++) {
        long seen = counter.load();
        while (!counter.compare_exchange_weak(seen, seen + 1))   // lost the race: try again
            failed++;
    }
    retries += failed;
}
 
int main() {
    const long n = 1000000;
    std::thread a(work, n), b(work, n);
    a.join(); b.join();
    std::printf("counter %ld\nfailed attempts %ld\n", counter.load(), retries.load());
}

counter 2000000
failed attempts 398646

The counter is exactly 2,000,000, so no update was lost, and no thread ever held a lock. The second line is the cost. In this run the threads made 2,398,646 attempts to complete 2,000,000 increments, so about one attempt in six was thrown away. The number changes a lot between runs, anywhere from about 200,000 to about 620,000 failures, because it depends on how the two threads happen to overlap. Every one of those failures is work done and discarded, and that is what the CAS loop pays instead of waiting.

A counter is a single word, though, which makes it the easiest case. Most shared data is bigger: lists, queues, stacks. Can the same trick protect a chain of linked nodes?

3.1Pushing without a lock

A stack is a pile where the last thing put on is the first thing taken off. Putting a node on is a push and taking the top one off is a pop. We'll build it as a chain of nodes, each holding a value and a pointer called next to the node below it, with one shared pointer, head, pointing at the top node. Say the stack holds one node, A, and two threads want to push X and Y at the same moment.

struct Node { int value; Node* next; };
std::atomic<Node*> head{nullptr};   // the top of the stack; nullptr when empty

head is atomic, so each read and each write of it happens in one piece. The obvious push has two steps. Point the new node's next at the current top, then make head point at the new node:

void push_unsafe(int v) {
    Node* n = new Node{v, head.load()};   // 1. point at the current top
    head.store(n);                        // 2. make this node the new top
}

Run that on two threads and the same thing goes wrong as with the counter, even though each step on its own is atomic. Both threads read head and see A, and both set their node's next to A. Thread 1 writes head = X, then Thread 2 writes head = Y, overwriting it. Node X is still there, but nothing points at it any more. The push was lost, because there was a gap between reading head and writing it, and the other thread slipped into the gap.

We already know the cure for that gap: replace the final write with a CAS that says "make head point at my node, but only if it still points at the node I saw". This is the classic lock-free stack, called a Treiber stack after R. Kent Treiber, who described it in 1986:

void push(int v) {
    Node* n = new Node{v, head.load(std::memory_order_relaxed)};
    while (!head.compare_exchange_weak(n->next, n,
               std::memory_order_release, std::memory_order_relaxed)) {}
}

The std::memory_order arguments say how much ordering the CAS imposes on the memory operations around it. You can read them as noise for now. Section 7.4 explains why the release matters.

?Why is the loop body empty?

Because there's nothing left to do. On failure, compare_exchange_weak writes the head it found into its first argument, which here is n->next. That is exactly the "point my node at the current top" step, so the retry is already set up, and the loop just calls CAS again.

3.2Two pushes at once

Here are the same two threads pushing X and Y onto a stack that holds A. Watch what each CAS expects, and what a failed one hands back.

One CAS succeeded, and the other saw the head had moved, failed and retried. Neither waited for the other.

?What if Thread 1 is descheduled halfway through?

Nothing happens to anyone else. Thread 1 has only set up its private node X, so it hasn't changed anything shared. Thread 2's CAS goes through as before, and the stack stays correct while Thread 1 is stopped. When Thread 1 wakes, its CAS fails, it retries, and it finishes.

That property has a name. An operation is lock-free when, however the scheduler treats the threads, some thread's operation always completes in a finite number of steps. That's a weaker promise than it sounds, and the next section looks at what it leaves out.

4.1A promise about progress

Look again at what the definition says. It says some thread always completes, and nothing about every thread, or about how fast. In the stack scene Thread 1's CAS failed precisely because Thread 2's succeeded. If Thread 2 kept winning, Thread 1 could lose again and again, and the stack would still be lock-free, because someone wins every round. The more threads fight over the same data, the more often this happens. That fighting is called contention, and it's where these promises get tested.

People who study this rank the possible promises about progress into four standard levels, and lock-free sits third. Blocking is the mutex from section 1: it promises nothing, because one stopped holder stops everyone. Obstruction-free means a thread finishes if it gets to run with no interference. Two threads that keep interfering can undo each other's work forever, which is called livelock: everyone is busy, and nobody gets anywhere. Lock-free rules out livelock for the system as a whole, but a single thread can still starve, meaning it keeps losing and never finishes. Wait-free is the strongest: every thread finishes within a fixed number of its own steps, no matter what the others do. Getting there usually takes a helping scheme, where a thread that finds another's operation half done finishes it for them before doing its own. That's why wait-free code is so much more complex and usually slower. Here are the four side by side:

The sentence to remember from the lock-free row is this one: the system progresses, but your thread might not.

4.2What you're buying

So what does lock-free get you, if not speed?

What does the trade cost? We have the counter, so we can measure.

5.1The same increment, three ways

Here's the plan. We'll make threads increment one shared counter in three ways: with a std::mutex, with the CAS loop from section 2, and with fetch_add. The last one you may remember from chapter 03. It adds a number to a word atomically in one step, with no retry loop, because adding is common enough that processors do it directly. Each thread does 200,000 increments, so adding threads adds work, and each figure is the time per increment. They are the median of three runs on a 10-core ARM chip that has the ARMv8.1 atomic instructions, which we'll meet in section 6.

Before you look at the numbers, a prediction:

With one thread, the CAS loop is about six times faster than the mutex, because there's nobody to collide with, so the loop runs once and never retries. With eight, it's about ten times slower. The crossover sits around four threads, and the mutex column barely moves the whole way down. Blocking turns out to be a very stable strategy. When threads collide, the mutex makes the loser wait, and a waiting thread isn't touching the counter at all. Section 6 shows why touching it is what costs so much.

Two cautions come with this table. The mutex's 15.6 ns at one thread is higher than the 4 ns chapter 13 measured for an uncontended lock, because the two chapters use different benchmark harnesses, so compare rows within this table and not across chapters. And the exact crossover depends on the hardware, so treat the direction as the lesson: the CAS loop gets worse as threads are added, and the mutex doesn't.

Here are the eight-thread numbers side by side:

fetch_add never retries, so it never falls off this cliff. At eight threads it costs about what the mutex does. The question is why the CAS loop falls so far.

6.1The two increments in assembly

The answer starts in the machine code. The compiler turns fetch_add and a CAS loop into very different instructions, and here are both, for an ARM processor:

;; a.fetch_add(1, relaxed)  —  ONE instruction, no branch
add:
    mov   w8, #0x1
    ldadd x8, x0, [x0]        ; LSE atomic: hardware resolves it
    ret
 
;; compare_exchange_weak loop  —  a SOFTWARE retry branch
cas:
    ldr   x8, [x0]
    add   x10, x8, #0x1
    mov   x9, x8
.Lretry:
    cas   x9, x10, [x0]
    cmp   x9, x8
    b.eq  .Ldone
    mov   x8, x9
    add   x10, x9, #0x1
    b     .Lretry             ;        GO ROUND AGAIN

Start with the top half. ldadd belongs to LSE, the large-system atomics that ARM added in version 8.1 of its instruction set. It adds to the word in memory in one step. When several cores execute it at once, the interconnect, the hardware that links the cores and memory, lines them up and applies each add in turn. A core that arrives late waits its turn and re-executes nothing.

In the bottom half the retry is in your program. ldr reads the counter, add works out the new value, and cas tries the swap. Then cmp and b.eq check whether it worked, and if it didn't, mov, add and b .Lretry recompute from the fresh value and go back. (The listing stops where the loop exits.) Every trip round the loop is a whole attempt, and the next step shows what an attempt costs.

Two more terms first. A register is one of the few tiny storage slots inside a core, and the loop keeps its working values there. A cache line is the small fixed-size chunk of memory, typically 64 bytes, that cores copy between their private caches. Only one core can write to a cache line at a time, so if two cores keep updating the same counter, the line has to travel back and forth between them. Here is one losing attempt:

Notice the cost of the failed attempt. It did no useful work, and it still pulled the cache line to its core, which takes the line away from whoever had it. With eight threads, every core is doing this to every other core.

6.2Counting the wasted attempts

We can count it. Let's call the number of attempts per successful increment the number of tries. One thread never collides, so it makes exactly one try per increment. Here is how it grows in the benchmark from section 5:

At eight threads the benchmark completes 1.6 million increments (eight threads times 200,000), and at 6.36 tries each that is about 10.2 million attempts. Of those, 8.58 million are thrown away, 84% of the total. Every discarded attempt still paid for a cache line transfer, and that's where the 162 ns goes. (Tries depend on timing. The two-thread run in section 2 saw about 0.2 failures per increment, against 0.04 here, but in both cases collisions grow with the number of threads.)

That is the cost you can measure. The next problem is that it's hard to see in a profile, and the ones after it are bugs.

7.1Livelock that looks like healthy CPU

Under heavy contention, threads can spend most of their time losing CAS attempts. The algorithm keeps its lock-free guarantee, since someone wins every round, while total throughput collapses, as the 162 ns row showed. Strictly speaking that isn't livelock, because by section 4's definition livelock means nobody gets anywhere. In practice it looks and feels so similar, with every thread busy and little finished, that engineers usually call it livelock anyway, and so do the tables at the end of this chapter.

?Why doesn't profiling catch it?

Because it looks like healthy CPU utilisation. A blocked thread shows up as time spent off the CPU, and perf sched, a Linux tool that records when each thread goes on and off a core, will find it. A thread spinning in a CAS retry loop is 100% on the CPU. In a flame graph, a chart where wider boxes mean more CPU time, it shows up as one hot function that someone will conclude is "just expensive".

The way to catch it is to count instructions retired (the instructions the processor finished) against operations completed. If you finished a million pushes but retired six million loop bodies, that's your answer, and no flame graph would have shown it.

7.2ABA

The next bug is in correctness. To see it we need pop, which removes the top node. It works like push: read head, find the node below it, and CAS head from the top node to the one below:

Node* pop() {
    Node* old = head.load();
    while (old && !head.compare_exchange_weak(old, old->next)) {}
    return old;
}

Look at what the CAS checks: that head still holds the same address as before. It doesn't check that the stack is unchanged. Compare-exchange compares the value in the word and knows nothing of its history. If a pointer goes from A to something else and back to A, the CAS succeeds, and the algorithm can be wrong. This is the ABA problem.

One more piece is needed to see it happen. When a thread frees a node with delete, the allocator, the part of the runtime behind new and delete (chapter 05), keeps that memory and hands it out again for the next new, often straight away. So a brand-new node can land at exactly the address of one that was just freed. Here is a stack of A, B and C, where that leads to ABA:

The CAS did exactly what it promised. The address matched. What it couldn't know is that everything behind that address had changed.

There are two fixes, roughly. One is a tagged pointer: keep a counter next to the address, add one to the counter on every change, and compare both together with a CAS on two words at once (x86-64 and ARM both have such a double-width CAS). Then the value differs even when the address repeats, and Thread 1's stale CAS fails. The other is never to reuse memory until you can prove that no thread still holds a reference to it. That second fix sounds easier than it is.

7.3When can you free a node?

Without a lock, nobody can say when it's safe to free a popped node, and the simple answer, free it immediately, creates a bug even without ABA. A thread reads head, gets pointer A, and is descheduled before it looks inside A. Another thread pops A and frees it. The first thread wakes and reads freed memory, which is a use-after-free.

?Why is this so much harder than with a lock?

With a lock, the holder knows nobody else is looking at the stack, so it can free what it removes. Lock-free code has no such moment. Any thread might be holding a pointer it read a moment ago, and there's no lock to ask. Deciding when a removed node can safely be freed is called memory reclamation. For lock-free structures it's a research area in itself, and three schemes have emerged to answer "when can I free this?".

In hazard pointers, each thread writes the pointer it's about to use into a slot that every other thread can read, and a node may be freed only if no slot holds it. The cost is that each read must publish its pointer and then use a fence, a special instruction that forces that write to become visible before anything after it, and the thread doing the freeing, the reclaimer, must scan every thread's slots. In epoch-based reclamation, a global counter marks the current epoch, a numbered period of time. Threads announce when they start and finish an operation, and a removed node is freed only after every thread has left the epoch it was removed in. Reads are nearly free, but one thread stalled in the middle of an operation holds the epoch open, and memory piles up until it moves.

RCU, short for read-copy-update, goes furthest. Readers take no lock and, on many builds, execute no atomic instructions at all. A writer replaces the data with a new copy, then waits for a grace period, a time long enough that every reader who could have seen the old copy has finished, before freeing it. It makes reads free and pushes all the cost onto writers. Linux uses RCU for its routing tables, its cache of recently looked-up file names (the directory entries from chapter 08) and much else, which makes it one of the most widely used techniques of this kind in production. It only pays off for data that's read far more often than it's written, because writers take turns and each one waits out a grace period.

Here are the three side by side:

crossbeam-epoch is a Rust library for epoch-based reclamation and is a large part of why lock-free structures are approachable in that ecosystem. The stalled-thread failure mode from the table is described in its documentation, and the epoch bookkeeping is clearer there than in most C++ implementations.

7.4Dropping release ordering because x86 didn't care

The last bug sits in the arguments we told you to ignore. The memory_order_release in the push above is load-bearing. It says that when another thread sees the new head, it must also see everything this thread wrote to the node before the CAS: the value and the next pointer. Downgrade it to relaxed and the code still compiles and passes light testing, then fails under load on a weakly ordered machine, one that may make writes visible out of order.

The reason is that a core doesn't write to memory the instant it executes a store. It parks the write in a small queue of its own, the store buffer, and drains it to the cache a little later. On some processors those writes can become visible to other cores in a different order from the one the program wrote them in. So another core can see the new head pointer while the node's value and next are still sitting in the writing core's store buffer, and read garbage from the node. (The reading side needs its half too: pop must load head with at least acquire, the partner of release. The pop above passes no ordering, which gives the strongest one, so it's covered. Chapter 03 explains the pair.)

x86-64, the processor family in most desktops and servers, hides that almost perfectly, because its hardware never lets one store become visible before an earlier one. ARM does allow that, so the same code can fail there. The operational advice is to run your tests on ARM.

Those are the traps. With the costs and the traps in view, we can choose.

8.1Four ways to update shared state

Back to the original question of two threads and a counter. Here are the four options, from the simplest to the strongest guarantee, now that you know what each costs.

8.2Five questions

Most decisions are settled by the first two questions.

1. Can you avoid sharing the thing at all? Give each thread its own copy, such as its own counter, and add the copies together now and then. That beats every algorithm here. Try this first, always.
2. Is there a single hardware atomic for it? Counters, flags and bitsets want fetch_add or fetch_or, never a CAS loop.
3. Is contention low, or the critical section long? Use a mutex. (The critical section, from chapter 13, is the code that runs while the lock is held. When it's long, a CAS loop would throw away a lot of work on every collision.)
4. Is blocking a correctness problem? Signal handler, interrupt, hard real-time: then lock-free, and use an existing implementation.
5. Otherwise measure both. The crossover depends on the hardware, and the table in section 5 is one data point.

Once something is running, how do you tell which of these trouble spots you're in?

9.1Commands for each question

Each question this chapter raised has a tool that answers it. These are Linux commands, and the comment on each points back to the section that raised the question.

# Are threads burning CPU on retries? (sections 6.2 and 7.1)
perf stat -e instructions,cycles ./yourprogram     # compare instructions retired with operations completed
 
# Is it blocked, or spinning? (section 7.1)
perf sched record -- ./yourprogram                 # off-CPU time from blocking shows up here
perf sched latency
 
# Did the compiler emit one atomic instruction or a retry loop? (section 6.1)
objdump -d ./yourprogram | grep -E 'ldadd|cas'     # on ARM
clang++ -O2 -march=armv8.1-a ...                   # target LSE atomics explicitly
 
# Is a node being used after it was freed? Is there a data race? (sections 7.3 and 7.4)
clang++ -fsanitize=address ...                     # catches use-after-free
clang++ -fsanitize=thread ...                      # catches data races

perf stat is the most useful. It prints the instructions the processor retired, and dividing by the number of operations your program completed gives instructions per operation. When that number climbs as you add threads while throughput falls, threads are doing work and discarding it.

9.2Rules that hold up

1. Share less before you share better. Per-thread state with a periodic merge needs no atomics at all.
2. Use fetch_add, fetch_or or exchange when one atomic does the job. A CAS loop for a counter is the slow row in the table.
3. Keep a mutex unless blocking is a correctness problem. It's flat under contention and easy to debug.
4. Use a library for lock-free structures. The hard parts are ABA, reclamation and ordering, and all three fail rarely and under load.
5. Test on ARM, and under load. Dropped orderings and use-after-free don't show up in a quiet test on x86.
6. Measure your own crossover. Count attempts per success at 1, 2, 4 and 8 threads, and compare with a mutex version.

9.3What you trade for what

9.4Symptom, cause, fix