15 Advanced Synchronization: Memory Ordering

15.1 Ordering: Why and How?

例1 以下这个例子在各个平台下都可以触发exists，包括x86。

/* C-SB+o-o+o-o.litmus */
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)

15.1.1 Why Hardware Misordering?

解释了上述的例子中是如何出现exists (1:r2=0 /\ 0:r2=0)这一结果的。

注意到第4行，在CPU0和CPU1同时发出read-invalidate消息之后，两个CPU会交换cacheline。

最后再将store buffer中的值写入到新得到的cacheline中。

15.1.2 How to Force Ordering?

例2

P0(int *x0, int *x1)
{
	int r2;

	WRITE_ONCE(*x0, 2);
	smp_mb();	
	r2 = READ_ONCE(*x1);
}


P1(int *x0, int *x1)
{
	int r2;

	WRITE_ONCE(*x1, 2);
	smp_mb();	
	r2 = READ_ONCE(*x0);
}

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

以下为exists (1:r2=2 /\ 0:r2=2)的时序：

以下为linux内核中内存序相关的原语：

15.1.3 Basic Rules of Thumb

15.2 Tricks and Traps

15.2.1 Variables With Multiple Values 15.2.2 Memory-Reference Reordering 15.2.3 Address Dependencies 15.2.4 Data Dependencies 15.2.5 Control Dependencies 15.2.6 Cache Coherence 15.2.7 Multicopy Atomicity

15.3 Compile-Time Consternation 15.3.1 Memory-Reference Restrictions 15.3.2 Address- and Data-Dependency 15.3.3 Control-Dependency Calamities 15.4 Hardware Specifics 15.4.1 Alpha 15.4.2 ARMv7-A/R 15.4.3 ARMv8 15.4.4 Itanium 15.4.5 MIPS 15.4.6 POWER / PowerPC 15.4.7 SPARC TSO 15.4.8 x86 15.4.9 z Systems 15.5 Where is Memory Ordering Needed?

Appendix C Why Memory Barriers?

C.1 Cache Structure

当一个特定的数据项初次被CPU访问时，它在缓存中还不存在，这称为“缓存缺失”(cache miss)。

经过一段时间后，CPU的缓存将被填满，后续的缓存缺失很可能需要换出缓存中现有的数据，以便为最近的访问项腾出空间。这种“缓存缺失”被称为“容量缺失”(capacity miss)，因为它是由于缓存容量限制而造成的。

但是，即使此时缓存还没有被填满，大量缓存也可能由于一个新数据而被换出。这是由于大容量缓存是通过硬件哈希表来实现的。

因此，在一个特定的CPU写数据前，让所有CPU都意识到数据被修改这一点是非常重要的，因此，它必须首先从其他CPU的缓存中移除，或者叫“使无效”(invalidated)。

一旦“使无效”操作完成，CPU可以安全的修改数据项。如果数据存在于该CPU缓存中，但是是只读的，这个过程称为“写缺失”(write miss)。

随后，如果另外某个CPU试图访问数据项，将会引起一次缓存缺失，此时，由于第一个CPU为了写而使得缓存项无效，这种类型的缓存缺失被称为“通信缺失”(communication miss)。

我的小问题:write miss和communication miss的区别是什么？ write miss的定义：如果数据存在于该CPU缓存中，但是是只读的，这个过程称为“写缺失”(write miss)。
这看起来更像是一种状态。
而communication miss是一种事件。

C.2 Cache-Coherence Protocols

详见原文。

我的小问题：如何理解read invalidate消息？

答案：When the CPU does an atomic readmodify-write operation on a data item that was not present in its cache. It transmits a “read invalidate”, receiving the data via a “read response”.
At the same time, the CPU can complete the transition of MESI status once it has also received a full set of “invalidate acknowledge” responses.
相当于把一个变量的所有权从其他CPU中夺了过来，与排他读的语义相近。

C.3 Stores Result in Unnecessary Stalls

C.3.1 Store Buffers

避免这种不必要的写停顿的方法之一，是在每个CPU和它的缓存之间，增加store buffer，如图C.5。通过增加这些store buffer区，CPU 0可以简单地将要保存的数据放到store buffer区中，并且继续运行。当缓存行最终从CPU1转到CPU0时，数据将从存储缓冲区转到缓存行中。

