Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/kernel/sched/core.c

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