linux-kernel - Re: [PATCH] ftrace: Avoid potential division by zero in function_stat

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20250204194820.7ef50d96@gandalf.local.home>
Date: Tue, 4 Feb 2025 19:48:20 -0500
From: Steven Rostedt <rostedt@...dmis.org>
To: Nikolay Kuratov <kniv@...dex-team.ru>
Cc: linux-kernel@...r.kernel.org, linux-trace-kernel@...r.kernel.org, Wen
 Yang <wenyang@...ux.alibaba.com>, Mark Rutland <mark.rutland@....com>,
 Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Subject: Re: [PATCH] ftrace: Avoid potential division by zero in
 function_stat_show()

On Tue, 4 Feb 2025 17:20:45 -0500
Steven Rostedt <rostedt@...dmis.org> 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