Version:  2.6.34 2.6.35 2.6.36 2.6.37 2.6.38 2.6.39 3.0 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14

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

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us