原子操作与内存顺序

注：本文作于刚学完计算机组成时，对真实 CPU 设计理解较少，有不少事实错误与过度简化，但结论应当是没有问题的。仅供参考，欢迎交流。

额外资料：

https://users.cs.utah.edu/~aburtsev/cs5460/lectures/lecture13-memory-ordering/lecture13-memory-barriers.pdf

https://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf

当我第一次遇到“原子操作”

曾经我刚接触原子操作时，产生了造自旋锁的梦；然而 Linus 的言论给我泼了一盆冷水：

In fact, I’d go even further: don’t ever make up your own locking routines. You will get the wrong, whether they are spinlocks or not. You’ll get memory ordering wrong, or you’ll get fairness wrong, or you’ll get issues like the above “busy-looping while somebody else has been scheduled out”.

当我兴致勃勃地搜索内存顺序——发现 C++ 规定多达六种顺序，网上的解释也五花八门。

CPP Reference (解读: 1 2 3) 定义了大量术语，包括 sequenced-before carries dependency (simply/strongly) happen before modification order release sequence dependency-ordered before inter-thread happens-before visible side-effects，建立了一个极其复杂、一看就是给编译器开发者而非普通开发者和 CPU 开发者写的依赖图模型。

Luyu Huang 采纳了 happens-before 概念，定义了 synchronizes-with（指令同步）概念，认为内存顺序决定了跨线程内存顺序操作之间的同步关系，实践中通过复杂的依赖推导 “happens-before”。

UncP 从 memory barrier(fence) 入手，将效果归结为可见性，认为内存顺序的组合可以确保特定范围的读写可见性。

雨乐从内存模型的来源：编译器优化、乱序执行、cache 不一致出发，解释了 CPP Reference 的一堆概念。

Peihao 将多 CPU 比喻成多个任性的记录员，认为内存顺序对可以保证指令同步和全局观测的顺序。

大多数解释提及了“同步”和“可见/观测到的顺序”，更有解释认为缓存一致性也干了。另一方面大多数文章并未解释真正会造成 bug 的具体情形和原因，而是逐个解释 CPP Reference 的一堆概念和例子；让人摸不清到底为什么要用原子操作和内存顺序。

最近学了计算机组成，对乱序执行、缓存有了深入的理解，回过头来和 ChatGPT 多次深入交流之后，才对原子操作和内存顺序有了初步的领会，本文旨在记录个人理解。

（前置知识：缓存一致性, 指令流水和乱序执行）

竞争状态

Race condition 可谓是万恶之源。所有人都知道多线程会产生竞争，例如下面的例子：

#include <thread>
#include <iostream>

const unsigned MAX = 1024*1024;
const unsigned THREADS = 8;
const unsigned CORRECT = MAX*THREADS;

volatile unsigned x = 0;

void thread_fn() {
    for(int i=0; i<MAX;i++) x++;
}

int main() {
    std::thread threads[THREADS];
    for(int i=0; i<THREADS; i++)
        threads[i]=std::thread(thread_fn);
    for(int i=0; i<THREADS; i++)
        threads[i].join();
    std::cout<<"correctness: "<< (double)x/(double)CORRECT<<'\n';
    return 0;
}

输出不会到达 1，而是一个远低于 1 的数。

这是由于出现了竞争状态，即在特定时序下会产生预期外的结果。

thread_fn 汇编如下：

thread_fn:
	movl	$1048576, %edx
.L4:
	movl	x(%rip), %eax
	addl	$1, %eax
	subl	$1, %edx
	movl	%eax, x(%rip)
	jne	.L4
	ret

周期	CPU0	CPU1
0	`movl x(%rip), %eax`	`addl $1, %eax`
1	`addl $1, %eax`	`movl %eax, x(%rip)`
2	`movl %eax, x(%rip)`	`jne .L4`

预期的行为是一个 cpu core 读、加、写完后另一个 cpu core 再读。然而在这样的时序下，两个 core 读到了相同的值，加一，因而写回了相同的值。问题的本质是：读-加-写操作并非“原子的”，特定的时序会导致操作内指令（并发地）重叠，而这会导致错误。

缓存一致性

很多人有一个误解，就是多核在竞争写一个 cacheline 时会不经同步而一个覆盖掉另一个，产生缓存一致性问题。但事实并非如此。市面上所有多核CPU都实现了严谨的缓存一致性（某些 GPU 可能实现不够严谨），即当一个核写入、另一个核的 cacheline 无效时，另一个核会同步这个 cacheline 再写*，并不会出现内容不一致。

