linux内核笔记【译】RCU(二)使用
引言
Read-Copy Update(RCU)是一种同步机制,2002年10月添加到Linux内核中。RCU 最常被描述为读写锁的替代品,但它也被以多种其他方式使用。RCU 的显著特点是 RCU reader 不直接与 RCU updater 同步,这使得 RCU 读路径非常快,并且允许 RCU reader 在与 RCU updater 并发运行时仍能完成有用的工作。
这引出了一个问题:“RCU 究竟是什么?” 本文从使用的角度回答了这个问题。由于 RCU 最常用于替换某些现有机制,我们主要从它与这些机制的关系角度来看待它,具体如下:
- RCU 是读写锁的替代品
- RCU 是一种受限的引用计数机制
- RCU 是一种批量引用计数机制
- RCU 是一种简易的垃圾回收器
- RCU 是一种提供存在性保证的方式
- RCU 是一种等待事物完成的方式
这些部分之后是结论和疑问的答案。
RCU 是读写锁的替代品
在 Linux 内核中,RCU 最常见的用途可能是作为读密集场景下读写锁的替代品。然而,这一用途在我最初接触时并非显而易见,事实上,在1990年代早期实现通用的 RCU 之前,我选择了实现类似 brlock 的机制。我为 proto-brlock 函数设想的所有用途最终都使用了 RCU 实现。事实上,直到三年多后,proto-brlock 函数才首次被使用。哇,我当时觉得自己真是愚蠢!
RCU 与读写锁的关键相似之处在于,两者的读侧临界区都可以并行执行。事实上,在某些情况下,可以机械地将 RCU API 成员替换为相应的读写锁 API 成员。但首先,为什么要这样做?
RCU 的优势包括性能、死锁免疫和实时延迟。当然,RCU 也有其局限性,包括 reader 和 updater 并发运行、低优先级的 RCU reader 可能会阻塞等待宽限期结束的高优先级线程,以及宽限期延迟可能长达数毫秒。这些优势和局限性将在以下章节中讨论。
性能
RCU 相较于读写锁的读侧性能优势在下图中展示,基于一个 16 CPU 的 3GHz Intel x86 系统。
请注意,在单 CPU 上,读写锁比 RCU 慢几个数量级,而在 16 个 CPU 上几乎又慢了两个数量级。相比之下,RCU 的扩展性非常好。在这两种情况下,误差条表示一个标准差的范围。
疑问1:WTF ??? 您如何期望我相信RCU在3GHz的时钟时间超过300 picsecond时具有100飞秒的开销?
在 CONFIG_PREEMPT 内核中可以获得更温和的视角,尽管 RCU 仍然比读写锁快一到三个数量级。请注意,随着 CPU 数量增加,读写锁的性能变异性较高。误差条表示一个标准差的范围。
当然,随着临界区开销的增加,读写锁的低性能影响将变得不那么显著,如下图所示,该图针对一个 16核 CPU 的系统。
疑问2: 为什么随着临界区开销的增加,读写锁的变异性和开销都会降低?
死锁免疫
尽管 RCU 在读多写少的场景下提供了显著的性能优势,但创建 RCU 的主要原因之一实际上是其对读侧死锁的免疫能力。这种免疫源于 RCU 读侧函数不会阻塞、自旋,甚至不会执行向后分支,因此它们的执行时间是确定性的。因此,它们不可能参与死锁循环。
RCU(Read-Copy Update)reader对死锁免疫的一个有趣结果是,可以无条件地将RCU reader 升级为RCU updater。尝试在读写锁下进行这种升级会导致死锁。以下是一个实现RCU读到更新升级的示例代码片段:
1
2
3
4
5
6
7
8
9
10
rcu_read_lock();
list_for_each_entry_rcu(p, head, list_field) {
do_something_with(p);
if (need_update(p)) {
spin_lock(&my_lock);
do_update(p);
spin_unlock(&my_lock);
}
}
rcu_read_unlock();
注意,do_update() 在锁的保护下执行,并且在 RCU 读侧保护下执行。 RCU 的死锁免疫性的另一个有趣后果是它对一大类优先级反转问题的免疫。例如,低优先级 RCU reader 无法阻止高优先级 RCU updater 获取更新侧锁。同样,低优先级 RCU updater 无法阻止高优先级 RCU reader 进入 RCU 读侧临界区。
疑问3: 这种死锁免疫是否有例外?如果有,什么事件顺序可能导致死锁?
实时延迟
由于 RCU 读侧函数既不自旋也不阻塞,因此它们提供了出色的实时延迟。此外,正如前面所述,这意味着它们对涉及 RCU 读侧函数和锁的优先级反转免疫。 然而,RCU 容易受到更微妙的优先级反转场景的影响,例如,在 -rt 内核中,一个高优先级进程被阻塞等待 RCU 宽限期结束时,可能被低优先级 RCU reader 阻塞。这可以通过使用 RCU 优先级提升来解决。
RCU reader 和 updater 并发运行
由于 RCU reader 从不自旋也不阻塞,并且 updater 不受任何回滚或中止语义的影响,因此 RCU reader 和 updater 必须并发运行。这意味着 RCU reader 可能会访问过时数据,甚至看到不一致性,这两者都使从读写锁转换为 RCU 变得复杂。
然而,在许多出人意料的情况下,不一致性和过时数据并不是问题。经典示例是网络路由表。因为路由更新到达给定系统可能需要相当长的时间(几秒钟甚至几分钟),当更新到达时,系统已经长时间发送数据包到错误的方向。通常,继续额外几毫秒发送到错误的方向并不是问题。此外,由于 RCU updater 可以在不等待 RCU reader 完成的情况下进行更改,因此 RCU reader 很可能比批量公平的读写锁读端更快地看到更改,如下面的图所示。
一旦更新被接收,rwlock 写者无法继续进行,直到最后一个读者完成,后续读者也无法继续进行,直到写者完成。然而,这些后续读者被保证看到新值,如绿色背景所示。相比之下,RCU readers 和 updaters 不会相互阻塞,这允许 RCU readers 更快地看到更新的值。当然,由于它们的执行与 RCU updater 重叠,所有 RCU readers 很可能看到更新的值,包括更新开始前启动的三个读者。尽管如此,只有绿色背景的 RCU readers 被保证看到更新的值,再次如绿色背景所示。
读写锁和 RCU 只是提供不同的保证。在读写锁中,任何在写者开始执行后开始的读者被保证看到新值,而那些在写者自旋时尝试开始的读者可能看到或可能看不到新值,这取决于所讨论的 rwlock 实现中的读者/写者偏好。相比之下,在 RCU 中,任何在 updater 完成后开始的 reader 被保证看到新值,而那些在 updater 开始后结束的 reader 可能看到或可能看不到新值,这取决于时序。
这里的要点是,虽然读写锁确实在计算机系统内部保证一致性,但有一些情况,这种一致性是以与外部世界增加不一致为代价的。换句话说,读写锁以相对于外部世界的无声过时数据为代价获得内部一致性。
尽管如此,还是有一些情况,在系统内部无法容忍不一致性和过时数据。幸运的是,有许多方法可以避免不一致性和过时数据,如在关于将 RCU 应用于 System V IPC 的 FREENIX 论文 和我的博士论文 中讨论的。然而,对这些方法的深入讨论超出了本文的范围。
低优先级 RCU Readers 可以阻塞高优先级回收器
在 Realtime RCU、SRCU 或 QRCU 中(这些将在本系列的最后一期中描述),被抢占的 reader 将阻止宽限期完成,即使高优先级任务被阻塞等待该宽限期完成。Realtime RCU 可以通过用 call_rcu() 替换 synchronize_rcu() 或使用 RCU 优先级提升 来避免这个问题,后者截至 2007 年晚期仍处于实验状态。可能需要为 SRCU 和 QRCU 添加 priority boosting,但只有在证明了明确的现实世界需求后才这样做。
RCU 宽限期延长数毫秒
除了 QRCU 外,RCU 宽限期会延长多个毫秒。虽然有许多技术可以使这样的长延迟无害,包括在可用时使用异步接口(call_rcu() 和 call_rcu_bh()),但这种情况是经验法则的主要原因,即 RCU 应用于读多写少的情况。
读写锁和 RCU 代码比较
在最佳情况下,从读写锁转换为 RCU 非常简单,如从 Wikipedia 取来的以下示例所示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
1 struct el { 1 struct el {
2 struct list_head list; 2 struct list_head list;
3 long key; 3 long key;
4 spinlock_t mutex; 4 spinlock_t mutex;
5 int data; 5 int data;
6 /* Other data fields */ 6 /* Other data fields */
7 }; 7 };
8 rwlock_t listmutex; 8 spinlock_t listmutex;
9 struct el head; 9 struct el head;
1 int search(long key, int *result) 1 int search(long key, int *result)
2 { 2 {
3 struct list_head *lp; 3 struct list_head *lp;
4 struct el *p; 4 struct el *p;
5 5
6 read_lock(&listmutex); 6 rcu_read_lock();
7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) {
8 if (p->key == key) { 8 if (p->key == key) {
9 *result = p->data; 9 *result = p->data;
10 read_unlock(&listmutex); 10 rcu_read_unlock();
11 return 1; 11 return 1;
12 } 12 }
13 } 13 }
14 read_unlock(&listmutex); 14 rcu_read_unlock();
15 return 0; 15 return 0;
16 } 16 }
1 int delete(long key) 1 int delete(long key)
2 { 2 {
3 struct el *p; 3 struct el *p;
4 4
5 write_lock(&listmutex); 5 spin_lock(&listmutex);
6 list_for_each_entry(p, head, lp) { 6 list_for_each_entry(p, head, lp) {
7 if (p->key == key) { 7 if (p->key == key) {
8 list_del(&p->list); 8 list_del_rcu(&p->list);
9 write_unlock(&listmutex); 9 spin_unlock(&listmutex);
10 synchronize_rcu();
10 kfree(p); 11 kfree(p);
11 return 1; 12 return 1;
12 } 13 }
13 } 14 }
14 write_unlock(&listmutex); 15 spin_unlock(&listmutex);
15 return 0; 16 return 0;
16 } 17 }
用RCU替换读写锁的更复杂的情况超出了本文的范围
RCU 是一种受限引用计数机制
由于在有 RCU 读侧临界区进行时不允许宽限期完成,因此 RCU 读侧函数可被用作一种受限的引用计数机制。例如,考虑以下代码片段
1
2
3
4
rcu_read_lock(); /* acquire reference. */
p = rcu_dereference(head);
/* do something with p. */
rcu_read_unlock(); /* release reference. */
rcu_read_lock() 函数可以被视为获取对 p 的引用,因为在 rcu_dereference() 赋值给 p 之后开始的宽限期不可能在到达匹配的 rcu_read_unlock() 之前结束。这种引用计数方案是受限的,因为我们不允许在 RCU 读侧临界区中阻塞,也不允许将 RCU 读侧临界区从一个任务移交给另一个任务。
尽管有这些限制,以下代码可以安全地删除 p:
1
2
3
4
5
6
spin_lock(&mylock);
p = head;
head = NULL;
spin_unlock(&mylock);
synchronize_rcu(); /* Wait for all references to be released. */
kfree(p);
对 head 的赋值防止了未来对 p 的任何引用被获取,而 synchronize_rcu() 等待任何先前已获取的引用被释放。
疑问4: 等等!这正是将 RCU 视为读写锁替代品时可能使用的相同代码!这是怎么回事?
当然,RCU 也可以与传统的引用计数结合使用,正如在 LKML 上讨论的,以及在 Linux 内核引用计数概述 中总结的。
但是为什么要费这个劲?答案的一部分是性能,如下面的图所示,该图再次显示了在 16 CPU 3GHz Intel x86 系统上采集的数据。
疑问5: 为什么 6 核 CPU 附近的 refcnt 开销会下降?
而且,正如读写锁一样,RCU 的性能优势在短时临界区中最为明显,如在 16 CPU 系统上的以下图所示。此外,正如读写锁一样,许多系统调用(以及其中包含的任何 RCU 读侧临界区)在几微秒内完成
然而,RCU 伴随的限制可能相当繁重。例如,在许多情况下,在 RCU 读侧临界区中禁止睡眠的规则会破坏整个目的。下一节将探讨解决这个问题的方法,同时在某些情况下减少传统引用计数的复杂性。
RCU 是一种批量引用计数机制
如前一节所述,传统的引用计数器通常与特定数据结构或与特定组的数据结构相关联。然而,为各种数据结构维护单个全局引用计数器通常会导致包含引用计数的缓存行反弹。这种缓存行反弹会严重降低性能。
缓存行反弹:多个 CPU 核同时访问同一缓存行(哪怕访问的是不同变量),导致缓存行在多个核心之间频繁地来回传递,从而造成性能大幅下降。
相比之下,RCU 的轻量级读侧函数允许极频繁的读侧使用,而性能退化微乎其微,这允许 RCU 被用作“批量引用计数”机制,而几乎或没有性能损失。在必须由单个任务跨越一个阻塞代码段持有引用的情况下,可以使用 Sleepable RCU (SRCU) 来适应。这无法覆盖不常见的场景,即引用从一个任务“传递”到另一个任务,例如,当在启动 I/O 时获取引用,并在相应的完成中断处理程序中释放引用时。(原则上,这可以通过 SRCU 实现来处理,但实际上,尚不清楚这是否是一个好的权衡。)
当然,SRCU 带来了自己的限制,即 srcu_read_lock() 的返回值必须传递到相应的 srcu_read_unlock() 中。至于这一限制会带来多大的问题,以及如何最好地处理它,目前还没有定论。
RCU 是穷人的垃圾回收器
初次学习 RCU 的人常会惊呼“RCU 有点像垃圾回收器!”。这个惊呼有很大的真实成分,但也可能具有误导性。
或许最好将 RCU 与自动垃圾回收器 (GC) 的关系视为:RCU 类似于 GC,因为收集的时机是自动确定的,但 RCU 与 GC 的不同在于:(1) 程序员必须手动指示给定数据结构何时有资格被收集,以及 (2) 程序员必须手动标记可能合法持有引用的 RCU 读侧临界区。
尽管有这些差异,这种相似性确实相当深刻,并且至少出现在一项对 RCU 的理论分析中。此外,我所知的第一个类似 RCU 的机制使用了垃圾回收器来处理宽限期。尽管如此,更好的思考 RCU 的方式将在下一节中描述。
RCU 是一种提供存在保证的方式
Gamsa等 讨论了存在保证,并描述了如何使用类似于 RCU 的机制来提供这些存在保证(见第 7 页第 5 节)。效果是,如果在 RCU 读侧临界区中访问任何 RCU 保护的数据元素,则该数据元素被保证在该 RCU 读侧临界区的持续时间内保持存在。
警觉的读者会认识到,这只是对原始“RCU 是一种等待事情完成的方式”主题的轻微变体,该主题将在下一节中讨论。
RCU 是一种等待事情完成的方式
如本系列第一篇文章所述,RCU 的一个重要组成部分是等待 RCU readers 完成的方式。RCU 的一个巨大优势是,它允许您等待数千种不同事物中的每一个完成,而无需显式跟踪它们中的每一个,也无需担心使用显式跟踪方案所固有的性能退化、可扩展性限制、复杂死锁场景以及内存泄漏风险。
在本节中,我们将展示 synchronize_sched()1 的读侧对应项(包括任何禁用抢占的操作,以及禁用 irq 的硬件操作和函数)如何允许您实现与不可屏蔽中断 (NMI) 处理程序的交互,如果使用锁的话,这些交互将相当困难。我在我的博士论文 中将这种方法称为“Pure RCU”,并且它在 Linux 内核的许多地方被使用。
这种“Pure RCU”设计的基本形式如下:
- 进行更改,例如,修改操作系统对 NMI 的反应方式。
- 等待所有预先存在的读侧临界区完全完成(例如,通过使用 synchronize_sched() 函数)。这里的关键观察是,后续的 RCU 读侧临界区被保证看到所做的任何更改。
- 清理,例如,返回指示更改已成功完成的的状态。
本节的其余部分呈现从 Linux 内核改编的示例代码。在这个示例中,timer_stop 函数使用 synchronize_sched() 来确保所有飞行中的 NMI 通知在释放相关资源之前完成。以下是该代码的简化版本:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct profile_buffer {
long size;
atomic_t entry[0];
};
static struct profile_buffer *buf = NULL;
void nmi_profile(unsigned long pcvalue)
{
atomic_t *p = rcu_dereference(buf);
if (p == NULL)
return;
if (pcvalue >= p->size)
return;
atomic_inc(&p->entry[pcvalue]);
}
void nmi_stop(void)
{
atomic_t *p = buf;
if (p == NULL)
return;
rcu_assign_pointer(buf, NULL);
synchronize_sched();
kfree(p);
}
第 1-4 行定义了一个 profile_buffer 结构,其中包含一个大小和一个不定长度的条目数组。第 5 行定义了一个指向 profile buffer 的指针,该指针假设在其他地方初始化为指向动态分配的内存区域。
第 7-16 行定义了 nmi_profile() 函数,该函数从 NMI 处理程序内部调用。因此,它无法被抢占,也无法被普通 irq 处理程序中断,然而,它仍然会受到缓存未命中、ECC 错误以及同一核心内其他硬件线程的周期窃取导致的延迟影响。第 9 行使用 rcu_dereference() 函数获取 profile buffer 的本地指针,以确保在 DEC Alpha 上内存排序,而第 11 和 12 行如果当前没有分配 profile buffer,则从该函数退出,第 13 和 14 行如果 pcvalue 参数超出范围,则从该函数退出。否则,第 15 行递增由 pcvalue 参数索引的 profile-buffer 条目。请注意,将大小与 buffer 一起存储保证了范围检查与 buffer 匹配,即使一个大 buffer 突然被一个小 buffer 替换。
疑问6:假设 nmi_profile() 函数是可抢占的。要使这个示例正确工作,需要改变什么?
第 18-27 行定义了 nmi_stop() 函数,其中调用者负责互斥(例如,持有正确的锁)。第 20 行获取指向 profile buffer 的指针,第 22 和 23 行如果没有 buffer,则退出函数。否则,第 24 行将 profile-buffer 指针置为 NULL(使用 rcu_assign_pointer() 以在弱排序机器上维护内存排序),第 25 行等待 RCU Sched 宽限期结束,特别是等待所有不可抢占的代码区域(包括 NMI 处理程序)完成。一旦执行继续到第 26 行,我们就被保证任何获取旧 buffer 指针的 nmi_profile() 实例都已经返回。因此,可以安全地释放 buffer,在本例中使用 kfree()释放。
简而言之,RCU 使动态切换 profile buffer 变得容易(您试试用原子操作高效地做到这一点,或者用锁来实现!)。然而,RCU 通常在更高的抽象级别上使用,正如前几节所示。
结论
在本质上,RCU 无非是一个提供以下功能的 API:
- 一个用于添加新数据的发布-订阅机制,
- 一种等待预先存在的 RCU readers 完成的方式,以及
- 一种维护多个版本的纪律,以允许在不损害或不适当延迟并发 RCU readers 的情况下进行更改。
话虽如此,可以在 RCU 之上构建更高级的构造,包括前几节中列出的读者-写者锁、引用计数和存在保证构造。此外,我毫不怀疑 Linux 社区将继续为 RCU 以及其他许多同步函数找到有趣的新用途。
疑问的答案
疑问1:WTF ??? 您如何期望我相信RCU在3GHz的时钟时间超过300 picsecond时具有100飞秒的开销?
答案:首先,考虑用于此测量的内循环如下:
1
2
3
4
for (i = 0; i < CSCOUNT_SCALE; i++) {
rcu_read_lock();
rcu_read_unlock();
}
接下来,考虑 rcu_read_lock() 和 rcu_read_unlock() 的有效定义:
1
2
1 #define rcu_read_lock() do { } while (0)
2 #define rcu_read_unlock() do { } while (0)
还要考虑编译器进行简单的优化,允许它将循环替换为:
i = CSCOUNT_SCALE;
因此,100 飞秒的“测量”只是定时测量固定开销除以内循环中调用 rcu_read_lock() 和 rcu_read_unlock() 的次数。因此,这个测量确实有误,事实上,误差可能达到任意数量级。正如上面 rcu_read_lock() 和 rcu_read_unlock() 的定义所示,实际开销精确为零。
当然,不是每天都有 100 飞秒的定时测量结果被证明是高估的!
疑问2:为什么随着临界区开销的增加,读写锁的变异性和开销都会降低?
答案:因为随着临界区开销的增加,底层 rwlock_t 的争用减少。然而,rwlock 开销不会完全降到单 CPU 的水平,因为存在缓存抖动开销。
疑问3: 这种死锁免疫是否有例外?如果有,什么事件顺序可能导致死锁?
答案:导致涉及 RCU 读侧函数的死锁循环的一种方式是通过以下(非法的)语句序列:
1
2
3
idx = srcu_read_lock(&srcucb);
synchronize_srcu(&srcucb);
srcu_read_unlock(&srcucb, idx);
直到所有预先存在的 SRCU 读侧临界区完成之前 synchronize_rcu() 无法返回,但它被包围在一个无法在 synchronize_srcu() 返回之前完成的 SRCU 读侧临界区中。结果是一个经典的自死锁——当尝试在获取一个读写锁的写锁时已经在持有它的读锁。
请注意,这种自死锁场景不适用于 RCU Classic,因为 synchronize_rcu() 执行的上下文切换将作为此 CPU 的静止状态,允许宽限期完成。然而,这如果说有什么的话,甚至更糟,因为 RCU 读侧临界区使用的数据可能会因为宽限期完成而被释放。
简而言之,不要在 RCU 读侧临界区中调用同步 RCU 更新侧原语。
疑问4: 等等!这正是将 RCU 视为读写锁替代品时可能使用的相同代码!这是怎么回事?
答案:这是玩具示例定律的效果:超过某个点,代码片段看起来相同。唯一的区别在于我们如何思考代码。然而,这种区别可能极其重要。例如,如果我们将 RCU 视为受限引用计数方案,我们永远不会被误导以为更新会与 RCU 读侧临界区竞争。
尽管如此,将 RCU 视为读写锁的替代品通常很有用,例如,当您用 RCU 替换读者-写者锁时。
玩具示例(Law of Toy Examples): 为了理解复杂系统或算法的核心机制,应该使用极其简单、高度理想化和最小化的示例或模型,即“玩具示例”(Toy Example)或“玩具模型”(Toy Model)
疑问5:为什么 6 核 CPU 附近的 refcnt 开销会下降?
答案:最可能是 NUMA 效应。然而,refcnt 线测量的值有相当大的方差,正如误差条所示。事实上,在某些情况下,标准差超过测量值的 10%。因此,开销的下降很可能是一个统计异常。
疑问6:假设 nmi_profile() 函数是可抢占的。要使这个示例正确工作,需要改变什么?
答案:一种方法是在 nmi_profile() 中使用 rcu_read_lock() 和 rcu_read_unlock(),并将 synchronize_sched() 替换为 synchronize_rcu(),或许如下所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct profile_buffer {
long size;
atomic_t entry[0];
};
static struct profile_buffer *buf = NULL;
void nmi_profile(unsigned long pcvalue)
{
atomic_t *p;
rcu_read_lock();
p = rcu_dereference(buf);
if (p == NULL) {
rcu_read_unlock();
return;
}
if (pcvalue >= p->size) {
rcu_read_unlock();
return;
}
atomic_inc(&p->entry[pcvalue]);
rcu_read_unlock();
}
void nmi_stop(void)
{
atomic_t *p = buf;
if (p == NULL)
return;
rcu_assign_pointer(buf, NULL);
synchronize_rcu();
kfree(p);
}
译者注
-
在现代内核中,synchronize_rcu() 已统一支持 synchronize_rcu_bh() 和 synchronize_sched() 的功能,无需区分。 ↩︎






