// SPDX-License-Identifier: GPL-2.0 /* * Timer events oriented CPU idle governor * * Copyright (C) 2018 - 2021 Intel Corporation * Author: Rafael J. Wysocki <[email protected]> */ /** * DOC: teo-description * * The idea of this governor is based on the observation that on many systems * timer events are two or more orders of magnitude more frequent than any * other interrupts, so they are likely to be the most significant cause of CPU * wakeups from idle states. Moreover, information about what happened in the * (relatively recent) past can be used to estimate whether or not the deepest * idle state with target residency within the (known) time till the closest * timer event, referred to as the sleep length, is likely to be suitable for * the upcoming CPU idle period and, if not, then which of the shallower idle * states to choose instead of it. * * Of course, non-timer wakeup sources are more important in some use cases * which can be covered by taking a few most recent idle time intervals of the * CPU into account. However, even in that context it is not necessary to * consider idle duration values greater than the sleep length, because the * closest timer will ultimately wake up the CPU anyway unless it is woken up * earlier. * * Thus this governor estimates whether or not the prospective idle duration of * a CPU is likely to be significantly shorter than the sleep length and selects * an idle state for it accordingly. * * 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 fall into the * same bin (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 * situations in which the measured idle duration is so much shorter than the * sleep length that the bin it falls into corresponds to an idle state * shallower than the one whose bin is fallen into by the sleep length (these * situations are referred to as "intercepts" below). * * 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 CPU idle state whose target residency does not exceed * the current sleep length (the candidate idle state) and compute 2 sums as * follows: * * - The sum of the "hits" and "intercepts" metrics for the candidate state * and all of the deeper idle states (it represents the cases in which the * CPU was idle long enough to avoid being intercepted if the sleep length * had been equal to the current one). * * - The sum of the "intercepts" metrics for all of the idle states shallower * than the candidate one (it represents the cases in which the CPU was not * idle long enough to avoid being intercepted if the sleep length had been * equal to the current one). * * 2. If the second sum is greater than the first one the CPU is likely to wake * up early, so look for an alternative idle state to select. * * - Traverse the idle states shallower than the candidate one in the * descending order. * * - 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 each of these sums that needs to be taken into account (because the * check related to it has indicated that the CPU is likely to wake up * early) is greater than a half of the corresponding sum computed in step * 1 (which means that the target residency of the state in question had * not exceeded the idle duration in over a half of the relevant cases), * select the given idle state instead of the candidate one. * * 3. By default, select the candidate state. */ #include <linux/cpuidle.h> #include <linux/jiffies.h> #include <linux/kernel.h> #include <linux/sched/clock.h> #include <linux/tick.h> #include "gov.h" /* * 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 … #define DECAY_SHIFT … /** * struct teo_bin - Metrics used by the TEO cpuidle governor. * @intercepts: The "intercepts" metric. * @hits: The "hits" metric. */ struct teo_bin { … }; /** * struct teo_cpu - CPU data used by the TEO cpuidle governor. * @time_span_ns: Time between idle state selection and post-wakeup update. * @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. * @tick_hits: Number of "hits" after TICK_NSEC. */ struct teo_cpu { … }; static DEFINE_PER_CPU(struct teo_cpu, teo_cpus); /** * 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) { … } static bool teo_state_ok(int i, struct cpuidle_driver *drv) { … } /** * 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. * @no_poll: Don't consider polling states. */ static int teo_find_shallower_state(struct cpuidle_driver *drv, struct cpuidle_device *dev, int state_idx, s64 duration_ns, bool no_poll) { … } /** * 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) { … } /** * 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) { … } /** * 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) { … } static struct cpuidle_governor teo_governor = …; static int __init teo_governor_init(void) { … } postcore_initcall(teo_governor_init);
Codebase Browser
linux