rseq，從零講起——讓 user space 偵測被搶佔，而不是用鎖去防它

kernel 裡到處是 per-CPU 資料結構，因為它有一個 user space 沒有的特權：它能關掉搶佔（preemption），在一段臨界區裡確定自己不會被排到別的 CPU。這篇要講的 restartable sequences（rseq）就是把這個能力的一個替代品交到 user space 手上——不是讓你關搶佔，而是讓你在被搶佔之後知道、然後重做。讀完你會知道 rseq 解決什麼問題、它的臨界區與 abort 機制長什麼樣、為什麼 malloc 跟計數器這種東西能靠它做出不用 atomic 的 fast path，以及它在什麼情況下不划算。

同一顆 CPU 上的計數器，為什麼還要付 atomic 的錢

先把場景縮到最小。你要做一個 per-CPU 計數器：每顆 CPU 自己一格，執行緒讀出「我現在在哪顆 CPU」，然後對那一格加一。聽起來不需要鎖——每顆 CPU 各加各的，不會互相踩。問題藏在「我現在在哪顆 CPU」與「對那一格加一」這兩件事之間。

在這兩步之間，排程器可以隨時把你的執行緒從 CPU 3 搬到 CPU 7。於是你讀到的是 CPU 3、加一加到的卻是另一顆正在跑你的 CPU——或者更糟，另一條執行緒此刻也在那一格上動手。你以為的「per-CPU、不會衝突」其實有一個你看不見的窗口：讀 CPU 編號到實際寫入之間，那段時間你不擁有任何東西。

傳統解法是把那一格的加一變成 atomic 操作，靠 CPU 的 read-modify-write 指令保證不被打斷。代價直接寫在指令上。EfficiOS 那篇談 rseq 的文章把問題講得很白：

「Concurrency control algorithms, paired with per-CPU data, are integral to ensuring low-level libraries and high-performance applications scale properly on today's hardware.」

它接著點出 atomic 的成本來源：

「The x86 `lock` prefix can easily add many cycles to the cost of the same instruction without the prefix.」

翻成工程語言：同一條加法指令，掛上 lock prefix 之後要多花可觀的 cycle，因為它得鎖住快取行、跟其他核心協調 cache coherence。在沒有 contention、其實只有你一個人在動這一格的情況下，這些 cycle 全是白付的——你付的是「以防萬一被別人搶」的保險，但大多數時候根本沒人來搶。per-CPU 資料結構的整個賣點就是「大多數時候只有本地這顆 CPU 在動」，偏偏 atomic 把這個 common case 也課了重稅。

kernel 自己不付這筆稅，因為它在臨界區裡可以 preempt_disable()。一旦關掉搶佔，「讀 CPU 編號」到「寫那一格」之間沒有人能把它搬走，也沒有別的 thread 能插進來，於是它可以用普通的 load / store，不需要 atomic。user space 沒有這個按鈕——你不能要求 kernel 在你跑這三行的時候別排程別人。rseq 要補的，正是這個落差。

關不掉搶佔，那就偵測它——rseq 的核心翻轉

rseq 的設計把問題反過來想。既然 user space 不能阻止搶佔與遷移，那就接受它會發生，但保證一件事：只要在臨界區中途被搶佔或被搬到別的 CPU，這段臨界區就不算數，kernel 會把控制權跳到一段 abort handler，讓你從頭再來一次。

關鍵在於臨界區的結構。它被切成兩段：一段是準備工作，可以無限次重來；最後一個動作是 commit——一條把結果寫進記憶體的單一指令。Linux 的 kernel 文件這樣描述 rseq 的目的：

「userspace to perform update operations on per-cpu data without requiring heavyweight atomic operations.」

TCMalloc 的文件把臨界區的契約講得最精準，因為它是真的拿 rseq 來做 allocator 的人：

「The entire sequence, except for its final store to memory which _commits_ the change, must be capable of starting over.」

把這句拆開看。準備階段做的事——讀 CPU 編號、算出要寫的位址、把舊值載進暫存器——全都是冪等的，重做幾次都沒有副作用。真正改變世界的只有最後那條 store。設計的精髓是：如果搶佔發生在 commit 之前，那麼世界還沒被改，丟掉重來完全安全；如果搶佔發生在 commit 之後，臨界區其實已經結束了，沒什麼好丟的。中間那條「commit 是單一指令」的要求，就是為了讓「之前」與「之後」之間不存在一個半完成的灰色地帶。

