Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
MIME-Version: 1.0
References: <20211029183339.3216491-1-kaleshsingh@google.com>
 <20211029183339.3216491-2-kaleshsingh@google.com> <20211029144524.367d6789@gandalf.local.home>
 <CAC_TJve9OsL5taBN0ckgjG4=HxvmWfP6ULwwqnVsDyRxuQuRkg@mail.gmail.com>
In-Reply-To: <CAC_TJve9OsL5taBN0ckgjG4=HxvmWfP6ULwwqnVsDyRxuQuRkg@mail.gmail.com>
From:   Kalesh Singh <kaleshsingh@google.com>
Date:   Fri, 29 Oct 2021 12:16:35 -0700
Message-ID: <CAC_TJvcLKT+Gaz46Y-=7f7o12zoRWD=z4Ht5cbu+y5s5K4qEWw@mail.gmail.com>
Subject: Re: [PATCH v2 1/4] tracing/histogram: Optimize division by constants
To:     Steven Rostedt <rostedt@goodmis.org>
Cc:     surenb@google.com, hridya@google.com, namhyung@kernel.org,
        kernel-team@android.com, mhiramat@kernel.org,
        Jonathan Corbet <corbet@lwn.net>,
        Ingo Molnar <mingo@redhat.com>, Shuah Khan <shuah@kernel.org>,
        Tom Zanussi <zanussi@kernel.org>, linux-doc@vger.kernel.org,
        linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Fri, Oct 29, 2021 at 11:53 AM Kalesh Singh <kaleshsingh@google.com> wrote:
