drivers/cpuquiet/governors/balanced.c

   1 /*
   2  * Copyright (c) 2012 NVIDIA CORPORATION.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; version 2 of the License.
   7  *
   8  * This program is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  11  * more details.
  12  *
  13  * You should have received a copy of the GNU General Public License along
  14  * with this program; if not, write to the Free Software Foundation, Inc.,
  15  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  16  *
  17  */
  18
  19 #include <linux/kernel.h>
  20 #include <linux/cpuquiet.h>
  21 #include <linux/cpumask.h>
  22 #include <linux/module.h>
  23 #include <linux/cpufreq.h>
  24 #include <linux/pm_qos_params.h>
  25 #include <linux/jiffies.h>
  26 #include <linux/slab.h>
  27 #include <linux/cpu.h>
  28 #include <linux/sched.h>
  29 #include <linux/tick.h>
  30 #include <asm/cputime.h>
  31
  32 #define CPUNAMELEN 8
  33
  34 typedef enum {
  35         CPU_SPEED_BALANCED,
  36         CPU_SPEED_BIASED,
  37         CPU_SPEED_SKEWED,
  38 } CPU_SPEED_BALANCE;
  39
  40 typedef enum {
  41         IDLE,
  42         DOWN,
  43         UP,
  44 } BALANCED_STATE;
  45
  46 struct idle_info {
  47         u64 idle_last;
  48         u64 last_timestamp;
  49         u64 idle_current;
  50         u64 timestamp;
  51 };
  52
  53 static DEFINE_PER_CPU(struct idle_info, idleinfo);
  54 static DEFINE_PER_CPU(unsigned int, cpu_load);
  55
  56 static struct timer_list load_timer;
  57 static bool load_timer_active;
  58 struct balanced_attribute {
  59         struct attribute attr;
  60         ssize_t (*show)(struct balanced_attribute *attr, char *buf);
  61         ssize_t (*store)(struct balanced_attribute *attr, const char *buf,
  62                                 size_t count);
  63         unsigned long *param;
  64 };
  65
  66 #define BALANCED_ATTRIBUTE(_name, _mode) \
  67         static struct balanced_attribute _name ## _attr = {             \
  68                 .attr = {.name = __stringify(_name), .mode = _mode },   \
  69                 .show   = show_attribute,                               \
  70                 .store  = store_attribute,                              \
  71                 .param  = &_name,                                       \
  72 }
  73
  74 /* configurable parameters */
  75 static unsigned long balance_level = 60;
  76 static unsigned long idle_bottom_freq;
  77 static unsigned long idle_top_freq;
  78 static unsigned long up_delay;
  79 static unsigned long down_delay;
  80 static unsigned long last_change_time;
  81 static unsigned long load_sample_rate = 20; // msec
  82 static struct workqueue_struct *balanced_wq;
  83 static struct delayed_work balanced_work;
  84 static BALANCED_STATE balanced_state;
  85 static struct kobject *balanced_kobject;
  86
  87 static void calculate_load_timer(unsigned long data)
  88 {
  89         int i;
  90         u64 idle_time, elapsed_time;
  91
  92         if (!load_timer_active)
  93                 return;
  94
  95         for_each_online_cpu(i) {
  96                 struct idle_info *iinfo = &per_cpu(idleinfo, i);
  97                 unsigned int *load = &per_cpu(cpu_load, i);
  98
  99                 iinfo->idle_last = iinfo->idle_current;
 100                 iinfo->last_timestamp = iinfo->timestamp;
 101                 iinfo->idle_current =
 102                         get_cpu_idle_time_us(i, &iinfo->timestamp);
 103                 elapsed_time = iinfo->timestamp - iinfo->last_timestamp;
 104
 105                 idle_time = iinfo->idle_current - iinfo->idle_last;
 106                 idle_time *= 100;
 107                 do_div(idle_time, elapsed_time);
 108                 *load = 100 - idle_time;
 109         }
 110         mod_timer(&load_timer, jiffies + msecs_to_jiffies(load_sample_rate));
 111 }
 112
 113 static void start_load_timer(void)
 114 {
 115         int i;
 116
 117         if (load_timer_active)
 118                 return;
 119
 120         load_timer_active = true;
 121
 122         for_each_online_cpu(i) {
 123                 struct idle_info *iinfo = &per_cpu(idleinfo, i);
 124
 125                 iinfo->idle_current =
 126                         get_cpu_idle_time_us(i, &iinfo->timestamp);
 127         }
 128         mod_timer(&load_timer, jiffies + msecs_to_jiffies(100));
 129 }
 130
 131 static void stop_load_timer(void)
 132 {
 133         if (!load_timer_active)
 134                 return;
 135
 136         load_timer_active = false;
 137         del_timer(&load_timer);
 138 }
 139
 140 static unsigned int get_slowest_cpu_n(void)
 141 {
 142         unsigned int cpu = nr_cpu_ids;
 143         unsigned long minload = ULONG_MAX;
 144         int i;
 145
 146         for_each_online_cpu(i) {
 147                 unsigned int *load = &per_cpu(cpu_load, i);
 148
 149                 if ((i > 0) && (minload > *load)) {
 150                         cpu = i;
 151                         minload = *load;
 152                 }
 153         }
 154
 155         return cpu;
 156 }
 157
 158 static unsigned int cpu_highest_speed(void)
 159 {
 160         unsigned int maxload = 0;
 161         int i;
 162
 163         for_each_online_cpu(i) {
 164                 unsigned int *load = &per_cpu(cpu_load, i);
 165
 166                 maxload = max(maxload, *load);
 167         }
 168
 169         return maxload;
 170 }
 171
 172 static unsigned int count_slow_cpus(unsigned int limit)
 173 {
 174         unsigned int cnt = 0;
 175         int i;
 176
 177         for_each_online_cpu(i) {
 178                 unsigned int *load = &per_cpu(cpu_load, i);
 179
 180                 if (*load <= limit)
 181                         cnt++;
 182         }
 183
 184         return cnt;
 185 }
 186
 187 #define NR_FSHIFT       2
 188 static unsigned int nr_run_thresholds[] = {
 189 /*      1,  2,  3,  4 - on-line cpus target */
 190         5,  9, 10, UINT_MAX /* avg run threads * 4 (e.g., 9 = 2.25 threads) */
 191 };
 192 static unsigned int nr_run_hysteresis = 2;      /* 0.5 thread */
 193 static unsigned int nr_run_last;
 194
 195 static CPU_SPEED_BALANCE balanced_speed_balance(void)
 196 {
 197         unsigned long highest_speed = cpu_highest_speed();
 198         unsigned long balanced_speed = highest_speed * balance_level / 100;
 199         unsigned long skewed_speed = balanced_speed / 2;
 200         unsigned int nr_cpus = num_online_cpus();
 201         unsigned int max_cpus = pm_qos_request(PM_QOS_MAX_ONLINE_CPUS) ? : 4;
 202         unsigned int avg_nr_run = avg_nr_running();
 203         unsigned int nr_run;
 204
 205         /* balanced: freq targets for all CPUs are above 50% of highest speed
 206            biased: freq target for at least one CPU is below 50% threshold
 207            skewed: freq targets for at least 2 CPUs are below 25% threshold */
 208         for (nr_run = 1; nr_run < ARRAY_SIZE(nr_run_thresholds); nr_run++) {
 209                 unsigned int nr_threshold = nr_run_thresholds[nr_run - 1];
 210                 if (nr_run_last <= nr_run)
 211                         nr_threshold += nr_run_hysteresis;
 212                 if (avg_nr_run <= (nr_threshold << (FSHIFT - NR_FSHIFT)))
 213                         break;
 214         }
 215         nr_run_last = nr_run;
 216
 217         if (count_slow_cpus(skewed_speed) >= 2 || nr_cpus > max_cpus ||
 218                 nr_run < nr_cpus)
 219                 return CPU_SPEED_SKEWED;
 220
 221         if (count_slow_cpus(balanced_speed) >= 1 || nr_cpus == max_cpus ||
 222                 nr_run <= nr_cpus)
 223                 return CPU_SPEED_BIASED;
 224
 225         return CPU_SPEED_BALANCED;
 226 }
 227
 228 static void balanced_work_func(struct work_struct *work)
 229 {
 230         bool up = false;
 231         unsigned int cpu = nr_cpu_ids;
 232         unsigned long now = jiffies;
 233
 234         CPU_SPEED_BALANCE balance;
 235
 236         switch (balanced_state) {
 237         case IDLE:
 238                 break;
 239         case DOWN:
 240                 cpu = get_slowest_cpu_n();
 241                 if (cpu < nr_cpu_ids) {
 242                         up = false;
 243                         queue_delayed_work(balanced_wq,
 244                                                  &balanced_work, up_delay);
 245                 } else
 246                         stop_load_timer();
 247                 break;
 248         case UP:
 249                 balance = balanced_speed_balance();
 250                 switch (balance) {
 251
 252                 /* cpu speed is up and balanced - one more on-line */
 253                 case CPU_SPEED_BALANCED:
 254                         cpu = cpumask_next_zero(0, cpu_online_mask);
 255                         if (cpu < nr_cpu_ids)
 256                                 up = true;
 257                         break;
 258                 /* cpu speed is up, but skewed - remove one core */
 259                 case CPU_SPEED_SKEWED:
 260                         cpu = get_slowest_cpu_n();
 261                         if (cpu < nr_cpu_ids)
 262                                 up = false;
 263                         break;
 264                 /* cpu speed is up, but under-utilized - do nothing */
 265                 case CPU_SPEED_BIASED:
 266                 default:
 267                         break;
 268                 }
 269                 queue_delayed_work(
 270                         balanced_wq, &balanced_work, up_delay);
 271                 break;
 272         default:
 273                 pr_err("%s: invalid cpuquiet balanced governor state %d\n",
 274                        __func__, balanced_state);
 275         }
 276
 277         if (!up && ((now - last_change_time) < down_delay))
 278                 cpu = nr_cpu_ids;
 279
 280         if (cpu < nr_cpu_ids) {
 281                 last_change_time = now;
 282                 if (up)
 283                         cpuquiet_wake_cpu(cpu);
 284                 else
 285                         cpuquiet_quiesence_cpu(cpu);
 286         }
 287 }
 288
 289 static int balanced_cpufreq_transition(struct notifier_block *nb,
 290         unsigned long state, void *data)
 291 {
 292         struct cpufreq_freqs *freqs = data;
 293         unsigned long cpu_freq;
 294
 295         if (state == CPUFREQ_POSTCHANGE || state == CPUFREQ_RESUMECHANGE) {
 296                 cpu_freq = freqs->new;
 297
 298                 switch (balanced_state) {
 299                 case IDLE:
 300                         if (cpu_freq > idle_top_freq) {
 301                                 balanced_state = UP;
 302                                 queue_delayed_work(
 303                                         balanced_wq, &balanced_work, up_delay);
 304                                 start_load_timer();
 305                         } else if (cpu_freq <= idle_bottom_freq) {
 306                                 balanced_state = DOWN;
 307                                 queue_delayed_work(
 308                                         balanced_wq, &balanced_work,
 309                                         down_delay);
 310                                 start_load_timer();
 311                         }
 312                         break;
 313                 case DOWN:
 314                         if (cpu_freq > idle_top_freq) {
 315                                 balanced_state = UP;
 316                                 queue_delayed_work(
 317                                         balanced_wq, &balanced_work, up_delay);
 318                                 start_load_timer();
 319                         }
 320                         break;
 321                 case UP:
 322                         if (cpu_freq <= idle_bottom_freq) {
 323                                 balanced_state = DOWN;
 324                                 queue_delayed_work(balanced_wq,
 325                                         &balanced_work, up_delay);
 326                                 start_load_timer();
 327                         }
 328                         break;
 329                 default:
 330                         pr_err("%s: invalid cpuquiet balanced governor "
 331                                 "state %d\n", __func__, balanced_state);
 332                 }
 333         }
 334
 335         return NOTIFY_OK;
 336 }
 337
 338 static struct notifier_block balanced_cpufreq_nb = {
 339         .notifier_call = balanced_cpufreq_transition,
 340 };
 341
 342 static ssize_t show_attribute(struct balanced_attribute *battr, char *buf)
 343 {
 344         return sprintf(buf, "%lu\n", *(battr->param));
 345 }
 346
 347 static ssize_t store_attribute(struct balanced_attribute *battr,
 348                                         const char *buf, size_t count)
 349 {
 350         int err;
 351         unsigned long val;
 352
 353         err = strict_strtoul(buf, 0, &val);
 354         if (err < 0)
 355                 return err;
 356
 357         *(battr->param) = val;
 358
 359         return count;
 360 }
 361
 362 static ssize_t balanced_sysfs_store(struct kobject *kobj,
 363                         struct attribute *attr, const char *buf, size_t count)
 364 {
 365         struct balanced_attribute *battr =
 366                  container_of(attr, struct balanced_attribute, attr);
 367
 368         if (battr->store)
 369                 return battr->store(battr, buf, count);
 370
 371         return -EINVAL;
 372 }
 373
 374 static ssize_t balanced_sysfs_show(struct kobject *kobj,
 375                         struct attribute *attr, char *buf)
 376 {
 377         struct balanced_attribute *battr =
 378                  container_of(attr, struct balanced_attribute, attr);
 379
 380         return battr->show(battr, buf);
 381 }
 382
 383 BALANCED_ATTRIBUTE(balance_level, 0644);
 384 BALANCED_ATTRIBUTE(idle_bottom_freq, 0644);
 385 BALANCED_ATTRIBUTE(idle_top_freq, 0644);
 386 BALANCED_ATTRIBUTE(up_delay, 0644);
 387 BALANCED_ATTRIBUTE(down_delay, 0644);
 388 BALANCED_ATTRIBUTE(load_sample_rate, 0644);
 389
 390 static struct attribute *balanced_attributes[] = {
 391         &balance_level_attr.attr,
 392         &idle_bottom_freq_attr.attr,
 393         &idle_top_freq_attr.attr,
 394         &up_delay_attr.attr,
 395         &down_delay_attr.attr,
 396         NULL,
 397 };
 398
 399 static const struct sysfs_ops balanced_sysfs_ops = {
 400         .show = balanced_sysfs_show,
 401         .store = balanced_sysfs_store,
 402 };
 403
 404 static struct kobj_type ktype_balanced = {
 405         .sysfs_ops = &balanced_sysfs_ops,
 406         .default_attrs = balanced_attributes,
 407 };
 408
 409 static int balanced_sysfs(void)
 410 {
 411         int err;
 412
 413         balanced_kobject = kzalloc(sizeof(*balanced_kobject),
 414                                 GFP_KERNEL);
 415
 416         if (!balanced_kobject)
 417                 return -ENOMEM;
 418
 419         err = cpuquiet_kobject_init(balanced_kobject, &ktype_balanced,
 420                                 "balanced");
 421
 422         if (err)
 423                 kfree(balanced_kobject);
 424
 425         return err;
 426 }
 427
 428 static void balanced_stop(void)
 429 {
 430
 431         /*
 432            first unregister the notifiers. This ensures the governor state
 433            can't be modified by a cpufreq transition
 434         */
 435         cpufreq_unregister_notifier(&balanced_cpufreq_nb,
 436                 CPUFREQ_TRANSITION_NOTIFIER);
 437
 438         /* now we can force the governor to be idle */
 439         balanced_state = IDLE;
 440         cancel_delayed_work_sync(&balanced_work);
 441         destroy_workqueue(balanced_wq);
 442         del_timer(&load_timer);
 443
 444         kobject_put(balanced_kobject);
 445 }
 446
 447 static int balanced_start(void)
 448 {
 449         int err, count;
 450         struct cpufreq_frequency_table *table;
 451         struct cpufreq_freqs initial_freq;
 452
 453         err = balanced_sysfs();
 454         if (err)
 455                 return err;
 456
 457         balanced_wq = alloc_workqueue("cpuquiet-balanced",
 458                         WQ_UNBOUND | WQ_RESCUER | WQ_FREEZABLE, 1);
 459         if (!balanced_wq)
 460                 return -ENOMEM;
 461
 462         INIT_DELAYED_WORK(&balanced_work, balanced_work_func);
 463
 464         up_delay = msecs_to_jiffies(100);
 465         down_delay = msecs_to_jiffies(500);
 466
 467         table = cpufreq_frequency_get_table(0);
 468         for (count = 0; table[count].frequency != CPUFREQ_TABLE_END; count++)
 469                 ;
 470
 471         idle_top_freq = table[(count / 2) - 1].frequency;
 472         idle_bottom_freq = table[(count / 2) - 2].frequency;
 473
 474         cpufreq_register_notifier(&balanced_cpufreq_nb,
 475                 CPUFREQ_TRANSITION_NOTIFIER);
 476
 477         init_timer(&load_timer);
 478         load_timer.function = calculate_load_timer;
 479
 480         /*FIXME: Kick start the state machine by faking a freq notification*/
 481         initial_freq.new = cpufreq_get(0);
 482         if (initial_freq.new != 0)
 483                 balanced_cpufreq_transition(NULL, CPUFREQ_RESUMECHANGE,
 484                                                 &initial_freq);
 485         return 0;
 486 }
 487
 488 struct cpuquiet_governor balanced_governor = {
 489         .name           = "balanced",
 490         .start          = balanced_start,
 491         .stop           = balanced_stop,
 492         .owner          = THIS_MODULE,
 493 };
 494
 495 static int __init init_balanced(void)
 496 {
 497         return cpuquiet_register_governor(&balanced_governor);
 498 }
 499
 500 static void __exit exit_balanced(void)
 501 {
 502         cpuquiet_unregister_governor(&balanced_governor);
 503 }
 504
 505 MODULE_LICENSE("GPL");
 506 module_init(init_balanced);
 507 module_exit(exit_balanced);
 508