From: Jonas Oberhauser <jonas.oberhauser@huaweicloud.com>
To: paulmck@kernel.org, Alan Stern <stern@rowland.harvard.edu>
Cc: Andrea Parri <parri.andrea@gmail.com>,
Jonas Oberhauser <jonas.oberhauser@huawei.com>,
Peter Zijlstra <peterz@infradead.org>, will <will@kernel.org>,
"boqun.feng" <boqun.feng@gmail.com>, npiggin <npiggin@gmail.com>,
dhowells <dhowells@redhat.com>, "j.alglave" <j.alglave@ucl.ac.uk>,
"luc.maranget" <luc.maranget@inria.fr>, akiyks <akiyks@gmail.com>,
dlustig <dlustig@nvidia.com>, joel <joel@joelfernandes.org>,
urezki <urezki@gmail.com>,
quic_neeraju <quic_neeraju@quicinc.com>,
frederic <frederic@kernel.org>,
Kernel development list <linux-kernel@vger.kernel.org>
Subject: Re: Internal vs. external barriers (was: Re: Interesting LKMM litmus test)
Date: Wed, 25 Jan 2023 18:42:52 +0100 [thread overview]
Message-ID: <404dd9fd-f735-e844-e439-ea8594f98388@huaweicloud.com> (raw)
In-Reply-To: <20230125171832.GH2948950@paulmck-ThinkPad-P17-Gen-1>
On 1/25/2023 6:18 PM, Paul E. McKenney wrote:
> On Wed, Jan 25, 2023 at 10:34:40AM -0500, Alan Stern wrote:
>> On Wed, Jan 25, 2023 at 07:05:20AM -0800, Paul E. McKenney wrote:
>>> On Wed, Jan 25, 2023 at 02:10:08PM +0100, Jonas Oberhauser wrote:
>>>>
>>>> On 1/25/2023 3:20 AM, Paul E. McKenney wrote:
>>>>> On Tue, Jan 24, 2023 at 08:54:56PM -0500, Alan Stern wrote:
>>>>>> On Tue, Jan 24, 2023 at 02:54:49PM -0800, Paul E. McKenney wrote:
>>>>>>> Within the Linux kernel, the rule for a given RCU "domain" is that if
>>>>>>> an event follows a grace period in pretty much any sense of the word,
>>>>>>> then that event sees the effects of all events in all read-side critical
>>>>>>> sections that began prior to the start of that grace period.
>>>>>>>
>>>>>>> Here the senses of the word "follow" include combinations of rf, fr,
>>>>>>> and co, combined with the various acyclic and irreflexive relations
>>>>>>> defined in LKMM.
>>>>>> The LKMM says pretty much the same thing. In fact, it says the event
>>>>>> sees the effects of all events po-before the unlock of (not just inside)
>>>>>> any read-side critical section that began prior to the start of the
>>>>>> grace period.
>>>>>>
>>>>>>>> And are these anything the memory model needs to worry about?
>>>>>>> Given that several people, yourself included, are starting to use LKMM
>>>>>>> to analyze the Linux-kernel RCU implementations, maybe it does.
>>>>>>>
>>>>>>> Me, I am happy either way.
>>>>>> Judging from your description, I don't think we have anything to worry
>>>>>> about.
>>>>> Sounds good, and let's proceed on that assumption then. We can always
>>>>> revisit later if need be.
>>>>>
>>>>> Thanx, Paul
>>>> FWIW, I currently don't see a need for either RCU nor "base" LKMM to have
>>>> this kind of guarantee.
>>> In the RCU case, it is because it is far easier to provide this guarantee,
>>> even though it is based on hardware and compilers rather than LKMM,
>>> than it would be to explain to some random person why the access that
>>> is intuitively clearly after the grace period can somehow come before it.
>>>
>>>> But I'm curious for why it doesn't exist in LKMM -- is it because of Alpha
>>>> or some other issues that make it hard to guarantee (like a compiler merging
>>>> two threads and optimizing or something?), or is it simply that it seemed
>>>> like a complicated guarantee with no discernible upside, or something else?
>>> Because to the best of my knowledge, no one has ever come up with a
>>> use for 2+2W and friends that isn't better handled by some much more
>>> straightforward pattern of accesses. So we did not guarantee it in LKMM.
>>>
>>> Yes, you could argue that my "ease of explanation" paragraph above is
>>> a valid use case, but I am not sure that this is all that compelling of
>>> an argument. ;-)
>> Are we all talking about the same thing? There were two different
>> guarantees mentioned above:
>>
>> The RCU guarantee about writes in a read-side critical section
>> becoming visible to all CPUs before a later grace period ends;
>>
>> The guarantee about the 2+2W pattern and friends being
>> forbidden.
>>
>> The LKMM includes the first of these but not the second (for the reason
>> Paul stated).
> I am not sure whether or not we are talking about the same thing,
> but given this litmus test:
>
> ------------------------------------------------------------------------
>
> C C-srcu-observed-4
>
> (*
> * Result: Sometimes
> *
> * The Linux-kernel implementation is suspected to forbid this.
> *)
>
> {}
>
> P0(int *x, int *y, int *z, struct srcu_struct *s)
> {
> int r1;
>
> r1 = srcu_read_lock(s);
> WRITE_ONCE(*y, 2);
> WRITE_ONCE(*x, 1);
> srcu_read_unlock(s, r1);
> }
>
> P1(int *x, int *y, int *z, struct srcu_struct *s)
> {
> int r1;
>
> WRITE_ONCE(*y, 1);
> synchronize_srcu(s);
> WRITE_ONCE(*z, 2);
> }
>
> P2(int *x, int *y, int *z, struct srcu_struct *s)
> {
> WRITE_ONCE(*z, 1);
> smp_store_release(x, 2);
> }
>
> exists (x=1 /\ y=1 /\ z=1)
>
> ------------------------------------------------------------------------
>
> We get the following from herd7:
>
> ------------------------------------------------------------------------
>
> $ herd7 -conf linux-kernel.cfg C-srcu-observed-4.litmus
> Test C-srcu-observed-4 Allowed
> States 8
> x=1; y=1; z=1;
> x=1; y=1; z=2;
> x=1; y=2; z=1;
> x=1; y=2; z=2;
> x=2; y=1; z=1;
> x=2; y=1; z=2;
> x=2; y=2; z=1;
> x=2; y=2; z=2;
> Ok
> Witnesses
> Positive: 1 Negative: 7
> Condition exists (x=1 /\ y=1 /\ z=1)
> Observation C-srcu-observed-4 Sometimes 1 7
> Time C-srcu-observed-4 0.02
> Hash=8b6020369b73ac19070864a9db00bbf8
>
> ------------------------------------------------------------------------
>
> This does not seem to me to be consistent with your "The RCU guarantee
> about writes in a read-side critical section becoming visible to all
> CPUs before a later grace period ends".
I believe the issue is a different one, it's about the prop;prop at the
end, not related to the grace period guarantee. The stores in the CS
become visible, but the store release never propagates anywhere, since
the co-later store from the CS already propagated everywhere.
I believe this is because A ->prop B ->prop C only says that there are
writes WB and WC such that WB propagates to B's CPU before B executes,
WC is co-after B, and WC propagates to C's CPU before C executes. (I
think B is the release store here).
But it does not say anything about the propagation/execution order of B
and WC, and I believe WC can propagate to every CPU (other than B's)
before B, and B never propagates anywhere.
> Again, I am OK with LKMM allowing C-srcu-observed-4.litmus, as long as
> the actual Linux-kernel implementation forbids it.
Is it really that important that the implementation forbids it? Do you
have a use case?
Best wishes, jonas
next prev parent reply other threads:[~2023-01-25 17:43 UTC|newest]
Thread overview: 161+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20220921173109.GA1214281@paulmck-ThinkPad-P17-Gen-1>
[not found] ` <YytfFiMT2Xsdwowf@rowland.harvard.edu>
[not found] ` <YywXuzZ/922LHfjI@hirez.programming.kicks-ass.net>
[not found] ` <114ECED5-FED1-4361-94F7-8D9BC02449B7>
[not found] ` <YzSAnclenTz7KQyt@rowland.harvard.edu>
[not found] ` <f763bd5ff835458d8750b61da47fe316@huawei.com>
2023-01-03 18:56 ` Internal vs. external barriers (was: Re: Interesting LKMM litmus test) Alan Stern
2023-01-04 15:37 ` Andrea Parri
2023-01-04 20:58 ` Alan Stern
[not found] ` <ee186bc17a5e48298a5373f688496dce@huawei.com>
2023-01-05 17:32 ` Paul E. McKenney
[not found] ` <bea712c82e6346f8973399a5711ff78a@huawei.com>
2023-01-11 15:06 ` Alan Stern
[not found] ` <768ffe7edc7f4ddfacd5b0a8e844ed84@huawei.com>
2023-01-11 17:01 ` Alan Stern
[not found] ` <07579baee4b84532a76ea8b0b33052bb@huawei.com>
2023-01-12 21:57 ` Paul E. McKenney
2023-01-13 16:38 ` Alan Stern
2023-01-13 19:54 ` Paul E. McKenney
[not found] ` <06a8aef7eb8d46bca34521a80880dae3@huawei.com>
2023-01-14 17:42 ` Paul E. McKenney
[not found] ` <e51c82a113484b6bb62354a49376f248@huawei.com>
2023-01-14 16:42 ` Alan Stern
2023-01-17 17:48 ` Jonas Oberhauser
2023-01-17 21:19 ` Alan Stern
2023-01-18 11:25 ` Jonas Oberhauser
2023-01-19 2:28 ` Alan Stern
2023-01-19 11:22 ` Jonas Oberhauser
2023-01-19 16:41 ` Alan Stern
2023-01-19 18:43 ` Paul E. McKenney
2023-01-23 16:16 ` Jonas Oberhauser
2023-01-23 19:58 ` Alan Stern
2023-01-23 20:06 ` Jonas Oberhauser
2023-01-23 20:41 ` Alan Stern
2023-01-24 13:21 ` Jonas Oberhauser
2023-01-24 15:54 ` Jonas Oberhauser
2023-01-24 17:22 ` Alan Stern
[not found] ` <4c1abc7733794519ad7c5153ae8b58f9@huawei.com>
2023-01-13 16:28 ` Alan Stern
2023-01-13 20:07 ` Paul E. McKenney
2023-01-13 20:32 ` Paul E. McKenney
2023-01-14 17:40 ` Alan Stern
2023-01-14 17:48 ` Paul E. McKenney
[not found] ` <136d019d8c8049f6b737627df830e66f@huawei.com>
2023-01-14 17:53 ` Paul E. McKenney
2023-01-14 18:15 ` Paul E. McKenney
2023-01-14 19:58 ` Alan Stern
2023-01-15 5:19 ` Paul E. McKenney
2023-01-14 20:19 ` Alan Stern
2023-01-15 5:15 ` Paul E. McKenney
2023-01-15 16:23 ` Alan Stern
2023-01-15 18:10 ` Paul E. McKenney
2023-01-15 20:46 ` Alan Stern
2023-01-16 4:23 ` Paul E. McKenney
2023-01-16 18:11 ` Alan Stern
2023-01-16 19:06 ` Paul E. McKenney
2023-01-16 19:20 ` Alan Stern
2023-01-16 22:13 ` Paul E. McKenney
2023-01-17 11:46 ` Andrea Parri
2023-01-17 15:14 ` Paul E. McKenney
2023-01-17 15:56 ` Alan Stern
2023-01-17 17:43 ` Paul E. McKenney
2023-01-17 18:27 ` Jonas Oberhauser
2023-01-17 18:55 ` Paul E. McKenney
2023-01-17 20:20 ` Jonas Oberhauser
2023-01-17 20:15 ` Alan Stern
2023-01-18 3:50 ` Paul E. McKenney
2023-01-18 16:50 ` Alan Stern
2023-01-18 19:42 ` Jonas Oberhauser
2023-01-18 20:19 ` Paul E. McKenney
2023-01-18 20:30 ` Jonas Oberhauser
2023-01-18 21:12 ` Paul E. McKenney
2023-01-18 21:24 ` Jonas Oberhauser
2023-01-19 0:11 ` Paul E. McKenney
2023-01-19 13:39 ` Jonas Oberhauser
2023-01-19 18:41 ` Paul E. McKenney
2023-01-19 19:51 ` Alan Stern
2023-01-19 21:53 ` Paul E. McKenney
2023-01-19 22:04 ` Alan Stern
2023-01-19 23:03 ` Paul E. McKenney
2023-01-20 9:43 ` Jonas Oberhauser
2023-01-20 15:39 ` Paul E. McKenney
2023-01-20 20:46 ` Jonas Oberhauser
2023-01-20 21:37 ` Paul E. McKenney
2023-01-20 22:36 ` Jonas Oberhauser
2023-01-20 23:19 ` Paul E. McKenney
2023-01-21 0:03 ` Jonas Oberhauser
2023-01-21 0:34 ` Paul E. McKenney
2023-01-20 3:55 ` Paul E. McKenney
2023-01-20 9:20 ` Jonas Oberhauser
2023-01-20 12:34 ` Jonas Oberhauser
2023-01-20 12:51 ` Jonas Oberhauser
2023-01-20 15:32 ` Paul E. McKenney
2023-01-20 20:56 ` Jonas Oberhauser
2023-01-20 21:40 ` Paul E. McKenney
2023-01-20 16:14 ` Alan Stern
2023-01-20 17:30 ` Paul E. McKenney
2023-01-20 18:15 ` Alan Stern
2023-01-20 18:59 ` Paul E. McKenney
2023-01-20 10:13 ` Jonas Oberhauser
2023-01-20 15:47 ` Paul E. McKenney
2023-01-20 22:21 ` Jonas Oberhauser
2023-01-20 16:18 ` Alan Stern
2023-01-20 21:41 ` Jonas Oberhauser
2023-01-21 4:38 ` Paul E. McKenney
2023-01-21 17:36 ` Alan Stern
2023-01-21 18:40 ` Paul E. McKenney
2023-01-21 19:56 ` Alan Stern
2023-01-21 20:10 ` Paul E. McKenney
2023-01-21 21:03 ` Alan Stern
2023-01-21 23:49 ` Paul E. McKenney
2023-01-23 11:48 ` Jonas Oberhauser
2023-01-23 15:55 ` Alan Stern
2023-01-23 19:40 ` Jonas Oberhauser
2023-01-23 20:34 ` Alan Stern
2023-01-18 20:06 ` Paul E. McKenney
2023-01-18 20:54 ` Alan Stern
2023-01-18 21:05 ` Jonas Oberhauser
2023-01-19 0:02 ` Paul E. McKenney
2023-01-19 2:19 ` Alan Stern
2023-01-19 11:23 ` Paul E. McKenney
2023-01-20 16:01 ` Alan Stern
2023-01-20 17:58 ` Paul E. McKenney
2023-01-20 18:37 ` Alan Stern
2023-01-20 19:20 ` Paul E. McKenney
2023-01-20 20:36 ` Alan Stern
2023-01-20 21:20 ` Paul E. McKenney
2023-01-22 20:32 ` Alan Stern
2023-01-23 20:16 ` Paul E. McKenney
2023-01-24 2:18 ` Alan Stern
2023-01-24 4:06 ` Paul E. McKenney
2023-01-24 11:09 ` Andrea Parri
2023-01-24 14:54 ` Paul E. McKenney
2023-01-24 15:11 ` Jonas Oberhauser
2023-01-24 16:22 ` Paul E. McKenney
2023-01-24 16:39 ` Jonas Oberhauser
2023-01-24 17:26 ` Paul E. McKenney
2023-01-24 19:30 ` Jonas Oberhauser
2023-01-24 22:15 ` Paul E. McKenney
2023-01-24 22:35 ` Alan Stern
2023-01-24 22:54 ` Paul E. McKenney
2023-01-25 1:54 ` Alan Stern
2023-01-25 2:20 ` Paul E. McKenney
2023-01-25 13:10 ` Jonas Oberhauser
2023-01-25 15:05 ` Paul E. McKenney
2023-01-25 15:34 ` Alan Stern
2023-01-25 17:18 ` Paul E. McKenney
2023-01-25 17:42 ` Jonas Oberhauser [this message]
2023-01-25 19:08 ` Alan Stern
2023-01-25 19:46 ` Paul E. McKenney
2023-01-25 20:36 ` Andrea Parri
2023-01-25 21:10 ` Jonas Oberhauser
2023-01-25 21:23 ` Paul E. McKenney
2023-01-25 20:46 ` Alan Stern
2023-01-25 21:38 ` Paul E. McKenney
2023-01-25 23:33 ` Paul E. McKenney
2023-01-26 1:45 ` Alan Stern
2023-01-26 1:53 ` Paul E. McKenney
2023-01-26 12:17 ` Jonas Oberhauser
2023-01-26 18:48 ` Paul E. McKenney
2023-01-27 15:03 ` Jonas Oberhauser
2023-01-27 16:50 ` Paul E. McKenney
2023-01-27 16:54 ` Paul E. McKenney
2023-01-18 19:57 ` Jonas Oberhauser
2023-01-18 21:06 ` Paul E. McKenney
2023-01-18 2:15 ` Alan Stern
2023-01-18 5:17 ` Paul E. McKenney
2023-01-18 16:03 ` Alan Stern
2023-01-18 16:59 ` Boqun Feng
2023-01-18 17:08 ` Alan Stern
2023-01-18 17:41 ` Paul E. McKenney
2023-01-19 19:07 ` Paul E. McKenney
2023-01-14 16:55 ` Alan Stern
2023-01-14 17:35 ` Paul E. McKenney
[not found] ` <17078dd97cb6480f9c51e27058af3197@huawei.com>
2023-01-14 17:27 ` 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=404dd9fd-f735-e844-e439-ea8594f98388@huaweicloud.com \
--to=jonas.oberhauser@huaweicloud.com \
--cc=akiyks@gmail.com \
--cc=boqun.feng@gmail.com \
--cc=dhowells@redhat.com \
--cc=dlustig@nvidia.com \
--cc=frederic@kernel.org \
--cc=j.alglave@ucl.ac.uk \
--cc=joel@joelfernandes.org \
--cc=jonas.oberhauser@huawei.com \
--cc=linux-kernel@vger.kernel.org \
--cc=luc.maranget@inria.fr \
--cc=npiggin@gmail.com \
--cc=parri.andrea@gmail.com \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=quic_neeraju@quicinc.com \
--cc=stern@rowland.harvard.edu \
--cc=urezki@gmail.com \
--cc=will@kernel.org \
/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).