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_preempt_note_context_switch() 又从 rcu_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 将导致 splat，但未能 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 加速宽限期开始以来已更改时，这会触发从其->expmaskinitnext字段更新每个rcu_node结构的->expmaskinit字段。每个
rcu_node结构的->expmaskinit字段用于在每个 RCU 加速宽限期开始时初始化该结构的->expmask。这意味着只有至少在线一次的 CPU 才会被考虑用于给定的宽限期。任何离线的 CPU 都会清除其叶
rcu_node结构的->qsmaskinitnext字段中的位，因此可以安全地忽略任何该位已清除的 CPU。但是，当cpu_online返回false时，上线或离线的 CPU 可能会在一段时间内设置此位。对于 RCU 认为当前在线的每个非空闲 CPU，宽限期会调用
smp_call_function_single()。如果成功，则 CPU 完全在线。失败表示 CPU 正在上线或离线过程中，在这种情况下，需要等待一小段时间并重试。此等待（或一系列等待，视情况而定）的目的是允许并发的 CPU 热插拔操作完成。对于 RCU-sched，传出 CPU 的最后一个动作之一是调用
rcutree_report_cpu_dead()，这会报告该 CPU 的静止状态。但是，这可能是偏执引起的冗余。
快速问答: |
为什么所有人都围绕着跟踪曾经在线的 CPU 的多个计数器和掩码跳舞？为什么不只有一个跟踪当前在线 CPU 的掩码集并完成它？ |
答案: |
维护跟踪在线 CPU 的单个掩码集听起来更容易，至少在您尝试解决宽限期初始化和 CPU 热插拔操作之间的所有竞争条件之前。例如，假设初始化正在向下遍历树，而 CPU 离线操作正在向上遍历树。这种情况可能会导致树顶端设置的位在树底端没有对应项。这些位永远不会被清除，这将导致宽限期挂起。简而言之，这种方式会导致疯狂，更不用说许多错误、挂起和死锁。相比之下，当前的多掩码多计数器方案可确保宽限期初始化始终会在树的上下看到一致的掩码，这比单掩码方法带来了显着的简化。 这是 推迟工作以避免同步 的一个实例。在下一个宽限期开始时延迟记录 CPU 热插拔事件极大地简化了 |
加速宽限期优化¶
空闲 CPU 检查¶
每个加速宽限期在最初形成要 IPIed 的 CPU 掩码时以及在 IPIing 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 加速宽限期在构建必须 IPIed 的 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 字段的当前值为零，因此添加 3 并清除底部位会导致值为 2，这两个任务都会将其记录在其各自 rcu_node 结构的 ->exp_seq_rq 字段中
Task A 和 Task B 将向上移动到根 rcu_node 结构。假设 Task A 获胜，记录其所需的宽限期序列号，从而导致以下状态
Task A 现在前进以启动一个新的宽限期，而 Task B 向上移动到根 rcu_node 结构，并且看到其所需的序列号已记录，因此在 ->exp_wq[1] 上阻塞。
快速问答: |
为什么是 |
答案: |
否。回想一下，所需的序列号的底部位指示当前是否正在进行宽限期。因此，有必要将序列号向右移动一位以获取宽限期的编号。这会导致 |
如果 Task C 和 Task D 也在此处到达，它们将计算出相同的所需宽限期序列号，并看到两个叶 rcu_node 结构都已记录该值。因此，它们将在其各自 rcu_node 结构的 ->exp_wq[1] 字段上阻塞，如下所示
Task A 现在获取 rcu_state 结构的 ->exp_mutex 并启动宽限期，这会递增 ->expedited_sequence。因此，如果 Task E 和 Task F 到达，它们将计算出所需的序列号为 4，并将该值记录如下所示
Task E 和 Task 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 递增到值 3。如果新任务 G 和 H 到达并同时向上移动组合树，则状态将如下所示
请注意，根 rcu_node 结构的等待队列中现在有三个被占用。但是，在某个时候，Task A 会唤醒在 ->exp_wq 等待队列上阻塞的任务，从而导致以下状态
执行将继续，Task E 和 Task H 完成其宽限期并执行其唤醒。
快速问答: |
如果 Task A 花费太长时间进行唤醒，导致 Task E 的宽限期完成，会发生什么情况？ |
答案: |
然后，Task E 将在 |
工作队列的使用¶
在早期的实现中，请求加速宽限期的任务也驱动它完成。这种直接的方法的缺点是需要考虑发送给用户任务的 POSIX 信号，因此最近的实现使用 Linux 内核的工作队列（参见 工作队列）。
请求任务仍然进行计数器快照和漏斗锁定处理，但是到达漏斗锁定顶端的任务会执行 schedule_work()（来自 _synchronize_rcu_expedited()），以便工作队列 kthread 进行实际的宽限期处理。由于工作队列 kthread 不接受 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热插拔操作之间需要紧密同步。dyntick-idle计数器用于避免向空闲CPU发送IPI（进程间中断），至少在常见情况下是这样。RCU-preempt 和 RCU-sched 使用不同的 IPI 处理程序和不同的代码来响应这些处理程序执行的状态更改，但在其他方面使用通用代码。
静止状态使用 rcu_node 树进行跟踪，一旦报告了所有必要的静止状态，则会唤醒所有等待此加速宽限期的任务。使用一对互斥锁允许一个宽限期的唤醒与下一个宽限期的处理同时进行。
这种机制组合允许加速宽限期相当有效地运行。但是，对于非时间关键型任务，应使用正常的宽限期，因为它们的持续时间更长，可以实现更高的批处理程度，从而降低每个请求的开销。