内存屏障的来历

前置内容：缓存一致性协议的工作方式

在「前置内容」中，我们了解到「最原始」的 cpu 是如何在缓存一致性协议 MESI 的指导下工作的，同时我们也发现此时 cpu 的性能因为同步请求远程（其他 cpu）数据而大打折扣。本文章将介绍 cpu 的优化过程，你将了解到硬件层面的优化——Store Buffer, Invalid Queue，以及软件层面的优化——cpu 内存屏障指令。

最原始的架构

性能优化之旅——Store Buffer

当 cpu 需要的数据在其他 cpu 的 cache 内时，需要请求，并且等待响应，这显然是一个同步行为，优化的方案也很明显，采用异步。思路大概是在 cpu 和 cache 之间加一个 store buffer，cpu 可以先将数据写到 store buffer，同时给其他 cpu 发送消息，然后继续做其它事情，等到收到其它 cpu 发过来的响应消息，再将数据从 store buffer 移到 cache line。

增加store buffer

该方案听起来不错！但逻辑上有漏洞，需要细化，我们来看几个漏洞。比如有如下代码:

a = 1;b = a + 1;assert(b == 2);

初始状态下，假设 a，b 值都为 0，并且 a 存在 cpu1 的 cache line 中(Shared 状态)，可能出现如下操作序列:

代码执行时序图，表明cache line的变化

1. cpu0 要写入 a，将 a=1 写入 store buffer，并发出 Read Invalidate 消息，继续其他指令。

2. cpu1 收到 Read Invalidate，返回 Read Response(包含 a=0 的 cache line)和 Invalidate ACK，cpu0 收到 Read Response，更新 cache line(a=0)。

3. cpu0 开始执行 b=a+1，此时 cache line 中还没有加载 b，于是发出 Read Invalidate 消息，从内存加载 b=0，同时 cache line 中已有 a=0，于是得到 b=1，状态为 Modified 状态。

4. cpu0 得到 b=1，断言失败。

5. cpu0 将 store buffer 中的 a=1 推送到 cache line，然而为时已晚。

造成这个问题的根源在于对同一个 cpu 存在对 a 的两份拷贝，一份在 cache，一份在 store buffer，而 cpu 计算 b=a+1 时，a 和 b 的值都来自 cache。仿佛代码的执行顺序变成了这个样子：

b = a + 1;a = 1;assert(b == 2);

这个问题需要优化。

思考题：以上操作序列只是其中一种可能，具体响应（也就是操作 2）什么时候到来是不确定的，那么假如响应在 cpu0 计算“b=a+1”之后到来会发生什么？

性能优化之旅——Store Forwarding

store buffer 可能导致破坏程序顺序的问题，硬件工程师在 store buffer 的基础上，又实现了”store forwarding”技术: cpu 可以直接从 store buffer 中加载数据，即支持将 cpu 存入 store buffer 的数据传递(forwarding)给后续的加载操作，而不经由 cache。

虽然现在解决了同一个 cpu 读写数据的问题，但还是有漏洞，来看看并发程序:

void foo() {    a = 1;    b = 1;}void bar() {    while (b == 0) continue;    assert(a == 1)}

初始状态下，假设 a，b 值都为 0，a 存在于 cpu1 的 cache 中，b 存在于 cpu0 的 cache 中，均为 Exclusive 状态，cpu0 执行 foo 函数，cpu1 执行 bar 函数，上面代码的预期断言为真。那么来看下执行序列:

1. cpu1 执行 while(b == 0)，由于 cpu1 的 Cache 中没有 b，发出 Read b 消息

2. cpu0 执行 a=1，由于 cpu0 的 cache 中没有 a，因此它将 a(当前值 1)写入到 store buffer 并发出 Read Invalidate a 消息

3. cpu0 执行 b=1，由于 b 已经存在在 cache 中，且为 Exclusive 状态，因此可直接执行写入

4. cpu0 收到 Read b 消息，将 cache 中的 b(当前值 1)返回给 cpu1，将 b 写回到内存，并将 cache Line 状态改为 Shared

5. cpu1 收到包含 b 的 cache line，结束 while (b == 0)循环

6. cpu1 执行 assert(a == 1)，由于此时 cpu1 cache line 中的 a 仍然为 0 并且有效(Exclusive)，断言失败

7. cpu1 收到 Read Invalidate a 消息，返回包含 a 的 cache line，并将本地包含 a 的 cache line 置为 Invalid，然而已经为时已晚。

8. cpu0 收到 cpu1 传过来的 cache line，然后将 store buffer 中的 a(当前值 1)刷新到 cache line

出现这个问题的原因在于 cpu 不知道 a, b 之间的数据依赖，cpu0 对 a 的写入需要和其他 cpu 通信，因此有延迟，而对 b 的写入直接修改本地 cache 就行，因此 b 比 a 先在 cache 中生效，导致 cpu1 读到 b=1 时，a 还存在于 store buffer 中。从代码的角度来看，foo 函数似乎变成了这个样子：

