RCU需求之旅

版权所有 IBM Corporation, 2015

作者: Paul E. McKenney

本文的初始版本出现在 LWN 上,分别是这些文章: 第一部分, 第二部分, 和 第三部分

简介

Read-copy update(RCU,读取-复制更新)是一种同步机制,通常用作读者-写者锁的替代品。RCU 的特别之处在于,更新者不会阻塞读者,这意味着 RCU 的读取端原语可以非常快速且可扩展。此外,更新者可以与读者并发地进行有用的前进。但是,RCU 读者和更新者之间的所有这些并发性确实提出了一个问题,即 RCU 读者究竟在做什么,这反过来又提出了 RCU 的要求究竟是什么的问题。

因此,本文档总结了 RCU 的要求,可以被认为是 RCU 的一个非正式的、高级的规范。重要的是要理解,RCU 的规范本质上主要是经验性的;事实上,我是在经历了许多困难之后才了解到其中的许多要求的。这种情况可能会引起一些惊愕,但是,不仅这个学习过程非常有趣,而且能够与这么多愿意以有趣的新方式应用技术的人一起工作也是一种巨大的荣幸。

抛开这些不谈,以下是当前已知的 RCU 要求的类别

  1. 基本要求

  2. 基本非要求

  3. 并行的生活常识

  4. 实现质量要求

  5. Linux内核的复杂性

  6. 软件工程要求

  7. 其他 RCU 风格

  8. 可能的未来变化

接下来是一个 总结,但是,每个小测验的答案紧随其后。用鼠标选择大的空白区域来查看答案。

基本要求

RCU 的基本要求是 RCU 最接近于严格的数学要求的东西。这些是

  1. 宽限期保证

  2. 发布/订阅保证

  3. 内存屏障保证

  4. 保证无条件执行的 RCU 原语

  5. 保证从读取到写入的升级

宽限期保证

RCU 的宽限期保证非常特别,因为它是预先考虑好的:Jack Slingwine 和我在 20 世纪 90 年代初开始研究 RCU(当时称为 “rclock”)时,就牢记着这个保证。也就是说,过去二十年使用 RCU 的经验已经产生了对这个保证的更详细的理解。

RCU 的宽限期保证允许更新者等待所有预先存在的 RCU 读取端临界区的完成。RCU 读取端临界区以标记 rcu_read_lock() 开始,以标记 rcu_read_unlock() 结束。这些标记可以嵌套,RCU 将嵌套集视为一个大的 RCU 读取端临界区。rcu_read_lock()rcu_read_unlock() 的生产质量实现非常轻量级,事实上,在为生产用途构建的 Linux 内核中,使用 CONFIG_PREEMPTION=n 时,它们的开销正好为零。

这个保证允许以极低的读者开销强制执行排序,例如

 1 int x, y;
 2
 3 void thread0(void)
 4 {
 5   rcu_read_lock();
 6   r1 = READ_ONCE(x);
 7   r2 = READ_ONCE(y);
 8   rcu_read_unlock();
 9 }
10
11 void thread1(void)
12 {
13   WRITE_ONCE(x, 1);
14   synchronize_rcu();
15   WRITE_ONCE(y, 1);
16 }

由于第 14 行的 synchronize_rcu() 等待所有预先存在的读者,因此从 x 加载值为零的任何 thread0() 实例必须在 thread1() 存储到 y 之前完成,因此该实例也必须从 y 加载值为零。类似地,从 y 加载值为 1 的任何 thread0() 实例必须在 synchronize_rcu() 启动之后开始,因此也必须从 x 加载值为 1。因此,结果

(r1 == 0 && r2 == 1)

不可能发生。

小测验:

等等!你说过更新者可以与读者并发地进行有用的前进,但是预先存在的读者会阻塞 synchronize_rcu()!!! 你到底想骗谁???

答案:

首先,如果更新者不希望被读者阻塞,他们可以使用 call_rcu()kfree_rcu(),稍后将对此进行讨论。其次,即使在使用 synchronize_rcu() 时,其他的更新端代码确实与读者并发运行,无论读者是预先存在的还是新加入的。

这个场景类似于 RCU 在 DYNIX/ptx 中的第一个用途之一,它管理着一个分布式锁管理器到适合处理从节点故障中恢复的状态的转换,或多或少如下所示

 1 #define STATE_NORMAL        0
 2 #define STATE_WANT_RECOVERY 1
 3 #define STATE_RECOVERING    2
 4 #define STATE_WANT_NORMAL   3
 5
 6 int state = STATE_NORMAL;
 7
 8 void do_something_dlm(void)
 9 {
10   int state_snap;
11
12   rcu_read_lock();
13   state_snap = READ_ONCE(state);
14   if (state_snap == STATE_NORMAL)
15     do_something();
16   else
17     do_something_carefully();
18   rcu_read_unlock();
19 }
20
21 void start_recovery(void)
22 {
23   WRITE_ONCE(state, STATE_WANT_RECOVERY);
24   synchronize_rcu();
25   WRITE_ONCE(state, STATE_RECOVERING);
26   recovery();
27   WRITE_ONCE(state, STATE_WANT_NORMAL);
28   synchronize_rcu();
29   WRITE_ONCE(state, STATE_NORMAL);
30 }

do_something_dlm() 中的 RCU 读取端临界区与 start_recovery() 中的 synchronize_rcu() 一起工作,以保证 do_something() 永远不会与 recovery() 并发运行,但在 do_something_dlm() 中几乎没有或没有同步开销。

小测验:

为什么需要第 28 行上的 synchronize_rcu()

答案:

如果没有额外的宽限期,内存重排序可能会导致 do_something_dlm() 与 recovery() 的最后几位并发执行 do_something()。

为了避免死锁等致命问题,RCU 读取端临界区不得包含对 synchronize_rcu() 的调用。类似地,RCU 读取端临界区不得包含任何直接或间接等待 synchronize_rcu() 的调用的完成的内容。

虽然 RCU 的宽限期保证本身很有用,并且具有 相当多的用例,但如果能够使用 RCU 来协调对链接数据结构的读取端访问,那就更好了。为此,宽限期保证是不够的,如下面的函数 add_gp_buggy() 所示。稍后我们将查看读者的代码,但与此同时,只需将读者想象成无锁地获取 gp 指针,并且如果加载的值不是 NULL,则无锁地访问 ->a->b 字段。

 1 bool add_gp_buggy(int a, int b)
 2 {
 3   p = kmalloc(sizeof(*p), GFP_KERNEL);
 4   if (!p)
 5     return -ENOMEM;
 6   spin_lock(&gp_lock);
 7   if (rcu_access_pointer(gp)) {
 8     spin_unlock(&gp_lock);
 9     return false;
10   }
11   p->a = a;
12   p->b = a;
13   gp = p; /* ORDERING BUG */
14   spin_unlock(&gp_lock);
15   return true;
16 }

问题在于编译器和弱序 CPU 都有权按如下方式对这段代码进行重排序

 1 bool add_gp_buggy_optimized(int a, int b)
 2 {
 3   p = kmalloc(sizeof(*p), GFP_KERNEL);
 4   if (!p)
 5     return -ENOMEM;
 6   spin_lock(&gp_lock);
 7   if (rcu_access_pointer(gp)) {
 8     spin_unlock(&gp_lock);
 9     return false;
10   }
11   gp = p; /* ORDERING BUG */
12   p->a = a;
13   p->b = a;
14   spin_unlock(&gp_lock);
15   return true;
16 }

如果 RCU 读者在 add_gp_buggy_optimized 执行第 11 行后立即获取 gp,它将在 ->a->b 字段中看到垃圾。而这只是编译器和硬件优化可能导致问题的众多方式之一。因此,我们显然需要某种方法来防止编译器和 CPU 以这种方式进行重排序,这使我们进入了下一节讨论的发布-订阅保证。

发布/订阅保证

RCU 的发布-订阅保证允许将数据插入到链接的数据结构中,而不会中断 RCU 读者。更新者使用 rcu_assign_pointer() 插入新数据,读者使用 rcu_dereference() 访问数据,无论是新的还是旧的。以下显示了一个插入示例

 1 bool add_gp(int a, int b)
 2 {
 3   p = kmalloc(sizeof(*p), GFP_KERNEL);
 4   if (!p)
 5     return -ENOMEM;
 6   spin_lock(&gp_lock);
 7   if (rcu_access_pointer(gp)) {
 8     spin_unlock(&gp_lock);
 9     return false;
10   }
11   p->a = a;
12   p->b = a;
13   rcu_assign_pointer(gp, p);
14   spin_unlock(&gp_lock);
15   return true;
16 }

第 13 行上的 rcu_assign_pointer() 在概念上等同于一个简单的赋值语句,但它也保证它的赋值将在第 11 行和第 12 行的两个赋值之后发生,类似于 C11 memory_order_release 存储操作。它还防止了任意数量的 “有趣” 的编译器优化,例如,使用 gp 作为紧接在赋值之前的暂存位置。

小测验:

但是 rcu_assign_pointer() 并没有阻止对 p->ap->b 的两个赋值被重排序。这难道不会导致问题吗?

答案:

不,不会。读者在赋值给 gp 之前无法看到这两个字段中的任何一个,到那时,这两个字段都已经完全初始化。因此,对 p->ap->b 的赋值进行重排序不可能导致任何问题。

很容易假设读者不需要做任何特别的事情来控制其对 RCU 保护数据的访问,如下面的 do_something_gp_buggy() 所示

 1 bool do_something_gp_buggy(void)
 2 {
 3   rcu_read_lock();
 4   p = gp;  /* OPTIMIZATIONS GALORE!!! */
 5   if (p) {
 6     do_something(p->a, p->b);
 7     rcu_read_unlock();
 8     return true;
 9   }
10   rcu_read_unlock();
11   return false;
12 }

但是,必须抵制这种诱惑,因为编译器(或像 DEC Alpha 这样的弱序 CPU)可能会以惊人的方式绊倒这段代码。举一个例子,如果编译器缺少寄存器,它可能会选择从 gp 重新获取,而不是像下面这样在 p 中保留一个单独的副本

 1 bool do_something_gp_buggy_optimized(void)
 2 {
 3   rcu_read_lock();
 4   if (gp) { /* OPTIMIZATIONS GALORE!!! */
 5     do_something(gp->a, gp->b);
 6     rcu_read_unlock();
 7     return true;
 8   }
 9   rcu_read_unlock();
10   return false;
11 }

如果此函数与一系列用新结构替换当前结构的更新并发运行,那么对 gp->agp->b 的获取很可能来自两个不同的结构,这可能会导致严重的混乱。为了防止这种情况(以及其他许多情况),do_something_gp() 使用 rcu_dereference()gp 获取

 1 bool do_something_gp(void)
 2 {
 3   rcu_read_lock();
 4   p = rcu_dereference(gp);
 5   if (p) {
 6     do_something(p->a, p->b);
 7     rcu_read_unlock();
 8     return true;
 9   }
10   rcu_read_unlock();
11   return false;
12 }

rcu_dereference() 在 Linux 内核中使用 volatile 转换和(对于 DEC Alpha)内存屏障。如果出现 C11 memory_order_consume 的高质量实现 [PDF],那么 rcu_dereference() 可以实现为 memory_order_consume 加载。无论具体实现如何,通过 rcu_dereference() 获取的指针不得在包含该 rcu_dereference() 的最外层 RCU 读取端临界区之外使用,除非相应的数据元素的保护已从 RCU 传递到某些其他的同步机制,最常见的是锁定或引用计数(请参阅 由 RCU 保护的列表/数组的元素的引用计数设计)。

简而言之,更新者使用 rcu_assign_pointer(),读者使用 rcu_dereference(),这两个 RCU API 元素协同工作,以确保读者可以一致地查看新添加的数据元素。

当然,还需要从 RCU 保护的数据结构中删除元素,例如,使用以下过程

  1. 从封闭结构中删除数据元素。

  2. 等待所有预先存在的 RCU 读取端临界区完成(因为只有预先存在的读者才可能引用新删除的数据元素)。

  3. 此时,只有更新者引用了新删除的数据元素,因此它可以安全地回收数据元素,例如,通过将其传递给 kfree()

这个过程由 remove_gp_synchronous() 实现

 1 bool remove_gp_synchronous(void)
 2 {
 3   struct foo *p;
 4
 5   spin_lock(&gp_lock);
 6   p = rcu_access_pointer(gp);
 7   if (!p) {
 8     spin_unlock(&gp_lock);
 9     return false;
10   }
11   rcu_assign_pointer(gp, NULL);
12   spin_unlock(&gp_lock);
13   synchronize_rcu();
14   kfree(p);
15   return true;
16 }

