文章

linux内核笔记【译】RCU（一）从根本上讲,什么是RCU

发表于
Preview Image
作者 Symbol Who
32 分钟阅读
linux内核笔记【译】RCU（一）从根本上讲,什么是RCU

引言

Read-Copy Update（RCU）是一种同步机制，2002年10月添加到 Linu 内核中。RCU 通过允许读取与更新同时发生来实现可扩展性的提高。相比于传统的锁函数(传统锁函数使并发线程之间互斥，无论它们是 reader 还是 updater ),或读写锁(允许并发读但不能更新)，RCU 支持单个 updater 和多个 reader 之间的并发。 RCU 通过维护多个版本的对象并确保在所有 reader 端的读取临界区完成之前都不会释放对应版本的对象来确保读取是连贯的。 RCU 定义并使用高效且可扩展的机制来发布和读取对象的新版本，并用于推迟旧版本的内存回收。这些机制在 read 和 update 的方式之间工作使 read 的性能非常高。在某些情况下（不可抢占内核），RCU 的读取函数的开销为零。

原文：What is RCU, Fundamentally?

疑问1: 但 seqlock 不也允许 reader 与 updater 的并发吗?

这提到了一个问题 RCU 到底是什么？，也许还有 RCU 如何工作? 的问题。（经常有人提出RCU无法正常工作）。本文档从基本原理的角度解释了这些问题；后面分别从使用和API层面。最后一部分还包括参考列表。

RCU由三种基本机制组成

  1. 发布-订阅机制 (新增数据)
  2. 等待 RCU Reader 完成 (删除数据)
  3. 维护最近更新对象的多个版本 (读取数据)

这些部分之后是结论和疑问的答案。

发布-订阅机制

RCU 的一个关键特性是可以安全的扫描数据，即使该数据正在并发被修改。RCU 通过一套精巧的发布-订阅机制，同时保证了 reader 的安全和 updater 的并发。

例如: 有一个初始化为 NULL 的全局指针 gp 将要被修改为指向一个新分配的有初始数据结构的内存地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct foo {
  int a;
  int b;
  int c;
};
struct foo *gp = NULL;

/* . . . */

p = kmalloc(sizeof(*p), GFP_KERNEL);
p->a = 1;
p->b = 2;
p->c = 3;
gp = p;

不幸的是，编译器和 CPU 并不会按顺序执行最后四个分配语句。如果对 gp 的分配发生在 p 字段初始化之前，则并行中的reader就看到了未初始化的值。CPU 需要内存屏障（ memory barrier ）才能保证有序执行，但众所周知，内存屏障用起来很复杂。因此，我们将它们封装到具有发布语义的函数 rcu_assign_pointer() 1,中。最后四行将如下所示：

1
2
3
4

p->a = 1;
p->b = 2;
p->c = 3;
rcu_assign_pointer(gp, p);

rcu_assign_pointer() 将发布新结构，约束编译器和 CPU 在分配 p 的字段之后再执行将gp指向p。 然而仅仅约束 updater 的顺序是不够的，reader 的执行顺序也必须进行适当的约束：

1
2
3
4

p = gp;
if (p != NULL) {
  do_something_with(p->a, p->b, p->c);
}

尽管上面的代码不容易被误解，但经过编译优化，在某些cpu上 p->a 、p->b 、p->c字段的值会在p的值之前被获取！

正常情况下，我们会认为程序会先获取指针 p 的值（即指向的内存地址），然后再根据这个地址去访问 p->a 、 p->b 和 p->c 的值。然而，在 DEC Alpha CPU 上，结合编译器的值预测优化，情况可能不同。

值预测优化是一种激进的编译器优化技术，特别是在基于性能分析的优化（ profile-driven optimization ）中。编译器会「猜测」指针 p 的值，并基于这个猜测提前获取 p->a 、 p->b 和 p->c 的值。然后，它再去实际获取 p 的值，以验证之前的猜测是否正确。这种优化会导致在获取 p 的值之前，p->a 、 p->b 和 p->c 已经被访问，从而可能引发内存访问顺序的错乱。

