RCU

一、 引言

众所周知，为了保护共享数据,需要一些同步机制,如自旋锁(spinlock)，读写锁(rwlock)，它们使用起来非常简单,而且是一种很有效的同步机制，在UNIX系统和Linux系统中得到了广泛的使用。但是随着计算机硬件的快速发展，获得这种锁的开销相对于CPU的速度在成倍地增加，原因很简单，CPU的速度与访问内存的速度差距越来越大，而这种锁使用了原子操作指令，它需要原子地访问内存，也就说获得锁的开销与访存速度相关，另外在大部分非x86架构上获取锁使用了内存栅(Memory Barrier)，这会导致处理器流水线停滞或刷新，因此它的开销相对于CPU速度而言就越来越大。表1数据证明了这一点。

表1是在700MHz的奔腾III机器上的基本操作的开销，在该机器上一个时钟周期能够执行两条整数指令。在1.8GHz的奔腾4机器上, 原子加1指令的开销要比700MHz的奔腾III机器慢75纳秒(ns)，尽管CPU速度快两倍多。

这种锁机制的另一个问题在于其可扩展性，在多处理器系统上，可扩展性非常重要，否则根本无法发挥其性能。图1表明了Linux上各种锁的扩展性。

图 1 Linux的4种锁机制的扩展性

注：refcnt表示自旋锁与引用记数一起使用。

读写锁rwlock在两个CPU的情况下性能反倒比一个CPU的差，在四个CPU的情况下，refcnt的性能要高于rwlock，refcnt大约是理论性能的45%，而rwlock是理论性能的39%,自旋缩spinlock的性能明显好于refcnt和rwlock，但它也只达到了理性性能的57%，brlock（Big Reader Lock）性能可以线性扩展。Brlock是由Redhat的Ingo Molnar实现的一个高性能的rwlock，它适用于读特多而写特少的情况，读者获得brlock的开销很低，但写者获得锁的开销非常大，而且它只预定义了几个锁，用户无法随便定义并使用这种锁，它也需要为每个CPU定义一个锁状态数组，因此这种锁并没有被作为rwlock的替代方案广泛使用，只是在一些特别的地方使用到。

正是在这种背景下，一个高性能的锁机制RCU呼之欲出，它克服了以上锁的缺点，具有很好的扩展性，但是这种锁机制的使用范围比较窄，它只适用于读多写少的情况，如网络路由表的查询更新、设备状态表的维护、数据结构的延迟释放以及多径I/O设备的维护等。

RCU并不是新的锁机制，它只是对Linux内核而言是新的。早在二十世纪八十年代就有了这种机制，而且在生产系

统中使用了这种机制，但这种早期的实现并不太好，在二十世纪九十年代出现了一个比较高效的实现，而在linux中是在开发内核2.5.43中引入该技术的并正式包含在2.6内核中。

二、RCU的原理

RCU(Read-Copy Update)，顾名思义就是读-拷贝修改，它是基于其原理命名的。对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的操作。

因此RCU实际上是一种改进的rwlock，读者几乎没有什么同步开销，它不需要锁，不使用原子指令，而且在除alpha的所有架构上也不需要内存栅（Memory Barrier），因此不会导致锁竞争，内存延迟以及流水线停滞。不需要锁也使得使用更容易，因为死锁问题就不需要考虑了。写者的同步开销比较大，它需要延迟数据结构的释放，复制被修改的数据结构，它也必须使用某种锁机制同步并行的其它写者的修改操作。读者必须提供一个信号给写者以便写者能够确定数据可以被安全地释放或修改的时机。有一个专门的垃圾收集器来探测读者的信号，一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。 RCU与rwlock的不同之处是：它既允许多个读者同时访问被保护的数据，又允许多个读者和多个写者同时访问被保护的数据（注意：是否可以有多个写者并行访问取决于写者之间使用的同步机制），读者没有任何同步开销，而写者的同步开销则取决于使用的写者间同步机制。但RCU不能替代rwlock，因为如果写比较多时，对读者的性能提高不能弥补写者导致的损失。

