Linux 核心專題: Usperspace RCU 研究

執行人: yuyuan0625
專題解說錄影

Reviewed by `Petakuo`

"具有零成本的 rcu_read_lock() 和 rcu_read_unlock()" 能否解釋這句話中零成本指的是甚麼?不占記憶體空間還是花費時間極少?又是怎麼做到的呢?

感謝你的疑問，零成本的用詞不夠精確，我已將敘述修改為低成本。
在 QSBR 中，rcu_read_lock() 和 rcu_read_unlock() 的實現是通過每個 thread 的本地變數來達成的。具體的方式如下：

Thread-Local Storage (TLS)：每個 thread 都有自己的本地變數來追蹤它是否處於 RCU 讀臨界區域內。這些變數存儲在 Thread-Local Storage (TLS) 中。

簡單標記：rcu_read_lock() 和 rcu_read_unlock() 操作僅僅是設置或清除這些本地變數。例如：
rcu_read_lock() 只是設置一個本地變數，表示該 thread 進入了讀臨界區域。
rcu_read_unlock() 則清除這個本地變數，表示該 thread 離開了讀臨界區域。

Reviewed by `eleanorLYJ`

想請問五種 URCU 是如何做 memory reclamination?
我在 Performance of memory reclamation for lockless synchronization 看到 4 種 memory reclamation 策略 (quiescent-state-based reclamation (QSBR), epoch-based recla-mation (EBR), hazard-pointer-based reclamation (HPBR), and lock-free reference counting (LFRC))，想請問 5 種 urcu 中是否使用了這些策略，還是用其他策略?

此 5 種 flavor 都是使用 QSBR 策略來進行 memory reclamation。不同 flavor 的差異主要在於它們實現 quiescent states 和同步的方法。

Reviewed by `stevend543`

筆記內容有提到 QSBR 需要再最後一個 onQuiescentState thread 做判別，請問這是如何做到的，需要額外的資料結構維護才有辦法讓所有 thread 對彼此的狀態都是 visiable?

每個 reader 一開始都要透過 urcu_qsbr_register_thread 將 reader 串連在一個全域雙向鏈結串列 registry ，藉由 registry 看每個 reader 的狀態判斷 GP 能否結束
程式碼如下:

void urcu_qsbr_register_thread(void)
{
    URCU_TLS(urcu_qsbr_reader).tid = pthread_self();
    urcu_posix_assert(URCU_TLS(urcu_qsbr_reader).ctr == 0);

    mutex_lock(&rcu_registry_lock);
    urcu_posix_assert(!URCU_TLS(urcu_qsbr_reader).registered);
    URCU_TLS(urcu_qsbr_reader).registered = 1;
    cds_list_add(&URCU_TLS(urcu_qsbr_reader).node, &registry);
    mutex_unlock(&rcu_registry_lock);
    _urcu_qsbr_thread_online();
}

cds_list_add(&URCU_TLS(urcu_qsbr_reader).node, &registry) 是將當前 thread 的 reader 加入到全域的 registry 雙向鏈結串列中。
如此一來全域雙向鏈結串列 registry 就包含了所有已註冊的 readers。藉由檢查這個 registry，系統可以判斷每個 reader 的狀態，從而決定是否能夠結束 grace period (GP)。

任務簡介

重現 2023 年專題: RCU 研究實驗並針對近期實作予以討論。

TODO: Userspace RCU 原理和實作考量

可重用 2023 年專題: RCU 研究素材，但要清楚解釋其設計和實作考量，中間你可能會遇到若干問題，記錄下來並討論。

RCU 概念

RCU (Read-Copy Update) 是一種資料同步機制，在 Linux 核心扮演重要作用。在 What is RCU, Fundamentally? 一文敘述:

RCU achieves scalability improvements by allowing reads to occur concurrently with updates.

RCU 適用於頻繁的讀取 (即多個 readers)、但資料寫入 (即少量的 updaters/writers) 卻不頻繁的情境。例如檔案系統經常需要搜尋特定目錄，但對目錄的修改卻相對少，這就是 RCU 理想應用場景。RCU 最大化讀取操作，犧牲寫入的效能。
下圖即為 RCU 在不同更新需求場景和不同資料一致性下的適用性，圖中藍色區域即為讀多寫少且可以接受資料不一致性的場景，即為 RCU 最適合的場景。反之，紅色區域為寫入頻繁且不允許資料不一致的情形，就不適合使用 RCU。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

出處: User-space RCU

RCU 模型

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

RCU 模型包含 3 個重要概念:

