1. 问题描述

在并发系统中，一个长时间运行的操作基于某个时刻的快照做决策，但在操作执行期间，底层数据已被另一个并发路径修改。操作完成时，其结果已基于过时状态（stale state），导致错误行为。

核心矛盾

• 操作 A：读取状态 S₀ → 长时间执行 → 基于 S₀ 写入结果
• 操作 B：在 A 执行期间修改状态 S₀ → S₁
• 结果：A 的写入基于已失效的 S₀，产生不一致

传统锁无法解决：A 不能长期持锁（阻塞 B，可能引发死锁或性能问题），也不能不持锁（数据过时）。

为什么 CAS/Seqlock 不够

• CAS：只能保护单个原子值的更新，无法覆盖"读取多个字段 → 长操作 → 写回"的场景
• Seqlock：读侧必须能无副作用地重试，但长操作可能已经产生了硬件副作用（如 DMA、PTE 更新）
• RCU：保护的是读侧生命周期，不解决"读取后决策是否仍然有效"的问题

---

2. 设计模式

┌─────────────────────────────────────────────────┐
│           Shared Mutable State                  │
│                                                 │
│   data: T                                       │
│   epoch: atomic<u64>  ← 每次修改时递增            │
│                                                 │
└─────────────────────────────────────────────────┘

Writer (短操作):              Reader/Actor (长操作):
                              
  lock(state)                   snapshot_epoch = state.epoch
  state.data = new_value        snapshot_data = read(state.data)
  unlock(state)                 unlock / release
  state.epoch++                 
                                ... long operation based on snapshot ...
                                (可能涉及 DMA、硬件操作等)
                              
                                lock(state)
                                if (state.epoch != snapshot_epoch) {
                                    // STALE - discard result
                                    unlock(state)
                                    retry or abort
                                }
                                apply_result(state)
                                unlock(state)

关键要素

要素	作用
Epoch counter	轻量级版本号，标记状态变更次数
Snapshot	长操作开始前捕获当前 epoch 值
Validation	长操作结束后，比较当前 epoch 与 snapshot
Resolution	检测到过时后的策略：丢弃、重试、跳过、或部分应用

适用条件

1. 修改者是短操作：epoch++ 可以在锁内/原子地完成
2. 执行者是长操作：不能全程持有锁
3. 结果可丢弃或重试：检测到 stale 后，能安全放弃本次结果
4. 正确性优先：宁可丢弃一次有效结果（false positive），也不能应用一次 stale 结果

---

3. 模式变体

3.1 Per-Object Epoch

每个独立对象维护自己的 epoch，减少 false positive（不相关修改不会误触发）：

struct managed_object {
    void *data;
    atomic_t epoch;
};

// 长操作只检查自己关心的对象
if (obj->epoch != my_snapshot_epoch)
    skip this object only;

3.2 Epoch Window（批量操作）

长操作覆盖多个对象，每个对象独立校验：

for each object in batch:
    if (object.epoch == snapshot_epoch)
        apply(object);   // still valid
    else
        skip(object);    // stale, let next iteration handle

优点：不需要因为一个对象 stale 而丢弃整个批次的工作。

3.3 Epoch + Generation（两级检测）

区分"小修改"和"结构性变更"：

struct state {
    atomic_t generation;  // 结构性变更（如对象被删除/替换）
    atomic_t epoch;       // 数据变更（如属性修改）
};

if (generation != my_generation)
    abort entirely;      // structure changed, cannot proceed
else if (epoch != my_epoch)
    partial retry;       // data changed but object still exists

3.4 Epoch + Fence（硬件同步）

长操作涉及硬件异步执行，需要结合 fence 等待：

snapshot_epoch = state.epoch;
submit_hw_operation();          // async
wait_for_hw_completion();       // fence

if (state.epoch != snapshot_epoch) {
    // HW operation completed but state is stale
    // undo or don't commit the HW result
    rollback();
}

---

4. 与其他并发模式的对比

模式	检测时机	副作用处理	适用操作时长	典型场景
悲观锁	预防（持锁期间不允许修改）	无需处理	短	简单临界区
乐观锁 (CAS)	写入时检测	重试	短	单值更新
Seqlock	读完成后检测	读侧重试（无副作用）	短读	统计计数器
RCU	延迟释放	读侧无需检测	短读	只读遍历
Epoch Staleness	commit 前检测	丢弃/回滚有副作用的结果	长	硬件操作、DMA