实际上发生的事情就是指令被乱序执行后可能乱序写回，可能乱序读取；同时，竞争状态也会造成一些预期外的的结果，形成了“如写”的假象，被一些人误解成缓存一致性问题。

*: 看似写覆盖了读，这一次读同步是无意义的；但实际上这能保证整个 cacheline 的同步性，尤其是只写了某些字节，而另一些字节被其他 core 修改时。这就是所谓“伪共享”的情形，padding 优化显而易见地可以减少 cacheline 的同步，提高性能。

原子操作

原子操作就是通过锁机制把读-特性操作-写绑定为一个指令，它大致流程如下(ref)

申请 cacheline 锁（旧式设计和非 cache 地址会加总线锁）（例如在 cacheline metadata 上加料）
读并等待 cacheline 被释放（例如 MESI 中变为 Shared/Exclusive 态）（由缓存一致性保证隐式实现）
操作
写并释放锁

由此可以避免指令/流水线的重叠，因而解决了竞争状态问题。不过这种解决方案仅限于已有的原子操作能覆盖的简单操作，更复杂的操作还是得用互斥锁。

常见的原子操作如下：

名称	x86	arm	risc-v
Locked Swap	`(lock) xchg`	/	`amoswap`
Compare and Swap	`cmpxchg`	`cas`	/
Fetch and Add	`xadd`	`ldadd`	`amoadd`
Fetch and And/Or/Xor	`lock and/or/xor`	`ldclr/ldset/ldeor`	`amoand/amoor/amoxor`
Fetch and Min/Max	/	`ldsmax/ldumax/ldsmin/ldumin`	`amomin/amominu/amomax/amomaxu`
Fetch and ?	/	`ldrex`+`strex`	`lr`+`sc`

相信大部分操作大家都不陌生了。值得注意的是最后的 “fetch and ?"。这是 RISC 指令集的一大杰作，通过上面的多个步骤可以看到一个原子操作本质上由多个操作构成，如锁、读、操作、写、解锁。这与 RISC 精简的初心相违背。因此 RISC 提出了 Load-Reserved + Store-Conditional 机制，本质相当于一个自旋临界区，由 Load-Reserved 指令声明进入对应地址的临界区，加上标记后就直接开始操作，直到最后写的时候再检查标记。当竞争发生时，先写的 cpu 会清除所有 cpu 的临界区标记；后写的 cpu 发现标记被清除，说明临界区失效，自旋重新 LR+OP+SC。

如此，每一步都是很 trivial 的，对精简设计和流水线非常友好。在低竞争状态下允许单写多读，而非锁掉整个 cacheline，同时是标记针对 word 而非整个 cacheline，特定场景会比 cacheline 锁快；而在高竞争时由于自旋特性比锁慢不少。不过高竞争——还是想想算法问题吧。

例如 Compare and Swap 可以写成这样：

cas:
    lr.w t0, (a0)        # Load the value from memory into t0 and reserve the address
    bne t0, a1, fail     # If the value is not as expected, jump to fail
    sc.w t1, a2, (a0)    # Attempt to store the new value
    bnez t1, cas         # If the store failed, retry
    mv a0, x0            # Success: return 0
    ret
fail:
    li a0, -1            # Failure: return -1
    ret

这其实严格意义上并不属于原子操作，但效果类似，机制类似，速度类似…就当作是原子操作吧。

内存屏障

我们都知道现在的处理器超标量且乱序执行，内存的读和写（提交）可以在数据相关性和无分支的情况下乱序发生。这通常不会有问题，除非有时序依赖：

volatile int x=0, y=10086;

void thread1() {
    y = y%7;
    x = 1;
}

void thread2() {
    while(x==0);
    assert(y==6);
}

在这个例子中，看似 thread2 会快乐运行下去，实际上由于 x = 1 操作远快于 y%7 操作，导致 y 写可能乱序到 x 之后，进而断言失败。

内存屏障的作用就是指定正确的时序，在屏障指令之前的特定类型指令完成之前，把屏障之后的特定类型指令暂停/挡在后面。例如上面的代码中，在 y=y%7 与 x=1 之间插入 __sync_synchronize() 或者 atomic_thread_fence(memory_order_seq_cst) 即可。

x86 保证了 load-store, load-load, store-store 操作之间不会被乱序，因此 x86 被称为强内存顺序架构；但是其他架构并不保证。上面的代码是 store-store 序，在 x86 上不会有 bug，但是其他架构会有。当然 x86 没有保证 store-load 之间的顺序，毕竟 store commit 在流水线最后，load 在最前面，要保证这个顺序还是太难为流水线了。另一方面，某些 x86 实现中的某些指令，例如向量指令，可能并没有强序保证。

