Locking Primitives, End to End

1.1Why count++ loses increments

A modern processor contains several cores, independent units that each run one thread at a time, so two threads can run at the same moment on two cores. A core doesn't add to a number while it sits in memory. It copies the number into a register, a tiny storage slot inside the core that only the thread running there can see, adds 1 in the register, and copies the result back. So count++ is a load, an add and a store. (Some processors, x86 among them, have an instruction that names a memory address directly, but the core still reads, adds and writes back as separate steps inside it, so the same problem applies.)

The order in which two threads' steps happen to mix is called an interleaving, and most interleavings are harmless. The dangerous one is when both threads load before either stores. Here it is, with count at 5 to keep the numbers small:

Watch the two registers and the single count in the diagram: the lost increment is the moment B stores a 6 that was computed from a 5 that was already out of date. Each thread did its work correctly, and the result is still wrong, because neither could know the other was in the middle of the same three steps.

1.2Causing it yourself

Chapter 03 started from this same experiment, and this version adds the thing we're about to study. The program below runs the two-thread counter twice. std::thread starts a thread running the function it's given, and join waits for that thread to finish. The first run uses a plain long counter. The volatile on it only stops the compiler from folding the whole loop into a single addition of 2,000,000, which it would otherwise be free to do. The second run does the same work on a second counter, but each increment happens inside a block that holds a std::mutex, the C++ lock. std::lock_guard takes the mutex when it's created and gives it back at the closing brace.

Save it as race.cpp, build it with clang++ -std=c++20 -O2 -pthread race.cpp -o race and run ./race. The -O2 flag turns on the optimiser as in a real build, and -pthread links the thread library on Linux.

#include <iostream>
#include <mutex>
#include <thread>
 
volatile long plain = 0;   // volatile: do the load and the store every time
long guarded = 0;
std::mutex m;
 
int main() {
    std::thread a1([] { for (int i = 0; i < 1'000'000; i++) plain = plain + 1; });
    std::thread a2([] { for (int i = 0; i < 1'000'000; i++) plain = plain + 1; });
    a1.join(); a2.join();
 
    std::thread b1([] { for (int i = 0; i < 1'000'000; i++) { std::lock_guard<std::mutex> g(m); guarded++; } });
    std::thread b2([] { for (int i = 0; i < 1'000'000; i++) { std::lock_guard<std::mutex> g(m); guarded++; } });
    b1.join(); b2.join();
 
    std::cout << "no lock:   " << plain << "\n";
    std::cout << "with lock: " << guarded << "\n";
}

no lock:   1004234
with lock: 2000000

The first line is the lost update at full scale. In this run almost half of the two million additions vanished: the two threads ran side by side on two cores, and a large share of the increments were computed from a value the other thread had already moved past, then stored on top of its work. The exact number changes from run to run, and it is practically never exactly two million. The second line is always exactly 2,000,000, because the lock lets only one thread through the count++ at a time.

The next widget lets you be the scheduler, the part of the kernel that decides which thread runs next. Each click runs one instruction of one thread. Produce the lost update by hand, then turn the lock on and try the same interleaving.

1.3What we need from a lock

The stretch of code that only one thread at a time may run is called a critical section. Here it's the load, add and store of count++. The thing that enforces the rule is a mutex, short for "mutual exclusion": a lock with two operations, lock() to take it, which waits if someone else has it, and unlock() to give it back. Think of a café with one bathroom and one key on a wooden spoon. Whoever has the spoon is inside, and everyone else waits at the counter until it's back on the hook.

?Why not use an atomic add for everything?

Chapter 03's fetch_add fixes this particular counter. It's an atomic operation, one that no other thread can see half done, and the whole job here is a single add to a single number. Most critical sections are bigger. Moving money means subtracting from one balance, adding to another and appending a log entry, and no single hardware instruction does all three. A lock protects any stretch of code, however long, by making every thread that wants to run it queue up.

So we need a lock, and the next question is what one looks like inside.

2.1A flag isn't a lock

