如何在 C++11 中实现 StoreLoad 屏障？

Question

我想编写解决经典问题变体的可移植代码（Intel、ARM、PowerPC...）：

Initially: X=Y=0

Thread A:
  X=1
  if(!Y){ do something }
Thread B:
  Y=1
  if(!X){ do something }

其中的目标是避免两个线程都在做something的情况。（如果两者都没有运行s 也没关系；这不是运行-exactly-once 机制。）如果您在下面的推理中发现一些缺陷，请纠正我。

我知道，我可以使用 memory_order_seq_cst 原子 stores 和 loads 实现目标，如下所示：

std::atomic<int> x{0},y{0};
void thread_a(){
  x.store(1);
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!x.load()) bar();
}

这就达到了目的，因为在
上肯定有一些单一的总订单 {x.store(1), y.store(1), y.load(), x.load()}个事件，必须符合程序顺序"edges":

x.store(1) "in TO is before" y.load()
y.store(1) "in TO is before" x.load()

如果 foo() 被调用，那么我们有额外的优势：

y.load() "reads value before" y.store(1)

如果调用了bar()，那么我们有额外的优势：

x.load() "reads value before" x.store(1)

所有这些边组合在一起将形成一个循环：

x.store(1) "in TO is before" y.load() "reads value before " y.store(1) "in TO is before" x.load() "reads value before" x.store(true)

这违反了订单没有周期的事实。

我故意使用非标准术语 "in TO is before" 和 "reads value before" 而不是像 happens-before 这样的标准术语，因为我想征求有关我的正确性的反馈假设这些边确实蕴含 happens-before 关系，可以在单个图中组合在一起，并且这种组合图中的循环是禁止的。我不确定。我所知道的是这段代码在 Intel gcc & clang 和 ARM gcc

上产生了正确的障碍

现在，我真正的问题有点复杂，因为我无法控制 "X" - 它隐藏在一些宏、模板等后面，可能比 seq_cst

我什至不知道 "X" 是单个变量还是其他概念（例如轻量级信号量或互斥量）。我所知道的是我有两个宏 set() 和 check() 这样 check() returns true "after" 另一个线程调用了 set(). （是也知道set和check是线程安全的，不能创建数据争用UB。）

所以概念上 set() 有点像 "X=1" 而 check() 就像 "X"，但我无法直接访问所涉及的原子，如果有的话。

void thread_a(){
  set();
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!check()) bar();
}

我担心，set() 可能在内部实现为 x.store(1,std::memory_order_release) and/or check() 可能是 x.load(std::memory_order_acquire)。或者假设 std::mutex 一个线程正在解锁而另一个线程正在 try_locking；在 ISO 标准中 std::mutex 只保证有获取和释放顺序，而不是 seq_cst.

如果是这种情况，那么 check() 的 if 正文可以是 y.store(true) 之前的 "reordered"（参见他们证明了这发生在 PowerPC).
这真的很糟糕，因为现在这一系列事件是可能的：

thread_b()首先加载x的旧值（0）
thread_a() 执行所有内容，包括 foo()
thread_b() 执行所有内容，包括 bar()

所以，foo() 和 bar() 都被调用了，我不得不避免。我有什么选择可以防止这种情况发生？

选项A

尝试强制存储加载屏障。实际上，这可以通过 std::atomic_thread_fence(std::memory_order_seq_cst); 来实现——正如 Alex in a different answer 所解释的那样，所有经过测试的编译器都发出了完整的栅栏：

x86_64: MFENCE

PowerPC: hwsync

Itanuim: mf

ARMv7 / ARMv8: dmb ish

MIPS64: sync

这种方法的问题是，我在 C++ 规则中找不到任何保证，即 std::atomic_thread_fence(std::memory_order_seq_cst) 必须转换为完整的内存屏障。实际上，C++ 中 atomic_thread_fence 的概念似乎与内存屏障的汇编概念处于不同的抽象级别，并且更多地处理诸如 "what atomic operation synchronizes with what" 之类的东西。有没有理论证明下面的实现可以达到目的？

void thread_a(){
  set();
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!y.load()) foo();
}
void thread_b(){
  y.store(true);
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!check()) bar();
}

选项 B

