# Invalidate Queue（失效队列）—— 为什么"作废别人的行"也不能等

> 这是 [store-buffer.md](/concepts/memory-ordering/store-buffer.md) 的对称篇。Store buffer 优化的是一致性握手的**发起方**（写方不必干等 `Inv-Ack`）；invalidate queue 优化的是**接收方**——收到 `invalidate` 的核，不必等"真把行置无效"做完就先回 Ack。两者一头一尾，共同让 [msi.md](/concepts/cache/msi.md) 场景3 那次"失效-确认握手"完全不阻塞流水线。


> 本篇详细论述：invalidate queue **解决什么问题**、**怎么设计**、**引入了什么新乱序**、**怎么用读屏障补救**，以及它和 store buffer **为什么必须成对理解**。前置：[store-buffer.md](/concepts/memory-ordering/store-buffer.md)、[msi.md](/concepts/cache/msi.md) 的握手、[mesi.md](/concepts/cache/mesi.md) 的状态机。

## 一、问题起点：接收侧也慢，会把写方重新拖住

先回到 [msi.md](/concepts/cache/msi.md) 场景3 的握手：核A 要写共享行 X，发 `invalidate(X)` 给持有者核B，**必须收齐核B 的 `Inv-Ack` 才能升 M 动笔**。

Store buffer 已经让核A 不必**同步**等这个 Ack（写先入队、后台等）。但问题转移到了核B 这一侧：

- 核B 收到 `invalidate(X)`，要真去自己的 L1 里找到 X 那条行、把状态置 **I(Invalid)**。
- 这一步**不是免费的**：L1 可能正忙（在处理本核自己的 load/store）、要查组、要改状态位。若核B **等这些全做完才回 Ack**，那核A 的 store buffer 就得等更久才凑齐 Ack、才能提交——**写方又被接收方拖慢了。**

```plantuml
@startuml
skinparam shadowing false
skinparam sequence {
  ParticipantBackgroundColor #E3F2FD
  ParticipantBorderColor     #1976D2
  ArrowColor                 #C62828
  LifeLineBorderColor        #90A4AE
}
participant "核A\nStore Buffer" as SBA
participant "核B" as B
participant "核B L1\n(正忙)" as L1B
SBA -> B : invalidate(X)
B -> L1B : 去把 X 置 I
note over L1B : L1 正忙于本核访存\n失效操作排队等着…😩
L1B --> B : (良久) 置 I 完成
B --> SBA : 现在才回 Inv-Ack
note over SBA : 核A 的写迟迟提交不了\n——接收侧成了新瓶颈
@enduml
```

> **矛盾**：一致性要求"失效必须发生"，但"失效真正发生"要占用接收核繁忙的 L1。若让写方等这个，store buffer 省下的时间又赔了进去。invalidate queue 就是为接收侧解耦而生。

## 二、核心思路：失效请求先入队、立刻回 Ack，稍后再生效

Invalidate queue 是**挂在核的一致性接收端、L1 之前的一个小队列**。设计同样一句话：**把收到的 `invalidate` 记下来就回 Ack，别让"真去改 L1"挡在握手的关键路径上。**

```plantuml
@startuml
skinparam shadowing false
skinparam componentStyle rectangle
skinparam rectangle {
  BackgroundColor<<net>> #E3F2FD
  BorderColor<<net>>     #1976D2
  BackgroundColor<<q>>   #FFCCBC
  BorderColor<<q>>       #E64A19
  BackgroundColor<<l1>>  #C8E6C9
  BorderColor<<l1>>      #388E3C
}
rectangle "互联\n(来自写方的 invalidate)" <<net>> as NET
rectangle "Invalidate Queue\n(积压待处理的失效: X, Z, ...)" <<q>> as IQ
rectangle "本核 L1" <<l1>> as L1
NET -down-> IQ : ① 收到 invalidate(X)\n**入队即刻回 Inv-Ack**
IQ -down-> L1 : ② 稍后(L1 有空时)\n才真把 X 置 I
note right of IQ
  Ack 抢先回 → 写方能尽快凑齐、提交
  代价：X 在本核**实际还没失效**的
  那段窗口里，本核读 X 仍命中旧值
end note
@enduml
```

两步拆开：

