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