void foo() {    b = 1;    a = 1;}

foo 函数的代码，即使是 store forwarding 也阻止不了它被 cpu“重排”，虽然这并没有影响 foo 函数的正确性，但会影响到所有依赖 foo 函数赋值顺序的线程。看来还要继续优化！

性能优化之旅——写屏障指令

到目前为止，我们发现了”指令重排“的其中一个本质，cpu 为了优化指令的执行效率，引入了 store buffer（forwarding），而又因此导致了指令执行顺序的变化。要保证这种顺序一致性，靠硬件是优化不了了，需要在软件层面支持，没错，cpu 提供了写屏障（write memory barrier）指令，Linux 操作系统将写屏障指令封装成了 smp_wmb()函数，cpu 执行 smp_mb()的思路是，会先把当前 store buffer 中的数据刷到 cache 之后，再执行屏障后的“写入操作”，该思路有两种实现方式: 一是简单地刷 store buffer，但如果此时远程 cache line 没有返回，则需要等待，二是将当前 store buffer 中的条目打标，然后将屏障后的“写入操作”也写到 store buffer 中，cpu 继续干其他的事，当被打标的条目全部刷到 cache line，之后再刷后面的条目（具体实现非本文目标），以第二种实现逻辑为例，我们看看以下代码执行过程：

void foo() {    a = 1;    smp_wmb()    b = 1;}void bar() {    while (b == 0) continue;    assert(a == 1)}

1. cpu1 执行 while(b == 0)，由于 cpu1 的 cache 中没有 b，发出 Read b 消息。

2. cpu0 执行 a=1，由于 cpu0 的 cache 中没有 a，因此它将 a(当前值 1)写入到 store buffer 并发出 Read Invalidate a 消息。

3. cpu0 看到 smp_wmb()内存屏障，它会标记当前 store buffer 中的所有条目(即 a=1 被标记)。

4. cpu0 执行 b=1，尽管 b 已经存在在 cache 中(Exclusive)，但是由于 store buffer 中还存在被标记的条目，因此 b 不能直接写入，只能先写入 store buffer 中。

5. cpu0 收到 Read b 消息，将 cache 中的 b(当前值 0)返回给 cpu1，将 b 写回到内存，并将 cache line 状态改为 Shared。

6. cpu1 收到包含 b 的 cache line，继续 while (b == 0)循环。

7. cpu1 收到 Read Invalidate a 消息，返回包含 a 的 cache line，并将本地的 cache line 置为 Invalid。

8. cpu0 收到 cpu1 传过来的包含 a 的 cache line，然后将 store buffer 中的 a(当前值 1)刷新到 cache line，并且将 cache line 状态置为 Modified。

9. 由于 cpu0 的 store buffer 中被标记的条目已经全部刷新到 cache，此时 cpu0 可以尝试将 store buffer 中的 b=1 刷新到 cache，但是由于包含 B 的 cache line 已经不是 Exclusive 而是 Shared，因此需要先发 Invalidate b 消息。

10. cpu1 收到 Invalidate b 消息，将包含 b 的 cache line 置为 Invalid，返回 Invalidate ACK。

11. cpu1 继续执行 while(b == 0)，此时 b 已经不在 cache 中，因此发出 Read 消息。

12. cpu0 收到 Invalidate ACK，将 store buffer 中的 b=1 写入 Cache。

13. cpu0 收到 Read 消息，返回包含 b 新值的 cache line。

14. cpu1 收到包含 b 的 cache line，可以继续执行 while(b == 0)，终止循环，然后执行 assert(a == 1)，此时 a 不在其 cache 中，因此发出 Read 消息。

15. cpu0 收到 Read 消息，返回包含 a 新值的 cache line。

16. cpu1 收到包含 a 的 cache line，断言为真。

性能优化之旅——Invalid Queue

引入了 store buffer，再辅以 store forwarding，写屏障，看起来好像可以自洽了，然而还有一个问题没有考虑: store buffer 的大小是有限的，所有的写入操作发生 cache missing（数据不再本地）都会使用 store buffer，特别是出现内存屏障时，后续的所有写入操作(不管是否 cache missing)都会挤压在 store buffer 中(直到 store buffer 中屏障前的条目处理完)，因此 store buffer 很容易会满，当 store buffer 满了之后，cpu 还是会卡在等对应的 Invalidate ACK 以处理 store buffer 中的条目。因此还是要回到 Invalidate ACK 中来，Invalidate ACK 耗时的主要原因是 cpu 要先将对应的 cache line 置为 Invalid 后再返回 Invalidate ACK，一个很忙的 cpu 可能会导致其它 cpu 都在等它回 Invalidate ACK。解决思路还是化同步为异步: cpu 不必要处理了 cache line 之后才回 Invalidate ACK，而是可以先将 Invalid 消息放到某个请求队列 Invalid Queue，然后就返回 Invalidate ACK。CPU 可以后续再处理 Invalid Queue 中的消息，大幅度降低 Invalidate ACK 响应时间。此时的 CPU Cache 结构图如下：

