std :: atomic_compare_exchange_weak线程不安全吗？

Question

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

    lock
    cmpxchgq   %rcx, (%rsp)
    cmpq       %rdx, %rax

哪个(编辑:为红鲱道歉)

打破CAS循环,例如Concurrency in Action的清单7.2:

while(!head.compare_exchange_weak(new_node->next, new_node);

规范(29.6.5 [atomics.types.operations.req]/21-22)似乎暗示比较的结果必须是原子操作的一部分:

效果:原子比较......

返回:比较的结果

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

Answer 1

TL; DR:atomic_compare_exchange_weak在设计上是安全的,但实际的实现是错误的.

这是Clang实际为这个小片段生成的代码:

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)) {}
}

结果:

  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

比较非常安全:它只是比较寄存器.但是,整个操作并不安全.

关键点是:compare_exchange_(weak | strong)的描述说:

原子如果为真,则将内存点的内容替换为所需的内容,如果为false,则更新内存中的内容以及此内存所指向的内存.

或者在伪代码中:

if (*this == expected)
  *this = desired;
else
  expected = *this;

请注意,expected仅在比较为false时*this写入,并且仅在比较为true时写入.C++的抽象模型不允许在两者都被写入的情况下执行.这对于push上面的正确性很重要,因为如果写入head发生,突然new_node指向其他线程可见的位置,这意味着其他线程可以开始读取next(通过访问head->next),如果写入expected(其别名new_node->next)也发生了,这是一场比赛.

而Clang new_node->next无条件地写道.在比较为真的情况下,这是一个发明的写作.

这是Clang的一个错误.我不知道海湾合作委员会是否做同样的事情.

此外,该标准的措辞不是最理想的.它声称整个操作必须以原子方式进行,但这是不可能的,因为expected它不是原子对象; 写到那里不可能原子地发生.标准应该说的是比较和写入以*this原子方式发生,但写入expected不是.但这并不是那么糟糕,因为没有人真的希望写入是原子的.

所以应该有一个针对Clang(可能还有GCC)的错误报告,以及该标准的缺陷报告.

Answer 2

我是最初发现这个bug的人.在过去的几天里,我一直在向Anthony Williams发送关于此问题和供应商实施的电子邮件.我没有意识到Cubbi引发了StackOverFlow问题.不仅仅是Clang或GCC,每个供应商都被打破了(无论如何都是重要的).Anthony Williams也是Just :: Thread(一个C++ 11线程和原子库)的作者,他确认他的库正确实现(只知道正确的实现).

Anthony提出了GCC错误报告http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60272

简单的例子:

   #include <atomic>
   struct Node { Node* next; };
   void Push(std::atomic<Node*> head, Node* node)
   {
       node->next = head.load();
       while(!head.compare_exchange_weak(node->next, node))
           ;
   }

g ++ 4.8 [汇编程序]

       mov    rdx, rdi
       mov    rax, QWORD PTR [rdi]
       mov    QWORD PTR [rsi], rax
   .L3:
       mov    rax, QWORD PTR [rsi]
       lock cmpxchg    QWORD PTR [rdx], rsi
       mov    QWORD PTR [rsi], rax !!!!!!!!!!!!!!!!!!!!!!!
       jne    .L3
       rep; ret

铿锵3.3 [汇编]

       movq    (%rdi), %rcx
       movq    %rcx, (%rsi)
   .LBB0_1:
       movq    %rcx, %rax
       lock
       cmpxchgq    %rsi, (%rdi)
       movq    %rax, (%rsi) !!!!!!!!!!!!!!!!!!!!!!!
       cmpq    %rcx, %rax !!!!!!!!!!!!!!!!!!!!!!!
       movq    %rax, %rcx
       jne    .LBB0_1
       ret

icc 13.0.1 [汇编]

       movl      %edx, %ecx
       movl      (%rsi), %r8d
       movl      %r8d, %eax
       lock
       cmpxchg   %ecx, (%rdi)
       movl      %eax, (%rsi) !!!!!!!!!!!!!!!!!!!!!!!
       cmpl      %eax, %r8d !!!!!!!!!!!!!!!!!!!!!!!
       je        ..B1.7
   ..B1.4:
       movl      %edx, %ecx
       movl      %eax, %r8d
       lock
       cmpxchg   %ecx, (%rdi)
       movl      %eax, (%rsi) !!!!!!!!!!!!!!!!!!!!!!!
       cmpl      %eax, %r8d !!!!!!!!!!!!!!!!!!!!!!!
       jne       ..B1.4
   ..B1.7:
       ret

Visual Studio 2012 [无需检查汇编程序,MS使用_InterlockedCompareExchange !!!]

   inline int _Compare_exchange_seq_cst_4(volatile _Uint4_t *_Tgt, _Uint4_t *_Exp, _Uint4_t _Value)
   {    /* compare and exchange values atomically with
       sequentially consistent memory order */
       int _Res;
       _Uint4_t _Prev = _InterlockedCompareExchange((volatile long
*)_Tgt, _Value, *_Exp);
       if (_Prev == *_Exp) !!!!!!!!!!!!!!!!!!!!!!!
           _Res = 1;
       else
       { /* copy old value */
           _Res = 0;
           *_Exp = _Prev;
       }
       return (_Res);
   }