Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1241371 > unrolled thread

[PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation

Started byWill Deacon <will.deacon@arm.com>
First post2015-10-07 13:10 +0200
Last post2015-10-09 19:30 +0200
Articles 6 on this page of 26 — 4 participants

Back to article view | Back to linux.kernel

Contents

  [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation Will Deacon <will.deacon@arm.com> - 2015-10-07 13:10 +0200
    Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-07 13:20 +0200
      Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Will Deacon <will.deacon@arm.com> - 2015-10-07 15:30 +0200
        Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-07 17:00 +0200
        Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-07 17:30 +0200
          Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Michael Ellerman <mpe@ellerman.id.au> - 2015-10-08 06:00 +0200
            Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-08 13:20 +0200
              Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Will Deacon <will.deacon@arm.com> - 2015-10-08 15:00 +0200
                Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-09 00:20 +0200
                  Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Will Deacon <will.deacon@arm.com> - 2015-10-09 12:00 +0200
                    Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-09 13:30 +0200
                      Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-09 19:50 +0200
                    Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-09 19:50 +0200
                      Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Will Deacon <will.deacon@arm.com> - 2015-10-09 20:40 +0200
                        Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-13 01:40 +0200
              Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-08 23:50 +0200
                Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-09 09:30 +0200
                Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-09 10:40 +0200
                  Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Will Deacon <will.deacon@arm.com> - 2015-10-09 11:50 +0200
                    Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-09 13:10 +0200
                      Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Will Deacon <will.deacon@arm.com> - 2015-10-09 14:50 +0200
                    Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-09 13:20 +0200
                      Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Will Deacon <will.deacon@arm.com> - 2015-10-09 15:00 +0200
                        Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-09 15:10 +0200
                    Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation Peter Zijlstra <peterz@infradead.org> - 2015-10-09 13:20 +0200
                    Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and  update documentation "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2015-10-09 19:30 +0200

Page 2 of 2 — ← Prev page 1 [2]

#1243319 — Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation

FromWill Deacon <will.deacon@arm.com>
Date2015-10-09 14:50 +0200
SubjectRe: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation
Message-ID<qhFhw-2oj-23@gated-at.bofh.it>
In reply to#1243250
On Fri, Oct 09, 2015 at 01:02:46PM +0200, Peter Zijlstra wrote:
> On Fri, Oct 09, 2015 at 10:40:39AM +0100, Will Deacon wrote:
> > Stepping back a second, I believe that there are three cases:
> > 
> > 
> >  RELEASE X -> ACQUIRE Y (same CPU)
> >    * Needs a barrier on TSO architectures for full ordering
> 	+PPC
> 
> >  UNLOCK X -> LOCK Y (same CPU)
> >    * Needs a barrier on PPC for full ordering
> 
> 
> >  RELEASE X -> ACQUIRE X (different CPUs)
>     * Fully ordered everywhere...
>     * ... but needs a barrier on TSO + PPC to become a full barrier
> 
> >  UNLOCK X -> ACQUIRE X (different CPUs)
> 
> s/ACQUIRE/LOCK/ ?

Yes, sorry.

Will
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1243252 — Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation

FromPeter Zijlstra <peterz@infradead.org>
Date2015-10-09 13:20 +0200
SubjectRe: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation
Message-ID<qhDSq-tO-5@gated-at.bofh.it>
In reply to#1243198
On Fri, Oct 09, 2015 at 10:40:39AM +0100, Will Deacon wrote:
> > Which leads me to think I would like to suggest alternative rules for
> > RELEASE/ACQUIRE (to replace those Will suggested; as I think those are
> > partly responsible for my confusion).
> 
> Yeah, sorry. I originally used the phrase "fully ordered" but changed it
> to "full barrier", which has stronger transitivity (newly understood
> definition) requirements that I didn't intend.

> Are we explicit about the difference between "fully ordered" and "full
> barrier" somewhere else, because this looks like it will confuse people.

I suspect we don't.

> >  - RELEASE -> ACQUIRE can be upgraded to a full barrier (including
> >    transitivity) using smp_mb__release_acquire(), either before RELEASE
> >    or after ACQUIRE (but consistently [*]).
> 
> Hmm, but we don't actually need this for RELEASE -> ACQUIRE, afaict. This
> is just needed for UNLOCK -> LOCK, and is exactly what RCU is currently
> using (for PPC only).

No, we do need that. RELEASE/ACQUIRE is RCpc for TSO as well as PPC.

UNLOCK/LOCK is only RCpc for PPC, the rest of the world has RCsc for
UNLOCK/LOCK.

The reason RELEASE/ACQUIRE differ from UNLOCK/LOCK is the fundamental
difference between ACQUIRE and LOCK.

Where ACQUIRE really is just a LOAD, LOCK ends up fundamentally being a
RmW and a control dependency.


Now, if you want to upgrade your RCpc RELEASE/ACQUIRE to RCsc, you need
to do that on the inside (either after ACQUIRE or before RELEASE), this
is crucial (as per Paul's argument) for the case where the RELEASE and
ACQUIRE happen on different CPUs.

IFF RELEASE and ACQUIRE happen on the _same_ CPU, then it doesn't
matter and you can place the barrier in any of the 3 possible locations
(before RELEASE, between RELEASE and ACQUIRE, after ACQUIRE).


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1243320 — Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation

FromWill Deacon <will.deacon@arm.com>
Date2015-10-09 15:00 +0200
SubjectRe: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation
Message-ID<qhFrc-2zB-1@gated-at.bofh.it>
In reply to#1243252
On Fri, Oct 09, 2015 at 01:12:02PM +0200, Peter Zijlstra wrote:
> On Fri, Oct 09, 2015 at 10:40:39AM +0100, Will Deacon wrote:
> > > Which leads me to think I would like to suggest alternative rules for
> > > RELEASE/ACQUIRE (to replace those Will suggested; as I think those are
> > > partly responsible for my confusion).
> > 
> > Yeah, sorry. I originally used the phrase "fully ordered" but changed it
> > to "full barrier", which has stronger transitivity (newly understood
> > definition) requirements that I didn't intend.
> 
> > Are we explicit about the difference between "fully ordered" and "full
> > barrier" somewhere else, because this looks like it will confuse people.
> 
> I suspect we don't.
> 
> > >  - RELEASE -> ACQUIRE can be upgraded to a full barrier (including
> > >    transitivity) using smp_mb__release_acquire(), either before RELEASE
> > >    or after ACQUIRE (but consistently [*]).
> > 
> > Hmm, but we don't actually need this for RELEASE -> ACQUIRE, afaict. This
> > is just needed for UNLOCK -> LOCK, and is exactly what RCU is currently
> > using (for PPC only).
> 
> No, we do need that. RELEASE/ACQUIRE is RCpc for TSO as well as PPC.
> 
> UNLOCK/LOCK is only RCpc for PPC, the rest of the world has RCsc for
> UNLOCK/LOCK.
> 
> The reason RELEASE/ACQUIRE differ from UNLOCK/LOCK is the fundamental
> difference between ACQUIRE and LOCK.

But they don't actually differ in the kernel memory model we have right
now, thanks to PPC (we can't be stronger than the weakest implementation).
That's the whole reason we've got this unlock_lock mess!

> Where ACQUIRE really is just a LOAD, LOCK ends up fundamentally being a
> RmW and a control dependency.

Have you checked that this is true for the recent RELEASE/ACQUIRE
conversions in things like the qrwlock? In particular, we should annotate
those control dependencies to make them glaringly obvious if we want to
rely on sequentially-consistent locks (and also Alpha may need that).

> Now, if you want to upgrade your RCpc RELEASE/ACQUIRE to RCsc, you need
> to do that on the inside (either after ACQUIRE or before RELEASE), this
> is crucial (as per Paul's argument) for the case where the RELEASE and
> ACQUIRE happen on different CPUs.
> 
> IFF RELEASE and ACQUIRE happen on the _same_ CPU, then it doesn't
> matter and you can place the barrier in any of the 3 possible locations
> (before RELEASE, between RELEASE and ACQUIRE, after ACQUIRE).

Right, but these two need to be different barriers so that we don't
penalise TSO when UNLOCK -> LOCK ordering is required. That's why I was
proposing the local variant of smp_mb__after_release_acquire().

I think we're in agreement about the barriers we need, we just need to
name them (and then I'll cook a patch and we can GOTO 10).

Will
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1243334 — Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation

FromPeter Zijlstra <peterz@infradead.org>
Date2015-10-09 15:10 +0200
SubjectRe: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation
Message-ID<qhFAT-30e-31@gated-at.bofh.it>
In reply to#1243320
On Fri, Oct 09, 2015 at 01:51:11PM +0100, Will Deacon wrote:
> On Fri, Oct 09, 2015 at 01:12:02PM +0200, Peter Zijlstra wrote:
> > On Fri, Oct 09, 2015 at 10:40:39AM +0100, Will Deacon wrote:
> > > > Which leads me to think I would like to suggest alternative rules for
> > > > RELEASE/ACQUIRE (to replace those Will suggested; as I think those are
> > > > partly responsible for my confusion).
> > > 
> > > Yeah, sorry. I originally used the phrase "fully ordered" but changed it
> > > to "full barrier", which has stronger transitivity (newly understood
> > > definition) requirements that I didn't intend.
> > 
> > > Are we explicit about the difference between "fully ordered" and "full
> > > barrier" somewhere else, because this looks like it will confuse people.
> > 
> > I suspect we don't.
> > 
> > > >  - RELEASE -> ACQUIRE can be upgraded to a full barrier (including
> > > >    transitivity) using smp_mb__release_acquire(), either before RELEASE
> > > >    or after ACQUIRE (but consistently [*]).
> > > 
> > > Hmm, but we don't actually need this for RELEASE -> ACQUIRE, afaict. This
> > > is just needed for UNLOCK -> LOCK, and is exactly what RCU is currently
> > > using (for PPC only).
> > 
> > No, we do need that. RELEASE/ACQUIRE is RCpc for TSO as well as PPC.
> > 
> > UNLOCK/LOCK is only RCpc for PPC, the rest of the world has RCsc for
> > UNLOCK/LOCK.
> > 
> > The reason RELEASE/ACQUIRE differ from UNLOCK/LOCK is the fundamental
> > difference between ACQUIRE and LOCK.
> 
> But they don't actually differ in the kernel memory model we have right
> now, thanks to PPC (we can't be stronger than the weakest implementation).
> That's the whole reason we've got this unlock_lock mess!

Correct, which is why I've suggested to separate UNLOCK/LOCK from
RELEASE/ACQUIRE (again).

Even if only PPC is RCpc for locks, this means we need to have different
upgrade barriers (or suffer superfluous full barriers on TSO archs,
which I think we all want to avoid).

> > Where ACQUIRE really is just a LOAD, LOCK ends up fundamentally being a
> > RmW and a control dependency.
> 
> Have you checked that this is true for the recent RELEASE/ACQUIRE
> conversions in things like the qrwlock? In particular, we should annotate
> those control dependencies to make them glaringly obvious if we want to
> rely on sequentially-consistent locks (and also Alpha may need that).

I have not, let me make a note of that.

> > Now, if you want to upgrade your RCpc RELEASE/ACQUIRE to RCsc, you need
> > to do that on the inside (either after ACQUIRE or before RELEASE), this
> > is crucial (as per Paul's argument) for the case where the RELEASE and
> > ACQUIRE happen on different CPUs.
> > 
> > IFF RELEASE and ACQUIRE happen on the _same_ CPU, then it doesn't
> > matter and you can place the barrier in any of the 3 possible locations
> > (before RELEASE, between RELEASE and ACQUIRE, after ACQUIRE).
> 
> Right, but these two need to be different barriers so that we don't
> penalise TSO when UNLOCK -> LOCK ordering is required. That's why I was
> proposing the local variant of smp_mb__after_release_acquire().
> 
> I think we're in agreement about the barriers we need, we just need to
> name them (and then I'll cook a patch and we can GOTO 10).

 smp_mb__after_unlock_lock()
 smp_mb__after_release_acquire()

Would work, unless of course we can convince the PPC people to go RCsc
on their locks -- which per the benchmark result posted is fairly
painful :/

Then again, I do sympathise with them not wanting to find all the bugs
for being the odd duck.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1243254 — Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation

FromPeter Zijlstra <peterz@infradead.org>
Date2015-10-09 13:20 +0200
SubjectRe: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation
Message-ID<qhDSq-tO-9@gated-at.bofh.it>
In reply to#1243198
On Fri, Oct 09, 2015 at 10:40:39AM +0100, Will Deacon wrote:
> 
> >  - RELEASE -> ACQUIRE _chains_ (on shared variables) preserve causality,
> >    (because each link is fully ordered) but are not transitive.
> 
> Yup, and that's the same for UNLOCK -> LOCK, too.

Agreed, except RELEASE/ACQUIRE is more RCpc than UNLOCK/LOCK.

IFF we can get UNLOCK/LOCK as RCsc the chains are strongly transitive,
unlike the RELEASE/ACQUIRE chains, which will be weakly so.


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1243549 — Re: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation

From"Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Date2015-10-09 19:30 +0200
SubjectRe: [PATCH v2] barriers: introduce smp_mb__release_acquire and update documentation
Message-ID<qhJEu-l4-11@gated-at.bofh.it>
In reply to#1243198
On Fri, Oct 09, 2015 at 10:40:39AM +0100, Will Deacon wrote:
> On Fri, Oct 09, 2015 at 10:31:38AM +0200, Peter Zijlstra wrote:
> > On Thu, Oct 08, 2015 at 02:44:39PM -0700, Paul E. McKenney wrote:
> > > On Thu, Oct 08, 2015 at 01:16:38PM +0200, Peter Zijlstra wrote:
> > > > On Thu, Oct 08, 2015 at 02:50:36PM +1100, Michael Ellerman wrote:
> > > > > On Wed, 2015-10-07 at 08:25 -0700, Paul E. McKenney wrote:
> > > > 
> > > > > > Currently, we do need smp_mb__after_unlock_lock() to be after the
> > > > > > acquisition on PPC -- putting it between the unlock and the lock
> > > > > > of course doesn't cut it for the cross-thread unlock/lock case.
> > > > 
> > > > This ^, that makes me think I don't understand
> > > > smp_mb__after_unlock_lock.
> > > > 
> > > > How is:
> > > > 
> > > > 	UNLOCK x
> > > > 	smp_mb__after_unlock_lock()
> > > > 	LOCK y
> > > > 
> > > > a problem? That's still a full barrier.
> > > 
> > > The problem is that I need smp_mb__after_unlock_lock() to give me
> > > transitivity even if the UNLOCK happened on one CPU and the LOCK
> > > on another.  For that to work, the smp_mb__after_unlock_lock() needs
> > > to be either immediately after the acquire (the current choice) or
> > > immediately before the release (which would also work from a purely
> > > technical viewpoint, but I much prefer the current choice).
> > > 
> > > Or am I missing your point?
> > 
> > So lots of little confusions added up to complete fail :-{

I know that feeling!

> > Mostly I think it was the UNLOCK x + LOCK x are fully ordered (where I
> > forgot: but not against uninvolved CPUs) and RELEASE/ACQUIRE are
> > transitive (where I forgot: RELEASE/ACQUIRE _chains_ are transitive, but
> > again not against uninvolved CPUs).
> > 
> > Which leads me to think I would like to suggest alternative rules for
> > RELEASE/ACQUIRE (to replace those Will suggested; as I think those are
> > partly responsible for my confusion).
> 
> Yeah, sorry. I originally used the phrase "fully ordered" but changed it
> to "full barrier", which has stronger transitivity (newly understood
> definition) requirements that I didn't intend.
> 
> RELEASE -> ACQUIRE should be used for message passing between two CPUs
> and not have ordering effects on other observers unless they're part of
> the RELEASE -> ACQUIRE chain.
> 
> >  - RELEASE -> ACQUIRE is fully ordered (but not a full barrier) when
> >    they operate on the same variable and the ACQUIRE reads from the
> >    RELEASE. Notable, RELEASE/ACQUIRE are RCpc and lack transitivity.

RELEASE->ACQUIRE has local transistivity/causality.  However, it is more
than just message passing:

	void thread0(void)
	{
		r1 = READ_ONCE(a);
		WRITE_ONCE(b, 1);
		smp_store_release(&c, 1);
	}

	void thread1(void)
	{
		r2 = smp_store_acquire(&c);
		WRITE_ONCE(a, 1);
		r3 = READ_ONCE(b);
		smp_store_release(&d, 1);
	}

	void thread2(void)
	{
		r4 = smp_load_acquire(&d);
		WRITE_ONCE(a, 2);
		r5 = READ_ONCE(b);
	}

After the dust settles, if r2==1&&r4==1, we should also have
r1==0&&r3==1&&r5==1.  And here is the PowerPC ppcmem/herd model:

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

PPC LinuxAcqRelLocal
""
(*
 * Does a powerpc lwsync-based Acq-Rel chain provide local causality?
 * October 9, 2015: Yes.
 *)
{
a=0; b=0; c=0; d=0;
0:r0=1; 0:r11=a; 0:r12=b; 0:r13=c; 0:r14=d;
1:r0=1; 1:r11=a; 1:r12=b; 1:r13=c; 1:r14=d;
2:r0=2; 2:r11=a; 2:r12=b; 2:r13=c; 2:r14=d;
}
 P0            | P1            | P2            ;
 lwz r1,0(r11) | lwz r2,0(r13) | lwz r4,0(r14) ;
 stw r0,0(r12) | lwsync        | lwsync        ;
 lwsync        | stw r0,0(r11) | stw r0,0(r11) ;
 stw r0,0(r13) | lwz r3,0(r12) | lwz r5,0(r12) ;
               | lwsync        |               ;
               | stw r0,0(r14) |               ;
exists
(1:r2=1 /\ 2:r4=1 /\ (0:r1=1 \/ 0:r1=2 \/ 1:r3=0 \/ 2:r5=0))

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

This confirms the local causality/transitivity.

So let's add an uninvolved observer thread, which will also require adding
another variable to avoid ordering via cache coherence:

	void thread0(void)
	{
		r1 = READ_ONCE(a);
		WRITE_ONCE(b, 1);
		smp_store_release(&c, 1);
	}

	void thread1(void)
	{
		r2 = smp_store_acquire(&c);
		WRITE_ONCE(a, 1);
		r3 = READ_ONCE(b);
		smp_store_release(&d, 1);
	}

	void thread2(void)
	{
		r4 = smp_load_acquire(&d);
		WRITE_ONCE(a, 2);
		r5 = READ_ONCE(b);
		r6 = READ_ONCE(e);
	}

	void thread3(void) /* uninvolved observer */
	{
		WRITE_ONCE(e, 1);
		smp_mb();
		r7 = READ_ONCE(b);
	}

Can we see r2==1&&r4==1&&r6=0&&r7==0?  Here is the PowerPC model:

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

PPC LinuxAcqRelGlobal
""
(*
 * Does a powerpc lwsync-based Acq-Rel chain provide global causality?
 * October 9, 2015: No.
 *)
{
a=0; b=0; c=0; d=0; e=0;
0:r0=1; 0:r11=a; 0:r12=b; 0:r13=c; 0:r14=d; 0:r15=e;
1:r0=1; 1:r11=a; 1:r12=b; 1:r13=c; 1:r14=d; 1:r15=e;
2:r0=2; 2:r11=a; 2:r12=b; 2:r13=c; 2:r14=d; 2:r15=e;
3:r0=1; 3:r11=a; 3:r12=b; 3:r13=c; 3:r14=d; 3:r15=e;
}
 P0            | P1            | P2            | P3            ;
 lwz r1,0(r11) | lwz r2,0(r13) | lwz r4,0(r14) | stw r0,0(r15) ;
 stw r0,0(r12) | lwsync        | lwsync        | sync          ;
 lwsync        | stw r0,0(r11) | stw r0,0(r11) | lwz r7,0(r12) ;
 stw r0,0(r13) | lwz r3,0(r12) | lwz r5,0(r12) |               ;
               | lwsync        | lwz r6,0(r15) |               ;
               | stw r0,0(r14) |               |               ;
exists
(1:r2=1 /\ 2:r4=1 /\ 2:r6=0 /\ 3:r7=0)

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

And, as expected, P3 can see misordering because it is not involved
in the acquire-release chain.

> Are we explicit about the difference between "fully ordered" and "full
> barrier" somewhere else, because this looks like it will confuse people.

Probably not.  We need something meaning "local transitivity" on the
one hand and "global transitivity" on the other.  I suppose we could use
"causality" for the local case and "transitivity" for the global case,
but I do not believe that normal formal/mathematical usage matches this.

The term "single-copy atomic" could reasonably be used to mean "local
transitivity" and "multi-copy atomic" to mean "global transitivity",
but those are all too easy to confuse with each other, require a lot of
knowledge to understand, and don't exactly roll off the tongue.

The phrases "locally visible causality" and "globally visible causality"
should be (relatively) easy to understand, but don't exactly roll off
the tongue, either.

Maybe LVC and GVC?

LVC:  Locally visible causality:  If you are in the causal chain,
	you are guaranteed to see the ordering.  Otherwise, you
	might not.

GVC: Globally visible causality:  You are guarantee to see the
	ordering whether or not you are in the causal chain.

I could of course poll the memory-ordering academics and get more options.  ;-)

> >  - RELEASE -> ACQUIRE can be upgraded to a full barrier (including
> >    transitivity) using smp_mb__release_acquire(), either before RELEASE
> >    or after ACQUIRE (but consistently [*]).
> 
> Hmm, but we don't actually need this for RELEASE -> ACQUIRE, afaict. This
> is just needed for UNLOCK -> LOCK, and is exactly what RCU is currently
> using (for PPC only).

If by "don't actually need this" you mean "don't currently know of a
use case", I agree.  For now, anyway.  ;-)

> Stepping back a second, I believe that there are three cases:
> 
> 
>  RELEASE X -> ACQUIRE Y (same CPU)
>    * Needs a barrier on TSO architectures for full ordering

Agreed, assuming these restatements match your views:

Compiler barrier() for TSO for ordering to be visible within the causal chain.

Memory-barrier instruction for TSO for ordering to be visible globally.

>  UNLOCK X -> LOCK Y (same CPU)
>    * Needs a barrier on PPC for full ordering

Where "full ordering" is what I have been calling "globally visible
ordering" (or transitivity or causality or whatever), agreed.

>  RELEASE X -> ACQUIRE X (different CPUs)
>  UNLOCK X -> ACQUIRE X (different CPUs)
>    * Fully ordered everywhere...
>    * ... but needs a barrier on PPC to become a full barrier

Agreed, assuming these restatements match your views:

With compiler barrier (for TSO) or lwsync-capable memory-barrier instruction
(for weakly ordered systems), ordering is visible within the causal chain.

With compiler barrier (for TSO) or full memory-barrier instruction
(for weakly ordered systems), ordering is visible globally.

> so maybe it makes more sense to split out the local and inter-cpu ordering
> with something like:
> 
>   smp_mb__after_release_acquire()
>   smp_mb__after_release_acquire_local()
> 
> then the first one directly replaces smp_mb__after_unlock_lock, and is
> only defined for PPC, whereas the second one is also defined for TSO archs.

I don't see the need for the _local() variant.  We already have
smp_store_release() and smp_load_acquire(), both of which imply any
barriers needed for the case of locally visible causality.

> >  - RELEASE -> ACQUIRE _chains_ (on shared variables) preserve causality,
> >    (because each link is fully ordered) but are not transitive.
> 
> Yup, and that's the same for UNLOCK -> LOCK, too.

Any transitive ordering is visible only locally, within the chain.
For global visibility, you need smp_mb__after_release_acquire().

> > And I think that in the past few weeks we've been using transitive
> > ambiguously, the definition we have in Documentation/memory-barriers.txt
> > is a _strong_ transitivity, where we can make guarantees about CPUs not
> > directly involved.
> > 
> > What we have here (due to RCpc) is a weak form of transitivity, which,
> > while it preserves the natural concept of causality, does not extend to
> > other CPUs.
> > 
> > So we could go around and call them 'strong' and 'weak' transitivity,
> > but I suspect its easier for everyone involved if we come up with
> > separate terms (less room for error if we accidentally omit the
> > 'strong/weak' qualifier).
> 
> Surely the general case is message passing and so "transitivity" should
> just refer to chains of RELEASE -> ACQUIRE? Then "strong transitivity"
> could refer to the far more complicated (imo) case that is synonymous
> with "full barrier".

We should have fun agreeing on the best words to describe all this, but
agreed.

One nit:  RELEASE->ACQUIRE chains can do more than message passing.
Anything before the RELEASE, be it a load or a store, is visible to
anything after any ACQUIRE further down the chain.  Here a prior load is
"visible" to a subsequent store in the sense that the store cannot affect
the value loaded.  This is consistent with the C11/C++11 memory model.

Seem reasonable?

							Thanx, Paul

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | linux.kernel

csiph-web