LKML Archive on lore.kernel.org
 help / color / Atom feed
From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Michael Ellerman <mpe@ellerman.id.au>,
	Peter Zijlstra <peterz@infradead.org>,
	Alan Stern <stern@rowland.harvard.edu>,
	andrea.parri@amarulasolutions.com,
	Will Deacon <will.deacon@arm.com>,
	Akira Yokosawa <akiyks@gmail.com>,
	Boqun Feng <boqun.feng@gmail.com>,
	Daniel Lustig <dlustig@nvidia.com>,
	David Howells <dhowells@redhat.com>,
	Jade Alglave <j.alglave@ucl.ac.uk>,
	Luc Maranget <luc.maranget@inria.fr>,
	Nick Piggin <npiggin@gmail.com>,
	Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH v2] tools/memory-model: Add extra ordering for locks and remove it for ordinary release/acquire
Date: Tue, 17 Jul 2018 12:38:25 -0700
Message-ID: <20180717193825.GS12945@linux.vnet.ibm.com> (raw)
In-Reply-To: <CA+55aFwA=TmJJkKvskX3wL9Rs1j8xZJDJVghv=G0spYufK9kYg@mail.gmail.com>

On Tue, Jul 17, 2018 at 11:44:23AM -0700, Linus Torvalds wrote:
> On Tue, Jul 17, 2018 at 11:31 AM Paul E. McKenney
> <paulmck@linux.vnet.ibm.com> wrote:
> >
> > The isync provides ordering roughly similar to lwsync, but nowhere near
> > as strong as sync, and it is sync that would be needed to cause lock
> > acquisition to provide full ordering.
> 
> That's only true when looking at isync in isolation.
> 
> Read the part I quoted. The AIX documentation implies that the
> *sequence* of load-compare-conditional branch-isync is a memory
> barrier, even if isync on its own is now.

You are referring to this URL, correct?

https://www.ibm.com/developerworks/systems/articles/powerpc.html

If so, the "this ordering property" refers to the ordering needed to
ensure that the later accesses happen after the "load global flag",
and lwsync suffices for that.  (As does the branch-isync, as you say.)
The sync instruction provides much stronger ordering due to the fact
that sync flushes the store buffer and waits for acknowledgments from all
other CPUs (or, more accurately makes it appear as if it had done so --
speculative execution can be and is used to hide some of the latency).

In contrast, isync (with or without the load and branch) does not
flush the store buffer nor does it cause any particular communication
with the other CPUs.  The ordering that isync provides is therefore
quite a bit weaker than that of the sync instruction.

> So I'm just saying that
> 
>  (a) isync-on-lock is supposed to be much cheaper than sync-on-lock

Completely agreed.

>  (b) the AIX documentation at least implies that isync-on-lock (when
> used together the the whole locking sequence) is actually a memory
> barrier

Agreed, but the ordering properties that it provides are similar to
those of the weaker lwsync memory-barrier instruction, and nowhere near
as strong of those of the sync memory-barrier instruction.

> Now, admittedly the powerpc barrier instructions are unfathomable
> crazy stuff, so who knows. But:
> 
>  (a) lwsync is a memory barrier for all the "easy" cases (ie
> load->store, load->load, and store->load).

Yes.

>  (b) lwsync is *not* a memory barrier for the store->load case.

Agreed.

>  (c) isync *is* (when in that *sequence*) a memory barrier for a
> store->load case (and has to be: loads inside a spinlocked region MUST
> NOT be done earlier than stores outside of it!).

Yes, isync will wait for the prior stores to -execute-, but it doesn't
necessarily wait for the corresponding entries to leave the store buffer.
And this suffices to provide ordering from the viewpoint of some other
CPU holding the lock.