The first idea is a flag, locked. A thread that wants in waits while the flag is set, then sets it and goes in. When it's done, it clears it.

while (locked) {}   // wait until nobody is inside
locked = true;      // take it
// ... critical section ...
locked = false;     // give it back

It looks right, and it has the same flaw as count++. Suppose locked is false and both threads reach the while at about the same moment. A reads locked and sees false, B reads it and sees false, both fall out of the loop, and both set it to true and walk in. Checking the flag and setting it are two separate steps, just like the load and the store of the counter, and the other thread can slip in between them.

What we need is for the check and the set to happen as a single indivisible step.

2.2Compare-and-swap

Processors provide exactly that, in the form of atomic operations. The one we need is compare-and-swap (CAS): "if this variable still holds the value I expect, replace it with a new one, and tell me whether it worked", all as one atomic step. Chapter 03 introduced it. Here we use it on an integer we'll call the lock word (a "word" being an integer of the size the processor handles in one go), flipping it from 0 (free) to 1 (held):

while (!compare_and_swap(&lock_word, 0, 1)) {}   // keep trying until we flip 0 -> 1
// ... critical section ...
lock_word = 0;                                   // give it back

Now take the same collision. A and B both try compare_and_swap(&lock_word, 0, 1) at the same moment. The hardware lines the two attempts up and runs them one after the other. The first sees a 0, changes it to 1 and reports success. The second sees a 1, changes nothing and reports failure, so it goes round the loop again. Exactly one thread gets in, and that's a working lock. A lock that waits by looping like this is called a spinlock.

2.3What spinning costs

Spinning works, and it has a cost that shows up the moment a thread has to wait for long. A thread stuck in the loop occupies a whole core from section 1 while doing no useful work, and it uses power the whole time it waits.

It gets worse when the thread holding the lock is taken off its core. The operating system runs more threads than there are cores by giving each thread a time slice on a core and then switching to another (chapter 06). If the holder's slice ends in the middle of the critical section, the holder is descheduled. Meanwhile every waiter sits on a core going round the loop, and they can spin for a whole time slice while the one thread that could release the lock isn't running at all.

It would be better for a waiter to go to sleep and be woken when the lock is free.

?Why not always sleep, then?

Because sleeping needs the kernel. A thread can't put itself to sleep and ask to be woken without a system call (syscall for short), a request to the kernel that costs a few hundred nanoseconds even for an empty one (chapter 07 measured about 350), and putting a thread to sleep and waking it later also takes a context switch, where the scheduler stops one thread and starts another. That price is acceptable when someone is waiting. It's far too much to pay on every lock, because most of the time the lock is free when you ask for it.

2.4The futex: spin when it's free, sleep when it isn't

So spinning is cheap when the lock is free and wasteful when it isn't, and sleeping is the reverse. What we want is a lock that behaves like a spinlock when the lock is free and sleeps only when it has to wait.

