[PATCH v3 0/3] cpuidle: teo: Avoid stopping scheduler tick too often

[PATCH v3 0/3] cpuidle: teo: Avoid stopping scheduler tick too often

[Rafael J. Wysocki]

Hi Folks,

Patch [1/3] in this series is a v3 of this patch posted last week:

https://lore.kernel.org/linux-pm/4506480.LvFx2qVVIh@kreacher/

Patch [2/3] (this is the second version of it) addresses some bail out paths
in teo_select() in which the scheduler tick may be stopped unnecessarily too.

Patch [3/3] replaces a structure field with a local variable (while at it)
and it is the same as its previous version.

According to this message:

https://lore.kernel.org/linux-pm/CAJZ5v0jJxHj65r2HXBTd3wfbZtsg=_StzwO1kA5STDnaPe_dWA@mail.gmail.com/

this series significantly reduces the number of cases in which the governor
requests stopping the tick when the selected idle state is shallow, which is
incorrect.

Thanks!

[PATCH v3 1/3] cpuidle: teo: Update idle duration estimate when choosing shallower state

[Rafael J. Wysocki]

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

The TEO governor takes CPU utilization into account by refining idle state
selection when the utilization is above a certain threshold.  This is done by
choosing an idle state shallower than the previously selected one.

However, when doing this, the idle duration estimate needs to be
adjusted so as to prevent the scheduler tick from being stopped when the
candidate idle state is shallow, which may lead to excessive energy
usage if the CPU is not woken up quickly enough going forward.
Moreover, if the scheduler tick has been stopped already and the new
idle duration estimate is too small, the replacement candidate state
cannot be used.

Modify the relevant code to take the above observations into account.

Fixes: 9ce0f7c4bc64 ("cpuidle: teo: Introduce util-awareness")
Link: https://lore.kernel.org/linux-pm/CAJZ5v0jJxHj65r2HXBTd3wfbZtsg=_StzwO1kA5STDnaPe_dWA@mail.gmail.com
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---

v2 -> v3:
   * Make the handling of the "2 idle state and utilized CPU" case more
     straightforward.

v1 -> v2:
   * Rework the code handling the special case when the CPU is utilized and
     there are only 2 idle states (drop the loop, avoid using state 0 when
     the tick has been stopped already and it is too shallow, check if
     state 1 is not disabled when about to use it, set low idle duration
     estimate).
   * Changelog edits.

---
 drivers/cpuidle/governors/teo.c |   40 ++++++++++++++++++++++++++++++----------
 1 file changed, 30 insertions(+), 10 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/teo.c
