0%

volatile和内存屏障

前言

事实上,我很多次以为我懂了volatile的原理,最终都是错误的。
关于重排序,CPU,缓存一致性,内存可见性的话题,其实非常复杂。

这篇文章较为混乱,较为详细的可以看笔者的一个系列:

搞懂内存屏障-CPU重排序

搞懂内存屏障-CPU的演进

搞懂内存屏障-指令与JMM

很多文章提到的关于volatile的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int data[5] = { 9, 9, 9, 9, 9 };
bool is_ready = false;

void init_data() {
for( int i=0; i < 5; ++i )
data[i] = i;
is_ready = true;
}

void sum_data() {
if( !is_ready )
return;
int sum = 0;
for( int i=0; i <5; ++i )
sum += data[i];
printf( "%d", sum );
}

如果我们启动两个线程,线程1执行init_data(),另外一个线程不断执行sum_data()
正常的结果应该是0+1+2+3+4,但是由于重排序和内存可见性的问题,得到的结果是不一定的。

其实我们很多人没有思考过一个问题:

在这个例子中,是因为内存可见性的问题造成的,还是重排序的问题造成的?还是两个一起造成的

太长不看:

  1. CPU对指令进行重排序的条件非常苛刻,在这个例子中,完全不存在CPU会将指令重排序的问题。这个代码运行出现的问题,完全是内存可见性的问题。
  2. 其实关于Volatile的所有问题都是内存可见性的问题,只不过看起来像是CPU重排序了。
  3. 内存屏障指令分编译器级别和CPU级别,内存屏障和CPU重排序没半点关系。
  4. CPU的厂家使用的协议和CPU具体实现不尽相同,JVM定义的4种内存屏障指令,在x86的机器上,其实只有一种有用,其他的都是空指令。
  5. JMM定义的”CPU缓存,主存“只是一种抽象,真正的CPU缓存实现,CPU之间在一定程度上是互相可见的。

我的思考

上面的例子有点复杂,我们再举个简单的例子:

1
2
3
4
5
6
7
8
void foo(void) {
a=1; //S1
b=1; //S2
}
void bar(void) {
while (b == 0) continue; //L1
assert(a == 1); //L2
}

执行的流程和上面的例子一样,我们把步骤拆成了4个,分别为S1,S2,L1,L2。

正常流程

正常流程应该是:
S1 > S2 > L1 > L2
也就是说,在执行L2的时候,a=1已经执行过了,所以这个断言是正确的。

内存可见性导致的问题

在JMM模型中,每个CPU都有自己的缓存,写入时,先写自己的缓存,然后再同步到主存中。
在这个例子中,如果还是S1 > S2 > L1 > L2的执行顺序
但是S1执行结束后,a其实存在于三个地方,这三个地方的可能值为:

  1. foo线程所在的CPU缓存中,这个地方a=1
  2. bar线程所在的CPU缓存中,这个地方a=0或者a=1
  3. 主存中,这个地方a=0或者a=1

同样的S2执行结束后,b也存在于三个地方。

如果在bar线程中,b的值为1,但是a的值还是0,那么断言还是失败的。

这个时候有人会告诉你使用volatile
被volatile修饰的变量,每次写入时,会实时同步到主存中,每次读取时,实时从主存中读取
这个就会导致S1和S2执行完之后,L1和L2步骤的a和b的值都是最新的。
没毛病,说得通对吧。

重排序导致的问题

CPU在执行中会对指令进行重排序
比如S1和S2这两个操作,在CPU看来没有任何数据依赖顺序,所以它可以乱序执行
这下执行顺序可能就变成S2 > L1 > L2 > S1
也会导致断言失败。
这个时候Volatile也会保证执行的时候不会导致重排序。
也没毛病。

内存屏障

Volatile的具体是怎么实现的呢?
实现就是插入内存屏障。
内存屏障是什么东西?
简单的说:保证内存屏障前的读写指令必须在屏障后的读写指令之前执行,通知被Volatile修饰的值,每次读取都从主存中读取,每次写入都同步写入主存(锁总线)。

总结

从这个例子中看到,其实重排序和内存可见性的问题都会导致程序产生和我们预期不一致的行为,
而Volatile恰好能解决这两个问题。

内存屏障底层指令

其实正常来说,一般的Java开发者能理解到上面的层次就行了。
但是我还想理解的更多,比如这个重排序其实是CPU级别的,我们的Volatile关键词,肯定会映射成汇编指令,那么是哪些汇编指令呢?

