理解Memory Order

经典计算机指令的先后顺序往往也意味着逻辑关系，我们总是会直觉性的认为程序指令是从上到下一个个执行的。虽然这种直觉在很多场景下是没有问题的，但真相不止于此。如果你对memory order这个概念还不是太了解，下面这个test应该会带来一点“惊喜” ^_^

// 代码段1
// store-buffering校验
P0(int x0, int x1)
{
    int r2;
    WRITE_ONCE(x0, 2); r2 = READ_ONCE(x1); 
}

P1(int x0, int x1)
{
    int r2;
    WRITE_ONCE(x1, 2); r2 = READ_ONCE(x0); 
 }

exists (1:r2=0 / 0:r2=0)

这个test的形象使用场景是——两个线程各自持有一个buffer，业务逻辑是写一次自己的buffer后读一下对方的buffer。P0和P1分别代表在两个处理器上跑的逻辑（刚开始x0，x1所指向的内存都是0），两个函数分别跑完之后，存在P0的r2等于0、P1的r2也等于0的可能性（即使在x86这种比较老实巴交的cpu上），即两个线程跑完各自逻辑后，都没有读到对方写入buffer的数据。怎么解释这个现象呢？那就好搬出主角——“memory order”~ 内存顺序这个概念是和计算机体系结构紧紧关联的。在最简单的计算机架构中，memory order其实不需要费心的。但是在更现代的计算机架构中，memory order就成为一个重要概念了。比如上边这个test，其实就与cpu的cache、store buffer有密切关系。

Cache结构

较现代化的CPU都有高速缓存，如下表所示，高速缓存的访问速度要比主存快两个数量级，这是个非常巨大的优势。但是有了缓存，缓存一致性的问题也就产生了。当多个CPU以非共享方式访问（至少一个有写入）同一个位置的内存时，就会遇到一致性的问题。

缓存访问速度对比
而对一般的SMP(symmetric multiple processors)来说，其对应的缓存架构如下图所示：

不同CPU分别有自己独立的cache单元，而不同的cache单元又相互连接在一起，最后再统一连接到内存总线上。cache单元之所以要相互连接到一起，其实是就是为了解决数据一致性的问题。倘若不同的cache单元各自单独连接到主存，则非常容易出现各个cache单元中对同一内存地址的数据不一致、而且最终一致性都不能保证。

MESI缓存一致性协议

为了解决MP系统的缓存一致性问题，缓存一致性协议就应运而生了，比如MESI协议。MESI存在”modified”,”exclusive”,”shared”和”invalid”四种状态，协议可以在一个指定的缓存中应用这四种状态。因此，协议在每一个缓存行中维护一个两位的状态”tag”，这个”tag”附着在缓存行的物理地址或者数据后。我之前有写过一篇相对详细的文章，为了文章整体的完整性和结构，这会简单的提一点重要概念。
- 处于“ modified” 状态的缓存行是由于相应的 CPU 最近进行了内存存储。并且相应的内存确保没有在其他 CPU 的缓存中出现。
- “exclusive”状态非常类似于“ modified” 状态，唯一的例外是缓存行还没有被相应的 CPU 修改，这表示缓存行中的数据及内存中的数据都是最新的。
- 处于“ shared” 状态的缓存行可能被复制到至少一个其他 CPU 缓存中，这样在没有得到其他 CPU 的许可时，不能向缓存行存储数据。
- 处于“ invalid” 状态的行是空的，换句话说，它没有保存任何有效数据。

MESI协议的核心部分就是MESI消息以及状态转移图。其中MESI消息就是cache单元以及内存控制器之间的通信协议，而MESI状态机则是缓存状态的记录方式。MESI消息有如下种类：
- Read：当CPU在自己的cache中没有发现需要的物理地址，就会发送一条“READ”消息，该消息包括缓存行需要读的物理地址。
- Read Response: 顾名思义，”Read Response”消息是回复“Read”消息的。“Read Response”消息是由内存或者其他CPU缓存提供的。如果其他缓存请求一个处于“modified”状态的数据，则本地缓存必须提供“Read Response”消息。这个很容易理解，别的CPU在请求本地缓存中的数据，而这份数据还没有刷新到内存，所以必须告诉其他CPU该数据的最新值。接收到”Read Response”消息后，该数据的缓存状态就由”invalid”变成了”share”或者”exclusive”，这取决于”Read Response”的提供者是内存还是其他CPU缓存。
- Invalidate：“ invalidate” 消息包含要使无效的缓存行的物理地址。其他的缓存必须从它们的缓存中移除相应的数据并且响应此消息。当CPU要对一个变量进行写操作，而此变量处于只读状态(share)，就需要发送“invalid”消息。由于一个变量被多个CPU缓存，所以单个CPU的改写会造成缓存不一致，所以在写之前必须告诉其他CPU你们缓存的值马上就要过时了。接收到”invalidate”消息的CPU就会把本地缓存中的对应数据无效掉。
- Invalidate Acknowledge：一个接收到“invalidate”消息的 CPU必须在移除指定数据后响应一个“invalidate acknowledge”消息。这个消息就是告诉“invalidate”消息的提供者“我已经知道你要更改这个数据了，我放弃使用自己缓存中的拷贝！”
- Read Invalidate：”read invalidate”消息包含要缓存行读取的物理地址。同时指示其他缓存移除数据。因此，它包含一个”read”和一个”invalidate”。“read invalidate”也需要“read response”以及”invalidate acknowledge”消息集。“Read Invalidate”消息的发送时机有两个：第一个是CPU对一个数据进行原子读写操作，但是该数据没有在本地CPU的缓存中，在其他CPU缓存中可能有该数据的拷贝。所以它需要发送一条“Read Invalidate”消息，它不仅需要读取该数据的最新值，还要无效掉其他的CPU缓存(它马上就要改写该数据)。
- Writeback：“writeback”消息包含要回写到内存的地址和数据。这个消息允许缓存在必要时换出“modified”状态的数据以腾出空间。消息的发送时机是，CPU把本地缓存中的数据刷新到内存中，而该数据是share状态(只读)，它需要告诉其他CPU”我不再使用这些缓存数据了”

MESI的状态机转移图如下所示，其中方块形的定点就是四种缓存状态、a~l这些边则是对应状态转移（一般是读写操作或者收到MESI消息触发的）。详细讲解需要的篇幅比较多，这里就不赘述了。

MESI协议状态转移图

Store Buffer结构

导致缓存一致性的根本原因还是写入操作，所以各种硬件优化都会紧紧围绕写入操作的流程。按照MESI协议，一次典型的写入可以展示为以下形式，箭头是时间轴： 开始的时候，同一个缓存行被两个CPU共享。然后CPU 0发射了一个写入指令，该指令会改动共享的缓存行，所以CPU 0（包括其cache结构）会给CPU 1发送一个Invalidate消息，CPU 1接收到这个Invalidate消息之后就会把相应的内存缓存行无效掉，然后给CPU 1回复一条Invalidate Ack消息。CPU 0收到Invalidate Ack之后就把自己的缓存行置为“Modified”。 虽然上面这段流程发生在很小的SMP上，但其实和网络程序是非常类似的。假设CPU就这样一个一个的执行指令，那它的模式就非常类似于BIO（Blocked IO）。一般来说BIO的吞吐量是比较差的，通常都会使用Non-blocked IO或者AIO提高吞吐量。对于SMP来说，也是可以采用类似的优化方案——把写入的后续操作放到一个队列中来异步形式的完成，这样就少了一段等待的时间。这样的硬件结构如下图所示：

带Store Buffer的SMP结构
值得注意的一点是这个图也体现了store forward的结构（为了实现store buffer和cache之间的一致性），这里不赘述。 store buffer引起的校验失败 现在再回头看开头提到的store buffer校验例子，就会发现不难理解了。step 2的写入操作其实只是放到了store buffer里面，step 4才真正开始执行写入操作，CPU 0和CPU 1之间相互invalidate对方的缓存数据，然后最终完成了写入操作。然而step 3的读操作由于有缓存的原因，非常快速的就完成了。从结果上来看，相当于store~load的操作顺序被调整为了load~store。事实上，几乎所有的现代CPU都会做这种优化。

Store Buffer与Memory Barrier

与上文中的代码片段类似，下面这个用例在主流的SMP（有store buffer结构）上基本都有可能失败。

// 代码段2
int a = 0, b = 0;
void foo(void) {
     a = 1;
     b = 1;
}

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

我们把可能的失败执行过程分析如下: 代码段2可能的失败流程 比较明显的看出来，就是这个store buffer在捣鬼，导致a、b写入的先后顺序变得不可靠了。为了解决这个问题，内存屏障（memory barrier就应运而生了）。memory barrier是一种特殊的指令。为了便于理解，我们先讨论作用于store buffer的内存屏障。这种内存屏障的指令的效果就是强制CPU在执行后续写入指令之前，把store buffer中现有的写入都执行完毕。 使用内存屏障改进上面的代码，可以得到如下的形式：

// 代码段3
 int a = 0, b = 0;
 void foo(void) {
     a = 1;
     smp_mb();
     b = 1;
 }

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

则执行的流程会变成下面这样： 代码段3的流程

Invalidate Queue结构

