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 结构中，每 16 次访问中只有一次会向上移动到树中。对于内部 rcu_node 结构，情况更加极端：每 64 次访问中只有一次会向上移动到树中。由于绝大多数 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：这个 per-CPU 结构是静止状态检测和 RCU 回调排队的核心。它还跟踪其与相应的叶子 rcu_node 结构的关系，以便更有效地将静止状态向上层传播到 rcu_node 组合树。与 rcu_node 结构一样，它提供宽限期信息的本地副本，允许从相应的 CPU 自由同步访问此信息。最后，此结构记录相应 CPU 过去的 dyntick-idle 状态，并跟踪统计信息。
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 结构，例如，如下所示

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

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

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

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

宽限期跟踪¶

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 字段以 jiffies 为单位跟踪最长宽限期的持续时间。它受根 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 中，它们管理 per-rcu_node 优先级提升内核线程（kthreads）和状态。最后，它们记录 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;

除非另有说明，否则此字段用于保护此结构中的其余字段。也就是说，可以出于跟踪目的在不锁定的情况下访问此结构中的所有字段。是的，这可能会导致令人困惑的跟踪，但总比被 Heisenbug 搞得一团糟要好。

宽限期跟踪¶

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 字段）排队到叶 rcu_node 结构的 ->blkd_tasks 列表的头部，该结构对应于执行传出上下文切换的 CPU。当这些任务稍后退出其 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，这在每个插槽有 8 个 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 预处理器变量中。

这些变量用于控制第 26-66 行的 C 预处理器 #if 语句，该语句计算树的每一层所需的 rcu_node 结构的数量以及所需的层数。层数由第 27、35、44 和 54 行放入 NUM_RCU_LVLS C 预处理器变量中。树的最顶层的 rcu_node 结构数量始终恰好为 1，此值由第 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（这与为空不同）。->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] 数组元素，还有一个重要的特殊情况：当此列表*禁用*时，它可以为 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 结构的回调，*而不是* ->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 的过去动态滴答空闲状态，并跟踪统计信息。

以下部分将单独或分组讨论 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 结构的位，并且在传播静止状态时也会使用。->beenonline 标志在相应的 CPU 上线时设置，这意味着 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 接收的回调数量。->n_nocbs_invoked 在 CPU 的回调被卸载到 kthread 时使用。

最后，->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 和跟踪器由 ->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 或用户模式以及从 dyntick-idle 或用户模式的转换，因此当 CPU 处于 dyntick-idle 模式或用户模式时，此计数器具有偶数值，否则具有奇数值。需要为用户模式自适应滴答支持计算到/从用户模式的转换（请参阅 NO_HZ：减少调度时钟滴答）。

->rcu_need_heavy_qs 字段用于记录 RCU 核心代码确实希望看到相应 CPU 的静止状态的事实，以至于它愿意调用重量级的 dyntick 计数器操作。此标志由 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_head 结构在封闭的 RCU 保护的数据结构中的偏移量。

这两个字段都在 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 字段跟踪此任务在当前 tasks-RCU 宽限期开始时经历的自愿上下文切换次数，如果当前 tasks-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 的动态滴答空闲状态由 rcu_data 结构中与动态滴答相关的字段跟踪。如果你已经读到这里，你就已经做好了充分的准备，可以阅读本系列其他文章中的代码演练。

致谢¶

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

法律声明¶

本作品代表作者的观点，不一定代表 IBM 的观点。

Linux 是 Linus Torvalds 的注册商标。

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

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 特定的字段¶