我们先来了解一下barrier()函数。

编译器重排序

对于指令重排序,我一直以为只有CPU才会进行重排序,其实编译器也会对我们的指令进行重排序。
举个例子:

1
2
3
4
5
6
int x, y, r;
void f()
{
x = r;
y = 1;
}

如果我们直接编译源文件:g++ -S test.cpp
会得到这样的汇编文件:

1
2
3
movl    r(%rip), %eax
movl %eax, x(%rip)
movl $1, y(%rip)

可以看到,这个结果并没有进行重排序

但是如果我们指定优化级别:g++ -O2 –S test.cpp
得到的汇编指令如下:

1
2
3
movl    r(%rip), %eax
movl $1, y(%rip)
movl %eax, x(%rip)

看,两个指令的顺序反了。
这也就是编译器的重排序。

那么怎么避免呢?
这个时候barrier()函数就派上用场了。

我们修改我们的代码:

1
2
3
4
5
6
7
int x, y, r;
void f()
{
x = r;
barrier();
y = 1;
}

这个时候我们再进行编译,会发现顺序并没有颠倒。

内存屏障

我们从内核的代码中找出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define barrier() __asm__ __volatile__("": : :"memory") 
#define mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)
#define rmb() alternative("lock; addl $0,0(%%esp)", "lfence", X86_FEATURE_XMM2)

#ifdef CONFIG_SMP
#define smp_mb() mb()
#define smp_rmb() rmb()
#define smp_wmb() wmb()
#define smp_read_barrier_depends() read_barrier_depends()
#define set_mb(var, value) do { (void) xchg(&var, value); } while (0)
#else
#define smp_mb() barrier()
#define smp_rmb() barrier()
#define smp_wmb() barrier()
#define smp_read_barrier_depends() do { } while(0)
#define set_mb(var, value) do { var = value; barrier(); } while (0)
#endif

别急,我们慢慢来看
内存屏障指令,大致有3个

  1. smp_mb
  2. smp_rmb
  3. smp_wmb

但是看这个#ifdef CONFGIG_SMP
SMP就是表示多核的意思。

内存屏障指令,在单核和多核的系统中的实现定义是不一样的

我们可以看到,如果计算机是单核的,那么其实所有的内存屏障指令都是编译器级别的,实际的实现都是barrier()函数,在CPU级别都是空操作。

我的疑惑

其实不对啊,既然CPU会进行重排序,那为什么单核中并没有使用任何CPU的指令避免重排序呢?

我们再回到那个例子:

1
2
3
4
5
6
7
8
void foo(void) {
a=1; //S1
b=1; //S2
}
void bar(void) {
while (b == 0) continue; //L1
assert(a == 1); //L2
}

假设这个程序是单核中执行的,也就是没有多核中的可见性的问题,但是CPU重排序的问题依然存在。
如果CPU进行重排序:
S2 > L2 > L2 > S1
那不是仍然会出问题吗?

黑人问号?

带着这个问题,我继续开始了我的资料搜寻。

内存一致性

主要内容来自高并发编程–多处理器编程中的一致性问题(上)
很多东西这个文章解释的很好,建议先读一读,有的我就直接略讲了

我产生上述疑惑的前提其实就是默认CPU会对指令进行重排序。
很多书中对Volatile也提到了这一点,问题源头都是CPU会对指令重排序。
这个时候我们可能会觉得CPU厂家不给力,把这个锅丢给了开发者去解决。

其实不是的。

那么为了保证不会出现这种超出预期的行为,我们就需要一种规则来约束这种行为不能出现。这个任务就是memory consistency需要保证的(这里指的是强一致性模型:SC/TSO, XC的memory consistency并不能保证这点)

CPU的理论中,其实有一系列协议约束CPU的执行不能出现上述行为。
也就是memory consistency,内存一致性。或者也叫Memory Model
中文资料关于这个话题确实很少被提到,这个知乎问答提到了哪儿可以去学习。
如何系统的学习 Memory Model?
其实这个话题也分理论与工业实现,就跟操作系统一样。

笔者了解的也不多,这里就简单提一下。
关于内存一致性的问题,其实和分布式的精髓略相似,有强弱之分,不同的CPU架构上实现的强弱程度不同。

Sequential Consistency

在理论上,不得不提一个人,Lamport,就是Paxos理论的那个教授。
他提出了Sequential Consistency,就是顺序一致性,硬件层面的一致性。

