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