1 // SPDX-License-Identifier: GPL-2.0
3 * Timer events oriented CPU idle governor
5 * Copyright (C) 2018 Intel Corporation
6 * Author: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
8 * The idea of this governor is based on the observation that on many systems
9 * timer events are two or more orders of magnitude more frequent than any
10 * other interrupts, so they are likely to be the most significant source of CPU
11 * wakeups from idle states. Moreover, information about what happened in the
12 * (relatively recent) past can be used to estimate whether or not the deepest
13 * idle state with target residency within the time to the closest timer is
14 * likely to be suitable for the upcoming idle time of the CPU and, if not, then
15 * which of the shallower idle states to choose.
17 * Of course, non-timer wakeup sources are more important in some use cases and
18 * they can be covered by taking a few most recent idle time intervals of the
19 * CPU into account. However, even in that case it is not necessary to consider
20 * idle duration values greater than the time till the closest timer, as the
21 * patterns that they may belong to produce average values close enough to
22 * the time till the closest timer (sleep length) anyway.
24 * Thus this governor estimates whether or not the upcoming idle time of the CPU
25 * is likely to be significantly shorter than the sleep length and selects an
26 * idle state for it in accordance with that, as follows:
28 * - Find an idle state on the basis of the sleep length and state statistics
29 * collected over time:
31 * o Find the deepest idle state whose target residency is less than or equal
32 * to the sleep length.
34 * o Select it if it matched both the sleep length and the observed idle
35 * duration in the past more often than it matched the sleep length alone
36 * (i.e. the observed idle duration was significantly shorter than the sleep
37 * length matched by it).
39 * o Otherwise, select the shallower state with the greatest matched "early"
42 * - If the majority of the most recent idle duration values are below the
43 * target residency of the idle state selected so far, use those values to
44 * compute the new expected idle duration and find an idle state matching it
45 * (which has to be shallower than the one selected so far).
48 #include <linux/cpuidle.h>
49 #include <linux/jiffies.h>
50 #include <linux/kernel.h>
51 #include <linux/sched/clock.h>
52 #include <linux/tick.h>
55 * The PULSE value is added to metrics when they grow and the DECAY_SHIFT value
56 * is used for decreasing metrics on a regular basis.
62 * Number of the most recent idle duration values to take into consideration for
63 * the detection of wakeup patterns.
68 * struct teo_idle_state - Idle state data used by the TEO cpuidle governor.
69 * @early_hits: "Early" CPU wakeups "matching" this state.
70 * @hits: "On time" CPU wakeups "matching" this state.
71 * @misses: CPU wakeups "missing" this state.
73 * A CPU wakeup is "matched" by a given idle state if the idle duration measured
74 * after the wakeup is between the target residency of that state and the target
75 * residency of the next one (or if this is the deepest available idle state, it
76 * "matches" a CPU wakeup when the measured idle duration is at least equal to
77 * its target residency).
79 * Also, from the TEO governor perspective, a CPU wakeup from idle is "early" if
80 * it occurs significantly earlier than the closest expected timer event (that
81 * is, early enough to match an idle state shallower than the one matching the
82 * time till the closest timer event). Otherwise, the wakeup is "on time", or
85 * A "miss" occurs when the given state doesn't match the wakeup, but it matches
86 * the time till the closest timer event used for idle state selection.
88 struct teo_idle_state {
89 unsigned int early_hits;
95 * struct teo_cpu - CPU data used by the TEO cpuidle governor.
96 * @time_span_ns: Time between idle state selection and post-wakeup update.
97 * @sleep_length_ns: Time till the closest timer event (at the selection time).
98 * @states: Idle states data corresponding to this CPU.
99 * @interval_idx: Index of the most recent saved idle interval.
100 * @intervals: Saved idle duration values.
105 struct teo_idle_state states[CPUIDLE_STATE_MAX];
107 unsigned int intervals[INTERVALS];
110 static DEFINE_PER_CPU(struct teo_cpu, teo_cpus);
113 * teo_update - Update CPU data after wakeup.
114 * @drv: cpuidle driver containing state data.
117 static void teo_update(struct cpuidle_driver *drv, struct cpuidle_device *dev)
119 struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
120 unsigned int sleep_length_us = ktime_to_us(cpu_data->sleep_length_ns);
121 int i, idx_hit = -1, idx_timer = -1;
122 unsigned int measured_us;
124 if (cpu_data->time_span_ns >= cpu_data->sleep_length_ns) {
126 * One of the safety nets has triggered or the wakeup was close
127 * enough to the closest timer event expected at the idle state
128 * selection time to be discarded.
130 measured_us = UINT_MAX;
134 lat = drv->states[dev->last_state_idx].exit_latency;
136 measured_us = ktime_to_us(cpu_data->time_span_ns);
138 * The delay between the wakeup and the first instruction
139 * executed by the CPU is not likely to be worst-case every
140 * time, so take 1/2 of the exit latency as a very rough
141 * approximation of the average of it.
143 if (measured_us >= lat)
144 measured_us -= lat / 2;
150 * Decay the "early hits" metric for all of the states and find the
151 * states matching the sleep length and the measured idle duration.
153 for (i = 0; i < drv->state_count; i++) {
154 unsigned int early_hits = cpu_data->states[i].early_hits;
156 cpu_data->states[i].early_hits -= early_hits >> DECAY_SHIFT;
158 if (drv->states[i].target_residency <= sleep_length_us) {
160 if (drv->states[i].target_residency <= measured_us)
166 * Update the "hits" and "misses" data for the state matching the sleep
167 * length. If it matches the measured idle duration too, this is a hit,
168 * so increase the "hits" metric for it then. Otherwise, this is a
169 * miss, so increase the "misses" metric for it. In the latter case
170 * also increase the "early hits" metric for the state that actually
171 * matches the measured idle duration.
173 if (idx_timer >= 0) {
174 unsigned int hits = cpu_data->states[idx_timer].hits;
175 unsigned int misses = cpu_data->states[idx_timer].misses;
177 hits -= hits >> DECAY_SHIFT;
178 misses -= misses >> DECAY_SHIFT;
180 if (idx_timer > idx_hit) {
183 cpu_data->states[idx_hit].early_hits += PULSE;
188 cpu_data->states[idx_timer].misses = misses;
189 cpu_data->states[idx_timer].hits = hits;
193 * Save idle duration values corresponding to non-timer wakeups for
196 cpu_data->intervals[cpu_data->interval_idx++] = measured_us;
197 if (cpu_data->interval_idx > INTERVALS)
198 cpu_data->interval_idx = 0;
202 * teo_find_shallower_state - Find shallower idle state matching given duration.
203 * @drv: cpuidle driver containing state data.
205 * @state_idx: Index of the capping idle state.
206 * @duration_us: Idle duration value to match.
208 static int teo_find_shallower_state(struct cpuidle_driver *drv,
209 struct cpuidle_device *dev, int state_idx,
210 unsigned int duration_us)
214 for (i = state_idx - 1; i >= 0; i--) {
215 if (drv->states[i].disabled || dev->states_usage[i].disable)
219 if (drv->states[i].target_residency <= duration_us)
226 * teo_select - Selects the next idle state to enter.
227 * @drv: cpuidle driver containing state data.
229 * @stop_tick: Indication on whether or not to stop the scheduler tick.
231 static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
234 struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
235 int latency_req = cpuidle_governor_latency_req(dev->cpu);
236 unsigned int duration_us, count;
237 int max_early_idx, constraint_idx, idx, i;
240 if (dev->last_state_idx >= 0) {
241 teo_update(drv, dev);
242 dev->last_state_idx = -1;
245 cpu_data->time_span_ns = local_clock();
247 cpu_data->sleep_length_ns = tick_nohz_get_sleep_length(&delta_tick);
248 duration_us = ktime_to_us(cpu_data->sleep_length_ns);
252 constraint_idx = drv->state_count;
255 for (i = 0; i < drv->state_count; i++) {
256 struct cpuidle_state *s = &drv->states[i];
257 struct cpuidle_state_usage *su = &dev->states_usage[i];
259 if (s->disabled || su->disable) {
261 * If the "early hits" metric of a disabled state is
262 * greater than the current maximum, it should be taken
263 * into account, because it would be a mistake to select
264 * a deeper state with lower "early hits" metric. The
265 * index cannot be changed to point to it, however, so
266 * just increase the max count alone and let the index
267 * still point to a shallower idle state.
269 if (max_early_idx >= 0 &&
270 count < cpu_data->states[i].early_hits)
271 count = cpu_data->states[i].early_hits;
277 idx = i; /* first enabled state */
279 if (s->target_residency > duration_us)
282 if (s->exit_latency > latency_req && constraint_idx > i)
287 if (count < cpu_data->states[i].early_hits &&
288 !(tick_nohz_tick_stopped() &&
289 drv->states[i].target_residency < TICK_USEC)) {
290 count = cpu_data->states[i].early_hits;
296 * If the "hits" metric of the idle state matching the sleep length is
297 * greater than its "misses" metric, that is the one to use. Otherwise,
298 * it is more likely that one of the shallower states will match the
299 * idle duration observed after wakeup, so take the one with the maximum
300 * "early hits" metric, but if that cannot be determined, just use the
301 * state selected so far.
303 if (cpu_data->states[idx].hits <= cpu_data->states[idx].misses &&
304 max_early_idx >= 0) {
306 duration_us = drv->states[idx].target_residency;
310 * If there is a latency constraint, it may be necessary to use a
311 * shallower idle state than the one selected so far.
313 if (constraint_idx < idx)
314 idx = constraint_idx;
317 idx = 0; /* No states enabled. Must use 0. */
318 } else if (idx > 0) {
324 * Count and sum the most recent idle duration values less than
325 * the current expected idle duration value.
327 for (i = 0; i < INTERVALS; i++) {
328 unsigned int val = cpu_data->intervals[i];
330 if (val >= duration_us)
338 * Give up unless the majority of the most recent idle duration
339 * values are in the interesting range.
341 if (count > INTERVALS / 2) {
342 unsigned int avg_us = div64_u64(sum, count);
345 * Avoid spending too much time in an idle state that
346 * would be too shallow.
348 if (!(tick_nohz_tick_stopped() && avg_us < TICK_USEC)) {
349 duration_us = avg_us;
350 if (drv->states[idx].target_residency > avg_us)
351 idx = teo_find_shallower_state(drv, dev,
358 * Don't stop the tick if the selected state is a polling one or if the
359 * expected idle duration is shorter than the tick period length.
361 if (((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) ||
362 duration_us < TICK_USEC) && !tick_nohz_tick_stopped()) {
363 unsigned int delta_tick_us = ktime_to_us(delta_tick);
368 * The tick is not going to be stopped, so if the target
369 * residency of the state to be returned is not within the time
370 * till the closest timer including the tick, try to correct
373 if (idx > 0 && drv->states[idx].target_residency > delta_tick_us)
374 idx = teo_find_shallower_state(drv, dev, idx, delta_tick_us);
381 * teo_reflect - Note that governor data for the CPU need to be updated.
383 * @state: Entered state.
385 static void teo_reflect(struct cpuidle_device *dev, int state)
387 struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
389 dev->last_state_idx = state;
391 * If the wakeup was not "natural", but triggered by one of the safety
392 * nets, assume that the CPU might have been idle for the entire sleep
395 if (dev->poll_time_limit ||
396 (tick_nohz_idle_got_tick() && cpu_data->sleep_length_ns > TICK_NSEC)) {
397 dev->poll_time_limit = false;
398 cpu_data->time_span_ns = cpu_data->sleep_length_ns;
400 cpu_data->time_span_ns = local_clock() - cpu_data->time_span_ns;
405 * teo_enable_device - Initialize the governor's data for the target CPU.
406 * @drv: cpuidle driver (not used).
409 static int teo_enable_device(struct cpuidle_driver *drv,
410 struct cpuidle_device *dev)
412 struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
415 memset(cpu_data, 0, sizeof(*cpu_data));
417 for (i = 0; i < INTERVALS; i++)
418 cpu_data->intervals[i] = UINT_MAX;
423 static struct cpuidle_governor teo_governor = {
426 .enable = teo_enable_device,
427 .select = teo_select,
428 .reflect = teo_reflect,
431 static int __init teo_governor_init(void)
433 return cpuidle_register_governor(&teo_governor);
436 postcore_initcall(teo_governor_init);