2009-09-11 15:36:48

by Arjan van de Ven

[permalink] [raw]
Subject: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

From: Arjan van de Ven <[email protected]>
Subject: [PATCH] cpuidle: A new variant of the menu governor

This patch adds a new idle governor which balances power savings,
energy efficiency and performance impact.

The reason for a reworked governor is that there have been
serious performance issues reported with the existing code
on Nehalem server systems.

To show this I'm sure Andrew wants to see benchmark results:
(benchmark is "fio", "no cstates" is using "idle=poll")

no cstates current linux new algorithm
1 disk 107 Mb/s 85 Mb/s 105 Mb/s
2 disks 215 Mb/s 123 Mb/s 209 Mb/s
12 disks 590 Mb/s 320 Mb/s 585 Mb/s

In various power benchmark measurements, no degredation was found
by our measurement&diagnostics team. Obviously a bit more power was
used in the "fio" benchmark, due to the much higher performance.

The integration plan for this is to first add the new governor,
but for one kernel generation, leave the old menu governor in place
so that it's possible to separate out behavior from this governor
versus other things in diagnostics. If no issues are found,
I'll remove the old governor in the kernel cycle after that.

While it would be a novel idea to describe the new algorithm in this
commit message, I cheaped out and described it in comments in the
code instead.

Signed-off-by: Arjan van de Ven <[email protected]>
---
drivers/cpuidle/Kconfig | 5 +
drivers/cpuidle/governors/Makefile | 2 +
drivers/cpuidle/governors/menu-tng.c | 334 ++++++++++++++++++++++++++++++++++
include/linux/sched.h | 4 +
kernel/sched.c | 15 ++
5 files changed, 360 insertions(+), 0 deletions(-)
create mode 100644 drivers/cpuidle/governors/menu-tng.c

diff --git a/drivers/cpuidle/Kconfig b/drivers/cpuidle/Kconfig
index 7dbc4a8..3a19d8c 100644
--- a/drivers/cpuidle/Kconfig
+++ b/drivers/cpuidle/Kconfig
@@ -18,3 +18,8 @@ config CPU_IDLE_GOV_MENU
bool
depends on CPU_IDLE && NO_HZ
default y
+
+config CPU_IDLE_GOV_MENU_TNG
+ bool
+ depends on CPU_IDLE && NO_HZ
+ default y
diff --git a/drivers/cpuidle/governors/Makefile b/drivers/cpuidle/governors/Makefile
index 1b51272..be4f8e3 100644
--- a/drivers/cpuidle/governors/Makefile
+++ b/drivers/cpuidle/governors/Makefile
@@ -4,3 +4,5 @@

