Skip to contentSkip to conversation

cpuidle,teo: Improve TEO vs NOHZ

RFC PATCH In review Peter Zijlstra 2 participants 7 messages Aug 2, 2023 – Aug 3, 2023

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v2 cover cpuidle,teo: Improve TEO vs NOHZ

Patches attempting to solve the TEO tick/nohz vs timer-pull issue.

Very lightly tested..

Since last time:

- 'split' tick_nohz_get_sleep_length()
- replaced the tick heuristic

#1 lore raw

RFC PATCH v2 1/5 tick/nohz: Introduce tick_get_sleep_length()

Add a variant of tick_nohz_get_sleep_length() that conditionally does the NOHZ part.

tick_get_sleep_length(false) returns the delta_next return value of tick_nohz_get_sleep_length(), while tick_get_sleep_length(true) returns the regular return of tick_nohz_get_sleep_length().

This allows eliding tick_nohz_next_event() -- which is going to be expensive with timer-pull.

---
 include/linux/tick.h     |    5 +++++
 kernel/time/tick-sched.c |   35 +++++++++++++++++++++++------------
 2 files changed, 28 insertions(+), 12 deletions(-)
include/linux/tick.h +5 -0
@@ -136,6 +136,7 @@ extern void tick_nohz_irq_exit(void);
 extern bool tick_nohz_idle_got_tick(void);
 extern ktime_t tick_nohz_get_next_hrtimer(void);
 extern ktime_t tick_nohz_get_sleep_length(ktime_t *delta_next);
+extern ktime_t tick_get_sleep_length(bool nohz);
 extern unsigned long tick_nohz_get_idle_calls(void);
 extern unsigned long tick_nohz_get_idle_calls_cpu(int cpu);
 extern u64 get_cpu_idle_time_us(int cpu, u64 *last_update_time);
@@ -168,6 +169,10 @@ static inline ktime_t tick_nohz_get_slee
 	*delta_next = TICK_NSEC;
 	return *delta_next;
 }
+static inline ktime_t tick_get_sleep_length(bool nohz)
+{
+	return TICK_NSEC;
+}
 static inline u64 get_cpu_idle_time_us(int cpu, u64 *unused) { return -1; }
 static inline u64 get_cpu_iowait_time_us(int cpu, u64 *unused) { return -1; }
 
kernel/time/tick-sched.c +23 -12
@@ -1218,17 +1218,7 @@ ktime_t tick_nohz_get_next_hrtimer(void)
 	return __this_cpu_read(tick_cpu_device.evtdev)->next_event;
 }
 
-/**
- * tick_nohz_get_sleep_length - return the expected length of the current sleep
- * @delta_next: duration until the next event if the tick cannot be stopped
- *
- * Called from power state control code with interrupts disabled.
- *
- * The return value of this function and/or the value returned by it through the
- * @delta_next pointer can be negative which must be taken into account by its
- * callers.
- */
-ktime_t tick_nohz_get_sleep_length(ktime_t *delta_next)
+static ktime_t __tick_nohz_get_sleep_length(ktime_t *delta_next, bool nohz)
 {
 	struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);
 	struct tick_sched *ts = this_cpu_ptr(&tick_cpu_sched);
