本文将基于第一性原理，浅谈x86的TSO memory ordering机制。

本文只讨论 x86-64 上自然对齐的普通 load/store，对普通 WB（Write-Back）cacheable memory 的访问。暂不讨论编译器重排、non-temporal store、string operation、WC/UC memory、MMIO、DMA、CLFLUSH、locked instruction 和 serializing instruction。

本文示例是硬件litmus test，不表示普通非原子C语言访问可以直接这样编写。

What

先把最容易混淆的一点说清楚：
Memory ordering 讨论的不是“CPU 是否按顺序执行指令”，而是多个 CPU 访问多个共享地址时，一个 CPU 的内存操作，可能以什么顺序被其他 CPU 观察到。

四种“顺序”

假设程序写的是：

1
2
3
A
B
C

这里实际上可能存在四种不同的顺序。

程序顺序 Program Order

源代码或机器指令中：

1
2
A 在 B 前面
B 在 C 前面

通常写成：

1
A →po B →po C

这只是”指令流中的顺序”。

CPU 内部执行顺序

现代 CPU 可能：

  • 提前发射 load
  • 推迟 store
  • 猜测执行
  • 并行执行无依赖指令
  • 将 store 暂存在 store buffer
  • 从 store buffer 向本核 load 转发数据

所以 CPU 内部实际开始或完成某条指令的时间，不一定等于程序顺序。

不过，单线程通常看不出区别，因为 CPU 必须维持单线程的架构语义。

内存操作的可见顺序

这是 memory ordering 真正关注的内容。

例如 CPU 0 执行：

1
2
x = 1;
y = 1;

CPU 1 可能看到：

1
2
y == 1
x == 0

这意味着，对 CPU 1 而言：

1
2
3
对 y 的 store
似乎先于
对 x 的 store

即使 CPU 0 的程序顺序正好相反。

注意：这里描述的是一般弱内存模型中可能出现的可见顺序，不是 x86 TSO 下普通 WB load/store 的合法结果。对于 x86，Store→Store 和 Load→Load 均保持顺序，因此 y==1 && x==0 被禁止。

同一地址的 coherence order

假设多个 CPU 依次向同一个地址写：

1
2
3
x = 1
x = 2
x = 3

缓存一致性协议通常要求：

对同一个地址，所有 coherent observer 对这些 store 的先后顺序必须达成一致。

但这只解决了单个地址的问题，并不自动解决不同地址之间的顺序：

1
2
x = 1
y = 1

因此必须牢记：

粗略地说，Cache Coherence 主要解决单个地址的一致性；Memory Ordering 主要解决多个地址之间的可见顺序。

Armv8 同样要求对同一位置的写进行序列化，但它并不为不同位置的普通访问提供类似 x86 TSO 的强顺序。

基础Example

初始状态：

1
2
x = 0
y = 0

程序：

1
2
3
4
CPU 0                       CPU 1

A: W(x)=1                   C: W(y)=1
B: R(y)→r0                  D: R(x)→r1

每个 CPU 的程序顺序是：

1
2
CPU 0：A → B
CPU 1：C → D

寄存器总共有四种组合：

1
2
3
4
r0=0, r1=0
r0=0, r1=1
r0=1, r1=0
r0=1, r1=1

Sequential Consistency

先构造一个最符合人直觉的模型。

Sequential Consistency，简称 SC，可以理解为：

系统仿佛有一个全局开关，每次只允许一个 CPU 完成一个内存操作；所有 CPU 的操作被混合进一个全局总序，同时每个 CPU 自己的程序顺序不能被打乱。

以基础Example为例，不能出现：

1
B A C D

因为它违反了 CPU 0 的程序顺序。

Example的结果

两个线程各有两个操作，保持：

1
2
A 在 B 前
C 在 D 前
全局顺序 执行过程 (r0,r1)
A B C D CPU 0 先写 x，再读到旧 y；随后 CPU 1 写 y、读到新 x (0,1)
A C B D 两个写先发生，两个读都看到 1 (1,1)
A C D B 两个写先发生，两个读都看到 1 (1,1)
C A B D 两个写先发生，两个读都看到 1 (1,1)
C A D B 两个写先发生，两个读都看到 1 (1,1)
C D A B CPU 1 先写 y，再读到旧 x；随后 CPU 0 写 x、读到新 y (1,0)
结果 SC
(0,0) 禁止
(0,1) 允许
(1,0) 允许
(1,1) 允许

store buffer

CPU 0 想执行：

1
x = 1

如果 x 对应的 cache line 当前被其他 CPU 共享，CPU 0 可能需要：

  1. 发出 Read For Ownership；
  2. 通知其他 CPU invalidate 该 cache line；
  3. 等待一致性协议响应；
  4. 获得写权限；
  5. 才能更新 cache line。

如果 CPU 每次 store 都等完整个过程，流水线会频繁停顿。

因此 CPU 通常先把 store 放进一个本地 store buffer：

1
2
3
4
5
6
7
CPU pipeline
     │
     ▼
Store Buffer：x = 1
     │
     ▼
L1 cache / coherence network