obj-$(CONFIG_CPU_IDLE_GOV_LADDER) += ladder.o
obj-$(CONFIG_CPU_IDLE_GOV_MENU) += menu.o
+obj-$(CONFIG_CPU_IDLE_GOV_MENU_TNG) += menu-tng.o
+
diff --git a/drivers/cpuidle/governors/menu-tng.c b/drivers/cpuidle/governors/menu-tng.c
new file mode 100644
index 0000000..6e76c56
--- /dev/null
+++ b/drivers/cpuidle/governors/menu-tng.c
@@ -0,0 +1,334 @@
+/*
+ * menu-tng.c - the menu idle governor
+ *
+ * Copyright (C) 2009 Intel Corporation
+ * Author:
+ * Arjan van de Ven <[email protected]>
+ *
+ * Based on framework code from
+ * Copyright (C) 2006-2007 Adam Belay <[email protected]>
+ *
+ * This code is licenced under the GPL version 2 as described
+ * in the COPYING file that acompanies the Linux Kernel.
+ */
+
+#include <linux/kernel.h>
+#include <linux/cpuidle.h>
+#include <linux/pm_qos_params.h>
+#include <linux/time.h>
+#include <linux/ktime.h>
+#include <linux/hrtimer.h>
+#include <linux/tick.h>
+#include <linux/sched.h>
+
+
+#define BUCKETS 12
+#define RESOLUTION 1024
+#define DECAY 4
+#define MAX_INTERESTING 50000
+
+/*
+ * Concepts and ideas behind the menu-tng governor
+ *
+ * For the menu-tng governor, there are 3 decision factors for picking a C
+ * state:
+ * 1) Energie break even point
+ * 2) Performance impact
+ * 3) Latency tolerance (from pmqos infrastructure)
+ * These these three factors are treated independently.
+ *
+ * Energy break even point
+ * -----------------------
+ * C state entry and exit have an energy cost, and a certain amount of time in
+ * the C state is required to actually break even on this cost. CPUIDLE
+ * provides us this duration in the "target_residency" field. So all that we
+ * need is a good prediction of how long we'll be idle. Like the traditional
+ * menu governor, we start with the actual known "next timer event" time.
+ *
+ * Since there are other source of wakeups (interrupts for example) than
+ * the next timer event, this estimation is rather optimistic. To get a
+ * more realistic estimate, a correction factor is applied to the estimate,
+ * that is based on historic behavior. For example, if in the past the actual
+ * duration always was 50% of the next timer tick, the correction factor will
+ * be 0.5.
+ *
+ * menu-tng uses a running average for this correction factor, however it uses a
+ * set of factors, not just a single factor. This stems from the realization
+ * that the ratio is dependent on the order of magnitude of the expected
+ * duration; if we expect 500 milliseconds of idle time the likelyhood of
+ * getting an interrupt very early is much higher than if we expect 50 micro
+ * seconds of idle time. A second independent factor that has big impact on
+ * the actual factor is if there is (disk) IO outstanding or not.
+ * (as a special twist, we consider every sleep longer than 50 milliseconds
+ * as perfect; there is no power gains for sleeping longer than this)
+ *
+ * For these two reasons we keep an array of 12 independent factors, that gets
+ * indexed based on the magnitude of the expected duration as well as the
+ * "is IO outstanding" property.
+ *
+ * Limiting Performance Impact
+ * ---------------------------
+ * C states, especially those with large exit latencies, can have a real
+ * noticable impact on workloads, which is not acceptable for most sysadmins,
+ * and in addition, less performance has a power price of its own.
+ *
+ * As a general rule of thumb, menu-tng assumes that the following heuristic
+ * holds:
+ * The busier the system, the less impact of C states is acceptable
+ *
+ * This rule-of-thumb is implemented using a performance-multiplier:
+ * If the exit latency times the performance multiplier is longer than
+ * the predicted duration, the C state is not considered a candidate
+ * for selection due to a too high performance impact. So the higher
+ * this multiplier is, the longer we need to be idle to pick a deep C
+ * state, and thus the less likely a busy CPU will hit such a deep
+ * C state.
+ *
+ * Two factors are used in determing this multiplier:
+ * a value of 10 is added for each point of "per cpu load average" we have.
+ * a value of 5 points is added for each process that is waiting for
+ * IO on this CPU.
+ * (these values are experimentally determined)
+ *
+ * The load average factor gives a longer term (few seconds) input to the
+ * decision, while the iowait value gives a cpu local instantanious input.
+ * The iowait factor may look low, but realize that this is also already
+ * represented in the system load average.
+ *
+ */
+
+struct menu_device {
+ int last_state_idx;
+
+ unsigned int expected_us;
+ u64 predicted_us;
+ unsigned int measured_us;
+ unsigned int exit_us;
+ unsigned int bucket;
+ u64 correction_factor[BUCKETS];
+};
+
+
+#define LOAD_INT(x) ((x) >> FSHIFT)
+#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
+
+static int get_loadavg(void)
+{
+ unsigned long this = this_cpu_load();
+
+
+ return LOAD_INT(this) * 10 + LOAD_FRAC(this) / 10;
+}
+
+static inline int which_bucket(unsigned int duration)
+{
+ int bucket = 0;
+
+ /*
+ * We keep two groups of stats; one with no
+ * IO pending, one without.
+ * This allows us to calculate
+ * E(duration)|iowait
+ */
+ if (nr_iowait_cpu())
+ bucket = BUCKETS/2;
+
+ if (duration < 10)
+ return bucket;
+ if (duration < 100)
+ return bucket + 1;
+ if (duration < 1000)
+ return bucket + 2;
+ if (duration < 10000)
+ return bucket + 3;
+ if (duration < 100000)
+ return bucket + 4;
+ return bucket + 5;
+}
+
+/*
+ * Return a multiplier for the exit latency that is intended
+ * to take performance requirements into account.
+ * The more performance critical we estimate the system
+ * to be, the higher this multiplier, and thus the higher
+ * the barrier to go to an expensive C state.
+ */
+static inline int performance_multiplier(void)
+{
+ int mult = 1;
+
+ /* for higher loadavg, we are more reluctant */
+
+ mult += 2 * get_loadavg();
+
+ /* for IO wait tasks (per cpu!) we add 5x each */
+ mult += 10 * nr_iowait_cpu();
+
+ return mult;
+}
+
+static DEFINE_PER_CPU(struct menu_device, menu_devices);
+
+/**
+ * menu_select - selects the next idle state to enter
+ * @dev: the CPU
+ */
+static int menu_select(struct cpuidle_device *dev)
+{
+ struct menu_device *data = &__get_cpu_var(menu_devices);
+ int latency_req = pm_qos_requirement(PM_QOS_CPU_DMA_LATENCY);
+ int i, multiplier;
+
+ data->last_state_idx = 0;
+ data->exit_us = 0;
+
+ /* Special case when user has set very strict latency requirement */
+ if (unlikely(latency_req == 0))
+ return 0;
+
+ /* determine the expected residency time, round up */
+ data->expected_us =
+ (u32) (ktime_to_ns(tick_nohz_get_sleep_length())+999) / 1000;
+
+
+ data->bucket = which_bucket(data->expected_us);
+
+ multiplier = performance_multiplier();
+
+ /*
+ * if the correction factor is 0 (eg first time init or cpu hotplug
+ * etc), we actually want to start out with a unity factor.
+ */
+ if (data->correction_factor[data->bucket] == 0)
+ data->correction_factor[data->bucket] = RESOLUTION * DECAY;
+
+ /* Make sure to round up for half microseconds */
+ data->predicted_us =
+ (data->expected_us * data->correction_factor[data->bucket] +
+ RESOLUTION * DECAY/2) / RESOLUTION / DECAY;
+
+ /*
+ * We want to default to C1 (hlt), not to busy polling
+ * unless the timer is happening really really soon.
+ */
+ if (data->expected_us > 5)
+ data->last_state_idx = CPUIDLE_DRIVER_STATE_START;
+
+
+ /* find the deepest idle state that satisfies our constraints */
+ for (i = CPUIDLE_DRIVER_STATE_START; i < dev->state_count; i++) {
+ struct cpuidle_state *s = &dev->states[i];
+
+ if (s->target_residency > data->predicted_us)
+ break;
+ if (s->exit_latency > latency_req)
+ break;
+ if (s->exit_latency * multiplier > data->predicted_us)
+ break;
+ data->exit_us = s->exit_latency;
+ data->last_state_idx = i;
+ }
+
+ return data->last_state_idx;
+}
+
+/**
+ * menu_reflect - attempts to guess what happened after entry
+ * @dev: the CPU
+ *
+ * NOTE: it's important to be fast here because this operation will add to
+ * the overall exit latency.
+ */
+static void menu_reflect(struct cpuidle_device *dev)
+{
+ struct menu_device *data = &__get_cpu_var(menu_devices);
+ int last_idx = data->last_state_idx;
+ unsigned int last_idle_us = cpuidle_get_last_residency(dev);
+ struct cpuidle_state *target = &dev->states[last_idx];
+ unsigned int measured_us;
+ u64 new_factor;
+
+ /*
+ * Ugh, this idle state doesn't support residency measurements, so we
+ * are basically lost in the dark. As a compromise, assume we slept
+ * for the whole expected time.
+ */
+ if (unlikely(!(target->flags & CPUIDLE_FLAG_TIME_VALID)))
+ last_idle_us = data->expected_us;
+
+
+ measured_us = last_idle_us;
+
+ /*
+ * We correct for the exit latency; we are assuming here that the
+ * exit latency happens after the event that we're interested in.
+ */
+ if (measured_us > data->exit_us)
+ measured_us -= data->exit_us;
+
+
+ /* update our correction ratio */
+
+ new_factor = data->correction_factor[data->bucket]
+ * (DECAY - 1) / DECAY;
+
+ if (data->expected_us > 0 && data->measured_us < MAX_INTERESTING)
+ new_factor += RESOLUTION * measured_us / data->expected_us;
+ else
+ /*
+ * we were idle so long that we count it as a perfect
+ * prediction
+ */
+ new_factor += RESOLUTION;
+
+ /*
+ * We don't want as factor; we always want at least
+ * a tiny bit of estimated time.
+ */
+ if (new_factor == 0)
+ new_factor = 1;
+
+ data->correction_factor[data->bucket] = new_factor;
+}
+
+/**
+ * menu_enable_device - scans a CPU's states and does setup
+ * @dev: the CPU
+ */
+static int menu_enable_device(struct cpuidle_device *dev)
+{
+ struct menu_device *data = &per_cpu(menu_devices, dev->cpu);
+
+ memset(data, 0, sizeof(struct menu_device));
+
+ return 0;
+}
+
+static struct cpuidle_governor menu_governor = {
+ .name = "menu-tng",
+ .rating = 30,
+ .enable = menu_enable_device,
+ .select = menu_select,
+ .reflect = menu_reflect,
+ .owner = THIS_MODULE,
+};
+
+/**
+ * init_menu - initializes the governor
+ */
+static int __init init_menu(void)
+{
+ return cpuidle_register_governor(&menu_governor);
+}
+
+/**
+ * exit_menu - exits the governor
+ */
+static void __exit exit_menu(void)
+{
+ cpuidle_unregister_governor(&menu_governor);
+}
+
+MODULE_LICENSE("GPL");
+module_init(init_menu);
+module_exit(exit_menu);
diff --git a/include/linux/sched.h b/include/linux/sched.h
index afb4812..79cbe44 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -140,6 +140,10 @@ extern int nr_processes(void);
extern unsigned long nr_running(void);
extern unsigned long nr_uninterruptible(void);
extern unsigned long nr_iowait(void);
+extern unsigned long nr_iowait_cpu(void);
+extern unsigned long this_cpu_load(void);
+
+
extern void calc_global_load(void);
extern u64 cpu_nr_migrations(int cpu);