+++ linux-pm/drivers/cpuidle/governors/teo.c
@@ -397,13 +397,23 @@ static int teo_select(struct cpuidle_dri
 	 * the shallowest non-polling state and exit.
 	 */
 	if (drv->state_count < 3 && cpu_data->utilized) {
-		for (i = 0; i < drv->state_count; ++i) {
-			if (!dev->states_usage[i].disable &&
-			    !(drv->states[i].flags & CPUIDLE_FLAG_POLLING)) {
-				idx = i;
-				goto end;
-			}
-		}
+		/* The CPU is utilized, so assume a short idle duration. */
+		duration_ns = teo_middle_of_bin(0, drv);
+		/*
+		 * If state 0 is enabled and it is not a polling one, select it
+		 * right away unless the scheduler tick has been stopped, in
+		 * which case care needs to be taken to leave the CPU in a deep
+		 * enough state in case it is not woken up any time soon after
+		 * all.  If state 1 is disabled, though, state 0 must be used
+		 * anyway.
+		 */
+		if ((!idx && !(drv->states[0].flags & CPUIDLE_FLAG_POLLING) &&
+		    teo_time_ok(duration_ns)) || dev->states_usage[1].disable)
+			idx = 0;
+		else /* Assume that state 1 is not a polling one and use it. */
+			idx = 1;
+
+		goto end;
 	}
 
 	/*
@@ -539,10 +549,20 @@ static int teo_select(struct cpuidle_dri
 
 	/*
 	 * If the CPU is being utilized over the threshold, choose a shallower
-	 * non-polling state to improve latency
+	 * non-polling state to improve latency, unless the scheduler tick has
+	 * been stopped already and the shallower state's target residency is
+	 * not sufficiently large.
 	 */
-	if (cpu_data->utilized)
-		idx = teo_find_shallower_state(drv, dev, idx, duration_ns, true);
+	if (cpu_data->utilized) {
+		s64 span_ns;
+
+		i = teo_find_shallower_state(drv, dev, idx, duration_ns, true);
+		span_ns = teo_middle_of_bin(i, drv);
+		if (teo_time_ok(span_ns)) {
+			idx = i;
+			duration_ns = span_ns;
+		}
+	}
 
 end:
 	/*

[PATCH v3 2/3] cpuidle: teo: Avoid stopping the tick unnecessarily when bailing out

[Rafael J. Wysocki]

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

When teo_select() is going to return early in some special cases, make
it avoid stopping the tick if the idle state to be returned is shallow.

In particular, never stop the tick if state 0 is to be returned.

Link: https://lore.kernel.org/linux-pm/CAJZ5v0jJxHj65r2HXBTd3wfbZtsg=_StzwO1kA5STDnaPe_dWA@mail.gmail.com
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---

v2 -> v3:
   * Cover all of the special cases when 0 is returned and never stop the tick
     in those cases.
   * Do not bail out when constraint_idx becomes the candidate state (it should
     be subject to the usual checks below, because it isn't really special).
   * Be more careful about stopping the tick when the first enabled idle state
     is used.

v1 -> v2: New patch

---
 drivers/cpuidle/governors/teo.c |   56 +++++++++++++++++++++++-----------------
 1 file changed, 33 insertions(+), 23 deletions(-)

Index: linux-pm/drivers/cpuidle/governors/teo.c
===================================================================
--- linux-pm.orig/drivers/cpuidle/governors/teo.c
+++ linux-pm/drivers/cpuidle/governors/teo.c
@@ -382,12 +382,13 @@ static int teo_select(struct cpuidle_dri
 	/* Check if there is any choice in the first place. */
 	if (drv->state_count < 2) {
 		idx = 0;
-		goto end;
+		goto out_tick;
 	}
+
 	if (!dev->states_usage[0].disable) {
 		idx = 0;
 		if (drv->states[1].target_residency_ns > duration_ns)
-			goto end;
+			goto out_tick;
 	}
 
 	cpu_data->utilized = teo_cpu_is_utilized(dev->cpu, cpu_data);
@@ -408,11 +409,12 @@ static int teo_select(struct cpuidle_dri
 		 * anyway.
 		 */
 		if ((!idx && !(drv->states[0].flags & CPUIDLE_FLAG_POLLING) &&
-		    teo_time_ok(duration_ns)) || dev->states_usage[1].disable)
+		    teo_time_ok(duration_ns)) || dev->states_usage[1].disable) {
 			idx = 0;
-		else /* Assume that state 1 is not a polling one and use it. */
-			idx = 1;
-
+			goto out_tick;
+		}
+		/* Assume that state 1 is not a polling one and use it. */
+		idx = 1;
 		goto end;
 	}
 
