xref: /openbmc/linux/kernel/sched/fair.c (revision a2fb4d78)
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);
3399 
3400 	if (!runtime)
3401 		return;
3402 
3403 	runtime = distribute_cfs_runtime(cfs_b, runtime, expires);
3404 
3405 	raw_spin_lock(&cfs_b->lock);
3406 	if (expires == cfs_b->runtime_expires)
3407 		cfs_b->runtime = runtime;
3408 	raw_spin_unlock(&cfs_b->lock);
3409 }
3410 
3411 /*
3412  * When a group wakes up we want to make sure that its quota is not already
3413  * expired/exceeded, otherwise it may be allowed to steal additional ticks of
3414  * runtime as update_curr() throttling can not not trigger until it's on-rq.
3415  */
3416 static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
3417 {
3418 	if (!cfs_bandwidth_used())
3419 		return;
3420 
3421 	/* an active group must be handled by the update_curr()->put() path */
3422 	if (!cfs_rq->runtime_enabled || cfs_rq->curr)
3423 		return;
3424 
3425 	/* ensure the group is not already throttled */
3426 	if (cfs_rq_throttled(cfs_rq))
3427 		return;
3428 
3429 	/* update runtime allocation */
3430 	account_cfs_rq_runtime(cfs_rq, 0);
3431 	if (cfs_rq->runtime_remaining <= 0)
3432 		throttle_cfs_rq(cfs_rq);
3433 }
3434 
3435 /* conditionally throttle active cfs_rq's from put_prev_entity() */
3436 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3437 {
3438 	if (!cfs_bandwidth_used())
3439 		return;
3440 
3441 	if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0))
3442 		return;
3443 
3444 	/*
3445 	 * it's possible for a throttled entity to be forced into a running
3446 	 * state (e.g. set_curr_task), in this case we're finished.
3447 	 */
3448 	if (cfs_rq_throttled(cfs_rq))
3449 		return;
3450 
3451 	throttle_cfs_rq(cfs_rq);
3452 }
3453 
3454 static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer)
3455 {
3456 	struct cfs_bandwidth *cfs_b =
3457 		container_of(timer, struct cfs_bandwidth, slack_timer);
3458 	do_sched_cfs_slack_timer(cfs_b);
3459 
3460 	return HRTIMER_NORESTART;
3461 }
3462 
3463 static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
3464 {
3465 	struct cfs_bandwidth *cfs_b =
3466 		container_of(timer, struct cfs_bandwidth, period_timer);
3467 	ktime_t now;
3468 	int overrun;
3469 	int idle = 0;
3470 
3471 	for (;;) {
3472 		now = hrtimer_cb_get_time(timer);
3473 		overrun = hrtimer_forward(timer, now, cfs_b->period);
3474 
3475 		if (!overrun)
3476 			break;
3477 
3478 		idle = do_sched_cfs_period_timer(cfs_b, overrun);
3479 	}
3480 
3481 	return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
3482 }
3483 
3484 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3485 {
3486 	raw_spin_lock_init(&cfs_b->lock);
3487 	cfs_b->runtime = 0;
3488 	cfs_b->quota = RUNTIME_INF;
3489 	cfs_b->period = ns_to_ktime(default_cfs_period());
3490 
3491 	INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
3492 	hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3493 	cfs_b->period_timer.function = sched_cfs_period_timer;
3494 	hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
3495 	cfs_b->slack_timer.function = sched_cfs_slack_timer;
3496 }
3497 
3498 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq)
3499 {
3500 	cfs_rq->runtime_enabled = 0;
3501 	INIT_LIST_HEAD(&cfs_rq->throttled_list);
3502 }
3503 
3504 /* requires cfs_b->lock, may release to reprogram timer */
3505 void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3506 {
3507 	/*
3508 	 * The timer may be active because we're trying to set a new bandwidth
3509 	 * period or because we're racing with the tear-down path
3510 	 * (timer_active==0 becomes visible before the hrtimer call-back
3511 	 * terminates).  In either case we ensure that it's re-programmed
3512 	 */
3513 	while (unlikely(hrtimer_active(&cfs_b->period_timer)) &&
3514 	       hrtimer_try_to_cancel(&cfs_b->period_timer) < 0) {
3515 		/* bounce the lock to allow do_sched_cfs_period_timer to run */
3516 		raw_spin_unlock(&cfs_b->lock);
3517 		cpu_relax();
3518 		raw_spin_lock(&cfs_b->lock);
3519 		/* if someone else restarted the timer then we're done */
3520 		if (cfs_b->timer_active)
3521 			return;
3522 	}
3523 
3524 	cfs_b->timer_active = 1;
3525 	start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
3526 }
3527 
3528 static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b)
3529 {
3530 	hrtimer_cancel(&cfs_b->period_timer);
3531 	hrtimer_cancel(&cfs_b->slack_timer);
3532 }
3533 
3534 static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq)
3535 {
3536 	struct cfs_rq *cfs_rq;
3537 
3538 	for_each_leaf_cfs_rq(rq, cfs_rq) {
3539 		struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
3540 
3541 		if (!cfs_rq->runtime_enabled)
3542 			continue;
3543 
3544 		/*
3545 		 * clock_task is not advancing so we just need to make sure
3546 		 * there's some valid quota amount
3547 		 */
3548 		cfs_rq->runtime_remaining = cfs_b->quota;
3549 		if (cfs_rq_throttled(cfs_rq))
3550 			unthrottle_cfs_rq(cfs_rq);
3551 	}
3552 }
3553 
3554 #else /* CONFIG_CFS_BANDWIDTH */
3555 static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq)
3556 {
3557 	return rq_clock_task(rq_of(cfs_rq));
3558 }
3559 
3560 static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) {}
3561 static void check_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3562 static void check_enqueue_throttle(struct cfs_rq *cfs_rq) {}
3563 static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3564 
3565 static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq)
3566 {
3567 	return 0;
3568 }
3569 
3570 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
3571 {
3572 	return 0;
3573 }
3574 
3575 static inline int throttled_lb_pair(struct task_group *tg,
3576 				    int src_cpu, int dest_cpu)
3577 {
3578 	return 0;
3579 }
3580 
3581 void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
3582 
3583 #ifdef CONFIG_FAIR_GROUP_SCHED
3584 static void init_cfs_rq_runtime(struct cfs_rq *cfs_rq) {}
3585 #endif
3586 
3587 static inline struct cfs_bandwidth *tg_cfs_bandwidth(struct task_group *tg)
3588 {
3589 	return NULL;
3590 }
3591 static inline void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) {}
3592 static inline void unthrottle_offline_cfs_rqs(struct rq *rq) {}
3593 
3594 #endif /* CONFIG_CFS_BANDWIDTH */
3595 
3596 /**************************************************
3597  * CFS operations on tasks:
3598  */
3599 
3600 #ifdef CONFIG_SCHED_HRTICK
3601 static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
3602 {
3603 	struct sched_entity *se = &p->se;
3604 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
3605 
3606 	WARN_ON(task_rq(p) != rq);
3607 
3608 	if (cfs_rq->nr_running > 1) {
3609 		u64 slice = sched_slice(cfs_rq, se);
3610 		u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
3611 		s64 delta = slice - ran;
3612 
3613 		if (delta < 0) {
3614 			if (rq->curr == p)
3615 				resched_task(p);
3616 			return;
3617 		}
3618 
3619 		/*
3620 		 * Don't schedule slices shorter than 10000ns, that just
3621 		 * doesn't make sense. Rely on vruntime for fairness.
3622 		 */
3623 		if (rq->curr != p)
3624 			delta = max_t(s64, 10000LL, delta);
3625 
3626 		hrtick_start(rq, delta);
3627 	}
3628 }
3629 
3630 /*
3631  * called from enqueue/dequeue and updates the hrtick when the
3632  * current task is from our class and nr_running is low enough
3633  * to matter.
3634  */
3635 static void hrtick_update(struct rq *rq)
3636 {
3637 	struct task_struct *curr = rq->curr;
3638 
3639 	if (!hrtick_enabled(rq) || curr->sched_class != &fair_sched_class)
3640 		return;
3641 
3642 	if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
3643 		hrtick_start_fair(rq, curr);
3644 }
3645 #else /* !CONFIG_SCHED_HRTICK */
3646 static inline void
3647 hrtick_start_fair(struct rq *rq, struct task_struct *p)
3648 {
3649 }
3650 
3651 static inline void hrtick_update(struct rq *rq)
3652 {
3653 }
3654 #endif
3655 
3656 /*
3657  * The enqueue_task method is called before nr_running is
3658  * increased. Here we update the fair scheduling stats and
3659  * then put the task into the rbtree:
3660  */
3661 static void
3662 enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
3663 {
3664 	struct cfs_rq *cfs_rq;
3665 	struct sched_entity *se = &p->se;
3666 
3667 	for_each_sched_entity(se) {
3668 		if (se->on_rq)
3669 			break;
3670 		cfs_rq = cfs_rq_of(se);
3671 		enqueue_entity(cfs_rq, se, flags);
3672 
3673 		/*
3674 		 * end evaluation on encountering a throttled cfs_rq
3675 		 *
3676 		 * note: in the case of encountering a throttled cfs_rq we will
3677 		 * post the final h_nr_running increment below.
3678 		*/
3679 		if (cfs_rq_throttled(cfs_rq))
3680 			break;
3681 		cfs_rq->h_nr_running++;
3682 
3683 		flags = ENQUEUE_WAKEUP;
3684 	}
3685 
3686 	for_each_sched_entity(se) {
3687 		cfs_rq = cfs_rq_of(se);
3688 		cfs_rq->h_nr_running++;
3689 
3690 		if (cfs_rq_throttled(cfs_rq))
3691 			break;
3692 
3693 		update_cfs_shares(cfs_rq);
3694 		update_entity_load_avg(se, 1);
3695 	}
3696 
3697 	if (!se) {
3698 		update_rq_runnable_avg(rq, rq->nr_running);
3699 		inc_nr_running(rq);
3700 	}
3701 	hrtick_update(rq);
3702 }
3703 
3704 static void set_next_buddy(struct sched_entity *se);
3705 
3706 /*
3707  * The dequeue_task method is called before nr_running is
3708  * decreased. We remove the task from the rbtree and
3709  * update the fair scheduling stats:
3710  */
3711 static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
3712 {
3713 	struct cfs_rq *cfs_rq;
3714 	struct sched_entity *se = &p->se;
3715 	int task_sleep = flags & DEQUEUE_SLEEP;
3716 
3717 	for_each_sched_entity(se) {
3718 		cfs_rq = cfs_rq_of(se);
3719 		dequeue_entity(cfs_rq, se, flags);
3720 
3721 		/*
3722 		 * end evaluation on encountering a throttled cfs_rq
3723 		 *
3724 		 * note: in the case of encountering a throttled cfs_rq we will
3725 		 * post the final h_nr_running decrement below.
3726 		*/
3727 		if (cfs_rq_throttled(cfs_rq))
3728 			break;
3729 		cfs_rq->h_nr_running--;
3730 
3731 		/* Don't dequeue parent if it has other entities besides us */
3732 		if (cfs_rq->load.weight) {
3733 			/*
3734 			 * Bias pick_next to pick a task from this cfs_rq, as
3735 			 * p is sleeping when it is within its sched_slice.
3736 			 */
3737 			if (task_sleep && parent_entity(se))
3738 				set_next_buddy(parent_entity(se));
3739 
3740 			/* avoid re-evaluating load for this entity */
3741 			se = parent_entity(se);
3742 			break;
3743 		}
3744 		flags |= DEQUEUE_SLEEP;
3745 	}
3746 
3747 	for_each_sched_entity(se) {
3748 		cfs_rq = cfs_rq_of(se);
3749 		cfs_rq->h_nr_running--;
3750 
3751 		if (cfs_rq_throttled(cfs_rq))
3752 			break;
3753 
3754 		update_cfs_shares(cfs_rq);
3755 		update_entity_load_avg(se, 1);
3756 	}
3757 
3758 	if (!se) {
3759 		dec_nr_running(rq);
3760 		update_rq_runnable_avg(rq, 1);
3761 	}
3762 	hrtick_update(rq);
3763 }
3764 
3765 #ifdef CONFIG_SMP
3766 /* Used instead of source_load when we know the type == 0 */
3767 static unsigned long weighted_cpuload(const int cpu)
3768 {
3769 	return cpu_rq(cpu)->cfs.runnable_load_avg;
3770 }
3771 
3772 /*
3773  * Return a low guess at the load of a migration-source cpu weighted
3774  * according to the scheduling class and "nice" value.
3775  *
3776  * We want to under-estimate the load of migration sources, to
3777  * balance conservatively.
3778  */
3779 static unsigned long source_load(int cpu, int type)
3780 {
3781 	struct rq *rq = cpu_rq(cpu);
3782 	unsigned long total = weighted_cpuload(cpu);
3783 
3784 	if (type == 0 || !sched_feat(LB_BIAS))
3785 		return total;
3786 
3787 	return min(rq->cpu_load[type-1], total);
3788 }
3789 
3790 /*
3791  * Return a high guess at the load of a migration-target cpu weighted
3792  * according to the scheduling class and "nice" value.
3793  */
3794 static unsigned long target_load(int cpu, int type)
3795 {
3796 	struct rq *rq = cpu_rq(cpu);
3797 	unsigned long total = weighted_cpuload(cpu);
3798 
3799 	if (type == 0 || !sched_feat(LB_BIAS))
3800 		return total;
3801 
3802 	return max(rq->cpu_load[type-1], total);
3803 }
3804 
3805 static unsigned long power_of(int cpu)
3806 {
3807 	return cpu_rq(cpu)->cpu_power;
3808 }
3809 
3810 static unsigned long cpu_avg_load_per_task(int cpu)
3811 {
3812 	struct rq *rq = cpu_rq(cpu);
3813 	unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
3814 	unsigned long load_avg = rq->cfs.runnable_load_avg;
3815 
3816 	if (nr_running)
3817 		return load_avg / nr_running;
3818 
3819 	return 0;
3820 }
3821 
3822 static void record_wakee(struct task_struct *p)
3823 {
3824 	/*
3825 	 * Rough decay (wiping) for cost saving, don't worry
3826 	 * about the boundary, really active task won't care
3827 	 * about the loss.
3828 	 */
3829 	if (jiffies > current->wakee_flip_decay_ts + HZ) {
3830 		current->wakee_flips = 0;
3831 		current->wakee_flip_decay_ts = jiffies;
3832 	}
3833 
3834 	if (current->last_wakee != p) {
3835 		current->last_wakee = p;
3836 		current->wakee_flips++;
3837 	}
3838 }
3839 
3840 static void task_waking_fair(struct task_struct *p)
3841 {
3842 	struct sched_entity *se = &p->se;
3843 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
3844 	u64 min_vruntime;
3845 
3846 #ifndef CONFIG_64BIT
3847 	u64 min_vruntime_copy;
3848 
3849 	do {
3850 		min_vruntime_copy = cfs_rq->min_vruntime_copy;
3851 		smp_rmb();
3852 		min_vruntime = cfs_rq->min_vruntime;
3853 	} while (min_vruntime != min_vruntime_copy);
3854 #else
3855 	min_vruntime = cfs_rq->min_vruntime;
3856 #endif
3857 
3858 	se->vruntime -= min_vruntime;
3859 	record_wakee(p);
3860 }
3861 
3862 #ifdef CONFIG_FAIR_GROUP_SCHED
3863 /*
3864  * effective_load() calculates the load change as seen from the root_task_group
3865  *
3866  * Adding load to a group doesn't make a group heavier, but can cause movement
3867  * of group shares between cpus. Assuming the shares were perfectly aligned one
3868  * can calculate the shift in shares.
3869  *
3870  * Calculate the effective load difference if @wl is added (subtracted) to @tg
3871  * on this @cpu and results in a total addition (subtraction) of @wg to the
3872  * total group weight.
3873  *
3874  * Given a runqueue weight distribution (rw_i) we can compute a shares
3875  * distribution (s_i) using:
3876  *
3877  *   s_i = rw_i / \Sum rw_j						(1)
3878  *
3879  * Suppose we have 4 CPUs and our @tg is a direct child of the root group and
3880  * has 7 equal weight tasks, distributed as below (rw_i), with the resulting
3881  * shares distribution (s_i):
3882  *
3883  *   rw_i = {   2,   4,   1,   0 }
3884  *   s_i  = { 2/7, 4/7, 1/7,   0 }
3885  *
3886  * As per wake_affine() we're interested in the load of two CPUs (the CPU the
3887  * task used to run on and the CPU the waker is running on), we need to
3888  * compute the effect of waking a task on either CPU and, in case of a sync
3889  * wakeup, compute the effect of the current task going to sleep.
3890  *
3891  * So for a change of @wl to the local @cpu with an overall group weight change
3892  * of @wl we can compute the new shares distribution (s'_i) using:
3893  *
3894  *   s'_i = (rw_i + @wl) / (@wg + \Sum rw_j)				(2)
3895  *
3896  * Suppose we're interested in CPUs 0 and 1, and want to compute the load
3897  * differences in waking a task to CPU 0. The additional task changes the
3898  * weight and shares distributions like:
3899  *
3900  *   rw'_i = {   3,   4,   1,   0 }
3901  *   s'_i  = { 3/8, 4/8, 1/8,   0 }
3902  *
3903  * We can then compute the difference in effective weight by using:
3904  *
3905  *   dw_i = S * (s'_i - s_i)						(3)
3906  *
3907  * Where 'S' is the group weight as seen by its parent.
3908  *
3909  * Therefore the effective change in loads on CPU 0 would be 5/56 (3/8 - 2/7)
3910  * times the weight of the group. The effect on CPU 1 would be -4/56 (4/8 -
3911  * 4/7) times the weight of the group.
3912  */
3913 static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
3914 {
3915 	struct sched_entity *se = tg->se[cpu];
3916 
3917 	if (!tg->parent)	/* the trivial, non-cgroup case */
3918 		return wl;
3919 
3920 	for_each_sched_entity(se) {
3921 		long w, W;
3922 
3923 		tg = se->my_q->tg;
3924 
3925 		/*
3926 		 * W = @wg + \Sum rw_j
3927 		 */
3928 		W = wg + calc_tg_weight(tg, se->my_q);
3929 
3930 		/*
3931 		 * w = rw_i + @wl
3932 		 */
3933 		w = se->my_q->load.weight + wl;
3934 
3935 		/*
3936 		 * wl = S * s'_i; see (2)
3937 		 */
3938 		if (W > 0 && w < W)
3939 			wl = (w * tg->shares) / W;
3940 		else
3941 			wl = tg->shares;
3942 
3943 		/*
3944 		 * Per the above, wl is the new se->load.weight value; since
3945 		 * those are clipped to [MIN_SHARES, ...) do so now. See
3946 		 * calc_cfs_shares().
3947 		 */
3948 		if (wl < MIN_SHARES)
3949 			wl = MIN_SHARES;
3950 
3951 		/*
3952 		 * wl = dw_i = S * (s'_i - s_i); see (3)
3953 		 */
3954 		wl -= se->load.weight;
3955 
3956 		/*
3957 		 * Recursively apply this logic to all parent groups to compute
3958 		 * the final effective load change on the root group. Since
3959 		 * only the @tg group gets extra weight, all parent groups can
3960 		 * only redistribute existing shares. @wl is the shift in shares
3961 		 * resulting from this level per the above.
3962 		 */
3963 		wg = 0;
3964 	}
3965 
3966 	return wl;
3967 }
3968 #else
3969 
3970 static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
3971 {
3972 	return wl;
3973 }
3974 
3975 #endif
3976 
3977 static int wake_wide(struct task_struct *p)
3978 {
3979 	int factor = this_cpu_read(sd_llc_size);
3980 
3981 	/*
3982 	 * Yeah, it's the switching-frequency, could means many wakee or
3983 	 * rapidly switch, use factor here will just help to automatically
3984 	 * adjust the loose-degree, so bigger node will lead to more pull.
3985 	 */
3986 	if (p->wakee_flips > factor) {
3987 		/*
3988 		 * wakee is somewhat hot, it needs certain amount of cpu
3989 		 * resource, so if waker is far more hot, prefer to leave
3990 		 * it alone.
3991 		 */
3992 		if (current->wakee_flips > (factor * p->wakee_flips))
3993 			return 1;
3994 	}
3995 
3996 	return 0;
3997 }
3998 
3999 static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
4000 {
4001 	s64 this_load, load;
4002 	int idx, this_cpu, prev_cpu;
4003 	unsigned long tl_per_task;
4004 	struct task_group *tg;
4005 	unsigned long weight;
4006 	int balanced;
4007 
4008 	/*
4009 	 * If we wake multiple tasks be careful to not bounce
4010 	 * ourselves around too much.
4011 	 */
4012 	if (wake_wide(p))
4013 		return 0;
4014 
4015 	idx	  = sd->wake_idx;
4016 	this_cpu  = smp_processor_id();
4017 	prev_cpu  = task_cpu(p);
4018 	load	  = source_load(prev_cpu, idx);
4019 	this_load = target_load(this_cpu, idx);
4020 
4021 	/*
4022 	 * If sync wakeup then subtract the (maximum possible)
4023 	 * effect of the currently running task from the load
4024 	 * of the current CPU:
4025 	 */
4026 	if (sync) {
4027 		tg = task_group(current);
4028 		weight = current->se.load.weight;
4029 
4030 		this_load += effective_load(tg, this_cpu, -weight, -weight);
4031 		load += effective_load(tg, prev_cpu, 0, -weight);
4032 	}
4033 
4034 	tg = task_group(p);
4035 	weight = p->se.load.weight;
4036 
4037 	/*
4038 	 * In low-load situations, where prev_cpu is idle and this_cpu is idle
4039 	 * due to the sync cause above having dropped this_load to 0, we'll
4040 	 * always have an imbalance, but there's really nothing you can do
4041 	 * about that, so that's good too.
4042 	 *
4043 	 * Otherwise check if either cpus are near enough in load to allow this
4044 	 * task to be woken on this_cpu.
4045 	 */
4046 	if (this_load > 0) {
4047 		s64 this_eff_load, prev_eff_load;
4048 
4049 		this_eff_load = 100;
4050 		this_eff_load *= power_of(prev_cpu);
4051 		this_eff_load *= this_load +
4052 			effective_load(tg, this_cpu, weight, weight);
4053 
4054 		prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
4055 		prev_eff_load *= power_of(this_cpu);
4056 		prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
4057 
4058 		balanced = this_eff_load <= prev_eff_load;
4059 	} else
4060 		balanced = true;
4061 
4062 	/*
4063 	 * If the currently running task will sleep within
4064 	 * a reasonable amount of time then attract this newly
4065 	 * woken task:
4066 	 */
4067 	if (sync && balanced)
4068 		return 1;
4069 
4070 	schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);
4071 	tl_per_task = cpu_avg_load_per_task(this_cpu);
4072 
4073 	if (balanced ||
4074 	    (this_load <= load &&
4075 	     this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
4076 		/*
4077 		 * This domain has SD_WAKE_AFFINE and
4078 		 * p is cache cold in this domain, and
4079 		 * there is no bad imbalance.
4080 		 */
4081 		schedstat_inc(sd, ttwu_move_affine);
4082 		schedstat_inc(p, se.statistics.nr_wakeups_affine);
4083 
4084 		return 1;
4085 	}
4086 	return 0;
4087 }
4088 
4089 /*
4090  * find_idlest_group finds and returns the least busy CPU group within the
4091  * domain.
4092  */
4093 static struct sched_group *
4094 find_idlest_group(struct sched_domain *sd, struct task_struct *p,
4095 		  int this_cpu, int sd_flag)
4096 {
4097 	struct sched_group *idlest = NULL, *group = sd->groups;
4098 	unsigned long min_load = ULONG_MAX, this_load = 0;
4099 	int load_idx = sd->forkexec_idx;
4100 	int imbalance = 100 + (sd->imbalance_pct-100)/2;
4101 
4102 	if (sd_flag & SD_BALANCE_WAKE)
4103 		load_idx = sd->wake_idx;
4104 
4105 	do {
4106 		unsigned long load, avg_load;
4107 		int local_group;
4108 		int i;
4109 
4110 		/* Skip over this group if it has no CPUs allowed */
4111 		if (!cpumask_intersects(sched_group_cpus(group),
4112 					tsk_cpus_allowed(p)))
4113 			continue;
4114 
4115 		local_group = cpumask_test_cpu(this_cpu,
4116 					       sched_group_cpus(group));
4117 
4118 		/* Tally up the load of all CPUs in the group */
4119 		avg_load = 0;
4120 
4121 		for_each_cpu(i, sched_group_cpus(group)) {
4122 			/* Bias balancing toward cpus of our domain */
4123 			if (local_group)
4124 				load = source_load(i, load_idx);
4125 			else
4126 				load = target_load(i, load_idx);
4127 
4128 			avg_load += load;
4129 		}
4130 
4131 		/* Adjust by relative CPU power of the group */
4132 		avg_load = (avg_load * SCHED_POWER_SCALE) / group->sgp->power;
4133 
4134 		if (local_group) {
4135 			this_load = avg_load;
4136 		} else if (avg_load < min_load) {
4137 			min_load = avg_load;
4138 			idlest = group;
4139 		}
4140 	} while (group = group->next, group != sd->groups);
4141 
4142 	if (!idlest || 100*this_load < imbalance*min_load)
4143 		return NULL;
4144 	return idlest;
4145 }
4146 
4147 /*
4148  * find_idlest_cpu - find the idlest cpu among the cpus in group.
4149  */
4150 static int
4151 find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
4152 {
4153 	unsigned long load, min_load = ULONG_MAX;
4154 	int idlest = -1;
4155 	int i;
4156 
4157 	/* Traverse only the allowed CPUs */
4158 	for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) {
4159 		load = weighted_cpuload(i);
4160 
4161 		if (load < min_load || (load == min_load && i == this_cpu)) {
4162 			min_load = load;
4163 			idlest = i;
4164 		}
4165 	}
4166 
4167 	return idlest;
4168 }
4169 
4170 /*
4171  * Try and locate an idle CPU in the sched_domain.
4172  */
4173 static int select_idle_sibling(struct task_struct *p, int target)
4174 {
4175 	struct sched_domain *sd;
4176 	struct sched_group *sg;
4177 	int i = task_cpu(p);
4178 
4179 	if (idle_cpu(target))
4180 		return target;
4181 
4182 	/*
4183 	 * If the prevous cpu is cache affine and idle, don't be stupid.
4184 	 */
4185 	if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
4186 		return i;
4187 
4188 	/*
4189 	 * Otherwise, iterate the domains and find an elegible idle cpu.
4190 	 */
4191 	sd = rcu_dereference(per_cpu(sd_llc, target));
4192 	for_each_lower_domain(sd) {
4193 		sg = sd->groups;
4194 		do {
4195 			if (!cpumask_intersects(sched_group_cpus(sg),
4196 						tsk_cpus_allowed(p)))
4197 				goto next;
4198 
4199 			for_each_cpu(i, sched_group_cpus(sg)) {
4200 				if (i == target || !idle_cpu(i))
4201 					goto next;
4202 			}
4203 
4204 			target = cpumask_first_and(sched_group_cpus(sg),
4205 					tsk_cpus_allowed(p));
4206 			goto done;
4207 next:
4208 			sg = sg->next;
4209 		} while (sg != sd->groups);
4210 	}
4211 done:
4212 	return target;
4213 }
4214 
4215 /*
4216  * sched_balance_self: balance the current task (running on cpu) in domains
4217  * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
4218  * SD_BALANCE_EXEC.
4219  *
4220  * Balance, ie. select the least loaded group.
4221  *
4222  * Returns the target CPU number, or the same CPU if no balancing is needed.
4223  *
4224  * preempt must be disabled.
4225  */
4226 static int
4227 select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags)
4228 {
4229 	struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
4230 	int cpu = smp_processor_id();
4231 	int new_cpu = cpu;
4232 	int want_affine = 0;
4233 	int sync = wake_flags & WF_SYNC;
4234 
4235 	if (p->nr_cpus_allowed == 1)
4236 		return prev_cpu;
4237 
4238 	if (sd_flag & SD_BALANCE_WAKE) {
4239 		if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
4240 			want_affine = 1;
4241 		new_cpu = prev_cpu;
4242 	}
4243 
4244 	rcu_read_lock();
4245 	for_each_domain(cpu, tmp) {
4246 		if (!(tmp->flags & SD_LOAD_BALANCE))
4247 			continue;
4248 
4249 		/*
4250 		 * If both cpu and prev_cpu are part of this domain,
4251 		 * cpu is a valid SD_WAKE_AFFINE target.
4252 		 */
4253 		if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
4254 		    cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
4255 			affine_sd = tmp;
4256 			break;
4257 		}
4258 
4259 		if (tmp->flags & sd_flag)
4260 			sd = tmp;
4261 	}
4262 
4263 	if (affine_sd) {
4264 		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
4265 			prev_cpu = cpu;
4266 
4267 		new_cpu = select_idle_sibling(p, prev_cpu);
4268 		goto unlock;
4269 	}
4270 
4271 	while (sd) {
4272 		struct sched_group *group;
4273 		int weight;
4274 
4275 		if (!(sd->flags & sd_flag)) {
4276 			sd = sd->child;
4277 			continue;
4278 		}
4279 
4280 		group = find_idlest_group(sd, p, cpu, sd_flag);
4281 		if (!group) {
4282 			sd = sd->child;
4283 			continue;
4284 		}
4285 
4286 		new_cpu = find_idlest_cpu(group, p, cpu);
4287 		if (new_cpu == -1 || new_cpu == cpu) {
4288 			/* Now try balancing at a lower domain level of cpu */
4289 			sd = sd->child;
4290 			continue;
4291 		}
4292 
4293 		/* Now try balancing at a lower domain level of new_cpu */
4294 		cpu = new_cpu;
4295 		weight = sd->span_weight;
4296 		sd = NULL;
4297 		for_each_domain(cpu, tmp) {
4298 			if (weight <= tmp->span_weight)
4299 				break;
4300 			if (tmp->flags & sd_flag)
4301 				sd = tmp;
4302 		}
4303 		/* while loop will break here if sd == NULL */
4304 	}
4305 unlock:
4306 	rcu_read_unlock();
4307 
4308 	return new_cpu;
4309 }
4310 
4311 /*
4312  * Called immediately before a task is migrated to a new cpu; task_cpu(p) and
4313  * cfs_rq_of(p) references at time of call are still valid and identify the
4314  * previous cpu.  However, the caller only guarantees p->pi_lock is held; no
4315  * other assumptions, including the state of rq->lock, should be made.
4316  */
4317 static void
4318 migrate_task_rq_fair(struct task_struct *p, int next_cpu)
4319 {
4320 	struct sched_entity *se = &p->se;
4321 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
4322 
4323 	/*
4324 	 * Load tracking: accumulate removed load so that it can be processed
4325 	 * when we next update owning cfs_rq under rq->lock.  Tasks contribute
4326 	 * to blocked load iff they have a positive decay-count.  It can never
4327 	 * be negative here since on-rq tasks have decay-count == 0.
4328 	 */
4329 	if (se->avg.decay_count) {
4330 		se->avg.decay_count = -__synchronize_entity_decay(se);
4331 		atomic_long_add(se->avg.load_avg_contrib,
4332 						&cfs_rq->removed_load);
4333 	}
4334 }
4335 #endif /* CONFIG_SMP */
4336 
4337 static unsigned long
4338 wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
4339 {
4340 	unsigned long gran = sysctl_sched_wakeup_granularity;
4341 
4342 	/*
4343 	 * Since its curr running now, convert the gran from real-time
4344 	 * to virtual-time in his units.
4345 	 *
4346 	 * By using 'se' instead of 'curr' we penalize light tasks, so
4347 	 * they get preempted easier. That is, if 'se' < 'curr' then
4348 	 * the resulting gran will be larger, therefore penalizing the
4349 	 * lighter, if otoh 'se' > 'curr' then the resulting gran will
4350 	 * be smaller, again penalizing the lighter task.
4351 	 *
4352 	 * This is especially important for buddies when the leftmost
4353 	 * task is higher priority than the buddy.
4354 	 */
4355 	return calc_delta_fair(gran, se);
4356 }
4357 
4358 /*
4359  * Should 'se' preempt 'curr'.
4360  *
4361  *             |s1
4362  *        |s2
4363  *   |s3
4364  *         g
4365  *      |<--->|c
4366  *
4367  *  w(c, s1) = -1
4368  *  w(c, s2) =  0
4369  *  w(c, s3) =  1
4370  *
4371  */
4372 static int
4373 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
4374 {
4375 	s64 gran, vdiff = curr->vruntime - se->vruntime;
4376 
4377 	if (vdiff <= 0)
4378 		return -1;
4379 
4380 	gran = wakeup_gran(curr, se);
4381 	if (vdiff > gran)
4382 		return 1;
4383 
4384 	return 0;
4385 }
4386 
4387 static void set_last_buddy(struct sched_entity *se)
4388 {
4389 	if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
4390 		return;
4391 
4392 	for_each_sched_entity(se)
4393 		cfs_rq_of(se)->last = se;
4394 }
4395 
4396 static void set_next_buddy(struct sched_entity *se)
4397 {
4398 	if (entity_is_task(se) && unlikely(task_of(se)->policy == SCHED_IDLE))
4399 		return;
4400 
4401 	for_each_sched_entity(se)
4402 		cfs_rq_of(se)->next = se;
4403 }
4404 
4405 static void set_skip_buddy(struct sched_entity *se)
4406 {
4407 	for_each_sched_entity(se)
4408 		cfs_rq_of(se)->skip = se;
4409 }
4410 
4411 /*
4412  * Preempt the current task with a newly woken task if needed:
4413  */
4414 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
4415 {
4416 	struct task_struct *curr = rq->curr;
4417 	struct sched_entity *se = &curr->se, *pse = &p->se;
4418 	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
4419 	int scale = cfs_rq->nr_running >= sched_nr_latency;
4420 	int next_buddy_marked = 0;
4421 
4422 	if (unlikely(se == pse))
4423 		return;
4424 
4425 	/*
4426 	 * This is possible from callers such as move_task(), in which we
4427 	 * unconditionally check_prempt_curr() after an enqueue (which may have
4428 	 * lead to a throttle).  This both saves work and prevents false
4429 	 * next-buddy nomination below.
4430 	 */
4431 	if (unlikely(throttled_hierarchy(cfs_rq_of(pse))))
4432 		return;
4433 
4434 	if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {
4435 		set_next_buddy(pse);
4436 		next_buddy_marked = 1;
4437 	}
4438 
4439 	/*
4440 	 * We can come here with TIF_NEED_RESCHED already set from new task
4441 	 * wake up path.
4442 	 *
4443 	 * Note: this also catches the edge-case of curr being in a throttled
4444 	 * group (e.g. via set_curr_task), since update_curr() (in the
4445 	 * enqueue of curr) will have resulted in resched being set.  This
4446 	 * prevents us from potentially nominating it as a false LAST_BUDDY
4447 	 * below.
4448 	 */
4449 	if (test_tsk_need_resched(curr))
4450 		return;
4451 
4452 	/* Idle tasks are by definition preempted by non-idle tasks. */
4453 	if (unlikely(curr->policy == SCHED_IDLE) &&
4454 	    likely(p->policy != SCHED_IDLE))
4455 		goto preempt;
4456 
4457 	/*
4458 	 * Batch and idle tasks do not preempt non-idle tasks (their preemption
4459 	 * is driven by the tick):
4460 	 */
4461 	if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
4462 		return;
4463 
4464 	find_matching_se(&se, &pse);
4465 	update_curr(cfs_rq_of(se));
4466 	BUG_ON(!pse);
4467 	if (wakeup_preempt_entity(se, pse) == 1) {
4468 		/*
4469 		 * Bias pick_next to pick the sched entity that is
4470 		 * triggering this preemption.
4471 		 */
4472 		if (!next_buddy_marked)
4473 			set_next_buddy(pse);
4474 		goto preempt;
4475 	}
4476 
4477 	return;
4478 
4479 preempt:
4480 	resched_task(curr);
4481 	/*
4482 	 * Only set the backward buddy when the current task is still
4483 	 * on the rq. This can happen when a wakeup gets interleaved
4484 	 * with schedule on the ->pre_schedule() or idle_balance()
4485 	 * point, either of which can * drop the rq lock.
4486 	 *
4487 	 * Also, during early boot the idle thread is in the fair class,
4488 	 * for obvious reasons its a bad idea to schedule back to it.
4489 	 */
4490 	if (unlikely(!se->on_rq || curr == rq->idle))
4491 		return;
4492 
4493 	if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
4494 		set_last_buddy(se);
4495 }
4496 
4497 static struct task_struct *pick_next_task_fair(struct rq *rq)
4498 {
4499 	struct task_struct *p;
4500 	struct cfs_rq *cfs_rq = &rq->cfs;
4501 	struct sched_entity *se;
4502 
4503 	if (!cfs_rq->nr_running)
4504 		return NULL;
4505 
4506 	do {
4507 		se = pick_next_entity(cfs_rq);
4508 		set_next_entity(cfs_rq, se);
4509 		cfs_rq = group_cfs_rq(se);
4510 	} while (cfs_rq);
4511 
4512 	p = task_of(se);
4513 	if (hrtick_enabled(rq))
4514 		hrtick_start_fair(rq, p);
4515 
4516 	return p;
4517 }
4518 
4519 /*
4520  * Account for a descheduled task:
4521  */
4522 static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
4523 {
4524 	struct sched_entity *se = &prev->se;
4525 	struct cfs_rq *cfs_rq;
4526 
4527 	for_each_sched_entity(se) {
4528 		cfs_rq = cfs_rq_of(se);
4529 		put_prev_entity(cfs_rq, se);
4530 	}
4531 }
4532 
4533 /*
4534  * sched_yield() is very simple
4535  *
4536  * The magic of dealing with the ->skip buddy is in pick_next_entity.
4537  */
4538 static void yield_task_fair(struct rq *rq)
4539 {
4540 	struct task_struct *curr = rq->curr;
4541 	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
4542 	struct sched_entity *se = &curr->se;
4543 
4544 	/*
4545 	 * Are we the only task in the tree?
4546 	 */
4547 	if (unlikely(rq->nr_running == 1))
4548 		return;
4549 
4550 	clear_buddies(cfs_rq, se);
4551 
4552 	if (curr->policy != SCHED_BATCH) {
4553 		update_rq_clock(rq);
4554 		/*
4555 		 * Update run-time statistics of the 'current'.
4556 		 */
4557 		update_curr(cfs_rq);
4558 		/*
4559 		 * Tell update_rq_clock() that we've just updated,
4560 		 * so we don't do microscopic update in schedule()
4561 		 * and double the fastpath cost.
4562 		 */
4563 		 rq->skip_clock_update = 1;
4564 	}
4565 
4566 	set_skip_buddy(se);
4567 }
4568 
4569 static bool yield_to_task_fair(struct rq *rq, struct task_struct *p, bool preempt)
4570 {
4571 	struct sched_entity *se = &p->se;
4572 
4573 	/* throttled hierarchies are not runnable */
4574 	if (!se->on_rq || throttled_hierarchy(cfs_rq_of(se)))
4575 		return false;
4576 
4577 	/* Tell the scheduler that we'd really like pse to run next. */
4578 	set_next_buddy(se);
4579 
4580 	yield_task_fair(rq);
4581 
4582 	return true;
4583 }
4584 
4585 #ifdef CONFIG_SMP
4586 /**************************************************
4587  * Fair scheduling class load-balancing methods.
4588  *
4589  * BASICS
4590  *
4591  * The purpose of load-balancing is to achieve the same basic fairness the
4592  * per-cpu scheduler provides, namely provide a proportional amount of compute
4593  * time to each task. This is expressed in the following equation:
4594  *
4595  *   W_i,n/P_i == W_j,n/P_j for all i,j                               (1)
4596  *
4597  * Where W_i,n is the n-th weight average for cpu i. The instantaneous weight
4598  * W_i,0 is defined as:
4599  *
4600  *   W_i,0 = \Sum_j w_i,j                                             (2)
4601  *
4602  * Where w_i,j is the weight of the j-th runnable task on cpu i. This weight
4603  * is derived from the nice value as per prio_to_weight[].
4604  *
4605  * The weight average is an exponential decay average of the instantaneous
4606  * weight:
4607  *
4608  *   W'_i,n = (2^n - 1) / 2^n * W_i,n + 1 / 2^n * W_i,0               (3)
4609  *
4610  * P_i is the cpu power (or compute capacity) of cpu i, typically it is the
4611  * fraction of 'recent' time available for SCHED_OTHER task execution. But it
4612  * can also include other factors [XXX].
4613  *
4614  * To achieve this balance we define a measure of imbalance which follows
4615  * directly from (1):
4616  *
4617  *   imb_i,j = max{ avg(W/P), W_i/P_i } - min{ avg(W/P), W_j/P_j }    (4)
4618  *
4619  * We them move tasks around to minimize the imbalance. In the continuous
4620  * function space it is obvious this converges, in the discrete case we get
4621  * a few fun cases generally called infeasible weight scenarios.
4622  *
4623  * [XXX expand on:
4624  *     - infeasible weights;
4625  *     - local vs global optima in the discrete case. ]
4626  *
4627  *
4628  * SCHED DOMAINS
4629  *
4630  * In order to solve the imbalance equation (4), and avoid the obvious O(n^2)
4631  * for all i,j solution, we create a tree of cpus that follows the hardware
4632  * topology where each level pairs two lower groups (or better). This results
4633  * in O(log n) layers. Furthermore we reduce the number of cpus going up the
4634  * tree to only the first of the previous level and we decrease the frequency
4635  * of load-balance at each level inv. proportional to the number of cpus in
4636  * the groups.
4637  *
4638  * This yields:
4639  *
4640  *     log_2 n     1     n
4641  *   \Sum       { --- * --- * 2^i } = O(n)                            (5)
4642  *     i = 0      2^i   2^i
4643  *                               `- size of each group
4644  *         |         |     `- number of cpus doing load-balance
4645  *         |         `- freq
4646  *         `- sum over all levels
4647  *
4648  * Coupled with a limit on how many tasks we can migrate every balance pass,
4649  * this makes (5) the runtime complexity of the balancer.
4650  *
4651  * An important property here is that each CPU is still (indirectly) connected
4652  * to every other cpu in at most O(log n) steps:
4653  *
4654  * The adjacency matrix of the resulting graph is given by:
4655  *
4656  *             log_2 n
4657  *   A_i,j = \Union     (i % 2^k == 0) && i / 2^(k+1) == j / 2^(k+1)  (6)
4658  *             k = 0
4659  *
4660  * And you'll find that:
4661  *
4662  *   A^(log_2 n)_i,j != 0  for all i,j                                (7)
4663  *
4664  * Showing there's indeed a path between every cpu in at most O(log n) steps.
4665  * The task movement gives a factor of O(m), giving a convergence complexity
4666  * of:
4667  *
4668  *   O(nm log n),  n := nr_cpus, m := nr_tasks                        (8)
4669  *
4670  *
4671  * WORK CONSERVING
4672  *
4673  * In order to avoid CPUs going idle while there's still work to do, new idle
4674  * balancing is more aggressive and has the newly idle cpu iterate up the domain
4675  * tree itself instead of relying on other CPUs to bring it work.
4676  *
4677  * This adds some complexity to both (5) and (8) but it reduces the total idle
4678  * time.
4679  *
4680  * [XXX more?]
4681  *
4682  *
4683  * CGROUPS
4684  *
4685  * Cgroups make a horror show out of (2), instead of a simple sum we get:
4686  *
4687  *                                s_k,i
4688  *   W_i,0 = \Sum_j \Prod_k w_k * -----                               (9)
4689  *                                 S_k
4690  *
4691  * Where
4692  *
4693  *   s_k,i = \Sum_j w_i,j,k  and  S_k = \Sum_i s_k,i                 (10)
4694  *
4695  * w_i,j,k is the weight of the j-th runnable task in the k-th cgroup on cpu i.
4696  *
4697  * The big problem is S_k, its a global sum needed to compute a local (W_i)
4698  * property.
4699  *
4700  * [XXX write more on how we solve this.. _after_ merging pjt's patches that
4701  *      rewrite all of this once again.]
4702  */
4703 
4704 static unsigned long __read_mostly max_load_balance_interval = HZ/10;
4705 
4706 enum fbq_type { regular, remote, all };
4707 
4708 #define LBF_ALL_PINNED	0x01
4709 #define LBF_NEED_BREAK	0x02
4710 #define LBF_DST_PINNED  0x04
4711 #define LBF_SOME_PINNED	0x08
4712 
4713 struct lb_env {
4714 	struct sched_domain	*sd;
4715 
4716 	struct rq		*src_rq;
4717 	int			src_cpu;
4718 
4719 	int			dst_cpu;
4720 	struct rq		*dst_rq;
4721 
4722 	struct cpumask		*dst_grpmask;
4723 	int			new_dst_cpu;
4724 	enum cpu_idle_type	idle;
4725 	long			imbalance;
4726 	/* The set of CPUs under consideration for load-balancing */
4727 	struct cpumask		*cpus;
4728 
4729 	unsigned int		flags;
4730 
4731 	unsigned int		loop;
4732 	unsigned int		loop_break;
4733 	unsigned int		loop_max;
4734 
4735 	enum fbq_type		fbq_type;
4736 };
4737 
4738 /*
4739  * move_task - move a task from one runqueue to another runqueue.
4740  * Both runqueues must be locked.
4741  */
4742 static void move_task(struct task_struct *p, struct lb_env *env)
4743 {
4744 	deactivate_task(env->src_rq, p, 0);
4745 	set_task_cpu(p, env->dst_cpu);
4746 	activate_task(env->dst_rq, p, 0);
4747 	check_preempt_curr(env->dst_rq, p, 0);
4748 }
4749 
4750 /*
4751  * Is this task likely cache-hot:
4752  */
4753 static int
4754 task_hot(struct task_struct *p, u64 now, struct sched_domain *sd)
4755 {
4756 	s64 delta;
4757 
4758 	if (p->sched_class != &fair_sched_class)
4759 		return 0;
4760 
4761 	if (unlikely(p->policy == SCHED_IDLE))
4762 		return 0;
4763 
4764 	/*
4765 	 * Buddy candidates are cache hot:
4766 	 */
4767 	if (sched_feat(CACHE_HOT_BUDDY) && this_rq()->nr_running &&
4768 			(&p->se == cfs_rq_of(&p->se)->next ||
4769 			 &p->se == cfs_rq_of(&p->se)->last))
4770 		return 1;
4771 
4772 	if (sysctl_sched_migration_cost == -1)
4773 		return 1;
4774 	if (sysctl_sched_migration_cost == 0)
4775 		return 0;
4776 
4777 	delta = now - p->se.exec_start;
4778 
4779 	return delta < (s64)sysctl_sched_migration_cost;
4780 }
4781 
4782 #ifdef CONFIG_NUMA_BALANCING
4783 /* Returns true if the destination node has incurred more faults */
4784 static bool migrate_improves_locality(struct task_struct *p, struct lb_env *env)
4785 {
4786 	int src_nid, dst_nid;
4787 
4788 	if (!sched_feat(NUMA_FAVOUR_HIGHER) || !p->numa_faults ||
4789 	    !(env->sd->flags & SD_NUMA)) {
4790 		return false;
4791 	}
4792 
4793 	src_nid = cpu_to_node(env->src_cpu);
4794 	dst_nid = cpu_to_node(env->dst_cpu);
4795 
4796 	if (src_nid == dst_nid)
4797 		return false;
4798 
4799 	/* Always encourage migration to the preferred node. */
4800 	if (dst_nid == p->numa_preferred_nid)
4801 		return true;
4802 
4803 	/* If both task and group weight improve, this move is a winner. */
4804 	if (task_weight(p, dst_nid) > task_weight(p, src_nid) &&
4805 	    group_weight(p, dst_nid) > group_weight(p, src_nid))
4806 		return true;
4807 
4808 	return false;
4809 }
4810 
4811 
4812 static bool migrate_degrades_locality(struct task_struct *p, struct lb_env *env)
4813 {
4814 	int src_nid, dst_nid;
4815 
4816 	if (!sched_feat(NUMA) || !sched_feat(NUMA_RESIST_LOWER))
4817 		return false;
4818 
4819 	if (!p->numa_faults || !(env->sd->flags & SD_NUMA))
4820 		return false;
4821 
4822 	src_nid = cpu_to_node(env->src_cpu);
4823 	dst_nid = cpu_to_node(env->dst_cpu);
4824 
4825 	if (src_nid == dst_nid)
4826 		return false;
4827 
4828 	/* Migrating away from the preferred node is always bad. */
4829 	if (src_nid == p->numa_preferred_nid)
4830 		return true;
4831 
4832 	/* If either task or group weight get worse, don't do it. */
4833 	if (task_weight(p, dst_nid) < task_weight(p, src_nid) ||
4834 	    group_weight(p, dst_nid) < group_weight(p, src_nid))
4835 		return true;
4836 
4837 	return false;
4838 }
4839 
4840 #else
4841 static inline bool migrate_improves_locality(struct task_struct *p,
4842 					     struct lb_env *env)
4843 {
4844 	return false;
4845 }
4846 
4847 static inline bool migrate_degrades_locality(struct task_struct *p,
4848 					     struct lb_env *env)
4849 {
4850 	return false;
4851 }
4852 #endif
4853 
4854 /*
4855  * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
4856  */
4857 static
4858 int can_migrate_task(struct task_struct *p, struct lb_env *env)
4859 {
4860 	int tsk_cache_hot = 0;
4861 	/*
4862 	 * We do not migrate tasks that are:
4863 	 * 1) throttled_lb_pair, or
4864 	 * 2) cannot be migrated to this CPU due to cpus_allowed, or
4865 	 * 3) running (obviously), or
4866 	 * 4) are cache-hot on their current CPU.
4867 	 */
4868 	if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
4869 		return 0;
4870 
4871 	if (!cpumask_test_cpu(env->dst_cpu, tsk_cpus_allowed(p))) {
4872 		int cpu;
4873 
4874 		schedstat_inc(p, se.statistics.nr_failed_migrations_affine);
4875 
4876 		env->flags |= LBF_SOME_PINNED;
4877 
4878 		/*
4879 		 * Remember if this task can be migrated to any other cpu in
4880 		 * our sched_group. We may want to revisit it if we couldn't
4881 		 * meet load balance goals by pulling other tasks on src_cpu.
4882 		 *
4883 		 * Also avoid computing new_dst_cpu if we have already computed
4884 		 * one in current iteration.
4885 		 */
4886 		if (!env->dst_grpmask || (env->flags & LBF_DST_PINNED))
4887 			return 0;
4888 
4889 		/* Prevent to re-select dst_cpu via env's cpus */
4890 		for_each_cpu_and(cpu, env->dst_grpmask, env->cpus) {
4891 			if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) {
4892 				env->flags |= LBF_DST_PINNED;
4893 				env->new_dst_cpu = cpu;
4894 				break;
4895 			}
4896 		}
4897 
4898 		return 0;
4899 	}
4900 
4901 	/* Record that we found atleast one task that could run on dst_cpu */
4902 	env->flags &= ~LBF_ALL_PINNED;
4903 
4904 	if (task_running(env->src_rq, p)) {
4905 		schedstat_inc(p, se.statistics.nr_failed_migrations_running);
4906 		return 0;
4907 	}
4908 
4909 	/*
4910 	 * Aggressive migration if:
4911 	 * 1) destination numa is preferred
4912 	 * 2) task is cache cold, or
4913 	 * 3) too many balance attempts have failed.
4914 	 */
4915 	tsk_cache_hot = task_hot(p, rq_clock_task(env->src_rq), env->sd);
4916 	if (!tsk_cache_hot)
4917 		tsk_cache_hot = migrate_degrades_locality(p, env);
4918 
4919 	if (migrate_improves_locality(p, env)) {
4920 #ifdef CONFIG_SCHEDSTATS
4921 		if (tsk_cache_hot) {
4922 			schedstat_inc(env->sd, lb_hot_gained[env->idle]);
4923 			schedstat_inc(p, se.statistics.nr_forced_migrations);
4924 		}
4925 #endif
4926 		return 1;
4927 	}
4928 
4929 	if (!tsk_cache_hot ||
4930 		env->sd->nr_balance_failed > env->sd->cache_nice_tries) {
4931 
4932 		if (tsk_cache_hot) {
4933 			schedstat_inc(env->sd, lb_hot_gained[env->idle]);
4934 			schedstat_inc(p, se.statistics.nr_forced_migrations);
4935 		}
4936 
4937 		return 1;
4938 	}
4939 
4940 	schedstat_inc(p, se.statistics.nr_failed_migrations_hot);
4941 	return 0;
4942 }
4943 
4944 /*
4945  * move_one_task tries to move exactly one task from busiest to this_rq, as
4946  * part of active balancing operations within "domain".
4947  * Returns 1 if successful and 0 otherwise.
4948  *
4949  * Called with both runqueues locked.
4950  */
4951 static int move_one_task(struct lb_env *env)
4952 {
4953 	struct task_struct *p, *n;
4954 
4955 	list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) {
4956 		if (!can_migrate_task(p, env))
4957 			continue;
4958 
4959 		move_task(p, env);
4960 		/*
4961 		 * Right now, this is only the second place move_task()
4962 		 * is called, so we can safely collect move_task()
4963 		 * stats here rather than inside move_task().
4964 		 */
4965 		schedstat_inc(env->sd, lb_gained[env->idle]);
4966 		return 1;
4967 	}
4968 	return 0;
4969 }
4970 
4971 static const unsigned int sched_nr_migrate_break = 32;
4972 
4973 /*
4974  * move_tasks tries to move up to imbalance weighted load from busiest to
4975  * this_rq, as part of a balancing operation within domain "sd".
4976  * Returns 1 if successful and 0 otherwise.
4977  *
4978  * Called with both runqueues locked.
4979  */
4980 static int move_tasks(struct lb_env *env)
4981 {
4982 	struct list_head *tasks = &env->src_rq->cfs_tasks;
4983 	struct task_struct *p;
4984 	unsigned long load;
4985 	int pulled = 0;
4986 
4987 	if (env->imbalance <= 0)
4988 		return 0;
4989 
4990 	while (!list_empty(tasks)) {
4991 		p = list_first_entry(tasks, struct task_struct, se.group_node);
4992 
4993 		env->loop++;
4994 		/* We've more or less seen every task there is, call it quits */
4995 		if (env->loop > env->loop_max)
4996 			break;
4997 
4998 		/* take a breather every nr_migrate tasks */
4999 		if (env->loop > env->loop_break) {
5000 			env->loop_break += sched_nr_migrate_break;
5001 			env->flags |= LBF_NEED_BREAK;
5002 			break;
5003 		}
5004 
5005 		if (!can_migrate_task(p, env))
5006 			goto next;
5007 
5008 		load = task_h_load(p);
5009 
5010 		if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
5011 			goto next;
5012 
5013 		if ((load / 2) > env->imbalance)
5014 			goto next;
5015 
5016 		move_task(p, env);
5017 		pulled++;
5018 		env->imbalance -= load;
5019 
5020 #ifdef CONFIG_PREEMPT
5021 		/*
5022 		 * NEWIDLE balancing is a source of latency, so preemptible
5023 		 * kernels will stop after the first task is pulled to minimize
5024 		 * the critical section.
5025 		 */
5026 		if (env->idle == CPU_NEWLY_IDLE)
5027 			break;
5028 #endif
5029 
5030 		/*
5031 		 * We only want to steal up to the prescribed amount of
5032 		 * weighted load.
5033 		 */
5034 		if (env->imbalance <= 0)
5035 			break;
5036 
5037 		continue;
5038 next:
5039 		list_move_tail(&p->se.group_node, tasks);
5040 	}
5041 
5042 	/*
5043 	 * Right now, this is one of only two places move_task() is called,
5044 	 * so we can safely collect move_task() stats here rather than
5045 	 * inside move_task().
5046 	 */
5047 	schedstat_add(env->sd, lb_gained[env->idle], pulled);
5048 
5049 	return pulled;
5050 }
5051 
5052 #ifdef CONFIG_FAIR_GROUP_SCHED
5053 /*
5054  * update tg->load_weight by folding this cpu's load_avg
5055  */
5056 static void __update_blocked_averages_cpu(struct task_group *tg, int cpu)
5057 {
5058 	struct sched_entity *se = tg->se[cpu];
5059 	struct cfs_rq *cfs_rq = tg->cfs_rq[cpu];
5060 
5061 	/* throttled entities do not contribute to load */
5062 	if (throttled_hierarchy(cfs_rq))
5063 		return;
5064 
5065 	update_cfs_rq_blocked_load(cfs_rq, 1);
5066 
5067 	if (se) {
5068 		update_entity_load_avg(se, 1);
5069 		/*
5070 		 * We pivot on our runnable average having decayed to zero for
5071 		 * list removal.  This generally implies that all our children
5072 		 * have also been removed (modulo rounding error or bandwidth
5073 		 * control); however, such cases are rare and we can fix these
5074 		 * at enqueue.
5075 		 *
5076 		 * TODO: fix up out-of-order children on enqueue.
5077 		 */
5078 		if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running)
5079 			list_del_leaf_cfs_rq(cfs_rq);
5080 	} else {
5081 		struct rq *rq = rq_of(cfs_rq);
5082 		update_rq_runnable_avg(rq, rq->nr_running);
5083 	}
5084 }
5085 
5086 static void update_blocked_averages(int cpu)
5087 {
5088 	struct rq *rq = cpu_rq(cpu);
5089 	struct cfs_rq *cfs_rq;
5090 	unsigned long flags;
5091 
5092 	raw_spin_lock_irqsave(&rq->lock, flags);
5093 	update_rq_clock(rq);
5094 	/*
5095 	 * Iterates the task_group tree in a bottom up fashion, see
5096 	 * list_add_leaf_cfs_rq() for details.
5097 	 */
5098 	for_each_leaf_cfs_rq(rq, cfs_rq) {
5099 		/*
5100 		 * Note: We may want to consider periodically releasing
5101 		 * rq->lock about these updates so that creating many task
5102 		 * groups does not result in continually extending hold time.
5103 		 */
5104 		__update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
5105 	}
5106 
5107 	raw_spin_unlock_irqrestore(&rq->lock, flags);
5108 }
5109 
5110 /*
5111  * Compute the hierarchical load factor for cfs_rq and all its ascendants.
5112  * This needs to be done in a top-down fashion because the load of a child
5113  * group is a fraction of its parents load.
5114  */
5115 static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
5116 {
5117 	struct rq *rq = rq_of(cfs_rq);
5118 	struct sched_entity *se = cfs_rq->tg->se[cpu_of(rq)];
5119 	unsigned long now = jiffies;
5120 	unsigned long load;
5121 
5122 	if (cfs_rq->last_h_load_update == now)
5123 		return;
5124 
5125 	cfs_rq->h_load_next = NULL;
5126 	for_each_sched_entity(se) {
5127 		cfs_rq = cfs_rq_of(se);
5128 		cfs_rq->h_load_next = se;
5129 		if (cfs_rq->last_h_load_update == now)
5130 			break;
5131 	}
5132 
5133 	if (!se) {
5134 		cfs_rq->h_load = cfs_rq->runnable_load_avg;
5135 		cfs_rq->last_h_load_update = now;
5136 	}
5137 
5138 	while ((se = cfs_rq->h_load_next) != NULL) {
5139 		load = cfs_rq->h_load;
5140 		load = div64_ul(load * se->avg.load_avg_contrib,
5141 				cfs_rq->runnable_load_avg + 1);
5142 		cfs_rq = group_cfs_rq(se);
5143 		cfs_rq->h_load = load;
5144 		cfs_rq->last_h_load_update = now;
5145 	}
5146 }
5147 
5148 static unsigned long task_h_load(struct task_struct *p)
5149 {
5150 	struct cfs_rq *cfs_rq = task_cfs_rq(p);
5151 
5152 	update_cfs_rq_h_load(cfs_rq);
5153 	return div64_ul(p->se.avg.load_avg_contrib * cfs_rq->h_load,
5154 			cfs_rq->runnable_load_avg + 1);
5155 }
5156 #else
5157 static inline void update_blocked_averages(int cpu)
5158 {
5159 }
5160 
5161 static unsigned long task_h_load(struct task_struct *p)
5162 {
5163 	return p->se.avg.load_avg_contrib;
5164 }
5165 #endif
5166 
5167 /********** Helpers for find_busiest_group ************************/
5168 /*
5169  * sg_lb_stats - stats of a sched_group required for load_balancing
5170  */
5171 struct sg_lb_stats {
5172 	unsigned long avg_load; /*Avg load across the CPUs of the group */
5173 	unsigned long group_load; /* Total load over the CPUs of the group */
5174 	unsigned long sum_weighted_load; /* Weighted load of group's tasks */
5175 	unsigned long load_per_task;
5176 	unsigned long group_power;
5177 	unsigned int sum_nr_running; /* Nr tasks running in the group */
5178 	unsigned int group_capacity;
5179 	unsigned int idle_cpus;
5180 	unsigned int group_weight;
5181 	int group_imb; /* Is there an imbalance in the group ? */
5182 	int group_has_capacity; /* Is there extra capacity in the group? */
5183 #ifdef CONFIG_NUMA_BALANCING
5184 	unsigned int nr_numa_running;
5185 	unsigned int nr_preferred_running;
5186 #endif
5187 };
5188 
5189 /*
5190  * sd_lb_stats - Structure to store the statistics of a sched_domain
5191  *		 during load balancing.
5192  */
5193 struct sd_lb_stats {
5194 	struct sched_group *busiest;	/* Busiest group in this sd */
5195 	struct sched_group *local;	/* Local group in this sd */
5196 	unsigned long total_load;	/* Total load of all groups in sd */
5197 	unsigned long total_pwr;	/* Total power of all groups in sd */
5198 	unsigned long avg_load;	/* Average load across all groups in sd */
5199 
5200 	struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */
5201 	struct sg_lb_stats local_stat;	/* Statistics of the local group */
5202 };
5203 
5204 static inline void init_sd_lb_stats(struct sd_lb_stats *sds)
5205 {
5206 	/*
5207 	 * Skimp on the clearing to avoid duplicate work. We can avoid clearing
5208 	 * local_stat because update_sg_lb_stats() does a full clear/assignment.
5209 	 * We must however clear busiest_stat::avg_load because
5210 	 * update_sd_pick_busiest() reads this before assignment.
5211 	 */
5212 	*sds = (struct sd_lb_stats){
5213 		.busiest = NULL,
5214 		.local = NULL,
5215 		.total_load = 0UL,
5216 		.total_pwr = 0UL,
5217 		.busiest_stat = {
5218 			.avg_load = 0UL,
5219 		},
5220 	};
5221 }
5222 
5223 /**
5224  * get_sd_load_idx - Obtain the load index for a given sched domain.
5225  * @sd: The sched_domain whose load_idx is to be obtained.
5226  * @idle: The idle status of the CPU for whose sd load_idx is obtained.
5227  *
5228  * Return: The load index.
5229  */
5230 static inline int get_sd_load_idx(struct sched_domain *sd,
5231 					enum cpu_idle_type idle)
5232 {
5233 	int load_idx;
5234 
5235 	switch (idle) {
5236 	case CPU_NOT_IDLE:
5237 		load_idx = sd->busy_idx;
5238 		break;
5239 
5240 	case CPU_NEWLY_IDLE:
5241 		load_idx = sd->newidle_idx;
5242 		break;
5243 	default:
5244 		load_idx = sd->idle_idx;
5245 		break;
5246 	}
5247 
5248 	return load_idx;
5249 }
5250 
5251 static unsigned long default_scale_freq_power(struct sched_domain *sd, int cpu)
5252 {
5253 	return SCHED_POWER_SCALE;
5254 }
5255 
5256 unsigned long __weak arch_scale_freq_power(struct sched_domain *sd, int cpu)
5257 {
5258 	return default_scale_freq_power(sd, cpu);
5259 }
5260 
5261 static unsigned long default_scale_smt_power(struct sched_domain *sd, int cpu)
5262 {
5263 	unsigned long weight = sd->span_weight;
5264 	unsigned long smt_gain = sd->smt_gain;
5265 
5266 	smt_gain /= weight;
5267 
5268 	return smt_gain;
5269 }
5270 
5271 unsigned long __weak arch_scale_smt_power(struct sched_domain *sd, int cpu)
5272 {
5273 	return default_scale_smt_power(sd, cpu);
5274 }
5275 
5276 static unsigned long scale_rt_power(int cpu)
5277 {
5278 	struct rq *rq = cpu_rq(cpu);
5279 	u64 total, available, age_stamp, avg;
5280 
5281 	/*
5282 	 * Since we're reading these variables without serialization make sure
5283 	 * we read them once before doing sanity checks on them.
5284 	 */
5285 	age_stamp = ACCESS_ONCE(rq->age_stamp);
5286 	avg = ACCESS_ONCE(rq->rt_avg);
5287 
5288 	total = sched_avg_period() + (rq_clock(rq) - age_stamp);
5289 
5290 	if (unlikely(total < avg)) {
5291 		/* Ensures that power won't end up being negative */
5292 		available = 0;
5293 	} else {
5294 		available = total - avg;
5295 	}
5296 
5297 	if (unlikely((s64)total < SCHED_POWER_SCALE))
5298 		total = SCHED_POWER_SCALE;
5299 
5300 	total >>= SCHED_POWER_SHIFT;
5301 
5302 	return div_u64(available, total);
5303 }
5304 
5305 static void update_cpu_power(struct sched_domain *sd, int cpu)
5306 {
5307 	unsigned long weight = sd->span_weight;
5308 	unsigned long power = SCHED_POWER_SCALE;
5309 	struct sched_group *sdg = sd->groups;
5310 
5311 	if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) {
5312 		if (sched_feat(ARCH_POWER))
5313 			power *= arch_scale_smt_power(sd, cpu);
5314 		else
5315 			power *= default_scale_smt_power(sd, cpu);
5316 
5317 		power >>= SCHED_POWER_SHIFT;
5318 	}
5319 
5320 	sdg->sgp->power_orig = power;
5321 
5322 	if (sched_feat(ARCH_POWER))
5323 		power *= arch_scale_freq_power(sd, cpu);
5324 	else
5325 		power *= default_scale_freq_power(sd, cpu);
5326 
5327 	power >>= SCHED_POWER_SHIFT;
5328 
5329 	power *= scale_rt_power(cpu);
5330 	power >>= SCHED_POWER_SHIFT;
5331 
5332 	if (!power)
5333 		power = 1;
5334 
5335 	cpu_rq(cpu)->cpu_power = power;
5336 	sdg->sgp->power = power;
5337 }
5338 
5339 void update_group_power(struct sched_domain *sd, int cpu)
5340 {
5341 	struct sched_domain *child = sd->child;
5342 	struct sched_group *group, *sdg = sd->groups;
5343 	unsigned long power, power_orig;
5344 	unsigned long interval;
5345 
5346 	interval = msecs_to_jiffies(sd->balance_interval);
5347 	interval = clamp(interval, 1UL, max_load_balance_interval);
5348 	sdg->sgp->next_update = jiffies + interval;
5349 
5350 	if (!child) {
5351 		update_cpu_power(sd, cpu);
5352 		return;
5353 	}
5354 
5355 	power_orig = power = 0;
5356 
5357 	if (child->flags & SD_OVERLAP) {
5358 		/*
5359 		 * SD_OVERLAP domains cannot assume that child groups
5360 		 * span the current group.
5361 		 */
5362 
5363 		for_each_cpu(cpu, sched_group_cpus(sdg)) {
5364 			struct sched_group_power *sgp;
5365 			struct rq *rq = cpu_rq(cpu);
5366 
5367 			/*
5368 			 * build_sched_domains() -> init_sched_groups_power()
5369 			 * gets here before we've attached the domains to the
5370 			 * runqueues.
5371 			 *
5372 			 * Use power_of(), which is set irrespective of domains
5373 			 * in update_cpu_power().
5374 			 *
5375 			 * This avoids power/power_orig from being 0 and
5376 			 * causing divide-by-zero issues on boot.
5377 			 *
5378 			 * Runtime updates will correct power_orig.
5379 			 */
5380 			if (unlikely(!rq->sd)) {
5381 				power_orig += power_of(cpu);
5382 				power += power_of(cpu);
5383 				continue;
5384 			}
5385 
5386 			sgp = rq->sd->groups->sgp;
5387 			power_orig += sgp->power_orig;
5388 			power += sgp->power;
5389 		}
5390 	} else  {
5391 		/*
5392 		 * !SD_OVERLAP domains can assume that child groups
5393 		 * span the current group.
5394 		 */
5395 
5396 		group = child->groups;
5397 		do {
5398 			power_orig += group->sgp->power_orig;
5399 			power += group->sgp->power;
5400 			group = group->next;
5401 		} while (group != child->groups);
5402 	}
5403 
5404 	sdg->sgp->power_orig = power_orig;
5405 	sdg->sgp->power = power;
5406 }
5407 
5408 /*
5409  * Try and fix up capacity for tiny siblings, this is needed when
5410  * things like SD_ASYM_PACKING need f_b_g to select another sibling
5411  * which on its own isn't powerful enough.
5412  *
5413  * See update_sd_pick_busiest() and check_asym_packing().
5414  */
5415 static inline int
5416 fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
5417 {
5418 	/*
5419 	 * Only siblings can have significantly less than SCHED_POWER_SCALE
5420 	 */
5421 	if (!(sd->flags & SD_SHARE_CPUPOWER))
5422 		return 0;
5423 
5424 	/*
5425 	 * If ~90% of the cpu_power is still there, we're good.
5426 	 */
5427 	if (group->sgp->power * 32 > group->sgp->power_orig * 29)
5428 		return 1;
5429 
5430 	return 0;
5431 }
5432 
5433 /*
5434  * Group imbalance indicates (and tries to solve) the problem where balancing
5435  * groups is inadequate due to tsk_cpus_allowed() constraints.
5436  *
5437  * Imagine a situation of two groups of 4 cpus each and 4 tasks each with a
5438  * cpumask covering 1 cpu of the first group and 3 cpus of the second group.
5439  * Something like:
5440  *
5441  * 	{ 0 1 2 3 } { 4 5 6 7 }
5442  * 	        *     * * *
5443  *
5444  * If we were to balance group-wise we'd place two tasks in the first group and
5445  * two tasks in the second group. Clearly this is undesired as it will overload
5446  * cpu 3 and leave one of the cpus in the second group unused.
5447  *
5448  * The current solution to this issue is detecting the skew in the first group
5449  * by noticing the lower domain failed to reach balance and had difficulty
5450  * moving tasks due to affinity constraints.
5451  *
5452  * When this is so detected; this group becomes a candidate for busiest; see
5453  * update_sd_pick_busiest(). And calculate_imbalance() and
5454  * find_busiest_group() avoid some of the usual balance conditions to allow it
5455  * to create an effective group imbalance.
5456  *
5457  * This is a somewhat tricky proposition since the next run might not find the
5458  * group imbalance and decide the groups need to be balanced again. A most
5459  * subtle and fragile situation.
5460  */
5461 
5462 static inline int sg_imbalanced(struct sched_group *group)
5463 {
5464 	return group->sgp->imbalance;
5465 }
5466 
5467 /*
5468  * Compute the group capacity.
5469  *
5470  * Avoid the issue where N*frac(smt_power) >= 1 creates 'phantom' cores by
5471  * first dividing out the smt factor and computing the actual number of cores
5472  * and limit power unit capacity with that.
5473  */
5474 static inline int sg_capacity(struct lb_env *env, struct sched_group *group)
5475 {
5476 	unsigned int capacity, smt, cpus;
5477 	unsigned int power, power_orig;
5478 
5479 	power = group->sgp->power;
5480 	power_orig = group->sgp->power_orig;
5481 	cpus = group->group_weight;
5482 
5483 	/* smt := ceil(cpus / power), assumes: 1 < smt_power < 2 */
5484 	smt = DIV_ROUND_UP(SCHED_POWER_SCALE * cpus, power_orig);
5485 	capacity = cpus / smt; /* cores */
5486 
5487 	capacity = min_t(unsigned, capacity, DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE));
5488 	if (!capacity)
5489 		capacity = fix_small_capacity(env->sd, group);
5490 
5491 	return capacity;
5492 }
5493 
5494 /**
5495  * update_sg_lb_stats - Update sched_group's statistics for load balancing.
5496  * @env: The load balancing environment.
5497  * @group: sched_group whose statistics are to be updated.
5498  * @load_idx: Load index of sched_domain of this_cpu for load calc.
5499  * @local_group: Does group contain this_cpu.
5500  * @sgs: variable to hold the statistics for this group.
5501  */
5502 static inline void update_sg_lb_stats(struct lb_env *env,
5503 			struct sched_group *group, int load_idx,
5504 			int local_group, struct sg_lb_stats *sgs)
5505 {
5506 	unsigned long load;
5507 	int i;
5508 
5509 	memset(sgs, 0, sizeof(*sgs));
5510 
5511 	for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
5512 		struct rq *rq = cpu_rq(i);
5513 
5514 		/* Bias balancing toward cpus of our domain */
5515 		if (local_group)
5516 			load = target_load(i, load_idx);
5517 		else
5518 			load = source_load(i, load_idx);
5519 
5520 		sgs->group_load += load;
5521 		sgs->sum_nr_running += rq->nr_running;
5522 #ifdef CONFIG_NUMA_BALANCING
5523 		sgs->nr_numa_running += rq->nr_numa_running;
5524 		sgs->nr_preferred_running += rq->nr_preferred_running;
5525 #endif
5526 		sgs->sum_weighted_load += weighted_cpuload(i);
5527 		if (idle_cpu(i))
5528 			sgs->idle_cpus++;
5529 	}
5530 
5531 	/* Adjust by relative CPU power of the group */
5532 	sgs->group_power = group->sgp->power;
5533 	sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE) / sgs->group_power;
5534 
5535 	if (sgs->sum_nr_running)
5536 		sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
5537 
5538 	sgs->group_weight = group->group_weight;
5539 
5540 	sgs->group_imb = sg_imbalanced(group);
5541 	sgs->group_capacity = sg_capacity(env, group);
5542 
5543 	if (sgs->group_capacity > sgs->sum_nr_running)
5544 		sgs->group_has_capacity = 1;
5545 }
5546 
5547 /**
5548  * update_sd_pick_busiest - return 1 on busiest group
5549  * @env: The load balancing environment.
5550  * @sds: sched_domain statistics
5551  * @sg: sched_group candidate to be checked for being the busiest
5552  * @sgs: sched_group statistics
5553  *
5554  * Determine if @sg is a busier group than the previously selected
5555  * busiest group.
5556  *
5557  * Return: %true if @sg is a busier group than the previously selected
5558  * busiest group. %false otherwise.
5559  */
5560 static bool update_sd_pick_busiest(struct lb_env *env,
5561 				   struct sd_lb_stats *sds,
5562 				   struct sched_group *sg,
5563 				   struct sg_lb_stats *sgs)
5564 {
5565 	if (sgs->avg_load <= sds->busiest_stat.avg_load)
5566 		return false;
5567 
5568 	if (sgs->sum_nr_running > sgs->group_capacity)
5569 		return true;
5570 
5571 	if (sgs->group_imb)
5572 		return true;
5573 
5574 	/*
5575 	 * ASYM_PACKING needs to move all the work to the lowest
5576 	 * numbered CPUs in the group, therefore mark all groups
5577 	 * higher than ourself as busy.
5578 	 */
5579 	if ((env->sd->flags & SD_ASYM_PACKING) && sgs->sum_nr_running &&
5580 	    env->dst_cpu < group_first_cpu(sg)) {
5581 		if (!sds->busiest)
5582 			return true;
5583 
5584 		if (group_first_cpu(sds->busiest) > group_first_cpu(sg))
5585 			return true;
5586 	}
5587 
5588 	return false;
5589 }
5590 
5591 #ifdef CONFIG_NUMA_BALANCING
5592 static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
5593 {
5594 	if (sgs->sum_nr_running > sgs->nr_numa_running)
5595 		return regular;
5596 	if (sgs->sum_nr_running > sgs->nr_preferred_running)
5597 		return remote;
5598 	return all;
5599 }
5600 
5601 static inline enum fbq_type fbq_classify_rq(struct rq *rq)
5602 {
5603 	if (rq->nr_running > rq->nr_numa_running)
5604 		return regular;
5605 	if (rq->nr_running > rq->nr_preferred_running)
5606 		return remote;
5607 	return all;
5608 }
5609 #else
5610 static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
5611 {
5612 	return all;
5613 }
5614 
5615 static inline enum fbq_type fbq_classify_rq(struct rq *rq)
5616 {
5617 	return regular;
5618 }
5619 #endif /* CONFIG_NUMA_BALANCING */
5620 
5621 /**
5622  * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
5623  * @env: The load balancing environment.
5624  * @sds: variable to hold the statistics for this sched_domain.
5625  */
5626 static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sds)
5627 {
5628 	struct sched_domain *child = env->sd->child;
5629 	struct sched_group *sg = env->sd->groups;
5630 	struct sg_lb_stats tmp_sgs;
5631 	int load_idx, prefer_sibling = 0;
5632 
5633 	if (child && child->flags & SD_PREFER_SIBLING)
5634 		prefer_sibling = 1;
5635 
5636 	load_idx = get_sd_load_idx(env->sd, env->idle);
5637 
5638 	do {
5639 		struct sg_lb_stats *sgs = &tmp_sgs;
5640 		int local_group;
5641 
5642 		local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg));
5643 		if (local_group) {
5644 			sds->local = sg;
5645 			sgs = &sds->local_stat;
5646 
5647 			if (env->idle != CPU_NEWLY_IDLE ||
5648 			    time_after_eq(jiffies, sg->sgp->next_update))
5649 				update_group_power(env->sd, env->dst_cpu);
5650 		}
5651 
5652 		update_sg_lb_stats(env, sg, load_idx, local_group, sgs);
5653 
5654 		if (local_group)
5655 			goto next_group;
5656 
5657 		/*
5658 		 * In case the child domain prefers tasks go to siblings
5659 		 * first, lower the sg capacity to one so that we'll try
5660 		 * and move all the excess tasks away. We lower the capacity
5661 		 * of a group only if the local group has the capacity to fit
5662 		 * these excess tasks, i.e. nr_running < group_capacity. The
5663 		 * extra check prevents the case where you always pull from the
5664 		 * heaviest group when it is already under-utilized (possible
5665 		 * with a large weight task outweighs the tasks on the system).
5666 		 */
5667 		if (prefer_sibling && sds->local &&
5668 		    sds->local_stat.group_has_capacity)
5669 			sgs->group_capacity = min(sgs->group_capacity, 1U);
5670 
5671 		if (update_sd_pick_busiest(env, sds, sg, sgs)) {
5672 			sds->busiest = sg;
5673 			sds->busiest_stat = *sgs;
5674 		}
5675 
5676 next_group:
5677 		/* Now, start updating sd_lb_stats */
5678 		sds->total_load += sgs->group_load;
5679 		sds->total_pwr += sgs->group_power;
5680 
5681 		sg = sg->next;
5682 	} while (sg != env->sd->groups);
5683 
5684 	if (env->sd->flags & SD_NUMA)
5685 		env->fbq_type = fbq_classify_group(&sds->busiest_stat);
5686 }
5687 
5688 /**
5689  * check_asym_packing - Check to see if the group is packed into the
5690  *			sched doman.
5691  *
5692  * This is primarily intended to used at the sibling level.  Some
5693  * cores like POWER7 prefer to use lower numbered SMT threads.  In the
5694  * case of POWER7, it can move to lower SMT modes only when higher
5695  * threads are idle.  When in lower SMT modes, the threads will
5696  * perform better since they share less core resources.  Hence when we
5697  * have idle threads, we want them to be the higher ones.
5698  *
5699  * This packing function is run on idle threads.  It checks to see if
5700  * the busiest CPU in this domain (core in the P7 case) has a higher
5701  * CPU number than the packing function is being run on.  Here we are
5702  * assuming lower CPU number will be equivalent to lower a SMT thread
5703  * number.
5704  *
5705  * Return: 1 when packing is required and a task should be moved to
5706  * this CPU.  The amount of the imbalance is returned in *imbalance.
5707  *
5708  * @env: The load balancing environment.
5709  * @sds: Statistics of the sched_domain which is to be packed
5710  */
5711 static int check_asym_packing(struct lb_env *env, struct sd_lb_stats *sds)
5712 {
5713 	int busiest_cpu;
5714 
5715 	if (!(env->sd->flags & SD_ASYM_PACKING))
5716 		return 0;
5717 
5718 	if (!sds->busiest)
5719 		return 0;
5720 
5721 	busiest_cpu = group_first_cpu(sds->busiest);
5722 	if (env->dst_cpu > busiest_cpu)
5723 		return 0;
5724 
5725 	env->imbalance = DIV_ROUND_CLOSEST(
5726 		sds->busiest_stat.avg_load * sds->busiest_stat.group_power,
5727 		SCHED_POWER_SCALE);
5728 
5729 	return 1;
5730 }
5731 
5732 /**
5733  * fix_small_imbalance - Calculate the minor imbalance that exists
5734  *			amongst the groups of a sched_domain, during
5735  *			load balancing.
5736  * @env: The load balancing environment.
5737  * @sds: Statistics of the sched_domain whose imbalance is to be calculated.
5738  */
5739 static inline
5740 void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
5741 {
5742 	unsigned long tmp, pwr_now = 0, pwr_move = 0;
5743 	unsigned int imbn = 2;
5744 	unsigned long scaled_busy_load_per_task;
5745 	struct sg_lb_stats *local, *busiest;
5746 
5747 	local = &sds->local_stat;
5748 	busiest = &sds->busiest_stat;
5749 
5750 	if (!local->sum_nr_running)
5751 		local->load_per_task = cpu_avg_load_per_task(env->dst_cpu);
5752 	else if (busiest->load_per_task > local->load_per_task)
5753 		imbn = 1;
5754 
5755 	scaled_busy_load_per_task =
5756 		(busiest->load_per_task * SCHED_POWER_SCALE) /
5757 		busiest->group_power;
5758 
5759 	if (busiest->avg_load + scaled_busy_load_per_task >=
5760 	    local->avg_load + (scaled_busy_load_per_task * imbn)) {
5761 		env->imbalance = busiest->load_per_task;
5762 		return;
5763 	}
5764 
5765 	/*
5766 	 * OK, we don't have enough imbalance to justify moving tasks,
5767 	 * however we may be able to increase total CPU power used by
5768 	 * moving them.
5769 	 */
5770 
5771 	pwr_now += busiest->group_power *
5772 			min(busiest->load_per_task, busiest->avg_load);
5773 	pwr_now += local->group_power *
5774 			min(local->load_per_task, local->avg_load);
5775 	pwr_now /= SCHED_POWER_SCALE;
5776 
5777 	/* Amount of load we'd subtract */
5778 	tmp = (busiest->load_per_task * SCHED_POWER_SCALE) /
5779 		busiest->group_power;
5780 	if (busiest->avg_load > tmp) {
5781 		pwr_move += busiest->group_power *
5782 			    min(busiest->load_per_task,
5783 				busiest->avg_load - tmp);
5784 	}
5785 
5786 	/* Amount of load we'd add */
5787 	if (busiest->avg_load * busiest->group_power <
5788 	    busiest->load_per_task * SCHED_POWER_SCALE) {
5789 		tmp = (busiest->avg_load * busiest->group_power) /
5790 		      local->group_power;
5791 	} else {
5792 		tmp = (busiest->load_per_task * SCHED_POWER_SCALE) /
5793 		      local->group_power;
5794 	}
5795 	pwr_move += local->group_power *
5796 		    min(local->load_per_task, local->avg_load + tmp);
5797 	pwr_move /= SCHED_POWER_SCALE;
5798 
5799 	/* Move if we gain throughput */
5800 	if (pwr_move > pwr_now)
5801 		env->imbalance = busiest->load_per_task;
5802 }
5803 
5804 /**
5805  * calculate_imbalance - Calculate the amount of imbalance present within the
5806  *			 groups of a given sched_domain during load balance.
5807  * @env: load balance environment
5808  * @sds: statistics of the sched_domain whose imbalance is to be calculated.
5809  */
5810 static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
5811 {
5812 	unsigned long max_pull, load_above_capacity = ~0UL;
5813 	struct sg_lb_stats *local, *busiest;
5814 
5815 	local = &sds->local_stat;
5816 	busiest = &sds->busiest_stat;
5817 
5818 	if (busiest->group_imb) {
5819 		/*
5820 		 * In the group_imb case we cannot rely on group-wide averages
5821 		 * to ensure cpu-load equilibrium, look at wider averages. XXX
5822 		 */
5823 		busiest->load_per_task =
5824 			min(busiest->load_per_task, sds->avg_load);
5825 	}
5826 
5827 	/*
5828 	 * In the presence of smp nice balancing, certain scenarios can have
5829 	 * max load less than avg load(as we skip the groups at or below
5830 	 * its cpu_power, while calculating max_load..)
5831 	 */
5832 	if (busiest->avg_load <= sds->avg_load ||
5833 	    local->avg_load >= sds->avg_load) {
5834 		env->imbalance = 0;
5835 		return fix_small_imbalance(env, sds);
5836 	}
5837 
5838 	if (!busiest->group_imb) {
5839 		/*
5840 		 * Don't want to pull so many tasks that a group would go idle.
5841 		 * Except of course for the group_imb case, since then we might
5842 		 * have to drop below capacity to reach cpu-load equilibrium.
5843 		 */
5844 		load_above_capacity =
5845 			(busiest->sum_nr_running - busiest->group_capacity);
5846 
5847 		load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_POWER_SCALE);
5848 		load_above_capacity /= busiest->group_power;
5849 	}
5850 
5851 	/*
5852 	 * We're trying to get all the cpus to the average_load, so we don't
5853 	 * want to push ourselves above the average load, nor do we wish to
5854 	 * reduce the max loaded cpu below the average load. At the same time,
5855 	 * we also don't want to reduce the group load below the group capacity
5856 	 * (so that we can implement power-savings policies etc). Thus we look
5857 	 * for the minimum possible imbalance.
5858 	 */
5859 	max_pull = min(busiest->avg_load - sds->avg_load, load_above_capacity);
5860 
5861 	/* How much load to actually move to equalise the imbalance */
5862 	env->imbalance = min(
5863 		max_pull * busiest->group_power,
5864 		(sds->avg_load - local->avg_load) * local->group_power
5865 	) / SCHED_POWER_SCALE;
5866 
5867 	/*
5868 	 * if *imbalance is less than the average load per runnable task
5869 	 * there is no guarantee that any tasks will be moved so we'll have
5870 	 * a think about bumping its value to force at least one task to be
5871 	 * moved
5872 	 */
5873 	if (env->imbalance < busiest->load_per_task)
5874 		return fix_small_imbalance(env, sds);
5875 }
5876 
5877 /******* find_busiest_group() helpers end here *********************/
5878 
5879 /**
5880  * find_busiest_group - Returns the busiest group within the sched_domain
5881  * if there is an imbalance. If there isn't an imbalance, and
5882  * the user has opted for power-savings, it returns a group whose
5883  * CPUs can be put to idle by rebalancing those tasks elsewhere, if
5884  * such a group exists.
5885  *
5886  * Also calculates the amount of weighted load which should be moved
5887  * to restore balance.
5888  *
5889  * @env: The load balancing environment.
5890  *
5891  * Return:	- The busiest group if imbalance exists.
5892  *		- If no imbalance and user has opted for power-savings balance,
5893  *		   return the least loaded group whose CPUs can be
5894  *		   put to idle by rebalancing its tasks onto our group.
5895  */
5896 static struct sched_group *find_busiest_group(struct lb_env *env)
5897 {
5898 	struct sg_lb_stats *local, *busiest;
5899 	struct sd_lb_stats sds;
5900 
5901 	init_sd_lb_stats(&sds);
5902 
5903 	/*
5904 	 * Compute the various statistics relavent for load balancing at
5905 	 * this level.
5906 	 */
5907 	update_sd_lb_stats(env, &sds);
5908 	local = &sds.local_stat;
5909 	busiest = &sds.busiest_stat;
5910 
5911 	if ((env->idle == CPU_IDLE || env->idle == CPU_NEWLY_IDLE) &&
5912 	    check_asym_packing(env, &sds))
5913 		return sds.busiest;
5914 
5915 	/* There is no busy sibling group to pull tasks from */
5916 	if (!sds.busiest || busiest->sum_nr_running == 0)
5917 		goto out_balanced;
5918 
5919 	sds.avg_load = (SCHED_POWER_SCALE * sds.total_load) / sds.total_pwr;
5920 
5921 	/*
5922 	 * If the busiest group is imbalanced the below checks don't
5923 	 * work because they assume all things are equal, which typically
5924 	 * isn't true due to cpus_allowed constraints and the like.
5925 	 */
5926 	if (busiest->group_imb)
5927 		goto force_balance;
5928 
5929 	/* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */
5930 	if (env->idle == CPU_NEWLY_IDLE && local->group_has_capacity &&
5931 	    !busiest->group_has_capacity)
5932 		goto force_balance;
5933 
5934 	/*
5935 	 * If the local group is more busy than the selected busiest group
5936 	 * don't try and pull any tasks.
5937 	 */
5938 	if (local->avg_load >= busiest->avg_load)
5939 		goto out_balanced;
5940 
5941 	/*
5942 	 * Don't pull any tasks if this group is already above the domain
5943 	 * average load.
5944 	 */
5945 	if (local->avg_load >= sds.avg_load)
5946 		goto out_balanced;
5947 
5948 	if (env->idle == CPU_IDLE) {
5949 		/*
5950 		 * This cpu is idle. If the busiest group load doesn't
5951 		 * have more tasks than the number of available cpu's and
5952 		 * there is no imbalance between this and busiest group
5953 		 * wrt to idle cpu's, it is balanced.
5954 		 */
5955 		if ((local->idle_cpus < busiest->idle_cpus) &&
5956 		    busiest->sum_nr_running <= busiest->group_weight)
5957 			goto out_balanced;
5958 	} else {
5959 		/*
5960 		 * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use
5961 		 * imbalance_pct to be conservative.
5962 		 */
5963 		if (100 * busiest->avg_load <=
5964 				env->sd->imbalance_pct * local->avg_load)
5965 			goto out_balanced;
5966 	}
5967 
5968 force_balance:
5969 	/* Looks like there is an imbalance. Compute it */
5970 	calculate_imbalance(env, &sds);
5971 	return sds.busiest;
5972 
5973 out_balanced:
5974 	env->imbalance = 0;
5975 	return NULL;
5976 }
5977 
5978 /*
5979  * find_busiest_queue - find the busiest runqueue among the cpus in group.
5980  */
5981 static struct rq *find_busiest_queue(struct lb_env *env,
5982 				     struct sched_group *group)
5983 {
5984 	struct rq *busiest = NULL, *rq;
5985 	unsigned long busiest_load = 0, busiest_power = 1;
5986 	int i;
5987 
5988 	for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
5989 		unsigned long power, capacity, wl;
5990 		enum fbq_type rt;
5991 
5992 		rq = cpu_rq(i);
5993 		rt = fbq_classify_rq(rq);
5994 
5995 		/*
5996 		 * We classify groups/runqueues into three groups:
5997 		 *  - regular: there are !numa tasks
5998 		 *  - remote:  there are numa tasks that run on the 'wrong' node
5999 		 *  - all:     there is no distinction
6000 		 *
6001 		 * In order to avoid migrating ideally placed numa tasks,
6002 		 * ignore those when there's better options.
6003 		 *
6004 		 * If we ignore the actual busiest queue to migrate another
6005 		 * task, the next balance pass can still reduce the busiest
6006 		 * queue by moving tasks around inside the node.
6007 		 *
6008 		 * If we cannot move enough load due to this classification
6009 		 * the next pass will adjust the group classification and
6010 		 * allow migration of more tasks.
6011 		 *
6012 		 * Both cases only affect the total convergence complexity.
6013 		 */
6014 		if (rt > env->fbq_type)
6015 			continue;
6016 
6017 		power = power_of(i);
6018 		capacity = DIV_ROUND_CLOSEST(power, SCHED_POWER_SCALE);
6019 		if (!capacity)
6020 			capacity = fix_small_capacity(env->sd, group);
6021 
6022 		wl = weighted_cpuload(i);
6023 
6024 		/*
6025 		 * When comparing with imbalance, use weighted_cpuload()
6026 		 * which is not scaled with the cpu power.
6027 		 */
6028 		if (capacity && rq->nr_running == 1 && wl > env->imbalance)
6029 			continue;
6030 
6031 		/*
6032 		 * For the load comparisons with the other cpu's, consider
6033 		 * the weighted_cpuload() scaled with the cpu power, so that
6034 		 * the load can be moved away from the cpu that is potentially
6035 		 * running at a lower capacity.
6036 		 *
6037 		 * Thus we're looking for max(wl_i / power_i), crosswise
6038 		 * multiplication to rid ourselves of the division works out
6039 		 * to: wl_i * power_j > wl_j * power_i;  where j is our
6040 		 * previous maximum.
6041 		 */
6042 		if (wl * busiest_power > busiest_load * power) {
6043 			busiest_load = wl;
6044 			busiest_power = power;
6045 			busiest = rq;
6046 		}
6047 	}
6048 
6049 	return busiest;
6050 }
6051 
6052 /*
6053  * Max backoff if we encounter pinned tasks. Pretty arbitrary value, but
6054  * so long as it is large enough.
6055  */
6056 #define MAX_PINNED_INTERVAL	512
6057 
6058 /* Working cpumask for load_balance and load_balance_newidle. */
6059 DEFINE_PER_CPU(cpumask_var_t, load_balance_mask);
6060 
6061 static int need_active_balance(struct lb_env *env)
6062 {
6063 	struct sched_domain *sd = env->sd;
6064 
6065 	if (env->idle == CPU_NEWLY_IDLE) {
6066 
6067 		/*
6068 		 * ASYM_PACKING needs to force migrate tasks from busy but
6069 		 * higher numbered CPUs in order to pack all tasks in the
6070 		 * lowest numbered CPUs.
6071 		 */
6072 		if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
6073 			return 1;
6074 	}
6075 
6076 	return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
6077 }
6078 
6079 static int active_load_balance_cpu_stop(void *data);
6080 
6081 static int should_we_balance(struct lb_env *env)
6082 {
6083 	struct sched_group *sg = env->sd->groups;
6084 	struct cpumask *sg_cpus, *sg_mask;
6085 	int cpu, balance_cpu = -1;
6086 
6087 	/*
6088 	 * In the newly idle case, we will allow all the cpu's
6089 	 * to do the newly idle load balance.
6090 	 */
6091 	if (env->idle == CPU_NEWLY_IDLE)
6092 		return 1;
6093 
6094 	sg_cpus = sched_group_cpus(sg);
6095 	sg_mask = sched_group_mask(sg);
6096 	/* Try to find first idle cpu */
6097 	for_each_cpu_and(cpu, sg_cpus, env->cpus) {
6098 		if (!cpumask_test_cpu(cpu, sg_mask) || !idle_cpu(cpu))
6099 			continue;
6100 
6101 		balance_cpu = cpu;
6102 		break;
6103 	}
6104 
6105 	if (balance_cpu == -1)
6106 		balance_cpu = group_balance_cpu(sg);
6107 
6108 	/*
6109 	 * First idle cpu or the first cpu(busiest) in this sched group
6110 	 * is eligible for doing load balancing at this and above domains.
6111 	 */
6112 	return balance_cpu == env->dst_cpu;
6113 }
6114 
6115 /*
6116  * Check this_cpu to ensure it is balanced within domain. Attempt to move
6117  * tasks if there is an imbalance.
6118  */
6119 static int load_balance(int this_cpu, struct rq *this_rq,
6120 			struct sched_domain *sd, enum cpu_idle_type idle,
6121 			int *continue_balancing)
6122 {
6123 	int ld_moved, cur_ld_moved, active_balance = 0;
6124 	struct sched_domain *sd_parent = sd->parent;
6125 	struct sched_group *group;
6126 	struct rq *busiest;
6127 	unsigned long flags;
6128 	struct cpumask *cpus = __get_cpu_var(load_balance_mask);
6129 
6130 	struct lb_env env = {
6131 		.sd		= sd,
6132 		.dst_cpu	= this_cpu,
6133 		.dst_rq		= this_rq,
6134 		.dst_grpmask    = sched_group_cpus(sd->groups),
6135 		.idle		= idle,
6136 		.loop_break	= sched_nr_migrate_break,
6137 		.cpus		= cpus,
6138 		.fbq_type	= all,
6139 	};
6140 
6141 	/*
6142 	 * For NEWLY_IDLE load_balancing, we don't need to consider
6143 	 * other cpus in our group
6144 	 */
6145 	if (idle == CPU_NEWLY_IDLE)
6146 		env.dst_grpmask = NULL;
6147 
6148 	cpumask_copy(cpus, cpu_active_mask);
6149 
6150 	schedstat_inc(sd, lb_count[idle]);
6151 
6152 redo:
6153 	if (!should_we_balance(&env)) {
6154 		*continue_balancing = 0;
6155 		goto out_balanced;
6156 	}
6157 
6158 	group = find_busiest_group(&env);
6159 	if (!group) {
6160 		schedstat_inc(sd, lb_nobusyg[idle]);
6161 		goto out_balanced;
6162 	}
6163 
6164 	busiest = find_busiest_queue(&env, group);
6165 	if (!busiest) {
6166 		schedstat_inc(sd, lb_nobusyq[idle]);
6167 		goto out_balanced;
6168 	}
6169 
6170 	BUG_ON(busiest == env.dst_rq);
6171 
6172 	schedstat_add(sd, lb_imbalance[idle], env.imbalance);
6173 
6174 	ld_moved = 0;
6175 	if (busiest->nr_running > 1) {
6176 		/*
6177 		 * Attempt to move tasks. If find_busiest_group has found
6178 		 * an imbalance but busiest->nr_running <= 1, the group is
6179 		 * still unbalanced. ld_moved simply stays zero, so it is
6180 		 * correctly treated as an imbalance.
6181 		 */
6182 		env.flags |= LBF_ALL_PINNED;
6183 		env.src_cpu   = busiest->cpu;
6184 		env.src_rq    = busiest;
6185 		env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);
6186 
6187 more_balance:
6188 		local_irq_save(flags);
6189 		double_rq_lock(env.dst_rq, busiest);
6190 
6191 		/*
6192 		 * cur_ld_moved - load moved in current iteration
6193 		 * ld_moved     - cumulative load moved across iterations
6194 		 */
6195 		cur_ld_moved = move_tasks(&env);
6196 		ld_moved += cur_ld_moved;
6197 		double_rq_unlock(env.dst_rq, busiest);
6198 		local_irq_restore(flags);
6199 
6200 		/*
6201 		 * some other cpu did the load balance for us.
6202 		 */
6203 		if (cur_ld_moved && env.dst_cpu != smp_processor_id())
6204 			resched_cpu(env.dst_cpu);
6205 
6206 		if (env.flags & LBF_NEED_BREAK) {
6207 			env.flags &= ~LBF_NEED_BREAK;
6208 			goto more_balance;
6209 		}
6210 
6211 		/*
6212 		 * Revisit (affine) tasks on src_cpu that couldn't be moved to
6213 		 * us and move them to an alternate dst_cpu in our sched_group
6214 		 * where they can run. The upper limit on how many times we
6215 		 * iterate on same src_cpu is dependent on number of cpus in our
6216 		 * sched_group.
6217 		 *
6218 		 * This changes load balance semantics a bit on who can move
6219 		 * load to a given_cpu. In addition to the given_cpu itself
6220 		 * (or a ilb_cpu acting on its behalf where given_cpu is
6221 		 * nohz-idle), we now have balance_cpu in a position to move
6222 		 * load to given_cpu. In rare situations, this may cause
6223 		 * conflicts (balance_cpu and given_cpu/ilb_cpu deciding
6224 		 * _independently_ and at _same_ time to move some load to
6225 		 * given_cpu) causing exceess load to be moved to given_cpu.
6226 		 * This however should not happen so much in practice and
6227 		 * moreover subsequent load balance cycles should correct the
6228 		 * excess load moved.
6229 		 */
6230 		if ((env.flags & LBF_DST_PINNED) && env.imbalance > 0) {
6231 
6232 			/* Prevent to re-select dst_cpu via env's cpus */
6233 			cpumask_clear_cpu(env.dst_cpu, env.cpus);
6234 
6235 			env.dst_rq	 = cpu_rq(env.new_dst_cpu);
6236 			env.dst_cpu	 = env.new_dst_cpu;
6237 			env.flags	&= ~LBF_DST_PINNED;
6238 			env.loop	 = 0;
6239 			env.loop_break	 = sched_nr_migrate_break;
6240 
6241 			/*
6242 			 * Go back to "more_balance" rather than "redo" since we
6243 			 * need to continue with same src_cpu.
6244 			 */
6245 			goto more_balance;
6246 		}
6247 
6248 		/*
6249 		 * We failed to reach balance because of affinity.
6250 		 */
6251 		if (sd_parent) {
6252 			int *group_imbalance = &sd_parent->groups->sgp->imbalance;
6253 
6254 			if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0) {
6255 				*group_imbalance = 1;
6256 			} else if (*group_imbalance)
6257 				*group_imbalance = 0;
6258 		}
6259 
6260 		/* All tasks on this runqueue were pinned by CPU affinity */
6261 		if (unlikely(env.flags & LBF_ALL_PINNED)) {
6262 			cpumask_clear_cpu(cpu_of(busiest), cpus);
6263 			if (!cpumask_empty(cpus)) {
6264 				env.loop = 0;
6265 				env.loop_break = sched_nr_migrate_break;
6266 				goto redo;
6267 			}
6268 			goto out_balanced;
6269 		}
6270 	}
6271 
6272 	if (!ld_moved) {
6273 		schedstat_inc(sd, lb_failed[idle]);
6274 		/*
6275 		 * Increment the failure counter only on periodic balance.
6276 		 * We do not want newidle balance, which can be very
6277 		 * frequent, pollute the failure counter causing
6278 		 * excessive cache_hot migrations and active balances.
6279 		 */
6280 		if (idle != CPU_NEWLY_IDLE)
6281 			sd->nr_balance_failed++;
6282 
6283 		if (need_active_balance(&env)) {
6284 			raw_spin_lock_irqsave(&busiest->lock, flags);
6285 
6286 			/* don't kick the active_load_balance_cpu_stop,
6287 			 * if the curr task on busiest cpu can't be
6288 			 * moved to this_cpu
6289 			 */
6290 			if (!cpumask_test_cpu(this_cpu,
6291 					tsk_cpus_allowed(busiest->curr))) {
6292 				raw_spin_unlock_irqrestore(&busiest->lock,
6293 							    flags);
6294 				env.flags |= LBF_ALL_PINNED;
6295 				goto out_one_pinned;
6296 			}
6297 
6298 			/*
6299 			 * ->active_balance synchronizes accesses to
6300 			 * ->active_balance_work.  Once set, it's cleared
6301 			 * only after active load balance is finished.
6302 			 */
6303 			if (!busiest->active_balance) {
6304 				busiest->active_balance = 1;
6305 				busiest->push_cpu = this_cpu;
6306 				active_balance = 1;
6307 			}
6308 			raw_spin_unlock_irqrestore(&busiest->lock, flags);
6309 
6310 			if (active_balance) {
6311 				stop_one_cpu_nowait(cpu_of(busiest),
6312 					active_load_balance_cpu_stop, busiest,
6313 					&busiest->active_balance_work);
6314 			}
6315 
6316 			/*
6317 			 * We've kicked active balancing, reset the failure
6318 			 * counter.
6319 			 */
6320 			sd->nr_balance_failed = sd->cache_nice_tries+1;
6321 		}
6322 	} else
6323 		sd->nr_balance_failed = 0;
6324 
6325 	if (likely(!active_balance)) {
6326 		/* We were unbalanced, so reset the balancing interval */
6327 		sd->balance_interval = sd->min_interval;
6328 	} else {
6329 		/*
6330 		 * If we've begun active balancing, start to back off. This
6331 		 * case may not be covered by the all_pinned logic if there
6332 		 * is only 1 task on the busy runqueue (because we don't call
6333 		 * move_tasks).
6334 		 */
6335 		if (sd->balance_interval < sd->max_interval)
6336 			sd->balance_interval *= 2;
6337 	}
6338 
6339 	goto out;
6340 
6341 out_balanced:
6342 	schedstat_inc(sd, lb_balanced[idle]);
6343 
6344 	sd->nr_balance_failed = 0;
6345 
6346 out_one_pinned:
6347 	/* tune up the balancing interval */
6348 	if (((env.flags & LBF_ALL_PINNED) &&
6349 			sd->balance_interval < MAX_PINNED_INTERVAL) ||
6350 			(sd->balance_interval < sd->max_interval))
6351 		sd->balance_interval *= 2;
6352 
6353 	ld_moved = 0;
6354 out:
6355 	return ld_moved;
6356 }
6357 
6358 /*
6359  * idle_balance is called by schedule() if this_cpu is about to become
6360  * idle. Attempts to pull tasks from other CPUs.
6361  */
6362 void idle_balance(int this_cpu, struct rq *this_rq)
6363 {
6364 	struct sched_domain *sd;
6365 	int pulled_task = 0;
6366 	unsigned long next_balance = jiffies + HZ;
6367 	u64 curr_cost = 0;
6368 
6369 	this_rq->idle_stamp = rq_clock(this_rq);
6370 
6371 	if (this_rq->avg_idle < sysctl_sched_migration_cost)
6372 		return;
6373 
6374 	/*
6375 	 * Drop the rq->lock, but keep IRQ/preempt disabled.
6376 	 */
6377 	raw_spin_unlock(&this_rq->lock);
6378 
6379 	update_blocked_averages(this_cpu);
6380 	rcu_read_lock();
6381 	for_each_domain(this_cpu, sd) {
6382 		unsigned long interval;
6383 		int continue_balancing = 1;
6384 		u64 t0, domain_cost;
6385 
6386 		if (!(sd->flags & SD_LOAD_BALANCE))
6387 			continue;
6388 
6389 		if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
6390 			break;
6391 
6392 		if (sd->flags & SD_BALANCE_NEWIDLE) {
6393 			t0 = sched_clock_cpu(this_cpu);
6394 
6395 			/* If we've pulled tasks over stop searching: */
6396 			pulled_task = load_balance(this_cpu, this_rq,
6397 						   sd, CPU_NEWLY_IDLE,
6398 						   &continue_balancing);
6399 
6400 			domain_cost = sched_clock_cpu(this_cpu) - t0;
6401 			if (domain_cost > sd->max_newidle_lb_cost)
6402 				sd->max_newidle_lb_cost = domain_cost;
6403 
6404 			curr_cost += domain_cost;
6405 		}
6406 
6407 		interval = msecs_to_jiffies(sd->balance_interval);
6408 		if (time_after(next_balance, sd->last_balance + interval))
6409 			next_balance = sd->last_balance + interval;
6410 		if (pulled_task) {
6411 			this_rq->idle_stamp = 0;
6412 			break;
6413 		}
6414 	}
6415 	rcu_read_unlock();
6416 
6417 	raw_spin_lock(&this_rq->lock);
6418 
6419 	if (pulled_task || time_after(jiffies, this_rq->next_balance)) {
6420 		/*
6421 		 * We are going idle. next_balance may be set based on
6422 		 * a busy processor. So reset next_balance.
6423 		 */
6424 		this_rq->next_balance = next_balance;
6425 	}
6426 
6427 	if (curr_cost > this_rq->max_idle_balance_cost)
6428 		this_rq->max_idle_balance_cost = curr_cost;
6429 }
6430 
6431 /*
6432  * active_load_balance_cpu_stop is run by cpu stopper. It pushes
6433  * running tasks off the busiest CPU onto idle CPUs. It requires at
6434  * least 1 task to be running on each physical CPU where possible, and
6435  * avoids physical / logical imbalances.
6436  */
6437 static int active_load_balance_cpu_stop(void *data)
6438 {
6439 	struct rq *busiest_rq = data;
6440 	int busiest_cpu = cpu_of(busiest_rq);
6441 	int target_cpu = busiest_rq->push_cpu;
6442 	struct rq *target_rq = cpu_rq(target_cpu);
6443 	struct sched_domain *sd;
6444 
6445 	raw_spin_lock_irq(&busiest_rq->lock);
6446 
6447 	/* make sure the requested cpu hasn't gone down in the meantime */
6448 	if (unlikely(busiest_cpu != smp_processor_id() ||
6449 		     !busiest_rq->active_balance))
6450 		goto out_unlock;
6451 
6452 	/* Is there any task to move? */
6453 	if (busiest_rq->nr_running <= 1)
6454 		goto out_unlock;
6455 
6456 	/*
6457 	 * This condition is "impossible", if it occurs
6458 	 * we need to fix it. Originally reported by
6459 	 * Bjorn Helgaas on a 128-cpu setup.
6460 	 */
6461 	BUG_ON(busiest_rq == target_rq);
6462 
6463 	/* move a task from busiest_rq to target_rq */
6464 	double_lock_balance(busiest_rq, target_rq);
6465 
6466 	/* Search for an sd spanning us and the target CPU. */
6467 	rcu_read_lock();
6468 	for_each_domain(target_cpu, sd) {
6469 		if ((sd->flags & SD_LOAD_BALANCE) &&
6470 		    cpumask_test_cpu(busiest_cpu, sched_domain_span(sd)))
6471 				break;
6472 	}
6473 
6474 	if (likely(sd)) {
6475 		struct lb_env env = {
6476 			.sd		= sd,
6477 			.dst_cpu	= target_cpu,
6478 			.dst_rq		= target_rq,
6479 			.src_cpu	= busiest_rq->cpu,
6480 			.src_rq		= busiest_rq,
6481 			.idle		= CPU_IDLE,
6482 		};
6483 
6484 		schedstat_inc(sd, alb_count);
6485 
6486 		if (move_one_task(&env))
6487 			schedstat_inc(sd, alb_pushed);
6488 		else
6489 			schedstat_inc(sd, alb_failed);
6490 	}
6491 	rcu_read_unlock();
6492 	double_unlock_balance(busiest_rq, target_rq);
6493 out_unlock:
6494 	busiest_rq->active_balance = 0;
6495 	raw_spin_unlock_irq(&busiest_rq->lock);
6496 	return 0;
6497 }
6498 
6499 #ifdef CONFIG_NO_HZ_COMMON
6500 /*
6501  * idle load balancing details
6502  * - When one of the busy CPUs notice that there may be an idle rebalancing
6503  *   needed, they will kick the idle load balancer, which then does idle
6504  *   load balancing for all the idle CPUs.
6505  */
6506 static struct {
6507 	cpumask_var_t idle_cpus_mask;
6508 	atomic_t nr_cpus;
6509 	unsigned long next_balance;     /* in jiffy units */
6510 } nohz ____cacheline_aligned;
6511 
6512 static inline int find_new_ilb(void)
6513 {
6514 	int ilb = cpumask_first(nohz.idle_cpus_mask);
6515 
6516 	if (ilb < nr_cpu_ids && idle_cpu(ilb))
6517 		return ilb;
6518 
6519 	return nr_cpu_ids;
6520 }
6521 
6522 /*
6523  * Kick a CPU to do the nohz balancing, if it is time for it. We pick the
6524  * nohz_load_balancer CPU (if there is one) otherwise fallback to any idle
6525  * CPU (if there is one).
6526  */
6527 static void nohz_balancer_kick(void)
6528 {
6529 	int ilb_cpu;
6530 
6531 	nohz.next_balance++;
6532 
6533 	ilb_cpu = find_new_ilb();
6534 
6535 	if (ilb_cpu >= nr_cpu_ids)
6536 		return;
6537 
6538 	if (test_and_set_bit(NOHZ_BALANCE_KICK, nohz_flags(ilb_cpu)))
6539 		return;
6540 	/*
6541 	 * Use smp_send_reschedule() instead of resched_cpu().
6542 	 * This way we generate a sched IPI on the target cpu which
6543 	 * is idle. And the softirq performing nohz idle load balance
6544 	 * will be run before returning from the IPI.
6545 	 */
6546 	smp_send_reschedule(ilb_cpu);
6547 	return;
6548 }
6549 
6550 static inline void nohz_balance_exit_idle(int cpu)
6551 {
6552 	if (unlikely(test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)))) {
6553 		cpumask_clear_cpu(cpu, nohz.idle_cpus_mask);
6554 		atomic_dec(&nohz.nr_cpus);
6555 		clear_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu));
6556 	}
6557 }
6558 
6559 static inline void set_cpu_sd_state_busy(void)
6560 {
6561 	struct sched_domain *sd;
6562 	int cpu = smp_processor_id();
6563 
6564 	rcu_read_lock();
6565 	sd = rcu_dereference(per_cpu(sd_busy, cpu));
6566 
6567 	if (!sd || !sd->nohz_idle)
6568 		goto unlock;
6569 	sd->nohz_idle = 0;
6570 
6571 	atomic_inc(&sd->groups->sgp->nr_busy_cpus);
6572 unlock:
6573 	rcu_read_unlock();
6574 }
6575 
6576 void set_cpu_sd_state_idle(void)
6577 {
6578 	struct sched_domain *sd;
6579 	int cpu = smp_processor_id();
6580 
6581 	rcu_read_lock();
6582 	sd = rcu_dereference(per_cpu(sd_busy, cpu));
6583 
6584 	if (!sd || sd->nohz_idle)
6585 		goto unlock;
6586 	sd->nohz_idle = 1;
6587 
6588 	atomic_dec(&sd->groups->sgp->nr_busy_cpus);
6589 unlock:
6590 	rcu_read_unlock();
6591 }
6592 
6593 /*
6594  * This routine will record that the cpu is going idle with tick stopped.
6595  * This info will be used in performing idle load balancing in the future.
6596  */
6597 void nohz_balance_enter_idle(int cpu)
6598 {
6599 	/*
6600 	 * If this cpu is going down, then nothing needs to be done.
6601 	 */
6602 	if (!cpu_active(cpu))
6603 		return;
6604 
6605 	if (test_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu)))
6606 		return;
6607 
6608 	cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
6609 	atomic_inc(&nohz.nr_cpus);
6610 	set_bit(NOHZ_TICK_STOPPED, nohz_flags(cpu));
6611 }
6612 
6613 static int sched_ilb_notifier(struct notifier_block *nfb,
6614 					unsigned long action, void *hcpu)
6615 {
6616 	switch (action & ~CPU_TASKS_FROZEN) {
6617 	case CPU_DYING:
6618 		nohz_balance_exit_idle(smp_processor_id());
6619 		return NOTIFY_OK;
6620 	default:
6621 		return NOTIFY_DONE;
6622 	}
6623 }
6624 #endif
6625 
6626 static DEFINE_SPINLOCK(balancing);
6627 
6628 /*
6629  * Scale the max load_balance interval with the number of CPUs in the system.
6630  * This trades load-balance latency on larger machines for less cross talk.
6631  */
6632 void update_max_interval(void)
6633 {
6634 	max_load_balance_interval = HZ*num_online_cpus()/10;
6635 }
6636 
6637 /*
6638  * It checks each scheduling domain to see if it is due to be balanced,
6639  * and initiates a balancing operation if so.
6640  *
6641  * Balancing parameters are set up in init_sched_domains.
6642  */
6643 static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
6644 {
6645 	int continue_balancing = 1;
6646 	int cpu = rq->cpu;
6647 	unsigned long interval;
6648 	struct sched_domain *sd;
6649 	/* Earliest time when we have to do rebalance again */
6650 	unsigned long next_balance = jiffies + 60*HZ;
6651 	int update_next_balance = 0;
6652 	int need_serialize, need_decay = 0;
6653 	u64 max_cost = 0;
6654 
6655 	update_blocked_averages(cpu);
6656 
6657 	rcu_read_lock();
6658 	for_each_domain(cpu, sd) {
6659 		/*
6660 		 * Decay the newidle max times here because this is a regular
6661 		 * visit to all the domains. Decay ~1% per second.
6662 		 */
6663 		if (time_after(jiffies, sd->next_decay_max_lb_cost)) {
6664 			sd->max_newidle_lb_cost =
6665 				(sd->max_newidle_lb_cost * 253) / 256;
6666 			sd->next_decay_max_lb_cost = jiffies + HZ;
6667 			need_decay = 1;
6668 		}
6669 		max_cost += sd->max_newidle_lb_cost;
6670 
6671 		if (!(sd->flags & SD_LOAD_BALANCE))
6672 			continue;
6673 
6674 		/*
6675 		 * Stop the load balance at this level. There is another
6676 		 * CPU in our sched group which is doing load balancing more
6677 		 * actively.
6678 		 */
6679 		if (!continue_balancing) {
6680 			if (need_decay)
6681 				continue;
6682 			break;
6683 		}
6684 
6685 		interval = sd->balance_interval;
6686 		if (idle != CPU_IDLE)
6687 			interval *= sd->busy_factor;
6688 
6689 		/* scale ms to jiffies */
6690 		interval = msecs_to_jiffies(interval);
6691 		interval = clamp(interval, 1UL, max_load_balance_interval);
6692 
6693 		need_serialize = sd->flags & SD_SERIALIZE;
6694 
6695 		if (need_serialize) {
6696 			if (!spin_trylock(&balancing))
6697 				goto out;
6698 		}
6699 
6700 		if (time_after_eq(jiffies, sd->last_balance + interval)) {
6701 			if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
6702 				/*
6703 				 * The LBF_DST_PINNED logic could have changed
6704 				 * env->dst_cpu, so we can't know our idle
6705 				 * state even if we migrated tasks. Update it.
6706 				 */
6707 				idle = idle_cpu(cpu) ? CPU_IDLE : CPU_NOT_IDLE;
6708 			}
6709 			sd->last_balance = jiffies;
6710 		}
6711 		if (need_serialize)
6712 			spin_unlock(&balancing);
6713 out:
6714 		if (time_after(next_balance, sd->last_balance + interval)) {
6715 			next_balance = sd->last_balance + interval;
6716 			update_next_balance = 1;
6717 		}
6718 	}
6719 	if (need_decay) {
6720 		/*
6721 		 * Ensure the rq-wide value also decays but keep it at a
6722 		 * reasonable floor to avoid funnies with rq->avg_idle.
6723 		 */
6724 		rq->max_idle_balance_cost =
6725 			max((u64)sysctl_sched_migration_cost, max_cost);
6726 	}
6727 	rcu_read_unlock();
6728 
6729 	/*
6730 	 * next_balance will be updated only when there is a need.
6731 	 * When the cpu is attached to null domain for ex, it will not be
6732 	 * updated.
6733 	 */
6734 	if (likely(update_next_balance))
6735 		rq->next_balance = next_balance;
6736 }
6737 
6738 #ifdef CONFIG_NO_HZ_COMMON
6739 /*
6740  * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
6741  * rebalancing for all the cpus for whom scheduler ticks are stopped.
6742  */
6743 static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)
6744 {
6745 	int this_cpu = this_rq->cpu;
6746 	struct rq *rq;
6747 	int balance_cpu;
6748 
6749 	if (idle != CPU_IDLE ||
6750 	    !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
6751 		goto end;
6752 
6753 	for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
6754 		if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
6755 			continue;
6756 
6757 		/*
6758 		 * If this cpu gets work to do, stop the load balancing
6759 		 * work being done for other cpus. Next load
6760 		 * balancing owner will pick it up.
6761 		 */
6762 		if (need_resched())
6763 			break;
6764 
6765 		rq = cpu_rq(balance_cpu);
6766 
6767 		raw_spin_lock_irq(&rq->lock);
6768 		update_rq_clock(rq);
6769 		update_idle_cpu_load(rq);
6770 		raw_spin_unlock_irq(&rq->lock);
6771 
6772 		rebalance_domains(rq, CPU_IDLE);
6773 
6774 		if (time_after(this_rq->next_balance, rq->next_balance))
6775 			this_rq->next_balance = rq->next_balance;
6776 	}
6777 	nohz.next_balance = this_rq->next_balance;
6778 end:
6779 	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
6780 }
6781 
6782 /*
6783  * Current heuristic for kicking the idle load balancer in the presence
6784  * of an idle cpu is the system.
6785  *   - This rq has more than one task.
6786  *   - At any scheduler domain level, this cpu's scheduler group has multiple
6787  *     busy cpu's exceeding the group's power.
6788  *   - For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler
6789  *     domain span are idle.
6790  */
6791 static inline int nohz_kick_needed(struct rq *rq)
6792 {
6793 	unsigned long now = jiffies;
6794 	struct sched_domain *sd;
6795 	struct sched_group_power *sgp;
6796 	int nr_busy, cpu = rq->cpu;
6797 
6798 	if (unlikely(rq->idle_balance))
6799 		return 0;
6800 
6801        /*
6802 	* We may be recently in ticked or tickless idle mode. At the first
6803 	* busy tick after returning from idle, we will update the busy stats.
6804 	*/
6805 	set_cpu_sd_state_busy();
6806 	nohz_balance_exit_idle(cpu);
6807 
6808 	/*
6809 	 * None are in tickless mode and hence no need for NOHZ idle load
6810 	 * balancing.
6811 	 */
6812 	if (likely(!atomic_read(&nohz.nr_cpus)))
6813 		return 0;
6814 
6815 	if (time_before(now, nohz.next_balance))
6816 		return 0;
6817 
6818 	if (rq->nr_running >= 2)
6819 		goto need_kick;
6820 
6821 	rcu_read_lock();
6822 	sd = rcu_dereference(per_cpu(sd_busy, cpu));
6823 
6824 	if (sd) {
6825 		sgp = sd->groups->sgp;
6826 		nr_busy = atomic_read(&sgp->nr_busy_cpus);
6827 
6828 		if (nr_busy > 1)
6829 			goto need_kick_unlock;
6830 	}
6831 
6832 	sd = rcu_dereference(per_cpu(sd_asym, cpu));
6833 
6834 	if (sd && (cpumask_first_and(nohz.idle_cpus_mask,
6835 				  sched_domain_span(sd)) < cpu))
6836 		goto need_kick_unlock;
6837 
6838 	rcu_read_unlock();
6839 	return 0;
6840 
6841 need_kick_unlock:
6842 	rcu_read_unlock();
6843 need_kick:
6844 	return 1;
6845 }
6846 #else
6847 static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) { }
6848 #endif
6849 
6850 /*
6851  * run_rebalance_domains is triggered when needed from the scheduler tick.
6852  * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
6853  */
6854 static void run_rebalance_domains(struct softirq_action *h)
6855 {
6856 	struct rq *this_rq = this_rq();
6857 	enum cpu_idle_type idle = this_rq->idle_balance ?
6858 						CPU_IDLE : CPU_NOT_IDLE;
6859 
6860 	rebalance_domains(this_rq, idle);
6861 
6862 	/*
6863 	 * If this cpu has a pending nohz_balance_kick, then do the
6864 	 * balancing on behalf of the other idle cpus whose ticks are
6865 	 * stopped.
6866 	 */
6867 	nohz_idle_balance(this_rq, idle);
6868 }
6869 
6870 static inline int on_null_domain(struct rq *rq)
6871 {
6872 	return !rcu_dereference_sched(rq->sd);
6873 }
6874 
6875 /*
6876  * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
6877  */
6878 void trigger_load_balance(struct rq *rq)
6879 {
6880 	/* Don't need to rebalance while attached to NULL domain */
6881 	if (unlikely(on_null_domain(rq)))
6882 		return;
6883 
6884 	if (time_after_eq(jiffies, rq->next_balance))
6885 		raise_softirq(SCHED_SOFTIRQ);
6886 #ifdef CONFIG_NO_HZ_COMMON
6887 	if (nohz_kick_needed(rq))
6888 		nohz_balancer_kick();
6889 #endif
6890 }
6891 
6892 static void rq_online_fair(struct rq *rq)
6893 {
6894 	update_sysctl();
6895 }
6896 
6897 static void rq_offline_fair(struct rq *rq)
6898 {
6899 	update_sysctl();
6900 
6901 	/* Ensure any throttled groups are reachable by pick_next_task */
6902 	unthrottle_offline_cfs_rqs(rq);
6903 }
6904 
6905 #endif /* CONFIG_SMP */
6906 
6907 /*
6908  * scheduler tick hitting a task of our scheduling class:
6909  */
6910 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
6911 {
6912 	struct cfs_rq *cfs_rq;
6913 	struct sched_entity *se = &curr->se;
6914 
6915 	for_each_sched_entity(se) {
6916 		cfs_rq = cfs_rq_of(se);
6917 		entity_tick(cfs_rq, se, queued);
6918 	}
6919 
6920 	if (numabalancing_enabled)
6921 		task_tick_numa(rq, curr);
6922 
6923 	update_rq_runnable_avg(rq, 1);
6924 }
6925 
6926 /*
6927  * called on fork with the child task as argument from the parent's context
6928  *  - child not yet on the tasklist
6929  *  - preemption disabled
6930  */
6931 static void task_fork_fair(struct task_struct *p)
6932 {
6933 	struct cfs_rq *cfs_rq;
6934 	struct sched_entity *se = &p->se, *curr;
6935 	int this_cpu = smp_processor_id();
6936 	struct rq *rq = this_rq();
6937 	unsigned long flags;
6938 
6939 	raw_spin_lock_irqsave(&rq->lock, flags);
6940 
6941 	update_rq_clock(rq);
6942 
6943 	cfs_rq = task_cfs_rq(current);
6944 	curr = cfs_rq->curr;
6945 
6946 	/*
6947 	 * Not only the cpu but also the task_group of the parent might have
6948 	 * been changed after parent->se.parent,cfs_rq were copied to
6949 	 * child->se.parent,cfs_rq. So call __set_task_cpu() to make those
6950 	 * of child point to valid ones.
6951 	 */
6952 	rcu_read_lock();
6953 	__set_task_cpu(p, this_cpu);
6954 	rcu_read_unlock();
6955 
6956 	update_curr(cfs_rq);
6957 
6958 	if (curr)
6959 		se->vruntime = curr->vruntime;
6960 	place_entity(cfs_rq, se, 1);
6961 
6962 	if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
6963 		/*
6964 		 * Upon rescheduling, sched_class::put_prev_task() will place
6965 		 * 'current' within the tree based on its new key value.
6966 		 */
6967 		swap(curr->vruntime, se->vruntime);
6968 		resched_task(rq->curr);
6969 	}
6970 
6971 	se->vruntime -= cfs_rq->min_vruntime;
6972 
6973 	raw_spin_unlock_irqrestore(&rq->lock, flags);
6974 }
6975 
6976 /*
6977  * Priority of the task has changed. Check to see if we preempt
6978  * the current task.
6979  */
6980 static void
6981 prio_changed_fair(struct rq *rq, struct task_struct *p, int oldprio)
6982 {
6983 	if (!p->se.on_rq)
6984 		return;
6985 
6986 	/*
6987 	 * Reschedule if we are currently running on this runqueue and
6988 	 * our priority decreased, or if we are not currently running on
6989 	 * this runqueue and our priority is higher than the current's
6990 	 */
6991 	if (rq->curr == p) {
6992 		if (p->prio > oldprio)
6993 			resched_task(rq->curr);
6994 	} else
6995 		check_preempt_curr(rq, p, 0);
6996 }
6997 
6998 static void switched_from_fair(struct rq *rq, struct task_struct *p)
6999 {
7000 	struct sched_entity *se = &p->se;
7001 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
7002 
7003 	/*
7004 	 * Ensure the task's vruntime is normalized, so that when it's
7005 	 * switched back to the fair class the enqueue_entity(.flags=0) will
7006 	 * do the right thing.
7007 	 *
7008 	 * If it's on_rq, then the dequeue_entity(.flags=0) will already
7009 	 * have normalized the vruntime, if it's !on_rq, then only when
7010 	 * the task is sleeping will it still have non-normalized vruntime.
7011 	 */
7012 	if (!p->on_rq && p->state != TASK_RUNNING) {
7013 		/*
7014 		 * Fix up our vruntime so that the current sleep doesn't
7015 		 * cause 'unlimited' sleep bonus.
7016 		 */
7017 		place_entity(cfs_rq, se, 0);
7018 		se->vruntime -= cfs_rq->min_vruntime;
7019 	}
7020 
7021 #ifdef CONFIG_SMP
7022 	/*
7023 	* Remove our load from contribution when we leave sched_fair
7024 	* and ensure we don't carry in an old decay_count if we
7025 	* switch back.
7026 	*/
7027 	if (se->avg.decay_count) {
7028 		__synchronize_entity_decay(se);
7029 		subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
7030 	}
7031 #endif
7032 }
7033 
7034 /*
7035  * We switched to the sched_fair class.
7036  */
7037 static void switched_to_fair(struct rq *rq, struct task_struct *p)
7038 {
7039 	if (!p->se.on_rq)
7040 		return;
7041 
7042 	/*
7043 	 * We were most likely switched from sched_rt, so
7044 	 * kick off the schedule if running, otherwise just see
7045 	 * if we can still preempt the current task.
7046 	 */
7047 	if (rq->curr == p)
7048 		resched_task(rq->curr);
7049 	else
7050 		check_preempt_curr(rq, p, 0);
7051 }
7052 
7053 /* Account for a task changing its policy or group.
7054  *
7055  * This routine is mostly called to set cfs_rq->curr field when a task
7056  * migrates between groups/classes.
7057  */
7058 static void set_curr_task_fair(struct rq *rq)
7059 {
7060 	struct sched_entity *se = &rq->curr->se;
7061 
7062 	for_each_sched_entity(se) {
7063 		struct cfs_rq *cfs_rq = cfs_rq_of(se);
7064 
7065 		set_next_entity(cfs_rq, se);
7066 		/* ensure bandwidth has been allocated on our new cfs_rq */
7067 		account_cfs_rq_runtime(cfs_rq, 0);
7068 	}
7069 }
7070 
7071 void init_cfs_rq(struct cfs_rq *cfs_rq)
7072 {
7073 	cfs_rq->tasks_timeline = RB_ROOT;
7074 	cfs_rq->min_vruntime = (u64)(-(1LL << 20));
7075 #ifndef CONFIG_64BIT
7076 	cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
7077 #endif
7078 #ifdef CONFIG_SMP
7079 	atomic64_set(&cfs_rq->decay_counter, 1);
7080 	atomic_long_set(&cfs_rq->removed_load, 0);
7081 #endif
7082 }
7083 
7084 #ifdef CONFIG_FAIR_GROUP_SCHED
7085 static void task_move_group_fair(struct task_struct *p, int on_rq)
7086 {
7087 	struct cfs_rq *cfs_rq;
7088 	/*
7089 	 * If the task was not on the rq at the time of this cgroup movement
7090 	 * it must have been asleep, sleeping tasks keep their ->vruntime
7091 	 * absolute on their old rq until wakeup (needed for the fair sleeper
7092 	 * bonus in place_entity()).
7093 	 *
7094 	 * If it was on the rq, we've just 'preempted' it, which does convert
7095 	 * ->vruntime to a relative base.
7096 	 *
7097 	 * Make sure both cases convert their relative position when migrating
7098 	 * to another cgroup's rq. This does somewhat interfere with the
7099 	 * fair sleeper stuff for the first placement, but who cares.
7100 	 */
7101 	/*
7102 	 * When !on_rq, vruntime of the task has usually NOT been normalized.
7103 	 * But there are some cases where it has already been normalized:
7104 	 *
7105 	 * - Moving a forked child which is waiting for being woken up by
7106 	 *   wake_up_new_task().
7107 	 * - Moving a task which has been woken up by try_to_wake_up() and
7108 	 *   waiting for actually being woken up by sched_ttwu_pending().
7109 	 *
7110 	 * To prevent boost or penalty in the new cfs_rq caused by delta
7111 	 * min_vruntime between the two cfs_rqs, we skip vruntime adjustment.
7112 	 */
7113 	if (!on_rq && (!p->se.sum_exec_runtime || p->state == TASK_WAKING))
7114 		on_rq = 1;
7115 
7116 	if (!on_rq)
7117 		p->se.vruntime -= cfs_rq_of(&p->se)->min_vruntime;
7118 	set_task_rq(p, task_cpu(p));
7119 	if (!on_rq) {
7120 		cfs_rq = cfs_rq_of(&p->se);
7121 		p->se.vruntime += cfs_rq->min_vruntime;
7122 #ifdef CONFIG_SMP
7123 		/*
7124 		 * migrate_task_rq_fair() will have removed our previous
7125 		 * contribution, but we must synchronize for ongoing future
7126 		 * decay.
7127 		 */
7128 		p->se.avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
7129 		cfs_rq->blocked_load_avg += p->se.avg.load_avg_contrib;
7130 #endif
7131 	}
7132 }
7133 
7134 void free_fair_sched_group(struct task_group *tg)
7135 {
7136 	int i;
7137 
7138 	destroy_cfs_bandwidth(tg_cfs_bandwidth(tg));
7139 
7140 	for_each_possible_cpu(i) {
7141 		if (tg->cfs_rq)
7142 			kfree(tg->cfs_rq[i]);
7143 		if (tg->se)
7144 			kfree(tg->se[i]);
7145 	}
7146 
7147 	kfree(tg->cfs_rq);
7148 	kfree(tg->se);
7149 }
7150 
7151 int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
7152 {
7153 	struct cfs_rq *cfs_rq;
7154 	struct sched_entity *se;
7155 	int i;
7156 
7157 	tg->cfs_rq = kzalloc(sizeof(cfs_rq) * nr_cpu_ids, GFP_KERNEL);
7158 	if (!tg->cfs_rq)
7159 		goto err;
7160 	tg->se = kzalloc(sizeof(se) * nr_cpu_ids, GFP_KERNEL);
7161 	if (!tg->se)
7162 		goto err;
7163 
7164 	tg->shares = NICE_0_LOAD;
7165 
7166 	init_cfs_bandwidth(tg_cfs_bandwidth(tg));
7167 
7168 	for_each_possible_cpu(i) {
7169 		cfs_rq = kzalloc_node(sizeof(struct cfs_rq),
7170 				      GFP_KERNEL, cpu_to_node(i));
7171 		if (!cfs_rq)
7172 			goto err;
7173 
7174 		se = kzalloc_node(sizeof(struct sched_entity),
7175 				  GFP_KERNEL, cpu_to_node(i));
7176 		if (!se)
7177 			goto err_free_rq;
7178 
7179 		init_cfs_rq(cfs_rq);
7180 		init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]);
7181 	}
7182 
7183 	return 1;
7184 
7185 err_free_rq:
7186 	kfree(cfs_rq);
7187 err:
7188 	return 0;
7189 }
7190 
7191 void unregister_fair_sched_group(struct task_group *tg, int cpu)
7192 {
7193 	struct rq *rq = cpu_rq(cpu);
7194 	unsigned long flags;
7195 
7196 	/*
7197 	* Only empty task groups can be destroyed; so we can speculatively
7198 	* check on_list without danger of it being re-added.
7199 	*/
7200 	if (!tg->cfs_rq[cpu]->on_list)
7201 		return;
7202 
7203 	raw_spin_lock_irqsave(&rq->lock, flags);
7204 	list_del_leaf_cfs_rq(tg->cfs_rq[cpu]);
7205 	raw_spin_unlock_irqrestore(&rq->lock, flags);
7206 }
7207 
7208 void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
7209 			struct sched_entity *se, int cpu,
7210 			struct sched_entity *parent)
7211 {
7212 	struct rq *rq = cpu_rq(cpu);
7213 
7214 	cfs_rq->tg = tg;
7215 	cfs_rq->rq = rq;
7216 	init_cfs_rq_runtime(cfs_rq);
7217 
7218 	tg->cfs_rq[cpu] = cfs_rq;
7219 	tg->se[cpu] = se;
7220 
7221 	/* se could be NULL for root_task_group */
7222 	if (!se)
7223 		return;
7224 
7225 	if (!parent)
7226 		se->cfs_rq = &rq->cfs;
7227 	else
7228 		se->cfs_rq = parent->my_q;
7229 
7230 	se->my_q = cfs_rq;
7231 	/* guarantee group entities always have weight */
7232 	update_load_set(&se->load, NICE_0_LOAD);
7233 	se->parent = parent;
7234 }
7235 
7236 static DEFINE_MUTEX(shares_mutex);
7237 
7238 int sched_group_set_shares(struct task_group *tg, unsigned long shares)
7239 {
7240 	int i;
7241 	unsigned long flags;
7242 
7243 	/*
7244 	 * We can't change the weight of the root cgroup.
7245 	 */
7246 	if (!tg->se[0])
7247 		return -EINVAL;
7248 
7249 	shares = clamp(shares, scale_load(MIN_SHARES), scale_load(MAX_SHARES));
7250 
7251 	mutex_lock(&shares_mutex);
7252 	if (tg->shares == shares)
7253 		goto done;
7254 
7255 	tg->shares = shares;
7256 	for_each_possible_cpu(i) {
7257 		struct rq *rq = cpu_rq(i);
7258 		struct sched_entity *se;
7259 
7260 		se = tg->se[i];
7261 		/* Propagate contribution to hierarchy */
7262 		raw_spin_lock_irqsave(&rq->lock, flags);
7263 
7264 		/* Possible calls to update_curr() need rq clock */
7265 		update_rq_clock(rq);
7266 		for_each_sched_entity(se)
7267 			update_cfs_shares(group_cfs_rq(se));
7268 		raw_spin_unlock_irqrestore(&rq->lock, flags);
7269 	}
7270 
7271 done:
7272 	mutex_unlock(&shares_mutex);
7273 	return 0;
7274 }
7275 #else /* CONFIG_FAIR_GROUP_SCHED */
7276 
7277 void free_fair_sched_group(struct task_group *tg) { }
7278 
7279 int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
7280 {
7281 	return 1;
7282 }
7283 
7284 void unregister_fair_sched_group(struct task_group *tg, int cpu) { }
7285 
7286 #endif /* CONFIG_FAIR_GROUP_SCHED */
7287 
7288 
7289 static unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
7290 {
7291 	struct sched_entity *se = &task->se;
7292 	unsigned int rr_interval = 0;
7293 
7294 	/*
7295 	 * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
7296 	 * idle runqueue:
7297 	 */
7298 	if (rq->cfs.load.weight)
7299 		rr_interval = NS_TO_JIFFIES(sched_slice(cfs_rq_of(se), se));
7300 
7301 	return rr_interval;
7302 }
7303 
7304 /*
7305  * All the scheduling class methods:
7306  */
7307 const struct sched_class fair_sched_class = {
7308 	.next			= &idle_sched_class,
7309 	.enqueue_task		= enqueue_task_fair,
7310 	.dequeue_task		= dequeue_task_fair,
7311 	.yield_task		= yield_task_fair,
7312 	.yield_to_task		= yield_to_task_fair,
7313 
7314 	.check_preempt_curr	= check_preempt_wakeup,
7315 
7316 	.pick_next_task		= pick_next_task_fair,
7317 	.put_prev_task		= put_prev_task_fair,
7318 
7319 #ifdef CONFIG_SMP
7320 	.select_task_rq		= select_task_rq_fair,
7321 	.migrate_task_rq	= migrate_task_rq_fair,
7322 
7323 	.rq_online		= rq_online_fair,
7324 	.rq_offline		= rq_offline_fair,
7325 
7326 	.task_waking		= task_waking_fair,
7327 #endif
7328 
7329 	.set_curr_task          = set_curr_task_fair,
7330 	.task_tick		= task_tick_fair,
7331 	.task_fork		= task_fork_fair,
7332 
7333 	.prio_changed		= prio_changed_fair,
7334 	.switched_from		= switched_from_fair,
7335 	.switched_to		= switched_to_fair,
7336 
7337 	.get_rr_interval	= get_rr_interval_fair,
7338 
7339 #ifdef CONFIG_FAIR_GROUP_SCHED
7340 	.task_move_group	= task_move_group_fair,
7341 #endif
7342 };
7343 
7344 #ifdef CONFIG_SCHED_DEBUG
7345 void print_cfs_stats(struct seq_file *m, int cpu)
7346 {
7347 	struct cfs_rq *cfs_rq;
7348 
7349 	rcu_read_lock();
7350 	for_each_leaf_cfs_rq(cpu_rq(cpu), cfs_rq)
7351 		print_cfs_rq(m, cpu, cfs_rq);
7352 	rcu_read_unlock();
7353 }
7354 #endif
7355 
7356 __init void init_sched_fair_class(void)
7357 {
7358 #ifdef CONFIG_SMP
7359 	open_softirq(SCHED_SOFTIRQ, run_rebalance_domains);
7360 
7361 #ifdef CONFIG_NO_HZ_COMMON
7362 	nohz.next_balance = jiffies;
7363 	zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
7364 	cpu_notifier(sched_ilb_notifier, 0);
7365 #endif
7366 #endif /* SMP */
7367 
7368 }
7369