Re: Memory-ordering recipes

From: Peter Zijlstra
Date: Thu Sep 21 2017 - 12:16:08 EST


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?