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]

Message-ID: <20170324141437.GD24630@mai>
Date:   Fri, 24 Mar 2017 15:14:37 +0100
From:   Daniel Lezcano <daniel.lezcano@...aro.org>
To:     Nicolas Pitre <nicolas.pitre@...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, Mar 23, 2017 at 03:40:39PM -0400, Nicolas Pitre wrote:
> 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.

There is no general rule about that. Depending on the load of the system, the
cpu number, etc ... they can be a few or a the max or in between.

> > +	 * 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.

Actually, stabilizing the math in this function has been the major effort with
this patch.

Changing the above won't save us anything because we have to compute the
variance each time in order to put apart the new value or not.

I understand a div64 can be scary but, I would like to put in place the
framework. Then we can think about optimizing the code.

-- 

 <http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs

Follow Linaro:  <http://www.facebook.com/pages/Linaro> Facebook |
<http://twitter.com/#!/linaroorg> Twitter |
<http://www.linaro.org/linaro-blog/> Blog