* (Non-) Ctrl Dependency in litmus-tests.txt?
@ 2022-06-03 14:12 Paul Heidekrüger
2022-06-03 14:48 ` Alan Stern
0 siblings, 1 reply; 2+ messages in thread
From: Paul Heidekrüger @ 2022-06-03 14:12 UTC (permalink / raw)
To: Alan Stern, Andrea Parri, Will Deacon, Peter Zijlstra,
Boqun Feng, Nicholas Piggin, David Howells, Jade Alglave,
Luc Maranget, Paul E. McKenney, Akira Yokosawa, Daniel Lustig,
Joel Fernandes, linux-kernel, linux-arch
Cc: Marco Elver
Hi all,
I was going through litmus-tests.txt and came across the following:
> LIMITATIONS
> ===========
>
> Limitations of the Linux-kernel memory model (LKMM) include:
>
> 1.Compiler optimizations are not accurately modeled. Of course,
> the use of READ_ONCE() and WRITE_ONCE() limits the compiler's
> ability to optimize, but under some circumstances it is possible
> for the compiler to undermine the memory model. For more
> information, see Documentation/explanation.txt (in particular,
> the "THE PROGRAM ORDER RELATION: po AND po-loc" and "A WARNING"
> sections).
>
> Note that this limitation in turn limits LKMM's ability to
> accurately model address, control, and data dependencies.
> For example, if the compiler can deduce the value of some variable
> carrying a dependency, then the compiler can break that dependency
> by substituting a constant of that value.
>
> Conversely, LKMM sometimes doesn't recognize that a particular
> optimization is not allowed, and as a result, thinks that a
> dependency is not present (because the optimization would break it).
> The memory model misses some pretty obvious control dependencies
> because of this limitation. A simple example is:
>
> r1 = READ_ONCE(x);
> if (r1 == 0)
> smp_mb();
> WRITE_ONCE(y, 1);
>
> There is a control dependency from the READ_ONCE to the WRITE_ONCE,
> even when r1 is nonzero, but LKMM doesn't realize this and thinks
> that the write may execute before the read if r1 != 0. (Yes, that
> doesn't make sense if you think about it, but the memory model's
> intelligence is limited.)
I'm unclear as to why the documentation sees a control dependency from
the READ_ONCE() to the WRITE_ONCE() here.
Quoting from explanation.txt:
> Finally, a read event and another memory access event are linked by a
> control dependency if the value obtained by the read affects whether
> the second event is executed at all.
Architectures might consider this control-dependent, yes, but since the
value of the if condition does not affect whether the WRITE_ONCE() is
executed at all, I'm not sure why this should be considered
control-dependent in LKMM?
I might have another question about explanation.txt's definition of
control dependencies as per above, but will address it more thoroughly
in another email :-)
Many thanks,
Paul
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: (Non-) Ctrl Dependency in litmus-tests.txt?
2022-06-03 14:12 (Non-) Ctrl Dependency in litmus-tests.txt? Paul Heidekrüger
@ 2022-06-03 14:48 ` Alan Stern
0 siblings, 0 replies; 2+ messages in thread
From: Alan Stern @ 2022-06-03 14:48 UTC (permalink / raw)
To: Paul Heidekrüger
Cc: Andrea Parri, Will Deacon, Peter Zijlstra, Boqun Feng,
Nicholas Piggin, David Howells, Jade Alglave, Luc Maranget,
Paul E. McKenney, Akira Yokosawa, Daniel Lustig, Joel Fernandes,
linux-kernel, linux-arch, Marco Elver
On Fri, Jun 03, 2022 at 04:12:37PM +0200, Paul Heidekrüger wrote:
> Hi all,
>
> I was going through litmus-tests.txt and came across the following:
>
> > LIMITATIONS
> > ===========
> >
> > Limitations of the Linux-kernel memory model (LKMM) include:
> >
> > 1.Compiler optimizations are not accurately modeled. Of course,
> > the use of READ_ONCE() and WRITE_ONCE() limits the compiler's
> > ability to optimize, but under some circumstances it is possible
> > for the compiler to undermine the memory model. For more
> > information, see Documentation/explanation.txt (in particular,
> > the "THE PROGRAM ORDER RELATION: po AND po-loc" and "A WARNING"
> > sections).
> >
> > Note that this limitation in turn limits LKMM's ability to
> > accurately model address, control, and data dependencies.
> > For example, if the compiler can deduce the value of some variable
> > carrying a dependency, then the compiler can break that dependency
> > by substituting a constant of that value.
> >
> > Conversely, LKMM sometimes doesn't recognize that a particular
> > optimization is not allowed, and as a result, thinks that a
> > dependency is not present (because the optimization would break it).
> > The memory model misses some pretty obvious control dependencies
> > because of this limitation. A simple example is:
> >
> > r1 = READ_ONCE(x);
> > if (r1 == 0)
> > smp_mb();
> > WRITE_ONCE(y, 1);
> >
> > There is a control dependency from the READ_ONCE to the WRITE_ONCE,
> > even when r1 is nonzero, but LKMM doesn't realize this and thinks
> > that the write may execute before the read if r1 != 0. (Yes, that
> > doesn't make sense if you think about it, but the memory model's
> > intelligence is limited.)
>
> I'm unclear as to why the documentation sees a control dependency from
> the READ_ONCE() to the WRITE_ONCE() here.
>
> Quoting from explanation.txt:
> > Finally, a read event and another memory access event are linked by a
> > control dependency if the value obtained by the read affects whether
> > the second event is executed at all.
>
> Architectures might consider this control-dependent, yes, but since the
> value of the if condition does not affect whether the WRITE_ONCE() is
> executed at all, I'm not sure why this should be considered
> control-dependent in LKMM?
>
> I might have another question about explanation.txt's definition of
> control dependencies as per above, but will address it more thoroughly
> in another email :-)
You're right; strictly speaking this isn't a control dependency. In
fact it's not a dependency at all, just an ordering restriction that's
connected with a conditional test.
If you would like to submit a patch updating the text, please feel free
to do so.
Alan
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2022-06-03 14:48 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-06-03 14:12 (Non-) Ctrl Dependency in litmus-tests.txt? Paul Heidekrüger
2022-06-03 14:48 ` Alan Stern
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.