这个函数很简单,第 13 行等待一个宽限期,然后第 14 行释放旧的数据元素。这个等待保证了读者将在数据元素被 p 引用的数据元素释放之前到达 do_something_gp() 的第 7 行。第 6 行上的 rcu_access_pointer() 类似于 rcu_dereference(),但

  1. 不能对 rcu_access_pointer() 返回的值进行解引用。如果你想访问指针指向的值以及指针本身,请使用 rcu_dereference() 而不是 rcu_access_pointer()

  2. 不需要保护对 rcu_access_pointer() 的调用。相比之下,rcu_dereference() 必须位于 RCU 读取端临界区内,或者位于指针无法更改的代码段中,例如,在受相应更新端锁保护的代码中。

小测验:

如果没有 rcu_dereference()rcu_access_pointer(),编译器可能会利用哪些破坏性优化?

答案:

让我们从 do_something_gp() 如果未能使用 rcu_dereference() 会发生什么开始。它可以重用以前从此指针获取的值。它也可以以一次一个字节的方式从 gp 获取指针,导致加载撕裂,进而导致两个不同的指针值的按字节混合。它甚至可以使用值推测优化,即它做出错误的猜测,但在它进行检查时,更新已经更改了指针以匹配错误的猜测。在此期间返回预初始化垃圾的任何解引用都很糟糕!对于 remove_gp_synchronous(),只要在持有 gp_lock 的同时执行对 gp 的所有修改,上述优化都是无害的。但是,如果您使用 __rcu 定义 gp,然后不使用 rcu_access_pointer()rcu_dereference() 访问它,sparse 会抱怨。

简而言之,RCU 的发布-订阅保证由 rcu_assign_pointer()rcu_dereference() 的组合提供。此保证允许将数据元素安全地添加到 RCU 保护的链接数据结构中,而不会中断 RCU 读者。此保证可以与宽限期保证结合使用,以允许从 RCU 保护的链接数据结构中删除数据元素,同样不会中断 RCU 读者。

这个保证只是部分预先考虑好的。DYNIX/ptx 使用显式内存屏障进行发布,但没有任何类似于 rcu_dereference() 用于订阅的东西,也没有任何类似于依赖关系排序屏障的东西,后者后来被纳入 rcu_dereference(),后来又纳入 READ_ONCE()。与 C 和 C++ 标准委员会的最新工作为编译器中的技巧和陷阱提供了很多教育。简而言之,编译器在 20 世纪 90 年代初的技巧性要差得多,但在 2015 年,甚至不要考虑省略 rcu_dereference()

内存屏障保证

前一节的简单链接数据结构场景清楚地表明,在具有多个 CPU 的系统上需要 RCU 严格的内存排序保证

  1. 每个具有在 synchronize_rcu() 启动之前开始的 RCU 读取端临界区的 CPU 保证在 RCU 读取端临界区结束的时间和 synchronize_rcu() 返回的时间之间执行完整的内存屏障。如果没有这个保证,预先存在的 RCU 读取端临界区可能会在 remove_gp_synchronous() 的第 14 行的 kfree() 之后持有对新删除的 struct foo 的引用。

  2. 每个具有在 synchronize_rcu() 返回之后结束的 RCU 读取端临界区的 CPU 保证在 synchronize_rcu() 开始的时间和 RCU 读取端临界区开始的时间之间执行完整的内存屏障。如果没有这个保证,在 remove_gp_synchronous() 的第 14 行上的 kfree() 之后运行的后面的 RCU 读取端临界区可能会稍后运行 do_something_gp() 并找到新删除的 struct foo

  3. 如果调用 synchronize_rcu() 的任务保持在给定的 CPU 上,那么保证该 CPU 在执行 synchronize_rcu() 的某个时间点执行一个完整的内存屏障。这个保证确保了 remove_gp_synchronous() 的第 14 行的 kfree() 真的在第 11 行的删除之后执行。

  4. 如果调用 synchronize_rcu() 的任务在该调用期间在一组 CPU 之间迁移,那么保证该组中的每个 CPU 在执行 synchronize_rcu() 的某个时间点执行一个完整的内存屏障。这个保证也确保了 remove_gp_synchronous() 的第 14 行的 kfree() 真的在第 11 行的删除之后执行,即使执行 synchronize_rcu() 的线程在此期间迁移。

小测验:

鉴于多个 CPU 可以在任何时间启动 RCU 读端临界区,没有任何排序要求,RCU 怎么可能判断给定的 RCU 读端临界区是否在 synchronize_rcu() 的给定实例之前开始?

答案:

如果 RCU 无法判断给定的 RCU 读端临界区是否在 synchronize_rcu() 的给定实例之前开始,那么它必须假设 RCU 读端临界区首先开始。换句话说,只有当 synchronize_rcu() 可以证明 synchronize_rcu() 首先开始时,synchronize_rcu() 的给定实例才能避免等待给定的 RCU 读端临界区。一个相关的问题是 “当 rcu_read_lock() 不生成任何代码时,它与宽限期的关系为什么重要?” 答案是,重要的不是 rcu_read_lock() 本身的关系,而是封闭的 RCU 读端临界区内的代码与宽限期之前和之后的代码的关系。如果我们采取这种观点,那么当宽限期之前的某个访问观察到临界区内的某个访问的影响时,给定的 RCU 读端临界区会在给定的宽限期之前开始,在这种情况下,临界区内的任何访问都不能观察到宽限期之后的任何访问的影响。

截至 2016 年底,RCU 的数学模型都采用了这种观点,例如,请参见 2016 LinuxCon EU 演示文稿的第 62 和 63 页。

小测验:

第一个和第二个保证要求令人难以置信的严格排序!所有这些内存屏障真的需要吗?

答案:

是的,它们确实是必需的。要了解为什么需要第一个保证,请考虑以下事件序列

  1. CPU 1: rcu_read_lock()

  2. CPU 1: q = rcu_dereference(gp); /* 很可能返回 p. */

  3. CPU 0: list_del_rcu(p);

  4. CPU 0: synchronize_rcu() 开始。

  5. CPU 1: do_something_with(q->a); /* 没有 smp_mb(),所以可能发生在 kfree() 之后。 */

  6. CPU 1: rcu_read_unlock()

  7. CPU 0: synchronize_rcu() 返回。

  8. CPU 0: kfree(p);

因此,在 RCU 读端临界区结束和宽限期结束之间必须存在完整的内存屏障。

证明第二条规则必要性的事件序列大致相似

  1. CPU 0: list_del_rcu(p);

  2. CPU 0: synchronize_rcu() 开始。

  3. CPU 1: rcu_read_lock()

  4. CPU 1: q = rcu_dereference(gp); /* 如果没有内存屏障,可能会返回 p */

  5. CPU 0: synchronize_rcu() 返回。

  6. CPU 0: kfree(p);

  7. CPU 1: do_something_with(q->a); /* Boom!!! */

  8. CPU 1: rcu_read_unlock()

同样,如果没有宽限期开始和 RCU 读端临界区开始之间的内存屏障,CPU 1 可能会最终访问空闲列表。

当然,“仿佛”规则适用,因此任何表现得好像已就位适当的内存屏障的实现都是正确的实现。也就是说,欺骗自己相信你已经遵守了仿佛规则比实际遵守它要容易得多!

小测验:

您声称 rcu_read_lock()rcu_read_unlock() 在某些内核构建中绝对不生成任何代码。这意味着编译器可能会任意重新排列连续的 RCU 读端临界区。鉴于这种重新排列,如果给定的 RCU 读端临界区已完成,您如何确保所有先前的 RCU 读端临界区都已完成?编译器重新排列不会使这不可能确定吗?

答案:

rcu_read_lock()rcu_read_unlock() 绝对不生成任何代码的情况下,RCU 仅在特殊位置(例如,在调度程序中)推断静止状态。因为调用 schedule() 最好防止调用代码对共享变量的访问在调用 schedule() 之间重新排列,所以如果 RCU 检测到给定的 RCU 读端临界区的结束,它将必然检测到所有先前 RCU 读端临界区的结束,无论编译器多么积极地扰乱代码。同样,这一切都假定编译器无法在调用调度程序、中断处理程序、空闲循环、用户模式代码等之间扰乱代码。但是,如果您的内核构建允许这种扰乱,那么您破坏的不仅仅是 RCU!

请注意,这些内存屏障要求不会取代 RCU 的基本要求,即宽限期等待所有预先存在的读取者。相反,本节中调用的内存屏障必须以强制执行此基本要求的方式运行。当然,不同的实现以不同的方式强制执行此要求,但它们必须强制执行。

保证无条件执行的 RCU 原语

常见的 RCU 原语是无条件的。它们被调用,它们完成它们的工作,然后它们返回,没有出错的可能性,也不需要重试。这是 RCU 的一个关键设计理念。

但是,这种理念是务实的,而不是顽固的。如果有人提出了一个对特定条件 RCU 原语的良好理由,那么它很可能会被实现和添加。毕竟,这种保证是被逆向工程的,而不是预先策划的。RCU 原语的无条件性质最初是实现上的偶然事件,后来使用具有条件原语的同步原语的经验使我将此偶然事件提升为保证。因此,将条件原语添加到 RCU 的理由需要基于详细且引人注目的用例。

保证的读到写升级

就 RCU 而言,始终可以在 RCU 读端临界区内执行更新。例如,该 RCU 读端临界区可能会搜索给定的数据元素,然后可能会获取更新端自旋锁以更新该元素,所有这些都在该 RCU 读端临界区内进行。当然,在调用 synchronize_rcu() 之前必须退出 RCU 读端临界区,但是,可以通过使用本文档后面描述的 call_rcu()kfree_rcu() API 成员来避免这种不便。

小测验:

但是,升级到写操作如何排除其他读取者?

答案:

它不会,就像正常的 RCU 更新一样,它也不会排除 RCU 读取者。

此保证允许在读端和更新端代码之间共享查找代码,并且是预先策划的,出现在最早的 DYNIX/ptx RCU 文档中。

基本非要求

RCU 提供了非常轻量级的读取者,并且它的读端保证虽然非常有用,但相应地也是轻量级的。因此,很容易假设 RCU 保证的比实际情况更多。当然,RCU 不保证的事情的列表是无限长的,但是,以下各节列出了一些引起混淆的非保证。除非另有说明,否则这些非保证是预先策划的。

  1. 读取者施加最小排序

  2. 读取者不排除更新者

  3. 更新者仅等待旧的读取者

  4. 宽限期不划分读端临界区

  5. 读端临界区不划分宽限期

读取者施加最小排序

读取者端标记(例如 rcu_read_lock()rcu_read_unlock())除了通过它们与宽限期 API(例如 synchronize_rcu())的交互之外,绝对不提供任何排序保证。要了解这一点,请考虑以下一对线程

 1 void thread0(void)
 2 {
 3   rcu_read_lock();
 4   WRITE_ONCE(x, 1);
 5   rcu_read_unlock();
 6   rcu_read_lock();
 7   WRITE_ONCE(y, 1);
 8   rcu_read_unlock();
 9 }
10
11 void thread1(void)
12 {
13   rcu_read_lock();
14   r1 = READ_ONCE(y);
15   rcu_read_unlock();
16   rcu_read_lock();
17   r2 = READ_ONCE(x);
18   rcu_read_unlock();
19 }

在 thread0() 和 thread1() 并发执行之后,完全有可能出现

(r1 == 1 && r2 == 0)

(也就是说,y 似乎在 x 之前被赋值),如果 rcu_read_lock()rcu_read_unlock() 具有很大的排序属性,这是不可能的。但它们没有,因此 CPU 有权进行大量的重新排序。这是设计使然:任何重要的排序约束都会降低这些快速路径 API 的速度。

小测验:

编译器不是也可以重新排序这段代码吗?

答案:

不,READ_ONCE() 和 WRITE_ONCE() 中的 volatile 转换会阻止编译器在这种特殊情况下进行重新排序。

读取者不排除更新者

rcu_read_lock()rcu_read_unlock() 都不排除更新。它们所做的只是阻止宽限期结束。以下示例说明了这一点

 1 void thread0(void)
 2 {
 3   rcu_read_lock();
 4   r1 = READ_ONCE(y);
 5   if (r1) {
 6     do_something_with_nonzero_x();
 7     r2 = READ_ONCE(x);
 8     WARN_ON(!r2); /* BUG!!! */
 9   }
10   rcu_read_unlock();
11 }
12
13 void thread1(void)
14 {
15   spin_lock(&my_lock);
16   WRITE_ONCE(x, 1);
17   WRITE_ONCE(y, 1);
18   spin_unlock(&my_lock);
19 }

如果 thread0() 函数的 rcu_read_lock() 排除 thread1() 函数的更新,则 WARN_ON() 永远不会触发。但事实是,rcu_read_lock() 除了后续的宽限期(thread1() 没有)之外,几乎不排除任何东西,因此 WARN_ON() 可以并且确实会触发。

更新者仅等待旧的读取者

可能会认为在 synchronize_rcu() 完成后,没有读取者正在执行。必须避免这种诱惑,因为新的读取者可以在 synchronize_rcu() 开始后立即开始,并且 synchronize_rcu() 没有义务等待这些新的读取者。

