大家好，我是极客范的本期栏目编辑小友，现在为大家讲解linux内核rcu机制详解问题。
RCU(Read-Copy Update)是一种数据同步方式，在当前的Linux内核中扮演着重要的角色。RCU的主要数据对象是链表，目的是提高遍历和读取数据的效率。当使用RCU机制读取数据时，不会对链表执行耗时的锁定操作。这样，多个线程可以同时读取链表，允许一个线程修改链表(修改时需要锁定)。RCU适用于需要频繁读取数据并且没有太多相应数据修改的情况。例如，在文件系统中，经常需要找到位置目录，但对目录的修改相对较少，这是RCU发挥其作用的最佳场景。
在Linux内核源代码中，关于RCU的文档相当完整，您可以在目录/DocumentaTIon/RCU/中找到这些文件。Paul E. McKenney是内核中RCU源代码的主要实现者，他也写过很多关于RCU的文章。今天，我们主要谈谈linux内核rcu的机制。
在RCU实施过程中，我们主要解决了以下问题：
1、在读取过程中，另一个线程删除了一个节点。删除线程可以将此节点从链表中删除，但不能直接销毁此节点，必须等到所有读取线程读取完毕后才能销毁。在RCU，这个过程被称为宽限期。
2.在读取过程中，另一个线程插入一个新节点，读取线程读取这个节点，所以需要保证读取的节点是完整的。这里涉及到发布-订阅机制。
3.保证阅读链表的完整性。或者添加或删除一个节点，以免遍历链表而从中间断开。但是，RCU并不保证它能够读取新添加的节点或不读取要删除的节点。
宽限期
通过例子，方便理解这个内容。下面的例子是根据保罗的文章修改的。
struct foo {
int a；
char b；
长c；
};
DEFINE _ SPINLOCK(foo _ mutex)；
struct foo * gbl _ foo
void foo_read(无效)
{
foo * fp=gbl _ foo
if (fp！=空)
dosomething(FP-》《a，FP-》《b，FP-》《c》)；
}
void foo_update(foo* new_fp)
{
spin _ lock(foo _ mutex)；
foo * old _ fp=gbl _ foo
gbl _ foo=new _ fp
自旋_解锁(foo _ mutex)；
kfee(old _ FP)；
}
上述过程用于全局变量gbl_foo的操作。假设以下场景。当两个线程同时运行foo_ read和foo_update时，线程在foo_ read执行赋值操作后切换。此时，另一个线程开始执行foo_update，执行完成。当运行foo_ read的进程切换回来，dosomething正在运行时，fp已经被删除，这会对系统造成危害。为了防止此类事件，RCU增加了一个新的概念，称为宽限期。如下图所示：
图中每一行代表一个线程，底线是删除线程。当它完成删除操作时，线程进入宽限期。宽限期的含义是，删除操作发生后，它必须等待宽限期开始前已启动的所有读取线程完成，然后才能销毁。原因是这些线程可能已经读取了要删除的元素。图中的宽限期必须等待1和2结束；但是，读取线程5在宽限期开始之前已经结束，因此无需考虑。不需要考虑3、4和6，因为宽限期结束后启动的线程无法读取已删除的元素。为此，RCU机制提供了相应的API来实现这一功能。
void foo_read(无效)
{
rcu _ read _ lock()；
foo * fp=gbl _ foo
if (fp！=空)
dosomething(FP-》《a，FP-》《b，FP-》《c》)；
rcu _ read _ unlock()；
}
void foo_update(foo* new_fp)
{
spin _ lock(foo _ mutex)；
foo * old _ fp=gbl _ foo
gbl _ foo=new _ fp
自旋_解锁(foo _ mutex)；
synchronize_rcu（）;kfee（old_fp）;
}
其中foo_read中增加了rcu_read_lock和rcu_read_unlock，这两个函数用来标记一个RCU读过程的开始和结束。其实作用就是帮助检测宽限期是否结束。
foo_update增加了一个函数synchronize_rcu（），调用该函数意味着一个宽限期的开始，而直到宽限期结束，该函数才会返回。我们再对比着图看一看，线程1和2，在synchronize_rcu之前可能得到了旧的gbl_foo，也就是foo_update中的old_fp，如果不等它们运行结束，就调用kfee（old_fp），极有可能造成系统崩溃。而3，4，6在synchronize_rcu之后运行，此时它们已经不可能得到old_fp，此次的kfee将不对它们产生影响。
宽限期是RCU实现中最复杂的部分，原因是在提高读数据性能的同时，删除数据的性能也不能太差。
订阅——发布机制当前使用的编译器大多会对代码做一定程度的优化，CPU也会对执行指令做一些优化调整，目的是提高代码的执行效率，但这样的优化，有时候会带来不期望的结果。如例：
void foo_update（ foo* new_fp ）
{
spin_lock（&foo_mutex）;
foo *old_fp = gbl_foo;
new_fp-》a = 1;
new_fp-》b = ‘b’;
new_fp-》c = 100;
gbl_foo = new_fp;
spin_unlock（&foo_mutex）;
synchronize_rcu（）;
kfee（old_fp）;
}
这段代码中，我们期望的是6，7，8行的代码在第10行代码之前执行。但优化后的代码并不对执行顺序做出保证。在这种情形下，一个读线程很可能读到 new_fp，但new_fp的成员赋值还没执行完成。当读线程执行dosomething（fp-》a， fp-》b ， fp-》c ） 的 时候，就有不确定的参数传入到dosomething，极有可能造成不期望的结果，甚至程序崩溃。可以通过优化屏障来解决该问题，RCU机制对优化屏障做了包装，提供了专用的API来解决该问题。这时候，第十行不再是直接的指针赋值，而应该改为 ：
rcu_assign_pointer（gbl_foo，new_fp）;
rcu_assign_pointer的实现比较简单，如下：
#define rcu_assign_pointer（p， v） \
__rcu_assign_pointer（（p）， （v）， __rcu）
#define __rcu_assign_pointer（p， v， space） \
do { \
smp_wmb（）; \
（p） = （typeof（*v） __force space *）（v）; \
} while （0）
我们可以看到它的实现只是在赋值之前加了优化屏障 smp_wmb来确保代码的执行顺序。另外就是宏中用到的__rcu，只是作为编译过程的检测条件来使用的。
在DEC Alpha CPU机器上还有一种更强悍的优化，如下所示：
void foo_read（void）
{
rcu_read_lock（）;
foo *fp = gbl_foo;
if （ fp ！= NULL ）
dosomething（fp-》a， fp-》b ，fp-》c）;
rcu_read_unlock（）;
}
第六行的 fp-》a，fp-》b，fp-》c会在第3行还没执行的时候就预先判断运行，当他和foo_update同时运行的时候，可能导致传入dosomething的一部分属于旧的gbl_foo，而另外的属于新的。这样导致运行结果的错误。为了避免该类问题，RCU还是提供了宏来解决该问题：
#define rcu_dereference（p） rcu_dereference_check（p， 0）
#define rcu_dereference_check（p， c） \
__rcu_dereference_check（（p）， rcu_read_lock_held（） || （c）， __rcu）
#define __rcu_dereference_check（p， c， space） \
（{ \
typeof（*p） *_________p1 = （typeof（*p）*__force ）ACCESS_ONCE（p）; \
rcu_lockdep_assert（c， “suspicious rcu_dereference_check（）” \
“ usage”）; \
rcu_dereference_sparse（p， space）; \
smp_read_barrier_depends（）; \
（（typeof（*p） __force __kernel *）（_________p1））; \
}）
staTIc inline int rcu_read_lock_held（void）
{
if （！debug_lockdep_rcu_enabled（））
return 1;
if （rcu_is_cpu_idle（））
return 0;
if （！rcu_lockdep_current_cpu_online（））
return 0;
return lock_is_held（&rcu_lock_map）;
}
这段代码中加入了调试信息，去除调试信息，可以是以下的形式（其实这也是旧版本中的代码）：
#define rcu_dereference（p） （{ \
typeof（p） _________p1 = p; \
smp_read_barrier_depends（）; \
（_________p1）; \
}）
在赋值后加入优化屏障smp_read_barrier_depends（）。
我们之前的第四行代码改为 foo *fp = rcu_dereference（gbl_foo）;，就可以防止上述问题。
数据读取的完整性
还是通过例子来说明这个问题：
如图我们在原list中加入一个节点new到A之前，所要做的第一步是将new的指针指向A节点，第二步才是将Head的指针指向new。这样做的目的是当插入操作完成第一步的时候，对于链表的读取并不产生影响，而执行完第二步的时候，读线程如果读到new节点，也可以继续遍历链表。如果把这个过程反过来，第一步head指向new，而这时一个线程读到new，由于new的指针指向的是Null，这样将导致读线程无法读取到A，B等后续节点。从以上过程中，可以看出RCU并不保证读线程读取到new节点。如果该节点对程序产生影响，那么就需要外部调用做相应的调整。如在文件系统中，通过RCU定位后，如果查找不到相应节点，就会进行其它形式的查找，相关内容等分析到文件系统的时候再进行叙述。
我们再看一下删除一个节点的例子：
如图我们希望删除B，这时候要做的就是将A的指针指向C，保持B的指针，然后删除程序将进入宽限期检测。由于B的内容并没有变更，读到B的线程仍然可以继续读取B的后续节点。B不能立即销毁，它必须等待宽限期结束后，才能进行相应销毁操作。由于A的节点已经指向了C，当宽限期开始之后所有的后续读操作通过A找到的是C，而B已经隐藏了，后续的读线程都不会读到它。这样就确保宽限期过后，删除B并不对系统造成影响。
小结RCU的原理并不复杂，应用也很简单。但代码的实现确并不是那么容易，难点都集中在了宽限期的检测上，后续分析源代码的时候，我们可以看到一些极富技巧的实现方式。