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 for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20160126010646.GH4503@linux.vnet.ibm.com>
Date:	Mon, 25 Jan 2016 17:06:46 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Will Deacon <will.deacon@....com>
Cc:	Leonid Yegoshin <Leonid.Yegoshin@...tec.com>,
	Peter Zijlstra <peterz@...radead.org>,
	"Michael S. Tsirkin" <mst@...hat.com>,
	linux-kernel@...r.kernel.org, Arnd Bergmann <arnd@...db.de>,
	linux-arch@...r.kernel.org,
	Andrew Cooper <andrew.cooper3@...rix.com>,
	Russell King - ARM Linux <linux@....linux.org.uk>,
	virtualization@...ts.linux-foundation.org,
	Stefano Stabellini <stefano.stabellini@...citrix.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...e.hu>, "H. Peter Anvin" <hpa@...or.com>,
	Joe Perches <joe@...ches.com>,
	David Miller <davem@...emloft.net>, linux-ia64@...r.kernel.org,
	linuxppc-dev@...ts.ozlabs.org, linux-s390@...r.kernel.org,
	sparclinux@...r.kernel.org, linux-arm-kernel@...ts.infradead.org,
	linux-metag@...r.kernel.org, linux-mips@...ux-mips.org,
	x86@...nel.org, user-mode-linux-devel@...ts.sourceforge.net,
	adi-buildroot-devel@...ts.sourceforge.net,
	linux-sh@...r.kernel.org, linux-xtensa@...ux-xtensa.org,
	xen-devel@...ts.xenproject.org, Ralf Baechle <ralf@...ux-mips.org>,
	Ingo Molnar <mingo@...nel.org>, ddaney.cavm@...il.com,
	james.hogan@...tec.com, Michael Ellerman <mpe@...erman.id.au>
Subject: Re: [v3,11/41] mips: reuse asm-generic/barrier.h

On Mon, Jan 25, 2016 at 02:41:34PM +0000, Will Deacon wrote:
> On Fri, Jan 15, 2016 at 11:28:45AM -0800, Paul E. McKenney wrote:
> > On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
> > > On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
> > > > See my earlier reply [1] (but also, your WRC Linux example looks more
> > > > like a variant on WWC and I couldn't really follow it).
> > > 
> > > I will revisit my WRC Linux example.  And yes, creating litmus tests
> > > that use non-fake dependencies is still a bit of an undertaking.  :-/
> > > I am sure that it will seem more natural with time and experience...
> > 
> > Hmmm...  You are quite right, I did do WWC.  I need to change cpu2()'s
> > last access from a store to a load to get WRC.  Plus the levels of
> > indirection definitely didn't match up, did they?
> 
> Nope, it was pretty baffling!

"It is a service that I provide."  ;-)

> > 	struct foo {
> > 		struct foo *next;
> > 	};
> > 	struct foo a;
> > 	struct foo b;
> > 	struct foo c = { &a };
> > 	struct foo d = { &b };
> > 	struct foo x = { &c };
> > 	struct foo y = { &d };
> > 	struct foo *r1, *r2, *r3;
> > 
> > 	void cpu0(void)
> > 	{
> > 		WRITE_ONCE(x.next, &y);
> > 	}
> > 
> > 	void cpu1(void)
> > 	{
> > 		r1 = lockless_dereference(x.next);
> > 		WRITE_ONCE(r1->next, &x);
> > 	}
> > 
> > 	void cpu2(void)
> > 	{
> > 		r2 = lockless_dereference(y.next);
> > 		r3 = READ_ONCE(r2->next);
> > 	}
> > 
> > In this case, it is legal to end the run with:
> > 
> > 	r1 == &y && r2 == &x && r3 == &c
> > 
> > Please see below for a ppcmem litmus test.
> > 
> > So, did I get it right this time?  ;-)
> 
> The code above looks correct to me (in that it matches WRC+addrs),
> but your litmus test:
> 
> > PPC WRCnf+addrs
> > ""
> > {
> > 0:r2=x; 0:r3=y;
> > 1:r2=x; 1:r3=y;
> > 2:r2=x; 2:r3=y;
> > c=a; d=b; x=c; y=d;
> > }
> >  P0           | P1            | P2            ;
> >  stw r3,0(r2) | lwz r8,0(r2)  | lwz r8,0(r3)  ;
> >               | stw r2,0(r3)  | lwz r9,0(r8)  ;
> > exists
> > (1:r8=y /\ 2:r8=x /\ 2:r9=c)
> 
> Seems to be missing the address dependency on P1.

You are quite correct!  How about the following?

As before, both herd and ppcmem say that the cycle is allowed, as
expected, given non-transitive ordering.  To prohibit the cycle, P1
needs a suitable memory-barrier instruction.

							Thanx, Paul

------------------------------------------------------------------------

PPC WRCnf+addrs
""
{
0:r2=x; 0:r3=y;
1:r2=x; 1:r3=y;
2:r2=x; 2:r3=y;
c=a; d=b; x=c; y=d;
}
 P0           | P1            | P2            ;
 stw r3,0(r2) | lwz r8,0(r2)  | lwz r8,0(r3)  ;
              | stw r2,0(r8)  | lwz r9,0(r8)  ;
exists
(1:r8=y /\ 2:r8=x /\ 2:r9=c)

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