Update Note:

• 18.07.15 initial version
• 18.07.26 修订，改了些明显的错误.

内联汇编 x 内存模型与内存屏障

program ordering vs. memory ordering

指令序和内存序的定义见[1].

单核 vs 多核

单核环境下，硬件保证program ordering.所以单核环境下唯一可能更改指令顺序的就是编译器了.（前提是操作的内存地址是对齐的.若非对齐的，1个非对齐操作会变成2次对齐操作。）
多核环境下，不提供program ordering的保证，但提供了一些指令用于显式地告诉CPU保序，迫使cpu清空cacheline、锁定总线等.
这样牺牲一定的一致性换取性能的提升. 下面会深入讨论下为什么多核环境不提供这种保证了。

上述观点来自[a]，[b], Ref:
[a] https://blog.codingnow.com/2007/12/fence_in_multi_core.html
[b] ‘In a single-core environment (assuming no interaction with DMA data) the only
re-ordering you need to be concerned with is that of the compiler.’
https://stackoverflow.com/questions/19965076/gcc-memory-barrier-sync-synchronize-vs-asm-volatile-memory

复习多Cache一致性

这里需要先复习一下体系结构里《多Cache一致性》这一章。这里的Cache我认为是特指L1Cache，因为L1Cache是每个核独占的。而L2或L3Cache则可能是被多个核所共享(Bank？Die？)。

Snooping（监听法）、Directory（目录法）。这个Cache Coherency本文里可以认为是透明的。

多核环境为什么没有一致性保障了？ —— write buffer

这个write buffer并不是我们经常提的CPU的L*(L1/L2/L3...)Cache. 可以看下面截自[c]的一个图.
Cache写回时并不是立即写入内存，而是把这个写操作扔进Write Buffer.

WB不是Cache.png

简单的CPU结构如上图

wiki上有一段话：In multi-core systems, write buffers destroy sequential consistency.

原因，单核中，被WB缓存住的写地址（此时还未写回主存），同时遇到指令读该地址的时候，会产生所谓的by-pass read，即把这个还没写回主存的内容返回。从而WB的存在是透明的。通过WB的批量处理Store，提升了性能。

多核的x86设计，每个核都有各自的WB（且是FIFO的）[1]，Cache同上所述，是另一套系统，在本文里可以认为是透明的, 有一些协议保证coherency，如MESI.

由于WB是每个核独占的[1], 操作共享内存的多线程程序，by-pass read可能失败. 在一个核的WB中的某地址的最新内容，另一个核无法获悉(invisible)。例子可以见[1]的4.1节。正是因为x86的这种设计，才有了内存屏障的这么多事情。

The option chosen by SPARC and later x86 was to abandon SC in favor of a memory consis-
model that allowed straightforward use of a first-in-first-out (FIFO) write buffer at each core.

另外再扯一句，屏障（mfence）的作用，是告诉核，清空WB并停止流水线直到Store内存的操作都完成；另外，单独的某个加lock前缀的指令也有同样的作用，并且它有个额外的副作用是锁住CPU->内存的总线，让其他CPU的Store操作停顿直到本CPU的写内存操作完成，粒度较大，在核比较多的机器可能造成较大的性能损失（与*fence指令相比）。

关于Write Buffer:
[c] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.7073&rep=rep1&type=pdf
[d] https://en.wikipedia.org/wiki/Write_buffer

内联汇编中实现内存屏障

指令重排软硬.png

如这个图所示，指令乱序的原因有2个编译器、硬件；针对这2者，分别有Compiler Barrier(优化屏障)和Memory Barrier（内存屏障）.

优化屏障不等于内存屏障！！！
优化屏障不等于内存屏障！！！
优化屏障不等于内存屏障！！！

优化屏障只作用于编译器不进行乱序优化；
内存屏障作用于CPU，是硬件层面的事情。

那问题如下：优化屏障有个卵用？ 答：在单核环境下，只需要优化屏障，不需要内存屏障(单核架构的CPU估计大多也不支持各种×fence指令)！
原因是，如最上面所述，单核环境，CPU都会保证program ordering，从而决定了从结果上看程序指令序必然不会被改变. 实际上单核环境如果用内存对齐的变量+单个赋值指令，可以保证SC的.

• 优化屏障(Compiler Barrier)

