1 /* 2 * menu.c - the menu idle governor 3 * 4 * Copyright (C) 2006-2007 Adam Belay <abelay@novell.com> 5 * Copyright (C) 2009 Intel Corporation 6 * Author: 7 * Arjan van de Ven <arjan@linux.intel.com> 8 * 9 * This code is licenced under the GPL version 2 as described 10 * in the COPYING file that acompanies the Linux Kernel. 11 */ 12 13 #include <linux/kernel.h> 14 #include <linux/cpuidle.h> 15 #include <linux/pm_qos_params.h> 16 #include <linux/time.h> 17 #include <linux/ktime.h> 18 #include <linux/hrtimer.h> 19 #include <linux/tick.h> 20 #include <linux/sched.h> 21 22 #define BUCKETS 12 23 #define RESOLUTION 1024 24 #define DECAY 4 25 #define MAX_INTERESTING 50000 26 27 /* 28 * Concepts and ideas behind the menu governor 29 * 30 * For the menu governor, there are 3 decision factors for picking a C 31 * state: 32 * 1) Energy break even point 33 * 2) Performance impact 34 * 3) Latency tolerance (from pmqos infrastructure) 35 * These these three factors are treated independently. 36 * 37 * Energy break even point 38 * ----------------------- 39 * C state entry and exit have an energy cost, and a certain amount of time in 40 * the C state is required to actually break even on this cost. CPUIDLE 41 * provides us this duration in the "target_residency" field. So all that we 42 * need is a good prediction of how long we'll be idle. Like the traditional 43 * menu governor, we start with the actual known "next timer event" time. 44 * 45 * Since there are other source of wakeups (interrupts for example) than 46 * the next timer event, this estimation is rather optimistic. To get a 47 * more realistic estimate, a correction factor is applied to the estimate, 48 * that is based on historic behavior. For example, if in the past the actual 49 * duration always was 50% of the next timer tick, the correction factor will 50 * be 0.5. 51 * 52 * menu uses a running average for this correction factor, however it uses a 53 * set of factors, not just a single factor. This stems from the realization 54 * that the ratio is dependent on the order of magnitude of the expected 55 * duration; if we expect 500 milliseconds of idle time the likelihood of 56 * getting an interrupt very early is much higher than if we expect 50 micro 57 * seconds of idle time. A second independent factor that has big impact on 58 * the actual factor is if there is (disk) IO outstanding or not. 59 * (as a special twist, we consider every sleep longer than 50 milliseconds 60 * as perfect; there are no power gains for sleeping longer than this) 61 * 62 * For these two reasons we keep an array of 12 independent factors, that gets 63 * indexed based on the magnitude of the expected duration as well as the 64 * "is IO outstanding" property. 65 * 66 * Limiting Performance Impact 67 * --------------------------- 68 * C states, especially those with large exit latencies, can have a real 69 * noticable impact on workloads, which is not acceptable for most sysadmins, 70 * and in addition, less performance has a power price of its own. 71 * 72 * As a general rule of thumb, menu assumes that the following heuristic 73 * holds: 74 * The busier the system, the less impact of C states is acceptable 75 * 76 * This rule-of-thumb is implemented using a performance-multiplier: 77 * If the exit latency times the performance multiplier is longer than 78 * the predicted duration, the C state is not considered a candidate 79 * for selection due to a too high performance impact. So the higher 80 * this multiplier is, the longer we need to be idle to pick a deep C 81 * state, and thus the less likely a busy CPU will hit such a deep 82 * C state. 83 * 84 * Two factors are used in determing this multiplier: 85 * a value of 10 is added for each point of "per cpu load average" we have. 86 * a value of 5 points is added for each process that is waiting for 87 * IO on this CPU. 88 * (these values are experimentally determined) 89 * 90 * The load average factor gives a longer term (few seconds) input to the 91 * decision, while the iowait value gives a cpu local instantanious input. 92 * The iowait factor may look low, but realize that this is also already 93 * represented in the system load average. 94 * 95 */ 96 97 struct menu_device { 98 int last_state_idx; 99 int needs_update; 100 101 unsigned int expected_us; 102 u64 predicted_us; 103 unsigned int measured_us; 104 unsigned int exit_us; 105 unsigned int bucket; 106 u64 correction_factor[BUCKETS]; 107 }; 108 109 110 #define LOAD_INT(x) ((x) >> FSHIFT) 111 #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100) 112 113 static int get_loadavg(void) 114 { 115 unsigned long this = this_cpu_load(); 116 117 118 return LOAD_INT(this) * 10 + LOAD_FRAC(this) / 10; 119 } 120 121 static inline int which_bucket(unsigned int duration) 122 { 123 int bucket = 0; 124 125 /* 126 * We keep two groups of stats; one with no 127 * IO pending, one without. 128 * This allows us to calculate 129 * E(duration)|iowait 130 */ 131 if (nr_iowait_cpu()) 132 bucket = BUCKETS/2; 133 134 if (duration < 10) 135 return bucket; 136 if (duration < 100) 137 return bucket + 1; 138 if (duration < 1000) 139 return bucket + 2; 140 if (duration < 10000) 141 return bucket + 3; 142 if (duration < 100000) 143 return bucket + 4; 144 return bucket + 5; 145 } 146 147 /* 148 * Return a multiplier for the exit latency that is intended 149 * to take performance requirements into account. 150 * The more performance critical we estimate the system 151 * to be, the higher this multiplier, and thus the higher 152 * the barrier to go to an expensive C state. 153 */ 154 static inline int performance_multiplier(void) 155 { 156 int mult = 1; 157 158 /* for higher loadavg, we are more reluctant */ 159 160 mult += 2 * get_loadavg(); 161 162 /* for IO wait tasks (per cpu!) we add 5x each */ 163 mult += 10 * nr_iowait_cpu(); 164 165 return mult; 166 } 167 168 static DEFINE_PER_CPU(struct menu_device, menu_devices); 169 170 static void menu_update(struct cpuidle_device *dev); 171 172 /** 173 * menu_select - selects the next idle state to enter 174 * @dev: the CPU 175 */ 176 static int menu_select(struct cpuidle_device *dev) 177 { 178 struct menu_device *data = &__get_cpu_var(menu_devices); 179 int latency_req = pm_qos_requirement(PM_QOS_CPU_DMA_LATENCY); 180 int i; 181 int multiplier; 182 183 data->last_state_idx = 0; 184 data->exit_us = 0; 185 186 if (data->needs_update) { 187 menu_update(dev); 188 data->needs_update = 0; 189 } 190 191 /* Special case when user has set very strict latency requirement */ 192 if (unlikely(latency_req == 0)) 193 return 0; 194 195 /* determine the expected residency time, round up */ 196 data->expected_us = 197 DIV_ROUND_UP((u32)ktime_to_ns(tick_nohz_get_sleep_length()), 1000); 198 199 200 data->bucket = which_bucket(data->expected_us); 201 202 multiplier = performance_multiplier(); 203 204 /* 205 * if the correction factor is 0 (eg first time init or cpu hotplug 206 * etc), we actually want to start out with a unity factor. 207 */ 208 if (data->correction_factor[data->bucket] == 0) 209 data->correction_factor[data->bucket] = RESOLUTION * DECAY; 210 211 /* Make sure to round up for half microseconds */ 212 data->predicted_us = DIV_ROUND_CLOSEST( 213 data->expected_us * data->correction_factor[data->bucket], 214 RESOLUTION * DECAY); 215 216 /* 217 * We want to default to C1 (hlt), not to busy polling 218 * unless the timer is happening really really soon. 219 */ 220 if (data->expected_us > 5) 221 data->last_state_idx = CPUIDLE_DRIVER_STATE_START; 222 223 224 /* find the deepest idle state that satisfies our constraints */ 225 for (i = CPUIDLE_DRIVER_STATE_START; i < dev->state_count; i++) { 226 struct cpuidle_state *s = &dev->states[i]; 227 228 if (s->target_residency > data->predicted_us) 229 break; 230 if (s->exit_latency > latency_req) 231 break; 232 if (s->exit_latency * multiplier > data->predicted_us) 233 break; 234 data->exit_us = s->exit_latency; 235 data->last_state_idx = i; 236 } 237 238 return data->last_state_idx; 239 } 240 241 /** 242 * menu_reflect - records that data structures need update 243 * @dev: the CPU 244 * 245 * NOTE: it's important to be fast here because this operation will add to 246 * the overall exit latency. 247 */ 248 static void menu_reflect(struct cpuidle_device *dev) 249 { 250 struct menu_device *data = &__get_cpu_var(menu_devices); 251 data->needs_update = 1; 252 } 253 254 /** 255 * menu_update - attempts to guess what happened after entry 256 * @dev: the CPU 257 */ 258 static void menu_update(struct cpuidle_device *dev) 259 { 260 struct menu_device *data = &__get_cpu_var(menu_devices); 261 int last_idx = data->last_state_idx; 262 unsigned int last_idle_us = cpuidle_get_last_residency(dev); 263 struct cpuidle_state *target = &dev->states[last_idx]; 264 unsigned int measured_us; 265 u64 new_factor; 266 267 /* 268 * Ugh, this idle state doesn't support residency measurements, so we 269 * are basically lost in the dark. As a compromise, assume we slept 270 * for the whole expected time. 271 */ 272 if (unlikely(!(target->flags & CPUIDLE_FLAG_TIME_VALID))) 273 last_idle_us = data->expected_us; 274 275 276 measured_us = last_idle_us; 277 278 /* 279 * We correct for the exit latency; we are assuming here that the 280 * exit latency happens after the event that we're interested in. 281 */ 282 if (measured_us > data->exit_us) 283 measured_us -= data->exit_us; 284 285 286 /* update our correction ratio */ 287 288 new_factor = data->correction_factor[data->bucket] 289 * (DECAY - 1) / DECAY; 290 291 if (data->expected_us > 0 && data->measured_us < MAX_INTERESTING) 292 new_factor += RESOLUTION * measured_us / data->expected_us; 293 else 294 /* 295 * we were idle so long that we count it as a perfect 296 * prediction 297 */ 298 new_factor += RESOLUTION; 299 300 /* 301 * We don't want 0 as factor; we always want at least 302 * a tiny bit of estimated time. 303 */ 304 if (new_factor == 0) 305 new_factor = 1; 306 307 data->correction_factor[data->bucket] = new_factor; 308 } 309 310 /** 311 * menu_enable_device - scans a CPU's states and does setup 312 * @dev: the CPU 313 */ 314 static int menu_enable_device(struct cpuidle_device *dev) 315 { 316 struct menu_device *data = &per_cpu(menu_devices, dev->cpu); 317 318 memset(data, 0, sizeof(struct menu_device)); 319 320 return 0; 321 } 322 323 static struct cpuidle_governor menu_governor = { 324 .name = "menu", 325 .rating = 20, 326 .enable = menu_enable_device, 327 .select = menu_select, 328 .reflect = menu_reflect, 329 .owner = THIS_MODULE, 330 }; 331 332 /** 333 * init_menu - initializes the governor 334 */ 335 static int __init init_menu(void) 336 { 337 return cpuidle_register_governor(&menu_governor); 338 } 339 340 /** 341 * exit_menu - exits the governor 342 */ 343 static void __exit exit_menu(void) 344 { 345 cpuidle_unregister_governor(&menu_governor); 346 } 347 348 MODULE_LICENSE("GPL"); 349 module_init(init_menu); 350 module_exit(exit_menu); 351