2022-Linux内核内存屏障简单介绍

原文地址 TODO!

Linux内核内存屏障简单介绍

在阅读很多底层的代码时，经常会碰到一个所谓内存屏障的概念，经常搞得一头雾水。本文将对这个概念进行一个系统的介绍。

一、为什么需要内存屏障

内存屏障的引入，本质上是由于CPU重排序指令引起的。重排序问题无时无刻不在发生，主要源自以下几种场景：

  • 编译器编译时的优化；
  • 处理器执行时的多发射和乱序优化；
  • 读取和存储指令的优化；
  • 缓存同步顺序（导致可见性问题）。

编译器优化

编译器在不改变单线程程序语义的前提下，也就是保证单线程程序执行结果正确的情况下，可以重新安排语句的执行顺序。编译器在优化的时候是不知道当前程序是在哪个线程中执行的，因此它只能保证单线程的正确性。

例如，有如下程序：

if (a)
    b = a;
else
    b = 42;

在经过编译器优化后可能变成：

b = 42;
if (a)
    b = a;

这种优化在单线程下是没有问题的，但是如果有另外一个线程要读取变量b的值时，有可能会有问题。前面的程序只有当变量a的值为0时，才会将b赋值42，后面的程序无论变量a的值是多少，都有一段时间会将b赋值为42。造成这个问题的原因是，编译器优化的时候只注重“结果”，不注重“过程”。这种优化在单线程程序中没有问题，代码一直都是自己运行，只要结果对就可以了，但是在多线程程序下，代码执行过程中的某些状态可能会对别的线程产生影响，这个是编译器优化无法考虑到的。

处理器执行时的多发射和乱序优化

现代处理器基本上都是支持多发射的，也就是在一个指令周期内可以同时执行多条指令。但是，处理器的资源就那么多，可能不能同时满足处理这些指令的要求。比如，处理器就只有一个加法器，如果同时有两条指令都需要算加法，那么有一条指令必须等待。如果这时候再下一条指令是读取指令，并且和前两条指令无关，那么这条指令将在前面某条加法指令之前完成。还有一种可能，就是前后指令之间具有相关性，比如对同一个地址先读取再写入，后面的写入操作必须等待前面的读取操作完成后才能执行。但是如果这时候第三条指令是写入一个无关的地址，那它可以在前面的写入操作之前被执行，执行顺序再次被打乱了。

所以，一般情况下指令乱序并不是CPU在执行指令之前刻意去调整顺序。CPU总是顺序的去内存里面取指令，然后将其顺序的放入指令流水线。但是指令执行时的各种条件，指令与指令之间的相互影响，可能导致顺序放入流水线的指令，最终不是按照放入的顺序执行完成，在外边看起来仿佛是“乱序”一样，这就是所谓的“顺序流入，乱序流出”。

读取和存储指令的优化

CPU有可能根据情况，将相临的两条读取或写入操作合并成一条。例如，对于如下的两条读取操作：

X = *A; Y = *(A + 4);

可能被合并成一条读取操作：

{X, Y} = LOAD {*A, *(A + 4) };

同样的，对于如下两条写入操作：

*A = X; *(A + 4) = Y;

有可能会被合并成一条：

STORE {*A, *(A + 4) } = {X, Y};

以上这几种情况，由于编译器或CPU，出于“优化”的目的，按照某种规则将指令重新排序的行为称作“真”重排序。不同的是，编译器重排序是在编译程序时进行的，一旦编译成功后执行次序就定下来了。而后面几种是在CPU运行程序时实时进行的，CPU架构不同可能起到的效果完全不同。

编译器或CPU在执行各种优化的时候，都有一些必须的前提，就是至少在单一CPU上执行不能出现问题。有一些数据访问明显是相互依赖的，就不能打乱它们的执行顺序。比如：

1）在一个给定的CPU上，有依赖的内存访问：

比如如下两条指令：

A = Load B;
C = Load *A

第二条加载指令的地址是由第一条指令加载的，第二条指令要能正确执行，必须要等到第一条指令执行完成后才行，也就是说第二条指令依赖于第一条指令。这种情况下，无论如何处理器是不会打乱这两条指令的执行次序的。不过，有可能会在这两条指令间插入别的指令，但必须保证第二条指令在第一条指令执行完后才能执行。

2）在一个给定的CPU上，交叉的加载和存储操作，它们访问的内存地址有重叠：

例如，先存储后加载同一个内存地址上的内容：

Store *X = A;
B = Load *X;

或者先加载后读取同一个内存地址上的内容：

A = Load *X;
Store *X = B;

对同一个内存地址的存取，如果两条指令执行次序被打乱了，那肯定会发生错误。但是，如果是两条加载或两条存储指令（中间没有加载），哪怕是对同一个内存地址的操作，也可能由于优化产生变化。有了上面两条限制，很容易想到，那如果所有加载或存储指令都没有相关性呢？这时候就要看CPU的心情了，可以以任何次序被执行，可以完全不按照它们在程序中出现的次序。

