RCU锁在linux内核的演变

2.6内核引入了RCU锁，这种锁十分高效，总的说来就是读时加锁，写时拷贝，读后更新。具体的流程可以参照 rcu的相关文档。本文主要谈一下rcu在linux2.6内核的演变过程，它分别经历了三个阶段，分别是传统rcu锁，可抢占rcu锁以及2.6.29 中将要引入的树形分层rcu锁。
     linux中最早引入的rcu锁十分的粗糙，实现原理也是非常简单，毕竟linux中不管多复杂的机制一开始的时候都是十分简单的，这一点可以看看 linux0.01到linux2.6.28的演变。传统的rcu锁就是在有读者读数据的时候加上rcu锁，注意这里的“加锁”仅仅是逻辑意义上的加锁， 至于真正实现可以很灵活，实际上linux的实现就没有用到所谓的锁，而是简单的禁用抢占。为何可以这么实现呢？因为在一个cpu上禁用了抢占也就禁用了 这个cpu上的进程切换，该cpu上的当前进程将一直运行，除非重新使能抢占，那么什么时候使能抢占呢？当然是在读者释放rcu锁的时候了，而linux 中传统rcu实现规定在进程切换的时候才会运行更新回调函数，这就是本质。每当一个cpu经历进程上下文切换时，rcu就说此cpu经过了一个 quiescent state，而所有的cpu都经过一个quiescent state的时间称为一个grace period，在这个grace period点之后，该grace period的更新回调函数就可以被安全的执行了，因为此时，系统已经确定所有的读者都不再持有rcu锁了。我们再次理一下这是为什么，读者释放锁就是使 能抢占，也就是可以切换进程，而且换进程的时候rcu就认为经过了一个quiescent state，所有的cpu都经过了一个quiescent state意味着所有的cpu都可以进程切换了，就是意味着所有的cpu上的读者都不再持有rcu锁了。就是这么简单，但是我们看一下这个实现会存在什么 问题，只要读者加锁，就意味着禁用抢占，就是禁止切换，这会很大地减低系统的交互性能，当然也会降低实时任务的性能，这一切都不是想要的，单独一个rcu 把大家都拖下水实在不应该，难道要为了保护读者保护的数据而冻住整个系统不让切换进程吗？传统的rcu不允许占有rcu的进程睡眠，睡眠了进程又不允许切 换，系统就相当于死掉了。于是下一个版本的rcu就要出来了，它试图将rcu对系统的影响减小到最小，也就是说将rcu单独做成一个可以自洽自治的模块， 它本身就可以处理好数据的保护而不再需要通过系统其它的机制来确保rcu读者数据在允许更新前被保护，这就是preemptible-RCU锁。其实 linux最开始引入的所谓传统的rcu锁是一个很失败的实现，操作系统的任务就是管理各种复杂的模块以模拟真实世界，优秀的操作系统可以做到模块化的管 理各种机制，比如进程，内存，设备，以及各种锁和并发机制等等，在管理它们的时候各个模块低耦合地通信而不至于互相依赖互相影响性能，如果说要想不出问 题，最简单也是最失败的方式就是只让一个进程跑，没有切换没有共享当然也就没有了竞争，没有竞争也就意味着没有竞态，也就意味着没有了并发问题，这很简 单，但是很不灵活，也让人感觉到这不是一个优秀的操作系统，就好像人不能说怕淋雨就不出门，正确的解决方案就是发明出雨伞和雨衣。linux第一代rcu 就是这种很差劲的实现。
