Linux内核32-读-拷贝-更新（RCU）

每一种技术的出现必然是因为某种需求。正因为人的本性是贪婪的，所以科技的创新才能日新月异。

1 引言

seqlock锁只能允许一个写操作，但是有些时候我们可能需要多个写操作可以并发执行。所以，Linux内核引入了读-拷贝-更新技术（英文是Read-copy update，简称RCU），它是另外一种同步技术，主要用来保护被多个CPU读取的数据结构。RCU允许多个读操作和多个写操作并发执行。更重要的是，RCU是一种免锁算法，也就是说，它没有使用共享的锁或计数器保护数据结构（但是，这儿还是主要指的读操作是无锁算法。而对于多个写操作来说，需要使用lock保护避免多个CPU的并发访问。所以，其使用场合也是比较严格的，多个写操作中的锁开销不能大于读操作采用无锁算法省下的开销）。这相对于读写自旋锁和seqlock来说，具有很大的优势，毕竟锁的申请和释放对Cache行的”窥视”和失效也是一个很大的负担。

1. Cache行的”窥视”，指的是因为每个CPU具有局部Cache，所以硬件snoop单元必须时时刻刻在”窥视”所有的Cache行，并对其不合法的数据进行失效处理，重新从内存获取数据替换到相应的Cache行中。而在这里，如果使用了共享的lock或者计数器，那么每次对其进行写操作，必然导致相应Cache行的失效。然后重新把使用这个lock的CPU的局部Cache进行更新。

2 RCU实现

既然RCU没有使用共享数据结构，那么它是如何神奇地实现同步技术的呢？其核心思想就是限制RCU的使用范围：

1. 只有动态分配的、通过指针进行访问的数据结构。
2. 进入RCU保护的临界代码段的内核控制路径不能休眠。

3 基本操作

• 对于reader，RCU的基本操作为：
  • （1）调用rcu_read_lock()，进入RCU保护的临界代码段。等价于调用preempt_disable()。
  • （2）调用rcu_dereference，获取RCU保护的数据指针。然后通过该指针读取数据。当然了，在此期间读操作不能发生休眠。
  • （3）调用rcu_read_unlock()，离开RCU保护的临界代码段。等价于调用preempt_enable()。
• 对于writer，RCU的基本操作为：
  • （1）拷贝一份旧数据到新数据，修改新数据。
  • （2）调用rcu_assign_pointer()，将RCU保护的指针修改为新数据的指针。 因为指针的修改是一个原子操作，所以不会发生读写不一致的问题。但是，需要插入一个内存屏障保证只有在数据被修改完成后，其它CPU才能看见更新的指针。尤其是当使用了自旋锁保护RCU禁止多个写操作的并发访问的时候。
  • （3）调用synchronize_rcu，等待所有的读操作都离开临界代码段，完成同步。 RCU技术的真正问题是当写操作更新了指针后，旧数据的存储空间不能立马释放。因为，这时候读操作可能还在读取旧数据，所以，必须等到所有的可能的读操作执行rcu_read_unlock()离开临界代码段后，旧数据的存储空间才能被释放。
  • （4）调用call_rcu()，完成旧数据存储空间的回收工作。 该函数的参数是类型为rcu_head的描述符的地址。该描述符嵌入在要回收的数据结构的内部。该函数还有一个参数就是一个回调函数，当所有的CPU处于空闲状态的时候执行这个回调函数。这个函数通常是负责旧数据存储空间的释放工作。 有一个问题需要注意的是，这个回调函数的执行是在另一个内核线程中执行。call_rcu()函数把回调函数的地址和其参数存储在rcu_head描述符中，然后将这个描述符插入到每个CPU的回调函数列表中（这儿又体现了per-CPU变量的重要性）。每个系统时间Tick，内核都会检查局部CPU是否处于空闲状态。当所有的CPU处于空闲状态的时候，一个特殊的tasklet就会执行所有的回调函数，这个tasklet描述符存储在每个CPU的rcu_tasklet变量中。

4 使用场合

RCU是从Linux2.6版本引入的，主要使用在网络层和虚拟文件系统层。