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()，此 WARN_ON() 可能会触发，例如在 PowerPC 上。 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 的任何先前临界区都存在完全排序，并且针对当前任务或 CPU 的任何 rcu_node 结构的 ->lock 的任何先前临界区也存在完全排序。
下一节将展示此排序如何确保在 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_node 结构的 ->gp_seq 字段之前在根处开始宽限期（通过推进 rcu_state 结构的 ->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 需要在相应的 CPU 热插拔操作中通知 RCU 它们的来去。排序效果如下所示
因为 CPU 热插拔操作比空闲转换的频率低得多，所以它们的权重更大，因此会获取 CPU 叶子 rcu_node 结构的 ->lock 并更新此结构的 ->qsmaskinitnext。RCU 宽限期内核线程会采样此掩码，以检测自宽限期开始以来已离线的 CPU。
如何将此机制融入到完整的宽限期执行中将在下方描述。
强制静止状态¶
如上所述，空闲和离线的 CPU 无法报告自己的静止状态，因此宽限期内核线程必须代表它们进行报告。此过程称为“强制静止状态”，它每隔几个时钟周期重复一次，其排序效果如下所示
每次强制静止状态的传递都保证遍历叶子 rcu_node 结构，并且如果没有由于最近空闲和/或离线的 CPU 而产生的新静止状态，则仅遍历叶子。但是，如果出现左侧所示的新离线 CPU 或右侧所示的新空闲 CPU，则相应的静止状态将被驱动到根。与自我报告的静止状态一样，一旦到达来自其他 CPU 的未完成静止状态的 rcu_node 结构，向上驱动就会停止。
快速测验: |
最左侧的向根驱动在到达根 |
答案: |
好分析！实际上，在 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 的注册商标。
其他公司、产品和服务名称可能是其他公司的商标或服务标记。