Epoch Staleness 的独特价值：长操作可能有不可逆的外部副作用（如硬件已经执行了 DMA），不能简单重试整个操作。检测到 stale 后，选择不 commit 结果（而非 undo 硬件操作）。

---

5. 实际驱动用例

5.1 Linux i915 GPU Driver — Request Resubmission

场景：Intel i915 驱动中，GPU context 被 reset 后需要重新提交 request。但 reset 期间，用户空间可能已经关闭了 context 或修改了 GEM object 绑定。

模式应用：

• i915_gem_context 维护一个 guilty 和 closed 标志
• Engine reset 是长操作（等待 GPU idle，保存/恢复状态）
• Reset 完成后，检查 context 是否已被 close，如果已 close 则不重新提交

// 类似逻辑 in i915_request.c
// guilty_count 作为一种 epoch - 表示 context 状态已变
if (ctx->guilty_count != saved_guilty_count)
    skip resubmission;

参考：drivers/gpu/drm/i915/gt/intel_reset.c

---

5.2 Linux NVMe Driver — Queue Pair Reconnection

场景：NVMe-oF (NVMe over Fabrics) 在网络断开后进行重连。重连期间，上层可能已经 abort 了部分 I/O 或整个 controller 被 shutdown。

模式应用：

• Controller 维护 ctrl->state 和 generation counter
• 重连是长操作（TCP 握手、认证、queue 建立）
• 重连完成后检查 controller state 是否仍然是 RECONNECTING

// drivers/nvme/host/tcp.c 中的逻辑
static void nvme_tcp_reconnect_ctrl_work(struct work_struct *work) {
    // 长操作：建立连接
    ret = nvme_tcp_setup_ctrl(ctrl, false);
    
    // 验证：如果 ctrl 已经被 shutdown，放弃重连结果
    if (ctrl->state != NVME_CTRL_CONNECTING) {
        // stale - someone changed state while we reconnected
        nvme_tcp_teardown_io_queues(ctrl, false);
        return;
    }
    // commit: 将 state 转为 LIVE
    nvme_start_ctrl(ctrl);
}

---

5.3 Linux Network Driver (mlx5) — Flow Table Update

场景：Mellanox mlx5 驱动中，flow steering rules 的硬件更新是异步的。在更新期间，用户空间可能通过 tc/flower 删除或修改了 rule。

模式应用：

• Flow table entry 维护修改计数
• 硬件 flow table 更新通过 firmware command（~ms 级别延迟）
• Command 完成回调中验证 rule 是否仍然有效

// 概念性代码 (mlx5_core flow steering)
struct mlx5_flow_rule {
    struct mlx5_flow_destination dest;
    atomic_t modify_count;  // epoch
};

// 提交硬件修改前
saved_count = atomic_read(&rule->modify_count);
mlx5_cmd_exec_async(dev, modify_flow_cmd, callback);

// 回调中
void modify_flow_callback(int status, void *ctx) {
    if (atomic_read(&rule->modify_count) != saved_count) {
        // Rule was modified/deleted while HW command in flight
        // Don't update SW state to match this stale HW state
        return;
    }
    // Commit: update SW tracking to reflect HW state
    rule->hw_state = ACTIVE;
}

---

5.4 Linux Block Layer — Plug/Unplug with Queue Freeze

场景：Block layer 在 queue freeze 期间批量修改 queue 参数。blk_mq_freeze_queue 是一个长操作（等待所有 in-flight I/O 完成）。

模式应用：

• Queue 维护 q->mq_freeze_depth 和 quiesce 状态
• Freeze 期间，其他路径可能调用 blk_cleanup_queue
• Freeze 完成后需要验证 queue 是否仍然有效

// 概念性（实际实现通过 refcount + state machine）
blk_mq_freeze_queue(q);        // 长操作：等待 in-flight I/O

if (blk_queue_dying(q)) {      // 验证：queue 是否已被删除
    blk_mq_unfreeze_queue(q);
    return -ENODEV;            // stale, abort
}

// commit: 修改 queue 参数
q->nr_hw_queues = new_count;
blk_mq_unfreeze_queue(q);

---

5.5 Linux DRM/KMS — Atomic Modeset

场景：DRM atomic modeset 是一个经典的 epoch/version 检测场景。Userspace 提交 atomic commit 时，内核需要验证硬件状态没有在 check 和 commit 之间被另一个 commit 修改。