> So a unlock/lock sequence where the unlock is using lwsync, and the
> lock is using isync, should in fact be a full memory barrier (which is
> the semantics we're looking for).
> 
> So doing performance testing on sync/lwsync (for lock/unlock
> respectively) seems the wrong thing to do.  Please test the
> isync/lwsync case instead.
> 
> Hmm? What am I missing?

That the load-branch-isync has ordering properties similar to the lwsync
memory-barrier instruction, not to the sync memory-barrier instruction.
This means that the isync/lwsync case simply won't provide full ordering
from the viewpoint of CPUs not holding the lock.  (As with lwsync,
CPUs holding the lock do see full ordering, as is absolutely required.)

You absolutely must use sync/lwsync or lwsync/sync to get the strong
order that is visible to other CPUs not holding the lock.

The PowerPC hardware verification tools agree, as shown below.

							Thanx, Paul

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

The PPCMEM tools (which the Power hardware guys helped to develop) agrees.
For the following litmus test, in which P0 does the lwsync-unlock and
isync-lock, and for which P1 checks the ordering, but without acquiring
the lock, PPCMEM says "no ordering".

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

PPC lock-1thread-WR-barrier.litmus
""
{
l=1;
0:r1=1; 0:r3=42; 0:r4=x; 0:r5=y; 0:r10=0; 0:r11=0; 0:r12=l;
1:r1=1;          1:r4=x; 1:r5=y;
}
 P0                | P1           ;
 stw r1,0(r4)      | stw r1,0(r5) ;
 lwsync            | sync         ;
 stw r10,0(r12)    | lwz r7,0(r4) ;
 lwarx r11,r10,r12 |              ;
 cmpwi r11,0       |              ;
 bne Fail1         |              ;
 stwcx. r1,r10,r12 |              ;
 bne Fail1         |              ;
 isync             |              ;
 lwz r3,0(r5)      |              ;
 Fail1:            |              ;


exists
(0:r3=0 /\ 1:r7=0)

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

Here is the output of running the tool locally:

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

0:r3=0; 1:r7=0;
0:r3=0; 1:r7=1;
0:r3=1; 1:r7=0;
0:r3=1; 1:r7=1;
0:r3=42; 1:r7=0;
0:r3=42; 1:r7=1;
Ok
Condition exists (0:r3=0 /\ 1:r7=0)
Hash=16c3d58e658f6c16bc3df7d6233d8bf8
Observation SB+lock+sync-Linus Sometimes 1 5

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

And you can see the "0:r3=0; 1:r7=0;" state, which indicates that neither
process's loads saw the other process's stores, which in turn indicates
no ordering.

That said, if P1 actually acquired the lock, there would be ordering.

Or you can get the same result manually using this web site:

https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html


  parent reply index

Thread overview: 84+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-07-09 20:01 Alan Stern
2018-07-09 21:45 ` Paul E. McKenney
2018-07-10 13:57   ` Alan Stern
2018-07-10 16:25     ` Paul E. McKenney
     [not found]       ` <Pine.LNX.4.44L0.1807101416390.1449-100000@iolanthe.rowland.org>
2018-07-10 19:58         ` [PATCH v3] " Paul E. McKenney
2018-07-10 20:24           ` Alan Stern
2018-07-10 20:31             ` Paul E. McKenney
2018-07-11  9:43         ` Will Deacon
2018-07-11 15:42           ` Paul E. McKenney
2018-07-11 16:17             ` Andrea Parri
2018-07-11 18:03               ` Paul E. McKenney
2018-07-11 16:34           ` Peter Zijlstra
2018-07-11 18:10             ` Paul E. McKenney
2018-07-10  9:38 ` [PATCH v2] " Andrea Parri
2018-07-10 14:48   ` Alan Stern
2018-07-10 15:24     ` Andrea Parri
2018-07-10 15:34       ` Alan Stern
2018-07-10 23:14         ` Andrea Parri
2018-07-11  9:43   ` Will Deacon
2018-07-11 12:34     ` Andrea Parri
2018-07-11 12:54       ` Andrea Parri
2018-07-11 15:57       ` Will Deacon
2018-07-11 16:28         ` Andrea Parri
2018-07-11 17:00         ` Peter Zijlstra
2018-07-11 17:50           ` Daniel Lustig
2018-07-12  8:34             ` Andrea Parri
2018-07-12  9:29             ` Peter Zijlstra
2018-07-12  7:40       ` Peter Zijlstra
2018-07-12  9:34         ` Peter Zijlstra
2018-07-12  9:45           ` Will Deacon
2018-07-13  2:17             ` Daniel Lustig
2018-07-12 11:52         ` Andrea Parri
2018-07-12 12:01           ` Andrea Parri
2018-07-12 12:11             ` Peter Zijlstra
2018-07-12 13:48           ` Peter Zijlstra
2018-07-12 16:19             ` Paul E. McKenney
2018-07-12 17:04             ` Alan Stern
2018-07-12 17:14               ` Will Deacon
2018-07-12 17:28               ` Paul E. McKenney
2018-07-12 18:05                 ` Peter Zijlstra
2018-07-12 18:10                   ` Linus Torvalds
2018-07-12 19:52                     ` Andrea Parri
2018-07-12 20:24                       ` Andrea Parri
2018-07-13  2:05                     ` Daniel Lustig
2018-07-13  4:03                       ` Paul E. McKenney
2018-07-13  9:07                       ` Andrea Parri
2018-07-13  9:35                         ` Will Deacon
2018-07-13 17:16                           ` Linus Torvalds
2018-07-13 19:06                             ` Andrea Parri
2018-07-14  1:51                               ` Alan Stern
2018-07-14  2:58                                 ` Linus Torvalds
2018-07-16  2:31                                   ` Paul E. McKenney
2018-07-13 11:08                     ` Peter Zijlstra
2018-07-13 13:15                       ` Michael Ellerman
2018-07-13 16:42                         ` Peter Zijlstra
2018-07-13 19:56                           ` Andrea Parri
2018-07-16 14:40                           ` Michael Ellerman
2018-07-16 19:01                             ` Peter Zijlstra
2018-07-16 19:30                             ` Linus Torvalds
2018-07-17 14:45                               ` Michael Ellerman
2018-07-17 16:19                                 ` Linus Torvalds
2018-07-17 18:33                                   ` Paul E. McKenney
2018-07-17 18:42                                     ` Peter Zijlstra
2018-07-17 19:40                                       ` Paul E. McKenney
2018-07-17 19:47                                       ` Alan Stern
2018-07-17 18:44                                     ` Linus Torvalds
2018-07-17 18:49                                       ` Linus Torvalds
2018-07-17 19:42                                         ` Paul E. McKenney
2018-07-17 19:37                                       ` Alan Stern
2018-07-17 20:13                                         ` Linus Torvalds
2018-07-17 19:38                                       ` Paul E. McKenney [this message]
2018-07-17 19:40                                     ` Andrea Parri
2018-07-17 19:52                                       ` Paul E. McKenney
2018-07-18 12:31                                   ` Michael Ellerman
2018-07-18 13:16                             ` Michael Ellerman
2018-07-12 17:52               ` Andrea Parri
2018-07-12 20:43                 ` Alan Stern
2018-07-12 21:13                   ` Andrea Parri
2018-07-12 21:23                     ` Andrea Parri
2018-07-12 18:33               ` Peter Zijlstra
2018-07-12 17:45             ` Andrea Parri
2018-07-10 16:56 ` Daniel Lustig
     [not found]   ` <Pine.LNX.4.44L0.1807101315140.1449-100000@iolanthe.rowland.org>
2018-07-10 23:31     ` Andrea Parri
2018-07-11 14:19       ` Alan Stern

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=20180717193825.GS12945@linux.vnet.ibm.com \
    --to=paulmck@linux.vnet.ibm.com \
    --cc=akiyks@gmail.com \
    --cc=andrea.parri@amarulasolutions.com \
    --cc=boqun.feng@gmail.com \
    --cc=dhowells@redhat.com \
    --cc=dlustig@nvidia.com \
    --cc=j.alglave@ucl.ac.uk \
    --cc=linux-kernel@vger.kernel.org \
    --cc=luc.maranget@inria.fr \
    --cc=mpe@ellerman.id.au \
    --cc=npiggin@gmail.com \
    --cc=peterz@infradead.org \
    --cc=stern@rowland.harvard.edu \
    --cc=torvalds@linux-foundation.org \
    --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

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lore.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lore.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lore.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lore.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lore.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lore.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lore.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lore.kernel.org/lkml/8 lkml/git/8.git
	git clone --mirror https://lore.kernel.org/lkml/9 lkml/git/9.git
	git clone --mirror https://lore.kernel.org/lkml/10 lkml/git/10.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lore.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git