在解释SC的理论之前,还得了解Program OrderMemory Order

Program Order: 就是我们写的代码的顺序,这个是静态的也是每个CPU core各自拥有的。
Memory Order: 就是代码执行的顺序,这个是全局的,每个CPU core对共享内存的执行都会出现在Memory order中。
用<p 表示Program order的先于顺序,<m表示Memory order的先于顺序。

SC的形式化定义如下:

1
2
3
4
If L(a) <p L(b) ⇒ L(a) <m L(b) /* Load→Load */
If L(a) <p S(b) ⇒ L(a) <m S(b) /* Load→Store */
If S(a) <p S(b) ⇒ S(a) <m S(b) /* Store→Store */
If S(a) <p L(b) ⇒ S(a) <m L(b) /* Store→Load */

在SC的理论中,这4种关系不允许被Reorder。
好了,根据这个理论,我们再看一看上面的代码:

1
2
3
4
5
6
7
8
void foo(void) {
a=1; //S1
b=1; //S2
}
void bar(void) {
while (b == 0) continue; //L1
assert(a == 1); //L2
}

在foo函数中,a的Store在程序顺序中是大于b的Store的,所以a=1的MemoryOrder是必须要大于b=1的MemoryOrder的。

也就说,如果CPU实现了SC协议,那么其实S2 -> S1这个重排序是不允许的。

Total Store Order

当然理论归理论,实现不一定按照理论来。
前面提到了SC的理论,在SC理论的指导下,一切都是按照顺序来的,对CPU重排序的条件非常苛刻。

SC的问题:

SC严格定义了对于共享内存的load和store操作,loadload,storestore,loadstore,storeload四种执行顺序是不允许reorder的。当下CPU的执行速度已经甩DRAM(memory)好几个量级,如果每次store,load操作都从DRAM读取会拖慢CPU的执行速度,在这个极度压榨硬件性能的时代,是不能接受这种行为的。因此在x86的架构实现中引入了TSO。

简单说,就是CPU厂家觉得SC太严格,不利于性能提升,所以几乎没人用SC,而X86而言,他自己定义了一个叫Total Store Order的内存模型。

在讲TSO之前,在提一嘴前面提到的,内存一致性的协议有强弱之分,就像分布式协议中的强一致性,最终一致性一样。
SC显然是强一致性,但是TSO的一致性就略微弱与SC。

具体体现在哪儿呢:

TSO在CPU与memory之间引入了write buffer。CPU写入的时候先写入write buffer然后就返回了,这样就将cpu与memory之间的差距隐藏了。

引入了write buffer后,这里其实就是一个内存可见性的隐藏问题,在write buffer中的值,到memory中其实需要一段时间的,这个时间是不定的。

所以还是会导致一些其他的问题出现:

比如我们看这个例子:

1
2
3
4
5
6
7
8
void foo(void) {
x=1; //S1
r1=y; //L1
}
void bar(void) {
y=1; //S2
r2=x;//L2
}

还是上面这个例子,S1将x=1放到了core C1的write buffer中,S2将y=1放到了C2的write buffer中,那么在执行L1,L2的时候,r1与r2这时候从memory读到是0。这个是违背了SC的,但是这样的设计确实带来了性能的提升。

怎么解决这个问题呢?

可能你想到了,就是我们使用某种指令,让CPU去同步Flush这个write buffer中的值。
这个指令就是我们提到的内存屏障。

在详细介绍内存屏障的指令前,我们在TSO模型下,看看我们之前举的例子,到底是什么原因导致的:
还是前面的例子:

1
2
3
4
5
6
7
8
void foo(void) {
a=1; //S1
b=1; //S2
}
void bar(void) {
while (b == 0) continue; //L1
assert(a == 1); //L2
}

在TOS的引入了write buffer后,我们再来看看上面的例子还会出现问题吗?
如果a=1,b=1先后被写入write buffer,并没有写入memory。但是如果把write buffer中的值flush到内存,b=1这个可见性的时间 >= a=1的可见性。
所以如果bar中,读到b=1了,那么a肯定也已经读到等于1了。
就不会出现上面的问题。

这个时候,我们可以解答我的疑惑了
为什么单核的情况下,仅仅需要禁止编译器的重排序就行了?
答案就是在TSO模型下,在上面的例子中,CPU不会进行指令的重排序。

内存屏障指令

让我们再回到这个代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define barrier() __asm__ __volatile__("": : :"memory") 
#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)

