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: <20250205103929.1538065-1-kniv@yandex-team.ru>
Date: Wed,  5 Feb 2025 13:39:29 +0300
From: Nikolay Kuratov <kniv@...dex-team.ru>
To: linux-kernel@...r.kernel.org
Cc: linux-trace-kernel@...r.kernel.org,
	Wen Yang <wenyang@...ux.alibaba.com>,
	Steven Rostedt <rostedt@...dmis.org>,
	Mark Rutland <mark.rutland@....com>,
	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
	kniv@...dex-team.ru
Subject: Re: [PATCH] ftrace: Avoid potential division by zero in function_stat_show()

Your approach should prevent both zero division and overflow in the
denominator. We also should consider that the numerator

> stddev = counter * rec->time_squared - rec->stddev_time * rec->stddev_time;

may overflow too. Suppose 1000 ns per call case. On each function execution
time_squared would get additional 10^6. So for 32-bit and
MAX_STDDEV_COUNTER = 2072 we would have
counter * rec->time_squared = 2071 * (2071 * 10^6) = 4289041000000,
a 42-bit number.

It looks like overflow prevention here is not viable with macro constants,
since function execution time is dynamic in nature.

My suggestion is to rewrite formula such as we perform division earlier
and avoid overflow checks as much as possible. Note that doing divisions
earlier may result in precision loss, but I think that is acceptable since
rec->time is nanoseconds precision. Also this allows us to not care about
counter overflow at all, because expression rec->time * rec->time will always
overflow earlier than both counter and rec->time_square_sum. Renamed
time_squared into time_square_sum just to clarify.

diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c
index 728ecda6e8d4..91e7185dd5de 100644
--- a/kernel/trace/ftrace.c
+++ b/kernel/trace/ftrace.c
@@ -419,7 +419,8 @@ struct ftrace_profile {
 	unsigned long			counter;
 #ifdef CONFIG_FUNCTION_GRAPH_TRACER
 	unsigned long long		time;
-	unsigned long long		time_squared;
+	unsigned long long		time_square_sum;
+	unsigned long long		saved_stddev;
 #endif
 };
 
@@ -560,22 +561,24 @@ static int function_stat_show(struct seq_file *m, void *v)
 	seq_puts(m, "    ");
 
 	/* Sample standard deviation (s^2) */
-	if (rec->counter <= 1)
+	if (rec->counter <= 1 || !rec->time)
 		stddev = 0;
+	else if (div64_ul(rec->time * rec->time, rec->time) != rec->time)
+		stddev = rec->saved_stddev;
 	else {
 		/*
-		 * Apply Welford's method:
-		 * s^2 = 1 / (n * (n-1)) * (n * \Sum (x_i)^2 - (\Sum x_i)^2)
+		 * A formula for calculating the variance is:
+		 * s^2 = (\Sum (x_i)^2 - (\Sum x_i)^2 / n) / (n - 1)
 		 */
-		stddev = rec->counter * rec->time_squared -
-			 rec->time * rec->time;
-
+		stddev = rec->time_square_sum -
+			 div64_ul(rec->time * rec->time, rec->counter);
+		stddev = div64_ul(stddev, rec->counter - 1);
 		/*
 		 * Divide only 1000 for ns^2 -> us^2 conversion.
 		 * trace_print_graph_duration will divide 1000 again.
 		 */
-		stddev = div64_ul(stddev,
-				  rec->counter * (rec->counter - 1) * 1000);
+		stddev = div64_ul(stddev, 1000);
+		rec->saved_stddev = stddev;
 	}
 
 	trace_seq_init(&s);
@@ -888,7 +891,7 @@ static void profile_graph_return(struct ftrace_graph_ret *trace,
 	rec = ftrace_find_profiled_func(stat, trace->func);
 	if (rec) {
 		rec->time += calltime;
-		rec->time_squared += calltime * calltime;
+		rec->time_square_sum += calltime * calltime;
 	}
 }