drivers/cpuidle/governors/menu.c

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