Writes, smp_wmb(), and transitivity?

Writes, smp_wmb(), and transitivity?

[Paul E. McKenney]

Hello!

Some architectures provide local transitivity for a chain of threads doing
writes separated by smp_wmb(), as exemplified by the litmus tests below.
The pattern is that each thread writes to a its own variable, does an
smp_wmb(), then writes a different value to the next thread's variable.

I don't know of a use of this, but if everyone supports it, it might
be good to mandate it.  Status quo is that smp_wmb() is non-transitive,
so it currently isn't supported.

Anyone know of any architectures that do -not- support this?

Assuming all architectures -do- support this, any arguments -against-
officially supporting it in Linux?

							Thanx, Paul

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

Two threads:

	int a, b;

	void thread0(void)
	{
		WRITE_ONCE(a, 1);
		smp_wmb();
		WRITE_ONCE(b, 2);
	}

	void thread1(void)
	{
		WRITE_ONCE(b, 1);
		smp_wmb();
		WRITE_ONCE(a, 2);
	}

	/* After all threads have completed and the dust has settled... */

	BUG_ON(a == 1 && b == 1);

Three threads:

	int a, b, c;

	void thread0(void)
	{
		WRITE_ONCE(a, 1);
		smp_wmb();
		WRITE_ONCE(b, 2);
	}

	void thread1(void)
	{
		WRITE_ONCE(b, 1);
		smp_wmb();
		WRITE_ONCE(c, 2);
	}

	void thread2(void)
	{
		WRITE_ONCE(c, 1);
		smp_wmb();
		WRITE_ONCE(a, 2);
	}

	/* After all threads have completed and the dust has settled... */

	BUG_ON(a == 1 && b == 1 && c == 1);

Four threads:

	int a, b, c, d;

	void thread0(void)
	{
		WRITE_ONCE(a, 1);
		smp_wmb();
		WRITE_ONCE(b, 2);
	}

	void thread1(void)
	{
		WRITE_ONCE(b, 1);
		smp_wmb();
		WRITE_ONCE(c, 2);
	}

	void thread2(void)
	{
		WRITE_ONCE(c, 1);
		smp_wmb();
		WRITE_ONCE(d, 2);
	}

	void thread3(void)
	{
		WRITE_ONCE(d, 1);
		smp_wmb();
		WRITE_ONCE(a, 2);
	}

	/* After all threads have completed and the dust has settled... */

	BUG_ON(a == 1 && b == 1 && c == 1 && d == 1);

And so on...

Re: Writes, smp_wmb(), and transitivity?

[Will Deacon]

On Mon, Feb 15, 2016 at 09:58:25AM -0800, Paul E. McKenney wrote:
> Hello!

Hi Paul,

> Some architectures provide local transitivity for a chain of threads doing
> writes separated by smp_wmb(), as exemplified by the litmus tests below.
> The pattern is that each thread writes to a its own variable, does an
> smp_wmb(), then writes a different value to the next thread's variable.
> 
> I don't know of a use of this, but if everyone supports it, it might
> be good to mandate it.  Status quo is that smp_wmb() is non-transitive,
> so it currently isn't supported.
> 
> Anyone know of any architectures that do -not- support this?
> 
> Assuming all architectures -do- support this, any arguments -against-
> officially supporting it in Linux?
> 
> 							Thanx, Paul
> 
> ------------------------------------------------------------------------
> 
> Two threads:
> 
> 	int a, b;
> 
> 	void thread0(void)
> 	{
> 		WRITE_ONCE(a, 1);
> 		smp_wmb();
> 		WRITE_ONCE(b, 2);
> 	}
> 
> 	void thread1(void)
> 	{
> 		WRITE_ONCE(b, 1);
> 		smp_wmb();
> 		WRITE_ONCE(a, 2);
> 	}
> 
> 	/* After all threads have completed and the dust has settled... */
> 
> 	BUG_ON(a == 1 && b == 1);

My understanding is that this test, and the generalisation to n threads,
is forbidden on ARM. However, the transitivity of DMB ST (used to
construct smp_wmb()) has been the subject of long debates, because we
allow the following test:


P0:
Wx = 1

P1:
Rx == 1
DMB ST
Wy = 1

P2:
Ry == 1
<addr dep>
Rx == 0


so I'd be uneasy about saying "it's all transitive".

Will

Re: Writes, smp_wmb(), and transitivity?

[Paul E. McKenney]

On Mon, Feb 15, 2016 at 06:58:32PM +0000, Will Deacon wrote:
> On Mon, Feb 15, 2016 at 09:58:25AM -0800, Paul E. McKenney wrote:
> > Hello!
> 
> Hi Paul,
> 
> > Some architectures provide local transitivity for a chain of threads doing
> > writes separated by smp_wmb(), as exemplified by the litmus tests below.
> > The pattern is that each thread writes to a its own variable, does an
> > smp_wmb(), then writes a different value to the next thread's variable.
> > 
> > I don't know of a use of this, but if everyone supports it, it might
> > be good to mandate it.  Status quo is that smp_wmb() is non-transitive,
> > so it currently isn't supported.
> > 
> > Anyone know of any architectures that do -not- support this?
> > 
> > Assuming all architectures -do- support this, any arguments -against-
> > officially supporting it in Linux?
> > 
> > 							Thanx, Paul
> > 
> > ------------------------------------------------------------------------
> > 
> > Two threads:
> > 
> > 	int a, b;
> > 
> > 	void thread0(void)
> > 	{
> > 		WRITE_ONCE(a, 1);
> > 		smp_wmb();
> > 		WRITE_ONCE(b, 2);
> > 	}
> > 
> > 	void thread1(void)
> > 	{
> > 		WRITE_ONCE(b, 1);
> > 		smp_wmb();
> > 		WRITE_ONCE(a, 2);
> > 	}
> > 
> > 	/* After all threads have completed and the dust has settled... */
> > 
> > 	BUG_ON(a == 1 && b == 1);
> 
> My understanding is that this test, and the generalisation to n threads,
> is forbidden on ARM. However, the transitivity of DMB ST (used to
> construct smp_wmb()) has been the subject of long debates, because we
> allow the following test:
> 
> 
> P0:
> Wx = 1
> 
> P1:
> Rx == 1
> DMB ST
> Wy = 1
> 
> P2:
> Ry == 1
> <addr dep>
> Rx == 0
> 
> 
> so I'd be uneasy about saying "it's all transitive".

Agreed!  For one thing, doesn't DMB ST need writes on both sides?

But that is one reason that I am only semi-enthusiastic about this.
The potentially locally transitive case is -very- restrictive, applying
only to situations where -all- accesses are writes.

							Thanx, Paul

Re: Writes, smp_wmb(), and transitivity?

[Will Deacon]

On Mon, Feb 15, 2016 at 12:35:12PM -0800, Paul E. McKenney wrote:
> On Mon, Feb 15, 2016 at 06:58:32PM +0000, Will Deacon wrote:
> > On Mon, Feb 15, 2016 at 09:58:25AM -0800, Paul E. McKenney wrote:
> > > Some architectures provide local transitivity for a chain of threads doing
> > > writes separated by smp_wmb(), as exemplified by the litmus tests below.
> > > The pattern is that each thread writes to a its own variable, does an
> > > smp_wmb(), then writes a different value to the next thread's variable.
> > > 
> > > I don't know of a use of this, but if everyone supports it, it might
> > > be good to mandate it.  Status quo is that smp_wmb() is non-transitive,
> > > so it currently isn't supported.
> > > 
> > > Anyone know of any architectures that do -not- support this?
> > > 
> > > Assuming all architectures -do- support this, any arguments -against-
> > > officially supporting it in Linux?
> > > 
> > > 							Thanx, Paul
> > > 
> > > ------------------------------------------------------------------------
> > > 
> > > Two threads:
> > > 
> > > 	int a, b;
> > > 
> > > 	void thread0(void)
> > > 	{
> > > 		WRITE_ONCE(a, 1);
> > > 		smp_wmb();
> > > 		WRITE_ONCE(b, 2);
> > > 	}
> > > 
> > > 	void thread1(void)
> > > 	{
> > > 		WRITE_ONCE(b, 1);
> > > 		smp_wmb();
> > > 		WRITE_ONCE(a, 2);
> > > 	}
> > > 
> > > 	/* After all threads have completed and the dust has settled... */
> > > 
> > > 	BUG_ON(a == 1 && b == 1);
> > 
> > My understanding is that this test, and the generalisation to n threads,
> > is forbidden on ARM. However, the transitivity of DMB ST (used to
> > construct smp_wmb()) has been the subject of long debates, because we
> > allow the following test:
> > 
> > 
> > P0:
> > Wx = 1
> > 
> > P1:
> > Rx == 1
> > DMB ST
> > Wy = 1
> > 
> > P2:
> > Ry == 1
> > <addr dep>
> > Rx == 0
> > 
> > 
> > so I'd be uneasy about saying "it's all transitive".
> 
> Agreed!  For one thing, doesn't DMB ST need writes on both sides?