C.3.2 Store Forwarding

每个CPU在执行加载操作时，将先从store buffer中获取，如图C.6。换句话说，一个特定的CPU存储操作直接转发给后续的读操作，而并不必然经过其缓存。

C.3.3 Store Buffers and Memory Barriers

内存屏障smp_mb将导致CPU在刷新store buffer中后续的store操作到cacheline之前，前面的store操作先被刷新。

C.4 Store Sequences Result in Unnecessary Stalls

不幸的是，每一个store buffer相对而言都比较小，这意味着执行一段较小的存储操作序列的CPU，就可能填满它的store buffer（例如，当所有store操作都发生了cache misses时）。从这一点来看，CPU在能够继续执行前，必须再次等待刷新操作完成，其目的是为了清空它的store buffer。

相同的情况可能在内存屏障之后发生，内存屏障之后的所有store操作指令，都必须等待刷新操作完成，而不管这些后续store是否存在缓存缺失。

这可以通过使invalidate acknowledge messages更快到达CPU来到得到改善。

C.4.1 Invalidate Queues

在发送应答前，CPU 不必真正使无效缓存行。它可以将使无效消息入队列。
如下图所示:

C.4.2 Invalidate Queues and Invalidate Acknowledge

CPU必须在准备发送使无效消息前，引用它的使无效队列。

如果一个缓存行相应的条目在使无效队列中，则CPU不能立即发送使无效消息，它必须等待无效队列中的条目被处理。

C.4.3 Invalidate Queues and Memory Barriers

内存屏障指令能够与使无效队列交互，这样，当一个特定的CPU执行一个内存屏障时，它标记无效队列中的所有条目，并强制所有后续的load操作进行等待，直到所有标记的条目都保存到CPU的缓存中。

C.5 Read and Write Memory Barriers

Roughly speaking，一个“读内存屏障”仅仅标记它的使无效队列，一个“写内存屏障”仅仅标记它的存储缓冲区，而完整的内存屏障同时标记无效队列及存储缓冲区。

C.6 Example Memory-Barrier Sequences

本节提供了一些有趣的、但是稍微有点不一样的内存屏障用法。
虽然它们能在大多数时候正常工作，但是其中一些只能在特定CPU上运行。
如果目的是为了产生那些能在所有CPU上都能运行的代码，那么这些用法必须要避免。
为了更好理解它们之间的微妙差别，我们首先需要关注乱序体系结构。

C.6.1 Ordering-Hostile Architecture

这里作者设计了一个虚构的、最大限度的乱序体系结构，如下图所示：

其硬件约束如下：

1．单个 CPU总是按照编程顺序来感知它自己的内存访问。

2．仅仅在操作不同地址时，CPU才对给定的store操作进行重新排序。

3．一个特定 CPU，在内存屏障之前的所有load操作（smp_rmb()）将在所有读内存屏障后面的操作之前被所有其他CPU所感知。

4．一个特定 CPU，所有在写内存屏障之前的写操作（smp_wmb()）都将在所有内存屏障之后的写操作之前，被所有其他CPU所感知。

5．一个特定 CPU，所有在内存屏障之前的内存访问（load和store）（smp_mb()）都将在所有内存屏障之后的内存访问之前，被所有其他CPU所感知。

小问题C.11：针对上述第1点——每个CPU按序看到它自己的内存访问，这样能够确保每一个用户线程按序看到它自己对内存的访问吗？为什么能，为什么不能？

答案：不能。考虑这样一种情况，一个线程从一个CPU迁移到另外一个CPU，目标CPU感知到源CPU最近对内存的访问是乱序的。为了保证用户态的安全，内核黑客必须在进程切换时使用内存屏障。但是，在进程切换时要求使用的锁操作，已经自动提供了必要的内存屏障，这导致用户态任务将按序看到自己对内存的访问。也就是说，如果你正在设计一个super-optimized scheduler，不管是在内核态还是用户态，都要注意这种情形。

C.6.2 Example 1

初始状态：a == b == c == 0

