TREE_RCU 数据结构导览 [LWN.net]¶

2016年12月18日

本文由 Paul E. McKenney 贡献

简介¶

本文档描述了 RCU 的主要数据结构及其相互关系。

数据结构关系¶

RCU 在所有意图和目的上都是一个大型状态机，其数据结构以允许 RCU 读取器极快地执行的方式维护状态，同时还以高效且极其可扩展的方式处理更新器请求的 RCU 宽限期。 RCU 更新器的效率和可扩展性主要由组合树提供，如下所示

此图显示了一个包含 rcu_node 结构树的封闭 rcu_state 结构。 rcu_node 树的每个叶节点最多有 16 个与之关联的 rcu_data 结构，因此有 NR_CPUS 个 rcu_data 结构，每个可能的 CPU 一个。如果需要，此结构在启动时会进行调整，以处理 nr_cpu_ids 远小于 NR_CPUs 的常见情况。例如，许多 Linux 发行版设置 NR_CPUs=4096，这会导致一个三级 rcu_node 树。如果实际硬件只有 16 个 CPU，则 RCU 将在启动时自行调整，从而得到一个只有一个节点的 rcu_node 树。

此组合树的目的是允许高效且可扩展地处理每个 CPU 的事件，例如静止状态、动态节拍空闲转换和 CPU 热插拔操作。静止状态由每个 CPU 的 rcu_data 结构记录，其他事件由叶级 rcu_node 结构记录。所有这些事件都会在树的每一层进行组合，直到最终在树的根 rcu_node 结构处完成宽限期。一旦每个 CPU（或者，在 CONFIG_PREEMPT_RCU 的情况下，任务）通过静止状态，就可以在根处完成宽限期。一旦宽限期完成，该事实的记录将传播回树中。

从图中可以看出，在 64 位系统上，具有 64 个叶子的两级树可以容纳 1,024 个 CPU，根部的扇出为 64，叶子的扇出为 16。

快速测验:

为什么叶子的扇出也不是 64？

答案:

因为影响叶级 rcu_node 结构的事件类型比树中更高层的事件类型更多。因此，如果叶 rcu_node 结构的扇出为 64，则在这些结构的 ->structures 上的争用变得过大。在各种系统上的实验表明，扇出 16 对于 rcu_node 树的叶子来说效果很好。

当然，使用数百或数千个 CPU 的进一步经验可能会表明，非叶 rcu_node 结构的扇出也必须减少。当且仅当证明有必要时，才能轻松进行这种减少。同时，如果您正在使用这样的系统并且在非叶 rcu_node 结构上遇到争用问题，则可以使用 CONFIG_RCU_FANOUT 内核配置参数根据需要减少非叶扇出。

为具有强大 NUMA 特征的系统构建的内核可能还需要调整 CONFIG_RCU_FANOUT，以便 rcu_node 结构的域与硬件边界对齐。但是，到目前为止还没有这种需要。

如果您的系统有超过 1,024 个 CPU（或者 32 位系统上有超过 512 个 CPU），则 RCU 将自动向树中添加更多层。例如，如果您疯狂到构建一个具有 65,536 个 CPU 的 64 位系统，RCU 会将 rcu_node 树配置如下

RCU 目前允许最多四级树，在 64 位系统上最多可容纳 4,194,304 个 CPU，但在 32 位系统上仅可容纳 524,288 个 CPU。另一方面，您可以将 CONFIG_RCU_FANOUT 和 CONFIG_RCU_FANOUT_LEAF 都设置为小至 2，这会导致使用 4 级树的 16 CPU 测试。这对于在小型测试机器上测试大型系统功能很有用。

这种多级组合树使我们能够获得分区的大部分性能和可扩展性优势，即使 RCU 宽限期检测本质上是全局操作。这里的诀窍是，只有最后一个报告静止状态到给定 rcu_node 结构的 CPU 才需要前进到树中上一级的 rcu_node 结构。这意味着在叶级 rcu_node 结构中，每十六次访问中只有一次会向上移动到树中。对于内部 rcu_node 结构，情况甚至更加极端：每六十四次访问中只有一次会向上移动到树中。因为绝大多数 CPU 不会向上移动到树中，所以锁争用在树中保持大致恒定。无论系统中存在多少 CPU，每个宽限期最多有 64 个静止状态报告会一直传递到根 rcu_node 结构，从而确保该根 rcu_node 结构上的锁争用保持在可接受的低水平。

实际上，组合树的作用就像一个大的减震器，无论系统上的负载水平如何，都能使锁争用保持在所有树级别的控制之下。

RCU 更新器通过注册 RCU 回调来等待正常宽限期，可以直接通过 call_rcu() 注册，也可以间接通过 synchronize_rcu() 及其友元函数注册。 RCU 回调由 rcu_head 结构表示，这些结构在等待宽限期过去时在 rcu_data 结构上排队，如下图所示

../../../_images/BigTreePreemptRCUBHdyntickCB.svg

此图显示了 TREE_RCU 和 PREEMPT_RCU 的主要数据结构是如何相关的。较小的数据结构将随着使用它们的算法一起引入。

请注意，上面图中的每个数据结构都有自己的同步

每个 rcu_state 结构都有一个锁和一个互斥锁，并且一些字段受到相应根 rcu_node 结构的锁的保护。
每个 rcu_node 结构都有一个自旋锁。
rcu_data 中的字段是相应 CPU 的私有字段，尽管其他 CPU 可以读取和写入其中的一些字段。