既然第二代rcu是preemptible的rcu，那么就是说在持有rcu锁期间不再需要禁用抢占了，这个实现看到 这里就知道它是一个很优秀的实现，因 为它不再需要抢占机制帮忙来实现数据保护，rcu的内部机制已经可以实现数据保护了。那么它是怎么实现的呢？如果你不想用别的机制实现rcu数据保护，那 么就要自己实现，当然代价就是引入新的数据结构和逻辑控制机制，在preemptible-rcu中，一个grace period被分解为了两个阶段而不是所有cpu完成quiescent state了所有的数据保护机制都是在这两个阶段大做文章而实现的。这两个阶段通过一系列的软件计数器来实现了rcu，之所以分为两个阶段是因为rcu有 lock和unlock两个动作，我们能不能像实现传统rcu一样，不用真正的锁就实现逻辑上的rcu锁呢？当然可以了，引入一个每cpu变量：
#define GP_STAGES    2
struct rcu_data {
         spinlock_t      lock;           //保护此结构中字段的自旋锁
         long            completed;      //总的阶段计数器
         int             waitlistcount;
         struct rcu_head *nextlist;     //一些链表，记录更新回调函数
         struct rcu_head **nexttail;
         struct rcu_head *waitlist[GP_STAGES];
         struct rcu_head **waittail[GP_STAGES];
         struct rcu_head *donelist;      
         struct rcu_head **donetail;
         long rcu_flipctr[2];        //这个很重要
         struct rcu_head *nextschedlist;
         struct rcu_head **nextschedtail;
         struct rcu_head *waitschedlist;
         struct rcu_head **waitschedtail;
         int rcu_sched_sleeping;
};
rcu_flipctr 这个字段十分重要，它是一个数组，每个元素其实就是一个计数器，第一个元素记录的是在本阶段中的本cpu的rcu锁持有者数量，而第二个元素表示上个阶段 的还没有释放的本cpu的rcu锁数量，注意，只有unlock操作可以递减第二个元素，lock操作只能递增第一个元素，另外unlock操作也可以递 减第一个元素，一旦所有cpu的第二个元素的和变为0了，那么就可以向前推进一个阶段了，在下一个阶段中，第一个元素成了只有unlock才能递减的元 素，而第二个元素lock和unlock都可触及，记录着当前阶段的新rcu锁数量，往下依次类推。每个阶段都要等待所有cpu的rcu_flipctr 的同一个元素的和成为0，然后进入下一个阶段，进入下一个阶段同时交换rcu_flipctr的两个元素的意义。系统维持一个状态机，为rcu设置了好几 种状态，其中包括一个等待所有cpu的前一个阶段的rcu计数器降到0的状态，这一个状态过去以后，rcu状态机就可以向前推进一个阶段了，注意，可抢占 的rcu锁机制的重点执行点不再是grace period，而是一个grace period的两个阶段，可抢占的rcu锁也是以阶段为基准的，也就是说，在每一个阶段结束时都会有一个计数器的和降为0，这时同步将这个计数器对应的回 调函数链表推进到最前面，然后就可以安全地执行这些更新回调函数了，这里执行回调函数链表的时间是每个阶段结束，而不必等到一个grace period的第二个阶段结束时。原先的传统rcu的实现在机进程切换时更新quiescent state状态然后判断是否过了一个grace period，现在的可抢占的rcu中，仅在时钟中断里面执行rcu状态机，状态机根据其前一个状态和当前的rcu状态采取不同的措施以维持状态机继续运 转，这么看来可抢占的rcu就和抢占没有关系了，cpu可以随便被抢占而不会破坏rcu读者保护的数据，于是就说rcu模块和抢占模块解耦合了，各自可以 通过各自的方式进行设计，调试，优化以提高性能而不用像原来那样互相依赖杂糅在一起。
我们看一下lock和unlock函数：
void __rcu_read_lock(void)
{
...
         } else {
                 unsigned long flags;
                 local_irq_save(flags);
                 idx = ACCESS_ONCE(rcu_ctrlblk.completed) & 0x1;
                 ACCESS_ONCE(RCU_DATA_ME()->rcu_flipctr[idx])++;
                 ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting + 1;
                 ACCESS_ONCE(t->rcu_flipctr_idx) = idx;
                 local_irq_restore(flags);
         }
}
void __rcu_read_unlock(void)
{
...
         } else {
                 unsigned long flags;
                 local_irq_save(flags);
                 idx = ACCESS_ONCE(t->rcu_flipctr_idx);
                 ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting - 1;
                 ACCESS_ONCE(RCU_DATA_ME()->rcu_flipctr[idx])--;
                 local_irq_restore(flags);
         }
}
然后看一幅图：

