teo.c

  1// SPDX-License-Identifier: GPL-2.0
  2/*
  3 * Timer events oriented CPU idle governor
  4 *
  5 * Copyright (C) 2018 - 2021 Intel Corporation
  6 * Author: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
  7 */
  8
  9/**
 10 * DOC: teo-description
 11 *
 12 * The idea of this governor is based on the observation that on many systems
 13 * timer interrupts are two or more orders of magnitude more frequent than any
 14 * other interrupt types, so they are likely to dominate CPU wakeup patterns.
 15 * Moreover, in principle, the time when the next timer event is going to occur
 16 * can be determined at the idle state selection time, although doing that may
 17 * be costly, so it can be regarded as the most reliable source of information
 18 * for idle state selection.
 19 *
 20 * Of course, non-timer wakeup sources are more important in some use cases,
 21 * but even then it is generally unnecessary to consider idle duration values
 22 * greater than the time till the next timer event, referred as the sleep
 23 * length in what follows, because the closest timer will ultimately wake up the
 24 * CPU anyway unless it is woken up earlier.
 25 *
 26 * However, since obtaining the sleep length may be costly, the governor first
 27 * checks if it can select a shallow idle state using wakeup pattern information
 28 * from recent times, in which case it can do without knowing the sleep length
 29 * at all.  For this purpose, it counts CPU wakeup events and looks for an idle
 30 * state whose target residency has not exceeded the idle duration (measured
 31 * after wakeup) in the majority of relevant recent cases.  If the target
 32 * residency of that state is small enough, it may be used right away and the
 33 * sleep length need not be determined.
 34 *
 35 * The computations carried out by this governor are based on using bins whose
 36 * boundaries are aligned with the target residency parameter values of the CPU
 37 * idle states provided by the %CPUIdle driver in the ascending order.  That is,
 38 * the first bin spans from 0 up to, but not including, the target residency of
 39 * the second idle state (idle state 1), the second bin spans from the target
 40 * residency of idle state 1 up to, but not including, the target residency of
 41 * idle state 2, the third bin spans from the target residency of idle state 2
 42 * up to, but not including, the target residency of idle state 3 and so on.
 43 * The last bin spans from the target residency of the deepest idle state
 44 * supplied by the driver to infinity.
 45 *
 46 * Two metrics called "hits" and "intercepts" are associated with each bin.
 47 * They are updated every time before selecting an idle state for the given CPU
 48 * in accordance with what happened last time.
 49 *
 50 * The "hits" metric reflects the relative frequency of situations in which the
 51 * sleep length and the idle duration measured after CPU wakeup fall into the
 52 * same bin (that is, the CPU appears to wake up "on time" relative to the sleep
 53 * length).  In turn, the "intercepts" metric reflects the relative frequency of
 54 * non-timer wakeup events for which the measured idle duration falls into a bin
 55 * that corresponds to an idle state shallower than the one whose bin is fallen
 56 * into by the sleep length (these events are also referred to as "intercepts"
 57 * below).
 58 *
 59 * The governor also counts "intercepts" with the measured idle duration below
 60 * the tick period length and uses this information when deciding whether or not
 61 * to stop the scheduler tick.
 62 *
 63 * In order to select an idle state for a CPU, the governor takes the following
 64 * steps (modulo the possible latency constraint that must be taken into account
 65 * too):
 66 *
 67 * 1. Find the deepest enabled CPU idle state (the candidate idle state) and
 68 *    compute 2 sums as follows:
 69 *
 70 *    - The sum of the "hits" metric for all of the idle states shallower than
 71 *      the candidate one (it represents the cases in which the CPU was likely
 72 *      woken up by a timer).
 73 *
 74 *    - The sum of the "intercepts" metric for all of the idle states shallower
 75 *      than the candidate one (it represents the cases in which the CPU was
 76 *      likely woken up by a non-timer wakeup source).
 77 *
 78 * 2. If the second sum computed in step 1 is greater than a half of the sum of
 79 *    both metrics for the candidate state bin and all subsequent bins (if any),
 80 *    a shallower idle state is likely to be more suitable, so look for it.
 81 *
 82 *    - Traverse the enabled idle states shallower than the candidate one in the
 83 *      descending order.
 84 *
 85 *    - For each of them compute the sum of the "intercepts" metrics over all
 86 *      of the idle states between it and the candidate one (including the
 87 *      former and excluding the latter).
 88 *
 89 *    - If this sum is greater than a half of the second sum computed in step 1,
 90 *      use the given idle state as the new candidate one.
 91 *
 92 * 3. If the current candidate state is state 0 or its target residency is short
 93 *    enough, return it and prevent the scheduler tick from being stopped.
 94 *
 95 * 4. Obtain the sleep length value and check if it is below the target
 96 *    residency of the current candidate state, in which case a new shallower
 97 *    candidate state needs to be found, so look for it.
 98 */
 99
