---
tags: LINUX KERNEL, LKI
---
# [Linux 核心設計](https://beta.hackfoldr.org/linux/): RCU 同步機制
Copyright (**慣C**) 2019 [宅色夫](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)
## 概念
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://en.wikipedia.org/wiki/Non-blocking_algorithm)滿足以下場景的同步需求:
* 頻繁的讀取，不頻繁的寫入
* 對資料沒有 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）。
```cpp
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) 這概念，描述共用資料的處理期間，寫入端執行緒發布共用資料的更新作為寬限期的起點，直到諸多讀取端執行緒得以達成取得更新資料的操作為止。
下方程式碼展示寬限期:
```cpp
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 改寫，在讀取端執行緒裡頭標注寬限期，成為以下:
```cpp
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 讀取過程的開始和結束，也就是幫助檢測寬限期是否結束。`foo_update` 增加`synchronize_rcu` 函式的呼叫，意味著寬限期的開始，而直到寬限期結束，該函式才會返回。示意如下:
寬限期是 RCU 實作中最複雜的部分，原因是在提高讀取資料的效能的同時，刪除資料的效能也不能太差。
## 訂閱—發布機制
圖解發布－訂閱 ([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) 為零，即可安全地釋放該記憶體空間。
## 顧及 [memory ordering](https://en.wikipedia.org/wiki/Memory_ordering) 的影響
現代編譯器通常會對程式碼進行一系列最佳化，CPU 也會在指令執行時進行調整 (reordering)，儘管手段不同，目的都是改進程式碼的執行效率，但這樣的最佳化有時會帶來非預期的結果。以往在讀取和寫入端都使用 lock 時，作業系統核心會處理 [memory ordering](https://en.wikipedia.org/wiki/Memory_ordering) 議題，但在 RCU 中，由於沒有 lock，因此我們需要自行處理。
考慮以下程式碼:
```cpp=
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 機制對 [memory barrier](https://en.wikipedia.org/wiki/Memory_barrier) 進行包裝，提供了專用 API 來解決該問題。於是上述的第 9 行不再是直接的指標數值指派，而該改為以下:
```cpp
rcu_assign_pointer(global_foo, new_fp);
```
關於 `rcu_assign_pointer`，可見 Linux 核心原始程式碼 [linux/include/linux/rcupdate.h](https://github.com/torvalds/linux/blob/master/include/linux/rcupdate.h):
```cpp
#define rcu_assign_pointer(p, v) \
do { \
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)); \
} while (0)
```
本身是個巨集定義，我們可見其實作只是在數值指派之前，加了 `WRITE_ONCE` 這樣的 [memory barrier](https://en.wikipedia.org/wiki/Memory_barrier) 來確保程式碼的執行順序。另外，上方程式碼列表出現的 `__rcu`，只是作為編譯過程的檢查條件用途，主要搭配 [Sparse](https://www.kernel.org/doc/html/latest/dev-tools/sparse.html)。
> 詳見 [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 loads（如：[control](https://yarchive.net/comp/linux/locking.html), [data](http://www.cs.umd.edu/~pugh/java/memoryModel/AlphaReordering.html)）。回顧稍早看到加入 RCU 的程式碼:
```cpp=
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 行還沒執行時，CPU 就預先判斷執行，於是當這樣的程式碼和 `foo_update` 同時執行的話，可能導致傳遞給 `do_something` 函式的一部分屬於舊的 `global_foo`，而其他則是新的數值。這樣導致執行結果的錯誤。為了避免這類問題，Linux 核心在 [linux/include/linux/rcupdate.h](https://github.com/torvalds/linux/blob/master/include/linux/rcupdate.h) 提供其他 RCU 巨集:
```cpp
#define rcu_dereference_check(p, c) \
__rcu_dereference_check((p), (c) || rcu_read_lock_held(), __rcu)
#define __rcu_dereference_check(p, c, space) \
({ \
/* Dependency order vs. p above. */ \
typeof(*p) *________p1 = (typeof(*p) *__force)READ_ONCE(p); \
RCU_LOCKDEP_WARN(!(c), "suspicious rcu_dereference_check() usage"); \
rcu_check_sparse(p, space); \
((typeof(*p) __force __kernel *)(________p1)); \
})
#define rcu_dereference(p) rcu_dereference_check(p, 0)
```
這段巨集定義包含除錯資訊，予以簡化後，展現如下 (其實也是舊版的程式碼):
```cpp
#define rcu_dereference(p) \
({ \
typeof(p) _________p1 = p; \
smp_read_barrier_depends(); \
(_________p1); \
})
```
之所以書寫看似冗長的 `________p1`，主要避免潛在的變數命名的衝突，在 [commit 24ba530](https://github.com/torvalds/linux/commit/24ba53017e188e031f9cb8b290286fad52d2af00) 則引入更好理解的變更。數值指派後，加入 [memory barrier](https://en.wikipedia.org/wiki/Memory_barrier) [`smp_read_barrier_depends()`](https://lkml.org/lkml/2012/2/1/521)
如此一來，我們可在稍早 `foo_read` 程式列表中，將
```cpp
foo *fp = global_foo;
```
更換為:
```cpp
foo *fp = rcu_dereference(global_foo);
```
即可防止上述問題。
## 資料讀取的完整性
考慮以下對 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)
延伸閱讀:
* [Using RCU for linked lists — a case study](https://lwn.net/Articles/610972/)
* [Linux RCU 原理剖析 (一) 初窺門徑](https://www.cnblogs.com/LoyenWang/p/12681494.html)
* [Linux RUC 原理頗析 (二) 進入佳境](https://www.cnblogs.com/LoyenWang/p/12770878.html)
* [Linux 核心同步機制之 (七) : RCU 基礎](http://www.wowotech.net/kernel_synchronization/rcu_fundamentals.html)
## 何時可銷毀舊資料？
考慮以下刪除特定 list 節點的程式碼:
```cpp=
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 節點的變更，對應的程式碼如下:
```cpp=
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)
> ==TODO==: 解釋 [rcu_list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu_list) 的流程和實作
在 [rcu_list](https://github.com/sysprog21/concurrent-programs/tree/master/rcu_list) 中，我們可影響到 RCU 實際表現的因素就是寬限期的設計，在 RCU 的情境中，需要搭配記憶體利回收機制，其中 QSBR (Quiescent State-Based Reclamation) 和 Epoch-Based Reclamation (EBR) 都是相當經典設計。
### 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) 期間，可能發生若干次 context switch:
寬限期 (grace period, GP) 指所有 CPU 都經歷靜默狀態所需要的等待的時間，亦即系統中所有的讀取端執行緒完成對 CS 的讀取。
```flow
st=>start: 起始
InitGP=>operation: 初始化 GP
NGPR=>condition: 需要新的 GP?
RIDLE=>operation: RCU Idle
CGP=>operation: 完成 GP
ACPTQ=>condition: 所有 CPU 經歷過 QS?
CPTQS=>operation: CPU 經歷過 QS
WFQS=>operation: 等待 QS
st->InitGP
InitGP(bottom)->ACPTQ
ACPTQ(no, bottom)->WFQS(left)->CPTQS(top)->ACPTQ
ACPTQ(yes)->CGP(bottom)->RIDLE(bottom)->NGPR
NGPR(yes, right)->InitGP
NGPR(no, left)->RIDLE
```
其原理是，讀取端 CS 保護並禁止其他 CPU 修改到指定區域，但允許多個 CPU 同時讀取:
3 個主要的參與者如下圖:
```graphviz
digraph rcu {
rankdir = "LR"
size="6,4"; ratio = auto;
node [color="lightblue2", style=filled, shape=box];
updater -> reader [ label = "publish" ]
reader -> updater [ label = "subscribe" ]
reader -> reclaimer [ label = "critical section" ]
updater -> reclaimer
}
```
* reader ： 安全地讀取 CS 資源，負責標識進出 CS
* updater : 複製一份資料，然後更新資料；用新資料覆蓋舊資料，然後進入寬限期
* reclaimer : 等待在寬限期之前的讀取端執行緒退出 CS；在寬限期結束後，負責回收舊資料；
3 個重要機制
* 發布－訂閱機制
- 主要用於更新資料，即使在資料被同時修改時，執行緒也能正確地讀取資料。RCU 藉由發布－訂閱機制，達到並行的新增操作；
* 延遲迴收機制
* 達到檢查舊資料上所有 RCU 讀取端執行緒完成，用於正確地刪除舊資料；
* 多版本機制
* 維護最近更新物件的多個版本，適用於讀取端執行緒可接受並行地新增和刪除新物件的多個版本
總結 RCU 關鍵概念:
* 讀取端執行緒 lock-free 讀取資料，標注進出 CS
* 寫入端 Read, Copy, Update —— 也就是 RCU 命名由來
* 舊資料延遲回收
## 對比其他 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)
## 在 Linux 核心中使用 RCU
Linux 核心中，會針對不同資料結構予以包裝 RCU，例如 [rculist](https://github.com/torvalds/linux/blob/master/include/linux/rculist.h):
```cpp
#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);
}
```
[Pathname lookup](https://github.com/torvalds/linux/blob/master/Documentation/filesystems/path-lookup.rst)
* [Pathname lookup in Linux](https://lwn.net/Articles/649115/)
* [RCU-walk: faster pathname lookup in Linux](https://lwn.net/Articles/649729/)
* [A walk among the symlinks](https://lwn.net/Articles/650786/)
其他 RCU 核心模組示範: [rcu-examples](https://github.com/jinb-park/rcu_example)
解說: [Yet another introduction to Linux RCU](https://www.slideshare.net/vh21/yet-another-introduction-of-linux-rcu)
## 待整理
* [Notes on Read-Copy Update](https://read.seas.harvard.edu/~kohler/class/cs261-f11/rcu.html)
* [深入理解 Linux 的 RCU 機制](https://cloud.tencent.com/developer/article/1006204)
* [Using RCU for linked lists — a case study](https://lwn.net/Articles/610972/)
* [Hierarchical RCU](https://lwn.net/Articles/305782/)
* [Real-Time Preemption and RCU](https://lwn.net/Articles/128228/)
* [sleepable RCU 的實現](http://www.wowotech.net/kernel_synchronization/linux2-6-23-RCU.html)
* [Verification of Tree-Based HierarchicalRead-Copy Update in the Linux Kernel](http://www.kroening.com/papers/date2018-rcu.pdf)
* [srcu-cbmc](https://github.com/torvalds/linux/tree/master/tools/testing/selftests/rcutorture/formal/srcu-cbmc): Linux 核心內部極少數引入 [形式化驗證](https://hackmd.io/s/H1xxp3pF0) 的程式碼
* [DPDK: RCU](https://www.yuque.com/zzqcn/opensource/nyvy7n)
* [Unraveling RCU-Usage Mysteries](http://www.rdrop.com/~paulmck/RCU/RCUusageFundamental.2021.12.07a.LF.pdf)
* [Linux 核心 Read-Copy Update 筆記整理](https://hackmd.io/@linD026/linux-kernel-RCU)
Sign in with Wallet
Connect another wallet