重要的是要注意，不同的数据结构可能对任何给定时间的 RCU 状态有非常不同的想法。举一个例子，对给定 RCU 宽限期的开始或结束的认识会缓慢地传播到数据结构中。这种缓慢的传播对于 RCU 具有良好的读取端性能是绝对必要的。如果这种巴尔干化的实现对您来说似乎很陌生，那么一个有用的技巧是将这些数据结构的每个实例都视为一个不同的人，每个人都对现实有通常略有不同的看法。

每个数据结构的一般作用如下

rcu_state：此结构构成 rcu_node 和 rcu_data 结构之间的互连，跟踪宽限期，充当 CPU 热插拔事件孤立的回调的短期存储库，维护 rcu_barrier() 状态，跟踪加速宽限期状态，并维护用于在宽限期延长太长时间时强制静止状态的状态，
rcu_node：此结构形成一个组合树，该树将静止状态信息从叶子传播到根，并将宽限期信息从根传播到叶子。它提供宽限期状态的本地副本，以便以同步方式访问此信息，而不会受到全局锁定原本会带来的可扩展性限制。在 CONFIG_PREEMPT_RCU 内核中，它管理在其当前 RCU 读取端临界区中被阻止的任务列表。在具有 CONFIG_RCU_BOOST 的 CONFIG_PREEMPT_RCU 中，它管理每个 rcu_node 的优先级提升内核线程 (kthread) 和状态。最后，它记录 CPU 热插拔状态，以便确定在给定的宽限期内应忽略哪些 CPU。
rcu_data：此每个 CPU 结构是静止状态检测和 RCU 回调排队的重点。它还会跟踪其与相应叶 rcu_node 结构的关系，以便更有效地将静止状态向上传播到 rcu_node 组合树中。与 rcu_node 结构一样，它提供宽限期信息的本地副本，以便从相应 CPU 免费同步访问此信息。最后，此结构记录相应 CPU 的过去动态节拍空闲状态，并跟踪统计信息。
rcu_head：此结构表示 RCU 回调，并且是唯一由 RCU 用户分配和管理的结构。 rcu_head 结构通常嵌入在 RCU 保护的数据结构中。

如果您从此文章中想要获得的是对 RCU 的数据结构如何相关的一般概念，那么您已经完成了。否则，以下每个部分都提供了有关 rcu_state、rcu_node 和 rcu_data 数据结构的更多详细信息。

`rcu_state` 结构¶

rcu_state 结构是表示系统中 RCU 状态的基础结构。此结构构成 rcu_node 和 rcu_data 结构之间的互连，跟踪宽限期，包含用于与 CPU 热插拔事件同步的锁，并维护用于在宽限期延长太长时间时强制静止状态的状态，

rcu_state 结构的几个字段在以下部分中单独和成组地进行讨论。更专业的字段将在讨论其用途时进行介绍。

与 rcu_node 和 rcu_data 结构的关系¶

rcu_state 结构的这一部分声明如下

 struct rcu_node node[NUM_RCU_NODES];
 struct rcu_node *level[NUM_RCU_LVLS + 1];
 struct rcu_data __percpu *rda;

快速测验:

等一下！您说 rcu_node 结构形成一棵树，但它们被声明为一个扁平数组！怎么回事？

答案:

这棵树在数组中展开。数组中的第一个节点是头节点，数组中的下一组节点是头节点的子节点，依此类推，直到数组中的最后一组节点是叶节点。请参见以下图表以了解其工作原理。

rcu_node 树嵌入到 ->node[] 数组中，如下图所示

此映射的一个有趣的后果是，树的广度优先遍历实现为数组的简单线性扫描，这实际上是 rcu_for_each_node_breadth_first() 宏的作用。此宏在宽限期的开始和结束时使用。

->level 数组的每个条目都引用树的相应级别上的第一个 rcu_node 结构，例如，如下图所示

数组的第零个元素引用根 rcu_node 结构，第一个元素引用根 rcu_node 的第一个子节点，最后第二个元素引用第一个叶 rcu_node 结构。

无论其价值如何，如果您将树绘制成树形而不是数组形，则很容易绘制平面表示

最后，->rda 字段引用每个 CPU 指向相应 CPU 的 rcu_data 结构的指针。

一旦初始化完成，所有这些字段都是常量，因此不需要任何保护。

宽限期跟踪¶

rcu_state 结构的这一部分声明如下

1   unsigned long gp_seq;

RCU 宽限期已编号，并且 ->gp_seq 字段包含当前宽限期序列号。底部的两个位是当前宽限期的状态，对于尚未启动的状态为零，对于正在进行的状态为一。换句话说，如果 ->gp_seq 的底部两位为零，则 RCU 处于空闲状态。底部两位中的任何其他值都表示某些东西已损坏。此字段由根 rcu_node 结构的 ->lock 字段保护。

rcu_node 和 rcu_data 结构中也有 ->gp_seq 字段。 rcu_state 结构中的字段表示最当前的值，并且对其他结构的字段进行比较，以便以分布式方式检测宽限期的开始和结束。这些值从 rcu_state 流向 rcu_node（从根向下到叶子）到 rcu_data。

杂项¶

rcu_state 结构的这一部分声明如下

 unsigned long gp_max;
 char abbr;
 char *name;

->gp_max 字段以节拍数跟踪最长宽限期的持续时间。它由根 rcu_node 的 ->lock 保护。

->name 和 ->abbr 字段区分可抢占 RCU（“rcu_preempt”和“p”）和不可抢占 RCU（“rcu_sched”和“s”）。这些字段用于诊断和跟踪目的。

`rcu_node` 结构¶