我们假设CPU 0最近经历了太多cache miss，以至于它的message queue满了。CPU 1比较幸运，它操作的内存变量在cacheline中都是exclusive状态，不需要发送和node 1进行交互的message，因此它的message queue是空的。对于CPU0而言，a和b的赋值都很快体现在了NODE 0的cache中（CPU1也是可见的），不过node 1不知道，因为message都阻塞在了cpu 0的message queue中。与之相反的是CPU1，其对c的赋值可以通过message queue通知到node1。这样导致的效果就是，从cpu2的角度看，它先观察到了CPU1上的c=1赋值，然后才看到CPU0上的对a变量的赋值，这也导致了尽管使用了memory barrier，CPU2上仍然遭遇了assert fail。之所以会fail，主要是在cpu2上发生了当z等于1的时候，却发现x等于0。

我的小问题：这里的Message Queue指的是什么？

我的答案：不是store buffer也不是invalid queue，因为如文中所述：a和b的赋值都很快体现在了NODE 0的cache中（CPU1也是可见的），说明此时新值已经从store buffer中写到了cache中，但是Invalidate消息还没发出去。
所以说明这里的message queue就是存放的就是本CPU要发送的message，可能堆积的是那些已经发出去但是还没得到应答的message。

小问题C.12：这段代码可以通过在CPU1的“while”和对“c”的赋值之间插入一个内存屏障来修复吗？(见C.6.3 Example 2)为什么能，为什么不能？

答案：不能，这样的内存屏障仅仅强制CPU1本地的内存顺序。它对CPU0和CPU1之间的关联顺序没有效果，因此断言仍然会失败。

保证(Guarantee):但是所有主流计算机系统提供一种“可传递”机制，这将提供一种直观感觉上的顺序，如果B看见A的操作，并且C看见B的操作，那么C必定也看见A的操作。

C.6.3 Example 2

分析见上述小问题C.12。

从原理上来说，编写可移植代码不能用上面的例子，但是，正如前面一样，实际上这段代码可以在大多数主流的计算机正常运行。

C.6.4 Example 3

请注意，不管是CPU 1 还是 CPU 2都要看到CPU0在第三行对“b”的赋值后，才能处理第5行。一旦CPU 1和2已经执行了第4行的内存屏障，它们就能够看到CPU0在第2行的内存屏障前的所有赋值。类似的，CPU0在第8行的内存屏障与CPU1和CPU2在第4行的内存屏障是一对内存屏障，因此CPU0将不会执行第9行的内存赋值，直到它对“a”的赋值被其他CPU可见。因此，CPU2在第9行的assert将不会触发。

Linux内核的synchronize_rcu（）原语使用了类似于本例中的算法。

小问题C.14：如果在表C.4的例子中，CPU 2 执行一个断言assert（e＝＝0

c＝＝1），这个断言会被触发吗？

答案：结果依赖于CPU是否支持“可传递性”。换句话说，通过在CPU 0对“c”的加载和对“e”的存储之间的内存屏障，CPU 0在看到CPU 1对“c”的存储之后，才对“e”进行存储。如果其他CPU看到CPU 0对“e”的存储，那么是否能够保证看到CPU 1的存储？

保证(Guarantee):所有我关注到的CPU都声称提供可传递性。

C.7 Memory-Barrier Instructions For Specific CPUs

内存序模型

每个CPU都有它自己特定的内存屏障指令，这可能会给我们带来一些移植性方面的挑战，如表C.5所示。

实际上，很多软件环境，包括pthreads和Java，简单的禁止直接使用内存屏障，强制要求程序员使用互斥原语，这些互斥原语包含内存屏障，对内存屏障进行所需的扩展。

在表C.5中，前4列表示CPU是否允许4种加载和存储组合进行重排。

第5-6列表示CPU是否允许加载/存储操作与原子指令一起进行重排。

第7列，数据依赖读重排，需要由随后与Alpha CPU相关的章节进行解释。简短的讲，Alpha需要为关联数据之间的读以及更新使用内存屏障。是的，这表示Alpha确实可能在它取得指针本身的值之前，取得指针指向的值。这听起来很奇怪，但是确实是真的。

这种极端弱内存序模型的好处是，Alpha可以使用更简单的缓存硬件，因而允许更高的时钟频率。

