Re: [PATCH] ftrace: Avoid potential division by zero in function_stat_show()

On Tue, 4 Feb 2025 17:20:45 -0500
Steven Rostedt [off-list ref] wrote:

x = rec->counter

  x * (x - 1) * 1000 = (2^32 - 1) // use minus 1 just to be sure
  x * (x - 1) = (2^32 - 1) / 1000
  x^2 - x = (2^32 - 1) / 1000
  x^2 - x - (2^32 - 1) / 1000 = 0

 x = (-b +/- sqrt(b^2 - 4ac)) / 2a

 a = 1
 b = -1
 c = -(2^32 - 1) / 1000 = -4294967.295

 x = (-1 +/- sqrt((-1)^2 - 4 * -4294967.295)) / 2

And I did make a mistake, as b = -1, and the above should start with -(-1)
or 1 :-p

 x = 2071.930 for 32bit

This should be: 2072.930

For 64bit we have

 c = -(2^64 - 1) / 1000 = -18446744073709551.615

That makes

  x = 135818790.812

And this needs to be: 135818791.812

+/*
+ * The calculation for stddev will overflow when the counter
+ * algorithm overflows the long size:
+ *
+ * rec->counter * (rec->counter - 1) * 1000 >= 2^BITS_PER_LONG
+ *
+ * Using the quadratic equation: x = (-b +/- sqrt(b^2 - 4ac)) / 2a
+ * we can figure out what the max rec->counter is before it
+ * overflows.
+ *
+ * x = rec->counter
+ * x * (x - 1) * 1000 = 2^BITS_PER_LONG - 1 // -1 for rounding
+ * x * (x - 1) = (2^BITS_PER_LONG - 1) / 1000
+ * x^2 - x = (2^BITS_PER_LONG - 1) / 1000
+ * x^2 - x - (2^BITS_PER_LONG - 1) / 1000 = 0
+ *
+ * a = 1
+ * b = -1
+ * c = -(2^BITS_PER_LONG - 1) / 1000
+ *
+ * x = (1 +/- sqrt(1 - 4 * -(2^BITS_PER_LONG - 1) / 1000)) / 2
+ *
+ * For 32bit that is: x = 2072.930 (or 2072)
+ * For 64bit that is: x = 135818791.812 (or 135818791)
+ */

But in the patch, I redid the numbers and did not copy from the above, and
here I did it correctly.

-- Steve