TREE_RCU 的宽限期内存排序之旅¶
2017 年 8 月 8 日
本文由 Paul E. McKenney 贡献
简介¶
本文档粗略地概述了 Tree RCU 的宽限期内存排序保证是如何提供的。
什么是 Tree RCU 的宽限期内存排序保证？¶
RCU 宽限期为非空闲非离线代码提供了极其强大的内存排序保证。保证在给定 RCU 宽限期结束之后发生的任何代码都能看到该宽限期开始之前的所有访问的效果，这些访问都在 RCU 读取端关键区域内。类似地，保证在给定 RCU 宽限期开始之前发生的任何代码都看不到该宽限期结束后发生的所有访问的效果，这些访问都在 RCU 读取端关键区域内。
请注意，RCU-sched 读取端关键区域包括禁用抢占的任何代码区域。鉴于每个单独的机器指令都可以被认为是一个极小的禁用抢占的代码区域，可以将 synchronize_rcu() 视为增强版的 smp_mb()。
RCU 更新器通过将其更新分为两个阶段来使用此保证，其中一个阶段在宽限期之前执行，另一个阶段在宽限期之后执行。在最常见的用例中，第一阶段从链接的 RCU 保护数据结构中删除一个元素，第二阶段释放该元素。为了使其工作，任何在第一阶段更新之前（在常见情况下，删除）目睹状态的读取器都不能目睹第二阶段更新之后（在常见情况下，释放）的状态。
RCU 实现使用基于锁的关键区域网络、内存屏障和每个 CPU 的处理来提供此保证，如下节所述。
Tree RCU 宽限期内存排序构建块¶
RCU 宽限期内存排序的主要工具是 rcu_node 结构的 ->lock 的关键区域。这些关键区域使用辅助函数进行锁获取，包括 raw_spin_lock_rcu_node()、raw_spin_lock_irq_rcu_node() 和 raw_spin_lock_irqsave_rcu_node()。它们的锁释放对应物分别是 raw_spin_unlock_rcu_node()、raw_spin_unlock_irq_rcu_node() 和 raw_spin_unlock_irqrestore_rcu_node()。为了完整起见，还提供了 raw_spin_trylock_rcu_node()。关键点在于锁获取函数，包括 raw_spin_trylock_rcu_node()，在成功获取锁后立即调用 smp_mb__after_unlock_lock()。
因此，对于任何给定的 rcu_node 结构，所有 CPU 都会看到在上述锁释放函数之一之前发生的任何访问发生在稍后的上述锁获取函数之一之后发生的任何访问之前。此外，所有 CPU 都会看到在给定 CPU 上上述锁释放函数之一之前发生的任何访问发生在稍后在该同一 CPU 上执行的上述锁获取函数之一之后发生的任何访问之前，即使锁释放和锁获取函数操作的是不同的 rcu_node 结构。Tree RCU 使用这两个排序保证在所有以任何方式参与宽限期的 CPU 之间形成排序网络，包括在相关宽限期期间上线或下线的任何 CPU。
以下测试程序展示了这些锁获取和锁释放函数的排序效果
1 int x, y, z;
2
3 void task0(void)
4 {
5 raw_spin_lock_rcu_node(rnp);
6 WRITE_ONCE(x, 1);
7 r1 = READ_ONCE(y);
8 raw_spin_unlock_rcu_node(rnp);
9 }
10
11 void task1(void)
12 {
13 raw_spin_lock_rcu_node(rnp);
14 WRITE_ONCE(y, 1);
15 r2 = READ_ONCE(z);
16 raw_spin_unlock_rcu_node(rnp);
17 }
18
19 void task2(void)
20 {
21 WRITE_ONCE(z, 1);
22 smp_mb();
23 r3 = READ_ONCE(x);
24 }
25
26 WARN_ON(r1 == 0 && r2 == 0 && r3 == 0);
WARN_ON() 在“时间尽头”评估，在所有更改都已在整个系统中传播之后。如果没有获取函数提供的 smp_mb__after_unlock_lock()，例如在 PowerPC 上，此 WARN_ON() 可能会触发。smp_mb__after_unlock_lock() 调用阻止此 WARN_ON() 触发。
快速测验: |
但是 rcu_node 结构锁获取链保证新的读取器将看到更新器的所有宽限期前访问，并且还保证更新器的宽限期后访问将看到所有旧读取器的访问。那么为什么我们需要所有这些对 smp_mb__after_unlock_lock() 的调用呢？ |
答案: |
因为我们必须为 RCU 的轮询宽限期原语提供排序，例如， CPU 0 CPU 1
---- ----
WRITE_ONCE(X, 1) WRITE_ONCE(Y, 1)
g = get_state_synchronize_rcu() smp_mb()
while (!poll_state_synchronize_rcu(g)) r1 = READ_ONCE(X)
continue;
r0 = READ_ONCE(Y)
RCU 保证不会发生 r0 == 0 && r1 == 0 的结果，即使 CPU 1 处于 RCU 扩展静止状态（空闲或离线），因此根本不会直接与 RCU 核心处理交互。 |
这种方法必须扩展到包括空闲 CPU，这些 CPU 需要 RCU 的宽限期内存排序保证，以扩展到当前空闲停留之前和之后的所有 RCU 读取端关键区域。这种情况由对强排序的 atomic_add_return() 读取-修改-写入原子操作的调用处理，该操作在空闲进入时的 ct_kernel_exit_state() 和空闲退出时的 ct_kernel_enter_state() 中调用。宽限期 kthread 首先调用 ct_rcu_watching_cpu_acquire()（前面有一个完整的内存屏障）和 rcu_watching_snap_stopped_since()（两者都依赖于获取语义）来检测空闲 CPU。
快速测验: |
但是对于在整个宽限期内保持离线的 CPU 呢？ |
答案: |
这样的 CPU 在宽限期开始时将处于离线状态，因此宽限期不会期望它们的静止状态。宽限期开始和 CPU 热插拔操作之间的竞争由 CPU 的叶 |
该方法必须扩展到处理最后一个案例，即唤醒在 synchronize_rcu() 中阻塞的任务。此任务可能被绑定到尚未意识到宽限期已结束的 CPU，因此可能尚未受到宽限期的内存排序的约束。因此，在 synchronize_rcu() 代码路径中，从 wait_for_completion() 返回后有一个 smp_mb()。
快速测验: |
什么？在哪里？？？我没有看到从 |
答案: |
那是因为我在创建此文档时发现了对该 |
Tree RCU 的宽限期内存排序保证最严重地依赖于 rcu_node 结构的 ->lock 字段，以至于有必要在下一节的图中缩写此模式。例如，考虑下面显示的 rcu_prepare_for_idle() 函数，该函数是强制执行新到达的 RCU 回调针对未来宽限期的排序的几个函数之一
1 static void rcu_prepare_for_idle(void)
2 {
3 bool needwake;
4 struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
5 struct rcu_node *rnp;
6 int tne;
7
8 lockdep_assert_irqs_disabled();
9 if (rcu_rdp_is_offloaded(rdp))
10 return;
11
12 /* Handle nohz enablement switches conservatively. */
13 tne = READ_ONCE(tick_nohz_active);
14 if (tne != rdp->tick_nohz_enabled_snap) {
15 if (!rcu_segcblist_empty(&rdp->cblist))
16 invoke_rcu_core(); /* force nohz to see update. */
17 rdp->tick_nohz_enabled_snap = tne;
18 return;
19 }
20 if (!tne)
21 return;
22
23 /*
24 * If we have not yet accelerated this jiffy, accelerate all
25 * callbacks on this CPU.
26 */
27 if (rdp->last_accelerate == jiffies)
28 return;
29 rdp->last_accelerate = jiffies;
30 if (rcu_segcblist_pend_cbs(&rdp->cblist)) {
31 rnp = rdp->mynode;
32 raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
33 needwake = rcu_accelerate_cbs(rnp, rdp);
34 raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */
35 if (needwake)
36 rcu_gp_kthread_wake();
37 }
38 }
但是对于此讨论真正重要的 rcu_prepare_for_idle() 的部分是第 32-34 行。因此，我们将此函数缩写如下
该框表示 rcu_node 结构的 ->lock 关键区域，顶部的双线表示额外的 smp_mb__after_unlock_lock()。
Tree RCU 宽限期内存排序组件¶
Tree RCU 的宽限期内存排序保证由多个 RCU 组件提供
以下每个部分都详细介绍了相应的组件。
回调注册表¶
如果 RCU 的宽限期保证有任何意义，那么在给定 call_rcu() 调用之前发生的任何访问也必须发生在相应的宽限期之前。RCU 宽限期保证的此部分的实现如下图所示
因为 call_rcu() 通常仅作用于 CPU 本地状态，所以它不提供任何排序保证，无论是对于自身还是对于更新的第一阶段（再次，通常是从 RCU 保护的数据结构中删除元素）。它只是将 rcu_head 结构排队到每个 CPU 的列表中，直到稍后调用 rcu_accelerate_cbs() 才能与宽限期关联，如上图所示。
左侧显示的一组代码路径通过 note_gp_changes() 调用 rcu_accelerate_cbs()，要么直接从 call_rcu() 调用（如果当前 CPU 被排队的 rcu_head 结构淹没），要么更可能从 RCU_SOFTIRQ 处理程序调用。中间的另一个代码路径仅在以 CONFIG_RCU_FAST_NO_HZ=y 构建的内核中采用，该路径通过 rcu_prepare_for_idle() 调用 rcu_accelerate_cbs()。右侧的最后一个代码路径仅在以 CONFIG_HOTPLUG_CPU=y 构建的内核中采用，该路径通过 rcu_advance_cbs()、rcu_migrate_callbacks、rcutree_migrate_callbacks() 和 takedown_cpu() 调用 rcu_accelerate_cbs()，而 takedown_cpu() 反过来又在传出 CPU 完全脱机后在幸存的 CPU 上调用。
宽限期处理中还有一些其他代码路径会机会主义地调用 rcu_accelerate_cbs()。但是，无论哪种方式，CPU 最近排队的所有 rcu_head 结构都与未来的宽限期编号相关联，该编号受 CPU 的主要 rcu_node 结构的 ->lock 的保护。在所有情况下，对于同一 rcu_node 结构的 ->lock 的任何先前关键区域，以及对于任何 rcu_node 结构的 ->lock 的当前任务或 CPU 的任何先前关键区域，都存在完整的排序。
下一节将显示此排序如何确保在 call_rcu() 之前发生的任何访问（特别包括更新的第一阶段）发生在相应宽限期开始之前。
快速测验: |
但是 |
答案: |
|
宽限期初始化¶
宽限期初始化由宽限期内核线程执行，该线程在 rcu_gp_init() 函数中多次遍历 rcu_node 树。这意味着显示通过宽限期计算的完整排序流程将需要复制此树。如果您发现这令人困惑，请注意 rcu_node 的状态会随着时间的推移而变化，就像赫拉克利特的河流一样。但是，为了使 rcu_node 河流易于处理，宽限期内核线程的遍历分多个部分呈现，从本节中的宽限期初始化的各个阶段开始。
第一个与排序相关的宽限期初始化操作是推进 rcu_state 结构的 ->gp_seq 宽限期编号计数器，如下所示
实际的增量是使用 smp_store_release() 执行的，这有助于拒绝误报 RCU CPU 停顿检测。请注意，仅触摸根 rcu_node 结构。
第一次遍历 rcu_node 树会根据自上次宽限期开始以来已上线或下线的 CPU 来更新位掩码。在常见情况下，此 rcu_node 结构的在线 CPU 数量尚未转换到或从零转换，此遍历将仅扫描叶 rcu_node 结构。但是，如果给定叶 rcu_node 结构的在线 CPU 数量已从零转换，则将为第一个传入的 CPU 调用 rcu_init_new_rnp()。类似地，如果给定叶 rcu_node 结构的在线 CPU 数量已转换为零，则将为最后一个传出的 CPU 调用 rcu_cleanup_dead_rnp()。下图显示了如果最左边的 rcu_node 结构上线其第一个 CPU 且如果下一个 rcu_node 结构没有在线 CPU（或者，如果最左边的 rcu_node 结构离线其最后一个 CPU 且如果下一个 rcu_node 结构没有在线 CPU）时的排序路径。
通过 rcu_node 树的最后一次 rcu_gp_init() 遍历以广度优先的方式进行，将每个 rcu_node 结构的 ->gp_seq 字段设置为来自 rcu_state 结构的最新推进值，如下图所示。
此更改还将导致每个 CPU 下一次调用 __note_gp_changes() 时注意到新的宽限期已经开始，如下节所述。但是因为宽限期 kthread 在根处（通过推进 rcu_state 结构的 ->gp_seq 字段）启动了宽限期，然后在设置每个叶 rcu_node 结构的 ->gp_seq 字段之前，每个 CPU 对宽限期开始的观察将在宽限期实际开始之后发生。
快速测验: |
但是启动宽限期的 CPU 呢？为什么它不会在启动宽限期时立即看到宽限期的开始？ |
答案: |
在某些深刻的哲学和过度拟人化的意义上，是的，启动宽限期的 CPU 会立即意识到已经这样做了。但是，如果我们改为假设 RCU 没有自我意识，那么即使启动宽限期的 CPU 也要到第一次调用 |
自我报告的静止状态¶
当可能阻止宽限期的所有实体都报告了静止状态（或者如后面的章节所述，已经代表它们报告了静止状态）时，宽限期可以结束。在线非空闲 CPU 报告自己的静止状态，如下图所示
这是最后一个报告静止状态的 CPU，它发出宽限期结束的信号。较早的静止状态将仅向上推动 rcu_node 树，直到它们遇到正在等待其他静止状态的 rcu_node 结构。但是，排序仍然得到保留，因为稍后的某个静止状态将获取该 rcu_node 结构的 ->lock。
任意数量的事件都可能导致 CPU 调用 note_gp_changes（或者，直接调用 __note_gp_changes()），此时该 CPU 将注意到在保持其叶 rcu_node 锁的同时，新的宽限期已经开始。因此，此图中显示的所有执行都在宽限期开始之后发生。此外，此 CPU 将考虑在调用 __note_gp_changes() 之前启动的任何 RCU 读取端关键区域在宽限期之前启动，因此宽限期必须等待的关键区域。
快速测验: |
但是 RCU 读取端关键区域可能在宽限期开始之后启动（较早的 |
答案: |
宽限期确实没有必要等待这样的关键区域。但是，允许等待它。而且，等待它也很重要，因为这种惰性方法比“大爆炸”一次性宽限期开始可能具有的可伸缩性要高得多。 |
如果 CPU 进行上下文切换，则 rcu_note_context_switch() 将在左侧注意到静止状态。另一方面，如果 CPU 在用户模式下执行时发生调度程序时钟中断，则 rcu_sched_clock_irq() 将在右侧注意到静止状态。无论哪种方式，通过静止状态的通道都将在每个 CPU 的变量中记录。
下次 RCU_SOFTIRQ 处理程序在此 CPU 上执行时（例如，在下一次调度程序时钟中断之后），rcu_core() 将调用 rcu_check_quiescent_state()，后者将注意到记录的静止状态，并调用 rcu_report_qs_rdp()。如果 rcu_report_qs_rdp() 验证静止状态确实适用于当前宽限期，它将调用 rcu_report_rnp()，后者将遍历 rcu_node 树，如图底部所示，从每个 rcu_node 结构的 ->qsmask 字段中清除位，并在结果为零时向树向上传播。
请注意，只有当当前 CPU 报告由该 rcu_node 结构为首的子树的最后一个静止状态时，遍历才会从给定的 rcu_node 结构向上传递。关键的一点是，如果 CPU 的遍历停止在给定的 rcu_node 结构处，那么将会有另一个 CPU（或者可能是同一个 CPU）的稍后遍历从该点向上进行，并且 rcu_node ->lock 保证第一个 CPU 的静止状态发生在第二个 CPU 遍历的其余部分之前。重复应用此思路表明，所有 CPU 的静止状态都发生在最后一个 CPU 遍历根 rcu_node 结构之前，“最后一个 CPU”是清除根 rcu_node 结构的 ->qsmask 字段中的最后一位的 CPU。
动态滴答接口¶
由于能源效率方面的考虑，RCU 被禁止干扰空闲 CPU。因此，CPU 需要在进入或离开空闲状态时通知 RCU，它们通过在每个 CPU 的变量上进行完全排序的返回值原子操作来做到这一点。排序效果如下所示
RCU 宽限期内核线程在保持相应 CPU 的叶 rcu_node 结构的 ->lock 的同时，对每个 CPU 的空闲变量进行采样。这意味着在空闲期间之前（上图顶部附近的椭圆）的任何 RCU 读取端关键区域都将在当前宽限期结束之前发生。类似地，当前宽限期的开始将在空闲期间之后的任何 RCU 读取端关键区域（上图底部附近的椭圆）之前发生。
将其整合到完整的宽限期执行中将在下面介绍。
CPU 热插拔接口¶
RCU 也被禁止干扰离线 CPU，这些 CPU 很可能已断电并已从系统中完全移除。因此，CPU 需要将它们的来来去去通知 RCU，作为相应的 CPU 热插拔操作的一部分。排序效果如下所示
由于 CPU 热插拔操作的频率远低于空闲转换，因此它们的权重更大，因此获取 CPU 的叶 rcu_node 结构的 ->lock 并更新该结构的 ->qsmaskinitnext。RCU 宽限期内核线程对该掩码进行采样，以检测自此宽限期开始以来已离线的 CPU。
将其整合到完整的宽限期执行中将在下面介绍。
强制静止状态¶
如上所述，空闲和离线 CPU 无法报告自己的静止状态，因此宽限期内核线程必须代表它们进行报告。此过程称为“强制静止状态”，每隔几个节拍重复一次，其排序效果如下所示
保证静止状态强制的每次通过都遍历叶 rcu_node 结构，如果没有由于最近空闲和/或离线 CPU 而导致的新静止状态，则仅遍历叶。但是，如果如左侧所示有新离线 CPU，或者如右侧所示有新空闲 CPU，则相应的静止状态将被推向根。与自我报告的静止状态一样，一旦到达 rcu_node 结构，该结构具有来自其他 CPU 的未完成的静止状态，则向上驱动停止。
快速测验: |
最左边的驱动程序在到达根 |
答案: |
分析得很好！实际上，在没有 RCU 的错误的情况下，这是不可能的。但是此图本身已经足够复杂，因此为了简洁而牺牲了准确性。您可以将其视为诗意的许可，也可以将其视为在拼接图中解决的误导。 |
宽限期清理¶
宽限期清理首先以广度优先的方式扫描 rcu_node 树，推进所有 ->gp_seq 字段，然后推进 rcu_state 结构的 ->gp_seq 字段。排序效果如下所示
如图底部的椭圆形所示，一旦宽限期清理完成，下一个宽限期就可以开始。
快速测验: |
但是宽限期到底何时结束呢？ |
答案: |
没有一个有用的单点可以说宽限期结束了。最早合理的候选时间是最后一个 CPU 报告其静止状态之后，但 RCU 可能需要几毫秒才能意识到这一点。最晚合理的候选时间是 |
回调调用¶
一旦给定的 CPU 的叶 rcu_node 结构的 ->gp_seq 字段已更新，该 CPU 就可以开始调用正在等待此宽限期结束的 RCU 回调。这些回调由 rcu_advance_cbs() 标识，通常由 __note_gp_changes() 调用。如下图所示，此调用可以由调度时钟中断（左侧的 rcu_sched_clock_irq()）或空闲进入（右侧的 rcu_cleanup_after_idle()）触发，但仅适用于使用 CONFIG_RCU_FAST_NO_HZ=y 构建的内核。无论哪种方式，都会引发 RCU_SOFTIRQ，从而导致 rcu_do_batch() 调用回调，进而允许这些回调执行每个更新所需的第二阶段处理（直接或间接通过唤醒）。
请注意，回调调用也可以由任何数量的极端情况代码路径提示，例如，当 CPU 注意到它已排队过多的回调时。在所有情况下，CPU 在调用回调之前都会获取其叶 rcu_node 结构的 ->lock，从而保持了针对新完成的宽限期所需的排序。
但是，如果回调函数与其他 CPU 通信，例如，执行唤醒操作，则保持排序是该函数的责任。例如，如果回调函数唤醒了一个在某些其他 CPU 上运行的任务，则回调函数和被唤醒的任务都必须正确排序。要了解为什么这很重要，请考虑宽限期清理图的上半部分。回调可能在对应于最左边的叶 rcu_node 结构的 CPU 上运行，并唤醒一个将在对应于最右边的叶 rcu_node 结构的 CPU 上运行的任务，并且宽限期内核线程可能尚未到达最右边的叶。在这种情况下，宽限期的内存排序可能尚未到达该 CPU，因此回调函数和唤醒的任务必须再次提供正确的排序。
整合在一起¶
拼接图在此处
法律声明¶
这项工作代表作者的观点，不一定代表 IBM 的观点。
Linux 是 Linus Torvalds 的注册商标。
其他公司、产品和服务名称可能是其他公司的商标或服务标志。