第8列表示特定CPU是否拥有一个不一致的指令缓存和流水线。对于自修改代码来说，一些CPU需要执行特殊的指令。

带括号的CPU名称表示CPU允许这样的模式，但是实际上很少被使用。

在2018版的perbook中的15.4节提供了最新的内存序图。

内核中的内存屏障指令

1．smp_mb（）：同时针对加载、存储进行排序的内存屏障。这表示在内存屏障之前的加载、存储，都将在内存屏障之后的加载、存储之前被提交到内存。

2．smp_rmb（）：仅仅对加载进行排序的读内存屏障。

3．smp_wmb（）：仅仅对存储进行排序的写内存屏障。

4．smp_read_barrier_depends（）：强制将依赖于之前操作的后续操作进行排序。除了ALPHA之外，这个原语在其他体系上都是空操作。

5．mmiowb（）：强制将那些由全局自旋锁保护的MMIO写操作进行排序。在自旋锁已经强制禁止MMIO乱序的平台中，这个原语是空操作。mmiowb（）非空的平台包括一些（但是不是全部）IA64、FRV、MIPS和SH。这个原语比较新，因此很少有驱动使用到了它。

我的小问题：什么是MMIO？全书多次提到这个概念，把它当成一种非通用场景作为考虑。

smp_前缀代表这些原语仅仅在SMP内核上才产生代码，它们都存在一个UP版本（分别是mb()、rmb()、wmb()和read_barrier_depends()），即使在UP内核中，这些原语在也生成代码。

我的小问题：什么是SMP内核，什么是UP内核。

C.7.3 ARMv7-A/R

ARM CPU族在嵌入式应用中极为流行，特别是在电源受限的应用中，如移动电话。虽然如此，ARM多核已经存在五年以上的时间了。它的内存模型类似于Power（参见C.7.6节），但是ARM使用了不同的内存屏障指令集：

1．DMB（数据内存屏障）导致在屏障前的相同类型的操作，看起来先于屏障后的操作先执行。操作类型可以是所有操作，也可能仅限于写操作。

ARM allows cache coherence to have one of three scopes: single processor, a subset of the processors (“inner”) and global (“outer”).

ARM 允许三种范围的缓存一致性：单处理器，处理器子集（“inner”）以及全局范围内的一致（“outer”）。

2．DSB（数据同步屏障）导致特定类型的操作，在随后的任何操作被执行前，真的已经完成。操作类型与DMB相同。在ARM体系早期的版本中，DSB指令被称为DWB（清除写缓冲区还是数据写屏障皆可）。

3．ISB（指令同步屏障）刷新CPU流水线，这样所有随后的指令仅仅在ISB指令完成后才被读取。例如，如果你编写一个自修改的程序（如JIT），应当在生成代码及执行代码之间执行一个ISB指令。

没有哪一个指令与Linux的rmb（）语义完全相符。因此必须将rmb（）实现为一个完整的DMB。DMB和DSB指令具有访问顺序方面的递归定义，其具有类似于POWER架构累积性的效果。

ARM also implements control dependencies, so that if a conditional branch depends on a load, then any store executed after that conditional branch will be ordered after the load.

ARM 也实现了控制依赖，因此，如果一个条件分支依赖于一个加载操作，那么在条件分支后面的存储操作都在加载操作后执行。

However, loads following the conditional branch will not be guaranteed to be ordered unless there is an ISB instruction between the branch and the load. Consider the following example:

但是，并不保证在条件分支后面的加载操作也是有序的，除非在分支和加载之间有一个ISB指令。如下例：

r1 = x;
if (r1 == 0)
    nop();
y = 1;
r2 = z;
ISB();
r3 = z;

In this example, load-store control dependency ordering causes the load from x on line 1 to be ordered before the store to y on line 4.

在这个例子中，存储/加载控制依赖导致在第1行的加载x操作被排序在第4行对Y的存储操作之前。

However, ARM does not respect load-load control dependencies, so that the load on line 1 might well happen after the load on line 5.

但是，ARM并不考虑加载/加载控制依赖，因此，第1行的加载也许会在第5行的加载操作后面发生。

