Control dependency between prior load in while condition and later store?

Control dependency between prior load in while condition and later store?

[Daniel Jordan]

A question for memory-barriers.txt aficionados.

Is there a control dependency between the prior load of 'a' and the 
later store of 'c'?:

   while (READ_ONCE(a));
   WRITE_ONCE(c, 1);

I have my doubts because memory-barriers.txt doesn't talk much about 
loops and because of what that document says here:

   In addition, control dependencies apply only to the then-clause and
   else-clause of the if-statement in question.  In particular, it does
   not necessarily apply to code following the if-statement:

   	q = READ_ONCE(a);
   	if (q) {
   		WRITE_ONCE(b, 1);
   	} else {
   		WRITE_ONCE(b, 2);
   	}
   	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from 'a'. */

It's not obvious to me how the then-clause/else-clause idea maps onto 
loops, but if we think of the example at the top like this...

   while (1) {
       if (!READ_ONCE(a)) {
           WRITE_ONCE(c, 1);
           break;
       }
   }

...then the dependent store is within the then-clause.  Viewed this way, 
it seems there would be a control dependency between a and c.

Is that right?

Thanks,
Daniel

Re: Control dependency between prior load in while condition and later store?

[Alan Stern]

On Wed, 4 Apr 2018, Daniel Jordan wrote:

> A question for memory-barriers.txt aficionados.
> 
> Is there a control dependency between the prior load of 'a' and the 
> later store of 'c'?:
> 
>    while (READ_ONCE(a));
>    WRITE_ONCE(c, 1);

I would say that yes, there is.

> I have my doubts because memory-barriers.txt doesn't talk much about 
> loops and because of what that document says here:
> 
>    In addition, control dependencies apply only to the then-clause and
>    else-clause of the if-statement in question.  In particular, it does
>    not necessarily apply to code following the if-statement:
> 
>    	q = READ_ONCE(a);
>    	if (q) {
>    		WRITE_ONCE(b, 1);
>    	} else {
>    		WRITE_ONCE(b, 2);
>    	}
>    	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from 'a'. */

This refers to situations where the two code paths meet up at the end
of the "if" statement.  If they don't meet up (because one of the paths
branches away -- especially if it branches backward) then the 
disclaimer doesn't apply, and everything following the "if" is 
dependent.

The reason is because the compiler knows that code following the "if" 
statement will be executed unconditionally if the paths meet up, so it 
can move that code back before the "if" (provided nothing else prevents 
such motion).  But if the paths don't meet up, the compiler can't 
perform the code motion -- if it did then the program might end up 
executing something that should not have been executed!

> It's not obvious to me how the then-clause/else-clause idea maps onto 
> loops, but if we think of the example at the top like this...
> 
>    while (1) {
>        if (!READ_ONCE(a)) {
>            WRITE_ONCE(c, 1);
>            break;
>        }
>    }
> 
> ...then the dependent store is within the then-clause.  Viewed this way, 
> it seems there would be a control dependency between a and c.
> 
> Is that right?

Yes, except that a more accurate view of the object code would be
something like this:

Loop:	r1 = READ_ONCE(a);
	if (r1)
		goto Loop;
	else
		;	// Do nothing
	WRITE_ONCE(c, 1);

Here you can see that one path branches backward, so everything 
following the "if" is dependent on the READ_ONCE.

Alan

Re: Control dependency between prior load in while condition and later store?

[Daniel Jordan]

On 04/04/2018 04:35 PM, Alan Stern wrote:
> On Wed, 4 Apr 2018, Daniel Jordan wrote:
> 
>> A question for memory-barriers.txt aficionados.
>>
>> Is there a control dependency between the prior load of 'a' and the
>> later store of 'c'?:
>>
>>     while (READ_ONCE(a));
>>     WRITE_ONCE(c, 1);
> 
> I would say that yes, there is.
> 
>> I have my doubts because memory-barriers.txt doesn't talk much about
>> loops and because of what that document says here:
>>
>>     In addition, control dependencies apply only to the then-clause and
>>     else-clause of the if-statement in question.  In particular, it does
>>     not necessarily apply to code following the if-statement:
>>
>>     	q = READ_ONCE(a);
>>     	if (q) {
>>     		WRITE_ONCE(b, 1);
>>     	} else {
>>     		WRITE_ONCE(b, 2);
>>     	}
>>     	WRITE_ONCE(c, 1);  /* BUG: No ordering against the read from 'a'. */
> 
> This refers to situations where the two code paths meet up at the end
> of the "if" statement.  If they don't meet up (because one of the paths
> branches away -- especially if it branches backward) then the
> disclaimer doesn't apply, and everything following the "if" is
> dependent.

Ok, that's the part I wasn't getting: this is how the while loop changes 
the situation.