模式应用：

• drm_crtc 维护 state->commit 序列
• Atomic check（长操作：验证所有 plane/crtc/connector 约束）
• Check 通过后，commit 前验证没有并发 commit 修改了同一 CRTC

// drivers/gpu/drm/drm_atomic_helper.c
// 每个 CRTC state 有 sequence number
// nonblocking commit 场景:
//   1. atomic_check (验证配置可行)
//   2. 等待前一个 commit 完成 (fence)
//   3. 提交到硬件
//   4. 如果前一个 commit 还在运行中，新 commit 必须等待或失败

---

5.6 Linux Filesystem — inode Writeback

场景：Writeback 是一个长操作（flush dirty pages 到磁盘）。期间 inode 可能被 truncate 或 unlink，导致 writeback 的数据已无意义。

模式应用：

• inode->i_version 或 i_generation 作为 epoch
• Writeback 开始时记录 page dirty 状态
• Writeback 完成后验证 inode 没有被 truncate

// 概念性 (ext4/xfs writeback 类似逻辑)
saved_size = i_size_read(inode);
// ... 长时间 writeback pages ...

if (i_size_read(inode) < saved_size) {
    // inode was truncated during writeback
    // pages beyond new size are irrelevant
    // don't update writeback accounting for those pages
}

---

5.7 RDMA/InfiniBand — Memory Region Invalidation

场景：RDMA MR (Memory Region) 注册到硬件后，用户空间可能在远端 RDMA 操作进行中 deregister MR。

模式应用：

• MR 维护 lkey generation
• 远端 RDMA read/write 是长操作
• 完成后验证 MR 是否仍然有效

// 概念性 (mlx5 RDMA)
struct mlx5_mr {
    u32 key;          // includes generation bits (epoch in the key itself)
    atomic_t live;
};

// Remote access completion
void handle_rdma_completion(struct mlx5_mr *mr, u32 used_key) {
    if (mr->key != used_key || !atomic_read(&mr->live)) {
        // MR was invalidated/re-keyed during RDMA op
        // report remote access error
        post_error_completion();
        return;
    }
}

---

6. 设计指南

何时使用此模式

• ✅ 操作耗时不可预测（涉及 I/O、硬件、网络）
• ✅ 操作期间不能持锁（会阻塞关键路径）
• ✅ 操作的结果可以安全丢弃（后续会有重试机会）
• ✅ 修改频率远低于长操作执行频率（否则 false positive 太多）

何时不要使用

• ❌ 操作很短（直接用锁更简单）
• ❌ 操作结果不可丢弃（必须成功，需要其他同步策略）
• ❌ 修改极其频繁（epoch 总是变化，长操作永远无法 commit）

实现注意事项

1. Epoch 递增的原子性：确保 epoch++ 与数据修改在同一个临界区，或使用 memory barrier 保证可见性顺序
2. False positive 容忍度：epoch 是全局的还是 per-object 的取决于对 false positive 的容忍度
3. ABA 问题：64-bit epoch 实际上不会 wrap around，但 32-bit 需要考虑
4. Stale 后的恢复路径：必须明确定义检测到 stale 后做什么（retry? skip? error?）
5. 与硬件副作用的关系：如果硬件已经执行了操作（如 DMA 完成），stale 检测后不能 undo 硬件，只能选择不在软件层面 commit 结果

---

7. 总结

Epoch-Based Staleness Detection 是一种乐观并发控制的变体，专为长操作 + 外部副作用场景设计。它的核心思想是：

允许长操作在无锁环境下执行，但在 commit 阶段通过轻量级版本比较来检测数据是否已过时，从而决定是否应用结果。

这种模式在 OS 内核驱动中广泛存在（虽然实现形式各异），因为驱动代码天然面临：

• 硬件操作延迟不确定
• 不能长期持有 mutex（会阻塞中断/调度）
• 并发路径多（用户空间 ioctl、中断、workqueue、timer）
• 硬件副作用不可逆

理解这个模式后，在分析驱动 race condition 时，可以系统地问：

1. 这个长操作基于什么状态做决策？
2. 哪些并发路径可能修改这个状态？
3. 操作完成后，有没有验证状态是否仍然有效？
4. 如果没有验证 → 潜在 bug，需要加 epoch 检测