1/*
2 *  kernel/sched/core.c
3 *
4 *  Kernel scheduler and related syscalls
5 *
6 *  Copyright (C) 1991-2002  Linus Torvalds
7 *
8 *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and
9 *		make semaphores SMP safe
10 *  1998-11-19	Implemented schedule_timeout() and related stuff
11 *		by Andrea Arcangeli
12 *  2002-01-04	New ultra-scalable O(1) scheduler by Ingo Molnar:
13 *		hybrid priority-list and round-robin design with
14 *		an array-switch method of distributing timeslices
15 *		and per-CPU runqueues.  Cleanups and useful suggestions
16 *		by Davide Libenzi, preemptible kernel bits by Robert Love.
17 *  2003-09-03	Interactivity tuning by Con Kolivas.
18 *  2004-04-02	Scheduler domains code by Nick Piggin
19 *  2007-04-15  Work begun on replacing all interactivity tuning with a
20 *              fair scheduling design by Con Kolivas.
21 *  2007-05-05  Load balancing (smp-nice) and other improvements
22 *              by Peter Williams
23 *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith
24 *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
25 *  2007-11-29  RT balancing improvements by Steven Rostedt, Gregory Haskins,
26 *              Thomas Gleixner, Mike Kravetz
27 */
28
29#include <linux/mm.h>
30#include <linux/module.h>
31#include <linux/nmi.h>
32#include <linux/init.h>
33#include <linux/uaccess.h>
34#include <linux/highmem.h>
35#include <asm/mmu_context.h>
36#include <linux/interrupt.h>
37#include <linux/capability.h>
38#include <linux/completion.h>
39#include <linux/kernel_stat.h>
40#include <linux/debug_locks.h>
41#include <linux/perf_event.h>
42#include <linux/security.h>
43#include <linux/notifier.h>
44#include <linux/profile.h>
45#include <linux/freezer.h>
46#include <linux/vmalloc.h>
47#include <linux/blkdev.h>
48#include <linux/delay.h>
49#include <linux/pid_namespace.h>
50#include <linux/smp.h>
51#include <linux/threads.h>
52#include <linux/timer.h>
53#include <linux/rcupdate.h>
54#include <linux/cpu.h>
55#include <linux/cpuset.h>
56#include <linux/percpu.h>
57#include <linux/proc_fs.h>
58#include <linux/seq_file.h>
59#include <linux/sysctl.h>
60#include <linux/syscalls.h>
61#include <linux/times.h>
62#include <linux/tsacct_kern.h>
63#include <linux/kprobes.h>
64#include <linux/delayacct.h>
65#include <linux/unistd.h>
66#include <linux/pagemap.h>
67#include <linux/hrtimer.h>
68#include <linux/tick.h>
69#include <linux/debugfs.h>
70#include <linux/ctype.h>
71#include <linux/ftrace.h>
72#include <linux/slab.h>
73#include <linux/init_task.h>
74#include <linux/binfmts.h>
75#include <linux/context_tracking.h>
76#include <linux/compiler.h>
77
78#include <asm/switch_to.h>
79#include <asm/tlb.h>
80#include <asm/irq_regs.h>
81#include <asm/mutex.h>
82#ifdef CONFIG_PARAVIRT
83#include <asm/paravirt.h>
84#endif
85
86#include "sched.h"
87#include "../workqueue_internal.h"
88#include "../smpboot.h"
89
90#define CREATE_TRACE_POINTS
91#include <trace/events/sched.h>
92
93void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
94{
95	unsigned long delta;
96	ktime_t soft, hard, now;
97
98	for (;;) {
99		if (hrtimer_active(period_timer))
100			break;
101
102		now = hrtimer_cb_get_time(period_timer);
103		hrtimer_forward(period_timer, now, period);
104
105		soft = hrtimer_get_softexpires(period_timer);
106		hard = hrtimer_get_expires(period_timer);
107		delta = ktime_to_ns(ktime_sub(hard, soft));
108		__hrtimer_start_range_ns(period_timer, soft, delta,
109					 HRTIMER_MODE_ABS_PINNED, 0);
110	}
111}
112
113DEFINE_MUTEX(sched_domains_mutex);
114DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
115
116static void update_rq_clock_task(struct rq *rq, s64 delta);
117
118void update_rq_clock(struct rq *rq)
119{
120	s64 delta;
121
122	if (rq->skip_clock_update > 0)
123		return;
124
125	delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
126	if (delta < 0)
127		return;
128	rq->clock += delta;
129	update_rq_clock_task(rq, delta);
130}
131
132/*
133 * Debugging: various feature bits
134 */
135
136#define SCHED_FEAT(name, enabled)	\
137	(1UL << __SCHED_FEAT_##name) * enabled |
138
139const_debug unsigned int sysctl_sched_features =
140#include "features.h"
141	0;
142
143#undef SCHED_FEAT
144
145#ifdef CONFIG_SCHED_DEBUG
146#define SCHED_FEAT(name, enabled)	\
147	#name ,
148
149static const char * const sched_feat_names[] = {
150#include "features.h"
151};
152
153#undef SCHED_FEAT
154
155static int sched_feat_show(struct seq_file *m, void *v)
156{
157	int i;
158
159	for (i = 0; i < __SCHED_FEAT_NR; i++) {
160		if (!(sysctl_sched_features & (1UL << i)))
161			seq_puts(m, "NO_");
162		seq_printf(m, "%s ", sched_feat_names[i]);
163	}
164	seq_puts(m, "\n");
165
166	return 0;
167}
168
169#ifdef HAVE_JUMP_LABEL
170
171#define jump_label_key__true  STATIC_KEY_INIT_TRUE
172#define jump_label_key__false STATIC_KEY_INIT_FALSE
173
174#define SCHED_FEAT(name, enabled)	\
175	jump_label_key__##enabled ,
176
177struct static_key sched_feat_keys[__SCHED_FEAT_NR] = {
178#include "features.h"
179};
180
181#undef SCHED_FEAT
182
183static void sched_feat_disable(int i)
184{
185	if (static_key_enabled(&sched_feat_keys[i]))
186		static_key_slow_dec(&sched_feat_keys[i]);
187}
188
189static void sched_feat_enable(int i)
190{
191	if (!static_key_enabled(&sched_feat_keys[i]))
192		static_key_slow_inc(&sched_feat_keys[i]);
193}
194#else
195static void sched_feat_disable(int i) { };
196static void sched_feat_enable(int i) { };
197#endif /* HAVE_JUMP_LABEL */
198
199static int sched_feat_set(char *cmp)
200{
201	int i;
202	int neg = 0;
203
204	if (strncmp(cmp, "NO_", 3) == 0) {
205		neg = 1;
206		cmp += 3;
207	}
208
209	for (i = 0; i < __SCHED_FEAT_NR; i++) {
210		if (strcmp(cmp, sched_feat_names[i]) == 0) {
211			if (neg) {
212				sysctl_sched_features &= ~(1UL << i);
213				sched_feat_disable(i);
214			} else {
215				sysctl_sched_features |= (1UL << i);
216				sched_feat_enable(i);
217			}
218			break;
219		}
220	}
221
222	return i;
223}
224
225static ssize_t
226sched_feat_write(struct file *filp, const char __user *ubuf,
227		size_t cnt, loff_t *ppos)
228{
229	char buf[64];
230	char *cmp;
231	int i;
232	struct inode *inode;
233
234	if (cnt > 63)
235		cnt = 63;
236
237	if (copy_from_user(&buf, ubuf, cnt))
238		return -EFAULT;
239
240	buf[cnt] = 0;
241	cmp = strstrip(buf);
242
243	/* Ensure the static_key remains in a consistent state */
244	inode = file_inode(filp);
245	mutex_lock(&inode->i_mutex);
246	i = sched_feat_set(cmp);
247	mutex_unlock(&inode->i_mutex);
248	if (i == __SCHED_FEAT_NR)
249		return -EINVAL;
250
251	*ppos += cnt;
252
253	return cnt;
254}
255
256static int sched_feat_open(struct inode *inode, struct file *filp)
257{
258	return single_open(filp, sched_feat_show, NULL);
259}
260
261static const struct file_operations sched_feat_fops = {
262	.open		= sched_feat_open,
263	.write		= sched_feat_write,
264	.read		= seq_read,
265	.llseek		= seq_lseek,
266	.release	= single_release,
267};
268
269static __init int sched_init_debug(void)
270{
271	debugfs_create_file("sched_features", 0644, NULL, NULL,
272			&sched_feat_fops);
273
274	return 0;
275}
276late_initcall(sched_init_debug);
277#endif /* CONFIG_SCHED_DEBUG */
278
279/*
280 * Number of tasks to iterate in a single balance run.
281 * Limited because this is done with IRQs disabled.
282 */
283const_debug unsigned int sysctl_sched_nr_migrate = 32;
284
285/*
286 * period over which we average the RT time consumption, measured
287 * in ms.
288 *
289 * default: 1s
290 */
291const_debug unsigned int sysctl_sched_time_avg = MSEC_PER_SEC;
292
293/*
294 * period over which we measure -rt task cpu usage in us.
295 * default: 1s
296 */
297unsigned int sysctl_sched_rt_period = 1000000;
298
299__read_mostly int scheduler_running;
300
301/*
302 * part of the period that we allow rt tasks to run in us.
303 * default: 0.95s
304 */
305int sysctl_sched_rt_runtime = 950000;
306
307/*
308 * __task_rq_lock - lock the rq @p resides on.
309 */
310static inline struct rq *__task_rq_lock(struct task_struct *p)
311	__acquires(rq->lock)
312{
313	struct rq *rq;
314
315	lockdep_assert_held(&p->pi_lock);
316
317	for (;;) {
318		rq = task_rq(p);
319		raw_spin_lock(&rq->lock);
320		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
321			return rq;
322		raw_spin_unlock(&rq->lock);
323
324		while (unlikely(task_on_rq_migrating(p)))
325			cpu_relax();
326	}
327}
328
329/*
330 * task_rq_lock - lock p->pi_lock and lock the rq @p resides on.
331 */
332static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
333	__acquires(p->pi_lock)
334	__acquires(rq->lock)
335{
336	struct rq *rq;
337
338	for (;;) {
339		raw_spin_lock_irqsave(&p->pi_lock, *flags);
340		rq = task_rq(p);
341		raw_spin_lock(&rq->lock);
342		if (likely(rq == task_rq(p) && !task_on_rq_migrating(p)))
343			return rq;
344		raw_spin_unlock(&rq->lock);
345		raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
346
347		while (unlikely(task_on_rq_migrating(p)))
348			cpu_relax();
349	}
350}
351
352static void __task_rq_unlock(struct rq *rq)
353	__releases(rq->lock)
354{
355	raw_spin_unlock(&rq->lock);
356}
357
358static inline void
359task_rq_unlock(struct rq *rq, struct task_struct *p, unsigned long *flags)
360	__releases(rq->lock)
361	__releases(p->pi_lock)
362{
363	raw_spin_unlock(&rq->lock);
364	raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
365}
366
367/*
368 * this_rq_lock - lock this runqueue and disable interrupts.
369 */
370static struct rq *this_rq_lock(void)
371	__acquires(rq->lock)
372{
373	struct rq *rq;
374
375	local_irq_disable();
376	rq = this_rq();
377	raw_spin_lock(&rq->lock);
378
379	return rq;
380}
381
382#ifdef CONFIG_SCHED_HRTICK
383/*
384 * Use HR-timers to deliver accurate preemption points.
385 */
386
387static void hrtick_clear(struct rq *rq)
388{
389	if (hrtimer_active(&rq->hrtick_timer))
390		hrtimer_cancel(&rq->hrtick_timer);
391}
392
393/*
394 * High-resolution timer tick.
395 * Runs from hardirq context with interrupts disabled.
396 */
397static enum hrtimer_restart hrtick(struct hrtimer *timer)
398{
399	struct rq *rq = container_of(timer, struct rq, hrtick_timer);
400
401	WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());
402
403	raw_spin_lock(&rq->lock);
404	update_rq_clock(rq);
405	rq->curr->sched_class->task_tick(rq, rq->curr, 1);
406	raw_spin_unlock(&rq->lock);
407
408	return HRTIMER_NORESTART;
409}
410
411#ifdef CONFIG_SMP
412
413static int __hrtick_restart(struct rq *rq)
414{
415	struct hrtimer *timer = &rq->hrtick_timer;
416	ktime_t time = hrtimer_get_softexpires(timer);
417
418	return __hrtimer_start_range_ns(timer, time, 0, HRTIMER_MODE_ABS_PINNED, 0);
419}
420
421/*
422 * called from hardirq (IPI) context
423 */
424static void __hrtick_start(void *arg)
425{
426	struct rq *rq = arg;
427
428	raw_spin_lock(&rq->lock);
429	__hrtick_restart(rq);
430	rq->hrtick_csd_pending = 0;
431	raw_spin_unlock(&rq->lock);
432}
433
434/*
435 * Called to set the hrtick timer state.
436 *
437 * called with rq->lock held and irqs disabled
438 */
439void hrtick_start(struct rq *rq, u64 delay)
440{
441	struct hrtimer *timer = &rq->hrtick_timer;
442	ktime_t time;
443	s64 delta;
444
445	/*
446	 * Don't schedule slices shorter than 10000ns, that just
447	 * doesn't make sense and can cause timer DoS.
448	 */
449	delta = max_t(s64, delay, 10000LL);
450	time = ktime_add_ns(timer->base->get_time(), delta);
451
452	hrtimer_set_expires(timer, time);
453
454	if (rq == this_rq()) {
455		__hrtick_restart(rq);
456	} else if (!rq->hrtick_csd_pending) {
457		smp_call_function_single_async(cpu_of(rq), &rq->hrtick_csd);
458		rq->hrtick_csd_pending = 1;
459	}
460}
461
462static int
463hotplug_hrtick(struct notifier_block *nfb, unsigned long action, void *hcpu)
464{
465	int cpu = (int)(long)hcpu;
466
467	switch (action) {
468	case CPU_UP_CANCELED:
469	case CPU_UP_CANCELED_FROZEN:
470	case CPU_DOWN_PREPARE:
471	case CPU_DOWN_PREPARE_FROZEN:
472	case CPU_DEAD:
473	case CPU_DEAD_FROZEN:
474		hrtick_clear(cpu_rq(cpu));
475		return NOTIFY_OK;
476	}
477
478	return NOTIFY_DONE;
479}
480
481static __init void init_hrtick(void)
482{
483	hotcpu_notifier(hotplug_hrtick, 0);
484}
485#else
486/*
487 * Called to set the hrtick timer state.
488 *
489 * called with rq->lock held and irqs disabled
490 */
491void hrtick_start(struct rq *rq, u64 delay)
492{
493	__hrtimer_start_range_ns(&rq->hrtick_timer, ns_to_ktime(delay), 0,
494			HRTIMER_MODE_REL_PINNED, 0);
495}
496
497static inline void init_hrtick(void)
498{
499}
500#endif /* CONFIG_SMP */
501
502static void init_rq_hrtick(struct rq *rq)
503{
504#ifdef CONFIG_SMP
505	rq->hrtick_csd_pending = 0;
506
507	rq->hrtick_csd.flags = 0;
508	rq->hrtick_csd.func = __hrtick_start;
509	rq->hrtick_csd.info = rq;
510#endif
511
512	hrtimer_init(&rq->hrtick_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
513	rq->hrtick_timer.function = hrtick;
514}
515#else	/* CONFIG_SCHED_HRTICK */
516static inline void hrtick_clear(struct rq *rq)
517{
518}
519
520static inline void init_rq_hrtick(struct rq *rq)
521{
522}
523
524static inline void init_hrtick(void)
525{
526}
527#endif	/* CONFIG_SCHED_HRTICK */
528
529/*
530 * cmpxchg based fetch_or, macro so it works for different integer types
531 */
532#define fetch_or(ptr, val)						\
533({	typeof(*(ptr)) __old, __val = *(ptr);				\
534 	for (;;) {							\
535 		__old = cmpxchg((ptr), __val, __val | (val));		\
536 		if (__old == __val)					\
537 			break;						\
538 		__val = __old;						\
539 	}								\
540 	__old;								\
541})
542
543#if defined(CONFIG_SMP) && defined(TIF_POLLING_NRFLAG)
544/*
545 * Atomically set TIF_NEED_RESCHED and test for TIF_POLLING_NRFLAG,
546 * this avoids any races wrt polling state changes and thereby avoids
547 * spurious IPIs.
548 */
549static bool set_nr_and_not_polling(struct task_struct *p)
550{
551	struct thread_info *ti = task_thread_info(p);
552	return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
553}
554
555/*
556 * Atomically set TIF_NEED_RESCHED if TIF_POLLING_NRFLAG is set.
557 *
558 * If this returns true, then the idle task promises to call
559 * sched_ttwu_pending() and reschedule soon.
560 */
561static bool set_nr_if_polling(struct task_struct *p)
562{
563	struct thread_info *ti = task_thread_info(p);
564	typeof(ti->flags) old, val = ACCESS_ONCE(ti->flags);
565
566	for (;;) {
567		if (!(val & _TIF_POLLING_NRFLAG))
568			return false;
569		if (val & _TIF_NEED_RESCHED)
570			return true;
571		old = cmpxchg(&ti->flags, val, val | _TIF_NEED_RESCHED);
572		if (old == val)
573			break;
574		val = old;
575	}
576	return true;
577}
578
579#else
580static bool set_nr_and_not_polling(struct task_struct *p)
581{
582	set_tsk_need_resched(p);
583	return true;
584}
585
586#ifdef CONFIG_SMP
587static bool set_nr_if_polling(struct task_struct *p)
588{
589	return false;
590}
591#endif
592#endif
593
594/*
595 * resched_curr - mark rq's current task 'to be rescheduled now'.
596 *
597 * On UP this means the setting of the need_resched flag, on SMP it
598 * might also involve a cross-CPU call to trigger the scheduler on
599 * the target CPU.
600 */
601void resched_curr(struct rq *rq)
602{
603	struct task_struct *curr = rq->curr;
604	int cpu;
605
606	lockdep_assert_held(&rq->lock);
607
608	if (test_tsk_need_resched(curr))
609		return;
610
611	cpu = cpu_of(rq);
612
613	if (cpu == smp_processor_id()) {
614		set_tsk_need_resched(curr);
615		set_preempt_need_resched();
616		return;
617	}
618
619	if (set_nr_and_not_polling(curr))
620		smp_send_reschedule(cpu);
621	else
622		trace_sched_wake_idle_without_ipi(cpu);
623}
624
625void resched_cpu(int cpu)
626{
627	struct rq *rq = cpu_rq(cpu);
628	unsigned long flags;
629
630	if (!raw_spin_trylock_irqsave(&rq->lock, flags))
631		return;
632	resched_curr(rq);
633	raw_spin_unlock_irqrestore(&rq->lock, flags);
634}
635
636#ifdef CONFIG_SMP
637#ifdef CONFIG_NO_HZ_COMMON
638/*
639 * In the semi idle case, use the nearest busy cpu for migrating timers
640 * from an idle cpu.  This is good for power-savings.
641 *
642 * We don't do similar optimization for completely idle system, as
643 * selecting an idle cpu will add more delays to the timers than intended
644 * (as that cpu's timer base may not be uptodate wrt jiffies etc).
645 */
646int get_nohz_timer_target(int pinned)
647{
648	int cpu = smp_processor_id();
649	int i;
650	struct sched_domain *sd;
651
652	if (pinned || !get_sysctl_timer_migration() || !idle_cpu(cpu))
653		return cpu;
654
655	rcu_read_lock();
656	for_each_domain(cpu, sd) {
657		for_each_cpu(i, sched_domain_span(sd)) {
658			if (!idle_cpu(i)) {
659				cpu = i;
660				goto unlock;
661			}
662		}
663	}
664unlock:
665	rcu_read_unlock();
666	return cpu;
667}
668/*
669 * When add_timer_on() enqueues a timer into the timer wheel of an
670 * idle CPU then this timer might expire before the next timer event
671 * which is scheduled to wake up that CPU. In case of a completely
672 * idle system the next event might even be infinite time into the
673 * future. wake_up_idle_cpu() ensures that the CPU is woken up and
674 * leaves the inner idle loop so the newly added timer is taken into
675 * account when the CPU goes back to idle and evaluates the timer
676 * wheel for the next timer event.
677 */
678static void wake_up_idle_cpu(int cpu)
679{
680	struct rq *rq = cpu_rq(cpu);
681
682	if (cpu == smp_processor_id())
683		return;
684
685	if (set_nr_and_not_polling(rq->idle))
686		smp_send_reschedule(cpu);
687	else
688		trace_sched_wake_idle_without_ipi(cpu);
689}
690
691static bool wake_up_full_nohz_cpu(int cpu)
692{
693	/*
694	 * We just need the target to call irq_exit() and re-evaluate
695	 * the next tick. The nohz full kick at least implies that.
696	 * If needed we can still optimize that later with an
697	 * empty IRQ.
698	 */
699	if (tick_nohz_full_cpu(cpu)) {
700		if (cpu != smp_processor_id() ||
701		    tick_nohz_tick_stopped())
702			tick_nohz_full_kick_cpu(cpu);
703		return true;
704	}
705
706	return false;
707}
708
709void wake_up_nohz_cpu(int cpu)
710{
711	if (!wake_up_full_nohz_cpu(cpu))
712		wake_up_idle_cpu(cpu);
713}
714
715static inline bool got_nohz_idle_kick(void)
716{
717	int cpu = smp_processor_id();
718
719	if (!test_bit(NOHZ_BALANCE_KICK, nohz_flags(cpu)))
720		return false;
721
722	if (idle_cpu(cpu) && !need_resched())
723		return true;
724
725	/*
726	 * We can't run Idle Load Balance on this CPU for this time so we
727	 * cancel it and clear NOHZ_BALANCE_KICK
728	 */
729	clear_bit(NOHZ_BALANCE_KICK, nohz_flags(cpu));
730	return false;
731}
732
733#else /* CONFIG_NO_HZ_COMMON */
734
735static inline bool got_nohz_idle_kick(void)
736{
737	return false;
738}
739
740#endif /* CONFIG_NO_HZ_COMMON */
741
742#ifdef CONFIG_NO_HZ_FULL
743bool sched_can_stop_tick(void)
744{
745	/*
746	 * More than one running task need preemption.
747	 * nr_running update is assumed to be visible
748	 * after IPI is sent from wakers.
749	 */
750	if (this_rq()->nr_running > 1)
751		return false;
752
753	return true;
754}
755#endif /* CONFIG_NO_HZ_FULL */
756
757void sched_avg_update(struct rq *rq)
758{
759	s64 period = sched_avg_period();
760
761	while ((s64)(rq_clock(rq) - rq->age_stamp) > period) {
762		/*
763		 * Inline assembly required to prevent the compiler
764		 * optimising this loop into a divmod call.
765		 * See __iter_div_u64_rem() for another example of this.
766		 */
767		asm("" : "+rm" (rq->age_stamp));
768		rq->age_stamp += period;
769		rq->rt_avg /= 2;
770	}
771}
772
773#endif /* CONFIG_SMP */
774
775#if defined(CONFIG_RT_GROUP_SCHED) || (defined(CONFIG_FAIR_GROUP_SCHED) && \
776			(defined(CONFIG_SMP) || defined(CONFIG_CFS_BANDWIDTH)))
777/*
778 * Iterate task_group tree rooted at *from, calling @down when first entering a
779 * node and @up when leaving it for the final time.
780 *
781 * Caller must hold rcu_lock or sufficient equivalent.
782 */
783int walk_tg_tree_from(struct task_group *from,
784			     tg_visitor down, tg_visitor up, void *data)
785{
786	struct task_group *parent, *child;
787	int ret;
788
789	parent = from;
790
791down:
792	ret = (*down)(parent, data);
793	if (ret)
794		goto out;
795	list_for_each_entry_rcu(child, &parent->children, siblings) {
796		parent = child;
797		goto down;
798
799up:
800		continue;
801	}
802	ret = (*up)(parent, data);
803	if (ret || parent == from)
804		goto out;
805
806	child = parent;
807	parent = parent->parent;
808	if (parent)
809		goto up;
810out:
811	return ret;
812}
813
814int tg_nop(struct task_group *tg, void *data)
815{
816	return 0;
817}
818#endif
819
820static void set_load_weight(struct task_struct *p)
821{
822	int prio = p->static_prio - MAX_RT_PRIO;
823	struct load_weight *load = &p->se.load;
824
825	/*
826	 * SCHED_IDLE tasks get minimal weight:
827	 */
828	if (p->policy == SCHED_IDLE) {
829		load->weight = scale_load(WEIGHT_IDLEPRIO);
830		load->inv_weight = WMULT_IDLEPRIO;
831		return;
832	}
833
834	load->weight = scale_load(prio_to_weight[prio]);
835	load->inv_weight = prio_to_wmult[prio];
836}
837
838static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
839{
840	update_rq_clock(rq);
841	sched_info_queued(rq, p);
842	p->sched_class->enqueue_task(rq, p, flags);
843}
844
845static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
846{
847	update_rq_clock(rq);
848	sched_info_dequeued(rq, p);
849	p->sched_class->dequeue_task(rq, p, flags);
850}
851
852void activate_task(struct rq *rq, struct task_struct *p, int flags)
853{
854	if (task_contributes_to_load(p))
855		rq->nr_uninterruptible--;
856
857	enqueue_task(rq, p, flags);
858}
859
860void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
861{
862	if (task_contributes_to_load(p))
863		rq->nr_uninterruptible++;
864
865	dequeue_task(rq, p, flags);
866}
867
868static void update_rq_clock_task(struct rq *rq, s64 delta)
869{
870/*
871 * In theory, the compile should just see 0 here, and optimize out the call
872 * to sched_rt_avg_update. But I don't trust it...
873 */
874#if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
875	s64 steal = 0, irq_delta = 0;
876#endif
877#ifdef CONFIG_IRQ_TIME_ACCOUNTING
878	irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;
879
880	/*
881	 * Since irq_time is only updated on {soft,}irq_exit, we might run into
882	 * this case when a previous update_rq_clock() happened inside a
883	 * {soft,}irq region.
884	 *
885	 * When this happens, we stop ->clock_task and only update the
886	 * prev_irq_time stamp to account for the part that fit, so that a next
887	 * update will consume the rest. This ensures ->clock_task is
888	 * monotonic.
889	 *
890	 * It does however cause some slight miss-attribution of {soft,}irq
891	 * time, a more accurate solution would be to update the irq_time using
892	 * the current rq->clock timestamp, except that would require using
893	 * atomic ops.
894	 */
895	if (irq_delta > delta)
896		irq_delta = delta;
897
898	rq->prev_irq_time += irq_delta;
899	delta -= irq_delta;
900#endif
901#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
902	if (static_key_false((&paravirt_steal_rq_enabled))) {
903		steal = paravirt_steal_clock(cpu_of(rq));
904		steal -= rq->prev_steal_time_rq;
905
906		if (unlikely(steal > delta))
907			steal = delta;
908
909		rq->prev_steal_time_rq += steal;
910		delta -= steal;
911	}
912#endif
913
914	rq->clock_task += delta;
915
916#if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
917	if ((irq_delta + steal) && sched_feat(NONTASK_CAPACITY))
918		sched_rt_avg_update(rq, irq_delta + steal);
919#endif
920}
921
922void sched_set_stop_task(int cpu, struct task_struct *stop)
923{
924	struct sched_param param = { .sched_priority = MAX_RT_PRIO - 1 };
925	struct task_struct *old_stop = cpu_rq(cpu)->stop;
926
927	if (stop) {
928		/*
929		 * Make it appear like a SCHED_FIFO task, its something
930		 * userspace knows about and won't get confused about.
931		 *
932		 * Also, it will make PI more or less work without too
933		 * much confusion -- but then, stop work should not
934		 * rely on PI working anyway.
935		 */
936		sched_setscheduler_nocheck(stop, SCHED_FIFO, &param);
937
938		stop->sched_class = &stop_sched_class;
939	}
940
941	cpu_rq(cpu)->stop = stop;
942
943	if (old_stop) {
944		/*
945		 * Reset it back to a normal scheduling class so that
946		 * it can die in pieces.
947		 */
948		old_stop->sched_class = &rt_sched_class;
949	}
950}
951
952/*
953 * __normal_prio - return the priority that is based on the static prio
954 */
955static inline int __normal_prio(struct task_struct *p)
956{
957	return p->static_prio;
958}
959
960/*
961 * Calculate the expected normal priority: i.e. priority
962 * without taking RT-inheritance into account. Might be
963 * boosted by interactivity modifiers. Changes upon fork,
964 * setprio syscalls, and whenever the interactivity
965 * estimator recalculates.
966 */
967static inline int normal_prio(struct task_struct *p)
968{
969	int prio;
970
971	if (task_has_dl_policy(p))
972		prio = MAX_DL_PRIO-1;
973	else if (task_has_rt_policy(p))
974		prio = MAX_RT_PRIO-1 - p->rt_priority;
975	else
976		prio = __normal_prio(p);
977	return prio;
978}
979
980/*
981 * Calculate the current priority, i.e. the priority
982 * taken into account by the scheduler. This value might
983 * be boosted by RT tasks, or might be boosted by
984 * interactivity modifiers. Will be RT if the task got
985 * RT-boosted. If not then it returns p->normal_prio.
986 */
987static int effective_prio(struct task_struct *p)
988{
989	p->normal_prio = normal_prio(p);
990	/*
991	 * If we are RT tasks or we were boosted to RT priority,
992	 * keep the priority unchanged. Otherwise, update priority
993	 * to the normal priority:
994	 */
995	if (!rt_prio(p->prio))
996		return p->normal_prio;
997	return p->prio;
998}
999
1000/**
1001 * task_curr - is this task currently executing on a CPU?
1002 * @p: the task in question.
1003 *
1004 * Return: 1 if the task is currently executing. 0 otherwise.
1005 */
1006inline int task_curr(const struct task_struct *p)
1007{
1008	return cpu_curr(task_cpu(p)) == p;
1009}
1010
1011static inline void check_class_changed(struct rq *rq, struct task_struct *p,
1012				       const struct sched_class *prev_class,
1013				       int oldprio)
1014{
1015	if (prev_class != p->sched_class) {
1016		if (prev_class->switched_from)
1017			prev_class->switched_from(rq, p);
1018		p->sched_class->switched_to(rq, p);
1019	} else if (oldprio != p->prio || dl_task(p))
1020		p->sched_class->prio_changed(rq, p, oldprio);
1021}
1022
1023void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
1024{
1025	const struct sched_class *class;
1026
1027	if (p->sched_class == rq->curr->sched_class) {
1028		rq->curr->sched_class->check_preempt_curr(rq, p, flags);
1029	} else {
1030		for_each_class(class) {
1031			if (class == rq->curr->sched_class)
1032				break;
1033			if (class == p->sched_class) {
1034				resched_curr(rq);
1035				break;
1036			}
1037		}
1038	}
1039
1040	/*
1041	 * A queue event has occurred, and we're going to schedule.  In
1042	 * this case, we can save a useless back to back clock update.
1043	 */
1044	if (task_on_rq_queued(rq->curr) && test_tsk_need_resched(rq->curr))
1045		rq->skip_clock_update = 1;
1046}
1047
1048#ifdef CONFIG_SMP
1049void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
1050{
1051#ifdef CONFIG_SCHED_DEBUG
1052	/*
1053	 * We should never call set_task_cpu() on a blocked task,
1054	 * ttwu() will sort out the placement.
1055	 */
1056	WARN_ON_ONCE(p->state != TASK_RUNNING && p->state != TASK_WAKING &&
1057			!(task_preempt_count(p) & PREEMPT_ACTIVE));
1058
1059#ifdef CONFIG_LOCKDEP
1060	/*
1061	 * The caller should hold either p->pi_lock or rq->lock, when changing
1062	 * a task's CPU. ->pi_lock for waking tasks, rq->lock for runnable tasks.
1063	 *
1064	 * sched_move_task() holds both and thus holding either pins the cgroup,
1065	 * see task_group().
1066	 *
1067	 * Furthermore, all task_rq users should acquire both locks, see
1068	 * task_rq_lock().
1069	 */
1070	WARN_ON_ONCE(debug_locks && !(lockdep_is_held(&p->pi_lock) ||
1071				      lockdep_is_held(&task_rq(p)->lock)));
1072#endif
1073#endif
1074
1075	trace_sched_migrate_task(p, new_cpu);
1076
1077	if (task_cpu(p) != new_cpu) {
1078		if (p->sched_class->migrate_task_rq)
1079			p->sched_class->migrate_task_rq(p, new_cpu);
1080		p->se.nr_migrations++;
1081		perf_sw_event(PERF_COUNT_SW_CPU_MIGRATIONS, 1, NULL, 0);
1082	}
1083
1084	__set_task_cpu(p, new_cpu);
1085}
1086
1087static void __migrate_swap_task(struct task_struct *p, int cpu)
1088{
1089	if (task_on_rq_queued(p)) {
1090		struct rq *src_rq, *dst_rq;
1091
1092		src_rq = task_rq(p);
1093		dst_rq = cpu_rq(cpu);
1094
1095		deactivate_task(src_rq, p, 0);
1096		set_task_cpu(p, cpu);
1097		activate_task(dst_rq, p, 0);
1098		check_preempt_curr(dst_rq, p, 0);
1099	} else {
1100		/*
1101		 * Task isn't running anymore; make it appear like we migrated
1102		 * it before it went to sleep. This means on wakeup we make the
1103		 * previous cpu our targer instead of where it really is.
1104		 */
1105		p->wake_cpu = cpu;
1106	}
1107}
1108
1109struct migration_swap_arg {
1110	struct task_struct *src_task, *dst_task;
1111	int src_cpu, dst_cpu;
1112};
1113
1114static int migrate_swap_stop(void *data)
1115{
1116	struct migration_swap_arg *arg = data;
1117	struct rq *src_rq, *dst_rq;
1118	int ret = -EAGAIN;
1119
1120	src_rq = cpu_rq(arg->src_cpu);
1121	dst_rq = cpu_rq(arg->dst_cpu);
1122
1123	double_raw_lock(&arg->src_task->pi_lock,
1124			&arg->dst_task->pi_lock);
1125	double_rq_lock(src_rq, dst_rq);
1126	if (task_cpu(arg->dst_task) != arg->dst_cpu)
1127		goto unlock;
1128
1129	if (task_cpu(arg->src_task) != arg->src_cpu)
1130		goto unlock;
1131
1132	if (!cpumask_test_cpu(arg->dst_cpu, tsk_cpus_allowed(arg->src_task)))
1133		goto unlock;
1134
1135	if (!cpumask_test_cpu(arg->src_cpu, tsk_cpus_allowed(arg->dst_task)))
1136		goto unlock;
1137
1138	__migrate_swap_task(arg->src_task, arg->dst_cpu);
1139	__migrate_swap_task(arg->dst_task, arg->src_cpu);
1140
1141	ret = 0;
1142
1143unlock:
1144	double_rq_unlock(src_rq, dst_rq);
1145	raw_spin_unlock(&arg->dst_task->pi_lock);
1146	raw_spin_unlock(&arg->src_task->pi_lock);
1147
1148	return ret;
1149}
1150
1151/*
1152 * Cross migrate two tasks
1153 */
1154int migrate_swap(struct task_struct *cur, struct task_struct *p)
1155{
1156	struct migration_swap_arg arg;
1157	int ret = -EINVAL;
1158
1159	arg = (struct migration_swap_arg){
1160		.src_task = cur,
1161		.src_cpu = task_cpu(cur),
1162		.dst_task = p,
1163		.dst_cpu = task_cpu(p),
1164	};
1165
1166	if (arg.src_cpu == arg.dst_cpu)
1167		goto out;
1168
1169	/*
1170	 * These three tests are all lockless; this is OK since all of them
1171	 * will be re-checked with proper locks held further down the line.
1172	 */
1173	if (!cpu_active(arg.src_cpu) || !cpu_active(arg.dst_cpu))
1174		goto out;
1175
1176	if (!cpumask_test_cpu(arg.dst_cpu, tsk_cpus_allowed(arg.src_task)))
1177		goto out;
1178
1179	if (!cpumask_test_cpu(arg.src_cpu, tsk_cpus_allowed(arg.dst_task)))
1180		goto out;
1181
1182	trace_sched_swap_numa(cur, arg.src_cpu, p, arg.dst_cpu);
1183	ret = stop_two_cpus(arg.dst_cpu, arg.src_cpu, migrate_swap_stop, &arg);
1184
1185out:
1186	return ret;
1187}
1188
1189struct migration_arg {
1190	struct task_struct *task;
1191	int dest_cpu;
1192};
1193
1194static int migration_cpu_stop(void *data);
1195
1196/*
1197 * wait_task_inactive - wait for a thread to unschedule.
1198 *
1199 * If @match_state is nonzero, it's the @p->state value just checked and
1200 * not expected to change.  If it changes, i.e. @p might have woken up,
1201 * then return zero.  When we succeed in waiting for @p to be off its CPU,
1202 * we return a positive number (its total switch count).  If a second call
1203 * a short while later returns the same number, the caller can be sure that
1204 * @p has remained unscheduled the whole time.
1205 *
1206 * The caller must ensure that the task *will* unschedule sometime soon,
1207 * else this function might spin for a *long* time. This function can't
1208 * be called with interrupts off, or it may introduce deadlock with
1209 * smp_call_function() if an IPI is sent by the same process we are
1210 * waiting to become inactive.
1211 */
1212unsigned long wait_task_inactive(struct task_struct *p, long match_state)
1213{
1214	unsigned long flags;
1215	int running, queued;
1216	unsigned long ncsw;
1217	struct rq *rq;
1218
1219	for (;;) {
1220		/*
1221		 * We do the initial early heuristics without holding
1222		 * any task-queue locks at all. We'll only try to get
1223		 * the runqueue lock when things look like they will
1224		 * work out!
1225		 */
1226		rq = task_rq(p);
1227
1228		/*
1229		 * If the task is actively running on another CPU
1230		 * still, just relax and busy-wait without holding
1231		 * any locks.
1232		 *
1233		 * NOTE! Since we don't hold any locks, it's not
1234		 * even sure that "rq" stays as the right runqueue!
1235		 * But we don't care, since "task_running()" will
1236		 * return false if the runqueue has changed and p
1237		 * is actually now running somewhere else!
1238		 */
1239		while (task_running(rq, p)) {
1240			if (match_state && unlikely(p->state != match_state))
1241				return 0;
1242			cpu_relax();
1243		}
1244
1245		/*
1246		 * Ok, time to look more closely! We need the rq
1247		 * lock now, to be *sure*. If we're wrong, we'll
1248		 * just go back and repeat.
1249		 */
1250		rq = task_rq_lock(p, &flags);
1251		trace_sched_wait_task(p);
1252		running = task_running(rq, p);
1253		queued = task_on_rq_queued(p);
1254		ncsw = 0;
1255		if (!match_state || p->state == match_state)
1256			ncsw = p->nvcsw | LONG_MIN; /* sets MSB */
1257		task_rq_unlock(rq, p, &flags);
1258
1259		/*
1260		 * If it changed from the expected state, bail out now.
1261		 */
1262		if (unlikely(!ncsw))
1263			break;
1264
1265		/*
1266		 * Was it really running after all now that we
1267		 * checked with the proper locks actually held?
1268		 *
1269		 * Oops. Go back and try again..
1270		 */
1271		if (unlikely(running)) {
1272			cpu_relax();
1273			continue;
1274		}
1275
1276		/*
1277		 * It's not enough that it's not actively running,
1278		 * it must be off the runqueue _entirely_, and not
1279		 * preempted!
1280		 *
1281		 * So if it was still runnable (but just not actively
1282		 * running right now), it's preempted, and we should
1283		 * yield - it could be a while.
1284		 */
1285		if (unlikely(queued)) {
1286			ktime_t to = ktime_set(0, NSEC_PER_SEC/HZ);
1287
1288			set_current_state(TASK_UNINTERRUPTIBLE);
1289			schedule_hrtimeout(&to, HRTIMER_MODE_REL);
1290			continue;
1291		}
1292
1293		/*
1294		 * Ahh, all good. It wasn't running, and it wasn't
1295		 * runnable, which means that it will never become
1296		 * running in the future either. We're all done!
1297		 */
1298		break;
1299	}
1300
1301	return ncsw;
1302}
1303
1304/***
1305 * kick_process - kick a running thread to enter/exit the kernel
1306 * @p: the to-be-kicked thread
1307 *
1308 * Cause a process which is running on another CPU to enter
1309 * kernel-mode, without any delay. (to get signals handled.)
1310 *
1311 * NOTE: this function doesn't have to take the runqueue lock,
1312 * because all it wants to ensure is that the remote task enters
1313 * the kernel. If the IPI races and the task has been migrated
1314 * to another CPU then no harm is done and the purpose has been
1315 * achieved as well.
1316 */
1317void kick_process(struct task_struct *p)
1318{
1319	int cpu;
1320
1321	preempt_disable();
1322	cpu = task_cpu(p);
1323	if ((cpu != smp_processor_id()) && task_curr(p))
1324		smp_send_reschedule(cpu);
1325	preempt_enable();
1326}
1327EXPORT_SYMBOL_GPL(kick_process);
1328#endif /* CONFIG_SMP */
1329
1330#ifdef CONFIG_SMP
1331/*
1332 * ->cpus_allowed is protected by both rq->lock and p->pi_lock
1333 */
1334static int select_fallback_rq(int cpu, struct task_struct *p)
1335{
1336	int nid = cpu_to_node(cpu);
1337	const struct cpumask *nodemask = NULL;
1338	enum { cpuset, possible, fail } state = cpuset;
1339	int dest_cpu;
1340
1341	/*
1342	 * If the node that the cpu is on has been offlined, cpu_to_node()
1343	 * will return -1. There is no cpu on the node, and we should
1344	 * select the cpu on the other node.
1345	 */
1346	if (nid != -1) {
1347		nodemask = cpumask_of_node(nid);
1348
1349		/* Look for allowed, online CPU in same node. */
1350		for_each_cpu(dest_cpu, nodemask) {
1351			if (!cpu_online(dest_cpu))
1352				continue;
1353			if (!cpu_active(dest_cpu))
1354				continue;
1355			if (cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
1356				return dest_cpu;
1357		}
1358	}
1359
1360	for (;;) {
1361		/* Any allowed, online CPU? */
1362		for_each_cpu(dest_cpu, tsk_cpus_allowed(p)) {
1363			if (!cpu_online(dest_cpu))
1364				continue;
1365			if (!cpu_active(dest_cpu))
1366				continue;
1367			goto out;
1368		}
1369
1370		switch (state) {
1371		case cpuset:
1372			/* No more Mr. Nice Guy. */
1373			cpuset_cpus_allowed_fallback(p);
1374			state = possible;
1375			break;
1376
1377		case possible:
1378			do_set_cpus_allowed(p, cpu_possible_mask);
1379			state = fail;
1380			break;
1381
1382		case fail:
1383			BUG();
1384			break;
1385		}
1386	}
1387
1388out:
1389	if (state != cpuset) {
1390		/*
1391		 * Don't tell them about moving exiting tasks or
1392		 * kernel threads (both mm NULL), since they never
1393		 * leave kernel.
1394		 */
1395		if (p->mm && printk_ratelimit()) {
1396			printk_deferred("process %d (%s) no longer affine to cpu%d\n",
1397					task_pid_nr(p), p->comm, cpu);
1398		}
1399	}
1400
1401	return dest_cpu;
1402}
1403
1404/*
1405 * The caller (fork, wakeup) owns p->pi_lock, ->cpus_allowed is stable.
1406 */
1407static inline
1408int select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags)
1409{
1410	cpu = p->sched_class->select_task_rq(p, cpu, sd_flags, wake_flags);
1411
1412	/*
1413	 * In order not to call set_task_cpu() on a blocking task we need
1414	 * to rely on ttwu() to place the task on a valid ->cpus_allowed
1415	 * cpu.
1416	 *
1417	 * Since this is common to all placement strategies, this lives here.
1418	 *
1419	 * [ this allows ->select_task() to simply return task_cpu(p) and
1420	 *   not worry about this generic constraint ]
1421	 */
1422	if (unlikely(!cpumask_test_cpu(cpu, tsk_cpus_allowed(p)) ||
1423		     !cpu_online(cpu)))
1424		cpu = select_fallback_rq(task_cpu(p), p);
1425
1426	return cpu;
1427}
1428
1429static void update_avg(u64 *avg, u64 sample)
1430{
1431	s64 diff = sample - *avg;
1432	*avg += diff >> 3;
1433}
1434#endif
1435
1436static void
1437ttwu_stat(struct task_struct *p, int cpu, int wake_flags)
1438{
1439#ifdef CONFIG_SCHEDSTATS
1440	struct rq *rq = this_rq();
1441
1442#ifdef CONFIG_SMP
1443	int this_cpu = smp_processor_id();
1444
1445	if (cpu == this_cpu) {
1446		schedstat_inc(rq, ttwu_local);
1447		schedstat_inc(p, se.statistics.nr_wakeups_local);
1448	} else {
1449		struct sched_domain *sd;
1450
1451		schedstat_inc(p, se.statistics.nr_wakeups_remote);
1452		rcu_read_lock();
1453		for_each_domain(this_cpu, sd) {
1454			if (cpumask_test_cpu(cpu, sched_domain_span(sd))) {
1455				schedstat_inc(sd, ttwu_wake_remote);
1456				break;
1457			}
1458		}
1459		rcu_read_unlock();
1460	}
1461
1462	if (wake_flags & WF_MIGRATED)
1463		schedstat_inc(p, se.statistics.nr_wakeups_migrate);
1464
1465#endif /* CONFIG_SMP */
1466
1467	schedstat_inc(rq, ttwu_count);
1468	schedstat_inc(p, se.statistics.nr_wakeups);
1469
1470	if (wake_flags & WF_SYNC)
1471		schedstat_inc(p, se.statistics.nr_wakeups_sync);
1472
1473#endif /* CONFIG_SCHEDSTATS */
1474}
1475
1476static void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
1477{
1478	activate_task(rq, p, en_flags);
1479	p->on_rq = TASK_ON_RQ_QUEUED;
1480
1481	/* if a worker is waking up, notify workqueue */
1482	if (p->flags & PF_WQ_WORKER)
1483		wq_worker_waking_up(p, cpu_of(rq));
1484}
1485
1486/*
1487 * Mark the task runnable and perform wakeup-preemption.
1488 */
1489static void
1490ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
1491{
1492	check_preempt_curr(rq, p, wake_flags);
1493	trace_sched_wakeup(p, true);
1494
1495	p->state = TASK_RUNNING;
1496#ifdef CONFIG_SMP
1497	if (p->sched_class->task_woken)
1498		p->sched_class->task_woken(rq, p);
1499
1500	if (rq->idle_stamp) {
1501		u64 delta = rq_clock(rq) - rq->idle_stamp;
1502		u64 max = 2*rq->max_idle_balance_cost;
1503
1504		update_avg(&rq->avg_idle, delta);
1505
1506		if (rq->avg_idle > max)
1507			rq->avg_idle = max;
1508
1509		rq->idle_stamp = 0;
1510	}
1511#endif
1512}
1513
1514static void
1515ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags)
1516{
1517#ifdef CONFIG_SMP
1518	if (p->sched_contributes_to_load)
1519		rq->nr_uninterruptible--;
1520#endif
1521
1522	ttwu_activate(rq, p, ENQUEUE_WAKEUP | ENQUEUE_WAKING);
1523	ttwu_do_wakeup(rq, p, wake_flags);
1524}
1525
1526/*
1527 * Called in case the task @p isn't fully descheduled from its runqueue,
1528 * in this case we must do a remote wakeup. Its a 'light' wakeup though,
1529 * since all we need to do is flip p->state to TASK_RUNNING, since
1530 * the task is still ->on_rq.
1531 */
1532static int ttwu_remote(struct task_struct *p, int wake_flags)
1533{
1534	struct rq *rq;
1535	int ret = 0;
1536
1537	rq = __task_rq_lock(p);
1538	if (task_on_rq_queued(p)) {
1539		/* check_preempt_curr() may use rq clock */
1540		update_rq_clock(rq);
1541		ttwu_do_wakeup(rq, p, wake_flags);
1542		ret = 1;
1543	}
1544	__task_rq_unlock(rq);
1545
1546	return ret;
1547}
1548
1549#ifdef CONFIG_SMP
1550void sched_ttwu_pending(void)
1551{
1552	struct rq *rq = this_rq();
1553	struct llist_node *llist = llist_del_all(&rq->wake_list);
1554	struct task_struct *p;
1555	unsigned long flags;
1556
1557	if (!llist)
1558		return;
1559
1560	raw_spin_lock_irqsave(&rq->lock, flags);
1561
1562	while (llist) {
1563		p = llist_entry(llist, struct task_struct, wake_entry);
1564		llist = llist_next(llist);
1565		ttwu_do_activate(rq, p, 0);
1566	}
1567
1568	raw_spin_unlock_irqrestore(&rq->lock, flags);
1569}
1570
1571void scheduler_ipi(void)
1572{
1573	/*
1574	 * Fold TIF_NEED_RESCHED into the preempt_count; anybody setting
1575	 * TIF_NEED_RESCHED remotely (for the first time) will also send
1576	 * this IPI.
1577	 */
1578	preempt_fold_need_resched();
1579
1580	if (llist_empty(&this_rq()->wake_list) && !got_nohz_idle_kick())
1581		return;
1582
1583	/*
1584	 * Not all reschedule IPI handlers call irq_enter/irq_exit, since
1585	 * traditionally all their work was done from the interrupt return
1586	 * path. Now that we actually do some work, we need to make sure
1587	 * we do call them.
1588	 *
1589	 * Some archs already do call them, luckily irq_enter/exit nest
1590	 * properly.
1591	 *
1592	 * Arguably we should visit all archs and update all handlers,
1593	 * however a fair share of IPIs are still resched only so this would
1594	 * somewhat pessimize the simple resched case.
1595	 */
1596	irq_enter();
1597	sched_ttwu_pending();
1598
1599	/*
1600	 * Check if someone kicked us for doing the nohz idle load balance.
1601	 */
1602	if (unlikely(got_nohz_idle_kick())) {
1603		this_rq()->idle_balance = 1;
1604		raise_softirq_irqoff(SCHED_SOFTIRQ);
1605	}
1606	irq_exit();
1607}
1608
1609static void ttwu_queue_remote(struct task_struct *p, int cpu)
1610{
1611	struct rq *rq = cpu_rq(cpu);
1612
1613	if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list)) {
1614		if (!set_nr_if_polling(rq->idle))
1615			smp_send_reschedule(cpu);
1616		else
1617			trace_sched_wake_idle_without_ipi(cpu);
1618	}
1619}
1620
1621void wake_up_if_idle(int cpu)
1622{
1623	struct rq *rq = cpu_rq(cpu);
1624	unsigned long flags;
1625
1626	rcu_read_lock();
1627
1628	if (!is_idle_task(rcu_dereference(rq->curr)))
1629		goto out;
1630
1631	if (set_nr_if_polling(rq->idle)) {
1632		trace_sched_wake_idle_without_ipi(cpu);
1633	} else {
1634		raw_spin_lock_irqsave(&rq->lock, flags);
1635		if (is_idle_task(rq->curr))
1636			smp_send_reschedule(cpu);
1637		/* Else cpu is not in idle, do nothing here */
1638		raw_spin_unlock_irqrestore(&rq->lock, flags);
1639	}
1640
1641out:
1642	rcu_read_unlock();
1643}
1644
1645bool cpus_share_cache(int this_cpu, int that_cpu)
1646{
1647	return per_cpu(sd_llc_id, this_cpu) == per_cpu(sd_llc_id, that_cpu);
1648}
1649#endif /* CONFIG_SMP */
1650
1651static void ttwu_queue(struct task_struct *p, int cpu)
1652{
1653	struct rq *rq = cpu_rq(cpu);
1654
1655#if defined(CONFIG_SMP)
1656	if (sched_feat(TTWU_QUEUE) && !cpus_share_cache(smp_processor_id(), cpu)) {
1657		sched_clock_cpu(cpu); /* sync clocks x-cpu */
1658		ttwu_queue_remote(p, cpu);
1659		return;
1660	}
1661#endif
1662
1663	raw_spin_lock(&rq->lock);
1664	ttwu_do_activate(rq, p, 0);
1665	raw_spin_unlock(&rq->lock);
1666}
1667
1668/**
1669 * try_to_wake_up - wake up a thread
1670 * @p: the thread to be awakened
1671 * @state: the mask of task states that can be woken
1672 * @wake_flags: wake modifier flags (WF_*)
1673 *
1674 * Put it on the run-queue if it's not already there. The "current"
1675 * thread is always on the run-queue (except when the actual
1676 * re-schedule is in progress), and as such you're allowed to do
1677 * the simpler "current->state = TASK_RUNNING" to mark yourself
1678 * runnable without the overhead of this.
1679 *
1680 * Return: %true if @p was woken up, %false if it was already running.
1681 * or @state didn't match @p's state.
1682 */
1683static int
1684try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
1685{
1686	unsigned long flags;
1687	int cpu, success = 0;
1688
1689	/*
1690	 * If we are going to wake up a thread waiting for CONDITION we
1691	 * need to ensure that CONDITION=1 done by the caller can not be
1692	 * reordered with p->state check below. This pairs with mb() in
1693	 * set_current_state() the waiting thread does.
1694	 */
1695	smp_mb__before_spinlock();
1696	raw_spin_lock_irqsave(&p->pi_lock, flags);
1697	if (!(p->state & state))
1698		goto out;
1699
1700	success = 1; /* we're going to change ->state */
1701	cpu = task_cpu(p);
1702
1703	if (p->on_rq && ttwu_remote(p, wake_flags))
1704		goto stat;
1705
1706#ifdef CONFIG_SMP
1707	/*
1708	 * If the owning (remote) cpu is still in the middle of schedule() with
1709	 * this task as prev, wait until its done referencing the task.
1710	 */
1711	while (p->on_cpu)
1712		cpu_relax();
1713	/*
1714	 * Pairs with the smp_wmb() in finish_lock_switch().
1715	 */
1716	smp_rmb();
1717
1718	p->sched_contributes_to_load = !!task_contributes_to_load(p);
1719	p->state = TASK_WAKING;
1720
1721	if (p->sched_class->task_waking)
1722		p->sched_class->task_waking(p);
1723
1724	cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);
1725	if (task_cpu(p) != cpu) {
1726		wake_flags |= WF_MIGRATED;
1727		set_task_cpu(p, cpu);
1728	}
1729#endif /* CONFIG_SMP */
1730
1731	ttwu_queue(p, cpu);
1732stat:
1733	ttwu_stat(p, cpu, wake_flags);
1734out:
1735	raw_spin_unlock_irqrestore(&p->pi_lock, flags);
1736
1737	return success;
1738}
1739
1740/**
1741 * try_to_wake_up_local - try to wake up a local task with rq lock held
1742 * @p: the thread to be awakened
1743 *
1744 * Put @p on the run-queue if it's not already there. The caller must
1745 * ensure that this_rq() is locked, @p is bound to this_rq() and not
1746 * the current task.
1747 */
1748static void try_to_wake_up_local(struct task_struct *p)
1749{
1750	struct rq *rq = task_rq(p);
1751
1752	if (WARN_ON_ONCE(rq != this_rq()) ||
1753	    WARN_ON_ONCE(p == current))
1754		return;
1755
1756	lockdep_assert_held(&rq->lock);
1757
1758	if (!raw_spin_trylock(&p->pi_lock)) {
1759		raw_spin_unlock(&rq->lock);
1760		raw_spin_lock(&p->pi_lock);
1761		raw_spin_lock(&rq->lock);
1762	}
1763
1764	if (!(p->state & TASK_NORMAL))
1765		goto out;
1766
1767	if (!task_on_rq_queued(p))
1768		ttwu_activate(rq, p, ENQUEUE_WAKEUP);
1769
1770	ttwu_do_wakeup(rq, p, 0);
1771	ttwu_stat(p, smp_processor_id(), 0);
1772out:
1773	raw_spin_unlock(&p->pi_lock);
1774}
1775
1776/**
1777 * wake_up_process - Wake up a specific process
1778 * @p: The process to be woken up.
1779 *
1780 * Attempt to wake up the nominated process and move it to the set of runnable
1781 * processes.
1782 *
1783 * Return: 1 if the process was woken up, 0 if it was already running.
1784 *
1785 * It may be assumed that this function implies a write memory barrier before
1786 * changing the task state if and only if any tasks are woken up.
1787 */
1788int wake_up_process(struct task_struct *p)
1789{
1790	WARN_ON(task_is_stopped_or_traced(p));
1791	return try_to_wake_up(p, TASK_NORMAL, 0);
1792}
1793EXPORT_SYMBOL(wake_up_process);
1794
1795int wake_up_state(struct task_struct *p, unsigned int state)
1796{
1797	return try_to_wake_up(p, state, 0);
1798}
1799
1800/*
1801 * This function clears the sched_dl_entity static params.
1802 */
1803void __dl_clear_params(struct task_struct *p)
1804{
1805	struct sched_dl_entity *dl_se = &p->dl;
1806
1807	dl_se->dl_runtime = 0;
1808	dl_se->dl_deadline = 0;
1809	dl_se->dl_period = 0;
1810	dl_se->flags = 0;
1811	dl_se->dl_bw = 0;
1812}
1813
1814/*
1815 * Perform scheduler related setup for a newly forked process p.
1816 * p is forked by current.
1817 *
1818 * __sched_fork() is basic setup used by init_idle() too:
1819 */
1820static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
1821{
1822	p->on_rq			= 0;
1823
1824	p->se.on_rq			= 0;
1825	p->se.exec_start		= 0;
1826	p->se.sum_exec_runtime		= 0;
1827	p->se.prev_sum_exec_runtime	= 0;
1828	p->se.nr_migrations		= 0;
1829	p->se.vruntime			= 0;
1830	INIT_LIST_HEAD(&p->se.group_node);
1831
1832#ifdef CONFIG_SCHEDSTATS
1833	memset(&p->se.statistics, 0, sizeof(p->se.statistics));
1834#endif
1835
1836	RB_CLEAR_NODE(&p->dl.rb_node);
1837	hrtimer_init(&p->dl.dl_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
1838	__dl_clear_params(p);
1839
1840	INIT_LIST_HEAD(&p->rt.run_list);
1841
1842#ifdef CONFIG_PREEMPT_NOTIFIERS
1843	INIT_HLIST_HEAD(&p->preempt_notifiers);
1844#endif
1845
1846#ifdef CONFIG_NUMA_BALANCING
1847	if (p->mm && atomic_read(&p->mm->mm_users) == 1) {
1848		p->mm->numa_next_scan = jiffies + msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
1849		p->mm->numa_scan_seq = 0;
1850	}
1851
1852	if (clone_flags & CLONE_VM)
1853		p->numa_preferred_nid = current->numa_preferred_nid;
1854	else
1855		p->numa_preferred_nid = -1;
1856
1857	p->node_stamp = 0ULL;
1858	p->numa_scan_seq = p->mm ? p->mm->numa_scan_seq : 0;
1859	p->numa_scan_period = sysctl_numa_balancing_scan_delay;
1860	p->numa_work.next = &p->numa_work;
1861	p->numa_faults_memory = NULL;
1862	p->numa_faults_buffer_memory = NULL;
1863	p->last_task_numa_placement = 0;
1864	p->last_sum_exec_runtime = 0;
1865
1866	INIT_LIST_HEAD(&p->numa_entry);
1867	p->numa_group = NULL;
1868#endif /* CONFIG_NUMA_BALANCING */
1869}
1870
1871#ifdef CONFIG_NUMA_BALANCING
1872#ifdef CONFIG_SCHED_DEBUG
1873void set_numabalancing_state(bool enabled)
1874{
1875	if (enabled)
1876		sched_feat_set("NUMA");
1877	else
1878		sched_feat_set("NO_NUMA");
1879}
1880#else
1881__read_mostly bool numabalancing_enabled;
1882
1883void set_numabalancing_state(bool enabled)
1884{
1885	numabalancing_enabled = enabled;
1886}
1887#endif /* CONFIG_SCHED_DEBUG */
1888
1889#ifdef CONFIG_PROC_SYSCTL
1890int sysctl_numa_balancing(struct ctl_table *table, int write,
1891			 void __user *buffer, size_t *lenp, loff_t *ppos)
1892{
1893	struct ctl_table t;
1894	int err;
1895	int state = numabalancing_enabled;
1896
1897	if (write && !capable(CAP_SYS_ADMIN))
1898		return -EPERM;
1899
1900	t = *table;
1901	t.data = &state;
1902	err = proc_dointvec_minmax(&t, write, buffer, lenp, ppos);
1903	if (err < 0)
1904		return err;
1905	if (write)
1906		set_numabalancing_state(state);
1907	return err;
1908}
1909#endif
1910#endif
1911
1912/*
1913 * fork()/clone()-time setup:
1914 */
1915int sched_fork(unsigned long clone_flags, struct task_struct *p)
1916{
1917	unsigned long flags;
1918	int cpu = get_cpu();
1919
1920	__sched_fork(clone_flags, p);
1921	/*
1922	 * We mark the process as running here. This guarantees that
1923	 * nobody will actually run it, and a signal or other external
1924	 * event cannot wake it up and insert it on the runqueue either.
1925	 */
1926	p->state = TASK_RUNNING;
1927
1928	/*
1929	 * Make sure we do not leak PI boosting priority to the child.
1930	 */
1931	p->prio = current->normal_prio;
1932
1933	/*
1934	 * Revert to default priority/policy on fork if requested.
1935	 */
1936	if (unlikely(p->sched_reset_on_fork)) {
1937		if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
1938			p->policy = SCHED_NORMAL;
1939			p->static_prio = NICE_TO_PRIO(0);
1940			p->rt_priority = 0;
1941		} else if (PRIO_TO_NICE(p->static_prio) < 0)
1942			p->static_prio = NICE_TO_PRIO(0);
1943
1944		p->prio = p->normal_prio = __normal_prio(p);
1945		set_load_weight(p);
1946
1947		/*
1948		 * We don't need the reset flag anymore after the fork. It has
1949		 * fulfilled its duty:
1950		 */
1951		p->sched_reset_on_fork = 0;
1952	}
1953
1954	if (dl_prio(p->prio)) {
1955		put_cpu();
1956		return -EAGAIN;
1957	} else if (rt_prio(p->prio)) {
1958		p->sched_class = &rt_sched_class;
1959	} else {
1960		p->sched_class = &fair_sched_class;
1961	}
1962
1963	if (p->sched_class->task_fork)
1964		p->sched_class->task_fork(p);
1965
1966	/*
1967	 * The child is not yet in the pid-hash so no cgroup attach races,
1968	 * and the cgroup is pinned to this child due to cgroup_fork()
1969	 * is ran before sched_fork().
1970	 *
1971	 * Silence PROVE_RCU.
1972	 */
1973	raw_spin_lock_irqsave(&p->pi_lock, flags);
1974	set_task_cpu(p, cpu);
1975	raw_spin_unlock_irqrestore(&p->pi_lock, flags);
1976
1977#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
1978	if (likely(sched_info_on()))
1979		memset(&p->sched_info, 0, sizeof(p->sched_info));
1980#endif
1981#if defined(CONFIG_SMP)
1982	p->on_cpu = 0;
1983#endif
1984	init_task_preempt_count(p);
1985#ifdef CONFIG_SMP
1986	plist_node_init(&p->pushable_tasks, MAX_PRIO);
1987	RB_CLEAR_NODE(&p->pushable_dl_tasks);
1988#endif
1989
1990	put_cpu();
1991	return 0;
1992}
1993
1994unsigned long to_ratio(u64 period, u64 runtime)
1995{
1996	if (runtime == RUNTIME_INF)
1997		return 1ULL << 20;
1998
1999	/*
2000	 * Doing this here saves a lot of checks in all
2001	 * the calling paths, and returning zero seems
2002	 * safe for them anyway.
2003	 */
2004	if (period == 0)
2005		return 0;
2006
2007	return div64_u64(runtime << 20, period);
2008}
2009
2010#ifdef CONFIG_SMP
2011inline struct dl_bw *dl_bw_of(int i)
2012{
2013	rcu_lockdep_assert(rcu_read_lock_sched_held(),
2014			   "sched RCU must be held");
2015	return &cpu_rq(i)->rd->dl_bw;
2016}
2017
2018static inline int dl_bw_cpus(int i)
2019{
2020	struct root_domain *rd = cpu_rq(i)->rd;
2021	int cpus = 0;
2022
2023	rcu_lockdep_assert(rcu_read_lock_sched_held(),
2024			   "sched RCU must be held");
2025	for_each_cpu_and(i, rd->span, cpu_active_mask)
2026		cpus++;
2027
2028	return cpus;
2029}
2030#else
2031inline struct dl_bw *dl_bw_of(int i)
2032{
2033	return &cpu_rq(i)->dl.dl_bw;
2034}
2035
2036static inline int dl_bw_cpus(int i)
2037{
2038	return 1;
2039}
2040#endif
2041
2042static inline
2043void __dl_clear(struct dl_bw *dl_b, u64 tsk_bw)
2044{
2045	dl_b->total_bw -= tsk_bw;
2046}
2047
2048static inline
2049void __dl_add(struct dl_bw *dl_b, u64 tsk_bw)
2050{
2051	dl_b->total_bw += tsk_bw;
2052}
2053
2054static inline
2055bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64 new_bw)
2056{
2057	return dl_b->bw != -1 &&
2058	       dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw;
2059}
2060
2061/*
2062 * We must be sure that accepting a new task (or allowing changing the
2063 * parameters of an existing one) is consistent with the bandwidth
2064 * constraints. If yes, this function also accordingly updates the currently
2065 * allocated bandwidth to reflect the new situation.
2066 *
2067 * This function is called while holding p's rq->lock.
2068 */
2069static int dl_overflow(struct task_struct *p, int policy,
2070		       const struct sched_attr *attr)
2071{
2072
2073	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
2074	u64 period = attr->sched_period ?: attr->sched_deadline;
2075	u64 runtime = attr->sched_runtime;
2076	u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) : 0;
2077	int cpus, err = -1;
2078
2079	if (new_bw == p->dl.dl_bw)
2080		return 0;
2081
2082	/*
2083	 * Either if a task, enters, leave, or stays -deadline but changes
2084	 * its parameters, we may need to update accordingly the total
2085	 * allocated bandwidth of the container.
2086	 */
2087	raw_spin_lock(&dl_b->lock);
2088	cpus = dl_bw_cpus(task_cpu(p));
2089	if (dl_policy(policy) && !task_has_dl_policy(p) &&
2090	    !__dl_overflow(dl_b, cpus, 0, new_bw)) {
2091		__dl_add(dl_b, new_bw);
2092		err = 0;
2093	} else if (dl_policy(policy) && task_has_dl_policy(p) &&
2094		   !__dl_overflow(dl_b, cpus, p->dl.dl_bw, new_bw)) {
2095		__dl_clear(dl_b, p->dl.dl_bw);
2096		__dl_add(dl_b, new_bw);
2097		err = 0;
2098	} else if (!dl_policy(policy) && task_has_dl_policy(p)) {
2099		__dl_clear(dl_b, p->dl.dl_bw);
2100		err = 0;
2101	}
2102	raw_spin_unlock(&dl_b->lock);
2103
2104	return err;
2105}
2106
2107extern void init_dl_bw(struct dl_bw *dl_b);
2108
2109/*
2110 * wake_up_new_task - wake up a newly created task for the first time.
2111 *
2112 * This function will do some initial scheduler statistics housekeeping
2113 * that must be done for every newly created context, then puts the task
2114 * on the runqueue and wakes it.
2115 */
2116void wake_up_new_task(struct task_struct *p)
2117{
2118	unsigned long flags;
2119	struct rq *rq;
2120
2121	raw_spin_lock_irqsave(&p->pi_lock, flags);
2122#ifdef CONFIG_SMP
2123	/*
2124	 * Fork balancing, do it here and not earlier because:
2125	 *  - cpus_allowed can change in the fork path
2126	 *  - any previously selected cpu might disappear through hotplug
2127	 */
2128	set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));
2129#endif
2130
2131	/* Initialize new task's runnable average */
2132	init_task_runnable_average(p);
2133	rq = __task_rq_lock(p);
2134	activate_task(rq, p, 0);
2135	p->on_rq = TASK_ON_RQ_QUEUED;
2136	trace_sched_wakeup_new(p, true);
2137	check_preempt_curr(rq, p, WF_FORK);
2138#ifdef CONFIG_SMP
2139	if (p->sched_class->task_woken)
2140		p->sched_class->task_woken(rq, p);
2141#endif
2142	task_rq_unlock(rq, p, &flags);
2143}
2144
2145#ifdef CONFIG_PREEMPT_NOTIFIERS
2146
2147/**
2148 * preempt_notifier_register - tell me when current is being preempted & rescheduled
2149 * @notifier: notifier struct to register
2150 */
2151void preempt_notifier_register(struct preempt_notifier *notifier)
2152{
2153	hlist_add_head(&notifier->link, &current->preempt_notifiers);
2154}
2155EXPORT_SYMBOL_GPL(preempt_notifier_register);
2156
2157/**
2158 * preempt_notifier_unregister - no longer interested in preemption notifications
2159 * @notifier: notifier struct to unregister
2160 *
2161 * This is safe to call from within a preemption notifier.
2162 */
2163void preempt_notifier_unregister(struct preempt_notifier *notifier)
2164{
2165	hlist_del(&notifier->link);
2166}
2167EXPORT_SYMBOL_GPL(preempt_notifier_unregister);
2168
2169static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
2170{
2171	struct preempt_notifier *notifier;
2172
2173	hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
2174		notifier->ops->sched_in(notifier, raw_smp_processor_id());
2175}
2176
2177static void
2178fire_sched_out_preempt_notifiers(struct task_struct *curr,
2179				 struct task_struct *next)
2180{
2181	struct preempt_notifier *notifier;
2182
2183	hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
2184		notifier->ops->sched_out(notifier, next);
2185}
2186
2187#else /* !CONFIG_PREEMPT_NOTIFIERS */
2188
2189static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
2190{
2191}
2192
2193static void
2194fire_sched_out_preempt_notifiers(struct task_struct *curr,
2195				 struct task_struct *next)
2196{
2197}
2198
2199#endif /* CONFIG_PREEMPT_NOTIFIERS */
2200
2201/**
2202 * prepare_task_switch - prepare to switch tasks
2203 * @rq: the runqueue preparing to switch
2204 * @prev: the current task that is being switched out
2205 * @next: the task we are going to switch to.
2206 *
2207 * This is called with the rq lock held and interrupts off. It must
2208 * be paired with a subsequent finish_task_switch after the context
2209 * switch.
2210 *
2211 * prepare_task_switch sets up locking and calls architecture specific
2212 * hooks.
2213 */
2214static inline void
2215prepare_task_switch(struct rq *rq, struct task_struct *prev,
2216		    struct task_struct *next)
2217{
2218	trace_sched_switch(prev, next);
2219	sched_info_switch(rq, prev, next);
2220	perf_event_task_sched_out(prev, next);
2221	fire_sched_out_preempt_notifiers(prev, next);
2222	prepare_lock_switch(rq, next);
2223	prepare_arch_switch(next);
2224}
2225
2226/**
2227 * finish_task_switch - clean up after a task-switch
2228 * @rq: runqueue associated with task-switch
2229 * @prev: the thread we just switched away from.
2230 *
2231 * finish_task_switch must be called after the context switch, paired
2232 * with a prepare_task_switch call before the context switch.
2233 * finish_task_switch will reconcile locking set up by prepare_task_switch,
2234 * and do any other architecture-specific cleanup actions.
2235 *
2236 * Note that we may have delayed dropping an mm in context_switch(). If
2237 * so, we finish that here outside of the runqueue lock. (Doing it
2238 * with the lock held can cause deadlocks; see schedule() for
2239 * details.)
2240 */
2241static void finish_task_switch(struct rq *rq, struct task_struct *prev)
2242	__releases(rq->lock)
2243{
2244	struct mm_struct *mm = rq->prev_mm;
2245	long prev_state;
2246
2247	rq->prev_mm = NULL;
2248
2249	/*
2250	 * A task struct has one reference for the use as "current".
2251	 * If a task dies, then it sets TASK_DEAD in tsk->state and calls
2252	 * schedule one last time. The schedule call will never return, and
2253	 * the scheduled task must drop that reference.
2254	 * The test for TASK_DEAD must occur while the runqueue locks are
2255	 * still held, otherwise prev could be scheduled on another cpu, die
2256	 * there before we look at prev->state, and then the reference would
2257	 * be dropped twice.
2258	 *		Manfred Spraul <manfred@colorfullife.com>
2259	 */
2260	prev_state = prev->state;
2261	vtime_task_switch(prev);
2262	finish_arch_switch(prev);
2263	perf_event_task_sched_in(prev, current);
2264	finish_lock_switch(rq, prev);
2265	finish_arch_post_lock_switch();
2266
2267	fire_sched_in_preempt_notifiers(current);
2268	if (mm)
2269		mmdrop(mm);
2270	if (unlikely(prev_state == TASK_DEAD)) {
2271		if (prev->sched_class->task_dead)
2272			prev->sched_class->task_dead(prev);
2273
2274		/*
2275		 * Remove function-return probe instances associated with this
2276		 * task and put them back on the free list.
2277		 */
2278		kprobe_flush_task(prev);
2279		put_task_struct(prev);
2280	}
2281
2282	tick_nohz_task_switch(current);
2283}
2284
2285#ifdef CONFIG_SMP
2286
2287/* rq->lock is NOT held, but preemption is disabled */
2288static inline void post_schedule(struct rq *rq)
2289{
2290	if (rq->post_schedule) {
2291		unsigned long flags;
2292
2293		raw_spin_lock_irqsave(&rq->lock, flags);
2294		if (rq->curr->sched_class->post_schedule)
2295			rq->curr->sched_class->post_schedule(rq);
2296		raw_spin_unlock_irqrestore(&rq->lock, flags);
2297
2298		rq->post_schedule = 0;
2299	}
2300}
2301
2302#else
2303
2304static inline void post_schedule(struct rq *rq)
2305{
2306}
2307
2308#endif
2309
2310/**
2311 * schedule_tail - first thing a freshly forked thread must call.
2312 * @prev: the thread we just switched away from.
2313 */
2314asmlinkage __visible void schedule_tail(struct task_struct *prev)
2315	__releases(rq->lock)
2316{
2317	struct rq *rq = this_rq();
2318
2319	finish_task_switch(rq, prev);
2320
2321	/*
2322	 * FIXME: do we need to worry about rq being invalidated by the
2323	 * task_switch?
2324	 */
2325	post_schedule(rq);
2326
2327	if (current->set_child_tid)
2328		put_user(task_pid_vnr(current), current->set_child_tid);
2329}
2330
2331/*
2332 * context_switch - switch to the new MM and the new
2333 * thread's register state.
2334 */
2335static inline void
2336context_switch(struct rq *rq, struct task_struct *prev,
2337	       struct task_struct *next)
2338{
2339	struct mm_struct *mm, *oldmm;
2340
2341	prepare_task_switch(rq, prev, next);
2342
2343	mm = next->mm;
2344	oldmm = prev->active_mm;
2345	/*
2346	 * For paravirt, this is coupled with an exit in switch_to to
2347	 * combine the page table reload and the switch backend into
2348	 * one hypercall.
2349	 */
2350	arch_start_context_switch(prev);
2351
2352	if (!mm) {
2353		next->active_mm = oldmm;
2354		atomic_inc(&oldmm->mm_count);
2355		enter_lazy_tlb(oldmm, next);
2356	} else
2357		switch_mm(oldmm, mm, next);
2358
2359	if (!prev->mm) {
2360		prev->active_mm = NULL;
2361		rq->prev_mm = oldmm;
2362	}
2363	/*
2364	 * Since the runqueue lock will be released by the next
2365	 * task (which is an invalid locking op but in the case
2366	 * of the scheduler it's an obvious special-case), so we
2367	 * do an early lockdep release here:
2368	 */
2369	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
2370
2371	context_tracking_task_switch(prev, next);
2372	/* Here we just switch the register state and the stack. */
2373	switch_to(prev, next, prev);
2374
2375	barrier();
2376	/*
2377	 * this_rq must be evaluated again because prev may have moved
2378	 * CPUs since it called schedule(), thus the 'rq' on its stack
2379	 * frame will be invalid.
2380	 */
2381	finish_task_switch(this_rq(), prev);
2382}
2383
2384/*
2385 * nr_running and nr_context_switches:
2386 *
2387 * externally visible scheduler statistics: current number of runnable
2388 * threads, total number of context switches performed since bootup.
2389 */
2390unsigned long nr_running(void)
2391{
2392	unsigned long i, sum = 0;
2393
2394	for_each_online_cpu(i)
2395		sum += cpu_rq(i)->nr_running;
2396
2397	return sum;
2398}
2399
2400/*
2401 * Check if only the current task is running on the cpu.
2402 */
2403bool single_task_running(void)
2404{
2405	if (cpu_rq(smp_processor_id())->nr_running == 1)
2406		return true;
2407	else
2408		return false;
2409}
2410EXPORT_SYMBOL(single_task_running);
2411
2412unsigned long long nr_context_switches(void)
2413{
2414	int i;
2415	unsigned long long sum = 0;
2416
2417	for_each_possible_cpu(i)
2418		sum += cpu_rq(i)->nr_switches;
2419
2420	return sum;
2421}
2422
2423unsigned long nr_iowait(void)
2424{
2425	unsigned long i, sum = 0;
2426
2427	for_each_possible_cpu(i)
2428		sum += atomic_read(&cpu_rq(i)->nr_iowait);
2429
2430	return sum;
2431}
2432
2433unsigned long nr_iowait_cpu(int cpu)
2434{
2435	struct rq *this = cpu_rq(cpu);
2436	return atomic_read(&this->nr_iowait);
2437}
2438
2439void get_iowait_load(unsigned long *nr_waiters, unsigned long *load)
2440{
2441	struct rq *this = this_rq();
2442	*nr_waiters = atomic_read(&this->nr_iowait);
2443	*load = this->cpu_load[0];
2444}
2445
2446#ifdef CONFIG_SMP
2447
2448/*
2449 * sched_exec - execve() is a valuable balancing opportunity, because at
2450 * this point the task has the smallest effective memory and cache footprint.
2451 */
2452void sched_exec(void)
2453{
2454	struct task_struct *p = current;
2455	unsigned long flags;
2456	int dest_cpu;
2457
2458	raw_spin_lock_irqsave(&p->pi_lock, flags);
2459	dest_cpu = p->sched_class->select_task_rq(p, task_cpu(p), SD_BALANCE_EXEC, 0);
2460	if (dest_cpu == smp_processor_id())
2461		goto unlock;
2462
2463	if (likely(cpu_active(dest_cpu))) {
2464		struct migration_arg arg = { p, dest_cpu };
2465
2466		raw_spin_unlock_irqrestore(&p->pi_lock, flags);
2467		stop_one_cpu(task_cpu(p), migration_cpu_stop, &arg);
2468		return;
2469	}
2470unlock:
2471	raw_spin_unlock_irqrestore(&p->pi_lock, flags);
2472}
2473
2474#endif
2475
2476DEFINE_PER_CPU(struct kernel_stat, kstat);
2477DEFINE_PER_CPU(struct kernel_cpustat, kernel_cpustat);
2478
2479EXPORT_PER_CPU_SYMBOL(kstat);
2480EXPORT_PER_CPU_SYMBOL(kernel_cpustat);
2481
2482/*
2483 * Return accounted runtime for the task.
2484 * In case the task is currently running, return the runtime plus current's
2485 * pending runtime that have not been accounted yet.
2486 */
2487unsigned long long task_sched_runtime(struct task_struct *p)
2488{
2489	unsigned long flags;
2490	struct rq *rq;
2491	u64 ns;
2492
2493#if defined(CONFIG_64BIT) && defined(CONFIG_SMP)
2494	/*
2495	 * 64-bit doesn't need locks to atomically read a 64bit value.
2496	 * So we have a optimization chance when the task's delta_exec is 0.
2497	 * Reading ->on_cpu is racy, but this is ok.
2498	 *
2499	 * If we race with it leaving cpu, we'll take a lock. So we're correct.
2500	 * If we race with it entering cpu, unaccounted time is 0. This is
2501	 * indistinguishable from the read occurring a few cycles earlier.
2502	 * If we see ->on_cpu without ->on_rq, the task is leaving, and has
2503	 * been accounted, so we're correct here as well.
2504	 */
2505	if (!p->on_cpu || !task_on_rq_queued(p))
2506		return p->se.sum_exec_runtime;
2507#endif
2508
2509	rq = task_rq_lock(p, &flags);
2510	/*
2511	 * Must be ->curr _and_ ->on_rq.  If dequeued, we would
2512	 * project cycles that may never be accounted to this
2513	 * thread, breaking clock_gettime().
2514	 */
2515	if (task_current(rq, p) && task_on_rq_queued(p)) {
2516		update_rq_clock(rq);
2517		p->sched_class->update_curr(rq);
2518	}
2519	ns = p->se.sum_exec_runtime;
2520	task_rq_unlock(rq, p, &flags);
2521
2522	return ns;
2523}
2524
2525/*
2526 * This function gets called by the timer code, with HZ frequency.
2527 * We call it with interrupts disabled.
2528 */
2529void scheduler_tick(void)
2530{
2531	int cpu = smp_processor_id();
2532	struct rq *rq = cpu_rq(cpu);
2533	struct task_struct *curr = rq->curr;
2534
2535	sched_clock_tick();
2536
2537	raw_spin_lock(&rq->lock);
2538	update_rq_clock(rq);
2539	curr->sched_class->task_tick(rq, curr, 0);
2540	update_cpu_load_active(rq);
2541	raw_spin_unlock(&rq->lock);
2542
2543	perf_event_task_tick();
2544
2545#ifdef CONFIG_SMP
2546	rq->idle_balance = idle_cpu(cpu);
2547	trigger_load_balance(rq);
2548#endif
2549	rq_last_tick_reset(rq);
2550}
2551
2552#ifdef CONFIG_NO_HZ_FULL
2553/**
2554 * scheduler_tick_max_deferment
2555 *
2556 * Keep at least one tick per second when a single
2557 * active task is running because the scheduler doesn't
2558 * yet completely support full dynticks environment.
2559 *
2560 * This makes sure that uptime, CFS vruntime, load
2561 * balancing, etc... continue to move forward, even
2562 * with a very low granularity.
2563 *
2564 * Return: Maximum deferment in nanoseconds.
2565 */
2566u64 scheduler_tick_max_deferment(void)
2567{
2568	struct rq *rq = this_rq();
2569	unsigned long next, now = ACCESS_ONCE(jiffies);
2570
2571	next = rq->last_sched_tick + HZ;
2572
2573	if (time_before_eq(next, now))
2574		return 0;
2575
2576	return jiffies_to_nsecs(next - now);
2577}
2578#endif
2579
2580notrace unsigned long get_parent_ip(unsigned long addr)
2581{
2582	if (in_lock_functions(addr)) {
2583		addr = CALLER_ADDR2;
2584		if (in_lock_functions(addr))
2585			addr = CALLER_ADDR3;
2586	}
2587	return addr;
2588}
2589
2590#if defined(CONFIG_PREEMPT) && (defined(CONFIG_DEBUG_PREEMPT) || \
2591				defined(CONFIG_PREEMPT_TRACER))
2592
2593void preempt_count_add(int val)
2594{
2595#ifdef CONFIG_DEBUG_PREEMPT
2596	/*
2597	 * Underflow?
2598	 */
2599	if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
2600		return;
2601#endif
2602	__preempt_count_add(val);
2603#ifdef CONFIG_DEBUG_PREEMPT
2604	/*
2605	 * Spinlock count overflowing soon?
2606	 */
2607	DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
2608				PREEMPT_MASK - 10);
2609#endif
2610	if (preempt_count() == val) {
2611		unsigned long ip = get_parent_ip(CALLER_ADDR1);
2612#ifdef CONFIG_DEBUG_PREEMPT
2613		current->preempt_disable_ip = ip;
2614#endif
2615		trace_preempt_off(CALLER_ADDR0, ip);
2616	}
2617}
2618EXPORT_SYMBOL(preempt_count_add);
2619NOKPROBE_SYMBOL(preempt_count_add);
2620
2621void preempt_count_sub(int val)
2622{
2623#ifdef CONFIG_DEBUG_PREEMPT
2624	/*
2625	 * Underflow?
2626	 */
2627	if (DEBUG_LOCKS_WARN_ON(val > preempt_count()))
2628		return;
2629	/*
2630	 * Is the spinlock portion underflowing?
2631	 */
2632	if (DEBUG_LOCKS_WARN_ON((val < PREEMPT_MASK) &&
2633			!(preempt_count() & PREEMPT_MASK)))
2634		return;
2635#endif
2636
2637	if (preempt_count() == val)
2638		trace_preempt_on(CALLER_ADDR0, get_parent_ip(CALLER_ADDR1));
2639	__preempt_count_sub(val);
2640}
2641EXPORT_SYMBOL(preempt_count_sub);
2642NOKPROBE_SYMBOL(preempt_count_sub);
2643
2644#endif
2645
2646/*
2647 * Print scheduling while atomic bug:
2648 */
2649static noinline void __schedule_bug(struct task_struct *prev)
2650{
2651	if (oops_in_progress)
2652		return;
2653
2654	printk(KERN_ERR "BUG: scheduling while atomic: %s/%d/0x%08x\n",
2655		prev->comm, prev->pid, preempt_count());
2656
2657	debug_show_held_locks(prev);
2658	print_modules();
2659	if (irqs_disabled())
2660		print_irqtrace_events(prev);
2661#ifdef CONFIG_DEBUG_PREEMPT
2662	if (in_atomic_preempt_off()) {
2663		pr_err("Preemption disabled at:");
2664		print_ip_sym(current->preempt_disable_ip);
2665		pr_cont("\n");
2666	}
2667#endif
2668	dump_stack();
2669	add_taint(TAINT_WARN, LOCKDEP_STILL_OK);
2670}
2671
2672/*
2673 * Various schedule()-time debugging checks and statistics:
2674 */
2675static inline void schedule_debug(struct task_struct *prev)
2676{
2677#ifdef CONFIG_SCHED_STACK_END_CHECK
2678	BUG_ON(unlikely(task_stack_end_corrupted(prev)));
2679#endif
2680	/*
2681	 * Test if we are atomic. Since do_exit() needs to call into
2682	 * schedule() atomically, we ignore that path. Otherwise whine
2683	 * if we are scheduling when we should not.
2684	 */
2685	if (unlikely(in_atomic_preempt_off() && prev->state != TASK_DEAD))
2686		__schedule_bug(prev);
2687	rcu_sleep_check();
2688
2689	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
2690
2691	schedstat_inc(this_rq(), sched_count);
2692}
2693
2694/*
2695 * Pick up the highest-prio task:
2696 */
2697static inline struct task_struct *
2698pick_next_task(struct rq *rq, struct task_struct *prev)
2699{
2700	const struct sched_class *class = &fair_sched_class;
2701	struct task_struct *p;
2702
2703	/*
2704	 * Optimization: we know that if all tasks are in
2705	 * the fair class we can call that function directly:
2706	 */
2707	if (likely(prev->sched_class == class &&
2708		   rq->nr_running == rq->cfs.h_nr_running)) {
2709		p = fair_sched_class.pick_next_task(rq, prev);
2710		if (unlikely(p == RETRY_TASK))
2711			goto again;
2712
2713		/* assumes fair_sched_class->next == idle_sched_class */
2714		if (unlikely(!p))
2715			p = idle_sched_class.pick_next_task(rq, prev);
2716
2717		return p;
2718	}
2719
2720again:
2721	for_each_class(class) {
2722		p = class->pick_next_task(rq, prev);
2723		if (p) {
2724			if (unlikely(p == RETRY_TASK))
2725				goto again;
2726			return p;
2727		}
2728	}
2729
2730	BUG(); /* the idle class will always have a runnable task */
2731}
2732
2733/*
2734 * __schedule() is the main scheduler function.
2735 *
2736 * The main means of driving the scheduler and thus entering this function are:
2737 *
2738 *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
2739 *
2740 *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
2741 *      paths. For example, see arch/x86/entry_64.S.
2742 *
2743 *      To drive preemption between tasks, the scheduler sets the flag in timer
2744 *      interrupt handler scheduler_tick().
2745 *
2746 *   3. Wakeups don't really cause entry into schedule(). They add a
2747 *      task to the run-queue and that's it.
2748 *
2749 *      Now, if the new task added to the run-queue preempts the current
2750 *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
2751 *      called on the nearest possible occasion:
2752 *
2753 *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
2754 *
2755 *         - in syscall or exception context, at the next outmost
2756 *           preempt_enable(). (this might be as soon as the wake_up()'s
2757 *           spin_unlock()!)
2758 *
2759 *         - in IRQ context, return from interrupt-handler to
2760 *           preemptible context
2761 *
2762 *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
2763 *         then at the next:
2764 *
2765 *          - cond_resched() call
2766 *          - explicit schedule() call
2767 *          - return from syscall or exception to user-space
2768 *          - return from interrupt-handler to user-space
2769 */
2770static void __sched __schedule(void)
2771{
2772	struct task_struct *prev, *next;
2773	unsigned long *switch_count;
2774	struct rq *rq;
2775	int cpu;
2776
2777need_resched:
2778	preempt_disable();
2779	cpu = smp_processor_id();
2780	rq = cpu_rq(cpu);
2781	rcu_note_context_switch(cpu);
2782	prev = rq->curr;
2783
2784	schedule_debug(prev);
2785
2786	if (sched_feat(HRTICK))
2787		hrtick_clear(rq);
2788
2789	/*
2790	 * Make sure that signal_pending_state()->signal_pending() below
2791	 * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
2792	 * done by the caller to avoid the race with signal_wake_up().
2793	 */
2794	smp_mb__before_spinlock();
2795	raw_spin_lock_irq(&rq->lock);
2796
2797	switch_count = &prev->nivcsw;
2798	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
2799		if (unlikely(signal_pending_state(prev->state, prev))) {
2800			prev->state = TASK_RUNNING;
2801		} else {
2802			deactivate_task(rq, prev, DEQUEUE_SLEEP);
2803			prev->on_rq = 0;
2804
2805			/*
2806			 * If a worker went to sleep, notify and ask workqueue
2807			 * whether it wants to wake up a task to maintain
2808			 * concurrency.
2809			 */
2810			if (prev->flags & PF_WQ_WORKER) {
2811				struct task_struct *to_wakeup;
2812
2813				to_wakeup = wq_worker_sleeping(prev, cpu);
2814				if (to_wakeup)
2815					try_to_wake_up_local(to_wakeup);
2816			}
2817		}
2818		switch_count = &prev->nvcsw;
2819	}
2820
2821	if (task_on_rq_queued(prev) || rq->skip_clock_update < 0)
2822		update_rq_clock(rq);
2823
2824	next = pick_next_task(rq, prev);
2825	clear_tsk_need_resched(prev);
2826	clear_preempt_need_resched();
2827	rq->skip_clock_update = 0;
2828
2829	if (likely(prev != next)) {
2830		rq->nr_switches++;
2831		rq->curr = next;
2832		++*switch_count;
2833
2834		context_switch(rq, prev, next); /* unlocks the rq */
2835		/*
2836		 * The context switch have flipped the stack from under us
2837		 * and restored the local variables which were saved when
2838		 * this task called schedule() in the past. prev == current
2839		 * is still correct, but it can be moved to another cpu/rq.
2840		 */
2841		cpu = smp_processor_id();
2842		rq = cpu_rq(cpu);
2843	} else
2844		raw_spin_unlock_irq(&rq->lock);
2845
2846	post_schedule(rq);
2847
2848	sched_preempt_enable_no_resched();
2849	if (need_resched())
2850		goto need_resched;
2851}
2852
2853static inline void sched_submit_work(struct task_struct *tsk)
2854{
2855	if (!tsk->state || tsk_is_pi_blocked(tsk))
2856		return;
2857	/*
2858	 * If we are going to sleep and we have plugged IO queued,
2859	 * make sure to submit it to avoid deadlocks.
2860	 */
2861	if (blk_needs_flush_plug(tsk))
2862		blk_schedule_flush_plug(tsk);
2863}
2864
2865asmlinkage __visible void __sched schedule(void)
2866{
2867	struct task_struct *tsk = current;
2868
2869	sched_submit_work(tsk);
2870	__schedule();
2871}
2872EXPORT_SYMBOL(schedule);
2873
2874#ifdef CONFIG_CONTEXT_TRACKING
2875asmlinkage __visible void __sched schedule_user(void)
2876{
2877	/*
2878	 * If we come here after a random call to set_need_resched(),
2879	 * or we have been woken up remotely but the IPI has not yet arrived,
2880	 * we haven't yet exited the RCU idle mode. Do it here manually until
2881	 * we find a better solution.
2882	 *
2883	 * NB: There are buggy callers of this function.  Ideally we
2884	 * should warn if prev_state != IN_USER, but that will trigger
2885	 * too frequently to make sense yet.
2886	 */
2887	enum ctx_state prev_state = exception_enter();
2888	schedule();
2889	exception_exit(prev_state);
2890}
2891#endif
2892
2893/**
2894 * schedule_preempt_disabled - called with preemption disabled
2895 *
2896 * Returns with preemption disabled. Note: preempt_count must be 1
2897 */
2898void __sched schedule_preempt_disabled(void)
2899{
2900	sched_preempt_enable_no_resched();
2901	schedule();
2902	preempt_disable();
2903}
2904
2905#ifdef CONFIG_PREEMPT
2906/*
2907 * this is the entry point to schedule() from in-kernel preemption
2908 * off of preempt_enable. Kernel preemptions off return from interrupt
2909 * occur there and call schedule directly.
2910 */
2911asmlinkage __visible void __sched notrace preempt_schedule(void)
2912{
2913	/*
2914	 * If there is a non-zero preempt_count or interrupts are disabled,
2915	 * we do not want to preempt the current task. Just return..
2916	 */
2917	if (likely(!preemptible()))
2918		return;
2919
2920	do {
2921		__preempt_count_add(PREEMPT_ACTIVE);
2922		__schedule();
2923		__preempt_count_sub(PREEMPT_ACTIVE);
2924
2925		/*
2926		 * Check again in case we missed a preemption opportunity
2927		 * between schedule and now.
2928		 */
2929		barrier();
2930	} while (need_resched());
2931}
2932NOKPROBE_SYMBOL(preempt_schedule);
2933EXPORT_SYMBOL(preempt_schedule);
2934
2935#ifdef CONFIG_CONTEXT_TRACKING
2936/**
2937 * preempt_schedule_context - preempt_schedule called by tracing
2938 *
2939 * The tracing infrastructure uses preempt_enable_notrace to prevent
2940 * recursion and tracing preempt enabling caused by the tracing
2941 * infrastructure itself. But as tracing can happen in areas coming
2942 * from userspace or just about to enter userspace, a preempt enable
2943 * can occur before user_exit() is called. This will cause the scheduler
2944 * to be called when the system is still in usermode.
2945 *
2946 * To prevent this, the preempt_enable_notrace will use this function
2947 * instead of preempt_schedule() to exit user context if needed before
2948 * calling the scheduler.
2949 */
2950asmlinkage __visible void __sched notrace preempt_schedule_context(void)
2951{
2952	enum ctx_state prev_ctx;
2953
2954	if (likely(!preemptible()))
2955		return;
2956
2957	do {
2958		__preempt_count_add(PREEMPT_ACTIVE);
2959		/*
2960		 * Needs preempt disabled in case user_exit() is traced
2961		 * and the tracer calls preempt_enable_notrace() causing
2962		 * an infinite recursion.
2963		 */
2964		prev_ctx = exception_enter();
2965		__schedule();
2966		exception_exit(prev_ctx);
2967
2968		__preempt_count_sub(PREEMPT_ACTIVE);
2969		barrier();
2970	} while (need_resched());
2971}
2972EXPORT_SYMBOL_GPL(preempt_schedule_context);
2973#endif /* CONFIG_CONTEXT_TRACKING */
2974
2975#endif /* CONFIG_PREEMPT */
2976
2977/*
2978 * this is the entry point to schedule() from kernel preemption
2979 * off of irq context.
2980 * Note, that this is called and return with irqs disabled. This will
2981 * protect us against recursive calling from irq.
2982 */
2983asmlinkage __visible void __sched preempt_schedule_irq(void)
2984{
2985	enum ctx_state prev_state;
2986
2987	/* Catch callers which need to be fixed */
2988	BUG_ON(preempt_count() || !irqs_disabled());
2989
2990	prev_state = exception_enter();
2991
2992	do {
2993		__preempt_count_add(PREEMPT_ACTIVE);
2994		local_irq_enable();
2995		__schedule();
2996		local_irq_disable();
2997		__preempt_count_sub(PREEMPT_ACTIVE);
2998
2999		/*
3000		 * Check again in case we missed a preemption opportunity
3001		 * between schedule and now.
3002		 */
3003		barrier();
3004	} while (need_resched());
3005
3006	exception_exit(prev_state);
3007}
3008
3009int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
3010			  void *key)
3011{
3012	return try_to_wake_up(curr->private, mode, wake_flags);
3013}
3014EXPORT_SYMBOL(default_wake_function);
3015
3016#ifdef CONFIG_RT_MUTEXES
3017
3018/*
3019 * rt_mutex_setprio - set the current priority of a task
3020 * @p: task
3021 * @prio: prio value (kernel-internal form)
3022 *
3023 * This function changes the 'effective' priority of a task. It does
3024 * not touch ->normal_prio like __setscheduler().
3025 *
3026 * Used by the rt_mutex code to implement priority inheritance
3027 * logic. Call site only calls if the priority of the task changed.
3028 */
3029void rt_mutex_setprio(struct task_struct *p, int prio)
3030{
3031	int oldprio, queued, running, enqueue_flag = 0;
3032	struct rq *rq;
3033	const struct sched_class *prev_class;
3034
3035	BUG_ON(prio > MAX_PRIO);
3036
3037	rq = __task_rq_lock(p);
3038
3039	/*
3040	 * Idle task boosting is a nono in general. There is one
3041	 * exception, when PREEMPT_RT and NOHZ is active:
3042	 *
3043	 * The idle task calls get_next_timer_interrupt() and holds
3044	 * the timer wheel base->lock on the CPU and another CPU wants
3045	 * to access the timer (probably to cancel it). We can safely
3046	 * ignore the boosting request, as the idle CPU runs this code
3047	 * with interrupts disabled and will complete the lock
3048	 * protected section without being interrupted. So there is no
3049	 * real need to boost.
3050	 */
3051	if (unlikely(p == rq->idle)) {
3052		WARN_ON(p != rq->curr);
3053		WARN_ON(p->pi_blocked_on);
3054		goto out_unlock;
3055	}
3056
3057	trace_sched_pi_setprio(p, prio);
3058	oldprio = p->prio;
3059	prev_class = p->sched_class;
3060	queued = task_on_rq_queued(p);
3061	running = task_current(rq, p);
3062	if (queued)
3063		dequeue_task(rq, p, 0);
3064	if (running)
3065		put_prev_task(rq, p);
3066
3067	/*
3068	 * Boosting condition are:
3069	 * 1. -rt task is running and holds mutex A
3070	 *      --> -dl task blocks on mutex A
3071	 *
3072	 * 2. -dl task is running and holds mutex A
3073	 *      --> -dl task blocks on mutex A and could preempt the
3074	 *          running task
3075	 */
3076	if (dl_prio(prio)) {
3077		struct task_struct *pi_task = rt_mutex_get_top_task(p);
3078		if (!dl_prio(p->normal_prio) ||
3079		    (pi_task && dl_entity_preempt(&pi_task->dl, &p->dl))) {
3080			p->dl.dl_boosted = 1;
3081			p->dl.dl_throttled = 0;
3082			enqueue_flag = ENQUEUE_REPLENISH;
3083		} else
3084			p->dl.dl_boosted = 0;
3085		p->sched_class = &dl_sched_class;
3086	} else if (rt_prio(prio)) {
3087		if (dl_prio(oldprio))
3088			p->dl.dl_boosted = 0;
3089		if (oldprio < prio)
3090			enqueue_flag = ENQUEUE_HEAD;
3091		p->sched_class = &rt_sched_class;
3092	} else {
3093		if (dl_prio(oldprio))
3094			p->dl.dl_boosted = 0;
3095		p->sched_class = &fair_sched_class;
3096	}
3097
3098	p->prio = prio;
3099
3100	if (running)
3101		p->sched_class->set_curr_task(rq);
3102	if (queued)
3103		enqueue_task(rq, p, enqueue_flag);
3104
3105	check_class_changed(rq, p, prev_class, oldprio);
3106out_unlock:
3107	__task_rq_unlock(rq);
3108}
3109#endif
3110
3111void set_user_nice(struct task_struct *p, long nice)
3112{
3113	int old_prio, delta, queued;
3114	unsigned long flags;
3115	struct rq *rq;
3116
3117	if (task_nice(p) == nice || nice < MIN_NICE || nice > MAX_NICE)
3118		return;
3119	/*
3120	 * We have to be careful, if called from sys_setpriority(),
3121	 * the task might be in the middle of scheduling on another CPU.
3122	 */
3123	rq = task_rq_lock(p, &flags);
3124	/*
3125	 * The RT priorities are set via sched_setscheduler(), but we still
3126	 * allow the 'normal' nice value to be set - but as expected
3127	 * it wont have any effect on scheduling until the task is
3128	 * SCHED_DEADLINE, SCHED_FIFO or SCHED_RR:
3129	 */
3130	if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
3131		p->static_prio = NICE_TO_PRIO(nice);
3132		goto out_unlock;
3133	}
3134	queued = task_on_rq_queued(p);
3135	if (queued)
3136		dequeue_task(rq, p, 0);
3137
3138	p->static_prio = NICE_TO_PRIO(nice);
3139	set_load_weight(p);
3140	old_prio = p->prio;
3141	p->prio = effective_prio(p);
3142	delta = p->prio - old_prio;
3143
3144	if (queued) {
3145		enqueue_task(rq, p, 0);
3146		/*
3147		 * If the task increased its priority or is running and
3148		 * lowered its priority, then reschedule its CPU:
3149		 */
3150		if (delta < 0 || (delta > 0 && task_running(rq, p)))
3151			resched_curr(rq);
3152	}
3153out_unlock:
3154	task_rq_unlock(rq, p, &flags);
3155}
3156EXPORT_SYMBOL(set_user_nice);
3157
3158/*
3159 * can_nice - check if a task can reduce its nice value
3160 * @p: task
3161 * @nice: nice value
3162 */
3163int can_nice(const struct task_struct *p, const int nice)
3164{
3165	/* convert nice value [19,-20] to rlimit style value [1,40] */
3166	int nice_rlim = nice_to_rlimit(nice);
3167
3168	return (nice_rlim <= task_rlimit(p, RLIMIT_NICE) ||
3169		capable(CAP_SYS_NICE));
3170}
3171
3172#ifdef __ARCH_WANT_SYS_NICE
3173
3174/*
3175 * sys_nice - change the priority of the current process.
3176 * @increment: priority increment
3177 *
3178 * sys_setpriority is a more generic, but much slower function that
3179 * does similar things.
3180 */
3181SYSCALL_DEFINE1(nice, int, increment)
3182{
3183	long nice, retval;
3184
3185	/*
3186	 * Setpriority might change our priority at the same moment.
3187	 * We don't have to worry. Conceptually one call occurs first
3188	 * and we have a single winner.
3189	 */
3190	increment = clamp(increment, -NICE_WIDTH, NICE_WIDTH);
3191	nice = task_nice(current) + increment;
3192
3193	nice = clamp_val(nice, MIN_NICE, MAX_NICE);
3194	if (increment < 0 && !can_nice(current, nice))
3195		return -EPERM;
3196
3197	retval = security_task_setnice(current, nice);
3198	if (retval)
3199		return retval;
3200
3201	set_user_nice(current, nice);
3202	return 0;
3203}
3204
3205#endif
3206
3207/**
3208 * task_prio - return the priority value of a given task.
3209 * @p: the task in question.
3210 *
3211 * Return: The priority value as seen by users in /proc.
3212 * RT tasks are offset by -200. Normal tasks are centered
3213 * around 0, value goes from -16 to +15.
3214 */
3215int task_prio(const struct task_struct *p)
3216{
3217	return p->prio - MAX_RT_PRIO;
3218}
3219
3220/**
3221 * idle_cpu - is a given cpu idle currently?
3222 * @cpu: the processor in question.
3223 *
3224 * Return: 1 if the CPU is currently idle. 0 otherwise.
3225 */
3226int idle_cpu(int cpu)
3227{
3228	struct rq *rq = cpu_rq(cpu);
3229
3230	if (rq->curr != rq->idle)
3231		return 0;
3232
3233	if (rq->nr_running)
3234		return 0;
3235
3236#ifdef CONFIG_SMP
3237	if (!llist_empty(&rq->wake_list))
3238		return 0;
3239#endif
3240
3241	return 1;
3242}
3243
3244/**
3245 * idle_task - return the idle task for a given cpu.
3246 * @cpu: the processor in question.
3247 *
3248 * Return: The idle task for the cpu @cpu.
3249 */
3250struct task_struct *idle_task(int cpu)
3251{
3252	return cpu_rq(cpu)->idle;
3253}
3254
3255/**
3256 * find_process_by_pid - find a process with a matching PID value.
3257 * @pid: the pid in question.
3258 *
3259 * The task of @pid, if found. %NULL otherwise.
3260 */
3261static struct task_struct *find_process_by_pid(pid_t pid)
3262{
3263	return pid ? find_task_by_vpid(pid) : current;
3264}
3265
3266/*
3267 * This function initializes the sched_dl_entity of a newly becoming
3268 * SCHED_DEADLINE task.
3269 *
3270 * Only the static values are considered here, the actual runtime and the
3271 * absolute deadline will be properly calculated when the task is enqueued
3272 * for the first time with its new policy.
3273 */
3274static void
3275__setparam_dl(struct task_struct *p, const struct sched_attr *attr)
3276{
3277	struct sched_dl_entity *dl_se = &p->dl;
3278
3279	init_dl_task_timer(dl_se);
3280	dl_se->dl_runtime = attr->sched_runtime;
3281	dl_se->dl_deadline = attr->sched_deadline;
3282	dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
3283	dl_se->flags = attr->sched_flags;
3284	dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
3285	dl_se->dl_throttled = 0;
3286	dl_se->dl_new = 1;
3287	dl_se->dl_yielded = 0;
3288}
3289
3290/*
3291 * sched_setparam() passes in -1 for its policy, to let the functions
3292 * it calls know not to change it.
3293 */
3294#define SETPARAM_POLICY	-1
3295
3296static void __setscheduler_params(struct task_struct *p,
3297		const struct sched_attr *attr)
3298{
3299	int policy = attr->sched_policy;
3300
3301	if (policy == SETPARAM_POLICY)
3302		policy = p->policy;
3303
3304	p->policy = policy;
3305
3306	if (dl_policy(policy))
3307		__setparam_dl(p, attr);
3308	else if (fair_policy(policy))
3309		p->static_prio = NICE_TO_PRIO(attr->sched_nice);
3310
3311	/*
3312	 * __sched_setscheduler() ensures attr->sched_priority == 0 when
3313	 * !rt_policy. Always setting this ensures that things like
3314	 * getparam()/getattr() don't report silly values for !rt tasks.
3315	 */
3316	p->rt_priority = attr->sched_priority;
3317	p->normal_prio = normal_prio(p);
3318	set_load_weight(p);
3319}
3320
3321/* Actually do priority change: must hold pi & rq lock. */
3322static void __setscheduler(struct rq *rq, struct task_struct *p,
3323			   const struct sched_attr *attr)
3324{
3325	__setscheduler_params(p, attr);
3326
3327	/*
3328	 * If we get here, there was no pi waiters boosting the
3329	 * task. It is safe to use the normal prio.
3330	 */
3331	p->prio = normal_prio(p);
3332
3333	if (dl_prio(p->prio))
3334		p->sched_class = &dl_sched_class;
3335	else if (rt_prio(p->prio))
3336		p->sched_class = &rt_sched_class;
3337	else
3338		p->sched_class = &fair_sched_class;
3339}
3340
3341static void
3342__getparam_dl(struct task_struct *p, struct sched_attr *attr)
3343{
3344	struct sched_dl_entity *dl_se = &p->dl;
3345
3346	attr->sched_priority = p->rt_priority;
3347	attr->sched_runtime = dl_se->dl_runtime;
3348	attr->sched_deadline = dl_se->dl_deadline;
3349	attr->sched_period = dl_se->dl_period;
3350	attr->sched_flags = dl_se->flags;
3351}
3352
3353/*
3354 * This function validates the new parameters of a -deadline task.
3355 * We ask for the deadline not being zero, and greater or equal
3356 * than the runtime, as well as the period of being zero or
3357 * greater than deadline. Furthermore, we have to be sure that
3358 * user parameters are above the internal resolution of 1us (we
3359 * check sched_runtime only since it is always the smaller one) and
3360 * below 2^63 ns (we have to check both sched_deadline and
3361 * sched_period, as the latter can be zero).
3362 */
3363static bool
3364__checkparam_dl(const struct sched_attr *attr)
3365{
3366	/* deadline != 0 */
3367	if (attr->sched_deadline == 0)
3368		return false;
3369
3370	/*
3371	 * Since we truncate DL_SCALE bits, make sure we're at least
3372	 * that big.
3373	 */
3374	if (attr->sched_runtime < (1ULL << DL_SCALE))
3375		return false;
3376
3377	/*
3378	 * Since we use the MSB for wrap-around and sign issues, make
3379	 * sure it's not set (mind that period can be equal to zero).
3380	 */
3381	if (attr->sched_deadline & (1ULL << 63) ||
3382	    attr->sched_period & (1ULL << 63))
3383		return false;
3384
3385	/* runtime <= deadline <= period (if period != 0) */
3386	if ((attr->sched_period != 0 &&
3387	     attr->sched_period < attr->sched_deadline) ||
3388	    attr->sched_deadline < attr->sched_runtime)
3389		return false;
3390
3391	return true;
3392}
3393
3394/*
3395 * check the target process has a UID that matches the current process's
3396 */
3397static bool check_same_owner(struct task_struct *p)
3398{
3399	const struct cred *cred = current_cred(), *pcred;
3400	bool match;
3401
3402	rcu_read_lock();
3403	pcred = __task_cred(p);
3404	match = (uid_eq(cred->euid, pcred->euid) ||
3405		 uid_eq(cred->euid, pcred->uid));
3406	rcu_read_unlock();
3407	return match;
3408}
3409
3410static int __sched_setscheduler(struct task_struct *p,
3411				const struct sched_attr *attr,
3412				bool user)
3413{
3414	int newprio = dl_policy(attr->sched_policy) ? MAX_DL_PRIO - 1 :
3415		      MAX_RT_PRIO - 1 - attr->sched_priority;
3416	int retval, oldprio, oldpolicy = -1, queued, running;
3417	int policy = attr->sched_policy;
3418	unsigned long flags;
3419	const struct sched_class *prev_class;
3420	struct rq *rq;
3421	int reset_on_fork;
3422
3423	/* may grab non-irq protected spin_locks */
3424	BUG_ON(in_interrupt());
3425recheck:
3426	/* double check policy once rq lock held */
3427	if (policy < 0) {
3428		reset_on_fork = p->sched_reset_on_fork;
3429		policy = oldpolicy = p->policy;
3430	} else {
3431		reset_on_fork = !!(attr->sched_flags & SCHED_FLAG_RESET_ON_FORK);
3432
3433		if (policy != SCHED_DEADLINE &&
3434				policy != SCHED_FIFO && policy != SCHED_RR &&
3435				policy != SCHED_NORMAL && policy != SCHED_BATCH &&
3436				policy != SCHED_IDLE)
3437			return -EINVAL;
3438	}
3439
3440	if (attr->sched_flags & ~(SCHED_FLAG_RESET_ON_FORK))
3441		return -EINVAL;
3442
3443	/*
3444	 * Valid priorities for SCHED_FIFO and SCHED_RR are
3445	 * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
3446	 * SCHED_BATCH and SCHED_IDLE is 0.
3447	 */
3448	if ((p->mm && attr->sched_priority > MAX_USER_RT_PRIO-1) ||
3449	    (!p->mm && attr->sched_priority > MAX_RT_PRIO-1))
3450		return -EINVAL;
3451	if ((dl_policy(policy) && !__checkparam_dl(attr)) ||
3452	    (rt_policy(policy) != (attr->sched_priority != 0)))
3453		return -EINVAL;
3454
3455	/*
3456	 * Allow unprivileged RT tasks to decrease priority:
3457	 */
3458	if (user && !capable(CAP_SYS_NICE)) {
3459		if (fair_policy(policy)) {
3460			if (attr->sched_nice < task_nice(p) &&
3461			    !can_nice(p, attr->sched_nice))
3462				return -EPERM;
3463		}
3464
3465		if (rt_policy(policy)) {
3466			unsigned long rlim_rtprio =
3467					task_rlimit(p, RLIMIT_RTPRIO);
3468
3469			/* can't set/change the rt policy */
3470			if (policy != p->policy && !rlim_rtprio)
3471				return -EPERM;
3472
3473			/* can't increase priority */
3474			if (attr->sched_priority > p->rt_priority &&
3475			    attr->sched_priority > rlim_rtprio)
3476				return -EPERM;
3477		}
3478
3479		 /*
3480		  * Can't set/change SCHED_DEADLINE policy at all for now
3481		  * (safest behavior); in the future we would like to allow
3482		  * unprivileged DL tasks to increase their relative deadline
3483		  * or reduce their runtime (both ways reducing utilization)
3484		  */
3485		if (dl_policy(policy))
3486			return -EPERM;
3487
3488		/*
3489		 * Treat SCHED_IDLE as nice 20. Only allow a switch to
3490		 * SCHED_NORMAL if the RLIMIT_NICE would normally permit it.
3491		 */
3492		if (p->policy == SCHED_IDLE && policy != SCHED_IDLE) {
3493			if (!can_nice(p, task_nice(p)))
3494				return -EPERM;
3495		}
3496
3497		/* can't change other user's priorities */
3498		if (!check_same_owner(p))
3499			return -EPERM;
3500
3501		/* Normal users shall not reset the sched_reset_on_fork flag */
3502		if (p->sched_reset_on_fork && !reset_on_fork)
3503			return -EPERM;
3504	}
3505
3506	if (user) {
3507		retval = security_task_setscheduler(p);
3508		if (retval)
3509			return retval;
3510	}
3511
3512	/*
3513	 * make sure no PI-waiters arrive (or leave) while we are
3514	 * changing the priority of the task:
3515	 *
3516	 * To be able to change p->policy safely, the appropriate
3517	 * runqueue lock must be held.
3518	 */
3519	rq = task_rq_lock(p, &flags);
3520
3521	/*
3522	 * Changing the policy of the stop threads its a very bad idea
3523	 */
3524	if (p == rq->stop) {
3525		task_rq_unlock(rq, p, &flags);
3526		return -EINVAL;
3527	}
3528
3529	/*
3530	 * If not changing anything there's no need to proceed further,
3531	 * but store a possible modification of reset_on_fork.
3532	 */
3533	if (unlikely(policy == p->policy)) {
3534		if (fair_policy(policy) && attr->sched_nice != task_nice(p))
3535			goto change;
3536		if (rt_policy(policy) && attr->sched_priority != p->rt_priority)
3537			goto change;
3538		if (dl_policy(policy))
3539			goto change;
3540
3541		p->sched_reset_on_fork = reset_on_fork;
3542		task_rq_unlock(rq, p, &flags);
3543		return 0;
3544	}
3545change:
3546
3547	if (user) {
3548#ifdef CONFIG_RT_GROUP_SCHED
3549		/*
3550		 * Do not allow realtime tasks into groups that have no runtime
3551		 * assigned.
3552		 */
3553		if (rt_bandwidth_enabled() && rt_policy(policy) &&
3554				task_group(p)->rt_bandwidth.rt_runtime == 0 &&
3555				!task_group_is_autogroup(task_group(p))) {
3556			task_rq_unlock(rq, p, &flags);
3557			return -EPERM;
3558		}
3559#endif
3560#ifdef CONFIG_SMP
3561		if (dl_bandwidth_enabled() && dl_policy(policy)) {
3562			cpumask_t *span = rq->rd->span;
3563
3564			/*
3565			 * Don't allow tasks with an affinity mask smaller than
3566			 * the entire root_domain to become SCHED_DEADLINE. We
3567			 * will also fail if there's no bandwidth available.
3568			 */
3569			if (!cpumask_subset(span, &p->cpus_allowed) ||
3570			    rq->rd->dl_bw.bw == 0) {
3571				task_rq_unlock(rq, p, &flags);
3572				return -EPERM;
3573			}
3574		}
3575#endif
3576	}
3577
3578	/* recheck policy now with rq lock held */
3579	if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
3580		policy = oldpolicy = -1;
3581		task_rq_unlock(rq, p, &flags);
3582		goto recheck;
3583	}
3584
3585	/*
3586	 * If setscheduling to SCHED_DEADLINE (or changing the parameters
3587	 * of a SCHED_DEADLINE task) we need to check if enough bandwidth
3588	 * is available.
3589	 */
3590	if ((dl_policy(policy) || dl_task(p)) && dl_overflow(p, policy, attr)) {
3591		task_rq_unlock(rq, p, &flags);
3592		return -EBUSY;
3593	}
3594
3595	p->sched_reset_on_fork = reset_on_fork;
3596	oldprio = p->prio;
3597
3598	/*
3599	 * Special case for priority boosted tasks.
3600	 *
3601	 * If the new priority is lower or equal (user space view)
3602	 * than the current (boosted) priority, we just store the new
3603	 * normal parameters and do not touch the scheduler class and
3604	 * the runqueue. This will be done when the task deboost
3605	 * itself.
3606	 */
3607	if (rt_mutex_check_prio(p, newprio)) {
3608		__setscheduler_params(p, attr);
3609		task_rq_unlock(rq, p, &flags);
3610		return 0;
3611	}
3612
3613	queued = task_on_rq_queued(p);
3614	running = task_current(rq, p);
3615	if (queued)
3616		dequeue_task(rq, p, 0);
3617	if (running)
3618		put_prev_task(rq, p);
3619
3620	prev_class = p->sched_class;
3621	__setscheduler(rq, p, attr);
3622
3623	if (running)
3624		p->sched_class->set_curr_task(rq);
3625	if (queued) {
3626		/*
3627		 * We enqueue to tail when the priority of a task is
3628		 * increased (user space view).
3629		 */
3630		enqueue_task(rq, p, oldprio <= p->prio ? ENQUEUE_HEAD : 0);
3631	}
3632
3633	check_class_changed(rq, p, prev_class, oldprio);
3634	task_rq_unlock(rq, p, &flags);
3635
3636	rt_mutex_adjust_pi(p);
3637
3638	return 0;
3639}
3640
3641static int _sched_setscheduler(struct task_struct *p, int policy,
3642			       const struct sched_param *param, bool check)
3643{
3644	struct sched_attr attr = {
3645		.sched_policy   = policy,
3646		.sched_priority = param->sched_priority,
3647		.sched_nice	= PRIO_TO_NICE(p->static_prio),
3648	};
3649
3650	/* Fixup the legacy SCHED_RESET_ON_FORK hack. */
3651	if ((policy != SETPARAM_POLICY) && (policy & SCHED_RESET_ON_FORK)) {
3652		attr.sched_flags |= SCHED_FLAG_RESET_ON_FORK;
3653		policy &= ~SCHED_RESET_ON_FORK;
3654		attr.sched_policy = policy;
3655	}
3656
3657	return __sched_setscheduler(p, &attr, check);
3658}
3659/**
3660 * sched_setscheduler - change the scheduling policy and/or RT priority of a thread.
3661 * @p: the task in question.
3662 * @policy: new policy.
3663 * @param: structure containing the new RT priority.
3664 *
3665 * Return: 0 on success. An error code otherwise.
3666 *
3667 * NOTE that the task may be already dead.
3668 */
3669int sched_setscheduler(struct task_struct *p, int policy,
3670		       const struct sched_param *param)
3671{
3672	return _sched_setscheduler(p, policy, param, true);
3673}
3674EXPORT_SYMBOL_GPL(sched_setscheduler);
3675
3676int sched_setattr(struct task_struct *p, const struct sched_attr *attr)
3677{
3678	return __sched_setscheduler(p, attr, true);
3679}
3680EXPORT_SYMBOL_GPL(sched_setattr);
3681
3682/**
3683 * sched_setscheduler_nocheck - change the scheduling policy and/or RT priority of a thread from kernelspace.
3684 * @p: the task in question.
3685 * @policy: new policy.
3686 * @param: structure containing the new RT priority.
3687 *
3688 * Just like sched_setscheduler, only don't bother checking if the
3689 * current context has permission.  For example, this is needed in
3690 * stop_machine(): we create temporary high priority worker threads,
3691 * but our caller might not have that capability.
3692 *
3693 * Return: 0 on success. An error code otherwise.
3694 */
3695int sched_setscheduler_nocheck(struct task_struct *p, int policy,
3696			       const struct sched_param *param)
3697{
3698	return _sched_setscheduler(p, policy, param, false);
3699}
3700
3701static int
3702do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
3703{
3704	struct sched_param lparam;
3705	struct task_struct *p;
3706	int retval;
3707
3708	if (!param || pid < 0)
3709		return -EINVAL;
3710	if (copy_from_user(&lparam, param, sizeof(struct sched_param)))
3711		return -EFAULT;
3712
3713	rcu_read_lock();
3714	retval = -ESRCH;
3715	p = find_process_by_pid(pid);
3716	if (p != NULL)
3717		retval = sched_setscheduler(p, policy, &lparam);
3718	rcu_read_unlock();
3719
3720	return retval;
3721}
3722
3723/*
3724 * Mimics kernel/events/core.c perf_copy_attr().
3725 */
3726static int sched_copy_attr(struct sched_attr __user *uattr,
3727			   struct sched_attr *attr)
3728{
3729	u32 size;
3730	int ret;
3731
3732	if (!access_ok(VERIFY_WRITE, uattr, SCHED_ATTR_SIZE_VER0))
3733		return -EFAULT;
3734
3735	/*
3736	 * zero the full structure, so that a short copy will be nice.
3737	 */
3738	memset(attr, 0, sizeof(*attr));
3739
3740	ret = get_user(size, &uattr->size);
3741	if (ret)
3742		return ret;
3743
3744	if (size > PAGE_SIZE)	/* silly large */
3745		goto err_size;
3746
3747	if (!size)		/* abi compat */
3748		size = SCHED_ATTR_SIZE_VER0;
3749
3750	if (size < SCHED_ATTR_SIZE_VER0)
3751		goto err_size;
3752
3753	/*
3754	 * If we're handed a bigger struct than we know of,
3755	 * ensure all the unknown bits are 0 - i.e. new
3756	 * user-space does not rely on any kernel feature
3757	 * extensions we dont know about yet.
3758	 */
3759	if (size > sizeof(*attr)) {
3760		unsigned char __user *addr;
3761		unsigned char __user *end;
3762		unsigned char val;
3763
3764		addr = (void __user *)uattr + sizeof(*attr);
3765		end  = (void __user *)uattr + size;
3766
3767		for (; addr < end; addr++) {
3768			ret = get_user(val, addr);
3769			if (ret)
3770				return ret;
3771			if (val)
3772				goto err_size;
3773		}
3774		size = sizeof(*attr);
3775	}
3776
3777	ret = copy_from_user(attr, uattr, size);
3778	if (ret)
3779		return -EFAULT;
3780
3781	/*
3782	 * XXX: do we want to be lenient like existing syscalls; or do we want
3783	 * to be strict and return an error on out-of-bounds values?
3784	 */
3785	attr->sched_nice = clamp(attr->sched_nice, MIN_NICE, MAX_NICE);
3786
3787	return 0;
3788
3789err_size:
3790	put_user(sizeof(*attr), &uattr->size);
3791	return -E2BIG;
3792}
3793
3794/**
3795 * sys_sched_setscheduler - set/change the scheduler policy and RT priority
3796 * @pid: the pid in question.
3797 * @policy: new policy.
3798 * @param: structure containing the new RT priority.
3799 *
3800 * Return: 0 on success. An error code otherwise.
3801 */
3802SYSCALL_DEFINE3(sched_setscheduler, pid_t, pid, int, policy,
3803		struct sched_param __user *, param)
3804{
3805	/* negative values for policy are not valid */
3806	if (policy < 0)
3807		return -EINVAL;
3808
3809	return do_sched_setscheduler(pid, policy, param);
3810}
3811
3812/**
3813 * sys_sched_setparam - set/change the RT priority of a thread
3814 * @pid: the pid in question.
3815 * @param: structure containing the new RT priority.
3816 *
3817 * Return: 0 on success. An error code otherwise.
3818 */
3819SYSCALL_DEFINE2(sched_setparam, pid_t, pid, struct sched_param __user *, param)
3820{
3821	return do_sched_setscheduler(pid, SETPARAM_POLICY, param);
3822}
3823
3824/**
3825 * sys_sched_setattr - same as above, but with extended sched_attr
3826 * @pid: the pid in question.
3827 * @uattr: structure containing the extended parameters.
3828 * @flags: for future extension.
3829 */
3830SYSCALL_DEFINE3(sched_setattr, pid_t, pid, struct sched_attr __user *, uattr,
3831			       unsigned int, flags)
3832{
3833	struct sched_attr attr;
3834	struct task_struct *p;
3835	int retval;
3836
3837	if (!uattr || pid < 0 || flags)
3838		return -EINVAL;
3839
3840	retval = sched_copy_attr(uattr, &attr);
3841	if (retval)
3842		return retval;
3843
3844	if ((int)attr.sched_policy < 0)
3845		return -EINVAL;
3846
3847	rcu_read_lock();
3848	retval = -ESRCH;
3849	p = find_process_by_pid(pid);
3850	if (p != NULL)
3851		retval = sched_setattr(p, &attr);
3852	rcu_read_unlock();
3853
3854	return retval;
3855}
3856
3857/**
3858 * sys_sched_getscheduler - get the policy (scheduling class) of a thread
3859 * @pid: the pid in question.
3860 *
3861 * Return: On success, the policy of the thread. Otherwise, a negative error
3862 * code.
3863 */
3864SYSCALL_DEFINE1(sched_getscheduler, pid_t, pid)
3865{
3866	struct task_struct *p;
3867	int retval;
3868
3869	if (pid < 0)
3870		return -EINVAL;
3871
3872	retval = -ESRCH;
3873	rcu_read_lock();
3874	p = find_process_by_pid(pid);
3875	if (p) {
3876		retval = security_task_getscheduler(p);
3877		if (!retval)
3878			retval = p->policy
3879				| (p->sched_reset_on_fork ? SCHED_RESET_ON_FORK : 0);
3880	}
3881	rcu_read_unlock();
3882	return retval;
3883}
3884
3885/**
3886 * sys_sched_getparam - get the RT priority of a thread
3887 * @pid: the pid in question.
3888 * @param: structure containing the RT priority.
3889 *
3890 * Return: On success, 0 and the RT priority is in @param. Otherwise, an error
3891 * code.
3892 */
3893SYSCALL_DEFINE2(sched_getparam, pid_t, pid, struct sched_param __user *, param)
3894{
3895	struct sched_param lp = { .sched_priority = 0 };
3896	struct task_struct *p;
3897	int retval;
3898
3899	if (!param || pid < 0)
3900		return -EINVAL;
3901
3902	rcu_read_lock();
3903	p = find_process_by_pid(pid);
3904	retval = -ESRCH;
3905	if (!p)
3906		goto out_unlock;
3907
3908	retval = security_task_getscheduler(p);
3909	if (retval)
3910		goto out_unlock;
3911
3912	if (task_has_rt_policy(p))
3913		lp.sched_priority = p->rt_priority;
3914	rcu_read_unlock();
3915
3916	/*
3917	 * This one might sleep, we cannot do it with a spinlock held ...
3918	 */
3919	retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
3920
3921	return retval;
3922
3923out_unlock:
3924	rcu_read_unlock();
3925	return retval;
3926}
3927
3928static int sched_read_attr(struct sched_attr __user *uattr,
3929			   struct sched_attr *attr,
3930			   unsigned int usize)
3931{
3932	int ret;
3933
3934	if (!access_ok(VERIFY_WRITE, uattr, usize))
3935		return -EFAULT;
3936
3937	/*
3938	 * If we're handed a smaller struct than we know of,
3939	 * ensure all the unknown bits are 0 - i.e. old
3940	 * user-space does not get uncomplete information.
3941	 */
3942	if (usize < sizeof(*attr)) {
3943		unsigned char *addr;
3944		unsigned char *end;
3945
3946		addr = (void *)attr + usize;
3947		end  = (void *)attr + sizeof(*attr);
3948
3949		for (; addr < end; addr++) {
3950			if (*addr)
3951				return -EFBIG;
3952		}
3953
3954		attr->size = usize;
3955	}
3956
3957	ret = copy_to_user(uattr, attr, attr->size);
3958	if (ret)
3959		return -EFAULT;
3960
3961	return 0;
3962}
3963
3964/**
3965 * sys_sched_getattr - similar to sched_getparam, but with sched_attr
3966 * @pid: the pid in question.
3967 * @uattr: structure containing the extended parameters.
3968 * @size: sizeof(attr) for fwd/bwd comp.
3969 * @flags: for future extension.
3970 */
3971SYSCALL_DEFINE4(sched_getattr, pid_t, pid, struct sched_attr __user *, uattr,
3972		unsigned int, size, unsigned int, flags)
3973{
3974	struct sched_attr attr = {
3975		.size = sizeof(struct sched_attr),
3976	};
3977	struct task_struct *p;
3978	int retval;
3979
3980	if (!uattr || pid < 0 || size > PAGE_SIZE ||
3981	    size < SCHED_ATTR_SIZE_VER0 || flags)
3982		return -EINVAL;
3983
3984	rcu_read_lock();
3985	p = find_process_by_pid(pid);
3986	retval = -ESRCH;
3987	if (!p)
3988		goto out_unlock;
3989
3990	retval = security_task_getscheduler(p);
3991	if (retval)
3992		goto out_unlock;
3993
3994	attr.sched_policy = p->policy;
3995	if (p->sched_reset_on_fork)
3996		attr.sched_flags |= SCHED_FLAG_RESET_ON_FORK;
3997	if (task_has_dl_policy(p))
3998		__getparam_dl(p, &attr);
3999	else if (task_has_rt_policy(p))
4000		attr.sched_priority = p->rt_priority;
4001	else
4002		attr.sched_nice = task_nice(p);
4003
4004	rcu_read_unlock();
4005
4006	retval = sched_read_attr(uattr, &attr, size);
4007	return retval;
4008
4009out_unlock:
4010	rcu_read_unlock();
4011	return retval;
4012}
4013
4014long sched_setaffinity(pid_t pid, const struct cpumask *in_mask)
4015{
4016	cpumask_var_t cpus_allowed, new_mask;
4017	struct task_struct *p;
4018	int retval;
4019
4020	rcu_read_lock();
4021
4022	p = find_process_by_pid(pid);
4023	if (!p) {
4024		rcu_read_unlock();
4025		return -ESRCH;
4026	}
4027
4028	/* Prevent p going away */
4029	get_task_struct(p);
4030	rcu_read_unlock();
4031
4032	if (p->flags & PF_NO_SETAFFINITY) {
4033		retval = -EINVAL;
4034		goto out_put_task;
4035	}
4036	if (!alloc_cpumask_var(&cpus_allowed, GFP_KERNEL)) {
4037		retval = -ENOMEM;
4038		goto out_put_task;
4039	}
4040	if (!alloc_cpumask_var(&new_mask, GFP_KERNEL)) {
4041		retval = -ENOMEM;
4042		goto out_free_cpus_allowed;
4043	}
4044	retval = -EPERM;
4045	if (!check_same_owner(p)) {
4046		rcu_read_lock();
4047		if (!ns_capable(__task_cred(p)->user_ns, CAP_SYS_NICE)) {
4048			rcu_read_unlock();
4049			goto out_free_new_mask;
4050		}
4051		rcu_read_unlock();
4052	}
4053
4054	retval = security_task_setscheduler(p);
4055	if (retval)
4056		goto out_free_new_mask;
4057
4058
4059	cpuset_cpus_allowed(p, cpus_allowed);
4060	cpumask_and(new_mask, in_mask, cpus_allowed);
4061
4062	/*
4063	 * Since bandwidth control happens on root_domain basis,
4064	 * if admission test is enabled, we only admit -deadline
4065	 * tasks allowed to run on all the CPUs in the task's
4066	 * root_domain.
4067	 */
4068#ifdef CONFIG_SMP
4069	if (task_has_dl_policy(p) && dl_bandwidth_enabled()) {
4070		rcu_read_lock();
4071		if (!cpumask_subset(task_rq(p)->rd->span, new_mask)) {
4072			retval = -EBUSY;
4073			rcu_read_unlock();
4074			goto out_free_new_mask;
4075		}
4076		rcu_read_unlock();
4077	}
4078#endif
4079again:
4080	retval = set_cpus_allowed_ptr(p, new_mask);
4081
4082	if (!retval) {
4083		cpuset_cpus_allowed(p, cpus_allowed);
4084		if (!cpumask_subset(new_mask, cpus_allowed)) {
4085			/*
4086			 * We must have raced with a concurrent cpuset
4087			 * update. Just reset the cpus_allowed to the
4088			 * cpuset's cpus_allowed
4089			 */
4090			cpumask_copy(new_mask, cpus_allowed);
4091			goto again;
4092		}
4093	}
4094out_free_new_mask:
4095	free_cpumask_var(new_mask);
4096out_free_cpus_allowed:
4097	free_cpumask_var(cpus_allowed);
4098out_put_task:
4099	put_task_struct(p);
4100	return retval;
4101}
4102
4103static int get_user_cpu_mask(unsigned long __user *user_mask_ptr, unsigned len,
4104			     struct cpumask *new_mask)
4105{
4106	if (len < cpumask_size())
4107		cpumask_clear(new_mask);
4108	else if (len > cpumask_size())
4109		len = cpumask_size();
4110
4111	return copy_from_user(new_mask, user_mask_ptr, len) ? -EFAULT : 0;
4112}
4113
4114/**
4115 * sys_sched_setaffinity - set the cpu affinity of a process
4116 * @pid: pid of the process
4117 * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4118 * @user_mask_ptr: user-space pointer to the new cpu mask
4119 *
4120 * Return: 0 on success. An error code otherwise.
4121 */
4122SYSCALL_DEFINE3(sched_setaffinity, pid_t, pid, unsigned int, len,
4123		unsigned long __user *, user_mask_ptr)
4124{
4125	cpumask_var_t new_mask;
4126	int retval;
4127
4128	if (!alloc_cpumask_var(&new_mask, GFP_KERNEL))
4129		return -ENOMEM;
4130
4131	retval = get_user_cpu_mask(user_mask_ptr, len, new_mask);
4132	if (retval == 0)
4133		retval = sched_setaffinity(pid, new_mask);
4134	free_cpumask_var(new_mask);
4135	return retval;
4136}
4137
4138long sched_getaffinity(pid_t pid, struct cpumask *mask)
4139{
4140	struct task_struct *p;
4141	unsigned long flags;
4142	int retval;
4143
4144	rcu_read_lock();
4145
4146	retval = -ESRCH;
4147	p = find_process_by_pid(pid);
4148	if (!p)
4149		goto out_unlock;
4150
4151	retval = security_task_getscheduler(p);
4152	if (retval)
4153		goto out_unlock;
4154
4155	raw_spin_lock_irqsave(&p->pi_lock, flags);
4156	cpumask_and(mask, &p->cpus_allowed, cpu_active_mask);
4157	raw_spin_unlock_irqrestore(&p->pi_lock, flags);
4158
4159out_unlock:
4160	rcu_read_unlock();
4161
4162	return retval;
4163}
4164
4165/**
4166 * sys_sched_getaffinity - get the cpu affinity of a process
4167 * @pid: pid of the process
4168 * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4169 * @user_mask_ptr: user-space pointer to hold the current cpu mask
4170 *
4171 * Return: 0 on success. An error code otherwise.
4172 */
4173SYSCALL_DEFINE3(sched_getaffinity, pid_t, pid, unsigned int, len,
4174		unsigned long __user *, user_mask_ptr)
4175{
4176	int ret;
4177	cpumask_var_t mask;
4178
4179	if ((len * BITS_PER_BYTE) < nr_cpu_ids)
4180		return -EINVAL;
4181	if (len & (sizeof(unsigned long)-1))
4182		return -EINVAL;
4183
4184	if (!alloc_cpumask_var(&mask, GFP_KERNEL))
4185		return -ENOMEM;
4186
4187	ret = sched_getaffinity(pid, mask);
4188	if (ret == 0) {
4189		size_t retlen = min_t(size_t, len, cpumask_size());
4190
4191		if (copy_to_user(user_mask_ptr, mask, retlen))
4192			ret = -EFAULT;
4193		else
4194			ret = retlen;
4195	}
4196	free_cpumask_var(mask);
4197
4198	return ret;
4199}
4200
4201/**
4202 * sys_sched_yield - yield the current processor to other threads.
4203 *
4204 * This function yields the current CPU to other tasks. If there are no
4205 * other threads running on this CPU then this function will return.
4206 *
4207 * Return: 0.
4208 */
4209SYSCALL_DEFINE0(sched_yield)
4210{
4211	struct rq *rq = this_rq_lock();
4212
4213	schedstat_inc(rq, yld_count);
4214	current->sched_class->yield_task(rq);
4215
4216	/*
4217	 * Since we are going to call schedule() anyway, there's
4218	 * no need to preempt or enable interrupts:
4219	 */
4220	__release(rq->lock);
4221	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
4222	do_raw_spin_unlock(&rq->lock);
4223	sched_preempt_enable_no_resched();
4224
4225	schedule();
4226
4227	return 0;
4228}
4229
4230static void __cond_resched(void)
4231{
4232	__preempt_count_add(PREEMPT_ACTIVE);
4233	__schedule();
4234	__preempt_count_sub(PREEMPT_ACTIVE);
4235}
4236
4237int __sched _cond_resched(void)
4238{
4239	if (should_resched()) {
4240		__cond_resched();
4241		return 1;
4242	}
4243	return 0;
4244}
4245EXPORT_SYMBOL(_cond_resched);
4246
4247/*
4248 * __cond_resched_lock() - if a reschedule is pending, drop the given lock,
4249 * call schedule, and on return reacquire the lock.
4250 *
4251 * This works OK both with and without CONFIG_PREEMPT. We do strange low-level
4252 * operations here to prevent schedule() from being called twice (once via
4253 * spin_unlock(), once by hand).
4254 */
4255int __cond_resched_lock(spinlock_t *lock)
4256{
4257	int resched = should_resched();
4258	int ret = 0;
4259
4260	lockdep_assert_held(lock);
4261
4262	if (spin_needbreak(lock) || resched) {
4263		spin_unlock(lock);
4264		if (resched)
4265			__cond_resched();
4266		else
4267			cpu_relax();
4268		ret = 1;
4269		spin_lock(lock);
4270	}
4271	return ret;
4272}
4273EXPORT_SYMBOL(__cond_resched_lock);
4274
4275int __sched __cond_resched_softirq(void)
4276{
4277	BUG_ON(!in_softirq());
4278
4279	if (should_resched()) {
4280		local_bh_enable();
4281		__cond_resched();
4282		local_bh_disable();
4283		return 1;
4284	}
4285	return 0;
4286}
4287EXPORT_SYMBOL(__cond_resched_softirq);
4288
4289/**
4290 * yield - yield the current processor to other threads.
4291 *
4292 * Do not ever use this function, there's a 99% chance you're doing it wrong.
4293 *
4294 * The scheduler is at all times free to pick the calling task as the most
4295 * eligible task to run, if removing the yield() call from your code breaks
4296 * it, its already broken.
4297 *
4298 * Typical broken usage is:
4299 *
4300 * while (!event)
4301 * 	yield();
4302 *
4303 * where one assumes that yield() will let 'the other' process run that will
4304 * make event true. If the current task is a SCHED_FIFO task that will never
4305 * happen. Never use yield() as a progress guarantee!!
4306 *
4307 * If you want to use yield() to wait for something, use wait_event().
4308 * If you want to use yield() to be 'nice' for others, use cond_resched().
4309 * If you still want to use yield(), do not!
4310 */
4311void __sched yield(void)
4312{
4313	set_current_state(TASK_RUNNING);
4314	sys_sched_yield();
4315}
4316EXPORT_SYMBOL(yield);
4317
4318/**
4319 * yield_to - yield the current processor to another thread in
4320 * your thread group, or accelerate that thread toward the
4321 * processor it's on.
4322 * @p: target task
4323 * @preempt: whether task preemption is allowed or not
4324 *
4325 * It's the caller's job to ensure that the target task struct
4326 * can't go away on us before we can do any checks.
4327 *
4328 * Return:
4329 *	true (>0) if we indeed boosted the target task.
4330 *	false (0) if we failed to boost the target.
4331 *	-ESRCH if there's no task to yield to.
4332 */
4333int __sched yield_to(struct task_struct *p, bool preempt)
4334{
4335	struct task_struct *curr = current;
4336	struct rq *rq, *p_rq;
4337	unsigned long flags;
4338	int yielded = 0;
4339
4340	local_irq_save(flags);
4341	rq = this_rq();
4342
4343again:
4344	p_rq = task_rq(p);
4345	/*
4346	 * If we're the only runnable task on the rq and target rq also
4347	 * has only one task, there's absolutely no point in yielding.
4348	 */
4349	if (rq->nr_running == 1 && p_rq->nr_running == 1) {
4350		yielded = -ESRCH;
4351		goto out_irq;
4352	}
4353
4354	double_rq_lock(rq, p_rq);
4355	if (task_rq(p) != p_rq) {
4356		double_rq_unlock(rq, p_rq);
4357		goto again;
4358	}
4359
4360	if (!curr->sched_class->yield_to_task)
4361		goto out_unlock;
4362
4363	if (curr->sched_class != p->sched_class)
4364		goto out_unlock;
4365
4366	if (task_running(p_rq, p) || p->state)
4367		goto out_unlock;
4368
4369	yielded = curr->sched_class->yield_to_task(rq, p, preempt);
4370	if (yielded) {
4371		schedstat_inc(rq, yld_count);
4372		/*
4373		 * Make p's CPU reschedule; pick_next_entity takes care of
4374		 * fairness.
4375		 */
4376		if (preempt && rq != p_rq)
4377			resched_curr(p_rq);
4378	}
4379
4380out_unlock:
4381	double_rq_unlock(rq, p_rq);
4382out_irq:
4383	local_irq_restore(flags);
4384
4385	if (yielded > 0)
4386		schedule();
4387
4388	return yielded;
4389}
4390EXPORT_SYMBOL_GPL(yield_to);
4391
4392/*
4393 * This task is about to go to sleep on IO. Increment rq->nr_iowait so
4394 * that process accounting knows that this is a task in IO wait state.
4395 */
4396void __sched io_schedule(void)
4397{
4398	struct rq *rq = raw_rq();
4399
4400	delayacct_blkio_start();
4401	atomic_inc(&rq->nr_iowait);
4402	blk_flush_plug(current);
4403	current->in_iowait = 1;
4404	schedule();
4405	current->in_iowait = 0;
4406	atomic_dec(&rq->nr_iowait);
4407	delayacct_blkio_end();
4408}
4409EXPORT_SYMBOL(io_schedule);
4410
4411long __sched io_schedule_timeout(long timeout)
4412{
4413	struct rq *rq = raw_rq();
4414	long ret;
4415
4416	delayacct_blkio_start();
4417	atomic_inc(&rq->nr_iowait);
4418	blk_flush_plug(current);
4419	current->in_iowait = 1;
4420	ret = schedule_timeout(timeout);
4421	current->in_iowait = 0;
4422	atomic_dec(&rq->nr_iowait);
4423	delayacct_blkio_end();
4424	return ret;
4425}
4426
4427/**
4428 * sys_sched_get_priority_max - return maximum RT priority.
4429 * @policy: scheduling class.
4430 *
4431 * Return: On success, this syscall returns the maximum
4432 * rt_priority that can be used by a given scheduling class.
4433 * On failure, a negative error code is returned.
4434 */
4435SYSCALL_DEFINE1(sched_get_priority_max, int, policy)
4436{
4437	int ret = -EINVAL;
4438
4439	switch (policy) {
4440	case SCHED_FIFO:
4441	case SCHED_RR:
4442		ret = MAX_USER_RT_PRIO-1;
4443		break;
4444	case SCHED_DEADLINE:
4445	case SCHED_NORMAL:
4446	case SCHED_BATCH:
4447	case SCHED_IDLE:
4448		ret = 0;
4449		break;
4450	}
4451	return ret;
4452}
4453
4454/**
4455 * sys_sched_get_priority_min - return minimum RT priority.
4456 * @policy: scheduling class.
4457 *
4458 * Return: On success, this syscall returns the minimum
4459 * rt_priority that can be used by a given scheduling class.
4460 * On failure, a negative error code is returned.
4461 */
4462SYSCALL_DEFINE1(sched_get_priority_min, int, policy)
4463{
4464	int ret = -EINVAL;
4465
4466	switch (policy) {
4467	case SCHED_FIFO:
4468	case SCHED_RR:
4469		ret = 1;
4470		break;
4471	case SCHED_DEADLINE:
4472	case SCHED_NORMAL:
4473	case SCHED_BATCH:
4474	case SCHED_IDLE:
4475		ret = 0;
4476	}
4477	return ret;
4478}
4479
4480/**
4481 * sys_sched_rr_get_interval - return the default timeslice of a process.
4482 * @pid: pid of the process.
4483 * @interval: userspace pointer to the timeslice value.
4484 *
4485 * this syscall writes the default timeslice value of a given process
4486 * into the user-space timespec buffer. A value of '0' means infinity.
4487 *
4488 * Return: On success, 0 and the timeslice is in @interval. Otherwise,
4489 * an error code.
4490 */
4491SYSCALL_DEFINE2(sched_rr_get_interval, pid_t, pid,
4492		struct timespec __user *, interval)
4493{
4494	struct task_struct *p;
4495	unsigned int time_slice;
4496	unsigned long flags;
4497	struct rq *rq;
4498	int retval;
4499	struct timespec t;
4500
4501	if (pid < 0)
4502		return -EINVAL;
4503
4504	retval = -ESRCH;
4505	rcu_read_lock();
4506	p = find_process_by_pid(pid);
4507	if (!p)
4508		goto out_unlock;
4509
4510	retval = security_task_getscheduler(p);
4511	if (retval)
4512		goto out_unlock;
4513
4514	rq = task_rq_lock(p, &flags);
4515	time_slice = 0;
4516	if (p->sched_class->get_rr_interval)
4517		time_slice = p->sched_class->get_rr_interval(rq, p);
4518	task_rq_unlock(rq, p, &flags);
4519
4520	rcu_read_unlock();
4521	jiffies_to_timespec(time_slice, &t);
4522	retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0;
4523	return retval;
4524
4525out_unlock:
4526	rcu_read_unlock();
4527	return retval;
4528}
4529
4530static const char stat_nam[] = TASK_STATE_TO_CHAR_STR;
4531
4532void sched_show_task(struct task_struct *p)
4533{
4534	unsigned long free = 0;
4535	int ppid;
4536	unsigned state;
4537
4538	state = p->state ? __ffs(p->state) + 1 : 0;
4539	printk(KERN_INFO "%-15.15s %c", p->comm,
4540		state < sizeof(stat_nam) - 1 ? stat_nam[state] : '?');
4541#if BITS_PER_LONG == 32
4542	if (state == TASK_RUNNING)
4543		printk(KERN_CONT " running  ");
4544	else
4545		printk(KERN_CONT " %08lx ", thread_saved_pc(p));
4546#else
4547	if (state == TASK_RUNNING)
4548		printk(KERN_CONT "  running task    ");
4549	else
4550		printk(KERN_CONT " %016lx ", thread_saved_pc(p));
4551#endif
4552#ifdef CONFIG_DEBUG_STACK_USAGE
4553	free = stack_not_used(p);
4554#endif
4555	rcu_read_lock();
4556	ppid = task_pid_nr(rcu_dereference(p->real_parent));
4557	rcu_read_unlock();
4558	printk(KERN_CONT "%5lu %5d %6d 0x%08lx\n", free,
4559		task_pid_nr(p), ppid,
4560		(unsigned long)task_thread_info(p)->flags);
4561
4562	print_worker_info(KERN_INFO, p);
4563	show_stack(p, NULL);
4564}
4565
4566void show_state_filter(unsigned long state_filter)
4567{
4568	struct task_struct *g, *p;
4569
4570#if BITS_PER_LONG == 32
4571	printk(KERN_INFO
4572		"  task                PC stack   pid father\n");
4573#else
4574	printk(KERN_INFO
4575		"  task                        PC stack   pid father\n");
4576#endif
4577	rcu_read_lock();
4578	for_each_process_thread(g, p) {
4579		/*
4580		 * reset the NMI-timeout, listing all files on a slow
4581		 * console might take a lot of time:
4582		 */
4583		touch_nmi_watchdog();
4584		if (!state_filter || (p->state & state_filter))
4585			sched_show_task(p);
4586	}
4587
4588	touch_all_softlockup_watchdogs();
4589
4590#ifdef CONFIG_SCHED_DEBUG
4591	sysrq_sched_debug_show();
4592#endif
4593	rcu_read_unlock();
4594	/*
4595	 * Only show locks if all tasks are dumped:
4596	 */
4597	if (!state_filter)
4598		debug_show_all_locks();
4599}
4600
4601void init_idle_bootup_task(struct task_struct *idle)
4602{
4603	idle->sched_class = &idle_sched_class;
4604}
4605
4606/**
4607 * init_idle - set up an idle thread for a given CPU
4608 * @idle: task in question
4609 * @cpu: cpu the idle task belongs to
4610 *
4611 * NOTE: this function does not set the idle thread's NEED_RESCHED
4612 * flag, to make booting more robust.
4613 */
4614void init_idle(struct task_struct *idle, int cpu)
4615{
4616	struct rq *rq = cpu_rq(cpu);
4617	unsigned long flags;
4618
4619	raw_spin_lock_irqsave(&rq->lock, flags);
4620
4621	__sched_fork(0, idle);
4622	idle->state = TASK_RUNNING;
4623	idle->se.exec_start = sched_clock();
4624
4625	do_set_cpus_allowed(idle, cpumask_of(cpu));
4626	/*
4627	 * We're having a chicken and egg problem, even though we are
4628	 * holding rq->lock, the cpu isn't yet set to this cpu so the
4629	 * lockdep check in task_group() will fail.
4630	 *
4631	 * Similar case to sched_fork(). / Alternatively we could
4632	 * use task_rq_lock() here and obtain the other rq->lock.
4633	 *
4634	 * Silence PROVE_RCU
4635	 */
4636	rcu_read_lock();
4637	__set_task_cpu(idle, cpu);
4638	rcu_read_unlock();
4639
4640	rq->curr = rq->idle = idle;
4641	idle->on_rq = TASK_ON_RQ_QUEUED;
4642#if defined(CONFIG_SMP)
4643	idle->on_cpu = 1;
4644#endif
4645	raw_spin_unlock_irqrestore(&rq->lock, flags);
4646
4647	/* Set the preempt count _outside_ the spinlocks! */
4648	init_idle_preempt_count(idle, cpu);
4649
4650	/*
4651	 * The idle tasks have their own, simple scheduling class:
4652	 */
4653	idle->sched_class = &idle_sched_class;
4654	ftrace_graph_init_idle_task(idle, cpu);
4655	vtime_init_idle(idle, cpu);
4656#if defined(CONFIG_SMP)
4657	sprintf(idle->comm, "%s/%d", INIT_TASK_COMM, cpu);
4658#endif
4659}
4660
4661#ifdef CONFIG_SMP
4662/*
4663 * move_queued_task - move a queued task to new rq.
4664 *
4665 * Returns (locked) new rq. Old rq's lock is released.
4666 */
4667static struct rq *move_queued_task(struct task_struct *p, int new_cpu)
4668{
4669	struct rq *rq = task_rq(p);
4670
4671	lockdep_assert_held(&rq->lock);
4672
4673	dequeue_task(rq, p, 0);
4674	p->on_rq = TASK_ON_RQ_MIGRATING;
4675	set_task_cpu(p, new_cpu);
4676	raw_spin_unlock(&rq->lock);
4677
4678	rq = cpu_rq(new_cpu);
4679
4680	raw_spin_lock(&rq->lock);
4681	BUG_ON(task_cpu(p) != new_cpu);
4682	p->on_rq = TASK_ON_RQ_QUEUED;
4683	enqueue_task(rq, p, 0);
4684	check_preempt_curr(rq, p, 0);
4685
4686	return rq;
4687}
4688
4689void do_set_cpus_allowed(struct task_struct *p, const struct cpumask *new_mask)
4690{
4691	if (p->sched_class && p->sched_class->set_cpus_allowed)
4692		p->sched_class->set_cpus_allowed(p, new_mask);
4693
4694	cpumask_copy(&p->cpus_allowed, new_mask);
4695	p->nr_cpus_allowed = cpumask_weight(new_mask);
4696}
4697
4698/*
4699 * This is how migration works:
4700 *
4701 * 1) we invoke migration_cpu_stop() on the target CPU using
4702 *    stop_one_cpu().
4703 * 2) stopper starts to run (implicitly forcing the migrated thread
4704 *    off the CPU)
4705 * 3) it checks whether the migrated task is still in the wrong runqueue.
4706 * 4) if it's in the wrong runqueue then the migration thread removes
4707 *    it and puts it into the right queue.
4708 * 5) stopper completes and stop_one_cpu() returns and the migration
4709 *    is done.
4710 */
4711
4712/*
4713 * Change a given task's CPU affinity. Migrate the thread to a
4714 * proper CPU and schedule it away if the CPU it's executing on
4715 * is removed from the allowed bitmask.
4716 *
4717 * NOTE: the caller must have a valid reference to the task, the
4718 * task must not exit() & deallocate itself prematurely. The
4719 * call is not atomic; no spinlocks may be held.
4720 */
4721int set_cpus_allowed_ptr(struct task_struct *p, const struct cpumask *new_mask)
4722{
4723	unsigned long flags;
4724	struct rq *rq;
4725	unsigned int dest_cpu;
4726	int ret = 0;
4727
4728	rq = task_rq_lock(p, &flags);
4729
4730	if (cpumask_equal(&p->cpus_allowed, new_mask))
4731		goto out;
4732
4733	if (!cpumask_intersects(new_mask, cpu_active_mask)) {
4734		ret = -EINVAL;
4735		goto out;
4736	}
4737
4738	do_set_cpus_allowed(p, new_mask);
4739
4740	/* Can the task run on the task's current CPU? If so, we're done */
4741	if (cpumask_test_cpu(task_cpu(p), new_mask))
4742		goto out;
4743
4744	dest_cpu = cpumask_any_and(cpu_active_mask, new_mask);
4745	if (task_running(rq, p) || p->state == TASK_WAKING) {
4746		struct migration_arg arg = { p, dest_cpu };
4747		/* Need help from migration thread: drop lock and wait. */
4748		task_rq_unlock(rq, p, &flags);
4749		stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
4750		tlb_migrate_finish(p->mm);
4751		return 0;
4752	} else if (task_on_rq_queued(p))
4753		rq = move_queued_task(p, dest_cpu);
4754out:
4755	task_rq_unlock(rq, p, &flags);
4756
4757	return ret;
4758}
4759EXPORT_SYMBOL_GPL(set_cpus_allowed_ptr);
4760
4761/*
4762 * Move (not current) task off this cpu, onto dest cpu. We're doing
4763 * this because either it can't run here any more (set_cpus_allowed()
4764 * away from this CPU, or CPU going down), or because we're
4765 * attempting to rebalance this task on exec (sched_exec).
4766 *
4767 * So we race with normal scheduler movements, but that's OK, as long
4768 * as the task is no longer on this CPU.
4769 *
4770 * Returns non-zero if task was successfully migrated.
4771 */
4772static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
4773{
4774	struct rq *rq;
4775	int ret = 0;
4776
4777	if (unlikely(!cpu_active(dest_cpu)))
4778		return ret;
4779
4780	rq = cpu_rq(src_cpu);
4781
4782	raw_spin_lock(&p->pi_lock);
4783	raw_spin_lock(&rq->lock);
4784	/* Already moved. */
4785	if (task_cpu(p) != src_cpu)
4786		goto done;
4787
4788	/* Affinity changed (again). */
4789	if (!cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
4790		goto fail;
4791
4792	/*
4793	 * If we're not on a rq, the next wake-up will ensure we're
4794	 * placed properly.
4795	 */
4796	if (task_on_rq_queued(p))
4797		rq = move_queued_task(p, dest_cpu);
4798done:
4799	ret = 1;
4800fail:
4801	raw_spin_unlock(&rq->lock);
4802	raw_spin_unlock(&p->pi_lock);
4803	return ret;
4804}
4805
4806#ifdef CONFIG_NUMA_BALANCING
4807/* Migrate current task p to target_cpu */
4808int migrate_task_to(struct task_struct *p, int target_cpu)
4809{
4810	struct migration_arg arg = { p, target_cpu };
4811	int curr_cpu = task_cpu(p);
4812
4813	if (curr_cpu == target_cpu)
4814		return 0;
4815
4816	if (!cpumask_test_cpu(target_cpu, tsk_cpus_allowed(p)))
4817		return -EINVAL;
4818
4819	/* TODO: This is not properly updating schedstats */
4820
4821	trace_sched_move_numa(p, curr_cpu, target_cpu);
4822	return stop_one_cpu(curr_cpu, migration_cpu_stop, &arg);
4823}
4824
4825/*
4826 * Requeue a task on a given node and accurately track the number of NUMA
4827 * tasks on the runqueues
4828 */
4829void sched_setnuma(struct task_struct *p, int nid)
4830{
4831	struct rq *rq;
4832	unsigned long flags;
4833	bool queued, running;
4834
4835	rq = task_rq_lock(p, &flags);
4836	queued = task_on_rq_queued(p);
4837	running = task_current(rq, p);
4838
4839	if (queued)
4840		dequeue_task(rq, p, 0);
4841	if (running)
4842		put_prev_task(rq, p);
4843
4844	p->numa_preferred_nid = nid;
4845
4846	if (running)
4847		p->sched_class->set_curr_task(rq);
4848	if (queued)
4849		enqueue_task(rq, p, 0);
4850	task_rq_unlock(rq, p, &flags);
4851}
4852#endif
4853
4854/*
4855 * migration_cpu_stop - this will be executed by a highprio stopper thread
4856 * and performs thread migration by bumping thread off CPU then
4857 * 'pushing' onto another runqueue.
4858 */
4859static int migration_cpu_stop(void *data)
4860{
4861	struct migration_arg *arg = data;
4862
4863	/*
4864	 * The original target cpu might have gone down and we might
4865	 * be on another cpu but it doesn't matter.
4866	 */
4867	local_irq_disable();
4868	/*
4869	 * We need to explicitly wake pending tasks before running
4870	 * __migrate_task() such that we will not miss enforcing cpus_allowed
4871	 * during wakeups, see set_cpus_allowed_ptr()'s TASK_WAKING test.
4872	 */
4873	sched_ttwu_pending();
4874	__migrate_task(arg->task, raw_smp_processor_id(), arg->dest_cpu);
4875	local_irq_enable();
4876	return 0;
4877}
4878
4879#ifdef CONFIG_HOTPLUG_CPU
4880
4881/*
4882 * Ensures that the idle task is using init_mm right before its cpu goes
4883 * offline.
4884 */
4885void idle_task_exit(void)
4886{
4887	struct mm_struct *mm = current->active_mm;
4888
4889	BUG_ON(cpu_online(smp_processor_id()));
4890
4891	if (mm != &init_mm) {
4892		switch_mm(mm, &init_mm, current);
4893		finish_arch_post_lock_switch();
4894	}
4895	mmdrop(mm);
4896}
4897
4898/*
4899 * Since this CPU is going 'away' for a while, fold any nr_active delta
4900 * we might have. Assumes we're called after migrate_tasks() so that the
4901 * nr_active count is stable.
4902 *
4903 * Also see the comment "Global load-average calculations".
4904 */
4905static void calc_load_migrate(struct rq *rq)
4906{
4907	long delta = calc_load_fold_active(rq);
4908	if (delta)
4909		atomic_long_add(delta, &calc_load_tasks);
4910}
4911
4912static void put_prev_task_fake(struct rq *rq, struct task_struct *prev)
4913{
4914}
4915
4916static const struct sched_class fake_sched_class = {
4917	.put_prev_task = put_prev_task_fake,
4918};
4919
4920static struct task_struct fake_task = {
4921	/*
4922	 * Avoid pull_{rt,dl}_task()
4923	 */
4924	.prio = MAX_PRIO + 1,
4925	.sched_class = &fake_sched_class,
4926};
4927
4928/*
4929 * Migrate all tasks from the rq, sleeping tasks will be migrated by
4930 * try_to_wake_up()->select_task_rq().
4931 *
4932 * Called with rq->lock held even though we'er in stop_machine() and
4933 * there's no concurrency possible, we hold the required locks anyway
4934 * because of lock validation efforts.
4935 */
4936static void migrate_tasks(unsigned int dead_cpu)
4937{
4938	struct rq *rq = cpu_rq(dead_cpu);
4939	struct task_struct *next, *stop = rq->stop;
4940	int dest_cpu;
4941
4942	/*
4943	 * Fudge the rq selection such that the below task selection loop
4944	 * doesn't get stuck on the currently eligible stop task.
4945	 *
4946	 * We're currently inside stop_machine() and the rq is either stuck
4947	 * in the stop_machine_cpu_stop() loop, or we're executing this code,
4948	 * either way we should never end up calling schedule() until we're
4949	 * done here.
4950	 */
4951	rq->stop = NULL;
4952
4953	/*
4954	 * put_prev_task() and pick_next_task() sched
4955	 * class method both need to have an up-to-date
4956	 * value of rq->clock[_task]
4957	 */
4958	update_rq_clock(rq);
4959
4960	for ( ; ; ) {
4961		/*
4962		 * There's this thread running, bail when that's the only
4963		 * remaining thread.
4964		 */
4965		if (rq->nr_running == 1)
4966			break;
4967
4968		next = pick_next_task(rq, &fake_task);
4969		BUG_ON(!next);
4970		next->sched_class->put_prev_task(rq, next);
4971
4972		/* Find suitable destination for @next, with force if needed. */
4973		dest_cpu = select_fallback_rq(dead_cpu, next);
4974		raw_spin_unlock(&rq->lock);
4975
4976		__migrate_task(next, dead_cpu, dest_cpu);
4977
4978		raw_spin_lock(&rq->lock);
4979	}
4980
4981	rq->stop = stop;
4982}
4983
4984#endif /* CONFIG_HOTPLUG_CPU */
4985
4986#if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL)
4987
4988static struct ctl_table sd_ctl_dir[] = {
4989	{
4990		.procname	= "sched_domain",
4991		.mode		= 0555,
4992	},
4993	{}
4994};
4995
4996static struct ctl_table sd_ctl_root[] = {
4997	{
4998		.procname	= "kernel",
4999		.mode		= 0555,
5000		.child		= sd_ctl_dir,
5001	},
5002	{}
5003};
5004
5005static struct ctl_table *sd_alloc_ctl_entry(int n)
5006{
5007	struct ctl_table *entry =
5008		kcalloc(n, sizeof(struct ctl_table), GFP_KERNEL);
5009
5010	return entry;
5011}
5012
5013static void sd_free_ctl_entry(struct ctl_table **tablep)
5014{
5015	struct ctl_table *entry;
5016
5017	/*
5018	 * In the intermediate directories, both the child directory and
5019	 * procname are dynamically allocated and could fail but the mode
5020	 * will always be set. In the lowest directory the names are
5021	 * static strings and all have proc handlers.
5022	 */
5023	for (entry = *tablep; entry->mode; entry++) {
5024		if (entry->child)
5025			sd_free_ctl_entry(&entry->child);
5026		if (entry->proc_handler == NULL)
5027			kfree(entry->procname);
5028	}
5029
5030	kfree(*tablep);
5031	*tablep = NULL;
5032}
5033
5034static int min_load_idx = 0;
5035static int max_load_idx = CPU_LOAD_IDX_MAX-1;
5036
5037static void
5038set_table_entry(struct ctl_table *entry,
5039		const char *procname, void *data, int maxlen,
5040		umode_t mode, proc_handler *proc_handler,
5041		bool load_idx)
5042{
5043	entry->procname = procname;
5044	entry->data = data;
5045	entry->maxlen = maxlen;
5046	entry->mode = mode;
5047	entry->proc_handler = proc_handler;
5048
5049	if (load_idx) {
5050		entry->extra1 = &min_load_idx;
5051		entry->extra2 = &max_load_idx;
5052	}
5053}
5054
5055static struct ctl_table *
5056sd_alloc_ctl_domain_table(struct sched_domain *sd)
5057{
5058	struct ctl_table *table = sd_alloc_ctl_entry(14);
5059
5060	if (table == NULL)
5061		return NULL;
5062
5063	set_table_entry(&table[0], "min_interval", &sd->min_interval,
5064		sizeof(long), 0644, proc_doulongvec_minmax, false);
5065	set_table_entry(&table[1], "max_interval", &sd->max_interval,
5066		sizeof(long), 0644, proc_doulongvec_minmax, false);
5067	set_table_entry(&table[2], "busy_idx", &sd->busy_idx,
5068		sizeof(int), 0644, proc_dointvec_minmax, true);
5069	set_table_entry(&table[3], "idle_idx", &sd->idle_idx,
5070		sizeof(int), 0644, proc_dointvec_minmax, true);
5071	set_table_entry(&table[4], "newidle_idx", &sd->newidle_idx,
5072		sizeof(int), 0644, proc_dointvec_minmax, true);
5073	set_table_entry(&table[5], "wake_idx", &sd->wake_idx,
5074		sizeof(int), 0644, proc_dointvec_minmax, true);
5075	set_table_entry(&table[6], "forkexec_idx", &sd->forkexec_idx,
5076		sizeof(int), 0644, proc_dointvec_minmax, true);
5077	set_table_entry(&table[7], "busy_factor", &sd->busy_factor,
5078		sizeof(int), 0644, proc_dointvec_minmax, false);
5079	set_table_entry(&table[8], "imbalance_pct", &sd->imbalance_pct,
5080		sizeof(int), 0644, proc_dointvec_minmax, false);
5081	set_table_entry(&table[9], "cache_nice_tries",
5082		&sd->cache_nice_tries,
5083		sizeof(int), 0644, proc_dointvec_minmax, false);
5084	set_table_entry(&table[10], "flags", &sd->flags,
5085		sizeof(int), 0644, proc_dointvec_minmax, false);
5086	set_table_entry(&table[11], "max_newidle_lb_cost",
5087		&sd->max_newidle_lb_cost,
5088		sizeof(long), 0644, proc_doulongvec_minmax, false);
5089	set_table_entry(&table[12], "name", sd->name,
5090		CORENAME_MAX_SIZE, 0444, proc_dostring, false);
5091	/* &table[13] is terminator */
5092
5093	return table;
5094}
5095
5096static struct ctl_table *sd_alloc_ctl_cpu_table(int cpu)
5097{
5098	struct ctl_table *entry, *table;
5099	struct sched_domain *sd;
5100	int domain_num = 0, i;
5101	char buf[32];
5102
5103	for_each_domain(cpu, sd)
5104		domain_num++;
5105	entry = table = sd_alloc_ctl_entry(domain_num + 1);
5106	if (table == NULL)
5107		return NULL;
5108
5109	i = 0;
5110	for_each_domain(cpu, sd) {
5111		snprintf(buf, 32, "domain%d", i);
5112		entry->procname = kstrdup(buf, GFP_KERNEL);
5113		entry->mode = 0555;
5114		entry->child = sd_alloc_ctl_domain_table(sd);
5115		entry++;
5116		i++;
5117	}
5118	return table;
5119}
5120
5121static struct ctl_table_header *sd_sysctl_header;
5122static void register_sched_domain_sysctl(void)
5123{
5124	int i, cpu_num = num_possible_cpus();
5125	struct ctl_table *entry = sd_alloc_ctl_entry(cpu_num + 1);
5126	char buf[32];
5127
5128	WARN_ON(sd_ctl_dir[0].child);
5129	sd_ctl_dir[0].child = entry;
5130
5131	if (entry == NULL)
5132		return;
5133
5134	for_each_possible_cpu(i) {
5135		snprintf(buf, 32, "cpu%d", i);
5136		entry->procname = kstrdup(buf, GFP_KERNEL);
5137		entry->mode = 0555;
5138		entry->child = sd_alloc_ctl_cpu_table(i);
5139		entry++;
5140	}
5141
5142	WARN_ON(sd_sysctl_header);
5143	sd_sysctl_header = register_sysctl_table(sd_ctl_root);
5144}
5145
5146/* may be called multiple times per register */
5147static void unregister_sched_domain_sysctl(void)
5148{
5149	if (sd_sysctl_header)
5150		unregister_sysctl_table(sd_sysctl_header);
5151	sd_sysctl_header = NULL;
5152	if (sd_ctl_dir[0].child)
5153		sd_free_ctl_entry(&sd_ctl_dir[0].child);
5154}
5155#else
5156static void register_sched_domain_sysctl(void)
5157{
5158}
5159static void unregister_sched_domain_sysctl(void)
5160{
5161}
5162#endif
5163
5164static void set_rq_online(struct rq *rq)
5165{
5166	if (!rq->online) {
5167		const struct sched_class *class;
5168
5169		cpumask_set_cpu(rq->cpu, rq->rd->online);
5170		rq->online = 1;
5171
5172		for_each_class(class) {
5173			if (class->rq_online)
5174				class->rq_online(rq);
5175		}
5176	}
5177}
5178
5179static void set_rq_offline(struct rq *rq)
5180{
5181	if (rq->online) {
5182		const struct sched_class *class;
5183
5184		for_each_class(class) {
5185			if (class->rq_offline)
5186				class->rq_offline(rq);
5187		}
5188
5189		cpumask_clear_cpu(rq->cpu, rq->rd->online);
5190		rq->online = 0;
5191	}
5192}
5193
5194/*
5195 * migration_call - callback that gets triggered when a CPU is added.
5196 * Here we can start up the necessary migration thread for the new CPU.
5197 */
5198static int
5199migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
5200{
5201	int cpu = (long)hcpu;
5202	unsigned long flags;
5203	struct rq *rq = cpu_rq(cpu);
5204
5205	switch (action & ~CPU_TASKS_FROZEN) {
5206
5207	case CPU_UP_PREPARE:
5208		rq->calc_load_update = calc_load_update;
5209		break;
5210
5211	case CPU_ONLINE:
5212		/* Update our root-domain */
5213		raw_spin_lock_irqsave(&rq->lock, flags);
5214		if (rq->rd) {
5215			BUG_ON(!cpumask_test_cpu(cpu, rq->rd->span));
5216
5217			set_rq_online(rq);
5218		}
5219		raw_spin_unlock_irqrestore(&rq->lock, flags);
5220		break;
5221
5222#ifdef CONFIG_HOTPLUG_CPU
5223	case CPU_DYING:
5224		sched_ttwu_pending();
5225		/* Update our root-domain */
5226		raw_spin_lock_irqsave(&rq->lock, flags);
5227		if (rq->rd) {
5228			BUG_ON(!cpumask_test_cpu(cpu, rq->rd->span));
5229			set_rq_offline(rq);
5230		}
5231		migrate_tasks(cpu);
5232		BUG_ON(rq->nr_running != 1); /* the migration thread */
5233		raw_spin_unlock_irqrestore(&rq->lock, flags);
5234		break;
5235
5236	case CPU_DEAD:
5237		calc_load_migrate(rq);
5238		break;
5239#endif
5240	}
5241
5242	update_max_interval();
5243
5244	return NOTIFY_OK;
5245}
5246
5247/*
5248 * Register at high priority so that task migration (migrate_all_tasks)
5249 * happens before everything else.  This has to be lower priority than
5250 * the notifier in the perf_event subsystem, though.
5251 */
5252static struct notifier_block migration_notifier = {
5253	.notifier_call = migration_call,
5254	.priority = CPU_PRI_MIGRATION,
5255};
5256
5257static void __cpuinit set_cpu_rq_start_time(void)
5258{
5259	int cpu = smp_processor_id();
5260	struct rq *rq = cpu_rq(cpu);
5261	rq->age_stamp = sched_clock_cpu(cpu);
5262}
5263
5264static int sched_cpu_active(struct notifier_block *nfb,
5265				      unsigned long action, void *hcpu)
5266{
5267	switch (action & ~CPU_TASKS_FROZEN) {
5268	case CPU_STARTING:
5269		set_cpu_rq_start_time();
5270		return NOTIFY_OK;
5271	case CPU_DOWN_FAILED:
5272		set_cpu_active((long)hcpu, true);
5273		return NOTIFY_OK;
5274	default:
5275		return NOTIFY_DONE;
5276	}
5277}
5278
5279static int sched_cpu_inactive(struct notifier_block *nfb,
5280					unsigned long action, void *hcpu)
5281{
5282	unsigned long flags;
5283	long cpu = (long)hcpu;
5284	struct dl_bw *dl_b;
5285
5286	switch (action & ~CPU_TASKS_FROZEN) {
5287	case CPU_DOWN_PREPARE:
5288		set_cpu_active(cpu, false);
5289
5290		/* explicitly allow suspend */
5291		if (!(action & CPU_TASKS_FROZEN)) {
5292			bool overflow;
5293			int cpus;
5294
5295			rcu_read_lock_sched();
5296			dl_b = dl_bw_of(cpu);
5297
5298			raw_spin_lock_irqsave(&dl_b->lock, flags);
5299			cpus = dl_bw_cpus(cpu);
5300			overflow = __dl_overflow(dl_b, cpus, 0, 0);
5301			raw_spin_unlock_irqrestore(&dl_b->lock, flags);
5302
5303			rcu_read_unlock_sched();
5304
5305			if (overflow)
5306				return notifier_from_errno(-EBUSY);
5307		}
5308		return NOTIFY_OK;
5309	}
5310
5311	return NOTIFY_DONE;
5312}
5313
5314static int __init migration_init(void)
5315{
5316	void *cpu = (void *)(long)smp_processor_id();
5317	int err;
5318
5319	/* Initialize migration for the boot CPU */
5320	err = migration_call(&migration_notifier, CPU_UP_PREPARE, cpu);
5321	BUG_ON(err == NOTIFY_BAD);
5322	migration_call(&migration_notifier, CPU_ONLINE, cpu);
5323	register_cpu_notifier(&migration_notifier);
5324
5325	/* Register cpu active notifiers */
5326	cpu_notifier(sched_cpu_active, CPU_PRI_SCHED_ACTIVE);
5327	cpu_notifier(sched_cpu_inactive, CPU_PRI_SCHED_INACTIVE);
5328
5329	return 0;
5330}
5331early_initcall(migration_init);
5332#endif
5333
5334#ifdef CONFIG_SMP
5335
5336static cpumask_var_t sched_domains_tmpmask; /* sched_domains_mutex */
5337
5338#ifdef CONFIG_SCHED_DEBUG
5339
5340static __read_mostly int sched_debug_enabled;
5341
5342static int __init sched_debug_setup(char *str)
5343{
5344	sched_debug_enabled = 1;
5345
5346	return 0;
5347}
5348early_param("sched_debug", sched_debug_setup);
5349
5350static inline bool sched_debug(void)
5351{
5352	return sched_debug_enabled;
5353}
5354
5355static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
5356				  struct cpumask *groupmask)
5357{
5358	struct sched_group *group = sd->groups;
5359	char str[256];
5360
5361	cpulist_scnprintf(str, sizeof(str), sched_domain_span(sd));
5362	cpumask_clear(groupmask);
5363
5364	printk(KERN_DEBUG "%*s domain %d: ", level, "", level);
5365
5366	if (!(sd->flags & SD_LOAD_BALANCE)) {
5367		printk("does not load-balance\n");
5368		if (sd->parent)
5369			printk(KERN_ERR "ERROR: !SD_LOAD_BALANCE domain"
5370					" has parent");
5371		return -1;
5372	}
5373
5374	printk(KERN_CONT "span %s level %s\n", str, sd->name);
5375
5376	if (!cpumask_test_cpu(cpu, sched_domain_span(sd))) {
5377		printk(KERN_ERR "ERROR: domain->span does not contain "
5378				"CPU%d\n", cpu);
5379	}
5380	if (!cpumask_test_cpu(cpu, sched_group_cpus(group))) {
5381		printk(KERN_ERR "ERROR: domain->groups does not contain"
5382				" CPU%d\n", cpu);
5383	}
5384
5385	printk(KERN_DEBUG "%*s groups:", level + 1, "");
5386	do {
5387		if (!group) {
5388			printk("\n");
5389			printk(KERN_ERR "ERROR: group is NULL\n");
5390			break;
5391		}
5392
5393		/*
5394		 * Even though we initialize ->capacity to something semi-sane,
5395		 * we leave capacity_orig unset. This allows us to detect if
5396		 * domain iteration is still funny without causing /0 traps.
5397		 */
5398		if (!group->sgc->capacity_orig) {
5399			printk(KERN_CONT "\n");
5400			printk(KERN_ERR "ERROR: domain->cpu_capacity not set\n");
5401			break;
5402		}
5403
5404		if (!cpumask_weight(sched_group_cpus(group))) {
5405			printk(KERN_CONT "\n");
5406			printk(KERN_ERR "ERROR: empty group\n");
5407			break;
5408		}
5409
5410		if (!(sd->flags & SD_OVERLAP) &&
5411		    cpumask_intersects(groupmask, sched_group_cpus(group))) {
5412			printk(KERN_CONT "\n");
5413			printk(KERN_ERR "ERROR: repeated CPUs\n");
5414			break;
5415		}
5416
5417		cpumask_or(groupmask, groupmask, sched_group_cpus(group));
5418
5419		cpulist_scnprintf(str, sizeof(str), sched_group_cpus(group));
5420
5421		printk(KERN_CONT " %s", str);
5422		if (group->sgc->capacity != SCHED_CAPACITY_SCALE) {
5423			printk(KERN_CONT " (cpu_capacity = %d)",
5424				group->sgc->capacity);
5425		}
5426
5427		group = group->next;
5428	} while (group != sd->groups);
5429	printk(KERN_CONT "\n");
5430
5431	if (!cpumask_equal(sched_domain_span(sd), groupmask))
5432		printk(KERN_ERR "ERROR: groups don't span domain->span\n");
5433
5434	if (sd->parent &&
5435	    !cpumask_subset(groupmask, sched_domain_span(sd->parent)))
5436		printk(KERN_ERR "ERROR: parent span is not a superset "
5437			"of domain->span\n");
5438	return 0;
5439}
5440
5441static void sched_domain_debug(struct sched_domain *sd, int cpu)
5442{
5443	int level = 0;
5444
5445	if (!sched_debug_enabled)
5446		return;
5447
5448	if (!sd) {
5449		printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
5450		return;
5451	}
5452
5453	printk(KERN_DEBUG "CPU%d attaching sched-domain:\n", cpu);
5454
5455	for (;;) {
5456		if (sched_domain_debug_one(sd, cpu, level, sched_domains_tmpmask))
5457			break;
5458		level++;
5459		sd = sd->parent;
5460		if (!sd)
5461			break;
5462	}
5463}
5464#else /* !CONFIG_SCHED_DEBUG */
5465# define sched_domain_debug(sd, cpu) do { } while (0)
5466static inline bool sched_debug(void)
5467{
5468	return false;
5469}
5470#endif /* CONFIG_SCHED_DEBUG */
5471
5472static int sd_degenerate(struct sched_domain *sd)
5473{
5474	if (cpumask_weight(sched_domain_span(sd)) == 1)
5475		return 1;
5476
5477	/* Following flags need at least 2 groups */
5478	if (sd->flags & (SD_LOAD_BALANCE |
5479			 SD_BALANCE_NEWIDLE |
5480			 SD_BALANCE_FORK |
5481			 SD_BALANCE_EXEC |
5482			 SD_SHARE_CPUCAPACITY |
5483			 SD_SHARE_PKG_RESOURCES |
5484			 SD_SHARE_POWERDOMAIN)) {
5485		if (sd->groups != sd->groups->next)
5486			return 0;
5487	}
5488
5489	/* Following flags don't use groups */
5490	if (sd->flags & (SD_WAKE_AFFINE))
5491		return 0;
5492
5493	return 1;
5494}
5495
5496static int
5497sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
5498{
5499	unsigned long cflags = sd->flags, pflags = parent->flags;
5500
5501	if (sd_degenerate(parent))
5502		return 1;
5503
5504	if (!cpumask_equal(sched_domain_span(sd), sched_domain_span(parent)))
5505		return 0;
5506
5507	/* Flags needing groups don't count if only 1 group in parent */
5508	if (parent->groups == parent->groups->next) {
5509		pflags &= ~(SD_LOAD_BALANCE |
5510				SD_BALANCE_NEWIDLE |
5511				SD_BALANCE_FORK |
5512				SD_BALANCE_EXEC |
5513				SD_SHARE_CPUCAPACITY |
5514				SD_SHARE_PKG_RESOURCES |
5515				SD_PREFER_SIBLING |
5516				SD_SHARE_POWERDOMAIN);
5517		if (nr_node_ids == 1)
5518			pflags &= ~SD_SERIALIZE;
5519	}
5520	if (~cflags & pflags)
5521		return 0;
5522
5523	return 1;
5524}
5525
5526static void free_rootdomain(struct rcu_head *rcu)
5527{
5528	struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
5529
5530	cpupri_cleanup(&rd->cpupri);
5531	cpudl_cleanup(&rd->cpudl);
5532	free_cpumask_var(rd->dlo_mask);
5533	free_cpumask_var(rd->rto_mask);
5534	free_cpumask_var(rd->online);
5535	free_cpumask_var(rd->span);
5536	kfree(rd);
5537}
5538
5539static void rq_attach_root(struct rq *rq, struct root_domain *rd)
5540{
5541	struct root_domain *old_rd = NULL;
5542	unsigned long flags;
5543
5544	raw_spin_lock_irqsave(&rq->lock, flags);
5545
5546	if (rq->rd) {
5547		old_rd = rq->rd;
5548
5549		if (cpumask_test_cpu(rq->cpu, old_rd->online))
5550			set_rq_offline(rq);
5551
5552		cpumask_clear_cpu(rq->cpu, old_rd->span);
5553
5554		/*
5555		 * If we dont want to free the old_rd yet then
5556		 * set old_rd to NULL to skip the freeing later
5557		 * in this function:
5558		 */
5559		if (!atomic_dec_and_test(&old_rd->refcount))
5560			old_rd = NULL;
5561	}
5562
5563	atomic_inc(&rd->refcount);
5564	rq->rd = rd;
5565
5566	cpumask_set_cpu(rq->cpu, rd->span);
5567	if (cpumask_test_cpu(rq->cpu, cpu_active_mask))
5568		set_rq_online(rq);
5569
5570	raw_spin_unlock_irqrestore(&rq->lock, flags);
5571
5572	if (old_rd)
5573		call_rcu_sched(&old_rd->rcu, free_rootdomain);
5574}
5575
5576static int init_rootdomain(struct root_domain *rd)
5577{
5578	memset(rd, 0, sizeof(*rd));
5579
5580	if (!alloc_cpumask_var(&rd->span, GFP_KERNEL))
5581		goto out;
5582	if (!alloc_cpumask_var(&rd->online, GFP_KERNEL))
5583		goto free_span;
5584	if (!alloc_cpumask_var(&rd->dlo_mask, GFP_KERNEL))
5585		goto free_online;
5586	if (!alloc_cpumask_var(&rd->rto_mask, GFP_KERNEL))
5587		goto free_dlo_mask;
5588
5589	init_dl_bw(&rd->dl_bw);
5590	if (cpudl_init(&rd->cpudl) != 0)
5591		goto free_dlo_mask;
5592
5593	if (cpupri_init(&rd->cpupri) != 0)
5594		goto free_rto_mask;
5595	return 0;
5596
5597free_rto_mask:
5598	free_cpumask_var(rd->rto_mask);
5599free_dlo_mask:
5600	free_cpumask_var(rd->dlo_mask);
5601free_online:
5602	free_cpumask_var(rd->online);
5603free_span:
5604	free_cpumask_var(rd->span);
5605out:
5606	return -ENOMEM;
5607}
5608
5609/*
5610 * By default the system creates a single root-domain with all cpus as
5611 * members (mimicking the global state we have today).
5612 */
5613struct root_domain def_root_domain;
5614
5615static void init_defrootdomain(void)
5616{
5617	init_rootdomain(&def_root_domain);
5618
5619	atomic_set(&def_root_domain.refcount, 1);
5620}
5621
5622static struct root_domain *alloc_rootdomain(void)
5623{
5624	struct root_domain *rd;
5625
5626	rd = kmalloc(sizeof(*rd), GFP_KERNEL);
5627	if (!rd)
5628		return NULL;
5629
5630	if (init_rootdomain(rd) != 0) {
5631		kfree(rd);
5632		return NULL;
5633	}
5634
5635	return rd;
5636}
5637
5638static void free_sched_groups(struct sched_group *sg, int free_sgc)
5639{
5640	struct sched_group *tmp, *first;
5641
5642	if (!sg)
5643		return;
5644
5645	first = sg;
5646	do {
5647		tmp = sg->next;
5648
5649		if (free_sgc && atomic_dec_and_test(&sg->sgc->ref))
5650			kfree(sg->sgc);
5651
5652		kfree(sg);
5653		sg = tmp;
5654	} while (sg != first);
5655}
5656
5657static void free_sched_domain(struct rcu_head *rcu)
5658{
5659	struct sched_domain *sd = container_of(rcu, struct sched_domain, rcu);
5660
5661	/*
5662	 * If its an overlapping domain it has private groups, iterate and
5663	 * nuke them all.
5664	 */
5665	if (sd->flags & SD_OVERLAP) {
5666		free_sched_groups(sd->groups, 1);
5667	} else if (atomic_dec_and_test(&sd->groups->ref)) {
5668		kfree(sd->groups->sgc);
5669		kfree(sd->groups);
5670	}
5671	kfree(sd);
5672}
5673
5674static void destroy_sched_domain(struct sched_domain *sd, int cpu)
5675{
5676	call_rcu(&sd->rcu, free_sched_domain);
5677}
5678
5679static void destroy_sched_domains(struct sched_domain *sd, int cpu)
5680{
5681	for (; sd; sd = sd->parent)
5682		destroy_sched_domain(sd, cpu);
5683}
5684
5685/*
5686 * Keep a special pointer to the highest sched_domain that has
5687 * SD_SHARE_PKG_RESOURCE set (Last Level Cache Domain) for this
5688 * allows us to avoid some pointer chasing select_idle_sibling().
5689 *
5690 * Also keep a unique ID per domain (we use the first cpu number in
5691 * the cpumask of the domain), this allows us to quickly tell if
5692 * two cpus are in the same cache domain, see cpus_share_cache().
5693 */
5694DEFINE_PER_CPU(struct sched_domain *, sd_llc);
5695DEFINE_PER_CPU(int, sd_llc_size);
5696DEFINE_PER_CPU(int, sd_llc_id);
5697DEFINE_PER_CPU(struct sched_domain *, sd_numa);
5698DEFINE_PER_CPU(struct sched_domain *, sd_busy);
5699DEFINE_PER_CPU(struct sched_domain *, sd_asym);
5700
5701static void update_top_cache_domain(int cpu)
5702{
5703	struct sched_domain *sd;
5704	struct sched_domain *busy_sd = NULL;
5705	int id = cpu;
5706	int size = 1;
5707
5708	sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
5709	if (sd) {
5710		id = cpumask_first(sched_domain_span(sd));
5711		size = cpumask_weight(sched_domain_span(sd));
5712		busy_sd = sd->parent; /* sd_busy */
5713	}
5714	rcu_assign_pointer(per_cpu(sd_busy, cpu), busy_sd);
5715
5716	rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
5717	per_cpu(sd_llc_size, cpu) = size;
5718	per_cpu(sd_llc_id, cpu) = id;
5719
5720	sd = lowest_flag_domain(cpu, SD_NUMA);
5721	rcu_assign_pointer(per_cpu(sd_numa, cpu), sd);
5722
5723	sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
5724	rcu_assign_pointer(per_cpu(sd_asym, cpu), sd);
5725}
5726
5727/*
5728 * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
5729 * hold the hotplug lock.
5730 */
5731static void
5732cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
5733{
5734	struct rq *rq = cpu_rq(cpu);
5735	struct sched_domain *tmp;
5736
5737	/* Remove the sched domains which do not contribute to scheduling. */
5738	for (tmp = sd; tmp; ) {
5739		struct sched_domain *parent = tmp->parent;
5740		if (!parent)
5741			break;
5742
5743		if (sd_parent_degenerate(tmp, parent)) {
5744			tmp->parent = parent->parent;
5745			if (parent->parent)
5746				parent->parent->child = tmp;
5747			/*
5748			 * Transfer SD_PREFER_SIBLING down in case of a
5749			 * degenerate parent; the spans match for this
5750			 * so the property transfers.
5751			 */
5752			if (parent->flags & SD_PREFER_SIBLING)
5753				tmp->flags |= SD_PREFER_SIBLING;
5754			destroy_sched_domain(parent, cpu);
5755		} else
5756			tmp = tmp->parent;
5757	}
5758
5759	if (sd && sd_degenerate(sd)) {
5760		tmp = sd;
5761		sd = sd->parent;
5762		destroy_sched_domain(tmp, cpu);
5763		if (sd)
5764			sd->child = NULL;
5765	}
5766
5767	sched_domain_debug(sd, cpu);
5768
5769	rq_attach_root(rq, rd);
5770	tmp = rq->sd;
5771	rcu_assign_pointer(rq->sd, sd);
5772	destroy_sched_domains(tmp, cpu);
5773
5774	update_top_cache_domain(cpu);
5775}
5776
5777/* cpus with isolated domains */
5778static cpumask_var_t cpu_isolated_map;
5779
5780/* Setup the mask of cpus configured for isolated domains */
5781static int __init isolated_cpu_setup(char *str)
5782{
5783	alloc_bootmem_cpumask_var(&cpu_isolated_map);
5784	cpulist_parse(str, cpu_isolated_map);
5785	return 1;
5786}
5787
5788__setup("isolcpus=", isolated_cpu_setup);
5789
5790struct s_data {
5791	struct sched_domain ** __percpu sd;
5792	struct root_domain	*rd;
5793};
5794
5795enum s_alloc {
5796	sa_rootdomain,
5797	sa_sd,
5798	sa_sd_storage,
5799	sa_none,
5800};
5801
5802/*
5803 * Build an iteration mask that can exclude certain CPUs from the upwards
5804 * domain traversal.
5805 *
5806 * Asymmetric node setups can result in situations where the domain tree is of
5807 * unequal depth, make sure to skip domains that already cover the entire
5808 * range.
5809 *
5810 * In that case build_sched_domains() will have terminated the iteration early
5811 * and our sibling sd spans will be empty. Domains should always include the
5812 * cpu they're built on, so check that.
5813 *
5814 */
5815static void build_group_mask(struct sched_domain *sd, struct sched_group *sg)
5816{
5817	const struct cpumask *span = sched_domain_span(sd);
5818	struct sd_data *sdd = sd->private;
5819	struct sched_domain *sibling;
5820	int i;
5821
5822	for_each_cpu(i, span) {
5823		sibling = *per_cpu_ptr(sdd->sd, i);
5824		if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
5825			continue;
5826
5827		cpumask_set_cpu(i, sched_group_mask(sg));
5828	}
5829}
5830
5831/*
5832 * Return the canonical balance cpu for this group, this is the first cpu
5833 * of this group that's also in the iteration mask.
5834 */
5835int group_balance_cpu(struct sched_group *sg)
5836{
5837	return cpumask_first_and(sched_group_cpus(sg), sched_group_mask(sg));
5838}
5839
5840static int
5841build_overlap_sched_groups(struct sched_domain *sd, int cpu)
5842{
5843	struct sched_group *first = NULL, *last = NULL, *groups = NULL, *sg;
5844	const struct cpumask *span = sched_domain_span(sd);
5845	struct cpumask *covered = sched_domains_tmpmask;
5846	struct sd_data *sdd = sd->private;
5847	struct sched_domain *sibling;
5848	int i;
5849
5850	cpumask_clear(covered);
5851
5852	for_each_cpu(i, span) {
5853		struct cpumask *sg_span;
5854
5855		if (cpumask_test_cpu(i, covered))
5856			continue;
5857
5858		sibling = *per_cpu_ptr(sdd->sd, i);
5859
5860		/* See the comment near build_group_mask(). */
5861		if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
5862			continue;
5863
5864		sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
5865				GFP_KERNEL, cpu_to_node(cpu));
5866
5867		if (!sg)
5868			goto fail;
5869
5870		sg_span = sched_group_cpus(sg);
5871		if (sibling->child)
5872			cpumask_copy(sg_span, sched_domain_span(sibling->child));
5873		else
5874			cpumask_set_cpu(i, sg_span);
5875
5876		cpumask_or(covered, covered, sg_span);
5877
5878		sg->sgc = *per_cpu_ptr(sdd->sgc, i);
5879		if (atomic_inc_return(&sg->sgc->ref) == 1)
5880			build_group_mask(sd, sg);
5881
5882		/*
5883		 * Initialize sgc->capacity such that even if we mess up the
5884		 * domains and no possible iteration will get us here, we won't
5885		 * die on a /0 trap.
5886		 */
5887		sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
5888		sg->sgc->capacity_orig = sg->sgc->capacity;
5889
5890		/*
5891		 * Make sure the first group of this domain contains the
5892		 * canonical balance cpu. Otherwise the sched_domain iteration
5893		 * breaks. See update_sg_lb_stats().
5894		 */
5895		if ((!groups && cpumask_test_cpu(cpu, sg_span)) ||
5896		    group_balance_cpu(sg) == cpu)
5897			groups = sg;
5898
5899		if (!first)
5900			first = sg;
5901		if (last)
5902			last->next = sg;
5903		last = sg;
5904		last->next = first;
5905	}
5906	sd->groups = groups;
5907
5908	return 0;
5909
5910fail:
5911	free_sched_groups(first, 0);
5912
5913	return -ENOMEM;
5914}
5915
5916static int get_group(int cpu, struct sd_data *sdd, struct sched_group **sg)
5917{
5918	struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
5919	struct sched_domain *child = sd->child;
5920
5921	if (child)
5922		cpu = cpumask_first(sched_domain_span(child));
5923
5924	if (sg) {
5925		*sg = *per_cpu_ptr(sdd->sg, cpu);
5926		(*sg)->sgc = *per_cpu_ptr(sdd->sgc, cpu);
5927		atomic_set(&(*sg)->sgc->ref, 1); /* for claim_allocations */
5928	}
5929
5930	return cpu;
5931}
5932
5933/*
5934 * build_sched_groups will build a circular linked list of the groups
5935 * covered by the given span, and will set each group's ->cpumask correctly,
5936 * and ->cpu_capacity to 0.
5937 *
5938 * Assumes the sched_domain tree is fully constructed
5939 */
5940static int
5941build_sched_groups(struct sched_domain *sd, int cpu)
5942{
5943	struct sched_group *first = NULL, *last = NULL;
5944	struct sd_data *sdd = sd->private;
5945	const struct cpumask *span = sched_domain_span(sd);
5946	struct cpumask *covered;
5947	int i;
5948
5949	get_group(cpu, sdd, &sd->groups);
5950	atomic_inc(&sd->groups->ref);
5951
5952	if (cpu != cpumask_first(span))
5953		return 0;
5954
5955	lockdep_assert_held(&sched_domains_mutex);
5956	covered = sched_domains_tmpmask;
5957
5958	cpumask_clear(covered);
5959
5960	for_each_cpu(i, span) {
5961		struct sched_group *sg;
5962		int group, j;
5963
5964		if (cpumask_test_cpu(i, covered))
5965			continue;
5966
5967		group = get_group(i, sdd, &sg);
5968		cpumask_setall(sched_group_mask(sg));
5969
5970		for_each_cpu(j, span) {
5971			if (get_group(j, sdd, NULL) != group)
5972				continue;
5973
5974			cpumask_set_cpu(j, covered);
5975			cpumask_set_cpu(j, sched_group_cpus(sg));
5976		}
5977
5978		if (!first)
5979			first = sg;
5980		if (last)
5981			last->next = sg;
5982		last = sg;
5983	}
5984	last->next = first;
5985
5986	return 0;
5987}
5988
5989/*
5990 * Initialize sched groups cpu_capacity.
5991 *
5992 * cpu_capacity indicates the capacity of sched group, which is used while
5993 * distributing the load between different sched groups in a sched domain.
5994 * Typically cpu_capacity for all the groups in a sched domain will be same
5995 * unless there are asymmetries in the topology. If there are asymmetries,
5996 * group having more cpu_capacity will pickup more load compared to the
5997 * group having less cpu_capacity.
5998 */
5999static void init_sched_groups_capacity(int cpu, struct sched_domain *sd)
6000{
6001	struct sched_group *sg = sd->groups;
6002
6003	WARN_ON(!sg);
6004
6005	do {
6006		sg->group_weight = cpumask_weight(sched_group_cpus(sg));
6007		sg = sg->next;
6008	} while (sg != sd->groups);
6009
6010	if (cpu != group_balance_cpu(sg))
6011		return;
6012
6013	update_group_capacity(sd, cpu);
6014	atomic_set(&sg->sgc->nr_busy_cpus, sg->group_weight);
6015}
6016
6017/*
6018 * Initializers for schedule domains
6019 * Non-inlined to reduce accumulated stack pressure in build_sched_domains()
6020 */
6021
6022static int default_relax_domain_level = -1;
6023int sched_domain_level_max;
6024
6025static int __init setup_relax_domain_level(char *str)
6026{
6027	if (kstrtoint(str, 0, &default_relax_domain_level))
6028		pr_warn("Unable to set relax_domain_level\n");
6029
6030	return 1;
6031}
6032__setup("relax_domain_level=", setup_relax_domain_level);
6033
6034static void set_domain_attribute(struct sched_domain *sd,
6035				 struct sched_domain_attr *attr)
6036{
6037	int request;
6038
6039	if (!attr || attr->relax_domain_level < 0) {
6040		if (default_relax_domain_level < 0)
6041			return;
6042		else
6043			request = default_relax_domain_level;
6044	} else
6045		request = attr->relax_domain_level;
6046	if (request < sd->level) {
6047		/* turn off idle balance on this domain */
6048		sd->flags &= ~(SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
6049	} else {
6050		/* turn on idle balance on this domain */
6051		sd->flags |= (SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
6052	}
6053}
6054
6055static void __sdt_free(const struct cpumask *cpu_map);
6056static int __sdt_alloc(const struct cpumask *cpu_map);
6057
6058static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
6059				 const struct cpumask *cpu_map)
6060{
6061	switch (what) {
6062	case sa_rootdomain:
6063		if (!atomic_read(&d->rd->refcount))
6064			free_rootdomain(&d->rd->rcu); /* fall through */
6065	case sa_sd:
6066		free_percpu(d->sd); /* fall through */
6067	case sa_sd_storage:
6068		__sdt_free(cpu_map); /* fall through */
6069	case sa_none:
6070		break;
6071	}
6072}
6073
6074static enum s_alloc __visit_domain_allocation_hell(struct s_data *d,
6075						   const struct cpumask *cpu_map)
6076{
6077	memset(d, 0, sizeof(*d));
6078
6079	if (__sdt_alloc(cpu_map))
6080		return sa_sd_storage;
6081	d->sd = alloc_percpu(struct sched_domain *);
6082	if (!d->sd)
6083		return sa_sd_storage;
6084	d->rd = alloc_rootdomain();
6085	if (!d->rd)
6086		return sa_sd;
6087	return sa_rootdomain;
6088}
6089
6090/*
6091 * NULL the sd_data elements we've used to build the sched_domain and
6092 * sched_group structure so that the subsequent __free_domain_allocs()
6093 * will not free the data we're using.
6094 */
6095static void claim_allocations(int cpu, struct sched_domain *sd)
6096{
6097	struct sd_data *sdd = sd->private;
6098
6099	WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
6100	*per_cpu_ptr(sdd->sd, cpu) = NULL;
6101
6102	if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
6103		*per_cpu_ptr(sdd->sg, cpu) = NULL;
6104
6105	if (atomic_read(&(*per_cpu_ptr(sdd->sgc, cpu))->ref))
6106		*per_cpu_ptr(sdd->sgc, cpu) = NULL;
6107}
6108
6109#ifdef CONFIG_NUMA
6110static int sched_domains_numa_levels;
6111static int *sched_domains_numa_distance;
6112static struct cpumask ***sched_domains_numa_masks;
6113static int sched_domains_curr_level;
6114#endif
6115
6116/*
6117 * SD_flags allowed in topology descriptions.
6118 *
6119 * SD_SHARE_CPUCAPACITY      - describes SMT topologies
6120 * SD_SHARE_PKG_RESOURCES - describes shared caches
6121 * SD_NUMA                - describes NUMA topologies
6122 * SD_SHARE_POWERDOMAIN   - describes shared power domain
6123 *
6124 * Odd one out:
6125 * SD_ASYM_PACKING        - describes SMT quirks
6126 */
6127#define TOPOLOGY_SD_FLAGS		\
6128	(SD_SHARE_CPUCAPACITY |		\
6129	 SD_SHARE_PKG_RESOURCES |	\
6130	 SD_NUMA |			\
6131	 SD_ASYM_PACKING |		\
6132	 SD_SHARE_POWERDOMAIN)
6133
6134static struct sched_domain *
6135sd_init(struct sched_domain_topology_level *tl, int cpu)
6136{
6137	struct sched_domain *sd = *per_cpu_ptr(tl->data.sd, cpu);
6138	int sd_weight, sd_flags = 0;
6139
6140#ifdef CONFIG_NUMA
6141	/*
6142	 * Ugly hack to pass state to sd_numa_mask()...
6143	 */
6144	sched_domains_curr_level = tl->numa_level;
6145#endif
6146
6147	sd_weight = cpumask_weight(tl->mask(cpu));
6148
6149	if (tl->sd_flags)
6150		sd_flags = (*tl->sd_flags)();
6151	if (WARN_ONCE(sd_flags & ~TOPOLOGY_SD_FLAGS,
6152			"wrong sd_flags in topology description\n"))
6153		sd_flags &= ~TOPOLOGY_SD_FLAGS;
6154
6155	*sd = (struct sched_domain){
6156		.min_interval		= sd_weight,
6157		.max_interval		= 2*sd_weight,
6158		.busy_factor		= 32,
6159		.imbalance_pct		= 125,
6160
6161		.cache_nice_tries	= 0,
6162		.busy_idx		= 0,
6163		.idle_idx		= 0,
6164		.newidle_idx		= 0,
6165		.wake_idx		= 0,
6166		.forkexec_idx		= 0,
6167
6168		.flags			= 1*SD_LOAD_BALANCE
6169					| 1*SD_BALANCE_NEWIDLE
6170					| 1*SD_BALANCE_EXEC
6171					| 1*SD_BALANCE_FORK
6172					| 0*SD_BALANCE_WAKE
6173					| 1*SD_WAKE_AFFINE
6174					| 0*SD_SHARE_CPUCAPACITY
6175					| 0*SD_SHARE_PKG_RESOURCES
6176					| 0*SD_SERIALIZE
6177					| 0*SD_PREFER_SIBLING
6178					| 0*SD_NUMA
6179					| sd_flags
6180					,
6181
6182		.last_balance		= jiffies,
6183		.balance_interval	= sd_weight,
6184		.smt_gain		= 0,
6185		.max_newidle_lb_cost	= 0,
6186		.next_decay_max_lb_cost	= jiffies,
6187#ifdef CONFIG_SCHED_DEBUG
6188		.name			= tl->name,
6189#endif
6190	};
6191
6192	/*
6193	 * Convert topological properties into behaviour.
6194	 */
6195
6196	if (sd->flags & SD_SHARE_CPUCAPACITY) {
6197		sd->imbalance_pct = 110;
6198		sd->smt_gain = 1178; /* ~15% */
6199
6200	} else if (sd->flags & SD_SHARE_PKG_RESOURCES) {
6201		sd->imbalance_pct = 117;
6202		sd->cache_nice_tries = 1;
6203		sd->busy_idx = 2;
6204
6205#ifdef CONFIG_NUMA
6206	} else if (sd->flags & SD_NUMA) {
6207		sd->cache_nice_tries = 2;
6208		sd->busy_idx = 3;
6209		sd->idle_idx = 2;
6210
6211		sd->flags |= SD_SERIALIZE;
6212		if (sched_domains_numa_distance[tl->numa_level] > RECLAIM_DISTANCE) {
6213			sd->flags &= ~(SD_BALANCE_EXEC |
6214				       SD_BALANCE_FORK |
6215				       SD_WAKE_AFFINE);
6216		}
6217
6218#endif
6219	} else {
6220		sd->flags |= SD_PREFER_SIBLING;
6221		sd->cache_nice_tries = 1;
6222		sd->busy_idx = 2;
6223		sd->idle_idx = 1;
6224	}
6225
6226	sd->private = &tl->data;
6227
6228	return sd;
6229}
6230
6231/*
6232 * Topology list, bottom-up.
6233 */
6234static struct sched_domain_topology_level default_topology[] = {
6235#ifdef CONFIG_SCHED_SMT
6236	{ cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
6237#endif
6238#ifdef CONFIG_SCHED_MC
6239	{ cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
6240#endif
6241	{ cpu_cpu_mask, SD_INIT_NAME(DIE) },
6242	{ NULL, },
6243};
6244
6245struct sched_domain_topology_level *sched_domain_topology = default_topology;
6246
6247#define for_each_sd_topology(tl)			\
6248	for (tl = sched_domain_topology; tl->mask; tl++)
6249
6250void set_sched_topology(struct sched_domain_topology_level *tl)
6251{
6252	sched_domain_topology = tl;
6253}
6254
6255#ifdef CONFIG_NUMA
6256
6257static const struct cpumask *sd_numa_mask(int cpu)
6258{
6259	return sched_domains_numa_masks[sched_domains_curr_level][cpu_to_node(cpu)];
6260}
6261
6262static void sched_numa_warn(const char *str)
6263{
6264	static int done = false;
6265	int i,j;
6266
6267	if (done)
6268		return;
6269
6270	done = true;
6271
6272	printk(KERN_WARNING "ERROR: %s\n\n", str);
6273
6274	for (i = 0; i < nr_node_ids; i++) {
6275		printk(KERN_WARNING "  ");
6276		for (j = 0; j < nr_node_ids; j++)
6277			printk(KERN_CONT "%02d ", node_distance(i,j));
6278		printk(KERN_CONT "\n");
6279	}
6280	printk(KERN_WARNING "\n");
6281}
6282
6283static bool find_numa_distance(int distance)
6284{
6285	int i;
6286
6287	if (distance == node_distance(0, 0))
6288		return true;
6289
6290	for (i = 0; i < sched_domains_numa_levels; i++) {
6291		if (sched_domains_numa_distance[i] == distance)
6292			return true;
6293	}
6294
6295	return false;
6296}
6297
6298static void sched_init_numa(void)
6299{
6300	int next_distance, curr_distance = node_distance(0, 0);
6301	struct sched_domain_topology_level *tl;
6302	int level = 0;
6303	int i, j, k;
6304
6305	sched_domains_numa_distance = kzalloc(sizeof(int) * nr_node_ids, GFP_KERNEL);
6306	if (!sched_domains_numa_distance)
6307		return;
6308
6309	/*
6310	 * O(nr_nodes^2) deduplicating selection sort -- in order to find the
6311	 * unique distances in the node_distance() table.
6312	 *
6313	 * Assumes node_distance(0,j) includes all distances in
6314	 * node_distance(i,j) in order to avoid cubic time.
6315	 */
6316	next_distance = curr_distance;
6317	for (i = 0; i < nr_node_ids; i++) {
6318		for (j = 0; j < nr_node_ids; j++) {
6319			for (k = 0; k < nr_node_ids; k++) {
6320				int distance = node_distance(i, k);
6321
6322				if (distance > curr_distance &&
6323				    (distance < next_distance ||
6324				     next_distance == curr_distance))
6325					next_distance = distance;
6326
6327				/*
6328				 * While not a strong assumption it would be nice to know
6329				 * about cases where if node A is connected to B, B is not
6330				 * equally connected to A.
6331				 */
6332				if (sched_debug() && node_distance(k, i) != distance)
6333					sched_numa_warn("Node-distance not symmetric");
6334
6335				if (sched_debug() && i && !find_numa_distance(distance))
6336					sched_numa_warn("Node-0 not representative");
6337			}
6338			if (next_distance != curr_distance) {
6339				sched_domains_numa_distance[level++] = next_distance;
6340				sched_domains_numa_levels = level;
6341				curr_distance = next_distance;
6342			} else break;
6343		}
6344
6345		/*
6346		 * In case of sched_debug() we verify the above assumption.
6347		 */
6348		if (!sched_debug())
6349			break;
6350	}
6351
6352	if (!level)
6353		return;
6354
6355	/*
6356	 * 'level' contains the number of unique distances, excluding the
6357	 * identity distance node_distance(i,i).
6358	 *
6359	 * The sched_domains_numa_distance[] array includes the actual distance
6360	 * numbers.
6361	 */
6362
6363	/*
6364	 * Here, we should temporarily reset sched_domains_numa_levels to 0.
6365	 * If it fails to allocate memory for array sched_domains_numa_masks[][],
6366	 * the array will contain less then 'level' members. This could be
6367	 * dangerous when we use it to iterate array sched_domains_numa_masks[][]
6368	 * in other functions.
6369	 *
6370	 * We reset it to 'level' at the end of this function.
6371	 */
6372	sched_domains_numa_levels = 0;
6373
6374	sched_domains_numa_masks = kzalloc(sizeof(void *) * level, GFP_KERNEL);
6375	if (!sched_domains_numa_masks)
6376		return;
6377
6378	/*
6379	 * Now for each level, construct a mask per node which contains all
6380	 * cpus of nodes that are that many hops away from us.
6381	 */
6382	for (i = 0; i < level; i++) {
6383		sched_domains_numa_masks[i] =
6384			kzalloc(nr_node_ids * sizeof(void *), GFP_KERNEL);
6385		if (!sched_domains_numa_masks[i])
6386			return;
6387
6388		for (j = 0; j < nr_node_ids; j++) {
6389			struct cpumask *mask = kzalloc(cpumask_size(), GFP_KERNEL);
6390			if (!mask)
6391				return;
6392
6393			sched_domains_numa_masks[i][j] = mask;
6394
6395			for (k = 0; k < nr_node_ids; k++) {
6396				if (node_distance(j, k) > sched_domains_numa_distance[i])
6397					continue;
6398
6399				cpumask_or(mask, mask, cpumask_of_node(k));
6400			}
6401		}
6402	}
6403
6404	/* Compute default topology size */
6405	for (i = 0; sched_domain_topology[i].mask; i++);
6406
6407	tl = kzalloc((i + level + 1) *
6408			sizeof(struct sched_domain_topology_level), GFP_KERNEL);
6409	if (!tl)
6410		return;
6411
6412	/*
6413	 * Copy the default topology bits..
6414	 */
6415	for (i = 0; sched_domain_topology[i].mask; i++)
6416		tl[i] = sched_domain_topology[i];
6417
6418	/*
6419	 * .. and append 'j' levels of NUMA goodness.
6420	 */
6421	for (j = 0; j < level; i++, j++) {
6422		tl[i] = (struct sched_domain_topology_level){
6423			.mask = sd_numa_mask,
6424			.sd_flags = cpu_numa_flags,
6425			.flags = SDTL_OVERLAP,
6426			.numa_level = j,
6427			SD_INIT_NAME(NUMA)
6428		};
6429	}
6430
6431	sched_domain_topology = tl;
6432
6433	sched_domains_numa_levels = level;
6434}
6435
6436static void sched_domains_numa_masks_set(int cpu)
6437{
6438	int i, j;
6439	int node = cpu_to_node(cpu);
6440
6441	for (i = 0; i < sched_domains_numa_levels; i++) {
6442		for (j = 0; j < nr_node_ids; j++) {
6443			if (node_distance(j, node) <= sched_domains_numa_distance[i])
6444				cpumask_set_cpu(cpu, sched_domains_numa_masks[i][j]);
6445		}
6446	}
6447}
6448
6449static void sched_domains_numa_masks_clear(int cpu)
6450{
6451	int i, j;
6452	for (i = 0; i < sched_domains_numa_levels; i++) {
6453		for (j = 0; j < nr_node_ids; j++)
6454			cpumask_clear_cpu(cpu, sched_domains_numa_masks[i][j]);
6455	}
6456}
6457
6458/*
6459 * Update sched_domains_numa_masks[level][node] array when new cpus
6460 * are onlined.
6461 */
6462static int sched_domains_numa_masks_update(struct notifier_block *nfb,
6463					   unsigned long action,
6464					   void *hcpu)
6465{
6466	int cpu = (long)hcpu;
6467
6468	switch (action & ~CPU_TASKS_FROZEN) {
6469	case CPU_ONLINE:
6470		sched_domains_numa_masks_set(cpu);
6471		break;
6472
6473	case CPU_DEAD:
6474		sched_domains_numa_masks_clear(cpu);
6475		break;
6476
6477	default:
6478		return NOTIFY_DONE;
6479	}
6480
6481	return NOTIFY_OK;
6482}
6483#else
6484static inline void sched_init_numa(void)
6485{
6486}
6487
6488static int sched_domains_numa_masks_update(struct notifier_block *nfb,
6489					   unsigned long action,
6490					   void *hcpu)
6491{
6492	return 0;
6493}
6494#endif /* CONFIG_NUMA */
6495
6496static int __sdt_alloc(const struct cpumask *cpu_map)
6497{
6498	struct sched_domain_topology_level *tl;
6499	int j;
6500
6501	for_each_sd_topology(tl) {
6502		struct sd_data *sdd = &tl->data;
6503
6504		sdd->sd = alloc_percpu(struct sched_domain *);
6505		if (!sdd->sd)
6506			return -ENOMEM;
6507
6508		sdd->sg = alloc_percpu(struct sched_group *);
6509		if (!sdd->sg)
6510			return -ENOMEM;
6511
6512		sdd->sgc = alloc_percpu(struct sched_group_capacity *);
6513		if (!sdd->sgc)
6514			return -ENOMEM;
6515
6516		for_each_cpu(j, cpu_map) {
6517			struct sched_domain *sd;
6518			struct sched_group *sg;
6519			struct sched_group_capacity *sgc;
6520
6521		       	sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(),
6522					GFP_KERNEL, cpu_to_node(j));
6523			if (!sd)
6524				return -ENOMEM;
6525
6526			*per_cpu_ptr(sdd->sd, j) = sd;
6527
6528			sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
6529					GFP_KERNEL, cpu_to_node(j));
6530			if (!sg)
6531				return -ENOMEM;
6532
6533			sg->next = sg;
6534
6535			*per_cpu_ptr(sdd->sg, j) = sg;
6536
6537			sgc = kzalloc_node(sizeof(struct sched_group_capacity) + cpumask_size(),
6538					GFP_KERNEL, cpu_to_node(j));
6539			if (!sgc)
6540				return -ENOMEM;
6541
6542			*per_cpu_ptr(sdd->sgc, j) = sgc;
6543		}
6544	}
6545
6546	return 0;
6547}
6548
6549static void __sdt_free(const struct cpumask *cpu_map)
6550{
6551	struct sched_domain_topology_level *tl;
6552	int j;
6553
6554	for_each_sd_topology(tl) {
6555		struct sd_data *sdd = &tl->data;
6556
6557		for_each_cpu(j, cpu_map) {
6558			struct sched_domain *sd;
6559
6560			if (sdd->sd) {
6561				sd = *per_cpu_ptr(sdd->sd, j);
6562				if (sd && (sd->flags & SD_OVERLAP))
6563					free_sched_groups(sd->groups, 0);
6564				kfree(*per_cpu_ptr(sdd->sd, j));
6565			}
6566
6567			if (sdd->sg)
6568				kfree(*per_cpu_ptr(sdd->sg, j));
6569			if (sdd->sgc)
6570				kfree(*per_cpu_ptr(sdd->sgc, j));
6571		}
6572		free_percpu(sdd->sd);
6573		sdd->sd = NULL;
6574		free_percpu(sdd->sg);
6575		sdd->sg = NULL;
6576		free_percpu(sdd->sgc);
6577		sdd->sgc = NULL;
6578	}
6579}
6580
6581struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
6582		const struct cpumask *cpu_map, struct sched_domain_attr *attr,
6583		struct sched_domain *child, int cpu)
6584{
6585	struct sched_domain *sd = sd_init(tl, cpu);
6586	if (!sd)
6587		return child;
6588
6589	cpumask_and(sched_domain_span(sd), cpu_map, tl->mask(cpu));
6590	if (child) {
6591		sd->level = child->level + 1;
6592		sched_domain_level_max = max(sched_domain_level_max, sd->level);
6593		child->parent = sd;
6594		sd->child = child;
6595
6596		if (!cpumask_subset(sched_domain_span(child),
6597				    sched_domain_span(sd))) {
6598			pr_err("BUG: arch topology borken\n");
6599#ifdef CONFIG_SCHED_DEBUG
6600			pr_err("     the %s domain not a subset of the %s domain\n",
6601					child->name, sd->name);
6602#endif
6603			/* Fixup, ensure @sd has at least @child cpus. */
6604			cpumask_or(sched_domain_span(sd),
6605				   sched_domain_span(sd),
6606				   sched_domain_span(child));
6607		}
6608
6609	}
6610	set_domain_attribute(sd, attr);
6611
6612	return sd;
6613}
6614
6615/*
6616 * Build sched domains for a given set of cpus and attach the sched domains
6617 * to the individual cpus
6618 */
6619static int build_sched_domains(const struct cpumask *cpu_map,
6620			       struct sched_domain_attr *attr)
6621{
6622	enum s_alloc alloc_state;
6623	struct sched_domain *sd;
6624	struct s_data d;
6625	int i, ret = -ENOMEM;
6626
6627	alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
6628	if (alloc_state != sa_rootdomain)
6629		goto error;
6630
6631	/* Set up domains for cpus specified by the cpu_map. */
6632	for_each_cpu(i, cpu_map) {
6633		struct sched_domain_topology_level *tl;
6634
6635		sd = NULL;
6636		for_each_sd_topology(tl) {
6637			sd = build_sched_domain(tl, cpu_map, attr, sd, i);
6638			if (tl == sched_domain_topology)
6639				*per_cpu_ptr(d.sd, i) = sd;
6640			if (tl->flags & SDTL_OVERLAP || sched_feat(FORCE_SD_OVERLAP))
6641				sd->flags |= SD_OVERLAP;
6642			if (cpumask_equal(cpu_map, sched_domain_span(sd)))
6643				break;
6644		}
6645	}
6646
6647	/* Build the groups for the domains */
6648	for_each_cpu(i, cpu_map) {
6649		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
6650			sd->span_weight = cpumask_weight(sched_domain_span(sd));
6651			if (sd->flags & SD_OVERLAP) {
6652				if (build_overlap_sched_groups(sd, i))
6653					goto error;
6654			} else {
6655				if (build_sched_groups(sd, i))
6656					goto error;
6657			}
6658		}
6659	}
6660
6661	/* Calculate CPU capacity for physical packages and nodes */
6662	for (i = nr_cpumask_bits-1; i >= 0; i--) {
6663		if (!cpumask_test_cpu(i, cpu_map))
6664			continue;
6665
6666		for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
6667			claim_allocations(i, sd);
6668			init_sched_groups_capacity(i, sd);
6669		}
6670	}
6671
6672	/* Attach the domains */
6673	rcu_read_lock();
6674	for_each_cpu(i, cpu_map) {
6675		sd = *per_cpu_ptr(d.sd, i);
6676		cpu_attach_domain(sd, d.rd, i);
6677	}
6678	rcu_read_unlock();
6679
6680	ret = 0;
6681error:
6682	__free_domain_allocs(&d, alloc_state, cpu_map);
6683	return ret;
6684}
6685
6686static cpumask_var_t *doms_cur;	/* current sched domains */
6687static int ndoms_cur;		/* number of sched domains in 'doms_cur' */
6688static struct sched_domain_attr *dattr_cur;
6689				/* attribues of custom domains in 'doms_cur' */
6690
6691/*
6692 * Special case: If a kmalloc of a doms_cur partition (array of
6693 * cpumask) fails, then fallback to a single sched domain,
6694 * as determined by the single cpumask fallback_doms.
6695 */
6696static cpumask_var_t fallback_doms;
6697
6698/*
6699 * arch_update_cpu_topology lets virtualized architectures update the
6700 * cpu core maps. It is supposed to return 1 if the topology changed
6701 * or 0 if it stayed the same.
6702 */
6703int __weak arch_update_cpu_topology(void)
6704{
6705	return 0;
6706}
6707
6708cpumask_var_t *alloc_sched_domains(unsigned int ndoms)
6709{
6710	int i;
6711	cpumask_var_t *doms;
6712
6713	doms = kmalloc(sizeof(*doms) * ndoms, GFP_KERNEL);
6714	if (!doms)
6715		return NULL;
6716	for (i = 0; i < ndoms; i++) {
6717		if (!alloc_cpumask_var(&doms[i], GFP_KERNEL)) {
6718			free_sched_domains(doms, i);
6719			return NULL;
6720		}
6721	}
6722	return doms;
6723}
6724
6725void free_sched_domains(cpumask_var_t doms[], unsigned int ndoms)
6726{
6727	unsigned int i;
6728	for (i = 0; i < ndoms; i++)
6729		free_cpumask_var(doms[i]);
6730	kfree(doms);
6731}
6732
6733/*
6734 * Set up scheduler domains and groups. Callers must hold the hotplug lock.
6735 * For now this just excludes isolated cpus, but could be used to
6736 * exclude other special cases in the future.
6737 */
6738static int init_sched_domains(const struct cpumask *cpu_map)
6739{
6740	int err;
6741
6742	arch_update_cpu_topology();
6743	ndoms_cur = 1;
6744	doms_cur = alloc_sched_domains(ndoms_cur);
6745	if (!doms_cur)
6746		doms_cur = &fallback_doms;
6747	cpumask_andnot(doms_cur[0], cpu_map, cpu_isolated_map);
6748	err = build_sched_domains(doms_cur[0], NULL);
6749	register_sched_domain_sysctl();
6750
6751	return err;
6752}
6753
6754/*
6755 * Detach sched domains from a group of cpus specified in cpu_map
6756 * These cpus will now be attached to the NULL domain
6757 */
6758static void detach_destroy_domains(const struct cpumask *cpu_map)
6759{
6760	int i;
6761
6762	rcu_read_lock();
6763	for_each_cpu(i, cpu_map)
6764		cpu_attach_domain(NULL, &def_root_domain, i);
6765	rcu_read_unlock();
6766}
6767
6768/* handle null as "default" */
6769static int dattrs_equal(struct sched_domain_attr *cur, int idx_cur,
6770			struct sched_domain_attr *new, int idx_new)
6771{
6772	struct sched_domain_attr tmp;
6773
6774	/* fast path */
6775	if (!new && !cur)
6776		return 1;
6777
6778	tmp = SD_ATTR_INIT;
6779	return !memcmp(cur ? (cur + idx_cur) : &tmp,
6780			new ? (new + idx_new) : &tmp,
6781			sizeof(struct sched_domain_attr));
6782}
6783
6784/*
6785 * Partition sched domains as specified by the 'ndoms_new'
6786 * cpumasks in the array doms_new[] of cpumasks. This compares
6787 * doms_new[] to the current sched domain partitioning, doms_cur[].
6788 * It destroys each deleted domain and builds each new domain.
6789 *
6790 * 'doms_new' is an array of cpumask_var_t's of length 'ndoms_new'.
6791 * The masks don't intersect (don't overlap.) We should setup one
6792 * sched domain for each mask. CPUs not in any of the cpumasks will
6793 * not be load balanced. If the same cpumask appears both in the
6794 * current 'doms_cur' domains and in the new 'doms_new', we can leave
6795 * it as it is.
6796 *
6797 * The passed in 'doms_new' should be allocated using
6798 * alloc_sched_domains.  This routine takes ownership of it and will
6799 * free_sched_domains it when done with it. If the caller failed the
6800 * alloc call, then it can pass in doms_new == NULL && ndoms_new == 1,
6801 * and partition_sched_domains() will fallback to the single partition
6802 * 'fallback_doms', it also forces the domains to be rebuilt.
6803 *
6804 * If doms_new == NULL it will be replaced with cpu_online_mask.
6805 * ndoms_new == 0 is a special case for destroying existing domains,
6806 * and it will not create the default domain.
6807 *
6808 * Call with hotplug lock held
6809 */
6810void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[],
6811			     struct sched_domain_attr *dattr_new)
6812{
6813	int i, j, n;
6814	int new_topology;
6815
6816	mutex_lock(&sched_domains_mutex);
6817
6818	/* always unregister in case we don't destroy any domains */
6819	unregister_sched_domain_sysctl();
6820
6821	/* Let architecture update cpu core mappings. */
6822	new_topology = arch_update_cpu_topology();
6823
6824	n = doms_new ? ndoms_new : 0;
6825
6826	/* Destroy deleted domains */
6827	for (i = 0; i < ndoms_cur; i++) {
6828		for (j = 0; j < n && !new_topology; j++) {
6829			if (cpumask_equal(doms_cur[i], doms_new[j])
6830			    && dattrs_equal(dattr_cur, i, dattr_new, j))
6831				goto match1;
6832		}
6833		/* no match - a current sched domain not in new doms_new[] */
6834		detach_destroy_domains(doms_cur[i]);
6835match1:
6836		;
6837	}
6838
6839	n = ndoms_cur;
6840	if (doms_new == NULL) {
6841		n = 0;
6842		doms_new = &fallback_doms;
6843		cpumask_andnot(doms_new[0], cpu_active_mask, cpu_isolated_map);
6844		WARN_ON_ONCE(dattr_new);
6845	}
6846
6847	/* Build new domains */
6848	for (i = 0; i < ndoms_new; i++) {
6849		for (j = 0; j < n && !new_topology; j++) {
6850			if (cpumask_equal(doms_new[i], doms_cur[j])
6851			    && dattrs_equal(dattr_new, i, dattr_cur, j))
6852				goto match2;
6853		}
6854		/* no match - add a new doms_new */
6855		build_sched_domains(doms_new[i], dattr_new ? dattr_new + i : NULL);
6856match2:
6857		;
6858	}
6859
6860	/* Remember the new sched domains */
6861	if (doms_cur != &fallback_doms)
6862		free_sched_domains(doms_cur, ndoms_cur);
6863	kfree(dattr_cur);	/* kfree(NULL) is safe */
6864	doms_cur = doms_new;
6865	dattr_cur = dattr_new;
6866	ndoms_cur = ndoms_new;
6867
6868	register_sched_domain_sysctl();
6869
6870	mutex_unlock(&sched_domains_mutex);
6871}
6872
6873static int num_cpus_frozen;	/* used to mark begin/end of suspend/resume */
6874
6875/*
6876 * Update cpusets according to cpu_active mask.  If cpusets are
6877 * disabled, cpuset_update_active_cpus() becomes a simple wrapper
6878 * around partition_sched_domains().
6879 *
6880 * If we come here as part of a suspend/resume, don't touch cpusets because we
6881 * want to restore it back to its original state upon resume anyway.
6882 */
6883static int cpuset_cpu_active(struct notifier_block *nfb, unsigned long action,
6884			     void *hcpu)
6885{
6886	switch (action) {
6887	case CPU_ONLINE_FROZEN:
6888	case CPU_DOWN_FAILED_FROZEN:
6889
6890		/*
6891		 * num_cpus_frozen tracks how many CPUs are involved in suspend
6892		 * resume sequence. As long as this is not the last online
6893		 * operation in the resume sequence, just build a single sched
6894		 * domain, ignoring cpusets.
6895		 */
6896		num_cpus_frozen--;
6897		if (likely(num_cpus_frozen)) {
6898			partition_sched_domains(1, NULL, NULL);
6899			break;
6900		}
6901
6902		/*
6903		 * This is the last CPU online operation. So fall through and
6904		 * restore the original sched domains by considering the
6905		 * cpuset configurations.
6906		 */
6907
6908	case CPU_ONLINE:
6909	case CPU_DOWN_FAILED:
6910		cpuset_update_active_cpus(true);
6911		break;
6912	default:
6913		return NOTIFY_DONE;
6914	}
6915	return NOTIFY_OK;
6916}
6917
6918static int cpuset_cpu_inactive(struct notifier_block *nfb, unsigned long action,
6919			       void *hcpu)
6920{
6921	switch (action) {
6922	case CPU_DOWN_PREPARE:
6923		cpuset_update_active_cpus(false);
6924		break;
6925	case CPU_DOWN_PREPARE_FROZEN:
6926		num_cpus_frozen++;
6927		partition_sched_domains(1, NULL, NULL);
6928		break;
6929	default:
6930		return NOTIFY_DONE;
6931	}
6932	return NOTIFY_OK;
6933}
6934
6935void __init sched_init_smp(void)
6936{
6937	cpumask_var_t non_isolated_cpus;
6938
6939	alloc_cpumask_var(&non_isolated_cpus, GFP_KERNEL);
6940	alloc_cpumask_var(&fallback_doms, GFP_KERNEL);
6941
6942	sched_init_numa();
6943
6944	/*
6945	 * There's no userspace yet to cause hotplug operations; hence all the
6946	 * cpu masks are stable and all blatant races in the below code cannot
6947	 * happen.
6948	 */
6949	mutex_lock(&sched_domains_mutex);
6950	init_sched_domains(cpu_active_mask);
6951	cpumask_andnot(non_isolated_cpus, cpu_possible_mask, cpu_isolated_map);
6952	if (cpumask_empty(non_isolated_cpus))
6953		cpumask_set_cpu(smp_processor_id(), non_isolated_cpus);
6954	mutex_unlock(&sched_domains_mutex);
6955
6956	hotcpu_notifier(sched_domains_numa_masks_update, CPU_PRI_SCHED_ACTIVE);
6957	hotcpu_notifier(cpuset_cpu_active, CPU_PRI_CPUSET_ACTIVE);
6958	hotcpu_notifier(cpuset_cpu_inactive, CPU_PRI_CPUSET_INACTIVE);
6959
6960	init_hrtick();
6961
6962	/* Move init over to a non-isolated CPU */
6963	if (set_cpus_allowed_ptr(current, non_isolated_cpus) < 0)
6964		BUG();
6965	sched_init_granularity();
6966	free_cpumask_var(non_isolated_cpus);
6967
6968	init_sched_rt_class();
6969	init_sched_dl_class();
6970}
6971#else
6972void __init sched_init_smp(void)
6973{
6974	sched_init_granularity();
6975}
6976#endif /* CONFIG_SMP */
6977
6978const_debug unsigned int sysctl_timer_migration = 1;
6979
6980int in_sched_functions(unsigned long addr)
6981{
6982	return in_lock_functions(addr) ||
6983		(addr >= (unsigned long)__sched_text_start
6984		&& addr < (unsigned long)__sched_text_end);
6985}
6986
6987#ifdef CONFIG_CGROUP_SCHED
6988/*
6989 * Default task group.
6990 * Every task in system belongs to this group at bootup.
6991 */
6992struct task_group root_task_group;
6993LIST_HEAD(task_groups);
6994#endif
6995
6996DECLARE_PER_CPU(cpumask_var_t, load_balance_mask);
6997
6998void __init sched_init(void)
6999{
7000	int i, j;
7001	unsigned long alloc_size = 0, ptr;
7002
7003#ifdef CONFIG_FAIR_GROUP_SCHED
7004	alloc_size += 2 * nr_cpu_ids * sizeof(void **);
7005#endif
7006#ifdef CONFIG_RT_GROUP_SCHED
7007	alloc_size += 2 * nr_cpu_ids * sizeof(void **);
7008#endif
7009#ifdef CONFIG_CPUMASK_OFFSTACK
7010	alloc_size += num_possible_cpus() * cpumask_size();
7011#endif
7012	if (alloc_size) {
7013		ptr = (unsigned long)kzalloc(alloc_size, GFP_NOWAIT);
7014
7015#ifdef CONFIG_FAIR_GROUP_SCHED
7016		root_task_group.se = (struct sched_entity **)ptr;
7017		ptr += nr_cpu_ids * sizeof(void **);
7018
7019		root_task_group.cfs_rq = (struct cfs_rq **)ptr;
7020		ptr += nr_cpu_ids * sizeof(void **);
7021
7022#endif /* CONFIG_FAIR_GROUP_SCHED */
7023#ifdef CONFIG_RT_GROUP_SCHED
7024		root_task_group.rt_se = (struct sched_rt_entity **)ptr;
7025		ptr += nr_cpu_ids * sizeof(void **);
7026
7027		root_task_group.rt_rq = (struct rt_rq **)ptr;
7028		ptr += nr_cpu_ids * sizeof(void **);
7029
7030#endif /* CONFIG_RT_GROUP_SCHED */
7031#<