RCU（Read-Copy-Update）是一种读者完全无锁、写者通过"复制新版本 + 原子替换指针 + 等待旧读者完成后释放旧版本"实现并发安全的同步机制，被 Linux 内核路由表、模块列表、网络协议栈等读多写极少场景广泛使用，读侧开销接近零。
相关文章：无锁队列（Michael-Scott Queue） · Disruptor（无锁环形缓冲）
目录
| 章节 | 说明 |
|---|---|
| 问题背景 | 为什么需要 RCU |
| 核心数据结构 | rcu_head、全局指针、CPU 状态 |
| 三个核心操作 | rcu_read_lock/unlock、rcu_assign_pointer、rcu_dereference |
| Grace Period：synchronize_rcu | synchronize_rcu 等待所有 CPU 经过 quiescent state |
| 单链表删除节点完整示例 | 读/写/删三条路径完整伪代码 |
| 执行追踪 | 具体数值步骤演示 |
| 与读写锁对比 | RCU 读零开销 vs rwlock |
| 异常与边界场景 | 并发写、超长 grace period、嵌套读锁、用户态 RCU |
| 适用场景 | 适合 vs 不适合 |
| 参考资料 | — |
问题背景
读写锁的痛点
rwlock 读路径：
读者 → spin_lock_read(&rwlock) // CAS 递增引用计数（写 cacheline）
→ 读数据
→ spin_unlock_read(&rwlock) // CAS 递减引用计数（再写 cacheline）
- 每次读都要写共享内存：引用计数 CAS 导致多核缓存行失效（cache line bouncing）
- 读写互斥：写者必须等所有读者退出，读者必须等写者释放
- 高读频率下锁竞争严重：路由表每秒数百万次查询，rwlock 成为瓶颈
RCU 的目标
让读者完全无锁（仅禁止抢占，不写任何共享内存），写者通过三步实现安全更新：
- Copy：复制一份旧数据的新版本并修改
- Update（原子替换指针）：用 memory barrier + 原子赋值让新读者看到新版本
- 等待旧读者全部完成（Grace Period）后安全释放旧版本
使用 RCU 的典型系统
- Linux 内核：路由表（FIB）、模块列表、网络过滤规则、任务列表
- QEMU、KVM：设备热插拔
- 用户态：liburcu（userspace RCU 库）
核心数据结构
// 被 RCU 保护的节点（以链表节点为例）
struct Node:
key : int
value : int
next : *Node // 指向下一个节点（RCU 保护的指针）
rcu_head: rcu_head // 用于延迟释放的回调钩子
// RCU 回调头（嵌入被保护对象）
struct rcu_head:
next : *rcu_head // 回调链表指针
func : (*rcu_head) -> void // 释放函数，synchronize_rcu 后由 RCU 子系统调用
// 全局受保护指针（volatile/atomic，确保编译器不缓存）
global gp : *Node // 指向链表头，读者通过 rcu_dereference(gp) 访问
// 每 CPU 状态（Linux 内核实现）
struct rcu_data[NR_CPUS]:
qs_mask : bitmask // 该 CPU 是否已经历过 quiescent state
nesting : int // rcu_read_lock 嵌套计数（> 0 表示在读临界区内）
// RCU 全局状态
struct rcu_state:
completed : long // 已完成的 grace period 编号
gpnum : long // 当前正在进行的 grace period 编号
qsmask : bitmask // 还未报告 quiescent state 的 CPU 集合
图示
三个核心操作
3.1 rcu_read_lock / rcu_read_unlock
// 读临界区开始：禁止抢占（不写任何共享内存！）
procedure rcu_read_lock():
preempt_disable() // 关闭当前 CPU 的抢占
// 注意：不递增任何引用计数，不获取任何锁
// 仅保证：在 rcu_read_unlock 之前，当前 CPU 不会被调度出去
// 读临界区结束：允许抢占
procedure rcu_read_unlock():
preempt_enable() // 开启当前 CPU 的抢占
// CPU 在此处可能发生调度（quiescent state）
为什么禁止抢占就足够？
- Linux 内核中，Grace Period 的判断依据是"每个 CPU 都经历过一次调度（上下文切换）"
- 禁止抢占 = 保证读临界区不会被切换出去 = 读者持有旧指针期间不会经历 quiescent state
- 一旦 rcu_read_unlock 后该 CPU 发生调度，RCU 子系统即认为该 CPU 的旧读者已全部完成
3.2 rcu_assign_pointer（写者使用）
// 原子替换全局指针，带写内存屏障
procedure rcu_assign_pointer(p: **Node, new_val: *Node):
smp_wmb() // 写内存屏障：确保 new_val 指向的新节点内容
// 对其他 CPU 可见，早于指针本身的更新
WRITE_ONCE(*p, new_val)
// 原子写入指针（在 x86 上天然原子，ARM 需要 stlr 指令）
// 之后：新读者通过 rcu_dereference 能看到完整的新节点内容
3.3 rcu_dereference（读者使用）
// 安全解引用 RCU 保护的指针，带读内存屏障
function rcu_dereference(p: **Node) -> *Node:
val = READ_ONCE(*p) // 原子读取指针（防止编译器将指针读取拆分或重排）
smp_read_barrier_depends()
// 数据依赖屏障：确保后续对 val->field 的读取
// 不会被重排到指针读取之前（Alpha 架构需要，x86/ARM 天然满足）
return val
// 返回值只在 rcu_read_lock/unlock 之间使用才安全！
Grace Period：synchronize_rcu
核心思想：等待系统中每个 CPU 都经历至少一次 quiescent state（调度/上下文切换），此后可以确定没有任何读者还持有旧指针。
// 写者调用：阻塞直到所有旧读者完成
procedure synchronize_rcu():
gpnum = rcu_state.gpnum + 1
rcu_state.gpnum = gpnum
rcu_state.qsmask = ALL_CPUS_BITMASK // 标记所有 CPU 需要报告
// 等待每个 CPU 经历一次 quiescent state
for each cpu in ALL_CPUS:
wait_for_quiescent_state(cpu) // 见下方伪代码
rcu_state.completed = gpnum
// 现在安全：所有旧读者已退出临界区，可以释放旧版本
// 每个 CPU 报告 quiescent state 的时机
procedure cpu_schedule_out(cpu): // 在上下文切换时由调度器调用
if rcu_data[cpu].nesting == 0: // 该 CPU 不在 RCU 读临界区内
rcu_state.qsmask.clear(cpu) // 报告：此 CPU 已经历 quiescent state
if rcu_state.qsmask == 0: // 所有 CPU 都报告完毕
wake_up(synchronize_rcu_waitq) // 唤醒等待中的 synchronize_rcu
// 异步版本（不阻塞写者）
procedure call_rcu(head: *rcu_head, func: callback):
head.func = func
enqueue(rcu_callback_list, head) // 加入回调队列
// Grace Period 结束后由 RCU 守护线程（kthread）调用 func(head)
// 通常 func 实现为：kfree(container_of(head, Node, rcu_head))
单链表删除节点完整示例
场景：链表 A → B → C，删除节点 B，读者可能正在读 B 或通过 B 访问 C。
// ========== 数据结构 ==========
struct Node:
key : int
value : int
next : *Node
rcu_head: rcu_head
global head : *Node = &A // 链表头，RCU 保护
// ========== 路径 1：读者访问链表 ==========
procedure reader_traverse():
rcu_read_lock() // 禁止抢占
cur = rcu_dereference(&head) // 安全读取头指针
while cur != NULL:
key = cur.key // 读取字段（cur 在临界区内有效）
val = cur.value
process(key, val)
cur = rcu_dereference(&cur.next) // 安全读取 next 指针
rcu_read_unlock() // 允许抢占，退出临界区
// ========== 路径 2：写者删除节点 B ==========
procedure writer_delete(target_key: int):
spin_lock(&write_lock) // 写者间互斥（多写者场景）
// Step 1：找到 B 的前驱节点 A
prev = &head
cur = head
while cur != NULL and cur.key != target_key:
prev = &cur.next
cur = cur.next
if cur == NULL:
spin_unlock(&write_lock)
return // 未找到目标节点
// Step 2：Copy + Update（绕过 B，将 A.next 指向 C）
// 注意：不需要复制 B 的新版本，直接修改 A.next 即可
rcu_assign_pointer(prev, cur.next)
// 此后：新读者从 A 遍历时看不到 B（直接跳到 C）
// 旧读者：可能还持有 cur（即 B 的指针），继续读 B 或 B.next（均安全）
spin_unlock(&write_lock)
// Step 3：等待所有旧读者完成
synchronize_rcu() // 阻塞，直到 Grace Period 结束
// 此时确保：没有任何读者还在访问 B
// Step 4：释放旧节点 B
free(cur) // 安全释放
// ========== 路径 2（异步版）：写者用 call_rcu 不阻塞 ==========
procedure free_node_callback(head: *rcu_head):
node = container_of(head, Node, rcu_head)
free(node) // Grace Period 结束后由 RCU 守护线程调用
procedure writer_delete_async(target_key: int):
spin_lock(&write_lock)
prev = &head
cur = head
while cur != NULL and cur.key != target_key:
prev = &cur.next
cur = cur.next
if cur == NULL:
spin_unlock(&write_lock)
return
rcu_assign_pointer(prev, cur.next) // 原子摘除 B
spin_unlock(&write_lock)
call_rcu(&cur.rcu_head, free_node_callback)
// 写者立即返回，不阻塞；释放由 RCU 守护线程异步完成
// ========== 路径 3：写者修改节点值（需要 Copy） ==========
procedure writer_update(target_key: int, new_value: int):
spin_lock(&write_lock)
cur = head
while cur != NULL and cur.key != target_key:
cur = cur.next
if cur == NULL:
spin_unlock(&write_lock)
return
// Step 1：Copy —— 分配新节点，复制旧内容
new_node = alloc(Node)
*new_node = *cur // 复制所有字段
new_node.value = new_value // 修改目标字段
// Step 2：Update —— 原子替换指针
// 找到指向 cur 的指针位置（prev.next 或 head）
rcu_assign_pointer(prev_ptr, new_node)
// 此后：新读者看到 new_node，旧读者继续访问 cur（旧节点）
spin_unlock(&write_lock)
// Step 3：等 Grace Period，释放旧节点
synchronize_rcu()
free(cur)
执行追踪
场景：链表 A(1) → B(2) → C(3)，Writer 删除 B，两个并发 Reader。
时间线（横轴为时间，纵轴为执行体）
T=0 T=1 T=2 T=3 T=4 T=5
│ │ │ │ │ │
Reader1:
rcu_read_lock()
cur = &A(1) // 读到头指针
process(A.key=1)
cur = &B(2) // 读到 B（旧版本）
process(B.key=2)
// 此时 Writer 已摘除 B，但 Reader1 仍持有 B 的指针
// B 的内存仍然有效（synchronize_rcu 尚未完成）
cur = &C(3) // 通过 B.next 读到 C（B.next 未被修改，仍指向 C）
process(C.key=3)
cur = NULL
rcu_read_unlock() // 退出临界区，允许抢占
// CPU0 发生调度 → 报告 quiescent state
Writer:
spin_lock(&write_lock)
// 找到 B，prev = &A.next，cur = &B
rcu_assign_pointer(&A.next, &C)
// A.next 现在指向 C，B 已从链表摘除
spin_unlock(&write_lock)
synchronize_rcu() // 开始等待 Grace Period
// 等待 Reader1 退出（Reader1 还在读 B）
// 等待 Reader2 退出
// Reader1 已退出 + CPU0 调度
// Reader2 已退出 + CPU1 调度
// 所有 CPU 报告 quiescent state
// synchronize_rcu 返回
free(&B) // 安全释放
Reader2（在 Writer 完成 rcu_assign_pointer 之后启动）:
rcu_read_lock()
cur = &A(1)
process(A.key=1)
cur = rcu_dereference(&A.next)
// 读到 &C（新版本，B 已被摘除）
process(C.key=3)
cur = NULL
rcu_read_unlock()
内存状态变化：
T=0: head→A→B→C （A.next=&B，B.next=&C）
T=2: head→A→C （A.next=&C，B 仍在内存但不在链表中）
Reader1 仍持有 &B，B.next=&C 仍有效
T=5: head→A→C，B 已释放
关键观察：
- Reader1 读到的是 B 的旧版本，完全合法（RCU 的语义是"快照一致性"，不是强一致）
- Writer 替换指针后立即对新 Reader 可见，无需等待 Reader1
- B 的内存在 synchronize_rcu 返回之前绝对不会被释放，Reader1 访问 B 永远安全
与读写锁对比
| 维度 | RCU | rwlock（读写自旋锁） |
|---|---|---|
| 读侧开销 | 仅 preempt_disable（无共享内存写） | CAS 递增/递减引用计数（写 cacheline） |
| 读写并发 | 读写可完全并发 | 有写者时读者必须等待 |
| 写侧开销 | 需要复制新版本 + 等待 Grace Period | 仅需等待所有读者退出 |
| 内存开销 | 新旧两个版本同时存在（Grace Period 内） | 单一版本 |
| 读一致性 | 快照一致性（读者可能看到旧版本） | 强一致（读者一定看到最新版本） |
| 写吞吐 | 低（每次写要等 Grace Period） | 中（短暂的读写互斥） |
| 适用场景 | 读极多、写极少、可容忍旧读 | 读多写少、需要强一致读 |
| 多核扩展性 | 极好（读侧无 cacheline 竞争） | 受限（引用计数 cacheline 争用） |
// 读侧开销对比（伪汇编）
// rwlock 读锁：
LOCK XADD [rwlock], 1 // 原子加（写共享 cacheline → 触发所有核的缓存失效）
... 读操作 ...
LOCK XADD [rwlock], -1 // 原子减
// RCU 读锁（x86）：
CLI / 设置 preempt_count++ // 本地操作，不写共享内存
... 读操作 ...
preempt_count-- // 本地操作
// 零共享内存写，零缓存失效
异常与边界场景
场景 1：写者更新期间多个读者并发
问题：多个读者同时在临界区，Writer 能否立即替换指针？
分析：
Reader1: rcu_read_lock → 读 A → 读 B → ...（还未退出）
Reader2: rcu_read_lock → 读 A → ...（还未退出）
Writer: rcu_assign_pointer(&A.next, &C) ← 可以立即执行！
结论：Writer 不需要等待任何读者。替换指针后：
- 新启动的 Reader3 看到新版本（A→C）
- Reader1/Reader2 继续读旧版本（持有 &B，B 内存仍有效）
- synchronize_rcu 等待 Reader1 和 Reader2 都退出后才释放 B
正确性保证：
- B 的内存在 synchronize_rcu 返回前不会被释放
- B.next 未被修改，Reader1 通过 B 仍能正确访问 C
- 无数据竞争（写者只修改 A.next，读者只读 B.next）
场景 2：Grace Period 超长（大量长时间读者）
问题：如果系统有大量长时间持有读临界区的读者，会发生什么？
场景：
Writer 调用 synchronize_rcu()
CPU0 上的 Reader 持续读取（rcu_read_lock 后执行大量计算，数秒未 unlock）
后果：
- synchronize_rcu 被阻塞数秒，写者无法完成
- 旧版本节点积压（多次写入导致多个待释放节点排队）
- 如果使用 call_rcu，回调队列积压，内存无法及时回收
缓解方案：
- 规范：RCU 读临界区应当极短（仅做指针解引用 + 简单读取）
- 严禁：在 rcu_read_lock/unlock 之间调用阻塞操作（sleep/mutex/IO）
- 监控：Linux 内核 /sys/kernel/debug/rcu/rcu_sched/rcudata 可查看积压情况
- RCU-preempt 变体：允许抢占但通过额外计数追踪，适合实时内核（CONFIG_PREEMPT_RCU）
场景 3：嵌套 rcu_read_lock
问题：rcu_read_lock 可以嵌套吗？
procedure nested_reader():
rcu_read_lock() // 第 1 层：preempt_count = 1
ptr1 = rcu_dereference(&gp1)
process(ptr1)
rcu_read_lock() // 第 2 层：preempt_count = 2（完全合法）
ptr2 = rcu_dereference(&gp2)
process(ptr2)
rcu_read_unlock() // preempt_count = 1（仍在第 1 层临界区）
rcu_read_unlock() // preempt_count = 0（完全退出）
结论：嵌套完全合法。preempt_count 是累加的，只有归零时才真正允许抢占。
注意：每个 rcu_read_lock 必须对应一个 rcu_read_unlock，否则 preempt_count 永不归零
→ 该 CPU 永远不会经历 quiescent state → synchronize_rcu 永久阻塞（死锁等价）
场景 4：用户态 RCU（liburcu）
问题：用户态没有 preempt_disable，如何实现 RCU？
liburcu 的实现方案（QSBR 变体）：
// 每个线程维护本地状态
struct urcu_tls:
ctr : unsigned long // 本地计数器，奇数=在临界区，偶数=在临界区外
procedure urcu_read_lock():
WRITE_ONCE(urcu_tls.ctr, global_ctr | 1) // 标记进入临界区
smp_mb() // 内存屏障
procedure urcu_read_unlock():
smp_mb()
WRITE_ONCE(urcu_tls.ctr, 0) // 标记退出临界区
procedure synchronize_rcu():
// 发布新 global_ctr（偶数值）
new_ctr = (global_ctr + 2) & ~1
WRITE_ONCE(global_ctr, new_ctr)
smp_mb()
// 等待每个线程的本地 ctr 与 global_ctr 同步（即线程经历过一次进出临界区）
for each thread t:
while urcu_tls[t].ctr & 1 and urcu_tls[t].ctr != new_ctr:
sched_yield() // 让出 CPU，等待线程完成临界区
特点：用户态轮询代替内核调度感知，Grace Period 依赖线程主动调用 urcu_quiescent_state()
场景 5：写者并发（多写者场景）
问题：两个写者同时尝试删除不同节点
Writer1: 删除节点 B（A→B→C→D，目标删 B）
Writer2: 删除节点 C（目标删 C）
如果无写者间同步：
Writer1: prev=&A.next, cur=&B, 读 cur.next=&C
Writer2: prev=&B.next, cur=&C, 读 cur.next=&D
Writer1: rcu_assign_pointer(&A.next, &C) // A.next → C
Writer2: rcu_assign_pointer(&B.next, &D) // B.next → D（但 B 已被摘除！）
结果：链表变成 A→C→D，C 被错误地留在链表中
解决方案：写者间必须用 spin_lock(&write_lock) 互斥
写者并发仅限"同时存在多个写者"，实际每次只有一个写者持锁修改链表结构
RCU 解决的是"读写并发"，不解决"写写并发"
适用场景
适合使用 RCU 的场景
| 场景 | 原因 |
|---|---|
| Linux 路由表（FIB）查询 | 每秒数百万次查询，路由更新极少 |
| 内核模块列表 | 模块加载/卸载极少，遍历频繁 |
| 网络过滤规则（iptables/nftables） | 规则变更少，每个数据包都要匹配 |
| 读多写极少的配置表 | 配置变更低频，读取高频 |
| 引用计数替代（对象生命周期管理） | 避免引用计数的原子操作开销 |
不适合使用 RCU 的场景
| 场景 | 原因 |
|---|---|
| 写频繁的数据结构 | 大量旧版本积压，内存占用高；Grace Period 频繁等待 |
| 需要强一致性读 | RCU 允许读者看到旧版本，不适合需要"立即看到最新值"的场景 |
| 读临界区较长 | 导致 Grace Period 超长，写者阻塞 |
| 实时性要求极高的写路径 | synchronize_rcu 可能阻塞毫秒级（但 call_rcu 可绕过） |
| 简单标量值的并发更新 | 用 atomic_t 或 seqlock 更合适 |
参考资料
- Paul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It?
- Linux Kernel Documentation:
Documentation/RCU/（whatisRCU.rst、Design/） - Paul E. McKenney, "RCU Usage In the Linux Kernel: One Decade Later", Linux Symposium 2013
- Mathieu Desnoyers et al., "User-Level Implementations of Read-Copy Update", IEEE Trans. Parallel Distrib. Syst., 2012
- Linux source:
kernel/rcu/tree.c、include/linux/rcupdate.h - liburcu 源码：https://github.com/urcu/userspace-rcu
评论 (0)
发表评论