FIXUP: sched/tune: fix payoff calculation for boost region
[firefly-linux-kernel-4.4.55.git] / kernel / sched / tune.c
1 #include <linux/cgroup.h>
2 #include <linux/err.h>
3 #include <linux/kernel.h>
4 #include <linux/percpu.h>
5 #include <linux/printk.h>
6 #include <linux/rcupdate.h>
7 #include <linux/slab.h>
8
9 #include <trace/events/sched.h>
10
11 #include "sched.h"
12 #include "tune.h"
13
14 unsigned int sysctl_sched_cfs_boost __read_mostly;
15
16 extern struct target_nrg schedtune_target_nrg;
17
18 /* Performance Boost region (B) threshold params */
19 static int perf_boost_idx;
20
21 /* Performance Constraint region (C) threshold params */
22 static int perf_constrain_idx;
23
24 /**
25  * Performance-Energy (P-E) Space thresholds constants
26  */
27 struct threshold_params {
28         int nrg_gain;
29         int cap_gain;
30 };
31
32 /*
33  * System specific P-E space thresholds constants
34  */
35 static struct threshold_params
36 threshold_gains[] = {
37         { 0, 4 }, /* >=  0% */
38         { 0, 4 }, /* >= 10% */
39         { 1, 4 }, /* >= 20% */
40         { 2, 4 }, /* >= 30% */
41         { 3, 4 }, /* >= 40% */
42         { 4, 3 }, /* >= 50% */
43         { 4, 2 }, /* >= 60% */
44         { 4, 1 }, /* >= 70% */
45         { 4, 0 }, /* >= 80% */
46         { 4, 0 }  /* >= 90% */
47 };
48
49 static int
50 __schedtune_accept_deltas(int nrg_delta, int cap_delta,
51                           int perf_boost_idx, int perf_constrain_idx)
52 {
53         int payoff = -INT_MAX;
54         int gain_idx = -1;
55
56         /* Performance Boost (B) region */
57         if (nrg_delta >= 0 && cap_delta > 0)
58                 gain_idx = perf_boost_idx;
59         /* Performance Constraint (C) region */
60         else if (nrg_delta < 0 && cap_delta <= 0)
61                 gain_idx = perf_constrain_idx;
62
63         /* Default: reject schedule candidate */
64         if (gain_idx == -1)
65                 return payoff;
66
67         /*
68          * Evaluate "Performance Boost" vs "Energy Increase"
69          *
70          * - Performance Boost (B) region
71          *
72          *   Condition: nrg_delta > 0 && cap_delta > 0
73          *   Payoff criteria:
74          *     cap_gain / nrg_gain  < cap_delta / nrg_delta =
75          *     cap_gain * nrg_delta < cap_delta * nrg_gain
76          *   Note that since both nrg_gain and nrg_delta are positive, the
77          *   inequality does not change. Thus:
78          *
79          *     payoff = (cap_delta * nrg_gain) - (cap_gain * nrg_delta)
80          *
81          * - Performance Constraint (C) region
82          *
83          *   Condition: nrg_delta < 0 && cap_delta < 0
84          *   payoff criteria:
85          *     cap_gain / nrg_gain  > cap_delta / nrg_delta =
86          *     cap_gain * nrg_delta < cap_delta * nrg_gain
87          *   Note that since nrg_gain > 0 while nrg_delta < 0, the
88          *   inequality change. Thus:
89          *
90          *     payoff = (cap_delta * nrg_gain) - (cap_gain * nrg_delta)
91          *
92          * This means that, in case of same positive defined {cap,nrg}_gain
93          * for both the B and C regions, we can use the same payoff formula
94          * where a positive value represents the accept condition.
95          */
96         payoff  = cap_delta * threshold_gains[gain_idx].nrg_gain;
97         payoff -= nrg_delta * threshold_gains[gain_idx].cap_gain;
98
99         return payoff;
100 }
101
102 #ifdef CONFIG_CGROUP_SCHEDTUNE
103
104 /*
105  * EAS scheduler tunables for task groups.
106  */
107
108 /* SchdTune tunables for a group of tasks */
109 struct schedtune {
110         /* SchedTune CGroup subsystem */
111         struct cgroup_subsys_state css;
112
113         /* Boost group allocated ID */
114         int idx;
115
116         /* Boost value for tasks on that SchedTune CGroup */
117         int boost;
118
119         /* Performance Boost (B) region threshold params */
120         int perf_boost_idx;
121
122         /* Performance Constraint (C) region threshold params */
123         int perf_constrain_idx;
124 };
125
126 static inline struct schedtune *css_st(struct cgroup_subsys_state *css)
127 {
128         return css ? container_of(css, struct schedtune, css) : NULL;
129 }
130
131 static inline struct schedtune *task_schedtune(struct task_struct *tsk)
132 {
133         return css_st(task_css(tsk, schedtune_cgrp_id));
134 }
135
136 static inline struct schedtune *parent_st(struct schedtune *st)
137 {
138         return css_st(st->css.parent);
139 }
140
141 /*
142  * SchedTune root control group
143  * The root control group is used to defined a system-wide boosting tuning,
144  * which is applied to all tasks in the system.
145  * Task specific boost tuning could be specified by creating and
146  * configuring a child control group under the root one.
147  * By default, system-wide boosting is disabled, i.e. no boosting is applied
148  * to tasks which are not into a child control group.
149  */
150 static struct schedtune
151 root_schedtune = {
152         .boost  = 0,
153         .perf_boost_idx = 0,
154         .perf_constrain_idx = 0,
155 };
156
157 int
158 schedtune_accept_deltas(int nrg_delta, int cap_delta,
159                         struct task_struct *task)
160 {
161         struct schedtune *ct;
162         int perf_boost_idx;
163         int perf_constrain_idx;
164
165         /* Optimal (O) region */
166         if (nrg_delta < 0 && cap_delta > 0) {
167                 trace_sched_tune_filter(nrg_delta, cap_delta, 0, 0, 1, 0);
168                 return INT_MAX;
169         }
170
171         /* Suboptimal (S) region */
172         if (nrg_delta > 0 && cap_delta < 0) {
173                 trace_sched_tune_filter(nrg_delta, cap_delta, 0, 0, -1, 5);
174                 return -INT_MAX;
175         }
176
177         /* Get task specific perf Boost/Constraints indexes */
178         rcu_read_lock();
179         ct = task_schedtune(task);
180         perf_boost_idx = ct->perf_boost_idx;
181         perf_constrain_idx = ct->perf_constrain_idx;
182         rcu_read_unlock();
183
184         return __schedtune_accept_deltas(nrg_delta, cap_delta,
185                         perf_boost_idx, perf_constrain_idx);
186 }
187
188 /*
189  * Maximum number of boost groups to support
190  * When per-task boosting is used we still allow only limited number of
191  * boost groups for two main reasons:
192  * 1. on a real system we usually have only few classes of workloads which
193  *    make sense to boost with different values (e.g. background vs foreground
194  *    tasks, interactive vs low-priority tasks)
195  * 2. a limited number allows for a simpler and more memory/time efficient
196  *    implementation especially for the computation of the per-CPU boost
197  *    value
198  */
199 #define BOOSTGROUPS_COUNT 4
200
201 /* Array of configured boostgroups */
202 static struct schedtune *allocated_group[BOOSTGROUPS_COUNT] = {
203         &root_schedtune,
204         NULL,
205 };
206
207 /* SchedTune boost groups
208  * Keep track of all the boost groups which impact on CPU, for example when a
209  * CPU has two RUNNABLE tasks belonging to two different boost groups and thus
210  * likely with different boost values.
211  * Since on each system we expect only a limited number of boost groups, here
212  * we use a simple array to keep track of the metrics required to compute the
213  * maximum per-CPU boosting value.
214  */
215 struct boost_groups {
216         /* Maximum boost value for all RUNNABLE tasks on a CPU */
217         bool idle;
218         int boost_max;
219         struct {
220                 /* The boost for tasks on that boost group */
221                 int boost;
222                 /* Count of RUNNABLE tasks on that boost group */
223                 unsigned tasks;
224         } group[BOOSTGROUPS_COUNT];
225 };
226
227 /* Boost groups affecting each CPU in the system */
228 DEFINE_PER_CPU(struct boost_groups, cpu_boost_groups);
229
230 static void
231 schedtune_cpu_update(int cpu)
232 {
233         struct boost_groups *bg;
234         int boost_max;
235         int idx;
236
237         bg = &per_cpu(cpu_boost_groups, cpu);
238
239         /* The root boost group is always active */
240         boost_max = bg->group[0].boost;
241         for (idx = 1; idx < BOOSTGROUPS_COUNT; ++idx) {
242                 /*
243                  * A boost group affects a CPU only if it has
244                  * RUNNABLE tasks on that CPU
245                  */
246                 if (bg->group[idx].tasks == 0)
247                         continue;
248
249                 boost_max = max(boost_max, bg->group[idx].boost);
250         }
251         /* Ensures boost_max is non-negative when all cgroup boost values
252          * are neagtive. Avoids under-accounting of cpu capacity which may cause
253          * task stacking and frequency spikes.*/
254         boost_max = max(boost_max, 0);
255         bg->boost_max = boost_max;
256 }
257
258 static int
259 schedtune_boostgroup_update(int idx, int boost)
260 {
261         struct boost_groups *bg;
262         int cur_boost_max;
263         int old_boost;
264         int cpu;
265
266         /* Update per CPU boost groups */
267         for_each_possible_cpu(cpu) {
268                 bg = &per_cpu(cpu_boost_groups, cpu);
269
270                 /*
271                  * Keep track of current boost values to compute the per CPU
272                  * maximum only when it has been affected by the new value of
273                  * the updated boost group
274                  */
275                 cur_boost_max = bg->boost_max;
276                 old_boost = bg->group[idx].boost;
277
278                 /* Update the boost value of this boost group */
279                 bg->group[idx].boost = boost;
280
281                 /* Check if this update increase current max */
282                 if (boost > cur_boost_max && bg->group[idx].tasks) {
283                         bg->boost_max = boost;
284                         trace_sched_tune_boostgroup_update(cpu, 1, bg->boost_max);
285                         continue;
286                 }
287
288                 /* Check if this update has decreased current max */
289                 if (cur_boost_max == old_boost && old_boost > boost) {
290                         schedtune_cpu_update(cpu);
291                         trace_sched_tune_boostgroup_update(cpu, -1, bg->boost_max);
292                         continue;
293                 }
294
295                 trace_sched_tune_boostgroup_update(cpu, 0, bg->boost_max);
296         }
297
298         return 0;
299 }
300
301 static inline void
302 schedtune_tasks_update(struct task_struct *p, int cpu, int idx, int task_count)
303 {
304         struct boost_groups *bg;
305         int tasks;
306
307         bg = &per_cpu(cpu_boost_groups, cpu);
308
309         /* Update boosted tasks count while avoiding to make it negative */
310         if (task_count < 0 && bg->group[idx].tasks <= -task_count)
311                 bg->group[idx].tasks = 0;
312         else
313                 bg->group[idx].tasks += task_count;
314
315         /* Boost group activation or deactivation on that RQ */
316         tasks = bg->group[idx].tasks;
317         if (tasks == 1 || tasks == 0)
318                 schedtune_cpu_update(cpu);
319
320         trace_sched_tune_tasks_update(p, cpu, tasks, idx,
321                         bg->group[idx].boost, bg->boost_max);
322
323 }
324
325 /*
326  * NOTE: This function must be called while holding the lock on the CPU RQ
327  */
328 void schedtune_enqueue_task(struct task_struct *p, int cpu)
329 {
330         struct schedtune *st;
331         int idx;
332
333         /*
334          * When a task is marked PF_EXITING by do_exit() it's going to be
335          * dequeued and enqueued multiple times in the exit path.
336          * Thus we avoid any further update, since we do not want to change
337          * CPU boosting while the task is exiting.
338          */
339         if (p->flags & PF_EXITING)
340                 return;
341
342         /* Get task boost group */
343         rcu_read_lock();
344         st = task_schedtune(p);
345         idx = st->idx;
346         rcu_read_unlock();
347
348         schedtune_tasks_update(p, cpu, idx, 1);
349 }
350
351 /*
352  * NOTE: This function must be called while holding the lock on the CPU RQ
353  */
354 void schedtune_dequeue_task(struct task_struct *p, int cpu)
355 {
356         struct schedtune *st;
357         int idx;
358
359         /*
360          * When a task is marked PF_EXITING by do_exit() it's going to be
361          * dequeued and enqueued multiple times in the exit path.
362          * Thus we avoid any further update, since we do not want to change
363          * CPU boosting while the task is exiting.
364          * The last dequeue will be done by cgroup exit() callback.
365          */
366         if (p->flags & PF_EXITING)
367                 return;
368
369         /* Get task boost group */
370         rcu_read_lock();
371         st = task_schedtune(p);
372         idx = st->idx;
373         rcu_read_unlock();
374
375         schedtune_tasks_update(p, cpu, idx, -1);
376 }
377
378 int schedtune_cpu_boost(int cpu)
379 {
380         struct boost_groups *bg;
381
382         bg = &per_cpu(cpu_boost_groups, cpu);
383         return bg->boost_max;
384 }
385
386 int schedtune_task_boost(struct task_struct *p)
387 {
388         struct schedtune *st;
389         int task_boost;
390
391         /* Get task boost value */
392         rcu_read_lock();
393         st = task_schedtune(p);
394         task_boost = st->boost;
395         rcu_read_unlock();
396
397         return task_boost;
398 }
399
400 static s64
401 boost_read(struct cgroup_subsys_state *css, struct cftype *cft)
402 {
403         struct schedtune *st = css_st(css);
404
405         return st->boost;
406 }
407
408 static int
409 boost_write(struct cgroup_subsys_state *css, struct cftype *cft,
410             s64 boost)
411 {
412         struct schedtune *st = css_st(css);
413         unsigned threshold_idx;
414         int boost_pct;
415
416         if (boost < -100 || boost > 100)
417                 return -EINVAL;
418
419         st->boost = boost;
420         if (css == &root_schedtune.css)
421                 sysctl_sched_cfs_boost = boost;
422
423         /* Update CPU boost */
424         schedtune_boostgroup_update(st->idx, st->boost);
425
426         trace_sched_tune_config(st->boost);
427
428         return 0;
429 }
430
431 static struct cftype files[] = {
432         {
433                 .name = "boost",
434                 .read_s64 = boost_read,
435                 .write_s64 = boost_write,
436         },
437         { }     /* terminate */
438 };
439
440 static int
441 schedtune_boostgroup_init(struct schedtune *st)
442 {
443         struct boost_groups *bg;
444         int cpu;
445
446         /* Keep track of allocated boost groups */
447         allocated_group[st->idx] = st;
448
449         /* Initialize the per CPU boost groups */
450         for_each_possible_cpu(cpu) {
451                 bg = &per_cpu(cpu_boost_groups, cpu);
452                 bg->group[st->idx].boost = 0;
453                 bg->group[st->idx].tasks = 0;
454         }
455
456         return 0;
457 }
458
459 static int
460 schedtune_init(void)
461 {
462         struct boost_groups *bg;
463         int cpu;
464
465         /* Initialize the per CPU boost groups */
466         for_each_possible_cpu(cpu) {
467                 bg = &per_cpu(cpu_boost_groups, cpu);
468                 memset(bg, 0, sizeof(struct boost_groups));
469         }
470
471         pr_info("  schedtune configured to support %d boost groups\n",
472                 BOOSTGROUPS_COUNT);
473         return 0;
474 }
475
476 static struct cgroup_subsys_state *
477 schedtune_css_alloc(struct cgroup_subsys_state *parent_css)
478 {
479         struct schedtune *st;
480         int idx;
481
482         if (!parent_css) {
483                 schedtune_init();
484                 return &root_schedtune.css;
485         }
486
487         /* Allow only single level hierachies */
488         if (parent_css != &root_schedtune.css) {
489                 pr_err("Nested SchedTune boosting groups not allowed\n");
490                 return ERR_PTR(-ENOMEM);
491         }
492
493         /* Allow only a limited number of boosting groups */
494         for (idx = 1; idx < BOOSTGROUPS_COUNT; ++idx)
495                 if (!allocated_group[idx])
496                         break;
497         if (idx == BOOSTGROUPS_COUNT) {
498                 pr_err("Trying to create more than %d SchedTune boosting groups\n",
499                        BOOSTGROUPS_COUNT);
500                 return ERR_PTR(-ENOSPC);
501         }
502
503         st = kzalloc(sizeof(*st), GFP_KERNEL);
504         if (!st)
505                 goto out;
506
507         /* Initialize per CPUs boost group support */
508         st->idx = idx;
509         if (schedtune_boostgroup_init(st))
510                 goto release;
511
512         return &st->css;
513
514 release:
515         kfree(st);
516 out:
517         return ERR_PTR(-ENOMEM);
518 }
519
520 static void
521 schedtune_boostgroup_release(struct schedtune *st)
522 {
523         /* Reset this boost group */
524         schedtune_boostgroup_update(st->idx, 0);
525
526         /* Keep track of allocated boost groups */
527         allocated_group[st->idx] = NULL;
528 }
529
530 static void
531 schedtune_css_free(struct cgroup_subsys_state *css)
532 {
533         struct schedtune *st = css_st(css);
534
535         schedtune_boostgroup_release(st);
536         kfree(st);
537 }
538
539 struct cgroup_subsys schedtune_cgrp_subsys = {
540         .css_alloc      = schedtune_css_alloc,
541         .css_free       = schedtune_css_free,
542         .legacy_cftypes = files,
543         .early_init     = 1,
544 };
545
546 #else /* CONFIG_CGROUP_SCHEDTUNE */
547
548 int
549 schedtune_accept_deltas(int nrg_delta, int cap_delta,
550                         struct task_struct *task)
551 {
552         /* Optimal (O) region */
553         if (nrg_delta < 0 && cap_delta > 0) {
554                 trace_sched_tune_filter(nrg_delta, cap_delta, 0, 0, 1, 0);
555                 return INT_MAX;
556         }
557
558         /* Suboptimal (S) region */
559         if (nrg_delta > 0 && cap_delta < 0) {
560                 trace_sched_tune_filter(nrg_delta, cap_delta, 0, 0, -1, 5);
561                 return -INT_MAX;
562         }
563
564         return __schedtune_accept_deltas(nrg_delta, cap_delta,
565                         perf_boost_idx, perf_constrain_idx);
566 }
567
568 #endif /* CONFIG_CGROUP_SCHEDTUNE */
569
570 int
571 sysctl_sched_cfs_boost_handler(struct ctl_table *table, int write,
572                                void __user *buffer, size_t *lenp,
573                                loff_t *ppos)
574 {
575         int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
576
577         if (ret || !write)
578                 return ret;
579
580         /* Performance Boost (B) region threshold params */
581         perf_boost_idx  = sysctl_sched_cfs_boost;
582         perf_boost_idx /= 10;
583
584         /* Performance Constraint (C) region threshold params */
585         perf_constrain_idx  = 100 - sysctl_sched_cfs_boost;
586         perf_constrain_idx /= 10;
587
588         return 0;
589 }
590
591 #ifdef CONFIG_SCHED_DEBUG
592 static void
593 schedtune_test_nrg(unsigned long delta_pwr)
594 {
595         unsigned long test_delta_pwr;
596         unsigned long test_norm_pwr;
597         int idx;
598
599         /*
600          * Check normalization constants using some constant system
601          * energy values
602          */
603         pr_info("schedtune: verify normalization constants...\n");
604         for (idx = 0; idx < 6; ++idx) {
605                 test_delta_pwr = delta_pwr >> idx;
606
607                 /* Normalize on max energy for target platform */
608                 test_norm_pwr = reciprocal_divide(
609                                         test_delta_pwr << SCHED_LOAD_SHIFT,
610                                         schedtune_target_nrg.rdiv);
611
612                 pr_info("schedtune: max_pwr/2^%d: %4lu => norm_pwr: %5lu\n",
613                         idx, test_delta_pwr, test_norm_pwr);
614         }
615 }
616 #else
617 #define schedtune_test_nrg(delta_pwr)
618 #endif
619
620 /*
621  * Compute the min/max power consumption of a cluster and all its CPUs
622  */
623 static void
624 schedtune_add_cluster_nrg(
625                 struct sched_domain *sd,
626                 struct sched_group *sg,
627                 struct target_nrg *ste)
628 {
629         struct sched_domain *sd2;
630         struct sched_group *sg2;
631
632         struct cpumask *cluster_cpus;
633         char str[32];
634
635         unsigned long min_pwr;
636         unsigned long max_pwr;
637         int cpu;
638
639         /* Get Cluster energy using EM data for the first CPU */
640         cluster_cpus = sched_group_cpus(sg);
641         snprintf(str, 32, "CLUSTER[%*pbl]",
642                  cpumask_pr_args(cluster_cpus));
643
644         min_pwr = sg->sge->idle_states[sg->sge->nr_idle_states - 1].power;
645         max_pwr = sg->sge->cap_states[sg->sge->nr_cap_states - 1].power;
646         pr_info("schedtune: %-17s min_pwr: %5lu max_pwr: %5lu\n",
647                 str, min_pwr, max_pwr);
648
649         /*
650          * Keep track of this cluster's energy in the computation of the
651          * overall system energy
652          */
653         ste->min_power += min_pwr;
654         ste->max_power += max_pwr;
655
656         /* Get CPU energy using EM data for each CPU in the group */
657         for_each_cpu(cpu, cluster_cpus) {
658                 /* Get a SD view for the specific CPU */
659                 for_each_domain(cpu, sd2) {
660                         /* Get the CPU group */
661                         sg2 = sd2->groups;
662                         min_pwr = sg2->sge->idle_states[sg2->sge->nr_idle_states - 1].power;
663                         max_pwr = sg2->sge->cap_states[sg2->sge->nr_cap_states - 1].power;
664
665                         ste->min_power += min_pwr;
666                         ste->max_power += max_pwr;
667
668                         snprintf(str, 32, "CPU[%d]", cpu);
669                         pr_info("schedtune: %-17s min_pwr: %5lu max_pwr: %5lu\n",
670                                 str, min_pwr, max_pwr);
671
672                         /*
673                          * Assume we have EM data only at the CPU and
674                          * the upper CLUSTER level
675                          */
676                         BUG_ON(!cpumask_equal(
677                                 sched_group_cpus(sg),
678                                 sched_group_cpus(sd2->parent->groups)
679                                 ));
680                         break;
681                 }
682         }
683 }
684
685 /*
686  * Initialize the constants required to compute normalized energy.
687  * The values of these constants depends on the EM data for the specific
688  * target system and topology.
689  * Thus, this function is expected to be called by the code
690  * that bind the EM to the topology information.
691  */
692 static int
693 schedtune_init_late(void)
694 {
695         struct target_nrg *ste = &schedtune_target_nrg;
696         unsigned long delta_pwr = 0;
697         struct sched_domain *sd;
698         struct sched_group *sg;
699
700         pr_info("schedtune: init normalization constants...\n");
701         ste->max_power = 0;
702         ste->min_power = 0;
703
704         rcu_read_lock();
705
706         /*
707          * When EAS is in use, we always have a pointer to the highest SD
708          * which provides EM data.
709          */
710         sd = rcu_dereference(per_cpu(sd_ea, cpumask_first(cpu_online_mask)));
711         if (!sd) {
712                 pr_info("schedtune: no energy model data\n");
713                 goto nodata;
714         }
715
716         sg = sd->groups;
717         do {
718                 schedtune_add_cluster_nrg(sd, sg, ste);
719         } while (sg = sg->next, sg != sd->groups);
720
721         rcu_read_unlock();
722
723         pr_info("schedtune: %-17s min_pwr: %5lu max_pwr: %5lu\n",
724                 "SYSTEM", ste->min_power, ste->max_power);
725
726         /* Compute normalization constants */
727         delta_pwr = ste->max_power - ste->min_power;
728         ste->rdiv = reciprocal_value(delta_pwr);
729         pr_info("schedtune: using normalization constants mul: %u sh1: %u sh2: %u\n",
730                 ste->rdiv.m, ste->rdiv.sh1, ste->rdiv.sh2);
731
732         schedtune_test_nrg(delta_pwr);
733         return 0;
734
735 nodata:
736         rcu_read_unlock();
737         return -EINVAL;
738 }
739 late_initcall(schedtune_init_late);