[RFC][PATCH 3/3] add the 'menu' cpuidle governor

[RFC][PATCH 3/3] add the 'menu' cpuidle governor

[Adam Belay]

This patch adds the 'menu' governor, as was described in my first email.

Thanks,
Adam

 Kconfig            |   11 +++
 governors/Makefile |    1
 governors/menu.c   |  152 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 164 insertions(+)


diff -urN a/drivers/cpuidle/governors/Makefile b/drivers/cpuidle/governors/Makefile
--- a/drivers/cpuidle/governors/Makefile	2007-03-23 23:09:45.000000000 -0400
+++ b/drivers/cpuidle/governors/Makefile	2007-03-24 02:10:29.000000000 -0400
@@ -3,3 +3,4 @@
 #
 
 obj-$(CONFIG_CPU_IDLE_GOV_LADDER) += ladder.o
+obj-$(CONFIG_CPU_IDLE_GOV_MENU) += menu.o
diff -urN a/drivers/cpuidle/governors/menu.c b/drivers/cpuidle/governors/menu.c
--- a/drivers/cpuidle/governors/menu.c	1969-12-31 19:00:00.000000000 -0500
+++ b/drivers/cpuidle/governors/menu.c	2007-03-23 23:51:15.000000000 -0400
@@ -0,0 +1,152 @@
+/*
+ * menu.c - the menu idle governor
+ *
+ * Copyright (C) 2006-2007 Adam Belay <abelay@novell.com>
+ *
+ * This code is licenced under the GPL.
+ */
+
+#include <linux/kernel.h>
+#include <linux/cpuidle.h>
+#include <linux/latency.h>
+#include <linux/time.h>
+#include <linux/ktime.h>
+#include <linux/tick.h>
+#include <linux/hrtimer.h>
+
+#define BM_HOLDOFF	20000	/* 20 ms */
+
+struct menu_device {
+	int		last_state_idx;
+	int		deepest_bm_state;
+
+	int		break_last_us;
+	int		break_elapsed_us;
+
+	int		bm_elapsed_us;
+	int		bm_holdoff_us;
+
+	unsigned long	idle_jiffies;
+};
+
+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 i, expected_us, max_state = dev->state_count;
+
+	/* discard BM history because it is sticky */
+	cpuidle_get_bm_activity();
+
+	/* determine the expected residency time */
+	expected_us = (s32) ktime_to_ns(tick_nohz_get_sleep_length()) / 1000;
+	expected_us = min(expected_us, data->break_last_us);
+
+	/* determine the maximum state compatible with current BM status */
+	if (cpuidle_get_bm_activity())
+		data->bm_elapsed_us = 0;
+	if (data->bm_elapsed_us <= data->bm_holdoff_us)
+		max_state = data->deepest_bm_state + 1;
+
+	/* find the deepest idle state that satisfies our constraints */
+	for (i = 1; i < max_state; i++) {
+		struct cpuidle_state *s = &dev->states[i];
+		if (s->target_residency > expected_us)
+			break;
+		if (s->exit_latency > system_latency_constraint())
+			break;
+	}
+
+	data->last_state_idx = i - 1;
+	data->idle_jiffies = tick_nohz_get_idle_jiffies();
+	return i - 1;
+}
+
+/**
+ * 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;
+	int measured_us = cpuidle_get_last_residency(dev);
+	struct cpuidle_state *target = &dev->states[last_idx];
+
+	/*
+	 * Ugh, this idle state doesn't support residency measurements, so we
+	 * are basically lost in the dark.  As a compromise, assume we slept
+	 * for one full standard timer tick.  However, be aware that this
+	 * could potentially result in a suboptimal state transition.
+	 */
+	if (!(target->flags & CPUIDLE_FLAG_TIME_VALID))
+		measured_us = USEC_PER_SEC / HZ;
+
+	data->bm_elapsed_us += measured_us;
+	data->break_elapsed_us += measured_us;
+
+	/*
+	 * Did something other than the timer interrupt cause the break event?
+	 */
+	if (tick_nohz_get_idle_jiffies() == data->idle_jiffies) {
+		data->break_last_us = data->break_elapsed_us;
+		data->break_elapsed_us = 0;
+	}
+}
+
+/**
+ * menu_scan_device - scans a CPU's states and does setup
+ * @dev: the CPU
+ */
+static void menu_scan_device(struct cpuidle_device *dev)
+{
+	struct menu_device *data = &per_cpu(menu_devices, dev->cpu);
+	int i;
+
+	data->last_state_idx = 0;
+	data->break_last_us = 0;
+	data->break_elapsed_us = 0;
+	data->bm_elapsed_us = 0;
+	data->bm_holdoff_us = BM_HOLDOFF;
+
+	for (i = 1; i < dev->state_count; i++)
+		if (dev->states[i].flags & CPUIDLE_FLAG_CHECK_BM)
+			break;
+	data->deepest_bm_state = i - 1;
+}
+
+struct cpuidle_governor menu_governor = {
+	.name =		"menu",
+	.scan =		menu_scan_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 -urN a/drivers/cpuidle/Kconfig b/drivers/cpuidle/Kconfig
--- a/drivers/cpuidle/Kconfig	2007-03-23 23:09:45.000000000 -0400
+++ b/drivers/cpuidle/Kconfig	2007-03-24 02:18:19.000000000 -0400
@@ -23,6 +23,17 @@
 	  states using residency time and bus master activity as metrics.  This
 	  algorithm was originally introduced in the old ACPI processor driver.
 
+config CPU_IDLE_GOV_MENU
+	tristate "'menu' governor"
+	depends on CPU_IDLE && NO_HZ
+	default y
+	help
+	  This cpuidle governor evaluates all available states and chooses the
+	  deepest state that meets all of the following constraints: BM activity,
+	  expected time until next timer interrupt, and last break event time
+	  delta.  It is designed to minimize power consumption.  Currently
+	  dynticks is required.
+
 endif	# CPU_IDLE
 
 endmenu

Re: [RFC][PATCH 3/3] add the 'menu' cpuidle governor

[Shaohua Li]

Hi,
On Sat, 2007-03-24 at 03:47 -0400, Adam Belay wrote:
> This patch adds the 'menu' governor, as was described in my first email.
> 

> +/**
> + * 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 i, expected_us, max_state = dev->state_count;
> +
> +	/* discard BM history because it is sticky */
> +	cpuidle_get_bm_activity();
Why discard BM history here? This way the next bm check almost always
return 0.
BTW, bm activity is global (Not cpu specific), we'd better account it
system wide.

> +	/* determine the expected residency time */
> +	expected_us = (s32) ktime_to_ns(tick_nohz_get_sleep_length()) / 1000;
> +	expected_us = min(expected_us, data->break_last_us);
> +
> +	/* determine the maximum state compatible with current BM status */
> +	if (cpuidle_get_bm_activity())
> +		data->bm_elapsed_us = 0;
> +	if (data->bm_elapsed_us <= data->bm_holdoff_us)
> +		max_state = data->deepest_bm_state + 1;
> +
> +	/* find the deepest idle state that satisfies our constraints */
> +	for (i = 1; i < max_state; i++) {
> +		struct cpuidle_state *s = &dev->states[i];
> +		if (s->target_residency > expected_us)
> +			break;
> +		if (s->exit_latency > system_latency_constraint())
> +			break;
> +	}
> +
> +	data->last_state_idx = i - 1;
> +	data->idle_jiffies = tick_nohz_get_idle_jiffies();
> +	return i - 1;
> +}
> +
> +/**
> + * 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;
> +	int measured_us = cpuidle_get_last_residency(dev);
> +	struct cpuidle_state *target = &dev->states[last_idx];
> +
> +	/*
> +	 * Ugh, this idle state doesn't support residency measurements, so we
> +	 * are basically lost in the dark.  As a compromise, assume we slept
> +	 * for one full standard timer tick.  However, be aware that this
> +	 * could potentially result in a suboptimal state transition.
> +	 */
> +	if (!(target->flags & CPUIDLE_FLAG_TIME_VALID))
> +		measured_us = USEC_PER_SEC / HZ;
> +
> +	data->bm_elapsed_us += measured_us;
> +	data->break_elapsed_us += measured_us;
See the system state: idle->running->idle
Looks the bm_elapsed_us and break_elapsed_us account ingored the running
state between the two idles. Eg, the 'running' might generate a lot of
bm activity, then maybe we should reset bm_elapsed_us in the next
'idle'.