100#include <linux/cpuidle.h>
101#include <linux/jiffies.h>
102#include <linux/kernel.h>
103#include <linux/sched/clock.h>
104#include <linux/tick.h>
105
106#include "gov.h"
107
108/*
109 * Idle state exit latency threshold used for deciding whether or not to check
110 * the time till the closest expected timer event.
111 */
112#define LATENCY_THRESHOLD_NS	(RESIDENCY_THRESHOLD_NS / 2)
113
114/*
115 * The PULSE value is added to metrics when they grow and the DECAY_SHIFT value
116 * is used for decreasing metrics on a regular basis.
117 */
118#define PULSE		1024
119#define DECAY_SHIFT	3
120
121/**
122 * struct teo_bin - Metrics used by the TEO cpuidle governor.
123 * @intercepts: The "intercepts" metric.
124 * @hits: The "hits" metric.
125 */
126struct teo_bin {
127	unsigned int intercepts;
128	unsigned int hits;
129};
130
131/**
132 * struct teo_cpu - CPU data used by the TEO cpuidle governor.
133 * @sleep_length_ns: Time till the closest timer event (at the selection time).
134 * @state_bins: Idle state data bins for this CPU.
135 * @total: Grand total of the "intercepts" and "hits" metrics for all bins.
136 * @total_tick: Wakeups by the scheduler tick.
137 * @tick_intercepts: "Intercepts" before TICK_NSEC.
138 * @short_idles: Wakeups after short idle periods.
139 * @tick_wakeup: Set if the last wakeup was by the scheduler tick.
140 */
141struct teo_cpu {
142	s64 sleep_length_ns;
143	struct teo_bin state_bins[CPUIDLE_STATE_MAX];
144	unsigned int total;
145	unsigned int total_tick;
146	unsigned int tick_intercepts;
147	unsigned int short_idles;
148	bool tick_wakeup;
149};
150
151static DEFINE_PER_CPU(struct teo_cpu, teo_cpus);
152
153static void teo_decay(unsigned int *metric)
154{
155	unsigned int delta = *metric >> DECAY_SHIFT;
156
157	if (delta)
158		*metric -= delta;
159	else
160		*metric = 0;
161}
162
163/**
164 * teo_update - Update CPU metrics after wakeup.
165 * @drv: cpuidle driver containing state data.
166 * @dev: Target CPU.
167 */
168static void teo_update(struct cpuidle_driver *drv, struct cpuidle_device *dev)
169{
170	struct teo_cpu *cpu_data = this_cpu_ptr(&teo_cpus);
171	int i, idx_timer = 0, idx_duration = 0;
172	s64 target_residency_ns, measured_ns;
173	unsigned int total = 0;
174
175	teo_decay(&cpu_data->short_idles);
176
177	if (dev->poll_time_limit) {
178		dev->poll_time_limit = false;
179		/*
180		 * Polling state timeout has triggered, so assume that this
181		 * might have been a long sleep.
182		 */
183		measured_ns = S64_MAX;
184	} else {
185		s64 lat_ns = drv->states[dev->last_state_idx].exit_latency_ns;
186
187		measured_ns = dev->last_residency_ns;
188		/*
189		 * The delay between the wakeup and the first instruction
190		 * executed by the CPU is not likely to be worst-case every
191		 * time, so take 1/2 of the exit latency as a very rough
192		 * approximation of the average of it.
193		 */
194		if (measured_ns >= lat_ns) {
195			measured_ns -= lat_ns / 2;
196			if (measured_ns < RESIDENCY_THRESHOLD_NS)
197				cpu_data->short_idles += PULSE;
198		} else {
199			measured_ns /= 2;
200			cpu_data->short_idles += PULSE;
201		}
202	}
203
204	/*
205	 * Decay the "hits" and "intercepts" metrics for all of the bins and
206	 * find the bins that the sleep length and the measured idle duration
207	 * fall into.
208	 */
209	for (i = 0; i < drv->state_count; i++) {
210		struct teo_bin *bin = &cpu_data->state_bins[i];
211
212		teo_decay(&bin->hits);
213		total += bin->hits;
214		teo_decay(&bin->intercepts);
215		total += bin->intercepts;
216
217		target_residency_ns = drv->states[i].target_residency_ns;
218
219		if (target_residency_ns <= cpu_data->sleep_length_ns) {
220			idx_timer = i;
221			if (target_residency_ns <= measured_ns)
222				idx_duration = i;
223		}
224	}
225
226	cpu_data->total = total + PULSE;
227
228	teo_decay(&cpu_data->tick_intercepts);
229
230	teo_decay(&cpu_data->total_tick);
231	if (cpu_data->tick_wakeup) {
232		cpu_data->total_tick += PULSE;
233		/*
234		 * If tick wakeups dominate the wakeup pattern, count this one
235		 * as a hit on the deepest available idle state to increase the
236		 * likelihood of stopping the tick.
237		 */
238		if (3 * cpu_data->total_tick > 2 * cpu_data->total) {
239			cpu_data->state_bins[drv->state_count-1].hits += PULSE;
240			return;
241		}
242	}
243
244	/*
245	 * If the measured idle duration falls into the same bin as the sleep
246	 * length, this is a "hit", so update the "hits" metric for that bin.
247	 * Otherwise, update the "intercepts" metric for the bin fallen into by
248	 * the measured idle duration.
249	 */
250	if (idx_timer == idx_duration) {
251		cpu_data->state_bins[idx_timer].hits += PULSE;
252	} else {
253		cpu_data->state_bins[idx_duration].intercepts += PULSE;
254		if (measured_ns <= TICK_NSEC)
255			cpu_data->tick_intercepts += PULSE;
256	}
257}
258
259/**
260 * teo_find_shallower_state - Find shallower idle state matching given duration.
261 * @drv: cpuidle driver containing state data.
262 * @dev: Target CPU.
263 * @state_idx: Index of the capping idle state.
264 * @duration_ns: Idle duration value to match.
265 */
266static int teo_find_shallower_state(struct cpuidle_driver *drv,
267				    struct cpuidle_device *dev, int state_idx,
268				    s64 duration_ns)
269{
270	int i;
271
272	for (i = state_idx - 1; i >= 0; i--) {
273		if (dev->states_usage[i].disable)
274			continue;
275
276		state_idx = i;
277		if (drv->states[i].target_residency_ns <= duration_ns)
278			break;
279	}
280	return state_idx;
281}
282
283/**
284 * teo_select - Selects the next idle state to enter.
285 * @drv: cpuidle driver containing state data.
286 * @dev: Target CPU.
287 * @stop_tick: Indication on whether or not to stop the scheduler tick.
288 */
289static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
290		      bool *stop_tick)
291{
292	struct teo_cpu *cpu_data = this_cpu_ptr(&teo_cpus);
293	s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
294	ktime_t delta_tick = TICK_NSEC / 2;
295	unsigned int idx_intercept_sum = 0;
296	unsigned int intercept_sum = 0;
297	unsigned int idx_hit_sum = 0;
298	unsigned int hit_sum = 0;
299	int constraint_idx = 0;
300	int idx0 = 0, idx = -1;
301	s64 duration_ns;
302	int i;
303
304	if (dev->last_state_idx >= 0) {
305		teo_update(drv, dev);
306		dev->last_state_idx = -1;
307	}
308
309	/*
310	 * Set the sleep length to infinity in case the invocation of
311	 * tick_nohz_get_sleep_length() below is skipped, in which case it won't
312	 * be known whether or not the subsequent wakeup is caused by a timer.
313	 * It is generally fine to count the wakeup as an intercept then, except
314	 * for the cases when the CPU is mostly woken up by timers and there may
315	 * be opportunities to ask for a deeper idle state when no imminent
316	 * timers are scheduled which may be missed.
317	 */
318	cpu_data->sleep_length_ns = KTIME_MAX;
319
320	/* Check if there is any choice in the first place. */
321	if (drv->state_count < 2) {
322		idx = 0;
323		goto out_tick;
324	}
325
326	if (!dev->states_usage[0].disable)
327		idx = 0;
328
329	/* Compute the sums of metrics for early wakeup pattern detection. */
330	for (i = 1; i < drv->state_count; i++) {
331		struct teo_bin *prev_bin = &cpu_data->state_bins[i-1];
332		struct cpuidle_state *s = &drv->states[i];
333
334		/*
335		 * Update the sums of idle state metrics for all of the states
336		 * shallower than the current one.
337		 */
338		intercept_sum += prev_bin->intercepts;
339		hit_sum += prev_bin->hits;
340
341		if (dev->states_usage[i].disable)
342			continue;
343
344		if (idx < 0)
345			idx0 = i; /* first enabled state */
346
347		idx = i;
348
349		if (s->exit_latency_ns <= latency_req)
350			constraint_idx = i;
351
352		/* Save the sums for the current state. */
353		idx_intercept_sum = intercept_sum;
354		idx_hit_sum = hit_sum;
355	}
356
357	/* Avoid unnecessary overhead. */
358	if (idx < 0) {
359		idx = 0; /* No states enabled, must use 0. */
360		goto out_tick;
361	}
362
363	if (idx == idx0) {
364		/*
365		 * Only one idle state is enabled, so use it, but do not
366		 * allow the tick to be stopped it is shallow enough.
367		 */
368		duration_ns = drv->states[idx].target_residency_ns;
369		goto end;
370	}
371
372	/*
373	 * If the sum of the intercepts metric for all of the idle states
374	 * shallower than the current candidate one (idx) is greater than the
375	 * sum of the intercepts and hits metrics for the candidate state and
376	 * all of the deeper states, a shallower idle state is likely to be a
377	 * better choice.
378	 */
379	if (2 * idx_intercept_sum > cpu_data->total - idx_hit_sum) {
380		int min_idx = idx0;
381
382		if (tick_nohz_tick_stopped()) {
383			/*
384			 * Look for the shallowest idle state below the current
385			 * candidate one whose target residency is at least
386			 * equal to the tick period length.
387			 */
388			while (min_idx < idx &&
389			       drv->states[min_idx].target_residency_ns < TICK_NSEC)
390				min_idx++;
391		}
392
393		/*
394		 * Look for the deepest idle state whose target residency had
395		 * not exceeded the idle duration in over a half of the relevant
396		 * cases in the past.
397		 *
398		 * Take the possible duration limitation present if the tick
399		 * has been stopped already into account.
400		 */
401		for (i = idx - 1, intercept_sum = 0; i >= min_idx; i--) {
402			intercept_sum += cpu_data->state_bins[i].intercepts;
403
404			if (dev->states_usage[i].disable)
405				continue;
406
407			idx = i;
408			if (2 * intercept_sum > idx_intercept_sum)
409				break;
410		}
411	}
412
413	/*
414	 * If there is a latency constraint, it may be necessary to select an
415	 * idle state shallower than the current candidate one.
416	 */
417	if (idx > constraint_idx)
418		idx = constraint_idx;
419
420	/*
421	 * If either the candidate state is state 0 or its target residency is
422	 * low enough, there is basically nothing more to do, but if the sleep
423	 * length is not updated, the subsequent wakeup will be counted as an
424	 * "intercept" which may be problematic in the cases when timer wakeups
425	 * are dominant.  Namely, it may effectively prevent deeper idle states
426	 * from being selected at one point even if no imminent timers are
427	 * scheduled.
428	 *
429	 * However, frequent timers in the RESIDENCY_THRESHOLD_NS range on one
430	 * CPU are unlikely (user space has a default 50 us slack value for
431	 * hrtimers and there are relatively few timers with a lower deadline
432	 * value in the kernel), and even if they did happen, the potential
433	 * benefit from using a deep idle state in that case would be
434	 * questionable anyway for latency reasons.  Thus if the measured idle
435	 * duration falls into that range in the majority of cases, assume
436	 * non-timer wakeups to be dominant and skip updating the sleep length
437	 * to reduce latency.
438	 *
439	 * Also, if the latency constraint is sufficiently low, it will force
440	 * shallow idle states regardless of the wakeup type, so the sleep
441	 * length need not be known in that case.
442	 */
443	if ((!idx || drv->states[idx].target_residency_ns < RESIDENCY_THRESHOLD_NS) &&
444	    (2 * cpu_data->short_idles >= cpu_data->total ||
445	     latency_req < LATENCY_THRESHOLD_NS))
446		goto out_tick;
447
448	duration_ns = tick_nohz_get_sleep_length(&delta_tick);
449	cpu_data->sleep_length_ns = duration_ns;
450
451	if (!idx)
452		goto out_tick;
453
454	/*
455	 * If the closest expected timer is before the target residency of the
456	 * candidate state, a shallower one needs to be found.
457	 */
458	if (drv->states[idx].target_residency_ns > duration_ns)
459		idx = teo_find_shallower_state(drv, dev, idx, duration_ns);
460
461	/*
462	 * If the selected state's target residency is below the tick length
463	 * and intercepts occurring before the tick length are the majority of
464	 * total wakeup events, do not stop the tick.
465	 */
466	if (drv->states[idx].target_residency_ns < TICK_NSEC &&
467	    cpu_data->tick_intercepts > cpu_data->total / 2 + cpu_data->total / 8)
468		duration_ns = TICK_NSEC / 2;
469
470end:
471	/*
472	 * Allow the tick to be stopped unless the selected state is a polling
473	 * one or the expected idle duration is shorter than the tick period
474	 * length.
475	 */
476	if ((!(drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
477	    duration_ns >= TICK_NSEC) || tick_nohz_tick_stopped())
478		return idx;
479
480	/*
481	 * The tick is not going to be stopped, so if the target residency of
482	 * the state to be returned is not within the time till the closest
483	 * timer including the tick, try to correct that.
484	 */
485	if (idx > idx0 &&
486	    drv->states[idx].target_residency_ns > delta_tick)
487		idx = teo_find_shallower_state(drv, dev, idx, delta_tick);
488
489out_tick:
490	*stop_tick = false;
491	return idx;
492}
493
494/**
495 * teo_reflect - Note that governor data for the CPU need to be updated.
496 * @dev: Target CPU.
497 * @state: Entered state.
498 */
499static void teo_reflect(struct cpuidle_device *dev, int state)
500{
501	struct teo_cpu *cpu_data = this_cpu_ptr(&teo_cpus);
502
503	cpu_data->tick_wakeup = tick_nohz_idle_got_tick();
504
505	dev->last_state_idx = state;
506}
507
508/**
509 * teo_enable_device - Initialize the governor's data for the target CPU.
510 * @drv: cpuidle driver (not used).
511 * @dev: Target CPU.
512 */
513static int teo_enable_device(struct cpuidle_driver *drv,
514			     struct cpuidle_device *dev)
515{
516	struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu);
517
518	memset(cpu_data, 0, sizeof(*cpu_data));
519
520	return 0;
521}
522
523static struct cpuidle_governor teo_governor = {
524	.name =		"teo",
525	.rating =	19,
526	.enable =	teo_enable_device,
527	.select =	teo_select,
528	.reflect =	teo_reflect,
529};
530
531static int __init teo_governor_init(void)
532{
533	return cpuidle_register_governor(&teo_governor);
534}
535
536postcore_initcall(teo_governor_init);