inline void memory_barrier_x86() {
  asm volatile(
    ""
    :
    :
    : "memory"
  );
}

• 优化屏障与内存屏障(Memory Barrier) ，从kernel里抠出来的。

#define barrier() __asm__ __volatile__("": : :"memory")
#define mb() barrier()
#define rmb() mb()
#define wmb() mb()

/*
 * Force strict CPU ordering.
 * And yes, this is required on UP too when we're talking
 * to devices.
 */
#ifdef CONFIG_X86_32
/*
 * Some non-Intel clones support out of order store. wmb() ceases to be a
 * nop for these.
 */
#define mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)
#define rmb() alternative("lock; addl $0,0(%%esp)", "lfence", X86_FEATURE_XMM2)
#define wmb() alternative("lock; addl $0,0(%%esp)", "sfence", X86_FEATURE_XMM)
#else
#define mb()    asm volatile("mfence":::"memory")
#define rmb()   asm volatile("lfence":::"memory")
#define wmb()   asm volatile("sfence" ::: "memory")
#endif

解释下，下面2者起的作用类似，前者效率低些.

• asm volatile("lock; addl $0,0(%%esp)":::"memory")

lock前缀的作用是锁总线，同时加上随便一条无意义的指令 + "momery"，可以达到内存屏障的作用:

1. "lock; addl $0,0(%%esp)"的作用:
   lock前缀让本核操作内存时锁定其他核，addl xxx是个无意义的内存操作，可令CPU清空WB，也起到了内存屏障的作用了。

lock prefix guarantee that result of instruction is immediately globaly visible.

2. "memory" 这个把memory放入破坏列表，我认为是一个编译器的概念，告诉编译器这个asm块“不可预料”地修改了内存, 需要后面的相关联的共享变量都从内存地址读。

• asm volatile("mfence":::"memory")

lfence:停止相关流水线，直到lfence之前对内存进行的读取操作指令全部完成.
sfence:停止相关流水线，直到lfence之前对内存进行的写入操作指令全部完成.
mfence:停止相关流水线，直到lfence之前对内存进行的读写操作指令全部完成.

Intel的CPU貌似可以根据*fence指令做一些优化，提前清空流水线之类的，让代价变小.

内存屏障主要解决的是什么问题

动机和实例请参考[1]的3.1章节. 这里提取出一些关键点.

简单地讲，内存屏障是实现内存模型的一种方式，而内存模型的提出是为了解决规范化内存一致性问题。注意，内存一致性问题(Memory Consistency)与缓存一致性问题(Cache Coherence)不同，不要混淆这2个概念.

• 内存一致性问题和缓存一致性问题的区分

缓存一致性问题主要是多核系统中的核特定缓存之间可能存在的不一致问题，解决方式有目录协议/监听协议等。这些都是硬件完成的，对软件透明。

内存一致性问题的核心问题是[多核]CPU访问(Load/Store)内存地址(同个/不同地址)的顺序问题。这些东西大多数情况是透明的，但如果用lock-free编程则不。

• 内存模型

访存的顺序问题其实涉及到2个层面，软件和硬件. 软件层面主要涉及编译器和工具链，包括编译阶段的指令优化和重排等，而硬件层面则可能涉及指令流水线、读写缓冲(是FIFO的还是非FIFO的)、DMA等. 内存访问的顺序从C代码到内存单元至少经过2-3次重新编排.

硬件层面的重排可能有4种类型:LL，SS, LS or SL(S for Store, L for Load),每个硬件平台允许的重排情况还不太相同.

内存一致性模型(我的理解)就是提出一系列范式来规定共享内存的访问顺序性。尤其是在多核+lock-free下这个规范就十分重要了.

SC内存模型

• SC内存模型(Sequential Consistent顺序一致内存模型)是内存模型中[最强的一致性保证].单核环境默认是SC的. 规定多线程交织后的指令满足其在单核上的执行顺序.术语上称作memory order respecting program order. 更精确的描述如下(参见[1]的第25页)

• SC内存模型要求满足:(翻译自[1])

 - 对于不同的内存地址，内存访问顺序满足程序的指令顺序. 
 - 对于同一个地址的访问，读操作读到的内容一定是最新的写操作的结果. //bypass-read  

[1]的3.11关于sc的扩展阅读

