How RCU Works: Grace Periods, Quiescent States, and Why Readers Skip Locks

A shared linked list in the kernel can be walked by thousands of cores at once. A writer still has to insert or delete a node. If every walker took a lock, the list would become a single-core structure with extra cache-line ping-pong. If the writer freed a node while a walker still held a pointer into it, the next load would be use-after-free.

Read-copy-update (RCU) is the Linux kernel's answer for read-mostly data. Readers do not take a lock. Writers publish a new version of a pointer and wait until every reader that could have seen the old version has finished. Only then is the old memory reclaimed. The wait is called a grace period. The events that prove a CPU is not inside an RCU read-side critical section are quiescent states.

This article is about that contract: publish-subscribe pointers, grace periods, Tree RCU's per-CPU reporting, and why the read side can be free on a server kernel. It is not a second tour of the scheduler, system-call entry, or CPU cache lines. CFS decides which task runs. System calls cross privilege. Caches move 64-byte lines. RCU decides when it is legal to free an object that concurrent readers might still be looking at.

For context, CFS decides which task runs through vruntime and its scheduling tree, while system calls explain the user-mode to kernel boundary. It is also not MVCC. A database snapshot keeps old row versions for a transaction's visibility rules. RCU keeps an old object alive only until in-flight kernel readers drop it. There is no snapshot ID and no transaction. MVCC uses snapshots and version chains for a different purpose.

The split: removal is not reclamation

An RCU update has two phases that must not collapse into one.

1. Removal (or replacement). Unlink the old object from the structure, or swing a global pointer to a newly allocated copy. After this store is visible, new readers see the new version. Old readers may still hold the previous pointer in a register.
2. Reclamation. Free the old object. This is legal only after every pre-existing reader has left its RCU read-side critical section.

The gap between those phases is the grace period. New readers that start after the pointer swing are irrelevant. They cannot observe the old object through the published pointer, so the grace period does not wait for them.

That is the whole trick. Track generations of readers without giving each reader a lock, a ticket, or a reference count on the hot path.

What a reader is allowed to do

A classic RCU reader looks like this:

rcu_read_lock();
p = rcu_dereference(global_ptr);
if (p)
    use(p->field);
rcu_read_unlock();

rcu_read_lock() and rcu_read_unlock() delimit the critical section. On a non-preemptible kernel they can compile to almost nothing: they mark a region in which the task must not block, sleep, or voluntarily schedule. Because the reader cannot schedule, a context switch on that CPU is proof that the critical section has ended.

rcu_dereference() is not a cast. It loads the pointer with READ_ONCE and a compiler barrier so the compiler cannot reload the pointer later, tear it, or hoist the dereference before the load. On most architectures the CPU's address dependency already orders later loads through that pointer. Alpha needed an explicit memory barrier; the API exists so driver authors do not have to remember which chip is special.

Readers may not block inside the section (vanilla RCU). They may not free the object. They may write fields of the object only if some other rule serializes those writes. RCU protects the lifetime of the pointer graph, not arbitrary mutation of every byte.

What a writer must publish

The matching store is rcu_assign_pointer(global_ptr, new). The macro is a release-store. Every initialization of new is required to become visible before the pointer itself becomes visible. Without that, a reader could load the new address and then observe uninitialized fields, a classic weak-memory bug that lock-free code hits on ARM and POWER even when x86 happens to hide it.

A typical replacement:

old = global_ptr;
new = kmalloc(...);
*new = *old;
new->field = updated;
rcu_assign_pointer(global_ptr, new);
synchronize_rcu();
kfree(old);

synchronize_rcu() blocks the writer until a grace period ends. call_rcu(&old->rh, free_cb) instead queues a callback that runs after the grace period, so the writer can continue. Lists use the same publish rule through helpers such as list_add_rcu, list_del_rcu, and list_for_each_entry_rcu. The list walk is a reader. The delete is removal. The later kfree is reclamation.

Writers still need mutual exclusion against other writers. RCU does not replace the writer lock. It removes the need for readers to take that lock.

Grace periods and quiescent states

A quiescent state is a point where a CPU (or, in preemptible RCU, a task) cannot be inside an RCU read-side critical section.

For non-preemptible vanilla RCU, the classic quiescent states are:

• a context switch
• execution in the idle loop
• execution in user mode
• the CPU going offline

If every CPU has passed through at least one of those after the pointer was published, every read-side section that existed at publish time has ended. The old object has no remaining legal readers. Reclamation is safe.

The definition is per pre-existing reader, not per future reader. A core that stays in a long read-side section delays the grace period. A core that is already in user space can report a quiescent state immediately.

Preemptible RCU, used by realtime and most desktop CONFIG_PREEMPT kernels, changes the proof. A reader can be preempted inside rcu_read_lock. A context switch is then no longer automatic proof for that task. The implementation tracks blocked readers on a per-rcu_node list and waits for those tasks to exit the section as well.

How Tree RCU scales the wait

A naive implementation would scan every CPU on every grace period. That scan itself would not scale.

Tree RCU places CPUs at the leaves of a combining tree of rcu_node structures. Each CPU reports a quiescent state upward. An interior node completes when all children have reported. The root completion ends the grace period and starts callback invocation. Force-quiescent-state passes exist for CPUs that go quiet without reporting: idle, nohz, and offline races.

The tree also carries the memory-ordering burden. Taking an rcu_node lock on the way up and down pairs with the read-side critical sections so that, after the grace period ends, the reclaimer is guaranteed to see every store those old readers could have done, and old readers are guaranteed to have seen the removal. The guarantee is stronger than “the pointer looks new.” It is a full happens-before between pre-existing readers and post-GP reclaim.

