Merge tag 'v3.14' 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 static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
876 {
877         rq->nr_numa_running += (p->numa_preferred_nid != -1);
878         rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
879 }
880
881 static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
882 {
883         rq->nr_numa_running -= (p->numa_preferred_nid != -1);
884         rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
885 }
886
887 struct numa_group {
888         atomic_t refcount;
889
890         spinlock_t lock; /* nr_tasks, tasks */
891         int nr_tasks;
892         pid_t gid;
893         struct list_head task_list;
894
895         struct rcu_head rcu;
896         unsigned long total_faults;
897         unsigned long faults[0];
898 };
899
900 pid_t task_numa_group_id(struct task_struct *p)
901 {
902         return p->numa_group ? p->numa_group->gid : 0;
903 }
904
905 static inline int task_faults_idx(int nid, int priv)
906 {
907         return 2 * nid + priv;
908 }
909
910 static inline unsigned long task_faults(struct task_struct *p, int nid)
911 {
912         if (!p->numa_faults)
913                 return 0;
914
915         return p->numa_faults[task_faults_idx(nid, 0)] +
916                 p->numa_faults[task_faults_idx(nid, 1)];
917 }
918
919 static inline unsigned long group_faults(struct task_struct *p, int nid)
920 {
921         if (!p->numa_group)
922                 return 0;
923
924         return p->numa_group->faults[task_faults_idx(nid, 0)] +
925                 p->numa_group->faults[task_faults_idx(nid, 1)];
926 }
927
928 /*
929  * These return the fraction of accesses done by a particular task, or
930  * task group, on a particular numa node.  The group weight is given a
931  * larger multiplier, in order to group tasks together that are almost
932  * evenly spread out between numa nodes.
933  */
934 static inline unsigned long task_weight(struct task_struct *p, int nid)
935 {
936         unsigned long total_faults;
937
938         if (!p->numa_faults)
939                 return 0;
940
941         total_faults = p->total_numa_faults;
942
943         if (!total_faults)
944                 return 0;
945
946         return 1000 * task_faults(p, nid) / total_faults;
947 }
948
949 static inline unsigned long group_weight(struct task_struct *p, int nid)
950 {
951         if (!p->numa_group || !p->numa_group->total_faults)
952                 return 0;
953
954         return 1000 * group_faults(p, nid) / p->numa_group->total_faults;
955 }
956
957 static unsigned long weighted_cpuload(const int cpu);
958 static unsigned long source_load(int cpu, int type);
959 static unsigned long target_load(int cpu, int type);
960 static unsigned long power_of(int cpu);
961 static long effective_load(struct task_group *tg, int cpu, long wl, long wg);
962
963 /* Cached statistics for all CPUs within a node */
964 struct numa_stats {
965         unsigned long nr_running;
966         unsigned long load;
967
968         /* Total compute capacity of CPUs on a node */
969         unsigned long power;
970
971         /* Approximate capacity in terms of runnable tasks on a node */
972         unsigned long capacity;
973         int has_capacity;
974 };
975
976 /*
977  * XXX borrowed from update_sg_lb_stats
978  */
979 static void update_numa_stats(struct numa_stats *ns, int nid)
980 {
981         int cpu, cpus = 0;
982
983         memset(ns, 0, sizeof(*ns));
984         for_each_cpu(cpu, cpumask_of_node(nid)) {
985                 struct rq *rq = cpu_rq(cpu);
986
987                 ns->nr_running += rq->nr_running;
988                 ns->load += weighted_cpuload(cpu);
989                 ns->power += power_of(cpu);
990
991                 cpus++;
992         }
993
994         /*
995          * If we raced with hotplug and there are no CPUs left in our mask
996          * the @ns structure is NULL'ed and task_numa_compare() will
997          * not find this node attractive.
998          *
999          * We'll either bail at !has_capacity, or we'll detect a huge imbalance
1000          * and bail there.
1001          */
1002         if (!cpus)
1003                 return;
1004
1005         ns->load = (ns->load * SCHED_POWER_SCALE) / ns->power;
1006         ns->capacity = DIV_ROUND_CLOSEST(ns->power, SCHED_POWER_SCALE);
1007         ns->has_capacity = (ns->nr_running < ns->capacity);
1008 }
1009
1010 struct task_numa_env {
1011         struct task_struct *p;
1012
1013         int src_cpu, src_nid;
1014         int dst_cpu, dst_nid;
1015
1016         struct numa_stats src_stats, dst_stats;
1017
1018         int imbalance_pct;
1019
1020         struct task_struct *best_task;
1021         long best_imp;
1022         int best_cpu;
1023 };
1024
1025 static void task_numa_assign(struct task_numa_env *env,
1026                              struct task_struct *p, long imp)
1027 {
1028         if (env->best_task)
1029                 put_task_struct(env->best_task);
1030         if (p)
1031                 get_task_struct(p);
1032
1033         env->best_task = p;
1034         env->best_imp = imp;
1035         env->best_cpu = env->dst_cpu;
1036 }
1037
1038 /*
1039  * This checks if the overall compute and NUMA accesses of the system would
1040  * be improved if the source tasks was migrated to the target dst_cpu taking
1041  * into account that it might be best if task running on the dst_cpu should
1042  * be exchanged with the source task
1043  */
1044 static void task_numa_compare(struct task_numa_env *env,
1045                               long taskimp, long groupimp)
1046 {
1047         struct rq *src_rq = cpu_rq(env->src_cpu);
1048         struct rq *dst_rq = cpu_rq(env->dst_cpu);
1049         struct task_struct *cur;
1050         long dst_load, src_load;
1051         long load;
1052         long imp = (groupimp > 0) ? groupimp : taskimp;
1053
1054         rcu_read_lock();
1055         cur = ACCESS_ONCE(dst_rq->curr);
1056         if (cur->pid == 0) /* idle */
1057                 cur = NULL;
1058
1059         /*
1060          * "imp" is the fault differential for the source task between the
1061          * source and destination node. Calculate the total differential for
1062          * the source task and potential destination task. The more negative
1063          * the value is, the more rmeote accesses that would be expected to
1064          * be incurred if the tasks were swapped.
1065          */
1066         if (cur) {
1067                 /* Skip this swap candidate if cannot move to the source cpu */
1068                 if (!cpumask_test_cpu(env->src_cpu, tsk_cpus_allowed(cur)))
1069                         goto unlock;
1070
1071                 /*
1072                  * If dst and source tasks are in the same NUMA group, or not
1073                  * in any group then look only at task weights.
1074                  */
1075                 if (cur->numa_group == env->p->numa_group) {
1076                         imp = taskimp + task_weight(cur, env->src_nid) -
1077                               task_weight(cur, env->dst_nid);
1078                         /*
1079                          * Add some hysteresis to prevent swapping the
1080                          * tasks within a group over tiny differences.
1081                          */
1082                         if (cur->numa_group)
1083                                 imp -= imp/16;
1084                 } else {
1085                         /*
1086                          * Compare the group weights. If a task is all by
1087                          * itself (not part of a group), use the task weight
1088                          * instead.
1089                          */
1090                         if (env->p->numa_group)
1091                                 imp = groupimp;
1092                         else
1093                                 imp = taskimp;
1094
1095                         if (cur->numa_group)
1096                                 imp += group_weight(cur, env->src_nid) -
1097                                        group_weight(cur, env->dst_nid);
1098                         else
1099                                 imp += task_weight(cur, env->src_nid) -
1100                                        task_weight(cur, env->dst_nid);
1101                 }
1102         }
1103
1104         if (imp < env->best_imp)
1105                 goto unlock;
1106
1107         if (!cur) {
1108                 /* Is there capacity at our destination? */
1109                 if (env->src_stats.has_capacity &&
1110                     !env->dst_stats.has_capacity)
1111                         goto unlock;
1112
1113                 goto balance;
1114         }
1115
1116         /* Balance doesn't matter much if we're running a task per cpu */
1117         if (src_rq->nr_running == 1 && dst_rq->nr_running == 1)
1118                 goto assign;
1119
1120         /*
1121          * In the overloaded case, try and keep the load balanced.
1122          */
1123 balance:
1124         dst_load = env->dst_stats.load;
1125         src_load = env->src_stats.load;
1126
1127         /* XXX missing power terms */
1128         load = task_h_load(env->p);
1129         dst_load += load;
1130         src_load -= load;
1131
1132         if (cur) {
1133                 load = task_h_load(cur);
1134                 dst_load -= load;
1135                 src_load += load;
1136         }
1137
1138         /* make src_load the smaller */
1139         if (dst_load < src_load)
1140                 swap(dst_load, src_load);
1141
1142         if (src_load * env->imbalance_pct < dst_load * 100)
1143                 goto unlock;
1144
1145 assign:
1146         task_numa_assign(env, cur, imp);
1147 unlock:
1148         rcu_read_unlock();
1149 }
1150
1151 static void task_numa_find_cpu(struct task_numa_env *env,
1152                                 long taskimp, long groupimp)
1153 {
1154         int cpu;
1155
1156         for_each_cpu(cpu, cpumask_of_node(env->dst_nid)) {
1157                 /* Skip this CPU if the source task cannot migrate */
1158                 if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(env->p)))
1159                         continue;
1160
1161                 env->dst_cpu = cpu;
1162                 task_numa_compare(env, taskimp, groupimp);
1163         }
1164 }
1165
1166 static int task_numa_migrate(struct task_struct *p)
1167 {
1168         struct task_numa_env env = {
1169                 .p = p,
1170
1171                 .src_cpu = task_cpu(p),
1172                 .src_nid = task_node(p),
1173
1174                 .imbalance_pct = 112,
1175
1176                 .best_task = NULL,
1177                 .best_imp = 0,
1178                 .best_cpu = -1
1179         };
1180         struct sched_domain *sd;
1181         unsigned long taskweight, groupweight;
1182         int nid, ret;
1183         long taskimp, groupimp;
1184
1185         /*
1186          * Pick the lowest SD_NUMA domain, as that would have the smallest
1187          * imbalance and would be the first to start moving tasks about.
1188          *
1189          * And we want to avoid any moving of tasks about, as that would create
1190          * random movement of tasks -- counter the numa conditions we're trying
1191          * to satisfy here.
1192          */
1193         rcu_read_lock();
1194         sd = rcu_dereference(per_cpu(sd_numa, env.src_cpu));
1195         if (sd)
1196                 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
1197         rcu_read_unlock();
1198
1199         /*
1200          * Cpusets can break the scheduler domain tree into smaller
1201          * balance domains, some of which do not cross NUMA boundaries.
1202          * Tasks that are "trapped" in such domains cannot be migrated
1203          * elsewhere, so there is no point in (re)trying.
1204          */
1205         if (unlikely(!sd)) {
1206                 p->numa_preferred_nid = task_node(p);
1207                 return -EINVAL;
1208         }
1209
1210         taskweight = task_weight(p, env.src_nid);
1211         groupweight = group_weight(p, env.src_nid);
1212         update_numa_stats(&env.src_stats, env.src_nid);
1213         env.dst_nid = p->numa_preferred_nid;
1214         taskimp = task_weight(p, env.dst_nid) - taskweight;
1215         groupimp = group_weight(p, env.dst_nid) - groupweight;
1216         update_numa_stats(&env.dst_stats, env.dst_nid);
1217
1218         /* If the preferred nid has capacity, try to use it. */
1219         if (env.dst_stats.has_capacity)
1220                 task_numa_find_cpu(&env, taskimp, groupimp);
1221
1222         /* No space available on the preferred nid. Look elsewhere. */
1223         if (env.best_cpu == -1) {
1224                 for_each_online_node(nid) {
1225                         if (nid == env.src_nid || nid == p->numa_preferred_nid)
1226                                 continue;
1227
1228                         /* Only consider nodes where both task and groups benefit */
1229                         taskimp = task_weight(p, nid) - taskweight;
1230                         groupimp = group_weight(p, nid) - groupweight;
1231                         if (taskimp < 0 && groupimp < 0)
1232                                 continue;
1233
1234                         env.dst_nid = nid;
1235                         update_numa_stats(&env.dst_stats, env.dst_nid);
1236                         task_numa_find_cpu(&env, taskimp, groupimp);
1237                 }
1238         }
1239
1240         /* No better CPU than the current one was found. */
1241         if (env.best_cpu == -1)
1242                 return -EAGAIN;
1243
1244         sched_setnuma(p, env.dst_nid);
1245
1246         /*
1247          * Reset the scan period if the task is being rescheduled on an
1248          * alternative node to recheck if the tasks is now properly placed.
1249          */
1250         p->numa_scan_period = task_scan_min(p);
1251
1252         if (env.best_task == NULL) {
1253                 ret = migrate_task_to(p, env.best_cpu);
1254                 if (ret != 0)
1255                         trace_sched_stick_numa(p, env.src_cpu, env.best_cpu);
1256                 return ret;
1257         }
1258
1259         ret = migrate_swap(p, env.best_task);
1260         if (ret != 0)
1261                 trace_sched_stick_numa(p, env.src_cpu, task_cpu(env.best_task));
1262         put_task_struct(env.best_task);
1263         return ret;
1264 }
1265
1266 /* Attempt to migrate a task to a CPU on the preferred node. */
1267 static void numa_migrate_preferred(struct task_struct *p)
1268 {
1269         /* This task has no NUMA fault statistics yet */
1270         if (unlikely(p->numa_preferred_nid == -1 || !p->numa_faults))
1271                 return;
1272
1273         /* Periodically retry migrating the task to the preferred node */
1274         p->numa_migrate_retry = jiffies + HZ;
1275
1276         /* Success if task is already running on preferred CPU */
1277         if (task_node(p) == p->numa_preferred_nid)
1278                 return;
1279
1280         /* Otherwise, try migrate to a CPU on the preferred node */
1281         task_numa_migrate(p);
1282 }
1283
1284 /*
1285  * When adapting the scan rate, the period is divided into NUMA_PERIOD_SLOTS
1286  * increments. The more local the fault statistics are, the higher the scan
1287  * period will be for the next scan window. If local/remote ratio is below
1288  * NUMA_PERIOD_THRESHOLD (where range of ratio is 1..NUMA_PERIOD_SLOTS) the
1289  * scan period will decrease
1290  */
1291 #define NUMA_PERIOD_SLOTS 10
1292 #define NUMA_PERIOD_THRESHOLD 3
1293
1294 /*
1295  * Increase the scan period (slow down scanning) if the majority of
1296  * our memory is already on our local node, or if the majority of
1297  * the page accesses are shared with other processes.
1298  * Otherwise, decrease the scan period.
1299  */
1300 static void update_task_scan_period(struct task_struct *p,
1301                         unsigned long shared, unsigned long private)
1302 {
1303         unsigned int period_slot;
1304         int ratio;
1305         int diff;
1306
1307         unsigned long remote = p->numa_faults_locality[0];
1308         unsigned long local = p->numa_faults_locality[1];
1309
1310         /*
1311          * If there were no record hinting faults then either the task is
1312          * completely idle or all activity is areas that are not of interest
1313          * to automatic numa balancing. Scan slower
1314          */
1315         if (local + shared == 0) {
1316                 p->numa_scan_period = min(p->numa_scan_period_max,
1317                         p->numa_scan_period << 1);
1318
1319                 p->mm->numa_next_scan = jiffies +
1320                         msecs_to_jiffies(p->numa_scan_period);
1321
1322                 return;
1323         }
1324
1325         /*
1326          * Prepare to scale scan period relative to the current period.
1327          *       == NUMA_PERIOD_THRESHOLD scan period stays the same
1328          *       <  NUMA_PERIOD_THRESHOLD scan period decreases (scan faster)
1329          *       >= NUMA_PERIOD_THRESHOLD scan period increases (scan slower)
1330          */
1331         period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
1332         ratio = (local * NUMA_PERIOD_SLOTS) / (local + remote);
1333         if (ratio >= NUMA_PERIOD_THRESHOLD) {
1334                 int slot = ratio - NUMA_PERIOD_THRESHOLD;
1335                 if (!slot)
1336                         slot = 1;
1337                 diff = slot * period_slot;
1338         } else {
1339                 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
1340
1341                 /*
1342                  * Scale scan rate increases based on sharing. There is an
1343                  * inverse relationship between the degree of sharing and
1344                  * the adjustment made to the scanning period. Broadly
1345                  * speaking the intent is that there is little point
1346                  * scanning faster if shared accesses dominate as it may
1347                  * simply bounce migrations uselessly
1348                  */
1349                 ratio = DIV_ROUND_UP(private * NUMA_PERIOD_SLOTS, (private + shared));
1350                 diff = (diff * ratio) / NUMA_PERIOD_SLOTS;
1351         }
1352
1353         p->numa_scan_period = clamp(p->numa_scan_period + diff,
1354                         task_scan_min(p), task_scan_max(p));
1355         memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1356 }
1357
1358 static void task_numa_placement(struct task_struct *p)
1359 {
1360         int seq, nid, max_nid = -1, max_group_nid = -1;
1361         unsigned long max_faults = 0, max_group_faults = 0;
1362         unsigned long fault_types[2] = { 0, 0 };
1363         spinlock_t *group_lock = NULL;
1364
1365         seq = ACCESS_ONCE(p->mm->numa_scan_seq);
1366         if (p->numa_scan_seq == seq)
1367                 return;
1368         p->numa_scan_seq = seq;
1369         p->numa_scan_period_max = task_scan_max(p);
1370
1371         /* If the task is part of a group prevent parallel updates to group stats */
1372         if (p->numa_group) {
1373                 group_lock = &p->numa_group->lock;
1374                 spin_lock(group_lock);
1375         }
1376
1377         /* Find the node with the highest number of faults */
1378         for_each_online_node(nid) {
1379                 unsigned long faults = 0, group_faults = 0;
1380                 int priv, i;
1381
1382                 for (priv = 0; priv < 2; priv++) {
1383                         long diff;
1384
1385                         i = task_faults_idx(nid, priv);
1386                         diff = -p->numa_faults[i];
1387
1388                         /* Decay existing window, copy faults since last scan */
1389                         p->numa_faults[i] >>= 1;
1390                         p->numa_faults[i] += p->numa_faults_buffer[i];
1391                         fault_types[priv] += p->numa_faults_buffer[i];
1392                         p->numa_faults_buffer[i] = 0;
1393
1394                         faults += p->numa_faults[i];
1395                         diff += p->numa_faults[i];
1396                         p->total_numa_faults += diff;
1397                         if (p->numa_group) {
1398                                 /* safe because we can only change our own group */
1399                                 p->numa_group->faults[i] += diff;
1400                                 p->numa_group->total_faults += diff;
1401                                 group_faults += p->numa_group->faults[i];
1402                         }
1403                 }
1404
1405                 if (faults > max_faults) {
1406                         max_faults = faults;
1407                         max_nid = nid;
1408                 }
1409
1410                 if (group_faults > max_group_faults) {
1411                         max_group_faults = group_faults;
1412                         max_group_nid = nid;
1413                 }
1414         }
1415
1416         update_task_scan_period(p, fault_types[0], fault_types[1]);
1417
1418         if (p->numa_group) {
1419                 /*
1420                  * If the preferred task and group nids are different,
1421                  * iterate over the nodes again to find the best place.
1422                  */
1423                 if (max_nid != max_group_nid) {
1424                         unsigned long weight, max_weight = 0;
1425
1426                         for_each_online_node(nid) {
1427                                 weight = task_weight(p, nid) + group_weight(p, nid);
1428                                 if (weight > max_weight) {
1429                                         max_weight = weight;
1430                                         max_nid = nid;
1431                                 }
1432                         }
1433                 }
1434
1435                 spin_unlock(group_lock);
1436         }
1437
1438         /* Preferred node as the node with the most faults */
1439         if (max_faults && max_nid != p->numa_preferred_nid) {
1440                 /* Update the preferred nid and migrate task if possible */
1441                 sched_setnuma(p, max_nid);
1442                 numa_migrate_preferred(p);
1443         }
1444 }
1445
1446 static inline int get_numa_group(struct numa_group *grp)
1447 {
1448         return atomic_inc_not_zero(&grp->refcount);
1449 }
1450
1451 static inline void put_numa_group(struct numa_group *grp)
1452 {
1453         if (atomic_dec_and_test(&grp->refcount))
1454                 kfree_rcu(grp, rcu);
1455 }
1456
1457 static void task_numa_group(struct task_struct *p, int cpupid, int flags,
1458                         int *priv)
1459 {
1460         struct numa_group *grp, *my_grp;
1461         struct task_struct *tsk;
1462         bool join = false;
1463         int cpu = cpupid_to_cpu(cpupid);
1464         int i;
1465
1466         if (unlikely(!p->numa_group)) {
1467                 unsigned int size = sizeof(struct numa_group) +
1468                                     2*nr_node_ids*sizeof(unsigned long);
1469
1470                 grp = kzalloc(size, GFP_KERNEL | __GFP_NOWARN);
1471                 if (!grp)
1472                         return;
1473
1474                 atomic_set(&grp->refcount, 1);
1475                 spin_lock_init(&grp->lock);
1476                 INIT_LIST_HEAD(&grp->task_list);
1477                 grp->gid = p->pid;
1478
1479                 for (i = 0; i < 2*nr_node_ids; i++)
1480                         grp->faults[i] = p->numa_faults[i];
1481
1482                 grp->total_faults = p->total_numa_faults;
1483
1484                 list_add(&p->numa_entry, &grp->task_list);
1485                 grp->nr_tasks++;
1486                 rcu_assign_pointer(p->numa_group, grp);
1487         }
1488
1489         rcu_read_lock();
1490         tsk = ACCESS_ONCE(cpu_rq(cpu)->curr);
1491
1492         if (!cpupid_match_pid(tsk, cpupid))
1493                 goto no_join;
1494
1495         grp = rcu_dereference(tsk->numa_group);
1496         if (!grp)
1497                 goto no_join;
1498
1499         my_grp = p->numa_group;
1500         if (grp == my_grp)
1501                 goto no_join;
1502
1503         /*
1504          * Only join the other group if its bigger; if we're the bigger group,
1505          * the other task will join us.
1506          */
1507         if (my_grp->nr_tasks > grp->nr_tasks)
1508                 goto no_join;
1509
1510         /*
1511          * Tie-break on the grp address.
1512          */
1513         if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
1514                 goto no_join;
1515
1516         /* Always join threads in the same process. */
1517         if (tsk->mm == current->mm)
1518                 join = true;
1519
1520         /* Simple filter to avoid false positives due to PID collisions */
1521         if (flags & TNF_SHARED)
1522                 join = true;
1523
1524         /* Update priv based on whether false sharing was detected */
1525         *priv = !join;
1526
1527         if (join && !get_numa_group(grp))
1528                 goto no_join;
1529
1530         rcu_read_unlock();
1531
1532         if (!join)
1533                 return;
1534
1535         double_lock(&my_grp->lock, &grp->lock);
1536
1537         for (i = 0; i < 2*nr_node_ids; i++) {
1538                 my_grp->faults[i] -= p->numa_faults[i];
1539                 grp->faults[i] += p->numa_faults[i];
1540         }
1541         my_grp->total_faults -= p->total_numa_faults;
1542         grp->total_faults += p->total_numa_faults;
1543
1544         list_move(&p->numa_entry, &grp->task_list);
1545         my_grp->nr_tasks--;
1546         grp->nr_tasks++;
1547
1548         spin_unlock(&my_grp->lock);
1549         spin_unlock(&grp->lock);
1550
1551         rcu_assign_pointer(p->numa_group, grp);
1552
1553         put_numa_group(my_grp);
1554         return;
1555
1556 no_join:
1557         rcu_read_unlock();
1558         return;
1559 }
1560
1561 void task_numa_free(struct task_struct *p)
1562 {
1563         struct numa_group *grp = p->numa_group;
1564         int i;
1565         void *numa_faults = p->numa_faults;
1566
1567         if (grp) {
1568                 spin_lock(&grp->lock);
1569                 for (i = 0; i < 2*nr_node_ids; i++)
1570                         grp->faults[i] -= p->numa_faults[i];
1571                 grp->total_faults -= p->total_numa_faults;
1572
1573                 list_del(&p->numa_entry);
1574                 grp->nr_tasks--;
1575                 spin_unlock(&grp->lock);
1576                 rcu_assign_pointer(p->numa_group, NULL);
1577                 put_numa_group(grp);
1578         }
1579
1580         p->numa_faults = NULL;
1581         p->numa_faults_buffer = NULL;
1582         kfree(numa_faults);
1583 }
1584
1585 /*
1586  * Got a PROT_NONE fault for a page on @node.
1587  */
1588 void task_numa_fault(int last_cpupid, int node, int pages, int flags)
1589 {
1590         struct task_struct *p = current;
1591         bool migrated = flags & TNF_MIGRATED;
1592         int priv;
1593
1594         if (!numabalancing_enabled)
1595                 return;
1596
1597         /* for example, ksmd faulting in a user's mm */
1598         if (!p->mm)
1599                 return;
1600
1601         /* Do not worry about placement if exiting */
1602         if (p->state == TASK_DEAD)
1603                 return;
1604
1605         /* Allocate buffer to track faults on a per-node basis */
1606         if (unlikely(!p->numa_faults)) {
1607                 int size = sizeof(*p->numa_faults) * 2 * nr_node_ids;
1608
1609                 /* numa_faults and numa_faults_buffer share the allocation */
1610                 p->numa_faults = kzalloc(size * 2, GFP_KERNEL|__GFP_NOWARN);
1611                 if (!p->numa_faults)
1612                         return;
1613
1614                 BUG_ON(p->numa_faults_buffer);
1615                 p->numa_faults_buffer = p->numa_faults + (2 * nr_node_ids);
1616                 p->total_numa_faults = 0;
1617                 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
1618         }
1619
1620         /*
1621          * First accesses are treated as private, otherwise consider accesses
1622          * to be private if the accessing pid has not changed
1623          */
1624         if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
1625                 priv = 1;
1626         } else {
1627                 priv = cpupid_match_pid(p, last_cpupid);
1628                 if (!priv && !(flags & TNF_NO_GROUP))
1629                         task_numa_group(p, last_cpupid, flags, &priv);
1630         }
1631
1632         task_numa_placement(p);
1633
1634         /*
1635          * Retry task to preferred node migration periodically, in case it
1636          * case it previously failed, or the scheduler moved us.
1637          */
1638         if (time_after(jiffies, p->numa_migrate_retry))
1639                 numa_migrate_preferred(p);
1640
1641         if (migrated)
1642                 p->numa_pages_migrated += pages;
1643
1644         p->numa_faults_buffer[task_faults_idx(node, priv)] += pages;
1645         p->numa_faults_locality[!!(flags & TNF_FAULT_LOCAL)] += pages;
1646 }
1647
1648 static void reset_ptenuma_scan(struct task_struct *p)
1649 {
1650         ACCESS_ONCE(p->mm->numa_scan_seq)++;
1651         p->mm->numa_scan_offset = 0;
1652 }
1653
1654 /*
1655  * The expensive part of numa migration is done from task_work context.
1656  * Triggered from task_tick_numa().
1657  */
1658 void task_numa_work(struct callback_head *work)
1659 {
1660         unsigned long migrate, next_scan, now = jiffies;
1661         struct task_struct *p = current;
1662         struct mm_struct *mm = p->mm;
1663         struct vm_area_struct *vma;
1664         unsigned long start, end;
1665         unsigned long nr_pte_updates = 0;
1666         long pages;
1667
1668         WARN_ON_ONCE(p != container_of(work, struct task_struct, numa_work));
1669
1670         work->next = work; /* protect against double add */
1671         /*
1672          * Who cares about NUMA placement when they're dying.
1673          *
1674          * NOTE: make sure not to dereference p->mm before this check,
1675          * exit_task_work() happens _after_ exit_mm() so we could be called
1676          * without p->mm even though we still had it when we enqueued this
1677          * work.
1678          */
1679         if (p->flags & PF_EXITING)
1680                 return;
1681
1682         if (!mm->numa_next_scan) {
1683                 mm->numa_next_scan = now +
1684                         msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
1685         }
1686
1687         /*
1688          * Enforce maximal scan/migration frequency..
1689          */
1690         migrate = mm->numa_next_scan;
1691         if (time_before(now, migrate))
1692                 return;
1693
1694         if (p->numa_scan_period == 0) {
1695                 p->numa_scan_period_max = task_scan_max(p);
1696                 p->numa_scan_period = task_scan_min(p);
1697         }
1698
1699         next_scan = now + msecs_to_jiffies(p->numa_scan_period);
1700         if (cmpxchg(&mm->numa_next_scan, migrate, next_scan) != migrate)
1701                 return;
1702
1703         /*
1704          * Delay this task enough that another task of this mm will likely win
1705          * the next time around.
1706          */
1707         p->node_stamp += 2 * TICK_NSEC;
1708
1709         start = mm->numa_scan_offset;
1710         pages = sysctl_numa_balancing_scan_size;
1711         pages <<= 20 - PAGE_SHIFT; /* MB in pages */
1712         if (!pages)
1713                 return;
1714
1715         down_read(&mm->mmap_sem);
1716         vma = find_vma(mm, start);
1717         if (!vma) {
1718                 reset_ptenuma_scan(p);
1719                 start = 0;
1720                 vma = mm->mmap;
1721         }
1722         for (; vma; vma = vma->vm_next) {
1723                 if (!vma_migratable(vma) || !vma_policy_mof(p, vma))
1724                         continue;
1725
1726                 /*
1727                  * Shared library pages mapped by multiple processes are not
1728                  * migrated as it is expected they are cache replicated. Avoid
1729                  * hinting faults in read-only file-backed mappings or the vdso
1730                  * as migrating the pages will be of marginal benefit.
1731                  */
1732                 if (!vma->vm_mm ||
1733                     (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ)))
1734                         continue;
1735
1736                 /*
1737                  * Skip inaccessible VMAs to avoid any confusion between
1738                  * PROT_NONE and NUMA hinting ptes
1739                  */
1740                 if (!(vma->vm_flags & (VM_READ | VM_EXEC | VM_WRITE)))
1741                         continue;
1742
1743                 do {
1744                         start = max(start, vma->vm_start);
1745                         end = ALIGN(start + (pages << PAGE_SHIFT), HPAGE_SIZE);
1746                         end = min(end, vma->vm_end);
1747                         nr_pte_updates += change_prot_numa(vma, start, end);
1748
1749                         /*
1750                          * Scan sysctl_numa_balancing_scan_size but ensure that
1751                          * at least one PTE is updated so that unused virtual
1752                          * address space is quickly skipped.
1753                          */
1754                         if (nr_pte_updates)
1755                                 pages -= (end - start) >> PAGE_SHIFT;
1756
1757                         start = end;
1758                         if (pages <= 0)
1759                                 goto out;
1760
1761                         cond_resched();
1762                 } while (end != vma->vm_end);
1763         }
1764
1765 out:
1766         /*
1767          * It is possible to reach the end of the VMA list but the last few
1768          * VMAs are not guaranteed to the vma_migratable. If they are not, we
1769          * would find the !migratable VMA on the next scan but not reset the
1770          * scanner to the start so check it now.
1771          */
1772         if (vma)
1773                 mm->numa_scan_offset = start;
1774         else
1775                 reset_ptenuma_scan(p);
1776         up_read(&mm->mmap_sem);
1777 }
1778
1779 /*
1780  * Drive the periodic memory faults..
1781  */
1782 void task_tick_numa(struct rq *rq, struct task_struct *curr)
1783 {
1784         struct callback_head *work = &curr->numa_work;
1785         u64 period, now;
1786
1787         /*
1788          * We don't care about NUMA placement if we don't have memory.
1789          */
1790         if (!curr->mm || (curr->flags & PF_EXITING) || work->next != work)
1791                 return;
1792
1793         /*
1794          * Using runtime rather than walltime has the dual advantage that
1795          * we (mostly) drive the selection from busy threads and that the
1796          * task needs to have done some actual work before we bother with
1797          * NUMA placement.
1798          */
1799         now = curr->se.sum_exec_runtime;
1800         period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
1801
1802         if (now - curr->node_stamp > period) {
1803                 if (!curr->node_stamp)
1804                         curr->numa_scan_period = task_scan_min(curr);
1805                 curr->node_stamp += period;
1806
1807                 if (!time_before(jiffies, curr->mm->numa_next_scan)) {
1808                         init_task_work(work, task_numa_work); /* TODO: move this into sched_fork() */
1809                         task_work_add(curr, work, true);
1810                 }
1811         }
1812 }
1813 #else
1814 static void task_tick_numa(struct rq *rq, struct task_struct *curr)
1815 {
1816 }
1817
1818 static inline void account_numa_enqueue(struct rq *rq, struct task_struct *p)
1819 {
1820 }
1821
1822 static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
1823 {
1824 }
1825 #endif /* CONFIG_NUMA_BALANCING */
1826
1827 static void
1828 account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
1829 {
1830         update_load_add(&cfs_rq->load, se->load.weight);
1831         if (!parent_entity(se))
1832                 update_load_add(&rq_of(cfs_rq)->load, se->load.weight);
1833 #ifdef CONFIG_SMP
1834         if (entity_is_task(se)) {
1835                 struct rq *rq = rq_of(cfs_rq);
1836
1837                 account_numa_enqueue(rq, task_of(se));
1838                 list_add(&se->group_node, &rq->cfs_tasks);
1839         }
1840 #endif
1841         cfs_rq->nr_running++;
1842 }
1843
1844 static void
1845 account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
1846 {
1847         update_load_sub(&cfs_rq->load, se->load.weight);
1848         if (!parent_entity(se))
1849                 update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
1850         if (entity_is_task(se)) {
1851                 account_numa_dequeue(rq_of(cfs_rq), task_of(se));
1852                 list_del_init(&se->group_node);
1853         }
1854         cfs_rq->nr_running--;
1855 }
1856
1857 #ifdef CONFIG_FAIR_GROUP_SCHED
1858 # ifdef CONFIG_SMP
1859 static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
1860 {
1861         long tg_weight;
1862
1863         /*
1864          * Use this CPU's actual weight instead of the last load_contribution
1865          * to gain a more accurate current total weight. See
1866          * update_cfs_rq_load_contribution().
1867          */
1868         tg_weight = atomic_long_read(&tg->load_avg);
1869         tg_weight -= cfs_rq->tg_load_contrib;
1870         tg_weight += cfs_rq->load.weight;
1871
1872         return tg_weight;
1873 }
1874
1875 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
1876 {
1877         long tg_weight, load, shares;
1878
1879         tg_weight = calc_tg_weight(tg, cfs_rq);
1880         load = cfs_rq->load.weight;
1881
1882         shares = (tg->shares * load);
1883         if (tg_weight)
1884                 shares /= tg_weight;
1885
1886         if (shares < MIN_SHARES)
1887                 shares = MIN_SHARES;
1888         if (shares > tg->shares)
1889                 shares = tg->shares;
1890
1891         return shares;
1892 }
1893 # else /* CONFIG_SMP */
1894 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
1895 {
1896         return tg->shares;
1897 }
1898 # endif /* CONFIG_SMP */
1899 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
1900                             unsigned long weight)
1901 {
1902         if (se->on_rq) {
1903                 /* commit outstanding execution time */
1904                 if (cfs_rq->curr == se)
1905                         update_curr(cfs_rq);
1906                 account_entity_dequeue(cfs_rq, se);
1907         }
1908
1909         update_load_set(&se->load, weight);
1910
1911         if (se->on_rq)
1912                 account_entity_enqueue(cfs_rq, se);
1913 }
1914
1915 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
1916
1917 static void update_cfs_shares(struct cfs_rq *cfs_rq)
1918 {
1919         struct task_group *tg;
1920         struct sched_entity *se;
1921         long shares;
1922
1923         tg = cfs_rq->tg;
1924         se = tg->se[cpu_of(rq_of(cfs_rq))];
1925         if (!se || throttled_hierarchy(cfs_rq))
1926                 return;
1927 #ifndef CONFIG_SMP
1928         if (likely(se->load.weight == tg->shares))
1929                 return;
1930 #endif
1931         shares = calc_cfs_shares(cfs_rq, tg);
1932
1933         reweight_entity(cfs_rq_of(se), se, shares);
1934 }
1935 #else /* CONFIG_FAIR_GROUP_SCHED */
1936 static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
1937 {
1938 }
1939 #endif /* CONFIG_FAIR_GROUP_SCHED */
1940
1941 #ifdef CONFIG_SMP
1942 /*
1943  * We choose a half-life close to 1 scheduling period.
1944  * Note: The tables below are dependent on this value.
1945  */
1946 #define LOAD_AVG_PERIOD 32
1947 #define LOAD_AVG_MAX 47742 /* maximum possible load avg */
1948 #define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */
1949
1950 /* Precomputed fixed inverse multiplies for multiplication by y^n */
1951 static const u32 runnable_avg_yN_inv[] = {
1952         0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
1953         0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
1954         0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
1955         0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
1956         0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
1957         0x85aac367, 0x82cd8698,
1958 };
1959
1960 /*
1961  * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
1962  * over-estimates when re-combining.
1963  */
1964 static const u32 runnable_avg_yN_sum[] = {
1965             0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
1966          9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
1967         17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
1968 };
1969
1970 /*
1971  * Approximate:
1972  *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
1973  */
1974 static __always_inline u64 decay_load(u64 val, u64 n)
1975 {
1976         unsigned int local_n;
1977
1978         if (!n)
1979                 return val;
1980         else if (unlikely(n > LOAD_AVG_PERIOD * 63))
1981                 return 0;
1982
1983         /* after bounds checking we can collapse to 32-bit */
1984         local_n = n;
1985
1986         /*
1987          * As y^PERIOD = 1/2, we can combine
1988          *    y^n = 1/2^(n/PERIOD) * k^(n%PERIOD)
1989          * With a look-up table which covers k^n (n<PERIOD)
1990          *
1991          * To achieve constant time decay_load.
1992          */
1993         if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
1994                 val >>= local_n / LOAD_AVG_PERIOD;
1995                 local_n %= LOAD_AVG_PERIOD;
1996         }
1997
1998         val *= runnable_avg_yN_inv[local_n];
1999         /* We don't use SRR here since we always want to round down. */
2000         return val >> 32;
2001 }
2002
2003 /*
2004  * For updates fully spanning n periods, the contribution to runnable
2005  * average will be: \Sum 1024*y^n
2006  *
2007  * We can compute this reasonably efficiently by combining:
2008  *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
2009  */
2010 static u32 __compute_runnable_contrib(u64 n)
2011 {
2012         u32 contrib = 0;
2013
2014         if (likely(n <= LOAD_AVG_PERIOD))
2015                 return runnable_avg_yN_sum[n];
2016         else if (unlikely(n >= LOAD_AVG_MAX_N))
2017                 return LOAD_AVG_MAX;
2018
2019         /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
2020         do {
2021                 contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
2022                 contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];
2023
2024                 n -= LOAD_AVG_PERIOD;
2025         } while (n > LOAD_AVG_PERIOD);
2026
2027         contrib = decay_load(contrib, n);
2028         return contrib + runnable_avg_yN_sum[n];
2029 }
2030
2031 /*
2032  * We can represent the historical contribution to runnable average as the
2033  * coefficients of a geometric series.  To do this we sub-divide our runnable
2034  * history into segments of approximately 1ms (1024us); label the segment that
2035  * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
2036  *
2037  * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
2038  *      p0            p1           p2
2039  *     (now)       (~1ms ago)  (~2ms ago)
2040  *
2041  * Let u_i denote the fraction of p_i that the entity was runnable.
2042  *
2043  * We then designate the fractions u_i as our co-efficients, yielding the
2044  * following representation of historical load:
2045  *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
2046  *
2047  * We choose y based on the with of a reasonably scheduling period, fixing:
2048  *   y^32 = 0.5
2049  *
2050  * This means that the contribution to load ~32ms ago (u_32) will be weighted
2051  * approximately half as much as the contribution to load within the last ms
2052  * (u_0).
2053  *
2054  * When a period "rolls over" and we have new u_0`, multiplying the previous
2055  * sum again by y is sufficient to update:
2056  *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
2057  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
2058  */
2059 static __always_inline int __update_entity_runnable_avg(u64 now,
2060                                                         struct sched_avg *sa,
2061                                                         int runnable)
2062 {
2063         u64 delta, periods;
2064         u32 runnable_contrib;
2065         int delta_w, decayed = 0;
2066
2067         delta = now - sa->last_runnable_update;
2068         /*
2069          * This should only happen when time goes backwards, which it
2070          * unfortunately does during sched clock init when we swap over to TSC.
2071          */
2072         if ((s64)delta < 0) {
2073                 sa->last_runnable_update = now;
2074                 return 0;
2075         }
2076
2077         /*
2078          * Use 1024ns as the unit of measurement since it's a reasonable
2079          * approximation of 1us and fast to compute.
2080          */
2081         delta >>= 10;
2082         if (!delta)
2083                 return 0;
2084         sa->last_runnable_update = now;
2085
2086         /* delta_w is the amount already accumulated against our next period */
2087         delta_w = sa->runnable_avg_period % 1024;
2088         if (delta + delta_w >= 1024) {
2089                 /* period roll-over */
2090                 decayed = 1;
2091
2092                 /*
2093                  * Now that we know we're crossing a period boundary, figure
2094                  * out how much from delta we need to complete the current
2095                  * period and accrue it.
2096                  */
2097                 delta_w = 1024 - delta_w;
2098                 if (runnable)
2099                         sa->runnable_avg_sum += delta_w;
2100                 sa->runnable_avg_period += delta_w;
2101
2102                 delta -= delta_w;
2103
2104                 /* Figure out how many additional periods this update spans */
2105                 periods = delta / 1024;
2106                 delta %= 1024;
2107
2108                 sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
2109                                                   periods + 1);
2110                 sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
2111                                                      periods + 1);
2112
2113                 /* Efficiently calculate \sum (1..n_period) 1024*y^i */
2114                 runnable_contrib = __compute_runnable_contrib(periods);
2115                 if (runnable)
2116                         sa->runnable_avg_sum += runnable_contrib;
2117                 sa->runnable_avg_period += runnable_contrib;
2118         }
2119
2120         /* Remainder of delta accrued against u_0` */
2121         if (runnable)
2122                 sa->runnable_avg_sum += delta;
2123         sa->runnable_avg_period += delta;
2124
2125         return decayed;
2126 }
2127
2128 /* Synchronize an entity's decay with its parenting cfs_rq.*/
2129 static inline u64 __synchronize_entity_decay(struct sched_entity *se)
2130 {
2131         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2132         u64 decays = atomic64_read(&cfs_rq->decay_counter);
2133
2134         decays -= se->avg.decay_count;
2135         if (!decays)
2136                 return 0;
2137
2138         se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);
2139         se->avg.decay_count = 0;
2140
2141         return decays;
2142 }
2143
2144 #ifdef CONFIG_FAIR_GROUP_SCHED
2145 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2146                                                  int force_update)
2147 {
2148         struct task_group *tg = cfs_rq->tg;
2149         long tg_contrib;
2150
2151         tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
2152         tg_contrib -= cfs_rq->tg_load_contrib;
2153
2154         if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
2155                 atomic_long_add(tg_contrib, &tg->load_avg);
2156                 cfs_rq->tg_load_contrib += tg_contrib;
2157         }
2158 }
2159
2160 /*
2161  * Aggregate cfs_rq runnable averages into an equivalent task_group
2162  * representation for computing load contributions.
2163  */
2164 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2165                                                   struct cfs_rq *cfs_rq)
2166 {
2167         struct task_group *tg = cfs_rq->tg;
2168         long contrib;
2169
2170         /* The fraction of a cpu used by this cfs_rq */
2171         contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
2172                           sa->runnable_avg_period + 1);
2173         contrib -= cfs_rq->tg_runnable_contrib;
2174
2175         if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
2176                 atomic_add(contrib, &tg->runnable_avg);
2177                 cfs_rq->tg_runnable_contrib += contrib;
2178         }
2179 }
2180
2181 static inline void __update_group_entity_contrib(struct sched_entity *se)
2182 {
2183         struct cfs_rq *cfs_rq = group_cfs_rq(se);
2184         struct task_group *tg = cfs_rq->tg;
2185         int runnable_avg;
2186
2187         u64 contrib;
2188
2189         contrib = cfs_rq->tg_load_contrib * tg->shares;
2190         se->avg.load_avg_contrib = div_u64(contrib,
2191                                      atomic_long_read(&tg->load_avg) + 1);
2192
2193         /*
2194          * For group entities we need to compute a correction term in the case
2195          * that they are consuming <1 cpu so that we would contribute the same
2196          * load as a task of equal weight.
2197          *
2198          * Explicitly co-ordinating this measurement would be expensive, but
2199          * fortunately the sum of each cpus contribution forms a usable
2200          * lower-bound on the true value.
2201          *
2202          * Consider the aggregate of 2 contributions.  Either they are disjoint
2203          * (and the sum represents true value) or they are disjoint and we are
2204          * understating by the aggregate of their overlap.
2205          *
2206          * Extending this to N cpus, for a given overlap, the maximum amount we
2207          * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of
2208          * cpus that overlap for this interval and w_i is the interval width.
2209          *
2210          * On a small machine; the first term is well-bounded which bounds the
2211          * total error since w_i is a subset of the period.  Whereas on a
2212          * larger machine, while this first term can be larger, if w_i is the
2213          * of consequential size guaranteed to see n_i*w_i quickly converge to
2214          * our upper bound of 1-cpu.
2215          */
2216         runnable_avg = atomic_read(&tg->runnable_avg);
2217         if (runnable_avg < NICE_0_LOAD) {
2218                 se->avg.load_avg_contrib *= runnable_avg;
2219                 se->avg.load_avg_contrib >>= NICE_0_SHIFT;
2220         }
2221 }
2222 #else
2223 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
2224                                                  int force_update) {}
2225 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
2226                                                   struct cfs_rq *cfs_rq) {}
2227 static inline void __update_group_entity_contrib(struct sched_entity *se) {}
2228 #endif
2229
2230 static inline void __update_task_entity_contrib(struct sched_entity *se)
2231 {
2232         u32 contrib;
2233
2234         /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
2235         contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
2236         contrib /= (se->avg.runnable_avg_period + 1);
2237         se->avg.load_avg_contrib = scale_load(contrib);
2238 }
2239
2240 /* Compute the current contribution to load_avg by se, return any delta */
2241 static long __update_entity_load_avg_contrib(struct sched_entity *se)
2242 {
2243         long old_contrib = se->avg.load_avg_contrib;
2244
2245         if (entity_is_task(se)) {
2246                 __update_task_entity_contrib(se);
2247         } else {
2248                 __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
2249                 __update_group_entity_contrib(se);
2250         }
2251
2252         return se->avg.load_avg_contrib - old_contrib;
2253 }
2254
2255 static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
2256                                                  long load_contrib)
2257 {
2258         if (likely(load_contrib < cfs_rq->blocked_load_avg))
2259                 cfs_rq->blocked_load_avg -= load_contrib;
2260         else
2261                 cfs_rq->blocked_load_avg = 0;
2262 }
2263
2264 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq);
2265
2266 /* Update a sched_entity's runnable average */
2267 static inline void update_entity_load_avg(struct sched_entity *se,
2268                                           int update_cfs_rq)
2269 {
2270         struct cfs_rq *cfs_rq = cfs_rq_of(se);
2271         long contrib_delta;
2272         u64 now;
2273
2274         /*
2275          * For a group entity we need to use their owned cfs_rq_clock_task() in
2276          * case they are the parent of a throttled hierarchy.
2277          */
2278         if (entity_is_task(se))
2279                 now = cfs_rq_clock_task(cfs_rq);
2280         else
2281                 now = cfs_rq_clock_task(group_cfs_rq(se));
2282
2283         if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
2284                 return;
2285
2286         contrib_delta = __update_entity_load_avg_contrib(se);
2287
2288         if (!update_cfs_rq)
2289                 return;
2290
2291         if (se->on_rq)
2292                 cfs_rq->runnable_load_avg += contrib_delta;
2293         else
2294                 subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
2295 }
2296
2297 /*
2298  * Decay the load contributed by all blocked children and account this so that
2299  * their contribution may appropriately discounted when they wake up.
2300  */
2301 static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
2302 {
2303         u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
2304         u64 decays;
2305
2306         decays = now - cfs_rq->last_decay;
2307         if (!decays && !force_update)
2308                 return;
2309
2310         if (atomic_long_read(&cfs_rq->removed_load)) {
2311                 unsigned long removed_load;
2312                 removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
2313                 subtract_blocked_load_contrib(cfs_rq, removed_load);
2314         }
2315
2316         if (decays) {
2317                 cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
2318                                                       decays);
2319                 atomic64_add(decays, &cfs_rq->decay_counter);
2320                 cfs_rq->last_decay = now;
2321         }
2322
2323         __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
2324 }
2325
2326 static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
2327 {
2328         __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
2329         __update_tg_runnable_avg(&rq->avg, &rq->cfs);
2330 }
2331
2332 /* Add the load generated by se into cfs_rq's child load-average */
2333 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2334                                                   struct sched_entity *se,
2335                                                   int wakeup)
2336 {
2337         /*
2338          * We track migrations using entity decay_count <= 0, on a wake-up
2339          * migration we use a negative decay count to track the remote decays
2340          * accumulated while sleeping.
2341          *
2342          * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
2343          * are seen by enqueue_entity_load_avg() as a migration with an already
2344          * constructed load_avg_contrib.
2345          */
2346         if (unlikely(se->avg.decay_count <= 0)) {
2347                 se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
2348                 if (se->avg.decay_count) {
2349                         /*
2350                          * In a wake-up migration we have to approximate the
2351                          * time sleeping.  This is because we can't synchronize
2352                          * clock_task between the two cpus, and it is not
2353                          * guaranteed to be read-safe.  Instead, we can
2354                          * approximate this using our carried decays, which are
2355                          * explicitly atomically readable.
2356                          */
2357                         se->avg.last_runnable_update -= (-se->avg.decay_count)
2358                                                         << 20;
2359                         update_entity_load_avg(se, 0);
2360                         /* Indicate that we're now synchronized and on-rq */
2361                         se->avg.decay_count = 0;
2362                 }
2363                 wakeup = 0;
2364         } else {
2365                 __synchronize_entity_decay(se);
2366         }
2367
2368         /* migrated tasks did not contribute to our blocked load */
2369         if (wakeup) {
2370                 subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
2371                 update_entity_load_avg(se, 0);
2372         }
2373
2374         cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
2375         /* we force update consideration on load-balancer moves */
2376         update_cfs_rq_blocked_load(cfs_rq, !wakeup);
2377 }
2378
2379 /*
2380  * Remove se's load from this cfs_rq child load-average, if the entity is
2381  * transitioning to a blocked state we track its projected decay using
2382  * blocked_load_avg.
2383  */
2384 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2385                                                   struct sched_entity *se,
2386                                                   int sleep)
2387 {
2388         update_entity_load_avg(se, 1);
2389         /* we force update consideration on load-balancer moves */
2390         update_cfs_rq_blocked_load(cfs_rq, !sleep);
2391
2392         cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
2393         if (sleep) {
2394                 cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
2395                 se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
2396         } /* migrations, e.g. sleep=0 leave decay_count == 0 */
2397 }
2398
2399 /*
2400  * Update the rq's load with the elapsed running time before entering
2401  * idle. if the last scheduled task is not a CFS task, idle_enter will
2402  * be the only way to update the runnable statistic.
2403  */
2404 void idle_enter_fair(struct rq *this_rq)
2405 {
2406         update_rq_runnable_avg(this_rq, 1);
2407 }
2408
2409 /*
2410  * Update the rq's load with the elapsed idle time before a task is
2411  * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
2412  * be the only way to update the runnable statistic.
2413  */
2414 void idle_exit_fair(struct rq *this_rq)
2415 {
2416         update_rq_runnable_avg(this_rq, 0);
2417 }
2418
2419 #else
2420 static inline void update_entity_load_avg(struct sched_entity *se,
2421                                           int update_cfs_rq) {}
2422 static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
2423 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
2424                                            struct sched_entity *se,
2425                                            int wakeup) {}
2426 static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
2427                                            struct sched_entity *se,
2428                                            int sleep) {}
2429 static inline void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
2430                                               int force_update) {}
2431 #endif
2432
2433 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
2434 {
2435 #ifdef CONFIG_SCHEDSTATS
2436         struct task_struct *tsk = NULL;
2437
2438         if (entity_is_task(se))
2439                 tsk = task_of(se);
2440
2441         if (se->statistics.sleep_start) {
2442                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.sleep_start;
2443
2444                 if ((s64)delta < 0)
2445                         delta = 0;
2446
2447                 if (unlikely(delta > se->statistics.sleep_max))
2448                         se->statistics.sleep_max = delta;
2449
2450                 se->statistics.sleep_start = 0;
2451                 se->statistics.sum_sleep_runtime += delta;
2452
2453                 if (tsk) {
2454                         account_scheduler_latency(tsk, delta >> 10, 1);
2455                         trace_sched_stat_sleep(tsk, delta);
2456                 }
2457         }
2458         if (se->statistics.block_start) {
2459                 u64 delta = rq_clock(rq_of(cfs_rq)) - se->statistics.block_start;
2460
2461                 if ((s64)delta < 0)
2462                         delta = 0;
2463
2464                 if (unlikely(delta > se->statistics.block_max))
2465                         se->statistics.block_max = delta;
2466
2467                 se->statistics.block_start = 0;
2468                 se->statistics.sum_sleep_runtime += delta;
2469
2470                 if (tsk) {
2471                         if (tsk->in_iowait) {
2472                                 se->statistics.iowait_sum += delta;
2473                                 se->statistics.iowait_count++;
2474                                 trace_sched_stat_iowait(tsk, delta);
2475                         }
2476
2477                         trace_sched_stat_blocked(tsk, delta);
2478
2479                         /*
2480                          * Blocking time is in units of nanosecs, so shift by
2481                          * 20 to get a milliseconds-range estimation of the
2482                          * amount of time that the task spent sleeping:
2483                          */
2484                         if (unlikely(prof_on == SLEEP_PROFILING)) {
2485                                 profile_hits(SLEEP_PROFILING,
2486                                                 (void *)get_wchan(tsk),
2487                                                 delta >> 20);
2488                         }
2489                         account_scheduler_latency(tsk, delta >> 10, 0);
2490                 }
2491         }
2492 #endif
2493 }
2494
2495 static void check_spread(struct cfs_rq *cfs_rq, struct sched_entity *se)
2496 {
2497 #ifdef CONFIG_SCHED_DEBUG
2498         s64 d = se->vruntime - cfs_rq->min_vruntime;
2499
2500         if (d < 0)
2501                 d = -d;
2502
2503         if (d > 3*sysctl_sched_latency)
2504                 schedstat_inc(cfs_rq, nr_spread_over);
2505 #endif
2506 }
2507
2508 static void
2509 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
2510 {
2511         u64 vruntime = cfs_rq->min_vruntime;
2512
2513         /*
2514          * The 'current' period is already promised to the current tasks,
2515          * however the extra weight of the new task will slow them down a
2516          * little, place the new task so that it fits in the slot that
2517          * stays open at the end.
2518          */
2519         if (initial && sched_feat(START_DEBIT))
2520                 vruntime += sched_vslice(cfs_rq, se);
2521
2522         /* sleeps up to a single latency don't count. */
2523         if (!initial) {
2524                 unsigned long thresh = sysctl_sched_latency;
2525
2526                 /*
2527                  * Halve their sleep time's effect, to allow
2528                  * for a gentler effect of sleepers:
2529                  */
2530                 if (sched_feat(GENTLE_FAIR_SLEEPERS))
2531                         thresh >>= 1;
2532
2533                 vruntime -= thresh;
2534         }
2535
2536         /* ensure we never gain time by being placed backwards. */
2537         se->vruntime = max_vruntime(se->vruntime, vruntime);
2538 }
2539
2540 static void check_enqueue_throttle(struct cfs_rq *cfs_rq);
2541
2542 static void
2543 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2544 {
2545         /*
2546          * Update the normalized vruntime before updating min_vruntime
2547          * through calling update_curr().
2548          */
2549         if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
2550                 se->vruntime += cfs_rq->min_vruntime;
2551
2552         /*
2553          * Update run-time statistics of the 'current'.
2554          */
2555         update_curr(cfs_rq);
2556         enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
2557         account_entity_enqueue(cfs_rq, se);
2558         update_cfs_shares(cfs_rq);
2559
2560         if (flags & ENQUEUE_WAKEUP) {
2561                 place_entity(cfs_rq, se, 0);
2562                 enqueue_sleeper(cfs_rq, se);
2563         }
2564
2565         update_stats_enqueue(cfs_rq, se);
2566         check_spread(cfs_rq, se);
2567         if (se != cfs_rq->curr)
2568                 __enqueue_entity(cfs_rq, se);
2569         se->on_rq = 1;
2570
2571         if (cfs_rq->nr_running == 1) {
2572                 list_add_leaf_cfs_rq(cfs_rq);
2573                 check_enqueue_throttle(cfs_rq);
2574         }
2575 }
2576
2577 static void __clear_buddies_last(struct sched_entity *se)
2578 {
2579         for_each_sched_entity(se) {
2580                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2581                 if (cfs_rq->last == se)
2582                         cfs_rq->last = NULL;
2583                 else
2584                         break;
2585         }
2586 }
2587
2588 static void __clear_buddies_next(struct sched_entity *se)
2589 {
2590         for_each_sched_entity(se) {
2591                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2592                 if (cfs_rq->next == se)
2593                         cfs_rq->next = NULL;
2594                 else
2595                         break;
2596         }
2597 }
2598
2599 static void __clear_buddies_skip(struct sched_entity *se)
2600 {
2601         for_each_sched_entity(se) {
2602                 struct cfs_rq *cfs_rq = cfs_rq_of(se);
2603                 if (cfs_rq->skip == se)
2604                         cfs_rq->skip = NULL;
2605                 else
2606                         break;
2607         }
2608 }
2609
2610 static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
2611 {
2612         if (cfs_rq->last == se)
2613                 __clear_buddies_last(se);
2614
2615         if (cfs_rq->next == se)
2616                 __clear_buddies_next(se);
2617
2618         if (cfs_rq->skip == se)
2619                 __clear_buddies_skip(se);
2620 }
2621
2622 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
2623
2624 static void
2625 dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
2626 {
2627         /*
2628          * Update run-time statistics of the 'current'.
2629          */
2630         update_curr(cfs_rq);
2631         dequeue_entity_load_avg(cfs_rq, se, flags & DEQUEUE_SLEEP);
2632
2633         update_stats_dequeue(cfs_rq, se);
2634         if (flags & DEQUEUE_SLEEP) {
2635 #ifdef CONFIG_SCHEDSTATS
2636                 if (entity_is_task(se)) {
2637                         struct task_struct *tsk = task_of(se);
2638
2639                         if (tsk->state & TASK_INTERRUPTIBLE)
2640                                 se->statistics.sleep_start = rq_clock(rq_of(cfs_rq));
2641                         if (tsk->state & TASK_UNINTERRUPTIBLE)
2642                                 se->statistics.block_start = rq_clock(rq_of(cfs_rq));
2643                 }
2644 #endif
2645         }
2646
2647         clear_buddies(cfs_rq, se);
2648
2649         if (se != cfs_rq->curr)
2650                 __dequeue_entity(cfs_rq, se);
2651         se->on_rq = 0;
2652         account_entity_dequeue(cfs_rq, se);
2653
2654         /*
2655          * Normalize the entity after updating the min_vruntime because the
2656          * update can refer to the ->curr item and we need to reflect this
2657          * movement in our normalized position.
2658          */
2659         if (!(flags & DEQUEUE_SLEEP))
2660                 se->vruntime -= cfs_rq->min_vruntime;
2661
2662         /* return excess runtime on last dequeue */
2663         return_cfs_rq_runtime(cfs_rq);
2664
2665         update_min_vruntime(cfs_rq);
2666         update_cfs_shares(cfs_rq);
2667 }
2668
2669 /*
2670  * Preempt the current task with a newly woken task if needed:
2671  */
2672 static void
2673 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
2674 {
2675         unsigned long ideal_runtime, delta_exec;
2676         struct sched_entity *se;
2677         s64 delta;
2678
2679         ideal_runtime = sched_slice(cfs_rq, curr);
2680         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
2681         if (delta_exec > ideal_runtime) {
2682                 resched_task(rq_of(cfs_rq)->curr);
2683                 /*
2684                  * The current task ran long enough, ensure it doesn't get
2685                  * re-elected due to buddy favours.
2686                  */
2687                 clear_buddies(cfs_rq, curr);
2688                 return;
2689         }
2690
2691         /*
2692          * Ensure that a task that missed wakeup preemption by a
2693          * narrow margin doesn't have to wait for a full slice.
2694          * This also mitigates buddy induced latencies under load.
2695          */
2696         if (delta_exec < sysctl_sched_min_granularity)
2697                 return;
2698
2699         se = __pick_first_entity(cfs_rq);
2700         delta = curr->vruntime - se->vruntime;
2701
2702         if (delta < 0)
2703                 return;
2704
2705         if (delta > ideal_runtime)
2706                 resched_task(rq_of(cfs_rq)->curr);
2707 }
2708
2709 static void
2710 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
2711 {
2712         /* 'current' is not kept within the tree. */
2713         if (se->on_rq) {
2714                 /*
2715                  * Any task has to be enqueued before it get to execute on
2716                  * a CPU. So account for the time it spent waiting on the
2717                  * runqueue.
2718                  */
2719                 update_stats_wait_end(cfs_rq, se);
2720                 __dequeue_entity(cfs_rq, se);
2721         }
2722
2723         update_stats_curr_start(cfs_rq, se);
2724         cfs_rq->curr = se;
2725 #ifdef CONFIG_SCHEDSTATS
2726         /*
2727          * Track our maximum slice length, if the CPU's load is at
2728          * least twice that of our own weight (i.e. dont track it
2729          * when there are only lesser-weight tasks around):
2730          */
2731         if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
2732                 se->statistics.slice_max = max(se->statistics.slice_max,
2733                         se->sum_exec_runtime - se->prev_sum_exec_runtime);
2734         }
2735 #endif
2736         se->prev_sum_exec_runtime = se->sum_exec_runtime;
2737 }
2738
2739 static int
2740 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
2741
2742 /*
2743  * Pick the next process, keeping these things in mind, in this order:
2744  * 1) keep things fair between processes/task groups
2745  * 2) pick the "next" process, since someone really wants that to run
2746  * 3) pick the "last" process, for cache locality
2747  * 4) do not run the "skip" process, if something else is available
2748  */
2749 static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
2750 {
2751         struct sched_entity *se = __pick_first_entity(cfs_rq);
2752         struct sched_entity *left = se;
2753
2754         /*
2755          * Avoid running the skip buddy, if running something else can
2756          * be done without getting too unfair.
2757          */
2758         if (cfs_rq->skip == se) {
2759                 struct sched_entity *second = __pick_next_entity(se);
2760                 if (second && wakeup_preempt_entity(second, left) < 1)
2761                         se = second;
2762         }
2763
2764         /*
2765          * Prefer last buddy, try to return the CPU to a preempted task.
2766          */
2767         if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
2768                 se = cfs_rq->last;
2769
2770         /*
2771          * Someone really wants this to run. If it's not unfair, run it.
2772          */
2773         if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
2774                 se = cfs_rq->next;
2775
2776         clear_buddies(cfs_rq, se);
2777
2778         return se;
2779 }
2780
2781 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
2782
2783 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
2784 {
2785         /*
2786          * If still on the runqueue then deactivate_task()
2787          * was not called and update_curr() has to be done:
2788          */
2789         if (prev->on_rq)
2790                 update_curr(cfs_rq);
2791
2792         /* throttle cfs_rqs exceeding runtime */
2793         check_cfs_rq_runtime(cfs_rq);
2794
2795         check_spread(cfs_rq, prev);
2796         if (prev->on_rq) {
2797                 update_stats_wait_start(cfs_rq, prev);
2798                 /* Put 'current' back into the tree. */
2799                 __enqueue_entity(cfs_rq, prev);
2800                 /* in !on_rq case, update occurred at dequeue */
2801                 update_entity_load_avg(prev, 1);
2802         }
2803         cfs_rq->curr = NULL;
2804 }
2805
2806 static void
2807 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
2808 {
2809         /*
2810          * Update run-time statistics of the 'current'.
2811          */
2812         update_curr(cfs_rq);
2813
2814         /*
2815          * Ensure that runnable average is periodically updated.
2816          */
2817         update_entity_load_avg(curr, 1);
2818         update_cfs_rq_blocked_load(cfs_rq, 1);
2819         update_cfs_shares(cfs_rq);
2820
2821 #ifdef CONFIG_SCHED_HRTICK
2822         /*
2823          * queued ticks are scheduled to match the slice, so don't bother
2824          * validating it and just reschedule.
2825          */
2826         if (queued) {
2827                 resched_task(rq_of(cfs_rq)->curr);
2828                 return;
2829         }
2830         /*
2831          * don't let the period tick interfere with the hrtick preemption
2832          */
2833         if (!sched_feat(DOUBLE_TICK) &&
2834                         hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
2835                 return;
2836 #endif
2837
2838         if (cfs_rq->nr_running > 1)
2839                 check_preempt_tick(cfs_rq, curr);
2840 }
2841
2842
2843 /**************************************************
2844  * CFS bandwidth control machinery
2845  */
2846
2847 #ifdef CONFIG_CFS_BANDWIDTH
2848
2849 #ifdef HAVE_JUMP_LABEL
2850 static struct static_key __cfs_bandwidth_used;
2851
2852 static inline bool cfs_bandwidth_used(void)
2853 {
2854         return static_key_false(&__cfs_bandwidth_used);
2855 }
2856
2857 void cfs_bandwidth_usage_inc(void)
2858 {
2859         static_key_slow_inc(&__cfs_bandwidth_used);
2860 }
2861
2862 void cfs_bandwidth_usage_dec(void)
2863 {
2864         static_key_slow_dec(&__cfs_bandwidth_used);
2865 }
2866 #else /* HAVE_JUMP_LABEL */
2867 static bool cfs_bandwidth_used(void)
2868 {
2869         return true;
2870 }
2871
2872 void cfs_bandwidth_usage_inc(void) {}
2873 void cfs_bandwidth_usage_dec(void) {}
2874 #endif /* HAVE_JUMP_LABEL */
2875
2876 /*
2877  * default period for cfs group bandwidth.
2878  * default: 0.1s, units: nanoseconds
2879  */
2880 static inline u64 default_cfs_period(void)
2881 {
2882         return 100000000ULL;
2883 }
2884
2885 static inline u64 sched_cfs_bandwidth_slice(void)
2886 {
2887         return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
2888 }
2889
2890 /*
2891  * Replenish runtime according to assigned quota and update expiration time.
2892  * We use sched_clock_cpu directly instead of rq->clock to avoid adding
2893  * additional synchronization around rq->lock.
2894  *
2895  * requires cfs_b->lock
2896  */
2897 void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b)
2898 {
2899         u64 now;
2900
2901         if (cfs_b->quota == RUNTIME_INF)
2902                 return;
2903
2904         now = sched_clock_cpu(smp_processor_id());
2905         cfs_b->runtime = cfs_b->quota;
2906         cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period);
2907 }
2908
2909 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
2910 {
2911         return &tg->cfs_bandwidth;
2912 }
2913
2914 /* rq->task_clock normalized against any time this cfs_rq has spent throttled */
2915 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
2916 {
2917         if (unlikely(cfs_rq->throttle_count))
2918                 return cfs_rq->throttled_clock_task;
2919
2920         return rq_clock_task(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
2921 }
2922
2923 /* returns 0 on failure to allocate runtime */
2924 static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
2925 {
2926         struct task_group *tg = cfs_rq->tg;
2927         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
2928         u64 amount = 0, min_amount, expires;
2929
2930         /* note: this is a positive sum as runtime_remaining <= 0 */
2931         min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;
2932
2933         raw_spin_lock(&cfs_b->lock);
2934         if (cfs_b->quota == RUNTIME_INF)
2935                 amount = min_amount;
2936         else {
2937                 /*
2938                  * If the bandwidth pool has become inactive, then at least one
2939                  * period must have elapsed since the last consumption.
2940                  * Refresh the global state and ensure bandwidth timer becomes
2941                  * active.
2942                  */
2943                 if (!cfs_b->timer_active) {
2944                         __refill_cfs_bandwidth_runtime(cfs_b);
2945                         __start_cfs_bandwidth(cfs_b);
2946                 }
2947
2948                 if (cfs_b->runtime > 0) {
2949                         amount = min(cfs_b->runtime, min_amount);
2950                         cfs_b->runtime -= amount;
2951                         cfs_b->idle = 0;
2952                 }
2953         }
2954         expires = cfs_b->runtime_expires;
2955         raw_spin_unlock(&cfs_b->lock);
2956
2957         cfs_rq->runtime_remaining += amount;
2958         /*
2959          * we may have advanced our local expiration to account for allowed
2960          * spread between our sched_clock and the one on which runtime was
2961          * issued.
2962          */
2963         if ((s64)(expires - cfs_rq->runtime_expires) > 0)
2964                 cfs_rq->runtime_expires = expires;
2965
2966         return cfs_rq->runtime_remaining > 0;
2967 }
2968
2969 /*
2970  * Note: This depends on the synchronization provided by sched_clock and the
2971  * fact that rq->clock snapshots this value.
2972  */
2973 static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
2974 {
2975         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
2976
2977         /* if the deadline is ahead of our clock, nothing to do */
2978         if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
2979                 return;
2980
2981         if (cfs_rq->runtime_remaining < 0)
2982                 return;
2983
2984         /*
2985          * If the local deadline has passed we have to consider the
2986          * possibility that our sched_clock is 'fast' and the global deadline
2987          * has not truly expired.
2988          *
2989          * Fortunately we can check determine whether this the case by checking
2990          * whether the global deadline has advanced.
2991          */
2992
2993         if ((s64)(cfs_rq->runtime_expires - cfs_b->runtime_expires) >= 0) {
2994                 /* extend local deadline, drift is bounded above by 2 ticks */
2995                 cfs_rq->runtime_expires += TICK_NSEC;
2996         } else {
2997                 /* global deadline is ahead, expiration has passed */
2998                 cfs_rq->runtime_remaining = 0;
2999         }
3000 }
3001
3002 static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3003 {
3004         /* dock delta_exec before expiring quota (as it could span periods) */
3005         cfs_rq->runtime_remaining -= delta_exec;
3006         expire_cfs_rq_runtime(cfs_rq);
3007
3008         if (likely(cfs_rq->runtime_remaining > 0))
3009                 return;
3010
3011         /*
3012          * if we're unable to extend our runtime we resched so that the active
3013          * hierarchy can be throttled
3014          */
3015         if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
3016                 resched_task(rq_of(cfs_rq)->curr);
3017 }
3018
3019 static __always_inline
3020 void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
3021 {
3022         if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
3023                 return;
3024
3025         __account_cfs_rq_runtime(cfs_rq, delta_exec);
3026 }
3027
3028 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3029 {
3030         return cfs_bandwidth_used() && cfs_rq->throttled;
3031 }
3032
3033 /* check whether cfs_rq, or any parent, is throttled */
3034 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3035 {
3036         return cfs_bandwidth_used() && cfs_rq->throttle_count;
3037 }
3038
3039 /*
3040  * Ensure that neither of the group entities corresponding to src_cpu or
3041  * dest_cpu are members of a throttled hierarchy when performing group
3042  * load-balance operations.
3043  */
3044 static inline int throttled_lb_pair(struct task_group *tg,
3045                                     int src_cpu, int dest_cpu)
3046 {
3047         struct cfs_rq *src_cfs_rq, *dest_cfs_rq;
3048
3049         src_cfs_rq = tg->cfs_rq[src_cpu];
3050         dest_cfs_rq = tg->cfs_rq[dest_cpu];
3051
3052         return throttled_hierarchy(src_cfs_rq) ||
3053                throttled_hierarchy(dest_cfs_rq);
3054 }
3055
3056 /* updated child weight may affect parent so we have to do this bottom up */
3057 static int tg_unthrottle_up(struct task_group *tg, void *data)
3058 {
3059         struct rq *rq = data;
3060         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3061
3062         cfs_rq->throttle_count--;
3063 #ifdef CONFIG_SMP
3064         if (!cfs_rq->throttle_count) {
3065                 /* adjust cfs_rq_clock_task() */
3066                 cfs_rq->throttled_clock_task_time += rq_clock_task(rq) -
3067                                              cfs_rq->throttled_clock_task;
3068         }
3069 #endif
3070
3071         return 0;
3072 }
3073
3074 static int tg_throttle_down(struct task_group *tg, void *data)
3075 {
3076         struct rq *rq = data;
3077         struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];
3078
3079         /* group is entering throttled state, stop time */
3080         if (!cfs_rq->throttle_count)
3081                 cfs_rq->throttled_clock_task = rq_clock_task(rq);
3082         cfs_rq->throttle_count++;
3083
3084         return 0;
3085 }
3086
3087 static void throttle_cfs_rq(struct cfs_rq *cfs_rq)
3088 {
3089         struct rq *rq = rq_of(cfs_rq);
3090         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3091         struct sched_entity *se;
3092         long task_delta, dequeue = 1;
3093
3094         se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];
3095
3096         /* freeze hierarchy runnable averages while throttled */
3097         rcu_read_lock();
3098         walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
3099         rcu_read_unlock();
3100
3101         task_delta = cfs_rq->h_nr_running;
3102         for_each_sched_entity(se) {
3103                 struct cfs_rq *qcfs_rq = cfs_rq_of(se);
3104                 /* throttled entity or throttle-on-deactivate */
3105                 if (!se->on_rq)
3106                         break;
3107
3108                 if (dequeue)
3109                         dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
3110                 qcfs_rq->h_nr_running -= task_delta;
3111
3112                 if (qcfs_rq->load.weight)
3113                         dequeue = 0;
3114         }
3115
3116         if (!se)
3117                 rq->nr_running -= task_delta;
3118
3119         cfs_rq->throttled = 1;
3120         cfs_rq->throttled_clock = rq_clock(rq);
3121         raw_spin_lock(&cfs_b->lock);
3122         list_add_tail_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq);
3123         if (!cfs_b->timer_active)
3124                 __start_cfs_bandwidth(cfs_b);
3125         raw_spin_unlock(&cfs_b->lock);
3126 }
3127
3128 void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
3129 {
3130         struct rq *rq = rq_of(cfs_rq);
3131         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3132         struct sched_entity *se;
3133         int enqueue = 1;
3134         long task_delta;
3135
3136         se = cfs_rq->tg->se[cpu_of(rq)];
3137
3138         cfs_rq->throttled = 0;
3139
3140         update_rq_clock(rq);
3141
3142         raw_spin_lock(&cfs_b->lock);
3143         cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
3144         list_del_rcu(&cfs_rq->throttled_list);
3145         raw_spin_unlock(&cfs_b->lock);
3146
3147         /* update hierarchical throttle state */
3148         walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
3149
3150         if (!cfs_rq->load.weight)
3151                 return;
3152
3153         task_delta = cfs_rq->h_nr_running;
3154         for_each_sched_entity(se) {
3155                 if (se->on_rq)
3156                         enqueue = 0;
3157
3158                 cfs_rq = cfs_rq_of(se);
3159                 if (enqueue)
3160                         enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);
3161                 cfs_rq->h_nr_running += task_delta;
3162
3163                 if (cfs_rq_throttled(cfs_rq))
3164                         break;
3165         }
3166
3167         if (!se)
3168                 rq->nr_running += task_delta;
3169
3170         /* determine whether we need to wake up potentially idle cpu */
3171         if (rq->curr == rq->idle && rq->cfs.nr_running)
3172                 resched_task(rq->curr);
3173 }
3174
3175 static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b,
3176                 u64 remaining, u64 expires)
3177 {
3178         struct cfs_rq *cfs_rq;
3179         u64 runtime = remaining;
3180
3181         rcu_read_lock();
3182         list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
3183                                 throttled_list) {
3184                 struct rq *rq = rq_of(cfs_rq);
3185
3186                 raw_spin_lock(&rq->lock);
3187                 if (!cfs_rq_throttled(cfs_rq))
3188                         goto next;
3189
3190                 runtime = -cfs_rq->runtime_remaining + 1;
3191                 if (runtime > remaining)
3192                         runtime = remaining;
3193                 remaining -= runtime;
3194
3195                 cfs_rq->runtime_remaining += runtime;
3196                 cfs_rq->runtime_expires = expires;
3197
3198                 /* we check whether we're throttled above */
3199                 if (cfs_rq->runtime_remaining > 0)
3200                         unthrottle_cfs_rq(cfs_rq);
3201
3202 next:
3203                 raw_spin_unlock(&rq->lock);
3204
3205                 if (!remaining)
3206                         break;
3207         }
3208         rcu_read_unlock();
3209
3210         return remaining;
3211 }
3212
3213 /*
3214  * Responsible for refilling a task_group's bandwidth and unthrottling its
3215  * cfs_rqs as appropriate. If there has been no activity within the last
3216  * period the timer is deactivated until scheduling resumes; cfs_b->idle is
3217  * used to track this state.
3218  */
3219 static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
3220 {
3221         u64 runtime, runtime_expires;
3222         int idle = 1, throttled;
3223
3224         raw_spin_lock(&cfs_b->lock);
3225         /* no need to continue the timer with no bandwidth constraint */
3226         if (cfs_b->quota == RUNTIME_INF)
3227                 goto out_unlock;
3228
3229         throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3230         /* idle depends on !throttled (for the case of a large deficit) */
3231         idle = cfs_b->idle && !throttled;
3232         cfs_b->nr_periods += overrun;
3233
3234         /* if we're going inactive then everything else can be deferred */
3235         if (idle)
3236                 goto out_unlock;
3237
3238         /*
3239          * if we have relooped after returning idle once, we need to update our
3240          * status as actually running, so that other cpus doing
3241          * __start_cfs_bandwidth will stop trying to cancel us.
3242          */
3243         cfs_b->timer_active = 1;
3244
3245         __refill_cfs_bandwidth_runtime(cfs_b);
3246
3247         if (!throttled) {
3248                 /* mark as potentially idle for the upcoming period */
3249                 cfs_b->idle = 1;
3250                 goto out_unlock;
3251         }
3252
3253         /* account preceding periods in which throttling occurred */
3254         cfs_b->nr_throttled += overrun;
3255
3256         /*
3257          * There are throttled entities so we must first use the new bandwidth
3258          * to unthrottle them before making it generally available.  This
3259          * ensures that all existing debts will be paid before a new cfs_rq is
3260          * allowed to run.
3261          */
3262         runtime = cfs_b->runtime;
3263         runtime_expires = cfs_b->runtime_expires;
3264         cfs_b->runtime = 0;
3265
3266         /*
3267          * This check is repeated as we are holding onto the new bandwidth
3268          * while we unthrottle.  This can potentially race with an unthrottled
3269          * group trying to acquire new bandwidth from the global pool.
3270          */
3271         while (throttled && runtime > 0) {
3272                 raw_spin_unlock(&cfs_b->lock);
3273                 /* we can't nest cfs_b->lock while distributing bandwidth */
3274                 runtime = distribute_cfs_runtime(cfs_b, runtime,
3275                                                  runtime_expires);
3276                 raw_spin_lock(&cfs_b->lock);
3277
3278                 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
3279         }
3280
3281         /* return (any) remaining runtime */
3282         cfs_b->runtime = runtime;
3283         /*
3284          * While we are ensured activity in the period following an
3285          * unthrottle, this also covers the case in which the new bandwidth is
3286          * insufficient to cover the existing bandwidth deficit.  (Forcing the
3287          * timer to remain active while there are any throttled entities.)
3288          */
3289         cfs_b->idle = 0;
3290 out_unlock:
3291         if (idle)
3292                 cfs_b->timer_active = 0;
3293         raw_spin_unlock(&cfs_b->lock);
3294
3295         return idle;
3296 }
3297
3298 /* a cfs_rq won't donate quota below this amount */
3299 static const u64 min_cfs_rq_runtime = 1 * NSEC_PER_MSEC;
3300 /* minimum remaining period time to redistribute slack quota */
3301 static const u64 min_bandwidth_expiration = 2 * NSEC_PER_MSEC;
3302 /* how long we wait to gather additional slack before distributing */
3303 static const u64 cfs_bandwidth_slack_period = 5 * NSEC_PER_MSEC;
3304
3305 /*
3306  * Are we near the end of the current quota period?
3307  *
3308  * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the
3309  * hrtimer base being cleared by __hrtimer_start_range_ns. In the case of
3310  * migrate_hrtimers, base is never cleared, so we are fine.
3311  */
3312 static int runtime_refresh_within(struct cfs_bandwidth *cfs_b, u64 min_expire)
3313 {
3314         struct hrtimer *refresh_timer = &cfs_b->period_timer;
3315         u64 remaining;
3316
3317         /* if the call-back is running a quota refresh is already occurring */
3318         if (hrtimer_callback_running(refresh_timer))
3319                 return 1;
3320
3321         /* is a quota refresh about to occur? */
3322         remaining = ktime_to_ns(hrtimer_expires_remaining(refresh_timer));
3323         if (remaining < min_expire)
3324                 return 1;
3325
3326         return 0;
3327 }
3328
3329 static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
3330 {
3331         u64 min_left = cfs_bandwidth_slack_period + min_bandwidth_expiration;
3332
3333         /* if there's a quota refresh soon don't bother with slack */
3334         if (runtime_refresh_within(cfs_b, min_left))
3335                 return;
3336
3337         start_bandwidth_timer(&cfs_b->slack_timer,
3338                                 ns_to_ktime(cfs_bandwidth_slack_period));
3339 }
3340
3341 /* we know any runtime found here is valid as update_curr() precedes return */
3342 static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3343 {
3344         struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3345         s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;
3346
3347         if (slack_runtime <= 0)
3348                 return;
3349
3350         raw_spin_lock(&cfs_b->lock);
3351         if (cfs_b->quota != RUNTIME_INF &&
3352             cfs_rq->runtime_expires == cfs_b->runtime_expires) {
3353                 cfs_b->runtime += slack_runtime;
3354
3355                 /* we are under rq->lock, defer unthrottling using a timer */
3356                 if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
3357                     !list_empty(&cfs_b->throttled_cfs_rq))
3358                         start_cfs_slack_bandwidth(cfs_b);
3359         }
3360         raw_spin_unlock(&cfs_b->lock);
3361
3362         /* even if it's not valid for return we don't want to try again */
3363         cfs_rq->runtime_remaining -= slack_runtime;
3364 }
3365
3366 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3367 {
3368         if (!cfs_bandwidth_used())
3369                 return;
3370
3371         if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
3372                 return;
3373
3374         __return_cfs_rq_runtime(cfs_rq);
3375 }
3376
3377 /*
3378  * This is done with a timer (instead of inline with bandwidth return) since
3379  * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs.
3380  */
3381 static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
3382 {
3383         u64 runtime = 0, slice = sched_cfs_bandwidth_slice();
3384         u64 expires;
3385
3386         /* confirm we're still not at a refresh boundary */
3387         raw_spin_lock(&cfs_b->lock);
3388         if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) {
3389                 raw_spin_unlock(&cfs_b->lock);
3390                 return;
3391         }
3392
3393         if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice) {
3394                 runtime = cfs_b->runtime;
3395                 cfs_b->runtime = 0;
3396         }
3397         expires = cfs_b->runtime_expires;
3398         raw_spin_unlock(&cfs_b->lock);