这个例子说明：虽然代码表面上看起来不会有内存访问顺序问题，但在特定的硬件和激进的编译器优化下，程序的执行顺序可能违反直觉。

显然，我们需要防止编译器和 CPU 进行这种狡猾的操作。rcu_dereference() 会使用所需的任何内存屏障指令和编译器指令2来实现这一目的：

1
2
3
4
5
6

rcu_read_lock();
p = rcu_dereference(gp);
if (p != NULL) {
  do_something_with(p->a, p->b, p->c);
}
rcu_read_unlock();

rcu_dereference() 函数可以被视为订阅指定指针的某个给定值，从而保证后续的反引用操作将看到在对应的发布（ rcu_assign_pointer ）操作之前发生的任何初始化。rcu_read_lock() 和 rcu_read_unlock() 调用是绝对必需的：它们定义了 RCU 读侧临界区的范围。它们的用途将在下一节中解释，然而，它们从不自旋或阻塞，也不阻止 list_add_rcu() 并发执行。事实上，在非 CONFIG_PREEMPT 内核中，它们生成的代码完全为空。

尽管 rcu_assign_pointer() 和 rcu_dereference() 理论上可以用来构建任何可想象的 RCU 保护的数据结构，但使用中通常最好抽象用在更高层的结构。因此，rcu_assign_pointer() 和 rcu_dereference() 函数已被嵌入到 Linux 链表操作 API 的特殊 RCU 变体函数中。Linux 有两种双向链表变体：循环的 struct list_head 和线性的 struct hlist_head/struct hlist_node 对。

下面给出了一个适配链表的指针发布的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

struct foo {
  struct list_head list;
  int a;
  int b;
  int c;
};
LIST_HEAD(head);

/* . . . */
 
 p = kmalloc(sizeof(*p), GFP_KERNEL);
 p->a = 1;
 p->b = 2;
 p->c = 3;
 list_add_rcu(&p->list, &head);

第 15 行使用 list_add_rcu() 将一个新节点添加到链表中，但这一操作必须受到某种同步机制（通常是锁）的保护，以防止多个 list_add() 实例同时执行导致竞争问题。然而，这种同步机制并不会阻止 list_add_rcu() 与 RCU 读操作并发执行。

订阅（访问）受 RCU 保护的链表的代码如下：

1
2
3
4
5

rcu_read_lock();// 进入 RCU 读侧临界区
list_for_each_entry_rcu(p, head, list) {// 遍历链表
  do_something_with(p->a, p->b, p->c);// 处理节点数据
}
rcu_read_unlock();// 退出 RCU 读侧临界区

list_add_rcu() 函数负责将一个新节点发布到指定的链表中，并保证后续的 list_for_each_entry_rcu() 调用能够正确订阅（访问）到这个节点。换句话说，list_add_rcu() 确保新添加的节点对读侧是可见的，而 list_for_each_entry_rcu() 则以安全的方式遍历链表，访问每个节点的数据。

疑问2: 为什么 list_for_each_entry_rcu() 不会在与 list_add_rcu() 同时执行时发生段错误？

Linux的另一个链表hlist，是一个线性链表，这意味着它仅需要一个指针，而不是环形链表所需的两个指针。因此，使用hlist可以将大量散列表的哈希桶阵列的内存消耗减半。

hlist指针发布、订阅（读取）也和list类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

struct foo {
  struct hlist_node *list;
  int a;
  int b;
  int c;
};
HLIST_HEAD(head);

/* . . . */
 
p = kmalloc(sizeof(*p), GFP_KERNEL);
p->a = 1;
p->b = 2;
p->c = 3;
hlist_add_head_rcu(&p->list, &head); // 同步机制 保护增加操作

/* . . . */

