6.1810 2024 L22: 多核可扩展性与 RCU

今日主题:

• 针对读密集型共享数据的多核内核性能。
• RCU (Read-Copy Update): 在 Linux 中非常成功。

难题:

• 在多核上，并行执行对性能至关重要。
• 内核具有大量自然的并行性。
  • 不同进程的系统调用在高级别上通常是独立的。
  • Fork、在缓存中读/写不同文件、管道、套接字等。
• 但内核的共享资源常常阻碍并行性。
  • 例如内存分配器、调度器、磁盘缓存、i-node 缓存等。
  • 通常的症状是 CPU 时间浪费在 acquire() 的自旋上。
• 在生产内核中为消除并行瓶颈付出了巨大努力。
• 许多设计模式，针对不同类型的情况量身定制。

今天的重点：读密集型内核数据结构。

示例：单向链表。

• 例如进程列表；缓存块列表等。
• 指向第一个元素的全局变量。
• 每个元素都有数据，例如嵌入的字符串和下一个指针。
• 假设大多数用途是扫描列表的读取。
• 偶尔有写入者添加元素；删除元素；更改元素中的字符串。

xv6 会要求列表的读者和写者获取一个自旋锁。

• 安全，但即使所有线程都是只读的，也没有并行性。
• 我们可以有一个允许并行读取的锁吗？
• 读写锁怎么样？

读写锁 API。

• 读者调用 r_lock(l) / r_unlock(l)
• 写者调用 w_lock(l) / w_unlock(l)
• 语义： 要么
  • 一个写者，但没有读者或其他写者；或者
  • 大量读者，但没有写者。

这是一个简化版的 Linux 读写锁。

struct rwlock { int n; };
  n=0  -> 未锁定
  n=-1 -> 被一个写者锁定
  n>0  -> 被 n 个读者锁定
r_lock(l):
  while 1:
    x = l->n
    if x < 0
      continue
    if CAS(&l->n, x, x + 1)
      return

CAS(p, a, b) 是原子比较并交换指令 if *p == a { *p = b; return true } else return false

w_lock(l):
  while 1:
    if CAS(&l->n, 0, -1)
      return

意外： 如果在许多核心上大量调用 r_lock()，它会非常慢：

• 即使没有写者！
• [图：总线、RAM、核心、缓存]
• N 个核心上的线程调用 r_lock(l)；没有写者。
• 所有 N 个核心都获取 l->n，看到 l->n == 0，执行 CAS(&n, 0, 1)。
• 只有一个 CAS 成功。
• 其余的失败，必须重新执行。
• 但原子 CAS 是一个接一个执行的 —— 不是并行的。
• 因此，一个 CPU 获取读锁需要 O(N) 时间。
• 其他 N-1 个核心都重试读取和 CAS；同样，只有一个成功。
• 因此，所有 N 个核心获取共享读锁的总时间为 O(N^2)。 令人失望：
• 列表读取本身可能只有几十个周期，如果已缓存。
  • 即使有很多核心在读取。
• 但如果 r_lock() 很受欢迎，它可能需要数百或数千个周期。
• 更多的核心 -> 更低的性能。

r_lock() 的根本问题是：它执行了昂贵的写操作。

我们能否对共享的读写数据进行纯只读的读取？

• 即，甚至避免锁定所需的写操作？
• (不过我们假设写者仍然会锁定。)

如果读者在没有锁定的情况下读取列表会出什么问题？

• [列表图，每个条目中都有字符串]
• 如果没有写者，不会出问题。
• 如果有并发的写者？
  1. 修改列表元素中的字符串？
  2. 插入一个新的列表元素？
  3. 删除一个元素？

所以读者简单地不加锁是行不通的。

• 但具体问题可以解决！
• 这就是 RCU 所做的。

读-复制-更新 (Read-Copy Update, RCU)。

• 快速读取： 读者不加锁（因此不写入）。
• 较慢的写入： 写者必须加锁，并做额外的工作来帮助读取。
• 对许多具有读密集型共享数据的情况有帮助（但不是全部）。
• 在 Linux 内核中广泛使用。

RCU 是一套针对读者和写者的规则和模式。

• 加上一些机制。

RCU 思想 1：写者不就地修改数据；而是准备一个新副本。Head -> E1 -> E2 -> E3 -> nil

• 假设写者想更改 E2 中的字符串。
  1. 加锁
  2. e = alloc()
  3. e->next = E2->next
  4. strcpy(e->x, "xxx");
  5. E1->next = e
  6. 解锁
