提问者:小点点

什么正式保证非原子变量不能看到凭空的值并创建像原子放松理论上可以的数据竞赛?


这是一个关于C标准的形式保证的问题。

该标准指出,std::memory_order_relaxed原子变量的规则允许出现“无中生有”/“出乎意料”的值。

但是对于非原子变量,这个例子可以有UB吗?r1==r2==42在C抽象机器中可能吗?最初都不是变量==42,所以如果body应该执行,你会期望都不是,这意味着不会写入共享变量。

// Global state
int x = 0, y = 0;

// Thread 1:
r1 = x;
if (r1 == 42) y = r1;

// Thread 2:
r2 = y;
if (r2 == 42) x = 42;

上面的示例改编自标准,该标准明确表示原子对象规范允许此类行为:

[注意:在以下示例中,要求确实允许r1==r2==42,x和y最初为零:

// Thread 1:
r1 = x.load(memory_order_relaxed);
if (r1 == 42) y.store(r1, memory_order_relaxed);
// Thread 2:
r2 = y.load(memory_order_relaxed);
if (r2 == 42) x.store(42, memory_order_relaxed);

但是,实现不应该允许这种行为。

所谓的“内存模型”的哪一部分保护非原子对象免受读取看到凭空值引起的这些交互?

xy存在具有不同值的竞争条件时,什么保证对共享变量(正常、非原子)的读取看不到这些值?

如果主体创建导致数据竞争的自我实现条件,不能执行吗?


共3个答案

匿名用户

你的问题的文本似乎没有抓住例子的重点和无中生有的值。你的例子不包含数据竞争UB。(如果在这些线程运行之前将xy设置为42,在这种情况下,所有赌注都取消,其他引用数据竞争UB的答案也适用。)

没有针对真实数据竞争的保护,只有针对无中生有的值。

我想你真的在问如何协调mo_relaxed示例与非原子变量的理智和明确定义的行为。这就是这个答案所涵盖的。

这个差距(我认为)不适用于非原子对象,只适用于mo_relaxed

他们说,然而,实现不应该允许这样的行为。-结束注释]。显然,标准委员会找不到一种方法来正式化这个要求,所以现在它只是一个注释,但不是可选的。

很明显,尽管这不是严格的规范,但C标准打算禁止松弛原子的凭空值(一般来说,我假设)。后来的标准讨论,例如2018年的p0668r5:修订C内存模型(它没有“修复”这个问题,这是一个不相关的变化)包括有趣的侧节点,如:

我们仍然没有一个可接受的方法来使我们非正式的(自C 14以来)禁止无中生有的结果精确。这样做的主要实际效果是使用松弛原子对C程序进行正式验证仍然不可行。上面的论文提出了一个类似于http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3710.html的解决方案。我们继续忽略这里的问题…

所以是的,标准的规范部分对于relaxed_atomic来说显然比对于非原子的弱。这似乎是他们如何定义规则的不幸副作用。

AFAIK在现实生活中,没有任何实现可以产生无中生有的价值。

标准短语非正式建议的较后版本更加明确,例如在当前草案中:https://timsong-cpp.github.io/cppwp/atomics.order#8

[注意:在以下示例中,[8.]的建议同样不允许r1==r2==42,x和y最初也是零:

   // Thread 1:
   r1 = x.load(memory_order::relaxed);
   if (r1 == 42) y.store(42, memory_order::relaxed);
   // Thread 2:
   r2 = y.load(memory_order::relaxed);
   if (r2 == 42) x.store(42, memory_order::relaxed);

-结束说明]

(其余的答案是在我确定标准也不允许mo_relaxed这样做之前写的。)

我很确定C抽象机器不允许r1==r2==42
C抽象机器操作中每一个可能的操作排序都会导致r1=r2=0没有UB,即使没有同步。因此程序没有UB,任何非零结果都会违反“as if”规则。

形式上,ISOC允许实现以任何方式实现函数/程序,以提供与C抽象机相同的结果。对于多线程代码,实现可以选择一种可能的抽象机排序,并决定总是发生的排序。(例如,当编译为强有序ISA时重新排序松弛的原子存储时。编写的标准甚至允许合并原子存储,但编译器选择不这样做)。但是程序的结果总是必须是抽象机器可以产生的。(只有原子章节介绍了一个线程在没有互斥体的情况下观察另一个线程的操作的可能性。否则,如果没有数据竞争UB,这是不可能的)。

我认为其他答案对此不够仔细。(当它第一次发布时,我也没有)。不执行的代码不会导致UB(包括数据竞争UB),编译器不允许发明对对象的写入。(除非在已经无条件写入它们的代码路径中,比如y=(x==42)?42: y;这显然会创建数据竞争UB。)

