Intel DPDK的内存屏障介绍

本文章由美团数据面大佬发表于知乎：

https://zhuanlan.zhihu.com/p/657085678

如有侵权，请联系删除文章，谢谢！

同步的目的是保证不同执行流对共享数据并发操作的一致性。在单核时代，使用原子变量就很容易达成这一目的。甚至因为CPU的一些访存特性，对某些内存对齐数据的读或写也具有原子的特性。但在多核架构下即使操作是原子的，仍然会因为其他原因导致同步失效。

首先是现代编译器的代码优化和编译器指令重排可能会影响到代码的执行顺序。

其次还有指令执行级别的乱序优化，流水线、乱序执行、分支预测都可能导致处理器次序（Process Ordering，机器指令在CPU实际执行时的顺序）和程序次序（Program Ordering，程序代码的逻辑执行顺序）不一致。可惜不影响语义依旧只能是保证单核指令序列间，单核时代CPU的Self-Consistent特性在多核时代已不存在（Self-Consistent即重排原则：有数据依赖不会进行重排，单核最终结果肯定一致）。

除此还有硬件级别Cache一致性（Cache Coherence）带来的问题，CPU架构中传统的MESI协议中有两个行为的执行成本比较大。一个是将某个Cache Line标记为Invalid状态，另一个是当某Cache Line当前状态为Invalid时写入新的数据。所以CPU通过Store Buffer和Invalidate Queue组件来降低这类操作的延时。如图所示：

当一个核心在Invalid状态进行写入时，首先会给其它CPU核发送Invalid消息，然后把当前写入的数据写入到Store Buffer中。然后异步在某个时刻真正的写入到Cache Line中。当前CPU核如果要读Cache Line中的数据，需要先扫描Store Buffer之后再读取Cache Line（Store-Buffer Forwarding）。但是此时其它CPU核是看不到当前核的Store Buffer中的数据的，要等到Store Buffer中的数据被刷到了Cache Line之后才会触发失效操作。

而当一个CPU核收到Invalid消息时，会把消息写入自身的Invalidate Queue中，随后异步将其设为Invalid状态。和Store Buffer不同的是，当前CPU核心使用Cache时并不扫描Invalidate Queue部分，所以可能会有极短时间的脏读问题。这里的Store Buffer和Invalidate Queue的说法是针对一般的SMP架构来说的，不涉及具体架构。

内存对于缓存更新策略，要区分Write-Through和Write-Back两种策略。前者更新内容直接写内存并不同时更新Cache，但要置Cache失效，后者先更新Cache，随后异步更新内存。通常X86 CPU更新内存都使用Write-Back策略。

2. 编译器屏障Compiler Barrior

/* The "volatile" is due to gcc bugs */

#define barrier() __asm__ __volatile__("": : :"memory")

阻止编译器重排，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。

3. CPU屏蔽屏障

CPU级别内存屏障其作用有两个：

防止指令之间的重排序

保证数据的可见性

指令重排中Load和Store两种操作会有Load-Store、Store-Load、Load-Load、Store-Store这四种可能的乱序结果。

LoadLoad Barrier（读读屏障）

指令 Load1; LoadLoad; Load2 保证了 Load1 先于 Load2 和后续所有的 load 指令加载数据。通常情况下，在执行预测读（speculative loads）或乱序处理（out-of-order processing）的处理器上需要显式的 LoadLoad Barrier。在始终保证读顺序（load ordering）的处理器上，这些屏障相当于无操作（no-ops）。

StoreStore Barrier（写写屏障）

指令 Store1; StoreStore; Store2 保证了 Store1 的数据先于 Store2 及后续 store 指令的数据对其他处理器可见（刷新到内存）。通常情况下，在不保证严格按照顺序从写缓冲区（store buffers）或者 缓存（caches）刷新到其他处理器或内存的处理器上，需要使用 StoreStore Barrier。

LoadStore Barrier（读写屏障）

指令 Load1; LoadStore; Store2 保证了 Load1 的加载数据先于 Store2 及后续 store 指令刷新数据到主内存。只有在乱序（out-of-order）处理器上，等待写指令（waiting store instructions）可以绕过读指令（loads）的情况下，才会需要使用 LoadStore 屏障。

StoreLoad Barrier（写读屏障）刷新写缓冲区，最耗时

