Merge tag 'v4.0' into p/abusse/merge_upgrade
[projects/modsched/linux.git] / kernel / sched / cfs / fair.c
1 /*
2  * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
3  *
4  *  Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
5  *
6  *  Interactivity improvements by Mike Galbraith
7  *  (C) 2007 Mike Galbraith <efault@gmx.de>
8  *
9  *  Various enhancements by Dmitry Adamushko.
10  *  (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
11  *
12  *  Group scheduling enhancements by Srivatsa Vaddagiri
13  *  Copyright IBM Corporation, 2007
14  *  Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
15  *
16  *  Scaled math optimizations by Thomas Gleixner
17  *  Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
18  *
19  *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
20  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
21  */
22
23 #include <linux/latencytop.h>
24 #include <linux/sched.h>
25 #include <linux/cpumask.h>
26 #include <linux/cpuidle.h>
27 #include <linux/slab.h>
28 #include <linux/profile.h>
29 #include <linux/interrupt.h>
30 #include <linux/mempolicy.h>
31 #include <linux/migrate.h>
32 #include <linux/task_work.h>
33
34 #include <trace/events/sched.h>
35
36 #include "sched.h"
37
38 /*
39  * Targeted preemption latency for CPU-bound tasks:
40  * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)
41  *
42  * NOTE: this latency value is not the same as the concept of
43  * 'timeslice length' - timeslices in CFS are of variable length
44  * and have no persistent notion like in traditional, time-slice
45  * based scheduling concepts.
46  *
47  * (to see the precise effective timeslice length of your workload,
48  *  run vmstat and monitor the context-switches (cs) field)
49  */
50 unsigned int sysctl_sched_latency = 6000000ULL;
51 unsigned int normalized_sysctl_sched_latency = 6000000ULL;
52
53 /*
54  * The initial- and re-scaling of tunables is configurable
55  * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
56  *
57  * Options are:
58  * SCHED_TUNABLESCALING_NONE - unscaled, always *1
59  * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
60  * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
61  */
62 enum sched_tunable_scaling sysctl_sched_tunable_scaling
63         = SCHED_TUNABLESCALING_LOG;
64
65 /*
66  * Minimal preemption granularity for CPU-bound tasks:
67  * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)
68  */
69 unsigned int sysctl_sched_min_granularity = 750000ULL;
70 unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;
71
72 /*
73  * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
74  */
75 static unsigned int sched_nr_latency = 8;
76
77 /*
78  * After fork, child runs first. If set to 0 (default) then
79  * parent will (try to) run first.
80  */
81 unsigned int sysctl_sched_child_runs_first __read_mostly;
82
83 /*
84  * SCHED_OTHER wake-up granularity.
85  * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
86  *
87  * This option delays the preemption effects of decoupled workloads
88  * and reduces their over-scheduling. Synchronous workloads will still
89  * have immediate wakeup/sleep latencies.
90  */
91 unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
92 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
93
94 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
95
96 /*
97  * The exponential sliding  window over which load is averaged for shares
98  * distribution.
99  * (default: 10msec)
100  */
101 unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL;
102
103 #ifdef CONFIG_CFS_BANDWIDTH
104 /*
105  * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
106  * each time a cfs_rq requests quota.
107  *
108  * Note: in the case that the slice exceeds the runtime remaining (either due
109  * to consumption or the quota being specified to be smaller than the slice)
110  * we will always only issue the remaining available time.
111  *
112  * default: 5 msec, units: microseconds
113   */
114 unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL;
115 #endif
116
117 static inline void update_load_add(struct load_weight *lw, unsigned long inc)
118 {
119         lw->weight += inc;
120         lw->inv_weight = 0;
121 }
122
123 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
124 {
125         lw->weight -= dec;
126         lw->inv_weight = 0;
127 }
128
129 static inline void update_load_set(struct load_weight *lw, unsigned long w)
130 {
131         lw->weight = w;
132         lw->inv_weight = 0;
133 }
134
135 /*
136  * Increase the granularity value when there are more CPUs,
137  * because with more CPUs the 'effective latency' as visible
138  * to users decreases. But the relationship is not linear,
139  * so pick a second-best guess by going with the log2 of the
140  * number of CPUs.
141  *
142  * This idea comes from the SD scheduler of Con Kolivas:
143  */
144 static int get_update_sysctl_factor(void)
145 {
146         unsigned int cpus = min_t(int, num_online_cpus(), 8);
147         unsigned int factor;
148
149         switch (sysctl_sched_tunable_scaling) {
150         case SCHED_TUNABLESCALING_NONE:
151                 factor = 1;
152                 break;
153         case SCHED_TUNABLESCALING_LINEAR:
154                 factor = cpus;
155                 break;
156         case SCHED_TUNABLESCALING_LOG:
157         default:
158                 factor = 1 + ilog2(cpus);
159                 break;
160         }
161
162         return factor;
163 }
164
165 static void update_sysctl(void)
166 {
167         unsigned int factor = get_update_sysctl_factor();
168
169 #define SET_SYSCTL(name) \
170         (sysctl_##name = (factor) * normalized_sysctl_##name)
171         SET_SYSCTL(sched_min_granularity);
172         SET_SYSCTL(sched_latency);
173         SET_SYSCTL(sched_wakeup_granularity);
174 #undef SET_SYSCTL
175 }
176
177 void sched_init_granularity(void)
178 {
179         update_sysctl();
180 }
181
182 #define WMULT_CONST     (~0U)
183 #define WMULT_SHIFT     32
184
185 static void __update_inv_weight(struct load_weight *lw)
186 {
187         unsigned long w;
188
189         if (likely(lw->inv_weight))
190                 return;
191
192         w = scale_load_down(lw->weight);
193
194         if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
195                 lw->inv_weight = 1;
196         else if (unlikely(!w))
197                 lw->inv_weight = WMULT_CONST;
198         else
199                 lw->inv_weight = WMULT_CONST / w;
200 }
201
202 /*
203  * delta_exec * weight / lw.weight
204  *   OR
205  * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
206  *
207  * Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case
208  * we're guaranteed shift stays positive because inv_weight is guaranteed to
209  * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
210  *
211  * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
212  * weight/lw.weight <= 1, and therefore our shift will also be positive.
213  */
214 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
215 {
216         u64 fact = scale_load_down(weight);
217         int shift = WMULT_SHIFT;
218
219         __update_inv_weight(lw);
220
221         if (unlikely(fact >> 32)) {
222                 while (fact >> 32) {
223                         fact >>= 1;
224                         shift--;
225                 }
226         }
227
228         /* hint to use a 32x32->64 mul */
229         fact = (u64)(u32)fact * lw->inv_weight;
230
231         while (fact >> 32) {
232                 fact >>= 1;
233                 shift--;
234         }
235
236         return mul_u64_u32_shr(delta_exec, fact, shift);
237 }
238
239
240 const struct sched_class fair_sched_class;
241
242 /**************************************************************
243  * CFS operations on generic schedulable entities:
244  */
245
246 #ifdef CONFIG_FAIR_GROUP_SCHED
247
248 /* cpu runqueue to which this cfs_rq is attached */
249 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
250 {
251         return cfs_rq->rq;
252 }
253
254 /* An entity is a task if it doesn't "own" a runqueue */
255 #define entity_is_task(se)      (!se->my_q)
256
257 static inline struct task_struct *task_of(struct sched_entity *se)
258 {
259 #ifdef CONFIG_SCHED_DEBUG
260         WARN_ON_ONCE(!entity_is_task(se));
261 #endif
262         return container_of(se, struct task_struct, se);
263 }
264
265 /* Walk up scheduling entities hierarchy */
266 #define for_each_sched_entity(se) \
267                 for (; se; se = se->parent)
268
269 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
270 {
271         return p->se.cfs_rq;
272 }
273
274 /* runqueue on which this entity is (to be) queued */
275 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
276 {
277         return se->cfs_rq;
278 }
279
280 /* runqueue "owned" by this group */
281 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
282 {
283         return grp->my_q;
284 }
285
286 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
287                                        int force_update);
288
289 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
290 {
291         if (!cfs_rq->on_list) {
292                 /*
293                  * Ensure we either appear before our parent (if already
294                  * enqueued) or force our parent to appear after us when it is
295                  * enqueued.  The fact that we always enqueue bottom-up
296                  * reduces this to two cases.
297                  */
298                 if (cfs_rq->tg->parent &&
299                     cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
300                         list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
301                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
302                 } else {
303                         list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
304                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
305                 }
306
307                 cfs_rq->on_list = 1;
308                 /* We should have no load, but we need to update last_decay. */
309                 update_cfs_rq_blocked_load(cfs_rq, 0);
310         }
311 }
312
313 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
314 {
315         if (cfs_rq->on_list) {
316                 list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
317                 cfs_rq->on_list = 0;
318         }
319 }
320
321 /* Iterate thr' all leaf cfs_rq's on a runqueue */
322 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
323         list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
324
325 /* Do the two (enqueued) entities belong to the same group ? */
326 static inline struct cfs_rq *
327 is_same_group(struct sched_entity *se, struct sched_entity *pse)
328 {
329         if (se->cfs_rq == pse->cfs_rq)
330                 return se->cfs_rq;
331
332         return NULL;
333 }
334
335 static inline struct sched_entity *parent_entity(struct sched_entity *se)
336 {
337         return se->parent;
338 }
339
340 static void
341 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
342 {
343         int se_depth, pse_depth;
344
345         /*
346          * preemption test can be made between sibling entities who are in the
347          * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
348          * both tasks until we find their ancestors who are siblings of common
349          * parent.
350          */
351
352         /* First walk up until both entities are at same depth */
353         se_depth = (*se)->depth;
354         pse_depth = (*pse)->depth;
355
356         while (se_depth > pse_depth) {
357                 se_depth--;
358                 *se = parent_entity(*se);
359         }
360
361         while (pse_depth > se_depth) {
362                 pse_depth--;
363                 *pse = parent_entity(*pse);
364         }
365
366         while (!is_same_group(*se, *pse)) {
367                 *se = parent_entity(*se);
368                 *pse = parent_entity(*pse);
369         }
370 }
371
372 #else   /* !CONFIG_FAIR_GROUP_SCHED */
373
374 static inline struct task_struct *task_of(struct sched_entity *se)
375 {
376         return container_of(se, struct task_struct, se);
377 }
378
379 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
380 {
381         return container_of(cfs_rq, struct rq, cfs);
382 }
383
384 #define entity_is_task(se)      1
385
386 #define for_each_sched_entity(se) \
387                 for (; se; se = NULL)
388
389 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
390 {
391         return &task_rq(p)->cfs;
392 }
393
394 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
395 {
396         struct task_struct *p = task_of(se);
397         struct rq *rq = task_rq(p);
398
399         return &rq->cfs;
400 }
401
402 /* runqueue "owned" by this group */
403 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
404 {
405         return NULL;
406 }
407
408 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
409 {
410 }
411
412 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
413 {
414 }
415
416 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
417                 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
418
419 static inline struct sched_entity *parent_entity(struct sched_entity *se)
420 {
421         return NULL;
422 }
423
424 static inline void
425 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
426 {
427 }
428
429 #endif  /* CONFIG_FAIR_GROUP_SCHED */
430
431 static __always_inline
432 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);
433
434 /**************************************************************
435  * Scheduling class tree data structure manipulation methods:
436  */
437
438 static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
439 {
440         s64 delta = (s64)(vruntime - max_vruntime);
441         if (delta > 0)
442                 max_vruntime = vruntime;
443
444         return max_vruntime;
445 }
446
447 static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
448 {
449         s64 delta = (s64)(vruntime - min_vruntime);
450         if (delta < 0)
451                 min_vruntime = vruntime;
452
453         return min_vruntime;
454 }
455
456 static inline int entity_before(struct sched_entity *a,
457                                 struct sched_entity *b)
458 {
459         return (s64)(a->vruntime - b->vruntime) < 0;
460 }
461
462 static void update_min_vruntime(struct cfs_rq *cfs_rq)
463 {
464         u64 vruntime = cfs_rq->min_vruntime;
465
466         if (cfs_rq->curr)
467                 vruntime = cfs_rq->curr->vruntime;
468
469         if (cfs_rq->rb_leftmost) {
470                 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
471                                                    struct sched_entity,
472                                                    run_node);
473
474                 if (!cfs_rq->curr)
475                         vruntime = se->vruntime;
476                 else
477                         vruntime = min_vruntime(vruntime, se->vruntime);
478         }
479
480         /* ensure we never gain time by being placed backwards. */
481         cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
482 #ifndef CONFIG_64BIT
483         smp_wmb();
484         cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
485 #endif
486 }
487
488 /*
489  * Enqueue an entity into the rb-tree:
490  */
491 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
492 {
493         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
494         struct rb_node *parent = NULL;
495         struct sched_entity *entry;
496         int leftmost = 1;
497
498         /*
499          * Find the right place in the rbtree:
500          */
501         while (*link) {
502                 parent = *link;
503                 entry = rb_entry(parent, struct sched_entity, run_node);
504                 /*
505                  * We dont care about collisions. Nodes with
506                  * the same key stay together.
507                  */
508                 if (entity_before(se, entry)) {
509                         link = &parent->rb_left;
510                 } else {
511                         link = &parent->rb_right;
512                         leftmost = 0;
513                 }
514         }
515
516         /*
517          * Maintain a cache of leftmost tree entries (it is frequently
518          * used):
519          */
520         if (leftmost)
521                 cfs_rq->rb_leftmost = &se->run_node;
522
523         rb_link_node(&se->run_node, parent, link);
524         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
525 }
526
527 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
528 {
529         if (cfs_rq->rb_leftmost == &se->run_node) {
530                 struct rb_node *next_node;
531
532                 next_node = rb_next(&se->run_node);
533                 cfs_rq->rb_leftmost = next_node;
534         }
535
536         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
537 }
538
539 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
540 {
541         struct rb_node *left = cfs_rq->rb_leftmost;
542
543         if (!left)
544                 return NULL;
545
546         return rb_entry(left, struct sched_entity, run_node);
547 }
548
549 static struct sched_entity *__pick_next_entity(struct sched_entity *se)
550 {
551         struct rb_node *next = rb_next(&se->run_node);
552
553         if (!next)
554                 return NULL;
555
556         return rb_entry(next, struct sched_entity, run_node);
557 }
558
559 #ifdef CONFIG_SCHED_DEBUG
560 struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
561 {
562         struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
563
564         if (!last)
565                 return NULL;
566
567         return rb_entry(last, struct sched_entity, run_node);
568 }
569
570 /**************************************************************
571  * Scheduling class statistics methods:
572  */
573
574 int sched_proc_update_handler(struct ctl_table *table, int write,
575                 void __user *buffer, size_t *lenp,
576                 loff_t *ppos)
577 {
578         int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
579         int factor = get_update_sysctl_factor();
580
581         if (ret || !write)
582                 return ret;
583
584         sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
585                                         sysctl_sched_min_granularity);
586
587 #define WRT_SYSCTL(name) \
588         (normalized_sysctl_##name = sysctl_##name / (factor))
589         WRT_SYSCTL(sched_min_granularity);
590         WRT_SYSCTL(sched_latency);
591         WRT_SYSCTL(sched_wakeup_granularity);
592 #undef WRT_SYSCTL
593
594         return 0;
595 }
596 #endif
597
598 /*
599  * delta /= w
600  */
601 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
602 {
603         if (unlikely(se->load.weight != NICE_0_LOAD))
604                 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
605
606         return delta;
607 }
608
609 /*
610  * The idea is to set a period in which each task runs once.
611  *
612  * When there are too many tasks (sched_nr_latency) we have to stretch
613  * this period because otherwise the slices get too small.
614  *
615  * p = (nr <= nl) ? l : l*nr/nl
616  */
617 static u64 __sched_period(unsigned long nr_running)
618 {
619         u64 period = sysctl_sched_latency;
620         unsigned long nr_latency = sched_nr_latency;
621
622         if (unlikely(nr_running > nr_latency)) {
623                 period = sysctl_sched_min_granularity;
624                 period *= nr_running;
625         }
626
627         return period;
628 }
629
630 /*
631  * We calculate the wall-time slice from the period by taking a part
632  * proportional to the weight.
633  *
634  * s = p*P[w/rw]
635  */
636 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
637 {
638         u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
639
640         for_each_sched_entity(se) {
641                 struct load_weight *load;
642                 struct load_weight lw;
643
644                 cfs_rq = cfs_rq_of(se);
645                 load = &cfs_rq->load;
646
647                 if (unlikely(!se->on_rq)) {
648                         lw = cfs_rq->load;
649
650                         update_load_add(&lw, se->load.weight);
651                         load = &lw;
652                 }
653                 slice = __calc_delta(slice, se->load.weight, load);
654         }
655         return slice;
656 }
657
658 /*
659  * We calculate the vruntime slice of a to-be-inserted task.
660  *
661  * vs = s/w
662  */
663 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
664 {
665         return calc_delta_fair(sched_slice(cfs_rq, se), se);
666 }
667
668 #ifdef CONFIG_SMP
669 static int select_idle_sibling(struct task_struct *p, int cpu);
670 static unsigned long task_h_load(struct task_struct *p);
671
672 static inline void __update_task_entity_contrib(struct sched_entity *se);
673
674 /* Give new task start runnable values to heavy its load in infant time */
675 void init_task_runnable_average(struct task_struct *p)
676 {
677         u32 slice;
678
679         slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
680         p->se.avg.runnable_avg_sum = slice;
681         p->se.avg.runnable_avg_period = slice;
682         __update_task_entity_contrib(&p->se);
683 }
684 #else
685 void init_task_runnable_average(struct task_struct *p)
686 {
687 }
688 #endif
689
690 /*
691  * Update the current task's runtime statistics.
692  */
693 static void update_curr(struct cfs_rq *cfs_rq)
694 {
695         struct sched_entity *curr = cfs_rq->curr;
696         u64 now = rq_clock_task(rq_of(cfs_rq));
697         u64 delta_exec;
698
699         if (unlikely(!curr))
700                 return;
701
702         delta_exec = now - curr->exec_start;
703         if (unlikely((s64)delta_exec <= 0))
704                 return;
705
706         curr->exec_start = now;
707
708         schedstat_set(curr->statistics.exec_max,
709                       max(delta_exec, curr->statistics.exec_max));
710
711         curr->sum_exec_runtime += delta_exec;
712         schedstat_add(cfs_rq, exec_clock, delta_exec);
713
714         curr->vruntime += calc_delta_fair(delta_exec, curr);
715         update_min_vruntime(cfs_rq);
716
717         if (entity_is_task(curr)) {
718                 struct task_struct *curtask = task_of(curr);
719
720                 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
721                 cpuacct_charge(curtask, delta_exec);
722                 account_group_exec_runtime(curtask, delta_exec);
723         }
724
725         account_cfs_rq_runtime(cfs_rq, delta_exec);
726 }
727
728 static void update_curr_fair(struct rq *rq)
729 {
730         update_curr(cfs_rq_of(&rq->curr->se));
731 }
732
733 static inline void
734 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
735 {
736         schedstat_set(se->statistics.wait_start, rq_clock(rq_of(cfs_rq)));
737 }
738
739 /*
740  * Task is being enqueued - update stats:
741  */
742 static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
743 {
744         /*
745          * Are we enqueueing a waiting task? (for current tasks
746          * a dequeue/enqueue event is a NOP)
747          */
748         if (se != cfs_rq->curr)
749                 update_stats_wait_start(cfs_rq, se);
750 }
751
752 static void
753 update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
754 {
755         schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
756                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start));
757         schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
758         schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
759                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
760 #ifdef CONFIG_SCHEDSTATS
761         if (entity_is_task(se)) {
762                 trace_sched_stat_wait(task_of(se),
763                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
764         }
765 #endif
766         schedstat_set(se->statistics.wait_start, 0);
767 }
768
769 static inline void
770 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
771 {
772         /*
773          * Mark the end of the wait period if dequeueing a
774          * waiting task:
775          */
776         if (se != cfs_rq->curr)
777                 update_stats_wait_end(cfs_rq, se);
778 }
779
780 /*
781  * We are picking a new current task - update its stats:
782  */
783 static inline void
784 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
785 {
786         /*
787          * We are starting a new run period:
788          */
789         se->exec_start = rq_clock_task(rq_of(cfs_rq));
790 }
791
792 /**************************************************
793  * Scheduling class queueing methods:
794  */
795
796 #ifdef CONFIG_NUMA_BALANCING
797 /*
798  * Approximate time to scan a full NUMA task in ms. The task scan period is
799  * calculated based on the tasks virtual memory size and
800  * numa_balancing_scan_size.
801  */
802 unsigned int sysctl_numa_balancing_scan_period_min = 1000;
803 unsigned int sysctl_numa_balancing_scan_period_max = 60000;
804
805 /* Portion of address space to scan in MB */
806 unsigned int sysctl_numa_balancing_scan_size = 256;
807
808 /* Scan @scan_size MB every @scan_period after an initial @scan_delay in ms */
809 unsigned int sysctl_numa_balancing_scan_delay = 1000;
810
811 static unsigned int task_nr_scan_windows(struct task_struct *p)
812 {
813         unsigned long rss = 0;
814         unsigned long nr_scan_pages;
815
816         /*
817          * Calculations based on RSS as non-present and empty pages are skipped
818          * by the PTE scanner and NUMA hinting faults should be trapped based
819          * on resident pages
820          */
821         nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT);
822         rss = get_mm_rss(p->mm);
823         if (!rss)
824                 rss = nr_scan_pages;
825
826         rss = round_up(rss, nr_scan_pages);
827         return rss / nr_scan_pages;
828 }
829
830 /* For sanitys sake, never scan more PTEs than MAX_SCAN_WINDOW MB/sec. */
831 #define MAX_SCAN_WINDOW 2560
832
833 static unsigned int task_scan_min(struct task_struct *p)
834 {
835         unsigned int scan_size = ACCESS_ONCE(sysctl_numa_balancing_scan_size);
836         unsigned int scan, floor;
837         unsigned int windows = 1;
838
839         if (scan_size < MAX_SCAN_WINDOW)
840                 windows = MAX_SCAN_WINDOW / scan_size;
841         floor = 1000 / windows;
842
843         scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p);
844         return max_t(unsigned int, floor, scan);
845 }
846
847 static unsigned int task_scan_max(struct task_struct *p)
848 {
849         unsigned int smin = task_scan_min(p);
850         unsigned int smax;
851
852         /* Watch for min being lower than max due to floor calculations */
853         smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p);
854         return max(smin, smax);
855 }
856
857 static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
858 {
859         rq->nr_numa_running += (p->numa_preferred_nid != -1);
860         rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
861 }
862
863 static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
864 {
865         rq->nr_numa_running -= (p->numa_preferred_nid != -1);
866         rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
867 }
868
869 struct numa_group {
870         atomic_t refcount;
871
872         spinlock_t lock; /* nr_tasks, tasks */
873         int nr_tasks;
874         pid_t gid;
875
876         struct rcu_head rcu;
877         nodemask_t active_nodes;
878         unsigned long total_faults;
879         /*
880          * Faults_cpu is used to decide whether memory should move
881          * towards the CPU. As a consequence, these stats are weighted
882          * more by CPU use than by memory faults.
883          */
884         unsigned long *faults_cpu;
885         unsigned long faults[0];
886 };
887
888 /* Shared or private faults. */
889 #define NR_NUMA_HINT_FAULT_TYPES 2
890
891 /* Memory and CPU locality */
892 #define NR_NUMA_HINT_FAULT_STATS (NR_NUMA_HINT_FAULT_TYPES * 2)
893
894 /* Averaged statistics, and temporary buffers. */
895 #define NR_NUMA_HINT_FAULT_BUCKETS (NR_NUMA_HINT_FAULT_STATS * 2)
896
897 pid_t task_numa_group_id(struct task_struct *p)
898 {
899         return p->numa_group ? p->numa_group->gid : 0;
900 }
901
902 /*
903  * The averaged statistics, shared & private, memory & cpu,
904  * occupy the first half of the array. The second half of the
905  * array is for current counters, which are averaged into the
906  * first set by task_numa_placement.
907  */
908 static inline int task_faults_idx(enum numa_faults_stats s, int nid, int priv)
909 {
910         return NR_NUMA_HINT_FAULT_TYPES * (s * nr_node_ids + nid) + priv;
911 }
912
913 static inline unsigned long task_faults(struct task_struct *p, int nid)
914 {
915         if (!p->numa_faults)
916                 return 0;
917
918         return p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)] +
919                 p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];
920 }
921
922 static inline unsigned long group_faults(struct task_struct *p, int nid)
923 {
924         if (!p->numa_group)
925                 return 0;
926
927         return p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 0)] +
928                 p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 1)];
929 }
930
931 static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
932 {
933         return group->faults_cpu[task_faults_idx(NUMA_MEM, nid, 0)] +
934                 group->faults_cpu[task_faults_idx(NUMA_MEM, nid, 1)];
935 }
936
937 /* Handle placement on systems where not all nodes are directly connected. */
938 static unsigned long score_nearby_nodes(struct task_struct *p, int nid,
939                                         int maxdist, bool task)
940 {
941         unsigned long score = 0;
942         int node;
943
944         /*
945          * All nodes are directly connected, and the same distance
946          * from each other. No need for fancy placement algorithms.
947          */
948         if (sched_numa_topology_type == NUMA_DIRECT)
949                 return 0;
950
951         /*
952          * This code is called for each node, introducing N^2 complexity,
953          * which should be ok given the number of nodes rarely exceeds 8.
954          */
955         for_each_online_node(node) {
956                 unsigned long faults;
957                 int dist = node_distance(nid, node);
958
959                 /*
960                  * The furthest away nodes in the system are not interesting
961                  * for placement; nid was already counted.
962                  */
963                 if (dist == sched_max_numa_distance || node == nid)
964                         continue;
965
966                 /*
967                  * On systems with a backplane NUMA topology, compare groups
968                  * of nodes, and move tasks towards the group with the most
969                  * memory accesses. When comparing two nodes at distance
970                  * "hoplimit", only nodes closer by than "hoplimit" are part
971                  * of each group. Skip other nodes.
972                  */
973                 if (sched_numa_topology_type == NUMA_BACKPLANE &&
974                                         dist > maxdist)
975                         continue;
976
977                 /* Add up the faults from nearby nodes. */
978                 if (task)
979                         faults = task_faults(p, node);
980                 else
981                         faults = group_faults(p, node);
982
983                 /*
984                  * On systems with a glueless mesh NUMA topology, there are
985                  * no fixed "groups of nodes". Instead, nodes that are not
986                  * directly connected bounce traffic through intermediate
987                  * nodes; a numa_group can occupy any set of nodes.
988                  * The further away a node is, the less the faults count.
989                  * This seems to result in good task placement.
990                  */
991                 if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
992                         faults *= (sched_max_numa_distance - dist);
993                         faults /= (sched_max_numa_distance - LOCAL_DISTANCE);
994                 }
995
996                 score += faults;
997         }
998
999         return score;
1000 }
1001
1002 /*
1003  * These return the fraction of accesses done by a particular task, or
1004  * task group, on a particular numa node.  The group weight is given a
1005  * larger multiplier, in order to group tasks together that are almost
1006  * evenly spread out between numa nodes.
1007  */
1008 static inline unsigned long task_weight(struct task_struct *p, int nid,
1009                                         int dist)
1010 {
1011         unsigned long faults, total_faults;
1012
1013         if (!p->numa_faults)
1014                 return 0;
1015
1016         total_faults = p->total_numa_faults;
1017
1018         if (!total_faults)
1019                 return 0;
1020
1021         faults = task_faults(p, nid);
1022         faults += score_nearby_nodes(p, nid, dist, true);
1023
1024         return 1000 * faults / total_faults;
1025 }
1026
1027 static inline unsigned long group_weight(struct task_struct *p, int nid,
1028                                          int dist)
1029 {
1030         unsigned long faults, total_faults;
1031
1032         if (!p->numa_group)
1033                 return 0;
1034
1035         total_faults = p->numa_group->total_faults;
1036
1037         if (!total_faults)
1038                 return 0;
1039
1040         faults = group_faults(p, nid);
1041         faults += score_nearby_nodes(p, nid, dist, false);
1042
1043         return 1000 * faults / total_faults;
1044 }
1045
1046 bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
1047                                 int src_nid, int dst_cpu)
1048 {
1049         struct numa_group *ng = p->numa_group;
1050         int dst_nid = cpu_to_node(dst_cpu);
1051         int last_cpupid, this_cpupid;
1052
1053         this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
1054
1055         /*
1056          * Multi-stage node selection is used in conjunction with a periodic
1057          * migration fault to build a temporal task<->page relation. By using
1058          * a two-stage filter we remove short/unlikely relations.
1059          *
1060          * Using P(p) ~ n_p / n_t as per frequentist probability, we can equate
1061          * a task's usage of a particular page (n_p) per total usage of this
1062          * page (n_t) (in a given time-span) to a probability.
1063          *
1064          * Our periodic faults will sample this probability and getting the
1065          * same result twice in a row, given these samples are fully
1066          * independent, is then given by P(n)^2, provided our sample period
1067          * is sufficiently short compared to the usage pattern.
1068          *
1069          * This quadric squishes small probabilities, making it less likely we
1070          * act on an unlikely task<->page relation.
1071          */
1072         last_cpupid = page_cpupid_xchg_last(page, this_cpupid);
1073         if (!cpupid_pid_unset(last_cpupid) &&
1074                                 cpupid_to_nid(last_cpupid) != dst_nid)
1075                 return false;
1076
1077         /* Always allow migrate on private faults */
1078         if (cpupid_match_pid(p, last_cpupid))
1079                 return true;
1080
1081         /* A shared fault, but p->numa_group has not been set up yet. */
1082         if (!ng)
1083                 return true;
1084
1085         /*
1086          * Do not migrate if the destination is not a node that
1087          * is actively used by this numa group.
1088          */
1089         if (!node_isset(dst_nid, ng->active_nodes))
1090                 return false;
1091
1092         /*
1093          * Source is a node that is not actively used by this
1094          * numa group, while the destination is. Migrate.
1095          */
1096         if (!node_isset(src_nid, ng->active_nodes))
1097                 return true;
1098
1099         /*
1100          * Both source and destination are nodes in active
1101          * use by this numa group. Maximize memory bandwidth
1102          * by migrating from more heavily used groups, to less
1103          * heavily used ones, spreading the load around.
1104          * Use a 1/4 hysteresis to avoid spurious page movement.
1105          */
1106         return group_faults(p, dst_nid) < (group_faults(p, src_nid) * 3 / 4);
1107 }
1108
1109 static unsigned long weighted_cpuload(const int cpu);
1110 static unsigned long source_load(int cpu, int type);
1111 static unsigned long target_load(int cpu, int type);
1112 static unsigned long capacity_of(int cpu);
1113 static long effective_load(struct task_group *tg, int cpu, long wl, long wg);
1114
1115 /* Cached statistics for all CPUs within a node */
1116 struct numa_stats {
1117         unsigned long nr_running;
1118         unsigned long load;
1119
1120         /* Total compute capacity of CPUs on a node */
1121         unsigned long compute_capacity;
1122
1123         /* Approximate capacity in terms of runnable tasks on a node */
1124         unsigned long task_capacity;
1125         int has_free_capacity;
1126 };
1127
1128 /*
1129  * XXX borrowed from update_sg_lb_stats
1130  */
1131 static void update_numa_stats(struct numa_stats *ns, int nid)
1132 {
1133         int smt, cpu, cpus = 0;
1134         unsigned long capacity;
1135
1136         memset(ns, 0, sizeof(*ns));
1137         for_each_cpu(cpu, cpumask_of_node(nid)) {
1138                 struct rq *rq = cpu_rq(cpu);
1139
1140                 ns->nr_running += rq->nr_running;
1141                 ns->load += weighted_cpuload(cpu);
1142                 ns->compute_capacity += capacity_of(cpu);
1143
1144                 cpus++;
1145         }
1146
1147         /*
1148          * If we raced with hotplug and there are no CPUs left in our mask
1149          * the @ns structure is NULL'ed and task_numa_compare() will
1150          * not find this node attractive.
1151          *
1152          * We'll either bail at !has_free_capacity, or we'll detect a huge
1153          * imbalance and bail there.
1154          */
1155         if (!cpus)
1156                 return;
1157
1158         /* smt := ceil(cpus / capacity), assumes: 1 < smt_power < 2 */
1159         smt = DIV_ROUND_UP(SCHED_CAPACITY_SCALE * cpus, ns->compute_capacity);
1160         capacity = cpus / smt; /* cores */
1161
1162         ns->task_capacity = min_t(unsigned, capacity,
1163                 DIV_ROUND_CLOSEST(ns->compute_capacity, SCHED_CAPACITY_SCALE));
1164         ns->has_free_capacity = (ns->nr_running < ns->task_capacity);
1165 }
1166
1167 struct task_numa_env {
1168         struct task_struct *p;
1169
1170         int src_cpu, src_nid;
1171         int dst_cpu, dst_nid;
1172
1173         struct numa_stats src_stats, dst_stats;
1174
1175         int imbalance_pct;
1176         int dist;
1177
1178         struct task_struct *best_task;
1179         long best_imp;
1180         int best_cpu;
1181 };
1182
1183 static void task_numa_assign(struct task_numa_env *env,
1184                              struct task_struct *p, long imp)
1185 {
1186         if (env->best_task)
1187                 put_task_struct(env->best_task);
1188         if (p)
1189                 get_task_struct(p);
1190
1191         env->best_task = p;
1192         env->best_imp = imp;
1193         env->best_cpu = env->dst_cpu;
1194 }
1195
1196 static bool load_too_imbalanced(long src_load, long dst_load,
1197                                 struct task_numa_env *env)
1198 {
1199         long imb, old_imb;
1200         long orig_src_load, orig_dst_load;
1201         long src_capacity, dst_capacity;
1202
1203         /*
1204          * The load is corrected for the CPU capacity available on each node.
1205          *
1206          * src_load        dst_load
1207          * ------------ vs ---------
1208          * src_capacity    dst_capacity
1209          */
1210         src_capacity = env->src_stats.compute_capacity;
1211         dst_capacity = env->dst_stats.compute_capacity;
1212
1213         /* We care about the slope of the imbalance, not the direction. */
1214         if (dst_load < src_load)
1215                 swap(dst_load, src_load);
1216
1217         /* Is the difference below the threshold? */
1218         imb = dst_load * src_capacity * 100 -
1219               src_load * dst_capacity * env->imbalance_pct;
1220         if (imb <= 0)
1221                 return false;
1222
1223         /*
1224          * The imbalance is above the allowed threshold.
1225          * Compare it with the old imbalance.
1226          */
1227         orig_src_load = env->src_stats.load;
1228         orig_dst_load = env->dst_stats.load;
1229
1230         if (orig_dst_load < orig_src_load)
1231                 swap(orig_dst_load, orig_src_load);
1232
1233         old_imb = orig_dst_load * src_capacity * 100 -
1234                   orig_src_load * dst_capacity * env->imbalance_pct;
1235
1236         /* Would this change make things worse? */
1237         return (imb > old_imb);
1238 }
1239
1240 /*
1241  * This checks if the overall compute and NUMA accesses of the system would
1242  * be improved if the source tasks was migrated to the target dst_cpu taking
1243  * into account that it might be best if task running on the dst_cpu should
1244  * be exchanged with the source task
1245  */
1246 static void task_numa_compare(struct task_numa_env *env,
1247                               long taskimp, long groupimp)
1248 {
1249         struct rq *src_rq = cpu_rq(env->src_cpu);
1250         struct rq *dst_rq = cpu_rq(env->dst_cpu);
1251         struct task_struct *cur;
1252         long src_load, dst_load;
1253         long load;
1254         long imp = env->p->numa_group ? groupimp : taskimp;
1255         long moveimp = imp;
1256         int dist = env->dist;
1257
1258         rcu_read_lock();
1259
1260         raw_spin_lock_irq(&dst_rq->lock);
1261         cur = dst_rq->curr;
1262         /*
1263          * No need to move the exiting task, and this ensures that ->curr
1264          * wasn't reaped and thus get_task_struct() in task_numa_assign()
1265          * is safe under RCU read lock.
1266          * Note that rcu_read_lock() itself can't protect from the final
1267          * put_task_struct() after the last schedule().
1268          */
1269         if ((cur->flags & PF_EXITING) || is_idle_task(cur))
1270                 cur = NULL;
1271         raw_spin_unlock_irq(&dst_rq->lock);
1272
1273         /*
1274          * Because we have preemption enabled we can get migrated around and
1275          * end try selecting ourselves (current == env->p) as a swap candidate.
1276          */
1277         if (cur == env->p)
1278                 goto unlock;
1279
1280         /*
1281          * "imp" is the fault differential for the source task between the
1282          * source and destination node. Calculate the total differential for
1283          * the source task and potential destination task. The more negative
1284          * the value is, the more rmeote accesses that would be expected to
1285          * be incurred if the tasks were swapped.
1286          */
1287         if (cur) {
1288                 /* Skip this swap candidate if cannot move to the source cpu */
1289                 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
1290                         goto unlock;
1291
1292                 /*
1293                  * If dst and source tasks are in the same NUMA group, or not
1294                  * in any group then look only at task weights.
1295                  */
1296                 if (cur->numa_group == env->p->numa_group) {
1297                         imp = taskimp + task_weight(cur, env->src_nid, dist) -
1298                               task_weight(cur, env->dst_nid, dist);
1299                         /*
1300                          * Add some hysteresis to prevent swapping the
1301                          * tasks within a group over tiny differences.
1302                          */
1303                         if (cur->numa_group)
1304                                 imp -= imp/16;
1305                 } else {
1306                         /*
1307                          * Compare the group weights. If a task is all by
1308                          * itself (not part of a group), use the task weight
1309                          * instead.
1310                          */
1311                         if (cur->numa_group)
1312                                 imp += group_weight(cur, env->src_nid, dist) -
1313                                        group_weight(cur, env->dst_nid, dist);
1314                         else
1315                                 imp += task_weight(cur, env->src_nid, dist) -
1316                                        task_weight(cur, env->dst_nid, dist);
1317                 }
1318         }
1319
1320         if (imp <= env->best_imp && moveimp <= env->best_imp)
1321                 goto unlock;
1322
1323         if (!cur) {
1324                 /* Is there capacity at our destination? */
1325                 if (env->src_stats.nr_running <= env->src_stats.task_capacity &&
1326                     !env->dst_stats.has_free_capacity)
1327                         goto unlock;
1328
1329                 goto balance;
1330         }
1331
1332         /* Balance doesn't matter much if we're running a task per cpu */
1333         if (imp > env->best_imp && src_rq->nr_running == 1 &&
1334                         dst_rq->nr_running == 1)
1335                 goto assign;
1336
1337         /*
1338          * In the overloaded case, try and keep the load balanced.
1339          */
1340 balance:
1341         load = task_h_load(env->p);
1342         dst_load = env->dst_stats.load + load;
1343         src_load = env->src_stats.load - load;
1344
1345         if (moveimp > imp && moveimp > env->best_imp) {
1346                 /*
1347                  * If the improvement from just moving env->p direction is
1348                  * better than swapping tasks around, check if a move is
1349                  * possible. Store a slightly smaller score than moveimp,
1350                  * so an actually idle CPU will win.
1351                  */
1352                 if (!load_too_imbalanced(src_load, dst_load, env)) {
1353                         imp = moveimp - 1;
1354                         cur = NULL;
1355                         goto assign;
1356                 }
1357         }
1358
1359         if (imp <= env->best_imp)
1360                 goto unlock;
1361
1362         if (cur) {
1363                 load = task_h_load(cur);
1364                 dst_load -= load;
1365                 src_load += load;
1366         }
1367
1368         if (load_too_imbalanced(src_load, dst_load, env))
1369                 goto unlock;
1370
1371         /*
1372          * One idle CPU per node is evaluated for a task numa move.
1373          * Call select_idle_sibling to maybe find a better one.
1374          */
1375         if (!cur)
1376                 env->dst_cpu = select_idle_sibling(env->p, env->dst_cpu);
1377
1378 assign:
1379         task_numa_assign(env, cur, imp);
1380 unlock:
1381         rcu_read_unlock();
1382 }
1383
1384 static void task_numa_find_cpu(struct task_numa_env *env,
1385                                 long taskimp, long groupimp)
1386 {
1387         int cpu;
1388
1389         for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
1390                 /* Skip this CPU if the source task cannot migrate */
1391                 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
1392                         continue;
1393
1394                 env->dst_cpu = cpu;
1395                 task_numa_compare(env, taskimp, groupimp);
1396         }
1397 }
1398
1399 static int task_numa_migrate(struct task_struct *p)
1400 {
1401         struct task_numa_env env = {
1402                 .p = p,
1403
1404                 .src_cpu = task_cpu(p),
1405                 .src_nid = task_node(p),
1406
1407                 .imbalance_pct = 112,
1408
1409                 .best_task = NULL,
1410                 .best_imp = 0,
1411                 .best_cpu = -1
1412         };
1413         struct sched_domain *sd;
1414         unsigned long taskweight, groupweight;
1415         int nid, ret, dist;
1416         long taskimp, groupimp;
1417
1418         /*
1419          * Pick the lowest SD_NUMA domain, as that would have the smallest
1420          * imbalance and would be the first to start moving tasks about.
1421          *
1422          * And we want to avoid any moving of tasks about, as that would create
1423          * random movement of tasks -- counter the numa conditions we're trying
1424          * to satisfy here.
1425          */
1426         rcu_read_lock();
1427         sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
1428         if (sd)
1429                 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
1430         rcu_read_unlock();
1431
1432         /*
1433          * Cpusets can break the scheduler domain tree into smaller
1434          * balance domains, some of which do not cross NUMA boundaries.
1435          * Tasks that are "trapped" in such domains cannot be migrated
1436          * elsewhere, so there is no point in (re)trying.
1437          */
1438         if (unlikely(!sd)) {
1439                 p->numa_preferred_nid = task_node(p);
1440                 return -EINVAL;
1441         }
1442
1443         env.dst_nid = p->numa_preferred_nid;
1444         dist = env.dist = node_distance(env.src_nid, env.dst_nid);
1445         taskweight = task_weight(p, env.src_nid, dist);
1446         groupweight = group_weight(p, env.src_nid, dist);
1447         update_numa_stats(&env.src_stats, env.src_nid);
1448         taskimp = task_weight(p, env.dst_nid, dist) - taskweight;
1449         groupimp = group_weight(p, env.dst_nid, dist) - groupweight;
1450         update_numa_stats(&env.dst_stats, env.dst_nid);
1451
1452         /* Try to find a spot on the preferred nid. */
1453         task_numa_find_cpu(&env, taskimp, groupimp);
1454
1455         /*
1456          * Look at other nodes in these cases:
1457          * - there is no space available on the preferred_nid
1458          * - the task is part of a numa_group that is interleaved across
1459          *   multiple NUMA nodes; in order to better consolidate the group,
1460          *   we need to check other locations.
1461          */
1462         if (env.best_cpu == -1 || (p->numa_group &&
1463                         nodes_weight(p->numa_group->active_nodes) > 1)) {
1464                 for_each_online_node(nid) {
1465                         if (nid == env.src_nid || nid == p->numa_preferred_nid)
1466                                 continue;
1467
1468                         dist = node_distance(env.src_nid, env.dst_nid);
1469                         if (sched_numa_topology_type == NUMA_BACKPLANE &&
1470                                                 dist != env.dist) {
1471                                 taskweight = task_weight(p, env.src_nid, dist);
1472                                 groupweight = group_weight(p, env.src_nid, dist);
1473                         }
1474
1475                         /* Only consider nodes where both task and groups benefit */
1476                         taskimp = task_weight(p, nid, dist) - taskweight;
1477                         groupimp = group_weight(p, nid, dist) - groupweight;
1478                         if (taskimp < 0 && groupimp < 0)
1479                                 continue;
1480
1481                         env.dist = dist;
1482                         env.dst_nid = nid;
1483                         update_numa_stats(&env.dst_stats, env.dst_nid);
1484                         task_numa_find_cpu(&env, taskimp, groupimp);
1485                 }
1486         }
1487
1488         /*
1489          * If the task is part of a workload that spans multiple NUMA nodes,
1490          * and is migrating into one of the workload's active nodes, remember
1491          * this node as the task's preferred numa node, so the workload can
1492          * settle down.
1493          * A task that migrated to a second choice node will be better off
1494          * trying for a better one later. Do not set the preferred node here.
1495          */
1496         if (p->numa_group) {
1497                 if (env.best_cpu == -1)
1498                         nid = env.src_nid;
1499                 else
1500                         nid = env.dst_nid;
1501
1502                 if (node_isset(nid, p->numa_group->active_nodes))
1503                         sched_setnuma(p, env.dst_nid);
1504         }
1505
1506         /* No better CPU than the current one was found. */
1507         if (env.best_cpu == -1)
1508                 return -EAGAIN;
1509
1510         /*
1511          * Reset the scan period if the task is being rescheduled on an
1512          * alternative node to recheck if the tasks is now properly placed.
1513          */
1514         p->numa_scan_period = task_scan_min(p);
1515
1516         if (env.best_task == NULL) {
1517                 ret = migrate_task_to(p, env.best_cpu);
1518                 if (ret != 0)
1519                         trace_sched_stick_numa(p, env.src_cpu, env.best_cpu);
1520                 return ret;
1521         }
1522
1523         ret = migrate_swap(p, env.best_task);
1524         if (ret != 0)
1525                 trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task));
1526         put_task_struct(env.best_task);
1527         return ret;
1528 }
1529
1530 /* Attempt to migrate a task to a CPU on the preferred node. */
1531 static void numa_migrate_preferred(struct task_struct *p)
1532 {
1533         unsigned long interval = HZ;
1534
1535         /* This task has no NUMA fault statistics yet */
1536         if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults))
1537                 return;
1538
1539         /* Periodically retry migrating the task to the preferred node */
1540         interval = min(interval, msecs_to_jiffies(p->numa_scan_period) / 16);
1541         p->numa_migrate_retry = jiffies + interval;
1542
1543         /* Success if task is already running on preferred CPU */
1544         if (task_node(p) == p->numa_preferred_nid)
1545                 return;
1546
1547         /* Otherwise, try migrate to a CPU on the preferred node */
1548         task_numa_migrate(p);
1549 }
1550
1551 /*
1552  * Find the nodes on which the workload is actively running. We do this by
1553  * tracking the nodes from which NUMA hinting faults are triggered. This can
1554  * be different from the set of nodes where the workload's memory is currently
1555  * located.
1556  *
1557  * The bitmask is used to make smarter decisions on when to do NUMA page
1558  * migrations, To prevent flip-flopping, and excessive page migrations, nodes
1559  * are added when they cause over 6/16 of the maximum number of faults, but
1560  * only removed when they drop below 3/16.
1561  */
1562 static void update_numa_active_node_mask(struct numa_group *numa_group)
1563 {
1564         unsigned long faults, max_faults = 0;
1565         int nid;
1566
1567         for_each_online_node(nid) {
1568                 faults = group_faults_cpu(numa_group, nid);
1569                 if (faults > max_faults)
1570                         max_faults = faults;
1571         }
1572
1573         for_each_online_node(nid) {
1574                 faults = group_faults_cpu(numa_group, nid);
1575                 if (!node_isset(nid, numa_group->active_nodes)) {
1576                         if (faults > max_faults * 6 / 16)
1577                                 node_set(nid, numa_group->active_nodes);
1578                 } else if (faults < max_faults * 3 / 16)
1579                         node_clear(nid, numa_group->active_nodes);
1580         }
1581 }
1582
1583 /*
1584  * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS
1585  * increments. The more local the fault statistics are, the higher the scan
1586  * period will be for the next scan window. If local/(local+remote) ratio is
1587  * below NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS)
1588  * the scan period will decrease. Aim for 70% local accesses.
1589  */
1590 #define NUMA_PERIOD_SLOTS 10
1591 #define NUMA_PERIOD_THRESHOLD 7
1592
1593 /*
1594  * Increase the scan period (slow down scanning) if the majority of
1595  * our memory is already on our local node, or if the majority of
1596  * the page accesses are shared with other processes.
1597  * Otherwise, decrease the scan period.
1598  */
1599 static void update_task_scan_period(struct task_struct *p,
1600                         unsigned long shared, unsigned long private)
1601 {
1602         unsigned int period_slot;
1603         int ratio;
1604         int diff;
1605
1606         unsigned long remote = p->numa_faults_locality[0];
1607         unsigned long local = p->numa_faults_locality[1];
1608
1609         /*
1610          * If there were no record hinting faults then either the task is
1611          * completely idle or all activity is areas that are not of interest
1612          * to automatic numa balancing. Related to that, if there were failed
1613          * migration then it implies we are migrating too quickly or the local
1614          * node is overloaded. In either case, scan slower
1615          */
1616         if (local + shared == 0 || p->numa_faults_locality[2]) {
1617                 p->numa_scan_period = min(p->numa_scan_period_max,
1618                         p->numa_scan_period << 1);
1619
1620                 p->mm->numa_next_scan = jiffies +
1621                         msecs_to_jiffies(p->numa_scan_period);
1622
1623                 return;
1624         }
1625
1626         /*
1627          * Prepare to scale scan period relative to the current period.
1628          *       == NUMA_PERIOD_THRESHOLD scan period stays the same
1629          *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
1630          *       >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
1631          */
1632         period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
1633         ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
1634         if (ratio >= NUMA_PERIOD_THRESHOLD) {
1635                 int slot = ratio - NUMA_PERIOD_THRESHOLD;
1636                 if (!slot)
1637                         slot = 1;
1638                 diff = slot * period_slot;
1639         } else {
1640                 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
1641
1642                 /*
1643                  * Scale scan rate increases based on sharing. There is an
1644                  * inverse relationship between the degree of sharing and
1645                  * the adjustment made to the scanning period. Broadly
1646                  * speaking the intent is that there is little point
1647                  * scanning faster if shared accesses dominate as it may
1648                  * simply bounce migrations uselessly
1649                  */
1650                 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared + 1));
1651                 diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
1652         }
1653
1654         p->numa_scan_period = clamp(p->numa_scan_period + diff,
1655                         task_scan_min(p), task_scan_max(p));
1656         memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1657 }
1658
1659 /*
1660  * Get the fraction of time the task has been running since the last
1661  * NUMA placement cycle. The scheduler keeps similar statistics, but
1662  * decays those on a 32ms period, which is orders of magnitude off
1663  * from the dozens-of-seconds NUMA balancing period. Use the scheduler
1664  * stats only if the task is so new there are no NUMA statistics yet.
1665  */
1666 static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
1667 {
1668         u64 runtime, delta, now;
1669         /* Use the start of this time slice to avoid calculations. */
1670         now = p->se.exec_start;
1671         runtime = p->se.sum_exec_runtime;
1672
1673         if (p->last_task_numa_placement) {
1674                 delta = runtime - p->last_sum_exec_runtime;
1675                 *period = now - p->last_task_numa_placement;
1676         } else {
1677                 delta = p->se.avg.runnable_avg_sum;
1678                 *period = p->se.avg.runnable_avg_period;
1679         }
1680
1681         p->last_sum_exec_runtime = runtime;
1682         p->last_task_numa_placement = now;
1683
1684         return delta;
1685 }
1686
1687 /*
1688  * Determine the preferred nid for a task in a numa_group. This needs to
1689  * be done in a way that produces consistent results with group_weight,
1690  * otherwise workloads might not converge.
1691  */
1692 static int preferred_group_nid(struct task_struct *p, int nid)
1693 {
1694         nodemask_t nodes;
1695         int dist;
1696
1697         /* Direct connections between all NUMA nodes. */
1698         if (sched_numa_topology_type == NUMA_DIRECT)
1699                 return nid;
1700
1701         /*
1702          * On a system with glueless mesh NUMA topology, group_weight
1703          * scores nodes according to the number of NUMA hinting faults on
1704          * both the node itself, and on nearby nodes.
1705          */
1706         if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
1707                 unsigned long score, max_score = 0;
1708                 int node, max_node = nid;
1709
1710                 dist = sched_max_numa_distance;
1711
1712                 for_each_online_node(node) {
1713                         score = group_weight(p, node, dist);
1714                         if (score > max_score) {
1715                                 max_score = score;
1716                                 max_node = node;
1717                         }
1718                 }
1719                 return max_node;
1720         }
1721
1722         /*
1723          * Finding the preferred nid in a system with NUMA backplane
1724          * interconnect topology is more involved. The goal is to locate
1725          * tasks from numa_groups near each other in the system, and
1726          * untangle workloads from different sides of the system. This requires
1727          * searching down the hierarchy of node groups, recursively searching
1728          * inside the highest scoring group of nodes. The nodemask tricks
1729          * keep the complexity of the search down.
1730          */
1731         nodes = node_online_map;
1732         for (dist = sched_max_numa_distance; dist > LOCAL_DISTANCE; dist--) {
1733                 unsigned long max_faults = 0;
1734                 nodemask_t max_group = NODE_MASK_NONE;
1735                 int a, b;
1736
1737                 /* Are there nodes at this distance from each other? */
1738                 if (!find_numa_distance(dist))
1739                         continue;
1740
1741                 for_each_node_mask(a, nodes) {
1742                         unsigned long faults = 0;
1743                         nodemask_t this_group;
1744                         nodes_clear(this_group);
1745
1746                         /* Sum group's NUMA faults; includes a==b case. */
1747                         for_each_node_mask(b, nodes) {
1748                                 if (node_distance(a, b) < dist) {
1749                                         faults += group_faults(p, b);
1750                                         node_set(b, this_group);
1751                                         node_clear(b, nodes);
1752                                 }
1753                         }
1754
1755                         /* Remember the top group. */
1756                         if (faults > max_faults) {
1757                                 max_faults = faults;
1758                                 max_group = this_group;
1759                                 /*
1760                                  * subtle: at the smallest distance there is
1761                                  * just one node left in each "group", the
1762                                  * winner is the preferred nid.
1763                                  */
1764                                 nid = a;
1765                         }
1766                 }
1767                 /* Next round, evaluate the nodes within max_group. */
1768                 nodes = max_group;
1769         }
1770         return nid;
1771 }
1772
1773 static void task_numa_placement(struct task_struct *p)
1774 {
1775         int seq, nid, max_nid = -1, max_group_nid = -1;
1776         unsigned long max_faults = 0, max_group_faults = 0;
1777         unsigned long fault_types[2] = { 0, 0 };
1778         unsigned long total_faults;
1779         u64 runtime, period;
1780         spinlock_t *group_lock = NULL;
1781
1782         seq = ACCESS_ONCE(p->mm->numa_scan_seq);
1783         if (p->numa_scan_seq == seq)
1784                 return;
1785         p->numa_scan_seq = seq;
1786         p->numa_scan_period_max = task_scan_max(p);
1787
1788         total_faults = p->numa_faults_locality[0] +
1789                        p->numa_faults_locality[1];
1790         runtime = numa_get_avg_runtime(p, &period);
1791
1792         /* If the task is part of a group prevent parallel updates to group stats */
1793         if (p->numa_group) {
1794                 group_lock = &p->numa_group->lock;
1795                 spin_lock_irq(group_lock);
1796         }
1797
1798         /* Find the node with the highest number of faults */
1799         for_each_online_node(nid) {
1800                 /* Keep track of the offsets in numa_faults array */
1801                 int mem_idx, membuf_idx, cpu_idx, cpubuf_idx;
1802                 unsigned long faults = 0, group_faults = 0;
1803                 int priv;
1804
1805                 for (priv = 0; priv < NR_NUMA_HINT_FAULT_TYPES; priv++) {
1806                         long diff, f_diff, f_weight;
1807
1808                         mem_idx = task_faults_idx(NUMA_MEM, nid, priv);
1809                         membuf_idx = task_faults_idx(NUMA_MEMBUF, nid, priv);
1810                         cpu_idx = task_faults_idx(NUMA_CPU, nid, priv);
1811                         cpubuf_idx = task_faults_idx(NUMA_CPUBUF, nid, priv);
1812
1813                         /* Decay existing window, copy faults since last scan */
1814                         diff = p->numa_faults[membuf_idx] - p->numa_faults[mem_idx] / 2;
1815                         fault_types[priv] += p->numa_faults[membuf_idx];
1816                         p->numa_faults[membuf_idx] = 0;
1817
1818                         /*
1819                          * Normalize the faults_from, so all tasks in a group
1820                          * count according to CPU use, instead of by the raw
1821                          * number of faults. Tasks with little runtime have
1822                          * little over-all impact on throughput, and thus their
1823                          * faults are less important.
1824                          */
1825                         f_weight = div64_u64(runtime << 16, period + 1);
1826                         f_weight = (f_weight * p->numa_faults[cpubuf_idx]) /
1827                                    (total_faults + 1);
1828                         f_diff = f_weight - p->numa_faults[cpu_idx] / 2;
1829                         p->numa_faults[cpubuf_idx] = 0;
1830
1831                         p->numa_faults[mem_idx] += diff;
1832                         p->numa_faults[cpu_idx] += f_diff;
1833                         faults += p->numa_faults[mem_idx];
1834                         p->total_numa_faults += diff;
1835                         if (p->numa_group) {
1836                                 /*
1837                                  * safe because we can only change our own group
1838                                  *
1839                                  * mem_idx represents the offset for a given
1840                                  * nid and priv in a specific region because it
1841                                  * is at the beginning of the numa_faults array.
1842                                  */
1843                                 p->numa_group->faults[mem_idx] += diff;
1844                                 p->numa_group->faults_cpu[mem_idx] += f_diff;
1845                                 p->numa_group->total_faults += diff;
1846                                 group_faults += p->numa_group->faults[mem_idx];
1847                         }
1848                 }
1849
1850                 if (faults > max_faults) {
1851                         max_faults = faults;
1852                         max_nid = nid;
1853                 }
1854
1855                 if (group_faults > max_group_faults) {
1856                         max_group_faults = group_faults;
1857                         max_group_nid = nid;
1858                 }
1859         }
1860
1861         update_task_scan_period(p, fault_types[0], fault_types[1]);
1862
1863         if (p->numa_group) {
1864                 update_numa_active_node_mask(p->numa_group);
1865                 spin_unlock_irq(group_lock);
1866                 max_nid = preferred_group_nid(p, max_group_nid);
1867         }
1868
1869         if (max_faults) {
1870                 /* Set the new preferred node */
1871                 if (max_nid != p->numa_preferred_nid)
1872                         sched_setnuma(p, max_nid);
1873
1874                 if (task_node(p) != p->numa_preferred_nid)
1875                         numa_migrate_preferred(p);
1876         }
1877 }
1878
1879 static inline int get_numa_group(struct numa_group *grp)
1880 {
1881         return atomic_inc_not_zero(&grp->refcount);
1882 }
1883
1884 static inline void put_numa_group(struct numa_group *grp)
1885 {
1886         if (atomic_dec_and_test(&grp->refcount))
1887                 kfree_rcu(grp, rcu);
1888 }
1889
1890 static void task_numa_group(struct task_struct *p, int cpupid, int flags,
1891                         int *priv)
1892 {
1893         struct numa_group *grp, *my_grp;
1894         struct task_struct *tsk;
1895         bool join = false;
1896         int cpu = cpupid_to_cpu(cpupid);
1897         int i;
1898
1899         if (unlikely(!p->numa_group)) {
1900                 unsigned int size = sizeof(struct numa_group) +
1901                                     4*nr_node_ids*sizeof(unsigned long);
1902
1903                 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
1904                 if (!grp)
1905                         return;
1906
1907                 atomic_set(&grp->refcount, 1);
1908                 spin_lock_init(&grp->lock);
1909                 grp->gid = p->pid;
1910                 /* Second half of the array tracks nids where faults happen */
1911                 grp->faults_cpu = grp->faults + NR_NUMA_HINT_FAULT_TYPES *
1912                                                 nr_node_ids;
1913
1914                 node_set(task_node(current), grp->active_nodes);
1915
1916                 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
1917                         grp->faults[i] = p->numa_faults[i];
1918
1919                 grp->total_faults = p->total_numa_faults;
1920
1921                 grp->nr_tasks++;
1922                 rcu_assign_pointer(p->numa_group, grp);
1923         }
1924
1925         rcu_read_lock();
1926         tsk = ACCESS_ONCE(cpu_rq(cpu)->curr);
1927
1928         if (!cpupid_match_pid(tsk, cpupid))
1929                 goto no_join;
1930
1931         grp = rcu_dereference(tsk->numa_group);
1932         if (!grp)
1933                 goto no_join;
1934
1935         my_grp = p->numa_group;
1936         if (grp == my_grp)
1937                 goto no_join;
1938
1939         /*
1940          * Only join the other group if its bigger; if we're the bigger group,
1941          * the other task will join us.
1942          */
1943         if (my_grp->nr_tasks > grp->nr_tasks)
1944                 goto no_join;
1945
1946         /*
1947          * Tie-break on the grp address.
1948          */
1949         if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
1950                 goto no_join;
1951
1952         /* Always join threads in the same process. */
1953         if (tsk->mm == current->mm)
1954                 join = true;
1955
1956         /* Simple filter to avoid false positives due to PID collisions */
1957         if (flags & TNF_SHARED)
1958                 join = true;
1959
1960         /* Update priv based on whether false sharing was detected */
1961         *priv = !join;
1962
1963         if (join && !get_numa_group(grp))
1964                 goto no_join;
1965
1966         rcu_read_unlock();
1967
1968         if (!join)
1969                 return;
1970
1971         BUG_ON(irqs_disabled());
1972         double_lock_irq(&my_grp->lock, &grp->lock);
1973
1974         for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++) {
1975                 my_grp->faults[i] -= p->numa_faults[i];
1976                 grp->faults[i] += p->numa_faults[i];
1977         }
1978         my_grp->total_faults -= p->total_numa_faults;
1979         grp->total_faults += p->total_numa_faults;
1980
1981         my_grp->nr_tasks--;
1982         grp->nr_tasks++;
1983
1984         spin_unlock(&my_grp->lock);
1985         spin_unlock_irq(&grp->lock);
1986
1987         rcu_assign_pointer(p->numa_group, grp);
1988
1989         put_numa_group(my_grp);
1990         return;
1991
1992 no_join:
1993         rcu_read_unlock();
1994         return;
1995 }
1996
1997 void task_numa_free(struct task_struct *p)
1998 {
1999         struct numa_group *grp = p->numa_group;
2000         void *numa_faults = p->numa_faults;
2001         unsigned long flags;
2002         int i;
2003
2004         if (grp) {
2005                 spin_lock_irqsave(&grp->lock, flags);
2006                 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
2007                         grp->faults[i] -= p->numa_faults[i];
2008                 grp->total_faults -= p->total_numa_faults;
2009
2010                 grp->nr_tasks--;
2011                 spin_unlock_irqrestore(&grp->lock, flags);
2012                 RCU_INIT_POINTER(p->numa_group, NULL);
2013                 put_numa_group(grp);
2014         }
2015
2016         p->numa_faults = NULL;
2017         kfree(numa_faults);
2018 }
2019
2020 /*
2021  * Got a PROT_NONE fault for a page on @node.
2022  */
2023 void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
2024 {
2025         struct task_struct *p = current;
2026         bool migrated = flags & TNF_MIGRATED;
2027         int cpu_node = task_node(current);
2028         int local = !!(flags & TNF_FAULT_LOCAL);
2029         int priv;
2030
2031         if (!numabalancing_enabled)
2032                 return;
2033
2034         /* for example, ksmd faulting in a user's mm */
2035         if (!p->mm)
2036                 return;
2037
2038         /* Allocate buffer to track faults on a per-node basis */
2039         if (unlikely(!p->numa_faults)) {
2040                 int size = sizeof(*p->numa_faults) *
2041                            NR_NUMA_HINT_FAULT_BUCKETS * nr_node_ids;
2042
2043                 p->numa_faults = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);
2044                 if (!p->numa_faults)
2045                         return;
2046
2047                 p->total_numa_faults = 0;
2048                 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
2049         }
2050
2051         /*
2052          * First accesses are treated as private, otherwise consider accesses
2053          * to be private if the accessing pid has not changed
2054          */
2055         if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
2056                 priv = 1;
2057         } else {
2058                 priv = cpupid_match_pid(p, last_cpupid);
2059                 if (!priv && !(flags & TNF_NO_GROUP))
2060                         task_numa_group(p, last_cpupid, flags, &priv);
2061         }
2062
2063         /*
2064          * If a workload spans multiple NUMA nodes, a shared fault that
2065          * occurs wholly within the set of nodes that the workload is
2066          * actively using should be counted as local. This allows the
2067          * scan rate to slow down when a workload has settled down.
2068          */
2069         if (!priv && !local && p->numa_group &&
2070                         node_isset(cpu_node, p->numa_group->active_nodes) &&
2071                         node_isset(mem_node, p->numa_group->active_nodes))
2072                 local = 1;
2073
2074         task_numa_placement(p);
2075
2076         /*
2077          * Retry task to preferred node migration periodically, in case it
2078          * case it previously failed, or the scheduler moved us.
2079          */
2080         if (time_after(jiffies, p->numa_migrate_retry))
2081                 numa_migrate_preferred(p);
2082
2083         if (migrated)
2084                 p->numa_pages_migrated += pages;
2085         if (flags & TNF_MIGRATE_FAIL)
2086                 p->numa_faults_locality[2] += pages;
2087
2088         p->numa_faults[task_faults_idx(NUMA_MEMBUF, mem_node, priv)] += pages;
2089         p->numa_faults[task_faults_idx(NUMA_CPUBUF, cpu_node, priv)] += pages;
2090         p->numa_faults_locality[local] += pages;
2091 }
2092
2093 static void reset_ptenuma_scan(struct task_struct *p)
2094 {
2095         ACCESS_ONCE(p->mm->numa_scan_seq)++;
2096         p->mm->numa_scan_offset = 0;
2097 }
2098
2099 /*
2100  * The expensive part of numa migration is done from task_work context.
2101  * Triggered from task_tick_numa().
2102  */
2103 void task_numa_work(struct callback_head *work)
2104 {
2105         unsigned long migrate, next_scan, now = jiffies;
2106         struct task_struct *p = current;
2107         struct mm_struct *mm = p->mm;
2108         struct vm_area_struct *vma;
2109         unsigned long start, end;
2110         unsigned long nr_pte_updates = 0;
2111         long pages;
2112
2113         WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work));
2114
2115         work->next = work; /* protect against double add */
2116         /*
2117          * Who cares about NUMA placement when they're dying.
2118          *
2119          * NOTE: make sure not to dereference p->mm before this check,
2120          * exit_task_work() happens _after_ exit_mm() so we could be called
2121          * without p->mm even though we still had it when we enqueued this
2122          * work.
2123          */
2124         if (p->flags & PF_EXITING)
2125                 return;
2126
2127         if (!mm->numa_next_scan) {
2128                 mm->numa_next_scan = now +
2129                         msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
2130         }
2131
2132         /*
2133          * Enforce maximal scan/migration frequency..
2134          */
2135         migrate = mm->numa_next_scan;
2136         if (time_before(now, migrate))
2137                 return;
2138
2139         if (p->numa_scan_period == 0) {
2140                 p->numa_scan_period_max = task_scan_max(p);
2141                 p->numa_scan_period = task_scan_min(p);
2142         }
2143
2144         next_scan = now + msecs_to_jiffies(p->numa_scan_period);
2145         if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
2146                 return;
2147
2148         /*
2149          * Delay this task enough that another task of this mm will likely win
2150          * the next time around.
2151          */
2152         p->node_stamp += 2 * TICK_NSEC;
2153
2154         start = mm->numa_scan_offset;
2155         pages = sysctl_numa_balancing_scan_size;
2156         pages <<= 20 - PAGE_SHIFT; /* MB in pages */
2157         if (!pages)
2158                 return;
2159
2160         down_read(&mm->mmap_sem);
2161         vma = find_vma(mm, start);
2162         if (!vma) {
2163                 reset_ptenuma_scan(p);
2164                 start = 0;
2165                 vma = mm->mmap;
2166         }
2167         for (; vma; vma = vma->vm_next) {
2168                 if (!vma_migratable(vma) || !vma_policy_mof(vma) ||
2169                         is_vm_hugetlb_page(vma)) {
2170                         continue;
2171                 }
2172
2173                 /*
2174                  * Shared library pages mapped by multiple processes are not
2175                  * migrated as it is expected they are cache replicated. Avoid
2176                  * hinting faults in read-only file-backed mappings or the vdso
2177                  * as migrating the pages will be of marginal benefit.
2178                  */
2179                 if (!vma->vm_mm ||
2180                     (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
2181                         continue;
2182
2183                 /*
2184                  * Skip inaccessible VMAs to avoid any confusion between
2185                  * PROT_NONE and NUMA hinting ptes
2186                  */
2187                 if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
2188                         continue;
2189
2190                 do {
2191                         start = max(start, vma->vm_start);
2192                         end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
2193                         end = min(end, vma->vm_end);
2194                         nr_pte_updates += change_prot_numa(vma, start, end);
2195
2196                         /*
2197                          * Scan sysctl_numa_balancing_scan_size but ensure that
2198                          * at least one PTE is updated so that unused virtual
2199                          * address space is quickly skipped.
2200                          */
2201                         if (nr_pte_updates)
2202                                 pages -= (end - start) >> PAGE_SHIFT;
2203
2204                         start = end;
2205                         if (pages <= 0)
2206                                 goto out;
2207
2208                         cond_resched();
2209                 } while (end != vma->vm_end);
2210         }
2211
2212 out:
2213         /*
2214          * It is possible to reach the end of the VMA list but the last few
2215          * VMAs are not guaranteed to the vma_migratable. If they are not, we
2216          * would find the !migratable VMA on the next scan but not reset the
2217          * scanner to the start so check it now.
2218          */
2219         if (vma)
2220                 mm->numa_scan_offset = start;
2221         else
2222                 reset_ptenuma_scan(p);
2223         up_read(&mm->mmap_sem);
2224 }
2225
2226 /*
2227  * Drive the periodic memory faults..
2228  */
2229 void task_tick_numa(struct rq *rq, struct task_struct *curr)
2230 {
2231         struct callback_head *work = &curr->numa_work;
2232         u64 period, now;
2233
2234         /*
2235          * We don't care about NUMA placement if we don't have memory.
2236          */
2237         if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
2238                 return;
2239
2240         /*
2241          * Using runtime rather than walltime has the dual advantage that
2242          * we (mostly) drive the selection from busy threads and that the
2243          * task needs to have done some actual work before we bother with
2244          * NUMA placement.
2245          */
2246         now = curr->se.sum_exec_runtime;
2247         period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
2248
2249         if (now - curr->node_stamp > period) {
2250                 if (!curr->node_stamp)
2251                         curr->numa_scan_period = task_scan_min(curr);
2252                 curr->node_stamp += period;
2253
2254                 if (!time_before(jiffies, curr->mm->numa_next_scan)) {
2255                         init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */
2256                         task_work_add(curr, work, true);
2257                 }
2258         }
2259 }
2260 #else
2261 static void task_tick_numa(struct rq *rq, struct task_struct *curr)
2262 {
2263 }
2264
2265 static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
2266 {
2267 }
2268
2269 static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
2270 {
2271 }
2272 #endif /* CONFIG_NUMA_BALANCING */
2273
2274 static void
2275 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2276 {
2277         update_load_add(&cfs_rq->load, se->load.weight);
2278         if (!parent_entity(se))
2279                 update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
2280 #ifdef CONFIG_SMP
2281         if (entity_is_task(se)) {
2282                 struct rq *rq = rq_of(cfs_rq);
2283
2284                 account_numa_enqueue(rq, task_of(se));
2285                 list_add(&se->group_node, &rq->cfs_tasks);
2286         }
2287 #endif
2288         cfs_rq->nr_running++;
2289 }
2290
2291 static void
2292 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2293 {
2294         update_load_sub(&cfs_rq->load, se->load.weight);
2295         if (!parent_entity(se))
2296                 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
2297         if (entity_is_task(se)) {
2298                 account_numa_dequeue(rq_of(cfs_rq), task_of(se));
2299                 list_del_init(&se->group_node);
2300         }
2301         cfs_rq->nr_running--;
2302 }
2303
2304 #ifdef CONFIG_FAIR_GROUP_SCHED
2305 # ifdef CONFIG_SMP
2306 static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
2307 {
2308         long tg_weight;
2309
2310         /*
2311          * Use this CPU's actual weight instead of the last load_contribution
2312          * to gain a more accurate current total weight. See
2313          * update_cfs_rq_load_contribution().
2314          */
2315         tg_weight = atomic_long_read(&tg->load_avg);
2316         tg_weight -= cfs_rq->tg_load_contrib;
2317         tg_weight += cfs_rq->load.weight;
2318
2319         return tg_weight;
2320 }
2321
2322 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2323 {
2324         long tg_weight, load, shares;
2325
2326         tg_weight = calc_tg_weight(tg, cfs_rq);
2327         load = cfs_rq->load.weight;
2328
2329         shares = (tg->shares * load);
2330         if (tg_weight)
2331                 shares /= tg_weight;
2332
2333         if (shares < MIN_SHARES)
2334                 shares = MIN_SHARES;
2335         if (shares > tg->shares)
2336                 shares = tg->shares;
2337
2338         return shares;
2339 }
2340 # else /* CONFIG_SMP */
2341 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2342 {
2343         return tg->shares;
2344 }
2345 # endif /* CONFIG_SMP */
2346 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
2347                             unsigned long weight)
2348 {
2349         if (se->on_rq) {
2350                 /* commit outstanding execution time */
2351                 if (cfs_rq->curr == se)
2352                         update_curr(cfs_rq);
2353                 account_entity_dequeue(cfs_rq, se);
2354         }
2355
2356         update_load_set(&se->load, weight);
2357
2358         if (se->on_rq)
2359                 account_entity_enqueue(cfs_rq, se);
2360 }
2361
2362 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
2363
2364 static void update_cfs_shares(struct cfs_rq *cfs_rq)
2365 {
2366         struct task_group *tg;
2367         struct sched_entity *se;
2368         long shares;
2369
2370         tg = cfs_rq->tg;
2371         se = tg->se[cpu_of(rq_of(cfs_rq))];
2372         if (!se || throttled_hierarchy(cfs_rq))
2373                 return;
2374 #ifndef CONFIG_SMP
2375         if (likely(se->load.weight == tg->shares))
2376                 return;
2377 #endif
2378         shares = calc_cfs_shares(cfs_rq, tg);
2379
2380         reweight_entity(cfs_rq_of(se), se, shares);
2381 }
2382 #else /* CONFIG_FAIR_GROUP_SCHED */
2383 static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
2384 {
2385 }
2386 #endif /* CONFIG_FAIR_GROUP_SCHED */
2387
2388 #ifdef CONFIG_SMP
2389 /*
2390  * We choose a half-life close to 1 scheduling period.
2391  * Note: The tables below are dependent on this value.
2392  */
2393 #define LOAD_AVG_PERIOD 32
2394 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
2395 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */
2396
2397 /* Precomputed fixed inverse multiplies for multiplication by y^n */
2398 static const u32 runnable_avg_yN_inv[] = {
2399         0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
2400         0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
2401         0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
2402         0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
2403         0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
2404         0x85aac367, 0x82cd8698,
2405 };
2406
2407 /*
2408  * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
2409  * over-estimates when re-combining.
2410  */
2411 static const u32 runnable_avg_yN_sum[] = {
2412             0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
2413          9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
2414         17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
2415 };
2416
2417 /*
2418  * Approximate:
2419  *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
2420  */
2421 static __always_inline u64 decay_load(u64 val, u64 n)
2422 {
2423         unsigned int local_n;
2424
2425         if (!n)
2426                 return val;
2427         else if (unlikely(n > LOAD_AVG_PERIOD * 63))
2428                 return 0;
2429
2430         /* after bounds checking we can collapse to 32-bit */
2431         local_n = n;
2432
2433         /*
2434          * As y^PERIOD = 1/2, we can combine
2435          *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
2436          * With a look-up table which covers y^n (n<PERIOD)
2437          *
2438          * To achieve constant time decay_load.
2439          */
2440         if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
2441                 val >>= local_n / LOAD_AVG_PERIOD;
2442                 local_n %= LOAD_AVG_PERIOD;
2443         }
2444
2445         val *= runnable_avg_yN_inv[local_n];
2446         /* We don't use SRR here since we always want to round down. */
2447         return val >> 32;
2448 }
2449
2450 /*
2451  * For updates fully spanning n periods, the contribution to runnable
2452  * average will be: \Sum 1024*y^n
2453  *
2454  * We can compute this reasonably efficiently by combining:
2455  *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
2456  */
2457 static u32 __compute_runnable_contrib(u64 n)
2458 {
2459         u32 contrib = 0;
2460
2461         if (likely(n <= LOAD_AVG_PERIOD))
2462                 return runnable_avg_yN_sum[n];
2463         else if (unlikely(n >= LOAD_AVG_MAX_N))
2464                 return LOAD_AVG_MAX;
2465
2466         /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
2467         do {
2468                 contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
2469                 contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
2470
2471                 n -= LOAD_AVG_PERIOD;
2472         } while (n > LOAD_AVG_PERIOD);
2473
2474         contrib = decay_load(contrib, n);
2475         return contrib + runnable_avg_yN_sum[n];
2476 }
2477
2478 /*
2479  * We can represent the historical contribution to runnable average as the
2480  * coefficients of a geometric series.  To do this we sub-divide our runnable
2481  * history into segments of approximately 1ms (1024us); label the segment that
2482  * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
2483  *
2484  * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
2485  *      p0            p1           p2
2486  *     (now)       (~1ms ago)  (~2ms ago)
2487  *
2488  * Let u_i denote the fraction of p_i that the entity was runnable.
2489  *
2490  * We then designate the fractions u_i as our co-efficients, yielding the
2491  * following representation of historical load:
2492  *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
2493  *
2494  * We choose y based on the with of a reasonably scheduling period, fixing:
2495  *   y^32 = 0.5
2496  *
2497  * This means that the contribution to load ~32ms ago (u_32) will be weighted
2498  * approximately half as much as the contribution to load within the last ms
2499  * (u_0).
2500  *
2501  * When a period "rolls over" and we have new u_0`, multiplying the previous
2502  * sum again by y is sufficient to update:
2503  *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
2504  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
2505  */
2506 static __always_inline int __update_entity_runnable_avg(u64 now,
2507                                                         struct sched_avg *sa,
2508                                                         int runnable)
2509 {
2510         u64 delta, periods;
2511         u32 runnable_contrib;
2512         int delta_w, decayed = 0;
2513
2514         delta = now - sa->last_runnable_update;
2515         /*
2516          * This should only happen when time goes backwards, which it
2517          * unfortunately does during sched clock init when we swap over to TSC.
2518          */
2519         if ((s64)delta < 0) {
2520                 sa->last_runnable_update = now;
2521                 return 0;
2522         }
2523
2524         /*
2525          * Use 1024ns as the unit of measurement since it's a reasonable
2526          * approximation of 1us and fast to compute.
2527          */
2528         delta >>= 10;
2529         if (!delta)
2530                 return 0;
2531         sa->last_runnable_update = now;
2532
2533         /* delta_w is the amount already accumulated against our next period */
2534         delta_w = sa->runnable_avg_period % 1024;
2535         if (delta + delta_w >= 1024) {
2536                 /* period roll-over */
2537                 decayed = 1;
2538
2539                 /*
2540                  * Now that we know we're crossing a period boundary, figure
2541                  * out how much from delta we need to complete the current
2542                  * period and accrue it.
2543                  */
2544                 delta_w = 1024 - delta_w;
2545                 if (runnable)
2546                         sa->runnable_avg_sum += delta_w;
2547                 sa->runnable_avg_period += delta_w;
2548
2549                 delta -= delta_w;
2550
2551                 /* Figure out how many additional periods this update spans */
2552                 periods = delta / 1024;
2553                 delta %= 1024;
2554
2555                 sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
2556                                                   periods + 1);
2557                 sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
2558                                                      periods + 1);
2559
2560                 /* Efficiently calculate \sum (1..n_period) 1024*y^i */
2561                 runnable_contrib = __compute_runnable_contrib(periods);
2562                 if (runnable)
2563                         sa->runnable_avg_sum += runnable_contrib;
2564                 sa->runnable_avg_period += runnable_contrib;
2565         }
2566
2567         /* Remainder of delta accrued against u_0` */
2568         if (runnable)
2569                 sa->runnable_avg_sum += delta;
2570         sa->runnable_avg_period += delta;
2571
2572         return decayed;
2573 }
2574
2575 /* Synchronize an entity's decay with its parenting cfs_rq.*/
2576 static inline u64 __synchronize_entity_decay(struct sched_entity *se)
2577 {
2578         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2579         u64 decays = atomic64_read(&cfs_rq->decay_counter);
2580
2581         decays -= se->avg.decay_count;
2582         se->avg.decay_count = 0;
2583         if (!decays)
2584                 return 0;
2585
2586         se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);
2587
2588         return decays;
2589 }
2590
2591 #ifdef CONFIG_FAIR_GROUP_SCHED
2592 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2593                                                  int force_update)
2594 {
2595         struct task_group *tg = cfs_rq->tg;
2596         long tg_contrib;
2597
2598         tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
2599         tg_contrib -= cfs_rq->tg_load_contrib;
2600
2601         if (!tg_contrib)
2602                 return;
2603
2604         if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
2605                 atomic_long_add(tg_contrib, &tg->load_avg);
2606                 cfs_rq->tg_load_contrib += tg_contrib;
2607         }
2608 }
2609
2610 /*
2611  * Aggregate cfs_rq runnable averages into an equivalent task_group
2612  * representation for computing load contributions.
2613  */
2614 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2615                                                   struct cfs_rq *cfs_rq)
2616 {
2617         struct task_group *tg = cfs_rq->tg;
2618         long contrib;
2619
2620         /* The fraction of a cpu used by this cfs_rq */
2621         contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
2622                           sa->runnable_avg_period + 1);
2623         contrib -= cfs_rq->tg_runnable_contrib;
2624
2625         if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
2626                 atomic_add(contrib, &tg->runnable_avg);
2627                 cfs_rq->tg_runnable_contrib += contrib;
2628         }
2629 }
2630
2631 static inline void __update_group_entity_contrib(struct sched_entity *se)
2632 {
2633         struct cfs_rq *cfs_rq = group_cfs_rq(se);
2634         struct task_group *tg = cfs_rq->tg;
2635         int runnable_avg;
2636
2637         u64 contrib;
2638
2639         contrib = cfs_rq->tg_load_contrib * tg->shares;
2640         se->avg.load_avg_contrib = div_u64(contrib,
2641                                      atomic_long_read(&tg->load_avg) + 1);
2642
2643         /*
2644          * For group entities we need to compute a correction term in the case
2645          * that they are consuming <1 cpu so that we would contribute the same
2646          * load as a task of equal weight.
2647          *
2648          * Explicitly co-ordinating this measurement would be expensive, but
2649          * fortunately the sum of each cpus contribution forms a usable
2650          * lower-bound on the true value.
2651          *
2652          * Consider the aggregate of 2 contributions.  Either they are disjoint
2653          * (and the sum represents true value) or they are disjoint and we are
2654          * understating by the aggregate of their overlap.
2655          *
2656          * Extending this to N cpus, for a given overlap, the maximum amount we
2657          * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of
2658          * cpus that overlap for this interval and w_i is the interval width.
2659          *
2660          * On a small machine; the first term is well-bounded which bounds the
2661          * total error since w_i is a subset of the period.  Whereas on a
2662          * larger machine, while this first term can be larger, if w_i is the
2663          * of consequential size guaranteed to see n_i*w_i quickly converge to
2664          * our upper bound of 1-cpu.
2665          */
2666         runnable_avg = atomic_read(&tg->runnable_avg);
2667         if (runnable_avg < NICE_0_LOAD) {
2668                 se->avg.load_avg_contrib *= runnable_avg;
2669                 se->avg.load_avg_contrib >>= NICE_0_SHIFT;
2670         }
2671 }
2672
2673 static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
2674 {
2675         __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
2676         __update_tg_runnable_avg(&rq->avg, &rq->cfs);
2677 }
2678 #else /* CONFIG_FAIR_GROUP_SCHED */
2679 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2680                                                  int force_update) {}
2681 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2682                                                   struct cfs_rq *cfs_rq) {}
2683 static inline void __update_group_entity_contrib(struct sched_entity *se) {}
2684 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2685 #endif /* CONFIG_FAIR_GROUP_SCHED */
2686
2687 static inline void __update_task_entity_contrib(struct sched_entity *se)
2688 {
2689         u32 contrib;
2690
2691         /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
2692         contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
2693         contrib /= (se->avg.runnable_avg_period + 1);
2694         se->avg.load_avg_contrib = scale_load(contrib);
2695 }
2696
2697 /* Compute the current contribution to load_avg by se, return any delta */
2698 static long __update_entity_load_avg_contrib(struct sched_entity *se)
2699 {
2700         long old_contrib = se->avg.load_avg_contrib;
2701
2702         if (entity_is_task(se)) {
2703                 __update_task_entity_contrib(se);
2704         } else {
2705                 __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
2706                 __update_group_entity_contrib(se);
2707         }
2708
2709         return se->avg.load_avg_contrib - old_contrib;
2710 }
2711
2712 static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
2713                                                  long load_contrib)
2714 {
2715         if (likely(load_contrib < cfs_rq->blocked_load_avg))
2716                 cfs_rq->blocked_load_avg -= load_contrib;
2717         else
2718                 cfs_rq->blocked_load_avg = 0;
2719 }
2720
2721 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
2722
2723 /* Update a sched_entity's runnable average */
2724 static inline void update_entity_load_avg(struct sched_entity *se,
2725                                           int update_cfs_rq)
2726 {
2727         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2728         long contrib_delta;
2729         u64 now;
2730
2731         /*
2732          * For a group entity we need to use their owned cfs_rq_clock_task() in
2733          * case they are the parent of a throttled hierarchy.
2734          */
2735         if (entity_is_task(se))
2736                 now = cfs_rq_clock_task(cfs_rq);
2737         else
2738                 now = cfs_rq_clock_task(group_cfs_rq(se));
2739
2740         if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
2741                 return;
2742
2743         contrib_delta = __update_entity_load_avg_contrib(se);
2744
2745         if (!update_cfs_rq)
2746                 return;
2747
2748         if (se->on_rq)
2749                 cfs_rq->runnable_load_avg += contrib_delta;
2750         else
2751                 subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
2752 }
2753
2754 /*
2755  * Decay the load contributed by all blocked children and account this so that
2756  * their contribution may appropriately discounted when they wake up.
2757  */
2758 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
2759 {
2760         u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
2761         u64 decays;
2762
2763         decays = now - cfs_rq->last_decay;
2764         if (!decays && !force_update)
2765                 return;
2766
2767         if (atomic_long_read(&cfs_rq->removed_load)) {
2768                 unsigned long removed_load;
2769                 removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
2770                 subtract_blocked_load_contrib(cfs_rq, removed_load);
2771         }
2772
2773         if (decays) {
2774                 cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
2775                                                       decays);
2776                 atomic64_add(decays, &cfs_rq->decay_counter);
2777                 cfs_rq->last_decay = now;
2778         }
2779
2780         __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
2781 }
2782
2783 /* Add the load generated by se into cfs_rq's child load-average */
2784 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2785                                                   struct sched_entity *se,
2786                                                   int wakeup)
2787 {
2788         /*
2789          * We track migrations using entity decay_count <= 0, on a wake-up
2790          * migration we use a negative decay count to track the remote decays
2791          * accumulated while sleeping.
2792          *
2793          * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
2794          * are seen by enqueue_entity_load_avg() as a migration with an already
2795          * constructed load_avg_contrib.
2796          */
2797         if (unlikely(se->avg.decay_count <= 0)) {
2798                 se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
2799                 if (se->avg.decay_count) {
2800                         /*
2801                          * In a wake-up migration we have to approximate the
2802                          * time sleeping.  This is because we can't synchronize
2803                          * clock_task between the two cpus, and it is not
2804                          * guaranteed to be read-safe.  Instead, we can
2805                          * approximate this using our carried decays, which are
2806                          * explicitly atomically readable.
2807                          */
2808                         se->avg.last_runnable_update -= (-se->avg.decay_count)
2809                                                         << 20;
2810                         update_entity_load_avg(se, 0);
2811                         /* Indicate that we're now synchronized and on-rq */
2812                         se->avg.decay_count = 0;
2813                 }
2814                 wakeup = 0;
2815         } else {
2816                 __synchronize_entity_decay(se);
2817         }
2818
2819         /* migrated tasks did not contribute to our blocked load */
2820         if (wakeup) {
2821                 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
2822                 update_entity_load_avg(se, 0);
2823         }
2824
2825         cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
2826         /* we force update consideration on load-balancer moves */
2827         update_cfs_rq_blocked_load(cfs_rq, !wakeup);
2828 }
2829
2830 /*
2831  * Remove se's load from this cfs_rq child load-average, if the entity is
2832  * transitioning to a blocked state we track its projected decay using
2833  * blocked_load_avg.
2834  */
2835 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2836                                                   struct sched_entity *se,
2837                                                   int sleep)
2838 {
2839         update_entity_load_avg(se, 1);
2840         /* we force update consideration on load-balancer moves */
2841         update_cfs_rq_blocked_load(cfs_rq, !sleep);
2842
2843         cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
2844         if (sleep) {
2845                 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
2846                 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
2847         } /* migrations, e.g. sleep=0 leave decay_count == 0 */
2848 }
2849
2850 /*
2851  * Update the rq's load with the elapsed running time before entering
2852  * idle. if the last scheduled task is not a CFS task, idle_enter will
2853  * be the only way to update the runnable statistic.
2854  */
2855 void idle_enter_fair(struct rq *this_rq)
2856 {
2857         update_rq_runnable_avg(this_rq, 1);
2858 }
2859
2860 /*
2861  * Update the rq's load with the elapsed idle time before a task is
2862  * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
2863  * be the only way to update the runnable statistic.
2864  */
2865 void idle_exit_fair(struct rq *this_rq)
2866 {
2867         update_rq_runnable_avg(this_rq, 0);
2868 }
2869
2870 static int idle_balance(struct rq *this_rq);
2871
2872 #else /* CONFIG_SMP */
2873
2874 static inline void update_entity_load_avg(struct sched_entity *se,
2875                                           int update_cfs_rq) {}
2876 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2877 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2878                                            struct sched_entity *se,
2879                                            int wakeup) {}
2880 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2881                                            struct sched_entity *se,
2882                                            int sleep) {}
2883 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
2884                                               int force_update) {}
2885
2886 static inline int idle_balance(struct rq *rq)
2887 {
2888         return 0;
2889 }
2890
2891 #endif /* CONFIG_SMP */
2892
2893 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
2894 {
2895 #ifdef CONFIG_SCHEDSTATS
2896         struct task_struct *tsk = NULL;
2897
2898         if (entity_is_task(se))
2899                 tsk = task_of(se);
2900
2901         if (se->statistics.sleep_start) {
2902                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.sleep_start;
2903
2904                 if ((s64)delta < 0)
2905                         delta = 0;
2906
2907                 if (unlikely(delta > se->statistics.sleep_max))
2908                         se->statistics.sleep_max = delta;
2909
2910                 se->statistics.sleep_start = 0;
2911                 se->statistics.sum_sleep_runtime += delta;
2912
2913                 if (tsk) {
2914                         account_scheduler_latency(tsk, delta >> 10, 1);
2915                         trace_sched_stat_sleep(tsk, delta);
2916                 }
2917         }
2918         if (se->statistics.block_start) {
2919                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.block_start;
2920
2921                 if ((s64)delta < 0)
2922                         delta = 0;
2923
2924                 if (unlikely(delta > se->statistics.block_max))
2925                         se->statistics.block_max = delta;
2926
2927                 se->statistics.block_start = 0;
2928                 se->statistics.sum_sleep_runtime += delta;
2929
2930                 if (tsk) {
2931                         if (tsk->in_iowait) {
2932                                 se->statistics.iowait_sum += delta;
2933                                 se->statistics.iowait_count++;
2934                                 trace_sched_stat_iowait(tsk, delta);
2935                         }
2936
2937                         trace_sched_stat_blocked(tsk, delta);
2938
2939                         /*
2940                          * Blocking time is in units of nanosecs, so shift by
2941                          * 20 to get a milliseconds-range estimation of the
2942                          * amount of time that the task spent sleeping:
2943                          */
2944                         if (unlikely(prof_on == SLEEP_PROFILING)) {
2945                                 profile_hits(SLEEP_PROFILING,
2946                                                 (void *)get_wchan(tsk),
2947                                                 delta >> 20);
2948                         }
2949                         account_scheduler_latency(tsk, delta >> 10, 0);
2950                 }
2951         }
2952 #endif
2953 }
2954
2955 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
2956 {
2957 #ifdef CONFIG_SCHED_DEBUG
2958         s64 d = se->vruntime - cfs_rq->min_vruntime;
2959
2960         if (d < 0)
2961                 d = -d;
2962
2963         if (d > 3*sysctl_sched_latency)
2964                 schedstat_inc(cfs_rq, nr_spread_over);
2965 #endif
2966 }
2967
2968 static void
2969 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
2970 {
2971         u64 vruntime = cfs_rq->min_vruntime;
2972
2973         /*
2974          * The 'current' period is already promised to the current tasks,
2975          * however the extra weight of the new task will slow them down a
2976          * little, place the new task so that it fits in the slot that
2977          * stays open at the end.
2978          */
2979         if (initial && sched_feat(START_DEBIT))
2980                 vruntime += sched_vslice(cfs_rq, se);
2981
2982         /* sleeps up to a single latency don't count. */
2983         if (!initial) {
2984                 unsigned long thresh = sysctl_sched_latency;
2985
2986                 /*
2987                  * Halve their sleep time's effect, to allow
2988                  * for a gentler effect of sleepers:
2989                  */
2990                 if (sched_feat(GENTLE_FAIR_SLEEPERS))
2991                         thresh >>= 1;
2992
2993                 vruntime -= thresh;
2994         }
2995
2996         /* ensure we never gain time by being placed backwards. */
2997         se->vruntime = max_vruntime(se->vruntime, vruntime);
2998 }
2999
3000 static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
3001
3002 static void
3003 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
3004 {
3005         /*
3006          * Update the normalized vruntime before updating min_vruntime
3007          * through calling update_curr().
3008          */
3009         if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
3010                 se->vruntime += cfs_rq->min_vruntime;
3011
3012         /*
3013          * Update run-time statistics of the 'current'.
3014          */
3015         update_curr(cfs_rq);
3016         enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
3017         account_entity_enqueue(cfs_rq, se);
3018         update_cfs_shares(cfs_rq);
3019
3020         if (flags & ENQUEUE_WAKEUP) {
3021                 place_entity(cfs_rq, se, 0);
3022                 enqueue_sleeper(cfs_rq, se);
3023         }
3024
3025         update_stats_enqueue(cfs_rq, se);
3026         check_spread(cfs_rq, se);
3027         if (se != cfs_rq->curr)
3028                 __enqueue_entity(cfs_rq, se);
3029         se->on_rq = 1;
3030
3031         if (cfs_rq->nr_running == 1) {
3032                 list_add_leaf_cfs_rq(cfs_rq);
3033                 check_enqueue_throttle(cfs_rq);
3034         }
3035 }
3036
3037 static void __clear_buddies_last(struct sched_entity *se)
3038 {
3039         for_each_sched_entity(se) {
3040                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
3041                 if (cfs_rq->last != se)
3042                         break;
3043
3044                 cfs_rq->last = NULL;
3045         }
3046 }
3047
3048 static void __clear_buddies_next(struct sched_entity *se)
3049 {
3050         for_each_sched_entity(se) {
3051                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
3052                 if (cfs_rq->next != se)
3053                         break;
3054
3055                 cfs_rq->next = NULL;
3056         }
3057 }
3058
3059 static void __clear_buddies_skip(struct sched_entity *se)
3060 {
3061         for_each_sched_entity(se) {
3062                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
3063                 if (cfs_rq->skip != se)
3064                         break;
3065
3066                 cfs_rq->skip = NULL;
3067         }
3068 }
3069
3070 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
3071 {
3072         if (cfs_rq->last == se)
3073                 __clear_buddies_last(se);
3074
3075         if (cfs_rq->next == se)
3076                 __clear_buddies_next(se);
3077
3078         if (cfs_rq->skip == se)
3079                 __clear_buddies_skip(se);
3080 }
3081
3082 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
3083
3084 static void
3085 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
3086 {
3087         /*
3088          * Update run-time statistics of the 'current'.
3089          */
3090         update_curr(cfs_rq);
3091         dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP);
3092
3093         update_stats_dequeue(cfs_rq, se);
3094         if (flags & DEQUEUE_SLEEP) {
3095 #ifdef CONFIG_SCHEDSTATS
3096                 if (entity_is_task(se)) {
3097                         struct task_struct *tsk = task_of(se);
3098
3099                         if (tsk->state & TASK_INTERRUPTIBLE)
3100                                 se->statistics.sleep_start = rq_clock(rq_of(cfs_rq));
3101                         if (tsk->state & TASK_UNINTERRUPTIBLE)
3102                                 se->statistics.block_start = rq_clock(rq_of(cfs_rq));
3103                 }
3104 #endif
3105         }
3106
3107         clear_buddies(cfs_rq, se);
3108
3109         if (se != cfs_rq->curr)
3110                 __dequeue_entity(cfs_rq, se);
3111         se->on_rq = 0;
3112         account_entity_dequeue(cfs_rq, se);
3113
3114         /*
3115          * Normalize the entity after updating the min_vruntime because the
3116          * update can refer to the ->curr item and we need to reflect this
3117          * movement in our normalized position.
3118          */
3119         if (!(flags & DEQUEUE_SLEEP))
3120                 se->vruntime -= cfs_rq->min_vruntime;
3121
3122         /* return excess runtime on last dequeue */
3123         return_cfs_rq_runtime(cfs_rq);
3124
3125         update_min_vruntime(cfs_rq);
3126         update_cfs_shares(cfs_rq);
3127 }
3128
3129 /*
3130  * Preempt the current task with a newly woken task if needed:
3131  */
3132 static void
3133 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
3134 {
3135         unsigned long ideal_runtime, delta_exec;
3136         struct sched_entity *se;
3137         s64 delta;
3138
3139         ideal_runtime = sched_slice(cfs_rq, curr);
3140         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
3141         if (delta_exec > ideal_runtime) {
3142                 resched_curr(rq_of(cfs_rq));
3143                 /*
3144                  * The current task ran long enough, ensure it doesn't get
3145                  * re-elected due to buddy favours.
3146                  */
3147                 clear_buddies(cfs_rq, curr);
3148                 return;
3149         }
3150
3151         /*
3152          * Ensure that a task that missed wakeup preemption by a
3153          * narrow margin doesn't have to wait for a full slice.
3154          * This also mitigates buddy induced latencies under load.
3155          */
3156         if (delta_exec < sysctl_sched_min_granularity)
3157                 return;
3158
3159         se = __pick_first_entity(cfs_rq);
3160         delta = curr->vruntime - se->vruntime;
3161
3162         if (delta < 0)
3163                 return;
3164
3165         if (delta > ideal_runtime)
3166                 resched_curr(rq_of(cfs_rq));
3167 }
3168
3169 static void
3170 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
3171 {
3172         /* 'current' is not kept within the tree. */
3173         if (se->on_rq) {
3174                 /*
3175                  * Any task has to be enqueued before it get to execute on
3176                  * a CPU. So account for the time it spent waiting on the
3177                  * runqueue.
3178                  */
3179                 update_stats_wait_end(cfs_rq, se);
3180                 __dequeue_entity(cfs_rq, se);
3181         }
3182
3183         update_stats_curr_start(cfs_rq, se);
3184         cfs_rq->curr = se;
3185 #ifdef CONFIG_SCHEDSTATS
3186         /*
3187          * Track our maximum slice length, if the CPU's load is at
3188          * least twice that of our own weight (i.e. dont track it
3189          * when there are only lesser-weight tasks around):
3190          */
3191         if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
3192                 se->statistics.slice_max = max(se->statistics.slice_max,
3193                         se->sum_exec_runtime - se->prev_sum_exec_runtime);
3194         }
3195 #endif
3196         se->prev_sum_exec_runtime = se->sum_exec_runtime;
3197 }
3198
3199 static int
3200 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
3201
3202 /*
3203  * Pick the next process, keeping these things in mind, in this order:
3204  * 1) keep things fair between processes/task groups
3205  * 2) pick the "next" process, since someone really wants that to run
3206  * 3) pick the "last" process, for cache locality
3207  * 4) do not run the "skip" process, if something else is available
3208  */
3209 static struct sched_entity *
3210 pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
3211 {
3212         struct sched_entity *left = __pick_first_entity(cfs_rq);
3213         struct sched_entity *se;
3214
3215         /*
3216          * If curr is set we have to see if its left of the leftmost entity
3217          * still in the tree, provided there was anything in the tree at all.
3218          */
3219         if (!left || (curr && entity_before(curr, left)))
3220                 left = curr;
3221
3222         se = left; /* ideally we run the leftmost entity */
3223
3224         /*
3225          * Avoid running the skip buddy, if running something else can
3226          * be done without getting too unfair.
3227          */
3228         if (cfs_rq->skip == se) {
3229                 struct sched_entity *second;
3230
3231                 if (se == curr) {
3232                         second = __pick_first_entity(cfs_rq);
3233                 } else {
3234                         second = __pick_next_entity(se);
3235                         if (!second || (curr && entity_before(curr, second)))
3236                                 second = curr;
3237                 }
3238
3239                 if (second && wakeup_preempt_entity(second, left) < 1)
3240                         se = second;
3241         }
3242
3243         /*
3244          * Prefer last buddy, try to return the CPU to a preempted task.
3245          */
3246         if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
3247                 se = cfs_rq->last;
3248
3249         /*
3250          * Someone really wants this to run. If it's not unfair, run it.
3251          */
3252         if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
3253                 se = cfs_rq->next;
3254
3255         clear_buddies(cfs_rq, se);
3256
3257         return se;
3258 }
3259
3260 static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
3261
3262 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
3263 {
3264         /*
3265          * If still on the runqueue then deactivate_task()
3266          * was not called and update_curr() has to be done:
3267          */
3268         if (prev->on_rq)
3269                 update_curr(cfs_rq);
3270
3271         /* throttle cfs_rqs exceeding runtime */
3272         check_cfs_rq_runtime(cfs_rq);
3273
3274         check_spread(cfs_rq, prev);
3275         if (prev->on_rq) {
3276                 update_stats_wait_start(cfs_rq, prev);
3277                 /* Put 'current' back into the tree. */
3278                 __enqueue_entity(cfs_rq, prev);
3279                 /* in !on_rq case, update occurred at dequeue */
3280                 update_entity_load_avg(prev, 1);
3281         }
3282         cfs_rq->curr = NULL;
3283 }
3284
3285 static void
3286 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
3287 {
3288         /*
3289          * Update run-time statistics of the 'current'.
3290          */
3291         update_curr(cfs_rq);
3292
3293         /*
3294          * Ensure that runnable average is periodically updated.
3295          */
3296         update_entity_load_avg(curr, 1);
3297         update_cfs_rq_blocked_load(cfs_rq, 1);
3298         update_cfs_shares(cfs_rq);
3299
3300 #ifdef CONFIG_SCHED_HRTICK
3301         /*
3302          * queued ticks are scheduled to match the slice, so don't bother
3303          * validating it and just reschedule.
3304          */
3305         if (queued) {
3306                 resched_curr(rq_of(cfs_rq));
3307                 return;
3308         }
3309         /*
3310          * don't let the period tick interfere with the hrtick preemption
3311          */
3312         if (!sched_feat(DOUBLE_TICK) &&
3313                         hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
3314                 return;
3315 #endif
3316
3317         if (cfs_rq->nr_running > 1)
3318                 check_preempt_tick(cfs_rq, curr);
3319 }
3320
3321
3322 /**************************************************
3323  * CFS bandwidth control machinery
3324  */
3325
3326 #ifdef CONFIG_CFS_BANDWIDTH
3327
3328 #ifdef HAVE_JUMP_LABEL
3329 static struct static_key __cfs_bandwidth_used;
3330
3331 static inline bool cfs_bandwidth_used(void)
3332 {
3333         return static_key_false(&__cfs_bandwidth_used);
3334 }
3335
3336 void cfs_bandwidth_usage_inc(void)
3337 {
3338         static_key_slow_inc(&__cfs_bandwidth_used);
3339 }
3340
3341 void cfs_bandwidth_usage_dec(void)
3342 {
3343         static_key_slow_dec(&__cfs_bandwidth_used);
3344 }
3345 #else /* HAVE_JUMP_LABEL */
3346 static bool cfs_bandwidth_used(void)
3347 {
3348         return true;
3349 }
3350
3351 void cfs_bandwidth_usage_inc(void) {}
3352 void cfs_bandwidth_usage_dec(void) {}
3353 #endif /* HAVE_JUMP_LABEL */
3354
3355 /*
3356  * default period for cfs group bandwidth.
3357  * default: 0.1s, units: nanoseconds
3358  */
3359 static inline u64 default_cfs_period(void)
3360 {
3361         return 100000000ULL;
3362 }
3363
3364 static inline u64 sched_cfs_bandwidth_slice(void)
3365 {
3366         return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
3367 }
3368
3369 /*
3370  * Replenish runtime according to assigned quota and update expiration time.
3371  * We use sched_clock_cpu directly instead of rq->clock to avoid adding
3372  * additional synchronization around rq->lock.
3373  *
3374  * requires cfs_b->lock
3375  */
3376 void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b)
3377 {
3378         u64 now;
3379
3380         if (cfs_b->quota == RUNTIME_INF)
3381                 return;
3382
3383         now = sched_clock_cpu(smp_processor_id());
3384         cfs_b->runtime = cfs_b->quota;
3385         cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period);
3386 }
3387
3388 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
3389 {
3390         return &tg->cfs_bandwidth;
3391 }
3392
3393 /* rq->task_clock normalized against any time this cfs_rq has spent throttled */
3394 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
3395 {
3396         if (unlikely(cfs_rq->throttle_count))
3397                 return cfs_rq->throttled_clock_task;
3398
3399         return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
3400 }
3401
3402 /* returns 0 on failure to allocate runtime */
3403 static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3404 {
3405         struct task_group *tg = cfs_rq->tg;
3406         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
3407         u64 amount = 0, min_amount, expires;
3408
3409         /* note: this is a positive sum as runtime_remaining <= 0 */
3410         min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;
3411
3412         raw_spin_lock(&cfs_b->lock);
3413         if (cfs_b->quota == RUNTIME_INF)
3414                 amount = min_amount;
3415         else {
3416                 /*
3417                  * If the bandwidth pool has become inactive, then at least one
3418                  * period must have elapsed since the last consumption.
3419                  * Refresh the global state and ensure bandwidth timer becomes
3420                  * active.
3421                  */
3422                 if (!cfs_b->timer_active) {
3423                         __refill_cfs_bandwidth_runtime(cfs_b);
3424                         __start_cfs_bandwidth(cfs_b, false);
3425                 }
3426
3427                 if (cfs_b->runtime > 0) {
3428                         amount = min(cfs_b->runtime, min_amount);
3429                         cfs_b->runtime -= amount;
3430                         cfs_b->idle = 0;
3431                 }
3432         }
3433         expires = cfs_b->runtime_expires;
3434         raw_spin_unlock(&cfs_b->lock);
3435
3436         cfs_rq->runtime_remaining += amount;
3437         /*
3438          * we may have advanced our local expiration to account for allowed
3439          * spread between our sched_clock and the one on which runtime was
3440          * issued.
3441          */
3442         if ((s64)(expires - cfs_rq->runtime_expires) > 0)
3443                 cfs_rq->runtime_expires = expires;
3444
3445         return cfs_rq->runtime_remaining > 0;
3446 }
3447
3448 /*
3449  * Note: This depends on the synchronization provided by sched_clock and the
3450  * fact that rq->clock snapshots this value.
3451  */
3452 static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3453 {
3454         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3455
3456         /* if the deadline is ahead of our clock, nothing to do */
3457         if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
3458                 return;
3459
3460         if (cfs_rq->runtime_remaining < 0)
3461                 return;
3462
3463         /*
3464          * If the local deadline has passed we have to consider the
3465          * possibility that our sched_clock is 'fast' and the global deadline
3466          * has not truly expired.
3467          *
3468          * Fortunately we can check determine whether this the case by checking
3469          * whether the global deadline has advanced. It is valid to compare
3470          * cfs_b->runtime_expires without any locks since we only care about
3471          * exact equality, so a partial write will still work.
3472          */
3473
3474         if (cfs_rq->runtime_expires != cfs_b->runtime_expires) {
3475                 /* extend local deadline, drift is bounded above by 2 ticks */
3476                 cfs_rq->runtime_expires += TICK_NSEC;
3477         } else {
3478                 /* global deadline is ahead, expiration has passed */
3479                 cfs_rq->runtime_remaining = 0;
3480         }
3481 }
3482
3483 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3484 {
3485         /* dock delta_exec before expiring quota (as it could span periods) */
3486         cfs_rq->runtime_remaining -= delta_exec;
3487         expire_cfs_rq_runtime(cfs_rq);
3488
3489         if (likely(cfs_rq->runtime_remaining > 0))
3490                 return;
3491
3492         /*
3493          * if we're unable to extend our runtime we resched so that the active
3494          * hierarchy can be throttled
3495          */
3496         if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
3497                 resched_curr(rq_of(cfs_rq));
3498 }
3499
3500 static __always_inline
3501 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3502 {
3503         if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
3504                 return;
3505
3506         __account_cfs_rq_runtime(cfs_rq, delta_exec);
3507 }
3508
3509 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3510 {
3511         return cfs_bandwidth_used() && cfs_rq->throttled;
3512 }
3513
3514 /* check whether cfs_rq, or any parent, is throttled */
3515 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3516 {
3517         return cfs_bandwidth_used() && cfs_rq->throttle_count;
3518 }
3519
3520 /*
3521  * Ensure that neither of the group entities corresponding to src_cpu or
3522  * dest_cpu are members of a throttled hierarchy when performing group
3523  * load-balance operations.
3524  */
3525 static inline int throttled_lb_pair(struct task_group *tg,
3526                                     int src_cpu, int dest_cpu)
3527 {
3528         struct cfs_rq *src_cfs_rq, *dest_cfs_rq;
3529
3530         src_cfs_rq = tg->cfs_rq[src_cpu];
3531         dest_cfs_rq = tg->cfs_rq[dest_cpu];
3532
3533         return throttled_hierarchy(src_cfs_rq) ||
3534                throttled_hierarchy(dest_cfs_rq);
3535 }
3536
3537 /* updated child weight may affect parent so we have to do this bottom up */
3538 static int tg_unthrottle_up(struct task_group *tg, void *data)
3539 {
3540         struct rq *rq = data;
3541         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3542
3543         cfs_rq->throttle_count--;
3544 #ifdef CONFIG_SMP
3545         if (!cfs_rq->throttle_count) {
3546                 /* adjust cfs_rq_clock_task() */
3547                 cfs_rq->throttled_clock_task_time += rq_clock_task(rq) -
3548                                              cfs_rq->throttled_clock_task;
3549         }
3550 #endif
3551
3552         return 0;
3553 }
3554
3555 static int tg_throttle_down(struct task_group *tg, void *data)
3556 {
3557         struct rq *rq = data;
3558         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3559
3560         /* group is entering throttled state, stop time */
3561         if (!cfs_rq->throttle_count)
3562                 cfs_rq->throttled_clock_task = rq_clock_task(rq);
3563         cfs_rq->throttle_count++;
3564
3565         return 0;
3566 }
3567
3568 static void throttle_cfs_rq(struct cfs_rq *cfs_rq)
3569 {
3570         struct rq *rq = rq_of(cfs_rq);
3571         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3572         struct sched_entity *se;
3573         long task_delta, dequeue = 1;
3574
3575         se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
3576
3577         /* freeze hierarchy runnable averages while throttled */
3578         rcu_read_lock();
3579         walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
3580         rcu_read_unlock();
3581
3582         task_delta = cfs_rq->h_nr_running;
3583         for_each_sched_entity(se) {
3584                 struct cfs_rq *qcfs_rq = cfs_rq_of(se);
3585                 /* throttled entity or throttle-on-deactivate */
3586                 if (!se->on_rq)
3587                         break;
3588
3589                 if (dequeue)
3590                         dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
3591                 qcfs_rq->h_nr_running -= task_delta;
3592
3593                 if (qcfs_rq->load.weight)
3594                         dequeue = 0;
3595         }
3596
3597         if (!se)
3598                 sub_nr_running(rq, task_delta);
3599
3600         cfs_rq->throttled = 1;
3601         cfs_rq->throttled_clock = rq_clock(rq);
3602         raw_spin_lock(&cfs_b->lock);
3603         /*
3604          * Add to the _head_ of the list, so that an already-started
3605          * distribute_cfs_runtime will not see us
3606          */
3607         list_add_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq);
3608         if (!cfs_b->timer_active)
3609                 __start_cfs_bandwidth(cfs_b, false);
3610         raw_spin_unlock(&cfs_b->lock);
3611 }
3612
3613 void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
3614 {
3615         struct rq *rq = rq_of(cfs_rq);
3616         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3617         struct sched_entity *se;
3618         int enqueue = 1;
3619         long task_delta;
3620
3621         se = cfs_rq->tg->se[cpu_of(rq)];
3622
3623         cfs_rq->throttled = 0;
3624
3625         update_rq_clock(rq);
3626
3627         raw_spin_lock(&cfs_b->lock);
3628         cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
3629         list_del_rcu(&cfs_rq->throttled_list);
3630         raw_spin_unlock(&cfs_b->lock);
3631
3632         /* update hierarchical throttle state */
3633         walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
3634
3635         if (!cfs_rq->load.weight)
3636                 return;
3637
3638         task_delta = cfs_rq->h_nr_running;
3639         for_each_sched_entity(se) {
3640                 if (se->on_rq)
3641                         enqueue = 0;
3642
3643                 cfs_rq = cfs_rq_of(se);
3644                 if (enqueue)
3645                         enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);
3646                 cfs_rq->h_nr_running += task_delta;
3647
3648                 if (cfs_rq_throttled(cfs_rq))
3649                         break;
3650         }
3651
3652         if (!se)
3653                 add_nr_running(rq, task_delta);
3654
3655         /* determine whether we need to wake up potentially idle cpu */
3656         if (rq->curr == rq->idle && rq->cfs.nr_running)
3657                 resched_curr(rq);
3658 }
3659
3660 static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b,
3661                 u64 remaining, u64 expires)
3662 {
3663         struct cfs_rq *cfs_rq;
3664         u64 runtime;
3665         u64 starting_runtime = remaining;
3666
3667         rcu_read_lock();
3668         list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
3669                                 throttled_list) {
3670                 struct rq *rq = rq_of(cfs_rq);
3671
3672                 raw_spin_lock(&rq->lock);
3673                 if (!cfs_rq_throttled(cfs_rq))
3674                         goto next;
3675
3676                 runtime = -cfs_rq->runtime_remaining + 1;
3677                 if (runtime > remaining)
3678                         runtime = remaining;
3679                 remaining -= runtime;
3680
3681                 cfs_rq->runtime_remaining += runtime;
3682                 cfs_rq->runtime_expires = expires;
3683
3684                 /* we check whether we're throttled above */
3685                 if (cfs_rq->runtime_remaining > 0)
3686                         unthrottle_cfs_rq(cfs_rq);
3687
3688 next:
3689                 raw_spin_unlock(&rq->lock);
3690
3691                 if (!remaining)
3692                         break;
3693         }
3694         rcu_read_unlock();
3695
3696         return starting_runtime - remaining;
3697 }
3698
3699 /*
3700  * Responsible for refilling a task_group's bandwidth and unthrottling its
3701  * cfs_rqs as appropriate. If there has been no activity within the last
3702  * period the timer is deactivated until scheduling resumes; cfs_b->idle is
3703  * used to track this state.
3704  */
3705 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
3706 {
3707         u64 runtime, runtime_expires;
3708         int throttled;
3709
3710         /* no need to continue the timer with no bandwidth constraint */
3711         if (cfs_b->quota == RUNTIME_INF)
3712                 goto out_deactivate;
3713
3714         throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3715         cfs_b->nr_periods += overrun;
3716
3717         /*
3718          * idle depends on !throttled (for the case of a large deficit), and if
3719          * we're going inactive then everything else can be deferred
3720          */
3721         if (cfs_b->idle && !throttled)
3722                 goto out_deactivate;
3723
3724         /*
3725          * if we have relooped after returning idle once, we need to update our
3726          * status as actually running, so that other cpus doing
3727          * __start_cfs_bandwidth will stop trying to cancel us.
3728          */
3729         cfs_b->timer_active = 1;
3730
3731         __refill_cfs_bandwidth_runtime(cfs_b);
3732
3733         if (!throttled) {
3734                 /* mark as potentially idle for the upcoming period */
3735                 cfs_b->idle = 1;
3736                 return 0;
3737         }
3738
3739         /* account preceding periods in which throttling occurred */
3740         cfs_b->nr_throttled += overrun;
3741
3742         runtime_expires = cfs_b->runtime_expires;
3743
3744         /*
3745          * This check is repeated as we are holding onto the new bandwidth while
3746          * we unthrottle. This can potentially race with an unthrottled group
3747          * trying to acquire new bandwidth from the global pool. This can result
3748          * in us over-using our runtime if it is all used during this loop, but
3749          * only by limited amounts in that extreme case.
3750          */
3751         while (throttled && cfs_b->runtime > 0) {
3752                 runtime = cfs_b->runtime;
3753                 raw_spin_unlock(&cfs_b->lock);
3754                 /* we can't nest cfs_b->lock while distributing bandwidth */
3755                 runtime = distribute_cfs_runtime(cfs_b, runtime,
3756                                                  runtime_expires);
3757                 raw_spin_lock(&cfs_b->lock);
3758
3759                 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3760
3761                 cfs_b->runtime -= min(runtime, cfs_b->runtime);
3762         }
3763
3764         /*
3765          * While we are ensured activity in the period following an
3766          * unthrottle, this also covers the case in which the new bandwidth is
3767          * insufficient to cover the existing bandwidth deficit.  (Forcing the
3768          * timer to remain active while there are any throttled entities.)
3769          */
3770         cfs_b->idle = 0;
3771
3772         return 0;
3773
3774 out_deactivate:
3775         cfs_b->timer_active = 0;
3776         return 1;
3777 }
3778
3779 /* a cfs_rq won't donate quota below this amount */
3780 static const u64 min_cfs_rq_runtime = 1 * NSEC_PER_MSEC;
3781 /* minimum remaining period time to redistribute slack quota */
3782 static const u64 min_bandwidth_expiration = 2 * NSEC_PER_MSEC;
3783 /* how long we wait to gather additional slack before distributing */
3784 static const u64 cfs_bandwidth_slack_period = 5 * NSEC_PER_MSEC;
3785
3786 /*
3787  * Are we near the end of the current quota period?
3788  *
3789  * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the
3790  * hrtimer base being cleared by __hrtimer_start_range_ns. In the case of
3791  * migrate_hrtimers, base is never cleared, so we are fine.
3792  */
3793 static int runtime_refresh_within(struct cfs_bandwidth *cfs_b, u64 min_expire)
3794 {
3795         struct hrtimer *refresh_timer = &cfs_b->period_timer;
3796         u64 remaining;
3797
3798         /* if the call-back is running a quota refresh is already occurring */
3799         if (hrtimer_callback_running(refresh_timer))
3800                 return 1;
3801
3802         /* is a quota refresh about to occur? */
3803         remaining = ktime_to_ns(hrtimer_expires_remaining(refresh_timer));
3804         if (remaining < min_expire)
3805                 return 1;
3806
3807         return 0;
3808 }
3809
3810 static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
3811 {
3812         u64 min_left = cfs_bandwidth_slack_period + min_bandwidth_expiration;
3813
3814         /* if there's a quota refresh soon don't bother with slack */
3815         if (runtime_refresh_within(cfs_b, min_left))
3816                 return;
3817
3818         start_bandwidth_timer(&cfs_b->slack_timer,
3819                                 ns_to_ktime(cfs_bandwidth_slack_period));
3820 }
3821
3822 /* we know any runtime found here is valid as update_curr() precedes return */
3823 static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3824 {
3825         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3826         s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;
3827
3828         if (slack_runtime <= 0)
3829                 return;
3830
3831         raw_spin_lock(&cfs_b->lock);
3832         if (cfs_b->quota != RUNTIME_INF &&
3833             cfs_rq->runtime_expires == cfs_b->runtime_expires) {
3834                 cfs_b->runtime += slack_runtime;
3835
3836                 /* we are under rq->lock, defer unthrottling using a timer */
3837                 if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
3838                     !list_empty(&cfs_b->throttled_cfs_rq))
3839                         start_cfs_slack_bandwidth(cfs_b);
3840         }
3841         raw_spin_unlock(&cfs_b->lock);
3842
3843         /* even if it's not valid for return we don't want to try again */
3844         cfs_rq->runtime_remaining -= slack_runtime;
3845 }
3846
3847 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3848 {
3849         if (!cfs_bandwidth_used())
3850                 return;
3851
3852         if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
3853                 return;
3854
3855         __return_cfs_rq_runtime(cfs_rq);
3856 }
3857
3858 /*
3859  * This is done with a timer (instead of inline with bandwidth return) since
3860  * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs.
3861  */
3862 static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
3863 {
3864         u64 runtime = 0, slice = sched_cfs_bandwidth_slice();
3865         u64 expires;
3866
3867         /* confirm we're still not at a refresh boundary */
3868         raw_spin_lock(&cfs_b->lock);
3869         if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) {
3870                 raw_spin_unlock(&cfs_b->lock);
3871                 return;
3872         }
3873
3874         if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice)
3875                 runtime = cfs_b->runtime;
3876
3877         expires = cfs_b->runtime_expires;
3878         raw_spin_unlock(&cfs_b->lock);
3879
3880         if (!runtime)
3881                 return;
3882
3883         runtime = distribute_cfs_runtime(cfs_b, runtime, expires);
3884
3885         raw_spin_lock(&cfs_b->lock);
3886         if (expires == cfs_b->runtime_expires)
3887                 cfs_b->runtime -= min(runtime, cfs_b->runtime);
3888         raw_spin_unlock(&cfs_b->lock);
3889 }