那「重來」具體怎麼發生？kernel 在每次 context switch 之後、訊號送達之前，會檢查當前執行緒有沒有註冊 rseq、指令指標是不是正落在某個已宣告的臨界區範圍內。如果是，它就不讓你從被打斷的地方繼續，而是把指令指標改到你預先登記的 abort handler。TCMalloc 文件描述這個動作：

「it restarts the thread at an abort sequence, the abort sequence determines the interrupted restartable sequence, and then returns to control to the entry point of this sequence.」

下面這個 widget 把整件事跑成動畫。一條執行緒沿著臨界區往 commit 走，搶佔事件隨機落下；落在 commit 之前，kernel 把它彈回 abort handler 重來，落在 commit 之後則算數。你會看到大多數時候它一次就過，偶爾被打斷就重跑——重跑的成本只在被打斷的那一次。

有一個容易誤會的點要先釘住：rseq 不保證臨界區只跑一次，它保證的是「commit 要嘛在你不被打斷的狀態下發生、要嘛不發生」。一段臨界區可能被 abort 重做好幾次才終於跑完一輪——但每一次失敗都沒有寫進任何東西，所以對外界來說，最終只有成功那一輪的 commit 看得見。這跟 atomic 的差別在這裡：atomic 是「保證這一條指令不被打斷」，rseq 是「允許被打斷，但被打斷的就丟掉」。

kernel 與 user space 之間的那塊共用記憶體

要讓 kernel 知道「現在這條執行緒正落在某個臨界區裡」，user space 得先把資訊放在一塊 kernel 看得到的地方。這塊地方就是 struct rseq，透過 rseq(2) system call 註冊成一個 thread-local 的記憶體區。kernel 文件描述它的角色：

「Restartable Sequences allow to register a per thread userspace memory area to be used as an ABI between kernel and userspace.」

注意「ABI between kernel and userspace」這個說法。這塊記憶體不是普通的 user 資料，它是雙方約好欄位意義的介面：有些欄位是 kernel 寫、user space 讀；有一個欄位是 user space 寫、kernel 讀。前者讓 user space 不用 system call 就能拿到「我現在在哪顆 CPU」「哪個 NUMA node」這類資訊；後者讓 user space 告訴 kernel「我現在在跑哪一段臨界區」。kernel 文件列出由 kernel 維護的唯讀欄位，包括 cpu_id_start、cpu_id、node_id、mm_cid，以及一個指向臨界區描述子的 rseq_cs 欄位與一個 flags 欄位。

下面這張圖把這塊共用記憶體攤開，標出每個欄位是誰寫誰讀，以及 rseq_cs 指到的那個臨界區描述子裡放了什麼。

這裡有一個容易被略過、但實作上很關鍵的安全設計：rseq 的 ABI 在 abort_ip 指向的位址前面放了一個約定好的 4-byte 簽章（signature）。合理的推測是，kernel 在把控制權跳過去之前會先核對這個簽章——因為 abort_ip 是 user space 自己填的，少了這層檢查，偽造一個 rseq_cs、把 abort_ip 指到任意位址，就可能變成一個由 kernel 幫忙觸發的控制流劫持。要求 abort handler 前面帶一個雙方約好的魔術數字，等於要求「你跳過去的地方確實是一段被當成 abort handler 編譯出來的程式碼」，而不是任意 gadget。

另一個欄位設計值得停一下：cpu_id_start 與 cpu_id 為什麼分兩個？cpu_id_start 是給臨界區一開始拿來算位址用的快取值，cpu_id 是 kernel 持續更新的當下值。fast path 用 cpu_id_start 算出要動哪一格，commit 之前如果被搬走，kernel 會 abort 整段——所以即使 cpu_id_start 已經過時，也不會造成寫錯格子，因為那一輪根本不會 commit。這就是「偵測而非防止」在欄位層級的體現。