1. **入队即回 Ack**：收到 `invalidate(X)`，把"待失效 X"塞进 invalidate queue 就**立刻回 `Inv-Ack`**。写方(核A)据此尽快凑齐 Ack、提交它的 store。握手的关键路径被缩短。
2. **异步生效**：invalidate queue 里的条目，等本核 L1 空闲时才真去把对应行置 I。这个"补作废"过程和本核前台执行**并行**。

> 本质和 store buffer 一模一样，只是方向相反：store buffer 把**"写的完成"**推后（异步提交进 L1），invalidate queue 把**"失效的完成"**推后（异步置 I）。两者都用"先应答、后干活"换取握手不阻塞。

## 三、代价：本核"答应作废了，却还在读旧值"

这是本篇的核心风险。核B 回了 `Inv-Ack`（对外宣称"X 我作废了"），但 X 还躺在 invalidate queue 里没真置 I——**这段窗口内，核B 自己去读 X，仍会在 L1 命中那条本应失效的旧行。**

```plantuml
@startuml
skinparam shadowing false
skinparam sequence {
  ParticipantBackgroundColor #E3F2FD
  ParticipantBorderColor     #1976D2
  LifeLineBorderColor        #90A4AE
}
participant "核A" as A
participant "核B\nInvalidate Queue" as IQ
participant "核B L1\n(X 仍是旧值)" as L1
participant "核B 流水线" as PB
A -> IQ : invalidate(X)
IQ --> A : Inv-Ack（先答应）
note over A : 以为 B 已作废 X\n继续写新值、往下跑
PB -> L1 : 读 X
note over L1 : X 还没被真正置 I\n→ **命中旧值** ❌
IQ -> L1 : (稍后) 才把 X 置 I（为时已晚）
@enduml
```

后果：核B 违反了它刚"答应"的失效——在它自己看来，别人的写**延迟才可见**。这正好和 store buffer 的后果**对称**：

| | Store Buffer | Invalidate Queue |
|---|---|---|
| 优化谁 | 一致性握手的**发起方**（写方）| 一致性握手的**接收方**（被失效方）|
| 把什么推后 | 写真正提交进 L1、对别人可见 | 失效真正在 L1 生效（置 I）|
| 先做什么 | 写**入队即放行**流水线 | 失效**入队即回 Ack** |
| 引入的乱序 | 本核的写**延迟对别人可见**（→ StoreLoad 重排）| 别人的写**延迟对本核可见**（本核读到旧值）|
| 站在"可见性"看 | 我的新值出得慢 | 别人的新值进得慢 |
| 对应屏障 | 写屏障 / 全屏障：**排空 store buffer** | 读屏障 / 全屏障：**排空 invalidate queue** |

## 四、经典翻车：invalidate queue 让 acquire 侧读到旧值

单看 store buffer，4.2 的两标志位例子只暴露了写方一侧。加入 invalidate queue，另一半问题才完整——**读方即使先读到了"新的标志位"，也可能读到"旧的数据"**。经典的 producer/consumer：

```c
// 生产者(核A)                 // 消费者(核B)
data = 42;                     while (ready == 0) { }  // 等标志
ready = 1;                     r = data;               // 读数据
```

期望：核B 看到 `ready==1` 后，`data` 必然是 42。但 invalidate queue 会破坏它：

```plantuml
@startuml
skinparam shadowing false
skinparam sequence {
  ParticipantBackgroundColor #E3F2FD
  ParticipantBorderColor     #1976D2
  LifeLineBorderColor        #90A4AE
}
participant "核A" as A
participant "核B\nInvalidate Queue" as IQ
participant "核B L1" as L1
participant "核B" as B
note over A : data=42、ready=1 都已写出并可见
A -> IQ : invalidate(data)  （data 变了，作废你的旧副本）
IQ --> A : Inv-Ack（先答应，data 的失效仍积压在队列里）
B -> L1 : 读 ready → 已是 1（这条已生效）
note over B : 通过了 while 循环
B -> L1 : 读 data → **旧副本还没被置 I → 命中旧 data** ❌
IQ -> L1 : (太晚) 才把 data 置 I
@enduml
```

**核B 看到了新的 `ready`，却读到了旧的 `data`**——因为 `invalidate(data)` 还压在核B 的 invalidate queue 里没生效。这就是为什么"只有 store buffer 的屏障"不够，**读方也必须有屏障**。

