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