linux seqlock & rcu 浅析

在linux内核中，有很多同步机制。比较经典的有spin_lock（忙等待的锁）、mutex（互斥锁）、semaphore（信号量）、等。并且它们几乎都有对应的rw_XXX（读写锁），以便在能够区分读与写的情况下，让读操作相互不互斥（读写、写写依然互斥）。
而seqlock和rcu应该可以不算在经典之列，它们是两种比较有意思的同步机制。

seqlock（顺序锁）

用于能够区分读与写的场合，并且是读操作很多、写操作很少，写操作的优先权大于读操作。
seqlock的实现思路是，用一个递增的整型数表示sequence。写操作进入临界区时，sequence++；退出临界区时，sequence再++。写操作还需要获得一个锁（比如mutex），这个锁仅用于写写互斥，以保证同一时间最多只有一个正在进行的写操作。
当sequence为奇数时，表示有写操作正在进行，这时读操作要进入临界区需要等待，直到sequence变为偶数。读操作进入临界区时，需要记录下当前sequence的值，等它退出临界区的时候用记录的sequence与当前sequence做比较，不相等则表示在读操作进入临界区期间发生了写操作，这时候读操作读到的东西是无效的，需要返回重试。

seqlock写写是必须要互斥的。但是seqlock的应用场景本身就是读多写少的情况，写冲突的概率是很低的。所以这里的写写互斥基本上不会有什么性能损失。
而读写操作是不需要互斥的。seqlock的应用场景是写操作优先于读操作，对于写操作来说，几乎是没有阻塞的（除非发生写写冲突这一小概率事件），只需要做sequence++这一附加动作。而读操作也不需要阻塞，只是当发现读写冲突时需要retry。

seqlock的一个典型应用是时钟的更新，系统中每1毫秒会有一个时钟中断，相应的中断处理程序会更新时钟（见《linux时钟浅析》）（写操作）。而用户程序可以调用gettimeofday之类的系统调用来获取当前时间（读操作）。在这种情况下，使用seqlock可以避免过多的gettimeofday系统调用把中断处理程序给阻塞了（如果使用读写锁，而不用seqlock的话就会这样）。中断处理程序总是优先的，而如果gettimeofday系统调用与之冲突了，那用户程序多等等也无妨。

seqlock的实现非常简单：
写操作进入临界区时：
void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock); // 上写写互斥锁
++sl->sequence; // sequence++
}
写操作退出临界区时：
void write_sequnlock(seqlock_t *sl)
{
sl->sequence++; // sequence再++
spin_unlock(&sl->lock); // 释放写写互斥锁
}

读操作进入临界区时：
unsigned read_seqbegin(const seqlock_t *sl)
{
unsigned ret;
repeat:
ret = sl->sequence; // 读sequence值
if (unlikely(ret & 1)) { // 如果sequence为奇数自旋等待
goto repeat;
}
return ret;
}
读操作尝试退出临界区时：
int read_seqretry(const seqlock_t *sl, unsigned start)
{
return (sl->sequence != start); // 看看sequence与进入临界区时是否发生过改变
}
而读操作一般会这样进行：
do {
seq = read_seqbegin(&seq_lock); // 进入临界区
do_something();
} while (read_seqretry(&seq_lock, seq)); // 尝试退出临界区，存在冲突则重试

RCU（read-copy-update）

RCU也是用于能够区分读与写的场合，并且也是读多写少，但是读操作的优先权大于写操作（与seqlock相反）。
RCU的实现思路是，读操作不需要互斥、不需要阻塞、也不需要原子指令，直接读就行了。而写操作在进行之前需要把被写的对象copy一份，写完之后再更新回去。其实RCU所能保护的并不是任意的临界区，它只能保护由指针指向的对象（而不保护指针本身）。读操作通过这个指针来访问对象（这个对象就是临界区）；写操作把对象复制一份，然后更新，最后修改指针使其指向新的对象。由于指针总是一个字长的，对它的读写对于CPU来说总是原子的，所以不用担心更新指针只更新到一半就被读取的情况（指针的值为0x11111111，要更新为0x22222222，不会出现类似0x11112222这样的中间状态）。所以，当读写操作同时发生时，读操作要么读到指针的旧值，引用了更新前的对象、要么读到了指针的新值，引用了更新后的对象。即使同时有多个写操作发生也没关系（是否需要写写互斥跟写操作本身的场景相关）。

