Merge tag 'v3.17' into p/abusse/merge_upgrade
[projects/modsched/linux.git] / kernel / sched / cfs / core.c
1 /*
2  *  kernel/sched/core.c
3  *
4  *  Kernel scheduler and related syscalls
5  *
6  *  Copyright (C) 1991-2002  Linus Torvalds
7  *
8  *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and
9  *              make semaphores SMP safe
10  *  1998-11-19  Implemented schedule_timeout() and related stuff
11  *              by Andrea Arcangeli
12  *  2002-01-04  New ultra-scalable O(1) scheduler by Ingo Molnar:
13  *              hybrid priority-list and round-robin design with
14  *              an array-switch method of distributing timeslices
15  *              and per-CPU runqueues.  Cleanups and useful suggestions
16  *              by Davide Libenzi, preemptible kernel bits by Robert Love.
17  *  2003-09-03  Interactivity tuning by Con Kolivas.
18  *  2004-04-02  Scheduler domains code by Nick Piggin
19  *  2007-04-15  Work begun on replacing all interactivity tuning with a
20  *              fair scheduling design by Con Kolivas.
21  *  2007-05-05  Load balancing (smp-nice) and other improvements
22  *              by Peter Williams
23  *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith
24  *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
25  *  2007-11-29  RT balancing improvements by Steven Rostedt, Gregory Haskins,
26  *              Thomas Gleixner, Mike Kravetz
27  */
28
29 #include <linux/mm.h>
30 #include <linux/module.h>
31 #include <linux/nmi.h>
32 #include <linux/init.h>
33 #include <linux/uaccess.h>
34 #include <linux/highmem.h>
35 #include <asm/mmu_context.h>
36 #include <linux/interrupt.h>
37 #include <linux/capability.h>
38 #include <linux/completion.h>
39 #include <linux/kernel_stat.h>
40 #include <linux/debug_locks.h>
41 #include <linux/perf_event.h>
42 #include <linux/security.h>
43 #include <linux/notifier.h>
44 #include <linux/profile.h>
45 #include <linux/freezer.h>
46 #include <linux/vmalloc.h>
47 #include <linux/blkdev.h>
48 #include <linux/delay.h>
49 #include <linux/pid_namespace.h>
50 #include <linux/smp.h>
51 #include <linux/threads.h>
52 #include <linux/timer.h>
53 #include <linux/rcupdate.h>
54 #include <linux/cpu.h>
55 #include <linux/cpuset.h>
56 #include <linux/percpu.h>
57 #include <linux/proc_fs.h>
58 #include <linux/seq_file.h>
59 #include <linux/sysctl.h>
60 #include <linux/syscalls.h>
61 #include <linux/times.h>
62 #include <linux/tsacct_kern.h>
63 #include <linux/kprobes.h>
64 #include <linux/delayacct.h>
65 #include <linux/unistd.h>
66 #include <linux/pagemap.h>
67 #include <linux/hrtimer.h>
68 #include <linux/tick.h>
69 #include <linux/debugfs.h>
70 #include <linux/ctype.h>
71 #include <linux/ftrace.h>
72 #include <linux/slab.h>
73 #include <linux/init_task.h>
74 #include <linux/binfmts.h>
75 #include <linux/context_tracking.h>
76 #include <linux/compiler.h>
77
78 #include <asm/switch_to.h>
79 #include <asm/tlb.h>
80 #include <asm/irq_regs.h>
81 #include <asm/mutex.h>
82 #ifdef CONFIG_PARAVIRT
83 #include <asm/paravirt.h>
84 #endif
85
86 #include "sched.h"
87 #include "../workqueue_internal.h"
88 #include "../smpboot.h"
89
90 #define CREATE_TRACE_POINTS
91 #include <trace/events/sched.h>
92
93 #ifdef smp_mb__before_atomic
94 void __smp_mb__before_atomic(void)
95 {
96         smp_mb__before_atomic();
97 }
98 EXPORT_SYMBOL(__smp_mb__before_atomic);
99 #endif
100
101 #ifdef smp_mb__after_atomic
102 void __smp_mb__after_atomic(void)
103 {
104         smp_mb__after_atomic();
105 }
106 EXPORT_SYMBOL(__smp_mb__after_atomic);
107 #endif
108
109 void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
110 {
111         unsigned long delta;
112         ktime_t soft, hard, now;
113
114         for (;;) {
115                 if (hrtimer_active(period_timer))
116                         break;
117
118                 now = hrtimer_cb_get_time(period_timer);
119                 hrtimer_forward(period_timer, now, period);
120
121                 soft = hrtimer_get_softexpires(period_timer);
122                 hard = hrtimer_get_expires(period_timer);
123                 delta = ktime_to_ns(ktime_sub(hard, soft));
124                 __hrtimer_start_range_ns(period_timer, soft, delta,
125                                          HRTIMER_MODE_ABS_PINNED, 0);
126         }
127 }
128
129 DEFINE_MUTEX(sched_domains_mutex);
130 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
131
132 static void update_rq_clock_task(struct rq *rq, s64 delta);
133
134 void update_rq_clock(struct rq *rq)
135 {
136         s64 delta;
137
138         if (rq->skip_clock_update > 0)
139                 return;
140
141         delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
142         if (delta < 0)
143                 return;
144         rq->clock += delta;
145         update_rq_clock_task(rq, delta);
146 }
147
148 /*
149  * Debugging: various feature bits
150  */
151
152 #define SCHED_FEAT(name, enabled)       \
153         (1UL << __SCHED_FEAT_##name) * enabled |
154
155 const_debug unsigned int sysctl_sched_features =
156 #include "features.h"
157         0;
158
159 #undef SCHED_FEAT
160
161 #ifdef CONFIG_SCHED_DEBUG
162 #define SCHED_FEAT(name, enabled)       \
163         #name ,
164
165 static const char * const sched_feat_names[] = {
166 #include "features.h"
167 };
168
169 #undef SCHED_FEAT
170
171 static int sched_feat_show(struct seq_file *m, void *v)
172 {
173         int i;
174
175         for (i = 0; i < __SCHED_FEAT_NR; i++) {
176                 if (!(sysctl_sched_features & (1UL << i)))
177                         seq_puts(m, "NO_");
178                 seq_printf(m, "%s ", sched_feat_names[i]);
179         }
180         seq_puts(m, "\n");
181
182         return 0;
183 }
184
185 #ifdef HAVE_JUMP_LABEL
186
187 #define jump_label_key__true  STATIC_KEY_INIT_TRUE
188 #define jump_label_key__false STATIC_KEY_INIT_FALSE
189
190 #define SCHED_FEAT(name, enabled)       \
191         jump_label_key__##enabled ,
192
193 struct static_key sched_feat_keys[__SCHED_FEAT_NR] = {
194 #include "features.h"
195 };
196
197 #undef SCHED_FEAT
198
199 static void sched_feat_disable(int i)
200 {
201         if (static_key_enabled(&sched_feat_keys[i]))
202                 static_key_slow_dec(&sched_feat_keys[i]);
203 }
204
205 static void sched_feat_enable(int i)
206 {
207         if (!static_key_enabled(&sched_feat_keys[i]))
208                 static_key_slow_inc(&sched_feat_keys[i]);
209 }
210 #else
211 static void sched_feat_disable(int i) { };
212 static void sched_feat_enable(int i) { };
213 #endif /* HAVE_JUMP_LABEL */
214
215 static int sched_feat_set(char *cmp)
216 {
217         int i;
218         int neg = 0;
219
220         if (strncmp(cmp, "NO_", 3) == 0) {
221                 neg = 1;
222                 cmp += 3;
223         }
224
225         for (i = 0; i < __SCHED_FEAT_NR; i++) {
226                 if (strcmp(cmp, sched_feat_names[i]) == 0) {
227                         if (neg) {
228                                 sysctl_sched_features &= ~(1UL << i);
229                                 sched_feat_disable(i);
230                         } else {
231                                 sysctl_sched_features |= (1UL << i);
232                                 sched_feat_enable(i);
233                         }
234                         break;
235                 }
236         }
237
238         return i;
239 }
240
241 static ssize_t
242 sched_feat_write(struct file *filp, const char __user *ubuf,
243                 size_t cnt, loff_t *ppos)
244 {
245         char buf[64];
246         char *cmp;
247         int i;
248         struct inode *inode;
249
250         if (cnt > 63)
251                 cnt = 63;
252
253         if (copy_from_user(&buf, ubuf, cnt))
254                 return -EFAULT;
255
256         buf[cnt] = 0;
257         cmp = strstrip(buf);
258
259         /* Ensure the static_key remains in a consistent state */
260         inode = file_inode(filp);
261         mutex_lock(&inode->i_mutex);
262         i = sched_feat_set(cmp);
263         mutex_unlock(&inode->i_mutex);
264         if (i == __SCHED_FEAT_NR)
265                 return -EINVAL;
266
267         *ppos += cnt;
268
269         return cnt;
270 }
271
272 static int sched_feat_open(struct inode *inode, struct file *filp)
273 {
274         return single_open(filp, sched_feat_show, NULL);
275 }
276
277 static const struct file_operations sched_feat_fops = {
278         .open           = sched_feat_open,
279         .write          = sched_feat_write,
280         .read           = seq_read,
281         .llseek         = seq_lseek,
282         .release        = single_release,
283 };
284
285 static __init int sched_init_debug(void)
286 {
287         debugfs_create_file("sched_features", 0644, NULL, NULL,
288                         &sched_feat_fops);
289
290         return 0;
291 }
292 late_initcall(sched_init_debug);
293 #endif /* CONFIG_SCHED_DEBUG */
294
295 /*
296  * Number of tasks to iterate in a single balance run.
297  * Limited because this is done with IRQs disabled.
298  */
299 const_debug unsigned int sysctl_sched_nr_migrate = 32;
300
301 /*
302  * period over which we average the RT time consumption, measured
303  * in ms.
304  *
305  * default: 1s
306  */
307 const_debug unsigned int sysctl_sched_time_avg = MSEC_PER_SEC;
308
309 /*
310  * period over which we measure -rt task cpu usage in us.
311  * default: 1s
312  */
313 unsigned int sysctl_sched_rt_period = 1000000;
314
315 __read_mostly int scheduler_running;
316
317 /*
318  * part of the period that we allow rt tasks to run in us.
319  * default: 0.95s
320  */
321 int sysctl_sched_rt_runtime = 950000;
322
323 /*
324  * __task_rq_lock - lock the rq @p resides on.
325  */
326 static inline struct rq *__task_rq_lock(struct task_struct *p)
327         __acquires(rq->lock)
328 {
329         struct rq *rq;
330
331         lockdep_assert_held(&p->pi_lock);
332
333         for (;;) {
334                 rq = task_rq(p);
335                 raw_spin_lock(&rq->lock);
336                 if (likely(rq == task_rq(p)))
337                         return rq;
338                 raw_spin_unlock(&rq->lock);
339         }
340 }
341
342 /*
343  * task_rq_lock - lock p->pi_lock and lock the rq @p resides on.
344  */
345 static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
346         __acquires(p->pi_lock)
347         __acquires(rq->lock)
348 {
349         struct rq *rq;
350
351         for (;;) {
352                 raw_spin_lock_irqsave(&p->pi_lock, *flags);
353                 rq = task_rq(p);
354                 raw_spin_lock(&rq->lock);
355                 if (likely(rq == task_rq(p)))
356                         return rq;
357                 raw_spin_unlock(&rq->lock);
358                 raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
359         }
360 }
361
362 static void __task_rq_unlock(struct rq *rq)
363         __releases(rq->lock)
364 {
365         raw_spin_unlock(&rq->lock);
366 }
367
368 static inline void
369 task_rq_unlock(struct rq *rq, struct task_struct *p, unsigned long *flags)
370         __releases(rq->lock)
371         __releases(p->pi_lock)
372 {
373         raw_spin_unlock(&rq->lock);
374         raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
375 }
376
377 /*
378  * this_rq_lock - lock this runqueue and disable interrupts.
379  */
380 static struct rq *this_rq_lock(void)
381         __acquires(rq->lock)
382 {
383         struct rq *rq;
384
385         local_irq_disable();
386         rq = this_rq();
387         raw_spin_lock(&rq->lock);
388
389         return rq;
390 }
391
392 #ifdef CONFIG_SCHED_HRTICK
393 /*
394  * Use HR-timers to deliver accurate preemption points.
395  */
396
397 static void hrtick_clear(struct rq *rq)
398 {
399         if (hrtimer_active(&rq->hrtick_timer))
400                 hrtimer_cancel(&rq->hrtick_timer);
401 }
402
403 /*
404  * High-resolution timer tick.
405  * Runs from hardirq context with interrupts disabled.
406  */
407 static enum hrtimer_restart hrtick(struct hrtimer *timer)
408 {
409         struct rq *rq = container_of(timer, struct rq, hrtick_timer);
410
411         WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());
412
413         raw_spin_lock(&rq->lock);
414         update_rq_clock(rq);
415         rq->curr->sched_class->task_tick(rq, rq->curr, 1);
416         raw_spin_unlock(&rq->lock);
417
418         return HRTIMER_NORESTART;
419 }
420
421 #ifdef CONFIG_SMP
422
423 static int __hrtick_restart(struct rq *rq)
424 {
425         struct hrtimer *timer = &rq->hrtick_timer;
426         ktime_t time = hrtimer_get_softexpires(timer);
427
428         return __hrtimer_start_range_ns(timer, time, 0, HRTIMER_MODE_ABS_PINNED, 0);
429 }
430
431 /*
432  * called from hardirq (IPI) context
433  */
434 static void __hrtick_start(void *arg)
435 {
436         struct rq *rq = arg;
437
438         raw_spin_lock(&rq->lock);
439         __hrtick_restart(rq);
440         rq->hrtick_csd_pending = 0;
441         raw_spin_unlock(&rq->lock);
442 }
443
444 /*
445  * Called to set the hrtick timer state.
446  *
447  * called with rq->lock held and irqs disabled
448  */
449 void hrtick_start(struct rq *rq, u64 delay)
450 {
451         struct hrtimer *timer = &rq->hrtick_timer;
452         ktime_t time = ktime_add_ns(timer->base->get_time(), delay);
453
454         hrtimer_set_expires(timer, time);
455
456         if (rq == this_rq()) {
457                 __hrtick_restart(rq);
458         } else if (!rq->hrtick_csd_pending) {
459                 smp_call_function_single_async(cpu_of(rq), &rq->hrtick_csd);
460                 rq->hrtick_csd_pending = 1;
461         }
462 }
463
464 static int
465 hotplug_hrtick(struct notifier_block *nfb, unsigned long action, void *hcpu)
466 {
467         int cpu = (int)(long)hcpu;
468
469         switch (action) {
470         case CPU_UP_CANCELED:
471         case CPU_UP_CANCELED_FROZEN:
472         case CPU_DOWN_PREPARE:
473         case CPU_DOWN_PREPARE_FROZEN:
474         case CPU_DEAD:
475         case CPU_DEAD_FROZEN:
476                 hrtick_clear(cpu_rq(cpu));
477                 return NOTIFY_OK;
478         }
479
480         return NOTIFY_DONE;
481 }
482
483 static __init void init_hrtick(void)
484 {
485         hotcpu_notifier(hotplug_hrtick, 0);
486 }
487 #else
488 /*
489  * Called to set the hrtick timer state.
490  *
491  * called with rq->lock held and irqs disabled
492  */
493 void hrtick_start(struct rq *rq, u64 delay)
494 {
495         __hrtimer_start_range_ns(&rq->hrtick_timer, ns_to_ktime(delay), 0,
496                         HRTIMER_MODE_REL_PINNED, 0);
497 }
498
499 static inline void init_hrtick(void)
500 {
501 }
502 #endif /* CONFIG_SMP */
503
504 static void init_rq_hrtick(struct rq *rq)
505 {
506 #ifdef CONFIG_SMP
507         rq->hrtick_csd_pending = 0;
508
509         rq->hrtick_csd.flags = 0;
510         rq->hrtick_csd.func = __hrtick_start;
511         rq->hrtick_csd.info = rq;
512 #endif
513
514         hrtimer_init(&rq->hrtick_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
515         rq->hrtick_timer.function = hrtick;
516 }
517 #else   /* CONFIG_SCHED_HRTICK */
518 static inline void hrtick_clear(struct rq *rq)
519 {
520 }
521
522 static inline void init_rq_hrtick(struct rq *rq)
523 {
524 }
525
526 static inline void init_hrtick(void)
527 {
528 }
529 #endif  /* CONFIG_SCHED_HRTICK */
530
531 /*
532  * cmpxchg based fetch_or, macro so it works for different integer types
533  */
534 #define fetch_or(ptr, val)                                              \
535 ({      typeof(*(ptr)) __old, __val = *(ptr);                           \
536         for (;;) {                                                      \
537                 __old = cmpxchg((ptr), __val, __val | (val));           \
538                 if (__old == __val)                                     \
539                         break;                                          \
540                 __val = __old;                                          \
541         }                                                               \
542         __old;                                                          \
543 })
544
545 #if defined(CONFIG_SMP) && defined(TIF_POLLING_NRFLAG)
546 /*
547  * Atomically set TIF_NEED_RESCHED and test for TIF_POLLING_NRFLAG,
548  * this avoids any races wrt polling state changes and thereby avoids
549  * spurious IPIs.
550  */
551 static bool set_nr_and_not_polling(struct task_struct *p)
552 {
553         struct thread_info *ti = task_thread_info(p);
554         return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
555 }
556
557 /*
558  * Atomically set TIF_NEED_RESCHED if TIF_POLLING_NRFLAG is set.
559  *
560  * If this returns true, then the idle task promises to call
561  * sched_ttwu_pending() and reschedule soon.
562  */
563 static bool set_nr_if_polling(struct task_struct *p)
564 {
565         struct thread_info *ti = task_thread_info(p);
566         typeof(ti->flags) old, val = ACCESS_ONCE(ti->flags);
567
568         for (;;) {
569                 if (!(val & _TIF_POLLING_NRFLAG))
570                         return false;
571                 if (val & _TIF_NEED_RESCHED)
572                         return true;
573                 old = cmpxchg(&ti->flags, val, val | _TIF_NEED_RESCHED);
574                 if (old == val)
575                         break;
576                 val = old;
577         }
578         return true;
579 }
580
581 #else
582 static bool set_nr_and_not_polling(struct task_struct *p)
583 {
584         set_tsk_need_resched(p);
585         return true;
586 }
587
588 #ifdef CONFIG_SMP
589 static bool set_nr_if_polling(struct task_struct *p)
590 {
591         return false;
592 }
593 #endif
594 #endif
595
596 /*
597  * resched_curr - mark rq's current task 'to be rescheduled now'.
598  *
599  * On UP this means the setting of the need_resched flag, on SMP it
600  * might also involve a cross-CPU call to trigger the scheduler on
601  * the target CPU.
602  */
603 void resched_curr(struct rq *rq)
604 {
605         struct task_struct *curr = rq->curr;
606         int cpu;
607
608         lockdep_assert_held(&rq->lock);
609
610         if (test_tsk_need_resched(curr))
611                 return;
612
613         cpu = cpu_of(rq);
614
615         if (cpu == smp_processor_id()) {
616                 set_tsk_need_resched(curr);
617                 set_preempt_need_resched();
618                 return;
619         }
620
621         if (set_nr_and_not_polling(curr))
622                 smp_send_reschedule(cpu);
623         else
624                 trace_sched_wake_idle_without_ipi(cpu);
625 }
626
627 void resched_cpu(int cpu)
628 {
629         struct rq *rq = cpu_rq(cpu);
630         unsigned long flags;
631
632         if (!raw_spin_trylock_irqsave(&rq->lock, flags))
633                 return;
634         resched_curr(rq);
635         raw_spin_unlock_irqrestore(&rq->lock, flags);
636 }
637
638 #ifdef CONFIG_SMP
639 #ifdef CONFIG_NO_HZ_COMMON
640 /*
641  * In the semi idle case, use the nearest busy cpu for migrating timers
642  * from an idle cpu.  This is good for power-savings.
643  *
644  * We don't do similar optimization for completely idle system, as
645  * selecting an idle cpu will add more delays to the timers than intended
646  * (as that cpu's timer base may not be uptodate wrt jiffies etc).
647  */
648 int get_nohz_timer_target(int pinned)
649 {
650         int cpu = smp_processor_id();
651         int i;
652         struct sched_domain *sd;
653
654         if (pinned || !get_sysctl_timer_migration() || !idle_cpu(cpu))
655                 return cpu;
656
657         rcu_read_lock();
658         for_each_domain(cpu, sd) {
659                 for_each_cpu(i, sched_domain_span(sd)) {
660                         if (!idle_cpu(i)) {
661                                 cpu = i;
662                                 goto unlock;
663                         }
664                 }
665         }
666 unlock:
667         rcu_read_unlock();
668         return cpu;
669 }
670 /*
671  * When add_timer_on() enqueues a timer into the timer wheel of an
672  * idle CPU then this timer might expire before the next timer event
673  * which is scheduled to wake up that CPU. In case of a completely
674  * idle system the next event might even be infinite time into the
675  * future. wake_up_idle_cpu() ensures that the CPU is woken up and
676  * leaves the inner idle loop so the newly added timer is taken into
677  * account when the CPU goes back to idle and evaluates the timer
678  * wheel for the next timer event.
679  */
680 static void wake_up_idle_cpu(int cpu)
681 {
682         struct rq *rq = cpu_rq(cpu);
683
684         if (cpu == smp_processor_id())
685                 return;
686
687         if (set_nr_and_not_polling(rq->idle))
688                 smp_send_reschedule(cpu);
689         else
690                 trace_sched_wake_idle_without_ipi(cpu);
691 }
692
693 static bool wake_up_full_nohz_cpu(int cpu)
694 {
695         /*
696          * We just need the target to call irq_exit() and re-evaluate
697          * the next tick. The nohz full kick at least implies that.
698          * If needed we can still optimize that later with an
699          * empty IRQ.
700          */
701         if (tick_nohz_full_cpu(cpu)) {
702                 if (cpu != smp_processor_id() ||
703                     tick_nohz_tick_stopped())
704                         tick_nohz_full_kick_cpu(cpu);
705                 return true;
706         }
707
708         return false;
709 }
710
711 void wake_up_nohz_cpu(int cpu)
712 {
713         if (!wake_up_full_nohz_cpu(cpu))
714                 wake_up_idle_cpu(cpu);
715 }
716
717 static inline bool got_nohz_idle_kick(void)
718 {
719         int cpu = smp_processor_id();
720
721         if (!test_bit(NOHZ_BALANCE_KICK, nohz_flags(cpu)))
722                 return false;
723
724         if (idle_cpu(cpu) && !need_resched())
725                 return true;
726
727         /*
728          * We can't run Idle Load Balance on this CPU for this time so we
729          * cancel it and clear NOHZ_BALANCE_KICK
730          */
731         clear_bit(NOHZ_BALANCE_KICK, nohz_flags(cpu));
732         return false;
733 }
734
735 #else /* CONFIG_NO_HZ_COMMON */
736
737 static inline bool got_nohz_idle_kick(void)
738 {
739         return false;
740 }
741
742 #endif /* CONFIG_NO_HZ_COMMON */
743
744 #ifdef CONFIG_NO_HZ_FULL
745 bool sched_can_stop_tick(void)
746 {
747         /*
748          * More than one running task need preemption.
749          * nr_running update is assumed to be visible
750          * after IPI is sent from wakers.
751          */
752         if (this_rq()->nr_running > 1)
753                 return false;
754
755         return true;
756 }
757 #endif /* CONFIG_NO_HZ_FULL */
758
759 void sched_avg_update(struct rq *rq)
760 {
761         s64 period = sched_avg_period();
762
763         while ((s64)(rq_clock(rq) - rq->age_stamp) > period) {
764                 /*
765                  * Inline assembly required to prevent the compiler
766                  * optimising this loop into a divmod call.
767                  * See __iter_div_u64_rem() for another example of this.
768                  */
769                 asm("" : "+rm" (rq->age_stamp));
770                 rq->age_stamp += period;
771                 rq->rt_avg /= 2;
772         }
773 }
774
775 #endif /* CONFIG_SMP */
776
777 #if defined(CONFIG_RT_GROUP_SCHED) || (defined(CONFIG_FAIR_GROUP_SCHED) && \
778                         (defined(CONFIG_SMP) || defined(CONFIG_CFS_BANDWIDTH)))
779 /*
780  * Iterate task_group tree rooted at *from, calling @down when first entering a
781  * node and @up when leaving it for the final time.
782  *
783  * Caller must hold rcu_lock or sufficient equivalent.
784  */
785 int walk_tg_tree_from(struct task_group *from,
786                              tg_visitor down, tg_visitor up, void *data)
787 {
788         struct task_group *parent, *child;
789         int ret;
790
791         parent = from;
792
793 down:
794         ret = (*down)(parent, data);
795         if (ret)
796                 goto out;
797         list_for_each_entry_rcu(child, &parent->children, siblings) {
798                 parent = child;
799                 goto down;
800
801 up:
802                 continue;
803         }
804         ret = (*up)(parent, data);
805         if (ret || parent == from)
806                 goto out;
807
808         child = parent;
809         parent = parent->parent;
810         if (parent)
811                 goto up;
812 out:
813         return ret;
814 }
815
816 int tg_nop(struct task_group *tg, void *data)
817 {
818         return 0;
819 }
820 #endif
821
822 static void set_load_weight(struct task_struct *p)
823 {
824         int prio = p->static_prio - MAX_RT_PRIO;
825         struct load_weight *load = &p->se.load;
826
827         /*
828          * SCHED_IDLE tasks get minimal weight:
829          */
830         if (p->policy == SCHED_IDLE) {
831                 load->weight = scale_load(WEIGHT_IDLEPRIO);
832                 load->inv_weight = WMULT_IDLEPRIO;
833                 return;
834         }
835
836         load->weight = scale_load(prio_to_weight[prio]);
837         load->inv_weight = prio_to_wmult[prio];
838 }
839
840 static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
841 {
842         update_rq_clock(rq);
843         sched_info_queued(rq, p);
844         p->sched_class->enqueue_task(rq, p, flags);
845 }
846
847 static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
848 {
849         update_rq_clock(rq);
850         sched_info_dequeued(rq, p);
851         p->sched_class->dequeue_task(rq, p, flags);
852 }
853
854 void activate_task(struct rq *rq, struct task_struct *p, int flags)
855 {
856         if (task_contributes_to_load(p))
857                 rq->nr_uninterruptible--;
858
859         enqueue_task(rq, p, flags);
860 }
861
862 void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
863 {
864         if (task_contributes_to_load(p))
865                 rq->nr_uninterruptible++;
866
867         dequeue_task(rq, p, flags);
868 }
869
870 static void update_rq_clock_task(struct rq *rq, s64 delta)
871 {
872 /*
873  * In theory, the compile should just see 0 here, and optimize out the call
874  * to sched_rt_avg_update. But I don't trust it...
875  */
876 #if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
877         s64 steal = 0, irq_delta = 0;
878 #endif
879 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
880         irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;
881
882         /*
883          * Since irq_time is only updated on {soft,}irq_exit, we might run into
884          * this case when a previous update_rq_clock() happened inside a
885          * {soft,}irq region.
886          *
887          * When this happens, we stop ->clock_task and only update the
888          * prev_irq_time stamp to account for the part that fit, so that a next
889          * update will consume the rest. This ensures ->clock_task is
890          * monotonic.
891          *
892          * It does however cause some slight miss-attribution of {soft,}irq
893          * time, a more accurate solution would be to update the irq_time using
894          * the current rq->clock timestamp, except that would require using
895          * atomic ops.
896          */
897         if (irq_delta > delta)
898                 irq_delta = delta;
899
900         rq->prev_irq_time += irq_delta;
901         delta -= irq_delta;
902 #endif
903 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
904         if (static_key_false((&paravirt_steal_rq_enabled))) {
905                 steal = paravirt_steal_clock(cpu_of(rq));
906                 steal -= rq->prev_steal_time_rq;
907
908                 if (unlikely(steal > delta))
909                         steal = delta;
910
911                 rq->prev_steal_time_rq += steal;
912                 delta -= steal;
913         }
914 #endif
915
916         rq->clock_task += delta;
917
918 #if defined(CONFIG_IRQ_TIME_ACCOUNTING) || defined(CONFIG_PARAVIRT_TIME_ACCOUNTING)
919         if ((irq_delta + steal) && sched_feat(NONTASK_CAPACITY))
920                 sched_rt_avg_update(rq, irq_delta + steal);
921 #endif
922 }
923
924 void sched_set_stop_task(int cpu, struct task_struct *stop)
925 {
926         struct sched_param param = { .sched_priority = MAX_RT_PRIO - 1 };
927         struct task_struct *old_stop = cpu_rq(cpu)->stop;
928
929         if (stop) {
930                 /*
931                  * Make it appear like a SCHED_FIFO task, its something
932                  * userspace knows about and won't get confused about.
933                  *
934                  * Also, it will make PI more or less work without too
935                  * much confusion -- but then, stop work should not
936                  * rely on PI working anyway.
937                  */
938                 sched_setscheduler_nocheck(stop, SCHED_FIFO, &param);
939
940                 stop->sched_class = &stop_sched_class;
941         }
942
943         cpu_rq(cpu)->stop = stop;
944
945         if (old_stop) {
946                 /*
947                  * Reset it back to a normal scheduling class so that
948                  * it can die in pieces.
949                  */
950                 old_stop->sched_class = &rt_sched_class;
951         }
952 }
953
954 /*
955  * __normal_prio - return the priority that is based on the static prio
956  */
957 static inline int __normal_prio(struct task_struct *p)
958 {
959         return p->static_prio;
960 }
961
962 /*
963  * Calculate the expected normal priority: i.e. priority
964  * without taking RT-inheritance into account. Might be
965  * boosted by interactivity modifiers. Changes upon fork,
966  * setprio syscalls, and whenever the interactivity
967  * estimator recalculates.
968  */
969 static inline int normal_prio(struct task_struct *p)
970 {
971         int prio;
972
973         if (task_has_dl_policy(p))
974                 prio = MAX_DL_PRIO-1;
975         else if (task_has_rt_policy(p))
976                 prio = MAX_RT_PRIO-1 - p->rt_priority;
977         else
978                 prio = __normal_prio(p);
979         return prio;
980 }
981
982 /*
983  * Calculate the current priority, i.e. the priority
984  * taken into account by the scheduler. This value might
985  * be boosted by RT tasks, or might be boosted by
986  * interactivity modifiers. Will be RT if the task got
987  * RT-boosted. If not then it returns p->normal_prio.
988  */
989 static int effective_prio(struct task_struct *p)
990 {
991         p->normal_prio = normal_prio(p);
992         /*
993          * If we are RT tasks or we were boosted to RT priority,
994          * keep the priority unchanged. Otherwise, update priority
995          * to the normal priority:
996          */
997         if (!rt_prio(p->prio))
998                 return p->normal_prio;
999         return p->prio;
1000 }
1001
1002 /**
1003  * task_curr - is this task currently executing on a CPU?
1004  * @p: the task in question.
1005  *
1006  * Return: 1 if the task is currently executing. 0 otherwise.
1007  */
1008 inline int task_curr(const struct task_struct *p)
1009 {
1010         return cpu_curr(task_cpu(p)) == p;
1011 }
1012
1013 static inline void check_class_changed(struct rq *rq, struct task_struct *p,
1014                                        const struct sched_class *prev_class,
1015                                        int oldprio)
1016 {
1017         if (prev_class != p->sched_class) {
1018                 if (prev_class->switched_from)
1019                         prev_class->switched_from(rq, p);
1020                 p->sched_class->switched_to(rq, p);
1021         } else if (oldprio != p->prio || dl_task(p))
1022                 p->sched_class->prio_changed(rq, p, oldprio);
1023 }
1024
1025 void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
1026 {
1027         const struct sched_class *class;
1028
1029         if (p->sched_class == rq->curr->sched_class) {
1030                 rq->curr->sched_class->check_preempt_curr(rq, p, flags);
1031         } else {
1032                 for_each_class(class) {
1033                         if (class == rq->curr->sched_class)
1034                                 break;
1035                         if (class == p->sched_class) {
1036                                 resched_curr(rq);
1037                                 break;
1038                         }
1039                 }
1040         }
1041
1042         /*
1043          * A queue event has occurred, and we're going to schedule.  In
1044          * this case, we can save a useless back to back clock update.
1045          */
1046         if (rq->curr->on_rq && test_tsk_need_resched(rq->curr))
1047                 rq->skip_clock_update = 1;
1048 }
1049
1050 #ifdef CONFIG_SMP
1051 void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
1052 {
1053 #ifdef CONFIG_SCHED_DEBUG
1054         /*
1055          * We should never call set_task_cpu() on a blocked task,
1056          * ttwu() will sort out the placement.
1057          */
1058         WARN_ON_ONCE(p->state != TASK_RUNNING && p->state != TASK_WAKING &&
1059                         !(task_preempt_count(p) & PREEMPT_ACTIVE));
1060
1061 #ifdef CONFIG_LOCKDEP
1062         /*
1063          * The caller should hold either p->pi_lock or rq->lock, when changing
1064          * a task's CPU. ->pi_lock for waking tasks, rq->lock for runnable tasks.
1065          *
1066          * sched_move_task() holds both and thus holding either pins the cgroup,
1067          * see task_group().
1068          *
1069          * Furthermore, all task_rq users should acquire both locks, see
1070          * task_rq_lock().
1071          */
1072         WARN_ON_ONCE(debug_locks && !(lockdep_is_held(&p->pi_lock) ||
1073                                       lockdep_is_held(&task_rq(p)->lock)));
1074 #endif
1075 #endif
1076
1077         trace_sched_migrate_task(p, new_cpu);
1078
1079         if (task_cpu(p) != new_cpu) {
1080                 if (p->sched_class->migrate_task_rq)
1081                         p->sched_class->migrate_task_rq(p, new_cpu);
1082                 p->se.nr_migrations++;
1083                 perf_sw_event(PERF_COUNT_SW_CPU_MIGRATIONS, 1, NULL, 0);
1084         }
1085
1086         __set_task_cpu(p, new_cpu);
1087 }
1088
1089 static void __migrate_swap_task(struct task_struct *p, int cpu)
1090 {
1091         if (p->on_rq) {
1092                 struct rq *src_rq, *dst_rq;
1093
1094                 src_rq = task_rq(p);
1095                 dst_rq = cpu_rq(cpu);
1096
1097                 deactivate_task(src_rq, p, 0);
1098                 set_task_cpu(p, cpu);
1099                 activate_task(dst_rq, p, 0);
1100                 check_preempt_curr(dst_rq, p, 0);
1101         } else {
1102                 /*
1103                  * Task isn't running anymore; make it appear like we migrated
1104                  * it before it went to sleep. This means on wakeup we make the
1105                  * previous cpu our targer instead of where it really is.
1106                  */
1107                 p->wake_cpu = cpu;
1108         }
1109 }
1110
1111 struct migration_swap_arg {
1112         struct task_struct *src_task, *dst_task;
1113         int src_cpu, dst_cpu;
1114 };
1115
1116 static int migrate_swap_stop(void *data)
1117 {
1118         struct migration_swap_arg *arg = data;
1119         struct rq *src_rq, *dst_rq;
1120         int ret = -EAGAIN;
1121
1122         src_rq = cpu_rq(arg->src_cpu);
1123         dst_rq = cpu_rq(arg->dst_cpu);
1124
1125         double_raw_lock(&arg->src_task->pi_lock,
1126                         &arg->dst_task->pi_lock);
1127         double_rq_lock(src_rq, dst_rq);
1128         if (task_cpu(arg->dst_task) != arg->dst_cpu)
1129                 goto unlock;
1130
1131         if (task_cpu(arg->src_task) != arg->src_cpu)
1132                 goto unlock;
1133
1134         if (!cpumask_test_cpu(arg->dst_cpu, tsk_cpus_allowed(arg->src_task)))
1135                 goto unlock;
1136
1137         if (!cpumask_test_cpu(arg->src_cpu, tsk_cpus_allowed(arg->dst_task)))
1138                 goto unlock;
1139
1140         __migrate_swap_task(arg->src_task, arg->dst_cpu);
1141         __migrate_swap_task(arg->dst_task, arg->src_cpu);
1142
1143         ret = 0;
1144
1145 unlock:
1146         double_rq_unlock(src_rq, dst_rq);
1147         raw_spin_unlock(&arg->dst_task->pi_lock);
1148         raw_spin_unlock(&arg->src_task->pi_lock);
1149
1150         return ret;
1151 }
1152
1153 /*
1154  * Cross migrate two tasks
1155  */
1156 int migrate_swap(struct task_struct *cur, struct task_struct *p)
1157 {
1158         struct migration_swap_arg arg;
1159         int ret = -EINVAL;
1160
1161         arg = (struct migration_swap_arg){
1162                 .src_task = cur,
1163                 .src_cpu = task_cpu(cur),
1164                 .dst_task = p,
1165                 .dst_cpu = task_cpu(p),
1166         };
1167
1168         if (arg.src_cpu == arg.dst_cpu)
1169                 goto out;
1170
1171         /*
1172          * These three tests are all lockless; this is OK since all of them
1173          * will be re-checked with proper locks held further down the line.
1174          */
1175         if (!cpu_active(arg.src_cpu) || !cpu_active(arg.dst_cpu))
1176                 goto out;
1177
1178         if (!cpumask_test_cpu(arg.dst_cpu, tsk_cpus_allowed(arg.src_task)))
1179                 goto out;
1180
1181         if (!cpumask_test_cpu(arg.src_cpu, tsk_cpus_allowed(arg.dst_task)))
1182                 goto out;
1183
1184         trace_sched_swap_numa(cur, arg.src_cpu, p, arg.dst_cpu);
1185         ret = stop_two_cpus(arg.dst_cpu, arg.src_cpu, migrate_swap_stop, &arg);
1186
1187 out:
1188         return ret;
1189 }
1190
1191 struct migration_arg {
1192         struct task_struct *task;
1193         int dest_cpu;
1194 };
1195
1196 static int migration_cpu_stop(void *data);
1197
1198 /*
1199  * wait_task_inactive - wait for a thread to unschedule.
1200  *
1201  * If @match_state is nonzero, it's the @p->state value just checked and
1202  * not expected to change.  If it changes, i.e. @p might have woken up,
1203  * then return zero.  When we succeed in waiting for @p to be off its CPU,
1204  * we return a positive number (its total switch count).  If a second call
1205  * a short while later returns the same number, the caller can be sure that
1206  * @p has remained unscheduled the whole time.
1207  *
1208  * The caller must ensure that the task *will* unschedule sometime soon,
1209  * else this function might spin for a *long* time. This function can't
1210  * be called with interrupts off, or it may introduce deadlock with
1211  * smp_call_function() if an IPI is sent by the same process we are
1212  * waiting to become inactive.
1213  */
1214 unsigned long wait_task_inactive(struct task_struct *p, long match_state)
1215 {
1216         unsigned long flags;
1217         int running, on_rq;
1218         unsigned long ncsw;
1219         struct rq *rq;
1220
1221         for (;;) {
1222                 /*
1223                  * We do the initial early heuristics without holding
1224                  * any task-queue locks at all. We'll only try to get
1225                  * the runqueue lock when things look like they will
1226                  * work out!
1227                  */
1228                 rq = task_rq(p);
1229
1230                 /*
1231                  * If the task is actively running on another CPU
1232                  * still, just relax and busy-wait without holding
1233                  * any locks.
1234                  *
1235                  * NOTE! Since we don't hold any locks, it's not
1236                  * even sure that "rq" stays as the right runqueue!
1237                  * But we don't care, since "task_running()" will
1238                  * return false if the runqueue has changed and p
1239                  * is actually now running somewhere else!
1240                  */
1241                 while (task_running(rq, p)) {
1242                         if (match_state && unlikely(p->state != match_state))
1243                                 return 0;
1244                         cpu_relax();
1245                 }
1246
1247                 /*
1248                  * Ok, time to look more closely! We need the rq
1249                  * lock now, to be *sure*. If we're wrong, we'll
1250                  * just go back and repeat.
1251                  */
1252                 rq = task_rq_lock(p, &flags);
1253                 trace_sched_wait_task(p);
1254                 running = task_running(rq, p);
1255                 on_rq = p->on_rq;
1256                 ncsw = 0;
1257                 if (!match_state || p->state == match_state)
1258                         ncsw = p->nvcsw | LONG_MIN; /* sets MSB */
1259                 task_rq_unlock(rq, p, &flags);
1260
1261                 /*
1262                  * If it changed from the expected state, bail out now.
1263                  */
1264                 if (unlikely(!ncsw))
1265                         break;
1266
1267                 /*
1268                  * Was it really running after all now that we
1269                  * checked with the proper locks actually held?
1270                  *
1271                  * Oops. Go back and try again..
1272                  */
1273                 if (unlikely(running)) {
1274                         cpu_relax();
1275                         continue;
1276                 }
1277
1278                 /*
1279                  * It's not enough that it's not actively running,
1280                  * it must be off the runqueue _entirely_, and not
1281                  * preempted!
1282                  *
1283                  * So if it was still runnable (but just not actively
1284                  * running right now), it's preempted, and we should
1285                  * yield - it could be a while.
1286                  */
1287                 if (unlikely(on_rq)) {
1288                         ktime_t to = ktime_set(0, NSEC_PER_SEC/HZ);
1289
1290                         set_current_state(TASK_UNINTERRUPTIBLE);
1291                         schedule_hrtimeout(&to, HRTIMER_MODE_REL);
1292                         continue;
1293                 }
1294
1295                 /*
1296                  * Ahh, all good. It wasn't running, and it wasn't
1297                  * runnable, which means that it will never become
1298                  * running in the future either. We're all done!
1299                  */
1300                 break;
1301         }
1302
1303         return ncsw;
1304 }
1305
1306 /***
1307  * kick_process - kick a running thread to enter/exit the kernel
1308  * @p: the to-be-kicked thread
1309  *
1310  * Cause a process which is running on another CPU to enter
1311  * kernel-mode, without any delay. (to get signals handled.)
1312  *
1313  * NOTE: this function doesn't have to take the runqueue lock,
1314  * because all it wants to ensure is that the remote task enters
1315  * the kernel. If the IPI races and the task has been migrated
1316  * to another CPU then no harm is done and the purpose has been
1317  * achieved as well.
1318  */
1319 void kick_process(struct task_struct *p)
1320 {
1321         int cpu;
1322
1323         preempt_disable();
1324         cpu = task_cpu(p);
1325         if ((cpu != smp_processor_id()) && task_curr(p))
1326                 smp_send_reschedule(cpu);
1327         preempt_enable();
1328 }
1329 EXPORT_SYMBOL_GPL(kick_process);
1330 #endif /* CONFIG_SMP */
1331
1332 #ifdef CONFIG_SMP
1333 /*
1334  * ->cpus_allowed is protected by both rq->lock and p->pi_lock
1335  */
1336 static int select_fallback_rq(int cpu, struct task_struct *p)
1337 {
1338         int nid = cpu_to_node(cpu);
1339         const struct cpumask *nodemask = NULL;
1340         enum { cpuset, possible, fail } state = cpuset;
1341         int dest_cpu;
1342
1343         /*
1344          * If the node that the cpu is on has been offlined, cpu_to_node()
1345          * will return -1. There is no cpu on the node, and we should
1346          * select the cpu on the other node.
1347          */
1348         if (nid != -1) {
1349                 nodemask = cpumask_of_node(nid);
1350
1351                 /* Look for allowed, online CPU in same node. */
1352                 for_each_cpu(dest_cpu, nodemask) {
1353                         if (!cpu_online(dest_cpu))
1354                                 continue;
1355                         if (!cpu_active(dest_cpu))
1356                                 continue;
1357                         if (cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
1358                                 return dest_cpu;
1359                 }
1360         }
1361
1362         for (;;) {
1363                 /* Any allowed, online CPU? */
1364                 for_each_cpu(dest_cpu, tsk_cpus_allowed(p)) {
1365                         if (!cpu_online(dest_cpu))
1366                                 continue;
1367                         if (!cpu_active(dest_cpu))
1368                                 continue;
1369                         goto out;
1370                 }
1371
1372                 switch (state) {
1373                 case cpuset:
1374                         /* No more Mr. Nice Guy. */
1375                         cpuset_cpus_allowed_fallback(p);
1376                         state = possible;
1377                         break;
1378
1379                 case possible:
1380                         do_set_cpus_allowed(p, cpu_possible_mask);
1381                         state = fail;
1382                         break;
1383
1384                 case fail:
1385                         BUG();
1386                         break;
1387                 }
1388         }
1389
1390 out:
1391         if (state != cpuset) {
1392                 /*
1393                  * Don't tell them about moving exiting tasks or
1394                  * kernel threads (both mm NULL), since they never
1395                  * leave kernel.
1396                  */
1397                 if (p->mm && printk_ratelimit()) {
1398                         printk_deferred("process %d (%s) no longer affine to cpu%d\n",
1399                                         task_pid_nr(p), p->comm, cpu);
1400                 }
1401         }
1402
1403         return dest_cpu;
1404 }
1405
1406 /*
1407  * The caller (fork, wakeup) owns p->pi_lock, ->cpus_allowed is stable.
1408  */
1409 static inline
1410 int select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags)
1411 {
1412         cpu = p->sched_class->select_task_rq(p, cpu, sd_flags, wake_flags);
1413
1414         /*
1415          * In order not to call set_task_cpu() on a blocking task we need
1416          * to rely on ttwu() to place the task on a valid ->cpus_allowed
1417          * cpu.
1418          *
1419          * Since this is common to all placement strategies, this lives here.
1420          *
1421          * [ this allows ->select_task() to simply return task_cpu(p) and
1422          *   not worry about this generic constraint ]
1423          */
1424         if (unlikely(!cpumask_test_cpu(cpu, tsk_cpus_allowed(p)) ||
1425                      !cpu_online(cpu)))
1426                 cpu = select_fallback_rq(task_cpu(p), p);
1427
1428         return cpu;
1429 }
1430
1431 static void update_avg(u64 *avg, u64 sample)
1432 {
1433         s64 diff = sample - *avg;
1434         *avg += diff >> 3;
1435 }
1436 #endif
1437
1438 static void
1439 ttwu_stat(struct task_struct *p, int cpu, int wake_flags)
1440 {
1441 #ifdef CONFIG_SCHEDSTATS
1442         struct rq *rq = this_rq();
1443
1444 #ifdef CONFIG_SMP
1445         int this_cpu = smp_processor_id();
1446
1447         if (cpu == this_cpu) {
1448                 schedstat_inc(rq, ttwu_local);
1449                 schedstat_inc(p, se.statistics.nr_wakeups_local);
1450         } else {
1451                 struct sched_domain *sd;
1452
1453                 schedstat_inc(p, se.statistics.nr_wakeups_remote);
1454                 rcu_read_lock();
1455                 for_each_domain(this_cpu, sd) {
1456                         if (cpumask_test_cpu(cpu, sched_domain_span(sd))) {
1457                                 schedstat_inc(sd, ttwu_wake_remote);
1458                                 break;
1459                         }
1460                 }
1461                 rcu_read_unlock();
1462         }
1463
1464         if (wake_flags & WF_MIGRATED)
1465                 schedstat_inc(p, se.statistics.nr_wakeups_migrate);
1466
1467 #endif /* CONFIG_SMP */
1468
1469         schedstat_inc(rq, ttwu_count);
1470         schedstat_inc(p, se.statistics.nr_wakeups);
1471
1472         if (wake_flags & WF_SYNC)
1473                 schedstat_inc(p, se.statistics.nr_wakeups_sync);
1474
1475 #endif /* CONFIG_SCHEDSTATS */
1476 }
1477
1478 static void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
1479 {
1480         activate_task(rq, p, en_flags);
1481         p->on_rq = 1;
1482
1483         /* if a worker is waking up, notify workqueue */
1484         if (p->flags & PF_WQ_WORKER)
1485                 wq_worker_waking_up(p, cpu_of(rq));
1486 }
1487
1488 /*
1489  * Mark the task runnable and perform wakeup-preemption.
1490  */
1491 static void
1492 ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
1493 {
1494         check_preempt_curr(rq, p, wake_flags);
1495         trace_sched_wakeup(p, true);
1496
1497         p->state = TASK_RUNNING;
1498 #ifdef CONFIG_SMP
1499         if (p->sched_class->task_woken)
1500                 p->sched_class->task_woken(rq, p);
1501
1502         if (rq->idle_stamp) {
1503                 u64 delta = rq_clock(rq) - rq->idle_stamp;
1504                 u64 max = 2*rq->max_idle_balance_cost;
1505
1506                 update_avg(&rq->avg_idle, delta);
1507
1508                 if (rq->avg_idle > max)
1509                         rq->avg_idle = max;
1510
1511                 rq->idle_stamp = 0;
1512         }
1513 #endif
1514 }
1515
1516 static void
1517 ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags)
1518 {
1519 #ifdef CONFIG_SMP
1520         if (p->sched_contributes_to_load)
1521                 rq->nr_uninterruptible--;
1522 #endif
1523
1524         ttwu_activate(rq, p, ENQUEUE_WAKEUP | ENQUEUE_WAKING);
1525         ttwu_do_wakeup(rq, p, wake_flags);
1526 }
1527
1528 /*
1529  * Called in case the task @p isn't fully descheduled from its runqueue,
1530  * in this case we must do a remote wakeup. Its a 'light' wakeup though,
1531  * since all we need to do is flip p->state to TASK_RUNNING, since
1532  * the task is still ->on_rq.
1533  */
1534 static int ttwu_remote(struct task_struct *p, int wake_flags)
1535 {
1536         struct rq *rq;
1537         int ret = 0;
1538
1539         rq = __task_rq_lock(p);
1540         if (p->on_rq) {
1541                 /* check_preempt_curr() may use rq clock */
1542                 update_rq_clock(rq);
1543                 ttwu_do_wakeup(rq, p, wake_flags);
1544                 ret = 1;
1545         }
1546         __task_rq_unlock(rq);
1547
1548         return ret;
1549 }
1550
1551 #ifdef CONFIG_SMP
1552 void sched_ttwu_pending(void)
1553 {
1554         struct rq *rq = this_rq();
1555         struct llist_node *llist = llist_del_all(&rq->wake_list);
1556         struct task_struct *p;
1557         unsigned long flags;
1558
1559         if (!llist)
1560                 return;
1561
1562         raw_spin_lock_irqsave(&rq->lock, flags);
1563
1564         while (llist) {
1565                 p = llist_entry(llist, struct task_struct, wake_entry);
1566                 llist = llist_next(llist);
1567                 ttwu_do_activate(rq, p, 0);
1568         }
1569
1570         raw_spin_unlock_irqrestore(&rq->lock, flags);
1571 }
1572
1573 void scheduler_ipi(void)
1574 {
1575         /*
1576          * Fold TIF_NEED_RESCHED into the preempt_count; anybody setting
1577          * TIF_NEED_RESCHED remotely (for the first time) will also send
1578          * this IPI.
1579          */
1580         preempt_fold_need_resched();
1581
1582         if (llist_empty(&this_rq()->wake_list) && !got_nohz_idle_kick())
1583                 return;
1584
1585         /*
1586          * Not all reschedule IPI handlers call irq_enter/irq_exit, since
1587          * traditionally all their work was done from the interrupt return
1588          * path. Now that we actually do some work, we need to make sure
1589          * we do call them.
1590          *
1591          * Some archs already do call them, luckily irq_enter/exit nest
1592          * properly.
1593          *
1594          * Arguably we should visit all archs and update all handlers,
1595          * however a fair share of IPIs are still resched only so this would
1596          * somewhat pessimize the simple resched case.
1597          */
1598         irq_enter();
1599         sched_ttwu_pending();
1600
1601         /*
1602          * Check if someone kicked us for doing the nohz idle load balance.
1603          */
1604         if (unlikely(got_nohz_idle_kick())) {
1605                 this_rq()->idle_balance = 1;
1606                 raise_softirq_irqoff(SCHED_SOFTIRQ);
1607         }
1608         irq_exit();
1609 }
1610
1611 static void ttwu_queue_remote(struct task_struct *p, int cpu)
1612 {
1613         struct rq *rq = cpu_rq(cpu);
1614
1615         if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list)) {
1616                 if (!set_nr_if_polling(rq->idle))
1617                         smp_send_reschedule(cpu);
1618                 else
1619                         trace_sched_wake_idle_without_ipi(cpu);
1620         }
1621 }
1622
1623 bool cpus_share_cache(int this_cpu, int that_cpu)
1624 {
1625         return per_cpu(sd_llc_id, this_cpu) == per_cpu(sd_llc_id, that_cpu);
1626 }
1627 #endif /* CONFIG_SMP */
1628
1629 static void ttwu_queue(struct task_struct *p, int cpu)
1630 {
1631         struct rq *rq = cpu_rq(cpu);
1632
1633 #if defined(CONFIG_SMP)
1634         if (sched_feat(TTWU_QUEUE) && !cpus_share_cache(smp_processor_id(), cpu)) {
1635                 sched_clock_cpu(cpu); /* sync clocks x-cpu */
1636                 ttwu_queue_remote(p, cpu);
1637                 return;
1638         }
1639 #endif
1640
1641         raw_spin_lock(&rq->lock);
1642         ttwu_do_activate(rq, p, 0);
1643         raw_spin_unlock(&rq->lock);
1644 }
1645
1646 /**
1647  * try_to_wake_up - wake up a thread
1648  * @p: the thread to be awakened
1649  * @state: the mask of task states that can be woken
1650  * @wake_flags: wake modifier flags (WF_*)
1651  *
1652  * Put it on the run-queue if it's not already there. The "current"
1653  * thread is always on the run-queue (except when the actual
1654  * re-schedule is in progress), and as such you're allowed to do
1655  * the simpler "current->state = TASK_RUNNING" to mark yourself
1656  * runnable without the overhead of this.
1657  *
1658  * Return: %true if @p was woken up, %false if it was already running.
1659  * or @state didn't match @p's state.
1660  */
1661 static int
1662 try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
1663 {
1664         unsigned long flags;
1665         int cpu, success = 0;
1666
1667         /*
1668          * If we are going to wake up a thread waiting for CONDITION we
1669          * need to ensure that CONDITION=1 done by the caller can not be
1670          * reordered with p->state check below. This pairs with mb() in
1671          * set_current_state() the waiting thread does.
1672          */
1673         smp_mb__before_spinlock();
1674         raw_spin_lock_irqsave(&p->pi_lock, flags);
1675         if (!(p->state & state))
1676                 goto out;
1677
1678         success = 1; /* we're going to change ->state */
1679         cpu = task_cpu(p);
1680
1681         if (p->on_rq && ttwu_remote(p, wake_flags))
1682                 goto stat;
1683
1684 #ifdef CONFIG_SMP
1685         /*
1686          * If the owning (remote) cpu is still in the middle of schedule() with
1687          * this task as prev, wait until its done referencing the task.
1688          */
1689         while (p->on_cpu)
1690                 cpu_relax();
1691         /*
1692          * Pairs with the smp_wmb() in finish_lock_switch().
1693          */
1694         smp_rmb();
1695
1696         p->sched_contributes_to_load = !!task_contributes_to_load(p);
1697         p->state = TASK_WAKING;
1698
1699         if (p->sched_class->task_waking)
1700                 p->sched_class->task_waking(p);
1701
1702         cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);
1703         if (task_cpu(p) != cpu) {
1704                 wake_flags |= WF_MIGRATED;
1705                 set_task_cpu(p, cpu);
1706         }
1707 #endif /* CONFIG_SMP */
1708
1709         ttwu_queue(p, cpu);
1710 stat:
1711         ttwu_stat(p, cpu, wake_flags);
1712 out:
1713         raw_spin_unlock_irqrestore(&p->pi_lock, flags);
1714
1715 //      if (test_tsk && ((int)test_tsk->pid == test_tsk_pid)) {
1716 //              printk("task(%i): try_to_wake_up -> %i\n", test_tsk_pid, TASK_RUNNING);
1717 //      }
1718
1719         return success;
1720 }
1721
1722 /**
1723  * try_to_wake_up_local - try to wake up a local task with rq lock held
1724  * @p: the thread to be awakened
1725  *
1726  * Put @p on the run-queue if it's not already there. The caller must
1727  * ensure that this_rq() is locked, @p is bound to this_rq() and not
1728  * the current task.
1729  */
1730 static void try_to_wake_up_local(struct task_struct *p)
1731 {
1732         struct rq *rq = task_rq(p);
1733
1734         if (WARN_ON_ONCE(rq != this_rq()) ||
1735             WARN_ON_ONCE(p == current))
1736                 return;
1737
1738         lockdep_assert_held(&rq->lock);
1739
1740         if (!raw_spin_trylock(&p->pi_lock)) {
1741                 raw_spin_unlock(&rq->lock);
1742                 raw_spin_lock(&p->pi_lock);
1743                 raw_spin_lock(&rq->lock);
1744         }
1745
1746         if (!(p->state & TASK_NORMAL))
1747                 goto out;
1748
1749         if (!p->on_rq)
1750                 ttwu_activate(rq, p, ENQUEUE_WAKEUP);
1751
1752         ttwu_do_wakeup(rq, p, 0);
1753         ttwu_stat(p, smp_processor_id(), 0);
1754 out:
1755         raw_spin_unlock(&p->pi_lock);
1756 }
1757
1758 /**
1759  * wake_up_process - Wake up a specific process
1760  * @p: The process to be woken up.
1761  *
1762  * Attempt to wake up the nominated process and move it to the set of runnable
1763  * processes.
1764  *
1765  * Return: 1 if the process was woken up, 0 if it was already running.
1766  *
1767  * It may be assumed that this function implies a write memory barrier before
1768  * changing the task state if and only if any tasks are woken up.
1769  */
1770 int wake_up_process(struct task_struct *p)
1771 {
1772         WARN_ON(task_is_stopped_or_traced(p));
1773         return try_to_wake_up(p, TASK_NORMAL, 0);
1774 }
1775 EXPORT_SYMBOL(wake_up_process);
1776
1777 int wake_up_state(struct task_struct *p, unsigned int state)
1778 {
1779         WARN_ON(task_is_stopped_or_traced(p));
1780         return try_to_wake_up(p, state, 0);
1781 }
1782 EXPORT_SYMBOL(wake_up_process);
1783
1784 /*
1785  * Perform scheduler related setup for a newly forked process p.
1786  * p is forked by current.
1787  *
1788  * __sched_fork() is basic setup used by init_idle() too:
1789  */
1790 static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
1791 {
1792         p->on_rq                        = 0;
1793
1794         p->se.on_rq                     = 0;
1795         p->se.exec_start                = 0;
1796         p->se.sum_exec_runtime          = 0;
1797         p->se.prev_sum_exec_runtime     = 0;
1798         p->se.nr_migrations             = 0;
1799         p->se.vruntime                  = 0;
1800         INIT_LIST_HEAD(&p->se.group_node);
1801
1802 #ifdef CONFIG_SCHEDSTATS
1803         memset(&p->se.statistics, 0, sizeof(p->se.statistics));
1804 #endif
1805
1806         RB_CLEAR_NODE(&p->dl.rb_node);
1807         hrtimer_init(&p->dl.dl_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
1808         p->dl.dl_runtime = p->dl.runtime = 0;
1809         p->dl.dl_deadline = p->dl.deadline = 0;
1810         p->dl.dl_period = 0;
1811         p->dl.flags = 0;
1812
1813         INIT_LIST_HEAD(&p->rt.run_list);
1814
1815 #ifdef CONFIG_PREEMPT_NOTIFIERS
1816         INIT_HLIST_HEAD(&p->preempt_notifiers);
1817 #endif
1818
1819 #ifdef CONFIG_NUMA_BALANCING
1820         if (p->mm && atomic_read(&p->mm->mm_users) == 1) {
1821                 p->mm->numa_next_scan = jiffies + msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
1822                 p->mm->numa_scan_seq = 0;
1823         }
1824
1825         if (clone_flags & CLONE_VM)
1826                 p->numa_preferred_nid = current->numa_preferred_nid;
1827         else
1828                 p->numa_preferred_nid = -1;
1829
1830         p->node_stamp = 0ULL;
1831         p->numa_scan_seq = p->mm ? p->mm->numa_scan_seq : 0;
1832         p->numa_scan_period = sysctl_numa_balancing_scan_delay;
1833         p->numa_work.next = &p->numa_work;
1834         p->numa_faults_memory = NULL;
1835         p->numa_faults_buffer_memory = NULL;
1836         p->last_task_numa_placement = 0;
1837         p->last_sum_exec_runtime = 0;
1838
1839         INIT_LIST_HEAD(&p->numa_entry);
1840         p->numa_group = NULL;
1841 #endif /* CONFIG_NUMA_BALANCING */
1842 }
1843
1844 #ifdef CONFIG_NUMA_BALANCING
1845 #ifdef CONFIG_SCHED_DEBUG
1846 void set_numabalancing_state(bool enabled)
1847 {
1848         if (enabled)
1849                 sched_feat_set("NUMA");
1850         else
1851                 sched_feat_set("NO_NUMA");
1852 }
1853 #else
1854 __read_mostly bool numabalancing_enabled;
1855
1856 void set_numabalancing_state(bool enabled)
1857 {
1858         numabalancing_enabled = enabled;
1859 }
1860 #endif /* CONFIG_SCHED_DEBUG */
1861
1862 #ifdef CONFIG_PROC_SYSCTL
1863 int sysctl_numa_balancing(struct ctl_table *table, int write,
1864                          void __user *buffer, size_t *lenp, loff_t *ppos)
1865 {
1866         struct ctl_table t;
1867         int err;
1868         int state = numabalancing_enabled;
1869
1870         if (write && !capable(CAP_SYS_ADMIN))
1871                 return -EPERM;
1872
1873         t = *table;
1874         t.data = &state;
1875         err = proc_dointvec_minmax(&t, write, buffer, lenp, ppos);
1876         if (err < 0)
1877                 return err;
1878         if (write)
1879                 set_numabalancing_state(state);
1880         return err;
1881 }
1882 #endif
1883 #endif
1884
1885 /*
1886  * fork()/clone()-time setup:
1887  */
1888 int sched_fork(unsigned long clone_flags, struct task_struct *p)
1889 {
1890         unsigned long flags;
1891         int cpu = get_cpu();
1892
1893         __sched_fork(clone_flags, p);
1894         /*
1895          * We mark the process as running here. This guarantees that
1896          * nobody will actually run it, and a signal or other external
1897          * event cannot wake it up and insert it on the runqueue either.
1898          */
1899         p->state = TASK_RUNNING;
1900
1901         /*
1902          * Make sure we do not leak PI boosting priority to the child.
1903          */
1904         p->prio = current->normal_prio;
1905
1906         /*
1907          * Revert to default priority/policy on fork if requested.
1908          */
1909         if (unlikely(p->sched_reset_on_fork)) {
1910                 if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
1911                         p->policy = SCHED_NORMAL;
1912                         p->static_prio = NICE_TO_PRIO(0);
1913                         p->rt_priority = 0;
1914                 } else if (PRIO_TO_NICE(p->static_prio) < 0)
1915                         p->static_prio = NICE_TO_PRIO(0);
1916
1917                 p->prio = p->normal_prio = __normal_prio(p);
1918                 set_load_weight(p);
1919
1920                 /*
1921                  * We don't need the reset flag anymore after the fork. It has
1922                  * fulfilled its duty:
1923                  */
1924                 p->sched_reset_on_fork = 0;
1925         }
1926
1927         if (dl_prio(p->prio)) {
1928                 put_cpu();
1929                 return -EAGAIN;
1930         } else if (rt_prio(p->prio)) {
1931                 p->sched_class = &rt_sched_class;
1932         } else {
1933                 p->sched_class = &fair_sched_class;
1934         }
1935
1936         if (p->sched_class->task_fork)
1937                 p->sched_class->task_fork(p);
1938
1939         /*
1940          * The child is not yet in the pid-hash so no cgroup attach races,
1941          * and the cgroup is pinned to this child due to cgroup_fork()
1942          * is ran before sched_fork().
1943          *
1944          * Silence PROVE_RCU.
1945          */
1946         raw_spin_lock_irqsave(&p->pi_lock, flags);
1947         set_task_cpu(p, cpu);
1948         raw_spin_unlock_irqrestore(&p->pi_lock, flags);
1949
1950 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
1951         if (likely(sched_info_on()))
1952                 memset(&p->sched_info, 0, sizeof(p->sched_info));
1953 #endif
1954 #if defined(CONFIG_SMP)
1955         p->on_cpu = 0;
1956 #endif
1957         init_task_preempt_count(p);
1958 #ifdef CONFIG_SMP
1959         plist_node_init(&p->pushable_tasks, MAX_PRIO);
1960         RB_CLEAR_NODE(&p->pushable_dl_tasks);
1961 #endif
1962
1963         put_cpu();
1964         return 0;
1965 }
1966
1967 unsigned long to_ratio(u64 period, u64 runtime)
1968 {
1969         if (runtime == RUNTIME_INF)
1970                 return 1ULL << 20;
1971
1972         /*
1973          * Doing this here saves a lot of checks in all
1974          * the calling paths, and returning zero seems
1975          * safe for them anyway.
1976          */
1977         if (period == 0)
1978                 return 0;
1979
1980         return div64_u64(runtime << 20, period);
1981 }
1982
1983 #ifdef CONFIG_SMP
1984 inline struct dl_bw *dl_bw_of(int i)
1985 {
1986         return &cpu_rq(i)->rd->dl_bw;
1987 }
1988
1989 static inline int dl_bw_cpus(int i)
1990 {
1991         struct root_domain *rd = cpu_rq(i)->rd;
1992         int cpus = 0;
1993
1994         for_each_cpu_and(i, rd->span, cpu_active_mask)
1995                 cpus++;
1996
1997         return cpus;
1998 }
1999 #else
2000 inline struct dl_bw *dl_bw_of(int i)
2001 {
2002         return &cpu_rq(i)->dl.dl_bw;
2003 }
2004
2005 static inline int dl_bw_cpus(int i)
2006 {
2007         return 1;
2008 }
2009 #endif
2010
2011 static inline
2012 void __dl_clear(struct dl_bw *dl_b, u64 tsk_bw)
2013 {
2014         dl_b->total_bw -= tsk_bw;
2015 }
2016
2017 static inline
2018 void __dl_add(struct dl_bw *dl_b, u64 tsk_bw)
2019 {
2020         dl_b->total_bw += tsk_bw;
2021 }
2022
2023 static inline
2024 bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64 new_bw)
2025 {
2026         return dl_b->bw != -1 &&
2027                dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw;
2028 }
2029
2030 /*
2031  * We must be sure that accepting a new task (or allowing changing the
2032  * parameters of an existing one) is consistent with the bandwidth
2033  * constraints. If yes, this function also accordingly updates the currently
2034  * allocated bandwidth to reflect the new situation.
2035  *
2036  * This function is called while holding p's rq->lock.
2037  */
2038 static int dl_overflow(struct task_struct *p, int policy,
2039                        const struct sched_attr *attr)
2040 {
2041
2042         struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
2043         u64 period = attr->sched_period ?: attr->sched_deadline;
2044         u64 runtime = attr->sched_runtime;
2045         u64 new_bw = dl_policy(policy) ? to_ratio(period, runtime) : 0;
2046         int cpus, err = -1;
2047
2048         if (new_bw == p->dl.dl_bw)
2049                 return 0;
2050
2051         /*
2052          * Either if a task, enters, leave, or stays -deadline but changes
2053          * its parameters, we may need to update accordingly the total
2054          * allocated bandwidth of the container.
2055          */
2056         raw_spin_lock(&dl_b->lock);
2057         cpus = dl_bw_cpus(task_cpu(p));
2058         if (dl_policy(policy) && !task_has_dl_policy(p) &&
2059             !__dl_overflow(dl_b, cpus, 0, new_bw)) {
2060                 __dl_add(dl_b, new_bw);
2061                 err = 0;
2062         } else if (dl_policy(policy) && task_has_dl_policy(p) &&
2063                    !__dl_overflow(dl_b, cpus, p->dl.dl_bw, new_bw)) {
2064                 __dl_clear(dl_b, p->dl.dl_bw);
2065                 __dl_add(dl_b, new_bw);
2066                 err = 0;
2067         } else if (!dl_policy(policy) && task_has_dl_policy(p)) {
2068                 __dl_clear(dl_b, p->dl.dl_bw);
2069                 err = 0;
2070         }
2071         raw_spin_unlock(&dl_b->lock);
2072
2073         return err;
2074 }
2075
2076 extern void init_dl_bw(struct dl_bw *dl_b);
2077
2078 /*
2079  * wake_up_new_task - wake up a newly created task for the first time.
2080  *
2081  * This function will do some initial scheduler statistics housekeeping
2082  * that must be done for every newly created context, then puts the task
2083  * on the runqueue and wakes it.
2084  */
2085 void wake_up_new_task(struct task_struct *p)
2086 {
2087         unsigned long flags;
2088         struct rq *rq;
2089
2090         raw_spin_lock_irqsave(&p->pi_lock, flags);
2091 #ifdef CONFIG_SMP
2092         /*
2093          * Fork balancing, do it here and not earlier because:
2094          *  - cpus_allowed can change in the fork path
2095          *  - any previously selected cpu might disappear through hotplug
2096          */
2097         set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));
2098 #endif
2099
2100         /* Initialize new task's runnable average */
2101         init_task_runnable_average(p);
2102         rq = __task_rq_lock(p);
2103         activate_task(rq, p, 0);
2104         p->on_rq = 1;
2105         trace_sched_wakeup_new(p, true);
2106         check_preempt_curr(rq, p, WF_FORK);
2107 #ifdef CONFIG_SMP
2108         if (p->sched_class->task_woken)
2109                 p->sched_class->task_woken(rq, p);
2110 #endif
2111         task_rq_unlock(rq, p, &flags);
2112 }
2113
2114 #ifdef CONFIG_PREEMPT_NOTIFIERS
2115
2116 /**
2117  * preempt_notifier_register - tell me when current is being preempted & rescheduled
2118  * @notifier: notifier struct to register
2119  */
2120 void preempt_notifier_register(struct preempt_notifier *notifier)
2121 {
2122         hlist_add_head(&notifier->link, &current->preempt_notifiers);
2123 }
2124 EXPORT_SYMBOL_GPL(preempt_notifier_register);
2125
2126 /**
2127  * preempt_notifier_unregister - no longer interested in preemption notifications
2128  * @notifier: notifier struct to unregister
2129  *
2130  * This is safe to call from within a preemption notifier.
2131  */
2132 void preempt_notifier_unregister(struct preempt_notifier *notifier)
2133 {
2134         hlist_del(&notifier->link);
2135 }
2136 EXPORT_SYMBOL_GPL(preempt_notifier_unregister);
2137
2138 static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
2139 {
2140         struct preempt_notifier *notifier;
2141
2142         hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
2143                 notifier->ops->sched_in(notifier, raw_smp_processor_id());
2144 }
2145
2146 static void
2147 fire_sched_out_preempt_notifiers(struct task_struct *curr,
2148                                  struct task_struct *next)
2149 {
2150         struct preempt_notifier *notifier;
2151
2152         hlist_for_each_entry(notifier, &curr->preempt_notifiers, link)
2153                 notifier->ops->sched_out(notifier, next);
2154 }
2155
2156 #else /* !CONFIG_PREEMPT_NOTIFIERS */
2157
2158 static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
2159 {
2160 }
2161
2162 static void
2163 fire_sched_out_preempt_notifiers(struct task_struct *curr,
2164                                  struct task_struct *next)
2165 {
2166 }
2167
2168 #endif /* CONFIG_PREEMPT_NOTIFIERS */
2169
2170 /**
2171  * prepare_task_switch - prepare to switch tasks
2172  * @rq: the runqueue preparing to switch
2173  * @prev: the current task that is being switched out
2174  * @next: the task we are going to switch to.
2175  *
2176  * This is called with the rq lock held and interrupts off. It must
2177  * be paired with a subsequent finish_task_switch after the context
2178  * switch.
2179  *
2180  * prepare_task_switch sets up locking and calls architecture specific
2181  * hooks.
2182  */
2183 static inline void
2184 prepare_task_switch(struct rq *rq, struct task_struct *prev,
2185                     struct task_struct *next)
2186 {
2187         trace_sched_switch(prev, next);
2188         sched_info_switch(rq, prev, next);
2189         perf_event_task_sched_out(prev, next);
2190         fire_sched_out_preempt_notifiers(prev, next);
2191         prepare_lock_switch(rq, next);
2192         prepare_arch_switch(next);
2193 }
2194
2195 /**
2196  * finish_task_switch - clean up after a task-switch
2197  * @rq: runqueue associated with task-switch
2198  * @prev: the thread we just switched away from.
2199  *
2200  * finish_task_switch must be called after the context switch, paired
2201  * with a prepare_task_switch call before the context switch.
2202  * finish_task_switch will reconcile locking set up by prepare_task_switch,
2203  * and do any other architecture-specific cleanup actions.
2204  *
2205  * Note that we may have delayed dropping an mm in context_switch(). If
2206  * so, we finish that here outside of the runqueue lock. (Doing it
2207  * with the lock held can cause deadlocks; see schedule() for
2208  * details.)
2209  */
2210 static void finish_task_switch(struct rq *rq, struct task_struct *prev)
2211         __releases(rq->lock)
2212 {
2213         struct mm_struct *mm = rq->prev_mm;
2214         long prev_state;
2215
2216         rq->prev_mm = NULL;
2217
2218         /*
2219          * A task struct has one reference for the use as "current".
2220          * If a task dies, then it sets TASK_DEAD in tsk->state and calls
2221          * schedule one last time. The schedule call will never return, and
2222          * the scheduled task must drop that reference.
2223          * The test for TASK_DEAD must occur while the runqueue locks are
2224          * still held, otherwise prev could be scheduled on another cpu, die
2225          * there before we look at prev->state, and then the reference would
2226          * be dropped twice.
2227          *              Manfred Spraul <manfred@colorfullife.com>
2228          */
2229         prev_state = prev->state;
2230         vtime_task_switch(prev);
2231         finish_arch_switch(prev);
2232         perf_event_task_sched_in(prev, current);
2233         finish_lock_switch(rq, prev);
2234         finish_arch_post_lock_switch();
2235
2236         fire_sched_in_preempt_notifiers(current);
2237         if (mm)
2238                 mmdrop(mm);
2239         if (unlikely(prev_state == TASK_DEAD)) {
2240                 if (prev->sched_class->task_dead)
2241                         prev->sched_class->task_dead(prev);
2242
2243                 /*
2244                  * Remove function-return probe instances associated with this
2245                  * task and put them back on the free list.
2246                  */
2247                 kprobe_flush_task(prev);
2248                 put_task_struct(prev);
2249         }
2250
2251         tick_nohz_task_switch(current);
2252 }
2253
2254 #ifdef CONFIG_SMP
2255
2256 /* rq->lock is NOT held, but preemption is disabled */
2257 static inline void post_schedule(struct rq *rq)
2258 {
2259         if (rq->post_schedule) {
2260                 unsigned long flags;
2261
2262                 raw_spin_lock_irqsave(&rq->lock, flags);
2263                 if (rq->curr->sched_class->post_schedule)
2264                         rq->curr->sched_class->post_schedule(rq);
2265                 raw_spin_unlock_irqrestore(&rq->lock, flags);
2266
2267                 rq->post_schedule = 0;
2268         }
2269 }
2270
2271 #else
2272
2273 static inline void post_schedule(struct rq *rq)
2274 {
2275 }
2276
2277 #endif
2278
2279 /**
2280  * schedule_tail - first thing a freshly forked thread must call.
2281  * @prev: the thread we just switched away from.
2282  */
2283 asmlinkage __visible void schedule_tail(struct task_struct *prev)
2284         __releases(rq->lock)
2285 {
2286         struct rq *rq = this_rq();
2287
2288         finish_task_switch(rq, prev);
2289
2290         /*
2291          * FIXME: do we need to worry about rq being invalidated by the
2292          * task_switch?
2293          */
2294         post_schedule(rq);
2295
2296 #ifdef __ARCH_WANT_UNLOCKED_CTXSW
2297         /* In this case, finish_task_switch does not reenable preemption */
2298         preempt_enable();
2299 #endif
2300         if (current->set_child_tid)
2301                 put_user(task_pid_vnr(current), current->set_child_tid);
2302 }
2303
2304 /*
2305  * context_switch - switch to the new MM and the new
2306  * thread's register state.
2307  */
2308 static inline void
2309 context_switch(struct rq *rq, struct task_struct *prev,
2310                struct task_struct *next)
2311 {
2312         struct mm_struct *mm, *oldmm;
2313
2314         prepare_task_switch(rq, prev, next);
2315
2316         mm = next->mm;
2317         oldmm = prev->active_mm;
2318         /*
2319          * For paravirt, this is coupled with an exit in switch_to to
2320          * combine the page table reload and the switch backend into
2321          * one hypercall.
2322          */
2323         arch_start_context_switch(prev);
2324
2325         if (!mm) {
2326                 next->active_mm = oldmm;
2327                 atomic_inc(&oldmm->mm_count);
2328                 enter_lazy_tlb(oldmm, next);
2329         } else
2330                 switch_mm(oldmm, mm, next);
2331
2332         if (!prev->mm) {
2333                 prev->active_mm = NULL;
2334                 rq->prev_mm = oldmm;
2335         }
2336         /*
2337          * Since the runqueue lock will be released by the next
2338          * task (which is an invalid locking op but in the case
2339          * of the scheduler it's an obvious special-case), so we
2340          * do an early lockdep release here:
2341          */
2342 #ifndef __ARCH_WANT_UNLOCKED_CTXSW
2343         spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
2344 #endif
2345
2346         context_tracking_task_switch(prev, next);
2347         /* Here we just switch the register state and the stack. */
2348         switch_to(prev, next, prev);
2349
2350         barrier();
2351         /*
2352          * this_rq must be evaluated again because prev may have moved
2353          * CPUs since it called schedule(), thus the 'rq' on its stack
2354          * frame will be invalid.
2355          */
2356         finish_task_switch(this_rq(), prev);
2357 }
2358
2359 /*
2360  * nr_running and nr_context_switches:
2361  *
2362  * externally visible scheduler statistics: current number of runnable
2363  * threads, total number of context switches performed since bootup.
2364  */
2365 unsigned long nr_running(void)
2366 {
2367         unsigned long i, sum = 0;
2368
2369         for_each_online_cpu(i)
2370                 sum += cpu_rq(i)->nr_running;
2371
2372         return sum;
2373 }
2374
2375 unsigned long long nr_context_switches(void)
2376 {
2377         int i;
2378         unsigned long long sum = 0;
2379
2380         for_each_possible_cpu(i)
2381                 sum += cpu_rq(i)->nr_switches;
2382
2383         return sum;
2384 }
2385
2386 unsigned long nr_iowait(void)
2387 {
2388         unsigned long i, sum = 0;
2389
2390         for_each_possible_cpu(i)
2391                 sum += atomic_read(&cpu_rq(i)->nr_iowait);
2392
2393         return sum;
2394 }
2395
2396 unsigned long nr_iowait_cpu(int cpu)
2397 {
2398         struct rq *this = cpu_rq(cpu);
2399         return atomic_read(&this->nr_iowait);
2400 }
2401
2402 void get_iowait_load(unsigned long *nr_waiters, unsigned long *load)
2403 {
2404         struct rq *this = this_rq();
2405         *nr_waiters = atomic_read(&this->nr_iowait);
2406         *load = this->cpu_load[0];
2407 }
2408
2409 #ifdef CONFIG_SMP
2410
2411 /*
2412  * sched_exec - execve() is a valuable balancing opportunity, because at
2413  * this point the task has the smallest effective memory and cache footprint.
2414  */
2415 void sched_exec(void)
2416 {
2417         struct task_struct *p = current;
2418         unsigned long flags;
2419         int dest_cpu;
2420
2421         raw_spin_lock_irqsave(&p->pi_lock, flags);
2422         dest_cpu = p->sched_class->select_task_rq(p, task_cpu(p), SD_BALANCE_EXEC, 0);
2423         if (dest_cpu == smp_processor_id())
2424                 goto unlock;
2425
2426         if (likely(cpu_active(dest_cpu))) {
2427                 struct migration_arg arg = { p, dest_cpu };
2428
2429                 raw_spin_unlock_irqrestore(&p->pi_lock, flags);
2430                 stop_one_cpu(task_cpu(p), migration_cpu_stop, &arg);
2431                 return;
2432         }
2433 unlock:
2434         raw_spin_unlock_irqrestore(&p->pi_lock, flags);
2435 }
2436
2437 #endif
2438
2439 DEFINE_PER_CPU(struct kernel_stat, kstat);
2440 DEFINE_PER_CPU(struct kernel_cpustat, kernel_cpustat);
2441
2442 EXPORT_PER_CPU_SYMBOL(kstat);
2443 EXPORT_PER_CPU_SYMBOL(kernel_cpustat);
2444
2445 /*
2446  * Return any ns on the sched_clock that have not yet been accounted in
2447  * @p in case that task is currently running.
2448  *
2449  * Called with task_rq_lock() held on @rq.
2450  */
2451 static u64 do_task_delta_exec(struct task_struct *p, struct rq *rq)
2452 {
2453         u64 ns = 0;
2454
2455         /*
2456          * Must be ->curr _and_ ->on_rq.  If dequeued, we would
2457          * project cycles that may never be accounted to this
2458          * thread, breaking clock_gettime().
2459          */
2460         if (task_current(rq, p) && p->on_rq) {
2461                 update_rq_clock(rq);
2462                 ns = rq_clock_task(rq) - p->se.exec_start;
2463                 if ((s64)ns < 0)
2464                         ns = 0;
2465         }
2466
2467         return ns;
2468 }
2469
2470 unsigned long long task_delta_exec(struct task_struct *p)
2471 {
2472         unsigned long flags;
2473         struct rq *rq;
2474         u64 ns = 0;
2475
2476         rq = task_rq_lock(p, &flags);
2477         ns = do_task_delta_exec(p, rq);
2478         task_rq_unlock(rq, p, &flags);
2479
2480         return ns;
2481 }
2482
2483 /*
2484  * Return accounted runtime for the task.
2485  * In case the task is currently running, return the runtime plus current's
2486  * pending runtime that have not been accounted yet.
2487  */
2488 unsigned long long task_sched_runtime(struct task_struct *p)
2489 {
2490         unsigned long flags;
2491         struct rq *rq;
2492         u64 ns = 0;
2493
2494 #if defined(CONFIG_64BIT) && defined(CONFIG_SMP)
2495         /*
2496          * 64-bit doesn't need locks to atomically read a 64bit value.
2497          * So we have a optimization chance when the task's delta_exec is 0.
2498          * Reading ->on_cpu is racy, but this is ok.
2499          *
2500          * If we race with it leaving cpu, we'll take a lock. So we're correct.
2501          * If we race with it entering cpu, unaccounted time is 0. This is
2502          * indistinguishable from the read occurring a few cycles earlier.
2503          * If we see ->on_cpu without ->on_rq, the task is leaving, and has
2504          * been accounted, so we're correct here as well.
2505          */
2506         if (!p->on_cpu || !p->on_rq)
2507                 return p->se.sum_exec_runtime;
2508 #endif
2509
2510         rq = task_rq_lock(p, &flags);
2511         ns = p->se.sum_exec_runtime + do_task_delta_exec(p, rq);
2512         task_rq_unlock(rq, p, &flags);
2513
2514         return ns;
2515 }
2516
2517 /*
2518  * This function gets called by the timer code, with HZ frequency.
2519  * We call it with interrupts disabled.
2520  */
2521 void scheduler_tick(void)
2522 {
2523         int cpu = smp_processor_id();
2524         struct rq *rq = cpu_rq(cpu);
2525         struct task_struct *curr = rq->curr;
2526
2527         sched_clock_tick();
2528
2529         raw_spin_lock(&rq->lock);
2530         update_rq_clock(rq);
2531         curr->sched_class->task_tick(rq, curr, 0);
2532         update_cpu_load_active(rq);
2533         raw_spin_unlock(&rq->lock);
2534
2535         perf_event_task_tick();
2536
2537 #ifdef CONFIG_SMP
2538         rq->idle_balance = idle_cpu(cpu);
2539         trigger_load_balance(rq);
2540 #endif
2541         rq_last_tick_reset(rq);
2542 }
2543
2544 #ifdef CONFIG_NO_HZ_FULL
2545 /**
2546  * scheduler_tick_max_deferment
2547  *
2548  * Keep at least one tick per second when a single
2549  * active task is running because the scheduler doesn't
2550  * yet completely support full dynticks environment.
2551  *
2552  * This makes sure that uptime, CFS vruntime, load
2553  * balancing, etc... continue to move forward, even
2554  * with a very low granularity.
2555  *
2556  * Return: Maximum deferment in nanoseconds.
2557  */
2558 u64 scheduler_tick_max_deferment(void)
2559 {
2560         struct rq *rq = this_rq();
2561         unsigned long next, now = ACCESS_ONCE(jiffies);
2562
2563         next = rq->last_sched_tick + HZ;
2564
2565         if (time_before_eq(next, now))
2566                 return 0;
2567
2568         return jiffies_to_nsecs(next - now);
2569 }
2570 #endif
2571
2572 notrace unsigned long get_parent_ip(unsigned long addr)
2573 {
2574         if (in_lock_functions(addr)) {
2575                 addr = CALLER_ADDR2;
2576                 if (in_lock_functions(addr))
2577                         addr = CALLER_ADDR3;
2578         }
2579         return addr;
2580 }
2581
2582 #if defined(CONFIG_PREEMPT) && (defined(CONFIG_DEBUG_PREEMPT) || \
2583                                 defined(CONFIG_PREEMPT_TRACER))
2584
2585 void preempt_count_add(int val)
2586 {
2587 #ifdef CONFIG_DEBUG_PREEMPT
2588         /*
2589          * Underflow?
2590          */
2591         if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
2592                 return;
2593 #endif
2594         __preempt_count_add(val);
2595 #ifdef CONFIG_DEBUG_PREEMPT
2596         /*
2597          * Spinlock count overflowing soon?
2598          */
2599         DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
2600                                 PREEMPT_MASK - 10);
2601 #endif
2602         if (preempt_count() == val) {
2603                 unsigned long ip = get_parent_ip(CALLER_ADDR1);
2604 #ifdef CONFIG_DEBUG_PREEMPT
2605                 current->preempt_disable_ip = ip;
2606 #endif
2607                 trace_preempt_off(CALLER_ADDR0, ip);
2608         }
2609 }
2610 EXPORT_SYMBOL(preempt_count_add);
2611 NOKPROBE_SYMBOL(preempt_count_add);
2612
2613 void preempt_count_sub(int val)
2614 {
2615 #ifdef CONFIG_DEBUG_PREEMPT
2616         /*
2617          * Underflow?
2618          */
2619         if (DEBUG_LOCKS_WARN_ON(val > preempt_count()))
2620                 return;
2621         /*
2622          * Is the spinlock portion underflowing?
2623          */
2624         if (DEBUG_LOCKS_WARN_ON((val < PREEMPT_MASK) &&
2625                         !(preempt_count() & PREEMPT_MASK)))
2626                 return;
2627 #endif
2628
2629         if (preempt_count() == val)
2630                 trace_preempt_on(CALLER_ADDR0, get_parent_ip(CALLER_ADDR1));
2631         __preempt_count_sub(val);
2632 }
2633 EXPORT_SYMBOL(preempt_count_sub);
2634 NOKPROBE_SYMBOL(preempt_count_sub);
2635
2636 #endif
2637
2638 /*
2639  * Print scheduling while atomic bug:
2640  */
2641 static noinline void __schedule_bug(struct task_struct *prev)
2642 {
2643         if (oops_in_progress)
2644                 return;
2645
2646         printk(KERN_ERR "BUG: scheduling while atomic: %s/%d/0x%08x\n",
2647                 prev->comm, prev->pid, preempt_count());
2648
2649         debug_show_held_locks(prev);
2650         print_modules();
2651         if (irqs_disabled())
2652                 print_irqtrace_events(prev);
2653 #ifdef CONFIG_DEBUG_PREEMPT
2654         if (in_atomic_preempt_off()) {
2655                 pr_err("Preemption disabled at:");
2656                 print_ip_sym(current->preempt_disable_ip);
2657                 pr_cont("\n");
2658         }
2659 #endif
2660         dump_stack();
2661         add_taint(TAINT_WARN, LOCKDEP_STILL_OK);
2662 }
2663
2664 /*
2665  * Various schedule()-time debugging checks and statistics:
2666  */
2667 static inline void schedule_debug(struct task_struct *prev)
2668 {
2669         /*
2670          * Test if we are atomic. Since do_exit() needs to call into
2671          * schedule() atomically, we ignore that path. Otherwise whine
2672          * if we are scheduling when we should not.
2673          */
2674         if (unlikely(in_atomic_preempt_off() && prev->state != TASK_DEAD))
2675                 __schedule_bug(prev);
2676         rcu_sleep_check();
2677
2678         profile_hit(SCHED_PROFILING, __builtin_return_address(0));
2679
2680         schedstat_inc(this_rq(), sched_count);
2681 }
2682
2683 /*
2684  * Pick up the highest-prio task:
2685  */
2686 static inline struct task_struct *
2687 pick_next_task(struct rq *rq, struct task_struct *prev)
2688 {
2689         const struct sched_class *class = &fair_sched_class;
2690         struct task_struct *p;
2691
2692         /*
2693          * Optimization: we know that if all tasks are in
2694          * the fair class we can call that function directly:
2695          */
2696         if (likely(prev->sched_class == class &&
2697                    rq->nr_running == rq->cfs.h_nr_running)) {
2698                 p = fair_sched_class.pick_next_task(rq, prev);
2699                 if (unlikely(p == RETRY_TASK))
2700                         goto again;
2701
2702                 /* assumes fair_sched_class->next == idle_sched_class */
2703                 if (unlikely(!p))
2704                         p = idle_sched_class.pick_next_task(rq, prev);
2705
2706                 return p;
2707         }
2708
2709 again:
2710         for_each_class(class) {
2711                 p = class->pick_next_task(rq, prev);
2712                 if (p) {
2713                         if (unlikely(p == RETRY_TASK))
2714                                 goto again;
2715                         return p;
2716                 }
2717         }
2718
2719         BUG(); /* the idle class will always have a runnable task */
2720 }
2721
2722 /*
2723  * __schedule() is the main scheduler function.
2724  *
2725  * The main means of driving the scheduler and thus entering this function are:
2726  *
2727  *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
2728  *
2729  *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
2730  *      paths. For example, see arch/x86/entry_64.S.
2731  *
2732  *      To drive preemption between tasks, the scheduler sets the flag in timer
2733  *      interrupt handler scheduler_tick().
2734  *
2735  *   3. Wakeups don't really cause entry into schedule(). They add a
2736  *      task to the run-queue and that's it.
2737  *
2738  *      Now, if the new task added to the run-queue preempts the current
2739  *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
2740  *      called on the nearest possible occasion:
2741  *
2742  *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
2743  *
2744  *         - in syscall or exception context, at the next outmost
2745  *           preempt_enable(). (this might be as soon as the wake_up()'s
2746  *           spin_unlock()!)
2747  *
2748  *         - in IRQ context, return from interrupt-handler to
2749  *           preemptible context
2750  *
2751  *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
2752  *         then at the next:
2753  *
2754  *          - cond_resched() call
2755  *          - explicit schedule() call
2756  *          - return from syscall or exception to user-space
2757  *          - return from interrupt-handler to user-space
2758  */
2759 //void print_rb_nodes(struct rq *rq) {
2760 //      struct task_struct *p;
2761 //
2762 //      if (!rq->cfs.rb_leftmost)
2763 //              return;
2764 //
2765 //      p = pick_next_task(rq);
2766 //      if (rq->cfs.rb_leftmost)
2767 //              print_rb_nodes(rq);
2768 //      put_prev_task(rq, p);
2769 //
2770 //      printk("%i ", p->pid);
2771 //}
2772 static void __sched __schedule(void)
2773 {
2774         struct task_struct *prev, *next;
2775         unsigned long *switch_count;
2776         struct rq *rq;
2777         int i, cpu;
2778
2779 need_resched:
2780         preempt_disable();
2781         cpu = smp_processor_id();
2782         rq = cpu_rq(cpu);
2783         rcu_note_context_switch(cpu);
2784         prev = rq->curr;
2785
2786         schedule_debug(prev);
2787
2788         if (sched_feat(HRTICK))
2789                 hrtick_clear(rq);
2790
2791         /*
2792          * Make sure that signal_pending_state()->signal_pending() below
2793          * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
2794          * done by the caller to avoid the race with signal_wake_up().
2795          */
2796         smp_mb__before_spinlock();
2797         raw_spin_lock_irq(&rq->lock);
2798
2799         switch_count = &prev->nivcsw;
2800         if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
2801                 if (unlikely(signal_pending_state(prev->state, prev))) {
2802                         prev->state = TASK_RUNNING;
2803                 } else {
2804                         deactivate_task(rq, prev, DEQUEUE_SLEEP);
2805                         prev->on_rq = 0;
2806
2807                         /*
2808                          * If a worker went to sleep, notify and ask workqueue
2809                          * whether it wants to wake up a task to maintain
2810                          * concurrency.
2811                          */
2812                         if (prev->flags & PF_WQ_WORKER) {
2813                                 struct task_struct *to_wakeup;
2814
2815                                 to_wakeup = wq_worker_sleeping(prev, cpu);
2816                                 if (to_wakeup)
2817                                         try_to_wake_up_local(to_wakeup);
2818                         }
2819                 }
2820                 switch_count = &prev->nvcsw;
2821         }
2822
2823         if (prev->on_rq || rq->skip_clock_update < 0)
2824                 update_rq_clock(rq);
2825
2826         next = pick_next_task(rq, prev);
2827         clear_tsk_need_resched(prev);
2828         clear_preempt_need_resched();
2829         rq->skip_clock_update = 0;
2830
2831         if (likely(prev != next)) {
2832                 rq->nr_switches++;
2833                 rq->curr = next;
2834                 ++*switch_count;
2835
2836                 context_switch(rq, prev, next); /* unlocks the rq */
2837                 /*
2838                  * The context switch have flipped the stack from under us
2839                  * and restored the local variables which were saved when
2840                  * this task called schedule() in the past. prev == current
2841                  * is still correct, but it can be moved to another cpu/rq.
2842                  */
2843                 cpu = smp_processor_id();
2844                 rq = cpu_rq(cpu);
2845         } else
2846                 raw_spin_unlock_irq(&rq->lock);
2847
2848         post_schedule(rq);
2849
2850         sched_preempt_enable_no_resched();
2851         if (need_resched())
2852                 goto need_resched;
2853 }
2854
2855 static inline void sched_submit_work(struct task_struct *tsk)
2856 {
2857         if (!tsk->state || tsk_is_pi_blocked(tsk))
2858                 return;
2859         /*
2860          * If we are going to sleep and we have plugged IO queued,
2861          * make sure to submit it to avoid deadlocks.
2862          */
2863         if (blk_needs_flush_plug(tsk))
2864                 blk_schedule_flush_plug(tsk);
2865 }
2866
2867 asmlinkage __visible void __sched schedule(void)
2868 {
2869         struct task_struct *tsk = current;
2870
2871         sched_submit_work(tsk);
2872         __schedule();
2873 }
2874 EXPORT_SYMBOL(schedule);
2875
2876 #ifdef CONFIG_CONTEXT_TRACKING
2877 asmlinkage __visible void __sched schedule_user(void)
2878 {
2879         /*
2880          * If we come here after a random call to set_need_resched(),
2881          * or we have been woken up remotely but the IPI has not yet arrived,
2882          * we haven't yet exited the RCU idle mode. Do it here manually until
2883          * we find a better solution.
2884          */
2885         user_exit();
2886         schedule();
2887         user_enter();
2888 }
2889 #endif
2890
2891 /**
2892  * schedule_preempt_disabled - called with preemption disabled
2893  *
2894  * Returns with preemption disabled. Note: preempt_count must be 1
2895  */
2896 void __sched schedule_preempt_disabled(void)
2897 {
2898         sched_preempt_enable_no_resched();
2899         schedule();
2900         preempt_disable();
2901 }
2902
2903 #ifdef CONFIG_PREEMPT
2904 /*
2905  * this is the entry point to schedule() from in-kernel preemption
2906  * off of preempt_enable. Kernel preemptions off return from interrupt
2907  * occur there and call schedule directly.
2908  */
2909 asmlinkage __visible void __sched notrace preempt_schedule(void)
2910 {
2911         /*
2912          * If there is a non-zero preempt_count or interrupts are disabled,
2913          * we do not want to preempt the current task. Just return..
2914          */
2915         if (likely(!preemptible()))
2916                 return;
2917
2918         do {
2919                 __preempt_count_add(PREEMPT_ACTIVE);
2920                 __schedule();
2921                 __preempt_count_sub(PREEMPT_ACTIVE);
2922
2923                 /*
2924                  * Check again in case we missed a preemption opportunity
2925                  * between schedule and now.
2926                  */
2927                 barrier();
2928         } while (need_resched());
2929 }
2930 NOKPROBE_SYMBOL(preempt_schedule);
2931 EXPORT_SYMBOL(preempt_schedule);
2932 #endif /* CONFIG_PREEMPT */
2933
2934 /*
2935  * this is the entry point to schedule() from kernel preemption
2936  * off of irq context.
2937  * Note, that this is called and return with irqs disabled. This will
2938  * protect us against recursive calling from irq.
2939  */
2940 asmlinkage __visible void __sched preempt_schedule_irq(void)
2941 {
2942         enum ctx_state prev_state;
2943
2944         /* Catch callers which need to be fixed */
2945         BUG_ON(preempt_count() || !irqs_disabled());
2946
2947         prev_state = exception_enter();
2948
2949         do {
2950                 __preempt_count_add(PREEMPT_ACTIVE);
2951                 local_irq_enable();
2952                 __schedule();
2953                 local_irq_disable();
2954                 __preempt_count_sub(PREEMPT_ACTIVE);
2955
2956                 /*
2957                  * Check again in case we missed a preemption opportunity
2958                  * between schedule and now.
2959                  */
2960                 barrier();
2961         } while (need_resched());
2962
2963         exception_exit(prev_state);
2964 }
2965
2966 int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
2967                           void *key)
2968 {
2969         return try_to_wake_up(curr->private, mode, wake_flags);
2970 }
2971 EXPORT_SYMBOL(default_wake_function);
2972
2973 #ifdef CONFIG_RT_MUTEXES
2974
2975 /*
2976  * rt_mutex_setprio - set the current priority of a task
2977  * @p: task
2978  * @prio: prio value (kernel-internal form)
2979  *
2980  * This function changes the 'effective' priority of a task. It does
2981  * not touch ->normal_prio like __setscheduler().
2982  *
2983  * Used by the rt_mutex code to implement priority inheritance
2984  * logic. Call site only calls if the priority of the task changed.
2985  */
2986 void rt_mutex_setprio(struct task_struct *p, int prio)
2987 {
2988         int oldprio, on_rq, running, enqueue_flag = 0;
2989         struct rq *rq;
2990         const struct sched_class *prev_class;
2991
2992         BUG_ON(prio > MAX_PRIO);
2993
2994         rq = __task_rq_lock(p);
2995
2996         /*
2997          * Idle task boosting is a nono in general. There is one
2998          * exception, when PREEMPT_RT and NOHZ is active:
2999          *
3000          * The idle task calls get_next_timer_interrupt() and holds
3001          * the timer wheel base->lock on the CPU and another CPU wants
3002          * to access the timer (probably to cancel it). We can safely
3003          * ignore the boosting request, as the idle CPU runs this code
3004          * with interrupts disabled and will complete the lock
3005          * protected section without being interrupted. So there is no
3006          * real need to boost.
3007          */
3008         if (unlikely(p == rq->idle)) {
3009                 WARN_ON(p != rq->curr);
3010                 WARN_ON(p->pi_blocked_on);
3011                 goto out_unlock;
3012         }
3013
3014         trace_sched_pi_setprio(p, prio);
3015         oldprio = p->prio;
3016         prev_class = p->sched_class;
3017         on_rq = p->on_rq;
3018         running = task_current(rq, p);
3019         if (on_rq)
3020                 dequeue_task(rq, p, 0);
3021         if (running)
3022                 p->sched_class->put_prev_task(rq, p);
3023
3024         /*
3025          * Boosting condition are:
3026          * 1. -rt task is running and holds mutex A
3027          *      --> -dl task blocks on mutex A
3028          *
3029          * 2. -dl task is running and holds mutex A
3030          *      --> -dl task blocks on mutex A and could preempt the
3031          *          running task
3032          */
3033         if (dl_prio(prio)) {
3034                 struct task_struct *pi_task = rt_mutex_get_top_task(p);
3035                 if (!dl_prio(p->normal_prio) ||
3036                     (pi_task && dl_entity_preempt(&pi_task->dl, &p->dl))) {
3037                         p->dl.dl_boosted = 1;
3038                         p->dl.dl_throttled = 0;
3039                         enqueue_flag = ENQUEUE_REPLENISH;
3040                 } else
3041                         p->dl.dl_boosted = 0;
3042                 p->sched_class = &dl_sched_class;
3043         } else if (rt_prio(prio)) {
3044                 if (dl_prio(oldprio))
3045                         p->dl.dl_boosted = 0;
3046                 if (oldprio < prio)
3047                         enqueue_flag = ENQUEUE_HEAD;
3048                 p->sched_class = &rt_sched_class;
3049         } else {
3050                 if (dl_prio(oldprio))
3051                         p->dl.dl_boosted = 0;
3052                 p->sched_class = &fair_sched_class;
3053         }
3054
3055         p->prio = prio;
3056
3057         if (running)
3058                 p->sched_class->set_curr_task(rq);
3059         if (on_rq)
3060                 enqueue_task(rq, p, enqueue_flag);
3061
3062         check_class_changed(rq, p, prev_class, oldprio);
3063 out_unlock:
3064         __task_rq_unlock(rq);
3065 }
3066 #endif
3067
3068 void set_user_nice(struct task_struct *p, long nice)
3069 {
3070         int old_prio, delta, on_rq;
3071         unsigned long flags;
3072         struct rq *rq;
3073
3074         if (task_nice(p) == nice || nice < MIN_NICE || nice > MAX_NICE)
3075                 return;
3076         /*
3077          * We have to be careful, if called from sys_setpriority(),
3078          * the task might be in the middle of scheduling on another CPU.
3079          */
3080         rq = task_rq_lock(p, &flags);
3081         /*
3082          * The RT priorities are set via sched_setscheduler(), but we still
3083          * allow the 'normal' nice value to be set - but as expected
3084          * it wont have any effect on scheduling until the task is
3085          * SCHED_DEADLINE, SCHED_FIFO or SCHED_RR:
3086          */
3087         if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
3088                 p->static_prio = NICE_TO_PRIO(nice);
3089                 goto out_unlock;
3090         }
3091         on_rq = p->on_rq;
3092         if (on_rq)
3093                 dequeue_task(rq, p, 0);
3094
3095         p->static_prio = NICE_TO_PRIO(nice);
3096         set_load_weight(p);
3097         old_prio = p->prio;
3098         p->prio = effective_prio(p);
3099         delta = p->prio - old_prio;
3100
3101         if (on_rq) {
3102                 enqueue_task(rq, p, 0);
3103                 /*
3104                  * If the task increased its priority or is running and
3105                  * lowered its priority, then reschedule its CPU:
3106                  */
3107                 if (delta < 0 || (delta > 0 && task_running(rq, p)))
3108                         resched_curr(rq);
3109         }
3110 out_unlock:
3111         task_rq_unlock(rq, p, &flags);
3112 }
3113 EXPORT_SYMBOL(set_user_nice);
3114
3115 /*
3116  * can_nice - check if a task can reduce its nice value
3117  * @p: task
3118  * @nice: nice value
3119  */
3120 int can_nice(const struct task_struct *p, const int nice)
3121 {
3122         /* convert nice value [19,-20] to rlimit style value [1,40] */
3123         int nice_rlim = nice_to_rlimit(nice);
3124
3125         return (nice_rlim <= task_rlimit(p, RLIMIT_NICE) ||
3126                 capable(CAP_SYS_NICE));
3127 }
3128
3129 #ifdef __ARCH_WANT_SYS_NICE
3130
3131 /*
3132  * sys_nice - change the priority of the current process.
3133  * @increment: priority increment
3134  *
3135  * sys_setpriority is a more generic, but much slower function that
3136  * does similar things.
3137  */
3138 SYSCALL_DEFINE1(nice, int, increment)
3139 {
3140         long nice, retval;
3141
3142         /*
3143          * Setpriority might change our priority at the same moment.
3144          * We don't have to worry. Conceptually one call occurs first
3145          * and we have a single winner.
3146          */
3147         increment = clamp(increment, -NICE_WIDTH, NICE_WIDTH);
3148         nice = task_nice(current) + increment;
3149
3150         nice = clamp_val(nice, MIN_NICE, MAX_NICE);
3151         if (increment < 0 && !can_nice(current, nice))
3152                 return -EPERM;
3153
3154         retval = security_task_setnice(current, nice);
3155         if (retval)
3156                 return retval;
3157
3158         set_user_nice(current, nice);
3159         return 0;
3160 }
3161
3162 #endif
3163
3164 /**
3165  * task_prio - return the priority value of a given task.
3166  * @p: the task in question.
3167  *
3168  * Return: The priority value as seen by users in /proc.
3169  * RT tasks are offset by -200. Normal tasks are centered
3170  * around 0, value goes from -16 to +15.
3171  */
3172 int task_prio(const struct task_struct *p)
3173 {
3174         return p->prio - MAX_RT_PRIO;
3175 }
3176
3177 /**
3178  * idle_cpu - is a given cpu idle currently?
3179  * @cpu: the processor in question.
3180  *
3181  * Return: 1 if the CPU is currently idle. 0 otherwise.
3182  */
3183 int idle_cpu(int cpu)
3184 {
3185         struct rq *rq = cpu_rq(cpu);
3186
3187         if (rq->curr != rq->idle)
3188                 return 0;
3189
3190         if (rq->nr_running)
3191                 return 0;
3192
3193 #ifdef CONFIG_SMP
3194         if (!llist_empty(&rq->wake_list))
3195                 return 0;
3196 #endif
3197
3198         return 1;
3199 }
3200
3201 /**
3202  * idle_task - return the idle task for a given cpu.
3203  * @cpu: the processor in question.
3204  *
3205  * Return: The idle task for the cpu @cpu.
3206  */
3207 struct task_struct *idle_task(int cpu)
3208 {
3209         return cpu_rq(cpu)->idle;
3210 }
3211
3212 /**
3213  * find_process_by_pid - find a process with a matching PID value.
3214  * @pid: the pid in question.
3215  *
3216  * The task of @pid, if found. %NULL otherwise.
3217  */
3218 static struct task_struct *find_process_by_pid(pid_t pid)
3219 {
3220         return pid ? find_task_by_vpid(pid) : current;
3221 }
3222
3223 /*
3224  * This function initializes the sched_dl_entity of a newly becoming
3225  * SCHED_DEADLINE task.
3226  *
3227  * Only the static values are considered here, the actual runtime and the
3228  * absolute deadline will be properly calculated when the task is enqueued
3229  * for the first time with its new policy.
3230  */
3231 static void
3232 __setparam_dl(struct task_struct *p, const struct sched_attr *attr)
3233 {
3234         struct sched_dl_entity *dl_se = &p->dl;
3235
3236         init_dl_task_timer(dl_se);
3237         dl_se->dl_runtime = attr->sched_runtime;
3238         dl_se->dl_deadline = attr->sched_deadline;
3239         dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
3240         dl_se->flags = attr->sched_flags;
3241         dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
3242         dl_se->dl_throttled = 0;
3243         dl_se->dl_new = 1;
3244         dl_se->dl_yielded = 0;
3245 }
3246
3247 /*
3248  * sched_setparam() passes in -1 for its policy, to let the functions
3249  * it calls know not to change it.
3250  */
3251 #define SETPARAM_POLICY -1
3252
3253 static void __setscheduler_params(struct task_struct *p,
3254                 const struct sched_attr *attr)
3255 {
3256         int policy = attr->sched_policy;
3257
3258         if (policy == SETPARAM_POLICY)
3259                 policy = p->policy;
3260
3261         p->policy = policy;
3262
3263         if (dl_policy(policy))
3264                 __setparam_dl(p, attr);
3265         else if (fair_policy(policy))
3266                 p->static_prio = NICE_TO_PRIO(attr->sched_nice);
3267
3268         /*
3269          * __sched_setscheduler() ensures attr->sched_priority == 0 when
3270          * !rt_policy. Always setting this ensures that things like
3271          * getparam()/getattr() don't report silly values for !rt tasks.
3272          */
3273         p->rt_priority = attr->sched_priority;
3274         p->normal_prio = normal_prio(p);
3275         set_load_weight(p);
3276 }
3277
3278 /* Actually do priority change: must hold pi & rq lock. */
3279 static void __setscheduler(struct rq *rq, struct task_struct *p,
3280                            const struct sched_attr *attr)
3281 {
3282         __setscheduler_params(p, attr);
3283
3284         /*
3285          * If we get here, there was no pi waiters boosting the
3286          * task. It is safe to use the normal prio.
3287          */
3288         p->prio = normal_prio(p);
3289
3290         if (dl_prio(p->prio))
3291                 p->sched_class = &dl_sched_class;
3292         else if (rt_prio(p->prio))
3293                 p->sched_class = &rt_sched_class;
3294         else
3295                 p->sched_class = &fair_sched_class;
3296 }
3297
3298 static void
3299 __getparam_dl(struct task_struct *p, struct sched_attr *attr)
3300 {
3301         struct sched_dl_entity *dl_se = &p->dl;
3302
3303         attr->sched_priority = p->rt_priority;
3304         attr->sched_runtime = dl_se->dl_runtime;
3305         attr->sched_deadline = dl_se->dl_deadline;
3306         attr->sched_period = dl_se->dl_period;
3307         attr->sched_flags = dl_se->flags;
3308 }
3309
3310 /*
3311  * This function validates the new parameters of a -deadline task.
3312  * We ask for the deadline not being zero, and greater or equal
3313  * than the runtime, as well as the period of being zero or
3314  * greater than deadline. Furthermore, we have to be sure that
3315  * user parameters are above the internal resolution of 1us (we
3316  * check sched_runtime only since it is always the smaller one) and
3317  * below 2^63 ns (we have to check both sched_deadline and
3318  * sched_period, as the latter can be zero).
3319  */
3320 static bool
3321 __checkparam_dl(const struct sched_attr *attr)
3322 {
3323         /* deadline != 0 */
3324         if (attr->sched_deadline == 0)
3325                 return false;
3326
3327         /*
3328          * Since we truncate DL_SCALE bits, make sure we're at least
3329          * that big.
3330          */
3331         if (attr->sched_runtime < (1ULL << DL_SCALE))
3332                 return false;
3333
3334         /*
3335          * Since we use the MSB for wrap-around and sign issues, make
3336          * sure it's not set (mind that period can be equal to zero).
3337          */
3338         if (attr->sched_deadline & (1ULL << 63) ||
3339             attr->sched_period & (1ULL << 63))
3340                 return false;
3341
3342         /* runtime <= deadline <= period (if period != 0) */
3343         if ((attr->sched_period != 0 &&
3344              attr->sched_period < attr->sched_deadline) ||
3345             attr->sched_deadline < attr->sched_runtime)
3346                 return false;
3347
3348         return true;
3349 }
3350
3351 /*
3352  * check the target process has a UID that matches the current process's
3353  */
3354 static bool check_same_owner(struct task_struct *p)
3355 {
3356         const struct cred *cred = current_cred(), *pcred;
3357         bool match;
3358
3359         rcu_read_lock();
3360         pcred = __task_cred(p);
3361         match = (uid_eq(cred->euid, pcred->euid) ||
3362                  uid_eq(cred->euid, pcred->uid));
3363         rcu_read_unlock();
3364         return match;
3365 }
3366
3367 static int __sched_setscheduler(struct task_struct *p,
3368                                 const struct sched_attr *attr,
3369                                 bool user)
3370 {
3371         int newprio = dl_policy(attr->sched_policy) ? MAX_DL_PRIO - 1 :
3372                       MAX_RT_PRIO - 1 - attr->sched_priority;
3373         int retval, oldprio, oldpolicy = -1, on_rq, running;
3374         int policy = attr->sched_policy;
3375         unsigned long flags;
3376         const struct sched_class *prev_class;
3377         struct rq *rq;
3378         int reset_on_fork;
3379
3380         /* may grab non-irq protected spin_locks */
3381         BUG_ON(in_interrupt());
3382 recheck:
3383         /* double check policy once rq lock held */
3384         if (policy < 0) {
3385                 reset_on_fork = p->sched_reset_on_fork;
3386                 policy = oldpolicy = p->policy;
3387         } else {
3388                 reset_on_fork = !!(attr->sched_flags & SCHED_FLAG_RESET_ON_FORK);
3389
3390                 if (policy != SCHED_DEADLINE &&
3391                                 policy != SCHED_FIFO && policy != SCHED_RR &&
3392                                 policy != SCHED_NORMAL && policy != SCHED_BATCH &&
3393                                 policy != SCHED_IDLE)
3394                         return -EINVAL;
3395         }
3396
3397         if (attr->sched_flags & ~(SCHED_FLAG_RESET_ON_FORK))
3398                 return -EINVAL;
3399
3400         /*
3401          * Valid priorities for SCHED_FIFO and SCHED_RR are
3402          * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
3403          * SCHED_BATCH and SCHED_IDLE is 0.
3404          */
3405         if ((p->mm && attr->sched_priority > MAX_USER_RT_PRIO-1) ||
3406             (!p->mm && attr->sched_priority > MAX_RT_PRIO-1))
3407                 return -EINVAL;
3408         if ((dl_policy(policy) && !__checkparam_dl(attr)) ||
3409             (rt_policy(policy) != (attr->sched_priority != 0)))
3410                 return -EINVAL;
3411
3412         /*
3413          * Allow unprivileged RT tasks to decrease priority:
3414          */
3415         if (user && !capable(CAP_SYS_NICE)) {
3416                 if (fair_policy(policy)) {
3417                         if (attr->sched_nice < task_nice(p) &&
3418                             !can_nice(p, attr->sched_nice))
3419                                 return -EPERM;
3420                 }
3421
3422                 if (rt_policy(policy)) {
3423                         unsigned long rlim_rtprio =
3424                                         task_rlimit(p, RLIMIT_RTPRIO);
3425
3426                         /* can't set/change the rt policy */
3427                         if (policy != p->policy && !rlim_rtprio)
3428                                 return -EPERM;
3429
3430                         /* can't increase priority */
3431                         if (attr->sched_priority > p->rt_priority &&
3432                             attr->sched_priority > rlim_rtprio)
3433                                 return -EPERM;
3434                 }
3435
3436                  /*
3437                   * Can't set/change SCHED_DEADLINE policy at all for now
3438                   * (safest behavior); in the future we would like to allow
3439                   * unprivileged DL tasks to increase their relative deadline
3440                   * or reduce their runtime (both ways reducing utilization)
3441                   */
3442                 if (dl_policy(policy))
3443                         return -EPERM;
3444
3445                 /*
3446                  * Treat SCHED_IDLE as nice 20. Only allow a switch to
3447                  * SCHED_NORMAL if the RLIMIT_NICE would normally permit it.
3448                  */
3449                 if (p->policy == SCHED_IDLE && policy != SCHED_IDLE) {
3450                         if (!can_nice(p, task_nice(p)))
3451                                 return -EPERM;
3452                 }
3453
3454                 /* can't change other user's priorities */
3455                 if (!check_same_owner(p))
3456                         return -EPERM;
3457
3458                 /* Normal users shall not reset the sched_reset_on_fork flag */
3459                 if (p->sched_reset_on_fork && !reset_on_fork)
3460                         return -EPERM;
3461         }
3462
3463         if (user) {
3464                 retval = security_task_setscheduler(p);
3465                 if (retval)
3466                         return retval;
3467         }
3468
3469         /*
3470          * make sure no PI-waiters arrive (or leave) while we are
3471          * changing the priority of the task:
3472          *
3473          * To be able to change p->policy safely, the appropriate
3474          * runqueue lock must be held.
3475          */
3476         rq = task_rq_lock(p, &flags);
3477
3478         /*
3479          * Changing the policy of the stop threads its a very bad idea
3480          */
3481         if (p == rq->stop) {
3482                 task_rq_unlock(rq, p, &flags);
3483                 return -EINVAL;
3484         }
3485
3486         /*
3487          * If not changing anything there's no need to proceed further,
3488          * but store a possible modification of reset_on_fork.
3489          */
3490         if (unlikely(policy == p->policy)) {
3491                 if (fair_policy(policy) && attr->sched_nice != task_nice(p))
3492                         goto change;
3493                 if (rt_policy(policy) && attr->sched_priority != p->rt_priority)
3494                         goto change;
3495                 if (dl_policy(policy))
3496                         goto change;
3497
3498                 p->sched_reset_on_fork = reset_on_fork;
3499                 task_rq_unlock(rq, p, &flags);
3500                 return 0;
3501         }
3502 change:
3503
3504         if (user) {
3505 #ifdef CONFIG_RT_GROUP_SCHED
3506                 /*
3507                  * Do not allow realtime tasks into groups that have no runtime
3508                  * assigned.
3509                  */
3510                 if (rt_bandwidth_enabled() && rt_policy(policy) &&
3511                                 task_group(p)->rt_bandwidth.rt_runtime == 0 &&
3512                                 !task_group_is_autogroup(task_group(p))) {
3513                         task_rq_unlock(rq, p, &flags);
3514                         return -EPERM;
3515                 }
3516 #endif
3517 #ifdef CONFIG_SMP
3518                 if (dl_bandwidth_enabled() && dl_policy(policy)) {
3519                         cpumask_t *span = rq->rd->span;
3520
3521                         /*
3522                          * Don't allow tasks with an affinity mask smaller than
3523                          * the entire root_domain to become SCHED_DEADLINE. We
3524                          * will also fail if there's no bandwidth available.
3525                          */
3526                         if (!cpumask_subset(span, &p->cpus_allowed) ||
3527                             rq->rd->dl_bw.bw == 0) {
3528                                 task_rq_unlock(rq, p, &flags);
3529                                 return -EPERM;
3530                         }
3531                 }
3532 #endif
3533         }
3534
3535         /* recheck policy now with rq lock held */
3536         if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
3537                 policy = oldpolicy = -1;
3538                 task_rq_unlock(rq, p, &flags);
3539                 goto recheck;
3540         }
3541
3542         /*
3543          * If setscheduling to SCHED_DEADLINE (or changing the parameters
3544          * of a SCHED_DEADLINE task) we need to check if enough bandwidth
3545          * is available.
3546          */
3547         if ((dl_policy(policy) || dl_task(p)) && dl_overflow(p, policy, attr)) {
3548                 task_rq_unlock(rq, p, &flags);
3549                 return -EBUSY;
3550         }
3551
3552         p->sched_reset_on_fork = reset_on_fork;
3553         oldprio = p->prio;
3554
3555         /*
3556          * Special case for priority boosted tasks.
3557          *
3558          * If the new priority is lower or equal (user space view)
3559          * than the current (boosted) priority, we just store the new
3560          * normal parameters and do not touch the scheduler class and
3561          * the runqueue. This will be done when the task deboost
3562          * itself.
3563          */
3564         if (rt_mutex_check_prio(p, newprio)) {
3565                 __setscheduler_params(p, attr);
3566                 task_rq_unlock(rq, p, &flags);
3567                 return 0;
3568         }
3569
3570         on_rq = p->on_rq;
3571         running = task_current(rq, p);
3572         if (on_rq)
3573                 dequeue_task(rq, p, 0);
3574         if (running)
3575                 p->sched_class->put_prev_task(rq, p);
3576
3577         prev_class = p->sched_class;
3578         __setscheduler(rq, p, attr);
3579
3580         if (running)
3581                 p->sched_class->set_curr_task(rq);
3582         if (on_rq) {
3583                 /*
3584                  * We enqueue to tail when the priority of a task is
3585                  * increased (user space view).
3586                  */
3587                 enqueue_task(rq, p, oldprio <= p->prio ? ENQUEUE_HEAD : 0);
3588         }
3589
3590         check_class_changed(rq, p, prev_class, oldprio);
3591         task_rq_unlock(rq, p, &flags);
3592
3593         rt_mutex_adjust_pi(p);
3594
3595         return 0;
3596 }
3597
3598 static int _sched_setscheduler(struct task_struct *p, int policy,
3599                                const struct sched_param *param, bool check)
3600 {
3601         struct sched_attr attr = {
3602                 .sched_policy   = policy,
3603                 .sched_priority = param->sched_priority,
3604                 .sched_nice     = PRIO_TO_NICE(p->static_prio),
3605         };
3606
3607         /* Fixup the legacy SCHED_RESET_ON_FORK hack. */
3608         if ((policy != SETPARAM_POLICY) && (policy & SCHED_RESET_ON_FORK)) {
3609                 attr.sched_flags |= SCHED_FLAG_RESET_ON_FORK;
3610                 policy &= ~SCHED_RESET_ON_FORK;
3611                 attr.sched_policy = policy;
3612         }
3613
3614         return __sched_setscheduler(p, &attr, check);
3615 }
3616 /**
3617  * sched_setscheduler - change the scheduling policy and/or RT priority of a thread.
3618  * @p: the task in question.
3619  * @policy: new policy.
3620  * @param: structure containing the new RT priority.
3621  *
3622  * Return: 0 on success. An error code otherwise.
3623  *
3624  * NOTE that the task may be already dead.
3625  */
3626 int sched_setscheduler(struct task_struct *p, int policy,
3627                        const struct sched_param *param)
3628 {
3629         return _sched_setscheduler(p, policy, param, true);
3630 }
3631 EXPORT_SYMBOL_GPL(sched_setscheduler);
3632
3633 int sched_setattr(struct task_struct *p, const struct sched_attr *attr)
3634 {
3635         return __sched_setscheduler(p, attr, true);
3636 }
3637 EXPORT_SYMBOL_GPL(sched_setattr);
3638
3639 /**
3640  * sched_setscheduler_nocheck - change the scheduling policy and/or RT priority of a thread from kernelspace.
3641  * @p: the task in question.
3642  * @policy: new policy.
3643  * @param: structure containing the new RT priority.
3644  *
3645  * Just like sched_setscheduler, only don't bother checking if the
3646  * current context has permission.  For example, this is needed in
3647  * stop_machine(): we create temporary high priority worker threads,
3648  * but our caller might not have that capability.
3649  *
3650  * Return: 0 on success. An error code otherwise.
3651  */
3652 int sched_setscheduler_nocheck(struct task_struct *p, int policy,
3653                                const struct sched_param *param)
3654 {
3655         return _sched_setscheduler(p, policy, param, false);
3656 }
3657
3658 static int
3659 do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
3660 {
3661         struct sched_param lparam;
3662         struct task_struct *p;
3663         int retval;
3664
3665         if (!param || pid < 0)
3666                 return -EINVAL;
3667         if (copy_from_user(&lparam, param, sizeof(struct sched_param)))
3668                 return -EFAULT;
3669
3670         rcu_read_lock();
3671         retval = -ESRCH;
3672         p = find_process_by_pid(pid);
3673         if (p != NULL)
3674                 retval = sched_setscheduler(p, policy, &lparam);
3675         rcu_read_unlock();
3676
3677         return retval;
3678 }
3679
3680 /*
3681  * Mimics kernel/events/core.c perf_copy_attr().
3682  */
3683 static int sched_copy_attr(struct sched_attr __user *uattr,
3684                            struct sched_attr *attr)
3685 {
3686         u32 size;
3687         int ret;
3688
3689         if (!access_ok(VERIFY_WRITE, uattr, SCHED_ATTR_SIZE_VER0))
3690                 return -EFAULT;
3691
3692         /*
3693          * zero the full structure, so that a short copy will be nice.
3694          */
3695         memset(attr, 0, sizeof(*attr));
3696
3697         ret = get_user(size, &uattr->size);
3698         if (ret)
3699                 return ret;
3700
3701         if (size > PAGE_SIZE)   /* silly large */
3702                 goto err_size;
3703
3704         if (!size)              /* abi compat */
3705                 size = SCHED_ATTR_SIZE_VER0;
3706
3707         if (size < SCHED_ATTR_SIZE_VER0)
3708                 goto err_size;
3709
3710         /*
3711          * If we're handed a bigger struct than we know of,
3712          * ensure all the unknown bits are 0 - i.e. new
3713          * user-space does not rely on any kernel feature
3714          * extensions we dont know about yet.
3715          */
3716         if (size > sizeof(*attr)) {
3717                 unsigned char __user *addr;
3718                 unsigned char __user *end;
3719                 unsigned char val;
3720
3721                 addr = (void __user *)uattr + sizeof(*attr);
3722                 end  = (void __user *)uattr + size;
3723
3724                 for (; addr < end; addr++) {
3725                         ret = get_user(val, addr);
3726                         if (ret)
3727                                 return ret;
3728                         if (val)
3729                                 goto err_size;
3730                 }
3731                 size = sizeof(*attr);
3732         }
3733
3734         ret = copy_from_user(attr, uattr, size);
3735         if (ret)
3736                 return -EFAULT;
3737
3738         /*
3739          * XXX: do we want to be lenient like existing syscalls; or do we want
3740          * to be strict and return an error on out-of-bounds values?
3741          */
3742         attr->sched_nice = clamp(attr->sched_nice, MIN_NICE, MAX_NICE);
3743
3744         return 0;
3745
3746 err_size:
3747         put_user(sizeof(*attr), &uattr->size);
3748         return -E2BIG;
3749 }
3750
3751 /**
3752  * sys_sched_setscheduler - set/change the scheduler policy and RT priority
3753  * @pid: the pid in question.
3754  * @policy: new policy.
3755  * @param: structure containing the new RT priority.
3756  *
3757  * Return: 0 on success. An error code otherwise.
3758  */
3759 SYSCALL_DEFINE3(sched_setscheduler, pid_t, pid, int, policy,
3760                 struct sched_param __user *, param)
3761 {
3762         /* negative values for policy are not valid */
3763         if (policy < 0)
3764                 return -EINVAL;
3765
3766         return do_sched_setscheduler(pid, policy, param);
3767 }
3768
3769 /**
3770  * sys_sched_setparam - set/change the RT priority of a thread
3771  * @pid: the pid in question.
3772  * @param: structure containing the new RT priority.
3773  *
3774  * Return: 0 on success. An error code otherwise.
3775  */
3776 SYSCALL_DEFINE2(sched_setparam, pid_t, pid, struct sched_param __user *, param)
3777 {
3778         return do_sched_setscheduler(pid, SETPARAM_POLICY, param);
3779 }
3780
3781 /**
3782  * sys_sched_setattr - same as above, but with extended sched_attr
3783  * @pid: the pid in question.
3784  * @uattr: structure containing the extended parameters.
3785  * @flags: for future extension.
3786  */
3787 SYSCALL_DEFINE3(sched_setattr, pid_t, pid, struct sched_attr __user *, uattr,
3788                                unsigned int, flags)
3789 {
3790         struct sched_attr attr;
3791         struct task_struct *p;
3792         int retval;
3793
3794         if (!uattr || pid < 0 || flags)
3795                 return -EINVAL;
3796
3797         retval = sched_copy_attr(uattr, &attr);
3798         if (retval)
3799                 return retval;
3800
3801         if ((int)attr.sched_policy < 0)
3802                 return -EINVAL;
3803
3804         rcu_read_lock();
3805         retval = -ESRCH;
3806         p = find_process_by_pid(pid);
3807         if (p != NULL)
3808                 retval = sched_setattr(p, &attr);
3809         rcu_read_unlock();
3810
3811         return retval;
3812 }
3813
3814 /**
3815  * sys_sched_getscheduler - get the policy (scheduling class) of a thread
3816  * @pid: the pid in question.
3817  *
3818  * Return: On success, the policy of the thread. Otherwise, a negative error
3819  * code.
3820  */
3821 SYSCALL_DEFINE1(sched_getscheduler, pid_t, pid)
3822 {
3823         struct task_struct *p;
3824         int retval;
3825
3826         if (pid < 0)
3827                 return -EINVAL;
3828
3829         retval = -ESRCH;
3830         rcu_read_lock();
3831         p = find_process_by_pid(pid);
3832         if (p) {
3833                 retval = security_task_getscheduler(p);
3834                 if (!retval)
3835                         retval = p->policy
3836                                 | (p->sched_reset_on_fork ? SCHED_RESET_ON_FORK : 0);
3837         }
3838         rcu_read_unlock();
3839         return retval;
3840 }
3841
3842 /**
3843  * sys_sched_getparam - get the RT priority of a thread
3844  * @pid: the pid in question.
3845  * @param: structure containing the RT priority.
3846  *
3847  * Return: On success, 0 and the RT priority is in @param. Otherwise, an error
3848  * code.
3849  */
3850 SYSCALL_DEFINE2(sched_getparam, pid_t, pid, struct sched_param __user *, param)
3851 {
3852         struct sched_param lp = { .sched_priority = 0 };
3853         struct task_struct *p;
3854         int retval;
3855
3856         if (!param || pid < 0)
3857                 return -EINVAL;
3858
3859         rcu_read_lock();
3860         p = find_process_by_pid(pid);
3861         retval = -ESRCH;
3862         if (!p)
3863                 goto out_unlock;
3864
3865         retval = security_task_getscheduler(p);
3866         if (retval)
3867                 goto out_unlock;
3868
3869         if (task_has_rt_policy(p))
3870                 lp.sched_priority = p->rt_priority;
3871         rcu_read_unlock();
3872
3873         /*
3874          * This one might sleep, we cannot do it with a spinlock held ...
3875          */
3876         retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
3877
3878         return retval;
3879
3880 out_unlock:
3881         rcu_read_unlock();
3882         return retval;
3883 }
3884
3885 static int sched_read_attr(struct sched_attr __user *uattr,
3886                            struct sched_attr *attr,
3887                            unsigned int usize)
3888 {
3889         int ret;
3890
3891         if (!access_ok(VERIFY_WRITE, uattr, usize))
3892                 return -EFAULT;
3893
3894         /*
3895          * If we're handed a smaller struct than we know of,
3896          * ensure all the unknown bits are 0 - i.e. old
3897          * user-space does not get uncomplete information.
3898          */
3899         if (usize < sizeof(*attr)) {
3900                 unsigned char *addr;
3901                 unsigned char *end;
3902
3903                 addr = (void *)attr + usize;
3904                 end  = (void *)attr + sizeof(*attr);
3905
3906                 for (; addr < end; addr++) {
3907                         if (*addr)
3908                                 return -EFBIG;
3909                 }
3910
3911                 attr->size = usize;
3912         }
3913
3914         ret = copy_to_user(uattr, attr, attr->size);
3915         if (ret)
3916                 return -EFAULT;
3917
3918         return 0;
3919 }
3920
3921 /**
3922  * sys_sched_getattr - similar to sched_getparam, but with sched_attr
3923  * @pid: the pid in question.
3924  * @uattr: structure containing the extended parameters.
3925  * @size: sizeof(attr) for fwd/bwd comp.
3926  * @flags: for future extension.
3927  */
3928 SYSCALL_DEFINE4(sched_getattr, pid_t, pid, struct sched_attr __user *, uattr,
3929                 unsigned int, size, unsigned int, flags)
3930 {
3931         struct sched_attr attr = {
3932                 .size = sizeof(struct sched_attr),
3933         };
3934         struct task_struct *p;
3935         int retval;
3936
3937         if (!uattr || pid < 0 || size > PAGE_SIZE ||
3938             size < SCHED_ATTR_SIZE_VER0 || flags)
3939                 return -EINVAL;
3940
3941         rcu_read_lock();
3942         p = find_process_by_pid(pid);
3943         retval = -ESRCH;
3944         if (!p)
3945                 goto out_unlock;
3946
3947         retval = security_task_getscheduler(p);
3948         if (retval)
3949                 goto out_unlock;
3950
3951         attr.sched_policy = p->policy;
3952         if (p->sched_reset_on_fork)
3953                 attr.sched_flags |= SCHED_FLAG_RESET_ON_FORK;
3954         if (task_has_dl_policy(p))
3955                 __getparam_dl(p, &attr);
3956         else if (task_has_rt_policy(p))
3957                 attr.sched_priority = p->rt_priority;
3958         else
3959                 attr.sched_nice = task_nice(p);
3960
3961         rcu_read_unlock();
3962
3963         retval = sched_read_attr(uattr, &attr, size);
3964         return retval;
3965
3966 out_unlock:
3967         rcu_read_unlock();
3968         return retval;
3969 }
3970
3971 long sched_setaffinity(pid_t pid, const struct cpumask *in_mask)
3972 {
3973         cpumask_var_t cpus_allowed, new_mask;
3974         struct task_struct *p;
3975         int retval;
3976
3977         rcu_read_lock();
3978
3979         p = find_process_by_pid(pid);
3980         if (!p) {
3981                 rcu_read_unlock();
3982                 return -ESRCH;
3983         }
3984
3985         /* Prevent p going away */
3986         get_task_struct(p);
3987         rcu_read_unlock();
3988
3989         if (p->flags & PF_NO_SETAFFINITY) {
3990                 retval = -EINVAL;
3991                 goto out_put_task;
3992         }
3993         if (!alloc_cpumask_var(&cpus_allowed, GFP_KERNEL)) {
3994                 retval = -ENOMEM;
3995                 goto out_put_task;
3996         }
3997         if (!alloc_cpumask_var(&new_mask, GFP_KERNEL)) {
3998                 retval = -ENOMEM;
3999                 goto out_free_cpus_allowed;
4000         }
4001         retval = -EPERM;
4002         if (!check_same_owner(p)) {
4003                 rcu_read_lock();
4004                 if (!ns_capable(__task_cred(p)->user_ns, CAP_SYS_NICE)) {
4005                         rcu_read_unlock();
4006                         goto out_unlock;
4007                 }
4008                 rcu_read_unlock();
4009         }
4010
4011         retval = security_task_setscheduler(p);
4012         if (retval)
4013                 goto out_unlock;
4014
4015
4016         cpuset_cpus_allowed(p, cpus_allowed);
4017         cpumask_and(new_mask, in_mask, cpus_allowed);
4018
4019         /*
4020          * Since bandwidth control happens on root_domain basis,
4021          * if admission test is enabled, we only admit -deadline
4022          * tasks allowed to run on all the CPUs in the task's
4023          * root_domain.
4024          */
4025 #ifdef CONFIG_SMP
4026         if (task_has_dl_policy(p)) {
4027                 const struct cpumask *span = task_rq(p)->rd->span;
4028
4029                 if (dl_bandwidth_enabled() && !cpumask_subset(span, new_mask)) {
4030                         retval = -EBUSY;
4031                         goto out_unlock;
4032                 }
4033         }
4034 #endif
4035 again:
4036         retval = set_cpus_allowed_ptr(p, new_mask);
4037
4038         if (!retval) {
4039                 cpuset_cpus_allowed(p, cpus_allowed);
4040                 if (!cpumask_subset(new_mask, cpus_allowed)) {
4041                         /*
4042                          * We must have raced with a concurrent cpuset
4043                          * update. Just reset the cpus_allowed to the
4044       &nb