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