rcu_node 结构形成一个组合树，该树将静止状态信息从叶子传播到根，并将宽限期信息从根向下传播到叶子。它们提供宽限期状态的本地副本，以便以同步方式访问此信息，而不会受到全局锁定原本会带来的可扩展性限制。在 CONFIG_PREEMPT_RCU 内核中，它们管理在其当前 RCU 读取端临界区中被阻止的任务列表。在具有 CONFIG_RCU_BOOST 的 CONFIG_PREEMPT_RCU 中，它们管理每个 rcu_node 的优先级提升内核线程 (kthread) 和状态。最后，它们记录 CPU 热插拔状态，以便确定在给定的宽限期内应忽略哪些 CPU。

rcu_node 结构的字段将在以下部分中单独和成组地进行讨论。

连接到组合树¶

rcu_node 结构的这一部分声明如下

 struct rcu_node *parent;
 u8 level;
 u8 grpnum;
 unsigned long grpmask;
 int grplo;
 int grphi;

->parent 指针引用树中高一级的 rcu_node，对于根 rcu_node，该指针为 NULL。 RCU 实现大量使用此字段来将静止状态向上推送到树中。 ->level 字段给出树中的级别，根位于级别零，其子节点位于级别一，依此类推。 ->grpnum 字段给出此节点在其父节点的子节点中的位置，因此此数字在 32 位系统上介于 0 和 31 之间，在 64 位系统上介于 0 和 63 之间。 ->level 和 ->grpnum 字段仅在初始化和跟踪期间使用。 ->grpmask 字段是 ->grpnum 的位掩码对应项，因此始终只有一个位设置。此掩码用于清除此 rcu_node 结构在其父节点的位掩码中的对应位，稍后将对此进行描述。最后，->grplo 和 ->grphi 字段分别包含此 rcu_node 结构服务的最低编号和最高编号 CPU。

所有这些字段都是常量，因此不需要任何同步。

同步¶

rcu_node 结构的此字段声明如下

1   raw_spinlock_t lock;

此字段用于保护此结构中的其余字段，除非另有说明。也就是说，此结构中的所有字段都可以在没有锁定的情况下访问以进行跟踪。是的，这可能会导致令人困惑的跟踪，但与其因为黑森堡虫而消失，不如一些跟踪混乱。

宽限期跟踪¶

rcu_node 结构的这一部分声明如下

1   unsigned long gp_seq;
2   unsigned long gp_seq_needed;

rcu_node 结构的 ->gp_seq 字段是 rcu_state 结构中同名字段的对应项。它们每个都可能最多落后于其 rcu_state 对应项一步。如果给定 rcu_node 结构的 ->gp_seq 字段的底部两位为零，则此 rcu_node 结构认为 RCU 处于空闲状态。

每个 rcu_node 结构的 >gp_seq 字段在每个宽限期的开始和结束时更新。

->gp_seq_needed 字段记录了相应 rcu_node 结构看到的未来最远的宽限期请求。当 ->gp_seq 字段的值等于或超过 ->gp_seq_needed 字段的值时，该请求被视为已满足。

快速测验:

假设此 rcu_node 结构很长时间没有看到请求。 ->gp_seq 字段的包装不会导致问题吗？

答案:

不会，因为如果 ->gp_seq_needed 字段落后于 ->gp_seq 字段，则 ->gp_seq_needed 字段将在宽限期结束时更新。因此，即使有包装，模算术比较也将始终获得正确的答案。

静止状态跟踪¶

这些字段管理静止状态在组合树中的传播。

rcu_node 结构的这一部分具有以下字段

 unsigned long qsmask;
 unsigned long expmask;
 unsigned long qsmaskinit;
 unsigned long expmaskinit;

->qsmask 字段跟踪此 rcu_node 结构的哪些子节点仍需要报告当前正常宽限期的静止状态。这样的子节点将在其对应位中具有值 1。请注意，叶 rcu_node 结构应被认为具有 rcu_data 结构作为其子节点。类似地，->expmask 字段跟踪此 rcu_node 结构的哪些子节点仍需要报告当前加速宽限期的静止状态。加速宽限期具有与正常宽限期相同的概念属性，但加速实现接受极端的 CPU 开销以获得低得多的宽限期延迟，例如，消耗几百微秒的 CPU 时间以将宽限期持续时间从毫秒减少到几十微秒。 ->qsmaskinit 字段跟踪此 rcu_node 结构的哪些子节点至少覆盖一个在线 CPU。此掩码用于初始化 ->qsmask，->expmaskinit 用于分别初始化 ->expmask 和正常宽限期和加速宽限期的开始。

快速测验:

为什么这些位掩码受到锁定的保护？来吧，您没听说过原子指令吗？？？

答案:

无锁宽限期计算！如此诱人的可能性！但请考虑以下事件序列

CPU 0 在动态节拍空闲模式下已有一段时间。当它醒来时，它注意到当前的 RCU 宽限期需要它报告，因此它设置了一个标志，调度时钟中断将在其中找到它。
同时，CPU 1 正在运行 force_quiescent_state()，并注意到 CPU 0 一直处于动态节拍空闲模式，这符合扩展静止状态的条件。
CPU 0 的调度时钟中断在 RCU 读取端临界区的中间触发，并注意到 RCU 核心需要一些东西，因此开始 RCU 软中断处理。
CPU 0 的软中断处理程序执行，并且几乎准备好将其静止状态报告给 rcu_node 树。
但是 CPU 1 抢先一步，完成了当前的宽限期并开始了新的宽限期。
CPU 0 现在报告其错误宽限期的静止状态。该宽限期现在可能在 RCU 读取端临界区之前结束。如果发生这种情况，将发生灾难。

因此，绝对需要锁定才能协调位清除与 ->gp_seq 中宽限期序列号的更新。

阻止任务管理¶