读者在访问被RCU保护的共享数据期间不能被阻塞，这是RCU机制得以实现的一个基本前提，也就说当读者在引用被RCU保护的共享数据期间，读者所在的CPU不能发生上下文切换，spinlock和rwlock都需要这样的前提。写者在访问被RCU保护的共享数据时不需要和读者竞争任何锁，只有在有多于一个写者的情况下需要获得某种锁以与其他写者同步。写者修改数据前首先拷贝一个被修改元素的副本，然后在副本上进行修改，修改完毕后它向垃圾回收器注册一个回调函数以便在适当的时机执行真正的修改操作。等待适当时机的这一时期称为grace period，而CPU发生了上下文切换称为经历一个quiescent state，grace period就是所有CPU都经历一次quiescent state所需要的等待的时间。垃圾收集器就是在grace period之后调用写者注册的回调函数来完成真正的数据修改或数据释放操作的。

以下以链表元素删除为例详细说明这一过程。

写者要从链表中删除元素 B，它首先遍历该链表得到指向元素 B 的指针，然后修改元素 B 的前一个元素的 next 指针指向元素 B 的 next 指针指向的元素C，修改元素 B 的 next 指针指向的元素 C 的 prep 指针指向元素 B 的 prep指针指向的元素 A,在这期间可能有读者访问该链表，修改指针指向的操作是原子的，所以不需要同步，而元素 B 的指针并没有去修改，因为读者可能正在使用 B 元素来得到下一个或前一个元素。写者完成这些操作后注册一个回调函数以便在 grace period 之后删除元素 B，然后就认为已经完成删除操作。垃圾收集器在检测到所有的CPU不在引用该链表后，即所有的 CPU 已经经历了 quiescent state,grace period 已经过去后，就调用刚才写者注册的回调函数删除了元素 B。

图 2 使用 RCU 进行链表删除操作

三、RCU 实现机制

按照第二节所讲原理，对于读者，RCU 仅需要抢占失效，因此获得读锁和释放读锁分别定义为：

它们有一个变种：

这个变种只在修改是通过 call_rcu_bh 进行的情况下使用，因为 call_rcu_bh将把 softirq 的执行完毕也认为是一个 quiescent state，因此如果修改是通过 call_rcu_bh 进行的，在进程上下文的读端临界区必须使用这一变种。

每一个 CPU 维护两个数据结构rcu_data,rcu_bh_data，它们用于保存回调函数，函数call_rcu和函数call_rcu_bh用户注册回调函数，前者把回调函数注册到rcu_data，而后者则把回调函数注册到rcu_bh_data，在每一个数据结构上，回调函数被组成一个链表，先注册的排在前头，后注册的排在末尾。

当在CPU上发生进程切换时，函数rcu_qsctr_inc将被调用以标记该CPU已经经历了一个quiescent state。该函数也会被时钟中断触发调用。

时钟中断触发垃圾收集器运行，它会检查：

如果以上四个条件只要有一个满足，它就调用函数rcu_check_callbacks。

函数rcu_check_callbacks首先检查该CPU是否经历了一个quiescent state，如果：

2． 当前进程为idle且当前不处在运行softirq状态，也不处在运行IRQ处理函数的状态；

那么，该CPU已经经历了一个quiescent state，因此通过调用函数rcu_qsctr_inc标记该CPU的数据结构rcu_data和rcu_bh_data的标记字段passed_quiesc，以记录该CPU已经经历一个quiescent state。

否则，如果当前不处在运行softirq状态，那么，只标记该CPU的数据结构rcu_bh_data的标记字段passed_quiesc，以记录该CPU已经经历一个quiescent state。注意，该标记只对rcu_bh_data有效。

然后，函数rcu_check_callbacks将调用tasklet_schedule，它将调度为该CPU设置的tasklet rcu_tasklet，每一个CPU都有一个对应的rcu_tasklet。