On the other hand, the combination of the conditional branch on line 2 and the ISB instruction on line 6 ensures that the load on line 7 happens after the load on line 1.

另一方面，第2行的条件分支与第6行的ISB指令确保第7行在第1行后面发生。

Note that inserting an additional ISB instruction somewhere between lines 3 and 4 would enforce ordering between lines 1 and 5.

注意，在第3行和第4行之间插入一个ISB指令将确保第1行和第5行之间的顺序。 如下所示：

r1 = x;
if (r1 == 0)
    nop();
ISB();
y = 1;
r2 = z;
ISB();
r3 = z;

15.4.3 ARMv8

ARMv8’s memory model closely resembles its ARMv7 counterpart, but adds load-acquire (LDLARB, LDLARH, and LDLAR) and store-release (STLLRB, STLLRH, and STLLR) instructions.

ARMv8的内存模型与ARMv7的存储器模型非常相似，但是增加了load-acquire（LDLARB，LDLARH和LDLAR）和store-release（STLLRB，STLLRH和STLLR）指令。

These instructions act as “half memory barriers”, so that ARMv8 CPUs can reorder previous accesses with a later LDLAR instruction, but are prohibited from reordering an earlier LDLAR instruction with later accesses, as fancifully depicted in Figure 15.14. Similarly, ARMv8 CPUs can reorder an earlier STLLR instruction with a subsequent access, but are prohibited from reordering previous accesses with a later STLLR instruction.
As one might expect, this means that these instructions directly support the C11 notion of load-acquire and store-release.(此概念的说明可参考此处)

Read-Acquire用于修饰内存读取指令，一条 read-acquire 的读指令会禁止它后面的内存操作指令被提前执行，即后续内存操作指令重排时无法向上越过屏障，下图直观的描述了这一功能：

Write-Release用于修饰内存写指令，一条 write-release 的写指令会禁止它上面的内存操作指令被滞后到写指令完成后才执行，即写指令之前的内存操作指令重排时不会向下越过屏障，下图直观描述了这一功能：

However, ARMv8 goes well beyond the C11 memory model by mandating that the combination of a store-release and load-acquire act as a full barrier under many circumstances. For example, in ARMv8, given a store followed by a store-release followed a load-acquire followed by a load, all to different variables and all from a single CPU, all CPUs would agree that the initial store preceded the final load.
Interestingly enough, most TSO architectures (including x86 and the mainframe) do not make this guarantee, as the two loads could be reordered before the two stores.

除了支持C11标准中对应的语义之外，ARMv8在许多情况下将store-release和load-acquire的结合作为full barrier。 例如，在ARMv8中，给出如下操作序列，所有这些都存储在不同的变量中，并且全部来自一个CPU，所有CPU都同意第1行的store在第4行的load之前执行。

store
store-release
load-acquire
load

有趣的是，大多数TSO(total store order)体系结构（包括x86和大型机）都不能保证这一点，因为可以两个store之前对这两个load进行重新排序。

ARMv8 is one of only two architectures that needs the smp_mb__after_spinlock() primitive to be a full barrier, due to its relatively weak lock-acquisition implementation in the Linux kernel.

ARMv8是仅有的两种需要smp_mb__after_spinlock（）原语成为完整障碍的体系结构之一，这是由于其在Linux内核中的锁获取实现相对较弱。

ARMv8 also has the distinction of being the first CPU whose vendor publicly defined its memory ordering with an executable formal model [ARM17].

ARMv8还有一个区别，它是第一个供应商使用可执行的正式模型公开定义其内存顺序的CPU，详见arm白皮书。

我的小问题：LDXR/STXR和LDAXR/STLXR的区别？

答案：LDXR/STXR具有Exclusive语义，而LDAXR/STLXR除此之外还具有Acquire-Release语义，用于保证执行顺序。

C.7.8 x86

由于x86 CPU提供“process ordering”，因此所有CPU都会一致性的看到某个特定CPU对内存的写操作。

这样smp_wmb（）实现为一个空操作。但是，它需要一个如下所示的编译屏障指令barrier()，以避免编译器进行性能优化，这样的性能优化导致越过smp_wmb（）前后的指令的重排。