Removal: 在寫入端的臨界區中，進行資料讀取 (Read)、複製 (Copy) 和更改 (Update) 操作
Grace Period (寬限期): 一個等待時期，主要目的是確保在更新操作生效之前，所有可能使用舊數據的讀操作都已經完成。具體步驟如下:
a. 標記開始
b. 等待寬限期: 更新操作後需要等待一個寬限期，這個期間保證所有在開始點之前的讀操作都已經完成
c. 安全刪除: 在寬限期結束後，舊數據可以安全地刪除或重新利用
Reclamation: 回收舊資料
- QSBR (Quiescent State-Based Reclamation)
- EBR (Epoch-Based Reclamation)

RCU 常見 APIs

讀取端 (Reader)

rcu_read_lock(): 用於標記 RCU 讀取端 critical section (以下簡稱 CS) 的開頭，可以確保目前的 reader 對於 RCU 保護的資料會有一致的讀取結果，不會受到 writer 更新的影響。
rcu_read_unlock(): 用於標記 RCU 讀取端 CS 的結束，此指令必須和 rcu_read_lock() 成對
rcu_dereference(): 用於安全 dereference 受 RCU 保護的指標。利用此 API 讀取指標時，編譯器不會對讀取操作進行重新排序，確保在 RCU 讀取端 CS 內可以正確的 dereference 指標

程式碼範例:

rcu_read_lock();
struct my_struct *p = rcu_dereference(my_rcu_pointer);
// Access the RCU-protected data structure here
rcu_read_unlock();

寫入端 (Updater)

synchronize_rcu(): 等待所有已存在的 RCU 讀取端臨界區完成。這個操作用來確保在修改或釋放 RCU 保護的資料之前，所有的讀操作都已經完成

程式碼範例:

// Update or remove an RCU-protected data structure
my_rcu_pointer = NULL;
synchronize_rcu(); // Wait for all readers to finish
// Now it is safe to free the old data structure

call_rcu(): synchronize_rcu() 對應的非同步函式，會在所有已存在的 RCU 讀取操作完成後呼叫指定的函式

程式碼範例:

struct my_struct {
    int data;                   
    struct rcu_head rcu;        // RCU head, for callback
};
void my_rcu_callback(struct rcu_head *head) {
    struct my_struct *p = container_of(head, struct my_struct, rcu);
    kfree(p); // Free the memory
}

// Update or remove an RCU-protected data structure
struct my_struct *old_ptr = my_rcu_pointer;
my_rcu_pointer = new_ptr;
call_rcu(&old_ptr->rcu, my_rcu_callback); // Schedule the callback

rcu_assign_pointer(): 用於更新受 RCU 保護的指標 (必須防止編譯器和 CPU 將此指定操作重新排序到任何初始化指向結構的指定操作之前)

程式碼範例:

struct my_struct *new_ptr = kmalloc(sizeof(struct my_struct), GFP_KERNEL);
// Initialize the new structure
rcu_assign_pointer(my_rcu_pointer, new_ptr); // Safely assign the new pointer

整理表格

Category	Primitive	Purpose
Readers	`rcu_read_lock()`	Start an RCU read-side critical section.
	`rcu_read_unlock()`	End an RCU read-side critical section.
	`rcu_dereference()`	Safely load an RCU-protected pointer.
Updaters	`synchronize_rcu()`	Wait for all pre-existing RCU read-side critical sections to complete.
	`call_rcu()`	Invoke the specified function after all pre-existing RCU read-side critical sections complete.
	`rcu_assign_pointer()`	Safely update an RCU-protected pointer.

此表格擷取自 Is Parallel Programming Hard, And, If So, What Can You Do About It?

RCU Fundamentals

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Updater 更新內容後，呼叫指定介面進行發布，reader 呼叫特定介面來讀取已發佈的內容。
由於現代編譯器會對程式碼進行一系列最佳化處理，而 CPU 在執行指令時也會進行重排序。儘管它們的手段不同，目標都是為了改進程式碼的執行效率。然而這些最佳化有時可能會導致非預期的結果。在 RCU 中，由於沒有 lock，因此我們需要自行處理 memory ordering 議題。

考慮以下程式碼:





















/* Definiton of global structure */
struct foo {
    int a;
    int b;
    int c;
};
struct foo *gp = NULL;

/* . . . */
/* =========Updater======== */ 
p = kmalloc(sizeof(*p), GFP_KERNEL);
p->a = 1;
p->b = 2;
p->c = 3;
gp = p;
 
