ISO/IEC JTC1 SC22 WG21 N3196 =わ 10-ひく0186 -ひく 2010年11月11日
Paul E. McKenney, paulmck@linux.vnet.ibm.com
Mark Batty, mjb220@cl.cam.ac.uk
Clark Nelson, clark.nelson@intel.com
Hans Boehm, hans.boehm@hp.com
Anthony Williams, anthony@justsoftwaresolutions.co.uk
Scott Owens, Scott.Owens@cl.cam.ac.uk
Susmit Sarkar, susmit.sarkar@cl.cam.ac.uk
Peter Sewell, Peter.Sewell@cl.cam.ac.uk
Tjark Weber, tw333@cam.ac.uk
Michael Wong, michaelw@ca.ibm.com
Lawrence Crowl, crowl@google.com
Benjamin Kosnik, bkoz@redhat.com
Mark Batty, Scott Owens, Susmit Sarkar, Peter Sewell, and Tjark Weber recently analyzed a formalized variant of the C++ memory model, which uncovered a number of potential issues discussed in an email thread entitled “Some more memory model issues from Mark Batty” initiated by Hans Boehm on June 13, 2010, in another email thread entitled “Further C++ concurrency discussion” initiated by Mark Batty on July 28, 2010, and in discussions in the Concurrency Working Group in Rapperswil. This paper summarizes the ensuing discussion, calling out changes that appear uncontroversial and summarizing positions on contended issues. Some of these issues have been captured as national-body comments, and the disposition of any remaining issues is to be determined.
Please note that only those issues related to the memory model and atomics are included in this paper.
More details on the work leading up to this paper may be found here and here.
This paper is based on N3125 and N3136, and on ensuing discussion in the Concurrency Working Group in Batavia.
Thread 0 Thread 1 r1 = x.load(memory_order_consume);r2 = y.load(memory_order_consume);y.store(1, memory_order_release);x.store(1, memory_order_release);
The standard permits the counter-intuitive outcome
x == 1 && y == 1, an outcome that cannot occur on any
hardware platform that we are aware of.
Batty et al. propose removing the word “subsequent” from 1.10p12 (presumably instead meaning 1.10p13), stating that this will clarify the definition.
This change has interesting consequences. The current wording is as follows, with the word being proposed for removal so marked:
The visible sequence of side effects on an atomic object
M, with respect to a value computationBofM, is a maximal contiguous sub-sequence of side effects in the modification order ofM, where the first side effect is visible with respect toB, and for every(削除) subsequent (削除ここまで)side effect, it is not the case that B happens before it. The value of an atomic objectM, as determined by evaluationB, shall be the value stored by some operation in the visible sequence ofMwith respect toB. Furthermore, if a value computationAof an atomic objectMhappens before a value computationBofM, and the value computed byAcorresponds to the value stored by side effectX, then the value computed byBshall either equal the value computed byA, or be the value stored by side effectY, whereYfollowsXin the modification order ofM. [ Note: This effectively disallows compiler reordering of atomic operations to a single object, even if both operations are “relaxed” loads. This effectively makes the “cache coherence” guarantee provided by most hardware available to C++ atomic operations. — end note ] [ Note: The visible sequence depends on the “happens before” relation, which depends on the values observed by loads of atomics, which we are restricting here. The intended reading is that there must exist an association of atomic loads with modifications they observe that, together with suitably chosen modification orders and the “happens before” relation derived as described above, satisfy the resulting constraints as imposed here. — end note ]
The effect of the current wording is as follows:
M
that happens before value computation B is the
visible side effect.
Call it V.
M
such that B happen before it will be called
I.
I and all subsequent side-effects are not
in the visible sequence of side effects.
M
that precedes V can be part of the visible
sequence of side effects.
Does some hardware actually operate in this fashion, so that a value
computation might return some value preceding the last side-effect in
the modification order of M that happens-before that value
computation?
Adopt the changes proposed for CA 8.
Batty et al. describe an interpretation of 1.10p6 that would only require that release sequences be extended back to the first release operation in a given thread out of a sequence of release operations on a given object.
This interpretation can be considered perverse in light of the wording of 1.10p7, however, the suggested modification is consistent with the intent.
Batty et al. suggest that the following wording from 1.10p13:
Furthermore, if a value computation
Aof an atomic objectMhappens before a value computationBofM, and the value computed byAcorresponds to the value stored by side effectX, then the value computed byBshall either equal the value computed byA, or be the value stored by side effectY, whereYfollowsXin the modification order ofM.
be changed to the following:
Furthermore, if a value computation
Aof an atomic objectMhappens before a value computationBofM, andAtakes its value from the side effectX, then the value computed byBshall either be the value stored byX, or the value stored by a side effectY, whereYfollowsXin the modification order ofM.
Batty et al. suggest adding the following non-normative note to 1.10p4:
[ Note: There may be non-atomic writes to atomic objects, for example on intialization and re-initialization. — end note ]
There was some dissatisfaction with this approach expressed in the June email thread. It is quite possible specifying this would be encroaching on the prerogatives of implementors, who are in any case free to perform operations non-atomically when permitted by the as-if rule. Implementors may also perform initializations atomically, again, when permitted by the as-if rule.
Adopt the update proposed by US 168.
Update 1.10p9 to make the inter-thread nature of the dependency-ordered before relation explicit.
Update 1.10p13 and add several subsequent paragraphs to explicitly define requirements for cache coherence.
At the time that the memory model was formulated, there was considerable uncertainty as to what architectures respect control dependencies, and to what extent. It appears that this uncertainty is being cleared up, and our hope is that it will be ripe for standardization in a later TR.
Not a Defect Future
The premise is incorrect;
atomic objects may not overlap.
The type argument to the atomic template
must be a trivially-copyable type (29.5.3p1)
and atomic objects are not trivially copyable.
The atomic types provide no means to obtain a reference to internal members;
all atomic operations are copy-in/copy-out.
In short, any attempt to generate a pair of atomic variables whose memory
overlaps results in undefined behavior.
Not a Defect
Adopt as recommended, but with more clarity.
After 29.6p4 [atomics.types.operations],
add a new function description for A::A().
Edit 29.6 [atomics.types.operations] paragraph 7 to call out initialization and then move it to just after the paragraph inserted above.
Move paragraph 6.5p5 to follow 1.10p16, but generalize it to
all code, not just for loops.
Change 1.10p4 as follows:
"The library defines a number of atomic operations (Clause 29) and operations on mutexes (Clause 30) that are specially identified as synchronization operations. These operations play a special role in making assignments in one thread visible to another. A synchronization operation on one or more memory locations is either a consume operation, an acquire operation, a release operation, or both an acquire and release operation. A synchronization operation without an associated memory location is a fence and can be either an acquire fence, a release fence, or both an acquire and release fence. In addition, there are relaxed atomic operations, which are not synchronization operations, and atomic read-modify-write operations, which have special characteristics. [ Note: For example, a call that acquires a lock on a mutex will perform an acquire operation on the locations comprising the mutex. Correspondingly, a call that releases the same lock will perform a release operation on those same locations. Informally, performing a release operation on A forces prior side effects on other memory locations to become visible to other threads that later perform a consume or an acquire operation on A. "Relaxed" atomic operations are not synchronization operations even though, like synchronization operations, they cannot contribute to data races. -- end note ]"
Change 1.10p7 as follows:
"Certain library calls synchronize with other library calls performed by another thread. In particular, an atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M and reads a value written by any side effect in the release sequence headed by A. [ Note: Except in the specified cases, reading a later value does not necessarily ensure visibility as described below. Such a requirement would sometimes interfere with efficient implementation. -- end note ] [ Note: The specifications of the synchronization operations define when one reads the value written by another. For atomic objects, the definition is clear. All operations on a given mutex occur in a single total order. Each lock acquisition "reads the value written" by the last lock release on the same mutex. -- end note ]"
Adopt the wording of GB 8, but with additional use of "mutex" for clarity.
Adopt the proposal
Normatively, the behavior is well-defined by 1.9p8. If the atomic object is volatile, then all operations on it are observable, otherwise not. Note that “observable” means “observable outside of the program.”
Not a Defect.
The last note of 1.10p12 refers to data races “as defined here”. Batty et al. recommend that this change to “as defined below”. Given that data races are defined in 1.10p14, it is easy to argue for “below”, however, it is equally easy to argue that the scope of “here” is the whole of 1.10.
National-body comment: GB 8, US 9, US 11
Changes:
The library defines a number of atomic operations (Clause 29) and operations on
(削除) locks (削除ここまで)(追記) mutexes (追記ここまで) (Clause 30) that are specially identified as synchronization operations. These operations play a special role in making assignments in one thread visible to another. A synchronization operation on one or more memory locations is either a consume operation, an acquire operation, a release operation, or both an acquire and release operation. A synchronization operation without an associated memory location is a fence and can be either an acquire fence, a release fence, or both an acquire and release fence. In addition, there are relaxed atomic operations, which are not synchronization operations, and atomic read-modify-write operations, which have special characteristics. [Note: For example, a call that acquires a(削除) lock (削除ここまで)(追記) mutex (追記ここまで) will perform an acquire operation on the locations comprising the(削除) lock (削除ここまで)(追記) mutex (追記ここまで). Correspondingly, a call that releases the same(削除) lock (削除ここまで)(追記) mutex (追記ここまで) will perform a release operation on those same locations. Informally, performing a release operation on A forces prior side effects on other memory locations to become visible to other threads that later perform a consume or an acquire operation on A. "Relaxed" atomic operations are not synchronization operations even though, like synchronization operations, they cannot contribute to data races. —end note]
National-body comment: CA 12
Changes:
A release sequence (追記) from a release operation
A(追記ここまで) on an atomic objectMis a maximal contiguous sub-sequence of side effects in the modification order ofM, where the first operation is(削除) a release (削除ここまで)(追記)A(追記ここまで), and every subsequent operation
- is performed by the same thread that performed
(削除) the release (削除ここまで)(追記)A(追記ここまで), or- is an atomic read-modify-write operation.
National-body comments: CA 9, GB 8, US 9, US 11
Changes:
Certain library calls synchronize with other library calls performed by another thread.
(削除) In particular, an atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M and reads a value written by any side effect in the release sequence headed by A. (削除ここまで)(追記) [ Example: An atomic store-release synchronizes with a load-acquire that takes its value from the store. (29.3 atomics.order) — end example ] (追記ここまで) [Note: Except in the specified cases, reading a later value does not necessarily ensure visibility as described below. Such a requirement would sometimes interfere with efficient implementation. —end note] [Note: The specifications of the synchronization operations define when one reads the value written by another. For atomic objects, the definition is clear. All operations on a given(削除) lock (削除ここまで)(追記) mutex (追記ここまで) occur in a single total order. Each (追記) mutex (追記ここまで)(削除) lock (削除ここまで)acquisition “reads the value written” by the last (追記) mutex (追記ここまで)(削除) lock (削除ここまで)release on the same mutex. —end note]
National-body comment: CA 15
Changes:
An evaluation
Ais dependency-ordered before an evaluationBif
Aperforms a release operation on an atomic objectM, and (追記) on another thread, (追記ここまで)Bperforms a consume operation onMand reads a value written by any side effect in the release sequence headed byA, or- for some evaluation
X,Ais dependency-ordered beforeXandXcarries a dependency toB.
National-body comments: CA 8, GB 10
Changes:
An evaluation A happens before an evaluation B if:
- A is sequenced before B, or
- A inter-thread happens before B.
(追記) The implementation shall ensure that no program execution demonstrates a cycle in the "happens before" relation. [ Note: This cycle would otherwise be possible only through the use of consume operations. — end note ] (追記ここまで)
National-body comments: CA 11, CA 13, CA 18, CA 19, CA 20, GB 11, GB 12
Changes:
The visible sequence of side effects on an atomic object M, with respect to a value computation B of M, is a maximal contiguous sub-sequence of side effects in the modification order of M, where the first side effect is visible with respect to B, and for every
(削除) subsequent (削除ここまで)side effect, it is not the case that B happens before it. The value of an atomic object M, as determined by evaluation B, shall be the value stored by some operation in the a visible sequence of M with respect to B. (追記) [Note: It can be shown that the visible sequence of side effects of a value computation is unique given the coherence requirements below. — end note] (追記ここまで)(削除) Furthermore, if a value computation A of an atomic object M happens before a value computation B of M, and the value computed by A corresponds to the value stored by side effect X, then the value computed by B shall either equal the value computed by A, or be the value stored by side effect Y, where Y follows X in the modification order of M. [ Note: This effectively disallows compiler reordering of atomic operations to a single object, even if both operations are “relaxed” loads. This effectively makes the “cache coherence” guarantee provided by most hardware available to C++ atomic operations. — end note] [ Note: The visible sequence depends on the “happens before” relation, which depends on the values observed by loads of atomics, which is restricted here. The intended reading is that there must exist an association of atomic loads with modifications they observe that, together with suitably chosen modification orders and the “happens before” relation derived as described above, satisfy the resulting constraints as imposed here. — end note] (削除ここまで)
National-body comments: CA 13, CA 18, CA 19, CA 20, GB 11, GB 12
Changes:
(追記) If an operation A that modifies an atomic object M happens before an operation B that modifies M, then A shall be earlier than B in the modification order of M. [ Note: This requirement is known as write-write coherence. — end note] (追記ここまで)
(追記) If a value computation A of an atomic object M happens before a value computation B of M, and A takes its value from a side effect X on M, then the value computed by B shall either be the value stored by X, or the value stored by a side effect Y on M, where Y follows X in the modification order of M. [ Note: This requirement is known as read-read coherence. — end note] (追記ここまで)
(追記) If a value computation A of an atomic object M happens before an operation B on M, then A shall take its value from a side effect X on M, where X precedes B in the modification order of M. [ Note: This requirement is known as read-write coherence. — end note] (追記ここまで)
(追記) If a side effect X on an atomic object M happens before a value computation B of M, then the evaluation B shall take its value from X or from a side effect Y that follows X in the modification order of M. [ Note: This requirement is known as write-read coherence. — end note] (追記ここまで)
(追記) [ Note: These four coherence requirements effectively disallow compiler reordering of atomic operations to a single object, even if both operations are relaxed loads. This effectively makes the “cache coherence” guarantee provided by most hardware available to C++ atomic operations. — end note] (追記ここまで)
(追記) [ Note: The visible sequence of side effects depends on the “happens before” relation, which depends on the values observed by loads of atomics, which we are restricting here. The intended reading is that there must exist an association of atomic loads with modifications they observe that, together with suitably chosen modification orders and the “happens before” relation derived as described above, satisfy the resulting constraints as imposed here. — end note] (追記ここまで)
National-body comment: US 12
Changes:
The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other. Any such data race results in undefined behavior. [ Note: It can be shown that programs that correctly use
(削除) simple locks (削除ここまで)(追記) mutexes andmemory_order_seq_cstoperations (追記ここまで) to prevent all data races and (追記) that (追記ここまで) use no other synchronization operations behave as(削除) though the executions of (削除ここまで)(追記) if the operations executed by (追記ここまで) their constituent threads were simply interleaved, with each(削除) observed value (削除ここまで)(追記) value computation (追記ここまで) of an object being (追記) taken from (追記ここまで) the(削除) last value assigned (削除ここまで)(追記) last side effect on that object (追記ここまで) in that interleaving. This is normally referred to as “sequential consistency”. However, this applies only to (追記) data– (追記ここまで)race–free programs, and (追記) data– (追記ここまで)race–free programs cannot observe most program transformations that do not change single–threaded program semantics. In fact, most single–threaded program transformations continue to be allowed, since any program that behaves differently as a result must perform an undefined operation. — end note ]
National-body comment: US 38
Changes:
(追記) The implementation is allowed to assume that any thread will eventually do one of the following: (追記ここまで)
- (追記) terminate, (追記ここまで)
- (追記) make a call to a library I/O function, (追記ここまで)
- (追記) access or modify a volatile object, or (追記ここまで)
- (追記) perform a synchronization operation or an atomic operation. (追記ここまで)
(追記) [ Note: This is intended to allow compiler transformations, such as removal of empty loops, even when termination cannot be proven. — end note ] (追記ここまで)
National-body comment: US 38
Deletion:
(削除) A loop that, outside of the for-init-statement in the case of aforstatement, (削除ここまで)
(削除) makes no calls to library I/O functions, and (削除ここまで)(削除) does not access or modify volatile objects, and (削除ここまで)(削除) performs no synchronization operations (1.10) or atomic operations (Clause 29) (削除ここまで)
(削除) may be assumed by the implementation to terminate. [ Note: This is intended to allow compiler transformations, such as removal of empty loops, even when termination cannot be proven. — end note ] (削除ここまで)
National-body comment: CA 9
Changes:
If one thread makes a library call a that writes a value to a stream and, as a result, another thread reads this value from the stream through a library call b such that this does not result in a data race, then a(追記) 's write (追記ここまで)
(削除) happens before (削除ここまで)(追記) synchronizes with (追記ここまで) b(追記) 's read (追記ここまで).
National-body comment: CA 9
Changes:
(追記) An atomic operation A that performs a release operation on an atomic object M synchronizes with an atomic operation B that performs an acquire operation on M and takes its value from any side effect in the release sequence headed by A. (追記ここまで)
National-body comment: US 168, US 171
Changes:
- (追記)
A::A() = default;(追記ここまで)- (追記) Effects: Leaves the atomic object in an uninitialized state. [Note: These semantics ensure compatiblity with C. —end note] (追記ここまで)
National-body comment: US 168, US 171
Change as follow, then move atomic_init() to follow
the new paragraph added after 29.6p4:
Effects: Non-atomically
(削除) assigns the value desired to(追記) initializes *object with value*object. (削除ここまで)desired. This function shall only be applied to objects that have been default constructed, and then only once. [Note: These semantics ensure compatibility with C. —end note] [Note: (追記ここまで) Concurrent access from another thread, even via an atomic operation, constitutes a data race. (追記) —end note] (追記ここまで)
National-body comment: CA 9
Changes:
Synchronization: The (追記) completion of the (追記ここまで) invocation of the constructor
(削除) happens before (削除ここまで)(追記) synchronizes with the beginning of (追記ここまで) the invocation of the copy of f.
National-body comment: CA 9
Changes:
Synchronization: The completion of the thread represented by *this
(削除) happens before (削除ここまで)(追記) synchronizes with (追記ここまで) (1.10) (追記) the corresponding successful (追記ここまで) join() return(削除) s (削除ここまで). [ Note: Operations on *this are not synchronized. — end note ]
National-body comment: CA 9
Changes:
Calls to functions that successfully set the stored result of an associated asynchronous state synchronize with (1.10) calls to functions successfully detecting the ready state resulting from that setting. The storage of the result (whether normal or exceptional) into the associated asynchronous state
(削除) happens before (削除ここまで)(追記) synchronizes with (追記ここまで) (1.10)(削除) that state is set to ready (削除ここまで)(追記) the successful return from a call to a waiting function on the associated asynchronous state (追記ここまで).
National-body comment: CA 9
Changes:
Synchronization: the invocation of async
(削除) happens before (削除ここまで)(追記) synchronizes with (追記ここまで) (1.10) the invocation of f. [ Note: this statement applies even when the corresponding future object is moved to another thread. — end note ] If the invocation is not deferred, a call to a waiting function on an asynchronous return object that shares the associated asynchronous state created by this async call shall block until the associated thread has completed. If the invocation is not deferred, the join() on the created thread(削除) happens-before (削除ここまで)(追記) synchronizes with (追記ここまで) (1.10) the first function that successfully detects the ready status of the associated asynchronous state returns or before the function that gives up the last reference to the associated asynchronous state returns, whichever happens first. If the invocation is deferred, the completion of the invocation of the deferred function(削除) happens-before (削除ここまで)(追記) synchronizes with (追記ここまで) the (追記) the successful return from a call to a waiting function on the associated asynchronous state. (追記ここまで)(削除) calls to the waiting functions return. (削除ここまで)
National-body comment: CA 9
Changes:
Synchronization: a successful call to operator() synchronizes with (1.10) a call to any member function of a future, shared_future, or atomic_future object that shares the associated asynchronous state of *this. The completion of the invocation of the stored task and the storage of the result (whether normal or exceptional) into the associated asynchronous state
(削除) happens before (削除ここまで)(追記) synchronizes with (追記ここまで) (1.10) (追記) the successful return from any member function that detects that (追記ここまで) the state is set to ready. [ Note: operator() synchronizes and serializes with other functions through the associated asynchronous state. — end note ]