#ifdef CONFIG_SMP
#define smp_mb() mb()
#define smp_rmb() rmb()
#define smp_wmb() wmb()
#define smp_read_barrier_depends() read_barrier_depends()
#define set_mb(var, value) do { (void) xchg(&var, value); } while (0)
#else
#define smp_mb() barrier()
#define smp_rmb() barrier()
#define smp_wmb() barrier()
#define smp_read_barrier_depends() do { } while(0)
#define set_mb(var, value) do { var = value; barrier(); } while (0)
#endif

常见的三种

x86/64系统架构提供了三种多核的内存屏障指令:(1) sfence; (2) lfence; (3) mfence

  1. sfence:在sfence指令前的写操作当必须在sfence指令后的写操作前完成。
  2. lfence:在lfence指令前的读操作当必须在lfence指令后的读操作前完成。
  3. mfence:在mfence指令前的读写操作当必须在mfence指令后的读写操作前完成。

其实总结起来就是读屏障,写屏障,读写屏障。

上述的是显式的会起到内存屏障作用的指令,但是还有许多指令带有异常的内存屏障的作用。

MMIO写屏障

Linux 内核有一个专门用于 MMIO 写的屏障:
mmiowb()
笔者也不熟悉这个的作用,后续再补上

隐藏的内存屏障

Linux 内核中一些锁或者调度函数暗含了内存屏障。

锁函数:

  • spin locks
  • R/W spin locks
  • mutexes
  • semaphores
  • R/W semaphores

中断禁止函数:
启动或禁止终端的函数的作用仅仅是作为编译器屏障,所以要使用内存或者 I/O 屏障 的场合,必须用别的函数。

SLEEP和WAKE-UP以及其它调度函数:
使用 SLEEP 和 WAKE-UP 函数时要改变 task 的状态标志,这需要使用合适的内存屏 障保证修改的顺序。

MESI缓存一致性

写不动了,缓存一致性的内容还是大家自己百度吧
其实简单点可以这么理解:

  1. JMM中的主存其实在实现上,包含了CPU的缓存
  2. JMM中的CPU的缓存在x86机器上可以理解为write buffer。

JMM

写到这儿,基本把开头的一些结论说清楚了,但是还有一个:
JVM定义的4种内存屏障指令,在x86的机器上,其实只有一种有用,其他的都是空指令。

我们先来看JMM中的定义,根据Store和Load的操作,JMM分成了4中:

  1. LoadLoad
  2. LoadStore
  3. StoreStore
  4. StoreLoad

这4中都是为了禁止重排序的
这里的Load就是从主存中获取值,Store就是把值同步写入主存。

按照读屏障,写屏障,读写屏障划分的话,和fence的对应关系如下:

  1. LoadLoad -> lfence
  2. LoadStore -> mfence
  3. StoreStore -> sfence
  4. StoreLoad -> mfence

当然了解这些还是不够的,我们还需要JMM对应了哪种CPU模型。
在x86中,我们除了内存,还了解到有write buffer的存在。
然而事实上,CPU的实现中,还有一个东西的存在叫invalidate queue

具体的演进与作用可以参照这篇文章:
内存屏障Memory Barrier: a Hardware View

StoreBuffer就是对应WriteBuffer
而Invalidate queue在x86的CPU上是不存在的。

再回到我们提到的例子:

1
2
3
4
5
6
7
8
void foo(void) {
x=1; //S1
r1=y; //S2
}
void bar(void) {
y=1; //L1
r2=x;//L2
}

在这个例子中,我们需要哪一种屏障呢?
就是StoreLoad屏障
按照TSO的协议解释,也就是我们读取y的值的之前,必须flush writebuffer。
这样,r1和r2就不会出现同时等于0的情况。

再具体的这个文章讲的很好:为什么在 x86 架构下只有 StoreLoad 屏障是有效指令?

参考

cpu-reordering-what-is-actually-being-reordered
什么是内存屏障(Memory Barriers)
Linux内核中的内存屏障
内存屏障
为什么我们需要内存屏障?
《大话处理器》Cache一致性协议之MESI
x86 TSO: A Programmer’s Model for x86 Multiprocessors
If I don’t use fences, how long could it take a core to see another core’s writes?
深入理解内存屏障
C和C++中的volatile、内存屏障和CPU缓存一致性协议MESI
从 Java 内存模型看内部细节
既然CPU有缓存一致性协议(MESI),为什么JMM还需要volatile关键字?

Welcome to my other publishing channels