/* =========Reader======== */
p = gp;
if (p != NULL) {
    do_something_with(p->a, p->b, p->c);
}

我們預期程式碼的第 12 到 14 行會在第 15 行之前進行，但因為編譯器最佳化後無法保證程式碼的執行順序，因此有可能在a, b, c 變數的數值指派完成之前就已經指派 gp ，後續讀取端執行 do_something_with(p->a, p->b, p->c) 時造成非預期的結果。

你如何得知上方陳述是成立的？用計算機結構的認知來解說。
注意：某些材料存在謬誤，即使是 Linux 核心內附的文件也可能出錯。
搭配並行程式設計: 執行順序，設計實驗來解說。
TODO

為了解決此問題， Linux 核心提供對 memory barrier 進行包裝的 rcu_assign_pointer() 和 rcu_dereference() 等巨集來確保執行順序。
於是上述程式碼的第 15 行應改為:

rcu_assign_pointer(gp, p);

而第 18 行應改為:

p = rcu_dereference(gp);

另外，Linux 核心也基於 rcu_assign_pointer() 和 rcu_dereference() 進行更高層次的包裝，如 list 和 hlist。
以下表格顯示了 RCU 的發布和訂閱的 API，以及“取消發布”或撤回的附加API

Category	Publish	Retract	Subscribe
Pointers	rcu_assign_pointer()	rcu_assign_pointer(…, NULL)	rcu_dereference()
Lists	list_add_rcu() list_add_tail_rcu() list_replace_rcu()	list_del_rcu()	list_for_each_entry_rcu()
Hlists	hlist_add_after_rcu() hlist_add_before_rcu() hlist_add_head_rcu() hlist_replace_rcu()	hlist_del_rcu()	hlist_for_each_entry_rcu()

2. 延遲回收機制

RCU 讀取端的 CS 以 rcu_read_lock() 開始，並且以對應的rcu_read_unlock() 結束。
RCU 使用寬限期的概念，共用資料的處理期間，寫入端執行緒發布共用資料的更新作為寬限期的起點，直到諸多讀取端執行緒得以達成取得更新資料的操作為止。 RCU 必須等待之前的讀取端都已經讀取完成(退出臨界區後)才能對已更變的資料進行回收處理。

3. 多版本機制

維護最近更新物件的多個版本，適用於讀取端執行緒可接受並行地新增和刪除新物件的多個版本

QSBR (Quiescent State-Based Reclamation) 演算法

QSBR 的關鍵概念就是決定執行緒的 quiescent state，該狀態和 CS 相對，執行緒一旦離開 CS 就會歸類在 quiescent state。每個 reader 在離開 CS 時記錄自身狀態，writer 會檢查這個狀態，當所有執行緒都都離開 CS 時，就可釋放舊節點所在的記憶體。

https://doc.dpdk.org/guides/prog_guide/rcu_lib.html

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

圖中有 4 個執行緒，執行緒 1 執行完更新操作後，增添釋放記憶體的 callback，此時執行緒 2, 3, 4 讀取的都是之前的內容。需要等他們執行完成後分別呼叫 onQuiescentState 來表明自身已是靜默狀態，等到最後一個執行緒呼叫 onQuiescentState 時，就可呼叫之前註冊的 callback。實作過程中要考量的點就是如何選擇適合的位置執行 onQuiescentState，以及如何得知哪個才是最後一個執行onQuiescentState 的執行緒。

URCU flavors

URCU 針對不同的應用場景提供五種不同的 RCU flavors:

QSBR (quiescent-state-based RCU)
Memory-barrier-based RCU
Bullet-proof RCU
Signal-based RCU
Signal-based RCU using an out-of-tree sys_membarrier() system call()

1. QSBR (urcu-qsbr)

相關程式碼可見 src/urcu-qsbr.c、include/urcu/static/urcu-qsbr.h

類似於“經典”的 RCU 實作：
- QSBR 與 Linux kernel 中的 RCU_TREE 和 RCU_TINY 實作類似
- 具有低成本的 rcu_read_lock() 和 rcu_read_unlock()
定期呼叫 rcu_quiescent_state()：
- qsbr flavor 在reader 結束 CS 之後並不會像其他 4 種 flavor 一樣會自動進入 quiescent state，因此 grace period 會比較長
- 每個執行緒必須定期呼叫 rcu_quiescent_state()，讓 reader 進入 quiescent state，類似於 kernel 中必須定期呼叫的 schedule()
執行緒註冊和取消註冊：
- 每個執行 RCU 讀取端臨界區的執行緒在創建後必須呼叫 rcu_register_thread()
- 執行緒在退出前必須呼叫 rcu_unregister_thread()
- 上述的要求對整體應用施加了嚴格的限制，使得 QSBR RCU 無法在大多函式庫中使用
性能優勢：
- QSBR 提供優秀的性能

