---
tags: LINUX KERNEL, LKI
---

# [Linux 核心設計](https://beta.hackfoldr.org/linux/): RCU 同步機制

Copyright (**慣C**) 2019,2026 [宅色夫](https://wiki.csie.ncku.edu.tw/User/jserv)

==[直播錄影 (上)](https://youtu.be/i25ojG2aknQ)==
==[直播錄影 (下)](https://youtu.be/N9pVyv09Kx0)==

## 點題

RCU 作為 Linux 核心的同步機制之一，允許多個 reader 在單一 writer 更新資料的同時，得以在不需要 lock 的前提，正確讀取資料。可是既然 reader 可能讀到更新前或更新後的資料，這樣怎麼會有「共識」呢？

探究本題材之前，請先研讀 [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync)。

本文探討以下：
1. 為什麼選 RCU、概念、寬限期、訂閱—發布機制：先說明傳統 lock 的 cache-line bouncing 瓶頸與 RCU 的三條適用判準，再以 NMI handler 案例建立基本心智模型，理解 reader 與 writer 為何不必互鎖
2. 顧及 memory ordering 的影響：說明 `rcu_assign_pointer` 與 `rcu_dereference` 為何不可省略，以及 Linux v5.9 把 `smp_read_barrier_depends()` 移除後的演進
3. 資料讀取的完整性、何時可銷毀舊資料：以鏈結串列的逐步圖示具現多版本機制，並引入 QSBR 的記憶體回收策略與 Linux 核心以外的實作
4. RCU 模型、Tree RCU 實作主體、RCU 變體：從抽象的 Reader/Updater/Reclaimer 三要素深入到 `rcu_state` / `rcu_node` / `rcu_data` 的階層樹，並列舉主線並存的 RCU flavor 與寬限期等待介面

## 為什麼選 RCU：lock 的擴充瓶頸

`spinlock_t` 與 `rwlock_t` 在實作上有一項共通結構：所有取得/釋放路徑都必須對「位於某條共用 cache line 的計數器」(spinlock 的 `next`/`owner`、rwlock 的 reader count) 執行 atomic 讀-改-寫。CPU 核數越多，這條 cache line 在各 CPU L1 快取之間被 invalidate-and-refetch 的頻率就越高，每筆 lock 操作的有效成本主導於跨 CPU 的 cache coherency 通訊，而非實際的演算邏輯。`seqlock_t` 的讀取端只讀 sequence 並比對重試、不寫共用狀態；它的擴充瓶頸出現在寫入端 (寫入端取得 spinlock 並 atomic 遞增 sequence)，與前二者「讀取端就引發 bouncing」的形態不同。Paul McKenney 在 [perfbook](https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html) 第 3 章 (Hardware and its Habits) 把這類跨 CPU coherence 成本歸入 `communications cache misses`。

digraph lock_cacheline_bouncing {
    rankdir = "TB";
    node [shape=box, style="rounded,filled", fontname="Helvetica"];
    edge [arrowsize=0.6];

    cpu0 [label="CPU 0\n(writer)", fillcolor="khaki"];
    cpu1 [label="CPU 1\n(reader)", fillcolor="lightblue2"];
    cpu2 [label="CPU 2\n(reader)", fillcolor="lightblue2"];
    cpuN [label="CPU N\n(reader)", fillcolor="lightblue2"];

    l1_0 [label="L1 (Modified)\nlock counter", fillcolor="lightcoral"];
    l1_1 [label="L1 (Invalid)", fillcolor="lightgray"];
    l1_2 [label="L1 (Invalid)", fillcolor="lightgray"];
    l1_N [label="L1 (Invalid)", fillcolor="lightgray"];

    cpu0 -> l1_0 [arrowhead=none];
    cpu1 -> l1_1 [arrowhead=none];
    cpu2 -> l1_2 [arrowhead=none];
    cpuN -> l1_N [arrowhead=none];

    bus [label="cache coherence traffic (shared cache line: lock counter)",
         shape=plaintext, fillcolor=transparent, fontcolor="firebrick"];

    l1_0 -> bus [dir=both, color="firebrick", penwidth=1.5];
    l1_1 -> bus [dir=both, color="firebrick", penwidth=1.5];
    l1_2 -> bus [dir=both, color="firebrick", penwidth=1.5];
    l1_N -> bus [dir=both, color="firebrick", penwidth=1.5];

    { rank=same; cpu0; cpu1; cpu2; cpuN }
    { rank=same; l1_0; l1_1; l1_2; l1_N }
}

上圖為概念示意：實際硬體經 MESI/MOESI 等協定處理，跨 CPU 的 coherence 流量視拓樸與 NoC/QPI 連線而異，並非真有單一「廣播匯流排」。但對軟體層面的觀察是一致的：CPU 0 寫入計數器使其 L1 行為 Modified；其他 CPU 的副本立即 Invalid，下一輪存取觸發 `communications cache misses`，必須跨 CPU/socket 取回最新值。重點在於 reader 端取得 rwlock 時同樣得 atomic 遞增 reader count — 這條 cache line 因此在多個 reader 之間反覆 bouncing。隨 CPU 數線性增長的不是邏輯工作量，而是這條 cache line 在系統中往返的次數。這也是〈實驗 U4〉中 rwlock 在 224 reader 下總吞吐量僅剩 3 M/s、隨 reader 數增加反而崩塌的根因。

RCU 改變了這個結構：讀取端不寫任何全域共用變數。`!CONFIG_PREEMPT_RCU` 下 `rcu_read_lock()` 展開為 `preempt_disable()` (修改 per-task 的 `preempt_count`，是 thread-local 寫入，不引發跨 CPU coherence)；`CONFIG_PREEMPT_RCU=y` 下展開為 `current->rcu_read_lock_nesting++` (per-task 計數器)。兩種設定的讀取端都不爭搶共用 atomic counter，同步成本被推到寫入端的寬限期等待，並由 CPU 自然的 context switch / tick 攤平。

採用 RCU 的三條結構前提：
1. 受保護的資料必須是動態配置、透過指標存取 — RCU 的「Copy-Update」步驟需要配置新版資料、不可分割 (atomic) 地切換指標；無法套用於原地修改的硬體暫存器、bitmap inline data 等
2. 讀取端 critical section 不可 sleep (Classic / Preemptible RCU)；需要 sleepable reader 時改用 SRCU 或 Tasks-Trace RCU (詳見〈RCU 變體〉)
3. 讀寫嚴重不對稱：writer 必須容忍寬限期延遲 (數毫秒至數十毫秒)。量化判準 (更新比例 $f$ 是否壓得到 $f \ll 1/n_{\text{CPU}}$) 見〈何時值得採用 RCU〉；若 writer 對延遲敏感、又無法滿足量化判準，請優先考慮 hazard pointer 或 `seqlock_t`

下方〈概念〉節以 NMI handler 案例展開 RCU 的具體運作；如需先看「為什麼 lock 擴充崩塌」的實測數字，可直接跳至〈實驗 U4：讀取端可擴充性〉。

## 概念

RCU ([Read-Copy Update](https://en.wikipedia.org/wiki/Read-copy-update)) 是一種資料同步機制，在 Linux 核心扮演重要作用。在 [What is RCU, Fundamentally?](https://lwn.net/Articles/262464/) 一文，開宗明義:
> Read-copy update (RCU) is a synchronization mechanism that was added to the Linux kernel in October of 2002. RCU achieves scalability improvements by allowing reads to occur concurrently with updates.

RCU 適用於頻繁的讀取 (即多個 reader)、但資料寫入 (即少量的 updater/writer) 卻不頻繁的情境，例如檔案系統，經常需要搜尋特定目錄，但對目錄的修改卻相對少，這就是 RCU 理想應用情境。

RCU 藉由 [lock-free 程式設計](https://hackmd.io/@sysprog/concurrency-lockfree)滿足以下情境的同步需求:
* 頻繁的讀取，不頻繁的寫入
* 對資料沒有 strong consistency 需求

舉例來說，[DNS resolution](https://nlp.stanford.edu/IR-book/html/htmledition/dns-resolution-1.html) 為了加快查詢速度，常會在主記憶體中保存網域名稱和 IP 位址的對照表格，即是頻繁的讀取，但僅在該對照表格沒有查詢者要求的項目 (條件 `1`)，或者某項目失效時 (條件 `2`)，才會更新表格。針對條件 `2`，需要重新走完整個 DNS 解析過程，並更新到網域名稱對 IP 位址的表格。若在失效的瞬間，有個程式採用該失效的資料，於是存取 IP 位址的操作勢必跟著失敗，但這無妨，只要程式再執行 DNS 解析即可，不影響最終的功能，於是就符合條件 `2`。我們用更通用的方式來解讀這個案例：即使存取舊的資料，不會影響最終行為的正確，這樣的情境就適合 RCU，對其他網路操作也有相似的考量。

另一個案例是 NMI 處理程式:

現代的伺服器在前方面板上有個實體的 NMI 按鈕:

> [Dell PowerEdge 2650: Diagnostic Indicators](http://alexandre.julie.free.fr/dtc.smartelearning.com/training/docs/pe2650/troubleshooting_indicators.html)

watchdog interrupt 可傳送到 NMI，進而取得系統出現問題 (例如 hard lock — 偵測中斷停用情況下的 deadlock) 的現場資訊，而不僅是重啟。hard lockup detector 透過週期性的 NMI 偵測中斷被長時間停用而引發嚴重問題 (hard lockup)。

rcu_list_t nmi_list;
spinlock_t nmi_list_lock;

void handle_nmi() {
    rcu_read_lock();
    rcu_list_for_each(&nmi_list, handler_t cb)
    cb();
    rcu_read_unlock();
}

void register_nmi_handler(handler_t cb) {
    spin_lock(&nmi_list_lock);
    rcu_list_add(&nmi_list, cb);
    spin_unlock(&nmi_list_lock);
}

void unregister_nmi_handler(handler_t cb) {
    spin_lock(&nmi_list_lock);
    rcu_list_remove(cb);
    spin_unlock(&nmi_list_lock);
    synchronize_rcu();
}

> RCU list 函式包含必要的 `rcu_dereference` 和 `rcu_assign_pointer` 呼叫
> 參見: [Using RCU to Protect Dynamic NMI Handlers](https://www.kernel.org/doc/Documentation/RCU/NMI-RCU.txt)

電子書《[Is Parallel Programming Hard, And, If So, What Can You Do About It?](https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html)》詳細描述 RCU 和相關同步處理機制的考量，本文參照該電子書部分內容，給予 RCU 概念闡述。
> RCU 演講和論文彙整: [Introduction to RCU](http://www2.rdrop.com/users/paulmck/RCU/)

以 linked list (鏈結串列，以下簡稱 `list`) 的操作來說，RCU 考慮以下議題:
1. 讀取過程中，另外一個執行緒刪除一個節點。執行刪除動作的執行緒可將該節點從 list 中移除，但因存在可能的記憶體參照 (reference)，它不能直接銷毀 (隱含「釋放記憶體」的操作) 這個節點，必須等到所有的讀取端執行緒讀取都完畢後，才進行銷毀操作。RCU 將這個過程稱為寬限期 (grace period)
2. 讀取過程中，另外一個執行緒插入一個新節點到 list，而讀取端執行緒讀取該節點，則要保證讀到的這個節點是完整，而非中間狀態。這涉及發布－訂閱 ([Publish-Subscribe](https://en.wikipedia.org/wiki/Publish%E2%80%93subscribe_pattern)) 機制
3. 保證讀取 list 的完整性。新增或者刪除一個節點，不至於導致逐一走訪 list 時會從中間斷開。但 RCU 不保證一定能讀到新增的節點或不讀到要被刪除的節點

## 寬限期

英語 [grace period](https://www.merriam-webster.com/dictionary/grace%20period) 指義務期限過後緊接的一段時期，只要在寬限期內履行義務，就可免除因未能按時完成任務而應採取的滯納金或進一步行動。寬限期可從幾分鐘到幾天甚至更長的時間不等。最常見的情況為借貸，其他情況如支付帳單、滿足政府或法律要求也適用。RCU 借用 [grace period](https://www.merriam-webster.com/dictionary/grace%20period) 這概念，描述共用資料的處理期間，寫入端執行緒發布共用資料的更新作為寬限期的起點，直到諸多讀取端執行緒得以達成取得更新資料的操作為止。

下方程式碼展示寬限期:

struct foo {
    int a;
    char b;
    long c;
};
 
DEFINE_SPINLOCK(foo_mutex);
 
struct foo *global_foo;
 
void foo_read(void) {
    foo *fp = global_foo;
    if (fp)
        do_something(fp->a, fp->b , fp->c);
}
 
void foo_update(foo *new_fp) {
    spin_lock(&foo_mutex);
    foo *old_fp = global_foo;
    global_foo = new_fp;
    spin_unlock(&foo_mutex);
    kfree(old_fp);
}

這程式是針對全域變數 `global_foo` 的操作。假設以下情境:
* 有 2 個執行緒同時執行 `foo_read` 和 `foo_update`，當 `foo_read` 執行完數值指派的操作 (即 `fp = global_foo`) 後，執行緒發生切換；
* 此時另一個執行緒正執行 `foo_update`，即將完成
* 當 `foo_read` 的執行緒切換回來後，正要執行 `do_something` 時，`fp` 對應的記憶體空間已被釋放，這將對系統造成危害

為了防止此類事件的發生，RCU 裡增加一個名為寬限期 (grace period) 的概念，示意如下:
> $\uparrow$ 圖一: 讀取端執行緒的狀態拆解 Reader~1-6~

上圖的 Reader~1-6~ 表示讀取端執行緒的不同狀態，例如 Reader~1~, Reader~4~, Reader~6~ 實際上可以是同一個執行緒，但在不同時間點存取共用資源，這也是為何我們不用 Thread~1-6~ 來標注。橫軸則是時間，需要考慮到 t~1,2,3~ 這三個時間點。

儘管 Reader~1,2,3~ 這三個讀取端執行緒讀取結束時間不同，但都在 t~1~ 前取得指標 `fp` 的讀取。t~2~ 這個時間點，資料更新者 (即 `foo_update`) 呼叫 `synchronize_rcu()`，這時 Reader~1~ 的 critical section (以下簡稱 `CS`) 已結束，但 Reader~2,3~ 尚在 CS，因此必須等到 Reader~2,3~ 的 CS 都結束，亦即 t~3~。在 t~3~ 後，就可執行 `kfree(old_fp)` 以釋放舊資料佔用的記憶體。

`synchronize_rcu()` 執行的這段時間即為寬限期，後者的意義是，在刪除動作發生後，它必須等待所有在寬限期開始前已開始的讀取端執行緒結束，方可進行銷毀操作。這樣做的原因是，這些執行緒可能讀到即將要刪除的資料。
而 Reader~4,5,6~ 由於讀取指標的時間在 t~1~ 之後， 就會參照到新版的內容，就不用理會前述的寬限期。

上述程式碼藉由 RCU 改寫，在讀取端執行緒裡頭標注寬限期，成為以下:

void foo_read(void) {
    rcu_read_lock();
    foo *fp = global_foo;
    if (fp)
        do_something(fp->a, fp->b, fp->c);
    rcu_read_unlock();
}
 
void foo_update(foo *new_fp) {
    spin_lock(&foo_mutex);
    foo *old_fp = global_foo;
    global_foo = new_fp;
    spin_unlock(&foo_mutex);
    synchronize_rcu();
    kfree(old_fp);
}

其中 `foo_read` 函式增加 `rcu_read_lock` 和 `rcu_read_unlock` 這兩個函式的呼叫，用來界定 RCU 讀取端 CS 的範圍，使核心得以判定哪些讀取端屬於「寬限期前已存在」、必須在釋放舊資料前等其離開。`foo_update` 增加 `synchronize_rcu` 函式的呼叫，意味著寬限期的開始，而直到寬限期結束，該函式才會返回。示意如下:

寬限期是 RCU 實作中最複雜的部分，原因是在提高讀取資料的效能的同時，刪除資料的效能也不能太差。

### 為何 RCU 選用 grace period 機制

寬限期的設計看似奇特：既然只需追蹤「誰正在讀舊版資料」即可，為何要等到「所有 pre-existing reader 都離開 CS」這種較粗的條件？答案在於四種替代方案的對照。

1. Reference counting (引用計數)
- 機制：每個 reader 進入時對共用 atomic counter 做 +1、離開時做 -1；writer 等到 counter == 0 才釋放
- 缺點：每筆讀取都要寫共用 cache line；reader 之間互相 invalidate，正是〈為什麼選 RCU〉節描述的 cache-line bouncing 災情
- 取捨：reclamation 立即且記憶體佔用低，但讀取端不可擴充；適用於讀寫接近的情境

2. Hazard pointer (HP)
- 機制：reader 把正在讀取的指標寫入 thread-local 的 hazard pointer 陣列；writer 拔除節點後掃描所有 thread 的 HP，全無人指向才釋放
- 缺點：reader 雖無 atomic RMW 但仍有 store；該 store 通常須伴隨 full memory barrier (例如 `smp_mb()`) 以保證寫入順序對 writer 的掃描可見，正是讀取端無法達到 RCU 級零開銷的關鍵
- 取捨：reclamation 上界明確 (`O(threads)` 物件量)，但讀取端非完全 wait-free；適用於對 reclamation 上界敏感的即時/嵌入式系統。Maged Michael 在 [Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects (TPDS 2004)](https://www.cs.otago.ac.nz/cosc440/readings/hazard-pointers.pdf) 提出此設計

3. Epoch-based reclamation (EBR)
- 機制：以全域 epoch counter 推進為主軸，reader 進入時記錄當前 epoch；writer 把廢棄物件掛到當前 epoch 的 limbo list；epoch 推進需所有 thread 都跨過該 epoch
- 與 QSBR 的關係：兩者皆屬 deferred reclamation 的同一族系，但細節不同 — EBR 仰賴顯式 epoch counter，reader 進入 CS 時須讀取並記錄 epoch；QSBR (見〈QSBR 演算法〉節) 則由 thread 在自然空檔主動宣告靜默狀態，無顯式 epoch counter。`liburcu` 的 `urcu-qsbr` flavor 為 QSBR 路線；典型的 EBR 實作見 Keir Fraser 2004 年博士論文 [Practical Lock-Freedom](https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf) §5.2 與 Crossbeam (Rust) 等

4. Grace period (RCU)
- 機制：reader 進入 CS 不寫任何全域共用狀態 (Classic RCU 透過 `preempt_disable()` 修改 per-task 的 `preempt_count`，是 thread-local 寫入)；writer 啟動 GP，藉由排程事件 (context switch、tick、idle entry) 累積證據，等所有 CPU 都自然走過 QS 即視為 pre-existing reader 全部離開
- 優點：read-side 接近零開銷、與 CPU 數無關；GP 推進完全寄生於 scheduler，無需專屬 atomic counter
- 缺點：「等全部 CPU」是粗粒度的悲觀策略 — 即使該 CPU 從未持有舊版指標也要等它過 QS；GP 延遲下界取決於最慢 reader 與 scheduler tick 頻率

選擇 GP 而非其他三者的根本理由有三：

- 讀寫成本不對稱：read-mostly 工作負載下 reader 數量與頻率遠大於 writer；把同步成本「全部推給 writer 等寬限期」對總體吞吐量最有利。實驗 U5 量到 `synchronize_rcu()` 寫入端開銷比 `call_rcu()` 高 22–27 倍，但代價是讀取端零開銷
- 避開 cache 通訊：reader 不寫共用狀態，因而不引發跨 CPU coherence；這是 RCU 在 224 個 logical CPU 仍能線性擴充的關鍵 (見實驗 U4 中 rcu-qsbr 隨 reader 數線性擴充至 43 G ops/s，反觀 rwlock 退化到 3 M/s)
- 與 scheduler 自然耦合：context switch、tick、idle entry 本來就會發生；以這些事件作為 QS 證據幾乎零額外成本，且天然分散在各 CPU。〈排程器事件與 QS 來源〉節已詳述此銜接

GP 的「悲觀」一面常被誤解為缺陷，但實際上是設計取捨：放棄精確追蹤每個 reader 對特定指標的引用，換取讀取端零成本與寫入端可批次釋放的好處。多筆 `synchronize_rcu()` / `call_rcu()` 可共享同一個 GP — 這正是 `kfree_rcu()` 的 SLAB bulk 路徑能批次釋放數百個物件的基礎。

從形式來看，writer 在時刻 $t_w$ 呼叫 `synchronize_rcu()` 算起，GP 的長度滿足：

$$\text{GP} \geq \max_{r \in R_{\text{pre}}} \left( T_{\text{end}}(r) - t_w \right)^+ + D_{\text{detect}}$$

其中 $R_{\text{pre}}$ 為「在 $t_w$ 之前已進入 CS」的 reader 集合，$T_{\text{end}}(r)$ 為其 CS 結束時間，$(x)^+ = \max(x, 0)$，$D_{\text{detect}}$ 為 GP 偵測機制本身的延遲下界 (例如 Tree RCU 中 `jiffies_till_first_fqs` 的初次 FQS 等待，或 liburcu 的 condition variable 喚醒成本)。這個下界在實驗 U3 已直接驗證：reader CS 持續 50 ms 時，`synchronize_rcu()` 阻塞約 50 ms，再加上 ~100 µs 的 liburcu 內部 $D_{\text{detect}}$；核心側對應的數據可見實驗 3 中 `synchronize_rcu_normal` 16–32 ms 的尾端延遲。

McKenney 與 Slingwine 在〈[Read-Copy Update: Using Execution History to Solve Concurrency Problems](http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf)〉(PDCS 1998 年) 將這種「等 pre-existing reader 過去」的策略追溯到 Sequent DYNIX/ptx 的 passive serialization；wait-for-readers 概念並非 RCU 獨創，但 RCU 是首個把它與〈訂閱—發布機制〉、多版本物件、與 scheduler-aware QS 偵測組合起來的同步原語，使其在多 CPU 核心擴充性不受限。較完整的屬性對照見後文〈對比其他 lock-free 同步機制〉的 reference counting / RCU / hazard pointer 表格。

## 訂閱—發布機制

圖解發布－訂閱 ([Publish-Subscribe](https://en.wikipedia.org/wiki/Publish%E2%80%93subscribe_pattern)) 機制:
* updater 和 reader 彼此的關係可用 Publisher 和 Subscriber 來描述
* updater 更新內容後，呼叫指定介面進行發布，reader 呼叫特定介面來讀取已發佈的內容

更細緻的圖解:
> $\uparrow$ RCU 機制圖解。橫軸是時間，縱軸可見 writer 和多個 reader。取自 [Read, Copy, Update, then what? RCU for non-kernel programmers](https://github.com/CppCon/CppCon2017/blob/master/Presentations/Read%2C%20Copy%2C%20Update...%20Then%20What/Read%2C%20Copy%2C%20Update...%20Then%20What%20-%20Fedor%20Pikus%20-%20CppCon%202017.pdf)

當寫入端執行緒想將原本指向 data~1~ 的指標 `p`，變更為指向 data~2~，需要考慮到讀取端執行緒可能已參照到 data~1~，於是寫入端執行緒會「發布」新資料，進入「等待讀取端執行緒離開 critical section」的時期。示意圖的 `p1` 表示讀取端執行緒讀到 data~1~，也就是舊的資料，而 `p2` 表示讀取到 data~2~，即寫入端執行緒所「發布」的新資料。顯然在寫入端執行緒「發布」資料變更前，二個讀取端執行緒都看到 `p1`，但在前述「等待讀取端執行緒離開 critical section」的時期內，「訂閱」資料變更的二個讀取端執行緒分別看到 `p1` 和 `p2` 不同版本的結果，直到全部的讀取端執行緒都離開該時期後，才會全部看到 `p2`，即更新的資料，舊的 data~1~ 也才可安全地釋放資源。

RCU 可透過多種方式來實作，考慮下圖是其中一種實作:

上圖左上部分可見 [reference counting](https://en.wikipedia.org/wiki/Reference_counting) 的運用，注意 RCU 的實作可能全然沒有 [reference counting](https://en.wikipedia.org/wiki/Reference_counting)。讀取端執行緒藉由呼叫 `rcu_read_lock` 和 `rcu_read_unlock` 標注 CS 的範圍，我們從上圖可得知 `p1` 和 `p2` 分別被多少個讀取端執行緒觸及，當 `p1` 對應的 [reference counting](https://en.wikipedia.org/wiki/Reference_counting) 為零，即可安全地釋放該記憶體空間。

Linux 核心 RCU 為三種被保護的資料形態提供成對的 publish/subscribe/retract 介面，整理如下:

| 形態 | Publish | Subscribe | Retract |
|---|---|---|---|
| Pointer | `rcu_assign_pointer()` | `rcu_dereference()` | `rcu_assign_pointer(..., NULL)` |
| List | `list_add_rcu()`、`list_add_tail_rcu()`、`list_replace_rcu()` | `list_for_each_entry_rcu()` | `list_del_rcu()` |
| Hlist | `hlist_add_head_rcu()`、`hlist_add_before_rcu()`、`hlist_add_after_rcu()`、`hlist_replace_rcu()` | `hlist_for_each_entry_rcu()` | `hlist_del_rcu()` |

也就是說，發布與訂閱分別由「寫入端的 `*_rcu()` 變體」和「讀取端的 `*_rcu()` 走訪巨集」對齊，兩端都不取得 lock，而是以 `rcu_assign_pointer()` 的 release 與 `rcu_dereference()` 的 dependency ordering 形成 happens-before 關係。

`list_add_rcu()` 的實作直接展示這層配對 (取自 [include/linux/rculist.h](https://github.com/torvalds/linux/blob/master/include/linux/rculist.h))：

#define hlist_next_rcu(node)	(*((struct hlist_node __rcu **)(&(node)->next)))

static inline void __list_add_rcu(struct list_head *new,
		struct list_head *prev, struct list_head *next)
{
	if (!__list_add_valid(new, prev, next))
		return;

	new->next = next;
	new->prev = prev;
	rcu_assign_pointer(list_next_rcu(prev), new);
	next->prev = new;
}

static inline void list_add_rcu(struct list_head *new, struct list_head *head)
{
	__list_add_rcu(new, head, head->next);
}

注意先設定新節點的 `next`/`prev` 與後繼節點 `prev` 是 lock-free 的本地寫入，最後一筆 `rcu_assign_pointer(list_next_rcu(prev), new)` 才是真正的「發布」：在這一刻之前任何 RCU reader 看到的都是舊的 list 拓樸，之後則可能看到新節點。這條 release 配對讀取端的 `list_for_each_entry_rcu()` 內部的 dependency-ordered load。完整 API 整理可見 [Documentation/RCU/rcuref.rst](https://www.kernel.org/doc/html/latest/RCU/rcuref.html) 與 [Documentation/RCU/listRCU.rst](https://www.kernel.org/doc/html/latest/RCU/listRCU.html)。

## 顧及 [memory ordering](https://en.wikipedia.org/wiki/Memory_ordering) 的影響

現代編譯器通常會對程式碼進行一系列最佳化，CPU 也會在指令執行時進行調整 (reordering)，儘管手段不同，目的都是改進程式碼的執行效率，但這樣的最佳化有時會帶來非預期的結果。以往在讀取和寫入端都使用 lock 時，Linux 核心會在 lock 的取得與釋放邊界一併交代 [memory ordering](https://en.wikipedia.org/wiki/Memory_ordering) 議題，但在 RCU 中，讀取端不取得 lock，相關次序必須由 RCU API 自行擔當。

> 本節討論的 atomic 操作、release/acquire 配對、dependency-ordered load 等概念可參見〈[並行程式設計：atomic 操作](https://hackmd.io/@sysprog/concurrency-atomics)〉教材；該教材對 C11/C++ atomic、Linux 核心 `READ_ONCE` / `WRITE_ONCE` / `smp_load_acquire` / `smp_store_release` 與底層 CPU memory model 之間的對應有完整剖析，可作為閱讀本節的前置知識。

考慮以下程式碼:

void foo_update(foo *new_fp) {
    spin_lock(&foo_mutex);
    foo *old_fp = global_foo;
	
    new_fp->a = 1;
    new_fp->b = 'b';
    new_fp->c = 100;
	
    global_foo = new_fp;
    spin_unlock(&foo_mutex);
    synchronize_rcu();
    kfree(old_fp);
}

預期程式碼的第 5, 6, 7 行會在第 9 行之前執行，一如原始程式碼的閱讀順序，但最佳化之後的程式碼無法對執行順序 (order) 進行任何保證。這意味著，一個讀取端執行緒很可能讀到 `new_fp`，但 `new_fp` 的成員 (指 `a`, `b`, `c` 等變數) 數值指派尚未完成。當讀取端執行緒執行 `do_something(fp->a, fp->b , fp->c)` 時，就無法確定哪些實際傳遞到 `do_something` 函式，自然就可能造成非預期的執行結果，甚至致使程式崩潰。

解法之一是藉由 [memory barrier](https://en.wikipedia.org/wiki/Memory_barrier)，RCU 把細節包裝為一組專用巨集，於是上述的第 9 行不再是直接的指標數值指派，而改為以下:

    rcu_assign_pointer(global_foo, new_fp);

關於 `rcu_assign_pointer`，目前 Linux 主線版本 (參見 [include/linux/rcupdate.h](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/rcupdate.h)) 的形式如下:

#define rcu_assign_pointer(p, v)					      \
context_unsafe(								      \
    uintptr_t _r_a_p__v = (uintptr_t)(v);				      \
    rcu_check_sparse(p, __rcu);						      \
									      \
    if (__builtin_constant_p(v) && (_r_a_p__v) == (uintptr_t)NULL)	      \
        WRITE_ONCE((p), (typeof(p))(_r_a_p__v));			      \
    else								      \
        smp_store_release(&p, RCU_INITIALIZER((typeof(p))_r_a_p__v));	      \
)

要點有四:

- 編譯時期常數 NULL 走 `WRITE_ONCE` 快路徑，因為對 `NULL` 不存在「先寫成員、再發布指標」的順序需求
- 一般情境走 `smp_store_release(&p, ...)`：發布前所有寫入 (即 `new_fp->a/b/c` 的指派) 必須在外界看到新指標前完成，正是 RCU 的「發布」語意
- `RCU_INITIALIZER` 處理 `__rcu` 註記的型別轉換，搭配 [Sparse](https://www.kernel.org/doc/html/latest/dev-tools/sparse.html) 進行靜態檢查
- 外層 `context_unsafe(...)` 是新近引入的 Clang context-analysis 包裝 (取代過往 `do { ... } while (0)`)，用於 lockdep 與 `__rcu_guarded` 之類靜態驗證；不影響展開後的程式碼語意

> 延伸閱讀: [Linux Kernel Memory Barriers](https://www.kernel.org/doc/Documentation/memory-barriers.txt)

> 圖二: [Weak vs. Strong Memory Models](https://preshing.com/20120930/weak-vs-strong-memory-models/)

讀取端的成對問題在 weak memory model 的硬體 (歷史上以 DEC Alpha 最為極端) 會浮現 reordered dependent load (參見 [control](https://yarchive.net/comp/linux/locking.html)、[data](http://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html))。回顧稍早加入 RCU 的程式碼:

void foo_read(void) {		
    rcu_read_lock();
    foo *fp = global_foo;
    if (fp)
        do_something(fp->a, fp->b, fp->c);
    rcu_read_unlock();
}

第 5 行的 `fp->a, fp->b, fp->c` 在 weak memory model 的硬體中，可能在第 3 行載入 `global_foo` 之前就被 CPU 預先發出，當與 `foo_update` 同時執行，傳遞給 `do_something` 的部分欄位屬於舊版本、其餘屬於新版本，產生一致性錯誤。為此 Linux 核心在 [include/linux/rcupdate.h](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/rcupdate.h) 提供 `rcu_dereference()` 系列巨集，目前主線形式為:

#define rcu_dereference_check(p, c) \
    __rcu_dereference_check((p), __UNIQUE_ID(rcu), \
                            (c) || rcu_read_lock_held(), __rcu)

#define __rcu_dereference_check(p, local, c, space) \
({ \
    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)); \
})

#define rcu_dereference(p) rcu_dereference_check(p, 0)

幾項與舊文獻的差異值得留意:

- 暫存名稱由原本 `________p1` 改為 `__UNIQUE_ID(rcu)` 產生的唯一識別字 (避免巢狀展開時變數名衝突)，[commit 24ba530](https://github.com/torvalds/linux/commit/24ba53017e188e031f9cb8b290286fad52d2af00) 是最早一次清理
- 巨集本體已不見 `smp_read_barrier_depends()` 呼叫。前置工作是 Paul McKenney 在 Linux v4.15 (2018 年) 提交的 commit `76ebbe78f739` (`READ_ONCE` 內部隱含 `smp_read_barrier_depends`)；後由 Will Deacon 在 Linux v5.9 (2020 年) commit `93fab07c2293` 直接把 `smp_read_barrier_depends()` 介面從主線拔除。自此跨架構的 dependency-ordered load 統一以 `READ_ONCE` 表達；DEC Alpha 移植層在 `READ_ONCE` 內部追加 `smp_mb()` 補強，其餘架構則自然滿足 dependency ordering
- `RCU_LOCKDEP_WARN` 與 `rcu_check_sparse` 屬除錯期工具，搭配 lockdep 與 Sparse 偵測誤用情境

如此一來，我們可在稍早 `foo_read` 程式列表中，將

    foo *fp = global_foo;

更換為:

    foo *fp = rcu_dereference(global_foo);

即可由 `READ_ONCE`-based dependency ordering 保證讀取端看到的 `fp` 與其後的 `fp->a/b/c` 之間維持因果序，避開上述失序問題。

> 在 Linux v5.8 之前的核心程式碼註解中，`rcu_dereference()` 的化簡版常以 `smp_read_barrier_depends()` 呈現；閱讀舊文章或 LWN 文獻時請以此觀點解讀，不要套到目前主線。

## 資料讀取的完整性

前述「寬限期」與「訂閱—發布機制」說明 reader/writer 為何不必互鎖；本節聚焦於另一個容易被忽略的面向：list 新增與刪除節點時，指標調整的「順序」直接決定走訪中的 reader 是否還能完整逐節點走完整條 list。

考慮以下對 list 新增節點的案例:

我們在原有的 list 中，加入一個節點 `new` 到 `A` 節點之前，所要做的第一步是將 `new` 的指標指向 `A` 節點，第二步才是將 `Head` 的指標指向 `new`。其目的是當插入操作完成第一步時，對於 linked list 的讀取不產生影響，而執行完第二步時，讀取端執行緒若讀到 `new` 節點，也可繼續逐一走訪 list。

若把這個過程反過來，第一步 `Head` 指向 `new` 節點，這時若一個執行緒讀到 `new`，由於 `new` 的指標指向 `NULL`，將導致讀取端執行緒無法讀取到 `A`, `B`, `C` 等後續節點。

由上述分析可知，RCU 不保證讀取端執行緒一定能讀取到 `new` 節點。若該節點對程式產生影響，就要在呼叫端進行相應的調整：例如在檔案系統中，藉由 RCU 找到特定索引，若找不到對應的節點，便會進行其他形式的搜尋；相關內容於分析到檔案系統時再進行解析。

對 linked list 刪除節點的探討:

我們希望刪除 `B` 節點，就將節點 `A` 的指標指向 `C` 節點，保持 `B` 節點的指標，然後刪除程式將進入寬限期檢查。由於 `B` 節點的內容沒有變更，讀到 `B` 的執行緒仍可繼續讀取 `B` 的後續節點。`B` 不能立即銷毀，它必須等待寬限期結束後，才能進行相應銷毀操作。由於 `A` 節點已指向 `C` 節點，當寬限期開始後，所有的後續讀取操作藉由 `A` 節點找到的是 `C` 節點，而 `B` 節點已隱藏，後續的讀取端執行緒都不會讀到它。這樣就確保寬限期過後，刪除 `B` 節點不對系統造成衝擊。

在 Linux 核心中，RCU 用來保護以下情境:

- 指標
- linked list
- hlist (hash list)

Neil Brown 在 [Using RCU for linked lists — a case study](https://lwn.net/Articles/610972/) 提及特別的順序問題：插入時必須先把 `new` 的 `next` 指好，再以 `rcu_assign_pointer` 接上 `prev`；刪除時 `B` 節點的 `next` 在寬限期內不可被竄改，否則仍在走訪的讀取端將斷鏈。處理 fork/signal 等與 list 拓撲交織的事件時，必要的 ordering 是先讓子行程出現於 process group list，再對親代行程送 signal，否則 RCU 讀取端讀到的 list 與 signal 旗標將彼此矛盾。`hlist_nulls` 系列 (用於 networking connection tracking) 則允許 NULL 哨兵以「非真正的 NULL」表達節點被搬離的事實。

## 何時可銷毀舊資料？

「寬限期」一節以單一全域指標 `global_foo` 示範 `synchronize_rcu()` 的時序；本節改以多節點 list 為例，把同樣的「寬限期過後才釋放」原則套到刪除與替換兩種典型操作，重點在於走訪過程中新舊版本如何短暫並存。

考慮以下刪除特定 list 節點的程式碼:

struct foo {
    struct list_head list;
    int a, b, c;
};
LIST_HEAD(head);

p = search(head, key);
if (p) {
    list_del_rcu(&p->list);
    synchronize_rcu();
    kfree(p);
}

假設這個 list 初始狀態如下:
> $\uparrow$ 鏈結串列初始狀態

每個方框表示 list 的節點，其中三個數值分別代表上述程式碼 foo 結構體的 `a`, `b`, `c` 等成員的內含值。紅色邊框代表可能有讀取端執行緒持有它們的參照 (reference)，由於讀取端執行緒並未與寫入端執行緒同步，因此讀取端執行緒可能會和寫入端執行緒並行執行。

第 9 行的 `list_del_rcu` 執行結束後，原本的 `5`, `6`, `7` 自 list 移除，如下圖展示。因為讀取端執行緒並未和寫入端執行緒進行同步，可能會有讀取端執行緒正在逐一走訪 list。這些讀取端執行緒可能看到剛移除的資料，也可能看不到，取決於讀取端執行緒逐一走訪 list 和寫入端執行緒變更資料的時機。那些看到舊版 list 的讀取端執行緒，可能在資料自 list 移除後，仍讀取該資料。此時，`5`, `6`, `7` 的邊框仍是紅色，不同的讀取端執行緒看來，list 存在二個版本。
> $\uparrow$ 鏈結串列移除 `p` 之後

值得留意是，讀取端執行緒離開 CS 後，絕不允許再持有 list 任何節點的引用，也就是說，不允許再讀取 list 的節點。因為一旦上述程式碼的第 10 行 `synchronize_rcu` 執行完畢，意味著所有之前的讀取端執行緒都已離開 CS，沒有任何讀取端執行緒可能持有剛移除節點 `p` 的參照，下圖可見它改由黑色邊框標識，此時所有的讀取端執行緒看到的 list，又回歸為唯一的版本。
> $\uparrow$ 鏈結串列經歷寬限期之後

這時指標 `p` 指向的節點內容 `5`, `6`, `7` 終於可被安全釋放。

我們理解到藉由 RCU，可達到 lock-free 的操作。

延續前述 list 的案例，考慮 list 節點的變更，對應的程式碼如下:

q = malloc(sizeof(*p));
*q = *p; 
q->b = 2;
q->c = 3; 
list_replace_rcu(&p->list , &q->list);
synchronize_rcu();
free(p);

程式碼看似很短，但細節卻不能馬虎。

假設 list 起始的狀態如下圖:
> $\uparrow$ 鏈結串列初始狀態

第 1 行 `malloc` 配置一個待替換的節點，成功執行後的示意：
> $\uparrow$ 配置待替換的節點

第 2 行將舊節點內容複製給新節點:
> $\uparrow$ 複製舊節點的內容

第 3 行變更稍早建立新節點的成員 `b`，現值為 `2`
> $\uparrow$ 變更新節點內容

第 4 行變更節點成員 `c` 內容，現值為 `3`
> $\uparrow$ 變更新節點內容

第 5 行替換節點，此際新的節點可被讀取端執行緒看到。如下圖，此時 list 存在二個版本，之前讀取端執行緒可能看到 `(5, 6, 7)` 的資料組合，新的讀取端執行緒則看到 `(5, 2, 3)`，儘管數值可能不同，任何讀取端執行緒都看到一個可順利逐一走訪的完整 list。
> $\uparrow$ 替換節點

第 6 行 `synchronize_rcu` 執行後，會經歷寬限期，之後所有的在 `list_replace_rcu` 之前進入 CS 的讀取端執行緒都已完成讀取操作，並離開 CS，也不會有新的讀取端執行緒讀取 `(5, 6, 7)`，後者的節點也變為黑色方框，表示沒有任何資料參照。這時 list 回歸到唯一版本。
> $\uparrow$ 替換節點

第7 行 `free` 執行後，list 如下所示:
> $\uparrow$ 鏈結串列最終狀態

以上所有操作都不需要持有 lock，但衍生新的問題：何時可釋放 `p` 指向的節點？因為無法確認是否仍有其他執行緒在讀取該記憶體區塊。

我們可透過 POSIX Thread 嘗試在使用者層級實作上述的 RCU 流程，一樣針對鏈結串列進行操作，程式碼可參見 [rcu-list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu-list)。引入 zombie list 這個單向鏈結串列來追蹤 RCU list 中應當被釋放的節點。

延伸閱讀:
* [Multithreading Using Lockless Lists and RCU](https://www.copperspice.com/pdf/Multi-Threading-with-RCU-CppNow-2017.pdf)
* [Read, Copy, Update, then what? RCU for non-kernel programmers](https://youtu.be/rxQ5K9lo034)

在 [rcu-list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu-list) 中，可影響 RCU 實際表現的因素就是寬限期的設計。RCU 情境需要搭配記憶體回收機制，其中 QSBR (quiescent state-based reclamation) 和 EBR (epoch-based reclamation) 是經典的設計。

### QSBR 演算法

QSBR 的關鍵概念就是決定執行緒的不活動 (quiescent, /kwiˈes.ənt/ 但並非靜止停滯 [freeze]，而是漢語「靜默」和「平靜」的意涵) 狀態，那該如何辨別呢？該狀態和 CS 相對，執行緒一旦離開 CS 就歸類於靜默狀態。每個 reader 在離開 CS 時記錄一下自身狀態，writer 檢查這個狀態，當所有執行緒都離開 CS 時，就可釋放舊節點所在的記憶體。
> [例句](https://dictionary.cambridge.org/dictionary/english/quiescent): The political situation was now relatively quiescent.
> 可翻譯為「政治形勢目前暫時平靜」，但政治作為集體決策的過程，本身不會靜止，因此這裡說「暫時平靜」是指某段期間內不會有爭端或破壞政治角力的平衡，背後當然仍會暗潮洶湧。

識別靜默狀態的演算法可採取類似下圖標注 generation 或 epoch 的方式，藉由一組在執行時期嚴格遞增的數值，追蹤 $N$, $N+1$, $N+2$ 來判斷是否達到回收舊資料的條件。

識別出靜默狀態，還需要通知狀態資訊，讓其他執行緒知曉，整個過程可用下圖描述:

如圖可見 4 個執行緒，執行緒 `1` 執行完更新操作後，增添釋放記憶體的 callback，此時執行緒 `2`, `3`, `4` 讀取的都是之前的內容，等他們執行完成後分別回去呼叫 `onQuiescentState` 來表明自身已是靜默狀態，等到最後一個執行緒呼叫 `onQuiescentState` 時，就可呼叫之前註冊的 callback。要實作上面這個過程，其要點就是選擇適合的位置執行 `onQuiescentState`，還有如何知道誰是最後一個執行`onQuiescentState` 的執行緒。

另外還要考慮批量回收，情境是若更新的次數較多，每次只呼叫一個 callback 來釋放一次記憶體，就會導致記憶體釋放跟不上回收的速度，為此需要進行批量回收，也就是說，每次更新都會註冊新的 callback，當第一次所有的執行緒都進入靜默狀態時，就把目前的所有 callback 保存，等待下次所有執行緒進入靜默狀態時，就呼叫前次所有的 callback。

延伸閱讀:
* [Using Quiescent States to Reclaim Memory](https://preshing.com/20160726/using-quiescent-states-to-reclaim-memory/)

### Linux 核心以外的實作

[Userspace RCU](https://liburcu.org/) 將 RCU 自 Linux 核心抽離，並在使用者層級重新實作，不限於 Linux 作業系統，也可在 macOS 上執行。

[Userspace RCU](https://liburcu.org/) 提供若干 RCU 實作:
* `rcu-qsbr`: 效能最好的 RCU，可做讀取端執行緒近乎零執行成本，但需要變更程式碼邏輯
* `rcu-signal`: 效能次佳，不需要更動程式碼邏輯
* `rcu-generic`: 效能表現最差，但不需要變更程式碼，可作為 mutex 的替代

在一台 16 核處理器進行效能評比，橫軸是讀取端執行緒數量，縱軸為時間 (單位為秒):

圖解:
* `urcu_read_only` 只有讀取端執行緒，沒有資料寫入，效能表現最佳 (理想狀態)
* `urcu_qsbr_test` 採用 `urcu-qsbr`
* `urcu_signal_test` 採用 `urcu-signal`
* `urcu_generic_test` 採用 `urcu-mb`
* `single_mutex_test` 使用 mutex 來保護共用資料
* `mutex_per_thread_test` 是每個讀取端執行緒都獨占一個 mutex，寫入端執行緒需要獲取所有讀取端執行緒的 mutex，以進入 CS

可見到，QSBR 的效能最接近於 `read_only`，其次是 `signal`，他們都比 mutex 效能好，且時間並不隨讀取端執行緒數量增長而大幅增加，這也說明 RCU 在 scalability 的效益。

[DPDK](https://www.dpdk.org/) 的 RCU/QSBR 實作程式碼，由 Arm 公司貢獻:
* [lib/rcu/rte_rcu_qsbr.h](https://github.com/DPDK/dpdk/blob/main/lib/rcu/rte_rcu_qsbr.h)
* [lib/rcu/rcu_qsbr_pvt.h](https://github.com/DPDK/dpdk/blob/main/lib/rcu/rcu_qsbr_pvt.h)
* [lib/rcu/rte_rcu_qsbr.c](https://github.com/DPDK/dpdk/blob/main/lib/rcu/rte_rcu_qsbr.c)
* [app/test/test_rcu_qsbr.c](https://github.com/DPDK/dpdk/blob/main/app/test/test_rcu_qsbr.c)
* [app/test/test_rcu_qsbr_perf.c](https://github.com/DPDK/dpdk/blob/main/app/test/test_rcu_qsbr_perf.c)
> 延伸閱讀: [DPDK RCU 原始程式碼分析](https://www.jianshu.com/p/20137b59589b)

Arm 公司另外維護 [progress64](https://github.com/ARM-software/progress64):
> `qsbr`: safe object reclamation using quiescent state based reclamation
> properties: reader wait-free, writer blocking

Facebook 公司維護的 Folly 框架提供 C++ Template 的 RCU 實作: [folly::rcu_reader](https://github.com/facebook/folly/blob/master/folly/synchronization/Rcu.h)

## RCU 模型

回顧前述示意圖:

其中蘊含的 3 個重要概念:

- Removal: 在寫入端的 CS 中，進行讀取資料 (Read)、資料複製 (Copy)，並更改資料 (Update) 操作
- Grace Period: 一個等待時期，確保所有與執行刪除的資料相關的讀取端執行緒都可完成讀取
- Reclamation: 回收舊資料

靜默狀態 (quiescent state，QS) 是 CPU 證明「目前不在任何 RCU 讀取端 CS」的時間點；context switch 即是其中一種典型的 QS (CPU 切離原本 task 後，自然就不再持有任何 read-side 指標)。下圖展示寬限期內若干個 CPU 在不同時刻達成 QS:

寬限期 (grace period，GP) 指所有 CPU 都經歷靜默狀態所需的等待時間，也就是系統中所有讀取端執行緒都完成手中的 CS。寬限期狀態機示意如下:

digraph gp_fsm {
    rankdir = "TB";
    node [shape=box, style="rounded,filled", fillcolor="lightblue2", fontname="Helvetica"];
    Idle  [label="RCU Idle"];
    Init  [label="初始化 GP\n(rcu_gp_init)"];
    Wait  [label="等待 QS\n(force_qs / fqs)"];
    Pass  [label="CPU 經歷 QS\n(rcu_qs / rcu_note_context_switch)"];
    Done  [label="完成 GP\n(rcu_gp_cleanup)"];
    AllQS [label="所有 CPU 經歷 QS?", shape=diamond, fillcolor="khaki"];
    NeedNew [label="需要新的 GP?", shape=diamond, fillcolor="khaki"];
    Idle  -> NeedNew;
    NeedNew -> Init  [label="yes"];
    NeedNew -> Idle  [label="no"];
    Init  -> AllQS;
    AllQS -> Wait    [label="no"];
    Wait  -> Pass;
    Pass  -> AllQS;
    AllQS -> Done    [label="yes"];
    Done  -> Idle;
}

其原理是，讀取端 CS 保護並禁止其他 CPU 修改到指定區域，但允許多個 CPU 同時讀取:

### Reader / Updater / Reclaimer 三要素

3 個主要的參與者如下圖:

digraph rcu {
    rankdir = "LR";
    size = "6,4"; ratio = auto;
    node [color="lightblue2", style=filled, shape=box, fontname="Helvetica"];
    Updater   [label="Updater\nrcu_assign_pointer()\nlist_add_rcu()"];
    Reader    [label="Reader\nrcu_read_lock()\nrcu_dereference()\nrcu_read_unlock()"];
    Reclaimer [label="Reclaimer\nsynchronize_rcu()\ncall_rcu()"];
    Updater -> Reader    [label="publish"];
    Reader  -> Updater   [label="subscribe", style=dashed];
    Reader  -> Reclaimer [label="critical section"];
    Updater -> Reclaimer [label="defer-free"];
}

- reader: 安全地讀取 CS 資源，負責標識進出 CS
- updater: 複製一份資料，然後更新資料；用新資料覆蓋舊資料，然後進入寬限期
- reclaimer: 等待在寬限期之前的讀取端執行緒退出 CS；在寬限期結束後，負責回收舊資料

### 三大機制

《[What is RCU, Fundamentally?](https://lwn.net/Articles/262464/)》提煉的三大特性已散見於前文：
1. Publish-Subscribe Mechanism — `rcu_assign_pointer()` (release) 與 `rcu_dereference()` (dependency-ordered load) 配對；完整 memory ordering 推導見〈訂閱—發布機制〉與〈顧及 memory ordering 的影響〉
2. Wait For Pre-Existing RCU Readers to Complete — `synchronize_rcu()` (同步) / `call_rcu()` (非同步) 只等寬限期前已進入 CS 的讀取端；機制與時序見〈寬限期〉
3. Maintain Multiple Versions of Recently Updated Objects — 寬限期內新舊版本並存，待 pre-existing reader 全部離開才回收；list 的逐步圖示見〈資料讀取的完整性〉與〈何時可銷毀舊資料？〉

對應的長篇推導與形式化討論可參考《Is Parallel Programming Hard, And, If So, What Can You Do About It?》§9.5 (Paul E. McKenney)。

總結 RCU 關鍵概念:
- 讀取端執行緒 lock-free 讀取資料，標注進出 CS
- 寫入端 Read, Copy, Update：也就是 RCU 命名由來
- 舊資料延遲回收

## Tree RCU 實作主體

早期 Classic RCU 以全域 cpumask 紀錄哪些 CPU 經歷過靜默狀態，CPU 數一多，全域 lock 就成為主要 scalability 瓶頸。Paul McKenney 在 [Linux v2.6.29](https://lwn.net/Articles/305782/) (2009 年初) 合入 Tree RCU 程式碼，於 v2.6.30 成為預設組態：CPU 分組組成階層樹，群組內部共用較細粒度的 lock，群組向上匯報，整體 lock 競爭就被打散。

目前主線 (`kernel/rcu/tree.h`、`kernel/rcu/tree.c`) 的主要結構分三層:

digraph tree_rcu {
    rankdir = "TB";
    node [shape=record, style=filled, fillcolor="lightblue2", fontname="Helvetica"];
    rcu_state [label="{ struct rcu_state | gp_seq | gp_kthread | call | barrier_mutex | node[NUM_RCU_NODES] }"];
    rnode_l0  [label="{ struct rcu_node (level 0, root) | qsmask | gp_seq | parent=NULL }"];
    rnode_l1a [label="{ struct rcu_node (level 1) | qsmask | parent }"];
    rnode_l1b [label="{ struct rcu_node (level 1) | qsmask | parent }"];
    rdata_a   [label="{ struct rcu_data (per-CPU) | gp_seq | cblist (rcu_segcblist) | mynode | core_needs_qs }"];
    rdata_b   [label="{ struct rcu_data (per-CPU) | gp_seq | cblist | mynode | core_needs_qs }"];
    rcu_state -> rnode_l0;
    rnode_l0  -> rnode_l1a;
    rnode_l0  -> rnode_l1b;
    rnode_l1a -> rdata_a;
    rnode_l1b -> rdata_b;
}

- `struct rcu_state`: 全域狀態，紀錄目前寬限期序號 `gp_seq`、執行寬限期的核心執行緒 `gp_kthread`、回呼註冊介面 `call`，並擁有所有 `rcu_node` 的扁平陣列
- `struct rcu_node`: 樹的內部節點。每節點各自的 `lock` 只保護本節點的 `qsmask` (尚未報告 QS 的 CPU 位元圖)，CPU 達成 QS 後，由末端節點向上 propagate 到根節點，整個寬限期就此結束
- `struct rcu_data`: per-CPU，紀錄該 CPU 觀察到的 `gp_seq`、是否需要報告 QS (`core_needs_qs`)、所屬 `rcu_node` (`mynode`)，以及待回收 callback 的 `rcu_segcblist`。callback 鏈以分段方式管理，分為 `RCU_DONE_TAIL`、`RCU_WAIT_TAIL`、`RCU_NEXT_READY_TAIL`、`RCU_NEXT_TAIL` 四段，依據寬限期推進順序前移

寬限期的推進由 `rcu_gp_kthread` 核心執行緒驅動，主要工作有三:

1. 開啟新寬限期，呼叫 `rcu_gp_init()` 將 `gp_seq` 推進並重置 `qsmask`
2. 在睡眠等待期間，若超時則透過 `force_qs_rnp()` 主動巡視 CPU，觸發 IPI 取得未報告的 QS
3. 寬限期結束時呼叫 `rcu_gp_cleanup()`，喚醒等待的 reclaimer，把 `RCU_WAIT_TAIL` 的 callback 推進到可呼叫狀態

CPU 端則在以下三類事件中報告 QS:

- 進入 user space (時鐘 tick 偵測 `user_mode(regs)`)
- 進入 idle loop (`rcu_idle_enter()` / `tick_nohz_idle_enter()`)
- context switch (`rcu_note_context_switch()`)

回呼真正執行的時機落在 `RCU_SOFTIRQ` 軟體中斷 (`rcu_core_si()`) 或 per-CPU 核心執行緒 `rcu_cpu_kthread`，後者在 `CONFIG_RCU_BOOST` 或 `rcu_nocbs=` 情境下會被選中，避免和高優先序軟中斷打架。

### 排程器事件與 QS 來源

RCU 的寬限期推進完全寄生於 scheduler 的事件流。理解 RCU 的延遲特性，須先理解 Linux 排程器在何種時機產生 context switch、tick、idle entry 等 QS 證據。三份教材分別從不同角度展開這個前置知識：

- [Linux 核心設計: CPU 排程器](https://hackmd.io/@sysprog/linux-scheduler)：CFS/EEVDF 排程類別、run queue 結構、`pick_next_task()` 的決策時機 — 對應 RCU 何時能取得 context switch 形態的 QS
- [Linux 核心設計: 搶佔機制](https://hackmd.io/@sysprog/linux-preempt)：`preempt_count`、`TIF_NEED_RESCHED` 與 PREEMPT_NONE / VOLUNTARY / FULL / RT / DYNAMIC / LAZY 各模式 — 直接決定上述三類 QS 事件的觸發頻率
- [Linux 核心設計: 行程管理](https://hackmd.io/@sysprog/linux-process)：`task_struct`、thread group、fork / exit 路徑 — 對應 RCU 在 `current->rcu_read_lock_nesting`、`rcu_node->blkd_tasks` 與 Tasks RCU「等所有 task 自願切換一次」的設計依據

下方要點整理排程模式對 RCU 的影響：

- `PREEMPT_NONE` / `VOLUNTARY`：context switch 主要發生在系統呼叫返回與顯式 `cond_resched()`。長時間在核心模式運算的 task 不會自動讓出，FQS 只能仰賴 tick；對應到實驗 3 中 `synchronize_rcu_normal` 的 16–32 ms 量級
- `PREEMPT` (full)：`preempt_count` 為 0 且 `TIF_NEED_RESCHED` 設位即搶占，context switch 頻率高、QS 報告密集
- `PREEMPT_RT`：spinlock 多數轉為可阻塞的 rt_mutex；RCU 仍要求讀取端不可顯式 sleep，但對因 PI 而隱式阻塞的 task，由 `boost_task` 機制提升優先順序，避免讀取端被低優先順序 task 拖住
- `PREEMPT_DYNAMIC` (Linux v5.12+，commit `826bfeb37bb4`)：開機期可在 none/voluntary/full 之間切換 (`/sys/kernel/debug/sched/preempt`)，但 RCU flavor 仍由編譯時期 `CONFIG_PREEMPT_RCU` 決定，runtime 不會跟著切換；改變的只是 context switch 的觸發頻率，連帶影響 GP 完成的尾端延遲
- `PREEMPT_LAZY` (Linux v6.13+)：新增 `TIF_NEED_RESCHED_LAZY`，把 SCHED_NORMAL task 的搶占延後到返回 user mode 才生效；但下一次 scheduler tick 會把 LAZY 旗標升格為一般 `TIF_NEED_RESCHED`，因此延遲有上界。RCU 自己仍透過 `set_need_resched_current()` 直接設定一般 `TIF_NEED_RESCHED`，QS 語意未變；若 task 長時間在 kernel space 運算，FQS 仍會經 IPI 催促

cond_resched 與 RCU 的歷史值得釐清：早期主線曾以 `cond_resched_rcu_qs()` 強制讀取端在禮貌讓出時也報告 QS；2018 年 commit `cee439398933` 將其改名為 `cond_resched_tasks_rcu_qs()`，並把語意縮小為僅給 Tasks RCU 用。一般路徑的 `cond_resched()` 自此不再呼叫 `rcu_qs()` — 它只是觸發排程器，QS 仍由後續的 `rcu_note_context_switch()` 報告。實驗 5 中 224-CPU 主機觀察到 context switch QS 數量低於 tick QS 即印證：絕大多數讀取端離開仰賴 tick 周期性檢查、而非主動讓出。

[Hierarchical RCU](https://lwn.net/Articles/305782/) (2008 年) 道出設計動機：Classic RCU 的 `rcu_ctrlblk->lock` 在 4096 CPU 規模成為 contention 熱點，Tree RCU 改以 `CONFIG_RCU_FANOUT` (64 位元核心預設 64，範圍 2–64；32 位元核心預設 32，範圍 2–32) 將末端節點 CPU 群分組，每群只有最後一位完成 QS 的 CPU 取得上層 `rcu_node->lock`，使全域 lock 競爭從 $O(N_\text{CPU})$ 降到 $O(\log N_\text{CPU})$。

> Liang、McKenney、Kroening、Melham 在 DATE 2018 發表 [Verification of Tree-Based Hierarchical Read-Copy Update in the Linux Kernel](http://www.kroening.com/papers/date2018-rcu.pdf)，將 Linux v4.3.6 Tree RCU 直接由 C 原始碼 (合計 8,626 行模型) 餵入 [CBMC](https://www.cprover.org/cbmc/) 進行 bounded model checking，驗證 safety 與 liveness 性質。這是首次對 Linux 核心 RCU 真實實作 (而非語言層級簡化版) 進行的形式化驗證，亦是 [srcu-cbmc](https://github.com/torvalds/linux/tree/master/tools/testing/selftests/rcutorture/formal/srcu-cbmc) 進入主線的前身。

### 啟動期初始化與 force-quiescent-state

開機時序中 `start_kernel()` 會呼叫 `rcu_init()`，此入口依組態分流到 [`kernel/rcu/tiny.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/rcu/tiny.c) (`CONFIG_TINY_RCU=y`，UP 系統) 或 [`kernel/rcu/tree.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/rcu/tree.c) (`CONFIG_TREE_RCU=y`)。Tree RCU 的初始化主要做三件事：

1. `rcu_init_geometry()`：依 `nr_cpu_ids` 與 `CONFIG_RCU_FANOUT_LEAF` 動態決定樹的高度和每層的 `rcu_node` 數量。`rcu_capacity[i]` 紀錄第 `i` 層能容納的 CPU 數，從葉端 `rcu_capacity[0] = rcu_fanout_leaf` 起，每層乘以 `CONFIG_RCU_FANOUT` 直到 ≥ `nr_cpu_ids`，最高 4 層
2. `rcu_init_one(&rcu_state)`：把上一步算出的拓樸寫入 `rcu_state.node[]` 陣列、設定每個 `rcu_node->parent`、初始化 per-CPU 的 `rcu_data`
3. `open_softirq(RCU_SOFTIRQ, rcu_core_si)`：將 `RCU_SOFTIRQ` 向量綁定到 `rcu_core_si()` 處理函式 (詳見實驗 2)

執行期還有一個 watchdog 機制 force-quiescent-state (FQS)：`rcu_gp_kthread` 在 `swait_event_idle_timeout_exclusive()` 上睡眠等待，醒來若仍有 CPU 未報告 QS，便呼叫 `force_qs_rnp()` 走訪 `rcu_node` 樹、向落後的 CPU 送 IPI 索取 QS。等待間隔由兩個 sysfs tunable 控制：

/* kernel/rcu/tree.c 預設值 */
jiffies_till_first_fqs = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
jiffies_till_next_fqs  = jiffies_till_first_fqs;
/* RCU_JIFFIES_TILL_FORCE_QS = 1 + (HZ > 250) + (HZ > 500) */
/* RCU_JIFFIES_FQS_DIV = 256 */

對 `HZ=1000`、224 CPU 的本機而言，因整數除法 `224 / 256 == 0`，`jiffies_till_first_fqs = 3 + 0 = 3 jiffies` (HZ=1000 下約 3 ms)：寬限期啟動 3 ms 後，若仍有 CPU 沒在 tick 或 context switch 報告 QS，FQS 就會啟動催促。`/sys/module/rcutree/parameters/jiffies_till_first_fqs` 可在執行時調整。

> linux-insides 的 [Linux kernel initialization process — RCU initialization](https://0xax.gitbook.io/linux-insides/summary/initialization/linux-initialization-9) 與 [Synchronization primitives](https://0xax.gitbook.io/linux-insides/summary/syncprim) 章節對 `rcu_init()` 與 `softirq_action` 的內部結構有更鉅細靡遺的逐行解說 (取自較早期 Linux 版本，當時 `rcu_bh_state` 與 `rcu_sched_state` 仍未統合)。

## RCU 變體

主線目前同時維護多種 RCU flavor 與 read-side 介面，依照 read-side 是否容許搶占與睡眠來分類:

| Flavor | Read-side 介面 | Wait 介面 | Read-side 限制 | 主要用途 |
|---|---|---|---|---|
| Classic RCU (`!CONFIG_PREEMPT_RCU`) | `rcu_read_lock()` (= `preempt_disable()`) | `synchronize_rcu()`、`call_rcu()` | 不可搶占、不可顯式 sleep | 一般 read-mostly 結構 |
| Preemptible RCU (`CONFIG_PREEMPT_RCU`) | `rcu_read_lock()` 走 `__rcu_read_lock()` 增加 `current->rcu_read_lock_nesting`；被搶占時 task 掛入 `rcu_node->blkd_tasks` 等回到 CS 後再回報 QS | 同上 | 可搶占；不可顯式 sleep (`PREEMPT_RT` 下因 PI spinlock 變 rt_mutex 而隱式阻塞屬例外，由 RCU 加入 priority boost 補償) | `PREEMPT_RT` 與低延遲情境 |
| RCU-bh / RCU-sched (歷史名稱，lockdep 標註) | `rcu_read_lock_bh()` (關閉 bottom half) / `rcu_read_lock_sched()` (= `preempt_disable()`) | 統合到 `synchronize_rcu()`；自 v4.20 起，`synchronize_rcu()` 同時等待 `preempt_disable()` 與 `local_bh_disable()` 區段 | 同 read-side 函式語意 | 保留作為 lockdep 友善的讀取端標注 (例如 networking softirq、scheduler 路徑) |
| SRCU | `srcu_read_lock(&ss)` | `synchronize_srcu(&ss)` | 可睡眠；需要 per-domain `srcu_struct` | 慢路徑、可睡眠的 reader |
| SRCU-NMI | `srcu_read_lock_nmisafe()` | 同 SRCU | NMI 安全，使用 atomic counter | NMI handler、`printk` backtrace |
| Tasks RCU | 隱式 | `synchronize_rcu_tasks()` | 等所有 task 至少自願切換一次 | trampoline (BPF、ftrace) |
| Tasks-Trace RCU | `rcu_read_lock_trace()` | `synchronize_rcu_tasks_trace()` | 容許睡眠的 read-side，配合 ftrace/BPF | sleepable BPF |
| Tasks-Rude RCU | 隱式 | `synchronize_rcu_tasks_rude()` | 透過 `schedule_on_each_cpu(rcu_tasks_be_rude)` 在每個 online CPU 上排程一份空工作，藉由必經的 context switch 完成 GP；不要求讀取端做任何標記 | momentary trampoline 移除、ftrace 過渡 |

> Linux v4.20 (2018 年) Paul McKenney 把 RCU-sched 與 RCU-bh 合併為單一的「RCU」介面，僅保留 `rcu_read_lock_bh()` / `rcu_read_lock_sched()` 作為 lockdep 友善的 read-side 標注；它們的等待端統一導向 `synchronize_rcu()`。

### SRCU：可睡眠 RCU 的內部設計

Classic / Preemptible RCU 嚴禁讀取端 sleep，因為它們以「全系統共用一個 GP」為前提：任一個讀取端拖延都會延遲所有 RCU callback 的回收。SRCU (Sleepable RCU，Linux v2.6.19 引入，v2.6.23 補完，2014 年由 Paul McKenney 重寫為 Tree SRCU) 為了放寬這條限制，做了三個結構性決定：

- per-domain GP：每個 SRCU 使用者持有獨立的 `struct srcu_struct`，子系統 A 的 reader 拖延只會延遲 A 自身的 callback，不會牽連其他子系統
- 不提供 `call_srcu()` 早期版本：強制走同步 `synchronize_srcu()`，藉阻塞呼叫端壓抑請求數量 (現代主線已補上 `call_srcu()`，但仍鼓勵同步使用)
- per-CPU 計數器配對：以兩個 per-CPU counter `c[0]` / `c[1]` 交替標示 current 與 next-pending GP，配合 `srcu_struct->completed` (現主線改名為 `srcu_struct->srcu_idx`) 的 LSB 決定當下用哪一個

digraph srcu_counter_toggle {
    rankdir = "LR";
    node [shape=box, style="rounded,filled", fontname="Helvetica"];

    completed [label="srcu_struct->srcu_idx\nLSB 決定 current 計數器", fillcolor="khaki"];

    subgraph cluster_pcpu {
        label = "struct srcu_data (per-CPU)";
        style = filled; fillcolor = "#e8f0ff";
        c0 [label="c[0]\n(可能是 current)", fillcolor="lightblue2"];
        c1 [label="c[1]\n(可能是 next-pending)", fillcolor="lightblue2"];
    }

    completed -> c0 [label="LSB=0 時選此", color="firebrick"];
    completed -> c1 [label="LSB=1 時選此", color="firebrick"];

    reader [label="srcu_read_lock(ss)\n回傳 idx (=srcu_idx & 0x1)\nthis_cpu_inc(c[idx])", fillcolor="lightgreen"];
    unlock [label="srcu_read_unlock(ss, idx)\nthis_cpu_dec(c[idx])", fillcolor="lightgreen"];
    sync [label="synchronize_srcu(ss)\n1. flip srcu_idx (++) — 後續 reader 改入新 c[]\n2. 等舊 c[] 的全 CPU 加總歸零", fillcolor="lightcoral"];

    reader -> c0 [style=dashed, label="加 1"];
    reader -> c1 [style=dashed, label="或加 1"];
    sync -> completed [color="firebrick"];
}

讀寫流程：

- `srcu_read_lock(ss)` 取得 `srcu_idx & 0x1` 作為 `idx`、對 `c[idx]` 自增；返回值 `idx` 必須沿用至 `srcu_read_unlock(ss, idx)`，因為呼叫期間 writer 可能已 toggle，下一次新 reader 會落到另一個 counter
- `synchronize_srcu(ss)` 先把 `srcu_idx` 加 1 (toggle)，使後續新 reader 進入「另一個」counter；再對所有 CPU 上的舊 counter 求和，等到歸零代表寬限期前已存在的 reader 全部離開，即可返回
- 因為新 reader 全部落在新 counter、不影響舊 counter 的歸零判斷，SRCU 寬限期可以等待任意長 (包含 reader sleep) 而不阻塞新 reader 進入 CS

這個設計把 RCU 的「寬限期」從全系統共用拆解為 per-domain，並用 counter toggle 取代 context switch / tick 作為 QS 證據，因此讀取端可放心 sleep。代價是寫入端必須走完整 atomic 加總路徑，比 Classic RCU 慢 (典型量級 µs vs ns)。Tree SRCU (v3.14+) 進一步把全 CPU 加總改為階層式，類比 Tree RCU 的 fanout 結構。詳細實作演進可參見 [Documentation/RCU/srcu.rst](https://www.kernel.org/doc/html/latest/RCU/srcu.html)。

### 寬限期等待的進階介面

| 介面 | 行為 |
|---|---|
| `synchronize_rcu()` | 阻塞直到目前寬限期結束 |
| `synchronize_rcu_expedited()` | 對所有 non-idle CPU 送 async IPI 促其儘快進入 QS (而非保證當場完成)，延遲低但 CPU 開銷高 |
| `call_rcu(head, func)` | 非同步註冊回呼，寬限期結束後由 `rcu_core()` 執行 (透過 `RCU_SOFTIRQ` 或 `rcuc/%u` kthread)；若該 CPU 走 nocb 路徑且 `CONFIG_RCU_LAZY=y` 並啟用 (見後文)，回呼可延遲到 `LAZY_FLUSH_JIFFIES` 之後再批次執行 |
| `call_rcu_hurry(head, func)` | 強制走非 lazy 路徑，並順手 flush 既有的 lazy callback 批次；模組卸載、`rcu_barrier()` 等不能等 lazy 排程的情境應使用此 API |
| `kfree_rcu(ptr, rhf)` | 不需自寫 callback 即可釋放結構；分為 SLAB bulk、vmalloc bulk、linked list 三條通道，最終經 workqueue 釋放 |
| `kfree_rcu_mightsleep(ptr)` | head-less 單參數變體 (`#define kfree_rcu_mightsleep(ptr) kvfree_rcu_arg_1(ptr)`)，呼叫者必須在可睡眠的 context；GP 結束後以 `kvfree()` 釋放整個 `ptr`，不需在物件內嵌 `struct rcu_head` |
| `get_state_synchronize_rcu()` / `poll_state_synchronize_rcu(cookie)` | 取得寬限期 cookie，事後輪詢檢查是否已過 GP，避免阻塞 |
| `cond_synchronize_rcu(cookie)` | 若 cookie 標示之 GP 尚未結束則阻塞，否則立即返回 |
| `rcu_barrier()` | 等所有已註冊 `call_rcu` 回呼皆執行完畢，模組卸載前必備 |

`rcu_nocbs=` 開機參數可把指定 CPU 的回呼處理外移到 `rcuog`/`rcuop` 核心執行緒，避免 `RCU_SOFTIRQ` 干擾 latency-critical 任務；`rcupdate.rcu_expedited=1` 則在開機階段把所有寬限期都改走 expedited 路徑，加速大型機器啟動。

Lazy RCU 是 Joel Fernandes 在 Linux v6.2 (2023 年，commit `3cb278e73be5`) 引入的機制，僅作用於 nocb (offloaded) callback 路徑：當 CPU 已透過 `rcu_nocbs=` 啟用 callback 卸載時，`call_rcu()` 註冊的回呼可延後到 `LAZY_FLUSH_JIFFIES (10 * HZ)` 之後批次執行，省電情境可顯著降低 `rcuog` 喚醒次數。Linux v6.8 (commit `7f66f099de4d`) 補上 `rcutree.enable_rcu_lazy` 開機參數與 `CONFIG_RCU_LAZY_DEFAULT_OFF`，讓發行版得以預設關閉此行為；上游 Kconfig help 明寫此特性建議搭配 `rcu_nocbs=all` 使用 (定義見 [`kernel/rcu/tree_nocb.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/rcu/tree_nocb.h))。對 latency-critical 路徑，請改呼叫 `call_rcu_hurry()` (走非 lazy 並 flush 既有批次)。Documentation/RCU/ 的 [whatisRCU.rst](https://www.kernel.org/doc/html/latest/RCU/whatisRCU.html)、[checklist.rst](https://www.kernel.org/doc/html/latest/RCU/checklist.html) 是最權威的當代 API 一覽。

## 對比其他 lock-free 同步機制

取自 [Proposed RCU C++ API](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0461r1.pdf) 和 [Folly](https://github.com/facebook/folly/blob/master/folly/synchronization/Rcu.h) 的表格:

| | [Reference Counting](https://en.wikipedia.org/wiki/Reference_counting) | RCU | [Hazptr](https://en.wikipedia.org/wiki/Hazard_pointer) |
|:----------------:|:------------------:|:---:|:------:|
| Unreclaimed objects | Bounded | Unbounded | Bounded |
| Contention among readers | High | None | None |
| Traversal forward progress | lock-free | wait-free | lock-free |
| Reclamation forward progress | lock-free | blocking | wait-free |
| Traversal speed | atomic | no-overhead | folly's is no-overhead |
| Reference acquisition | unconditional | unconditional | conditional |
| Automatic reclamation | yes | no | no |
| Purpose of domains | N/A | isolate slow reader | configuration |

通用 [concurrency control](https://en.wikipedia.org/wiki/Concurrency_control) 的討論: (並行允許許多交易得以在同一時間存取同一筆資料，而並行控制則要讓這些交易不會互相干擾)
* [Is RCU a generic concurrency control?](https://concurrencyfreaks.blogspot.com/2019/10/is-rcu-generic-concurrency-control.html)
* [How about RLU? Is RLU a generic concurrency control?](https://concurrencyfreaks.blogspot.com/2019/10/how-about-rlu-is-rlu-generic.html)

## 應用案例彙整

Christian Bewermeyer 在 [Applications of RCU (FAU Erlangen-Nürnberg, 2017)](https://www4.cs.fau.de/Lehre/SS17/V_AKSS/Ausarbeitungen/bewermeyer.pdf) 整理了 RCU 在實際系統的部署樣貌。以下擷取本文先前未涵蓋的情境並交叉核實，部分敘述距今近十年需要修正。

### 何時值得採用 RCU

Paul McKenney 等人在〈[Read-Copy Update](http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf)〉(OLS 2001) 給出量化判準：
$$
f \ll \frac{1}{n_{\text{CPU}}}
$$

其中 $f$ 是更新次數佔總存取的比例，$n_{\text{CPU}}$ 是系統 CPU 數量。8 個 CPU 核的系統需要 $f \ll 0.125$ (即更新比例顯著低於 12.5%)，本文實驗的 ThunderX2 (224 logical CPU) 把判準推至 $f \ll 0.0045$。一旦更新比例稍高，寬限期延遲 (數毫秒到數十毫秒) 就會主宰整體效能，這時 `seqlock_t`、`rwlock_t` 或 hazard pointer 通常更適合。

採用 RCU 的運行成本 (前提之外的代價，與〈為什麼選 RCU〉的三條結構前提互補)：
- 讀取端看到的可能是更新前的快照 (寬限期內舊版仍合法)；應用必須容忍 stale read，或於讀取端自行加上版本/旗標檢查
- 寬限期內新舊版資料並存，記憶體佔用暫時翻倍；資料越大、更新越頻繁，footprint 放大越明顯
- 即使滿足量化門檻，每筆寫入端的 `synchronize_rcu()` 仍要付出實驗 U3 量到的「reader CS 時間 + ~100 µs」延遲；對寫入端延遲敏感者，請改走 `call_rcu()` 非同步路徑 (見實驗 U5)

### Linux 核心內的指標性案例

NMI handler 註冊表已於本文「概念」節介紹，是 RCU 在核心最直觀的範例。下列案例則代表 RCU 在生產系統中真正承擔擴充性的情境，每例皆附「若不用 RCU」的衝擊評估，藉以量化「為何這些路徑非 RCU 不可」。

dentry cache 與 RCU-walk
- 位置：[`fs/dcache.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/fs/dcache.c)、[`fs/namei.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/fs/namei.c) 的 `__d_lookup_rcu()` 與 `walk_component()`；Nick Piggin 在 Linux v2.6.38 (2011 年) 引入。RCU-walk 模式下，`walk_component()` → `lookup_fast()` → `__d_lookup_rcu()` 走父 dentry 的 hash chain (`dentry_hashtable`) 完成 lockless 名稱比對，遇 mountpoint 或符號連結才回退到 ref-walk
- 不用 RCU 的衝擊：path resolution 是任何 `open()` / `stat()` / `getdents()` 的必經路徑，伺服器級工作負載每秒上百萬次。改回 v2.6.38 之前的 `dentry->d_lock` 路徑會讓鎖計數器在多 CPU 之間反覆 invalidate；Nick Piggin 的 [RCU pathname walk 提案](https://lwn.net/Articles/394762/) 在 8 核心已量到顯著加速，CPU 數越大效益越突出

網路收封包路徑：FIB / netfilter / socket lookup
- 位置：[`net/ipv4/fib_trie.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/net/ipv4/fib_trie.c) 的 LC-trie 路由表、`net/netfilter/` 的規則表、`net/ipv4/inet_hashtables.c` 的 socket lookup，全部以 `rcu_read_lock_bh()` / `rcu_dereference_rtnl()` 走訪。McKenney 2012 [RCU usage in the Linux kernel: One decade later](http://www.rdrop.com/users/paulmck/RCU/RCUusage.2013.02.24a.pdf) 統計顯示 networking 是核心內 RCU 用量最高的子系統
- 不用 RCU 的衝擊：10 GbE 線速小封包約 14 Mpps、100 GbE 達 148 Mpps，每個封包皆需查路由表與 netfilter 規則。改用 rwlock_t，N 個 CPU 同時執行 forwarding 時，rwlock 讀取端的 atomic counter 即〈為什麼選 RCU〉節描述的 cache-line bouncing 災情。早期 `fib_hash_lock` 即為 `rwlock_t`，直到 2010 年 Eric Dumazet 以 commit `ebc0ffae5d77` 為代表的一系列改造把 `fib_lookup()` 路徑轉為 RCU；當時 multi-Gbps 路由器難以單機架構，正是促成 RCU 在 networking 鋪開的歷史驅力。實驗 U4 中 rwlock 在 224 reader 下總吞吐 3 M/s 即此情境的縮影
- 反過來說：iptables/nftables 的規則更新走 `synchronize_rcu()` 等寬限期，這也是大型雲端環境一次推送幾千條規則需要 ~50–200 ms 的根因；多版本並存避免封包流量被卡住

System V IPC (semget / shmget / msgget)
- 位置：[`ipc/util.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/ipc/util.c) 的 `ipc_ids` 走 RCU。Andrea Arcangeli、Mingming Cao、Paul McKenney、Dipankar Sarma 在 [Using Read-Copy-Update Techniques for System V IPC in the Linux 2.5 Kernel (USENIX FREENIX 2003)](http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf) 把原本的 rwlock 換成 RCU
- 不用 RCU 的衝擊：Oracle、Postgres 等資料庫高度依賴 System V semaphore；上述論文記錄當時 `struct ipc_ids` 的 `ary` 欄位 (與 `newary` 配置路徑) 為主要熱點。若改回 rwlock，reader 之間爭搶同一條 cache line，semaphore 操作率被 lock 競爭上限封頂，OLTP 工作負載的 CPU scaling 曲線將從接近線性退化為飽和、甚至下降

fdtable / file descriptor lookup
- 位置：[`fs/file.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/fs/file.c) 的 `__fget_files_rcu()` / `lookup_fdget_rcu()`；`include/linux/fdtable.h` 的 `files_struct->fdt`。Dipankar Sarma 在 2005-09-09 提交 `[PATCH] files: files struct with RCU` (commit `ab2af1f5...`)，自 Linux v2.6.12 起 `fdtable` 由 RCU 保護
- 不用 RCU 的衝擊：每個 `read()` / `write()` / `epoll_wait()` 都要先把 fd 轉成 `struct file *`。Linux 重 I/O 工作負載 (例如 nginx + epoll、io_uring) 單核可達 10M syscall/s。若改用 spinlock 保護 `fdtable`，同 process 多 thread 並行 syscall 時讀取端互相阻塞；改用 atomic_t refcount 雖不阻塞，但每次 lookup 必然觸發 cache line bouncing — 兩種方案都會讓 syscall hot path 喪失可擴充性
- 多版本的價值：當行程做 `dup2()` 或 fdtable resize 時，writer 配置新 fdtable、`rcu_assign_pointer` 切換、`call_rcu` 釋放舊版；在這之間正在跑的 `read(fd)` 仍合法持有舊 fdtable 並完成 lookup，不需停下來等

/proc/PID 與 task_struct lookup
- 位置：[`kernel/pid.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/pid.c) 的 `find_pid_ns()` / `find_task_by_pid_ns()` 強制要求 `rcu_read_lock_held()` (commit `RCU_LOCKDEP_WARN`)；signal 投遞、`kill()`、`/proc/*` 走訪皆走此路徑
- 不用 RCU 的衝擊：上述操作早期由全域 `tasklist_lock` (rwlock_t) 保護。一台 1000+ task、100+ CPU 的伺服器，ps/top/htop 等監控工具持續掃 /proc，加上 systemd cgroup 統計、container runtime 探針、Prometheus node_exporter — 任何一個都可能在 hot path 取讀鎖。`tasklist_lock` 寫入端 (fork、exit、signal 群組變動) 必須等所有讀取端離開才能更新，造成 latency spike；改成 RCU 後寫入端只需 `rcu_assign_pointer` 即可繼續，讀取端完全無阻塞

BPF program 與 BPF map 執行
- 位置：[`include/linux/bpf.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/bpf.h) 的 `bpf_prog_run_array()` 以 `RCU_LOCKDEP_WARN(!rcu_read_lock_held(), ...)` 強制 caller 持 RCU 讀鎖；sleepable BPF (uprobe / fentry on faulting code) 走另一條入口 `bpf_prog_run_array_uprobe()`，改以 `RCU_LOCKDEP_WARN(!rcu_read_lock_trace_held(), ...)` 要求 [Tasks-Trace RCU](https://www.kernel.org/doc/html/latest/RCU/checklist.html) 讀鎖
- 不用 RCU 的衝擊：bpftrace、bcc、cilium 等工具動輒對 kprobe / tracepoint / sched event 掛 BPF；單個 tracepoint 在生產環境每秒可觸發數百萬次。BPF program 的更新 (replace、attach/detach) 採 `rcu_assign_pointer`；改成 spinlock，每個 trace event 都需取鎖，等同把整個 tracing 框架的觀測 overhead 翻數倍 — 直接違背 BPF「低開銷觀測」的設計初衷。亦因此，BPF 的 reader 端必然要走 RCU，map 操作的 helper (例如 `bpf_map_lookup_elem`) 才能維持 wait-free

netfilter conntrack 與 atomic notifier chain
- 位置：[`kernel/notifier.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/notifier.c) 的 `atomic_notifier_chain_register()` 以 `rcu_assign_pointer` 發布新 callback、`atomic_notifier_call_chain()` 在 `rcu_read_lock()` / `rcu_read_unlock()` 之間走訪 callback list；netfilter conntrack 另以 `nf_conntrack_lock` 配合 RCU 保護 hash table。CPU hotplug、suspend/resume、network device 上下、battery 事件等都走 atomic notifier chain
- 不用 RCU 的衝擊：notifier delivery 在中斷 context 與 atomic context 觸發；改用 spinlock 等於要求 callback 在拿著一把全域鎖的情況下執行 — 任何阻塞或長時間運算就把整個事件分發路徑卡住，嚴重時整台機器無法 suspend、無法 hotplug CPU

歷史校正：模組卸載常被列為 RCU 案例 (Bewermeyer 論文亦循此敘述)，但需要釐清：模組存活仍由 `atomic_t refcnt` 配合 `try_module_get()` / `module_put()` 控制，RCU 在卸載路徑只負責「等所有進入模組程式碼的 read-side CS 退出」，二者互補而非取代。

總結而言，上述案例構成現代 Linux 核心 read-mostly 路徑的骨幹。設想若一夕之間把 RCU 從核心拔除而僅以 rwlock_t 替換，多 CPU 伺服器的 syscall throughput、網路 forwarding rate、資料庫 OLTP 都將回退到十年前甚至更早的水準；寫入端的寬限期延遲也會被 rwlock 的 reader 阻塞放大為 latency spike。這正是 [perfbook §9.5 RCU Usage](https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html) 所要彰顯的：RCU 並非眾多同步機制中的另一個選項，而是現代 Linux 擴充到數百 CPU 的必要前提。

### 使用者層級的 RCU 採用

[LTTng](https://lttng.org/) (Linux Trace Toolkit Next Generation) 是 [Userspace RCU](https://liburcu.org/) 最早的實際使用者，也是 Mathieu Desnoyers (URCU 主要作者) 同時推進的專案。LTTng 以函式庫 (`liblttng-ust`) 形式被受測程式載入，無法強制應用程式週期性呼叫 `rcu_quiescent_state()`，因此只能採用 memory-barrier 版本 (`urcu-mb`)；QSBR 雖效能最佳，卻需呼叫端配合，不適合通用函式庫情境。這同時解釋本文先前「Linux 核心以外的實作」評比中 `urcu-mb` 為何仍有獨立存在價值：通用性比效能更重要的情境，barrier 帶來的固定開銷是必要代價。

Bewermeyer 論文把 BIND DNS 伺服器列為 URCU 的應用，須區分「邏輯上契合」與「實際採用」：DNS 解析器確實大量查詢、罕見更新，但主流產品 (BIND9、Unbound、PowerDNS Recursor) 並未連結 liburcu，而是各自實作分片雜湊或 per-thread cache。把 RCU 視為「DNS cache 設計值得參考的同步典範」較貼近事實；視為「BIND 的實作」則屬訛傳。

## 使用陷阱與調優

### 讀取端 CS 內不可睡眠

Classic RCU (`!CONFIG_PREEMPT_RCU`) 的寬限期偵測直接以 context switch 為 QS — 讀取端 CS 內呼叫 `schedule()` 或會引發切換的路徑 (例如 `mutex_lock()`、`msleep()`、`wait_event()`) 等於宣告「我已離開 CS」，核心便允許 GP 結束、舊資料被 `kfree`，讀取端醒來繼續使用指標即 use-after-free。Preemptible RCU (`CONFIG_PREEMPT_RCU=y`) 對非自願搶占有保護 — task 被切走時掛入 `rcu_node->blkd_tasks`，等回到 CS 跑完才回報 QS — 但對顯式呼叫 `schedule()` 之類的「主動 sleep」沒有保護，仍會被視為離開 CS。`PREEMPT_RT` 是唯一例外：因 PI spinlock 已轉為 rt_mutex，由 RCU 的 priority boost 機制配合處理隱式阻塞，但讀取端仍嚴禁顯式 sleep。

/* 反面示範：兩種 RCU flavor 皆會 use-after-free */
rcu_read_lock();
node = rcu_dereference(g_list);
mutex_lock(&node->lock);   /* 主動讓出 CPU：寬限期判斷失效 */
...
rcu_read_unlock();

需要在讀取端睡眠時，改用 SRCU (`srcu_read_lock(&ss)` / `srcu_read_unlock(&ss, idx)`)；若是 BPF 等 trampoline 情境，採用 Tasks-Trace RCU (`rcu_read_lock_trace()`)。

### 不要在讀取端內外混用不相容的 lock

兩個 lock 的取得順序若不一致就會出現 ABBA deadlock：A 在 RCU 讀取端 CS 取 `lock_x` 並嘗試取 `lock_y`，B 持 `lock_y` 並呼叫 `synchronize_rcu()` 等待寬限期結束。lockdep 多半能抓到這類順序衝突，發生時一定要把寫入端的 `synchronize_rcu()` 移出 lock 區段，或改用非同步 `call_rcu()` 解耦。

### 釋放只能透過 `call_rcu` / `kfree_rcu` 或 `synchronize_rcu` 之後

寫入端拔除節點 (`list_del_rcu`) 並更新指標 (`rcu_assign_pointer`) 之後，必須等到寬限期結束才能釋放：

/* 兩種等價寫法 */
list_del_rcu(&p->list);
synchronize_rcu();
kfree(p);

/* 或非同步 */
list_del_rcu(&p->list);
kfree_rcu(p, rcu);  /* 內部即時把 p 排入 RCU 回呼，不阻塞 */

直接 `kfree` 等於 race condition，使用 `kfree_rcu` 還可走 SLAB bulk 通道一次釋放多筆，避免單筆 callback 排隊塞滿 `RCU_SOFTIRQ`。

### 模組卸載前的 `rcu_barrier`

模組若用過 `call_rcu(&obj->rcu, free_obj)`，卸載前務必呼叫 `rcu_barrier()`，等所有已註冊但尚未執行的 callback 完成；否則 callback 函式所在的 `.text` 已被解除映射，呼叫時就 oops。SRCU 對應 `srcu_barrier()`；Tasks RCU 對應 `rcu_barrier_tasks()`。

### 效能調優

| 旋鈕 | 用途 |
|---|---|
| `rcu_nocbs=<cpus>` | 指定 CPU 不在 `RCU_SOFTIRQ` 處理 callback，改由 `rcuog` / `rcuop` 核心執行緒處理；常用於 latency-critical workload (NFV、HPC) |
| `rcupdate.rcu_expedited=1` | 開機期所有寬限期走 expedited 路徑；以 IPI 換延遲，僅建議啟動階段啟用 |
| `rcupdate.rcu_normal=1` | 強制關閉 expedited 路徑，避免大量 IPI 干擾 |
| `rcupdate.rcu_cpu_stall_timeout` | 調整 RCU CPU stall warning 的容忍秒數，預設 21 秒 |
| `CONFIG_RCU_NOCB_CPU` | 編譯期啟用 nocb 相關核心執行緒，搭配 `rcu_nocbs=` 才能生效 |

判斷是否該採用 RCU 的判準與限制散見前文：〈為什麼選 RCU〉節列出三條結構前提 (動態指標、讀取端不可 sleep、讀寫不對稱)；〈何時值得採用 RCU〉節給出量化判準 $f \ll 1/n_{\text{CPU}}$ 與運行成本。任一條不成立時，請改用 `seqlock_t`、`rwlock_t` 或 `atomic_t` + `cmpxchg`。

## 實驗 (一)：以 liburcu 親手驗證 RCU 原理

前文以圖示與程式碼片段闡述 RCU，但讀取端最直接的學習路徑仍是「自己跑」。本節以 [Userspace RCU (liburcu)](https://liburcu.org/) 0.15.1 在使用者層級重現 RCU 的關鍵語意，無須 `sudo`、不必動到核心，便於快速迭代。所有量測同樣取自 ThunderX2 (224 logical CPU、Ubuntu 25.04、gcc 14.2)。完整可建置的原始碼與 Makefile 置於本倉庫的 [`rcu-experiments/`](rcu-experiments/) 目錄；下方僅節錄關鍵片段。

五個實驗依序揭示 RCU 的內部機制：

| 實驗 | 揭示的機制 | 對應章節 |
|---|---|---|
| U1：環境準備與 flavor 列舉 | liburcu 0.15 的 flavor 變遷 (`signal` 已移除、`memb` 取代為基於 `membarrier(2)` 的版本) | 〈Linux 核心以外的實作〉 |
| U2：訂閱—發布與 tear 偵測 | reader 永不看到撕裂的物件；writer 必須先寫成員再發布指標 | 〈寬限期〉、〈訂閱—發布機制〉、〈顧及 memory ordering 的影響〉 |
| U3：寬限期等待最後一位讀取端 | `synchronize_rcu()` 阻塞時間 ≈ 寬限期內最長的 read-side CS | 〈寬限期〉 |
| U4：讀取端可擴充性 vs lock | 224 reader 下 RCU 比 rwlock 快 4 個量級；qsbr / memb / mb 的成本梯度 | 〈對比其他 lock-free 同步機制〉 |
| U5：同步 vs 非同步 reclaimer | `call_rcu()` 把寫入端從寬限期關鍵路徑解耦，吞吐量提升一個量級 | 〈寬限期等待的進階介面〉 |

### 實驗 U1：環境準備與 flavor 列舉

Ubuntu 25.04 的安裝命令：

$ sudo apt-get install -y liburcu-dev
$ pkg-config --modversion liburcu liburcu-qsbr liburcu-mb liburcu-memb liburcu-bp
0.15.1
0.15.1
0.15.1
0.15.1
0.15.1

liburcu 0.15.1 提供下列 flavor，與 Bewermeyer 2017 論文描述的「QSBR / memory-barrier / signal」三者不同 — `signal` flavor 已於 [v0.15.0](https://github.com/urcu/userspace-rcu/blob/master/ChangeLog) (2024 年 12 月) 完全移除 (v0.13/v0.14 為 deprecation 過渡期)。

主流情境改用 `urcu-memb`：寫入端在 `synchronize_rcu()` 內呼叫 [`membarrier(2)`](https://man7.org/linux/man-pages/man2/membarrier.2.html)，讓核心向所有對應 process 的 CPU 廣播 IPI 等級的 memory barrier，使讀取端可省去硬體 barrier — 只保留 `cmm_barrier()` (編譯器屏障，零硬體成本)。本機核心 v6.14 支援 [`MEMBARRIER_CMD_PRIVATE_EXPEDITED`](https://docs.kernel.org/scheduler/membarrier.html) (Linux v4.14, 2017 年)，liburcu 自動偵測並使用；`membarrier(2)` 系統呼叫本身於 Linux v4.3 (2015 年) 引入。`urcu-mb` 是 fallback：當核心或 container 不允許 `membarrier(2)` 時退回讀取端 full barrier (`dmb ish` on aarch64)。

| Flavor (link 旗標) | 讀取端硬體成本 | 寫入端 GP 機制 | 對程式設計人員的限制 | 典型使用情境 |
|---|---|---|---|---|
| `urcu-qsbr` (`-lurcu-qsbr -lurcu-common`) | 零 (讀取端是空函式) | 等所有 thread 自報 quiescent state | 須週期性呼叫 `rcu_quiescent_state()` | DPDK、自家伺服器 |
| `urcu-memb` (`-lurcu -lurcu-common`，預設) | 接近零 (僅 compiler barrier，需核心支援 sys_membarrier) | `synchronize_rcu()` 內呼叫 `membarrier(2)` 廣播 | 無 (註冊執行緒即可) | 函式庫內部、LTTng |
| `urcu-mb` (`-lurcu-mb -lurcu-common`) | 高 (每次讀取端含 full barrier) | 純讀取端 barrier 配對寫入端 barrier | 無 | 不能用 `membarrier(2)` 的核心或受限 container |
| `urcu-bp` (`-lurcu-bp`) | 接近零 (與 memb 同) | 同 memb | 自動註冊執行緒 | `dlopen()` 載入的外掛 |

下文實驗 U2、U5 為呈現預設行為採用 `urcu-memb`；實驗 U3、U4 顯式列出 flavor 影響。

### 實驗 U2：訂閱—發布與 tear 偵測

驗證〈訂閱—發布機制〉節的關鍵命題：

> reader 在 `rcu_read_lock()` ... `rcu_read_unlock()` 之間取得指標的快照後，永遠不會看到「部分屬於舊版、部分屬於新版」的混合狀態；writer 必須先寫好成員、再以 `rcu_assign_pointer()` (或 `rcu_xchg_pointer()`) 發布。

`pubsub.c` 模型：每代 `g` 寫入 `payload[0..14] = g`，reader 取出指標後檢驗 15 個欄位是否同屬一代。任何欄位不一致即為 tear。

struct cfg { int generation; int payload[15]; };
static struct cfg *config;

static void *reader(void *_) {
    rcu_register_thread();
    long unique = 0, last = -1, corrupt = 0;
    while (!stop) {
        rcu_read_lock();
        struct cfg *c = rcu_dereference(config);
        int g = c->generation, bad = 0;
        for (int i = 0; i < 15; i++) bad |= (c->payload[i] != g);
        rcu_read_unlock();
        if (bad)        corrupt++;
        if (g != last)  { unique++; last = g; }
    }
    /* report counters */
}

static void *writer(void *_) {
    while (!stop) {
        struct cfg *new = malloc(sizeof *new);
        long g = ++writer_ops;
        new->generation = (int)g;
        for (int i = 0; i < 15; i++) new->payload[i] = (int)g;
        struct cfg *old = rcu_xchg_pointer(&config, new);
        synchronize_rcu();
        free(old);
        usleep(1000);          /* 1 ms 之間隔 */
    }
}

$ gcc -O2 -pthread -o pubsub pubsub.c $(pkg-config --cflags --libs liburcu)
$ ./pubsub 4 3
readers=4 dur=3s  read_ops=451732452 (150.58M/s)  unique_versions=11136
  writer_updates=2783  corrupt_reads=0

判讀：

- 4 個 reader 在 3 秒內完成 4.5 億次讀取，平均每秒 1.5 億；writer 每 1 ms 發布一版，3 秒共 2783 版，4 reader × 2783 ≈ 11132 ≈ 觀測到的 11136 unique versions
- `corrupt_reads = 0` 是這個實驗的關鍵：aarch64 對齊的 word load/store 本身是 atomic，個別欄位不會撕裂；但若把讀取端的 `rcu_dereference(config)` 換成裸指標 `config`，編譯器可能把 `c->payload[i]` 的讀取上提，越過 `c = config` 的指標載入，導致跨欄位讀到「指標已是新版、payload 仍是舊版」的混合狀態 — 也就是 view inconsistency 而非真正的 word tearing。`rcu_xchg_pointer` 內部以 `smp_store_release()` 發布、`rcu_dereference` 內部以 dependency-ordered load 訂閱，這對 release/acquire 配對是〈顧及 memory ordering 的影響〉節的具體應用
- reader 同時觀察到「許多版本之同一版」(stale read) 與 「跨版本的 unique」，呼應〈寬限期〉節：寬限期內舊版仍可被合法讀取，但每筆讀取自身完整

### 實驗 U3：寬限期等待最後一位讀取端

驗證 `synchronize_rcu()` 必須等到「寬限期前已進入 CS 的最後一位 reader」離開為止 — 寬限期長度由最慢的 pre-existing reader 決定。

static long sleep_us;
static atomic_int reader_in_cs;

static void *slow_reader(void *_) {
    rcu_register_thread();
    rcu_read_lock();
    atomic_store_explicit(&reader_in_cs, 1, memory_order_release);
    if (sleep_us > 0) {
        struct timespec ts = { sleep_us / 1000000,
                               (sleep_us % 1000000) * 1000L };
        nanosleep(&ts, NULL);
    }
    rcu_read_unlock();
    rcu_unregister_thread();
    return NULL;
}

int main(void) {
    rcu_init();
    long us[] = { 0, 100, 500, 1000, 5000, 10000, 50000 };
    for (size_t i = 0; i < sizeof us / sizeof *us; i++) {
        sleep_us = us[i];
        atomic_store(&reader_in_cs, 0);
        pthread_t t;
        pthread_create(&t, NULL, slow_reader, NULL);
        while (!atomic_load_explicit(&reader_in_cs, memory_order_acquire)) ;
        struct timespec a, b;
        clock_gettime(CLOCK_MONOTONIC, &a);
        synchronize_rcu();
        clock_gettime(CLOCK_MONOTONIC, &b);
        pthread_join(t, NULL);
        printf("reader_cs_us=%6ld  synchronize_rcu_us=%6ld\n",
               sleep_us, (ns(b) - ns(a)) / 1000);
    }
}

關鍵點：reader thread 先呼叫 `rcu_read_lock()` 再設定 `reader_in_cs = 1`；主 thread busy-wait 該旗標再啟動 `synchronize_rcu()`，確保「寬限期前已存在的 reader」這個前提成立 — 否則 race 之下可能寫入端先過了寬限期才見到讀取端。

reader_cs_us   synchronize_rcu_us
            0                   2
          100                 194
          500                 593
         1000                1103
         5000                5092
        10000               10090
        50000               50097

判讀：

- 寬限期延遲 ≈ reader CS 時間 + 約 100 µs 的 liburcu 內部開銷 (POSIX condition variable 喚醒 + 旗標檢查)；幾乎是 1:1 線性
- reader CS 為 0 µs (進入即離開) 時，`synchronize_rcu` 仍需 ~2 µs，這是 liburcu 偵測「已無 pre-existing reader」的最低成本
- 把 reader CS 拉到 50 ms，寫入端就被綁住 50 ms — 直接呼應〈使用陷阱與調優〉節「讀取端 CS 內不可睡眠」的警告：核心 RCU 的寬限期同樣由最慢 reader 決定，只是核心在 PREEMPT_RCU=n 下偵測 QS 的代價更低

### 實驗 U4：讀取端可擴充性 (RCU 三 flavor vs rwlock vs mutex)

把同一支 `scale.c` 編譯成 5 種 flavor，量測「N 個 reader + 1 個 writer (每 1 ms 更新) 共跑 3 秒」的總讀取吞吐量：

/* 共用 reader 內迴圈 — 以巨集切換 flavor (節錄) */
#if defined(FLAVOR_QSBR)
  #include <urcu/urcu-qsbr.h>
  #define R_LOCK()  urcu_qsbr_read_lock()
  /* QSBR 需週期性宣告 quiescent state */
#elif defined(FLAVOR_MEMB)
  #include <urcu/urcu-memb.h>
  #define R_LOCK()  urcu_memb_read_lock()
#elif defined(FLAVOR_RWLOCK)
  #define R_LOCK()  pthread_rwlock_rdlock(&rw)
/* ... */
#endif

while (!stop) {
    R_LOCK();
    g = rcu_dereference(config)->generation;
    R_UNLOCK();
    if ((ops & 0x3FF) == 0) R_QS();   /* 僅 QSBR */
    ops++;
}

建置：

$ gcc -O2 -pthread -DFLAVOR_QSBR  -o scale_qsbr   scale.c -lurcu-qsbr -lurcu-common
$ gcc -O2 -pthread -DFLAVOR_MEMB  -o scale_memb   scale.c -lurcu      -lurcu-common
$ gcc -O2 -pthread -DFLAVOR_MB    -o scale_mb     scale.c -lurcu-mb   -lurcu-common
$ gcc -O2 -pthread -DFLAVOR_RWLOCK -o scale_rwlock scale.c
$ gcc -O2 -pthread -DFLAVOR_MUTEX  -o scale_mutex  scale.c
$ for n in 1 4 16 64 128 224; do for f in qsbr memb mb rwlock mutex; do ./scale_$f $n 3; done; done

匯整 (單位皆為「百萬讀取 ops/秒」)：

| readers | rcu-qsbr (M/s) | rcu-memb (M/s) | rcu-mb (M/s) | rwlock (M/s) | mutex (M/s) |
|---:|---:|---:|---:|---:|---:|
| 1 | 826 | 249 | 50 | 31 | 27 |
| 4 | 3 303 | 995 | 199 | 8 | 6 |
| 16 | 13 198 | 3 979 | 796 | 1.7 | 6 |
| 64 | 46 132 | 13 954 | 3 163 | 0.9 | 6 |
| 128 | 46 313 | 13 205 | 6 113 | 1.9 | 6 |
| 224 | 43 616 | 8 146 | 6 119 | 3 | 6 |

判讀：

- RCU 三 flavor 隨 reader 數呈線性擴充，直到記憶體頻寬飽和：qsbr 從 1 reader 825 M/s × 64 ≈ 52 800 M/s 的理論值，實測 46 132 M/s (87%) 接近滿載；超過 128 reader 因 NUMA 跨 socket 共用 cache 而趨於平緩
- rwlock 與 mutex 出現負擴充：reader 越多，總吞吐量越低 — 全部 reader 爭搶同一條 cache line (鎖計數器)，造成寫入端 invalidate broadcast 飽和。224 reader 下 rwlock 僅剩 3 M/s 總吞吐，相當於每位 reader 13 K ops/秒，比 qsbr 的每位 reader 195 M/s 慢約 15 000 倍
- qsbr 與 memb 的差距固定 ~3.3 倍：qsbr 讀取端是空函式；memb 讀取端在 sys_membarrier 可用時只剩 `cmm_barrier()` (編譯器屏障)，但仍要載入 per-thread `rcu_reader.ctr` 並寫回更新後的 nesting 值，差距主要源於這對 TLS 讀寫與快取一致性流量。`mb` 又比 memb 慢約 5 倍，因為每次讀取端皆有完整 `dmb ish` 硬體屏障，無法藉助寫入端的 IPI 廣播
- `qsbr` 把成本前推給應用程式 (要求週期性呼叫 `rcu_quiescent_state()`)，這正是〈使用者層級的 RCU 採用〉節提到 LTTng 為何「無法採用 QSBR」 — 受測程式無法被強制插入 quiescent state 標記

這份實測直接量化〈對比其他 lock-free 同步機制〉表中「Contention among readers: None (RCU) / High (rwlock)」的具體差距。

### 實驗 U5：同步 vs 非同步 reclaimer

呼應〈寬限期等待的進階介面〉表中「`synchronize_rcu()` 阻塞 vs `call_rcu()` 非同步」的取捨。`async.c` 寫入端切換 `MODE_SYNC` 與 `MODE_ASYNC`：

static void cb_free(struct rcu_head *h) {
    free(caa_container_of(h, struct cfg, h));
    atomic_fetch_add(&callbacks_run, 1);
}

while (!stop) {
    struct cfg *new = malloc(sizeof *new);
    new->generation = ++writer_ops;
    struct cfg *old = rcu_xchg_pointer(&config, new);
#ifdef MODE_SYNC
    synchronize_rcu();
    free(old);
#else
    call_rcu(&old->h, cb_free);
#endif
}
/* main 結束前: rcu_barrier() 確保所有 callback 跑完 */

$ gcc -O2 -pthread -DMODE_SYNC  -o async_sync  async.c $(pkg-config --cflags --libs liburcu)
$ gcc -O2 -pthread -DMODE_ASYNC -o async_async async.c $(pkg-config --cflags --libs liburcu)
$ ./async_sync  4 3 ; ./async_async 4 3
$ ./async_sync 64 3 ; ./async_async 64 3

| 模式 | readers=4 寫入端 ops/秒 | readers=64 寫入端 ops/秒 |
|---|---:|---:|
| `synchronize_rcu()` (sync) | 56 K | 12 K |
| `call_rcu()` (async) | 1 548 K | 256 K |

判讀：

- 同樣 4 個 reader、同樣 1 ms 寫入端間隔，`call_rcu` 的吞吐量是 `synchronize_rcu` 的 27 倍；64 個 reader 仍領先 22 倍
- 寫入端在 sync 模式下，每筆 `synchronize_rcu` 必須阻塞等待寬限期 — 其延遲已在實驗 U3 量到 ≈ reader CS + 100 µs；64 reader 共享 socket 0 時 reader 之間 cache 競爭，寬限期延長至 ~80 µs，寫入端因此被綁住
- async 模式 `call_rcu` 僅把 callback 排入 per-thread 佇列、由背景執行緒收掉，寫入端立即返回；`rcu_barrier()` 在 main 結束前才真正等所有 callback 處理完，呼應〈使用陷阱與調優〉節對「模組卸載前的 `rcu_barrier`」的描述
- 觀察方向與後文〈實驗 (二)〉實驗 4 一致：核心 RCU 中 `call_rcu` 呼叫量遠高於 `synchronize_rcu`，根本原因之一正是寫入端等待寬限期的開銷 — 實測一旦改走非同步介面，吞吐量提升整整一個量級

### 對照表：使用者層級觀察 ↔ 核心行為

| 使用者層級觀察 (本節) | 核心對應行為 (〈實驗 (二)〉) |
|---|---|
| U2 reader 看到 stale read 但不 corrupt | GP 期間 reader 仍持有舊版指標、新 reader 已看到新指標，皆讀取完整物件 |
| U3 `synchronize_rcu` 阻塞 ≈ max reader CS | `synchronize_rcu_normal` 16–32 ms 反映 224 CPU 走過 QS 所需尾端時間 |
| U4 RCU 三 flavor 成本梯度 | 核心同樣把 GP/QS 成本移到更新端與排程路徑，避免在每筆讀取端都放硬體 barrier (`PREEMPT_RCU=y` 透過 per-task `rcu_read_lock_nesting`，`PREEMPT_RCU=n` 仰賴 context switch 視為 QS) |
| U5 `call_rcu` 寫入端不阻塞 | 實驗 4 中 `call_rcu` 呼叫量遠高於 `synchronize_rcu_normal`，方向一致 |

兩組實驗構成完整迴路：使用者層級量化 RCU 基礎語意與成本曲線，bpftrace 揭示核心如何把這些語意實作為 Tree RCU 的階層樹、QS 報告路徑、與 IPI 換延遲的 expedited 機制。

## 實驗 (二)：以 bpftrace 觀察 Linux 核心的 RCU

以下實驗一律在 Arm64/Linux 主機上執行，需 `sudo` 權限。本文測量取自一台 224 logical CPU 的 Marvell ThunderX2 雙路伺服器 (Ubuntu 25.04，Linux v6.14)；數值會因系統負載與核心配置而異，但觀察到的相對關係應一致。eBPF/bpftrace 用法可參見〈[Linux 核心的 eBPF](https://hackmd.io/@sysprog/linux-ebpf)〉。

每個實驗對應前文的特定論述：

| 實驗 | 對應章節 | 驗證的論點 |
|---|---|---|
| 1：列舉 RCU 探針 | 〈Tree RCU 實作主體〉、〈RCU 變體〉 | tracepoint 與 kprobe 涵蓋的 RCU 觀測點 |
| 2：rcu_utilization 熱區 | 〈Tree RCU 實作主體〉的 QS 來源 | tick / context switch / RCU core 的相對頻率 |
| 3：normal vs expedited 延遲 | 〈寬限期等待的進階介面〉 | IPI 換延遲的取捨，量級差兩到三個 |
| 4：call_rcu 呼叫者分佈 | 〈何時可銷毀舊資料？〉、〈使用陷阱〉 | 非同步介面為常態、`synchronize_rcu` 屬慢路徑 |
| 5：QS 報告的 per-CPU 分布 | 〈Tree RCU 實作主體〉的階層 lock | leaf node 的鎖只在群組內競爭 |
| 6：辨識 RCU 核心執行緒 | 〈RCU 變體〉、〈Tree RCU 實作主體〉 | GP 編排與 callback 執行是兩本帳 |

### 實驗 1：列舉可觀察的 RCU 探針

Linux v6.14 主流發行版核心通常未啟用 `CONFIG_RCU_TRACE_EVENTS`，僅保留兩個 RCU tracepoint，但大量 RCU 函式仍以 kprobe 形式可掛接。

$ sudo bpftrace -l 'tracepoint:rcu:*'
tracepoint:rcu:rcu_stall_warning
tracepoint:rcu:rcu_utilization

$ sudo bpftrace -l 2>/dev/null | grep -E 'kprobe:(call_rcu|kvfree_call_rcu|synchronize_rcu|invoke_rcu|note_gp|__rcu_read)' | head
kprobe:__rcu_read_lock
kprobe:__rcu_read_unlock
kprobe:call_rcu
kprobe:call_rcu_hurry
kprobe:invoke_rcu_core
kprobe:kvfree_call_rcu
kprobe:note_gp_changes
kprobe:synchronize_rcu
kprobe:synchronize_rcu_expedited
kprobe:synchronize_rcu_normal

`tracepoint:rcu:rcu_utilization` 接受字串參數，標示 RCU 進出三段關鍵熱區：兩段對應 QS 觀測點，第三段對應 callback 與 GP 的後端處理。

### 實驗 2：rcu_utilization 熱區分布

$ sudo timeout 5 bpftrace -e '
tracepoint:rcu:rcu_utilization { @[str(args->s)] = count(); }
'
@[End RCU core]: 747
@[Start RCU core]: 747
@[Start context switch]: 1554
@[End context switch]: 1554
@[End scheduler-tick]: 2773
@[Start scheduler-tick]: 2773

5 秒取樣的 224-CPU 閒置主機觀察到三組 Start/End 配對，分屬兩個層次：

QS 觀測點 (read-side 何時可被視為已離開 CS)：

- scheduler-tick (2773 次)：時鐘 tick 進入 `rcu_sched_clock_irq()` 時包夾；CPU 在 user space 或 idle 時的 tick 視為 QS
- context switch (1554 次)：`rcu_note_context_switch()` 包夾，每次任務切換代表該 CPU 走出目前 read-side CS

GP 後端處理熱區：

- RCU core (747 次)：`rcu_core()` 的整段執行，由 `RCU_SOFTIRQ` 或 (當 `rcutree.use_softirq=N` 時) per-CPU `rcuc/%u` kthread 觸發；負責 deferred QS 處理、GP 推進、callback 執行。它本身不是 QS 來源，而是消化 QS 與啟動 callback 的工作端

三段配對 Start 與 End 嚴格相等，代表每段熱區都正常結束；觀測值可隨工作負載漂移 (例如 sshd-session 大量 fork 時 context switch 會超過 tick)。

### 實驗 3：synchronize_rcu_normal vs synchronize_rcu_expedited 延遲

對應「expedited 路徑：對 non-idle CPU 送 async IPI 促其儘快進入 QS，延遲低但 CPU 開銷高」。在背景觸發 `unshare --net` 製造 GP 需求，同時量測兩條路徑的延遲：

$ sudo timeout 12 bpftrace -e '
kprobe:synchronize_rcu_normal { @e[tid] = nsecs; @cnt["normal"] = count(); }
kretprobe:synchronize_rcu_normal /@e[tid]/ {
  @us_normal = hist((nsecs - @e[tid]) / 1000); delete(@e[tid]);
}
kprobe:synchronize_rcu_expedited { @ee[tid] = nsecs; @cnt["expedited"] = count(); }
kretprobe:synchronize_rcu_expedited /@ee[tid]/ {
  @us_expedited = hist((nsecs - @ee[tid]) / 1000); delete(@ee[tid]);
}
END { clear(@e); clear(@ee); }
' &
$ sleep 1; for i in $(seq 1 20); do sudo unshare --net /bin/true; done; wait

實測結果：

@cnt[normal]: 13
@cnt[expedited]: 120

@us_expedited: 
[32, 64)              64 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[64, 128)             48 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@             |
[128, 256)             6 |@@@@                                                |
[256, 512)             2 |@                                                   |

@us_normal: 
[16K, 32K)             1 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|

`synchronize_rcu_expedited` 集中於 32–256 µs：`_synchronize_rcu_expedited()` 經 `sync_rcu_exp_select_cpus()` 挑選需要催促的 CPU，再以 `smp_call_function_single_async()` 傳送 IPI；IPI handler 依當下 CPU 狀態決定立即回報 QS、設置 deferred QS，或要求 resched，等下一次 `rcu_read_unlock()` 或 quiescent state 才正式回報。對於 224 logical CPU，最壞情況一次 expedited GP 需對近 200 個 CPU 各傳一次 IPI，這正是「以 IPI 換延遲」的 CPU 成本。

`synchronize_rcu_normal` 則落在 16–32 ms，這個量級可由前文「啟動期初始化與 force-quiescent-state」的時序推得：`rcu_gp_kthread` 啟動 GP 後睡 `jiffies_till_first_fqs` (本機 3 ms) 才醒來檢查；只要尚有 CPU 在跑 user space 或 kernel-side preempt-disabled loop，FQS 巡視就會反覆催促，直到自然 tick (HZ=1000 即 1 ms 一次) 與 context switch 累積出每個 CPU 至少一次 QS，整段 GP 才能 cleanup 退出。也就是說，3 ms 是 watchdog 的「最早催促時刻」、不是 GP 結束時刻；16–32 ms 反映 224 個 CPU 全部走過 QS 所需的尾端延遲。expedited 與 normal 因此相差兩到三個量級。

### 實驗 4：call_rcu / kvfree_call_rcu / synchronize_rcu 呼叫者對照

對應「非同步介面 `call_rcu` 與 `kfree_rcu` 是常態，`synchronize_rcu` 屬於模組卸載等慢路徑」。

$ sudo timeout 5 bpftrace -e '
kprobe:call_rcu              { @rate["call_rcu"] = count(); }
kprobe:kvfree_call_rcu       { @rate["kvfree_call_rcu"] = count(); }
kprobe:synchronize_rcu_normal    { @rate["sync_normal"] = count(); }
kprobe:synchronize_rcu_expedited { @rate["sync_expedited"] = count(); }
END { print(@rate); }
'
@rate[sync_normal]: 4
@rate[kvfree_call_rcu]: 15
@rate[call_rcu]: 812

- `call_rcu` 在閒置主機 5 秒內仍有 812 次呼叫，對應背景 ssh、systemd、kworker 的物件回收
- `kvfree_call_rcu` (`kfree_rcu` 的主要入口) 數量遠少於 `call_rcu`，但其 SLAB bulk 通道使得單次呼叫可帶走多個物件
- 同時段 `synchronize_rcu_normal` 僅 4 次。同步介面真實負擔與其在學習材料中的能見度成反比：解說時是主角，運轉中是少數派

進一步看 `call_rcu` 來源 (`comm` 為 task 名稱)：

$ sudo timeout 5 bpftrace -e 'kprobe:call_rcu { @[comm] = count(); }' | tail
@[swapper/140]: 3
@[systemd-journal]: 4
@[gmain]: 4
@[redir]: 8
@[systemd]: 15
@[sshd]: 51
@[sshd-session]: 710

`sshd-session` 占 87 % 的 `call_rcu`：每筆 ssh 連線結束、socket 回收、bash session 退場都會觸發。這呼應 RCU「read-mostly」的設計前提：寫入端集中於少數高頻元件 (網路與 IPC)，但每筆寫入都不阻塞讀取端。

### 實驗 5：QS 報告事件的 per-CPU 分布

對應「Tree RCU 將 CPU 分組，群組向上匯報」。在 224-CPU 主機上 6 秒取樣 context-switch QS 報告：

$ sudo timeout 6 bpftrace -e '
tracepoint:rcu:rcu_utilization /str(args->s) == "Start context switch"/ {
    @ctxsw[cpu] = count();
}
END { print(@ctxsw, 12); }
' | tail -15
@ctxsw[129]: 103
@ctxsw[17]: 112
@ctxsw[43]: 122
@ctxsw[172]: 134
@ctxsw[135]: 201
@ctxsw[134]: 216

最忙的 CPU (134、135) 報告 QS 達 200+ 次，而閒置 CPU 只有個位數。本機 `rcu_fanout_leaf=16` (預設值)，於是 224 個 CPU 分成 14 個末端節點，CPU 134、CPU 135 同屬編號 8 的末端節點 (覆蓋 CPU 128–143)，僅在該末端節點的 `rcu_node->lock` 上競爭；CPU 17、43、49、98、129、172 等熱門 CPU 則落在不同末端節點 (1、2、3、6、8、10)，彼此鎖獨立。Tree RCU 的階層結構恰好應付這種傾斜：避免 224 個 CPU 全部爭奪一個全域 lock，末端節點層的鎖競爭只發生在群組內部。

> CPU 134 與 CPU 135 並非同一實體 core 的 SMT 同輩處理器核 (本機 SMT 採跨條紋編號，CPU 134 的 SMT 同輩處理器核是 `134,162,190,218`)；二者同步偏忙是因為 NUMA-aware 排程把 sshd-session 與其衍生 worker 留在 socket 1 的相鄰 cores。完整 ThunderX2 拓樸見後續「大量 CPU 核數主機的 RCU 部署考量」一節。

### 實驗 6：辨識 RCU 核心執行緒

對應「寬限期的推進由 `rcu_gp_kthread` 核心執行緒驅動」。

$ ps -ef | grep -E 'rcu_|kworker.*rcu' | grep -v grep
root           4       2  ?        00:00:00 [kworker/R-rcu_gp]
root           6       2  ?        00:00:00 [kworker/R-kvfree_rcu_reclaim]
root          14       2  ?        00:00:00 [rcu_tasks_kthread]
root          15       2  ?        00:00:00 [rcu_tasks_rude_kthread]
root          16       2  ?        00:00:00 [rcu_tasks_trace_kthread]
root          18       2  ?        00:03:21 [rcu_preempt]
root          19       2  ?        00:00:00 [rcu_exp_par_gp_kthread_worker/1]
root          20       2  ?        00:00:00 [rcu_exp_gp_kthread_worker]

執行緒分為「GP 編排」與「callback 執行」兩類：

GP 編排執行緒：

- `rcu_preempt` (PID 18，累積 3 分 21 秒 CPU 時間)：`CONFIG_PREEMPT_RCU=y` 下的主 `rcu_gp_kthread` (`rcu_state.name` 即 `"rcu_preempt"`)，負責寬限期初始化 (`rcu_gp_init`)、QS 收集、超時時呼叫 `force_qs_rnp()` 催促，以及寬限期結束 (`rcu_gp_cleanup`)；本身不執行 callback。`CONFIG_PREEMPT_RCU=n` 時改名為 `rcu_sched`
- `rcu_exp_gp_kthread_worker` 與 `rcu_exp_par_gp_kthread_worker/N`：expedited GP 專用 worker，處理 `synchronize_rcu_expedited()` 的 IPI 派送與結果收集
- `rcu_tasks_kthread`、`rcu_tasks_rude_kthread`、`rcu_tasks_trace_kthread`：對應 RCU 變體表中 Tasks RCU 三變體的 GP 推進

Callback 執行端 (對應 `RCU core` 熱區)：

- `RCU_SOFTIRQ` (預設) 或 `rcuc/%u` kthread (`rcutree.use_softirq=N`)：在每個非 nocb CPU 上呼叫 `rcu_core()`，執行該 CPU 的 callback 與 deferred QS
- `rcuog/N` 與 `rcuop/N` (僅在 `rcu_nocbs=` 啟用後出現)：把 nocb CPU 的 callback 集中到 housekeeping CPU 上批次處理

兩個 workqueue rescuer：

- `kworker/R-rcu_gp`：`rcu_gp` workqueue 的 rescuer thread，僅在 workqueue worker 不足時才被喚起；累積時間通常為 0
- `kworker/R-kvfree_rcu_reclaim`：`kvfree_rcu_reclaim` workqueue 的 rescuer thread，搭配 `kvfree_rcu()` / `kfree_rcu()` 的批次回收 (SLAB bulk、vmalloc bulk、linked list 三條通道皆可能用到)

`rcu_preempt` 累積 3 分鐘 CPU 時間 (主機自 4 月 19 日起運行)，平均每天約 11 秒；這是 GP 編排的整體成本下限，與 callback 執行 (落在 `RCU_SOFTIRQ` 或 `rcuc`) 是兩本帳。對於 read-mostly 工作負載，光是把 read 端從 rwlock 換成 RCU，就已抵掉這幾秒以上的開銷。

### 檢討

實驗結果與文章敘述彼此對齊：

1. 三類 QS 報告事件的相對頻率 (tick > context switch > RCU core) 對應其觸發機制：tick 屬被動週期取樣，context switch 隨任務行為，RCU core 僅在有工作時才被喚起
2. expedited 與 normal GP 延遲相差約 100–1000 倍，與「以 IPI 換延遲」的設計取捨吻合
3. `call_rcu` 是非同步介面的事實命脈，其呼叫量遠高於同步 `synchronize_rcu`，呼應「寬限期的關鍵在於只等 pre-existing reader，而不是無限期阻塞所有後續讀取端」的多版本機制
4. 224-CPU 主機的 QS 報告呈現明顯傾斜，Tree RCU 的階層 lock 結構正是為這種非均勻負載而設計

這些觀察均不需要 RCU CONFIG_RCU_TRACE_EVENTS，僅憑 `tracepoint:rcu:rcu_utilization` 與少量 kprobe 即可獲得，適合在發行版預設核心上重現。

## 大量 CPU 核數主機的 RCU 部署考量

實驗主機是 Marvell ThunderX2 CN9975 雙路伺服器，以下先描述其拓樸，再對照 RCU 在這類規模上的實務影響。

### ThunderX2 CN9975 拓樸概觀

ThunderX2 系列原為 Broadcom Vulcan，2016 年由 Cavium 收購並重新發行，2018 年隨 Cavium 併入 Marvell 後續維護；本機所用 CN9975 規格如下：

由 `lscpu`、`numactl -H` 與 `/sys/devices/system/cpu/cpuN/topology/` 取得的本機規格：

| 項目 | 數值 |
|---|---|
| 架構 | Armv8.1-A，64-bit (`CPU implementer 0x43` = Cavium，model name `ThunderX2-99xx`) |
| 每 socket 實體 CPU 核數 | 28 |
| SMT | 4-way (每核 4 個 hardware thread) |
| Logical CPU per socket | 112 |
| Socket 數 | 2 |
| Logical CPU 總數 | 224 (28 × 4 × 2) |
| Cache | per-core 32 KiB L1I + 32 KiB L1D + 256 KiB L2；per-socket 32 MiB shared L3 (lscpu 顯示 56 個 L1/L2 instance、2 個 L3 instance) |
| 記憶體通道 | 每 socket 8 通道 DDR4-2666；node 各 64 GiB |
| Inter-socket 互連 | Cavium Coherent Processor Interconnect 2 (CCPI2)；NUMA distance 10/20 |
| NUMA node 數 | 2 (一 socket 一 node) |

兩個 socket 透過 CCPI2 互連的整體拓樸：

digraph thunderx2 {
    rankdir = "LR";
    node [shape=box, style="rounded,filled", fontname="Helvetica"];
    edge [arrowsize=0.5];

    subgraph cluster_s0 {
        label = "socket 0  (NUMA node 0, 64 GiB)";
        style = filled; fillcolor = "#e8f0ff";
        s0_l3 [label="32 MiB shared L3", fillcolor="khaki"];
        s0_c0 [label="core 0\nL1+L2\n4 SMT\n(CPU 0,28,56,84)", fillcolor="lightblue2"];
        s0_c1 [label="core 1\n(CPU 1,29,57,85)", fillcolor="lightblue2"];
        s0_dots [label="...", shape=plaintext, fillcolor=transparent];
        s0_c27 [label="core 27\n(CPU 27,55,83,111)", fillcolor="lightblue2"];
        s0_dram [label="8× DDR4-2666\n8 channels", fillcolor="lightyellow"];
        s0_c0 -> s0_l3 [dir=both];
        s0_c1 -> s0_l3 [dir=both];
        s0_c27 -> s0_l3 [dir=both];
        s0_l3 -> s0_dram [dir=both];
    }

    subgraph cluster_s1 {
        label = "socket 1  (NUMA node 1, 64 GiB)";
        style = filled; fillcolor = "#fff0e8";
        s1_l3 [label="32 MiB shared L3", fillcolor="khaki"];
        s1_c0 [label="core 0\nL1+L2\n4 SMT\n(CPU 112,140,168,196)", fillcolor="lightblue2"];
        s1_c1 [label="core 1\n(CPU 113,141,169,197)", fillcolor="lightblue2"];
        s1_dots [label="...", shape=plaintext, fillcolor=transparent];
        s1_c27 [label="core 27\n(CPU 139,167,195,223)", fillcolor="lightblue2"];
        s1_dram [label="8× DDR4-2666\n8 channels", fillcolor="lightyellow"];
        s1_c0 -> s1_l3 [dir=both];
        s1_c1 -> s1_l3 [dir=both];
        s1_c27 -> s1_l3 [dir=both];
        s1_l3 -> s1_dram [dir=both];
    }

    s0_l3 -> s1_l3 [dir=both, label="CCPI2\nNUMA dist 20", color="firebrick", penwidth=2];
}

Linux 對 logical CPU 採 striped (跨 SMT 條紋) 編號：

node 0 (socket 0)：CPU 0-111
  CPU  0- 27 = thread 0 of cores 0-27
  CPU 28- 55 = thread 1 of cores 0-27
  CPU 56- 83 = thread 2 of cores 0-27
  CPU 84-111 = thread 3 of cores 0-27
node 1 (socket 1)：CPU 112-223  (同樣 4 條紋)

驗證：`/sys/devices/system/cpu/cpu0/topology/thread_siblings_list` 為 `0,28,56,84`，CPU 134 的 SMT 同輩處理器核是 `134,162,190,218` (而非常見直覺的 `132-135`)。也就是說，實驗 5 中 CPU 134 與 CPU 135 並非同一實體 core 的 SMT 執行緒，而是 socket 1 上相鄰的兩個實體 core (core 22 與 core 23) 的 thread 0；之所以二者 QS 報告同步偏高，是因為 sshd-session 與其衍生的 worker 被 NUMA-aware 排程器留在同一 socket 的相鄰 cores，並未跨越 CCPI2。這對 RCU 的影響是兩條：第一，它們的 QS 競爭仍落在同一 leaf node (覆蓋 CPU 128–143)；第二，CCPI2 跨 socket 流量在這個 workload 不顯著。

### Tree RCU 階層仍只有二層

將前述〈Tree RCU 實作主體〉的階層樹規則套到本機：`CONFIG_RCU_FANOUT_LEAF=16` 與 `CONFIG_RCU_FANOUT=64` 預設下，224 個 logical CPU 切成 14 個末端節點，全部直接掛在 root 之下，整棵樹深度為 2 (root + leaves)。每個 `rcu_node->qsmask` 是 `unsigned long` 位元圖，16 個位元只用了 1/4，沒有壓力；無需調整 `CONFIG_RCU_FANOUT`，要動通常得到 1024 個以上才有意義。

digraph rcu_node_224 {
    rankdir = "TB";
    node [shape=box, style="rounded,filled", fillcolor="lightblue2", fontname="Helvetica"];
    edge [arrowsize=0.5];

    root [label="root rcu_node\nlevel 0\nqsmask = 14 bits", fillcolor="khaki"];

    L0  [label="leaf 0\nCPU 0-15"];
    L1  [label="leaf 1\nCPU 16-31"];
    L2  [label="leaf 2\nCPU 32-47"];
    L3  [label="leaf 3\nCPU 48-63"];
    L4  [label="leaf 4\nCPU 64-79"];
    L5  [label="leaf 5\nCPU 80-95"];
    L6  [label="leaf 6\nCPU 96-111"];
    L7  [label="leaf 7\nCPU 112-127"];
    L8  [label="leaf 8\nCPU 128-143", fillcolor="lightcoral"];
    L9  [label="leaf 9\nCPU 144-159"];
    L10 [label="leaf 10\nCPU 160-175"];
    L11 [label="leaf 11\nCPU 176-191"];
    L12 [label="leaf 12\nCPU 192-207"];
    L13 [label="leaf 13\nCPU 208-223"];

    root -> { L0 L1 L2 L3 L4 L5 L6 L7 L8 L9 L10 L11 L12 L13 };

    socket0 [label="socket 0 boundary\n(NUMA node 0, CPU 0-111)", shape=plaintext, fillcolor=transparent];
    socket1 [label="socket 1 boundary\n(NUMA node 1, CPU 112-223)", shape=plaintext, fillcolor=transparent];
    { rank=same; socket0; L0; L1; L2; L3; L4; L5; L6 }
    { rank=same; socket1; L7; L8; L9; L10; L11; L12; L13 }
}

實驗 5 中熱點 CPU 134、135 以紅色標示的 leaf 8 (CPU 128–143) 為共同 `rcu_node->lock` 的競爭對象；leaf 0–6 屬 socket 0 (NUMA node 0)、leaf 7–13 屬 socket 1 (NUMA node 1)，末端節點本身不跨 socket，因此 leaf 層的鎖永遠是 intra-socket 競爭。只有 root 層的 `qsmask` 更新會涉及兩個 socket 的位元同步。

### expedited GP 的 IPI 成本被 NUMA 放大

`synchronize_rcu_expedited()` 經 `sync_rcu_exp_select_cpus()` 對所有非 idle 的 CPU 各送一次 async IPI；本機 224 logical CPU、雙 socket，最壞情況一次 expedited GP 要送近 200 個 IPI，其中半數跨越 CCPI2 socket 邊界，延遲明顯高於 intra-socket。實驗 3 量到 32–256 µs 是低負載下的最佳值，工作負載夾在 active CPU 多時延遲尾部會拉長。

對 latency-critical 路徑：

- 避免設定 `rcupdate.rcu_expedited=1` (僅開機階段使用，加速啟動)
- 改採 `synchronize_rcu_normal()` 的 16–32 ms 或 polled GP (`get_state_synchronize_rcu()` + `poll_state_synchronize_rcu(cookie)`)，後者讓呼叫者把等待時間用於其他工作
- 真要降低 normal GP 等待的喚醒延遲，可設定 `rcutree.rcu_normal_wake_from_gp=1` 讓 GP kthread 直接喚醒等待者，省掉一輪排程延遲；定義見 [`kernel/rcu/tree.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/rcu/tree.c) 的 `rcu_normal_wake_from_gp` module_param

### NOCB 與 housekeeping CPU 是必要配置

預設組態下每個 CPU 都跑 `RCU_SOFTIRQ`，HPC、NFV、即時 workload 會被 callback 處理打斷。建議搭配以下開機參數：

rcu_nocbs=8-223
nohz_full=8-223
isolcpus=8-223

把 callback 集中到 housekeeping CPU `0–7` 上的 `rcuog`/`rcuop` kthread，工作 CPU 僅執行使用者 task。此外：

- `rcu_nocb_gp_stride=N` 控制多少 nocb CPU 共用一個 `rcuog`；NUMA 大機器宜手動設為單一 socket 內的數字 (例如 16)，避免 `rcuog` 跨 socket 處理 callback
- 本機若改用此組態，會額外出現 `rcuog/N`、`rcuop/N` per-socket kthread

digraph nocb_layout {
    rankdir = "LR";
    node [shape=box, style="rounded,filled", fontname="Helvetica"];
    edge [arrowsize=0.5];

    subgraph cluster_hk {
        label = "housekeeping CPU 0-7  (兩 socket 各取 4)";
        style = filled; fillcolor = "#fff7d6";
        hk0 [label="CPU 0-3\n(socket 0)", fillcolor="khaki"];
        hk1 [label="CPU 4-7\n(socket 0)", fillcolor="khaki"];
        rcuog0 [label="rcuog/0\nrcuop/0", fillcolor="orange"];
        rcuog1 [label="rcuog/1\nrcuop/1", fillcolor="orange"];
        hk0 -> rcuog0 [style=invis];
        hk1 -> rcuog1 [style=invis];
    }

    subgraph cluster_iso {
        label = "isolated / nocb CPU 8-223  (latency-critical workload)";
        style = filled; fillcolor = "#e8f0ff";
        iso_s0 [label="CPU 8-111\n(socket 0)\nuser task only", fillcolor="lightblue2"];
        iso_s1 [label="CPU 112-223\n(socket 1)\nuser task only", fillcolor="lightblue2"];
    }

    iso_s0 -> rcuog0 [label="call_rcu()\noffloaded", color="firebrick"];
    iso_s1 -> rcuog1 [label="call_rcu()\noffloaded", color="firebrick"];
}

紅線示意 isolated CPU 將 callback 委由 housekeeping CPU 上的 `rcuog/N` 排程；以 `rcu_nocb_gp_stride` 切分時，宜讓每個 stride 不跨 socket，避免 callback 處理拉動 CCPI2 流量。

### CPU stall warning 與 FQS 間隔隨 CPU 數放大

由「啟動期初始化與 force-quiescent-state」一節的公式：

RCU_JIFFIES_TILL_FORCE_QS = 1 + (HZ > 250) + (HZ > 500)
jiffies_till_first_fqs ≈ RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / 256

`HZ=1000` / 224 CPU 的本機算出 `jiffies_till_first_fqs = 3 jiffies (約 3 ms)` (224/256 整數除法為 0)，與一般小機器同等；FQS 不是 stall 的觸發條件而是其防範手段。預設 `rcupdate.rcu_cpu_stall_timeout=21s` 通常夠用；以下情境須加長至 60 s 以上：

- 上面跑 KVM nested guest (guest VM exit 拉長 host 的 read-side CS)
- `PREEMPT_RT` 啟用且 priority inversion 風險高
- HPC 或 storage workload 在 isolated CPU 上跑非 preemptible 區段超過 21 秒

一旦 `dmesg` 出現 `rcu: INFO: rcu_preempt detected stalls`，先比對 `/proc/softirqs` 的 RCU 欄位是不是某個 CPU 完全沒處理過 RCU softirq；若是，多半是該 CPU 被 user space 長時間獨占 (例如 spin loop) 或誤把 `nohz_full` CPU 沒同步加進 `rcu_nocbs`。

### 相對不需要操心的部分

- Lazy RCU (`rcutree.enable_rcu_lazy=1`)：定位在筆電/手持裝置的 idle 省電 (見「RCU 變體」一節介紹)，伺服器型 workload 沒有同等的 idle window，效益有限且會放大 stall 觀察區段；發行版多半維持預設停用，本機亦無需主動開啟
- `CONFIG_RCU_FANOUT`：224 個 logical CPU 在預設 64 fanout 下仍是 2 層樹；要調動 fanout 通常得到 1024 個以上才有意義
- `rcu_read_lock()` 在 `CONFIG_PREEMPT_RCU=y` 下只是 per-task `rcu_read_lock_nesting++`，與 CPU 數無關；單純讀取端 overhead 不會因 224 個 CPU 變慢

### 健康度驗證命令

實驗 5 的 per-CPU QS 分布是基準觀察。若懷疑 RCU 不健康，再加上下列檢查：

# FQS 是否頻繁啟動 — 過高代表 QS 報告不及時
$ sudo bpftrace -e 'kprobe:force_qs_rnp { @[cpu] = count(); }' &
$ sleep 10; sudo kill %1

# rcu_preempt kthread 的 wakeup 來源 (CONFIG_PREEMPT_RCU=y)
$ sudo bpftrace -e 'kprobe:try_to_wake_up /str(((struct task_struct *)arg0)->comm) == "rcu_preempt"/ { @[kstack] = count(); }'

# 觀察是否有任一 CPU 長時間沒進 rcu_note_context_switch
$ sudo bpftrace -e 'tracepoint:rcu:rcu_utilization /str(args->s) == "Start context switch"/ { @last[cpu] = nsecs; } interval:s:5 { ... }'

`force_qs_rnp` 觸發頻率高代表自然 QS (tick + context switch) 不足以讓寬限期推進，FQS watchdog 在強制催促 CPU。在 224 個 CPU 的機器上，這通常意味某個 isolated CPU 被誤設成 `nohz_full` 但沒對應 `rcu_nocbs`，造成 RCU 等不到 QS。

## 延伸閱讀

入門教材
- [Notes on Read-Copy Update (Eddie Kohler，Harvard CS 261)](https://read.seas.harvard.edu/~kohler/class/cs261-f11/rcu.html)
- [Linux 核心設計: CPU 排程器](https://hackmd.io/@sysprog/linux-scheduler) — CFS/EEVDF 排程類別、run queue 結構、`pick_next_task()` 的決策時機；本文〈排程器事件與 QS 來源〉節以此為前置知識
- [Linux 核心設計: 行程管理](https://hackmd.io/@sysprog/linux-process) — `task_struct`、thread group、fork/exit 路徑；本文 Preemptible RCU 的 `current->rcu_read_lock_nesting` 與 `rcu_node->blkd_tasks`、Tasks RCU 的「等所有 task 自願切換一次」均對應此教材的核心概念
- [Linux 核心設計: 搶佔機制](https://hackmd.io/@sysprog/linux-preempt) — `preempt_count` 結構、PREEMPT_NONE/VOLUNTARY/FULL/RT 四種模式、PREEMPT_DYNAMIC (v5.12+) 與 PREEMPT_LAZY (v6.13+) 的演進，本文〈排程器事件與 QS 來源〉小節對照此教材建立 RCU 與 scheduler 的銜接
- [並行程式設計: atomic 操作](https://hackmd.io/@sysprog/concurrency-atomics) — C11/C++ atomic、release/acquire 配對、dependency-ordered load 與 Linux 核心 `READ_ONCE` / `smp_load_acquire` / `smp_store_release` 的對照；本文〈訂閱—發布機制〉、〈顧及 memory ordering 的影響〉與〈為什麼選 RCU〉所引用的底層機制皆於此教材展開
- [What is RCU, Fundamentally? (Paul McKenney)](https://lwn.net/Articles/262464/) — RCU 設計理念三段式 (Publish-Subscribe / Wait / Multi-Version)
- [Unraveling RCU-Usage Mysteries (Paul McKenney)](http://www.rdrop.com/~paulmck/RCU/RCUusageFundamental.2021.12.07a.LF.pdf) (2021 年) — 5 種使用樣式：existence guarantees、type-safe memory、publication、wait for things to finish、phased state change
- [Is Parallel Programming Hard, And, If So, What Can You Do About It? (perfbook)](https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html) §9.5
- [linux-insides: RCU initialization](https://0xax.gitbook.io/linux-insides/summary/initialization/linux-initialization-9) — `rcu_init()`、`rcu_init_geometry()`、`open_softirq(RCU_SOFTIRQ, ...)` 的逐行導讀 (基於早期版本，仍區分 `rcu_bh_state` 與 `rcu_sched_state`)
- [linux-insides: Synchronization primitives](https://0xax.gitbook.io/linux-insides/summary/syncprim) — spinlock、queued spinlock、semaphore、mutex、rwsem、seqlock 各 `_rcu` 變體的對照背景

設計演進
- [Hierarchical RCU](https://lwn.net/Articles/305782/) (2008 年) — Tree RCU 設計動機與 4096-CPU 目標
- [Real-Time Preemption and RCU](https://lwn.net/Articles/128228/) (2005 年) — Preemptible RCU 萌芽
- [The 2024 edition of the RCU API](https://lwn.net/Articles/777036/) — `kfree_rcu_mightsleep`、polled GP、NMI-safe SRCU

形式化驗證
- [Verification of Tree-Based Hierarchical Read-Copy Update in the Linux Kernel (Liang/McKenney/Kroening/Melham，DATE 2018)](http://www.kroening.com/papers/date2018-rcu.pdf)
- [srcu-cbmc 主線 selftest](https://github.com/torvalds/linux/tree/master/tools/testing/selftests/rcutorture/formal/srcu-cbmc)

非 Linux 核心的 RCU 實作
- [Userspace RCU (liburcu)](https://liburcu.org/)
- DPDK RCU/QSBR：[rte_rcu_qsbr.h](https://github.com/DPDK/dpdk/blob/main/lib/rcu/rte_rcu_qsbr.h)、[rte_rcu_qsbr.c](https://github.com/DPDK/dpdk/blob/main/lib/rcu/rte_rcu_qsbr.c)、[文件](https://doc.dpdk.org/guides/prog_guide/rcu_lib.html)
- [Arm progress64](https://github.com/ARM-software/progress64) (qsbr)
- [Folly rcu_reader](https://github.com/facebook/folly/blob/master/folly/synchronization/Rcu.h)

使用案例
- [Using RCU for linked lists — a case study (Neil Brown)](https://lwn.net/Articles/610972/) (2014 年)
- [Pathname lookup in Linux](https://lwn.net/Articles/649115/)、[RCU-walk](https://lwn.net/Articles/649729/)、[A walk among the symlinks](https://lwn.net/Articles/650786/)
- [rcu_example 核心模組示範](https://github.com/jinb-park/rcu_example)
- [Yet another introduction to Linux RCU](https://www.slideshare.net/vh21/yet-another-introduction-of-linux-rcu)