Read-Copy-Update (RCU): A Primer

This post introduces Read-Copy-Update (RCU), the synchronization mechanism the Linux kernel uses to let readers traverse shared data structures at essentially zero cost while writers concurrently modify them. RCU is not a lock in the conventional sense: it enforces no mutual exclusion between readers and writers at all. Instead, it replaces the question “who may access this data?” with a different one — “when is it safe to free this data?” — and answers it with a mechanism cheap enough that the kernel invokes it billions of times per second.

What was missing

The previous post in this series ended with a progression. The reader–writer lock admits concurrent readers, but every reader performs an atomic read-modify-write on the lock word, so all readers serialize on one cache line — at high core counts, the coherence traffic alone can cost more than the critical section it protects. The seqlock removes reader-side writes entirely, but readers must retry whenever a writer intervenes, and because a reader may observe torn intermediate state, seqlocks cannot safely protect pointer-linked structures: a half-updated pointer that is dereferenced is a crash, not a retry.

What was missing is a primitive with all of the following properties:

Wait-free, invisible readers. A reader executes no atomic operations, no writes to shared memory, no memory barriers (on most architectures), and never retries or blocks. Reader overhead is that of an ordinary function call — in non-preemptible kernel builds, exactly zero instructions.
Pointer-linked structures. Readers may follow pointers through lists, hash tables, and trees while writers concurrently insert, remove, and replace elements.
Concurrent forward progress. Writers never wait for readers to finish before modifying the structure — only before reclaiming memory.

RCU provides precisely this, at a deliberate semantic price: readers and writers genuinely overlap, so a reader may observe data that is slightly stale, and two readers may simultaneously observe different versions. RCU is therefore not a drop-in mutex replacement; it is a specialization for read-mostly data where such relaxed semantics are acceptable — which, in an operating-system kernel, turns out to be remarkably often.

The core idea

RCU decomposes every update into two phases separated in time:

Removal. The writer makes the old data unreachable — typically by atomically swinging one pointer from the old version to a new one. Readers that arrived before the swing may still hold references to the old version; readers arriving after see only the new version. Both proceed without interference.
Reclamation. The writer frees the old version — but only after a grace period has elapsed: a window guaranteed to contain the completion of every reader that could possibly hold a reference to the old version.

The correctness argument rests on one rule. Readers bracket their accesses in read-side critical sections, and a reader may not hold a reference to RCU-protected data outside such a section. A grace period, by definition, waits until every read-side critical section that was in flight at the start of the grace period has ended. Any reader that could have obtained a reference to the removed data must have started before the removal — hence before the grace period — hence must have finished by the time the grace period ends. Freeing the data after the grace period is therefore safe, without ever knowing which readers, if any, actually touched it.

flowchart LR
    A["<b>Copy</b><br/>allocate a new version"] --> B["<b>Update</b><br/>modify the private copy"]
    B --> C["<b>Publish</b><br/>rcu_assign_pointer()"]
    C --> D["<b>Grace period</b><br/>synchronize_rcu() waits for<br/>all pre-existing readers"]
    D --> E["<b>Reclaim</b><br/>kfree() the old version"]

    classDef prep fill:#dae8fc,stroke:#6c8ebf,stroke-width:1.5px,color:#1a1a1a
    classDef pub fill:#d5e8d4,stroke:#82b366,stroke-width:1.5px,color:#1a1a1a
    classDef wait fill:#ffe6cc,stroke:#d79b00,stroke-width:1.5px,color:#1a1a1a
    classDef free fill:#f8cecc,stroke:#b85450,stroke-width:1.5px,color:#1a1a1a
    class A,B prep
    class C pub
    class D wait
    class E free

The name is now self-explanatory: read the existing version, copy it, update the copy, publish, and reclaim after a grace period.

The constructs

The entire read side of the classic RCU API is five primitives:

Primitive	Role
`rcu_read_lock()` / `rcu_read_unlock()`	Delimit a read-side critical section. May nest. Must not sleep inside (classic RCU).
`rcu_dereference(p)`	Load an RCU-protected pointer for reading. A dependency-ordered load — free on every modern architecture.
`rcu_assign_pointer(p, v)`	Publish a new version. A store-release: all initialization of `v` is visible before the pointer swing.
`synchronize_rcu()`	Block until a grace period elapses. Writer-side, may sleep.
`call_rcu(head, func)`	Asynchronous alternative: invoke `func` after a grace period, without blocking.

Two of these deserve emphasis, because they encode the memory-ordering contract. rcu_assign_pointer() guarantees that a reader who sees the new pointer also sees the fully initialized object behind it — without it, the compiler or CPU may reorder the pointer store before the initialization stores. rcu_dereference() guarantees the reader’s subsequent accesses are ordered after the pointer load via the address dependency, and additionally documents to both the compiler and the human that the pointer is RCU-protected. The pair implements the publish–subscribe discipline that makes pointer-following safe where the seqlock’s retry discipline could not.

A toy example