在时钟中断返回后，rcu_tasklet将在softirq上下文被运行。

rcu_tasklet将运行函数rcu_process_callbacks，函数rcu_process_callbacks可能做以下事情：

1． 开始一个新的grace period；这通过调用函数rcu_start_batch实现。

2． 运行需要处理的回调函数；这通过调用函数rcu_do_batch实现。

3． 检查该CPU是否经历一个quiescent state；这通过函数rcu_check_quiescent_state实现

如果还没有开始grace period，就调用rcu_start_batch开始新的grace period。调用函数rcu_check_quiescent_state检查该CPU是否经历了一个quiescent state,如果是并且是最后一个经历quiescent state的CPU，那么就结束grace period，并开始新的grace period。如果有完成的grace period，那么就调用rcu_do_batch运行所有需要处理的回调函数。函数rcu_process_callbacks将对该CPU的两个数据结构rcu_data和rcu_bh_data执行上述操作。

四、RCU API

rcu_read_lock()

读者在读取由RCU保护的共享数据时使用该函数标记它进入读端临界区。

rcu_read_unlock()

该函数与rcu_read_lock配对使用，用以标记读者退出读端临界区。夹在这两个函数之间的代码区称为”读端临界区”(read-side critical section)。读端临界区可以嵌套，如图3，临界区2被嵌套在临界区1内。

图 3 嵌套读端临界区示例

synchronize_rcu()

该函数由RCU写端调用，它将阻塞写者，直到经过grace period后，即所有的读者已经完成读端临界区，写者才可以继续下一步操作。如果有多个RCU写端调用该函数，他们将在一个grace period之后全部被唤醒。注意，该函数在2.6.11及以前的2.6内核版本中为synchronize_kernel，只是在2.6.12才更名为synchronize_rcu,但在2.6.12中也提供了synchronize_kernel和一个新的函数synchronize_sched，因为以前有很多内核开发者使用synchronize_kernel用于等待所有CPU都退出不可抢占区，而在RCU设计时该函数只是用于等待所有CPU都退出读端临界区，它可能会随着RCU实现的修改而发生语意变化，因此为了预先防止这种情况发生，在新的修改中增加了专门的用于其它内核用户的synchronize_sched函数和只用于RCU使用的synchronize_rcu，现在建议非RCU内核代码部分不使用synchronize_kernel而使用synchronize_sched，RCU代码部分则使用synchronize_rcu，synchronize_kernel之所以存在是为了保证代码兼容性。

synchronize_kernel()

其他非RCU的内核代码使用该函数来等待所有CPU处在可抢占状态，目前功能等同于synchronize_rcu，但现在已经不建议使用，而使用synchronize_sched。

synchronize_sched()

该函数用于等待所有CPU都处在可抢占状态，它能保证正在运行的中断处理函数处理完毕，但不能保证正在运行的softirq处理完毕。注意，synchronize_rcu只保证所有CPU都处理完正在运行的读端临界区。 注：在2.6.12内核中，synchronize_kernel和synchronize_sched都实际使用synchronize_rcu，因此当前它们的功能实际是完全等同的，但是将来将可能有大的变化，因此务必根据需求选择恰当的函数。

函数 call_rcu 也由 RCU 写端调用，它不会使写者阻塞，因而可以在中断上下文或 softirq 使用，而 synchronize_rcu、synchronize_kernel 和synchronize_shced 只能在进程上下文使用。该函数将把函数 func 挂接到 RCU回调函数链上，然后立即返回。一旦所有的 CPU 都已经完成端临界区操作，该函数将被调用来释放删除的将绝不在被应用的数据。参数 head 用于记录回调函数 func，一般该结构会作为被 RCU 保护的数据结构的一个字段，以便省去单独为该结构分配内存的操作。需要指出的是，函数 synchronize_rcu 的实现实际上使用函数call_rcu。

函数call_ruc_bh功能几乎与call_rcu完全相同，唯一差别就是它把softirq的完成也当作经历一个quiescent state，因此如果写端使用了该函数，在进程上下文的读端必须使用rcu_read_lock_bh。