PREEMPT_RCU 允许任务在其 RCU 读取端临界区中被抢占，并且必须显式跟踪这些任务。准确地说，为什么以及如何跟踪它们的详细信息将在另一篇关于 RCU 读取端处理的文章中介绍。现在，足以知道 rcu_node 结构跟踪它们。

 struct list_head blkd_tasks;
 struct list_head *gp_tasks;
 struct list_head *exp_tasks;
 bool wait_blkd_tasks;

->blkd_tasks 字段是被阻止和被抢占任务的列表的列表头。当任务在 RCU 读取端临界区中进行上下文切换时，它们的 task_struct 结构（通过 task_struct 的 ->rcu_node_entry 字段）排队到与传出上下文切换执行的 CPU 对应的叶 rcu_node 结构的 ->blkd_tasks 列表的头部。当这些任务稍后退出其 RCU 读取端临界区时，它们会从列表中删除自己。因此，此列表按反时间顺序排列，因此，如果其中一个任务正在阻止当前的宽限期，则所有后续任务也必须阻止相同的宽限期。因此，指向此列表的单个指针足以跟踪阻止给定宽限期的所有任务。该指针存储在正常宽限期的 ->gp_tasks 中，存储在加速宽限期的 ->exp_tasks 中。如果没有正在进行的宽限期，或者没有阻止任务阻止该宽限期完成，则最后两个字段为 NULL。如果这两个指针中的任何一个引用从 ->blkd_tasks 列表中删除自己的任务，则该任务必须将指针前进到列表中的下一个任务，或者如果没有列表中的后续任务，则将指针设置为 NULL。

例如，假设任务 T1、T2 和 T3 都硬关联到系统中编号最大的 CPU。然后，如果任务 T1 在 RCU 读取端临界区中被阻止，则加速宽限期开始，然后任务 T2 在 RCU 读取端临界区中被阻止，然后正常宽限期开始，最后任务 3 在 RCU 读取端临界区中被阻止，则最后一个叶 rcu_node 结构的阻止任务列表的状态将如下所示

任务 T1 正在阻止两个宽限期，任务 T2 仅阻止正常宽限期，任务 T3 不阻止任何宽限期。请注意，这些任务不会在恢复执行后立即从列表中删除自己。相反，它们将保留在列表中，直到它们执行结束其 RCU 读取端临界区的最外层 rcu_read_unlock()。

->wait_blkd_tasks 字段指示当前宽限期是否正在等待被阻止的任务。

调整 `rcu_node` 数组的大小¶

rcu_node 数组的大小通过一系列 C 预处理器表达式来调整，如下所示

#ifdef CONFIG_RCU_FANOUT
#define RCU_FANOUT CONFIG_RCU_FANOUT
#else
# ifdef CONFIG_64BIT
# define RCU_FANOUT 64
# else
# define RCU_FANOUT 32
# endif
#endif
10
#ifdef CONFIG_RCU_FANOUT_LEAF
#define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
#else
# ifdef CONFIG_64BIT
# define RCU_FANOUT_LEAF 64
# else
# define RCU_FANOUT_LEAF 32
# endif
#endif
20
#define RCU_FANOUT_1        (RCU_FANOUT_LEAF)
#define RCU_FANOUT_2        (RCU_FANOUT_1 * RCU_FANOUT)
#define RCU_FANOUT_3        (RCU_FANOUT_2 * RCU_FANOUT)
#define RCU_FANOUT_4        (RCU_FANOUT_3 * RCU_FANOUT)
25
#if NR_CPUS <= RCU_FANOUT_1
#  define RCU_NUM_LVLS        1
#  define NUM_RCU_LVL_0        1
#  define NUM_RCU_NODES        NUM_RCU_LVL_0
#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0 }
#  define RCU_NODE_NAME_INIT  { "rcu_node_0" }
#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0" }
#  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0" }
#elif NR_CPUS <= RCU_FANOUT_2
#  define RCU_NUM_LVLS        2
#  define NUM_RCU_LVL_0        1
#  define NUM_RCU_LVL_1        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
#  define NUM_RCU_NODES        (NUM_RCU_LVL_0 + NUM_RCU_LVL_1)
#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
#  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1" }
#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1" }
#  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0", "rcu_node_exp_1" }
#elif NR_CPUS <= RCU_FANOUT_3
#  define RCU_NUM_LVLS        3
#  define NUM_RCU_LVL_0        1
#  define NUM_RCU_LVL_1        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
#  define NUM_RCU_LVL_2        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
#  define NUM_RCU_NODES        (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2)
#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
#  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2" }
#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" }
#  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2" }
#elif NR_CPUS <= RCU_FANOUT_4
#  define RCU_NUM_LVLS        4
#  define NUM_RCU_LVL_0        1
#  define NUM_RCU_LVL_1        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
#  define NUM_RCU_LVL_2        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
#  define NUM_RCU_LVL_3        DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
#  define NUM_RCU_NODES        (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
#  define NUM_RCU_LVL_INIT    { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
#  define RCU_NODE_NAME_INIT  { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" }
#  define RCU_FQS_NAME_INIT   { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
#  define RCU_EXP_NAME_INIT   { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2", "rcu_node_exp_3" }
#else
# error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
#endif

rcu_node 结构中的最大级别数当前限制为四个，如第 21-24 行和后续“if”语句的结构所指定。对于 32 位系统，这允许 16*32*32*32=524,288 个 CPU，这至少应该足够未来几年使用。对于 64 位系统，允许 16*64*64*64=4,194,304 个 CPU，这应该足以让我们度过未来十年左右的时间。这个四级树还允许使用 CONFIG_RCU_FANOUT=8 构建的内核最多支持 4096 个 CPU，这在每个插槽有八个 CPU 的非常大的系统中可能很有用（但请注意，还没有人显示由于未对齐的插槽和 rcu_node 边界而导致的任何可测量的性能下降）。此外，使用完整的四级 rcu_node 树构建内核允许更好地测试 RCU 的组合树代码。