值得補一句 kernel 是什麼時候做這個檢查的。它不是每條指令都盯著看——那樣太貴。kernel 文件寫得很明確：核心在每次 context switch 之後、訊號送達之前處理 rseq。換句話說，搶佔與遷移的發生點，本來就是核心要做排程切換的那一刻；rseq 只是讓核心在那個它原本就要停下來的點，順手多看一眼當前執行緒的指令指標有沒有落在已宣告的臨界區裡，有的話就改寫指令指標。這個設計讓 abort 的偵測幾乎不增加額外成本，因為它搭的是 context switch 這班本來就要開的車。

一段 rseq critical section 拆開看

把前面講的東西具象成程式碼。一段 rseq 的 fast path 在組語層面有三個區段，分別對應描述子裡的三個位址。下面三個 tab 把同一個「per-CPU 計數器加一」的 fast path 拆成準備段、commit、abort handler 並排看——重點不是組語細節，是看清楚哪一行是那條神聖的單一 commit 指令、以及失敗時控制流往哪走。

// 在臨界區開始前，把這段 rseq_cs 描述子的位址寫進 struct rseq 的 rseq_cs 欄位
// 從這裡起 kernel 知道：指令指標若落在本區間且被搶佔，就跳 abort
start_ip:
    cpu = load   rseq.cpu_id_start      // 讀快取的 CPU 編號（普通 load，不用 atomic）
    slot = base + cpu * SLOT_SIZE        // 算出本 CPU 那一格的位址
    old  = load   [slot]                 // 載入目前計數值
    new  = old + 1                       // 純計算，沒有副作用，重做幾次都一樣
// 以上每一行都可以從頭再來；世界還沒被改變

// commit：唯一一條把結果寫回記憶體的指令
// 設計鐵律——commit 必須是單一 store，沒有半完成狀態
    store [slot] = new                    // ← 這一條就是 commit
post_commit_ip:                           // start_ip + post_commit_offset 落在這
// 若搶佔發生在 store 之前：本輪沒寫進任何東西，abort 重來完全安全
// 若搶佔發生在 store 之後：臨界區已結束，preempt 無害
// 普通 store，不需要 lock prefix，因為「被打斷就丟掉」取代了「不准被打斷」

// abort handler：kernel 偵測到中途被搶佔／遷移時，把指令指標改到這裡
// 注意 abort_ip 的前 4 byte 必須是雙方約好的簽章，kernel 跳過來前會核對
.long  RSEQ_SIGNATURE                     // abort_ip 之前的魔術數字（防控制流劫持）
abort_ip:
    jmp  start_ip                         // 最單純的 abort：整段從頭再來一次
// 也可以在這裡做別的補救，但最常見就是直接 retry
// 重做的成本只在「真的被打斷」那一次發生

這個結構解釋了為什麼 rseq 的 fast path 能完全避開 atomic：準備段全是普通 load 與算術，commit 是普通 store，沒有任何一條指令需要 lock prefix。同一顆 CPU 上不會有兩條執行緒同時跑——因為要嘛你沒被搶佔（那就是你獨占這顆 CPU 的這段時間），要嘛你被搶佔了（那這一輪整個作廢）。正確性不是靠指令的原子性撐起來，是靠「被打斷就不算數」這條規則撐起來。

TCMalloc 文件把這個保證的範圍寫得很精確：一段臨界區的承諾是「execute a region to completion (atomically with respect to other threads on the same CPU) or to be aborted if interrupted by the kernel.」注意那個括號裡的限定——原子性是相對於同一顆 CPU 上的其他執行緒而言。rseq 不保證跨 CPU 的原子性，它根本不需要：每顆 CPU 動自己那一格，跨 CPU 本來就不會踩到同一塊記憶體。它要排除的只有「同一顆 CPU 上、在我這段準備到 commit 之間，有別人插進來改了我正要動的格子」這一種情況，而搶佔正是這種插隊唯一的入口。把搶佔這個入口堵住（偵測到就作廢），同 CPU 上的序列化就自動成立，連鎖都不必擺。

再回頭看那個分兩個欄位的 cpu_id_start／cpu_id 設計，會更有感覺。假設你在 CPU 3 上讀了 cpu_id_start = 3、算好了要動 slot[3]，這時候被搬到 CPU 7。kernel 在 context switch 時發現你的指令指標還落在臨界區範圍內、而且 CPU 變了，於是把你彈回 abort handler。你重來一次，這次讀到的 cpu_id_start 是 7，動的是 slot[7]——永遠不會發生「在 CPU 7 上卻寫了 slot[3]」這種錯位。整個正確性論證不需要任何鎖，只需要 kernel 在搶佔點上誠實地把過時的那一輪丟掉。