rcu_read_lock();// 进入 RCU 读侧临界区
hlist_for_each_entry_rcu(p, q, head, list) {// 遍历链表
  do_something_with(p->a, p->b, p->c);// 处理节点数据
}
rcu_read_unlock();// 退出 RCU 读侧临界区

疑问3: 为什么 hlist_for_each_entry_rcu() 需要提供两个指针，而list_for_each_entry_rcu() 只需要1个？ 3

下表显示了RCU发布和订阅函数的集合，以及「取消发布」或「撤回」的函数：

类型 发布 撤回（取消发布） 订阅
Pointers rcu_assign_pointer() rcu_assign_pointer(…, NULL) rcu_dereference()
Lists list_add_rcu()
list_add_tail_rcu()
list_replace_rcu()		 list_del_rcu() list_for_each_entry_rcu()
Hlists hlist_add_after_rcu()
hlist_add_before_rcu()
hlist_add_head_rcu()
hlist_replace_rcu()		 hlist_del_rcu() hlist_for_each_entry_rcu()

请注意，list_replace_rcu()、list_del_rcu()、hlist_replace_rcu() 和 hlist_del_rcu() API 增加了一些复杂性：什么时候可以安全地释放被替换或删除的数据元素？特别是，我们如何能够知道所有 reader 何时已经释放了对该数据元素的引用？

这些问题将在下一节中讨论。

等待RCU reader完成

基本上，RCU 是一套等待事情完成的方法。当然，还有许多其他等待事情完成的方法，包括引用计数、读写锁、事件等等。RCU 的最大优势在于它可以等待（例如）20,000 个不同的事物完成，而无需显式跟踪每一个事物，也无需担心性能下降、可扩展性限制、复杂的死锁场景以及使用显式跟踪方案时固有的内存泄漏风险。

在 RCU 的场景下，等待的事物被称为RCU 读侧临界区。RCU 读侧临界区以 rcu_read_lock() 函数开始，并以对应的 rcu_read_unlock() 函数结束。RCU 读侧临界区可以嵌套，并且可以包含几乎任何代码，只要这些代码不显式阻塞或睡眠（尽管有一种特殊的 RCU 形式称为SRCU，它允许在 SRCU 读侧临界区中进行一般的睡眠）。如果你遵循这些约定，你就可以使用 RCU 来等待任何想要的代码段完成。

RCU 通过间接确定这些等待中的事物何时完成来实现这一特性，正如在 RCU Classic 和 实时 RCU 中其他地方所描述的那样。

特别是，如下图所示，RCU 是一种等待现有 RCU 读临界区完全完成的方法，包括这些临界区执行的内存操作。

等待读临界区 等待读临界区

然而，请注意，在某个宽限期开始之后开始的 RCU 读侧临界区可以并且将会延续到该宽限期结束之后。

以下伪代码展示了使用 RCU 等待 reader 的算法基本形式：

  1. 进行更改，例如，替换链表中的一个元素。
  2. 等待所有现有的 RCU 读侧临界区完全完成（例如，通过使用 synchronize_rcu() 函数）。这里的关键观察是：后续的 RCU 读侧临界区无法获得对被替换元素的引用。
  3. 清理，例如，释放上面被替换的元素。

下面的代码片段，改编自上一节的内容，演示了这个过程，其中字段 a 是搜索键：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct foo {
  struct list_head list;
  int a;
  int b;
  int c;
};
LIST_HEAD(head);

/* . . . */

p = search(head, key);
if (p == NULL) {
  /* 采取适当的行动，解锁并返回 */
}
q = kmalloc(sizeof(*p), GFP_KERNEL);
*q = *p;  // 复制
q->b = 2; // 更新
q->c = 3;
/* list_replace_rcu(struct list_head *old, struct list_head *new) */
list_replace_rcu(&p->list, &q->list); 
synchronize_rcu();
kfree(p);

