Read-Copy-Update (RCU) & Lock-Free Read Access

A 48-core router forwards 10 million packets per second. Each packet needs a routing table lookup. A BGP peer sends an update that changes one route. How does the kernel modify the routing table without making any of those 10 million lookups wait?

The answer is not a read-write lock. A read-write lock forces every reader to atomically increment a shared counter, and on 48 cores that counter's cache line bounces across 48 L1 caches on every single packet. Uncontended in the traditional sense, but devastatingly slow at scale.

RCU -- Read-Copy-Update -- solves this by eliminating reader-side synchronization entirely. Readers do not lock anything. Readers do not increment anything. Readers do not even execute a memory barrier. They just read. The cost of an RCU read-side critical section on x86 is literally zero instructions beyond the normal read.

What Actually Happens

Here is the sequence for an RCU-protected data structure update:

1. Read side. Any CPU that needs to access the shared data calls rcu_read_lock(), reads the pointer with rcu_dereference(), uses the data, and calls rcu_read_unlock(). On non-preemptible kernels, rcu_read_lock() compiles down to preempt_disable(). No atomic operation. No shared cache line touched.

2. Copy. The writer allocates a new version of the data structure and initializes it completely. The old version is not modified.

3. Update. The writer calls rcu_assign_pointer() to atomically swing the global pointer from the old version to the new version. This includes a write barrier so that readers on other CPUs see the fully initialized new structure, not a half-written one.

4. Wait. The writer calls synchronize_rcu() (blocking) or call_rcu() (non-blocking callback). This waits until every CPU that might have been reading the old version has finished its read-side critical section. The kernel tracks this by watching for quiescent states -- context switches, idle periods, user-mode execution.

5. Reclaim. After the grace period, no reader can possibly hold a reference to the old version. The old memory is freed.

The critical insight: the writer never touches the old data. Readers of the old version keep reading it without interruption. Readers that start after step 3 see the new version. There is no moment where any reader sees inconsistent data, and no moment where any reader waits.

For the routing table, this means: fib_lookup() runs entirely inside rcu_read_lock(). Ten million lookups per second across 48 cores, each touching only its own CPU-local data. When a route changes, the new entry is published via rcu_assign_pointer(), and the old entry is freed via call_rcu() after the grace period. Packet forwarding is never interrupted.

Under the Hood

Grace period detection. The kernel must determine when every CPU has passed through a quiescent state. The production implementation (Tree RCU, in kernel/rcu/tree.c) organizes CPUs into a hierarchical tree. Leaf nodes group 16-64 CPUs. Each CPU reports its quiescent state to its leaf node via a bitmask. When all CPUs in a leaf have reported, the leaf propagates up to its parent. When the root node sees all children reported, the grace period ends. This hierarchical approach scales to thousands of CPUs without a single global lock.

What counts as a quiescent state. For RCU-sched (the variant used by most kernel code): a context switch, entering the idle loop, or executing in user mode. The scheduler calls rcu_note_context_switch() on every context switch. The idle loop calls rcu_idle_enter(). These are events that already happen constantly -- RCU piggybacks on them rather than adding new synchronization.

rcu_read_lock() internals. On CONFIG_PREEMPT_NONE or CONFIG_PREEMPT_VOLUNTARY kernels:

static inline void rcu_read_lock(void) {
    preempt_disable();  /* One instruction: increment per-CPU preempt_count */
}

That is it. No atomic. No barrier. No shared memory access. On CONFIG_PREEMPT_RT (real-time) kernels, RCU read-side critical sections are preemptible, and rcu_read_lock() becomes a per-CPU reference count -- still cheap, but not free.

call_rcu() vs synchronize_rcu(). synchronize_rcu() puts the caller to sleep until the grace period ends. Simple to reason about, but it blocks. call_rcu() registers a callback function and a pointer; the callback runs after the grace period in softirq context. This is how the networking code works -- call_rcu(&old_route->rcu_head, route_free_rcu) queues the free and returns immediately. The writer continues without waiting.

rcu_barrier() drains callbacks. When a kernel module is unloaded, any pending call_rcu() callbacks referencing module code must complete before the module's code pages are freed. rcu_barrier() blocks until all previously queued callbacks on all CPUs have executed. Without it, unloading a module with pending callbacks causes a kernel oops when the callback tries to execute freed code.

Memory ordering. On x86, rcu_dereference() is a plain pointer load -- x86 hardware does not reorder dependent loads, so if the pointer load returns the new pointer, all subsequent dependent loads see the data the writer initialized before publishing. On ARM and POWER, rcu_dereference() includes a data dependency barrier (smp_read_barrier_depends() or the C11 memory_order_consume equivalent) because these architectures can speculatively satisfy dependent loads from stale cache lines.

Common Questions

How does RCU handle data structures larger than a single pointer?

RCU protects pointer-mediated access, not individual fields. The pattern is: allocate a complete new structure, populate it fully, then swing one pointer. For linked lists, list_add_rcu() and list_del_rcu() manipulate next/prev pointers with the necessary barriers so that readers traversing the list under rcu_read_lock() always see a consistent chain. A reader might traverse the old path or the new path depending on timing, but it never sees a corrupted pointer or a dangling reference.

What happens if a reader is preempted in an RCU critical section on a CONFIG_PREEMPT kernel?

On preemptible kernels, rcu_read_lock() does not disable preemption. Instead, the kernel tracks which tasks are inside RCU read-side critical sections using a per-task counter. The grace period cannot end until all such tasks have exited their critical sections. This means a preempted reader extends the grace period -- writers wait longer, but correctness is maintained. This is why preemptible RCU has slightly higher overhead and longer grace periods than non-preemptible RCU.

Can RCU completely replace read-write locks?

Not always. RCU works when reads vastly outnumber writes and when the data can be updated by replacing an entire structure via pointer swap. It does not work for in-place field updates (use per-field atomics or seqlocks), does not work when reads must block (use SRCU), and adds complexity that is not justified when a simple mutex has acceptable performance. The rule of thumb: if read-side scalability across many CPUs is the bottleneck, RCU is the answer. If the workload is write-heavy or runs on fewer than 8 cores, a rwlock is simpler and sufficient.

How much memory overhead does deferred freeing add?

Grace periods typically complete in 1-20ms. In that window, old versions of updated structures remain allocated. For a routing table that changes 100 times per second, that is at most 1-2 old route entries alive at any time -- negligible. For a workload that deletes 100,000 objects per second via call_rcu(), the backlog can reach thousands of pending callbacks per CPU. The kernel monitors this and can invoke callbacks more aggressively (via rcu_nocbs CPUs or by forcing a grace period) to prevent memory pressure. In extreme cases, rcu_barrier() provides a hard synchronization point.