> 注意分工：让核A 的 `data=42` 先于 `ready=1` 出去，是**写屏障(排空 store buffer)** 的活；让核B 在读 `data` 前先把积压失效生效，是**读屏障(排空 invalidate queue)** 的活。producer/consumer 要正确，**两端各加一个屏障**，缺一不可——这正是 C++ `release`(写方)/`acquire`(读方) 必须**配对**使用的硬件根源。

## 五、补救：读屏障强制排空 invalidate queue

修复手段和 store buffer 对称：在关键读之前插**读屏障**，强制把 invalidate queue 里积压的失效**全部先生效**，再往下读，保证读到的是最新状态。

```plantuml
@startuml
skinparam shadowing false
skinparam sequence {
  ParticipantBackgroundColor #E3F2FD
  ParticipantBorderColor     #1976D2
  ArrowColor                 #C62828
  LifeLineBorderColor        #90A4AE
}
participant "核B" as B
participant "核B\nInvalidate Queue" as IQ
participant "核B L1" as L1
B -> B : 读 ready==1，通过循环
B -> B : **读屏障(acquire)** —— 排空 invalidate queue！
IQ -> L1 : 把积压的 invalidate(data) 立刻全部生效
note over L1 : data 被置 I
B -> L1 : 读 data → L1 miss → 重新取到新值 42 ✅
@enduml
```

对应到指令与 C++：

| 层面 | 手段 | 对 invalidate queue 的作用 |
|------|------|---------------------------|
| C++ | `atomic_load(&ready, memory_order_acquire)` | acquire 语义：在此之后的读之前，排空 invalidate queue |
| C++ | 默认 `seq_cst` | 同时含 acquire，自动带读屏障 |
| x86 | 一般的 load（x86 已是强模型）| **x86 的 acquire 通常"免费"**——见下 |
| ARM | `dmb ld` / `ldar` | 弱模型必须显式读屏障 |

### 为什么 x86 上"感觉不到"invalidate queue？

x86 是强内存模型(**TSO**)，它对读的排序保证很强（不允许 LoadLoad/LoadStore 重排）。硬件上，x86 的实现要么不使用会引起可见乱序的 invalidate queue，要么保证 load 之前相关失效已生效——**所以 x86 程序员几乎感觉不到 invalidate queue 的存在，普通 load 就自带 acquire 效果。**

而 **ARM/Power 是弱模型**：invalidate queue 的乱序对软件可见，`ready` 看到新值不代表 `data` 也新，**必须显式 `ldar`/`dmb` 读屏障**。这就是同一段 producer/consumer 代码"x86 上没加屏障也碰巧对、搬到 ARM 就偶发读到旧值"的根本原因。

> **一句话**：invalidate queue 是弱内存模型里"读方也要加屏障"的硬件根源。x86 强模型把这层屏障隐含在普通 load 里，你写 `acquire` 也几乎零成本；ARM 上它是实打实的一条屏障指令。（x86-TSO/弱模型对四种重排各自允许还是禁止的完整对比,见总纲 [memory-reordering.md](/concepts/memory-ordering/memory-reordering.md) 第三节;本节只讲 invalidate queue 这一侧的表现。）

> 本篇讲的是 invalidate queue 造成的 **LoadLoad/LoadStore** 那两种重排；四种重排的全景表、成因归属与屏障对应见总纲 [memory-reordering.md](/concepts/memory-ordering/memory-reordering.md)。

## 六、全屏障 = 同时管两端

一个完整的 `mfence`（全屏障）实际干**两件事**，正好各治一个队列（[store-buffer.md](/concepts/memory-ordering/store-buffer.md) 讲了发起侧的那一半）：

```plantuml
@startuml
skinparam shadowing false
skinparam rectangle {
  BackgroundColor<<sb>> #FFF9C4
  BorderColor<<sb>>     #F9A825
  BackgroundColor<<iq>> #FFCCBC
  BorderColor<<iq>>     #E64A19
  BackgroundColor<<f>>  #E1BEE7
  BorderColor<<f>>      #6A1B9A
}
rectangle "全屏障 mfence" <<f>> as F
rectangle "排空 Store Buffer\n(让我的写出去、全局可见)" <<sb>> as SB
rectangle "排空 Invalidate Queue\n(让别人的写进来、旧副本作废)" <<iq>> as IQ
F -down-> SB
F -down-> IQ
note bottom of SB : 治 StoreLoad 重排\n(发起方问题)
note bottom of IQ : 治"读到旧值"\n(接收方问题)
@enduml
```

