From: Jonas Oberhauser <jonas.oberhauser@huaweicloud.com>
To: Alan Stern <stern@rowland.harvard.edu>
Cc: paulmck@kernel.org, parri.andrea@gmail.com, will@kernel.org,
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, joel@joelfernandes.org,
urezki@gmail.com, quic_neeraju@quicinc.com, frederic@kernel.org,
linux-kernel@vger.kernel.org, lkmm@lists.linux.dev,
hernan.poncedeleon@huaweicloud.com
Subject: Re: [RFC] tools/memory-model: Rule out OOTA
Date: Fri, 17 Jan 2025 17:45:50 +0100 [thread overview]
Message-ID: <a1019624-7f82-4897-a1f2-3a381794b2ad@huaweicloud.com> (raw)
In-Reply-To: <b0bac412-cfc4-4334-8d8e-2fb080fe6e3e@rowland.harvard.edu>
Am 1/17/2025 um 4:52 PM schrieb Alan Stern:
> On Thu, Jan 16, 2025 at 06:02:18PM -0500, Alan Stern wrote:
>> On Thu, Jan 16, 2025 at 08:08:22PM +0100, Jonas Oberhauser wrote:
>>> I would say that the approach with volatile is overzealous because it tries
>>> to create a "local" order solution to the problem that only requires a
>>> "global" ordering solution. Since not every semantic dependency needs to
>>> provide order in C++ -- only the cycle of dependencies -- it is totally ok
>>> to add too many semantic dependency edges to a program, even those that are
>>> not going to be exactly maintained by every compiler, as long as we can
>>> ensure that globally, no dependency cycle occurs.
>>
>> But then how would you characterize semantic dependencies, if you want
>> to allow the definition to include some dependencies that aren't
>> semantic but not so many that you ever create a cycle? This sounds like
>> an even worse problem than we started with!
>
> An interesting side comment on this issue...
>
> This is a slight variation of the example on page 19 (section 4.3) of
> the paper. (Pretend this is actually C++ code, the shared variables are
> all atomic, and their accesses are all relaxed.)
>
> bool x, y, z;
>
> void P0(bool *x, bool *y, bool *z) {
> bool r1, r2;
>
> r1 = *x;
> r2 = *y;
>
> *z = (r1 != r2);
> }
>
> The paper points out that although there is an apparent semantic
> dependency from the load of x to the store to z, if the compiler is
> allowed not to handle atomics as quasi volatile then the dependency
> can be broken. Nevertheless, I am not able to think of a program that
> could exhibit OOTA as a result of breaking the semantic dependency. The
> best I can come up with is this:
>
> [P0 as above]
>
> void P1(bool *x, bool *y, bool *z) {
> bool r3;
>
> r3 = z;
> x = r3;
> }
>
> void P2(bool *x, bool *y, bool *z) {
> y = true;
> }
>
> exists (x=true /\ z=true)
>
> If P2 were not present, this result could not occur in any physical
> execution, even if the dependency in P0 is broken. With P2 this result
> isn't OOTA, even in executions where P0 ends up storing z before loading
> x, because P2 could have executed first, then P0, then P1.
>
> So perhaps this is an example of what you were talking about -- a
> dependency which may or may not be semantic, but either way cannot lead
> to OOTA.
Yes, that looks like an example of what I have in mind.
If at the model level we just say "yes there is a dependency, but no it
does not give any ordering guarantee", then the compiler is still free
to break the dependency like in your example.
A thread P3 { r1 = z; atomic_thread_fence(); r2 = y; }
could still observe r2 == false, r1 == true, "showing" that the
dependency was broken.
This would not violate such a model.
(if we consider consume, then that would need to restrict the compiler
from eliminating the dependency like this)
That is not to say that I am 100% sure that it is possible to define
sdep correctly to make this work.
One problem is if the compiler merges two threads (with an OOTA cycle of
3+ threads), it can turn sdep;rfe;sdep;rfe into sdep;rfi;sdep;rfe.
If sdep is too naive then it is easy to come up with counter examples
where this sdep;rfi;sdep no longer provides ordering, making the whole
sdep;rfe cycle possible.
I am not sure if sdep can be formalized in a way that ensures that this
sdep;rfi;sdep edge would still need to be preserved.
Of course one could have inter-thread semantic dependencies and only forbid
isdep ; rf (e?)
from being reflexive...
Best wishes,
jonas
next prev parent reply other threads:[~2025-01-17 16:46 UTC|newest]
Thread overview: 59+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-01-06 21:40 [RFC] tools/memory-model: Rule out OOTA Jonas Oberhauser
2025-01-07 10:06 ` Peter Zijlstra
2025-01-07 11:02 ` Jonas Oberhauser
2025-01-07 15:46 ` Jonas Oberhauser
2025-01-07 16:09 ` Alan Stern
2025-01-07 18:47 ` Paul E. McKenney
2025-01-08 17:39 ` Jonas Oberhauser
2025-01-08 18:09 ` Paul E. McKenney
2025-01-08 19:17 ` Jonas Oberhauser
2025-01-09 17:54 ` Paul E. McKenney
2025-01-09 18:35 ` Jonas Oberhauser
2025-01-10 14:54 ` Paul E. McKenney
2025-01-10 16:21 ` Jonas Oberhauser
2025-01-13 22:04 ` Paul E. McKenney
2025-01-16 18:40 ` Paul E. McKenney
2025-01-16 19:13 ` Jonas Oberhauser
2025-01-16 19:31 ` Paul E. McKenney
2025-01-16 20:21 ` Jonas Oberhauser
2025-01-16 19:28 ` Jonas Oberhauser
2025-01-16 19:39 ` Paul E. McKenney
2025-01-17 12:08 ` Jonas Oberhauser
2025-01-16 19:08 ` Jonas Oberhauser
2025-01-16 23:02 ` Alan Stern
2025-01-17 8:34 ` Hernan Ponce de Leon
2025-01-17 11:29 ` Jonas Oberhauser
2025-01-17 20:01 ` Alan Stern
2025-01-21 10:36 ` Jonas Oberhauser
2025-01-21 16:39 ` Alan Stern
2025-01-22 3:46 ` Jonas Oberhauser
2025-01-22 19:11 ` Alan Stern
2025-01-17 15:52 ` Alan Stern
2025-01-17 16:45 ` Jonas Oberhauser [this message]
2025-01-17 19:02 ` Alan Stern
2025-01-09 20:37 ` Peter Zijlstra
2025-01-09 21:13 ` Paul E. McKenney
2025-01-08 17:33 ` Jonas Oberhauser
2025-01-08 18:47 ` Alan Stern
2025-01-08 19:22 ` Jonas Oberhauser
2025-01-09 16:17 ` Alan Stern
2025-01-09 16:44 ` Jonas Oberhauser
2025-01-09 19:27 ` Alan Stern
2025-01-09 20:09 ` Jonas Oberhauser
2025-01-10 3:12 ` Alan Stern
2025-01-10 12:21 ` Jonas Oberhauser
2025-01-10 21:51 ` Alan Stern
2025-01-11 12:46 ` Jonas Oberhauser
2025-01-11 21:19 ` Alan Stern
2025-01-12 15:55 ` Jonas Oberhauser
2025-01-13 19:43 ` Alan Stern
2025-07-23 0:43 ` Paul E. McKenney
2025-07-23 7:26 ` Hernan Ponce de Leon
2025-07-23 16:39 ` Paul E. McKenney
2025-07-24 14:14 ` Paul E. McKenney
2025-07-25 5:23 ` Hernan Ponce de Leon
2025-07-29 20:34 ` Paul E. McKenney
2025-07-23 17:13 ` Alan Stern
2025-07-23 17:27 ` Paul E. McKenney
2025-07-23 19:25 ` Alan Stern
2025-07-23 19:57 ` 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=a1019624-7f82-4897-a1f2-3a381794b2ad@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=hernan.poncedeleon@huaweicloud.com \
--cc=j.alglave@ucl.ac.uk \
--cc=joel@joelfernandes.org \
--cc=linux-kernel@vger.kernel.org \
--cc=lkmm@lists.linux.dev \
--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 read-only IMAP folder(s) and NNTP newsgroup(s).