[cpp-threads] Visible sequence of side effects and coherence requirements

[Paul E. McKenney]

On Tue, Nov 23, 2010 at 11:29:45AM -0500, Alan Stern wrote:
> Given the coherence requirements expressed in D3196 ("New Paragraphs
> Following 1.10.p13"), the definition of "visible sequence of side
> effects" (VSSE) in 1.10.p13 is too broad.  That is, the VSSE on an
> atomic object M with respect to a value computation B of M may include
> side effects which could not possibly be the value determined by B.
> 
> For example, suppose that side effects A1 and A2 both modify M, where
> A1 occurs before A2 in the modification order of M.  Further suppose
> that A1 and A2 both happen before B, but neither happens before the
> other.
> 
> Then the VSSE on M with respect to B includes both A1 and A2, because
> A1 is visible with respect to B and B does not happen before either A1
> or A2.  But the write-read coherence requirement for A2 and B does not
> allow B to take its value from A1.  Hence A1 shouldn't be in the VSSE,
> even though the current definition puts it there.
> 
> In short, although the current definition of VSSE is not incorrect, it
> could be improved.  For instance, it might be stated as:
> 
> 	The visible sequence of side effects on an atomic object M,
> 	with respect to a value computation B of M, is the contiguous
> 	sub-sequence of side effects in the modification order of M
> 	beginning with the last side effect that happens before B and
> 	continuing up to, but not including, the first side effect
> 	that B happens before, if any.
> 
> However I'm not going to advocate changing the definition of VSSE.  
> Instead, I suggest removing the whole concept from the formal part of
> the standard entirely!
> 
> The VSSE is defined solely for the purpose of this specification:
> 
> 	The value of an atomic object M, as determined by evaluation
> 	B, shall be the value stored by some operation in the visible
> 	sequence of M with respect to B.
> 
> This does not need to be stated expicitly, because it follows directly
> from the new coherence requirements.  Here's how:
> 
> Let X be the last side effect in the modification order of M that 
> happens before B, let Y be the side effect from which B determines the 
> value of M, and let Z the first side effect in the modification order 
> of M that B happens before (if any).
> 
> The write-read coherence requirement, applied to X and B, states that Y
> either is X or follows X in the modification order.  The read-write
> coherence requirement, applied to B and Z, states that Y precedes Z in
> the modification order.  Together these facts imply that Y belongs to
> the maximal contiguous sub-sequence defined above (or the sub-sequence
> defined as in 1.10.p13).
> 
> (As a special case, if Z doesn't exist then the only requirement is
> that Y is X or follows X, again agreeing with the definition of the
> VSSE.  If X doesn't exist then the behavior is undefined or
> unspecified, because B could read an uninitialized value.)
> 
> This argument shows that the only reason for introducing the VSSE into
> the standard has now been superseded.  Therefore I suggest that the
> existing text of 1.10.p13 be removed completely, leaving only the new
> coherence requirements.

I of course like the thought of removing unnecessary words from the
standard.

Mark, Hans, Clark, any thoughts?

							Thanx, Paul