Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1311542 > unrolled thread

Re: [RFC PATCH 2/2] sched: idle: IRQ based next prediction for idle period

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC PATCH 2/2] sched: idle: IRQ based next prediction for idle  period Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-18 14:30 +0100
    Re: [RFC PATCH 2/2] sched: idle: IRQ based next prediction for idle  period Thomas Gleixner <tglx@linutronix.de> - 2016-01-20 16:50 +0100
      [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-20 17:10 +0100
        Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Nicolas Pitre <nicolas.pitre@linaro.org> - 2016-01-20 18:50 +0100
          Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Peter Zijlstra <peterz@infradead.org> - 2016-01-20 19:50 +0100
          Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 11:10 +0100
        Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Peter Zijlstra <peterz@infradead.org> - 2016-01-20 20:10 +0100
          Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Nicolas Pitre <nicolas.pitre@linaro.org> - 2016-01-20 20:20 +0100
            Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Peter Zijlstra <peterz@infradead.org> - 2016-01-20 20:40 +0100
        Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Peter Zijlstra <peterz@infradead.org> - 2016-01-20 20:40 +0100
        Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Peter Zijlstra <peterz@infradead.org> - 2016-01-20 20:50 +0100
          Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Nicolas Pitre <nicolas.pitre@linaro.org> - 2016-01-20 21:00 +0100
            Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Peter Zijlstra <peterz@infradead.org> - 2016-01-20 21:30 +0100
        Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Thomas Gleixner <tglx@linutronix.de> - 2016-01-20 21:00 +0100
          Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 15:00 +0100
            Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Thomas Gleixner <tglx@linutronix.de> - 2016-01-21 15:20 +0100
      [RFC V2 0/2] IRQ based next prediction Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-20 17:10 +0100
      [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-20 17:10 +0100
        Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Nicolas Pitre <nicolas.pitre@linaro.org> - 2016-01-20 21:20 +0100
          Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle  period Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 14:10 +0100
      [RFC V2 0/2] IRQ based next prediction Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-20 17:10 +0100
        [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-20 17:10 +0100
          Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Thomas Gleixner <tglx@linutronix.de> - 2016-01-20 19:00 +0100
            Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 10:30 +0100
              Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Thomas Gleixner <tglx@linutronix.de> - 2016-01-21 11:30 +0100
          Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Peter Zijlstra <peterz@infradead.org> - 2016-01-20 20:10 +0100
            Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Thomas Gleixner <tglx@linutronix.de> - 2016-01-20 21:00 +0100
              Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Nicolas Pitre <nicolas.pitre@linaro.org> - 2016-01-20 21:10 +0100
              Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Peter Zijlstra <peterz@infradead.org> - 2016-01-20 21:30 +0100
                Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Thomas Gleixner <tglx@linutronix.de> - 2016-01-20 21:30 +0100
              Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 11:00 +0100
                Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Peter Zijlstra <peterz@infradead.org> - 2016-01-21 11:10 +0100
                  Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 13:40 +0100
                  Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Thomas Gleixner <tglx@linutronix.de> - 2016-01-21 21:30 +0100
                Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Thomas Gleixner <tglx@linutronix.de> - 2016-01-21 15:00 +0100
                  Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 15:20 +0100
                    Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Thomas Gleixner <tglx@linutronix.de> - 2016-01-21 20:00 +0100
                      Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Peter Zijlstra <peterz@infradead.org> - 2016-01-22 11:20 +0100
            Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 10:30 +0100
          Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Peter Zijlstra <peterz@infradead.org> - 2016-01-20 20:30 +0100
            Re: [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-21 11:00 +0100
        [RFC V2 1/2] irq: Add a framework to measure interrupt timings Daniel Lezcano <daniel.lezcano@linaro.org> - 2016-01-20 17:10 +0100

Page 1 of 3  [1] 2 3  Next page →

#1311542 — Re: [RFC PATCH 2/2] sched: idle: IRQ based next prediction for idle period

On 01/08/2016 04:43 PM, Thomas Gleixner wrote:
> On Wed, 6 Jan 2016, Daniel Lezcano wrote:

[ ... ]

>> +	/*
>> +	 * For all the irq already setup, assign the timing callback.
>> +	 * All interrupts with their desc NULL will be discarded.
>> +	 */
>> +	for_each_irq_desc(irq, desc)
>> +		sched_irq_timing_setup(irq, desc->action);
>
> No, no, no. This belongs into the core code register_irq_timings() function
> which installs the handler into the irq descs with the proper protections and
> once it has done that enables the static key.
>
> The above is completely unprotected against interrupts being setup or even
> freed concurrently.
>
> Aside of that, you call that setup function in setup_irq for each action() and
> here you call it only for the first one.

Hi Thomas,

I went through the different comments and almost finished the changes 
but I think the 'register_ops' approach, which happens after some irq 
were setup, introduces some useless complexity and because of the desc 
lock section, the ops can't do memory allocation. Before going further, 
I am wondering if declaring the irq_timings_ops statically (read without 
'register_ops' - hence without a init time dependency) and calling the 
init/free ops from alloc_desc/free_desc wouldn't be cleaner and simpler.

What do you think ?

   -- Daniel


-- 
  <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

[toc] | [next] | [standalone]

#1313309

On Mon, 18 Jan 2016, Daniel Lezcano wrote:
> On 01/08/2016 04:43 PM, Thomas Gleixner wrote:
> > The above is completely unprotected against interrupts being setup or even
> > freed concurrently.
> > 
> > Aside of that, you call that setup function in setup_irq for each action()
> > and
> > here you call it only for the first one.
> 
> I went through the different comments and almost finished the changes but I
> think the 'register_ops' approach, which happens after some irq were setup,
> introduces some useless complexity and because of the desc lock section, the
> ops can't do memory allocation.

You can't protect that with desc_lock. You need to take the sparse_irq_lock,
which is a mutex, to protect the irq desc walk.

> Before going further, I am wondering if declaring the irq_timings_ops
> statically (read without 'register_ops' - hence without a init time
> dependency) and calling the init/free ops from alloc_desc/free_desc wouldn't
> be cleaner and simpler.

Then you don't need those ops at all. You can make it simple function calls,
which get compiled out if that stuff is not enabled.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1313314 — [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

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 <daniel.lezcano@linaro.org>
---
 drivers/cpuidle/Kconfig   |   9 +
 kernel/sched/Makefile     |   1 +
 kernel/sched/idle-sched.c | 529 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 539 insertions(+)
 create mode 100644 kernel/sched/idle-sched.c

diff --git a/drivers/cpuidle/Kconfig b/drivers/cpuidle/Kconfig
index 8c7930b..a606106 100644
--- a/drivers/cpuidle/Kconfig
+++ b/drivers/cpuidle/Kconfig
@@ -25,6 +25,15 @@ config CPU_IDLE_GOV_MENU
 	bool "Menu governor (for tickless system)"
 	default y
 
+config CPU_IDLE_GOV_SCHED
+	bool "Sched idle governor"
+	select IRQ_TIMINGS
+	help
+	  Enables an irq timings tracking mechanism to track the wakeup sources
+	  of the platform.
+
+	  If you are unsure, it is safe to say N.
+
 config DT_IDLE_STATES
 	bool
 
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 6768797..f7d5a35 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -19,3 +19,4 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
 obj-$(CONFIG_SCHEDSTATS) += stats.o
 obj-$(CONFIG_SCHED_DEBUG) += debug.o
 obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o
+obj-$(CONFIG_CPU_IDLE_GOV_SCHED) += idle-sched.o
diff --git a/kernel/sched/idle-sched.c b/kernel/sched/idle-sched.c
new file mode 100644
index 0000000..c2b8568
--- /dev/null
+++ b/kernel/sched/idle-sched.c
@@ -0,0 +1,529 @@
+/*
+ *  Copyright (C) 2016 Linaro Ltd, Daniel Lezcano <daniel.lezcano@linaro.org>
+ *                                 Nicolas Pitre <nicolas.pitre@linaro.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ */
+#include <linux/cpuidle.h>
+#include <linux/interrupt.h>
+#include <linux/irqdesc.h>
+#include <linux/ktime.h>
+#include <linux/slab.h>
+#include <linux/tick.h>
+#include <linux/time64.h>
+
+/*
+ * Define the number of samples over which the average and variance
+ * are computed. A power of 2 is preferred so to let the compiler
+ * optimize divisions by that number with simple arithmetic shifts.
+ */
+#define STATS_NR_VALUES 4
+
+/**
+ * struct stats - internal structure to encapsulate stats informations
+ *
+ * @sum: sum of the values
+ * @values: array of values to do stats on
+ * @w_ptr: current buffer pointer
+ */
+struct stats {
+	u64           sum;                     /* sum of values */
+	u32           values[STATS_NR_VALUES]; /* array of values */
+	unsigned char w_ptr;                   /* current window pointer */
+};
+
+/**
+ * struct wakeup - internal structure describing a source of wakeup
+ *
+ * @stats: the stats structure on the different event intervals
+ * @timestamp: latest update timestamp
+ */
+struct wakeup {
+	struct stats stats;
+	ktime_t timestamp;
+};
+
+/*
+ * Per cpu and irq statistics. Each cpu receives interrupts and those
+ * ones can be distributed following an irq chip specific
+ * algorithm. Random irq distribution is the worst case to predict
+ * interruption behavior but usually that does not happen or could be
+ * fixed from userspace by setting the irq affinity.
+ */
+static DEFINE_PER_CPU(struct wakeup, *wakeups[NR_IRQS]);
+
+static DECLARE_BITMAP(enabled_irq, NR_IRQS);
+
+/**
+ * stats_add - add a new value in the statistic structure
+ *
+ * @s: the statistic structure
+ * @value: the new value to be added
+ *
+ * Adds the value to the array, if the array is full, the oldest value
+ * is replaced.
+ */
+static void stats_add(struct stats *s, u32 value)
+{
+	/*
+	 * This is a circular buffer, so the oldest value is the next
+	 * one in the buffer. Let's compute the next pointer to
+	 * retrieve the oldest value and re-use it to update the w_ptr
+	 * after adding the new value.
+	 */
+	s->w_ptr = (s->w_ptr + 1) % STATS_NR_VALUES;
+
+	/*
+	 * Remove the oldest value from the summing. If this is the
+	 * first time we go through this array slot, the previous
+	 * value will be zero and we won't substract anything from the
+	 * current sum. Hence this code relies on a zero-ed stat
+	 * structure at init time via memset or kzalloc.
+	 */
+	s->sum -= s->values[s->w_ptr];
+	s->values[s->w_ptr] = value;
+
+	/*
+	 * In order to reduce the overhead and to prevent value
+	 * derivation due to the integer computation, we just sum the
+	 * value and do the division when the average and the variance
+	 * are requested.
+	 */
+	s->sum += value;
+}
+
+/**
+ * stats_reset - reset the stats
+ *
+ * @s: the statistic structure
+ *
+ * Reset the statistics and reset the values
+ */
+static inline void stats_reset(struct stats *s)
+{
+	memset(s, 0, sizeof(*s));
+}
+
+/**
+ * stats_mean - compute the average
+ *
+ * @s: the statistics structure
+ *
+ * Returns an u32 corresponding to the mean value, or zero if there is
+ * no data
+ */
+static inline u32 stats_mean(struct stats *s)
+{
+	/*
+	 * gcc is smart enough to convert to a bits shift when the
+	 * divisor is constant and multiple of 2^x.
+	 *
+	 * The number of values could have not reached STATS_NR_VALUES
+	 * yet, but we can consider it acceptable as the situation is
+	 * only at the beginning of the burst of irqs.
+	 */
+	return s->sum / STATS_NR_VALUES;
+}
+
+/**
+ * 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++) {
+		s64 diff = s->values[i] - mean;
+		variance += (u64)diff * diff;
+	}
+
+	return variance / STATS_NR_VALUES;
+}
+
+/**
+ * sched_idle_irq - irq timestamp callback
+ *
+ * @irq: the irq number
+ * @timestamp: when the interrupt occured
+ * @dev_id: device id for shared interrupt (not yet used)
+ *
+ * Interrupt callback called when an interrupt happens. This function
+ * is critical as it is called under an interrupt section: minimum
+ * operations as possible are done here:
+ */
+static void sched_irq_timing_handler(unsigned int irq, ktime_t timestamp, void *dev_id)
+{
+	u32 diff;
+	unsigned int cpu = raw_smp_processor_id();
+	struct wakeup *w = per_cpu(wakeups[irq], cpu);
+
+	/*
+	 * It is the first time the interrupt occurs of the series, we
+	 * can't do any stats as we don't have an interval, just store
+	 * the timestamp and exit.
+	 */
+	if (ktime_equal(w->timestamp, ktime_set(0, 0))) {
+		w->timestamp = timestamp;
+		return;
+	}
+
+	/*
+	 * Microsec resolution is enough for our purpose.
+	 */
+	diff = ktime_us_delta(timestamp, w->timestamp);
+	w->timestamp = 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 (diff > (1 << 20)) {
+		stats_reset(&w->stats);
+		return;
+	}
+
+	stats_add(&w->stats, diff);
+}
+
+static ktime_t next_irq_event(void)
+{
+	unsigned int irq, cpu = raw_smp_processor_id();
+	ktime_t diff, next, min = ktime_set(KTIME_SEC_MAX, 0);
+	ktime_t now = ktime_get();
+	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 = find_next_bit(enabled_irq, NR_IRQS, irq)) {
+
+		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;
+		}
+
+		/*
+		 * 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];
+		if ((u64)((interval - mean) * (interval - mean)) > variance)
+			continue;
+
+		/*
+		 * 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, now);
+
+	/*
+	 * 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_set(KTIME_SEC_MAX, 0);
+
+	return diff;
+}
+
+/**
+ * sched_idle_next_wakeup - Predict the next wakeup on the current cpu
+ *
+ * The next event on the cpu is based on a statistic approach of the
+ * interrupt events and the timer deterministic value. From the timer
+ * or the irqs, we return the one expected to occur first.
+ *
+ * Returns the expected remaining idle time before being woken up by
+ * an interruption.
+ */
+s64 sched_idle_next_wakeup(void)
+{
+	s64 next_timer = ktime_to_us(tick_nohz_get_sleep_length());
+	s64 next_irq = ktime_to_us(next_irq_event());
+
+	return min(next_irq, next_timer);
+}
+
+/**
+ * sched_idle - go to idle for a specified amount of time
+ *
+ * @duration: the idle duration time
+ * @latency: the latency constraint
+ *
+ * Returns 0 on success, < 0 otherwise.
+ */
+int sched_idle(s64 duration, unsigned int latency)
+{
+	struct cpuidle_device *dev = __this_cpu_read(cpuidle_devices);
+	struct cpuidle_driver *drv = cpuidle_get_cpu_driver(dev);
+	struct cpuidle_state_usage *su;
+	struct cpuidle_state *s;
+	int i, ret = 0, index = -1;
+
+	rcu_idle_enter();
+
+	/*
+	 * No cpuidle driver is available, let's use the default arch
+	 * idle function.
+	 */
+	if (cpuidle_not_available(drv, dev))
+		goto default_idle;
+
+	/*
+	 * Find the idle state with the lowest power while satisfying
+	 * our constraints. We will save energy if the duration of the
+	 * idle time is bigger than the target residency which is the
+	 * break even point. The choice will be modulated by the
+	 * latency.
+	 */
+	for (i = 0; i < drv->state_count; i++) {
+
+		s = &drv->states[i];
+
+		su = &dev->states_usage[i];
+
+		if (s->disabled || su->disable)
+			continue;
+		if (s->target_residency > duration)
+			continue;
+		if (s->exit_latency > latency)
+			continue;
+
+		index = i;
+	}
+
+	/*
+	 * The idle task must be scheduled, it is pointless to go to
+	 * idle, just re-enable the interrupt and return.
+	 */
+	if (current_clr_polling_and_test()) {
+		local_irq_enable();
+		goto out;
+	}
+
+	if (index < 0) {
+		/*
+		 * No idle callbacks fulfilled the constraints, jump
+		 * to the default function like there wasn't any
+		 * cpuidle driver.
+		 */
+		goto default_idle;
+	} else {
+		/*
+		 * Enter the idle state previously returned by the
+		 * governor decision.  This function will block until
+		 * an interrupt occurs and will take care of
+		 * re-enabling the local interrupts
+		 */
+		return cpuidle_enter(drv, dev, index);
+	}
+
+default_idle:
+	default_idle_call();
+out:
+	rcu_idle_exit();
+	return ret;
+}
+
+/**
+ * sched_irq_timing_remove - disable the tracking of the specified irq
+ *
+ * Clear the irq table slot to stop tracking the interrupt.
+ *
+ * @irq: the irq number to stop tracking
+ * @dev_id: the device id for shared irq
+ *
+ * This function will remove from the wakeup source prediction table.
+ */
+static void sched_irq_timing_remove(unsigned int irq, void *dev_id)
+{
+	clear_bit(irq, enabled_irq);
+}
+
+/**
+ * sched_irq_timing_setup - enable the tracking of the specified irq
+ *
+ * Function is called with the corresponding irqdesc lock taken. It is
+ * not allowed to do any memory allocation or blocking call. Flag the
+ * irq table slot to be tracked in order to predict the next event.
+ *
+ * @irq: the interrupt numbe to be tracked
+ * @act: the new irq action to be set to this interrupt
+ *
+ * Returns zero on success, < 0 otherwise.
+ */
+static int sched_irq_timing_setup(unsigned int irq, struct irqaction *act)
+{
+	/*
+	 * No interrupt set for this descriptor or related to a timer.
+	 * Timers are deterministic, so no need to try to do any
+	 * prediction on them. No error for both cases, we are just not
+	 * interested.
+	 */
+	if (!(act->flags & __IRQF_TIMER))
+		return 0;
+
+	set_bit(irq, enabled_irq);
+
+	return 0;
+}
+
+/**
+ * sched_irq_timing_free - free memory previously allocated
+ *
+ * @irq: the interrupt number
+ */
+static void sched_irq_timing_free(unsigned int irq)
+{
+	struct wakeup *w;
+	int cpu;
+
+	for_each_possible_cpu(cpu) {
+
+		w = per_cpu(wakeups[irq], cpu);
+		if (!w)
+			continue;
+
+		per_cpu(wakeups[irq], cpu) = NULL;
+		kfree(w);
+	}
+}
+
+/**
+ * sched_irq_timing_alloc - allocates memory for irq tracking
+ *
+ * Allocates the memory to track the specified irq.
+ *
+ * @irq: the interrupt number
+ *
+ * Returns 0 on success, -ENOMEM on error.
+ */
+static int sched_irq_timing_alloc(unsigned int irq)
+{
+	struct wakeup *w;
+	int cpu, ret = -ENOMEM;
+
+	/*
+	 * Allocates the wakeup structure and the stats structure. As
+	 * the interrupt can occur on any cpu, allocate the wakeup
+	 * structure per cpu basis.
+	 */
+	for_each_possible_cpu(cpu) {
+
+		w = kzalloc(sizeof(*w), GFP_KERNEL);
+		if (!w)
+			goto out;
+
+		per_cpu(wakeups[irq], cpu) = w;
+	}
+
+	ret = 0;
+out:
+	if (ret)
+		sched_irq_timing_free(irq);
+
+	return ret;
+}
+
+static struct irqtimings_ops irqt_ops = {
+	.alloc   = sched_irq_timing_alloc,
+	.free    = sched_irq_timing_free,
+	.setup   = sched_irq_timing_setup,
+	.remove  = sched_irq_timing_remove,
+	.handler = sched_irq_timing_handler,
+};
+
+DECLARE_IRQ_TIMINGS(&irqt_ops);
-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1313409 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, 20 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 <daniel.lezcano@linaro.org>
> ---
>  drivers/cpuidle/Kconfig   |   9 +
>  kernel/sched/Makefile     |   1 +
>  kernel/sched/idle-sched.c | 529 ++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 539 insertions(+)
>  create mode 100644 kernel/sched/idle-sched.c
> 
> diff --git a/drivers/cpuidle/Kconfig b/drivers/cpuidle/Kconfig
> index 8c7930b..a606106 100644
> --- a/drivers/cpuidle/Kconfig
> +++ b/drivers/cpuidle/Kconfig
> @@ -25,6 +25,15 @@ config CPU_IDLE_GOV_MENU
>  	bool "Menu governor (for tickless system)"
>  	default y
>  
> +config CPU_IDLE_GOV_SCHED
> +	bool "Sched idle governor"
> +	select IRQ_TIMINGS
> +	help
> +	  Enables an irq timings tracking mechanism to track the wakeup sources
> +	  of the platform.
> +
> +	  If you are unsure, it is safe to say N.
> +
>  config DT_IDLE_STATES
>  	bool
>  
> diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
> index 6768797..f7d5a35 100644
> --- a/kernel/sched/Makefile
> +++ b/kernel/sched/Makefile
> @@ -19,3 +19,4 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
>  obj-$(CONFIG_SCHEDSTATS) += stats.o
>  obj-$(CONFIG_SCHED_DEBUG) += debug.o
>  obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o
> +obj-$(CONFIG_CPU_IDLE_GOV_SCHED) += idle-sched.o
> diff --git a/kernel/sched/idle-sched.c b/kernel/sched/idle-sched.c
> new file mode 100644
> index 0000000..c2b8568
> --- /dev/null
> +++ b/kernel/sched/idle-sched.c
> @@ -0,0 +1,529 @@
> +/*
> + *  Copyright (C) 2016 Linaro Ltd, Daniel Lezcano <daniel.lezcano@linaro.org>
> + *                                 Nicolas Pitre <nicolas.pitre@linaro.org>
> + *
> + * This program is free software; you can redistribute it and/or modify
> + * it under the terms of the GNU General Public License version 2 as
> + * published by the Free Software Foundation.
> + *
> + */
> +#include <linux/cpuidle.h>
> +#include <linux/interrupt.h>
> +#include <linux/irqdesc.h>
> +#include <linux/ktime.h>
> +#include <linux/slab.h>
> +#include <linux/tick.h>
> +#include <linux/time64.h>
> +
> +/*
> + * Define the number of samples over which the average and variance
> + * are computed. A power of 2 is preferred so to let the compiler
> + * optimize divisions by that number with simple arithmetic shifts.
> + */
> +#define STATS_NR_VALUES 4
> +
> +/**
> + * struct stats - internal structure to encapsulate stats informations
> + *
> + * @sum: sum of the values
> + * @values: array of values to do stats on
> + * @w_ptr: current buffer pointer
> + */
> +struct stats {
> +	u64           sum;                     /* sum of values */
> +	u32           values[STATS_NR_VALUES]; /* array of values */
> +	unsigned char w_ptr;                   /* current window pointer */

Why did you change this from an unsigned int?

This won't provide any memory space saving given that the structure has 
to be padded up to the next 64-bit boundary.

> +};
> +
> +/**
> + * struct wakeup - internal structure describing a source of wakeup
> + *
> + * @stats: the stats structure on the different event intervals
> + * @timestamp: latest update timestamp
> + */
> +struct wakeup {
> +	struct stats stats;
> +	ktime_t timestamp;
> +};
> +
> +/*
> + * Per cpu and irq statistics. Each cpu receives interrupts and those
> + * ones can be distributed following an irq chip specific
> + * algorithm. Random irq distribution is the worst case to predict
> + * interruption behavior but usually that does not happen or could be
> + * fixed from userspace by setting the irq affinity.
> + */
> +static DEFINE_PER_CPU(struct wakeup, *wakeups[NR_IRQS]);
> +
> +static DECLARE_BITMAP(enabled_irq, NR_IRQS);
> +
> +/**
> + * stats_add - add a new value in the statistic structure
> + *
> + * @s: the statistic structure
> + * @value: the new value to be added
> + *
> + * Adds the value to the array, if the array is full, the oldest value
> + * is replaced.
> + */
> +static void stats_add(struct stats *s, u32 value)
> +{
> +	/*
> +	 * This is a circular buffer, so the oldest value is the next
> +	 * one in the buffer. Let's compute the next pointer to
> +	 * retrieve the oldest value and re-use it to update the w_ptr
> +	 * after adding the new value.
> +	 */
> +	s->w_ptr = (s->w_ptr + 1) % STATS_NR_VALUES;
> +
> +	/*
> +	 * Remove the oldest value from the summing. If this is the
> +	 * first time we go through this array slot, the previous
> +	 * value will be zero and we won't substract anything from the
> +	 * current sum. Hence this code relies on a zero-ed stat
> +	 * structure at init time via memset or kzalloc.
> +	 */
> +	s->sum -= s->values[s->w_ptr];
> +	s->values[s->w_ptr] = value;
> +
> +	/*
> +	 * In order to reduce the overhead and to prevent value
> +	 * derivation due to the integer computation, we just sum the
> +	 * value and do the division when the average and the variance
> +	 * are requested.
> +	 */
> +	s->sum += value;
> +}
> +
> +/**
> + * stats_reset - reset the stats
> + *
> + * @s: the statistic structure
> + *
> + * Reset the statistics and reset the values
> + */
> +static inline void stats_reset(struct stats *s)
> +{
> +	memset(s, 0, sizeof(*s));
> +}
> +
> +/**
> + * stats_mean - compute the average
> + *
> + * @s: the statistics structure
> + *
> + * Returns an u32 corresponding to the mean value, or zero if there is
> + * no data
> + */
> +static inline u32 stats_mean(struct stats *s)
> +{
> +	/*
> +	 * gcc is smart enough to convert to a bits shift when the
> +	 * divisor is constant and multiple of 2^x.
> +	 *
> +	 * The number of values could have not reached STATS_NR_VALUES
> +	 * yet, but we can consider it acceptable as the situation is
> +	 * only at the beginning of the burst of irqs.
> +	 */
> +	return s->sum / STATS_NR_VALUES;
> +}
> +
> +/**
> + * 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++) {
> +		s64 diff = s->values[i] - mean;
> +		variance += (u64)diff * diff;
> +	}

This is completely wrong.  Even more wrong than it used to be.  I must
have expressed myself badly about this last time.

To avoid any confusion, here's what the code should be:

	int i;
	u64 variance = 0;

	for (i = 0; i < STATS_NR_VALUES; i++) {
		s32 diff = s->values[i] - mean;
		variance += (s64)diff * diff;
	}

	[...]

> +
> +	return variance / STATS_NR_VALUES;
> +}
> +
> +/**
> + * sched_idle_irq - irq timestamp callback
> + *
> + * @irq: the irq number
> + * @timestamp: when the interrupt occured
> + * @dev_id: device id for shared interrupt (not yet used)
> + *
> + * Interrupt callback called when an interrupt happens. This function
> + * is critical as it is called under an interrupt section: minimum
> + * operations as possible are done here:
> + */
> +static void sched_irq_timing_handler(unsigned int irq, ktime_t timestamp, void *dev_id)
> +{
> +	u32 diff;
> +	unsigned int cpu = raw_smp_processor_id();
> +	struct wakeup *w = per_cpu(wakeups[irq], cpu);
> +
> +	/*
> +	 * It is the first time the interrupt occurs of the series, we
> +	 * can't do any stats as we don't have an interval, just store
> +	 * the timestamp and exit.
> +	 */
> +	if (ktime_equal(w->timestamp, ktime_set(0, 0))) {
> +		w->timestamp = timestamp;
> +		return;
> +	}
> +
> +	/*
> +	 * Microsec resolution is enough for our purpose.
> +	 */
> +	diff = ktime_us_delta(timestamp, w->timestamp);
> +	w->timestamp = 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 (diff > (1 << 20)) {

You could use the USEC_PER_SEC constant here. It is already widely used 
and would make the code even more obvious.

> +		stats_reset(&w->stats);
> +		return;
> +	}
> +
> +	stats_add(&w->stats, diff);
> +}
> +
> +static ktime_t next_irq_event(void)
> +{
> +	unsigned int irq, cpu = raw_smp_processor_id();
> +	ktime_t diff, next, min = ktime_set(KTIME_SEC_MAX, 0);
> +	ktime_t now = ktime_get();
> +	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 = find_next_bit(enabled_irq, NR_IRQS, irq)) {
> +
> +		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.
> +		 */

This comment is wrong.  It is relevant in sched_irq_timing_handler() but 
not here.  Instead this should be something like:

		/*
		 * This interrupt last triggered more than a second ago.
		 * It is definitely not predictable for our purpose anymore.
		 */

> +		if (unlikely(ktime_after(diff, ktime_set(1, 0)))) {
> +			stats_reset(&w->stats);
> +			continue;
> +		}
> +
> +		/*
> +		 * 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];
> +		if ((u64)((interval - mean) * (interval - mean)) > variance)

s/u64/s64/ please.

> +			continue;
> +
> +		/*
> +		 * 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, now);
> +
> +	/*
> +	 * 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_set(KTIME_SEC_MAX, 0);
> +
> +	return diff;
> +}
> +
> +/**
> + * sched_idle_next_wakeup - Predict the next wakeup on the current cpu
> + *
> + * The next event on the cpu is based on a statistic approach of the
> + * interrupt events and the timer deterministic value. From the timer
> + * or the irqs, we return the one expected to occur first.
> + *
> + * Returns the expected remaining idle time before being woken up by
> + * an interruption.
> + */
> +s64 sched_idle_next_wakeup(void)
> +{
> +	s64 next_timer = ktime_to_us(tick_nohz_get_sleep_length());
> +	s64 next_irq = ktime_to_us(next_irq_event());
> +
> +	return min(next_irq, next_timer);
> +}
> +
> +/**
> + * sched_idle - go to idle for a specified amount of time
> + *
> + * @duration: the idle duration time
> + * @latency: the latency constraint
> + *
> + * Returns 0 on success, < 0 otherwise.
> + */
> +int sched_idle(s64 duration, unsigned int latency)
> +{
> +	struct cpuidle_device *dev = __this_cpu_read(cpuidle_devices);
> +	struct cpuidle_driver *drv = cpuidle_get_cpu_driver(dev);
> +	struct cpuidle_state_usage *su;
> +	struct cpuidle_state *s;
> +	int i, ret = 0, index = -1;
> +
> +	rcu_idle_enter();
> +
> +	/*
> +	 * No cpuidle driver is available, let's use the default arch
> +	 * idle function.
> +	 */
> +	if (cpuidle_not_available(drv, dev))
> +		goto default_idle;
> +
> +	/*
> +	 * Find the idle state with the lowest power while satisfying
> +	 * our constraints. We will save energy if the duration of the
> +	 * idle time is bigger than the target residency which is the
> +	 * break even point. The choice will be modulated by the
> +	 * latency.
> +	 */
> +	for (i = 0; i < drv->state_count; i++) {
> +
> +		s = &drv->states[i];
> +
> +		su = &dev->states_usage[i];
> +
> +		if (s->disabled || su->disable)
> +			continue;
> +		if (s->target_residency > duration)
> +			continue;
> +		if (s->exit_latency > latency)
> +			continue;
> +
> +		index = i;
> +	}
> +
> +	/*
> +	 * The idle task must be scheduled, it is pointless to go to
> +	 * idle, just re-enable the interrupt and return.
> +	 */
> +	if (current_clr_polling_and_test()) {
> +		local_irq_enable();
> +		goto out;
> +	}
> +
> +	if (index < 0) {
> +		/*
> +		 * No idle callbacks fulfilled the constraints, jump
> +		 * to the default function like there wasn't any
> +		 * cpuidle driver.
> +		 */
> +		goto default_idle;
> +	} else {
> +		/*
> +		 * Enter the idle state previously returned by the
> +		 * governor decision.  This function will block until
> +		 * an interrupt occurs and will take care of
> +		 * re-enabling the local interrupts
> +		 */
> +		return cpuidle_enter(drv, dev, index);
> +	}
> +
> +default_idle:
> +	default_idle_call();
> +out:
> +	rcu_idle_exit();
> +	return ret;
> +}
> +
> +/**
> + * sched_irq_timing_remove - disable the tracking of the specified irq
> + *
> + * Clear the irq table slot to stop tracking the interrupt.
> + *
> + * @irq: the irq number to stop tracking
> + * @dev_id: the device id for shared irq
> + *
> + * This function will remove from the wakeup source prediction table.
> + */
> +static void sched_irq_timing_remove(unsigned int irq, void *dev_id)
> +{
> +	clear_bit(irq, enabled_irq);
> +}
> +
> +/**
> + * sched_irq_timing_setup - enable the tracking of the specified irq
> + *
> + * Function is called with the corresponding irqdesc lock taken. It is
> + * not allowed to do any memory allocation or blocking call. Flag the
> + * irq table slot to be tracked in order to predict the next event.
> + *
> + * @irq: the interrupt numbe to be tracked
> + * @act: the new irq action to be set to this interrupt
> + *
> + * Returns zero on success, < 0 otherwise.
> + */
> +static int sched_irq_timing_setup(unsigned int irq, struct irqaction *act)
> +{
> +	/*
> +	 * No interrupt set for this descriptor or related to a timer.
> +	 * Timers are deterministic, so no need to try to do any
> +	 * prediction on them. No error for both cases, we are just not
> +	 * interested.
> +	 */
> +	if (!(act->flags & __IRQF_TIMER))
> +		return 0;
> +
> +	set_bit(irq, enabled_irq);
> +
> +	return 0;
> +}
> +
> +/**
> + * sched_irq_timing_free - free memory previously allocated
> + *
> + * @irq: the interrupt number
> + */
> +static void sched_irq_timing_free(unsigned int irq)
> +{
> +	struct wakeup *w;
> +	int cpu;
> +
> +	for_each_possible_cpu(cpu) {
> +
> +		w = per_cpu(wakeups[irq], cpu);
> +		if (!w)
> +			continue;
> +
> +		per_cpu(wakeups[irq], cpu) = NULL;
> +		kfree(w);
> +	}
> +}
> +
> +/**
> + * sched_irq_timing_alloc - allocates memory for irq tracking
> + *
> + * Allocates the memory to track the specified irq.
> + *
> + * @irq: the interrupt number
> + *
> + * Returns 0 on success, -ENOMEM on error.
> + */
> +static int sched_irq_timing_alloc(unsigned int irq)
> +{
> +	struct wakeup *w;
> +	int cpu, ret = -ENOMEM;
> +
> +	/*
> +	 * Allocates the wakeup structure and the stats structure. As
> +	 * the interrupt can occur on any cpu, allocate the wakeup
> +	 * structure per cpu basis.
> +	 */
> +	for_each_possible_cpu(cpu) {
> +
> +		w = kzalloc(sizeof(*w), GFP_KERNEL);
> +		if (!w)
> +			goto out;
> +
> +		per_cpu(wakeups[irq], cpu) = w;
> +	}
> +
> +	ret = 0;
> +out:
> +	if (ret)
> +		sched_irq_timing_free(irq);
> +
> +	return ret;
> +}
> +
> +static struct irqtimings_ops irqt_ops = {
> +	.alloc   = sched_irq_timing_alloc,
> +	.free    = sched_irq_timing_free,
> +	.setup   = sched_irq_timing_setup,
> +	.remove  = sched_irq_timing_remove,
> +	.handler = sched_irq_timing_handler,
> +};
> +
> +DECLARE_IRQ_TIMINGS(&irqt_ops);
> -- 
> 1.9.1
> 
> 

[toc] | [prev] | [next] | [standalone]

#1313441 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, Jan 20, 2016 at 12:46:48PM -0500, Nicolas Pitre wrote:
> > +struct stats {
> > +	u64           sum;                     /* sum of values */
> > +	u32           values[STATS_NR_VALUES]; /* array of values */
> > +	unsigned char w_ptr;                   /* current window pointer */
> 
> Why did you change this from an unsigned int?
> 
> This won't provide any memory space saving given that the structure has 
> to be padded up to the next 64-bit boundary.

Not to mention that loading bytes is more expensive on many archs
compared to full words.

Also, its not a pointer, its an index.

So:	unsigned int w_idx;

[toc] | [prev] | [next] | [standalone]

#1314066 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

Hi Nico,


On 01/20/2016 06:46 PM, Nicolas Pitre wrote:
> On Wed, 20 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 <daniel.lezcano@linaro.org>
>> ---

[ ... ]

>> +struct stats {
>> +	u64           sum;                     /* sum of values */
>> +	u32           values[STATS_NR_VALUES]; /* array of values */
>> +	unsigned char w_ptr;                   /* current window pointer */
>
> Why did you change this from an unsigned int?
>
> This won't provide any memory space saving given that the structure has
> to be padded up to the next 64-bit boundary.

Ok, I will change it back to unsigned int.

[ ... ]

>> +	for (i = 0; i < STATS_NR_VALUES; i++) {
>> +		s64 diff = s->values[i] - mean;
>> +		variance += (u64)diff * diff;
>> +	}
>
> This is completely wrong.  Even more wrong than it used to be.  I must
> have expressed myself badly about this last time.
>
> To avoid any confusion, here's what the code should be:
>
> 	int i;
> 	u64 variance = 0;
>
> 	for (i = 0; i < STATS_NR_VALUES; i++) {
> 		s32 diff = s->values[i] - mean;
> 		variance += (s64)diff * diff;
> 	}
>
> 	[...]

Aah, ok :)

[ ... ]

>> +	if (diff > (1 << 20)) {
>
> You could use the USEC_PER_SEC constant here. It is already widely used
> and would make the code even more obvious.

Indeed.

[ ... ]

>> +		/*
>> +		 * 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.
>> +		 */
>
> This comment is wrong.  It is relevant in sched_irq_timing_handler() but
> not here.  Instead this should be something like:
>
> 		/*
> 		 * This interrupt last triggered more than a second ago.
> 		 * It is definitely not predictable for our purpose anymore.
> 		 */

Ok.

[ ... ]

>> +		interval = w->stats.values[w->stats.w_ptr];
>> +		if ((u64)((interval - mean) * (interval - mean)) > variance)
>
> s/u64/s64/ please.

Noted.

Thanks Nico for the review.


   -- Daniel

-- 
  <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

[toc] | [prev] | [next] | [standalone]

#1313452 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, Jan 20, 2016 at 05:00:33PM +0100, Daniel Lezcano wrote:
> +static void sched_irq_timing_handler(unsigned int irq, ktime_t timestamp, void *dev_id)
> +{
> +	u32 diff;
> +	unsigned int cpu = raw_smp_processor_id();
> +	struct wakeup *w = per_cpu(wakeups[irq], cpu);
> +
> +	/*
> +	 * It is the first time the interrupt occurs of the series, we
> +	 * can't do any stats as we don't have an interval, just store
> +	 * the timestamp and exit.
> +	 */
> +	if (ktime_equal(w->timestamp, ktime_set(0, 0))) {
> +		w->timestamp = timestamp;
> +		return;
> +	}
> +
> +	/*
> +	 * Microsec resolution is enough for our purpose.
> +	 */

It is also a friggin pointless /1000. The cpuidle code also loves to do
this, and its silly, u64 add/sub are _way_ cheaper than u64 / 1000.

> +	diff = ktime_us_delta(timestamp, w->timestamp);
> +	w->timestamp = 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 (diff > (1 << 20)) {
> +		stats_reset(&w->stats);
> +		return;
> +	}
> +
> +	stats_add(&w->stats, diff);
> +}
> +
> +static ktime_t next_irq_event(void)
> +{
> +	unsigned int irq, cpu = raw_smp_processor_id();
> +	ktime_t diff, next, min = ktime_set(KTIME_SEC_MAX, 0);
> +	ktime_t now = ktime_get();

Why !?! do we care about NTP correct timestamps?

ktime_get() can be horrendously slow, don't use it for statistics.

> +		next = ktime_add_us(w->timestamp, stats_mean(&w->stats));
> +	s64 next_timer = ktime_to_us(tick_nohz_get_sleep_length());
> +	s64 next_irq = ktime_to_us(next_irq_event());

more nonsense, just say no.

[toc] | [prev] | [next] | [standalone]

#1313456 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, 20 Jan 2016, Peter Zijlstra wrote:

> On Wed, Jan 20, 2016 at 05:00:33PM +0100, Daniel Lezcano wrote:
> > +static void sched_irq_timing_handler(unsigned int irq, ktime_t timestamp, void *dev_id)
> > +{
> > +	u32 diff;
> > +	unsigned int cpu = raw_smp_processor_id();
> > +	struct wakeup *w = per_cpu(wakeups[irq], cpu);
> > +
> > +	/*
> > +	 * It is the first time the interrupt occurs of the series, we
> > +	 * can't do any stats as we don't have an interval, just store
> > +	 * the timestamp and exit.
> > +	 */
> > +	if (ktime_equal(w->timestamp, ktime_set(0, 0))) {
> > +		w->timestamp = timestamp;
> > +		return;
> > +	}
> > +
> > +	/*
> > +	 * Microsec resolution is enough for our purpose.
> > +	 */
> 
> It is also a friggin pointless /1000. The cpuidle code also loves to do
> this, and its silly, u64 add/sub are _way_ cheaper than u64 / 1000.

For the purpose of this code, nanoseconds simply provides too many bits 
for what we care.  Computing the variance implies squared values.

*However* we can simply do diff = (timestamp - w->timestamp) >> 10 
instead.  No need to have an exact microsecs base.

> > +	ktime_t now = ktime_get();
> 
> Why !?! do we care about NTP correct timestamps?

Not at all. Using sched_clock() instead would be more than good enough 
indeed.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1313465 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, Jan 20, 2016 at 02:17:57PM -0500, Nicolas Pitre wrote:
> > It is also a friggin pointless /1000. The cpuidle code also loves to do
> > this, and its silly, u64 add/sub are _way_ cheaper than u64 / 1000.
> 
> For the purpose of this code, nanoseconds simply provides too many bits 
> for what we care.  Computing the variance implies squared values.
> 
> *However* we can simply do diff = (timestamp - w->timestamp) >> 10 
> instead.  No need to have an exact microsecs base.

Right, you could also reduce bits at the variance computation, but yes.

[toc] | [prev] | [next] | [standalone]

#1313461 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, Jan 20, 2016 at 05:00:33PM +0100, Daniel Lezcano wrote:
> +		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];
> +		if ((u64)((interval - mean) * (interval - mean)) > variance)
> +			continue;
> +

Cute :-)

You could consider putting a simple 3 point median filter in front of
stat_add() to get rid of the worst input noise.

(I know, improving all this was a point for later)

[toc] | [prev] | [next] | [standalone]

#1313471 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, Jan 20, 2016 at 05:00:33PM +0100, Daniel Lezcano wrote:
> +static inline u32 stats_mean(struct stats *s)
> +{
> +	/*
> +	 * gcc is smart enough to convert to a bits shift when the
> +	 * divisor is constant and multiple of 2^x.
> +	 *
> +	 * The number of values could have not reached STATS_NR_VALUES
> +	 * yet, but we can consider it acceptable as the situation is
> +	 * only at the beginning of the burst of irqs.
> +	 */
> +	return s->sum / STATS_NR_VALUES;
> +}

Note that ->sum is u64, so you're very prone to truncation.

[toc] | [prev] | [next] | [standalone]

#1313480 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, 20 Jan 2016, Peter Zijlstra wrote:

> On Wed, Jan 20, 2016 at 05:00:33PM +0100, Daniel Lezcano wrote:
> > +static inline u32 stats_mean(struct stats *s)
> > +{
> > +	/*
> > +	 * gcc is smart enough to convert to a bits shift when the
> > +	 * divisor is constant and multiple of 2^x.
> > +	 *
> > +	 * The number of values could have not reached STATS_NR_VALUES
> > +	 * yet, but we can consider it acceptable as the situation is
> > +	 * only at the beginning of the burst of irqs.
> > +	 */
> > +	return s->sum / STATS_NR_VALUES;
> > +}
> 
> Note that ->sum is u64, so you're very prone to truncation.

It won't.  It is the sum of u32 values, so the mean of those values 
can't exceed 32 bits.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1313502 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, Jan 20, 2016 at 02:57:07PM -0500, Nicolas Pitre wrote:
> On Wed, 20 Jan 2016, Peter Zijlstra wrote:
> 
> > On Wed, Jan 20, 2016 at 05:00:33PM +0100, Daniel Lezcano wrote:
> > > +static inline u32 stats_mean(struct stats *s)
> > > +{
> > > +	/*
> > > +	 * gcc is smart enough to convert to a bits shift when the
> > > +	 * divisor is constant and multiple of 2^x.
> > > +	 *
> > > +	 * The number of values could have not reached STATS_NR_VALUES
> > > +	 * yet, but we can consider it acceptable as the situation is
> > > +	 * only at the beginning of the burst of irqs.
> > > +	 */
> > > +	return s->sum / STATS_NR_VALUES;
> > > +}
> > 
> > Note that ->sum is u64, so you're very prone to truncation.
> 
> It won't.  It is the sum of u32 values, so the mean of those values 
> can't exceed 32 bits.

Ah indeed!

[toc] | [prev] | [next] | [standalone]

#1313479 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, 20 Jan 2016, Daniel Lezcano wrote:
> +/*
> + * Per cpu and irq statistics. Each cpu receives interrupts and those
> + * ones can be distributed following an irq chip specific
> + * algorithm. Random irq distribution is the worst case to predict
> + * interruption behavior but usually that does not happen or could be
> + * fixed from userspace by setting the irq affinity.
> + */
> +static DEFINE_PER_CPU(struct wakeup, *wakeups[NR_IRQS]);

That does not work with sparse irqs. With sparse irqs NR_IRQS can be very
small and the core can expand up to NR_IRQS + 8196

> +static DECLARE_BITMAP(enabled_irq, NR_IRQS);

Ditto.

> +static void stats_add(struct stats *s, u32 value)
> +{
> +	/*
> +	 * This is a circular buffer, so the oldest value is the next
> +	 * one in the buffer. Let's compute the next pointer to
> +	 * retrieve the oldest value and re-use it to update the w_ptr
> +	 * after adding the new value.
> +	 */
> +	s->w_ptr = (s->w_ptr + 1) % STATS_NR_VALUES;

I rather have that an explicit '& STATS_NR_MASK' here and some enforcement
that STATS_NR_VALUES is a power of two.

> +/**
> + * stats_mean - compute the average
> + *
> + * @s: the statistics structure
> + *
> + * Returns an u32 corresponding to the mean value, or zero if there is
> + * no data
> + */
> +static inline u32 stats_mean(struct stats *s)
> +{
> +	/*
> +	 * gcc is smart enough to convert to a bits shift when the
> +	 * divisor is constant and multiple of 2^x.

Instead of adding those comments everywhere, you just could use a shift value,
which naturally enforces the power of 2 of STATS_NR_VALUES

> +	 *
> +	 * The number of values could have not reached STATS_NR_VALUES
> +	 * yet, but we can consider it acceptable as the situation is
> +	 * only at the beginning of the burst of irqs.
> +	 */
> +	return s->sum / STATS_NR_VALUES;
> +}

> +/**
> + * sched_idle_irq - irq timestamp callback

There is a way to actually compile KernelDoc ....

> + *
> + * @irq: the irq number
> + * @timestamp: when the interrupt occured
> + * @dev_id: device id for shared interrupt (not yet used)

What is it going to be used for?

> +	/*
> +	 * Microsec resolution is enough for our purpose.
> +	 */
> +	diff = ktime_us_delta(timestamp, w->timestamp);

You force a division by 1000 here. Storing the nsec values is way cheaper. If
you really need to make it smaller for computational reasons, then use a shift
value. There is no requirement for this to be precise.

> +static ktime_t next_irq_event(void)
> +{
> +	unsigned int irq, cpu = raw_smp_processor_id();
> +	ktime_t diff, next, min = ktime_set(KTIME_SEC_MAX, 0);
> +	ktime_t now = ktime_get();
> +	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 = find_next_bit(enabled_irq, NR_IRQS, irq)) {

Again. This cannot work. 

1) NR_IRQS is the wrong thing to look at.

2) It's racy against a concurrent teardown of interrupts.

> +		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;

That comment makes no sense whatsoever. You look at the data which you
allocated from __setup_irq(). So how is that related?

> +/**
> + * sched_irq_timing_remove - disable the tracking of the specified irq
> + *
> + * Clear the irq table slot to stop tracking the interrupt.
> + *
> + * @irq: the irq number to stop tracking
> + * @dev_id: the device id for shared irq
> + *
> + * This function will remove from the wakeup source prediction table.
> + */
> +static void sched_irq_timing_remove(unsigned int irq, void *dev_id)
> +{
> +	clear_bit(irq, enabled_irq);
> +}
> +
> +/**
> + * sched_irq_timing_setup - enable the tracking of the specified irq
> + *
> + * Function is called with the corresponding irqdesc lock taken. It is
> + * not allowed to do any memory allocation or blocking call. Flag the
> + * irq table slot to be tracked in order to predict the next event.
> + *
> + * @irq: the interrupt numbe to be tracked
> + * @act: the new irq action to be set to this interrupt
> + *
> + * Returns zero on success, < 0 otherwise.
> + */
> +static int sched_irq_timing_setup(unsigned int irq, struct irqaction *act)
> +{
> +	/*
> +	 * No interrupt set for this descriptor or related to a timer.
> +	 * Timers are deterministic, so no need to try to do any
> +	 * prediction on them. No error for both cases, we are just not
> +	 * interested.
> +	 */
> +	if (!(act->flags & __IRQF_TIMER))
> +		return 0;

Well, you do not make any predicitions, but you allocate the data and do
sampling ...

> +
> +	set_bit(irq, enabled_irq);
> +
> +	return 0;
> +}

These two are required for what? The callsite is broken as well. You call
setup() for the first action of an irq and remove() for any action which gets
torn down. That does not make any sense at all.

> +/**
> + * sched_irq_timing_free - free memory previously allocated
> + *
> + * @irq: the interrupt number
> + */
> +static void sched_irq_timing_free(unsigned int irq)
> +{
> +	struct wakeup *w;
> +	int cpu;
> +
> +	for_each_possible_cpu(cpu) {
> +
> +		w = per_cpu(wakeups[irq], cpu);
> +		if (!w)
> +			continue;
> +
> +		per_cpu(wakeups[irq], cpu) = NULL;
> +		kfree(w);

Your simple array does not work. You need a radix_tree to handle SPARSE_IRQ
and you need proper protection against teardown.

So we can avoid all that stuff and simply stick that data into irqdesc and let
the core handle it. That allows us to use proper percpu allocations and avoid
that for_each_possible_cpu() sillyness.

That leaves the iterator, but that's a solvable problem. We simply can have an
iterator function in the irq core, which gives you the next sample
structure. Something like this:

struct irqtiming_sample *irqtiming_get_next(int *irq)
{
	struct irq_desc *desc;
	int next;

	/* Do a racy lookup of the next allocated irq */
	next = irq_get_next_irq(*irq);
	if (next >= nr_irqs)
	   	 return NULL;

	*irq = next + 1;

	/* Now lookup the descriptor. It's RCU protected. */
	desc = irq_to_desc(next);
	if (!desc || !desc->irqtimings || !(desc->istate & IRQS_TIMING))
	   	 return NULL;

	return this_cpu_ptr(&desc->irqtimings);
}

And that needs to be called rcu protected;

    	 next = 0;
    	 rcu_read_lock();
	 sample = irqtiming_get_next(&next);
	 while (sample) {
	       ....
	       sample = irqtiming_get_next(&next);
	 }
    	 rcu_read_unlock();

So the interrupt part becomes:

         if (desc->istate & IRQS_TIMING)
	       	 irqtimings_handle(__this_cpu_ptr(&desc->irqtimings));

So now for the allocation/free of that data. We simply allocate/free it along
with the irq descriptor. That IRQS_TIMING bit gets set in __setup_irq() except
for timer interrupts. That's simple and avoid _all_ the issues.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1314206 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On 01/20/2016 08:49 PM, Thomas Gleixner wrote:

[ ... ]

Thanks for all your comments. I agree with them.

One question below.

>> +static void sched_irq_timing_free(unsigned int irq)
>> +{
>> +	struct wakeup *w;
>> +	int cpu;
>> +
>> +	for_each_possible_cpu(cpu) {
>> +
>> +		w = per_cpu(wakeups[irq], cpu);
>> +		if (!w)
>> +			continue;
>> +
>> +		per_cpu(wakeups[irq], cpu) = NULL;
>> +		kfree(w);
>
> Your simple array does not work. You need a radix_tree to handle SPARSE_IRQ
> and you need proper protection against teardown.
>
> So we can avoid all that stuff and simply stick that data into irqdesc and let
> the core handle it. That allows us to use proper percpu allocations and avoid
> that for_each_possible_cpu() sillyness.
>
> That leaves the iterator, but that's a solvable problem. We simply can have an
> iterator function in the irq core, which gives you the next sample
> structure. Something like this:
>
> struct irqtiming_sample *irqtiming_get_next(int *irq)
> {
> 	struct irq_desc *desc;
> 	int next;
>
> 	/* Do a racy lookup of the next allocated irq */
> 	next = irq_get_next_irq(*irq);
> 	if (next >= nr_irqs)
> 	   	 return NULL;
>
> 	*irq = next + 1;
>
> 	/* Now lookup the descriptor. It's RCU protected. */
> 	desc = irq_to_desc(next);
> 	if (!desc || !desc->irqtimings || !(desc->istate & IRQS_TIMING))
> 	   	 return NULL;
>
> 	return this_cpu_ptr(&desc->irqtimings);
> }
>
> And that needs to be called rcu protected;
>
>      	 next = 0;
>      	 rcu_read_lock();
> 	 sample = irqtiming_get_next(&next);
> 	 while (sample) {
> 	       ....
> 	       sample = irqtiming_get_next(&next);
> 	 }
>      	 rcu_read_unlock();
>
> So the interrupt part becomes:
>
>           if (desc->istate & IRQS_TIMING)
> 	       	 irqtimings_handle(__this_cpu_ptr(&desc->irqtimings));
>
> So now for the allocation/free of that data. We simply allocate/free it along
> with the irq descriptor. That IRQS_TIMING bit gets set in __setup_irq() except
> for timer interrupts. That's simple and avoid _all_ the issues.

Indeed, making this as part of the irq code makes everything much more 
simple and self contained. For the shared interrupts, shouldn't we put 
the timings samples into the irqaction structure instead of the irqdesc 
structure ?

eg.

#define IRQT_MAX_VALUES 4

struct irqaction {
	...
#ifdef CONFIG_IRQ_TIMINGS
	u32 irqtimings_samples[IRQT_MAX_VALUES];
#endif
	...
};

So we don't have to deal with the allocation/free under locks. The 
drawback is the array won't be used in the case of the timers.

Does it make sense ?

Thanks Thomas for your help, your time and your suggestions.




-- 
  <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

[toc] | [prev] | [next] | [standalone]

#1314220 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Thu, 21 Jan 2016, Daniel Lezcano wrote:
> On 01/20/2016 08:49 PM, Thomas Gleixner wrote:
> > So now for the allocation/free of that data. We simply allocate/free it
> > along
> > with the irq descriptor. That IRQS_TIMING bit gets set in __setup_irq()
> > except
> > for timer interrupts. That's simple and avoid _all_ the issues.
> 
> Indeed, making this as part of the irq code makes everything much more simple
> and self contained. For the shared interrupts, shouldn't we put the timings
> samples into the irqaction structure instead of the irqdesc structure ?
> 
> eg.
> 
> #define IRQT_MAX_VALUES 4
> 
> struct irqaction {
> 	...
> #ifdef CONFIG_IRQ_TIMINGS
> 	u32 irqtimings_samples[IRQT_MAX_VALUES];
> #endif
> 	...
> };
> 
> So we don't have to deal with the allocation/free under locks. The drawback is
> the array won't be used in the case of the timers.

I still have to ask the question whether a per device information is useful at
all. I don't see the value, but I might miss something.

Thanks,

	tglx

[toc] | [prev] | [next] | [standalone]

#1313316 — [RFC V2 0/2] IRQ based next prediction

The current approach to select an idle state is based on the idle period
statistics computation.

Useless to say this approach satisfied everyone as a solution to find the
best trade-off between the performances and the energy saving via the menu
governor.

However, the kernel is evolving to act pro-actively regarding the energy
constraints with the scheduler and the different power management subsystems
are not collaborating with the scheduler as the conductor of the decisions,
they all act independently.

The cpuidle governors are based on idle period statistics, without knowledge
of what woke up the cpu. In these sources of wakes up, the IPI are of course
accounted (as well as the timers irq) which results in doing statistics on
the scheduler behavior too. It is no sense to let the scheduler to take a
decision based on a next prediction of its own decisions.

In order to integrate the cpuidle framework into the scheduler, we have to
radically change the approach by clearly identifying what is causing a wake
up and how it behaves.

This serie inverts the logic.

Instead of tracking the idle durations and do statistics on them, these
patches track the interrupt individually and try to predict the next interrupt.

By combining the interrupts' next event on a single CPU, we can predict the
next event for the CPU, hence predict how long we will be sleeping when
entering idle.

The IPI and timer interrupts are not taken into account.

The first patch provides a callback to be registered in the irq subsystem
and to be called when an interrupt is handled with a timestamp.

The second patch uses the callback provided by the patch above to compute
the delta and store it in a circular buffer. It is per cpu, the callback
implements minimal operations as it is in an interrupt context.

When we the cpu enters idle, it asks for the expected sleep time. Then the
expected minimum sleep length for all interrupts is used and compared to
the timer sleep length, again the minimum is taken and gives the expected
sleep time.

The statistics are very trivial and could be improved later but this first
step shows we have a nice overall improvement in SMP. In UP the menu governor
is a bit better which may indicate the next prediction computation could be
improved but confirms removing the IPI from the equation increase the
accuracy.

Changelog:
	V2:
	   - Changed the register_ops approach for the irq subsystem
           - Fixed Nicolas's comments

Daniel Lezcano (2):
  irq: Add a framework to measure interrupt timings
  sched: idle: IRQ based next prediction for idle period

 drivers/cpuidle/Kconfig    |   9 +
 include/linux/interrupt.h  |  26 +++
 include/linux/irqhandler.h |   1 +
 kernel/irq/Kconfig         |   4 +
 kernel/irq/handle.c        |   1 +
 kernel/irq/internals.h     |  43 ++++
 kernel/irq/irqdesc.c       |   6 +
 kernel/irq/manage.c        |  10 +-
 kernel/sched/Makefile      |   1 +
 kernel/sched/idle-sched.c  | 529 +++++++++++++++++++++++++++++++++++++++++++++
 10 files changed, 629 insertions(+), 1 deletion(-)
 create mode 100644 kernel/sched/idle-sched.c

-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1313317 — [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

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 <daniel.lezcano@linaro.org>
---
 drivers/cpuidle/Kconfig   |   9 +
 kernel/sched/Makefile     |   1 +
 kernel/sched/idle-sched.c | 529 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 539 insertions(+)
 create mode 100644 kernel/sched/idle-sched.c

diff --git a/drivers/cpuidle/Kconfig b/drivers/cpuidle/Kconfig
index 8c7930b..a606106 100644
--- a/drivers/cpuidle/Kconfig
+++ b/drivers/cpuidle/Kconfig
@@ -25,6 +25,15 @@ config CPU_IDLE_GOV_MENU
 	bool "Menu governor (for tickless system)"
 	default y
 
+config CPU_IDLE_GOV_SCHED
+	bool "Sched idle governor"
+	select IRQ_TIMINGS
+	help
+	  Enables an irq timings tracking mechanism to track the wakeup sources
+	  of the platform.
+
+	  If you are unsure, it is safe to say N.
+
 config DT_IDLE_STATES
 	bool
 
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index 6768797..f7d5a35 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -19,3 +19,4 @@ obj-$(CONFIG_SCHED_AUTOGROUP) += auto_group.o
 obj-$(CONFIG_SCHEDSTATS) += stats.o
 obj-$(CONFIG_SCHED_DEBUG) += debug.o
 obj-$(CONFIG_CGROUP_CPUACCT) += cpuacct.o
+obj-$(CONFIG_CPU_IDLE_GOV_SCHED) += idle-sched.o
diff --git a/kernel/sched/idle-sched.c b/kernel/sched/idle-sched.c
new file mode 100644
index 0000000..c2b8568
--- /dev/null
+++ b/kernel/sched/idle-sched.c
@@ -0,0 +1,529 @@
+/*
+ *  Copyright (C) 2016 Linaro Ltd, Daniel Lezcano <daniel.lezcano@linaro.org>
+ *                                 Nicolas Pitre <nicolas.pitre@linaro.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ *
+ */
+#include <linux/cpuidle.h>
+#include <linux/interrupt.h>
+#include <linux/irqdesc.h>
+#include <linux/ktime.h>
+#include <linux/slab.h>
+#include <linux/tick.h>
+#include <linux/time64.h>
+
+/*
+ * Define the number of samples over which the average and variance
+ * are computed. A power of 2 is preferred so to let the compiler
+ * optimize divisions by that number with simple arithmetic shifts.
+ */
+#define STATS_NR_VALUES 4
+
+/**
+ * struct stats - internal structure to encapsulate stats informations
+ *
+ * @sum: sum of the values
+ * @values: array of values to do stats on
+ * @w_ptr: current buffer pointer
+ */
+struct stats {
+	u64           sum;                     /* sum of values */
+	u32           values[STATS_NR_VALUES]; /* array of values */
+	unsigned char w_ptr;                   /* current window pointer */
+};
+
+/**
+ * struct wakeup - internal structure describing a source of wakeup
+ *
+ * @stats: the stats structure on the different event intervals
+ * @timestamp: latest update timestamp
+ */
+struct wakeup {
+	struct stats stats;
+	ktime_t timestamp;
+};
+
+/*
+ * Per cpu and irq statistics. Each cpu receives interrupts and those
+ * ones can be distributed following an irq chip specific
+ * algorithm. Random irq distribution is the worst case to predict
+ * interruption behavior but usually that does not happen or could be
+ * fixed from userspace by setting the irq affinity.
+ */
+static DEFINE_PER_CPU(struct wakeup, *wakeups[NR_IRQS]);
+
+static DECLARE_BITMAP(enabled_irq, NR_IRQS);
+
+/**
+ * stats_add - add a new value in the statistic structure
+ *
+ * @s: the statistic structure
+ * @value: the new value to be added
+ *
+ * Adds the value to the array, if the array is full, the oldest value
+ * is replaced.
+ */
+static void stats_add(struct stats *s, u32 value)
+{
+	/*
+	 * This is a circular buffer, so the oldest value is the next
+	 * one in the buffer. Let's compute the next pointer to
+	 * retrieve the oldest value and re-use it to update the w_ptr
+	 * after adding the new value.
+	 */
+	s->w_ptr = (s->w_ptr + 1) % STATS_NR_VALUES;
+
+	/*
+	 * Remove the oldest value from the summing. If this is the
+	 * first time we go through this array slot, the previous
+	 * value will be zero and we won't substract anything from the
+	 * current sum. Hence this code relies on a zero-ed stat
+	 * structure at init time via memset or kzalloc.
+	 */
+	s->sum -= s->values[s->w_ptr];
+	s->values[s->w_ptr] = value;
+
+	/*
+	 * In order to reduce the overhead and to prevent value
+	 * derivation due to the integer computation, we just sum the
+	 * value and do the division when the average and the variance
+	 * are requested.
+	 */
+	s->sum += value;
+}
+
+/**
+ * stats_reset - reset the stats
+ *
+ * @s: the statistic structure
+ *
+ * Reset the statistics and reset the values
+ */
+static inline void stats_reset(struct stats *s)
+{
+	memset(s, 0, sizeof(*s));
+}
+
+/**
+ * stats_mean - compute the average
+ *
+ * @s: the statistics structure
+ *
+ * Returns an u32 corresponding to the mean value, or zero if there is
+ * no data
+ */
+static inline u32 stats_mean(struct stats *s)
+{
+	/*
+	 * gcc is smart enough to convert to a bits shift when the
+	 * divisor is constant and multiple of 2^x.
+	 *
+	 * The number of values could have not reached STATS_NR_VALUES
+	 * yet, but we can consider it acceptable as the situation is
+	 * only at the beginning of the burst of irqs.
+	 */
+	return s->sum / STATS_NR_VALUES;
+}
+
+/**
+ * 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++) {
+		s64 diff = s->values[i] - mean;
+		variance += (u64)diff * diff;
+	}
+
+	return variance / STATS_NR_VALUES;
+}
+
+/**
+ * sched_idle_irq - irq timestamp callback
+ *
+ * @irq: the irq number
+ * @timestamp: when the interrupt occured
+ * @dev_id: device id for shared interrupt (not yet used)
+ *
+ * Interrupt callback called when an interrupt happens. This function
+ * is critical as it is called under an interrupt section: minimum
+ * operations as possible are done here:
+ */
+static void sched_irq_timing_handler(unsigned int irq, ktime_t timestamp, void *dev_id)
+{
+	u32 diff;
+	unsigned int cpu = raw_smp_processor_id();
+	struct wakeup *w = per_cpu(wakeups[irq], cpu);
+
+	/*
+	 * It is the first time the interrupt occurs of the series, we
+	 * can't do any stats as we don't have an interval, just store
+	 * the timestamp and exit.
+	 */
+	if (ktime_equal(w->timestamp, ktime_set(0, 0))) {
+		w->timestamp = timestamp;
+		return;
+	}
+
+	/*
+	 * Microsec resolution is enough for our purpose.
+	 */
+	diff = ktime_us_delta(timestamp, w->timestamp);
+	w->timestamp = 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 (diff > (1 << 20)) {
+		stats_reset(&w->stats);
+		return;
+	}
+
+	stats_add(&w->stats, diff);
+}
+
+static ktime_t next_irq_event(void)
+{
+	unsigned int irq, cpu = raw_smp_processor_id();
+	ktime_t diff, next, min = ktime_set(KTIME_SEC_MAX, 0);
+	ktime_t now = ktime_get();
+	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 = find_next_bit(enabled_irq, NR_IRQS, irq)) {
+
+		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;
+		}
+
+		/*
+		 * 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];
+		if ((u64)((interval - mean) * (interval - mean)) > variance)
+			continue;
+
+		/*
+		 * 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, now);
+
+	/*
+	 * 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_set(KTIME_SEC_MAX, 0);
+
+	return diff;
+}
+
+/**
+ * sched_idle_next_wakeup - Predict the next wakeup on the current cpu
+ *
+ * The next event on the cpu is based on a statistic approach of the
+ * interrupt events and the timer deterministic value. From the timer
+ * or the irqs, we return the one expected to occur first.
+ *
+ * Returns the expected remaining idle time before being woken up by
+ * an interruption.
+ */
+s64 sched_idle_next_wakeup(void)
+{
+	s64 next_timer = ktime_to_us(tick_nohz_get_sleep_length());
+	s64 next_irq = ktime_to_us(next_irq_event());
+
+	return min(next_irq, next_timer);
+}
+
+/**
+ * sched_idle - go to idle for a specified amount of time
+ *
+ * @duration: the idle duration time
+ * @latency: the latency constraint
+ *
+ * Returns 0 on success, < 0 otherwise.
+ */
+int sched_idle(s64 duration, unsigned int latency)
+{
+	struct cpuidle_device *dev = __this_cpu_read(cpuidle_devices);
+	struct cpuidle_driver *drv = cpuidle_get_cpu_driver(dev);
+	struct cpuidle_state_usage *su;
+	struct cpuidle_state *s;
+	int i, ret = 0, index = -1;
+
+	rcu_idle_enter();
+
+	/*
+	 * No cpuidle driver is available, let's use the default arch
+	 * idle function.
+	 */
+	if (cpuidle_not_available(drv, dev))
+		goto default_idle;
+
+	/*
+	 * Find the idle state with the lowest power while satisfying
+	 * our constraints. We will save energy if the duration of the
+	 * idle time is bigger than the target residency which is the
+	 * break even point. The choice will be modulated by the
+	 * latency.
+	 */
+	for (i = 0; i < drv->state_count; i++) {
+
+		s = &drv->states[i];
+
+		su = &dev->states_usage[i];
+
+		if (s->disabled || su->disable)
+			continue;
+		if (s->target_residency > duration)
+			continue;
+		if (s->exit_latency > latency)
+			continue;
+
+		index = i;
+	}
+
+	/*
+	 * The idle task must be scheduled, it is pointless to go to
+	 * idle, just re-enable the interrupt and return.
+	 */
+	if (current_clr_polling_and_test()) {
+		local_irq_enable();
+		goto out;
+	}
+
+	if (index < 0) {
+		/*
+		 * No idle callbacks fulfilled the constraints, jump
+		 * to the default function like there wasn't any
+		 * cpuidle driver.
+		 */
+		goto default_idle;
+	} else {
+		/*
+		 * Enter the idle state previously returned by the
+		 * governor decision.  This function will block until
+		 * an interrupt occurs and will take care of
+		 * re-enabling the local interrupts
+		 */
+		return cpuidle_enter(drv, dev, index);
+	}
+
+default_idle:
+	default_idle_call();
+out:
+	rcu_idle_exit();
+	return ret;
+}
+
+/**
+ * sched_irq_timing_remove - disable the tracking of the specified irq
+ *
+ * Clear the irq table slot to stop tracking the interrupt.
+ *
+ * @irq: the irq number to stop tracking
+ * @dev_id: the device id for shared irq
+ *
+ * This function will remove from the wakeup source prediction table.
+ */
+static void sched_irq_timing_remove(unsigned int irq, void *dev_id)
+{
+	clear_bit(irq, enabled_irq);
+}
+
+/**
+ * sched_irq_timing_setup - enable the tracking of the specified irq
+ *
+ * Function is called with the corresponding irqdesc lock taken. It is
+ * not allowed to do any memory allocation or blocking call. Flag the
+ * irq table slot to be tracked in order to predict the next event.
+ *
+ * @irq: the interrupt numbe to be tracked
+ * @act: the new irq action to be set to this interrupt
+ *
+ * Returns zero on success, < 0 otherwise.
+ */
+static int sched_irq_timing_setup(unsigned int irq, struct irqaction *act)
+{
+	/*
+	 * No interrupt set for this descriptor or related to a timer.
+	 * Timers are deterministic, so no need to try to do any
+	 * prediction on them. No error for both cases, we are just not
+	 * interested.
+	 */
+	if (!(act->flags & __IRQF_TIMER))
+		return 0;
+
+	set_bit(irq, enabled_irq);
+
+	return 0;
+}
+
+/**
+ * sched_irq_timing_free - free memory previously allocated
+ *
+ * @irq: the interrupt number
+ */
+static void sched_irq_timing_free(unsigned int irq)
+{
+	struct wakeup *w;
+	int cpu;
+
+	for_each_possible_cpu(cpu) {
+
+		w = per_cpu(wakeups[irq], cpu);
+		if (!w)
+			continue;
+
+		per_cpu(wakeups[irq], cpu) = NULL;
+		kfree(w);
+	}
+}
+
+/**
+ * sched_irq_timing_alloc - allocates memory for irq tracking
+ *
+ * Allocates the memory to track the specified irq.
+ *
+ * @irq: the interrupt number
+ *
+ * Returns 0 on success, -ENOMEM on error.
+ */
+static int sched_irq_timing_alloc(unsigned int irq)
+{
+	struct wakeup *w;
+	int cpu, ret = -ENOMEM;
+
+	/*
+	 * Allocates the wakeup structure and the stats structure. As
+	 * the interrupt can occur on any cpu, allocate the wakeup
+	 * structure per cpu basis.
+	 */
+	for_each_possible_cpu(cpu) {
+
+		w = kzalloc(sizeof(*w), GFP_KERNEL);
+		if (!w)
+			goto out;
+
+		per_cpu(wakeups[irq], cpu) = w;
+	}
+
+	ret = 0;
+out:
+	if (ret)
+		sched_irq_timing_free(irq);
+
+	return ret;
+}
+
+static struct irqtimings_ops irqt_ops = {
+	.alloc   = sched_irq_timing_alloc,
+	.free    = sched_irq_timing_free,
+	.setup   = sched_irq_timing_setup,
+	.remove  = sched_irq_timing_remove,
+	.handler = sched_irq_timing_handler,
+};
+
+DECLARE_IRQ_TIMINGS(&irqt_ops);
-- 
1.9.1

[toc] | [prev] | [next] | [standalone]

#1313496 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On Wed, 20 Jan 2016, Daniel Lezcano wrote:
[...]

One more comment:

> +		/*
> +		 * 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];
> +		if ((u64)((interval - mean) * (interval - mean)) > variance)
> +			continue;
> +
> +		/*
> +		 * 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));

You don't need to call stats_mean() again as you have it in the 'mean' 
variable already.


Nicolas

[toc] | [prev] | [next] | [standalone]

#1314191 — Re: [RFC V2 2/2] sched: idle: IRQ based next prediction for idle period

On 01/20/2016 09:14 PM, Nicolas Pitre wrote:
> On Wed, 20 Jan 2016, Daniel Lezcano wrote:
> [...]
>
> One more comment:
>
>> +		/*
>> +		 * 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];
>> +		if ((u64)((interval - mean) * (interval - mean)) > variance)
>> +			continue;
>> +
>> +		/*
>> +		 * 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));
>
> You don't need to call stats_mean() again as you have it in the 'mean'
> variable already.

Good point.


-- 
  <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

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | linux.kernel

csiph-web