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

[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.

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

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-02-19
     Ever confirmed|0                           |1

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

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org,
                   |                            |rth at gcc dot gnu.org,
                   |                            |torvald at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Even our __atomic_compare_exchange* documentation states that:
If they are not equal, the current contents of
@code{*@var{ptr}} is written into @code{*@var{expected}}.
But then expand_builtin_atomic_compare_exchange doesn't care:
  oldval = expect;
  if (!expand_atomic_compare_and_swap ((target == const0_rtx ? NULL : &target),
                                       &oldval, mem, oldval, desired,
                                       is_weak, success, failure))
    return NULL_RTX;

  if (oldval != expect)
    emit_move_insn (expect, oldval);

That effectively means that expect will be stored unconditionally.
So, either we'd need to change this function, so that it sets oldval to
NULL_RTX
first, and passes ..., &oldval, mem, expected, ... and needs to also always ask
for target, then conditionally on target store to expected, or perhaps add
extra parameter to expand_atomic_compare_and_swap and do the store only
conditionally in that case.  Richard/Torvald?

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

[torvald at gcc dot gnu.org]

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

--- Comment #2 from torvald at gcc dot gnu.org ---
(In reply to Jakub Jelinek from comment #1)
> So, either we'd need to change this function, so that it sets oldval to
> NULL_RTX
> first, and passes ..., &oldval, mem, expected, ... and needs to also always
> ask for target, then conditionally on target store to expected, or perhaps
> add extra parameter to expand_atomic_compare_and_swap and do the store only
> conditionally in that case.  Richard/Torvald?

I'm not sure what's better.  But getting this fixed in 4.9.0 would be good! :)

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

[rth at gcc dot gnu.org]

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

Richard Henderson <rth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |rth at gcc dot gnu.org

--- Comment #3 from Richard Henderson <rth at gcc dot gnu.org> ---
Agreed.  Mine.

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

[rth at gcc dot gnu.org]

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

--- Comment #4 from Richard Henderson <rth at gcc dot gnu.org> ---
Author: rth
Date: Thu Feb 20 17:43:53 2014
New Revision: 207966

URL: http://gcc.gnu.org/viewcvs?rev=207966&root=gcc&view=rev
Log:
PR c++/60272

gcc/
    * builtins.c (expand_builtin_atomic_compare_exchange): Conditionalize
    on failure the store back into EXPECT.
libatomic/
    * cas_n.c (libat_compare_exchange): Conditionalize on failure
    the store back to EPTR.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/builtins.c
    trunk/libatomic/ChangeLog
    trunk/libatomic/cas_n.c

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

[rth at gcc dot gnu.org]

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

--- Comment #5 from Richard Henderson <rth at gcc dot gnu.org> ---
Author: rth
Date: Fri Feb 21 00:11:43 2014
New Revision: 207972

URL: http://gcc.gnu.org/viewcvs?rev=207972&root=gcc&view=rev
Log:
PR c++/60272

        * builtins.c (expand_builtin_atomic_compare_exchange): Always make
        a new pseudo for OLDVAL.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/builtins.c

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

[rth at gcc dot gnu.org]

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

--- Comment #6 from Richard Henderson <rth at gcc dot gnu.org> ---
Author: rth
Date: Fri Feb 21 00:14:05 2014
New Revision: 207973

URL: http://gcc.gnu.org/viewcvs?rev=207973&root=gcc&view=rev
Log:
PR c++/60272

gcc/
    * builtins.c (expand_builtin_atomic_compare_exchange): Conditionalize
    on failure the store back into EXPECT.
libatomic/
    * cas_n.c (libat_compare_exchange): Conditionalize on failure
    the store back to EPTR.

Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/builtins.c
    branches/gcc-4_8-branch/libatomic/ChangeLog
    branches/gcc-4_8-branch/libatomic/cas_n.c

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

[rth at gcc dot gnu.org]

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

Richard Henderson <rth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |4.8.3

--- Comment #7 from Richard Henderson <rth at gcc dot gnu.org> ---
Fixed.