除了「搬運」既有的素材，難道你不會好奇，QSBR 何以有更好的性能？又，既然有 QSBR，為何要探討 EBR 呢？

2. Memory-barrier-based RCU (qsbr-mb)

相關程式碼可見 src/urcu.c、include/urcu/static/urcu-mb.h

類似於早期的可搶佔 RCU 實現：
- 類似於最早被接受到 -rt patchset 中的可搶佔 RCU 實作
- rcu_read_lock() 和 rcu_read_unlock() 包含 memory barrier (但不包含重量級的 atomics 指令)
讀取端成本較高
- 由於包含 memory barrier，此實作相較於標準 RCU 有更高的讀取成本
不需要定期呼叫
- 不像 QSBR 需要定期呼叫 rcu_quiescent_state()，因此能用於函式庫中
實作上 mb、signal、MEMBARRIER 類似，後面兩者即是對讀取端的 memory barrier 進行改善

3. Bullet-proof RCU (qsbr-bp)

相關程式碼可見 src/urcu.c、include/urcu/static/urcu-bp.h

自動呼叫 rcu_register_thread() / rcu_unregister_thread()
- 讀取端在進入臨界區前會自動 register，讀取端執行緒結束前會自動 unregister
RCU primitives 的成本提高 (讀、寫都較慢)
- 由於需要自動呼叫 rcu_register_thread()，進一步增加了成本
當使用者無法掌控執行緒的開始和結束時， bp flavor 會是最適合的選擇

4. Signal-based RCU (qsbr-signal)

從 rcu_read_lock() 和 rcu_read_unlock() 中移除 memory barriers，因此擁有最接近 qsbr flavor 的讀取端效能
需要放棄一個 POSIX 訊號，該訊號將被 synchronize_rcu() 用於取代讀取端的 memory barriers
即使移除了 memory barriers，Signal-based RCU 仍允許 primitives 被函式庫使用
目前此實作因為訊號產生的副作用已在 2023 年被棄用

Phase 1 of deprecating liburcu-signal
Complete removal of urcu-signal flavor

簡單來說，Signal-based RCU 減少了primitives 的成本，但需要使用者放棄一個 POSIX 訊號，並且所有執行緒在使用 RCU 之前必須註冊。

5. Signal-based RCU using an out-of-tree `sys_membarrier()` system call (qsbr-memb)

相關程式碼可見 src/urcu.c、include/urcu/static/urcu-memb.h

以實驗性的 sys_membarrier() 系統呼叫取代 Signal-based RCU 使用的 POSIX 訊號，而 sys_membarrier() 因為可以只通知正在執行的執行緒，所以相較於 POSIX 訊號更輕量化
減少中斷範圍
- 與 signal flavor 對註冊為 RCU 讀取端的每個執行緒發送 POSIX 訊號不同，memb flavor 只中斷當前正在運行的執行緒
Blocking 的執行緒在過程中已經執行過 memory barriers，並且在喚醒時會再次執行，所以不需要中斷，使得整體性能更高

簡單來說，memb flavor 透過使用處理器間中斷而非 POSIX 信號減少對系統的負擔，同時只中斷當前運行的執行緒來進一步優化性能。

實作

rcu_init :
- rcu_sys_membarrier_init : 檢查作業系統核心是否支援 sys_membarrier ，沒有則退回 mb flavor
smp_mb_master : 若 kernel 支援 sys_membarrier， writer 透過它將 reader 的 compiler barrier 提升成 memory barrier
urcu_memb_smp_mb_slave : 若 kernel 支援 sys_membarrier，將 memory barrier 換成 compiler barrier

各種 RCU flavor 的應用場景

除了「搬運」，你能說出個別 RCU flavor 對應到哪些真實世界的應用場景嗎？

qsbr 版本: 若使用者非常在意效能且能清楚知道讀取端的每個執行緒如何進入 quiescent state 以避免寫入端被 block 太久或寬限期無法結束。
反之則適合使用另外三種 flavor，使用者就可以不用考慮何時讓 reader 進入 quiescent state
- mb 版本: 適合於無法讓出 POSIX 信號或不支援 membarrier 且需要最佳寫入端效能的情況
- signal 版本: 適合於可以讓出 POSIX 信號且最在意讀取端效能的情況
- memb 版本: 適合於支援 membarrier 並希望平衡讀取端和寫入端效能的情況

