linux-kernel - Re: Compilers and RCU readers: Once more unto the breach!

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: <20150522173029.GD3072@arm.com>
Date:	Fri, 22 May 2015 18:30:29 +0100
From:	Will Deacon <will.deacon@....com>
To:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:	Linus Torvalds <torvalds@...ux-foundation.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	"c++std-parallel@...u.org" <c++std-parallel@...u.org>,
	"linux-arch@...r.kernel.org" <linux-arch@...r.kernel.org>,
	"gcc@....gnu.org" <gcc@....gnu.org>,
	p796231 <Peter.Sewell@...cam.ac.uk>,
	"mark.batty@...cam.ac.uk" <Mark.Batty@...cam.ac.uk>,
	Peter Zijlstra <peterz@...radead.org>,
	Ramana Radhakrishnan <Ramana.Radhakrishnan@....com>,
	David Howells <dhowells@...hat.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Ingo Molnar <mingo@...nel.org>,
	"michaelw@...ibm.com" <michaelw@...ibm.com>
Subject: Re: Compilers and RCU readers: Once more unto the breach!

Hi Paul,

On Thu, May 21, 2015 at 09:02:12PM +0100, Paul E. McKenney wrote:
> On Thu, May 21, 2015 at 08:24:22PM +0100, Will Deacon wrote:
> > On Wed, May 20, 2015 at 07:16:06PM +0100, Paul E. McKenney wrote:
> > > On to #5:
> > > 
> > > 	r1 = atomic_load_explicit(&x, memory_order_consume);
> > > 	if (r1 == 42)
> > > 	  atomic_store_explicit(&y, r1, memory_order_relaxed);
> > > 	----------------------------------------------------
> > > 	r2 = atomic_load_explicit(&y, memory_order_consume);
> > > 	if (r2 == 42)
> > > 	  atomic_store_explicit(&x, 42, memory_order_relaxed);
> > > 
> > > The first thread's accesses are dependency ordered.  The second thread's
> > > ordering is in a corner case that memory-barriers.txt does not cover.
> > > You are supposed to start control dependencies with READ_ONCE_CTRL(), not
> > > a memory_order_consume load (AKA rcu_dereference and friends).  However,
> > > Alpha would have a full barrier as part of the memory_order_consume load,
> > > and the rest of the processors would (one way or another) respect the
> > > control dependency.  And the compiler would have some fun trying to
> > > break it.
> > 
> > But this is interesting because the first thread is ordered whilst the
> > second is not, so doesn't that effectively forbid the compiler from
> > constant-folding values if it can't prove that there is no dependency
> > chain?
> 
> You lost me on this one.  Are you suggesting that the compiler
> speculate the second thread's atomic store?  That would be very
> bad regardless of dependency chains.
> 
> So what constant-folding optimization are you thinking of here?
> If the above example is not amenable to such an optimization, could
> you please give me an example where constant folding would apply
> in a way that is sensitive to dependency chains?

Unless I'm missing something, I can't see what would prevent a compiler
from looking at the code in thread1 and transforming it into the code in
thread2 (i.e. constant folding r1 with 42 given that the taken branch
must mean that r1 == 42). However, such an optimisation breaks the
dependency chain, which means that a compiler needs to walk backwards
to see if there is a dependency chain extending to r1.

> > > So the current Linux memory model would allow (r1 == 42 && r2 == 42),
> > > but I don't know of any hardware/compiler combination that would
> > > allow it.  And no, I am -not- going to update memory-barriers.txt for
> > > this litmus test, its theoretical interest notwithstanding!  ;-)

Of course, I'm not asking for that at all! I'm just trying to see how
your proposal holds up with the example.

Will
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/