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沒有變化，讀者認為讀取數據成功。這樣會造成數據不一致。
