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