指令 Store1; StoreLoad; Load2 保证了 Store1 的数据对其他处理器可见（刷新数据到内存）先于 Load2 及后续的 load 指令加载数据。StoreLoad 屏障可以防止后续的读操作错误地使用了 Store1 写的数据，而不是使用来自另一个处理器的更近的对同一位置的写。因此只有需要将对同一个位置的写操作（stores）和随后的读操作（loads）分开时，才严格需要 StoreLoad 屏障。StoreLoad 屏障通常是开销最大的屏障，几乎所有的现代处理器都需要该屏障。之所以开销大，部分原因是它需要禁用绕过缓存（cache）从写缓冲区（Store Buffer）读取数据的机制。这可以通过让缓冲区完全刷新，外加暂停其他操作来实现，这就是 Fence 的效果。一般用 Fence 代替 StoreLoad Barrier ，所以事实上，执行 StoreLoad 指令同时也获得了其他三个屏障的效果，但是通过组合其他屏障通常不能获得与 StoreLoad Barrier 相同的效果。

4. 写缓冲与写屏障

按照MESI协议，核心0 在修改本地缓存之前，需要向其他核心发送 Invalid 消息，其他核心收到消息后，使他们本地对应的缓存行失效，并返回 Invalid acknowledgement 消息，核心0 收到后修改缓存行。这里核心0 等待其他核心返回确认消息的时间对核心来说是漫长的。

为了解决这个问题，引入了Store Buffers。

Store Buffers

防止这种不必要的写入停滞的一种方法就是在每个CPU和它的CPU之间添加“存储缓冲区”，当核心想修改缓存时，直接写入Store Buffers，无需等待，继续处理其他事情，由Store Buffers完成后续工作。

Caches With Store Buffers

这样写的速度加快，可是有新的问题：

如果要了解第一个复杂的情况，违反自一致性，先来看一段代码，其中变量“a”和“b”最初都为零，并且高速缓存行包含最初由 CPU 1 持有的变量“a”，并且包含“b”最初由 CPU 0 持有

1 a=1;

2 b=a+1;

3 assert(b == 2);

我们不期望这一断言会失败。然而，如果有使用图上 所示的非常简单的架构，人们就会感到惊讶。这样的系统可能会看到以下事件序列：

1. CPU 0 开始执行 a=1。

2. CPU 0 在缓存中查找“a”，发现丢失

3. 因此，CPU 0 发送“读无效”消息，以获得包含“a”的缓存行的独占所有权。

4. CPU 0 将存储记录到其存储缓冲区中的“a”。

5. CPU 1 接收“读无效”消息，并通过传输高速缓存行并从其高速缓存中删除该高速缓存行来进行响应。

6. CPU 0 开始执行 b=a+1。

7. CPU 0从CPU 1接收缓存行，“a”的值仍然为零。

8. CPU 0 从其缓存加载“a”，发现值为零。

9. CPU 0 将其存储队列中的条目应用到新到达的高速缓存行，将其高速缓存中的“a”值设置为 1。

10. CPU 0 将上面“a”加载的值零加一，并将其存储到包含“b”的高速缓存行中（我们假设它已经属于 CPU 0）。

11. CPU 0 执行assert(b==2)，失败。

问题是我们有两个“a”的副本，一个在缓存中，另一个在存储缓冲区中。

这个例子打破了一个非常重要的约定，即每个 CPU 总是会看到自己的操作，就好像它们按照程序顺序发生一样。打破这个保证对于软件类型来说是非常违反常规，所以硬件人员实现了“存储转发”，其中每个CPU在执行时引用（或“窥探”）其存储缓冲区以及缓存加载，如图 下 所示。换句话说，给定 CPU 的存储直接转发到其后续加载，而无需通过缓存。

5. 存储缓冲区与内存屏障

要了解第二个复杂的情况（违反全局内存顺序），请考虑以下代码序列，其中变量“a”和“b”最初为零：

void foo(void)

{

a=1;

b=1;

}

void bar(void) {

while (b == 0) continue;

assert(a == 1);

}

假设CPU 0 执行foo()，CPU 1 执行bar()。进一步假设包含“a”的缓存行仅驻留在CPU 1的缓存中，并且包含“b”的缓存行属于CPU 0。那么操作顺序可能如下：

1. CPU 0执行a=1。该缓存行不在 CPU 0 的缓存中，因此 CPU 0 将“a”的新值放入其存储缓冲区中，并发送“读无效”消息。

2. CPU 1 执行 while(b==0)Continue，但包含“b”的缓存行不在其缓存中。因此它发送“已读”消息。

