# 並行程式的同步機制: rseq 系統呼叫(Restartable Sequence)

## 引言

對於在 userspace 中運行的並行(Concurrent)程式碼，它們多數時候與在 kernel 中運行的程式碼有相同的限制。其中之一是在進行跨 CPU 的操作時，往往會造成對性能的衝擊。這意味著相同資料的存取，應盡可能在相同 CPU 上完成。

但與 kernel space 程式碼的不同是，userspace 的每段程式碼都不能進入 atomic context。所謂 atomic context，是指一段不能被[搶佔(preemption)](https://en.wikipedia.org/wiki/Preemption_(computing))的程式碼。藉由禁用搶佔，可以保護該段程式碼在同一個 CPU 中完成。而 userspace 中由於不存在此種性質。

針對此問題，Google 的工程師 Paul Turner 在 2013 的 LPC 上[展示](https://blog.linuxplumbersconf.org/2013/ocw/system/presentations/1695/original/LPC%20-%20PerCpu%20Atomics.pdf)了一種名為 "Restartable Sequence" 的技術，作為能在 userspace 達成類似 atomic context 效果的有限解決方案。這在建立 **wait-free** 的 userspace per-CPU 資料上帶來幫助，後者能為應用程式的同步帶來顯著的效能提升。並在多年的努力下，Restartable sequence 於 Linux 4.18 開始支援([rseq.c](https://github.com/torvalds/linux/blob/master/kernel/rseq.c))。

## Per-CPU 資料

Ref

## 並行程式在 userspace Per-CPU 資料的問題

Per-CPU 資料能在現代硬體上維持程式的擴展性(scability)，進而帶來性能的優勢。而為了確保同步正確性，必須將[並行控制](https://en.wikipedia.org/wiki/Concurrency_control)演算法與 Per-CPU 的資料相結合。理想的演算法應該要能夠提供高效的性能，同時保證資料在不同 CPU 同時存取時，可以保持一致，即正確地同步。

### 案例

想像在維護一個 per-CPU 的 linked list，並且需要在 list head 插入一個新元素。對應的程式碼會像以下這樣:

    new_item->next = list_head[cpu];
    list_head[cpu] = new_item;

而這樣看似簡單的程式碼，在多處理器環境中可能存在問題: 其一，如果在兩個語句之間發生搶佔，則另一個 process 可能會介入並插入新元素；當原始進程恢復時，`list_head[cpu]` 將被覆蓋，導致最終 linked list 的結果不正確。如下範例:

1. Process A/`new_item1->next = head`

digraph graphname{
        node[shape=box]
        
        head[shape=plaintext,fontcolor=red]
        rankdir=LR
        {
            rankdir = LR
            A[label=A]
            B[label=B]
            C[label=C]
            N[label="new_item1"]
            NULL[label=NULL,shape=plaintext]
        }
        
        {
            rank="same";
            head->A     
        }
        N->A
        A->B->C->NULL
	}

2. Process B/`new_item2->next = head`

digraph graphname{
        node[shape=box]
        
        head[shape=plaintext,fontcolor=red]
        rankdir=LR
        {
            rankdir = LR
            A[label=A]
            B[label=B]
            C[label=C]
            N1[label="new_item1"]
            N2[label="new_item2"]
            NULL[label=NULL,shape=plaintext]
        }
        
        {
            rank="same";
            head->A     
        }
        N1->A
        N2->A
        A->B->C->NULL
	}

3. Process B/`head = new_item2`

digraph graphname{
        node[shape=box]
        
        head[shape=plaintext,fontcolor=red]
        rankdir=LR
        {
            rankdir = LR
            A[label=A]
            B[label=B]
            C[label=C]
            N1[label="new_item1"]
            N2[label="new_item2"]
            NULL[label=NULL,shape=plaintext]
        }
        
        {
            rank="same";
            head->N2     
        }
        N1->A
        N2->A
        A->B->C->NULL
	}

4. Process A/`head = new_item1`

digraph graphname{
        node[shape=box]
        
        head[shape=plaintext,fontcolor=red]
        rankdir=LR
        {
            rankdir = LR
            A[label=A]
            B[label=B]
            C[label=C]
            N1[label="new_item1"]
            N2[label="new_item2"]
            NULL[label=NULL,shape=plaintext]
        }
        
        {
            rank="same";
            head->N1     
        }
        N1->A
        N2->A
        A->B->C->NULL
	}

相反，如果將進程移至不同的 CPU，它可能會在每個 CPU 的列表之間混淆，或者與原始 CPU 上的新進程同時運行；無論哪種情況，結果都會導致列表損壞，並且開發人員不得不在深夜打電話。

其二，如果將 process 移至不同的 CPU，它可能會在每個 CPU 的 list 之間混淆，或者與遷移到的 CPU 上的另一個 process 產生競爭。最後也是造成錯誤結果。

### 現有的同步機制

在解決上述正確性的問題上，最常見的而可擴展性最差的方式是[互斥鎖Mutual exclusion](https://en.wikipedia.org/wiki/Mutual_exclusion)。藉由一次只允許一個執行緒修改資料來保證正確。但是這種方式在 per-CPU 資料上的應用效果並不好。由於只有一個執行緒可以運行 critical section，因此可能會有多個執行緒等待獲取鎖。

另外一種方式是使用如 [CAS(compare-and-swap)](https://en.wikipedia.org/wiki/Compare-and-swap) 的 atomic operation。但這個方案的問題是，atomic operation 在現代處理器上有很大的[指令周期(Instruction Cycle)](https://en.wikipedia.org/wiki/Instruction_cycle)開銷。且在同時只有一個執行緒執行該段程式碼的情況下，也必須承擔 atomic operation 的成本。

對於 per-CPU 資料，kernel space 能藉由關閉中斷來保護相關數據，但在 userspace 該方式並不可行。這是 Restartable Sequence 被提出來的動機。

## 何謂 "Restartable Sequence"?

Restartable Sequence 是基於以下觀察: 許多與效能相關的程式碼(例如上述範例)都共享一個特定性質，即 Critical section 可以被細分為準備(prepare)階段和提交(commit)階段，其中提交步階段是單一的 CPU 指令。且如果在 Crtical section 期間中被中斷，重新執行 critical section 仍可以維持正確性。

若在提交前就發生以下其中一種情況，Crtical section 都視為被中斷:

* 執行緒被遷移到另一個 CPU
* 有 signal 被傳遞到執行緒
* 執行緒被搶佔

藉由此設計，於最佳情況，即 crtical section 不會被中斷時，因為可以捨棄鎖和 atomic operation，不需要任何額外開銷，

用更具體的例子說明，第一行的 `new_item->next = list_head[cpu]` 在其執行的 process 之外沒有可見的影響(對於 list 本身的使用是沒有改變的，因為從操作上以 head 為起點)。如果該 process 在該行之後被搶佔，它可以從頭再次執行。

但第二行的 `list_head[cpu] = new_item` 就具有其他 process 可見的效果。因此，總結來說如果正在執行的程式在中間被搶佔，不得執行到最後。相反，如果這段程式碼不被打斷地運行，則無需 lock 或 atomic operation 即可正確完成。這會反過來使它變得更快。

因此，Restartable Sequence 就是如字面意義的「可被重新開始的一段程式碼序列」，而系統將提供機制以實現如上所述的設定和提交階段。如果某個 process 在段序列中運行時被搶佔（或將其移至另一個 CPU），則控制權將跳到特殊的 "restart handler"。這個 handler 將重新啟動這段序列的執行。

## 使用方式

### System call
Restartable sequence 的具體使用有點棘手。因為 userspace 必須能夠告訴 kernel 此類序列何時運行。但是直接執行系統呼叫會導致執行緒持有鎖，導致違背最初想加速的目的。

因此，Restartable sequence 的實作是由 userspace 和 kernel space 之間共享的特殊記憶體區域進行管理。具體來說，userspace 需設定一個特殊的 thread-local [`struct rseq`](https://elixir.bootlin.com/linux/v6.14.2/source/include/uapi/linux/rseq.h#L62) 結構並使用 `rseq()` 系統呼叫將該結構傳遞給 kernel。而 `struct rseq` 中的關鍵成員是指向 [`rseq_cs`](https://elixir.bootlin.com/linux/v6.14.2/source/include/uapi/linux/rseq.h#L45) 結構的指標(準確來說，是 `rseq_cs` 存在的位址)。`rseq_cs` 用來定義 critical section。

/*
 * struct rseq_cs is aligned on 4 * 8 bytes to ensure it is always
 * contained within a single cache-line. It is usually declared as
 * link-time constant data.
 */
struct rseq_cs {
	/* Version of this structure. */
	__u32 version;
	/* enum rseq_cs_flags */
	__u32 flags;
	__u64 start_ip;
	/* Offset from start_ip. */
	__u64 post_commit_offset;
	__u64 abort_ip;
} __attribute__((aligned(4 * sizeof(__u64))));

* `start_ip` 是 critical section 中第一條指令的位址
* `post_commit_offset` 是 critical section 的長度(以 bytes 為單位)
* `abort_ip` 是當序列在完成之前被打斷（搶佔或 CPU 遷移）時要跳到的指令位址
* `version` 定義該結構的版本(確保 userspace 的使用符合 kernel 支援)
* `flag` 調整重啟行為特定特性

透過在 crtical section 前，將 `rseq_cs` 的位址儲存到核心中註冊的 `rseq` 結構中，當核心搶佔時，它就能夠檢查 Program counter 以查看是否在執行 crtical section 。若是，當執行緒恢復執行後，它將跳到 `abort_ip` 位址的 Abort handler，嘗試重新啟動。

Critical section 和 Abort handler 的實作都有限制。首先， Abort handler 必須位於 Critical section 之外。其次，Critical section 內不允許進行 system call，嘗試執行 Critical section 將導致 Segmentation Fault 而終止。

`rseq` 的介面在設計上附加了限制，即每個執行緒只能註冊一個 `rseq_cs` 到 kernel。這是因為即便是單一個 `rseq` 也會導致排程器增加開銷，如果允許定義一個 `rseq_cs` 的 list，這帶來的成本將會是不可接受的。

但是當一個執行緒中可能必須存在多個 restartable sequence 時，這就會在使用上帶來問題。為了使 restartable sequence 變成有效的機制，必須有方法來防止這之間的互相干擾。

### Library

由於 `rseq` 在 userspace 的使用相對一般的系統呼叫晦澀難懂，且存在上述限制，一般來說仰賴函式庫的支援。

在 glibc 2.35 開始支援相關的介面。為了解決前面提到的共享問題，glibc 提出的實作方式是將 glibc 置於中間 kernel 和 userspace 應用的中間層，以協調前後端的使用。

因此，`rseq` 結構的初始化與 `rseq()` 系統呼叫的註冊，是由 glibc 在初始化期間就完成的。如果應用程式不想要 glibc 的介入，則可以執行應用時加上 `GLIBC_TUNABLES=glibc.pthread.rseq=0` 環境變數來停用此功能。

想透過 glibc 使用 restartable sequence 需要 include `<sys/rseq.h>`。其中定義了 `rseq` 和 `rseq_cs` 結構。此外也包含一些重要變數。

其一是 `__rseq_size`。這將是函式庫註冊的 `rseq` 結構的大小，如果由於核心不支援或停用等原因未進行註冊，則為零。

再來是 `__rseq_offset`。glibc 註冊的 rseq 結構被放在 **Thread control block (TCB)**。具體是可以在距 thread pointer `__rseq_offset` bytes 偏移處的位置找到。
* 而 thread pointer 的取得則特定於架構。在某些架構上，GCC 提供了 `__builtin_thread_pointer()` 來取得，但存在例外。碰巧 x86 就是其中的例外之一，其 thread pointer 是儲存在 FS 暫存器中。

最後是 `__rseq_flags`，對應到註冊給 kernel 相關的設定。但目前始終保持為 0。

> 詳見 [35.2.2.5 Restartable Sequences](https://www.gnu.org/software/libc/manual/html_node/Restartable-Sequences.html)

glibc 註冊的 `rseq` 結構由給定執行緒內的所有使用者共用，但每個使用者都應建立自己的 `rseq_cs` 結構來描述其關鍵部分。在進入 critical section 前，執行緒應該將其 `rseq_cs` 結構的位址儲存到 `rseq` 結構的 `rseq_cs` 欄位中，然後在退出時將該欄位重設為 NULL。這種設計意味這 restartable sequence 中不能有另一個 restartable sequence。但考慮其使用情境，這應當不成問題。

位於 `abort_ip` 的程式碼必須以特殊的 `RSEQ_SIG` 標記開頭，後者的定義方式與架構相關。留意到如果呼叫中止程式碼執行，`rseq_cs` 欄位會被 kernel 清除，必須在重新進入 critical 之前重新設定好。

## 範例

### CPU index

Restartable Sequence 的一個使用情境是取得執行緒運行所在的 CPU 編號，通常用來當成存取 Per-CPU 資料的 index。如果使用舊有的 `sched_getcpu()`，在 ARM 上需要 system call，而 x86 則可以使用 VDSO。但 `rseq` 允許讀取 kernel 和 userspace 共享的 `struct rseq` 結構中的 CPU 編號值，後者的存取效率更好。

### 記憶體配置器

對於記憶體分配器，良好的設計需要同時為多個執行緒提供服務，因此相關的 lock 很容易受到激烈的競爭(Contention)。對此，TCMalloc 提出一種維護 Thread-local cached blocks 的方法，藉為 thread 維護各自獨立的記憶體區塊來減少競爭。

:::info
"TC" 即 "Thread Cached" 之簡稱
:::

然而 Threads 的建立與消滅是動態的，因此相關資料結構就必須動態調整。且大型的應用可能有數萬個 thread，則 Per-Thread 作法的成本在此情況下將大幅增加。此外，由於 context swtich 時，對於目前 CPU 上的執行緒，可能因前一個執行緒做了完全不同的操作，或者該執行緒是由其他 CPU 遷移而來，導致 CPU miss 發生而帶來額外延遲。

因此，目前 TCMalloc 不再使用 Per-Thread，而是改為使用 Per-CPU 來維護記憶體配置器的資料。這有利對 CPU cache 的運用: 因為每分資料各自只能由一個 CPU 存取。此外，因為對 Per-CPU 資料的操作不需要與其他 CPU 同步，過程無須涉及 atomic operation，因此對效能更佳。

### 延伸閱讀
> * [Restartable Sequence Mechanism for TCMalloc](https://google.github.io/tcmalloc/rseq.html)
> * [Atomicless Concurrency](https://mcyoung.xyz/2023/03/29/rseq-checkout/)

## Reference

* [Restartable sequences](https://lwn.net/Articles/650333/)
* [Restartable sequences in glibc](https://lwn.net/Articles/883104/)
* [The 5-year journey to bring restartable sequences to Linux](https://www.efficios.com/blog/2019/02/08/linux-restartable-sequences/)

https://lwn.net/Articles/1016408/

https://zhuanlan.zhihu.com/p/376868361