[编者按：这是 read-copy-update 机制如何工作的系列文章的第一篇。非常感谢 Paul McKenney 和 Jonathan Walpole 允许我们发布这些文章。剩余的 未来几周将出现两个部分。]

什么是 RCU，真的吗？

Paul E. McKenney，IBM Linux 技术中心
Jonathan Walpole，波特兰州立大学计算机科学系

介绍

读-复制-更新（RCU）是一种同步机制，于2002年10月被添加到Linux内核中。RCU通过允许读操作与更新操作并发执行来实现可扩展性的提升。与传统的锁原语（无论线程是读者还是更新者，都确保互斥）或读写锁（允许并发读但不允许在更新存在时进行并发读）不同，RCU支持单个更新者和多个读者之间的并发。RCU通过维护对象的多个版本并确保这些版本不会在所有现有的读侧临界区完成之前被释放，从而保证读操作的一致性。RCU定义并使用了高效且可扩展的机制来发布和读取对象的新版本，并且还推迟旧版本的回收。这些机制以一种方式分配读和更新路径的工作，使得读路径非常快速。在某些情况下（如不可抢占内核），RCU的读侧原语具有零开销。

快速测验 1：但 seqlock 不也允许读者和更新者并发执行吗？

这引出了一个问题：“RCU 究竟是什么？” 也许还有另一个问题：“RCU 是如何工作的？”（或者，更常见的是，断言 RCU 根本不可能工作）。本文档从基本角度回答这些问题；后续部分将从使用和 API 角度探讨这些问题。最后一部分还包括一个参考文献列表。

RCU 由三个基本机制组成，第一个用于插入，第二个用于删除，第三个用于使读者能够容忍并发的插入和删除。这些机制在以下章节中描述，重点是将 RCU 应用于链表：

• 发布-订阅机制（用于插入）
• 等待现有的 RCU 读者完成（用于删除）
• 维护最近更新对象的多个版本（用于读者）

这些章节之后是结论性评述和快速测验的答案。

发布-订阅机制

RCU 的一个关键特性是能够在数据被并发修改时安全地扫描数据。为了支持并发插入，RCU 使用了一种可以被视为发布-订阅机制的方法。例如，考虑一个初始为 NULL 的全局指针 gp，该指针将被修改以指向一个新分配和初始化的数据结构。以下代码片段（加上适当的锁）可能用于此目的：

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 的字段初始化之前，那么并发读取者可能会看到未初始化的值。需要内存屏障来保持顺序，但内存屏障出了名地难用。因此，我们将它们封装到具有发布语义的原语 rcu_assign_pointer() 中。最后四行代码将如下所示：

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

rcu_assign_pointer()将发布新的结构，强制编译器和 CPU 在对 p 的字段赋值之后再执行对 gp 的赋值。

然而，仅在更新者处强制顺序是不够的，读者也必须强制正确的顺序。考虑以下代码片段：

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

尽管这段代码看起来似乎不会出现乱序问题，不幸的是，DEC Alpha CPU [PDF] 和基于值推测的编译器优化确实可能导致在获取 p 的值之前就获取了 p->a、p->b 和 p->c 的值！这在基于值推测的编译器优化中最为明显，编译器会猜测 p 的值，然后获取 p->a、p->b 和 p->c 的值，最后获取 p 的实际值以检查其猜测是否正确。这种优化非常激进，甚至可以说是疯狂的，但在基于性能分析的优化上下文中确实会发生。

显然，我们需要阻止编译器和 CPU 的这类行为。rcu_dereference() 原语使用所需的内存屏障指令和编译器指令来达到这个目的：

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() 并发执行。实际上，在非抢占式内核中，它们完全不会产生任何代码。

虽然理论上 rcu_assign_pointer() 和 rcu_dereference() 可以用来构造任何可以想象得到的受 RCU 保护的数据结构，但实际上通常最好使用更高层次的构造。因此，rcu_assign_pointer() 和 rcu_dereference() 原语已经被嵌入到了 Linux 的列表操作 API 的特殊 RCU 变体中。Linux 有两个双链表变体，一个是循环的 struct list_head，另一个是线性的 struct hlist_head/struct hlist_node 对。前者布局如下图所示，其中绿色框表示列表头，蓝色框表示列表中的元素。

将指针发布的示例适配到链表中，代码如下：

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() 实例并发执行。然而，这种同步机制并不会阻止这个 list_add() 与 RCU 读取者并发执行。

订阅受 RCU 保护的链表

订阅一个受 RCU 保护的链表非常直接：

rcu_read_lock();
list_for_each_entry_rcu(p, head, list) {
  do_something_with(p->a, p->b, p->c);
}
rcu_read_unlock();

list_add_rcu() 原语将一个条目发布到指定的链表中，确保相应的 list_for_each_entry_rcu() 调用能够正确地订阅同一个条目。

快速测验 2：如果 list_for_each_entry_rcu() 恰好在 list_add_rcu() 执行的同时运行，如何防止 list_for_each_entry_rcu() 发生段错误？

在 RCU 保护的链表中，list_for_each_entry_rcu() 和 list_add_rcu() 可以并发执行。为了防止 list_for_each_entry_rcu() 在遍历过程中遇到新添加的节点而发生段错误，RCU 机制确保了以下几点：

1. 内存屏障：

• list_add_rcu() 使用适当的内存屏障指令来确保新添加的节点在发布之前是完全初始化的。
• rcu_dereference() 原语在读取者端使用内存屏障指令，确保在解引用指针之前，所有之前的写操作都已完成。

2. 旧版本保留：

• RCU 通过维护多个版本的数据来确保读者始终看到一致的状态。即使在 list_add_rcu() 添加新节点时，旧的链表结构仍然保持不变，直到所有现有的读侧临界区完成。
• 这意味着在 list_for_each_entry_rcu() 遍历时，它总是看到一个完整的、一致的链表视图，即使该视图可能不是最新的。

3. 宽限期：

• 在 list_del_rcu() 删除节点后，RCU 会等待一个宽限期（Grace Period），以确保所有现有的读侧临界区已经完成，然后再释放被删除的节点。
• 这保证了在 list_for_each_entry_rcu() 遍历时，不会访问到已经被删除但尚未释放的节点。

Linux 的另一种双链表：hlist

Linux 的另一种双链表 hlist 是线性的，这意味着它的头部只需要一个指针，而不是循环链表所需的两个指针。因此，使用 hlist 可以将大型哈希表的哈希桶数组的内存消耗减半。

将新元素发布到 RCU 保护的 hlist

将新元素发布到 RCU 保护的 hlist 与发布到循环链表非常相似：

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);

同样，第15行必须受到某种同步机制（例如锁）的保护，以防止多个 hlist_add_head_rcu() 实例并发执行。

订阅 RCU 保护的 hlist

订阅 RCU 保护的 hlist 也与订阅循环链表类似：

rcu_read_lock();
hlist_for_each_entry_rcu(p, q, head, list) {
  do_something_with(p->a, p->b, p->c);
}
rcu_read_unlock()

快速测验 3：为什么 hlist_for_each_entry_rcu() 需要传递两个指针，而 list_for_each_entry_rcu() 只需要一个？

RCU 发布、撤销和订阅原语

RCU 提供了一组发布和订阅原语，以及一些用于“撤销”或收回发布的原语。这些原语如下表所示：

类别	发布	撤销	订阅
指针	rcu_assign_pointer()	rcu_assign_pointer(..., NULL)	rcu_dereference()
列表	list_add_rcu() list_add_tail_rcu() list_replace_rcu()	list_del_rcu()	list_for_each_entry_rcu()
哈希列表	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 引入了一个复杂性问题：何时可以安全地释放被替换或移除的数据元素？特别是，我们如何知道所有读者已经释放了对该数据元素的引用？

这个问题将在接下来的部分中进行讨论。

等待现有的 RCU 读侧临界区完成

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

在 RCU 的情况下，被等待的事物被称为“RCU 读侧临界区”。一个 RCU 读侧临界区从 rcu_read_lock() 原语开始，到相应的 rcu_read_unlock() 原语结束。RCU 读侧临界区可以嵌套，并且可以包含几乎任何代码，只要这些代码不显式地阻塞或休眠（尽管有一种称为 SRCU 的特殊形式的 RCU 允许在 SRCU 读侧临界区中进行一般的休眠）。如果你遵守这些约定，你可以使用 RCU 来等待任意期望的代码段完成。

RCU 通过间接确定这些其他事物何时完成来实现这一壮举，正如对经典 RCU 和实时 RCU 所描述的那样。

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

宽限期扩展以包含现有的 RCU 读侧临界区。然而，请注意，在给定宽限期开始后开始的 RCU 读侧临界区可以并且将会超出该宽限期的结束时间。

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

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

下面的代码片段，改编自前面部分的代码，演示了这个过程，其中字段 a 作为搜索键：

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

/* . . . */

p = search(head, key);
if (p == NULL) {
  /* Take appropriate action, unlock, and return. */
}
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);