RCU_FANOUT 符号控制在 rcu_node 树的每个非叶级别允许的子节点数。如果未指定 CONFIG_RCU_FANOUT Kconfig 选项，则会根据系统的字长来设置，这也是 Kconfig 的默认值。

RCU_FANOUT_LEAF 符号控制每个叶 rcu_node 结构处理的 CPU 数量。经验表明，允许给定的叶 rcu_node 结构处理 64 个 CPU（正如 64 位系统上 ->qsmask 字段中的位数所允许的那样），会导致叶 rcu_node 结构的 ->lock 字段过度争用。因此，在 CONFIG_RCU_FANOUT_LEAF 的默认值下，每个叶 rcu_node 结构的 CPU 数量限制为 16。如果未指定 CONFIG_RCU_FANOUT_LEAF，则选择的值基于系统的字长，就像 CONFIG_RCU_FANOUT 一样。第 11-19 行执行此计算。

第 21-24 行计算单级（包含单个 rcu_node 结构）、两级、三级和四级 rcu_node 树分别支持的最大 CPU 数量，给定由 RCU_FANOUT 和 RCU_FANOUT_LEAF 指定的扇出。这些 CPU 数量分别保留在 RCU_FANOUT_1、 RCU_FANOUT_2、 RCU_FANOUT_3 和 RCU_FANOUT_4 C 预处理器变量中。

这些变量用于控制 C 预处理器 #if 语句（跨越第 26-66 行），该语句计算树的每一级所需的 rcu_node 结构的數量，以及所需的级别数。级别数放置在第 27、35、44 和 54 行的 NUM_RCU_LVLS C 预处理器变量中。树顶层级的 rcu_node 结构的数量始终只有一个，并且此值由第 28、36、45 和 55 行无条件地放置到 NUM_RCU_LVL_0 中。 rcu_node 树的其余级别（如果有）通过将 CPU 的最大数量除以从当前级别向下支持的级别数的扇出，并向上舍入来计算。此计算由第 37、46-47 和 56-58 行执行。第 31-33、40-42、50-52 和 62-63 行为 lockdep 锁类名称创建初始化程序。最后，如果 CPU 的最大数量对于指定的扇出而言太大，则第 64-66 行会产生错误。

`rcu_segcblist` 结构 ¶

rcu_segcblist 结构维护一个分段的回调列表，如下所示

#define RCU_DONE_TAIL        0
#define RCU_WAIT_TAIL        1
#define RCU_NEXT_READY_TAIL  2
#define RCU_NEXT_TAIL        3
#define RCU_CBLIST_NSEGS     4
 6
struct rcu_segcblist {
 struct rcu_head *head;
 struct rcu_head **tails[RCU_CBLIST_NSEGS];
 unsigned long gp_seq[RCU_CBLIST_NSEGS];
 long len;
 long len_lazy;
};

段如下

RCU_DONE_TAIL: 宽限期已过的回调。这些回调已准备好被调用。
RCU_WAIT_TAIL: 等待当前宽限期的回调。请注意，不同的 CPU 可能对哪个宽限期是当前的宽限期有不同的想法，因此有 ->gp_seq 字段。
RCU_NEXT_READY_TAIL: 等待下一个宽限期开始的回调。
RCU_NEXT_TAIL: 尚未与宽限期关联的回调。

->head 指针引用第一个回调，如果列表不包含回调，则为 NULL （这与空 not 相同）。 ->tails[] 数组的每个元素都引用列表中相应段的最后一个回调的 ->next 指针，如果该段和所有先前的段都为空，则引用列表的 ->head 指针。如果相应的段为空但某些先前的段不为空，则数组元素与其前身相同。较旧的回调更靠近列表的头部，新的回调添加到尾部。 ->head 指针， ->tails[] 数组和回调之间的这种关系显示在此图中

在此图中， ->head 指针引用列表中的第一个 RCU 回调。 ->tails[RCU_DONE_TAIL] 数组元素引用 ->head 指针本身，表明没有回调已准备好调用。 ->tails[RCU_WAIT_TAIL] 数组元素引用回调 CB 2 的 ->next 指针，表明 CB 1 和 CB 2 都在等待当前的宽限期，并且可能对哪个宽限期是当前的宽限期存在可能的异议。 ->tails[RCU_NEXT_READY_TAIL] 数组元素引用与 ->tails[RCU_WAIT_TAIL] 相同的 RCU 回调，表明没有回调在等待下一个 RCU 宽限期。 ->tails[RCU_NEXT_TAIL] 数组元素引用 CB 4 的 ->next 指针，表明所有剩余的 RCU 回调尚未分配给 RCU 宽限期。请注意， ->tails[RCU_NEXT_TAIL] 数组元素始终引用最后一个 RCU 回调的 ->next 指针，除非回调列表为空，在这种情况下，它引用 ->head 指针。

->tails[RCU_NEXT_TAIL] 数组元素还有一个重要的特殊情况：当此列表 disabled 时，它可以为 NULL 。当相应的 CPU 离线或相应的 CPU 的回调被卸载到 kthread 时，列表将被禁用，这两者都在其他地方描述。

随着宽限期的推进，CPU 将其回调从 RCU_NEXT_TAIL 推进到 RCU_NEXT_READY_TAIL 到 RCU_WAIT_TAIL 到 RCU_DONE_TAIL 列表段。

