linux-kernel - Re: [RFT][PATCH v1 2/5] cpuidle: menu: Use one loop for average and variance computations

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: <4ccf81b2-fa1e-479d-91f4-1c518594f877@arm.com>
Date: Mon, 17 Feb 2025 13:03:01 +0000
From: Christian Loehle <christian.loehle@....com>
To: "Rafael J. Wysocki" <rjw@...ysocki.net>,
 Linux PM <linux-pm@...r.kernel.org>
Cc: LKML <linux-kernel@...r.kernel.org>,
 Daniel Lezcano <daniel.lezcano@...aro.org>,
 Artem Bityutskiy <artem.bityutskiy@...ux.intel.com>,
 Aboorva Devarajan <aboorvad@...ux.ibm.com>
Subject: Re: [RFT][PATCH v1 2/5] cpuidle: menu: Use one loop for average and
 variance computations

On 2/6/25 14:24, Rafael J. Wysocki wrote:
> From: Rafael J. Wysocki <rafael.j.wysocki@...el.com>
> 
> Use the observation that one loop is sufficient to compute the average
> of an array of values and their variance to eliminate one of the loops
> from get_typical_interval().
> 
> While at it, make get_typical_interval() consistently use u64 as the
> 64-bit unsigned integer data type and rearrange some white space and the
> declarations of local variables in it (to make them follow the reverse
> X-mas tree pattern).
> 
> No intentional functional impact.
> 
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@...el.com>
> ---
>  drivers/cpuidle/governors/menu.c |   61 +++++++++++++++++----------------------
>  1 file changed, 28 insertions(+), 33 deletions(-)
> 
> --- a/drivers/cpuidle/governors/menu.c
> +++ b/drivers/cpuidle/governors/menu.c
> @@ -116,49 +116,45 @@
>   */
>  static unsigned int get_typical_interval(struct menu_device *data)
>  {
> -	int i, divisor;
> -	unsigned int max, thresh, avg;
> -	uint64_t sum, variance;
> -
> -	thresh = INT_MAX; /* Discard outliers above this value */
> +	unsigned int max, divisor, thresh = INT_MAX;
> +	u64 avg, variance, avg_sq;
> +	int i;
>  
>  again:
> -
> -	/* First calculate the average of past intervals */
> +	/* Compute the average and variance of past intervals. */
>  	max = 0;
> -	sum = 0;
> +	avg = 0;
> +	variance = 0;
>  	divisor = 0;
>  	for (i = 0; i < INTERVALS; i++) {
>  		unsigned int value = data->intervals[i];
> -		if (value <= thresh) {
> -			sum += value;
> -			divisor++;
> -			if (value > max)
> -				max = value;
> -		}
> +
> +		/* Discard data points above the threshold. */
> +		if (value > thresh)
> +			continue;
> +
> +		divisor++;
> +
> +		avg += value;
> +		variance += (u64)value * value;
> +
> +		if (value > max)
> +			max = value;
>  	}
>  
>  	if (!max)
>  		return UINT_MAX;
>  
> -	if (divisor == INTERVALS)
> -		avg = sum >> INTERVAL_SHIFT;
> -	else
> -		avg = div_u64(sum, divisor);
> -
> -	/* Then try to determine variance */
> -	variance = 0;
> -	for (i = 0; i < INTERVALS; i++) {
> -		unsigned int value = data->intervals[i];
> -		if (value <= thresh) {
> -			int64_t diff = (int64_t)value - avg;
> -			variance += diff * diff;
> -		}
> -	}
> -	if (divisor == INTERVALS)
> +	if (divisor == INTERVALS) {
> +		avg >>= INTERVAL_SHIFT;
>  		variance >>= INTERVAL_SHIFT;
> -	else
> +	} else {
> +		do_div(avg, divisor);
>  		do_div(variance, divisor);
> +	}
> +
> +	avg_sq = avg * avg;
> +	variance -= avg_sq;
>  
>  	/*
>  	 * The typical interval is obtained when standard deviation is
> @@ -173,10 +169,9 @@
>  	 * Use this result only if there is no timer to wake us up sooner.
>  	 */
>  	if (likely(variance <= U64_MAX/36)) {
> -		if ((((u64)avg*avg > variance*36) && (divisor * 4 >= INTERVALS * 3))
> -							|| variance <= 400) {
> +		if ((avg_sq > variance * 36 && divisor * 4 >= INTERVALS * 3) ||
> +		    variance <= 400)
>  			return avg;
> -		}
>  	}
>  
>  	/*
> 

Reviewed-by: Christian Loehle <christian.loehle@....com>