该宏用于在RCU读端临界区获得一个RCU保护的指针，该指针可以在以后安全地引用，内存栅只在alpha架构上才使用。

除了这些API，RCU还增加了链表操作的RCU版本，因为对于RCU，对共享数据的操作必须保证能够被没有使用同步机制的读者看到，所以内存栅是非常必要的。

static inline void list_add_rcu(struct list_head *new, struct list_head *head) 该函数把链表项new插入到RCU保护的链表head的开头。使用内存栅保证了在引用这个新插入的链表项之前，新链表项的链接指针的修改对所有读者是可见的。

该函数类似于list_add_rcu，它将把新的链表项new添加到被RCU保护的链表的末尾。

该函数从RCU保护的链表中移走指定的链表项entry，并且把entry的prev指针设置为LIST_POISON2，但是并没有把entry的next指针设置为LIST_POISON1，因为该指针可能仍然在被读者用于便利该链表。

该函数是RCU新添加的函数，并不存在非RCU版本。它使用新的链表项new取代旧的链表项old，内存栅保证在引用新的链表项之前，它的链接指针的修正对所有读者可见。

该宏用于遍历由RCU保护的链表head，只要在读端临界区使用该函数，它就可以安全地和其它_rcu链表操作函数（如list_add_rcu）并发运行。

该宏类似于list_for_each_rcu，但不同之处在于它允许安全地删除当前链表项pos。

该宏类似于list_for_each_rcu，不同之处在于它用于遍历指定类型的数据结构链表，当前链表项pos为一包含struct list_head结构的特定的数据结构。

该宏用于在退出点之后继续遍历由RCU保护的链表head。

它从由RCU保护的哈希链表中移走链表项n，并设置n的ppre指针为LIST_POISON2，但并没有设置next为LIST_POISON1,因为该指针可能被读者使用用于遍利链表。

该函数用于把链表项n插入到被RCU保护的哈希链表的开头，但同时允许读者对该哈希链表的遍历。内存栅确保在引用新链表项之前，它的指针修正对所有读者可见。

该宏用于遍历由RCU保护的哈希链表head，只要在读端临界区使用该函数，它就可以安全地和其它_rcu哈希链表操作函数（如hlist_add_rcu）并发运行。

类似于hlist_for_each_rcu，不同之处在于它用于遍历指定类型的数据结构哈希链表，当前链表项pos为一包含struct list_head结构的特定的数据结构。

五、RCU 典型应用

在 linux 2.6 内核中，RCU 被内核使用的越来越广泛。下面是在最新的 2.6.12内核中搜索得到的RCU使用情况统计表。

表 1 rcu_read_lock 的使用情况统计

表 2 rcu_read_unlock 的使用情况统计

表 3 rcu_read_lock_bh 的使用情况统计

表 4 rcu_read_unlock_bh 的使用情况统计

表 5 call_rcu 的使用情况统计

表 6 call_rcu_bh 的使用情况统计

表 7 list API 的使用情况统计

表 8 synchronize_rcu 的使用情况统计

表 9 rcu_dereferance 的使用情况统计

从以上统计结果可以看出，RCU已经在网络驱动层、网络核心层、IPC、dcache、内存设备层、软RAID层、系统调用审计和SELinux中使用。从所有RCU API的使用统计汇总（表 10），不难看出，RCU已经是一个非常重要的内核锁机制。

表 10 所有RCU API使用情况总汇

因此，如何正确使用 RCU 对于内核开发者而言非常重要。

下面部分将就 RCU 的几种典型应用情况详细讲解。

1．只有增加和删除的链表操作

在这种应用情况下，绝大部分是对链表的遍历，即读操作，而很少出现的写操作只有增加或删除链表项，并没有对链表项的修改操作，这种情况使用RCU非常容易，从rwlock转换成RCU非常自然。路由表的维护就是这种情况的典型应用，对路由表的操作，绝大部分是路由表查询，而对路由表的写操作也仅仅是增加或删除，因此使用RCU替换原来的rwlock顺理成章。系统调用审计也是这样的情况。

