Linux中的RCU（读拷贝更新机制）使用方法

本文主要摘抄并翻译自 http://www2./~paulmck/techreports/RCUUsage.2013.02.24a.pdf，同时也加入了译者在内核研发中的一些感悟，写出来以飨读者。

介绍

内核开发者使用了各种不同的同步原语来提升内核的并行性：细粒度锁（fine-grained locks），无锁化数据结构（lock-free data structures），CPU本地数据结构（per-CPU data structures），以及读拷贝更新机制(RCU)。RCU机制在2002年开始在linux kernel中使用，在2013年已经超过6500个API在内核中被使用。RCU的成功得以与在并发读与写情况下的高性能，主要包括两个语义：读者在RCU读关键区间（RCU read-side critical sections）中访问数据结构；写者使用RCU同步语句等待已在读关键区间的读者完成。

---

使用RCU的好处

RCU的存在满足了内核的三点需求：

在有写者的情况下支持并行读

内核中有许多的数据结构被设计来支持大量的读写操作，特别是VFS以及网络子系统。

举个例子，VFS中使用dentry来缓存最近访问的文件元数据，因为应用程序会访问大量的文件，内核需要经常访问或者替换dentry，所以理想情况下线程在读取缓存数据的同时不希望与写冲突。RCU即满足了这种场景的需要。

很低的计算与存储代价

低空间代价是很重要的，因为内核会同时访问成千上万的对象，比如，在一些服务器中缓存了800万个dentry，就算在dentry的结构中加入极少的字节也会带来很大的存储代价。

低计算代价也很重要，因为内核频繁访问的数据结构往往是很短的代码路径，比如SELinux访问数据结构AVC，只有很段的代码路径进行访问，如果通过锁来保护，由于拿锁放锁带来的cache miss可能会有几百个cycle，而这就已经是访问AVC数据结构的一倍时间了，所以低执行代价在一些场景中非常重要。

读操作确定的运行时间

在NMI处理函数中访问共享数据的时候，线程可能在执行关键区域被中断。如果使用spinlock有可能带来死锁。而如果使用无锁化的数据结构，那么在冲突的时候就需要多次尝试直到成功，而这点却使得运行的时间变成非确定性的。

回到相关的一些同步原语设计：读写锁，本地锁，全局锁，事务性内存，都无法满足上诉讨论的特性。就算仅使用一个32位的字段存储锁数据，在很多场景下也是不可接受的。并且这些锁还会带来代价很大的原子操作以及内存屏障。

RCU的设计

RCU原语包含两个方面：RCU临界区以及RCU同步。

线程通过调用rcu_read_lock进入临界区，离开则是使用rcu_read_unlock。当需要进行RCU同步的时候，则使用synchronize_rcu，当这个接口被调用之后，会等待所有的进入临界区的线程都退出了才会返回。synchronize_rcu既不会阻止线程新进入临界区，也不会去等待synchronize_rcu调用之后进入临界区的线程。RCU允许线程去等待已在临界区的读者完成，但是不会提供多个写者之间的同步原语，多个写者还是需要锁机制来保证。

为了满足读写并发、低空间低计算代价、以及读操作确定时间，Linux内核通过调度器上下文切换的契机进行RCU的同步处理。在进入临界区的时候禁止抢占，那么一次的上下文切换就意味着线程已经出了临界区。synchronize_rcu则只需要等待所有的CPU经历一次上下文切换即可。

在实际实现中，synchronize_rcu会等待所有的CPU都经历过一次上下文切换，而不是去在每一个CPU上调度一下线程。

除了使用同步的synchronize_rcu，线程还可以使用异步的原语call_rcu，当所有的CPU都经历了上下文切换，则会通过一个回调函数来完成特定的需求。

由于RCU的读者和写者并行执行，在设计上还有需要考虑乱序问题，例如编译器指令乱序以及访存乱序。如果不能很好的保证顺序，读者有可能访问到一个写者初始化之前的值，造成空指针访问之类的问题。RCU通过接口rcu_dereference和rcu_assign_pointer来保证访存顺序。这两个接口通过体系结构相关的一些内存屏障指令或者编译器指令来强制保证访存顺序。