Yes, but it's a common trap that people fall into where they think the
above is forbidden because the DMB ST in P1 should order P0's write
before its own write of y.

> But that is one reason that I am only semi-enthusiastic about this.
> The potentially locally transitive case is -very- restrictive, applying
> only to situations where -all- accesses are writes.

I think that we will confuse people more by trying to describe the
restricted case where we provide order than if we blanket say that its
not transitive. I know Linus prefers to be as strong as possible, but
this doesn't look like a realistic programming paradigm and having a
straightforward rule that "rmb and wmb are not transitive" is much
easier for people to deal with in my opinion.

Will

Re: Writes, smp_wmb(), and transitivity?

[Paul E. McKenney]

On Tue, Feb 16, 2016 at 09:53:20AM +0000, Will Deacon wrote:
> On Mon, Feb 15, 2016 at 12:35:12PM -0800, Paul E. McKenney wrote:
> > On Mon, Feb 15, 2016 at 06:58:32PM +0000, Will Deacon wrote:
> > > On Mon, Feb 15, 2016 at 09:58:25AM -0800, Paul E. McKenney wrote:
> > > > Some architectures provide local transitivity for a chain of threads doing
> > > > writes separated by smp_wmb(), as exemplified by the litmus tests below.
> > > > The pattern is that each thread writes to a its own variable, does an
> > > > smp_wmb(), then writes a different value to the next thread's variable.
> > > > 
> > > > I don't know of a use of this, but if everyone supports it, it might
> > > > be good to mandate it.  Status quo is that smp_wmb() is non-transitive,
> > > > so it currently isn't supported.
> > > > 
> > > > Anyone know of any architectures that do -not- support this?
> > > > 
> > > > Assuming all architectures -do- support this, any arguments -against-
> > > > officially supporting it in Linux?
> > > > 
> > > > 							Thanx, Paul
> > > > 
> > > > ------------------------------------------------------------------------
> > > > 
> > > > Two threads:
> > > > 
> > > > 	int a, b;
> > > > 
> > > > 	void thread0(void)
> > > > 	{
> > > > 		WRITE_ONCE(a, 1);
> > > > 		smp_wmb();
> > > > 		WRITE_ONCE(b, 2);
> > > > 	}
> > > > 
> > > > 	void thread1(void)
> > > > 	{
> > > > 		WRITE_ONCE(b, 1);
> > > > 		smp_wmb();
> > > > 		WRITE_ONCE(a, 2);
> > > > 	}
> > > > 
> > > > 	/* After all threads have completed and the dust has settled... */
> > > > 
> > > > 	BUG_ON(a == 1 && b == 1);
> > > 
> > > My understanding is that this test, and the generalisation to n threads,
> > > is forbidden on ARM. However, the transitivity of DMB ST (used to
> > > construct smp_wmb()) has been the subject of long debates, because we
> > > allow the following test:
> > > 
> > > 
> > > P0:
> > > Wx = 1
> > > 
> > > P1:
> > > Rx == 1
> > > DMB ST
> > > Wy = 1
> > > 
> > > P2:
> > > Ry == 1
> > > <addr dep>
> > > Rx == 0
> > > 
> > > 
> > > so I'd be uneasy about saying "it's all transitive".
> > 
> > Agreed!  For one thing, doesn't DMB ST need writes on both sides?
> 
> Yes, but it's a common trap that people fall into where they think the
> above is forbidden because the DMB ST in P1 should order P0's write
> before its own write of y.

