[PATCH] tracing/histogram: Optimize division by constants

[PATCH] tracing/histogram: Optimize division by constants

[Kalesh Singh]

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>
---

This patch is dependent on the series at:
https://lore.kernel.org/r/20211025200852.3002369-1-kaleshsingh@google.com/

 kernel/trace/trace_events_hist.c | 120 ++++++++++++++++++++++++++++++-
 1 file changed, 119 insertions(+), 1 deletion(-)

diff --git a/kernel/trace/trace_events_hist.c b/kernel/trace/trace_events_hist.c
index 364cb3091789..c806df88ddb5 100644
--- a/kernel/trace/trace_events_hist.c
+++ b/kernel/trace/trace_events_hist.c
@@ -92,6 +92,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 +161,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 +314,83 @@ static u64 hist_field_div(struct hist_field *hist_field,
 	return div64_u64(val1, val2);
 }
 
+static u64 div_by_zero(struct hist_field *hist_field,
+			struct tracing_map_elt *elt,
+			struct trace_buffer *buffer,
+			struct ring_buffer_event *rbe,
+			void *event)
+{
+	return -1;
+}
+
+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);
+
+	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 hist_field_fn_t hist_field_get_div_fn(struct hist_field *divisor);
+
 static u64 hist_field_mult(struct hist_field *hist_field,
 			   struct tracing_map_elt *elt,
 			   struct trace_buffer *buffer,
@@ -573,6 +653,40 @@ 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)
+		return div_by_zero;
+
+	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;
@@ -2595,7 +2709,11 @@ static struct hist_field *parse_expr(struct hist_trigger_data *hist_data,
 
 		expr->name = expr_str(expr, 0);
 	} else {
-		expr->fn = op_fn;
+		if (field_op == FIELD_OP_DIV &&
+				operand2_flags & HIST_FIELD_FL_CONST)
+			expr->fn = hist_field_get_div_fn(operand2);
+		else
+			expr->fn = op_fn;
 
 		/* The operand sizes should be the same, so just pick one */
 		expr->size = operand1->size;
-- 
2.33.0.1079.g6e70778dc9-goog

Re: [PATCH] tracing/histogram: Optimize division by constants

[Steven Rostedt]

On Wed, 27 Oct 2021 20:28:54 -0700
Kalesh Singh <kaleshsingh@google.com> wrote:

> +/*
> + * 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)
> +		return div_by_zero;

Do we really need a div_by_zero constant function? What about just
erroring here and perhaps return -EDOM?

-- Steve

> +
> +	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;
> +}
> +

Re: [PATCH] tracing/histogram: Optimize division by constants

[Kalesh Singh]

On Thu, Oct 28, 2021 at 7:01 PM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Wed, 27 Oct 2021 20:28:54 -0700
> Kalesh Singh <kaleshsingh@google.com> wrote:
>
> > +/*
> > + * 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)
> > +             return div_by_zero;
>
> Do we really need a div_by_zero constant function? What about just
> erroring here and perhaps return -EDOM?

Good point. We can detect this if the divisor is a constant and print
an error message instead. It'll also warrant a small update to the
tests and documentation. I'll send out a new version addressing these.

Thanks,
Kalesh

>
> -- Steve
>
> > +
> > +     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;
> > +}
> > +