->gp_seq[] 数组记录与列表段对应的宽限期编号。这就是允许不同的 CPU 对哪个是当前的宽限期有不同的想法，同时仍然避免过早调用它们的回调。特别是，这允许空闲时间过长的 CPU 确定在重新唤醒后哪些回调已准备好被调用。

->len 计数器包含 ->head 中的回调数， ->len_lazy 包含已知仅释放内存的回调数，并且可以安全地延迟其调用。

重要

正是 ->len 字段决定了是否有关联到此 rcu_segcblist 结构的回调， not ->head 指针。原因是所有准备好调用的回调（即 RCU_DONE_TAIL 段中的回调）都会在回调调用时间 (rcu_do_batch) 一次性提取出来，因此，如果没有 rcu_segcblist 中剩余的未完成回调，则 ->head 可能会设置为 NULL。如果必须推迟回调调用，例如，因为一个高优先级进程刚刚在此 CPU 上唤醒，则剩余的回调会放回 RCU_DONE_TAIL 段，并且 ->head 再次指向该段的开头。简而言之，即使 CPU 一直存在回调，head 字段也可能短暂地为 NULL 。因此，测试 ->head 指针是否为 NULL 是不合适的。

相比之下，只有在调用了相应的回调后，才会调整 ->len 和 ->len_lazy 计数。这意味着只有当 rcu_segcblist 结构确实没有回调时， ->len 计数才为零。当然，对 ->len 计数的异 CPU 采样需要仔细使用适当的同步，例如内存屏障。这种同步可能有点微妙，特别是在 rcu_barrier() 的情况下。

`rcu_data` 结构 ¶

rcu_data 维护 RCU 子系统的每个 CPU 状态。除非另有说明，否则此结构中的字段只能从相应的 CPU （和从跟踪）访问。此结构是静止状态检测和 RCU 回调排队的重点。它还跟踪其与相应的叶 rcu_node 结构的关系，以允许更有效地将静止状态传播到 rcu_node 组合树。与 rcu_node 结构一样，它提供了宽限期信息的本地副本，以允许从相应的 CPU 免费同步访问此信息。最后，此结构记录了相应 CPU 的过去 dyntick-idle 状态，并跟踪统计信息。

rcu_data 结构的字段将在以下各节中单独或分组讨论。

与其他数据结构的连接 ¶

rcu_data 结构的这一部分声明如下

 int cpu;
 struct rcu_node *mynode;
 unsigned long grpmask;
 bool beenonline;

->cpu 字段包含相应 CPU 的编号， ->mynode 字段引用相应的 rcu_node 结构。 ->mynode 用于将静止状态传播到组合树。这两个字段是常量，因此不需要同步。

->grpmask 字段指示 ->mynode->qsmask 中对应于此 rcu_data 结构的位，并且在传播静止状态时也使用。每当相应的 CPU 上线时，就会设置 ->beenonline 标志，这意味着 debugfs 跟踪不需要转储任何未设置此标志的 rcu_data 结构。

静止状态和宽限期跟踪 ¶

rcu_data 结构的这一部分声明如下

 unsigned long gp_seq;
 unsigned long gp_seq_needed;
 bool cpu_no_qs;
 bool core_needs_qs;
 bool gpwrap;

->gp_seq 字段与 rcu_state 和 rcu_node 结构中同名字段的对应字段相同。 ->gp_seq_needed 字段是 rcu_node 结构中同名字段的对应字段。它们中的每一个最多可以比它们的 rcu_node 对应字段滞后一个，但在 CONFIG_NO_HZ_IDLE 和 CONFIG_NO_HZ_FULL 内核中，处于 dyntick-idle 模式的 CPU 的滞后程度可能任意大（但这些计数器会在退出 dyntick-idle 模式后赶上）。如果给定 rcu_data 结构的 ->gp_seq 的低两位为零，则此 rcu_data 结构认为 RCU 处于空闲状态。

快速测验:

所有这些宽限期编号的复制只会导致巨大的混乱。为什么不只保留一个全局序列号并完成它???

答案:

因为如果只有一个全局序列号，则需要一个全局锁来安全地访问和更新它。如果我们不打算使用单个全局锁，我们需要小心地按节点管理这些数字。回想一下先前快速测验的答案，将先前采样的静止状态应用于错误的宽限期的后果非常严重。

->cpu_no_qs 标志指示 CPU 尚未通过静止状态，而 ->core_needs_qs 标志指示 RCU 核心需要来自相应 CPU 的静止状态。 ->gpwrap 字段指示相应的 CPU 已保持空闲状态很长时间，以至于 gp_seq 计数器有溢出的危险，这将导致 CPU 在下次退出空闲状态时忽略其计数器的值。

RCU 回调处理 ¶

在没有 CPU 热插拔事件的情况下，RCU 回调由注册它们的同一 CPU 调用。这严格来说是一种缓存局部性优化：回调可以在注册它们的 CPU 以外的 CPU 上调用，并且确实会发生这种情况。毕竟，如果注册给定回调的 CPU 在回调可以被调用之前已经离线，那么实际上没有其他选择。

rcu_data 结构的这一部分声明如下

struct rcu_segcblist cblist;
long qlen_last_fqs_check;
unsigned long n_cbs_invoked;
unsigned long n_nocbs_invoked;
unsigned long n_cbs_orphaned;
unsigned long n_cbs_adopted;
unsigned long n_force_qs_snap;
long blimit;

->cblist 结构是前面描述的分段回调列表。每当 CPU 注意到另一个 RCU 宽限期已完成时，它就会推进其 rcu_data 结构中的回调。 CPU 通过注意到其 rcu_data 结构的 ->gp_seq 字段的值与其叶 rcu_node 结构的值不同来检测 RCU 宽限期的完成。回想一下，每个 rcu_node 结构的 ->gp_seq 字段在每个宽限期的开始和结束时都会更新。

