linux-kernel - (Non-) Ctrl Dependency in litmus-tests.txt?

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-next>] [day] [month] [year] [list]

Date:   Fri, 3 Jun 2022 16:12:37 +0200
From:   Paul Heidekrüger <paul.heidekrueger@...tum.de>
To:     Alan Stern <stern@...land.harvard.edu>,
        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>,
        linux-kernel@...r.kernel.org, linux-arch@...r.kernel.org
Cc:     Marco Elver <elver@...gle.com>
Subject: (Non-) Ctrl Dependency in litmus-tests.txt?

Hi all,

I was going through litmus-tests.txt and came across the following:

> LIMITATIONS
> ===========
> 
> Limitations of the Linux-kernel memory model (LKMM) include:
> 
> 1.Compiler optimizations are not accurately modeled.  Of course,
> 	the use of READ_ONCE() and WRITE_ONCE() limits the compiler's
> 	ability to optimize, but under some circumstances it is possible
> 	for the compiler to undermine the memory model.  For more
> 	information, see Documentation/explanation.txt (in particular,
> 	the "THE PROGRAM ORDER RELATION: po AND po-loc" and "A WARNING"
> 	sections).
> 
> 	Note that this limitation in turn limits LKMM's ability to
> 	accurately model address, control, and data dependencies.
> 	For example, if the compiler can deduce the value of some variable
> 	carrying a dependency, then the compiler can break that dependency
> 	by substituting a constant of that value.
> 
> 	Conversely, LKMM sometimes doesn't recognize that a particular
> 	optimization is not allowed, and as a result, thinks that a
> 	dependency is not present (because the optimization would break it).
> 	The memory model misses some pretty obvious control dependencies
> 	because of this limitation.  A simple example is:
> 
> 		r1 = READ_ONCE(x);
> 		if (r1 == 0)
> 			smp_mb();
> 		WRITE_ONCE(y, 1);
> 
> 	There is a control dependency from the READ_ONCE to the WRITE_ONCE,
> 	even when r1 is nonzero, but LKMM doesn't realize this and thinks
> 	that the write may execute before the read if r1 != 0.  (Yes, that
> 	doesn't make sense if you think about it, but the memory model's
> 	intelligence is limited.)

I'm unclear as to why the documentation sees a control dependency from
the READ_ONCE() to the WRITE_ONCE() here.

Quoting from explanation.txt:
> Finally, a read event and another memory access event are linked by a
> control dependency if the value obtained by the read affects whether
> the second event is executed at all.

Architectures might consider this control-dependent, yes, but since the
value of the if condition does not affect whether the WRITE_ONCE() is
executed at all, I'm not sure why this should be considered
control-dependent in LKMM? 

I might have another question about explanation.txt's definition of
control dependencies as per above, but will address it more thoroughly
in another email :-)

Many thanks,
Paul