@@ -1244,7 +1234,7 @@ ktime_t tick_nohz_get_sleep_length(ktime
 
 	*delta_next = ktime_sub(dev->next_event, now);
 
-	if (!can_stop_idle_tick(cpu, ts))
+	if (!nohz || !can_stop_idle_tick(cpu, ts))
 		return *delta_next;
 
 	next_event = tick_nohz_next_event(ts, cpu);
@@ -1262,6 +1252,27 @@ ktime_t tick_nohz_get_sleep_length(ktime
 }
 
 /**
+ * tick_nohz_get_sleep_length - return the expected length of the current sleep
+ * @delta_next: duration until the next event if the tick cannot be stopped
+ *
+ * Called from power state control code with interrupts disabled.
+ *
+ * The return value of this function and/or the value returned by it through the
+ * @delta_next pointer can be negative which must be taken into account by its
+ * callers.
+ */
+ktime_t tick_nohz_get_sleep_length(ktime_t *delta_next)
+{
+	return __tick_nohz_get_sleep_length(delta_next, true);
+}
+
+ktime_t tick_get_sleep_length(bool nohz)
+{
+	ktime_t delta;
+	return __tick_nohz_get_sleep_length(&delta, nohz);
+}
+
+/**
  * tick_nohz_get_idle_calls_cpu - return the current idle calls counter value
  * for a particular CPU.
  *
#2 lore raw

RFC PATCH v2 2/5 cpuidle: Inject tick boundary state

In reply to Peter Zijlstra

In order to facilitate governors that track history in idle-state buckets (TEO) making a useful decision about NOHZ, make sure we have a bucket that counts tick-and-longer.

In order to be inclusive of the tick itself -- after all, if we do not disable NOHZ we'll sleep for a full tick, the actual boundary should be just short of a full tick.

IOW, when registering the idle-states, add one that is always disabled, just to have a bucket.

---
 drivers/cpuidle/cpuidle.h |    2 +
 drivers/cpuidle/driver.c  |   48 +++++++++++++++++++++++++++++++++++++++++++++-
 include/linux/cpuidle.h   |    2 -
 3 files changed, 50 insertions(+), 2 deletions(-)
drivers/cpuidle/cpuidle.h +2 -0
@@ -72,4 +72,6 @@ static inline void cpuidle_coupled_unreg
 }
 #endif
 
+#define SHORT_TICK_NSEC (TICK_NSEC - TICK_NSEC/32)
+
 #endif /* __DRIVER_CPUIDLE_H */
drivers/cpuidle/driver.c +47 -1

72 lines not on this page · raw message

include/linux/cpuidle.h +1 -1
@@ -16,7 +16,7 @@
 #include <linux/hrtimer.h>
 #include <linux/context_tracking.h>
 
-#define CPUIDLE_STATE_MAX	10
+#define CPUIDLE_STATE_MAX	16
 #define CPUIDLE_NAME_LEN	16
 #define CPUIDLE_DESC_LEN	32
 
#3 lore raw

RFC PATCH v2 3/5 cpuidle/teo: Simplify a little

In reply to Peter Zijlstra

Remove some of the early exit cases that rely on state_count, since we have the additional tick state. Declutters some of the next patches, can possibly be re-instated later if desired.

---
 drivers/cpuidle/governors/teo.c |   31 +------------------------------
 1 file changed, 1 insertion(+), 30 deletions(-)
drivers/cpuidle/governors/teo.c +1 -30
@@ -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);
@@ -379,33 +377,6 @@ static int teo_select(struct cpuidle_dri
 	duration_ns = tick_nohz_get_sleep_length(&delta_tick);
 	cpu_data->sleep_length_ns = duration_ns;
 
-	/* Check if there is any choice in the first place. */
-	if (drv->state_count < 2) {
-		idx = 0;
-		goto end;
-	}
-	if (!dev->states_usage[0].disable) {
-		idx = 0;
-		if (drv->states[1].target_residency_ns > duration_ns)
-			goto end;
-	}
-
-	cpu_data->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) {
-		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;
-			}
-		}
-	}
-
 	/*
 	 * Find the deepest idle state whose target residency does not exceed
 	 * the current sleep length and the deepest idle state not deeper than
@@ -541,7 +512,7 @@ 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
 	 */
-	if (cpu_data->utilized)
+	if (teo_cpu_is_utilized(dev->cpu, cpu_data))
 		idx = teo_find_shallower_state(drv, dev, idx, duration_ns, true);
 
 end:
#4 lore raw

Re: [RFC][PATCH v2 3/5] cpuidle/teo: Simplify a little

Quoted 3 lines · Peter Zijlstra

Remove some of the early exit cases that rely on state_count, since we have the additional tick state. Declutters some of the next patches, can possibly be re-instated later if desired.

How does having that added tick state compensate for not checking the amount of states that the governor can choose from in the first place?

[...]

Quoted 16 lines
drivers/cpuidle/governors/teo.c +0 -16
-	/* Check if there is any choice in the first place. */
-	if (drv->state_count < 2) {
-		idx = 0;
-		goto end;
-	}
-	if (!dev->states_usage[0].disable) {
-		idx = 0;
-		if (drv->states[1].target_residency_ns > duration_ns)
-			goto end;
-	}
-
-	cpu_data->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.

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

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

What exactly is the benefit of removing this part? On systems with 2 idle states this will just make the governor pointlessly execute the metrics code when the result is already known regardless. Seems like pure added overhead.

Quoted 15 lines
drivers/cpuidle/governors/teo.c +1 -2
-
 	/*
 	 * Find the deepest idle state whose target residency does not exceed
 	 * the current sleep length and the deepest idle state not deeper than
@@ -541,7 +512,7 @@ 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
 	 */
-	if (cpu_data->utilized)
+	if (teo_cpu_is_utilized(dev->cpu, cpu_data))
 		idx = teo_find_shallower_state(drv, dev, idx, duration_ns, true);
 
 end:
#5 lore raw

RFC PATCH v2 4/5 cpuidle/teo: Avoid tick_nohz_next_event()

In reply to Peter Zijlstra

Use the new tick_get_sleep_length() call in conjunction with the new TICK state to elide tick_nohz_next_event() when possible.

Specifically, start the state selection using the existing next timer (tick or earlier). And only when state selection lands on the TICK state ask for the NOHZ next timer.

---
 drivers/cpuidle/governors/teo.c |   21 +++++++++++++++------
 1 file changed, 15 insertions(+), 6 deletions(-)
drivers/cpuidle/governors/teo.c +15 -6
@@ -139,6 +139,7 @@
 #include <linux/sched/clock.h>
 #include <linux/sched/topology.h>
 #include <linux/tick.h>
+#include "../cpuidle.h"
 
 /*
  * The number of bits to shift the CPU's capacity by in order to determine
@@ -363,8 +364,7 @@ static int teo_select(struct cpuidle_dri
 	int constraint_idx = 0;
 	int idx0 = 0, idx = -1;
 	bool alt_intercepts, alt_recent;
-	ktime_t delta_tick;
-	s64 duration_ns;
+	s64 duration_ns, tick_ns;
 	int i;
 
 	if (dev->last_state_idx >= 0) {
@@ -374,8 +374,7 @@ static int teo_select(struct cpuidle_dri
 
 	cpu_data->time_span_ns = local_clock();
 
-	duration_ns = tick_nohz_get_sleep_length(&delta_tick);
-	cpu_data->sleep_length_ns = duration_ns;
+	duration_ns = tick_ns = tick_get_sleep_length(false);
 
 	/*
 	 * Find the deepest idle state whose target residency does not exceed
@@ -407,6 +406,14 @@ static int teo_select(struct cpuidle_dri
 		if (s->target_residency_ns > duration_ns)
 			break;
 
+		if (s->target_residency_ns == SHORT_TICK_NSEC) {
+			/*
+			 * We hit the tick state, see if it makes sense to
+			 * disable the tick and go deeper still.
+			 */
+			duration_ns = tick_get_sleep_length(true);
+		}
+
 		idx = i;
 
 		if (s->exit_latency_ns <= latency_req)
@@ -417,6 +424,8 @@ static int teo_select(struct cpuidle_dri
 		idx_recent_sum = recent_sum;
 	}
 
+	cpu_data->sleep_length_ns = duration_ns;
+
 	/* Avoid unnecessary overhead. */
 	if (idx < 0) {
 		idx = 0; /* No states enabled, must use 0. */
@@ -531,8 +540,8 @@ static int teo_select(struct cpuidle_dri
 		 * that.
 		 */
 		if (idx > idx0 &&
-		    drv->states[idx].target_residency_ns > delta_tick)
-			idx = teo_find_shallower_state(drv, dev, idx, delta_tick, false);
+		    drv->states[idx].target_residency_ns > tick_ns)
+			idx = teo_find_shallower_state(drv, dev, idx, tick_ns, false);
 	}
 
 	return idx;
#6 lore raw

RFC PATCH v2 5/5 cpuidle,teo: Improve state selection

In reply to Peter Zijlstra

When selecting a state, stop when history tells us 66% of recent idles were at or below our current state.

---
 drivers/cpuidle/governors/teo.c |    6 ++++++
 1 file changed, 6 insertions(+)
drivers/cpuidle/governors/teo.c +6 -0
@@ -361,6 +361,7 @@ static int teo_select(struct cpuidle_dri
 	unsigned int recent_sum = 0;
 	unsigned int idx_hit_sum = 0;
 	unsigned int hit_sum = 0;
+	unsigned int thresh_sum = 0;
 	int constraint_idx = 0;
 	int idx0 = 0, idx = -1;
 	bool alt_intercepts, alt_recent;
@@ -376,6 +377,8 @@ static int teo_select(struct cpuidle_dri
 
 	duration_ns = tick_ns = tick_get_sleep_length(false);
 
+	thresh_sum = 2 * cpu_data->total / 3; /* 66% */
+
 	/*
 	 * Find the deepest idle state whose target residency does not exceed
 	 * the current sleep length and the deepest idle state not deeper than
@@ -406,6 +409,9 @@ static int teo_select(struct cpuidle_dri
 		if (s->target_residency_ns > duration_ns)
 			break;
 
+		if (intercept_sum + hit_sum > thresh_sum)
+			break;
+
 		if (s->target_residency_ns == SHORT_TICK_NSEC) {
 			/*
 			 * We hit the tick state, see if it makes sense to