对于任何非原子对象,如果没有真正写入它,那么其他线程也可能正在读取它,而不管未执行的中的代码是否阻塞。标准允许这样做,并且不允许在抽象机器没有写入变量时突然将其读取为不同的值。(对于我们甚至不读取的对象,例如相邻的数组元素,另一个线程甚至可能正在编写它们。)

因此,我们不能做任何事情,让另一个线程暂时看到对象的不同值,或者踩在它的写上。发明对非原子对象的写入基本上总是编译器bug;这是众所周知的,也是普遍同意的,因为它可以破坏不包含UB的代码(并且在实践中已经这样做了一些创建它的编译器错误的案例,例如IA-64GCC我认为有这样的bug在某一点上破坏了Linux内核)。IIRC,Herb Sutter在他演讲的第一部分或第二部分提到了这样的错误,原子

或者另一个最近使用ICC for x86的示例:使用icc崩溃:编译器可以在抽象机器中不存在的地方发明写入吗?

在C抽象机器中,无论分支条件的加载顺序或同时性如何,执行都无法达到y=r1;x=r2;xy都读取为0,并且两个线程都没有写入它们。

不需要同步来避免UB,因为没有抽象机器操作的顺序会导致数据竞争。ISOC标准没有任何关于推测执行或错误推测到达代码时会发生什么的内容。这是因为推测是真实实现的一个特性,而不是抽象机器的特性。由实现(硬件供应商和编译器编写者)来确保“假设”规则得到尊重。

在C语言中,编写像这样的代码是合法的,如果(global_id==mine)shared_var=123;并让所有线程执行它,只要最多有一个线程实际运行shared_var=123;语句。(只要存在同步以避免非原子intglobal_id上的数据竞争)。如果这样的事情发生故障,那将是混乱的。例如,你显然可以得出错误的结论,比如在C中重新排序原子操作

观察到未发生非写入不是数据竞争UB。

如果(i)运行也不是UB

我认为“出乎意料”的价值发明说明只适用于松弛原子,显然是作为原子一章中对它们的特殊警告。(即使这样,AFAIK它实际上也不会发生在任何真正的C实现上,当然也不会发生在主流实现上。在这一点上,实现不必采取任何特殊措施来确保它不会发生在非原子变量上。)

我不知道在标准的原子章节之外有任何类似的语言允许实现允许值像这样突然出现。

我看不出有任何理智的方式可以争辩说C抽象机器在执行此操作时的任何时候都会导致UB,但是看到r1==r2==42会暗示发生了不同步的读写,但这是数据竞争UB。如果这种情况可能发生,实现可以因为推测执行(或其他原因)而发明UB吗?答案必须是“否”,C标准才能使用。

对于轻松的原子,凭空发明42并不意味着UB已经发生;也许这就是为什么标准说它是规则允许的?据我所知,除了标准的原子章节之外,没有任何东西允许它。

(没有人希望这样,希望每个人都同意构建这样的硬件是个坏主意。当检测到错误预测或其他错误猜测时,将逻辑内核之间的猜测耦合起来似乎不太可能值得回滚所有内核。)

为了使42成为可能,线程1必须看到线程2的推测存储,线程1的存储必须被线程2的负载看到。(确认分支推测是好的,允许这条执行路径成为实际采取的真实路径。)

即跨线程的推测:如果它们在同一个内核上运行,并且只有轻量级上下文切换,则在当前HW上是可能的,例如协程或绿色线程。

但是在当前的HW上,在这种情况下,线程之间的内存重新排序是不可能的。在同一个内核上乱序执行代码会给人一种一切都按程序顺序发生的错觉。要获得线程之间的内存重新排序,它们需要在不同的内核上运行。

因此,我们需要一个将两个逻辑内核之间的推测耦合在一起的设计。没有人这样做,因为这意味着如果检测到错误预测,需要回滚更多的状态。但这在假设上是可能的。例如,一个OoO SMT内核,它允许逻辑内核之间的存储转发,甚至在它们从无序内核退出之前(即变得非推测)。

PowerPC允许停用存储的逻辑内核之间的存储转发,这意味着线程可以对存储的全局顺序产生分歧。但是等到它们“毕业”(即退休)并变得不可推测意味着它不会将对单独逻辑内核的推测联系在一起。因此,当一个人从分支丢失中恢复时,其他人可以让后端保持忙碌。如果他们都必须回滚任何逻辑核心上的错误预测,那将破坏SMT的很大一部分好处。

我想了一会儿,我发现了一个排序,导致了一个真正的弱排序CPU的单核(线程之间的用户空间上下文切换),但是最后一步存储不能转发到第一步加载,因为这是程序顺序,OoO exec保留了它。

