Tree RCU

Tree RCU is the scalable implementation of Read-Copy-Update (RCU) grace-period detection used in essentially every production Linux kernel. The hard problem it solves is collective: to end a grace period, RCU must confirm that every CPU has passed through a quiescent state (a point where it holds no RCU read-side reference). A naive design would have all CPUs report into one global lock-protected counter — fine at four cores, a catastrophic cache-line bottleneck at hundreds. Tree RCU instead arranges per-CPU rcu_data structures under a combining tree of rcu_node structures rooted at a single rcu_state. Quiescent-state reports propagate up the tree and grace-period start/end propagate down, so lock contention is bounded by the tree’s fan-out — not by the CPU count (Data-Structures.rst). The kernel documentation calls the tree “a big shock absorber, keeping lock contention under control at all tree levels regardless of the level of loading on the system.” This note explains the structures, the up/down traffic, and why a tree is the right answer to RCU’s inherent scalability tension. Facts are pinned to Linux 6.12 LTS (2024-11-17).

The conceptual model of RCU — publish, wait a grace period, reclaim — is in Read-Copy-Update Fundamentals. What a grace period is and how synchronize_rcu() waits for one is in RCU Grace Periods. The writer-side deferred-free path that consumes Tree RCU’s grace-period signal is call_rcu and Deferred Reclamation. This note is about the engine that detects grace periods at scale.

Mental Model: a combining tree, not a flat counter

Imagine a stadium where every section must confirm “everyone in my section has stood up at least once” before the announcer can declare the wave complete. If all 80,000 people shouted directly at the announcer, the announcer is the bottleneck. Instead, each row reports to a section captain; each section captain reports to a tier captain; the tier captains report to the announcer. Most reports die at the row or section level; only a trickle reaches the top. Tree RCU is exactly this hierarchy: CPUs are the spectators, leaf rcu_node structures are section captains, internal rcu_nodes are tier captains, and the root rcu_node (inside rcu_state) is the announcer who declares the grace period over.

flowchart TB
  RS["rcu_state (root rcu_node)<br/>gp_seq, gp_kthread<br/>declares GP complete"]
  N1["internal rcu_node"]
  N2["internal rcu_node"]
  L1["leaf rcu_node<br/>qsmask bits = CPUs"]
  L2["leaf rcu_node"]
  L3["leaf rcu_node"]
  L4["leaf rcu_node"]
  C1["rcu_data CPU0..15"]
  C2["rcu_data CPU16..31"]
  C3["rcu_data CPU.."]
  C4["rcu_data CPU.."]
  RS --> N1 --> L1 --> C1
  N1 --> L2 --> C2
  RS --> N2 --> L3 --> C3
  N2 --> L4 --> C4
  C1 -.->|"quiescent state<br/>clears my bit"| L1
  L1 -.->|"last bit cleared<br/>-> report up"| N1
  N1 -.->|"last child done<br/>-> report up"| RS
  RS -.->|"GP start/end<br/>propagates down"| N1

The rcu_node combining tree. What it shows: per-CPU rcu_data (bottom) attach to leaf rcu_nodes; leaves attach to internal nodes; internal nodes attach to the root inside rcu_state (top). Quiescent-state reports flow upward (dashed, bottom-up) but each report only advances one level if it was the last sibling to check in; grace-period start and end flow downward. The insight to take: the tree turns a global “did all N CPUs check in?” question into a cascade of small local “did all my children check in?” questions, each guarded by a different lock, so no single lock is touched by all N CPUs.

The three structures

Tree RCU is built from exactly three structure types, defined in kernel/rcu/tree.h (tree.h):

rcu_data — one per CPU. It records that CPU’s quiescent-state status (cpu_no_qs, core_needs_qs), tracks the grace-period number it has observed (gp_seq), holds the CPU’s segmented callback list (cblist), and — critically for the tree — carries struct rcu_node *mynode (a pointer to its leaf node) and unsigned long grpmask (a one-bit mask identifying this CPU’s position within that leaf’s bitmask). The rcu_data is the “spectator”: it knows which “section captain” to report to and which bit in that captain’s tally is its own.