Consider a global configuration object, read on every packet but updated a few times a day — an extreme read-mostly ratio, ideal for RCU:

struct config {
	int threshold;
	int mode;
};

static struct config __rcu *cfg;
static DEFINE_MUTEX(cfg_mutex);      /* serializes writers only */

/* Read side: no locks, no atomics, no barriers, no retries. */
int cfg_threshold(void)
{
	int t;

	rcu_read_lock();
	t = rcu_dereference(cfg)->threshold;
	rcu_read_unlock();
	return t;
}

/* Write side: copy, update, publish, wait, reclaim. */
void cfg_set(int threshold, int mode)
{
	struct config *new, *old;

	new = kmalloc(sizeof(*new), GFP_KERNEL);
	new->threshold = threshold;
	new->mode      = mode;

	mutex_lock(&cfg_mutex);
	old = rcu_dereference_protected(cfg,
	                                lockdep_is_held(&cfg_mutex));
	rcu_assign_pointer(cfg, new);    /* removal: publish new version */
	mutex_unlock(&cfg_mutex);

	synchronize_rcu();               /* wait for pre-existing readers */
	kfree(old);                      /* reclamation: now provably safe */
}

Note what RCU does not provide here: writers still serialize against each other with an ordinary mutex. RCU coordinates readers with writers; writer–writer coordination remains the writer’s problem.

The timeline below shows why the kfree() is safe. Reader A began before the pointer swing and may be traversing the old version — the grace period waits for it. Reader B began after the swing, can only have seen the new version, and is not waited for:

sequenceDiagram
    participant W as Writer
    participant A as Reader A (pre-existing)
    participant B as Reader B (later)

    A->>A: rcu_read_lock()
    A->>A: p = rcu_dereference(cfg) — old version
    W->>W: rcu_assign_pointer(cfg, new)
    W->>W: synchronize_rcu() begins
    B->>B: rcu_read_lock() — observes only the new version
    B->>B: rcu_read_unlock()
    A->>A: rcu_read_unlock()
    Note over W: grace period ends — every reader that could<br/>hold the old pointer has finished
    W->>W: kfree(old)

The same pattern extends to linked structures through the _rcu list API — list_add_rcu(), list_del_rcu(), list_for_each_entry_rcu() — which package the publish/subscribe barriers into the list operations themselves.

How the kernel implements it

The elegance of RCU lies in how cheaply the kernel detects “all pre-existing readers have finished” without tracking any readers at all.

Readers that cost nothing

In a kernel built without preemption, a read-side critical section cannot be interrupted by a context switch — code holding rcu_read_lock() runs until it releases. Therefore, if a CPU has passed through a context switch, it cannot be inside any read-side critical section that began before that switch. A context switch is a quiescent state, and a grace period is complete once every CPU has passed through one. This yields the remarkable implementation:

static inline void rcu_read_lock(void)  { }   /* literally nothing */
static inline void rcu_read_unlock(void) { }

The read-side primitives compile to zero instructions; all cost is displaced to the writer, who waits for every CPU to context-switch.

**What about preemptible kernels?** In a kernel built with `CONFIG_PREEMPT`, the argument above collapses: a task can be preempted *inside* a read-side critical section, so a context switch no longer proves that a CPU's readers have finished. Preemptible RCU therefore reintroduces a minimal amount of state, while keeping the fast path free of atomic instructions and memory barriers:

rcu_read_lock() increments current->rcu_read_lock_nesting — a plain, non-atomic, per-task counter. It is a counter rather than a flag because read-side critical sections may nest.
If the task is preempted while that counter is nonzero, the scheduler queues it on the blkd_tasks list of its CPU’s leaf rcu_node. The grace period now waits not only for every CPU’s quiescent state but also for every task on these lists to exit its critical section.
rcu_read_unlock() decrements the counter. In the common case that is the whole story — a few local instructions, exactly as in the non-preemptible build. Only a task that was actually preempted (or boosted) inside the critical section takes a slow path, rcu_read_unlock_special(), which removes it from the blocked list and reports the deferred quiescent state.
A new hazard appears: a low-priority reader preempted indefinitely would stall grace periods — and with them, all deferred reclamation — forever. Preemptible RCU therefore includes priority boosting: a reader that blocks a grace period for too long is temporarily boosted through an rt-mutex until it exits its critical section.

The invariant across both builds is worth internalizing: the read-side fast path never executes an atomic operation or a memory barrier. Preemptibility merely moves the accounting from “nothing at all” to “a per-task counter, plus a slow path that only preempted readers ever see.”

The grace period: a bitmask cleared by context switches

How does the kernel know that a grace period — “every CPU has passed through a quiescent state” — has actually elapsed? The classic implementation (Linux through 2.6.28) used exactly the mechanism one would design on a whiteboard: a global bit vector with one bit per CPU, held in struct rcu_ctrlblk as a cpumask.

The protocol:

Start. When a grace period begins, the bit for every online CPU is set: every CPU owes one quiescent state.
Detect. Each CPU, from its scheduler-tick and softirq path, notices that it has passed through a quiescent state since the grace period began — a context switch, or execution in the idle loop or user mode, since none of these can occur inside a read-side critical section.
Report. The CPU clears its own bit in the mask (under a global lock).
End. The CPU that clears the last bit ends the grace period: pending callbacks advance, synchronize_rcu() callers wake, and the next grace period, if needed, begins.

flowchart LR
    S["Grace period starts<br/>cpumask = 1 1 1 1"] --> A["CPU 1<br/>context-switches<br/>cpumask = 1 0 1 1"]
    A --> B["CPU 3 enters<br/>the idle loop<br/>cpumask = 1 0 1 0"]
    B --> C["CPU 0, then CPU 2,<br/>context-switch<br/>cpumask = 0 0 0 0"]
    C --> E["Grace period ends<br/>callbacks invoked,<br/>old versions freed"]

    classDef pend fill:#ffe6cc,stroke:#d79b00,stroke-width:1.5px,color:#1a1a1a
    classDef done fill:#d5e8d4,stroke:#82b366,stroke-width:1.5px,color:#1a1a1a
    class S,A,B,C pend
    class E done

Two properties of this design are worth internalizing. First, detection is entirely passive: the writer interrupts no one and readers report nothing; the bookkeeping piggybacks on scheduler events that were happening anyway, which is why a grace period costs the read side nothing. Second, the mechanism is deliberately conservative: the kernel does not know whether any CPU actually held a reference to the retired data — it waits for all of them regardless, trading grace-period latency (milliseconds) for zero per-reader accounting. A CPU sitting in dyntick-idle with its tick stopped is handled specially: it is recorded as already-quiescent so that an idle machine need not be woken just to clear a bit.

From one bitmask to a tree

The global mask has an obvious flaw: every CPU clears its bit under one global lock, so at hundreds of CPUs the grace-period bookkeeping itself becomes a contention bottleneck. Tree RCU (merged in 2008, and the implementation ever since) keeps the bitmask idea but shards it hierarchically: CPUs are grouped under leaf rcu_node structures, each holding a ->qsmask bitmask covering up to 16 CPUs (interior levels fan out up to 64). A CPU clears its bit in its leaf node, contending only with its ~15 neighbors; only the CPU that clears a node’s last bit acquires the parent’s lock to clear one bit there, and so on to the root. Lock contention is bounded per level and grace-period propagation is O(log N), which is how the same code runs unmodified from 4-CPU phones to 1024-CPU servers.

Deferred reclamation at scale

synchronize_rcu() blocks for a full grace period — typically milliseconds — which writers on hot paths cannot afford. call_rcu() instead appends a callback to a per-CPU list that is invoked (in softirq context or per-CPU rcuo kthreads) after the grace period ends. A busy system batches thousands of reclamations behind one grace period, amortizing the detection cost to near zero per update.

The variants

The mechanism generalizes along the “what is a quiescent state” axis: SRCU (sleepable RCU) permits readers to sleep by tracking per-domain reader counts; RCU-bh treats softirq completion as quiescence (protecting networking data from denial-of-service by packet floods); expedited grace periods (synchronize_rcu_expedited()) trade IPIs to every CPU for microsecond-scale grace periods when latency matters more than efficiency.

How it is used

RCU is not an exotic corner of the kernel; it is load-bearing infrastructure, with well over ten thousand call sites. Canonical users:

Path-name lookup. Every open() walks the dentry cache under RCU; the pre-RCU implementation took per-dentry locks on every path component, which limited multi-core file-system scalability. RCU-walk turned path lookup into a lock-free traversal with a fallback to the locked slow path.
Networking. Routing-table (FIB) lookups, netfilter rule traversal, and socket lookups all run under RCU — a router forwards packets over a routing table that is concurrently being updated, without a reader-side lock anywhere on the forwarding path.
Existence guarantees. A pervasive idiom: an object may not be freed while a reader can still reach it, so “look up under RCU, then take the object’s own lock (or elevate its refcount) before use” replaces a global lookup lock with per-object synchronization.
Type-safe memory. SLAB_TYPESAFE_BY_RCU allows a slab to reuse memory within a grace period, provided it is reused only as the same type — a weaker but cheaper guarantee that lock-free lookups validate with a recheck after acquiring the object’s lock.

The boundaries are equally important. RCU is inappropriate when readers must observe the single latest value (its readers tolerate staleness), when updates are frequent relative to reads (grace-period and copy overhead dominates), and — for classic RCU — when readers must sleep (use SRCU). Within its niche of read-mostly, staleness-tolerant data, however, measurements consistently show reader-side costs orders of magnitude below any lock, precisely because there is nothing to measure.

What was missing#

The core idea#

The constructs#

A toy example#

How the kernel implements it#

Readers that cost nothing#

The grace period: a bitmask cleared by context switches#

From one bitmask to a tree#

Deferred reclamation at scale#

The variants#

How it is used#

Further reading#