> The reason is because the compiler knows that code following the "if"
> statement will be executed unconditionally if the paths meet up, so it
> can move that code back before the "if" (provided nothing else prevents
> such motion).  But if the paths don't meet up, the compiler can't
> perform the code motion -- if it did then the program might end up
> executing something that should not have been executed!
> 
>> It's not obvious to me how the then-clause/else-clause idea maps onto
>> loops, but if we think of the example at the top like this...
>>
>>     while (1) {
>>         if (!READ_ONCE(a)) {
>>             WRITE_ONCE(c, 1);
>>             break;
>>         }
>>     }
>>
>> ...then the dependent store is within the then-clause.  Viewed this way,
>> it seems there would be a control dependency between a and c.
>>
>> Is that right?
> 
> Yes, except that a more accurate view of the object code would be
> something like this:
> 
> Loop:	r1 = READ_ONCE(a);
> 	if (r1)
> 		goto Loop;
> 	else
> 		;	// Do nothing
> 	WRITE_ONCE(c, 1);
> 
> Here you can see that one path branches backward, so everything
> following the "if" is dependent on the READ_ONCE.

That clears it up, thanks very much!

Re: Control dependency between prior load in while condition and later store?

[Peter Zijlstra]

On Wed, Apr 04, 2018 at 04:35:32PM -0400, Alan Stern wrote:
> On Wed, 4 Apr 2018, Daniel Jordan wrote:
> 
> > A question for memory-barriers.txt aficionados.
> > 
> > Is there a control dependency between the prior load of 'a' and the 
> > later store of 'c'?:
> > 
> >    while (READ_ONCE(a));
> >    WRITE_ONCE(c, 1);
> 
> I would say that yes, there is.

Indeed.

> Yes, except that a more accurate view of the object code would be
> something like this:
> 
> Loop:	r1 = READ_ONCE(a);
> 	if (r1)
> 		goto Loop;
> 	else
> 		;	// Do nothing
> 	WRITE_ONCE(c, 1);
> 
> Here you can see that one path branches backward, so everything 
> following the "if" is dependent on the READ_ONCE.

Agreed, and I think I even have code that relies on such a pattern
somewhere.. Ah.. yes, see smp_cond_load_acquire().

Re: Control dependency between prior load in while condition and later store?

[Alan Stern]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=UTF-8, Size: 1920 bytes --]

On Thu, 5 Apr 2018, Peter Zijlstra wrote:

> On Wed, Apr 04, 2018 at 04:35:32PM -0400, Alan Stern wrote:
> > On Wed, 4 Apr 2018, Daniel Jordan wrote:
> > 
> > > A question for memory-barriers.txt aficionados.
> > > 
> > > Is there a control dependency between the prior load of 'a' and the 
> > > later store of 'c'?:
> > > 
> > >    while (READ_ONCE(a));
> > >    WRITE_ONCE(c, 1);
> > 
> > I would say that yes, there is.
> 
> Indeed.
> 
> > Yes, except that a more accurate view of the object code would be
> > something like this:
> > 
> > Loop:	r1 = READ_ONCE(a);
> > 	if (r1)
> > 		goto Loop;
> > 	else
> > 		;	// Do nothing
> > 	WRITE_ONCE(c, 1);
> > 
> > Here you can see that one path branches backward, so everything 
> > following the "if" is dependent on the READ_ONCE.
> 
> Agreed, and I think I even have code that relies on such a pattern
> somewhere.. Ah.. yes, see smp_cond_load_acquire().

One does have to be very careful when talking about compiler behavior.  
This happens to be a particularly delicate point.  My old copy of the
C++11 draft standard says (section 1.10 paragraph 24):


The implementation may 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 ]


In this example, READ_ONCE() is in fact a volatile access, so we're 
okay.  But if it weren't, the compiler might decide to assume the loop 
will eventually terminate, meaning that the WRITE_ONCE() would always 
be executed eventually.  Then there would be nothing to prevent the 
compiler from moving the WRITE_ONCE() up before the start of the loop, 
which would of course destroy the control dependency.

Alan

Re: Control dependency between prior load in while condition and later store?

[Peter Zijlstra]

On Thu, Apr 05, 2018 at 10:35:22AM -0400, Alan Stern wrote:
> In this example, READ_ONCE() is in fact a volatile access, so we're 
> okay.

But our documentation clearly states a control-dep can only be from a
READ_ONCE() (or something stronger), right? So we should be good
irrespectively.

Re: Control dependency between prior load in while condition and later store?

[Alan Stern]

On Thu, 5 Apr 2018, Peter Zijlstra wrote:

> On Thu, Apr 05, 2018 at 10:35:22AM -0400, Alan Stern wrote:
> > In this example, READ_ONCE() is in fact a volatile access, so we're 
> > okay.
> 
> But our documentation clearly states a control-dep can only be from a
> READ_ONCE() (or something stronger), right? So we should be good
> irrespectively.

Agreed.  My point was that these are delicate issues.  (And they will 
become more relevant when we want to expand the Linux Kernel Memory 
Consistency Model to cover ordinary accesses and data races.)

Alan