Bug 60272 - atomic<>::compare_exchange_weak has spurious store and can cause race conditions
Summary: atomic<>::compare_exchange_weak has spurious store and can cause race conditions
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 4.8.1
: P3 normal
Target Milestone: 4.8.3
Assignee: Richard Henderson
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-02-19 11:04 UTC by Anthony Williams
Modified: 2016-06-04 22:16 UTC (History)
6 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2014-02-19 00:00:00


Attachments
Sample code that demonstrates the problem (207 bytes, text/x-c++src)
2014-02-19 11:04 UTC, Anthony Williams
Details
Example code that still triggers this bug. (626 bytes, text/x-csrc)
2016-06-04 07:36 UTC, Max Wittal
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Anthony Williams 2014-02-19 11:04:54 UTC
Created attachment 32170 [details]
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.
Comment 1 Jakub Jelinek 2014-02-19 12:27:44 UTC
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?
Comment 2 torvald 2014-02-19 18:19:41 UTC
(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! :)
Comment 3 Richard Henderson 2014-02-19 18:34:30 UTC
Agreed.  Mine.
Comment 4 Richard Henderson 2014-02-20 17:44:26 UTC
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
Comment 5 Richard Henderson 2014-02-21 00:12:14 UTC
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
Comment 6 Richard Henderson 2014-02-21 00:14:37 UTC
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
Comment 7 Richard Henderson 2014-02-21 00:17:13 UTC
Fixed.
Comment 8 Max Wittal 2016-06-04 07:36:46 UTC
Created attachment 38642 [details]
Example code that still triggers this bug.
Comment 9 Max Wittal 2016-06-04 07:40:30 UTC
I still get this bug in gcc version 5.2.1 20151010 on x86_64-linux-gnu.

Please see attached code.
Comment 10 Max Wittal 2016-06-04 22:16:39 UTC
Sorry, I'm pretty sure now that there is some hard to find bug in my code, like the ABA problem.

Please disregard my comment above.