blob: b0a7ad566081a2f3d9b51f3a3d52ae9263064b33 [file] [log] [blame]
Thomas Gleixner7925f8f2019-05-28 10:10:18 -07001// SPDX-License-Identifier: GPL-2.0-only
Len Brown4f86d3a2007-10-03 18:58:00 -04002/*
3 * menu.c - the menu idle governor
4 *
5 * Copyright (C) 2006-2007 Adam Belay <abelay@novell.com>
Arjan van de Ven69d25872009-09-21 17:04:08 -07006 * Copyright (C) 2009 Intel Corporation
7 * Author:
8 * Arjan van de Ven <arjan@linux.intel.com>
Len Brown4f86d3a2007-10-03 18:58:00 -04009 */
10
11#include <linux/kernel.h>
12#include <linux/cpuidle.h>
Len Brown4f86d3a2007-10-03 18:58:00 -040013#include <linux/time.h>
14#include <linux/ktime.h>
15#include <linux/hrtimer.h>
16#include <linux/tick.h>
Arjan van de Ven69d25872009-09-21 17:04:08 -070017#include <linux/sched.h>
Ingo Molnar4f177222017-02-08 08:45:17 +010018#include <linux/sched/loadavg.h>
Ingo Molnar03441a32017-02-08 18:51:35 +010019#include <linux/sched/stat.h>
Stephen Hemminger57875362010-01-08 14:43:08 -080020#include <linux/math64.h>
Len Brown4f86d3a2007-10-03 18:58:00 -040021
Arjan van de Ven69d25872009-09-21 17:04:08 -070022#define BUCKETS 12
Mel Gormanae779302014-08-06 14:19:18 +010023#define INTERVAL_SHIFT 3
24#define INTERVALS (1UL << INTERVAL_SHIFT)
Arjan van de Ven69d25872009-09-21 17:04:08 -070025#define RESOLUTION 1024
Arjan van de Ven1f85f872010-05-24 14:32:59 -070026#define DECAY 8
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +010027#define MAX_INTERESTING (50000 * NSEC_PER_USEC)
Arjan van de Ven69d25872009-09-21 17:04:08 -070028
29/*
30 * Concepts and ideas behind the menu governor
31 *
32 * For the menu governor, there are 3 decision factors for picking a C
33 * state:
34 * 1) Energy break even point
35 * 2) Performance impact
36 * 3) Latency tolerance (from pmqos infrastructure)
37 * These these three factors are treated independently.
38 *
39 * Energy break even point
40 * -----------------------
41 * C state entry and exit have an energy cost, and a certain amount of time in
42 * the C state is required to actually break even on this cost. CPUIDLE
43 * provides us this duration in the "target_residency" field. So all that we
44 * need is a good prediction of how long we'll be idle. Like the traditional
45 * menu governor, we start with the actual known "next timer event" time.
46 *
47 * Since there are other source of wakeups (interrupts for example) than
48 * the next timer event, this estimation is rather optimistic. To get a
49 * more realistic estimate, a correction factor is applied to the estimate,
50 * that is based on historic behavior. For example, if in the past the actual
51 * duration always was 50% of the next timer tick, the correction factor will
52 * be 0.5.
53 *
54 * menu uses a running average for this correction factor, however it uses a
55 * set of factors, not just a single factor. This stems from the realization
56 * that the ratio is dependent on the order of magnitude of the expected
57 * duration; if we expect 500 milliseconds of idle time the likelihood of
58 * getting an interrupt very early is much higher than if we expect 50 micro
59 * seconds of idle time. A second independent factor that has big impact on
60 * the actual factor is if there is (disk) IO outstanding or not.
61 * (as a special twist, we consider every sleep longer than 50 milliseconds
62 * as perfect; there are no power gains for sleeping longer than this)
63 *
64 * For these two reasons we keep an array of 12 independent factors, that gets
65 * indexed based on the magnitude of the expected duration as well as the
66 * "is IO outstanding" property.
67 *
Arjan van de Ven1f85f872010-05-24 14:32:59 -070068 * Repeatable-interval-detector
69 * ----------------------------
70 * There are some cases where "next timer" is a completely unusable predictor:
71 * Those cases where the interval is fixed, for example due to hardware
72 * interrupt mitigation, but also due to fixed transfer rate devices such as
73 * mice.
74 * For this, we use a different predictor: We track the duration of the last 8
75 * intervals and if the stand deviation of these 8 intervals is below a
76 * threshold value, we use the average of these intervals as prediction.
77 *
Arjan van de Ven69d25872009-09-21 17:04:08 -070078 * Limiting Performance Impact
79 * ---------------------------
80 * C states, especially those with large exit latencies, can have a real
Lucas De Marchi20e33412010-09-07 12:53:49 -040081 * noticeable impact on workloads, which is not acceptable for most sysadmins,
Arjan van de Ven69d25872009-09-21 17:04:08 -070082 * and in addition, less performance has a power price of its own.
83 *
84 * As a general rule of thumb, menu assumes that the following heuristic
85 * holds:
86 * The busier the system, the less impact of C states is acceptable
87 *
88 * This rule-of-thumb is implemented using a performance-multiplier:
89 * If the exit latency times the performance multiplier is longer than
90 * the predicted duration, the C state is not considered a candidate
91 * for selection due to a too high performance impact. So the higher
92 * this multiplier is, the longer we need to be idle to pick a deep C
93 * state, and thus the less likely a busy CPU will hit such a deep
94 * C state.
95 *
96 * Two factors are used in determing this multiplier:
97 * a value of 10 is added for each point of "per cpu load average" we have.
98 * a value of 5 points is added for each process that is waiting for
99 * IO on this CPU.
100 * (these values are experimentally determined)
101 *
102 * The load average factor gives a longer term (few seconds) input to the
103 * decision, while the iowait value gives a cpu local instantanious input.
104 * The iowait factor may look low, but realize that this is also already
105 * represented in the system load average.
106 *
107 */
Len Brown4f86d3a2007-10-03 18:58:00 -0400108
109struct menu_device {
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700110 int needs_update;
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100111 int tick_wakeup;
Len Brown4f86d3a2007-10-03 18:58:00 -0400112
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100113 u64 next_timer_ns;
Arjan van de Ven69d25872009-09-21 17:04:08 -0700114 unsigned int bucket;
Tuukka Tikkanen51f245b2013-08-14 19:02:41 +0300115 unsigned int correction_factor[BUCKETS];
Tuukka Tikkanen939e33b2013-08-14 19:02:38 +0300116 unsigned int intervals[INTERVALS];
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700117 int interval_ptr;
Len Brown4f86d3a2007-10-03 18:58:00 -0400118};
119
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100120static inline int which_bucket(u64 duration_ns, unsigned long nr_iowaiters)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700121{
122 int bucket = 0;
123
124 /*
125 * We keep two groups of stats; one with no
126 * IO pending, one without.
127 * This allows us to calculate
128 * E(duration)|iowait
129 */
Mel Gorman64b4ca52014-08-06 14:19:20 +0100130 if (nr_iowaiters)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700131 bucket = BUCKETS/2;
132
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100133 if (duration_ns < 10ULL * NSEC_PER_USEC)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700134 return bucket;
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100135 if (duration_ns < 100ULL * NSEC_PER_USEC)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700136 return bucket + 1;
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100137 if (duration_ns < 1000ULL * NSEC_PER_USEC)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700138 return bucket + 2;
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100139 if (duration_ns < 10000ULL * NSEC_PER_USEC)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700140 return bucket + 3;
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100141 if (duration_ns < 100000ULL * NSEC_PER_USEC)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700142 return bucket + 4;
143 return bucket + 5;
144}
145
146/*
147 * Return a multiplier for the exit latency that is intended
148 * to take performance requirements into account.
149 * The more performance critical we estimate the system
150 * to be, the higher this multiplier, and thus the higher
151 * the barrier to go to an expensive C state.
152 */
Daniel Lezcanoa7fe5192018-10-04 14:04:03 +0200153static inline int performance_multiplier(unsigned long nr_iowaiters)
Arjan van de Ven69d25872009-09-21 17:04:08 -0700154{
Daniel Lezcanoa7fe5192018-10-04 14:04:03 +0200155 /* for IO wait tasks (per cpu!) we add 10x each */
156 return 1 + 10 * nr_iowaiters;
Arjan van de Ven69d25872009-09-21 17:04:08 -0700157}
158
Len Brown4f86d3a2007-10-03 18:58:00 -0400159static DEFINE_PER_CPU(struct menu_device, menu_devices);
160
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530161static void menu_update(struct cpuidle_driver *drv, struct cpuidle_device *dev);
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700162
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700163/*
164 * Try detecting repeating patterns by keeping track of the last 8
165 * intervals, and checking if the standard deviation of that set
166 * of points is below a threshold. If it is... then use the
167 * average of these 8 points as the estimated value.
168 */
Rafael J. Wysockif1c8e412018-10-15 13:53:25 +0200169static unsigned int get_typical_interval(struct menu_device *data,
170 unsigned int predicted_us)
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700171{
Tuukka Tikkanen4cd46bc2013-08-14 19:02:37 +0300172 int i, divisor;
Rafael J. Wysockif1c8e412018-10-15 13:53:25 +0200173 unsigned int min, max, thresh, avg;
Rasmus Villemoes3b996692016-02-16 20:19:19 +0100174 uint64_t sum, variance;
Tuukka Tikkanen0e96d5a2013-08-14 19:02:39 +0300175
Rafael J. Wysocki814b87972019-02-27 14:35:50 +0100176 thresh = INT_MAX; /* Discard outliers above this value */
Youquan Songc96ca4f2012-10-26 12:27:07 +0200177
178again:
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700179
Tuukka Tikkanen0e96d5a2013-08-14 19:02:39 +0300180 /* First calculate the average of past intervals */
Rafael J. Wysockif1c8e412018-10-15 13:53:25 +0200181 min = UINT_MAX;
Tuukka Tikkanen4cd46bc2013-08-14 19:02:37 +0300182 max = 0;
Rasmus Villemoes3b996692016-02-16 20:19:19 +0100183 sum = 0;
Tuukka Tikkanen4cd46bc2013-08-14 19:02:37 +0300184 divisor = 0;
Youquan Songc96ca4f2012-10-26 12:27:07 +0200185 for (i = 0; i < INTERVALS; i++) {
Tuukka Tikkanen0e96d5a2013-08-14 19:02:39 +0300186 unsigned int value = data->intervals[i];
Youquan Songc96ca4f2012-10-26 12:27:07 +0200187 if (value <= thresh) {
Rasmus Villemoes3b996692016-02-16 20:19:19 +0100188 sum += value;
Youquan Songc96ca4f2012-10-26 12:27:07 +0200189 divisor++;
190 if (value > max)
191 max = value;
Rafael J. Wysockif1c8e412018-10-15 13:53:25 +0200192
193 if (value < min)
194 min = value;
Youquan Songc96ca4f2012-10-26 12:27:07 +0200195 }
196 }
Rafael J. Wysockif1c8e412018-10-15 13:53:25 +0200197
198 /*
199 * If the result of the computation is going to be discarded anyway,
200 * avoid the computation altogether.
201 */
202 if (min >= predicted_us)
203 return UINT_MAX;
204
Mel Gormanae779302014-08-06 14:19:18 +0100205 if (divisor == INTERVALS)
Rasmus Villemoes3b996692016-02-16 20:19:19 +0100206 avg = sum >> INTERVAL_SHIFT;
Mel Gormanae779302014-08-06 14:19:18 +0100207 else
Rasmus Villemoes3b996692016-02-16 20:19:19 +0100208 avg = div_u64(sum, divisor);
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700209
Rasmus Villemoes7024b182016-02-16 20:19:18 +0100210 /* Then try to determine variance */
211 variance = 0;
Youquan Songc96ca4f2012-10-26 12:27:07 +0200212 for (i = 0; i < INTERVALS; i++) {
Tuukka Tikkanen0e96d5a2013-08-14 19:02:39 +0300213 unsigned int value = data->intervals[i];
Youquan Songc96ca4f2012-10-26 12:27:07 +0200214 if (value <= thresh) {
Rasmus Villemoes3b996692016-02-16 20:19:19 +0100215 int64_t diff = (int64_t)value - avg;
Rasmus Villemoes7024b182016-02-16 20:19:18 +0100216 variance += diff * diff;
Youquan Songc96ca4f2012-10-26 12:27:07 +0200217 }
218 }
Mel Gormanae779302014-08-06 14:19:18 +0100219 if (divisor == INTERVALS)
Rasmus Villemoes7024b182016-02-16 20:19:18 +0100220 variance >>= INTERVAL_SHIFT;
Mel Gormanae779302014-08-06 14:19:18 +0100221 else
Rasmus Villemoes7024b182016-02-16 20:19:18 +0100222 do_div(variance, divisor);
Mel Gormanae779302014-08-06 14:19:18 +0100223
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700224 /*
Rasmus Villemoes7024b182016-02-16 20:19:18 +0100225 * The typical interval is obtained when standard deviation is
226 * small (stddev <= 20 us, variance <= 400 us^2) or standard
227 * deviation is small compared to the average interval (avg >
228 * 6*stddev, avg^2 > 36*variance). The average is smaller than
229 * UINT_MAX aka U32_MAX, so computing its square does not
230 * overflow a u64. We simply reject this candidate average if
231 * the standard deviation is greater than 715 s (which is
232 * rather unlikely).
Tuukka Tikkanen0d6a7ff2013-08-14 19:02:36 +0300233 *
Tuukka Tikkanen330647a2013-08-14 19:02:34 +0300234 * Use this result only if there is no timer to wake us up sooner.
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700235 */
Rasmus Villemoes7024b182016-02-16 20:19:18 +0100236 if (likely(variance <= U64_MAX/36)) {
Rasmus Villemoes3b996692016-02-16 20:19:19 +0100237 if ((((u64)avg*avg > variance*36) && (divisor * 4 >= INTERVALS * 3))
Rasmus Villemoes7024b182016-02-16 20:19:18 +0100238 || variance <= 400) {
Rik van Riele132b9b2016-03-16 12:14:00 -0400239 return avg;
Tuukka Tikkanen0d6a7ff2013-08-14 19:02:36 +0300240 }
Youquan Song69a37be2012-10-26 12:26:41 +0200241 }
Tuukka Tikkanen017099e2013-08-14 19:02:35 +0300242
243 /*
244 * If we have outliers to the upside in our distribution, discard
245 * those by setting the threshold to exclude these outliers, then
246 * calculate the average and standard deviation again. Once we get
247 * down to the bottom 3/4 of our samples, stop excluding samples.
248 *
249 * This can deal with workloads that have long pauses interspersed
250 * with sporadic activity with a bunch of short pauses.
251 */
252 if ((divisor * 4) <= INTERVALS * 3)
Rik van Riele132b9b2016-03-16 12:14:00 -0400253 return UINT_MAX;
Tuukka Tikkanen017099e2013-08-14 19:02:35 +0300254
255 thresh = max - 1;
256 goto again;
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700257}
258
Len Brown4f86d3a2007-10-03 18:58:00 -0400259/**
260 * menu_select - selects the next idle state to enter
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530261 * @drv: cpuidle driver containing state data
Len Brown4f86d3a2007-10-03 18:58:00 -0400262 * @dev: the CPU
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100263 * @stop_tick: indication on whether or not to stop the tick
Len Brown4f86d3a2007-10-03 18:58:00 -0400264 */
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100265static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev,
266 bool *stop_tick)
Len Brown4f86d3a2007-10-03 18:58:00 -0400267{
Christoph Lameter229b6862014-08-17 12:30:30 -0500268 struct menu_device *data = this_cpu_ptr(&menu_devices);
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100269 s64 latency_req = cpuidle_governor_latency_req(dev->cpu);
Rafael J. Wysocki03dba272018-10-01 11:56:21 +0200270 unsigned int predicted_us;
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100271 u64 predicted_ns;
272 u64 interactivity_req;
Daniel Lezcanoa7fe5192018-10-04 14:04:03 +0200273 unsigned long nr_iowaiters;
Rafael J. Wysocki296bb1e2018-04-05 19:12:34 +0200274 ktime_t delta_next;
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100275 int i, idx;
Arjan van de Ven69d25872009-09-21 17:04:08 -0700276
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700277 if (data->needs_update) {
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530278 menu_update(drv, dev);
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700279 data->needs_update = 0;
280 }
281
Arjan van de Ven69d25872009-09-21 17:04:08 -0700282 /* determine the expected residency time, round up */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100283 data->next_timer_ns = tick_nohz_get_sleep_length(&delta_next);
Len Brown4f86d3a2007-10-03 18:58:00 -0400284
Daniel Lezcanoa7fe5192018-10-04 14:04:03 +0200285 nr_iowaiters = nr_iowait_cpu(dev->cpu);
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100286 data->bucket = which_bucket(data->next_timer_ns, nr_iowaiters);
Arjan van de Ven69d25872009-09-21 17:04:08 -0700287
Rafael J. Wysocki53812cd2018-10-02 23:47:43 +0200288 if (unlikely(drv->state_count <= 1 || latency_req == 0) ||
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100289 ((data->next_timer_ns < drv->states[1].target_residency_ns ||
290 latency_req < drv->states[1].exit_latency_ns) &&
Rafael J. Wysocki99e98d32019-11-04 12:16:17 +0100291 !dev->states_usage[0].disable)) {
Rafael J. Wysocki8b007eb2018-10-02 23:46:28 +0200292 /*
293 * In this case state[0] will be used no matter what, so return
Rafael J. Wysocki32b91ca2019-07-18 10:53:21 +0200294 * it right away and keep the tick running if state[0] is a
295 * polling one.
Rafael J. Wysocki8b007eb2018-10-02 23:46:28 +0200296 */
Rafael J. Wysocki32b91ca2019-07-18 10:53:21 +0200297 *stop_tick = !(drv->states[0].flags & CPUIDLE_FLAG_POLLING);
Rafael J. Wysocki8b007eb2018-10-02 23:46:28 +0200298 return 0;
299 }
300
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100301 /* Round up the result for half microseconds. */
302 predicted_us = div_u64(data->next_timer_ns *
303 data->correction_factor[data->bucket] +
304 (RESOLUTION * DECAY * NSEC_PER_USEC) / 2,
305 RESOLUTION * DECAY * NSEC_PER_USEC);
306 /* Use the lowest expected idle interval to pick the idle state. */
307 predicted_ns = (u64)min(predicted_us,
308 get_typical_interval(data, predicted_us)) *
309 NSEC_PER_USEC;
Rik van Riele132b9b2016-03-16 12:14:00 -0400310
Rafael J. Wysocki87c9fe62018-04-05 19:12:43 +0200311 if (tick_nohz_tick_stopped()) {
312 /*
313 * If the tick is already stopped, the cost of possible short
314 * idle duration misprediction is much higher, because the CPU
315 * may be stuck in a shallow idle state for a long time as a
Rafael J. Wysocki5ef499c2018-08-14 12:34:40 +0200316 * result of it. In that case say we might mispredict and use
317 * the known time till the closest timer event for the idle
318 * state selection.
Rafael J. Wysocki87c9fe62018-04-05 19:12:43 +0200319 */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100320 if (predicted_ns < TICK_NSEC)
321 predicted_ns = delta_next;
Rafael J. Wysocki87c9fe62018-04-05 19:12:43 +0200322 } else {
323 /*
324 * Use the performance multiplier and the user-configurable
325 * latency_req to determine the maximum exit latency.
326 */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100327 interactivity_req = div64_u64(predicted_ns,
328 performance_multiplier(nr_iowaiters));
Rafael J. Wysocki87c9fe62018-04-05 19:12:43 +0200329 if (latency_req > interactivity_req)
330 latency_req = interactivity_req;
331 }
Rik van Riele132b9b2016-03-16 12:14:00 -0400332
333 /*
Ai Li71abbbf2010-08-09 17:20:13 -0700334 * Find the idle state with the lowest power while satisfying
335 * our constraints.
336 */
Nicholas Piggin3ed09c92017-06-26 15:38:15 +1000337 idx = -1;
Rafael J. Wysocki96c3d112018-10-02 23:44:06 +0200338 for (i = 0; i < drv->state_count; i++) {
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530339 struct cpuidle_state *s = &drv->states[i];
Len Brown4f86d3a2007-10-03 18:58:00 -0400340
Rafael J. Wysocki99e98d32019-11-04 12:16:17 +0100341 if (dev->states_usage[i].disable)
ShuoX Liu3a53396b2012-03-28 15:19:11 -0700342 continue;
Rafael J. Wysocki96c3d112018-10-02 23:44:06 +0200343
Nicholas Piggin3ed09c92017-06-26 15:38:15 +1000344 if (idx == -1)
345 idx = i; /* first enabled state */
Rafael J. Wysocki96c3d112018-10-02 23:44:06 +0200346
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100347 if (s->target_residency_ns > predicted_ns) {
Rafael J. Wysocki96c3d112018-10-02 23:44:06 +0200348 /*
349 * Use a physical idle state, not busy polling, unless
Rafael J. Wysockibde091e2018-10-10 14:16:38 +0200350 * a timer is going to trigger soon enough.
Rafael J. Wysocki96c3d112018-10-02 23:44:06 +0200351 */
352 if ((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) &&
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100353 s->exit_latency_ns <= latency_req &&
354 s->target_residency_ns <= data->next_timer_ns) {
355 predicted_ns = s->target_residency_ns;
Rafael J. Wysocki96c3d112018-10-02 23:44:06 +0200356 idx = i;
357 break;
358 }
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100359 if (predicted_ns < TICK_NSEC)
Rafael J. Wysocki5ef499c2018-08-14 12:34:40 +0200360 break;
361
Rafael J. Wysocki757ab152018-08-21 10:44:10 +0200362 if (!tick_nohz_tick_stopped()) {
363 /*
364 * If the state selected so far is shallow,
365 * waking up early won't hurt, so retain the
366 * tick in that case and let the governor run
367 * again in the next iteration of the loop.
368 */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100369 predicted_ns = drv->states[idx].target_residency_ns;
Rafael J. Wysocki757ab152018-08-21 10:44:10 +0200370 break;
371 }
372
Rafael J. Wysocki5ef499c2018-08-14 12:34:40 +0200373 /*
374 * If the state selected so far is shallow and this
375 * state's target residency matches the time till the
376 * closest timer event, select this one to avoid getting
377 * stuck in the shallow one for too long.
378 */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100379 if (drv->states[idx].target_residency_ns < TICK_NSEC &&
380 s->target_residency_ns <= delta_next)
Rafael J. Wysocki5ef499c2018-08-14 12:34:40 +0200381 idx = i;
382
Rafael J. Wysockieb40a382018-10-02 23:45:07 +0200383 return idx;
Rafael J. Wysocki5ef499c2018-08-14 12:34:40 +0200384 }
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100385 if (s->exit_latency_ns > latency_req)
Alex Shi8e37e1a2017-01-12 21:27:02 +0800386 break;
Rafael J. Wysocki32b91ca2019-07-18 10:53:21 +0200387
Nicholas Piggin3ed09c92017-06-26 15:38:15 +1000388 idx = i;
Len Brown4f86d3a2007-10-03 18:58:00 -0400389 }
390
Nicholas Piggin3ed09c92017-06-26 15:38:15 +1000391 if (idx == -1)
392 idx = 0; /* No states enabled. Must use 0. */
393
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100394 /*
395 * Don't stop the tick if the selected state is a polling one or if the
396 * expected idle duration is shorter than the tick period length.
397 */
Rafael J. Wysocki5ef499c2018-08-14 12:34:40 +0200398 if (((drv->states[idx].flags & CPUIDLE_FLAG_POLLING) ||
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100399 predicted_ns < TICK_NSEC) && !tick_nohz_tick_stopped()) {
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100400 *stop_tick = false;
401
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100402 if (idx > 0 && drv->states[idx].target_residency_ns > delta_next) {
Rafael J. Wysocki296bb1e2018-04-05 19:12:34 +0200403 /*
404 * The tick is not going to be stopped and the target
405 * residency of the state to be returned is not within
406 * the time until the next timer event including the
407 * tick, so try to correct that.
408 */
409 for (i = idx - 1; i >= 0; i--) {
Rafael J. Wysocki99e98d32019-11-04 12:16:17 +0100410 if (dev->states_usage[i].disable)
Rafael J. Wysocki296bb1e2018-04-05 19:12:34 +0200411 continue;
412
413 idx = i;
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100414 if (drv->states[i].target_residency_ns <= delta_next)
Rafael J. Wysocki296bb1e2018-04-05 19:12:34 +0200415 break;
416 }
417 }
418 }
419
Rafael J. Wysockieb40a382018-10-02 23:45:07 +0200420 return idx;
Len Brown4f86d3a2007-10-03 18:58:00 -0400421}
422
423/**
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700424 * menu_reflect - records that data structures need update
Len Brown4f86d3a2007-10-03 18:58:00 -0400425 * @dev: the CPU
Deepthi Dharware978aa72011-10-28 16:20:09 +0530426 * @index: the index of actual entered state
Len Brown4f86d3a2007-10-03 18:58:00 -0400427 *
428 * NOTE: it's important to be fast here because this operation will add to
429 * the overall exit latency.
430 */
Deepthi Dharware978aa72011-10-28 16:20:09 +0530431static void menu_reflect(struct cpuidle_device *dev, int index)
Len Brown4f86d3a2007-10-03 18:58:00 -0400432{
Christoph Lameter229b6862014-08-17 12:30:30 -0500433 struct menu_device *data = this_cpu_ptr(&menu_devices);
Rafael J. Wysockia802ea92015-05-04 22:53:28 +0200434
Marcelo Tosatti7d4daee2019-07-03 20:51:27 -0300435 dev->last_state_idx = index;
Rafael J. Wysockia802ea92015-05-04 22:53:28 +0200436 data->needs_update = 1;
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100437 data->tick_wakeup = tick_nohz_idle_got_tick();
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700438}
439
440/**
441 * menu_update - attempts to guess what happened after entry
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530442 * @drv: cpuidle driver containing state data
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700443 * @dev: the CPU
444 */
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530445static void menu_update(struct cpuidle_driver *drv, struct cpuidle_device *dev)
Corrado Zoccolo672917d2009-09-21 17:04:09 -0700446{
Christoph Lameter229b6862014-08-17 12:30:30 -0500447 struct menu_device *data = this_cpu_ptr(&menu_devices);
Marcelo Tosatti7d4daee2019-07-03 20:51:27 -0300448 int last_idx = dev->last_state_idx;
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530449 struct cpuidle_state *target = &drv->states[last_idx];
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100450 u64 measured_ns;
Tuukka Tikkanen51f245b2013-08-14 19:02:41 +0300451 unsigned int new_factor;
Len Brown4f86d3a2007-10-03 18:58:00 -0400452
453 /*
tuukka.tikkanen@linaro.org61c66d62014-02-24 08:29:34 +0200454 * Try to figure out how much time passed between entry to low
455 * power state and occurrence of the wakeup event.
456 *
457 * If the entered idle state didn't support residency measurements,
Len Brown4108b3d2014-12-16 01:52:06 -0500458 * we use them anyway if they are short, and if long,
459 * truncate to the whole expected time.
tuukka.tikkanen@linaro.org61c66d62014-02-24 08:29:34 +0200460 *
461 * Any measured amount of time will include the exit latency.
462 * Since we are interested in when the wakeup begun, not when it
Antonio Ospite2fba5372014-06-04 14:03:45 +0200463 * was completed, we must subtract the exit latency. However, if
tuukka.tikkanen@linaro.org61c66d62014-02-24 08:29:34 +0200464 * the measured amount of time is less than the exit latency,
465 * assume the state was never reached and the exit latency is 0.
Len Brown4f86d3a2007-10-03 18:58:00 -0400466 */
Len Brown4108b3d2014-12-16 01:52:06 -0500467
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100468 if (data->tick_wakeup && data->next_timer_ns > TICK_NSEC) {
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100469 /*
470 * The nohz code said that there wouldn't be any events within
471 * the tick boundary (if the tick was stopped), but the idle
472 * duration predictor had a differing opinion. Since the CPU
473 * was woken up by a tick (that wasn't stopped after all), the
474 * predictor was not quite right, so assume that the CPU could
475 * have been idle long (but not forever) to help the idle
476 * duration predictor do a better job next time.
477 */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100478 measured_ns = 9 * MAX_INTERESTING / 10;
Rafael J. Wysocki5f26bdc2018-10-02 23:42:02 +0200479 } else if ((drv->states[last_idx].flags & CPUIDLE_FLAG_POLLING) &&
480 dev->poll_time_limit) {
481 /*
482 * The CPU exited the "polling" state due to a time limit, so
483 * the idle duration prediction leading to the selection of that
484 * state was inaccurate. If a better prediction had been made,
485 * the CPU might have been woken up from idle by the next timer.
486 * Assume that to be the case.
487 */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100488 measured_ns = data->next_timer_ns;
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100489 } else {
490 /* measured value */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100491 measured_ns = dev->last_residency_ns;
Len Brown4108b3d2014-12-16 01:52:06 -0500492
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100493 /* Deduct exit latency */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100494 if (measured_ns > 2 * target->exit_latency_ns)
495 measured_ns -= target->exit_latency_ns;
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100496 else
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100497 measured_ns /= 2;
Rafael J. Wysocki45f1ff52018-03-22 17:50:49 +0100498 }
Len Brown4108b3d2014-12-16 01:52:06 -0500499
500 /* Make sure our coefficients do not exceed unity */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100501 if (measured_ns > data->next_timer_ns)
502 measured_ns = data->next_timer_ns;
Arjan van de Ven69d25872009-09-21 17:04:08 -0700503
Tuukka Tikkanen51f245b2013-08-14 19:02:41 +0300504 /* Update our correction ratio */
505 new_factor = data->correction_factor[data->bucket];
506 new_factor -= new_factor / DECAY;
Arjan van de Ven69d25872009-09-21 17:04:08 -0700507
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100508 if (data->next_timer_ns > 0 && measured_ns < MAX_INTERESTING)
509 new_factor += div64_u64(RESOLUTION * measured_ns,
510 data->next_timer_ns);
venkatesh.pallipadi@intel.com320eee72008-07-30 19:21:43 -0700511 else
Arjan van de Ven69d25872009-09-21 17:04:08 -0700512 /*
513 * we were idle so long that we count it as a perfect
514 * prediction
515 */
516 new_factor += RESOLUTION;
venkatesh.pallipadi@intel.com320eee72008-07-30 19:21:43 -0700517
Arjan van de Ven69d25872009-09-21 17:04:08 -0700518 /*
519 * We don't want 0 as factor; we always want at least
Tuukka Tikkanen51f245b2013-08-14 19:02:41 +0300520 * a tiny bit of estimated time. Fortunately, due to rounding,
521 * new_factor will stay nonzero regardless of measured_us values
522 * and the compiler can eliminate this test as long as DECAY > 1.
Arjan van de Ven69d25872009-09-21 17:04:08 -0700523 */
Tuukka Tikkanen51f245b2013-08-14 19:02:41 +0300524 if (DECAY == 1 && unlikely(new_factor == 0))
Arjan van de Ven69d25872009-09-21 17:04:08 -0700525 new_factor = 1;
venkatesh.pallipadi@intel.com320eee72008-07-30 19:21:43 -0700526
Arjan van de Ven69d25872009-09-21 17:04:08 -0700527 data->correction_factor[data->bucket] = new_factor;
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700528
529 /* update the repeating-pattern data */
Rafael J. Wysockic1d51f62019-11-07 15:25:12 +0100530 data->intervals[data->interval_ptr++] = ktime_to_us(measured_ns);
Arjan van de Ven1f85f872010-05-24 14:32:59 -0700531 if (data->interval_ptr >= INTERVALS)
532 data->interval_ptr = 0;
Len Brown4f86d3a2007-10-03 18:58:00 -0400533}
534
535/**
536 * menu_enable_device - scans a CPU's states and does setup
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530537 * @drv: cpuidle driver
Len Brown4f86d3a2007-10-03 18:58:00 -0400538 * @dev: the CPU
539 */
Deepthi Dharwar46bcfad2011-10-28 16:20:42 +0530540static int menu_enable_device(struct cpuidle_driver *drv,
541 struct cpuidle_device *dev)
Len Brown4f86d3a2007-10-03 18:58:00 -0400542{
543 struct menu_device *data = &per_cpu(menu_devices, dev->cpu);
Chander Kashyapbed4d592014-04-22 18:08:04 +0530544 int i;
Len Brown4f86d3a2007-10-03 18:58:00 -0400545
546 memset(data, 0, sizeof(struct menu_device));
547
Chander Kashyapbed4d592014-04-22 18:08:04 +0530548 /*
549 * if the correction factor is 0 (eg first time init or cpu hotplug
550 * etc), we actually want to start out with a unity factor.
551 */
552 for(i = 0; i < BUCKETS; i++)
553 data->correction_factor[i] = RESOLUTION * DECAY;
554
Len Brown4f86d3a2007-10-03 18:58:00 -0400555 return 0;
556}
557
558static struct cpuidle_governor menu_governor = {
559 .name = "menu",
560 .rating = 20,
561 .enable = menu_enable_device,
562 .select = menu_select,
563 .reflect = menu_reflect,
Len Brown4f86d3a2007-10-03 18:58:00 -0400564};
565
566/**
567 * init_menu - initializes the governor
568 */
569static int __init init_menu(void)
570{
571 return cpuidle_register_governor(&menu_governor);
572}
573
Daniel Lezcano137b9442013-06-12 15:08:48 +0200574postcore_initcall(init_menu);