使用我们对 Y 的控制来实现同步，通过在 Y 上使用读-修改-写 memory_order_acq_rel 操作：

void thread_a(){
  set();
  if(!y.fetch_add(0,std::memory_order_acq_rel)) foo();
}
void thread_b(){
  y.exchange(1,std::memory_order_acq_rel);
  if(!check()) bar();
}

这里的想法是访问单个原子 (y) 必须形成一个所有观察者都同意的单一顺序，所以 fetch_add 在 exchange 之前或者反之-相反。

如果 fetch_add 在 exchange 之前，那么 fetch_add 的 "release" 部分与 exchange 的 "acquire" 部分同步，因此所有set() 的副作用必须对执行 check() 的代码可见，因此不会调用 bar()。

否则，exchange 在 fetch_add 之前，那么 fetch_add 将看到 1 而不会调用 foo()。所以，不可能同时调用foo()和bar()。这个推理正确吗？

选项 C

使用虚拟原子，引入"edges"防止灾难。考虑以下方法：

void thread_a(){
  std::atomic<int> dummy1{};
  set();
  dummy1.store(13);
  if(!y.load()) foo();
}
void thread_b(){
  std::atomic<int> dummy2{};
  y.store(1);
  dummy2.load();
  if(!check()) bar();
}

如果你认为这里的问题是 atomics 是局部的，那么想象一下将它们移动到全局范围，在下面的推理中它对我来说似乎无关紧要，我是故意的以这样的方式编写代码，以暴露 dummy1 和 dummy2 完全分开是多么有趣。

为什么这会奏效？好吧，必须有一些 {dummy1.store(13), y.load(), y.store(1), dummy2.load()} 的总顺序必须与程序顺序一致 "edges":

dummy1.store(13) "in TO is before" y.load()
y.store(1) "in TO is before" dummy2.load()

（seq_cst store + load 有望形成 C++ 等效的完整内存屏障，包括 StoreLoad，就像它们在真正的 ISA 上的 asm 中所做的那样，甚至包括不需要单独屏障指令的 AArch64。）

现在，我们有两种情况要考虑：y.store(1) 在总顺序中在 y.load() 之前或之后。

如果 y.store(1) 在 y.load() 之前，那么 foo() 将不会被调用，我们是安全的。

如果y.load()在y.store(1)之前，那么将它与我们在程序顺序中已有的两条边结合起来，我们推导出：

dummy1.store(13) "in TO is before" dummy2.load()

现在dummy1.store(13)是释放操作，释放set()的效果，而dummy2.load()是获取操作，所以check()应该看到效果set() 因此 bar() 不会被调用，我们是安全的。

这里认为 check() 会看到 set() 的结果是否正确？ 我可以这样组合各种"edges"（"program order" aka Sequenced Before, "total order", "before release", "after acquire"）吗？ 我对此深表怀疑：C++ 规则似乎在谈论 "synchronizes-with" 同一位置上存储和加载之间的关系 - 这里没有这种情况。

请注意，我们只担心已知（通过其他推理）在 dummy2.load 之前的情况 seq_cst总订单。因此，如果他们一直在访问同一个变量，负载就会看到存储的值并与之同步。

（原子加载和存储编译为至少单向内存屏障的实现的内存屏障/重新排序推理（并且 seq_cst 操作无法重新排序：例如 seq_cst 存储无法传递 seq_cst 负载）是 dummy2.load 之后的任何 loads/stores 肯定对其他线程可见在 y.store 之后。并且与另一个线程类似，...在 y.load.)

之前

您可以在 https://godbolt.org/z/u3dTa8

试玩我对选项 A、B、C 的实现

Answer 1

选项 A 和 B 是有效的解决方案。

选项 A：seq-cst 栅栏翻译成什么并不重要，C++ 标准明确定义了它提供的保证。我把它们放在这个 post 中：When is a memory_order_seq_cst fence useful?
选项B：是的，你的推理是正确的。对某个对象的所有修改都有一个总顺序（修改顺序），因此您可以使用它来同步线程并确保所有副作用的可见性。

