linux-kernel - Re: Memory-ordering recipes

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: <20170921161547.w6kcp26pism3r7id@hirez.programming.kicks-ass.net>
Date:   Thu, 21 Sep 2017 18:15:47 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:     j.alglave@....ac.uk, luc.maranget@...ia.fr, parri.andrea@...il.com,
        stern@...land.harvard.edu, dhowells@...hat.com,
        will.deacon@....com, boqun.feng@...il.com, npiggin@...il.com,
        linux-kernel@...r.kernel.org
Subject: Re: Memory-ordering recipes

On Thu, Sep 21, 2017 at 08:26:42AM -0700, Paul E. McKenney wrote:
> ISA2 is the first one on page 2, and has this pattern of reads and
> writes:
> 
> 	CPU 0			CPU 1			CPU 2
> 
> 	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
> 	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	r3 = READ_ONCE(x);
> 
> 	BUG_ON(r1 == 1 && r2 == 1 && r3 == 0);
> 
> Arbitrary ordering can be added to all of these litmus-test patterns,
> for example, the writes to y and z might become smp_store_release()
> and the read from z might become smp_load_acquire().  Or, alternatively,
> smp_mb() might be placed between accesses on all thread CPUs.  The key
> point is that "ISA2" identifies not a specific litmus test, but instead a
> family of them with the same pattern of reads, writes and RMW operations,
> but with different ordering properties.
> 
> Z6.3 is the second one on page 2:
> 
> 	CPU 0			CPU 1			CPU 2
> 
> 	WRITE_ONCE(x, 2);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
> 	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	WRITE_ONCE(x, 1);
> 
> 	BUG_ON(r1 == 1 && r2 == 1 && x == 2);

But why are these useful to include in a recipes list? I would imagine
those should cover the simple 2 threads stuff. Once you go fancy and
need 3 CPUs I feel people had better know wth they're on about.

> LB is the last on on the extreme left of page 1.  "LB" stands for
> "load buffering", and each CPU's first access is a load and last
> access is a store:
> 
> 	CPU 0			CPU 1
> 
> 	r1 = READ_ONCE(x);	r2 = READ_ONCE(y);
> 	WRITE_ONCE(y, 1);	WRITE_ONCE(x, 1);
> 
> 	BUG_ON(r1 == 1 && r2 == 1);

> MP is the second on the extreme left of page 1.  "MP" stands for "message
> passing", and is used very heavily.  The idea is that "x" is the message
> (sent by CPU 0), and "y" is a flag saying that the message is ready to
> be received (by CPU 1).
> 
> 	CPU 0			CPU 1
> 
> 	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);
> 	WRITE_ONCE(y, 1);	r1 = READ_ONCE(x);
> 
> 	BUG_ON(r1 == 1 && r2 == 0);

Right, these two are fairly common patterns.

> SB is the fourth on the extreme left of page 1.  "SB" stands for "store
> buffering" because systems without store buffers won't reorder this one.
> 
> 	CPU 0			CPU 1
> 
> 	WRITE_ONCE(x, 1);	WRITE_ONCE(y, 1);
> 	r1 = READ_ONCE(y);	r2 = READ_ONCE(x);
> 
> 	BUG_ON(r1 == 0 && r2 == 0);
> 
> Does that help?
> 
> Oh, and the actual recipes would include ordering as indicated by
> the sub-bullets.

Which just generates a terrible lot of noise. Why would people be
interested in these permutations? Why not the minimal set that makes the
guarantee?

Also, none of these cover 'simple' stuff like a ring-buffer.

So I have to ask, what is the purpose of this recipes list?