Thanks,
Shaohua

Re: [RFC][PATCH 3/3] add the 'menu' cpuidle governor

[Adam Belay]

On Mon, 2007-03-26 at 13:36 +0800, Shaohua Li wrote:
> Hi,
> On Sat, 2007-03-24 at 03:47 -0400, Adam Belay wrote:
> > This patch adds the 'menu' governor, as was described in my first email.
> > 
> 
> > +/**
> > + * 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 i, expected_us, max_state = dev->state_count;
> > +
> > +	/* discard BM history because it is sticky */
> > +	cpuidle_get_bm_activity();
> Why discard BM history here? This way the next bm check almost always
> return 0.

Yes, although in testing it detects BM activity more often then one
might think, I agree, this is probably too aggressive.  At the time, I
was trying to avoid situations where BM_STS goes high early during a
long busy period and as a result becomes stale.

> BTW, bm activity is global (Not cpu specific), we'd better account it
> system wide.

Yes, but do we need to support BM_STS in the SMP case?

> 
> > +	/* determine the expected residency time */
> > +	expected_us = (s32) ktime_to_ns(tick_nohz_get_sleep_length()) / 1000;
> > +	expected_us = min(expected_us, data->break_last_us);
> > +
> > +	/* determine the maximum state compatible with current BM status */
> > +	if (cpuidle_get_bm_activity())
> > +		data->bm_elapsed_us = 0;
> > +	if (data->bm_elapsed_us <= data->bm_holdoff_us)
> > +		max_state = data->deepest_bm_state + 1;
> > +
> > +	/* find the deepest idle state that satisfies our constraints */
> > +	for (i = 1; i < max_state; i++) {
> > +		struct cpuidle_state *s = &dev->states[i];
> > +		if (s->target_residency > expected_us)
> > +			break;
> > +		if (s->exit_latency > system_latency_constraint())
> > +			break;
> > +	}
> > +
> > +	data->last_state_idx = i - 1;
> > +	data->idle_jiffies = tick_nohz_get_idle_jiffies();
> > +	return i - 1;
> > +}
> > +
> > +/**
> > + * 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;
> > +	int measured_us = cpuidle_get_last_residency(dev);
> > +	struct cpuidle_state *target = &dev->states[last_idx];
> > +
> > +	/*
> > +	 * Ugh, this idle state doesn't support residency measurements, so we
> > +	 * are basically lost in the dark.  As a compromise, assume we slept
> > +	 * for one full standard timer tick.  However, be aware that this
> > +	 * could potentially result in a suboptimal state transition.
> > +	 */
> > +	if (!(target->flags & CPUIDLE_FLAG_TIME_VALID))
> > +		measured_us = USEC_PER_SEC / HZ;
> > +
> > +	data->bm_elapsed_us += measured_us;
> > +	data->break_elapsed_us += measured_us;
> See the system state: idle->running->idle
> Looks the bm_elapsed_us and break_elapsed_us account ingored the running
> state between the two idles. Eg, the 'running' might generate a lot of
> bm activity, then maybe we should reset bm_elapsed_us in the next
> 'idle'.

