Merge tag 'v3.13' into p/abusse/merge_upgrade
[projects/modsched/linux.git] / kernel / sched / cfs / fair.c
1 /*
2  * Completely Fair Scheduling (CFS) Class (SCHED_NORMAL/SCHED_BATCH)
3  *
4  *  Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
5  *
6  *  Interactivity improvements by Mike Galbraith
7  *  (C) 2007 Mike Galbraith <efault@gmx.de>
8  *
9  *  Various enhancements by Dmitry Adamushko.
10  *  (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
11  *
12  *  Group scheduling enhancements by Srivatsa Vaddagiri
13  *  Copyright IBM Corporation, 2007
14  *  Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
15  *
16  *  Scaled math optimizations by Thomas Gleixner
17  *  Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
18  *
19  *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
20  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
21  */
22
23 #include <linux/latencytop.h>
24 #include <linux/sched.h>
25 #include <linux/cpumask.h>
26 #include <linux/slab.h>
27 #include <linux/profile.h>
28 #include <linux/interrupt.h>
29 #include <linux/mempolicy.h>
30 #include <linux/migrate.h>
31 #include <linux/task_work.h>
32
33 #include <trace/events/sched.h>
34
35 #include "sched.h"
36
37 /*
38  * Targeted preemption latency for CPU-bound tasks:
39  * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)
40  *
41  * NOTE: this latency value is not the same as the concept of
42  * 'timeslice length' - timeslices in CFS are of variable length
43  * and have no persistent notion like in traditional, time-slice
44  * based scheduling concepts.
45  *
46  * (to see the precise effective timeslice length of your workload,
47  *  run vmstat and monitor the context-switches (cs) field)
48  */
49 unsigned int sysctl_sched_latency = 6000000ULL;
50 unsigned int normalized_sysctl_sched_latency = 6000000ULL;
51
52 /*
53  * The initial- and re-scaling of tunables is configurable
54  * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
55  *
56  * Options are:
57  * SCHED_TUNABLESCALING_NONE - unscaled, always *1
58  * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
59  * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
60  */
61 enum sched_tunable_scaling sysctl_sched_tunable_scaling
62         = SCHED_TUNABLESCALING_LOG;
63
64 /*
65  * Minimal preemption granularity for CPU-bound tasks:
66  * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)
67  */
68 unsigned int sysctl_sched_min_granularity = 750000ULL;
69 unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;
70
71 /*
72  * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
73  */
74 static unsigned int sched_nr_latency = 8;
75
76 /*
77  * After fork, child runs first. If set to 0 (default) then
78  * parent will (try to) run first.
79  */
80 unsigned int sysctl_sched_child_runs_first __read_mostly;
81
82 /*
83  * SCHED_OTHER wake-up granularity.
84  * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
85  *
86  * This option delays the preemption effects of decoupled workloads
87  * and reduces their over-scheduling. Synchronous workloads will still
88  * have immediate wakeup/sleep latencies.
89  */
90 unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
91 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
92
93 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
94
95 /*
96  * The exponential sliding  window over which load is averaged for shares
97  * distribution.
98  * (default: 10msec)
99  */
100 unsigned int __read_mostly sysctl_sched_shares_window = 10000000UL;
101
102 #ifdef CONFIG_CFS_BANDWIDTH
103 /*
104  * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
105  * each time a cfs_rq requests quota.
106  *
107  * Note: in the case that the slice exceeds the runtime remaining (either due
108  * to consumption or the quota being specified to be smaller than the slice)
109  * we will always only issue the remaining available time.
110  *
111  * default: 5 msec, units: microseconds
112   */
113 unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL;
114 #endif
115
116 static inline void update_load_add(struct load_weight *lw, unsigned long inc)
117 {
118         lw->weight += inc;
119         lw->inv_weight = 0;
120 }
121
122 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
123 {
124         lw->weight -= dec;
125         lw->inv_weight = 0;
126 }
127
128 static inline void update_load_set(struct load_weight *lw, unsigned long w)
129 {
130         lw->weight = w;
131         lw->inv_weight = 0;
132 }
133
134 /*
135  * Increase the granularity value when there are more CPUs,
136  * because with more CPUs the 'effective latency' as visible
137  * to users decreases. But the relationship is not linear,
138  * so pick a second-best guess by going with the log2 of the
139  * number of CPUs.
140  *
141  * This idea comes from the SD scheduler of Con Kolivas:
142  */
143 static int get_update_sysctl_factor(void)
144 {
145         unsigned int cpus = min_t(int, num_online_cpus(), 8);
146         unsigned int factor;
147
148         switch (sysctl_sched_tunable_scaling) {
149         case SCHED_TUNABLESCALING_NONE:
150                 factor = 1;
151                 break;
152         case SCHED_TUNABLESCALING_LINEAR:
153                 factor = cpus;
154                 break;
155         case SCHED_TUNABLESCALING_LOG:
156         default:
157                 factor = 1 + ilog2(cpus);
158                 break;
159         }
160
161         return factor;
162 }
163
164 static void update_sysctl(void)
165 {
166         unsigned int factor = get_update_sysctl_factor();
167
168 #define SET_SYSCTL(name) \
169         (sysctl_##name = (factor) * normalized_sysctl_##name)
170         SET_SYSCTL(sched_min_granularity);
171         SET_SYSCTL(sched_latency);
172         SET_SYSCTL(sched_wakeup_granularity);
173 #undef SET_SYSCTL
174 }
175
176 void sched_init_granularity(void)
177 {
178         update_sysctl();
179 }
180
181 #define WMULT_CONST     (~0U)
182 #define WMULT_SHIFT     32
183
184 static void __update_inv_weight(struct load_weight *lw)
185 {
186         unsigned long w;
187
188         if (likely(lw->inv_weight))
189                 return;
190
191         w = scale_load_down(lw->weight);
192
193         if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
194                 lw->inv_weight = 1;
195         else if (unlikely(!w))
196                 lw->inv_weight = WMULT_CONST;
197         else
198                 lw->inv_weight = WMULT_CONST / w;
199 }
200
201 /*
202  * delta_exec * weight / lw.weight
203  *   OR
204  * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
205  *
206  * Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case
207  * we're guaranteed shift stays positive because inv_weight is guaranteed to
208  * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
209  *
210  * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
211  * weight/lw.weight <= 1, and therefore our shift will also be positive.
212  */
213 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
214 {
215         u64 fact = scale_load_down(weight);
216         int shift = WMULT_SHIFT;
217
218         __update_inv_weight(lw);
219
220         if (unlikely(fact >> 32)) {
221                 while (fact >> 32) {
222                         fact >>= 1;
223                         shift--;
224                 }
225         }
226
227         /* hint to use a 32x32->64 mul */
228         fact = (u64)(u32)fact * lw->inv_weight;
229
230         while (fact >> 32) {
231                 fact >>= 1;
232                 shift--;
233         }
234
235         return mul_u64_u32_shr(delta_exec, fact, shift);
236 }
237
238
239 const struct sched_class fair_sched_class;
240
241 /**************************************************************
242  * CFS operations on generic schedulable entities:
243  */
244
245 #ifdef CONFIG_FAIR_GROUP_SCHED
246
247 /* cpu runqueue to which this cfs_rq is attached */
248 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
249 {
250         return cfs_rq->rq;
251 }
252
253 /* An entity is a task if it doesn't "own" a runqueue */
254 #define entity_is_task(se)      (!se->my_q)
255
256 static inline struct task_struct *task_of(struct sched_entity *se)
257 {
258 #ifdef CONFIG_SCHED_DEBUG
259         WARN_ON_ONCE(!entity_is_task(se));
260 #endif
261         return container_of(se, struct task_struct, se);
262 }
263
264 /* Walk up scheduling entities hierarchy */
265 #define for_each_sched_entity(se) \
266                 for (; se; se = se->parent)
267
268 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
269 {
270         return p->se.cfs_rq;
271 }
272
273 /* runqueue on which this entity is (to be) queued */
274 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
275 {
276         return se->cfs_rq;
277 }
278
279 /* runqueue "owned" by this group */
280 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
281 {
282         return grp->my_q;
283 }
284
285 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
286                                        int force_update);
287
288 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
289 {
290         if (!cfs_rq->on_list) {
291                 /*
292                  * Ensure we either appear before our parent (if already
293                  * enqueued) or force our parent to appear after us when it is
294                  * enqueued.  The fact that we always enqueue bottom-up
295                  * reduces this to two cases.
296                  */
297                 if (cfs_rq->tg->parent &&
298                     cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
299                         list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
300                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
301                 } else {
302                         list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
303                                 &rq_of(cfs_rq)->leaf_cfs_rq_list);
304                 }
305
306                 cfs_rq->on_list = 1;
307                 /* We should have no load, but we need to update last_decay. */
308                 update_cfs_rq_blocked_load(cfs_rq, 0);
309         }
310 }
311
312 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
313 {
314         if (cfs_rq->on_list) {
315                 list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
316                 cfs_rq->on_list = 0;
317         }
318 }
319
320 /* Iterate thr' all leaf cfs_rq's on a runqueue */
321 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
322         list_for_each_entry_rcu(cfs_rq, &rq->leaf_cfs_rq_list, leaf_cfs_rq_list)
323
324 /* Do the two (enqueued) entities belong to the same group ? */
325 static inline int
326 is_same_group(struct sched_entity *se, struct sched_entity *pse)
327 {
328         if (se->cfs_rq == pse->cfs_rq)
329                 return 1;
330
331         return 0;
332 }
333
334 static inline struct sched_entity *parent_entity(struct sched_entity *se)
335 {
336         return se->parent;
337 }
338
339 /* return depth at which a sched entity is present in the hierarchy */
340 static inline int depth_se(struct sched_entity *se)
341 {
342         int depth = 0;
343
344         for_each_sched_entity(se)
345                 depth++;
346
347         return depth;
348 }
349
350 static void
351 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
352 {
353         int se_depth, pse_depth;
354
355         /*
356          * preemption test can be made between sibling entities who are in the
357          * same cfs_rq i.e who have a common parent. Walk up the hierarchy of
358          * both tasks until we find their ancestors who are siblings of common
359          * parent.
360          */
361
362         /* First walk up until both entities are at same depth */
363         se_depth = depth_se(*se);
364         pse_depth = depth_se(*pse);
365
366         while (se_depth > pse_depth) {
367                 se_depth--;
368                 *se = parent_entity(*se);
369         }
370
371         while (pse_depth > se_depth) {
372                 pse_depth--;
373                 *pse = parent_entity(*pse);
374         }
375
376         while (!is_same_group(*se, *pse)) {
377                 *se = parent_entity(*se);
378                 *pse = parent_entity(*pse);
379         }
380 }
381
382 #else   /* !CONFIG_FAIR_GROUP_SCHED */
383
384 static inline struct task_struct *task_of(struct sched_entity *se)
385 {
386         return container_of(se, struct task_struct, se);
387 }
388
389 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
390 {
391         return container_of(cfs_rq, struct rq, cfs);
392 }
393
394 #define entity_is_task(se)      1
395
396 #define for_each_sched_entity(se) \
397                 for (; se; se = NULL)
398
399 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
400 {
401         return &task_rq(p)->cfs;
402 }
403
404 static inline struct cfs_rq *cfs_rq_of(struct sched_entity *se)
405 {
406         struct task_struct *p = task_of(se);
407         struct rq *rq = task_rq(p);
408
409         return &rq->cfs;
410 }
411
412 /* runqueue "owned" by this group */
413 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
414 {
415         return NULL;
416 }
417
418 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
419 {
420 }
421
422 static inline void list_del_leaf_cfs_rq(struct cfs_rq *cfs_rq)
423 {
424 }
425
426 #define for_each_leaf_cfs_rq(rq, cfs_rq) \
427                 for (cfs_rq = &rq->cfs; cfs_rq; cfs_rq = NULL)
428
429 static inline int
430 is_same_group(struct sched_entity *se, struct sched_entity *pse)
431 {
432         return 1;
433 }
434
435 static inline struct sched_entity *parent_entity(struct sched_entity *se)
436 {
437         return NULL;
438 }
439
440 static inline void
441 find_matching_se(struct sched_entity **se, struct sched_entity **pse)
442 {
443 }
444
445 #endif  /* CONFIG_FAIR_GROUP_SCHED */
446
447 static __always_inline
448 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec);
449
450 /**************************************************************
451  * Scheduling class tree data structure manipulation methods:
452  */
453
454 static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
455 {
456         s64 delta = (s64)(vruntime - max_vruntime);
457         if (delta > 0)
458                 max_vruntime = vruntime;
459
460         return max_vruntime;
461 }
462
463 static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
464 {
465         s64 delta = (s64)(vruntime - min_vruntime);
466         if (delta < 0)
467                 min_vruntime = vruntime;
468
469         return min_vruntime;
470 }
471
472 static inline int entity_before(struct sched_entity *a,
473                                 struct sched_entity *b)
474 {
475         return (s64)(a->vruntime - b->vruntime) < 0;
476 }
477
478 static void update_min_vruntime(struct cfs_rq *cfs_rq)
479 {
480         u64 vruntime = cfs_rq->min_vruntime;
481
482         if (cfs_rq->curr)
483                 vruntime = cfs_rq->curr->vruntime;
484
485         if (cfs_rq->rb_leftmost) {
486                 struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
487                                                    struct sched_entity,
488                                                    run_node);
489
490                 if (!cfs_rq->curr)
491                         vruntime = se->vruntime;
492                 else
493                         vruntime = min_vruntime(vruntime, se->vruntime);
494         }
495
496         /* ensure we never gain time by being placed backwards. */
497         cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
498 #ifndef CONFIG_64BIT
499         smp_wmb();
500         cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
501 #endif
502 }
503
504 /*
505  * Enqueue an entity into the rb-tree:
506  */
507 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
508 {
509         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
510         struct rb_node *parent = NULL;
511         struct sched_entity *entry;
512         int leftmost = 1;
513
514         /*
515          * Find the right place in the rbtree:
516          */
517         while (*link) {
518                 parent = *link;
519                 entry = rb_entry(parent, struct sched_entity, run_node);
520                 /*
521                  * We dont care about collisions. Nodes with
522                  * the same key stay together.
523                  */
524                 if (entity_before(se, entry)) {
525                         link = &parent->rb_left;
526                 } else {
527                         link = &parent->rb_right;
528                         leftmost = 0;
529                 }
530         }
531
532         /*
533          * Maintain a cache of leftmost tree entries (it is frequently
534          * used):
535          */
536         if (leftmost)
537                 cfs_rq->rb_leftmost = &se->run_node;
538
539         rb_link_node(&se->run_node, parent, link);
540         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
541 }
542
543 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
544 {
545         if (cfs_rq->rb_leftmost == &se->run_node) {
546                 struct rb_node *next_node;
547
548                 next_node = rb_next(&se->run_node);
549                 cfs_rq->rb_leftmost = next_node;
550         }
551
552         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
553 }
554
555 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
556 {
557         struct rb_node *left = cfs_rq->rb_leftmost;
558
559         if (!left)
560                 return NULL;
561
562         return rb_entry(left, struct sched_entity, run_node);
563 }
564
565 static struct sched_entity *__pick_next_entity(struct sched_entity *se)
566 {
567         struct rb_node *next = rb_next(&se->run_node);
568
569         if (!next)
570                 return NULL;
571
572         return rb_entry(next, struct sched_entity, run_node);
573 }
574
575 #ifdef CONFIG_SCHED_DEBUG
576 struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
577 {
578         struct rb_node *last = rb_last(&cfs_rq->tasks_timeline);
579
580         if (!last)
581                 return NULL;
582
583         return rb_entry(last, struct sched_entity, run_node);
584 }
585
586 /**************************************************************
587  * Scheduling class statistics methods:
588  */
589
590 int sched_proc_update_handler(struct ctl_table *table, int write,
591                 void __user *buffer, size_t *lenp,
592                 loff_t *ppos)
593 {
594         int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
595         int factor = get_update_sysctl_factor();
596
597         if (ret || !write)
598                 return ret;
599
600         sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
601                                         sysctl_sched_min_granularity);
602
603 #define WRT_SYSCTL(name) \
604         (normalized_sysctl_##name = sysctl_##name / (factor))
605         WRT_SYSCTL(sched_min_granularity);
606         WRT_SYSCTL(sched_latency);
607         WRT_SYSCTL(sched_wakeup_granularity);
608 #undef WRT_SYSCTL
609
610         return 0;
611 }
612 #endif
613
614 /*
615  * delta /= w
616  */
617 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
618 {
619         if (unlikely(se->load.weight != NICE_0_LOAD))
620                 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
621
622         return delta;
623 }
624
625 /*
626  * The idea is to set a period in which each task runs once.
627  *
628  * When there are too many tasks (sched_nr_latency) we have to stretch
629  * this period because otherwise the slices get too small.
630  *
631  * p = (nr <= nl) ? l : l*nr/nl
632  */
633 static u64 __sched_period(unsigned long nr_running)
634 {
635         u64 period = sysctl_sched_latency;
636         unsigned long nr_latency = sched_nr_latency;
637
638         if (unlikely(nr_running > nr_latency)) {
639                 period = sysctl_sched_min_granularity;
640                 period *= nr_running;
641         }
642
643         return period;
644 }
645
646 /*
647  * We calculate the wall-time slice from the period by taking a part
648  * proportional to the weight.
649  *
650  * s = p*P[w/rw]
651  */
652 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
653 {
654         u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
655
656         for_each_sched_entity(se) {
657                 struct load_weight *load;
658                 struct load_weight lw;
659
660                 cfs_rq = cfs_rq_of(se);
661                 load = &cfs_rq->load;
662
663                 if (unlikely(!se->on_rq)) {
664                         lw = cfs_rq->load;
665
666                         update_load_add(&lw, se->load.weight);
667                         load = &lw;
668                 }
669                 slice = __calc_delta(slice, se->load.weight, load);
670         }
671         return slice;
672 }
673
674 /*
675  * We calculate the vruntime slice of a to-be-inserted task.
676  *
677  * vs = s/w
678  */
679 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
680 {
681         return calc_delta_fair(sched_slice(cfs_rq, se), se);
682 }
683
684 #ifdef CONFIG_SMP
685 static unsigned long task_h_load(struct task_struct *p);
686
687 static inline void __update_task_entity_contrib(struct sched_entity *se);
688
689 /* Give new task start runnable values to heavy its load in infant time */
690 void init_task_runnable_average(struct task_struct *p)
691 {
692         u32 slice;
693
694         p->se.avg.decay_count = 0;
695         slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
696         p->se.avg.runnable_avg_sum = slice;
697         p->se.avg.runnable_avg_period = slice;
698         __update_task_entity_contrib(&p->se);
699 }
700 #else
701 void init_task_runnable_average(struct task_struct *p)
702 {
703 }
704 #endif
705
706 /*
707  * Update the current task's runtime statistics.
708  */
709 static void update_curr(struct cfs_rq *cfs_rq)
710 {
711         struct sched_entity *curr = cfs_rq->curr;
712         u64 now = rq_clock_task(rq_of(cfs_rq));
713         u64 delta_exec;
714
715         if (unlikely(!curr))
716                 return;
717
718         delta_exec = now - curr->exec_start;
719         if (unlikely((s64)delta_exec <= 0))
720                 return;
721
722         curr->exec_start = now;
723
724         schedstat_set(curr->statistics.exec_max,
725                       max(delta_exec, curr->statistics.exec_max));
726
727         curr->sum_exec_runtime += delta_exec;
728         schedstat_add(cfs_rq, exec_clock, delta_exec);
729
730         curr->vruntime += calc_delta_fair(delta_exec, curr);
731         update_min_vruntime(cfs_rq);
732
733         if (entity_is_task(curr)) {
734                 struct task_struct *curtask = task_of(curr);
735
736                 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
737                 cpuacct_charge(curtask, delta_exec);
738                 account_group_exec_runtime(curtask, delta_exec);
739         }
740
741         account_cfs_rq_runtime(cfs_rq, delta_exec);
742 }
743
744 static inline void
745 update_stats_wait_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
746 {
747         schedstat_set(se->statistics.wait_start, rq_clock(rq_of(cfs_rq)));
748 }
749
750 /*
751  * Task is being enqueued - update stats:
752  */
753 static void update_stats_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
754 {
755         /*
756          * Are we enqueueing a waiting task? (for current tasks
757          * a dequeue/enqueue event is a NOP)
758          */
759         if (se != cfs_rq->curr)
760                 update_stats_wait_start(cfs_rq, se);
761 }
762
763 static void
764 update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
765 {
766         schedstat_set(se->statistics.wait_max, max(se->statistics.wait_max,
767                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start));
768         schedstat_set(se->statistics.wait_count, se->statistics.wait_count + 1);
769         schedstat_set(se->statistics.wait_sum, se->statistics.wait_sum +
770                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
771 #ifdef CONFIG_SCHEDSTATS
772         if (entity_is_task(se)) {
773                 trace_sched_stat_wait(task_of(se),
774                         rq_clock(rq_of(cfs_rq)) - se->statistics.wait_start);
775         }
776 #endif
777         schedstat_set(se->statistics.wait_start, 0);
778 }
779
780 static inline void
781 update_stats_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
782 {
783         /*
784          * Mark the end of the wait period if dequeueing a
785          * waiting task:
786          */
787         if (se != cfs_rq->curr)
788                 update_stats_wait_end(cfs_rq, se);
789 }
790
791 /*
792  * We are picking a new current task - update its stats:
793  */
794 static inline void
795 update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
796 {
797         /*
798          * We are starting a new run period:
799          */
800         se->exec_start = rq_clock_task(rq_of(cfs_rq));
801 }
802
803 /**************************************************
804  * Scheduling class queueing methods:
805  */
806
807 #ifdef CONFIG_NUMA_BALANCING
808 /*
809  * Approximate time to scan a full NUMA task in ms. The task scan period is
810  * calculated based on the tasks virtual memory size and
811  * numa_balancing_scan_size.
812  */
813 unsigned int sysctl_numa_balancing_scan_period_min = 1000;
814 unsigned int sysctl_numa_balancing_scan_period_max = 60000;
815
816 /* Portion of address space to scan in MB */
817 unsigned int sysctl_numa_balancing_scan_size = 256;
818
819 /* Scan @scan_size MB every @scan_period after an initial @scan_delay in ms */
820 unsigned int sysctl_numa_balancing_scan_delay = 1000;
821
822 /*
823  * After skipping a page migration on a shared page, skip N more numa page
824  * migrations unconditionally. This reduces the number of NUMA migrations
825  * in shared memory workloads, and has the effect of pulling tasks towards
826  * where their memory lives, over pulling the memory towards the task.
827  */
828 unsigned int sysctl_numa_balancing_migrate_deferred = 16;
829
830 static unsigned int task_nr_scan_windows(struct task_struct *p)
831 {
832         unsigned long rss = 0;
833         unsigned long nr_scan_pages;
834
835         /*
836          * Calculations based on RSS as non-present and empty pages are skipped
837          * by the PTE scanner and NUMA hinting faults should be trapped based
838          * on resident pages
839          */
840         nr_scan_pages = sysctl_numa_balancing_scan_size << (20 - PAGE_SHIFT);
841         rss = get_mm_rss(p->mm);
842         if (!rss)
843                 rss = nr_scan_pages;
844
845         rss = round_up(rss, nr_scan_pages);
846         return rss / nr_scan_pages;
847 }
848
849 /* For sanitys sake, never scan more PTEs than MAX_SCAN_WINDOW MB/sec. */
850 #define MAX_SCAN_WINDOW 2560
851
852 static unsigned int task_scan_min(struct task_struct *p)
853 {
854         unsigned int scan, floor;
855         unsigned int windows = 1;
856
857         if (sysctl_numa_balancing_scan_size < MAX_SCAN_WINDOW)
858                 windows = MAX_SCAN_WINDOW / sysctl_numa_balancing_scan_size;
859         floor = 1000 / windows;
860
861         scan = sysctl_numa_balancing_scan_period_min / task_nr_scan_windows(p);
862         return max_t(unsigned int, floor, scan);
863 }
864
865 static unsigned int task_scan_max(struct task_struct *p)
866 {
867         unsigned int smin = task_scan_min(p);
868         unsigned int smax;
869
870         /* Watch for min being lower than max due to floor calculations */
871         smax = sysctl_numa_balancing_scan_period_max / task_nr_scan_windows(p);
872         return max(smin, smax);
873 }
874
875 /*
876  * Once a preferred node is selected the scheduler balancer will prefer moving
877  * a task to that node for sysctl_numa_balancing_settle_count number of PTE
878  * scans. This will give the process the chance to accumulate more faults on
879  * the preferred node but still allow the scheduler to move the task again if
880  * the nodes CPUs are overloaded.
881  */
882 unsigned int sysctl_numa_balancing_settle_count __read_mostly = 4;
883
884 static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
885 {
886         rq->nr_numa_running += (p->numa_preferred_nid != -1);
887         rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
888 }
889
890 static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
891 {
892         rq->nr_numa_running -= (p->numa_preferred_nid != -1);
893         rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
894 }
895
896 struct numa_group {
897         atomic_t refcount;
898
899         spinlock_t lock; /* nr_tasks, tasks */
900         int nr_tasks;
901         pid_t gid;
902         struct list_head task_list;
903
904         struct rcu_head rcu;
905         unsigned long total_faults;
906         unsigned long faults[0];
907 };
908
909 pid_t task_numa_group_id(struct task_struct *p)
910 {
911         return p->numa_group ? p->numa_group->gid : 0;
912 }
913
914 static inline int task_faults_idx(int nid, int priv)
915 {
916         return 2 * nid + priv;
917 }
918
919 static inline unsigned long task_faults(struct task_struct *p, int nid)
920 {
921         if (!p->numa_faults)
922                 return 0;
923
924         return p->numa_faults[task_faults_idx(nid, 0)] +
925                 p->numa_faults[task_faults_idx(nid, 1)];
926 }
927
928 static inline unsigned long group_faults(struct task_struct *p, int nid)
929 {
930         if (!p->numa_group)
931                 return 0;
932
933         return p->numa_group->faults[2*nid] + p->numa_group->faults[2*nid+1];
934 }
935
936 /*
937  * These return the fraction of accesses done by a particular task, or
938  * task group, on a particular numa node.  The group weight is given a
939  * larger multiplier, in order to group tasks together that are almost
940  * evenly spread out between numa nodes.
941  */
942 static inline unsigned long task_weight(struct task_struct *p, int nid)
943 {
944         unsigned long total_faults;
945
946         if (!p->numa_faults)
947                 return 0;
948
949         total_faults = p->total_numa_faults;
950
951         if (!total_faults)
952                 return 0;
953
954         return 1000 * task_faults(p, nid) / total_faults;
955 }
956
957 static inline unsigned long group_weight(struct task_struct *p, int nid)
958 {
959         if (!p->numa_group || !p->numa_group->total_faults)
960                 return 0;
961
962         return 1000 * group_faults(p, nid) / p->numa_group->total_faults;
963 }
964
965 static unsigned long weighted_cpuload(const int cpu);
966 static unsigned long source_load(int cpu, int type);
967 static unsigned long target_load(int cpu, int type);
968 static unsigned long power_of(int cpu);
969 static long effective_load(struct task_group *tg, int cpu, long wl, long wg);
970
971 /* Cached statistics for all CPUs within a node */
972 struct numa_stats {
973         unsigned long nr_running;
974         unsigned long load;
975
976         /* Total compute capacity of CPUs on a node */
977         unsigned long power;
978
979         /* Approximate capacity in terms of runnable tasks on a node */
980         unsigned long capacity;
981         int has_capacity;
982 };
983
984 /*
985  * XXX borrowed from update_sg_lb_stats
986  */
987 static void update_numa_stats(struct numa_stats *ns, int nid)
988 {
989         int cpu, cpus = 0;
990
991         memset(ns, 0, sizeof(*ns));
992         for_each_cpu(cpu, cpumask_of_node(nid)) {
993                 struct rq *rq = cpu_rq(cpu);
994
995                 ns->nr_running += rq->nr_running;
996                 ns->load += weighted_cpuload(cpu);
997                 ns->power += power_of(cpu);
998
999                 cpus++;
1000         }
1001
1002         /*
1003          * If we raced with hotplug and there are no CPUs left in our mask
1004          * the @ns structure is NULL'ed and task_numa_compare() will
1005          * not find this node attractive.
1006          *
1007          * We'll either bail at !has_capacity, or we'll detect a huge imbalance
1008          * and bail there.
1009          */
1010         if (!cpus)
1011                 return;
1012
1013         ns->load = (ns->load * SCHED_POWER_SCALE) / ns->power;
1014         ns->capacity = DIV_ROUND_CLOSEST(ns->power, SCHED_POWER_SCALE);
1015         ns->has_capacity = (ns->nr_running < ns->capacity);
1016 }
1017
1018 struct task_numa_env {
1019         struct task_struct *p;
1020
1021         int src_cpu, src_nid;
1022         int dst_cpu, dst_nid;
1023
1024         struct numa_stats src_stats, dst_stats;
1025
1026         int imbalance_pct, idx;
1027
1028         struct task_struct *best_task;
1029         long best_imp;
1030         int best_cpu;
1031 };
1032
1033 static void task_numa_assign(struct task_numa_env *env,
1034                              struct task_struct *p, long imp)
1035 {
1036         if (env->best_task)
1037                 put_task_struct(env->best_task);
1038         if (p)
1039                 get_task_struct(p);
1040
1041         env->best_task = p;
1042         env->best_imp = imp;
1043         env->best_cpu = env->dst_cpu;
1044 }
1045
1046 /*
1047  * This checks if the overall compute and NUMA accesses of the system would
1048  * be improved if the source tasks was migrated to the target dst_cpu taking
1049  * into account that it might be best if task running on the dst_cpu should
1050  * be exchanged with the source task
1051  */
1052 static void task_numa_compare(struct task_numa_env *env,
1053                               long taskimp, long groupimp)
1054 {
1055         struct rq *src_rq = cpu_rq(env->src_cpu);
1056         struct rq *dst_rq = cpu_rq(env->dst_cpu);
1057         struct task_struct *cur;
1058         long dst_load, src_load;
1059         long load;
1060         long imp = (groupimp > 0) ? groupimp : taskimp;
1061
1062         rcu_read_lock();
1063         cur = ACCESS_ONCE(dst_rq->curr);
1064         if (cur->pid == 0) /* idle */
1065                 cur = NULL;
1066
1067         /*
1068          * "imp" is the fault differential for the source task between the
1069          * source and destination node. Calculate the total differential for
1070          * the source task and potential destination task. The more negative
1071          * the value is, the more rmeote accesses that would be expected to
1072          * be incurred if the tasks were swapped.
1073          */
1074         if (cur) {
1075                 /* Skip this swap candidate if cannot move to the source cpu */
1076                 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
1077                         goto unlock;
1078
1079                 /*
1080                  * If dst and source tasks are in the same NUMA group, or not
1081                  * in any group then look only at task weights.
1082                  */
1083                 if (cur->numa_group == env->p->numa_group) {
1084                         imp = taskimp + task_weight(cur, env->src_nid) -
1085                               task_weight(cur, env->dst_nid);
1086                         /*
1087                          * Add some hysteresis to prevent swapping the
1088                          * tasks within a group over tiny differences.
1089                          */
1090                         if (cur->numa_group)
1091                                 imp -= imp/16;
1092                 } else {
1093                         /*
1094                          * Compare the group weights. If a task is all by
1095                          * itself (not part of a group), use the task weight
1096                          * instead.
1097                          */
1098                         if (env->p->numa_group)
1099                                 imp = groupimp;
1100                         else
1101                                 imp = taskimp;
1102
1103                         if (cur->numa_group)
1104                                 imp += group_weight(cur, env->src_nid) -
1105                                        group_weight(cur, env->dst_nid);
1106                         else
1107                                 imp += task_weight(cur, env->src_nid) -
1108                                        task_weight(cur, env->dst_nid);
1109                 }
1110         }
1111
1112         if (imp < env->best_imp)
1113                 goto unlock;
1114
1115         if (!cur) {
1116                 /* Is there capacity at our destination? */
1117                 if (env->src_stats.has_capacity &&
1118                     !env->dst_stats.has_capacity)
1119                         goto unlock;
1120
1121                 goto balance;
1122         }
1123
1124         /* Balance doesn't matter much if we're running a task per cpu */
1125         if (src_rq->nr_running == 1 && dst_rq->nr_running == 1)
1126                 goto assign;
1127
1128         /*
1129          * In the overloaded case, try and keep the load balanced.
1130          */
1131 balance:
1132         dst_load = env->dst_stats.load;
1133         src_load = env->src_stats.load;
1134
1135         /* XXX missing power terms */
1136         load = task_h_load(env->p);
1137         dst_load += load;
1138         src_load -= load;
1139
1140         if (cur) {
1141                 load = task_h_load(cur);
1142                 dst_load -= load;
1143                 src_load += load;
1144         }
1145
1146         /* make src_load the smaller */
1147         if (dst_load < src_load)
1148                 swap(dst_load, src_load);
1149
1150         if (src_load * env->imbalance_pct < dst_load * 100)
1151                 goto unlock;
1152
1153 assign:
1154         task_numa_assign(env, cur, imp);
1155 unlock:
1156         rcu_read_unlock();
1157 }
1158
1159 static void task_numa_find_cpu(struct task_numa_env *env,
1160                                 long taskimp, long groupimp)
1161 {
1162         int cpu;
1163
1164         for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
1165                 /* Skip this CPU if the source task cannot migrate */
1166                 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
1167                         continue;
1168
1169                 env->dst_cpu = cpu;
1170                 task_numa_compare(env, taskimp, groupimp);
1171         }
1172 }
1173
1174 static int task_numa_migrate(struct task_struct *p)
1175 {
1176         struct task_numa_env env = {
1177                 .p = p,
1178
1179                 .src_cpu = task_cpu(p),
1180                 .src_nid = task_node(p),
1181
1182                 .imbalance_pct = 112,
1183
1184                 .best_task = NULL,
1185                 .best_imp = 0,
1186                 .best_cpu = -1
1187         };
1188         struct sched_domain *sd;
1189         unsigned long taskweight, groupweight;
1190         int nid, ret;
1191         long taskimp, groupimp;
1192
1193         /*
1194          * Pick the lowest SD_NUMA domain, as that would have the smallest
1195          * imbalance and would be the first to start moving tasks about.
1196          *
1197          * And we want to avoid any moving of tasks about, as that would create
1198          * random movement of tasks -- counter the numa conditions we're trying
1199          * to satisfy here.
1200          */
1201         rcu_read_lock();
1202         sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
1203         if (sd)
1204                 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
1205         rcu_read_unlock();
1206
1207         /*
1208          * Cpusets can break the scheduler domain tree into smaller
1209          * balance domains, some of which do not cross NUMA boundaries.
1210          * Tasks that are "trapped" in such domains cannot be migrated
1211          * elsewhere, so there is no point in (re)trying.
1212          */
1213         if (unlikely(!sd)) {
1214                 p->numa_preferred_nid = cpu_to_node(task_cpu(p));
1215                 return -EINVAL;
1216         }
1217
1218         taskweight = task_weight(p, env.src_nid);
1219         groupweight = group_weight(p, env.src_nid);
1220         update_numa_stats(&env.src_stats, env.src_nid);
1221         env.dst_nid = p->numa_preferred_nid;
1222         taskimp = task_weight(p, env.dst_nid) - taskweight;
1223         groupimp = group_weight(p, env.dst_nid) - groupweight;
1224         update_numa_stats(&env.dst_stats, env.dst_nid);
1225
1226         /* If the preferred nid has capacity, try to use it. */
1227         if (env.dst_stats.has_capacity)
1228                 task_numa_find_cpu(&env, taskimp, groupimp);
1229
1230         /* No space available on the preferred nid. Look elsewhere. */
1231         if (env.best_cpu == -1) {
1232                 for_each_online_node(nid) {
1233                         if (nid == env.src_nid || nid == p->numa_preferred_nid)
1234                                 continue;
1235
1236                         /* Only consider nodes where both task and groups benefit */
1237                         taskimp = task_weight(p, nid) - taskweight;
1238                         groupimp = group_weight(p, nid) - groupweight;
1239                         if (taskimp < 0 && groupimp < 0)
1240                                 continue;
1241
1242                         env.dst_nid = nid;
1243                         update_numa_stats(&env.dst_stats, env.dst_nid);
1244                         task_numa_find_cpu(&env, taskimp, groupimp);
1245                 }
1246         }
1247
1248         /* No better CPU than the current one was found. */
1249         if (env.best_cpu == -1)
1250                 return -EAGAIN;
1251
1252         sched_setnuma(p, env.dst_nid);
1253
1254         /*
1255          * Reset the scan period if the task is being rescheduled on an
1256          * alternative node to recheck if the tasks is now properly placed.
1257          */
1258         p->numa_scan_period = task_scan_min(p);
1259
1260         if (env.best_task == NULL) {
1261                 int ret = migrate_task_to(p, env.best_cpu);
1262                 return ret;
1263         }
1264
1265         ret = migrate_swap(p, env.best_task);
1266         put_task_struct(env.best_task);
1267         return ret;
1268 }
1269
1270 /* Attempt to migrate a task to a CPU on the preferred node. */
1271 static void numa_migrate_preferred(struct task_struct *p)
1272 {
1273         /* This task has no NUMA fault statistics yet */
1274         if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults))
1275                 return;
1276
1277         /* Periodically retry migrating the task to the preferred node */
1278         p->numa_migrate_retry = jiffies + HZ;
1279
1280         /* Success if task is already running on preferred CPU */
1281         if (cpu_to_node(task_cpu(p)) == p->numa_preferred_nid)
1282                 return;
1283
1284         /* Otherwise, try migrate to a CPU on the preferred node */
1285         task_numa_migrate(p);
1286 }
1287
1288 /*
1289  * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS
1290  * increments. The more local the fault statistics are, the higher the scan
1291  * period will be for the next scan window. If local/remote ratio is below
1292  * NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS) the
1293  * scan period will decrease
1294  */
1295 #define NUMA_PERIOD_SLOTS 10
1296 #define NUMA_PERIOD_THRESHOLD 3
1297
1298 /*
1299  * Increase the scan period (slow down scanning) if the majority of
1300  * our memory is already on our local node, or if the majority of
1301  * the page accesses are shared with other processes.
1302  * Otherwise, decrease the scan period.
1303  */
1304 static void update_task_scan_period(struct task_struct *p,
1305                         unsigned long shared, unsigned long private)
1306 {
1307         unsigned int period_slot;
1308         int ratio;
1309         int diff;
1310
1311         unsigned long remote = p->numa_faults_locality[0];
1312         unsigned long local = p->numa_faults_locality[1];
1313
1314         /*
1315          * If there were no record hinting faults then either the task is
1316          * completely idle or all activity is areas that are not of interest
1317          * to automatic numa balancing. Scan slower
1318          */
1319         if (local + shared == 0) {
1320                 p->numa_scan_period = min(p->numa_scan_period_max,
1321                         p->numa_scan_period << 1);
1322
1323                 p->mm->numa_next_scan = jiffies +
1324                         msecs_to_jiffies(p->numa_scan_period);
1325
1326                 return;
1327         }
1328
1329         /*
1330          * Prepare to scale scan period relative to the current period.
1331          *       == NUMA_PERIOD_THRESHOLD scan period stays the same
1332          *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
1333          *       >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
1334          */
1335         period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
1336         ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
1337         if (ratio >= NUMA_PERIOD_THRESHOLD) {
1338                 int slot = ratio - NUMA_PERIOD_THRESHOLD;
1339                 if (!slot)
1340                         slot = 1;
1341                 diff = slot * period_slot;
1342         } else {
1343                 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
1344
1345                 /*
1346                  * Scale scan rate increases based on sharing. There is an
1347                  * inverse relationship between the degree of sharing and
1348                  * the adjustment made to the scanning period. Broadly
1349                  * speaking the intent is that there is little point
1350                  * scanning faster if shared accesses dominate as it may
1351                  * simply bounce migrations uselessly
1352                  */
1353                 period_slot = DIV_ROUND_UP(diff, NUMA_PERIOD_SLOTS);
1354                 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared));
1355                 diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
1356         }
1357
1358         p->numa_scan_period = clamp(p->numa_scan_period + diff,
1359                         task_scan_min(p), task_scan_max(p));
1360         memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1361 }
1362
1363 static void task_numa_placement(struct task_struct *p)
1364 {
1365         int seq, nid, max_nid = -1, max_group_nid = -1;
1366         unsigned long max_faults = 0, max_group_faults = 0;
1367         unsigned long fault_types[2] = { 0, 0 };
1368         spinlock_t *group_lock = NULL;
1369
1370         seq = ACCESS_ONCE(p->mm->numa_scan_seq);
1371         if (p->numa_scan_seq == seq)
1372                 return;
1373         p->numa_scan_seq = seq;
1374         p->numa_scan_period_max = task_scan_max(p);
1375
1376         /* If the task is part of a group prevent parallel updates to group stats */
1377         if (p->numa_group) {
1378                 group_lock = &p->numa_group->lock;
1379                 spin_lock(group_lock);
1380         }
1381
1382         /* Find the node with the highest number of faults */
1383         for_each_online_node(nid) {
1384                 unsigned long faults = 0, group_faults = 0;
1385                 int priv, i;
1386
1387                 for (priv = 0; priv < 2; priv++) {
1388                         long diff;
1389
1390                         i = task_faults_idx(nid, priv);
1391                         diff = -p->numa_faults[i];
1392
1393                         /* Decay existing window, copy faults since last scan */
1394                         p->numa_faults[i] >>= 1;
1395                         p->numa_faults[i] += p->numa_faults_buffer[i];
1396                         fault_types[priv] += p->numa_faults_buffer[i];
1397                         p->numa_faults_buffer[i] = 0;
1398
1399                         faults += p->numa_faults[i];
1400                         diff += p->numa_faults[i];
1401                         p->total_numa_faults += diff;
1402                         if (p->numa_group) {
1403                                 /* safe because we can only change our own group */
1404                                 p->numa_group->faults[i] += diff;
1405                                 p->numa_group->total_faults += diff;
1406                                 group_faults += p->numa_group->faults[i];
1407                         }
1408                 }
1409
1410                 if (faults > max_faults) {
1411                         max_faults = faults;
1412                         max_nid = nid;
1413                 }
1414
1415                 if (group_faults > max_group_faults) {
1416                         max_group_faults = group_faults;
1417                         max_group_nid = nid;
1418                 }
1419         }
1420
1421         update_task_scan_period(p, fault_types[0], fault_types[1]);
1422
1423         if (p->numa_group) {
1424                 /*
1425                  * If the preferred task and group nids are different,
1426                  * iterate over the nodes again to find the best place.
1427                  */
1428                 if (max_nid != max_group_nid) {
1429                         unsigned long weight, max_weight = 0;
1430
1431                         for_each_online_node(nid) {
1432                                 weight = task_weight(p, nid) + group_weight(p, nid);
1433                                 if (weight > max_weight) {
1434                                         max_weight = weight;
1435                                         max_nid = nid;
1436                                 }
1437                         }
1438                 }
1439
1440                 spin_unlock(group_lock);
1441         }
1442
1443         /* Preferred node as the node with the most faults */
1444         if (max_faults && max_nid != p->numa_preferred_nid) {
1445                 /* Update the preferred nid and migrate task if possible */
1446                 sched_setnuma(p, max_nid);
1447                 numa_migrate_preferred(p);
1448         }
1449 }
1450
1451 static inline int get_numa_group(struct numa_group *grp)
1452 {
1453         return atomic_inc_not_zero(&grp->refcount);
1454 }
1455
1456 static inline void put_numa_group(struct numa_group *grp)
1457 {
1458         if (atomic_dec_and_test(&grp->refcount))
1459                 kfree_rcu(grp, rcu);
1460 }
1461
1462 static void task_numa_group(struct task_struct *p, int cpupid, int flags,
1463                         int *priv)
1464 {
1465         struct numa_group *grp, *my_grp;
1466         struct task_struct *tsk;
1467         bool join = false;
1468         int cpu = cpupid_to_cpu(cpupid);
1469         int i;
1470
1471         if (unlikely(!p->numa_group)) {
1472                 unsigned int size = sizeof(struct numa_group) +
1473                                     2*nr_node_ids*sizeof(unsigned long);
1474
1475                 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
1476                 if (!grp)
1477                         return;
1478
1479                 atomic_set(&grp->refcount, 1);
1480                 spin_lock_init(&grp->lock);
1481                 INIT_LIST_HEAD(&grp->task_list);
1482                 grp->gid = p->pid;
1483
1484                 for (i = 0; i < 2*nr_node_ids; i++)
1485                         grp->faults[i] = p->numa_faults[i];
1486
1487                 grp->total_faults = p->total_numa_faults;
1488
1489                 list_add(&p->numa_entry, &grp->task_list);
1490                 grp->nr_tasks++;
1491                 rcu_assign_pointer(p->numa_group, grp);
1492         }
1493
1494         rcu_read_lock();
1495         tsk = ACCESS_ONCE(cpu_rq(cpu)->curr);
1496
1497         if (!cpupid_match_pid(tsk, cpupid))
1498                 goto no_join;
1499
1500         grp = rcu_dereference(tsk->numa_group);
1501         if (!grp)
1502                 goto no_join;
1503
1504         my_grp = p->numa_group;
1505         if (grp == my_grp)
1506                 goto no_join;
1507
1508         /*
1509          * Only join the other group if its bigger; if we're the bigger group,
1510          * the other task will join us.
1511          */
1512         if (my_grp->nr_tasks > grp->nr_tasks)
1513                 goto no_join;
1514
1515         /*
1516          * Tie-break on the grp address.
1517          */
1518         if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
1519                 goto no_join;
1520
1521         /* Always join threads in the same process. */
1522         if (tsk->mm == current->mm)
1523                 join = true;
1524
1525         /* Simple filter to avoid false positives due to PID collisions */
1526         if (flags & TNF_SHARED)
1527                 join = true;
1528
1529         /* Update priv based on whether false sharing was detected */
1530         *priv = !join;
1531
1532         if (join && !get_numa_group(grp))
1533                 goto no_join;
1534
1535         rcu_read_unlock();
1536
1537         if (!join)
1538                 return;
1539
1540         double_lock(&my_grp->lock, &grp->lock);
1541
1542         for (i = 0; i < 2*nr_node_ids; i++) {
1543                 my_grp->faults[i] -= p->numa_faults[i];
1544                 grp->faults[i] += p->numa_faults[i];
1545         }
1546         my_grp->total_faults -= p->total_numa_faults;
1547         grp->total_faults += p->total_numa_faults;
1548
1549         list_move(&p->numa_entry, &grp->task_list);
1550         my_grp->nr_tasks--;
1551         grp->nr_tasks++;
1552
1553         spin_unlock(&my_grp->lock);
1554         spin_unlock(&grp->lock);
1555
1556         rcu_assign_pointer(p->numa_group, grp);
1557
1558         put_numa_group(my_grp);
1559         return;
1560
1561 no_join:
1562         rcu_read_unlock();
1563         return;
1564 }
1565
1566 void task_numa_free(struct task_struct *p)
1567 {
1568         struct numa_group *grp = p->numa_group;
1569         int i;
1570         void *numa_faults = p->numa_faults;
1571
1572         if (grp) {
1573                 spin_lock(&grp->lock);
1574                 for (i = 0; i < 2*nr_node_ids; i++)
1575                         grp->faults[i] -= p->numa_faults[i];
1576                 grp->total_faults -= p->total_numa_faults;
1577
1578                 list_del(&p->numa_entry);
1579                 grp->nr_tasks--;
1580                 spin_unlock(&grp->lock);
1581                 rcu_assign_pointer(p->numa_group, NULL);
1582                 put_numa_group(grp);
1583         }
1584
1585         p->numa_faults = NULL;
1586         p->numa_faults_buffer = NULL;
1587         kfree(numa_faults);
1588 }
1589
1590 /*
1591  * Got a PROT_NONE fault for a page on @node.
1592  */
1593 void task_numa_fault(int last_cpupid, int node, int pages, int flags)
1594 {
1595         struct task_struct *p = current;
1596         bool migrated = flags & TNF_MIGRATED;
1597         int priv;
1598
1599         if (!numabalancing_enabled)
1600                 return;
1601
1602         /* for example, ksmd faulting in a user's mm */
1603         if (!p->mm)
1604                 return;
1605
1606         /* Do not worry about placement if exiting */
1607         if (p->state == TASK_DEAD)
1608                 return;
1609
1610         /* Allocate buffer to track faults on a per-node basis */
1611         if (unlikely(!p->numa_faults)) {
1612                 int size = sizeof(*p->numa_faults) * 2 * nr_node_ids;
1613
1614                 /* numa_faults and numa_faults_buffer share the allocation */
1615                 p->numa_faults = kzalloc(size * 2, GFP_KERNEL|__GFP_NOWARN);
1616                 if (!p->numa_faults)
1617                         return;
1618
1619                 BUG_ON(p->numa_faults_buffer);
1620                 p->numa_faults_buffer = p->numa_faults + (2 * nr_node_ids);
1621                 p->total_numa_faults = 0;
1622                 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1623         }
1624
1625         /*
1626          * First accesses are treated as private, otherwise consider accesses
1627          * to be private if the accessing pid has not changed
1628          */
1629         if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
1630                 priv = 1;
1631         } else {
1632                 priv = cpupid_match_pid(p, last_cpupid);
1633                 if (!priv && !(flags & TNF_NO_GROUP))
1634                         task_numa_group(p, last_cpupid, flags, &priv);
1635         }
1636
1637         task_numa_placement(p);
1638
1639         /*
1640          * Retry task to preferred node migration periodically, in case it
1641          * case it previously failed, or the scheduler moved us.
1642          */
1643         if (time_after(jiffies, p->numa_migrate_retry))
1644                 numa_migrate_preferred(p);
1645
1646         if (migrated)
1647                 p->numa_pages_migrated += pages;
1648
1649         p->numa_faults_buffer[task_faults_idx(node, priv)] += pages;
1650         p->numa_faults_locality[!!(flags & TNF_FAULT_LOCAL)] += pages;
1651 }
1652
1653 static void reset_ptenuma_scan(struct task_struct *p)
1654 {
1655         ACCESS_ONCE(p->mm->numa_scan_seq)++;
1656         p->mm->numa_scan_offset = 0;
1657 }
1658
1659 /*
1660  * The expensive part of numa migration is done from task_work context.
1661  * Triggered from task_tick_numa().
1662  */
1663 void task_numa_work(struct callback_head *work)
1664 {
1665         unsigned long migrate, next_scan, now = jiffies;
1666         struct task_struct *p = current;
1667         struct mm_struct *mm = p->mm;
1668         struct vm_area_struct *vma;
1669         unsigned long start, end;
1670         unsigned long nr_pte_updates = 0;
1671         long pages;
1672
1673         WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work));
1674
1675         work->next = work; /* protect against double add */
1676         /*
1677          * Who cares about NUMA placement when they're dying.
1678          *
1679          * NOTE: make sure not to dereference p->mm before this check,
1680          * exit_task_work() happens _after_ exit_mm() so we could be called
1681          * without p->mm even though we still had it when we enqueued this
1682          * work.
1683          */
1684         if (p->flags & PF_EXITING)
1685                 return;
1686
1687         if (!mm->numa_next_scan) {
1688                 mm->numa_next_scan = now +
1689                         msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
1690         }
1691
1692         /*
1693          * Enforce maximal scan/migration frequency..
1694          */
1695         migrate = mm->numa_next_scan;
1696         if (time_before(now, migrate))
1697                 return;
1698
1699         if (p->numa_scan_period == 0) {
1700                 p->numa_scan_period_max = task_scan_max(p);
1701                 p->numa_scan_period = task_scan_min(p);
1702         }
1703
1704         next_scan = now + msecs_to_jiffies(p->numa_scan_period);
1705         if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
1706                 return;
1707
1708         /*
1709          * Delay this task enough that another task of this mm will likely win
1710          * the next time around.
1711          */
1712         p->node_stamp += 2 * TICK_NSEC;
1713
1714         start = mm->numa_scan_offset;
1715         pages = sysctl_numa_balancing_scan_size;
1716         pages <<= 20 - PAGE_SHIFT; /* MB in pages */
1717         if (!pages)
1718                 return;
1719
1720         down_read(&mm->mmap_sem);
1721         vma = find_vma(mm, start);
1722         if (!vma) {
1723                 reset_ptenuma_scan(p);
1724                 start = 0;
1725                 vma = mm->mmap;
1726         }
1727         for (; vma; vma = vma->vm_next) {
1728                 if (!vma_migratable(vma) || !vma_policy_mof(p, vma))
1729                         continue;
1730
1731                 /*
1732                  * Shared library pages mapped by multiple processes are not
1733                  * migrated as it is expected they are cache replicated. Avoid
1734                  * hinting faults in read-only file-backed mappings or the vdso
1735                  * as migrating the pages will be of marginal benefit.
1736                  */
1737                 if (!vma->vm_mm ||
1738                     (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
1739                         continue;
1740
1741                 /*
1742                  * Skip inaccessible VMAs to avoid any confusion between
1743                  * PROT_NONE and NUMA hinting ptes
1744                  */
1745                 if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
1746                         continue;
1747
1748                 do {
1749                         start = max(start, vma->vm_start);
1750                         end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
1751                         end = min(end, vma->vm_end);
1752                         nr_pte_updates += change_prot_numa(vma, start, end);
1753
1754                         /*
1755                          * Scan sysctl_numa_balancing_scan_size but ensure that
1756                          * at least one PTE is updated so that unused virtual
1757                          * address space is quickly skipped.
1758                          */
1759                         if (nr_pte_updates)
1760                                 pages -= (end - start) >> PAGE_SHIFT;
1761
1762                         start = end;
1763                         if (pages <= 0)
1764                                 goto out;
1765                 } while (end != vma->vm_end);
1766         }
1767
1768 out:
1769         /*
1770          * It is possible to reach the end of the VMA list but the last few
1771          * VMAs are not guaranteed to the vma_migratable. If they are not, we
1772          * would find the !migratable VMA on the next scan but not reset the
1773          * scanner to the start so check it now.
1774          */
1775         if (vma)
1776                 mm->numa_scan_offset = start;
1777         else
1778                 reset_ptenuma_scan(p);
1779         up_read(&mm->mmap_sem);
1780 }
1781
1782 /*
1783  * Drive the periodic memory faults..
1784  */
1785 void task_tick_numa(struct rq *rq, struct task_struct *curr)
1786 {
1787         struct callback_head *work = &curr->numa_work;
1788         u64 period, now;
1789
1790         /*
1791          * We don't care about NUMA placement if we don't have memory.
1792          */
1793         if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
1794                 return;
1795
1796         /*
1797          * Using runtime rather than walltime has the dual advantage that
1798          * we (mostly) drive the selection from busy threads and that the
1799          * task needs to have done some actual work before we bother with
1800          * NUMA placement.
1801          */
1802         now = curr->se.sum_exec_runtime;
1803         period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
1804
1805         if (now - curr->node_stamp > period) {
1806                 if (!curr->node_stamp)
1807                         curr->numa_scan_period = task_scan_min(curr);
1808                 curr->node_stamp += period;
1809
1810                 if (!time_before(jiffies, curr->mm->numa_next_scan)) {
1811                         init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */
1812                         task_work_add(curr, work, true);
1813                 }
1814         }
1815 }
1816 #else
1817 static void task_tick_numa(struct rq *rq, struct task_struct *curr)
1818 {
1819 }
1820
1821 static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
1822 {
1823 }
1824
1825 static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
1826 {
1827 }
1828 #endif /* CONFIG_NUMA_BALANCING */
1829
1830 static void
1831 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
1832 {
1833         update_load_add(&cfs_rq->load, se->load.weight);
1834         if (!parent_entity(se))
1835                 update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
1836 #ifdef CONFIG_SMP
1837         if (entity_is_task(se)) {
1838                 struct rq *rq = rq_of(cfs_rq);
1839
1840                 account_numa_enqueue(rq, task_of(se));
1841                 list_add(&se->group_node, &rq->cfs_tasks);
1842         }
1843 #endif
1844         cfs_rq->nr_running++;
1845 }
1846
1847 static void
1848 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
1849 {
1850         update_load_sub(&cfs_rq->load, se->load.weight);
1851         if (!parent_entity(se))
1852                 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
1853         if (entity_is_task(se)) {
1854                 account_numa_dequeue(rq_of(cfs_rq), task_of(se));
1855                 list_del_init(&se->group_node);
1856         }
1857         cfs_rq->nr_running--;
1858 }
1859
1860 #ifdef CONFIG_FAIR_GROUP_SCHED
1861 # ifdef CONFIG_SMP
1862 static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
1863 {
1864         long tg_weight;
1865
1866         /*
1867          * Use this CPU's actual weight instead of the last load_contribution
1868          * to gain a more accurate current total weight. See
1869          * update_cfs_rq_load_contribution().
1870          */
1871         tg_weight = atomic_long_read(&tg->load_avg);
1872         tg_weight -= cfs_rq->tg_load_contrib;
1873         tg_weight += cfs_rq->load.weight;
1874
1875         return tg_weight;
1876 }
1877
1878 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
1879 {
1880         long tg_weight, load, shares;
1881
1882         tg_weight = calc_tg_weight(tg, cfs_rq);
1883         load = cfs_rq->load.weight;
1884
1885         shares = (tg->shares * load);
1886         if (tg_weight)
1887                 shares /= tg_weight;
1888
1889         if (shares < MIN_SHARES)
1890                 shares = MIN_SHARES;
1891         if (shares > tg->shares)
1892                 shares = tg->shares;
1893
1894         return shares;
1895 }
1896 # else /* CONFIG_SMP */
1897 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
1898 {
1899         return tg->shares;
1900 }
1901 # endif /* CONFIG_SMP */
1902 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
1903                             unsigned long weight)
1904 {
1905         if (se->on_rq) {
1906                 /* commit outstanding execution time */
1907                 if (cfs_rq->curr == se)
1908                         update_curr(cfs_rq);
1909                 account_entity_dequeue(cfs_rq, se);
1910         }
1911
1912         update_load_set(&se->load, weight);
1913
1914         if (se->on_rq)
1915                 account_entity_enqueue(cfs_rq, se);
1916 }
1917
1918 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
1919
1920 static void update_cfs_shares(struct cfs_rq *cfs_rq)
1921 {
1922         struct task_group *tg;
1923         struct sched_entity *se;
1924         long shares;
1925
1926         tg = cfs_rq->tg;
1927         se = tg->se[cpu_of(rq_of(cfs_rq))];
1928         if (!se || throttled_hierarchy(cfs_rq))
1929                 return;
1930 #ifndef CONFIG_SMP
1931         if (likely(se->load.weight == tg->shares))
1932                 return;
1933 #endif
1934         shares = calc_cfs_shares(cfs_rq, tg);
1935
1936         reweight_entity(cfs_rq_of(se), se, shares);
1937 }
1938 #else /* CONFIG_FAIR_GROUP_SCHED */
1939 static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
1940 {
1941 }
1942 #endif /* CONFIG_FAIR_GROUP_SCHED */
1943
1944 #ifdef CONFIG_SMP
1945 /*
1946  * We choose a half-life close to 1 scheduling period.
1947  * Note: The tables below are dependent on this value.
1948  */
1949 #define LOAD_AVG_PERIOD 32
1950 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
1951 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */
1952
1953 /* Precomputed fixed inverse multiplies for multiplication by y^n */
1954 static const u32 runnable_avg_yN_inv[] = {
1955         0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
1956         0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
1957         0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
1958         0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
1959         0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
1960         0x85aac367, 0x82cd8698,
1961 };
1962
1963 /*
1964  * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
1965  * over-estimates when re-combining.
1966  */
1967 static const u32 runnable_avg_yN_sum[] = {
1968             0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
1969          9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
1970         17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
1971 };
1972
1973 /*
1974  * Approximate:
1975  *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
1976  */
1977 static __always_inline u64 decay_load(u64 val, u64 n)
1978 {
1979         unsigned int local_n;
1980
1981         if (!n)
1982                 return val;
1983         else if (unlikely(n > LOAD_AVG_PERIOD * 63))
1984                 return 0;
1985
1986         /* after bounds checking we can collapse to 32-bit */
1987         local_n = n;
1988
1989         /*
1990          * As y^PERIOD = 1/2, we can combine
1991          *    y^n = 1/2^(n/PERIOD) * k^(n%PERIOD)
1992          * With a look-up table which covers k^n (n<PERIOD)
1993          *
1994          * To achieve constant time decay_load.
1995          */
1996         if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
1997                 val >>= local_n / LOAD_AVG_PERIOD;
1998                 local_n %= LOAD_AVG_PERIOD;
1999         }
2000
2001         val *= runnable_avg_yN_inv[local_n];
2002         /* We don't use SRR here since we always want to round down. */
2003         return val >> 32;
2004 }
2005
2006 /*
2007  * For updates fully spanning n periods, the contribution to runnable
2008  * average will be: \Sum 1024*y^n
2009  *
2010  * We can compute this reasonably efficiently by combining:
2011  *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
2012  */
2013 static u32 __compute_runnable_contrib(u64 n)
2014 {
2015         u32 contrib = 0;
2016
2017         if (likely(n <= LOAD_AVG_PERIOD))
2018                 return runnable_avg_yN_sum[n];
2019         else if (unlikely(n >= LOAD_AVG_MAX_N))
2020                 return LOAD_AVG_MAX;
2021
2022         /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
2023         do {
2024                 contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
2025                 contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
2026
2027                 n -= LOAD_AVG_PERIOD;
2028         } while (n > LOAD_AVG_PERIOD);
2029
2030         contrib = decay_load(contrib, n);
2031         return contrib + runnable_avg_yN_sum[n];
2032 }
2033
2034 /*
2035  * We can represent the historical contribution to runnable average as the
2036  * coefficients of a geometric series.  To do this we sub-divide our runnable
2037  * history into segments of approximately 1ms (1024us); label the segment that
2038  * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
2039  *
2040  * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
2041  *      p0            p1           p2
2042  *     (now)       (~1ms ago)  (~2ms ago)
2043  *
2044  * Let u_i denote the fraction of p_i that the entity was runnable.
2045  *
2046  * We then designate the fractions u_i as our co-efficients, yielding the
2047  * following representation of historical load:
2048  *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
2049  *
2050  * We choose y based on the with of a reasonably scheduling period, fixing:
2051  *   y^32 = 0.5
2052  *
2053  * This means that the contribution to load ~32ms ago (u_32) will be weighted
2054  * approximately half as much as the contribution to load within the last ms
2055  * (u_0).
2056  *
2057  * When a period "rolls over" and we have new u_0`, multiplying the previous
2058  * sum again by y is sufficient to update:
2059  *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
2060  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
2061  */
2062 static __always_inline int __update_entity_runnable_avg(u64 now,
2063                                                         struct sched_avg *sa,
2064                                                         int runnable)
2065 {
2066         u64 delta, periods;
2067         u32 runnable_contrib;
2068         int delta_w, decayed = 0;
2069
2070         delta = now - sa->last_runnable_update;
2071         /*
2072          * This should only happen when time goes backwards, which it
2073          * unfortunately does during sched clock init when we swap over to TSC.
2074          */
2075         if ((s64)delta < 0) {
2076                 sa->last_runnable_update = now;
2077                 return 0;
2078         }
2079
2080         /*
2081          * Use 1024ns as the unit of measurement since it's a reasonable
2082          * approximation of 1us and fast to compute.
2083          */
2084         delta >>= 10;
2085         if (!delta)
2086                 return 0;
2087         sa->last_runnable_update = now;
2088
2089         /* delta_w is the amount already accumulated against our next period */
2090         delta_w = sa->runnable_avg_period % 1024;
2091         if (delta + delta_w >= 1024) {
2092                 /* period roll-over */
2093                 decayed = 1;
2094
2095                 /*
2096                  * Now that we know we're crossing a period boundary, figure
2097                  * out how much from delta we need to complete the current
2098                  * period and accrue it.
2099                  */
2100                 delta_w = 1024 - delta_w;
2101                 if (runnable)
2102                         sa->runnable_avg_sum += delta_w;
2103                 sa->runnable_avg_period += delta_w;
2104
2105                 delta -= delta_w;
2106
2107                 /* Figure out how many additional periods this update spans */
2108                 periods = delta / 1024;
2109                 delta %= 1024;
2110
2111                 sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
2112                                                   periods + 1);
2113                 sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
2114                                                      periods + 1);
2115
2116                 /* Efficiently calculate \sum (1..n_period) 1024*y^i */
2117                 runnable_contrib = __compute_runnable_contrib(periods);
2118                 if (runnable)
2119                         sa->runnable_avg_sum += runnable_contrib;
2120                 sa->runnable_avg_period += runnable_contrib;
2121         }
2122
2123         /* Remainder of delta accrued against u_0` */
2124         if (runnable)
2125                 sa->runnable_avg_sum += delta;
2126         sa->runnable_avg_period += delta;
2127
2128         return decayed;
2129 }
2130
2131 /* Synchronize an entity's decay with its parenting cfs_rq.*/
2132 static inline u64 __synchronize_entity_decay(struct sched_entity *se)
2133 {
2134         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2135         u64 decays = atomic64_read(&cfs_rq->decay_counter);
2136
2137         decays -= se->avg.decay_count;
2138         if (!decays)
2139                 return 0;
2140
2141         se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);
2142         se->avg.decay_count = 0;
2143
2144         return decays;
2145 }
2146
2147 #ifdef CONFIG_FAIR_GROUP_SCHED
2148 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2149                                                  int force_update)
2150 {
2151         struct task_group *tg = cfs_rq->tg;
2152         long tg_contrib;
2153
2154         tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
2155         tg_contrib -= cfs_rq->tg_load_contrib;
2156
2157         if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
2158                 atomic_long_add(tg_contrib, &tg->load_avg);
2159                 cfs_rq->tg_load_contrib += tg_contrib;
2160         }
2161 }
2162
2163 /*
2164  * Aggregate cfs_rq runnable averages into an equivalent task_group
2165  * representation for computing load contributions.
2166  */
2167 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2168                                                   struct cfs_rq *cfs_rq)
2169 {
2170         struct task_group *tg = cfs_rq->tg;
2171         long contrib;
2172
2173         /* The fraction of a cpu used by this cfs_rq */
2174         contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
2175                           sa->runnable_avg_period + 1);
2176         contrib -= cfs_rq->tg_runnable_contrib;
2177
2178         if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
2179                 atomic_add(contrib, &tg->runnable_avg);
2180                 cfs_rq->tg_runnable_contrib += contrib;
2181         }
2182 }
2183
2184 static inline void __update_group_entity_contrib(struct sched_entity *se)
2185 {
2186         struct cfs_rq *cfs_rq = group_cfs_rq(se);
2187         struct task_group *tg = cfs_rq->tg;
2188         int runnable_avg;
2189
2190         u64 contrib;
2191
2192         contrib = cfs_rq->tg_load_contrib * tg->shares;
2193         se->avg.load_avg_contrib = div_u64(contrib,
2194                                      atomic_long_read(&tg->load_avg) + 1);
2195
2196         /*
2197          * For group entities we need to compute a correction term in the case
2198          * that they are consuming <1 cpu so that we would contribute the same
2199          * load as a task of equal weight.
2200          *
2201          * Explicitly co-ordinating this measurement would be expensive, but
2202          * fortunately the sum of each cpus contribution forms a usable
2203          * lower-bound on the true value.
2204          *
2205          * Consider the aggregate of 2 contributions.  Either they are disjoint
2206          * (and the sum represents true value) or they are disjoint and we are
2207          * understating by the aggregate of their overlap.
2208          *
2209          * Extending this to N cpus, for a given overlap, the maximum amount we
2210          * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of
2211          * cpus that overlap for this interval and w_i is the interval width.
2212          *
2213          * On a small machine; the first term is well-bounded which bounds the
2214          * total error since w_i is a subset of the period.  Whereas on a
2215          * larger machine, while this first term can be larger, if w_i is the
2216          * of consequential size guaranteed to see n_i*w_i quickly converge to
2217          * our upper bound of 1-cpu.
2218          */
2219         runnable_avg = atomic_read(&tg->runnable_avg);
2220         if (runnable_avg < NICE_0_LOAD) {
2221                 se->avg.load_avg_contrib *= runnable_avg;
2222                 se->avg.load_avg_contrib >>= NICE_0_SHIFT;
2223         }
2224 }
2225 #else
2226 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2227                                                  int force_update) {}
2228 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2229                                                   struct cfs_rq *cfs_rq) {}
2230 static inline void __update_group_entity_contrib(struct sched_entity *se) {}
2231 #endif
2232
2233 static inline void __update_task_entity_contrib(struct sched_entity *se)
2234 {
2235         u32 contrib;
2236
2237         /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
2238         contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
2239         contrib /= (se->avg.runnable_avg_period + 1);
2240         se->avg.load_avg_contrib = scale_load(contrib);
2241 }
2242
2243 /* Compute the current contribution to load_avg by se, return any delta */
2244 static long __update_entity_load_avg_contrib(struct sched_entity *se)
2245 {
2246         long old_contrib = se->avg.load_avg_contrib;
2247
2248         if (entity_is_task(se)) {
2249                 __update_task_entity_contrib(se);
2250         } else {
2251                 __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
2252                 __update_group_entity_contrib(se);
2253         }
2254
2255         return se->avg.load_avg_contrib - old_contrib;
2256 }
2257
2258 static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
2259                                                  long load_contrib)
2260 {
2261         if (likely(load_contrib < cfs_rq->blocked_load_avg))
2262                 cfs_rq->blocked_load_avg -= load_contrib;
2263         else
2264                 cfs_rq->blocked_load_avg = 0;
2265 }
2266
2267 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
2268
2269 /* Update a sched_entity's runnable average */
2270 static inline void update_entity_load_avg(struct sched_entity *se,
2271                                           int update_cfs_rq)
2272 {
2273         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2274         long contrib_delta;
2275         u64 now;
2276
2277         /*
2278          * For a group entity we need to use their owned cfs_rq_clock_task() in
2279          * case they are the parent of a throttled hierarchy.
2280          */
2281         if (entity_is_task(se))
2282                 now = cfs_rq_clock_task(cfs_rq);
2283         else
2284                 now = cfs_rq_clock_task(group_cfs_rq(se));
2285
2286         if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
2287                 return;
2288
2289         contrib_delta = __update_entity_load_avg_contrib(se);
2290
2291         if (!update_cfs_rq)
2292                 return;
2293
2294         if (se->on_rq)
2295                 cfs_rq->runnable_load_avg += contrib_delta;
2296         else
2297                 subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
2298 }
2299
2300 /*
2301  * Decay the load contributed by all blocked children and account this so that
2302  * their contribution may appropriately discounted when they wake up.
2303  */
2304 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
2305 {
2306         u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
2307         u64 decays;
2308
2309         decays = now - cfs_rq->last_decay;
2310         if (!decays && !force_update)
2311                 return;
2312
2313         if (atomic_long_read(&cfs_rq->removed_load)) {
2314                 unsigned long removed_load;
2315                 removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
2316                 subtract_blocked_load_contrib(cfs_rq, removed_load);
2317         }
2318
2319         if (decays) {
2320                 cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
2321                                                       decays);
2322                 atomic64_add(decays, &cfs_rq->decay_counter);
2323                 cfs_rq->last_decay = now;
2324         }
2325
2326         __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
2327 }
2328
2329 static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
2330 {
2331         __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
2332         __update_tg_runnable_avg(&rq->avg, &rq->cfs);
2333 }
2334
2335 /* Add the load generated by se into cfs_rq's child load-average */
2336 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2337                                                   struct sched_entity *se,
2338                                                   int wakeup)
2339 {
2340         /*
2341          * We track migrations using entity decay_count <= 0, on a wake-up
2342          * migration we use a negative decay count to track the remote decays
2343          * accumulated while sleeping.
2344          *
2345          * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
2346          * are seen by enqueue_entity_load_avg() as a migration with an already
2347          * constructed load_avg_contrib.
2348          */
2349         if (unlikely(se->avg.decay_count <= 0)) {
2350                 se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
2351                 if (se->avg.decay_count) {
2352                         /*
2353                          * In a wake-up migration we have to approximate the
2354                          * time sleeping.  This is because we can't synchronize
2355                          * clock_task between the two cpus, and it is not
2356                          * guaranteed to be read-safe.  Instead, we can
2357                          * approximate this using our carried decays, which are
2358                          * explicitly atomically readable.
2359                          */
2360                         se->avg.last_runnable_update -= (-se->avg.decay_count)
2361                                                         << 20;
2362                         update_entity_load_avg(se, 0);
2363                         /* Indicate that we're now synchronized and on-rq */
2364                         se->avg.decay_count = 0;
2365                 }
2366                 wakeup = 0;
2367         } else {
2368                 /*
2369                  * Task re-woke on same cpu (or else migrate_task_rq_fair()
2370                  * would have made count negative); we must be careful to avoid
2371                  * double-accounting blocked time after synchronizing decays.
2372                  */
2373                 se->avg.last_runnable_update += __synchronize_entity_decay(se)
2374                                                         << 20;
2375         }
2376
2377         /* migrated tasks did not contribute to our blocked load */
2378         if (wakeup) {
2379                 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
2380                 update_entity_load_avg(se, 0);
2381         }
2382
2383         cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
2384         /* we force update consideration on load-balancer moves */
2385         update_cfs_rq_blocked_load(cfs_rq, !wakeup);
2386 }
2387
2388 /*
2389  * Remove se's load from this cfs_rq child load-average, if the entity is
2390  * transitioning to a blocked state we track its projected decay using
2391  * blocked_load_avg.
2392  */
2393 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2394                                                   struct sched_entity *se,
2395                                                   int sleep)
2396 {
2397         update_entity_load_avg(se, 1);
2398         /* we force update consideration on load-balancer moves */
2399         update_cfs_rq_blocked_load(cfs_rq, !sleep);
2400
2401         cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
2402         if (sleep) {
2403                 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
2404                 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
2405         } /* migrations, e.g. sleep=0 leave decay_count == 0 */
2406 }
2407
2408 /*
2409  * Update the rq's load with the elapsed running time before entering
2410  * idle. if the last scheduled task is not a CFS task, idle_enter will
2411  * be the only way to update the runnable statistic.
2412  */
2413 void idle_enter_fair(struct rq *this_rq)
2414 {
2415         update_rq_runnable_avg(this_rq, 1);
2416 }
2417
2418 /*
2419  * Update the rq's load with the elapsed idle time before a task is
2420  * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
2421  * be the only way to update the runnable statistic.
2422  */
2423 void idle_exit_fair(struct rq *this_rq)
2424 {
2425         update_rq_runnable_avg(this_rq, 0);
2426 }
2427
2428 #else
2429 static inline void update_entity_load_avg(struct sched_entity *se,
2430                                           int update_cfs_rq) {}
2431 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2432 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2433                                            struct sched_entity *se,
2434                                            int wakeup) {}
2435 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2436                                            struct sched_entity *se,
2437                                            int sleep) {}
2438 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
2439                                               int force_update) {}
2440 #endif
2441
2442 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
2443 {
2444 #ifdef CONFIG_SCHEDSTATS
2445         struct task_struct *tsk = NULL;
2446
2447         if (entity_is_task(se))
2448                 tsk = task_of(se);
2449
2450         if (se->statistics.sleep_start) {
2451                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.sleep_start;
2452
2453                 if ((s64)delta < 0)
2454                         delta = 0;
2455
2456                 if (unlikely(delta > se->statistics.sleep_max))
2457                         se->statistics.sleep_max = delta;
2458
2459                 se->statistics.sleep_start = 0;
2460                 se->statistics.sum_sleep_runtime += delta;
2461
2462                 if (tsk) {
2463                         account_scheduler_latency(tsk, delta >> 10, 1);
2464                         trace_sched_stat_sleep(tsk, delta);
2465                 }
2466         }
2467         if (se->statistics.block_start) {
2468                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.block_start;
2469
2470                 if ((s64)delta < 0)
2471                         delta = 0;
2472
2473                 if (unlikely(delta > se->statistics.block_max))
2474                         se->statistics.block_max = delta;
2475
2476                 se->statistics.block_start = 0;
2477                 se->statistics.sum_sleep_runtime += delta;
2478
2479                 if (tsk) {
2480                         if (tsk->in_iowait) {
2481                                 se->statistics.iowait_sum += delta;
2482                                 se->statistics.iowait_count++;
2483                                 trace_sched_stat_iowait(tsk, delta);
2484                         }
2485
2486                         trace_sched_stat_blocked(tsk, delta);
2487
2488                         /*
2489                          * Blocking time is in units of nanosecs, so shift by
2490                          * 20 to get a milliseconds-range estimation of the
2491                          * amount of time that the task spent sleeping:
2492                          */
2493                         if (unlikely(prof_on == SLEEP_PROFILING)) {
2494                                 profile_hits(SLEEP_PROFILING,
2495                                                 (void *)get_wchan(tsk),
2496                                                 delta >> 20);
2497                         }
2498                         account_scheduler_latency(tsk, delta >> 10, 0);
2499                 }
2500         }
2501 #endif
2502 }
2503
2504 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
2505 {
2506 #ifdef CONFIG_SCHED_DEBUG
2507         s64 d = se->vruntime - cfs_rq->min_vruntime;
2508
2509         if (d < 0)
2510                 d = -d;
2511
2512         if (d > 3*sysctl_sched_latency)
2513                 schedstat_inc(cfs_rq, nr_spread_over);
2514 #endif
2515 }
2516
2517 static void
2518 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
2519 {
2520         u64 vruntime = cfs_rq->min_vruntime;
2521
2522         /*
2523          * The 'current' period is already promised to the current tasks,
2524          * however the extra weight of the new task will slow them down a
2525          * little, place the new task so that it fits in the slot that
2526          * stays open at the end.
2527          */
2528         if (initial && sched_feat(START_DEBIT))
2529                 vruntime += sched_vslice(cfs_rq, se);
2530
2531         /* sleeps up to a single latency don't count. */
2532         if (!initial) {
2533                 unsigned long thresh = sysctl_sched_latency;
2534
2535                 /*
2536                  * Halve their sleep time's effect, to allow
2537                  * for a gentler effect of sleepers:
2538                  */
2539                 if (sched_feat(GENTLE_FAIR_SLEEPERS))
2540                         thresh >>= 1;
2541
2542                 vruntime -= thresh;
2543         }
2544
2545         /* ensure we never gain time by being placed backwards. */
2546         se->vruntime = max_vruntime(se->vruntime, vruntime);
2547 }
2548
2549 static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
2550
2551 static void
2552 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2553 {
2554         /*
2555          * Update the normalized vruntime before updating min_vruntime
2556          * through calling update_curr().
2557          */
2558         if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
2559                 se->vruntime += cfs_rq->min_vruntime;
2560
2561         /*
2562          * Update run-time statistics of the 'current'.
2563          */
2564         update_curr(cfs_rq);
2565         enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
2566         account_entity_enqueue(cfs_rq, se);
2567         update_cfs_shares(cfs_rq);
2568
2569         if (flags & ENQUEUE_WAKEUP) {
2570                 place_entity(cfs_rq, se, 0);
2571                 enqueue_sleeper(cfs_rq, se);
2572         }
2573
2574         update_stats_enqueue(cfs_rq, se);
2575         check_spread(cfs_rq, se);
2576         if (se != cfs_rq->curr)
2577                 __enqueue_entity(cfs_rq, se);
2578         se->on_rq = 1;
2579
2580         if (cfs_rq->nr_running == 1) {
2581                 list_add_leaf_cfs_rq(cfs_rq);
2582                 check_enqueue_throttle(cfs_rq);
2583         }
2584 }
2585
2586 static void __clear_buddies_last(struct sched_entity *se)
2587 {
2588         for_each_sched_entity(se) {
2589                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2590                 if (cfs_rq->last == se)
2591                         cfs_rq->last = NULL;
2592                 else
2593                         break;
2594         }
2595 }
2596
2597 static void __clear_buddies_next(struct sched_entity *se)
2598 {
2599         for_each_sched_entity(se) {
2600                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2601                 if (cfs_rq->next == se)
2602                         cfs_rq->next = NULL;
2603                 else
2604                         break;
2605         }
2606 }
2607
2608 static void __clear_buddies_skip(struct sched_entity *se)
2609 {
2610         for_each_sched_entity(se) {
2611                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2612                 if (cfs_rq->skip == se)
2613                         cfs_rq->skip = NULL;
2614                 else
2615                         break;
2616         }
2617 }
2618
2619 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
2620 {
2621         if (cfs_rq->last == se)
2622                 __clear_buddies_last(se);
2623
2624         if (cfs_rq->next == se)
2625                 __clear_buddies_next(se);
2626
2627         if (cfs_rq->skip == se)
2628                 __clear_buddies_skip(se);
2629 }
2630
2631 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
2632
2633 static void
2634 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2635 {
2636         /*
2637          * Update run-time statistics of the 'current'.
2638          */
2639         update_curr(cfs_rq);
2640         dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP);
2641
2642         update_stats_dequeue(cfs_rq, se);
2643         if (flags & DEQUEUE_SLEEP) {
2644 #ifdef CONFIG_SCHEDSTATS
2645                 if (entity_is_task(se)) {
2646                         struct task_struct *tsk = task_of(se);
2647
2648                         if (tsk->state & TASK_INTERRUPTIBLE)
2649                                 se->statistics.sleep_start = rq_clock(rq_of(cfs_rq));
2650                         if (tsk->state & TASK_UNINTERRUPTIBLE)
2651                                 se->statistics.block_start = rq_clock(rq_of(cfs_rq));
2652                 }
2653 #endif
2654         }
2655
2656         clear_buddies(cfs_rq, se);
2657
2658         if (se != cfs_rq->curr)
2659                 __dequeue_entity(cfs_rq, se);
2660         se->on_rq = 0;
2661         account_entity_dequeue(cfs_rq, se);
2662
2663         /*
2664          * Normalize the entity after updating the min_vruntime because the
2665          * update can refer to the ->curr item and we need to reflect this
2666          * movement in our normalized position.
2667          */
2668         if (!(flags & DEQUEUE_SLEEP))
2669                 se->vruntime -= cfs_rq->min_vruntime;
2670
2671         /* return excess runtime on last dequeue */
2672         return_cfs_rq_runtime(cfs_rq);
2673
2674         update_min_vruntime(cfs_rq);
2675         update_cfs_shares(cfs_rq);
2676 }
2677
2678 /*
2679  * Preempt the current task with a newly woken task if needed:
2680  */
2681 static void
2682 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
2683 {
2684         unsigned long ideal_runtime, delta_exec;
2685         struct sched_entity *se;
2686         s64 delta;
2687
2688         ideal_runtime = sched_slice(cfs_rq, curr);
2689         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
2690         if (delta_exec > ideal_runtime) {
2691                 resched_task(rq_of(cfs_rq)->curr);
2692                 /*
2693                  * The current task ran long enough, ensure it doesn't get
2694                  * re-elected due to buddy favours.
2695                  */
2696                 clear_buddies(cfs_rq, curr);
2697                 return;
2698         }
2699
2700         /*
2701          * Ensure that a task that missed wakeup preemption by a
2702          * narrow margin doesn't have to wait for a full slice.
2703          * This also mitigates buddy induced latencies under load.
2704          */
2705         if (delta_exec < sysctl_sched_min_granularity)
2706                 return;
2707
2708         se = __pick_first_entity(cfs_rq);
2709         delta = curr->vruntime - se->vruntime;
2710
2711         if (delta < 0)
2712                 return;
2713
2714         if (delta > ideal_runtime)
2715                 resched_task(rq_of(cfs_rq)->curr);
2716 }
2717
2718 static void
2719 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
2720 {
2721         /* 'current' is not kept within the tree. */
2722         if (se->on_rq) {
2723                 /*
2724                  * Any task has to be enqueued before it get to execute on
2725                  * a CPU. So account for the time it spent waiting on the
2726                  * runqueue.
2727                  */
2728                 update_stats_wait_end(cfs_rq, se);
2729                 __dequeue_entity(cfs_rq, se);
2730         }
2731
2732         update_stats_curr_start(cfs_rq, se);
2733         cfs_rq->curr = se;
2734 #ifdef CONFIG_SCHEDSTATS
2735         /*
2736          * Track our maximum slice length, if the CPU's load is at
2737          * least twice that of our own weight (i.e. dont track it
2738          * when there are only lesser-weight tasks around):
2739          */
2740         if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
2741                 se->statistics.slice_max = max(se->statistics.slice_max,
2742                         se->sum_exec_runtime - se->prev_sum_exec_runtime);
2743         }
2744 #endif
2745         se->prev_sum_exec_runtime = se->sum_exec_runtime;
2746 }
2747
2748 static int
2749 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
2750
2751 /*
2752  * Pick the next process, keeping these things in mind, in this order:
2753  * 1) keep things fair between processes/task groups
2754  * 2) pick the "next" process, since someone really wants that to run
2755  * 3) pick the "last" process, for cache locality
2756  * 4) do not run the "skip" process, if something else is available
2757  */
2758 static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
2759 {
2760         struct sched_entity *se = __pick_first_entity(cfs_rq);
2761         struct sched_entity *left = se;
2762
2763         /*
2764          * Avoid running the skip buddy, if running something else can
2765          * be done without getting too unfair.
2766          */
2767         if (cfs_rq->skip == se) {
2768                 struct sched_entity *second = __pick_next_entity(se);
2769                 if (second && wakeup_preempt_entity(second, left) < 1)
2770                         se = second;
2771         }
2772
2773         /*
2774          * Prefer last buddy, try to return the CPU to a preempted task.
2775          */
2776         if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
2777                 se = cfs_rq->last;
2778
2779         /*
2780          * Someone really wants this to run. If it's not unfair, run it.
2781          */
2782         if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
2783                 se = cfs_rq->next;
2784
2785         clear_buddies(cfs_rq, se);
2786
2787         return se;
2788 }
2789
2790 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
2791
2792 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
2793 {
2794         /*
2795          * If still on the runqueue then deactivate_task()
2796          * was not called and update_curr() has to be done:
2797          */
2798         if (prev->on_rq)
2799                 update_curr(cfs_rq);
2800
2801         /* throttle cfs_rqs exceeding runtime */
2802         check_cfs_rq_runtime(cfs_rq);
2803
2804         check_spread(cfs_rq, prev);
2805         if (prev->on_rq) {
2806                 update_stats_wait_start(cfs_rq, prev);
2807                 /* Put 'current' back into the tree. */
2808                 __enqueue_entity(cfs_rq, prev);
2809                 /* in !on_rq case, update occurred at dequeue */
2810                 update_entity_load_avg(prev, 1);
2811         }
2812         cfs_rq->curr = NULL;
2813 }
2814
2815 static void
2816 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
2817 {
2818         /*
2819          * Update run-time statistics of the 'current'.
2820          */
2821         update_curr(cfs_rq);
2822
2823         /*
2824          * Ensure that runnable average is periodically updated.
2825          */
2826         update_entity_load_avg(curr, 1);
2827         update_cfs_rq_blocked_load(cfs_rq, 1);
2828         update_cfs_shares(cfs_rq);
2829
2830 #ifdef CONFIG_SCHED_HRTICK
2831         /*
2832          * queued ticks are scheduled to match the slice, so don't bother
2833          * validating it and just reschedule.
2834          */
2835         if (queued) {
2836                 resched_task(rq_of(cfs_rq)->curr);
2837                 return;
2838         }
2839         /*
2840          * don't let the period tick interfere with the hrtick preemption
2841          */
2842         if (!sched_feat(DOUBLE_TICK) &&
2843                         hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
2844                 return;
2845 #endif
2846
2847         if (cfs_rq->nr_running > 1)
2848                 check_preempt_tick(cfs_rq, curr);
2849 }
2850
2851
2852 /**************************************************
2853  * CFS bandwidth control machinery
2854  */
2855
2856 #ifdef CONFIG_CFS_BANDWIDTH
2857
2858 #ifdef HAVE_JUMP_LABEL
2859 static struct static_key __cfs_bandwidth_used;
2860
2861 static inline bool cfs_bandwidth_used(void)
2862 {
2863         return static_key_false(&__cfs_bandwidth_used);
2864 }
2865
2866 void cfs_bandwidth_usage_inc(void)
2867 {
2868         static_key_slow_inc(&__cfs_bandwidth_used);
2869 }
2870
2871 void cfs_bandwidth_usage_dec(void)
2872 {
2873         static_key_slow_dec(&__cfs_bandwidth_used);
2874 }
2875 #else /* HAVE_JUMP_LABEL */
2876 static bool cfs_bandwidth_used(void)
2877 {
2878         return true;
2879 }
2880
2881 void cfs_bandwidth_usage_inc(void) {}
2882 void cfs_bandwidth_usage_dec(void) {}
2883 #endif /* HAVE_JUMP_LABEL */
2884
2885 /*
2886  * default period for cfs group bandwidth.
2887  * default: 0.1s, units: nanoseconds
2888  */
2889 static inline u64 default_cfs_period(void)
2890 {
2891         return 100000000ULL;
2892 }
2893
2894 static inline u64 sched_cfs_bandwidth_slice(void)
2895 {
2896         return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
2897 }
2898
2899 /*
2900  * Replenish runtime according to assigned quota and update expiration time.
2901  * We use sched_clock_cpu directly instead of rq->clock to avoid adding
2902  * additional synchronization around rq->lock.
2903  *
2904  * requires cfs_b->lock
2905  */
2906 void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b)
2907 {
2908         u64 now;
2909
2910         if (cfs_b->quota == RUNTIME_INF)
2911                 return;
2912
2913         now = sched_clock_cpu(smp_processor_id());
2914         cfs_b->runtime = cfs_b->quota;
2915         cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period);
2916 }
2917
2918 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
2919 {
2920         return &tg->cfs_bandwidth;
2921 }
2922
2923 /* rq->task_clock normalized against any time this cfs_rq has spent throttled */
2924 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
2925 {
2926         if (unlikely(cfs_rq->throttle_count))
2927                 return cfs_rq->throttled_clock_task;
2928
2929         return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
2930 }
2931
2932 /* returns 0 on failure to allocate runtime */
2933 static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
2934 {
2935         struct task_group *tg = cfs_rq->tg;
2936         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
2937         u64 amount = 0, min_amount, expires;
2938
2939         /* note: this is a positive sum as runtime_remaining <= 0 */
2940         min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;
2941
2942         raw_spin_lock(&cfs_b->lock);
2943         if (cfs_b->quota == RUNTIME_INF)
2944                 amount = min_amount;
2945         else {
2946                 /*
2947                  * If the bandwidth pool has become inactive, then at least one
2948                  * period must have elapsed since the last consumption.
2949                  * Refresh the global state and ensure bandwidth timer becomes
2950                  * active.
2951                  */
2952                 if (!cfs_b->timer_active) {
2953                         __refill_cfs_bandwidth_runtime(cfs_b);
2954                         __start_cfs_bandwidth(cfs_b);
2955                 }
2956
2957                 if (cfs_b->runtime > 0) {
2958                         amount = min(cfs_b->runtime, min_amount);
2959                         cfs_b->runtime -= amount;
2960                         cfs_b->idle = 0;
2961                 }
2962         }
2963         expires = cfs_b->runtime_expires;
2964         raw_spin_unlock(&cfs_b->lock);
2965
2966         cfs_rq->runtime_remaining += amount;
2967         /*
2968          * we may have advanced our local expiration to account for allowed
2969          * spread between our sched_clock and the one on which runtime was
2970          * issued.
2971          */
2972         if ((s64)(expires - cfs_rq->runtime_expires) > 0)
2973                 cfs_rq->runtime_expires = expires;
2974
2975         return cfs_rq->runtime_remaining > 0;
2976 }
2977
2978 /*
2979  * Note: This depends on the synchronization provided by sched_clock and the
2980  * fact that rq->clock snapshots this value.
2981  */
2982 static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
2983 {
2984         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
2985
2986         /* if the deadline is ahead of our clock, nothing to do */
2987         if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
2988                 return;
2989
2990         if (cfs_rq->runtime_remaining < 0)
2991                 return;
2992
2993         /*
2994          * If the local deadline has passed we have to consider the
2995          * possibility that our sched_clock is 'fast' and the global deadline
2996          * has not truly expired.
2997          *
2998          * Fortunately we can check determine whether this the case by checking
2999          * whether the global deadline has advanced.
3000          */
3001
3002         if ((s64)(cfs_rq->runtime_expires - cfs_b->runtime_expires) >= 0) {
3003                 /* extend local deadline, drift is bounded above by 2 ticks */
3004                 cfs_rq->runtime_expires += TICK_NSEC;
3005         } else {
3006                 /* global deadline is ahead, expiration has passed */
3007                 cfs_rq->runtime_remaining = 0;
3008         }
3009 }
3010
3011 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3012 {
3013         /* dock delta_exec before expiring quota (as it could span periods) */
3014         cfs_rq->runtime_remaining -= delta_exec;
3015         expire_cfs_rq_runtime(cfs_rq);
3016
3017         if (likely(cfs_rq->runtime_remaining > 0))
3018                 return;
3019
3020         /*
3021          * if we're unable to extend our runtime we resched so that the active
3022          * hierarchy can be throttled
3023          */
3024         if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
3025                 resched_task(rq_of(cfs_rq)->curr);
3026 }
3027
3028 static __always_inline
3029 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3030 {
3031         if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
3032                 return;
3033
3034         __account_cfs_rq_runtime(cfs_rq, delta_exec);
3035 }
3036
3037 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3038 {
3039         return cfs_bandwidth_used() && cfs_rq->throttled;
3040 }
3041
3042 /* check whether cfs_rq, or any parent, is throttled */
3043 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3044 {
3045         return cfs_bandwidth_used() && cfs_rq->throttle_count;
3046 }
3047
3048 /*
3049  * Ensure that neither of the group entities corresponding to src_cpu or
3050  * dest_cpu are members of a throttled hierarchy when performing group
3051  * load-balance operations.
3052  */
3053 static inline int throttled_lb_pair(struct task_group *tg,
3054                                     int src_cpu, int dest_cpu)
3055 {
3056         struct cfs_rq *src_cfs_rq, *dest_cfs_rq;
3057
3058         src_cfs_rq = tg->cfs_rq[src_cpu];
3059         dest_cfs_rq = tg->cfs_rq[dest_cpu];
3060
3061         return throttled_hierarchy(src_cfs_rq) ||
3062                throttled_hierarchy(dest_cfs_rq);
3063 }
3064
3065 /* updated child weight may affect parent so we have to do this bottom up */
3066 static int tg_unthrottle_up(struct task_group *tg, void *data)
3067 {
3068         struct rq *rq = data;
3069         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3070
3071         cfs_rq->throttle_count--;
3072 #ifdef CONFIG_SMP
3073         if (!cfs_rq->throttle_count) {
3074                 /* adjust cfs_rq_clock_task() */
3075                 cfs_rq->throttled_clock_task_time += rq_clock_task(rq) -
3076                                              cfs_rq->throttled_clock_task;
3077         }
3078 #endif
3079
3080         return 0;
3081 }
3082
3083 static int tg_throttle_down(struct task_group *tg, void *data)
3084 {
3085         struct rq *rq = data;
3086         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3087
3088         /* group is entering throttled state, stop time */
3089         if (!cfs_rq->throttle_count)
3090                 cfs_rq->throttled_clock_task = rq_clock_task(rq);
3091         cfs_rq->throttle_count++;
3092
3093         return 0;
3094 }
3095
3096 static void throttle_cfs_rq(struct cfs_rq *cfs_rq)
3097 {
3098         struct rq *rq = rq_of(cfs_rq);
3099         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3100         struct sched_entity *se;
3101         long task_delta, dequeue = 1;
3102
3103         se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
3104
3105         /* freeze hierarchy runnable averages while throttled */
3106         rcu_read_lock();
3107         walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
3108         rcu_read_unlock();
3109
3110         task_delta = cfs_rq->h_nr_running;
3111         for_each_sched_entity(se) {
3112                 struct cfs_rq *qcfs_rq = cfs_rq_of(se);
3113                 /* throttled entity or throttle-on-deactivate */
3114                 if (!se->on_rq)
3115                         break;
3116
3117                 if (dequeue)
3118                         dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
3119                 qcfs_rq->h_nr_running -= task_delta;
3120
3121                 if (qcfs_rq->load.weight)
3122                         dequeue = 0;
3123         }
3124
3125         if (!se)
3126                 rq->nr_running -= task_delta;
3127
3128         cfs_rq->throttled = 1;
3129         cfs_rq->throttled_clock = rq_clock(rq);
3130         raw_spin_lock(&cfs_b->lock);
3131         list_add_tail_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq);
3132         if (!cfs_b->timer_active)
3133                 __start_cfs_bandwidth(cfs_b);
3134         raw_spin_unlock(&cfs_b->lock);
3135 }
3136
3137 void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
3138 {
3139         struct rq *rq = rq_of(cfs_rq);
3140         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3141         struct sched_entity *se;
3142         int enqueue = 1;
3143         long task_delta;
3144
3145         se = cfs_rq->tg->se[cpu_of(rq)];
3146
3147         cfs_rq->throttled = 0;
3148
3149         update_rq_clock(rq);
3150
3151         raw_spin_lock(&cfs_b->lock);
3152         cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
3153         list_del_rcu(&cfs_rq->throttled_list);
3154         raw_spin_unlock(&cfs_b->lock);
3155
3156         /* update hierarchical throttle state */
3157         walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
3158
3159         if (!cfs_rq->load.weight)
3160                 return;
3161
3162         task_delta = cfs_rq->h_nr_running;
3163         for_each_sched_entity(se) {
3164                 if (se->on_rq)
3165                         enqueue = 0;
3166
3167                 cfs_rq = cfs_rq_of(se);
3168                 if (enqueue)
3169                         enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);
3170                 cfs_rq->h_nr_running += task_delta;
3171
3172                 if (cfs_rq_throttled(cfs_rq))
3173                         break;
3174         }
3175
3176         if (!se)
3177                 rq->nr_running += task_delta;
3178
3179         /* determine whether we need to wake up potentially idle cpu */
3180         if (rq->curr == rq->idle && rq->cfs.nr_running)
3181                 resched_task(rq->curr);
3182 }
3183
3184 static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b,
3185                 u64 remaining, u64 expires)
3186 {
3187         struct cfs_rq *cfs_rq;
3188         u64 runtime = remaining;
3189
3190         rcu_read_lock();
3191         list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
3192                                 throttled_list) {
3193                 struct rq *rq = rq_of(cfs_rq);
3194
3195                 raw_spin_lock(&rq->lock);
3196                 if (!cfs_rq_throttled(cfs_rq))
3197                         goto next;
3198
3199                 runtime = -cfs_rq->runtime_remaining + 1;
3200                 if (runtime > remaining)
3201                         runtime = remaining;
3202                 remaining -= runtime;
3203
3204                 cfs_rq->runtime_remaining += runtime;
3205                 cfs_rq->runtime_expires = expires;
3206
3207                 /* we check whether we're throttled above */
3208                 if (cfs_rq->runtime_remaining > 0)
3209                         unthrottle_cfs_rq(cfs_rq);
3210
3211 next:
3212                 raw_spin_unlock(&rq->lock);
3213
3214                 if (!remaining)
3215                         break;
3216         }
3217         rcu_read_unlock();
3218
3219         return remaining;
3220 }
3221
3222 /*
3223  * Responsible for refilling a task_group's bandwidth and unthrottling its
3224  * cfs_rqs as appropriate. If there has been no activity within the last
3225  * period the timer is deactivated until scheduling resumes; cfs_b->idle is
3226  * used to track this state.
3227  */
3228 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
3229 {
3230         u64 runtime, runtime_expires;
3231         int idle = 1, throttled;
3232
3233         raw_spin_lock(&cfs_b->lock);
3234         /* no need to continue the timer with no bandwidth constraint */
3235         if (cfs_b->quota == RUNTIME_INF)
3236                 goto out_unlock;
3237
3238         throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3239         /* idle depends on !throttled (for the case of a large deficit) */
3240         idle = cfs_b->idle && !throttled;
3241         cfs_b->nr_periods += overrun;
3242
3243         /* if we're going inactive then everything else can be deferred */
3244         if (idle)
3245                 goto out_unlock;
3246
3247         /*
3248          * if we have relooped after returning idle once, we need to update our
3249          * status as actually running, so that other cpus doing
3250          * __start_cfs_bandwidth will stop trying to cancel us.
3251          */
3252         cfs_b->timer_active = 1;
3253
3254         __refill_cfs_bandwidth_runtime(cfs_b);
3255
3256         if (!throttled) {
3257                 /* mark as potentially idle for the upcoming period */
3258                 cfs_b->idle = 1;
3259                 goto out_unlock;
3260         }
3261
3262         /* account preceding periods in which throttling occurred */
3263         cfs_b->nr_throttled += overrun;
3264
3265         /*
3266          * There are throttled entities so we must first use the new bandwidth
3267          * to unthrottle them before making it generally available.  This
3268          * ensures that all existing debts will be paid before a new cfs_rq is
3269          * allowed to run.
3270          */
3271         runtime = cfs_b->runtime;
3272         runtime_expires = cfs_b->runtime_expires;
3273         cfs_b->runtime = 0;
3274
3275         /*
3276          * This check is repeated as we are holding onto the new bandwidth
3277          * while we unthrottle.  This can potentially race with an unthrottled
3278          * group trying to acquire new bandwidth from the global pool.
3279          */
3280         while (throttled && runtime > 0) {
3281                 raw_spin_unlock(&cfs_b->lock);
3282                 /* we can't nest cfs_b->lock while distributing bandwidth */
3283                 runtime = distribute_cfs_runtime(cfs_b, runtime,
3284                                                  runtime_expires);
3285                 raw_spin_lock(&cfs_b->lock);
3286
3287                 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3288         }
3289
3290         /* return (any) remaining runtime */
3291         cfs_b->runtime = runtime;
3292         /*
3293          * While we are ensured activity in the period following an
3294          * unthrottle, this also covers the case in which the new bandwidth is
3295          * insufficient to cover the existing bandwidth deficit.  (Forcing the
3296          * timer to remain active while there are any throttled entities.)
3297          */
3298         cfs_b->idle = 0;
3299 out_unlock:
3300         if (idle)
3301                 cfs_b->timer_active = 0;
3302         raw_spin_unlock(&cfs_b->lock);
3303
3304         return idle;
3305 }
3306
3307 /* a cfs_rq won't donate quota below this amount */
3308 static const u64 min_cfs_rq_runtime = 1 * NSEC_PER_MSEC;
3309 /* minimum remaining period time to redistribute slack quota */
3310 static const u64 min_bandwidth_expiration = 2 * NSEC_PER_MSEC;
3311 /* how long we wait to gather additional slack before distributing */
3312 static const u64 cfs_bandwidth_slack_period = 5 * NSEC_PER_MSEC;
3313
3314 /*
3315  * Are we near the end of the current quota period?
3316  *
3317  * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the
3318  * hrtimer base being cleared by __hrtimer_start_range_ns. In the case of
3319  * migrate_hrtimers, base is never cleared, so we are fine.
3320  */
3321 static int runtime_refresh_within(struct cfs_bandwidth *cfs_b, u64 min_expire)
3322 {
3323         struct hrtimer *refresh_timer = &cfs_b->period_timer;
3324         u64 remaining;
3325
3326         /* if the call-back is running a quota refresh is already occurring */
3327         if (hrtimer_callback_running(refresh_timer))
3328                 return 1;
3329
3330         /* is a quota refresh about to occur? */
3331         remaining = ktime_to_ns(hrtimer_expires_remaining(refresh_timer));
3332         if (remaining < min_expire)
3333                 return 1;
3334
3335         return 0;
3336 }
3337
3338 static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
3339 {
3340         u64 min_left = cfs_bandwidth_slack_period + min_bandwidth_expiration;
3341
3342         /* if there's a quota refresh soon don't bother with slack */
3343         if (runtime_refresh_within(cfs_b, min_left))
3344                 return;
3345
3346         start_bandwidth_timer(&cfs_b->slack_timer,
3347                                 ns_to_ktime(cfs_bandwidth_slack_period));
3348 }
3349
3350 /* we know any runtime found here is valid as update_curr() precedes return */
3351 static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3352 {
3353         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3354         s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;
3355
3356         if (slack_runtime <= 0)
3357                 return;
3358
3359         raw_spin_lock(&cfs_b->lock);
3360         if (cfs_b->quota != RUNTIME_INF &&
3361             cfs_rq->runtime_expires == cfs_b->runtime_expires) {
3362                 cfs_b->runtime += slack_runtime;
3363
3364                 /* we are under rq->lock, defer unthrottling using a timer */
3365                 if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
3366                     !list_empty(&cfs_b->throttled_cfs_rq))
3367                         start_cfs_slack_bandwidth(cfs_b);
3368         }
3369         raw_spin_unlock(&cfs_b->lock);
3370
3371         /* even if it's not valid for return we don't want to try again */
3372         cfs_rq->runtime_remaining -= slack_runtime;
3373 }
3374
3375 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3376 {
3377         if (!cfs_bandwidth_used())
3378                 return;
3379
3380         if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
3381                 return;
3382
3383         __return_cfs_rq_runtime(cfs_rq);
3384 }
3385
3386 /*
3387  * This is done with a timer (instead of inline with bandwidth return) since
3388  * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs.
3389  */
3390 static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
3391 {
3392         u64 runtime = 0, slice = sched_cfs_bandwidth_slice();
3393         u64 expires;
3394
3395         /* confirm we're still not at a refresh boundary */
3396         raw_spin_lock(&cfs_b->lock);
3397         if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) {
3398                 raw_spin_unlock(&cfs_b->lock);
3399                 return;
3400         }
3401
3402         if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice) {
3403                 runtime = cfs_b->runtime;
3404                 cfs_b->runtime = 0;
3405         }
3406         expires = cfs_b->runtime_expires;
3407         raw_spin_unlock(&cfs_b->lock);
3408
3409         if (!runtime)
3410                 return;
3411
3412         runtime = distribute_cfs_runtime(cfs_b, runtime, expires);
3413
3414         raw_spin_lock(&cfs_b->lock);
3415         if (expires == cfs_b->runtime_expires)
3416                 cfs_b->runtime = runtime;
3417         raw_spin_unlock(&cfs_b->lock);
3418 }
3419
3420 /*
3421  * When a group wakes up we want to make sure that its quota is not already
3422  * expired/exceeded, otherwise it may be allowed to steal additional ticks of
3423  * runtime as update_curr() throttling can not not trigger until it's on-rq.
3424  */
3425 static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
3426 {
3427         if (!cfs_bandwidth_used())
3428                 return;
3429
3430         /* an active group must be handled by the update_curr()->put() path */
3431         if (!cfs_rq->runtime_enabled || cfs_rq->curr)
3432                 return;
3433
3434         /* ensure the group is not already throttled */
3435         if (cfs_rq_throttled(cfs_rq))
3436                 return;
3437
3438         /* update runtime allocation */
3439         account_cfs_rq_runtime(cfs_rq, 0);
3440         if (cfs_rq->runtime_remaining <= 0)
3441                 throttle_cfs_rq(cfs_rq);
3442 }
3443
3444 /* conditionally throttle active cfs_rq's from put_prev_entity() */
3445 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3446 {
3447         if (!cfs_bandwidth_used())
3448                 return;
3449
3450         if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
3451                 return;
3452
3453         /*
3454          * it's possible for a throttled entity to be forced into a running
3455          * state (e.g. set_curr_task), in this case we're finished.
3456          */
3457         if (cfs_rq_throttled(cfs_rq))
3458                 return;
3459
3460         throttle_cfs_rq(cfs_rq);
3461 }
3462
3463 static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer)
3464 {
3465         struct cfs_bandwidth *cfs_b =
3466                 container_of(timer, struct cfs_bandwidth, slack_timer);
3467         do_sched_cfs_slack_timer(cfs_b);
3468
3469         return HRTIMER_NORESTART;
3470 }
3471
3472 static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
3473 {
3474         struct cfs_bandwidth *cfs_b =
3475                 container_of(timer, struct cfs_bandwidth, period_timer);
3476         ktime_t now;
3477         int overrun;
3478         int idle = 0;
3479
3480         for (;;) {
3481                 now = hrtimer_cb_get_time(timer);
3482                 overrun = hrtimer_forward(timer, now, cfs_b->period);
3483
3484                 if (!overrun)
3485                         break;
3486
3487                 idle = do_sched_cfs_period_timer(cfs_b, overrun);
3488         }
3489
3490         return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
3491 }
3492
3493 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3494 {
3495         raw_spin_lock_init(&cfs_b->lock);
3496         cfs_b->runtime = 0;
3497         cfs_b->quota = RUNTIME_INF;
3498         cfs_b->period = ns_to_ktime(default_cfs_period());
3499
3500         INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
3501         hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3502         cfs_b->period_timer.function = sched_cfs_period_timer;
3503         hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3504         cfs_b->slack_timer.function = sched_cfs_slack_timer;
3505 }
3506
3507 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3508 {
3509         cfs_rq->runtime_enabled = 0;
3510         INIT_LIST_HEAD(&cfs_rq->throttled_list);
3511 }
3512
3513 /* requires cfs_b->lock, may release to reprogram timer */
3514 void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3515 {
3516         /*
3517          * The timer may be active because we're trying to set a new bandwidth
3518          * period or because we're racing with the tear-down path
3519          * (timer_active==0 becomes visible before the hrtimer call-back
3520          * terminates).  In either case we ensure that it's re-programmed
3521          */
3522         while (unlikely(hrtimer_active(&cfs_b->period_timer)) &&
3523                hrtimer_try_to_cancel(&cfs_b->period_timer) < 0) {
3524                 /* bounce the lock to allow do_sched_cfs_period_timer to run */
3525                 raw_spin_unlock(&cfs_b->lock);
3526                 cpu_relax();
3527                 raw_spin_lock(&cfs_b->lock);
3528                 /* if someone else restarted the timer then we're done */
3529                 if (cfs_b->timer_active)
3530                         return;
3531         }
3532
3533         cfs_b->timer_active = 1;
3534         start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
3535 }
3536
3537 static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3538 {
3539         hrtimer_cancel(&cfs_b->period_timer);
3540         hrtimer_cancel(&cfs_b->slack_timer);
3541 }
3542
3543 static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq)
3544 {
3545         struct cfs_rq *cfs_rq;
3546
3547         for_each_leaf_cfs_rq(rq, cfs_rq) {
3548                 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3549
3550                 if (!cfs_rq->runtime_enabled)
3551                         continue;
3552
3553                 /*
3554                  * clock_task is not advancing so we just need to make sure
3555                  * there's some valid quota amount
3556                  */
3557                 cfs_rq->runtime_remaining = cfs_b->quota;
3558                 if (cfs_rq_throttled(cfs_rq))
3559                         unthrottle_cfs_rq(cfs_rq);
3560         }
3561 }
3562
3563 #else /* CONFIG_CFS_BANDWIDTH */
3564 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
3565 {
3566         return rq_clock_task(rq_of(cfs_rq));
3567 }
3568
3569 static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) {}
3570 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3571 static void check_enqueue_throttle(struct cfs_rq *cfs_rq) {}
3572 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3573
3574 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3575 {
3576         return 0;
3577 }
3578
3579 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3580 {
3581         return 0;
3582 }
3583
3584 static inline int throttled_lb_pair(struct task_group *tg,
3585                                     int src_cpu, int dest_cpu)
3586 {
3587         return 0;
3588 }
3589
3590 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
3591
3592 #ifdef CONFIG_FAIR_GROUP_SCHED
3593 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3594 #endif
3595
3596 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
3597 {
3598         return NULL;
3599 }
3600 static inline void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
3601 static inline void unthrottle_offline_cfs_rqs(struct rq *rq) {}
3602
3603 #endif /* CONFIG_CFS_BANDWIDTH */
3604
3605 /**************************************************
3606  * CFS operations on tasks:
3607  */
3608
3609 #ifdef CONFIG_SCHED_HRTICK
3610 static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
3611 {
3612         struct sched_entity *se = &p->se;
3613         struct cfs_rq *cfs_rq = cfs_rq_of(se);
3614
3615         WARN_ON(task_rq(p) != rq);
3616
3617         if (cfs_rq->nr_running > 1) {
3618                 u64 slice = sched_slice(cfs_rq, se);
3619                 u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
3620                 s64 delta = slice - ran;
3621
3622                 if (delta < 0) {
3623                         if (rq->curr == p)
3624                                 resched_task(p);
3625                         return;
3626                 }
3627
3628                 /*
3629                  * Don't schedule slices shorter than 10000ns, that just
3630                  * doesn't make sense. Rely on vruntime for fairness.
3631                  */
3632                 if (rq->curr != p)
3633                         delta = max_t(s64, 10000LL, delta);
3634
3635                 hrtick_start(rq, delta);
3636         }
3637 }
3638
3639 /*
3640  * called from enqueue/dequeue and updates the hrtick when the
3641  * current task is from our class and nr_running is low enough
3642  * to matter.
3643  */
3644 static void hrtick_update(struct rq *rq)
3645 {
3646         struct task_struct *curr = rq->curr;
3647
3648         if (!hrtick_enabled(rq) || curr->sched_class != &fair_sched_class)
3649                 return;
3650
3651         if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
3652                 hrtick_start_fair(rq, curr);
3653 }
3654 #else /* !CONFIG_SCHED_HRTICK */
3655 static inline void
3656 hrtick_start_fair(struct rq *rq, struct task_struct *p)
3657 {
3658 }
3659
3660 static inline void hrtick_update(struct rq *rq)
3661 {
3662 }
3663 #endif
3664
3665 /*
3666  * The enqueue_task method is called before nr_running is
3667  * increased. Here we update the fair scheduling stats and
3668  * then put the task into the rbtree:
3669  */
3670 static void
3671 enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
3672 {
3673         struct cfs_rq *cfs_rq;
3674         struct sched_entity *se = &p->se;
3675
3676         for_each_sched_entity(se) {
3677                 if (se->on_rq)
3678                         break;
3679                 cfs_rq = cfs_rq_of(se);
3680                 enqueue_entity(cfs_rq, se, flags);
3681
3682                 /*
3683                  * end evaluation on encountering a throttled cfs_rq
3684                  *
3685                  * note: in the case of encountering a throttled cfs_rq we will
3686                  * post the final h_nr_running increment below.
3687                 */
3688                 if (cfs_rq_throttled(cfs_rq))
3689                         break;
3690                 cfs_rq->h_nr_running++;
3691
3692                 flags = ENQUEUE_WAKEUP;
3693         }
3694
3695         for_each_sched_entity(se) {
3696                 cfs_rq = cfs_rq_of(se);
3697                 cfs_rq->h_nr_running++;
3698
3699                 if (cfs_rq_throttled(cfs_rq))
3700                         break;
3701
3702                 update_cfs_shares(cfs_rq);
3703                 update_entity_load_avg(se, 1);
3704         }
3705
3706         if (!se) {
3707                 update_rq_runnable_avg(rq, rq->nr_running);
3708                 inc_nr_running(rq);
3709         }
3710         hrtick_update(rq);
3711 }
3712
3713 static void set_next_buddy(struct sched_entity *se);
3714
3715 /*
3716  * The dequeue_task method is called before nr_running is
3717  * decreased. We remove the task from the rbtree and
3718  * update the fair scheduling stats:
3719  */
3720 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
3721 {
3722         struct cfs_rq *cfs_rq;
3723         struct sched_entity *se = &p->se;
3724         int task_sleep = flags & DEQUEUE_SLEEP;
3725
3726         for_each_sched_entity(se) {
3727                 cfs_rq = cfs_rq_of(se);
3728                 dequeue_entity(cfs_rq, se, flags);
3729
3730                 /*
3731                  * end evaluation on encountering a throttled cfs_rq
3732                  *
3733                  * note: in the case of encountering a throttled cfs_rq we will
3734                  * post the final h_nr_running decrement below.
3735                 */
3736                 if (cfs_rq_throttled(cfs_rq))
3737                         break;
3738                 cfs_rq->h_nr_running--;
3739
3740                 /* Don't dequeue parent if it has other entities besides us */
3741                 if (cfs_rq->load.weight) {
3742                         /*
3743                          * Bias pick_next to pick a task from this cfs_rq, as
3744                          * p is sleeping when it is within its sched_slice.
3745                          */
3746                         if (task_sleep && parent_entity(se))
3747                                 set_next_buddy(parent_entity(se));
3748
3749                         /* avoid re-evaluating load for this entity */
3750                         se = parent_entity(se);
3751                         break;
3752                 }
3753                 flags |= DEQUEUE_SLEEP;
3754         }
3755
3756         for_each_sched_entity(se) {
3757                 cfs_rq = cfs_rq_of(se);
3758                 cfs_rq->h_nr_running--;
3759
3760                 if (cfs_rq_throttled(cfs_rq))
3761                         break;
3762
3763                 update_cfs_shares(cfs_rq);
3764                 update_entity_load_avg(se, 1);
3765         }
3766
3767         if (!se) {
3768                 dec_nr_running(rq);
3769                 update_rq_runnable_avg(rq, 1);
3770         }
3771         hrtick_update(rq);
3772 }
3773
3774 #ifdef CONFIG_SMP
3775 /* Used instead of source_load when we know the type == 0 */
3776 static unsigned long weighted_cpuload(const int cpu)
3777 {
3778         return cpu_rq(cpu)->cfs.runnable_load_avg;
3779 }
3780
3781 /*
3782  * Return a low guess at the load of a migration-source cpu weighted
3783  * according to the scheduling class and "nice" value.
3784  *
3785  * We want to under-estimate the load of migration sources, to
3786  * balance conservatively.
3787  */
3788 static unsigned long source_load(int cpu, int type)
3789 {
3790         struct rq *rq = cpu_rq(cpu);
3791         unsigned long total = weighted_cpuload(cpu);
3792
3793         if (type == 0 || !sched_feat(LB_BIAS))
3794                 return total;
3795
3796         return min(rq->cpu_load[type-1], total);
3797 }
3798
3799 /*
3800  * Return a high guess at the load of a migration-target cpu weighted
3801  * according to the scheduling class and "nice" value.
3802  */
3803 static unsigned long target_load(int cpu, int type)
3804 {
3805         struct rq *rq = cpu_rq(cpu);
3806         unsigned long total = weighted_cpuload(cpu);
3807
3808         if (type == 0 || !sched_feat(LB_BIAS))
3809                 return total;
3810
3811         return max(rq->cpu_load[type-1], total);
3812 }
3813
3814 static unsigned long power_of(int cpu)
3815 {
3816         return cpu_rq(cpu)->cpu_power;
3817 }
3818
3819 static unsigned long cpu_avg_load_per_task(int cpu)
3820 {
3821         struct rq *rq = cpu_rq(cpu);
3822         unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
3823         unsigned long load_avg = rq->cfs.runnable_load_avg;
3824
3825         if (nr_running)
3826                 return load_avg / nr_running;
3827
3828         return 0;
3829 }
3830
3831 static void record_wakee(struct task_struct *p)
3832 {
3833         /*
3834          * Rough decay (wiping) for cost saving, don't worry
3835          * about the boundary, really active task won't care
3836          * about the loss.
3837          */
3838         if (jiffies > current->wakee_flip_decay_ts + HZ) {
3839                 current->wakee_flips = 0;
3840                 current->wakee_flip_decay_ts = jiffies;
3841         }
3842
3843         if (current->last_wakee != p) {
3844                 current->last_wakee = p;
3845                 current->wakee_flips++;
3846         }
3847 }
3848
3849 static void task_waking_fair(struct task_struct *p)
3850 {
3851         struct sched_entity *se = &p->se;
3852         struct cfs_rq *cfs_rq = cfs_rq_of(se);
3853         u64 min_vruntime;
3854
3855 #ifndef CONFIG_64BIT
3856         u64 min_vruntime_copy;
3857
3858         do {
3859                 min_vruntime_copy = cfs_rq->min_vruntime_copy;
3860                 smp_rmb();
3861                 min_vruntime = cfs_rq->min_vruntime;
3862         } while (min_vruntime != min_vruntime_copy);
3863 #else
3864         min_vruntime = cfs_rq->min_vruntime;
3865 #endif
3866
3867         se->vruntime -= min_vruntime;
3868         record_wakee(p);
3869 }
3870
3871 #ifdef CONFIG_FAIR_GROUP_SCHED
3872 /*
3873  * effective_load() calculates the load change as seen from the root_task_group
3874  *
3875  * Adding load to a group doesn't make a group heavier, but can cause movement
3876  * of group shares between cpus. Assuming the shares were perfectly aligned one
3877  * can calculate the shift in shares.
3878  *
3879  * Calculate the effective load difference if @wl is added (subtracted) to @tg
3880  * on this @cpu and results in a total addition (subtraction) of @wg to the
3881  * total group weight.
3882  *
3883  * Given a runqueue weight distribution (rw_i) we can compute a shares
3884  * distribution (s_i) using:
3885  *
3886  *   s_i = rw_i / \Sum rw_j                                             (1)
3887  *
3888  * Suppose we have 4 CPUs and our @tg is a direct child of the root group and
3889  * has 7 equal weight tasks, distributed as below (rw_i), with the resulting
3890  * shares distribution (s_i):
3891  *
3892  *   rw_i = {   2,   4,   1,   0 }
3893  *   s_i  = { 2/7, 4/7, 1/7,   0 }
3894  *
3895  * As per wake_affine() we're interested in the load of two CPUs (the CPU the
3896  * task used to run on and the CPU the waker is running on), we need to
3897  * compute the effect of waking a task on either CPU and, in case of a sync
3898  * wakeup, compute the effect of the current task going to sleep.
3899  *
3900  * So for a change of @wl to the local @cpu with an overall group weight change
3901  * of @wl we can compute the new shares distribution (s'_i) using:
3902  *
3903  *   s'_i = (rw_i + @wl) / (@wg + \Sum rw_j)                            (2)
3904  *
3905  * Suppose we're interested in CPUs 0 and 1, and want to compute the load
3906  * differences in waking a task to CPU 0. The additional task changes the
3907  * weight and shares distributions like:
3908  *
3909  *   rw'_i = {   3,   4,   1,   0 }
3910  *   s'_i  = { 3/8, 4/8, 1/8,   0 }
3911  *
3912  * We can then compute the difference in effective weight by using:
3913  *
3914  *   dw_i = S * (s'_i - s_i)                                            (3)
3915  *
3916  * Where 'S' is the group weight as seen by its parent.
3917  *
3918  * Therefore the effective change in loads on CPU 0 would be 5/56 (3/8 - 2/7)
3919  * times the weight of the group. The effect on CPU 1 would be -4/56 (4/8 -
3920  * 4/7) times the weight of the group.
3921  */
3922 static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
3923 {
3924         struct sched_entity *se = tg->se[cpu];
3925
3926         if (!tg->parent)        /* the trivial, non-cgroup case */
3927                 return wl;
3928
3929         for_each_sched_entity(se) {
3930                 long w, W;
3931
3932                 tg = se->my_q->tg;
3933
3934                 /*
3935                  * W = @wg + \Sum rw_j
3936                  */
3937                 W = wg + calc_tg_weight(tg, se->my_q);
3938
3939                 /*
3940                  * w = rw_i + @wl
3941                  */
3942                 w = se->my_q->load.weight + wl;
3943
3944                 /*
3945                  * wl = S * s'_i; see (2)
3946                  */
3947                 if (W > 0 && w < W)
3948                         wl = (w * tg->shares) / W;
3949                 else
3950                         wl = tg->shares;
3951
3952                 /*
3953                  * Per the above, wl is the new se->load.weight value; since
3954                  * those are clipped to [MIN_SHARES, ...) do so now. See
3955                  * calc_cfs_shares().