Linux provides this, and calls it the futex, short for "fast userspace mutex". (Userspace is everything outside the kernel: your program's own code and memory.) With a futex, the lock stays an ordinary integer in your program's memory. If it's free, one atomic instruction takes it and the kernel never hears about it. Only when another thread holds it does the waiter make a system call, futex_wait, that means "put me to sleep until this address changes", and the thread that unlocks makes a matching call, futex_wake, that means "wake someone who's sleeping on this address". Here are the three strategies side by side:

That leaves a puzzle for the unlocking thread. To skip the kernel when nobody's asleep, it has to know whether anyone is, and the kernel is the only one who knows. The answer is in the integer itself.

3.1The futex word

On Linux, std::mutex is a thin wrapper around pthread_mutex_t, the mutex type of the POSIX threads ("pthreads") interface that Unix-like systems share. Its code lives in glibc, the standard C library on most Linux systems. Inside it, the one field that decides whether a thread gets the lock or has to wait is a 32-bit integer called the futex word, and that word takes three values.

A full pthread_mutex_t carries more: the id of the thread that owns it, a count of how many times that owner has locked it (for mutex kinds that let one thread lock twice, which section 5.2 comes back to), and a field saying which kind of mutex it is. These fields are bookkeeping, for error checking and for repeated locking by one thread. glibc reads the kind to choose which code to run and records the owner after it takes the lock, but only the atomic on the futex word decides who gets in, and none of the other fields ever needs the kernel.

Go's sync.Mutex and Java's locks are built differently underneath. They follow the same pattern, though: a single atomic instruction when the lock is free, and a call into the language runtime or the kernel only when someone has to wait, so the rest of this chapter carries over to them.

3.2Why two states aren't enough

Two states, free and held, would be enough for correctness.

?So why a third?

So that unlock can tell whether anyone needs waking. With only free and held, the unlocking thread has no idea whether someone is asleep on the lock, so it would have to call futex_wake on every single unlock, just in case.

Programmers call the code that runs when the lock is free the fast path, and the code that runs when a thread has to wait the slow path. futex_wake is a system call, so it costs a few hundred nanoseconds even when there's nobody to wake (chapter 07 measured about 350 for the bare kernel crossing). The whole fast path costs about four nanoseconds, so a wake call on every unlock would make unlocking close to a hundred times dearer. With two states, that price would be paid on every release to handle a case that almost never happens. With three states, a waiter changes the word to 2 before it goes to sleep. The unlocking thread's atomic instruction hands back the value the word held just before, so the thread only has to check whether that value was 2, a comparison on a number already sitting in a register.

Now we have the pieces, and we can read the algorithm that puts them together.

4.1The fast path: no kernel at all

When nobody else wants the lock, lock() is one cmpxchg and unlock() is one atomic_fetch_sub. Here's thread A running its count++ alone. Watch the kernel row at the bottom: nothing in it changes until the last step confirms it was never needed.

The second function is the clever half. atomic_fetch_sub returns the previous value, so comparing it against 1 asks "was I the only one interested?" When the answer is yes, and it overwhelmingly is, the function returns without entering the kernel. That's where the four nanoseconds comes from, which section 7 measures.

4.2The slow path: parking in the kernel

Now let thread B arrive while A holds the lock. When a thread asks for a lock that someone else holds, the lock is contended. Threads competing for one lock in this way is called contention, and it's the case every slow path exists for. The scene follows B from its first failed attempt to the moment it gets the lock.

B never spins. It sleeps in a kernel queue and is woken by A's unlock. Each of the two system calls costs hundreds of nanoseconds and the sleep itself needs two context switches, so a contended handoff costs about a microsecond instead of a few nanoseconds.

?Why does the kernel key its queues by address?

The kernel doesn't know what a lock is. It keeps a table of wait queues and picks the queue by hashing the address of the futex word, so every thread that waits on one address ends up in one queue. For a lock shared between processes, the kernel builds the key from the shared memory itself (which shared page or file it is, and the offset of the word inside it), which lets two processes reach the same queue even if each maps the shared memory at a different virtual address (chapter 04). A lock private to one process is keyed by that process's address space and the word's virtual address, a cheaper lookup. In both cases the kernel keeps nothing about a lock that nobody waits on. The word in your memory is the lock, and all the kernel manages is the queue of waiting threads.

4.3The race that futex_wait's argument closes

There's a race hiding in the slow path. B sets the word to 2 and then calls futex_wait. Those are two separate steps, and A can unlock in between.

futex_wait(addr, expected) takes the value the caller expects to see, and that value check closes the window. The kernel re-reads the word while holding the lock on that wait queue (the kernel calls it the bucket lock), so a wake can't slip in between the check and the sleep. If the word no longer matches, the call returns at once and B tries again.

macOS has no futex. Its os_unfair_lock uses the system calls __ulock_wait and __ulock_wake, and Windows uses WaitOnAddress. They have different names and the same shape: an atomic in userspace, a kernel queue keyed by address, and a value check to close that race.

So the lock works, and it's fast when nobody waits. The next question is what a program can rely on it for.

5.1What you get

A mutex promises that at most one thread holds it at a time. You also get two things beyond exclusion:

Release/acquire ordering is the memory-model rule from chapter 03: unlock is a release and lock is an acquire, so a thread that locks sees every write made by the thread that unlocked before it. That's the reason code inside a critical section can use ordinary variables.

5.2What you don't get

Everything else you might assume, a mutex doesn't promise:

Fairness is the one that surprises people. A thread that has just released a lock and immediately asks for it again will often win it back, while a thread that's been queued for a millisecond waits longer. Taking a lock that's free in the middle of someone else's wake-up is called barging.

?Why would anyone design a lock that's unfair?

Because barging is what keeps the uncontended path at four nanoseconds, and the uncontended path is the one that runs a billion times a day. The relocking thread's core probably still holds the lock word in its own cache, a small fast memory next to each core that keeps copies of recently used data, so retaking the lock is almost free. Handing the lock to a sleeping waiter instead would mean a wake-up and a context switch on every release.

std::recursive_mutex exists for the reentrancy case, but reaching for it is usually a sign the ownership model needs rethinking.

A lock with no fairness, no ordering of waiters and no idea what it protects still does its one job. What it can't do is stop threads from waiting on each other in ways that never end, and that's the next section.

6.1Deadlock and the one strategy that scales

Give our two threads a second lock each to deal with. Suppose a program protects two counters with two locks, L1 and L2, and the two threads take them in opposite orders:

• Thread A takes L1, and is then about to ask for L2.
• Thread B takes L2, and is then about to ask for L1.
• A waits for L2, which B holds. B waits for L1, which A holds.
• Neither can release what it holds until it gets what it's waiting for, so neither ever moves again.

That's a deadlock: every thread in a cycle is waiting for a lock another one in the cycle holds. The program doesn't crash and doesn't report anything. It stops, with every thread asleep.

There's exactly one prevention strategy that scales, a global lock order. Number your locks, write the order down, and never ask for a lock numbered lower than one you already hold. If A and B both take L1 before L2, the opposite-order case can't happen: whoever takes L1 first also takes L2 first, and the other one waits at L1 holding nothing.

Two tools check the order for you at runtime by watching which locks are taken while which others are held. lockdep does it inside the Linux kernel, and ThreadSanitizer does it for ordinary programs.

6.2Priority inversion and Mars Pathfinder

Every thread has a priority, a number that tells the scheduler whom to run first when there aren't enough cores, and a high-priority thread normally preempts (takes the core from) a lower one. Locks can turn that upside down. A low-priority thread holds a lock and a high-priority thread wants it, so the high one waits. Then a medium-priority thread that wants nothing from the lock preempts the holder, because it outranks it. The high-priority thread is now waiting on a thread that can't run, and it will wait for as long as the medium one keeps the core.

This is priority inversion, and it grounded a Mars lander. On Pathfinder in 1997, a high-priority bus management task blocked on a mutex held by a low-priority meteorological task, which a medium-priority communications task kept preempting. A watchdog timer, a safety check that resets the computer when expected work stops happening, noticed the bus task hadn't finished on time and rebooted the lander, again and again. A fix uploaded from Earth enabled priority inheritance on that one mutex.

Priority inheritance is still the fix, and the reason PTHREAD_PRIO_INHERIT exists in the standard: the holder is temporarily boosted to the priority of its highest-priority waiter, so nothing in the middle can preempt it until it unlocks. Linux implements this with PI futexes, a separate kernel path where the owner's thread id is recorded in the futex word itself.

6.3Convoys

The third failure is the hardest to spot. Picture thread A descheduled in the middle of its critical section, while B and several more threads ask for the same lock. Each of them finds it held, sets the word to 2 and goes to sleep in the kernel queue, as in section 4.2. When A runs again and unlocks, one sleeper is woken, takes the lock, runs its short critical section, and unlocks, which wakes the next one. The threads now move through the lock one at a time in a line, paying a wake-up and a context switch at every handoff, and the line tends to re-form as fast as it drains. This is a convoy.

?Why don't the dashboards show it?

Two measures describe a busy system. Throughput is how much work it finishes per second, and latency is how long one piece of work, such as a request, takes from start to finish. In a convoy throughput can look fine, because the system is still finishing work, while latency falls apart, because every request now waits its turn in a queue whose order nobody chose. Section 7.2 shows a convoy turning up as a number.

Here are the three failures side by side:

We've been saying a handoff is expensive and an uncontended lock is cheap. It's time to put numbers on both.

7.1The uncontended path

First the case from section 4.1: one thread, no one else wants the lock.

Four nanoseconds, no syscall, about two and a half times a bare atomic. If you take one number from this chapter, take that one. A thousand uncontended lock-and-unlock pairs cost about four microseconds, the price of four contended handoffs.

7.2Adding threads

Once threads on different cores take turns on one lock, something new costs time. Recall the per-core cache from section 5.2. Memory is copied into it in pieces of 64 or 128 bytes called cache lines. When one core writes to a line, the coherence protocol, the hardware's rules for keeping the cores' copies in agreement, throws away every other core's copy of that line. The lock word is written on every lock and unlock, so each time a different core takes the lock, the line holding the word has to travel to it from the previous core's cache.

A common way to get the benchmark for this wrong is to fix the total work, say 2,000,000 operations, and split it across the threads. It produces numbers like these:

2 threads    67.1 ns per critical section
4 threads    24.6 ns
8 threads    18.9 ns

Contention seems to get cheaper as threads are added, and that's hard to believe. What shrinks is the work each thread does: eight threads each do 250,000 operations where a single thread would do two million, so the fixed costs of starting threads, which sit inside the timer too, get spread differently at each row. The numbers say nothing reliable about contention.

With fixed work per thread, before you look at the numbers: going from four threads to eight, what happens to the cost per critical section?

One thread pays only the lock itself. Two threads add a handoff on every operation, because the lock word's cache line moves between two cores each time, and the cost rises to 6.24 ns. Four threads cost far more per operation, and eight cost less than four.

?Why is eight threads faster than four?

Once enough threads are waiting, most of them are asleep in the kernel queue, and a sleeping thread doesn't pull the cache line back and forth. The thread that holds the lock has the line in its own cache, so when it unlocks and immediately asks again it usually wins (the barging from section 5.2), and it runs a long batch of critical sections unopposed while the queue waits. Throughput improves and fairness is destroyed. That's the queue of sleepers from the convoy in section 6.3, seen from the side the throughput number shows.

The four-thread row is still open. It swings between 31 and 63 nanoseconds from run to run while every other row is stable to two decimal places. On a chip that mixes fast and slow cores, four threads sit at the boundary where the scheduler's choice of cores can change the answer, which would explain a swing like this, but it hasn't been proven. Pinning the threads to one type of core would settle it, though macOS makes that awkward. An unexplained factor of two is the kind of thing benchmarks quietly average away.

7.3False sharing: costlier than the lock

The cost we just saw came from threads sharing one lock word. The same cost can appear with no lock at all. Suppose thread A increments its own counter a and thread B increments its own counter b, and the two counters happen to sit next to each other in memory. They're different variables, and each thread touches only its own. But a core can't write half a cache line, so when A writes a the whole line, b included, moves to A's core, and when B writes b it moves to B's core. The line bounces between the cores on every write, which is called false sharing.

The picture below puts eight threads' counters side by side. In the top row all eight counters share one line, so every write by any thread takes the line from the others. In the bottom row, each counter is padded out to occupy a whole line of its own.

The experiment gives each of up to eight threads its own std::atomic<long> counter, and each thread adds 1 to its own counter five million times. In one version the eight counters are packed into one array and so share a line. In the other, alignas(128) forces each counter to start on a 128-byte boundary so every counter gets a line to itself. fetch_add with memory_order_relaxed is the atomic add with no ordering requirements, and a private counter needs nothing more. The 128 is the line size on Apple's M-series chips, as the code comment says, and x86-64 processors use 64.

constexpr int LINE = 128;                  // M-series. On x86-64 it's 64.
 
std::atomic<long> packed[8] = {};          // 64 bytes, all inside one line
 
struct alignas(LINE) Padded { std::atomic<long> v{0}; };
std::vector<Padded> padded(8);             // one counter per line
 
// Each thread hammers its OWN counter 5,000,000 times.
// No thread ever touches another thread's data.
for (int t = 0; t < T; t++)
    threads.emplace_back([&, t] {
        for (long i = 0; i < 5'000'000; i++)
            packed[t].fetch_add(1, std::memory_order_relaxed);
    });

The numbers are nanoseconds per increment. Read the padded column first: it falls from 0.82 to 0.27 as threads are added, which is what you hope for from parallel work, because each thread does the same amount and they all run at once. The shared column does the opposite, rising from 3.0 to 14.6 ns, because every added thread is one more core fighting for the same line. At eight threads one alignas(128) is worth fifty-five times. No algorithm changed, no lock was involved, and the only difference is which cache line the bytes landed in.

C++17 added std::hardware_destructive_interference_size for exactly this padding problem. Then the two main C++ standard libraries, libstdc++ and libc++, disagreed about whether it's safe to use in structures shared between separately compiled code, because its value can change with compiler flags. GCC warns when you use it in a header. The libc++ in a current Apple clang provides it, and on an arm64 Mac it reports 256 bytes while sysctl reports a 128-byte line. Check your platform's real line size before you pad.

Now we know what a lock costs and how it fails. The last question is how to find, on a running system, the one lock that's hurting you.

8.1Off-CPU time

When a lock is hurting you, reach first for perf lock contention --threads, a command of Linux's perf profiler. It ranks contended locks by total wait time. It was built for the kernel's own locks, though. A mutex in your program waits through futex_wait, so for those the off-CPU recording below, or perf trace -s, which totals the time each thread spent in each system call, is the more direct view.

?Why not just look at a flame graph?

A flame graph is a chart of where CPU time goes, built by sampling what each thread is running. A blocked thread burns no cycles, so it never shows up in one at all. Wait time answers "where is the time going" far more directly than a CPU profile does. The other half is off-CPU analysis, which records what threads were doing while they weren't on a core, via perf record -e sched:sched_switch -g.

Each of these commands answers a question from this chapter:

# Which lock are threads waiting on, and for how long? (sections 4.2 and 6.3)
perf lock record ./yourapp && perf lock contention --threads
 
# Where do threads go to sleep? (off-CPU time, section 6.3)
perf record -e sched:sched_switch -g ./yourapp
 
# How long do your own threads spend in futex calls? (section 4.2)
perf trace -s ./yourapp
 
# Is it the lock, or the cache line? (sections 7.2 and 7.3)
perf stat -e cache-misses,cache-references ./yourapp
 
# macOS
xcrun xctrace record --template 'System Trace' --launch ./yourapp
 
# A hang with every thread idle: where is each thread stuck? (section 6.1)
gdb -p $PID -batch -ex 'thread apply all bt'

8.2Rules that hold up

1. Keep critical sections short and free of I/O. The shorter the time a lock is held, the less often anyone else finds it held (section 3.2).
2. Take locks in one global order, and write the order down (section 6.1).
3. Don't assume FIFO. If a thread must not starve, build fairness explicitly (section 5.2).
4. Split state so threads rarely want the same lock, and pad hot per-thread data to the real cache line size (section 7.3).
5. Measure with work fixed per thread, and look at wait time, not CPU time, when you hunt contention (sections 7.2 and 8.1).

8.3Symptom, cause, fix

The symptoms are distinctive enough to shortcut most of the search. Here p50 is the median request time and p99 is the time that 99 percent of requests beat, so a flat p50 with a high p99 means most requests are fine and a few are very slow.

8.4The trade you're making