Re: [RFC PATCH] LKMM: Add ctrl_dep() macro for control dependency

[Linus Torvalds <torvalds@linux-foundation.org>]

On Fri, Oct 1, 2021 at 8:45 AM Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
>
> Well AFAIU, this example with cinc does guarantee the control dependency for the store
> to "y". The issue arises if we have additional stores which are also expected to be
> ordered by the control dependency, e.g.:
>
>         if (READ_ONCE(x)) {
>                 WRITE_ONCE(y, 1);
>         } else {
>                 WRITE_ONCE(y, 2);
>         }
>         WRITE_ONCE(z, 3);
>
> Here the store to "z" would not necessarily be ordered by the control dependency.

Actually, it is ordered as far as the *compiler* is concerned.

It's just that the two writes to 'y' might become a data dependency
(ie using a cmov or arithmetic tricks like 'adc'), then the hardware
might end up considering the write to 'z' to not have any dependencies
and be done early.

> Likewise with clang if we store the same value to different memory locations, e.g.:
>
>         if (READ_ONCE(x)) {
>                 WRITE_ONCE(a, 0);
>         } else {
>                 WRITE_ONCE(b, 0);
>         }
>         WRITE_ONCE(z, 3);
>
> With armv8, the csel instruction is done on the address being written to, which also
> removes the conditional branch. I think this last example is missing from the kernel
> documentation.

Note that the important part isn't necessarily the "control" part of
the dependency.

A *data* dependency is equally strong and valid, and orders the write
wrt the read too.

IOW, this chain is ordered:

     WRITE_ONCE(a, READ_ONCE(b));

without any control dependencies at all. The CPU fundamentally cannot
do the write before it has done the read.

So turning a control dependency into a data dependency DOES NOT remove
the ordering. It's fine. And it doesn't matter whether the data
dependency is on the actual stored data, or on the stored address. In
both cases it's a dependency, and the store cannot be done before the
load.

(NOTE! The CPU _internally_ might speculate the store address or store
data, and thus "do the store first". But it cannot become _visible_ to
anybody else before the speculation has been validated, so from a
memory ordering standpoint, the load always happens first - even if
the CPU internally might have done parts of the store before. All that
matters is the _effective_ memory ordering visible externally, not the
order in which the CPU did things).

Of course, the issue with a data dependency is that it's then "local
to that data". The example above with the write to 'z' is probably a
good example. If the "if ()" statement ends up visible to the CPU as
control flow, then the READ_ONCE(x) is ordered wrt the WRITE_ONCE(z).

But if the conditional WRITE_ONCE(a/b) ends up being done as a data
dependency on the address (or the store data), then the WRITE_ONCE(z)
is ordered in the instruction stream (because those are the C volatile
semantics), but could be visible out of order thanks to CPU memory
ordering.

But again - a lot of these made-up examples are exactly that: made up.
For us to have a ctrl_dep() macro, I really want to see an actual
honest-to-goodness case of this that we can point to.

               Linus