- **`release`**（写方）≈ 只保证"此前的写"先于本次写出去 → 偏向排空 store buffer。
- **`acquire`**（读方）≈ 只保证"此后的读"看到最新 → 偏向排空 invalidate queue。
- **`seq_cst` / `mfence`** = 两端都做，最强也最贵。

acquire/release 之所以比 `seq_cst` 便宜，就是因为它**只做半边**：写方无须理会 invalidate queue，读方无须理会 store buffer。理解这两个队列，才真正理解 `std::memory_order` 各档在硬件上省的是哪一半。

## 七、串起来：两个队列在一次握手里的完整位置

把 store buffer 与 invalidate queue 放进 [msi.md](/concepts/cache/msi.md) 场景3 的同一张握手图——这是两篇文档的会合点：

```plantuml
@startuml
skinparam shadowing false
skinparam sequence {
  ParticipantBackgroundColor #E3F2FD
  ParticipantBorderColor     #1976D2
  LifeLineBorderColor        #90A4AE
}
participant "核A 流水线" as PA
participant "核A\nStore Buffer" as SBA
participant "互联/目录" as DIR
participant "核B\nInvalidate Queue" as IQB
participant "核B L1" as L1B
PA -> SBA : store X（入队即放行，流水线不停）
SBA -> DIR : 后台发 invalidate(X)
DIR -> IQB : invalidate(X)
IQB --> DIR : **入队即回 Inv-Ack**（不等真失效）
DIR --> SBA : 收齐 Ack → 授予独占
SBA -> SBA : 把 X 提交进核A L1（此刻才全局可见）
IQB -> L1B : (稍后) 才把核B 的 X 置 I
note over PA, L1B
  两个队列各让一端不干等：
  · Store Buffer   —— 核A 写完不停摆（发起侧）
  · Invalidate Queue —— 核B 失效不阻塞、Ack 抢先回（接收侧）
  代价合起来：X 的“写入”与“对 B 真正失效”之间，是一段双向乱序窗口
  → 要强一致，就在 A 端加写屏障、B 端加读屏障，两头堵死
end note
@enduml
```

**完整图景**：MESI 保证最终一致（正确性下限）；**store buffer + invalidate queue** 让握手两端都不为一致性干等（性能）；**写屏障 + 读屏障**在需要处成对堵住乱序窗口（按需拔高一致性）。三层分工，缺一不可。

## 八、和本仓库其他文档的关系

- **对称篇**：[store-buffer.md](/concepts/memory-ordering/store-buffer.md)——发起侧优化、StoreLoad 重排、x86-TSO；本篇是它的接收侧镜像，建议对照读。
- **上游**：[msi.md](/concepts/cache/msi.md)（握手与 `Inv-Ack` 的来源）、[mesi.md](/concepts/cache/mesi.md)（M/E/S/I 状态机）。
- **下游**：[atomic.md](/concepts/cache/atomic.md)（`std::memory_order` 的 acquire/release/seq_cst——acquire 的硬件含义就是本篇的"排空 invalidate queue"）。
- **性能观测**：invalidate queue 相关的可见性乱序，在弱模型上表现为"偶发读到旧值"的难复现 bug；在 x86 上更多体现为屏障(`mfence`)带来的停顿。

```bash
# 内存序相关的流水线清空/屏障开销（事件名因型号而异，先 perf list 查）
perf stat -e cycles,instructions,machine_clears.memory_ordering ./app
perf list | grep -i "machine_clears\|mem_\|fence"
```

## 九、一句话总结

> **失效"真正生效"要占用接收核繁忙的 L1，若让写方等它就白费了 store buffer。于是接收侧用 invalidate queue "先回 Ack、后置 I"——代价是本核答应作废却还在读旧值，即别人的写延迟才对本核可见。这和 store buffer 完全对称，需要读屏障(acquire)排空队列来补救。写方的写屏障 + 读方的读屏障成对使用，才堵住两端的乱序窗口——这正是 release/acquire 必须配对、以及 x86 强模型下读屏障"隐含免费"的根源。**