LINUX内核内存屏障（上）
点击上方“蓝字”可以关注我们哦
内存访问抽象模型
考虑如下抽象系统模型
假设每个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与系统中其他部分的界面(见图中的虚线)之后, 才能被其他部分所感知.
举例来说, 考虑如下的操作序列:
这一组访问指令在内存系统(见上图的中间部分)上生效的顺序, 可以有24种不同的组合:
然后这就产生四种不同组合的结果值:
x == 1, y == 2
x == 1, y == 4
x == 3, y == 2
x == 3, y == 4
甚至于,一个CPU在内存系统上提交的STORE操作还可能不会以相同的顺序被其他CPU所执行的LOAD操作所感知.
进一步举例说明, 考虑如下的操作序列:
这里有一处明显的数据依赖, 因为在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操作(译注: 因为存在数据依赖).
操作设备
对于一些设备, 其控制寄存器被映射到一组内存地址集合上, 而这些控制寄存器被访问的顺序是至关重要的. 假设, 一个以太网卡拥有一些内部寄存器, 通过一个地址端口寄存器(A)和一个数据端口寄存器(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 = *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
数据依赖屏障
数据依赖屏障的使用需求有点微妙, 并不总是很明显就能看出需要他们. 为了说明这一点, 考虑如下的操作序列:
这里有明显的数据依赖, 在序列执行完之后, Q的值一定是&A和&B之一, 也就是:
(Q == &A) 那么 (D == 1)
(Q == &B) 那么 (D == 4)
但是! CPU 2可能在看到P被更新之后, 才看到B被更新, 这就导致下面的情况:
(Q == &B) 且 (D == 2) ????
虽然这看起来似乎是一个一致性错误或逻辑关系错误, 但其实不是, 并且在一些真实的CPU中就能看到这样的行为(就比如DEC Alpha).
为了解决这个问题, 必须在取地址和取数据之间插入一个数据依赖或更强的屏障:这将强制最终结果是前两种情况之一, 而避免出现第三种情况.
[!] 注意, 这种非常违反直觉的情况最容易出现在cache分列的机器上, 比如, 一个cache组处理偶数号的cache行, 另一个cache组处理奇数号的cache行. P指针可能存储在奇数号的cache行中, 而B的值可能存储在偶数号的cache行中. 这样一来, 如果执行读操作的CPU的偶数号cache组非常繁忙, 而奇数号cache组空闲, 它就可能看到P已被更新成新值(&B), 而B还是旧值(2).
另一个可能需要数据依赖屏障的例子是, 从内存读取一个数值, 用于计算数组的访问偏移:
数据依赖屏障对于RCU非常重要, 举例来说. 参阅include/linux/rcupdate.h文件中的rcu_dereference()函数. 这个函数使得当前RCU指针指向的对象被替换成新的对象时, 不会发生新对象尚未初始化完成的情况. (译注: 更新RCU对象时, 一般步骤是: 1-为新对象分配空间; 2-初始化新对象; 3-调用rcu_dereference()函数, 将对象指针指到新的对象上, 这就意味着新的对象已生效. 这个过程中如果出现乱序访存, 可能导致对象指针的更新发生在新对象初始化完成之前. 也就是说, 新对象尚未初始化完成就已经生效了. 那么别的CPU就可能引用到一个尚未初始化完成的新对象, 从而出现错误.)
控制依赖
控制依赖需要使用一个完整的读内存屏障, 简单的数据依赖屏障不能使其正确工作. 考虑下面的代码:
q = &a;
if (p)
q = &b;
<数据依赖屏障>
x = *q;
这段代码可能达不到预期的效果, 因为这里其实并不是数据依赖, 而是控制依赖, CPU可能试图通过提前预测结果而对"if (p)"进行短路. 在这样的情况下, 需要的是:
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上的写屏障是为了保证这样的逻辑: 如果a == 3 || b == 4, 那么必定有p == 1.但是到了CPU 2, 可能a或b的值已更新, 而p的值未更新. 那么这时使用数据依赖屏障就不能保证p的更新. 因为从代码逻辑上说, p跟任何人都没有依赖关系. 这时必须使用读屏障, 以确保x = *q之前, p被更新.原文中"短路"的意思就是, 由于p没有数据依赖关系, CPU可以早获得它的值, 而不必考虑更新.)
SMP内存屏障的配对使用
在处理CPU与CPU的交互时, 对应类型的内存屏障总是应该配对使用. 缺乏适当配对的使用基本上可以肯定是错误的.
一个写屏障总是与一个数据依赖屏障或读屏障相配对, 虽然通用屏障也可行.类似的, 一个读屏障或数据依赖屏障也总是与一个写屏障相配对,尽管一个通用屏障也同样可行:
基本上, 读屏障总是需要用在这些地方的, 尽管可以使用"弱"类型.
[!] 注意, 在写屏障之前出现的STORE操作通常总是期望匹配读屏障或数据依赖屏障之后出现的LOAD操作, 反之亦然:
我知道一种学习
○
于坚
下载我们APP
Android和IOS均可使用
这里有最新鲜的干货
ITPUB｜ChinaUnix｜IT168