3. CPU 0 执行 b=1。它已经拥有该缓存行（换句话说，该缓存行已经处于“已修改”或“独占”状态），因此它将“b”的新值存储在其缓存行中。

4. CPU 0 接收“读”消息，并将包含当前更新的“b”值的缓存行传输到 CPU 1，同时将该行标记为在自己的缓存中“共享”。

5. CPU 1 接收包含“b”的高速缓存行并将其安装到其高速缓存中。

6. CPU 1 现在可以完成 while(b==0) continue 的执行，并且由于它发现“b”的值为 1，因此继续执行下一条语句。

7. CPU 1 执行断言(a==1)，并且由于 CPU 1 正在使用“a”的旧值，因此该断言失败。

8. CPU 1 收到“read invalidate”消息，将包含“a”的缓存行传输到 CPU 0，并从自己的缓存中使该缓存行无效。但已经太晚了。

9. CPU 0 接收到包含“a”的缓存行并及时应用缓冲存储，从而成为 CPU 1 断言失败的受害者。

在上面的步骤 1 中，为什么 CPU 0 需要发出“读无效”而不是简单的“无效”？

硬件设计者无法在这里直接提供帮助，因为 CPU 不知道哪些变量是相关的，更不用说它们是如何相关的了。因此，硬件设计者提供内存屏障指令来允许软件告诉CPU这种关系。必须更新程序片段以包含内存屏障：

1 void foo(void)

2{

3 a=1;

4 smp_mb();

5 b=1;

6}

7

8 void bar(void) 9{

10 while (b == 0) continue;

11 assert(a == 1);

12 }

内存屏障 smp_mb() 将导致 CPU 在将每个后续存储应用到其变量的缓存行之前刷新其存储缓冲区。CPU 可以简单地停止直到存储缓冲区为空，然后再继续，或者它可以使用存储缓冲区来保存后续存储，直到应用了存储缓冲区中的所有先前条目。

对于后一种方法，操作顺序可能如下：

1. CPU 0执行a=1。该缓存行不在 CPU 0 的缓存中，因此 CPU 0 将“a”的新值放入其存储缓冲区中，并发送“读无效”消息。

2. CPU 1 执行 while(b==0)Continue，但包含“b”的缓存行不在其缓存中。因此它发送“已读”消息。

3. CPU 0 执行 smp_mb()，并标记所有当前存储缓冲区条目（即 a=1）。

4. CPU 0 执行 b=1。它已经拥有该缓存行（换句话说，该缓存行已经处于“已修改”或“独占”状态），但存储缓冲区中有一个标记的条目。因此，它不会将“b”的新值存储在缓存行中，而是将其放置在存储缓冲区中（但在未标记的条目中）。

5. CPU 0 接收“read”消息，并将包含“b”原始值的缓存行传输到 CPU 1。它还将自己的该缓存行副本标记为“共享”。

6. CPU 1 接收包含“b”的高速缓存行并将其安装到其高速缓存中。

7. CPU 1 现在可以加载“b”的值，但由于它发现“b”的值仍然是 0，因此它重复 while 语句。“b”的新值安全地隐藏在 CPU 0 的存储缓冲区中。

8. CPU 1 收到“read invalidate”消息，将包含“a”的缓存行传输到 CPU 0，并从自己的缓存中使该缓存行无效。

9. CPU 0 接收包含“a”的高速缓存行并应用缓冲存储，将该行置于“已修改”状态。

10. 由于存储到“a”是存储缓冲区中由 smp_mb() 标记的唯一条目，CPU 0 还可以存储“b”的新值 — 除了包含“b”的高速缓存行这一事实”现在处于“共享”状态。

11. 因此，CPU 0 向 CPU 1 发送“无效”消息。

12. CPU 1 收到“invalidate”消息，使其缓存中包含“b”的缓存行无效，并向 CPU 0 发送“acknowledgement”消息。

13. CPU 1 执行 while(b==0)Continue，但包含“b”的缓存行不在其缓存中。因此，它向 CPU 0 发送“已读”消息。

14. CPU 0 收到“确认”消息，并将包含“b”的缓存行置于“独占”状态。CPU 0 现在将“b”的新值存储到缓存行中。

15. CPU 0 接收“读”消息，并将包含新值“b”的缓存行传输到 CPU 1。它还将自己的该缓存行副本标记为“共享”。

16. CPU 1 接收包含“b”的高速缓存行并将其安装到其高速缓存中。

17. CPU 1 现在可以加载“b”的值，并且由于它发现“b”的值为 1，因此它退出 while 循环并继续执行下一条语句。