diff --git a/kernel/sched.c b/kernel/sched.c
index 69b9730..132accc 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -3047,6 +3047,21 @@ unsigned long nr_iowait(void)
return sum;
}

+unsigned long nr_iowait_cpu(void)
+{
+ int this_cpu = smp_processor_id();
+ struct rq *this_rq = cpu_rq(this_cpu);
+ return atomic_read(&this_rq->nr_iowait);
+}
+
+unsigned long this_cpu_load(void)
+{
+ int this_cpu = smp_processor_id();
+ struct rq *this_rq = cpu_rq(this_cpu);
+ return this_rq->cpu_load[0];
+}
+
+
/* Variables and functions for calc_load */
static atomic_long_t calc_load_tasks;
static unsigned long calc_load_update;
--
1.6.0.6



--
Arjan van de Ven Intel Open Source Technology Centre
For development, discussion and tips for power savings,
visit http://www.lesswatts.org


2009-09-11 16:37:32

by Jens Axboe

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Fri, Sep 11 2009, Arjan van de Ven wrote:
> From: Arjan van de Ven <[email protected]>
> Subject: [PATCH] cpuidle: A new variant of the menu governor
>
> This patch adds a new idle governor which balances power savings,
> energy efficiency and performance impact.
>
> The reason for a reworked governor is that there have been
> serious performance issues reported with the existing code
> on Nehalem server systems.
>
> To show this I'm sure Andrew wants to see benchmark results:
> (benchmark is "fio", "no cstates" is using "idle=poll")
>
> no cstates current linux new algorithm
> 1 disk 107 Mb/s 85 Mb/s 105 Mb/s
> 2 disks 215 Mb/s 123 Mb/s 209 Mb/s
> 12 disks 590 Mb/s 320 Mb/s 585 Mb/s

