c++ - std::atomic_compare_exchange_weak 是线程不安全的设计吗？

Question

它是在 cppreference atomic_compare_exchange Talk page 上提出的std::atomic_compare_exchange_weak 的现有实现 使用非原子比较指令计算 CAS 的 bool 结果，例如

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

which(编辑:为红鲱鱼道歉)

break CAS 循环，例如 Concurrency in Action 的 list 7.2:

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

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

Effects: atomically compares ...

Returns: the result of the comparison

但它真的可以实现吗？我们应该向供应商或 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)的描述说:

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

或者在伪代码中:

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

注意 expected 仅在比较为 false 时写入到 ，而 *this 仅在比较为 false 时写入到 真的。 C++ 的抽象模型不允许同时写入两者的执行。这对于上面 push 的正确性很重要，因为如果发生对 head 的写入，突然 new_node 指向一个对其他线程可见的位置，这意味着其他线程可以开始读取next(通过访问head->next)，如果写入expected(别名为new_node->next) 也会发生，这是一场竞赛。

并且 Clang 无条件地写入 new_node->next。如果比较为真，那就是虚构的写法。

这是 Clang 中的一个错误。我不知道 GCC 是否也这样做。

此外，标准的措辞并不理想。它声称整个操作必须原子地发生，但这是不可能的，因为 expected 不是原子对象；写入那里不能原子发生。标准应该说的是比较和写入 *this 是原子发生的，但写入 expected 不会。但这并没有那么糟糕，因为没有人真正期望写入是原子的。

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