Linux内核RCU(Read Copy Update)锁简析-前传

weewee

如果你用Linux perf tool的top命令做热点纠察时，你会发现，前10名嫌疑犯里面肯定有好几个都是锁！
在进行并行多处理时，不可 避免地会遇到锁的问题，这是不可避免的，因为这一直以来也许是保护共享数据的唯一方式，被保护的区域就是临界区。而我们知道，锁的开销是巨大的，因为它不 可避免地要么等待，要么让别人等待，然而这并不是开销的本质，开销的本质在于很多锁都采用了“原子操作”这么一个技术，如此一个原子操作会对总线或者 cache一致性造成很大的影响，比如要对一个变量进行原子加1，不要认为它很简单，其实背后会有很多不希望的操作，在某架构的处理器上，首先要LOCK 总线，这意味着LOCK不解除期间，其它处理器不能访存(起码是内存的某些区域)，可能还要涉及到刷cache，或者触发cache一致性操作...这还 不算最猛的打击，在某些架构上，存在内存栅栏，它会刷掉CPU的流水线，刷掉cache，几乎所有的为优化而设计的方案全部失效，当然，这是代价，收益就 是你保护了临界区。
       你要保护临界区，你要付出代价，这个代价如果用复杂的锁来支付的话，未免有点大。非要这样子吗？也许是你的数据结构设计地不好，也许是你的代码流设计地不 好，比如多个线程同时读共享数据，两个线程一个读一个写，能否采用环形缓冲区来减轻竞争呢？事实上很多诸如网卡，硬盘等共享外设驱动程序都是这么玩的，代 码只要保证读指针和写指针不相互超越即可，这样可以最小化锁的使用，当然这只是一个非常简单的例子。

       设计好的数据结构和代码流程是一方面，但是这个层次不够抽象，更好的方式就是设计一种更加优化的锁。读写锁这种不对称的锁应对读者多写者少的情景是一种优 化的锁，它对读者的优待就是无需等待，只要没有写者就可以直接读，否则才等待。而对于写者，它需要等待所有读者的完成。这种读写的实现可以依赖于另一种叫 做自旋锁的机制实现，我的一个实现如下所示：

typedef struct {

    spinlock_t *spinlock;

    atomic_t readers;

}rwlock_t;
static inline void rdlock(rwlock_t *lock)
{
    spinlock_t *lck = lock->spinlock;
    if (likely(!lock->readers++))
        spin_lock(lck);
}

static inline void rdunlock(rwlock_t *lock)
{
    spinlock_t *lck = lock->spinlock;
    if (likely(!--lock->readers))
        spin_unlock(lck);
}

static inline void wrlock(rwlock_t *lock)
{
    spin_lock(lock->spinlock);
}

static inline void wrunlock(rwlock_t *lock)
{
    spin_unlock(lock->spinlock);
}


很OK，不是吗？但是最好的方案就是彻底抛弃锁，彻底不用锁。
       我曾经在设计我的转发表的时候，为了降低lock开销，我为每个CPU复制了一个局部的本地转发表，这些转发表是一致的，由路由表生成，心想这就可以避免 竞争，然而，这些转发表总要面临更新问题，如何更新它们？？我最初采用的方式是采用IPI(处理器间中断)，在处理函数中，停掉处理线程，然后更新数据， 最后开启线程，这样可以在处理期间避免lock。十分合理，不是吗？可是我想复杂了。
       仔细看看读写锁的写锁，它鲁莽地进行了标准锁定操作，而读锁也是在第一个读者进来的时候采用了锁定动作。这些锁定操作导致的等待可以避免吗？看看我原始的 IPI方案，停掉线程是为了防止读者读到错误的数据，实际上是将主动将执行流让位给了写者，写者先来，然后再看看读写锁中的写者，发现有读者存在时，没有 主动地让位，而只是被动地等待，这种等待很无聊！
       能否将我的方式和读写锁的方式结合呢？
       怎么结合？按照刚刚的思路，无非就是为写者是被动等待还是抢先读者做一个决策！但是它还有一个别的选择，那就是先按照自己的流程写数据，不是写原始数据， 而是写原始数据的一份拷贝(伟大的写时拷贝)，然后将这件事挂在一个未竟事务链表上直接走人，等待系统发现所有的读者都完成时用链表上的数据逐个覆盖原始 数据。这是个多么好的结合，这就是伟大的RCU锁。读者的代价就是简单地标示一下有人读即可，而写者也无需等待持锁，直接写副本，写完走人，后来的事就交 给系统了....