執行人: JUSTUSVMOS
jserv
如何驗證 RCU 實作行為符合預期且具備 lock-free/wait-free 特性?
- 先看 RCU 讀取端的程式路徑,確認沒有用 mutex 或 spinlock 把 read 包起來,這樣 reader 才不會因為其他執行緒被卡住。
- 可以直接開 kernel 裡的
CONFIG_PROVE_LOCKING
或__rcu
sparse 這些工具,讓它幫你找出同步問題或 API 用錯的地方,比較保險。
- 直接跑 rcutorture 或 liburcu 壓力測試,把 reader 跟 writer 數量開大,看看讀端會不會被卡住,只要 writer 再怎麼寫,讀的都能順利執行就沒問題,效能數據也可以順便看一下。
理工人員測試若只憑感覺、沒辦法拿出理論和量化分析,該如何保證品質呢?
使用本課程教材對於並行處理的分析方式,來探討上述問題。
解說錄影呢?
紀錄閱讀課程教材 (以第一手材料為主) 過程中遇到的疑惑,充分討論
在自己的電腦上準備 Userspace RCU (URCU) 函式庫並進行評估,注意不得使用虛擬機器
- 解釋給定程式碼的原理,指出其缺失並予以改進
- 開發得以搭配 Userspace RCU 和測驗題程式碼運作的效能評比程式,量化在高度並行場景的效能表現
- 改進測驗題程式碼,運用於高度並行的 Valkey 實作,並評估其效能表現,隨後指出改進方案
為什麼快?
synchronize_rcu()
→ 一次 GP ≅ 0.6–1 ms。為什麼安全?
free()
前執行 一次 synchronize_rcu()
,故滿足語義;每個 writer thread 各自維護一組陣列與計數器,避免鎖競爭。
用 CLOCK_MONOTONIC
避免被 NTP、date
調整影響。
安全性重點:
free()
緊跟在synchronize_rcu()
之後,永遠不會早於 GP。
update_global_state()
(Writer 快路徑)atomic_exchange(..., memory_order_release)
release
:保證先寫入 *new_state
,再讓其他 CPU 看到指標;acquire
/consume
load 就能正確讀到資料。*push → flush
確保程式結束時不留下尚待回收的記憶體。
memory_order_acquire
對應 writer 的 release
,確保指標→資料順序。atomic_signal_fence(seq_cst)
,成本極低。*無論批次與否,真正進入 GP 時仍需 一次 membarrier 來截斷 A/F、C/F 之間的潛在亂序。
gp_holdouts
futex 等待返回後的 Fence H確保「所有 reader 退出」→「釋放資料」有全域 SC 順序。
指標(32R╳8W, 20 µs) | 每筆即 GP | 批次 256/5 ms | 說明 |
---|---|---|---|
Updater 迴圈 /3 s | ~45 | ~2500 | ↑約 60 倍 |
平均 GP 延遲 | 60–90 ms | 0.8–1 ms | ↓約 70 倍 |
Reader 吞吐 | 3–5×10⁸ | 3–5×10⁸ | 幾乎不變 |
批次(thread-local batch)
把大量寫入先累積起來,一次 batch_flush()
送到全域佇列,降低每筆寫入的 CAS 次數與記憶體屏障。
延遲回收(call_rcu + reclaimer)
Writer 永遠不自己跑 GP;真正的 synchronize_rcu()
只在背景 reclaimer 執行緒中發生,寫端完全非阻塞。
每位 writer 都有自己的小池子;Writer path 只有 push 陣列,無鎖、無系統呼叫。
1 筆更新 → 1× atomic_exchange
+ 1× push;絕大多數讀者場景耗時 < 100 ns。
batch_flush()
──把 L1 丟進 L2此時 沒有 GP;Writer flush 完立即返回,繼續衝下一批。
call_rcu()
──MPSC lock-free push單純「把新節點掛到頭」的 CAS;保證 push 前的寫入對 reclaimer acquire 可見。
reclaimer_fn()
──偷走→GP→free背景執行緒把所有 callback 一口氣 搬走,一次 GP 就釋放整批。
GP 數量 = callback 佇列清空次數,遠低於寫入頻率。
main()
中)務必使用課程規範的術語,見 https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics
不要依賴大語言模型來產生內容,以課程教材和 Linux 核心第一手材料為主
路徑 | 主要 atomic operation | 為何安全 |
---|---|---|
Writer push L1 → L2 | call_rcu() :store-release (CAS 成功) |
保證 舊指標內容 先於 cb_head 更新對 reclaimer 可見 |
Reclaimer 取得 list | exchange-acquire |
讀到最新 list 之後,能看到所有節點 arg 實體 |
GP 之前 不得 free | synchronize_rcu() 強制等待所有 reader 離開舊世界 |
符合 RCU 安全定義 |
GP 之後 free() | Reader 此時最早也看到新指標,不會再解參考舊指標 | 無 use-after-free |
synchronize_rcu()
;背景 GP 與 writer 解耦。call_rcu()
就對應一次 GP
(或小批次)。batch[256]
,GP + free()
→巨集 | 作用 | 預設 |
---|---|---|
COALESCE_BATCH_SIZE |
單批最多 callback | 256 |
COALESCE_TIMEOUT_US |
最長等待時間 | 5000 µs |
call_rcu()
— lock-free MPSC push (L43)cb->arg
。usleep(200)
,避免忙迴圈。now_us()
採 CLOCK_MONOTONIC
,不受 NTP 影響。free()
永遠排在 GP 之後,符合 RCU 語意。stop_reclaimer
置真後,再把殘餘 callback 清完;避免洩漏。call_rcu()
。__thread unsigned long long iterations
:量化每執行緒工作量,便於觀察效能。-r/-u/-t/-i
:可快速調換 Reader/Updater 數與更新間隔,驗證不同負載下 GP 合併效果。務必使用課程規範的術語,見 https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics
不要依賴大語言模型來產生內容,以課程教材和 Linux 核心第一手材料為主
路徑 | 主要atomic operation | 保證 |
---|---|---|
Writer → cb_head | CAS release | callback 內容對 reclaimer 可見 |
Reclaimer 偷 list | exchange-acquire |
看到每個 cb 內 arg 的最新值 |
Reclaimer → free() | synchronize_rcu() 後 |
Reader 不再持有舊指標,避免 UAF |
測項 | 觀察重點 |
---|---|
Avg/Max GP 間隔 | 應落在 5 ms 以內,除非寫入頻率極低 |
Updater p99 latency | 理想值 ≈ atomic_exchange + malloc ≈ 200 ns |
Reclaimer CPU 占用 | 高频寫入時大幅低於「每筆 GP」版本 |
寫端阻塞 ≈ 0,GP 數量取決於「匯入速度」vs 「批次門檻」。
如需再壓縮延遲,可改成 動態 BATCH_SIZE(根據 cb 積壓量調整)。
synchronize_rcu()
全在背景執行緒,不再打斷 Updater。開發環境
本次實驗以 32 個 reader、8 個 updater 執行緒為測試架構,統一測試時間 3000 ms,採用不同的 updater interval(-i)參數,觀察四種 RCU 優化版本的寫入與讀取效能。
測試參數 | 數值 |
---|---|
Readers | 32 |
Updaters | 8 |
測試時間 | 3 秒 |
Updater 間隔 -i | 1、2、5、20、100 μs |
改進以下:
版本 | -i=1 μs | -i=2 μs | -i=5 μs | -i=20 μs | -i=100 μs |
---|---|---|---|---|---|
main | ~107 / 3.27e9 | ~107 / 2.96e9 | ~104 / 2.96e9 | ~95 / 2.96e9 | ~103 / 2.96e9 |
delay | 120,147/2.69e9 | 118,031/2.67e9 | 113,834/2.70e9 | 93,502/2.72e9 | 48,012/2.80e9 |
batch | 7,604/2.94e9 | 7,870/2.95e9 | 7,244/2.94e9 | 6,313/2.96e9 | 2,868/2.95e9 |
gpc | 118,740/2.67e9 | 117,447/2.66e9 | 112,167/2.68e9 | 91,890/2.71e9 | 47,948/2.79e9 |
(單位:Updater 次/3秒 / Reader 次/3秒;科學記號 e.g. 2.96e9 = 2,960,000,000)
圖:各 RCU 策略下,隨 updater 間隔 -i 改變,Updater 與 Reader 吞吐量的變化(橫軸 log 標示)
main(每筆都同步 GP)
main_delay(每筆 usleep + GP)
main_batch(累積批次 GP)
main_gpc(延遲回收+reclaimer 合併 GP)
機制 | Updater 吞吐 | Reader 吞吐 | GP 開銷主控點 | 適用場景 |
---|---|---|---|---|
main | 最差 | 高 | 每筆更新後執行 | 低頻寫,高頻讀 |
main_delay | 極佳(看 -i) | 高 | usleep > GP | 寫端負載中等 |
main_batch | 普通 | 高 | 256 筆合併一次 GP | 間歇高頻寫 |
main_gpc | 最佳 | 高 | 寫端僅送 callback | 高頻寫、低延遲 |
承接前章 mini-RCU 四個版本(main、delay、batch、gpc)的測試架構,本章新增參考實務界廣泛應用的 Userspace RCU (liburcu) 進行同場壓力測試。
測試條件完全一致(32 reader、8 updater、3 秒、-i 1/2/5/20/100),確保能直接比較不同實作的真實吞吐極限與行為。
版本 | 實現方式簡述 |
---|---|
main | 每筆寫入即同步 GP |
delay | 每筆寫入前 usleep,仍每筆 GP |
batch | 累積 256 筆/5ms,批次 GP |
gpc | 寫端僅送 callback,集中合併 GP |
liburcu | 官方 API,call_rcu 與 rcu_read_lock 典型用法 |
版本 | -i=1 | -i=2 | -i=5 | -i=20 | -i=100 | 讀端吞吐 (範例) |
---|---|---|---|---|---|---|
main | 109 | 106 | 106 | 116 | 104 | 3.2e9 |
delay | 119,716 | 119,010 | 113,491 | 92,655 | 47,925 | 2.7e9 |
batch | 7,786 | 8,101 | 7,410 | 5,515 | 2,720 | 2.9e9 |
gpc | 117,598 | 115,839 | 111,514 | 91,508 | 47,741 | 2.6e9 |
liburcu | 116,591 | 116,232 | 111,783 | 91,775 | 47,807 | 3.99e8 |
單位:Updater 次/3秒,Reader 次/3秒(科學記號 e.g. 3.2e9 = 3,200,000,000)
文字訊息不要用圖片展現,確認圖片的存取權限
寫端效能比較
讀端效能比較
寫入/讀取雙極限情境
編號 | 目標敘述 |
---|---|
G1 | 把自製 mini-URCU hash table 以 Module 方式植入 Valkey,驗證「讀多寫少」場景能否 降低延遲、提升吞吐。 |
G2 | 與 Valkey 原生 SET/GET 進行 定量比較(ops/sec、avg / p95 / p99 latency)。 |
G3 | 探索 桶數 與 GP 批次回收 (GPC) 對寫入效率的影響,提出最佳化指引。 |
rcu_ht.c
)rcu_read_lock/unlock()
,零鎖、零系統呼叫。synchronize_rcu()
。rcuht_module.c
)項目 | 規格 |
---|---|
CPU | Intel® NUC 10 i7 (8c/16t) |
OS | Ubuntu 24.04 LTS × Linux 6.8 |
Valkey | commit 293be3e3 + rcuht.so |
liburcu | 0.14 (memb) |
測試工具 | valkey-benchmark (500 k req / 500 conn / pipeline 16 / key space 100 k) |
啟動 command
注意用語!
實作 (port) | 指令 | Throughput (ops/s) | Avg Latency (ms) |
---|---|---|---|
RCU-HT :6380 | GET |
902 527 | 7.95 |
SET |
145 349 | 0.70 | |
Native :6379 | GET |
1 179 245 | 6.01 |
SET |
970 874 | 7.48 |
(吞吐取 rps
;延遲取 avg_latency_ms
,皆來自 valkey-benchmark --csv
輸出)
Throughput (ops/sec) | Average latency (ms) |
---|---|
修正圖片的存取權限