RCU writer

jijo 2008-06-04

展开全文

RCU：linux kernel 2.6中所使用的lock-free synchronization

两个事实：

（1）multiprocessor会越来越重要
（2）spinlock或是lock在multiprocessor上可能会成为bottleneck，在high concurrency的情况下会导致lock contention，从而影响系统的scalability。

为了解决这个问题，linux kernel 2.6在一些“reader远多于writer”的shared data structure上使用了RCU这种lock-free的synchronization。这篇blog主要讲解一下RCU的原理、应用以及它在kernel 2.6 main tree中的实现方法。

RCU的意思是read-copy-update。它的基本思想是将一个write操作分为removal和reclamation两部分。removal所作的事情就是把一个item从某个data structure上删除（或是替换），但是并不释放这个item的memory。由于对一个reference的修改在modern processor上都是一个atomic operation，所以这个operation是可以和其他的reader concurrency执行；由于一个被removal的item的memory没有被释放，所以拥有这个item reference的reader将不受任何影响。只有当所有的reader都不再拥有这个reference的时候，writer才能执行reclamation的操作，来释放item的内存：writer可以阻塞直到这个时刻的到来，也可以指定一个callback function，由kernel在安全的时刻自动调度。
对于使用RCU的data structure来说，所有的reader都不需要任何的synchronization；所有的writer也不需要任何的synchronization，这就是RCU比传统的lock/spinlock高效的原因。但是writer的update需要分成两步进行：

（1）直接修改一些“aligned”machine word，可以delete/replace一个item(修改一个reference)。在这个操作之后的reader将不会再看到被removal的item。
（2）等待，直到所有先于removal操作的reader都退出critical section（因为这些reader可能拥有被remove的item的reference）。那些在removal操作之后的reader由于不会看到被删除的item，所以writer不用等待它们。
（3）此时，可以确认没有任何reader拥有被remove的reference，writer可以安全地释放这个item的memory。当然，writer也可以把cleanup的工作register成一个callback function。

如果用一句话来概括RCU，那就是：推迟writer的cleanup直到所有的reader都退出critical section，从而使所有的reader、writer可以不做任何synchronization而直接进入critical section。
RCU适用于“reader远远多于writer”的shared data structure。一般来说这个比例控制在10％左右，即如果所有的操作中write操作不大于10％，RCU将会有非常好的性能（与传统的lock/spinlock相比）。

这些描述可能过于抽象，我们先来看一个简单的例子：
假设我们有一个shared data structure，它的type是foo，我们会对它有concurrency的read、write访问：

struct foo {
int a,b,c;
};
struct foo* global_foo;

一个reader会执行下面这个函数：

void read() {
rcu_read_lock();
process_foo(rcu_dereference(global_foo));
rcu_read_unlock();
}

这里要说明两点：

（1）rcu_read_lock()、rcu_read_unlock()是用来标记reader的critical section，这些函数不是synchronization。reader在rcu_read_lock()上不会block。所有对shared data structure的read，都必须在critical section之内。
（2）rcu_dereference(global_foo)实际上返回的就是global_foo。“rcu_dereference()”这个函数所作的工作就是加上适当的memory barrier。因为我们使用的lock-free的synchronization，所以必须使用memory barrier来解决memory ordering的问题。

一个writer会执行下面这个函数：

void update(int new_a,int new_b,int new_c) {
struct foo *new_foo,*old_foo;
new_foo = (struct foo*)kmalloc(sizeof(struct foo), GFP_KERNEL);
spin_lock(&foo_mutex);
old_foo = global_foo;
*new_foo = *global_foo;
new_foo->a = new_a;
new_foo->b = new_b;
new_foo->c = new_c;
rcu_assign_pointer(global_foo, new_foo);
spin_unlock(&foo_mutex);
synchronize_rcu();
kfree(old_foo);
}?????

（1）RCU同一时刻只允许一个writer进入critical section，这是RCU的一个严格规定！所以在“update()”中使用了一个spinlock来保证这一点。
（2）这个函数先是复制了一份global_foo，然后修改了相应的field。
（3）“rcu_assign_pointer(global_foo,new_foo)”等同于“global_foo = new_foo”。与“rcu_dereference()”一样，它只是加上了适当的memory barrier。
（4）由于global_foo=new_foo是一个atomic operation，这条语句之前的reader将读到旧的global_foo，在这条语句之后的reader则会读到新的global_foo。
（5）被替换掉的global_foo是不能立刻free的，因为可能有其他的reader持有着它的reference。“synchronize_rcu()”的作用就是block直到所有“这样”的reader都退出critical section（即不再持有被替换掉的global_foo的reference）。如前所述，我们还可以不block writer，而是使用“call_rcu()”register一个callback function，由kernel在安全的时刻调用。

这个例子虽然非常简单，但是很有代表性，而且有许多的实际应用：

（1）在kernel中，interrupt handler是可以在runtime改变的，所以这个data structure会被多个CPU同时读写。于是这个data structure就被RCU用类似的方法保护起来：一个writer可以利用atomic operation完成interrupt handler的安装；当原先的handler被所有的CPU访问完毕，interrupt handler的data structure才会被清理掉。
（2）类似，kernel module也可以使用类似的方法。kernel可以“unload”一个正在被执行的module。
（3）修改shared resizable array也可以使用这种方法，先作一个新array，然后赋值，最后在没有CPU使用的时候free原来array。

下边我们来看看两个复杂一点的例子，也是在kernel中使用RCU最多的地方：lock-free的link list。为了code的简洁，我们假设这个link list有head node，这也是linux kernel中list library的实现方法。
（1）node的删除：

void delete(struct el *p) {
spin_lock(&list_lock);
p->next->prev = p->prev;
p->prev->next = p->next;
spin_unlock(&list_lock);
call_rcu(&p->my_rcu_head, my_free, p);
}

一个writer可以在其他reader遍历list的同时，调用delete()函数；reader、writer都不需要任何的synchronization。一个reader可能会看到这个被删除的node，也可能看不到，但是读到的数据肯定是一致的（感谢modern processor的atomic operation）。由于只是把node p从list上取下来，并没有free memory，那些持有这个reference的reader不会受到任何的影响，它们还可以通过p->next或是p->prev继续遍历这个list。call_rcu() register了一个callback function，当所有的reader都不再持有p的reference的时候，my_free会被执行。在这里，my_free就是kfree的一个简单的wrapper。和上边的例子一样，spin_lock用于保证同一时刻只有一个writer可以访问这个list。
（2）in-place的修改：

void update(struct el *p,int new_a,int new_b) {
struct el *new_node = (struct el*)kmalloc(sizeof(struct el), GFP_KERNEL);
spin_lock(&list_lock);
*new_node=*p;
new_node->a=new_a;
new_node->b=new_b;
p->next->prev=new_node;
p->prev->next=new_node;
spin_unlock(&list_lock);
call_rcu(&p->my_rcu_head,my_free,p);
}

这段code先是copy了一个要修改的node，进行修改，替换掉原来的节点，最后利用callback在安全的时刻free被替换掉的node。

最后，我们简单地看一看RCU是如何在linux kernel 2.6中实现的。
其实RCU实现的核心问题就是：kernel如何判断所有的reader都不再持有被writer remove的object？由于reader所有对shared data structure的access都要发生在critical section之内，即必须用rcu_read_lock()和rcu_read_unlock()包围起来，所以这个问题就变成了：如何判断所有的reader都退出了critical section？
linux kernel使用了一个简单的近似算法：由于所有的reader在critical section里面都不会被preempt CPU，那么如果系统所有的CPU都进行了一次context switch，我们就可以断言所有的reader都出了critical section，它们不会再持有任何可能已经被删除了的object reference。
如果kernel被config成non-preemptive的，那么在kernel mode就不会有context switch发生，很简单地就保证了reader在critical section中不会被preempt。在这种情况下，rcu_read_lock()和rcu_read_unlock()都是no-op。如果kernel被config成preemptive的，那么rcu_read_lock()和rcu_read_unlock()就会分别调用preempt_disable()和preempt_enable()，来保证reader在critical section之内不会被preempt。
如果所有的CPU都进行了至少一次context switch，我们就说系统pass了一个“grace period”。实际上synchronize_rcu()就是阻塞writer直到一个grace period的到来，而call_rcu所register的callback function会在一个grace period到来之后被kernel调用。再进一步说，synchronize_rcu()实际上可以依靠call_rcu()来实现：synchronize_rcu()先是block自己，然后利用call_rcu() register一个把自己wake up的call back function，当synchronize_rcu()再次得到CPU的时候，系统肯定pass了一个grace period。
每当call_rcu()被调用的时候，用户的callback function会被放到当前CPU的一个per-CPU的list中。每个CPU的timer interrupt handler（实际上是schedule了一个tasklet）会检查系统是否pass了一个grace period；如果是，CPU就会把callback list中所有等待这个grace period的callback function一起执行。
这样的设计有两个优点：