LINUX内核内存屏障
=================
LINUX内核内存屏障
=================
By: David Howells dhowells@redhat.com
Paul E. McKenney paulmck@linux.vnet.ibm.com
译: kouu kouucocu@126.com
出处: Linux内核文档 -- Documentation/memory-barriers.txt
文件夹:
(*) 内存訪问抽象模型.
- 操作设备.
- 保证.
(*) 什么是内存屏障?
- 各式各样的内存屏障.
- 关于内存屏障, 不能假定什么?
- 数据依赖屏障.
- 控制依赖.
- SMP内存屏障的配对使用.
- 内存屏障举例.
- 读内存屏障与内存预取.
(*) 内核中显式的内存屏障.
- 编译优化屏障.
- CPU内存屏障.
- MMIO写屏障.
(*) 内核中隐式的内存屏障.
- 锁相关函数.
- 禁止中断函数.
- 睡眠唤醒函数.
- 其它函数.
(*) 跨CPU的锁的屏障作用.
- 锁与内存訪问.
- 锁与IO訪问.
(*) 什么地方须要内存屏障?
- 处理器间交互.
- 原子操作.
- 訪问设备.
- 中断.
(*) 内核中I/O屏障的作用.
(*) 最小限度有序的假想模型.
(*) CPU cache的影响.
- Cache一致性.
- Cache一致性与DMA.
- Cache一致性与MMIO.
(*) CPU所能做到的.
- 特别值得一提的Alpha处理器.
(*) 使用演示样例.
- 环型缓冲区.
(*) 引用.
================
内存訪问抽象模型
================
考虑例如以下抽象系统模型:
: :
: :
: :
+-------+ : +--------+ : +-------+
| | : | | : | |
| | : | | : | |
| CPU 1 |<----->| 内存 |<----->| CPU 2 |
| | : | | : | |
| | : | | : | |
+-------+ : +--------+ : +-------+
^ : ^ : ^
| : | : |
| : | : |
| : v : |
| : +--------+ : |
| : | | : |
| : | | : |
+---------->| 设备 |<----------+
: | | :
: | | :
: +--------+ :
: :
如果每一个CPU都分别执行着一个会触发内存訪问操作的程序. 对于这样一个CPU, 其内存訪问
顺序是很松散的, 在保证程序上下文逻辑关系的前提下, CPU能够按它所喜欢的顺序来执
行内存操作. 类似的, 编译器也能够将它输出的指令安排成不论什么它喜欢的顺序, 仅仅要保证不
影响程序表面的运行逻辑.
(译注:
内存屏障是为应付内存訪问操作的乱序运行而生的. 那么, 内存訪问为什么会乱序呢? 这里
先简要介绍一下:
如今的CPU一般採用流水线来运行指令. 一个指令的运行被分成: 取指, 译码, 訪存, 运行,
写回, 等若干个阶段.
指令流水线并非串行化的, 并不会由于一个耗时非常长的指令在"运行"阶段呆非常长时间, 而
导致兴许的指令都卡在"运行"之前的阶段上.
相反, 流水线中的多个指令是能够同一时候处于一个阶段的, 仅仅要CPU内部对应的处理部件未被
占满. 比方说CPU有一个加法器和一个除法器, 那么一条加法指令和一条除法指令就可能同
时处于"运行"阶段, 而两条加法指令在"运行"阶段就仅仅能串行工作.
这样一来, 乱序可能就产生了. 比方一条加法指令出如今一条除法指令的后面, 可是因为除
法的运行时间非常长, 在它运行完之前, 加法可能先运行完了. 再比方两条訪存指令, 可能由
于第二条指令命中了cache(或其它原因)而导致它先于第一条指令完毕.
普通情况下, 指令乱序并非CPU在运行指令之前刻意去调整顺序. CPU总是顺序的去内存里
面取指令, 然后将其顺序的放入指令流水线. 可是指令运行时的各种条件, 指令与指令之间
的相互影响, 可能导致顺序放入流水线的指令, 终于乱序运行完毕. 这就是所谓的"顺序流
入, 乱序流出".
指令流水线除了在资源不足的情况下会卡住之外(如前所述的一个加法器应付两条加法指令)
, 指令之间的相关性才是导致流水线堵塞的主要原因.
下文中也会多次提到, CPU的乱序运行并非随意的乱序, 而必须保证上下文依赖逻辑的正
确性. 比方: a++; b=f(a); 因为b=f(a)这条指令依赖于第一条指令(a++)的运行结果, 所以
b=f(a)将在"运行"阶段之前被堵塞, 直到a++的运行结果被生成出来.
假设两条像这样有依赖关系的指令挨得非常近, 后一条指令必然会由于等待前一条运行的结果
, 而在流水线中堵塞非常久. 而编译器的乱序, 作为编译优化的一种手段, 则试图通过指令重
排将这种两条指令拉开距离, 以至于后一条指令运行的时候前一条指令结果已经得到了,
那么也就不再须要堵塞等待了.
相比于CPU的乱序, 编译器的乱序才是真正对指令顺序做了调整. 可是编译器的乱序也必须
保证程序上下文的依赖逻辑.
因为指令运行存在这种乱序, 那么自然, 由指令运行而引发的内存訪问势必也可能乱序.
)
在上面的图示中, 一个CPU运行内存操作所产生的影响, 一直要到该操作穿越该CPU与系统中
其它部分的界面(见图中的虚线)之后, 才干被其它部分所感知.
举例来说, 考虑例如以下的操作序列:
CPU 1 CPU 2
=============== ===============
{ A == 1; B == 2 }
A = 3; x = A;
B = 4; y = B;
这一组訪问指令在内存系统(见上图的中间部分)上生效的顺序, 能够有24种不同的组合:
STORE A=3, STORE B=4, x=LOAD A->3, y=LOAD B->4
STORE A=3, STORE B=4, y=LOAD B->4, x=LOAD A->3
STORE A=3, x=LOAD A->3, STORE B=4, y=LOAD B->4
STORE A=3, x=LOAD A->3, y=LOAD B->2, STORE B=4
STORE A=3, y=LOAD B->2, STORE B=4, x=LOAD A->3
STORE A=3, y=LOAD B->2, x=LOAD A->3, STORE B=4
STORE B=4, STORE A=3, x=LOAD A->3, y=LOAD B->4
STORE B=4, ...
...
然后这就产生四种不同组合的结果值:
x == 1, y == 2
x == 1, y == 4
x == 3, y == 2
x == 3, y == 4
甚至于, 一个CPU在内存系统上提交的STORE操作还可能不会以同样的顺序被其它CPU所运行
的LOAD操作所感知.
进一步举例说明, 考虑例如以下的操作序列:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4; Q = P;
P = &B D = *Q;
这里有一处明显的数据依赖, 由于在CPU2上, LOAD到D里面的值依赖于从P获取到的地址. 在
操作序列的最后, 以下的几种结果都是有可能出现的:
(Q == &A) 且 (D == 1)
(Q == &B) 且 (D == 2)
(Q == &B) 且 (D == 4)
注意, CPU2决不会将C的值LOAD到D, 由于CPU保证在将P的值装载到Q之后才会运行对*Q的
LOAD操作(译注: 由于存在数据依赖).
操作设备
--------
对于一些设备, 其控制寄存器被映射到一组内存地址集合上, 而这些控制寄存器被訪问的顺
序是至关重要的. 如果, 一个以太网卡拥有一些内部寄存器, 通过一个地址port寄存器(A)
和一个数据port寄存器(D)来訪问它们. 要读取编号为5的内部寄存器, 可能使用例如以下代码:
*A = 5;
x = *D;
可是这可能会表现为下面两个序列之中的一个(译注: 由于从程序表面看, A和D是不存在依赖的):
STORE *A = 5, x = LOAD *D
x = LOAD *D, STORE *A = 5
当中的另外一种差点儿肯定会导致错误, 由于它在读取寄存器之后才设置寄存器的编号.
保证
----
对于一个CPU, 它最低限度会提供例如以下的保证:
(*) 对于一个CPU, 在它上面出现的有上下文依赖关系的内存訪问将被按顺序运行. 这意味
着:
Q = P; D = *Q;
CPU会顺序运行下面訪存:
Q = LOAD P, D = LOAD *Q
而且总是按这种顺序.
(*) 对于一个CPU, 重叠的LOAD和STORE操作将被按顺序运行. 这意味着:
a = *X; *X = b;
CPU仅仅会按下面顺序运行訪存:
a = LOAD *X, STORE *X = b
相同, 对于:
*X = c; d = *X;
CPU仅仅会按下面顺序运行訪存:
STORE *X = c, d = LOAD *X
(假设LOAD和STORE的目标指向同一块内存地址, 则觉得是重叠).
另一些事情是必须被假定或者必须不被假定的:
(*) 必须不能假定无关的LOAD和STORE会按给定的顺序被运行. 这意味着:
X = *A; Y = *B; *D = Z;
可能会得到例如以下几种运行序列之中的一个:
X = LOAD *A, Y = LOAD *B, STORE *D = Z
X = LOAD *A, STORE *D = Z, Y = LOAD *B
Y = LOAD *B, X = LOAD *A, STORE *D = Z
Y = LOAD *B, STORE *D = Z, X = LOAD *A
STORE *D = Z, X = LOAD *A, Y = LOAD *B
STORE *D = Z, Y = LOAD *B, X = LOAD *A
(*) 必须假定重叠内存訪问可能被合并或丢弃. 这意味着:
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) };
相同, 对于:
*A = X; Y = *A;
可能会得到例如以下几种运行序列之中的一个:
STORE *A = X; Y = LOAD *A;
STORE *A = Y = X;
===============
什么是内存屏障?
===============
正如上面所说, 无关的内存操作会被按随机顺序有效的得到运行, 可是在CPU与CPU交互时或
CPU与IO设备交互时, 这可能会成为问题. 我们须要一些手段来干预编译器和CPU, 使其限制
指令顺序.
内存屏障就是这种干预手段. 他们能保证处于内存屏障两边的内存操作满足部分有序. (
译注: 这里"部分有序"的意思是, 内存屏障之前的操作都会先于屏障之后的操作, 可是假设
几个操作出如今屏障的同一边, 则不保证它们的顺序. 这一点下文将多次提到.)
这种强制措施是很重要的, 由于系统中的CPU和其它设备能够使用各种各样的策略来提
高性能, 包含对内存操作的乱序, 延迟和合并运行; 预取; 投机性的分支预測和各种缓存.
内存屏障用于禁用或抑制这些策略, 使代码可以清楚的控制多个CPU和/或设备的交互.
各式各样的内存屏障
------------------
内存屏障有四种基本类型:
(1) 写(STORE)内存屏障.
写内存屏障提供这种保证: 全部出如今屏障之前的STORE操作都将先于全部出如今屏
障之后的STORE操作被系统中的其它组件所感知.
写屏障仅保证针对STORE操作的部分有序; 不要求对LOAD操作产生影响.
随着时间的推移, 一个CPU提交的STORE操作序列将被存储系统所感知. 全部在写屏障
之前的STORE操作将先于全部在写屏障之后的STORE操作出如今被感知的序列中.
[!] 注意, 写屏障一般须要与读屏障或数据依赖屏障配对使用; 參阅"SMP内存屏障配
对"章节. (译注: 由于写屏障仅仅保证自己提交的顺序, 而无法干预其它代码读内
存的顺序. 所以配对使用非常重要. 其它类型的屏障亦是同理.)
(2) 数据依赖屏障.
数据依赖屏障是读屏障的弱化版本号. 如果有两个LOAD操作的场景, 当中第二个LOAD操
作的结果依赖于第一个操作(比方, 第一个LOAD获取地址, 而第二个LOAD使用该地址去
取数据), 数据依赖屏障确保在第一个LOAD获取的地址被用于訪问之前, 第二个LOAD的
目标内存已经更新.
(译注: 由于第二个LOAD要使用第一个LOAD的结果来作为LOAD的目标, 这里存在着数
据依赖. 由前面的"保证"章节可知, 第一个LOAD必然会在第二个LOAD之前运行, 不需
要使用读屏障来保证顺序, 仅仅须要使用数据依赖屏障来保证内存已刷新.)
数据依赖屏障仅保证针对相互依赖的LOAD操作的部分有序; 不要求对STORE操作,
独立的LOAD操作, 或重叠的LOAD操作产生影响.
正如(1)中所提到的, 在一个CPU看来, 系统中的其它CPU提交到内存系统的STORE操作
序列在某一时刻能够被其感知到. 而在该CPU上触发的数据依赖屏障将保证, 对于在屏
障之前发生的LOAD操作, 假设一个LOAD操作的目标被其它CPU的STORE操作所改动, 那
么在屏障完毕之时, 这个相应的STORE操作之前的全部STORE操作所产生的影响, 将被
数据依赖屏障之后运行的LOAD操作所感知.
參阅"内存屏障举例"章节所描写叙述的时序图.
[!] 注意, 对第一个LOAD的依赖的确是一个数据依赖而不是控制依赖. 而假设第二个
LOAD的地址依赖于第一个LOAD, 但并非通过实际载入的地址本身这种依赖条
件, 那么这就是控制依赖, 须要一个完整的读屏障或更强的屏障. 參阅"控制依
赖"相关章节.
[!] 注意, 数据依赖屏障一般要跟写屏障配对使用; 參阅"SMP内存屏障的配对使用"章
节.
(3) 读(LOAD)内存屏障.
读屏障包括数据依赖屏障的功能, 而且保证全部出如今屏障之前的LOAD操作都将先于
全部出如今屏障之后的LOAD操作被系统中的其它组件所感知.
读屏障仅保证针对LOAD操作的部分有序; 不要求对STORE操作产生影响.
读内存屏障隐含了数据依赖屏障, 因此能够用于替代它们.
[!] 注意, 读屏障一般要跟写屏障配对使用; 參阅"SMP内存屏障的配对使用"章节.
(4) 通用内存屏障.
通用内存屏障保证全部出如今屏障之前的LOAD和STORE操作都将先于全部出如今屏障
之后的LOAD和STORE操作被系统中的其它组件所感知.
通用内存屏障是针对LOAD和STORE操作的部分有序.
通用内存屏障隐含了读屏障和写屏障, 因此能够用于替代它们.
内存屏障还有两种隐式类型:
(5) LOCK操作.
它的作用相当于一个单向渗透屏障. 它保证全部出如今LOCK之后的内存操作都将在
LOCK操作被系统中的其它组件所感知之后才干发生.
出如今LOCK之前的内存操作可能在LOCK完毕之后才发生.
LOCK操作总是跟UNLOCK操作配对出现的.
(6) UNLOCK操作.
它的作用也相当于一个单向渗透屏障. 它保证全部出如今UNLOCK之前的内存操作都将
在UNLOCK操作被系统中的其它组件所感知之前发生.
出如今UNLOCK之后的内存操作可能在UNLOCK完毕之前就发生了.
须要保证LOCK和UNLOCK操作严格依照相互影响的正确顺序出现.
(译注: LOCK和UNLOCK的这样的单向屏障作用, 确保临界区内的訪存操作不能跑到临界区
外, 否则就起不到"保护"作用了.)
使用LOCK和UNLOCK之后, 一般就不再须要其它内存屏障了(可是注意"MMIO写屏障"章节
中所提到的例外).
仅仅有在存在多CPU交互或CPU与设备交互的情况下才可能须要用到内存屏障. 假设能够确保某
段代码中不存在这种交互, 那么这段代码就不须要使用内存屏障. (译注: CPU乱序运行指
令, 相同会导致寄存器的存取顺序被打乱, 可是为什么不须要寄存器屏障呢?
就是由于寄存
器是CPU私有的, 不存在跟其它CPU或设备的交互.)
注意, 对于前面提到的最低限度保证. 不同的体系结构可能提供很多其它的保证, 可是在特定体
系结构的代码之外, 不能依赖于这些额外的保证.
关于内存屏障, 不能假定什么?
---------------------------
Linux内核的内存屏障不保证以下这些事情:
(*) 在内存屏障之前出现的内存訪问不保证在内存屏障指令完毕之前完毕; 内存屏障相当
于在该CPU的訪问队列中画一条线, 使得相关訪存类型的请求不能相互跨越. (译注:
用于实现内存屏障的指令, 其本身并不作为參考对象, 其两边的訪存操作才被当作參
考对象. 所以屏障指令运行完毕并不表示出如今屏障之前的訪存操作已经完毕. 而如
果屏障之后的某一个訪存操作已经完毕, 则屏障之前的全部訪存操作必然都已经完毕
了.)
(*) 在一个CPU上运行的内存屏障不保证会直接影响其它系统中的CPU或硬件设备. 仅仅会间
接影响到第二个CPU感知第一个CPU产生訪存效果的顺序, 只是请看下一点:
(*) 不能保证一个CPU可以按顺序看到还有一个CPU的訪存效果, 即使还有一个CPU使用了内存屏
障, 除非这个CPU也使用了与之配对的内存屏障(參阅"SMP内存屏障的配对使用"章节).
(*) 不保证一些与CPU相关的硬件不会乱序訪存. CPU cache一致性机构会在CPU之间传播内
存屏障所带来的间接影响, 可是可能不是按顺序的.
[*] 很多其它关于总线主控DMA和一致性的问题请參阅:
Documentation/PCI/pci.txt
Documentation/PCI/PCI-DMA-mapping.txt
Documentation/DMA-API.txt
数据依赖屏障
------------
数据依赖屏障的使用需求有点微妙, 并不总是非常明显就能看出须要他们. 为了说明这一点,
考虑例如以下的操作序列:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<写屏障>
P = &B
Q = P;
D = *Q;
这里有明显的数据依赖, 在序列运行完之后, Q的值一定是&A和&B之中的一个, 也就是:
(Q == &A) 那么 (D == 1)
(Q == &B) 那么 (D == 4)
可是! CPU 2可能在看到P被更新之后, 才看到B被更新, 这就导致以下的情况:
(Q == &B) 且 (D == 2) ?
?
?
?
尽管这看起来似乎是一个一致性错误或逻辑关系错误, 但事实上不是, 而且在一些真实的CPU
中就能看到这种行为(就比方DEC Alpha).
为了解决问题, 必须在取地址和取数据之间插入一个数据依赖或更强的屏障:
CPU 1 CPU 2
=============== ===============
{ A == 1, B == 2, C = 3, P == &A, Q == &C }
B = 4;
<写屏障>
P = &B
Q = P;
<数据依赖屏障>
D = *Q;
这将强制终于结果是前两种情况之中的一个, 而避免出现第三种情况.
[!] 注意, 这样的很违反直觉的情况最easy出如今cache分列的机器上, 比方, 一个cache组
处理偶数号的cache行, 还有一个cache组处理奇数号的cache行. P指针可能存储在奇数号
的cache行中, 而B的值可能存储在偶数号的cache行中. 这样一来, 假设运行读操作的
CPU的偶数号cache组很繁忙, 而奇数号cache组空暇, 它就可能看到P已被更新成新值
(&B), 而B还是旧值(2).
还有一个可能须要数据依赖屏障的样例是, 从内存读取一个数值, 用于计算数组的訪问偏移:
CPU 1 CPU 2
=============== ===============
{ M[0] == 1, M[1] == 2, M[3] = 3, P == 0, Q == 3 }
M[1] = 4;
<写屏障>
P = 1
Q = P;
<数据依赖屏障>
D = M[Q];
数据依赖屏障对于RCU很重要, 举例来说. 參阅include/linux/rcupdate.h文件里的
rcu_dereference()函数. 这个函数使得当前RCU指针指向的对象被替换成新的对象时, 不会
发生新对象尚未初始化完毕的情况. (译注: 更新RCU对象时, 一般步骤是: 1-为新对象分配
空间; 2-初始化新对象; 3-调用rcu_dereference()函数, 将对象指针指到新的对象上, 这
就意味着新的对象已生效. 这个过程中假设出现乱序訪存, 可能导致对象指针的更新发生在
新对象初始化完毕之前. 也就是说, 新对象尚未初始化完毕就已经生效了. 那么别的CPU就
可能引用到一个尚未初始化完毕的新对象, 从而出现错误.)
更详尽的样例请參阅"Cache一致性"章节.
控制依赖
--------
控制依赖须要使用一个完整的读内存屏障, 简单的数据依赖屏障不能使其正确工作. 考虑
以下的代码:
q = &a;
if (p)
q = &b;
<数据依赖屏障>
x = *q;
这段代码可能达不到预期的效果, 由于这里事实上并非数据依赖, 而是控制依赖, CPU可能
试图通过提前预測结果而对"if (p)"进行短路. 在这种情况下, 须要的是:
q = &a;
if (p)
q = &b;
<读屏障>
x = *q;
(译注:
比如:
CPU 1 CPU 2
=============== ===============
{ a == 1, b == 2, p == 0}
a = 3;
b = 4;
<写屏障>
p = 1;
q = &a;
if (p)
q = &b;
<数据依赖屏障>
x = *q;
CPU 1上的写屏障是为了保证这种逻辑: 假设p == 1, 那么必然有a == 3 && b == 4.
可是到了CPU 2, 可能p的值已更新(==1), 而a和b的值未更新, 那么这时数据依赖屏障能够
起作用, 确保x = *q时a和b的值更新. 由于从代码逻辑上说, q跟a或b是有所依赖的, 数据
依赖屏障能保证这些有依赖关系的值都已更新.
然而, 换一个写法:
CPU 1 CPU 2
=============== ===============
{ a == 1, b == 2, p == 0}
p = 1;
<写屏障>
a = 3;
b = 4;
q = &a;
if (p)
q = &b;
<读屏障>
x = *q;
CPU 1上的写屏障是为了保证这种逻辑: 假设a == 3 || b == 4, 那么必然有p == 1.
可是到了CPU 2, 可能a或b的值已更新, 而p的值未更新. 那么这时使用数据依赖屏障就不能
保证p的更新. 由于从代码逻辑上说, p跟不论什么人都没有依赖关系. 这时必须使用读屏障, 以
确保x = *q之前, p被更新.
原文中"短路"的意思就是, 因为p没有数据依赖关系, CPU能够早早获得它的值, 而不必考虑
更新.)
SMP内存屏障的配对使用
---------------------
在处理CPU与CPU的交互时, 相应类型的内存屏障总是应该配对使用. 缺乏适当配对的使用基
本上能够肯定是错误的.
一个写屏障总是与一个数据依赖屏障或读屏障相配对, 尽管通用屏障也可行. 类似的, 一个
读屏障或数据依赖屏障也总是与一个写屏障相配对, 虽然一个通用屏障也相同可行:
CPU 1 CPU 2
=============== ===============
a = 1;
<写屏障>
b = 2; x = b;
<读屏障>
y = a;
或:
CPU 1 CPU 2
=============== ===============
a = 1;
<写屏障>
b = &a; x = b;
<数据依赖屏障>
y = *x;
基本上, 读屏障总是须要用在这些地方的, 虽然能够使用"弱"类型.
[!] 注意, 在写屏障之前出现的STORE操作通常总是期望匹配读屏障或数据依赖屏障之后出
现的LOAD操作, 反之亦然:
CPU 1 CPU 2
=============== ===============
a = 1; }---- --->{ v = c
b = 2; } \ / { w = d
<写屏障> \ <读屏障>
c = 3; } / \ { x = a;
d = 4; }---- --->{ y = b;
内存屏障举例
------------
首先, 写屏障用作部分有序的STORE操作. 考虑例如以下的操作序列:
CPU 1
=======================
STORE A = 1
STORE B = 2
STORE C = 3
<写屏障>
STORE D = 4
STORE E = 5
这个操作序列会按顺序被提交到内存一致性系统, 而系统中的其它组件可能看到
{ STORE A, STORE B, STORE C }的组合出如今{ STORE D, STORE E }的组合之前, 而组合
内部可能乱序:
+-------+ : :
| | +------+
| |------>| C=3 | } /\
| | : +------+ }----- \ -----> 操作被系统中的其它
| | : | A=1 | } / 组件所感知
| | : +------+ }
| CPU 1 | : | B=2 | }
| | +------+ }
| | wwwwwwwwwwwwwwww } <--- 在这一时刻, 写屏障要求在它之
| | +------+ } 前出现的STORE操作都先于在它
| | : | E=5 | } 之后出现的STORE操作被提交
| | : +------+ }
| |------>| D=4 | }
| | +------+
+-------+ : :
|
| CPU 1发起的STORE操作被提交到内存系统的顺序
|
V
其次, 数据依赖屏障用作部分有序的数据依赖LOAD操作. 考虑例如以下的操作序列:
CPU 1 CPU 2
======================= =======================
{ B = 7; X = 9; Y = 8; C = &Y }
STORE A = 1
STORE B = 2
<写屏障>
STORE C = &B LOAD X
STORE D = 4 LOAD C (得到&B)
LOAD *C (读取B)
没有干预的话, CPU 1的操作被CPU 2感知到的顺序是随机的, 虽然CPU 1运行了写屏障:
+-------+ : : : :
| | +------+ +-------+ | CPU 2所示
| |------>| B=2 |----- --->| Y->8 | | 更新序列
| | : +------+ \ +-------+ |
| CPU 1 | : | A=1 | \ --->| C->&Y | V
| | +------+ | +-------+
| | wwwwwwwwwwwwwwww | : :
| | +------+ | : :
| | : | C=&B |--- | : : +-------+
| | : +------+ \ | +-------+ | |
| |------>| D=4 | ----------->| C->&B |------>| |
| | +------+ | +-------+ | |
+-------+ : : | : : | |
| : : | |
| : : | CPU 2 |
| +-------+ | |
对B的取值显然不对 ---> | | B->7 |------>| |
| +-------+ | |
| : : | |
| +-------+ | |
对X的LOAD延误了B的 ---> \ | X->9 |------>| |
一致性更新 \ +-------+ | |
----->| B->2 | +-------+
+-------+
: :
在上面的样例中, CPU 2看到的B的值是7, 虽然对*C(值应该是B)的LOAD发生在对C的LOAD之
后.
可是, 如果一个数据依赖屏障被放到CPU 2的LOAD C和LOAD *C(如果值是B)之间:
CPU 1 CPU 2
======================= =======================
{ B = 7; X = 9; Y = 8; C = &Y }
STORE A = 1
STORE B = 2
<写屏障>
STORE C = &B LOAD X
STORE D = 4 LOAD C (获得&B)
<数据依赖屏障>
LOAD *C (读取B)
那么以下的情况将会发生:
+-------+ : : : :
| | +------+ +-------+
| |------>| B=2 |----- --->| Y->8 |
| | : +------+ \ +-------+
| CPU 1 | : | A=1 | \ --->| C->&Y |
| | +------+ | +-------+
| | wwwwwwwwwwwwwwww | : :
| | +------+ | : :
| | : | C=&B |--- | : : +-------+
| | : +------+ \ | +-------+ | |
| |------>| D=4 | ----------->| C->&B |------>| |
| | +------+ | +-------+ | |
+-------+ : : | : : | |
| : : | |
| : : | CPU 2 |
| +-------+ | |
| | X->9 |------>| |
| +-------+ | |
确保STORE C之前的影响 ---> \ ddddddddddddddddd | |
都被兴许的LOAD操作感 \ +-------+ | |
知到 ----->| B->2 |------>| |
+-------+ | |
: : +-------+
第三, 读屏障用作部分有序的LOAD操作. 考虑例如以下事件序列:
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
STORE A=1
<写屏障>
STORE B=2
LOAD B
LOAD A
没有干预的话, CPU 1的操作被CPU 2感知到的顺序是随机的, 虽然CPU 1运行了写屏障:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| | A->0 |------>| |
| +-------+ | |
| : : +-------+
\ : :
\ +-------+
---->| A->1 |
+-------+
: :
可是, 假设一个读屏障被放到CPU 2的LOAD B和LOAD A之间:
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
STORE A=1
<写屏障>
STORE B=2
LOAD B
<读屏障>
LOAD A
那么CPU 1所施加的部分有序将正确的被CPU 2所感知:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| : : | |
| : : | |
在这一时刻, 读屏障导致 ----> \ rrrrrrrrrrrrrrrrr | |
STORE B之前的影响都被 \ +-------+ | |
CPU 2所感知 ---->| A->1 |------>| |
+-------+ | |
: : +-------+
为了更全面地说明这一点, 考虑一下假设代码在读屏障的两边都有一个LOAD A的话, 会发生
什么:
CPU 1 CPU 2
======================= =======================
{ A = 0, B = 9 }
STORE A=1
<写屏障>
STORE B=2
LOAD B
LOAD A [第一次LOAD A]
<读屏障>
LOAD A [第二次LOAD A]
虽然两次LOAD A都发生在LOAD B之后, 它们也可能得到不同的值:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| : : | |
| : : | |
| +-------+ | |
| | A->0 |------>| 一次 |
| +-------+ | |
在这一时刻, 读屏障导致 ----> \ rrrrrrrrrrrrrrrrr | |
STORE B之前的影响都被 \ +-------+ | |
CPU 2所感知 ---->| A->1 |------>| 二次 |
+-------+ | |
: : +-------+
可是也可能CPU 2在读屏障结束之前就感知到CPU 1对A的更新:
+-------+ : : : :
| | +------+ +-------+
| |------>| A=1 |------ --->| A->0 |
| | +------+ \ +-------+
| CPU 1 | wwwwwwwwwwwwwwww \ --->| B->9 |
| | +------+ | +-------+
| |------>| B=2 |--- | : :
| | +------+ \ | : : +-------+
+-------+ : : \ | +-------+ | |
---------->| B->2 |------>| |
| +-------+ | CPU 2 |
| : : | |
\ : : | |
\ +-------+ | |
---->| A->1 |------>| 一次 |
+-------+ | |
rrrrrrrrrrrrrrrrr | |
+-------+ | |
| A->1 |------>| 二次 |
+-------+ | |
: : +-------+
这里仅仅保证, 假设LOAD B得到的值是2的话, 第二个LOAD A能得到的值是1. 对于第一个
LOAD A是不存在这种保证的; 它可能得到A的值是0或是1.
读内存屏障与内存预取
--------------------
很多CPU会对LOAD操作进行预取: 作为性能优化的一种手段, 当CPU发现它们将要从内存LOAD
一个数据时, 它们会寻找一个不须要使用总线来进行其它LOAD操作的时机, 用于LOAD这个数
据 - 虽然他们的指令运行流程实际上还没有到达该处LOAD的地方. 实际上, 这可能使得某
些LOAD指令可以马上完毕, 由于CPU已经预取到了所须要LOAD的值.
这也可能出现CPU实际上用不到这个预取的值的情况 - 可能由于一个分支而避开了这次LOAD
- 在这种情况下, CPU能够丢弃这个值或者干脆就缓存它以备兴许使用.
考虑例如以下场景:
CPU 1 CPU 2
======================= =======================
LOAD B
DIVIDE } 除法指令通常消耗
DIVIDE } 非常长的运行时间
LOAD A
这可能将表现为例如以下情况:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :DIVIDE | |
+-------+ | |
CPU在运行除法指令 ---> -->| A->0 |~~~~ | |
的同一时候, 预取A +-------+ ~ | |
(译注: 此时总线空暇) : : ~ | |
: :DIVIDE | |
: : ~ | |
一旦除法结束, --> : : ~-->| |
CPU能立即使 : : | |
LOAD指令生效 : : +-------+
假设在第二个LOAD之前放一个读屏障或数据依赖屏障:
CPU 1 CPU 2
======================= =======================
LOAD B
DIVIDE
DIVIDE
<读屏障>
LOAD A
这在一定程度上将迫使预取所获得的值, 依据屏障的类型而被又一次考虑. 假设没有新的更新
操作作用到已经被预取的内存地址, 则预取到的值就会被使用:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :DIVIDE | |
+-------+ | |
CPU在运行除法指令 ---> -->| A->0 |~~~~ | |
的同一时候, 预取A +-------+ ~ | |
: : ~ | |
: :DIVIDE | |
: : ~ | |
: : ~ | |
rrrrrrrrrrrrrrrr~ | |
: : ~ | |
: : ~-->| |
: : | |
: : +-------+
可是, 假设存在一个来自于其它CPU的更新或失效, 那么预取将被取消, 而且又一次加载值:
: : +-------+
+-------+ | |
--->| B->2 |------>| |
+-------+ | CPU 2 |
: :DIVIDE | |
+-------+ | |
CPU在运行除法指令 ---> -->| A->0 |~~~~ | |
的同一时候, 预取A +-------+ ~ | |
: : ~ | |
: :DIVIDE | |
: : ~ | |
: : ~ | |
rrrrrrrrrrrrrrrrr | |
+-------+ | |
预取被丢弃, 而且更 --> -->| A->1 |------>| |
新后的值被又一次获取 +-------+ | |
: : +-------+
====================
内核中显式的内存屏障
====================
linux内核拥有各式各样的屏障, 作用在不同层次上:
(*) 编译优化屏障.
(*) CPU内存屏障.
(*) MMIO写屏障.
编译优化屏障
------------
Linux内核有一个显式的编译器屏障函数, 可以防止编译器优化将訪存操作从它的任一側移
到还有一側:
barrier();
这是一个通用屏障 - 弱类型的编译优化屏障并不存在.
编译优化屏障并不直接作用到CPU, CPU依旧能够按其意愿乱序运行代码.
(译注:
既然编译优化屏障并不能限制CPU的乱序訪存, 那么单纯的编译优化屏障能起到什么作用呢?
以内核中的preempt_disable宏为例:
#define preempt_disable() \
do { \
inc_preempt_count(); \
barrier(); \
} while (0)
preempt_disable()和相应的preempt_enable()之间的代码是禁止内核抢占的, 通过对当前
进程的preempt_count进行++, 以标识进入禁止抢占状态(preempt_count==0时可抢占). 这
里在对preempt_count自增之后, 使用了编译优化屏障.
假设不使用屏障, 本该在不可抢占状态下运行的指令可能被重排到preempt_count++之前(因
为这些指令基本上不会对preempt_count有依赖). 而抢占可能是由中断处理程序来触发的,
在那些应该在不可抢占状态下运行的指令被运行之后, preempt_count++之前, 可能发生中
断. 中断来了, preempt_count的值还是0, 于是进程可能会被错误的抢占掉.
究其原因, 是由于编译器看到的上下文依赖逻辑是静态的, 它不知道这段代码跟中断处理程
序还存在依赖关系, 所以没法限制自己的乱序行为. 所以, 这里的编译优化屏障是必要的.
可是, 只使用编译优化屏障就足够了么? 是的, 由于preempt_count这个变量是属于当前
进程的, 仅会被当前CPU訪问.
CPU乱序可能导致后面应该在禁止抢占状态下运行的指令先于preempt_disable()运行完, 但
是没有关系, 由于前面也提到过, CPU是"顺序流入, 乱序流出"的, 就算后面的指令先运行
完, preempt_disable()也必然已经存在于流水线中了, CPU知道preempt_count变量将要被
改动. 而触发抢占的代码肯定会检查preempt_count是否为0, 而这里的检查又将依赖于
preempt_disable()的改动结果, 必然在preempt_disable()完毕之后才会进行.
究其原因, 是由于CPU看到的上下文依赖逻辑是动态的, 它无论指令是来自于普通的处理流
程, 还是来自于中断处理程序, 仅仅要指令存在依赖, 它都能发现. 所以, 对于类似这种仅仅
被一个CPU所关注的内存訪问, CPU的乱序訪存并不会存在问题.
)
CPU内存屏障
-----------
Linux内核有8种主要的CPU内存屏障:
类型 强制 SMP环境
=============== ======================= ===========================
通用 mb() smp_mb()
写 wmb() smp_wmb()
读 rmb() smp_rmb()
数据依赖 read_barrier_depends() smp_read_barrier_depends()
(译注: 这里所说有SMP屏障是仅仅在SMP环境下才生效的屏障, 而强制屏障则是无论在不在SMP
环境下都生效的屏障. 这里所谓的SMP环境, 确切的说, 事实上是内核的编译选项指定为SMP的
情况, 并非指实际执行内核的机器的环境. 只是既然编译选项指定了SMP环境, 那么编译
生成的内核也基本上将会执行在SMP环境. 以下提到的UP环境亦是同理.)
除了数据依赖屏障之外, 全部的内存屏障都隐含了编译优化屏障的功能. 数据依赖屏障不正确
编译器输出的代码顺序造成不论什么额外的影响.
注: 在存在数据依赖关系的情况下, 编译器预期会将LOAD指令按正确的顺序输出(比如, 在
a[b]
语句中, 对b的load必须放在对a[b]的load之前), 但在C规范下, 并不保证编译器不
去预測B的值(比方预測它等于1), 于是先load a再load b(比方,
tmp = a[1]; if (b != 1) tmp = a[b]