TREE_RCU 加速宽限期之旅¶
简介¶
本文档描述了 RCU 的加速宽限期。与 RCU 的正常宽限期不同，后者为了获得高效率和最小的干扰而接受较长的延迟，加速宽限期为了获得更短的延迟而接受较低的效率和显著的干扰。
RCU 有两种风格（RCU-preempt 和 RCU-sched），早期的第三种 RCU-bh 风格已通过其他两种风格实现。每种实现都在其各自的部分中进行介绍。
加速宽限期设计¶
加速 RCU 宽限期不能被指责为微妙，因为它们实际上会锤击每个尚未为当前加速宽限期提供静止状态的 CPU。唯一的好处是，随着时间的推移，锤子变得小了一点：旧的 try_stop_cpus() 调用已被一系列 smp_call_function_single() 调用所取代，每个调用都会导致向目标 CPU 发送 IPI。相应的处理函数检查 CPU 的状态，在可能的情况下促使更快的静止状态，并触发该静止状态的报告。与 RCU 一样，一旦所有内容都在静止状态下花费了一段时间，加速宽限期就完成了。
smp_call_function_single() 处理程序的操作细节取决于 RCU 的风格，如下节所述。
RCU-preempt 加速宽限期¶
CONFIG_PREEMPTION=y 内核实现 RCU-preempt。下图显示了 RCU-preempt 加速宽限期对给定 CPU 的处理的总体流程
实线箭头表示直接操作，例如函数调用。虚线箭头表示间接操作，例如，IPI 或一段时间后达到的状态。
如果给定的 CPU 处于离线或空闲状态，synchronize_rcu_expedited() 将忽略它，因为空闲和离线 CPU 已经处于静止状态。否则，加速宽限期将使用 smp_call_function_single() 向 CPU 发送 IPI，该 IPI 由 rcu_exp_handler() 处理。
但是，因为这是可抢占的 RCU，rcu_exp_handler() 可以检查 CPU 当前是否正在 RCU 读取侧临界区中运行。如果不是，则处理程序可以立即报告静止状态。否则，它会设置标志，以便最外层的 rcu_read_unlock() 调用将提供所需的静止状态报告。此标志设置避免了之前对所有可能具有 RCU 读取侧临界区的 CPU 的强制抢占。此外，此标志设置的目的是避免增加通过调度程序的常见快速路径的开销。
同样因为这是可抢占的 RCU，所以可以抢占 RCU 读取侧临界区。发生这种情况时，RCU 会将任务入队，直到它恢复并找到其最外层的 rcu_read_unlock() 时，才会继续阻止当前的加速宽限期。CPU 将在入队任务后立即报告静止状态，因为 CPU 不再阻止宽限期。相反，被抢占的任务正在进行阻止。rcu_preempt_ctxt_queue() 管理被阻止的任务列表，该函数从 rcu_preempt_note_context_switch() 调用，后者又从 rcu_note_context_switch() 调用，后者又从调度程序调用。
快速测试: |
为什么不让加速宽限期只检查所有 CPU 的状态？毕竟，这将避免所有那些对实时不利的 IPI。 |
答案: |
因为我们希望 RCU 读取侧临界区快速运行，这意味着没有内存屏障。因此，不可能安全地从其他 CPU 检查状态。即使可以安全地检查状态，仍然需要 IPI CPU 来安全地与即将到来的 防止您的实时应用程序受到这些 IPI 影响的一种方法是使用 |
请注意，这只是总体流程：由于与 CPU 进入空闲或离线状态的竞争，以及其他因素，可能会出现其他复杂情况。
RCU-sched 加速宽限期¶
CONFIG_PREEMPTION=n 内核实现 RCU-sched。下图显示了 RCU-sched 加速宽限期对给定 CPU 的处理的总体流程
与 RCU-preempt 一样，RCU-sched 的 synchronize_rcu_expedited() 会忽略离线和空闲 CPU，同样是因为它们处于远程可检测的静止状态。但是，由于 rcu_read_lock_sched() 和 rcu_read_unlock_sched() 没有留下其调用的痕迹，因此通常无法判断当前 CPU 是否处于 RCU 读取侧临界区。RCU-sched 的 rcu_exp_handler() 可以做的最好的事情是检查是否空闲，以防万一 CPU 在 IPI 传输过程中进入空闲状态。如果 CPU 处于空闲状态，则 rcu_exp_handler() 会报告静止状态。
否则，处理程序通过设置当前任务的线程标志和 CPU 抢占计数器的 NEED_RESCHED 标志来强制进行未来的上下文切换。在上下文切换时，CPU 会报告静止状态。如果 CPU 先离线，则它会在此时报告静止状态。
加速宽限期和 CPU 热插拔¶
加速宽限期的加速特性需要与 CPU 热插拔操作进行比正常宽限期更紧密的交互。此外，尝试 IPI 离线 CPU 会导致错误，但未能 IPI 在线 CPU 会导致宽限期过短。在生产内核中，这两种选择都不可接受。
加速宽限期和 CPU 热插拔操作之间的交互在多个级别上进行
曾经在线的 CPU 数量由
rcu_state结构的->ncpus字段跟踪。rcu_state结构的->ncpus_snap字段跟踪 RCU 加速宽限期开始时曾经在线的 CPU 数量。请注意，此数字永远不会减少，至少在没有时间机器的情况下。曾经在线的 CPU 的标识由
rcu_node结构的->expmaskinitnext字段跟踪。rcu_node结构的->expmaskinit字段跟踪在最近的 RCU 加速宽限期开始时至少在线一次的 CPU 的标识。rcu_state结构的->ncpus和->ncpus_snap字段用于检测何时首次有新的 CPU 上线，即当rcu_node结构的->expmaskinitnext字段自上次 RCU 加速宽限期开始以来发生更改时，这会触发每个rcu_node结构的->expmaskinit字段从其->expmaskinitnext字段进行更新。每个
rcu_node结构的->expmaskinit字段用于在每个 RCU 加速宽限期开始时初始化该结构的->expmask。这意味着只有至少在线一次的 CPU 才会被考虑用于给定的宽限期。任何离线的 CPU 都将清除其在叶
rcu_node结构的->qsmaskinitnext字段中的位，因此可以安全地忽略任何具有该位清除的 CPU。但是，对于上线或离线的 CPU 而言，当cpu_online返回false时，此位可能设置一段时间。对于 RCU 认为当前在线的每个非空闲 CPU，宽限期会调用
smp_call_function_single()。如果此调用成功，则表示 CPU 完全在线。如果失败，则表示 CPU 正在上线或下线过程中，此时需要等待一小段时间然后重试。此等待（或一系列等待，视情况而定）的目的是允许并发的 CPU 热插拔操作完成。对于 RCU-sched，即将离线的 CPU 的最后一个操作之一是调用
rcutree_report_cpu_dead()，该调用会报告该 CPU 的静止状态。然而，这很可能是出于偏执而产生的冗余操作。
快速测试: |
为什么要使用多个计数器和掩码来跟踪曾经在线的 CPU？为什么不只使用一组掩码来跟踪当前在线的 CPU 就完事了呢？ |
答案: |
维护一组跟踪在线 CPU 的掩码听起来更容易，至少在您尝试解决宽限期初始化和 CPU 热插拔操作之间的所有竞争条件之前是这样。例如，假设初始化在树中向下进行，而 CPU 下线操作在树中向上进行。这种情况可能导致树顶部的位被设置，而在树底部没有对应的位。这些位将永远不会被清除，这将导致宽限期挂起。简而言之，那样做会导致混乱，更不用说大量的错误、挂起和死锁。相比之下，当前的多掩码多计数器方案确保宽限期初始化始终可以看到树中上下一致的掩码，这比单掩码方法带来了显著的简化。 这是一个 为了避免同步而延迟工作 的例子。在下一个宽限期开始时惰性地记录 CPU 热插拔事件，大大简化了 |
加速宽限期改进¶
空闲 CPU 检查¶
每个加速宽限期在最初形成要进行 IPI 的 CPU 掩码时以及在 IPI CPU 之前都会检查空闲 CPU（这两个检查都由 sync_rcu_exp_select_cpus() 执行）。如果 CPU 在这两个时间之间的任何时间处于空闲状态，则不会 IPI 该 CPU。相反，将宽限期向前推进的任务会将空闲 CPU 包含在传递给 rcu_report_exp_cpu_mult() 的掩码中。
对于 RCU-sched，还有一个额外的检查：如果 IPI 中断了空闲循环，则 rcu_exp_handler() 会调用 rcu_report_exp_rdp() 来报告相应的静止状态。
对于 RCU-preempt，IPI 处理程序 (rcu_exp_handler()) 中没有针对空闲的特定检查，但由于不允许在空闲循环中进行 RCU 读取侧临界区，如果 rcu_exp_handler() 看到 CPU 处于 RCU 读取侧临界区内，则该 CPU 不可能处于空闲状态。否则，rcu_exp_handler() 会调用 rcu_report_exp_rdp() 来报告相应的静止状态，而不管该静止状态是否是由于 CPU 处于空闲状态导致的。
总而言之，RCU 加速宽限期在构建必须进行 IPI 的 CPU 的位掩码时、在发送每个 IPI 之前以及（显式或隐式地）在 IPI 处理程序中都会检查空闲状态。
通过序列计数器进行批处理¶
如果每个宽限期请求都单独执行，则加速宽限期将具有极差的可伸缩性和有问题的高负载特性。由于每个宽限期操作都可以服务于无限数量的更新，因此批处理请求非常重要，以便单个加速宽限期操作可以覆盖相应批次中的所有请求。
此批处理由 rcu_state 结构中名为 ->expedited_sequence 的序列计数器控制。当加速宽限期正在进行时，此计数器具有奇数值，否则具有偶数值，因此将计数器值除以 2 可以得到已完成的宽限期数。在任何给定的更新请求期间，计数器必须从偶数转换为奇数，然后再转换回偶数，从而表明一个宽限期已经过去。因此，如果计数器的初始值为 s，则更新程序必须等到计数器至少达到值 (s+3)&~0x1。此计数器由以下访问函数管理
rcu_exp_gp_seq_start()，它标记加速宽限期的开始。rcu_exp_gp_seq_end()，它标记加速宽限期的结束。rcu_exp_gp_seq_snap()，它获取计数器的快照。rcu_exp_gp_seq_done()，如果自上次调用rcu_exp_gp_seq_snap()以来已经过去了完整的加速宽限期，则返回true。
再次强调，给定批次中只有一个请求需要实际执行宽限期操作，这意味着必须有一种有效的方法来识别许多并发请求中的哪个请求将启动宽限期，并且剩余的请求必须有一种有效的方法来等待该宽限期完成。但是，这是下一节的主题。
漏斗锁和等待/唤醒¶
理清一批更新程序中哪个将启动加速宽限期的自然方法是使用 rcu_node 组合树，由 exp_funnel_lock() 函数实现。对应于给定宽限期的第一个到达给定 rcu_node 结构的更新程序会在 ->exp_seq_rq 字段中记录其所需的宽限期序列号，并移动到树中的下一层。否则，如果 ->exp_seq_rq 字段已包含所需宽限期的序列号或后续的序列号，则更新程序会使用从下数第二个和从下数第三个位作为索引，阻塞在 ->exp_wq[] 数组中的四个等待队列之一上。rcu_node 结构中的 ->exp_lock 字段同步对这些字段的访问。
下图显示了一个空的 rcu_node 树，其中白色单元格表示 ->exp_seq_rq 字段，红色单元格表示 ->exp_wq[] 数组的元素。
下图显示了 Task A 和 Task B 分别到达最左侧和最右侧的叶 rcu_node 结构后的情况。rcu_state 结构的 ->expedited_sequence 字段的当前值为零，因此加三并清除最低位后得到值二，这两个任务都会将其记录在其各自 rcu_node 结构的 ->exp_seq_rq 字段中
Task A 和 B 中的每一个都将移动到根 rcu_node 结构。假设 Task A 获胜，记录其所需的宽限期序列号，并导致出现如下所示的状态
Task A 现在开始启动新的宽限期，而 Task B 移动到根 rcu_node 结构，看到其所需的序列号已记录，则阻塞在 ->exp_wq[1] 上。
快速测试: |
为什么是 |
答案: |
不是的。回想一下，所需序列号的最低位表示当前是否有宽限期正在进行。因此，必须将序列号右移一位才能获得宽限期的编号。这导致 |
如果 Task C 和 D 也在此刻到达，它们将计算出相同的所需宽限期序列号，并看到两个叶 rcu_node 结构都已记录了该值。因此，它们将阻塞在其各自 rcu_node 结构的 ->exp_wq[1] 字段上，如下所示
Task A 现在获取 rcu_state 结构的 ->exp_mutex 并启动宽限期，这将递增 ->expedited_sequence。因此，如果 Task E 和 F 到达，它们将计算出所需的序列号为 4，并将此值记录如下所示
Task E 和 F 将在 rcu_node 组合树中向上传播，其中 Task F 阻塞在根 rcu_node 结构上，而 Task E 等待 Task A 完成以便它可以启动下一个宽限期。结果状态如下所示
宽限期完成后，Task A 开始唤醒等待此宽限期完成的任务，递增 ->expedited_sequence，获取 ->exp_wake_mutex，然后释放 ->exp_mutex。这导致以下状态
然后，Task E 可以获取 ->exp_mutex 并将 ->expedited_sequence 递增至值三。如果新任务 G 和 H 到达并同时在组合树中向上移动，则状态将如下所示
请注意，根 rcu_node 结构的三个等待队列现在被占用。但是，在某个时刻，任务 A 将会唤醒在 ->exp_wq 等待队列上阻塞的任务，从而导致以下状态
执行将继续，任务 E 和 H 完成它们的宽限期并执行唤醒操作。
快速测试: |
如果任务 A 花费太长时间进行唤醒操作，以至于任务 E 的宽限期完成，会发生什么？ |
答案: |
那么任务 E 将会阻塞在 |
工作队列的使用¶
在早期的实现中，请求加速宽限期的任务也将其驱动到完成。这种直接的方法的缺点是需要考虑发送给用户任务的 POSIX 信号，因此最近的实现使用了 Linux 内核的工作队列（请参阅工作队列）。
请求任务仍然执行计数器快照和漏斗锁处理，但是到达漏斗锁顶部的任务会执行 schedule_work()（来自 _synchronize_rcu_expedited()），以便工作队列内核线程执行实际的宽限期处理。由于工作队列内核线程不接受 POSIX 信号，因此宽限期等待处理无需考虑 POSIX 信号。此外，这种方法允许将上一个加速宽限期的唤醒与下一个加速宽限期的处理重叠。由于只有四组等待队列，因此必须确保在上一个宽限期的唤醒完成之后才能开始下一个宽限期的唤醒。这通过让 ->exp_mutex 保护加速宽限期处理和 ->exp_wake_mutex 保护唤醒来实现。关键点是 ->exp_mutex 直到第一个唤醒完成才会被释放，这意味着此时 ->exp_wake_mutex 已经被获取。这种方法确保可以在当前宽限期正在处理时执行上一个宽限期的唤醒，但是这些唤醒将在下一个宽限期开始之前完成。这意味着只需要三个等待队列，保证提供的四个队列足够。
停顿警告¶
当 RCU 读取器花费太长时间时，加速宽限期不会加快速度，因此加速宽限期会像正常的宽限期一样检查停顿。
快速测试: |
但是，考虑到给定的读取器必须同时阻塞正常宽限期和加速宽限期，为什么不让正常的宽限期机制检测停顿呢？ |
答案: |
因为在给定时间可能没有正在进行的正常宽限期，在这种情况下，正常宽限期无法发出停顿警告。 |
synchronize_sched_expedited_wait() 函数循环等待加速宽限期结束，但超时时间设置为当前 RCU CPU 停顿警告时间。如果超过此时间，则会打印阻塞当前宽限期的任何 CPU 或 rcu_node 结构。每个停顿警告都会导致循环中的另一次传递，但第二次和后续传递会使用更长的停顿时间。
启动中期操作¶
使用工作队列的优点是加速宽限期代码无需担心 POSIX 信号。不幸的是，它也有相应的缺点，即直到初始化后才能使用工作队列，而这在调度程序产生第一个任务后一段时间才会发生。鉴于内核的某些部分确实希望在此启动中期的“死区”执行宽限期，因此加速宽限期在此期间必须执行其他操作。
它们所做的就是恢复到旧的做法，即要求请求任务驱动加速宽限期，这在工作队列使用之前是这种情况。但是，仅在启动中期的死区期间才需要请求任务驱动宽限期。在启动中期之前，同步宽限期是空操作。启动中期后的一段时间，将使用工作队列。
非加速的非 SRCU 同步宽限期也必须在启动中期正常运行。这是通过使非加速宽限期在启动中期采用加速代码路径来处理的。
当前代码假设在启动中期的死区期间没有 POSIX 信号。但是，如果对 POSIX 信号的需求非常强烈，则可以对加速停顿警告代码进行适当的调整。一种这样的调整将恢复工作队列之前的停顿警告检查，但仅在启动中期的死区期间进行。
通过这种改进，现在几乎可以在内核生命周期的任何时候从任务上下文中使用同步宽限期。也就是说，除了挂起、休眠或关闭代码路径中的某些点之外。
总结¶
加速宽限期使用序列号方法来促进批处理，以便单个宽限期操作可以为多个请求提供服务。漏斗锁用于有效地识别并发组中将请求宽限期的一个任务。该组的所有成员都将阻塞在 rcu_node 结构中提供的等待队列上。实际的宽限期处理由工作队列执行。
CPU 热插拔操作会被延迟记录，以避免加速宽限期和 CPU 热插拔操作之间需要紧密的同步。动态滴答空闲计数器用于避免向空闲 CPU 发送 IPI，至少在常见情况下是这样。RCU-preempt 和 RCU-sched 使用不同的 IPI 处理程序和不同的代码来响应这些处理程序执行的状态更改，但在其他方面使用通用代码。
静止状态使用 rcu_node 树进行跟踪，一旦所有必需的静止状态都已报告，则会唤醒等待此加速宽限期的所有任务。一对互斥锁用于允许一个宽限期的唤醒与下一个宽限期的处理并发进行。
这种机制组合使得加速宽限期能够合理高效地运行。但是，对于非时间关键型任务，应使用正常的宽限期，因为它们的持续时间更长，允许更高的批处理程度，从而降低每次请求的开销。