// SPDX-License-Identifier: GPL-2.0 /* * Timer events oriented CPU idle governor * * Copyright (C) 2018 - 2021 Intel Corporation * Author: Rafael J. Wysocki <rafael.j.wysocki@intel.com> */ /** * DOC: teo-description * * The idea of this governor is based on the observation that on many systems * timer interrupts are two or more orders of magnitude more frequent than any * other interrupt types, so they are likely to dominate CPU wakeup patterns. * Moreover, in principle, the time when the next timer event is going to occur * can be determined at the idle state selection time, although doing that may * be costly, so it can be regarded as the most reliable source of information * for idle state selection. * * Of course, non-timer wakeup sources are more important in some use cases, * but even then it is generally unnecessary to consider idle duration values * greater than the time till the next timer event, referred as the sleep * length in what follows, because the closest timer will ultimately wake up the * CPU anyway unless it is woken up earlier. * * However, since obtaining the sleep length may be costly, the governor first * checks if it can select a shallow idle state using wakeup pattern information * from recent times, in which case it can do without knowing the sleep length * at all. For this purpose, it counts CPU wakeup events and looks for an idle * state whose target residency has not exceeded the idle duration (measured * after wakeup) in the majority of relevant recent cases. If the target * residency of that state is small enough, it may be used right away and the * sleep length need not be determined. * * The computations carried out by this governor are based on using bins whose * boundaries are aligned with the target residency parameter values of the CPU * idle states provided by the %CPUIdle driver in the ascending order. That is, * the first bin spans from 0 up to, but not including, the target residency of * the second idle state (idle state 1), the second bin spans from the target * residency of idle state 1 up to, but not including, the target residency of * idle state 2, the third bin spans from the target residency of idle state 2 * up to, but not including, the target residency of idle state 3 and so on. * The last bin spans from the target residency of the deepest idle state * supplied by the driver to infinity. * * Two metrics called "hits" and "intercepts" are associated with each bin. * They are updated every time before selecting an idle state for the given CPU * in accordance with what happened last time. * * The "hits" metric reflects the relative frequency of situations in which the * sleep length and the idle duration measured after CPU wakeup are close enough * (that is, the CPU appears to wake up "on time" relative to the sleep length). * In turn, the "intercepts" metric reflects the relative frequency of non-timer * wakeup events for which the measured idle duration is significantly different * from the sleep length (these events are also referred to as "intercepts" * below). * * The governor also counts "intercepts" with the measured idle duration below * the tick period length and uses this information when deciding whether or not * to stop the scheduler tick. * * In order to select an idle state for a CPU, the governor takes the following * steps (modulo the possible latency constraint that must be taken into account * too): * * 1. Find the deepest enabled CPU idle state (the candidate idle state) and * compute 2 sums as follows: * * - The sum of the "hits" metric for all of the idle states shallower than * the candidate one (it represents the cases in which the CPU was likely * woken up by a timer). * * - The sum of the "intercepts" metric for all of the idle states shallower * than the candidate one (it represents the cases in which the CPU was * likely woken up by a non-timer wakeup source). * * Also find the idle state with the maximum intercepts metric (if there are * multiple states with the maximum intercepts metric, choose the one with * the highest index). * * 2. If the second sum computed in step 1 is greater than a half of the sum of * both metrics for the candidate state bin and all subsequent bins (if any), * a shallower idle state is likely to be more suitable, so look for it. * * - Traverse the enabled idle states shallower than the candidate one in the * descending order, starting at the state with the maximum intercepts * metric found in step 1. * * - For each of them compute the sum of the "intercepts" metrics over all * of the idle states between it and the candidate one (including the * former and excluding the latter). * * - If this sum is greater than a half of the second sum computed in step 1, * use the given idle state as the new candidate one. * * 3. If the current candidate state is state 0 or its target residency is short * enough, return it and prevent the scheduler tick from being stopped. * * 4. Obtain the sleep length value and check if it is below the target * residency of the current candidate state, in which case a new shallower * candidate state needs to be found, so look for it. */ #include <linux/cpuidle.h> #include <linux/jiffies.h> #include <linux/kernel.h> #include <linux/sched/clock.h> #include <linux/tick.h> #include "gov.h" /* * Idle state exit latency threshold used for deciding whether or not to check * the time till the closest expected timer event. */ #define LATENCY_THRESHOLD_NS (RESIDENCY_THRESHOLD_NS / 2) /* * The PULSE value is added to metrics when they grow and the DECAY_SHIFT value * is used for decreasing metrics on a regular basis. */ #define PULSE 1024 #define DECAY_SHIFT 3 /** * struct teo_bin - Metrics used by the TEO cpuidle governor. * @intercepts: The "intercepts" metric. * @hits: The "hits" metric. */ struct teo_bin { unsigned int intercepts; unsigned int hits; }; /** * struct teo_cpu - CPU data used by the TEO cpuidle governor. * @sleep_length_ns: Time till the closest timer event (at the selection time). * @state_bins: Idle state data bins for this CPU. * @total: Grand total of the "intercepts" and "hits" metrics for all bins. * @total_tick: Wakeups by the scheduler tick. * @tick_intercepts: "Intercepts" before TICK_NSEC. * @short_idles: Wakeups after short idle periods. * @tick_wakeup: Set if the last wakeup was by the scheduler tick. */ struct teo_cpu { s64 sleep_length_ns; struct teo_bin state_bins[CPUIDLE_STATE_MAX]; unsigned int total; unsigned int total_tick; unsigned int tick_intercepts; unsigned int short_idles; bool tick_wakeup; }; static DEFINE_PER_CPU(struct teo_cpu, teo_cpus); static void teo_decay(unsigned int *metric) { unsigned int delta = *metric >> DECAY_SHIFT; if (delta) *metric -= delta; else *metric = 0; } /** * teo_update - Update CPU metrics after wakeup. * @drv: cpuidle driver containing state data. * @dev: Target CPU. */ static void teo_update(struct cpuidle_driver *drv, struct cpuidle_device *dev) { s64 lat_ns = drv->states[dev->last_state_idx].exit_latency_ns; struct teo_cpu *cpu_data = this_cpu_ptr(&teo_cpus); int i, idx_timer = 0, idx_duration = 0; s64 target_residency_ns, measured_ns; unsigned int total = 0; teo_decay(&cpu_data->short_idles); if (dev->poll_time_limit) { dev->poll_time_limit = false; /* * Polling state timeout has triggered, so assume that this * might have been a long sleep. */ measured_ns = S64_MAX; } else { measured_ns = dev->last_residency_ns; /* * The delay between the wakeup and the first instruction * executed by the CPU is not likely to be worst-case every * time, so take 1/2 of the exit latency as a very rough * approximation of the average of it. */ if (measured_ns >= lat_ns) { measured_ns -= lat_ns / 2; if (measured_ns < RESIDENCY_THRESHOLD_NS) cpu_data->short_idles += PULSE; } else { measured_ns /= 2; cpu_data->short_idles += PULSE; } } /* * Decay the "hits" and "intercepts" metrics for all of the bins and * find the bins that the sleep length and the measured idle duration * fall into. */ for (i = 0; i < drv->state_count; i++) { struct teo_bin *bin = &cpu_data->state_bins[i]; teo_decay(&bin->hits); total += bin->hits; teo_decay(&bin->intercepts); total += bin->intercepts; target_residency_ns = drv->states[i].target_residency_ns; if (target_residency_ns <= cpu_data->sleep_length_ns) { idx_timer = i; if (target_residency_ns <= measured_ns) idx_duration = i; } } cpu_data->total = total + PULSE; teo_decay(&cpu_data->tick_intercepts); teo_decay(&cpu_data->total_tick); if (cpu_data->tick_wakeup) { cpu_data->total_tick += PULSE; /* * If tick wakeups dominate the wakeup pattern, count this one * as a hit on the deepest available idle state to increase the * likelihood of stopping the tick. */ if (3 * cpu_data->total_tick > 2 * cpu_data->total) { cpu_data->state_bins[drv->state_count-1].hits += PULSE; return; } /* * If intercepts within the tick period range are not frequent * enough, count this wakeup as a hit, since it is likely that * the tick has woken up the CPU because an expected intercept * was not there. Otherwise, one of the intercepts may have * been incidentally preceded by the tick wakeup. */ if (3 * cpu_data->tick_intercepts < 2 * total) { cpu_data->state_bins[idx_timer].hits += PULSE; return; } } /* * If the measured idle duration (adjusted for the entered state exit * latency) falls into the same bin as the sleep length and the latter * is less than the "raw" measured idle duration (so the wakeup appears * to have occurred after the anticipated timer event), this is a "hit", * so update the "hits" metric for that bin. * * Otherwise, update the "intercepts" metric for the bin fallen into by * the measured idle duration. */ if (idx_timer == idx_duration && cpu_data->sleep_length_ns - measured_ns < lat_ns / 2) { cpu_data->state_bins[idx_timer].hits += PULSE; } else { cpu_data->state_bins[idx_duration].intercepts += PULSE; if (measured_ns <= TICK_NSEC) cpu_data->tick_intercepts += PULSE; } } /** * teo_find_shallower_state - Find shallower idle state matching given duration. * @drv: cpuidle driver containing state data. * @dev: Target CPU. * @state_idx: Index of the capping idle state. * @duration_ns: Idle duration value to match. */ static int teo_find_shallower_state(struct cpuidle_driver *drv, struct cpuidle_device *dev, int state_idx, s64 duration_ns) { int i; for (i = state_idx - 1; i >= 0; i--) { if (dev->states_usage[i].disable) continue; state_idx = i; if (drv->states[i].target_residency_ns <= duration_ns) break; } return state_idx; } /** * teo_select - Selects the next idle state to enter. * @drv: cpuidle driver containing state data. * @dev: Target CPU. * @stop_tick: Indication on whether or not to stop the scheduler tick. */ static int teo_select(struct cpuidle_driver *drv, struct cpuidle_device *dev, bool *stop_tick) { struct teo_cpu *cpu_data = this_cpu_ptr(&teo_cpus); s64 latency_req = cpuidle_governor_latency_req(dev->cpu); ktime_t delta_tick = TICK_NSEC / 2; unsigned int idx_intercept_sum = 0; unsigned int intercept_sum = 0; unsigned int intercept_max = 0; unsigned int idx_hit_sum = 0; unsigned int hit_sum = 0; int intercept_max_idx = -1; int constraint_idx = 0; int idx0 = 0, idx = -1; s64 duration_ns; int i; if (dev->last_state_idx >= 0) { teo_update(drv, dev); dev->last_state_idx = -1; } /* * Set the sleep length to infinity in case the invocation of * tick_nohz_get_sleep_length() below is skipped, in which case it won't * be known whether or not the subsequent wakeup is caused by a timer. * It is generally fine to count the wakeup as an intercept then, except * for the cases when the CPU is mostly woken up by timers and there may * be opportunities to ask for a deeper idle state when no imminent * timers are scheduled which may be missed. */ cpu_data->sleep_length_ns = KTIME_MAX; if (!dev->states_usage[0].disable) idx = 0; /* * Compute the sums of metrics for early wakeup pattern detection and * look for the state bin with the maximum intercepts metric below the * deepest enabled one (if there are multiple states with the maximum * intercepts metric, choose the one with the highest index). */ for (i = 1; i < drv->state_count; i++) { struct teo_bin *prev_bin = &cpu_data->state_bins[i-1]; unsigned int prev_intercepts = prev_bin->intercepts; struct cpuidle_state *s = &drv->states[i]; /* * Update the sums of idle state metrics for all of the states * shallower than the current one. */ hit_sum += prev_bin->hits; intercept_sum += prev_intercepts; /* * Check if this is the bin with the maximum number of * intercepts so far and in that case update the index of * the state with the maximum intercepts metric. */ if (prev_intercepts >= intercept_max) { intercept_max = prev_intercepts; intercept_max_idx = i - 1; } if (dev->states_usage[i].disable) continue; if (idx < 0) idx0 = i; /* first enabled state */ idx = i; if (s->exit_latency_ns <= latency_req) constraint_idx = i; /* Save the sums for the current state. */ idx_intercept_sum = intercept_sum; idx_hit_sum = hit_sum; } /* Avoid unnecessary overhead. */ if (idx < 0) { idx = 0; /* No states enabled, must use 0. */ goto out_tick; } if (idx == idx0) { /* * Only one idle state is enabled, 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; } /* * If the sum of the intercepts metric for all of the idle states * shallower than the current candidate one (idx) is greater than the * sum of the intercepts and hits metrics for the candidate state and * all of the deeper states, a shallower idle state is likely to be a * better choice. */ if (2 * idx_intercept_sum > cpu_data->total - idx_hit_sum) { /* * Look for the deepest enabled idle state, at most as deep as * the one with the maximum intercepts metric, whose target * residency had not been greater than the idle duration in over * a half of the relevant cases in the past. */ for (i = idx - 1, intercept_sum = 0; i >= idx0; i--) { intercept_sum += cpu_data->state_bins[i].intercepts; if (dev->states_usage[i].disable) continue; idx = i; if (2 * intercept_sum > idx_intercept_sum && i <= intercept_max_idx) break; } } /* * If there is a latency constraint, it may be necessary to select an * idle state shallower than the current candidate one. */ if (idx > constraint_idx) idx = constraint_idx; /* * If the tick has not been stopped and either the candidate state is * state 0 or its target residency is low enough, there is basically * nothing more to do, but if the sleep length is not updated, the * subsequent wakeup will be counted as an "intercept". That may be * problematic in the cases when timer wakeups are dominant because it * may effectively prevent deeper idle states from being selected at one * point even if no imminent timers are scheduled. * * However, frequent timers in the RESIDENCY_THRESHOLD_NS range on one * CPU are unlikely (user space has a default 50 us slack value for * hrtimers and there are relatively few timers with a lower deadline * value in the kernel), and even if they did happen, the potential * benefit from using a deep idle state in that case would be * questionable anyway for latency reasons. Thus if the measured idle * duration falls into that range in the majority of cases, assume * non-timer wakeups to be dominant and skip updating the sleep length * to reduce latency. * * Also, if the latency constraint is sufficiently low, it will force * shallow idle states regardless of the wakeup type, so the sleep * length need not be known in that case. */ if (!tick_nohz_tick_stopped() && (!idx || drv->states[idx].target_residency_ns < RESIDENCY_THRESHOLD_NS) && (2 * cpu_data->short_idles >= cpu_data->total || latency_req < LATENCY_THRESHOLD_NS)) goto out_tick; duration_ns = tick_nohz_get_sleep_length(&delta_tick); cpu_data->sleep_length_ns = duration_ns; /* * If the tick has been stopped and the closest timer is too far away, * update the selection to prevent the CPU from getting stuck in a * shallow idle state for too long. */ if (tick_nohz_tick_stopped() && duration_ns > SAFE_TIMER_RANGE_NS && drv->states[idx].target_residency_ns < TICK_NSEC) { /* * Look for the deepest enabled idle state with exit latency * within the PM QoS limit and with target residency within * duration_ns. */ for (i = constraint_idx; i > idx; i--) { if (dev->states_usage[i].disable) continue; if (drv->states[i].target_residency_ns <= duration_ns) { idx = i; break; } } return idx; } if (!idx) goto out_tick; /* * If the closest expected timer is before the target residency of the * candidate state, a shallower one needs to be found. */ if (drv->states[idx].target_residency_ns > duration_ns) idx = teo_find_shallower_state(drv, dev, idx, duration_ns); /* * If the selected state's target residency is below the tick length * and intercepts occurring before the tick length are the majority of * total wakeup events, do not stop the tick. */ if (drv->states[idx].target_residency_ns < TICK_NSEC && 3 * cpu_data->tick_intercepts >= 2 * cpu_data->total) duration_ns = TICK_NSEC / 2; end: /* * 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()) 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); out_tick: *stop_tick = false; return idx; } /** * teo_reflect - Note that governor data for the CPU need to be updated. * @dev: Target CPU. * @state: Entered state. */ static void teo_reflect(struct cpuidle_device *dev, int state) { struct teo_cpu *cpu_data = this_cpu_ptr(&teo_cpus); cpu_data->tick_wakeup = tick_nohz_idle_got_tick(); dev->last_state_idx = state; } /** * teo_enable_device - Initialize the governor's data for the target CPU. * @drv: cpuidle driver (not used). * @dev: Target CPU. */ static int teo_enable_device(struct cpuidle_driver *drv, struct cpuidle_device *dev) { struct teo_cpu *cpu_data = per_cpu_ptr(&teo_cpus, dev->cpu); memset(cpu_data, 0, sizeof(*cpu_data)); return 0; } static struct cpuidle_governor teo_governor = { .name = "teo", .rating = 19, .enable = teo_enable_device, .select = teo_select, .reflect = teo_reflect, }; static int __init teo_governor_init(void) { return cpuidle_register_governor(&teo_governor); } postcore_initcall(teo_governor_init);