Heh that's interesting, I have noticed some oddities that I haven't
pursued further yet. But it was definitely power state related, so I'll
give your patch spin.

--
Jens Axboe

2009-09-11 19:31:16

by John Stoffel

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

>>>>> "Arjan" == Arjan van de Ven <[email protected]> writes:

Arjan> From: Arjan van de Ven <[email protected]>
Arjan> Subject: [PATCH] cpuidle: A new variant of the menu governor

Arjan> This patch adds a new idle governor which balances power savings,
Arjan> energy efficiency and performance impact.

Arjan> The reason for a reworked governor is that there have been
Arjan> serious performance issues reported with the existing code
Arjan> on Nehalem server systems.

Arjan> To show this I'm sure Andrew wants to see benchmark results:
Arjan> (benchmark is "fio", "no cstates" is using "idle=poll")

Arjan> no cstates current linux new algorithm
Arjan> 1 disk 107 Mb/s 85 Mb/s 105 Mb/s
Arjan> 2 disks 215 Mb/s 123 Mb/s 209 Mb/s
Arjan> 12 disks 590 Mb/s 320 Mb/s 585 Mb/s

Don't you need another row or three where you show a) how much time
each test took, and b) how much (or average) power used for the
duration of the test?

I'm just curious if the new algorithm (or even the current one!) saves
any appreciable power over the 'no cstates' case. It's not clear what
the savings are.

Also, latency in terms of switching to higher power and then back down
would be nice to see.

Cheers,
John

2009-09-11 19:48:06

by Arjan van de Ven

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Fri, 11 Sep 2009 15:16:49 -0400
"John Stoffel" <[email protected]> wrote:

> >>>>> "Arjan" == Arjan van de Ven <[email protected]> writes:
>
> Arjan> From: Arjan van de Ven <[email protected]>
> Arjan> Subject: [PATCH] cpuidle: A new variant of the menu governor
>
> Arjan> This patch adds a new idle governor which balances power
> Arjan> savings, energy efficiency and performance impact.
>
> Arjan> The reason for a reworked governor is that there have been
> Arjan> serious performance issues reported with the existing code
> Arjan> on Nehalem server systems.
>
> Arjan> To show this I'm sure Andrew wants to see benchmark results:
> Arjan> (benchmark is "fio", "no cstates" is using "idle=poll")
>
> Arjan> no cstates current linux new
> Arjan> algorithm 1 disk 107 Mb/s 85
> Arjan> Mb/s 105 Mb/s 2 disks 215
> Arjan> Mb/s 123 Mb/s 209 Mb/s 12 disks 590
> Arjan> Mb/s 320 Mb/s 585 Mb/s
>
> Don't you need another row or three where you show a) how much time
> each test took, and b) how much (or average) power used for the
> duration of the test?
>
> I'm just curious if the new algorithm (or even the current one!) saves
> any appreciable power over the 'no cstates' case. It's not clear what
> the savings are.

if you don't do C states your cpu is likely using 50 Watts more power.
not an option in general.

>
> Also, latency in terms of switching to higher power and then back down
> would be nice to see.

these are C states not P states.


latency depends on the cpu; this is exposed in sysfs;
tends to be for the deepest C state in the 80 to 200 usec range.


--
Arjan van de Ven Intel Open Source Technology Centre
For development, discussion and tips for power savings,
visit http://www.lesswatts.org

2009-09-11 22:03:24

by Matthew Garrett

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

When you say that a bit more power was used, is that instantaneous power
draw or total power consumption over the run of the benchmark? I'd have
expected that completing it 50% faster and then going idle would be a
win overall.

--
Matthew Garrett | [email protected]

2009-09-12 03:23:19

by Arjan van de Ven

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Fri, 11 Sep 2009 23:03:09 +0100
Matthew Garrett <[email protected]> wrote:

> When you say that a bit more power was used, is that instantaneous
> power draw or total power consumption over the run of the benchmark?
> I'd have expected that completing it 50% faster and then going idle
> would be a win overall.

I meant power, not total energy :-)

in terms of energy it's a win if you only do a fixed amount of work...

>


--
Arjan van de Ven Intel Open Source Technology Centre
For development, discussion and tips for power savings,
visit http://www.lesswatts.org

2009-09-12 11:39:55

by Matthew Garrett

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Sat, Sep 12, 2009 at 05:26:47AM +0200, Arjan van de Ven wrote:
> On Fri, 11 Sep 2009 23:03:09 +0100
> Matthew Garrett <[email protected]> wrote:
>
> > When you say that a bit more power was used, is that instantaneous
> > power draw or total power consumption over the run of the benchmark?
> > I'd have expected that completing it 50% faster and then going idle
> > would be a win overall.
>
> I meant power, not total energy :-)
>
> in terms of energy it's a win if you only do a fixed amount of work...

Ok, so not really a downside. Not entirely relatedly, we've also seen io
throughput issues related to P-states - using ondemand, we get reduced
throughput until the number of clients becomes high enough to push the
system into a higher P state. Is this something you've been able to
measure?

--
Matthew Garrett | [email protected]

2009-09-12 14:01:11

