From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753479AbcAGPnF (ORCPT ); Thu, 7 Jan 2016 10:43:05 -0500 Received: from mail-wm0-f49.google.com ([74.125.82.49]:35422 "EHLO mail-wm0-f49.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752062AbcAGPnD (ORCPT ); Thu, 7 Jan 2016 10:43:03 -0500 Subject: Re: [RFC PATCH 2/2] sched: idle: IRQ based next prediction for idle period To: Nicolas Pitre References: <1452093774-17831-1-git-send-email-daniel.lezcano@linaro.org> <1452093774-17831-3-git-send-email-daniel.lezcano@linaro.org> Cc: tglx@linutronix.de, peterz@infradead.org, rafael@kernel.org, linux-pm@vger.kernel.org, linux-kernel@vger.kernel.org, vincent.guittot@linaro.org From: Daniel Lezcano Message-ID: <568E8782.9020401@linaro.org> Date: Thu, 7 Jan 2016 16:42:58 +0100 User-Agent: Mozilla/5.0 (X11; Linux i686; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 01/06/2016 06:40 PM, Nicolas Pitre wrote: > On Wed, 6 Jan 2016, Daniel Lezcano wrote: > >> Many IRQs are quiet most of the time, or they tend to come in bursts of >> fairly equal time intervals within each burst. It is therefore possible >> to detect those IRQs with stable intervals and guestimate when the next >> IRQ event is most likely to happen. >> >> Examples of such IRQs may include audio related IRQs where the FIFO size >> and/or DMA descriptor size with the sample rate create stable intervals, >> block devices during large data transfers, etc. Even network streaming >> of multimedia content creates patterns of periodic network interface IRQs >> in some cases. >> >> This patch adds code to track the mean interval and variance for each IRQ >> over a window of time intervals between IRQ events. Those statistics can >> be used to assist cpuidle in selecting the most appropriate sleep state >> by predicting the most likely time for the next interrupt. >> >> Because the stats are gathered in interrupt context, the core computation >> is as light as possible. >> >> Signed-off-by: Daniel Lezcano > > There are still a few problems with this patch. > > Please see comments below. [ ... ] >> +/** >> + * stats_variance - compute the variance >> + * >> + * @s: the statistic structure >> + * >> + * Returns an u64 corresponding to the variance, or zero if there is >> + * no data >> + */ >> +static u64 stats_variance(struct stats *s, u32 mean) >> +{ >> + int i; >> + u64 variance = 0; >> + >> + /* >> + * The variance is the sum of the squared difference to the >> + * average divided by the number of elements. >> + */ >> + for (i = 0; i < STATS_NR_VALUES; i++) { >> + s32 diff = s->values[i] - mean; >> + variance += (u64)diff * diff; > > Strictly speaking, diff should be casted to s64 as it is a signed value > that may actually be negative. Because of the strange C type promotion > rules, the generated code appears correct (at least on ARM), but it > would be clearer to use s64 anyway. I don't get the connection in your explanation of why it should be a s64. It is already a signed s32, s->values[] are s32 and mean is u32. What would be the benefit to convert diff to s64 ? > The product will end up being positive in all cases of course so > variance may remain as a u64. > [ ... ] >> +static ktime_t next_irq_event(void) >> +{ >> + unsigned int irq, cpu = raw_smp_processor_id(); >> + ktime_t diff, next, min = { .tv64 = KTIME_MAX }; > > To avoid exposing the ktime_t definition, you should use > ktime_set(KTIME_SEC_MAX, 0) instead of { .tv64 = KTIME_MAX }. Ok. >> + struct wakeup *w; >> + u32 interval, mean; >> + u64 variance; >> + >> + /* >> + * Lookup the interrupt array for this cpu and search for the >> + * earlier expected interruption. >> + */ >> + for (irq = 0; irq < NR_IRQS; irq++) { >> + >> + ktime_t now = ktime_get(); > > ktime_get() is potentially non-trivial. It should be plenty good enough > to call it only once outside the loop. Ok. >> + w = per_cpu(wakeups[irq], cpu); >> + >> + /* >> + * The interrupt was not setup as a source of a wakeup >> + * or the wakeup source is not considered at this >> + * moment stable enough to do a prediction. >> + */ >> + if (!w) >> + continue; >> + >> + /* >> + * No statistics available yet. >> + */ >> + if (ktime_equal(w->timestamp, ktime_set(0, 0))) >> + continue; >> + >> + diff = ktime_sub(now, w->timestamp); >> + >> + /* >> + * There is no point attempting predictions on interrupts more >> + * than 1 second apart. This has no benefit for sleep state >> + * selection and increases the risk of overflowing our variance >> + * computation. Reset all stats in that case. >> + */ >> + if (unlikely(ktime_after(diff, ktime_set(1, 0)))) { >> + stats_reset(&w->stats); >> + continue; >> + } > > The above is wrong. It is not computing the interval between successive > interruts but rather the interval between the last interrupt occurrence > and the present time (i.e. when we're about to go idle). This won't > prevent interrupt intervals greater than one second from being summed > and potentially overflowing the variance if this code is executed less > than a second after one such IRQ interval. This test should rather be > performed in sched_idle_irq(). Ok, I will move it. >> + * If the mean value is null, just ignore this wakeup >> + * source. >> + */ >> + mean = stats_mean(&w->stats); >> + if (!mean) >> + continue; >> + >> + variance = stats_variance(&w->stats, mean); >> + /* >> + * We want to check the last interval is: >> + * >> + * mean - stddev < interval < mean + stddev >> + * >> + * That simplifies to: >> + * >> + * -stddev < interval - mean < stddev >> + * >> + * abs(interval - mean) < stddev >> + * >> + * The standard deviation is the sqrt of the variance: >> + * >> + * abs(interval - mean) < sqrt(variance) >> + * >> + * and we want to prevent to do an sqrt, so we square >> + * the equation: >> + * >> + * (interval - mean)^2 < variance >> + * >> + * So if the latest value of the stats complies with >> + * this condition, then the wakeup source is >> + * considered predictable and can be used to predict >> + * the next event. >> + */ >> + interval = w->stats.values[(w->stats.w_ptr + 1) % STATS_NR_VALUES]; > > But here (w->stats.w_ptr + 1) % STATS_NR_VALUES does not point at the > last interval. It rather points at the second oldest. > To make things simpler, you should rather pre-increment the pointer > before updating the array in stats_add(), and here the value you want > will directly be accessible with w->stats.values[w->stats.w_ptr]. Yeah, there is a glitch here. I will look at it. >> + if ((u64)((interval - mean) * (interval - mean)) > variance) >> + continue; > > Same comment as in stats_variance(): this should be s64. > >> + /* >> + * Let's compute the next event: the wakeup source is >> + * considered predictable, we add the average interval >> + * time added to the latest interruption event time. >> + */ >> + next = ktime_add_us(w->timestamp, stats_mean(&w->stats)); >> + >> + /* >> + * If the interrupt is supposed to happen before the >> + * minimum time, then it becomes the minimum. >> + */ >> + if (ktime_before(next, min)) >> + min = next; >> + } >> + >> + /* >> + * At this point, we have our prediction but the caller is >> + * expecting the remaining time before the next event, so >> + * compute the expected sleep length. >> + */ >> + diff = ktime_sub(min, ktime_get()); > > You should use the variable 'now' rather than asking for the current > time again. Yep. >> + /* >> + * The result could be negative for different reasons: >> + * - the prediction is incorrect >> + * - the prediction was too near now and expired while we were >> + * in this function >> + * >> + * In both cases, we return KTIME_MAX as a failure to do a >> + * prediction >> + */ >> + if (ktime_compare(diff, ktime_set(0, 0)) <= 0) >> + return (ktime_t){ .tv64 = KTIME_MAX }; > > See my comment about ktime_t internals at the beginning of this > function. Ok. Thanks for the review. -- Daniel -- Linaro.org │ Open source software for ARM SoCs Follow Linaro: Facebook | Twitter | Blog