>

  • T2:r2=y;失速(例如缓存未命中)

    T2:分支预测预测r2==42将为真。(x=42应该运行。

    t2:x=42运行。(仍然推测;r2=y尚未获得值,因此r2==42'比较/分支仍在等待确认猜测)。

    上下文切换到线程1时,不会将CPU回滚到停用状态,也不会等待猜测被确认为良好或检测为错误猜测。

    这部分不会发生在真正的C实现上,除非它们使用M: N线程模型,而不是更常见的1:1 C线程来OS线程。真正的CPU不会重命名权限级别:它们不会接受中断或以其他方式进入内核,并带有可能需要从不同的架构状态回滚和重做进入内核模式的推测性指令。

    t1:r1=x;从推测的x=42存储中获取其值

    t1:r1==42被发现是真的。(分支推测也发生在这里,实际上不是等待商店转发完成。但是沿着这条执行路径,在x=42确实发生的地方,这个分支条件将执行并确认预测)。

    T1:y=42运行。

    这都是在同一个CPU上的,所以这个y=42存储在r2=y加载之后;它不能给那个加载一个42来让r2==42猜测得到确认。所以这种可能的顺序毕竟不能在实际操作中证明这一点。这就是为什么线程必须在不同的内核上运行,并在线程间进行猜测,这样的效果才是可能的。

    请注意,x=42r2没有数据依赖,因此不需要值预测来实现这一点。无论如何,y=r1都在if(r1==42)中,因此编译器可以根据需要优化到y=42,从而打破其他线程中的数据依赖关系并使事物对称。

    请注意,关于单个内核上的绿色线程或其他上下文切换的参数实际上并不相关:我们需要单独的内核来重新排序内存。

    我之前评论说,我认为这可能涉及到值预测。ISOC标准的内存模型肯定足够弱,可以允许值预测可以创建的各种疯狂的“重新排序”来使用,但这不是这种重新排序所必需的。y=r1可以优化为y=42,并且原始代码无论如何都包含x=42,因此该存储对r2=y负载没有数据依赖。42的推测存储很容易在没有值预测的情况下实现。(问题是让另一个线程看到它们!)

    因为分支预测而不是值预测而进行推测在这里具有相同的效果。并且在这两种情况下,负载最终都需要看到42以确认推测是正确的。

    价值预测甚至无助于使这种重新排序更加合理。我们仍然需要线程间推测和内存重新排序,以使两个推测存储相互确认并引导它们自己存在。

    ISOC选择允许松弛原子,但是AFAICT不允许这个非原子变量。除了说明没有明确禁止之外,我不确定我是否确切地看到标准中允许ISOC中的松弛原子情况。如果有任何其他代码对xy做了任何事情,那么也许,但我认为我的论点也适用于松弛原子情况。C抽象机器中通过源代码的路径无法产生它。

    正如我所说的,这在实践中是不可能的AFAIK在任何真正的硬件上(在asm中),或者在任何真正的C实现上。这更像是一个有趣的思想实验,研究非常弱的排序规则的疯狂后果,比如C的松弛原子(那些排序规则不允许它,但我认为假设规则和标准的其余部分不允许它,除非有一些规定允许松弛原子读取从未由任何线程实际写入的值。)

    如果有这样的规则,它只适用于松弛的原子,而不是非原子变量。数据竞争UB几乎是标准需要说的关于非原子变量和内存排序的所有内容,但我们没有。

  • 匿名用户

    当竞争条件可能存在时,什么保证共享变量(正常、非原子)的读取看不到写入

    没有这样的保证。

    当竞争条件存在时,程序的行为是未定义的:

    [引入.种族]

    两个操作可能是并发的,如果

    • 它们由不同的线程执行,或者
    • 它们是无序的,至少一个由信号处理程序执行,并且它们不都是由同一个信号处理程序调用执行的。

    如果程序的执行包含两个潜在的并发冲突操作,其中至少一个不是原子的,并且两者都不会在另一个之前发生,则程序的执行包含数据竞争。下面描述的信号处理程序的特殊情况除外。任何这样的数据竞争都会导致未定义的行为。…

    这个特殊情况与这个问题不是很相关,但为了完整起见,我会包括它:

    如果两个访问都发生在同一个线程中,即使一个或多个发生在信号处理程序中,对相同类型的对象的两次访问d::sig_atomic_t也不会导致数据竞争。…

    匿名用户

    所谓的“内存模型”的哪一部分保护非原子对象免受看到交互的读取引起的这些交互?

    没有。事实上,你会得到相反的结果,标准明确地将其称为未定义的行为。在[intr.种族]\21中,我们有

    如果程序的执行包含两个潜在的并发冲突操作,其中至少一个不是原子的,并且两者都不会在另一个之前发生,则程序的执行包含数据竞争。下面描述的信号处理程序的特殊情况除外。任何这样的数据竞争都会导致未定义的行为。

    这涵盖了您的第二个示例。

    规则是,如果您在多个线程中共享数据,并且这些线程中至少有一个写入了该共享数据,那么您需要同步。否则,您将出现数据竞争和未定义的行为。请注意易失性不是有效的同步机制。您需要原子/mutexs/条件变量来保护共享访问。

    相关问题