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