The reader who pays nothing
Guide 4 left you with two ways to answer the reclamation problem — when is it safe to free a node nobody might still be reading? Hazard pointers make each reader announce, with an atomic store, exactly which node it is touching, so a deleter can scan those announcements before freeing. Epoch-based reclamation is cheaper: readers just bump into an epoch counter on entry, and a node is freed only once every reader has moved past the epoch in which it was unlinked. RCU — read-copy-update — pushes the epoch idea to its limit and asks a daring question: can the read side cost literally nothing on the fast path? No atomic, no CAS, no store at all?
The astonishing answer in the classic kernel design is yes. To enter an RCU read-side critical section you call rcu_read_lock(); to leave it you call rcu_read_unlock(). Despite the names, in the original non-preemptible kernel build these expand to nothing that touches shared memory — they only disable preemption on this CPU, which is a cheap per-CPU flag, not a lock and not an atomic. Inside the section a reader follows pointers and reads data with no contention, no cache-line ping-pong, no waiting on anyone. Readers do not block writers and writers do not block readers. The whole asymmetry is deliberate: RCU is built for data that is read constantly and written rarely — routing tables, configuration, the kernel's own internal lists.
Read, copy, update — and the grace period
If readers never lock, how can a writer change anything without tearing the structure out from under them? The answer is the three words in the name. A writer does not mutate a node in place. It reads the current node, makes a private copy, edits the copy, then updates the structure by atomically swinging a single pointer from the old node to the new one. Because the swing is one aligned pointer store, every reader sees either the whole old node or the whole new node — never a half-edited mixture. New readers arriving after the swing follow the new pointer; readers who grabbed the old pointer a moment earlier keep walking the old node, which is still perfectly intact in memory.
So far this is just a careful pointer swap — guide 2's lesson that an aligned pointer store is atomic, now used on purpose. The deep part is reclaiming the old node. The writer has unlinked it, but it cannot free() it yet: some reader who started before the swing may still be walking it. RCU's central idea is the grace period. The writer waits until every reader that was active at the moment of the swing has finished its read-side critical section. Once all of them have called rcu_read_unlock() at least once, no thread can possibly still hold a pointer to the old node — anyone reading now must have arrived after the swing and is on the new node. Only then is free() safe.
How does the writer know the grace period has passed without readers signalling anything? This is the quiet genius of the classic design. Because a non-preemptible reader cannot be context-switched while inside its critical section, the writer can wait for a grace period by simply waiting until every CPU has passed through a quiescent state — a moment where it is provably not in any read-side section, such as a context switch, an idle loop, or a return to user space. Observe each CPU schedule once and you know every prior reader has drained. The kernel call synchronize_rcu() blocks the writer until this happens; call_rcu() instead registers a callback to free the node later, so the writer never blocks at all.
WRITER READER (lock-free, no atomics) ------------------------------------ -------------------------------- new = copy_of(old); rcu_read_lock(); // just disables preempt edit(new); p = rcu_dereference(shared); rcu_assign_pointer(shared, new); use(*p); // walks old OR new node // ^ one atomic pointer swing rcu_read_unlock(); synchronize_rcu(); // wait grace free(old); // now safe -- no reader can still hold 'old'
The barriers hiding in the dereference
There is a subtlety in that read side that cost real kernel developers real bugs, and it ties straight back to the memory ordering you learned last rung. The writer fills in the new node's fields before swinging the pointer. But the reader loads the pointer and then dereferences it to read those fields. If either the compiler or the CPU lets the reader see the new pointer before the new node's fields are visible, the reader walks into a half-initialized node — garbage. The single plain pointer store on its own does not promise the writer's earlier field writes are visible first.
This is why the API has two paired macros that look like plain pointer access but are not. rcu_assign_pointer() on the write side is a release store: it forces all the writer's field initializations to become visible before the pointer itself. rcu_dereference() on the read side is the matching consume/acquire load: it guarantees that once the reader sees the new pointer, it also sees everything the writer published before the swing. Together they build the release-acquire relationship that makes the publication safe — the same happens-before machinery from the memory-model rung, dressed in RCU clothing. Omit them and your code passes every test on x86, where the hardware ordering is strong, then corrupts memory the day it runs on ARM.
Why this is so hard to get right
Step back now over the whole rung. You have a conditional atomic write, a retry loop, the ABA trap, three or four reclamation schemes, and RCU's grace periods. Every piece, examined alone, is comprehensible. So why does this remain a field where world-class engineers ship subtle bugs into shipping systems, and where new lock-free structures are still publishable research? The honest answer is that the difficulty is not in any one piece — it is combinatorial. Correctness must hold across every possible interleaving of every thread at every instruction boundary, and that space is astronomically large.
Concretely, several layers of nondeterminism stack on top of each other. The scheduler can preempt any thread between any two instructions. The CPU can reorder loads and stores within the limits of its memory model. The compiler can reorder, fuse, or delete operations under the as-if rule, and is allowed to assume undefined behavior never happens — a data race is UB, so the optimizer may legally do things that make a racy program behave nonsensically. A bug can require a precise three-way coincidence of timing that appears once in ten billion runs, which means it sails through your test suite, survives months in production, and then corrupts a database at 3 a.m. under a traffic spike. You cannot test your way to confidence here the way you can with sequential code.
And recall the two axes from guide 1, because the hardness lives in their product, not their sum. Linearizability demands you pin down a single instant — the linearization point — at which each operation appears to take effect, and prove that instant is consistent under all interleavings; the reclamation work demands you also prove no node is ever freed while reachable, again under all interleavings. A change that fixes the progress story can silently break the linearization argument, or open an ABA window, or move a free() one instruction too early. The pieces are not independent, so you cannot reason about them one at a time — which is exactly why the whole is so much harder than its parts.
How the experts actually cope
Faced with a space too large to test, the people who do this for a living lean on tools and discipline instead of cleverness. They run ThreadSanitizer on everything, which turns invisible data races into loud failures. They use model checkers and stress tools — CDSChecker, Loom in Rust, the kernel's own RCU torture tests — that systematically explore enormous numbers of interleavings, including the cruel ones a fuzzer would take years to stumble on. For the structures that truly matter, they reach for formal proofs and mechanized verification, because for these algorithms a paper proof is the minimum bar, not a luxury. None of this is optional polish; it is the price of admission.
The most important discipline, though, is knowing when not to do this at all. Lock-free programming buys you exactly one thing — the progress guarantee from guide 1 — and it costs you enormously in design time, review time, and the lifelong risk of a latent race. For the overwhelming majority of programs, a well-placed mutex is correct, fast enough, and far easier to reason about; that is not a failure of ambition, it is good engineering. The right moves are usually to reduce sharing, shrink critical sections, or reach for a battle-tested library structure that experts have already verified — not to hand-roll your own Michael-Scott queue on a deadline.
That is the honest close to this rung. You now understand the real machinery — progress guarantees, CAS and its ABA trap, lock-free stacks and queues and ring buffers, hazard pointers and epochs, RCU and its grace period — not just the names. That understanding is exactly what lets you read this code, reason about a bug report, and recognize when a colleague's clever lock-free idea is quietly broken. It is also what lets you make the wisest move of all with full awareness of the tradeoff: most of the time, reach for the mutex, and save the lock-free machinery for the rare place where its one guarantee is truly worth its very high price.