@@ -459,8 +461,15 @@ static int teo_select(struct cpuidle_dri
 	/* Avoid unnecessary overhead. */
 	if (idx < 0) {
 		idx = 0; /* No states enabled, must use 0. */
-		goto end;
-	} else if (idx == idx0) {
+		goto out_tick;
+	}
+
+	if (idx == idx0) {
+		/*
+		 * This is the first enabled idle state, so use it, but do not
+		 * allow the tick to be stopped it is shallow enough.
+		 */
+		duration_ns = drv->states[idx].target_residency_ns;
 		goto end;
 	}
 
@@ -566,24 +575,25 @@ static int teo_select(struct cpuidle_dri
 
 end:
 	/*
-	 * Don't stop the tick if the selected state is a polling one or if the
-	 * expected idle duration is shorter than the tick period length.
+	 * Allow the tick to be stopped unless the selected state is a polling
+	 * one or the expected idle duration is shorter than the tick period
+	 * length.
 	 */
-	if (((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) ||
-	    duration_ns < TICK_NSEC) && !tick_nohz_tick_stopped()) {
-		*stop_tick = false;
+	if ((!(drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
+	    duration_ns >= TICK_NSEC) || tick_nohz_tick_stopped())
+		return idx;
 
-		/*
-		 * The tick is not going to be stopped, so if the target
-		 * residency of the state to be returned is not within the time
-		 * till the closest timer including the tick, try to correct
-		 * that.
-		 */
-		if (idx > idx0 &&
-		    drv->states[idx].target_residency_ns > delta_tick)
-			idx = teo_find_shallower_state(drv, dev, idx, delta_tick, false);
-	}
+	/*
+	 * The tick is not going to be stopped, so if the target residency of
+	 * the state to be returned is not within the time till the closest
+	 * timer including the tick, try to correct that.
+	 */
+	if (idx > idx0 &&
+	    drv->states[idx].target_residency_ns > delta_tick)
+		idx = teo_find_shallower_state(drv, dev, idx, delta_tick, false);
 
+out_tick:
+	*stop_tick = false;
 	return idx;
 }
 

[PATCH v3 3/3] cpuidle: teo: Drop utilized from struct teo_cpu

[Rafael J. Wysocki]

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

Because the utilized field in struct teo_cpu is only used locally in
teo_select(), replace it with a local variable in that function.

No intentional functional impact.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---

v2 -> v3: No changes

v1 -> v2: New patch

---
 drivers/cpuidle/governors/teo.c |    9 ++++-----
 1 file changed, 4 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
@@ -187,7 +187,6 @@ struct teo_bin {
  * @next_recent_idx: Index of the next @recent_idx entry to update.
  * @recent_idx: Indices of bins corresponding to recent "intercepts".
  * @util_threshold: Threshold above which the CPU is considered utilized
- * @utilized: Whether the last sleep on the CPU happened while utilized
  */
 struct teo_cpu {
 	s64 time_span_ns;
@@ -197,7 +196,6 @@ struct teo_cpu {
 	int next_recent_idx;
 	int recent_idx[NR_RECENT];
 	unsigned long util_threshold;
-	bool utilized;
 };
 
 static DEFINE_PER_CPU(struct teo_cpu, teo_cpus);
@@ -366,6 +364,7 @@ static int teo_select(struct cpuidle_dri
 	int idx0 = 0, idx = -1;
 	bool alt_intercepts, alt_recent;
 	ktime_t delta_tick;
+	bool cpu_utilized;
 	s64 duration_ns;
 	int i;
 
@@ -391,13 +390,13 @@ static int teo_select(struct cpuidle_dri
 			goto out_tick;
 	}
 
-	cpu_data->utilized = teo_cpu_is_utilized(dev->cpu, cpu_data);
+	cpu_utilized = teo_cpu_is_utilized(dev->cpu, cpu_data);
 	/*
 	 * If the CPU is being utilized over the threshold and there are only 2
 	 * states to choose from, the metrics need not be considered, so choose
 	 * the shallowest non-polling state and exit.
 	 */
-	if (drv->state_count < 3 && cpu_data->utilized) {
+	if (drv->state_count < 3 && cpu_utilized) {
 		/* The CPU is utilized, so assume a short idle duration. */
 		duration_ns = teo_middle_of_bin(0, drv);
 		/*
@@ -562,7 +561,7 @@ static int teo_select(struct cpuidle_dri
 	 * been stopped already and the shallower state's target residency is
 	 * not sufficiently large.
 	 */
-	if (cpu_data->utilized) {
+	if (cpu_utilized) {
 		s64 span_ns;
 
 		i = teo_find_shallower_state(drv, dev, idx, duration_ns, true);

Re: [PATCH v3 0/3] cpuidle: teo: Avoid stopping scheduler tick too often

[Kajetan Puchalski]

Hi Rafael,

> Hi Folks,
> 
> Patch [1/3] in this series is a v3 of this patch posted last week:
> 
> https://lore.kernel.org/linux-pm/4506480.LvFx2qVVIh@kreacher/
> 
> Patch [2/3] (this is the second version of it) addresses some bail out paths
> in teo_select() in which the scheduler tick may be stopped unnecessarily too.
> 
> Patch [3/3] replaces a structure field with a local variable (while at it)
> and it is the same as its previous version.
> 
> According to this message:
> 
> https://lore.kernel.org/linux-pm/CAJZ5v0jJxHj65r2HXBTd3wfbZtsg=_StzwO1kA5STDnaPe_dWA@mail.gmail.com/
> 
> this series significantly reduces the number of cases in which the governor
> requests stopping the tick when the selected idle state is shallow, which is
> incorrect.
> 
> Thanks!
> 
> 

I did some initial testing with this on Android (Pixel 6, Android 13).

1. Geekbench 6

+---------------------------+---------------+-----------------+
|          metric           |      teo      |     teo_tick    |
+---------------------------+---------------+-----------------+
|      multicore_score      | 3320.9 (0.0%) | 3303.3 (-0.53%) |
|           score           | 1415.7 (0.0%) | 1417.7 (0.14%)  |
|      CPU_total_power      | 2421.3 (0.0%) | 2429.3 (0.33%)  |
|  latency (AsyncTask #1)   | 49.41μ (0.0%) | 51.07μ (3.36%)  |
| latency (labs.geekbench6) | 65.63μ (0.0%) | 77.47μ (18.03%) |
| latency (surfaceflinger)  | 39.46μ (0.0%) | 36.94μ (-6.39%) |
+---------------------------+---------------+-----------------+

So the big picture for this workload looks roughly the same, the
differences are too small for me to be confident in saying that the
score/power difference is the result of the patches and not something
random in the system.
Same with the latency, the difference for labs.gb6 stands out but that's
a pretty irrelevant task that sets up the benchmark, not the benchmark
itself so not the biggest deal I think.

+---------------+---------+------------+--------+
|     kernel    | cluster | idle_state |  time  |
+---------------+---------+------------+--------+
|      teo      | little  |    0.0     | 146.75 |
|      teo      | little  |    1.0     | 53.75  |
|    teo_tick   | little  |    0.0     |  63.5  |
|    teo_tick   | little  |    1.0     | 146.78 |
+---------------+---------+------------+--------+

+---------------+-------------+------------+
|     kernel    |    type     | count_perc |
+---------------+-------------+------------+
|   teo         |  too deep   |   2.034    |
|   teo         | too shallow |   15.791   |
|   teo_tick    |  too deep   |    2.16    |
|   teo_tick    | too shallow |   20.881   |
+---------------+-------------+------------+

The difference shows up in the idle numbers themselves, looks like we
get a big shift towards deeper idle on our efficiency cores (little
cluster) and more missed wakeups overall, both too deep & too shallow.

Notably, the percentage of too shallow sleeps on the performance cores has
more or less doubled (2% + 0.8% -> 4.3% + 1.8%). This doesn't
necessarily have to be an issue but I'll do more testing just in case.

2. JetNews (Light UI workload)

+------------------+---------------+----------------+
|      metric      |      teo      |    teo_tick    |
+------------------+---------------+----------------+
|       fps        |  86.2 (0.0%)  |  86.4 (0.16%)  |
|     janks_pc     |  0.8 (0.0%)   |  0.8 (-0.00%)  |
| CPU_total_power  | 185.2 (0.0%)  | 178.2 (-3.76%) |
+------------------+---------------+----------------+

For the UI side, the frame data comes out the same on both variants but
alongside better power usage which is nice to have.

+---------------+---------+------------+-------+
|    kernel     | cluster | idle_state | time  |
+---------------+---------+------------+-------+
|      teo      | little  |    0.0     | 25.06 |
|      teo      | little  |    1.0     | 12.21 |
|      teo      |   mid   |    0.0     | 38.32 |
|      teo      |   mid   |    1.0     | 17.82 |
|      teo      |   big   |    0.0     | 30.45 |
|      teo      |   big   |    1.0     | 38.5  |
|    teo_tick   | little  |    0.0     | 23.18 |
|    teo_tick   | little  |    1.0     | 14.21 |
|    teo_tick   |   mid   |    0.0     | 36.31 |
|    teo_tick   |   mid   |    1.0     | 19.88 |
|    teo_tick   |   big   |    0.0     | 27.13 |
|    teo_tick   |   big   |    1.0     | 42.09 |
+---------------+---------+------------+-------+

+---------------+-------------+------------+
|    kernel     |    type     | count_perc |
+---------------+-------------+------------+
|      teo      |  too deep   |   0.992    |
|      teo      | too shallow |   17.085   |
|   teo_tick    |  too deep   |   0.945    |
|   teo_tick    | too shallow |   15.236   |
+---------------+-------------+------------+

For the idle stuff here all 3 clusters shift a bit towards deeper idle
but the overall miss rate is lower across the board which is perfectly
fine.

TLDR:
Mostly no change for a busy workload, no change + better power for a UI
one. The patches make sense to me & the results look all right so no big
problems at this stage. I'll do more testing (including the RFC you sent
out a moment ago) over the next few days and send those out as well.

Short of bumping into any other problems along the way, feel free to
grab this if you'd like:
Reviewed-and-tested-by: Kajetan Puchalski <kajetan.puchalski@arm.com>

Re: [PATCH v3 0/3] cpuidle: teo: Avoid stopping scheduler tick too often

[Rafael J. Wysocki]

On Tue, Aug 1, 2023 at 11:53 PM Kajetan Puchalski
<kajetan.puchalski@arm.com> wrote:
>
> Hi Rafael,
>
> > Hi Folks,
> >
> > Patch [1/3] in this series is a v3 of this patch posted last week:
> >
> > https://lore.kernel.org/linux-pm/4506480.LvFx2qVVIh@kreacher/
> >
> > Patch [2/3] (this is the second version of it) addresses some bail out paths
> > in teo_select() in which the scheduler tick may be stopped unnecessarily too.
> >
> > Patch [3/3] replaces a structure field with a local variable (while at it)
> > and it is the same as its previous version.
> >
> > According to this message:
> >
> > https://lore.kernel.org/linux-pm/CAJZ5v0jJxHj65r2HXBTd3wfbZtsg=_StzwO1kA5STDnaPe_dWA@mail.gmail.com/
> >
> > this series significantly reduces the number of cases in which the governor
> > requests stopping the tick when the selected idle state is shallow, which is
> > incorrect.
> >
> > Thanks!
> >
> >
>
> I did some initial testing with this on Android (Pixel 6, Android 13).
>
> 1. Geekbench 6
>
> +---------------------------+---------------+-----------------+
> |          metric           |      teo      |     teo_tick    |
> +---------------------------+---------------+-----------------+
> |      multicore_score      | 3320.9 (0.0%) | 3303.3 (-0.53%) |
> |           score           | 1415.7 (0.0%) | 1417.7 (0.14%)  |
> |      CPU_total_power      | 2421.3 (0.0%) | 2429.3 (0.33%)  |
> |  latency (AsyncTask #1)   | 49.41μ (0.0%) | 51.07μ (3.36%)  |
> | latency (labs.geekbench6) | 65.63μ (0.0%) | 77.47μ (18.03%) |
> | latency (surfaceflinger)  | 39.46μ (0.0%) | 36.94μ (-6.39%) |
> +---------------------------+---------------+-----------------+
>
> So the big picture for this workload looks roughly the same, the
> differences are too small for me to be confident in saying that the
> score/power difference is the result of the patches and not something
> random in the system.
> Same with the latency, the difference for labs.gb6 stands out but that's
> a pretty irrelevant task that sets up the benchmark, not the benchmark
> itself so not the biggest deal I think.
>
> +---------------+---------+------------+--------+
> |     kernel    | cluster | idle_state |  time  |
> +---------------+---------+------------+--------+
> |      teo      | little  |    0.0     | 146.75 |
> |      teo      | little  |    1.0     | 53.75  |
> |    teo_tick   | little  |    0.0     |  63.5  |
> |    teo_tick   | little  |    1.0     | 146.78 |
> +---------------+---------+------------+--------+
>
> +---------------+-------------+------------+
> |     kernel    |    type     | count_perc |
> +---------------+-------------+------------+
> |   teo         |  too deep   |   2.034    |
> |   teo         | too shallow |   15.791   |
> |   teo_tick    |  too deep   |    2.16    |
> |   teo_tick    | too shallow |   20.881   |
> +---------------+-------------+------------+
>
> The difference shows up in the idle numbers themselves, looks like we
> get a big shift towards deeper idle on our efficiency cores (little
> cluster) and more missed wakeups overall, both too deep & too shallow.
>
> Notably, the percentage of too shallow sleeps on the performance cores has
> more or less doubled (2% + 0.8% -> 4.3% + 1.8%). This doesn't
> necessarily have to be an issue but I'll do more testing just in case.
>
> 2. JetNews (Light UI workload)
>
> +------------------+---------------+----------------+
> |      metric      |      teo      |    teo_tick    |
> +------------------+---------------+----------------+
> |       fps        |  86.2 (0.0%)  |  86.4 (0.16%)  |
> |     janks_pc     |  0.8 (0.0%)   |  0.8 (-0.00%)  |
> | CPU_total_power  | 185.2 (0.0%)  | 178.2 (-3.76%) |
> +------------------+---------------+----------------+
>
> For the UI side, the frame data comes out the same on both variants but
> alongside better power usage which is nice to have.
>
> +---------------+---------+------------+-------+
> |    kernel     | cluster | idle_state | time  |
> +---------------+---------+------------+-------+
> |      teo      | little  |    0.0     | 25.06 |
> |      teo      | little  |    1.0     | 12.21 |
> |      teo      |   mid   |    0.0     | 38.32 |
> |      teo      |   mid   |    1.0     | 17.82 |
> |      teo      |   big   |    0.0     | 30.45 |
> |      teo      |   big   |    1.0     | 38.5  |
> |    teo_tick   | little  |    0.0     | 23.18 |
> |    teo_tick   | little  |    1.0     | 14.21 |
> |    teo_tick   |   mid   |    0.0     | 36.31 |
> |    teo_tick   |   mid   |    1.0     | 19.88 |
> |    teo_tick   |   big   |    0.0     | 27.13 |
> |    teo_tick   |   big   |    1.0     | 42.09 |
> +---------------+---------+------------+-------+
>
> +---------------+-------------+------------+
> |    kernel     |    type     | count_perc |
> +---------------+-------------+------------+
> |      teo      |  too deep   |   0.992    |
> |      teo      | too shallow |   17.085   |
> |   teo_tick    |  too deep   |   0.945    |
> |   teo_tick    | too shallow |   15.236   |
> +---------------+-------------+------------+
>
> For the idle stuff here all 3 clusters shift a bit towards deeper idle
> but the overall miss rate is lower across the board which is perfectly
> fine.
>
> TLDR:
> Mostly no change for a busy workload, no change + better power for a UI
> one. The patches make sense to me & the results look all right so no big
> problems at this stage. I'll do more testing (including the RFC you sent
> out a moment ago) over the next few days and send those out as well.
>
> Short of bumping into any other problems along the way, feel free to
> grab this if you'd like:
> Reviewed-and-tested-by: Kajetan Puchalski <kajetan.puchalski@arm.com>

Thank you!