>
> On Fri, Oct 29, 2021 at 11:45 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> >
> > On Fri, 29 Oct 2021 11:33:27 -0700
> > Kalesh Singh <kaleshsingh@google.com> wrote:
> >
> > > If the divisor is a constant use specific division functions to
> > > avoid extra branches when the trigger is hit.
> > >
> > > If the divisor constant but not a power of 2, the division can be
> > > replaced with a multiplication and shift in the following case:
> > >
> > > Let X = dividend and Y = divisor.
> > >
> > > Choose Z = some power of 2. If Y <= Z, then:
> > >     X / Y = (X * (Z / Y)) / Z
> > >
> > > (Z / Y) is a constant (mult) which is calculated at parse time, so:
> > >     X / Y = (X * mult) / Z
> > >
> > > The division by Z can be replaced by a shift since Z is a power of 2:
> > >     X / Y = (X * mult) >> shift
> > >
> > > As long, as X < Z the results will not be off by more than 1.
> > >
> > > Signed-off-by: Kalesh Singh <kaleshsingh@google.com>
> > > Suggested-by: Steven Rostedt <rostedt@goodmis.org>
> > > ---
> > >
> > > Changes in v2:
> > >   - Return -EDOM if divisor is a constant and zero, per Steve
> > >
> > >  kernel/trace/trace_events_hist.c | 117 ++++++++++++++++++++++++++++++-
> > >  1 file changed, 116 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/kernel/trace/trace_events_hist.c b/kernel/trace/trace_events_hist.c
> > > index 364cb3091789..1084aa41f047 100644
> > > --- a/kernel/trace/trace_events_hist.c
> > > +++ b/kernel/trace/trace_events_hist.c
> > > @@ -68,7 +68,8 @@
> > >       C(INVALID_SORT_FIELD,   "Sort field must be a key or a val"),   \
> > >       C(INVALID_STR_OPERAND,  "String type can not be an operand in expression"), \
> > >       C(EXPECT_NUMBER,        "Expecting numeric literal"),           \
> > > -     C(UNARY_MINUS_SUBEXPR,  "Unary minus not supported in sub-expressions"),
> > > +     C(UNARY_MINUS_SUBEXPR,  "Unary minus not supported in sub-expressions"), \
> > > +     C(DIVISION_BY_ZERO,     "Division by zero"),
> > >
> > >  #undef C
> > >  #define C(a, b)              HIST_ERR_##a
> > > @@ -92,6 +93,7 @@ typedef u64 (*hist_field_fn_t) (struct hist_field *field,
> > >  #define HIST_FIELDS_MAX              (TRACING_MAP_FIELDS_MAX + TRACING_MAP_VARS_MAX)
> > >  #define HIST_ACTIONS_MAX     8
> > >  #define HIST_CONST_DIGITS_MAX        21
> > > +#define HIST_DIV_SHIFT               20  /* For optimizing division by constants */
> > >
> > >  enum field_op_id {
> > >       FIELD_OP_NONE,
> > > @@ -160,6 +162,8 @@ struct hist_field {
> > >
> > >       /* Numeric literals are represented as u64 */
> > >       u64                             constant;
> > > +     /* Used to optimize division by constants */
> > > +     u64                             div_multiplier;
> > >  };
> > >
> > >  static u64 hist_field_none(struct hist_field *field,
> > > @@ -311,6 +315,72 @@ static u64 hist_field_div(struct hist_field *hist_field,
> > >       return div64_u64(val1, val2);
> > >  }
> > >
> > > +static u64 div_by_power_of_two(struct hist_field *hist_field,
> > > +                             struct tracing_map_elt *elt,
> > > +                             struct trace_buffer *buffer,
> > > +                             struct ring_buffer_event *rbe,
> > > +                             void *event)
> > > +{
> > > +     struct hist_field *operand1 = hist_field->operands[0];
> > > +     struct hist_field *operand2 = hist_field->operands[1];
> > > +
> > > +     u64 val1 = operand1->fn(operand1, elt, buffer, rbe, event);
> > > +     u64 val2 = operand2->fn(operand2, elt, buffer, rbe, event);
> >
> > If these functions are only called when val2 is constant, can't we make it
> > such that we get val2 from the hist_field directly? That is:
> >
> >         u64 val2 = operand2->constant;
>
> operand2 might be a var ref to a constant, so we would need to resolve
> that with hist_field_var_ref().
>
> -Kalesh
>
> >
> > That would save us a function call, and an indirect on at that (that gets
> > slowed down by spectre).

So would it be adding something like below?

if (operand2->flags & HIST_FIELD_FL_CONST)
        val2 = operand2->constant;
else
        val2 = operand2->fn(operand2, elt, buffer, rbe, event);

Thanks,
Kalesh

> >
> > Same for the ones below.
> >
> > -- Steve
> >
> >
> > > +
> > > +     return val1 >> __ffs64(val2);
> > > +}
> > > +
> > > +static u64 div_by_not_power_of_two(struct hist_field *hist_field,
> > > +                             struct tracing_map_elt *elt,
> > > +                             struct trace_buffer *buffer,
> > > +                             struct ring_buffer_event *rbe,
> > > +                             void *event)
> > > +{
> > > +     struct hist_field *operand1 = hist_field->operands[0];
> > > +     struct hist_field *operand2 = hist_field->operands[1];
> > > +
> > > +     u64 val1 = operand1->fn(operand1, elt, buffer, rbe, event);
> > > +     u64 val2 = operand2->fn(operand2, elt, buffer, rbe, event);
> > > +
> > > +     return div64_u64(val1, val2);
> > > +}
> > > +
> > > +static u64 div_by_mult_and_shift(struct hist_field *hist_field,
> > > +                             struct tracing_map_elt *elt,
> > > +                             struct trace_buffer *buffer,
> > > +                             struct ring_buffer_event *rbe,
> > > +                             void *event)
> > > +{
> > > +     struct hist_field *operand1 = hist_field->operands[0];
> > > +     struct hist_field *operand2 = hist_field->operands[1];
> > > +
> > > +     u64 val1 = operand1->fn(operand1, elt, buffer, rbe, event);
> > > +
> > > +     /*
> > > +      * If the divisor is a constant, do a multiplication and shift instead.
> > > +      *
> > > +      * Choose Z = some power of 2. If Y <= Z, then:
> > > +      *     X / Y = (X * (Z / Y)) / Z
> > > +      *
> > > +      * (Z / Y) is a constant (mult) which is calculated at parse time, so:
> > > +      *     X / Y = (X * mult) / Z
> > > +      *
> > > +      * The division by Z can be replaced by a shift since Z is a power of 2:
> > > +      *     X / Y = (X * mult) >> HIST_DIV_SHIFT
> > > +      *
> > > +      * As long, as X < Z the results will not be off by more than 1.
> > > +      */
> > > +     if (val1 < (1 << HIST_DIV_SHIFT)) {
> > > +             u64 mult = operand2->div_multiplier;
> > > +
> > > +             return (val1 * mult + ((1 << HIST_DIV_SHIFT) - 1)) >> HIST_DIV_SHIFT;
> > > +     } else {
> > > +             u64 val2 = operand2->fn(operand2, elt, buffer, rbe, event);
> > > +
> > > +             return div64_u64(val1, val2);
> > > +     }
> > > +}
> > > +
> > >  static u64 hist_field_mult(struct hist_field *hist_field,
> > >                          struct tracing_map_elt *elt,
> > >                          struct trace_buffer *buffer,
> > > @@ -573,6 +643,37 @@ struct snapshot_context {
> > >       void                    *key;
> > >  };
> > >
> > > +
> > > +static struct hist_field *find_var_field(struct hist_trigger_data *hist_data,
> > > +                                      const char *var_name);
> > > +
> > > +/*
> > > + * Returns the specific division function to use if the divisor
> > > + * is constant. This avoids extra branches when the trigger is hit.
> > > + */
> > > +static hist_field_fn_t hist_field_get_div_fn(struct hist_field *divisor)
> > > +{
> > > +     u64 div;
> > > +
> > > +     if (divisor->flags & HIST_FIELD_FL_VAR_REF) {
> > > +             struct hist_field *var;
> > > +
> > > +             var = find_var_field(divisor->var.hist_data, divisor->name);
> > > +             div = var->constant;
> > > +     } else
> > > +             div = divisor->constant;
> > > +
> > > +     if (!(div & (div - 1)))
> > > +             return div_by_power_of_two;
> > > +
> > > +     /* If the divisor is too large, do a regular division */
> > > +     if (div > (1 << HIST_DIV_SHIFT))
> > > +             return div_by_not_power_of_two;
> > > +
> > > +     divisor->div_multiplier = div64_u64((u64)(1 << HIST_DIV_SHIFT), div);
> > > +     return div_by_mult_and_shift;
> > > +}
> > > +
> > >  static void track_data_free(struct track_data *track_data)
> > >  {
> > >       struct hist_elt_data *elt_data;
> > > @@ -2575,6 +2676,20 @@ static struct hist_field *parse_expr(struct hist_trigger_data *hist_data,
> > >       expr->operands[0] = operand1;
> > >       expr->operands[1] = operand2;
> > >
> > > +
> > > +     if (field_op == FIELD_OP_DIV &&
> > > +                     operand2_flags & HIST_FIELD_FL_CONST) {
> > > +             u64 divisor = (var2) ? var2->constant : operand2->constant;
> > > +
> > > +             if (!divisor) {
> > > +                     hist_err(file->tr, HIST_ERR_DIVISION_BY_ZERO, errpos(str));
> > > +                     ret = -EDOM;
> > > +                     goto free;
> > > +             }
> > > +
> > > +             op_fn = hist_field_get_div_fn(operand2);
> > > +     }
> > > +
> > >       if (combine_consts) {
> > >               if (var1)
> > >                       expr->operands[0] = var1;
> >