linux-kernel - Re: XDP socket rings, and LKMM litmus tests

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: <YEB/PGHs94W2l6hA@boqun-archlinux>
Date:   Thu, 4 Mar 2021 14:33:32 +0800
From:   Boqun Feng <boqun.feng@...il.com>
To:     Alan Stern <stern@...land.harvard.edu>
Cc:     "Paul E. McKenney" <paulmck@...nel.org>,
        Björn Töpel <bjorn.topel@...il.com>,
        bpf <bpf@...r.kernel.org>, LKML <linux-kernel@...r.kernel.org>,
        parri.andrea@...il.com, Will Deacon <will@...nel.org>,
        Peter Zijlstra <peterz@...radead.org>, npiggin@...il.com,
        dhowells@...hat.com, j.alglave@....ac.uk, luc.maranget@...ia.fr,
        akiyks@...il.com, dlustig@...dia.com, joel@...lfernandes.org,
        Toke Høiland-Jørgensen <toke@...hat.com>,
        "Karlsson, Magnus" <magnus.karlsson@...el.com>
Subject: Re: XDP socket rings, and LKMM litmus tests

On Wed, Mar 03, 2021 at 10:13:22PM -0500, Alan Stern wrote:
> On Thu, Mar 04, 2021 at 09:26:31AM +0800, Boqun Feng wrote:
> > On Wed, Mar 03, 2021 at 03:22:46PM -0500, Alan Stern wrote:
> 
> > > Which brings us back to the case of the
> > > 
> > > 	dep ; rfi
> > > 
> > > dependency relation, where the accesses in the middle are plain and 
> > > non-racy.  Should the LKMM be changed to allow this?
> > > 
> > 
> > For this particular question, do we need to consider code as the follow?
> > 
> > 	r1 = READ_ONCE(x);  // f
> > 	if (r == 1) {
> > 		local_v = &y; // g
> > 		do_something_a();
> > 	}
> > 	else {
> > 		local_v = &y;
> > 		do_something_b();
> > 	}
> > 
> > 	r2 = READ_ONCE(*local_v); // e
> > 
> > , do we have the guarantee that the first READ_ONCE() happens before the
> > second one? Can compiler optimize the code as:
> > 
> > 	r2 = READ_ONCE(y);
> > 	r1 = READ_ONCE(x);
> 
> Well, it can't do that because the compiler isn't allowed to reorder
> volatile accesses (which includes READ_ONCE).  But the compiler could
> do:
> 
> 	r1 = READ_ONCE(x);
> 	r2 = READ_ONCE(y);
> 
> > 	if (r == 1) {
> > 		do_something_a();
> > 	}
> > 	else {
> > 		do_something_b();
> > 	}
> > 
> > ? Although we have:
> > 
> > 	f ->dep g ->rfi ->addr e
> 
> This would be an example of a problem Paul has described on several
> occasions, where both arms of an "if" statement store the same value
> (in this case to local_v).  This problem arises even when local
> variables are not involved.  For example:
> 
> 	if (READ_ONCE(x) == 0) {
> 		WRITE_ONCE(y, 1);
> 		do_a();
> 	} else {
> 		WRITE_ONCE(y, 1);
> 		do_b();
> 	}
> 
> The compiler can change this to:
> 
> 	r = READ_ONCE(x);
> 	WRITE_ONCE(y, 1);
> 	if (r == 0)
> 		do_a();
> 	else
> 		do_b();
> 
> thus allowing the marked accesses to be reordered by the CPU and
> breaking the apparent control dependency.
> 
> So the answer to your question is: No, we don't have this guarantee,
> but the reason is because of doing the same store in both arms, not
> because of the use of local variables.
> 

Right, I was thinking about something unrelated.. but how about the
following case:

	local_v = &y;
	r1 = READ_ONCE(*x); // f

	if (r1 == 1) {
		local_v = &y; // e
	} else {
		local_v = &z; // d
	}

	p = READ_ONCE(local_v); // g

	r2 = READ_ONCE(*p);   // h

if r1 == 1, we definitely think we have:

	f ->ctrl e ->rfi g ->addr h

, and if we treat ctrl;rfi as "to-r", then we have "f" happens before
"h". However compile can optimze the above as:

	local_v = &y;

	r1 = READ_ONCE(*x); // f

	if (r1 != 1) {
		local_v = &z; // d
	}

	p = READ_ONCE(local_v); // g

	r2 = READ_ONCE(*p);   // h

, and when this gets executed, I don't think we have the guarantee we
have "f" happens before "h", because CPU can do optimistic read for "g"
and "h".

Part of this is because when we take plain access into consideration, we
won't guarantee a read-from or other relations exists if compiler
optimization happens.

Maybe I'm missing something subtle, but just try to think through the
effect of making dep; rfi as "to-r".

Regards,
Boqun

> Alan