Linux并发 - 顺序锁
Introduction
概述
读写自旋锁一个很大的缺点是容易造成写饥饿，内核给出的解决方案之一是顺序锁。
顺序锁特点：
- 适用于读多写少的场景
- 读者之间是并发的; 写者和读者, 写者和写者都是互斥的
- 写者的优先级更高，一旦数据被更新，读者需要丢弃掉已经读到的数据（牺牲读者的性能）
顺序锁的思想比较简单，所有的代码位于 linux-5.10/include/linux/seqlock.h
当今内核提供两种方式使用顺序锁：
- 直接使用 seqcount：写者的互斥由用户自行保证（通常是额外自旋锁）
- 使用seqlock: 基于 seqcount 实现，添加自旋锁用于做写者之间数据一致性的保护。
由于 seqcount 是所有接口实现的核心，故我们先分析 seqcount， 再分析 seqlock
Seqcount
概述
seqcount 是顺序锁的核心，本章的目的就是了解其基本使用于原理
数据结构
seqcount 数据结构内容很简洁，就只有一个表示序号的sequence
[linux-5.10/include/linux/seqlock.h]
typedef struct seqcount {
unsigned sequence;
... //CONFIG_DEBUG_LOCK_ALLOC
} seqcount_t;
API
seqcount 最基础的API如下
void seqcount_init(seqcount_t *s);
unsigned read_seqcount_begin(seqcount_t *s);
int read_seqcount_t_retry(const seqcount_t *s, unsigned start); //需要retry返回true
void write_seqcount_begin(seqcount_t *s);
void write_seqcount_end(seqcount_t *s);
使用范例
使用方式参考内核对 jiffies_64 的读写
[linux-5.10/kernel/time/jiffies.c]
__cacheline_aligned_in_smp seqcount_t jiffies_seq; //定义，(全局变量默认为0,不用初始化?)
u64 get_jiffies_64(void)
{
unsigned int seq;
u64 ret;
//Reader
do {
seq = read_seqcount_begin(&jiffies_seq);
ret = jiffies_64; //临界区域
} while (read_seqcount_retry(&jiffies_seq, seq));
return ret;
}
[linux-5.10/kernel/time/tick-common.c]
static void tick_periodic(int cpu)
{
if (tick_do_timer_cpu == cpu) {
raw_spin_lock(&jiffies_lock); //写者之间互斥的访问
//Writer
write_seqcount_begin(&jiffies_seq);
do_timer(1); //核心操作 jiffies_64 += 1
write_seqcount_end(&jiffies_seq);
raw_spin_unlock(&jiffies_lock);
update_wall_time();
}
...
}
实现原理
seqcout的核心逻辑十分简洁，但如果追踪linux-5.10代码，会发现各种宏定义包裹，原因可能是方便调试。
但为了直观了解其实现原理，后续接口分析直接给出代码核心逻辑。
写者
void write_seqcount_begin(seqcount_t *s)
{
s->sequence++;
smp_wmb();
}
void write_seqcount_end(seqcount_t *s)
{
smp_wmb();
s->sequence++;
}
写者的 lock 和 unlock 的核心操作都是更新 s->sequence
由于起始点是0，是偶数，故当sequence为奇数时，表示写者还在持有锁
读者
unsigned read_seqcount_begin(seqcount_t *s)
{
unsigned seq;
while ((seq = s->sequence) & 1) //为奇数时，表示写者持有锁，
cpu_relax();
smp_rmb();
return seq;
}
int read_seqcount_t_retry(const seqcount_t *s, unsigned start)
{
smp_rmb();
return unlikely(READ_ONCE(s->sequence) != start);
}
结合写者来看，读者的实现逻辑非常清晰，不在做过多的藐视
Seqlock
概述
通过前面对 seqcount的学习，基本可以掌握顺序锁的精髓。
为了方便用户使用，内核提供了seqlock, API层面提供写者的互斥。当然本质就是 seqcount 与对应锁的组合
数据结构
seqlock 的本质是 seqcount 与对应锁的组合
[linux-5.10/include/linux/seqlock.h]
typedef struct {
seqcount_spinlock_t seqcount;
spinlock_t lock;
} seqlock_t;
API
void seqlock_init(seqlock_t *seqlock);
#define DEFINE_SEQLOCK(sl) seqlock_t sl = __SEQLOCK_UNLOCKED(sl);
unsigned read_seqbegin(const seqlock_t *sl);
unsigned read_seqretry(const seqlock_t *sl, unsigned start);
void write_seqlock(seqlock_t *sl);
void write_sequnlock(seqlock_t *sl);
void write_seqlock_bh(seqlock_t *sl);
void write_seqlock_irq(seqlock_t *sl);
... //bh, irq, irq_save的变种
使用范例
seqlock 和 seqcount 使用类似，伪代码如下
DEFINE_SEQLOCK(myseqlock);
void reader(void)
{
do {
unsigned seq = read_seqbegin(&myseqlock);
... //临界区
} while (read_seqretry(&myseqlock, seq));
}
void writer(void)
{
write_seqlock(myseqlock);
... //临界区
write_sequnlock(myseqlock);
}
原理
从原理可以看到，seqlock也是对seqcount的包装，不在赘述
//写者
static inline void write_seqlock(seqlock_t *sl)
{
spin_lock(&sl->lock);
write_seqcount_t_begin(&sl->seqcount.seqcount);
}
static inline void write_sequnlock(seqlock_t *sl)
{
write_seqcount_t_end(&sl->seqcount.seqcount);
spin_unlock(&sl->lock);
}
//读者
static inline unsigned read_seqbegin(const seqlock_t *sl)
{
unsigned ret = read_seqcount_begin(&sl->seqcount);
kcsan_atomic_next(0); /* non-raw usage, assume closing read_seqretry() */
kcsan_flat_atomic_begin();
return ret;
}
static inline unsigned read_seqretry(const seqlock_t *sl, unsigned start)
{
kcsan_flat_atomic_end();
return read_seqcount_retry(&sl->seqcount, start);
}
其他
问题
为什么读者需要写者退出后才能读取？换句话说如果写者只在加锁时增加s->sequence会怎样？
假设写者获取了锁，自增sequence，需要更新一个结构体所有成员。读者仅需读取结构体首尾两个成员，第一次读取后发现sequence变化，尝试重新读取。但第二次读取数据只有首部被更新，尾部写者还未更新。因为sequence没有变化，读者认为读取数据成功。这样会造成数据不一致。
