Read-Copy-Update: Publishing New Versions and Waiting Out Old Readers

A read-copy-update reader executes no atomic instruction, writes no shared word, and holds no lock. It reads a pointer, follows it, and finishes. A writer that wants to change the pointed-to structure allocates a replacement, fills it in, and stores the new pointer in a single atomic operation. Readers that started before the store continue on the old structure. The old structure cannot be freed until every such reader has finished, and determining when that is true is the entire problem RCU solves.

The three operations and the one that is hard

The interface is small enough to state completely. A reader brackets its critical section with something that marks it as being inside, a writer publishes a new pointer with release semantics, and a writer waits for a grace period before reclaiming the old object. On Linux the reader’s bracket is rcu_read_lock() and rcu_read_unlock(), which in the common configuration compile to nothing at all: they prevent the compiler from moving accesses across the boundary and, in a preemptible kernel, increment a per-task nesting count that the scheduler consults. The writer’s publication is rcu_assign_pointer(), which is a release store. The wait is synchronize_rcu(), which blocks until a grace period has elapsed.

The property that makes the reader free is that it never announces which object it is using. It only announces that it is inside a critical section, and the announcement is often implicit in the fact that the reader is running in the kernel with preemption disabled, or in the fact that the reader has not yet passed a quiescent state. Because no reader is registered anywhere, no reader can contend on a shared word, and the read-side cost does not grow with the number of readers or with the number of cores.

The cost moves to the writer and to the reclamation machinery. A writer that frees immediately would free memory that a concurrent reader is still traversing, so it must wait. The wait is what a grace period is: an interval at the end of which every thread that could have been inside a read-side critical section at the start of the interval has left it.

What a grace period must prove

The definition is worth restating carefully, because the common misreading is that a grace period waits for all readers to finish. It does not. It waits until every reader that started before the grace period began has finished. Readers that start during the grace period are irrelevant to the object being reclaimed, because they can only have obtained a pointer to the new version, not the old one.

This is why the proof is a statement about threads rather than about readers. If a thread is known to have passed through a quiescent state since the grace period began, then any read-side critical section it was in at the start has ended. A quiescent state is a point at which the thread demonstrably holds no RCU read lock: a context switch, a return to user mode, an idle loop, or an explicit call. The grace period ends when every CPU has reported a quiescent state, or every task has, depending on the flavour.

The classic implementation for a non-preemptible kernel is the simplest: since a read-side critical section cannot be preempted, a thread cannot be inside one across a context switch. The grace period therefore ends when every CPU has scheduled at least once. A per-CPU counter of context switches suffices, and the writer’s wait is a comparison of a starting snapshot against the counters. On a machine with many CPUs, that wait is at least the time for each CPU to reach a scheduling point, which is bounded by the scheduling-clock interrupt; a CPU that stays in the kernel with interrupts disabled postpones the end of the grace period by however long it remains there.

A preemptible kernel needs more. Since a reader can be preempted inside its critical section, the per-CPU counter is not enough, and the implementation must track which tasks are inside read-side sections, or use a mechanism that blocks preemption during the section. The trade is direct: preemptible RCU gives lower latency for readers at the cost of a more expensive reader bracket and a more expensive grace period.

/* Publication and reclamation, kernel-style, with the ordering made explicit. */
struct config *global_cfg;

void replace_config(struct config *new)
{
    struct config *old = rcu_dereference(global_cfg);

    rcu_assign_pointer(global_cfg, new);   /* release: fields before pointer */
    synchronize_rcu();                     /* wait for pre-existing readers */
    kfree(old);                            /* now provably unreferenced */
}

int read_value(void)
{
    struct config *c;
    int v;

    rcu_read_lock();
    c = rcu_dereference(global_cfg);        /* acquire: pointer before fields */
    v = c->value;
    rcu_read_unlock();
    return v;
}

The reader’s rcu_dereference carries an acquire dependency, so the field loads happen after the pointer load. Without it, a weakly ordered machine can speculatively read c->value from the old object after having loaded the new pointer, or the compiler can hoist the load above the pointer read. The dependency is what makes the read safe without a fence on the reader’s fast path on architectures that track address dependencies.

The writer’s rcu_assign_pointer must be a release store so that the new object’s fields are visible before the pointer. If the pointer becomes visible first, a reader can follow it and read uninitialized memory. This is the same publish-and-consume pattern as acquire and release ordering, applied to a heap object instead of a flag.