前面仅仅从写入方的角度分析了吞吐量的提升方案，其实还有另外一个角度——读取方。考虑一次CPU的写入操作，执行时可能会向其他CPU发送invalidate消息。如果短时间内有多个CPU执行写入操作（针对不同的缓冲行），则某一个CPU会在短时间内收到非常多的invalidate消息。如果是同步处理的话，有的CPU就会被阻塞了。为了优化这个点，一个新的硬件结构被提出来了，这就是Invalidate Queue。CPU 0给CPU 1发送invalidate消息的时候，只需要把消息投递到CPU 1的Invalidate Queue这个队列就好。此时的SMP结构如下：
带Invalidate Queue的SMP结构
如果说前面的store buffer结构已经引入了一些理解上的“麻烦”，那Invalidate Queue也不是省油的灯。上边的那段针对Store Buffer的改进版代码，它真的就很安全了吗？NO！很不幸，这个断言在有Invalidate Queue的CPU上还是有可能失败。 其实原因和Store Buffer引起的问题非常类似，依然是异步的问题。Invalidate消息会被放到Invalidate Queue里面，导致一些cache内容没有及时的无效掉。而在这个中间时间内，CPU就可能读到旧的值，继而导致“乱序现象”。 原因类似导致解决方法也非常类似，就是增加读取的memory barrier指令。这种“读”内存屏障的指令的效果就是强制CPU在执行后续读取指令之前，把Invalidate Queue中现有的invalidate任务都处理完毕。 其实非常容易理解，把Invalidate Queue里面的Invalidate消息处理完毕之后，cache里面的内容就是很新的版本了，此时再去读取就能保证“内存顺序”了。则代码会成为下面这样：

// 代码段4
int a = 0, b = 0;
void foo(void) {
     a = 1;
     smp_mb(); // 可以优化为只作用于store buffer
     b = 1;
}

void bar(void) {
     while (b == 0) continue;
     smp_mb(); // 可以优化为只作用于invalidate queue
     assert(a == 1)
}

Memory Fence(barrier)与程序设计

虽然各家CPU都提供了内存屏障的汇编指令，但是如今大家都用高级语言做程序设计，并且希望同样的代码可以兼容不同的硬件平台。所以如今的native语言也引入了memory order的概念，而memory order在高性能程序设计、无锁编程场景中就显得比较重要的了。

// 代码段5 没考虑load-store重排序
typedef enum memory_order {
    memory_order_relaxed, // 等于啥都不干
    memory_order_consume, // 根据数据依赖关系插入内存屏障，实验性
    memory_order_acquire, // 利用读取内存屏障，作用于上文中的invalidate queue
    memory_order_release, // 利用写入内存屏障，作用于上问中的store buffer
    memory_order_acq_rel, // 按需使用读取、写入内存屏障，如compare_and_swap
    memory_order_seq_cst  // 同时使用读取、写入内存屏障，比较高成本
} memory_order;

上面这段代码是C++ 20中memory order的定义，注释里简单介绍了一下各个枚举类型。memory order有一个好伙伴，经常和它一起出现，这就是原子变量（atomic variable）。下面举一个例子：

// 代码段6
#include <thread>;
#include <atomic>;
#include <cassert>;
#include <string>;

std::atomic<std::string*> ptr;
int data;

void producer(){
     std::string* p  = new std::string(“Hello");
     data = 42;
     ptr.store(p, std::memory_order_release);
}

void consumer(){
      std::string* p2;
      while (!(p2 = ptr.load(std::memory_order_acquire)))
            ;
      assert(*p2 == "Hello"); // never fires
      assert(data == 42); // never fires
}
int main(){
      std::thread t1(producer);
      std::thread t2(consumer);
      t1.join(); t2.join();
}

这段代码相当于实现了一个消息传递的逻辑，ptr是保护消息是否准备好的flag，data是消息的具体内容。当消费者读到消息已经ready的时候，就会去消费消息。我们需要保证此时消费者读到的消息数据一定是最新的，这就借助了memory order的API。代码段6 其实就是 代码段4 的更优化、更标准版本(如果我们不去讨论更复杂的情况)。

本文主要是以Store Buffer和Invalidate Queue结构为依据，分析了memory order的设计。个人感觉从硬件设计的角度才能更好的理解memory order这一概念。 虽然大量依据了《Is Parallel Programming Hard, And, If So, What Can You Do About It?》，但是本文其实是有不少缺陷的。缺陷主要体现在没有考虑load-store之间的reorder。这种reorder在x86、powerPC上虽然不存在，但是在其他更乱序的硬件上是存在的。所以本文中的不少表述是不准确的，但个人认为读者可以关注于思路。 这种load-store乱序对应的硬件结构是Load Buffer或者Reorder Buffer。为什么这种乱序是有意义的呢？可以考虑一个场景，load指令没有命中cache、但之后的store指令发射时store buffer刚好满了，则load会耗时比较久，如果load可以异步等待，则可以达到更高的指令吞吐量。但由于个人水平有限，对Load Buffer或者Reorder Buffer的理解还很浅，这里就先不细写了。

参考资料：

1. 《Is Parallel Programming Hard, And, If So, What Can You Do About It?》

2. https://iis-people.ee.ethz.ch/~gmichi/asocd/addinfo/Out-of-Order_execution.pdf

3. https://www.modernescpp.com/index.php/fences-as-memory-barriers

4. https://en.cppreference.com/w/cpp/atomic/memory_order

5. https://llvm.org/docs/Atomics.html