Store 可以先被本核接受并进入私有 Store Buffer，CPU 随后继续执行后续指令；但此时该 Store 可能还没有排出 Store Buffer，因此尚未对其他处理器全局可见。

x86 TSO

x86-64 普通 WB 内存的模型通常称为：

1
TSO：Total Store Order

可以用下面这个简化模型理解：

1
2
3
4
5
6
7
8
9
10
每个 CPU：

程序
  │
  ├── Load ───────────────> cache/coherence
  │
  └── Store ──> FIFO Store Buffer ──> cache/coherence
                         ▲
                         │
             本核 load 可以做 store forwarding

一个 store 可以先进入本核 store buffer，而暂时不对其他核可见。后面的 load 如果访问不同地址，可以绕过这个尚未排空的 store。

因此，简化地说，x86 保持：

1
2
3
Load  → Load
Load  → Store
Store → Store

但放松：

1
Store → Load       不同地址时

Intel 手册明确规定：普通读之间不重排，写不能越过更早的读，普通写之间不重排；但读可以越过更早的、访问不同地址的写。

关键性质是：

  1. 本 CPU 的 store 按程序顺序从 store buffer 对外传播；
  2. load 通常按程序顺序被观察；
  3. 但 load 可以绕过更早的、访问不同地址的 buffered store；
  4. 对同一地址，CPU 必须处理 store forwarding 和同地址 coherence order。

Intel 给出的普通 load/store 顺序规则可以总结为：

较老操作 → 较新操作 x86 普通 WB 内存能否表现为重排
Load → Load 否
Load → Store 否
Store → Store 否
Store → Load，不同地址 可以
Store → Load，同一地址 不可以读回旧值

这里的“否”表示架构不允许其他处理器观察到相反顺序。

Example的结果

可以出现如下执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
时间
 │
 ▼

CPU 0                              CPU 1

W(x)=1 进入 Store Buffer           W(y)=1 进入 Store Buffer
    │                                  │
    │ x 尚未对 CPU 1 可见              │ y 尚未对 CPU 0 可见
    │                                  │
R(y) 从 cache/memory 读到 0         R(x) 从 cache/memory 读到 0
    │                                  │
Store Buffer 最后排出 x=1           Store Buffer 最后排出 y=1

注意：

  • CPU 0 自己知道它写了 x=1；
  • 但 CPU 1 暂时还看不到；
  • CPU 0 后面的 load 访问的是另一个地址 y，可以不等 x=1 排出；
  • CPU 1 同理。

所以：

1
2
r0=0
r1=0

在 x86 上是允许的。

store forwarding

初始：

1
x = 0

CPU 0 执行：

1
2
x = 1;
r0 = x;

从程序语义来看，结果必须是：

1
r0 = 1

但是，前面说过，x = 1 可能先进入 Store Buffer：

1
2
3
4
5
6
7
8
9
10
CPU 0

执行 x = 1
     │
     ▼
Store Buffer：
    x = 1

Cache / 内存：
    x = 0

这时，如果后面的：

1
r0 = x;

直接去 Cache 中读取，就会读到：

1
r0 = 0

这显然违反单线程程序语义：

1
2
3
4
x = 1;
r0 = x;

assert(r0 == 1);

因此，CPU 执行 load 时不能只看 Cache，还需要检查：

1
Store Buffer 中有没有更早的、写同一地址的 store？

如果有，就直接使用 Store Buffer 中的新值：

1
2
3
4
5
6
7
                   ┌─────────────────────┐
x = 1 ───────────> │ Store Buffer: x = 1 │
                   └──────────┬──────────┘
                              │
                              │ Store Forwarding
                              ▼
r0 = x  <──────────────────── 1

所以最终：

1
r0 = 1

这个机制就叫：

1
Store-to-Load Forwarding

或者简称：

1
Store Forwarding

Intel 的优化手册将其描述为：当较早的 store 和较新的 load 满足地址、大小等条件时，load 可以直接从 store buffer 获得数据，而不需要等待 store 写入缓存。

为什么叫 Total Store Order

x86 TSO 可以抽象成“每核一个私有 FIFO Store Buffer，加一个共享内存”；Load 可以提前读取本核最新的 buffered Store，而各核 Store 排入共享内存时形成一致的全局 Store 顺序。

1
2
3
4
5
6
7
8
Total：
    Store 最终进入一个一致的全局顺序

Store：
    这里强调的是 Store 的顺序

Order：
    同一核 Store 按程序顺序，跨核 Store 由系统交织

记忆图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SC
│
│ 所有 program-order 边都保留
│
├── Load  → Load
├── Load  → Store
├── Store → Store
└── Store → Load
        都保留


x86 TSO
│
├── Load  → Load       保留
├── Load  → Store      保留
├── Store → Store      保留
└── Store → Load       不同地址时可能放松

参考资料:

  1. Intel 64 and IA-32 Architectures Software Developer’s Manual
  2. Intel Optimization Reference Manual
  3. x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors
  4. 内存一致性模型-TSO
  5. Sequential Consistency in Armv8
  6. Explanation of the Linux-Kernel Memory Consistency Model