第 20 和 21、22 行实现了上述三个步骤。第 16-20 行赋予了 RCU（“读取-复制-更新”）其名称：在允许并发读取的同时，第 16 行进行复制，第 17-20 行进行更新。 synchronize_rcu() 函数乍看之下可能有些神秘。毕竟，它必须等待所有 RCU 读侧临界区完成，而正如我们之前所见，rcu_read_lock() 和 rcu_read_unlock() 函数（用于界定 RCU 读侧临界区）在非 CONFIG_PREEMPT 内核中甚至不会生成任何代码！

这里有一个技巧：RCU Classic 的读侧临界区（由 rcu_read_lock() 和 rcu_read_unlock() 界定）不允许阻塞或睡眠。因此，当某个 CPU 执行上下文切换时，我们可以保证之前的 RCU 读侧临界区已经完成。这意味着，只要每个 CPU 至少执行了一次上下文切换，所有之前的 RCU 读侧临界区就保证已经完成，从而 synchronize_rcu() 可以安全返回。 因此，RCU Classic 的 synchronize_rcu() 在概念上可以简单到如下形式：

1
2

for_each_online_cpu(cpu)
  run_on(cpu);

run_on() 将当前线程切换到指定的 CPU，从而强制该 CPU 进行上下文切换。因此，for_each_online_cpu() 循环会强制每个 CPU 进行上下文切换，从而保证所有之前的 RCU 读侧临界区已经完成，如所需。虽然这种简单的方法适用于禁止在 RCU 读侧临界区中进行抢占的内核（即非 CONFIG_PREEMPT 和 CONFIG_PREEMPT 内核），但它不适用于 CONFIG_PREEMPT_RT 实时（-rt）内核。因此，实时 RCU 使用了一种基于引用计数的不同方法。

当然，Linux 内核中的实际实现要复杂得多，因为它需要处理中断、NMI（Non-Maskable Interrupt）、CPU 热插拔以及生产环境中内核的其他风险，同时还要保持良好的性能和可扩展性。实时 RCU 实现还必须有助于提供良好的实时响应，这排除了依赖于禁用抢占的实现（例如上面简单的两行代码）。

虽然知道 synchronize_rcu() 有一个简单的概念性实现很有帮助，但其他问题仍然存在。例如，RCU reader 在遍历并发更新的列表时究竟会看到什么？这个问题将在下一节中讨论。

维护最近更新的对象的多个版本

本节展示了 RCU 如何维护列表的多个版本以适应无同步的 reader 。以下展示了两个示例，说明在 reader 仍处于其 RCU 读侧临界区时，可能被引用的元素必须保持完整。第一个示例演示了删除列表元素，第二个示例演示了替换元素。

示例1 删除期间维护多个版本

为了开始“删除”示例，我们将修改上一节示例中的第 11-22 行代码如下：

1
2
3
4
5
6

 p = search(head, key);
 if (p != NULL) {
   list_del_rcu(&p->list);
   synchronize_rcu();
   kfree(p);
 }

列表的初始状态，包括指针 p，如下所示：

对象多版本维护1

每个元素中的三元组分别表示字段 a、b 和 c 的值。每个元素上的白色边框表示 reader 可能持有对它们的引用，并且由于 reader 不直接与 updater 同步，reader 可能在整个替换过程中并发运行。(为了清晰起见，我们省略了反向指针以及从列表尾部到头部的链接。)

在第 3 行的 list_del_rcu() 完成之后，元素 5,6,7 已从列表中移除，如下所示。由于 reader 不直接与 updater 同步，reader 可能在并发扫描此列表时看到或看不到新移除的元素，这取决于时间点。然而，如果 reader 在获取指向新移除元素的指针后被延迟（例如，由于中断、ECC 内存错误，或在 CONFIG_PREEMPT_RT 内核中被抢占），他们可能在移除后相当长的时间内仍看到列表的旧版本。因此，我们现在有两个版本的列表：一个包含元素 5,6,7，一个不包含。元素 5,6,7 的边框仍为白色，表示 reader 可能仍在引用它。