• 另一个核心上的读者遍历列表会怎么样？
  • 读者会在某个时刻读取 E1->next。
  • 要么在第 5 步之前，要么在之后（这是一个简化，见下文）。
  • 如果在之前，读者看到旧的 E2 和旧的字符串。
  • 如果在之后，读者看到新的元素和新的字符串。
  • 无论哪种方式，读者都会看到 ...->next 指向 E3。
• 重点： 读者不会看到部分更新的字符串。
  • 即使读者没有加锁。

一个很好的思考这个想法的方式：

• E1->next 的更新是一个“提交写入”。
• 在此之前，读者看不到任何变化。
• 在此之后，所有变化都变得可见。
• 这避免了读者看到部分完成的更新的问题。
• RCU 最适合于单个指针写入即可提交的数据结构。
  • 例如列表和树。

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

• 即，读者不会在 E1->next 指针中看到新旧位的混合。
• 这在我所知的所有 64 位 CPU 上都是如此。
  • 对于对齐的加载/存储。

RCU 思想 2：读者和写者必须使用内存屏障来强制顺序。

• 我们不希望编译器或机器将第 3 步或第 4 步移到第 5 步之后。
• 写者必须在第 5 步之前有一个屏障。
• 读者在 Rx = E1->next 和解引用 Rx 读取元素内容之间可能需要一个屏障。

下一个问题：当写者 free() 一个已删除的列表元素时会发生什么？

• 移除可见引用可以阻止新的读者，但是
• 一个并发的读者可能仍在查看已删除的元素！
• 释放后使用 (Use-after-free) 是一个潜在的灾难：
  • 可能会被重新分配并覆盖用于其他用途。
• 写者需要给读者时间来完成 —— 一个“宽限期”。
  • 在它移除对元素的可见引用之后。
• 写者应该等待多久？
• 可以使用 GC 或引用计数，但它们很昂贵。

RCU 思想 3 (宽限期):

1. 规则： 读者不能在上下文切换期间持有指向 RCU 数据的指针。
   • 程序员负责遵守此规则。
2. 写者延迟释放，直到所有 CPU 都进行了上下文切换。

• 写者必须等待，
  • 但假设是写入很少见。
• 如何实现这种延迟？
  • 每个核心计算上下文切换次数，写者观察计数。
  • synchronize_rcu()
  • (实现宽限期的方法有很多。)

Linux RCU 读者的接口：

• rcu_read_lock()
• rcu_read_unlock()
• rcu_dereference(p)对于写者：
• synchronize_rcu()
• call_rcu(fn,x)
• rcu_assign_pointer(pa, p)

使用 Linux RCU 接口的列表读者：

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

rcu_read_lock/unlock 几乎什么都不做。

• 尽管它们的名字里有“锁”，但它们不加锁。
• 禁用计时器中断以防止抢占。
  • 因为上下文切换意味着 RCU 对象处理完毕。
• 作为文档。

注意： 代码只允许在 rcu_read_lock/unlock 内部使用 e！

• 它不能例如 return(e)
• 并且在持有 e 的同时不允许进行上下文切换。

rcu_dereference(e) 做什么？

• 告诉编译器只计算一次指针。
  • 而不是例如在第一次迭代中用 head 替换 e。
• 然后是一个屏障，以确保读取的 CPU 看到写入。

写者替换第一个列表元素的代码：

acquire(lock)
e = alloc()
e->x = ...
e->next = head->next
old = head
rcu_assign_pointer(&head, e)
release(lock)

synchronize_rcu()
free(old)

synchronize_rcu() 做什么？

• 实现宽限期：延迟直到所有 CPU 都进行了上下文切换
• 可能需要很长时间，并且可以放弃 CPU。
• 替代方案：call_rcu(free,old)
  • 将 <free,old> 添加到一个列表中。
  • 立即返回

rcu_assign_pointer(p, val) 做什么？

• 内存栅栏
• *p = val

RCU 性能与读/写锁相比？

• 对于读者：
  • RCU 对读取几乎没有成本。
  • 读/写锁可能需要数百或数千个周期（图 8，上线）。
  • 此外，RCU 可以在写入进行时读取！
  • 此外，RCU 读取不易发生死锁！
• 对于写者：
  • 由于 synchronize_rcu()，RCU 可能需要更长的时间。
  • 因此，当写入很少或对时间不敏感时，RCU 是有意义的。

示例：移除 NMI 处理程序；论文第 4.1 节；图 4。

