9030da7bcb15f62f5d4873857c81e920e61fe052
[platform/adaptation/renesas_rcar/renesas_kernel.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/slab.h>
27 #include <linux/profile.h>
28 #include <linux/interrupt.h>
29 #include <linux/mempolicy.h>
30 #include <linux/migrate.h>
31 #include <linux/task_work.h>
32
33 #include <trace/events/sched.h>
34
35 #include "sched.h"
36
37 /*
38  * Targeted preemption latency for CPU-bound tasks:
39  * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)
40  *
41  * NOTE: this latency value is not the same as the concept of
42  * 'timeslice length' - timeslices in CFS are of variable length
43  * and have no persistent notion like in traditional, time-slice
44  * based scheduling concepts.
45  *
46  * (to see the precise effective timeslice length of your workload,
47  *  run vmstat and monitor the context-switches (cs) field)
48  */
49 unsigned int sysctl_sched_latency = 6000000ULL;
50 unsigned int normalized_sysctl_sched_latency = 6000000ULL;
51
52 /*
53  * The initial- and re-scaling of tunables is configurable
54  * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
55  *
56  * Options are:
57  * SCHED_TUNABLESCALING_NONE - unscaled, always *1
58  * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
59  * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
60  */
61 enum sched_tunable_scaling sysctl_sched_tunable_scaling
62         = SCHED_TUNABLESCALING_LOG;
63
64 /*
65  * Minimal preemption granularity for CPU-bound tasks:
66  * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)
67  */
68 unsigned int sysctl_sched_min_granularity = 750000ULL;
69 unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;
70
71 /*
72  * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
73  */
74 static unsigned int sched_nr_latency = 8;
75
76 /*
77  * After fork, child runs first. If set to 0 (default) then
78  * parent will (try to) run first.
79  */
80 unsigned int sysctl_sched_child_runs_first __read_mostly;
81
82 /*
83  * SCHED_OTHER wake-up granularity.
84  * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
85  *
86  * This option delays the preemption effects of decoupled workloads
87  * and reduces their over-scheduling. Synchronous workloads will still
88  * have immediate wakeup/sleep latencies.
89  */
90 unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
91 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
92
93 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
94
95 /*
96  * The exponential sliding  window over which load is averaged for shares
97  * distribution.
98  * (default: 10msec)
99  */
100 unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL;
101
102 #ifdef CONFIG_CFS_BANDWIDTH
103 /*
104  * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
105  * each time a cfs_rq requests quota.
106  *
107  * Note: in the case that the slice exceeds the runtime remaining (either due
108  * to consumption or the quota being specified to be smaller than the slice)
109  * we will always only issue the remaining available time.
110  *
111  * default: 5 msec, units: microseconds
112   */
113 unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL;
114 #endif
115
116 static inline void update_load_add(struct load_weight *lw, unsigned long inc)
117 {
118         lw->weight += inc;
119         lw->inv_weight = 0;
120 }
121
122 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
123 {
124         lw->weight -= dec;
125         lw->inv_weight = 0;
126 }
127
128 static inline void update_load_set(struct load_weight *lw, unsigned long w)
129 {
130         lw->weight = w;
131         lw->inv_weight = 0;
132 }
133
134 /*
135  * Increase the granularity value when there are more CPUs,
136  * because with more CPUs the 'effective latency' as visible
137  * to users decreases. But the relationship is not linear,
138  * so pick a second-best guess by going with the log2 of the
139  * number of CPUs.
140  *
141  * This idea comes from the SD scheduler of Con Kolivas:
142  */
143 static int get_update_sysctl_factor(void)
144 {
145         unsigned int cpus = min_t(int, num_online_cpus(), 8);
146         unsigned int factor;
147
148         switch (sysctl_sched_tunable_scaling) {
149         case SCHED_TUNABLESCALING_NONE:
150                 factor = 1;
151                 break;
152         case SCHED_TUNABLESCALING_LINEAR:
153                 factor = cpus;
154                 break;
155         case SCHED_TUNABLESCALING_LOG:
156         default:
157                 factor = 1 + ilog2(cpus);
158                 break;
159         }
160
161         return factor;
162 }
163
164 static void update_sysctl(void)
165 {
166         unsigned int factor = get_update_sysctl_factor();
167
168 #define SET_SYSCTL(name) \
169         (sysctl_##name = (factor) * normalized_sysctl_##name)
170         SET_SYSCTL(sched_min_granularity);
171         SET_SYSCTL(sched_latency);
172         SET_SYSCTL(sched_wakeup_granularity);
173 #undef SET_SYSCTL
174 }
175
176 void sched_init_granularity(void)
177 {
178         update_sysctl();
179 }
180
181 #define WMULT_CONST     (~0U)
182 #define WMULT_SHIFT     32
183
184 static void __update_inv_weight(struct load_weight *lw)
185 {
186         unsigned long w;
187
188         if (likely(lw->inv_weight))
189                 return;
190
191         w = scale_load_down(lw->weight);
192
193         if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
194                 lw->inv_weight = 1;
195         else if (unlikely(!w))
196                 lw->inv_weight = WMULT_CONST;
197         else
198                 lw->inv_weight = WMULT_CONST / w;
199 }
200
201 /*
202  * delta_exec * weight / lw.weight
203  *   OR
204  * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
205  *
206  * Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case
207  * we're guaranteed shift stays positive because inv_weight is guaranteed to
208  * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
209  *
210  * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
211  * weight/lw.weight <= 1, and therefore our shift will also be positive.
212  */
213 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
214 {
215         u64 fact = scale_load_down(weight);
216         int shift = WMULT_SHIFT;
217
218         __update_inv_weight(lw);
219
220         if (unlikely(fact >> 32)) {
221                 while (fact >> 32) {
222                         fact >>= 1;
223                         shift--;
224                 }
225         }
226
227         /* hint to use a 32x32->64 mul */
228         fact = (u64)(u32)fact * lw->inv_weight;
229
230         while (fact >> 32) {
231                 fact >>= 1;
232                 shift--;
233         }
234
235         return mul_u64_u32_shr(delta_exec, fact, shift);
236 }
237
238
239 const struct sched_class fair_sched_class;
240
241 /**************************************************************
242  * CFS operations on generic schedulable entities:
243  */
244
245 #ifdef CONFIG_FAIR_GROUP_SCHED
246
247 /* cpu runqueue to which this cfs_rq is attached */
248 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
249 {
250         return cfs_rq->rq;
251 }
252
253 /* An entity is a task if it doesn't "own" a runqueue */
254 #define entity_is_task(se)      (!se->my_q)
255
256 static inline struct task_struct *task_of(struct sched_entity *se)
257 {
258 #ifdef CONFIG_SCHED_DEBUG
259         WARN_ON_ONCE(!entity_is_task(se));
260 #endif
261         return container_of(se, struct task_struct, se);
262 }
263
264 /* Walk up scheduling entities hierarchy */
265 #define for_each_sched_entity(se) \
266                 for (; se; se = se->parent)
267
268 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
269 {
270         return p->se.cfs_rq;
271 }
272
273 /* runqueue on which this entity is (to be) queued */
274 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
275 {
276         return se->cfs_rq;
277 }
278
279 /* runqueue "owned" by this group */
280 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
281 {
282         return grp->my_q;
283 }
284
285 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
286                                        int force_update);
287
288 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
289 {
290         if (!cfs_rq->on_list) {
291                 /*
292                  * Ensure we either appear before our parent (if already
293                  * enqueued) or force our parent to appear after us when it is
294                  * enqueued.  The fact that we always enqueue bottom-up
295                  * reduces this to two cases.
296                  */
297                 if (cfs_rq->tg->parent &&
298                     cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
299                         list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
300                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
301                 } else {
302                         list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
303                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
304                 }
305
306                 cfs_rq->on_list = 1;
307                 /* We should have no load, but we need to update last_decay. */
308                 update_cfs_rq_blocked_load(cfs_rq, 0);
309         }
310 }
311
312 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
313 {
314         if (cfs_rq->on_list) {
315                 list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
316                 cfs_rq->on_list = 0;
317         }
318 }
319
320 /* Iterate thr' all leaf cfs_rq's on a runqueue */
321 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
322         list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
323
324 /* Do the two (enqueued) entities belong to the same group ? */
325 static inline int
326 is_same_group(struct sched_entity *se, struct sched_entity *pse)
327 {
328         if (se->cfs_rq == pse->cfs_rq)
329                 return 1;
330
331         return 0;
332 }
333
334 static inline struct sched_entity *parent_entity(struct sched_entity *se)
335 {
336         return se->parent;
337 }
338
339 /* return depth at which a sched entity is present in the hierarchy */
340 static inline int depth_se(struct sched_entity *se)
341 {
342         int depth = 0;
343
344         for_each_sched_entity(se)
345                 depth++;
346
347         return depth;
348 }
349
350 static void
351 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
352 {
353         int se_depth, pse_depth;
354
355         /*
356          * preemption test can be made between sibling entities who are in the
357          * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
358          * both tasks until we find their ancestors who are siblings of common
359          * parent.
360          */
361
362         /* First walk up until both entities are at same depth */
363         se_depth = depth_se(*se);
364         pse_depth = depth_se(*pse);
365
366         while (se_depth > pse_depth) {
367                 se_depth--;
368                 *se = parent_entity(*se);
369         }
370
371         while (pse_depth > se_depth) {
372                 pse_depth--;
373                 *pse = parent_entity(*pse);
374         }
375
376         while (!is_same_group(*se, *pse)) {
377                 *se = parent_entity(*se);
378                 *pse = parent_entity(*pse);
379         }
380 }
381
382 #else   /* !CONFIG_FAIR_GROUP_SCHED */
383
384 static inline struct task_struct *task_of(struct sched_entity *se)
385 {
386         return container_of(se, struct task_struct, se);
387 }
388
389 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
390 {
391         return container_of(cfs_rq, struct rq, cfs);
392 }
393
394 #define entity_is_task(se)      1
395
396 #define for_each_sched_entity(se) \
397                 for (; se; se = NULL)
398
399 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
400 {
401         return &task_rq(p)->cfs;
402 }
403
404 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
405 {
406         struct task_struct *p = task_of(se);
407         struct rq *rq = task_rq(p);
408
409         return &rq->cfs;
410 }
411
412 /* runqueue "owned" by this group */
413 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
414 {
415         return NULL;
416 }
417
418 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
419 {
420 }
421
422 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
423 {
424 }
425
426 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
427                 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
428
429 static inline int
430 is_same_group(struct sched_entity *se, struct sched_entity *pse)
431 {
432         return 1;
433 }
434
435 static inline struct sched_entity *parent_entity(struct sched_entity *se)
436 {
437         return NULL;
438 }
439
440 static inline void
441 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
442 {
443 }
444
445 #endif  /* CONFIG_FAIR_GROUP_SCHED */
446
447 static __always_inline
448 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);
449
450 /**************************************************************
451  * Scheduling class tree data structure manipulation methods:
452  */
453
454 static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
455 {
456         s64 delta = (s64)(vruntime - max_vruntime);
457         if (delta > 0)
458                 max_vruntime = vruntime;
459
460         return max_vruntime;
461 }
462
463 static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
464 {
465         s64 delta = (s64)(vruntime - min_vruntime);
466         if (delta < 0)
467                 min_vruntime = vruntime;
468
469         return min_vruntime;
470 }
471
472 static inline int entity_before(struct sched_entity *a,
473                                 struct sched_entity *b)
474 {
475         return (s64)(a->vruntime - b->vruntime) < 0;
476 }
477
478 static void update_min_vruntime(struct cfs_rq *cfs_rq)
479 {
480         u64 vruntime = cfs_rq->min_vruntime;
481
482         if (cfs_rq->curr)
483                 vruntime = cfs_rq->curr->vruntime;
484
485         if (cfs_rq->rb_leftmost) {
486                 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
487                                                    struct sched_entity,
488                                                    run_node);
489
490                 if (!cfs_rq->curr)
491                         vruntime = se->vruntime;
492                 else
493                         vruntime = min_vruntime(vruntime, se->vruntime);
494         }
495
496         /* ensure we never gain time by being placed backwards. */
497         cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
498 #ifndef CONFIG_64BIT
499         smp_wmb();
500         cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
501 #endif
502 }
503
504 /*
505  * Enqueue an entity into the rb-tree:
506  */
507 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
508 {
509         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
510         struct rb_node *parent = NULL;
511         struct sched_entity *entry;
512         int leftmost = 1;
513
514         /*
515          * Find the right place in the rbtree:
516          */
517         while (*link) {
518                 parent = *link;
519                 entry = rb_entry(parent, struct sched_entity, run_node);
520                 /*
521                  * We dont care about collisions. Nodes with
522                  * the same key stay together.
523                  */
524                 if (entity_before(se, entry)) {
525                         link = &parent->rb_left;
526                 } else {
527                         link = &parent->rb_right;
528                         leftmost = 0;
529                 }
530         }
531
532         /*
533          * Maintain a cache of leftmost tree entries (it is frequently
534          * used):
535          */
536         if (leftmost)
537                 cfs_rq->rb_leftmost = &se->run_node;
538
539         rb_link_node(&se->run_node, parent, link);
540         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
541 }
542
543 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
544 {
545         if (cfs_rq->rb_leftmost == &se->run_node) {
546                 struct rb_node *next_node;
547
548                 next_node = rb_next(&se->run_node);
549                 cfs_rq->rb_leftmost = next_node;
550         }
551
552         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
553 }
554
555 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
556 {
557         struct rb_node *left = cfs_rq->rb_leftmost;
558
559         if (!left)
560                 return NULL;
561
562         return rb_entry(left, struct sched_entity, run_node);
563 }
564
565 static struct sched_entity *__pick_next_entity(struct sched_entity *se)
566 {
567         struct rb_node *next = rb_next(&se->run_node);
568
569         if (!next)
570                 return NULL;
571
572         return rb_entry(next, struct sched_entity, run_node);
573 }
574
575 #ifdef CONFIG_SCHED_DEBUG
576 struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
577 {
578         struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
579
580         if (!last)
581                 return NULL;
582
583         return rb_entry(last, struct sched_entity, run_node);
584 }
585
586 /**************************************************************
587  * Scheduling class statistics methods:
588  */
589
590 int sched_proc_update_handler(struct ctl_table *table, int write,
591                 void __user *buffer, size_t *lenp,
592                 loff_t *ppos)
593 {
594         int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
595         int factor = get_update_sysctl_factor();
596
597         if (ret || !write)
598                 return ret;
599
600         sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
601                                         sysctl_sched_min_granularity);
602
603 #define WRT_SYSCTL(name) \
604         (normalized_sysctl_##name = sysctl_##name / (factor))
605         WRT_SYSCTL(sched_min_granularity);
606         WRT_SYSCTL(sched_latency);
607         WRT_SYSCTL(sched_wakeup_granularity);
608 #undef WRT_SYSCTL
609
610         return 0;
611 }
612 #endif
613
614 /*
615  * delta /= w
616  */
617 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
618 {
619         if (unlikely(se->load.weight != NICE_0_LOAD))
620                 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
621
622         return delta;
623 }
624
625 /*
626  * The idea is to set a period in which each task runs once.
627  *
628  * When there are too many tasks (sched_nr_latency) we have to stretch
629  * this period because otherwise the slices get too small.
630  *
631  * p = (nr <= nl) ? l : l*nr/nl
632  */
633 static u64 __sched_period(unsigned long nr_running)
634 {
635         u64 period = sysctl_sched_latency;
636         unsigned long nr_latency = sched_nr_latency;
637
638         if (unlikely(nr_running > nr_latency)) {
639                 period = sysctl_sched_min_granularity;
640                 period *= nr_running;
641         }
642
643         return period;
644 }
645
646 /*
647  * We calculate the wall-time slice from the period by taking a part
648  * proportional to the weight.
649  *
650  * s = p*P[w/rw]
651  */
652 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
653 {
654         u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
655
656         for_each_sched_entity(se) {
657                 struct load_weight *load;
658                 struct load_weight lw;
659
660                 cfs_rq = cfs_rq_of(se);
661                 load = &cfs_rq->load;
662
663                 if (unlikely(!se->on_rq)) {
664                         lw = cfs_rq->load;
665
666                         update_load_add(&lw, se->load.weight);
667                         load = &lw;
668                 }
669                 slice = __calc_delta(slice, se->load.weight, load);
670         }
671         return slice;
672 }
673
674 /*
675  * We calculate the vruntime slice of a to-be-inserted task.
676  *
677  * vs = s/w
678  */
679 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
680 {
681         return calc_delta_fair(sched_slice(cfs_rq, se), se);
682 }
683
684 #ifdef CONFIG_SMP
685 static unsigned long task_h_load(struct task_struct *p);
686
687 static inline void __update_task_entity_contrib(struct sched_entity *se);
688
689 /* Give new task start runnable values to heavy its load in infant time */
690 void init_task_runnable_average(struct task_struct *p)
691 {
692         u32 slice;
693
694         p->se.avg.decay_count = 0;
695         slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
696         p->se.avg.runnable_avg_sum = slice;
697         p->se.avg.runnable_avg_period = slice;
698         __update_task_entity_contrib(&p->se);
699 }
700 #else
701 void init_task_runnable_average(struct task_struct *p)
702 {
703 }
704 #endif
705
706 /*
707  * Update the current task's runtime statistics.
708  */
709 static void update_curr(struct cfs_rq *cfs_rq)
710 {
711         struct sched_entity *curr = cfs_rq->curr;
712         u64 now = rq_clock_task(rq_of(cfs_rq));
713         u64 delta_exec;
714
715         if (unlikely(!curr))
716                 return;
717
718         delta_exec = now - curr->exec_start;
719         if (unlikely((s64)delta_exec <= 0))
720                 return;
721
722         curr->exec_start = now;
723
724         schedstat_set(curr->statistics.exec_max,
725                       max(delta_exec, curr->statistics.exec_max));
726
727         curr->sum_exec_runtime += delta_exec;
728         schedstat_add(cfs_rq, exec_clock, delta_exec);
729
730         curr->vruntime += calc_delta_fair(delta_exec, curr);
731         update_min_vruntime(cfs_rq);
732
733         if (entity_is_task(curr)) {
734                 struct task_struct *curtask = task_of(curr);
735
736                 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
737                 cpuacct_charge(curtask, delta_exec);
738                 account_group_exec_runtime(curtask, delta_exec);
739         }
740
741         account_cfs_rq_runtime(cfs_rq, delta_exec);
742 }
743
744 static inline void
745 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
746 {
747         schedstat_set(se->statistics.wait_start, rq_clock(rq_of(cfs_rq)));
748 }
749
750 /*
751  * Task is being enqueued - update stats:
752  */
753 static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
754 {
755         /*
756          * Are we enqueueing a waiting task? (for current tasks
757          * a dequeue/enqueue event is a NOP)
758          */
759         if (se != cfs_rq->curr)
760                 update_stats_wait_start(cfs_rq, se);
761 }
762
763 static void
764 update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
765 {
766         schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
767                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start));
768         schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
769         schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
770                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
771 #ifdef CONFIG_SCHEDSTATS
772         if (entity_is_task(se)) {
773                 trace_sched_stat_wait(task_of(se),
774                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
775         }
776 #endif
777         schedstat_set(se->statistics.wait_start, 0);
778 }
779
780 static inline void
781 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
782 {
783         /*
784          * Mark the end of the wait period if dequeueing a
785          * waiting task:
786          */
787         if (se != cfs_rq->curr)
788                 update_stats_wait_end(cfs_rq, se);
789 }
790
791 /*
792  * We are picking a new current task - update its stats:
793  */
794 static inline void
795 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
796 {
797         /*
798          * We are starting a new run period:
799          */
800         se->exec_start = rq_clock_task(rq_of(cfs_rq));
801 }
802
803 /**************************************************
804  * Scheduling class queueing methods:
805  */
806
807 #ifdef CONFIG_NUMA_BALANCING
808 /*
809  * Approximate time to scan a full NUMA task in ms. The task scan period is
810  * calculated based on the tasks virtual memory size and
811  * numa_balancing_scan_size.
812  */
813 unsigned int sysctl_numa_balancing_scan_period_min = 1000;
814 unsigned int sysctl_numa_balancing_scan_period_max = 60000;
815
816 /* Portion of address space to scan in MB */
817 unsigned int sysctl_numa_balancing_scan_size = 256;
818
819 /* Scan @scan_size MB every @scan_period after an initial @scan_delay in ms */
820 unsigned int sysctl_numa_balancing_scan_delay = 1000;
821
822 /*
823  * After skipping a page migration on a shared page, skip N more numa page
824  * migrations unconditionally. This reduces the number of NUMA migrations
825  * in shared memory workloads, and has the effect of pulling tasks towards
826  * where their memory lives, over pulling the memory towards the task.
827  */
828 unsigned int sysctl_numa_balancing_migrate_deferred = 16;
829
830 static unsigned int task_nr_scan_windows(struct task_struct *p)
831 {
832         unsigned long rss = 0;
833         unsigned long nr_scan_pages;
834
835         /*
836          * Calculations based on RSS as non-present and empty pages are skipped
837          * by the PTE scanner and NUMA hinting faults should be trapped based
838          * on resident pages
839          */
840         nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT);
841         rss = get_mm_rss(p->mm);
842         if (!rss)
843                 rss = nr_scan_pages;
844
845         rss = round_up(rss, nr_scan_pages);
846         return rss / nr_scan_pages;
847 }
848
849 /* For sanitys sake, never scan more PTEs than MAX_SCAN_WINDOW MB/sec. */
850 #define MAX_SCAN_WINDOW 2560
851
852 static unsigned int task_scan_min(struct task_struct *p)
853 {
854         unsigned int scan, floor;
855         unsigned int windows = 1;
856
857         if (sysctl_numa_balancing_scan_size < MAX_SCAN_WINDOW)
858                 windows = MAX_SCAN_WINDOW / sysctl_numa_balancing_scan_size;
859         floor = 1000 / windows;
860
861         scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p);
862         return max_t(unsigned int, floor, scan);
863 }
864
865 static unsigned int task_scan_max(struct task_struct *p)
866 {
867         unsigned int smin = task_scan_min(p);
868         unsigned int smax;
869
870         /* Watch for min being lower than max due to floor calculations */
871         smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p);
872         return max(smin, smax);
873 }
874
875 /*
876  * Once a preferred node is selected the scheduler balancer will prefer moving
877  * a task to that node for sysctl_numa_balancing_settle_count number of PTE
878  * scans. This will give the process the chance to accumulate more faults on
879  * the preferred node but still allow the scheduler to move the task again if
880  * the nodes CPUs are overloaded.
881  */
882 unsigned int sysctl_numa_balancing_settle_count __read_mostly = 4;
883
884 static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
885 {
886         rq->nr_numa_running += (p->numa_preferred_nid != -1);
887         rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
888 }
889
890 static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
891 {
892         rq->nr_numa_running -= (p->numa_preferred_nid != -1);
893         rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
894 }
895
896 struct numa_group {
897         atomic_t refcount;
898
899         spinlock_t lock; /* nr_tasks, tasks */
900         int nr_tasks;
901         pid_t gid;
902         struct list_head task_list;
903
904         struct rcu_head rcu;
905         unsigned long total_faults;
906         unsigned long faults[0];
907 };
908
909 pid_t task_numa_group_id(struct task_struct *p)
910 {
911         return p->numa_group ? p->numa_group->gid : 0;
912 }
913
914 static inline int task_faults_idx(int nid, int priv)
915 {
916         return 2 * nid + priv;
917 }
918
919 static inline unsigned long task_faults(struct task_struct *p, int nid)
920 {
921         if (!p->numa_faults)
922                 return 0;
923
924         return p->numa_faults[task_faults_idx(nid, 0)] +
925                 p->numa_faults[task_faults_idx(nid, 1)];
926 }
927
928 static inline unsigned long group_faults(struct task_struct *p, int nid)
929 {
930         if (!p->numa_group)
931                 return 0;
932
933         return p->numa_group->faults[2*nid] + p->numa_group->faults[2*nid+1];
934 }
935
936 /*
937  * These return the fraction of accesses done by a particular task, or
938  * task group, on a particular numa node.  The group weight is given a
939  * larger multiplier, in order to group tasks together that are almost
940  * evenly spread out between numa nodes.
941  */
942 static inline unsigned long task_weight(struct task_struct *p, int nid)
943 {
944         unsigned long total_faults;
945
946         if (!p->numa_faults)
947                 return 0;
948
949         total_faults = p->total_numa_faults;
950
951         if (!total_faults)
952                 return 0;
953
954         return 1000 * task_faults(p, nid) / total_faults;
955 }
956
957 static inline unsigned long group_weight(struct task_struct *p, int nid)
958 {
959         if (!p->numa_group || !p->numa_group->total_faults)
960                 return 0;
961
962         return 1000 * group_faults(p, nid) / p->numa_group->total_faults;
963 }
964
965 static unsigned long weighted_cpuload(const int cpu);
966 static unsigned long source_load(int cpu, int type);
967 static unsigned long target_load(int cpu, int type);
968 static unsigned long power_of(int cpu);
969 static long effective_load(struct task_group *tg, int cpu, long wl, long wg);
970
971 /* Cached statistics for all CPUs within a node */
972 struct numa_stats {
973         unsigned long nr_running;
974         unsigned long load;
975
976         /* Total compute capacity of CPUs on a node */
977         unsigned long power;
978
979         /* Approximate capacity in terms of runnable tasks on a node */
980         unsigned long capacity;
981         int has_capacity;
982 };
983
984 /*
985  * XXX borrowed from update_sg_lb_stats
986  */
987 static void update_numa_stats(struct numa_stats *ns, int nid)
988 {
989         int cpu, cpus = 0;
990
991         memset(ns, 0, sizeof(*ns));
992         for_each_cpu(cpu, cpumask_of_node(nid)) {
993                 struct rq *rq = cpu_rq(cpu);
994
995                 ns->nr_running += rq->nr_running;
996                 ns->load += weighted_cpuload(cpu);
997                 ns->power += power_of(cpu);
998
999                 cpus++;
1000         }
1001
1002         /*
1003          * If we raced with hotplug and there are no CPUs left in our mask
1004          * the @ns structure is NULL'ed and task_numa_compare() will
1005          * not find this node attractive.
1006          *
1007          * We'll either bail at !has_capacity, or we'll detect a huge imbalance
1008          * and bail there.
1009          */
1010         if (!cpus)
1011                 return;
1012
1013         ns->load = (ns->load * SCHED_POWER_SCALE) / ns->power;
1014         ns->capacity = DIV_ROUND_CLOSEST(ns->power, SCHED_POWER_SCALE);
1015         ns->has_capacity = (ns->nr_running < ns->capacity);
1016 }
1017
1018 struct task_numa_env {
1019         struct task_struct *p;
1020
1021         int src_cpu, src_nid;
1022         int dst_cpu, dst_nid;
1023
1024         struct numa_stats src_stats, dst_stats;
1025
1026         int imbalance_pct, idx;
1027
1028         struct task_struct *best_task;
1029         long best_imp;
1030         int best_cpu;
1031 };
1032
1033 static void task_numa_assign(struct task_numa_env *env,
1034                              struct task_struct *p, long imp)
1035 {
1036         if (env->best_task)
1037                 put_task_struct(env->best_task);
1038         if (p)
1039                 get_task_struct(p);
1040
1041         env->best_task = p;
1042         env->best_imp = imp;
1043         env->best_cpu = env->dst_cpu;
1044 }
1045
1046 /*
1047  * This checks if the overall compute and NUMA accesses of the system would
1048  * be improved if the source tasks was migrated to the target dst_cpu taking
1049  * into account that it might be best if task running on the dst_cpu should
1050  * be exchanged with the source task
1051  */
1052 static void task_numa_compare(struct task_numa_env *env,
1053                               long taskimp, long groupimp)
1054 {
1055         struct rq *src_rq = cpu_rq(env->src_cpu);
1056         struct rq *dst_rq = cpu_rq(env->dst_cpu);
1057         struct task_struct *cur;
1058         long dst_load, src_load;
1059         long load;
1060         long imp = (groupimp > 0) ? groupimp : taskimp;
1061
1062         rcu_read_lock();
1063         cur = ACCESS_ONCE(dst_rq->curr);
1064         if (cur->pid == 0) /* idle */
1065                 cur = NULL;
1066
1067         /*
1068          * "imp" is the fault differential for the source task between the
1069          * source and destination node. Calculate the total differential for
1070          * the source task and potential destination task. The more negative
1071          * the value is, the more rmeote accesses that would be expected to
1072          * be incurred if the tasks were swapped.
1073          */
1074         if (cur) {
1075                 /* Skip this swap candidate if cannot move to the source cpu */
1076                 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
1077                         goto unlock;
1078
1079                 /*
1080                  * If dst and source tasks are in the same NUMA group, or not
1081                  * in any group then look only at task weights.
1082                  */
1083                 if (cur->numa_group == env->p->numa_group) {
1084                         imp = taskimp + task_weight(cur, env->src_nid) -
1085                               task_weight(cur, env->dst_nid);
1086                         /*
1087                          * Add some hysteresis to prevent swapping the
1088                          * tasks within a group over tiny differences.
1089                          */
1090                         if (cur->numa_group)
1091                                 imp -= imp/16;
1092                 } else {
1093                         /*
1094                          * Compare the group weights. If a task is all by
1095                          * itself (not part of a group), use the task weight
1096                          * instead.
1097                          */
1098                         if (env->p->numa_group)
1099                                 imp = groupimp;
1100                         else
1101                                 imp = taskimp;
1102
1103                         if (cur->numa_group)
1104                                 imp += group_weight(cur, env->src_nid) -
1105                                        group_weight(cur, env->dst_nid);
1106                         else
1107                                 imp += task_weight(cur, env->src_nid) -
1108                                        task_weight(cur, env->dst_nid);
1109                 }
1110         }
1111
1112         if (imp < env->best_imp)
1113                 goto unlock;
1114
1115         if (!cur) {
1116                 /* Is there capacity at our destination? */
1117                 if (env->src_stats.has_capacity &&
1118                     !env->dst_stats.has_capacity)
1119                         goto unlock;
1120
1121                 goto balance;
1122         }
1123
1124         /* Balance doesn't matter much if we're running a task per cpu */
1125         if (src_rq->nr_running == 1 && dst_rq->nr_running == 1)
1126                 goto assign;
1127
1128         /*
1129          * In the overloaded case, try and keep the load balanced.
1130          */
1131 balance:
1132         dst_load = env->dst_stats.load;
1133         src_load = env->src_stats.load;
1134
1135         /* XXX missing power terms */
1136         load = task_h_load(env->p);
1137         dst_load += load;
1138         src_load -= load;
1139
1140         if (cur) {
1141                 load = task_h_load(cur);
1142                 dst_load -= load;
1143                 src_load += load;
1144         }
1145
1146         /* make src_load the smaller */
1147         if (dst_load < src_load)
1148                 swap(dst_load, src_load);
1149
1150         if (src_load * env->imbalance_pct < dst_load * 100)
1151                 goto unlock;
1152
1153 assign:
1154         task_numa_assign(env, cur, imp);
1155 unlock:
1156         rcu_read_unlock();
1157 }
1158
1159 static void task_numa_find_cpu(struct task_numa_env *env,
1160                                 long taskimp, long groupimp)
1161 {
1162         int cpu;
1163
1164         for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
1165                 /* Skip this CPU if the source task cannot migrate */
1166                 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
1167                         continue;
1168
1169                 env->dst_cpu = cpu;
1170                 task_numa_compare(env, taskimp, groupimp);
1171         }
1172 }
1173
1174 static int task_numa_migrate(struct task_struct *p)
1175 {
1176         struct task_numa_env env = {
1177                 .p = p,
1178
1179                 .src_cpu = task_cpu(p),
1180                 .src_nid = task_node(p),
1181
1182                 .imbalance_pct = 112,
1183
1184                 .best_task = NULL,
1185                 .best_imp = 0,
1186                 .best_cpu = -1
1187         };
1188         struct sched_domain *sd;
1189         unsigned long taskweight, groupweight;
1190         int nid, ret;
1191         long taskimp, groupimp;
1192
1193         /*
1194          * Pick the lowest SD_NUMA domain, as that would have the smallest
1195          * imbalance and would be the first to start moving tasks about.
1196          *
1197          * And we want to avoid any moving of tasks about, as that would create
1198          * random movement of tasks -- counter the numa conditions we're trying
1199          * to satisfy here.
1200          */
1201         rcu_read_lock();
1202         sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
1203         if (sd)
1204                 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
1205         rcu_read_unlock();
1206
1207         /*
1208          * Cpusets can break the scheduler domain tree into smaller
1209          * balance domains, some of which do not cross NUMA boundaries.
1210          * Tasks that are "trapped" in such domains cannot be migrated
1211          * elsewhere, so there is no point in (re)trying.
1212          */
1213         if (unlikely(!sd)) {
1214                 p->numa_preferred_nid = cpu_to_node(task_cpu(p));
1215                 return -EINVAL;
1216         }
1217
1218         taskweight = task_weight(p, env.src_nid);
1219         groupweight = group_weight(p, env.src_nid);
1220         update_numa_stats(&env.src_stats, env.src_nid);
1221         env.dst_nid = p->numa_preferred_nid;
1222         taskimp = task_weight(p, env.dst_nid) - taskweight;
1223         groupimp = group_weight(p, env.dst_nid) - groupweight;
1224         update_numa_stats(&env.dst_stats, env.dst_nid);
1225
1226         /* If the preferred nid has capacity, try to use it. */
1227         if (env.dst_stats.has_capacity)
1228                 task_numa_find_cpu(&env, taskimp, groupimp);
1229
1230         /* No space available on the preferred nid. Look elsewhere. */
1231         if (env.best_cpu == -1) {
1232                 for_each_online_node(nid) {
1233                         if (nid == env.src_nid || nid == p->numa_preferred_nid)
1234                                 continue;
1235
1236                         /* Only consider nodes where both task and groups benefit */
1237                         taskimp = task_weight(p, nid) - taskweight;
1238                         groupimp = group_weight(p, nid) - groupweight;
1239                         if (taskimp < 0 && groupimp < 0)
1240                                 continue;
1241
1242                         env.dst_nid = nid;
1243                         update_numa_stats(&env.dst_stats, env.dst_nid);
1244                         task_numa_find_cpu(&env, taskimp, groupimp);
1245                 }
1246         }
1247
1248         /* No better CPU than the current one was found. */
1249         if (env.best_cpu == -1)
1250                 return -EAGAIN;
1251
1252         sched_setnuma(p, env.dst_nid);
1253
1254         /*
1255          * Reset the scan period if the task is being rescheduled on an
1256          * alternative node to recheck if the tasks is now properly placed.
1257          */
1258         p->numa_scan_period = task_scan_min(p);
1259
1260         if (env.best_task == NULL) {
1261                 int ret = migrate_task_to(p, env.best_cpu);
1262                 return ret;
1263         }
1264
1265         ret = migrate_swap(p, env.best_task);
1266         put_task_struct(env.best_task);
1267         return ret;
1268 }
1269
1270 /* Attempt to migrate a task to a CPU on the preferred node. */
1271 static void numa_migrate_preferred(struct task_struct *p)
1272 {
1273         /* This task has no NUMA fault statistics yet */
1274         if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults))
1275                 return;
1276
1277         /* Periodically retry migrating the task to the preferred node */
1278         p->numa_migrate_retry = jiffies + HZ;
1279
1280         /* Success if task is already running on preferred CPU */
1281         if (cpu_to_node(task_cpu(p)) == p->numa_preferred_nid)
1282                 return;
1283
1284         /* Otherwise, try migrate to a CPU on the preferred node */
1285         task_numa_migrate(p);
1286 }
1287
1288 /*
1289  * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS
1290  * increments. The more local the fault statistics are, the higher the scan
1291  * period will be for the next scan window. If local/remote ratio is below
1292  * NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS) the
1293  * scan period will decrease
1294  */
1295 #define NUMA_PERIOD_SLOTS 10
1296 #define NUMA_PERIOD_THRESHOLD 3
1297
1298 /*
1299  * Increase the scan period (slow down scanning) if the majority of
1300  * our memory is already on our local node, or if the majority of
1301  * the page accesses are shared with other processes.
1302  * Otherwise, decrease the scan period.
1303  */
1304 static void update_task_scan_period(struct task_struct *p,
1305                         unsigned long shared, unsigned long private)
1306 {
1307         unsigned int period_slot;
1308         int ratio;
1309         int diff;
1310
1311         unsigned long remote = p->numa_faults_locality[0];
1312         unsigned long local = p->numa_faults_locality[1];
1313
1314         /*
1315          * If there were no record hinting faults then either the task is
1316          * completely idle or all activity is areas that are not of interest
1317          * to automatic numa balancing. Scan slower
1318          */
1319         if (local + shared == 0) {
1320                 p->numa_scan_period = min(p->numa_scan_period_max,
1321                         p->numa_scan_period << 1);
1322
1323                 p->mm->numa_next_scan = jiffies +
1324                         msecs_to_jiffies(p->numa_scan_period);
1325
1326                 return;
1327         }
1328
1329         /*
1330          * Prepare to scale scan period relative to the current period.
1331          *       == NUMA_PERIOD_THRESHOLD scan period stays the same
1332          *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
1333          *       >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
1334          */
1335         period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
1336         ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
1337         if (ratio >= NUMA_PERIOD_THRESHOLD) {
1338                 int slot = ratio - NUMA_PERIOD_THRESHOLD;
1339                 if (!slot)
1340                         slot = 1;
1341                 diff = slot * period_slot;
1342         } else {
1343                 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
1344
1345                 /*
1346                  * Scale scan rate increases based on sharing. There is an
1347                  * inverse relationship between the degree of sharing and
1348                  * the adjustment made to the scanning period. Broadly
1349                  * speaking the intent is that there is little point
1350                  * scanning faster if shared accesses dominate as it may
1351                  * simply bounce migrations uselessly
1352                  */
1353                 period_slot = DIV_ROUND_UP(diff, NUMA_PERIOD_SLOTS);
1354                 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared));
1355                 diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
1356         }
1357
1358         p->numa_scan_period = clamp(p->numa_scan_period + diff,
1359                         task_scan_min(p), task_scan_max(p));
1360         memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1361 }
1362
1363 static void task_numa_placement(struct task_struct *p)
1364 {
1365         int seq, nid, max_nid = -1, max_group_nid = -1;
1366         unsigned long max_faults = 0, max_group_faults = 0;
1367         unsigned long fault_types[2] = { 0, 0 };
1368         spinlock_t *group_lock = NULL;
1369
1370         seq = ACCESS_ONCE(p->mm->numa_scan_seq);
1371         if (p->numa_scan_seq == seq)
1372                 return;
1373         p->numa_scan_seq = seq;
1374         p->numa_scan_period_max = task_scan_max(p);
1375
1376         /* If the task is part of a group prevent parallel updates to group stats */
1377         if (p->numa_group) {
1378                 group_lock = &p->numa_group->lock;
1379                 spin_lock(group_lock);
1380         }
1381
1382         /* Find the node with the highest number of faults */
1383         for_each_online_node(nid) {
1384                 unsigned long faults = 0, group_faults = 0;
1385                 int priv, i;
1386
1387                 for (priv = 0; priv < 2; priv++) {
1388                         long diff;
1389
1390                         i = task_faults_idx(nid, priv);
1391                         diff = -p->numa_faults[i];
1392
1393                         /* Decay existing window, copy faults since last scan */
1394                         p->numa_faults[i] >>= 1;
1395                         p->numa_faults[i] += p->numa_faults_buffer[i];
1396                         fault_types[priv] += p->numa_faults_buffer[i];
1397                         p->numa_faults_buffer[i] = 0;
1398
1399                         faults += p->numa_faults[i];
1400                         diff += p->numa_faults[i];
1401                         p->total_numa_faults += diff;
1402                         if (p->numa_group) {
1403                                 /* safe because we can only change our own group */
1404                                 p->numa_group->faults[i] += diff;
1405                                 p->numa_group->total_faults += diff;
1406                                 group_faults += p->numa_group->faults[i];
1407                         }
1408                 }
1409
1410                 if (faults > max_faults) {
1411                         max_faults = faults;
1412                         max_nid = nid;
1413                 }
1414
1415                 if (group_faults > max_group_faults) {
1416                         max_group_faults = group_faults;
1417                         max_group_nid = nid;
1418                 }
1419         }
1420
1421         update_task_scan_period(p, fault_types[0], fault_types[1]);
1422
1423         if (p->numa_group) {
1424                 /*
1425                  * If the preferred task and group nids are different,
1426                  * iterate over the nodes again to find the best place.
1427                  */
1428                 if (max_nid != max_group_nid) {
1429                         unsigned long weight, max_weight = 0;
1430
1431                         for_each_online_node(nid) {
1432                                 weight = task_weight(p, nid) + group_weight(p, nid);
1433                                 if (weight > max_weight) {
1434                                         max_weight = weight;
1435                                         max_nid = nid;
1436                                 }
1437                         }
1438                 }
1439
1440                 spin_unlock(group_lock);
1441         }
1442
1443         /* Preferred node as the node with the most faults */
1444         if (max_faults && max_nid != p->numa_preferred_nid) {
1445                 /* Update the preferred nid and migrate task if possible */
1446                 sched_setnuma(p, max_nid);
1447                 numa_migrate_preferred(p);
1448         }
1449 }
1450
1451 static inline int get_numa_group(struct numa_group *grp)
1452 {
1453         return atomic_inc_not_zero(&grp->refcount);
1454 }
1455
1456 static inline void put_numa_group(struct numa_group *grp)
1457 {
1458         if (atomic_dec_and_test(&grp->refcount))
1459                 kfree_rcu(grp, rcu);
1460 }
1461
1462 static void task_numa_group(struct task_struct *p, int cpupid, int flags,
1463                         int *priv)
1464 {
1465         struct numa_group *grp, *my_grp;
1466         struct task_struct *tsk;
1467         bool join = false;
1468         int cpu = cpupid_to_cpu(cpupid);
1469         int i;
1470
1471         if (unlikely(!p->numa_group)) {
1472                 unsigned int size = sizeof(struct numa_group) +
1473                                     2*nr_node_ids*sizeof(unsigned long);
1474
1475                 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
1476                 if (!grp)
1477                         return;
1478
1479                 atomic_set(&grp->refcount, 1);
1480                 spin_lock_init(&grp->lock);
1481                 INIT_LIST_HEAD(&grp->task_list);
1482                 grp->gid = p->pid;
1483
1484                 for (i = 0; i < 2*nr_node_ids; i++)
1485                         grp->faults[i] = p->numa_faults[i];
1486
1487                 grp->total_faults = p->total_numa_faults;
1488
1489                 list_add(&p->numa_entry, &grp->task_list);
1490                 grp->nr_tasks++;
1491                 rcu_assign_pointer(p->numa_group, grp);
1492         }
1493
1494         rcu_read_lock();
1495         tsk = ACCESS_ONCE(cpu_rq(cpu)->curr);
1496
1497         if (!cpupid_match_pid(tsk, cpupid))
1498                 goto no_join;
1499
1500         grp = rcu_dereference(tsk->numa_group);
1501         if (!grp)
1502                 goto no_join;
1503
1504         my_grp = p->numa_group;
1505         if (grp == my_grp)
1506                 goto no_join;
1507
1508         /*
1509          * Only join the other group if its bigger; if we're the bigger group,
1510          * the other task will join us.
1511          */
1512         if (my_grp->nr_tasks > grp->nr_tasks)
1513                 goto no_join;
1514
1515         /*
1516          * Tie-break on the grp address.
1517          */
1518         if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
1519                 goto no_join;
1520
1521         /* Always join threads in the same process. */
1522         if (tsk->mm == current->mm)
1523                 join = true;
1524
1525         /* Simple filter to avoid false positives due to PID collisions */
1526         if (flags & TNF_SHARED)
1527                 join = true;
1528
1529         /* Update priv based on whether false sharing was detected */
1530         *priv = !join;
1531
1532         if (join && !get_numa_group(grp))
1533                 goto no_join;
1534
1535         rcu_read_unlock();
1536
1537         if (!join)
1538                 return;
1539
1540         double_lock(&my_grp->lock, &grp->lock);
1541
1542         for (i = 0; i < 2*nr_node_ids; i++) {
1543                 my_grp->faults[i] -= p->numa_faults[i];
1544                 grp->faults[i] += p->numa_faults[i];
1545         }
1546         my_grp->total_faults -= p->total_numa_faults;
1547         grp->total_faults += p->total_numa_faults;
1548
1549         list_move(&p->numa_entry, &grp->task_list);
1550         my_grp->nr_tasks--;
1551         grp->nr_tasks++;
1552
1553         spin_unlock(&my_grp->lock);
1554         spin_unlock(&grp->lock);
1555
1556         rcu_assign_pointer(p->numa_group, grp);
1557
1558         put_numa_group(my_grp);
1559         return;
1560
1561 no_join:
1562         rcu_read_unlock();
1563         return;
1564 }
1565
1566 void task_numa_free(struct task_struct *p)
1567 {
1568         struct numa_group *grp = p->numa_group;
1569         int i;
1570         void *numa_faults = p->numa_faults;
1571
1572         if (grp) {
1573                 spin_lock(&grp->lock);
1574                 for (i = 0; i < 2*nr_node_ids; i++)
1575                         grp->faults[i] -= p->numa_faults[i];
1576                 grp->total_faults -= p->total_numa_faults;
1577
1578                 list_del(&p->numa_entry);
1579                 grp->nr_tasks--;
1580                 spin_unlock(&grp->lock);
1581                 rcu_assign_pointer(p->numa_group, NULL);
1582                 put_numa_group(grp);
1583         }
1584
1585         p->numa_faults = NULL;
1586         p->numa_faults_buffer = NULL;
1587         kfree(numa_faults);
1588 }
1589
1590 /*
1591  * Got a PROT_NONE fault for a page on @node.
1592  */
1593 void task_numa_fault(int last_cpupid, int node, int pages, int flags)
1594 {
1595         struct task_struct *p = current;
1596         bool migrated = flags & TNF_MIGRATED;
1597         int priv;
1598
1599         if (!numabalancing_enabled)
1600                 return;
1601
1602         /* for example, ksmd faulting in a user's mm */
1603         if (!p->mm)
1604                 return;
1605
1606         /* Do not worry about placement if exiting */
1607         if (p->state == TASK_DEAD)
1608                 return;
1609
1610         /* Allocate buffer to track faults on a per-node basis */
1611         if (unlikely(!p->numa_faults)) {
1612                 int size = sizeof(*p->numa_faults) * 2 * nr_node_ids;
1613
1614                 /* numa_faults and numa_faults_buffer share the allocation */
1615                 p->numa_faults = kzalloc(size * 2, GFP_KERNEL|__GFP_NOWARN);
1616                 if (!p->numa_faults)
1617                         return;
1618
1619                 BUG_ON(p->numa_faults_buffer);
1620                 p->numa_faults_buffer = p->numa_faults + (2 * nr_node_ids);
1621                 p->total_numa_faults = 0;
1622                 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1623         }
1624
1625         /*
1626          * First accesses are treated as private, otherwise consider accesses
1627          * to be private if the accessing pid has not changed
1628          */
1629         if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
1630                 priv = 1;
1631         } else {
1632                 priv = cpupid_match_pid(p, last_cpupid);
1633                 if (!priv && !(flags & TNF_NO_GROUP))
1634                         task_numa_group(p, last_cpupid, flags, &priv);
1635         }
1636
1637         task_numa_placement(p);
1638
1639         /*
1640          * Retry task to preferred node migration periodically, in case it
1641          * case it previously failed, or the scheduler moved us.
1642          */
1643         if (time_after(jiffies, p->numa_migrate_retry))
1644                 numa_migrate_preferred(p);
1645
1646         if (migrated)
1647                 p->numa_pages_migrated += pages;
1648
1649         p->numa_faults_buffer[task_faults_idx(node, priv)] += pages;
1650         p->numa_faults_locality[!!(flags & TNF_FAULT_LOCAL)] += pages;
1651 }
1652
1653 static void reset_ptenuma_scan(struct task_struct *p)
1654 {
1655         ACCESS_ONCE(p->mm->numa_scan_seq)++;
1656         p->mm->numa_scan_offset = 0;
1657 }
1658
1659 /*
1660  * The expensive part of numa migration is done from task_work context.
1661  * Triggered from task_tick_numa().
1662  */
1663 void task_numa_work(struct callback_head *work)
1664 {
1665         unsigned long migrate, next_scan, now = jiffies;
1666         struct task_struct *p = current;
1667         struct mm_struct *mm = p->mm;
1668         struct vm_area_struct *vma;
1669         unsigned long start, end;
1670         unsigned long nr_pte_updates = 0;
1671         long pages;
1672
1673         WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work));
1674
1675         work->next = work; /* protect against double add */
1676         /*
1677          * Who cares about NUMA placement when they're dying.
1678          *
1679          * NOTE: make sure not to dereference p->mm before this check,
1680          * exit_task_work() happens _after_ exit_mm() so we could be called
1681          * without p->mm even though we still had it when we enqueued this
1682          * work.
1683          */
1684         if (p->flags & PF_EXITING)
1685                 return;
1686
1687         if (!mm->numa_next_scan) {
1688                 mm->numa_next_scan = now +
1689                         msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
1690         }
1691
1692         /*
1693          * Enforce maximal scan/migration frequency..
1694          */
1695         migrate = mm->numa_next_scan;
1696         if (time_before(now, migrate))
1697                 return;
1698
1699         if (p->numa_scan_period == 0) {
1700                 p->numa_scan_period_max = task_scan_max(p);
1701                 p->numa_scan_period = task_scan_min(p);
1702         }
1703
1704         next_scan = now + msecs_to_jiffies(p->numa_scan_period);
1705         if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
1706                 return;
1707
1708         /*
1709          * Delay this task enough that another task of this mm will likely win
1710          * the next time around.
1711          */
1712         p->node_stamp += 2 * TICK_NSEC;
1713
1714         start = mm->numa_scan_offset;
1715         pages = sysctl_numa_balancing_scan_size;
1716         pages <<= 20 - PAGE_SHIFT; /* MB in pages */
1717         if (!pages)
1718                 return;
1719
1720         down_read(&mm->mmap_sem);
1721         vma = find_vma(mm, start);
1722         if (!vma) {
1723                 reset_ptenuma_scan(p);
1724                 start = 0;
1725                 vma = mm->mmap;
1726         }
1727         for (; vma; vma = vma->vm_next) {
1728                 if (!vma_migratable(vma) || !vma_policy_mof(p, vma))
1729                         continue;
1730
1731                 /*
1732                  * Shared library pages mapped by multiple processes are not
1733                  * migrated as it is expected they are cache replicated. Avoid
1734                  * hinting faults in read-only file-backed mappings or the vdso
1735                  * as migrating the pages will be of marginal benefit.
1736                  */
1737                 if (!vma->vm_mm ||
1738                     (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
1739                         continue;
1740
1741                 do {
1742                         start = max(start, vma->vm_start);
1743                         end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
1744                         end = min(end, vma->vm_end);
1745                         nr_pte_updates += change_prot_numa(vma, start, end);
1746
1747                         /*
1748                          * Scan sysctl_numa_balancing_scan_size but ensure that
1749                          * at least one PTE is updated so that unused virtual
1750                          * address space is quickly skipped.
1751                          */
1752                         if (nr_pte_updates)
1753                                 pages -= (end - start) >> PAGE_SHIFT;
1754
1755                         start = end;
1756                         if (pages <= 0)
1757                                 goto out;
1758                 } while (end != vma->vm_end);
1759         }
1760
1761 out:
1762         /*
1763          * It is possible to reach the end of the VMA list but the last few
1764          * VMAs are not guaranteed to the vma_migratable. If they are not, we
1765          * would find the !migratable VMA on the next scan but not reset the
1766          * scanner to the start so check it now.
1767          */
1768         if (vma)
1769                 mm->numa_scan_offset = start;
1770         else
1771                 reset_ptenuma_scan(p);
1772         up_read(&mm->mmap_sem);
1773 }
1774
1775 /*
1776  * Drive the periodic memory faults..
1777  */
1778 void task_tick_numa(struct rq *rq, struct task_struct *curr)
1779 {
1780         struct callback_head *work = &curr->numa_work;
1781         u64 period, now;
1782
1783         /*
1784          * We don't care about NUMA placement if we don't have memory.
1785          */
1786         if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
1787                 return;
1788
1789         /*
1790          * Using runtime rather than walltime has the dual advantage that
1791          * we (mostly) drive the selection from busy threads and that the
1792          * task needs to have done some actual work before we bother with
1793          * NUMA placement.
1794          */
1795         now = curr->se.sum_exec_runtime;
1796         period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
1797
1798         if (now - curr->node_stamp > period) {
1799                 if (!curr->node_stamp)
1800                         curr->numa_scan_period = task_scan_min(curr);
1801                 curr->node_stamp += period;
1802
1803                 if (!time_before(jiffies, curr->mm->numa_next_scan)) {
1804                         init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */
1805                         task_work_add(curr, work, true);
1806                 }
1807         }
1808 }
1809 #else
1810 static void task_tick_numa(struct rq *rq, struct task_struct *curr)
1811 {
1812 }
1813
1814 static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
1815 {
1816 }
1817
1818 static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
1819 {
1820 }
1821 #endif /* CONFIG_NUMA_BALANCING */
1822
1823 static void
1824 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
1825 {
1826         update_load_add(&cfs_rq->load, se->load.weight);
1827         if (!parent_entity(se))
1828                 update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
1829 #ifdef CONFIG_SMP
1830         if (entity_is_task(se)) {
1831                 struct rq *rq = rq_of(cfs_rq);
1832
1833                 account_numa_enqueue(rq, task_of(se));
1834                 list_add(&se->group_node, &rq->cfs_tasks);
1835         }
1836 #endif
1837         cfs_rq->nr_running++;
1838 }
1839
1840 static void
1841 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
1842 {
1843         update_load_sub(&cfs_rq->load, se->load.weight);
1844         if (!parent_entity(se))
1845                 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
1846         if (entity_is_task(se)) {
1847                 account_numa_dequeue(rq_of(cfs_rq), task_of(se));
1848                 list_del_init(&se->group_node);
1849         }
1850         cfs_rq->nr_running--;
1851 }
1852
1853 #ifdef CONFIG_FAIR_GROUP_SCHED
1854 # ifdef CONFIG_SMP
1855 static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
1856 {
1857         long tg_weight;
1858
1859         /*
1860          * Use this CPU's actual weight instead of the last load_contribution
1861          * to gain a more accurate current total weight. See
1862          * update_cfs_rq_load_contribution().
1863          */
1864         tg_weight = atomic_long_read(&tg->load_avg);
1865         tg_weight -= cfs_rq->tg_load_contrib;
1866         tg_weight += cfs_rq->load.weight;
1867
1868         return tg_weight;
1869 }
1870
1871 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
1872 {
1873         long tg_weight, load, shares;
1874
1875         tg_weight = calc_tg_weight(tg, cfs_rq);
1876         load = cfs_rq->load.weight;
1877
1878         shares = (tg->shares * load);
1879         if (tg_weight)
1880                 shares /= tg_weight;
1881
1882         if (shares < MIN_SHARES)
1883                 shares = MIN_SHARES;
1884         if (shares > tg->shares)
1885                 shares = tg->shares;
1886
1887         return shares;
1888 }
1889 # else /* CONFIG_SMP */
1890 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
1891 {
1892         return tg->shares;
1893 }
1894 # endif /* CONFIG_SMP */
1895 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
1896                             unsigned long weight)
1897 {
1898         if (se->on_rq) {
1899                 /* commit outstanding execution time */
1900                 if (cfs_rq->curr == se)
1901                         update_curr(cfs_rq);
1902                 account_entity_dequeue(cfs_rq, se);
1903         }
1904
1905         update_load_set(&se->load, weight);
1906
1907         if (se->on_rq)
1908                 account_entity_enqueue(cfs_rq, se);
1909 }
1910
1911 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
1912
1913 static void update_cfs_shares(struct cfs_rq *cfs_rq)
1914 {
1915         struct task_group *tg;
1916         struct sched_entity *se;
1917         long shares;
1918
1919         tg = cfs_rq->tg;
1920         se = tg->se[cpu_of(rq_of(cfs_rq))];
1921         if (!se || throttled_hierarchy(cfs_rq))
1922                 return;
1923 #ifndef CONFIG_SMP
1924         if (likely(se->load.weight == tg->shares))
1925                 return;
1926 #endif
1927         shares = calc_cfs_shares(cfs_rq, tg);
1928
1929         reweight_entity(cfs_rq_of(se), se, shares);
1930 }
1931 #else /* CONFIG_FAIR_GROUP_SCHED */
1932 static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
1933 {
1934 }
1935 #endif /* CONFIG_FAIR_GROUP_SCHED */
1936
1937 #ifdef CONFIG_SMP
1938 /*
1939  * We choose a half-life close to 1 scheduling period.
1940  * Note: The tables below are dependent on this value.
1941  */
1942 #define LOAD_AVG_PERIOD 32
1943 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
1944 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */
1945
1946 /* Precomputed fixed inverse multiplies for multiplication by y^n */
1947 static const u32 runnable_avg_yN_inv[] = {
1948         0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
1949         0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
1950         0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
1951         0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
1952         0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
1953         0x85aac367, 0x82cd8698,
1954 };
1955
1956 /*
1957  * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
1958  * over-estimates when re-combining.
1959  */
1960 static const u32 runnable_avg_yN_sum[] = {
1961             0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
1962          9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
1963         17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
1964 };
1965
1966 /*
1967  * Approximate:
1968  *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
1969  */
1970 static __always_inline u64 decay_load(u64 val, u64 n)
1971 {
1972         unsigned int local_n;
1973
1974         if (!n)
1975                 return val;
1976         else if (unlikely(n > LOAD_AVG_PERIOD * 63))
1977                 return 0;
1978
1979         /* after bounds checking we can collapse to 32-bit */
1980         local_n = n;
1981
1982         /*
1983          * As y^PERIOD = 1/2, we can combine
1984          *    y^n = 1/2^(n/PERIOD) * k^(n%PERIOD)
1985          * With a look-up table which covers k^n (n<PERIOD)
1986          *
1987          * To achieve constant time decay_load.
1988          */
1989         if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
1990                 val >>= local_n / LOAD_AVG_PERIOD;
1991                 local_n %= LOAD_AVG_PERIOD;
1992         }
1993
1994         val *= runnable_avg_yN_inv[local_n];
1995         /* We don't use SRR here since we always want to round down. */
1996         return val >> 32;
1997 }
1998
1999 /*
2000  * For updates fully spanning n periods, the contribution to runnable
2001  * average will be: \Sum 1024*y^n
2002  *
2003  * We can compute this reasonably efficiently by combining:
2004  *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
2005  */
2006 static u32 __compute_runnable_contrib(u64 n)
2007 {
2008         u32 contrib = 0;
2009
2010         if (likely(n <= LOAD_AVG_PERIOD))
2011                 return runnable_avg_yN_sum[n];
2012         else if (unlikely(n >= LOAD_AVG_MAX_N))
2013                 return LOAD_AVG_MAX;
2014
2015         /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
2016         do {
2017                 contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
2018                 contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
2019
2020                 n -= LOAD_AVG_PERIOD;
2021         } while (n > LOAD_AVG_PERIOD);
2022
2023         contrib = decay_load(contrib, n);
2024         return contrib + runnable_avg_yN_sum[n];
2025 }
2026
2027 /*
2028  * We can represent the historical contribution to runnable average as the
2029  * coefficients of a geometric series.  To do this we sub-divide our runnable
2030  * history into segments of approximately 1ms (1024us); label the segment that
2031  * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
2032  *
2033  * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
2034  *      p0            p1           p2
2035  *     (now)       (~1ms ago)  (~2ms ago)
2036  *
2037  * Let u_i denote the fraction of p_i that the entity was runnable.
2038  *
2039  * We then designate the fractions u_i as our co-efficients, yielding the
2040  * following representation of historical load:
2041  *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
2042  *
2043  * We choose y based on the with of a reasonably scheduling period, fixing:
2044  *   y^32 = 0.5
2045  *
2046  * This means that the contribution to load ~32ms ago (u_32) will be weighted
2047  * approximately half as much as the contribution to load within the last ms
2048  * (u_0).
2049  *
2050  * When a period "rolls over" and we have new u_0`, multiplying the previous
2051  * sum again by y is sufficient to update:
2052  *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
2053  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
2054  */
2055 static __always_inline int __update_entity_runnable_avg(u64 now,
2056                                                         struct sched_avg *sa,
2057                                                         int runnable)
2058 {
2059         u64 delta, periods;
2060         u32 runnable_contrib;
2061         int delta_w, decayed = 0;
2062
2063         delta = now - sa->last_runnable_update;
2064         /*
2065          * This should only happen when time goes backwards, which it
2066          * unfortunately does during sched clock init when we swap over to TSC.
2067          */
2068         if ((s64)delta < 0) {
2069                 sa->last_runnable_update = now;
2070                 return 0;
2071         }
2072
2073         /*
2074          * Use 1024ns as the unit of measurement since it's a reasonable
2075          * approximation of 1us and fast to compute.
2076          */
2077         delta >>= 10;
2078         if (!delta)
2079                 return 0;
2080         sa->last_runnable_update = now;
2081
2082         /* delta_w is the amount already accumulated against our next period */
2083         delta_w = sa->runnable_avg_period % 1024;
2084         if (delta + delta_w >= 1024) {
2085                 /* period roll-over */
2086                 decayed = 1;
2087
2088                 /*
2089                  * Now that we know we're crossing a period boundary, figure
2090                  * out how much from delta we need to complete the current
2091                  * period and accrue it.
2092                  */
2093                 delta_w = 1024 - delta_w;
2094                 if (runnable)
2095                         sa->runnable_avg_sum += delta_w;
2096                 sa->runnable_avg_period += delta_w;
2097
2098                 delta -= delta_w;
2099
2100                 /* Figure out how many additional periods this update spans */
2101                 periods = delta / 1024;
2102                 delta %= 1024;
2103
2104                 sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
2105                                                   periods + 1);
2106                 sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
2107                                                      periods + 1);
2108
2109                 /* Efficiently calculate \sum (1..n_period) 1024*y^i */
2110                 runnable_contrib = __compute_runnable_contrib(periods);
2111                 if (runnable)
2112                         sa->runnable_avg_sum += runnable_contrib;
2113                 sa->runnable_avg_period += runnable_contrib;
2114         }
2115
2116         /* Remainder of delta accrued against u_0` */
2117         if (runnable)
2118                 sa->runnable_avg_sum += delta;
2119         sa->runnable_avg_period += delta;
2120
2121         return decayed;
2122 }
2123
2124 /* Synchronize an entity's decay with its parenting cfs_rq.*/
2125 static inline u64 __synchronize_entity_decay(struct sched_entity *se)
2126 {
2127         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2128         u64 decays = atomic64_read(&cfs_rq->decay_counter);
2129
2130         decays -= se->avg.decay_count;
2131         if (!decays)
2132                 return 0;
2133
2134         se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);
2135         se->avg.decay_count = 0;
2136
2137         return decays;
2138 }
2139
2140 #ifdef CONFIG_FAIR_GROUP_SCHED
2141 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2142                                                  int force_update)
2143 {
2144         struct task_group *tg = cfs_rq->tg;
2145         long tg_contrib;
2146
2147         tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
2148         tg_contrib -= cfs_rq->tg_load_contrib;
2149
2150         if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
2151                 atomic_long_add(tg_contrib, &tg->load_avg);
2152                 cfs_rq->tg_load_contrib += tg_contrib;
2153         }
2154 }
2155
2156 /*
2157  * Aggregate cfs_rq runnable averages into an equivalent task_group
2158  * representation for computing load contributions.
2159  */
2160 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2161                                                   struct cfs_rq *cfs_rq)
2162 {
2163         struct task_group *tg = cfs_rq->tg;
2164         long contrib;
2165
2166         /* The fraction of a cpu used by this cfs_rq */
2167         contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
2168                           sa->runnable_avg_period + 1);
2169         contrib -= cfs_rq->tg_runnable_contrib;
2170
2171         if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
2172                 atomic_add(contrib, &tg->runnable_avg);
2173                 cfs_rq->tg_runnable_contrib += contrib;
2174         }
2175 }
2176
2177 static inline void __update_group_entity_contrib(struct sched_entity *se)
2178 {
2179         struct cfs_rq *cfs_rq = group_cfs_rq(se);
2180         struct task_group *tg = cfs_rq->tg;
2181         int runnable_avg;
2182
2183         u64 contrib;
2184
2185         contrib = cfs_rq->tg_load_contrib * tg->shares;
2186         se->avg.load_avg_contrib = div_u64(contrib,
2187                                      atomic_long_read(&tg->load_avg) + 1);
2188
2189         /*
2190          * For group entities we need to compute a correction term in the case
2191          * that they are consuming <1 cpu so that we would contribute the same
2192          * load as a task of equal weight.
2193          *
2194          * Explicitly co-ordinating this measurement would be expensive, but
2195          * fortunately the sum of each cpus contribution forms a usable
2196          * lower-bound on the true value.
2197          *
2198          * Consider the aggregate of 2 contributions.  Either they are disjoint
2199          * (and the sum represents true value) or they are disjoint and we are
2200          * understating by the aggregate of their overlap.
2201          *
2202          * Extending this to N cpus, for a given overlap, the maximum amount we
2203          * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of
2204          * cpus that overlap for this interval and w_i is the interval width.
2205          *
2206          * On a small machine; the first term is well-bounded which bounds the
2207          * total error since w_i is a subset of the period.  Whereas on a
2208          * larger machine, while this first term can be larger, if w_i is the
2209          * of consequential size guaranteed to see n_i*w_i quickly converge to
2210          * our upper bound of 1-cpu.
2211          */
2212         runnable_avg = atomic_read(&tg->runnable_avg);
2213         if (runnable_avg < NICE_0_LOAD) {
2214                 se->avg.load_avg_contrib *= runnable_avg;
2215                 se->avg.load_avg_contrib >>= NICE_0_SHIFT;
2216         }
2217 }
2218 #else
2219 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2220                                                  int force_update) {}
2221 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2222                                                   struct cfs_rq *cfs_rq) {}
2223 static inline void __update_group_entity_contrib(struct sched_entity *se) {}
2224 #endif
2225
2226 static inline void __update_task_entity_contrib(struct sched_entity *se)
2227 {
2228         u32 contrib;
2229
2230         /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
2231         contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
2232         contrib /= (se->avg.runnable_avg_period + 1);
2233         se->avg.load_avg_contrib = scale_load(contrib);
2234 }
2235
2236 /* Compute the current contribution to load_avg by se, return any delta */
2237 static long __update_entity_load_avg_contrib(struct sched_entity *se)
2238 {
2239         long old_contrib = se->avg.load_avg_contrib;
2240
2241         if (entity_is_task(se)) {
2242                 __update_task_entity_contrib(se);
2243         } else {
2244                 __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
2245                 __update_group_entity_contrib(se);
2246         }
2247
2248         return se->avg.load_avg_contrib - old_contrib;
2249 }
2250
2251 static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
2252                                                  long load_contrib)
2253 {
2254         if (likely(load_contrib < cfs_rq->blocked_load_avg))
2255                 cfs_rq->blocked_load_avg -= load_contrib;
2256         else
2257                 cfs_rq->blocked_load_avg = 0;
2258 }
2259
2260 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
2261
2262 /* Update a sched_entity's runnable average */
2263 static inline void update_entity_load_avg(struct sched_entity *se,
2264                                           int update_cfs_rq)
2265 {
2266         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2267         long contrib_delta;
2268         u64 now;
2269
2270         /*
2271          * For a group entity we need to use their owned cfs_rq_clock_task() in
2272          * case they are the parent of a throttled hierarchy.
2273          */
2274         if (entity_is_task(se))
2275                 now = cfs_rq_clock_task(cfs_rq);
2276         else
2277                 now = cfs_rq_clock_task(group_cfs_rq(se));
2278
2279         if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
2280                 return;
2281
2282         contrib_delta = __update_entity_load_avg_contrib(se);
2283
2284         if (!update_cfs_rq)
2285                 return;
2286
2287         if (se->on_rq)
2288                 cfs_rq->runnable_load_avg += contrib_delta;
2289         else
2290                 subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
2291 }
2292
2293 /*
2294  * Decay the load contributed by all blocked children and account this so that
2295  * their contribution may appropriately discounted when they wake up.
2296  */
2297 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
2298 {
2299         u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
2300         u64 decays;
2301
2302         decays = now - cfs_rq->last_decay;
2303         if (!decays && !force_update)
2304                 return;
2305
2306         if (atomic_long_read(&cfs_rq->removed_load)) {
2307                 unsigned long removed_load;
2308                 removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
2309                 subtract_blocked_load_contrib(cfs_rq, removed_load);
2310         }
2311
2312         if (decays) {
2313                 cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
2314                                                       decays);
2315                 atomic64_add(decays, &cfs_rq->decay_counter);
2316                 cfs_rq->last_decay = now;
2317         }
2318
2319         __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
2320 }
2321
2322 static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
2323 {
2324         __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
2325         __update_tg_runnable_avg(&rq->avg, &rq->cfs);
2326 }
2327
2328 /* Add the load generated by se into cfs_rq's child load-average */
2329 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2330                                                   struct sched_entity *se,
2331                                                   int wakeup)
2332 {
2333         /*
2334          * We track migrations using entity decay_count <= 0, on a wake-up
2335          * migration we use a negative decay count to track the remote decays
2336          * accumulated while sleeping.
2337          *
2338          * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
2339          * are seen by enqueue_entity_load_avg() as a migration with an already
2340          * constructed load_avg_contrib.
2341          */
2342         if (unlikely(se->avg.decay_count <= 0)) {
2343                 se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
2344                 if (se->avg.decay_count) {
2345                         /*
2346                          * In a wake-up migration we have to approximate the
2347                          * time sleeping.  This is because we can't synchronize
2348                          * clock_task between the two cpus, and it is not
2349                          * guaranteed to be read-safe.  Instead, we can
2350                          * approximate this using our carried decays, which are
2351                          * explicitly atomically readable.
2352                          */
2353                         se->avg.last_runnable_update -= (-se->avg.decay_count)
2354                                                         << 20;
2355                         update_entity_load_avg(se, 0);
2356                         /* Indicate that we're now synchronized and on-rq */
2357                         se->avg.decay_count = 0;
2358                 }
2359                 wakeup = 0;
2360         } else {
2361                 /*
2362                  * Task re-woke on same cpu (or else migrate_task_rq_fair()
2363                  * would have made count negative); we must be careful to avoid
2364                  * double-accounting blocked time after synchronizing decays.
2365                  */
2366                 se->avg.last_runnable_update += __synchronize_entity_decay(se)
2367                                                         << 20;
2368         }
2369
2370         /* migrated tasks did not contribute to our blocked load */
2371         if (wakeup) {
2372                 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
2373                 update_entity_load_avg(se, 0);
2374         }
2375
2376         cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
2377         /* we force update consideration on load-balancer moves */
2378         update_cfs_rq_blocked_load(cfs_rq, !wakeup);
2379 }
2380
2381 /*
2382  * Remove se's load from this cfs_rq child load-average, if the entity is
2383  * transitioning to a blocked state we track its projected decay using
2384  * blocked_load_avg.
2385  */
2386 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2387                                                   struct sched_entity *se,
2388                                                   int sleep)
2389 {
2390         update_entity_load_avg(se, 1);
2391         /* we force update consideration on load-balancer moves */
2392         update_cfs_rq_blocked_load(cfs_rq, !sleep);
2393
2394         cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
2395         if (sleep) {
2396                 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
2397                 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
2398         } /* migrations, e.g. sleep=0 leave decay_count == 0 */
2399 }
2400
2401 /*
2402  * Update the rq's load with the elapsed running time before entering
2403  * idle. if the last scheduled task is not a CFS task, idle_enter will
2404  * be the only way to update the runnable statistic.
2405  */
2406 void idle_enter_fair(struct rq *this_rq)
2407 {
2408         update_rq_runnable_avg(this_rq, 1);
2409 }
2410
2411 /*
2412  * Update the rq's load with the elapsed idle time before a task is
2413  * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
2414  * be the only way to update the runnable statistic.
2415  */
2416 void idle_exit_fair(struct rq *this_rq)
2417 {
2418         update_rq_runnable_avg(this_rq, 0);
2419 }
2420
2421 #else
2422 static inline void update_entity_load_avg(struct sched_entity *se,
2423                                           int update_cfs_rq) {}
2424 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2425 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2426                                            struct sched_entity *se,
2427                                            int wakeup) {}
2428 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2429                                            struct sched_entity *se,
2430                                            int sleep) {}
2431 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
2432                                               int force_update) {}
2433 #endif
2434
2435 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
2436 {
2437 #ifdef CONFIG_SCHEDSTATS
2438         struct task_struct *tsk = NULL;
2439
2440         if (entity_is_task(se))
2441                 tsk = task_of(se);
2442
2443         if (se->statistics.sleep_start) {
2444                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.sleep_start;
2445
2446                 if ((s64)delta < 0)
2447                         delta = 0;
2448
2449                 if (unlikely(delta > se->statistics.sleep_max))
2450                         se->statistics.sleep_max = delta;
2451
2452                 se->statistics.sleep_start = 0;
2453                 se->statistics.sum_sleep_runtime += delta;
2454
2455                 if (tsk) {
2456                         account_scheduler_latency(tsk, delta >> 10, 1);
2457                         trace_sched_stat_sleep(tsk, delta);
2458                 }
2459         }
2460         if (se->statistics.block_start) {
2461                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.block_start;
2462
2463                 if ((s64)delta < 0)
2464                         delta = 0;
2465
2466                 if (unlikely(delta > se->statistics.block_max))
2467                         se->statistics.block_max = delta;
2468
2469                 se->statistics.block_start = 0;
2470                 se->statistics.sum_sleep_runtime += delta;
2471
2472                 if (tsk) {
2473                         if (tsk->in_iowait) {
2474                                 se->statistics.iowait_sum += delta;
2475                                 se->statistics.iowait_count++;
2476                                 trace_sched_stat_iowait(tsk, delta);
2477                         }
2478
2479                         trace_sched_stat_blocked(tsk, delta);
2480
2481                         /*
2482                          * Blocking time is in units of nanosecs, so shift by
2483                          * 20 to get a milliseconds-range estimation of the
2484                          * amount of time that the task spent sleeping:
2485                          */
2486                         if (unlikely(prof_on == SLEEP_PROFILING)) {
2487                                 profile_hits(SLEEP_PROFILING,
2488                                                 (void *)get_wchan(tsk),
2489                                                 delta >> 20);
2490                         }
2491                         account_scheduler_latency(tsk, delta >> 10, 0);
2492                 }
2493         }
2494 #endif
2495 }
2496
2497 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
2498 {
2499 #ifdef CONFIG_SCHED_DEBUG
2500         s64 d = se->vruntime - cfs_rq->min_vruntime;
2501
2502         if (d < 0)
2503                 d = -d;
2504
2505         if (d > 3*sysctl_sched_latency)
2506                 schedstat_inc(cfs_rq, nr_spread_over);
2507 #endif
2508 }
2509
2510 static void
2511 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
2512 {
2513         u64 vruntime = cfs_rq->min_vruntime;
2514
2515         /*
2516          * The 'current' period is already promised to the current tasks,
2517          * however the extra weight of the new task will slow them down a
2518          * little, place the new task so that it fits in the slot that
2519          * stays open at the end.
2520          */
2521         if (initial && sched_feat(START_DEBIT))
2522                 vruntime += sched_vslice(cfs_rq, se);
2523
2524         /* sleeps up to a single latency don't count. */
2525         if (!initial) {
2526                 unsigned long thresh = sysctl_sched_latency;
2527
2528                 /*
2529                  * Halve their sleep time's effect, to allow
2530                  * for a gentler effect of sleepers:
2531                  */
2532                 if (sched_feat(GENTLE_FAIR_SLEEPERS))
2533                         thresh >>= 1;
2534
2535                 vruntime -= thresh;
2536         }
2537
2538         /* ensure we never gain time by being placed backwards. */
2539         se->vruntime = max_vruntime(se->vruntime, vruntime);
2540 }
2541
2542 static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
2543
2544 static void
2545 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2546 {
2547         /*
2548          * Update the normalized vruntime before updating min_vruntime
2549          * through calling update_curr().
2550          */
2551         if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
2552                 se->vruntime += cfs_rq->min_vruntime;
2553
2554         /*
2555          * Update run-time statistics of the 'current'.
2556          */
2557         update_curr(cfs_rq);
2558         enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
2559         account_entity_enqueue(cfs_rq, se);
2560         update_cfs_shares(cfs_rq);
2561
2562         if (flags & ENQUEUE_WAKEUP) {
2563                 place_entity(cfs_rq, se, 0);
2564                 enqueue_sleeper(cfs_rq, se);
2565         }
2566
2567         update_stats_enqueue(cfs_rq, se);
2568         check_spread(cfs_rq, se);
2569         if (se != cfs_rq->curr)
2570                 __enqueue_entity(cfs_rq, se);
2571         se->on_rq = 1;
2572
2573         if (cfs_rq->nr_running == 1) {
2574                 list_add_leaf_cfs_rq(cfs_rq);
2575                 check_enqueue_throttle(cfs_rq);
2576         }
2577 }
2578
2579 static void __clear_buddies_last(struct sched_entity *se)
2580 {
2581         for_each_sched_entity(se) {
2582                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2583                 if (cfs_rq->last == se)
2584                         cfs_rq->last = NULL;
2585                 else
2586                         break;
2587         }
2588 }
2589
2590 static void __clear_buddies_next(struct sched_entity *se)
2591 {
2592         for_each_sched_entity(se) {
2593                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2594                 if (cfs_rq->next == se)
2595                         cfs_rq->next = NULL;
2596                 else
2597                         break;
2598         }
2599 }
2600
2601 static void __clear_buddies_skip(struct sched_entity *se)
2602 {
2603         for_each_sched_entity(se) {
2604                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2605                 if (cfs_rq->skip == se)
2606                         cfs_rq->skip = NULL;
2607                 else
2608                         break;
2609         }
2610 }
2611
2612 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
2613 {
2614         if (cfs_rq->last == se)
2615                 __clear_buddies_last(se);
2616
2617         if (cfs_rq->next == se)
2618                 __clear_buddies_next(se);
2619
2620         if (cfs_rq->skip == se)
2621                 __clear_buddies_skip(se);
2622 }
2623
2624 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
2625
2626 static void
2627 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2628 {
2629         /*
2630          * Update run-time statistics of the 'current'.
2631          */
2632         update_curr(cfs_rq);
2633         dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP);
2634
2635         update_stats_dequeue(cfs_rq, se);
2636         if (flags & DEQUEUE_SLEEP) {
2637 #ifdef CONFIG_SCHEDSTATS
2638                 if (entity_is_task(se)) {
2639                         struct task_struct *tsk = task_of(se);
2640
2641                         if (tsk->state & TASK_INTERRUPTIBLE)
2642                                 se->statistics.sleep_start = rq_clock(rq_of(cfs_rq));
2643                         if (tsk->state & TASK_UNINTERRUPTIBLE)
2644                                 se->statistics.block_start = rq_clock(rq_of(cfs_rq));
2645                 }
2646 #endif
2647         }
2648
2649         clear_buddies(cfs_rq, se);
2650
2651         if (se != cfs_rq->curr)
2652                 __dequeue_entity(cfs_rq, se);
2653         se->on_rq = 0;
2654         account_entity_dequeue(cfs_rq, se);
2655
2656         /*
2657          * Normalize the entity after updating the min_vruntime because the
2658          * update can refer to the ->curr item and we need to reflect this
2659          * movement in our normalized position.
2660          */
2661         if (!(flags & DEQUEUE_SLEEP))
2662                 se->vruntime -= cfs_rq->min_vruntime;
2663
2664         /* return excess runtime on last dequeue */
2665         return_cfs_rq_runtime(cfs_rq);
2666
2667         update_min_vruntime(cfs_rq);
2668         update_cfs_shares(cfs_rq);
2669 }
2670
2671 /*
2672  * Preempt the current task with a newly woken task if needed:
2673  */
2674 static void
2675 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
2676 {
2677         unsigned long ideal_runtime, delta_exec;
2678         struct sched_entity *se;
2679         s64 delta;
2680
2681         ideal_runtime = sched_slice(cfs_rq, curr);
2682         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
2683         if (delta_exec > ideal_runtime) {
2684                 resched_task(rq_of(cfs_rq)->curr);
2685                 /*
2686                  * The current task ran long enough, ensure it doesn't get
2687                  * re-elected due to buddy favours.
2688                  */
2689                 clear_buddies(cfs_rq, curr);
2690                 return;
2691         }
2692
2693         /*
2694          * Ensure that a task that missed wakeup preemption by a
2695          * narrow margin doesn't have to wait for a full slice.
2696          * This also mitigates buddy induced latencies under load.
2697          */
2698         if (delta_exec < sysctl_sched_min_granularity)
2699                 return;
2700
2701         se = __pick_first_entity(cfs_rq);
2702         delta = curr->vruntime - se->vruntime;
2703
2704         if (delta < 0)
2705                 return;
2706
2707         if (delta > ideal_runtime)
2708                 resched_task(rq_of(cfs_rq)->curr);
2709 }
2710
2711 static void
2712 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
2713 {
2714         /* 'current' is not kept within the tree. */
2715         if (se->on_rq) {
2716                 /*
2717                  * Any task has to be enqueued before it get to execute on
2718                  * a CPU. So account for the time it spent waiting on the
2719                  * runqueue.
2720                  */
2721                 update_stats_wait_end(cfs_rq, se);
2722                 __dequeue_entity(cfs_rq, se);
2723         }
2724
2725         update_stats_curr_start(cfs_rq, se);
2726         cfs_rq->curr = se;
2727 #ifdef CONFIG_SCHEDSTATS
2728         /*
2729          * Track our maximum slice length, if the CPU's load is at
2730          * least twice that of our own weight (i.e. dont track it
2731          * when there are only lesser-weight tasks around):
2732          */
2733         if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
2734                 se->statistics.slice_max = max(se->statistics.slice_max,
2735                         se->sum_exec_runtime - se->prev_sum_exec_runtime);
2736         }
2737 #endif
2738         se->prev_sum_exec_runtime = se->sum_exec_runtime;
2739 }
2740
2741 static int
2742 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
2743
2744 /*
2745  * Pick the next process, keeping these things in mind, in this order:
2746  * 1) keep things fair between processes/task groups
2747  * 2) pick the "next" process, since someone really wants that to run
2748  * 3) pick the "last" process, for cache locality
2749  * 4) do not run the "skip" process, if something else is available
2750  */
2751 static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
2752 {
2753         struct sched_entity *se = __pick_first_entity(cfs_rq);
2754         struct sched_entity *left = se;
2755
2756         /*
2757          * Avoid running the skip buddy, if running something else can
2758          * be done without getting too unfair.
2759          */
2760         if (cfs_rq->skip == se) {
2761                 struct sched_entity *second = __pick_next_entity(se);
2762                 if (second && wakeup_preempt_entity(second, left) < 1)
2763                         se = second;
2764         }
2765
2766         /*
2767          * Prefer last buddy, try to return the CPU to a preempted task.
2768          */
2769         if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
2770                 se = cfs_rq->last;
2771
2772         /*
2773          * Someone really wants this to run. If it's not unfair, run it.
2774          */
2775         if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
2776                 se = cfs_rq->next;
2777
2778         clear_buddies(cfs_rq, se);
2779
2780         return se;
2781 }
2782
2783 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
2784
2785 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
2786 {
2787         /*
2788          * If still on the runqueue then deactivate_task()
2789          * was not called and update_curr() has to be done:
2790          */
2791         if (prev->on_rq)
2792                 update_curr(cfs_rq);
2793
2794         /* throttle cfs_rqs exceeding runtime */
2795         check_cfs_rq_runtime(cfs_rq);
2796
2797         check_spread(cfs_rq, prev);
2798         if (prev->on_rq) {
2799                 update_stats_wait_start(cfs_rq, prev);
2800                 /* Put 'current' back into the tree. */
2801                 __enqueue_entity(cfs_rq, prev);
2802                 /* in !on_rq case, update occurred at dequeue */
2803                 update_entity_load_avg(prev, 1);
2804         }
2805         cfs_rq->curr = NULL;
2806 }
2807
2808 static void
2809 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
2810 {
2811         /*
2812          * Update run-time statistics of the 'current'.
2813          */
2814         update_curr(cfs_rq);
2815
2816         /*
2817          * Ensure that runnable average is periodically updated.
2818          */
2819         update_entity_load_avg(curr, 1);
2820         update_cfs_rq_blocked_load(cfs_rq, 1);
2821         update_cfs_shares(cfs_rq);
2822
2823 #ifdef CONFIG_SCHED_HRTICK
2824         /*
2825          * queued ticks are scheduled to match the slice, so don't bother
2826          * validating it and just reschedule.
2827          */
2828         if (queued) {
2829                 resched_task(rq_of(cfs_rq)->curr);
2830                 return;
2831         }
2832         /*
2833          * don't let the period tick interfere with the hrtick preemption
2834          */
2835         if (!sched_feat(DOUBLE_TICK) &&
2836                         hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
2837                 return;
2838 #endif
2839
2840         if (cfs_rq->nr_running > 1)
2841                 check_preempt_tick(cfs_rq, curr);
2842 }
2843
2844
2845 /**************************************************
2846  * CFS bandwidth control machinery
2847  */
2848
2849 #ifdef CONFIG_CFS_BANDWIDTH
2850
2851 #ifdef HAVE_JUMP_LABEL
2852 static struct static_key __cfs_bandwidth_used;
2853
2854 static inline bool cfs_bandwidth_used(void)
2855 {
2856         return static_key_false(&__cfs_bandwidth_used);
2857 }
2858
2859 void cfs_bandwidth_usage_inc(void)
2860 {
2861         static_key_slow_inc(&__cfs_bandwidth_used);
2862 }
2863
2864 void cfs_bandwidth_usage_dec(void)
2865 {
2866         static_key_slow_dec(&__cfs_bandwidth_used);
2867 }
2868 #else /* HAVE_JUMP_LABEL */
2869 static bool cfs_bandwidth_used(void)
2870 {
2871         return true;
2872 }
2873
2874 void cfs_bandwidth_usage_inc(void) {}
2875 void cfs_bandwidth_usage_dec(void) {}
2876 #endif /* HAVE_JUMP_LABEL */
2877
2878 /*
2879  * default period for cfs group bandwidth.
2880  * default: 0.1s, units: nanoseconds
2881  */
2882 static inline u64 default_cfs_period(void)
2883 {
2884         return 100000000ULL;
2885 }
2886
2887 static inline u64 sched_cfs_bandwidth_slice(void)
2888 {
2889         return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
2890 }
2891
2892 /*
2893  * Replenish runtime according to assigned quota and update expiration time.
2894  * We use sched_clock_cpu directly instead of rq->clock to avoid adding
2895  * additional synchronization around rq->lock.
2896  *
2897  * requires cfs_b->lock
2898  */
2899 void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b)
2900 {
2901         u64 now;
2902
2903         if (cfs_b->quota == RUNTIME_INF)
2904                 return;
2905
2906         now = sched_clock_cpu(smp_processor_id());
2907         cfs_b->runtime = cfs_b->quota;
2908         cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period);
2909 }
2910
2911 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
2912 {
2913         return &tg->cfs_bandwidth;
2914 }
2915
2916 /* rq->task_clock normalized against any time this cfs_rq has spent throttled */
2917 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
2918 {
2919         if (unlikely(cfs_rq->throttle_count))
2920                 return cfs_rq->throttled_clock_task;
2921
2922         return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
2923 }
2924
2925 /* returns 0 on failure to allocate runtime */
2926 static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
2927 {
2928         struct task_group *tg = cfs_rq->tg;
2929         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
2930         u64 amount = 0, min_amount, expires;
2931
2932         /* note: this is a positive sum as runtime_remaining <= 0 */
2933         min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;
2934
2935         raw_spin_lock(&cfs_b->lock);
2936         if (cfs_b->quota == RUNTIME_INF)
2937                 amount = min_amount;
2938         else {
2939                 /*
2940                  * If the bandwidth pool has become inactive, then at least one
2941                  * period must have elapsed since the last consumption.
2942                  * Refresh the global state and ensure bandwidth timer becomes
2943                  * active.
2944                  */
2945                 if (!cfs_b->timer_active) {
2946                         __refill_cfs_bandwidth_runtime(cfs_b);
2947                         __start_cfs_bandwidth(cfs_b);
2948                 }
2949
2950                 if (cfs_b->runtime > 0) {
2951                         amount = min(cfs_b->runtime, min_amount);
2952                         cfs_b->runtime -= amount;
2953                         cfs_b->idle = 0;
2954                 }
2955         }
2956         expires = cfs_b->runtime_expires;
2957         raw_spin_unlock(&cfs_b->lock);
2958
2959         cfs_rq->runtime_remaining += amount;
2960         /*
2961          * we may have advanced our local expiration to account for allowed
2962          * spread between our sched_clock and the one on which runtime was
2963          * issued.
2964          */
2965         if ((s64)(expires - cfs_rq->runtime_expires) > 0)
2966                 cfs_rq->runtime_expires = expires;
2967
2968         return cfs_rq->runtime_remaining > 0;
2969 }
2970
2971 /*
2972  * Note: This depends on the synchronization provided by sched_clock and the
2973  * fact that rq->clock snapshots this value.
2974  */
2975 static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
2976 {
2977         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
2978
2979         /* if the deadline is ahead of our clock, nothing to do */
2980         if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
2981                 return;
2982
2983         if (cfs_rq->runtime_remaining < 0)
2984                 return;
2985
2986         /*
2987          * If the local deadline has passed we have to consider the
2988          * possibility that our sched_clock is 'fast' and the global deadline
2989          * has not truly expired.
2990          *
2991          * Fortunately we can check determine whether this the case by checking
2992          * whether the global deadline has advanced.
2993          */
2994
2995         if ((s64)(cfs_rq->runtime_expires - cfs_b->runtime_expires) >= 0) {
2996                 /* extend local deadline, drift is bounded above by 2 ticks */
2997                 cfs_rq->runtime_expires += TICK_NSEC;
2998         } else {
2999                 /* global deadline is ahead, expiration has passed */
3000                 cfs_rq->runtime_remaining = 0;
3001         }
3002 }
3003
3004 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3005 {
3006         /* dock delta_exec before expiring quota (as it could span periods) */
3007         cfs_rq->runtime_remaining -= delta_exec;
3008         expire_cfs_rq_runtime(cfs_rq);
3009
3010         if (likely(cfs_rq->runtime_remaining > 0))
3011                 return;
3012
3013         /*
3014          * if we're unable to extend our runtime we resched so that the active
3015          * hierarchy can be throttled
3016          */
3017         if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
3018                 resched_task(rq_of(cfs_rq)->curr);
3019 }
3020
3021 static __always_inline
3022 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3023 {
3024         if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
3025                 return;
3026
3027         __account_cfs_rq_runtime(cfs_rq, delta_exec);
3028 }
3029
3030 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3031 {
3032         return cfs_bandwidth_used() && cfs_rq->throttled;
3033 }
3034
3035 /* check whether cfs_rq, or any parent, is throttled */
3036 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3037 {
3038         return cfs_bandwidth_used() && cfs_rq->throttle_count;
3039 }
3040
3041 /*
3042  * Ensure that neither of the group entities corresponding to src_cpu or
3043  * dest_cpu are members of a throttled hierarchy when performing group
3044  * load-balance operations.
3045  */
3046 static inline int throttled_lb_pair(struct task_group *tg,
3047                                     int src_cpu, int dest_cpu)
3048 {
3049         struct cfs_rq *src_cfs_rq, *dest_cfs_rq;
3050
3051         src_cfs_rq = tg->cfs_rq[src_cpu];
3052         dest_cfs_rq = tg->cfs_rq[dest_cpu];
3053
3054         return throttled_hierarchy(src_cfs_rq) ||
3055                throttled_hierarchy(dest_cfs_rq);
3056 }
3057
3058 /* updated child weight may affect parent so we have to do this bottom up */
3059 static int tg_unthrottle_up(struct task_group *tg, void *data)
3060 {
3061         struct rq *rq = data;
3062         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3063
3064         cfs_rq->throttle_count--;
3065 #ifdef CONFIG_SMP
3066         if (!cfs_rq->throttle_count) {
3067                 /* adjust cfs_rq_clock_task() */
3068                 cfs_rq->throttled_clock_task_time += rq_clock_task(rq) -
3069                                              cfs_rq->throttled_clock_task;
3070         }
3071 #endif
3072
3073         return 0;
3074 }
3075
3076 static int tg_throttle_down(struct task_group *tg, void *data)
3077 {
3078         struct rq *rq = data;
3079         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3080
3081         /* group is entering throttled state, stop time */
3082         if (!cfs_rq->throttle_count)
3083                 cfs_rq->throttled_clock_task = rq_clock_task(rq);
3084         cfs_rq->throttle_count++;
3085
3086         return 0;
3087 }
3088
3089 static void throttle_cfs_rq(struct cfs_rq *cfs_rq)
3090 {
3091         struct rq *rq = rq_of(cfs_rq);
3092         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3093         struct sched_entity *se;
3094         long task_delta, dequeue = 1;
3095
3096         se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
3097
3098         /* freeze hierarchy runnable averages while throttled */
3099         rcu_read_lock();
3100         walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
3101         rcu_read_unlock();
3102
3103         task_delta = cfs_rq->h_nr_running;
3104         for_each_sched_entity(se) {
3105                 struct cfs_rq *qcfs_rq = cfs_rq_of(se);
3106                 /* throttled entity or throttle-on-deactivate */
3107                 if (!se->on_rq)
3108                         break;
3109
3110                 if (dequeue)
3111                         dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
3112                 qcfs_rq->h_nr_running -= task_delta;
3113
3114                 if (qcfs_rq->load.weight)
3115                         dequeue = 0;
3116         }
3117
3118         if (!se)
3119                 rq->nr_running -= task_delta;
3120
3121         cfs_rq->throttled = 1;
3122         cfs_rq->throttled_clock = rq_clock(rq);
3123         raw_spin_lock(&cfs_b->lock);
3124         list_add_tail_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq);
3125         if (!cfs_b->timer_active)
3126                 __start_cfs_bandwidth(cfs_b);
3127         raw_spin_unlock(&cfs_b->lock);
3128 }
3129
3130 void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
3131 {
3132         struct rq *rq = rq_of(cfs_rq);
3133         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3134         struct sched_entity *se;
3135         int enqueue = 1;
3136         long task_delta;
3137
3138         se = cfs_rq->tg->se[cpu_of(rq)];
3139
3140         cfs_rq->throttled = 0;
3141
3142         update_rq_clock(rq);
3143
3144         raw_spin_lock(&cfs_b->lock);
3145         cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
3146         list_del_rcu(&cfs_rq->throttled_list);
3147         raw_spin_unlock(&cfs_b->lock);
3148
3149         /* update hierarchical throttle state */
3150         walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
3151
3152         if (!cfs_rq->load.weight)
3153                 return;
3154
3155         task_delta = cfs_rq->h_nr_running;
3156         for_each_sched_entity(se) {
3157                 if (se->on_rq)
3158                         enqueue = 0;
3159
3160                 cfs_rq = cfs_rq_of(se);
3161                 if (enqueue)
3162                         enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);
3163                 cfs_rq->h_nr_running += task_delta;
3164
3165                 if (cfs_rq_throttled(cfs_rq))
3166                         break;
3167         }
3168
3169         if (!se)
3170                 rq->nr_running += task_delta;
3171
3172         /* determine whether we need to wake up potentially idle cpu */
3173         if (rq->curr == rq->idle && rq->cfs.nr_running)
3174                 resched_task(rq->curr);
3175 }
3176
3177 static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b,
3178                 u64 remaining, u64 expires)
3179 {
3180         struct cfs_rq *cfs_rq;
3181         u64 runtime = remaining;
3182
3183         rcu_read_lock();
3184         list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
3185                                 throttled_list) {
3186                 struct rq *rq = rq_of(cfs_rq);
3187
3188                 raw_spin_lock(&rq->lock);
3189                 if (!cfs_rq_throttled(cfs_rq))
3190                         goto next;
3191
3192                 runtime = -cfs_rq->runtime_remaining + 1;
3193                 if (runtime > remaining)
3194                         runtime = remaining;
3195                 remaining -= runtime;
3196
3197                 cfs_rq->runtime_remaining += runtime;
3198                 cfs_rq->runtime_expires = expires;
3199
3200                 /* we check whether we're throttled above */
3201                 if (cfs_rq->runtime_remaining > 0)
3202                         unthrottle_cfs_rq(cfs_rq);
3203
3204 next:
3205                 raw_spin_unlock(&rq->lock);
3206
3207                 if (!remaining)
3208                         break;
3209         }
3210         rcu_read_unlock();
3211
3212         return remaining;
3213 }
3214
3215 /*
3216  * Responsible for refilling a task_group's bandwidth and unthrottling its
3217  * cfs_rqs as appropriate. If there has been no activity within the last
3218  * period the timer is deactivated until scheduling resumes; cfs_b->idle is
3219  * used to track this state.
3220  */
3221 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
3222 {
3223         u64 runtime, runtime_expires;
3224         int idle = 1, throttled;
3225
3226         raw_spin_lock(&cfs_b->lock);
3227         /* no need to continue the timer with no bandwidth constraint */
3228         if (cfs_b->quota == RUNTIME_INF)
3229                 goto out_unlock;
3230
3231         throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3232         /* idle depends on !throttled (for the case of a large deficit) */
3233         idle = cfs_b->idle && !throttled;
3234         cfs_b->nr_periods += overrun;
3235
3236         /* if we're going inactive then everything else can be deferred */
3237         if (idle)
3238                 goto out_unlock;
3239
3240         /*
3241          * if we have relooped after returning idle once, we need to update our
3242          * status as actually running, so that other cpus doing
3243          * __start_cfs_bandwidth will stop trying to cancel us.
3244          */
3245         cfs_b->timer_active = 1;
3246
3247         __refill_cfs_bandwidth_runtime(cfs_b);
3248
3249         if (!throttled) {
3250                 /* mark as potentially idle for the upcoming period */
3251                 cfs_b->idle = 1;
3252                 goto out_unlock;
3253         }
3254
3255         /* account preceding periods in which throttling occurred */
3256         cfs_b->nr_throttled += overrun;
3257
3258         /*
3259          * There are throttled entities so we must first use the new bandwidth
3260          * to unthrottle them before making it generally available.  This
3261          * ensures that all existing debts will be paid before a new cfs_rq is
3262          * allowed to run.
3263          */
3264         runtime = cfs_b->runtime;
3265         runtime_expires = cfs_b->runtime_expires;
3266         cfs_b->runtime = 0;
3267
3268         /*
3269          * This check is repeated as we are holding onto the new bandwidth
3270          * while we unthrottle.  This can potentially race with an unthrottled
3271          * group trying to acquire new bandwidth from the global pool.
3272          */
3273         while (throttled && runtime > 0) {
3274                 raw_spin_unlock(&cfs_b->lock);
3275                 /* we can't nest cfs_b->lock while distributing bandwidth */
3276                 runtime = distribute_cfs_runtime(cfs_b, runtime,
3277                                                  runtime_expires);
3278                 raw_spin_lock(&cfs_b->lock);
3279
3280                 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3281         }
3282
3283         /* return (any) remaining runtime */
3284         cfs_b->runtime = runtime;
3285         /*
3286          * While we are ensured activity in the period following an
3287          * unthrottle, this also covers the case in which the new bandwidth is
3288          * insufficient to cover the existing bandwidth deficit.  (Forcing the
3289          * timer to remain active while there are any throttled entities.)
3290          */
3291         cfs_b->idle = 0;
3292 out_unlock:
3293         if (idle)
3294                 cfs_b->timer_active = 0;
3295         raw_spin_unlock(&cfs_b->lock);
3296
3297         return idle;
3298 }
3299
3300 /* a cfs_rq won't donate quota below this amount */
3301 static const u64 min_cfs_rq_runtime = 1 * NSEC_PER_MSEC;
3302 /* minimum remaining period time to redistribute slack quota */
3303 static const u64 min_bandwidth_expiration = 2 * NSEC_PER_MSEC;
3304 /* how long we wait to gather additional slack before distributing */
3305 static const u64 cfs_bandwidth_slack_period = 5 * NSEC_PER_MSEC;
3306
3307 /*
3308  * Are we near the end of the current quota period?
3309  *
3310  * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the
3311  * hrtimer base being cleared by __hrtimer_start_range_ns. In the case of
3312  * migrate_hrtimers, base is never cleared, so we are fine.
3313  */
3314 static int runtime_refresh_within(struct cfs_bandwidth *cfs_b, u64 min_expire)
3315 {
3316         struct hrtimer *refresh_timer = &cfs_b->period_timer;
3317         u64 remaining;
3318
3319         /* if the call-back is running a quota refresh is already occurring */
3320         if (hrtimer_callback_running(refresh_timer))
3321                 return 1;
3322
3323         /* is a quota refresh about to occur? */
3324         remaining = ktime_to_ns(hrtimer_expires_remaining(refresh_timer));
3325         if (remaining < min_expire)
3326                 return 1;
3327
3328         return 0;
3329 }
3330
3331 static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
3332 {
3333         u64 min_left = cfs_bandwidth_slack_period + min_bandwidth_expiration;
3334
3335         /* if there's a quota refresh soon don't bother with slack */
3336         if (runtime_refresh_within(cfs_b, min_left))
3337                 return;
3338
3339         start_bandwidth_timer(&cfs_b->slack_timer,
3340                                 ns_to_ktime(cfs_bandwidth_slack_period));
3341 }
3342
3343 /* we know any runtime found here is valid as update_curr() precedes return */
3344 static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3345 {
3346         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3347         s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;
3348
3349         if (slack_runtime <= 0)
3350                 return;
3351
3352         raw_spin_lock(&cfs_b->lock);
3353         if (cfs_b->quota != RUNTIME_INF &&
3354             cfs_rq->runtime_expires == cfs_b->runtime_expires) {
3355                 cfs_b->runtime += slack_runtime;
3356
3357                 /* we are under rq->lock, defer unthrottling using a timer */
3358                 if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
3359                     !list_empty(&cfs_b->throttled_cfs_rq))
3360                         start_cfs_slack_bandwidth(cfs_b);
3361         }
3362         raw_spin_unlock(&cfs_b->lock);
3363
3364         /* even if it's not valid for return we don't want to try again */
3365         cfs_rq->runtime_remaining -= slack_runtime;
3366 }
3367
3368 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3369 {
3370         if (!cfs_bandwidth_used())
3371                 return;
3372
3373         if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
3374                 return;
3375
3376         __return_cfs_rq_runtime(cfs_rq);
3377 }
3378
3379 /*
3380  * This is done with a timer (instead of inline with bandwidth return) since
3381  * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs.
3382  */
3383 static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
3384 {
3385         u64 runtime = 0, slice = sched_cfs_bandwidth_slice();
3386         u64 expires;
3387
3388         /* confirm we're still not at a refresh boundary */
3389         raw_spin_lock(&cfs_b->lock);
3390         if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) {
3391                 raw_spin_unlock(&cfs_b->lock);
3392                 return;
3393         }
3394
3395         if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice) {
3396                 runtime = cfs_b->runtime;
3397                 cfs_b->runtime = 0;
3398         }
3399         expires = cfs_b->runtime_expires;
3400         raw_spin_unlock(&cfs_b->lock);
3401
3402         if (!runtime)
3403                 return;
3404
3405         runtime = distribute_cfs_runtime(cfs_b, runtime, expires);
3406
3407         raw_spin_lock(&cfs_b->lock);
3408         if (expires == cfs_b->runtime_expires)
3409                 cfs_b->runtime = runtime;
3410         raw_spin_unlock(&cfs_b->lock);
3411 }
3412
3413 /*
3414  * When a group wakes up we want to make sure that its quota is not already
3415  * expired/exceeded, otherwise it may be allowed to steal additional ticks of
3416  * runtime as update_curr() throttling can not not trigger until it's on-rq.
3417  */
3418 static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
3419 {
3420         if (!cfs_bandwidth_used())
3421                 return;
3422
3423         /* an active group must be handled by the update_curr()->put() path */
3424         if (!cfs_rq->runtime_enabled || cfs_rq->curr)
3425                 return;
3426
3427         /* ensure the group is not already throttled */
3428         if (cfs_rq_throttled(cfs_rq))
3429                 return;
3430
3431         /* update runtime allocation */
3432         account_cfs_rq_runtime(cfs_rq, 0);
3433         if (cfs_rq->runtime_remaining <= 0)
3434                 throttle_cfs_rq(cfs_rq);
3435 }
3436
3437 /* conditionally throttle active cfs_rq's from put_prev_entity() */
3438 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3439 {
3440         if (!cfs_bandwidth_used())
3441                 return;
3442
3443         if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
3444                 return;
3445
3446         /*
3447          * it's possible for a throttled entity to be forced into a running
3448          * state (e.g. set_curr_task), in this case we're finished.
3449          */
3450         if (cfs_rq_throttled(cfs_rq))
3451                 return;
3452
3453         throttle_cfs_rq(cfs_rq);
3454 }
3455
3456 static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer)
3457 {
3458         struct cfs_bandwidth *cfs_b =
3459                 container_of(timer, struct cfs_bandwidth, slack_timer);
3460         do_sched_cfs_slack_timer(cfs_b);
3461
3462         return HRTIMER_NORESTART;
3463 }
3464
3465 static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
3466 {
3467         struct cfs_bandwidth *cfs_b =
3468                 container_of(timer, struct cfs_bandwidth, period_timer);
3469         ktime_t now;
3470         int overrun;
3471         int idle = 0;
3472
3473         for (;;) {
3474                 now = hrtimer_cb_get_time(timer);
3475                 overrun = hrtimer_forward(timer, now, cfs_b->period);
3476
3477                 if (!overrun)
3478                         break;
3479
3480                 idle = do_sched_cfs_period_timer(cfs_b, overrun);
3481         }
3482
3483         return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
3484 }
3485
3486 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3487 {
3488         raw_spin_lock_init(&cfs_b->lock);
3489         cfs_b->runtime = 0;
3490         cfs_b->quota = RUNTIME_INF;
3491         cfs_b->period = ns_to_ktime(default_cfs_period());
3492
3493         INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
3494         hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3495         cfs_b->period_timer.function = sched_cfs_period_timer;
3496         hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3497         cfs_b->slack_timer.function = sched_cfs_slack_timer;
3498 }
3499
3500 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3501 {
3502         cfs_rq->runtime_enabled = 0;
3503         INIT_LIST_HEAD(&cfs_rq->throttled_list);
3504 }
3505
3506 /* requires cfs_b->lock, may release to reprogram timer */
3507 void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3508 {
3509         /*
3510          * The timer may be active because we're trying to set a new bandwidth
3511          * period or because we're racing with the tear-down path
3512          * (timer_active==0 becomes visible before the hrtimer call-back
3513          * terminates).  In either case we ensure that it's re-programmed
3514          */
3515         while (unlikely(hrtimer_active(&cfs_b->period_timer)) &&
3516                hrtimer_try_to_cancel(&cfs_b->period_timer) < 0) {
3517                 /* bounce the lock to allow do_sched_cfs_period_timer to run */
3518                 raw_spin_unlock(&cfs_b->lock);
3519                 cpu_relax();
3520                 raw_spin_lock(&cfs_b->lock);
3521                 /* if someone else restarted the timer then we're done */
3522                 if (cfs_b->timer_active)
3523                         return;
3524         }
3525
3526         cfs_b->timer_active = 1;
3527         start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
3528 }
3529
3530 static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3531 {
3532         hrtimer_cancel(&cfs_b->period_timer);
3533         hrtimer_cancel(&cfs_b->slack_timer);
3534 }
3535
3536 static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq)
3537 {
3538         struct cfs_rq *cfs_rq;
3539
3540         for_each_leaf_cfs_rq(rq, cfs_rq) {
3541                 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3542
3543                 if (!cfs_rq->runtime_enabled)
3544                         continue;
3545
3546                 /*
3547                  * clock_task is not advancing so we just need to make sure
3548                  * there's some valid quota amount
3549                  */
3550                 cfs_rq->runtime_remaining = cfs_b->quota;
3551                 if (cfs_rq_throttled(cfs_rq))
3552                         unthrottle_cfs_rq(cfs_rq);
3553         }
3554 }
3555
3556 #else /* CONFIG_CFS_BANDWIDTH */
3557 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
3558 {
3559         return rq_clock_task(rq_of(cfs_rq));
3560 }
3561
3562 static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) {}
3563 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3564 static void check_enqueue_throttle(struct cfs_rq *cfs_rq) {}
3565 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3566
3567 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3568 {
3569         return 0;
3570 }
3571
3572 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3573 {
3574         return 0;
3575 }
3576
3577 static inline int throttled_lb_pair(struct task_group *tg,
3578                                     int src_cpu, int dest_cpu)
3579 {
3580         return 0;
3581 }
3582
3583 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
3584
3585 #ifdef CONFIG_FAIR_GROUP_SCHED
3586 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3587 #endif
3588
3589 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
3590 {
3591         return NULL;
3592 }
3593 static inline void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
3594 static inline void unthrottle_offline_cfs_rqs(struct rq *rq) {}
3595
3596 #endif /* CONFIG_CFS_BANDWIDTH */
3597
3598 /**************************************************
3599  * CFS operations on tasks:
3600  */
3601
3602 #ifdef CONFIG_SCHED_HRTICK
3603 static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
3604 {
3605         struct sched_entity *se = &p->se;
3606         struct cfs_rq *cfs_rq = cfs_rq_of(se);
3607
3608         WARN_ON(task_rq(p) != rq);
3609
3610         if (cfs_rq->nr_running > 1) {
3611                 u64 slice = sched_slice(cfs_rq, se);
3612                 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
3613                 s64 delta = slice - ran;
3614
3615                 if (delta < 0) {
3616                         if (rq->curr == p)
3617                                 resched_task(p);
3618                         return;
3619                 }
3620
3621                 /*
3622                  * Don't schedule slices shorter than 10000ns, that just
3623                  * doesn't make sense. Rely on vruntime for fairness.
3624                  */
3625                 if (rq->curr != p)
3626                         delta = max_t(s64, 10000LL, delta);
3627
3628                 hrtick_start(rq, delta);
3629         }
3630 }
3631
3632 /*
3633  * called from enqueue/dequeue and updates the hrtick when the
3634  * current task is from our class and nr_running is low enough
3635  * to matter.
3636  */
3637 static void hrtick_update(struct rq *rq)
3638 {
3639         struct task_struct *curr = rq->curr;
3640
3641         if (!hrtick_enabled(rq) || curr->sched_class != &fair_sched_class)
3642                 return;
3643
3644         if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
3645                 hrtick_start_fair(rq, curr);
3646 }
3647 #else /* !CONFIG_SCHED_HRTICK */
3648 static inline void
3649 hrtick_start_fair(struct rq *rq, struct task_struct *p)
3650 {
3651 }
3652
3653 static inline void hrtick_update(struct rq *rq)
3654 {
3655 }
3656 #endif
3657
3658 /*
3659  * The enqueue_task method is called before nr_running is
3660  * increased. Here we update the fair scheduling stats and
3661  * then put the task into the rbtree:
3662  */
3663 static void
3664 enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
3665 {
3666         struct cfs_rq *cfs_rq;
3667         struct sched_entity *se = &p->se;
3668
3669         for_each_sched_entity(se) {
3670                 if (se->on_rq)
3671                         break;
3672                 cfs_rq = cfs_rq_of(se);
3673                 enqueue_entity(cfs_rq, se, flags);
3674
3675                 /*
3676                  * end evaluation on encountering a throttled cfs_rq
3677                  *
3678                  * note: in the case of encountering a throttled cfs_rq we will
3679                  * post the final h_nr_running increment below.
3680                 */
3681                 if (cfs_rq_throttled(cfs_rq))
3682                         break;
3683                 cfs_rq->h_nr_running++;
3684
3685                 flags = ENQUEUE_WAKEUP;
3686         }
3687
3688         for_each_sched_entity(se) {
3689                 cfs_rq = cfs_rq_of(se);
3690                 cfs_rq->h_nr_running++;
3691
3692                 if (cfs_rq_throttled(cfs_rq))
3693                         break;
3694
3695                 update_cfs_shares(cfs_rq);
3696                 update_entity_load_avg(se, 1);
3697         }
3698
3699         if (!se) {
3700                 update_rq_runnable_avg(rq, rq->nr_running);
3701                 inc_nr_running(rq);
3702         }
3703         hrtick_update(rq);
3704 }
3705
3706 static void set_next_buddy(struct sched_entity *se);
3707
3708 /*
3709  * The dequeue_task method is called before nr_running is
3710  * decreased. We remove the task from the rbtree and
3711  * update the fair scheduling stats:
3712  */
3713 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
3714 {
3715         struct cfs_rq *cfs_rq;
3716         struct sched_entity *se = &p->se;
3717         int task_sleep = flags & DEQUEUE_SLEEP;
3718
3719         for_each_sched_entity(se) {
3720                 cfs_rq = cfs_rq_of(se);
3721                 dequeue_entity(cfs_rq, se, flags);
3722
3723                 /*
3724                  * end evaluation on encountering a throttled cfs_rq
3725                  *
3726                  * note: in the case of encountering a throttled cfs_rq we will
3727                  * post the final h_nr_running decrement below.
3728                 */
3729                 if (cfs_rq_throttled(cfs_rq))
3730                         break;
3731                 cfs_rq->h_nr_running--;
3732
3733                 /* Don't dequeue parent if it has other entities besides us */
3734                 if (cfs_rq->load.weight) {
3735                         /*
3736                          * Bias pick_next to pick a task from this cfs_rq, as
3737                          * p is sleeping when it is within its sched_slice.
3738                          */
3739                         if (task_sleep && parent_entity(se))
3740                                 set_next_buddy(parent_entity(se));
3741
3742                         /* avoid re-evaluating load for this entity */
3743                         se = parent_entity(se);
3744                         break;
3745                 }
3746                 flags |= DEQUEUE_SLEEP;
3747         }
3748
3749         for_each_sched_entity(se) {
3750                 cfs_rq = cfs_rq_of(se);
3751                 cfs_rq->h_nr_running--;
3752
3753                 if (cfs_rq_throttled(cfs_rq))
3754                         break;
3755
3756                 update_cfs_shares(cfs_rq);
3757                 update_entity_load_avg(se, 1);
3758         }
3759
3760         if (!se) {
3761                 dec_nr_running(rq);
3762                 update_rq_runnable_avg(rq, 1);
3763         }
3764         hrtick_update(rq);
3765 }
3766
3767 #ifdef CONFIG_SMP
3768 /* Used instead of source_load when we know the type == 0 */
3769 static unsigned long weighted_cpuload(const int cpu)
3770 {
3771         return cpu_rq(cpu)->cfs.runnable_load_avg;
3772 }
3773
3774 /*
3775  * Return a low guess at the load of a migration-source cpu weighted
3776  * according to the scheduling class and "nice" value.
3777  *
3778  * We want to under-estimate the load of migration sources, to
3779  * balance conservatively.
3780  */
3781 static unsigned long source_load(int cpu, int type)
3782 {
3783         struct rq *rq = cpu_rq(cpu);
3784         unsigned long total = weighted_cpuload(cpu);
3785
3786         if (type == 0 || !sched_feat(LB_BIAS))
3787                 return total;
3788
3789         return min(rq->cpu_load[type-1], total);
3790 }
3791
3792 /*
3793  * Return a high guess at the load of a migration-target cpu weighted
3794  * according to the scheduling class and "nice" value.
3795  */
3796 static unsigned long target_load(int cpu, int type)
3797 {
3798         struct rq *rq = cpu_rq(cpu);
3799         unsigned long total = weighted_cpuload(cpu);
3800
3801         if (type == 0 || !sched_feat(LB_BIAS))
3802                 return total;
3803
3804         return max(rq->cpu_load[type-1], total);
3805 }
3806
3807 static unsigned long power_of(int cpu)
3808 {
3809         return cpu_rq(cpu)->cpu_power;
3810 }
3811
3812 static unsigned long cpu_avg_load_per_task(int cpu)
3813 {
3814         struct rq *rq = cpu_rq(cpu);
3815         unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
3816         unsigned long load_avg = rq->cfs.runnable_load_avg;
3817
3818         if (nr_running)
3819                 return load_avg / nr_running;
3820
3821         return 0;
3822 }
3823
3824 static void record_wakee(struct task_struct *p)
3825 {
3826         /*
3827          * Rough decay (wiping) for cost saving, don't worry
3828          * about the boundary, really active task won't care
3829          * about the loss.
3830          */
3831         if (jiffies > current->wakee_flip_decay_ts + HZ) {
3832                 current->wakee_flips = 0;
3833                 current->wakee_flip_decay_ts = jiffies;
3834         }
3835
3836         if (current->last_wakee != p) {
3837                 current->last_wakee = p;
3838                 current->wakee_flips++;
3839         }
3840 }
3841
3842 static void task_waking_fair(struct task_struct *p)
3843 {
3844         struct sched_entity *se = &p->se;
3845         struct cfs_rq *cfs_rq = cfs_rq_of(se);
3846         u64 min_vruntime;
3847
3848 #ifndef CONFIG_64BIT
3849         u64 min_vruntime_copy;
3850
3851         do {
3852                 min_vruntime_copy = cfs_rq->min_vruntime_copy;
3853                 smp_rmb();
3854                 min_vruntime = cfs_rq->min_vruntime;
3855         } while (min_vruntime != min_vruntime_copy);
3856 #else
3857         min_vruntime = cfs_rq->min_vruntime;
3858 #endif
3859
3860         se->vruntime -= min_vruntime;
3861         record_wakee(p);
3862 }
3863
3864 #ifdef CONFIG_FAIR_GROUP_SCHED
3865 /*
3866  * effective_load() calculates the load change as seen from the root_task_group
3867  *
3868  * Adding load to a group doesn't make a group heavier, but can cause movement
3869  * of group shares between cpus. Assuming the shares were perfectly aligned one
3870  * can calculate the shift in shares.
3871  *
3872  * Calculate the effective load difference if @wl is added (subtracted) to @tg
3873  * on this @cpu and results in a total addition (subtraction) of @wg to the
3874  * total group weight.
3875  *
3876  * Given a runqueue weight distribution (rw_i) we can compute a shares
3877  * distribution (s_i) using:
3878  *
3879  *   s_i = rw_i / \Sum rw_j                                             (1)
3880  *
3881  * Suppose we have 4 CPUs and our @tg is a direct child of the root group and
3882  * has 7 equal weight tasks, distributed as below (rw_i), with the resulting
3883  * shares distribution (s_i):
3884  *
3885  *   rw_i = {   2,   4,   1,   0 }
3886  *   s_i  = { 2/7, 4/7, 1/7,   0 }
3887  *
3888  * As per wake_affine() we're interested in the load of two CPUs (the CPU the
3889  * task used to run on and the CPU the waker is running on), we need to
3890  * compute the effect of waking a task on either CPU and, in case of a sync
3891  * wakeup, compute the effect of the current task going to sleep.
3892  *
3893  * So for a change of @wl to the local @cpu with an overall group weight change
3894  * of @wl we can compute the new shares distribution (s'_i) using:
3895  *
3896  *   s'_i = (rw_i + @wl) / (@wg + \Sum rw_j)                            (2)
3897  *
3898  * Suppose we're interested in CPUs 0 and 1, and want to compute the load
3899  * differences in waking a task to CPU 0. The additional task changes the
3900  * weight and shares distributions like:
3901  *
3902  *   rw'_i = {   3,   4,   1,   0 }
3903  *   s'_i  = { 3/8, 4/8, 1/8,   0 }
3904  *
3905  * We can then compute the difference in effective weight by using:
3906  *
3907  *   dw_i = S * (s'_i - s_i)                                            (3)
3908  *
3909  * Where 'S' is the group weight as seen by its parent.
3910  *
3911  * Therefore the effective change in loads on CPU 0 would be 5/56 (3/8 - 2/7)
3912  * times the weight of the group. The effect on CPU 1 would be -4/56 (4/8 -
3913  * 4/7) times the weight of the group.
3914  */
3915 static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
3916 {
3917         struct sched_entity *se = tg->se[cpu];
3918
3919         if (!tg->parent || !wl) /* the trivial, non-cgroup case */
3920                 return wl;
3921
3922         for_each_sched_entity(se) {
3923                 long w, W;
3924
3925                 tg = se->my_q->tg;
3926
3927                 /*
3928                  * W = @wg + \Sum rw_j
3929                  */
3930                 W = wg + calc_tg_weight(tg, se->my_q);
3931
3932                 /*
3933                  * w = rw_i + @wl
3934                  */
3935                 w = se->my_q->load.weight + wl;
3936
3937                 /*
3938                  * wl = S * s'_i; see (2)
3939                  */
3940                 if (W > 0 && w < W)
3941                         wl = (w * tg->shares) / W;
3942                 else
3943                         wl = tg->shares;
3944
3945                 /*
3946                  * Per the above, wl is the new se->load.weight value; since
3947                  * those are clipped to [MIN_SHARES, ...) do so now. See
3948                  * calc_cfs_shares().
3949                  */
3950                 if (wl < MIN_SHARES)
3951                         wl = MIN_SHARES;
3952
3953                 /*
3954                  * wl = dw_i = S * (s'_i - s_i); see (3)
3955                  */
3956                 wl -= se->load.weight;
3957
3958                 /*
3959                  * Recursively apply this logic to all parent groups to compute
3960                  * the final effective load change on the root group. Since
3961                  * only the @tg group gets extra weight, all parent groups can
3962                  * only redistribute existing shares. @wl is the shift in shares
3963                  * resulting from this level per the above.
3964                  */
3965                 wg = 0;
3966         }
3967
3968         return wl;
3969 }
3970 #else
3971
3972 static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
3973 {
3974         return wl;
3975 }
3976
3977 #endif
3978
3979 static int wake_wide(struct task_struct *p)
3980 {
3981         int factor = this_cpu_read(sd_llc_size);
3982
3983         /*
3984          * Yeah, it's the switching-frequency, could means many wakee or
3985          * rapidly switch, use factor here will just help to automatically
3986          * adjust the loose-degree, so bigger node will lead to more pull.
3987          */
3988         if (p->wakee_flips > factor) {
3989                 /*
3990                  * wakee is somewhat hot, it needs certain amount of cpu
3991                  * resource, so if waker is far more hot, prefer to leave
3992                  * it alone.
3993                  */
3994                 if (current->wakee_flips > (factor * p->wakee_flips))
3995                         return 1;
3996         }
3997
3998         return 0;
3999 }
4000
4001 static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
4002 {
4003         s64 this_load, load;
4004         int idx, this_cpu, prev_cpu;
4005         unsigned long tl_per_task;
4006         struct task_group *tg;
4007         unsigned long weight;
4008         int balanced;
4009
4010         /*
4011          * If we wake multiple tasks be careful to not bounce
4012          * ourselves around too much.
4013          */
4014         if (wake_wide(p))
4015                 return 0;
4016
4017         idx       = sd->wake_idx;
4018         this_cpu  = smp_processor_id();
4019         prev_cpu  = task_cpu(p);
4020         load      = source_load(prev_cpu, idx);
4021         this_load = target_load(this_cpu, idx);
4022
4023         /*
4024          * If sync wakeup then subtract the (maximum possible)
4025          * effect of the currently running task from the load
4026          * of the current CPU:
4027          */
4028         if (sync) {
4029                 tg = task_group(current);
4030                 weight = current->se.load.weight;
4031
4032                 this_load += effective_load(tg, this_cpu, -weight, -weight);
4033                 load += effective_load(tg, prev_cpu, 0, -weight);
4034         }
4035
4036         tg = task_group(p);
4037         weight = p->se.load.weight;
4038
4039         /*
4040          * In low-load situations, where prev_cpu is idle and this_cpu is idle
4041          * due to the sync cause above having dropped this_load to 0, we'll
4042          * always have an imbalance, but there's really nothing you can do
4043          * about that, so that's good too.
4044          *
4045          * Otherwise check if either cpus are near enough in load to allow this
4046          * task to be woken on this_cpu.
4047          */
4048         if (this_load > 0) {
4049                 s64 this_eff_load, prev_eff_load;
4050
4051                 this_eff_load = 100;
4052                 this_eff_load *= power_of(prev_cpu);
4053                 this_eff_load *= this_load +
4054                         effective_load(tg, this_cpu, weight, weight);
4055
4056                 prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
4057                 prev_eff_load *= power_of(this_cpu);
4058                 prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
4059
4060                 balanced = this_eff_load <= prev_eff_load;
4061         } else
4062                 balanced = true;
4063
4064         /*
4065          * If the currently running task will sleep within
4066          * a reasonable amount of time then attract this newly
4067          * woken task:
4068          */
4069         if (sync && balanced)
4070                 return 1;
4071
4072         schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);
4073         tl_per_task = cpu_avg_load_per_task(this_cpu);
4074
4075         if (balanced ||
4076             (this_load <= load &&
4077              this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
4078                 /*
4079                  * This domain has SD_WAKE_AFFINE and
4080                  * p is cache cold in this domain, and
4081                  * there is no bad imbalance.
4082                  */
4083                 schedstat_inc(sd, ttwu_move_affine);
4084                 schedstat_inc(p, se.statistics.nr_wakeups_affine);
4085
4086                 return 1;
4087         }
4088         return 0;
4089 }
4090
4091 /*
4092  * find_idlest_group finds and returns the least busy CPU group within the
4093  * domain.
4094  */
4095 static struct sched_group *
4096 find_idlest_group(struct sched_domain *sd, struct task_struct *p,
4097                   int this_cpu, int load_idx)
4098 {
4099         struct sched_group *idlest = NULL, *group = sd->groups;
4100         unsigned long min_load = ULONG_MAX, this_load = 0;
4101         int imbalance = 100 + (sd->imbalance_pct-100)/2;
4102
4103         do {
4104                 unsigned long load, avg_load;
4105                 int local_group;
4106                 int i;
4107
4108                 /* Skip over this group if it has no CPUs allowed */
4109                 if (!cpumask_intersects(sched_group_cpus(group),
4110                                         tsk_cpus_allowed(p)))
4111                         continue;
4112
4113                 local_group = cpumask_test_cpu(this_cpu,
4114                                                sched_group_cpus(group));
4115
4116                 /* Tally up the load of all CPUs in the group */
4117                 avg_load = 0;
4118
4119                 for_each_cpu(i, sched_group_cpus(group)) {
4120                         /* Bias balancing toward cpus of our domain */
4121                         if (local_group)
4122                                 load = source_load(i, load_idx);
4123                         else
4124                                 load = target_load(i, load_idx);
4125
4126                         avg_load += load;
4127                 }
4128
4129                 /* Adjust by relative CPU power of the group */
4130                 avg_load = (avg_load * SCHED_POWER_SCALE) / group->sgp->power;
4131
4132                 if (local_group) {
4133                         this_load = avg_load;
4134                 } else if (avg_load < min_load) {
4135                         min_load = avg_load;
4136                         idlest = group;
4137                 }
4138         } while (group = group->next, group != sd->groups);
4139
4140         if (!idlest || 100*this_load < imbalance*min_load)
4141                 return NULL;
4142         return idlest;
4143 }
4144
4145 /*
4146  * find_idlest_cpu - find the idlest cpu among the cpus in group.
4147  */
4148 static int
4149 find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
4150 {
4151         unsigned long load, min_load = ULONG_MAX;
4152         int idlest = -1;
4153         int i;
4154
4155         /* Traverse only the allowed CPUs */
4156         for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) {
4157                 load = weighted_cpuload(i);
4158
4159                 if (load < min_load || (load == min_load && i == this_cpu)) {
4160                         min_load = load;
4161                         idlest = i;
4162                 }
4163         }
4164
4165         return idlest;
4166 }
4167
4168 /*
4169  * Try and locate an idle CPU in the sched_domain.
4170  */
4171 static int select_idle_sibling(struct task_struct *p, int target)
4172 {
4173         struct sched_domain *sd;
4174         struct sched_group *sg;
4175         int i = task_cpu(p);
4176
4177         if (idle_cpu(target))
4178                 return target;
4179
4180         /*
4181          * If the prevous cpu is cache affine and idle, don't be stupid.
4182          */
4183         if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
4184                 return i;
4185
4186         /*
4187          * Otherwise, iterate the domains and find an elegible idle cpu.
4188          */
4189         sd = rcu_dereference(per_cpu(sd_llc, target));
4190         for_each_lower_domain(sd) {
4191                 sg = sd->groups;
4192                 do {
4193                         if (!cpumask_intersects(sched_group_cpus(sg),
4194                                                 tsk_cpus_allowed(p)))
4195                                 goto next;
4196
4197                         for_each_cpu(i, sched_group_cpus(sg)) {
4198                                 if (i == target || !idle_cpu(i))
4199                                         goto next;
4200                         }
4201
4202                         target = cpumask_first_and(sched_group_cpus(sg),
4203                                         tsk_cpus_allowed(p));
4204                         goto done;
4205 next:
4206                         sg = sg->next;
4207                 } while (sg != sd->groups);
4208         }
4209 done:
4210         return target;
4211 }
4212
4213 /*
4214  * sched_balance_self: balance the current task (running on cpu) in domains
4215  * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
4216  * SD_BALANCE_EXEC.
4217  *
4218  * Balance, ie. select the least loaded group.
4219  *
4220  * Returns the target CPU number, or the same CPU if no balancing is needed.
4221  *
4222  * preempt must be disabled.
4223  */
4224 static int
4225 select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags)
4226 {
4227         struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
4228         int cpu = smp_processor_id();
4229         int new_cpu = cpu;
4230         int want_affine = 0;
4231         int sync = wake_flags & WF_SYNC;
4232
4233         if (p->nr_cpus_allowed == 1)
4234                 return prev_cpu;
4235
4236         if (sd_flag & SD_BALANCE_WAKE) {
4237                 if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
4238                         want_affine = 1;
4239                 new_cpu = prev_cpu;
4240         }
4241
4242         rcu_read_lock();
4243         for_each_domain(cpu, tmp) {
4244                 if (!(tmp->flags & SD_LOAD_BALANCE))
4245                         continue;
4246
4247                 /*
4248                  * If both cpu and prev_cpu are part of this domain,
4249                  * cpu is a valid SD_WAKE_AFFINE target.
4250                  */
4251                 if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
4252                     cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
4253                         affine_sd = tmp;
4254                         break;
4255                 }
4256
4257                 if (tmp->flags & sd_flag)
4258                         sd = tmp;
4259         }
4260
4261         if (affine_sd) {
4262                 if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
4263                         prev_cpu = cpu;
4264
4265                 new_cpu = select_idle_sibling(p, prev_cpu);
4266                 goto unlock;
4267         }
4268
4269         while (sd) {
4270                 int load_idx = sd->forkexec_idx;
4271                 struct sched_group *group;
4272                 int weight;
4273
4274                 if (!(sd->flags & sd_flag)) {
4275                         sd = sd->child;
4276                         continue;
4277                 }
4278
4279                 if (sd_flag & SD_BALANCE_WAKE)
4280                         load_idx = sd->wake_idx;
4281
4282                 group = find_idlest_group(sd, p, cpu, load_idx);
4283                 if (!group) {
4284                         sd = sd->child;
4285                         continue;
4286                 }
4287
4288                 new_cpu = find_idlest_cpu(group, p, cpu);
4289                 if (new_cpu == -1 || new_cpu == cpu) {
4290                         /* Now try balancing at a lower domain level of cpu */
4291                         sd = sd->child;
4292                         continue;
4293                 }
4294
4295                 /* Now try balancing at a lower domain level of new_cpu */
4296                 cpu = new_cpu;
4297                 weight = sd->span_weight;
4298                 sd = NULL;
4299                 for_each_domain(cpu, tmp) {
4300                         if (weight <= tmp->span_weight)
4301                                 break;
4302                         if (tmp->flags & sd_flag)
4303                                 sd = tmp;
4304                 }
4305                 /* while loop will break here if sd == NULL */
4306         }
4307 unlock:
4308         rcu_read_unlock();
4309
4310         return new_cpu;
4311 }
4312
4313 /*
4314  * Called immediately before a task is migrated to a new cpu; task_cpu(p) and
4315  * cfs_rq_of(p) references at time of call are still valid and identify the
4316  * previous cpu.  However, the caller only guarantees p->pi_lock is held; no
4317  * other assumptions, including the state of rq->lock, should be made.
4318  */
4319 static void
4320 migrate_task_rq_fair(struct task_struct *p, int next_cpu)
4321 {
4322         struct sched_entity *se = &p->se;
4323         struct cfs_rq *cfs_rq = cfs_rq_of(se);
4324
4325         /*
4326          * Load tracking: accumulate removed load so that it can be processed
4327          * when we next update owning cfs_rq under rq->lock.  Tasks contribute
4328          * to blocked load iff they have a positive decay-count.  It can never
4329          * be negative here since on-rq tasks have decay-count == 0.
4330          */
4331         if (se->avg.decay_count) {
4332                 se->avg.decay_count = -__synchronize_entity_decay(se);
4333                 atomic_long_add(se->avg.load_avg_contrib,
4334                                                 &cfs_rq->removed_load);
4335         }
4336 }
4337 #endif /* CONFIG_SMP */
4338
4339 static unsigned long
4340 wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
4341 {
4342         unsigned long gran = sysctl_sched_wakeup_granularity;
4343
4344         /*
4345          * Since its curr running now, convert the gran from real-time
4346          * to virtual-time in his units.
4347          *
4348          * By using 'se' instead of 'curr' we penalize light tasks, so
4349          * they get preempted easier. That is, if 'se' < 'curr' then
4350          * the resulting gran will be larger, therefore penalizing the
4351          * lighter, if otoh 'se' > 'curr' then the resulting gran will
4352          * be smaller, again penalizing the lighter task.
4353          *
4354          * This is especially important for buddies when the leftmost
4355          * task is higher priority than the buddy.
4356          */
4357         return calc_delta_fair(gran, se);
4358 }
4359
4360 /*
4361  * Should 'se' preempt 'curr'.
4362  *
4363  *             |s1
4364  *        |s2
4365  *   |s3
4366  *         g
4367  *      |<--->|c
4368  *
4369  *  w(c, s1) = -1
4370  *  w(c, s2) =  0
4371  *  w(c, s3) =  1
4372  *
4373  */
4374 static int
4375 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
4376 {
4377         s64 gran, vdiff = curr->vruntime - se->vruntime;
4378
4379         if (vdiff <= 0)
4380                 return -1;
4381
4382         gran = wakeup_gran(curr, se);
4383         if (vdiff > gran)
4384                 return 1;
4385
4386         return 0;
4387 }
4388
4389 static void set_last_buddy(struct sched_entity *se)
4390 {
4391         if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
4392                 return;
4393
4394         for_each_sched_entity(se)
4395                 cfs_rq_of(se)->last = se;
4396 }
4397
4398 static void set_next_buddy(struct sched_entity *se)
4399 {
4400         if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
4401                 return;
4402
4403         for_each_sched_entity(se)
4404                 cfs_rq_of(se)->next = se;
4405 }
4406
4407 static void set_skip_buddy(struct sched_entity *se)
4408 {
4409         for_each_sched_entity(se)
4410                 cfs_rq_of(se)->skip = se;
4411 }
4412
4413 /*
4414  * Preempt the current task with a newly woken task if needed:
4415  */
4416 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
4417 {
4418         struct task_struct *curr = rq->curr;
4419         struct sched_entity *se = &curr->se, *pse = &p->se;
4420         struct cfs_rq *cfs_rq = task_cfs_rq(curr);
4421         int scale = cfs_rq->nr_running >= sched_nr_latency;
4422         int next_buddy_marked = 0;
4423
4424         if (unlikely(se == pse))
4425                 return;
4426
4427         /*
4428          * This is possible from callers such as move_task(), in which we
4429          * unconditionally check_prempt_curr() after an enqueue (which may have
4430          * lead to a throttle).  This both saves work and prevents false
4431          * next-buddy nomination below.
4432          */
4433         if (unlikely(throttled_hierarchy(cfs_rq_of(pse))))
4434                 return;
4435
4436         if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {
4437                 set_next_buddy(pse);
4438                 next_buddy_marked = 1;
4439         }
4440
4441         /*
4442          * We can come here with TIF_NEED_RESCHED already set from new task
4443          * wake up path.
4444          *
4445          * Note: this also catches the edge-case of curr being in a throttled
4446          * group (e.g. via set_curr_task), since update_curr() (in the
4447          * enqueue of curr) will have resulted in resched being set.  This
4448          * prevents us from potentially nominating it as a false LAST_BUDDY
4449          * below.
4450          */
4451         if (test_tsk_need_resched(curr))
4452                 return;
4453
4454         /* Idle tasks are by definition preempted by non-idle tasks. */
4455         if (unlikely(curr->policy == SCHED_IDLE) &&
4456             likely(p->policy != SCHED_IDLE))
4457                 goto preempt;
4458
4459         /*
4460          * Batch and idle tasks do not preempt non-idle tasks (their preemption
4461          * is driven by the tick):
4462          */
4463         if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
4464                 return;
4465
4466         find_matching_se(&se, &pse);
4467         update_curr(cfs_rq_of(se));
4468         BUG_ON(!pse);
4469         if (wakeup_preempt_entity(se, pse) == 1) {
4470                 /*
4471                  * Bias pick_next to pick the sched entity that is
4472                  * triggering this preemption.
4473                  */
4474                 if (!next_buddy_marked)
4475                         set_next_buddy(pse);
4476                 goto preempt;
4477         }
4478
4479         return;
4480
4481 preempt:
4482         resched_task(curr);
4483         /*
4484          * Only set the backward buddy when the current task is still
4485          * on the rq. This can happen when a wakeup gets interleaved
4486          * with schedule on the ->pre_schedule() or idle_balance()
4487          * point, either of which can * drop the rq lock.
4488          *
4489          * Also, during early boot the idle thread is in the fair class,
4490          * for obvious reasons its a bad idea to schedule back to it.
4491          */
4492         if (unlikely(!se->on_rq || curr == rq->idle))
4493                 return;
4494
4495         if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
4496                 set_last_buddy(se);
4497 }
4498
4499 static struct task_struct *pick_next_task_fair(struct rq *rq)
4500 {
4501         struct task_struct *p;
4502         struct cfs_rq *cfs_rq = &rq->cfs;
4503         struct sched_entity *se;
4504
4505         if (!cfs_rq->nr_running)
4506                 return NULL;
4507
4508         do {
4509                 se = pick_next_entity(cfs_rq);
4510                 set_next_entity(cfs_rq, se);
4511                 cfs_rq = group_cfs_rq(se);
4512         } while (cfs_rq);
4513
4514         p = task_of(se);
4515         if (hrtick_enabled(rq))
4516                 hrtick_start_fair(rq, p);
4517
4518         return p;
4519 }
4520
4521 /*
4522  * Account for a descheduled task:
4523  */
4524 static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
4525 {
4526         struct sched_entity *se = &prev->se;
4527         struct cfs_rq *cfs_rq;
4528
4529         for_each_sched_entity(se) {
4530                 cfs_rq = cfs_rq_of(se);
4531                 put_prev_entity(cfs_rq, se);
4532         }
4533 }
4534
4535 /*
4536  * sched_yield() is very simple
4537  *
4538  * The magic of dealing with the ->skip buddy is in pick_next_entity.
4539  */
4540 static void yield_task_fair(struct rq *rq)
4541 {
4542         struct task_struct *curr = rq->curr;
4543         struct cfs_rq *cfs_rq = task_cfs_rq(curr);
4544         struct sched_entity *se = &curr->se;
4545
4546         /*
4547          * Are we the only task in the tree?
4548          */
4549         if (unlikely(rq->nr_running == 1))
4550                 return;
4551
4552         clear_buddies(cfs_rq, se);
4553
4554         if (curr->policy != SCHED_BATCH) {
4555                 update_rq_clock(rq);
4556                 /*
4557                  * Update run-time statistics of the 'current'.
4558                  */
4559                 update_curr(cfs_rq);
4560                 /*
4561                  * Tell update_rq_clock() that we've just updated,
4562                  * so we don't do microscopic update in schedule()
4563                  * and double the fastpath cost.
4564                  */
4565                  rq->skip_clock_update = 1;
4566         }
4567
4568         set_skip_buddy(se);
4569 }
4570
4571 static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preempt)
4572 {
4573         struct sched_entity *se = &p->se;
4574
4575         /* throttled hierarchies are not runnable */
4576         if (!se->on_rq || throttled_hierarchy(cfs_rq_of(se)))
4577                 return false;
4578
4579         /* Tell the scheduler that we'd really like pse to run next. */
4580         set_next_buddy(se);
4581
4582         yield_task_fair(rq);
4583
4584         return true;
4585 }
4586
4587 #ifdef CONFIG_SMP
4588 /**************************************************
4589  * Fair scheduling class load-balancing methods.
4590  *
4591  * BASICS
4592  *
4593  * The purpose of load-balancing is to achieve the same basic fairness the
4594  * per-cpu scheduler provides, namely provide a proportional amount of compute
4595  * time to each task. This is expressed in the following equation:
4596  *
4597  *   W_i,n/P_i == W_j,n/P_j for all i,j                               (1)
4598  *
4599  * Where W_i,n is the n-th weight average for cpu i. The instantaneous weight
4600  * W_i,0 is defined as:
4601  *
4602  *   W_i,0 = \Sum_j w_i,j                                             (2)
4603  *
4604  * Where w_i,j is the weight of the j-th runnable task on cpu i. This weight
4605  * is derived from the nice value as per prio_to_weight[].
4606  *
4607  * The weight average is an exponential decay average of the instantaneous
4608  * weight:
4609  *
4610  *   W'_i,n = (2^n - 1) / 2^n * W_i,n + 1 / 2^n * W_i,0               (3)
4611  *
4612  * P_i is the cpu power (or compute capacity) of cpu i, typically it is the
4613  * fraction of 'recent' time available for SCHED_OTHER task execution. But it
4614  * can also include other factors [XXX].
4615  *
4616  * To achieve this balance we define a measure of imbalance which follows
4617  * directly from (1):
4618  *
4619  *   imb_i,j = max{ avg(W/P), W_i/P_i } - min{ avg(W/P), W_j/P_j }    (4)
4620  *
4621  * We them move tasks around to minimize the imbalance. In the continuous
4622  * function space it is obvious this converges, in the discrete case we get
4623  * a few fun cases generally called infeasible weight scenarios.
4624  *
4625  * [XXX expand on:
4626  *     - infeasible weights;
4627  *     - local vs global optima in the discrete case. ]
4628  *
4629  *
4630  * SCHED DOMAINS
4631  *
4632  * In order to solve the imbalance equation (4), and avoid the obvious O(n^2)
4633  * for all i,j solution, we create a tree of cpus that follows the hardware
4634  * topology where each level pairs two lower groups (or better). This results
4635  * in O(log n) layers. Furthermore we reduce the number of cpus going up the
4636  * tree to only the first of the previous level and we decrease the frequency
4637  * of load-balance at each level inv. proportional to the number of cpus in
4638  * the groups.
4639  *
4640  * This yields:
4641  *
4642  *     log_2 n     1     n
4643  *   \Sum       { --- * --- * 2^i } = O(n)                            (5)
4644  *     i = 0      2^i   2^i
4645  *                               `- size of each group
4646  *         |         |     `- number of cpus doing load-balance
4647  *         |         `- freq
4648  *         `- sum over all levels
4649  *
4650  * Coupled with a limit on how many tasks we can migrate every balance pass,
4651  * this makes (5) the runtime complexity of the balancer.
4652  *
4653  * An important property here is that each CPU is still (indirectly) connected
4654  * to every other cpu in at most O(log n) steps:
4655  *
4656  * The adjacency matrix of the resulting graph is given by:
4657  *
4658  *             log_2 n     
4659  *   A_i,j = \Union     (i % 2^k == 0) && i / 2^(k+1) == j / 2^(k+1)  (6)
4660  *             k = 0
4661  *
4662  * And you'll find that:
4663  *
4664  *   A^(log_2 n)_i,j != 0  for all i,j                                (7)
4665  *
4666  * Showing there's indeed a path between every cpu in at most O(log n) steps.
4667  * The task movement gives a factor of O(m), giving a convergence complexity
4668  * of:
4669  *
4670  *   O(nm log n),  n := nr_cpus, m := nr_tasks                        (8)
4671  *
4672  *
4673  * WORK CONSERVING
4674  *
4675  * In order to avoid CPUs going idle while there's still work to do, new idle
4676  * balancing is more aggressive and has the newly idle cpu iterate up the domain
4677  * tree itself instead of relying on other CPUs to bring it work.
4678  *
4679  * This adds some complexity to both (5) and (8) but it reduces the total idle
4680  * time.
4681  *
4682  * [XXX more?]
4683  *
4684  *
4685  * CGROUPS
4686  *
4687  * Cgroups make a horror show out of (2), instead of a simple sum we get:
4688  *
4689  *                                s_k,i
4690  *   W_i,0 = \Sum_j \Prod_k w_k * -----                               (9)
4691  *                                 S_k
4692  *
4693  * Where
4694  *
4695  *   s_k,i = \Sum_j w_i,j,k  and  S_k = \Sum_i s_k,i                 (10)
4696  *
4697  * w_i,j,k is the weight of the j-th runnable task in the k-th cgroup on cpu i.
4698  *
4699  * The big problem is S_k, its a global sum needed to compute a local (W_i)
4700  * property.
4701  *
4702  * [XXX write more on how we solve this.. _after_ merging pjt's patches that
4703  *      rewrite all of this once again.]
4704  */ 
4705
4706 static unsigned long __read_mostly max_load_balance_interval = HZ/10;
4707
4708 enum fbq_type { regular, remote, all };
4709
4710 #define LBF_ALL_PINNED  0x01
4711 #define LBF_NEED_BREAK  0x02
4712 #define LBF_DST_PINNED  0x04
4713 #define LBF_SOME_PINNED 0x08
4714
4715 struct lb_env {
4716         struct sched_domain     *sd;
4717
4718         struct rq               *src_rq;
4719         int                     src_cpu;
4720
4721         int                     dst_cpu;
4722         struct rq               *dst_rq;
4723
4724         struct cpumask          *dst_grpmask;
4725         int                     new_dst_cpu;
4726         enum cpu_idle_type      idle;
4727         long                    imbalance;
4728         /* The set of CPUs under consideration for load-balancing */
4729         struct cpumask          *cpus;
4730
4731         unsigned int            flags;
4732
4733         unsigned int            loop;
4734         unsigned int            loop_break;
4735         unsigned int            loop_max;
4736
4737         enum fbq_type           fbq_type;
4738 };
4739
4740 /*
4741  * move_task - move a task from one runqueue to another runqueue.
4742  * Both runqueues must be locked.
4743  */
4744 static void move_task(struct task_struct *p, struct lb_env *env)
4745 {
4746         deactivate_task(env->src_rq, p, 0);
4747         set_task_cpu(p, env->dst_cpu);
4748         activate_task(env->dst_rq, p, 0);
4749         check_preempt_curr(env->dst_rq, p, 0);
4750 }
4751
4752 /*
4753  * Is this task likely cache-hot:
4754  */
4755 static int
4756 task_hot(struct task_struct *p, u64 now, struct sched_domain *sd)
4757 {
4758         s64 delta;
4759
4760         if (p->sched_class != &fair_sched_class)
4761                 return 0;
4762
4763         if (unlikely(p->policy == SCHED_IDLE))
4764                 return 0;
4765
4766         /*
4767          * Buddy candidates are cache hot:
4768          */
4769         if (sched_feat(CACHE_HOT_BUDDY) && this_rq()->nr_running &&
4770                         (&p->se == cfs_rq_of(&p->se)->next ||
4771                          &p->se == cfs_rq_of(&p->se)->last))
4772                 return 1;
4773
4774         if (sysctl_sched_migration_cost == -1)
4775                 return 1;
4776         if (sysctl_sched_migration_cost == 0)
4777                 return 0;
4778
4779         delta = now - p->se.exec_start;
4780
4781         return delta < (s64)sysctl_sched_migration_cost;
4782 }
4783
4784 #ifdef CONFIG_NUMA_BALANCING
4785 /* Returns true if the destination node has incurred more faults */
4786 static bool migrate_improves_locality(struct task_struct *p, struct lb_env *env)
4787 {
4788         int src_nid, dst_nid;
4789
4790         if (!sched_feat(NUMA_FAVOUR_HIGHER) || !p->numa_faults ||
4791             !(env->sd->flags & SD_NUMA)) {
4792                 return false;
4793         }
4794
4795         src_nid = cpu_to_node(env->src_cpu);
4796         dst_nid = cpu_to_node(env->dst_cpu);
4797
4798         if (src_nid == dst_nid)
4799                 return false;
4800
4801         /* Always encourage migration to the preferred node. */
4802         if (dst_nid == p->numa_preferred_nid)
4803                 return true;
4804
4805         /* If both task and group weight improve, this move is a winner. */
4806         if (task_weight(p, dst_nid) > task_weight(p, src_nid) &&
4807             group_weight(p, dst_nid) > group_weight(p, src_nid))
4808                 return true;
4809
4810         return false;
4811 }
4812
4813
4814 static bool migrate_degrades_locality(struct task_struct *p, struct lb_env *env)
4815 {
4816         int src_nid, dst_nid;
4817
4818         if (!sched_feat(NUMA) || !sched_feat(NUMA_RESIST_LOWER))
4819                 return false;
4820
4821         if (!p->numa_faults || !(env->sd->flags & SD_NUMA))
4822                 return false;
4823
4824         src_nid = cpu_to_node(env->src_cpu);
4825         dst_nid = cpu_to_node(env->dst_cpu);
4826
4827         if (src_nid == dst_nid)
4828                 return false;
4829
4830         /* Migrating away from the preferred node is always bad. */
4831         if (src_nid == p->numa_preferred_nid)
4832                 return true;
4833
4834         /* If either task or group weight get worse, don't do it. */
4835         if (task_weight(p, dst_nid) < task_weight(p, src_nid) ||
4836             group_weight(p, dst_nid) < group_weight(p, src_nid))
4837                 return true;
4838
4839         return false;
4840 }
4841
4842 #else
4843 static inline bool migrate_improves_locality(struct task_struct *p,
4844                                              struct lb_env *env)
4845 {
4846         return false;
4847 }
4848
4849 static inline bool migrate_degrades_locality(struct task_struct *p,
4850                                              struct lb_env *env)
4851 {
4852         return false;
4853 }
4854 #endif
4855
4856 /*
4857  * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
4858  */
4859 static
4860 int can_migrate_task(struct task_struct *p, struct lb_env *env)
4861 {
4862         int tsk_cache_hot = 0;
4863         /*
4864          * We do not migrate tasks that are:
4865          * 1) throttled_lb_pair, or
4866          * 2) cannot be migrated to this CPU due to cpus_allowed, or
4867          * 3) running (obviously), or
4868          * 4) are cache-hot on their current CPU.
4869          */
4870         if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
4871                 return 0;
4872
4873         if (!cpumask_test_cpu(env->dst_cpu, tsk_cpus_allowed(p))) {
4874                 int cpu;
4875
4876                 schedstat_inc(p, se.statistics.nr_failed_migrations_affine);
4877
4878                 env->flags |= LBF_SOME_PINNED;
4879
4880                 /*
4881                  * Remember if this task can be migrated to any other cpu in
4882                  * our sched_group. We may want to revisit it if we couldn't
4883                  * meet load balance goals by pulling other tasks on src_cpu.
4884                  *
4885                  * Also avoid computing new_dst_cpu if we have already computed
4886                  * one in current iteration.
4887                  */
4888                 if (!env->dst_grpmask || (env->flags & LBF_DST_PINNED))
4889                         return 0;
4890
4891                 /* Prevent to re-select dst_cpu via env's cpus */
4892                 for_each_cpu_and(cpu, env->dst_grpmask, env->cpus) {
4893                         if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) {
4894                                 env->flags |= LBF_DST_PINNED;
4895                                 env->new_dst_cpu = cpu;
4896                                 break;
4897                         }
4898                 }
4899
4900                 return 0;
4901         }
4902
4903         /* Record that we found atleast one task that could run on dst_cpu */
4904         env->flags &= ~LBF_ALL_PINNED;
4905
4906         if (task_running(env->src_rq, p)) {
4907                 schedstat_inc(p, se.statistics.nr_failed_migrations_running);
4908                 return 0;
4909         }
4910
4911         /*
4912          * Aggressive migration if:
4913          * 1) destination numa is preferred
4914          * 2) task is cache cold, or
4915          * 3) too many balance attempts have failed.
4916          */
4917         tsk_cache_hot = task_hot(p, rq_clock_task(env->src_rq), env->sd);
4918         if (!tsk_cache_hot)
4919                 tsk_cache_hot = migrate_degrades_locality(p, env);
4920
4921         if (migrate_improves_locality(p, env)) {
4922 #ifdef CONFIG_SCHEDSTATS
4923                 if (tsk_cache_hot) {
4924                         schedstat_inc(env->sd, lb_hot_gained[env->idle]);
4925                         schedstat_inc(p, se.statistics.nr_forced_migrations);
4926                 }
4927 #endif
4928                 return 1;
4929         }
4930
4931         if (!tsk_cache_hot ||
4932                 env->sd->nr_balance_failed > env->sd->cache_nice_tries) {
4933
4934                 if (tsk_cache_hot) {
4935                         schedstat_inc(env->sd, lb_hot_gained[env->idle]);
4936                         schedstat_inc(p, se.statistics.nr_forced_migrations);
4937                 }
4938
4939                 return 1;
4940         }
4941
4942         schedstat_inc(p, se.statistics.nr_failed_migrations_hot);
4943         return 0;
4944 }
4945
4946 /*
4947  * move_one_task tries to move exactly one task from busiest to this_rq, as
4948  * part of active balancing operations within "domain".
4949  * Returns 1 if successful and 0 otherwise.
4950  *
4951  * Called with both runqueues locked.
4952  */
4953 static int move_one_task(struct lb_env *env)
4954 {
4955         struct task_struct *p, *n;
4956
4957         list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) {
4958                 if (!can_migrate_task(p, env))
4959                         continue;
4960
4961                 move_task(p, env);
4962                 /*
4963                  * Right now, this is only the second place move_task()
4964                  * is called, so we can safely collect move_task()
4965                  * stats here rather than inside move_task().
4966                  */
4967                 schedstat_inc(env->sd, lb_gained[env->idle]);
4968                 return 1;
4969         }
4970         return 0;
4971 }
4972
4973 static const unsigned int sched_nr_migrate_break = 32;
4974
4975 /*
4976  * move_tasks tries to move up to imbalance weighted load from busiest to
4977  * this_rq, as part of a balancing operation within domain "sd".
4978  * Returns 1 if successful and 0 otherwise.
4979  *
4980  * Called with both runqueues locked.
4981  */
4982 static int move_tasks(struct lb_env *env)
4983 {
4984         struct list_head *tasks = &env->src_rq->cfs_tasks;
4985         struct task_struct *p;
4986         unsigned long load;
4987         int pulled = 0;
4988
4989         if (env->imbalance <= 0)
4990                 return 0;
4991
4992         while (!list_empty(tasks)) {
4993                 p = list_first_entry(tasks, struct task_struct, se.group_node);
4994
4995                 env->loop++;
4996                 /* We've more or less seen every task there is, call it quits */
4997                 if (env->loop > env->loop_max)
4998                         break;
4999
5000                 /* take a breather every nr_migrate tasks */
5001                 if (env->loop > env->loop_break) {
5002                         env->loop_break += sched_nr_migrate_break;
5003                         env->flags |= LBF_NEED_BREAK;
5004                         break;
5005                 }
5006
5007                 if (!can_migrate_task(p, env))
5008                         goto next;
5009
5010                 load = task_h_load(p);
5011
5012                 if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
5013                         goto next;
5014
5015                 if ((load / 2) > env->imbalance)
5016                         goto next;
5017
5018                 move_task(p, env);
5019                 pulled++;
5020                 env->imbalance -= load;
5021
5022 #ifdef CONFIG_PREEMPT
5023                 /*
5024                  * NEWIDLE balancing is a source of latency, so preemptible
5025                  * kernels will stop after the first task is pulled to minimize
5026                  * the critical section.
5027                  */
5028                 if (env->idle == CPU_NEWLY_IDLE)
5029                         break;
5030 #endif
5031
5032                 /*
5033                  * We only want to steal up to the prescribed amount of
5034                  * weighted load.
5035                  */
5036                 if (env->imbalance <= 0)
5037                         break;
5038
5039                 continue;
5040 next:
5041                 list_move_tail(&p->se.group_node, tasks);
5042         }
5043
5044         /*
5045          * Right now, this is one of only two places move_task() is called,
5046          * so we can safely collect move_task() stats here rather than
5047          * inside move_task().
5048          */
5049         schedstat_add(env->sd, lb_gained[env->idle], pulled);
5050
5051         return pulled;
5052 }
5053
5054 #ifdef CONFIG_FAIR_GROUP_SCHED
5055 /*
5056  * update tg->load_weight by folding this cpu's load_avg
5057  */
5058 static void __update_blocked_averages_cpu(struct task_group *tg, int cpu)
5059 {
5060         struct sched_entity *se = tg->se[cpu];
5061         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu];
5062
5063         /* throttled entities do not contribute to load */
5064         if (throttled_hierarchy(cfs_rq))
5065                 return;
5066
5067         update_cfs_rq_blocked_load(cfs_rq, 1);
5068
5069         if (se) {
5070                 update_entity_load_avg(se, 1);
5071                 /*
5072                  * We pivot on our runnable average having decayed to zero for
5073                  * list removal.  This generally implies that all our children
5074                  * have also been removed (modulo rounding error or bandwidth
5075                  * control); however, such cases are rare and we can fix these
5076                  * at enqueue.
5077                  *
5078                  * TODO: fix up out-of-order children on enqueue.
5079                  */
5080                 if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running)
5081                         list_del_leaf_cfs_rq(cfs_rq);
5082         } else {
5083                 struct rq *rq = rq_of(cfs_rq);
5084                 update_rq_runnable_avg(rq, rq->nr_running);
5085         }
5086 }
5087
5088 static void update_blocked_averages(int cpu)
5089 {
5090         struct rq *rq = cpu_rq(cpu);
5091         struct cfs_rq *cfs_rq;
5092         unsigned long flags;
5093
5094         raw_spin_lock_irqsave(&rq->lock, flags);
5095         update_rq_clock(rq);
5096         /*
5097          * Iterates the task_group tree in a bottom up fashion, see
5098          * list_add_leaf_cfs_rq() for details.
5099          */
5100         for_each_leaf_cfs_rq(rq, cfs_rq) {
5101                 /*
5102                  * Note: We may want to consider periodically releasing
5103                  * rq->lock about these updates so that creating many task
5104                  * groups does not result in continually extending hold time.
5105                  */
5106                 __update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
5107         }
5108
5109         raw_spin_unlock_irqrestore(&rq->lock, flags);
5110 }
5111
5112 /*
5113  * Compute the hierarchical load factor for cfs_rq and all its ascendants.
5114  * This needs to be done in a top-down fashion because the load of a child
5115  * group is a fraction of its parents load.
5116  */
5117 static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
5118 {
5119         struct rq *rq = rq_of(cfs_rq);
5120         struct sched_entity *se = cfs_rq->tg->se[cpu_of(rq)];
5121         unsigned long now = jiffies;
5122         unsigned long load;
5123
5124         if (cfs_rq->last_h_load_update == now)
5125                 return;
5126
5127         cfs_rq->h_load_next = NULL;
5128         for_each_sched_entity(se) {
5129                 cfs_rq = cfs_rq_of(se);
5130                 cfs_rq->h_load_next = se;
5131                 if (cfs_rq->last_h_load_update == now)
5132                         break;
5133         }
5134
5135         if (!se) {
5136                 cfs_rq->h_load = cfs_rq->runnable_load_avg;
5137                 cfs_rq->last_h_load_update = now;
5138         }
5139
5140         while ((se = cfs_rq->h_load_next) != NULL) {
5141                 load = cfs_rq->h_load;
5142                 load = div64_ul(load * se->avg.load_avg_contrib,
5143                                 cfs_rq->runnable_load_avg + 1);
5144                 cfs_rq = group_cfs_rq(se);
5145                 cfs_rq->h_load = load;
5146                 cfs_rq->last_h_load_update = now;
5147         }
5148 }
5149
5150 static unsigned long task_h_load(struct task_struct *p)
5151 {
5152         struct cfs_rq *cfs_rq = task_cfs_rq(p);
5153
5154         update_cfs_rq_h_load(cfs_rq);
5155         return div64_ul(p->se.avg.load_avg_contrib * cfs_rq->h_load,
5156                         cfs_rq->runnable_load_avg + 1);
5157 }
5158 #else
5159 static inline void update_blocked_averages(int cpu)
5160 {
5161 }
5162
5163 static unsigned long task_h_load(struct task_struct *p)
5164 {
5165         return p->se.avg.load_avg_contrib;
5166 }
5167 #endif
5168
5169 /********** Helpers for find_busiest_group ************************/
5170 /*
5171  * sg_lb_stats - stats of a sched_group required for load_balancing
5172  */
5173 struct sg_lb_stats {
5174         unsigned long avg_load; /*Avg load across the CPUs of the group */
5175         unsigned long group_load; /* Total load over the CPUs of the group */
5176         unsigned long sum_weighted_load; /* Weighted load of group's tasks */
5177         unsigned long load_per_task;
5178         unsigned long group_power;
5179         unsigned int sum_nr_running; /* Nr tasks running in the group */
5180         unsigned int group_capacity;
5181         unsigned int idle_cpus;
5182         unsigned int group_weight;
5183         int group_imb; /* Is there an imbalance in the group ? */
5184         int group_has_capacity; /* Is there extra capacity in the group? */
5185 #ifdef CONFIG_NUMA_BALANCING
5186         unsigned int nr_numa_running;
5187         unsigned int nr_preferred_running;
5188 #endif
5189 };
5190
5191 /*
5192  * sd_lb_stats - Structure to store the statistics of a sched_domain
5193  *               during load balancing.
5194  */
5195 struct sd_lb_stats {
5196         struct sched_group *busiest;    /* Busiest group in this sd */
5197         struct sched_group *local;      /* Local group in this sd */
5198         unsigned long total_load;       /* Total load of all groups in sd */
5199         unsigned long total_pwr;        /* Total power of all groups in sd */
5200         unsigned long avg_load; /* Average load across all groups in sd */
5201
5202         struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */
5203         struct sg_lb_stats local_stat;  /* Statistics of the local group */
5204 };
5205
5206 static inline void init_sd_lb_stats(struct sd_lb_stats *sds)
5207 {
5208         /*
5209          * Skimp on the clearing to avoid duplicate work. We can avoid clearing
5210          * local_stat because update_sg_lb_stats() does a full clear/assignment.
5211          * We must however clear busiest_stat::avg_load because
5212          * update_sd_pick_busiest() reads this before assignment.
5213          */
5214         *sds = (struct sd_lb_stats){
5215                 .busiest = NULL,
5216                 .local = NULL,
5217                 .total_load = 0UL,
5218                 .total_pwr = 0UL,
5219                 .busiest_stat = {
5220                         .avg_load = 0UL,
5221                 },
5222         };
5223 }
5224
5225 /**
5226  * get_sd_load_idx - Obtain the load index for a given sched domain.
5227  * @sd: The sched_domain whose load_idx is to be obtained.
5228  * @idle: The idle status of the CPU for whose sd load_idx is obtained.
5229  *
5230  * Return: The load index.
5231  */
5232 static inline int get_sd_load_idx(struct sched_domain *sd,
5233                                         enum cpu_idle_type idle)
5234 {
5235         int load_idx;
5236
5237         switch (idle) {
5238         case CPU_NOT_IDLE:
5239                 load_idx = sd->busy_idx;
5240                 break;
5241
5242         case CPU_NEWLY_IDLE:
5243                 load_idx = sd->newidle_idx;
5244                 break;
5245         default:
5246                 load_idx = sd->idle_idx;
5247                 break;
5248         }
5249
5250         return load_idx;
5251 }
5252
5253 static unsigned long default_scale_freq_power(struct sched_domain *sd, int cpu)
5254 {
5255         return SCHED_POWER_SCALE;
5256 }
5257
5258 unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu)
5259 {
5260         return default_scale_freq_power(sd, cpu);
5261 }
5262
5263 static unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu)
5264 {
5265         unsigned long weight = sd->span_weight;
5266         unsigned long smt_gain = sd->smt_gain;
5267
5268         smt_gain /= weight;
5269
5270         return smt_gain;
5271 }
5272
5273 unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu)
5274 {
5275         return default_scale_smt_power(sd, cpu);
5276 }
5277
5278 static unsigned long scale_rt_power(int cpu)
5279 {
5280         struct rq *rq = cpu_rq(cpu);
5281         u64 total, available, age_stamp, avg;
5282
5283         /*
5284          * Since we're reading these variables without serialization make sure
5285          * we read them once before doing sanity checks on them.
5286          */
5287         age_stamp = ACCESS_ONCE(rq->age_stamp);
5288         avg = ACCESS_ONCE(rq->rt_avg);
5289
5290         total = sched_avg_period() + (rq_clock(rq) - age_stamp);
5291
5292         if (unlikely(total < avg)) {
5293                 /* Ensures that power won't end up being negative */
5294                 available = 0;
5295         } else {
5296                 available = total - avg;
5297         }
5298
5299         if (unlikely((s64)total < SCHED_POWER_SCALE))
5300                 total = SCHED_POWER_SCALE;
5301
5302         total >>= SCHED_POWER_SHIFT;
5303
5304         return div_u64(available, total);
5305 }
5306
5307 static void update_cpu_power(struct sched_domain *sd, int cpu)
5308 {
5309         unsigned long weight = sd->span_weight;
5310         unsigned long power = SCHED_POWER_SCALE;
5311         struct sched_group *sdg = sd->groups;
5312
5313         if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) {
5314                 if (sched_feat(ARCH_POWER))
5315                         power *= arch_scale_smt_power(sd, cpu);
5316                 else
5317                         power *= default_scale_smt_power(sd, cpu);
5318
5319                 power >>= SCHED_POWER_SHIFT;
5320         }
5321
5322         sdg->sgp->power_orig = power;
5323
5324         if (sched_feat(ARCH_POWER))
5325                 power *= arch_scale_freq_power(sd, cpu);
5326         else
5327                 power *= default_scale_freq_power(sd, cpu);
5328
5329         power >>= SCHED_POWER_SHIFT;
5330
5331         power *= scale_rt_power(cpu);
5332         power >>= SCHED_POWER_SHIFT;
5333
5334         if (!power)
5335                 power = 1;
5336
5337         cpu_rq(cpu)->cpu_power = power;
5338         sdg->sgp->power = power;
5339 }
5340
5341 void update_group_power(struct sched_domain *sd, int cpu)
5342 {
5343         struct sched_domain *child = sd->child;
5344         struct sched_group *group, *sdg = sd->groups;
5345         unsigned long power, power_orig;
5346         unsigned long interval;
5347
5348         interval = msecs_to_jiffies(sd->balance_interval);
5349         interval = clamp(interval, 1UL, max_load_balance_interval);
5350         sdg->sgp->next_update = jiffies + interval;
5351
5352         if (!child) {
5353                 update_cpu_power(sd, cpu);
5354                 return;
5355         }
5356
5357         power_orig = power = 0;
5358
5359         if (child->flags & SD_OVERLAP) {
5360                 /*
5361                  * SD_OVERLAP domains cannot assume that child groups
5362                  * span the current group.
5363                  */
5364
5365                 for_each_cpu(cpu, sched_group_cpus(sdg)) {
5366                         struct sched_group_power *sgp;
5367                         struct rq *rq = cpu_rq(cpu);
5368
5369                         /*
5370                          * build_sched_domains() -> init_sched_groups_power()
5371                          * gets here before we've attached the domains to the
5372                          * runqueues.
5373                          *
5374                          * Use power_of(), which is set irrespective of domains
5375                          * in update_cpu_power().
5376                          *
5377                          * This avoids power/power_orig from being 0 and
5378                          * causing divide-by-zero issues on boot.
5379                          *
5380                          * Runtime updates will correct power_orig.
5381                          */
5382                         if (unlikely(!rq->sd)) {
5383                                 power_orig += power_of(cpu);
5384                                 power += power_of(cpu);
5385                                 continue;
5386                         }
5387
5388                         sgp = rq->sd->groups->sgp;
5389                         power_orig += sgp->power_orig;
5390                         power += sgp->power;
5391                 }
5392         } else  {
5393                 /*
5394                  * !SD_OVERLAP domains can assume that child groups
5395                  * span the current group.
5396                  */ 
5397
5398                 group = child->groups;
5399                 do {
5400                         power_orig += group->sgp->power_orig;
5401                         power += group->sgp->power;
5402                         group = group->next;
5403                 } while (group != child->groups);
5404         }
5405
5406         sdg->sgp->power_orig = power_orig;
5407         sdg->sgp->power = power;
5408 }
5409
5410 /*
5411  * Try and fix up capacity for tiny siblings, this is needed when
5412  * things like SD_ASYM_PACKING need f_b_g to select another sibling
5413  * which on its own isn't powerful enough.
5414  *
5415  * See update_sd_pick_busiest() and check_asym_packing().
5416  */
5417 static inline int
5418 fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
5419 {
5420         /*
5421          * Only siblings can have significantly less than SCHED_POWER_SCALE
5422          */
5423         if (!(sd->flags & SD_SHARE_CPUPOWER))
5424                 return 0;
5425
5426         /*
5427          * If ~90% of the cpu_power is still there, we're good.
5428          */
5429         if (group->sgp->power * 32 > group->sgp->power_orig * 29)
5430                 return 1;
5431
5432         return 0;
5433 }
5434
5435 /*
5436  * Group imbalance indicates (and tries to solve) the problem where balancing
5437  * groups is inadequate due to tsk_cpus_allowed() constraints.
5438  *
5439  * Imagine a situation of two groups of 4 cpus each and 4 tasks each with a
5440  * cpumask covering 1 cpu of the first group and 3 cpus of the second group.
5441  * Something like:
5442  *
5443  *      { 0 1 2 3 } { 4 5 6 7 }
5444  *              *     * * *
5445  *
5446  * If we were to balance group-wise we'd place two tasks in the first group and
5447  * two tasks in the second group. Clearly this is undesired as it will overload
5448  * cpu 3 and leave one of the cpus in the second group unused.
5449  *
5450  * The current solution to this issue is detecting the skew in the first group
5451  * by noticing the lower domain failed to reach balance and had difficulty
5452  * moving tasks due to affinity constraints.
5453  *
5454  * When this is so detected; this group becomes a candidate for busiest; see
5455  * update_sd_pick_busiest(). And calculate_imbalance() and
5456  * find_busiest_group() avoid some of the usual balance conditions to allow it
5457  * to create an effective group imbalance.
5458  *
5459  * This is a somewhat tricky proposition since the next run might not find the
5460  * group imbalance and decide the groups need to be balanced again. A most
5461  * subtle and fragile situation.
5462  */
5463
5464 static inline int sg_imbalanced(struct sched_group *group)
5465 {
5466         return group->sgp->imbalance;
5467 }
5468
5469 /*
5470  * Compute the group capacity.
5471  *
5472  * Avoid the issue where N*frac(smt_power) >= 1 creates 'phantom' cores by
5473  * first dividing out the smt factor and computing the actual number of cores
5474  * and limit power unit capacity with that.
5475  */
5476 static inline int sg_capacity(struct lb_env *env, struct sched_group *group)
5477 {
5478         unsigned int capacity, smt, cpus;
5479         unsigned int power, power_orig;
5480
5481         power = group->sgp->power;
5482         power_orig = group->sgp->power_orig;
5483         cpus = group->group_weight;
5484
5485         /* smt := ceil(cpus / power), assumes: 1 < smt_power < 2 */
5486         smt = DIV_ROUND_UP(SCHED_POWER_SCALE * cpus, power_orig);
5487         capacity = cpus / smt; /* cores */
5488
5489         capacity = min_t(unsigned, capacity, DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE));
5490         if (!capacity)
5491                 capacity = fix_small_capacity(env->sd, group);
5492
5493         return capacity;
5494 }
5495
5496 /**
5497  * update_sg_lb_stats - Update sched_group's statistics for load balancing.
5498  * @env: The load balancing environment.
5499  * @group: sched_group whose statistics are to be updated.
5500  * @load_idx: Load index of sched_domain of this_cpu for load calc.
5501  * @local_group: Does group contain this_cpu.
5502  * @sgs: variable to hold the statistics for this group.
5503  */
5504 static inline void update_sg_lb_stats(struct lb_env *env,
5505                         struct sched_group *group, int load_idx,
5506                         int local_group, struct sg_lb_stats *sgs)
5507 {
5508         unsigned long nr_running;
5509         unsigned long load;
5510         int i;
5511
5512         memset(sgs, 0, sizeof(*sgs));
5513
5514         for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
5515                 struct rq *rq = cpu_rq(i);
5516
5517                 nr_running = rq->nr_running;
5518
5519                 /* Bias balancing toward cpus of our domain */
5520                 if (local_group)
5521                         load = target_load(i, load_idx);
5522                 else
5523                         load = source_load(i, load_idx);
5524
5525                 sgs->group_load += load;
5526                 sgs->sum_nr_running += nr_running;
5527 #ifdef CONFIG_NUMA_BALANCING
5528                 sgs->nr_numa_running += rq->nr_numa_running;
5529                 sgs->nr_preferred_running += rq->nr_preferred_running;
5530 #endif
5531                 sgs->sum_weighted_load += weighted_cpuload(i);
5532                 if (idle_cpu(i))
5533                         sgs->idle_cpus++;
5534         }
5535
5536         /* Adjust by relative CPU power of the group */
5537         sgs->group_power = group->sgp->power;
5538         sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE) / sgs->group_power;
5539
5540         if (sgs->sum_nr_running)
5541                 sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
5542
5543         sgs->group_weight = group->group_weight;
5544
5545         sgs->group_imb = sg_imbalanced(group);
5546         sgs->group_capacity = sg_capacity(env, group);
5547
5548         if (sgs->group_capacity > sgs->sum_nr_running)
5549                 sgs->group_has_capacity = 1;
5550 }
5551
5552 /**
5553  * update_sd_pick_busiest - return 1 on busiest group
5554  * @env: The load balancing environment.
5555  * @sds: sched_domain statistics
5556  * @sg: sched_group candidate to be checked for being the busiest
5557  * @sgs: sched_group statistics
5558  *
5559  * Determine if @sg is a busier group than the previously selected
5560  * busiest group.
5561  *
5562  * Return: %true if @sg is a busier group than the previously selected
5563  * busiest group. %false otherwise.
5564  */
5565 static bool update_sd_pick_busiest(struct lb_env *env,
5566                                    struct sd_lb_stats *sds,
5567                                    struct sched_group *sg,
5568                                    struct sg_lb_stats *sgs)
5569 {
5570         if (sgs->avg_load <= sds->busiest_stat.avg_load)
5571                 return false;
5572
5573         if (sgs->sum_nr_running > sgs->group_capacity)
5574                 return true;
5575
5576         if (sgs->group_imb)
5577                 return true;
5578
5579         /*
5580          * ASYM_PACKING needs to move all the work to the lowest
5581          * numbered CPUs in the group, therefore mark all groups
5582          * higher than ourself as busy.
5583          */
5584         if ((env->sd->flags & SD_ASYM_PACKING) && sgs->sum_nr_running &&
5585             env->dst_cpu < group_first_cpu(sg)) {
5586                 if (!sds->busiest)
5587                         return true;
5588
5589                 if (group_first_cpu(sds->busiest) > group_first_cpu(sg))
5590                         return true;
5591         }
5592
5593         return false;
5594 }
5595
5596 #ifdef CONFIG_NUMA_BALANCING
5597 static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
5598 {
5599         if (sgs->sum_nr_running > sgs->nr_numa_running)
5600                 return regular;
5601         if (sgs->sum_nr_running > sgs->nr_preferred_running)
5602                 return remote;
5603         return all;
5604 }
5605
5606 static inline enum fbq_type fbq_classify_rq(struct rq *rq)
5607 {
5608         if (rq->nr_running > rq->nr_numa_running)
5609                 return regular;
5610         if (rq->nr_running > rq->nr_preferred_running)
5611                 return remote;
5612         return all;
5613 }
5614 #else
5615 static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
5616 {
5617         return all;
5618 }
5619
5620 static inline enum fbq_type fbq_classify_rq(struct rq *rq)
5621 {
5622         return regular;
5623 }
5624 #endif /* CONFIG_NUMA_BALANCING */
5625
5626 /**
5627  * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
5628  * @env: The load balancing environment.
5629  * @sds: variable to hold the statistics for this sched_domain.
5630  */
5631 static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sds)
5632 {
5633         struct sched_domain *child = env->sd->child;
5634         struct sched_group *sg = env->sd->groups;
5635         struct sg_lb_stats tmp_sgs;
5636         int load_idx, prefer_sibling = 0;
5637
5638         if (child && child->flags & SD_PREFER_SIBLING)
5639                 prefer_sibling = 1;
5640
5641         load_idx = get_sd_load_idx(env->sd, env->idle);
5642
5643         do {
5644                 struct sg_lb_stats *sgs = &tmp_sgs;
5645                 int local_group;
5646
5647                 local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg));
5648                 if (local_group) {
5649                         sds->local = sg;
5650                         sgs = &sds->local_stat;
5651
5652                         if (env->idle != CPU_NEWLY_IDLE ||
5653                             time_after_eq(jiffies, sg->sgp->next_update))
5654                                 update_group_power(env->sd, env->dst_cpu);
5655                 }
5656
5657                 update_sg_lb_stats(env, sg, load_idx, local_group, sgs);
5658
5659                 if (local_group)
5660                         goto next_group;
5661
5662                 /*
5663                  * In case the child domain prefers tasks go to siblings
5664                  * first, lower the sg capacity to one so that we'll try
5665                  * and move all the excess tasks away. We lower the capacity
5666                  * of a group only if the local group has the capacity to fit
5667                  * these excess tasks, i.e. nr_running < group_capacity. The
5668                  * extra check prevents the case where you always pull from the
5669                  * heaviest group when it is already under-utilized (possible
5670                  * with a large weight task outweighs the tasks on the system).
5671                  */
5672                 if (prefer_sibling && sds->local &&
5673                     sds->local_stat.group_has_capacity)
5674                         sgs->group_capacity = min(sgs->group_capacity, 1U);
5675
5676                 if (update_sd_pick_busiest(env, sds, sg, sgs)) {
5677                         sds->busiest = sg;
5678                         sds->busiest_stat = *sgs;
5679                 }
5680
5681 next_group:
5682                 /* Now, start updating sd_lb_stats */
5683                 sds->total_load += sgs->group_load;
5684                 sds->total_pwr += sgs->group_power;
5685
5686                 sg = sg->next;
5687         } while (sg != env->sd->groups);
5688
5689         if (env->sd->flags & SD_NUMA)
5690                 env->fbq_type = fbq_classify_group(&sds->busiest_stat);
5691 }
5692
5693 /**
5694  * check_asym_packing - Check to see if the group is packed into the
5695  *                      sched doman.
5696  *
5697  * This is primarily intended to used at the sibling level.  Some
5698  * cores like POWER7 prefer to use lower numbered SMT threads.  In the
5699  * case of POWER7, it can move to lower SMT modes only when higher
5700  * threads are idle.  When in lower SMT modes, the threads will
5701  * perform better since they share less core resources.  Hence when we
5702  * have idle threads, we want them to be the higher ones.
5703  *
5704  * This packing function is run on idle threads.  It checks to see if
5705  * the busiest CPU in this domain (core in the P7 case) has a higher
5706  * CPU number than the packing function is being run on.  Here we are
5707  * assuming lower CPU number will be equivalent to lower a SMT thread
5708  * number.
5709  *
5710  * Return: 1 when packing is required and a task should be moved to
5711  * this CPU.  The amount of the imbalance is returned in *imbalance.
5712  *
5713  * @env: The load balancing environment.
5714  * @sds: Statistics of the sched_domain which is to be packed
5715  */
5716 static int check_asym_packing(struct lb_env *env, struct sd_lb_stats *sds)
5717 {
5718         int busiest_cpu;
5719
5720         if (!(env->sd->flags & SD_ASYM_PACKING))
5721                 return 0;
5722
5723         if (!sds->busiest)
5724                 return 0;
5725
5726         busiest_cpu = group_first_cpu(sds->busiest);
5727         if (env->dst_cpu > busiest_cpu)
5728                 return 0;
5729
5730         env->imbalance = DIV_ROUND_CLOSEST(
5731                 sds->busiest_stat.avg_load * sds->busiest_stat.group_power,
5732                 SCHED_POWER_SCALE);
5733
5734         return 1;
5735 }
5736
5737 /**
5738  * fix_small_imbalance - Calculate the minor imbalance that exists
5739  *                      amongst the groups of a sched_domain, during
5740  *                      load balancing.
5741  * @env: The load balancing environment.
5742  * @sds: Statistics of the sched_domain whose imbalance is to be calculated.
5743  */
5744 static inline
5745 void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
5746 {
5747         unsigned long tmp, pwr_now = 0, pwr_move = 0;
5748         unsigned int imbn = 2;
5749         unsigned long scaled_busy_load_per_task;
5750         struct sg_lb_stats *local, *busiest;
5751
5752         local = &sds->local_stat;
5753         busiest = &sds->busiest_stat;
5754
5755         if (!local->sum_nr_running)
5756                 local->load_per_task = cpu_avg_load_per_task(env->dst_cpu);
5757         else if (busiest->load_per_task > local->load_per_task)
5758                 imbn = 1;
5759
5760         scaled_busy_load_per_task =
5761                 (busiest->load_per_task * SCHED_POWER_SCALE) /
5762                 busiest->group_power;
5763
5764         if (busiest->avg_load + scaled_busy_load_per_task >=
5765             local->avg_load + (scaled_busy_load_per_task * imbn)) {
5766                 env->imbalance = busiest->load_per_task;
5767                 return;
5768         }
5769
5770         /*
5771          * OK, we don't have enough imbalance to justify moving tasks,
5772          * however we may be able to increase total CPU power used by
5773          * moving them.
5774          */
5775
5776         pwr_now += busiest->group_power *
5777                         min(busiest->load_per_task, busiest->avg_load);
5778         pwr_now += local->group_power *
5779                         min(local->load_per_task, local->avg_load);
5780         pwr_now /= SCHED_POWER_SCALE;
5781
5782         /* Amount of load we'd subtract */
5783         tmp = (busiest->load_per_task * SCHED_POWER_SCALE) /
5784                 busiest->group_power;
5785         if (busiest->avg_load > tmp) {
5786                 pwr_move += busiest->group_power *
5787                             min(busiest->load_per_task,
5788                                 busiest->avg_load - tmp);
5789         }
5790
5791         /* Amount of load we'd add */
5792         if (busiest->avg_load * busiest->group_power <
5793             busiest->load_per_task * SCHED_POWER_SCALE) {
5794                 tmp = (busiest->avg_load * busiest->group_power) /
5795                       local->group_power;
5796         } else {
5797                 tmp = (busiest->load_per_task * SCHED_POWER_SCALE) /
5798                       local->group_power;
5799         }
5800         pwr_move += local->group_power *
5801                     min(local->load_per_task, local->avg_load + tmp);
5802         pwr_move /= SCHED_POWER_SCALE;
5803
5804         /* Move if we gain throughput */
5805         if (pwr_move > pwr_now)
5806                 env->imbalance = busiest->load_per_task;
5807 }
5808
5809 /**
5810  * calculate_imbalance - Calculate the amount of imbalance present within the
5811  *                       groups of a given sched_domain during load balance.
5812  * @env: load balance environment
5813  * @sds: statistics of the sched_domain whose imbalance is to be calculated.
5814  */
5815 static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
5816 {
5817         unsigned long max_pull, load_above_capacity = ~0UL;
5818         struct sg_lb_stats *local, *busiest;
5819
5820         local = &sds->local_stat;
5821         busiest = &sds->busiest_stat;
5822
5823         if (busiest->group_imb) {
5824                 /*
5825                  * In the group_imb case we cannot rely on group-wide averages
5826                  * to ensure cpu-load equilibrium, look at wider averages. XXX
5827                  */
5828                 busiest->load_per_task =
5829                         min(busiest->load_per_task, sds->avg_load);
5830         }
5831
5832         /*
5833          * In the presence of smp nice balancing, certain scenarios can have
5834          * max load less than avg load(as we skip the groups at or below
5835          * its cpu_power, while calculating max_load..)
5836          */
5837         if (busiest->avg_load <= sds->avg_load ||
5838             local->avg_load >= sds->avg_load) {
5839                 env->imbalance = 0;
5840                 return fix_small_imbalance(env, sds);
5841         }
5842
5843         if (!busiest->group_imb) {
5844                 /*
5845                  * Don't want to pull so many tasks that a group would go idle.
5846                  * Except of course for the group_imb case, since then we might
5847                  * have to drop below capacity to reach cpu-load equilibrium.
5848                  */
5849                 load_above_capacity =
5850                         (busiest->sum_nr_running - busiest->group_capacity);
5851
5852                 load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_POWER_SCALE);
5853                 load_above_capacity /= busiest->group_power;
5854         }
5855
5856         /*
5857          * We're trying to get all the cpus to the average_load, so we don't
5858          * want to push ourselves above the average load, nor do we wish to
5859          * reduce the max loaded cpu below the average load. At the same time,
5860          * we also don't want to reduce the group load below the group capacity
5861          * (so that we can implement power-savings policies etc). Thus we look
5862          * for the minimum possible imbalance.
5863          */
5864         max_pull = min(busiest->avg_load - sds->avg_load, load_above_capacity);
5865
5866         /* How much load to actually move to equalise the imbalance */
5867         env->imbalance = min(
5868                 max_pull * busiest->group_power,
5869                 (sds->avg_load - local->avg_load) * local->group_power
5870         ) / SCHED_POWER_SCALE;
5871
5872         /*
5873          * if *imbalance is less than the average load per runnable task
5874          * there is no guarantee that any tasks will be moved so we'll have
5875          * a think about bumping its value to force at least one task to be
5876          * moved
5877          */
5878         if (env->imbalance < busiest->load_per_task)
5879                 return fix_small_imbalance(env, sds);
5880 }
5881
5882 /******* find_busiest_group() helpers end here *********************/
5883
5884 /**
5885  * find_busiest_group - Returns the busiest group within the sched_domain
5886  * if there is an imbalance. If there isn't an imbalance, and
5887  * the user has opted for power-savings, it returns a group whose
5888  * CPUs can be put to idle by rebalancing those tasks elsewhere, if
5889  * such a group exists.
5890  *
5891  * Also calculates the amount of weighted load which should be moved
5892  * to restore balance.
5893  *
5894  * @env: The load balancing environment.
5895  *
5896  * Return:      - The busiest group if imbalance exists.
5897  *              - If no imbalance and user has opted for power-savings balance,
5898  *                 return the least loaded group whose CPUs can be
5899  *                 put to idle by rebalancing its tasks onto our group.
5900  */
5901 static struct sched_group *find_busiest_group(struct lb_env *env)
5902 {
5903         struct sg_lb_stats *local, *busiest;
5904         struct sd_lb_stats sds;
5905
5906         init_sd_lb_stats(&sds);
5907
5908         /*
5909          * Compute the various statistics relavent for load balancing at
5910          * this level.
5911          */
5912         update_sd_lb_stats(env, &sds);
5913         local = &sds.local_stat;
5914         busiest = &sds.busiest_stat;
5915
5916         if ((env->idle == CPU_IDLE || env->idle == CPU_NEWLY_IDLE) &&
5917             check_asym_packing(env, &sds))
5918                 return sds.busiest;
5919
5920         /* There is no busy sibling group to pull tasks from */
5921         if (!sds.busiest || busiest->sum_nr_running == 0)
5922                 goto out_balanced;
5923
5924         sds.avg_load = (SCHED_POWER_SCALE * sds.total_load) / sds.total_pwr;
5925
5926         /*
5927          * If the busiest group is imbalanced the below checks don't
5928          * work because they assume all things are equal, which typically
5929          * isn't true due to cpus_allowed constraints and the like.
5930          */
5931         if (busiest->group_imb)
5932                 goto force_balance;
5933
5934         /* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */
5935         if (env->idle == CPU_NEWLY_IDLE && local->group_has_capacity &&
5936             !busiest->group_has_capacity)
5937                 goto force_balance;
5938
5939         /*
5940          * If the local group is more busy than the selected busiest group
5941          * don't try and pull any tasks.
5942          */
5943         if (local->avg_load >= busiest->avg_load)
5944                 goto out_balanced;
5945
5946         /*
5947          * Don't pull any tasks if this group is already above the domain
5948          * average load.
5949          */
5950         if (local->avg_load >= sds.avg_load)
5951                 goto out_balanced;
5952
5953         if (env->idle == CPU_IDLE) {
5954                 /*
5955                  * This cpu is idle. If the busiest group load doesn't
5956                  * have more tasks than the number of available cpu's and
5957                  * there is no imbalance between this and busiest group
5958                  * wrt to idle cpu's, it is balanced.
5959                  */
5960                 if ((local->idle_cpus < busiest->idle_cpus) &&
5961                     busiest->sum_nr_running <= busiest->group_weight)
5962                         goto out_balanced;
5963         } else {
5964                 /*
5965                  * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use
5966                  * imbalance_pct to be conservative.
5967                  */
5968                 if (100 * busiest->avg_load <=
5969                                 env->sd->imbalance_pct * local->avg_load)
5970                         goto out_balanced;
5971         }
5972
5973 force_balance:
5974         /* Looks like there is an imbalance. Compute it */
5975         calculate_imbalance(env, &sds);
5976         return sds.busiest;
5977
5978 out_balanced:
5979         env->imbalance = 0;
5980         return NULL;
5981 }
5982
5983 /*
5984  * find_busiest_queue - find the busiest runqueue among the cpus in group.
5985  */
5986 static struct rq *find_busiest_queue(struct lb_env *env,
5987                                      struct sched_group *group)
5988 {
5989         struct rq *busiest = NULL, *rq;
5990         unsigned long busiest_load = 0, busiest_power = 1;
5991         int i;
5992
5993         for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
5994                 unsigned long power, capacity, wl;
5995                 enum fbq_type rt;
5996
5997                 rq = cpu_rq(i);
5998                 rt = fbq_classify_rq(rq);
5999
6000                 /*
6001                  * We classify groups/runqueues into three groups:
6002                  *  - regular: there are !numa tasks
6003                  *  - remote:  there are numa tasks that run on the 'wrong' node
6004                  *  - all:     there is no distinction
6005                  *
6006                  * In order to avoid migrating ideally placed numa tasks,
6007                  * ignore those when there's better options.
6008                  *
6009                  * If we ignore the actual busiest queue to migrate another
6010                  * task, the next balance pass can still reduce the busiest
6011                  * queue by moving tasks around inside the node.
6012                  *
6013                  * If we cannot move enough load due to this classification
6014                  * the next pass will adjust the group classification and
6015                  * allow migration of more tasks.
6016                  *
6017                  * Both cases only affect the total convergence complexity.
6018                  */
6019                 if (rt > env->fbq_type)
6020                         continue;
6021
6022                 power = power_of(i);
6023                 capacity = DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE);
6024                 if (!capacity)
6025                         capacity = fix_small_capacity(env->sd, group);
6026
6027                 wl = weighted_cpuload(i);
6028
6029                 /*
6030                  * When comparing with imbalance, use weighted_cpuload()
6031                  * which is not scaled with the cpu power.
6032                  */
6033                 if (capacity && rq->nr_running == 1 && wl > env->imbalance)
6034                         continue;
6035
6036                 /*
6037                  * For the load comparisons with the other cpu's, consider
6038                  * the weighted_cpuload() scaled with the cpu power, so that
6039                  * the load can be moved away from the cpu that is potentially
6040                  * running at a lower capacity.
6041                  *
6042                  * Thus we're looking for max(wl_i / power_i), crosswise
6043                  * multiplication to rid ourselves of the division works out
6044                  * to: wl_i * power_j > wl_j * power_i;  where j is our
6045                  * previous maximum.
6046                  */
6047                 if (wl * busiest_power > busiest_load * power) {
6048                         busiest_load = wl;
6049                         busiest_power = power;
6050                         busiest = rq;
6051                 }
6052         }
6053
6054         return busiest;
6055 }
6056
6057 /*
6058  * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
6059  * so long as it is large enough.
6060  */
6061 #define MAX_PINNED_INTERVAL     512
6062
6063 /* Working cpumask for load_balance and load_balance_newidle. */
6064 DEFINE_PER_CPU(cpumask_var_t, load_balance_mask);
6065
6066 static int need_active_balance(struct lb_env *env)
6067 {
6068         struct sched_domain *sd = env->sd;
6069
6070         if (env->idle == CPU_NEWLY_IDLE) {
6071
6072                 /*
6073                  * ASYM_PACKING needs to force migrate tasks from busy but
6074                  * higher numbered CPUs in order to pack all tasks in the
6075                  * lowest numbered CPUs.
6076                  */
6077                 if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
6078                         return 1;
6079         }
6080
6081         return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
6082 }
6083
6084 static int active_load_balance_cpu_stop(void *data);
6085
6086 static int should_we_balance(struct lb_env *env)
6087 {
6088         struct sched_group *sg = env->sd->groups;
6089         struct cpumask *sg_cpus, *sg_mask;
6090         int cpu, balance_cpu = -1;
6091
6092         /*
6093          * In the newly idle case, we will allow all the cpu's
6094          * to do the newly idle load balance.
6095          */
6096         if (env->idle == CPU_NEWLY_IDLE)
6097                 return 1;
6098
6099         sg_cpus = sched_group_cpus(sg);
6100         sg_mask = sched_group_mask(sg);
6101         /* Try to find first idle cpu */
6102         for_each_cpu_and(cpu, sg_cpus, env->cpus) {
6103                 if (!cpumask_test_cpu(cpu, sg_mask) || !idle_cpu(cpu))
6104                         continue;
6105
6106                 balance_cpu = cpu;
6107                 break;
6108         }
6109
6110         if (balance_cpu == -1)
6111                 balance_cpu = group_balance_cpu(sg);
6112
6113         /*
6114          * First idle cpu or the first cpu(busiest) in this sched group
6115          * is eligible for doing load balancing at this and above domains.
6116          */
6117         return balance_cpu == env->dst_cpu;
6118 }
6119
6120 /*
6121  * Check this_cpu to ensure it is balanced within domain. Attempt to move
6122  * tasks if there is an imbalance.
6123  */
6124 static int load_balance(int this_cpu, struct rq *this_rq,
6125                         struct sched_domain *sd, enum cpu_idle_type idle,
6126                         int *continue_balancing)
6127 {
6128         int ld_moved, cur_ld_moved, active_balance = 0;
6129         struct sched_domain *sd_parent = sd->parent;
6130         struct sched_group *group;
6131         struct rq *busiest;
6132         unsigned long flags;
6133         struct cpumask *cpus = __get_cpu_var(load_balance_mask);
6134
6135         struct lb_env env = {
6136                 .sd             = sd,
6137                 .dst_cpu        = this_cpu,
6138                 .dst_rq         = this_rq,
6139                 .dst_grpmask    = sched_group_cpus(sd->groups),
6140                 .idle           = idle,
6141                 .loop_break     = sched_nr_migrate_break,
6142                 .cpus           = cpus,
6143                 .fbq_type       = all,
6144         };
6145
6146         /*
6147          * For NEWLY_IDLE load_balancing, we don't need to consider
6148          * other cpus in our group
6149          */
6150         if (idle == CPU_NEWLY_IDLE)
6151                 env.dst_grpmask = NULL;
6152
6153         cpumask_copy(cpus, cpu_active_mask);
6154
6155         schedstat_inc(sd, lb_count[idle]);
6156
6157 redo:
6158         if (!should_we_balance(&env)) {
6159                 *continue_balancing = 0;
6160                 goto out_balanced;
6161         }
6162
6163         group = find_busiest_group(&env);
6164         if (!group) {
6165                 schedstat_inc(sd, lb_nobusyg[idle]);
6166                 goto out_balanced;
6167         }
6168
6169         busiest = find_busiest_queue(&env, group);
6170         if (!busiest) {
6171                 schedstat_inc(sd, lb_nobusyq[idle]);
6172                 goto out_balanced;
6173         }
6174
6175         BUG_ON(busiest == env.dst_rq);
6176
6177         schedstat_add(sd, lb_imbalance[idle], env.imbalance);
6178
6179         ld_moved = 0;
6180         if (busiest->nr_running > 1) {
6181                 /*
6182                  * Attempt to move tasks. If find_busiest_group has found
6183                  * an imbalance but busiest->nr_running <= 1, the group is
6184                  * still unbalanced. ld_moved simply stays zero, so it is
6185                  * correctly treated as an imbalance.
6186                  */
6187                 env.flags |= LBF_ALL_PINNED;
6188                 env.src_cpu   = busiest->cpu;
6189                 env.src_rq    = busiest;
6190                 env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);
6191
6192 more_balance:
6193                 local_irq_save(flags);
6194                 double_rq_lock(env.dst_rq, busiest);
6195
6196                 /*
6197                  * cur_ld_moved - load moved in current iteration
6198                  * ld_moved     - cumulative load moved across iterations
6199                  */
6200                 cur_ld_moved = move_tasks(&env);
6201                 ld_moved += cur_ld_moved;
6202                 double_rq_unlock(env.dst_rq, busiest);
6203                 local_irq_restore(flags);
6204
6205                 /*
6206                  * some other cpu did the load balance for us.
6207                  */
6208                 if (cur_ld_moved && env.dst_cpu != smp_processor_id())
6209                         resched_cpu(env.dst_cpu);
6210
6211                 if (env.flags & LBF_NEED_BREAK) {
6212                         env.flags &= ~LBF_NEED_BREAK;
6213                         goto more_balance;
6214                 }
6215
6216                 /*
6217                  * Revisit (affine) tasks on src_cpu that couldn't be moved to
6218                  * us and move them to an alternate dst_cpu in our sched_group
6219                  * where they can run. The upper limit on how many times we
6220                  * iterate on same src_cpu is dependent on number of cpus in our
6221                  * sched_group.
6222                  *
6223                  * This changes load balance semantics a bit on who can move
6224                  * load to a given_cpu. In addition to the given_cpu itself
6225                  * (or a ilb_cpu acting on its behalf where given_cpu is
6226                  * nohz-idle), we now have balance_cpu in a position to move
6227                  * load to given_cpu. In rare situations, this may cause
6228                  * conflicts (balance_cpu and given_cpu/ilb_cpu deciding
6229                  * _independently_ and at _same_ time to move some load to
6230                  * given_cpu) causing exceess load to be moved to given_cpu.
6231                  * This however should not happen so much in practice and
6232                  * moreover subsequent load balance cycles should correct the
6233                  * excess load moved.
6234                  */
6235                 if ((env.flags & LBF_DST_PINNED) && env.imbalance > 0) {
6236
6237                         /* Prevent to re-select dst_cpu via env's cpus */
6238                         cpumask_clear_cpu(env.dst_cpu, env.cpus);
6239
6240                         env.dst_rq       = cpu_rq(env.new_dst_cpu);
6241                         env.dst_cpu      = env.new_dst_cpu;
6242                         env.flags       &= ~LBF_DST_PINNED;
6243                         env.loop         = 0;
6244                         env.loop_break   = sched_nr_migrate_break;
6245
6246                         /*
6247                          * Go back to "more_balance" rather than "redo" since we
6248                          * need to continue with same src_cpu.
6249                          */
6250                         goto more_balance;
6251                 }
6252
6253                 /*
6254                  * We failed to reach balance because of affinity.
6255                  */
6256                 if (sd_parent) {
6257                         int *group_imbalance = &sd_parent->groups->sgp->imbalance;
6258
6259                         if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0) {
6260                                 *group_imbalance = 1;
6261                         } else if (*group_imbalance)
6262                                 *group_imbalance = 0;
6263                 }
6264
6265                 /* All tasks on this runqueue were pinned by CPU affinity */
6266                 if (unlikely(env.flags & LBF_ALL_PINNED)) {
6267                         cpumask_clear_cpu(cpu_of(busiest), cpus);
6268                         if (!cpumask_empty(cpus)) {
6269                                 env.loop = 0;
6270                                 env.loop_break = sched_nr_migrate_break;
6271                                 goto redo;
6272                         }
6273                         goto out_balanced;
6274                 }
6275         }
6276
6277         if (!ld_moved) {
6278                 schedstat_inc(sd, lb_failed[idle]);
6279                 /*
6280                  * Increment the failure counter only on periodic balance.
6281                  * We do not want newidle balance, which can be very
6282                  * frequent, pollute the failure counter causing
6283                  * excessive cache_hot migrations and active balances.
6284                  */
6285                 if (idle != CPU_NEWLY_IDLE)
6286                         sd->nr_balance_failed++;
6287
6288                 if (need_active_balance(&env)) {
6289                         raw_spin_lock_irqsave(&busiest->lock, flags);
6290
6291                         /* don't kick the active_load_balance_cpu_stop,
6292                          * if the curr task on busiest cpu can't be
6293                          * moved to this_cpu
6294                          */
6295                         if (!cpumask_test_cpu(this_cpu,
6296                                         tsk_cpus_allowed(busiest->curr))) {
6297                                 raw_spin_unlock_irqrestore(&busiest->lock,
6298                                                             flags);
6299                                 env.flags |= LBF_ALL_PINNED;
6300                                 goto out_one_pinned;
6301                         }
6302
6303                         /*
6304                          * ->active_balance synchronizes accesses to
6305                          * ->active_balance_work.  Once set, it's cleared
6306                          * only after active load balance is finished.
6307                          */
6308                         if (!busiest->active_balance) {
6309                                 busiest->active_balance = 1;
6310                                 busiest->push_cpu = this_cpu;
6311                                 active_balance = 1;
6312                         }
6313                         raw_spin_unlock_irqrestore(&busiest->lock, flags);
6314
6315                         if (active_balance) {
6316                                 stop_one_cpu_nowait(cpu_of(busiest),
6317                                         active_load_balance_cpu_stop, busiest,
6318                                         &busiest->active_balance_work);
6319                         }
6320
6321                         /*
6322                          * We've kicked active balancing, reset the failure
6323                          * counter.
6324                          */
6325                         sd->nr_balance_failed = sd->cache_nice_tries+1;
6326                 }
6327         } else
6328                 sd->nr_balance_failed = 0;
6329
6330         if (likely(!active_balance)) {
6331                 /* We were unbalanced, so reset the balancing interval */
6332                 sd->balance_interval = sd->min_interval;
6333         } else {
6334                 /*
6335                  * If we've begun active balancing, start to back off. This
6336                  * case may not be covered by the all_pinned logic if there
6337                  * is only 1 task on the busy runqueue (because we don't call
6338                  * move_tasks).
6339                  */
6340                 if (sd->balance_interval < sd->max_interval)
6341                         sd->balance_interval *= 2;
6342         }
6343
6344         goto out;
6345
6346 out_balanced:
6347         schedstat_inc(sd, lb_balanced[idle]);
6348
6349         sd->nr_balance_failed = 0;
6350
6351 out_one_pinned:
6352         /* tune up the balancing interval */
6353         if (((env.flags & LBF_ALL_PINNED) &&
6354                         sd->balance_interval < MAX_PINNED_INTERVAL) ||
6355                         (sd->balance_interval < sd->max_interval))
6356                 sd->balance_interval *= 2;
6357
6358         ld_moved = 0;
6359 out:
6360         return ld_moved;
6361 }
6362
6363 /*
6364  * idle_balance is called by schedule() if this_cpu is about to become
6365  * idle. Attempts to pull tasks from other CPUs.
6366  */
6367 void idle_balance(int this_cpu, struct rq *this_rq)
6368 {
6369         struct sched_domain *sd;
6370         int pulled_task = 0;
6371         unsigned long next_balance = jiffies + HZ;
6372         u64 curr_cost = 0;
6373
6374         this_rq->idle_stamp = rq_clock(this_rq);
6375
6376         if (this_rq->avg_idle < sysctl_sched_migration_cost)
6377                 return;
6378
6379         /*
6380          * Drop the rq->lock, but keep IRQ/preempt disabled.
6381          */
6382         raw_spin_unlock(&this_rq->lock);
6383
6384         update_blocked_averages(this_cpu);
6385         rcu_read_lock();
6386         for_each_domain(this_cpu, sd) {
6387                 unsigned long interval;
6388                 int continue_balancing = 1;
6389                 u64 t0, domain_cost;
6390
6391                 if (!(sd->flags & SD_LOAD_BALANCE))
6392                         continue;
6393
6394                 if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
6395                         break;
6396
6397                 if (sd->flags & SD_BALANCE_NEWIDLE) {
6398                         t0 = sched_clock_cpu(this_cpu);
6399
6400                         /* If we've pulled tasks over stop searching: */
6401                         pulled_task = load_balance(this_cpu, this_rq,
6402                                                    sd, CPU_NEWLY_IDLE,
6403                                                    &continue_balancing);
6404
6405                         domain_cost = sched_clock_cpu(this_cpu) - t0;
6406                         if (domain_cost > sd->max_newidle_lb_cost)
6407                                 sd->max_newidle_lb_cost = domain_cost;
6408
6409                         curr_cost += domain_cost;
6410                 }
6411
6412                 interval = msecs_to_jiffies(sd->balance_interval);
6413                 if (time_after(next_balance, sd->last_balance + interval))
6414                         next_balance = sd->last_balance + interval;
6415                 if (pulled_task) {
6416                         this_rq->idle_stamp = 0;
6417                         break;
6418                 }
6419         }
6420         rcu_read_unlock();
6421
6422         raw_spin_lock(&this_rq->lock);
6423
6424         if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
6425                 /*
6426                  * We are going idle. next_balance may be set based on
6427                  * a busy processor. So reset next_balance.
6428                  */
6429                 this_rq->next_balance = next_balance;
6430         }
6431
6432         if (curr_cost > this_rq->max_idle_balance_cost)
6433                 this_rq->max_idle_balance_cost = curr_cost;
6434 }
6435
6436 /*
6437  * active_load_balance_cpu_stop is run by cpu stopper. It pushes
6438  * running tasks off the busiest CPU onto idle CPUs. It requires at
6439  * least 1 task to be running on each physical CPU where possible, and
6440  * avoids physical / logical imbalances.
6441  */
6442 static int active_load_balance_cpu_stop(void *data)
6443 {
6444         struct rq *busiest_rq = data;
6445         int busiest_cpu = cpu_of(busiest_rq);
6446         int target_cpu = busiest_rq->push_cpu;
6447         struct rq *target_rq = cpu_rq(target_cpu);
6448         struct sched_domain *sd;
6449
6450         raw_spin_lock_irq(&busiest_rq->lock);
6451
6452         /* make sure the requested cpu hasn't gone down in the meantime */
6453         if (unlikely(busiest_cpu != smp_processor_id() ||
6454                      !busiest_rq->active_balance))
6455                 goto out_unlock;
6456
6457         /* Is there any task to move? */
6458         if (busiest_rq->nr_running <= 1)
6459                 goto out_unlock;
6460
6461         /*
6462          * This condition is "impossible", if it occurs
6463          * we need to fix it. Originally reported by
6464          * Bjorn Helgaas on a 128-cpu setup.
6465          */
6466         BUG_ON(busiest_rq == target_rq);
6467
6468         /* move a task from busiest_rq to target_rq */
6469         double_lock_balance(busiest_rq, target_rq);
6470
6471         /* Search for an sd spanning us and the target CPU. */
6472         rcu_read_lock();
6473         for_each_domain(target_cpu, sd) {
6474                 if ((sd->flags & SD_LOAD_BALANCE) &&
6475                     cpumask_test_cpu(busiest_cpu, sched_domain_span(sd)))
6476                                 break;
6477         }
6478
6479         if (likely(sd)) {
6480                 struct lb_env env = {
6481                         .sd             = sd,
6482                         .dst_cpu        = target_cpu,
6483                         .dst_rq         = target_rq,
6484                         .src_cpu        = busiest_rq->cpu,
6485                         .src_rq         = busiest_rq,
6486                         .idle           = CPU_IDLE,
6487                 };
6488
6489                 schedstat_inc(sd, alb_count);
6490
6491                 if (move_one_task(&env))
6492                         schedstat_inc(sd, alb_pushed);
6493                 else
6494                         schedstat_inc(sd, alb_failed);
6495         }
6496         rcu_read_unlock();
6497         double_unlock_balance(busiest_rq, target_rq);
6498 out_unlock:
6499         busiest_rq->active_balance = 0;
6500         raw_spin_unlock_irq(&busiest_rq->lock);
6501         return 0;
6502 }
6503
6504 #ifdef CONFIG_NO_HZ_COMMON
6505 /*
6506  * idle load balancing details
6507  * - When one of the busy CPUs notice that there may be an idle rebalancing
6508  *   needed, they will kick the idle load balancer, which then does idle
6509  *   load balancing for all the idle CPUs.
6510  */
6511 static struct {
6512         cpumask_var_t idle_cpus_mask;
6513         atomic_t nr_cpus;
6514         unsigned long next_balance;     /* in jiffy units */
6515 } nohz ____cacheline_aligned;
6516
6517 static inline int find_new_ilb(int call_cpu)
6518 {
6519         int ilb = cpumask_first(nohz.idle_cpus_mask);
6520
6521         if (ilb < nr_cpu_ids && idle_cpu(ilb))
6522                 return ilb;
6523
6524         return nr_cpu_ids;
6525 }
6526
6527 /*
6528  * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
6529  * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
6530  * CPU (if there is one).
6531  */
6532 static void nohz_balancer_kick(int cpu)
6533 {
6534         int ilb_cpu;
6535
6536         nohz.next_balance++;
6537
6538         ilb_cpu = find_new_ilb(cpu);
6539
6540         if (ilb_cpu >= nr_cpu_ids)
6541                 return;
6542
6543         if (test_and_set_bit(NOHZ_BALANCE_KICK, nohz_flags(ilb_cpu)))
6544                 return;
6545         /*
6546          * Use smp_send_reschedule() instead of resched_cpu().
6547          * This way we generate a sched IPI on the target cpu which
6548          * is idle. And the softirq performing nohz idle load balance
6549          * will be run before returning from the IPI.
6550          */
6551         smp_send_reschedule(ilb_cpu);
6552         return;
6553 }
6554
6555 static inline void nohz_balance_exit_idle(int cpu)
6556 {
6557         if (unlikely(test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)))) {
6558                 cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
6559                 atomic_dec(&nohz.nr_cpus);
6560                 clear_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu));
6561         }
6562 }
6563
6564 static inline void set_cpu_sd_state_busy(void)
6565 {
6566         struct sched_domain *sd;
6567         int cpu = smp_processor_id();
6568
6569         rcu_read_lock();
6570         sd = rcu_dereference(per_cpu(sd_busy, cpu));
6571
6572         if (!sd || !sd->nohz_idle)
6573                 goto unlock;
6574         sd->nohz_idle = 0;
6575
6576         atomic_inc(&sd->groups->sgp->nr_busy_cpus);
6577 unlock:
6578         rcu_read_unlock();
6579 }
6580
6581 void set_cpu_sd_state_idle(void)
6582 {
6583         struct sched_domain *sd;
6584         int cpu = smp_processor_id();
6585
6586         rcu_read_lock();
6587         sd = rcu_dereference(per_cpu(sd_busy, cpu));
6588
6589         if (!sd || sd->nohz_idle)
6590                 goto unlock;
6591         sd->nohz_idle = 1;
6592
6593         atomic_dec(&sd->groups->sgp->nr_busy_cpus);
6594 unlock:
6595         rcu_read_unlock();
6596 }
6597
6598 /*
6599  * This routine will record that the cpu is going idle with tick stopped.
6600  * This info will be used in performing idle load balancing in the future.
6601  */
6602 void nohz_balance_enter_idle(int cpu)
6603 {
6604         /*
6605          * If this cpu is going down, then nothing needs to be done.
6606          */
6607         if (!cpu_active(cpu))
6608                 return;
6609
6610         if (test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)))
6611                 return;
6612
6613         cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
6614         atomic_inc(&nohz.nr_cpus);
6615         set_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu));
6616 }
6617
6618 static int sched_ilb_notifier(struct notifier_block *nfb,
6619                                         unsigned long action, void *hcpu)
6620 {
6621         switch (action & ~CPU_TASKS_FROZEN) {
6622         case CPU_DYING:
6623                 nohz_balance_exit_idle(smp_processor_id());
6624                 return NOTIFY_OK;
6625         default:
6626                 return NOTIFY_DONE;
6627         }
6628 }
6629 #endif
6630
6631 static DEFINE_SPINLOCK(balancing);
6632
6633 /*
6634  * Scale the max load_balance interval with the number of CPUs in the system.
6635  * This trades load-balance latency on larger machines for less cross talk.
6636  */
6637 void update_max_interval(void)
6638 {
6639         max_load_balance_interval = HZ*num_online_cpus()/10;
6640 }
6641
6642 /*
6643  * It checks each scheduling domain to see if it is due to be balanced,
6644  * and initiates a balancing operation if so.
6645  *
6646  * Balancing parameters are set up in init_sched_domains.
6647  */
6648 static void rebalance_domains(int cpu, enum cpu_idle_type idle)
6649 {
6650         int continue_balancing = 1;
6651         struct rq *rq = cpu_rq(cpu);
6652         unsigned long interval;
6653         struct sched_domain *sd;
6654         /* Earliest time when we have to do rebalance again */
6655         unsigned long next_balance = jiffies + 60*HZ;
6656         int update_next_balance = 0;
6657         int need_serialize, need_decay = 0;
6658         u64 max_cost = 0;
6659
6660         update_blocked_averages(cpu);
6661
6662         rcu_read_lock();
6663         for_each_domain(cpu, sd) {
6664                 /*
6665                  * Decay the newidle max times here because this is a regular
6666                  * visit to all the domains. Decay ~1% per second.
6667                  */
6668                 if (time_after(jiffies, sd->next_decay_max_lb_cost)) {
6669                         sd->max_newidle_lb_cost =
6670                                 (sd->max_newidle_lb_cost * 253) / 256;
6671                         sd->next_decay_max_lb_cost = jiffies + HZ;
6672                         need_decay = 1;
6673                 }
6674                 max_cost += sd->max_newidle_lb_cost;
6675
6676                 if (!(sd->flags & SD_LOAD_BALANCE))
6677                         continue;
6678
6679                 /*
6680                  * Stop the load balance at this level. There is another
6681                  * CPU in our sched group which is doing load balancing more
6682                  * actively.
6683                  */
6684                 if (!continue_balancing) {
6685                         if (need_decay)
6686                                 continue;
6687                         break;
6688                 }
6689
6690                 interval = sd->balance_interval;
6691                 if (idle != CPU_IDLE)
6692                         interval *= sd->busy_factor;
6693
6694                 /* scale ms to jiffies */
6695                 interval = msecs_to_jiffies(interval);
6696                 interval = clamp(interval, 1UL, max_load_balance_interval);
6697
6698                 need_serialize = sd->flags & SD_SERIALIZE;
6699
6700                 if (need_serialize) {
6701                         if (!spin_trylock(&balancing))
6702                                 goto out;
6703                 }
6704
6705                 if (time_after_eq(jiffies, sd->last_balance + interval)) {
6706                         if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
6707                                 /*
6708                                  * The LBF_DST_PINNED logic could have changed
6709                                  * env->dst_cpu, so we can't know our idle
6710                                  * state even if we migrated tasks. Update it.
6711                                  */
6712                                 idle = idle_cpu(cpu) ? CPU_IDLE : CPU_NOT_IDLE;
6713                         }
6714                         sd->last_balance = jiffies;
6715                 }
6716                 if (need_serialize)
6717                         spin_unlock(&balancing);
6718 out:
6719                 if (time_after(next_balance, sd->last_balance + interval)) {
6720                         next_balance = sd->last_balance + interval;
6721                         update_next_balance = 1;
6722                 }
6723         }
6724         if (need_decay) {
6725                 /*
6726                  * Ensure the rq-wide value also decays but keep it at a
6727                  * reasonable floor to avoid funnies with rq->avg_idle.
6728                  */
6729                 rq->max_idle_balance_cost =
6730                         max((u64)sysctl_sched_migration_cost, max_cost);
6731         }
6732         rcu_read_unlock();
6733
6734         /*
6735          * next_balance will be updated only when there is a need.
6736          * When the cpu is attached to null domain for ex, it will not be
6737          * updated.
6738          */
6739         if (likely(update_next_balance))
6740                 rq->next_balance = next_balance;
6741 }
6742
6743 #ifdef CONFIG_NO_HZ_COMMON
6744 /*
6745  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
6746  * rebalancing for all the cpus for whom scheduler ticks are stopped.
6747  */
6748 static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle)
6749 {
6750         struct rq *this_rq = cpu_rq(this_cpu);
6751         struct rq *rq;
6752         int balance_cpu;
6753
6754         if (idle != CPU_IDLE ||
6755             !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
6756                 goto end;
6757
6758         for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
6759                 if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
6760                         continue;
6761
6762                 /*
6763                  * If this cpu gets work to do, stop the load balancing
6764                  * work being done for other cpus. Next load
6765                  * balancing owner will pick it up.
6766                  */
6767                 if (need_resched())
6768                         break;
6769
6770                 rq = cpu_rq(balance_cpu);
6771
6772                 raw_spin_lock_irq(&rq->lock);
6773                 update_rq_clock(rq);
6774                 update_idle_cpu_load(rq);
6775                 raw_spin_unlock_irq(&rq->lock);
6776
6777                 rebalance_domains(balance_cpu, CPU_IDLE);
6778
6779                 if (time_after(this_rq->next_balance, rq->next_balance))
6780                         this_rq->next_balance = rq->next_balance;
6781         }
6782         nohz.next_balance = this_rq->next_balance;
6783 end:
6784         clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
6785 }
6786
6787 /*
6788  * Current heuristic for kicking the idle load balancer in the presence
6789  * of an idle cpu is the system.
6790  *   - This rq has more than one task.
6791  *   - At any scheduler domain level, this cpu's scheduler group has multiple
6792  *     busy cpu's exceeding the group's power.
6793  *   - For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler
6794  *     domain span are idle.
6795  */
6796 static inline int nohz_kick_needed(struct rq *rq, int cpu)
6797 {
6798         unsigned long now = jiffies;
6799         struct sched_domain *sd;
6800         struct sched_group_power *sgp;
6801         int nr_busy;
6802
6803         if (unlikely(idle_cpu(cpu)))
6804                 return 0;
6805
6806        /*
6807         * We may be recently in ticked or tickless idle mode. At the first
6808         * busy tick after returning from idle, we will update the busy stats.
6809         */
6810         set_cpu_sd_state_busy();
6811         nohz_balance_exit_idle(cpu);
6812
6813         /*
6814          * None are in tickless mode and hence no need for NOHZ idle load
6815          * balancing.
6816          */
6817         if (likely(!atomic_read(&nohz.nr_cpus)))
6818                 return 0;
6819
6820         if (time_before(now, nohz.next_balance))
6821                 return 0;
6822
6823         if (rq->nr_running >= 2)
6824                 goto need_kick;
6825
6826         rcu_read_lock();
6827         sd = rcu_dereference(per_cpu(sd_busy, cpu));
6828
6829         if (sd) {
6830                 sgp = sd->groups->sgp;
6831                 nr_busy = atomic_read(&sgp->nr_busy_cpus);
6832
6833                 if (nr_busy > 1)
6834                         goto need_kick_unlock;
6835         }
6836
6837         sd = rcu_dereference(per_cpu(sd_asym, cpu));
6838
6839         if (sd && (cpumask_first_and(nohz.idle_cpus_mask,
6840                                   sched_domain_span(sd)) < cpu))
6841                 goto need_kick_unlock;
6842
6843         rcu_read_unlock();
6844         return 0;
6845
6846 need_kick_unlock:
6847         rcu_read_unlock();
6848 need_kick:
6849         return 1;
6850 }
6851 #else
6852 static void nohz_idle_balance(int this_cpu, enum cpu_idle_type idle) { }
6853 #endif
6854
6855 /*
6856  * run_rebalance_domains is triggered when needed from the scheduler tick.
6857  * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
6858  */
6859 static void run_rebalance_domains(struct softirq_action *h)
6860 {
6861         int this_cpu = smp_processor_id();
6862         struct rq *this_rq = cpu_rq(this_cpu);
6863         enum cpu_idle_type idle = this_rq->idle_balance ?
6864                                                 CPU_IDLE : CPU_NOT_IDLE;
6865
6866         rebalance_domains(this_cpu, idle);
6867
6868         /*
6869          * If this cpu has a pending nohz_balance_kick, then do the
6870          * balancing on behalf of the other idle cpus whose ticks are
6871          * stopped.
6872          */
6873         nohz_idle_balance(this_cpu, idle);
6874 }
6875
6876 static inline int on_null_domain(int cpu)
6877 {
6878         return !rcu_dereference_sched(cpu_rq(cpu)->sd);
6879 }
6880
6881 /*
6882  * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
6883  */
6884 void trigger_load_balance(struct rq *rq, int cpu)
6885 {
6886         /* Don't need to rebalance while attached to NULL domain */
6887         if (time_after_eq(jiffies, rq->next_balance) &&
6888             likely(!on_null_domain(cpu)))
6889                 raise_softirq(SCHED_SOFTIRQ);
6890 #ifdef CONFIG_NO_HZ_COMMON
6891         if (nohz_kick_needed(rq, cpu) && likely(!on_null_domain(cpu)))
6892                 nohz_balancer_kick(cpu);
6893 #endif
6894 }
6895
6896 static void rq_online_fair(struct rq *rq)
6897 {
6898         update_sysctl();
6899 }
6900
6901 static void rq_offline_fair(struct rq *rq)
6902 {
6903         update_sysctl();
6904
6905         /* Ensure any throttled groups are reachable by pick_next_task */
6906         unthrottle_offline_cfs_rqs(rq);
6907 }
6908
6909 #endif /* CONFIG_SMP */
6910
6911 /*
6912  * scheduler tick hitting a task of our scheduling class:
6913  */
6914 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
6915 {
6916         struct cfs_rq *cfs_rq;
6917         struct sched_entity *se = &curr->se;
6918
6919         for_each_sched_entity(se) {
6920                 cfs_rq = cfs_rq_of(se);
6921                 entity_tick(cfs_rq, se, queued);
6922         }
6923
6924         if (numabalancing_enabled)
6925                 task_tick_numa(rq, curr);
6926
6927         update_rq_runnable_avg(rq, 1);
6928 }
6929
6930 /*
6931  * called on fork with the child task as argument from the parent's context
6932  *  - child not yet on the tasklist
6933  *  - preemption disabled
6934  */
6935 static void task_fork_fair(struct task_struct *p)
6936 {
6937         struct cfs_rq *cfs_rq;
6938         struct sched_entity *se = &p->se, *curr;
6939         int this_cpu = smp_processor_id();
6940         struct rq *rq = this_rq();
6941         unsigned long flags;
6942
6943         raw_spin_lock_irqsave(&rq->lock, flags);
6944
6945         update_rq_clock(rq);
6946
6947         cfs_rq = task_cfs_rq(current);
6948         curr = cfs_rq->curr;
6949
6950         /*
6951          * Not only the cpu but also the task_group of the parent might have
6952          * been changed after parent->se.parent,cfs_rq were copied to
6953          * child->se.parent,cfs_rq. So call __set_task_cpu() to make those
6954          * of child point to valid ones.
6955          */
6956         rcu_read_lock();
6957         __set_task_cpu(p, this_cpu);
6958         rcu_read_unlock();
6959
6960         update_curr(cfs_rq);
6961
6962         if (curr)
6963                 se->vruntime = curr->vruntime;
6964         place_entity(cfs_rq, se, 1);
6965
6966         if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
6967                 /*
6968                  * Upon rescheduling, sched_class::put_prev_task() will place
6969                  * 'current' within the tree based on its new key value.
6970                  */
6971                 swap(curr->vruntime, se->vruntime);
6972                 resched_task(rq->curr);
6973         }
6974
6975         se->vruntime -= cfs_rq->min_vruntime;
6976
6977         raw_spin_unlock_irqrestore(&rq->lock, flags);
6978 }
6979
6980 /*
6981  * Priority of the task has changed. Check to see if we preempt
6982  * the current task.
6983  */
6984 static void
6985 prio_changed_fair(struct rq *rq, struct task_struct *p, int oldprio)
6986 {
6987         if (!p->se.on_rq)
6988                 return;
6989
6990         /*
6991          * Reschedule if we are currently running on this runqueue and
6992          * our priority decreased, or if we are not currently running on
6993          * this runqueue and our priority is higher than the current's
6994          */
6995         if (rq->curr == p) {
6996                 if (p->prio > oldprio)
6997                         resched_task(rq->curr);
6998         } else
6999                 check_preempt_curr(rq, p, 0);
7000 }
7001
7002 static void switched_from_fair(struct rq *rq, struct task_struct *p)
7003 {
7004         struct sched_entity *se = &p->se;
7005         struct cfs_rq *cfs_rq = cfs_rq_of(se);
7006
7007         /*
7008          * Ensure the task's vruntime is normalized, so that when its
7009          * switched back to the fair class the enqueue_entity(.flags=0) will
7010          * do the right thing.
7011          *
7012          * If it was on_rq, then the dequeue_entity(.flags=0) will already
7013          * have normalized the vruntime, if it was !on_rq, then only when
7014          * the task is sleeping will it still have non-normalized vruntime.
7015          */
7016         if (!se->on_rq && p->state != TASK_RUNNING) {
7017                 /*
7018                  * Fix up our vruntime so that the current sleep doesn't
7019                  * cause 'unlimited' sleep bonus.
7020                  */
7021                 place_entity(cfs_rq, se, 0);
7022                 se->vruntime -= cfs_rq->min_vruntime;
7023         }
7024
7025 #ifdef CONFIG_SMP
7026         /*
7027         * Remove our load from contribution when we leave sched_fair
7028         * and ensure we don't carry in an old decay_count if we
7029         * switch back.
7030         */
7031         if (se->avg.decay_count) {
7032                 __synchronize_entity_decay(se);
7033                 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
7034         }
7035 #endif
7036 }
7037
7038 /*
7039  * We switched to the sched_fair class.
7040  */
7041 static void switched_to_fair(struct rq *rq, struct task_struct *p)
7042 {
7043         if (!p->se.on_rq)
7044                 return;
7045
7046         /*
7047          * We were most likely switched from sched_rt, so
7048          * kick off the schedule if running, otherwise just see
7049          * if we can still preempt the current task.
7050          */
7051         if (rq->curr == p)
7052                 resched_task(rq->curr);
7053         else
7054                 check_preempt_curr(rq, p, 0);
7055 }
7056
7057 /* Account for a task changing its policy or group.
7058  *
7059  * This routine is mostly called to set cfs_rq->curr field when a task
7060  * migrates between groups/classes.
7061  */
7062 static void set_curr_task_fair(struct rq *rq)
7063 {
7064         struct sched_entity *se = &rq->curr->se;
7065
7066         for_each_sched_entity(se) {
7067                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
7068
7069                 set_next_entity(cfs_rq, se);
7070                 /* ensure bandwidth has been allocated on our new cfs_rq */
7071                 account_cfs_rq_runtime(cfs_rq, 0);
7072         }
7073 }
7074
7075 void init_cfs_rq(struct cfs_rq *cfs_rq)
7076 {
7077         cfs_rq->tasks_timeline = RB_ROOT;
7078         cfs_rq->min_vruntime = (u64)(-(1LL << 20));
7079 #ifndef CONFIG_64BIT
7080         cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
7081 #endif
7082 #ifdef CONFIG_SMP
7083         atomic64_set(&cfs_rq->decay_counter, 1);
7084         atomic_long_set(&cfs_rq->removed_load, 0);
7085 #endif
7086 }
7087
7088 #ifdef CONFIG_FAIR_GROUP_SCHED
7089 static void task_move_group_fair(struct task_struct *p, int on_rq)
7090 {
7091         struct cfs_rq *cfs_rq;
7092         /*
7093          * If the task was not on the rq at the time of this cgroup movement
7094          * it must have been asleep, sleeping tasks keep their ->vruntime
7095          * absolute on their old rq until wakeup (needed for the fair sleeper
7096          * bonus in place_entity()).
7097          *
7098          * If it was on the rq, we've just 'preempted' it, which does convert
7099          * ->vruntime to a relative base.
7100          *
7101          * Make sure both cases convert their relative position when migrating
7102          * to another cgroup's rq. This does somewhat interfere with the
7103          * fair sleeper stuff for the first placement, but who cares.
7104          */
7105         /*
7106          * When !on_rq, vruntime of the task has usually NOT been normalized.
7107          * But there are some cases where it has already been normalized:
7108          *
7109          * - Moving a forked child which is waiting for being woken up by
7110          *   wake_up_new_task().
7111          * - Moving a task which has been woken up by try_to_wake_up() and
7112          *   waiting for actually being woken up by sched_ttwu_pending().
7113          *
7114          * To prevent boost or penalty in the new cfs_rq caused by delta
7115          * min_vruntime between the two cfs_rqs, we skip vruntime adjustment.
7116          */
7117         if (!on_rq && (!p->se.sum_exec_runtime || p->state == TASK_WAKING))
7118                 on_rq = 1;
7119
7120         if (!on_rq)
7121                 p->se.vruntime -= cfs_rq_of(&p->se)->min_vruntime;
7122         set_task_rq(p, task_cpu(p));
7123         if (!on_rq) {
7124                 cfs_rq = cfs_rq_of(&p->se);
7125                 p->se.vruntime += cfs_rq->min_vruntime;
7126 #ifdef CONFIG_SMP
7127                 /*
7128                  * migrate_task_rq_fair() will have removed our previous
7129                  * contribution, but we must synchronize for ongoing future
7130                  * decay.
7131                  */
7132                 p->se.avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
7133                 cfs_rq->blocked_load_avg += p->se.avg.load_avg_contrib;
7134 #endif
7135         }
7136 }
7137
7138 void free_fair_sched_group(struct task_group *tg)
7139 {
7140         int i;
7141
7142         destroy_cfs_bandwidth(tg_cfs_bandwidth(tg));
7143
7144         for_each_possible_cpu(i) {
7145                 if (tg->cfs_rq)
7146                         kfree(tg->cfs_rq[i]);
7147                 if (tg->se)
7148                         kfree(tg->se[i]);
7149         }
7150
7151         kfree(tg->cfs_rq);
7152         kfree(tg->se);
7153 }
7154
7155 int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
7156 {
7157         struct cfs_rq *cfs_rq;
7158         struct sched_entity *se;
7159         int i;
7160
7161         tg->cfs_rq = kzalloc(sizeof(cfs_rq) * nr_cpu_ids, GFP_KERNEL);
7162         if (!tg->cfs_rq)
7163                 goto err;
7164         tg->se = kzalloc(sizeof(se) * nr_cpu_ids, GFP_KERNEL);
7165         if (!tg->se)
7166                 goto err;
7167
7168         tg->shares = NICE_0_LOAD;
7169
7170         init_cfs_bandwidth(tg_cfs_bandwidth(tg));
7171
7172         for_each_possible_cpu(i) {
7173                 cfs_rq = kzalloc_node(sizeof(struct cfs_rq),
7174                                       GFP_KERNEL, cpu_to_node(i));
7175                 if (!cfs_rq)
7176                         goto err;
7177
7178                 se = kzalloc_node(sizeof(struct sched_entity),
7179                                   GFP_KERNEL, cpu_to_node(i));
7180                 if (!se)
7181                         goto err_free_rq;
7182
7183                 init_cfs_rq(cfs_rq);
7184                 init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]);
7185         }
7186
7187         return 1;
7188
7189 err_free_rq:
7190         kfree(cfs_rq);
7191 err:
7192         return 0;
7193 }
7194
7195 void unregister_fair_sched_group(struct task_group *tg, int cpu)
7196 {
7197         struct rq *rq = cpu_rq(cpu);
7198         unsigned long flags;
7199
7200         /*
7201         * Only empty task groups can be destroyed; so we can speculatively
7202         * check on_list without danger of it being re-added.
7203         */
7204         if (!tg->cfs_rq[cpu]->on_list)
7205                 return;
7206
7207         raw_spin_lock_irqsave(&rq->lock, flags);
7208         list_del_leaf_cfs_rq(tg->cfs_rq[cpu]);
7209         raw_spin_unlock_irqrestore(&rq->lock, flags);
7210 }
7211
7212 void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
7213                         struct sched_entity *se, int cpu,
7214                         struct sched_entity *parent)
7215 {
7216         struct rq *rq = cpu_rq(cpu);
7217
7218         cfs_rq->tg = tg;
7219         cfs_rq->rq = rq;
7220         init_cfs_rq_runtime(cfs_rq);
7221
7222         tg->cfs_rq[cpu] = cfs_rq;
7223         tg->se[cpu] = se;
7224
7225         /* se could be NULL for root_task_group */
7226         if (!se)
7227                 return;
7228
7229         if (!parent)
7230                 se->cfs_rq = &rq->cfs;
7231         else
7232                 se->cfs_rq = parent->my_q;
7233
7234         se->my_q = cfs_rq;
7235         /* guarantee group entities always have weight */
7236         update_load_set(&se->load, NICE_0_LOAD);
7237         se->parent = parent;
7238 }
7239
7240 static DEFINE_MUTEX(shares_mutex);
7241
7242 int sched_group_set_shares(struct task_group *tg, unsigned long shares)
7243 {
7244         int i;
7245         unsigned long flags;
7246
7247         /*
7248          * We can't change the weight of the root cgroup.
7249          */
7250         if (!tg->se[0])
7251                 return -EINVAL;
7252
7253         shares = clamp(shares, scale_load(MIN_SHARES), scale_load(MAX_SHARES));
7254
7255         mutex_lock(&shares_mutex);
7256         if (tg->shares == shares)
7257                 goto done;
7258
7259         tg->shares = shares;
7260         for_each_possible_cpu(i) {
7261                 struct rq *rq = cpu_rq(i);
7262                 struct sched_entity *se;
7263
7264                 se = tg->se[i];
7265                 /* Propagate contribution to hierarchy */
7266                 raw_spin_lock_irqsave(&rq->lock, flags);
7267
7268                 /* Possible calls to update_curr() need rq clock */
7269                 update_rq_clock(rq);
7270                 for_each_sched_entity(se)
7271                         update_cfs_shares(group_cfs_rq(se));
7272                 raw_spin_unlock_irqrestore(&rq->lock, flags);
7273         }
7274
7275 done:
7276         mutex_unlock(&shares_mutex);
7277         return 0;
7278 }
7279 #else /* CONFIG_FAIR_GROUP_SCHED */
7280
7281 void free_fair_sched_group(struct task_group *tg) { }
7282
7283 int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
7284 {
7285         return 1;
7286 }
7287
7288 void unregister_fair_sched_group(struct task_group *tg, int cpu) { }
7289
7290 #endif /* CONFIG_FAIR_GROUP_SCHED */
7291
7292
7293 static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
7294 {
7295         struct sched_entity *se = &task->se;
7296         unsigned int rr_interval = 0;
7297
7298         /*
7299          * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
7300          * idle runqueue:
7301          */
7302         if (rq->cfs.load.weight)
7303                 rr_interval = NS_TO_JIFFIES(sched_slice(cfs_rq_of(se), se));
7304
7305         return rr_interval;
7306 }
7307
7308 /*
7309  * All the scheduling class methods:
7310  */
7311 const struct sched_class fair_sched_class = {
7312         .next                   = &idle_sched_class,
7313         .enqueue_task           = enqueue_task_fair,
7314         .dequeue_task           = dequeue_task_fair,
7315         .yield_task             = yield_task_fair,
7316         .yield_to_task          = yield_to_task_fair,
7317
7318         .check_preempt_curr     = check_preempt_wakeup,
7319
7320         .pick_next_task         = pick_next_task_fair,
7321         .put_prev_task          = put_prev_task_fair,
7322
7323 #ifdef CONFIG_SMP
7324         .select_task_rq         = select_task_rq_fair,
7325         .migrate_task_rq        = migrate_task_rq_fair,
7326
7327         .rq_online              = rq_online_fair,
7328         .rq_offline             = rq_offline_fair,
7329
7330         .task_waking            = task_waking_fair,
7331 #endif
7332
7333         .set_curr_task          = set_curr_task_fair,
7334         .task_tick              = task_tick_fair,
7335         .task_fork              = task_fork_fair,
7336
7337         .prio_changed           = prio_changed_fair,
7338         .switched_from          = switched_from_fair,
7339         .switched_to            = switched_to_fair,
7340
7341         .get_rr_interval        = get_rr_interval_fair,
7342
7343 #ifdef CONFIG_FAIR_GROUP_SCHED
7344         .task_move_group        = task_move_group_fair,
7345 #endif
7346 };
7347
7348 #ifdef CONFIG_SCHED_DEBUG
7349 void print_cfs_stats(struct seq_file *m, int cpu)
7350 {
7351         struct cfs_rq *cfs_rq;
7352
7353         rcu_read_lock();
7354         for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
7355                 print_cfs_rq(m, cpu, cfs_rq);
7356         rcu_read_unlock();
7357 }
7358 #endif
7359
7360 __init void init_sched_fair_class(void)
7361 {
7362 #ifdef CONFIG_SMP
7363         open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
7364
7365 #ifdef CONFIG_NO_HZ_COMMON
7366         nohz.next_balance = jiffies;
7367         zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
7368         cpu_notifier(sched_ilb_notifier, 0);
7369 #endif
7370 #endif /* SMP */
7371
7372 }