小测验:

假设 synchronize_rcu() 等到所有读取者都已完成,而不是仅等待预先存在的读取者。更新者可以在多长时间内依靠没有读取者?

答案:

根本没有时间。即使 synchronize_rcu() 等到所有读取者都已完成,新的读取者也可能在 synchronize_rcu() 完成后立即开始。因此,synchronize_rcu() 之后的代码永远不能依赖于没有读取者。

宽限期不划分读端临界区

可能会认为如果一个 RCU 读端临界区的任何部分在给定的宽限期之前,并且另一个 RCU 读端临界区的任何部分在同一宽限期之后,那么第一个 RCU 读端临界区的所有部分必须在第二个 RCU 读端临界区的所有部分之前。但是,事实并非如此:单个宽限期不会划分 RCU 读端临界区的集合。这种情况的示例可以说明如下,其中 xyz 最初都为零

 1 void thread0(void)
 2 {
 3   rcu_read_lock();
 4   WRITE_ONCE(a, 1);
 5   WRITE_ONCE(b, 1);
 6   rcu_read_unlock();
 7 }
 8
 9 void thread1(void)
10 {
11   r1 = READ_ONCE(a);
12   synchronize_rcu();
13   WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18   rcu_read_lock();
19   r2 = READ_ONCE(b);
20   r3 = READ_ONCE(c);
21   rcu_read_unlock();
22 }

结果表明,结果

(r1 == 1 && r2 == 0 && r3 == 1)

完全有可能。下图显示了这种情况如何发生,每个带圈的 QS 表示 RCU 为每个线程记录静止状态的点,也就是说,RCU 知道该线程不可能是正在进行的在当前宽限期之前开始的 RCU 读端临界区中

../../../_images/GPpartitionReaders1.svg

如果需要以这种方式划分 RCU 读端临界区,则需要使用两个宽限期,其中第一个宽限期已知在第二个宽限期开始之前结束

 1 void thread0(void)
 2 {
 3   rcu_read_lock();
 4   WRITE_ONCE(a, 1);
 5   WRITE_ONCE(b, 1);
 6   rcu_read_unlock();
 7 }
 8
 9 void thread1(void)
10 {
11   r1 = READ_ONCE(a);
12   synchronize_rcu();
13   WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18   r2 = READ_ONCE(c);
19   synchronize_rcu();
20   WRITE_ONCE(d, 1);
21 }
22
23 void thread3(void)
24 {
25   rcu_read_lock();
26   r3 = READ_ONCE(b);
27   r4 = READ_ONCE(d);
28   rcu_read_unlock();
29 }

在这里,如果 (r1 == 1),则 thread0() 对 b 的写入必须在 thread1() 的宽限期结束之前发生。如果此外 (r4 == 1),则 thread3() 对 b 的读取必须在 thread2() 的宽限期开始之后发生。如果也是 (r2 == 1),则 thread1() 的宽限期结束必须在 thread2() 的宽限期开始之前发生。这意味着两个 RCU 读端临界区不能重叠,从而保证 (r3 == 1)。因此,结果

(r1 == 1 && r2 == 1 && r3 == 0 && r4 == 1)

不可能发生。

这种非要求也不是预先策划的,但在研究 RCU 与内存排序的交互时变得显而易见。

读端临界区不划分宽限期

如果 RCU 读端临界区发生在两个宽限期之间,则可能会认为这些宽限期不能重叠。但是,这种诱惑不会导致任何好的结果,可以通过以下方式说明,其中所有变量最初都为零

 1 void thread0(void)
 2 {
 3   rcu_read_lock();
 4   WRITE_ONCE(a, 1);
 5   WRITE_ONCE(b, 1);
 6   rcu_read_unlock();
 7 }
 8
 9 void thread1(void)
10 {
11   r1 = READ_ONCE(a);
12   synchronize_rcu();
13   WRITE_ONCE(c, 1);
14 }
15
16 void thread2(void)
17 {
18   rcu_read_lock();
19   WRITE_ONCE(d, 1);
20   r2 = READ_ONCE(c);
21   rcu_read_unlock();
22 }
23
24 void thread3(void)
25 {
26   r3 = READ_ONCE(d);
27   synchronize_rcu();
28   WRITE_ONCE(e, 1);
29 }
30
31 void thread4(void)
32 {
33   rcu_read_lock();
34   r4 = READ_ONCE(b);
35   r5 = READ_ONCE(e);
36   rcu_read_unlock();
37 }

在这种情况下,结果

(r1 == 1 && r2 == 1 && r3 == 1 && r4 == 0 && r5 == 1)

完全有可能,如下图所示

../../../_images/ReadersPartitionGP1.svg

同样,RCU 读端临界区可以与给定的宽限期几乎所有部分重叠,只要它不与整个宽限期重叠即可。因此,RCU 读端临界区不能划分一对 RCU 宽限期。

小测验:

分隔链条开头和结尾的 RCU 读端临界区需要多长时间的宽限期序列,每个宽限期都由一个 RCU 读端临界区分隔?

答案:

理论上是无限数量。实际上是一个未知的数字,它对实现细节和时间考虑因素都很敏感。因此,即使在实践中,RCU 用户也必须遵守理论上的答案,而不是实际上的答案。

并行性的生活真相

这些并行性的生活真相绝非 RCU 独有,但 RCU 实现必须遵守它们。因此,有必要重复一下

  1. 任何 CPU 或任务都可能在任何时候被延迟,并且任何通过禁用抢占、中断或任何其他方式来避免这些延迟的尝试都是完全徒劳的。这在可抢占的用户级环境和虚拟化环境(其中给定客户操作系统的 VCPU 可以随时被底层虚拟机管理程序抢占)中最为明显,但由于 ECC 错误、NMI 和其他硬件事件,也可能发生在裸机环境中。虽然超过大约 20 秒的延迟可能会导致崩溃,但 RCU 实现有义务使用可以容忍极长延迟的算法,但其中“极长”不足以允许在递增 64 位计数器时回绕。

  2. 编译器和 CPU 都可以重新排序内存访问。在重要的地方,RCU 必须使用编译器指令和内存屏障指令来保持排序。

  3. 对任何给定缓存行中的内存位置的冲突写入将导致昂贵的缓存未命中。更大数量的并发写入和更频繁的并发写入将导致更显着的减速。因此,RCU 有义务使用具有足够局部性的算法,以避免显着的性能和可伸缩性问题。

  4. 作为一条粗略的经验法则,在任何给定的独占锁的保护下,只能执行一个 CPU 的处理量。因此,RCU 必须使用可伸缩的锁定设计。

  5. 计数器是有限的,尤其是在 32 位系统上。因此,RCU 对计数器的使用必须容忍计数器回绕,或者设计成计数器回绕所花费的时间比单个系统可能运行的时间长得多。十年的正常运行时间是完全可能的,一个世纪的运行时就不太可能了。作为后者的一个例子,RCU 的 dyntick-idle 嵌套计数器允许中断嵌套级别使用 54 位(即使在 32 位系统上,此计数器也是 64 位的)。溢出此计数器需要在一个给定的 CPU 上进行 254 次半中断,而该 CPU 从未进入空闲状态。如果每微秒发生一次半中断,则需要 570 年的运行时才能溢出此计数器,目前认为这是一个可接受的长的时间。

  6. Linux 系统可以在单个共享内存环境中运行数千个 CPU 运行单个 Linux 内核。因此,RCU 必须密切关注高端可伸缩性。

最后一个并行性的生活真相意味着 RCU 必须特别关注前面的生活真相。Linux 可能会扩展到具有数千个 CPU 的系统的想法在 1990 年代会受到一些怀疑,但这些要求在 1990 年代初就已经不足为奇了。

实现质量要求

这些章节列出了实现质量要求。虽然可以仍然使用忽略这些要求的 RCU 实现,但它可能会受到限制,使其不适合工业强度生产使用。实现质量要求的类别如下

  1. 专业化

  2. 性能和可伸缩性

  3. 前进性

  4. 可组合性

  5. 极端情况

以下章节将介绍这些类别。

专业化

RCU 始终主要用于读取为主的情况,这意味着 RCU 的读取端原语经过优化,通常以牺牲其更新端原语为代价。到目前为止的经验已被以下情况列表捕获

  1. 读取为主的数据,其中陈旧和不一致的数据不是问题:RCU 工作得很好!

  2. 读取为主的数据,其中数据必须一致:RCU 工作良好。

  3. 读写数据,其中数据必须一致:RCU 可能 可以正常工作。或者不能。

  4. 写入为主的数据,其中数据必须一致:RCU 很可能不是适合这项工作的工具,但以下例外情况除外,RCU 可以提供

    1. 更新友好机制的存在保证。

    2. 实时使用的无等待读端原语。

这种对读取为主情况的关注意味着 RCU 必须与其他同步原语互操作。例如,前面讨论的 add_gp() 和 remove_gp_synchronous() 示例使用 RCU 来保护读取者并锁定以协调更新者。但是,这种需求扩展到更远,要求各种同步原语在 RCU 读端临界区内都是合法的,包括自旋锁、序列锁、原子操作、引用计数器和内存屏障。

小测验:

那么睡眠锁呢?

答案:

在Linux内核RCU读取侧临界区内,这些操作是被禁止的,因为在RCU读取侧临界区内放置静止状态(在本例中为自愿上下文切换)是不合法的。但是,睡眠锁可以在用户空间RCU读取侧临界区内使用,也可以在Linux内核可睡眠RCU (SRCU) 读取侧临界区内使用。此外,-rt补丁集将自旋锁转换为睡眠锁,以便相应的临界区可以被抢占,这也意味着这些睡眠锁化的自旋锁(但不是其他睡眠锁!)可以在-rt-Linux内核RCU读取侧临界区内获取。请注意,正常的RCU读取侧临界区可以有条件地获取睡眠锁(如mutex_trylock()),但只要它不无限循环尝试有条件地获取该睡眠锁即可。关键是像mutex_trylock()这样的函数,要么在持有互斥锁的情况下返回,要么在互斥锁无法立即使用的情况下返回错误指示。无论哪种方式,mutex_trylock()都会立即返回,而不会睡眠。

通常令人惊讶的是,许多算法不需要数据的一致视图,但许多算法可以在这种模式下运行,网络路由就是一个典型的例子。互联网路由算法需要相当长的时间来传播更新,因此当更新到达给定的系统时,该系统已经以错误的方式发送网络流量相当长的时间了。让一些线程继续以错误的方式发送流量几毫秒显然不是问题:在最坏的情况下,TCP重传最终会将数据发送到需要去的地方。一般来说,当跟踪计算机外部的宇宙状态时,由于光速延迟等原因,必须容忍一定程度的不一致性。

此外,在许多情况下,外部状态的不确定性是固有的。例如,一对兽医可能会使用心跳来确定给定的猫是否还活着。但是,在最后一次心跳之后,他们应该等待多久才能确定这只猫确实已经死了?等待时间少于400毫秒是没有意义的,因为这意味着一只放松的猫会被认为每分钟在死亡和生命之间循环100多次。此外,就像人类一样,猫的心脏可能会停止一段时间,因此确切的等待时间是一种判断。我们这对兽医中的一位可能会在宣布猫死亡之前等待30秒,而另一位可能会坚持等待整整一分钟。然后,两位兽医会在最后一次心跳后的一分钟的最后30秒内对猫的状态产生分歧。

有趣的是,这种情况也适用于硬件。关键时刻,我们如何判断某个外部服务器是否发生故障?我们会定期向其发送消息,如果在给定的时间内未收到响应,则声明其发生故障。策略决策通常可以容忍短时间的不一致。该策略是前一段时间决定的,现在才开始生效,因此几毫秒的延迟通常无关紧要。

但是,有些算法绝对必须看到一致的数据。例如,用户级别SystemV信号量ID与相应的内核数据结构之间的转换受到RCU的保护,但绝对禁止更新刚刚删除的信号量。在Linux内核中,这种对一致性的需求通过从RCU读取侧临界区内获取位于内核数据结构中的自旋锁来满足,这在上面的图中用绿色框表示。可以使用许多其他技术,并且实际上在Linux内核中使用。

简而言之,RCU不需要保持一致性,当需要一致性时,可以与其他机制结合使用。RCU的专业化使其能够出色地完成其工作,并且它与其他同步机制互操作的能力允许为给定的工作使用正确的同步工具组合。

性能和可扩展性

能源效率是当今性能的关键组成部分,因此Linux内核RCU实现必须避免不必要地唤醒空闲CPU。我不能声称这种要求是有预谋的。事实上,我是在一次电话交谈中得知这一点的,在电话中,我收到了关于电池供电系统中能源效率的重要性和Linux内核RCU实现的具体能源效率缺点的“坦诚和公开”的反馈。以我的经验来看,电池供电的嵌入式社区会认为任何不必要的唤醒都是非常不友好的行为。以至于仅仅是Linux内核邮件列表帖子不足以发泄他们的愤怒。