缓存同步顺序

上面的几种情况都比较好理解，最诡异的是所谓的缓存同步顺序的问题。要把这个问题说清楚首先要说一下缓存是什么。

现代CPU的运算速度比现代内存系统的速度快得多，它们的速度差了几个数量级，那怎么办呢？硬件设计者想到了在内存和CPU之间加入一个速度足够快，但空间不是很大的存储空间，这个就是所谓的缓存。缓存的速度足够快，但是它一般是某个或某些CPU核独享的，而不像计算机的主存，一般认为是系统中所有CPU共享的。

CPU 缓存、内存模块

一旦引入了缓存，就会引入多个地方存放同一个数据的问题，就有可能出现数据不一致的问题。假设变量X所在内存同时被两个CPU都缓存了，但是这时候CPU0对变量X的值做出了修改，这之后CPU1如果试图读取变量X的值时，其实读到的是老的值。这个时候就需要所谓的缓存一致性协议了，一般常用的是MESI协议。MESI代表“Modified”、“Exclusive”、“Shared”和“Invalid”四种状态的缩写，特定缓存行可以处在该协议采用的这四种状态上：

  • 处于“Modified”状态的缓存行：当前CPU已经对缓存行的数据进行了修改，但是该缓存行的内容并没有在其它CPU的缓存中出现。因此，处于该状态的缓存行可以认为被当前CPU所“拥有”。这就是所谓的“脏”行，它的内容和内存中的内容不一样。由于只有当前CPU的缓存持有最新的数据，因此要么将“脏”数据写回到内存，要么将该数据“转移”给其它缓存。

  • 处于“Exclusive”状态的缓存行：该状态非常类似于“Modified”状态，缓存的内容确保没有在其它CPU的缓存中出现。唯一的差别是，该缓存行还没有被当前的CPU修改，也就是说缓存行内容和内存中的是一样，是对内存数据的最新复制。但是，由于当前CPU能够在任何时刻将数据存储到该缓存行而不考虑其它CPU，因此处于“Exclusive”状态的缓存行也可以认为被当前CPU所“拥有”。

  • 处于“Shared”状态的缓存行：表示缓存行的数据和主存中的一样，并且可能已经被复制到至少一个其它CPU的缓存中。但是，在没有得到其他CPU“许可”的情况下，任何CPU不能向该缓存行存储数据。与“Exclusive”状态相同，由于内存中的值是最新的，因此当需要丢弃该缓存行时，可以不用向内存回写。

  • 处于“Invalid”状态的缓存行：表示该缓存行已经失效了，不能再被继续使用了。当有新数据进入缓存时，它可以直接放置到一个处于“Invalid”状态的缓存行上，不需要做其它的任何处理。

为了维护这个状态机，需要各个CPU之间进行通信，会引入下面几种类型的消息：

  • 读消息：该消息包含要读取的缓存行的物理地址。
  • 读响应消息：该消息包含较早前的读消息所请求的数据，这个读响应消息要么由物理内存提供，要么由某一个其它CPU上的缓存提供。例如，如果某一个CPU上的缓存拥有处于“Modified”状态的目标数据，那么该CPU上的缓存必须提供读响应消息。
  • 使无效消息：该消息包含要使无效的缓存行的物理地址，所有其它CPU上的缓存必须移除相应的数据并且响应此消息。
  • 使无效应答消息：一个接收到使无效消息的CPU必须在移除指定数据后响应一个使无效应答消息。
  • 读使无效消息：该消息包含要被读取的缓存行的物理地址，同时指示其它CPU上的缓存移除对应的数据。因此，正如名字所示，它将读消息和使无效消息合并成了一条消息。读使无效消息同时需要一个读响应消息及一组使无效应答消息进行应答。
  • 写回消息：该包含要回写到物理内存的地址和数据。这个消息允许缓存在必要时换出处于“Modified”状态的数据，以便为其它数据腾出空间。

通过上面的介绍可以看到，MESI缓存一致性协议可以保证系统中的各个CPU核上的缓存都是一致的。但是也带来了一个很大的问题，由于所有的操作都是“同步”的，必须要等待远端CPU完成指定操作后收到响应消息才能真正执行对应的存储或加载操作，这样会极大降低系统的性能。比如说，如果CPU0和CPU1上同时缓存了同一段数据，如果CPU0想对其进行更改，那么必须先发送使无效消息给CPU1，等到CPU1真的将该缓存的数据段标记成“Invalid”状态后，会向CPU0发送使无效应答消息，理论上只有CPU0收到这个消息后，才可以真的更改数据。但是，从要更改到真的能更改已经经过了好几个阶段了，这时CPU0只能等在那里。

