How Linux RCU Unlocks Read-Side Scaling

A routing table on a busy server is queried millions of times per second and modified perhaps once per minute. A traditional reader-writer lock would serialize every read on those modifications, tanking throughput. Linux RCU fixes this: all readers run completely lock-free, in parallel, on an immutable snapshot; a writer prepares a new version invisibly and flips one pointer—then waits to confirm nobody is reading the old version anymore before freeing it.

Left: traditional locking blocks every reader while a writer mutates. Right: RCU lets readers proceed on the old version while the writer works off to the side.

The Naive Approach: Reader-Writer Locks

Reader-writer locks (rwlocks) promise to separate reader and writer traffic: many readers can hold the lock concurrently, but a single writer blocks them all. On paper, this sounds reasonable for read-heavy workloads.

In practice, it fails catastrophically under concurrency. Consider a routing table on a 64-core server handling a million lookups per second. Each lookup acquires the read lock, scans the table (~100–500 ns), then releases it. A single route update grabs the write lock—which must wait for every in-flight reader to finish, then blocks all new readers until the update is done.

The cost is atomic operations on the read path. Every lookup does atomic_inc(&rwlock->readers) on entry and atomic_dec() on exit. On a 64-core machine, those atomics alone become a bottleneck—each one bounces a cache line between cores, contending for the atomic on the lock word. The write lock almost never runs, but readers starve it. Worse, readers starve each other on the cache line.

Real-world impact: a 64-core system with a read-writer lock on a hot data structure sees throughput drop 50–90% as cores climb, due to lock contention. The atomic operations serialize despite zero actual data dependency.

The RCU Insight: Copy, Flip, Wait

RCU inverts the problem. Instead of protecting the data with a lock, RCU makes the data structure immutable from the reader’s perspective. A writer never modifies in-place. Instead:

1. Copy the data structure (or the relevant portion).
2. Mutate the copy—no lock, no readers watching.
3. Flip one pointer atomically—readers now point to the new version; old-version readers keep their pointers.
4. Wait for a grace period—until every CPU has proven it’s not reading the old version.
5. Free the old version.

Readers require no synchronization at all. They fetch the current pointer (READ_ONCE(ptr)), dereference it, and proceed. No atomics, no locks. All 64 cores can read in parallel without contention. The read-side critical section is just a pointer dereference—typically < 10 nanoseconds.

The trade-off is on the write side. Preparing a new version takes time. But if reads outnumber writes by 100:1 or 1000:1, the amortized cost is negligible.

The Mechanism: Four Stages

RCU in four stages: copy the structure (readers still on old), mutate the copy (old version untouched), flip the pointer (new readers point to new), then wait for grace period (old readers finish and drift away).

Stage 1: Copy

The writer allocates a new version of the data structure and copies the old one into it. At this point, the old pointer is still active—all readers point to the old version. No reader has changed; they keep reading the old data at full speed. The copy runs without any synchronization; it’s a regular memcpy or a custom deep-copy function.

Stage 2: Mutate

The writer modifies the new copy: updating routing table entries, changing config fields, or appending to a list. Again, no lock, no reader synchronization. Readers are oblivious—they’re still reading the old version. This is the key insight: isolation without blocking.

Stage 3: Atomic Pointer Flip

The writer issues one atomic operation: xchg(&global_ptr, new_version). This is a single atomic; all readers that call READ_ONCE(global_ptr) after this flip will see the new version. Readers that called READ_ONCE() before the flip still hold the old pointer and keep reading the old data.

This is the critical moment. New readers instantly see the new data. Old readers are frozen on the old pointer—they won’t hit the new version, even if the new version changes again. Their read is stable.

Stage 4: Grace Period and Reclamation

Here’s the puzzle: how do we know when to free the old version?

A reader might have called READ_ONCE() just before the flip, acquired the old pointer, and is now mid-read. If we free the old version immediately, that reader crashes with a use-after-free. We must wait until every reader on the old version is gone.

This is where the grace period comes in. RCU enforces a synchronization point on every CPU: the quiescent state. A CPU reaches a quiescent state when:

• It context switches away from user space or kernel code (proving any in-flight read is done).
• It explicitly calls rcu_read_unlock() (leaving an RCU read-side critical section).

A grace period is defined as: a span of time during which every CPU has passed through at least one quiescent state. Once the grace period ends, we have proof that no reader can still hold a reference to the old version. Now it’s safe to free.

On a 64-core machine, the grace period typically takes 10–100 milliseconds, depending on CPU activity and tick rates. Batch the updates—free 1,000 old versions in one grace period, not one per update—and the reclamation cost amortizes away.

Why This Scales

Traditional locks scale as O(1) in throughput as cores climb, hitting a ceiling due to contention. RCU reads scale as O(N)—linear in core count. On a 64-core machine:

• rwlock: ~20–30 million reads/sec (contention plateau)
• RCU: ~800 million reads/sec (linear scaling)

This is because RCU reads have zero shared cache line traffic. Each core reads a local copy of the pointer and the data. The atomic operations (if any) are infrequent and batched on the write side.

Trade-Offs and When NOT to Use RCU

RCU is not a universal lock replacement. It shines in specific scenarios:

• Read-heavy workloads (reads > 100x writes): routing tables, firewall rules, TCP connection lookup.
• Small data structures or infrequent mutations: a config map reloaded once per hour.
• Latency-sensitive readers: network packet forwarding, scheduler, memory allocator.

RCU is poor for:

• Write-heavy workloads: if writers contend, RCU offers no benefit. Use mutexes or optimistic locking.
• Writers that need immediate consistency: RCU readers see stale data during a grace period. If a config change must apply to all readers instantly, RCU delays visibility by a grace period.
• Unbounded grace periods: in systems with real-time constraints, waiting for all CPUs to quiesce may be unacceptable.

The Kernel’s Bet

The Linux kernel made RCU central to its read path: file path lookup (d_seq), scheduler rbtree iteration, IP routing, and netfilter rules all use RCU. The payoff: millions of reads per second with near-zero contention, enabling kernel throughput to scale with core count rather than flatline at a lock.

The downside: RCU is hard to reason about. Use-after-free is a silent risk if a reader escapes a grace period. The kernel mitigates this with srcu_read_lock() (for longer critical sections) and rcu_dereference() macros to enforce annotations.

For most applications, RCU is overkill. Use it when you’ve measured that lock contention on reads is your bottleneck, and your workload is read-heavy and update-infrequent. When you do, the scaling win is worth the complexity.

Summary

RCU is a synchronization primitive that trades write-side complexity for read-side freedom. Readers run lock-free and scale linearly; writers copy, mutate, flip a pointer, and wait for a grace period before reclaiming the old version. The grace period—waiting for all CPUs to quiesce—is the crux: it proves that no reader can still hold the old data.

The kernel ships RCU because the win is enormous: routing tables, config, and other hot read paths scale from single-core saturation to linear scaling across tens or hundreds of cores. For the right workload, RCU is unbeatable.