18. CPU 1 执行断言(a==1)，但包含“a”的缓存行不再位于其缓存中。一旦它从 CPU 0 获取此缓存，它将使用“a”的最新值，因此断言会通过。

正如您所看到的，这个过程涉及大量的簿记工作。即使是直观上简单的事情，例如“加载 a 的值”，也可能涉及芯片中的许多复杂步骤。

6. 失效队列与内存屏障

不幸的是，每个存储缓冲区必须相对较小，这意味着 CPU 执行适度的存储序列就可以填满其存储缓冲区（例如，如果所有存储缓冲区都导致高速缓存未命中）。此时，CPU 必须再次等待失效完成，以便耗尽其存储缓冲区，然后才能继续执行。当所有后续存储指令必须等待失效完成时，无论这些存储是否会导致缓存未命中，内存屏障之后都会立即出现相同的情况。

通过使无效确认消息更快到达可以改善这种情况。实现此目的的一种方法是使用每个 CPU 的无效消息队列，或“无效队列”。

无效确认消息可能需要很长时间的原因之一是它们必须确保相应的缓存行实际上已失效，并且如果缓存繁忙（例如，如果 CPU 正在密集地加载和存储数据），则该失效可能会被延迟，所有这些都驻留在缓存中。此外，如果大量无效消息在短时间内到达，给定的 CPU 可能无法及时处理这些消息，从而可能导致所有其他 CPU 停止运行。

然而，CPU 在发送确认之前实际上不需要使高速缓存行无效。相反，它可以将无效消息排队，并理解该消息将在 CPU 发送有关该缓存行的任何进一步消息之前得到处理。

Caches With Invalidate Queues

图 上显示了具有无效队列的系统。具有无效队列的 CPU 可以在无效消息放入队列后立即确认该消息，而不必等到相应的行实际无效。当然，CPU在准备传输无效消息时必须参考其无效队列——如果相应缓存行的条目在无效队列中，CPU无法立即传输无效消息；它必须等到无效队列条目被处理。

将条目放入无效队列本质上是 CPU 承诺在传输任何有关该缓存行的 MESI 协议消息之前处理该条目。只要相应的数据结构没有高度竞争，CPU 就很少会因为这样的承诺而感到不便。

然而，无效消息可以缓冲在无效队列中这一事实为内存乱序提供了额外的机。

让我们假设 CPU 将失效请求排队，但立即响应它们。这种方法最大限度地减少了 CPU 进行存储时出现的缓存失效延迟，但可以克服内存障碍，如以下示例所示。

假设“a”和“b”的值最初为零，“a”被复制为只读（MESI“共享”状态），并且“b”由CPU 0拥有（MESI“独占”或“修改”状态）。然后假设 CPU 0 执行 foo()，而 CPU 1 执行函数 bar()，如下代码片段所示：

1 void foo(void)

2 {

3 a=1;

4 smp_mb();

5 b=1;

6 }

7

8 void bar(void)

9 {

10 while (b == 0) continue;

11 assert(a == 1);

12 }

那么操作顺序可能如下：

1. CPU 0执行a=1。相应的缓存行在 CPU 0 的缓存中是只读的，因此 CPU 0 将新值“a”放入其存储缓冲区中，并发送“无效”消息，以便从 CPU 1 的缓存中刷新相应的缓存行。

2. CPU 1 执行 while(b==0)Continue，但包含“b”的缓存行不在其缓存中。因此它发送“已读”消息。

3. CPU 1收到CPU 0的“invalidate”消息，将其放入队列，并立即响应。

4. CPU 0 收到来自 CPU 1 的响应，因此可以自由地继续执行上面第 4 行上的 smp_mb()，将“a”的值从其存储缓冲区移动到其高速缓存行。

5. CPU 0 执行 b=1。它已经拥有该缓存行（换句话说，该缓存行已经处于“已修改”或“独占”状态），因此它将“b”的新值存储在其缓存行中。

6. CPU 0 接收“读”消息，并将包含当前更新的“b”值的缓存行传输到 CPU 1，同时将该行标记为在自己的缓存中“共享”。

7. CPU 1 接收包含“b”的高速缓存行并将其安装到其高速缓存中。

8. CPU 1 现在可以完成 while(b==0) continue 的执行，并且由于它发现“b”的值为 1，所以它继续执行下一条语句。

9. CPU 1 执行断言(a==1)，由于“a”的旧值仍在 CPU 1 的缓存中，因此该断言失败。