x86 提供了一些屏障 (barrier/fence) 指令以强制屏障之后的内存操作推迟到屏障之前内存操作完成之后。lfence 和 sfence 分别保证了 load-load, store-store 顺序，这两个指令不太有用，因为正常的 x86 指令都已经保证了。mfence 保证了 load/store-load/store 四种顺序组合，最有用的还是 store-load 顺序，只有在需要 store-load 连续操作且保证时序时才需要。

arm 提供了三种屏障。dmb 类似于 mfence，要求此前的内存操作流水完成再执行此后的内存操作流水，它有很多参数。dsb 是 dmb 的加强版，在此前内存操作流水完成之前暂停发射此后的所有指令，包括和内存操作无关的；这在需要保证内存流水完全完成时才执行后面的指令的地方很有用，比如指令隐式依赖内存读写（例如 DMA 指令，IO 指令），或者任何你认为需要等待读写完成的情况。isb 是 dsb 的终极版，是流水线级屏障，此前的流水线全部完成后此后的指令才能开始 fetch；在一些重大上下文变化时需要这条指令，例如状态寄存器修改，页表切换。

例如一个奇妙的情形中，我们的代码可以 JIT 乃至覆盖原来的代码，每次 JIT 完，首先要 dsb 保证写完了，然后需要 invalidate l1i cache （cache coherence 并不保证 l1d 和 l1i 之间的同步），最后 isb 清空之后的流水线，重新 fetch。

更详细的说明非常建议阅读 arm 文档里的内存屏障和内存属性。

riscv 提供了 fence，它允许两个参数：屏障前需完成的操作，和被挡在屏障后的操作。每个参数包括 iorw，即外设的读写，和内存的读写。很灵活。

可见，实用中内存屏障指令通常可以指定前后的读写，它会保证屏障前后的内存操作顺序。

btw 对于外设读写，arm 和 riscv 都提供了对应参数处理，但是 x86 没有，需要通过 cpuid 的串行化 hack 充当 io fence。

内存顺序

所谓强弱内存顺序 CPU，实际上就是 x86 为强而其他为弱（暴论）。x86 为所有的内存操作强加了 load-store, load-load, store-store 之间的顺序保证，代价就是亿些些重排序队列；其他 CPU 则大多纯乱序读写，通过特殊指令来实现特定的屏障和顺序。

C++ 定义的内存顺序如是说（打括号的意味着包装的变量本身读写）：

Relaxed: 允许乱序
Acquire: (load)-store/load
Release: store/load-(store)
AcqRel: Acquire && Release
SeqCst: load/store-(load/store)-load/store

至于 Consume？没 CPU 实现，已经和 Acquire 合并了（悲）

看 Weak ordering CPU 上的朴素实现就很好理解了：

Relaxed: 不插入内存屏障
Release: 在前面插入内存屏障
Acquire: 在后面插入内存屏障
SeqCst: 在前后都插入内存屏障

x86 显然已经保证了 Acquire 和 Release ordering；其 SeqCst 也就是插入 mfence。

对于既读又写的 AcqRel 原子操作，例如成功的 cas, fetch-and-x, 既有前向的屏障也有后向的屏障，因此等效于 SeqCst 顺序等级。

不同架构也提供了一些更高等级内存顺序指令。例如 ldaxr stlr 就是 Acquire-Release。这些指令自带屏障属性，可以减少独立屏障指令的使用。

具体到应用：

Relaxed: 没有其他场景限制的需求，例如全局计数器
Release: 作为临界区开始（加锁），使得所有对某个共享对象的读写都在此后才能开始
Acquire: 作为临界区结束（解锁），使得所有对某个共享对象的读写都在此前已经结束
SeqCst: 一个有严格时序需求的变量操作序列

下面通过一个简陋的 shared_ptr 的实现来展示屏障的效果：

#include <atomic>

template <typename T>
struct shared_ptr_inner {
    std::atomic<size_t> ref_count;
    T data;

    shared_ptr_inner(T data) : ref_count(1), data(std::move(data)) {}
};

template <typename T>
class shared_ptr {
    shared_ptr_inner<T>* inner;

public:
    explicit shared_ptr(T data) : inner(new shared_ptr_inner<T>(std::move(data))) {}

    shared_ptr(const shared_ptr& other) : inner(other.inner) {
        inner->ref_count.fetch_add(1, std::memory_order_relaxed);
    }

    ~shared_ptr() {
        if (inner->ref_count.fetch_sub(1, std::memory_order_release) == 1) {
            std::atomic_thread_fence(std::memory_order_acquire);
            delete inner;
        }
    }