by Arjan van de Ven

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Sat, 12 Sep 2009 12:39:39 +0100
Matthew Garrett <[email protected]> wrote:

> On Sat, Sep 12, 2009 at 05:26:47AM +0200, Arjan van de Ven wrote:
> > On Fri, 11 Sep 2009 23:03:09 +0100
> > Matthew Garrett <[email protected]> wrote:
> >
> > > When you say that a bit more power was used, is that instantaneous
> > > power draw or total power consumption over the run of the
> > > benchmark? I'd have expected that completing it 50% faster and
> > > then going idle would be a win overall.
> >
> > I meant power, not total energy :-)
> >
> > in terms of energy it's a win if you only do a fixed amount of
> > work...
>
> Ok, so not really a downside.

correct.

> Not entirely relatedly, we've also seen
> io throughput issues related to P-states - using ondemand, we get
> reduced throughput until the number of clients becomes high enough to
> push the system into a higher P state. Is this something you've been
> able to measure?

so far, with a 10 msec ondemand interval, there is room for
improvement, but it's not too bleak either. With longer intervals there
clearly are problems.

I have some patches for that. However the gain is not nearly as clear
as with this C state patch, and they need some more tweaking...

--
Arjan van de Ven Intel Open Source Technology Centre
For development, discussion and tips for power savings,
visit http://www.lesswatts.org

2009-09-13 23:31:42

by Andrew Morton

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Fri, 11 Sep 2009 17:40:19 +0200 Arjan van de Ven <[email protected]> wrote:

> From: Arjan van de Ven <[email protected]>
> Subject: [PATCH] cpuidle: A new variant of the menu governor
>
> This patch adds a new idle governor which balances power savings,
> energy efficiency and performance impact.
>
> The reason for a reworked governor is that there have been
> serious performance issues reported with the existing code
> on Nehalem server systems.
>
> To show this I'm sure Andrew wants to see benchmark results:
> (benchmark is "fio", "no cstates" is using "idle=poll")
>
> no cstates current linux new algorithm
> 1 disk 107 Mb/s 85 Mb/s 105 Mb/s
> 2 disks 215 Mb/s 123 Mb/s 209 Mb/s
> 12 disks 590 Mb/s 320 Mb/s 585 Mb/s
>
> In various power benchmark measurements, no degredation was found
> by our measurement&diagnostics team. Obviously a bit more power was
> used in the "fio" benchmark, due to the much higher performance.
>
> The integration plan for this is to first add the new governor,
> but for one kernel generation, leave the old menu governor in place
> so that it's possible to separate out behavior from this governor
> versus other things in diagnostics. If no issues are found,
> I'll remove the old governor in the kernel cycle after that.

We can't just fix up the existing code?

What worries me about the integration plan is that we find that there
are some machines/workloads where the old code worked better and we
can't find a way to fix the new code so we end up with two
implementations for users to choose between. As happened (and
continues to happen) with slab.

> While it would be a novel idea to describe the new algorithm in this
> commit message, I cheaped out and described it in comments in the
> code instead.
>
>
> ...
>
> +#define BUCKETS 12
> +#define RESOLUTION 1024
> +#define DECAY 4
> +#define MAX_INTERESTING 50000

Interesting! Unobvious what it does though.