RCU封装了rcu_dereference和rcu_assign_pointer两个函数，分别用于对指针进行读和写。
rcu_assign_pointer(p, v) => (p) = (v)
rcu_dereference(p) => (p)
里面其实就是简单的指针读和写，然后可能设置内存屏障（以避免编译器或CPU指令乱序对程序造成影响）。当然，如果出现了一种奇怪的不能直接保证原子性读写指针的体系结构，还需要这两个函数来保证原子性。

可以看到，使用了RCU之后，读写操作竟然神奇地都不需要阻塞了，临界区已经不是临界区了。只不过写操作稍微麻烦些，需要read、copy再update。不过RCU的核心问题并不是如何同步，而是如何释放旧的对象。指向对象的指针被更新了，但是之前发生的读操作可能还在引用旧的对象呢，旧的对象什么时候释放掉呢？让读操作来释放旧的对象似乎并不是很和理，它不知道对象是否已经被更新了，也不知道有多少读操作都引用了这个旧对象。给对象加一个引用计数呢？这或许可以奏效，但是这也太不通用了，RCU是一种机制，如果要求每个使用RCU的对象都在对象的某某位置维护一个引用计数，相当于RCU机制要跟具体的对象耦合上了。并且对引用计数的修改还需要另一套同步机制来提供保障。
为解决旧对象释放的问题，RCU提供了四个函数（另外还有一些它们的变形）：
rcu_read_lock(void)、rcu_read_unlock(void)
synchronize_rcu(void)、call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *head))。
当读操作要调用rcu_dereference访问对象之前，需要先调用rcu_read_lock；当不再需要访问对象时，调用rcu_read_unlock。
当写操作调用rcu_assign_pointer完成对对象的更新之后，需要调用synchronize_rcu或call_rcu。其中synchronize_rcu会阻塞等待在此之前所有调用了rcu_read_lock的读操作都已经调用rcu_read_unlock，synchronize_rcu返回后写操作一方就可以将被它替换掉的旧对象释放了；而call_rcu则是通过注册回调函数的方式，由回调函数来释放旧对象，写操作一方将不需要阻塞等待。同样，等到在此之前所有调用了rcu_read_lock的读操作都调用rcu_read_unlock之后，回调函数将被调用。

如果你足够细心，可能已经注意到了这样一个问题。synchronize_rcu和call_rcu会等待的是“在此之前所有调用了rcu_read_lock的读操作都已经调用了rcu_read_unlock”，然而在rcu_assign_pointer与synchronize_rcu或call_rcu之间，可能也有读操作发生（调用了rcu_read_lock），它们引用到的是写操作rcu_assign_pointer后的新对象。按理说写操作一方想要释放旧对象时，是不需要等待这样的读操作的。但是由于这些读操作发生在synchronize_rcu或call_rcu之前，按照RCU的机制，还真得等它们都rcu_read_unlock。这岂不是多等了一些时日？
实际情况的确是这样，甚至可能更糟。因为目前linux内核里面的RCU是一个全局的实现，注意，rcu_read_lock、synchronize_rcu、等等操作都是不带参数的。它不像seqlock或其他同步机制那样，一把锁保护一个临界区。这个全局的RCU将保护使用RCU机制的所有临界区。所以，对于写操作一方来说，在它调用synchronize_rcu或call_rcu之前发生的所有读操作它都得等待（不管读的对象与该写操作有无关系），直到这些读操作都rcu_read_unlock之后，旧的对象才能被释放。所以，写操作更新对象之后，旧对象并不是精确地在它能够被释放之时立刻被释放的，可能会存在一定的延迟。
不过话说回来，这样的实现减少了很多不必要的麻烦，因为旧的对象晚一些释放是不会有太大关系的。想一想，精确旧对象的释放时机有多大意义呢？无非是尽可能早的回收一些内存（一般来说，内核里面使用的这些对象并不会太大吧，晚一点回收也不会晚得太过分吧）。但是为此你得花费很大的代价去跟踪每一个对象的引用情况，这是不是有些得不偿失呢？

最后，RCU要求，读操作在rcu_read_lock与rcu_read_unlock之间是不能睡眠的（WHY？），call_rcu提供的回调函数也不能睡眠（因为回调函数一般会在软中断里面去调用，中断上下文是不能睡眠的，见《linux中断处理浅析》）。