上述代码展示了Linux中RCU的接口。

使用RCU的几个场景

Wait for completion

Linux内核使用RCU进行NMI处理函数的注销操作。在注销之前，内核必须保证没有CPU当前正在执行NMI处理函数，否则，就有可能出现内核将NMI处理函数的所在的内存释放了，但CPU却尝试访问处理函数。

上面的伪代码展示了NMI系统的工作流程nmi_list保存了NMI的处理函数，并且使用spinlock进行写保护，但支持无锁化的读操作。rcu_list_for_each在遍历每一个元素的时候会调用rcu_dereference，rcu_list_ad和rcu_list_remove则会调用rcu_assign_pointer。在一个RCU临界区内，NMI系统会执行所有的NMI处理函数。注销处理函数的时候，NMI系统会先清空list，然后调用synchronize_rcu保证它返回时所有的处理函数都已经完成了。

在此场景下，如果想使用读写锁，很容易造成死锁，CPU在unregister_nmi_handler中拿锁的情况下，依然会被NMI打断，NMI处理函数中也会尝试拿锁，造成死锁。

引用计数

RCU是一个替代引用计数的很好的办法。不需要显式对特定的数据对象进行引用计数，对象的使用者在读临界区进行操作即可，为了释放一个数据对象，线程可以同调用 call_rcu防止其他线程持有对象的指针。

上面的伪代码展示了RCU在Linux网络栈中取代引用计数的应用。该例子利用RCU对IP options进行引用计数，表示当前内核网络栈正在拷贝IP options到一个packet中。udp_sendmsg调用rcu_read_lock与rcu_read_unlock标记临界区的进入与退出。而应用程序可以通过系统调用sys_setsockop(最终到内核的setsockopt函数)对IP options进行修改。修改的过程是先将新值拷贝，然后调用call_rcu进行旧值的删除。

类型安全内存（Type Safe Memory）

类型安全内存指的是在释放之后保留它的类型，这个对一个线程已经释放某一个对象，而有其他线程仍然持有这个对象的引用很有帮组。一般来说，RCU可以直接使用因为它可以保证在其他线程持有引用的情况下内存对象不会重复利用。然而有些情况下是RCU覆盖不到，比如异步是否对象的调用可能会被阻塞。这样的话使用RCU不能提供存在的保证，而是用来实现类型安全内存。

Linux slab分配器就是使用这个的例子，每一个slab分配器首先利用页分配器，并把他们划分成单一类型的对象进行管理。当一个完整的页中对象都变成free时，slab分配器可以将这个页还给页分配器。如果开发者不希望这个页被重复使用为不同的对象类型，可以设置特殊SLAB_DESTROY_BY_RCU，这样如果这个slab中对象通过RCU临界区访问的话，这个方法可以保证类型安全内存。

订阅发布（Publish-Subscribe）

在订阅-发布使用时，写者会调用rcu_assign_pointer来发布，并发的读者使用rcu_dereference来获取指针。

上面是linux中使用订阅-发布一个例子，内核通过使用rcu_assign_pointer发布指针来追加系统调用表，在索引系统调用表与执行系统调用之前调用rcu_read_lock，并通过调用rcu_deference读取扩展的系统调用表。

替代读写锁（Read-Write Lock Alternative）

Linux中的RCU最常用的是替代读写锁，相对传统的读写锁，RCU除了可以提供高性能以外，还能够防止死锁的发生。Linux使用单一整型变量来实现读写锁，为了保证锁在读写状态，线程必须使用昂贵的原子指令和内存屏障来实现。

使用RCU作为读写锁的一个例子是同步访问PID哈希表：

使用RCU与读写锁一个重要的区别是RCU支持并发读写相同的数据，而读写锁保证他们的互斥。但是RCU并发访问的结果与读写锁不同，比如上面的例子，设想两个现象同时增加A与B到不同哈希桶中，一个并发执行的读进程可能先找到A，但是找不到B。而另外一个读者可能找到B但是没有找到A，这个结果是合理的，但是在使用读写锁时不会发生。