    T& operator*() const {
        return inner->data;
    }

    T* operator->() const {
        return &inner->data;
    }
};

首先看析构：由于需要保证所有 inner 的内存读写在可能的析构前已经完成，需要用一个 release 顺序来减一，而在确定需要析构后用一个 acquire fence 来让后续析构操作在这个 fence 之后才能发生。

有人可能会问，既然只有发生析构才需要 fence，为什么不是 relax + seqcst？可以试想，如果减计数器用 relax，可能会出现如下乱序执行的时序：

(ref_counter = 2)

周期	CPU0	CPU1
0	一些很耗时的写 data	-
1	`ref_counter--` (=1)	-
2	一些很耗时的写 data	`ref_counter--`(=0)
3	一些很耗时的写 data	析构

某个很耗时的写 data 操作乱序到了 counter 写之后，但这个 data 已被另一个 thread 析构了；从而导致乱序执行意义上的 use after free。本质上，减计数器有临界区结束的意味，因此即使是本线程不会析构，也必须用 release fence 确保操作完了才操作 shared_ptr 计数器。

那么为什么复制构造就可以使用 relax 顺序呢？理论上似乎他是一个临界区的开始，应当使用 acquire 顺序；这是因为 acquire 能够防止的就是极端的内容操作被乱序到此 counter 操作前且产生问题的情况，在 shared_ptr 的例子下，有如下可能：

提前访问了 data：由于复制源本就合法，提前访问不成问题
复制源提前析构了：由于析构自带一个 release fence，会把本操作的 load/store 拦在前面，因此并不会提前析构

因此可以用 relax 顺序。

可以看出，这里的 relax 是经过缜密的考虑乱序带来的影响后才选定的；平凡的临界区模型中，还是用 acquire-release 顺序比较好，只有经过仔细考虑后才能使用更宽松的内存顺序。

Boost Doc 提供了一系列使用原子操作和内存顺序的例子和解释，但解释可能不尽严谨，可以参考学习。

编译器乱序

最后一个问题就是编译器乱序了，即编译器会自己打乱指令的顺序，以结合处理器的架构优化。

例如内存屏障的这个例子

volatile int x=0, y=10086;

void thread1() {
    y = y%7;
    x = 1;
}

void thread2() {
    while(x==0);
    assert(y==6);
}

如果不带 volatile，则编译器可能会打乱顺序；此时需要一个 compiler hint asm volatile("" ::: "memory");。

分支后屏障（错误理解）

我之前对分支有一个错误理解：

值得一提的是，当变量操作在一个分支、后续操作位于另一个分支，例如自旋锁，这实际上已经实现了一个简陋的 (branch)-load/store 后屏障机制，因为所有另一个分支的操作在分支跳转前都不能进行，流水线里预测的也会被冲洗掉，只有跳转后才会进行后续操作。因此这种情况下不需要任何内存屏障，编译器也会据此做小小的优化，节省一次后内存屏障指令。
.spin:
    ldr x2, [x0]       // Load the value at the address in x0 into x2
    cmp x2, #0         // Compare x2 with 0
    b.ne .spin         // Branch back to .spin if x2 is not equal to 0
    str x2, [x1]       // Store the value in x2 into the address in x1
    ldr x0, [x1, #8]   // Load the value at the address in x1 + 8 into x0
这是一个加强版的 acquire fence。它可以应用在临界区的开始，例如单例初始化，自旋锁加锁，汇编代码通常不含屏障。

这是完全错误的理解，因为存在一种情况：当分支预测器预测的全是临界区内的分支，仍然不能避免已获取的临界区内外的指令的乱序执行。

总结

综上所述，原子操作和内存屏障主要解决了时序交叉（竞争状态）、乱序执行两大时序导致的问题。一些文档编写者试图隐藏这些底层原理而解释，结果就是 CPP Reference 里面的一堆恶心概念，让众多开发者望洋兴叹，令人遗憾。

对于一般的原子操作场景，例如计数器、累加器，不需要考虑额外的内存屏障和内存顺序。只有有时序要求，或者存在临界区时，例如单例、竞争、同步，才需要仔细考虑。不过最好还是利用已有的同步机制，正如 Intel 软件开发文档里所说：

Software intended to operate correctly in processor-ordered processors should not depend on the relatively strong ordering of the Pentium or Intel486 processors. Instead, it should ensure that accesses to shared variables that are intended to control concurrent execution among processors are explicitly required to obey program ordering through the use of appropriate locking or serializing operations.

不过高抽象的同步机制也不是完全安全的，使用时还是有很多典型漏洞场景。建议刷一遍 Deadlock Empire 先（逃