CH09-延后处理
延后工作的策略可能在人类有记录历史出现之前就存在了,它偶尔被嘲笑为拖延甚至纯粹的懒惰。但直到最近几十年,人们才认识到该策略在简化并行化算法的价值。通用的并行编程延后处理方式包括引用计数、顺序锁、RCU。
引用计数
引用计数指的是跟踪一个对象被引用的次数,防止对象被过早释放。虽然这是一种概念上很简单的技术,但是细节中隐藏着很多魔鬼。毕竟,如果对象不会太提前释放,那么就不需要引用计数了。但是如果容易被提前释放,那么如何阻止对象在获取引用计数过程中被提前释放呢?
该问题有以下几种可能的答案:
- 在操作引用计数时必须持有一把处于对象之外的锁。
- 使用不为 0 的引用计数创建对象,只有在当前引用计数不为 0 时才能获取新的引用计数。如果线程没有对某指定对象的引用,则它可以在已经具有引用的另一线程的帮助下获得引用。
- 为对象提供存在担保,这样在任何有实体尝试获取引用的时刻都无法释放对象。存在担保通常是由自动垃圾收集器来提供,并且在后续章节介绍的 RCU 中也会能提供存在担保。
- 为对象提供类型安全的存在担保,当获取到引用时将会执行附加的类型检查。类型安全的存在担保可以由专用内存分配器提供,也可以由 Linux 内核中的 SLAB_DESTORY_BY_RCU 特性提供。
当然,任何提供存在担保的机制,根据其定义也能提供类型安全的保证。所以本节将后两种答案合并成放在 RCU 一类,这样我们就有 3 种保护引用获取的类型,即锁、引用计数和 RCU。
考虑到引用计数问题的关键是对引用获取和释放对象之间的同步,我们共有 9 种可能的机制组合。
获取同步 | 释放同步—锁 | 释放同步—引用计数 | 释放同步—RCU |
---|---|---|---|
锁 | — | CAM | CA |
引用计数 | A | AM | A |
RCU | CA | MCA | CA |
下图将引用计数机制归为以下几个大类:
- (—):简单计数,不适用原子操作、内存屏障、对齐限制。
- (A):不使用内存屏障的原子计数。
- (AM):原子计数,仅在释放时使用内存屏障。
- (CAM):原子计数,在获取时使用原子操作检查,在释放时使用内存屏障。
- (CA):原子计数,在获取时使用原子操作检查。
- (MCA):原子计数,在获取时使用原子操作检查,同时还使用内存屏障。
但是,由于 Linux 内核中所有“返回值的原子”都包含内存屏障,所有释放操作也包含内存屏障。因此类型 CA 和 MCA 与 CAM 相等,这样就剩下四种类型:—、A、AM、CAM。后续章节将会列出支持引用计数的 Linux 原语。稍后的章节也将给出一种优化,可以改进引用获取和释放十分频繁、而很少需要检查引用是否为 0 这一情况下的性能。
各种引用计数的实现
简单计数
简单计数,既不使用原子操作、也不使用内存屏障,可以用于在获取和释放引用计数时都用同一把锁保护的情况。在这种情况下,引用计数可以以非原子操作方式读写,因为锁提供了必要的互斥保护、内存屏障、原子指令和禁用编译器优化。这种方式适用于锁在保护引用计数之外还保护其他操作的情况,这样也使得引用一个对象必须得等到锁(被其他地方)释放后再持有。
原子计数
原子计数适用于这种情况:任何 CPU 必须先持有一个引用才能获取引用。这是用在当单个 CPU 创建一个对象以供自己使用时,同时也允许其他 CPU、任务、定时器处理函数或者 CPU 后来产生的 IO 完成回调处理函数来访问该对象。CPU 在将对象传递给其他实体之前,必须先以该实体的名义获取一个新的引用。在 Linux 内核中,kref 原语就是用于这种引用计数的。
因为锁无法保护所有引用计数操作,所以需要原子计数,这意味着可能会有两个不同的 CPU 并发地操纵引用计数。如果使用普通的增减函数,一对 CPU 可以同时获取引用计数,假设他们都获取到了计数值 3。如果他们各自都增加各自的值,就得到计数值 4,然后将值写回引用计数中。但是引用计数的新值本该是 5,这样就丢失了其中一次增加。因此,计数的增减操作必须使用原子操作。
如果释放引用计数由锁或 RCU 保护,那么就不需要再使用内存屏障了(以及禁用编译器优化),并且锁也可以防止一对释放操作同时执行。如果是 RCU,清理必须延后直到所有当前 RCU 读端的临界区执行完毕,RCU 框架会提供所有需要的内存屏障和进制编译器优化。因此,如果 2 个 CPU 同时释放了最后 2 个引用,实际的清理工作将延后到所有 CPU 退出它们读端的连接区才会开始。
带释放内存屏障的原子计数
Linux 内核的网络层采用了这种风格的引用,在报文路由中用于跟踪目的地缓存。实际的实现要更复杂一点,本节将关注 struct_dst_entry
引用计数是如何满足这种实例的。
如果调用者已经持有一个 dst_entry 的引用,那么可以使用 dist_clone()
原语,该原语会获取另一个引用,然后传递给内核中的其他实体。因为调用者已经持有了一个引用,dis_clone()
不需要再执行任何内存屏障。将 dst_entry 传递给其他实体的行为是否需要内存屏障,要视情况而定,不过如果需要内存屏障,那么内存屏障已经嵌入在传递给 dst_entry 的过程中了。
dist_release()
原语可以在任何情况下调用,调用者可能在调用 dst_release()
的上一条语句获取 dst_entry 结构的元素的引用。因此在第 14 行上,dst_release()
原语包含了一个内存屏障,阻止编译器和 CPU 的乱序执行。
请注意,开发者在调用 dst_clone()
和 dst_release()
时不需要关心内存屏障,只需要了解使用这两个原语的规则就够了。
带检查和释放内存屏障的原子计数
引用计数的获取和释放可以并发执行这一事实增加了引用计数的复杂性。假设某次引用计数的释放操作发现引用计数的新值为 0,这表明他现在可以安全清除被引用的对象。此时我们肯定不希望在清理工作进行时又发生一次引用计数的获取操作,所以获取操作必须包含一个检查当前引用值是否为 0 的检查。该检查必须是原子自增的一部分。
Linux 黑盒的 fget()
和 fput()
原语都属于这种风格的引用计数,下面是简化后的实现:
第 4 行的 fget 取出一个指向当前进程的文件描述符表的指针,该表可能在多个进程间共享。第 6 行调用 rcu_read_lock
,进入 RCU 读端临界区。后续任何 call_rcu
原语调用的回调函数将延后到对应的 rcu_read_unlock
完成后执行。第 7 行根据参数 fd 指定的文件描述符,查找对应的 struct file 结构,文件描述符的内容稍后再讲。如果指定的文件描述符存在一个对应的已打开文件,那么第 9 行尝试原子地获取一个引用计数。如果第 9 行的操作失败,那么第 10、11 行退出 RCU 读写端临界区,返回失败。如果第 9 行的操作成功,那么第 14、15 行退出读写端临界区,返回一个指向 struct file 的指针。
fcheck_files
原语是 fget
的辅助函数。该函数使用 rcu_dereference
原语来安全地获取受 RCU 保护的指针,用于之后的解引用(这会在如 DEC Alpha 之类的 CPU 上产生一个内存屏障,在这种机器上数据依赖并不保证内存顺序执行)。第 22 行使用 rcu_dereference
来获取指向任务当前的文件描述符表的指针,第 25 行获取该 struct file 的指针,然后调用 rcu_dereference
原语。第 26 行返回 struct file 的指针,如果第 24 行检查失败,那么这里返回 NULL。
fput
原语释放一个 struct file 的引用。第 31 行原子地减少引用计数,如果自减后值为 0,那么第 32 行调用 call_rcu
原语来释放 struct file(通过 call_rcu()
的第二个参数指定的 file_free_rcu
函数),不过这只在当前所有执行 RCU 读端临界区的代码执行完毕后才会发生。等待当前所有执行 RCU 读端临界区的时间被称为“宽限期”。请注意,atomic_dec_and_test
原语中包含一个内存屏障。在本例中该屏障并非必要,因为 struct file 只有在所有 RCU 读端临界区完成后才能销毁,但是在 Linux 中,根据定义所有会返回值的原子操作都需要包含内存屏障。
一旦宽限期完毕,第 39 行 file_free_rcu
函数获取 struct file 的指针,第 40 行释放该指针。
本方法也用于 Linux 虚拟内存系统中,请见针对 page 结构的 get_page_unless_zero
和 put_page_test_zero
函数,以及针对内存映射的 try_to_unuse
和 mmput
函数。
危险指针
前面小节讨论的所有引用计数机制都需要一些其他预防机制,以防止在正在获取引用计数的引用时删除数据元素。该机制可以是一个预先存在的对数据元素的引用、锁、RCU 或原子操作,但所有这些操作都会降低性能和扩展性,或者限制应用场景。
有一种避免这些问题的方法是反过来实现引用计数,也就是说,不是增加存储在数据元素内的某个整数,而是在每 CPU(或每线程)链表中存储指向该数据元素的指针。这个链表里的元素被称为危险指针。每个元素都有一个“虚引用计数”,其值可以通过计算有多少个危险指针指向该元素而得到。因此,如果该元素已经被标记为不可访问,并且不再有任何引用它的危险指针,该元素就可以安全地释放。
当然,这意味着危险指针的获取必须要谨慎,以避免并发删除导致的破坏性后果。
因为使用危险指针的算法可能在他们的任何步骤中重新启动对数据结构的遍历,这些算法通常在获得所有危险指针之前,必须注意避免对数据结构进行任何更改。
以这些限制为交换,危险指针可以为读端提供优秀的性能和扩展性。在第十章将会比较危险指针及其他引用计数机制的性能。
支持引用计数的 Linux 原语
atomic_t
,可提供原子操作的 32 位类型定义。void atomic_dec(atomic_t *var)
,不需要内存屏障或阻止编译器优化的原子自减引用计数操作。int atomic_dec_and_test(atomic_t *var)
,原子减少引用计数,如果结果为 0 则返回 true。需要内存屏障并且阻止编译器优化,否则可能让引用计数在原语外改变。void atomic_inc(atomic_t *var)
,原子增加引用计数,不需要内存屏障或禁用编译器优化。int atomic_inc_not_zero(atomic_t *var)
,原子增加引用计数,如果结果不为 0,那么在增加后返回 true。会产生内存屏障并禁止编译器优化,否则引用会在原语外改变。int atomic_read(atomic_t *var)
,返回引用计数的整数值。非原子操作、不需要内存屏障、不需要禁止编译器优化。void atomic_set(atomic_t *var, int val)
,将引用计数的值设置为 val。非原子操作、不需要内存屏障、不需要禁止编译器优化。void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *head))
,在当前所有执行 RCU 读端临界区完成后调用 func,不过call_rcu
原语是立即返回的。请注意,head 通常是受 RCU 保护的数据结构的一个字段,func 通常是释放该数据结构的函数。从调用call_rcu
到调用 func 之间的时间间隔被称为宽限期。任何包含一个宽限期的时间间隔本身就是一个宽限期。type *container_of(p, type, f)
,给出指针 p,指向类型为 type 的数据结构中的字段 f,返回指向数据结构的指针。void rcu_read_lock(void)
,标记一个 RCU 读端临界区的开始。void rcu_read_unlock(void)
,标记一个 RCU 读端临界区的结束。RCU 读临界区可以嵌套。void smp_mb__before_atomic_dec(vod)
,只有在该平台的atomic_dec
原语没有产生内存屏障,禁止编译器的乱序优化时才有用,执行上面的操作。struct rcu_head
用于 RCU 基础框架的数据结构,用来跟踪等待宽限期的对象。通常作为受 RCU 保护的数据结构中的一个字段。
计数优化
在经常更改计数但很少检查计数是否为 0 的场合里,像第 5 章讨论的那样,维护一个每 CPU 或者每任务计数很有用。关于此计数在 RCU 上的实例,参见关于可睡眠 RCU 的论文。该方法可避免在增减计数函数中使用原子操作或内存屏障,但还是要禁用编译器的乱序优化。另外,像 synchronize_srcu
这样的原语,检查总的引用计数是否为 0 的速度十分缓慢。这使得该方法不适合用于频繁获取和释放引用计数的场合,不过对于极少检查引用计数是否为 0 的场合还是合适的。
顺序锁
Linux 内核中使用的顺序锁主要用于保护以读取为主的数据,多个读者观察到的状态必须一致。不像读写锁,顺序锁的读者不能阻塞写者。它反而更像是危险指针,如果检测到有并发的写者,顺序锁会强迫读者重试。在代码中使用顺序锁的时候,设计很重要,尽量不要让读者有重试的机会。
顺序锁的关键组成部分是序列号,没有写着的情况下其序列号为偶数值,如果有一个更新正在进行中,其序列号为奇数值。读者在每次访问之前和之后可以对值进行快照。如果快照是奇数值,又或者如果两个快照的值不同,则存在并发更新,此时读者必须丢弃访问的结果,然后重试。读者使用 read_seqbegin
和 read_seqretry
函数访问由顺序锁保护的数据。写者必须在每次更新前后增加该值,并且在任意时间内只允许一个写者。写者使用 write_seqlock
和 write_sequnlock
函数更新由顺序锁保护的数据。
顺序锁保护的数据可以拥有任意数量的并发读者,但一次只有有一个写者。在 Linux 内核中顺序锁用于保护计时的校准值。它也用在遍历路径名时检测并发的重命名操作。
可以将顺序锁的读端和写端临界区视为事务,因此顺序锁定可以被认为是一种有限形式的事务内存,后续将会讨论。顺序锁的限制是:顺序锁限制更新和;顺序锁不允许遍历指向可能被写者释放的指针。事务内存当然不存在这些限制,但是通过配合使用其他同步原语,顺序锁也可以克服这些限制。
顺序锁允许写者延迟读者,但反之不可。在存在大量写操作的环境中,这可能引起对读者的不公平甚至饥饿。另一方面,在没有写者时,顺序锁的运行相当快且可以线性扩展。人们总是要鱼和熊掌兼得:快速的读者和不需要重试的读者,并且不会发生饥饿。此外,如果能够不受顺序锁对指针的限制就更好了。下面将介绍同时拥有这些特性的同步机制。
读-复制-修改(RCU)
RCU 介绍
假设你正在编写一个需要访问随时变化的数据的并行实时程序,数据可能是随着温度、湿度的变化而逐渐变化的大气压。该程序的实时响应要求是如此严格,不允许存在任何自旋或阻塞,因此锁就被排除了。同样也不允许使用重试循环,这就排除了顺序锁。幸运的是,温度和压力的范围通常是可控的,这样使用默认的编码数据集也可行。
但是,温度、湿度和压力偶尔会偏离默认值太远,在这种情况下,有必要提供替换默认值的数据。因为温度、湿度和压力是逐渐变化的,尽管数值必须在几分钟内更新,但提供更新值并不是非常紧急的事情。该程序使用一个全局指针,即 gptr,通常为 NULL,表示要使用默认值。否则,gptr 指向假设命名为 a/b/c 的变量,它们的值用于实时计算。
我们如何在不妨碍实时性的情况下安全地为读者提供更新后的数据呢?
上图是一种经典的方式。第一排显示默认状态,其中 gptr 等于 NULL。在第二排中,我们已经分配了一个默认的结构,如问号所示。在第三排,我们已经初始化了该结构。接下来,我们让 gptr 来引用这个新元素。在现代计算机系统中,并发的读者要么看到一个 NULL 指针、要么看到指向新结构 p 的指针,不会看到中间结果,从这种意义上说,这种赋值是原子的。因此,每个读者都可以读到默认值 NULL,或者获取新赋值的非默认值。但无论哪种方式,每个读者都会看到一致的结果。更好的是,读者不需要使用任何昂贵的同步原语,因此这种方式非常适合用于实时场景。
但是我们迟早需要从并发的读者手中删除指向指针的数据。让我们转到一个更加复杂的例子,我们正在删除一个来自链表的元素,如下图:
此链表最初包含元素 A/B/C,首先我们需要删除元素 B,我们使用 list_del()
执行删除操作,此时所有新加入的读者都将看到元素 B 已经从链表删除了。然而,可能仍然有老读者在引用这个元素。一旦所有这些旧的读者读取完成,我们可以安全地释放元素 B,如图中最后一部分所示。
但是我们怎么知道读者何时完成读取呢?
引用计数的方案很有诱惑力,但是这也可能导致长延迟,正如锁和顺序锁,我们已经拒绝这种选择。
让我们考虑极端情况下的逻辑,读者完全不将他们的存在告诉任何人。这种方式显然让读者的性能更佳(毕竟免费是一个非常好的价格),但留给写者的问题是如何才能确定所有的老读者都已经完成。如果要给这个问题提供一个合理的答案,我们显然需要一些额外的约束条件。
有一种约束适合某种类型的实时操作系统(以及某些操作系统内核),让线程不会被抢占。在这种不可抢占的环境中,每个线程将一直运行,直到它明确地并自愿地阻塞自己。这意味着一个不能阻塞的无限循环将使该 CPU 在循环开始后无法用于任何其他目的。不可抢占性还要求线程在持有自旋锁时禁止阻塞。如果没有这个禁止,当持有自旋锁的线程被阻塞后,所有 CPU 都可能陷入某个要求获取自旋锁的线程中无法自拔。要求获取自旋锁的线程在获得锁之前不会放弃他们的 CPU,但是持有锁的线程因为拿不到 CPU,又不能释放自旋锁。这是一种经典的死锁。
然后我们对遍历链表的读线程施加相同的约束:这样的线程在完成遍历之前不允许阻塞。返回到上图的第二排,其中写者刚刚执行完 list_del()
,想象 CPU0 这时做了一个上下文切换。因为读者不允许在遍历链表时阻塞,所以我们可以保证所有先前运行在 CPU0 上的读者已经完成。将这个推理扩展到其他 CPU,一旦每个 CPU 被观察到执行了上下文切换,我们就能保证所有之前的读者都已经完成,该 CPU 不会再有任何引用元素 B 的读线程。此时写者可以安全地释放元素 B 了,也就是上图最后一排所示的状态。
这种方法的示意图如下所示,图中的时间从顶部推移到底部:
虽然这种方法在生产环境上的实现可能相当复杂,但是玩具实现却非常简单:
for_each_online_cpu(cpu);
run_on(cpu);
for_each_online_cpu()
原语遍历所有 CUP,run_on()
函数导致当前线程在指定的 CPU 上运行,这会强制目标 CPU 切换上下文。因此,一旦 for_each_online_cpu
完成,每个 CPU 都执行了一次上下文切换,这又保证了所有之前存在的读线程已经完成。
请注意,该方法不能用于生产环境。正确处理各种边界条件和对性能优化的强烈要求意味着用于生产环境的代码实现将十分复杂。此外,可抢占环境的 RCU 实现需要读者实际去做点什么事情。不过,这种简单的不可抢占方法在概念上是完整的,并为下一节理解 RCU 的基本原理形成了良好的初步基础。
RCU 基础
RCU 是一种同步机制,2002 年 10 月引入 Linux 内核。RCU 允许读操作可以与更新操作并发执行,这一点提升了程序的可扩展性。常规的互斥锁让并发线程互斥执行,并不关心该线程是读者还是写者,而读写锁在没有写者时允许并发的读者,相比于这些常规操作,RCU 在维护对象的每个版本时确保读线程保持一致,同时保证只在所有当前读端临界区都执行完毕后才释放对象。RCU 定义并使用了高效且易于扩展的机制,用来发布和读取对象的新版本,还用于延后旧版本对象的垃圾收集工作。这些机制恰当地在读端和更新端分布工作,让读端非常快速。在某些场合下(比如非抢占式内核里),RCU 读端的函数完全是零开销。
看到这里,读者通常会疑惑“究竟 RCU 是什么”,或者“RCU 怎么工作”。本节将致力于从一种基本的视角回答上述问题,稍后的章节将从用户使用和 API 的视角从新看待这些问题。最后一节会给出一个图表。
RCU 由三种基础机制构成,第一个机制用于插入,第二个机制用于删除,第三个用于让读者可以不受并发插入和删除的干扰。
订阅机制
RCU 的一个关键特性是可以安全的扫描数据,即使数据此时正被修改。RCU 通过一种发布——订阅机制达到了并发的数据插入。举个例子,假设初始值为 NULL 的全局指针 gp 现在被赋值指向一个刚分配并初始化的数据结构。如下代码所示:
1 struct foo {
2 int a;
3 int b;
4 int c;
5 };
6 struct foo *gp = NULL;
7
8 /* . . . */
9
10 p = kmalloc(sizeof(*p), GFP_KERNEL);
11 p->a = 1;
12 p->b = 2;
13 p->c = 3;
14 gp = p;
不幸的是,这块代码无法保证编译器和 CPU 会按照顺序执行最后 4 条赋值语句。如果对 gp 的复制发生在初始化 p 的各种字段之前,那么并发的读者会读到未初始化的值。这里需要内存屏障来保证事情按顺序发生,可是内存屏障又向来以难用著称。所以我们这里用一句 rcu_assign_pointer()
原语将内存屏障封装起来,让其拥有发布的语义。最后 4 行代码如下:
1 p->a = 1;
2 p->b = 2;
3 p->c = 3;
4 rcu_assign_pointer(gp, p);
rcu_assign_pointer “发布”一个新结构,强制让编译器和 CPU 在为 p 的个字段复制之后再去为 gp 赋值。
不过,只保证更新者的执行顺序并不够,因为读者也需要保证读取顺序。请看下面的代码:
1 p = gp;
2 if (p != NULL) {
3 do_something_with(p->a, p->b, p->c);
4 }
这块代码看起来好像不会受乱序执行的影响,可惜事与愿违,在 DEC Alpha CPU 机器上,还有启用编译器值推测优化时,会让 p->a, p->b, p->c 的值在 p 赋值之前被读取,此时编译器会先猜测 p->a, p->b, p->c 的值,然后再去读取 p 的实际值来检查编译器的猜测是否正确。这种类型的优化十分激进,甚至有点疯狂,但是这确实发生在档案驱动(profile-driven)优化的上下文中。
显然,我们必须在编译器和 CPU 层面阻止这种危险的优化。rcu_dereferenc
e 原语用了各种内存屏障和编译器指令来达到这一目的。
1 rcu_read_lock();
2 p = rcu_dereference(gp);
3 if (p != NULL) {
4 do_something_with(p->a, p->b, p->c);
5 }
6 rcu_read_unlock();
rcu_dereference()
原语用一种订阅的方式来获取指定指针的值。然后后续的解引用操作可以看见在对应的发布操作(rcu_read_pointer)前进行的初始化。rcu_read_lock
和 rcu_read_unlock
是肯定需要的:这对原语定义了 RCU 读端的临界区。后续将会介绍它们的意图,不过请注意,这对原语既不会自旋或阻塞,也不会组织 list_add_rcu
的并发执行。事实上,在没有配置 CONFIG_PREEMPT 的内核里,这对原语就是空函数。
虽然理论上 rcu_assign_pointer
的 rcu_dereference
可以用于构造任何能想象到的受 RCU 保护的数据结构,但是实践中常常只用于上层的构造。因此这两个原语是嵌入在特殊的 RCU 变体——即 Linux 操纵链表的 API 中。Linux 有两种双链表的变体,循环链表和哈希表 struct hlist_head/struct hlist_node。前一种如第一个图所示,深色代表链表元头,浅色代表链表元素。而第二张图给出了一种简化方法:
第 15 行必须采用某种同步机制(最常见的是各种锁)来保护,放置多核 list_add 实例并发执行。不过,同步并不能阻止 list_add 的实例与 RCU 的读者并发执行。
订阅一个受 RCU 保护的链表则非常直接:
1 struct foo {
2 struct list_head *list;
3 int a;
4 int b;
5 int c;
6 };
7 LIST_HEAD(head);
8
9 /* . . . */
10
11 p = kmalloc(sizeof(*p), GFP_KERNEL);
12 p->a = 1;
13 p->b = 2;
14 p->c = 3;
15 list_add_rcu(&p->list, &head);
list_add_rcu 原语向指定的链表发布了一条项目,保证对应的 list_for_each_entry_rcu 可以订阅到同一条目。
Linux 的其他双链表、哈希链表都是线性链表,这意味着它的头部节点只需要一个指针,而不是向循环链表那样需要两个,如上图所示。因此哈希表的使用可以减少哈希表的 hash bucket 数组一半的内存消耗。和前面一样,这种表示法太麻烦了,哈希表也可以用和链表一样的简化表达方式。
向受 RCU 保护的哈希表发布新元素和向循环链表的操作十分类似,如下面的示例:
1 struct foo {
2 struct hlist_node *list;
3 int a;
4 int b;
5 int c;
6 };
7 HLIST_HEAD(head);
8
9 /* . . . */
10
11 p = kmalloc(sizeof(*p), GFP_KERNEL);
12 p->a = 1;
13 p->b = 2;
14 p->c = 3;
15 hlist_add_head_rcu(&p->list, &head);
和之前一样,第 15 行必须要使用某种同步机制来保护,比如锁。
订阅受 RCU 保护的哈希表和订阅循环链表没什么区别:
1 rcu_read_lock();
2 hlist_for_each_entry_rcu(p, head, list) {
3 do_something_with(p->a, p->b, p->c);
4 }
5 rcu_read_unlock();
下表是 RCU 的订阅和发布原语,及一个取消发布原语:
类别 | 发布 | 取消发布 | 订阅 |
---|---|---|---|
指针 | rcu_asign_pointer | rcu_assign_pointer(…, NULL) | rcu_dereference |
链表 | list_add_rcu list_add_tail_rcu list_replace_rcu | list_del_rcu | list_for_each_entry_rcu |
哈希链表 | hlist_add_after_rcu hlist_add_before_rcu hlist_add_head_rcu hlist_replace_rcu | hlist_del_rcu | hlist_for_each_entry_rcu |
请注意,list_replace_rcu/list_del_rcu/hlist_replace_rcu/hlist_del_rcu 这些 API 引入了一点复杂性。何时才能安全地释放刚被替换或删除的数据元素?我们怎么知道何时所有读者释放了他们对数据元素的引用?
这些问题将在随后的小节中得到回到。
等待已有的 RCU 读者执行完毕
从最基本的角度来说,RCU 就是一种等待事物结束的方式。当然,有很多其他的方式可以用来等待事物结束,比如引用计数、读写锁、事件等等。RCU 最伟大之处在于它可以等待 20000 种不同的事物,而无需显式的跟追他们中的每一个,也无需去单行对性能的影响、对扩展性的限制、复杂的死锁场景、还有内存泄露带来的危害等等那些使用显式跟踪手段会出现的问题。
在 RCU 的例子中,被等待的事物称为 RCU 读端临界区。RCU 读端临界区从 rcu_read_lock 原语开始,到对应的 rcu_read_unlock 原语结束。RCU 读端临界区可以嵌套,也可以包含一大段代码,只要这其中的代码不会阻塞会睡眠。如果遵守这些约定,就可以使用 RCU 去等待任何代码的完成。
RCU 通过间接地确定这些事物合适完成,才实现了这样的壮举。
如上图所示,RCU 是一种等待已有的 RCU 读端临界区执行完毕的方法,这里的执行完毕也包括在临界区内执行的内存操作。不过请注意,某个宽限期开始后才启动的 RCU 读端临界区会扩展到该宽限期的结尾处。
下列伪代码展示了使用 RCU 等待读者的基本算法:
- 做出改变,比如替换链表中的一个元素。
- 等待所有已有的 RCU 读端临界区执行完毕,这里需要注意的是后续的 RCU 读端临界区无法获取刚刚删除元素的引用。
- 清理,比如释放刚才被替换的元素。
如下面的代码片段所示,其中演示了这个过程,其中字段 a 是搜索关键字:
1 struct foo {
2 struct list_head *list;
3 int a;
4 int b;
5 int c;
6 };
7 LIST_HEAD(head);
8
9 /* . . . */
10
11 p = search(head, key);
12 if (p == NULL) {
13 /* Take appropriate action, unlock, & return. */
14 }
15 q = kmalloc(sizeof(*p), GFP_KERNEL);
16 *q = *p;
17 q->b = 2;
18 q->c = 3;
19 list_replace_rcu(&p->list, &q->list);
20 synchronize_rcu();
21 kfree(p);
第 9、20、21 行实现了刚才提到的 3 个步骤。16~19 行正如 RCU 其名(读-复制-更新),在允许并发度的同时,第 16 行复制,17~19 更新。
正如前面讨论的 synchronize_rcu
原语可以相当简单。然而,想要达到生产质量,代码实现必须处理一些困难的边界情况,并且需要大量优化,这两者都将导致显著的复杂性。虽然知道 synchronize_rcu
有一个简单的实现很好,但是其他问题仍然存在。例如,当 RCU 读者遍历正在更新的链表时会看到什么?该问题将在下节讨论。
维护最近被更新对象的多个版本
本节将展示 RCU 如何维护链表的多个版本,供并发的读者访问。本节通过两个例子来说明在读者还处于 RCU 读端临界区时,被读者引用的数据元素如何保持完整性。第一个例子展示了链表元素的删除,第二个例子展示了链表元素的替换。
例子1:在删除过程中维护多个版本
在开始这个例子前,我们先将上面的代码中 11~20 行改为如下形式:
1 p = search(head, key);
2 if (p != NULL) {
3 list_del_rcu(&p->list);
4 synchronize_rcu();
5 kfree(p);
6 }
这段代码用下图展示的方式跟新链表。每个元素中的三个数字分别代表子弹 a/b/c 的值。红色的元素表示 RCU 读者此时正持有该元素的引用。请注意,我们为了让图更清楚,忽略了后向指针和从尾指向头的指针。
等第 3 行的 list_del_rcu 执行完毕后,5、6、7 元素从链表中被删除,如第 2 行代码所示。如果读者不直接与更新者同步,所以读者可能还在并发地扫描链表。这些并发的读者都有可能看见,也有可能看不见刚刚被删除的元素,这取决于扫描的时机。不过,刚好在取出指向被删除元素指针后被延迟的读者(比如由于终端、ECC 内存错误、配置了 CONFIG_PREEMPT_RT 内核中的抢占),有就可能在删除后还看见链表元素的值。因此,我们此时有两个版本的链表,一个拥有元素 5、6、7,而另一个没有。元素 5、6、7 用黄色标注,表名老读者可能还在引用它,但是新读者已经无法得到它的引用。
请注意,读者不允许在退出 RCU 读临界区后还维护元素 5、6、7的引用。因此,一旦第 4 行的 synchronize_rcu 执行完毕,所有已有的读者都要保证执行完成,不能再有读者引用该元素,图图中第三排的绿色部分。这样我们就又回到了唯一版本的链表。
此时,元素 5、6、7 可以被安全释放了。如图中最后一排所示。这样我们就完成了元素的删除。本节后面部分将描述元素的替换。
例子2:在替换过程中维护多个版本
在开始替换之前,我们先看看前面例子中最后几行代码:
1 q = kmalloc(sizeof(*p), GFP_KERNEL);
2 *q = *p;
3 q->b = 2;
4 q->c = 3;
5 list_replace_rcu(&p->list, &q->list);
6 synchronize_rcu();
7 kfree(p);
链表的初始状态包括指针 p 都和删除例子中一样,如下图中的第一排所示:
和前面一样,每个元素的三个数字分别代表字段 a/b/c。红色的元素表示读者可能正在引用,并且因为读者不直接与更新者同步,所以读者有可能与整个替换过程并发执行。请注意我们为了图表的清晰,再一次忽略了后向指针和指向头的指针。
下面描述了元素 2、5、3 如何替换元素 5、6、7 的过程,任何特定的读者都有可能看见这两个值的其中一个。
第 1 行用 kmalloc 分配了要替换的元素,如图第二排所示。此时没有读者持有刚分配的元素的引用(绿色),并且该元素是未初始化的(问号)。
第 2 行将旧元素复制给新元素,如图第三排所示。新元素此时还不能被读者访问,但是已经初始化了。
第 3 行将 q->b 的值更新为 2,这样新元素终于对读者可见了,因此颜色也变成了红色,如图第五排所示。此时,链表就有两个版本了。已经存在的老读者也可能看到元素 5、6、7(黄色),而新读者可能会看到 5、2、3。不过这里可以保证任何读者都能看到一个完好的链表。
随着第 6 行 synchronize_rcu 的返回,宽限期结束,所有在 list_replace_rcu 之前开始的读者都已经完成。特别是任何可能持有元素 5、6、7 引用的读者保证已经退出了它们的 RCU 读端临界区,不能继续持有引用。因此,不再有任何读者持有旧数据的引用,如图第六排绿色部分所示。这样我们又回到了单一版本的链表,只是用新元素替换了旧元素。
等第 7 行的 kfree 完成后,链表就成了图中最后一排的样子。
不过尽管 RCU 是因替换的例子而得名的,但是 RCU 在内核中的用途还是和简单的删除例子一样。
讨论上述这些例子假设整个更新操作都持有一把互斥锁,这意味着任意时刻最多会有两个版本的链表。
这个事件序列显示了 RCU 更新如何使用多个版本,在有读者并发的情况下安全地执行改变。当然,有些算法无法优雅地处理多个版本。有些技术在 RCU 中采用了这些算法,但是超过了本节的范围。
RCU 基础总结
本节描述了 RCU 算法的三个基本组件。
- 添加新数据的发布——订阅机制。
- 等待已有 RCU 读者结束的方法。
- 维护多个版本数据的准则,允许在不影响或延迟其他并发 RCU 读者的前提下改变数据。
这三个 RCU 组件使得数据可以在有并发读者时被改写,通过不同方式的组合,这三种组件可以实现各种基于 RCU 算法的变体,后续将会讨论。
RCU 的用法
本节将从使用 RCU 的视角,以及使用哪种 RCU 的角度来回答“什么是 RCU”。因为 RCU 最常用的目的是替换已有的机制,所以我们首先观察 RCU 与这些机制之间的关系。
RCU 是读写锁的替代者
也许在 Linux 内核中 RCU 最常见的用途就是在读占大多数时间的情况下替换读写锁了。可是在一开始我并没有想到 RCU 的这个用途,事实上在 20 世纪 90 年代初期,我在实现通用 RCU 实现之前选择实现了一种轻量的读写锁。我为这个轻量级读写锁原型想象的每个用途最后都是用 RCU 来实现了。事实上,在请练级读写锁第一次实际使用时 RCU 已经出现了不止三年了。兄弟们,我是不是看起来很傻!
RCU 和读写锁最关键的相似之处在于两者都有可以并行执行的读端临界区。事实上,在某些情况下,完全可以从机制上用对应的读写锁 API 来替换 RCU 的 API。不过,这样做有什么必要呢?
RCU 的有点在于性能、没有死锁,并能提供实时的延迟。当然 RCU 也有一些缺点,比如读者与写者并发执行,比如低优先级 RCU 读者可以阻塞正等待宽限期完毕的高优先级线程,还比如宽限期的延迟可以有好几毫秒。这些优点和缺点在后续会继续介绍。
如下图,“性能 RCU”相较于读写锁在读端的性能优势。
请注意,在单个 CPU 上读写锁比 RCU 慢一个数量级,在 16 个 CPU 要慢两个数量级,RCU 的扩展性要好很多。在上面两个例子中,错误曲线几乎是水平的。
更温和的视角来自 CONFIG_PREEMPT 内核,虽然 RCU 仍然超过了读写锁 1 到 3 个数量级,如下图。请注意,读写锁在 CPU 数目很多时的陡峭曲线。在任一方向上误差都超过了一个标准差。
当然,如下图中所示,由于不现实的零临界区长度,读写锁的低性能被夸大了。随着临界区的增长,RCU 的性能优势也不再显著,在上图的 16 个 CPU 系统中,Y 轴代表读端原语的总开销,X 轴代表临界区长度。
但是考虑到很多系统调用(以及他们所包含的 RCU 读端临界区)都能在几毫秒内完成,所以这个结果对 RCU 是有利的。另外,下面将会讨论,RCU 读端原语基本上是不会死锁的。
免于死锁虽然 RCU 在多数为读的工作符合下提供了显著的性能优势,但是使用 RCU 的主要目标却不是它可以免于死锁的特性。这种免于死锁的能力来源于 RCU 的读端原语不阻塞、不自旋,甚至不会向后跳转,所以 RCU 读端原语的执行实现是确定的。这使得 RCU 读端原语不可能组成死锁循环。
RCU 读端免于死锁的能力带来了一个有趣的结果,RCU 读者可以无条件地升级为 RCU 更新者。在读写锁中尝试这种升级则会造成死锁。进行 RCU 读者到更新者提升的代码如下所示:
1 rcu_read_lock();
2 list_for_each_entry_rcu(p, &head, list_field) {
3 do_something_with(p);
4 if (need_update(p)) {
5 spin_lock(my_lock);
6 do_update(p);
7 spin_unlock(&my_lock);
8 }
9 }
10 rcu_read_unlock();
请注意,do_update 是在所的保护下执行的,也是在 RCU 读端的保护下执行。
RCU 免于死锁的特性带来的另一个有趣后果是 RCU 不会受很多优先级反转问题的影响。比如,低优先级的 RCU 读者无法阻止高优先级的 RCU 更新者获取更新端锁。类似的,低优先级的更新者也无法阻止高优先级的 RCU 读者进入 RCU 读端临界区。
实时延迟因为 RCU 读端原语既不自旋也不阻塞,所以这些原语有着极佳的实时延迟。另外,如之前所说,这也就意味着这些原语不会受与 RCU 读端原语和锁有关的优先级反转影响。
但是,RCU 还是会受到更隐晦的优先级反转问题影响,比如,在等待 RCU 宽限期结束时阻塞的高优先级进程,会被 -rt 内核的低优先级 RCU 读者阻塞。这也可以用 RCU 优先级提升来解决。
RCU 读者与更新着并发执行因为 RCU 读者既不自旋也不阻塞,还因为 RCU 更新者没有任何类似回滚或中止的语义,所以 RCU 读者和更新者必然可以并发执行。这意味着 RCU 读者有可能访问旧数据,还有可能发现数据不一致,无论这两个问题中的哪一个都有可能让读写锁卷土重来。
不过,令人吃惊的是在大量场景中,数据不一致的旧数据都不是问题。网络路由表是一个经典例子。因为路由的更新可能要花相当长的一段时间才能到达指定系统,所以系统可能会在更新到来后的一段时间内仍然将报文发到错误的地址去。通常在几毫秒内将报文发送到错误的地址并不算什么问题。并且,因为 RCU 的更新者可以在无需等待 RCU 读者执行完毕的情况下发生,所以 RCU 读者可能会比读写锁的读者更早看到更新后的路由表。如下图所示:
一旦收到更新,rwlock 的写者在最后一个读者完成之前不能继续执行,后续的读者在写者更新完成之前不能去读。不过,这一点也保证了后续的读者可以看见最新的值,如果图中绿色部分。相反,RCU 读者和更新者互相不会阻塞,这就允许 RCU 读者可以更快看见更新后的值。当然,因为读者和更新者的执行重叠了一部分,所以所有 RCU 读者都“可能”看见更新后的值,包括图中三个在更新者之前就已开始的 RCU 读者。然而,再一次强调,只有绿色的 RCU 读者才能保证看到更新后的值。
简而言之,读写锁和 RCU 提供了不同的保证。在读写锁中,任何在写者开始之后开始的读者都保证能看到新值,而在写者正在自旋时候开始的读者有可能看到新值,也有可能看到旧值,这取决于读写锁实现中的读写这哪一个优先级更高。与之相反,在 RCU 中,在更新者完成后才开始的读者都保证能看见新值,在更新者开始后才完成的读者有可能看见新值或旧值,这取决于具体的时机。
这里面的关键点是,虽然限定在计算机系统这一范围内读写锁保证了一致性,但是这种一致性是以增加外部世界的不一致性作为代价的。换句话说,读写锁以外部世界的旧数据作为代价,获取了内部的一致性。
然而,总有一种场合让系统无法容忍数据不一致和旧数据。幸运的是,有很多种办法可以避免这种问题,有一些办法是基于前面提到的引用计数。
低优先级 RCU 读者可以阻塞高优先级的回收者。在实时 RCU 中,被抢占的读者将阻止正在进行中的宽限期完成,即使高优先级的任务因为等待宽限期完成而阻塞也是如此。实时 RCU 可以通过用 call_rcu 替换 synchronize_rcu 来避免该问题,或者采用 RCU 优先级提升来避免,不过该方法在 2008 年初还处于实验状态。虽然有必要讨论 SRCU 和 QRCU 的优先级提升,但是现在实时领域还没有实际的需求。
延续好几毫秒的 RCU 宽限期。除了 QRCU 和前面提到的几个玩具 RCU 实现,RCU 宽限期会延续好几个毫秒。虽然有些手段可以消除这样长的延迟带来的损害,比如使用在可能时使用异步接口,但是根据拇指定律,这也是 RCU 使用在读数据占多数的场景的主要原因。
读写锁与 RCU 代码对比。在最好的情况下,将读写锁转换成 RCU 非常简单,如下图所示,这些都来自 Wikipedia。
详细阐述如何使用 RCU 替换读写锁已经超出了本书的范围。
RCU 是一种受限的引用计数机制
因为宽限期不能在 RCU 读端临界区进行时完毕,所以 RCU 读端原语可以像受限的引用计数机制一样使用。比如下面的代码片段:
1 rcu_read_lock(); /* acquire reference. */
2 p = rcu_dereference(head);
3 /* do something with p. */
4 rcu_read_unlock(); /* release reference. */
rcu_read_lock 原语可以看做是获取对 p 的引用,因为在 rcu_dereference 为 p 赋值之后才开始宽限期无法在配对的 rcu_read_unlock 之前完成。这种引用计数机制是受限的,因为我们不允许在 RCU 读端临界区中阻塞,也不允许将一个任务的 RCU 读端临界区传递给另一个任务。
不管上述的限制,下列代码可以安全的删除 p:
1 spin_lock(&mylock);
2 p = head;
3 rcu_assign_pointer(head, NULL);
4 spin_unlock(&mylock);
5 /* Wait for all references to be released. */
6 synchronize_rcu();
7 kfree(p);
将 p 赋值给 head 阻止了任何获取将来对 p 的引用的操作,synchronize_rcu 等待所有值钱获取的引用释放。
当然,RCU 也可以与传统的引用计数结合,LKML 中对此有过讨论,前面也做过了总结。
但是何必这么麻烦呢?我再回到一次,部分原因是性能,如果下图所示,图中再次显示了在 16 个 3GHZ CPU 的 Intel x86 系统中采集的数据。
并且,和读写锁一样,RCU 的性能优势主要来源于较短的临界区,如下图中所示。另外,和读写锁一样,许多系统调用(以及他们包含的任何 RCU 读端临界区)都在几毫秒内完成。
但是,伴随着 RCU 的限制有可能相当麻烦,比如,在许多情况下,在 RCU 读端临界区中禁止睡眠可能与我们的整个目标不符。下节将从解决该问题的方式触发,同时涉及在某些情况下如何降低传统引用计数的复杂性。
RCU 是一种可大规模使用的引用计数机制
前面曾经说过,传统的引用计数通常与某种或者一组数据结构有联系。然而,维护大量不同种类的数据结构的单一全局引用计数,通常会导致包含引用计数的缓存来回“乒乓”。这种缓存行“乒乓”会严重影响系统性能。
相反,RCU 的较轻量级读端原语允许读端极其频繁的调用,却只带来微不足道的性能影响,这使得 RCU 可以作为一种几乎没有任何惩罚的“批量引用计数机制”。当某个任务需要在一系列代码中持有引用时,可以送可休眠 RCU(SRCU)。但是这里没有包含特殊情景,一个任务将引用传递给另一个引用,在开始一次 IO 时获取引用,然后当对应的 IO 完成时在中断处理函数里释放该引用。(原则上 SRCU 的实现可以处理这一点,但是在实践中还不清楚这是否是一个好的权衡)
当然,SRCU 带来了它自己的限制条件,即要传递给对应 srcu_read_lock 和 srcu_read_unlock 返回值,以及硬件终端处理函数或者 NMI/SMI 处理函数不能调用 SRCU 原语。SRCU 的限制会带来多少问题,如何更好的处理这些问题,这一切还尚未有定论。
RCU 是穷人版的垃圾回收器
当人们开始学习 RCU 时,有种比较少见的感叹是“RCU 有点像垃圾回收器”。这种感叹有一部分是对的,不过还是会给学习造成误导。
也许思考 RCU 与垃圾回收器(GC)之间关系的最好办法是,RCU 类似自动的决定垃圾回收的时机。但是 RCU 与 GC 有两个不同点:
- 程序员必须手动指示何时可以回收数据结构。
- 程序员必须手动标出可以合法持有引用的 RCU 读端临界区。
尽管存在这些差异,两者的相似度仍然很高,就我所知至少有一篇理论分析 RCU 的文献曾经分析过两者的相似度。不仅如此,我所知道的第一种类 RCU 的机制就是运用垃圾回收器来处理宽限期。下节提供了一种更好思考 RCU 的方法。
RCU 是一种提供存在担保的方法
Gamsa 等人讨论了存在担保,并且描述了如何用一种类似 RCU 的机制提供这种担保。前面讨论过如何通过锁来提供存在担保及其弊端。如果任何受 RCU 保护的数据元素在 RCU 读端临界区中被访问,那么数据元素在 RCU 读端临界区持续期间保证存在。
1 int delete(int key)
2 {
3 struct element *p;
4 int b;
5
6 b = hashfunction(key);
7 rcu_read_lock();
8 p = rcu_dereference(hashtable[b]);
9 if (p == NULL || p->key != key) {
10 rcu_read_unlock();
11 return 0;
12 }
13 spin_lock(&p->lock);
14 if (hashtable[b] == p && p->key == key) {
15 rcu_read_unlock();
16 rcu_assign_pointer(hashtable[b], NULL);
17 spin_unlock(&p->lock);
18 synchronize_rcu();
19 kfree(p);
20 return 1;
21 }
22 spin_unlock(&p->lock);
23 rcu_read_unlock();
24 return 0;
25 }
上面的代码展示了基于 RCU 的存在担保如何通过从哈希表删除元素的函数来实现每数据元素锁。第 6 行计算哈希函数,第 7 行进入 RCU 读端临界区。如果第 9 行发现哈希表对应的哈希项(bucket)为空,或者数据元素不是我们想要删除的那个,那么第 10 行退出 RCU 读端临界区,第 11 行返回错误。
如果第 9 行判断为 false,第 13 行获取更新端的自旋锁,然后第 14 行检查元素是否还是我们想要的。如果是,第 15 行退出 RCU 读端临界区,第 16 行从哈希表中删除找到的元素,第 17 行释放锁,第 18 行等待所有值钱已经存在的 RCU 读端临界区退出,第 19 行释放刚被删除的元素,最后 20 行返回成功。如果 14 行的判断发现元素不再是我们想要的,那么 22 行释放锁,第 23 行退出 RCU 读端临界区,第 24 行返回错误以删除该关键字。
细心的读者可能会发现,该例子中只不过是前面“RCU 是一种等待事物结束的方式”中那个例子的变体。细心的读者还会发现免于死锁要比 前面讨论的基于锁的存在担保更好。
RCU 是一种提供类型安全内存的方法
很多无锁算法并不需要数据元素在被 RCU 读端临界区引用时保持完全一致,只要数据元素的类型不变就可以了。换句话说,只要结构类型不变,无锁算法可以允许某个数据元素在被其他对象引用时可以释放并重新分配,但是决不允许类型上的改变。这种“保证”,在学术文献中被称为“类型安全的内存”,比前一节提到的存在担保要弱一些,因此处理起来也要困难一些。类型安全的内存算法在 Linux 内核中的应用是 slab 缓存,被 SLAB_DESTROY_BY_RCU 专门标记出来的缓存通过 RCU 将释放的 slab 返回给系统内存。在任何已有的 RCU 读端临界区持续读期间,使用 RCU 可以保证所有带有 SLAB_DESTROY_BY_RCU 标记且正在使用的 slab 元素仍然在 slab 中,且类型保持一致。
这些算法一般使用了一个验证步骤,用于确定刚刚被引用的数据结构确实是被请求的数据。这种验证要求数据结构的一部分不能被释放——重新分配过程触碰。通常这种有效性检查很难保证不存在隐晦且难以解决的故障。
因此,虽然基于类型安全的无锁算法在一种很难达到的情景下非常有效,但是你最好还是尽量使用存在担保。毕竟简单总是好的。
RCU 是一种等待事物结束的方式
在前面我们提到 RCU 的一个重要组件是等待 RCU 读者结束的方法。RCU 的强大之处,其中之一就是允许你在等待上千个不同事物结束的同时,又不用显式去跟踪其中每一个,因此也就无需担心性能下降、扩展限制、复杂的死锁场景、内存泄露等显式跟踪机制自身的问题。
在本节中,我们将展示 synchronize_sched 的读端版本(包括禁止抢占、禁止中断原语)如何让你实现与不可屏蔽中断(NMI)处理函数的交互,如果用锁来实现,这将极其困难。这种方法被称为“纯 RCU”,Linux 的多处使用了该方法。
“纯 RCU” 设计的基本形式如下:
- 做出改变,比如,OS 对一个 NMI 做出反应。
- 等待所有已有读端临界区完全退出(比如使用 synchronize_sched 原语)。这里的关键是后续的 RCU 读端临界区保证可以看见变化发生后的样子。
- 扫尾工作,比如,返回表明改变成功完成的状态。
本节剩下的部分将使用 Linux 内核中的例子做展示。在下面的例子中 timer_stop 函数使用 synchronize_sched 确保在释放相关资源之前,所有正在处理的 NMI 处理函数都已完成。下面是对该例简化后的代码实现:
1 struct profile_buffer {
2 long size;
3 atomic_t entry[0];
4 };
5 static struct profile_buffer *buf = NULL;
6
7 void nmi_profile(unsigned long pcvalue)
8 {
9 struct profile_buffer *p = rcu_dereference(buf);
10
11 if (p == NULL)
12 return;
13 if (pcvalue >= p->size)
14 return;
15 atomic_inc(&p->entry[pcvalue]);
16 }
17
18 void nmi_stop(void)
19 {
20 struct profile_buffer *p = buf;
21
22 if (p == NULL)
23 return;
24 rcu_assign_pointer(buf, NULL);
25 synchronize_sched();
26 kfree(p);
27 }
第 1~4 行定义了 profile_buffer 结构,包含一个大小和一个变长数据的入口。第 5 行定义了指向 profile_buffer 的指针,这里假设别处对该指针进行了初始化,指向内存的动态分配区。
第 7~16 行定义了 nmi_profile 函数,供 NMI 中断处理函数使用。该函数不会被抢占,也不会被普通的中断处理函数中断,但是,该函数还是会受高速缓存未命中、ECC 错误以及被一个核的其他硬件线程抢占时钟周期等因素影响。第 9 行使用 rcu_dereference 原语来获取指向 profile_buffer 的本地指针,这样做是为了确保在 DEC Alpha 上的内存顺序执行,如果当前没有分配 profile_buffer,第 11 和 12 行退出,如果参数 pcvalue 超出范围,第 13 和 14 行退出。否则,第 15 行增加以参数 pcvalue 为下标的 profile_buffer 项的值。请注意,profile_buffer 结构中的 size 保证了 pcvalue 不会超出缓冲区的范围,即使突然将较大的缓冲区替换成了较小的缓冲区也是如此。
第 18~27 行定义了 nmi_stop 函数,由调用者负责互斥访问(比如持有正确的锁)。第 20 行获取 profile_buffer 的指针,如果缓冲区为空,第 22 和 23 行退出。否则,第 24 行将 profile_buffer 的指针置 NULL(使用 rcu_assign_pointer 原语在弱顺序的机器中保证内存顺序访问)。第 25 行等待 RCU Sched 的宽限期结束,尤其是等待所有不可抢占的代码——包括 NMI 中断处理函数一一结束。一旦执行到第 26 行,我们就可以保证所有获取到指向旧缓冲区指针的 nmi_profile 实例都已经返回了。现在可以安全释放缓冲区,这时使用 kfree 原语。
简而言之,RCU 让 profile_buffer 动态切换变得简单(你可以试试原子操作,或者还可以用锁来折磨下自己)。但是,RCU 通常还是运用在较高层次的抽象上,正如前面几个小节所述。
RCU 用法总结
RCU 的核心只是提供一下功能的 API。
- 用于添加新数据的发布——订阅机制。
- 等待已有 RCU 读者结束的方法。
- 维护多版本的准则,使得在有 RCU 读者并发时不会影响或延迟数据更新。
也就是说,在 RCU 之上建造更高抽象级别的架构是可能的,比如前面几节列出的读写锁、引用计数和存在担保。更进一步,我对 Linux 社区会继续为 RCU 寻找新用法丝毫不感到怀疑,当然其他的同步原语肯定也是这样。
上图展示了 RCU 的适用范围,这是关于 RCU 最有用的经验法则。
如图中顶部的蓝色框所示,如果你的读侧重数据允许获取旧值和不一致的结果,RCU 是最好的(但有关旧值和不一致数据的更多信息见下面的部分)。Linux 内核在这种情况的例子是路由表。因为可能需要很多秒甚至几分钟,才能更新路由表并通过互联网传播出去,这时系统已经以错误的方式发送相当一段时间的数据包了。再以小概率发送几毫秒错误的数据就简直算不上什么事了。
如果你有一个以读为主工作的负载,需要一致的数据,RCU 可以工作的不错,如绿色“读侧重,需要一致数据”框所示。Linux 内核在这种情况下的例子是从系统 V 的用户态信号 ID 映射到相应的内核数据结构。读信号量往往大大超过它们被创建和销毁的速度,所以这个映射是读侧重的。然而,在已被删除的信号量上执行信号量操作是错误的。这种对一致性的要求是通过内核信号量数据结构中的锁、以及在删除信号量时设置“已删除”标志达到的。如果用户 ID 映射到了一个具有“已删除”标志的内核数据结构,这个内核数据结构将被忽略,同时用户 ID 被设为无效。
虽然这要求读者获得内核信号量的锁,但这允许内核不用对要映射的数据结构加锁。因此,读者可以无锁地遍历从 ID 映射来的树状数据结构,这反过来大大提升了性能、可扩展性和实时响应性。
如黄色“读写”框所示,当数据需要一致性时,RCU 也可用于读写平衡的工作负载,虽然通常要与其他同步原语结合使用。例如,在最近的 Linux 内核中,目录项缓存使用了 RCU、顺序锁、每 CPU 锁和每数据结构锁,这才用于在常见情况下无锁地遍历路径名。虽然 RCU 在这种读写平衡的情况下可以非常有益,但是这种用法通常要比读侧重情况复杂的多。
最后,如底部的红色框所示,当以更新为主并且需要数据一致性的工作负载时,很少有适用 RCU 的地方,虽然也存在一些例外。此外,如前所述,在 Linux 内核里,SLAB_DESTROY_BY_RCU slab 分配器为 RCU 读者提供类型安全的内存,这可以大大简化非阻塞同步和其他无锁算法的实现。
简而言之,RCU 是一个包括用于添加新数据的发布——订阅机制的 API,等待已存在的 RCU 读者完成的一种方式,以及一门维护多个版本以使更新不会上海或延迟并发的 RCU 读者的学科。这个 RCU API 最适合以读者为主的情况,特别是如果应用程序可以容仍陈旧不一致的数据。
Linux 内核中的 RCU API
等待完成的 API 族
发布-订阅、版本维护 API
这些 API 的用处
RCU 究竟是什么
RCU 的核心不过是一种支持对插入操作的发布和订阅、等待所有 RCU 读者完成、维护多个版本的 API。也就是说,完全可以在 RCU 之上构建抽象级别更高的模型,比如读写锁、引用计数、存在担保等在前面列出的模型。更进一步,我相信 Linux 社区也会继续不断的寻找新的用法,当然其他的同步原语肯定也是一样。
当然,对 RCU 更复杂的看法还包括所有拿这些 API 能做的事情。
但是,对很多人来说,想要完整观察 RCU,就需要一个 RCU 的例子实现。
RCU 的玩具实现
基于锁的 RCU
基于每线程锁的 RCU
基于计数的简单 RCU
避免更新者饥饿的引用计数 RCU
可扩展的基于计数的 RCU
基于自由增长计数的 RCU
基于自由增长计数的可嵌套 RCU
基于静止状态的 RCU
总结
之前的章节列出了各种 RCU 原语的理想特性。这里我们整理一个列表,供有意实现自己的 RCU 的读者作为参考:
- 必须有读者端原语和宽限期原语,如:rcu_read_lock/rcu_read_unlock, synchronize_rcu。任何在宽限期开始前就存在的 RCU 读端临界区必须在宽限期结束前完毕。
- RCU 读端原语应该有最小的开销。特别是应该避免如高速缓存未命中、原子操作、内存平展和分支之类的操作。
- RCU 读端原语应该有 O(1) 的时间复杂度,可以用于实时用途。(这意味着读者可以与更新着并发执行)
- RCU 读端原语应该在所有上下文中都可以使用(在 Linux 内核中,只有空循环时不能使用 RCU 读端原语)。一个重要的特例是 RCU 读端原语必须可以在 RCU 读端临界区中使用,换句话说,必须允许 RCU 读端临界区嵌套。
- RCU 读端临界区不应该有条件判断,不会返回失败。该特性十分重要,因为错误检查会增加复杂度,让测试和验证变得更加复杂。
- 除了静止状态意外的任何操作都能在 RCU 读端原语中执行。比如像 IO 这样不幂等的操作也应用允许。
- 应该允许在 RCU 读端临界区中执行的同时更新一个受 RCU 保护的数据结构。
- RCU 读端和更新端的原语应该在内存分配器的设计和实现上独立,换句话说,同样的 RCU 实现应该能在不管数据原语是分配还是释放的同时,保护数据元素。
- RCU 宽限期不应该被在 RCU 读端临界区之外阻塞的线程而阻塞(但是请注意,大多数基于静止状态的实现破坏了这一愿望)。
RCU 练习
如何选择
下图提供了一些粗略的经验法则,可以帮助你选择延迟处理技术。
存在保证 | 写读者并行 | 读取端开销 | 批量引用 | 低内存占用 | 无条件获取 | 非阻塞更新 | |
---|---|---|---|---|---|---|---|
引用计数 | Y | Y | ++->atomic(*) | Y | ? | ||
危险指针 | Y | Y | MB(**) | Y | Y | ||
顺序锁 | 2MB(***) | N/A | N/A | ||||
RCU | Y | Y | 0->2MB | Y | Y | ? |
*
:在每次重试中遍历的每个元素上产生**
:在每次重试时产生***
:原子操作MB
:内存屏障
如“存在保证”一列中所示,如果你需要链接的数据元素的存在保证,那么必须使用引用计数、危险指针或 RCU。顺序锁不提供存在保证,而是提供更新检测,遭遇更新时重试读取端临界区。
当然,如“写读者并行”一列中所示,更新检测意味着顺序锁定不允许更新者和读者同步进行。毕竟,防止这种同步前进是使用顺序锁的全部意义所在。这时可以让顺序锁与引用计数、危险指针或 RCU 结合,以便同时提供存在保证和更新检测。事实上,Linux 内核就是以结合 RCU 和顺序锁的方式进行路径名查找的。
“读取端开销”一列给出了这些技术在读取端的大致开销。引用技术的开销变化范围很大。在低端,简单的非原子自增就够了,至少在有锁的保护下获取引用时如此。在高端,则需要完全有序的原子操作。引用计数会在遍历每个数据元素时产生此开销。危险指针在遍历每个元素时都产生一个内存屏障的开销,顺序锁在每次尝试执行临界区会产生两个内存屏障的开销。RCU 实现的开销从零到每次执行读取端临界区时的两个内存屏障开销不等,后者为 RCU 带来最佳性能,特别是对于读取端临界区需要遍历很多数据元素时。
“批量引用”一列表示只有 RCU 能够以恒定开销获取多个引用。属性怒锁的条件“N/A”,这是因为顺序锁采用更新检测额不是获取引用。
“低内存占用”一列表示那些技术的内存占用较低。此列和“批量引用”一列互补:因为获取大量元素的引用的能力意味着所有这些数据元素必须持续存在,这反过来意味着交道的内存占用。例如,一个线程可能会删除大量的数据元素,而此时另一个线程则并发执行长时间的 RCU 读端临界区。因为读端临界区可能潜在保留对任何新近删除元素的引用,所以在整个临界区持续时间内都必须保留所有这些元素。相反,引用计数和危险指针保留只有那些实际上并发读者引用的特定数据元素。
然而,这种低内存占用的优势是有代价的,如表中“无条件获取”一列。想要看到这一点,请想象哟一个大型的链式数据结构,引用技术或危险指针的读者(线程 A)持有该结构中某个鼓励数据元素的引用。考虑如下事件顺序:
- 线程 B 删除 A 引用的数据元素。由于这个引用,数据元素还不能被释放。
- B 删除 与 A 引用的所有数据元素相邻的所有数据元素。因为没有指向这些数据元素的引用,所有他们都被立即释放。因为 A 的数据元素已被删除,它指向的外部指针不更新。
- 所有 A 的数据元素的外部指针现在指向的是被释放的地址,因此已经不能安全的遍历。
- 因此,引用计数或危险指针的实现无法让 A 通过任何指向数据元素外部的指针来获取引用。
简而言之。任何提供精确引用追踪的延后处理计数都要做好无法获取引用的准备。因此,RCU 高内存占用的缺点反而意味着易于使用的优势,即 RCU 读者不需要处理获取失败的情况。
Linux 内核有时通过结合使用 RCU 和引用技术,来解决内存占用、精确跟踪和获取失败之间的这种竞争关系。RCU 用于短期引用,这意味着 RCU 读端临界区可以很短。这就意味着响应的 RCU 宽限期也很短,从而限制了内存占用。对于一些需要长期引用的数据元素,可以使用引用计数。这意味着只有少数数据元素需要处理应用获取失败的复杂性,因为 RCU,大部分引用的获取都是无条件的。
最后,“非阻塞更新”一列表示危险指针可以提供这种特性。引用计数则要取决于实现。然而,因为在更新端的锁,顺序锁定不能提供非阻塞更新。RCU 的写者必须等待读者,这也排除了完全非阻塞更新。不过有时唯一的阻塞操作是等待释放内存,这在很多情况下都可视为是非阻塞的。
更新端的问题
对于读侧重的情况,本章中提到的延迟处理技术一般都非常适用,但这提出了一个问题:“更新端怎么办?”。毕竟,增加读者的性能和扩展性是很好的,但是自然而然我们也希望为写者提供出色的性能和扩展性。
对于写者,我们已经看到了一种具有高性能和扩展性的情况,即前面提到的计数算法。这些计数算法通过部分分割数据结构,使得可以在本地进行更新,而较昂贵的读取则必须在整个数据结构上求和。Silas BoydWickhizer 把这种概念推广到 OpLog 上,Linux 内核路径名查找、VM 反向映射和 stat 系统调用都使用了这个工具。
另一种方法,称为 Disruptor,是为处理大量流数据输入的引用程序设计的。该方法是依靠单个生产者和单个消费者的 FIFO 队列,最小化对同步的需要。对于 Java 应用程序,Disruptor 还具有减少对垃圾处理器的使用这个优点。
当然,只要是可行的情况,完全分割或“分片”系统总是能提供优秀的性能和扩展性。
Feedback
Was this page helpful?
Glad to hear it! Please tell us how we can improve.
Sorry to hear that. Please tell us how we can improve.