在大多数情况下,内存消耗并不是特别重要,并且随着内存容量的扩大和内存成本的下降,其重要性也在降低。但是,正如我从Matt Mackall的bloatwatch努力中了解到的一样,在具有不可抢占(CONFIG_PREEMPTION=n)内核的单CPU系统上,内存占用至关重要,因此tiny RCU应运而生。Josh Triplett后来通过他的Linux内核精简化项目接管了小内存的旗帜,该项目导致SRCU对于那些不需要它的内核成为可选的。

其余的性能要求在很大程度上并不令人意外。例如,为了与RCU读取侧的专业化保持一致,rcu_dereference()应该具有可以忽略不计的开销(例如,抑制一些次要的编译器优化)。同样,在不可抢占的环境中,rcu_read_lock()rcu_read_unlock()应该完全没有开销。

在可抢占的环境中,如果RCU读取侧临界区没有被抢占(对于最高优先级的实时进程来说,情况就是这样),rcu_read_lock()rcu_read_unlock()应该具有最小的开销。特别是,它们不应包含原子读-修改-写操作、内存屏障指令、抢占禁用、中断禁用或向后分支。但是,如果RCU读取侧临界区被抢占,rcu_read_unlock()可能会获取自旋锁并禁用中断。这就是为什么最好将RCU读取侧临界区嵌套在抢占禁用区域内,而不是反过来,至少在临界区足够短以避免不适当地降低实时延迟的情况下。

synchronize_rcu()宽限期等待原语针对吞吐量进行了优化。因此,除了最长的RCU读取侧临界区的持续时间之外,它还可能会产生几毫秒的延迟。另一方面,需要多次并发调用synchronize_rcu()来使用批处理优化,以便可以通过单个底层宽限期等待操作来满足它们。例如,在Linux内核中,单个宽限期等待操作服务于1,000多个单独的synchronize_rcu()调用是很常见的,从而将每次调用的开销分摊到几乎为零。但是,宽限期优化也需要避免可测量的实时调度和中断延迟的降低。

在某些情况下,几毫秒的synchronize_rcu()延迟是不可接受的。在这些情况下,可以改用synchronize_rcu_expedited(),从而将宽限期延迟降低到小型系统上的几十微秒,至少在RCU读取侧临界区很短的情况下。目前对大型系统上的synchronize_rcu_expedited()没有特殊的延迟要求,但是,与RCU规范的经验性质一致,这可能会发生变化。但是,肯定有可扩展性要求:在4096个CPU上爆发synchronize_rcu_expedited()调用至少应该取得合理的进展。作为其较短延迟的回报,允许synchronize_rcu_expedited()对非空闲在线CPU施加适度的实时延迟降低。在这里,“适度”意味着与调度时钟中断大致相同的延迟降低。

在许多情况下,即使是synchronize_rcu_expedited()的减少的宽限期延迟也是不可接受的。在这些情况下,可以使用异步call_rcu()代替synchronize_rcu(),如下所示

 1 struct foo {
 2   int a;
 3   int b;
 4   struct rcu_head rh;
 5 };
 6
 7 static void remove_gp_cb(struct rcu_head *rhp)
 8 {
 9   struct foo *p = container_of(rhp, struct foo, rh);
10
11   kfree(p);
12 }
13
14 bool remove_gp_asynchronous(void)
15 {
16   struct foo *p;
17
18   spin_lock(&gp_lock);
19   p = rcu_access_pointer(gp);
20   if (!p) {
21     spin_unlock(&gp_lock);
22     return false;
23   }
24   rcu_assign_pointer(gp, NULL);
25   call_rcu(&p->rh, remove_gp_cb);
26   spin_unlock(&gp_lock);
27   return true;
28 }

最后需要struct foo的定义,它出现在第1-5行。函数remove_gp_cb()在第25行传递给call_rcu(),并且将在随后的宽限期结束后被调用。这与remove_gp_synchronous()具有相同的效果,但无需强制更新器等待宽限期过去。call_rcu()函数可以在许多情况下使用,在这些情况下,synchronize_rcu()synchronize_rcu_expedited()都是非法的,包括在抢占禁用代码、local_bh_disable()代码、中断禁用代码和中断处理程序中。但是,即使是call_rcu()在NMI处理程序以及来自空闲和离线CPU的代码中也是非法的。回调函数(在本例中为remove_gp_cb())将在Linux内核中的softirq(软件中断)环境中执行,无论是在真正的softirq处理程序中还是在local_bh_disable()的保护下。在Linux内核和用户空间中,编写运行时间过长的RCU回调函数都是不好的做法。长时间运行的操作应该交给单独的线程或(在Linux内核中)工作队列。

小测验:

为什么第19行使用rcu_access_pointer()?毕竟,第25行的call_rcu()存储到结构中,这会与并发插入产生不良影响。这是否意味着需要rcu_dereference()

答案:

大概第18行获取的->gp_lock排除了任何更改,包括rcu_dereference()会防止的任何插入。因此,任何插入都将延迟到第25行释放->gp_lock之后,这反过来意味着rcu_access_pointer()就足够了。

但是,remove_gp_cb()所做的只是在数据元素上调用kfree()。这是一个常见的习惯用法,并由kfree_rcu()支持,它允许“发射后不管”操作,如下所示

 1 struct foo {
 2   int a;
 3   int b;
 4   struct rcu_head rh;
 5 };
 6
 7 bool remove_gp_faf(void)
 8 {
 9   struct foo *p;
10
11   spin_lock(&gp_lock);
12   p = rcu_dereference(gp);
13   if (!p) {
14     spin_unlock(&gp_lock);
15     return false;
16   }
17   rcu_assign_pointer(gp, NULL);
18   kfree_rcu(p, rh);
19   spin_unlock(&gp_lock);
20   return true;
21 }

请注意,remove_gp_faf()仅调用kfree_rcu()并继续,而无需进一步关注随后的宽限期和kfree()。允许从与call_rcu()相同的环境调用kfree_rcu()。有趣的是,DYNIX/ptx具有与call_rcu()kfree_rcu()等效的功能,但没有synchronize_rcu()。这是因为RCU在DYNIX/ptx中没有被大量使用,因此极少数需要类似synchronize_rcu()的功能的地方只是简单地打开了它。

小测验:

之前声称call_rcu()kfree_rcu()允许更新器避免被读取器阻止。但是,考虑到回调的调用和内存的释放(分别)仍然必须等待宽限期过去,这怎么可能是正确的?

答案:

我们可以这样定义,但请记住,这种定义会说垃圾回收语言中的更新在下次垃圾回收器运行之前无法完成,这似乎完全不合理。关键是,在大多数情况下,使用call_rcu()kfree_rcu()的更新器一旦调用call_rcu()kfree_rcu(),就可以继续进行下一个更新,而无需等待随后的宽限期。

但是,如果更新器必须等待在宽限期结束后执行的代码完成,但同时可以执行其他任务呢?轮询式get_state_synchronize_rcu()cond_synchronize_rcu()函数可以用于此目的,如下所示

 1 bool remove_gp_poll(void)
 2 {
 3   struct foo *p;
 4   unsigned long s;
 5
 6   spin_lock(&gp_lock);
 7   p = rcu_access_pointer(gp);
 8   if (!p) {
 9     spin_unlock(&gp_lock);
10     return false;
11   }
12   rcu_assign_pointer(gp, NULL);
13   spin_unlock(&gp_lock);
14   s = get_state_synchronize_rcu();
15   do_something_while_waiting();
16   cond_synchronize_rcu(s);
17   kfree(p);
18   return true;
19 }

在第14行,get_state_synchronize_rcu()从RCU获取一个“cookie”,然后在第15行执行其他任务,最后,如果在该期间宽限期已经过去,则第16行立即返回,否则根据需要等待。对get_state_synchronize_rcucond_synchronize_rcu()的需求最近才出现,因此判断它们是否经得起时间的考验还为时过早。

因此,RCU提供了一系列工具,允许更新器在延迟、灵活性和CPU开销之间进行所需的权衡。

向前进展

理论上,延迟宽限期完成和回调调用是无害的。在实践中,不仅内存大小有限,而且回调有时会进行唤醒,并且足够延迟的唤醒可能难以与系统挂起区分开来。因此,RCU必须提供许多机制来促进向前进展。

这些机制并非万无一失,也无法做到。举一个简单的例子,RCU读取侧临界区中的无限循环必须定义为阻止以后的宽限期完成。对于一个更复杂的例子,考虑一个使用CONFIG_RCU_NOCB_CPU=y构建并使用rcu_nocbs=1-63启动的64CPU系统,其中CPU 1到63在调用call_rcu()的紧密循环中旋转。即使这些紧密循环也包含对cond_resched()的调用(从而允许宽限期完成),CPU 0也根本无法像其他63个CPU注册它们一样快地调用回调,至少在系统耗尽内存之前是这样。在这两个例子中,都适用蜘蛛侠原则:能力越大,责任越大。但是,除非达到这种滥用程度,否则RCU需要确保及时完成宽限期和及时调用回调。

RCU采取以下步骤来鼓励及时完成宽限期

  1. 如果宽限期在100毫秒内未能完成,RCU会导致未来在拒不合作的CPU上调用cond_resched()以提供RCU静止状态。RCU还会导致这些CPU的need_resched()调用返回true,但仅在相应CPU的下一个调度时钟之后。

  2. nohz_full内核启动参数中提到的CPU可以在内核中无限期地运行,而无需调度时钟中断,这会破坏上述need_resched()策略。因此,RCU将在109毫秒后仍在拒绝合作的任何nohz_full CPU上调用resched_cpu()。

  3. 在使用CONFIG_RCU_BOOST=y构建的内核中,如果给定的任务在RCU读取侧临界区内被抢占的时间超过500毫秒,RCU将求助于优先级提升。

  4. 如果CPU在宽限期开始后的10秒钟内仍然拒绝合作,则无论其nohz_full状态如何,RCU都会在其上调用resched_cpu()。

上述值是在HZ=1000下运行的系统的默认值。它们会随着HZ的值而变化,也可以使用相关的Kconfig选项和内核启动参数进行更改。RCU目前没有对这些参数进行太多的健全性检查,因此在更改它们时请务必小心。请注意,这些向前进展措施仅适用于RCU,不适用于SRCUTasks RCU

当任何给定的非rcu_nocbs CPU具有10,000个回调,或者比上次提供鼓励时多10,000个回调时,RCU会在call_rcu()中采取以下步骤来鼓励及时调用回调

  1. 启动一个宽限期,如果一个宽限期尚未进行中。

  2. 强制立即检查静止状态,而不是等待自宽限期开始以来经过三毫秒。

  3. 立即使用CPU的宽限期完成编号标记CPU的回调,而不是等待RCU_SOFTIRQ处理程序来处理它。

  4. 取消回调执行批处理限制,这会以降低实时响应为代价来加速回调调用。

同样,这些是在HZ=1000下运行时的默认值,并且可以被覆盖。同样,这些向前进展措施仅适用于RCU,不适用于SRCUTasks RCU。即使对于RCU,rcu_nocbs CPU的回调调用向前进展也没有得到很好的发展,部分原因是受益于rcu_nocbs CPU的工作负载倾向于相对不频繁地调用call_rcu()。如果出现既需要rcu_nocbs CPU又需要高call_rcu()调用速率的工作负载,则需要进行额外的向前进展工作。

可组合性

近年来,可组合性受到了广泛关注,这可能部分是由于多核硬件与在单线程环境中为单线程使用而设计的面向对象技术的碰撞。理论上,RCU读取侧临界区可以组合,并且实际上可以任意深度地嵌套。在实践中,与所有可组合结构的实际实现一样,存在限制。

对于rcu_read_lock()rcu_read_unlock()不生成任何代码的RCU实现(例如,当CONFIG_PREEMPTION=n时,Linux内核RCU)可以任意深度地嵌套。毕竟,没有开销。除非所有这些rcu_read_lock()rcu_read_unlock()的实例对编译器可见,否则编译最终会由于耗尽内存、海量存储或用户耐心而失败,无论哪个先到。如果嵌套对编译器不可见(就像每个都在自己的转换单元中的相互递归函数一样),则会导致堆栈溢出。如果嵌套采用循环的形式(可能伪装成尾递归),则控制变量将溢出,或者(在Linux内核中)你将收到RCU CPU stall警告。尽管如此,此类RCU实现是现有可组合性最强的结构之一。

显式跟踪嵌套深度的 RCU 实现受嵌套深度计数器的限制。例如,Linux 内核的可抢占 RCU 将嵌套限制为 INT_MAX。对于几乎所有实际用途来说,这都应该足够了。也就是说,如果两个连续的 RCU 读端临界区之间存在一个等待宽限期的操作,则不能将它们包含在另一个 RCU 读端临界区中。这是因为在 RCU 读端临界区内等待宽限期是不合法的:这样做要么会导致死锁,要么会导致 RCU 隐式地拆分包含它的 RCU 读端临界区,这两种情况都不利于内核的长期稳定和繁荣。

