【操作系统百科】seqlock 与 seqcount

xtime / ktime_get() 返回当前时间——这是内核最高频的读路径之一。不能用锁，RCU 也不合适（数据在原地更新）。seqlock 是答案。

一、先看图

sequenceDiagram
    participant W as Writer
    participant R as Reader

    W->>W: write_seqcount_begin<br/>seq++（偶→奇）
    W->>W: 更新数据
    W->>W: write_seqcount_end<br/>seq++（奇→偶）

    R->>R: seq1 = read_seqcount_begin
    R->>R: 读数据（可能不一致）
    R->>R: read_seqcount_retry(seq1)?
    alt seq 变了
        R->>R: 重试
    else seq 没变
        R->>R: 数据有效
    end

二、核心思想

• 写者修改数据前后各递增一次序列号（seq）
• seq 奇数 = 写入进行中
• 读者记录 seq → 读数据 → 检查 seq 是否变化 → 变了则重试

三、seqcount vs seqlock

3.1 seqcount_t

只有序列号，不保护写者之间的互斥：

seqcount_t seq;

// 写者（外部需自己互斥）
write_seqcount_begin(&seq);
data = new_value;
write_seqcount_end(&seq);

// 读者
unsigned s;
do {
    s = read_seqcount_begin(&seq);
    val = data;
} while (read_seqcount_retry(&seq, s));

3.2 seqlock_t

seqcount + spinlock（写者互斥）：

seqlock_t lock;

// 写者
write_seqlock(&lock);
data = new_value;
write_sequnlock(&lock);

// 读者
unsigned s;
do {
    s = read_seqbegin(&lock);
    val = data;
} while (read_seqretry(&lock, s));

四、Timekeeper 用法

// kernel/time/timekeeping.c
struct timekeeper {
    seqcount_raw_spinlock_t seq;
    // 时间数据
};

ktime_get() 路径：

do {
    s = read_seqcount_begin(&tk->seq);
    // 读 timekeeper 数据
} while (read_seqcount_retry(&tk->seq, s));

时间更新（tick 中断）只有一个写者 → seqcount 足够。

五、与 RCU 对比

seqlock 适合：小的、可以原地更新的数据（如时间戳、统计计数器）。

六、load tearing 风险

读者可能读到写者写了一半的数据：

// 64 位数据在 32 位架构上
// 读者可能看到 high 32 bit = new, low 32 bit = old

解决：用 READ_ONCE 读每个字段，或保证数据对齐 + 自然宽度。

七、seqcount latch

struct latch_tree {
    seqcount_latch_t seq;
    struct rb_root tree[2];  // 两棵树交替
};

写者更新一棵树 → 切换 seq → 更新另一棵树。读者根据 seq 选择哪棵。

用途：频繁更新的查找结构（如模块地址查找）。

八、typed seqcount（5.10+）

seqcount_spinlock_t     // 关联 spinlock
seqcount_raw_spinlock_t // 关联 raw_spinlock
seqcount_rwlock_t       // 关联 rwlock
seqcount_mutex_t        // 关联 mutex

lockdep 可以跟踪 seqcount 与其保护锁的关系。

九、观察

# seqlock 竞争
bpftrace -e 'kprobe:read_seqcount_begin { @[kstack(3)] = count(); }'
# timekeeper 读重试率
perf stat -e 'sched:sched_stat_runtime' -a sleep 1

十、小结

• seqlock 适合小数据、写少读多、原地更新
• 写者递增序列号，读者重试
• timekeeper 是最经典用例
• 与 RCU 互补：RCU 适合指针/链表，seqlock 适合固定大小数据

参考文献

• include/linux/seqlock.h
• kernel/time/timekeeping.c
• Documentation/locking/seqlock.rst
• include/linux/seqlock_types.h（typed seqcount）

工具

• lockdep（typed seqcount）
• bpftrace

上一篇：RCU 下一篇：percpu_refcount