另外linux绝对不会放过任何可以优化的空间的，只要能节省一条指令的执行，那么linux内核就会认为这么做就是值得的，比如在可抢占的rcu中，有两个函数：
void rcu_irq_enter(void)
{
         int cpu = smp_processor_id();
         struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
         if (per_cpu(rcu_update_flag, cpu))
                 per_cpu(rcu_update_flag, cpu)++;
         if (!in_interrupt() && (rdssp->dynticks & 0x1) == 0) {
                 rdssp->dynticks++;
                 smp_mb();
                 per_cpu(rcu_update_flag, cpu)++;
         }
}
void rcu_irq_exit(void)
{
         int cpu = smp_processor_id();
         struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
         if (per_cpu(rcu_update_flag, cpu)) {
                 if (--per_cpu(rcu_update_flag, cpu))
                         return;
                 WARN_ON(in_interrupt());
                 smp_mb();
                 rdssp->dynticks++;
                 WARN_ON(rdssp->dynticks & 0x1);
         }
}
注 意有一个dynticks，它在进入irq和出去irq的时候都会递增，它被初始化为1，但是更要注意，这种递增是有条件的，比如在 rcu_irq_enter中，这个dynticks递增的条件就是中断非嵌套并且dynticks为偶数，显然第一次进入中断时dynticks不可能 为偶数，这就是说dynticks应该第一次在rcu_irq_exit中被增加，其实这个小算法的意义就是在进入nohz的时候或者停掉时钟节拍的时 候，当事cpu就没有必要按照常规的更新自己-通知他人-等待他人的方式维持状态机了，而是直接忽略当事cpu，按照应该的方式直接将该cpu向前推进， 这样的话就免去了很多操作，在实现这个小算法的时候，巧妙地利用了奇数偶数的方式，判断上减少了很多条指令，具体不多说，最后看一眼下面的利用 dynticks的函数：
static inline int rcu_try_flip_waitack_needed(int cpu)
{
         long curr;
         long snap;
         struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
         curr = rdssp->dynticks;
         snap = rdssp->dynticks_snap;
         smp_mb();
         if ((curr == snap) && ((curr & 0x1) == 0))
                 return 0;
         if ((curr - snap) > 2 || (curr & 0x1) == 0)
                 return 0;
         return 1;
}
以 上就是第二代的可抢占的rcu的思想和框架，那么第三代的rcu在那些方面有所创新呢？虽然第三代的rcu还没有被合进2.6.28内核，准备合入 2.6.29内核，但是Changelog中已经描述地很清晰了，它的主体思想就是：One effective way to reduce lock contention is to create a hierarchy.这句话真的要仔细推敲，这涉及到一个设计思想问题。分布式的对等结构是趋势吗？这么看来这句话就是大错特错了，但是分级管理确实可以 省很多事，这样分级正确的话，对等结构岂不是错误的结构吗？因此这个问题很有意义。国家机器应该是何种结构呢？金字塔式的等级政府合理吗？第三代的rcu 称为树形rcu，它采用了树结构，将锁定定义为一个分层分级的操作。这就类似于百米赛跑选拔过程，如果一共有50个人参加，那么有两种方式可以进行选拔， 一个是50个人同时上场，这样的话消耗巨大，另外就是分批分组选拔，这样的话消耗很小，分批分组其实就是分级选拔，将50个人分为25组，每组2人，这样 的话同时只有2人比赛，而且25组不必在一个场地上。树形的rcu就是这么干的，把所有的cpu分组，每组2个或多于2个，这样同时竞争rcu锁的cpu 就会减少很多，低级组的赢家竞争更高一级的rcu，然后赢家继续类似的竞争。见下面的几幅图：

在上面的图中，6个cpu分为3组，每两个同时竞争，之后赢了的3个再竞争，避免了6个同时竞争。

上 面的图就不多说了。在存在大量cpu的机器上，难道要把cpu们分为很多组，必须两个一组吗？没有必要，两个一组当然可以，但是那是教条，实际上文档上讲 64个cpu同时竞争锁的情形下所测试得到的性能是很不错的，因此上面的图示所示的两两分组的方式实属为了说明问题而设，树形rcu的真正用武之地不是少 量cpu的机器而是大量，也就是成千cpu的巨猛机器，这些是我接触不到的，因此我只谈思想而没有任何实战经验。如果为了运用树形rcu而在拥有少量 cpu的机器上实施的话，那么势必会因为树形复杂的结构而占用大量的内存空间，所得到的益处不能补偿其带来的弊端，因此一味追求新技术是不对的，必须了解 这种新技术最适合的场合再作考虑，考虑好是用时间换空间还是用空间换时间，自己的系统是空间重要还是时间重要。
另外树形的rcu也实现了节能机制，同样利用可抢占rcu的奇数偶数小算法技巧实现，这样持有偶数计数器的cpu就不必被唤醒以维持状态机，因为持有偶数计数器的cpu处的状态是时钟节拍停止（nohz），或者挂起状态，这样就减少了不必要的能源消耗，可谓不错。
其 实，树形的分层结构不但可以实现rcu，任何锁都可以用树形结构实现，树形锁的关键在于它可以减少同时竞争锁的cpu的数量，从而避免过多的竞态。.第 一代rcu在linux上实现表明了linux可以实现这个古老的锁机制;第二代的可抢占的rcu说明了一个优秀的机制可以作为一个模块脱离别的机制独立 存在,并且活得很好;第三代的树形rcu表明在实施上,分布式的对等结构是不错的,在管理上有时分层的等级结构是必要的,毕竟实施的时候实体很多很不确 定,分布式对等结构可以增加系统的对称性提高效率,但是管理的时候实体很确定,工作很明确,分层的等级结构带来的是更有条理,管理更有效.