加入了 invalid queue 之后，cpu 在处理任何 cache line 的 MSEI 状态前，都必须先看 invalid queue 中是否有该 cache line 的 Invalid 消息没有处理。另外，它也再一次破坏了内存的一致性。请看代码：

void foo() {    a = 1;    smp_wmb()    b = 1;}void bar() {    while (b == 0) continue;    assert(a == 1)}

仍然假设 a, b 的初始值为 0，a 在 cpu0，cpu1 中均为 Shared 状态，b 在 cpu0 独占(Exclusive 状态)，cpu0 执行 foo，cpu1 执行 bar:

1. cpu0 执行 a=1，由于其有包含 a 的 cache line，将 a 写入 store buffer，并发出 Invalidate a 消息。

2. cpu1 执行 while(b == 0)，它没有 b 的 cache，发出 Read b 消息。

3. cpu1 收到 cpu0 的 Invalidate a 消息，将其放入 Invalidate Queue，返回 Invalidate ACK。

4. cpu0 收到 Invalidate ACK，将 store buffer 中的 a=1 刷新到 cache line，标记为 Modified。

5. cpu0 看到 smp_wmb()内存屏障，但是由于其 store buffer 为空，因此它可以直接跳过该语句。

6. cpu0 执行 b=1，由于其 cache 独占 b，因此直接执行写入，cache line 标记为 Modified。

7. cpu0 收到 cpu1 发的 Read b 消息，将包含 b 的 cache line 写回内存并返回该 cache line，本地的 cache line 标记为 Shared。

8. cpu1 收到包含 b(当前值 1)的 cache line，结束 while 循环。

9. cpu1 执行 assert(a == 1)，由于其本地有包含 a 旧值的 cache line，读到 a 初始值 0，断言失败。

10. cpu1 这时才处理 Invalid Queue 中的消息，将包含 a 旧值的 cache line 置为 Invalid。

问题在于第 9 步中 cpu1 在读取 a 的 cache line 时，没有先处理 Invalid Queue 中该 cache line 的 Invalid 操作，怎么办？其实 cpu 还提供了读屏障指令，Linux 将其封装成 smp_rmb()函数，将该函数插入到 bar 函数中，就像这样：

void foo() {    a = 1;    smp_wmb()    b = 1;}void bar() {    while (b == 0) continue;    smp_rmb()    assert(a == 1)}

和 smp_wmb()类似，cpu 执行 smp_rmb()的时，会先把当前 invalidate queue 中的数据处理掉之后，再执行屏障后的“读取操作”，具体操作序列不再赘述。

内存屏障

到目前为止，我们已经接触到了「读屏障」和「写屏障」，本节我们就专门聊聊内存屏障。首先内存屏障有几个不同的种类，比如「读屏障」、「写屏障」、「全屏障」等等，各个 cpu 厂商可以自行选择支持哪些语义以及如何支持，所以不同的 cpu 支持的语义不同，对应的指令也不同，我们来看看下图：

横轴表示 8 个内存屏障语义，纵轴表示不同的 cpu，此图表示不同 cpu 对内存屏障语义的支持情况。事实上作为应用开发的程序员没必要再继续深入了，Linux 操作系统面向 cpu 抽象出了自己的一套内存屏障函数，它们分别是：

• smp_rmb(): 在 invalid queue 的数据被刷完之后再执行屏障后的读操作。

• smp_wmb(): 在 store buffer 的数据被刷完之后再执行屏障后的写操作。

• smp_mb(): 同时具有读屏障和写屏障功能。

• smp_read_barrier_depends() that forces subsequent operations that depend on prior operations to be ordered. This primitive is a no-op on all platforms except Alpha.

• mmiowb() that forces ordering on MMIO writes that are guarded by global spinlocks. This primitive is a no-op on all platforms on which the memory barriers in spinlocks already enforce MMIO ordering. The platforms with a nonno-op mmiowb() definition include some (but not all) IA64, FRV, MIPS, and SH systems. This primitive is relatively new, so relatively few drivers take advantage of it.

后面两个不想翻译了，等用到了再了解。

总结

本文通过 cpu 的优化过程，最终引出内存屏障的概念，可以看出，内存屏障是硬件之上，操作系统之下对一致性的最后一层保障。另外，我在看原论文中对执行序列的描述感觉头很大，所以想出用时序图的方式去表示代码执行过程中各 cache line 的状态变化，希望对你的理解有所帮助。

Memory Barriers: a Hardware View for Software Hackers

题图：乔戈里峰