還是沒解釋「真實世界」中的應用，例如 Linux 核心和 LTT-ng 怎麼運用？

不要刪除這些標注的訊息，除非你獲得充分的檢閱。

小結

本表格擷取自 User-space RCU

TODO: 重現 2023 年實驗

比較不同 flavor 的讀寫效能，解讀其表現。注意：近期程式碼可能會有不同的表現，而且你可能會遇到某些程式碼無法運作，試圖修正，並貢獻回 Userspace RCU 專案。

Userspace RCU 安裝

Building

./bootstrap # skip if using tarball
./configure
make
make install
ldconfig

其中 ./bootstrap 需要使用 Autoconf 和 libtool
另外雖然官方教學沒有寫，但make install 和 ldconfig 都需要利用 sudo 提高權限才能成功執行。

sudo apt-get install autoconf 
sudo apt-get install libtool

Benchmark 實驗

使用 tests/benchmark 目錄下的測試檔來比較以上 4 種（signal flavor 已棄用，故不討論）flavor 的讀寫效能。

./test_urcu_qsbr 6 2 1    /*6 writers, 2 readers, 1 second*/

下表為 6 reader, 2 writer, 1 second 的結果

6 reader/ 2 writer	read	write
qsbr	1735352485	235117
signal	-	-
memb	138286044	754509
mb	136154230	721500
bp	673107223	122460

可以觀察到 bp flavor 的 read 次數比 memb 高，推測是因為 bp flavor 的 write 次數較少，因此產生的 cache-line exchanges 也較少，所以 reader 受到 cache 的效能影響降低。

至於 bp flavor write 次數較少的原因是因為在 urcu_bp_synchronize_rcu 要將 signal block ，來確保 signal safe，透過 perf 可以發現它佔整體的 90%，產生的 overhead 非常高。

解釋其設計考量，要能充分對應到你的實驗結果。

$ sudo perf record -g --call-graph dwarf ./test_urcu_bp 0 1 1
$ sudo perf report --stdio -g graph,0.5,caller

|--94.58%--urcu_bp_synchronize_rcu
               |          |          
               |          |--90.80%--__GI___pthread_sigmask (inlined)
               |          |          |          
               |          |          |--66.20%--entry_SYSCALL_64_after_hwframe
               |          |          |          |          
               |          |          |          |--45.75%--do_syscall_64
               |          |          |          |          |          
               |          |          |          |          |--32.16%--syscall_exit_to_user_mode
               |          |          |          |          |          |          
               |          |          |          |          |           --1.91%--exit_to_user_mode_prepare
               |          |          |          |          |

參考資料

~~Linux RCU 原理剖析 (一) 初窺門徑~~

以第一手的材料為主，特別是 Paul E. McKenney 博士撰寫的論文和技術報告。

好的，因為此網頁有出現在Linux 核心設計: RCU 同步機制的延伸閱讀中，所以學生才會也納入參考。會再多參考 Paul E. McKenney 博士的第一手材料!

User-Level Implementations of Read-Copy Update

Supplementary Material for User-Level Implementations of Read-Copy Update

Linux 核心專題: Usperspace RCU 研究

Reviewed by Petakuo

Reviewed by eleanorLYJ

Reviewed by stevend543

任務簡介

TODO: Userspace RCU 原理和實作考量

RCU 概念

RCU 模型

RCU 常見 APIs

讀取端 (Reader)

寫入端 (Updater)

RCU Fundamentals

1. 發布－訂閱機制 (Publish-Subscribe Mechanism)

2. 延遲回收機制

3. 多版本機制

QSBR (Quiescent State-Based Reclamation) 演算法

URCU flavors

1. QSBR (urcu-qsbr)

2. Memory-barrier-based RCU (qsbr-mb)

3. Bullet-proof RCU (qsbr-bp)

4. Signal-based RCU (qsbr-signal)

5. Signal-based RCU using an out-of-tree sys_membarrier() system call (qsbr-memb)

實作

各種 RCU flavor 的應用場景

TODO: 重現 2023 年實驗

Userspace RCU 安裝

Building

Benchmark 實驗

參考資料

針對其他學員期末專題發表提出的問題或建議

Reviewed by `Petakuo`

Reviewed by `eleanorLYJ`

Reviewed by `stevend543`

5. Signal-based RCU using an out-of-tree `sys_membarrier()` system call (qsbr-memb)