• x86平台由于是TSO内存模型，不提供SC保证，因此内存屏障就是人为地在TSO体系上构建SC保证的程序了.参见附录1 - 内存屏障的作用实例

• c++11提供的原子操作，默认为SC顺序一致性.std::memory_order_seq_cst

• 关于c++11的原子操作，leveldb里有段注释：

  5 // AtomicPointer provides storage for a lock-free pointer.
  6 // Platform-dependent implementation of AtomicPointer:
  7 // - If the platform provides a cheap barrier, we use it with raw pointers
  8 // - If <atomic> is present (on newer versions of gcc, it is), we use
  9 //   a <atomic>-based AtomicPointer.  However we prefer the memory
  10 //   barrier based version, because at least on a gcc 4.4 32-bit build
  11 //   on linux, we have encountered a buggy <atomic> implementation.
  12 //   Also, some <atomic> implementations are much slower than a memory-barrier
  13 //   based implementation (~16ns for <atomic> based acquire-load vs. ~1ns for
  14 //   a barrier based acquire-load).
  15 // This code is based on atomicops-internals-* in Google's perftools:
  16 // http://code.google.com/p/google-perftools/source/browse/#svn%2Ftrunk%2Fsrc%2Fbase
  

  划重点
  ~16ns for <atomic> based acquire-load vs. ~1ns for a barrier based acquire-load

TSO(Total Store Order)即x86的内存模型

• 使用TSO内存模型的架构： x86, SPARC
• TSO内存模型要求满足：
  1. LL，LS，SS 类型的操作一定是保序的。//通过FIFO的WB实现SS保序
  2. SL类型的操作可能实际执行时S在L之后。//
  3. 对于同一个地址的SL型操作，同一个核上会产生bypassing-load，可以保证拿到最新的数据。

  4. TSO引入了FENCE指令，可以手动保序。
     为什么允许SL类型的乱序其实在上面已经有解释了，以x86多核为例，它使用了每个核独占的FIFO-Write-Buffer. 这样Store操作（写）实际上可能被延后, 但Store与Store之间是保序的，因为WB是FIFO的。

     
     
     符合TSO但不符合SC的执行例子.png

其他更为松弛的内存模型如 PSO，RMO等

这里就不展开了,这方面再深入就是学海无涯了。
但需要注意的是[1]的5.5.1, Release Consistency提出了acquire/release语义。一种更细粒度的内存序控制机制。

内存布局和内存模型区别

内存布局是个静态的概念，内存模型主要是针对动态的程序行为；
内存布局关键点如pod和非pod，继承、虚函数对内存布局的影响等.
内存模型指的就是内存一致性模型，主要是访存的顺序性问题，也就是上面讨论的一大堆东西 [4].

Acquire/Release语义

TBD.

内存模型概览(from [5] & [3])

内存模型概览

HLL内存模型与c++的内存模型

HLL-high-level-language
主要的意思由于编译器的存在，高级语言本身也存在内存模型。即HLL-Memory-Model.

c++内存模型是什么？官方的说法是SC-for-DRF（DRF， data-race-free），啥意思呢? 就是如果你用了atomic，就提供sc保障，如果不用，就不提供sc保障。

The C++ memory model guarantees sequential consistency if you use atomic operations with the appropriate memory orderings to guarantee sequential consistency. If you just use plain non-atomic operations, or relaxed atomics, and no mutexes, then sequential consistency is not guaranteed.

Compilers are free to re-order operations if the difference in behaviour cannot be observed, that's the as-if rule. So for example, if re-ordering sequentially consistent atomics would produce a different observable result then it doesn't meet the as-if rule. If it would not produce a different observable result, then reordering is allowed.

• Ref
  [x] https://stackoverflow.com/questions/38425920/memory-model-in-c-sequential-consistency-and-atomicity

c++11引入的6种内存序

下[5]对这个深入讲解了很多.
看这6个图就行了，平时能用上的可能性我表示严重怀疑。= =!!!

Relax.png

Release.png

Acquire.png

Acquire_Release.png

Consume.png

SC.png

• Ref:
  [0] 计算机体系结构
  [1] A Primer on Memory Consistency and Cache Coherence
  [2] c++11 Memory Model
  [3] Preshing on Programming的博客
  [4] https://www.cnblogs.com/haippy/p/3412858.html
  [5] https://en.wikipedia.org/wiki/Memory_ordering
  [6] https://stackoverflow.com/questions/1787450/how-do-i-understand-read-memory-barriers-and-volatile