值得注意的是,RCU 并不是唯一限制可组合性的机制。例如,许多事务内存实现禁止组合由不可撤销操作(例如,网络接收操作)分隔的一对事务。再例如,基于锁的临界区可以以惊人的自由度进行组合,但前提是避免死锁。

简而言之,尽管 RCU 读端临界区具有高度的可组合性,但在某些情况下需要小心,就像任何其他可组合的同步机制一样。

极端情况

给定的 RCU 工作负载可能具有无休止且密集的 RCU 读端临界区流,甚至可能如此密集,以至于任何时刻都至少有一个 RCU 读端临界区在运行。RCU 不能允许这种情况阻止宽限期:只要所有 RCU 读端临界区都是有限的,宽限期也必须是有限的。

也就是说,可抢占的 RCU 实现可能会导致 RCU 读端临界区被抢占很长时间,从而产生一个长时间的 RCU 读端临界区。这种情况仅在负载很重的系统中才会出现,但使用实时优先级的系统当然更容易受到影响。因此,提供了 RCU 优先级提升来帮助处理这种情况。也就是说,随着经验的积累,对 RCU 优先级提升的确切要求可能会发生变化。

其他工作负载可能具有非常高的更新率。尽管可以认为此类工作负载应该使用 RCU 以外的其他机制,但事实仍然是 RCU 必须优雅地处理此类工作负载。这个要求是推动宽限期批处理的另一个因素,但它也是 call_rcu() 代码路径中检查大量排队的 RCU 回调函数的原因。最后,高更新率不应延迟 RCU 读端临界区,尽管在使用 synchronize_rcu_expedited() 时可能会出现一些小的读端延迟,这要归功于此函数对 smp_call_function_single() 的使用。

尽管所有这三个极端情况在 1990 年代初就已经被理解,但在 2000 年代初,一个简单的用户级测试,包括在一个紧密循环中使用 close(open(path)),突然提供了对高更新率极端情况的更深刻理解。该测试还促使添加了一些 RCU 代码来应对高更新率,例如,如果给定的 CPU 发现自己排队了超过 10,000 个 RCU 回调函数,它将导致 RCU 采取规避措施,更积极地启动宽限期,并更积极地强制完成宽限期处理。这种规避措施会导致宽限期更快地完成,但代价是限制了 RCU 的批处理优化,从而增加了该宽限期产生的 CPU 开销。

软件工程要求

考虑到墨菲定律和“人非圣贤,孰能无过”,有必要防范事故和误用。

  1. 很容易忘记在需要使用 rcu_read_lock() 的地方都使用它,因此使用 CONFIG_PROVE_RCU=y 构建的内核如果 rcu_dereference() 在 RCU 读端临界区之外使用,则会崩溃。更新端代码可以使用 rcu_dereference_protected(),它接受一个 lockdep 表达式 来指示什么提供了保护。如果未提供指示的保护,则会发出 lockdep splat。在读者和更新者之间共享的代码可以使用 rcu_dereference_check(),它也接受一个 lockdep 表达式,并且如果 rcu_read_lock() 和指示的保护都不存在,则会发出 lockdep splat。此外,rcu_dereference_raw() 用于那些(希望罕见的)无法轻松描述所需保护的情况。最后,提供了 rcu_read_lock_held(),以允许函数验证它是否已在 RCU 读端临界区内被调用。在 Thomas Gleixner 审核了一些 RCU 用法后不久,我就意识到了这一组要求。

  2. 给定的函数可能希望在进入时检查与 RCU 相关的先决条件,然后再使用任何其他 RCU API。rcu_lockdep_assert() 完成此工作,在启用了 lockdep 的内核中断言表达式,否则不执行任何操作。

  3. 也很容易忘记使用 rcu_assign_pointer()rcu_dereference(),可能(错误地)用简单的赋值替换。为了捕获这种错误,可以使用 __rcu 标记给定的 RCU 保护的指针,之后,sparse 将抱怨对该指针的简单赋值访问。Arnd Bergmann 让我意识到了此要求,并提供了所需的 补丁系列

  4. 使用 CONFIG_DEBUG_OBJECTS_RCU_HEAD=y 构建的内核如果一个数据元素连续两次传递给 call_rcu(),并且两次调用之间没有宽限期,则会崩溃。(此错误类似于双重释放。)动态分配的相应 rcu_head 结构会自动跟踪,但是分配在堆栈上的 rcu_head 结构必须使用 init_rcu_head_on_stack() 初始化,并使用 destroy_rcu_head_on_stack() 清理。同样,静态分配的非堆栈 rcu_head 结构必须使用 init_rcu_head() 初始化,并使用 destroy_rcu_head() 清理。Mathieu Desnoyers 让我意识到了此要求,并提供了所需的 补丁

  5. RCU 读端临界区中的无限循环最终将触发 RCU CPU stall 警告 splat,其中“最终”的持续时间由 RCU_CPU_STALL_TIMEOUT Kconfig 选项控制,或者由 rcupdate.rcu_cpu_stall_timeout 启动/sysfs 参数控制。但是,除非有宽限期等待该特定的 RCU 读端临界区,否则 RCU 没有义务生成此 splat。

    某些极端工作负载可能会有意延迟 RCU 宽限期,并且运行这些工作负载的系统可以使用 rcupdate.rcu_cpu_stall_suppress 启动,以抑制 splat。此内核参数也可以通过 sysfs 设置。此外,RCU CPU stall 警告在 sysrq 转储和 panic 期间会适得其反。因此,RCU 提供了 rcu_sysrq_start() 和 rcu_sysrq_end() API 成员,以便在长时间的 sysrq 转储之前和之后调用。RCU 还提供了 rcu_panic() 通知程序,该通知程序会在 panic 开始时自动调用,以抑制进一步的 RCU CPU stall 警告。

    早在 1990 年代初,当需要调试 CPU stall 时,就知道了此要求。也就是说,与 Linux 相比,DYNIX/ptx 中的初始实现非常通用。

  6. 尽管检测指针从 RCU 读端临界区泄漏出来非常好,但目前没有好的方法可以做到这一点。一个复杂因素是需要区分指针泄漏和已从 RCU 移交给其他同步机制的指针,例如,引用计数。

  7. 在使用 CONFIG_RCU_TRACE=y 构建的内核中,通过事件跟踪提供与 RCU 相关的信息。

  8. 使用 rcu_assign_pointer()rcu_dereference() 来创建典型的链接数据结构可能会非常容易出错。因此,RCU 保护的 链表 和最近 RCU 保护的 哈希表 可用。Linux 内核和用户空间 RCU 库中提供了许多其他专用 RCU 保护的数据结构。

  9. 某些链接结构是在编译时创建的,但仍然需要 __rcu 检查。RCU_POINTER_INITIALIZER() 宏用于此目的。

  10. 创建要通过单个外部指针发布的链接结构时,无需使用 rcu_assign_pointer()。为此任务提供了 RCU_INIT_POINTER() 宏。

这不是一个硬性列表:RCU 的诊断能力将继续受到在实际 RCU 使用中发现的用法错误的数量和类型的指导。

Linux 内核的复杂性

Linux 内核为各种软件(包括 RCU)提供了一个有趣的环境。以下是一些相关的兴趣点

  1. 配置

  2. 固件接口

  3. 早期启动

  4. 中断和 NMI

  5. 可加载模块

  6. 热插拔 CPU

  7. 调度程序和 RCU

  8. 跟踪和 RCU

  9. 对用户内存和 RCU 的访问

  10. 能源效率

  11. 调度时钟中断和 RCU

  12. 内存效率

  13. 性能、可伸缩性、响应时间和可靠性

此列表可能不完整,但它确实给出了最值得注意的 Linux 内核复杂性的感觉。以下每个部分都涵盖了上述主题之一。

配置

RCU 的目标是自动配置,因此几乎没有人需要担心 RCU 的 Kconfig 选项。对于几乎所有用户来说,RCU 实际上都可以很好地“开箱即用”。

但是,有些专门的用例由内核启动参数和 Kconfig 选项处理。不幸的是,Kconfig 系统会明确地询问用户新的 Kconfig 选项,这要求几乎所有这些选项都隐藏在 CONFIG_RCU_EXPERT Kconfig 选项后面。

这一切应该非常明显,但事实仍然是 Linus Torvalds 最近不得不 提醒 我这个要求。

固件接口

在许多情况下,内核从固件获取有关系统的信息,有时信息会在翻译过程中丢失。或者翻译是准确的,但原始消息是伪造的。

例如,某些系统的固件会过度报告 CPU 的数量,有时会过度报告很大。如果 RCU 天真地相信固件(就像以前那样),它将创建太多的每个 CPU 的 kthread。尽管生成的系统仍然可以正确运行,但额外的 kthread 会不必要地消耗内存,并且当它们出现在 ps 列表中时可能会引起混乱。

因此,RCU 必须等待给定的 CPU 实际上线,然后才能允许自己相信该 CPU 确实存在。由此产生的“幽灵 CPU”(永远不会上线)会导致许多 有趣的复杂情况

早期启动

Linux 内核的启动序列是一个有趣的过程,RCU 甚至在调用 rcu_init() 之前就被早期使用。事实上,只要初始任务的 task_struct 可用并且启动 CPU 的每个 CPU 变量都已设置,就可以使用许多 RCU 的原语。读端原语(rcu_read_lock()rcu_read_unlock()rcu_dereference()rcu_access_pointer())将在早期正常运行,rcu_assign_pointer() 也是如此。

尽管可以在启动期间的任何时间调用 call_rcu(),但在生成所有 RCU 的 kthread 之后,才能保证调用回调函数,这发生在 early_initcall() 时。回调函数调用的延迟是由于 RCU 在完全初始化后才调用回调函数,并且在调度程序将其自身初始化到 RCU 可以生成和运行其 kthread 的程度之前,无法进行此完全初始化。从理论上讲,可以更早地调用回调函数,但是,这不是万灵药,因为对这些回调函数可以调用的操作将有严格的限制。

也许令人惊讶的是,synchronize_rcu()synchronize_rcu_expedited() 将在非常早期的启动期间正常运行,原因是只有一个 CPU 并且禁用了抢占。这意味着调用 synchronize_rcu()(或其友元)本身是一个静止状态,因此是一个宽限期,因此早期启动实现可以是一个空操作。

但是,一旦调度程序生成了它的第一个 kthread,此早期启动技巧对于 CONFIG_PREEMPTION=y 内核中的 synchronize_rcu()(以及 synchronize_rcu_expedited()) 失败。原因是 RCU 读端临界区可能会被抢占,这意味着随后的 synchronize_rcu() 确实必须等待某些东西,而不是简单地立即返回。不幸的是,在生成所有 kthread 之前,synchronize_rcu() 无法做到这一点,直到 early_initcalls() 时才发生。但这并不是借口:尽管如此,RCU 仍然需要在此时段内正确处理同步宽限期。一旦所有 kthread 都启动并运行,RCU 就会开始正常运行。

小测验:

在生成 RCU 的所有 kthread 之前,RCU 如何可能处理宽限期???

答案:

非常小心!在调度程序生成第一个任务到生成 RCU 的所有 kthread 之间的“死区”期间,所有同步宽限期都由加速的宽限期机制处理。在运行时,此加速机制依赖于工作队列,但在死区期间,请求任务本身会驱动所需的加速宽限期。由于死区执行发生在任务上下文中,因此一切正常。一旦死区结束,加速宽限期将恢复为使用工作队列,这是避免用户任务在驱动加速宽限期时收到 POSIX 信号时可能发生的问题所必需的。

是的,这确实意味着在调度程序生成其第一个 kthread 到 RCU 的所有 kthread 都已生成之间的这段时间内,向随机任务发送 POSIX 信号是没有帮助的。如果将来发现有充分的理由在此期间发送 POSIX 信号,则将进行适当的调整。(如果发现在此期间发送 POSIX 信号没有充分的理由,则将进行其他调整,适当与否。)

我从一系列系统挂起中了解了这些启动时间要求。

中断和 NMI

Linux 内核具有中断,并且 RCU 读端临界区在中断处理程序和代码的禁用中断区域内是合法的,调用 call_rcu() 也是如此。

某些 Linux 内核体系结构可以从非空闲进程上下文中进入中断处理程序,然后永远不会离开它,而是偷偷地转换回进程上下文。有时使用此技巧从内核内部调用系统调用。这些“半中断”意味着 RCU 必须非常小心地计算中断嵌套级别。在重写 RCU 的 dyntick-idle 代码期间,我以惨痛的方式了解了此要求。

Linux 内核具有不可屏蔽中断 (NMI),并且 RCU 读端临界区在 NMI 处理程序内是合法的。值得庆幸的是,禁止在 NMI 处理程序内使用 RCU 更新端原语,包括 call_rcu()

