翻译：kernel-5.10\Documentation\RCU\Design\Expedited-Grace-Periods\Expedited-Grace-Periods.rst
=================================================
TREE_RCU 加速宽限期
=================================================
介绍
============
本文档描述了 RCU 的加急宽限期。 与 RCU 的正常宽限期接受长延迟以实现高效率和最小干扰不同，加速宽限期接受较低的效率和显着的干扰以实现更短的延迟。
RCU 有两种风格（RCU-preempt 和 RCU-sched），早期的第三种 RCU-bh 风格已经根据其他两种实现。 这两个实现中的每一个都在其自己的部分中进行了介绍。
加速宽限期设计
=============================
不能指责加速的 RCU 宽限期是微妙的，因为它们出于所有意图和目的都会打击每个尚未为当前加速宽限期提供静止状态的 CPU。
一个可取之处是锤子随着时间的推移变小了一点：对 try_stop_cpus() 的旧调用已被一组对 smp_call_function_single() 的调用所取代，每个调用都会产生一个 IPI 到目标 CPU。
相应的处理函数检查 CPU 的状态，在可能的情况下激发更快的静止状态，并触发该静止状态的报告。
与 RCU 一样，一旦一切都处于静止状态一段时间，加速宽限期就结束了。
``smp_call_function_single()`` 处理程序操作的细节取决于 RCU 风格，如以下部分所述。
RCU-preempt 加速宽限期
===================================
``CONFIG_PREEMPT=y`` 内核实现 RCU 抢占。 RCU-preempt 加速宽限期处理给定 CPU 的总体流程如下图所示：
.. 内核图:: ExpRCUFlow.svg
实线箭头表示直接动作，例如函数调用。 虚线箭头表示间接动作，例如 IPI 或一段时间后达到的状态。
如果给定的 CPU 处于离线或空闲状态，``synchronize_rcu_expedited()`` 将忽略它，因为空闲和离线 CPU 已经处于静止状态。########### 否则，加速宽限期将使用 ``smp_call_function_single()``
向 CPU 发送一个 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_note_context_switch()``
调用下来的，后者又从调度程序调用 .
| **小测验**： |
+------------------------------------------------ ----------------------+
| 为什么不让加速宽限期检查所有 CPU 的状态？ 毕竟，这将避免所有那些实时不友好的 IPI。 |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 因为我们希望 RCU 读端临界区运行得快，这意味着没有内存障碍。 因此，无法从其他 CPU 安全地检查状态。 即使可以安全地检查状态，仍然有必要对 CPU 进行 IPI 以安全地与即将到来的
| rcu_read_unlock() 调用进行交互，这意味着远程状态测试无助于最坏的情况的实时应用程序关心的延迟。
| 防止您的实时应用程序受到这些 IPI 影响的一种方法是使用“CONFIG_NO_HZ_FULL=y”构建您的内核。 然后 RCU 会认为运行应用程序的 CPU 处于空闲状态，并且它能够安全地检测到该状态，而无需对
| CPU 进行 IPI。
请注意，这只是整体流程：由于 CPU 闲置或离线等原因，可能会出现额外的复杂情况。
RCU 安排的加速宽限期
----------------------------------
``CONFIG_PREEMPT=n`` 内核实现 RCU-sched。 RCU 调度的加速宽限期处理给定 CPU 的总体流程如下图所示：
.. 内核图:: ExpSchedFlow.svg
与 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 热插拔操作的交互比正常宽限期所需的交互更紧密。 此外，尝试对离线 CPU 进行 IPI 会导致 splats，但对在线 CPU 进行 IPI 失败会导致宽限期过短。
这两个选项在生产内核中都是不可接受的。
加速宽限期和 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_online 返回 false 时，CPU 上线
或下线可能会将此位设置一段时间。
#. 对于 RCU 认为当前在线的每个非空闲 CPU，宽限期调用“smp_call_function_single()”。 如果成功，则 CPU 完全在线。 Failure表示CPU正在上线或下线过程中，需要稍等片刻再试。 这
种等待（或一系列等待，视情况而定）的目的是允许并发 CPU 热插拔操作完成。
#. 在 RCU-sched 的情况下，传出 CPU 的最后一个动作是调用 ``rcu_report_dead()``，它报告该 CPU 的静止状态。 然而，这很可能是偏执狂引起的冗余。
| **小测验**： |
+------------------------------------------------ ----------------------+
| 为什么要用多个计数器和掩码跟踪曾经在线的 CPU？ 为什么不只使用一组掩码来跟踪当前在线的 CPU 并完成它呢？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 维护一组跟踪在线 CPU 的掩码*听起来*更容易，至少在您尝试解决宽限期初始化和 CPU 热插拔操作之间的所有竞争条件之前是这样。 例如，假设初始化在树下进行，而 CPU 离线操作在树上进行。
| 这种情况会导致在树的顶部设置的位在树的底部没有对应的位。 这些位永远不会被清除，这将导致宽限期挂起。 简而言之，这种方式很疯狂，更不用说大量的错误、挂起和死锁了。 相比之下，当前
| 的多掩码多计数器方案可确保宽限期初始化始终在树上下看到一致的掩码，这比单掩码方法带来了显着的简化。
|
| 这是“延迟工作以避免同步 <http://www.cs.columbia.edu/~library/TR-repository/reports/reports-1992/cucs-039-92.ps.gz>”的一个实例 __. 在下一个宽限期开始时延迟记录 CPU 热插拔事件大
| 大简化了 ``rcu_node`` 树中 CPU 跟踪位掩码的维护。
加速宽限期细化
----------------------------------
空闲 CPU 检查
~~~~~~~~~~~~~~~
每个加速宽限期在最初形成要进行 IPI 的 CPU 掩码时以及在对 CPU 进行 IPI 之前再次检查空闲 CPU（这两种检查均由 ``sync_rcu_exp_select_cpus()`` 执行）。 如果 CPU 在这两次之间的任何时
间处于空闲状态，则 CPU 将不会进行 IPI。 相反，将宽限期向前推进的任务将在传递给 rcu_report_exp_cpu_mult() 的掩码中包括空闲 CPU。
对于 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[]”数组的元素。
..内核图:: Funnel0.svg
下图显示了任务 A 和任务 B 分别到达最左边和最右边的叶子“rcu_node”结构后的情况。 ``rcu_state`` 结构的``->expedited_sequence`` 字段的当前值为零，因此加三并清除底部位的结果为值二，
这两个任务都记录在它们各自的 ``rcu_node`` 结构的``->exp_seq_rq`` 字段中：
..内核图:: Funnel1.svg
任务 A 和 B 中的每一个都将向上移动到根“rcu_node”结构。 假设任务 A 获胜，记录其所需的宽限期序列号并导致如下所示的状态：
..内核图:: Funnel2.svg
任务 A 现在开始启动一个新的宽限期，而任务 B 向上移动到根 ``rcu_node`` 结构，并且看到它所需的序列号已经被记录，阻塞在 ``->exp_wq[1]`` .
| **小测验**： |
+------------------------------------------------ ----------------------+
| 为什么是``->exp_wq[1]``？ 鉴于这些任务的所需序列号的值为 2，那么它们不应该阻塞在 ``->exp_wq[2]`` 上吗？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| No, 回想一下，所需序列号的底部位指示当前是否正在进行宽限期。 因此需要将序号右移一位，得到宽限期的序号。 这导致 `->exp_wq[1]``。
如果任务 C 和 D 也到达这一点，它们将计算相同的所需宽限期序列号，并看到两个叶 ``rcu_node`` 结构已经记录了该值。 因此，它们将阻塞各自的 ``rcu_node`` 结构的 ``->exp_wq[1]`` 字段，如下所示：
..内核图:: Funnel3.svg
任务 A 现在获取 ``rcu_state`` 结构的 ``->exp_mutex`` 并启动宽限期，这会增加 ``->expedited_sequence``。 因此，如果任务 E 和 F 到达，它们将计算所需的序列号 4 并将记录此值，如下所示：
..内核图:: Funnel4.svg
任务 E 和 F 将向上传播“rcu_node”组合树，任务 F 阻塞在根“rcu_node”结构上，任务 E 等待任务 A 完成，以便它可以开始下一个宽限期。 结果状态如下图：
..内核图:: Funnel5.svg
宽限期结束后，任务 A 开始唤醒等待此宽限期完成的任务，增加 ``->expedited_sequence``，获取 ``->exp_wake_mutex`` 然后释放 ``->exp_mutex` `。 这导致以下状态：
..内核图:: Funnel6.svg
任务 E 然后可以获取 ``->exp_mutex`` 并将 ``->expedited_sequence`` 增加到值三。 如果新任务 G 和 H 同时到达并向上移动组合树，则状态如下：
..内核图:: Funnel7.svg
请注意，三个根“rcu_node”结构的等待队列现在已被占用。 然而，在某些时候，任务 A 将唤醒阻塞在 ``->exp_wq`` 等待队列中的任务，导致以下状态：
..内核图:: Funnel8.svg
执行将继续，任务 E 和 H 完成它们的宽限期并执行它们的唤醒。
| **小测验**： |
+------------------------------------------------ ----------------------+
| 如果任务 A 的唤醒时间太长以至于任务 E 的宽限期结束，会发生什么情况？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 然后任务 E 将阻塞 ``->exp_wake_mutex``，这也将阻止它释放 ``->exp_mutex``，这反过来又将阻止下一个宽限期开始。 这最后一点对于防止 ``->exp_wq[]`` 数组溢出很重要。
工作队列的使用
~~~~~~~~~~~~~~~~~
在早期的实现中，请求加速宽限期的任务也促使它完成。 这种直接的方法的缺点是需要考虑发送给用户任务的 POSIX 信号，因此最近的实现使用 Linux 内核的“工作队列”
<https://www.kernel.org/doc/Documentation/core-api/workqueue.rst >`__。
请求任务仍然进行计数器快照和漏斗锁处理，但是到达漏斗锁顶部的任务执行 ``schedule_work()``（来自 ``_synchronize_rcu_expedited()`` 以便工作队列 kthread 执行实际的宽限期
-period 处理。因为工作队列 kthreads 不接受 POSIX 信号，grace-period-wait 处理不需要考虑 POSIX 信号。此外，这种方法允许前一个加速宽限期的唤醒与下一个加速宽限期的处理重
叠 . 因为只有四组等待队列，所以有必要确保前一个宽限期的唤醒在下一个宽限期的唤醒开始之前完成。这是通过让 ``->exp_mutex`` 守卫加速宽限期处理和 ``->exp_wake_mutex`` 守
卫唤醒。关键是 ``->exp_mutex`` 直到第一次唤醒完成后才被释放，这意味着 ``->exp_wake_mutex`` 已经在 那一点。 此方法可确保当前宽限期正在进行时可以执行上一个宽限期的唤醒，
但这些唤醒将在下一个宽限期开始之前完成。 这意味着只需要三个等待队列，保证提供的四个就足够了。
Stall警告
~~~~~~~~~~~~~~
当 RCU 读取器花费太长时间时，加快宽限期不会加快速度，因此加快宽限期会像正常宽限期一样检查停顿（Stall）。
+------------------------------------------------ ----------------------+
| **小测验**： |
+------------------------------------------------ ----------------------+
| 但是为什么不让正常的宽限期机制检测到停顿，因为给定的读者必须阻止正常和加速的宽限期？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 因为很可能在给定时间没有正在进行的正常宽限期，在这种情况下，正常宽限期无法发出stall警告。
``synchronize_sched_expedited_wait()`` 函数循环等待加速宽限期结束，但超时设置为当前 RCU CPU 停顿警告时间。 如果超过这个时间，任何阻塞当前宽限期的 CPU 或 ``rcu_node`` 结
构都会被打印出来。 每个stall警告都会导致循环再次通过，但第二次和后续通过使用更长的stall时间。
Mid-boot操作
~~~~~~~~~~~~~~~~~~
使用工作队列的优点是加速宽限期代码无需担心 POSIX 信号。 不幸的是，它有相应的缺点，即工作队列在初始化之前不能使用，而这在调度程序生成第一个任务后的某个时间才会发生。 鉴于
内核的某些部分确实希望在这个引导中期“死区”期间执行宽限期，加速宽限期必须在此期间做其他事情。
他们所做的是回到要求请求任务驱动加速宽限期的旧做法，就像使用工作队列之前的情况一样。 然而，请求任务只需要在引导中期死区期间驱动宽限期。 在中启动之前，同步宽限期是空操作。
中间启动后的某个时间，使用工作队列。
非加速非 SRCU 同步宽限期也必须在引导期间正常运行。 这是通过使非加速宽限期在启动期间采用加速代码路径来处理的。
当前的代码假设在启动死区期间没有 POSIX 信号。 但是，如果以某种方式出现对 POSIX 信号的压倒性需求，则可以对加速失速警告代码进行适当的调整。 其中一项调整是恢复工作队列前的停
顿警告检查，但仅限于启动过程中的死区。
通过这种改进，现在可以在内核生命周期中的几乎任何时候从任务上下文中使用同步宽限期。 也就是说，除了挂起、休眠或关闭代码路径中的某些点。
概括
~~~~~~~
加急宽限期使用序列号方法来促进批处理，因此单个宽限期操作可以处理大量请求。 漏斗锁用于有效地识别将请求宽限期的并发组中的一个任务。 该组的所有成员都将阻塞在 ``rcu_node`` 结构
中提供的等待队列上。 实际的宽限期处理是由工作队列执行的。
延迟记录 CPU 热插拔操作，以防止加速宽限期和 CPU 热插拔操作之间需要紧密同步。 dyntick-idle 计数器用于避免将 IPI 发送到空闲 CPU，至少在常见情况下是这样。 RCU-preempt 和
RCU-sched 使用不同的 IPI 处理程序和不同的代码来响应这些处理程序执行的状态更改，但在其他方面使用通用代码。
使用“rcu_node”树跟踪静止状态，一旦报告了所有必要的静止状态，所有等待这个加速宽限期的任务都会被唤醒。 一对互斥体用于允许一个宽限期的唤醒与下一个宽限期的处理同时进行。
这种机制的组合允许加速宽限期合理有效地运行。 然而，对于非时间关键任务，应该使用正常的宽限期，因为它们的持续时间更长，允许更高程度的批处理，因此每个请求的开销要低得多。
标签：RCU,加速,rcu,Expedited,exp,宽限期,rst,CPU From： https://www.cnblogs.com/hellokitty2/p/17000792.html