[Bug c++/60272] New: atomic<>::compare_exchange_weak has spurious store and can cause race conditions

[anthony.ajw at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60272

            Bug ID: 60272
           Summary: atomic<>::compare_exchange_weak has spurious store and
                    can cause race conditions
           Product: gcc
           Version: 4.8.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: anthony.ajw at gmail dot com

Created attachment 32170
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32170&action=edit
Sample code that demonstrates the problem

G++ 4.8.1 is producing incorrect code for std::atomic<>::compare_exchange_weak
on x86-64 linux.

In particular, if the exchange succeeds, then there is an additional spurious
store to the "expected" parameter after the exchange, which may race with other
threads and cause problems.

e.g.

#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))
        ;
}

When compiled with

g++-4.8 -S -std=c++11 -pthread -O3 t.cpp

the generated code is:

    movq    (%rdi), %rax
    movq    %rax, (%rsi)
    movq    (%rsi), %rax
    .p2align 4,,10
    .p2align 3
.L3:
    lock; cmpxchgq    %rsi, (%rdi)
    movq    %rax, (%rsi) *******
    jne    .L3
    rep; ret

The line marked ******* is an unconditional store to node->next in this
example, and will be executed even if the exchange is successful.

This will cause a race with code that uses the compare-exchange to order memory
operations.

e.g.

void Pop(std::atomic<Node*>& head){
    for(;;){
        Node* value=head.exchange(nullptr);
        if(value){
            delete value;
            break;
        }
    }
}

If the exchange successfully retrieves a non-null value, it should be OK to
delete it (assuming the node was allocated with new). However, if one thread is
calling Push() and is suspended after the CMPXCHG and before the line marked
******* is executed then another thread running Pop() can successfully complete
the exchange and call delete. When the first thread is resumed, the line marked
******* will then store to deallocated memory.

This is in contradiction to 29.6.5p21 of the C++ Standard, which states that
"expected" is only updated in the case of failure.