The variants and their costs

Several flavours of the same idea exist because the grace period’s cost depends on what the kernel can assume.

The non-preemptible flavour has the cheapest reader and the coarsest grace period: a reader blocks preemption for its duration, so a long read-side section delays every grace period on that CPU. A read-side section that sleeps is a bug, since sleeping inside a section that assumes non-preemption deadlocks the grace period.

The preemptible flavour lets a read-side section be preempted and even migrate, tracking sections per task. The reader pays an increment and a decrement of a task-local nesting counter and, in some configurations, a memory barrier. The grace period must then wait for the tracked tasks, which is more work but does not require every CPU to schedule.

The sleepable flavour permits a read-side section to block, which is necessary for code that must perform I/O or allocate memory while holding a reference to a protected structure. The implementation depends on sleeping readers being tracked explicitly, and the grace period is correspondingly more expensive.

The expedited variants force a grace period to complete quickly by sending inter-processor interrupts to every CPU and waiting for them to be handled. An ordinary grace period ends when every CPU has passed through a quiescent state, so it is bounded below by the scheduling-clock period and in practice takes on the order of milliseconds on a busy machine; an expedited grace period shortens the wait to the time an interrupt takes to be delivered and handled, on the order of tens of microseconds, at the cost of interrupting every core. That ratio is why expedited grace periods are used only on paths where the delay is unacceptable, such as module unload or filesystem unmount.

There is also a variant that does not block the writer at all: a callback-based interface schedules the free to happen after the grace period rather than waiting for it. The writer continues immediately, and the reclamation happens later on a worker. This is the preferred form in interrupt context and in any path that cannot sleep.

Where the pattern stops working

RCU’s assumptions are specific, and the failure modes follow from violating them.

The reader must not block, in the flavours that assume non-preemption. A read-side section that calls into code which sleeps leaves the section open across a context switch, and the grace period may complete while the reader is still holding a reference. The resulting use-after-free is intermittent and appears only under memory pressure.

The reader must not retain a reference past the end of the section. A pointer stored in a local variable and used after rcu_read_unlock is no longer protected, and the object may be freed at any moment. The discipline is that the section must cover every access, which is easy to state and easy to break when a helper function is refactored.

The protected object must be replaced rather than modified. In-place updates are visible to concurrent readers, and RCU gives no consistency guarantee for them. A writer that changes a field of the live object creates a data race with readers that the mechanism cannot detect. This is why the pattern is called read-copy-update: the copy is mandatory. Structures that cannot be cheaply copied, or that are too large to duplicate, are poor candidates, which is why RCU is used for pointer-linked tables, configuration blocks, and lookup structures rather than for large mutable arrays.

Writers must be serialized among themselves. RCU provides no mutual exclusion on the write side; two concurrent writers replacing the same pointer both succeed at the store and one update is lost. A separate lock around the update is required, and it is usually a spinlock or a mutex that is held only by writers.

Finally, the memory must eventually be freed by something that is not the writer’s fast path. A callback-based design needs a worker, a queue, and a bound on the backlog. If the reclamation cannot keep up with the update rate, the deferred objects accumulate, and the mechanism turns into a memory leak with a delay. Systems that update a protected structure on every packet must use per-CPU copies or a different mechanism rather than a single RCU-protected pointer.

Why the read side wins

The economics are simple to state and hard to beat. A reader under RCU costs a compiler barrier and, in the preemptible flavour, two counter operations on memory that is local to the task. A reader under a reader-writer lock costs an atomic increment and decrement on a shared cache line, which under many readers is a coherence hot spot, as described in reader-writer locks and their scaling limits. On a machine with dozens of cores reading the same structure, the difference is not a constant factor but a change in scaling: RCU’s read cost is flat, and the lock’s is not.

The price is paid in the write path and in the discipline required of readers. That trade is acceptable exactly when reads vastly outnumber writes, which is the common shape of kernel data: routing tables, mount tables, security hooks, and configuration. Where writes are frequent, the grace period dominates and the mechanism loses to a lock. Where the read side must sleep, the mechanism needs its most expensive flavour. The design is not a universal replacement for locking, and treating it as one produces the use-after-free bugs that its discipline is meant to prevent.

The related problem of freeing memory in a lock-free data structure, where there is no reader bracket to bound at all, is treated in lock-free reclamation and the ABA problem.