drivers/cpuquiet/governors/runnable_threads.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/pm_qos.h>
  24 #include <linux/jiffies.h>
  25 #include <linux/slab.h>
  26 #include <linux/cpu.h>
  27 #include <linux/sched.h>
  28
  29 typedef enum {
  30         DISABLED,
  31         IDLE,
  32         DOWN,
  33         UP,
  34 } RUNNABLES_STATE;
  35
  36 static struct work_struct runnables_work;
  37 static struct kobject *runnables_kobject;
  38 static struct timer_list runnables_timer;
  39
  40 static RUNNABLES_STATE runnables_state;
  41 /* configurable parameters */
  42 static unsigned int sample_rate = 20;           /* msec */
  43
  44 static RUNNABLES_STATE runnables_state;
  45
  46 #define NR_FSHIFT_EXP   3
  47 #define NR_FSHIFT       (1 << NR_FSHIFT_EXP)
  48 /* avg run threads * 8 (e.g., 11 = 1.375 threads) */
  49 static unsigned int default_thresholds[] = {
  50         10, 18, 20, UINT_MAX
  51 };
  52
  53 static unsigned int nr_run_last;
  54 static unsigned int nr_run_hysteresis = 2;              /* 1 / 2 thread */
  55 static unsigned int default_threshold_level = 4;        /* 1 / 4 thread */
  56 static unsigned int nr_run_thresholds[NR_CPUS];
  57
  58 DEFINE_MUTEX(runnables_work_lock);
  59
  60 struct runnables_avg_sample {
  61         u64 previous_integral;
  62         unsigned int avg;
  63         bool integral_sampled;
  64         u64 prev_timestamp;
  65 };
  66
  67 static DEFINE_PER_CPU(struct runnables_avg_sample, avg_nr_sample);
  68
  69 /* EXP = alpha in the exponential moving average.
  70  * Alpha = e ^ (-sample_rate / window_size) * FIXED_1
  71  * Calculated for sample_rate of 20ms, window size of 100ms
  72  */
  73 #define EXP    1677
  74
  75 static unsigned int get_avg_nr_runnables(void)
  76 {
  77         unsigned int i, sum = 0;
  78         static unsigned int avg;
  79         struct runnables_avg_sample *sample;
  80         u64 integral, old_integral, delta_integral, delta_time, cur_time;
  81
  82         for_each_online_cpu(i) {
  83                 sample = &per_cpu(avg_nr_sample, i);
  84                 integral = nr_running_integral(i);
  85                 old_integral = sample->previous_integral;
  86                 sample->previous_integral = integral;
  87                 cur_time = ktime_to_ns(ktime_get());
  88                 delta_time = cur_time - sample->prev_timestamp;
  89                 sample->prev_timestamp = cur_time;
  90
  91                 if (!sample->integral_sampled) {
  92                         sample->integral_sampled = true;
  93                         /* First sample to initialize prev_integral, skip
  94                          * avg calculation
  95                          */
  96                         continue;
  97                 }
  98
  99                 if (integral < old_integral) {
 100                         /* Overflow */
 101                         delta_integral = (ULLONG_MAX - old_integral) + integral;
 102                 } else {
 103                         delta_integral = integral - old_integral;
 104                 }
 105
 106                 /* Calculate average for the previous sample window */
 107                 do_div(delta_integral, delta_time);
 108                 sample->avg = delta_integral;
 109                 sum += sample->avg;
 110         }
 111
 112         /* Exponential moving average
 113          * Avgn = Avgn-1 * alpha + new_avg * (1 - alpha)
 114          */
 115         avg *= EXP;
 116         avg += sum * (FIXED_1 - EXP);
 117         avg >>= FSHIFT;
 118
 119         return avg;
 120 }
 121
 122 static void update_runnables_state(unsigned int nr_run)
 123 {
 124         unsigned int nr_cpus = num_online_cpus();
 125         int max_cpus = pm_qos_request(PM_QOS_MAX_ONLINE_CPUS) ? : 4;
 126         int min_cpus = pm_qos_request(PM_QOS_MIN_ONLINE_CPUS);
 127
 128         if ((nr_cpus > max_cpus || nr_run < nr_cpus) && nr_cpus >= min_cpus) {
 129                 runnables_state = DOWN;
 130         } else if (nr_cpus < min_cpus || nr_run > nr_cpus) {
 131                 runnables_state =  UP;
 132         } else {
 133                 runnables_state = IDLE;
 134         }
 135 }
 136
 137 static void runnables_avg_sampler(unsigned long data)
 138 {
 139         unsigned int nr_run, avg_nr_run;
 140
 141         if (runnables_state == DISABLED)
 142                 return;
 143
 144         avg_nr_run = get_avg_nr_runnables();
 145         mod_timer(&runnables_timer, jiffies + msecs_to_jiffies(sample_rate));
 146
 147         for (nr_run = 1; nr_run < ARRAY_SIZE(nr_run_thresholds); nr_run++) {
 148                 unsigned int nr_threshold = nr_run_thresholds[nr_run - 1];
 149                 if (nr_run_last <= nr_run)
 150                         nr_threshold += NR_FSHIFT / nr_run_hysteresis;
 151                 if (avg_nr_run <= (nr_threshold << (FSHIFT - NR_FSHIFT_EXP)))
 152                         break;
 153         }
 154
 155         nr_run_last = nr_run;
 156         update_runnables_state(nr_run);
 157
 158         if (runnables_state != DISABLED && runnables_state != IDLE)
 159                 schedule_work(&runnables_work);
 160 }
 161
 162 static unsigned int get_lightest_loaded_cpu_n(void)
 163 {
 164         unsigned long min_avg_runnables = ULONG_MAX;
 165         unsigned int cpu = nr_cpu_ids;
 166         int i;
 167
 168         for_each_online_cpu(i) {
 169                 struct runnables_avg_sample *s = &per_cpu(avg_nr_sample, i);
 170                 unsigned int nr_runnables = s->avg;
 171                 if (i > 0 && min_avg_runnables > nr_runnables) {
 172                         cpu = i;
 173                         min_avg_runnables = nr_runnables;
 174                 }
 175         }
 176
 177         return cpu;
 178 }
 179
 180 static void runnables_work_func(struct work_struct *work)
 181 {
 182         bool up = false;
 183         unsigned int cpu = nr_cpu_ids;
 184
 185         mutex_lock(&runnables_work_lock);
 186
 187         /* Update state to avoid duplicate operations */
 188         update_runnables_state(nr_run_last);
 189
 190         switch (runnables_state) {
 191         case DISABLED:
 192         case IDLE:
 193                 break;
 194         case UP:
 195                 cpu = cpumask_next_zero(0, cpu_online_mask);
 196                 up = true;
 197                 break;
 198         case DOWN:
 199                 cpu = get_lightest_loaded_cpu_n();
 200                 break;
 201         default:
 202                 pr_err("%s: invalid cpuquiet runnable governor state %d\n",
 203                         __func__, runnables_state);
 204                 break;
 205         }
 206
 207         if (cpu < nr_cpu_ids) {
 208                 if (up)
 209                         cpuquiet_wake_cpu(cpu);
 210                 else
 211                         cpuquiet_quiesence_cpu(cpu);
 212         }
 213
 214         mutex_unlock(&runnables_work_lock);
 215 }
 216
 217 CPQ_BASIC_ATTRIBUTE(sample_rate, 0644, uint);
 218 CPQ_BASIC_ATTRIBUTE(nr_run_hysteresis, 0644, uint);
 219
 220 static struct attribute *runnables_attributes[] = {
 221         &sample_rate_attr.attr,
 222         &nr_run_hysteresis_attr.attr,
 223         NULL,
 224 };
 225
 226 static const struct sysfs_ops runnables_sysfs_ops = {
 227         .show = cpuquiet_auto_sysfs_show,
 228         .store = cpuquiet_auto_sysfs_store,
 229 };
 230
 231 static struct kobj_type ktype_runnables = {
 232         .sysfs_ops = &runnables_sysfs_ops,
 233         .default_attrs = runnables_attributes,
 234 };
 235
 236 static int runnables_sysfs(void)
 237 {
 238         int err;
 239
 240         runnables_kobject = kzalloc(sizeof(*runnables_kobject),
 241                                 GFP_KERNEL);
 242
 243         if (!runnables_kobject)
 244                 return -ENOMEM;
 245
 246         err = cpuquiet_kobject_init(runnables_kobject, &ktype_runnables,
 247                                 "runnable_threads");
 248
 249         if (err)
 250                 kfree(runnables_kobject);
 251
 252         return err;
 253 }
 254
 255 static void runnables_device_busy(void)
 256 {
 257         if (runnables_state != DISABLED) {
 258                 runnables_state = DISABLED;
 259                 cancel_work_sync(&runnables_work);
 260         }
 261 }
 262
 263 static void runnables_device_free(void)
 264 {
 265         if (runnables_state == DISABLED) {
 266                 runnables_state = IDLE;
 267                 mod_timer(&runnables_timer, jiffies + 1);
 268         }
 269 }
 270
 271 static void runnables_stop(void)
 272 {
 273         runnables_state = DISABLED;
 274         cancel_work_sync(&runnables_work);
 275         kobject_put(runnables_kobject);
 276 }
 277
 278 static int runnables_start(void)
 279 {
 280         int err, i;
 281
 282         err = runnables_sysfs();
 283         if (err)
 284                 return err;
 285
 286         INIT_WORK(&runnables_work, runnables_work_func);
 287
 288         init_timer(&runnables_timer);
 289         runnables_timer.function = runnables_avg_sampler;
 290
 291         for(i = 0; i < ARRAY_SIZE(nr_run_thresholds); ++i) {
 292                 if (i < ARRAY_SIZE(default_thresholds))
 293                         nr_run_thresholds[i] = default_thresholds[i];
 294                 else if (i == (ARRAY_SIZE(nr_run_thresholds) - 1))
 295                         nr_run_thresholds[i] = UINT_MAX;
 296                 else
 297                         nr_run_thresholds[i] = i + 1 +
 298                                 NR_FSHIFT / default_threshold_level;
 299         }
 300
 301         runnables_state = IDLE;
 302         runnables_avg_sampler(0);
 303
 304         return 0;
 305 }
 306
 307 struct cpuquiet_governor runnables_governor = {
 308         .name                     = "runnable",
 309         .start                    = runnables_start,
 310         .device_free_notification = runnables_device_free,
 311         .device_busy_notification = runnables_device_busy,
 312         .stop                     = runnables_stop,
 313         .owner                    = THIS_MODULE,
 314 };
 315
 316 static int __init init_runnables(void)
 317 {
 318         return cpuquiet_register_governor(&runnables_governor);
 319 }
 320
 321 static void __exit exit_runnables(void)
 322 {
 323         cpuquiet_unregister_governor(&runnables_governor);
 324 }
 325
 326 MODULE_LICENSE("GPL");
 327 #ifdef CONFIG_CPUQUIET_DEFAULT_GOV_RUNNABLE
 328 fs_initcall(init_runnables);
 329 #else
 330 module_init(init_runnables);
 331 #endif
 332 module_exit(exit_runnables);