当回调列表变得过长时， ->qlen_last_fqs_check 和 ->n_force_qs_snap 协调从 call_rcu() 及其友元强制静止状态。

->n_cbs_invoked, ->n_cbs_orphaned 和 ->n_cbs_adopted 字段分别计算回调的调用次数、在此 CPU 离线时发送到其他 CPU 的回调数，以及在其他 CPU 离线时从其他 CPU 接收的回调数。当 CPU 的回调被卸载到 kthread 时，使用 ->n_nocbs_invoked 。

最后， ->blimit 计数器是给定时间可以调用的 RCU 回调的最大数量。

Dyntick-Idle 处理 ¶

rcu_data 结构的这一部分声明如下

1   int watching_snap;
2   unsigned long dynticks_fqs;

->watching_snap 字段用于在强制静止状态时获取相应 CPU 的 dyntick-idle 状态的快照，因此可以从其他 CPU 访问。最后， ->dynticks_fqs 字段用于计算此 CPU 被确定处于 dyntick-idle 状态的次数，并用于跟踪和调试目的。

rcu_data 结构的这一部分声明如下

 long nesting;
 long nmi_nesting;
 atomic_t dynticks;
 bool rcu_need_heavy_qs;
 bool rcu_urgent_qs;

rcu_data 结构中的这些字段维护相应 CPU 的每个 CPU dyntick-idle 状态。除非另有说明，否则这些字段只能从相应的 CPU （和从跟踪）访问。

->nesting 字段计算进程执行的嵌套深度，因此在正常情况下，此计数器的值为零或一。 NMI、irq 和 tracers 由 ->nmi_nesting 字段计数。由于 NMI 无法屏蔽，因此必须使用 Andy Lutomirski 提供的算法小心地对该变量进行更改。从空闲状态的初始转换增加 1，嵌套转换增加 2，因此 5 的嵌套级别由 ->nmi_nesting 值 9 表示。因此，除了进程级别转换之外，该计数器可以被认为是计算不允许此 CPU 进入 dyntick-idle 模式的原因的数量。

然而，事实证明，在非空闲内核上下文中运行时，Linux 内核完全能够进入永远不会退出的中断处理程序，反之亦然。因此，每当 ->nesting 字段从零递增时， ->nmi_nesting 字段都会设置为一个大的正数，每当 ->nesting 字段递减为零时， ->nmi_nesting 字段都会设置为零。假设错误嵌套中断的数量不足以使计数器溢出，则此方法每次相应的 CPU 从进程上下文中进入空闲循环时都会更正 ->nmi_nesting 字段。

->dynticks 字段计算相应 CPU 与 dyntick-idle 或用户模式之间的转换，因此当 CPU 处于 dyntick-idle 模式或用户模式时，此计数器具有偶数值，否则具有奇数值。需要为用户模式自适应滴答支持计数到/从用户模式的转换（请参阅 NO_HZ: 减少调度时钟滴答）。

->rcu_need_heavy_qs 字段用于记录 RCU 核心代码确实希望看到相应 CPU 的静止状态的事实，以至于它愿意调用重量级 dyntick-counter 操作。此标志由 RCU 的上下文切换和 cond_resched() 代码检查，这些代码提供了短暂的空闲停留时间来作为响应。

最后， ->rcu_urgent_qs 字段用于记录 RCU 核心代码确实希望看到相应 CPU 的静止状态的事实，其中各种其他字段指示 RCU 有多希望获得此静止状态。此标志由 RCU 的上下文切换路径 (rcu_note_context_switch) 和 cond_resched 代码检查。

快速测验:

为什么不简单地将 ->nesting 和 ->nmi_nesting 计数器合并为一个计数器，该计数器仅计算相应 CPU 非空闲的原因的数量？

答案:

因为这会在处理程序永远不会返回的中断和设法从虚构的中断返回的处理程序面前失败。

存在一些特殊用途构建的其他字段，将在单独讨论。

`rcu_head` 结构 ¶

每个 rcu_head 结构表示一个 RCU 回调。这些结构通常嵌入在使用异步宽限期的算法的 RCU 保护的数据结构中。相比之下，当使用阻塞等待 RCU 宽限期的算法时，RCU 用户不需要提供 rcu_head 结构。

rcu_head 结构具有以下字段

1   struct rcu_head *next;
2   void (*func)(struct rcu_head *head);

->next 字段用于将 rcu_head 结构链接在一起在 rcu_data 结构中的列表中。 ->func 字段是指向回调准备好被调用时要调用的函数的指针，并且该函数被传递给一个指向 rcu_head 结构的指针。但是， kfree_rcu() 使用 ->func 字段来记录包含的 RCU 保护的数据结构中 rcu_head 结构的偏移量。

这两个字段都由 RCU 在内部使用。从 RCU 用户的角度来看，此结构是一个不透明的“cookie”。

快速测验:

鉴于回调函数 ->func 被传递给一个指向 rcu_head 结构的指针，该函数应该如何找到包含的 RCU 保护的数据结构的开头？

答案:

在实际实践中，每种类型的 RCU 保护的数据结构都有一个单独的回调函数。因此，回调函数可以使用 Linux 内核中的 container_of() 宏（或其他软件环境中的其他指针操作工具）来查找包含结构的开头。

`task_struct` 结构中的 RCU 特定字段 ¶

CONFIG_PREEMPT_RCU 实现使用 task_struct 结构中的一些附加字段

