Linux内核原语（七）——顺序锁（seqlock）
小狼@http://blog.csdn.net/xiaolangyangyang
上一章中讲到的读-写自旋锁，更加偏向于读者。内核提供了更加偏向于写者的锁 —— seqlock
这种锁提供了一种简单的读写共享的机制，他的设计偏向于写者，无论是什么情况（没有多个写者竞争的情况），写者都有直接写入的权利（霸道），而读者呢？这里提供了一个序列值，当写者进入的时候，这个序列值会加 1，而读者去在读出数值的前后分别来 check 这个值，便知道是否在读的过程中（奇数还偶数），被写者“篡改”过数据，如果有的话，则再次 spin 的去读，一直到数据被完全的篡改完毕。
顺序锁临界区只允许一个writer thread进入（在多个写者之间是互斥的），临界区只允许一个writer thread进入，在没有writer thread的情况下，reader thread可以随意进入，也就是说reader不会阻挡reader。在临界区只有有reader thread的情况下，writer thread可以立刻执行，不会等待
Writer thread的操作：
对于writer thread，获取seqlock操作如下：
（1）获取锁（例如spin lock），该锁确保临界区只有一个writer进入。
（2）sequence counter加一
释放seqlock操作如下：
（1）释放锁，允许其他writer thread进入临界区。
（2）sequence counter加一（注意：不是减一哦，sequence counter是一个不断累加的counter）
由上面的操作可知，如果临界区没有任何的writer thread，那么sequence counter是偶数（sequence counter初始化为0），如果临界区有一个writer thread（当然，也只能有一个），那么sequence counter是奇数。
Reader thread的操作如下：
（1）获取sequence counter的值，如果是偶数，可以进入临界区，如果是奇数，那么等待writer离开临界区（sequence counter变成偶数）。进入临界区时候的sequence counter的值我们称之old sequence counter。
（2）进入临界区，读取数据
（3）获取sequence counter的值，如果等于old sequence counter，说明一切OK，否则回到step（1）
适用场景：
一般而言，seqlock适用于：
（1）read操作比较频繁
（2）write操作较少，但是性能要求高，不希望被reader thread阻挡（之所以要求write操作较少主要是考虑read side的性能）
（3）数据类型比较简单，但是数据的访问又无法利用原子操作来保护。我们举一个简单的例子来描述：假设需要保护的数据是一个链表，header--->A node--->B node--->C node--->null。reader thread遍历链表的过程中，将B node的指针赋给了临时变量x，这时候，中断发生了，reader thread被preempt（注意，对于seqlock，reader并没有禁止抢占）。这样在其他cpu上执行的writer thread有充足的时间释放B node的memory（注意：reader thread中的临时变量x还指向这段内存）。当read thread恢复执行，并通过x这个指针进行内存访问（例如试图通过next找到C node），悲剧发生了……
顺序锁的使用
定义
定义一个顺序锁有两种方式：
seqlock_t seqlock
seqlock_init(&seqlock)DEFINE_SEQLOCK(seqlock)
写临界区：
write_seqlock(&seqlock);
/* -------- 写临界区 ---------*/
write_sequnlock(&seqlock);读临界区：
unsigned long seq;
do {
seq = read_seqbegin(&seqlock);
/* ---------- 这里读临界区数据 ----------*/
} while (read_seqretry(&seqlock, seq));
例子：在 kernel 中，jiffies_64 保存了从系统启动以来的 tick 数目，对该数据的访问（以及其他jiffies相关数据）需要持有jiffies_lock 这个 seq lock：
读当前的 tick ：
u64 get_jiffies_64(void)
{
do {
seq = read_seqbegin(&jiffies_lock);
ret = jiffies_64;
} while (read_seqretry(&jiffies_lock, seq));
}内核更新当前的 tick ：
static void tick_do_update_jiffies64(ktime_t now)
{
write_seqlock(&jiffies_lock);
/* 临界区会修改jiffies_64等相关变量 */
write_sequnlock(&jiffies_lock);
}
顺序锁的实现
1. seqlock_t 结构：
typedef struct {
struct seqcount seqcount;
spinlock_t lock;
} seqlock_t;2. write_seqlock/write_sequnlock
static inline void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock);
sl->sequence++;
smp_wmb();
}
static inline void write_sequnlock(seqlock_t *sl)
{
smp_wmb();
s->sequence++;
spin_unlock(&sl->lock);
}可以看到 seqlock 其实也是基于 spinlock 的。smp_wmb 是写内存屏障，由于seq lock 是基于 sequence counter 的，所以必须保证这个操作。
3. read_seqbegin：
static inline unsigned read_seqbegin(const seqlock_t *sl)
{
unsigned ret;
repeat:
ret = ACCESS_ONCE(sl->sequence); －－－进入临界区之前，先要获取sequenc counter的快照
if (unlikely(ret & 1)) { －－－－－如果是奇数，说明有writer thread
cpu_relax();
goto repeat; －－－－如果有writer，那么先不要进入临界区，不断的polling sequenc counter
}
smp_rmb(); －－－确保sequenc counter和临界区的内存访问顺序
return ret;
}如果有writer thread，read_seqbegin函数中会有一个不断polling sequenc counter，直到其变成偶数的过程，在这个过程中，如果不加以控制，那么整体系统的性能会有损失（这里的性能指的是功耗和速度）。因此，在polling过程中，有一个cpu_relax的调用，对于ARM64，其代码是：
static inline void cpu_relax(void)
{
asm volatile("yield" ::: "memory");
}yield 指令用来告知硬件系统，本cpu上执行的指令是polling操作，没有那么急迫，如果有任何的资源冲突，本cpu可以让出控制权。
4. read_seqretry
static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start)
{
smp_rmb();－－－确保sequenc counter和临界区的内存访问顺序
return unlikely(sl->sequence != start);
}start参数就是进入临界区时候的sequenc counter的快照，比对当前退出临界区的sequenc counter，如果相等，说明没有writer进入打搅reader thread，那么可以愉快的离开临界区。
还有一个比较有意思的逻辑问题：read_seqbegin为何要进行奇偶判断？把一切都推到read_seqretry中进行判断不可以吗？也就是说，为何read_seqbegin要等到没有writer thread的情况下才进入临界区？其实有writer thread也可以进入，反正在read_seqretry中可以进行奇偶以及相等判断，从而保证逻辑的正确性。当然，这样想也是对的，不过在performance上有欠缺，reader在检测到有writer thread在临界区后，仍然放reader thread进入，可能会导致writer thread的一些额外的开销（cache miss），因此，最好的方法是在read_seqbegin中拦截。
参考文献 ： http://www.wowotech.net/kernel_synchronization/seqlock.html