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