但是，选项 C 无效！只能通过 acquire/release-operations 在同一对象 上建立同步关系。在您的情况下，您有两个完全不同且独立的对象 dummy1 和 dummy2。但是这些不能用于建立 happens-before 关系。事实上，由于原子变量是纯本地的（即，它们只被一个线程触及），编译器可以根据假设规则.[=自由删除它们。 32=]

更新

选项A：
我假设 set() 和 check() 确实对某些原子值进行操作。那么我们有如下情况（->表示sequenced-before）：

set()-> fence1(seq_cst) -> y.load()
y.store(true) -> fence2(seq_cst) -> check()

所以我们可以应用以下规则：

For atomic operations A and B on an atomic object M, where A modifies M and B takes its value, if there are memory_order_seq_cst fences X and Y such that A is sequenced before X, Y is sequenced before B, and X precedes Y in S, then B observes either the effects of A or a later modification of M in its modification order.

即，check() 看到存储在 set 中的值，或者 y.load() 看到写入的值是 y.store()（对 y 的操作可以甚至使用 memory_order_relaxed).

选项 C:
C++17 standard 声明 [32.4.3, p1347]:

There shall be a single total order S on all memory_order_seq_cst operations, consistent with the "happens before" order and modification orders for all affected locations [...]

这里的重点是"consistent"。这意味着如果操作 A 发生在操作 B 之前，则 A 必须先于 [= S 中的 50=]B。然而，逻辑蕴涵是单向的，所以我们不能推导出相反的结论：仅仅因为某些操作 C 在操作 D 之前 S 并不意味着 C 发生在 D.

之前

特别是，即使操作在 S 中完全有序，也不能使用对两个单独对象的两个 seq-cst 操作来建立发生在关系之前。 如果你想要在单独的对象上排序操作，您必须参考 seq-cst-fences（参见选项 A）。

Answer 2

在第一个示例中，y.load() 读数为 0 并不意味着 y.load() 发生在 y.store(1) 之前。

它确实暗示它在单个总订单中较早，这要归功于 seq_cst 加载 returns 总计中最后一个 seq_cst 存储的值的规则order，或者在它之前没有发生的一些非 seq_cst 存储的值（在这种情况下不存在）。因此，如果 y.store(1) 在总顺序中早于 y.load()，则 y.load() 将返回 1。

证明仍然正确，因为单个总订单没有循环。

这个解决方案怎么样？

std::atomic<int> x2{0},y{0};

void thread_a(){
  set();
  x2.store(1);
  if(!y.load()) foo();
}

void thread_b(){
  y.store(1);
  if(!x2.load()) bar();
}

Answer 3

@mpoeter 解释了为什么选项 A 和 B 是安全的。

在实际实现的实践中，我认为选项 A 在线程 A 中只需要 std::atomic_thread_fence(std::memory_order_seq_cst)，而不是 B。

seq-cst 存储在实践中包括一个完整的内存屏障，或者在 AArch64 上至少不能用以后的获取或 seq_cst 加载重新排序（stlr 顺序释放必须从在 ldar 可以从缓存中读取之前存储缓冲区。

C++ -> asm mappings 可以选择将耗尽存储缓冲区的成本放在原子存储或原子加载上。实际实现的明智选择是使原子加载便宜，因此 seq_cst 存储包含一个完整的屏障（包括 StoreLoad）。虽然 seq_cst 负载与获取负载相同。

（但不是 POWER；甚至负载需要重量级同步 = 完全屏障来停止来自同一核心上其他 SMT 线程的存储转发，这可能导致 IRIW 重新排序，因为 seq_cst 需要所有线程能够就所有 seq_cst 操作的顺序达成一致。)

（当然，为了 正式保证 安全，我们确实需要在两者中设置栅栏以将 acquire/release set() -> check() 提升为 seq_cst 同步。我认为也适用于宽松的集合，但宽松的检查可以从其他线程的 POV 重新排序。）

我认为选项 C 的真正问题在于它取决于某些假设的观察者，即可以与 y 同步和虚拟操作. 因此我们希望编译器在为基于屏障的 ISA 制作 asm 时保留该顺序，其中有一个单一的连贯共享内存状态和屏障命令此 core/thread 对该共享的访问状态。另请参阅以了解有关此模型与 stdatomic 同步排序模型的更多信息，用于弱于 seq_cst 的障碍。

