Re: Memory-ordering recipes

[Paul E. McKenney]

On Thu, Sep 21, 2017 at 02:45:31PM +0200, Peter Zijlstra wrote:
> On Sun, Sep 17, 2017 at 04:05:09PM -0700, Paul E. McKenney wrote:
> 
> > So what litmus tests are needed?  Here is my initial set:
> > 
> > 1.	Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB

I grouped the expansions of all of these names at the end.

> > 	Lots of variety here, can in some cases substitute:
> > 	
> > 	a.	READ_ONCE() for smp_load_acquire()
> > 	b.	WRITE_ONCE() for smp_store_release()
> > 	c.	Dependencies for both smp_load_acquire() and
> > 		smp_store_release().
> > 	d.	smp_wmb() for smp_store_release() in first thread
> > 		of ISA2 and Z6.2.
> > 	e.	smp_rmb() for smp_load_acquire() in last thread of ISA2.

The key point of these is to illustrate patterns that require only
the lightest ordering.

> > 2.	MP (see test6.pdf for nickname translation)
> > 
> > 	a.	smp_store_release() / smp_load_acquire()
> > 	b.	rcu_assign_pointer() / rcu_dereference()
> > 	c.	smp_wmb() / smp_rmb()
> > 	d.	Replacing either of the above with smp_mb()

This one is a workhorse, used very frequently.

> > 3.	SB
> > 
> > 	a.	smp_mb(), as in lockless wait-wakeup coordination.
> > 		And as in sys_membarrier()-scheduler coordination,
> > 		for that matter.

This is also used frequently, for example, in lockless wait-wakeup
situations.

> > Others?

Someone (quite rightly) suggested adding some single-variable SC
examples, which I will do.

> So I have no idea what you're proposing here. The above is just a bunch
> of words without meaning :-(

As Boqun said on IRC, this URL is your friend:

	https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

Many of the names seem quite arbitrary, but the abbreviation can be useful.

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);

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);

3.LB is simply a three-CPU extension of LB, and "LB" by itself is
sometimes used to cover an arbitrary number of CPUs:

	CPU 0			CPU 1			CPU 2

	r1 = READ_ONCE(x);	r2 = READ_ONCE(y);	r3 = READ_ONCE(z);
	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	WRITE_ONCE(x, 1);

	BUG_ON(r1 == 1 && r2 == 1 && r3 == 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);

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.

							Thanx, Paul