I ignore the time between idle states because I'm only interested in
accounting the idle sleep behavior.  A more sophisticated strategy might
also account the running time between idles in some way.  However, it is
worth noting that a busy system has the indirect effect of shortening
the idle residency times. 

I think removing the BM_STS clear attempt at the beginning should help
to reset bm_elapsed_us after sufficiently long busy periods.

> 
> Thanks,
> Shaohua

Thanks for the feedback.

-Adam

Re: [RFC][PATCH 3/3] add the 'menu' cpuidle governor

[Venki Pallipadi]

On Mar 27, 2007, at 12:04 PM, Adam Belay wrote:

> On Mon, 2007-03-26 at 13:36 +0800, Shaohua Li wrote:
>> Hi,
>> On Sat, 2007-03-24 at 03:47 -0400, Adam Belay wrote:
>>> This patch adds the 'menu' governor, as was described in my first  
>>> email.
>>>
>>
>>> +/**
>>> + * 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 i, expected_us, max_state = dev->state_count;
>>> +
>>> +	/* discard BM history because it is sticky */
>>> +	cpuidle_get_bm_activity();
>> Why discard BM history here? This way the next bm check almost always
>> return 0.
>
> Yes, although in testing it detects BM activity more often then one
> might think, I agree, this is probably too aggressive.  At the time, I
> was trying to avoid situations where BM_STS goes high early during a
> long busy period and as a result becomes stale.