rcu_node — the combining-tree node, used at every level. Its load-bearing fields:

raw_spinlock_t lock — each node has its own lock. This is the whole point: contention is distributed across nodes.
unsigned long qsmask — the bitmask of children that still need to report a quiescent state for the current grace period. In a leaf node each bit is a CPU (rcu_data); in an internal node each bit is a child rcu_node.
unsigned long grpmask — the single bit this node occupies in its parent’s qsmask. Exactly one bit is set.
struct rcu_node *parent — the node one level up (NULL at the root).
int grplo, grphi — the range of CPU numbers served by this node’s subtree.
unsigned long gp_seq — this node’s view of the grace-period sequence number, used to detect stale reports.

rcu_state — the single global structure (rcu_state.node[0] is the root rcu_node). It holds the entire tree as a flattened array and the authoritative grace-period counter (tree.h):

struct rcu_state {
        struct rcu_node node[NUM_RCU_NODES];   /* Hierarchy. */
        struct rcu_node *level[RCU_NUM_LVLS + 1]; /* Pointers into node[] by level. */
        int ncpus;
        unsigned long gp_seq ____cacheline_internodealigned_in_smp; /* Grace-period seq #. */
        struct task_struct *gp_kthread;        /* The grace-period kthread. */
        struct swait_queue_head gp_wq;         /* Where the GP task waits. */
        short gp_flags;
        ...
};

Two details from this declaration matter. First, the whole tree lives in one contiguous node[NUM_RCU_NODES] array; the level[] pointers index into it so the code can walk a level at a time. Second, rcu_state.gp_seq is the single source of truth for the grace-period number and is ____cacheline_internodealigned_in_smp — placed on its own cache line so updating it does not falsely share with neighboring fields. The gp_kthread field anchors the dedicated kernel thread that drives grace periods, discussed below.

Mechanical Walk-through

Building the tree at boot

rcu_init_one() constructs the tree from three Kconfig-derived constants (tree.c): RCU_FANOUT (children per internal node), RCU_FANOUT_LEAF (CPUs per leaf node), and the actual CPU count. At boot RCU computes how many levels and nodes it needs (rcu_num_lvls, num_rcu_lvl[]), then walks the node[] array bottom-up wiring each node’s parent, grpmask, grplo, and grphi. Crucially, the tree is right-sized to the running hardware: a kernel built with NR_CPUS=4096 would nominally want a three-level tree, but if it boots on a 16-CPU machine RCU collapses the tree to a single node (Data-Structures.rst). On small systems the “tree” is one node and Tree RCU degenerates gracefully to the flat design it generalizes.

Quiescent states propagate up

When a CPU passes through a quiescent state for the current grace period, it must clear its bit. The core routine is rcu_report_qs_rnp(), which walks up the tree clearing bits (tree.c):

static void rcu_report_qs_rnp(unsigned long mask, struct rcu_node *rnp,
                              unsigned long gps, unsigned long flags)
{
        for (;;) {
                if ((!(rnp->qsmask & mask) && mask) || rnp->gp_seq != gps) {
                        raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
                        return;          /* bit already cleared, or GP already over */
                }
                WRITE_ONCE(rnp->qsmask, rnp->qsmask & ~mask);   /* clear my bit */
                if (rnp->qsmask != 0 || rcu_preempt_blocked_readers_cgp(rnp)) {
                        raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
                        return;          /* other siblings still pending -> stop here */
                }
                rnp->completedqs = rnp->gp_seq;
                mask = rnp->grpmask;     /* now report THIS node up to the parent */
                if (rnp->parent == NULL)
                        break;           /* reached the root, holding its lock */
                raw_spin_unlock_irqrestore_rcu_node(rnp, flags);
                rnp = rnp->parent;
                raw_spin_lock_irqsave_rcu_node(rnp, flags);
        }
        rcu_report_qs_rsp(flags);        /* last CPU overall -> end the GP */
}