第19、20和21行实现了上述提到的三个步骤。第16-19行给出了 RCU（“读-复制-更新”）的名字：允许并发读取的同时，第16行进行复制，第17-19行进行更新。

synchronize_rcu() 原语乍一看可能有点神秘。毕竟，它必须等待所有 RCU 读侧临界区完成，而且正如我们之前看到的，界定 RCU 读侧临界区的 rcu_read_lock() 和 rcu_read_unlock() 原语在非 CONFIG_PREEMPT 内核中甚至不会生成任何代码！

这里有一个技巧，那就是由 rcu_read_lock() 和 rcu_read_unlock() 限定的经典 RCU 读侧临界区不允许阻塞或休眠。因此，当给定 CPU 执行上下文切换时，我们可以保证任何先前的 RCU 读侧临界区都已完成。这意味着一旦每个 CPU 至少执行了一次上下文切换，所有先前的 RCU 读侧临界区都保证已完成，这样 synchronize_rcu() 就可以安全地返回。

因此，经典 RCU 的 synchronize_rcu() 可以概念上简化为以下内容：

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、CPU 热插拔以及其他生产级内核的危险情况，同时还要保持良好的性能和可扩展性。实时 RCU 的实现还必须有助于提供良好的实时响应，这排除了依赖于禁用抢占的实现（如上面的两行代码）。

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

在对象更新期间维护多个版本

本节展示 RCU 如何在更新过程中维护列表的多个版本以适应无同步的读者。将介绍两个示例，说明如何在给定读者仍处于其 RCU 读侧临界区时保留对元素的引用。第一个例子演示删除列表元素，第二个例子演示替换元素。

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

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

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

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

每个元素中的三元组分别表示字段 a、b 和 c 的值。每个元素的红色边框表示读者可能会持有它们的引用，因为读者不会直接与更新者同步，所以读者可能会与整个替换过程并发运行。请注意，出于清晰起见，我们省略了反向指针和尾部链接到头部的链接。

在第 3 行的 list_del_rcu() 完成之后，5,6,7 元素已从列表中删除，如下所示。由于读者不会直接与更新者同步，根据时机不同，正在并发扫描此列表的读者可能会或可能不会看到刚刚删除的新元素。但是，如果在获取指向刚删除的元素的指针后因中断、ECC 内存错误或在实时 -rt 内核中预占等原因延迟的读者可能会在删除后相当长一段时间内看到旧版本的列表。因此，我们现在有两个版本的列表，一个带有元素 5,6,7，另一个没有。5,6,7 元素的边框仍然是红色，表示读者可能会引用它。

请记住，读者在退出 RCU 读侧临界区后不得保留对元素 5,6,7 的引用。因此，一旦第 4 行的 synchronize_rcu() 完成，确保所有预先存在的读者已经完成，就不再有读者引用此元素，如下所示，它的边框变为黑色。现在我们回到了列表的一个单一版本。

此时，可以安全地释放 5,6,7 元素，如下所示：

 至此，我们完成了元素 5,6,7 的删除。接下来的部分将涉及替换。

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

以下是前一节示例的最后几行：

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，与删除示例相同：

与以前一样，每个元素中的三元组分别表示字段 a、b 和 c 的值。每个元素的红色边框表示读者可能会持有它们的引用，因为读者不会直接与更新者同步，所以读者可能会与整个替换过程并发运行。同样，出于清晰起见，我们再次省略了反向指针和尾部链接到头部的链接。

第 1 行分配了一个替代元素，如下所示：

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

第 3 行将 q->b 更新为值“2”：

第 4 行将 q->c 更新为值“3”：

现在，第 5 行进行了替换，以便新元素最终对读者可见。此时，如下所示，我们有两个版本的列表。预先存在的读者可能会看到 5,6,7 元素，但新的读者会看到 5,2,3 元素。但是，任何给定的读者都会看到某个定义明确的列表。

在第 6 行的 synchronize_rcu() 返回后，宽限期已经过去，因此在 list_replace_rcu() 开始之前的所有读取都将完成。特别是，可能一直持有对 5,6,7 元素的引用的任何读者都有保证退出他们的 RCU 读侧临界区，并且禁止继续持有引用。因此，不可能再有任何读者持有对旧元素的引用，如下所示，5,6,7 元素周围有一条细黑边框。对于读者来说，我们又回到了只有一个版本的列表，但新元素取代了旧元素的位置。

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

