From: Alan Stern <stern@rowland.harvard.edu>
To: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
Cc: Daniel Lustig <dlustig@nvidia.com>,
Will Deacon <will.deacon@arm.com>,
Andrea Parri <andrea.parri@amarulasolutions.com>,
Andrea Parri <parri.andrea@gmail.com>,
Kernel development list <linux-kernel@vger.kernel.org>,
<linux-arch@vger.kernel.org>, <mingo@kernel.org>,
<peterz@infradead.org>, <boqun.feng@gmail.com>,
<npiggin@gmail.com>, <dhowells@redhat.com>,
Jade Alglave <j.alglave@ucl.ac.uk>,
Luc Maranget <luc.maranget@inria.fr>, <akiyks@gmail.com>,
Palmer Dabbelt <palmer@sifive.com>
Subject: Re: [PATCH RFC LKMM 1/7] tools/memory-model: Add extra ordering for locks and remove it for ordinary release/acquire
Date: Thu, 13 Sep 2018 13:07:39 -0400 (EDT) [thread overview]
Message-ID: <Pine.LNX.4.44L0.1809131300370.1382-100000@iolanthe.rowland.org> (raw)
In-Reply-To: <20180911200328.GA4225@linux.vnet.ibm.com>
Not having received any responses to the question about usages of RCtso
locks, I have decided to post the newly updated version of the patch
description for commit c8c5779c854f ("tools/memory-model: Add extra
ordering for locks and remove it for ordinary release/acquire") in
Paul's LKMM branch. There are no changes to the patch itself.
Hopefully this includes all the important issues that people have
raised. (Admittedly, some parts of the discussion have seemed less
consequential than others, and some parts I didn't understand at all.)
Alan
-----------------------------------------------------------------------------
More than one kernel developer has expressed the opinion that the LKMM
should enforce ordering of writes by locking. In other words, given
the following code:
WRITE_ONCE(x, 1);
spin_unlock(&s):
spin_lock(&s);
WRITE_ONCE(y, 1);
the stores to x and y should be propagated in order to all other CPUs,
even though those other CPUs might not access the lock s. In terms of
the memory model, this means expanding the cumul-fence relation.
Locks should also provide read-read (and read-write) ordering in a
similar way. Given:
READ_ONCE(x);
spin_unlock(&s);
spin_lock(&s);
READ_ONCE(y); // or WRITE_ONCE(y, 1);
the load of x should be executed before the load of (or store to) y.
The LKMM already provides this ordering, but it provides it even in
the case where the two accesses are separated by a release/acquire
pair of fences rather than unlock/lock. This would prevent
architectures from using weakly ordered implementations of release and
acquire, which seems like an unnecessary restriction. The patch
therefore removes the ordering requirement from the LKMM for that
case.
There are several arguments both for and against this change. Let us
refer to these enhanced ordering properties by saying that the LKMM
would require locks to be RCtso (a bit of a misnomer, but analogous to
RCpc and RCsc) and it would require ordinary acquire/release only to
be RCpc. (Note: In the following, the phrase "all supported
architectures" does not include RISC-V, which is still somewhat in
a state of flux.)
Pros:
The kernel already provides RCtso ordering for locks on all
supported architectures, even though this is not stated
explicitly anywhere. Therefore the LKMM should formalize it.
In theory, guaranteeing RCtso ordering would reduce the need
for additional barrier-like constructs meant to increase the
ordering strength of locks.
Will Deacon and Peter Zijlstra are strongly in favor of
formalizing the RCtso requirement. Linus Torvalds and Will
would like to go even further, requiring locks to have RCsc
behavior (ordering preceding writes against later reads), but
they recognize that this would incur a noticeable performance
degradation on the POWER architecture. Linus also points out
that people have made the mistake, in the past, of assuming
that locking has stronger ordering properties than is
currently guaranteed, and this change would reduce the
likelihood of such mistakes.
Cons:
Andrea Parri and Luc Maranget feel that locks should have the
same ordering properties as ordinary acquire/release (indeed,
Luc points out that the names "acquire" and "release" derive
from the usage of locks) and that having different ordering
properties for different forms of acquires and releases would
be confusing and unmaintainable. Will and Linus, on the other
hand, feel that architectures should be free to implement
ordinary acquire/release using relatively weak RCpc machine
instructions. Linus points out that locks should be easy for
people to use without worrying about memory consistency
issues, since they are so pervasive in the kernel, whereas
acquire/release is much more of an "expertss only" tool.
Locks are constructed from lower-level primitives, typically
RMW-acquire (for locking) and ordinary release (for unlock).
It is illogical to require stronger ordering properties from
the high-level operations than from the low-level operations
they comprise. Thus, this change would make
while (cmpxchg_acquire(&s, 0, 1) != 0)
cpu_relax();
an incorrect implementation of spin_lock(&s). In theory this
weakness can be ameliorated by changing the LKMM even further,
requiring RMW-acquire/release also to be RCtso (which it
already is on all supported architectures).
As far as I know, nobody has singled out any examples of code
in the kernel that actually relies on locks being RCtso.
(People mumble about RCU and the scheduler, but nobody has
pointed to any actual code. If there are any real cases,
their number is likely quite small.) If RCtso ordering is not
needed, why require it?
A handful of locking constructs (qspinlocks, qrwlocks, and
mcs_spinlocks) are built on top of smp_cond_load_acquire()
instead of an RMW-acquire instruction. It currently provides
only the ordinary acquire semantics, not the stronger ordering
this patch would require of locks. In theory this could be
ameliorated by requiring smp_cond_load_acquire() in
combination with ordinary release also to be RCtso (which is
currently true in all supported architectures).
On future weakly ordered architectures, people may be able to
implement locks in a non-RCtso fashion with significant
performance improvement. Meeting the RCtso requirement would
necessarily add run-time overhead.
Overall, the technical aspects of these arguments seem relatively
minor, and it appears mostly to boil down to a matter of opinion.
Since the opinions of long-time kernel developers such as Linus,
Peter, and Will carry more weight than those of Luc and Andrea, this
patch changes the model in accordance with the developers' wishes.
Signed-off-by: Alan Stern <stern@rowland.harvard.edu>
---
v.4: Added pros and cons discussion to the Changelog.
v.3: Rebased against the dev branch of Paul's linux-rcu tree.
Changed unlock-rf-lock-po to po-unlock-rf-lock-po, making it more
symmetrical and more in accordance with the use of fence.tso for
the release on RISC-V.
v.2: Restrict the ordering to lock operations, not general release
and acquire fences.
next prev parent reply other threads:[~2018-09-13 17:35 UTC|newest]
Thread overview: 56+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-08-29 21:10 [PATCH RFC memory-model 0/7] Memory-model changes Paul E. McKenney
2018-08-29 21:10 ` [PATCH RFC LKMM 1/7] tools/memory-model: Add extra ordering for locks and remove it for ordinary release/acquire Paul E. McKenney
2018-08-30 12:50 ` Andrea Parri
2018-08-30 21:31 ` Alan Stern
2018-08-31 9:17 ` Andrea Parri
2018-08-31 14:52 ` Alan Stern
2018-08-31 16:06 ` Will Deacon
2018-08-31 18:28 ` Andrea Parri
2018-09-03 9:01 ` Andrea Parri
2018-09-03 17:04 ` Will Deacon
2018-09-04 8:11 ` Andrea Parri
2018-09-04 19:09 ` Alan Stern
2018-09-05 7:21 ` Andrea Parri
2018-09-05 14:33 ` Akira Yokosawa
2018-09-05 14:53 ` Paul E. McKenney
2018-09-05 15:00 ` Andrea Parri
2018-09-05 15:04 ` Akira Yokosawa
2018-09-05 15:24 ` Andrea Parri
2018-09-03 17:52 ` Alan Stern
2018-09-03 18:28 ` Andrea Parri
2018-09-06 1:25 ` Alan Stern
2018-09-06 9:36 ` Andrea Parri
2018-09-07 16:00 ` Alan Stern
2018-09-07 16:09 ` Will Deacon
2018-09-07 16:39 ` Daniel Lustig
2018-09-07 17:38 ` Alan Stern
2018-09-08 0:04 ` Daniel Lustig
2018-09-08 9:58 ` Andrea Parri
2018-09-11 19:31 ` Alan Stern
2018-09-11 20:03 ` Paul E. McKenney
2018-09-12 14:24 ` Alan Stern
2018-09-13 17:07 ` Alan Stern [this message]
2018-09-14 14:37 ` Andrea Parri
2018-09-14 16:29 ` Alan Stern
2018-09-14 19:44 ` Andrea Parri
2018-09-14 21:08 ` [PATCH v5] " Alan Stern
2018-09-15 3:56 ` Paul E. McKenney
2018-09-03 17:05 ` [PATCH RFC LKMM 1/7] " Will Deacon
2018-08-31 17:55 ` Andrea Parri
2018-08-29 21:10 ` [PATCH RFC LKMM 2/7] doc: Replace smp_cond_acquire() with smp_cond_load_acquire() Paul E. McKenney
2018-09-14 16:59 ` Will Deacon
2018-09-14 18:20 ` Paul E. McKenney
2018-08-29 21:10 ` [PATCH RFC LKMM 3/7] EXP tools/memory-model: Add more LKMM limitations Paul E. McKenney
2018-08-30 9:17 ` Andrea Parri
2018-08-30 22:18 ` Paul E. McKenney
2018-08-31 9:43 ` Andrea Parri
2018-09-06 18:34 ` Paul E. McKenney
2018-08-29 21:10 ` [PATCH RFC LKMM 4/7] tools/memory-model: Fix a README typo Paul E. McKenney
2018-08-29 21:10 ` [PATCH RFC LKMM 5/7] EXP tools/memory-model: Add scripts to check github litmus tests Paul E. McKenney
2018-08-29 21:10 ` [PATCH RFC LKMM 6/7] EXP tools/memory-model: Make scripts take "-j" abbreviation for "--jobs" Paul E. McKenney
2018-08-29 21:10 ` [PATCH RFC LKMM 7/7] EXP tools/memory-model: Add .cfg and .cat files for s390 Paul E. McKenney
2018-08-31 16:06 ` Will Deacon
2018-09-01 17:08 ` Paul E. McKenney
2018-09-14 16:36 ` [PATCH RFC memory-model 0/7] Memory-model changes Paul E. McKenney
2018-09-14 17:19 ` Alan Stern
2018-09-14 18:29 ` 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=Pine.LNX.4.44L0.1809131300370.1382-100000@iolanthe.rowland.org \
--to=stern@rowland.harvard.edu \
--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-arch@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=luc.maranget@inria.fr \
--cc=mingo@kernel.org \
--cc=npiggin@gmail.com \
--cc=palmer@sifive.com \
--cc=parri.andrea@gmail.com \
--cc=paulmck@linux.vnet.ibm.com \
--cc=peterz@infradead.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
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).