这是一段使用rwlock的系统调用审计部分的读端代码：

使用RCU后将变成：

这种转换非常直接，使用rcu_read_lock和rcu_read_unlock分别替换read_lock和read_unlock，链表遍历函数使用_rcu版本替换就可以了。

使用rwlock的写端代码：

使用RCU后写端代码变成为：

对于链表删除操作，list_del替换为list_del_rcu和call_rcu，这是因为被删除的链表项可能还在被别的读者引用，所以不能立即删除，必须等到所有读者经历一个quiescent state才可以删除。另外，list_for_each_entry并没有被替换为list_for_each_entry_rcu，这是因为，只有一个写者在做链表删除操作，因此没有必要使用_rcu版本。

通常情况下，write_lock和write_unlock应当分别替换成spin_lock和spin_unlock，但是对于只是对链表进行增加和删除操作而且只有一个写者的写端，在使用了_rcu版本的链表操作API后，rwlock可以完全消除，不需要spinlock来同步读者的访问。对于上面的例子，由于已经有audit_netlink_sem被调用者保持，所以spinlock就没有必要了。

这种情况允许修改结果延后一定时间才可见，而且写者对链表仅仅做增加和删除操作，所以转换成使用RCU非常容易。

2．写端需要对链表条目进行修改操作

如果写者需要对链表条目进行修改，那么就需要首先拷贝要修改的条目，然后修改条目的拷贝，等修改完毕后，再使用条目拷贝取代要修改的条目，要修改条目将被在经历一个grace period后安全删除。

对于系统调用审计代码，并没有这种情况。这里假设有修改的情况，那么使用rwlock的修改代码应当如下：

如果使用RCU，修改代码应当为；

3．修改操作立即可见

前面两种情况，读者能够容忍修改可以在一段时间后看到，也就说读者在修改后某一时间段内，仍然看到的是原来的数据。在很多情况下，读者不能容忍看到旧的数据，这种情况下，需要使用一些新措施，如System V IPC，它在每一个链表条目中增加了一个deleted字段，标记该字段是否删除，如果删除了，就设置为真，否则设置为假，当代码在遍历链表时，核对每一个条目的deleted字段，如果为真，就认为它是不存在的。

还是以系统调用审计代码为例，如果它不能容忍旧数据，那么，读端代码应该修改为：

注意，对于这种情况，每一个链表条目都需要一个spinlock保护，因为删除操作将修改条目的deleted标志。此外，该函数如果搜索到条目，返回时应当保持该条目的锁，因为只有这样，才能看到新的修改的数据，否则，仍然可能看到就的数据。

写端的删除操作将变成：

删除条目时，需要标记该条目为已删除。这样读者就可以通过该标志立即得知条目是否已经删除。

六、小结

RCU是2.6内核引入的新的锁机制，在绝大部分为读而只有极少部分为写的情况下，它是非常高效的，因此在路由表维护、系统调用审计、SELinux的AVC、dcache和IPC等代码部分中，使用它来取代rwlock来获得更高的性能。但是，它也有缺点，延后的删除或释放将占用一些内存，尤其是对嵌入式系统，这可能是非常昂贵的内存开销。此外，写者的开销比较大，尤其是对于那些无法容忍旧数据的情况以及不只一个写者的情况，写者需要spinlock或其他的锁机制来与其他写者同步。

在作者先前的两篇文章”Linux 实时技术与典型实现分析, 第 1 部分: 介绍”和”Linux 实时技术与典型实现分析, 第 2 部分: Ingo Molnar 的实时补丁”中，Ingo Molnar的实时实现要求RCU读端临界区可抢占，而RCU的实现的前提是读端临界区不可抢占，因此如何解决这一矛盾但同时不损害RCU的性能是RCU未来的一大挑战。