True enough.

> > But that is one reason that I am only semi-enthusiastic about this.
> > The potentially locally transitive case is -very- restrictive, applying
> > only to situations where -all- accesses are writes.
> 
> I think that we will confuse people more by trying to describe the
> restricted case where we provide order than if we blanket say that its
> not transitive. I know Linus prefers to be as strong as possible, but
> this doesn't look like a realistic programming paradigm and having a
> straightforward rule that "rmb and wmb are not transitive" is much
> easier for people to deal with in my opinion.

That is a good explanation of why I am only semi-enthusiastic about
this.  ;-)

							Thanx, Paul

Re: Writes, smp_wmb(), and transitivity?

[Linus Torvalds]

On Mon, Feb 15, 2016 at 9:58 AM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
>
> Two threads:
>
>         int a, b;
>
>         void thread0(void)
>         {
>                 WRITE_ONCE(a, 1);
>                 smp_wmb();
>                 WRITE_ONCE(b, 2);
>         }
>
>         void thread1(void)
>         {
>                 WRITE_ONCE(b, 1);
>                 smp_wmb();
>                 WRITE_ONCE(a, 2);
>         }
>
>         /* After all threads have completed and the dust has settled... */
>
>         BUG_ON(a == 1 && b == 1);

So the more I look at that kind of litmus test, the less I think that
we should care, because I can't come up with a scenario in where that
kind of test makes sense. without even a possibility of any causal
relationship between the two, I can't say why we'd ever care about the
ordering of the (independent) writes to the individual variables.

If somebody can make up a causal chain, things differ. But as long as
all the CPU's are just doing locally ordered writes, I don't think we
need to care about a global store ordering.

              Linus

Re: Writes, smp_wmb(), and transitivity?

[Paul E. McKenney]

On Tue, Feb 16, 2016 at 10:59:08AM -0800, Linus Torvalds wrote:
> On Mon, Feb 15, 2016 at 9:58 AM, Paul E. McKenney
> <paulmck-23VcF4HTsmIX0ybBhKVfKdBPR1lH4CV8@public.gmane.org> wrote:
> >
> > Two threads:
> >
> >         int a, b;
> >
> >         void thread0(void)
> >         {
> >                 WRITE_ONCE(a, 1);
> >                 smp_wmb();
> >                 WRITE_ONCE(b, 2);
> >         }
> >
> >         void thread1(void)
> >         {
> >                 WRITE_ONCE(b, 1);
> >                 smp_wmb();
> >                 WRITE_ONCE(a, 2);
> >         }
> >
> >         /* After all threads have completed and the dust has settled... */
> >
> >         BUG_ON(a == 1 && b == 1);
> 
> So the more I look at that kind of litmus test, the less I think that
> we should care, because I can't come up with a scenario in where that
> kind of test makes sense. without even a possibility of any causal
> relationship between the two, I can't say why we'd ever care about the
> ordering of the (independent) writes to the individual variables.
> 
> If somebody can make up a causal chain, things differ. But as long as
> all the CPU's are just doing locally ordered writes, I don't think we
> need to care about a global store ordering.

Works for me!  (Yes, I can artificially generate a use case for this
thing, but all the ones I have come up with have some better and more
sane way to get the job done.  So I completely agree with your not caring
about it.)

So for transitivity, we focus on causal chains, where one task writes
to some variable that the next task reads.

In addition, if all threads use full memory barriers throughout, as in
smp_mb(), then full ordering is of course provided regardless of the
pattern of reads and writes.

							Thanx, Paul