This loop is the scalability mechanism, so read it carefully. The CPU clears its mask bit from the leaf’s qsmask while holding only the leaf’s lock. If other bits remain set — other CPUs in the same leaf have not yet reported — it stops immediately. Only when its bit was the last one set in the leaf does the loop continue: it then takes mask = rnp->grpmask (the leaf’s own bit in the parent) and walks up to acquire the parent’s lock and clear the leaf’s bit there. The same test repeats at each level. The result is the property the documentation calls out: “only the last CPU to report a quiescent state into a given rcu_node structure need advance to the rcu_node structure at the next level up” (Data-Structures.rst). With a leaf fan-out of 16, only one report in sixteen climbs past the leaf; with internal fan-out 64, only one in sixty-four climbs past an internal node. The root lock therefore sees at most ~64 reports per grace period no matter how many thousands of CPUs exist. When the walk reaches the root and clears the last bit, rcu_report_qs_rsp() ends the grace period.

The same up-propagation handles CPU hotplug and dyntick-idle: an offline or idle CPU cannot report quiescent states for itself, so the tree’s qsmaskinit/qsmaskinitnext machinery removes its bit at grace-period initialization, and an idle CPU is treated as having an implicit quiescent state. These events are recorded at the leaf level and combined upward by the same lock-distributed cascade.

Grace-period control propagates down

The downward direction is driven by a single dedicated thread, the grace-period kthread, rcu_gp_kthread() (tree.c):

static int __noreturn rcu_gp_kthread(void *unused)
{
        rcu_bind_gp_kthread();
        for (;;) {
                /* Handle grace-period start. */
                ... swait_event_idle_exclusive(rcu_state.gp_wq, gp_flags & RCU_GP_FLAG_INIT);
                    if (rcu_gp_init()) break;
                /* Handle quiescent-state forcing. */
                rcu_gp_fqs_loop();
                /* Handle grace-period end. */
                rcu_gp_cleanup();
        }
}

The kthread sleeps on rcu_state.gp_wq until an updater requests a grace period (sets RCU_GP_FLAG_INIT). It then runs three phases:

rcu_gp_init() — initialize a new grace period. It bumps rcu_state.gp_seq, then propagates the new grace-period number down the tree, copying each node’s qsmaskinit into its live qsmask (re-arming every still-online CPU’s bit) and recording the new gp_seq at each node. This downward sweep is what tells every CPU “a new grace period has started; I need a quiescent state from you.”
rcu_gp_fqs_loop() — the force-quiescent-state loop. The kthread sleeps for a tunable interval, then wakes to nudge CPUs that have not yet reported (e.g. CPUs spinning in long kernel code), re-checking idle/offline CPUs and prodding stragglers. This bounds grace-period latency even when some CPU is slow to reach a quiescent state.
rcu_gp_cleanup() — once the root’s qsmask is empty (the upward cascade reported in), end the grace period: advance gp_seq to “completed,” propagate the completion down the tree so each CPU’s rcu_data learns the grace period it was waiting on is done, and wake any synchronize_rcu() waiters. This completion signal is exactly what lets queued callbacks advance to the “done” segment and run.

Centralizing grace-period control in one kthread is itself a scalability decision: rather than every CPU independently driving grace-period state machinery (the old pre-2010 design had grace-period logic scattered across CPUs and was prone to lock contention and stalls), a single thread owns the protocol and the per-node locks serialize only the brief read/modify of each node’s bitmask.

The leaf-to-CPU mapping

Each rcu_data knows its leaf via rdp->mynode and its bit via rdp->grpmask, both wired at boot. Up to RCU_FANOUT_LEAF CPUs map to one leaf rcu_node; the leaf’s grplo/grphi give the CPU-number range it covers. This static mapping means a CPU reporting a quiescent state always contends on the same leaf lock — and, because leaves are sized to a modest fan-out, that leaf is shared with only a handful of other CPUs. The Quick Quiz in the documentation explains why leaves are deliberately narrower than internal nodes (fan-out 16 vs 64): leaf nodes absorb more event types (quiescent states, dyntick transitions, hotplug), so a wide leaf would over-concentrate contention; “experimentation on a wide variety of systems has shown that a fanout of 16 works well for the leaves” (Data-Structures.rst).

