Linux 锁 (4) - seqlock

1. 前言

限于作者能力水平，本文可能存在谬误，因此而给读者带来的损失，作者不做任何承诺。

2. seqlock 实现

seqlock通过一个初始为 0 计数器，实现writer和reader共享数据的读写同步。

writer一方更新共享数据的步骤如下：

1. 计数器 +1，计数变为奇数
2. 更新共享数据
3. 计数器再 +1，计数变为偶数

reader一方读取共享数据的步骤如下：

1. 循环读取计数器的值，直到读到一个偶数值并返回，记为S1
2. 读取共享数据
3. 再次读取计数的值，直到读到一个偶数值并返回，计为S2
4. 比较 S1 和 S2，如果S1 == S2，则表明步骤2.读取的共享数据是最新的，则可用；否则跳到步骤1.再次读取。

来看具体的实现代码：

// include/linux/seqlock.htypedefstructseqcount{unsignedsequence;#ifdefCONFIG_DEBUG_LOCK_ALLOC...#endif}seqcount_t;

• seqlock 初始化

staticinlinevoid__seqcount_init(seqcount_t*s,constchar*name,structlock_class_key*key){/* * Make sure we are not reinitializing a held lock: */lockdep_init_map(&s->dep_map,name,key,0);s->sequence=0;}#defineseqcount_init(s)__seqcount_init(s,NULL,NULL)#defineSEQCNT_ZERO(lockname){.sequence=0,SEQCOUNT_DEP_MAP_INIT(lockname)}

初始化将seqcount::sequence设为0。

• writer：更新共享数据

writer更新共享数据的逻辑如下：

structseqcountseqlock;seqcount_init(&seqlock);write_seqcount_begin(&seqlock);// 更新 writer/reader 贡献的数据write_seqcount_end(&seqlock);

seqcount_init()初始化了锁的计数器为0，这在前面已经分析，这里不再赘述。来看write_seqcount_begin()和write_seqcount_end()。

先看共享数据更新之前的write_seqcount_begin()：

staticinlinevoidwrite_seqcount_begin(seqcount_t*s){write_seqcount_begin_nested(s,0);}staticinlinevoidwrite_seqcount_begin_nested(seqcount_t*s,intsubclass){raw_write_seqcount_begin(s);...}staticinlinevoidraw_write_seqcount_begin(seqcount_t*s){s->sequence++;/* 标记写开始: 奇数 *//* * 确保让系统中的所有 CPU 观察到: * s->sequence++ 操作, 在 锁保护的共享数据 的 更新操作 之前 完成. */smp_wmb();}

再看共享数据更新之后的write_seqcount_end()：

staticinlinevoidwrite_seqcount_end(seqcount_t*s){...raw_write_seqcount_end(s);}staticinlinevoidraw_write_seqcount_end(seqcount_t*s){/* * 确保让系统中的所有 CPU 观察到: * s->sequence++ 操作, 在 锁保护的共享数据 的 更新操作 之后 完成. */smp_wmb();s->sequence++;/* 标记写结束: 偶数 */}

• reader：读取（更新的）共享数据

reader读取共享数据的逻辑如下（假设使用的struct seqcount名为seqlock）：

unsignedlongseq;do{seq=read_seqcount_begin(&seqlock);// 读取共享数据}while(read_seqcount_retry(&seqlock,seq));// 本次读取数据结束

先看read_seqcount_begin()：

staticinlineunsignedread_seqcount_begin(constseqcount_t*s){...returnraw_read_seqcount_begin(s);}staticinlineunsignedraw_read_seqcount_begin(constseqcount_t*s){unsignedret=__read_seqcount_begin(s);/* * 确保系统中所有 CPU 观察到: * __read_seqcount_begin() 对锁计数器 s->sequence 的读取操作, * 在接下来 对共享数据的读操作 之前 完成. * 也即按 writer 先递增(第 1 次)了 锁计数器 s->sequence, 然后 * 更新共享数据同样的顺序去读取。 */smp_rmb();returnret;}staticinlineunsigned__read_seqcount_begin(constseqcount_t*s){unsignedret;repeat:ret=READ_ONCE(s->sequence);if(unlikely(ret&1)){/* 奇数: 正在写 */cpu_relax();gotorepeat;/* 重复读取计数器，直至写结束 */}returnret;/* 返回偶数计数器 */}

再看read_seqcount_retry()：

staticinlineintread_seqcount_retry(constseqcount_t*s,unsignedstart){/* * 确保系统中所有 CPU 观察到: * __read_seqcount_retry() 对锁计数器 s->sequence 的读取操作, 在 对共享数据的读操作 * 之后 完成。 * 也即按 writer 先更新了共享数据，然后第 2 次递增了 锁计数器 s->sequence 同样的顺序 * 去读取。 */smp_rmb();return__read_seqcount_retry(s,start);}staticinlineint__read_seqcount_retry(constseqcount_t*s,unsignedstart){returnunlikely(s->sequence!=start);}

当然，上面reader的读取逻辑，在writer首次更新共享数据前，reader也能正确工作，因为初始的计数值为 0，是一个偶数。

3. 小结

seqlock适合保护快速读写的小量数据，比单单保护单个数据 atomic 操作更进一步。类似于rwlock，seqlock也是针对读多写少的场景，但它改善了rwlock的writer的优先级低，甚至极端情况下被饿死的问题，seqlock的writer优先级更高，它可以随时打断reader（通过更新计数器）。seqlock不会导致进程睡眠，但也不会像 spinlock 那样禁用抢占，一直在一个 CPU 上自旋，seqlock持锁期间可能出现临界区代码被调度出去的情形。如果seqlock保护的共享数据包含指针，则不宜使用 seqlock，因为 writer 可能会使 reader 正在访问的指针无效，因为 reader 工作的同时，它无法阻止 writer 对共享数据的更新。最后，seqlock无法串行化多个writer，必须借助外部锁来实现这一点。

4. 参考资料

Sequence counters and sequential locks