关于原子操作和弱内存序

作者：赵仁海

什么是原子操作

大家都知道在多核系统上，可以多个CPU核并行执行，即使是在单核系统上，也可以通过中断的方式模拟并行执行。但是内存只有一个，或者确切的说，某一个地址上的数据在内存里只有一个，当有可能出现多个线程对某一个内存地址上的数据同时进行操作的时候，由于这个操作一般会被翻译成CPU的多个指令，当你想实现： 让这多个指令的执行不能被中断，或者同一个内存地址当当前线程在操作的时候其他CPU核不能访问，即使被中断了，或者被其他核访问了，对当前线程也没有任何影响的操作，就可以称之为原子操作。

上面一段话有点绕，我们举个具体的例子：
对一个全局变量i的加一操作，比如i++这行代码，在ARM上，实际编译为底层指令之后，是三个指令，ldr，add，str，也就是首先从内存把i这个变量的值加载到寄存器里面，然后在寄存器上加1，然后再存储到内存里面去。 假设i的值初始为0，这时候一个线程执行了前面两个指令，将寄存器的值加为了1，这个时候另外一个核也执行了同样的代码，或者说当前线程被中断了，被调度给了另外一个执行同样代码的线程，另外一个线程执行完毕之后，i的值为1，当前线程获得执行机会继续执行，但是由于当前线程的前面两个指令执行完了，最后一个指令还没执行，当前线程就会把寄存器里面的值1给存储到内存里面去，i的值仍然是1， 这样就产生了错误。本来两个线程的目的都是加1，结果应该是2，但是执行完结果却是1， 所以在这种时候，就需要原子操作，来保证这三个指令不能被中断，或者说即使被中断了，也不会对结果有什么影响。

原子操作是怎么实现的

上面简单举了个例子供大家来初步认识下什么是原子操作。具体的实现还是比较复杂的。
我们先来看看X86是怎么实现原子操作的，首先我们来看看单核系统的情况，单核系统比较简单，而且在X86上，由于是CISC指令集，是有单独的对内存上的数据直接加1的指令的，也就是说在X86的单核系统上，i++是可以直接被编译成一个原子的指令的，不需要什么额外的操作。但是在多核系统上，由于多个核有可能执行同样的代码，同时访问内存，这个时候也会有可能出现混乱的情况，所以每个核在执行前就需要先锁住内存上的数据，保证在这个指令完成之前，其他CPU不能访问内存这个地址上的数据。 所以如果是在多核的X86系统上，对一个全局变量i++，最后翻译成的汇编指令通常类似于这样的代码：LOCK “incl %0”，其中LOCK的意思就是锁住内存的意思。（最新的X86的CPU实现不是锁内存，而是锁Cache，然后由MESI协议来保证Cache一致性，可以参考这篇文章https://cloud.tencent.com/developer/article/1367365 ，关于MESI协议，是一个更复杂的话题，本文暂不涉及）
再来看看在ARM上，ARM是RISC指令集，一开始我们举得例子也说了，同样的一行代码，ARM要翻译成3个指令，这就说明了，即使在单核的ARM系统上，线程在执行这行代码的时候也有可能被中断，所以如果要实现原子指令，在单核系统上最简单的方法就是关闭中断。
原子操作开始前，先把中断关闭，执行完后再打开，就实现了原子操作。 但是这种方法在多核系统上也不好用了，ARM在多核系统上采用了另外一种方法来实现原子操作。
（下面这段关于多核系统上ARM实现原子指令的描述来自于知乎兰新宇大神的文章，因为写的比较好，我就不重复写了，为了保持叙述的完整性，我把这段copy了过来，原文在这里https://zhuanlan.zhihu.com/p/89299392 ）
在ARM V8.1之前，为实现RMW的原子操作采用的方法主要是LL/SC(Load-Link/Store-Conditional)。ARMv7中实现LL/SC的指令是LDREX/STREX，其实就是比基础的LDR和STR指令多了一个”EX”，”EX”表示exclusive（独占）。具体说来就是，当用LDREX指令从内存某个地址取出数据放到寄存器后，一个硬件的monitor会将此地址标记为exclusive。
假设CPU A先进行load操作，并标记了变量v所在的内存地址为exclusive，在CPU A进行下一步的store操作之前，CPU B也进行了对变量v的load操作，那么这个内存地址的exclusive就成了CPU B标记的了。
之后CPU A使用STREX进行store操作，它会测试store的目标地址的exclusive是不是自己标记的（是否为自己独占），结果不是，那么store失败。接下来CPU B也执行STREX，因为exclusive是自己标记的，所以可以store成功，exclusive标记也同步失效。此时CPU A会再次尝试一轮LL/SC的操作，直到store成功。
ARM64使用LL/SC模式实现原子操作的相关代码位于”/arch/arm64/include/asm/atomic_ll_sc.h”，它通过对”##”粘合符的运用，将不同原子操作的实现放进了同一段代码中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

