linux-kernel - Re: [PATCH RFC] tools/memory-model: Adjust ctrl dependency definition

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]

Message-Id: <04B4DBD6-1262-4905-9E85-9466FC104895@in.tum.de>
Date:   Mon, 27 Jun 2022 11:47:43 +0200
From:   Paul Heidekrüger <Paul.Heidekrueger@...tum.de>
To:     Alan Stern <stern@...land.harvard.edu>
Cc:     clang-built-linux <llvm@...ts.linux.dev>,
        linux-toolchains@...r.kernel.org,
        Andrea Parri <parri.andrea@...il.com>,
        Will Deacon <will@...nel.org>,
        Peter Zijlstra <peterz@...radead.org>,
        Boqun Feng <boqun.feng@...il.com>,
        Nicholas Piggin <npiggin@...il.com>,
        David Howells <dhowells@...hat.com>,
        Jade Alglave <j.alglave@....ac.uk>,
        Luc Maranget <luc.maranget@...ia.fr>,
        "Paul E. McKenney" <paulmck@...nel.org>,
        Akira Yokosawa <akiyks@...il.com>,
        Daniel Lustig <dlustig@...dia.com>,
        Joel Fernandes <joel@...lfernandes.org>,
        Nathan Chancellor <nathan@...nel.org>,
        Nick Desaulniers <ndesaulniers@...gle.com>,
        Tom Rix <trix@...hat.com>, Palmer Dabbelt <palmer@...belt.com>,
        LKML <linux-kernel@...r.kernel.org>,
        linux-arch <linux-arch@...r.kernel.org>,
        Marco Elver <elver@...gle.com>,
        Charalampos Mainas <charalampos.mainas@...il.com>,
        Pramod Bhatotia <pramod.bhatotia@...tum.de>,
        Soham Chakraborty <s.s.chakraborty@...elft.nl>,
        Martin Fink <martin.fink@...tum.de>
Subject: Re: [PATCH RFC] tools/memory-model: Adjust ctrl dependency definition


> On 21. Jun 2022, at 16:24, Alan Stern <stern@...land.harvard.edu> wrote:
> 
> On Tue, Jun 21, 2022 at 01:59:27PM +0200, Paul Heidekrüger wrote:
>> OK. So, LKMM limits the scope of control dependencies to its arm(s), hence
>> there is a control dependency from the last READ_ONCE() before the loop
>> exists to the WRITE_ONCE().
>> 
>> But then what about the following:
>> 
>>> int *x, *y;
>>> 
>>> int foo()
>>> {
>>> 	/* More code */
>>> 
>>> 	if(READ_ONCE(x))
>>> 		return 42;
>>> 
>>> 	/* More code */
>>> 
>>> 	WRITE_ONCE(y, 42);
>>> 
>>> 	/* More code */
>>> 
>>> 	return 0;
>>> }
>> 
>> The READ_ONCE() determines whether the WRITE_ONCE() will be executed at all,
>> but the WRITE_ONCE() doesn't lie in the if condition's arm.
> 
> So in this case the LKMM would not recognize that there's a control 
> dependency, even though it clearly exists.

Oh, that's unfortunate.

Then I would still argue that the "at all" definition is misleading. This
time in the other direction as I had initially proposed though, as the above
example is a case where "at all" holds true, but LKMM doesn't cover it. Or
do you think that caveating this in litmus-tests.txt, e.g. via the patch we
had recently worked out [1], is enough?

>>  However, by
>> "inverting" the if, we get the following equivalent code:
>> 
>>> if(!READ_ONCE(x)) {
>>> 	/* More code */
>>> 
>>> 	WRITE_ONCE(y, 42);
>>> 
>>> 	/* More code */
>>> 
>>> 	return 0;
>>> }
>>> 
>>> return 42;
>> 
>> Now, the WRITE_ONCE() is in the if's arm, and there is clearly a control
>> dependency.
> 
> Correct.
> 
>> Similar cases:
>> 
>>> if(READ_ONCE())
>>> 	foo(); /* WRITE_ONCE() in foo() */
>>> return 42;
>> 
>> or
>> 
>>> if(READ_ONCE())
>>>    goto foo; /* WRITE_ONCE() after foo */
>>> return 42;
>> 
>> In both cases, the WRITE_ONCE() again isn't in the if's arm syntactically
>> speaking, but again, with rewriting, you can end up with a control
>> dependency; in the first case via inlining, in the second case by simply
>> copying the code after the "foo" marker.
> 
> Again, correct.  The LKMM isn't always consistent, and it behaves this 
> way to try to avoid presuming too much about the optimizations that 
> compilers may apply.

Many thanks,
Paul

--
[1]: https://lore.kernel.org/all/20220614154812.1870099-1-paul.heidekrueger@in.tum.de/
Download attachment "smime.p7s" of type "application/pkcs7-signature" (5449 bytes)