那么，RCU具体是怎么实现的呢？尽管没有要求在精确的时间回收旧对象，RCU的实现还是很复杂的。以下简单讨论一下rcu_read_lock、rcu_read_unlock、call_rcu三个函数的实现。而synchronize_rcu实际上是利用call_rcu来实现的（调用call_rcu提交一个回调函数，然后自己进入睡眠，而回调函数要做的事情就是把自己唤醒）。
在linux 2.6.30版本中，RCU有三种实现，分别命名为rcuclassic、rcupreempt、rcutree。这三种实现也是逐步发展出来的，最开始是rcuclassic，然后rcupreempt，最后rcutree。在编译内核时可以通过编译选项选择需要使用的RCU实现。

rcuclassic
rcuclassic的实现思路是，读操作在rcu_read_lock时禁止内核抢占、在rcu_read_unlock时重新启用内核抢占。由于RCU只会在内核态里面使用，而且RCU也要求rcu_read_lock与rcu_read_unlock之间不能睡眠。所以在rcu_read_lock之后，这个读操作的相关代码肯定会在当前CPU上持续被执行，直到rcu_read_unlock之后才可能被调度。而同一时间，在一个CPU上，也最多只能有一个正在进行的读操作。可以说，rcuclassic是基于CPU来跟踪读操作的。
于是，如果发现一个CPU已经发生了调度，就说明这个CPU上的读操作肯定已经rcu_read_unlock了（注意这里又是一次延迟，rcu_read_unlock之后可能还要过一段时间才会发生调度。RCU的实现中，这样的延迟随处可见，因为它根本就不要求在精确的时间点回收旧对象）。于是，从一次call_rcu被调用之后开始，如果等到所有CPU都已经发生了调度，这次call_rcu需要等待的读操作就必定都已经rcu_read_unlock了，这时候就可以处理这个call_rcu提交的回调函数了。
但是实现上，rcuclassic并不是为每一次call_rcu都提供一个这样的等待周期（等待所有CPU都已发生调度），那样的话粒度太细，实现起来会比较复杂。rcuclassic将现有的全部call_rcu提交的回调函数分为两个批次（batch），以批次为单位来进行等待。如果所有CPU都已发生调度，则第一批次的所有回调函数将被调用，然后将第一批次清空、第二批变为第一批，并继续下一次的等待。而所有新来的call_rcu总是将回调函数提交到第二批。
rcuclassic逻辑上通过三个链表来管理call_rcu提交的回调函数，分别是第二批次链表、第一批次链表、待处理链表（2.6.30版本的实现实际用了四个链表，把待处理链表分解成两个链表）。call_rcu总是将回调函数提交到第二批次链表中，如果发现第一批次链表为空（之前的call_rcu都已经处理完了），就将第二批次链表中的回调函数都移入第一批次链表（第二批次链表清空）；从回调函数被移入第一批次链表开始，如果所有CPU都发生了调度，则将第一批次链表中的回调函数都移入待处理链表（第一批次链表清空，同时第二批次链表中新的回调函数又被移过来）；待处理链表里面的回调函数都是等待被调用的，下一次进入软中断的时候就要调用它们。
什么时候检查“所有CPU都已发生调度”呢？并不是在CPU发生调度的时候。调度的时候只是做一个标记，标记这个CPU已经调度过了。而检查是放在每毫秒一次的时钟中断处理函数里面来进行的。
另外，这里提到的第二批次链表、第一批次链表、待处理链表其实是每个CPU维护一份的，这样可以避免操作链表时CPU之间的竞争。
rcuclassic的实现利用了禁止内核抢占，这对于一些实时性要求高的环境是不适用的（实时性要求不高则无妨），所以后来又有了rcupreempt的实现。