>
> ...
>
> +static int menu_select(struct cpuidle_device *dev)
> +{
> + struct menu_device *data = &__get_cpu_var(menu_devices);
> + int latency_req = pm_qos_requirement(PM_QOS_CPU_DMA_LATENCY);
> + int i, multiplier;
> +
> + data->last_state_idx = 0;
> + data->exit_us = 0;
> +
> + /* Special case when user has set very strict latency requirement */
> + if (unlikely(latency_req == 0))
> + return 0;
> +
> + /* determine the expected residency time, round up */
> + data->expected_us =
> + (u32) (ktime_to_ns(tick_nohz_get_sleep_length())+999) / 1000;

That's DIV_ROUND_UP().

> +
> + data->bucket = which_bucket(data->expected_us);
> +
> + multiplier = performance_multiplier();
> +
> + /*
> + * if the correction factor is 0 (eg first time init or cpu hotplug
> + * etc), we actually want to start out with a unity factor.
> + */
> + if (data->correction_factor[data->bucket] == 0)
> + data->correction_factor[data->bucket] = RESOLUTION * DECAY;
> +
> + /* Make sure to round up for half microseconds */
> + data->predicted_us =
> + (data->expected_us * data->correction_factor[data->bucket] +
> + RESOLUTION * DECAY/2) / RESOLUTION / DECAY;
> +
> + /*
> + * We want to default to C1 (hlt), not to busy polling
> + * unless the timer is happening really really soon.
> + */
> + if (data->expected_us > 5)
> + data->last_state_idx = CPUIDLE_DRIVER_STATE_START;
> +
> +
> + /* find the deepest idle state that satisfies our constraints */
> + for (i = CPUIDLE_DRIVER_STATE_START; i < dev->state_count; i++) {
> + struct cpuidle_state *s = &dev->states[i];
> +
> + if (s->target_residency > data->predicted_us)
> + break;
> + if (s->exit_latency > latency_req)
> + break;
> + if (s->exit_latency * multiplier > data->predicted_us)
> + break;
> + data->exit_us = s->exit_latency;
> + data->last_state_idx = i;
> + }
> +
> + return data->last_state_idx;
> +}
> +
>
> ...
>
> +static void menu_reflect(struct cpuidle_device *dev)
> +{
> + struct menu_device *data = &__get_cpu_var(menu_devices);
> + int last_idx = data->last_state_idx;
> + unsigned int last_idle_us = cpuidle_get_last_residency(dev);
> + struct cpuidle_state *target = &dev->states[last_idx];
> + unsigned int measured_us;
> + u64 new_factor;
> +
> + /*
> + * Ugh, this idle state doesn't support residency measurements, so we
> + * are basically lost in the dark. As a compromise, assume we slept
> + * for the whole expected time.
> + */
> + if (unlikely(!(target->flags & CPUIDLE_FLAG_TIME_VALID)))
> + last_idle_us = data->expected_us;
> +
> +
> + measured_us = last_idle_us;
> +
> + /*
> + * We correct for the exit latency; we are assuming here that the
> + * exit latency happens after the event that we're interested in.
> + */
> + if (measured_us > data->exit_us)
> + measured_us -= data->exit_us;
> +
> +
> + /* update our correction ratio */
> +
> + new_factor = data->correction_factor[data->bucket]
> + * (DECAY - 1) / DECAY;

This code is available on 32-bit. I wouldn't be surprised if we see
some udivdi2-isn't-there problems with some compiler versions. We'll see.

> + if (data->expected_us > 0 && data->measured_us < MAX_INTERESTING)
> + new_factor += RESOLUTION * measured_us / data->expected_us;
> + else
> + /*
> + * we were idle so long that we count it as a perfect
> + * prediction
> + */
> + new_factor += RESOLUTION;
> +
> + /*
> + * We don't want as factor; we always want at least
> + * a tiny bit of estimated time.
> + */
> + if (new_factor == 0)
> + new_factor = 1;
> +
> + data->correction_factor[data->bucket] = new_factor;
> +}
> +
>
> ...
>
> +unsigned long nr_iowait_cpu(void)
> +{
> + int this_cpu = smp_processor_id();
> + struct rq *this_rq = cpu_rq(this_cpu);
> + return atomic_read(&this_rq->nr_iowait);
> +}
> +
> +unsigned long this_cpu_load(void)
> +{
> + int this_cpu = smp_processor_id();
> + struct rq *this_rq = cpu_rq(this_cpu);
> + return this_rq->cpu_load[0];
> +}

hm, how come we don't get smp_processor_id-in-preemptible warnings.
Are all current callers pinned to a CPU?


some spelling fixlets:


--- a/drivers/cpuidle/governors/menu-tng.c~cpuidle-a-new-variant-of-the-menu-governor-to-boost-io-performance-fix
+++ a/drivers/cpuidle/governors/menu-tng.c
@@ -32,7 +32,7 @@
*
* For the menu-tng governor, there are 3 decision factors for picking a C
* state:
- * 1) Energie break even point
+ * 1) Energy break even point
* 2) Performance impact
* 3) Latency tolerance (from pmqos infrastructure)
* These these three factors are treated independently.
@@ -55,12 +55,12 @@
* menu-tng uses a running average for this correction factor, however it uses a
* set of factors, not just a single factor. This stems from the realization
* that the ratio is dependent on the order of magnitude of the expected
- * duration; if we expect 500 milliseconds of idle time the likelyhood of
+ * duration; if we expect 500 milliseconds of idle time the likelihood of
* getting an interrupt very early is much higher than if we expect 50 micro
* seconds of idle time. A second independent factor that has big impact on
* the actual factor is if there is (disk) IO outstanding or not.
* (as a special twist, we consider every sleep longer than 50 milliseconds
- * as perfect; there is no power gains for sleeping longer than this)
+ * as perfect; there are no power gains for sleeping longer than this)
*
* For these two reasons we keep an array of 12 independent factors, that gets
* indexed based on the magnitude of the expected duration as well as the
_

2009-09-14 02:41:38

by Arjan van de Ven

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Sun, 13 Sep 2009 16:30:07 -0700
Andrew Morton <[email protected]> wrote:
>
> We can't just fix up the existing code?

we could, it'd be just replacing menu.c.
(since the new one started out with menu.c anyway)
I don't mind either way, will replace.

> > +#define BUCKETS 12
> > +#define RESOLUTION 1024
> > +#define DECAY 4
> > +#define MAX_INTERESTING 50000
>
> Interesting! Unobvious what it does though.

at least I documented it:
* the actual factor is if there is (disk) IO outstanding or not.
* (as a special twist, we consider every sleep longer than 50 milliseconds
* as perfect; there is no power gains for sleeping longer than this)

>
> That's DIV_ROUND_UP().

ok

> > + new_factor = data->correction_factor[data->bucket]
> > + * (DECAY - 1) / DECAY;
>
> This code is available on 32-bit. I wouldn't be surprised if we see
> some udivdi2-isn't-there problems with some compiler versions. We'll
> see.

