Day66 - RCU Quiescent State and Tree RCU Overview¶

Topic¶

Linux Kernel RCU internals.

This session focused on understanding how Linux RCU scales beyond the simple global reader counter model used in educational implementations.

Goals¶

Understand why a global reader counter does not scale.
Understand the meaning of a quiescent state.
Understand how Linux RCU tracks CPU progress instead of counting readers.
Understand grace period detection at a high level.
Understand the motivation behind Tree RCU.

Completed Labs¶

Lab1 - Quiescent State Tracking Simulation¶

Implemented two grace period models.

Model A - Global Reader Counter¶

Used a shared atomic counter:

reader_count++;
...
reader_count--;

Grace period completion:

while (reader_count != 0)
    ;

This model matches the simplified Mini RCU implementation used in previous labs.

Model B - Quiescent State Tracking¶

Used per-thread state tracking:

enum qs_state {
    QS_PENDING,
    QS_REPORTED,
};

Each reader reports a quiescent state after leaving its read-side critical section.

Grace period completion:

All readers reported QS
        ↓
Grace Period Complete

This model demonstrates the fundamental idea behind Linux RCU internals.

Key Understanding¶

A global reader counter is easy to understand:

Grace Period Complete
=
reader_count == 0

However, this design does not scale on large multi-core systems because every reader must modify the same shared counter.

Linux RCU avoids this design.

Instead, Linux tracks whether each CPU has progressed through a safe point where it can no longer hold a reader from the beginning of the grace period.

Quiescent State¶

A quiescent state does not mean:

CPU is idle
CPU stopped running
CPU has no work

Instead, it means:

This CPU can no longer hold a reader
that existed before the current grace period.

Conceptually:

Grace Period Start
        ↓
CPU passes through Quiescent State
        ↓
CPU is considered safe

When all relevant CPUs become safe, the grace period can complete.

Reader Counter vs CPU Progress Tracking¶

Educational Mini RCU:

Count Readers
        ↓
Wait Until Counter Becomes Zero

Linux RCU:

Track CPU Progress
        ↓
Wait Until All CPUs Report Safe Progress

This is the most important conceptual difference between the two approaches.

Tree RCU Motivation¶

Tracking a small number of CPUs is simple:

CPU0
CPU1
CPU2
CPU3

However, modern systems may contain:

64 CPUs
128 CPUs
256 CPUs
or more

Scanning every CPU for every grace period would become expensive.

Linux solves this using a hierarchical tracking structure:

CPU State
    ↓
Group State
    ↓
Root State

This design is known as Tree RCU.

Tree RCU allows grace period status to be aggregated efficiently across large CPU counts.

Lab Observations¶

Model A demonstrated:

Grace Period Complete
=
reader_count == 0

Model B demonstrated:

Grace Period Complete
=
All Readers Reported Quiescent State

Although the lab used threads instead of CPUs, it clearly showed the conceptual shift from reader counting to progress tracking.

Summary¶

Day66 completed the introduction to Linux RCU internals.

The most important conclusion is:

Mini RCU counts readers.

Linux RCU tracks CPU progress.

Grace period detection is based on quiescent state reporting rather than a global reader counter.

Next¶

Synchronization series wrap-up:

Linux Synchronization Topic Summary
Linux Synchronization API Reference

Future topics:

Workqueue
Kernel Thread
Completion
Notifier Chain