Read-Copy-Update (RCU) in the Linux Kernel
Read-Copy-Update (RCU) in the Linux Kernel
A routing table, a process’s credentials, a file descriptor table, a network device alias, and the dentry cache share one access pattern: many contexts follow pointers into them, while relatively few contexts replace an entry. A reader-writer lock makes every reader touch a shared lock word. A seqlock makes every reader validate a sequence number and retry if a writer interfered. RCU takes a third path: readers walk the structure without acquiring anything and without retrying, and writers publish a new version immediately. The price is paid later, by the writer, as a grace period before the old version can be freed.
That sentence is the whole design. RCU is not a lock in the usual sense: there is no rcu_write_lock(), because writers do not exclude readers. Nor does RCU protect arbitrary fields. It protects the **lifetime** of objects reachable through pointers. A reader sees either the old object or the new one, and the old object stays allocated until every reader that could still hold it has left its read-side critical section. The writer must publish and remove in the right order so that no reader observes a half-initialized object or a dangling pointer. On AArch64 that order is enforced by release stores, dependency-ordered loads, and full barriers around grace-period transitions.
This document describes RCU in Linux v7.3-rc7 on AArch64. It develops the protocol from first principles, then covers Tree RCU, reclamation, SRCU, Tiny RCU, the bh/sched variants, and the list primitives built on top. Unless stated otherwise, it assumes a non-PREEMPT_RT AArch64 SMP kernel using Tree RCU; PREEMPT_RCU, PREEMPT_RT, and SRCU are treated separately because they change the rules for sleeping and reader tracking.
Diagram conventions. Timelines run top to bottom. Side-by-side columns are concurrent CPUs or tasks, not a strict wall-clock order. GP means grace period, QS means quiescent state, and versions are v0, v1, and so on.
Table of Contents
- Why Seqlocks Are Not Enough
- The Core Idea and Terminology
- Read-Side Critical Sections
- Publication and Memory Ordering on AArch64
- Grace Periods and Quiescent States
- Tree RCU Internals
- The Write Side: Removal and Reclamation
- RCU-Protected Lists
- A Complete Multi-Kthread Example
- Contexts, Nesting, and Sleeping
- 10.1 Nesting Rules
- 10.2 Non-Preemptible RCU
- 10.3 PREEMPT_RCU
- 10.4 Interrupts, Softirqs, and NMI
- 10.5 Can a Reader Sleep?
- 10.6 Context Selection Matrix
- Sleepable RCU (SRCU)
- 11.1 Why SRCU Exists
- 11.2 Data Structures
- 11.3 Read Side
- 11.4 Grace Period and Index Flip
- 11.5 API, Rules, and Costs
- Tiny RCU and the Flavors
- 12.1 Tiny RCU
- 12.2 Tree RCU
- 12.3 Production Choice
- 12.4 RCU-bh and RCU-sched
- 12.5 Tasks RCU and Other Flavors
- 12.6 Flavor Selection at a Glance
- Real-World Users
- 13.1 Credentials
- 13.2 PIDs
- 13.3 File Descriptor Tables
- 13.4 Network Device Names and Aliases
- 13.5 VFS and Networking at Large
- Performance and Scalability
- Limitations and Comparison with Seqlocks
- 15.1 Fundamental Limitations
- 15.2 Seqlock vs. RCU
- 15.3 Decision Matrix
- 15.4 Important Rules
- 15.5 Sharp Edges at a Glance
- References
1. Why Seqlocks Are Not Enough
1.1 The Reader’s Retry Tax
A seqlock is optimistic concurrency control. The writer bumps a sequence counter before and after an update; the reader samples the counter, copies the data, and validates:
1
2
3
4
do {
seq = read_seqbegin(&lock);
copy = shared_value; /* possibly several fields */
} while (read_seqretry(&lock, seq));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
┌─▶ seq = read_seqbegin()
│ │
│ ▼
│ copy the data (every field the reader needs)
│ │
│ ▼
│ read_seqretry(&lock, seq) ──▶ changed ──┐
│ │ │
│ stable │
│ │ │
│ ▼ │
│ use the copy │
│ │
└───────────────────────────────────────────┘
the back edge is taken once per writer update that overlaps the copy,
so reader latency follows the writer's update rate, not the reader's
own work; every retry also repeats any side effect that must be undone
The writer never waits, which is the attractive part. The loop is the cost. Under a sustained write stream a reader can fail repeatedly, and every retry repeats its work and any side effect that must then be undone. Reader latency is therefore unbounded even though writer latency is not. A seqlock is excellent for small, cheap-to-copy values such as jiffies_64, timekeeping state, and generation counters. It is not a general solution for pointer-based structures.
1.2 Pointers, Lifetimes, and the Copy-Out Rule
The deeper problem appears when the data contains pointers. Suppose a reader loads head->next and follows it while a writer removes and frees that node. The seqlock can report that the sequence changed, but it cannot resurrect freed memory. Validation after the fact is too late: the reader has already dereferenced a dangling pointer, and retrying cannot undo the fault.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
before: head ──▶ [ A ] ──▶ [ B ] ──▶ [ C ] ──▶ NULL
│
│ 1 reader saves "C" from B->next
│ and is preempted
▼
writer: unlink(B) ──▶ head ──▶ [ A ] ──▶ [ C ] ──▶ NULL
kfree(B) ──▶ [ B ] back in the allocator, possibly reused
│
│ 2 reader resumes and follows the
▼ pointer it saved in step 1
reader: load C->value ──▶ fault, or another owner's data
the sequence check runs after the dereference, so it can
report the change but cannot make the dereference legal
The usual rule is therefore blunt: do not follow unprotected pointers inside a seqlock read-side section. Copy scalars out and validate them; do not copy a pointer and use it after the check. That rule excludes routing tables, credential pointers, file descriptor tables, and linked lists of device names — all structures whose readers want to traverse pointers and need the target to stay alive.
A reader-writer lock solves the lifetime problem by excluding writers, but it reintroduces the shared lock word and the writer’s wait for the last reader. A reference count protects one object, but taking and dropping a reference is itself a shared-memory operation, and the reader still needs a safe way to find the object. RCU fills that gap: it gives the reader a stable pointer whose target stays alive through the read-side critical section, without any shared lock write.
1.3 What RCU Changes
RCU changes the question from “is the data stable?” to “is this object still alive?” The writer does not modify the published object in place. It creates a new version, initializes it completely, and replaces the pointer with an atomic publication operation. A reader that loaded the old pointer keeps using the old object; a reader that loads the new pointer sees the new object. The old object is not freed until a grace period proves that every reader that could have observed it has finished.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
seqlock / mutex — the writer edits the live object
──────────────────────────────────────────────────
┌──────────────────┐
readers ────▶│ a=1 b=1 │◀── writer: a=2, then b=2
│ │ a reader between the two
│ reader sees │ stores sees a=2, b=1
│ a=2, b=1 ✗ │
└──────────────────┘
RCU — the writer builds v1, then flips the pointer
──────────────────────────────────────────────────
┌──────────────────┐ ┌──────────────────┐
readers ────▶│ v0: a=1 b=1 │ │ v1: a=2 b=2 │
(old) └──────────────────┘ └──────────────────┘
▲ ▲
│ │
existing readers rcu_assign_pointer()
keep using v0 makes v1 reachable;
later readers get v1
│
└── v0 freed only after a grace period
| Property | Sequential lock | RCU |
|---|---|---|
| Reader validates a sequence number | Yes | No |
| Reader can be forced to retry | Yes | No |
| Writer modifies data in place | Yes, under the sequence protocol | No, for objects readers traverse |
| Reader can safely follow pointers | No, unless lifetime is protected separately | Yes, within the read-side section |
| Reader can perform side effects | Only if they can be undone | Yes, subject to context rules |
| Writer waits before making the new value visible | No | No |
| Writer waits before freeing the old value | Not applicable | Yes, for a grace period |
| Reader sees a consistent multi-field snapshot | Yes, after successful validation | Not automatically; objects must be immutable or separately synchronized |
| Memory cost | One copy | Old and new versions may coexist until the grace period ends |
The last row is the common source of confusion. RCU does not promise a coherent snapshot of a structure that a writer is changing field by field. It promises a valid object with a stable identity. If several fields must change together, the writer publishes a new object containing all the new values, or uses a seqlock. The two primitives are complementary, not interchangeable.
2. The Core Idea and Terminology
2.1 Readers, Updaters, and Reclaimers
RCU divides the world into three roles:
- A reader runs an RCU read-side critical section delimited by
rcu_read_lock()andrcu_read_unlock(), or by an equivalent implicit region. It may dereference RCU-protected pointers and use the objects it finds. - An updater (or writer) changes the published structure. It serializes with other updaters using an ordinary lock or another mechanism, prepares a new version, and publishes it.
- A reclaimer frees the old version after the grace period. It is often an RCU callback, sometimes the updater itself after
synchronize_rcu()returns.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
┌───────────────┐ ┌───────────────┐
│ updater │ │ reader │
└───────┬───────┘ └───────┬───────┘
│ 1 allocate + initialize v1 │ rcu_read_lock()
│ 2 rcu_assign_pointer(&p, v1) │ rcu_dereference(p)
▼ ▼
┌──────────────────────────────────────────────────────────────┐
│ p ──▶ v1 complete before it becomes reachable │
│ v0: unlinked, still allocated for readers already inside │
└───────────────┬──────────────────────────────────────────────┘
│ 3 synchronize_rcu() or call_rcu(callback)
▼
┌───────────────┐
│ grace period │◀── a reader still in a section that
└───────┬───────┘ began before the removal holds it open
│ 4 GP ended: no reader can still hold v0
▼
┌───────────────┐
│ reclaimer │ kfree(v0) — or the queued callback runs
└───────────────┘
Updater and reclaimer may be the same task; they are conceptually separate because removal and freeing happen at different times, with a grace period in between. The central invariant is:
Once an object has been removed from every RCU-protected path a reader can traverse, it may not be freed until a grace period that began after the removal has elapsed.
That invariant is what lets a reader use a pointer without a reference count. The reader only has to stay inside its read-side section. The writer proves the other half: remove first, wait for all readers that could have been using the object, then free.
2.2 Grace Periods and Quiescent States
A grace period is an interval during which every CPU and task that was in an RCU read-side critical section at the start of the interval has exited it. A quiescent state is a point at which a CPU or task is known not to be inside such a section. The grace period ends when all CPUs and tasks that were readers at its start have passed through a quiescent state.
The grace period is one interval shared by every CPU: a single t0, a single t1, and every caller waiting on it returns when it ends. What is per-CPU is the evidence. Each CPU passes through its own quiescent states, at its own times, by its own mechanism, and a report from one CPU credits only that CPU. The interval is therefore a global barrier assembled from per-CPU reports: it cannot end until every CPU that was a reader at t0 has produced one of its own.
The definitions are operational. RCU does not track objects or pointers; it only needs to know whether a CPU or task can still be a reader. A context switch, a return to user mode, an idle transition, and a CPU going offline can all establish a quiescent state. The kernel combines these events into a distributed state machine.
A grace period is not a fixed timeout. It can complete in microseconds on an idle system and can be delayed by a long read-side section, a preempted reader, or a CPU that is not responding. The kernel emits stall warnings when it takes too long, because a stuck reader usually indicates a bug.
1
2
3
4
5
6
7
8
9
10
11
12
13
t0 t1
│◀──── one grace period, all CPUs ─▶│
│ │
CPU0 ── R ──────────┤ QS (context switch) ──────────────┤
│ │
CPU1 ──────── R ────┤──── R continues ────┴ QS (user) ──┤
│ │
CPU2 ┄┄┄ idle: EQS ┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄│
│ quiescent for its whole span; no report needed
CPU3 ── QS ── R ────┤───── R continues ───────┤ QS ─────┤
✗ too early │ this QS is before t0, so it does not count
└── one interval for every CPU; each CPU supplies
its own quiescent state, at its own time
2.3 The Removal and Reclamation Split
An update has two phases. Removal unlinks the old data or replaces the pointer; it may overlap readers because the old object is still allocated. Reclamation frees the old data, but only after a grace period that began after removal.
1
2
3
4
5
6
7
8
time ─────────────────────────────────────────────────────────────▶
writer allocate v1 ─ init v1 ─ publish v1 ─ unlink v0 ─ wait GP ─ free v0
│ │ │ │ │ │
▼ ▼ ▼ ▼ ▼ ▼
readers ── R0 (v0) ─────────────────────────────────────┤
└── R1 (v0) ────────────────────────────────────┤
R2 (v1) ────────────────────────────────────────────▶
In the figure, R0 and R1 loaded v0 and are waited for; R2 started after publication and is not. The pointer update is atomic and the old object is still allocated, so a reader either obtained the old pointer before the update or the new pointer after it. It cannot obtain a partially overwritten object if the writer follows the publication rules. Reclamation must not overlap readers that could still hold the old pointer, which is exactly what the grace period guarantees.
The sequence is:
- Remove pointers to the data, so later readers cannot gain a reference.
- Wait for all previous readers to finish their read-side sections.
- Free the data; no reader can still hold a reference.
See Documentation/RCU/whatisRCU.rst.
2.4 Why Readers Never Retry
A seqlock reader retries because the writer may modify the data underneath it. An RCU reader does not retry because the writer never modifies the object the reader is using. The writer creates a new object, publishes it, and leaves the old object untouched until the reader is done. The reader’s view is always a complete version, even if it is no longer current.
1
2
3
4
5
6
7
8
9
10
11
12
13
seqlock reader:
read seq ──▶ copy data ──▶ check seq ──┬── stable ──▶ use copy
│
└── changed ──▶ discard
│
◀────────────────────────────────────────────┘
retry from the beginning
RCU reader:
rcu_read_lock ──▶ load pointer ──▶ use object ──▶ rcu_read_unlock
│
├── old version: still allocated until the GP ends
└── new version: fully initialized before publication
The seqlock path has a back edge; the RCU path does not. That structural difference is why an RCU reader’s latency is bounded by its own work rather than by the writer’s update rate.
The RCU reader may see stale data. In exchange it gets a bounded, non-blocking read path. A writer that requires readers to see the new value immediately must use another mechanism, or accept that RCU readers can lag. The no-retry property also depends on writer discipline: freeing early causes a fault, and mutating in place causes a torn read. Safety comes from the protocol, not from a hardware check.
2.5 Terminology at a Glance
| Term | Meaning |
|---|---|
| RCU read-side critical section | Code between rcu_read_lock() and rcu_read_unlock(), or an equivalent implicit reader region. |
| Grace period (GP) | Interval after a removal during which all pre-existing readers are guaranteed to finish. |
| Quiescent state (QS) | A point at which a CPU or task is known not to be in an RCU read-side section. |
| Extended quiescent state (EQS) | A long-lived quiescent state, such as dynticks-idle or user mode, tracked by context tracking. |
| Updater / writer | Code that changes an RCU-protected structure. |
| Reclaimer | Code that frees an old version after the grace period. |
| Callback | A function queued with call_rcu() and invoked after a grace period. |
| Publication | Making a fully initialized object reachable with rcu_assign_pointer(). |
| Removal | Unlinking or replacing the published pointer. |
| Expedited GP | A grace period that uses IPIs and other aggressive mechanisms to finish quickly. |
| SRCU | Sleepable RCU, a separate domain whose readers may block. |
| NOCB | Callback offloading, where per-CPU callbacks are invoked by dedicated kthreads. |
3. Read-Side Critical Sections
3.1 rcu_read_lock() and rcu_read_unlock()
The public reader API is intentionally tiny:
1
2
3
4
5
rcu_read_lock();
p = rcu_dereference(gp);
if (p)
use(p);
rcu_read_unlock();
rcu_read_lock() does not acquire a lock in the mutual-exclusion sense. It marks the current context as an RCU reader and prevents the current CPU or task from being considered quiescent for the duration. The implementation depends on the RCU configuration.
In a non-preemptible RCU build (!CONFIG_PREEMPT_RCU), the inner primitive is simply preempt_disable():
1
2
3
4
5
6
7
8
9
10
11
static inline void __rcu_read_lock(void)
{
preempt_disable();
}
static inline void __rcu_read_unlock(void)
{
if (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD))
rcu_read_unlock_strict();
preempt_enable();
}
See include/linux/rcupdate.h. Preemption is disabled, so the task cannot be scheduled out in the middle of the read-side section. A context switch therefore cannot happen inside the section, which makes the CPU’s own quiescent-state tracking sufficient: when the CPU eventually reports a context switch or a return to user mode, no reader can still be active on that CPU.
In a preemptible RCU build (CONFIG_PREEMPT_RCU), the reader is tracked per task instead:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void __rcu_read_lock(void)
{
rcu_preempt_read_enter();
if (IS_ENABLED(CONFIG_PROVE_LOCKING))
WARN_ON_ONCE(rcu_preempt_depth() > RCU_NEST_PMAX);
if (IS_ENABLED(CONFIG_RCU_STRICT_GRACE_PERIOD) && rcu_state.gp_kthread)
WRITE_ONCE(current->rcu_read_unlock_special.b.need_qs, true);
barrier(); /* critical section after entry code. */
}
void __rcu_read_unlock(void)
{
struct task_struct *t = current;
barrier(); /* critical section before exit code. */
if (rcu_preempt_read_exit() == 0) {
barrier(); /* critical-section exit before .s check. */
if (unlikely(READ_ONCE(t->rcu_read_unlock_special.s)))
rcu_read_unlock_special(t);
}
if (IS_ENABLED(CONFIG_PROVE_LOCKING)) {
int rrln = rcu_preempt_depth();
WARN_ON_ONCE(rrln < 0 || rrln > RCU_NEST_PMAX);
}
}
See kernel/rcu/tree_plugin.h. The fast path is a per-task increment and decrement, with compiler barriers around the critical section. There is no atomic read-modify-write and no shared cache line in the common case. If the task is preempted while inside the section, rcu_note_context_switch() notices the non-zero nesting depth and queues the task on the leaf rcu_node’s blocked-task list, so the grace period knows that this task must be waited for.
The outer wrappers add lockdep and context tracking:
1
2
3
4
5
6
7
8
static __always_inline void rcu_read_lock(void)
{
__rcu_read_lock();
__acquire_shared(RCU);
rcu_lock_acquire(&rcu_lock_map);
RCU_LOCKDEP_WARN(!rcu_is_watching(),
"rcu_read_lock() used illegally while idle");
}
and the matching unlock validates the context before dropping the reader state. See include/linux/rcupdate.h and include/linux/rcupdate.h. The rcu_is_watching() check is important: entering an RCU read-side section from an extended quiescent state such as the idle loop is a bug, because RCU is not watching that CPU and cannot guarantee that a grace period will wait for it.
The bh and sched variants are convenience wrappers that also disable the corresponding context:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static inline void rcu_read_lock_bh(void)
{
local_bh_disable();
__acquire_shared(RCU);
__acquire_shared(RCU_BH);
rcu_lock_acquire(&rcu_bh_lock_map);
RCU_LOCKDEP_WARN(!rcu_is_watching(),
"rcu_read_lock_bh() used illegally while idle");
}
static inline void rcu_read_lock_sched(void)
{
preempt_disable();
__acquire_shared(RCU);
__acquire_shared(RCU_SCHED);
rcu_lock_acquire(&rcu_sched_lock_map);
RCU_LOCKDEP_WARN(!rcu_is_watching(),
"rcu_read_lock_sched() used illegally while idle");
}
See include/linux/rcupdate.h and include/linux/rcupdate.h. In v7.3-rc7 these are not separate grace-period flavors; they are reader-context annotations on top of the unified vanilla RCU grace period. That distinction is covered in Section 12.4.
3.2 The Four Reader Contexts
It helps to separate four situations in which a context can be an RCU reader:
- Explicit RCU reader. The code calls
rcu_read_lock()andrcu_read_unlock(). This is the normal case for pointer-based data structures. - Preemption-disabled region. In non-preemptible kernels,
preempt_disable()itself is a reader region. In preemptible kernels, the kernel still treats preemption-disabled regions as readers for the unified grace period, because a task in such a region cannot be preempted and therefore cannot pass through a quiescent state. This is whyrcu_read_lock_sched()is meaningful. - Interrupt-disabled or NMI region. A hardirq handler or NMI handler runs with preemption disabled and is treated as a reader. The kernel does not need an explicit
rcu_read_lock()for the interrupt handler’s stack frame to be protected, although code that follows pointers should still use the appropriatercu_dereference()variant. - Softirq-disabled region.
local_bh_disable()keeps softirqs from running and is treated as a reader for the unified grace period.rcu_read_lock_bh()is the explicit form, but anylocal_bh_disable()region has the same effect for RCU.
This is why the modern kernel can say that “anything that disables preemption, interrupts, or bottom halves is an RCU read-side critical section.” The statement is a consequence of the grace-period implementation, not a separate API contract. It also explains why synchronize_rcu() waits for more than just explicit rcu_read_lock() sections.
A useful mental model is:
1
2
3
4
5
explicit rcu_read_lock() ─┐
preempt_disable() ├──► contexts the grace period must wait for
local_irq_disable() │
local_bh_disable() │
hardirq / NMI entry ┘
The implementation collapses these into the same grace-period tracking. The bh and sched APIs remain useful for documentation, lockdep, and reader-specific dereference checks.
3.3 rcu_dereference() and Friends
The pointer accessors are where the RCU protocol becomes visible in C. The basic reader-side primitive is:
1
#define rcu_dereference(p) rcu_dereference_check(p, 0)
which expands through __rcu_dereference_check() to a READ_ONCE() of the pointer, followed by lockdep validation:
1
2
3
4
5
6
7
8
#define __rcu_dereference_check(p, local, c, space) \
({ \
/* Dependency order vs. p above. */ \
typeof(*p) *local = (typeof(*p) *__force)READ_ONCE(p); \
RCU_LOCKDEP_WARN(!(c), "suspicious rcu_dereference_check() usage"); \
rcu_check_sparse(p, space); \
((typeof(*p) __force __kernel *)(local)); \
})
See include/linux/rcupdate.h, include/linux/rcupdate.h, and include/linux/rcupdate.h.
The family has several members, each with a different purpose:
| Primitive | Use |
|---|---|
rcu_dereference(p) | Normal reader-side load of an RCU-protected pointer. |
rcu_dereference_check(p, c) | Reader-side load with an additional lockdep condition. |
rcu_dereference_protected(p, c) | Update-side load when a lock prevents concurrent replacement; no READ_ONCE(). |
rcu_access_pointer(p) | Load the pointer value without dereferencing it; omits the read-side lockdep check. |
rcu_dereference_raw(p) | Load without lockdep checking, for special low-level code. |
rcu_dereference_bh(p) | bh flavor with the corresponding lockdep check. |
rcu_dereference_sched(p) | sched flavor with the corresponding lockdep check. |
srcu_dereference(p, ssp) | Load a pointer protected by a specific SRCU domain. |
rcu_access_pointer() is for comparisons and NULL tests where the pointer is not dereferenced. rcu_dereference_protected() is for the update side, where the writer already holds the lock that serializes replacements. Using rcu_dereference_protected() on the read side is a bug: it deliberately omits READ_ONCE() and the dependency-preserving machinery.
The reader must use one of these primitives rather than reading the pointer directly. A plain C load can be reloaded, folded, or combined by the compiler, and on a weakly ordered CPU it may not preserve the dependency between the pointer load and the subsequent dereference. The Linux documentation is explicit that the returned pointer carries an address or data dependency, and that the compiler must not be allowed to break it. See Documentation/RCU/rcu_dereference.rst.
3.4 Reading an Object
A typical reader does three things: enter, fetch the pointer, and use the object while still inside the section.
1
2
3
4
5
6
7
8
9
10
struct config *cfg;
u64 version;
rcu_read_lock();
cfg = rcu_dereference(global_cfg);
if (cfg) {
version = READ_ONCE(cfg->version);
do_something(cfg->payload, cfg->payload_len);
}
rcu_read_unlock();
The important rules are:
- The pointer must be fetched with
rcu_dereference()(or a variant) inside the read-side section. - The object must not be used after
rcu_read_unlock(). Once the section ends, the object may be reclaimed at any time. - The object’s fields must be treated as immutable for the duration of the section. If the writer mutates a field in place, RCU provides no snapshot guarantee.
- If the reader needs to keep the object after the section, it must acquire a reference count or copy the data while still inside the section.
- The reader should not sleep in a classic RCU section. Section 10.5 covers the exact rules for PREEMPT_RCU and SRCU.
A common pattern is to combine RCU with a reference count:
1
2
3
4
5
6
7
8
9
10
11
rcu_read_lock();
p = rcu_dereference(global_obj);
if (p && !refcount_inc_not_zero(&p->ref))
p = NULL;
rcu_read_unlock();
if (p) {
/* p is now pinned by the reference count */
use_after_rcu(p);
refcount_dec_and_test(&p->ref);
}
The RCU section protects the lookup and the reference acquisition. The reference count protects the object after the RCU section ends. This is the standard “RCU lookup plus refcount” pattern used by the VFS, the PID code, and many other subsystems.
3.5 Nesting
RCU read-side critical sections may be nested. The same task can call rcu_read_lock() several times before the matching unlocks:
1
2
3
4
5
6
7
8
9
10
rcu_read_lock();
p = rcu_dereference(global_a);
if (p) {
rcu_read_lock();
q = rcu_dereference(p->child);
if (q)
use(q);
rcu_read_unlock();
}
rcu_read_unlock();
In non-preemptible RCU, nesting is just the preemption count: each rcu_read_lock() increments it and each unlock decrements it. The outermost unlock is the one that re-enables preemption and makes the task eligible for a quiescent state. In PREEMPT_RCU, nesting is tracked in current->rcu_read_lock_nesting; the outermost unlock runs the special handling for blocked readers and deferred quiescent states. See kernel/rcu/tree_plugin.h.
The flavors nest with each other, but the unlock must match the lock. A rcu_read_lock_bh() section can contain a plain rcu_read_lock() section; the inner unlock ends only the inner reader, and the outer rcu_read_unlock_bh() ends the bh region. The lock and unlock must occur in the same context. Calling rcu_read_unlock_bh() from a different task than the one that called rcu_read_lock_bh() is illegal, because the bottom-half state is per task.
Nesting is not a way to extend an object’s lifetime past a grace period. The task remains a reader until the outermost unlock, so the grace period waits for the whole nest. That is usually what the code wants, but it also means that a long outer section delays reclamation for every object removed during it. Keep read-side sections short.
4. Publication and Memory Ordering on AArch64
A reader’s safety has two halves. The temporal half is handled by grace periods: the old object stays allocated until nobody can still be using it. The spatial half is handled by publication: when a reader loads the published pointer and then loads a field through it, the field must already contain the value the writer stored before publishing. Without the second half, a reader can obtain a perfectly live object and still observe uninitialized bytes inside it.
On AArch64 the vocabulary is small: stlr, ldar, ldapr, and dmb ish. This section explains why the two RCU accessors exist, what they compile to, and what they deliberately do not do.
4.1 Why rcu_assign_pointer() Exists
Consider the naive way to install a new object:
1
2
3
4
5
struct config *new = kmalloc(sizeof(*new), GFP_KERNEL);
new->timeout = 100;
new->flags = CONFIG_FLAG_NEW;
global_config = new; /* wrong */
There are two independent reordering hazards. The compiler may move the store to global_config before the stores to the fields, because the objects do not alias and C has no notion of publication. The CPU may commit the pointer store to the coherency point before the field stores are visible. AArch64 permits this: stores to different addresses have no ordering relationship unless the program asks for one.
1
2
3
4
5
6
7
8
9
10
11
12
13
NAIVE: plain store CORRECT: rcu_assign_pointer()
─────────────────── ─────────────────────────────
new->timeout = 100 new->timeout = 100
new->flags = NEW new->flags = NEW
str global_config, new stlr global_config, new
│ │
│ compiler or CPU may move the │ release store: every prior
│ pointer store ahead of the │ store is visible before the
│ field stores │ pointer becomes visible
▼ ▼
reader: ptr = new reader: ptr = new
timeout = 0 ✗ timeout = 100 ✓
flags = 0 ✗ flags = NEW ✓
A reader on another CPU can then load global_config, follow it, and read new->flags as zero. The object is live but not yet initialized from the reader’s point of view. This is the classic publication race, and no grace-period machinery can fix it, because the object was never correctly published.
rcu_assign_pointer() closes the race by making the pointer store a release store. Every access before the store in program order is visible to any CPU that observes the stored value, provided the observer orders its subsequent accesses after that observation. On AArch64 the store is stlr; the observer’s half is an acquiring load (ldar/ldapr) or a genuine address dependency. RCU uses the dependency form on the common path, which is why a plain ldr suffices for rcu_dereference().
A literal NULL assignment is special-cased to WRITE_ONCE(): there is no new object to order, but the store must still be single and non-torn. That is an optimization, not permission to publish real objects with WRITE_ONCE().
| Operation | Compiles to | Orders prior stores | Safe for first publication |
|---|---|---|---|
rcu_assign_pointer(p, v) | stlr | Yes | Yes |
RCU_INIT_POINTER(p, v) | str (via WRITE_ONCE) | No | No, unless already published |
WRITE_ONCE(p, v) | str | No | No, unless already published |
smp_store_release(&p, v) | stlr | Yes | Yes, but lacks the __rcu annotation |
smp_wmb(); WRITE_ONCE(p, v); | dmb ishst + str | Yes | Yes, but more expensive and easier to get wrong |
RCU_INIT_POINTER() provides no ordering for either the compiler or the CPU. It is permitted when setting the pointer to NULL, when the caller has prevented concurrent readers, or when the structure has already been exposed and has not changed in a reader-visible way. smp_store_release() is the primitive underneath rcu_assign_pointer(); using it directly works but loses the sparse annotation and lockdep discipline. The smp_wmb() form is strictly worse on AArch64: dmb ishst is a full store barrier, while stlr carries release semantics in the store itself.
4.2 Why rcu_dereference() Exists
The reader’s hazard is subtler. A plain C load of the pointer is not a stable operation. The compiler may reload it, merge it with another load, hoist it out of a loop, or rewrite the address dependency into a control dependency. Once that happens, the CPU may speculate the dependent load past a branch, because a control dependency does not order speculative loads on AArch64.
1
2
p = global_config; /* plain load */
x = p->timeout; /* dependent load */
The two dependency shapes look similar but behave differently:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
address dependency — safe control dependency — speculated
───────────────────────── ──────────────────────────────
ldr p, [global_config] ldr p, [global_config]
ldr x, [p + timeout] cbz p, .skip
│ ldr x, [p + timeout]
│ address unknown until │
│ the first load returns, so │ CPU may execute this load
│ the second cannot issue │ before the branch resolves
▼ ▼
ordered not ordered on AArch64
what the compiler may do what rcu_dereference() does
──────────────────────── ────────────────────────────
reload global_config one READ_ONCE() per dereference
merge the two loads a single value it cannot duplicate
hoist the load out of a loop keeps the address dependency intact
turn the dependency into a branch ldar / ldapr under LTO, so even a
control dependency cannot speculate
If the compiler reads global_config twice or uses a stale value of p, the reader can observe a torn or inconsistent view. rcu_dereference() forces a single READ_ONCE() and keeps the dependent access attached to the loaded value.
On most architectures, including AArch64, an address dependency is enough to order two loads: the CPU cannot perform the second load before the first returns, because it does not yet know the address. That was not true on Alpha, which required an explicit rmb; the Alpha port is gone and the old smp_read_barrier_depends() is now a no-op.
What AArch64 does need is protection against the compiler destroying the dependency. Under link-time optimization this is a live concern, so the AArch64 build overrides READ_ONCE() to emit ldar, or ldapr when the CPU has the RCpc extension, ensuring that a dependency converted into a control dependency still cannot be speculated. ldapr is a Load-Acquire RCpc: it orders later accesses against release stores, which is exactly the strength publication needs. The ALTERNATIVE machinery patches the cheapest correct instruction at boot.
See arch/arm64/include/asm/rwonce.h.
4.3 The AArch64 Instructions
| Instruction | Kernel wrapper | Ordering semantics | RCU use |
|---|---|---|---|
ldr | READ_ONCE() | None beyond address/data dependencies | Plain rcu_dereference() loads |
ldar | smp_load_acquire() | Load-acquire: later accesses observe after this load | smp_load_acquire(), LTO READ_ONCE() fallback |
ldapr | none directly | Load-acquire RCpc: later accesses ordered against release stores | LTO READ_ONCE() when ARM64_HAS_LDAPR |
stlr | smp_store_release() | Store-release: earlier accesses observed before this store | rcu_assign_pointer() |
stlrb, stlrh | smp_store_release() | Byte and halfword release stores | Narrow RCU-protected flags |
dmb ish | smp_mb() | Full barrier in the inner-shareable domain | GP transitions, synchronize_rcu() machinery |
dmb ishld | smp_rmb() | Load-load barrier | Read-side ordering where needed |
dmb ishst | smp_wmb() | Store-store barrier | Open-coded publication (discouraged) |
dsb sy | mb() | Full system barrier, waits for completion | Device I/O, not RCU data paths |
isb | isb() | Instruction synchronization | Self-modifying code, not RCU data paths |
Why dmb ish rather than dsb sy? The inner-shareable domain covers all CPUs that share the coherency point, which on a normal AArch64 system means all CPUs. dsb also waits for completion; dmb only enforces ordering and lets the pipeline continue. RCU needs ordering, not completion, so dmb ish is correct and much cheaper. The DMA barriers use the outer-shareable domain (osh) because they coordinate devices outside CPU coherency; RCU never needs osh.
AArch64 is other multi-copy atomic: a store becomes visible to all observers at the same instant. That is what makes the release-acquire handshake sufficient for publication and why RCU does not need Alpha-style transitivity tricks.
4.4 The Publication Protocol
A correct publication has five writer steps and three reader steps:
- Allocate a new object; it is private to the writer.
- Initialize every field a reader can reach.
- Publish with
rcu_assign_pointer(); the release store makes prior initialization visible. - Remove the old object from every RCU-protected path.
- Wait for a grace period, then free the old object.
The reader enters with rcu_read_lock(), loads with rcu_dereference(), and uses the object only while still inside the section.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct config {
u64 timeout;
u32 flags;
char name[32];
};
static struct config __rcu *global_config;
static int publish_config(u64 timeout, u32 flags, const char *name)
{
struct config *new;
new = kmalloc(sizeof(*new), GFP_KERNEL);
if (!new)
return -ENOMEM;
new->timeout = timeout;
new->flags = flags;
strscpy(new->name, name, sizeof(new->name));
rcu_assign_pointer(global_config, new);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
writer CPU reader CPU
────────── ──────────
new = kmalloc()
new->timeout = 100
new->flags = NEW
new->name = "fast"
│
│ stlr global_config, new
├──────────────────────────────────────────▶ ldr cfg, [global_config]
│ │ (address dependency)
│ ▼
│ ldr x, [cfg + timeout]
│ │
│ x == 100
│
│ old object still allocated
│ (grace period not yet started)
The dependency edge is the point. The reader’s ldr cfg returns the value written by stlr. Because the store is a release store and the load heads an address-dependency chain, the subsequent ldr x, [cfg + timeout] cannot execute before ldr cfg completes, and the writer’s initialization stores cannot become visible after the release store does. The reader therefore sees 100, never zero.
Two details are easy to miss. First, the release store orders all prior writes, not just the new object’s fields; if the writer updates a generation counter before publishing, that store is ordered too. Second, a reader that reaches the object through a different path needs that path’s ordering. If the object is also linked into a global array, publishing global_config does not order the array insertion. Each independently reachable pointer needs its own publication operation.
The same rule applies to lists and trees. __list_add_rcu() initializes new->next and new->prev, publishes the node with rcu_assign_pointer(), and only then fixes the backward link. A reader that acquires the predecessor’s next sees a fully formed node; the backward link is after publication because readers traverse forward. Section 8 covers the full list protocol.
4.5 What RCU Does Not Order
The most common RCU bug is not a missing grace period. It is an assumption that RCU provides an ordering guarantee it does not.
rcu_read_lock() is not an acquire barrier. In a non-preemptible kernel it is preempt_disable(), a compiler barrier plus a preemption count. In a preemptible kernel it is a per-task counter plus barrier(). Neither prevents a later load from being hoisted above the lock, nor a store inside the section from sinking below the unlock. A reader that needs to order an unrelated load must use smp_load_acquire(), smp_rmb(), or a data dependency.
rcu_read_unlock() is not a release barrier. A store inside the section is not automatically visible to a writer that observes the end of the section. The grace-period machinery provides a global ordering guarantee when synchronize_rcu() returns, but the unlock itself does not.
1
2
3
4
5
WRONG: "my store inside the section is published by the unlock"
R ── store x ──┤ unlock ├──▶ another CPU reads x ✗ unordered
RIGHT: "the grace period supplies the barrier"
R ── store x ──┤ unlock ├──── ... ──── dmb ish ── GP ends ──▶ reader ✓
The synchronize_rcu() guarantee is precise:
On systems with more than one CPU, when
synchronize_rcu()returns, each CPU is guaranteed to have executed a full memory barrier since the end of its last RCU read-side critical section whose beginning preceded the call tosynchronize_rcu(). In addition, each CPU having an RCU read-side critical section that extends beyond the return fromsynchronize_rcu()is guaranteed to have executed a full memory barrier after the beginning ofsynchronize_rcu()and before the beginning of that RCU read-side critical section.
See kernel/rcu/tree.c. On AArch64 this means, in effect, that every CPU has executed a dmb ish between the end of its old section and the return of synchronize_rcu().
1
2
3
4
5
6
7
8
9
10
CPU0 ── R ──┤unlock├──── dmb ish ───────────────────▶│
CPU1 ──────── R ────┤unlock├──── dmb ish ───────────▶│ synchronize_rcu()
CPU2 ── R ──┤unlock├───────── dmb ish ──────────────▶│ returns here
│
each CPU that was a reader before the call has executed a full
barrier between the end of that section and the return
CPU3 ────────────────── R (started late) ─────────────────▶ continues
it must also execute a barrier after the call began and before
its section started, or the grace period does not wait for it
rcu_assign_pointer() orders prior writes only:
1
2
rcu_assign_pointer(global, new);
new->late_field = 1; /* not ordered by the publication */
A reader that acquires global and reads late_field has no guarantee of seeing 1. The field must be initialized before publication.
RCU also does not order two unrelated pointers. If a writer publishes a then b, a reader that acquires b is not guaranteed to see the new value of a; the release store on b orders earlier stores only for a reader that acquires b. Each pointer’s readers need their own synchronization. Finally, RCU does not provide snapshot consistency. Loading two fields of the same object can yield one old value and one new value if the writer mutates in place. The contract is about object lifetime, not field atomicity. Section 15 returns to this when comparing RCU with seqlocks.
5. Grace Periods and Quiescent States
A grace period turns “the object is no longer reachable” into “the object is safe to free”. This section states the contract precisely, enumerates what counts as a quiescent state, explains the detection layers, and follows a grace period from start to finish.
5.1 The Grace-Period Contract
Let t0 be the moment a grace period starts. The contract is:
Every CPU and every task that was inside an RCU read-side critical section at
t0has left that critical section by the time the grace period ends.
Three consequences follow.
The grace period is global, not per-object. It waits for all CPUs and tasks, not just those that might have touched a particular object. That is what makes the read side cheap: the reader registers no object, version, or hazard pointer; it only marks that it is a reader. The price is paid by the writer, which waits for a system-wide event.
Readers that start after t1 do not extend the grace period. A reader that begins after the grace period ends cannot have acquired the old object during the covered interval. The removal was ordered before the grace period started, and a post-t1 reader normally obtains the new object. What it sees is still governed by publication ordering.
A reader that starts during the grace period may see either version. If it loads the old pointer, its CPU cannot report a quiescent state until the section ends, so the grace period waits. The guarantee is not that every reader during the interval sees the new value; it is that no reader can still hold the old value once the grace period ends. That depends on the removal happening before t0. If the writer removes after t0, the grace period does not cover the removal and the writer must start another one. This is why synchronize_rcu() is called after removal, never before.
1
2
3
4
5
6
7
8
9
10
11
12
t0 t1
│ │
writer remove old ───┤ ├─── free old
│◀───────── grace period ───────────▶│
│ │
R_old ──▶ (v0) ─────┤ │
│ ──▶ (v0) ───────────────────────▶│
│ │
R_late │ ──▶ (v1) ─────────────────────────────▶
│ │
└── every reader running at t0 ──────┘
has left before t1
R_old began before t0 and must finish before t1. R_new began after t0; if it loaded the old pointer, the grace period waits for it. A reader that runs past t1 must have started after its CPU reported a quiescent state, so it is outside the covered set. The grace period is a barrier between generations, not against all future readers.
| Guarantee | Provided by a grace period? |
|---|---|
| All pre-existing readers have finished | Yes |
| The old object can be freed | Yes, once the GP ends |
| Readers that start after the GP ends see the new value | Yes, if removal happened before t0 |
| The reader sees a consistent multi-field snapshot | No |
| Reader-side ordering of unrelated loads | No |
| A bound on how long the GP takes | No |
| That the writer’s later stores are visible | No |
5.2 What Counts as a Quiescent State
A quiescent state is any point at which a CPU or task is known not to be inside an RCU read-side critical section.
| Event or state | Why it is quiescent | How it is reported |
|---|---|---|
| Context switch | The task is no longer running; if it was a reader, it is either preemption-disabled or queued as a blocked reader | rcu_note_context_switch() |
| Return to user mode | No kernel read-side section spans the user/kernel boundary | Context tracking, ct_user_exit() |
| Idle | The CPU has no task and cannot be a reader | Context tracking, ct_idle_enter() |
| CPU offline | The CPU is out of the mask and reports for its tasks | CPU hotplug, rcu_report_qs_rnp() |
rcu_qs() | Explicit report by code that knows it is not a reader | Direct call |
cond_resched() | Voluntary reschedule point | rcu_all_qs() |
rcu_all_qs() | Explicit “safe point” report | Direct call |
| NMI entry | Handlers are implicit readers, not quiescent points | Not a QS |
The first four are events that happen at a definite time. rcu_qs() and cond_resched() are requests: the code tells RCU it has reached a point where it cannot be a reader. An NMI is neither: it runs on top of whatever the CPU was doing, possibly on top of a reader, so entering or leaving it proves nothing about the interrupted context.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
is the CPU or task provably outside
every RCU read-side critical section?
│
┌─────────────────────┼─────────────────────┐
▼ ▼ ▼
definite event explicit request no proof
────────────── ──────────────── ────────
context switch rcu_qs() NMI entry
return to user cond_resched() tick inside
idle entry rcu_all_qs() a reader
CPU offline ordinary kernel
execution
│ │ │
▼ ▼ ▼
report now, report now, not a QS: force a
valid only if it valid only if it reschedule or wait
falls inside the falls inside the for the CPU to
current GP current GP report on its own
An extended quiescent state (EQS) is a sustained state in which RCU is not watching the CPU: dynticks-idle and user mode are the important examples. No read-side section can be active in an EQS, so the whole interval counts as quiescent. The kernel tracks this with the per-CPU CT_RCU_WATCHING bit. Ordinary quiescent states are momentary and must occur inside the grace period to count; a CPU that reported before the grace period started must report again.
The preemption-disabled subtlety
In a non-preemptible build, rcu_read_lock() is preempt_disable(). A task inside the section cannot be context-switched, so a context switch proves the task was not a reader. That is why non-preemptible RCU can use CPU-only tracking.
In a preemptible build, a reader can be preempted. The context switch is still a quiescent state for the CPU, but the preempted task remains a reader and must be waited for separately. It is queued on the leaf rcu_node’s blkd_tasks list, and the grace period cannot end until every task that was blocking it has left its section. Sections 6.4 and 10.3 cover this.
What is not a quiescent state
rcu_read_unlock() by itself is not a quiescent state. It ends the reader, but the CPU may still be in the kernel running other readers. In a preemptible build the outermost unlock can report a quiescent state if the task was blocking the current grace period; that is why rcu_read_unlock_special() exists. In a non-preemptible build the unlock simply re-enables preemption; the next context switch, tick, or explicit report provides the quiescent state.
A scheduling-clock tick is not automatically a quiescent state either. A tick that interrupts a reader is evidence that the CPU is not quiescent. The handler checks whether the CPU is in user mode or idle; if it is, the tick is quiescent. If it is in kernel mode, the tick can only request a quiescent state by setting need_resched, which forces a context switch at the next opportunity.
5.3 Detection Mechanisms
Three layers feed the same per-CPU state and the same upward tree walk:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
event sources per-CPU state tree
───────────── ───────────── ────
context switch ──▶ rcu_note_context_switch ─┐
return to user ──▶ ct_user_exit ────────────┤
idle entry ──────▶ ct_idle_enter ───────────┼──▶ rdp->cpu_no_qs
explicit rcu_qs() / cond_resched() ─────────┤ rdp->gp_seq
scheduling-clock tick ──────────────────────┤ │
forced resched / expedited IPI ─────────────┘ ▼
rcu_report_qs_rdp()
│
▼
leaf rnp->qsmask
│ all bits clear
▼
parent rnp->qsmask
│ ...
▼
root rnp->qsmask == 0
│
▼
rcu_seq_end()
The sources differ in cost and availability. A context switch is free because the scheduler is already running. A tick is nearly free but only arrives if the CPU has a tick. An IPI is expensive but works on a CPU that is otherwise ignoring RCU. The tree walk is shared, so a new detection mechanism only has to produce a credible quiescent state.
Layer 1: voluntary reporting. rcu_note_context_switch() runs on every context switch. If the task is in a read-side section, it queues the task and marks it blocked; otherwise it reports a quiescent state for the CPU. A WARN_ONCE catches a voluntary context switch inside a preemptible read-side section, which is illegal. cond_resched() funnels into rcu_all_qs(), whose fast path returns immediately unless a grace period has asked for urgency via rcu_urgent_qs.
Layer 2: the scheduling-clock tick. rcu_sched_clock_irq() increments ticks_this_gp, checks rcu_urgent_qs, and, if the CPU is in kernel mode, sets need_resched so that the resulting context switch reports the quiescent state. If the CPU is in user mode or came from idle, it is already in an EQS and no reschedule is needed.
Layer 3: forced quiescent states. If a CPU does not report on its own, the grace-period kthread forces one. The force-quiescent-state loop scans the leaf nodes and calls a flavor-specific check. A positive return credits the CPU; a negative return asks for resched_cpu(). The resulting context switch is the quiescent state. This is why a CPU stuck in a long kernel loop with preemption enabled can still be pushed through a grace period.
The EQS snapshot
A CPU that is idle with the tick stopped produces no context switch and no tick. RCU handles this by snapshotting the CPU’s CT_RCU_WATCHING state at the first scan and comparing it later:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
first FQS scan later FQS recheck(s)
│ │
▼ ▼
snap = ct_rcu_watching_cpu_acquire() cur = ct_rcu_watching_cpu_acquire()
│ │
├── snap is EQS ──▶ credit QS now │
│ │
└── not EQS ──▶ wait for recheck ────────────┘
│
▼
snap == cur?
├── yes ──▶ not proven, keep waiting
└── no ──▶ passed through an EQS
credit QS
The question is not “is the CPU idle now?” but “has the counter changed since the snapshot?” A CPU can be back in kernel mode when the kthread looks; the changed counter still proves it passed through an EQS, which rules out a reader that predates the grace period. The bit lives in the per-CPU context_tracking.state word and is incremented with atomic_add_return(), which orders the transition against prior read-side sections.
On AArch64 the tick arrives through the architected timer and the GIC along the generic path, so the RCU handler itself is not architecture-specific. What is specific is the absence of a tick on dynticks-idle and nohz_full CPUs, which is exactly why the EQS bit and snapshot exist. Expedited grace periods use an IPI instead; on AArch64 it is delivered as IPI_CALL_FUNC through the GIC SGI mechanism.
5.4 The Grace-Period Sequence Number
RCU tracks grace periods with a single unsigned long, gp_seq. Its low two bits encode state and the rest count completed grace periods:
| Bits | Meaning |
|---|---|
[1:0] | State: 0 = idle, 1 = grace period in progress |
[63:2] | Counter: number of grace periods completed |
Starting a grace period adds one and leaves the state at 1; ending it adds three, which clears the state back to 0 and carries one into the counter, for a total change of +4 from an idle value. Both transitions execute an smp_mb(): the start barrier ensures the writer’s removal is visible before the grace period begins, and the end barrier ensures completion is visible before the writer frees.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
63 2 1 0
┌───────────────────────────────────────┬───────┐
│ completed grace periods │ state │
└───────────────────────────────────────┴───────┘
│ │
│ └─ 1 : GP in progress
└─── 0 : idle
idle 0x100 ──start +1──▶ 0x101 ──end +3──▶ 0x104 idle
│ │
│ snapshot │ snapshot
▼ ▼
0x108 0x108
│ │
└── one GP each ───┘
(the in-progress case skips 0x104:
that GP may predate the removal)
valid for a CPU to report? rdp->gp_seq == rnp->gp_seq
and not rdp->gpwrap
done? rcu_seq_done(&gp_seq, snap)
ULONG_CMP_GE(gp_seq, snap), circle-safe
A snapshot requests a future gp_seq value that proves a full grace period has elapsed:
1
s = (READ_ONCE(*sp) + 2 * RCU_SEQ_STATE_MASK + 1) & ~RCU_SEQ_STATE_MASK;
With RCU_SEQ_STATE_MASK == 3, this is (cur + 7) & ~3:
Current gp_seq | State | Snapshot | Meaning |
|---|---|---|---|
0x100 | Idle | 0x104 | Wait for the next grace period to end |
0x101 | In progress | 0x108 | Wait for the current GP to end, then one more |
0x104 | Idle | 0x108 | Wait for the next GP |
0x107 | In progress | 0x10c | Wait for the current GP to end, then one more |
The extra grace period in the in-progress case is a guard band. A snapshot taken during a grace period cannot be satisfied by the end of that same grace period, because the caller’s removal may have happened after it started. Waiting for the next one guarantees coverage. Wraparound safety is separate: rcu_seq_done() uses ULONG_CMP_GE(), a half-range unsigned comparison that treats the counter as a circle.
Each CPU keeps rdp->gp_seq and each node keeps rnp->gp_seq. A quiescent state is valid only for the grace period in which it was reported. rcu_report_qs_rdp() rejects a report when rdp->gp_seq != rnp->gp_seq or rdp->gpwrap is set; the CPU must then report again for the current grace period. That is why a long-idle CPU does not accidentally satisfy grace periods it never observed.
5.5 One Timeline
The following grace period runs on four CPUs. CPU0 and CPU1 are readers; CPU2 goes idle in the middle; CPU3 is busy in the kernel but not in a read-side section. The figure follows it through four phases: start, readers and reports, forcing the stragglers, and end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
Legend: R = read-side section QS = quiescent state EQS = extended QS
time flows downward; the GP kthread column is the reference
GP kthread CPU0 CPU1 CPU2 CPU3
────────── ──── ──── ──── ────
│ │ │ │ │
── PHASE 1 · START THE GRACE PERIOD ─────────────────────────────────────────────────────
│ gp_init │ │ │ │
│ seq 0x100→0x101 │ │ │ │
│ qsmask = 1111 │ │ │ │
│───── set bits ──────▶ │ │ │
│ · all four CPUs are now owed a quiescent state
│ · the start transition runs smp_mb(), so the writer's removal
│ is visible before the interval begins
│ │ │ │ │
── PHASE 2 · READERS ENTER AND LEAVE ────────────────────────────────────────────────────
│ │ rcu_read_lock() │ │ │
│ │ │ rcu_read_lock() │ │
│ │ (reader) │ (reader) │ ct_idle_enter │
│ │ │ │ watching = 0 │
│ · CPU2 stops its tick and enters an extended quiescent state;
│ it will never send an explicit report for this grace period
│ │ │ │ │
│ │ │ rcu_read_unlock │ │
│ │ rcu_read_unlock │ │ │
│ · in a non-preemptible build the unlock does not report by
│ itself; the next context switch or rcu_qs() supplies the QS
│◀──── QS report ─────┤ │ │ │
│ qsmask = 1110 │ │ │ │
│◀─────────────── QS report ────────────────┤ │ │
│ qsmask = 1100 │ │ │ │
│ · two bits cleared; CPU2 and CPU3 are still outstanding
│ │ │ │ │
── PHASE 3 · FORCE THE STRAGGLERS (FQS) ─────────────────────────────────────────────────
│ force_qs_rnp │ │ │ │
│─────────────────────── snapshot changed ────────────────────────▶ │
│ CPU2 credited │ │ │ │
│ with EQS │ │ │ │
│ qsmask = 1000 │ │ │ │
│ · no IPI reached CPU2: the kthread saw CT_RCU_WATCHING change
│ since the first scan, which proves it passed through an EQS
│ │ │ │ │
│ CPU3 in kernel, │ │ │ │
│ not a reader │ │ │ │
│────────────────────────────────── tick→need_resched ──────────────────────────────────▶
│ │ │ │ │ sched()
│ · the tick could not credit CPU3 because it was in kernel
│ mode; it only set need_resched, and the context switch reported
│◀───────────────────────────────────── QS report ──────────────────────────────────────┤
│ qsmask = 0000 │ │ │ │
│ │ │ │ │
── PHASE 4 · END AND RECLAIM ────────────────────────────────────────────────────────────
│ gp_cleanup │ │ │ │
│ seq 0x101→0x104 │ │ │ │
│ · the end transition runs smp_mb() so completion is visible first
│ │ │ │ │
│ callbacks run │ │ │ │
│ · call_rcu() callbacks for this GP may now free their objects
▼ │ │ │ │
one shared interval, four different ways to satisfy it
The same timeline in sequence form, without the per-row commentary:
sequenceDiagram
participant GP as GP kthread
participant C0 as CPU0
participant C1 as CPU1
participant C2 as CPU2
participant C3 as CPU3
Note over GP: t0 · seq 0x100→0x101 · qsmask 1111
C0->>C0: rcu_read_lock()
C1->>C1: rcu_read_lock()
C2->>C2: ct_idle_enter()
Note over C2: EQS: no report will come
C0->>C0: rcu_read_unlock()
C0->>GP: QS · qsmask 1110
C1->>C1: rcu_read_unlock()
C1->>GP: QS · qsmask 1100
GP->>C2: FQS · snapshot changed
Note over C2: EQS credited · qsmask 1000
GP->>C3: tick → need_resched
C3->>GP: QS · qsmask 0000
Note over GP: t1 · seq 0x101→0x104
Note over GP,C3: callbacks may free v0
Four different mechanisms satisfy the same grace period:
- CPU0 and CPU1 report through the unlock path. In a non-preemptible build the unlock itself does not report; the following context switch or
rcu_qs()does. In a preemptible build the outermost unlock can report directly if the task was blocking the grace period. - CPU2 is credited through the EQS snapshot. It never reported anything; the kthread observed that
CT_RCU_WATCHINGchanged and inferred the quiescent state. - CPU3 is forced through a reschedule. It was in the kernel, so the tick could not credit it directly; the urgency flag caused
need_resched, and the context switch reported the quiescent state. - The GP kthread itself reports a quiescent state as soon as it starts, because it cannot be a reader while running the scan. On a single-CPU system this eliminates a second FQS wait.
The FQS scans are controlled by jiffies_till_first_fqs and jiffies_till_next_fqs. The defaults let an idle system finish in milliseconds while avoiding excessive scanning on a busy system. The FQS loop is a polling mechanism layered on top of event-driven quiescent states; it exists for dynticks-idle CPUs, CPUs in long kernel loops, and offline CPUs still marked in the mask. Both the scan and the forced reschedule are paid by the writer, which is why RCU suits read-mostly workloads and not write-heavy ones.
The argument so far, end to end:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
§1 a seqlock cannot protect a pointer's lifetime
│ the sequence check runs after the dereference
▼
§2 split the update: remove ──▶ grace period ──▶ free
│
▼
§3 reader contract: no blocking, no sleeping, no side effects
│ that cannot be undone
▼
§4 spatial half — publication
│ init every field ──▶ stlr ──▶ ldr + address dependency
▼
§5 temporal half — reclamation
│ QS ──▶ per-CPU state ──▶ rcu_node tree ──▶ gp_seq advances
▼
§6 Tree RCU: the structures that make §5 scale past a few CPUs
Sections 1–5 state the rules a caller must obey and the guarantees the caller may rely on. The rest of this document is about how the kernel implements those guarantees efficiently on a machine with many CPUs, dynticks-idle cores, and CPUs that go offline while a grace period is in flight.
6. Tree RCU Internals
The previous section treated the grace period as a contract. This section opens the machinery that implements it. Tree RCU is a distributed state machine spread across three data structures: a global rcu_state, a hierarchy of rcu_node structures, and a per-CPU rcu_data. The hierarchy exists for one reason: to keep the cost of reporting a quiescent state proportional to the depth of a tree rather than to the number of CPUs.
6.1 The Data Structures
The global state is struct rcu_state:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct rcu_state {
struct rcu_node node[NUM_RCU_NODES]; /* Hierarchy. */
struct rcu_node *level[RCU_NUM_LVLS + 1];
/* Hierarchy levels (+1 to
* shut bogus gcc warning) */
int ncpus; /* # CPUs seen so far. */
int n_online_cpus; /* # CPUs online for RCU. */
/* The following fields are guarded by the root rcu_node's lock. */
unsigned long gp_seq ____cacheline_internodealigned_in_smp;
/* Grace-period sequence #. */
unsigned long gp_max; /* Maximum GP duration in jiffies. */
struct task_struct *gp_kthread; /* Task for grace periods. */
struct swait_queue_head gp_wq; /* Where GP task waits. */
short gp_flags; /* Commands for GP task. */
short gp_state; /* GP kthread sleep state. */
unsigned long gp_wake_time; /* Last GP kthread wake. */
unsigned long gp_wake_seq; /* ->gp_seq at ^^^. */
...
struct mutex barrier_mutex; /* Guards barrier fields. */
atomic_t barrier_cpu_count; /* # CPUs waiting on. */
struct completion barrier_completion; /* Wake at barrier end. */
unsigned long barrier_sequence; /* ++ at start and end of
* rcu_barrier(). */
...
struct mutex exp_mutex; /* Serialize expedited GP. */
...
unsigned long jiffies_force_qs; /* Time at which to invoke
* force_quiescent_state(). */
...
int nr_fqs_jiffies_stall; /* Number of fqs loops after
* which read jiffies and set
* jiffies_stall. */
...
const char *name; /* Name of structure. */
char abbr; /* Abbreviated name. */
...
};
See kernel/rcu/tree.h. The ____cacheline_internodealigned_in_smp on gp_seq is not cosmetic: it puts the most frequently read grace-period counter on its own cache line so that CPUs polling it do not invalidate the cache lines holding the kthread’s other state.
An rcu_node is one node of the hierarchy:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct rcu_node {
raw_spinlock_t __private lock; /* Root rcu_node's lock protects
* some rcu_state fields as well as
* following. */
unsigned long gp_seq; /* Track rsp->gp_seq. */
unsigned long gp_seq_needed; /* Track furthest future GP request. */
unsigned long completedqs; /* All QSes done for this node. */
unsigned long qsmask; /* CPUs or groups that need to switch in
* order for current grace period to proceed.
* In leaf rcu_node, each bit corresponds to
* an rcu_data structure, otherwise, each
* bit corresponds to a child rcu_node. */
unsigned long rcu_gp_init_mask; /* Mask of offline CPUs at GP init. */
unsigned long qsmaskinit; /* Per-GP initial value for qsmask. */
unsigned long qsmaskinitnext; /* Online CPUs for next GP. */
unsigned long expmask; /* CPUs or groups that need to check in
* to allow the current expedited GP
* to complete. */
...
unsigned long grpmask; /* Mask to apply to parent qsmask. */
int grplo; /* lowest-numbered CPU here. */
int grphi; /* highest-numbered CPU here. */
u8 grpnum; /* group number for next level up. */
u8 level; /* root is at level 0. */
bool wait_blkd_tasks;/* Necessary to wait for blocked tasks to
* exit RCU read-side critical sections
* before propagating offline up the
* rcu_node tree? */
struct rcu_node *parent;
struct list_head blkd_tasks;
/* Tasks blocked in RCU read-side
* critical section. Tasks are placed
* at the head of this list and age
* towards the tail. */
struct list_head *gp_tasks;
/* Pointer to the first task blocking
* the current grace period, or NULL
* if there is no such task. */
struct list_head *exp_tasks;
/* Pointer to the first task blocking
* the current expedited grace period,
* or NULL if there is no such task. */
...
};
See kernel/rcu/tree.h. The qsmask field is the heart of the hierarchy: at a leaf, each bit represents a CPU; at an interior node, each bit represents a child node. When a leaf’s qsmask becomes zero, it reports its grpmask to its parent, which clears the corresponding bit in the parent’s qsmask. When the root’s qsmask becomes zero, the grace period is complete.
The per-CPU state is struct rcu_data:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct rcu_data {
/* 1) quiescent-state and grace-period handling : */
unsigned long gp_seq; /* Track rsp->gp_seq counter. */
unsigned long gp_seq_needed; /* Track furthest future GP request. */
union rcu_noqs cpu_no_qs; /* No QSes yet for this CPU. */
bool core_needs_qs; /* Core waits for quiescent state. */
bool beenonline; /* CPU online at least once. */
bool gpwrap; /* Possible ->gp_seq wrap. */
unsigned int gpwrap_count; /* Count of GP sequence wrap. */
bool cpu_started; /* RCU watching this onlining CPU. */
struct rcu_node *mynode; /* This CPU's leaf of hierarchy */
unsigned long grpmask; /* Mask to apply to leaf qsmask. */
unsigned long ticks_this_gp; /* The number of scheduling-clock
* ticks this CPU has handled
* during and after the last grace
* period it is aware of. */
struct irq_work defer_qs_iw; /* Obtain later scheduler attention. */
int defer_qs_pending; /* irqwork or softirq pending? */
struct work_struct strict_work; /* Schedule readers for strict GPs. */
/* 2) batch handling */
struct rcu_segcblist cblist; /* Segmented callback list, with
* different callbacks waiting for
* different grace periods. */
long qlen_last_fqs_check;
unsigned long n_cbs_invoked; /* # callbacks invoked since boot. */
unsigned long n_force_qs_snap;
long blimit; /* Upper limit on a processed batch. */
/* 3) dynticks interface. */
int watching_snap; /* Per-GP tracking for dynticks. */
bool rcu_need_heavy_qs; /* GP old, so heavy quiescent state! */
bool rcu_urgent_qs; /* GP old need light quiescent state. */
bool rcu_forced_tick; /* Forced tick to provide QS. */
bool rcu_forced_tick_exp; /* ... provide QS to expedited GP. */
/* 4) rcu_barrier(), OOM callbacks, and expediting. */
unsigned long barrier_seq_snap; /* Snap of rcu_state.barrier_sequence. */
struct rcu_head barrier_head;
int exp_watching_snap; /* Double-check need for IPI. */
/* 5) Callback offloading. */
#ifdef CONFIG_RCU_NOCB_CPU
struct swait_queue_head nocb_cb_wq; /* For nocb kthreads to sleep on. */
...
#endif
...
};
See kernel/rcu/tree.h. The per-CPU structure is deliberately cache-line separated in several places. The nocb_* fields, when enabled, get their own cache lines because the offload kthreads and the enqueue path would otherwise contend on the same lines.
The callback list is a segmented list:
1
2
3
4
5
6
7
8
9
10
11
12
struct rcu_segcblist {
struct rcu_head *head;
struct rcu_head **tails[RCU_CBLIST_NSEGS];
struct rcu_gp_seq gp_seq[RCU_CBLIST_NSEGS];
#ifdef CONFIG_RCU_NOCB_CPU
atomic_long_t len;
#else
long len;
#endif
long seglen[RCU_CBLIST_NSEGS];
u8 flags;
};
See include/linux/rcu_segcblist.h. The four segments are:
| Segment | Callbacks | Ready to invoke? |
|---|---|---|
RCU_DONE_TAIL | Grace period has elapsed | Yes |
RCU_WAIT_TAIL | Waiting for the current grace period | No |
RCU_NEXT_READY_TAIL | Arrived before the next grace period started | No, but the next GP can handle them |
RCU_NEXT_TAIL | Might have arrived after the next GP started | No, not yet assigned a GP |
See include/linux/rcu_segcblist.h. The segmentation is what lets a single per-CPU list serve many grace periods: when a grace period ends, the RCU_WAIT_TAIL segment moves to RCU_DONE_TAIL, and the later segments shift down. Callbacks do not need to be scanned individually to decide which grace period they belong to.
The three structures fit together like this:
Segmentation lets one per-CPU list serve many grace periods. When a grace period ends, RCU_WAIT_TAIL moves to RCU_DONE_TAIL and later segments shift down; callbacks never have to be scanned individually to decide which grace period they belong to.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
┌────────────────────────────────────┐
│ struct rcu_state │
│ gp_seq, gp_flags, gp_wq │
│ node[] hierarchy, barrier state │
└─────────────────┬──────────────────┘
│ owns
┌────────────────────────────────────┐
│ root rcu_node │
│ qsmask, gp_seq, blkd_tasks │
└─────────────────┬──────────────────┘
│
┌───────────────────────┬───────────────────────┐
┌─────────────▼─────────────┐ ┌─────────────▼─────────────┐
│ leaf rcu_node │ │ leaf rcu_node │
│ qsmask, gp_seq │ │ qsmask, gp_seq │
│ blkd_tasks │ │ blkd_tasks │
└──────┬─────────────┬──────┘ └──────┬─────────────┬──────┘
│ │ │ │
┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐
│ rcu_data │ │ rcu_data │ │ rcu_data │ │ rcu_data │
│ cblist │ │ cblist │ │ cblist │ │ cblist │
│ mynode │ │ mynode │ │ mynode │ │ mynode │
└───────────┘ └───────────┘ └───────────┘ └───────────┘
CPU 0 CPU 1 CPU ... CPU N
rcu_state owns the tree and the global sequence. A CPU’s quiescent state travels up through mynode and its ancestors; a callback travels down from the global grace period into the per-CPU cblist.
6.2 The Combining Tree
The tree is built at boot from NR_CPUS, CONFIG_RCU_FANOUT, and CONFIG_RCU_FANOUT_LEAF. The leaf fanout is deliberately small (16 by default) because every CPU under a leaf touches that leaf’s lock. The interior fanout is large (64 on 64-bit) because interior nodes are touched only when a whole group reports.
For a 256-CPU machine with the defaults:
1
2
3
4
5
6
7
8
9
10
11
12
┌─────────────────────┐
│ root rcu_node │ level 0
│ qsmask: 16 bits │
└──────────┬──────────┘
┌─────────────────────┬──────────┬──────────────────────────────────┐
┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐
│ leaf 0 │ │ leaf 1 │ ... │ leaf 15 │ level 1
│ qsmask: │ │ qsmask: │ │ qsmask: │
│ 16 bits │ │ 16 bits │ │ 16 bits │
└───────────┘ └───────────┘ └───────────┘
│ │ │
CPU 0..15 CPU 16..31 CPU 240..255
Each leaf covers 16 CPUs, so 16 leaves cover 256 CPUs. A quiescent state from CPU 37 clears bit 5 of leaf 2’s qsmask. When leaf 2’s mask reaches zero, it clears bit 2 of the root’s mask. When the root reaches zero, the grace period is over.
rcu_report_qs_rnp() walks upward. It validates the grace period at every level with rnp->gp_seq != gps, which rejects a late report from an old grace period. It unlocks the child before locking the parent, and the rcu_node lock helpers order the child update before the parent update. On AArch64 that ordering comes from stlr/ldar and other-multi-copy atomicity, so the smp_mb__after_unlock_lock() used on weaker architectures expands to nothing. When the walk reaches the root, rcu_report_qs_rsp() sets RCU_GP_FLAG_FQS and wakes the grace-period kthread rather than doing the cleanup inline, keeping the reporting path short.
The propagation is implemented by rcu_report_qs_rnp():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
static void rcu_report_qs_rnp(unsigned long mask, struct rcu_node *rnp,
unsigned long gps, unsigned long flags)
__releases(rnp->lock)
{
unsigned long oldmask = 0;
struct rcu_node *rnp_c;
raw_lockdep_assert_held_rcu_node(rnp);
/* Walk up the rcu_node hierarchy. */
for (;;) {
if ((!(rnp->qsmask & mask) && mask) || rnp->gp_seq != gps) {
/*
* Our bit has already been cleared, or the
* relevant grace period is already over, so done.
*/
raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
return;
}
WARN_ON_ONCE(oldmask); /* Any child must be all zeroed! */
WARN_ON_ONCE(!rcu_is_leaf_node(rnp) &&
rcu_preempt_blocked_readers_cgp(rnp));
WRITE_ONCE(rnp->qsmask, rnp->qsmask & ~mask);
trace_rcu_quiescent_state_report(rcu_state.name, rnp->gp_seq,
mask, rnp->qsmask, rnp->level,
rnp->grplo, rnp->grphi,
!!rnp->gp_tasks);
if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
/* Other bits still set at this level, so done. */
raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
return;
}
rnp->completedqs = rnp->gp_seq;
mask = rnp->grpmask;
if (rnp->parent == NULL) {
/* No more levels. Exit loop holding root lock. */
break;
}
raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
rnp_c = rnp;
rnp = rnp->parent;
raw_spin_lock_irqsave_rcu_node(rnp, flags);
oldmask = READ_ONCE(rnp_c->qsmask);
}
/*
* Get here if we are the last CPU to pass through a quiescent
* state for this grace period. Invoke rcu_report_qs_rsp()
* to clean up and start the next grace period if one is needed.
*/
rcu_report_qs_rsp(flags); /* releases rnp->lock. */
}
See kernel/rcu/tree.c. The loop has three important properties.
The loop has three important properties.
It validates the grace period at every level. The rnp->gp_seq != gps check rejects a report that arrives after the grace period has ended. Without it, a late quiescent state from an old grace period could clear a bit that a new grace period needs.
It unlocks the child before locking the parent. The raw_spin_unlock_irqrestore_rcu_node(rnp, flags); ... rnp = rnp->parent; raw_spin_lock_irqsave_rcu_node(rnp, flags); sequence is an unlock-lock pair, and it is what orders the child’s qsmask update before the parent’s update. The rcu_node locking helpers call smp_mb__after_unlock_lock() immediately after a successful acquisition. See kernel/rcu/rcu.h. On AArch64 that macro expands to nothing, because the architecture does not select CONFIG_ARCH_WEAK_RELEASE_ACQUIRE; the ordering comes instead from the fact that stlr and ldar are RCsc acquire/release operations and AArch64 is other-multi-copy atomic. Architectures with weaker acquire/release semantics, such as PowerPC, need the explicit smp_mb(). See include/linux/rcupdate.h and Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.rst.
It stops at the root and calls rcu_report_qs_rsp(). That function does not end the grace period itself. It sets RCU_GP_FLAG_FQS and wakes the grace-period kthread:
The hierarchy is why RCU scales. Without it, every CPU would clear a bit in one global mask and contend on one cache line. With a fanout of 16, a CPU touches only its leaf; the root is touched once per group. The number of contended operations per grace period is proportional to the number of nodes, not the number of CPUs. On a 4096-CPU machine that is a two-order-of-magnitude difference.
6.3 The Grace-Period Kthread
The grace-period kthread runs an explicit loop: wait for a request, initialize the grace period, force quiescent states until the root mask clears, then clean up.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
request or wakeup
│
▼
┌─────────────────────────┐
┌───▶│ RCU_GP_WAIT_GPS │
│ └────────────┬────────────┘
│ │ rcu_gp_init()
│ ▼
│ ┌─────────────────────────┐
│ │ RCU_GP_DONE_GPS │
│ └────────────┬────────────┘
│ │ rcu_gp_fqs_loop()
│ ▼
│ ┌─────────────────────────┐ FQS due ┌──────────────────────┐
│ │ RCU_GP_WAIT_FQS │──────────▶│ RCU_GP_DOING_FQS │
│ └────────────┬────────────┘◀──────────└──────────────────────┘
│ │ root qsmask == 0
│ ▼
│ ┌─────────────────────────┐
│ │ RCU_GP_CLEANUP │
│ └────────────┬────────────┘
│ │ rcu_gp_cleanup()
│ ▼
│ ┌─────────────────────────┐
└────│ RCU_GP_CLEANED │
└─────────────────────────┘
rcu_gp_init() checks for a spurious wakeup, clears gp_flags, starts a normal synchronize_rcu segment, calls rcu_seq_start() on gp_seq, scans the leaf nodes to apply buffered CPU hotplug changes, copies qsmaskinit into qsmask at every node, and reports a quiescent state for its own CPU. The ordering of rcu_seq_start() before the hotplug scan is critical: if the counter advanced after the scan, a CPU that came online during the scan could be missed, and a reader on that CPU could hold an object the grace period frees. The smp_mb() inside rcu_seq_start() prevents that reordering.
rcu_gp_cleanup() does the reverse. It computes the post-grace-period value in a local variable, writes it to every node so that CPUs observing their leaf know the grace period is over, and only then reacquires the root lock and calls rcu_seq_end(&rcu_state.gp_seq). That final barrier publishes the completion globally. Propagating the new sequence to the nodes first lets CPUs advance their callbacks without waiting for the next grace period.
6.4 Quiescent-State Reporting
The per-CPU path is rcu_report_qs_rdp(). It has three cases:
- No valid quiescent state for this grace period.
rdp->cpu_no_qs.b.normis true; the report cannot be credited. - The report belongs to an older grace period.
rdp->gp_seq != rnp->gp_seqcatches it. This happens when a CPU was idle or offline across a grace-period boundary. - The report is valid. The CPU’s bit is cleared and the report propagates up the tree.
If the CPU’s callbacks are still waiting, the fact that it is reporting means the current grace period is about to end, so rcu_accelerate_cbs() moves them to RCU_WAIT_TAIL for the next one.
Blocked readers in PREEMPT_RCU
In a preemptible build a task can be preempted inside a read-side section. The CPU can still report a quiescent state — the task is not running — but the grace period cannot complete until the task leaves the section. The task is queued on the leaf rcu_node’s blkd_tasks list, ordered by age: new tasks go to the head, and gp_tasks points at the first task blocking the current grace period. Because the grace period must wait for all tasks that were readers when it started, it waits for the whole tail, not just gp_tasks. When a task leaves its section it removes itself; when gp_tasks reaches the tail, the grace period can proceed.
A leaf with a non-NULL gp_tasks cannot be considered done even if all CPUs reported, because one CPU has a preempted reader still holding a pointer. Priority boosting (CONFIG_RCU_BOOST) is the escape hatch when a low-priority reader blocks a high-priority waiter; it is a scheduling mitigation, not a correctness mechanism.
6.5 Forced Quiescent States and Dynticks
The first FQS scan and later scans do different things. The first saves a snapshot of each CPU’s CT_RCU_WATCHING state; later scans recheck it. The split is necessary because a CPU already idle at the start of the grace period has no transition to observe and must be credited from the initial snapshot, while a CPU that goes idle during the grace period has a transition that the recheck detects.
The function pointer passed to force_qs_rnp() is the flavor-specific check. Offline CPUs cannot report for themselves, so their quiescent state is reported by CPU hotplug or by rcu_gp_init()’s qsmaskinitnext scan. Online CPUs that do not respond are forced through resched_cpu().
rcu_need_heavy_qs requests a heavy quiescent state: the CPU should enter a real EQS (idle), not merely report a lightweight one. rcu_momentary_eqs() implements this by briefly entering and leaving an extended quiescent state. That distinction matters when a grace period has been stalled for a long time and lightweight reports are not convincing.
Stall detection is layered on top. If a grace period has been in progress longer than jiffies_stall, the kernel prints a stall warning with a stack trace of the offending CPU or task. A stall usually means a reader is stuck in a loop, a task is blocked in a read-side section, or a CPU is not responding to interrupts. rcutorture deliberately creates these conditions to verify that the warnings fire.
6.6 Expedited Grace Periods
An expedited grace period refuses to wait for the next tick. It is selected by synchronize_rcu_expedited() or the rcu_expedited boot parameter, and the protocol is:
- Snapshot the expedited sequence with
rcu_exp_gp_seq_snap(). - Serialize with other expedited requests using
exp_funnel_lock(). - Initialize
expmaskin every node fromexpmaskinitnext. - Send an IPI to each CPU that has not checked in.
- Wait on the root node’s
exp_wqfor the sequence to complete.
On AArch64 the IPI is IPI_CALL_FUNC delivered through the GIC. rcu_exp_handler() checks the interrupted context: if the CPU is not in a read-side section and is preemptible (or was interrupted from idle), it reports immediately; if it is in a section, it sets rcu_read_unlock_special.b.exp_hint so the outermost unlock reports; if it is in a preemption- or softirq-disabled region, it defers with rcu_exp_need_qs().
Expedited grace periods finish in microseconds instead of milliseconds, but they interrupt every CPU, including CPUs running real-time tasks, and can cause latency spikes. The kernel documentation explicitly warns against using them in a loop: batch the updates and use a single synchronize_rcu(). The rcu_expedited boot parameter has the same caution; it is useful for debugging and very latency-sensitive systems, not for general-purpose kernels.
6.7 Callback Processing
Callbacks are invoked by rcu_do_batch(), called from rcu_core() in softirq context or from the rcuc/N kthread when CONFIG_RCU_BOOST is enabled. Offloaded CPUs use rcuop/N kthreads instead. The function extracts the done segment into a temporary list, invokes the callbacks, and stops when a count or time limit is reached. Remaining callbacks stay in RCU_DONE_TAIL, and invoke_rcu_core() arranges another pass.
The batch has two limits: a count limit (bl) that adapts to the number of pending callbacks, and a time limit that prevents a callback flood from monopolizing the CPU. In softirq context the code also checks need_resched(), because running too long starves other softirq vectors. In kthread context it can run longer, but it still checks the time limit because an rcuc kthread that runs too long delays its own quiescent-state reporting.
rcu_core() is the “do everything that needs doing on this CPU” function: report deferred quiescent states, advance callbacks, start a grace period if needed, check for stalls, and invoke ready callbacks. It is invoked from the RCU_SOFTIRQ handler, from the tick when rcu_pending() is true, and from call_rcu_core() when a callback is enqueued.
rcu_advance_cbs() moves callbacks whose gp_seq has completed into the done segment, then classifies the rest and may start a new grace period. This is where the two halves of RCU meet: the grace-period machinery produces a new gp_seq, and the callback machinery compares each segment’s sequence against it and advances the segment when it is safe. A callback runs only when its segment reaches RCU_DONE_TAIL.
7. The Write Side: Removal and Reclamation
The read side is deliberately simple. The write side carries the complexity because it must make the old object unreachable before freeing it, then choose between blocking until that is true and deferring the free to a callback.
7.1 The Update Sequence
Every RCU update follows the same five steps:
- Allocate and initialize a new version. No reader can see it yet.
- Publish it with
rcu_assign_pointer(), or link it with the appropriate_rcuprimitive. - Remove the old version from every path a reader can traverse.
- Wait for a grace period that started after the removal.
- Free the old version.
Steps 3 and 4 are separate on purpose. Removal must happen before the grace period starts, otherwise the grace period does not cover readers that could still hold the old pointer. This is the most common hand-written RCU mistake:
1
2
3
4
5
6
7
8
9
/* Wrong: the grace period may start before the removal. */
synchronize_rcu();
rcu_assign_pointer(global, new);
kfree(old);
/* Right: remove first, then wait. */
rcu_assign_pointer(global, new);
synchronize_rcu();
kfree(old);
Even the right order is incomplete if old is reachable through another path. If the object is in both a hash table and a linked list, both links must be removed before the grace period.
The canonical single-pointer update is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static DEFINE_MUTEX(config_mutex);
static struct config __rcu *global_config;
static int replace_config(struct config *new)
{
struct config *old;
mutex_lock(&config_mutex);
old = rcu_dereference_protected(global_config,
lockdep_is_held(&config_mutex));
rcu_assign_pointer(global_config, new);
mutex_unlock(&config_mutex);
synchronize_rcu();
kfree(old);
return 0;
}
The mutex serializes writers; it does not exclude readers and does not need to. Publication and removal are atomic with respect to readers. rcu_dereference_protected() is correct on the update side because the mutex prevents another writer from changing the pointer concurrently. synchronize_rcu() is outside the mutex so that a slow grace period does not block other writers; it only has to happen after removal and before the free.
7.2 Choosing a Reclaim Method
The choice is dictated by context and by what the caller must do next.
| Property | synchronize_rcu() | call_rcu() | kfree_rcu() |
|---|---|---|---|
| Blocks | Yes | No | No |
| Callable from atomic context | No | Yes | Yes, two-argument form |
| Callable from interrupt context | No | Yes | Yes, two-argument form |
| Callable from RCU read-side section | No | Yes | Yes |
| Returns after the object is safe to free | Yes | No; callback runs later | No; deferred free runs later |
Needs an rcu_head in the object | No | Yes | Yes, for the two-argument form |
| Grace-period cost | Paid synchronously | Amortized with other callbacks | Batched; amortized |
| Latency | Milliseconds | Depends on callback load | Intentionally less predictable |
| Typical use | Teardown, setsockopt(), namespace exit | Packet queues, inode eviction, interrupt context | Plain kmalloc objects |
A simple decision procedure:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Need to reclaim an old RCU-protected version
│
▼
Can the caller block?
├── yes ──▶ synchronize_rcu(), then free/reclaim
└── no
│
▼
Is it a plain kmalloc/kvfree object with
the rcu_head within the first 4096 bytes?
├── yes ──▶ kfree_rcu()
└── no ──▶ call_rcu(head, callback)
│
▼
Need the callback promptly?
├── yes ──▶ call_rcu_hurry()
└── no ──▶ call_rcu()
If many objects share the same removal, batch them:
unlink the batch, then one callback pass instead of
one grace period per object.
synchronize_rcu() is listed first because it is the simplest option when the caller can wait, and its blocking behavior provides natural backpressure against a writer producing old versions faster than RCU can reclaim them. The last rule matters most for performance: a loop of synchronize_rcu() pays one grace period per object, while a loop of call_rcu() shares grace periods. If the objects can be collected into a list, unlink the whole list and use one callback for the batch.
7.3 synchronize_rcu()
synchronize_rcu() is the blocking form. It waits until a grace period that started after the call has elapsed, and it may sleep. It is the right choice when the writer is in process context and needs the old object gone before continuing.
The entry point has three cases:
| Case | Condition | Action |
|---|---|---|
| Early boot or uniprocessor | rcu_blocking_is_gp() | Advance the counters locally; the call is a vacuous grace period |
| Expedited mode | rcu_gp_is_expedited() | synchronize_rcu_expedited() |
| Normal mode | Otherwise | synchronize_rcu_normal() |
The normal path has two implementations. The classic one queues a callback with call_rcu_hurry() and waits on a completion; the newer rcu_sr_normal path batches waiters on a lockless list and wakes them when the grace period ends. Both provide the same guarantee; the choice is a performance detail, not a semantic one.
Calling synchronize_rcu() from inside an RCU read-side section is illegal: it would wait for a grace period that cannot end until the caller leaves the section. It is a self-deadlock, and lockdep catches it.
The guarantee that makes the call useful is the memory-ordering paragraph from Section 4.5: when it returns, each CPU has executed a full barrier since the end of its last read-side section whose beginning preceded the call. That is why the writer needs no explicit smp_mb() afterward. In practice, a store performed by a reader before rcu_read_unlock() is visible to the writer after synchronize_rcu() returns. The kernel enforces it with the smp_mb() calls in rcu_seq_start()/rcu_seq_end() and with the unlock-lock pairs in the rcu_node hierarchy.
The cost is the cost of a grace period: a wakeup, a tree scan, and possibly a forced reschedule or an IPI. On an idle system it is a few milliseconds; on a busy system it can be longer. Calling it in a loop is almost always a design error. If a writer has many objects to free, batch them under one grace period, or use call_rcu() and let the callback machinery amortize the cost.
7.4 call_rcu()
call_rcu() is the non-blocking form. It queues a callback that runs after a grace period. The caller must embed a struct rcu_head in the object or allocate one separately; the callback receives a pointer to the head and typically uses container_of() to recover the object.
1
2
3
4
5
6
7
8
9
10
11
struct my_obj {
struct rcu_head rcu;
/* ... */
};
static void my_obj_free(struct rcu_head *head)
{
struct my_obj *obj = container_of(head, struct my_obj, rcu);
kfree(obj);
}
struct rcu_head is an alias for struct callback_head, which contains a next pointer and a function pointer and must be pointer-aligned. The enqueue path validates alignment and the function pointer, detects a double enqueue, and adds the callback to the current CPU’s segmented list with interrupts disabled. The IRQ disable protects the non-atomic list operations against concurrent enqueues from interrupt handlers.
The callback is queued on the CPU that called call_rcu(), so callbacks from the same CPU are invoked in FIFO order within a grace period; callbacks on different CPUs have no global order. The enqueue does not necessarily start a grace period: below the qhimark threshold, the callback waits for the next grace period started for some other reason. That batching is what makes RCU efficient under load.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
call_rcu(head, func)
│
▼
┌──────────────────────────────┐
│ __call_rcu_common() │
│ validate alignment / func │
│ head->func = func │
│ local_irq_save() │
└──────────────┬───────────────┘
│
┌──────┴───────┐
▼ ▼
normal CPU offloaded CPU
call_rcu_core call_rcu_nocb
│ │
▼ ▼
rdp->cblist rcuop/N queue
RCU_NEXT_TAIL │
│ │
└──────┬───────┘
▼
grace period starts
│
▼
callback moves to RCU_DONE_TAIL
│
▼
softirq / rcuc / rcuop invokes
func(head)
│
▼
callback frees or recycles object
The callback contract has hard rules:
- The
rcu_headmust not be freed or reused until the callback runs. Reusing it is a double-enqueue bug; the kernel may leak the object rather than risk corruption. - The callback runs in softirq context, or an
rcuc/rcuopkthread, and must not sleep. It may not callsynchronize_rcu(),mutex_lock(), or another blocking primitive, and it should be short. - The callback may re-post itself. Calling
call_rcu(head, func)from insidefuncis legal and is common for periodic work; the new callback waits for a new grace period. - Callbacks are ordered per CPU, not globally.
- The callback may run concurrently with new readers. Pre-existing readers have finished, but a reader that started after
call_rcu()can still be inside a section when the callback runs; it cannot hold the freed object because it started after the removal.
7.5 kfree_rcu()
Most RCU callbacks do nothing but call kfree(). Allocating a callback function for each one wastes text space and, in a module, forces the module to call rcu_barrier() at unload. kfree_rcu() handles the common case:
1
2
3
4
5
6
struct my_obj {
struct rcu_head rcu;
char data[];
};
kfree_rcu(obj, rcu);
The two-argument form takes the object and the name of its rcu_head field. The headless form, kfree_rcu_mightsleep(ptr), does not require an rcu_head but may only be called from a context that can sleep, because it can fall back to synchronize_rcu() under memory pressure. kfree_rcu_nolock() supports only the two-argument form for contexts where the per-CPU lock cannot be taken.
The implementation batches requests per CPU in a kfree_rcu_cpu structure and drains them from a workqueue every KFREE_DRAIN_JIFFIES:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
kfree_rcu(obj, rcu)
│
▼
per-CPU kfree_rcu_cpu
┌──────────────────────────────┐
│ bulk array / page cache │
│ head list (fallback path) │
└──────────────┬───────────────┘
│ KFREE_DRAIN_JIFFIES
▼
drain workqueue
│
▼
queue callback(s) / request GP
│
▼
grace period
│
▼
workqueue frees the batch with kvfree()
The extra per-CPU layer is why kfree_rcu() can turn a stream of individual frees into a handful of grace periods, and why its latency is intentionally less predictable than call_rcu_hurry().
Constraints:
- The object must have been allocated by
kmalloc(),kmalloc_nolock(), orkmem_cache_alloc(). - The
rcu_headfield must be within the first 4096 bytes. The callback recovers the base address by aligning down to a page boundary, which only works within one page; the check is a compile-timeBUILD_BUG_ON(). kfree_rcu()is not a destructor. If the object owns other resources, a callback must free them;kfree_rcu()is not enough.
7.6 rcu_barrier()
rcu_barrier() waits until all call_rcu() callbacks queued before the call have been invoked. It is not a grace-period primitive:
Note that this primitive does not necessarily wait for an RCU grace period to complete. For example, if there are no RCU callbacks queued anywhere in the system, then
rcu_barrier()is within its rights to return immediately, without waiting for anything, much less an RCU grace period.
See kernel/rcu/tree.c. synchronize_rcu() waits for readers; rcu_barrier() waits for callbacks. A queued callback may still be waiting for its grace period, so the barrier waits for that indirectly, but if no callbacks are queued there is nothing to wait for.
The implementation is a distributed counting scheme. It snapshots barrier_sequence, sets barrier_cpu_count to two, and for each CPU with callbacks runs rcu_barrier_handler() on that CPU via smp_call_function_single(). The handler enqueues a special callback on that CPU’s FIFO list. Because the list is FIFO, the special callback cannot run until all earlier callbacks have run. Each special callback decrements the count; when it reaches zero, the barrier completes. The retry path handles a CPU going offline or an IPI failure by waiting a jiffy and trying again.
rcu_barrier() is typically used at module unload. If a module queues callbacks that reference module code, it cannot be unloaded until those callbacks have run, because their function pointers would point into freed text:
1
2
3
4
5
static void __exit my_module_exit(void)
{
unregister_everything(); /* stop new callbacks */
rcu_barrier(); /* wait for queued callbacks */
}
A module that uses kfree_rcu() does not need rcu_barrier() at unload, because there is no module-local callback function to protect. Two limitations matter: the barrier only covers callbacks queued before the call, and it does not wait for SRCU callbacks; srcu_barrier() is the SRCU equivalent.
7.7 Callback Context, Lazy Callbacks, and Offloading
A callback runs in one of three contexts:
| Configuration | Context | Can sleep? |
|---|---|---|
| Default | RCU_SOFTIRQ softirq | No |
CONFIG_RCU_BOOST or callback kthreads | rcuc/N kthread, softirqs disabled | No |
CONFIG_RCU_NOCB_CPU | rcuop/N (or rcuos/N) kthread | No; dedicated kthread, but still BH-disabled around each callback |
In all three cases the callback must not sleep. The softirq path is the most constrained: interrupts are enabled but bottom halves are disabled. The rcuc and rcuop kthreads are real kthreads, but they deliberately emulate that environment. The restriction comes from the execution context, not from the callback-list lock, which is released before the callback is invoked. A sleeping callback would stall rcu_barrier() and the queue behind it, and could wait on a task that is itself waiting for the grace period.
CONFIG_RCU_NOCB_CPU moves callback processing off selected CPUs, configured with rcu_nocbs=. An offloaded CPU has no callbacks of its own; rcuog/N handles grace-period requests and rcuop/N/rcuos/N invokes callbacks. This is used with nohz_full to let a CPU run a single task without RCU interrupts. The cost is extra scheduling latency for the offload kthreads.
CONFIG_RCU_LAZY is the other callback policy. With it, plain call_rcu() may keep a callback lazy and delay the grace period for many seconds to save energy on low-utilization battery-powered devices. call_rcu_hurry() bypasses the delay. Code that frees memory under pressure should hurry; code that frees cold objects on an idle system can let the kernel batch the work. The behavior is controlled by the rcutree.enable_rcu_lazy module parameter.
A callback enqueue wakes the grace-period kthread only when the callback count exceeds qhimark, when a synchronize_rcu() caller wakes it, when the FQS timer expires, on a CPU hotplug event, or when an expedited grace period is requested. That laziness is deliberate: starting a grace period costs, and the kernel amortizes it across as many callbacks as possible.
7.8 Write-Side API at a Glance
| API | Blocks? | Waits for | Callback context | Use |
|---|---|---|---|---|
synchronize_rcu() | Yes | Pre-existing readers | — | Process context; free before returning |
synchronize_rcu_expedited() | Yes | Pre-existing readers, aggressively | — | Rare latency-sensitive reconfiguration |
call_rcu() | No | Nothing; queues a callback | Softirq / rcuc | Atomic or interrupt context; defer free |
call_rcu_hurry() | No | Nothing; starts the GP promptly | Softirq / rcuc | Latency-sensitive asynchronous free |
kfree_rcu() | No | Nothing; batches a deferred free | Workqueue | Plain kmalloc object, two-argument form |
kfree_rcu_mightsleep() | May sleep | Nothing; batches a deferred free | Workqueue | Headless form, sleepable context |
rcu_barrier() | Yes | All previously queued callbacks | — | Module unload, teardown |
srcu_barrier() | Yes | All queued call_srcu() callbacks | — | SRCU teardown |
8. RCU-Protected Lists
Linked lists are the most common RCU-protected structure and the place where the protocol becomes concrete. A reader walks head->next, then next->next, and so on. A writer unlinks a node by changing its predecessor’s next. If the writer poisons or frees the node, a reader already on it follows a bad pointer on its next step. The _rcu primitives exist to prevent that.
8.1 Why List Operations Need Special Variants
Ordinary list_del() is designed for callers that exclude all other access. It unlinks the node and then poisons both links:
1
2
3
4
5
6
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
Under a lock, poisoning is a debugging aid: touching the removed node after the unlock faults loudly. Under RCU it is fatal, because a reader may legitimately still be on the node:
1
2
3
4
5
6
reader: ... ──▶ [ B ] ──▶ [ C ] ──▶ ...
▲
writer: └── list_del(B); kfree(B)
│
└── B->next = LIST_POISON1
reader next step: B->next ──▶ fault
The reader loaded B before the removal and is about to read B->next. It is not buggy: it is inside an RCU section, and the point of RCU is that it may still use B. The list primitive, not the reader, must preserve the traversal.
The _rcu variants follow three rules:
- Never poison the forward pointer of a removed node. A reader on the node must be able to follow
nextto a node still in the list. - Publish insertions with a release store. A reader that acquires the predecessor’s
nextmust see a fully initialized new node. - Do not free the removed node until a grace period has elapsed. The node stays readable but is no longer reachable from the head.
The primitives implement the first two; the caller implements the third with synchronize_rcu() or call_rcu().
8.2 Adding, Replacing, and Removing
All insertion helpers funnel through __list_add_rcu():
1
2
3
4
new->next = next;
new->prev = prev;
rcu_assign_pointer(list_next_rcu(prev), new);
next->prev = new;
The order is deliberate. new->next and new->prev are set while the node is private. rcu_assign_pointer() publishes it; the release store guarantees that a reader seeing the new node also sees its links. next->prev = new fixes the backward link after publication, which is safe because readers traverse forward. list_add_rcu() inserts after the head (stack behavior); list_add_tail_rcu() inserts before the head (queue behavior).
1
2
3
4
5
6
7
8
9
10
11
12
before: head ──▶ A ──▶ B ──▶ ...
new node: new->next = B
new->prev = A
(private to the writer)
step 1: A ──▶ new ──▶ B (release store: A->next = new)
(new->next and new->prev were set before publication)
step 2: B->prev = new (backward link, after publication)
after: head ──▶ A ──▶ new ──▶ B ──▶ ...
list_replace_rcu() is a single atomic publication: it copies the old node’s links into the new node, release-stores the predecessor’s next, fixes the successor’s prev, and poisons only old->prev. A reader that loaded old still sees a valid old->next; a reader that loads after publication sees new. The old->prev poison is safe because forward traversal does not use it.
list_del_rcu() unlinks the node and poisons only prev:
1
2
3
4
5
static inline void list_del_rcu(struct list_head *entry)
{
__list_del_entry(entry);
entry->prev = LIST_POISON2;
}
The next pointer is left intact, so a reader already on the node can still reach the successor, which is still in the list. list_bidir_del_rcu() poisons neither pointer for readers that traverse backward; the cost is that the node’s links are left inconsistent, so ordinary predicates such as list_empty() cannot be used on it.
Hash lists use the same pattern. hlist_add_head_rcu() publishes with rcu_assign_pointer(); hlist_del_rcu() unlinks and poisons only pprev, leaving next for forward traversal.
None of these primitives serialize writers with each other. A concurrent add and remove on the same list will corrupt the links, because both modify the same prev/next pointers. RCU protects readers from writers, not writers from each other. The usual solution is a mutex or spinlock around all mutations.
8.3 Traversal
The reader-side iterator is list_for_each_entry_rcu(). It is a plain for loop whose RCU-specific parts are:
list_entry_rcu()wrapsREAD_ONCE()around the link load and usescontainer_of(), preserving the address dependency from the link to the containing object.__list_check_rcu()is a lockdep check that fires if the iterator is used outside an RCU section or outside the alternate protection named bycond.
The iterator family:
| Iterator | Starts at | Use |
|---|---|---|
list_for_each_entry_rcu() | First entry | Normal traversal |
list_for_each_entry_continue_rcu() | After the current entry | Resume a traversal |
list_for_each_entry_from_rcu() | The current entry | Resume including the current entry |
list_for_each_entry_srcu() | First entry | SRCU-protected list |
list_for_each_entry_lockless() | First entry | Exception context or add-only lists |
The continue and from variants require that the starting node was in the list when the read-side section began, or that the caller holds a non-RCU reference keeping it alive and in the list. Otherwise the node may have been removed and freed before the iterator touches it.
There is deliberately no list_empty_rcu() or list_first_entry_rcu(). A separate emptiness check followed by a first-entry load has a race: the list can become empty between the two. Use list_first_or_null_rcu(), which performs a single READ_ONCE() of head->next and returns NULL if the list is empty.
list_for_each_entry_rcu() guarantees that the links it follows are valid and that the current entry is not freed while the section is active, provided the writer used list_del_rcu() and waited for a grace period. It does not guarantee that the entry is still in the list, that the traversal is a snapshot, or that the entry’s fields are immutable. Treat the entry as read-only and revalidate any predicate if it matters.
8.4 list_del_rcu() vs. list_del()
| Property | list_del() | list_del_rcu() |
|---|---|---|
| Unlinks the node | Yes | Yes |
Poisons next | Yes, LIST_POISON1 | No |
Poisons prev | Yes, LIST_POISON2 | Yes, LIST_POISON2 |
| Safe for a reader already on the node | No | Yes |
| Safe for a reader that has not reached the node | No | Yes |
| Can free immediately | No, even with RCU | No, needs a grace period |
| Can re-add immediately | No, it is poisoned | No, it is still linked to old neighbours |
| Typical use | Under an exclusive lock | RCU-protected list |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
┌──── list_del(B) ─────┐
│ prev->next = C │
│ C->prev = prev │
│ B->next = POISON1 │
│ B->prev = POISON2 │
└──────────────────────┘
reader: load B ─────────────────────────────▶ load B->next ──▶ fault
┌──── list_del_rcu(B) ─┐
│ prev->next = C │
│ C->prev = prev │
│ B->prev = POISON2 │
│ B->next unchanged │
└──────────────────────┘
reader: load B ─────────────────────────────▶ load B->next ──▶ C
The forward pointer is the crucial one. The reader walks from B to C and continues; B is no longer reachable from the head, so no new reader can arrive at it, but the reader already there can finish. If a reader needs backward traversal, use list_bidir_del_rcu(), which leaves both links intact at the cost of losing the poisoning check.
Neither function replaces a grace period. list_del_rcu() makes the node safe to traverse, not safe to free. The node can still be in a reader’s hands:
1
2
list_del_rcu(&entry->list);
call_rcu(&entry->rcu, free_entry);
or
1
2
3
list_del_rcu(&entry->list);
synchronize_rcu();
kfree(entry);
list_del_rcu() also does not reinitialize the node. list_empty() on it does not return true, and re-adding it before the grace period is a bug because next still points at its old successor. Reinitialize with INIT_LIST_HEAD() only after the grace period.
8.5 List API at a Glance
| API | Purpose | Writer lock needed? | Free after GP? |
|---|---|---|---|
list_add_rcu(new, head) | Insert after head (stack) | Yes | — |
list_add_tail_rcu(new, head) | Insert before head (queue) | Yes | — |
list_replace_rcu(old, new) | Atomically replace a node | Yes | Yes, for old |
list_del_rcu(entry) | Unlink, preserve next | Yes | Yes |
list_bidir_del_rcu(entry) | Unlink, preserve both links | Yes | Yes |
hlist_add_head_rcu(n, h) | Insert at hash-list head | Yes | — |
hlist_del_rcu(n) | Unlink, preserve next | Yes | Yes |
list_for_each_entry_rcu(pos, head, member) | Traverse | Reader section only | — |
list_first_or_null_rcu(head, type, member) | Race-free first entry | Reader section only | — |
9. A Complete Multi-Kthread Example
This section builds a loadable module that exercises the whole protocol: several reader kthreads traversing an RCU-protected list, a writer adding and removing entries, and an exit path that stops everything, waits for readers and callbacks, and reclaims the remaining memory. The code is pedagogical but structured like real kernel code, and every rule it demonstrates has a counterpart in the VFS, the network stack, or the credential code.
9.1 The Module
The module keeps a bounded list of struct demo_entry, each with an immutable seq and value. Readers sum the values; the writer adds at the tail and removes from the head. Module boilerplate and kthread creation are elided; the code below is the part that matters for RCU.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
struct demo_entry {
struct list_head list;
struct rcu_head rcu;
u64 seq;
u64 value;
};
static LIST_HEAD(demo_list);
static DEFINE_MUTEX(demo_mutex);
static atomic_t demo_count = ATOMIC_INIT(0);
static atomic64_t demo_next_seq = ATOMIC64_INIT(0);
static atomic64_t demo_sum = ATOMIC64_INIT(0);
static void demo_entry_free_rcu(struct rcu_head *head)
{
struct demo_entry *entry = container_of(head, struct demo_entry, rcu);
kfree(entry);
}
static void demo_add(void)
{
struct demo_entry *entry = kzalloc(sizeof(*entry), GFP_KERNEL);
if (!entry)
return;
entry->seq = atomic64_inc_return(&demo_next_seq);
entry->value = entry->seq * 2654435761ULL;
mutex_lock(&demo_mutex);
list_add_tail_rcu(&entry->list, &demo_list);
atomic_inc(&demo_count);
mutex_unlock(&demo_mutex);
}
static bool demo_remove_oldest(void)
{
struct demo_entry *entry;
mutex_lock(&demo_mutex);
if (atomic_read(&demo_count) <= DEMO_MAX_ENTRIES) {
mutex_unlock(&demo_mutex);
return false;
}
entry = list_first_entry_or_null(&demo_list, struct demo_entry, list);
if (entry) {
list_del_rcu(&entry->list);
atomic_dec(&demo_count);
}
mutex_unlock(&demo_mutex);
if (!entry)
return false;
/*
* The entry is unreachable from demo_list, but a reader that
* loaded it before the removal may still be using it. The
* callback runs after a grace period, so the entry stays valid
* until every such reader has finished.
*/
call_rcu(&entry->rcu, demo_entry_free_rcu);
return true;
}
static int demo_reader_fn(void *arg)
{
while (!kthread_should_stop()) {
struct demo_entry *entry;
u64 local = 0;
rcu_read_lock();
list_for_each_entry_rcu(entry, &demo_list, list)
local += entry->value;
rcu_read_unlock();
atomic64_add(local, &demo_sum);
usleep_range(1000, 2000); /* outside the RCU section */
}
return 0;
}
static void __exit demo_exit(void)
{
struct demo_entry *entry, *tmp;
/*
* The reader and writer kthreads have already been stopped.
* Wait for readers that were still in a section when they
* stopped, then for callbacks queued before this point.
*/
synchronize_rcu();
rcu_barrier();
mutex_lock(&demo_mutex);
list_for_each_entry_safe(entry, tmp, &demo_list, list) {
list_del_rcu(&entry->list);
kfree(entry);
}
mutex_unlock(&demo_mutex);
}
The reader calls usleep_range() outside the RCU section. Sleeping inside a classic RCU reader is illegal because the grace period is waiting for it and a sleeping task can delay it indefinitely. If the reader needed to sleep while holding a reference to an entry, it would use SRCU (Section 11) or take a reference count before leaving the section.
9.2 The Writer’s Lifecycle
The writer has four phases, each with a rule.
Allocate and initialize. kzalloc() returns memory no reader can reach. seq, value, and any other fields are set before publication. No reader can see any of this.
Publish. list_add_tail_rcu() release-stores the previous tail’s next. The mutex is not for readers; it is for other writers. Without it, two concurrent adds could both read head->prev and corrupt the list.
Remove. list_del_rcu() unlinks the head and leaves its forward pointer intact. The unlink is atomic with respect to readers: a reader sees either the old head or the new one, never a half-updated link.
Reclaim. call_rcu() queues the entry’s head. The callback runs after a grace period that started after the removal, so every reader that could have loaded the entry has finished. The callback is small, does not sleep, and only calls kfree().
The ordering between removal and reclamation is the one that matters:
1
2
list_del_rcu(&entry->list); /* unreachable */
call_rcu(&entry->rcu, free_entry); /* deferred free */
Reversing them is a real bug: the grace period could end before the removal, and a reader that started after the grace period could still find the entry in the list, then use it after it is freed. The callback is invoked after a grace period that begins at the call_rcu() call, not at some later point. “Pre-existing” means readers active at the call; a reader that starts between the call and the removal is not covered.
The exit path stops the kthreads first, then calls synchronize_rcu() for readers still in a section, then rcu_barrier() for callbacks queued before the stop, then frees the remaining list. The barrier is mandatory here because the callback is module-local: without it, an entry could still be pending when the module text is unmapped. The final list_for_each_entry_safe() is safe because the list is quiescent — no readers can start and no callbacks are pending — so list_del_rcu() plus direct kfree() is fine.
9.3 One Timeline: Four Cases
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
┌─ 1. correct removal and reclamation ───────────────────────────────────┐
│ reader CPU │ writer CPU │
│ ────────────────────────────────────── │ ───────────────────────────── │
│ rcu_read_lock() │ │
│ pos = head->next ──▶ A │ │
│ pos = A->next ──▶ B │ │
│ │ mutex_lock │
│ │ list_del_rcu(B) │
│ │ prev->next = C │
│ │ C->prev = prev │
│ │ B->prev = POISON2 │
│ │ mutex_unlock │
│ │ call_rcu(&B->rcu, free) │
│ pos = B->next ──▶ C │ (B->next still valid) │
│ pos = C->next ──▶ D │ │
│ ... │ │
│ rcu_read_unlock() │ │
│ │ grace period ends │
│ │ free(B) │
└────────────────────────────────────────────────────────────────────────┘
┌─ 2. premature free ────────────────────────────────────────────────────┐
│ reader CPU │ writer CPU │
│ ────────────────────────────────────── │ ───────────────────────────── │
│ rcu_read_lock() │ │
│ pos = A │ │
│ pos = B │ │
│ │ list_del_rcu(B) │
│ │ kfree(B) <-- wrong │
│ pos = B->next ──▶ ??? │ (B may be reused) │
└────────────────────────────────────────────────────────────────────────┘
┌─ 3. list_del() instead of list_del_rcu() ──────────────────────────────┐
│ reader CPU │ writer CPU │
│ ────────────────────────────────────── │ ───────────────────────────── │
│ rcu_read_lock() │ │
│ pos = A │ │
│ pos = B │ │
│ │ list_del(B) │
│ │ prev->next = C │
│ │ C->prev = prev │
│ │ B->next = POISON1 │
│ │ B->prev = POISON2 │
│ pos = B->next ──▶ POISON1 │ │
│ ──▶ fault │ │
└────────────────────────────────────────────────────────────────────────┘
┌─ 4. publication ───────────────────────────────────────────────────────┐
│ writer CPU │ reader CPU │
│ ────────────────────────────────────── │ ───────────────────────────── │
│ entry = kzalloc() │ │
│ entry->seq = ... │ │
│ entry->value = ... │ │
│ │ rcu_read_lock() │
│ │ pos = head->next │
│ mutex_lock │ │
│ list_add_tail_rcu(entry, head) │ │
│ entry->next = head │ │
│ entry->prev = head->prev │ │
│ stlr head->prev->next, entry │ │
│ head->prev = entry │ │
│ mutex_unlock │ │
│ │ pos = entry │
│ │ sum += entry->value │
│ │ pos = entry->next = head │
│ │ rcu_read_unlock() │
└────────────────────────────────────────────────────────────────────────┘
In case 1 the reader is on B when the writer removes it. The removal changes the predecessor’s next and C->prev, but not B->next. The reader advances to C and continues. The grace period starts after removal and ends after rcu_read_unlock(), so free(B) cannot run while the reader still uses B.
In case 2 the writer frees immediately. The memory may be reused, so B->next may point anywhere; the reader can fault, read corrupted data, or silently follow a pointer into an unrelated object. This is the classic use-after-free RCU is designed to prevent, and the only fix is to defer the free.
In case 3 the grace period is irrelevant: the reader faults before reaching rcu_read_unlock(), because list_del() poisoned the forward pointer. Replacing list_del_rcu() with list_del() “because we are going to wait anyway” is wrong.
In case 4 the reader either sees the entry or does not, depending on whether it loaded the previous tail’s next before or after the stlr. If it sees the entry, the release store guarantees that all fields are visible. It never sees a partially initialized entry.
9.4 What the Example Demonstrates
| Module construct | Rule it demonstrates |
|---|---|
kzalloc() before list_add_tail_rcu() | Initialize before publishing |
list_add_tail_rcu() | Release-store publication |
demo_mutex around mutations | RCU does not serialize writers |
list_for_each_entry_rcu() | Reader traversal with READ_ONCE() and dependency ordering |
rcu_read_lock() / rcu_read_unlock() | Read-side critical section |
list_del_rcu() | Do not poison the forward pointer |
call_rcu() after list_del_rcu() | Defer reclamation until after a grace period |
synchronize_rcu() in exit | Blocking grace period from process context |
rcu_barrier() in exit | Wait for in-flight callbacks before unload |
usleep_range() outside the section | Sleeping is illegal inside classic RCU |
The example also shows why the list is bounded. An unbounded RCU-protected list is a memory leak with extra steps: entries are added faster than they are removed, the list grows without limit, and every reader’s traversal slows. DEMO_MAX_ENTRIES is a simple back-pressure mechanism. Real structures use more sophisticated policies, but the principle is the same: an RCU-protected structure still needs a lifecycle policy for its entries.
The read side and the write side are almost independent. Readers do not know a writer exists; they only know they are in a section and that the list is RCU-protected. The writer does not know which readers are active; it only knows to remove before waiting and wait before freeing. The grace period is the only communication, and it is deliberately implicit. That decoupling is what makes RCU scale, and it is also what makes the ordering rules easy to get wrong.
10. Contexts, Nesting, and Sleeping
The same three-line reader appears in drivers, filesystems, and the scheduler. What it means depends on the build and the context. In a non-preemptible kernel it disables preemption. In PREEMPT_RCU it increments a task-local counter and allows preemption. Both forbid an explicit sleep, for different reasons. In an interrupt handler it nests inside whatever the CPU was doing; in an NMI it may not be legal at all if RCU is not watching. Most RCU bugs that survive compilation are context bugs: a reader that sleeps, a section entered and exited in different contexts, or a callback assuming process context it does not have.
10.1 Nesting Rules
Sections nest. A function may call another that also takes rcu_read_lock(), and an interrupt may arrive while a task is inside a section and take its own.
In a non-preemptible build, the preemption count is the nesting count: two locks increment it twice, and only the second unlock makes the task preemptible again. In PREEMPT_RCU, current->rcu_read_lock_nesting is explicit; the matching unlock decrements it and invokes the expensive rcu_read_unlock_special() path only when the result reaches zero. The compiler barriers around the decrement prevent critical-section accesses from moving past the exit.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
task context relative depth
──────────── ──────────────
rcu_read_lock() 1
│
├── rcu_read_lock() 2
│ │
│ └── rcu_read_unlock() 1
│
└── rcu_read_unlock() 0
│
└── outermost unlock:
preempt_enable() (non-preempt)
or rcu_read_unlock_special() (PREEMPT_RCU)
interrupt nesting:
task: rcu_read_lock() ─────────────────────────────▶ rcu_read_unlock()
│
IRQ: ├── rcu_read_lock() ──▶ rcu_read_unlock()
│
└── the IRQ's unlock ends only its own section
The depths are relative. In a non-preemptible build the preemption counter also contains softirq and interrupt-disable bits, so only the delta matters; in PREEMPT_RCU the task-local counter tracks only reader nesting. Only the transition to relative depth zero ends the task’s reader. An interrupt that nests inside the section temporarily raises the depth and lowers it again, but the task remains a reader until its own outermost unlock.
The rules:
- Every
rcu_read_lock()needs a matching unlock in the same execution context. - The unlock order is the reverse of the lock order.
- A read-side section may contain other read-side sections, including ones acquired by interrupt handlers.
- A section may not be entered in process context and exited in an interrupt handler, or entered in one task and exited in another. The counter belongs to the task.
- A section must not substitute for a lock protecting an invariant. Nesting gives a longer lifetime window, not mutual exclusion.
The fourth rule is structural, not diagnostic. A workqueue that calls rcu_read_unlock() for a lock taken by another task may underflow the nesting count, release a section that was never taken, or leave the original task a reader forever. Lockdep catches the lockdep side, but the lifetime bug remains.
rcu_read_lock_bh(), rcu_read_lock_sched(), and SRCU have the same same-context requirement. SRCU goes further: the value returned by srcu_read_lock() must be passed unchanged to the matching srcu_read_unlock(), and both calls must be in the same context.
10.2 Non-Preemptible RCU
A non-preemptible build is the simplest case. rcu_read_lock() disables preemption: with CONFIG_PREEMPT_COUNT it is a per-CPU counter increment plus a compiler barrier; without it, only a compiler barrier. The invariant is the same: while the section is active, the kernel will not involuntarily switch the task out.
That invariant makes detection cheap. If a CPU reports a context switch and preemption cannot happen inside a read-side section, the switched-out task cannot have been a reader. The CPU reports a quiescent state without inspecting pointer state. The entire read side reduces to “do not let this CPU be preempted”, and the grace-period machinery only observes the CPU.
The subtle point is that preempt_disable() is not a sleep inhibitor. On PREEMPT_NONE, preemption is already disabled almost everywhere, so rcu_read_lock() may compile to nothing. A call to schedule() inside the section would still switch the task out. The scheduler would report a context switch, RCU would treat it as quiescent, and a grace period could end while the sleeping task still holds a pointer. The prohibition is a protocol rule, not a property of the instruction sequence:
In non-preemptible RCU implementations (pure
TREE_RCUandTINY_RCU), it is illegal to block while in an RCU read-side critical section.
See include/linux/rcupdate.h. The non-preemptible reader is also the one that benefits most from RCU’s design: the read-side cost is a per-CPU count or compiler barrier, not a shared cache line, atomic instruction, or retry.
10.3 PREEMPT_RCU
PREEMPT_RCU exists because a non-preemptible section is a latency hazard. If a high-priority task needs the CPU while a low-priority task is inside a long section, it must wait. PREEMPT_RCU lets the reader be preempted while tracking the preempted task so the grace period still waits for it.
The read-side counter lives in struct task_struct as current->rcu_read_lock_nesting. The increment is task-local, so a reader can migrate between CPUs and be preempted at any point. The grace-period machinery can no longer infer “this CPU switched, therefore no reader”; it must ask whether the switched-out task was in a section.
rcu_note_context_switch() answers that. If the task is a reader, it is linked into the leaf rcu_node’s blkd_tasks list and marked blocked. The grace period cannot end until the tasks that predate it leave their sections. When the task runs again and calls rcu_read_unlock(), the outermost unlock notices rcu_read_unlock_special, removes it from the list, and, if it was blocking the current grace period, reports the quiescent state.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
READER RUNNING
current->rcu_read_lock_nesting > 0
│
│ scheduler preempts the task
▼
PREEMPTED READER
rcu_note_context_switch(preempt=true)
│
├── nesting == 0 ──▶ rcu_qs(): CPU is quiescent
│
└── nesting > 0
│
▼
queue on leaf rnp->blkd_tasks
set rcu_read_unlock_special.blocked
│
│ task is scheduled again
▼
READER RUNNING AGAIN
│
│ outermost rcu_read_unlock()
▼
dequeue from blkd_tasks
│
├── was blocking current GP ──▶ report QS
└── not blocking ─────────────▶ no extra QS
The branch at the context switch is the important one. A task with depth zero has left its reader, so the CPU can report immediately. A task with non-zero depth must be remembered; the CPU may report its own quiescent state, but the grace period cannot end until the task reaches its outermost unlock.
The WARN_ONCE on a voluntary context switch distinguishes preemption from blocking. A preempted task did not choose to leave the CPU; the scheduler took it away, and RCU recorded that. A task that calls schedule() or sleeps on a waitqueue chose to block while holding a reference, which is illegal in a PREEMPT_RCU section even though the implementation could queue it. Allowing arbitrary blocking creates deadlocks RCU cannot resolve: a task could sleep waiting for a mutex held by the writer waiting in synchronize_rcu() for that very task. The grace period waits for the reader, the reader waits for the writer, and the writer waits for the grace period. PREEMPT_RCU breaks the cycle by declaring the block illegal.
PREEMPT_RT narrows the exception: a reader may block while acquiring a spinlock that has been converted to a priority-inheritance mutex, because that is how RT implements spinlocks. It may not sleep on an arbitrary waitqueue while holding an RCU reference.
CONFIG_RCU_BOOST can raise the priority of a preempted reader that has blocked a grace period for too long. It is a mitigation for priority inversion, not a licence to sleep; it makes the reader run sooner so it can finish and release the grace period.
Deferred quiescent states are the last detail. If rcu_read_unlock() is called with interrupts or bottom halves disabled, the unlock may not be able to take the rcu_node lock safely. rcu_read_unlock_special() then arranges for the quiescent state to be reported later through a softirq, IRQ work, or the scheduler. That is why rcu_read_unlock() is described as immune from deadlock in almost all situations: the slow path avoids taking a sleeping lock in atomic context.
10.4 Interrupts, Softirqs, and NMI
rcu_read_lock() does not disable interrupts. A hardirq can arrive in the middle of a section and take its own rcu_read_lock(). The outer reader remains active, and the grace period waits for both. That nesting is what lets interrupt handlers use RCU without a special API.
There is also implicit protection. Regions in which interrupts, softirqs, or preemption are disabled are themselves RCU read-side critical sections for synchronize_rcu() and call_rcu():
Both
synchronize_rcu()andcall_rcu()also wait for regions of code with preemption disabled, including regions of code with interrupts or softirqs disabled.
See include/linux/rcupdate.h. This includes hardware interrupt handlers, softirq handlers, and NMI handlers. A hardirq runs with interrupts disabled, so even without rcu_read_lock() a grace period that starts while it runs cannot end until it exits. That is why an NMI handler can use rcu_dereference_sched() without an explicit lock, and why synchronize_rcu() can wait for an NMI handler to finish before freeing its data:
1
2
3
unset_nmi_callback();
synchronize_rcu();
kfree(my_nmi_data);
See Documentation/RCU/NMI-RCU.rst.
That does not make every RCU API legal in every NMI. rcu_read_lock() checks rcu_is_watching(), which is false in deep idle, in parts of kernel entry and exit, and on offline CPUs. An NMI that interrupts such a state cannot assume a normal rcu_read_lock() is valid. The NMI-safe APIs, and careful use of implicit preemption-disabled protection, exist for that case.
rcu_read_lock_bh() disables bottom halves and takes the reader; rcu_read_lock_sched() disables preemption and takes the reader. Since v5.0 the two share the same grace period, so the RCU_BH and RCU_SCHED lockdep classes are about documentation and diagnostics rather than separate GP flavors. The unlock must occur in the same context, and neither wrapper makes sleeping legal. For NMI-safe SRCU there is srcu_read_lock_nmisafe(), which uses atomic per-CPU operations because the normal SRCU counter update is not NMI-safe.
The practical rule for interrupt contexts:
| Context | Normal rcu_read_lock() | What it protects | Notes |
|---|---|---|---|
| Process, non-preemptible kernel | Yes | Until outermost unlock | Preemption disabled; no sleeping |
Process, PREEMPT_RCU | Yes | Until outermost unlock | May be preempted; no explicit sleep |
| Hardirq | Yes | Handler and interrupted reader | Interrupts already disabled |
| Softirq | Yes | Handler and interrupted reader | Often already bh-disabled |
| NMI, RCU watching | Possible | Handler and interrupted context | Must not block; use NMI-safe APIs when unsure |
| NMI, RCU not watching | No | Not a valid reader | Use srcu_read_lock_nmisafe() or implicit protection |
| Idle | No | — | rcu_is_watching() is false |
10.5 Can a Reader Sleep?
The short answer: no for classic RCU, no for PREEMPT_RCU in the sense of an explicit block, yes for SRCU, and “only in the narrow PREEMPT_RT spinlock case” for PREEMPT_RT.
For non-preemptible RCU, a sleeping reader lets the CPU report a context switch, which the machinery treats as evidence that the CPU is no longer a reader. The task still holds the pointer, but the CPU has no reason to wait, and the object can be freed underneath it. This is why rcu_read_lock() is banned around copy_to_user(), kmalloc(GFP_KERNEL), mutex acquisition, and anything else that can block.
For PREEMPT_RCU, preemption is fine because the scheduler records the preempted task as a blocked reader. An explicit sleep is still illegal because it creates an unbounded dependency between the reader and the grace period. The reader might wait for a resource the writer needs, or the writer might wait for the reader to release a resource. The kernel forbids the cycle rather than trying to detect it.
For PREEMPT_RT, spinlocks become sleeping priority-inheritance mutexes, so a reader acquiring such a lock may block without leaving the section. That is a property of the RT locking model, not permission to call msleep() inside rcu_read_lock().
When a reader genuinely needs to sleep, there are two standard solutions. The first is SRCU, covered in Section 11. The second is to leave the RCU section with a reference count:
1
2
3
4
5
6
7
8
9
10
11
rcu_read_lock();
p = rcu_dereference(global_ptr);
if (!p || !get_ref(p)) { /* acquire a lifetime reference */
rcu_read_unlock();
return -ENOENT;
}
rcu_read_unlock();
/* p is now safe to use across sleeps */
do_something_slow(p);
put_ref(p);
The reference count, not RCU, now protects the object. RCU only protected the lookup. The acquisition must be safe against concurrent free; helpers such as get_cred_rcu() use atomic_long_inc_not_zero(), and a zero count means the object is already on its way out, so the caller retries the lookup or reports failure. That is a reference-count retry, not an RCU retry.
A third option is to copy the data out while in the section and use the copy afterward. That works for small, fixed-size values, not for pointers into the object, because the copy would contain a pointer whose lifetime is not protected.
10.6 Context Selection Matrix
| Requirement | Recommended API | Can the reader sleep? | Can it be preempted? | Grace period waits for | Main cost |
|---|---|---|---|---|---|
| Short process-context read, no sleep | rcu_read_lock() | No | Yes in PREEMPT_RCU, no otherwise | Outer section | Preempt count or task-local counter |
| Read in softirq or bh-disabled code | rcu_read_lock_bh() | No | No while bh disabled | bh-disabled region | local_bh_disable() |
| Read with preemption already disabled | rcu_read_lock_sched() | No | No | Preemption-disabled region | Preempt count |
| Read in hardirq | rcu_read_lock() or implicit | No | N/A | Handler | Interrupt-disabled region |
| Read in NMI | NMI-safe API or implicit | No | N/A | Handler | Atomic counter for NMI-safe SRCU |
| Reader must sleep | SRCU | Yes | Yes | SRCU read section | Per-CPU counters and smp_mb() |
| Reader must sleep, tracing only | RCU Tasks Trace | Yes | Yes | Trace reader | SRCU-fast plus task nesting |
| Code patching, trampolines | RCU Tasks / Tasks Rude | No explicit reader | N/A | Voluntary context switch or IPI | IPIs and scheduling |
| Reader needs a stable multi-field snapshot | seqlock or mutex, not RCU | Depends | Depends | — | Retry or blocking |
The last row is not an RCU variant. It is a reminder that RCU is not a consistency mechanism. If the reader must see two fields updated together, RCU alone cannot provide that. The writer can publish a new object containing both fields, but the reader must load the pointer once and use that object for both. If the object is mutable, the reader needs a lock, a seqlock, or an immutable replacement.
The distinction between “can be preempted” and “can sleep” is the important column. PREEMPT_RCU is preemptible, which suits low-latency kernels, but it is not sleepable. PREEMPT_RT allows a narrow form of blocking through PI spinlocks, but it is not general sleepable RCU. SRCU is the API whose contract explicitly includes sleeping readers, and it pays for that with heavier read-side operations and a separate grace-period domain.
11. Sleepable RCU (SRCU)
Classic RCU is built around a read-side section that cannot block. That is unacceptable for a filesystem performing I/O while holding a reference to a superblock, a driver waiting for firmware, or a network path allocating with GFP_KERNEL. **Sleepable RCU** (SRCU) allows those readers.
SRCU is not a drop-in replacement for RCU. It has its own struct srcu_struct, read-side API, grace-period machinery, and rules. The most important difference is that each SRCU domain has an independent grace period: synchronize_srcu(&ss) waits only for readers of ss, not for every SRCU domain or classic RCU. That independence makes SRCU usable in subsystems that cannot afford a global grace period, and it makes it a scalability tool in its own right.
11.1 Why SRCU Exists
The classic contract has two parts: readers are cheap, and readers cannot block. SRCU keeps the first as much as it can and relaxes the second. __A reader calls srcu_read_lock(&ss), receives an integer index, and later calls srcu_read_unlock(&ss, idx). In between it may sleep, take mutexes, perform I/O, or be preempted arbitrarily. The writer calls synchronize_srcu(&ss) or call_srcu(&ss, ...), and the grace period waits for readers active in that domain.__
The price is on the read side. Classic RCU readers do not touch a shared counter; SRCU readers increment per-CPU lock and unlock counters and execute full barriers to order the counter updates against data accesses. The counters are per-CPU, so there is no global cache-line hotspot, but an SRCU section is still more expensive than an RCU section.
SRCU also has a different failure mode. Because readers can sleep, one reader can delay a grace period for a long time. The implementation has adaptive waiting and expedited modes, but it cannot make a sleeping reader finish. SRCU has no CPU stall warnings; a stuck reader is a hang, not a stall splat. That makes SRCU a poor choice for code that cannot tolerate an unbounded wait unless the domain’s readers are carefully bounded.
The canonical use case is a reader that holds a reference across a blocking operation:
1
2
3
4
5
6
7
int idx = srcu_read_lock(&my_srcu);
p = srcu_dereference(global_ptr, &my_srcu);
if (p) {
/* May sleep, allocate, or wait for I/O. */
do_slow_work(p);
}
srcu_read_unlock(&my_srcu, idx);
The writer replaces global_ptr under its update lock, waits with synchronize_srcu(), then frees the old object. The reader’s sleep does not break the grace period because SRCU tracks the reader through the counter, not through CPU preemption state.
11.2 Data Structures
An SRCU domain is represented by struct srcu_struct. The read side needs only srcu_ctrp, which points at one of two per-CPU counter arrays. The update side needs srcu_sup, which holds the grace-period sequence, the callback list, the combining tree, and the locks that serialize grace-period processing. Keeping the halves separate is a cache-layout decision: readers touch srcu_ctrp and their per-CPU counters; the writer touches update-side state.
The per-CPU read state contains two sets of counters:
1
2
3
4
5
6
7
8
9
10
struct srcu_ctr {
atomic_long_t srcu_locks;
atomic_long_t srcu_unlocks;
};
struct srcu_data {
struct srcu_ctr srcu_ctrs[2];
int srcu_reader_flavor;
...
};
The two elements of srcu_ctrs[] are the two ranks (or indices). At any moment srcu_ctrp points at one of them, and new readers increment the counters in that rank. The other rank is being drained by the current grace period. The writer flips srcu_ctrp when it has established that the old rank has no readers. That flip is the heart of the algorithm.
The update side also has a combining tree of struct srcu_node objects, used for callback management and grace-period aggregation. Readers never walk it; the writer does when it needs to know which CPUs have callbacks to advance.
SRCU structures can be static or dynamic. DEFINE_SRCU() and DEFINE_STATIC_SRCU() create a statically initialized domain; init_srcu_struct() initializes a dynamic one; cleanup_srcu_struct() releases it. A static domain must not be passed to init_srcu_struct() or cleanup_srcu_struct(). A dynamic domain must be cleaned up after all readers and callbacks are gone, or its per-CPU allocations leak.
11.3 Read Side
The read-side API is small. srcu_read_lock() validates the flavor, calls __srcu_read_lock(), and acquires the domain’s lockdep map. The real work loads ssp->srcu_ctrp, increments the current CPU’s lock counter for that rank, executes the B barrier, and returns an index that encodes the rank:
1
2
3
4
5
6
7
8
int __srcu_read_lock(struct srcu_struct *ssp)
{
struct srcu_ctr __percpu *scp = READ_ONCE(ssp->srcu_ctrp);
this_cpu_inc(scp->srcu_locks.counter);
smp_mb(); /* B: avoid leaking the critical section */
return __srcu_ptr_to_ctr(ssp, scp);
}
The B barrier prevents the reader’s subsequent accesses from being reordered before the lock count becomes visible. Without it, a writer could see the data accesses but not the lock count, conclude the rank is empty, and free the object while the reader is using it.
The unlock executes the C barrier, then increments the unlock counter for the index returned by the lock:
1
2
3
4
5
void __srcu_read_unlock(struct srcu_struct *ssp, int idx)
{
smp_mb(); /* C: avoid leaking the critical section */
this_cpu_inc(__srcu_ctr_to_ptr(ssp, idx)->srcu_unlocks.counter);
}
The C barrier prevents the reader’s accesses from being reordered after the unlock count. The unlock charges the rank that was returned by the lock, on whatever CPU it runs; it need not be the same CPU, because the writer may have flipped srcu_ctrp by then. That is why the index must be preserved. The public wrapper warns if idx has any bit other than the low one set, and releases the lockdep map.
The read side is nestable. Each call increments a counter and returns an index; if a grace period flips the pointer between two nested locks, the indices differ and each unlock is charged to the correct rank.
A reader may sleep, but it may not wait on an SRCU grace period for the same domain:
However, it is illegal to call anything that waits on an SRCU grace period for the same
srcu_struct, whether directly or indirectly.
See include/linux/srcu.h. synchronize_srcu(&ss) inside a reader of &ss is a self-deadlock: the writer waits for the reader, and the reader is the writer. The same applies to acquiring a mutex held by a thread waiting on the same domain. Waiting on a different domain is allowed, which is why SRCU domains are sometimes layered.
11.4 Grace Period and Index Flip
The SRCU grace period is a two-rank scan. The goal is to prove that every reader active when the grace period started has incremented an unlock counter. The writer cannot simply read the lock counters once, because a reader might have loaded the old srcu_ctrp and then been delayed before incrementing. Two ranks and full barriers close that window.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
state: srcu_ctrp ──▶ rank A, rank B empty
│
│ writer starts a grace period
▼
SCAN1: check the inactive rank (B) == 0
│ must be empty before B can be reused
▼
FLIP: srcu_ctrp ──▶ rank B
│ new readers use B
│ old readers may still be entering A
▼
SCAN2: check the old rank (A) == 0
│ locks == unlocks for every CPU
▼
GP END: A is drained; the next GP will reuse it
SCAN1 is the safety check for rank reuse. SCAN2 drains the readers that were active at the start of this grace period. The flip between them separates readers that must be waited for from readers that arrived after the grace period began.
The flip itself performs an smp_mb() (E), writes srcu_ctrp, and performs another smp_mb() (D). New readers that load the pointer after the flip use the new rank. Readers that loaded the old pointer before the flip may still increment the old rank after the flip, which is why a second scan is needed.
The check compares sums:
1
2
3
unlocks = srcu_readers_unlock_idx(ssp, idx);
smp_mb(); /* A */
return srcu_readers_lock_idx(ssp, idx, did_gp, unlocks);
The writer first sums the unlock counters, executes a full barrier (A), then sums the lock counters. If the sums are equal, every lock in that rank has a matching unlock. The barrier prevents the writer from seeing an unlock that has not yet been paired with a visible lock, or vice versa.
The equality test has a subtlety: a reader may have loaded srcu_ctrp but not yet incremented its lock counter. If the writer scans before that increment, the sums can still be equal even though the reader is about to enter. The two-rank protocol handles it. If the reader loaded the old rank before the flip, its increment lands in the old rank and SCAN2 sees it. If it loaded the new rank, it started after the flip and need not be waited for by this grace period. A delayed reader that loaded an even older rank is caught by SCAN1 before that rank is reused.
1
2
3
4
5
6
7
8
9
10
11
initial state: srcu_ctrp ──▶ ctr[0]
readers: R0 uses ctr[0]
writer: SCAN1 checks ctr[1] (inactive) == 0
flip: srcu_ctrp ──▶ ctr[1]
new readers R1 use ctr[1]
SCAN2 checks ctr[0] (old) == 0
grace period ends
old readers R0 may still be sleeping, but their unlocks
are counted in ctr[0] before SCAN2 accepts the GP.
try_check_zero() spins briefly and then backs off to sleeping waits. If the sums do not match, it returns false and the grace-period machinery retries later. That is why synchronize_srcu() can be used from process context: the fast path spins briefly, the slow path sleeps, and a sleeping reader simply makes the writer sleep as well.
SRCU grace periods are not global. Each domain has its own sequence, pointer, ranks, and callback list, so a writer waiting on one domain does not wait for readers of another. The isolation is deliberate: a subsystem chooses the readers it actually needs to wait for instead of paying for every RCU reader in the system.
11.5 API, Rules, and Costs
| Operation | Waits for | Can sleep? | Typical use |
|---|---|---|---|
srcu_read_lock() / srcu_read_unlock() | — | Yes | Reader that may block |
synchronize_srcu() | Pre-existing readers of one domain | Yes | Writer that can block before freeing |
call_srcu() | Queues a callback for after one domain’s GP | No; callback runs later | Writer that cannot block |
srcu_barrier() | All pending call_srcu() callbacks on the domain | Yes | Teardown, module unload |
synchronize_srcu_expedited() | Same as synchronize_srcu(), more aggressive | Yes, but spin-heavy | Low-latency update |
cleanup_srcu_struct() | No readers, no callbacks, no pending work | Yes | Destroy a dynamic domain |
The important rules:
- Use the matching domain. Every lock, unlock, dereference,
synchronize_srcu(),call_srcu(), andsrcu_barrier()must use the samestruct srcu_struct. - Preserve the index. The value returned by
srcu_read_lock()must be passed unchanged tosrcu_read_unlock(). - Keep lock and unlock in the same context. A reader may sleep but may not hand the unlock to another task or an interrupt handler without a matching lock.
- Do not wait on the same domain inside a reader. Waiting on a different domain is allowed.
- Do not sleep in the callback.
call_srcu()callbacks run with bh disabled; use a workqueue for sleepable cleanup. - Call
srcu_barrier()beforecleanup_srcu_struct(). - Use the NMI-safe API in NMI.
srcu_read_lock_nmisafe()uses atomic operations; mixing flavors on the same domain is prohibited. - Bound the readers. A sleeping SRCU reader can delay the grace period indefinitely, and there is no stall detector.
- Do not use SRCU as a general mutex. It protects lifetime, not writer serialization or reader mutual exclusion.
- Prefer classic RCU when the reader cannot sleep. The extra barriers and separate grace period are justified only when the reader must block.
A cost comparison:
| Property | Classic RCU | SRCU |
|---|---|---|
| Reader may sleep | No | Yes |
| Reader may be preempted | Yes in PREEMPT_RCU | Yes |
| Read-side atomic operations | None (task-local counter) | Per-CPU counter increments |
| Read-side memory barrier | None on AArch64 in the common case | dmb ish on entry and exit |
| Grace-period scope | Global | Per srcu_struct |
| Writer can block | synchronize_rcu() does | synchronize_srcu() does |
| Async callback | call_rcu() | call_srcu() |
| Callback context | Softirq | Process, bh disabled |
| Barrier for callbacks | rcu_barrier() | srcu_barrier() |
| Stall detector | Yes | No |
| NMI-safe variant | Implicit / NMI-safe APIs | srcu_read_lock_nmisafe() |
| Typical use | Pointer-based read-mostly data | Readers that block |
The last row is the one to remember. If the reader can complete without sleeping, classic RCU is almost always better. If it must sleep, SRCU is the mechanism the kernel provides, and its extra rules are the price of that capability.
12. Tiny RCU and the Flavors
The RCU API is stable across configurations, but the implementation behind it is not. A uniprocessor embedded board and a 256-core server expose the same rcu_read_lock(), synchronize_rcu(), and call_rcu() interfaces, but the cost of a reader, the meaning of a quiescent state, and the callback path differ. This section separates the implementations from the reader-context variants and the specialized flavors.
12.1 Tiny RCU
Tiny RCU is the uniprocessor implementation that does not need preemptible RCU. Its Kconfig entry makes the scope explicit: default y if !PREEMPT_RCU && !SMP. There is no tree, no per-CPU rcu_data array, no grace-period kthread, and no quiescent-state bitmap. The entire callback and grace-period state is a single global structure with a callback list, a tail pointer for enqueueing, a “done” boundary, and a sequence counter.
The read side is still an RCU section, but the implementation has almost nothing to do. In a non-preemptible build it is preempt_disable()/preempt_enable(), exactly as in non-preemptible Tree RCU; on a UP kernel with no preemption counting it can collapse to a compiler barrier. The semantic point is not the instruction count: a legal reader cannot block and cannot migrate, because there is only one CPU.
The grace period is radically different. synchronize_rcu() does not wait for other CPUs, because there are none. It checks that the caller is not already in a read-side section, disables preemption, advances the grace-period counter, and returns. A legal call cannot be inside a section, so on UP the caller itself is a quiescent state.
Callbacks are still deferred. call_rcu() appends the head to the global list with interrupts disabled. rcu_qs() moves the “done” boundary to the current tail, making every earlier callback eligible, and raises RCU_SOFTIRQ so rcu_process_callbacks() invokes them. The scheduling-clock interrupt calls rcu_qs() when it observes a return to user mode. rcu_barrier() is simply wait_rcu_gp(call_rcu_hurry): the barrier callback cannot run until every earlier callback on the single list has been processed.
Tiny RCU is an excellent fit for a small UP system: tiny footprint, short code paths. It is a poor fit for SMP and is not selected when PREEMPT_RCU is enabled. A uniprocessor AArch64 build with PREEMPT_NONE can use it, but any SMP AArch64 kernel uses Tree RCU regardless of board size. A single global callback list and grace-period counter cannot represent concurrent readers on multiple CPUs.
12.2 Tree RCU
Tree RCU is the SMP implementation. Its name comes from the combining tree of rcu_node structures that aggregates quiescent-state reports instead of making every CPU contend on one global bitmap. The tree also bounds the grace-period kthread’s work per level, which is what lets RCU scale to hundreds or thousands of CPUs.
The state splits into three pieces:
struct rcu_state: the global grace-period sequence, the root of the node tree, the grace-period kthread, and global configuration.struct rcu_node: a group of CPUs. A leaf covers a small range of CPU IDs; an interior node covers the union of its children; the root covers every online CPU.struct rcu_data: per-CPU state, including the callback list, quiescent-state flags,mynode, and local counters.
The tree is built from RCU_FANOUT and RCU_FANOUT_LEAF. On 64-bit the defaults are 64 and 16. A 256-CPU machine has 16 leaves of 16 CPUs and one root. A quiescent state goes to the leaf; when all CPUs under a leaf report, the leaf reports upward; when all leaves report, the root ends the grace period.
The grace-period kthread is the engine: rcu_gp_init() snapshots the online CPUs, initializes qsmask at every node, and records the sequence; the kthread waits for quiescent states, forces them when a CPU is late, and calls rcu_gp_cleanup() when the root mask clears. The per-CPU callback list is segmented so one grace-period completion advances a whole segment. rcu_do_batch() invokes ready callbacks with count and time limits.
Tree RCU is a family of paths around one algorithm: the normal path uses ticks and context switches, the dynticks path handles idle and user-mode CPUs without a tick, the expedited path sends IPIs, and the offloaded path hands callback invocation to kthreads. All share the same rcu_node tree and grace-period sequence.
12.3 Production Choice
| Build | Selected implementation | Why |
|---|---|---|
SMP, PREEMPT_NONE | TREE_RCU, non-preemptible | Multiple CPUs require a tree; readers disable preemption |
SMP, PREEMPT or PREEMPT_DYNAMIC | PREEMPT_RCU, which selects TREE_RCU | Readers may be preempted; task-local nesting is tracked |
SMP, PREEMPT_RT | PREEMPT_RCU plus RT locking | Same tree, with priority boosting and RT spinlocks |
UP, PREEMPT_NONE | TINY_RCU | Smallest footprint; no other CPU to wait for |
UP, PREEMPT | PREEMPT_RCU selects TREE_RCU | Preemptible readers need task tracking even on one CPU |
The practical rule: every production multi-CPU AArch64 system uses Tree RCU, and most use PREEMPT_RCU because they are built with CONFIG_PREEMPT or CONFIG_PREEMPT_DYNAMIC. Tiny RCU appears in uniprocessor firmware, small appliances, and bring-up kernels, not in servers, phones, or desktops.
TREE_RCU is also the base for TREE_SRCU. SRCU has its own per-domain counters and grace-period state, but on SMP it uses Tree SRCU rather than Tiny SRCU. The pairing is deliberate: Tiny RCU goes with Tiny SRCU, Tree RCU with Tree SRCU. Callback offloading and lazy callbacks do not change the implementation; they are policies layered on Tree RCU.
12.4 RCU-bh and RCU-sched
The names RCU-bh and RCU-sched date from when Linux had separate grace-period domains for different reader contexts. RCU-bh was for networking code that could be monopolized by softirqs: a normal grace period could be delayed indefinitely if a CPU spent all its time in softirq context, because the CPU never passed through a context switch or user return. RCU-bh treated local_bh_disable() regions as readers and allowed a grace period to complete without waiting for softirq processing. RCU-sched was for code that disabled preemption or interrupts, including NMI handlers; it treated preempt_disable(), local_irq_disable(), and NMI entry as read-side regions.
Those separate domains no longer exist. Since about v4.20, there is a single RCU flavor: it behaves like the old RCU-sched when PREEMPTION=n and like RCU-preempt when PREEMPTION=y. The old update-side APIs are gone; synchronize_rcu() and call_rcu() serve all reader markers. Anything that disables bottom halves also marks an RCU-bh read-side section, and anything that disables preemption also marks an RCU-sched read-side section.
The reader APIs remain because they document intent, participate in lockdep, and select the right rcu_dereference() variant. rcu_read_lock_bh() disables bottom halves; rcu_read_lock_sched() disables preemption. Both are readers for the unified grace period. The RCU_BH and RCU_SCHED lockdep classes check that the unlock matches the lock and that protected data is accessed under a compatible reader.
The compatibility rule is unchanged: rcu_read_lock_bh() and rcu_read_unlock_bh() must occur in the same context, and likewise for sched. When reading a modern call site, translate rcu_read_lock_bh() to “disable BH and enter an RCU reader” and rcu_read_lock_sched() to “disable preemption and enter an RCU reader”. Do not look for synchronize_rcu_bh() or synchronize_rcu_sched(); those update-side APIs are gone.
12.5 Tasks RCU and Other Flavors
Classic RCU assumes a reader can be identified by an explicit marker or a context the kernel already tracks. Tracing breaks that assumption. A trampoline implementing an ftrace or BPF probe can be entered from arbitrary code, including code with no rcu_read_lock() and where adding one is impossible because the probe must patch the instruction stream. The reader also needs protection for a few instructions before it reaches the trampoline, because those instructions may compute the trampoline address. A normal RCU section cannot express that.
Tasks RCU makes the read-side section implicit and task-based. A grace period waits for every task to pass through a voluntary context switch, a transition to or from user mode, or an idle state. The reader calls nothing. The API is call_rcu_tasks(), synchronize_rcu_tasks(), and rcu_barrier_tasks(). Involuntary preemption is not a Tasks RCU quiescent state, because a task preempted in a trampoline has not left it; the flavor must wait for the task to resume and leave.
Tasks Rude RCU waits for preemption-disabled regions, including regions on CPUs where RCU is not watching, such as deep idle and entry/exit code. It has no explicit readers and forces work on each online CPU, which is effective but disruptive to real-time and battery-powered systems. Its API is essentially synchronize_rcu_tasks_rude(). The implementation can be compiled out on architectures that guarantee noinstr coverage; AArch64 selects ARCH_WANTS_NO_INSTR.
Tasks Trace RCU is the sleepable task-based flavor used by tracing. It combines explicit rcu_read_lock_trace() markers with an SRCU-fast implementation, so readers may sleep and the read side avoids ordinary SRCU’s full barriers on architectures with complete noinstr coverage. The API is rcu_read_lock_trace(), rcu_read_unlock_trace(), call_rcu_tasks_trace(), synchronize_rcu_tasks_trace(), and rcu_barrier_tasks_trace(). On AArch64, ARCH_WANTS_NO_INSTR lets the smp_mb() be compiled out in expert configurations; otherwise the barrier remains.
12.6 Flavor Selection at a Glance
| Flavor | Reader marker | Quiescent states | May sleep? | Primary use |
|---|---|---|---|---|
| Classic RCU | rcu_read_lock() or implicit disabled context | Context switch, user, idle, forced QS | No | Normal pointer-based data |
| RCU-bh | rcu_read_lock_bh() or BH-disabled region | Same unified GP; BH-disabled region is a reader | No | Softirq-heavy networking |
| RCU-sched | rcu_read_lock_sched() or preempt/IRQ-disabled region | Same unified GP; preempt-disabled region is a reader | No | Preemption-disabled code, NMI-adjacent code |
| SRCU | srcu_read_lock() | Domain-specific counters | Yes | Readers that block |
| Tasks RCU | Implicit | Voluntary context switch, user, idle | A voluntary block ends protection | Trampolines and tracing |
| Tasks Rude RCU | Implicit | Forced work on every CPU | N/A, no explicit reader | Preemption-disabled regions including idle |
| Tasks Trace RCU | rcu_read_lock_trace() | Task nesting plus SRCU-fast | Yes | Sleepable tracing readers |
Two final notes prevent overgeneralization. SLAB_TYPESAFE_BY_RCU is not a flavor; it is a slab-cache property that lets a reader continue to access an object while it is freed and reused, with the obligation to validate identity and refcount (Section 13.3). And the task-based flavors are specialized: for ordinary data structures, classic RCU or SRCU remains the right default.
13. Real-World Users
RCU is used wherever a structure is read constantly and changed rarely, and where a reader must not take a lock. The pattern repeats across subsystems: the writer builds a replacement, publishes it with a single ordered store, unlinks the old version, and arranges for the old version to be freed after a grace period. The subsystem’s own mutex serializes writers; readers never see it. The examples below are chosen because each one adds a different lesson.
13.1 Credentials
A task’s credentials — user and group IDs, capabilities, security labels, keyrings — are stored in a credential structure that is treated as immutable once published. Changing credentials does not edit the existing structure. The writer allocates a new one, copies the old values, applies the change, and publishes the result through the task’s credential pointer. Readers obtain the pointer inside an RCU section and use it without a lock, so a system call that checks capabilities does not contend with a concurrent credential change.
Lifetime has two layers. A reader that only needs the credentials for the duration of its RCU section is protected by the grace period alone. A reader that must keep them across a blocking operation takes a reference count while still inside the section, and the final reference release schedules the free through a callback. That is the canonical RCU-plus-refcount shape: RCU makes the lookup safe, and the reference count carries the object beyond the section.
One detail is a useful reminder about accessor choice. The current task’s own credentials are read with the update-side accessor, because only the task itself changes its subjective credentials and there is no concurrent writer to race with. Choosing the stronger reader API everywhere is harmless but obscures the reasoning; choosing the weaker one on a genuinely shared pointer is a bug.
13.2 PIDs
Looking up a task by process ID walks a hash table of PID objects and then resolves the task structure for a given PID type. Both structures are RCU-protected. The lookup runs under a read-side section, and if the caller needs the task beyond that section it takes a reference count before unlocking. A task that is exiting has its PID links removed, but a reader that already found it can still safely inspect it because the object is not freed until the grace period ends.
PID lookup also shows why RCU staleness is acceptable in practice. A reader may observe a task that is in the middle of exiting, or may miss a task that is in the middle of being attached. The kernel does not promise a linearizable snapshot of the task list; it promises that whatever the reader finds stays alive long enough to be examined. Callers that need a stronger guarantee revalidate under the task’s own lock, or accept that the answer was true at some instant during the call.
13.3 File Descriptor Tables
A process’s open files live in a file descriptor table that is replaced wholesale when it grows. The resize path allocates a larger table, copies the existing entries, publishes the new table with an ordered store, and frees the old one after a grace period. A thread performing a lockless lookup — the common case for a system call that only needs to read a file pointer — walks whichever table it loaded and never blocks on the resize. The old table remains valid for the duration of that walk.
A related optimization appears in slab caches that recycle objects. A cache can be marked so that a freed object is returned to the allocator immediately rather than waiting for a grace period, on the condition that readers validate the object’s identity after loading it. The reader might find memory that has already been reused for a different object of the same type; a generation counter, a magic value, or a reference count acquired with a compare-and-increment tells it whether the object is still the one it wanted. This trades a grace period for a validation step, and it is only correct when the validation is genuinely race-free.
13.4 Network Device Names and Aliases
Network devices are found by name on packet transmit and receive paths, in ioctl handlers, and in routing decisions. The name-to-device mapping is therefore read on every packet and changed only by administrative commands such as renaming an interface or adding an alias. The mapping is published as an RCU-protected structure, so the lookup is a read-side section and a pointer walk, with no lock on the fast path. A rename builds a new mapping, publishes it, and retires the old one through a callback.
The lesson here is that the protected object is not always the device itself. Often it is a small name node or alias record that points at the device, and the device lifetime is managed separately by its own reference count. RCU covers the lookup structure; the reference count covers the device. Mixing the two responsibilities is a common source of bugs, because a reader can hold a valid name node whose target is already being unregistered.
13.5 VFS and Networking at Large
The dentry cache, mount tables, routing tables, neighbour entries, netfilter rule sets, and BPF maps all follow the same shape. Readers walk the structure on the hot path with no lock and no retry. Writers serialize among themselves with a subsystem mutex or spinlock, build a replacement where necessary, publish it, and defer reclamation. Garbage collection, timers, and shrinkers act as reclaimers and use callbacks so they do not block on a grace period.
Two patterns recur so often that they are worth naming. The first is copy-and-replace: the writer cannot mutate the object safely, so it allocates a new version containing the change and swaps the pointer. The second is unlink-and-defer: the writer removes a node from a list or hash chain and schedules its free, while readers already on the node finish their traversal using the preserved forward link. Almost every RCU user is a combination of these two, and almost every RCU bug is a violation of one of them.
14. Performance and Scalability
RCU is a performance technique before it is a correctness technique, and the performance argument is lopsided: the read side is nearly free, and the write side pays for it. This section quantifies that asymmetry and identifies the cases where the bill comes due.
14.1 The Reader Fast Path
The read-side cost is a handful of instructions and no shared-memory write. In a non-preemptible kernel the lock and unlock adjust the preemption count in the current task’s thread information, which is a thread-local operation on most architectures. In a preemptible kernel they increment and decrement a counter inside the current task structure. Neither touches a lock word that other CPUs are polling, so readers scale linearly with core count.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
reader fast path
─────────────────────────────────────────────────────────────
rcu_read_lock() preempt count++ or task->nesting++
│ (no atomic, no cache-line write)
▼
p = rcu_dereference(gp) single load; address dependency
│
▼
use p->field ... ordinary loads through the dependency
│
▼
rcu_read_unlock() count--; special path only if it hit zero
and a grace period was blocked on this task
─────────────────────────────────────────────────────────────
cost: a few instructions, no shared write, no retry, no wait
The important property is not the instruction count but the absence of a contended cache line. A reader-writer lock makes every reader write to the lock word, so all cores serialize on that line’s ownership even when the critical section is trivial. RCU readers never do, which is why a read-mostly workload can scale to hundreds of cores with no read-side contention at all. The one exception is the outermost unlock in a preemptible kernel when the task was blocking a grace period; that path takes a lock and is deliberately kept rare.
On AArch64 the common reader path needs no barrier. Publication is ordered by the writer’s release store, and the reader’s dependent loads are ordered by the address dependency. The compiler is kept from breaking the dependency by the single-load accessor, and that is the whole read-side memory-ordering budget.
14.2 The Writer and Grace-Period Cost
A grace period is measured in milliseconds on an idle system and can stretch further under load, because it must wait for every CPU to report and may need to force a quiescent state. A writer that calls the blocking form pays that latency inline. A writer that uses a callback pays it asynchronously but still consumes the same machine time: a wakeup, a tree scan, and possibly an inter-processor interrupt or a forced reschedule.
The consequence is a simple design rule. One grace period can reclaim any number of objects that were all removed before it started, so batching is nearly free and serial waiting is nearly always wrong. A loop that frees one object per grace period turns a cleanup that could share a single wait into N serial waits, and a control plane that calls the blocking form for every configuration change will show up as latency spikes under load. The asynchronous forms exist precisely so that one grace period can be shared.
Expedited grace periods invert the trade. They finish in microseconds by interrupting every CPU, which is attractive for a rare reconfiguration and unacceptable in a loop. They also disturb real-time tasks and can be disabled or rate-limited in production configurations. Use them when a specific operation must complete before returning, not as a default.
14.3 Cache Lines and NUMA
The tree is a cache-line optimization as much as a fanout optimization. With a flat bitmap, every quiescent state would write to one global word and every grace period would invalidate it on every core. With a combining tree, a CPU writes its leaf’s mask, and the root is touched once per group of CPUs. The number of contended operations per grace period grows with the number of nodes, not the number of CPUs.
Callback state is also per-CPU and cache-line separated where it matters. A callback enqueue touches only the local CPU’s list in the common case, and a grace period advances segments locally before the callback is invoked. The global sequence is read-mostly, and the fields that the grace-period kthread polls are placed away from the fields that CPUs update. That layout choice is not cosmetic: false sharing between the callback list and the quiescent-state flags would put the reporting path and the reclaim path back into contention with each other.
On NUMA systems the same reasoning applies one level up. Per-CPU data stays on the local node, the tree node locks are distributed, and offloading can move callback processing to a CPU that is cheap to interrupt. What does not distribute is the grace period itself: it is still a global event, so a writer on one node waits for readers on every node. That is the fundamental scalability limit, and it is why RCU favors structures whose updates are infrequent and whose readers are local.
14.4 Callback Batching and Offloading
Three mechanisms amortize reclamation. Segmented callback lists let one grace-period completion advance an entire segment, so callbacks are classified once rather than scanned individually. The deferred-free path batches objects per CPU and drains them in groups, turning a stream of individual frees into a handful of grace periods. Lazy callbacks go further and delay the grace period itself on idle systems, trading memory retention for energy.
Offloading moves callback invocation off selected CPUs entirely. It is used with full dynticks to let a CPU run a single task without RCU interrupts, at the cost of extra scheduling latency for the kthreads that do the work. The choice is a policy decision, not a correctness one: the same grace period guarantee holds, but the time and place of the free change.
The trade in every case is latency against throughput and energy. A latency-sensitive subsystem uses the hurrying variant of the asynchronous API so that its free is not delayed behind cold work. A battery-powered device with idle cores can afford to wait. Neither choice affects the read side, which is the point: reclamation policy is tunable without touching the readers.
14.5 When RCU Is the Wrong Tool
RCU is wrong when writers are frequent. Every update eventually costs a grace period, and a workload that replaces an object on every packet or every syscall will spend more time in reclamation than in useful work. It is wrong when readers need mutual exclusion rather than lifetime protection: RCU does not stop two writers, does not give a reader a consistent snapshot, and does not keep a removed object reachable. It is wrong when the structure is small and copied cheaply, because a seqlock or a plain lock is simpler and has no reclamation tail.
It is also wrong when the grace period cannot be bounded to the application’s satisfaction. A long-running reader delays every reclamation in the system, and a subsystem that must free memory promptly cannot tolerate an unbounded wait. SRCU narrows the scope to one domain, but a sleeping reader still delays it and there is no stall detector to bail out. Finally, RCU is wrong in code that cannot be preempted or interrupted safely, or that runs before the RCU machinery is initialized; those contexts need explicit synchronization or a different lifetime scheme.
15. Limitations and Comparison with Seqlocks
15.1 Fundamental Limitations
RCU protects object lifetime, and nothing else. It does not serialize writers, so two concurrent updates to the same structure still need a lock. It does not provide a consistent snapshot, so a reader that loads two fields can see values from different versions unless the object is immutable or the fields are read under a stronger mechanism. It does not make a removed object reachable again, and it does not delay the writer’s publication.
The read side has its own constraints. Classic RCU readers may not block, and a reader that sleeps can let a grace period end while it still holds a pointer in a non-preemptible kernel. Readers must stay inside their sections, must use the correct accessor, and must not assume that the object they found is still linked into the structure. None of these rules is enforced by hardware; they are enforced by review, lockdep, and testing.
Reclamation is the cost that never goes away. Memory for an old version is retained until the grace period ends, so a workload with many in-flight updates has a memory footprint proportional to its update rate times the grace-period latency. A grace period is also a global event with no hard upper bound, which is acceptable for a read-mostly data plane and unacceptable for a subsystem that must guarantee forward progress under memory pressure.
15.2 Seqlock vs. RCU
| Property | Sequential lock | RCU |
|---|---|---|
| Read-side cost | Sequence read, data copy, re-validation | Pointer load plus dependency-ordered field loads |
| Reader can be forced to retry | Yes | No |
| Reader can follow pointers safely | No, unless lifetime is protected separately | Yes |
| Writer modifies data in place | Yes, under the sequence protocol | No, for objects readers traverse |
| Reader sees a consistent multi-field snapshot | Yes, after successful validation | No, unless the object is immutable |
| Writer waits before publishing | No | No |
| Writer waits before reclaiming | No | Yes, for a grace period |
| Read-side latency | Unbounded under a write stream | Bounded by the reader’s own work |
| Memory cost | One copy plus a sequence word | Old and new versions coexist until the GP ends |
| Best fit | Small scalar or fixed-size state | Pointer-based, read-mostly structures |
The two are complementary. A seqlock is the right answer when the reader needs a coherent view of a small value that changes often; RCU is the right answer when the reader needs a pointer to stay valid while it walks a structure. A design that needs both — a pointer to an object whose fields change together — should publish a new immutable object and let RCU handle the lifetime, rather than combining a seqlock with a pointer walk.
15.3 Decision Matrix
| Situation | Recommended primitive | Reason |
|---|---|---|
| Read-mostly pointer structure, short sections | RCU | No reader lock, no retry, cheap traversal |
| Reader must sleep or block on I/O | SRCU | Classic RCU forbids blocking |
| Small value updated frequently, reader needs snapshot | Seqlock | Retry gives a coherent view without writer blocking |
| Writers must exclude each other | Mutex or spinlock plus RCU for readers | RCU does not serialize writers |
| Reader needs mutual exclusion with writer | Reader-writer lock or mutex | RCU does not exclude anyone |
| Reader needs a stable multi-field snapshot | Seqlock, mutex, or immutable replacement | RCU gives lifetime, not consistency |
| Tight memory, latency-sensitive free | Reference count, or RCU with hurrying | Grace period retains old versions |
| Teardown or module unload | synchronize_rcu() then rcu_barrier() | Wait for readers, then for callbacks |
| Tracing or code patching | Tasks RCU family | Readers are implicit and may be preempted |
| NMI context | NMI-safe SRCU or implicit protection | Normal reader entry may not be watching |
15.4 Important Rules
- Remove before waiting, wait before freeing. A grace period only covers readers that existed when it started, and the removal must precede that point.
- Publish with the release accessor. A plain store exposes a half-initialized object to a reader on another CPU.
- Load with the dependency accessor. A plain load may be reloaded, merged, or hoisted, and a control dependency does not order speculative loads on AArch64.
- Keep read-side sections short and non-blocking. A long section delays every reclamation in the system.
- Do not sleep in classic RCU. Use SRCU or a reference count if the reader must block.
- Use the
_rculist and hash primitives for mutation. Ordinary removal poisons the forward link that a reader still needs. - Serialize writers with an ordinary lock. RCU protects readers from writers, not writers from each other.
- Match every lock with an unlock in the same context. Nesting counts are per task; an unlock in another context corrupts them.
- Embed the callback head correctly and keep it alive. Reusing a callback head before its callback runs is a double-enqueue bug.
- Call the barrier before unloading code that owns callbacks. A pending callback would otherwise jump into unmapped text.
15.5 Sharp Edges at a Glance
| Symptom | Likely cause | Fix |
|---|---|---|
| Use-after-free in a reader | Old object freed before the grace period ended | Defer the free with a callback or wait for synchronize_rcu() |
| Reader sees zeroed or stale fields | Pointer published before initialization | Initialize fully, then publish with the release accessor |
| Reader follows a poison pointer | list_del() used instead of list_del_rcu() | Use the _rcu variant and keep the forward link intact |
| List corruption under concurrent updates | Writers not serialized | Add a mutex or spinlock around all mutations |
Hang in synchronize_rcu() | Called from inside an RCU read-side section, or a reader is stuck | Move the call outside the section; find the stuck reader |
Hang in synchronize_srcu() | Reader waits on the same SRCU domain | Never wait on a domain from inside its own reader |
| Callback never runs | Callback head reused, or callback sleeps and stalls the queue | Keep the head unique until invocation; make callbacks non-blocking |
| Module unload crash | Pending callback points into freed module text | Call rcu_barrier() before unloading |
| Stall warning with a long section | Reader blocked or looping inside the section | Shorten the section; use SRCU if it must block |
| Reader misses an update indefinitely | Staleness is inherent; the reader expected a snapshot | Revalidate or use a seqlock or lock |
| Grace-period latency spikes | Expedited grace periods called in a loop | Batch updates; use the normal or asynchronous path |
| Memory growth after updates | Old versions retained until a grace period completes | Batch removals; check for a stuck reader |
16. References
16.1 Core API and Types
- Documentation/RCU/whatisRCU.rst — the canonical introduction and the update/reclaim protocol.
- Documentation/RCU/rcu_dereference.rst — accessor rules and dependency ordering.
- include/linux/rcupdate.h — reader API, accessor macros, and the implicit-reader contract.
- include/linux/rcutree.h — Tree RCU public interfaces.
- kernel/rcu/update.c — expedited handling, barriers, and shared update code.
16.2 Tree RCU and Tiny RCU
- kernel/rcu/tree.c — grace-period state machine, quiescent-state reporting, and callback processing.
- kernel/rcu/tree.h —
rcu_state,rcu_node, andrcu_datalayouts. - kernel/rcu/tree_plugin.h — preemptible RCU, blocked readers, and callback offloading.
- kernel/rcu/tree_exp.h — expedited grace periods.
- kernel/rcu/tiny.c — the uniprocessor implementation.
16.3 SRCU, Tasks RCU, and the Flavors
- kernel/rcu/srcutree.c — SRCU counters, index flip, and grace periods.
- include/linux/srcu.h — SRCU read-side API and rules.
- kernel/rcu/tasks.h — Tasks RCU, Tasks Rude RCU, and Tasks Trace RCU.
- Documentation/RCU/NMI-RCU.rst — NMI interaction and deferred freeing.
- Documentation/RCU/Design/Requirements/Requirements.rst — the formal requirements behind the API.
16.4 AArch64 Memory Ordering
- arch/arm64/include/asm/rwonce.h —
READ_ONCE()and theldar/ldapralternatives. - arch/arm64/include/asm/barrier.h —
dmb,dsb, and thesmp_*barrier definitions. - arch/arm64/include/asm/atomic.h — release/acquire primitives used by publication.
- Documentation/memory-barriers.txt — acquire/release semantics and ordering vocabulary.
16.5 Lists and Users
- include/linux/rculist.h —
_rculist primitives and iterators. - include/linux/rculist_nulls.h — hash-list variants with NULL-terminated chains.
- kernel/cred.c — credentials, reference counts, and callback freeing.
- kernel/pid.c — PID lookup and task reference acquisition.
- fs/file.c — file descriptor table replacement and deferred freeing.
- net/core/dev.c — device lookup, name nodes, and alias handling.