[LLVMbugs] [Bug 18899] New: atomic::compare_exchange_weak invents a write on success

bugzilla-daemon at llvm.org bugzilla-daemon at llvm.org
Wed Feb 19 05:08:44 PST 2014


http://llvm.org/bugs/show_bug.cgi?id=18899

            Bug ID: 18899
           Summary: atomic::compare_exchange_weak invents a write on
                    success
           Product: clang
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: C++11
          Assignee: unassignedclangbugs at nondot.org
          Reporter: sebastian.redl at getdesigned.at
                CC: dgregor at apple.com, llvmbugs at cs.uiuc.edu
    Classification: Unclassified

The standard says that compare_exchange_* writes to the atomic object
(atomically) if the comparison of the current value and `expected` is true, and
to `expected` (also, if you interpret the wording literally, atomically, but
this is impossible since `expected` is not an atomic object) if the comparison
is false. So in response to this SO thread:

http://stackoverflow.com/questions/21879331/is-stdatomic-compare-exchange-weak-thread-unsafe-by-design/21881095#21881095

I wrote a little test:

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

Here's the code Clang generates (clang++ -std=c++11 -S -O2):

  .globl  _Z4pushi
  .align  16, 0x90
  .type _Z4pushi, at function
_Z4pushi:                               # @_Z4pushi
  .cfi_startproc
# BB#0:                                 # %entry
  pushq %rbx
.Ltmp2:
  .cfi_def_cfa_offset 16
.Ltmp3:
  .cfi_offset %rbx, -16
  # Allocate and initialize node
  movl  %edi, %ebx
  movl  $16, %edi
  callq _Znwm
  movq  %rax, %rcx
  movl  %ebx, (%rcx)
  movq  $0, 8(%rcx)
  # new_node->next = head.load(...)
  movq  head(%rip), %rdx
  movq  %rdx, 8(%rcx)
  .align  16, 0x90
.LBB0_1:                                # %while.cond
                                        # =>This Inner Loop Header: Depth=1
  # compare_exchange
  movq  %rdx, %rax
  lock
  cmpxchgq  %rcx, head(%rip)
  # Problematic: Writing back to `expected`
  movq  %rax, 8(%rcx)
  cmpq  %rdx, %rax
  movq  %rax, %rdx
  jne .LBB0_1
# BB#2:                                 # %while.end
  popq  %rbx
  ret
.Ltmp4:
  .size _Z4pushi, .Ltmp4-_Z4pushi
  .cfi_endproc

Note that Clang writes to `expected` unconditionally. In theory, %rax contains
the same thing as 8(%rcx); however, it is still an invented write if the
comparison is successful. This is bad. Note that if there is another thread
that loops, waiting for `head` to be non-null, and then immediately grabs it
and reads and/or writes to head->next, that operation races with the write to
`expected`. More concretely, if the pushing thread is pre-empted immediately
after the cmpxchg, head already has the new value. A different thread could now
overwrite `head->next`. When the pushing thread continues, it will overwrite
`expected` (which aliases `head->next`) again, losing the update from the other
thread.

The integrity of compare_exchange_weak uses relies on the idea that if the
comparison succeeds, the data has been published and must not be modified
anymore. But Clang inserts the spurious write, unseen by the programmer.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20140219/4770e2f8/attachment.html>


More information about the llvm-bugs mailing list