Skip to contentSkip to conversation

cpuidle: teo: Bug fix, formal correction and cleanup

PATCH In review Rafael J. Wysocki 3 participants 7 messages Nov 13, 2019 – Nov 15, 2019 CPU idle time management framework

lore
Share & tools
lore
#0 lore raw

cover cpuidle: teo: Bug fix, formal correction and cleanup

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

#1 lore raw

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

From: Rafael J. Wysocki <[email protected]>

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")
---
 drivers/cpuidle/governors/teo.c |   21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)
drivers/cpuidle/governors/teo.c +17 -4
Index: 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;
+		}
 	}
 
 	/*
#2 lore raw

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

In reply to Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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.

---
 drivers/cpuidle/governors/teo.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)
drivers/cpuidle/governors/teo.c +8 -1
Index: 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;
 		}
 	}
 
#3 lore raw

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

Quoted 22 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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.

---
 drivers/cpuidle/governors/teo.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================

drivers/cpuidle/governors/teo.c +0 -1
@@ -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;

drivers/cpuidle/governors/teo.c static int teo_select(struct cpuidle_dri · line 372

Quoted 10 lines
drivers/cpuidle/governors/teo.c +8 -0
+                       /*
+                        * 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!

#4 lore raw

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

Quoted 20 lines · On 2019.11.14 15:51 Rafael J. Wysocki wrote:
Quoted 19 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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.

---
 drivers/cpuidle/governors/teo.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================

drivers/cpuidle/governors/teo.c +0 -0
@@ -360,7 +360,14 @@ static int teo_select(struct cpuidle_dri
 
Quoted 16 lines

drivers/cpuidle/governors/teo.c static int teo_select(struct cpuidle_dri · line 372

Quoted 13 lines
drivers/cpuidle/governors/teo.c +8 -1
                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

#5 lore raw

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

Quoted 56 lines · Doug Smythies
Quoted 20 lines · On 2019.11.14 15:51 Rafael J. Wysocki wrote:
Quoted 19 lines · Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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.

---
 drivers/cpuidle/governors/teo.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================

drivers/cpuidle/governors/teo.c +0 -0
@@ -360,7 +360,14 @@ static int teo_select(struct cpuidle_dri
 
Quoted 16 lines

drivers/cpuidle/governors/teo.c static int teo_select(struct cpuidle_dri · line 372

Quoted 13 lines
drivers/cpuidle/governors/teo.c +8 -1
                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

Quoted 8 lines

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!

#6 lore raw

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

In reply to Rafael J. Wysocki

From: Rafael J. Wysocki <[email protected]>

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.

---
 drivers/cpuidle/governors/teo.c |   13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)
drivers/cpuidle/governors/teo.c +8 -5
Index: 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,