10. 尽管断言失败，CPU 1 仍处理排队的“无效”消息，并（迟缓地）使包含来自其自己的高速缓存的“a”的高速缓存行无效。

在第一个场景的步骤 1 中，为什么发送“invalidate”而不是“read invalidate”消息？CPU 0 不需要与“a”共享该缓存行的其他变量的值吗？

如果加速无效响应会导致内存障碍被有效忽略，那么显然没有多大意义。然而，内存屏障指令可以与无效队列交互，因此当给定的CPU执行内存屏障时，它会标记当前在其无效队列中的所有条目，并强制任何后续加载等待，直到所有标记的条目都已完成。被应用到CPU的缓存中。因此，我们可以向函数bar添加一个内存屏障，如下所示：

1 void foo(void)

2 {

3 a=1;

4 smp_mb();

5 b=1;

6}

7

8 void bar(void)

9 {

10 while (b == 0) continue;

11 smp_mb();

12 assert(a == 1);

13 }

进行此更改后，操作顺序可能如下：

1. CPU 0执行a=1。相应的缓存行在 CPU 0 的缓存中是只读的，因此 CPU 0 将新值“a”放入其存储缓冲区中，并发送“无效”消息，以便从 CPU 1 的缓存中刷新相应的缓存行。

2. CPU 1 执行 while(b==0)Continue，但包含“b”的缓存行不在其缓存中。因此它发送“已读”消息。

3. CPU 1收到CPU 0的“invalidate”消息，将其放入队列，并立即响应。

4. CPU 0 收到来自 CPU 1 的响应，因此可以自由地继续执行上面第 4 行上的 smp_mb()，将“a”的值从其存储缓冲区移动到其高速缓存行。

5. CPU 0 执行 b=1。它已经拥有该缓存行（换句话说，该缓存行已经处于“已修改”或“独占”状态），因此它将“b”的新值存储在其缓存行中。

6. CPU 0 接收“读”消息，并将包含当前更新的“b”值的缓存行传输到 CPU 1，同时将该行标记为在自己的缓存中“共享”。

7. CPU 1 接收包含“b”的高速缓存行并将其安装到其高速缓存中。

8. CPU 1 现在可以完成 while(b==0) continue 的执行，并且由于它发现“b”的值为 1，因此它继续执行下一条语句，该语句现在是内存屏障。

9. CPU 1 现在必须停止运行，直到处理完其失效队列中所有预先存在的消息。

10. CPU 1 现在处理排队的“invalidate”消息，并使自己的缓存中包含“a”的缓存行无效。

11. CPU 1 执行断言（a==1），并且由于包含“a”的缓存行不再位于 CPU 1 的缓存中，因此它发送“读”消息。

12. CPU 0 使用包含新值“a”的高速缓存行响应此“读取”消息。

13. CPU 1 接收该缓存行，其中“a”的值为 1，因此不会触发断言。

通过大量 MESI 消息的传递，CPU 得出正确的答案，所以这就是为什么 CPU 设计者必须极其小心地进行缓存一致性优化。

7. 读写屏障分离

在上一节中，内存屏障用于标记存储缓冲区和无效队列中的条目。但在我们的代码片段中，foo() 没有理由对无效队列执行任何操作，而 bar() 同样没有理由对存储队列执行任何操作。

因此，许多 CPU 架构提供较弱的内存屏障指令，仅执行这两者中的一个或另一个。粗略地说，“读内存屏障”仅标记无效队列，“写内存屏障”仅标记存储缓冲区，而成熟的内存屏障则两者兼而有之。

这样做的效果是，读内存屏障仅命令执行它的 CPU 上的加载，因此读内存屏障之前的所有加载看起来都在读内存屏障之后的任何加载之前完成。类似地，写内存屏障仅对执行它的CPU上的存储进行排序，并且再次使得写内存屏障之前的所有存储看起来都在写内存屏障之后的任何存储之前完成。成熟的内存屏障对加载和存储进行排序，但同样仅在执行内存屏障的 CPU 上进行。

如果我们更新 foo 和 bar 以使用读写内存屏障，它们将显示如下：

1 void foo(void)

2{

3 a=1;

4 smp_wmb();

5 b=1;

6}

7

8 void bar(void)

9{

10 while (b == 0) continue;

11 smp_rmb();

12 assert(a == 1);

13 }

有些计算机甚至有更多类型的内存屏障，但了解这几种内存屏障能够更好的帮助你理解。