1459. Overlapping evaluations are allowed

Section: 32.4 [atomics.order] Status: LEWG Submitter: Canada Opened: 2010-08-25 Last modified: 2016-02-10

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 [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.8.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 [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 [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.8.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 [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.4 [atomics.order] p9 (formerly p8), and I agree with the comments that this isn't entirely satisfactory. 32.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.

However, in the short term, I'm still inclined to declare this NAD, for two separate reasons:

  1. 6.8.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.

  2. 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.8.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.4 [atomics.order] p10 probably leads to the wrong impression here.

    An alternative resolution would be to simply delete our flakey attempt at preventing out-of-thin-air reads, by removing 32.4 [atomics.order] p9-11, possibly adding a note that explains that we technically allow, but strongly discourage them. If we were starting this from scratch now, that would probably be my preference. But it seems like too drastic a resolution at this stage.

[2011-03-24 Madrid]

Moved to NAD Future

Proposed resolution: