# Restartable Sequences (rseq) 机制

## 1. 概述

Restartable Sequences（rseq，可重启序列）是一种用户态与内核协作的机制，用于实现高效的 per-CPU 数据访问。它允许用户态程序在不使用传统同步原语（如锁或原子操作）的情况下，安全地访问和修改 per-CPU 数据结构。

### 1.1 设计目标

rseq 的核心目标是提供一种**乐观并发**机制：

- 用户态代码可以假设自己不会被打断，直接操作 per-CPU 数据
- 如果确实被打断（抢占、信号等），内核负责将执行重定向到恢复路径
- 这种"要么完整执行，要么从头开始"的语义，避免了传统锁的开销

### 1.2 典型应用场景

- **内存分配器**：tcmalloc、jemalloc 等使用 per-CPU 缓存加速分配
- **引用计数**：per-CPU 引用计数可避免缓存行争用
- **统计计数器**：per-CPU 计数器的无锁更新
- **RCU 读侧临界区**：快速获取当前 CPU 信息

## 2. 核心概念

### 2.1 临界区（Critical Section）

rseq 临界区是一段用户态代码，具有以下特征：

```
┌─────────────────────────────────────────────────────────────┐
│                     rseq 临界区                              │
│                                                             │
│  start_ip ──► ┌─────────────────────────────────┐           │
│               │  1. 读取 cpu_id                  │           │
│               │  2. 使用 cpu_id 索引 per-CPU 数据 │           │
│               │  3. 执行操作（读/改/写）          │           │
│               │  4. 提交点（commit point）        │           │
│  end_ip ────► └─────────────────────────────────┘           │
│                         │                                   │
│                         │ 被打断时跳转                       │
│                         ▼                                   │
│  abort_ip ──► ┌─────────────────────────────────┐           │
│               │  恢复/重试逻辑                    │           │
│               └─────────────────────────────────┘           │
└─────────────────────────────────────────────────────────────┘
```

- **start_ip**：临界区起始地址
- **post_commit_offset**：从 start_ip 到提交点的偏移量
- **abort_ip**：中断恢复地址，必须位于临界区外

### 2.2 用户态数据结构

用户态需要在 TLS（线程本地存储）中维护一个 `struct rseq` 结构：

| 字段 | 大小 | 说明 |
|------|------|------|
| cpu_id_start | u32 | 进入临界区时的 CPU ID |
| cpu_id | u32 | 当前 CPU ID（内核更新） |
| rseq_cs | u64 | 指向当前临界区描述符的指针 |
| flags | u32 | 标志位（保留） |
| node_id | u32 | NUMA 节点 ID |
| mm_cid | u32 | 内存管理上下文 ID |

### 2.3 临界区描述符

`struct rseq_cs` 描述一个具体的临界区：

| 字段 | 大小 | 说明 |
|------|------|------|
| version | u32 | 版本号，必须为 0 |
| flags | u32 | 标志位 |
| start_ip | u64 | 临界区起始地址 |
| post_commit_offset | u64 | 临界区长度 |
| abort_ip | u64 | 中断恢复地址 |

## 3. 工作原理

### 3.1 注册流程

```
用户态                                    内核态
  │                                         │
  │  sys_rseq(rseq_ptr, len, 0, sig)       │
  │ ──────────────────────────────────────► │
  │                                         │ 1. 验证参数
  │                                         │ 2. 记录注册信息
  │                                         │ 3. 设置 NEED_RSEQ 标志
  │                                         │
  │  返回 0（成功）                          │
  │ ◄────────────────────────────────────── │
  │                                         │
```

### 3.2 临界区执行

正常执行时，用户态代码：

1. 将临界区描述符地址写入 `rseq->rseq_cs`
2. 读取 `rseq->cpu_id` 获取当前 CPU
3. 使用该 CPU ID 访问 per-CPU 数据
4. 完成操作后，清除 `rseq->rseq_cs`

### 3.3 内核干预时机

内核在以下事件发生后，返回用户态前进行检查和修正：

```
┌──────────────────────────────────────────────────────────────┐
│                    触发 rseq 处理的事件                        │
├──────────────────────────────────────────────────────────────┤
│  抢占（Preemption）                                           │
│    └─► 调度器切换进程时设置 PREEMPT 事件                        │
│                                                              │
│  信号递送（Signal Delivery）                                   │
│    └─► 设置信号帧前设置 SIGNAL 事件                            │
│                                                              │
│  CPU 迁移（Migration）                                        │
│    └─► 进程被迁移到其他 CPU 时设置 MIGRATE 事件                 │
└──────────────────────────────────────────────────────────────┘
```

### 3.4 返回用户态前的处理

当进程即将返回用户态时，内核执行以下步骤：

```
                    返回用户态前处理流程
                           │
                           ▼
                  ┌─────────────────┐
                  │ 检查 NEED_RSEQ  │
                  │    标志位       │
                  └────────┬────────┘
                           │ 已设置
                           ▼
                  ┌─────────────────┐
                  │  读取 rseq_cs   │
                  │  指针           │
                  └────────┬────────┘
                           │
              ┌────────────┴────────────┐
              │                         │
              ▼                         ▼
        rseq_cs == 0              rseq_cs != 0
        (不在临界区)               (在临界区)
              │                         │
              │                         ▼
              │                 ┌───────────────┐
              │                 │ 当前 IP 在    │
              │                 │ 临界区内？    │
              │                 └───────┬───────┘
              │                    是   │   否
              │              ┌──────────┴──────────┐
              │              ▼                     ▼
              │      ┌───────────────┐     ┌───────────────┐
              │      │ 修改返回地址   │     │ 清除 rseq_cs  │
              │      │ 为 abort_ip   │     │ (lazy clear)  │
              │      └───────────────┘     └───────────────┘
              │              │                     │
              └──────────────┴─────────────────────┘
                             │
                             ▼
                    ┌─────────────────┐
                    │ 更新 cpu_id 等  │
                    │ TLS 字段        │
                    └─────────────────┘
                             │
                             ▼
                      返回用户态
```

## 4. 安全机制

### 4.1 签名验证

注册时用户提供一个 32 位签名值（sig），内核在处理临界区时会验证：

- 读取 `abort_ip - 4` 处的 4 字节
- 必须与注册时的签名匹配
- 防止恶意构造的临界区描述符

### 4.2 地址验证

内核对所有用户态地址进行严格验证：

- `start_ip`、`abort_ip` 必须在用户地址空间内
- `start_ip + post_commit_offset` 不能溢出
- `abort_ip` 必须在临界区外

### 4.3 错误处理

当检测到以下错误时，内核向进程发送 SIGSEGV：

- 用户内存访问失败
- 签名不匹配
- 地址验证失败
- 版本号不为 0

## 5. 与进程生命周期的集成

### 5.1 fork

- **CLONE_VM（线程）**：子线程需要重新注册 rseq
- **fork（进程）**：子进程继承父进程的 rseq 注册状态

### 5.2 execve

执行新程序时，rseq 注册状态被清除，新程序需要重新注册。

### 5.3 exit

进程退出时，rseq 状态随 PCB 一起释放，无需特殊处理。

## 6. 系统调用接口

### sys_rseq

```c
long sys_rseq(struct rseq *rseq, u32 rseq_len, int flags, u32 sig);
```

**参数：**
- `rseq`：用户态 rseq 结构的地址
- `rseq_len`：结构长度（至少 32 字节）
- `flags`：0 表示注册，RSEQ_FLAG_UNREGISTER (1) 表示注销
- `sig`：签名值

**返回值：**
- 成功：0
- 失败：负的错误码

**错误码：**
| 错误码 | 说明 |
|--------|------|
| EINVAL | 参数无效（长度、对齐、flags 等） |
| EPERM | 签名不匹配 |
| EBUSY | 已注册（重复注册相同参数） |
| EFAULT | 地址无效 |

## 7. 辅助向量（auxv）

内核通过 ELF 辅助向量向用户态传递 rseq 支持信息：

| 类型 | 值 | 说明 |
|------|-----|------|
| AT_RSEQ_FEATURE_SIZE | 27 | rseq 结构大小（32） |
| AT_RSEQ_ALIGN | 28 | rseq 对齐要求（32） |

用户态库（如 glibc）使用这些信息来：
- 确定内核是否支持 rseq
- 正确分配和对齐 TLS 中的 rseq 结构

## 8. 使用示例

以下伪代码展示了 rseq 的典型使用模式：

```c
// 1. 注册 rseq
struct rseq *rseq_ptr = &__rseq_abi;  // TLS 中的 rseq 结构
syscall(SYS_rseq, rseq_ptr, sizeof(*rseq_ptr), 0, RSEQ_SIG);

// 2. 定义临界区描述符
struct rseq_cs cs = {
    .version = 0,
    .flags = 0,
    .start_ip = (uintptr_t)&&start,
    .post_commit_offset = (uintptr_t)&&commit - (uintptr_t)&&start,
    .abort_ip = (uintptr_t)&&abort,
};

// 3. 执行临界区
retry:
    rseq_ptr->rseq_cs = (uintptr_t)&cs;
start:
    cpu = rseq_ptr->cpu_id;
    // 使用 cpu 访问 per-CPU 数据
    per_cpu_data[cpu].counter++;
commit:
    rseq_ptr->rseq_cs = 0;
    goto done;

abort:
    // 签名（必须紧挨在 abort 标签前）
    .int RSEQ_SIG
    rseq_ptr->rseq_cs = 0;
    goto retry;

done:
    // 操作完成
```

## 9. 参考资料

- [Linux rseq(2) man page](https://man7.org/linux/man-pages/man2/rseq.2.html)
- [LWN: Restartable sequences](https://lwn.net/Articles/697979/)
- Linux 6.6.21 kernel/rseq.c