Configuration: `RCU_FANOUT` and `RCU_FANOUT_LEAF`

The tree shape is governed by two Kconfig options (kernel/rcu/Kconfig):

config RCU_FANOUT
        int "Tree-based hierarchical RCU fanout value"
        range 2 64 if 64BIT
        range 2 32 if !64BIT
        depends on TREE_RCU && RCU_EXPERT
        default 64 if 64BIT
        default 32 if !64BIT

config RCU_FANOUT_LEAF
        int "Tree-based hierarchical RCU leaf-level fanout value"
        ...
        default 16 if !RCU_STRICT_GRACE_PERIOD
        default 2 if RCU_STRICT_GRACE_PERIOD

Reading the defaults precisely matters, because they are routinely conflated. RCU_FANOUT — the fan-out of internal (non-leaf) nodes — defaults to 64 on 64-bit systems and 32 on 32-bit (it is capped at the bitmask width, since qsmask is one unsigned long). RCU_FANOUT_LEAF — the leaf fan-out, CPUs per leaf — defaults to 16. So the common shorthand “fan-out 16/64” means leaf 16, internal 64, not a range. Both options are hidden behind RCU_EXPERT; the Kconfig help says outright “The default value of RCU_FANOUT should be used for production systems” and is only worth changing to stress-test large-system code paths on small machines.

The arithmetic of these defaults: a two-level 64-bit tree with 64 leaves × 16 CPUs accommodates 1,024 CPUs with internal fan-out 64 and leaf fan-out 16 (Data-Structures.rst). Beyond 1,024 CPUs RCU automatically adds levels — it supports up to a four-level tree, which on 64-bit accommodates up to 4,194,304 CPUs. You can also shrink both options to 2, producing a deep tree on a small machine for testing large-system paths.

Uncertain

Verify: that RCU_FANOUT defaults to 64 (64-bit) / 32 (32-bit) and RCU_FANOUT_LEAF defaults to 16. Reason: the brief gave a “~16/64” hint that conflated the two; this note’s values are read directly from the default lines in the v6.12 kernel/rcu/Kconfig blob actually fetched, where RCU_FANOUT default 64 if 64BIT and RCU_FANOUT_LEAF default 16 if !RCU_STRICT_GRACE_PERIOD. To resolve: confirmed against v6.12 Kconfig — the only caveat is that RCU_FANOUT_LEAF drops to 2 under the debug option CONFIG_RCU_STRICT_GRACE_PERIOD. uncertain

Why a tree is the answer

RCU’s grace-period detection is inherently global: by definition a grace period cannot end until every CPU has checked in, so some piece of state must be touched by all of them. The flat design makes that piece a single lock-protected counter, and the cache line holding it ping-pongs between every CPU’s cache on every report — the textbook cache-line-bouncing bottleneck that gets quadratically worse with core count and dominated RCU’s earlier “Classic RCU” implementation on large systems.

The tree does not remove the global dependency — it cannot, the question is genuinely global — but it partitions the contention. Because only the last reporter at each node climbs to the next level, the number of accesses that reach any given node is bounded by that node’s fan-out, independent of total CPU count. The documentation’s framing is precise: “only one access out of sixteen will progress up the tree” at the leaves and “one access out of sixty-four” at internal nodes, so “no matter how many CPUs there are in the system, at most 64 quiescent-state reports per grace period will progress all the way to the root” (Data-Structures.rst). The root lock — the one truly global lock — therefore sees a constant trickle regardless of scale. That is the precise sense in which the tree is “a big shock absorber”: it converts O(N) contention on one lock into roughly O(log N / log fanout) levels of bounded contention, distributed across many locks. This is the same combining-tree idea used in scalable barrier and counter algorithms, applied to RCU’s quiescent-state tally.