#define barrier() __asm__ __volatile__("": : :"memory")

从其他方面来说，x86 CPU传统上不保证load的顺序，smp_mb（）和smp_rmb（）被扩展为lock;addl。这个原子指令实际上是一个同时针对load和store的屏障。

Intel也为x86发布了一个内存模型白皮书：Intel® 64 Architecture Memory Ordering White Paper。

事实证明，Intel 实际的CPU执行比前面的规范要求更严的内存序，因此，这个规范事实上只是强制规范早期的行为。

Even more recently, Intel published an updated memory model for x86 [Int11, Section 8.2], which mandates a total global order for stores, although individual CPUs are still permitted to see their own stores as having happened earlier than this total global order would indicate. This exception to the total ordering is needed to allow important hardware optimizations involving store buffers.

最近一段时间，Intel 发布了一个更新的内存模型，详见Int11的8.2节——它要求对store来说实现全局序。虽然对单个CPU来说，仍然允许它看到自己的存储操作，而这些操作早于全局序发生。这个全局序的例外情况是必要的，因为每个CPU需要其store buffer的优化。

In addition, memory ordering obeys causality, so that if CPU 0 sees a store by CPU 1,then CPU 0 is guaranteed to see all stores that CPU 1 saw prior to its store. Software may use atomic operations to override these hardware optimizations, which is one reason that atomic operations tend to be more expensive than their non-atomic counterparts. This total store order is not guaranteed on older processors.

另外，内存序遵从“传递性”，因此，如果CPU0看到CPU1存储的值，那么CPU0也能看到，在CPU 1的存储操作之前，它所能看到的值。软件可以使用原子操作，来使这些优化无效，这也是原子操作比非原子操作开销更大的原因之一。全局存储序在老的处理器上并不能得到保证。

It is also important to note that atomic instructions operating on a given memory location should all be of the same size [Int11, Section 8.1.2.2]. For example, if you write a program where one CPU atomically increments a byte while another CPU executes a 4-byte atomic increment on that same location, you are on your own.

有一个特别需要注意的是，在一个特定内存位置的原子指令操作应当对齐相同大小的内存(Int11的8.1.2.2)。例如，如果你编写一个程序，它在一个CPU上对一个字节进行原子递增，而另一个CPU对同一个地址执行一个4字节原子递增，其后果需要由你自己负责。

However, note that some SSE instructions are weakly ordered (clflush and non-temporal move instructions [Int04a]). CPUs that have SSE can use mfence for smp_mb(), lfence for smp_rmb(), and sfence for smp_wmb().

但是，请注意某些SSE 指令是弱序的（clflush及non-temporal搬移指令[Int04a]）。有SSE指令的CPU可以用mfence实现smp_mb（），lfence实现smp_rmb（），sfence实现smp_wmb（）。

A few versions of the x86 CPU have a mode bit that enables out-of-order stores, and for these CPUs, smp_wmb() must also be defined to be lock;addl.

某些版本的x86 CPU有一个模式位，允许在存储之间乱序，在这些CPU上，smp_wmb（）必须被定义为lock；addl。

Although newer x86 implementations accommodate self-modifying code without any special instructions, to be fully compatible with past and potential future x86 implementations, a given CPU must execute a jump instruction or a serializing instruction (e.g., cpuid) between modifying the code and executing it [Int11, Section 8.1.3]

虽然较新的x86 实现可以适应自修改代码而不需要任何特殊指令，但是为了兼容旧的及以后的x86实现，一个特定CPU必须在修改代码及执行该代码之间，执行一个跳转指令或者串行化指令（例如cpuid等）[Int11，8.1.3节]。

C.8 Are Memory Barriers Forever?

讨论未来的CPU设计是否会做出一定的改变使得内存屏障成为历史。

C.9 Advice to Hardware Designers

过去的硬件设计中引入的问题：

1. I/O devices that ignore cache coherence.
2. External busses that fail to transmit cache-coherence data.
3. Device interrupts that ignore cache coherence.
4. Inter-processor interrupts (IPIs) that ignore cache coherence.
5. Context switches that get ahead of cache coherence.
6. Overly kind simulators and emulators.

其他参考资料

多进程和多线程的区别