#ifdef CONFIG_PREEMPT_RCU
 int rcu_read_lock_nesting;
 union rcu_special rcu_read_unlock_special;
 struct list_head rcu_node_entry;
 struct rcu_node *rcu_blocked_node;
#endif /* #ifdef CONFIG_PREEMPT_RCU */
#ifdef CONFIG_TASKS_RCU
 unsigned long rcu_tasks_nvcsw;
 bool rcu_tasks_holdout;
 struct list_head rcu_tasks_holdout_list;
 int rcu_tasks_idle_cpu;
#endif /* #ifdef CONFIG_TASKS_RCU */

->rcu_read_lock_nesting 字段记录 RCU 读取侧临界区的嵌套级别， ->rcu_read_unlock_special 字段是一个位掩码，用于记录需要 rcu_read_unlock() 执行额外工作的特殊条件。 ->rcu_node_entry 字段用于形成已在可抢占 RCU 读取侧临界区中阻塞的任务的列表， ->rcu_blocked_node 字段引用 rcu_node 结构，该结构是此任务所属的列表，如果它没有在可抢占 RCU 读取侧临界区中阻塞，则为 NULL 。

->rcu_tasks_nvcsw 字段跟踪此任务在当前任务 RCU 宽限期开始时经历的自愿上下文切换次数，如果当前的 task-RCU 宽限期正在等待此任务，则设置 ->rcu_tasks_holdout ， ->rcu_tasks_holdout_list 是一个列表元素，将此任务排队到保留列表， ->rcu_tasks_idle_cpu 跟踪此空闲任务正在运行的 CPU，但仅当该任务当前正在运行时，即 CPU 当前处于空闲状态。

访问器函数 ¶

以下列表显示了 rcu_get_root(), rcu_for_each_node_breadth_first 和 rcu_for_each_leaf_node() 函数和宏

static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
{
 return &rsp->node[0];
}
 5
#define rcu_for_each_node_breadth_first(rsp, rnp) \
 for ((rnp) = &(rsp)->node[0]; \
      (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)
 9
#define rcu_for_each_leaf_node(rsp, rnp) \
 for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \
      (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)

rcu_get_root() 只是返回一个指向指定的 rcu_state 结构的 ->node[] 数组的第一个元素的指针，这是根 rcu_node 结构。

如前所述， rcu_for_each_node_breadth_first() 宏利用 rcu_state 结构的 ->node[] 数组中 rcu_node 结构的布局，通过简单地按顺序遍历数组来执行广度优先遍历。类似地， rcu_for_each_leaf_node() 宏仅遍历数组的最后一部分，因此仅遍历叶 rcu_node 结构。

快速测验:

如果 rcu_node 树仅包含单个节点， rcu_for_each_leaf_node() 会做什么？

答案:

在单节点情况下， rcu_for_each_leaf_node() 遍历单个节点。

总结 ¶

因此，RCU 的状态由 rcu_state 结构表示，该结构包含 rcu_node 和 rcu_data 结构的组合树。最后，在 CONFIG_NO_HZ_IDLE 内核中，每个 CPU 的 dyntick-idle 状态都由 rcu_data 结构中与 dynticks 相关的字段跟踪。如果您走到这一步，您已经为阅读本系列其他文章中的代码演练做好了充分的准备。

致谢 ¶

我感谢 Cyrill Gorcunov、Mathieu Desnoyers、Dhaval Giani、Paul Turner、Abhishek Srivastava、Matt Kowalczyk 和 Serge Hallyn 帮助我将本文档置于更易于阅读的状态。

法律声明 ¶

这项工作代表作者的观点，并不一定代表 IBM 的观点。

Linux 是 Linus Torvalds 的注册商标。

其他公司、产品和服务名称可能是其他公司的商标或服务标记。

Linux 内核

目录

本页

TREE_RCU 数据结构导览 [LWN.net]¶

简介¶

数据结构关系¶

`rcu_state` 结构¶

与 rcu_node 和 rcu_data 结构的关系¶

宽限期跟踪¶

杂项¶

`rcu_node` 结构¶

连接到组合树¶

同步¶

宽限期跟踪¶

静止状态跟踪¶

阻止任务管理¶

调整 `rcu_node` 数组的大小¶

`rcu_segcblist` 结构 ¶

`rcu_data` 结构 ¶

与其他数据结构的连接 ¶

静止状态和宽限期跟踪 ¶

RCU 回调处理 ¶

Dyntick-Idle 处理 ¶

`rcu_head` 结构 ¶

`task_struct` 结构中的 RCU 特定字段 ¶

访问器函数 ¶

总结 ¶

致谢 ¶

法律声明 ¶

TREE_RCU 数据结构导览 [LWN.net]¶

简介¶

数据结构关系¶

rcu_state 结构¶

与 rcu_node 和 rcu_data 结构的关系¶

宽限期跟踪¶

杂项¶

rcu_node 结构¶

连接到组合树¶

同步¶

宽限期跟踪¶

静止状态跟踪¶

阻止任务管理¶

调整 rcu_node 数组的大小¶

rcu_segcblist 结构 ¶

rcu_data 结构 ¶

与其他数据结构的连接 ¶

静止状态和宽限期跟踪 ¶

RCU 回调处理 ¶

Dyntick-Idle 处理 ¶

rcu_head 结构 ¶

task_struct 结构中的 RCU 特定字段 ¶

访问器函数 ¶

总结 ¶

致谢 ¶

法律声明 ¶

`rcu_state` 结构¶

`rcu_node` 结构¶

调整 `rcu_node` 数组的大小¶

`rcu_segcblist` 结构 ¶

`rcu_data` 结构 ¶

`rcu_head` 结构 ¶

`task_struct` 结构中的 RCU 特定字段 ¶