Merge branch 'sched-urgent-for-linus' of git://git.kernel.org/pub/scm/linux/kernel...
[sfrench/cifs-2.6.git] / kernel / sched / fair.c
1 /*
2  * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
3  *
4  *  Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
5  *
6  *  Interactivity improvements by Mike Galbraith
7  *  (C) 2007 Mike Galbraith <efault@gmx.de>
8  *
9  *  Various enhancements by Dmitry Adamushko.
10  *  (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
11  *
12  *  Group scheduling enhancements by Srivatsa Vaddagiri
13  *  Copyright IBM Corporation, 2007
14  *  Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
15  *
16  *  Scaled math optimizations by Thomas Gleixner
17  *  Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
18  *
19  *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
20  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
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 /*
118  * The margin used when comparing utilization with CPU capacity:
119  * util * 1024 < capacity * margin
120  */
121 unsigned int capacity_margin = 1280; /* ~20% */
122
123 static inline void update_load_add(struct load_weight *lw, unsigned long inc)
124 {
125         lw->weight += inc;
126         lw->inv_weight = 0;
127 }
128
129 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
130 {
131         lw->weight -= dec;
132         lw->inv_weight = 0;
133 }
134
135 static inline void update_load_set(struct load_weight *lw, unsigned long w)
136 {
137         lw->weight = w;
138         lw->inv_weight = 0;
139 }
140
141 /*
142  * Increase the granularity value when there are more CPUs,
143  * because with more CPUs the 'effective latency' as visible
144  * to users decreases. But the relationship is not linear,
145  * so pick a second-best guess by going with the log2 of the
146  * number of CPUs.
147  *
148  * This idea comes from the SD scheduler of Con Kolivas:
149  */
150 static unsigned int get_update_sysctl_factor(void)
151 {
152         unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
153         unsigned int factor;
154
155         switch (sysctl_sched_tunable_scaling) {
156         case SCHED_TUNABLESCALING_NONE:
157                 factor = 1;
158                 break;
159         case SCHED_TUNABLESCALING_LINEAR:
160                 factor = cpus;
161                 break;
162         case SCHED_TUNABLESCALING_LOG:
163         default:
164                 factor = 1 + ilog2(cpus);
165                 break;
166         }
167
168         return factor;
169 }
170
171 static void update_sysctl(void)
172 {
173         unsigned int factor = get_update_sysctl_factor();
174
175 #define SET_SYSCTL(name) \
176         (sysctl_##name = (factor) * normalized_sysctl_##name)
177         SET_SYSCTL(sched_min_granularity);
178         SET_SYSCTL(sched_latency);
179         SET_SYSCTL(sched_wakeup_granularity);
180 #undef SET_SYSCTL
181 }
182
183 void sched_init_granularity(void)
184 {
185         update_sysctl();
186 }
187
188 #define WMULT_CONST     (~0U)
189 #define WMULT_SHIFT     32
190
191 static void __update_inv_weight(struct load_weight *lw)
192 {
193         unsigned long w;
194
195         if (likely(lw->inv_weight))
196                 return;
197
198         w = scale_load_down(lw->weight);
199
200         if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
201                 lw->inv_weight = 1;
202         else if (unlikely(!w))
203                 lw->inv_weight = WMULT_CONST;
204         else
205                 lw->inv_weight = WMULT_CONST / w;
206 }
207
208 /*
209  * delta_exec * weight / lw.weight
210  *   OR
211  * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
212  *
213  * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case
214  * we're guaranteed shift stays positive because inv_weight is guaranteed to
215  * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
216  *
217  * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
218  * weight/lw.weight <= 1, and therefore our shift will also be positive.
219  */
220 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
221 {
222         u64 fact = scale_load_down(weight);
223         int shift = WMULT_SHIFT;
224
225         __update_inv_weight(lw);
226
227         if (unlikely(fact >> 32)) {
228                 while (fact >> 32) {
229                         fact >>= 1;
230                         shift--;
231                 }
232         }
233
234         /* hint to use a 32x32->64 mul */
235         fact = (u64)(u32)fact * lw->inv_weight;
236
237         while (fact >> 32) {
238                 fact >>= 1;
239                 shift--;
240         }
241
242         return mul_u64_u32_shr(delta_exec, fact, shift);
243 }
244
245
246 const struct sched_class fair_sched_class;
247
248 /**************************************************************
249  * CFS operations on generic schedulable entities:
250  */
251
252 #ifdef CONFIG_FAIR_GROUP_SCHED
253
254 /* cpu runqueue to which this cfs_rq is attached */
255 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
256 {
257         return cfs_rq->rq;
258 }
259
260 /* An entity is a task if it doesn't "own" a runqueue */
261 #define entity_is_task(se)      (!se->my_q)
262
263 static inline struct task_struct *task_of(struct sched_entity *se)
264 {
265         SCHED_WARN_ON(!entity_is_task(se));
266         return container_of(se, struct task_struct, se);
267 }
268
269 /* Walk up scheduling entities hierarchy */
270 #define for_each_sched_entity(se) \
271                 for (; se; se = se->parent)
272
273 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
274 {
275         return p->se.cfs_rq;
276 }
277
278 /* runqueue on which this entity is (to be) queued */
279 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
280 {
281         return se->cfs_rq;
282 }
283
284 /* runqueue "owned" by this group */
285 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
286 {
287         return grp->my_q;
288 }
289
290 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
291 {
292         if (!cfs_rq->on_list) {
293                 /*
294                  * Ensure we either appear before our parent (if already
295                  * enqueued) or force our parent to appear after us when it is
296                  * enqueued.  The fact that we always enqueue bottom-up
297                  * reduces this to two cases.
298                  */
299                 if (cfs_rq->tg->parent &&
300                     cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
301                         list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
302                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
303                 } else {
304                         list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
305                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
306                 }
307
308                 cfs_rq->on_list = 1;
309         }
310 }
311
312 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
313 {
314         if (cfs_rq->on_list) {
315                 list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
316                 cfs_rq->on_list = 0;
317         }
318 }
319
320 /* Iterate thr' all leaf cfs_rq's on a runqueue */
321 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
322         list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
323
324 /* Do the two (enqueued) entities belong to the same group ? */
325 static inline struct cfs_rq *
326 is_same_group(struct sched_entity *se, struct sched_entity *pse)
327 {
328         if (se->cfs_rq == pse->cfs_rq)
329                 return se->cfs_rq;
330
331         return NULL;
332 }
333
334 static inline struct sched_entity *parent_entity(struct sched_entity *se)
335 {
336         return se->parent;
337 }
338
339 static void
340 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
341 {
342         int se_depth, pse_depth;
343
344         /*
345          * preemption test can be made between sibling entities who are in the
346          * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
347          * both tasks until we find their ancestors who are siblings of common
348          * parent.
349          */
350
351         /* First walk up until both entities are at same depth */
352         se_depth = (*se)->depth;
353         pse_depth = (*pse)->depth;
354
355         while (se_depth > pse_depth) {
356                 se_depth--;
357                 *se = parent_entity(*se);
358         }
359
360         while (pse_depth > se_depth) {
361                 pse_depth--;
362                 *pse = parent_entity(*pse);
363         }
364
365         while (!is_same_group(*se, *pse)) {
366                 *se = parent_entity(*se);
367                 *pse = parent_entity(*pse);
368         }
369 }
370
371 #else   /* !CONFIG_FAIR_GROUP_SCHED */
372
373 static inline struct task_struct *task_of(struct sched_entity *se)
374 {
375         return container_of(se, struct task_struct, se);
376 }
377
378 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
379 {
380         return container_of(cfs_rq, struct rq, cfs);
381 }
382
383 #define entity_is_task(se)      1
384
385 #define for_each_sched_entity(se) \
386                 for (; se; se = NULL)
387
388 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
389 {
390         return &task_rq(p)->cfs;
391 }
392
393 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
394 {
395         struct task_struct *p = task_of(se);
396         struct rq *rq = task_rq(p);
397
398         return &rq->cfs;
399 }
400
401 /* runqueue "owned" by this group */
402 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
403 {
404         return NULL;
405 }
406
407 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
408 {
409 }
410
411 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
412 {
413 }
414
415 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
416                 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
417
418 static inline struct sched_entity *parent_entity(struct sched_entity *se)
419 {
420         return NULL;
421 }
422
423 static inline void
424 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
425 {
426 }
427
428 #endif  /* CONFIG_FAIR_GROUP_SCHED */
429
430 static __always_inline
431 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);
432
433 /**************************************************************
434  * Scheduling class tree data structure manipulation methods:
435  */
436
437 static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
438 {
439         s64 delta = (s64)(vruntime - max_vruntime);
440         if (delta > 0)
441                 max_vruntime = vruntime;
442
443         return max_vruntime;
444 }
445
446 static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
447 {
448         s64 delta = (s64)(vruntime - min_vruntime);
449         if (delta < 0)
450                 min_vruntime = vruntime;
451
452         return min_vruntime;
453 }
454
455 static inline int entity_before(struct sched_entity *a,
456                                 struct sched_entity *b)
457 {
458         return (s64)(a->vruntime - b->vruntime) < 0;
459 }
460
461 static void update_min_vruntime(struct cfs_rq *cfs_rq)
462 {
463         struct sched_entity *curr = cfs_rq->curr;
464
465         u64 vruntime = cfs_rq->min_vruntime;
466
467         if (curr) {
468                 if (curr->on_rq)
469                         vruntime = curr->vruntime;
470                 else
471                         curr = NULL;
472         }
473
474         if (cfs_rq->rb_leftmost) {
475                 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
476                                                    struct sched_entity,
477                                                    run_node);
478
479                 if (!curr)
480                         vruntime = se->vruntime;
481                 else
482                         vruntime = min_vruntime(vruntime, se->vruntime);
483         }
484
485         /* ensure we never gain time by being placed backwards. */
486         cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
487 #ifndef CONFIG_64BIT
488         smp_wmb();
489         cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
490 #endif
491 }
492
493 /*
494  * Enqueue an entity into the rb-tree:
495  */
496 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
497 {
498         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
499         struct rb_node *parent = NULL;
500         struct sched_entity *entry;
501         int leftmost = 1;
502
503         /*
504          * Find the right place in the rbtree:
505          */
506         while (*link) {
507                 parent = *link;
508                 entry = rb_entry(parent, struct sched_entity, run_node);
509                 /*
510                  * We dont care about collisions. Nodes with
511                  * the same key stay together.
512                  */
513                 if (entity_before(se, entry)) {
514                         link = &parent->rb_left;
515                 } else {
516                         link = &parent->rb_right;
517                         leftmost = 0;
518                 }
519         }
520
521         /*
522          * Maintain a cache of leftmost tree entries (it is frequently
523          * used):
524          */
525         if (leftmost)
526                 cfs_rq->rb_leftmost = &se->run_node;
527
528         rb_link_node(&se->run_node, parent, link);
529         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
530 }
531
532 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
533 {
534         if (cfs_rq->rb_leftmost == &se->run_node) {
535                 struct rb_node *next_node;
536
537                 next_node = rb_next(&se->run_node);
538                 cfs_rq->rb_leftmost = next_node;
539         }
540
541         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
542 }
543
544 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
545 {
546         struct rb_node *left = cfs_rq->rb_leftmost;
547
548         if (!left)
549                 return NULL;
550
551         return rb_entry(left, struct sched_entity, run_node);
552 }
553
554 static struct sched_entity *__pick_next_entity(struct sched_entity *se)
555 {
556         struct rb_node *next = rb_next(&se->run_node);
557
558         if (!next)
559                 return NULL;
560
561         return rb_entry(next, struct sched_entity, run_node);
562 }
563
564 #ifdef CONFIG_SCHED_DEBUG
565 struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
566 {
567         struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
568
569         if (!last)
570                 return NULL;
571
572         return rb_entry(last, struct sched_entity, run_node);
573 }
574
575 /**************************************************************
576  * Scheduling class statistics methods:
577  */
578
579 int sched_proc_update_handler(struct ctl_table *table, int write,
580                 void __user *buffer, size_t *lenp,
581                 loff_t *ppos)
582 {
583         int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
584         unsigned int factor = get_update_sysctl_factor();
585
586         if (ret || !write)
587                 return ret;
588
589         sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
590                                         sysctl_sched_min_granularity);
591
592 #define WRT_SYSCTL(name) \
593         (normalized_sysctl_##name = sysctl_##name / (factor))
594         WRT_SYSCTL(sched_min_granularity);
595         WRT_SYSCTL(sched_latency);
596         WRT_SYSCTL(sched_wakeup_granularity);
597 #undef WRT_SYSCTL
598
599         return 0;
600 }
601 #endif
602
603 /*
604  * delta /= w
605  */
606 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
607 {
608         if (unlikely(se->load.weight != NICE_0_LOAD))
609                 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
610
611         return delta;
612 }
613
614 /*
615  * The idea is to set a period in which each task runs once.
616  *
617  * When there are too many tasks (sched_nr_latency) we have to stretch
618  * this period because otherwise the slices get too small.
619  *
620  * p = (nr <= nl) ? l : l*nr/nl
621  */
622 static u64 __sched_period(unsigned long nr_running)
623 {
624         if (unlikely(nr_running > sched_nr_latency))
625                 return nr_running * sysctl_sched_min_granularity;
626         else
627                 return sysctl_sched_latency;
628 }
629
630 /*
631  * We calculate the wall-time slice from the period by taking a part
632  * proportional to the weight.
633  *
634  * s = p*P[w/rw]
635  */
636 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
637 {
638         u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
639
640         for_each_sched_entity(se) {
641                 struct load_weight *load;
642                 struct load_weight lw;
643
644                 cfs_rq = cfs_rq_of(se);
645                 load = &cfs_rq->load;
646
647                 if (unlikely(!se->on_rq)) {
648                         lw = cfs_rq->load;
649
650                         update_load_add(&lw, se->load.weight);
651                         load = &lw;
652                 }
653                 slice = __calc_delta(slice, se->load.weight, load);
654         }
655         return slice;
656 }
657
658 /*
659  * We calculate the vruntime slice of a to-be-inserted task.
660  *
661  * vs = s/w
662  */
663 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
664 {
665         return calc_delta_fair(sched_slice(cfs_rq, se), se);
666 }
667
668 #ifdef CONFIG_SMP
669 static int select_idle_sibling(struct task_struct *p, int prev_cpu, int cpu);
670 static unsigned long task_h_load(struct task_struct *p);
671
672 /*
673  * We choose a half-life close to 1 scheduling period.
674  * Note: The tables runnable_avg_yN_inv and runnable_avg_yN_sum are
675  * dependent on this value.
676  */
677 #define LOAD_AVG_PERIOD 32
678 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
679 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_AVG_MAX */
680
681 /* Give new sched_entity start runnable values to heavy its load in infant time */
682 void init_entity_runnable_average(struct sched_entity *se)
683 {
684         struct sched_avg *sa = &se->avg;
685
686         sa->last_update_time = 0;
687         /*
688          * sched_avg's period_contrib should be strictly less then 1024, so
689          * we give it 1023 to make sure it is almost a period (1024us), and
690          * will definitely be update (after enqueue).
691          */
692         sa->period_contrib = 1023;
693         sa->load_avg = scale_load_down(se->load.weight);
694         sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
695         /*
696          * At this point, util_avg won't be used in select_task_rq_fair anyway
697          */
698         sa->util_avg = 0;
699         sa->util_sum = 0;
700         /* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
701 }
702
703 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
704 static int update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq, bool update_freq);
705 static void update_tg_load_avg(struct cfs_rq *cfs_rq, int force);
706 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se);
707
708 /*
709  * With new tasks being created, their initial util_avgs are extrapolated
710  * based on the cfs_rq's current util_avg:
711  *
712  *   util_avg = cfs_rq->util_avg / (cfs_rq->load_avg + 1) * se.load.weight
713  *
714  * However, in many cases, the above util_avg does not give a desired
715  * value. Moreover, the sum of the util_avgs may be divergent, such
716  * as when the series is a harmonic series.
717  *
718  * To solve this problem, we also cap the util_avg of successive tasks to
719  * only 1/2 of the left utilization budget:
720  *
721  *   util_avg_cap = (1024 - cfs_rq->avg.util_avg) / 2^n
722  *
723  * where n denotes the nth task.
724  *
725  * For example, a simplest series from the beginning would be like:
726  *
727  *  task  util_avg: 512, 256, 128,  64,  32,   16,    8, ...
728  * cfs_rq util_avg: 512, 768, 896, 960, 992, 1008, 1016, ...
729  *
730  * Finally, that extrapolated util_avg is clamped to the cap (util_avg_cap)
731  * if util_avg > util_avg_cap.
732  */
733 void post_init_entity_util_avg(struct sched_entity *se)
734 {
735         struct cfs_rq *cfs_rq = cfs_rq_of(se);
736         struct sched_avg *sa = &se->avg;
737         long cap = (long)(SCHED_CAPACITY_SCALE - cfs_rq->avg.util_avg) / 2;
738         u64 now = cfs_rq_clock_task(cfs_rq);
739
740         if (cap > 0) {
741                 if (cfs_rq->avg.util_avg != 0) {
742                         sa->util_avg  = cfs_rq->avg.util_avg * se->load.weight;
743                         sa->util_avg /= (cfs_rq->avg.load_avg + 1);
744
745                         if (sa->util_avg > cap)
746                                 sa->util_avg = cap;
747                 } else {
748                         sa->util_avg = cap;
749                 }
750                 sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
751         }
752
753         if (entity_is_task(se)) {
754                 struct task_struct *p = task_of(se);
755                 if (p->sched_class != &fair_sched_class) {
756                         /*
757                          * For !fair tasks do:
758                          *
759                         update_cfs_rq_load_avg(now, cfs_rq, false);
760                         attach_entity_load_avg(cfs_rq, se);
761                         switched_from_fair(rq, p);
762                          *
763                          * such that the next switched_to_fair() has the
764                          * expected state.
765                          */
766                         se->avg.last_update_time = now;
767                         return;
768                 }
769         }
770
771         update_cfs_rq_load_avg(now, cfs_rq, false);
772         attach_entity_load_avg(cfs_rq, se);
773         update_tg_load_avg(cfs_rq, false);
774 }
775
776 #else /* !CONFIG_SMP */
777 void init_entity_runnable_average(struct sched_entity *se)
778 {
779 }
780 void post_init_entity_util_avg(struct sched_entity *se)
781 {
782 }
783 static void update_tg_load_avg(struct cfs_rq *cfs_rq, int force)
784 {
785 }
786 #endif /* CONFIG_SMP */
787
788 /*
789  * Update the current task's runtime statistics.
790  */
791 static void update_curr(struct cfs_rq *cfs_rq)
792 {
793         struct sched_entity *curr = cfs_rq->curr;
794         u64 now = rq_clock_task(rq_of(cfs_rq));
795         u64 delta_exec;
796
797         if (unlikely(!curr))
798                 return;
799
800         delta_exec = now - curr->exec_start;
801         if (unlikely((s64)delta_exec <= 0))
802                 return;
803
804         curr->exec_start = now;
805
806         schedstat_set(curr->statistics.exec_max,
807                       max(delta_exec, curr->statistics.exec_max));
808
809         curr->sum_exec_runtime += delta_exec;
810         schedstat_add(cfs_rq->exec_clock, delta_exec);
811
812         curr->vruntime += calc_delta_fair(delta_exec, curr);
813         update_min_vruntime(cfs_rq);
814
815         if (entity_is_task(curr)) {
816                 struct task_struct *curtask = task_of(curr);
817
818                 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
819                 cpuacct_charge(curtask, delta_exec);
820                 account_group_exec_runtime(curtask, delta_exec);
821         }
822
823         account_cfs_rq_runtime(cfs_rq, delta_exec);
824 }
825
826 static void update_curr_fair(struct rq *rq)
827 {
828         update_curr(cfs_rq_of(&rq->curr->se));
829 }
830
831 static inline void
832 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
833 {
834         u64 wait_start, prev_wait_start;
835
836         if (!schedstat_enabled())
837                 return;
838
839         wait_start = rq_clock(rq_of(cfs_rq));
840         prev_wait_start = schedstat_val(se->statistics.wait_start);
841
842         if (entity_is_task(se) && task_on_rq_migrating(task_of(se)) &&
843             likely(wait_start > prev_wait_start))
844                 wait_start -= prev_wait_start;
845
846         schedstat_set(se->statistics.wait_start, wait_start);
847 }
848
849 static inline 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         if (!schedstat_enabled())
856                 return;
857
858         delta = rq_clock(rq_of(cfs_rq)) - schedstat_val(se->statistics.wait_start);
859
860         if (entity_is_task(se)) {
861                 p = task_of(se);
862                 if (task_on_rq_migrating(p)) {
863                         /*
864                          * Preserve migrating task's wait time so wait_start
865                          * time stamp can be adjusted to accumulate wait time
866                          * prior to migration.
867                          */
868                         schedstat_set(se->statistics.wait_start, delta);
869                         return;
870                 }
871                 trace_sched_stat_wait(p, delta);
872         }
873
874         schedstat_set(se->statistics.wait_max,
875                       max(schedstat_val(se->statistics.wait_max), delta));
876         schedstat_inc(se->statistics.wait_count);
877         schedstat_add(se->statistics.wait_sum, delta);
878         schedstat_set(se->statistics.wait_start, 0);
879 }
880
881 static inline void
882 update_stats_enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
883 {
884         struct task_struct *tsk = NULL;
885         u64 sleep_start, block_start;
886
887         if (!schedstat_enabled())
888                 return;
889
890         sleep_start = schedstat_val(se->statistics.sleep_start);
891         block_start = schedstat_val(se->statistics.block_start);
892
893         if (entity_is_task(se))
894                 tsk = task_of(se);
895
896         if (sleep_start) {
897                 u64 delta = rq_clock(rq_of(cfs_rq)) - sleep_start;
898
899                 if ((s64)delta < 0)
900                         delta = 0;
901
902                 if (unlikely(delta > schedstat_val(se->statistics.sleep_max)))
903                         schedstat_set(se->statistics.sleep_max, delta);
904
905                 schedstat_set(se->statistics.sleep_start, 0);
906                 schedstat_add(se->statistics.sum_sleep_runtime, delta);
907
908                 if (tsk) {
909                         account_scheduler_latency(tsk, delta >> 10, 1);
910                         trace_sched_stat_sleep(tsk, delta);
911                 }
912         }
913         if (block_start) {
914                 u64 delta = rq_clock(rq_of(cfs_rq)) - block_start;
915
916                 if ((s64)delta < 0)
917                         delta = 0;
918
919                 if (unlikely(delta > schedstat_val(se->statistics.block_max)))
920                         schedstat_set(se->statistics.block_max, delta);
921
922                 schedstat_set(se->statistics.block_start, 0);
923                 schedstat_add(se->statistics.sum_sleep_runtime, delta);
924
925                 if (tsk) {
926                         if (tsk->in_iowait) {
927                                 schedstat_add(se->statistics.iowait_sum, delta);
928                                 schedstat_inc(se->statistics.iowait_count);
929                                 trace_sched_stat_iowait(tsk, delta);
930                         }
931
932                         trace_sched_stat_blocked(tsk, delta);
933
934                         /*
935                          * Blocking time is in units of nanosecs, so shift by
936                          * 20 to get a milliseconds-range estimation of the
937                          * amount of time that the task spent sleeping:
938                          */
939                         if (unlikely(prof_on == SLEEP_PROFILING)) {
940                                 profile_hits(SLEEP_PROFILING,
941                                                 (void *)get_wchan(tsk),
942                                                 delta >> 20);
943                         }
944                         account_scheduler_latency(tsk, delta >> 10, 0);
945                 }
946         }
947 }
948
949 /*
950  * Task is being enqueued - update stats:
951  */
952 static inline void
953 update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
954 {
955         if (!schedstat_enabled())
956                 return;
957
958         /*
959          * Are we enqueueing a waiting task? (for current tasks
960          * a dequeue/enqueue event is a NOP)
961          */
962         if (se != cfs_rq->curr)
963                 update_stats_wait_start(cfs_rq, se);
964
965         if (flags & ENQUEUE_WAKEUP)
966                 update_stats_enqueue_sleeper(cfs_rq, se);
967 }
968
969 static inline void
970 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
971 {
972
973         if (!schedstat_enabled())
974                 return;
975
976         /*
977          * Mark the end of the wait period if dequeueing a
978          * waiting task:
979          */
980         if (se != cfs_rq->curr)
981                 update_stats_wait_end(cfs_rq, se);
982
983         if ((flags & DEQUEUE_SLEEP) && entity_is_task(se)) {
984                 struct task_struct *tsk = task_of(se);
985
986                 if (tsk->state & TASK_INTERRUPTIBLE)
987                         schedstat_set(se->statistics.sleep_start,
988                                       rq_clock(rq_of(cfs_rq)));
989                 if (tsk->state & TASK_UNINTERRUPTIBLE)
990                         schedstat_set(se->statistics.block_start,
991                                       rq_clock(rq_of(cfs_rq)));
992         }
993 }
994
995 /*
996  * We are picking a new current task - update its stats:
997  */
998 static inline void
999 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
1000 {
1001         /*
1002          * We are starting a new run period:
1003          */
1004         se->exec_start = rq_clock_task(rq_of(cfs_rq));
1005 }
1006
1007 /**************************************************
1008  * Scheduling class queueing methods:
1009  */
1010
1011 #ifdef CONFIG_NUMA_BALANCING
1012 /*
1013  * Approximate time to scan a full NUMA task in ms. The task scan period is
1014  * calculated based on the tasks virtual memory size and
1015  * numa_balancing_scan_size.
1016  */
1017 unsigned int sysctl_numa_balancing_scan_period_min = 1000;
1018 unsigned int sysctl_numa_balancing_scan_period_max = 60000;
1019
1020 /* Portion of address space to scan in MB */
1021 unsigned int sysctl_numa_balancing_scan_size = 256;
1022
1023 /* Scan @scan_size MB every @scan_period after an initial @scan_delay in ms */
1024 unsigned int sysctl_numa_balancing_scan_delay = 1000;
1025
1026 static unsigned int task_nr_scan_windows(struct task_struct *p)
1027 {
1028         unsigned long rss = 0;
1029         unsigned long nr_scan_pages;
1030
1031         /*
1032          * Calculations based on RSS as non-present and empty pages are skipped
1033          * by the PTE scanner and NUMA hinting faults should be trapped based
1034          * on resident pages
1035          */
1036         nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT);
1037         rss = get_mm_rss(p->mm);
1038         if (!rss)
1039                 rss = nr_scan_pages;
1040
1041         rss = round_up(rss, nr_scan_pages);
1042         return rss / nr_scan_pages;
1043 }
1044
1045 /* For sanitys sake, never scan more PTEs than MAX_SCAN_WINDOW MB/sec. */
1046 #define MAX_SCAN_WINDOW 2560
1047
1048 static unsigned int task_scan_min(struct task_struct *p)
1049 {
1050         unsigned int scan_size = READ_ONCE(sysctl_numa_balancing_scan_size);
1051         unsigned int scan, floor;
1052         unsigned int windows = 1;
1053
1054         if (scan_size < MAX_SCAN_WINDOW)
1055                 windows = MAX_SCAN_WINDOW / scan_size;
1056         floor = 1000 / windows;
1057
1058         scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p);
1059         return max_t(unsigned int, floor, scan);
1060 }
1061
1062 static unsigned int task_scan_max(struct task_struct *p)
1063 {
1064         unsigned int smin = task_scan_min(p);
1065         unsigned int smax;
1066
1067         /* Watch for min being lower than max due to floor calculations */
1068         smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p);
1069         return max(smin, smax);
1070 }
1071
1072 static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
1073 {
1074         rq->nr_numa_running += (p->numa_preferred_nid != -1);
1075         rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
1076 }
1077
1078 static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
1079 {
1080         rq->nr_numa_running -= (p->numa_preferred_nid != -1);
1081         rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
1082 }
1083
1084 struct numa_group {
1085         atomic_t refcount;
1086
1087         spinlock_t lock; /* nr_tasks, tasks */
1088         int nr_tasks;
1089         pid_t gid;
1090         int active_nodes;
1091
1092         struct rcu_head rcu;
1093         unsigned long total_faults;
1094         unsigned long max_faults_cpu;
1095         /*
1096          * Faults_cpu is used to decide whether memory should move
1097          * towards the CPU. As a consequence, these stats are weighted
1098          * more by CPU use than by memory faults.
1099          */
1100         unsigned long *faults_cpu;
1101         unsigned long faults[0];
1102 };
1103
1104 /* Shared or private faults. */
1105 #define NR_NUMA_HINT_FAULT_TYPES 2
1106
1107 /* Memory and CPU locality */
1108 #define NR_NUMA_HINT_FAULT_STATS (NR_NUMA_HINT_FAULT_TYPES * 2)
1109
1110 /* Averaged statistics, and temporary buffers. */
1111 #define NR_NUMA_HINT_FAULT_BUCKETS (NR_NUMA_HINT_FAULT_STATS * 2)
1112
1113 pid_t task_numa_group_id(struct task_struct *p)
1114 {
1115         return p->numa_group ? p->numa_group->gid : 0;
1116 }
1117
1118 /*
1119  * The averaged statistics, shared & private, memory & cpu,
1120  * occupy the first half of the array. The second half of the
1121  * array is for current counters, which are averaged into the
1122  * first set by task_numa_placement.
1123  */
1124 static inline int task_faults_idx(enum numa_faults_stats s, int nid, int priv)
1125 {
1126         return NR_NUMA_HINT_FAULT_TYPES * (s * nr_node_ids + nid) + priv;
1127 }
1128
1129 static inline unsigned long task_faults(struct task_struct *p, int nid)
1130 {
1131         if (!p->numa_faults)
1132                 return 0;
1133
1134         return p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)] +
1135                 p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];
1136 }
1137
1138 static inline unsigned long group_faults(struct task_struct *p, int nid)
1139 {
1140         if (!p->numa_group)
1141                 return 0;
1142
1143         return p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 0)] +
1144                 p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 1)];
1145 }
1146
1147 static inline unsigned long group_faults_cpu(struct numa_group *group, int nid)
1148 {
1149         return group->faults_cpu[task_faults_idx(NUMA_MEM, nid, 0)] +
1150                 group->faults_cpu[task_faults_idx(NUMA_MEM, nid, 1)];
1151 }
1152
1153 /*
1154  * A node triggering more than 1/3 as many NUMA faults as the maximum is
1155  * considered part of a numa group's pseudo-interleaving set. Migrations
1156  * between these nodes are slowed down, to allow things to settle down.
1157  */
1158 #define ACTIVE_NODE_FRACTION 3
1159
1160 static bool numa_is_active_node(int nid, struct numa_group *ng)
1161 {
1162         return group_faults_cpu(ng, nid) * ACTIVE_NODE_FRACTION > ng->max_faults_cpu;
1163 }
1164
1165 /* Handle placement on systems where not all nodes are directly connected. */
1166 static unsigned long score_nearby_nodes(struct task_struct *p, int nid,
1167                                         int maxdist, bool task)
1168 {
1169         unsigned long score = 0;
1170         int node;
1171
1172         /*
1173          * All nodes are directly connected, and the same distance
1174          * from each other. No need for fancy placement algorithms.
1175          */
1176         if (sched_numa_topology_type == NUMA_DIRECT)
1177                 return 0;
1178
1179         /*
1180          * This code is called for each node, introducing N^2 complexity,
1181          * which should be ok given the number of nodes rarely exceeds 8.
1182          */
1183         for_each_online_node(node) {
1184                 unsigned long faults;
1185                 int dist = node_distance(nid, node);
1186
1187                 /*
1188                  * The furthest away nodes in the system are not interesting
1189                  * for placement; nid was already counted.
1190                  */
1191                 if (dist == sched_max_numa_distance || node == nid)
1192                         continue;
1193
1194                 /*
1195                  * On systems with a backplane NUMA topology, compare groups
1196                  * of nodes, and move tasks towards the group with the most
1197                  * memory accesses. When comparing two nodes at distance
1198                  * "hoplimit", only nodes closer by than "hoplimit" are part
1199                  * of each group. Skip other nodes.
1200                  */
1201                 if (sched_numa_topology_type == NUMA_BACKPLANE &&
1202                                         dist > maxdist)
1203                         continue;
1204
1205                 /* Add up the faults from nearby nodes. */
1206                 if (task)
1207                         faults = task_faults(p, node);
1208                 else
1209                         faults = group_faults(p, node);
1210
1211                 /*
1212                  * On systems with a glueless mesh NUMA topology, there are
1213                  * no fixed "groups of nodes". Instead, nodes that are not
1214                  * directly connected bounce traffic through intermediate
1215                  * nodes; a numa_group can occupy any set of nodes.
1216                  * The further away a node is, the less the faults count.
1217                  * This seems to result in good task placement.
1218                  */
1219                 if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
1220                         faults *= (sched_max_numa_distance - dist);
1221                         faults /= (sched_max_numa_distance - LOCAL_DISTANCE);
1222                 }
1223
1224                 score += faults;
1225         }
1226
1227         return score;
1228 }
1229
1230 /*
1231  * These return the fraction of accesses done by a particular task, or
1232  * task group, on a particular numa node.  The group weight is given a
1233  * larger multiplier, in order to group tasks together that are almost
1234  * evenly spread out between numa nodes.
1235  */
1236 static inline unsigned long task_weight(struct task_struct *p, int nid,
1237                                         int dist)
1238 {
1239         unsigned long faults, total_faults;
1240
1241         if (!p->numa_faults)
1242                 return 0;
1243
1244         total_faults = p->total_numa_faults;
1245
1246         if (!total_faults)
1247                 return 0;
1248
1249         faults = task_faults(p, nid);
1250         faults += score_nearby_nodes(p, nid, dist, true);
1251
1252         return 1000 * faults / total_faults;
1253 }
1254
1255 static inline unsigned long group_weight(struct task_struct *p, int nid,
1256                                          int dist)
1257 {
1258         unsigned long faults, total_faults;
1259
1260         if (!p->numa_group)
1261                 return 0;
1262
1263         total_faults = p->numa_group->total_faults;
1264
1265         if (!total_faults)
1266                 return 0;
1267
1268         faults = group_faults(p, nid);
1269         faults += score_nearby_nodes(p, nid, dist, false);
1270
1271         return 1000 * faults / total_faults;
1272 }
1273
1274 bool should_numa_migrate_memory(struct task_struct *p, struct page * page,
1275                                 int src_nid, int dst_cpu)
1276 {
1277         struct numa_group *ng = p->numa_group;
1278         int dst_nid = cpu_to_node(dst_cpu);
1279         int last_cpupid, this_cpupid;
1280
1281         this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
1282
1283         /*
1284          * Multi-stage node selection is used in conjunction with a periodic
1285          * migration fault to build a temporal task<->page relation. By using
1286          * a two-stage filter we remove short/unlikely relations.
1287          *
1288          * Using P(p) ~ n_p / n_t as per frequentist probability, we can equate
1289          * a task's usage of a particular page (n_p) per total usage of this
1290          * page (n_t) (in a given time-span) to a probability.
1291          *
1292          * Our periodic faults will sample this probability and getting the
1293          * same result twice in a row, given these samples are fully
1294          * independent, is then given by P(n)^2, provided our sample period
1295          * is sufficiently short compared to the usage pattern.
1296          *
1297          * This quadric squishes small probabilities, making it less likely we
1298          * act on an unlikely task<->page relation.
1299          */
1300         last_cpupid = page_cpupid_xchg_last(page, this_cpupid);
1301         if (!cpupid_pid_unset(last_cpupid) &&
1302                                 cpupid_to_nid(last_cpupid) != dst_nid)
1303                 return false;
1304
1305         /* Always allow migrate on private faults */
1306         if (cpupid_match_pid(p, last_cpupid))
1307                 return true;
1308
1309         /* A shared fault, but p->numa_group has not been set up yet. */
1310         if (!ng)
1311                 return true;
1312
1313         /*
1314          * Destination node is much more heavily used than the source
1315          * node? Allow migration.
1316          */
1317         if (group_faults_cpu(ng, dst_nid) > group_faults_cpu(ng, src_nid) *
1318                                         ACTIVE_NODE_FRACTION)
1319                 return true;
1320
1321         /*
1322          * Distribute memory according to CPU & memory use on each node,
1323          * with 3/4 hysteresis to avoid unnecessary memory migrations:
1324          *
1325          * faults_cpu(dst)   3   faults_cpu(src)
1326          * --------------- * - > ---------------
1327          * faults_mem(dst)   4   faults_mem(src)
1328          */
1329         return group_faults_cpu(ng, dst_nid) * group_faults(p, src_nid) * 3 >
1330                group_faults_cpu(ng, src_nid) * group_faults(p, dst_nid) * 4;
1331 }
1332
1333 static unsigned long weighted_cpuload(const int cpu);
1334 static unsigned long source_load(int cpu, int type);
1335 static unsigned long target_load(int cpu, int type);
1336 static unsigned long capacity_of(int cpu);
1337 static long effective_load(struct task_group *tg, int cpu, long wl, long wg);
1338
1339 /* Cached statistics for all CPUs within a node */
1340 struct numa_stats {
1341         unsigned long nr_running;
1342         unsigned long load;
1343
1344         /* Total compute capacity of CPUs on a node */
1345         unsigned long compute_capacity;
1346
1347         /* Approximate capacity in terms of runnable tasks on a node */
1348         unsigned long task_capacity;
1349         int has_free_capacity;
1350 };
1351
1352 /*
1353  * XXX borrowed from update_sg_lb_stats
1354  */
1355 static void update_numa_stats(struct numa_stats *ns, int nid)
1356 {
1357         int smt, cpu, cpus = 0;
1358         unsigned long capacity;
1359
1360         memset(ns, 0, sizeof(*ns));
1361         for_each_cpu(cpu, cpumask_of_node(nid)) {
1362                 struct rq *rq = cpu_rq(cpu);
1363
1364                 ns->nr_running += rq->nr_running;
1365                 ns->load += weighted_cpuload(cpu);
1366                 ns->compute_capacity += capacity_of(cpu);
1367
1368                 cpus++;
1369         }
1370
1371         /*
1372          * If we raced with hotplug and there are no CPUs left in our mask
1373          * the @ns structure is NULL'ed and task_numa_compare() will
1374          * not find this node attractive.
1375          *
1376          * We'll either bail at !has_free_capacity, or we'll detect a huge
1377          * imbalance and bail there.
1378          */
1379         if (!cpus)
1380                 return;
1381
1382         /* smt := ceil(cpus / capacity), assumes: 1 < smt_power < 2 */
1383         smt = DIV_ROUND_UP(SCHED_CAPACITY_SCALE * cpus, ns->compute_capacity);
1384         capacity = cpus / smt; /* cores */
1385
1386         ns->task_capacity = min_t(unsigned, capacity,
1387                 DIV_ROUND_CLOSEST(ns->compute_capacity, SCHED_CAPACITY_SCALE));
1388         ns->has_free_capacity = (ns->nr_running < ns->task_capacity);
1389 }
1390
1391 struct task_numa_env {
1392         struct task_struct *p;
1393
1394         int src_cpu, src_nid;
1395         int dst_cpu, dst_nid;
1396
1397         struct numa_stats src_stats, dst_stats;
1398
1399         int imbalance_pct;
1400         int dist;
1401
1402         struct task_struct *best_task;
1403         long best_imp;
1404         int best_cpu;
1405 };
1406
1407 static void task_numa_assign(struct task_numa_env *env,
1408                              struct task_struct *p, long imp)
1409 {
1410         if (env->best_task)
1411                 put_task_struct(env->best_task);
1412         if (p)
1413                 get_task_struct(p);
1414
1415         env->best_task = p;
1416         env->best_imp = imp;
1417         env->best_cpu = env->dst_cpu;
1418 }
1419
1420 static bool load_too_imbalanced(long src_load, long dst_load,
1421                                 struct task_numa_env *env)
1422 {
1423         long imb, old_imb;
1424         long orig_src_load, orig_dst_load;
1425         long src_capacity, dst_capacity;
1426
1427         /*
1428          * The load is corrected for the CPU capacity available on each node.
1429          *
1430          * src_load        dst_load
1431          * ------------ vs ---------
1432          * src_capacity    dst_capacity
1433          */
1434         src_capacity = env->src_stats.compute_capacity;
1435         dst_capacity = env->dst_stats.compute_capacity;
1436
1437         /* We care about the slope of the imbalance, not the direction. */
1438         if (dst_load < src_load)
1439                 swap(dst_load, src_load);
1440
1441         /* Is the difference below the threshold? */
1442         imb = dst_load * src_capacity * 100 -
1443               src_load * dst_capacity * env->imbalance_pct;
1444         if (imb <= 0)
1445                 return false;
1446
1447         /*
1448          * The imbalance is above the allowed threshold.
1449          * Compare it with the old imbalance.
1450          */
1451         orig_src_load = env->src_stats.load;
1452         orig_dst_load = env->dst_stats.load;
1453
1454         if (orig_dst_load < orig_src_load)
1455                 swap(orig_dst_load, orig_src_load);
1456
1457         old_imb = orig_dst_load * src_capacity * 100 -
1458                   orig_src_load * dst_capacity * env->imbalance_pct;
1459
1460         /* Would this change make things worse? */
1461         return (imb > old_imb);
1462 }
1463
1464 /*
1465  * This checks if the overall compute and NUMA accesses of the system would
1466  * be improved if the source tasks was migrated to the target dst_cpu taking
1467  * into account that it might be best if task running on the dst_cpu should
1468  * be exchanged with the source task
1469  */
1470 static void task_numa_compare(struct task_numa_env *env,
1471                               long taskimp, long groupimp)
1472 {
1473         struct rq *src_rq = cpu_rq(env->src_cpu);
1474         struct rq *dst_rq = cpu_rq(env->dst_cpu);
1475         struct task_struct *cur;
1476         long src_load, dst_load;
1477         long load;
1478         long imp = env->p->numa_group ? groupimp : taskimp;
1479         long moveimp = imp;
1480         int dist = env->dist;
1481
1482         rcu_read_lock();
1483         cur = task_rcu_dereference(&dst_rq->curr);
1484         if (cur && ((cur->flags & PF_EXITING) || is_idle_task(cur)))
1485                 cur = NULL;
1486
1487         /*
1488          * Because we have preemption enabled we can get migrated around and
1489          * end try selecting ourselves (current == env->p) as a swap candidate.
1490          */
1491         if (cur == env->p)
1492                 goto unlock;
1493
1494         /*
1495          * "imp" is the fault differential for the source task between the
1496          * source and destination node. Calculate the total differential for
1497          * the source task and potential destination task. The more negative
1498          * the value is, the more rmeote accesses that would be expected to
1499          * be incurred if the tasks were swapped.
1500          */
1501         if (cur) {
1502                 /* Skip this swap candidate if cannot move to the source cpu */
1503                 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
1504                         goto unlock;
1505
1506                 /*
1507                  * If dst and source tasks are in the same NUMA group, or not
1508                  * in any group then look only at task weights.
1509                  */
1510                 if (cur->numa_group == env->p->numa_group) {
1511                         imp = taskimp + task_weight(cur, env->src_nid, dist) -
1512                               task_weight(cur, env->dst_nid, dist);
1513                         /*
1514                          * Add some hysteresis to prevent swapping the
1515                          * tasks within a group over tiny differences.
1516                          */
1517                         if (cur->numa_group)
1518                                 imp -= imp/16;
1519                 } else {
1520                         /*
1521                          * Compare the group weights. If a task is all by
1522                          * itself (not part of a group), use the task weight
1523                          * instead.
1524                          */
1525                         if (cur->numa_group)
1526                                 imp += group_weight(cur, env->src_nid, dist) -
1527                                        group_weight(cur, env->dst_nid, dist);
1528                         else
1529                                 imp += task_weight(cur, env->src_nid, dist) -
1530                                        task_weight(cur, env->dst_nid, dist);
1531                 }
1532         }
1533
1534         if (imp <= env->best_imp && moveimp <= env->best_imp)
1535                 goto unlock;
1536
1537         if (!cur) {
1538                 /* Is there capacity at our destination? */
1539                 if (env->src_stats.nr_running <= env->src_stats.task_capacity &&
1540                     !env->dst_stats.has_free_capacity)
1541                         goto unlock;
1542
1543                 goto balance;
1544         }
1545
1546         /* Balance doesn't matter much if we're running a task per cpu */
1547         if (imp > env->best_imp && src_rq->nr_running == 1 &&
1548                         dst_rq->nr_running == 1)
1549                 goto assign;
1550
1551         /*
1552          * In the overloaded case, try and keep the load balanced.
1553          */
1554 balance:
1555         load = task_h_load(env->p);
1556         dst_load = env->dst_stats.load + load;
1557         src_load = env->src_stats.load - load;
1558
1559         if (moveimp > imp && moveimp > env->best_imp) {
1560                 /*
1561                  * If the improvement from just moving env->p direction is
1562                  * better than swapping tasks around, check if a move is
1563                  * possible. Store a slightly smaller score than moveimp,
1564                  * so an actually idle CPU will win.
1565                  */
1566                 if (!load_too_imbalanced(src_load, dst_load, env)) {
1567                         imp = moveimp - 1;
1568                         cur = NULL;
1569                         goto assign;
1570                 }
1571         }
1572
1573         if (imp <= env->best_imp)
1574                 goto unlock;
1575
1576         if (cur) {
1577                 load = task_h_load(cur);
1578                 dst_load -= load;
1579                 src_load += load;
1580         }
1581
1582         if (load_too_imbalanced(src_load, dst_load, env))
1583                 goto unlock;
1584
1585         /*
1586          * One idle CPU per node is evaluated for a task numa move.
1587          * Call select_idle_sibling to maybe find a better one.
1588          */
1589         if (!cur) {
1590                 /*
1591                  * select_idle_siblings() uses an per-cpu cpumask that
1592                  * can be used from IRQ context.
1593                  */
1594                 local_irq_disable();
1595                 env->dst_cpu = select_idle_sibling(env->p, env->src_cpu,
1596                                                    env->dst_cpu);
1597                 local_irq_enable();
1598         }
1599
1600 assign:
1601         task_numa_assign(env, cur, imp);
1602 unlock:
1603         rcu_read_unlock();
1604 }
1605
1606 static void task_numa_find_cpu(struct task_numa_env *env,
1607                                 long taskimp, long groupimp)
1608 {
1609         int cpu;
1610
1611         for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
1612                 /* Skip this CPU if the source task cannot migrate */
1613                 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
1614                         continue;
1615
1616                 env->dst_cpu = cpu;
1617                 task_numa_compare(env, taskimp, groupimp);
1618         }
1619 }
1620
1621 /* Only move tasks to a NUMA node less busy than the current node. */
1622 static bool numa_has_capacity(struct task_numa_env *env)
1623 {
1624         struct numa_stats *src = &env->src_stats;
1625         struct numa_stats *dst = &env->dst_stats;
1626
1627         if (src->has_free_capacity && !dst->has_free_capacity)
1628                 return false;
1629
1630         /*
1631          * Only consider a task move if the source has a higher load
1632          * than the destination, corrected for CPU capacity on each node.
1633          *
1634          *      src->load                dst->load
1635          * --------------------- vs ---------------------
1636          * src->compute_capacity    dst->compute_capacity
1637          */
1638         if (src->load * dst->compute_capacity * env->imbalance_pct >
1639
1640             dst->load * src->compute_capacity * 100)
1641                 return true;
1642
1643         return false;
1644 }
1645
1646 static int task_numa_migrate(struct task_struct *p)
1647 {
1648         struct task_numa_env env = {
1649                 .p = p,
1650
1651                 .src_cpu = task_cpu(p),
1652                 .src_nid = task_node(p),
1653
1654                 .imbalance_pct = 112,
1655
1656                 .best_task = NULL,
1657                 .best_imp = 0,
1658                 .best_cpu = -1,
1659         };
1660         struct sched_domain *sd;
1661         unsigned long taskweight, groupweight;
1662         int nid, ret, dist;
1663         long taskimp, groupimp;
1664
1665         /*
1666          * Pick the lowest SD_NUMA domain, as that would have the smallest
1667          * imbalance and would be the first to start moving tasks about.
1668          *
1669          * And we want to avoid any moving of tasks about, as that would create
1670          * random movement of tasks -- counter the numa conditions we're trying
1671          * to satisfy here.
1672          */
1673         rcu_read_lock();
1674         sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
1675         if (sd)
1676                 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
1677         rcu_read_unlock();
1678
1679         /*
1680          * Cpusets can break the scheduler domain tree into smaller
1681          * balance domains, some of which do not cross NUMA boundaries.
1682          * Tasks that are "trapped" in such domains cannot be migrated
1683          * elsewhere, so there is no point in (re)trying.
1684          */
1685         if (unlikely(!sd)) {
1686                 p->numa_preferred_nid = task_node(p);
1687                 return -EINVAL;
1688         }
1689
1690         env.dst_nid = p->numa_preferred_nid;
1691         dist = env.dist = node_distance(env.src_nid, env.dst_nid);
1692         taskweight = task_weight(p, env.src_nid, dist);
1693         groupweight = group_weight(p, env.src_nid, dist);
1694         update_numa_stats(&env.src_stats, env.src_nid);
1695         taskimp = task_weight(p, env.dst_nid, dist) - taskweight;
1696         groupimp = group_weight(p, env.dst_nid, dist) - groupweight;
1697         update_numa_stats(&env.dst_stats, env.dst_nid);
1698
1699         /* Try to find a spot on the preferred nid. */
1700         if (numa_has_capacity(&env))
1701                 task_numa_find_cpu(&env, taskimp, groupimp);
1702
1703         /*
1704          * Look at other nodes in these cases:
1705          * - there is no space available on the preferred_nid
1706          * - the task is part of a numa_group that is interleaved across
1707          *   multiple NUMA nodes; in order to better consolidate the group,
1708          *   we need to check other locations.
1709          */
1710         if (env.best_cpu == -1 || (p->numa_group && p->numa_group->active_nodes > 1)) {
1711                 for_each_online_node(nid) {
1712                         if (nid == env.src_nid || nid == p->numa_preferred_nid)
1713                                 continue;
1714
1715                         dist = node_distance(env.src_nid, env.dst_nid);
1716                         if (sched_numa_topology_type == NUMA_BACKPLANE &&
1717                                                 dist != env.dist) {
1718                                 taskweight = task_weight(p, env.src_nid, dist);
1719                                 groupweight = group_weight(p, env.src_nid, dist);
1720                         }
1721
1722                         /* Only consider nodes where both task and groups benefit */
1723                         taskimp = task_weight(p, nid, dist) - taskweight;
1724                         groupimp = group_weight(p, nid, dist) - groupweight;
1725                         if (taskimp < 0 && groupimp < 0)
1726                                 continue;
1727
1728                         env.dist = dist;
1729                         env.dst_nid = nid;
1730                         update_numa_stats(&env.dst_stats, env.dst_nid);
1731                         if (numa_has_capacity(&env))
1732                                 task_numa_find_cpu(&env, taskimp, groupimp);
1733                 }
1734         }
1735
1736         /*
1737          * If the task is part of a workload that spans multiple NUMA nodes,
1738          * and is migrating into one of the workload's active nodes, remember
1739          * this node as the task's preferred numa node, so the workload can
1740          * settle down.
1741          * A task that migrated to a second choice node will be better off
1742          * trying for a better one later. Do not set the preferred node here.
1743          */
1744         if (p->numa_group) {
1745                 struct numa_group *ng = p->numa_group;
1746
1747                 if (env.best_cpu == -1)
1748                         nid = env.src_nid;
1749                 else
1750                         nid = env.dst_nid;
1751
1752                 if (ng->active_nodes > 1 && numa_is_active_node(env.dst_nid, ng))
1753                         sched_setnuma(p, env.dst_nid);
1754         }
1755
1756         /* No better CPU than the current one was found. */
1757         if (env.best_cpu == -1)
1758                 return -EAGAIN;
1759
1760         /*
1761          * Reset the scan period if the task is being rescheduled on an
1762          * alternative node to recheck if the tasks is now properly placed.
1763          */
1764         p->numa_scan_period = task_scan_min(p);
1765
1766         if (env.best_task == NULL) {
1767                 ret = migrate_task_to(p, env.best_cpu);
1768                 if (ret != 0)
1769                         trace_sched_stick_numa(p, env.src_cpu, env.best_cpu);
1770                 return ret;
1771         }
1772
1773         ret = migrate_swap(p, env.best_task);
1774         if (ret != 0)
1775                 trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task));
1776         put_task_struct(env.best_task);
1777         return ret;
1778 }
1779
1780 /* Attempt to migrate a task to a CPU on the preferred node. */
1781 static void numa_migrate_preferred(struct task_struct *p)
1782 {
1783         unsigned long interval = HZ;
1784
1785         /* This task has no NUMA fault statistics yet */
1786         if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults))
1787                 return;
1788
1789         /* Periodically retry migrating the task to the preferred node */
1790         interval = min(interval, msecs_to_jiffies(p->numa_scan_period) / 16);
1791         p->numa_migrate_retry = jiffies + interval;
1792
1793         /* Success if task is already running on preferred CPU */
1794         if (task_node(p) == p->numa_preferred_nid)
1795                 return;
1796
1797         /* Otherwise, try migrate to a CPU on the preferred node */
1798         task_numa_migrate(p);
1799 }
1800
1801 /*
1802  * Find out how many nodes on the workload is actively running on. Do this by
1803  * tracking the nodes from which NUMA hinting faults are triggered. This can
1804  * be different from the set of nodes where the workload's memory is currently
1805  * located.
1806  */
1807 static void numa_group_count_active_nodes(struct numa_group *numa_group)
1808 {
1809         unsigned long faults, max_faults = 0;
1810         int nid, active_nodes = 0;
1811
1812         for_each_online_node(nid) {
1813                 faults = group_faults_cpu(numa_group, nid);
1814                 if (faults > max_faults)
1815                         max_faults = faults;
1816         }
1817
1818         for_each_online_node(nid) {
1819                 faults = group_faults_cpu(numa_group, nid);
1820                 if (faults * ACTIVE_NODE_FRACTION > max_faults)
1821                         active_nodes++;
1822         }
1823
1824         numa_group->max_faults_cpu = max_faults;
1825         numa_group->active_nodes = active_nodes;
1826 }
1827
1828 /*
1829  * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS
1830  * increments. The more local the fault statistics are, the higher the scan
1831  * period will be for the next scan window. If local/(local+remote) ratio is
1832  * below NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS)
1833  * the scan period will decrease. Aim for 70% local accesses.
1834  */
1835 #define NUMA_PERIOD_SLOTS 10
1836 #define NUMA_PERIOD_THRESHOLD 7
1837
1838 /*
1839  * Increase the scan period (slow down scanning) if the majority of
1840  * our memory is already on our local node, or if the majority of
1841  * the page accesses are shared with other processes.
1842  * Otherwise, decrease the scan period.
1843  */
1844 static void update_task_scan_period(struct task_struct *p,
1845                         unsigned long shared, unsigned long private)
1846 {
1847         unsigned int period_slot;
1848         int ratio;
1849         int diff;
1850
1851         unsigned long remote = p->numa_faults_locality[0];
1852         unsigned long local = p->numa_faults_locality[1];
1853
1854         /*
1855          * If there were no record hinting faults then either the task is
1856          * completely idle or all activity is areas that are not of interest
1857          * to automatic numa balancing. Related to that, if there were failed
1858          * migration then it implies we are migrating too quickly or the local
1859          * node is overloaded. In either case, scan slower
1860          */
1861         if (local + shared == 0 || p->numa_faults_locality[2]) {
1862                 p->numa_scan_period = min(p->numa_scan_period_max,
1863                         p->numa_scan_period << 1);
1864
1865                 p->mm->numa_next_scan = jiffies +
1866                         msecs_to_jiffies(p->numa_scan_period);
1867
1868                 return;
1869         }
1870
1871         /*
1872          * Prepare to scale scan period relative to the current period.
1873          *       == NUMA_PERIOD_THRESHOLD scan period stays the same
1874          *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
1875          *       >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
1876          */
1877         period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
1878         ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
1879         if (ratio >= NUMA_PERIOD_THRESHOLD) {
1880                 int slot = ratio - NUMA_PERIOD_THRESHOLD;
1881                 if (!slot)
1882                         slot = 1;
1883                 diff = slot * period_slot;
1884         } else {
1885                 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
1886
1887                 /*
1888                  * Scale scan rate increases based on sharing. There is an
1889                  * inverse relationship between the degree of sharing and
1890                  * the adjustment made to the scanning period. Broadly
1891                  * speaking the intent is that there is little point
1892                  * scanning faster if shared accesses dominate as it may
1893                  * simply bounce migrations uselessly
1894                  */
1895                 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared + 1));
1896                 diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
1897         }
1898
1899         p->numa_scan_period = clamp(p->numa_scan_period + diff,
1900                         task_scan_min(p), task_scan_max(p));
1901         memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1902 }
1903
1904 /*
1905  * Get the fraction of time the task has been running since the last
1906  * NUMA placement cycle. The scheduler keeps similar statistics, but
1907  * decays those on a 32ms period, which is orders of magnitude off
1908  * from the dozens-of-seconds NUMA balancing period. Use the scheduler
1909  * stats only if the task is so new there are no NUMA statistics yet.
1910  */
1911 static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
1912 {
1913         u64 runtime, delta, now;
1914         /* Use the start of this time slice to avoid calculations. */
1915         now = p->se.exec_start;
1916         runtime = p->se.sum_exec_runtime;
1917
1918         if (p->last_task_numa_placement) {
1919                 delta = runtime - p->last_sum_exec_runtime;
1920                 *period = now - p->last_task_numa_placement;
1921         } else {
1922                 delta = p->se.avg.load_sum / p->se.load.weight;
1923                 *period = LOAD_AVG_MAX;
1924         }
1925
1926         p->last_sum_exec_runtime = runtime;
1927         p->last_task_numa_placement = now;
1928
1929         return delta;
1930 }
1931
1932 /*
1933  * Determine the preferred nid for a task in a numa_group. This needs to
1934  * be done in a way that produces consistent results with group_weight,
1935  * otherwise workloads might not converge.
1936  */
1937 static int preferred_group_nid(struct task_struct *p, int nid)
1938 {
1939         nodemask_t nodes;
1940         int dist;
1941
1942         /* Direct connections between all NUMA nodes. */
1943         if (sched_numa_topology_type == NUMA_DIRECT)
1944                 return nid;
1945
1946         /*
1947          * On a system with glueless mesh NUMA topology, group_weight
1948          * scores nodes according to the number of NUMA hinting faults on
1949          * both the node itself, and on nearby nodes.
1950          */
1951         if (sched_numa_topology_type == NUMA_GLUELESS_MESH) {
1952                 unsigned long score, max_score = 0;
1953                 int node, max_node = nid;
1954
1955                 dist = sched_max_numa_distance;
1956
1957                 for_each_online_node(node) {
1958                         score = group_weight(p, node, dist);
1959                         if (score > max_score) {
1960                                 max_score = score;
1961                                 max_node = node;
1962                         }
1963                 }
1964                 return max_node;
1965         }
1966
1967         /*
1968          * Finding the preferred nid in a system with NUMA backplane
1969          * interconnect topology is more involved. The goal is to locate
1970          * tasks from numa_groups near each other in the system, and
1971          * untangle workloads from different sides of the system. This requires
1972          * searching down the hierarchy of node groups, recursively searching
1973          * inside the highest scoring group of nodes. The nodemask tricks
1974          * keep the complexity of the search down.
1975          */
1976         nodes = node_online_map;
1977         for (dist = sched_max_numa_distance; dist > LOCAL_DISTANCE; dist--) {
1978                 unsigned long max_faults = 0;
1979                 nodemask_t max_group = NODE_MASK_NONE;
1980                 int a, b;
1981
1982                 /* Are there nodes at this distance from each other? */
1983                 if (!find_numa_distance(dist))
1984                         continue;
1985
1986                 for_each_node_mask(a, nodes) {
1987                         unsigned long faults = 0;
1988                         nodemask_t this_group;
1989                         nodes_clear(this_group);
1990
1991                         /* Sum group's NUMA faults; includes a==b case. */
1992                         for_each_node_mask(b, nodes) {
1993                                 if (node_distance(a, b) < dist) {
1994                                         faults += group_faults(p, b);
1995                                         node_set(b, this_group);
1996                                         node_clear(b, nodes);
1997                                 }
1998                         }
1999
2000                         /* Remember the top group. */
2001                         if (faults > max_faults) {
2002                                 max_faults = faults;
2003                                 max_group = this_group;
2004                                 /*
2005                                  * subtle: at the smallest distance there is
2006                                  * just one node left in each "group", the
2007                                  * winner is the preferred nid.
2008                                  */
2009                                 nid = a;
2010                         }
2011                 }
2012                 /* Next round, evaluate the nodes within max_group. */
2013                 if (!max_faults)
2014                         break;
2015                 nodes = max_group;
2016         }
2017         return nid;
2018 }
2019
2020 static void task_numa_placement(struct task_struct *p)
2021 {
2022         int seq, nid, max_nid = -1, max_group_nid = -1;
2023         unsigned long max_faults = 0, max_group_faults = 0;
2024         unsigned long fault_types[2] = { 0, 0 };
2025         unsigned long total_faults;
2026         u64 runtime, period;
2027         spinlock_t *group_lock = NULL;
2028
2029         /*
2030          * The p->mm->numa_scan_seq field gets updated without
2031          * exclusive access. Use READ_ONCE() here to ensure
2032          * that the field is read in a single access:
2033          */
2034         seq = READ_ONCE(p->mm->numa_scan_seq);
2035         if (p->numa_scan_seq == seq)
2036                 return;
2037         p->numa_scan_seq = seq;
2038         p->numa_scan_period_max = task_scan_max(p);
2039
2040         total_faults = p->numa_faults_locality[0] +
2041                        p->numa_faults_locality[1];
2042         runtime = numa_get_avg_runtime(p, &period);
2043
2044         /* If the task is part of a group prevent parallel updates to group stats */
2045         if (p->numa_group) {
2046                 group_lock = &p->numa_group->lock;
2047                 spin_lock_irq(group_lock);
2048         }
2049
2050         /* Find the node with the highest number of faults */
2051         for_each_online_node(nid) {
2052                 /* Keep track of the offsets in numa_faults array */
2053                 int mem_idx, membuf_idx, cpu_idx, cpubuf_idx;
2054                 unsigned long faults = 0, group_faults = 0;
2055                 int priv;
2056
2057                 for (priv = 0; priv < NR_NUMA_HINT_FAULT_TYPES; priv++) {
2058                         long diff, f_diff, f_weight;
2059
2060                         mem_idx = task_faults_idx(NUMA_MEM, nid, priv);
2061                         membuf_idx = task_faults_idx(NUMA_MEMBUF, nid, priv);
2062                         cpu_idx = task_faults_idx(NUMA_CPU, nid, priv);
2063                         cpubuf_idx = task_faults_idx(NUMA_CPUBUF, nid, priv);
2064
2065                         /* Decay existing window, copy faults since last scan */
2066                         diff = p->numa_faults[membuf_idx] - p->numa_faults[mem_idx] / 2;
2067                         fault_types[priv] += p->numa_faults[membuf_idx];
2068                         p->numa_faults[membuf_idx] = 0;
2069
2070                         /*
2071                          * Normalize the faults_from, so all tasks in a group
2072                          * count according to CPU use, instead of by the raw
2073                          * number of faults. Tasks with little runtime have
2074                          * little over-all impact on throughput, and thus their
2075                          * faults are less important.
2076                          */
2077                         f_weight = div64_u64(runtime << 16, period + 1);
2078                         f_weight = (f_weight * p->numa_faults[cpubuf_idx]) /
2079                                    (total_faults + 1);
2080                         f_diff = f_weight - p->numa_faults[cpu_idx] / 2;
2081                         p->numa_faults[cpubuf_idx] = 0;
2082
2083                         p->numa_faults[mem_idx] += diff;
2084                         p->numa_faults[cpu_idx] += f_diff;
2085                         faults += p->numa_faults[mem_idx];
2086                         p->total_numa_faults += diff;
2087                         if (p->numa_group) {
2088                                 /*
2089                                  * safe because we can only change our own group
2090                                  *
2091                                  * mem_idx represents the offset for a given
2092                                  * nid and priv in a specific region because it
2093                                  * is at the beginning of the numa_faults array.
2094                                  */
2095                                 p->numa_group->faults[mem_idx] += diff;
2096                                 p->numa_group->faults_cpu[mem_idx] += f_diff;
2097                                 p->numa_group->total_faults += diff;
2098                                 group_faults += p->numa_group->faults[mem_idx];
2099                         }
2100                 }
2101
2102                 if (faults > max_faults) {
2103                         max_faults = faults;
2104                         max_nid = nid;
2105                 }
2106
2107                 if (group_faults > max_group_faults) {
2108                         max_group_faults = group_faults;
2109                         max_group_nid = nid;
2110                 }
2111         }
2112
2113         update_task_scan_period(p, fault_types[0], fault_types[1]);
2114
2115         if (p->numa_group) {
2116                 numa_group_count_active_nodes(p->numa_group);
2117                 spin_unlock_irq(group_lock);
2118                 max_nid = preferred_group_nid(p, max_group_nid);
2119         }
2120
2121         if (max_faults) {
2122                 /* Set the new preferred node */
2123                 if (max_nid != p->numa_preferred_nid)
2124                         sched_setnuma(p, max_nid);
2125
2126                 if (task_node(p) != p->numa_preferred_nid)
2127                         numa_migrate_preferred(p);
2128         }
2129 }
2130
2131 static inline int get_numa_group(struct numa_group *grp)
2132 {
2133         return atomic_inc_not_zero(&grp->refcount);
2134 }
2135
2136 static inline void put_numa_group(struct numa_group *grp)
2137 {
2138         if (atomic_dec_and_test(&grp->refcount))
2139                 kfree_rcu(grp, rcu);
2140 }
2141
2142 static void task_numa_group(struct task_struct *p, int cpupid, int flags,
2143                         int *priv)
2144 {
2145         struct numa_group *grp, *my_grp;
2146         struct task_struct *tsk;
2147         bool join = false;
2148         int cpu = cpupid_to_cpu(cpupid);
2149         int i;
2150
2151         if (unlikely(!p->numa_group)) {
2152                 unsigned int size = sizeof(struct numa_group) +
2153                                     4*nr_node_ids*sizeof(unsigned long);
2154
2155                 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
2156                 if (!grp)
2157                         return;
2158
2159                 atomic_set(&grp->refcount, 1);
2160                 grp->active_nodes = 1;
2161                 grp->max_faults_cpu = 0;
2162                 spin_lock_init(&grp->lock);
2163                 grp->gid = p->pid;
2164                 /* Second half of the array tracks nids where faults happen */
2165                 grp->faults_cpu = grp->faults + NR_NUMA_HINT_FAULT_TYPES *
2166                                                 nr_node_ids;
2167
2168                 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
2169                         grp->faults[i] = p->numa_faults[i];
2170
2171                 grp->total_faults = p->total_numa_faults;
2172
2173                 grp->nr_tasks++;
2174                 rcu_assign_pointer(p->numa_group, grp);
2175         }
2176
2177         rcu_read_lock();
2178         tsk = READ_ONCE(cpu_rq(cpu)->curr);
2179
2180         if (!cpupid_match_pid(tsk, cpupid))
2181                 goto no_join;
2182
2183         grp = rcu_dereference(tsk->numa_group);
2184         if (!grp)
2185                 goto no_join;
2186
2187         my_grp = p->numa_group;
2188         if (grp == my_grp)
2189                 goto no_join;
2190
2191         /*
2192          * Only join the other group if its bigger; if we're the bigger group,
2193          * the other task will join us.
2194          */
2195         if (my_grp->nr_tasks > grp->nr_tasks)
2196                 goto no_join;
2197
2198         /*
2199          * Tie-break on the grp address.
2200          */
2201         if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
2202                 goto no_join;
2203
2204         /* Always join threads in the same process. */
2205         if (tsk->mm == current->mm)
2206                 join = true;
2207
2208         /* Simple filter to avoid false positives due to PID collisions */
2209         if (flags & TNF_SHARED)
2210                 join = true;
2211
2212         /* Update priv based on whether false sharing was detected */
2213         *priv = !join;
2214
2215         if (join && !get_numa_group(grp))
2216                 goto no_join;
2217
2218         rcu_read_unlock();
2219
2220         if (!join)
2221                 return;
2222
2223         BUG_ON(irqs_disabled());
2224         double_lock_irq(&my_grp->lock, &grp->lock);
2225
2226         for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++) {
2227                 my_grp->faults[i] -= p->numa_faults[i];
2228                 grp->faults[i] += p->numa_faults[i];
2229         }
2230         my_grp->total_faults -= p->total_numa_faults;
2231         grp->total_faults += p->total_numa_faults;
2232
2233         my_grp->nr_tasks--;
2234         grp->nr_tasks++;
2235
2236         spin_unlock(&my_grp->lock);
2237         spin_unlock_irq(&grp->lock);
2238
2239         rcu_assign_pointer(p->numa_group, grp);
2240
2241         put_numa_group(my_grp);
2242         return;
2243
2244 no_join:
2245         rcu_read_unlock();
2246         return;
2247 }
2248
2249 void task_numa_free(struct task_struct *p)
2250 {
2251         struct numa_group *grp = p->numa_group;
2252         void *numa_faults = p->numa_faults;
2253         unsigned long flags;
2254         int i;
2255
2256         if (grp) {
2257                 spin_lock_irqsave(&grp->lock, flags);
2258                 for (i = 0; i < NR_NUMA_HINT_FAULT_STATS * nr_node_ids; i++)
2259                         grp->faults[i] -= p->numa_faults[i];
2260                 grp->total_faults -= p->total_numa_faults;
2261
2262                 grp->nr_tasks--;
2263                 spin_unlock_irqrestore(&grp->lock, flags);
2264                 RCU_INIT_POINTER(p->numa_group, NULL);
2265                 put_numa_group(grp);
2266         }
2267
2268         p->numa_faults = NULL;
2269         kfree(numa_faults);
2270 }
2271
2272 /*
2273  * Got a PROT_NONE fault for a page on @node.
2274  */
2275 void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
2276 {
2277         struct task_struct *p = current;
2278         bool migrated = flags & TNF_MIGRATED;
2279         int cpu_node = task_node(current);
2280         int local = !!(flags & TNF_FAULT_LOCAL);
2281         struct numa_group *ng;
2282         int priv;
2283
2284         if (!static_branch_likely(&sched_numa_balancing))
2285                 return;
2286
2287         /* for example, ksmd faulting in a user's mm */
2288         if (!p->mm)
2289                 return;
2290
2291         /* Allocate buffer to track faults on a per-node basis */
2292         if (unlikely(!p->numa_faults)) {
2293                 int size = sizeof(*p->numa_faults) *
2294                            NR_NUMA_HINT_FAULT_BUCKETS * nr_node_ids;
2295
2296                 p->numa_faults = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);
2297                 if (!p->numa_faults)
2298                         return;
2299
2300                 p->total_numa_faults = 0;
2301                 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
2302         }
2303
2304         /*
2305          * First accesses are treated as private, otherwise consider accesses
2306          * to be private if the accessing pid has not changed
2307          */
2308         if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
2309                 priv = 1;
2310         } else {
2311                 priv = cpupid_match_pid(p, last_cpupid);
2312                 if (!priv && !(flags & TNF_NO_GROUP))
2313                         task_numa_group(p, last_cpupid, flags, &priv);
2314         }
2315
2316         /*
2317          * If a workload spans multiple NUMA nodes, a shared fault that
2318          * occurs wholly within the set of nodes that the workload is
2319          * actively using should be counted as local. This allows the
2320          * scan rate to slow down when a workload has settled down.
2321          */
2322         ng = p->numa_group;
2323         if (!priv && !local && ng && ng->active_nodes > 1 &&
2324                                 numa_is_active_node(cpu_node, ng) &&
2325                                 numa_is_active_node(mem_node, ng))
2326                 local = 1;
2327
2328         task_numa_placement(p);
2329
2330         /*
2331          * Retry task to preferred node migration periodically, in case it
2332          * case it previously failed, or the scheduler moved us.
2333          */
2334         if (time_after(jiffies, p->numa_migrate_retry))
2335                 numa_migrate_preferred(p);
2336
2337         if (migrated)
2338                 p->numa_pages_migrated += pages;
2339         if (flags & TNF_MIGRATE_FAIL)
2340                 p->numa_faults_locality[2] += pages;
2341
2342         p->numa_faults[task_faults_idx(NUMA_MEMBUF, mem_node, priv)] += pages;
2343         p->numa_faults[task_faults_idx(NUMA_CPUBUF, cpu_node, priv)] += pages;
2344         p->numa_faults_locality[local] += pages;
2345 }
2346
2347 static void reset_ptenuma_scan(struct task_struct *p)
2348 {
2349         /*
2350          * We only did a read acquisition of the mmap sem, so
2351          * p->mm->numa_scan_seq is written to without exclusive access
2352          * and the update is not guaranteed to be atomic. That's not
2353          * much of an issue though, since this is just used for
2354          * statistical sampling. Use READ_ONCE/WRITE_ONCE, which are not
2355          * expensive, to avoid any form of compiler optimizations:
2356          */
2357         WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
2358         p->mm->numa_scan_offset = 0;
2359 }
2360
2361 /*
2362  * The expensive part of numa migration is done from task_work context.
2363  * Triggered from task_tick_numa().
2364  */
2365 void task_numa_work(struct callback_head *work)
2366 {
2367         unsigned long migrate, next_scan, now = jiffies;
2368         struct task_struct *p = current;
2369         struct mm_struct *mm = p->mm;
2370         u64 runtime = p->se.sum_exec_runtime;
2371         struct vm_area_struct *vma;
2372         unsigned long start, end;
2373         unsigned long nr_pte_updates = 0;
2374         long pages, virtpages;
2375
2376         SCHED_WARN_ON(p != container_of(work, struct task_struct, numa_work));
2377
2378         work->next = work; /* protect against double add */
2379         /*
2380          * Who cares about NUMA placement when they're dying.
2381          *
2382          * NOTE: make sure not to dereference p->mm before this check,
2383          * exit_task_work() happens _after_ exit_mm() so we could be called
2384          * without p->mm even though we still had it when we enqueued this
2385          * work.
2386          */
2387         if (p->flags & PF_EXITING)
2388                 return;
2389
2390         if (!mm->numa_next_scan) {
2391                 mm->numa_next_scan = now +
2392                         msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
2393         }
2394
2395         /*
2396          * Enforce maximal scan/migration frequency..
2397          */
2398         migrate = mm->numa_next_scan;
2399         if (time_before(now, migrate))
2400                 return;
2401
2402         if (p->numa_scan_period == 0) {
2403                 p->numa_scan_period_max = task_scan_max(p);
2404                 p->numa_scan_period = task_scan_min(p);
2405         }
2406
2407         next_scan = now + msecs_to_jiffies(p->numa_scan_period);
2408         if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
2409                 return;
2410
2411         /*
2412          * Delay this task enough that another task of this mm will likely win
2413          * the next time around.
2414          */
2415         p->node_stamp += 2 * TICK_NSEC;
2416
2417         start = mm->numa_scan_offset;
2418         pages = sysctl_numa_balancing_scan_size;
2419         pages <<= 20 - PAGE_SHIFT; /* MB in pages */
2420         virtpages = pages * 8;     /* Scan up to this much virtual space */
2421         if (!pages)
2422                 return;
2423
2424
2425         down_read(&mm->mmap_sem);
2426         vma = find_vma(mm, start);
2427         if (!vma) {
2428                 reset_ptenuma_scan(p);
2429                 start = 0;
2430                 vma = mm->mmap;
2431         }
2432         for (; vma; vma = vma->vm_next) {
2433                 if (!vma_migratable(vma) || !vma_policy_mof(vma) ||
2434                         is_vm_hugetlb_page(vma) || (vma->vm_flags & VM_MIXEDMAP)) {
2435                         continue;
2436                 }
2437
2438                 /*
2439                  * Shared library pages mapped by multiple processes are not
2440                  * migrated as it is expected they are cache replicated. Avoid
2441                  * hinting faults in read-only file-backed mappings or the vdso
2442                  * as migrating the pages will be of marginal benefit.
2443                  */
2444                 if (!vma->vm_mm ||
2445                     (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
2446                         continue;
2447
2448                 /*
2449                  * Skip inaccessible VMAs to avoid any confusion between
2450                  * PROT_NONE and NUMA hinting ptes
2451                  */
2452                 if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
2453                         continue;
2454
2455                 do {
2456                         start = max(start, vma->vm_start);
2457                         end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
2458                         end = min(end, vma->vm_end);
2459                         nr_pte_updates = change_prot_numa(vma, start, end);
2460
2461                         /*
2462                          * Try to scan sysctl_numa_balancing_size worth of
2463                          * hpages that have at least one present PTE that
2464                          * is not already pte-numa. If the VMA contains
2465                          * areas that are unused or already full of prot_numa
2466                          * PTEs, scan up to virtpages, to skip through those
2467                          * areas faster.
2468                          */
2469                         if (nr_pte_updates)
2470                                 pages -= (end - start) >> PAGE_SHIFT;
2471                         virtpages -= (end - start) >> PAGE_SHIFT;
2472
2473                         start = end;
2474                         if (pages <= 0 || virtpages <= 0)
2475                                 goto out;
2476
2477                         cond_resched();
2478                 } while (end != vma->vm_end);
2479         }
2480
2481 out:
2482         /*
2483          * It is possible to reach the end of the VMA list but the last few
2484          * VMAs are not guaranteed to the vma_migratable. If they are not, we
2485          * would find the !migratable VMA on the next scan but not reset the
2486          * scanner to the start so check it now.
2487          */
2488         if (vma)
2489                 mm->numa_scan_offset = start;
2490         else
2491                 reset_ptenuma_scan(p);
2492         up_read(&mm->mmap_sem);
2493
2494         /*
2495          * Make sure tasks use at least 32x as much time to run other code
2496          * than they used here, to limit NUMA PTE scanning overhead to 3% max.
2497          * Usually update_task_scan_period slows down scanning enough; on an
2498          * overloaded system we need to limit overhead on a per task basis.
2499          */
2500         if (unlikely(p->se.sum_exec_runtime != runtime)) {
2501                 u64 diff = p->se.sum_exec_runtime - runtime;
2502                 p->node_stamp += 32 * diff;
2503         }
2504 }
2505
2506 /*
2507  * Drive the periodic memory faults..
2508  */
2509 void task_tick_numa(struct rq *rq, struct task_struct *curr)
2510 {
2511         struct callback_head *work = &curr->numa_work;
2512         u64 period, now;
2513
2514         /*
2515          * We don't care about NUMA placement if we don't have memory.
2516          */
2517         if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
2518                 return;
2519
2520         /*
2521          * Using runtime rather than walltime has the dual advantage that
2522          * we (mostly) drive the selection from busy threads and that the
2523          * task needs to have done some actual work before we bother with
2524          * NUMA placement.
2525          */
2526         now = curr->se.sum_exec_runtime;
2527         period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
2528
2529         if (now > curr->node_stamp + period) {
2530                 if (!curr->node_stamp)
2531                         curr->numa_scan_period = task_scan_min(curr);
2532                 curr->node_stamp += period;
2533
2534                 if (!time_before(jiffies, curr->mm->numa_next_scan)) {
2535                         init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */
2536                         task_work_add(curr, work, true);
2537                 }
2538         }
2539 }
2540 #else
2541 static void task_tick_numa(struct rq *rq, struct task_struct *curr)
2542 {
2543 }
2544
2545 static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
2546 {
2547 }
2548
2549 static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
2550 {
2551 }
2552 #endif /* CONFIG_NUMA_BALANCING */
2553
2554 static void
2555 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2556 {
2557         update_load_add(&cfs_rq->load, se->load.weight);
2558         if (!parent_entity(se))
2559                 update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
2560 #ifdef CONFIG_SMP
2561         if (entity_is_task(se)) {
2562                 struct rq *rq = rq_of(cfs_rq);
2563
2564                 account_numa_enqueue(rq, task_of(se));
2565                 list_add(&se->group_node, &rq->cfs_tasks);
2566         }
2567 #endif
2568         cfs_rq->nr_running++;
2569 }
2570
2571 static void
2572 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
2573 {
2574         update_load_sub(&cfs_rq->load, se->load.weight);
2575         if (!parent_entity(se))
2576                 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
2577 #ifdef CONFIG_SMP
2578         if (entity_is_task(se)) {
2579                 account_numa_dequeue(rq_of(cfs_rq), task_of(se));
2580                 list_del_init(&se->group_node);
2581         }
2582 #endif
2583         cfs_rq->nr_running--;
2584 }
2585
2586 #ifdef CONFIG_FAIR_GROUP_SCHED
2587 # ifdef CONFIG_SMP
2588 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2589 {
2590         long tg_weight, load, shares;
2591
2592         /*
2593          * This really should be: cfs_rq->avg.load_avg, but instead we use
2594          * cfs_rq->load.weight, which is its upper bound. This helps ramp up
2595          * the shares for small weight interactive tasks.
2596          */
2597         load = scale_load_down(cfs_rq->load.weight);
2598
2599         tg_weight = atomic_long_read(&tg->load_avg);
2600
2601         /* Ensure tg_weight >= load */
2602         tg_weight -= cfs_rq->tg_load_avg_contrib;
2603         tg_weight += load;
2604
2605         shares = (tg->shares * load);
2606         if (tg_weight)
2607                 shares /= tg_weight;
2608
2609         if (shares < MIN_SHARES)
2610                 shares = MIN_SHARES;
2611         if (shares > tg->shares)
2612                 shares = tg->shares;
2613
2614         return shares;
2615 }
2616 # else /* CONFIG_SMP */
2617 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
2618 {
2619         return tg->shares;
2620 }
2621 # endif /* CONFIG_SMP */
2622
2623 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
2624                             unsigned long weight)
2625 {
2626         if (se->on_rq) {
2627                 /* commit outstanding execution time */
2628                 if (cfs_rq->curr == se)
2629                         update_curr(cfs_rq);
2630                 account_entity_dequeue(cfs_rq, se);
2631         }
2632
2633         update_load_set(&se->load, weight);
2634
2635         if (se->on_rq)
2636                 account_entity_enqueue(cfs_rq, se);
2637 }
2638
2639 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
2640
2641 static void update_cfs_shares(struct cfs_rq *cfs_rq)
2642 {
2643         struct task_group *tg;
2644         struct sched_entity *se;
2645         long shares;
2646
2647         tg = cfs_rq->tg;
2648         se = tg->se[cpu_of(rq_of(cfs_rq))];
2649         if (!se || throttled_hierarchy(cfs_rq))
2650                 return;
2651 #ifndef CONFIG_SMP
2652         if (likely(se->load.weight == tg->shares))
2653                 return;
2654 #endif
2655         shares = calc_cfs_shares(cfs_rq, tg);
2656
2657         reweight_entity(cfs_rq_of(se), se, shares);
2658 }
2659 #else /* CONFIG_FAIR_GROUP_SCHED */
2660 static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
2661 {
2662 }
2663 #endif /* CONFIG_FAIR_GROUP_SCHED */
2664
2665 #ifdef CONFIG_SMP
2666 /* Precomputed fixed inverse multiplies for multiplication by y^n */
2667 static const u32 runnable_avg_yN_inv[] = {
2668         0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
2669         0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
2670         0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
2671         0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
2672         0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
2673         0x85aac367, 0x82cd8698,
2674 };
2675
2676 /*
2677  * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
2678  * over-estimates when re-combining.
2679  */
2680 static const u32 runnable_avg_yN_sum[] = {
2681             0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
2682          9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
2683         17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
2684 };
2685
2686 /*
2687  * Precomputed \Sum y^k { 1<=k<=n, where n%32=0). Values are rolled down to
2688  * lower integers. See Documentation/scheduler/sched-avg.txt how these
2689  * were generated:
2690  */
2691 static const u32 __accumulated_sum_N32[] = {
2692             0, 23371, 35056, 40899, 43820, 45281,
2693         46011, 46376, 46559, 46650, 46696, 46719,
2694 };
2695
2696 /*
2697  * Approximate:
2698  *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
2699  */
2700 static __always_inline u64 decay_load(u64 val, u64 n)
2701 {
2702         unsigned int local_n;
2703
2704         if (!n)
2705                 return val;
2706         else if (unlikely(n > LOAD_AVG_PERIOD * 63))
2707                 return 0;
2708
2709         /* after bounds checking we can collapse to 32-bit */
2710         local_n = n;
2711
2712         /*
2713          * As y^PERIOD = 1/2, we can combine
2714          *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
2715          * With a look-up table which covers y^n (n<PERIOD)
2716          *
2717          * To achieve constant time decay_load.
2718          */
2719         if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
2720                 val >>= local_n / LOAD_AVG_PERIOD;
2721                 local_n %= LOAD_AVG_PERIOD;
2722         }
2723
2724         val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
2725         return val;
2726 }
2727
2728 /*
2729  * For updates fully spanning n periods, the contribution to runnable
2730  * average will be: \Sum 1024*y^n
2731  *
2732  * We can compute this reasonably efficiently by combining:
2733  *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
2734  */
2735 static u32 __compute_runnable_contrib(u64 n)
2736 {
2737         u32 contrib = 0;
2738
2739         if (likely(n <= LOAD_AVG_PERIOD))
2740                 return runnable_avg_yN_sum[n];
2741         else if (unlikely(n >= LOAD_AVG_MAX_N))
2742                 return LOAD_AVG_MAX;
2743
2744         /* Since n < LOAD_AVG_MAX_N, n/LOAD_AVG_PERIOD < 11 */
2745         contrib = __accumulated_sum_N32[n/LOAD_AVG_PERIOD];
2746         n %= LOAD_AVG_PERIOD;
2747         contrib = decay_load(contrib, n);
2748         return contrib + runnable_avg_yN_sum[n];
2749 }
2750
2751 #define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
2752
2753 /*
2754  * We can represent the historical contribution to runnable average as the
2755  * coefficients of a geometric series.  To do this we sub-divide our runnable
2756  * history into segments of approximately 1ms (1024us); label the segment that
2757  * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
2758  *
2759  * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
2760  *      p0            p1           p2
2761  *     (now)       (~1ms ago)  (~2ms ago)
2762  *
2763  * Let u_i denote the fraction of p_i that the entity was runnable.
2764  *
2765  * We then designate the fractions u_i as our co-efficients, yielding the
2766  * following representation of historical load:
2767  *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
2768  *
2769  * We choose y based on the with of a reasonably scheduling period, fixing:
2770  *   y^32 = 0.5
2771  *
2772  * This means that the contribution to load ~32ms ago (u_32) will be weighted
2773  * approximately half as much as the contribution to load within the last ms
2774  * (u_0).
2775  *
2776  * When a period "rolls over" and we have new u_0`, multiplying the previous
2777  * sum again by y is sufficient to update:
2778  *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
2779  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
2780  */
2781 static __always_inline int
2782 __update_load_avg(u64 now, int cpu, struct sched_avg *sa,
2783                   unsigned long weight, int running, struct cfs_rq *cfs_rq)
2784 {
2785         u64 delta, scaled_delta, periods;
2786         u32 contrib;
2787         unsigned int delta_w, scaled_delta_w, decayed = 0;
2788         unsigned long scale_freq, scale_cpu;
2789
2790         delta = now - sa->last_update_time;
2791         /*
2792          * This should only happen when time goes backwards, which it
2793          * unfortunately does during sched clock init when we swap over to TSC.
2794          */
2795         if ((s64)delta < 0) {
2796                 sa->last_update_time = now;
2797                 return 0;
2798         }
2799
2800         /*
2801          * Use 1024ns as the unit of measurement since it's a reasonable
2802          * approximation of 1us and fast to compute.
2803          */
2804         delta >>= 10;
2805         if (!delta)
2806                 return 0;
2807         sa->last_update_time = now;
2808
2809         scale_freq = arch_scale_freq_capacity(NULL, cpu);
2810         scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
2811
2812         /* delta_w is the amount already accumulated against our next period */
2813         delta_w = sa->period_contrib;
2814         if (delta + delta_w >= 1024) {
2815                 decayed = 1;
2816
2817                 /* how much left for next period will start over, we don't know yet */
2818                 sa->period_contrib = 0;
2819
2820                 /*
2821                  * Now that we know we're crossing a period boundary, figure
2822                  * out how much from delta we need to complete the current
2823                  * period and accrue it.
2824                  */
2825                 delta_w = 1024 - delta_w;
2826                 scaled_delta_w = cap_scale(delta_w, scale_freq);
2827                 if (weight) {
2828                         sa->load_sum += weight * scaled_delta_w;
2829                         if (cfs_rq) {
2830                                 cfs_rq->runnable_load_sum +=
2831                                                 weight * scaled_delta_w;
2832                         }
2833                 }
2834                 if (running)
2835                         sa->util_sum += scaled_delta_w * scale_cpu;
2836
2837                 delta -= delta_w;
2838
2839                 /* Figure out how many additional periods this update spans */
2840                 periods = delta / 1024;
2841                 delta %= 1024;
2842
2843                 sa->load_sum = decay_load(sa->load_sum, periods + 1);
2844                 if (cfs_rq) {
2845                         cfs_rq->runnable_load_sum =
2846                                 decay_load(cfs_rq->runnable_load_sum, periods + 1);
2847                 }
2848                 sa->util_sum = decay_load((u64)(sa->util_sum), periods + 1);
2849
2850                 /* Efficiently calculate \sum (1..n_period) 1024*y^i */
2851                 contrib = __compute_runnable_contrib(periods);
2852                 contrib = cap_scale(contrib, scale_freq);
2853                 if (weight) {
2854                         sa->load_sum += weight * contrib;
2855                         if (cfs_rq)
2856                                 cfs_rq->runnable_load_sum += weight * contrib;
2857                 }
2858                 if (running)
2859                         sa->util_sum += contrib * scale_cpu;
2860         }
2861
2862         /* Remainder of delta accrued against u_0` */
2863         scaled_delta = cap_scale(delta, scale_freq);
2864         if (weight) {
2865                 sa->load_sum += weight * scaled_delta;
2866                 if (cfs_rq)
2867                         cfs_rq->runnable_load_sum += weight * scaled_delta;
2868         }
2869         if (running)
2870                 sa->util_sum += scaled_delta * scale_cpu;
2871
2872         sa->period_contrib += delta;
2873
2874         if (decayed) {
2875                 sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX);
2876                 if (cfs_rq) {
2877                         cfs_rq->runnable_load_avg =
2878                                 div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
2879                 }
2880                 sa->util_avg = sa->util_sum / LOAD_AVG_MAX;
2881         }
2882
2883         return decayed;
2884 }
2885
2886 #ifdef CONFIG_FAIR_GROUP_SCHED
2887 /**
2888  * update_tg_load_avg - update the tg's load avg
2889  * @cfs_rq: the cfs_rq whose avg changed
2890  * @force: update regardless of how small the difference
2891  *
2892  * This function 'ensures': tg->load_avg := \Sum tg->cfs_rq[]->avg.load.
2893  * However, because tg->load_avg is a global value there are performance
2894  * considerations.
2895  *
2896  * In order to avoid having to look at the other cfs_rq's, we use a
2897  * differential update where we store the last value we propagated. This in
2898  * turn allows skipping updates if the differential is 'small'.
2899  *
2900  * Updating tg's load_avg is necessary before update_cfs_share() (which is
2901  * done) and effective_load() (which is not done because it is too costly).
2902  */
2903 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq, int force)
2904 {
2905         long delta = cfs_rq->avg.load_avg - cfs_rq->tg_load_avg_contrib;
2906
2907         /*
2908          * No need to update load_avg for root_task_group as it is not used.
2909          */
2910         if (cfs_rq->tg == &root_task_group)
2911                 return;
2912
2913         if (force || abs(delta) > cfs_rq->tg_load_avg_contrib / 64) {
2914                 atomic_long_add(delta, &cfs_rq->tg->load_avg);
2915                 cfs_rq->tg_load_avg_contrib = cfs_rq->avg.load_avg;
2916         }
2917 }
2918
2919 /*
2920  * Called within set_task_rq() right before setting a task's cpu. The
2921  * caller only guarantees p->pi_lock is held; no other assumptions,
2922  * including the state of rq->lock, should be made.
2923  */
2924 void set_task_rq_fair(struct sched_entity *se,
2925                       struct cfs_rq *prev, struct cfs_rq *next)
2926 {
2927         if (!sched_feat(ATTACH_AGE_LOAD))
2928                 return;
2929
2930         /*
2931          * We are supposed to update the task to "current" time, then its up to
2932          * date and ready to go to new CPU/cfs_rq. But we have difficulty in
2933          * getting what current time is, so simply throw away the out-of-date
2934          * time. This will result in the wakee task is less decayed, but giving
2935          * the wakee more load sounds not bad.
2936          */
2937         if (se->avg.last_update_time && prev) {
2938                 u64 p_last_update_time;
2939                 u64 n_last_update_time;
2940
2941 #ifndef CONFIG_64BIT
2942                 u64 p_last_update_time_copy;
2943                 u64 n_last_update_time_copy;
2944
2945                 do {
2946                         p_last_update_time_copy = prev->load_last_update_time_copy;
2947                         n_last_update_time_copy = next->load_last_update_time_copy;
2948
2949                         smp_rmb();
2950
2951                         p_last_update_time = prev->avg.last_update_time;
2952                         n_last_update_time = next->avg.last_update_time;
2953
2954                 } while (p_last_update_time != p_last_update_time_copy ||
2955                          n_last_update_time != n_last_update_time_copy);
2956 #else
2957                 p_last_update_time = prev->avg.last_update_time;
2958                 n_last_update_time = next->avg.last_update_time;
2959 #endif
2960                 __update_load_avg(p_last_update_time, cpu_of(rq_of(prev)),
2961                                   &se->avg, 0, 0, NULL);
2962                 se->avg.last_update_time = n_last_update_time;
2963         }
2964 }
2965 #else /* CONFIG_FAIR_GROUP_SCHED */
2966 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq, int force) {}
2967 #endif /* CONFIG_FAIR_GROUP_SCHED */
2968
2969 static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq)
2970 {
2971         if (&this_rq()->cfs == cfs_rq) {
2972                 /*
2973                  * There are a few boundary cases this might miss but it should
2974                  * get called often enough that that should (hopefully) not be
2975                  * a real problem -- added to that it only calls on the local
2976                  * CPU, so if we enqueue remotely we'll miss an update, but
2977                  * the next tick/schedule should update.
2978                  *
2979                  * It will not get called when we go idle, because the idle
2980                  * thread is a different class (!fair), nor will the utilization
2981                  * number include things like RT tasks.
2982                  *
2983                  * As is, the util number is not freq-invariant (we'd have to
2984                  * implement arch_scale_freq_capacity() for that).
2985                  *
2986                  * See cpu_util().
2987                  */
2988                 cpufreq_update_util(rq_of(cfs_rq), 0);
2989         }
2990 }
2991
2992 /*
2993  * Unsigned subtract and clamp on underflow.
2994  *
2995  * Explicitly do a load-store to ensure the intermediate value never hits
2996  * memory. This allows lockless observations without ever seeing the negative
2997  * values.
2998  */
2999 #define sub_positive(_ptr, _val) do {                           \
3000         typeof(_ptr) ptr = (_ptr);                              \
3001         typeof(*ptr) val = (_val);                              \
3002         typeof(*ptr) res, var = READ_ONCE(*ptr);                \
3003         res = var - val;                                        \
3004         if (res > var)                                          \
3005                 res = 0;                                        \
3006         WRITE_ONCE(*ptr, res);                                  \
3007 } while (0)
3008
3009 /**
3010  * update_cfs_rq_load_avg - update the cfs_rq's load/util averages
3011  * @now: current time, as per cfs_rq_clock_task()
3012  * @cfs_rq: cfs_rq to update
3013  * @update_freq: should we call cfs_rq_util_change() or will the call do so
3014  *
3015  * The cfs_rq avg is the direct sum of all its entities (blocked and runnable)
3016  * avg. The immediate corollary is that all (fair) tasks must be attached, see
3017  * post_init_entity_util_avg().
3018  *
3019  * cfs_rq->avg is used for task_h_load() and update_cfs_share() for example.
3020  *
3021  * Returns true if the load decayed or we removed load.
3022  *
3023  * Since both these conditions indicate a changed cfs_rq->avg.load we should
3024  * call update_tg_load_avg() when this function returns true.
3025  */
3026 static inline int
3027 update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq, bool update_freq)
3028 {
3029         struct sched_avg *sa = &cfs_rq->avg;
3030         int decayed, removed_load = 0, removed_util = 0;
3031
3032         if (atomic_long_read(&cfs_rq->removed_load_avg)) {
3033                 s64 r = atomic_long_xchg(&cfs_rq->removed_load_avg, 0);
3034                 sub_positive(&sa->load_avg, r);
3035                 sub_positive(&sa->load_sum, r * LOAD_AVG_MAX);
3036                 removed_load = 1;
3037         }
3038
3039         if (atomic_long_read(&cfs_rq->removed_util_avg)) {
3040                 long r = atomic_long_xchg(&cfs_rq->removed_util_avg, 0);
3041                 sub_positive(&sa->util_avg, r);
3042                 sub_positive(&sa->util_sum, r * LOAD_AVG_MAX);
3043                 removed_util = 1;
3044         }
3045
3046         decayed = __update_load_avg(now, cpu_of(rq_of(cfs_rq)), sa,
3047                 scale_load_down(cfs_rq->load.weight), cfs_rq->curr != NULL, cfs_rq);
3048
3049 #ifndef CONFIG_64BIT
3050         smp_wmb();
3051         cfs_rq->load_last_update_time_copy = sa->last_update_time;
3052 #endif
3053
3054         if (update_freq && (decayed || removed_util))
3055                 cfs_rq_util_change(cfs_rq);
3056
3057         return decayed || removed_load;
3058 }
3059
3060 /* Update task and its cfs_rq load average */
3061 static inline void update_load_avg(struct sched_entity *se, int update_tg)
3062 {
3063         struct cfs_rq *cfs_rq = cfs_rq_of(se);
3064         u64 now = cfs_rq_clock_task(cfs_rq);
3065         struct rq *rq = rq_of(cfs_rq);
3066         int cpu = cpu_of(rq);
3067
3068         /*
3069          * Track task load average for carrying it to new CPU after migrated, and
3070          * track group sched_entity load average for task_h_load calc in migration
3071          */
3072         __update_load_avg(now, cpu, &se->avg,
3073                           se->on_rq * scale_load_down(se->load.weight),
3074                           cfs_rq->curr == se, NULL);
3075
3076         if (update_cfs_rq_load_avg(now, cfs_rq, true) && update_tg)
3077                 update_tg_load_avg(cfs_rq, 0);
3078 }
3079
3080 /**
3081  * attach_entity_load_avg - attach this entity to its cfs_rq load avg
3082  * @cfs_rq: cfs_rq to attach to
3083  * @se: sched_entity to attach
3084  *
3085  * Must call update_cfs_rq_load_avg() before this, since we rely on
3086  * cfs_rq->avg.last_update_time being current.
3087  */
3088 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
3089 {
3090         if (!sched_feat(ATTACH_AGE_LOAD))
3091                 goto skip_aging;
3092
3093         /*
3094          * If we got migrated (either between CPUs or between cgroups) we'll
3095          * have aged the average right before clearing @last_update_time.
3096          *
3097          * Or we're fresh through post_init_entity_util_avg().
3098          */
3099         if (se->avg.last_update_time) {
3100                 __update_load_avg(cfs_rq->avg.last_update_time, cpu_of(rq_of(cfs_rq)),
3101                                   &se->avg, 0, 0, NULL);
3102
3103                 /*
3104                  * XXX: we could have just aged the entire load away if we've been
3105                  * absent from the fair class for too long.
3106                  */
3107         }
3108
3109 skip_aging:
3110         se->avg.last_update_time = cfs_rq->avg.last_update_time;
3111         cfs_rq->avg.load_avg += se->avg.load_avg;
3112         cfs_rq->avg.load_sum += se->avg.load_sum;
3113         cfs_rq->avg.util_avg += se->avg.util_avg;
3114         cfs_rq->avg.util_sum += se->avg.util_sum;
3115
3116         cfs_rq_util_change(cfs_rq);
3117 }
3118
3119 /**
3120  * detach_entity_load_avg - detach this entity from its cfs_rq load avg
3121  * @cfs_rq: cfs_rq to detach from
3122  * @se: sched_entity to detach
3123  *
3124  * Must call update_cfs_rq_load_avg() before this, since we rely on
3125  * cfs_rq->avg.last_update_time being current.
3126  */
3127 static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
3128 {
3129         __update_load_avg(cfs_rq->avg.last_update_time, cpu_of(rq_of(cfs_rq)),
3130                           &se->avg, se->on_rq * scale_load_down(se->load.weight),
3131                           cfs_rq->curr == se, NULL);
3132
3133         sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
3134         sub_positive(&cfs_rq->avg.load_sum, se->avg.load_sum);
3135         sub_positive(&cfs_rq->avg.util_avg, se->avg.util_avg);
3136         sub_positive(&cfs_rq->avg.util_sum, se->avg.util_sum);
3137
3138         cfs_rq_util_change(cfs_rq);
3139 }
3140
3141 /* Add the load generated by se into cfs_rq's load average */
3142 static inline void
3143 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
3144 {
3145         struct sched_avg *sa = &se->avg;
3146         u64 now = cfs_rq_clock_task(cfs_rq);
3147         int migrated, decayed;
3148
3149         migrated = !sa->last_update_time;
3150         if (!migrated) {
3151                 __update_load_avg(now, cpu_of(rq_of(cfs_rq)), sa,
3152                         se->on_rq * scale_load_down(se->load.weight),
3153                         cfs_rq->curr == se, NULL);
3154         }
3155
3156         decayed = update_cfs_rq_load_avg(now, cfs_rq, !migrated);
3157
3158         cfs_rq->runnable_load_avg += sa->load_avg;
3159         cfs_rq->runnable_load_sum += sa->load_sum;
3160
3161         if (migrated)
3162                 attach_entity_load_avg(cfs_rq, se);
3163
3164         if (decayed || migrated)
3165                 update_tg_load_avg(cfs_rq, 0);
3166 }
3167
3168 /* Remove the runnable load generated by se from cfs_rq's runnable load average */
3169 static inline void
3170 dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
3171 {
3172         update_load_avg(se, 1);
3173
3174         cfs_rq->runnable_load_avg =
3175                 max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
3176         cfs_rq->runnable_load_sum =
3177                 max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);
3178 }
3179
3180 #ifndef CONFIG_64BIT
3181 static inline u64 cfs_rq_last_update_time(struct cfs_rq *cfs_rq)
3182 {
3183         u64 last_update_time_copy;
3184         u64 last_update_time;
3185
3186         do {
3187                 last_update_time_copy = cfs_rq->load_last_update_time_copy;
3188                 smp_rmb();
3189                 last_update_time = cfs_rq->avg.last_update_time;
3190         } while (last_update_time != last_update_time_copy);
3191
3192         return last_update_time;
3193 }
3194 #else
3195 static inline u64 cfs_rq_last_update_time(struct cfs_rq *cfs_rq)
3196 {
3197         return cfs_rq->avg.last_update_time;
3198 }
3199 #endif
3200
3201 /*
3202  * Task first catches up with cfs_rq, and then subtract
3203  * itself from the cfs_rq (task must be off the queue now).
3204  */
3205 void remove_entity_load_avg(struct sched_entity *se)
3206 {
3207         struct cfs_rq *cfs_rq = cfs_rq_of(se);
3208         u64 last_update_time;
3209
3210         /*
3211          * tasks cannot exit without having gone through wake_up_new_task() ->
3212          * post_init_entity_util_avg() which will have added things to the
3213          * cfs_rq, so we can remove unconditionally.
3214          *
3215          * Similarly for groups, they will have passed through
3216          * post_init_entity_util_avg() before unregister_sched_fair_group()
3217          * calls this.
3218          */
3219
3220         last_update_time = cfs_rq_last_update_time(cfs_rq);
3221
3222         __update_load_avg(last_update_time, cpu_of(rq_of(cfs_rq)), &se->avg, 0, 0, NULL);
3223         atomic_long_add(se->avg.load_avg, &cfs_rq->removed_load_avg);
3224         atomic_long_add(se->avg.util_avg, &cfs_rq->removed_util_avg);
3225 }
3226
3227 static inline unsigned long cfs_rq_runnable_load_avg(struct cfs_rq *cfs_rq)
3228 {
3229         return cfs_rq->runnable_load_avg;
3230 }
3231
3232 static inline unsigned long cfs_rq_load_avg(struct cfs_rq *cfs_rq)
3233 {
3234         return cfs_rq->avg.load_avg;
3235 }
3236
3237 static int idle_balance(struct rq *this_rq);
3238
3239 #else /* CONFIG_SMP */
3240
3241 static inline int
3242 update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq, bool update_freq)
3243 {
3244         return 0;
3245 }
3246
3247 static inline void update_load_avg(struct sched_entity *se, int not_used)
3248 {
3249         cpufreq_update_util(rq_of(cfs_rq_of(se)), 0);
3250 }
3251
3252 static inline void
3253 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
3254 static inline void
3255 dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
3256 static inline void remove_entity_load_avg(struct sched_entity *se) {}
3257
3258 static inline void
3259 attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
3260 static inline void
3261 detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
3262
3263 static inline int idle_balance(struct rq *rq)
3264 {
3265         return 0;
3266 }
3267
3268 #endif /* CONFIG_SMP */
3269
3270 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
3271 {
3272 #ifdef CONFIG_SCHED_DEBUG
3273         s64 d = se->vruntime - cfs_rq->min_vruntime;
3274
3275         if (d < 0)
3276                 d = -d;
3277
3278         if (d > 3*sysctl_sched_latency)
3279                 schedstat_inc(cfs_rq->nr_spread_over);
3280 #endif
3281 }
3282
3283 static void
3284 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
3285 {
3286         u64 vruntime = cfs_rq->min_vruntime;
3287
3288         /*
3289          * The 'current' period is already promised to the current tasks,
3290          * however the extra weight of the new task will slow them down a
3291          * little, place the new task so that it fits in the slot that
3292          * stays open at the end.
3293          */
3294         if (initial && sched_feat(START_DEBIT))
3295                 vruntime += sched_vslice(cfs_rq, se);
3296
3297         /* sleeps up to a single latency don't count. */
3298         if (!initial) {
3299                 unsigned long thresh = sysctl_sched_latency;
3300
3301                 /*
3302                  * Halve their sleep time's effect, to allow
3303                  * for a gentler effect of sleepers:
3304                  */
3305                 if (sched_feat(GENTLE_FAIR_SLEEPERS))
3306                         thresh >>= 1;
3307
3308                 vruntime -= thresh;
3309         }
3310
3311         /* ensure we never gain time by being placed backwards. */
3312         se->vruntime = max_vruntime(se->vruntime, vruntime);
3313 }
3314
3315 static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
3316
3317 static inline void check_schedstat_required(void)
3318 {
3319 #ifdef CONFIG_SCHEDSTATS
3320         if (schedstat_enabled())
3321                 return;
3322
3323         /* Force schedstat enabled if a dependent tracepoint is active */
3324         if (trace_sched_stat_wait_enabled()    ||
3325                         trace_sched_stat_sleep_enabled()   ||
3326                         trace_sched_stat_iowait_enabled()  ||
3327                         trace_sched_stat_blocked_enabled() ||
3328                         trace_sched_stat_runtime_enabled())  {
3329                 printk_deferred_once("Scheduler tracepoints stat_sleep, stat_iowait, "
3330                              "stat_blocked and stat_runtime require the "
3331                              "kernel parameter schedstats=enabled or "
3332                              "kernel.sched_schedstats=1\n");
3333         }
3334 #endif
3335 }
3336
3337
3338 /*
3339  * MIGRATION
3340  *
3341  *      dequeue
3342  *        update_curr()
3343  *          update_min_vruntime()
3344  *        vruntime -= min_vruntime
3345  *