~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/kernel/sched/fair.c

Version: ~ [ linux-5.4-rc7 ] ~ [ linux-5.3.10 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.83 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.153 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.200 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.200 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.76 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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