How do you see lot of bm_activity. The monitoring window seems to be  
very small here. Just around the calculation of expected_us.


>> BTW, bm activity is global (Not cpu specific), we'd better account it
>> system wide.
>
> Yes, but do we need to support BM_STS in the SMP case?
>
>>
>>> +	/* determine the expected residency time */
>>> +	expected_us = (s32) ktime_to_ns(tick_nohz_get_sleep_length()) /  
>>> 1000;
>>> +	expected_us = min(expected_us, data->break_last_us);
>>> +
>>> +	/* determine the maximum state compatible with current BM  
>>> status */
>>> +	if (cpuidle_get_bm_activity())
>>> +		data->bm_elapsed_us = 0;
>>> +	if (data->bm_elapsed_us <= data->bm_holdoff_us)
>>> +		max_state = data->deepest_bm_state + 1;
>>> +
>>> +	/* find the deepest idle state that satisfies our constraints */
>>> +	for (i = 1; i < max_state; i++) {
>>> +		struct cpuidle_state *s = &dev->states[i];
>>> +		if (s->target_residency > expected_us)
>>> +			break;
>>> +		if (s->exit_latency > system_latency_constraint())
>>> +			break;
>>> +	}
>>> +
>>> +	data->last_state_idx = i - 1;
>>> +	data->idle_jiffies = tick_nohz_get_idle_jiffies();
>>> +	return i - 1;
>>> +}
>>> +
>>> +/**
>>> + * 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;
>>> +	int measured_us = cpuidle_get_last_residency(dev);
>>> +	struct cpuidle_state *target = &dev->states[last_idx];
>>> +
>>> +	/*
>>> +	 * Ugh, this idle state doesn't support residency measurements,  
>>> so we
>>> +	 * are basically lost in the dark.  As a compromise, assume we  
>>> slept
>>> +	 * for one full standard timer tick.  However, be aware that this
>>> +	 * could potentially result in a suboptimal state transition.
>>> +	 */
>>> +	if (!(target->flags & CPUIDLE_FLAG_TIME_VALID))
>>> +		measured_us = USEC_PER_SEC / HZ;
>>> +
>>> +	data->bm_elapsed_us += measured_us;
>>> +	data->break_elapsed_us += measured_us;
>> See the system state: idle->running->idle
>> Looks the bm_elapsed_us and break_elapsed_us account ingored the  
>> running
>> state between the two idles. Eg, the 'running' might generate a  
>> lot of
>> bm activity, then maybe we should reset bm_elapsed_us in the next
>> 'idle'.
>
> I ignore the time between idle states because I'm only interested in
> accounting the idle sleep behavior.  A more sophisticated strategy  
> might
> also account the running time between idles in some way.  However,  
> it is
> worth noting that a busy system has the indirect effect of shortening
> the idle residency times.
>
> I think removing the BM_STS clear attempt at the beginning should help
> to reset bm_elapsed_us after sufficiently long busy periods.
>

I am also thinking about break_elapsed_us.
>>> +	data->break_elapsed_us += measured_us;

It seems to assume that we are in back to back idle. But it can be
idle -> busy -> idle -> busy -> idle -> busy that is going to cause  
some interrupt in near future -> idle -> busy
In this case break_elapsed _us would be a huge number which would be  
wrong.
Better way may be to make break_elapsed_us to zero once we notice  
some busy-ness.

Also, instead of one break_elapsed_us and bm, we may have to  
experiment with maintaining previous X values as history and using  
the min of those X values than just one last value. What do you think?

Thanks,
Venki