at least not on the ones I tried. DECAY is "4" which means it'll be
shifts anyway (that's not entirely accidental)

> > +
> > +unsigned long this_cpu_load(void)
> > +{
> > + int this_cpu = smp_processor_id();
> > + struct rq *this_rq = cpu_rq(this_cpu);
> > + return this_rq->cpu_load[0];
> > +}
>
> hm, how come we don't get smp_processor_id-in-preemptible warnings.
> Are all current callers pinned to a CPU?

the idle loop is pinned by definition, and also runs with irqs off

"all current callers".. this is a new function, with menutng being the
only caller. I'm fine with requiring all callers to be pinned, it's
*this* cpu's load after all ;-)



>
>
> some spelling fixlets:

never been my strong point (esp when jetlagged); thanks!


--
Arjan van de Ven Intel Open Source Technology Centre
For development, discussion and tips for power savings,
visit http://www.lesswatts.org

2009-09-14 03:31:39

by Yanmin Zhang

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Fri, 2009-09-11 at 15:16 -0400, John Stoffel wrote:
> >>>>> "Arjan" == Arjan van de Ven <[email protected]> writes:
>
> Arjan> From: Arjan van de Ven <[email protected]>
> Arjan> Subject: [PATCH] cpuidle: A new variant of the menu governor
>
> Arjan> This patch adds a new idle governor which balances power savings,
> Arjan> energy efficiency and performance impact.
>
> Arjan> The reason for a reworked governor is that there have been
> Arjan> serious performance issues reported with the existing code
> Arjan> on Nehalem server systems.
>
> Arjan> To show this I'm sure Andrew wants to see benchmark results:
> Arjan> (benchmark is "fio", "no cstates" is using "idle=poll")
>
> Arjan> no cstates current linux new algorithm
> Arjan> 1 disk 107 Mb/s 85 Mb/s 105 Mb/s
> Arjan> 2 disks 215 Mb/s 123 Mb/s 209 Mb/s
> Arjan> 12 disks 590 Mb/s 320 Mb/s 585 Mb/s
>
> Don't you need another row or three where you show a) how much time
> each test took,
We start fio and always ask it running for 15 minutes.

> and b) how much (or average) power used for the
> duration of the test?
The power consumption with the patch almost is equal to the one
without the patch. But the fio result is far better with the patch.

>
> I'm just curious if the new algorithm (or even the current one!) saves
> any appreciable power over the 'no cstates' case. It's not clear what
> the savings are.
>
> Also, latency in terms of switching to higher power and then back down
> would be nice to see.
>
> Cheers,
> John

2009-09-14 07:44:43

by Andrew Morton

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Fri, 11 Sep 2009 17:40:19 +0200 Arjan van de Ven <[email protected]> wrote:

> From: Arjan van de Ven <[email protected]>
> Subject: [PATCH] cpuidle: A new variant of the menu governor
>
> This patch adds a new idle governor which balances power savings,
> energy efficiency and performance impact.
>
> The reason for a reworked governor is that there have been
> serious performance issues reported with the existing code
> on Nehalem server systems.
>
> To show this I'm sure Andrew wants to see benchmark results:
> (benchmark is "fio", "no cstates" is using "idle=poll")
>
> no cstates current linux new algorithm
> 1 disk 107 Mb/s 85 Mb/s 105 Mb/s
> 2 disks 215 Mb/s 123 Mb/s 209 Mb/s
> 12 disks 590 Mb/s 320 Mb/s 585 Mb/s
>
> In various power benchmark measurements, no degredation was found
> by our measurement&diagnostics team. Obviously a bit more power was
> used in the "fio" benchmark, due to the much higher performance.
>
> The integration plan for this is to first add the new governor,
> but for one kernel generation, leave the old menu governor in place
> so that it's possible to separate out behavior from this governor
> versus other things in diagnostics. If no issues are found,
> I'll remove the old governor in the kernel cycle after that.
>
> While it would be a novel idea to describe the new algorithm in this
> commit message, I cheaped out and described it in comments in the
> code instead.

This fails to compile in linux-next:

drivers/cpuidle/governors/menu-tng.o:(.discard+0x0): multiple definition of `__pcpu_unique_menu_devices'
drivers/cpuidle/governors/menu.o:(.discard+0x0): first defined here

because we have

static DEFINE_PER_CPU(struct menu_device, menu_devices);

in both menu.c and menu-tng.c.

Despite the `static', the percpu changes in

commit 7c756e6e19e71f0327760d8955f7077118ebb2b1
Author: Tejun Heo <[email protected]>
AuthorDate: Wed Jun 24 15:13:50 2009 +0900
Commit: Tejun Heo <[email protected]>
CommitDate: Wed Jun 24 15:13:50 2009 +0900

percpu: implement optional weak percpu definitions

are emitting global symbol derived from `menu_devices' and they clash.


I'll rename menu_devices to fix that up, but we have a problem...

2009-09-14 08:04:46

by Tejun Heo

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

Andrew Morton wrote:
> This fails to compile in linux-next:
>
> drivers/cpuidle/governors/menu-tng.o:(.discard+0x0): multiple definition of `__pcpu_unique_menu_devices'
> drivers/cpuidle/governors/menu.o:(.discard+0x0): first defined here
>
> because we have
>
> static DEFINE_PER_CPU(struct menu_device, menu_devices);
>
> in both menu.c and menu-tng.c.
>
> Despite the `static', the percpu changes in
>
> commit 7c756e6e19e71f0327760d8955f7077118ebb2b1
> Author: Tejun Heo <[email protected]>
> AuthorDate: Wed Jun 24 15:13:50 2009 +0900
> Commit: Tejun Heo <[email protected]>
> CommitDate: Wed Jun 24 15:13:50 2009 +0900
>
> percpu: implement optional weak percpu definitions
>
> are emitting global symbol derived from `menu_devices' and they clash.
>
> I'll rename menu_devices to fix that up, but we have a problem...