LevelDB的AtomicPointer

TBD.

内存屏障与volatile

• volatile不提供内存屏障语义.
• volatile仅仅是个编译器的标识.(可认为是编译器屏障... or compiler barrier)

内存屏障不是(from 下[2])：

• 内存屏障不会提高性能.
• 内存屏障不会魔法地使多线程同步.
• 内存屏障不会涉及多核间load/store先后顺序的通信. 所以多核架构下，线程之间并不知道各自的L/S的先后顺序.
• 内存屏障不提供无条件的内存序保证.这的条件还是指原子变量需要自己去判断.

个人理解是使用内存屏障顶多让你达到SC顺序一致性，代码要work还是需要程序员做一些判断.

内存屏障进一步区分，还有读内存屏障，写内存屏障.

• further read:
  [0] http://www.cl.cam.ac.uk/~pes20/weakmemory/index.html#x86
  [1] 1个c++内存模型的测试站点 http://svr-pes20-cppmem.cl.cam.ac.uk/cppmem/help.html
  [2] https://lwn.net/Articles/573436/
  [3] https://blog.csdn.net/Adam040606/article/details/50898070
  [4] https://stackoverflow.com/questions/19965076/gcc-memory-barrier-sync-synchronize-vs-asm-volatile-memory
  [5] https://mariadb.org/wp-content/uploads/2017/11/2017-11-Memory-barriers.pdf

Some Tests

附1 内存屏障的使用

使用了自己写的一个小库quark(https://github.com/hi-quasars/quark).做个演示,如果不用内存屏障,同步会有问题.同时volatile也不足够应付.

 1   #include <misc.h>
 2   #include <sys.h>
 3   #include <atomic.h>
 4
 5   #include <iostream>
 6   #include <string.h>
 7   #include <stdio.h>
 8
 9
 10  #include "tests_utils.h"
 11
 12  // Part I. Tests for Memory Barrier.
 13  //
 14  using quark::os::Thread;
 15  using quark::atomic::qk_atomic_t;
 16
 17  qk_atomic_t ready;
 18  const char *bptr;
 19
 20  class Producer : public Thread<Producer>::dthread { // is a non-joinable thread.
 21      public:
 22          Producer(const char* txt) : foo(txt){}
 23          void WorkLoop(Producer *) {
 24              // Work's own bussiness logic goes here.        
 25              while(ready != 0) {
 26              };
 27
 28              bptr = foo;
 29              quark::atomic::memory_barrier();
 30              ready = 1;
 31          }
 32
 33      private:
 34          const char *foo;
 35  };
 36
 37
 38  class Consumer : public Thread<Consumer>::jthread {
 39      public:
 40          Consumer(const char* f) {
 41              fp = fopen(f, "w+");
 42              if (fp == NULL) {
 43                  QuarkFatal(f, errno);
 44                  abort();
 45              }
 46          }
 47          ~Consumer() {
 48              fclose(fp);
 49          }
 50          void WorkLoop(Consumer *) {
 51              while(1) {
 52                  while(ready == 0) {
 53                  };
 54                  
 55                  std::cout << "to flush: " << strlen(bptr) << std::endl;
 56                  
 57                  fwrite(bptr, strlen(bptr), 1, fp);
 58                  std::cout << "flush buffer, wait again" << std::endl;
 59                  
 60                  quark::atomic::memory_barrier();
 61                  ready = 0;
 62                  bptr = nullptr;
 63                  fflush(fp);
 64              }
 65          }
 66      private:
 67          FILE* fp;
 68  };
 69
 70  void Test_For_MB1() {
 71      bptr = "Not this!";
 72      Producer p1("HelloHello,Test For MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM, barrier");
 73      Consumer c1("./output.txt");
 74      
 75      Thread<Producer> *t1 = Thread<Producer>::NewThread(&p1);
 76      Thread<Consumer> *t2 = Thread<Consumer>::NewThread(&c1);
 77      
 78      ready = 0;
 79
 80      t2->Run();
 81      t1->Run();
 82
 83      //
 84      t1->Run();
 85
 86      t2->Join();
 87  }
 88
 89
 90  TESTSMAIN( Test_For_MB1, "test for memory barrier 01 ",
 91      NULL)