尽管名称如此,但某些 Linux 内核体系结构可以具有嵌套的 NMI,RCU 必须正确处理。Andy Lutomirski 让我感到惊讶,他提出了此要求;他还好心地 惊讶地向我提出了一种算法,该算法满足此要求。

此外,NMI 处理程序可能会被 RCU 认为是正常中断的中断。发生这种情况的一种方法是从 NMI 处理程序中调用直接调用 ct_irq_enter() 和 ct_irq_exit() 的代码。这个令人震惊的事实促使了当前的代码结构,该结构具有 ct_irq_enter() 调用 ct_nmi_enter() 和 ct_irq_exit() 调用 ct_nmi_exit()。是的,我也以惨痛的方式了解了此要求。

可加载模块

Linux 内核具有可加载模块,并且这些模块也可以卸载。卸载给定的模块后,任何尝试调用其函数的尝试都会导致段错误。因此,模块卸载函数必须取消对可加载模块函数的任何延迟调用,例如,必须通过 timer_shutdown_sync() 或类似方法处理任何未完成的 mod_timer()

不幸的是,没有办法取消 RCU 回调函数;一旦你调用 call_rcu(),最终将调用回调函数,除非系统首先崩溃。因为通常认为响应模块卸载请求而使系统崩溃是不负责任的,所以我们需要一些其他方法来处理正在进行的 RCU 回调函数。

因此,RCU 提供了 rcu_barrier(),它会一直等待,直到所有正在进行的 RCU 回调函数都被调用。如果一个模块使用 call_rcu(),它的退出函数应该阻止将来调用 call_rcu(),然后调用 rcu_barrier()。从理论上讲,底层模块卸载代码可以无条件地调用 rcu_barrier(),但在实践中,这会产生不可接受的延迟。

Nikita Danilov 注意到了一个类似的文件系统卸载情况的此要求,Dipankar Sarma 将 rcu_barrier() 合并到 RCU 中。后来才发现模块卸载需要 rcu_barrier()

重要

rcu_barrier() 函数没有义务等待宽限期,重复一遍,没有 义务。相反,它只需要等待已经发布的 RCU 回调函数。因此,如果系统中没有发布任何 RCU 回调函数,rcu_barrier() 有权立即返回。即使发布了回调函数,rcu_barrier() 也不一定需要等待宽限期。

小测验:

等一下!每个 RCU 回调函数必须等待一个宽限期才能完成,并且 rcu_barrier() 必须等待每个预先存在的回调函数被调用。因此,如果系统中的任何地方存在一个回调函数,rcu_barrier() 不是需要等待一个完整的宽限期吗?

答案:

绝对不是!!!是的,每个 RCU 回调函数必须等待一个宽限期才能完成,但在调用 rcu_barrier() 时,它可能已经部分(甚至完全)完成了等待。在这种情况下,rcu_barrier() 只需要等待宽限期的剩余部分流逝。因此,即使发布了相当多的回调函数,rcu_barrier() 也可能会很快返回。

因此,如果您需要等待宽限期以及所有预先存在的回调函数,您将需要同时调用 synchronize_rcu()rcu_barrier()。如果延迟是一个问题,您可以始终使用工作队列来并发地调用它们。

热插拔 CPU

Linux 内核支持 CPU 热插拔,这意味着 CPU 可以来来去去。从离线 CPU 使用任何 RCU API 成员当然是非法的,除了 SRCU 读端临界区。这个要求从 DYNIX/ptx 的第一天就存在了,但另一方面,Linux 内核的 CPU 热插拔实现是“有趣的”。

Linux 内核的 CPU 热插拔实现具有通知器,用于允许各种内核子系统(包括 RCU)对给定的 CPU 热插拔操作做出适当的响应。大多数 RCU 操作可以从 CPU 热插拔通知器调用,甚至包括同步宽限期操作,例如 (synchronize_rcu()synchronize_rcu_expedited())。但是,这些同步操作会阻塞,因此不能从通过 stop_machine() 执行的通知器中调用,特别是那些在 CPUHP_AP_OFFLINECPUHP_AP_ONLINE 状态之间的通知器。

此外,所有回调等待操作(例如 rcu_barrier())不得从任何 CPU 热插拔通知器中调用。此限制是由于 CPU 热插拔操作的某些阶段,传出 CPU 的回调函数直到 CPU 热插拔操作结束后才会被调用,这也可能导致死锁。此外,rcu_barrier() 在执行期间会阻止 CPU 热插拔操作,这会导致从 CPU 热插拔通知器调用时出现另一种类型的死锁。

最后,RCU 必须避免由于热插拔、定时器和宽限期处理之间的交互而导致的死锁。它通过维护自己的书籍来复制集中维护的 cpu_online_mask,并且还在 CPU 离线时显式报告静止状态。这种显式报告静止状态避免了强制静止状态循环 (FQS) 报告离线 CPU 的静止状态。但是,作为一种调试措施,如果离线 CPU 阻塞 RCU 宽限期过长,FQS 循环会崩溃。

离线 CPU 的静止状态将被报告为

  1. 当 CPU 使用 RCU 的热插拔通知器 (rcutree_report_cpu_dead()) 离线时。

  2. 当宽限期初始化 (rcu_gp_init()) 检测到与 CPU 离线或与任务在叶子 rcu_node 结构上解除阻塞的竞争时,其中叶子 rcu_node 结构的所有 CPU 均已离线。

CPU 在线路径 (rcutree_report_cpu_starting()) 永远不需要报告离线 CPU 的静止状态。但是,作为一种调试措施,如果尚未为该 CPU 报告静止状态,它会发出警告。

在检查/修改 RCU 的热插拔簿记期间,将持有相应 CPU 的叶子节点锁。这避免了 RCU 的热插拔通知器挂钩、宽限期初始化代码和 FQS 循环之间的竞争条件,所有这些都引用或修改此簿记。

调度器和 RCU

RCU 使用 kthreads,并且有必要避免这些 kthreads 过度累积 CPU 时间。这个要求并不令人意外,但当使用 CONFIG_NO_HZ_FULL=y 构建且运行上下文切换繁重的工作负载时,RCU 违反了该要求,这 确实令人惊讶 [PDF]。 RCU 在满足此要求方面取得了良好进展,即使对于上下文切换繁重的 CONFIG_NO_HZ_FULL=y 工作负载也是如此,但仍有进一步改进的空间。

rcu_read_unlock() 上持有任何调度器的运行队列或优先级继承自旋锁不再有任何禁止,即使在相应 RCU 读端临界区的某个地方启用了中断和抢占。因此,现在可以完全合法地在启用抢占的情况下执行 rcu_read_lock(),获取其中一个调度器锁,并在匹配的 rcu_read_unlock() 上持有该锁。

类似地,RCU 风味整合消除了对负嵌套的需求。代码的禁用中断区域隐式地充当 RCU 读端临界区,从而避免了早期通过中断处理程序使用 RCU 导致破坏性递归的问题。

跟踪和 RCU

可以在 RCU 代码上使用跟踪,但跟踪本身使用 RCU。因此,提供了 rcu_dereference_raw_check() 以供跟踪使用,这避免了可能随之而来的破坏性递归。一些架构中的虚拟化也使用此 API,其中 RCU 读取器在无法使用跟踪的环境中执行。跟踪人员找到了需求并提供了所需的修复,因此这个令人惊讶的需求相对来说是毫不费力的。

访问用户内存和 RCU

内核需要访问用户空间内存,例如,访问系统调用参数引用的数据。get_user() 宏执行此作业。

但是,用户空间内存很可能已分页到磁盘,这意味着 get_user() 很可能会发生页面错误,因此在等待生成的 I/O 完成时会阻塞。编译器将 get_user() 调用重新排序到 RCU 读端临界区中将是一件非常糟糕的事情。

例如,假设源代码如下所示

1 rcu_read_lock();
2 p = rcu_dereference(gp);
3 v = p->value;
4 rcu_read_unlock();
5 get_user(user_v, user_p);
6 do_something_with(v, user_v);

不允许编译器将此源代码转换为以下内容

1 rcu_read_lock();
2 p = rcu_dereference(gp);
3 get_user(user_v, user_p); // BUG: POSSIBLE PAGE FAULT!!!
4 v = p->value;
5 rcu_read_unlock();
6 do_something_with(v, user_v);

如果编译器在 CONFIG_PREEMPTION=n 内核版本中进行了此转换,并且如果 get_user() 确实发生了页面错误,则结果将是在 RCU 读端临界区中间的静止状态。这个错位的静止状态可能导致第 4 行是使用后释放访问,这对您内核的精算统计数据可能是不利的。可以使用对 get_user() 的调用在 rcu_read_lock() 之前来构建类似的示例。

不幸的是,get_user() 没有任何特定的排序属性,并且在某些架构中,底层 asm 甚至没有标记为 volatile。即使它被标记为 volatile,上面对 p->value 的访问也不是 volatile,因此编译器没有任何理由保持这两个访问的顺序。

因此,rcu_read_lock()rcu_read_unlock() 的 Linux 内核定义必须充当编译器屏障,至少对于嵌套 RCU 读端临界区集合中的最外层 rcu_read_lock()rcu_read_unlock() 实例。

能源效率

中断空闲 CPU 被认为是社会上不可接受的,尤其是对于具有电池供电嵌入式系统的人们。因此,RCU 通过检测哪些 CPU 处于空闲状态来节省能源,包括跟踪已从空闲状态中断的 CPU。这是能源效率要求的大部分,所以我通过愤怒的电话了解到了这一点。

因为 RCU 避免中断空闲 CPU,所以在空闲 CPU 上执行 RCU 读端临界区是非法的。(使用 CONFIG_PROVE_RCU=y 构建的内核会在您尝试时崩溃。)

类似地,中断在用户空间中运行的 nohz_full CPU 在社会上也是不可接受的。因此,RCU 必须跟踪 nohz_full 用户空间执行。因此,RCU 必须能够对两个时间点上的状态进行采样,并且能够确定是否有任何其他 CPU 花费任何时间处于空闲状态和/或在用户空间中执行。

这些能源效率要求已被证明非常难以理解和满足,例如,RCU 的能源效率代码已经有超过五次的全新重写,其中最后一次终于能够证明 在真实硬件上运行的真实节能 [PDF]。如前所述,我通过愤怒的电话了解到了许多这些要求:在 Linux 内核邮件列表上火焰攻击我显然不足以充分发泄他们对 RCU 能源效率错误的愤怒!

调度时钟中断和 RCU

内核在内核非空闲执行、用户空间执行和空闲循环之间转换。根据内核配置,RCU 以不同的方式处理这些状态

HZ Kconfig

内核中

用户模式

空闲

HZ_PERIODIC

可以依赖调度时钟中断。

可以依赖调度时钟中断及其对用户模式中断的检测。

可以依赖 RCU 的 dyntick-idle 检测。

NO_HZ_IDLE

可以依赖调度时钟中断。

可以依赖调度时钟中断及其对用户模式中断的检测。

可以依赖 RCU 的 dyntick-idle 检测。

NO_HZ_FULL

只能有时依赖调度时钟中断。在其他情况下,有必要限制内核执行时间和/或使用 IPI。

可以依赖 RCU 的 dyntick-idle 检测。

可以依赖 RCU 的 dyntick-idle 检测。

小测验:

为什么 NO_HZ_FULL 内核中执行不能像 HZ_PERIODICNO_HZ_IDLE 那样依赖调度时钟中断?

答案:

因为,作为一种性能优化,NO_HZ_FULL 不一定会在每次进入系统调用时重新启用调度时钟中断。

但是,必须可靠地告知 RCU 任何给定的 CPU 当前是否处于空闲循环中,并且对于 NO_HZ_FULL,还要告知该 CPU 是否在用户模式下执行,如 前面 所讨论的。它还需要在 RCU 需要时启用调度时钟中断

  1. 如果 CPU 处于空闲状态或在用户模式下执行,并且 RCU 认为它处于非空闲状态,则调度时钟节拍最好正在运行。否则,您将收到 RCU CPU 停顿警告。或者充其量,非常长(11 秒)的宽限期,并且不时地发出无意义的 IPI 以唤醒 CPU。

  2. 如果 CPU 处于内核中执行 RCU 读端临界区的部分,并且 RCU 认为此 CPU 处于空闲状态,您将得到随机的内存损坏。不要这样做!!! 这是使用 lockdep 进行测试的原因之一,它会抱怨这类事情。

  3. 如果 CPU 处于内核的某个部分,该部分绝对保证绝不会执行任何 RCU 读端临界区,并且 RCU 认为此 CPU 处于空闲状态,则没有问题。某些架构将此类事情用于轻量级异常处理程序,然后可以避免在异常进入和退出时分别使用 ct_irq_enter() 和 ct_irq_exit() 的开销。有些人更进一步,避免使用整个 irq_enter() 和 irq_exit()。只需确保您使用 CONFIG_PROVE_RCU=y 运行一些测试,以防万一您的某个代码路径实际上是在开玩笑说不执行 RCU 读端临界区。

  4. 如果 CPU 在内核中使用调度时钟中断被禁用的情况下执行,并且 RCU 认为此 CPU 处于非空闲状态,并且如果 CPU 每隔几个节拍(从 RCU 的角度来看)就变为空闲状态,则没有问题。通常可以接受空闲周期之间偶尔出现长达一秒左右的间隔。如果间隔变得太长,您将收到 RCU CPU 停顿警告。

  5. 如果 CPU 处于空闲状态或在用户模式下执行,并且 RCU 认为它处于空闲状态,则当然没有问题。

  6. 如果 CPU 在内核中执行,内核代码路径正在以合理的频率通过静止状态(最好大约每几个节拍一次,但偶尔超出到一秒左右通常是可以的),并且调度时钟中断已启用,则当然没有问题。如果连续一对静止状态之间的间隔变得太长,您将收到 RCU CPU 停顿警告。