Failure Modes and Diagnostics

RCU CPU stall warnings. If a CPU fails to report a quiescent state for too long — typically because it is stuck in a long non-preemptible kernel loop, an interrupt storm, or a livelock — the grace-period kthread’s force-quiescent-state loop cannot complete the grace period, and RCU prints an RCU CPU stall warning naming the delinquent CPU(s) and dumping their stacks. The stall report walks the tree printing each node’s qsmask so you can see which CPUs’ bits are still set. The usual root causes are a missing cond_resched() in a long kernel loop, a disabled-preemption section held too long, or a hung CPU.

gp_kthread starvation. Because one kthread drives all grace periods, if that thread is starved of CPU (e.g. on a misconfigured real-time system where it is outranked by busy RT tasks), grace periods stall system-wide and callbacks pile up. Stall warnings flag this as the grace-period kthread not running. Pinning and priority of the gp_kthread (and the rcuc/rcuo kthreads) are tunable for this reason.

Misreading fan-out. A common analysis error is assuming the tree fan-out is uniform. It is not: leaves use RCU_FANOUT_LEAF (16) and internal nodes use RCU_FANOUT (64). Tooling that infers tree depth from a single fan-out will miscount nodes.

Alternatives and When to Choose Them

Tiny RCU (TINY_RCU) — for uniprocessor builds (!SMP), RCU collapses to almost nothing: with one CPU there is no combining problem, so the tree machinery is replaced by a trivial implementation. Tree RCU is for SMP. (Data-Structures.rst)
Expedited grace periods — Tree RCU’s normal grace period is throughput-optimized and can take milliseconds. When latency matters, expedited grace periods use IPIs to force quiescent states immediately, trading CPU disruption for speed; they reuse the same rcu_node tree (expmask mirrors qsmask).
SRCU (Sleepable RCU) — a separate flavor allowing readers to block, with its own per-srcu_struct state rather than the global tree. Choose SRCU when readers must sleep; choose Tree RCU for the classic non-sleeping read-side. (whatisRCU)
NOCB offload — orthogonal to the tree: NOCB changes who runs the callbacks (offloaded rcuo kthreads) without changing grace-period detection. See RCU and NOCB Offloaded Callbacks.

Production Notes

Tree RCU has been the default RCU implementation since the rewrite that introduced the rcu_node hierarchy (the “Hierarchical RCU” work, circa 2.6.30+), motivated directly by lock contention on large SGI and IBM systems where Classic RCU’s flat design collapsed. Today every mainstream distribution kernel (CONFIG_TREE_RCU=y) runs it, on machines from laptops (where the tree is one node) to thousand-core servers (multi-level trees). The maintainer’s design documents under Documentation/RCU/Design/ — including the Data-Structures and Memory-Ordering write-ups — are the authoritative reference and were the primary source for this note. The combining-tree pattern Tree RCU embodies is one of the kernel’s clearest case studies in turning a fundamentally global operation into a contention-bounded one, and it is why RCU scales to core counts where lock-based read protection would have collapsed.

vault

Explorer

Tree RCU

Tree RCU

Mental Model: a combining tree, not a flat counter

The three structures

Mechanical Walk-through

Building the tree at boot

Quiescent states propagate up

Grace-period control propagates down

The leaf-to-CPU mapping

Configuration: `RCU_FANOUT` and `RCU_FANOUT_LEAF`

Why a tree is the answer

Failure Modes and Diagnostics

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Tree RCU

Tree RCU

Mental Model: a combining tree, not a flat counter

The three structures

Mechanical Walk-through

Building the tree at boot

Quiescent states propagate up

Grace-period control propagates down

The leaf-to-CPU mapping

Configuration: RCU_FANOUT and RCU_FANOUT_LEAF

Why a tree is the answer

Failure Modes and Diagnostics

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks

Configuration: `RCU_FANOUT` and `RCU_FANOUT_LEAF`