linux-kernel - Re: [PATCH V8 3/3] irq: Compute the periodic interval for interrupts

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]

Date:   Thu, 23 Mar 2017 15:40:39 -0400 (EDT)
From:   Nicolas Pitre <nicolas.pitre@...aro.org>
To:     Daniel Lezcano <daniel.lezcano@...aro.org>
cc:     tglx@...utronix.de, linux-kernel@...r.kernel.org,
        peterz@...radead.org, rafael@...nel.org, vincent.guittot@...aro.org
Subject: Re: [PATCH V8 3/3] irq: Compute the periodic interval for
 interrupts

On Thu, 23 Mar 2017, Daniel Lezcano wrote:

> +	/*
> +	 * Online variance divided by the number of elements if there
> +	 * is more than one sample.
> +	 */
> +	if (likely(irqs->count > 1))
> +		variance = div_u64(irqs->variance, irqs->count - 1);

Isn't it mostly likely that irqs->count will be equal to 
IRQ_TIMINGS_SIZE in most cases?  And if so, given that IRQ_TIMINGS_SIZE 
== 32, we _could_ possibly approximate the division by 31 with a 
division by 32 without affecting too much the final outcome.  Then the 
very expensive div_u64() could be replaced by:

	variance = irqs->variance >> 5;

Or at least keep a constant divisor that div_u64() is able to optimize 
with a reciprocal multiplication.

This is even more important by the fact that this function is called 
in a loop, up to IRQ_TIMINGS_SIZE times.

> +	 * The rule of thumb in statistics for the normal distribution
> +	 * is having at least 30 samples in order to have the model to
> +	 * apply. Values outside the interval are considered as an
> +	 * anomaly.
> +	 */
> +	if ((irqs->count >= 30) && ((diff * diff) > (9 * variance))) {
> +		/*
> +		 * After three consecutive anomalies, we reset the
> +		 * stats as it is no longer stable enough.
> +		 */
> +		if (irqs->anomalies++ >= 3) {
> +			memset(irqs, 0, sizeof(*irqs));
> +			irqs->lts = ts;
> +			return;
> +		}
> +	} else {
> +		/*
> +		 * The anomalies must be consecutives, so at this
> +		 * point, we reset the anomalies counter.
> +		 */
> +		irqs->anomalies = 0;
> +	}
> +
> +	/*
> +	 * The interrupt is considered stable enough to try to predict
> +	 * the next event on it.
> +	 */
> +	irqs->valid = 1;
> +
> +	/*
> +	 * Online average algorithm:
> +	 *
> +	 *  new_average = average + ((value - average) / count)
> +	 *
> +	 * The variance computation depends on the new average
> +	 * to be computed here first.
> +	 *
> +	 */
> +	irqs->avg = irqs->avg + div_s64(diff, irqs->count);

Why not computing the average outside this function in a loop of its 
own?  This way you'd have only one division to perform instead of 32.
The above is also skewed as it gives way more weight to the initial 
samples when irqs->count is still low.

Nicolas