小测验:

但是,如果我的驱动程序有一个硬件中断处理程序,可以运行数秒?毕竟,我无法从硬件中断处理程序中调用 schedule()!

答案:

一种方法是每隔一段时间执行 ct_irq_exit();ct_irq_enter();。但是,鉴于长时间运行的中断处理程序可能会导致其他问题,尤其是对于响应时间,您不应该努力将中断处理程序的运行时保持在合理的范围内吗?

但是,只要正确告知 RCU 内核状态在内核中执行、用户模式执行和空闲之间的转换,并且只要在 RCU 需要时启用调度时钟中断,您就可以放心,您遇到的错误将在 RCU 的其他部分或内核的其他部分中!

内存效率

虽然小内存非实时系统可以简单地使用 Tiny RCU,但代码大小只是内存效率的一个方面。另一方面是 call_rcu()kfree_rcu() 使用的 rcu_head 结构的大小。虽然此结构仅包含一对指针,但它确实出现在许多受 RCU 保护的数据结构中,包括一些对大小至关重要的结构。page 结构就是一个例子,正如该结构中多次出现 union 关键字所证明的那样。

这种对内存效率的需求是 RCU 使用手工制作的单链表来跟踪等待宽限期流逝的 rcu_head 结构的原因之一。这也是 rcu_head 结构不包含调试信息的原因,例如跟踪 call_rcu()kfree_rcu()(发布它们)的文件和行的字段。虽然此信息可能会在调试专用内核版本中的某个时间点出现,但与此同时,->func 字段通常会提供所需的调试信息。

但是,在某些情况下,对内存效率的需求会导致更极端的措施。回到 page 结构,rcu_head 字段与在相应页面的生命周期的各个点使用的许多其他结构共享存储空间。为了正确解决某些 竞争条件,Linux 内核的内存管理子系统需要一个特定的位在宽限期处理的所有阶段都保持为零,并且该位恰好映射到 rcu_head 结构的 ->next 字段的底部位。只要使用 call_rcu() 来发布回调(而不是 kfree_rcu() 或未来可能有一天为提高能源效率而创建的 call_rcu() 的某些“延迟”变体),RCU 就可以保证这一点。

也就是说,存在限制。RCU 要求 rcu_head 结构与两字节边界对齐,并且将未对齐的 rcu_head 结构传递给 call_rcu() 系列函数中的一个将导致崩溃。因此,在打包包含 rcu_head 类型字段的结构时,必须谨慎。为什么不是四字节甚至八字节的对齐要求?因为 m68k 架构仅提供两字节对齐,因此充当对齐的最小公分母。

保留指向 rcu_head 结构的指针的底部位的原因是为可以安全延迟调用的“延迟”回调打开大门。延迟调用可能会带来能源效率方面的好处,但前提是对于某些重要的工作负载,非延迟回调的速率显着降低。与此同时,保留底部位可以使此选项保持打开状态,以防有一天它变得有用。

性能、可伸缩性、响应时间和可靠性

扩展 先前讨论,RCU 被 Linux 内核的网络、安全、虚拟化和调度代码路径中对性能至关重要的部分中的热代码路径大量使用。因此,RCU 必须使用高效的实现,尤其是在其读端原语中。为此,如果可抢占 RCU 的 rcu_read_lock() 实现可以内联,那就太好了,但是,这样做需要解决与 task_struct 结构相关的 #include 问题。

Linux 内核支持具有多达 4096 个 CPU 的硬件配置,这意味着 RCU 必须具有极强的可伸缩性。频繁获取全局锁或频繁对全局变量执行原子操作的算法在 RCU 实现中是完全无法容忍的。因此,RCU 大量使用基于 rcu_node 结构的组合树。RCU 需要容忍所有 CPU 持续调用 RCU 的运行时原语的任何组合,并且每个操作的开销最小。事实上,在许多情况下,增加负载必须降低每个操作的开销,参见 synchronize_rcu()call_rcu()synchronize_rcu_expedited()rcu_barrier() 的批处理优化。通常,RCU 必须愉快地接受 Linux 内核的其余部分决定抛给它的任何东西。

Linux 内核用于实时工作负载,特别是与 -rt 补丁集 结合使用。实时延迟响应要求是,跨 RCU 读端临界区禁用抢占的传统方法是不合适的。因此,使用 CONFIG_PREEMPTION=y 构建的内核使用一种 RCU 实现,该实现允许抢占 RCU 读端临界区。在使用户明确表示早期的 实时补丁 无法满足他们的需求之后,出现了这一要求,并结合了 -rt 补丁集的早期版本遇到的一些 RCU 问题

此外,RCU 必须在低于 100 微秒的实时延迟预算内完成。事实上,在具有 -rt 补丁集的小型系统上,Linux 内核为包括 RCU 在内的整个内核提供低于 20 微秒的实时延迟。因此,RCU 的可伸缩性和延迟必须足以满足这些类型的配置。令我惊讶的是,低于 100 微秒的实时延迟预算 甚至适用于最大的系统 [PDF],包括具有 4096 个 CPU 的系统。这种实时需求促使了宽限期 kthread 的出现,这也简化了许多竞争条件的处理。

RCU 必须避免降低 CPU 密集型线程的实时响应,无论是在用户模式下执行(这是 CONFIG_NO_HZ_FULL=y 的一种用例)还是在内核中。也就是说,内核中的 CPU 密集型循环必须至少每几十毫秒执行一次 cond_resched(),以避免收到来自 RCU 的 IPI。

最后,RCU 作为同步原语的状态意味着任何 RCU 故障都可能导致任意内存损坏,这可能非常难以调试。这意味着 RCU 必须非常可靠,这在实践中也意味着 RCU 必须具有积极的压力测试套件。此压力测试套件称为 rcutorture

虽然对 rcutorture 的需求并不令人意外,但当前 Linux 内核的巨大受欢迎程度正在带来有趣且可能前所未有的验证挑战。要了解这一点,请记住,考虑到 Android 智能手机、Linux 驱动的电视和服务器,如今运行的 Linux 内核实例已超过 10 亿个。随着著名的物联网的出现,预计这个数字会急剧增加。

假设 RCU 中存在一个竞争条件,平均每百万年运行时才会出现一次。那么,在已安装的设备中,这个 bug 大约每天会发生三次。RCU 可以简单地隐藏在硬件错误率之下,因为没有人真的期望他们的智能手机能使用一百万年。然而,任何对此想法感到过于安慰的人都应该考虑到,在大多数司法管辖区,对给定机制(可能包括 Linux 内核)进行成功的多年测试,足以获得多种类型的安全关键认证。事实上,有传言说 Linux 内核已经在生产中用于安全关键型应用。我不知道你怎么想,但如果 RCU 中的一个 bug 导致有人死亡,我会感到非常难过。这可能解释了我最近对验证和确认的关注。

其他 RCU 变体

关于 RCU,更令人惊讶的事情之一是,现在至少有五种 变体 或 API 系列。此外,到目前为止,唯一关注的主要变体有两种不同的实现方式:不可抢占式和可抢占式。其他四种变体如下所列,每种变体的要求将在单独的章节中进行描述。

  1. Bottom-Half 变体(历史)

  2. Sched 变体(历史)

  3. 可睡眠 RCU

  4. Tasks RCU

  5. Tasks Trace RCU

Bottom-Half 变体(历史)

作为将三个变体整合为单个变体的一部分,RCU-bh 变体已经用其他 RCU 变体来表示。读取端 API 仍然存在,并且仍然禁用 softirq 并由 lockdep 记录。因此,本节中的大部分内容本质上是历史性的。

softirq-disable(又名 “bottom-half”,因此缩写为 “_bh”)RCU 变体,或 RCU-bh,由 Dipankar Sarma 开发,旨在提供一种可以承受 Robert Olsson 研究的基于网络的拒绝服务攻击的 RCU 变体。这些攻击给系统带来了如此多的网络负载,以至于某些 CPU 永远不会退出 softirq 执行,进而阻止这些 CPU 执行上下文切换,而在当时的 RCU 实现中,这阻止了宽限期的结束。结果是内存不足的情况和系统挂起。

解决方案是创建 RCU-bh,它在其读取端关键部分执行 local_bh_disable(),并且除了上下文切换、空闲、用户模式和离线之外,还使用从一种类型的 softirq 处理到另一种类型的转换作为静止状态。这意味着即使某些 CPU 无限期地在 softirq 中执行,RCU-bh 宽限期也可以完成,从而允许基于 RCU-bh 的算法承受基于网络的拒绝服务攻击。

由于 rcu_read_lock_bh()rcu_read_unlock_bh() 禁用和重新启用 softirq 处理程序,因此在 RCU-bh 读取端关键部分启动 softirq 处理程序的任何尝试都将被延迟。在这种情况下,rcu_read_unlock_bh() 将调用 softirq 处理,这可能需要相当长的时间。当然,可以争辩说,这种 softirq 开销应该与 RCU-bh 读取端关键部分后面的代码相关联,而不是 rcu_read_unlock_bh(),但事实是,大多数分析工具都不能指望做出这种精细的区分。例如,假设一个三毫秒长的 RCU-bh 读取端关键部分在网络负载很重的时间内执行。很可能会尝试在该三毫秒内调用至少一个 softirq 处理程序,但任何此类调用都将被延迟到 rcu_read_unlock_bh() 时。这当然可能乍一看好像 rcu_read_unlock_bh() 执行得非常慢。

RCU-bh API 包括 rcu_read_lock_bh(), rcu_read_unlock_bh(), rcu_dereference_bh(), rcu_dereference_bh_check(), 和 rcu_read_lock_bh_held()。但是,旧的 RCU-bh 更新端 API 现在已经消失,取而代之的是 synchronize_rcu(), synchronize_rcu_expedited(), call_rcu(), 和 rcu_barrier()。此外,任何禁用 bottom halves 的操作也标记了一个 RCU-bh 读取端关键部分,包括 local_bh_disable() 和 local_bh_enable()、local_irq_save() 和 local_irq_restore() 等。

Sched 变体(历史)

作为将三个变体整合为单个变体的一部分,RCU-sched 变体已经用其他 RCU 变体来表示。读取端 API 仍然存在,并且继续禁用抢占并由 lockdep 记录。因此,本节中的大部分内容本质上是历史性的。

在可抢占 RCU 之前,等待 RCU 宽限期也具有等待所有预先存在的中断和 NMI 处理程序的副作用。但是,存在不具有此属性的合法的可抢占 RCU 实现,因为 RCU 读取端关键部分之外的任何代码点都可以是静止状态。因此,创建了 RCU-sched,它遵循 “经典” RCU,即 RCU-sched 宽限期等待预先存在的中断和 NMI 处理程序。在使用 CONFIG_PREEMPTION=n 构建的内核中,RCU 和 RCU-sched API 具有相同的实现,而使用 CONFIG_PREEMPTION=y 构建的内核为每个 API 提供单独的实现。

请注意,在 CONFIG_PREEMPTION=y 内核中,rcu_read_lock_sched()rcu_read_unlock_sched() 分别禁用和重新启用抢占。这意味着如果在 RCU-sched 读取端关键部分期间发生抢占尝试,rcu_read_unlock_sched() 将进入调度程序,并带来所有延迟和开销。正如 rcu_read_unlock_bh() 一样,这可以使它看起来好像 rcu_read_unlock_sched() 执行得非常慢。但是,最高优先级的任务不会被抢占,因此该任务将享受低开销的 rcu_read_unlock_sched() 调用。

RCU-sched API 包括 rcu_read_lock_sched(), rcu_read_unlock_sched(), rcu_read_lock_sched_notrace(), rcu_read_unlock_sched_notrace(), rcu_dereference_sched(), rcu_dereference_sched_check(), 和 rcu_read_lock_sched_held()。但是,旧的 RCU-sched 更新端 API 现在已经消失,取而代之的是 synchronize_rcu(), synchronize_rcu_expedited(), call_rcu(), 和 rcu_barrier()。此外,任何禁用抢占的操作也标记了一个 RCU-sched 读取端关键部分,包括 preempt_disable() 和 preempt_enable()、local_irq_save() 和 local_irq_restore() 等。