尽管 RCU 的命名源于替换案例，但在 Linux 内核内部，大多数 RCU 使用依赖于前一节中显示的简单删除案例。

讨论

这些示例假设在整个更新操作过程中持有一个互斥锁，这意味着在给定时间最多只能有两个版本的列表处于活动状态。

快速测验 4：如何修改删除示例以允许多于两个版本的列表同时处于活动状态？

快速测验 5：在任何给定时间，一个特定列表可以有多少个 RCU 版本处于活动状态？

这一系列事件展示了 RCU 更新如何使用多个版本来安全地在存在并发读者的情况下执行更改。当然，并非所有算法都能优雅地处理多个版本。有一些技术[PDF]可以将这样的算法适应于 RCU，但这些超出了本文的范围。

快速测验答案提示

快速测验 4 答案提示： 要允许多于两个版本的列表同时处于活动状态，可以在删除或替换元素时不要求持有互斥锁。取而代之的是，允许并发更新发生，但需要确保每个更新操作都使用 list_del_rcu() 或 list_replace_rcu() 来进行，随后调用 synchronize_rcu() 来等待宽限期完成。这会允许在宽限期结束前有多个版本的列表共存。此外，可能还需要引入额外的数据结构来跟踪和管理不同版本的列表。

快速测验 5 答案提示： 在任何给定时间，一个特定列表可以有多少个 RCU 版本处于活动状态取决于系统中正在进行多少个并发更新以及每个更新是否已经完成了它们的宽限期。理论上，如果没有任何限制并且有许多并发更新，那么活动的 RCU 版本数量可以是任意多的。但实际上，由于系统资源的限制（例如内存），活动版本的数量会受到物理约束。通常情况下，RCU 的设计是为了支持少量的并发更新，这样在大多数情况下，活跃的版本数不会太多。实际的限制因素通常是系统的实现细节和可用资源。

 

结论

本文描述了基于 RCU（读-复制-更新）算法的三个基本组成部分：

1. 用于添加新数据的发布-订阅机制，
2. 一种等待现有的 RCU 读者完成的方法，以及
3. 维护多个版本以允许更改而不损害或不适当延迟并发 RCU 读者的规则。

快速测验 6：考虑到 rcu_read_lock() 和 rcu_read_unlock() 原语既不自旋也不阻塞，RCU 更新者怎么可能延迟 RCU 读者？

这三个 RCU 组件允许在面对并发读者时更新数据，并且可以以不同的方式组合起来实现多种类型的基于 RCU 的算法。其中一些将在本“什么是 RCU？”系列的后续文章中讨论。

致谢

我们非常感谢 Andy Whitcroft、Gautham Shenoy 和 Mike Fulton 对本文档早期草稿的审阅，他们的反馈极大地提高了文档的质量。我们还要感谢相对编程项目成员和 PNW TEC 成员提供的许多有价值的讨论。我们对 Dan Frye 对此工作的支持表示感谢。最后，这项工作得到了美国国家科学基金会资助（编号 CNS-0719851）的支持。

这份材料代表了作者的观点，并不一定代表 IBM 或波特兰州立大学的观点。

Linux 是 Linus Torvalds 的注册商标。

其他公司、产品和服务名称可能是他人的商标或服务标志。

快速测验答案

快速测验 1：但 seqlock 不是也允许读者和更新者同时进行工作吗？

答案：是也不是。虽然 seqlock 读者可以与 seqlock 写者并发运行，但每当这种情况发生时，read_seqretry() 原语将迫使读者重试。这意味着任何在 seqlock 读者与 seqlock 更新者并发运行时完成的工作都将被丢弃并重新执行。因此，seqlock 读者可以与更新者并发运行，但在这种情况下他们实际上无法完成任何有效工作。

相比之下，即使存在并发的 RCU 更新者，RCU 读者也能执行有用的工作。

快速测验 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() 只需要一个？

答案：因为在 hlist 中必须检查是否为 NULL 而不是遇到头节点。（尝试编写一个单指针版本的 hlist_for_each_entry_rcu()。如果你找到了一个好的解决方案，那将是非常好的！）

快速测验 4：如何修改删除示例以允许多于两个版本的列表同时处于活动状态？

答案：一种实现方式如下：

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 更新者怎么可能延迟 RCU 读者？

答案：给定的 RCU 更新者所做的修改会导致相应 CPU 使包含数据的缓存行失效，迫使运行并发 RCU 读者的 CPU 承受昂贵的缓存未命中。（你能设计出一种算法来改变数据结构而不对并发读者造成昂贵的缓存未命中吗？对于后续的读者呢？）