Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 1 | /* |
| 2 | * menu.c - the menu idle governor |
| 3 | * |
| 4 | * Copyright (C) 2006-2007 Adam Belay <abelay@novell.com> |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 5 | * Copyright (C) 2009 Intel Corporation |
| 6 | * Author: |
| 7 | * Arjan van de Ven <arjan@linux.intel.com> |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 8 | * |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 9 | * This code is licenced under the GPL version 2 as described |
| 10 | * in the COPYING file that acompanies the Linux Kernel. |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 11 | */ |
| 12 | |
| 13 | #include <linux/kernel.h> |
| 14 | #include <linux/cpuidle.h> |
Jean Pihet | e8db0be | 2011-08-25 15:35:03 +0200 | [diff] [blame] | 15 | #include <linux/pm_qos.h> |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 16 | #include <linux/time.h> |
| 17 | #include <linux/ktime.h> |
| 18 | #include <linux/hrtimer.h> |
| 19 | #include <linux/tick.h> |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 20 | #include <linux/sched.h> |
Stephen Hemminger | 5787536 | 2010-01-08 14:43:08 -0800 | [diff] [blame] | 21 | #include <linux/math64.h> |
Paul Gortmaker | 884b17e | 2011-08-29 17:52:39 -0400 | [diff] [blame] | 22 | #include <linux/module.h> |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 23 | |
Tuukka Tikkanen | decd51b | 2013-08-14 19:02:40 +0300 | [diff] [blame] | 24 | /* |
| 25 | * Please note when changing the tuning values: |
| 26 | * If (MAX_INTERESTING-1) * RESOLUTION > UINT_MAX, the result of |
| 27 | * a scaling operation multiplication may overflow on 32 bit platforms. |
| 28 | * In that case, #define RESOLUTION as ULL to get 64 bit result: |
| 29 | * #define RESOLUTION 1024ULL |
| 30 | * |
| 31 | * The default values do not overflow. |
| 32 | */ |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 33 | #define BUCKETS 12 |
Mel Gorman | ae77930 | 2014-08-06 14:19:18 +0100 | [diff] [blame] | 34 | #define INTERVAL_SHIFT 3 |
| 35 | #define INTERVALS (1UL << INTERVAL_SHIFT) |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 36 | #define RESOLUTION 1024 |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 37 | #define DECAY 8 |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 38 | #define MAX_INTERESTING 50000 |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 39 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 40 | |
| 41 | /* |
| 42 | * Concepts and ideas behind the menu governor |
| 43 | * |
| 44 | * For the menu governor, there are 3 decision factors for picking a C |
| 45 | * state: |
| 46 | * 1) Energy break even point |
| 47 | * 2) Performance impact |
| 48 | * 3) Latency tolerance (from pmqos infrastructure) |
| 49 | * These these three factors are treated independently. |
| 50 | * |
| 51 | * Energy break even point |
| 52 | * ----------------------- |
| 53 | * C state entry and exit have an energy cost, and a certain amount of time in |
| 54 | * the C state is required to actually break even on this cost. CPUIDLE |
| 55 | * provides us this duration in the "target_residency" field. So all that we |
| 56 | * need is a good prediction of how long we'll be idle. Like the traditional |
| 57 | * menu governor, we start with the actual known "next timer event" time. |
| 58 | * |
| 59 | * Since there are other source of wakeups (interrupts for example) than |
| 60 | * the next timer event, this estimation is rather optimistic. To get a |
| 61 | * more realistic estimate, a correction factor is applied to the estimate, |
| 62 | * that is based on historic behavior. For example, if in the past the actual |
| 63 | * duration always was 50% of the next timer tick, the correction factor will |
| 64 | * be 0.5. |
| 65 | * |
| 66 | * menu uses a running average for this correction factor, however it uses a |
| 67 | * set of factors, not just a single factor. This stems from the realization |
| 68 | * that the ratio is dependent on the order of magnitude of the expected |
| 69 | * duration; if we expect 500 milliseconds of idle time the likelihood of |
| 70 | * getting an interrupt very early is much higher than if we expect 50 micro |
| 71 | * seconds of idle time. A second independent factor that has big impact on |
| 72 | * the actual factor is if there is (disk) IO outstanding or not. |
| 73 | * (as a special twist, we consider every sleep longer than 50 milliseconds |
| 74 | * as perfect; there are no power gains for sleeping longer than this) |
| 75 | * |
| 76 | * For these two reasons we keep an array of 12 independent factors, that gets |
| 77 | * indexed based on the magnitude of the expected duration as well as the |
| 78 | * "is IO outstanding" property. |
| 79 | * |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 80 | * Repeatable-interval-detector |
| 81 | * ---------------------------- |
| 82 | * There are some cases where "next timer" is a completely unusable predictor: |
| 83 | * Those cases where the interval is fixed, for example due to hardware |
| 84 | * interrupt mitigation, but also due to fixed transfer rate devices such as |
| 85 | * mice. |
| 86 | * For this, we use a different predictor: We track the duration of the last 8 |
| 87 | * intervals and if the stand deviation of these 8 intervals is below a |
| 88 | * threshold value, we use the average of these intervals as prediction. |
| 89 | * |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 90 | * Limiting Performance Impact |
| 91 | * --------------------------- |
| 92 | * C states, especially those with large exit latencies, can have a real |
Lucas De Marchi | 20e3341 | 2010-09-07 12:53:49 -0400 | [diff] [blame] | 93 | * noticeable impact on workloads, which is not acceptable for most sysadmins, |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 94 | * and in addition, less performance has a power price of its own. |
| 95 | * |
| 96 | * As a general rule of thumb, menu assumes that the following heuristic |
| 97 | * holds: |
| 98 | * The busier the system, the less impact of C states is acceptable |
| 99 | * |
| 100 | * This rule-of-thumb is implemented using a performance-multiplier: |
| 101 | * If the exit latency times the performance multiplier is longer than |
| 102 | * the predicted duration, the C state is not considered a candidate |
| 103 | * for selection due to a too high performance impact. So the higher |
| 104 | * this multiplier is, the longer we need to be idle to pick a deep C |
| 105 | * state, and thus the less likely a busy CPU will hit such a deep |
| 106 | * C state. |
| 107 | * |
| 108 | * Two factors are used in determing this multiplier: |
| 109 | * a value of 10 is added for each point of "per cpu load average" we have. |
| 110 | * a value of 5 points is added for each process that is waiting for |
| 111 | * IO on this CPU. |
| 112 | * (these values are experimentally determined) |
| 113 | * |
| 114 | * The load average factor gives a longer term (few seconds) input to the |
| 115 | * decision, while the iowait value gives a cpu local instantanious input. |
| 116 | * The iowait factor may look low, but realize that this is also already |
| 117 | * represented in the system load average. |
| 118 | * |
| 119 | */ |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 120 | |
| 121 | struct menu_device { |
| 122 | int last_state_idx; |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 123 | int needs_update; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 124 | |
tuukka.tikkanen@linaro.org | 5dc2f5a | 2014-02-24 08:29:31 +0200 | [diff] [blame] | 125 | unsigned int next_timer_us; |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 126 | unsigned int predicted_us; |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 127 | unsigned int bucket; |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 128 | unsigned int correction_factor[BUCKETS]; |
Tuukka Tikkanen | 939e33b | 2013-08-14 19:02:38 +0300 | [diff] [blame] | 129 | unsigned int intervals[INTERVALS]; |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 130 | int interval_ptr; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 131 | }; |
| 132 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 133 | |
| 134 | #define LOAD_INT(x) ((x) >> FSHIFT) |
| 135 | #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100) |
| 136 | |
Mel Gorman | 372ba8c | 2014-08-06 14:19:21 +0100 | [diff] [blame] | 137 | static inline int get_loadavg(unsigned long load) |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 138 | { |
Mel Gorman | 372ba8c | 2014-08-06 14:19:21 +0100 | [diff] [blame] | 139 | return LOAD_INT(load) * 10 + LOAD_FRAC(load) / 10; |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 140 | } |
| 141 | |
Mel Gorman | 64b4ca5 | 2014-08-06 14:19:20 +0100 | [diff] [blame] | 142 | static inline int which_bucket(unsigned int duration, unsigned long nr_iowaiters) |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 143 | { |
| 144 | int bucket = 0; |
| 145 | |
| 146 | /* |
| 147 | * We keep two groups of stats; one with no |
| 148 | * IO pending, one without. |
| 149 | * This allows us to calculate |
| 150 | * E(duration)|iowait |
| 151 | */ |
Mel Gorman | 64b4ca5 | 2014-08-06 14:19:20 +0100 | [diff] [blame] | 152 | if (nr_iowaiters) |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 153 | bucket = BUCKETS/2; |
| 154 | |
| 155 | if (duration < 10) |
| 156 | return bucket; |
| 157 | if (duration < 100) |
| 158 | return bucket + 1; |
| 159 | if (duration < 1000) |
| 160 | return bucket + 2; |
| 161 | if (duration < 10000) |
| 162 | return bucket + 3; |
| 163 | if (duration < 100000) |
| 164 | return bucket + 4; |
| 165 | return bucket + 5; |
| 166 | } |
| 167 | |
| 168 | /* |
| 169 | * Return a multiplier for the exit latency that is intended |
| 170 | * to take performance requirements into account. |
| 171 | * The more performance critical we estimate the system |
| 172 | * to be, the higher this multiplier, and thus the higher |
| 173 | * the barrier to go to an expensive C state. |
| 174 | */ |
Mel Gorman | 372ba8c | 2014-08-06 14:19:21 +0100 | [diff] [blame] | 175 | static inline int performance_multiplier(unsigned long nr_iowaiters, unsigned long load) |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 176 | { |
| 177 | int mult = 1; |
| 178 | |
| 179 | /* for higher loadavg, we are more reluctant */ |
| 180 | |
Mel Gorman | 372ba8c | 2014-08-06 14:19:21 +0100 | [diff] [blame] | 181 | mult += 2 * get_loadavg(load); |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 182 | |
| 183 | /* for IO wait tasks (per cpu!) we add 5x each */ |
Mel Gorman | 64b4ca5 | 2014-08-06 14:19:20 +0100 | [diff] [blame] | 184 | mult += 10 * nr_iowaiters; |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 185 | |
| 186 | return mult; |
| 187 | } |
| 188 | |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 189 | static DEFINE_PER_CPU(struct menu_device, menu_devices); |
| 190 | |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 191 | static void menu_update(struct cpuidle_driver *drv, struct cpuidle_device *dev); |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 192 | |
Stephen Hemminger | 5787536 | 2010-01-08 14:43:08 -0800 | [diff] [blame] | 193 | /* This implements DIV_ROUND_CLOSEST but avoids 64 bit division */ |
| 194 | static u64 div_round64(u64 dividend, u32 divisor) |
| 195 | { |
| 196 | return div_u64(dividend + (divisor / 2), divisor); |
| 197 | } |
| 198 | |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 199 | /* |
| 200 | * Try detecting repeating patterns by keeping track of the last 8 |
| 201 | * intervals, and checking if the standard deviation of that set |
| 202 | * of points is below a threshold. If it is... then use the |
| 203 | * average of these 8 points as the estimated value. |
| 204 | */ |
Rafael J. Wysocki | 1485191 | 2013-07-27 01:41:34 +0200 | [diff] [blame] | 205 | static void get_typical_interval(struct menu_device *data) |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 206 | { |
Tuukka Tikkanen | 4cd46bc | 2013-08-14 19:02:37 +0300 | [diff] [blame] | 207 | int i, divisor; |
Tuukka Tikkanen | 0e96d5a | 2013-08-14 19:02:39 +0300 | [diff] [blame] | 208 | unsigned int max, thresh; |
| 209 | uint64_t avg, stddev; |
| 210 | |
| 211 | thresh = UINT_MAX; /* Discard outliers above this value */ |
Youquan Song | c96ca4f | 2012-10-26 12:27:07 +0200 | [diff] [blame] | 212 | |
| 213 | again: |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 214 | |
Tuukka Tikkanen | 0e96d5a | 2013-08-14 19:02:39 +0300 | [diff] [blame] | 215 | /* First calculate the average of past intervals */ |
Tuukka Tikkanen | 4cd46bc | 2013-08-14 19:02:37 +0300 | [diff] [blame] | 216 | max = 0; |
| 217 | avg = 0; |
| 218 | divisor = 0; |
Youquan Song | c96ca4f | 2012-10-26 12:27:07 +0200 | [diff] [blame] | 219 | for (i = 0; i < INTERVALS; i++) { |
Tuukka Tikkanen | 0e96d5a | 2013-08-14 19:02:39 +0300 | [diff] [blame] | 220 | unsigned int value = data->intervals[i]; |
Youquan Song | c96ca4f | 2012-10-26 12:27:07 +0200 | [diff] [blame] | 221 | if (value <= thresh) { |
| 222 | avg += value; |
| 223 | divisor++; |
| 224 | if (value > max) |
| 225 | max = value; |
| 226 | } |
| 227 | } |
Mel Gorman | ae77930 | 2014-08-06 14:19:18 +0100 | [diff] [blame] | 228 | if (divisor == INTERVALS) |
| 229 | avg >>= INTERVAL_SHIFT; |
| 230 | else |
| 231 | do_div(avg, divisor); |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 232 | |
Tuukka Tikkanen | 0e96d5a | 2013-08-14 19:02:39 +0300 | [diff] [blame] | 233 | /* Then try to determine standard deviation */ |
| 234 | stddev = 0; |
Youquan Song | c96ca4f | 2012-10-26 12:27:07 +0200 | [diff] [blame] | 235 | for (i = 0; i < INTERVALS; i++) { |
Tuukka Tikkanen | 0e96d5a | 2013-08-14 19:02:39 +0300 | [diff] [blame] | 236 | unsigned int value = data->intervals[i]; |
Youquan Song | c96ca4f | 2012-10-26 12:27:07 +0200 | [diff] [blame] | 237 | if (value <= thresh) { |
| 238 | int64_t diff = value - avg; |
| 239 | stddev += diff * diff; |
| 240 | } |
| 241 | } |
Mel Gorman | ae77930 | 2014-08-06 14:19:18 +0100 | [diff] [blame] | 242 | if (divisor == INTERVALS) |
| 243 | stddev >>= INTERVAL_SHIFT; |
| 244 | else |
| 245 | do_div(stddev, divisor); |
| 246 | |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 247 | /* |
Youquan Song | c96ca4f | 2012-10-26 12:27:07 +0200 | [diff] [blame] | 248 | * The typical interval is obtained when standard deviation is small |
| 249 | * or standard deviation is small compared to the average interval. |
Tuukka Tikkanen | 330647a | 2013-08-14 19:02:34 +0300 | [diff] [blame] | 250 | * |
Tuukka Tikkanen | 0d6a7ff | 2013-08-14 19:02:36 +0300 | [diff] [blame] | 251 | * int_sqrt() formal parameter type is unsigned long. When the |
| 252 | * greatest difference to an outlier exceeds ~65 ms * sqrt(divisor) |
| 253 | * the resulting squared standard deviation exceeds the input domain |
| 254 | * of int_sqrt on platforms where unsigned long is 32 bits in size. |
| 255 | * In such case reject the candidate average. |
| 256 | * |
Tuukka Tikkanen | 330647a | 2013-08-14 19:02:34 +0300 | [diff] [blame] | 257 | * Use this result only if there is no timer to wake us up sooner. |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 258 | */ |
Tuukka Tikkanen | 0d6a7ff | 2013-08-14 19:02:36 +0300 | [diff] [blame] | 259 | if (likely(stddev <= ULONG_MAX)) { |
| 260 | stddev = int_sqrt(stddev); |
| 261 | if (((avg > stddev * 6) && (divisor * 4 >= INTERVALS * 3)) |
Youquan Song | c96ca4f | 2012-10-26 12:27:07 +0200 | [diff] [blame] | 262 | || stddev <= 20) { |
tuukka.tikkanen@linaro.org | 5dc2f5a | 2014-02-24 08:29:31 +0200 | [diff] [blame] | 263 | if (data->next_timer_us > avg) |
Tuukka Tikkanen | 0d6a7ff | 2013-08-14 19:02:36 +0300 | [diff] [blame] | 264 | data->predicted_us = avg; |
| 265 | return; |
| 266 | } |
Youquan Song | 69a37be | 2012-10-26 12:26:41 +0200 | [diff] [blame] | 267 | } |
Tuukka Tikkanen | 017099e | 2013-08-14 19:02:35 +0300 | [diff] [blame] | 268 | |
| 269 | /* |
| 270 | * If we have outliers to the upside in our distribution, discard |
| 271 | * those by setting the threshold to exclude these outliers, then |
| 272 | * calculate the average and standard deviation again. Once we get |
| 273 | * down to the bottom 3/4 of our samples, stop excluding samples. |
| 274 | * |
| 275 | * This can deal with workloads that have long pauses interspersed |
| 276 | * with sporadic activity with a bunch of short pauses. |
| 277 | */ |
| 278 | if ((divisor * 4) <= INTERVALS * 3) |
| 279 | return; |
| 280 | |
| 281 | thresh = max - 1; |
| 282 | goto again; |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 283 | } |
| 284 | |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 285 | /** |
| 286 | * menu_select - selects the next idle state to enter |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 287 | * @drv: cpuidle driver containing state data |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 288 | * @dev: the CPU |
| 289 | */ |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 290 | static int menu_select(struct cpuidle_driver *drv, struct cpuidle_device *dev) |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 291 | { |
Christoph Lameter | 229b686 | 2014-08-17 12:30:30 -0500 | [diff] [blame] | 292 | struct menu_device *data = this_cpu_ptr(&menu_devices); |
Mark Gross | ed77134 | 2010-05-06 01:59:26 +0200 | [diff] [blame] | 293 | int latency_req = pm_qos_request(PM_QOS_CPU_DMA_LATENCY); |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 294 | int i; |
tuukka.tikkanen@linaro.org | 96e9518 | 2014-02-24 08:29:35 +0200 | [diff] [blame] | 295 | unsigned int interactivity_req; |
Mel Gorman | 372ba8c | 2014-08-06 14:19:21 +0100 | [diff] [blame] | 296 | unsigned long nr_iowaiters, cpu_load; |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 297 | |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 298 | if (data->needs_update) { |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 299 | menu_update(drv, dev); |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 300 | data->needs_update = 0; |
| 301 | } |
| 302 | |
Rafael J. Wysocki | 3836785 | 2014-05-01 00:14:04 +0200 | [diff] [blame] | 303 | data->last_state_idx = CPUIDLE_DRIVER_STATE_START - 1; |
Arjan van de Ven | 1c6fe03 | 2010-05-08 15:47:37 -0700 | [diff] [blame] | 304 | |
venkatesh.pallipadi@intel.com | a2bd9202 | 2008-07-30 19:21:42 -0700 | [diff] [blame] | 305 | /* Special case when user has set very strict latency requirement */ |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 306 | if (unlikely(latency_req == 0)) |
venkatesh.pallipadi@intel.com | a2bd9202 | 2008-07-30 19:21:42 -0700 | [diff] [blame] | 307 | return 0; |
venkatesh.pallipadi@intel.com | a2bd9202 | 2008-07-30 19:21:42 -0700 | [diff] [blame] | 308 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 309 | /* determine the expected residency time, round up */ |
Mel Gorman | 107d4f4 | 2014-08-06 14:19:19 +0100 | [diff] [blame] | 310 | data->next_timer_us = ktime_to_us(tick_nohz_get_sleep_length()); |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 311 | |
Mel Gorman | 372ba8c | 2014-08-06 14:19:21 +0100 | [diff] [blame] | 312 | get_iowait_load(&nr_iowaiters, &cpu_load); |
Mel Gorman | 64b4ca5 | 2014-08-06 14:19:20 +0100 | [diff] [blame] | 313 | data->bucket = which_bucket(data->next_timer_us, nr_iowaiters); |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 314 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 315 | /* |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 316 | * Force the result of multiplication to be 64 bits even if both |
| 317 | * operands are 32 bits. |
| 318 | * Make sure to round up for half microseconds. |
| 319 | */ |
tuukka.tikkanen@linaro.org | 5dc2f5a | 2014-02-24 08:29:31 +0200 | [diff] [blame] | 320 | data->predicted_us = div_round64((uint64_t)data->next_timer_us * |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 321 | data->correction_factor[data->bucket], |
Stephen Hemminger | 5787536 | 2010-01-08 14:43:08 -0800 | [diff] [blame] | 322 | RESOLUTION * DECAY); |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 323 | |
Rafael J. Wysocki | 1485191 | 2013-07-27 01:41:34 +0200 | [diff] [blame] | 324 | get_typical_interval(data); |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 325 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 326 | /* |
tuukka.tikkanen@linaro.org | 96e9518 | 2014-02-24 08:29:35 +0200 | [diff] [blame] | 327 | * Performance multiplier defines a minimum predicted idle |
| 328 | * duration / latency ratio. Adjust the latency limit if |
| 329 | * necessary. |
| 330 | */ |
Mel Gorman | 372ba8c | 2014-08-06 14:19:21 +0100 | [diff] [blame] | 331 | interactivity_req = data->predicted_us / performance_multiplier(nr_iowaiters, cpu_load); |
tuukka.tikkanen@linaro.org | 96e9518 | 2014-02-24 08:29:35 +0200 | [diff] [blame] | 332 | if (latency_req > interactivity_req) |
| 333 | latency_req = interactivity_req; |
| 334 | |
| 335 | /* |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 336 | * We want to default to C1 (hlt), not to busy polling |
| 337 | * unless the timer is happening really really soon. |
| 338 | */ |
tuukka.tikkanen@linaro.org | 5dc2f5a | 2014-02-24 08:29:31 +0200 | [diff] [blame] | 339 | if (data->next_timer_us > 5 && |
Rafael J. Wysocki | cbc9ef0 | 2012-07-03 19:07:42 +0200 | [diff] [blame] | 340 | !drv->states[CPUIDLE_DRIVER_STATE_START].disabled && |
ShuoX Liu | dc7fd27 | 2012-07-03 19:05:31 +0200 | [diff] [blame] | 341 | dev->states_usage[CPUIDLE_DRIVER_STATE_START].disable == 0) |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 342 | data->last_state_idx = CPUIDLE_DRIVER_STATE_START; |
| 343 | |
Ai Li | 71abbbf | 2010-08-09 17:20:13 -0700 | [diff] [blame] | 344 | /* |
| 345 | * Find the idle state with the lowest power while satisfying |
| 346 | * our constraints. |
| 347 | */ |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 348 | for (i = CPUIDLE_DRIVER_STATE_START; i < drv->state_count; i++) { |
| 349 | struct cpuidle_state *s = &drv->states[i]; |
ShuoX Liu | dc7fd27 | 2012-07-03 19:05:31 +0200 | [diff] [blame] | 350 | struct cpuidle_state_usage *su = &dev->states_usage[i]; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 351 | |
Rafael J. Wysocki | cbc9ef0 | 2012-07-03 19:07:42 +0200 | [diff] [blame] | 352 | if (s->disabled || su->disable) |
ShuoX Liu | 3a53396 | 2012-03-28 15:19:11 -0700 | [diff] [blame] | 353 | continue; |
Rafael J. Wysocki | 1485191 | 2013-07-27 01:41:34 +0200 | [diff] [blame] | 354 | if (s->target_residency > data->predicted_us) |
Ai Li | 71abbbf | 2010-08-09 17:20:13 -0700 | [diff] [blame] | 355 | continue; |
venkatesh.pallipadi@intel.com | a2bd9202 | 2008-07-30 19:21:42 -0700 | [diff] [blame] | 356 | if (s->exit_latency > latency_req) |
Ai Li | 71abbbf | 2010-08-09 17:20:13 -0700 | [diff] [blame] | 357 | continue; |
Ai Li | 71abbbf | 2010-08-09 17:20:13 -0700 | [diff] [blame] | 358 | |
Daniel Lezcano | 8aef33a | 2013-01-15 14:18:04 +0100 | [diff] [blame] | 359 | data->last_state_idx = i; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 360 | } |
| 361 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 362 | return data->last_state_idx; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 363 | } |
| 364 | |
| 365 | /** |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 366 | * menu_reflect - records that data structures need update |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 367 | * @dev: the CPU |
Deepthi Dharwar | e978aa7 | 2011-10-28 16:20:09 +0530 | [diff] [blame] | 368 | * @index: the index of actual entered state |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 369 | * |
| 370 | * NOTE: it's important to be fast here because this operation will add to |
| 371 | * the overall exit latency. |
| 372 | */ |
Deepthi Dharwar | e978aa7 | 2011-10-28 16:20:09 +0530 | [diff] [blame] | 373 | static void menu_reflect(struct cpuidle_device *dev, int index) |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 374 | { |
Christoph Lameter | 229b686 | 2014-08-17 12:30:30 -0500 | [diff] [blame] | 375 | struct menu_device *data = this_cpu_ptr(&menu_devices); |
Deepthi Dharwar | e978aa7 | 2011-10-28 16:20:09 +0530 | [diff] [blame] | 376 | data->last_state_idx = index; |
| 377 | if (index >= 0) |
| 378 | data->needs_update = 1; |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 379 | } |
| 380 | |
| 381 | /** |
| 382 | * menu_update - attempts to guess what happened after entry |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 383 | * @drv: cpuidle driver containing state data |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 384 | * @dev: the CPU |
| 385 | */ |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 386 | static void menu_update(struct cpuidle_driver *drv, struct cpuidle_device *dev) |
Corrado Zoccolo | 672917d | 2009-09-21 17:04:09 -0700 | [diff] [blame] | 387 | { |
Christoph Lameter | 229b686 | 2014-08-17 12:30:30 -0500 | [diff] [blame] | 388 | struct menu_device *data = this_cpu_ptr(&menu_devices); |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 389 | int last_idx = data->last_state_idx; |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 390 | struct cpuidle_state *target = &drv->states[last_idx]; |
venkatesh.pallipadi@intel.com | 320eee7 | 2008-07-30 19:21:43 -0700 | [diff] [blame] | 391 | unsigned int measured_us; |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 392 | unsigned int new_factor; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 393 | |
| 394 | /* |
tuukka.tikkanen@linaro.org | 61c66d6 | 2014-02-24 08:29:34 +0200 | [diff] [blame] | 395 | * Try to figure out how much time passed between entry to low |
| 396 | * power state and occurrence of the wakeup event. |
| 397 | * |
| 398 | * If the entered idle state didn't support residency measurements, |
| 399 | * we are basically lost in the dark how much time passed. |
| 400 | * As a compromise, assume we slept for the whole expected time. |
| 401 | * |
| 402 | * Any measured amount of time will include the exit latency. |
| 403 | * Since we are interested in when the wakeup begun, not when it |
Antonio Ospite | 2fba537 | 2014-06-04 14:03:45 +0200 | [diff] [blame] | 404 | * was completed, we must subtract the exit latency. However, if |
tuukka.tikkanen@linaro.org | 61c66d6 | 2014-02-24 08:29:34 +0200 | [diff] [blame] | 405 | * the measured amount of time is less than the exit latency, |
| 406 | * assume the state was never reached and the exit latency is 0. |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 407 | */ |
tuukka.tikkanen@linaro.org | 61c66d6 | 2014-02-24 08:29:34 +0200 | [diff] [blame] | 408 | if (unlikely(!(target->flags & CPUIDLE_FLAG_TIME_VALID))) { |
| 409 | /* Use timer value as is */ |
tuukka.tikkanen@linaro.org | 7ac2643 | 2014-02-24 08:29:33 +0200 | [diff] [blame] | 410 | measured_us = data->next_timer_us; |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 411 | |
tuukka.tikkanen@linaro.org | 61c66d6 | 2014-02-24 08:29:34 +0200 | [diff] [blame] | 412 | } else { |
| 413 | /* Use measured value */ |
| 414 | measured_us = cpuidle_get_last_residency(dev); |
| 415 | |
| 416 | /* Deduct exit latency */ |
| 417 | if (measured_us > target->exit_latency) |
| 418 | measured_us -= target->exit_latency; |
| 419 | |
| 420 | /* Make sure our coefficients do not exceed unity */ |
| 421 | if (measured_us > data->next_timer_us) |
| 422 | measured_us = data->next_timer_us; |
| 423 | } |
| 424 | |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 425 | /* Update our correction ratio */ |
| 426 | new_factor = data->correction_factor[data->bucket]; |
| 427 | new_factor -= new_factor / DECAY; |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 428 | |
tuukka.tikkanen@linaro.org | 5dc2f5a | 2014-02-24 08:29:31 +0200 | [diff] [blame] | 429 | if (data->next_timer_us > 0 && measured_us < MAX_INTERESTING) |
| 430 | new_factor += RESOLUTION * measured_us / data->next_timer_us; |
venkatesh.pallipadi@intel.com | 320eee7 | 2008-07-30 19:21:43 -0700 | [diff] [blame] | 431 | else |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 432 | /* |
| 433 | * we were idle so long that we count it as a perfect |
| 434 | * prediction |
| 435 | */ |
| 436 | new_factor += RESOLUTION; |
venkatesh.pallipadi@intel.com | 320eee7 | 2008-07-30 19:21:43 -0700 | [diff] [blame] | 437 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 438 | /* |
| 439 | * We don't want 0 as factor; we always want at least |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 440 | * a tiny bit of estimated time. Fortunately, due to rounding, |
| 441 | * new_factor will stay nonzero regardless of measured_us values |
| 442 | * and the compiler can eliminate this test as long as DECAY > 1. |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 443 | */ |
Tuukka Tikkanen | 51f245b | 2013-08-14 19:02:41 +0300 | [diff] [blame] | 444 | if (DECAY == 1 && unlikely(new_factor == 0)) |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 445 | new_factor = 1; |
venkatesh.pallipadi@intel.com | 320eee7 | 2008-07-30 19:21:43 -0700 | [diff] [blame] | 446 | |
Arjan van de Ven | 69d2587 | 2009-09-21 17:04:08 -0700 | [diff] [blame] | 447 | data->correction_factor[data->bucket] = new_factor; |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 448 | |
| 449 | /* update the repeating-pattern data */ |
tuukka.tikkanen@linaro.org | 61c66d6 | 2014-02-24 08:29:34 +0200 | [diff] [blame] | 450 | data->intervals[data->interval_ptr++] = measured_us; |
Arjan van de Ven | 1f85f87 | 2010-05-24 14:32:59 -0700 | [diff] [blame] | 451 | if (data->interval_ptr >= INTERVALS) |
| 452 | data->interval_ptr = 0; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 453 | } |
| 454 | |
| 455 | /** |
| 456 | * menu_enable_device - scans a CPU's states and does setup |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 457 | * @drv: cpuidle driver |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 458 | * @dev: the CPU |
| 459 | */ |
Deepthi Dharwar | 46bcfad | 2011-10-28 16:20:42 +0530 | [diff] [blame] | 460 | static int menu_enable_device(struct cpuidle_driver *drv, |
| 461 | struct cpuidle_device *dev) |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 462 | { |
| 463 | struct menu_device *data = &per_cpu(menu_devices, dev->cpu); |
Chander Kashyap | bed4d59 | 2014-04-22 18:08:04 +0530 | [diff] [blame] | 464 | int i; |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 465 | |
| 466 | memset(data, 0, sizeof(struct menu_device)); |
| 467 | |
Chander Kashyap | bed4d59 | 2014-04-22 18:08:04 +0530 | [diff] [blame] | 468 | /* |
| 469 | * if the correction factor is 0 (eg first time init or cpu hotplug |
| 470 | * etc), we actually want to start out with a unity factor. |
| 471 | */ |
| 472 | for(i = 0; i < BUCKETS; i++) |
| 473 | data->correction_factor[i] = RESOLUTION * DECAY; |
| 474 | |
Len Brown | 4f86d3a | 2007-10-03 18:58:00 -0400 | [diff] [blame] | 475 | return 0; |
| 476 | } |
| 477 | |
| 478 | static struct cpuidle_governor menu_governor = { |
| 479 | .name = "menu", |
| 480 | .rating = 20, |
| 481 | .enable = menu_enable_device, |
| 482 | .select = menu_select, |
| 483 | .reflect = menu_reflect, |
| 484 | .owner = THIS_MODULE, |
| 485 | }; |
| 486 | |
| 487 | /** |
| 488 | * init_menu - initializes the governor |
| 489 | */ |
| 490 | static int __init init_menu(void) |
| 491 | { |
| 492 | return cpuidle_register_governor(&menu_governor); |
| 493 | } |
| 494 | |
Daniel Lezcano | 137b944 | 2013-06-12 15:08:48 +0200 | [diff] [blame] | 495 | postcore_initcall(init_menu); |