对象多版本维护2

请注意，reader 在退出其 RCU 读侧临界区后，不允许继续持有对元素 5,6,7 的引用。因此，一旦第 4 行的 synchronize_rcu() 完成，保证所有现有的 reader 都已完成，就不会有 reader 再引用该元素，如下图所示，旧元素的白色边框消失，列表恢复到单一版本。

对象多版本维护3

此时，元素 5,6,7 可以安全地被释放：

对象多版本维护4

至此，我们完成了元素 5,6,7 的删除。下一节将讨论替换。

示例2 替换期间维护多个版本

开始替换示例，以下是上一节示例中的代码后续

1
2
3
4
5
6
7

q = kmalloc(sizeof(*p), GFP_KERNEL);
*q = *p;
q->b = 2;
q->c = 3;
list_replace_rcu(&p->list, &q->list);
synchronize_rcu();
kfree(p);

列表的初始状态，包括指针 p，与删除示例相同：

对象多版本维护1

与之前一样，每个元素中的三元组分别表示字段 a、b 和 c 的值。每个元素上的白色边框表示 reader 可能持有对它们的引用，并且由于 reader 不直接与 updater 同步，reader 可能在整个替换过程中并发运行。(同样省略了反向指针以及从列表尾部到头部的链接。)

第 1 行通过 kmalloc() 分配一个替换元素，如下所示：

对象多版本维护5

第 2 行将旧元素复制到新元素：

对象多版本维护6

第 3、4 行更新 q->b、q->c的值

对象多版本维护7

现在，第 5 行执行替换操作，使得新元素最终对 reader 可见。此时，如下所示，我们有两个版本的列表。现有 reader 可能看到元素 5,6,7，但新 reader 将看到元素 5,2,3。但任何特定的 reader 都保证会看到一个定义明确的列表。

对象多版本维护8

在第 6 行的 synchronize_rcu() 返回后，一个宽限期已经过去，因此在 list_replace_rcu() 之前开始的所有读取都已完成。特别是，任何可能持有对元素 5,6,7 引用的 reader 都保证已经退出其 RCU 读侧临界区，因此被禁止继续持有引用。因此，不再有 reader 持有对旧元素的引用，如下图所示，旧元素的白色边框消失。对 reader 而言，我们回到了只有一个列表版本的状态，但新元素已替换旧元素。

对象多版本维护9

在第 7 行的 kfree() 完成后，列表将如下所示：

对象多版本维护10

尽管 RCU 以替换的情况命名，但在 Linux 内核中，绝大多数 RCU 使用依赖于上一示例所示的简单删除情况。

讨论

这些示例假设在整个更新操作期间持有一个互斥锁，这意味着在任何给定时间最多只能有两个版本的列表处于活动状态。 疑问4：如何修改删除示例以允许超过两个版本的列表同时处于活动状态？ 疑问5：在任何时间，一个列表可以有多少个 RCU 版本处于活动状态？

这一系列事件展示了 RCU 更新如何使用多个版本在存在并发 reader 的情况下安全地进行更改。当然，一些算法无法优雅地处理多个版本。存在一些技术可以将此类算法适配到 RCU，但这些超出了本文的范围。

结论

本文描述了基于 RCU 的算法的三个基本组成部分：

  1. 用于添加新数据的发布-订阅机制，
  2. 等待现有 RCU reader 完成的方法，
  3. 通过维护多个版本的数据，在不损害或过度延迟的并发中的 RCU reader 的情况下进行更改。

疑问6：考虑到 rcu_read_lock() 和 rcu_read_unlock() 函数既不自旋也不阻塞，RCU updater 如何可能延迟 RCU reader？