Expedited grace periods take a different path. They IPI CPUs that have not yet reported and ask them to report sooner. That is faster for the updater and ruder to idle cores, which is why battery-sensitive and nohz-full machines care about the distinction. Lazy call_rcu on modern kernels can delay starting a grace period for callbacks that are only freeing memory, to avoid waking idle CPUs for a handful of kfrees.

Cache-line movement is part of the same scaling story; the CPU-cache model explains why shared hot words create coherence traffic.

Flavors exist because the read-side rules differ

The kernel does not have one RCU. It has flavors that change what counts as a quiescent state.

• Vanilla / Tree RCU: the default. Read side is rcu_read_lock. Sleeping is forbidden.
• SRCU (sleepable RCU): readers may block. The read side uses a per-domain counter pair, so the grace period waits on those counters instead of context switches. It is heavier for readers and necessary when a path might call schedule or wait on I/O while still holding a published pointer.
• RCU-bh / RCU-sched: older specialized flavors. Since v5.0, vanilla grace periods also wait for local_bh_disable regions; much of the old split collapsed.
• Tasks RCU: a voluntary context switch is the quiescent state. Used to retire ftrace and kprobe trampolines that a task might still be executing, even though those trampolines never take rcu_read_lock.
• Tasks Trace RCU: for sleepable BPF programs attached where trampoline lifetime must be synchronized. It is related to eBPF attachment and teardown, not the verifier's safety proof.

Picking the wrong flavor is a real bug class. Using vanilla RCU around a call that sleeps is illegal. Using SRCU on a cache-hot packet path pays an atomic increment you did not need.

Worked sequence

Four CPUs. global_ptr refers to object A.

• CPU 0 is inside rcu_read_lock; its register holds A.
• CPU 1 publishes B with rcu_assign_pointer and calls synchronize_rcu.
• CPU 2 enters a new read-side section and loads B. It does not delay the grace period.
• CPU 3 is in user mode: that is already a quiescent state.
• CPU 1 cannot free A yet. CPU 0 still has A.
• CPU 0 later hits rcu_read_unlock and then a timer tick schedules another task. That context switch is a quiescent state for CPU 0.
• Once every leaf has reported, the root ends the grace period. synchronize_rcu on CPU 1 returns. kfree(A) is legal.

If CPU 0 had been spinning in a long critical section, the writer would wait. That is the latency trade: readers stay off the lock, while writers absorb delay and extra memory until the last old reader leaves.

Why locks do not scale the same way

A reader-writer lock still writes a shared word on the read path, or at least bounces a cache line when the last reader drops and a writer arrives. Under MESI, that line moves. On a many-core box, a popular list walked on every packet or every system call becomes a coherency hot spot even if the lock is held for tens of cycles.

RCU's common-case read path does not write shared cache lines. On CONFIG_PREEMPT=n server builds, rcu_read_lock can be empty of atomics. The cost moves to the writer: allocation of a new version, a release-store, and a grace period that may take milliseconds. That is a good trade when updates are rare and reads are the workload. It is a bad trade when updates are frequent enough that you run out of memory waiting for grace periods, or when the updater is on a latency budget that synchronize_rcu cannot meet. In those cases you want a different structure, a bounded hazard-pointer scheme, or an expedited GP with eyes open about IPIs.

Reference counts are the right tool when an object has a user-visible lifetime, such as a file or socket. They are the wrong tool when the hot path is “look up and copy three fields” and you would increment and decrement a cache-hot counter millions of times a second.

Misconceptions

• “RCU is lock-free for everyone.” Writers usually still take a mutex or spinlock against each other. Readers are lock-free. The update side is not a free-for-all.
• “synchronize_rcu waits for all future readers.” It waits only for readers already in a critical section at the start of the grace period.
• “I can free in the same function that did list_del.” Not without a grace period between those lines. list_del_rcu plus immediate kfree is a use-after-free under concurrency.
• “Quiescent state means the CPU is idle.” Idle is one quiescent state. User mode and context switch are others.
• “RCU replaces MVCC.” MVCC answers which row version a query may see. RCU answers when an unlinked kernel object may be freed. Different software, different invariants.
• “The read side is always zero cost.” On preemptible kernels, rcu_read_lock adjusts preempt state. SRCU increments a counter. Wrong flavor, wrong bill.

Where this sits next to other machinery

The scheduler's context switch is a quiescent-state source for vanilla RCU. That is a coupling, not an equivalence: CFS still picks who runs; RCU only observes that a pick happened.

A blocking system call is a quiescent state for the CPU that left the kernel, once the task is no longer in an RCU section. The call itself is not an RCU operation.

eBPF programs that sleep need Tasks Trace RCU (or SRCU, depending on the attach point) so a program being unloaded cannot vanish under a running trampoline. The verifier does not implement grace periods; the attachment lifetime does. The eBPF verifier, maps, and JIT cover the program side of that system.

Takeaways

RCU splits update into a visible pointer swing and a later free. Readers subscribe to the current pointer without writing a shared lock word. The kernel proves it is safe to reclaim by waiting until every CPU—and, when preemption is on, every preempted reader—has passed through a state that cannot still hold the old pointer. Tree RCU makes that wait scale. Flavors change what the wait means. Use it when reads dominate and a few milliseconds of deferred free are acceptable. Use a lock, a refcount, or SRCU when the read path must sleep or the object lifetime is part of a user-visible API.

When a kernel oops points at a freed RCU object, look at whether the free sat after a real grace period, whether the load used rcu_dereference, and whether the read side used the same flavor the updater waited on.