From: "Paul E. McKenney" <paulmck@linux.ibm.com>
To: Alan Stern <stern@rowland.harvard.edu>
Cc: David Goldblatt <davidtgoldblatt@gmail.com>,
mathieu.desnoyers@efficios.com,
Florian Weimer <fweimer@redhat.com>,
triegel@redhat.com, libc-alpha@sourceware.org,
andrea.parri@amarulasolutions.com, will.deacon@arm.com,
peterz@infradead.org, boqun.feng@gmail.com, npiggin@gmail.com,
dhowells@redhat.com, j.alglave@ucl.ac.uk, luc.maranget@inria.fr,
akiyks@gmail.com, dlustig@nvidia.com, linux-arch@vger.kernel.org,
linux-kernel@vger.kernel.org
Subject: Re: [PATCH] Linux: Implement membarrier function
Date: Wed, 12 Dec 2018 09:07:06 -0800 [thread overview]
Message-ID: <20181212170706.GA17397@linux.ibm.com> (raw)
In-Reply-To: <20181211212204.GR4170@linux.ibm.com>
On Tue, Dec 11, 2018 at 01:22:04PM -0800, Paul E. McKenney wrote:
> On Tue, Dec 11, 2018 at 03:09:33PM -0500, Alan Stern wrote:
> > On Tue, 11 Dec 2018, Paul E. McKenney wrote:
> >
> > > > Rewriting the litmus test in these terms gives:
> > > >
> > > > P0 P1 P2 P3 P4 P5
> > > > Wa=2 Wb=2 Wc=2 [mb23] [mb14] [mb05]
> > > > mb0s mb1s mb2s Wd=2 We=2 Wf=2
> > > > mb0e mb1e mb2e Re=0 Rf=0 Ra=0
> > > > Rb=0 Rc=0 Rd=0
> > > >
> > > > Here the brackets in "[mb23]", "[mb14]", and "[mb05]" mean that the
> > > > positions of these barriers in their respective threads' program
> > > > orderings is undetermined; they need not come at the top as shown.
> > > >
> > > > (Also, in case David is unfamiliar with it, the "Wa=2" notation is
> > > > shorthand for "Write 2 to a" and "Rb=0" is short for "Read 0 from b".)
> > > >
> > > > Finally, here are a few facts which may be well known and obvious, but
> > > > I'll state them anyway:
> > > >
> > > > A CPU cannot reorder instructions across a memory barrier.
> > > > If x is po-after a barrier then x executes after the barrier
> > > > is finished.
> > > >
> > > > If a store is po-before a barrier then the store propagates
> > > > to every CPU before the barrier finishes.
> > > >
> > > > If a store propagates to some CPU before a load on that CPU
> > > > reads from the same location, then the load will obtain the
> > > > value from that store or a co-later store. This implies that
> > > > if a load obtains a value co-earlier than some store then the
> > > > load must have executed before the store propagated to the
> > > > load's CPU.
> > > >
> > > > The proof consists of three main stages, each requiring three steps.
> > > > Using the facts that b - f are all read as 0, I'll show that P1
> > > > executes Rc before P3 executes Re, then that P0 executes Rb before P4
> > > > executes Rf, and lastly that P5's Ra must obtain 2, not 0. This will
> > > > demonstrate that the litmus test is not allowed.
> > > >
> > > > 1. Suppose that mb23 ends up coming po-later than Wd in P3.
> > > > Then we would have:
> > > >
> > > > Wd propagates to P2 < mb23 < mb2e < Rd,
> > > >
> > > > and so Rd would obtain 2, not 0. Hence mb23 must come
> > > > po-before Wd (as shown in the listing): mb23 < Wd.
> > > >
> > > > 2. Since mb23 therefore occurs po-before Re and instructions
> > > > cannot be reordered across barriers, mb23 < Re.
> > > >
> > > > 3. Since Rc obtains 0, we must have:
> > > >
> > > > Rc < Wc propagates to P1 < mb2s < mb23 < Re.
> > > >
> > > > Thus Rc < Re.
> > > >
> > > > 4. Suppose that mb14 ends up coming po-later than We in P4.
> > > > Then we would have:
> > > >
> > > > We propagates to P3 < mb14 < mb1e < Rc < Re,
> > > >
> > > > and so Re would obtain 2, not 0. Hence mb14 must come
> > > > po-before We (as shown in the listing): mb14 < We.
> > > >
> > > > 5. Since mb14 therefore occurs po-before Rf and instructions
> > > > cannot be reordered across barriers, mb14 < Rf.
> > > >
> > > > 6. Since Rb obtains 0, we must have:
> > > >
> > > > Rb < Wb propagates to P0 < mb1s < mb14 < Rf.
> > > >
> > > > Thus Rb < Rf.
> > > >
> > > > 7. Suppose that mb05 ends up coming po-later than Wf in P5.
> > > > Then we would have:
> > > >
> > > > Wf propagates to P4 < mb05 < mb0e < Rb < Rf,
> > > >
> > > > and so Rf would obtain 2, not 0. Hence mb05 must come
> > > > po-before Wf (as shown in the listing): mb05 < Wf.
> > > >
> > > > 8. Since mb05 therefore occurs po-before Ra and instructions
> > > > cannot be reordered across barriers, mb05 < Ra.
> > > >
> > > > 9. Now we have:
> > > >
> > > > Wa propagates to P5 < mb0s < mb05 < Ra,
> > > >
> > > > and so Ra must obtain 2, not 0. QED.
> > >
> > > Like this, then, with maximal reordering of P3-P5's reads?
> > >
> > > P0 P1 P2 P3 P4 P5
> > > Wa=2
> > > mb0s
> > > [mb05]
> > > mb0e Ra=0
> > > Rb=0 Wb=2
> > > mb1s
> > > [mb14]
> > > mb1e Rf=0
> > > Rc=0 Wc=2 Wf=2
> > > mb2s
> > > [mb23]
> > > mb2e Re=0
> > > Rd=0 We=2
> > > Wd=2
> >
> > Yes, that's right. This shows how P5's Ra must obtain 2 instead of 0.
> >
> > > But don't the sys_membarrier() calls affect everyone, especially given
> > > the shared-variable communication?
> >
> > They do, but the other effects are irrelevant for this proof.
>
> If I understand correctly, the shared-variable communication within
> sys_membarrier() is included in your proof in the form of ordering
> between memory barriers in the mainline sys_membarrier() code and
> in the IPI handlers.
>
> > > If so, why wouldn't this more strict
> > > variant hold?
> > >
> > > P0 P1 P2 P3 P4 P5
> > > Wa=2
> > > mb0s
> > > [mb05] [mb05] [mb05]
> >
> > You have misunderstood the naming scheme. mb05 is the barrier injected
> > by P0's sys_membarrier call into P5. So the three barriers above
> > should be named "mb03", "mb04", and "mb05". And you left out mb01 and
> > mb02.
>
> The former is a copy-and-paste error on my part, the latter was
> intentional because the IPIs among P0, P1, and P2 don't seem to
> strengthen the ordering.
>
> > > mb0e
> > > Rb=0 Wb=2
> > > mb1s
> > > [mb14] [mb14] [mb14]
> > > mb1e
> > > Rc=0 Wc=2
> > > mb2s
> > > [mb23] [mb23] [mb23]
> > > mb2e Re=0 Rf=0 Ra=0
> > > Rd=0 We=2 Wf=2
> > > Wd=2
> >
> > Yes, this does hold. But since it doesn't affect the end result,
> > there's no point in mentioning all those other barriers.
> >
> > > In which case, wouldn't this cycle be forbidden even if it had only one
> > > sys_membarrier() call?
> >
> > No, it wouldn't. I don't understand why you might think it would.
>
> Because I hadn't yet thought of the scenario I showed below.
>
> > This is just like RCU, if you imagine a tiny critical section between
> > each adjacent pair of instructions. You wouldn't expect RCU to enforce
> > ordering among six CPUs with only one synchronize_rcu call.
>
> Yes, I do now agree in light of the scenario shown below.
>
> > > Ah, but the IPIs are not necessarily synchronized across the CPUs,
> > > so that the following could happen:
> > >
> > > P0 P1 P2 P3 P4 P5
> > > Wa=2
> > > mb0s
> > > [mb05] [mb05] [mb05]
> > > mb0e Ra=0
> > > Rb=0 Wb=2
> > > mb1s
> > > [mb14] [mb14]
> > > Rf=0
> > > Wf=2
> > > [mb14]
> > > mb1e
> > > Rc=0 Wc=2
> > > mb2s
> > > [mb23]
> > > Re=0
> > > We=2
> > > [mb23] [mb23]
> > > mb2e
> > > Rd=0
> > > Wd=2
> >
> > Yes it could. But even in this execution you would end up with Ra=2
> > instead of Ra=0.
>
> Agreed. Or I should have said that the above execution is forbidden,
> either way.
>
> > > I guess in light of this post in 2001, I really don't have an excuse,
> > > do I? ;-)
> > >
> > > https://lists.gt.net/linux/kernel/223555
> > >
> > > Or am I still missing something here?
> >
> > You tell me...
>
> I think I am on board. ;-)
And more to the point, here is a three-process variant showing a cycle
that is permitted:
P0 P1 P2
Wa=2 Wb=2 Wc=2
mb0s
[mb01] [mb02]
mb0e
Rb=0 Rc=0 Ra=0
As can be seen by reordering it as follows:
P0 P1 P2
Ra=0
Wa=2
mb0s
[mb01]
Rc=0
Wc=2
[mb02]
mb0e
Rb=0
Wb=2
Make sense?
Thanx, Paul
next prev parent reply other threads:[~2018-12-12 17:07 UTC|newest]
Thread overview: 27+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <8736rldyzm.fsf@oldenburg.str.redhat.com>
[not found] ` <1543444466.5493.220.camel@redhat.com>
[not found] ` <87y39c2dsg.fsf@oldenburg.str.redhat.com>
[not found] ` <1689938209.14804.1543502662882.JavaMail.zimbra@efficios.com>
[not found] ` <20181129150433.GH4170@linux.ibm.com>
[not found] ` <CAHD6eXcvx1bskbp-X+vuMYoMQiCLOt0PiCZ5FT1yFsda9Ud-yA@mail.gmail.com>
2018-12-06 21:54 ` [PATCH] Linux: Implement membarrier function Paul E. McKenney
2018-12-10 16:22 ` Alan Stern
2018-12-10 18:25 ` Paul E. McKenney
2018-12-11 16:21 ` Alan Stern
2018-12-11 19:08 ` Paul E. McKenney
2018-12-11 20:09 ` Alan Stern
2018-12-11 21:22 ` Paul E. McKenney
2018-12-12 17:07 ` Paul E. McKenney [this message]
2018-12-12 18:04 ` Alan Stern
2018-12-12 19:42 ` Paul E. McKenney
2018-12-12 21:32 ` Alan Stern
2018-12-12 21:52 ` Paul E. McKenney
2018-12-12 22:12 ` Alan Stern
2018-12-12 22:49 ` Paul E. McKenney
2018-12-13 15:49 ` Alan Stern
2018-12-14 0:20 ` Paul E. McKenney
2018-12-14 2:26 ` Alan Stern
2018-12-14 5:20 ` Paul E. McKenney
2018-12-14 15:31 ` Alan Stern
2018-12-14 18:43 ` Paul E. McKenney
2018-12-14 21:39 ` Alan Stern
2018-12-16 18:51 ` Paul E. McKenney
2018-12-17 16:02 ` Alan Stern
2018-12-17 18:32 ` Paul E. McKenney
2018-12-12 22:19 ` Paul E. McKenney
2018-12-11 6:42 ` David Goldblatt
2018-12-11 14:49 ` Paul E. McKenney
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20181212170706.GA17397@linux.ibm.com \
--to=paulmck@linux.ibm.com \
--cc=akiyks@gmail.com \
--cc=andrea.parri@amarulasolutions.com \
--cc=boqun.feng@gmail.com \
--cc=davidtgoldblatt@gmail.com \
--cc=dhowells@redhat.com \
--cc=dlustig@nvidia.com \
--cc=fweimer@redhat.com \
--cc=j.alglave@ucl.ac.uk \
--cc=libc-alpha@sourceware.org \
--cc=linux-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=luc.maranget@inria.fr \
--cc=mathieu.desnoyers@efficios.com \
--cc=npiggin@gmail.com \
--cc=peterz@infradead.org \
--cc=stern@rowland.harvard.edu \
--cc=triegel@redhat.com \
--cc=will.deacon@arm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).