rcupreempt
rcupreempt是相对于rcuclassic禁止内核抢占而言的，rcupreempt允许内核抢占，以满足更高的实时性要求。
rcupreempt的实现思路是，通过计数器来记录rcu_read_lock与rcu_read_unlock发生的次数。读操作在rcu_read_lock时给计数器加1，rcu_read_unlock时则减1。只要计数器的值为0，说明所有的读操作都rcu_read_unlock了，则在此之前所有call_rcu提交的回调函数都可以被执行。不过，这样的话，新来的rcu_read_lock会使得之前的call_rcu不断延迟（如果rcu_read_unlock总是跟不上rcu_read_lock的速度，那么计数器可能永远都无法减为0。但是对于之前的某个call_rcu来说，它所关心的读操作却可能都已经rcu_read_unlock了）。所以，rcupreempt还是像rcuclassic那样，将call_rcu提交的回调函数分为两个批次，然后由两个计数器分别计数。
跟rcuclassic一样，call_rcu提交的回调函数总是加入到第二批次，所以rcu_read_lock总是增加第二批次的计数。而当第一批次为空时，第二批次将移动到第一批次，计数值也应该一起移过来。所以，rcu_read_unlock必须知道它应该减少哪个批次的计数（rcu_read_lock增加第二批次的计数，之后第一批次可能被处理，然后第二批次被移动到第一批次。这种情况下对应的rcu_read_unlock应该减少的是第一批次的计数了）。
实现上，rcupreempt提供了两个[等待队列+计数器]，并且交替的选择其中的一个作为“第一批次”。之前说的将第二批次移动到第一批次的过程实际上就是批次交替一次的过程，批次并没移动，只是两个[等待队列+计数器]的含义发生了交换。于是，rcu_read_lock的时候需要记录下现在增加的是第几个计数器的计数，rcu_read_unlock就相应减少那个计数就行了。
那么rcu_read_lock与rcu_read_unlock怎么对应上呢？rcupreempt已经不禁止内核抢占了，同一个读操作里面的rcu_read_lock和rcu_read_unlock可能发生在不同CPU上，不能通过CPU来联系rcu_read_lock与rcu_read_unlock，只能通过上下文，也就是执行rcu_read_lock与rcu_read_unlock的进程。所以，在进程控制块（task_struct）中新增了一个index字段，用来记录这个进程上执行的rcu_read_lock增加了哪个计数器的计数，于是这个进程上执行的rcu_read_unlock也应该减少相应的计数。
rcupreempt也维护了一个待处理链表。于是，当第一批次的计数为0时，第一批次里面的回调函数将被移动到待处理链表中，等到下一次进入软中断的时候就调用它们。然后第一批次被清空，两个批次做交换（相当于第二批次移动到第一批次）。
跟rcuclassic类似，对于计数值的检查并不是在rcu_read_unlock的时候进行的，rcu_read_unlock只管修改计数值。而检查也是放在每毫秒一次的时钟中断处理函数里面来进行的。
同样，这里提到的等待队列和计数器也是每个CPU维护一份的，以避免操作链表和计数器时CPU之间的竞争。那么当然，要检查第一批次计数为0，是需要把所有CPU的第一批次计数值进行相加的。

rcutree
最后说说rcutree。它跟rcuclassic的实现思路几乎是一模一样的，通过禁止抢占、检查每一个CPU是否已经发生过调度，来判断发生在某一批次rcu_call之前的所有读操作是否都已经rcu_read_unlock。并且实现上，批次的管理、各种队列、等等都几乎一样，CPU发生调度时也是通过设置一个标记来表示自己已经调度过了，然后又在时钟中断的处理程序中判断是否所有CPU都已经发生过调度……那么，不同之处在哪里呢？在于“判断是否每一个CPU都调度过”这一细节上。
rcuclassic对于多个CPU的管理是对称的，在时钟中断处理函数中，要判断是否每一个CPU都调度过就得去看每一个CPU所设置的标记，而这个“看”的过程势必是需要互斥的（因为这些标记也会被其他CPU读或写）。这样就造成了CPU之间的竞争。如果CPU个数不多，就这么竞争一下倒也无妨。要是CPU很多的话（比如64个？或更多？），那当然越少竞争越好。rcutree就是为了这种拥有很多CPU的环境而设计的，以期减少竞争。
rcutree的思路是提供一个树型结构，其中的每一个非叶子节点提供一个锁（代表了一次竞争），而每个CPU就对应到树的叶子节点上。然后呢？当需要判断“是否每一个CPU都调度过”的时候，CPU尝试在自己的父节点上锁（这个锁只会由它的子节点来竞争，而不会被所有CPU竞争），然后判断这个“父节点”的子节点（CPU）是否都已经调度过。如果不是，则显然“每一个CPU都调度过”不成立。而如果是，则再向上遍历，直到走到树根，那么就可以知道所有CPU都已经调度过了。使用这样的树型结构就缩小了每一次加锁的粒度，减少了CPU间的竞争。