鱼和熊掌都兼得是不可能的，想提高性能，只能稍微放松一下对缓存一致性的要求。具体的，会引入如下两个模块：

  • 存储缓冲：前面提到过，在写数据之前我们先要得到缓存段的独占权，如果当前CPU没有独占权，要先让系统中别的CPU上缓存的同一段数据都变成无效状态。为了提高性能，可以引入一个叫做存储缓冲（Store Buffer）的模块，将其放置在每个CPU和它的缓存之间。当前CPU发起写操作，如果发现没有独占权，可以先将要写入的数据放在存储缓冲中，并继续运行，仿佛独占权瞬间就得到了一样。当然，存储缓冲中的数据最后还是会被同步到缓存中的，但就相当于是异步执行了，不会让CPU等了。并且，当前CPU在读取数据的时候应该首先检查其是否存在于存储缓冲中。

  • 无效队列：如果当前CPU上收到一条消息，要使某个缓存段失效，但是此时缓存正在处理其它事情，那这个消息可能无法在当前的指令周期中得到处理，而会将其放入所谓的无效队列（Invalidation Queue）中，同时立即发送使无效应答消息。那个待处理的使无效消息将保存在队列中，直到缓存有空为止。

无效队列

加入了这两个模块之后，CPU的性能是提高了，但缓存一致性就遭到了一定程度的破坏。假设变量X所在内存同时被两个CPU都缓存了，但是这时候CPU0对变量X的值做出了修改，这之后CPU1如果试图读取变量X的值时，有可能读到的是老的值，当然也有可能读到的是新的值。但是，在经过一段不确定的时间后，CPU1一定是可以读到变量X新的值，可以理解为满足所谓的最终一致性。

但这只是对单个变量来说的，如果程序中有多个变量，那么在其它CPU看来，它们之间的读写次序将完全无法得到保证。假设有CPU0上要执行对三个变量的写操作：

Store A = 1;
Store B = 2;
Store C = 3;

但是，这三个变量在缓存中的状态不一样，假设A变量和B变量在CPU0和CPU1中的缓存都存在，也就是处于“Shared”状态，而C变量是CPU0独占的，也就是处于“Exclusive”状态。假设系统经历了如下几个步骤：

  • 在对变量A和B赋值时，CPU0发现其实别的CPU也缓存了，因此会将它们临时放到存储缓冲中。
  • 在对变量C赋值时，CPU0发现是独占的，那么可以直接修改缓存的值，该缓存行的状态被切换成了“Modified”。注意，这个时候，如果在CPU1上执行了读取变量C的操作，其实已经可以读到变量C的最新值了，CPU1发送读消息，CPU0发送读响应消息，包含最新的数据，同时将缓存行的状态都切换成“Shared”。但是，如果这个时候如果CPU1尝试读取变量A或者变量B的数据，将会获得老的数据，因为CPU1上对应变量A和B的缓存行的状态仍然是“Shared”。
  • CPU0开始处理对应变量A和B的存储缓冲，将它们更新进缓存，但之前必须要向CPU1发送使无效消息。这里再次假设变量A的缓存正忙，而变量B的可以立即处理。那么变量A的使无效消息将存放在CPU1的无效队列中，而变量B的缓存行已经失效。这时，如果CPU1尝试获得变量B，是可以获得最新的数据的，而变量A还是不行。
  • CPU1对应变量A的缓存已经空闲了，可以处理当前无效队列的请求，因此变量A对应的缓存行将失效。直到这时CPU1才可以真正的读到变量A的最新值。

通过以上的步骤可以看到，虽然在CPU0上是先对变量A赋值，接着对B赋值，最后对C赋值，但是在CPU1上“看到”的顺序刚好是相反的，先“看到”C，接着“看到”B，最后看到“A”。在CPU1上会产生一种错觉，方式CPU0是先对C赋值，再对B赋值，最后对A赋值一样。这种由于缓存同步顺序的问题，让程序看起来好像指令被重排序了的情况，称作“伪”重排序。

总结

所以，总结一下，以上几种场景都有可能产生所谓指令重排序的效果。由于编译器优化引起的是静态的，是由编译器决定的，一旦程序编译完成就定下来了。而其它剩下的场景都是动态的，在处理器执行的时候，根据当前系统状态动态的调整。并且不同的架构的处理器提供不同级别的数据一致性保证，这也称作所谓的内存模型。有的平台提供很强的保证（比如X86），有的比较弱（比如Arm）。

由于缓存同步顺序引入的乱序问题称作“伪”重排序，就是说即使某个CPU按照代码的次序执行了程序更新了数据，但是在其它CPU看来，看到数据的次序和代码执行的次序也不一样。而其它剩下的情况都是所谓的“真”重排序，也就是说代码执行的顺序确实是和程序中的顺序不一样。不管是“真”重排序还是“伪”重排序，对于系统中其它的CPU来说，叠加后产生的影响是一样的，都是看到数据的次序和代码执行的次序不一样。这其实可以分解成三个问题：

  • 执行指令的CPU不是按照指令执行的次序修改内存的（由于“真”重排序）；
  • 修改内存的操作不是按照实际修改的顺序被别的CPU感知的（由于缓存一致性问题而引入的“伪”重排序）；
  • 别的CPU不是按照指令执行的次序来感知内存更改的（还是由于“真”重排序）。

最近更新于0001-01-01