这三个 RCU 组件允许在存在并发 reader 的情况下更新数据，并且可以以不同方式组合，以实现令人惊讶的多种基于 RCU 的算法，这些算法将是「什么是真正的RCU」系列下一部分的主题。

疑问的答案

疑问1: 但 seqlock 不也允许 reader 与 updater 的并发吗?

答案：是也不是。虽然 seqlock reader 可以与 seqlock updater 并发运行，但每当这种情况发生时，read_seqretry() 函数会迫使 reader 重试。这意味着任何在 seqlock reader 与 seqlock updater 并发运行时所做的工作都将被丢弃并重做。因此，seqlock reader 虽然可以与 updater 并发运行，但在此场景下实际上无法完成任何工作。 相比之下，即使在存在并发 RCU updater 的情况下，RCU reader 也可以执行有用的工作。

疑问2: 为什么 list_for_each_entry_rcu() 不会在与 list_add_rcu() 同时执行时发生段错误？

答案：在运行 Linux 的所有系统上，指针的加载和存储是原子的，也就是说，如果对一个指针的存储与从同一指针的加载同时发生，加载将返回初始值或存储的值，而不会是两者的某种位混合。此外，list_for_each_entry_rcu() 总是向前遍历列表，永不回溯。因此，list_for_each_entry_rcu() 要么看到 list_add_rcu() 添加的元素，要么看不到，但无论如何，它都会看到一个有效且格式正确的列表。

疑问3: 为什么 hlist_for_each_entry_rcu() 需要提供两个指针，而list_for_each_entry_rcu() 只需要1个？

答案：因为在 hlist 中，需要检查是否为 NULL，而不是检查是否遇到头节点。（尝试编写一个单指针的 hlist_for_each_entry_rcu()。如果你能想出一个好的解决方案，那将是非常棒的事情！）

疑问4：如何修改删除示例以允许超过两个版本的列表同时处于活动状态？

答案：实现这一点的一种方法如下：

1
2
3
4
5
6
7
8
9
10

spin_lock(&mylock);
p = search(head, key);
if (p == NULL)
    spin_unlock(&mylock);
else {
    list_del_rcu(&p->list);
    spin_unlock(&mylock);
    synchronize_rcu();
    kfree(p);
}

这意味着多个并发删除可能在 synchronize_rcu() 中等待。

疑问5：在任何时间，一个列表可以有多少个 RCU 版本处于活动状态？

答案：这取决于同步设计。如果保护更新的锁在宽限期内一直被持有，那么最多只能有两个版本，即旧版本和新版本。 然而，如果只有搜索、更新和 list_replace_rcu() 受锁保护，那么可能有任意数量的版本处于活动状态，仅受内存和宽限期内可完成的更新次数的限制。但请注意，更新如此频繁的数据结构可能不是 RCU 的理想候选者。尽管如此，RCU 在必要时可以处理高更新率。

疑问6：考虑到 rcu_read_lock() 和 rcu_read_unlock() 函数既不自旋也不阻塞，RCU updater 如何会延迟到 RCU reader？

答案： RCU updater 进行的修改会导致相应 CPU 使包含数据的缓存行失效，迫使运行并发 RCU reader 的 CPU 承受昂贵的缓存未命中。（你能设计一种算法，在更改数据结构时不给并发读者带来昂贵的缓存未命中吗？对后续读者呢？）

译者注

  1. rcu_assign_pointer() 使用 smp_store_release() 来保证写指令的顺序 ↩︎

  2. rcu_dereference() 在绝大多数架构（x86, ARM, PowerPC 等）上，这是隐式的，通常只需要 READ_ONCE() 来防止编译器重排。但在 DEC Alpha 架构上，它显式调用了 smp_read_barrier_depends()。 ↩︎

  3. 在现代内核中，hlist_for_each_entry_rcu 与 list_for_each_entry_rcu 只需要3个固定参数 pos、head、member 与可选参数 cond ↩︎

Linux
Linux RCU
本文由作者按照 CC BY 4.0 进行授权