MIT 6.1810 · 第 20 课 · rtm

多核扩展性与 RCU

多核时代，内核性能的关键在于减少共享数据的竞争。RCU（Read-Copy Update）是 Linux 内核中广泛使用的无锁读取技术。

背景：摩尔定律的终结

谜题

• 内核有很多自然并行性——不同进程的系统调用通常是独立的
• 但内核的共享资源常常阻碍并行性
  • 内存分配器、调度器、磁盘缓存、inode 缓存等
  • 症状：CPU 时间浪费在 acquire() 的自旋上

示例：单向链表

// 典型内核数据结构
struct list {
  struct elem *head;
};

struct elem {
  int n;
  int refcnt;
  struct elem *next;
};

// 大多数使用是读取（扫描链表）
// 偶尔写入（添加元素、删除元素、修改元素）

读写锁 (Read-Write Lock)

// API
void rwlock_r_acquire(l);   // 读锁获取
void rwlock_r_release(l);   // 读锁释放
void rwlock_w_lock(l);      // 写锁获取
void rwlock_w_unlock(l);    // 写锁释放

// 语义：要么一个写者（无读者），要么多个读者（无写者）

实现

// rwlk->n 计数读者数
// CAS 原子更新 rwlk->n 为 n+1
// 如果 0x80000000 被设置，rwlk->n 计数写者

惊喜：读写锁很慢！

性能数据

// 4 核，rwlock
ncore 4 ltype rwlock
  10000000 list_search took 2.86s
  10000000 list_search took 2.89s
  10000000 list_search took 3.35s
  10000000 list_search took 3.36s

// 4 核，spinlock
ncore 4 ltype spinlock
  10000000 list_search took 1.02s
  10000000 list_search took 3.22s
  10000000 list_search took 3.27s
  10000000 list_search took 3.29s

// 即使没有写者，rwlock 也更慢！

时间花在哪里？

$ perf record -g ./clist 4 1
$ perf report
   59.26%  rwlock_r_acquire
   33.48%  rwlock_r_release
    5.40%  run_core
    3.01%  list_search

两个效应

N 个核心调用 r_acquire(l)，没有写者
所有 N 个核心获取 rwlk->n，看到 rwlk->n == 0
执行 atomic_compare_exchange
只有一个 CAS 成功，其余失败并重试
atomic compare_exchange 一次执行一个——不并行
因此一个 CPU 获取读锁需要 O(N) 时间
所有 N 个核心的总时间 = O(N²)

核心问题

Read-Copy Update (RCU)

性能预览

ncore 4 ltype rcu
  10000000 list_search took 0.09s
  10000000 list_search took 0.09s
  10000000 list_search took 0.09s
  10000000 list_search took 0.10s

比 rwlock 快 30 倍以上！

RCU 是一组规则和模式

• 快速读取：读者不加锁（因此不写入）
• 较慢写入：写者必须加锁，并做额外工作帮助读取
• 帮助许多读重于写的情况（但不是全部）
• 在 Linux 内核中广泛使用

RCU 思想 1：写者不原地修改数据，而是准备新副本

Head  ->  E1  ->  E2  ->  E3  ->  nil

// 假设写者想修改 E1 的 n 和 refcnt
1. 加锁
2. e = alloc()
3. e->next = E1->next
4. e->n = 10
5. e->refcnt = 1
6. E1->next = e    // "提交写入"
7. 解锁

RCU 最佳适用场景

RCU 最适合单次指针写入提交的数据结构，例如链表和树。

要求 64 位写入和读取是原子的

读者不会看到 E1->next 指针的旧位和新位的混合。这对所有已知的 64 位 CPU 的对齐加载/存储都成立。

RCU 思想 2：读者和写者必须使用内存屏障

// 写者必须在步骤 6 之前有屏障
// 读者可能需要在 Rx = E1->next 和 Rx 的解引用之间有屏障
// rcu_dereference() 确保这一点

RCU 思想 3：宽限期 (Grace Period)

宽限期规则

1. 规则：读者不能在上下文切换期间持有指向 RCU 数据的指针
2. 写者：延迟 free 直到所有 CPU 都已上下文切换

写者必须等待，但假设写入很少。

Linux RCU 接口

读者接口

rcu_read_lock()
rcu_read_unlock()
rcu_dereference(p)

写者接口

synchronize_rcu()          // 等待宽限期
call_rcu(fn, x)             // 延迟执行 fn(x)
rcu_assign_pointer(pa, p)   // 带屏障的指针赋值

使用 RCU 的链表读者

rcu_read_lock()
e = rcu_dereference(head)
while(e){
    查看 e->n, e->refcnt, ...
    e = rcu_dereference(e->next)
}
rcu_read_unlock()

写者替换第一个链表元素

acquire(lock)
e = alloc()
e->n = ...
e->next = head->next
old = head
rcu_assign_pointer(&head, e)  // 提交写入
release(lock)

synchronize_rcu()             // 等待宽限期
free(old)                     // 现在可以安全释放

各函数的作用

RCU vs 读写锁性能对比

RCU 示例

示例 1：移除 NMI 处理程序

示例 2：IP 选项

IP 数据包头部可以包含选项。发送代码（udp_sendmsg()）不加锁地复制套接字选项。选项读取远多于写入 → 好的 RCU 候选。

RCU 的局限性

• 不帮助写入
• 只在读取 >> 写入时提高性能
• 不适用于必须在 yield/sleep 期间持有引用的代码
• 如果数据结构不适合单次提交写入则难以应用
• 读者可能看到过时数据
• 给写者增加复杂性
• 需要上下文切换频繁，且需要知道它们

共享写入密集型数据怎么办？

要点总结

测验

延伸阅读

• RCU 规则清单
• RCU 实现论文
• 无锁模式