[PATCH 0/3] cpuidle: teo: Bug fix, formal correction and cleanup

[PATCH 0/3] cpuidle: teo: Bug fix, formal correction and cleanup

[Rafael J. Wysocki]

Hi All,

These are three updates of the teo cpuidle governor.

Patch [1/3] fixes a bug in it (present from the outset and not addressed by
recent updates).  Patch [2/3] is a formal correction, mostly about avoiding
unrealistic expectations (even if that doesn't make much of a practical
difference), and patch [3/3] is a cleanup.

The series is on top of the linux-next branch in the linux-pm.git tree from
today.

Thanks,
Rafael

[PATCH 1/3] cpuidle: teo: Avoid using "early hits" incorrectly

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

If the current state with the maximum "early hits" metric in
teo_select() is also the one "matching" the expected idle duration,
it will be used as the candidate one for selection even if its
"misses" metric is greater than its "hits" metric, which is not
correct.

In that case, the candidate state should be shallower than the
current one and its "early hits" metric should be the maximum
among the idle states shallower than the current one.

To make that happen, modify teo_select() to save the index of
the state whose "early hits" metric is the maximum for the
range of states below the current one and go back to that state
if it turns out that the current one should be rejected.

Fixes: 159e48560f51 ("cpuidle: teo: Fix "early hits" handling for disabled idle states")
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/teo.c |   21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/teo.c
+++ linux-pm/drivers/cpuidle/governors/teo.c
@@ -239,7 +239,7 @@ static int teo_select(struct cpuidle_dri
 	s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
 	u64 duration_ns;
 	unsigned int hits, misses, early_hits;
-	int max_early_idx, constraint_idx, idx, i;
+	int max_early_idx, prev_max_early_idx, constraint_idx, idx, i;
 	ktime_t delta_tick;
 
 	if (dev->last_state_idx >= 0) {
@@ -256,6 +256,7 @@ static int teo_select(struct cpuidle_dri
 	misses = 0;
 	early_hits = 0;
 	max_early_idx = -1;
+	prev_max_early_idx = -1;
 	constraint_idx = drv->state_count;
 	idx = -1;
 
@@ -307,6 +308,7 @@ static int teo_select(struct cpuidle_dri
 			 */
 			if (!(tick_nohz_tick_stopped() &&
 			      drv->states[idx].target_residency_ns < TICK_NSEC)) {
+				prev_max_early_idx = max_early_idx;
 				early_hits = cpu_data->states[i].early_hits;
 				max_early_idx = idx;
 			}
@@ -333,6 +335,7 @@ static int teo_select(struct cpuidle_dri
 		if (early_hits < cpu_data->states[i].early_hits &&
 		    !(tick_nohz_tick_stopped() &&
 		      drv->states[i].target_residency_ns < TICK_NSEC)) {
+			prev_max_early_idx = max_early_idx;
 			early_hits = cpu_data->states[i].early_hits;
 			max_early_idx = i;
 		}
@@ -346,9 +349,19 @@ static int teo_select(struct cpuidle_dri
 	 * "early hits" metric, but if that cannot be determined, just use the
 	 * state selected so far.
 	 */
-	if (hits <= misses && max_early_idx >= 0) {
-		idx = max_early_idx;
-		duration_ns = drv->states[idx].target_residency_ns;
+	if (hits <= misses) {
+		/*
+		 * The current candidate state is not suitable, so take the one
+		 * whose "early hits" metric is the maximum for the range of
+		 * shallower states.
+		 */
+		if (idx == max_early_idx)
+			max_early_idx = prev_max_early_idx;
+
+		if (max_early_idx >= 0) {
+			idx = max_early_idx;
+			duration_ns = drv->states[idx].target_residency_ns;
+		}
 	}
 
 	/*

[PATCH 2/3] cpuidle: teo: Avoid expecting unrealistic idle times

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

If an idle state shallower than the one "matching" the time till the
next timer event is considered for selection, expect the idle duration
to fall in the middle of the "bin" corresponding to that state rather
than at the beginning of it which is unrealistic.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/teo.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/teo.c
+++ linux-pm/drivers/cpuidle/governors/teo.c
@@ -360,7 +360,14 @@ static int teo_select(struct cpuidle_dri
 
 		if (max_early_idx >= 0) {
 			idx = max_early_idx;
-			duration_ns = drv->states[idx].target_residency_ns;
+			/*
+			 * Expect the idle duration to fall in the middle of the
+			 * "bin" corresponding to idx (note that the maximum
+			 * state index is guaranteed to be greater than idx at
+			 * this point).
+			 */
+			duration_ns = (drv->states[idx].target_residency_ns +
+				drv->states[idx+1].target_residency_ns) / 2;
 		}
 	}
 

[PATCH 3/3] cpuidle: teo: Avoid code duplication in conditionals

[Rafael J. Wysocki]

From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

There are three places in teo_select() where a given amount of time
is compared with TICK_NSEC if tick_nohz_tick_stopped() returns true,
which is a bit of duplicated code.

Avoid that code duplication by defining a helper function to do the
check and using it in all of the places in question.

No intentional functional impact.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/teo.c |   13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/teo.c
+++ linux-pm/drivers/cpuidle/governors/teo.c
@@ -202,6 +202,11 @@ static void teo_update(struct cpuidle_dr
 		cpu_data->interval_idx = 0;
 }
 
+static bool teo_time_ok(u64 interval_ns)
+{
+	return !tick_nohz_tick_stopped() || interval_ns >= TICK_NSEC;
+}
+
 /**
  * teo_find_shallower_state - Find shallower idle state matching given duration.
  * @drv: cpuidle driver containing state data.
@@ -306,8 +311,7 @@ static int teo_select(struct cpuidle_dri
 			 * check if the current candidate state is not too
 			 * shallow for that role.
 			 */
-			if (!(tick_nohz_tick_stopped() &&
-			      drv->states[idx].target_residency_ns < TICK_NSEC)) {
+			if (teo_time_ok(drv->states[idx].target_residency_ns)) {
 				prev_max_early_idx = max_early_idx;
 				early_hits = cpu_data->states[i].early_hits;
 				max_early_idx = idx;
@@ -333,8 +337,7 @@ static int teo_select(struct cpuidle_dri
 		misses = cpu_data->states[i].misses;
 
 		if (early_hits < cpu_data->states[i].early_hits &&
-		    !(tick_nohz_tick_stopped() &&
-		      drv->states[i].target_residency_ns < TICK_NSEC)) {
+		    teo_time_ok(drv->states[i].target_residency_ns)) {
 			prev_max_early_idx = max_early_idx;
 			early_hits = cpu_data->states[i].early_hits;
 			max_early_idx = i;
@@ -409,7 +412,7 @@ static int teo_select(struct cpuidle_dri
 			 * Avoid spending too much time in an idle state that
 			 * would be too shallow.
 			 */
-			if (!(tick_nohz_tick_stopped() && avg_ns < TICK_NSEC)) {
+			if (teo_time_ok(avg_ns)) {
 				duration_ns = avg_ns;
 				if (drv->states[idx].target_residency_ns > avg_ns)
 					idx = teo_find_shallower_state(drv, dev,

Re: [PATCH 2/3] cpuidle: teo: Avoid expecting unrealistic idle times

[Rafael J. Wysocki]

On Wed, Nov 13, 2019 at 1:11 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
>
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
>
> If an idle state shallower than the one "matching" the time till the
> next timer event is considered for selection, expect the idle duration
> to fall in the middle of the "bin" corresponding to that state rather
> than at the beginning of it which is unrealistic.
>
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> ---
>  drivers/cpuidle/governors/teo.c |    9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
>
> Index: linux-pm/drivers/cpuidle/governors/teo.c
> ===================================================================
> --- linux-pm.orig/drivers/cpuidle/governors/teo.c
> +++ linux-pm/drivers/cpuidle/governors/teo.c
> @@ -360,7 +360,14 @@ static int teo_select(struct cpuidle_dri
>
>                 if (max_early_idx >= 0) {
>                         idx = max_early_idx;
> -                       duration_ns = drv->states[idx].target_residency_ns;
> +                       /*
> +                        * Expect the idle duration to fall in the middle of the
> +                        * "bin" corresponding to idx (note that the maximum
> +                        * state index is guaranteed to be greater than idx at
> +                        * this point).
> +                        */
> +                       duration_ns = (drv->states[idx].target_residency_ns +
> +                               drv->states[idx+1].target_residency_ns) / 2;
>                 }
>         }

This change turns out to cause the governor to choose idle states that
are too deep or too shallow too often, so I'm withdrawing it.

Thanks!

RE: [PATCH 2/3] cpuidle: teo: Avoid expecting unrealistic idle times

[Doug Smythies]

On 2019.11.14 15:51 Rafael J. Wysocki wrote:
> On Wed, Nov 13, 2019 at 1:11 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
>>
>> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
>>
>> If an idle state shallower than the one "matching" the time till the
>> next timer event is considered for selection, expect the idle duration
>> to fall in the middle of the "bin" corresponding to that state rather
>> than at the beginning of it which is unrealistic.
>>
>> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
>> ---
>>  drivers/cpuidle/governors/teo.c |    9 ++++++++-
>>  1 file changed, 8 insertions(+), 1 deletion(-)
>>
>> Index: linux-pm/drivers/cpuidle/governors/teo.c
>> ===================================================================
>> --- linux-pm.orig/drivers/cpuidle/governors/teo.c
>> +++ linux-pm/drivers/cpuidle/governors/teo.c
>> @@ -360,7 +360,14 @@ static int teo_select(struct cpuidle_dri
>>
>>                 if (max_early_idx >= 0) {
>>                         idx = max_early_idx;
>> -                       duration_ns = drv->states[idx].target_residency_ns;
>> +                       /*
>> +                        * Expect the idle duration to fall in the middle of the
>> +                        * "bin" corresponding to idx (note that the maximum
>> +                        * state index is guaranteed to be greater than idx at
>> +                        * this point).
>> +                        */
>> +                       duration_ns = (drv->states[idx].target_residency_ns +
>> +                               drv->states[idx+1].target_residency_ns) / 2;
>>                 }
>>         }
>
> This change turns out to cause the governor to choose idle states that
> are too deep or too shallow too often, so I'm withdrawing it.

O.K. thanks for letting us know.
I did see some differences in the testing I did so far, but hadn't drilled down
into it yet.
I am somewhat wondering about the above and below stats in general.

By the way, I had a daft mistake in my post processing program, such that the
"below" graph for idle state 0 was always plotting 0.

Reference for that sweep test that I do (which is as far I got so far):
http://www.smythies.com/~doug/linux/idle/teo-2019-11/sweep/index.html

Legend:

teo-v2: re-run of previous teo-v2 so that I could get non-zero idle state "below" data
linux-next 2019.11.07 + cpuidle: Consolidate disabled state checks +
[PATCH v2] cpuidle: Use nanoseconds as the unit of time

teo-v3: teo-v2 + cpuidle: teo: Exclude cpuidle overhead from computations

teo-v4: linux-pm + linux-next 2019.11.12 +
cpuidle: teo: Avoid code duplication in conditionals
cpuidle: teo: Avoid expecting unrealistic idle times
cpuidle: teo: Avoid using "early hits" incorrectly

teo-v5: teo-v4 + cpuidle: teo: Exclude cpuidle overhead from computations

... Doug

Re: [PATCH 2/3] cpuidle: teo: Avoid expecting unrealistic idle times

[Rafael J. Wysocki]

On Fri, Nov 15, 2019 at 2:24 AM Doug Smythies <dsmythies@telus.net> wrote:
>
> On 2019.11.14 15:51 Rafael J. Wysocki wrote:
> > On Wed, Nov 13, 2019 at 1:11 AM Rafael J. Wysocki <rjw@rjwysocki.net> wrote:
> >>
> >> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >>
> >> If an idle state shallower than the one "matching" the time till the
> >> next timer event is considered for selection, expect the idle duration
> >> to fall in the middle of the "bin" corresponding to that state rather
> >> than at the beginning of it which is unrealistic.
> >>
> >> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> >> ---
> >>  drivers/cpuidle/governors/teo.c |    9 ++++++++-
> >>  1 file changed, 8 insertions(+), 1 deletion(-)
> >>
> >> Index: linux-pm/drivers/cpuidle/governors/teo.c
> >> ===================================================================
> >> --- linux-pm.orig/drivers/cpuidle/governors/teo.c
> >> +++ linux-pm/drivers/cpuidle/governors/teo.c
> >> @@ -360,7 +360,14 @@ static int teo_select(struct cpuidle_dri
> >>
> >>                 if (max_early_idx >= 0) {
> >>                         idx = max_early_idx;
> >> -                       duration_ns = drv->states[idx].target_residency_ns;
> >> +                       /*
> >> +                        * Expect the idle duration to fall in the middle of the
> >> +                        * "bin" corresponding to idx (note that the maximum
> >> +                        * state index is guaranteed to be greater than idx at
> >> +                        * this point).
> >> +                        */
> >> +                       duration_ns = (drv->states[idx].target_residency_ns +
> >> +                               drv->states[idx+1].target_residency_ns) / 2;
> >>                 }
> >>         }
> >
> > This change turns out to cause the governor to choose idle states that
> > are too deep or too shallow too often, so I'm withdrawing it.
>
> O.K. thanks for letting us know.
> I did see some differences in the testing I did so far, but hadn't drilled down
> into it yet.
> I am somewhat wondering about the above and below stats in general.
>
> By the way, I had a daft mistake in my post processing program, such that the
> "below" graph for idle state 0 was always plotting 0.
>
> Reference for that sweep test that I do (which is as far I got so far):
> http://www.smythies.com/~doug/linux/idle/teo-2019-11/sweep/index.html
>
> Legend:
>
> teo-v2: re-run of previous teo-v2 so that I could get non-zero idle state "below" data
> linux-next 2019.11.07 + cpuidle: Consolidate disabled state checks +
> [PATCH v2] cpuidle: Use nanoseconds as the unit of time
>
> teo-v3: teo-v2 + cpuidle: teo: Exclude cpuidle overhead from computations
>
> teo-v4: linux-pm + linux-next 2019.11.12 +
> cpuidle: teo: Avoid code duplication in conditionals
> cpuidle: teo: Avoid expecting unrealistic idle times
> cpuidle: teo: Avoid using "early hits" incorrectly
>
> teo-v5: teo-v4 + cpuidle: teo: Exclude cpuidle overhead from computations

Thanks for running the tests, appreciated!