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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Wed, 4 Apr 2018 16:35:32 -0400 (EDT)
From:   Alan Stern <stern@...land.harvard.edu>
To:     Daniel Jordan <daniel.m.jordan@...cle.com>
cc:     parri.andrea@...il.com, <will.deacon@....com>,
        <peterz@...radead.org>, <boqun.feng@...il.com>,
        <npiggin@...il.com>, <dhowells@...hat.com>, <j.alglave@....ac.uk>,
        <luc.maranget@...ia.fr>, <paulmck@...ux.vnet.ibm.com>,
        <akiyks@...il.com>, <linux-kernel@...r.kernel.org>,
        Steven Sistare <steven.sistare@...cle.com>,
        Pasha Tatashin <pasha.tatashin@...cle.com>
Subject: Re: Control dependency between prior load in while condition and
 later store?

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