drivers/cpuquiet/governors/runnable_threads.c

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