深入理解RCU实现
深入理解RCU实现
——基于内核2.6.21RCU实现(lvyilong316)
RCU(Read-Copy Update)，顾名思义就是读-拷贝修改，它是基于其原理命名的。对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。那么这个“适当的时机”是怎么确定的呢？这是由内核确定的，也是我们后面讨论的重点。
RCU原理
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之后调用写者注册的回调函数来完成真正的数据修改或数据释放操作的。
要想使用好RCU，就要知道RCU的实现原理。我们拿linux 2.6.21 kernel的实现开始分析，为什么选择这个版本的实现呢？因为这个版本的实现相对较为单纯，也比较简单。当然之后内核做了不少改进，如抢占RCU、可睡眠RCU、分层RCU。但是基本思想都是类似的。所以先从简单入手。
首先，上一节我们提到，写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。而这个“适当的时机”就是所有CPU经历了一次进程切换（也就是一个grace period）。为什么这么设计？因为RCU读者的实现就是关抢占执行读取，读完了当然就可以进程切换了，也就等于是写者可以操作临界区了。那么就自然可以想到，内核会设计两个元素，来分别表示写者被挂起的起始点，以及每cpu变量，来表示该cpu是否经过了一次进程切换(quies state)。就是说，当写者被挂起后，
1）重置每cpu变量，值为0。
2）当某个cpu经历一次进程切换后，就将自己的变量设为1。
3）当所有的cpu变量都为1后，就可以唤醒写者了。
下面我们来分别看linux里是如何完成这三步的。
从一个例子开始
我们从一个例子入手，这个例子来源于linux kernel文档中的whatisRCU.txt。这个例子使用RCU的核心API来保护一个指向动态分配内存的全局指针。
struct foo {
int a;
char b;
long c;
};
DEFINE_SPINLOCK(foo_mutex);
struct foo *gbl_foo;
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = gbl_foo;
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
synchronize_rcu();
kfree(old_fp);
}
int foo_get_a(void)
{
int retval;
rcu_read_lock();
retval = rcu_dereference(gbl_foo)->a;
rcu_read_unlock();
return retval;
}
如上代码所示,RCU被用来保护全局指针struct foo *gbl_foo。foo_get_a()用来从RCU保护的结构中取得gbl_foo的值。而foo_update_a()用来更新被RCU保护的gbl_foo的值（更新其a成员）。
首先,我们思考一下,为什么要在foo_update_a()中使用自旋锁foo_mutex呢?假设中间没有使用自旋锁.那foo_update_a()的代码如下:
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
old_fp = gbl_foo;
1:-------------------------
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
synchronize_rcu();
kfree(old_fp);
}
假设A进程在上图----标识处被B进程抢点.B进程也执行了goo_ipdate_a().等B执行完后，再切换回A进程.此时,A进程所持的old_fd实际上已经被B进程给释放掉了.此后A进程对old_fd的操作都是非法的。所以在此我们得到一个重要结论：RCU允许多个读者同时访问被保护的数据，也允许多个读者在有写者时访问被保护的数据（但是注意：是否可以有多个写者并行访问取决于写者之间使用的同步机制）。
说明：本文中说的进程不是用户态的进程，而是内核的调用路径，也可能是内核线程或软中断等。
RCU的核心API
另外,我们在上面也看到了几个有关RCU的核心API。它们为别是:
rcu_read_lock()
rcu_read_unlock()
synchronize_rcu()
rcu_assign_pointer()