理解内存屏障
1 前言
内存屏障是搞软件的需要面对的一个涉及硬件cpu的问题，很多人困惑不解。本文是我们对linux内核内存屏障的理解，参考linux内核（4.0版本）的Documentation/memory-barriers.txt。
2 内容
主要内容如下：
2.1 内存访问的的抽象模型
2.2 什么是内存屏障
2.3 内核中的显式和隐式的内存屏障
2.4 cpu间的锁和屏障的关系
2.5 哪里需要使用屏障
2.6 内核中io屏障的作用
2.7 执行有序的最小假想模型
2.8 cpu cache对屏障的影响
2.9 alpha cpu
2.10 一个环形缓冲区的使用样例
好，让我们开始遐想（本文需要借助想象力，否则。。。）吧！
2.1 内存访问的抽象模型
如下图，多个cpu共同访问一个内存的场景（模型）：
我们的理解是：只要能保证程序逻辑正确执行，cpu和complier（为了提升性能）怎么个乱序（优化）都行！
举例说明，如下：
CPU 1CPU 2
==============================
{ A == 1; B == 2 }
A = 3;x = B;
B = 4;y = A;
cpu1有2条指令，cpu2也有2条指令，共4条指令，总共有24种执行顺序（其实就是4的阶乘），够多了吧！（更可怕的是，这还是建立在一个重要假设之下的：假设cpu上执行顺序和其它cpu感知的是一样的！否则。。。）
就这个例子而言，我们只关注x和y组成的可能结果，不外乎4种（其实就是2*2）：
x == 2, y == 1
x == 2, y == 3
x == 4, y == 1
x == 4, y == 3
再举个例子：
CPU 1CPU 2
==============================
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;Q = P;
P = &BD = *Q;
只关注Q和D组成的结果的话，会出现“Q == 3”的结果么？cpu2这里有数据依赖性（或者说程序逻辑性）：必须先取Q，再取*Q！这样看，cpu2肯定是先执行“Q = P”，所以一定不会出现“Q == 3”的结果了。
再看一个例子：
*A = 5;
x = *D;
A是地址端口寄存器，D是数据端口寄存器。很明显，此时必须先放地址，再读数据，我们肯定认为只能这一种顺序，但是谁也保证不了！
至此，我们停顿下来，做个分析。貌似很乱了，软件根本搞不定，感觉是个硬件问题啊，那就让硬件做些限制（保证）吧！（cpu必须得做一些前提保证，否则软件世界大乱。。。）
前面说了，cpu会按照自己的（优化）顺序去执行指令，但一定不能违反一个大准则：程序本身的逻辑顺序。它会做如下保证：
1）有依赖的，保证保持现有顺序。
比如下面指针使用的例子：
ACCESS_ONCE(Q) = P; smp_read_barrier_depends(); D = ACCESS_ONCE(*Q);
smp_read_barrier_depends()一般为空，也就是说大部分的cpu是（不需要特殊处理）保证这种顺序的：因为得保持程序自身的依赖关系！
2）保证对重叠操作的处理保序
所谓重叠操作就是对同一内存地址的连续处理。
比如：
a = ACCESS_ONCE(*X); ACCESS_ONCE(*X) = b;
对地址X的处理顺序的两条指令就是重叠操作，cpu会保证现有顺序。
3）对毫无关系的指令，cpu保证你猜不出顺序！比如：
X = *A; Y = *B; *D = Z;
这样的指令序列，会有几种可能的顺序？6种（3的阶乘）顺序，哪种都可能！
4）cpu保证对重叠部分可能合并，可能覆盖！
比如：
X = *A; Y = *(A + 4);
此时可能有：
X = LOAD *A; Y = LOAD *(A + 4);
Y = LOAD *(A + 4); X = LOAD *A;
{X, Y} = LOAD {*A, *(A + 4) };
再比如：
X = *A; Y = *(A + 4);
此时可能有：
STORE *A = X; STORE *(A + 4) = Y;
STORE *(A + 4) = Y; STORE *A = X;
STORE {*A, *(A + 4) } = {X, Y};
可见，重叠时，cpu可能会合并（又可能导致覆盖）。
cpu能做出以上保证，算给软件稍微（一点点）减负了。
特别需要注意的是位域结构：一般地，位域操作不是线程安全的！就是说，对同一个结构体内的不同位域成员（即使连续定义的成员）的多线程访问是无法保证线程安全的：
Do not attempt to use bitfields to synchronize parallel algorithms.
我们来仔细分析这个问题，先看跟位域相关的一个memory location定义：
memory location
either an object of scalar type, or a maximal sequence
of adjacent bit-fields all having nonzero width
所谓memory location，指的是一个标量类型对象或一个最大的连续非0长度位域组。特别地，0长度位域会单独霸占一个memory location，从而隔离出memory location！
那memory location到底对线程安全有何影响？对同一memory location的访问（包括更新）不是线程安全的；对不同memory location的访问（包括更新）则是线程安全的。
更具体地讲，对于一个结构体（各个字段的类型，可能是位域，也可能不是）而言，我们总结如下几个要点：
位域类型和非位域类型之间的并发访问（包括更新），是线程安全（两个线程分别访问其中一个类型字段）的。
此结构体内部和该结构体的嵌套子结构体之间的位域字段，是线程安全的。
位域之间如果有0长度位域分割，则是线程安全的。
位域之间如果被一个非位域分割，则是线程安全的。
位域之间所有的位域都是非0位域，则是线程不安全的。
综上，要使访问位域线程安全化，可以采用锁，也可以在两个位域之间插入0长度位域（虽然有点浪费空间）。
好了，我们这次就讲到这里。总之，每个控制主体（compiler、各个cpu、程序逻辑本身）都会有自己所期望的顺序，那如何协调呢？下次开始讲什么是内存屏障。。。（未完待续）
上次我们了解了cpu/compiler乱序的一些现象，我们这次开始正式探讨内存屏障。
2.2 什么是内存屏障
cpu会把无关（对相关性的判断，cpu和程序逻辑可能会有分歧）的内存操作乱序化处理（类似的，还有其它处理：延迟、预读、分支预测、合并、cache等），目的很单纯，就是提升性能。但cpu这种自以为是的单方处理，在多cpu间或者cpu与io设备间的交互操作时会有问题，而内存屏障就是为解决问题而生的。
2.2.1 内存屏障的种类
(1) 写内存屏障
写内存屏障保证：该屏障之前的写操作和之后的写操作相比，先被系统其它组件感知。
可见写内存屏障：与读操作无关；只是保证部分（相对）保序。注意：写屏障一般与读屏障或数据依赖屏障一起使用（详细内容后文会讲）。
(2) 数据依赖屏障
数据依赖屏障是读屏障的弱版本，仅保证（有依赖）部分的读操作有序。
比如，读地址的读操作和读该地址内容的读操作之间就需要数据依赖屏障来保证正确的顺序。说它是读屏障的弱版本，是因为不必（像读屏障那样）保证所有读操作有序，而只需要保证（有依赖的）部分读操作有序。
数据依赖屏障的作用（目的）是让当前cpu能感知到其他cpu的写操作顺序（可能是已乱序后的）对自己读操作的影响。具体说，数据依赖屏障之后的读操作可以感知到该屏障之前的读操作涉及的其它cpu的写操作（即保证最新数据）。
另外，如果依赖不涉及数据，那就是控制依赖（后文会讲）。注意：和读屏障一样，数据依赖屏障一般需要和写屏障一起配合使用。
(3) 读屏障
读屏障内置了数据依赖屏障，同时保证读屏障之前的读操作相比读屏障之后的读操作，会先被系统其它组件感知。
同上，读屏障一般需要和写屏障配对使用。
(4) 通用内存屏障
通用内存屏障保证该屏障之前的读/写操作和之后的读/写操作相比，会先被系统其它组件感知。
通用内存屏障其实就是读屏障和写屏障的合集。
(5) ACQUIRE操作（相当于lock）
ACQUIRE操作（属于单向屏障）保证：该操作后（该操作前的不做任何保证）的操作和该操作相比，会后于被系统其它组件感知。
ACQUIRE operations include LOCK operations and smp_load_acquire()
operations.
一般和RELEASE操作配对使用。
(6) RELEASE操作（相当于unlock）
RELEASE操作（属于单向屏障）保证：该操作前（该操作后的不做任何保证）的操作和该操作相比，会先于被系统其它组件感知。
RELEASE operations include UNLOCK operations and
smp_store_release() operations.
一般用了ACQUIRE/RELEASE操作，就不需要用内存屏障了（mmio写屏障例外）。
可见，RELEASE+ACQUIRE配对并不是一个完全意义上的内存屏障，但是它能保证：先RELEASE一个旧临界区，再ACQUIRE一个新临界区，新临界区里肯定能看到旧临界区对同一数据的影响。
最后，重复一下：仅在多cpu间以及cpu与io设备间交互操作时，必要情况下才需要动用内存屏障。
2.2.2 内存屏障的非保证
内存屏障对以下内容不做保证：
不保证内存屏障之前的内存操作在该内存屏障指令完成前完成，因为它保证的仅是相对顺序。
本cpu上的内存屏障不会直接影响其他cpu，而是间接影响（通过改变其感知顺序）。
不保证cpu1能看到cpu2的正确顺序，即使cpu2使用了内存屏障，除非cpu1也用了（正确的）配对内存屏障。
cache的同步机制可能会给内存屏障在cpu间作用带来问题（导致发生不期望顺序）。
2.2.3 数据依赖屏障
先看例子:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
ACCESS_ONCE(P) = &B
Q = ACCESS_ONCE(P);
D = *Q;
先无视依赖，那么cpu2可能先感知到P，再感知到B，所以会有下面错误结果:
(Q == &B) and (D == 2) ????
在某些cpu是可能出现这个错误结果的，比如alpha cpu。解决这个错误，就是插入数据依赖屏障:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
ACCESS_ONCE(P) = &B
Q = ACCESS_ONCE(P);
D = *Q;
这种错误情况容易发生在使用split caches机制的cpu上，原因是：cpu2感知B和P的顺序和cup1上真实顺序不一定一样。
另一个例子:
CPU 1 CPU 2
=============== ===============
{ M[ 0 ] == 1, M[ 1 ] == 2, M[ 3 ] = 3, P == 0, Q == 3 }
M[ 1 ] = 4;
ACCESS_ONCE(P) = 1
Q = ACCESS_ONCE(P);
D = M[Q];
道理和上例是一样的，cpu2需要加数据依赖屏障，否则可能会（错误地）先感知P再感知M[ 1 ]！
数据依赖屏障在rcu机制里大展拳脚：可以保证rcu切换到新对象指针时，不会发生新对象没有初始化的错误。因为它保证读该指针时，对象已经初始化完毕。
2.2.4 控制屏障
某些依赖不是数据依赖性质的，可能是跟逻辑控制相关，需要使用控制屏障。控制依赖时需要使用读屏障（或者RELEASE/ACQUIRE），而不能用数据依赖屏障。
举例如下：
q = ACCESS_ONCE(a);
if (q) {
/* BUG: No data dependency!!! */
p = ACCESS_ONCE(b);
}
由于分支预测，其它cpu对本cpu的感知可能是：此cpu先读b再读a（即使本cpu上有条件判断做依赖）。此时需要控制（读）屏障:
q = ACCESS_ONCE(a);
if (q) {
p = ACCESS_ONCE(b);
}
感觉这个性质导致更乱了，还好，没有预写机制：
commit 18c03c61444a211237f3d4782353cb38dba795df
Author: Peter Zijlstra
Date: Wed Dec 11 13:59:06 2013 -0800
Documentation/memory-barriers.txt: Prohibit speculative writes
No SMP architecture currently supporting Linux allows
speculative writes
所以，下例是保序的:
q = ACCESS_ONCE(a);
if (q) {
ACCESS_ONCE(b) = p;
}
注意：这里的ACCESS_ONCE()是必须的，防止与其它操作合并，同时防止编译器优化方式读值。
如果compiler获悉a非0，则可能有更狠的优化:
q = a;
b = p; /* BUG: Compiler and CPU can both reorder!!! */
再考虑另一种优化场景。如果在条件分支里加入相同的优化屏障（为何用优化屏障不用控制（读）屏障？上面刚提到了，不需要支持预写）和写操作，比如：
q = ACCESS_ONCE(a);
if (q) {
barrier();
ACCESS_ONCE(b) = p;
do_something();
} else {
barrier();
ACCESS_ONCE(b) = p;
do_something_else();
}
此时，compiler应该会优化为：
q = ACCESS_ONCE(a);
barrier();
ACCESS_ONCE(b) = p; /* BUG: No ordering vs. load from a!!! */
if (q) {
/* ACCESS_ONCE(b) = p; -- moved up, BUG!!! */
do_something();
} else {
/* ACCESS_ONCE(b) = p; -- moved up, BUG!!! */
do_something_else();
}
这样，在读a和写b之间没有了条件依赖，所以cpu又可以更乱了（远不是控制屏障所能束缚的了）。
要想让其它系统组件正确感知，此处可以用smp_store_release():
q = ACCESS_ONCE(a);
if (q) {
smp_store_release(&b, p);
do_something();
} else {
smp_store_release(&b, p);
do_something_else();
}
关于smp_store_release()如何做到的（其实就是上面内存屏障分类里提到的RELEASE操作），参见：
smp_store_release() writes a value back to memory, ensuring that the write happens after any previously-executed reads or writes.
当然，即使没有内存屏障，如果两个条件里的写操作不同，还是可以保序的：
q = ACCESS_ONCE(a);
if (q) {
ACCESS_ONCE(b) = p;
do_something();
} else {
ACCESS_ONCE(b) = r;
do_something_else();
}
此处注意一个优化特例：可能优化局部变量q，从而删掉条件：
q = ACCESS_ONCE(a);
if (q % MAX) {
ACCESS_ONCE(b) = p;
do_something();
} else {
ACCESS_ONCE(b) = r;
do_something_else();
}
如果此时compiler获悉MAX是1，那么它就随意优化（删掉条件）了：
q = ACCESS_ONCE(a);
ACCESS_ONCE(b) = p;
do_something_else();
此时，没了条件，cpu又可以更乱了。解决方法是加上MAX大于1的保证：
q = ACCESS_ONCE(a);
BUILD_BUG_ON(MAX <= 1); /* Order load from a with store to b. */
if (q % MAX) {
ACCESS_ONCE(b) = p;
do_something();
} else {
ACCESS_ONCE(b) = r;
do_something_else();
}
注意，上面两个条件中的写操作是不同的，否则。。。
另外，在bool类型时也会有问题:
q = ACCESS_ONCE(a);
if (a || 1 > 0)
ACCESS_ONCE(b) = 1;
因为条件恒真，所以优化为：
q = ACCESS_ONCE(a);
ACCESS_ONCE(b) = 1;
注意，cpu要乱，ACCESS_ONCE()是挡不住的：
although ACCESS_ONCE() does force
the compiler to actually emit code for a given load, it does not force
the compiler to use the results.
对控制屏障的总结:
1）控制依赖保证前面的读操作和后面的写操作的次序。不保证：前面的读和后面的读，前面的写和后面的所有。
2）如果if的两个条件里有相同的写操作，每个（条件）的开头都需要优化屏障。
3）compiler可能会把控制屏障优化掉，使用ACCESS_ONCE()或优化屏障减小这种丢失可能。
总之，内存屏障就是在防优化、防乱序、防预测、等等。。。防的多了，最终可能还是防不胜防？（未完待续）
