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