• NMI 是不可屏蔽的中断。
  • 用于 CPU 分析、关键硬件错误、看门狗计时器。
• 内核代码可以注册在 NMI 期间调用的处理程序。
• 也可以注销处理程序，并释放包含处理程序代码的内存。
• NMI 频繁；注册/注销很少见；因此读取 >> 写入。
• 如果在调用注销时某个核心正在 NMI 代码中怎么办？
• 图 4 在 unregister_nmi_handler() 中的解决方案：
  1. 删除 NMI 处理程序列表条目（因此未来的中断不会看到它）。
  2. synchronize_rcu() 等待所有当前中断完成。
     • 因为一个核心在离开中断之前不会进行上下文切换。
  3. (未显示) 释放持有 NMI 处理程序代码的内存。
• 这个例子使用 RCU 来延迟释放，直到所有使用都完成。
• 一个有趣的转折：
  • NMI 不能被禁用。
  • 所以自旋锁不能阻止 NMI。
  • 所以通常不允许 NMI 获取锁（死锁...）。
  • 所以在这里，RCU 不仅比读者的锁更快，
    • 而且在锁无法工作的地方实际有效。

示例：IP 选项；第 4.2 节；图 6。

• IP 数据包头部可以包含选项（例如记录路由）。
• 内核套接字有（可选的）选项，复制到每个传出的数据包中。
• 发送代码 (udp_sendmsg()) 无锁复制套接字选项。
• 选项的读取比写入频繁得多 -> 很好的 RCU 候选者。
• setsockopt() 使用 call_rcu(kfree,old) 延迟释放被取代的选项。
• 为什么读取代码是安全的？
  1. 写者在发布指针之前完全准备好新选项。
  2. 写者和读者使用内存屏障。
  3. 写者延迟释放，直到任何旧的读者都必须完成。
• 论文称之为“引用计数”，但没有引用计数。
  • “延迟释放”或“垃圾回收”可能是更好的术语。

RCU 并非普遍适用。

• 对写入没有帮助。
• 仅在读取 >> 写入时提高性能。
• 不适用于必须在 yield/sleep 期间持有引用的代码（但可以修复）。
• 如果数据结构不适合单个提交指针写入，则难以应用。
  • 例如，如果读者双向扫描双向链表。
  • 或者如果需要就地更新。
• 读者可能会看到过时的数据。
  • 例如，图 6 中的 udp_sendmsg() 可能会使用旧的 IP 选项发送。
  • 在这里不是问题；在少数情况下可能是（例如数据库事务）。
• RCU 给写者增加了复杂性。
  • 在网上搜索“RCU 补丁的审查清单”
• RCU 需要上下文切换频繁，并且需要了解它们。
  • 在内核中很容易，但用户空间不知道核心切换。

如何高效地实现 synchronize_rcu()？

• 这是 McKenney 和 Slingwine 的一篇论文中的一个设计
  • http://www2.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf
  • 第 3.5.4 节
• 每个核心的数据：
  • 此核心的上下文切换计数。
  • 等待 synchronize_rcu() 和 call_rcu() 的列表。
• 周期性地，每个核心处理一批（列表）RCU 写者：
  • 保存列表，清空它。
  • 记录所有其他核心的计数。
  • 每次上下文切换，再次查看其他核心的计数。
  • 如果所有都已更改，则唤醒/运行保存列表上的所有内容。

如果你有共享的写密集型数据怎么办？

• 最佳： 重新设计为无共享。
• 次佳： 以某种方式对数据进行分区，并按分区加锁。
  • 示例：锁实验中的 kalloc —— 按核心分区。
  • 示例：统计计数器。
    • 每个核心在单独的自旋锁下保持自己的计数。
    • 要写入，获取本地锁，增加本地计数。
      • 如果只从一个核心使用，自旋锁很便宜。
    • 要读取，获取所有锁，读取并求和所有计数。
      • 昂贵，但我们假设是写密集型的。

RCU 总结

• 在加速对共享内核数据的读取访问方面非常成功。
  • 在现代 Linux 中随处可见。
• 完全消除了读者的锁定成本。
• 允许读者与写者并行执行。
• 关键思想是类似 GC 的宽限期，以延迟释放对象。

考试在下周四！

• 涵盖论文、讲座、实验。

---

RCU 规则: https://www.kernel.org/doc/Documentation/RCU/checklist.txt RCU 实现: http://www2.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf 无锁模式: https://lwn.net/Articles/850202/ 使用 KCSAN 检测缺失的内存屏障: https://lwn.net/Articles/877200/