lkml.org 
[lkml]   [2021]   [Oct]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC PATCH] LKMM: Add ctrl_dep() macro for control dependency
On Fri, Oct 01, 2021 at 11:28:58AM -0400, Mathieu Desnoyers wrote:
> ----- On Sep 29, 2021, at 7:57 PM, paulmck paulmck@kernel.org wrote:
>
> > On Wed, Sep 29, 2021 at 04:47:03PM -0500, Segher Boessenkool wrote:
> >> Hi!
> >>
> >> On Tue, Sep 28, 2021 at 05:15:07PM -0400, Mathieu Desnoyers wrote:
> >> > C99 describes that accessing volatile objects are side-effects, and that
> >> > "at certain specified points in the execution sequence called sequence
> >> > points, all side effects of previous evaluations shall be complete
> >> > and no side effects of subsequent evaluations shall have taken
> >> > place". [2]
> >>
> >> But note that the kernel explicitly uses C89 (with GNU extensions).
> >> Side effects are largely equal there though.
> >>
> >> Also note that there may no place in the generated machine code that
> >> corresponds exactly to some sequence point. Sequence points are a
> >> concept that applies to the source program and how that executes on the
> >> abstract machine.
> >
> > Plus the "as if" rule rears its ugly head in many of these situations.
> >
> >> > +Because ctrl_dep emits distinct asm volatile within each leg of the if
> >> > +statement, the compiler cannot transform the two writes to 'b' into a
> >> > +conditional-move (cmov) instruction, thus ensuring the presence of a
> >> > +conditional branch. Also because the ctrl_dep emits asm volatile within
> >> > +each leg of the if statement, the compiler cannot move the write to 'c'
> >> > +before the conditional branch.
> >>
> >> I think your reasoning here misses some things. So many that I don't
> >> know where to start to list them, every "because" and "thus" here does
> >> not follow, and even the statements of fact are not a given.
> >>
> >> Why do you want a conditional branch insn at all, anyway? You really
> >> want something else as far as I can see.
> >
> > Because at the assembly language level on some architectures, a
> > conditional branch instruction provides weak but very real and very
> > useful memory-ordering properties. Such a branch orders all loads
> > whose return values feed into the branch condition before any stores
> > that execute after the branch does (regardless of whether or not the
> > branch was taken). And this is all the ordering that is required for
> > the use cases that Mathieu is worried about.
> >
> > Yes, you can use explicit memory-barrier or acquire-load instructions,
> > but those incur more overhead on some types of hardware. The code in
> > question is on a hotpath and is thus performance-critical.
> >
> > It would be nice to be able to somehow tell the compiler exactly
> > what the ordering constraints are ("this particular load must be
> > ordered before these particular stores") and then let it (1) figure
> > out that a conditional branch will do the trick and (2) generate the
> > code accordingly. But last I checked, this was not going to happen any
> > time soon. So for the time being, we have to live within the current
> > capability of the tools that are available to us.
> >
> > Linus points out that in all the actual control-dependent code in
> > the Linux kernel, the compiler is going to be hard-pressed to fail
> > to emit the required branch. (Or in the case of ARMv8, the required
> > conditional-move instruction.)
> >
> > Mathieu, for his part, recently read the relevant portions of
> > memory-barriers.txt (reproduced below) and would like to simplify these
> > coding guidlines, which, speaking as the author of those guidelines,
> > would be an extremely good thing. His patches are attempting to move
> > us in that direction.
> >
> > Alternatives include: (1) Using acquire loads or memory barriers
> > and accepting the loss in performance, but giving the compiler much
> > less leeway, (2) Ripping all of the two-legged "if" examples from
> > memory-barriers.txt and restricting control dependencies to else-less
> > "if" statements, again giving the compiler less leeway, and (3) Your
> > ideas here.
> >
> > Does that help, or am I missing your point?
>
> Thanks Paul, it does help explaining the motivation for relying on
> control dependencies for some fast-path memory ordering in the kernel.
>
> And yes, my main goal is to simplify the coding guide lines, but I have
> not found any example of bad generated code in the tree kernel at this
> point. In some cases (e.g. uses of smp_acquire__after_ctrl_dep()) it's
> mainly thanks to luck though.
>
> There is another alternative we could list here: implement ctrl_dep_true(),
> ctrl_dep_false() and ctrl_dep(), which would respectively ensure a
> control dependency on the then leg, on the else leg, or on both legs of
> a conditional expression evaluation.
>
> >
> >> It is essential here that there is a READ_ONCE and the WRITE_ONCE.
> >> Those things might make it work the way you want, but as Linus says this
> >> is all way too subtle. Can you include the *_ONCE into the primitive
> >> itself somehow?
> >
> > Actually, if the store is not involved in a data race, the WRITE_ONCE()
> > is not needed. And in that case, the compiler is much less able to
> > fail to provide the needed ordering. (No, the current documentation
> > does not reflect this.) But if there is a data race, then your point
> > is right on the mark -- that WRITE_ONCE() cannot be safely omitted.
> >
> > But you are absolutely right that the READ_ONCE() or equivalent is not
> > at all optional. An example of an acceptable equivalent is an atomic
> > read-modify-write operation such as atomic_xchg_relaxed().
> >
> > The question about whether the READ_ONCE() and WRITE_ONCE() can be
> > incorporated into the macro I leave to Mathieu. I can certainly see
> > serious benefits from this approach, at least from a compiler viewpoint.
> > I must reserve judgment on usability until I see a proposal.
>
> [...]
>
> After having audited thoroughly all obviously documented control dependencies
> in the kernel tree, I'm not sure that including the READ_ONCE() and WRITE_ONCE()
> with the ctrl_dep() macro is a good idea, because in some cases there is
> calculation to be done on the result of the READ_ONCE() (e.g. through
> a static inline) before handing it over to the conditional expression.
> In other cases many stores are being done after the control dependency, e.g.:
>
> kernel/events/ring_buffer.c:__perf_output_begin()
>
> do {
> tail = READ_ONCE(rb->user_page->data_tail);
> offset = head = local_read(&rb->head);
> if (!rb->overwrite) {
> if (unlikely(!ring_buffer_has_space(head, tail,
> perf_data_size(rb),
> size, backward)))
> goto fail;
> }
>
> /*
> * The above forms a control dependency barrier separating the
> * @tail load above from the data stores below. Since the @tail
> * load is required to compute the branch to fail below.
> *
> * A, matches D; the full memory barrier userspace SHOULD issue
> * after reading the data and before storing the new tail
> * position.
> *
> * See perf_output_put_handle().
> */
>
> if (!backward)
> head += size;
> else
> head -= size;
> } while (local_cmpxchg(&rb->head, offset, head) != offset);
>
> if (backward) {
> offset = head;
> head = (u64)(-head);
> }
>
> /*
> * We rely on the implied barrier() by local_cmpxchg() to ensure
> * none of the data stores below can be lifted up by the compiler.
> */
>
> [...]

Indeed, these things do not necessarily fit a nice simple pattern.

> Note that I suspect that this control dependency documentation could be
> improved to state that the first control dependency is with the following
> local_cmpxchg store, which itself has a control dependency (when it evaluates
> to false) with the following stores to the ring buffer. Those are not volatile
> stores, but the "memory" clobber with the local_cmpxchg should ensure that
> following stores are after the local_cmpxchg in program order.
>
> One other thing we could do to improve things slightly would be to turn
> smp_acquire__after_ctrl_dep() into something which really is an acquire
> in all cases, which may not currently be true if the compiler finds a
> matching barrier()/smp_rmb() in the other leg after the conditional
> expression.

Tools to post-process binaries have been suggested in other venues,
but there would still need to be a way to tell the tool what the
constraints are.

Thanx, Paul

\
 
 \ /
  Last update: 2021-10-02 00:54    [W:0.100 / U:0.120 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site