它到底快多少——以及什麼時候不划算

rseq 不是免費午餐，它把成本從「每次操作都付 atomic 稅」搬到「只有被搶佔那次付重做的錢」。這個 trade-off 划不划算，取決於你被搶佔的頻率。EfficiOS 把這條取捨講得很直接（這裡引的是 TCMalloc 文件的說法，因為它最白）：

「Choosing to restart on migration across cores or preemption allows us to optimize the common case - we stay on the same core - by avoiding atomics, over the more rare case - we are actually preempted.」

common case 是「我們留在同一顆核心上」，rare case 才是「真的被搶佔」。只要前者遠多於後者，整體就賺。下面這張表是 EfficiOS 量到的實際數字，對比 rseq fast path 與傳統 atomic 做法在不同操作上的加速比。

從這張表能讀出 rseq 的適用邊界。加速比最誇張的是「取得 CPU 編號」與「短計數器」——這些操作本身極短，atomic 或 system call 的固定成本佔比極高，把它拿掉自然倍數驚人。反過來看 LTTng-UST 事件緩衝只有 1.1× 到 1.2×，因為那個操作本來就重，rseq 省下的那點固定成本佔比小。一句話：操作越短、本來 atomic 稅佔比越高，rseq 越值得；操作越重，邊際效益越薄。

這套機制併進主線其實不算太久——restartable sequences 在 Linux 4.18 才被併入核心。在那之前，user space 要對 per-CPU 資料做無鎖更新，幾乎只能回到 atomic 那條路；rseq 之後，kernel 文件描述的那個目標——讓 user space 對 per-CPU 資料做更新而不需重量級 atomic——才真正成為一條可用的 fast path。這也是為什麼底層函式庫會搶著接：對 malloc、allocator、計數器這種被頻繁呼叫的熱路徑，常見情況遠多於被搶佔的情況，省下 atomic 稅的效益就被這個比例放大。

那「被搶佔頻率」這個變數到底怎麼吃掉好處？下面這個 widget 讓你直接拖。橫軸是平均每段臨界區被搶佔的機率，縱軸是相對於 atomic 基準的有效吞吐量——被搶佔越頻繁，重做的次數越多，rseq 的優勢就被磨平，超過某個點甚至會輸給老老實實用 atomic。

這也劃出了 rseq 的限制。它的甜蜜區是「短臨界區 ＋ 低搶佔率」。如果你的臨界區很長、或系統處在高度 oversubscribe（執行緒數遠多於 CPU、被搶佔頻繁）的狀態，重做成本會累積到吃光、甚至倒貼。另外，臨界區裡不能做任何「無法安全重來」的事——不能呼叫會產生外部副作用的 system call、不能在中途 commit 一半的狀態，所有寫入必須收斂到最後那條單一 store。這也是為什麼 rseq 的典型使用者是 malloc（TCMalloc 已公開實作）、memory allocator、per-CPU 計數器這類「臨界區極短、純記憶體操作」的場景，而不是任意一段業務邏輯。

從 user space 工程師的角度，你幾乎不會手寫 rseq 組語——它太底層、abort handler 與簽章的細節太容易出錯。你更可能是「用到它」而不自知：你連結的 malloc、你用的 tracing library（LTTng-UST、Userspace RCU 都已採用），底下可能就跑著 rseq 的 fast path。知道它存在、知道它的甜蜜區與限制，足以讓你在效能分析時多一個解釋變數——當你發現某個 per-CPU 結構在高 contention 下意外地不退化，rseq 很可能就是答案；當你發現它在 oversubscribe 的 container 裡退化得莫名其妙，過高的搶佔率導致 rseq 一直 abort 也是一個要查的方向。

Take-away：rseq 不是更快的鎖，是把「不准被打斷」換成「被打斷就丟掉」——臨界區拆成可重做的準備段加一條單一 commit，kernel 在搶佔時把你彈回 abort handler，於是沒被搶的常見情況一次就過、零 atomic 成本，代價是搶佔頻繁時要不斷重做。