Unfortunately, this was the only way we could come up with to get
alpha and s390 working with the new percpu allocator. On other archs,
the global definition isn't necessary but config option
DEBUG_FORCE_WEAK_PER_CPU enables it so that alpha and s390 don't choke
on generic code later.

The core of the problem is that the memory model used by gcc on those
two archs assume that static symbols are reachable with small offset
but percpu variables, static or not, always end up way away. Making
all percpu variables weak and using global symbols to enforce global
uniqueness works around the problem but with the side effect you're
seeing.

If someone has any better ideas, I would happy to remove the annoying
restriction.

Thanks.

--
tejun

2009-09-14 08:16:25

by Peter Zijlstra

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Mon, 2009-09-14 at 17:04 +0900, Tejun Heo wrote:
> Andrew Morton wrote:
> > This fails to compile in linux-next:
> >
> > drivers/cpuidle/governors/menu-tng.o:(.discard+0x0): multiple definition of `__pcpu_unique_menu_devices'
> > drivers/cpuidle/governors/menu.o:(.discard+0x0): first defined here
> >
> > because we have
> >
> > static DEFINE_PER_CPU(struct menu_device, menu_devices);
> >
> > in both menu.c and menu-tng.c.
> >
> > Despite the `static', the percpu changes in
> >
> > commit 7c756e6e19e71f0327760d8955f7077118ebb2b1
> > Author: Tejun Heo <[email protected]>
> > AuthorDate: Wed Jun 24 15:13:50 2009 +0900
> > Commit: Tejun Heo <[email protected]>
> > CommitDate: Wed Jun 24 15:13:50 2009 +0900
> >
> > percpu: implement optional weak percpu definitions
> >
> > are emitting global symbol derived from `menu_devices' and they clash.
> >
> > I'll rename menu_devices to fix that up, but we have a problem...
>
> Unfortunately, this was the only way we could come up with to get
> alpha and s390 working with the new percpu allocator. On other archs,
> the global definition isn't necessary but config option
> DEBUG_FORCE_WEAK_PER_CPU enables it so that alpha and s390 don't choke
> on generic code later.
>
> The core of the problem is that the memory model used by gcc on those
> two archs assume that static symbols are reachable with small offset
> but percpu variables, static or not, always end up way away. Making
> all percpu variables weak and using global symbols to enforce global
> uniqueness works around the problem but with the side effect you're
> seeing.
>
> If someone has any better ideas, I would happy to remove the annoying
> restriction.

That sounds like a variable __attribute__((no-explicit-relocs)) should
be proposed to the GCC folks or something. Then we can at least have a
hope of lifting this restriction some time in the future.

(Alternatively we build the full alpha kernel with
--mno-explicit-relocs, but that would be sub-optimal as well)

Not sure if s390 has anything similar..

Alternatively we could file it as a bug, since the symbols are in a
custom .section, which is a strong indication we're going to play funny
games anyway.

2009-09-14 09:09:47

by Tejun Heo

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

Hello,

Peter Zijlstra wrote:
>> If someone has any better ideas, I would happy to remove the annoying
>> restriction.
>
> That sounds like a variable __attribute__((no-explicit-relocs)) should
> be proposed to the GCC folks or something. Then we can at least have a
> hope of lifting this restriction some time in the future.
>
> (Alternatively we build the full alpha kernel with
> --mno-explicit-relocs, but that would be sub-optimal as well)
>
> Not sure if s390 has anything similar..

If possible, something like __attribute__((dont-expect-it-to-be-near))
would be very nice in this case.

> Alternatively we could file it as a bug, since the symbols are in a
> custom .section, which is a strong indication we're going to play funny
> games anyway.

This sounds quite appealing but I think it has certain possibility of
coming back and bite us in the rear.

Hmmm... Offsets for symbols which fit in the first chunk are
guaranteed to be addressable with the reduced range and thus the weak
trick is only necessary for modules, so a solution we can implement in
kernel proper is to reserve address range for module text and data to
be loaded near the builtin text and data. Percpu already supports
reservation in the first chunk (for x86-64 for example) so that part
is already there. Ah... only if s390 and alpha are a little easier to
come by. :-(

Thanks.

--
tejun

2009-09-14 20:28:28

by Arjan van de Ven

[permalink] [raw]
Subject: Re: PATCH] cpuidle: A new variant of the menu governor to boost IO performance

On Mon, 14 Sep 2009 00:43:01 -0700
Andrew Morton <[email protected]> wrote:

>
> static DEFINE_PER_CPU(struct menu_device, menu_devices);
>
> in both menu.c and menu-tng.c.
>
> Despite the `static', the percpu changes in
>
> commit 7c756e6e19e71f0327760d8955f7077118ebb2b1
> Author: Tejun Heo <[email protected]>
> AuthorDate: Wed Jun 24 15:13:50 2009 +0900
> Commit: Tejun Heo <[email protected]>
> CommitDate: Wed Jun 24 15:13:50 2009 +0900
>
> percpu: implement optional weak percpu definitions
>
> are emitting global symbol derived from `menu_devices' and they clash.
>
>
> I'll rename menu_devices to fix that up, but we have a problem...

I would consider "static" not working a problem...
yes here it's easy to fix, but it's not nice if you can't make .c file
private..


--
Arjan van de Ven Intel Open Source Technology Centre
For development, discussion and tips for power savings,
visit http://www.lesswatts.org