Day66 - Quiescent State Tracking and Tree RCU Overview

Overview

This lab explores the conceptual difference between a simple reader-counting RCU implementation and the high-level design used by Linux RCU.

The goal is not to implement Linux Tree RCU, but to understand why Linux tracks CPU progress and quiescent states instead of maintaining a global reader counter.

---

Learning Objectives

• Understand the limitation of a global reader counter.
• Understand the concept of a quiescent state.
• Understand grace period completion using progress tracking.
• Understand why Linux RCU scales better on large multi-core systems.
• Understand the motivation behind Tree RCU.

---

Lab1 - Reader Counter vs Quiescent State Tracking

Objective

Compare two grace period detection models:

Model A
Global Reader Counter

Model B
Per-Thread Quiescent State Tracking

The lab demonstrates how Linux RCU shifts from reader counting to CPU progress tracking.

---

Model A - Global Reader Counter

Design

A shared counter tracks active readers:

static atomic_int g_reader_count;

Reader entry:

atomic_fetch_add_explicit(
    &g_reader_count,
    1,
    memory_order_acquire);

Reader exit:

atomic_fetch_sub_explicit(
    &g_reader_count,
    1,
    memory_order_release);

---

Grace Period Detection

Writer waits until:

reader_count == 0

Pseudo code:

while (atomic_load(&g_reader_count) != 0)
    sched_yield();

---

Conceptual Model

Reader Enter
      ↓
reader_count++
      ↓
Reader Exit
      ↓
reader_count--
      ↓
reader_count == 0
      ↓
Grace Period Complete

---

Limitation

Every reader modifies the same shared variable:

CPU0
  ↓
reader_count

CPU1
  ↓
reader_count

CPU2
  ↓
reader_count

CPU3
  ↓
reader_count

This becomes increasingly expensive as CPU count grows.

---

Model B - Quiescent State Tracking

Design

Each reader maintains its own state:

enum qs_state {
    QS_PENDING = 0,
    QS_REPORTED,
};

Per-reader tracking:

static atomic_int g_qs_state[READER_NUM];

---

Reader Flow

Reader enters:

Active

Reader exits:

Report Quiescent State

Example:

atomic_store_explicit(
    &g_qs_state[id],
    QS_REPORTED,
    memory_order_release);

---

Grace Period Detection

Writer waits until every reader reports:

QS_REPORTED

Pseudo code:

for (;;) {

    all_done = true;

    for (i = 0; i < READER_NUM; i++) {

        if (g_qs_state[i] != QS_REPORTED) {
            all_done = false;
            break;
        }
    }

    if (all_done)
        break;
}

---

Conceptual Model

Reader Exit
      ↓
Report QS
      ↓
All Readers Report QS
      ↓
Grace Period Complete

---

What Is a Quiescent State?

A quiescent state is often misunderstood.

It does not mean:

CPU is idle
CPU is sleeping
CPU has stopped running

Instead it means:

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

---

Simplified Interpretation

Grace Period Starts
        ↓
CPU progresses
        ↓
CPU reaches safe point
        ↓
CPU reports QS
        ↓
Grace Period progresses

---

Reader Counting vs Progress Tracking

Mini RCU

Count Readers
        ↓
reader_count == 0
        ↓
Grace Period Complete

---

Linux RCU

Track CPU Progress
        ↓
All CPUs reach safe state
        ↓
Grace Period Complete

---

Tree RCU Motivation

Tracking a few CPUs is easy.

Example:

CPU0
CPU1
CPU2
CPU3

However, Linux may run on systems containing:

64 CPUs
128 CPUs
256 CPUs
1024 CPUs

Checking every CPU individually becomes inefficient.

---

Hierarchical Tracking

Linux aggregates status through multiple layers:

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

---

Aggregation

Instead of tracking every CPU directly:

CPU0 → GroupA
CPU1 → GroupA

CPU2 → GroupB
CPU3 → GroupB

Groups report completion upward.

Eventually:

All Groups Complete
        ↓
Grace Period Complete

This concept is known as Tree RCU.

---

Results

Model A

Grace period completion depends on:

reader_count == 0

The system counts active readers.

---

Model B

Grace period completion depends on:

All readers reported quiescent state

The system tracks progress rather than counting readers.

---

Key Takeaways

Model A

Simple
Easy to understand
Poor scalability
Shared global state

---

Model B

Progress tracking
Per-reader state
Closer to Linux RCU design
More scalable

---

Most Important Conclusion

Mini RCU counts readers.

Linux RCU tracks CPU progress.

This shift from reader counting to progress tracking is the foundation of modern Linux RCU implementations.