Skip to content

RCU Quiescent State and Tree RCU

Overview

Previous RCU learning focused on:

  • Object publication
  • Grace period
  • Deferred reclamation
  • RCU APIs

A simplified educational implementation often uses a global reader counter:

reader_count++;
...
reader_count--;

and determines grace period completion using:

while (reader_count != 0)
    ;

Although easy to understand, this approach does not scale well on large multi-core systems.

Linux RCU uses a different design based on quiescent state tracking and per-CPU progress monitoring.

The Limitation of Reader Counting

A simple implementation maintains:

static atomic_int reader_count;

Every reader performs:

reader_count++;
...
reader_count--;

Grace period completion becomes:

reader_count == 0

Problem

All CPUs modify the same shared variable:

CPU0
  ↓
reader_count

CPU1
  ↓
reader_count

CPU2
  ↓
reader_count

CPU3
  ↓
reader_count

This creates:

  • Shared cacheline contention
  • Atomic operation overhead
  • Poor scalability

As CPU count increases, the cost of maintaining a global reader counter becomes significant.

Linux RCU Philosophy

Linux RCU does not ask:

How many readers are active?

Instead it asks:

Has every CPU progressed beyond
all readers that existed when
the grace period started?

This is a fundamentally different way of thinking.

Quiescent State

Definition

A quiescent state (QS) is a point where a CPU can no longer hold a reader that existed before the current grace period.

Conceptually:

Grace Period Start
        ↓
CPU Progresses
        ↓
CPU Reaches Safe Point
        ↓
Quiescent State

Common Misconceptions

A quiescent state does not mean:

CPU is idle
CPU is sleeping
CPU has no work
CPU stopped executing

A CPU may remain busy while still passing through a quiescent state.

Practical Interpretation

A quiescent state means:

This CPU is no longer capable
of holding an old RCU reader.

Once a CPU reaches this point, it becomes safe for the current grace period.

Reader Counting vs Progress Tracking

Reader Counting

Educational Mini RCU:

Count Readers
        ↓
reader_count == 0
        ↓
Grace Period Complete

Progress Tracking

Linux RCU:

Track CPU Progress
        ↓
All CPUs Reach Safe State
        ↓
Grace Period Complete

This removes the need for a globally shared reader counter.

Per-CPU State

Instead of maintaining:

reader_count

Linux maintains per-CPU information.

Conceptually:

struct rcu_cpu_state {
    bool safe_for_gp;
};

Each CPU tracks its own progress.

This avoids constant modification of a shared global variable.

Grace Period Detection

When a grace period begins:

GP #100 Start

Linux records which CPUs must be observed.

Conceptually:

Need Wait:
CPU0
CPU1
CPU2
CPU3

As CPUs report quiescent states:

CPU0 Done
CPU1 Done
CPU2 Done
CPU3 Done

The grace period completes.

Why Snapshot Matters

Linux only waits for CPUs that existed at the beginning of the grace period.

Conceptually:

GP Start
        ↓
Snapshot CPUs
        ↓
Wait For Snapshot Set

New CPUs appearing later are not part of the current grace period.

This prevents grace periods from growing indefinitely.

Tree RCU Motivation

A small system may contain:

4 CPUs
8 CPUs
16 CPUs

Tracking each CPU individually is simple.

Modern systems may contain:

64 CPUs
128 CPUs
256 CPUs
1024 CPUs

Scanning every CPU becomes increasingly expensive.

Tree Aggregation

Linux organizes CPU state hierarchically.

Conceptually:

                Root
               /    \
              /      \
          GroupA    GroupB
           /  \      /  \
        CPU0 CPU1 CPU2 CPU3

Aggregated Reporting

Instead of reporting every CPU to the root:

CPU0 → GroupA
CPU1 → GroupA

CPU2 → GroupB
CPU3 → GroupB

Each group reports:

Group Complete

The root only tracks group status.

Benefits

Tree aggregation provides:

  • Better scalability
  • Reduced tracking overhead
  • Efficient grace period detection
  • Support for very large CPU counts

Relationship to RCU APIs

The internal implementation is largely hidden from users.

Typical driver code still uses:

rcu_read_lock();
...
rcu_read_unlock();

obj = rcu_dereference(ptr);

rcu_assign_pointer(ptr, new_obj);

synchronize_rcu();

call_rcu(...);

Most kernel developers use the RCU APIs without needing to understand the full Tree RCU implementation.

Summary

Educational Mini RCU:

Count Readers
        ↓
reader_count == 0
        ↓
Grace Period Complete

Linux RCU:

Track CPU Progress
        ↓
Quiescent State Detection
        ↓
Tree Aggregation
        ↓
Grace Period Complete

The most important conceptual transition is:

Mini RCU counts readers.

Linux RCU tracks CPU progress.

This design allows Linux RCU to scale efficiently on systems with large numbers of CPUs.