可睡眠 RCU

十多年来,有人说 “我需要在 RCU 读取端关键部分内阻塞” 是一个可靠的迹象,表明此人不理解 RCU。毕竟,如果您总是在 RCU 读取端关键部分中阻塞,那么您可能可以使用更高开销的同步机制。但是,随着 Linux 内核的通知程序的出现,这种情况发生了变化,通知程序的 RCU 读取端关键部分几乎从不睡眠,但有时需要睡眠。这导致了 可睡眠 RCUSRCU 的引入。

SRCU 允许定义不同的域,每个域都由 srcu_struct 结构的实例定义。指向此结构的指针必须传递给每个 SRCU 函数,例如,synchronize_srcu(&ss),其中 sssrcu_struct 结构。这些域的关键好处是,一个域中的慢速 SRCU 读取器不会延迟某些其他域中的 SRCU 宽限期。也就是说,这些域的一个结果是,读取端代码必须将 “cookie” 从 srcu_read_lock() 传递到 srcu_read_unlock(),例如,如下所示

1 int idx;
2
3 idx = srcu_read_lock(&ss);
4 do_something();
5 srcu_read_unlock(&ss, idx);

如上所述,在 SRCU 读取端关键部分内阻塞是合法的,但是,强大的力量伴随着巨大的责任。如果您在给定域的 SRCU 读取端关键部分之一中永久阻塞,那么该域的宽限期也将被永久阻塞。当然,永久阻塞的一个好方法是死锁,如果给定域的 SRCU 读取端关键部分中的任何操作可以直接或间接地等待该域的宽限期到期,则可能会发生死锁。例如,这将导致自死锁

1 int idx;
2
3 idx = srcu_read_lock(&ss);
4 do_something();
5 synchronize_srcu(&ss);
6 srcu_read_unlock(&ss, idx);

但是,如果第 5 行获取了一个互斥锁,该互斥锁在 ss 域的 synchronize_srcu() 中持有,仍然可能发生死锁。此外,如果第 5 行获取了一个互斥锁,该互斥锁在某些其他域 ss1synchronize_srcu() 中持有,并且如果 ss1 域 SRCU 读取端关键部分获取了另一个互斥锁,该互斥锁在 sssynchronize_srcu() 中持有,则可能再次发生死锁。这样的死锁循环可以跨越任意数量的不同 SRCU 域。再次,强大的力量伴随着巨大的责任。

与其他 RCU 变体不同,SRCU 读取端关键部分可以在空闲甚至离线 CPU 上运行。此功能要求 srcu_read_lock()srcu_read_unlock() 包含内存屏障,这意味着 SRCU 读取器将比 RCU 读取器运行得慢一些。这也激发了 smp_mb__after_srcu_read_unlock() API,它与 srcu_read_unlock() 结合使用,保证了完整的内存屏障。

同样与其他 RCU 变体不同,由于 SRCU 宽限期使用计时器以及计时器暂时 “滞留” 在传出 CPU 上的可能性,因此 不能 从 CPU 热插拔通知程序调用 synchronize_srcu()。计时器的这种滞留意味着发布到传出 CPU 的计时器将不会触发,直到 CPU 热插拔过程的后期。问题是,如果通知程序正在等待 SRCU 宽限期,则该宽限期正在等待计时器,并且该计时器滞留在传出 CPU 上,那么通知程序将永远不会被唤醒,换句话说,发生了死锁。当然,这种相同的情况也禁止从 CPU 热插拔通知程序调用 srcu_barrier()

SRCU 与其他 RCU 变体的不同之处还在于,SRCU 的加速和非加速宽限期由相同的机制实现。这意味着在当前的 SRCU 实现中,加速未来的宽限期具有加速所有尚未完成的先前宽限期的副作用。(但请注意,这是当前实现的属性,不一定是未来实现的属性。)此外,如果 SRCU 处于空闲状态的时间长于 srcutree.exp_holdoff 内核引导参数(默认情况下为 25 微秒)指定的时间间隔,并且 synchronize_srcu() 调用结束了此空闲期,则该调用将自动加速。

从 v4.12 开始,SRCU 的回调按 CPU 维护,消除了先前内核版本中存在的锁定瓶颈。尽管这将允许用户对 call_srcu() 施加更大的压力,但重要的是要注意 SRCU 尚未采取任何特殊措施来处理回调洪水。因此,如果您每秒每个 CPU 发布(例如)10,000 个 SRCU 回调,那么您可能完全没问题,但如果您打算每秒每个 CPU 发布(例如)1,000,000 个 SRCU 回调,请先运行一些测试。SRCU 可能需要进行一些调整才能处理这种负载。当然,您的结果可能会因 CPU 的速度和内存的大小而异。

SRCU API 包括 srcu_read_lock(), srcu_read_unlock(), srcu_dereference(), srcu_dereference_check(), synchronize_srcu(), synchronize_srcu_expedited(), call_srcu(), srcu_barrier(), 和 srcu_read_lock_held()。它还包括 DEFINE_SRCU()、DEFINE_STATIC_SRCU() 和 init_srcu_struct() API,用于定义和初始化 srcu_struct 结构。

最近,SRCU API 添加了轮询接口

  1. start_poll_synchronize_srcu() 返回一个 cookie,用于标识未来 SRCU 宽限期的完成,并确保将启动此宽限期。

  2. poll_state_synchronize_srcu() 返回 true,当且仅当指定的 cookie 对应于已经完成的 SRCU 宽限期。

  3. get_state_synchronize_srcu() 返回一个 cookie,就像 start_poll_synchronize_srcu() 一样,但不同之处在于它不采取任何措施来确保将启动任何未来的 SRCU 宽限期。

这些函数用于避免在具有多阶段老化机制的某些类型的缓冲区缓存算法中出现不必要的 SRCU 宽限期。想法是,到块从缓存中完全老化时,SRCU 宽限期很可能已经过去。

Tasks RCU

某些形式的跟踪使用 “trampolines” 来处理安装不同类型探针所需的二进制重写。能够释放旧的 trampolines 是件好事,这听起来像是某种形式的 RCU 的工作。但是,由于有必要能够在代码中的任何位置安装跟踪,因此不可能使用读取端标记,例如 rcu_read_lock()rcu_read_unlock()。此外,在 trampoline 本身中使用这些标记也是行不通的,因为在 rcu_read_unlock() 之后需要有指令。synchronize_rcu() 将保证执行到达 rcu_read_unlock(),但它无法保证执行已完全离开 trampoline。更糟糕的是,在某些情况下,trampoline 的保护必须扩展到执行到达 trampoline 之前 的几个指令。例如,这几个指令可能会计算 trampoline 的地址,以便在执行实际到达 trampoline 本身之前很长一段时间预先确定进入 trampoline。

解决方案是以 Tasks RCU 的形式出现,它具有由自愿上下文切换(即,调用 schedule()、cond_resched() 和 synchronize_rcu_tasks())分隔的隐式读取端关键部分。此外,进出用户空间执行的转换也会分隔 tasks-RCU 读取端关键部分。Tasks RCU 会忽略空闲任务,并且可以使用 Tasks Rude RCU 与它们交互。

请注意,非自愿上下文切换 不是 Tasks-RCU 静止状态。毕竟,在可抢占内核中,在 trampoline 中执行代码的任务可能会被抢占。在这种情况下,Tasks-RCU 宽限期显然不能结束,直到该任务恢复并且其执行离开该 trampoline。这意味着,除其他事项外,cond_resched() 不提供 Tasks RCU 静止状态。(相反,从 softirq 使用 rcu_softirq_qs(),否则使用 rcu_tasks_classic_qs()。)

tasks-RCU API 非常简洁,仅包含 call_rcu_tasks()synchronize_rcu_tasks()rcu_barrier_tasks()。在 CONFIG_PREEMPTION=n 内核中,trampoline 不会被抢占,因此这些 API 映射到 call_rcu()synchronize_rcu()rcu_barrier()。在 CONFIG_PREEMPTION=y 内核中,trampoline 可以被抢占,因此这三个 API 由单独的函数实现,这些函数会检查自愿上下文切换。

Tasks Rude RCU

某些形式的跟踪需要等待在任何在线 CPU 上运行的所有禁用抢占的代码区域,包括 RCU 未监视时执行的代码。这意味着 synchronize_rcu() 是不够的,必须使用 Tasks Rude RCU。这种 RCU 通过强制在每个在线 CPU 上调度一个工作队列来完成其工作,因此得名 “Rude”。对于不希望其 nohz_full CPU 接收 IPI 的实时工作负载以及不希望其空闲 CPU 被唤醒的电池供电系统来说,此操作被认为是相当粗鲁的。

一旦内核入口/出口和深度空闲函数被正确标记为 noinstr,Tasks RCU 就可以开始关注空闲任务(除了那些从 RCU 角度来看是空闲的任务),然后可以将 Tasks Rude RCU 从内核中删除。

tasks-rude-RCU API 也是无读者标记的,因此非常简洁,仅包含 synchronize_rcu_tasks_rude()

Tasks Trace RCU

某些形式的跟踪需要在读取器中休眠,但不能容忍 SRCU 的读取端开销,包括 srcu_read_lock()srcu_read_unlock() 中的完整内存屏障。这种需求由 Tasks Trace RCU 处理,它使用调度器锁定和 IPI 来与读取器同步。不能容忍 IPI 的实时系统可以使用 CONFIG_TASKS_TRACE_RCU_READ_MB=y 构建其内核,这避免了 IPI,但代价是在读取端原语中添加了完整的内存屏障。

tasks-trace-RCU API 也相当简洁,包括 rcu_read_lock_trace()rcu_read_unlock_trace()、rcu_read_lock_trace_held()、call_rcu_tasks_trace()synchronize_rcu_tasks_trace()rcu_barrier_tasks_trace()

可能的未来变化

RCU 用于实现更新端可伸缩性的技巧之一是随着 CPU 数量的增加而增加宽限期延迟。如果这成为一个严重的问题,则有必要重新设计宽限期状态机,以避免需要额外的延迟。

RCU 在一些地方禁用了 CPU 热插拔,最值得注意的是在 rcu_barrier() 操作中。 如果有充分的理由在 CPU 热插拔通知程序中使用 rcu_barrier(),则有必要避免禁用 CPU 热插拔。 这会引入一些复杂性,因此最好有一个 *非常* 好的理由。

一方面是宽限期延迟,另一方面是其他 CPU 的中断,这两者之间的权衡可能需要重新审视。 期望当然是零宽限期延迟以及在加速宽限期操作期间进行的零处理器间中断。 虽然这种理想不太可能实现,但很可能可以进行进一步的改进。

RCU 的多处理器实现使用组合树来对 CPU 进行分组,以减少锁争用并提高缓存局部性。 但是,此组合树不会将其内存分散到 NUMA 节点上,也不会使 CPU 组与硬件功能(如套接字或内核)对齐。 目前认为这种分散和对齐是不必要的,因为热路径读取端原语不访问组合树,并且通常情况下 call_rcu() 也不访问。 如果您认为您的架构需要这种分散和对齐,那么您的架构也应该受益于 rcutree.rcu_fanout_leaf 启动参数,该参数可以设置为套接字、NUMA 节点或任何东西中的 CPU 数量。 如果 CPU 数量太大,请使用 CPU 数量的一部分。 如果 CPU 数量是一个大的质数,那么这当然是一个“有趣”的架构选择! 可以考虑更灵活的安排,但前提是 rcutree.rcu_fanout_leaf 已被证明不足,并且只有在通过精心运行和真实的系统级工作负载证明其不足之后。

请注意,需要 RCU 重新映射 CPU 编号的安排将需要极好的需求论证以及对替代方案的全面探索。

RCU 的各种 kthread 是相对较新的补充。 很可能需要进行调整才能更优雅地处理极端负载。 可能还需要能够将 RCU 的 kthread 和软中断处理程序使用的 CPU 利用率与引发此 CPU 利用率的代码相关联。 例如,RCU 回调开销可能会被计入原始 call_rcu() 实例,尽管可能不会在生产内核中这样做。

可能需要做更多的工作,以在繁重负载下为宽限期和回调调用提供合理的向前进展保证。

总结

本文档介绍了二十多年来 RCU 的需求。 鉴于需求不断变化,这不会是关于此主题的最后结论,但至少它可以用来阐明需求的一个重要子集。

致谢

我感谢 Steven Rostedt、Lai Jiangshan、Ingo Molnar、Oleg Nesterov、Borislav Petkov、Peter Zijlstra、Boqun Feng 和 Andy Lutomirski 在使本文易于理解方面的帮助,以及 Michelle Rankin 对此努力的支持。 其他贡献已在 Linux 内核的 git 存档中得到确认。