是std :: atomic_compare_exchange_weak线程不安全的设计？ [英] Is std::atomic_compare_exchange_weak thread-unsafe by design?

问题描述

这是在 cppreference atomic_compare_exchange Talk页面上提出的，现有的 std :: atomic_compare_exchange_weak 使用非原子比较指令计算CAS的布尔结果，例如

  lock 
 cmpxchgq％rcx，（％rsp）
 cmpq％rdx，％rax 
  

其中（编辑：为红色鲱鱼道歉）

：

  while（！head.compare_exchange_weak（new_node-> next，new_node）; 
  

规范（29.6.5 [atomics.types.operations.req] / 21-22）似乎意味着比较的结果必须作为原子操作的一部分：

效果：原子比较...

返回：比较结果

但实际上是可实现的吗？我们应该向供应商或LWG提交错误报告吗？

解决方案

TL; DR：atomic_compare_exchange_weak是设计安全的，

下面是Clang为这个小片段生成的代码：

  struct node {
 int data; 
 node * next; 
}; 
 
 std :: atomic< node *>头; 
 
 void push（int data）{
 node * new_node = new node {data}; 
 new_node-> next = head.load（std :: memory_order_relaxed）; 
 while（！head.compare_exchange_weak（new_node-> next，new_node，
 std :: memory_order_release，std :: memory_order_relaxed））{} 
} 
  
 
 
 
结果：
  ％ebx 
＃分配内存
 movl $ 16，％edi 
 callq _Znwm 
 movq％rax，％rcx 
＃初始化数据和0 
 movl％ ebx，（％rcx）
 movq $ 0，8（％rcx）;死存储，应该已经优化掉
＃用head.load覆盖下一个
 movq头（％rip），％rdx 
 movq％rdx，8（％rcx）
。 align 16，0x90 
 .LBB0_1：＃％while.cond 
＃=>此内循环标题：深度= 1 
＃将头的值置入比较/结果位置
 movq％rdx，％rax 
＃原子操作在这里，比较第二个参数％rax，存储第一个参数
＃在第二个如果相同，第二个在％rax否则
 lock 
 cmpxchgq％rcx，head（％rip）
＃无条件地将旧值写回下一个 - 等等，什么？ 
 movq％rax，8（％rcx）
＃检查cmpxchg是否修改结果位置
 cmpq％rdx，％rax 
 movq％rax，％rdx 
 .LBB0_1 
  
比较是完全安全的：它只是比较寄存器。但是，整个操作并不安全。
 
 
 
关键点是：compare_exchange_（weak | strong）的说明：
 
 
 Atomically [...]如果为true，用期望的内存点替换内存点的内容，如果为false，则更新内存的内容，由此
 
 
指向的内存的内容或以伪代码指向：
  if（* this == expected）
 * this = desired; 
 else 
 expected = * this; 
  
注意预期 strong>如果比较为假，而 *仅当比较为真时才会写入此。 C ++的抽象模型不允许两者都被写入的执行。这对于上面 push 的正确性很重要，因为如果写入头发生，突然new_node指向一个位置，这意味着其他线程可以开始读取 next （通过访问 head-> next ） ，如果写入预期（其中别名 new_node->下一个）也会发生，这是一场比赛。 / p> 
 
 
并且Clang无条件地写入 new_node-> next 。在比较是真的情况下，这是一个发明的写。
 
 
 
 这是Clang中的错误。我不知道GCC做同样的事情。
 
 
 
此外，标准的措辞是次优的。它声称整个操作必须以原子方式进行，但这是不可能的，因为 expected 不是一个原子对象;写入到那里不能原子地发生。标准应该说的是，比较和写入 * this 原子性地发生，但写入 expected 不。但是这不是那么糟糕，因为没有人真正期望写为原子无论如何。
 
 
 
所以应该有一个错误报告Clang（和可能的GCC）和标准的缺陷报告。
 
It was brought up on cppreference atomic_compare_exchange Talk page that the existing implementations of std::atomic_compare_exchange_weak compute the boolean result of the CAS with a non-atomic compare instruction, e.g.
    lock
    cmpxchgq   %rcx, (%rsp)
    cmpq       %rdx, %rax
which (Edit: apologies for the red herring)

break CAS loops such as Concurrency in Action's listing 7.2:
while(!head.compare_exchange_weak(new_node->next, new_node);
The specification (29.6.5[atomics.types.operations.req]/21-22) seems to imply that the result of the comparison must be a part of the atomic operation: 

  
Effects: atomically compares ...
  
  
Returns: the result of the comparison
but is it actually implementable? Should we file bug reports to the vendors or to the LWG?
解决方案
TL;DR: atomic_compare_exchange_weak is safe by design, but actual implementations are buggy.

Here's the code that Clang actually generates for this little snippet:
struct node {
  int data;
  node* next;
};

std::atomic<node*> head;

void push(int data) {
  node* new_node = new node{data};
  new_node->next = head.load(std::memory_order_relaxed);
  while (!head.compare_exchange_weak(new_node->next, new_node,
      std::memory_order_release, std::memory_order_relaxed)) {}
}
Result:
  movl  %edi, %ebx
  # Allocate memory
  movl  $16, %edi
  callq _Znwm
  movq  %rax, %rcx
  # Initialize with data and 0
  movl  %ebx, (%rcx)
  movq  $0, 8(%rcx) ; dead store, should have been optimized away
  # Overwrite next with head.load
  movq  head(%rip), %rdx
  movq  %rdx, 8(%rcx)
  .align  16, 0x90
.LBB0_1:                                # %while.cond
                                        # =>This Inner Loop Header: Depth=1
  # put value of head into comparand/result position
  movq  %rdx, %rax
  # atomic operation here, compares second argument to %rax, stores first argument
  # in second if same, and second in %rax otherwise
  lock
  cmpxchgq  %rcx, head(%rip)
  # unconditionally write old value back to next - wait, what?
  movq  %rax, 8(%rcx)
  # check if cmpxchg modified the result position
  cmpq  %rdx, %rax
  movq  %rax, %rdx
  jne .LBB0_1
The comparison is perfectly safe: it's just comparing registers. However, the whole operation is not safe.

The critical point is this: the description of compare_exchange_(weak|strong) says:

  
Atomically [...] if true, replace the contents of the memory point to by this with that in desired, and if false, updates the contents of the memory in expected with the contents of the memory pointed to by this
Or in pseudo-code:
if (*this == expected)
  *this = desired;
else
  expected = *this;
Note that expected is only written to if the comparison is false, and *this is only written to if comparison is true. The abstract model of C++ does not allow an execution where both are written to. This is important for the correctness of push above, because if the write to head happens, suddenly new_node points to a location that is visible to other threads, which means other threads can start reading next (by accessing head->next), and if the write to expected (which aliases new_node->next) also happens, that's a race.

And Clang writes to new_node->next unconditionally. In the case where the comparison is true, that's an invented write.

This is a bug in Clang. I don't know whether GCC does the same thing.

In addition, the wording of the standard is suboptimal. It claims that the entire operation must happen atomically, but this is impossible, because expected is not an atomic object; writes to there cannot happen atomically. What the standard should say is that the comparison and the write to *this happen atomically, but the write to expected does not. But this isn't that bad, because no one really expects that write to be atomic anyway.

So there should be a bug report for Clang (and possibly GCC), and a defect report for the standard.

                        
这篇关于是std :: atomic_compare_exchange_weak线程不安全的设计？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！