在真正的 ISA 上，这将成为现实；两个线程都包含一个完整的屏障或等效物，并且编译器（还）没有优化原子。但是当然 "compiling to a barrier-based ISA" 不是 ISO C++ 标准的一部分。 一致性共享缓存是存在于 asm 推理而非 ISO C++ 推理的假设观察者。

要使选项 C 起作用，我们需要像 dummy1.store(13); / y.load() / set(); 这样的顺序（如线程 B 所见）违反某些 ISO C++规则.

线程运行这些语句必须表现得 就好像 set() 首先执行（因为 Sequenced Before）。没关系，运行时内存排序 and/or 编译时操作的重新排序仍然可以做到这一点。

两个seq_cst操作d1=13和y与Sequenced Before（程序顺序）一致。 set() 不参与 seq_cst 操作所需的存在全局顺序，因为它不是 seq_cst.

线程 B 不与 dummy1.store 同步，因此 set 相对于 d1=13 的 happens-before 要求不适用 ，甚至尽管该分配是释放操作。

我没有发现任何其他可能的违规行为；我在这里找不到任何需要与 set Sequenced-Before d1=13.

一致的东西

"dummy1.store releases set()" 推理是错误的。该排序仅适用于与其同步的真实观察者，或在 asm. 中，正如@mpoeter 回答的那样，seq_cst 总顺序的存在不会创建或暗示发生在关系之前，这是唯一正式保证在 seq_cst.

之外订购的东西

任何类型的 "normal" CPU 具有连贯的共享缓存，这种重新排序可能在运行时真正发生的情况似乎不太合理。（但是如果编译器可以删除 dummy1 和 dummy2 那么显然我们会有问题，我认为这是标准允许的。）

但是由于 C++ 内存模型不是根据存储缓冲区、共享一致缓存或允许重新排序的石蕊测试来定义的，因此 C++ 规则没有正式要求健全性要求的东西。这可能是有意允许优化甚至 seq_cst 结果是线程私有的变量。（当然，当前的编译器不这样做，也不对原子对象进行任何其他优化。）

一个线程真正可以最后看到 set() 而另一个线程可以首先看到 set() 的实现听起来难以置信。甚至 POWER 也做不到。 seq_cst 加载和存储都包含 POWER 的完整障碍。（我在评论中建议 IRIW 重新排序可能与此相关；C++ 的 acq/rel 规则足够弱以适应这一点，但在同步或其他发生之前的情况之外完全缺乏保证比任何情况都弱得多硬件。)

C++ 不为非 seq_cst 提供任何保证，除非实际上是一个观察者，然后仅针对该观察者。 没有一个，我们就在薛定谔的猫领地里。或者，如果森林里有两棵树倒下，一棵先倒下吗？（如果它是一片大森林，广义相对论说它取决于观察者并且没有普遍的同时性概念。）

@mpoeter 建议编译器甚至可以删除虚拟加载和存储操作，即使在 seq_cst 对象上也是如此。

我认为当他们能够证明没有任何东西可以与操作同步时，这可能是正确的。例如可以看到 dummy2 没有转义函数的编译器可能会删除 seq_cst 负载。

这至少有一个现实世界的后果：如果为 AArch64 编译，这将允许较早的 seq_cst 商店在实践中重新排序，后来的宽松操作，这在 seq_cst store + load 在执行任何后续加载之前耗尽存储缓冲区。

当然，当前的编译器根本不优化原子，即使 ISO C++ 不禁止它； that's an unsolved problem 代表标准委员会。

我认为这是允许的，因为 C++ 内存模型没有隐式观察器或所有线程都同意排序的要求。它确实提供了一些基于一致性缓存的保证，但它不需要同时对所有线程可见。

Answer 4

in the ISO standard std::mutex is only guaranteed to have acquire and release ordering, not seq_cst.

但没有任何东西可以保证 "seq_cst ordering"，因为 seq_cst 不是任何操作的属性。

seq_cst 是对 std::atomic 或替代原子 class 的给定实现的所有操作的保证。因此，你的问题是不合理的。

如何在 C++11 中实现 StoreLoad 屏障？

How to achieve a StoreLoad barrier in C++11?

c++

atomic

memory-barriers

language-lawyer

stdatomic