本文内容主要是对“Memory Barriers: a Hardware View for Software Hackers” 这篇论文的总结。

背景

在 Linux 内核和 SPDK 代码中经常见到 memory barrier 的使用，线上也遇到过因未正确使用 memory barrier 导致的故障，自己在尝试理解 memory barrier 过程中也走了些弯路，写此文用以记录。

memory barrier 并不解决同步互斥问题，而是解决 “order” 问题，即在一个 CPU 上对不同数据的先后改动，在另一个 CPU 上观察到的结果中，两个数据的先后变动顺序不能改变。通常只有高性能编程才会涉及，比如内核和 SPDK，普通编程场景使用的“锁”也能解决 order 问题，但和 memory barrier比起来性能开销太大。

编译器优化、CPU 乱序机制也会导致 order 问题，但本文讨论范围并不包括这两个因素，仅讨论 cache 原生带来的 order 问题。当然 memory barrier 解决的 order 问题既包括 cache 原生带来的，也包括编译器和 CPU 乱序带来的。

细节

一、cache 及问题由来

CPU 速度远高于 memory，为了提升效率引入了 Cache。

加入 cache 后的变化

二、缓存一致性协议

本来在没有 Cache 的情况下可以依靠内存总线确保数据在不同 CPU 上的一致性，但引入 Cache 后则出现了数据一致性问题：即同一时刻不同 CPU 看到的数据可能不一致。为解决这个问题引入了cache-coherence protocol，即给每个 cache 数据增加状态信息，CPU 之间通过发消息来驱动状态变更，某个读写请求只有在Cache 处于特定状态下才能执行。

以一个 4 状态的一致性协议举例。MESI state：分别代表 Modified，Exclusive，Shared，Invalid 四种状态。当 CPU0 需要读某个数据时，如果数据在 cache 中且是Shared 状态，则可以直接读取 cache 中的数据；如果是 Invalid 状态，则需要发送一个 read 消息到其他 CPU，假设 CPU1 占有该数据，且处于 Modified 状态，说明数据有修改，需要先刷回主存，再将状态转为 shared，并回一个 ACK 消息，最终相关的 CPU 都进入 shared 状态，CPU0 可以确认读取到的数据为最新数据。

三、优化

1. store buffer

一致性协议虽然解决了一致性问题，但显然通过消息传递机制仍会有性能损失。比如 CPU0 要对变量 a 赋值，需要先将 CPU1 的 cache invalidate，在 CPU1 返回 ACK 前只能等待。

一致性协议中的阻塞

为解决等待带来的性能问题，在 CPU 和 Cache 之间又加了一层 buffer，在对端回应前可以先写入 buffer，而不是阻塞等待。

引入 store buffer

// 加入 store buffer 后，对 a 的赋值直接写入 store buffer，不再阻塞后续对 b 的操作
a = 1;
b = 1;

2. write barrier

但随之而来的问题是数据的顺序依赖问题。比如这段代码：

// 初始 a==0, b==0，a 在 CPU1 cache 中，b 在 CPU0 cache 中
// cpu0 执行
void func1() {
  a = 1;
  b = 1;
}
// cpu1 执行
void func2() {
  while(b==0) continue;
  assert(a==1);
}

CPU0 会先向 CPU1 发送 Invalidate 请求CPU1 放弃 a 的 cache，但在收到 ACK 前可以先将改动写入自己的 buffer，然后继续修改 b 并写入 cache（因为独占 b，所以不用写到 buffer）。CPU1 得到 b 的新值后，开始通过一致性协议读取 a，此时 a 在 CPU0 的 cache 中，值为 0，因此 CPU1 得到的值也为 0。
造成这个问题的原因是数据间有依赖，且因 store buffer 的引入，后写的数据已经在 cache 中，但先写的数据还没刷到 cache。解决这个问题有两种办法：

当 buffer 非空时，所有后续写入均写入 buffer。这样就能避免其他 CPU 通过 cache 先获得后修改的数据。
在执行赋值前将 buffer 刷回 cache。这样虽然也要等待，但只有连续写入才会有等待，而其他场景则仍有store buffer 的优化效果。

系统层面则提供了 smp_wmb() 调用，效果就是下刷当前 store buffer。修改后的正确代码如下：

void func1() {
  a = 1;
  smp_wmb();
  b = 1;
}
// cpu1 执行
void func2() {
  while(b==0) continue;
  assert(a==1);
}

3. read barrier

现在重新考虑下引入 store buffer 的初衷：等待 invalidate 返回时间太长。既然这样，也可以从加快 invalidate 返回入手。

引入 invalidate queue

为加快对 invalidate 消息的处理，引入了 Invalidate queue，作用就是当 cpu 收到 invalidate 消息后，先放到队列，立刻返回一个 ACK，CPU 后续再逐个处理队列中的消息。

但这个改动对下面的代码将带来错误：

void func1() {
  a = 1;
  smp_wmb();
  b = 1;
}
// cpu1 执行
void func2() {
  while(b==0) continue;
  assert(a==1);
}

原因是由于 invalidate queue 的引入，CPU1 对 a 的 invalidate 可能滞后于对 b 的加载，如果执行 assert 时仍未完成对 a 的 invalidate，则会认为命中 cache，而此时 CPU1 中关于a 的 cache 是旧值。
解决办法便是引入 read barrier，系统接口为smp_rmb()，正确代码如下：

void func1() {
  a = 1;
  smp_wmb();
  b = 1;
}
// cpu1 执行
void func2() {
  while(b==0) continue;
  smp_rmb();
  assert(a==1);
}

read barrier 起作用的方式便是强制等待处理完 invalidate queue。

4. 其他

上述的smp_wmb()和smp_rmb()还有一个合并版本：smp_mb()，即同时保证 read order 和 write order。除了这个最常见的接口，每个系统还有其他版本的优化，具体可以参考内核文档，此处不展开。

总结

关于 memory barrier 的产生以及整个过程解决的问题描述如下：

memory barrier 的产生过程

参考资料

LKMM : 内核代码中的文档，非常贴心地按照难易程度进行了划分。当然读起来也会比较吃力。
Memory Barriers: a Hardware View for Software Hackers。强烈推荐的一篇论文，难度比内核文档低，看完后再去看内核文档阻力会小很多。

关于 memory barrier 的一些记录