__LL_SC_PREFIX(arch_atomic_##op(int i, atomic_t *v))			
{									
	unsigned long tmp;						
	int result;							
									
	asm volatile("// atomic_" #op "\n"				
"	prfm	pstl1strm, %2\n"    // prefetch memory			
"1:	ldxr	%w0, %2\n"    // w0 = %2(v->counter)				
"	" #asm_op "	%w0, %w0, %w3\n"     // w0 = w0 + w3 （假设是add）				
"	stxr	%w1, %w0, %2\n"     // %2(v->counter) = w0, 执行结果存储在w1
"	cbnz	%w1, 1b"	   // 若w1 != 0，说明store失败，跳转到标号1重试      		
	"=&r" (result), "=&r" (tmp), "+Q" (v->counter)	// input+output	
	: "Ir" (i));	 // input						
}

这里的”ldxr”和”stxr”就是前面讲的”ldrex”和”strex”，只不过到了ARMv8.0中被改了个名字而已。可以看到，代码实现中会有个比较和循环，失败则会重试。
重试一次还好，如果CPU之间竞争比较激烈，可能导致重试的次数较多，所以从2014年的ARMv8.1开始，ARM推出了用于原子操作的LSE(Large System Extension)指令集扩展，新增的指令包括CAS, SWP和LD, ST等，其中可以是ADD, CLR, EOR, SET等。这些指令也类似于X86上，可以直接对内存上的数据进行原子计算。ARM64使用LSE指令实现原子操作的相关代码位于”/arch/arm64/include/asm/atomic_lse.h”。

1
2
3
4
5
6
7
8
9
10

static inline void arch_atomic_##op(int i, atomic_t *v)			
{									
	register int w0 asm ("w0") = i;					
	register atomic_t *x1 asm ("x1") = v;				
									
	asm volatile(ARM64_LSE_ATOMIC_INSN(__LL_SC_ATOMIC(op),	" " #asm_op "	%w[i], %[v]\n")					
	: [i] "+r" (w0), [v] "+Q" (v->counter)   // nput+output				
	: "r" (x1)      // input						
	: "x16", "x17", "x30");    // clobber list  					
}

确实比LL/SC的实现方式简洁了很多，一条指令就可以搞定，比如实现arch_atomic_add()，只用LDADD指令即可，load操作和store操作合二为一，比较类似于x86的实现（用add指令）。
既然load和store都二合一了，那为啥还分别有LD和ST呢？其实，两者的效果是一样的，比如STADD就可以看做是LDADD的别名(alias)。
STADD <Xs>, [<Xn|SP>]
等同于
LDADD <Xs>, XZR, [<Xn|SP>]
（Copy兰新宇大神文章的内容到此为止）

关于ARMv8.1新的原子指令，这里多说一下，只有在很高的并发下才能显示出性能优势，一般情况下和老的原子指令性能差不多，在一般系统的性能测试下显示不出来差别。关于如何启用新版本的原子指令的方法，可以参考这篇文章：
https://kunpengcompute.github.io/2020/08/29/aarch64-fu-wu-qi-ying-yong-ruan-jian-kai-fa-xu-yao-tian-jia-de-bian-yi-can-shu/

原子操作有什么用

原子操作的用途通过之前的描述，大家应该也清楚了，最简单的，需要全局计数器的场景。
还有像实现自旋锁，信号量等多线程同步机制的地方，都会用到。比如对信号量的count值进行增加，都必须要是原子的。
另外有时候无锁编程的时候也需要原子变量，我们来看一个简单的例子，什么是无锁编程。
还是一开始那个对变量加一的操作例子，假设有两种线程，一种是读线程，负责读取这个变量的值并进行打印，一种是写线程，对这个变量，进行自增。我们现在知道写线程本质上不是原子的，因为它由三个不同的步骤组成，读取值，将其递增，然后将新值存储回去。如果使用锁，伪代码大概是这个样子的：

1
2
3
4
5
6
7
8
9
10
11

mutex = initialize_mutex()
i = 0
reader_thread()
    mutex.lock()
    print(i)
    mutex.unlock()

writer_thread()
    mutex.lock()
    i++
    mutex.unlock()

获取锁的第一个线程可以执行，而其他线程必须排队等待。

相反，无锁方法引入了另一种模式：通过采用原子操作，线程可以不受任何阻碍地自由运行。例如：

1
2
3
4
5
6

i = 0
reader_thread()
    print(load(i))

writer_thread()
    fetch_and_add(i, 1)

这里fetch_and_add()和load()是基于相应硬件指令的原子操作伪代码。这里没有任何东西被锁定。原子性load()确保没有读线程将读取共享值的一半完成，并且没有写线程会由于造成部分写入而损坏共享值。

什么是弱内存序

内存序，顾名思义就是CPU访问内存的顺序。
举个简单的例子，如下代码

1
2
3

a = 1
b = 2
c = a + b

强内存序的机器，就会按顺序执行，a =1 ，b=2， c=a+b
但是弱内存序的机器，有可能会执行成，b=2， a=1，c=a+b，因为a =1和b=2之间先后没什么逻辑依赖，先执行哪个，都不会导致结果有问题，编译器或者CPU就会自动的做一些优化，因为根据现代CPU结构的设计，指令执行流水线的重新排序或者乱序执行可能会带来性能的提升。这就是弱内存序。
那有人会问，那c = a+b会不会先执行？有可能还真会，但是在ARM和X86上都不会，在Alpha上会。上面说的强内存序和弱内存序也都是为了方便理解，简单的说法，实际上有多种内存序，不同的CPU架构上有不同的内存序。我们可以看看下表（转自https://zh.wikipedia.org/wiki/%E5%86%85%E5%AD%98%E6%8E%92%E5%BA%8F 考虑到国内有人无法访问维基，把表截过来）

可以看出来，内存序分了读读是否会乱序，读写是否会乱序，写写是否会乱序，写读是否会乱序，依赖是否会乱序等多种，在不同的架构上支持各种不同的内存访问顺序。 可以看出来，ARM对于上下文有依赖的指令，还是不会乱序执行的。
为了简单理解起见，后文我们就简单认为ARM是弱内存序模型，X86是强内存序模型。

弱内存序会导致什么问题

如果所有代码都是单线程的，当然不会有什么问题，但是如果代码是多线程的，就可能会了。考虑如下代码：

1
2
3
4
5
6
7
8
9
10
11

void foo(void)
{
   a = 1;
   b = 1;
}

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

假如一个线程执行foo，另外一个线程执行bar，在强内存序机器上，不会有问题，肯定可以确保，当b的值不为0以后，a的值肯定是1。但是在弱内存序机器上就会出现问题，因为b=1有可能先于a=1执行，因为在执行foo的线程来看，这两个并没有什么逻辑关系。 这个时候执行bar的线程如果在b=1执行完之后得到了执行的机会，这个时候，assert（a==1）就会返回错误了。

怎么避免弱内存序带来的问题

内存屏障可以避免弱内存序带来的问题。
内存屏障有两种，一种是编译器的内存屏障，这种内存屏障对避免弱内存序的问题，其实没什么用，这种内存屏障只是保证了编译器编译出来的汇编指令，b=1肯定会在a=1后面，但是实际CPU执行的时候到底谁在先，谁在后就不一定了。（编译器的内存屏障，在ARM上就是这么一行代码，asm volatile(“”: : :”memory”)，在一些特殊的场景有用，比如明确需要避免编译器自动优化的场景）

另外一种就是CPU的内存屏障，这种可以解决弱内存序的问题。
CPU内存屏障分为三种，读内存屏障，写内存屏障，还有就是读写内存屏障。
读内存屏障的意思就是本线程所有后续的读操作均在本条指令以后执行，写内存屏障就是本线程所有之前的写操作均在本条指令以前执行。
X86上的CPU内存屏障指令要简单一些，就分了三种：lfence，sfence，mfence，分别对应读屏障，写屏障，读写屏障。
(有人会问X86既然是强内存序，为什么还需要内存屏障，其实X86，并不是完全有序的，根据上面的表格，X86在某些场景也会乱序执行，可以参考这篇文章 https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/ ）
ARM上的稍微有点复杂，又分了几种情况：
DMB
全称 Data Memory Barrier，仅当所有在它前面的存储器访问都执行完毕后，才执行它后面的存储器访问动作（注意只对存储器访问敏感），其它非内存访问指令依然可以乱序执行。
DSB
全称Data Synchronous Barrier，比DMB严格：仅当所有在它前面的存储器访问都执行完毕后，才执行它在后面的指令（亦即任何指令都要等待）。
ISB
全称 Instruction Synchronous Barrier，该指令将刷新CPU pipeline和prefetch buffer，ISB之后的指令需要重新从cache或memory取指，以保证所有它前面的指令都执行完毕之后，才执行它后面的指令。
其中每种指令，根据内存和Cache共享域又分了这么些参数：

其中共享域的含义如下：
Non-shareable：core独享区域
Inner shareable：可被多核共享，但不需要都可访问。一个系统中可能有多个Inner shareable区域
Outer shareable：影响Outer Shareable的操作，隐性的会影响其中的所有Inner Shareable区域。反过来不成立
Full System：影响系统中的所有observer

如果考虑到X86到ARM的移植，一般对应关系是这样的：

建议平时如果新写的代码的话，尽量用linux提供的API，列表如下：

其中barrier就是我们所说的编译器屏障，其余都是CPU屏障
在内核中，tools/arch/arm64/include/asm/barrier.h文件给出了常用的内存屏障相关的宏定义，实际上和上面x86和arm对应表格里面的内容一样的。

1
2
3

#define smp_mb()    asm volatile("dmb ish" ::: "memory")
#define smp_wmb()   asm volatile("dmb ishst" ::: "memory")
#define smp_rmb()   asm volatile("dmb ishld" ::: "memory")

原子操作怎么会和弱内存序扯到一块

在ARM平台上，从ARMv8开始，在很多指令里面就直接加上了内存屏障的语义，比如ldxr/stxr汇编指令 和ldaxr/stlxr汇编指令，如果在需要内存屏障的场景，用ldxr或者stxr的话，还需要再加上单独的内存屏障的指令，但是如果用ldaxr和stlxr的话，就不再需要内存屏障了。实测效果，后者要比前者性能更好。从ARMv8.1开始，新加入的原子指令，也有实现了内存屏障语义的版本，可以参考这篇文章：
https://blog.csdn.net/Roland_Sun/article/details/107552574
当然上面用汇编指令讲解，只是为了方便大家理解，平时如果是新开发代码的话，建议不要直接使用汇编指令，建议使用gcc内置的函数，这样平台通用性更强，具体函数列表可以参考这个链接：
https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
里面的内存屏障参数语义含义如下：

我们为什么要学习原子操作和弱内存序

有人说这些东西是不是太底层了，平时是不是用不到这些知识。其实不是，除了上面所说的无锁编程场景之外，至少以下几种场景还是要用到的。
1 C和C++多线程编程，如果不了解弱内存序的知识，还是很可能会产生一些bug的，而且这些bug都很难定位。
2 定位由于弱内存序产生的bug，即使是业界知名的软件，比如mysql等一些软件，在兼容ARM的过程中，由于弱内存序的问题，也会有很多bug，定位这些bug，也需要这方面的相关知识。
3 如果一些软件一开始只支持了X86，并且使用了底层的原子操作，你如果想要将这些软件兼容ARM，并进行相关开发工作的话，你就要对这些原子操作汇编指令等等进行对应的移植，还要优化。这个时候也需要这方面的知识。比如我们团队在移植Impala过程中的相关开发工作：https://gerrit.cloudera.org/#/c/15300/
4 有时候有些软件的内存序使用过于严格，也需要进行优化，会对软件的性能有一定的提升。比如我们团队大牛在mysql上的一些优化工作，就是针对这方面的，比如有些原子变量的自增，并不需要依赖上下文，所以就可以不需要严格的内存屏障语义。可以参考：
https://bugs.mysql.com/bug.php?id=99432
https://bugs.mysql.com/bug.php?id=100119
https://bugs.mysql.com/bug.php?id=100432
https://bugs.mysql.com/bug.php?id=100060
https://bugs.mysql.com/bug.php?id=100132

参考资料：
https://blog.csdn.net/jus3ve/article/details/81294505
http://blog.sina.com.cn/s/blog_70441c8e0102vrcs.html
https://zhuanlan.zhihu.com/p/89299392
https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
https://www.cnblogs.com/fanzhidongyzby/p/3654855.html
https://labs.supinfochina.com/%E5%85%B7%E6%9C%89%E5%8E%9F%E5%AD%90%E6%93%8D%E4%BD%9C%E7%9A%84%E6%97%A0%E9%94%81%E5%A4%9A%E7%BA%BF%E7%A8%8B/
https://zh.wikipedia.org/wiki/%E4%B9%B1%E5%BA%8F%E6%89%A7%E8%A1%8C
http://www.wowotech.net/memory_management/456.html
http://www.wowotech.net/kernel_synchronization/Why-Memory-Barriers.html
https://zhuanlan.zhihu.com/p/94421667
https://zh.wikipedia.org/wiki/%E5%86%85%E5%AD%98%E6%8E%92%E5%BA%8F
https://zh.wikipedia.org/wiki/%E5%86%85%E5%AD%98%E5%B1%8F%E9%9A%9C
http://www.wowotech.net/kernel_synchronization/memory-barrier.html
http://www.wowotech.net/armv8a_arch/Observability.html
https://stackoverflow.com/questions/21535058/arm64-ldxr-stxr-vs-ldaxr-stlxr
https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/
https://cloud.tencent.com/developer/article/1367365