Almost every important kernel data structure is read far more often than it is written:
the list of network routes, the table of mounted filesystems, the set of loaded modules, the process
list. A route is looked up on every single packet; it changes when you plug in a cable. For workloads this
lopsided, even a
Read-Copy-Update (RCU) is the audacious answer: make readers pay literally nothing — no locks, no atomics, no writes, not even a memory fence on strongly-ordered CPUs. Readers just read. All the cost is shoved onto the rare writer, which does not modify data in place but instead copies it, updates the copy, atomically publishes a new pointer, and then waits — through a grace period — until every reader that could still be looking at the old version has finished, before reclaiming it. RCU is one of the most important scalability techniques in the Linux kernel, used in tens of thousands of places.
The writer's job is spelled out by the acronym. Say you want to change one field of a node in a shared list:
The old node is now unreachable to new readers but may still be in use by readers that grabbed the pointer a moment ago. You cannot free it yet. The whole subtlety of RCU is: when is it safe to free the old copy?
This picture is the heart of RCU. The writer publishes the new version at one instant. Any reader that started before that instant might still hold a pointer to the old version, so the old copy must survive until the last such reader is done. The writer waits until every CPU has hit a quiescent state — a point where it cannot possibly hold an old reference — and only then is the grace period over and the old copy safe to free. Readers that start after publication see the new version and are irrelevant to this grace period.
Notice what the writer does not do: it never asks readers to raise a hand, never inspects a reference count, never touches a per-reader variable. It simply waits for a guarantee that follows from the scheduler's own behaviour — "once every CPU has context-switched at least once since publication, no old reader can remain." That is why readers can be free: the bookkeeping lives entirely in the passage of time and the definition of a quiescent state, not in any per-read cost.
A quiescent state for a CPU is any moment it is guaranteed to hold no RCU read-side reference. In classic (non-preemptible) kernel RCU, read-side critical sections run with pre-emption disabled — so a CPU that performs a voluntary context switch must not be inside one. Thus "every CPU has context-switched" is a sound, cheap proxy for "every pre-existing reader has finished." The grace period is the interval from publication until every CPU has reported a quiescent state.
This is delightfully lazy. RCU does not track individual readers at all; it tracks the far coarser event
"has this whole CPU passed a safe point?" That coarseness is exactly why reads cost nothing — the price of
freedom is that the writer's grace period can be long (milliseconds), so RCU batches many pending
frees and reclaims them together. A writer that cannot afford to block calls the asynchronous
Let's model an RCU update over a set of CPUs. Readers come and go; a writer publishes a new version and must wait until all readers that were active at publication time have released before it may reclaim the old copy. The simulation prints the grace period unfolding and shows a reader that started after publication correctly seeing the new value.
RCU makes reads free and writes expensive-but-deferred. A seqlock (sequence lock)
makes the opposite trade and suits a different read-mostly case — small values updated in place, like a
system clock (Linux uses one for
Readers take no lock and never block writers, but — unlike RCU — a reader may have to retry if a write lands mid-read, so the data being read must be safe to read while changing (no pointer chasing into freed memory). Writers are cheap (bump the counter, write, bump again) but must be mutually excluded from each other. Seqlock: cheap writes, retrying reads. RCU: free reads, deferred-reclamation writes. Both exist because the read/write ratio, and whether readers can tolerate a retry, decide which wins.
| Reader cost | Writer cost | Reader can be forced to… | |
|---|---|---|---|
| rwlock | atomic + cache bounce | atomic + exclusion | block on a writer |
| seqlock | 2 counter reads (no write) | cheap (2 counter bumps) | retry the read |
| RCU | ~nothing | copy + grace-period wait | nothing — never blocks or retries |
The magic that unsettles everyone new to RCU: readers write nothing, so how can a writer ever know when they are done? The answer is that RCU offloads its detection onto an event the kernel is already performing anyway — the context switch. In classic RCU, read-side critical sections run with pre-emption disabled, so the very act of a CPU voluntarily switching tasks proves it left any read-side section. The writer therefore needs no communication with readers at all; it just waits for the scheduler to do its ordinary rounds. RCU is, in a sense, synchronization for free by reusing information the system generates for another reason entirely. That is why it scales to hundreds of cores where reference counting and reader-writer locks collapse — the read path adds zero contended memory traffic.
Two misconceptions sink RCU newcomers. First, "RCU is a faster lock" — no: it makes reads nearly free while making writes heavier (copy, publish, and a grace-period wait that can take milliseconds). It is a spectacular win only when reads vastly outnumber writes; for a write-heavy structure it is a poor fit. Second, "readers always see the newest data" — no: a reader that started before a writer published will keep seeing the old version for the rest of its critical section. RCU guarantees each reader sees a consistent version, not necessarily the latest. If your code needs every reader to observe writes the instant they happen, RCU is the wrong tool — you need a lock or a seqlock-style retry. RCU trades a little staleness for enormous read scalability, on purpose.