ef2b104b254cb8c60d954a92e62f0f8a626ed024
[projects/modsched/linux.git] / kernel / sched / 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         p->se.avg.decay_count = 0;
680         slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
681         p->se.avg.runnable_avg_sum = slice;
682         p->se.avg.runnable_avg_period = slice;
683         __update_task_entity_contrib(&p->se);
684 }
685 #else
686 void init_task_runnable_average(struct task_struct *p)
687 {
688 }
689 #endif
690
691 /*
692  * Update the current task's runtime statistics.
693  */
694 static void update_curr(struct cfs_rq *cfs_rq)
695 {
696         struct sched_entity *curr = cfs_rq->curr;
697         u64 now = rq_clock_task(rq_of(cfs_rq));
698         u64 delta_exec;
699
700         if (unlikely(!curr))
701                 return;
702
703         delta_exec = now - curr->exec_start;
704         if (unlikely((s64)delta_exec <= 0))
705                 return;
706
707         curr->exec_start = now;
708
709         schedstat_set(curr->statistics.exec_max,
710                       max(delta_exec, curr->statistics.exec_max));
711
712         curr->sum_exec_runtime += delta_exec;
713         schedstat_add(cfs_rq, exec_clock, delta_exec);
714
715         curr->vruntime += calc_delta_fair(delta_exec, curr);
716         update_min_vruntime(cfs_rq);
717
718         if (entity_is_task(curr)) {
719                 struct task_struct *curtask = task_of(curr);
720
721                 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
722                 cpuacct_charge(curtask, delta_exec);
723                 account_group_exec_runtime(curtask, delta_exec);
724         }
725
726         account_cfs_rq_runtime(cfs_rq, delta_exec);
727 }
728
729 static void update_curr_fair(struct rq *rq)
730 {
731         update_curr(cfs_rq_of(&rq->curr->se));
732 }
733
734 static inline void
735 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
736 {
737         schedstat_set(se->statistics.wait_start, rq_clock(rq_of(cfs_rq)));
738 }
739
740 /*
741  * Task is being enqueued - update stats:
742  */
743 static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
744 {
745         /*
746          * Are we enqueueing a waiting task? (for current tasks
747          * a dequeue/enqueue event is a NOP)
748          */
749         if (se != cfs_rq->curr)
750                 update_stats_wait_start(cfs_rq, se);
751 }
752
753 static void
754 update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
755 {
756         schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
757                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start));
758         schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
759         schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
760                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
761 #ifdef CONFIG_SCHEDSTATS
762         if (entity_is_task(se)) {
763                 trace_sched_stat_wait(task_of(se),
764                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
765         }
766 #endif
767         schedstat_set(se->statistics.wait_start, 0);
768 }
769
770 static inline void
771 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
772 {
773         /*
774          * Mark the end of the wait period if dequeueing a
775          * waiting task:
776          */
777         if (se != cfs_rq->curr)
778                 update_stats_wait_end(cfs_rq, se);
779 }
780
781 /*
782  * We are picking a new current task - update its stats:
783  */
784 static inline void
785 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
786 {
787         /*
788          * We are starting a new run period:
789          */
790         se->exec_start = rq_clock_task(rq_of(cfs_rq));
791 }
792
793 /**************************************************
794  * Scheduling class queueing methods:
795  */
796
797 #ifdef CONFIG_NUMA_BALANCING
798 /*
799  * Approximate time to scan a full NUMA task in ms. The task scan period is
800  * calculated based on the tasks virtual memory size and
801  * numa_balancing_scan_size.
802  */
803 unsigned int sysctl_numa_balancing_scan_period_min = 1000;
804 unsigned int sysctl_numa_balancing_scan_period_max = 60000;
805
806 /* Portion of address space to scan in MB */
807 unsigned int sysctl_numa_balancing_scan_size = 256;
808
809 /* Scan @scan_size MB every @scan_period after an initial @scan_delay in ms */
810 unsigned int sysctl_numa_balancing_scan_delay = 1000;
811
812 static unsigned int task_nr_scan_windows(struct task_struct *p)
813 {
814         unsigned long rss = 0;
815         unsigned long nr_scan_pages;
816
817         /*
818          * Calculations based on RSS as non-present and empty pages are skipped
819          * by the PTE scanner and NUMA hinting faults should be trapped based
820          * on resident pages
821          */
822         nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT);
823         rss = get_mm_rss(p->mm);
824         if (!rss)
825                 rss = nr_scan_pages;
826
827         rss = round_up(rss, nr_scan_pages);
828         return rss / nr_scan_pages;
829 }
830
831 /* For sanitys sake, never scan more PTEs than MAX_SCAN_WINDOW MB/sec. */
832 #define MAX_SCAN_WINDOW 2560
833
834 static unsigned int task_scan_min(struct task_struct *p)
835 {
836         unsigned int scan_size = ACCESS_ONCE(sysctl_numa_balancing_scan_size);
837         unsigned int scan, floor;
838         unsigned int windows = 1;
839
840         if (scan_size < MAX_SCAN_WINDOW)
841                 windows = MAX_SCAN_WINDOW / scan_size;
842         floor = 1000 / windows;
843
844         scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p);
845         return max_t(unsigned int, floor, scan);
846 }
847
848 static unsigned int task_scan_max(struct task_struct *p)
849 {
850         unsigned int smin = task_scan_min(p);
851         unsigned int smax;
852
853         /* Watch for min being lower than max due to floor calculations */
854         smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p);
855         return max(smin, smax);
856 }
857
858 static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
859 {
860         rq->nr_numa_running += (p->numa_preferred_nid != -1);
861         rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
862 }
863
864 static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
865 {
866         rq->nr_numa_running -= (p->numa_preferred_nid != -1);
867         rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
868 }
869
870 struct numa_group {
871         atomic_t refcount;
872
873         spinlock_t lock; /* nr_tasks, tasks */
874         int nr_tasks;
875         pid_t gid;
876         struct list_head task_list;
877
878         struct rcu_head rcu;
879         nodemask_t active_nodes;
880         unsigned long total_faults;
881         /*
882          * Faults_cpu is used to decide whether memory should move
883          * towards the CPU. As a consequence, these stats are weighted
884          * more by CPU use than by memory faults.
885          */
886         unsigned long *faults_cpu;
887         unsigned long faults[0];
888 };
889
890 /* Shared or private faults. */
891 #define NR_NUMA_HINT_FAULT_TYPES 2
892
893 /* Memory and CPU locality */
894 #define NR_NUMA_HINT_FAULT_STATS (NR_NUMA_HINT_FAULT_TYPES * 2)
895
896 /* Averaged statistics, and temporary buffers. */
897 #define NR_NUMA_HINT_FAULT_BUCKETS (NR_NUMA_HINT_FAULT_STATS * 2)
898
899 pid_t task_numa_group_id(struct task_struct *p)
900 {
901         return p->numa_group ? p->numa_group->gid : 0;
902 }
903
904 static inline int task_faults_idx(int nid, int priv)
905 {
906         return NR_NUMA_HINT_FAULT_TYPES * nid + priv;
907 }
908
909 static inline unsigned long task_faults(struct task_struct *p, int nid)
910 {
911         if (!p->numa_faults_memory)
912                 return 0;
913
914         return p->numa_faults_memory[task_faults_idx(nid, 0)] +
915                 p->numa_faults_memory[task_faults_idx(nid, 1)];
916 }
917
918 static inline unsigned long group_faults(struct task_struct *p, int nid)
919 {
920         if (!p->numa_group)
921                 return 0;
922
923         return p->numa_group->faults[task_faults_idx(nid, 0)] +
924                 p->numa_group->faults[task_faults_idx(nid, 1)];
925 }
926
927 static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
928 {
929         return group->faults_cpu[task_faults_idx(nid, 0)] +
930                 group->faults_cpu[task_faults_idx(nid, 1)];
931 }
932
933 /*
934  * These return the fraction of accesses done by a particular task, or
935  * task group, on a particular numa node.  The group weight is given a
936  * larger multiplier, in order to group tasks together that are almost
937  * evenly spread out between numa nodes.
938  */
939 static inline unsigned long task_weight(struct task_struct *p, int nid)
940 {
941         unsigned long total_faults;
942
943         if (!p->numa_faults_memory)
944                 return 0;
945
946         total_faults = p->total_numa_faults;
947
948         if (!total_faults)
949                 return 0;
950
951         return 1000 * task_faults(p, nid) / total_faults;
952 }
953
954 static inline unsigned long group_weight(struct task_struct *p, int nid)
955 {
956         if (!p->numa_group || !p->numa_group->total_faults)
957                 return 0;
958
959         return 1000 * group_faults(p, nid) / p->numa_group->total_faults;
960 }
961
962 bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
963                                 int src_nid, int dst_cpu)
964 {
965         struct numa_group *ng = p->numa_group;
966         int dst_nid = cpu_to_node(dst_cpu);
967         int last_cpupid, this_cpupid;
968
969         this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
970
971         /*
972          * Multi-stage node selection is used in conjunction with a periodic
973          * migration fault to build a temporal task<->page relation. By using
974          * a two-stage filter we remove short/unlikely relations.
975          *
976          * Using P(p) ~ n_p / n_t as per frequentist probability, we can equate
977          * a task's usage of a particular page (n_p) per total usage of this
978          * page (n_t) (in a given time-span) to a probability.
979          *
980          * Our periodic faults will sample this probability and getting the
981          * same result twice in a row, given these samples are fully
982          * independent, is then given by P(n)^2, provided our sample period
983          * is sufficiently short compared to the usage pattern.
984          *
985          * This quadric squishes small probabilities, making it less likely we
986          * act on an unlikely task<->page relation.
987          */
988         last_cpupid = page_cpupid_xchg_last(page, this_cpupid);
989         if (!cpupid_pid_unset(last_cpupid) &&
990                                 cpupid_to_nid(last_cpupid) != dst_nid)
991                 return false;
992
993         /* Always allow migrate on private faults */
994         if (cpupid_match_pid(p, last_cpupid))
995                 return true;
996
997         /* A shared fault, but p->numa_group has not been set up yet. */
998         if (!ng)
999                 return true;
1000
1001         /*
1002          * Do not migrate if the destination is not a node that
1003          * is actively used by this numa group.
1004          */
1005         if (!node_isset(dst_nid, ng->active_nodes))
1006                 return false;
1007
1008         /*
1009          * Source is a node that is not actively used by this
1010          * numa group, while the destination is. Migrate.
1011          */
1012         if (!node_isset(src_nid, ng->active_nodes))
1013                 return true;
1014
1015         /*
1016          * Both source and destination are nodes in active
1017          * use by this numa group. Maximize memory bandwidth
1018          * by migrating from more heavily used groups, to less
1019          * heavily used ones, spreading the load around.
1020          * Use a 1/4 hysteresis to avoid spurious page movement.
1021          */
1022         return group_faults(p, dst_nid) < (group_faults(p, src_nid) * 3 / 4);
1023 }
1024
1025 static unsigned long weighted_cpuload(const int cpu);
1026 static unsigned long source_load(int cpu, int type);
1027 static unsigned long target_load(int cpu, int type);
1028 static unsigned long capacity_of(int cpu);
1029 static long effective_load(struct task_group *tg, int cpu, long wl, long wg);
1030
1031 /* Cached statistics for all CPUs within a node */
1032 struct numa_stats {
1033         unsigned long nr_running;
1034         unsigned long load;
1035
1036         /* Total compute capacity of CPUs on a node */
1037         unsigned long compute_capacity;
1038
1039         /* Approximate capacity in terms of runnable tasks on a node */
1040         unsigned long task_capacity;
1041         int has_free_capacity;
1042 };
1043
1044 /*
1045  * XXX borrowed from update_sg_lb_stats
1046  */
1047 static void update_numa_stats(struct numa_stats *ns, int nid)
1048 {
1049         int smt, cpu, cpus = 0;
1050         unsigned long capacity;
1051
1052         memset(ns, 0, sizeof(*ns));
1053         for_each_cpu(cpu, cpumask_of_node(nid)) {
1054                 struct rq *rq = cpu_rq(cpu);
1055
1056                 ns->nr_running += rq->nr_running;
1057                 ns->load += weighted_cpuload(cpu);
1058                 ns->compute_capacity += capacity_of(cpu);
1059
1060                 cpus++;
1061         }
1062
1063         /*
1064          * If we raced with hotplug and there are no CPUs left in our mask
1065          * the @ns structure is NULL'ed and task_numa_compare() will
1066          * not find this node attractive.
1067          *
1068          * We'll either bail at !has_free_capacity, or we'll detect a huge
1069          * imbalance and bail there.
1070          */
1071         if (!cpus)
1072                 return;
1073
1074         /* smt := ceil(cpus / capacity), assumes: 1 < smt_power < 2 */
1075         smt = DIV_ROUND_UP(SCHED_CAPACITY_SCALE * cpus, ns->compute_capacity);
1076         capacity = cpus / smt; /* cores */
1077
1078         ns->task_capacity = min_t(unsigned, capacity,
1079                 DIV_ROUND_CLOSEST(ns->compute_capacity, SCHED_CAPACITY_SCALE));
1080         ns->has_free_capacity = (ns->nr_running < ns->task_capacity);
1081 }
1082
1083 struct task_numa_env {
1084         struct task_struct *p;
1085
1086         int src_cpu, src_nid;
1087         int dst_cpu, dst_nid;
1088
1089         struct numa_stats src_stats, dst_stats;
1090
1091         int imbalance_pct;
1092
1093         struct task_struct *best_task;
1094         long best_imp;
1095         int best_cpu;
1096 };
1097
1098 static void task_numa_assign(struct task_numa_env *env,
1099                              struct task_struct *p, long imp)
1100 {
1101         if (env->best_task)
1102                 put_task_struct(env->best_task);
1103         if (p)
1104                 get_task_struct(p);
1105
1106         env->best_task = p;
1107         env->best_imp = imp;
1108         env->best_cpu = env->dst_cpu;
1109 }
1110
1111 static bool load_too_imbalanced(long src_load, long dst_load,
1112                                 struct task_numa_env *env)
1113 {
1114         long imb, old_imb;
1115         long orig_src_load, orig_dst_load;
1116         long src_capacity, dst_capacity;
1117
1118         /*
1119          * The load is corrected for the CPU capacity available on each node.
1120          *
1121          * src_load        dst_load
1122          * ------------ vs ---------
1123          * src_capacity    dst_capacity
1124          */
1125         src_capacity = env->src_stats.compute_capacity;
1126         dst_capacity = env->dst_stats.compute_capacity;
1127
1128         /* We care about the slope of the imbalance, not the direction. */
1129         if (dst_load < src_load)
1130                 swap(dst_load, src_load);
1131
1132         /* Is the difference below the threshold? */
1133         imb = dst_load * src_capacity * 100 -
1134               src_load * dst_capacity * env->imbalance_pct;
1135         if (imb <= 0)
1136                 return false;
1137
1138         /*
1139          * The imbalance is above the allowed threshold.
1140          * Compare it with the old imbalance.
1141          */
1142         orig_src_load = env->src_stats.load;
1143         orig_dst_load = env->dst_stats.load;
1144
1145         if (orig_dst_load < orig_src_load)
1146                 swap(orig_dst_load, orig_src_load);
1147
1148         old_imb = orig_dst_load * src_capacity * 100 -
1149                   orig_src_load * dst_capacity * env->imbalance_pct;
1150
1151         /* Would this change make things worse? */
1152         return (imb > old_imb);
1153 }
1154
1155 /*
1156  * This checks if the overall compute and NUMA accesses of the system would
1157  * be improved if the source tasks was migrated to the target dst_cpu taking
1158  * into account that it might be best if task running on the dst_cpu should
1159  * be exchanged with the source task
1160  */
1161 static void task_numa_compare(struct task_numa_env *env,
1162                               long taskimp, long groupimp)
1163 {
1164         struct rq *src_rq = cpu_rq(env->src_cpu);
1165         struct rq *dst_rq = cpu_rq(env->dst_cpu);
1166         struct task_struct *cur;
1167         long src_load, dst_load;
1168         long load;
1169         long imp = env->p->numa_group ? groupimp : taskimp;
1170         long moveimp = imp;
1171
1172         rcu_read_lock();
1173
1174         raw_spin_lock_irq(&dst_rq->lock);
1175         cur = dst_rq->curr;
1176         /*
1177          * No need to move the exiting task, and this ensures that ->curr
1178          * wasn't reaped and thus get_task_struct() in task_numa_assign()
1179          * is safe under RCU read lock.
1180          * Note that rcu_read_lock() itself can't protect from the final
1181          * put_task_struct() after the last schedule().
1182          */
1183         if ((cur->flags & PF_EXITING) || is_idle_task(cur))
1184                 cur = NULL;
1185         raw_spin_unlock_irq(&dst_rq->lock);
1186
1187         /*
1188          * Because we have preemption enabled we can get migrated around and
1189          * end try selecting ourselves (current == env->p) as a swap candidate.
1190          */
1191         if (cur == env->p)
1192                 goto unlock;
1193
1194         /*
1195          * "imp" is the fault differential for the source task between the
1196          * source and destination node. Calculate the total differential for
1197          * the source task and potential destination task. The more negative
1198          * the value is, the more rmeote accesses that would be expected to
1199          * be incurred if the tasks were swapped.
1200          */
1201         if (cur) {
1202                 /* Skip this swap candidate if cannot move to the source cpu */
1203                 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
1204                         goto unlock;
1205
1206                 /*
1207                  * If dst and source tasks are in the same NUMA group, or not
1208                  * in any group then look only at task weights.
1209                  */
1210                 if (cur->numa_group == env->p->numa_group) {
1211                         imp = taskimp + task_weight(cur, env->src_nid) -
1212                               task_weight(cur, env->dst_nid);
1213                         /*
1214                          * Add some hysteresis to prevent swapping the
1215                          * tasks within a group over tiny differences.
1216                          */
1217                         if (cur->numa_group)
1218                                 imp -= imp/16;
1219                 } else {
1220                         /*
1221                          * Compare the group weights. If a task is all by
1222                          * itself (not part of a group), use the task weight
1223                          * instead.
1224                          */
1225                         if (cur->numa_group)
1226                                 imp += group_weight(cur, env->src_nid) -
1227                                        group_weight(cur, env->dst_nid);
1228                         else
1229                                 imp += task_weight(cur, env->src_nid) -
1230                                        task_weight(cur, env->dst_nid);
1231                 }
1232         }
1233
1234         if (imp <= env->best_imp && moveimp <= env->best_imp)
1235                 goto unlock;
1236
1237         if (!cur) {
1238                 /* Is there capacity at our destination? */
1239                 if (env->src_stats.nr_running <= env->src_stats.task_capacity &&
1240                     !env->dst_stats.has_free_capacity)
1241                         goto unlock;
1242
1243                 goto balance;
1244         }
1245
1246         /* Balance doesn't matter much if we're running a task per cpu */
1247         if (imp > env->best_imp && src_rq->nr_running == 1 &&
1248                         dst_rq->nr_running == 1)
1249                 goto assign;
1250
1251         /*
1252          * In the overloaded case, try and keep the load balanced.
1253          */
1254 balance:
1255         load = task_h_load(env->p);
1256         dst_load = env->dst_stats.load + load;
1257         src_load = env->src_stats.load - load;
1258
1259         if (moveimp > imp && moveimp > env->best_imp) {
1260                 /*
1261                  * If the improvement from just moving env->p direction is
1262                  * better than swapping tasks around, check if a move is
1263                  * possible. Store a slightly smaller score than moveimp,
1264                  * so an actually idle CPU will win.
1265                  */
1266                 if (!load_too_imbalanced(src_load, dst_load, env)) {
1267                         imp = moveimp - 1;
1268                         cur = NULL;
1269                         goto assign;
1270                 }
1271         }
1272
1273         if (imp <= env->best_imp)
1274                 goto unlock;
1275
1276         if (cur) {
1277                 load = task_h_load(cur);
1278                 dst_load -= load;
1279                 src_load += load;
1280         }
1281
1282         if (load_too_imbalanced(src_load, dst_load, env))
1283                 goto unlock;
1284
1285         /*
1286          * One idle CPU per node is evaluated for a task numa move.
1287          * Call select_idle_sibling to maybe find a better one.
1288          */
1289         if (!cur)
1290                 env->dst_cpu = select_idle_sibling(env->p, env->dst_cpu);
1291
1292 assign:
1293         task_numa_assign(env, cur, imp);
1294 unlock:
1295         rcu_read_unlock();
1296 }
1297
1298 static void task_numa_find_cpu(struct task_numa_env *env,
1299                                 long taskimp, long groupimp)
1300 {
1301         int cpu;
1302
1303         for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
1304                 /* Skip this CPU if the source task cannot migrate */
1305                 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
1306                         continue;
1307
1308                 env->dst_cpu = cpu;
1309                 task_numa_compare(env, taskimp, groupimp);
1310         }
1311 }
1312
1313 static int task_numa_migrate(struct task_struct *p)
1314 {
1315         struct task_numa_env env = {
1316                 .p = p,
1317
1318                 .src_cpu = task_cpu(p),
1319                 .src_nid = task_node(p),
1320
1321                 .imbalance_pct = 112,
1322
1323                 .best_task = NULL,
1324                 .best_imp = 0,
1325                 .best_cpu = -1
1326         };
1327         struct sched_domain *sd;
1328         unsigned long taskweight, groupweight;
1329         int nid, ret;
1330         long taskimp, groupimp;
1331
1332         /*
1333          * Pick the lowest SD_NUMA domain, as that would have the smallest
1334          * imbalance and would be the first to start moving tasks about.
1335          *
1336          * And we want to avoid any moving of tasks about, as that would create
1337          * random movement of tasks -- counter the numa conditions we're trying
1338          * to satisfy here.
1339          */
1340         rcu_read_lock();
1341         sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
1342         if (sd)
1343                 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
1344         rcu_read_unlock();
1345
1346         /*
1347          * Cpusets can break the scheduler domain tree into smaller
1348          * balance domains, some of which do not cross NUMA boundaries.
1349          * Tasks that are "trapped" in such domains cannot be migrated
1350          * elsewhere, so there is no point in (re)trying.
1351          */
1352         if (unlikely(!sd)) {
1353                 p->numa_preferred_nid = task_node(p);
1354                 return -EINVAL;
1355         }
1356
1357         taskweight = task_weight(p, env.src_nid);
1358         groupweight = group_weight(p, env.src_nid);
1359         update_numa_stats(&env.src_stats, env.src_nid);
1360         env.dst_nid = p->numa_preferred_nid;
1361         taskimp = task_weight(p, env.dst_nid) - taskweight;
1362         groupimp = group_weight(p, env.dst_nid) - groupweight;
1363         update_numa_stats(&env.dst_stats, env.dst_nid);
1364
1365         /* Try to find a spot on the preferred nid. */
1366         task_numa_find_cpu(&env, taskimp, groupimp);
1367
1368         /* No space available on the preferred nid. Look elsewhere. */
1369         if (env.best_cpu == -1) {
1370                 for_each_online_node(nid) {
1371                         if (nid == env.src_nid || nid == p->numa_preferred_nid)
1372                                 continue;
1373
1374                         /* Only consider nodes where both task and groups benefit */
1375                         taskimp = task_weight(p, nid) - taskweight;
1376                         groupimp = group_weight(p, nid) - groupweight;
1377                         if (taskimp < 0 && groupimp < 0)
1378                                 continue;
1379
1380                         env.dst_nid = nid;
1381                         update_numa_stats(&env.dst_stats, env.dst_nid);
1382                         task_numa_find_cpu(&env, taskimp, groupimp);
1383                 }
1384         }
1385
1386         /*
1387          * If the task is part of a workload that spans multiple NUMA nodes,
1388          * and is migrating into one of the workload's active nodes, remember
1389          * this node as the task's preferred numa node, so the workload can
1390          * settle down.
1391          * A task that migrated to a second choice node will be better off
1392          * trying for a better one later. Do not set the preferred node here.
1393          */
1394         if (p->numa_group) {
1395                 if (env.best_cpu == -1)
1396                         nid = env.src_nid;
1397                 else
1398                         nid = env.dst_nid;
1399
1400                 if (node_isset(nid, p->numa_group->active_nodes))
1401                         sched_setnuma(p, env.dst_nid);
1402         }
1403
1404         /* No better CPU than the current one was found. */
1405         if (env.best_cpu == -1)
1406                 return -EAGAIN;
1407
1408         /*
1409          * Reset the scan period if the task is being rescheduled on an
1410          * alternative node to recheck if the tasks is now properly placed.
1411          */
1412         p->numa_scan_period = task_scan_min(p);
1413
1414         if (env.best_task == NULL) {
1415                 ret = migrate_task_to(p, env.best_cpu);
1416                 if (ret != 0)
1417                         trace_sched_stick_numa(p, env.src_cpu, env.best_cpu);
1418                 return ret;
1419         }
1420
1421         ret = migrate_swap(p, env.best_task);
1422         if (ret != 0)
1423                 trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task));
1424         put_task_struct(env.best_task);
1425         return ret;
1426 }
1427
1428 /* Attempt to migrate a task to a CPU on the preferred node. */
1429 static void numa_migrate_preferred(struct task_struct *p)
1430 {
1431         unsigned long interval = HZ;
1432
1433         /* This task has no NUMA fault statistics yet */
1434         if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults_memory))
1435                 return;
1436
1437         /* Periodically retry migrating the task to the preferred node */
1438         interval = min(interval, msecs_to_jiffies(p->numa_scan_period) / 16);
1439         p->numa_migrate_retry = jiffies + interval;
1440
1441         /* Success if task is already running on preferred CPU */
1442         if (task_node(p) == p->numa_preferred_nid)
1443                 return;
1444
1445         /* Otherwise, try migrate to a CPU on the preferred node */
1446         task_numa_migrate(p);
1447 }
1448
1449 /*
1450  * Find the nodes on which the workload is actively running. We do this by
1451  * tracking the nodes from which NUMA hinting faults are triggered. This can
1452  * be different from the set of nodes where the workload's memory is currently
1453  * located.
1454  *
1455  * The bitmask is used to make smarter decisions on when to do NUMA page
1456  * migrations, To prevent flip-flopping, and excessive page migrations, nodes
1457  * are added when they cause over 6/16 of the maximum number of faults, but
1458  * only removed when they drop below 3/16.
1459  */
1460 static void update_numa_active_node_mask(struct numa_group *numa_group)
1461 {
1462         unsigned long faults, max_faults = 0;
1463         int nid;
1464
1465         for_each_online_node(nid) {
1466                 faults = group_faults_cpu(numa_group, nid);
1467                 if (faults > max_faults)
1468                         max_faults = faults;
1469         }
1470
1471         for_each_online_node(nid) {
1472                 faults = group_faults_cpu(numa_group, nid);
1473                 if (!node_isset(nid, numa_group->active_nodes)) {
1474                         if (faults > max_faults * 6 / 16)
1475                                 node_set(nid, numa_group->active_nodes);
1476                 } else if (faults < max_faults * 3 / 16)
1477                         node_clear(nid, numa_group->active_nodes);
1478         }
1479 }
1480
1481 /*
1482  * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS
1483  * increments. The more local the fault statistics are, the higher the scan
1484  * period will be for the next scan window. If local/(local+remote) ratio is
1485  * below NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS)
1486  * the scan period will decrease. Aim for 70% local accesses.
1487  */
1488 #define NUMA_PERIOD_SLOTS 10
1489 #define NUMA_PERIOD_THRESHOLD 7
1490
1491 /*
1492  * Increase the scan period (slow down scanning) if the majority of
1493  * our memory is already on our local node, or if the majority of
1494  * the page accesses are shared with other processes.
1495  * Otherwise, decrease the scan period.
1496  */
1497 static void update_task_scan_period(struct task_struct *p,
1498                         unsigned long shared, unsigned long private)
1499 {
1500         unsigned int period_slot;
1501         int ratio;
1502         int diff;
1503
1504         unsigned long remote = p->numa_faults_locality[0];
1505         unsigned long local = p->numa_faults_locality[1];
1506
1507         /*
1508          * If there were no record hinting faults then either the task is
1509          * completely idle or all activity is areas that are not of interest
1510          * to automatic numa balancing. Scan slower
1511          */
1512         if (local + shared == 0) {
1513                 p->numa_scan_period = min(p->numa_scan_period_max,
1514                         p->numa_scan_period << 1);
1515
1516                 p->mm->numa_next_scan = jiffies +
1517                         msecs_to_jiffies(p->numa_scan_period);
1518
1519                 return;
1520         }
1521
1522         /*
1523          * Prepare to scale scan period relative to the current period.
1524          *       == NUMA_PERIOD_THRESHOLD scan period stays the same
1525          *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
1526          *       >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
1527          */
1528         period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
1529         ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
1530         if (ratio >= NUMA_PERIOD_THRESHOLD) {
1531                 int slot = ratio - NUMA_PERIOD_THRESHOLD;
1532                 if (!slot)
1533                         slot = 1;
1534                 diff = slot * period_slot;
1535         } else {
1536                 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
1537
1538                 /*
1539                  * Scale scan rate increases based on sharing. There is an
1540                  * inverse relationship between the degree of sharing and
1541                  * the adjustment made to the scanning period. Broadly
1542                  * speaking the intent is that there is little point
1543                  * scanning faster if shared accesses dominate as it may
1544                  * simply bounce migrations uselessly
1545                  */
1546                 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared + 1));
1547                 diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
1548         }
1549
1550         p->numa_scan_period = clamp(p->numa_scan_period + diff,
1551                         task_scan_min(p), task_scan_max(p));
1552         memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1553 }
1554
1555 /*
1556  * Get the fraction of time the task has been running since the last
1557  * NUMA placement cycle. The scheduler keeps similar statistics, but
1558  * decays those on a 32ms period, which is orders of magnitude off
1559  * from the dozens-of-seconds NUMA balancing period. Use the scheduler
1560  * stats only if the task is so new there are no NUMA statistics yet.
1561  */
1562 static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
1563 {
1564         u64 runtime, delta, now;
1565         /* Use the start of this time slice to avoid calculations. */
1566         now = p->se.exec_start;
1567         runtime = p->se.sum_exec_runtime;
1568
1569         if (p->last_task_numa_placement) {
1570                 delta = runtime - p->last_sum_exec_runtime;
1571                 *period = now - p->last_task_numa_placement;
1572         } else {
1573                 delta = p->se.avg.runnable_avg_sum;
1574                 *period = p->se.avg.runnable_avg_period;
1575         }
1576
1577         p->last_sum_exec_runtime = runtime;
1578         p->last_task_numa_placement = now;
1579
1580         return delta;
1581 }
1582
1583 static void task_numa_placement(struct task_struct *p)
1584 {
1585         int seq, nid, max_nid = -1, max_group_nid = -1;
1586         unsigned long max_faults = 0, max_group_faults = 0;
1587         unsigned long fault_types[2] = { 0, 0 };
1588         unsigned long total_faults;
1589         u64 runtime, period;
1590         spinlock_t *group_lock = NULL;
1591
1592         seq = ACCESS_ONCE(p->mm->numa_scan_seq);
1593         if (p->numa_scan_seq == seq)
1594                 return;
1595         p->numa_scan_seq = seq;
1596         p->numa_scan_period_max = task_scan_max(p);
1597
1598         total_faults = p->numa_faults_locality[0] +
1599                        p->numa_faults_locality[1];
1600         runtime = numa_get_avg_runtime(p, &period);
1601
1602         /* If the task is part of a group prevent parallel updates to group stats */
1603         if (p->numa_group) {
1604                 group_lock = &p->numa_group->lock;
1605                 spin_lock_irq(group_lock);
1606         }
1607
1608         /* Find the node with the highest number of faults */
1609         for_each_online_node(nid) {
1610                 unsigned long faults = 0, group_faults = 0;
1611                 int priv, i;
1612
1613                 for (priv = 0; priv < NR_NUMA_HINT_FAULT_TYPES; priv++) {
1614                         long diff, f_diff, f_weight;
1615
1616                         i = task_faults_idx(nid, priv);
1617
1618                         /* Decay existing window, copy faults since last scan */
1619                         diff = p->numa_faults_buffer_memory[i] - p->numa_faults_memory[i] / 2;
1620                         fault_types[priv] += p->numa_faults_buffer_memory[i];
1621                         p->numa_faults_buffer_memory[i] = 0;
1622
1623                         /*
1624                          * Normalize the faults_from, so all tasks in a group
1625                          * count according to CPU use, instead of by the raw
1626                          * number of faults. Tasks with little runtime have
1627                          * little over-all impact on throughput, and thus their
1628                          * faults are less important.
1629                          */
1630                         f_weight = div64_u64(runtime << 16, period + 1);
1631                         f_weight = (f_weight * p->numa_faults_buffer_cpu[i]) /
1632                                    (total_faults + 1);
1633                         f_diff = f_weight - p->numa_faults_cpu[i] / 2;
1634                         p->numa_faults_buffer_cpu[i] = 0;
1635
1636                         p->numa_faults_memory[i] += diff;
1637                         p->numa_faults_cpu[i] += f_diff;
1638                         faults += p->numa_faults_memory[i];
1639                         p->total_numa_faults += diff;
1640                         if (p->numa_group) {
1641                                 /* safe because we can only change our own group */
1642                                 p->numa_group->faults[i] += diff;
1643                                 p->numa_group->faults_cpu[i] += f_diff;
1644                                 p->numa_group->total_faults += diff;
1645                                 group_faults += p->numa_group->faults[i];
1646                         }
1647                 }
1648
1649                 if (faults > max_faults) {
1650                         max_faults = faults;
1651                         max_nid = nid;
1652                 }
1653
1654                 if (group_faults > max_group_faults) {
1655                         max_group_faults = group_faults;
1656                         max_group_nid = nid;
1657                 }
1658         }
1659
1660         update_task_scan_period(p, fault_types[0], fault_types[1]);
1661
1662         if (p->numa_group) {
1663                 update_numa_active_node_mask(p->numa_group);
1664                 spin_unlock_irq(group_lock);
1665                 max_nid = max_group_nid;
1666         }
1667
1668         if (max_faults) {
1669                 /* Set the new preferred node */
1670                 if (max_nid != p->numa_preferred_nid)
1671                         sched_setnuma(p, max_nid);
1672
1673                 if (task_node(p) != p->numa_preferred_nid)
1674                         numa_migrate_preferred(p);
1675         }
1676 }
1677
1678 static inline int get_numa_group(struct numa_group *grp)
1679 {
1680         return atomic_inc_not_zero(&grp->refcount);
1681 }
1682
1683 static inline void put_numa_group(struct numa_group *grp)
1684 {
1685         if (atomic_dec_and_test(&grp->refcount))
1686                 kfree_rcu(grp, rcu);
1687 }
1688
1689 static void task_numa_group(struct task_struct *p, int cpupid, int flags,
1690                         int *priv)
1691 {
1692         struct numa_group *grp, *my_grp;
1693         struct task_struct *tsk;
1694         bool join = false;
1695         int cpu = cpupid_to_cpu(cpupid);
1696         int i;
1697
1698         if (unlikely(!p->numa_group)) {
1699                 unsigned int size = sizeof(struct numa_group) +
1700                                     4*nr_node_ids*sizeof(unsigned long);
1701
1702                 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
1703                 if (!grp)
1704                         return;
1705
1706                 atomic_set(&grp->refcount, 1);
1707                 spin_lock_init(&grp->lock);
1708                 INIT_LIST_HEAD(&grp->task_list);
1709                 grp->gid = p->pid;
1710                 /* Second half of the array tracks nids where faults happen */
1711                 grp->faults_cpu = grp->faults + NR_NUMA_HINT_FAULT_TYPES *
1712                                                 nr_node_ids;
1713
1714                 node_set(task_node(current), grp->active_nodes);
1715
1716                 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
1717                         grp->faults[i] = p->numa_faults_memory[i];
1718
1719                 grp->total_faults = p->total_numa_faults;
1720
1721                 list_add(&p->numa_entry, &grp->task_list);
1722                 grp->nr_tasks++;
1723                 rcu_assign_pointer(p->numa_group, grp);
1724         }
1725
1726         rcu_read_lock();
1727         tsk = ACCESS_ONCE(cpu_rq(cpu)->curr);
1728
1729         if (!cpupid_match_pid(tsk, cpupid))
1730                 goto no_join;
1731
1732         grp = rcu_dereference(tsk->numa_group);
1733         if (!grp)
1734                 goto no_join;
1735
1736         my_grp = p->numa_group;
1737         if (grp == my_grp)
1738                 goto no_join;
1739
1740         /*
1741          * Only join the other group if its bigger; if we're the bigger group,
1742          * the other task will join us.
1743          */
1744         if (my_grp->nr_tasks > grp->nr_tasks)
1745                 goto no_join;
1746
1747         /*
1748          * Tie-break on the grp address.
1749          */
1750         if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
1751                 goto no_join;
1752
1753         /* Always join threads in the same process. */
1754         if (tsk->mm == current->mm)
1755                 join = true;
1756
1757         /* Simple filter to avoid false positives due to PID collisions */
1758         if (flags & TNF_SHARED)
1759                 join = true;
1760
1761         /* Update priv based on whether false sharing was detected */
1762         *priv = !join;
1763
1764         if (join && !get_numa_group(grp))
1765                 goto no_join;
1766
1767         rcu_read_unlock();
1768
1769         if (!join)
1770                 return;
1771
1772         BUG_ON(irqs_disabled());
1773         double_lock_irq(&my_grp->lock, &grp->lock);
1774
1775         for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++) {
1776                 my_grp->faults[i] -= p->numa_faults_memory[i];
1777                 grp->faults[i] += p->numa_faults_memory[i];
1778         }
1779         my_grp->total_faults -= p->total_numa_faults;
1780         grp->total_faults += p->total_numa_faults;
1781
1782         list_move(&p->numa_entry, &grp->task_list);
1783         my_grp->nr_tasks--;
1784         grp->nr_tasks++;
1785
1786         spin_unlock(&my_grp->lock);
1787         spin_unlock_irq(&grp->lock);
1788
1789         rcu_assign_pointer(p->numa_group, grp);
1790
1791         put_numa_group(my_grp);
1792         return;
1793
1794 no_join:
1795         rcu_read_unlock();
1796         return;
1797 }
1798
1799 void task_numa_free(struct task_struct *p)
1800 {
1801         struct numa_group *grp = p->numa_group;
1802         void *numa_faults = p->numa_faults_memory;
1803         unsigned long flags;
1804         int i;
1805
1806         if (grp) {
1807                 spin_lock_irqsave(&grp->lock, flags);
1808                 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
1809                         grp->faults[i] -= p->numa_faults_memory[i];
1810                 grp->total_faults -= p->total_numa_faults;
1811
1812                 list_del(&p->numa_entry);
1813                 grp->nr_tasks--;
1814                 spin_unlock_irqrestore(&grp->lock, flags);
1815                 RCU_INIT_POINTER(p->numa_group, NULL);
1816                 put_numa_group(grp);
1817         }
1818
1819         p->numa_faults_memory = NULL;
1820         p->numa_faults_buffer_memory = NULL;
1821         p->numa_faults_cpu= NULL;
1822         p->numa_faults_buffer_cpu = NULL;
1823         kfree(numa_faults);
1824 }
1825
1826 /*
1827  * Got a PROT_NONE fault for a page on @node.
1828  */
1829 void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
1830 {
1831         struct task_struct *p = current;
1832         bool migrated = flags & TNF_MIGRATED;
1833         int cpu_node = task_node(current);
1834         int local = !!(flags & TNF_FAULT_LOCAL);
1835         int priv;
1836
1837         if (!numabalancing_enabled)
1838                 return;
1839
1840         /* for example, ksmd faulting in a user's mm */
1841         if (!p->mm)
1842                 return;
1843
1844         /* Allocate buffer to track faults on a per-node basis */
1845         if (unlikely(!p->numa_faults_memory)) {
1846                 int size = sizeof(*p->numa_faults_memory) *
1847                            NR_NUMA_HINT_FAULT_BUCKETS * nr_node_ids;
1848
1849                 p->numa_faults_memory = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);
1850                 if (!p->numa_faults_memory)
1851                         return;
1852
1853                 BUG_ON(p->numa_faults_buffer_memory);
1854                 /*
1855                  * The averaged statistics, shared & private, memory & cpu,
1856                  * occupy the first half of the array. The second half of the
1857                  * array is for current counters, which are averaged into the
1858                  * first set by task_numa_placement.
1859                  */
1860                 p->numa_faults_cpu = p->numa_faults_memory + (2 * nr_node_ids);
1861                 p->numa_faults_buffer_memory = p->numa_faults_memory + (4 * nr_node_ids);
1862                 p->numa_faults_buffer_cpu = p->numa_faults_memory + (6 * nr_node_ids);
1863                 p->total_numa_faults = 0;
1864                 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1865         }
1866
1867         /*
1868          * First accesses are treated as private, otherwise consider accesses
1869          * to be private if the accessing pid has not changed
1870          */
1871         if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
1872                 priv = 1;
1873         } else {
1874                 priv = cpupid_match_pid(p, last_cpupid);
1875                 if (!priv && !(flags & TNF_NO_GROUP))
1876                         task_numa_group(p, last_cpupid, flags, &priv);
1877         }
1878
1879         /*
1880          * If a workload spans multiple NUMA nodes, a shared fault that
1881          * occurs wholly within the set of nodes that the workload is
1882          * actively using should be counted as local. This allows the
1883          * scan rate to slow down when a workload has settled down.
1884          */
1885         if (!priv && !local && p->numa_group &&
1886                         node_isset(cpu_node, p->numa_group->active_nodes) &&
1887                         node_isset(mem_node, p->numa_group->active_nodes))
1888                 local = 1;
1889
1890         task_numa_placement(p);
1891
1892         /*
1893          * Retry task to preferred node migration periodically, in case it
1894          * case it previously failed, or the scheduler moved us.
1895          */
1896         if (time_after(jiffies, p->numa_migrate_retry))
1897                 numa_migrate_preferred(p);
1898
1899         if (migrated)
1900                 p->numa_pages_migrated += pages;
1901
1902         p->numa_faults_buffer_memory[task_faults_idx(mem_node, priv)] += pages;
1903         p->numa_faults_buffer_cpu[task_faults_idx(cpu_node, priv)] += pages;
1904         p->numa_faults_locality[local] += pages;
1905 }
1906
1907 static void reset_ptenuma_scan(struct task_struct *p)
1908 {
1909         ACCESS_ONCE(p->mm->numa_scan_seq)++;
1910         p->mm->numa_scan_offset = 0;
1911 }
1912
1913 /*
1914  * The expensive part of numa migration is done from task_work context.
1915  * Triggered from task_tick_numa().
1916  */
1917 void task_numa_work(struct callback_head *work)
1918 {
1919         unsigned long migrate, next_scan, now = jiffies;
1920         struct task_struct *p = current;
1921         struct mm_struct *mm = p->mm;
1922         struct vm_area_struct *vma;
1923         unsigned long start, end;
1924         unsigned long nr_pte_updates = 0;
1925         long pages;
1926
1927         WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work));
1928
1929         work->next = work; /* protect against double add */
1930         /*
1931          * Who cares about NUMA placement when they're dying.
1932          *
1933          * NOTE: make sure not to dereference p->mm before this check,
1934          * exit_task_work() happens _after_ exit_mm() so we could be called
1935          * without p->mm even though we still had it when we enqueued this
1936          * work.
1937          */
1938         if (p->flags & PF_EXITING)
1939                 return;
1940
1941         if (!mm->numa_next_scan) {
1942                 mm->numa_next_scan = now +
1943                         msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
1944         }
1945
1946         /*
1947          * Enforce maximal scan/migration frequency..
1948          */
1949         migrate = mm->numa_next_scan;
1950         if (time_before(now, migrate))
1951                 return;
1952
1953         if (p->numa_scan_period == 0) {
1954                 p->numa_scan_period_max = task_scan_max(p);
1955                 p->numa_scan_period = task_scan_min(p);
1956         }
1957
1958         next_scan = now + msecs_to_jiffies(p->numa_scan_period);
1959         if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
1960                 return;
1961
1962         /*
1963          * Delay this task enough that another task of this mm will likely win
1964          * the next time around.
1965          */
1966         p->node_stamp += 2 * TICK_NSEC;
1967
1968         start = mm->numa_scan_offset;
1969         pages = sysctl_numa_balancing_scan_size;
1970         pages <<= 20 - PAGE_SHIFT; /* MB in pages */
1971         if (!pages)
1972                 return;
1973
1974         down_read(&mm->mmap_sem);
1975         vma = find_vma(mm, start);
1976         if (!vma) {
1977                 reset_ptenuma_scan(p);
1978                 start = 0;
1979                 vma = mm->mmap;
1980         }
1981         for (; vma; vma = vma->vm_next) {
1982                 if (!vma_migratable(vma) || !vma_policy_mof(vma))
1983                         continue;
1984
1985                 /*
1986                  * Shared library pages mapped by multiple processes are not
1987                  * migrated as it is expected they are cache replicated. Avoid
1988                  * hinting faults in read-only file-backed mappings or the vdso
1989                  * as migrating the pages will be of marginal benefit.
1990                  */
1991                 if (!vma->vm_mm ||
1992                     (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
1993                         continue;
1994
1995                 /*
1996                  * Skip inaccessible VMAs to avoid any confusion between
1997                  * PROT_NONE and NUMA hinting ptes
1998                  */
1999                 if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
2000                         continue;
2001
2002                 do {
2003                         start = max(start, vma->vm_start);
2004                         end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
2005                         end = min(end, vma->vm_end);
2006                         nr_pte_updates += change_prot_numa(vma, start, end);
2007
2008                         /*
2009                          * Scan sysctl_numa_balancing_scan_size but ensure that
2010                          * at least one PTE is updated so that unused virtual
2011                          * address space is quickly skipped.
2012                          */
2013                         if (nr_pte_updates)
2014                                 pages -= (end - start) >> PAGE_SHIFT;
2015
2016                         start = end;
2017                         if (pages <= 0)
2018                                 goto out;
2019
2020                         cond_resched();
2021                 } while (end != vma->vm_end);
2022         }
2023
2024 out:
2025         /*
2026          * It is possible to reach the end of the VMA list but the last few
2027          * VMAs are not guaranteed to the vma_migratable. If they are not, we
2028          * would find the !migratable VMA on the next scan but not reset the
2029          * scanner to the start so check it now.
2030          */
2031         if (vma)
2032                 mm->numa_scan_offset = start;
2033         else
2034                 reset_ptenuma_scan(p);
2035         up_read(&mm->mmap_sem);
2036 }
2037
2038 /*
2039  * Drive the periodic memory faults..
2040  */
2041 void task_tick_numa(struct rq *rq, struct task_struct *curr)
2042 {
2043         struct callback_head *work = &curr->numa_work;
2044         u64 period, now;
2045
2046         /*
2047          * We don't care about NUMA placement if we don't have memory.
2048          */
2049         if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
2050                 return;
2051
2052         /*
2053          * Using runtime rather than walltime has the dual advantage that
2054          * we (mostly) drive the selection from busy threads and that the
2055          * task needs to have done some actual work before we bother with
2056          * NUMA placement.
2057          */
2058         now = curr->se.sum_exec_runtime;
2059         period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
2060
2061         if (now - curr->node_stamp > period) {
2062                 if (!curr->node_stamp)
2063                         curr->numa_scan_period = task_scan_min(curr);
2064                 curr->node_stamp += period;
2065
2066                 if (!time_before(jiffies, curr->mm->numa_next_scan)) {
2067                         init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */
2068                         task_work_add(curr, work, true);
2069                 }
2070         }
2071 }
2072 #else
2073 static void task_tick_numa(struct rq *rq, struct task_struct *curr)
2074 {
2075 }
2076
2077 static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
2078 {
2079 }
2080
2081 static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
2082 {
2083 }
2084 #endif /* CONFIG_NUMA_BALANCING */
2085
2086 static void
2087 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2088 {
2089         update_load_add(&cfs_rq->load, se->load.weight);
2090         if (!parent_entity(se))
2091                 update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
2092 #ifdef CONFIG_SMP
2093         if (entity_is_task(se)) {
2094                 struct rq *rq = rq_of(cfs_rq);
2095
2096                 account_numa_enqueue(rq, task_of(se));
2097                 list_add(&se->group_node, &rq->cfs_tasks);
2098         }
2099 #endif
2100         cfs_rq->nr_running++;
2101 }
2102
2103 static void
2104 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2105 {
2106         update_load_sub(&cfs_rq->load, se->load.weight);
2107         if (!parent_entity(se))
2108                 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
2109         if (entity_is_task(se)) {
2110                 account_numa_dequeue(rq_of(cfs_rq), task_of(se));
2111                 list_del_init(&se->group_node);
2112         }
2113         cfs_rq->nr_running--;
2114 }
2115
2116 #ifdef CONFIG_FAIR_GROUP_SCHED
2117 # ifdef CONFIG_SMP
2118 static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
2119 {
2120         long tg_weight;
2121
2122         /*
2123          * Use this CPU's actual weight instead of the last load_contribution
2124          * to gain a more accurate current total weight. See
2125          * update_cfs_rq_load_contribution().
2126          */
2127         tg_weight = atomic_long_read(&tg->load_avg);
2128         tg_weight -= cfs_rq->tg_load_contrib;
2129         tg_weight += cfs_rq->load.weight;
2130
2131         return tg_weight;
2132 }
2133
2134 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2135 {
2136         long tg_weight, load, shares;
2137
2138         tg_weight = calc_tg_weight(tg, cfs_rq);
2139         load = cfs_rq->load.weight;
2140
2141         shares = (tg->shares * load);
2142         if (tg_weight)
2143                 shares /= tg_weight;
2144
2145         if (shares < MIN_SHARES)
2146                 shares = MIN_SHARES;
2147         if (shares > tg->shares)
2148                 shares = tg->shares;
2149
2150         return shares;
2151 }
2152 # else /* CONFIG_SMP */
2153 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2154 {
2155         return tg->shares;
2156 }
2157 # endif /* CONFIG_SMP */
2158 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
2159                             unsigned long weight)
2160 {
2161         if (se->on_rq) {
2162                 /* commit outstanding execution time */
2163                 if (cfs_rq->curr == se)
2164                         update_curr(cfs_rq);
2165                 account_entity_dequeue(cfs_rq, se);
2166         }
2167
2168         update_load_set(&se->load, weight);
2169
2170         if (se->on_rq)
2171                 account_entity_enqueue(cfs_rq, se);
2172 }
2173
2174 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
2175
2176 static void update_cfs_shares(struct cfs_rq *cfs_rq)
2177 {
2178         struct task_group *tg;
2179         struct sched_entity *se;
2180         long shares;
2181
2182         tg = cfs_rq->tg;
2183         se = tg->se[cpu_of(rq_of(cfs_rq))];
2184         if (!se || throttled_hierarchy(cfs_rq))
2185                 return;
2186 #ifndef CONFIG_SMP
2187         if (likely(se->load.weight == tg->shares))
2188                 return;
2189 #endif
2190         shares = calc_cfs_shares(cfs_rq, tg);
2191
2192         reweight_entity(cfs_rq_of(se), se, shares);
2193 }
2194 #else /* CONFIG_FAIR_GROUP_SCHED */
2195 static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
2196 {
2197 }
2198 #endif /* CONFIG_FAIR_GROUP_SCHED */
2199
2200 #ifdef CONFIG_SMP
2201 /*
2202  * We choose a half-life close to 1 scheduling period.
2203  * Note: The tables below are dependent on this value.
2204  */
2205 #define LOAD_AVG_PERIOD 32
2206 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
2207 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */
2208
2209 /* Precomputed fixed inverse multiplies for multiplication by y^n */
2210 static const u32 runnable_avg_yN_inv[] = {
2211         0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
2212         0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
2213         0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
2214         0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
2215         0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
2216         0x85aac367, 0x82cd8698,
2217 };
2218
2219 /*
2220  * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
2221  * over-estimates when re-combining.
2222  */
2223 static const u32 runnable_avg_yN_sum[] = {
2224             0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
2225          9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
2226         17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
2227 };
2228
2229 /*
2230  * Approximate:
2231  *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
2232  */
2233 static __always_inline u64 decay_load(u64 val, u64 n)
2234 {
2235         unsigned int local_n;
2236
2237         if (!n)
2238                 return val;
2239         else if (unlikely(n > LOAD_AVG_PERIOD * 63))
2240                 return 0;
2241
2242         /* after bounds checking we can collapse to 32-bit */
2243         local_n = n;
2244
2245         /*
2246          * As y^PERIOD = 1/2, we can combine
2247          *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
2248          * With a look-up table which covers y^n (n<PERIOD)
2249          *
2250          * To achieve constant time decay_load.
2251          */
2252         if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
2253                 val >>= local_n / LOAD_AVG_PERIOD;
2254                 local_n %= LOAD_AVG_PERIOD;
2255         }
2256
2257         val *= runnable_avg_yN_inv[local_n];
2258         /* We don't use SRR here since we always want to round down. */
2259         return val >> 32;
2260 }
2261
2262 /*
2263  * For updates fully spanning n periods, the contribution to runnable
2264  * average will be: \Sum 1024*y^n
2265  *
2266  * We can compute this reasonably efficiently by combining:
2267  *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
2268  */
2269 static u32 __compute_runnable_contrib(u64 n)
2270 {
2271         u32 contrib = 0;
2272
2273         if (likely(n <= LOAD_AVG_PERIOD))
2274                 return runnable_avg_yN_sum[n];
2275         else if (unlikely(n >= LOAD_AVG_MAX_N))
2276                 return LOAD_AVG_MAX;
2277
2278         /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
2279         do {
2280                 contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
2281                 contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
2282
2283                 n -= LOAD_AVG_PERIOD;
2284         } while (n > LOAD_AVG_PERIOD);
2285
2286         contrib = decay_load(contrib, n);
2287         return contrib + runnable_avg_yN_sum[n];
2288 }
2289
2290 /*
2291  * We can represent the historical contribution to runnable average as the
2292  * coefficients of a geometric series.  To do this we sub-divide our runnable
2293  * history into segments of approximately 1ms (1024us); label the segment that
2294  * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
2295  *
2296  * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
2297  *      p0            p1           p2
2298  *     (now)       (~1ms ago)  (~2ms ago)
2299  *
2300  * Let u_i denote the fraction of p_i that the entity was runnable.
2301  *
2302  * We then designate the fractions u_i as our co-efficients, yielding the
2303  * following representation of historical load:
2304  *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
2305  *
2306  * We choose y based on the with of a reasonably scheduling period, fixing:
2307  *   y^32 = 0.5
2308  *
2309  * This means that the contribution to load ~32ms ago (u_32) will be weighted
2310  * approximately half as much as the contribution to load within the last ms
2311  * (u_0).
2312  *
2313  * When a period "rolls over" and we have new u_0`, multiplying the previous
2314  * sum again by y is sufficient to update:
2315  *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
2316  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
2317  */
2318 static __always_inline int __update_entity_runnable_avg(u64 now,
2319                                                         struct sched_avg *sa,
2320                                                         int runnable)
2321 {
2322         u64 delta, periods;
2323         u32 runnable_contrib;
2324         int delta_w, decayed = 0;
2325
2326         delta = now - sa->last_runnable_update;
2327         /*
2328          * This should only happen when time goes backwards, which it
2329          * unfortunately does during sched clock init when we swap over to TSC.
2330          */
2331         if ((s64)delta < 0) {
2332                 sa->last_runnable_update = now;
2333                 return 0;
2334         }
2335
2336         /*
2337          * Use 1024ns as the unit of measurement since it's a reasonable
2338          * approximation of 1us and fast to compute.
2339          */
2340         delta >>= 10;
2341         if (!delta)
2342                 return 0;
2343         sa->last_runnable_update = now;
2344
2345         /* delta_w is the amount already accumulated against our next period */
2346         delta_w = sa->runnable_avg_period % 1024;
2347         if (delta + delta_w >= 1024) {
2348                 /* period roll-over */
2349                 decayed = 1;
2350
2351                 /*
2352                  * Now that we know we're crossing a period boundary, figure
2353                  * out how much from delta we need to complete the current
2354                  * period and accrue it.
2355                  */
2356                 delta_w = 1024 - delta_w;
2357                 if (runnable)
2358                         sa->runnable_avg_sum += delta_w;
2359                 sa->runnable_avg_period += delta_w;
2360
2361                 delta -= delta_w;
2362
2363                 /* Figure out how many additional periods this update spans */
2364                 periods = delta / 1024;
2365                 delta %= 1024;
2366
2367                 sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
2368                                                   periods + 1);
2369                 sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
2370                                                      periods + 1);
2371
2372                 /* Efficiently calculate \sum (1..n_period) 1024*y^i */
2373                 runnable_contrib = __compute_runnable_contrib(periods);
2374                 if (runnable)
2375                         sa->runnable_avg_sum += runnable_contrib;
2376                 sa->runnable_avg_period += runnable_contrib;
2377         }
2378
2379         /* Remainder of delta accrued against u_0` */
2380         if (runnable)
2381                 sa->runnable_avg_sum += delta;
2382         sa->runnable_avg_period += delta;
2383
2384         return decayed;
2385 }
2386
2387 /* Synchronize an entity's decay with its parenting cfs_rq.*/
2388 static inline u64 __synchronize_entity_decay(struct sched_entity *se)
2389 {
2390         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2391         u64 decays = atomic64_read(&cfs_rq->decay_counter);
2392
2393         decays -= se->avg.decay_count;
2394         if (!decays)
2395                 return 0;
2396
2397         se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);
2398         se->avg.decay_count = 0;
2399
2400         return decays;
2401 }
2402
2403 #ifdef CONFIG_FAIR_GROUP_SCHED
2404 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2405                                                  int force_update)
2406 {
2407         struct task_group *tg = cfs_rq->tg;
2408         long tg_contrib;
2409
2410         tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
2411         tg_contrib -= cfs_rq->tg_load_contrib;
2412
2413         if (!tg_contrib)
2414                 return;
2415
2416         if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
2417                 atomic_long_add(tg_contrib, &tg->load_avg);
2418                 cfs_rq->tg_load_contrib += tg_contrib;
2419         }
2420 }
2421
2422 /*
2423  * Aggregate cfs_rq runnable averages into an equivalent task_group
2424  * representation for computing load contributions.
2425  */
2426 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2427                                                   struct cfs_rq *cfs_rq)
2428 {
2429         struct task_group *tg = cfs_rq->tg;
2430         long contrib;
2431
2432         /* The fraction of a cpu used by this cfs_rq */
2433         contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
2434                           sa->runnable_avg_period + 1);
2435         contrib -= cfs_rq->tg_runnable_contrib;
2436
2437         if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
2438                 atomic_add(contrib, &tg->runnable_avg);
2439                 cfs_rq->tg_runnable_contrib += contrib;
2440         }
2441 }
2442
2443 static inline void __update_group_entity_contrib(struct sched_entity *se)
2444 {
2445         struct cfs_rq *cfs_rq = group_cfs_rq(se);
2446         struct task_group *tg = cfs_rq->tg;
2447         int runnable_avg;
2448
2449         u64 contrib;
2450
2451         contrib = cfs_rq->tg_load_contrib * tg->shares;
2452         se->avg.load_avg_contrib = div_u64(contrib,
2453                                      atomic_long_read(&tg->load_avg) + 1);
2454
2455         /*
2456          * For group entities we need to compute a correction term in the case
2457          * that they are consuming <1 cpu so that we would contribute the same
2458          * load as a task of equal weight.
2459          *
2460          * Explicitly co-ordinating this measurement would be expensive, but
2461          * fortunately the sum of each cpus contribution forms a usable
2462          * lower-bound on the true value.
2463          *
2464          * Consider the aggregate of 2 contributions.  Either they are disjoint
2465          * (and the sum represents true value) or they are disjoint and we are
2466          * understating by the aggregate of their overlap.
2467          *
2468          * Extending this to N cpus, for a given overlap, the maximum amount we
2469          * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of
2470          * cpus that overlap for this interval and w_i is the interval width.
2471          *
2472          * On a small machine; the first term is well-bounded which bounds the
2473          * total error since w_i is a subset of the period.  Whereas on a
2474          * larger machine, while this first term can be larger, if w_i is the
2475          * of consequential size guaranteed to see n_i*w_i quickly converge to
2476          * our upper bound of 1-cpu.
2477          */
2478         runnable_avg = atomic_read(&tg->runnable_avg);
2479         if (runnable_avg < NICE_0_LOAD) {
2480                 se->avg.load_avg_contrib *= runnable_avg;
2481                 se->avg.load_avg_contrib >>= NICE_0_SHIFT;
2482         }
2483 }
2484
2485 static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
2486 {
2487         __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
2488         __update_tg_runnable_avg(&rq->avg, &rq->cfs);
2489 }
2490 #else /* CONFIG_FAIR_GROUP_SCHED */
2491 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2492                                                  int force_update) {}
2493 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2494                                                   struct cfs_rq *cfs_rq) {}
2495 static inline void __update_group_entity_contrib(struct sched_entity *se) {}
2496 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2497 #endif /* CONFIG_FAIR_GROUP_SCHED */
2498
2499 static inline void __update_task_entity_contrib(struct sched_entity *se)
2500 {
2501         u32 contrib;
2502
2503         /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
2504         contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
2505         contrib /= (se->avg.runnable_avg_period + 1);
2506         se->avg.load_avg_contrib = scale_load(contrib);
2507 }
2508
2509 /* Compute the current contribution to load_avg by se, return any delta */
2510 static long __update_entity_load_avg_contrib(struct sched_entity *se)
2511 {
2512         long old_contrib = se->avg.load_avg_contrib;
2513
2514         if (entity_is_task(se)) {
2515                 __update_task_entity_contrib(se);
2516         } else {
2517                 __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
2518                 __update_group_entity_contrib(se);
2519         }
2520
2521         return se->avg.load_avg_contrib - old_contrib;
2522 }
2523
2524 static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
2525                                                  long load_contrib)
2526 {
2527         if (likely(load_contrib < cfs_rq->blocked_load_avg))
2528                 cfs_rq->blocked_load_avg -= load_contrib;
2529         else
2530                 cfs_rq->blocked_load_avg = 0;
2531 }
2532
2533 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
2534
2535 /* Update a sched_entity's runnable average */
2536 static inline void update_entity_load_avg(struct sched_entity *se,
2537                                           int update_cfs_rq)
2538 {
2539         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2540         long contrib_delta;
2541         u64 now;
2542
2543         /*
2544          * For a group entity we need to use their owned cfs_rq_clock_task() in
2545          * case they are the parent of a throttled hierarchy.
2546          */
2547         if (entity_is_task(se))
2548                 now = cfs_rq_clock_task(cfs_rq);
2549         else
2550                 now = cfs_rq_clock_task(group_cfs_rq(se));
2551
2552         if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
2553                 return;
2554
2555         contrib_delta = __update_entity_load_avg_contrib(se);
2556
2557         if (!update_cfs_rq)
2558                 return;
2559
2560         if (se->on_rq)
2561                 cfs_rq->runnable_load_avg += contrib_delta;
2562         else
2563                 subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
2564 }
2565
2566 /*
2567  * Decay the load contributed by all blocked children and account this so that
2568  * their contribution may appropriately discounted when they wake up.
2569  */
2570 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
2571 {
2572         u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
2573         u64 decays;
2574
2575         decays = now - cfs_rq->last_decay;
2576         if (!decays && !force_update)
2577                 return;
2578
2579         if (atomic_long_read(&cfs_rq->removed_load)) {
2580                 unsigned long removed_load;
2581                 removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
2582                 subtract_blocked_load_contrib(cfs_rq, removed_load);
2583         }
2584
2585         if (decays) {
2586                 cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
2587                                                       decays);
2588                 atomic64_add(decays, &cfs_rq->decay_counter);
2589                 cfs_rq->last_decay = now;
2590         }
2591
2592         __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
2593 }
2594
2595 /* Add the load generated by se into cfs_rq's child load-average */
2596 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2597                                                   struct sched_entity *se,
2598                                                   int wakeup)
2599 {
2600         /*
2601          * We track migrations using entity decay_count <= 0, on a wake-up
2602          * migration we use a negative decay count to track the remote decays
2603          * accumulated while sleeping.
2604          *
2605          * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
2606          * are seen by enqueue_entity_load_avg() as a migration with an already
2607          * constructed load_avg_contrib.
2608          */
2609         if (unlikely(se->avg.decay_count <= 0)) {
2610                 se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
2611                 if (se->avg.decay_count) {
2612                         /*
2613                          * In a wake-up migration we have to approximate the
2614                          * time sleeping.  This is because we can't synchronize
2615                          * clock_task between the two cpus, and it is not
2616                          * guaranteed to be read-safe.  Instead, we can
2617                          * approximate this using our carried decays, which are
2618                          * explicitly atomically readable.
2619                          */
2620                         se->avg.last_runnable_update -= (-se->avg.decay_count)
2621                                                         << 20;
2622                         update_entity_load_avg(se, 0);
2623                         /* Indicate that we're now synchronized and on-rq */
2624                         se->avg.decay_count = 0;
2625                 }
2626                 wakeup = 0;
2627         } else {
2628                 __synchronize_entity_decay(se);
2629         }
2630
2631         /* migrated tasks did not contribute to our blocked load */
2632         if (wakeup) {
2633                 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
2634                 update_entity_load_avg(se, 0);
2635         }
2636
2637         cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
2638         /* we force update consideration on load-balancer moves */
2639         update_cfs_rq_blocked_load(cfs_rq, !wakeup);
2640 }
2641
2642 /*
2643  * Remove se's load from this cfs_rq child load-average, if the entity is
2644  * transitioning to a blocked state we track its projected decay using
2645  * blocked_load_avg.
2646  */
2647 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2648                                                   struct sched_entity *se,
2649                                                   int sleep)
2650 {
2651         update_entity_load_avg(se, 1);
2652         /* we force update consideration on load-balancer moves */
2653         update_cfs_rq_blocked_load(cfs_rq, !sleep);
2654
2655         cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
2656         if (sleep) {
2657                 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
2658                 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
2659         } /* migrations, e.g. sleep=0 leave decay_count == 0 */
2660 }
2661
2662 /*
2663  * Update the rq's load with the elapsed running time before entering
2664  * idle. if the last scheduled task is not a CFS task, idle_enter will
2665  * be the only way to update the runnable statistic.
2666  */
2667 void idle_enter_fair(struct rq *this_rq)
2668 {
2669         update_rq_runnable_avg(this_rq, 1);
2670 }
2671
2672 /*
2673  * Update the rq's load with the elapsed idle time before a task is
2674  * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
2675  * be the only way to update the runnable statistic.
2676  */
2677 void idle_exit_fair(struct rq *this_rq)
2678 {
2679         update_rq_runnable_avg(this_rq, 0);
2680 }
2681
2682 static int idle_balance(struct rq *this_rq);
2683
2684 #else /* CONFIG_SMP */
2685
2686 static inline void update_entity_load_avg(struct sched_entity *se,
2687                                           int update_cfs_rq) {}
2688 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2689 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2690                                            struct sched_entity *se,
2691                                            int wakeup) {}
2692 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2693                                            struct sched_entity *se,
2694                                            int sleep) {}
2695 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
2696                                               int force_update) {}
2697
2698 static inline int idle_balance(struct rq *rq)
2699 {
2700         return 0;
2701 }
2702
2703 #endif /* CONFIG_SMP */
2704
2705 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
2706 {
2707 #ifdef CONFIG_SCHEDSTATS
2708         struct task_struct *tsk = NULL;
2709
2710         if (entity_is_task(se))
2711                 tsk = task_of(se);
2712
2713         if (se->statistics.sleep_start) {
2714                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.sleep_start;
2715
2716                 if ((s64)delta < 0)
2717                         delta = 0;
2718
2719                 if (unlikely(delta > se->statistics.sleep_max))
2720                         se->statistics.sleep_max = delta;
2721
2722                 se->statistics.sleep_start = 0;
2723                 se->statistics.sum_sleep_runtime += delta;
2724
2725                 if (tsk) {
2726                         account_scheduler_latency(tsk, delta >> 10, 1);
2727                         trace_sched_stat_sleep(tsk, delta);
2728                 }
2729         }
2730         if (se->statistics.block_start) {
2731                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.block_start;
2732
2733                 if ((s64)delta < 0)
2734                         delta = 0;
2735
2736                 if (unlikely(delta > se->statistics.block_max))
2737                         se->statistics.block_max = delta;
2738
2739                 se->statistics.block_start = 0;
2740                 se->statistics.sum_sleep_runtime += delta;
2741
2742                 if (tsk) {
2743                         if (tsk->in_iowait) {
2744                                 se->statistics.iowait_sum += delta;
2745                                 se->statistics.iowait_count++;
2746                                 trace_sched_stat_iowait(tsk, delta);
2747                         }
2748
2749                         trace_sched_stat_blocked(tsk, delta);
2750
2751                         /*
2752                          * Blocking time is in units of nanosecs, so shift by
2753                          * 20 to get a milliseconds-range estimation of the
2754                          * amount of time that the task spent sleeping:
2755                          */
2756                         if (unlikely(prof_on == SLEEP_PROFILING)) {
2757                                 profile_hits(SLEEP_PROFILING,
2758                                                 (void *)get_wchan(tsk),
2759                                                 delta >> 20);
2760                         }
2761                         account_scheduler_latency(tsk, delta >> 10, 0);
2762                 }
2763         }
2764 #endif
2765 }
2766
2767 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
2768 {
2769 #ifdef CONFIG_SCHED_DEBUG
2770         s64 d = se->vruntime - cfs_rq->min_vruntime;
2771
2772         if (d < 0)
2773                 d = -d;
2774
2775         if (d > 3*sysctl_sched_latency)
2776                 schedstat_inc(cfs_rq, nr_spread_over);
2777 #endif
2778 }
2779
2780 static void
2781 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
2782 {
2783         u64 vruntime = cfs_rq->min_vruntime;
2784
2785         /*
2786          * The 'current' period is already promised to the current tasks,
2787          * however the extra weight of the new task will slow them down a
2788          * little, place the new task so that it fits in the slot that
2789          * stays open at the end.
2790          */
2791         if (initial && sched_feat(START_DEBIT))
2792                 vruntime += sched_vslice(cfs_rq, se);
2793
2794         /* sleeps up to a single latency don't count. */
2795         if (!initial) {
2796                 unsigned long thresh = sysctl_sched_latency;
2797
2798                 /*
2799                  * Halve their sleep time's effect, to allow
2800                  * for a gentler effect of sleepers:
2801                  */
2802                 if (sched_feat(GENTLE_FAIR_SLEEPERS))
2803                         thresh >>= 1;
2804
2805                 vruntime -= thresh;
2806         }
2807
2808         /* ensure we never gain time by being placed backwards. */
2809         se->vruntime = max_vruntime(se->vruntime, vruntime);
2810 }
2811
2812 static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
2813
2814 static void
2815 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2816 {
2817         /*
2818          * Update the normalized vruntime before updating min_vruntime
2819          * through calling update_curr().
2820          */
2821         if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
2822                 se->vruntime += cfs_rq->min_vruntime;
2823
2824         /*
2825          * Update run-time statistics of the 'current'.
2826          */
2827         update_curr(cfs_rq);
2828         enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
2829         account_entity_enqueue(cfs_rq, se);
2830         update_cfs_shares(cfs_rq);
2831
2832         if (flags & ENQUEUE_WAKEUP) {
2833                 place_entity(cfs_rq, se, 0);
2834                 enqueue_sleeper(cfs_rq, se);
2835         }
2836
2837         update_stats_enqueue(cfs_rq, se);
2838         check_spread(cfs_rq, se);
2839         if (se != cfs_rq->curr)
2840                 __enqueue_entity(cfs_rq, se);
2841         se->on_rq = 1;
2842
2843         if (cfs_rq->nr_running == 1) {
2844                 list_add_leaf_cfs_rq(cfs_rq);
2845                 check_enqueue_throttle(cfs_rq);
2846         }
2847 }
2848
2849 static void __clear_buddies_last(struct sched_entity *se)
2850 {
2851         for_each_sched_entity(se) {
2852                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2853                 if (cfs_rq->last != se)
2854                         break;
2855
2856                 cfs_rq->last = NULL;
2857         }
2858 }
2859
2860 static void __clear_buddies_next(struct sched_entity *se)
2861 {
2862         for_each_sched_entity(se) {
2863                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2864                 if (cfs_rq->next != se)
2865                         break;
2866
2867                 cfs_rq->next = NULL;
2868         }
2869 }
2870
2871 static void __clear_buddies_skip(struct sched_entity *se)
2872 {
2873         for_each_sched_entity(se) {
2874                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2875                 if (cfs_rq->skip != se)
2876                         break;
2877
2878                 cfs_rq->skip = NULL;
2879         }
2880 }
2881
2882 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
2883 {
2884         if (cfs_rq->last == se)
2885                 __clear_buddies_last(se);
2886
2887         if (cfs_rq->next == se)
2888                 __clear_buddies_next(se);
2889
2890         if (cfs_rq->skip == se)
2891                 __clear_buddies_skip(se);
2892 }
2893
2894 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
2895
2896 static void
2897 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2898 {
2899         /*
2900          * Update run-time statistics of the 'current'.
2901          */
2902         update_curr(cfs_rq);
2903         dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP);
2904
2905         update_stats_dequeue(cfs_rq, se);
2906         if (flags & DEQUEUE_SLEEP) {
2907 #ifdef CONFIG_SCHEDSTATS
2908                 if (entity_is_task(se)) {
2909                         struct task_struct *tsk = task_of(se);
2910
2911                         if (tsk->state & TASK_INTERRUPTIBLE)
2912                                 se->statistics.sleep_start = rq_clock(rq_of(cfs_rq));
2913                         if (tsk->state & TASK_UNINTERRUPTIBLE)
2914                                 se->statistics.block_start = rq_clock(rq_of(cfs_rq));
2915                 }
2916 #endif
2917         }
2918
2919         clear_buddies(cfs_rq, se);
2920
2921         if (se != cfs_rq->curr)
2922                 __dequeue_entity(cfs_rq, se);
2923         se->on_rq = 0;
2924         account_entity_dequeue(cfs_rq, se);
2925
2926         /*
2927          * Normalize the entity after updating the min_vruntime because the
2928          * update can refer to the ->curr item and we need to reflect this
2929          * movement in our normalized position.
2930          */
2931         if (!(flags & DEQUEUE_SLEEP))
2932                 se->vruntime -= cfs_rq->min_vruntime;
2933
2934         /* return excess runtime on last dequeue */
2935         return_cfs_rq_runtime(cfs_rq);
2936
2937         update_min_vruntime(cfs_rq);
2938         update_cfs_shares(cfs_rq);
2939 }
2940
2941 /*
2942  * Preempt the current task with a newly woken task if needed:
2943  */
2944 static void
2945 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
2946 {
2947         unsigned long ideal_runtime, delta_exec;
2948         struct sched_entity *se;
2949         s64 delta;
2950
2951         ideal_runtime = sched_slice(cfs_rq, curr);
2952         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
2953         if (delta_exec > ideal_runtime) {
2954                 resched_curr(rq_of(cfs_rq));
2955                 /*
2956                  * The current task ran long enough, ensure it doesn't get
2957                  * re-elected due to buddy favours.
2958                  */
2959                 clear_buddies(cfs_rq, curr);
2960                 return;
2961         }
2962
2963         /*
2964          * Ensure that a task that missed wakeup preemption by a
2965          * narrow margin doesn't have to wait for a full slice.
2966          * This also mitigates buddy induced latencies under load.
2967          */
2968         if (delta_exec < sysctl_sched_min_granularity)
2969                 return;
2970
2971         se = __pick_first_entity(cfs_rq);
2972         delta = curr->vruntime - se->vruntime;
2973
2974         if (delta < 0)
2975                 return;
2976
2977         if (delta > ideal_runtime)
2978                 resched_curr(rq_of(cfs_rq));
2979 }
2980
2981 static void
2982 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
2983 {
2984         /* 'current' is not kept within the tree. */
2985         if (se->on_rq) {
2986                 /*
2987                  * Any task has to be enqueued before it get to execute on
2988                  * a CPU. So account for the time it spent waiting on the
2989                  * runqueue.
2990                  */
2991                 update_stats_wait_end(cfs_rq, se);
2992                 __dequeue_entity(cfs_rq, se);
2993         }
2994
2995         update_stats_curr_start(cfs_rq, se);
2996         cfs_rq->curr = se;
2997 #ifdef CONFIG_SCHEDSTATS
2998         /*
2999          * Track our maximum slice length, if the CPU's load is at
3000          * least twice that of our own weight (i.e. dont track it
3001          * when there are only lesser-weight tasks around):
3002          */
3003         if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
3004                 se->statistics.slice_max = max(se->statistics.slice_max,
3005                         se->sum_exec_runtime - se->prev_sum_exec_runtime);
3006         }
3007 #endif
3008         se->prev_sum_exec_runtime = se->sum_exec_runtime;
3009 }
3010
3011 static int
3012 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
3013
3014 /*
3015  * Pick the next process, keeping these things in mind, in this order:
3016  * 1) keep things fair between processes/task groups
3017  * 2) pick the "next" process, since someone really wants that to run
3018  * 3) pick the "last" process, for cache locality
3019  * 4) do not run the "skip" process, if something else is available
3020  */
3021 static struct sched_entity *
3022 pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
3023 {
3024         struct sched_entity *left = __pick_first_entity(cfs_rq);
3025         struct sched_entity *se;
3026
3027         /*
3028          * If curr is set we have to see if its left of the leftmost entity
3029          * still in the tree, provided there was anything in the tree at all.
3030          */
3031         if (!left || (curr && entity_before(curr, left)))
3032                 left = curr;
3033
3034         se = left; /* ideally we run the leftmost entity */
3035
3036         /*
3037          * Avoid running the skip buddy, if running something else can
3038          * be done without getting too unfair.
3039          */
3040         if (cfs_rq->skip == se) {
3041                 struct sched_entity *second;
3042
3043                 if (se == curr) {
3044                         second = __pick_first_entity(cfs_rq);
3045                 } else {
3046                         second = __pick_next_entity(se);
3047                         if (!second || (curr && entity_before(curr, second)))
3048                                 second = curr;
3049                 }
3050
3051                 if (second && wakeup_preempt_entity(second, left) < 1)
3052                         se = second;
3053         }
3054
3055         /*
3056          * Prefer last buddy, try to return the CPU to a preempted task.
3057          */
3058         if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
3059                 se = cfs_rq->last;
3060
3061         /*
3062          * Someone really wants this to run. If it's not unfair, run it.
3063          */
3064         if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
3065                 se = cfs_rq->next;
3066
3067         clear_buddies(cfs_rq, se);
3068
3069         return se;
3070 }
3071
3072 static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
3073
3074 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
3075 {
3076         /*
3077          * If still on the runqueue then deactivate_task()
3078          * was not called and update_curr() has to be done:
3079          */
3080         if (prev->on_rq)
3081                 update_curr(cfs_rq);
3082
3083         /* throttle cfs_rqs exceeding runtime */
3084         check_cfs_rq_runtime(cfs_rq);
3085
3086         check_spread(cfs_rq, prev);
3087         if (prev->on_rq) {
3088                 update_stats_wait_start(cfs_rq, prev);
3089                 /* Put 'current' back into the tree. */
3090                 __enqueue_entity(cfs_rq, prev);
3091                 /* in !on_rq case, update occurred at dequeue */
3092                 update_entity_load_avg(prev, 1);
3093         }
3094         cfs_rq->curr = NULL;
3095 }
3096
3097 static void
3098 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
3099 {
3100         /*
3101          * Update run-time statistics of the 'current'.
3102          */
3103         update_curr(cfs_rq);
3104
3105         /*
3106          * Ensure that runnable average is periodically updated.
3107          */
3108         update_entity_load_avg(curr, 1);
3109         update_cfs_rq_blocked_load(cfs_rq, 1);
3110         update_cfs_shares(cfs_rq);
3111
3112 #ifdef CONFIG_SCHED_HRTICK
3113         /*
3114          * queued ticks are scheduled to match the slice, so don't bother
3115          * validating it and just reschedule.
3116          */
3117         if (queued) {
3118                 resched_curr(rq_of(cfs_rq));
3119                 return;
3120         }
3121         /*
3122          * don't let the period tick interfere with the hrtick preemption
3123          */
3124         if (!sched_feat(DOUBLE_TICK) &&
3125                         hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
3126                 return;
3127 #endif
3128
3129         if (cfs_rq->nr_running > 1)
3130                 check_preempt_tick(cfs_rq, curr);
3131 }
3132
3133
3134 /**************************************************
3135  * CFS bandwidth control machinery
3136  */
3137
3138 #ifdef CONFIG_CFS_BANDWIDTH
3139
3140 #ifdef HAVE_JUMP_LABEL
3141 static struct static_key __cfs_bandwidth_used;
3142
3143 static inline bool cfs_bandwidth_used(void)
3144 {
3145         return static_key_false(&__cfs_bandwidth_used);
3146 }
3147
3148 void cfs_bandwidth_usage_inc(void)
3149 {
3150         static_key_slow_inc(&__cfs_bandwidth_used);
3151 }
3152
3153 void cfs_bandwidth_usage_dec(void)
3154 {
3155         static_key_slow_dec(&__cfs_bandwidth_used);
3156 }
3157 #else /* HAVE_JUMP_LABEL */
3158 static bool cfs_bandwidth_used(void)
3159 {
3160         return true;
3161 }
3162
3163 void cfs_bandwidth_usage_inc(void) {}
3164 void cfs_bandwidth_usage_dec(void) {}
3165 #endif /* HAVE_JUMP_LABEL */
3166
3167 /*
3168  * default period for cfs group bandwidth.
3169  * default: 0.1s, units: nanoseconds
3170  */
3171 static inline u64 default_cfs_period(void)
3172 {
3173         return 100000000ULL;
3174 }
3175
3176 static inline u64 sched_cfs_bandwidth_slice(void)
3177 {
3178         return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
3179 }
3180
3181 /*
3182  * Replenish runtime according to assigned quota and update expiration time.
3183  * We use sched_clock_cpu directly instead of rq->clock to avoid adding
3184  * additional synchronization around rq->lock.
3185  *
3186  * requires cfs_b->lock
3187  */
3188 void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b)
3189 {
3190         u64 now;
3191
3192         if (cfs_b->quota == RUNTIME_INF)
3193                 return;
3194
3195         now = sched_clock_cpu(smp_processor_id());
3196         cfs_b->runtime = cfs_b->quota;
3197         cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period);
3198 }
3199
3200 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
3201 {
3202         return &tg->cfs_bandwidth;
3203 }
3204
3205 /* rq->task_clock normalized against any time this cfs_rq has spent throttled */
3206 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
3207 {
3208         if (unlikely(cfs_rq->throttle_count))
3209                 return cfs_rq->throttled_clock_task;
3210
3211         return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
3212 }
3213
3214 /* returns 0 on failure to allocate runtime */
3215 static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3216 {
3217         struct task_group *tg = cfs_rq->tg;
3218         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
3219         u64 amount = 0, min_amount, expires;
3220
3221         /* note: this is a positive sum as runtime_remaining <= 0 */
3222         min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;
3223
3224         raw_spin_lock(&cfs_b->lock);
3225         if (cfs_b->quota == RUNTIME_INF)
3226                 amount = min_amount;
3227         else {
3228                 /*
3229                  * If the bandwidth pool has become inactive, then at least one
3230                  * period must have elapsed since the last consumption.
3231                  * Refresh the global state and ensure bandwidth timer becomes
3232                  * active.
3233                  */
3234                 if (!cfs_b->timer_active) {
3235                         __refill_cfs_bandwidth_runtime(cfs_b);
3236                         __start_cfs_bandwidth(cfs_b, false);
3237                 }
3238
3239                 if (cfs_b->runtime > 0) {
3240                         amount = min(cfs_b->runtime, min_amount);
3241                         cfs_b->runtime -= amount;
3242                         cfs_b->idle = 0;
3243                 }
3244         }
3245         expires = cfs_b->runtime_expires;
3246         raw_spin_unlock(&cfs_b->lock);
3247
3248         cfs_rq->runtime_remaining += amount;
3249         /*
3250          * we may have advanced our local expiration to account for allowed
3251          * spread between our sched_clock and the one on which runtime was
3252          * issued.
3253          */
3254         if ((s64)(expires - cfs_rq->runtime_expires) > 0)
3255                 cfs_rq->runtime_expires = expires;
3256
3257         return cfs_rq->runtime_remaining > 0;
3258 }
3259
3260 /*
3261  * Note: This depends on the synchronization provided by sched_clock and the
3262  * fact that rq->clock snapshots this value.
3263  */
3264 static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3265 {
3266         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3267
3268         /* if the deadline is ahead of our clock, nothing to do */
3269         if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
3270                 return;
3271
3272         if (cfs_rq->runtime_remaining < 0)
3273                 return;
3274
3275         /*
3276          * If the local deadline has passed we have to consider the
3277          * possibility that our sched_clock is 'fast' and the global deadline
3278          * has not truly expired.
3279          *
3280          * Fortunately we can check determine whether this the case by checking
3281          * whether the global deadline has advanced. It is valid to compare
3282          * cfs_b->runtime_expires without any locks since we only care about
3283          * exact equality, so a partial write will still work.
3284          */
3285
3286         if (cfs_rq->runtime_expires != cfs_b->runtime_expires) {
3287                 /* extend local deadline, drift is bounded above by 2 ticks */
3288                 cfs_rq->runtime_expires += TICK_NSEC;
3289         } else {
3290                 /* global deadline is ahead, expiration has passed */
3291                 cfs_rq->runtime_remaining = 0;
3292         }
3293 }
3294
3295 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3296 {
3297         /* dock delta_exec before expiring quota (as it could span periods) */
3298         cfs_rq->runtime_remaining -= delta_exec;
3299         expire_cfs_rq_runtime(cfs_rq);
3300
3301         if (likely(cfs_rq->runtime_remaining > 0))
3302                 return;
3303
3304         /*
3305          * if we're unable to extend our runtime we resched so that the active
3306          * hierarchy can be throttled
3307          */
3308         if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
3309                 resched_curr(rq_of(cfs_rq));
3310 }
3311
3312 static __always_inline
3313 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3314 {
3315         if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
3316                 return;
3317
3318         __account_cfs_rq_runtime(cfs_rq, delta_exec);
3319 }
3320
3321 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3322 {
3323         return cfs_bandwidth_used() && cfs_rq->throttled;
3324 }
3325
3326 /* check whether cfs_rq, or any parent, is throttled */
3327 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3328 {
3329         return cfs_bandwidth_used() && cfs_rq->throttle_count;
3330 }
3331
3332 /*
3333  * Ensure that neither of the group entities corresponding to src_cpu or
3334  * dest_cpu are members of a throttled hierarchy when performing group
3335  * load-balance operations.
3336  */
3337 static inline int throttled_lb_pair(struct task_group *tg,
3338                                     int src_cpu, int dest_cpu)
3339 {
3340         struct cfs_rq *src_cfs_rq, *dest_cfs_rq;
3341
3342         src_cfs_rq = tg->cfs_rq[src_cpu];
3343         dest_cfs_rq = tg->cfs_rq[dest_cpu];
3344
3345         return throttled_hierarchy(src_cfs_rq) ||
3346                throttled_hierarchy(dest_cfs_rq);
3347 }
3348
3349 /* updated child weight may affect parent so we have to do this bottom up */
3350 static int tg_unthrottle_up(struct task_group *tg, void *data)
3351 {
3352         struct rq *rq = data;
3353         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3354
3355         cfs_rq->throttle_count--;
3356 #ifdef CONFIG_SMP
3357         if (!cfs_rq->throttle_count) {
3358                 /* adjust cfs_rq_clock_task() */
3359                 cfs_rq->throttled_clock_task_time += rq_clock_task(rq) -
3360                                              cfs_rq->throttled_clock_task;
3361         }
3362 #endif
3363
3364         return 0;
3365 }
3366
3367 static int tg_throttle_down(struct task_group *tg, void *data)
3368 {
3369         struct rq *rq = data;
3370         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3371
3372         /* group is entering throttled state, stop time */
3373         if (!cfs_rq->throttle_count)
3374                 cfs_rq->throttled_clock_task = rq_clock_task(rq);
3375         cfs_rq->throttle_count++;
3376
3377         return 0;
3378 }
3379
3380 static void throttle_cfs_rq(struct cfs_rq *cfs_rq)
3381 {
3382         struct rq *rq = rq_of(cfs_rq);
3383         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3384         struct sched_entity *se;
3385         long task_delta, dequeue = 1;
3386
3387         se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
3388
3389         /* freeze hierarchy runnable averages while throttled */
3390         rcu_read_lock();
3391         walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
3392         rcu_read_unlock();
3393
3394         task_delta = cfs_rq->h_nr_running;
3395         for_each_sched_entity(se) {
3396                 struct cfs_rq *qcfs_rq = cfs_rq_of(se);
3397                 /* throttled entity or throttle-on-deactivate */
3398                 if (!se->on_rq)
3399                         break;
3400
3401                 if (dequeue)
3402                         dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
3403                 qcfs_rq->h_nr_running -= task_delta;
3404
3405                 if (qcfs_rq->load.weight)
3406                         dequeue = 0;
3407         }
3408
3409         if (!se)
3410                 sub_nr_running(rq, task_delta);
3411
3412         cfs_rq->throttled = 1;
3413         cfs_rq->throttled_clock = rq_clock(rq);
3414         raw_spin_lock(&cfs_b->lock);
3415         /*
3416          * Add to the _head_ of the list, so that an already-started
3417          * distribute_cfs_runtime will not see us
3418          */
3419         list_add_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq);
3420         if (!cfs_b->timer_active)
3421                 __start_cfs_bandwidth(cfs_b, false);
3422         raw_spin_unlock(&cfs_b->lock);
3423 }
3424
3425 void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
3426 {
3427         struct rq *rq = rq_of(cfs_rq);