Section: 32.5.4 [atomics.order] Status: LEWG Submitter: Canada Opened: 2010-08-25 Last modified: 2016-01-28
Priority: Not Prioritized
View other active issues in [atomics.order].
View all other issues in [atomics.order].
View all issues with LEWG status.
Duplicate of: 1458
Discussion:
Addresses CA-21, GB-131
32.5.5 [atomics.lockfree] p.8 states:
An atomic store shall only store a value that has been computed from constants and program input values by a finite sequence of program evaluations, such that each evaluation observes the values of variables as computed by the last prior assignment in the sequence.
... but 6.9.1 [intro.execution] p.13 states:
If A is not sequenced before B and B is not sequenced before A, then A and B are unsequenced. [ Note: The execution of unsequenced evaluations can overlap. — end note ]
Overlapping executions can make it impossible to construct the sequence described in 32.5.5 [atomics.lockfree] p.8. We are not sure of the intention here and do not offer a suggestion for change, but note that 32.5.5 [atomics.lockfree] p.8 is the condition that prevents out-of-thin-air reads.
For an example, suppose we have a function invocation f(e1,e2). The evaluations of e1 and e2 can overlap. Suppose that the evaluation of e1 writes y and reads x whereas the evaluation of e2 reads y and writes x, with reads-from edges as below (all this is within a single thread).
e1 e2
Wrlx y-- --Wrlx x
rf\ /rf
X
/ \
Rrlx x<- ->Rrlx y
This seems like it should be allowed, but there seems to be no way to produce a sequence of evaluations with the property above.
In more detail, here the two evaluations, e1 and e2, are being executed as the arguments of a function and are consequently not sequenced-before each other. In practice we'd expect that they could overlap (as allowed by 6.9.1 [intro.execution] p.13), with the two writes taking effect before the two reads. However, if we have to construct a linear order of evaluations, as in 32.5.5 [atomics.lockfree] p.8, then the execution above is not permited. Is that really intended?
[ Resolution proposed by ballot comment ]
Please clarify.
[2011-03-09 Hans comments:]
I'm not proud of 32.5.4 [atomics.order] p9 (formerly p8), and I agree with the comments that this
isn't entirely satisfactory. 32.5.4 [atomics.order] p9 was designed to preclude
out-of-thin-air results for races among memory_order_relaxed atomics, in spite of
the fact that Java experience has shown we don't really know how to do that adequately. In
the long run, we probably want to revisit this.
6.9.1 [intro.execution] p15 states: "If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined." I think the examples presented here have undefined behavior as a result. It's not completely clear to me whether examples can be constructed that exhibit this problem, and don't have undefined behavior.
This comment seems to be using a different meaning of "evaluation"
from what is used elsewhere in the standard. The sequence of evaluations
here doesn't have to consist of full expression evaluations. They
can be evaluations of operations like lvalue to rvalue conversion,
or individual assignments. In particular, the reads and writes
executed by e1 and e2 in the example could be treated as separate
evaluations for purposes of producing the sequence.
The definition of "sequenced before" in 6.9.1 [intro.execution] makes
little sense if the term "evaluation" is restricted to any notion
of complete expression. Perhaps we should add yet another note
to clarify this? 32.5.4 [atomics.order] p10 probably leads to
the wrong impression here.
[2011-03-24 Madrid]
Moved to NAD Future
Proposed resolution: