Linux 6.7-rc7
[linux-modified.git] / kernel / sched / sched.h
1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3  * Scheduler internal types and methods:
4  */
5 #ifndef _KERNEL_SCHED_SCHED_H
6 #define _KERNEL_SCHED_SCHED_H
7
8 #include <linux/sched/affinity.h>
9 #include <linux/sched/autogroup.h>
10 #include <linux/sched/cpufreq.h>
11 #include <linux/sched/deadline.h>
12 #include <linux/sched.h>
13 #include <linux/sched/loadavg.h>
14 #include <linux/sched/mm.h>
15 #include <linux/sched/rseq_api.h>
16 #include <linux/sched/signal.h>
17 #include <linux/sched/smt.h>
18 #include <linux/sched/stat.h>
19 #include <linux/sched/sysctl.h>
20 #include <linux/sched/task_flags.h>
21 #include <linux/sched/task.h>
22 #include <linux/sched/topology.h>
23
24 #include <linux/atomic.h>
25 #include <linux/bitmap.h>
26 #include <linux/bug.h>
27 #include <linux/capability.h>
28 #include <linux/cgroup_api.h>
29 #include <linux/cgroup.h>
30 #include <linux/context_tracking.h>
31 #include <linux/cpufreq.h>
32 #include <linux/cpumask_api.h>
33 #include <linux/ctype.h>
34 #include <linux/file.h>
35 #include <linux/fs_api.h>
36 #include <linux/hrtimer_api.h>
37 #include <linux/interrupt.h>
38 #include <linux/irq_work.h>
39 #include <linux/jiffies.h>
40 #include <linux/kref_api.h>
41 #include <linux/kthread.h>
42 #include <linux/ktime_api.h>
43 #include <linux/lockdep_api.h>
44 #include <linux/lockdep.h>
45 #include <linux/minmax.h>
46 #include <linux/mm.h>
47 #include <linux/module.h>
48 #include <linux/mutex_api.h>
49 #include <linux/plist.h>
50 #include <linux/poll.h>
51 #include <linux/proc_fs.h>
52 #include <linux/profile.h>
53 #include <linux/psi.h>
54 #include <linux/rcupdate.h>
55 #include <linux/seq_file.h>
56 #include <linux/seqlock.h>
57 #include <linux/softirq.h>
58 #include <linux/spinlock_api.h>
59 #include <linux/static_key.h>
60 #include <linux/stop_machine.h>
61 #include <linux/syscalls_api.h>
62 #include <linux/syscalls.h>
63 #include <linux/tick.h>
64 #include <linux/topology.h>
65 #include <linux/types.h>
66 #include <linux/u64_stats_sync_api.h>
67 #include <linux/uaccess.h>
68 #include <linux/wait_api.h>
69 #include <linux/wait_bit.h>
70 #include <linux/workqueue_api.h>
71
72 #include <trace/events/power.h>
73 #include <trace/events/sched.h>
74
75 #include "../workqueue_internal.h"
76
77 #ifdef CONFIG_PARAVIRT
78 # include <asm/paravirt.h>
79 # include <asm/paravirt_api_clock.h>
80 #endif
81
82 #include "cpupri.h"
83 #include "cpudeadline.h"
84
85 #ifdef CONFIG_SCHED_DEBUG
86 # define SCHED_WARN_ON(x)      WARN_ONCE(x, #x)
87 #else
88 # define SCHED_WARN_ON(x)      ({ (void)(x), 0; })
89 #endif
90
91 struct rq;
92 struct cpuidle_state;
93
94 /* task_struct::on_rq states: */
95 #define TASK_ON_RQ_QUEUED       1
96 #define TASK_ON_RQ_MIGRATING    2
97
98 extern __read_mostly int scheduler_running;
99
100 extern unsigned long calc_load_update;
101 extern atomic_long_t calc_load_tasks;
102
103 extern void calc_global_load_tick(struct rq *this_rq);
104 extern long calc_load_fold_active(struct rq *this_rq, long adjust);
105
106 extern void call_trace_sched_update_nr_running(struct rq *rq, int count);
107
108 extern int sysctl_sched_rt_period;
109 extern int sysctl_sched_rt_runtime;
110 extern int sched_rr_timeslice;
111
112 /*
113  * Helpers for converting nanosecond timing to jiffy resolution
114  */
115 #define NS_TO_JIFFIES(TIME)     ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))
116
117 /*
118  * Increase resolution of nice-level calculations for 64-bit architectures.
119  * The extra resolution improves shares distribution and load balancing of
120  * low-weight task groups (eg. nice +19 on an autogroup), deeper taskgroup
121  * hierarchies, especially on larger systems. This is not a user-visible change
122  * and does not change the user-interface for setting shares/weights.
123  *
124  * We increase resolution only if we have enough bits to allow this increased
125  * resolution (i.e. 64-bit). The costs for increasing resolution when 32-bit
126  * are pretty high and the returns do not justify the increased costs.
127  *
128  * Really only required when CONFIG_FAIR_GROUP_SCHED=y is also set, but to
129  * increase coverage and consistency always enable it on 64-bit platforms.
130  */
131 #ifdef CONFIG_64BIT
132 # define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT)
133 # define scale_load(w)          ((w) << SCHED_FIXEDPOINT_SHIFT)
134 # define scale_load_down(w) \
135 ({ \
136         unsigned long __w = (w); \
137         if (__w) \
138                 __w = max(2UL, __w >> SCHED_FIXEDPOINT_SHIFT); \
139         __w; \
140 })
141 #else
142 # define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT)
143 # define scale_load(w)          (w)
144 # define scale_load_down(w)     (w)
145 #endif
146
147 /*
148  * Task weight (visible to users) and its load (invisible to users) have
149  * independent resolution, but they should be well calibrated. We use
150  * scale_load() and scale_load_down(w) to convert between them. The
151  * following must be true:
152  *
153  *  scale_load(sched_prio_to_weight[NICE_TO_PRIO(0)-MAX_RT_PRIO]) == NICE_0_LOAD
154  *
155  */
156 #define NICE_0_LOAD             (1L << NICE_0_LOAD_SHIFT)
157
158 /*
159  * Single value that decides SCHED_DEADLINE internal math precision.
160  * 10 -> just above 1us
161  * 9  -> just above 0.5us
162  */
163 #define DL_SCALE                10
164
165 /*
166  * Single value that denotes runtime == period, ie unlimited time.
167  */
168 #define RUNTIME_INF             ((u64)~0ULL)
169
170 static inline int idle_policy(int policy)
171 {
172         return policy == SCHED_IDLE;
173 }
174 static inline int fair_policy(int policy)
175 {
176         return policy == SCHED_NORMAL || policy == SCHED_BATCH;
177 }
178
179 static inline int rt_policy(int policy)
180 {
181         return policy == SCHED_FIFO || policy == SCHED_RR;
182 }
183
184 static inline int dl_policy(int policy)
185 {
186         return policy == SCHED_DEADLINE;
187 }
188 static inline bool valid_policy(int policy)
189 {
190         return idle_policy(policy) || fair_policy(policy) ||
191                 rt_policy(policy) || dl_policy(policy);
192 }
193
194 static inline int task_has_idle_policy(struct task_struct *p)
195 {
196         return idle_policy(p->policy);
197 }
198
199 static inline int task_has_rt_policy(struct task_struct *p)
200 {
201         return rt_policy(p->policy);
202 }
203
204 static inline int task_has_dl_policy(struct task_struct *p)
205 {
206         return dl_policy(p->policy);
207 }
208
209 #define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
210
211 static inline void update_avg(u64 *avg, u64 sample)
212 {
213         s64 diff = sample - *avg;
214         *avg += diff / 8;
215 }
216
217 /*
218  * Shifting a value by an exponent greater *or equal* to the size of said value
219  * is UB; cap at size-1.
220  */
221 #define shr_bound(val, shift)                                                   \
222         (val >> min_t(typeof(shift), shift, BITS_PER_TYPE(typeof(val)) - 1))
223
224 /*
225  * !! For sched_setattr_nocheck() (kernel) only !!
226  *
227  * This is actually gross. :(
228  *
229  * It is used to make schedutil kworker(s) higher priority than SCHED_DEADLINE
230  * tasks, but still be able to sleep. We need this on platforms that cannot
231  * atomically change clock frequency. Remove once fast switching will be
232  * available on such platforms.
233  *
234  * SUGOV stands for SchedUtil GOVernor.
235  */
236 #define SCHED_FLAG_SUGOV        0x10000000
237
238 #define SCHED_DL_FLAGS (SCHED_FLAG_RECLAIM | SCHED_FLAG_DL_OVERRUN | SCHED_FLAG_SUGOV)
239
240 static inline bool dl_entity_is_special(const struct sched_dl_entity *dl_se)
241 {
242 #ifdef CONFIG_CPU_FREQ_GOV_SCHEDUTIL
243         return unlikely(dl_se->flags & SCHED_FLAG_SUGOV);
244 #else
245         return false;
246 #endif
247 }
248
249 /*
250  * Tells if entity @a should preempt entity @b.
251  */
252 static inline bool dl_entity_preempt(const struct sched_dl_entity *a,
253                                      const struct sched_dl_entity *b)
254 {
255         return dl_entity_is_special(a) ||
256                dl_time_before(a->deadline, b->deadline);
257 }
258
259 /*
260  * This is the priority-queue data structure of the RT scheduling class:
261  */
262 struct rt_prio_array {
263         DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
264         struct list_head queue[MAX_RT_PRIO];
265 };
266
267 struct rt_bandwidth {
268         /* nests inside the rq lock: */
269         raw_spinlock_t          rt_runtime_lock;
270         ktime_t                 rt_period;
271         u64                     rt_runtime;
272         struct hrtimer          rt_period_timer;
273         unsigned int            rt_period_active;
274 };
275
276 void __dl_clear_params(struct task_struct *p);
277
278 static inline int dl_bandwidth_enabled(void)
279 {
280         return sysctl_sched_rt_runtime >= 0;
281 }
282
283 /*
284  * To keep the bandwidth of -deadline tasks under control
285  * we need some place where:
286  *  - store the maximum -deadline bandwidth of each cpu;
287  *  - cache the fraction of bandwidth that is currently allocated in
288  *    each root domain;
289  *
290  * This is all done in the data structure below. It is similar to the
291  * one used for RT-throttling (rt_bandwidth), with the main difference
292  * that, since here we are only interested in admission control, we
293  * do not decrease any runtime while the group "executes", neither we
294  * need a timer to replenish it.
295  *
296  * With respect to SMP, bandwidth is given on a per root domain basis,
297  * meaning that:
298  *  - bw (< 100%) is the deadline bandwidth of each CPU;
299  *  - total_bw is the currently allocated bandwidth in each root domain;
300  */
301 struct dl_bw {
302         raw_spinlock_t          lock;
303         u64                     bw;
304         u64                     total_bw;
305 };
306
307 extern void init_dl_bw(struct dl_bw *dl_b);
308 extern int  sched_dl_global_validate(void);
309 extern void sched_dl_do_global(void);
310 extern int  sched_dl_overflow(struct task_struct *p, int policy, const struct sched_attr *attr);
311 extern void __setparam_dl(struct task_struct *p, const struct sched_attr *attr);
312 extern void __getparam_dl(struct task_struct *p, struct sched_attr *attr);
313 extern bool __checkparam_dl(const struct sched_attr *attr);
314 extern bool dl_param_changed(struct task_struct *p, const struct sched_attr *attr);
315 extern int  dl_cpuset_cpumask_can_shrink(const struct cpumask *cur, const struct cpumask *trial);
316 extern int  dl_bw_check_overflow(int cpu);
317
318 #ifdef CONFIG_CGROUP_SCHED
319
320 struct cfs_rq;
321 struct rt_rq;
322
323 extern struct list_head task_groups;
324
325 struct cfs_bandwidth {
326 #ifdef CONFIG_CFS_BANDWIDTH
327         raw_spinlock_t          lock;
328         ktime_t                 period;
329         u64                     quota;
330         u64                     runtime;
331         u64                     burst;
332         u64                     runtime_snap;
333         s64                     hierarchical_quota;
334
335         u8                      idle;
336         u8                      period_active;
337         u8                      slack_started;
338         struct hrtimer          period_timer;
339         struct hrtimer          slack_timer;
340         struct list_head        throttled_cfs_rq;
341
342         /* Statistics: */
343         int                     nr_periods;
344         int                     nr_throttled;
345         int                     nr_burst;
346         u64                     throttled_time;
347         u64                     burst_time;
348 #endif
349 };
350
351 /* Task group related information */
352 struct task_group {
353         struct cgroup_subsys_state css;
354
355 #ifdef CONFIG_FAIR_GROUP_SCHED
356         /* schedulable entities of this group on each CPU */
357         struct sched_entity     **se;
358         /* runqueue "owned" by this group on each CPU */
359         struct cfs_rq           **cfs_rq;
360         unsigned long           shares;
361
362         /* A positive value indicates that this is a SCHED_IDLE group. */
363         int                     idle;
364
365 #ifdef  CONFIG_SMP
366         /*
367          * load_avg can be heavily contended at clock tick time, so put
368          * it in its own cacheline separated from the fields above which
369          * will also be accessed at each tick.
370          */
371         atomic_long_t           load_avg ____cacheline_aligned;
372 #endif
373 #endif
374
375 #ifdef CONFIG_RT_GROUP_SCHED
376         struct sched_rt_entity  **rt_se;
377         struct rt_rq            **rt_rq;
378
379         struct rt_bandwidth     rt_bandwidth;
380 #endif
381
382         struct rcu_head         rcu;
383         struct list_head        list;
384
385         struct task_group       *parent;
386         struct list_head        siblings;
387         struct list_head        children;
388
389 #ifdef CONFIG_SCHED_AUTOGROUP
390         struct autogroup        *autogroup;
391 #endif
392
393         struct cfs_bandwidth    cfs_bandwidth;
394
395 #ifdef CONFIG_UCLAMP_TASK_GROUP
396         /* The two decimal precision [%] value requested from user-space */
397         unsigned int            uclamp_pct[UCLAMP_CNT];
398         /* Clamp values requested for a task group */
399         struct uclamp_se        uclamp_req[UCLAMP_CNT];
400         /* Effective clamp values used for a task group */
401         struct uclamp_se        uclamp[UCLAMP_CNT];
402 #endif
403
404 };
405
406 #ifdef CONFIG_FAIR_GROUP_SCHED
407 #define ROOT_TASK_GROUP_LOAD    NICE_0_LOAD
408
409 /*
410  * A weight of 0 or 1 can cause arithmetics problems.
411  * A weight of a cfs_rq is the sum of weights of which entities
412  * are queued on this cfs_rq, so a weight of a entity should not be
413  * too large, so as the shares value of a task group.
414  * (The default weight is 1024 - so there's no practical
415  *  limitation from this.)
416  */
417 #define MIN_SHARES              (1UL <<  1)
418 #define MAX_SHARES              (1UL << 18)
419 #endif
420
421 typedef int (*tg_visitor)(struct task_group *, void *);
422
423 extern int walk_tg_tree_from(struct task_group *from,
424                              tg_visitor down, tg_visitor up, void *data);
425
426 /*
427  * Iterate the full tree, calling @down when first entering a node and @up when
428  * leaving it for the final time.
429  *
430  * Caller must hold rcu_lock or sufficient equivalent.
431  */
432 static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data)
433 {
434         return walk_tg_tree_from(&root_task_group, down, up, data);
435 }
436
437 extern int tg_nop(struct task_group *tg, void *data);
438
439 extern void free_fair_sched_group(struct task_group *tg);
440 extern int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent);
441 extern void online_fair_sched_group(struct task_group *tg);
442 extern void unregister_fair_sched_group(struct task_group *tg);
443 extern void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
444                         struct sched_entity *se, int cpu,
445                         struct sched_entity *parent);
446 extern void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b, struct cfs_bandwidth *parent);
447
448 extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b);
449 extern void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
450 extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq);
451 extern bool cfs_task_bw_constrained(struct task_struct *p);
452
453 extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
454                 struct sched_rt_entity *rt_se, int cpu,
455                 struct sched_rt_entity *parent);
456 extern int sched_group_set_rt_runtime(struct task_group *tg, long rt_runtime_us);
457 extern int sched_group_set_rt_period(struct task_group *tg, u64 rt_period_us);
458 extern long sched_group_rt_runtime(struct task_group *tg);
459 extern long sched_group_rt_period(struct task_group *tg);
460 extern int sched_rt_can_attach(struct task_group *tg, struct task_struct *tsk);
461
462 extern struct task_group *sched_create_group(struct task_group *parent);
463 extern void sched_online_group(struct task_group *tg,
464                                struct task_group *parent);
465 extern void sched_destroy_group(struct task_group *tg);
466 extern void sched_release_group(struct task_group *tg);
467
468 extern void sched_move_task(struct task_struct *tsk);
469
470 #ifdef CONFIG_FAIR_GROUP_SCHED
471 extern int sched_group_set_shares(struct task_group *tg, unsigned long shares);
472
473 extern int sched_group_set_idle(struct task_group *tg, long idle);
474
475 #ifdef CONFIG_SMP
476 extern void set_task_rq_fair(struct sched_entity *se,
477                              struct cfs_rq *prev, struct cfs_rq *next);
478 #else /* !CONFIG_SMP */
479 static inline void set_task_rq_fair(struct sched_entity *se,
480                              struct cfs_rq *prev, struct cfs_rq *next) { }
481 #endif /* CONFIG_SMP */
482 #endif /* CONFIG_FAIR_GROUP_SCHED */
483
484 #else /* CONFIG_CGROUP_SCHED */
485
486 struct cfs_bandwidth { };
487 static inline bool cfs_task_bw_constrained(struct task_struct *p) { return false; }
488
489 #endif  /* CONFIG_CGROUP_SCHED */
490
491 extern void unregister_rt_sched_group(struct task_group *tg);
492 extern void free_rt_sched_group(struct task_group *tg);
493 extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent);
494
495 /*
496  * u64_u32_load/u64_u32_store
497  *
498  * Use a copy of a u64 value to protect against data race. This is only
499  * applicable for 32-bits architectures.
500  */
501 #ifdef CONFIG_64BIT
502 # define u64_u32_load_copy(var, copy)       var
503 # define u64_u32_store_copy(var, copy, val) (var = val)
504 #else
505 # define u64_u32_load_copy(var, copy)                                   \
506 ({                                                                      \
507         u64 __val, __val_copy;                                          \
508         do {                                                            \
509                 __val_copy = copy;                                      \
510                 /*                                                      \
511                  * paired with u64_u32_store_copy(), ordering access    \
512                  * to var and copy.                                     \
513                  */                                                     \
514                 smp_rmb();                                              \
515                 __val = var;                                            \
516         } while (__val != __val_copy);                                  \
517         __val;                                                          \
518 })
519 # define u64_u32_store_copy(var, copy, val)                             \
520 do {                                                                    \
521         typeof(val) __val = (val);                                      \
522         var = __val;                                                    \
523         /*                                                              \
524          * paired with u64_u32_load_copy(), ordering access to var and  \
525          * copy.                                                        \
526          */                                                             \
527         smp_wmb();                                                      \
528         copy = __val;                                                   \
529 } while (0)
530 #endif
531 # define u64_u32_load(var)      u64_u32_load_copy(var, var##_copy)
532 # define u64_u32_store(var, val) u64_u32_store_copy(var, var##_copy, val)
533
534 /* CFS-related fields in a runqueue */
535 struct cfs_rq {
536         struct load_weight      load;
537         unsigned int            nr_running;
538         unsigned int            h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */
539         unsigned int            idle_nr_running;   /* SCHED_IDLE */
540         unsigned int            idle_h_nr_running; /* SCHED_IDLE */
541
542         s64                     avg_vruntime;
543         u64                     avg_load;
544
545         u64                     exec_clock;
546         u64                     min_vruntime;
547 #ifdef CONFIG_SCHED_CORE
548         unsigned int            forceidle_seq;
549         u64                     min_vruntime_fi;
550 #endif
551
552 #ifndef CONFIG_64BIT
553         u64                     min_vruntime_copy;
554 #endif
555
556         struct rb_root_cached   tasks_timeline;
557
558         /*
559          * 'curr' points to currently running entity on this cfs_rq.
560          * It is set to NULL otherwise (i.e when none are currently running).
561          */
562         struct sched_entity     *curr;
563         struct sched_entity     *next;
564
565 #ifdef  CONFIG_SCHED_DEBUG
566         unsigned int            nr_spread_over;
567 #endif
568
569 #ifdef CONFIG_SMP
570         /*
571          * CFS load tracking
572          */
573         struct sched_avg        avg;
574 #ifndef CONFIG_64BIT
575         u64                     last_update_time_copy;
576 #endif
577         struct {
578                 raw_spinlock_t  lock ____cacheline_aligned;
579                 int             nr;
580                 unsigned long   load_avg;
581                 unsigned long   util_avg;
582                 unsigned long   runnable_avg;
583         } removed;
584
585 #ifdef CONFIG_FAIR_GROUP_SCHED
586         u64                     last_update_tg_load_avg;
587         unsigned long           tg_load_avg_contrib;
588         long                    propagate;
589         long                    prop_runnable_sum;
590
591         /*
592          *   h_load = weight * f(tg)
593          *
594          * Where f(tg) is the recursive weight fraction assigned to
595          * this group.
596          */
597         unsigned long           h_load;
598         u64                     last_h_load_update;
599         struct sched_entity     *h_load_next;
600 #endif /* CONFIG_FAIR_GROUP_SCHED */
601 #endif /* CONFIG_SMP */
602
603 #ifdef CONFIG_FAIR_GROUP_SCHED
604         struct rq               *rq;    /* CPU runqueue to which this cfs_rq is attached */
605
606         /*
607          * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
608          * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
609          * (like users, containers etc.)
610          *
611          * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a CPU.
612          * This list is used during load balance.
613          */
614         int                     on_list;
615         struct list_head        leaf_cfs_rq_list;
616         struct task_group       *tg;    /* group that "owns" this runqueue */
617
618         /* Locally cached copy of our task_group's idle value */
619         int                     idle;
620
621 #ifdef CONFIG_CFS_BANDWIDTH
622         int                     runtime_enabled;
623         s64                     runtime_remaining;
624
625         u64                     throttled_pelt_idle;
626 #ifndef CONFIG_64BIT
627         u64                     throttled_pelt_idle_copy;
628 #endif
629         u64                     throttled_clock;
630         u64                     throttled_clock_pelt;
631         u64                     throttled_clock_pelt_time;
632         u64                     throttled_clock_self;
633         u64                     throttled_clock_self_time;
634         int                     throttled;
635         int                     throttle_count;
636         struct list_head        throttled_list;
637         struct list_head        throttled_csd_list;
638 #endif /* CONFIG_CFS_BANDWIDTH */
639 #endif /* CONFIG_FAIR_GROUP_SCHED */
640 };
641
642 static inline int rt_bandwidth_enabled(void)
643 {
644         return sysctl_sched_rt_runtime >= 0;
645 }
646
647 /* RT IPI pull logic requires IRQ_WORK */
648 #if defined(CONFIG_IRQ_WORK) && defined(CONFIG_SMP)
649 # define HAVE_RT_PUSH_IPI
650 #endif
651
652 /* Real-Time classes' related field in a runqueue: */
653 struct rt_rq {
654         struct rt_prio_array    active;
655         unsigned int            rt_nr_running;
656         unsigned int            rr_nr_running;
657 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
658         struct {
659                 int             curr; /* highest queued rt task prio */
660 #ifdef CONFIG_SMP
661                 int             next; /* next highest */
662 #endif
663         } highest_prio;
664 #endif
665 #ifdef CONFIG_SMP
666         int                     overloaded;
667         struct plist_head       pushable_tasks;
668
669 #endif /* CONFIG_SMP */
670         int                     rt_queued;
671
672         int                     rt_throttled;
673         u64                     rt_time;
674         u64                     rt_runtime;
675         /* Nests inside the rq lock: */
676         raw_spinlock_t          rt_runtime_lock;
677
678 #ifdef CONFIG_RT_GROUP_SCHED
679         unsigned int            rt_nr_boosted;
680
681         struct rq               *rq;
682         struct task_group       *tg;
683 #endif
684 };
685
686 static inline bool rt_rq_is_runnable(struct rt_rq *rt_rq)
687 {
688         return rt_rq->rt_queued && rt_rq->rt_nr_running;
689 }
690
691 /* Deadline class' related fields in a runqueue */
692 struct dl_rq {
693         /* runqueue is an rbtree, ordered by deadline */
694         struct rb_root_cached   root;
695
696         unsigned int            dl_nr_running;
697
698 #ifdef CONFIG_SMP
699         /*
700          * Deadline values of the currently executing and the
701          * earliest ready task on this rq. Caching these facilitates
702          * the decision whether or not a ready but not running task
703          * should migrate somewhere else.
704          */
705         struct {
706                 u64             curr;
707                 u64             next;
708         } earliest_dl;
709
710         int                     overloaded;
711
712         /*
713          * Tasks on this rq that can be pushed away. They are kept in
714          * an rb-tree, ordered by tasks' deadlines, with caching
715          * of the leftmost (earliest deadline) element.
716          */
717         struct rb_root_cached   pushable_dl_tasks_root;
718 #else
719         struct dl_bw            dl_bw;
720 #endif
721         /*
722          * "Active utilization" for this runqueue: increased when a
723          * task wakes up (becomes TASK_RUNNING) and decreased when a
724          * task blocks
725          */
726         u64                     running_bw;
727
728         /*
729          * Utilization of the tasks "assigned" to this runqueue (including
730          * the tasks that are in runqueue and the tasks that executed on this
731          * CPU and blocked). Increased when a task moves to this runqueue, and
732          * decreased when the task moves away (migrates, changes scheduling
733          * policy, or terminates).
734          * This is needed to compute the "inactive utilization" for the
735          * runqueue (inactive utilization = this_bw - running_bw).
736          */
737         u64                     this_bw;
738         u64                     extra_bw;
739
740         /*
741          * Maximum available bandwidth for reclaiming by SCHED_FLAG_RECLAIM
742          * tasks of this rq. Used in calculation of reclaimable bandwidth(GRUB).
743          */
744         u64                     max_bw;
745
746         /*
747          * Inverse of the fraction of CPU utilization that can be reclaimed
748          * by the GRUB algorithm.
749          */
750         u64                     bw_ratio;
751 };
752
753 #ifdef CONFIG_FAIR_GROUP_SCHED
754 /* An entity is a task if it doesn't "own" a runqueue */
755 #define entity_is_task(se)      (!se->my_q)
756
757 static inline void se_update_runnable(struct sched_entity *se)
758 {
759         if (!entity_is_task(se))
760                 se->runnable_weight = se->my_q->h_nr_running;
761 }
762
763 static inline long se_runnable(struct sched_entity *se)
764 {
765         if (entity_is_task(se))
766                 return !!se->on_rq;
767         else
768                 return se->runnable_weight;
769 }
770
771 #else
772 #define entity_is_task(se)      1
773
774 static inline void se_update_runnable(struct sched_entity *se) {}
775
776 static inline long se_runnable(struct sched_entity *se)
777 {
778         return !!se->on_rq;
779 }
780 #endif
781
782 #ifdef CONFIG_SMP
783 /*
784  * XXX we want to get rid of these helpers and use the full load resolution.
785  */
786 static inline long se_weight(struct sched_entity *se)
787 {
788         return scale_load_down(se->load.weight);
789 }
790
791
792 static inline bool sched_asym_prefer(int a, int b)
793 {
794         return arch_asym_cpu_priority(a) > arch_asym_cpu_priority(b);
795 }
796
797 struct perf_domain {
798         struct em_perf_domain *em_pd;
799         struct perf_domain *next;
800         struct rcu_head rcu;
801 };
802
803 /* Scheduling group status flags */
804 #define SG_OVERLOAD             0x1 /* More than one runnable task on a CPU. */
805 #define SG_OVERUTILIZED         0x2 /* One or more CPUs are over-utilized. */
806
807 /*
808  * We add the notion of a root-domain which will be used to define per-domain
809  * variables. Each exclusive cpuset essentially defines an island domain by
810  * fully partitioning the member CPUs from any other cpuset. Whenever a new
811  * exclusive cpuset is created, we also create and attach a new root-domain
812  * object.
813  *
814  */
815 struct root_domain {
816         atomic_t                refcount;
817         atomic_t                rto_count;
818         struct rcu_head         rcu;
819         cpumask_var_t           span;
820         cpumask_var_t           online;
821
822         /*
823          * Indicate pullable load on at least one CPU, e.g:
824          * - More than one runnable task
825          * - Running task is misfit
826          */
827         int                     overload;
828
829         /* Indicate one or more cpus over-utilized (tipping point) */
830         int                     overutilized;
831
832         /*
833          * The bit corresponding to a CPU gets set here if such CPU has more
834          * than one runnable -deadline task (as it is below for RT tasks).
835          */
836         cpumask_var_t           dlo_mask;
837         atomic_t                dlo_count;
838         struct dl_bw            dl_bw;
839         struct cpudl            cpudl;
840
841         /*
842          * Indicate whether a root_domain's dl_bw has been checked or
843          * updated. It's monotonously increasing value.
844          *
845          * Also, some corner cases, like 'wrap around' is dangerous, but given
846          * that u64 is 'big enough'. So that shouldn't be a concern.
847          */
848         u64 visit_gen;
849
850 #ifdef HAVE_RT_PUSH_IPI
851         /*
852          * For IPI pull requests, loop across the rto_mask.
853          */
854         struct irq_work         rto_push_work;
855         raw_spinlock_t          rto_lock;
856         /* These are only updated and read within rto_lock */
857         int                     rto_loop;
858         int                     rto_cpu;
859         /* These atomics are updated outside of a lock */
860         atomic_t                rto_loop_next;
861         atomic_t                rto_loop_start;
862 #endif
863         /*
864          * The "RT overload" flag: it gets set if a CPU has more than
865          * one runnable RT task.
866          */
867         cpumask_var_t           rto_mask;
868         struct cpupri           cpupri;
869
870         unsigned long           max_cpu_capacity;
871
872         /*
873          * NULL-terminated list of performance domains intersecting with the
874          * CPUs of the rd. Protected by RCU.
875          */
876         struct perf_domain __rcu *pd;
877 };
878
879 extern void init_defrootdomain(void);
880 extern int sched_init_domains(const struct cpumask *cpu_map);
881 extern void rq_attach_root(struct rq *rq, struct root_domain *rd);
882 extern void sched_get_rd(struct root_domain *rd);
883 extern void sched_put_rd(struct root_domain *rd);
884
885 #ifdef HAVE_RT_PUSH_IPI
886 extern void rto_push_irq_work_func(struct irq_work *work);
887 #endif
888 #endif /* CONFIG_SMP */
889
890 #ifdef CONFIG_UCLAMP_TASK
891 /*
892  * struct uclamp_bucket - Utilization clamp bucket
893  * @value: utilization clamp value for tasks on this clamp bucket
894  * @tasks: number of RUNNABLE tasks on this clamp bucket
895  *
896  * Keep track of how many tasks are RUNNABLE for a given utilization
897  * clamp value.
898  */
899 struct uclamp_bucket {
900         unsigned long value : bits_per(SCHED_CAPACITY_SCALE);
901         unsigned long tasks : BITS_PER_LONG - bits_per(SCHED_CAPACITY_SCALE);
902 };
903
904 /*
905  * struct uclamp_rq - rq's utilization clamp
906  * @value: currently active clamp values for a rq
907  * @bucket: utilization clamp buckets affecting a rq
908  *
909  * Keep track of RUNNABLE tasks on a rq to aggregate their clamp values.
910  * A clamp value is affecting a rq when there is at least one task RUNNABLE
911  * (or actually running) with that value.
912  *
913  * There are up to UCLAMP_CNT possible different clamp values, currently there
914  * are only two: minimum utilization and maximum utilization.
915  *
916  * All utilization clamping values are MAX aggregated, since:
917  * - for util_min: we want to run the CPU at least at the max of the minimum
918  *   utilization required by its currently RUNNABLE tasks.
919  * - for util_max: we want to allow the CPU to run up to the max of the
920  *   maximum utilization allowed by its currently RUNNABLE tasks.
921  *
922  * Since on each system we expect only a limited number of different
923  * utilization clamp values (UCLAMP_BUCKETS), use a simple array to track
924  * the metrics required to compute all the per-rq utilization clamp values.
925  */
926 struct uclamp_rq {
927         unsigned int value;
928         struct uclamp_bucket bucket[UCLAMP_BUCKETS];
929 };
930
931 DECLARE_STATIC_KEY_FALSE(sched_uclamp_used);
932 #endif /* CONFIG_UCLAMP_TASK */
933
934 struct rq;
935 struct balance_callback {
936         struct balance_callback *next;
937         void (*func)(struct rq *rq);
938 };
939
940 /*
941  * This is the main, per-CPU runqueue data structure.
942  *
943  * Locking rule: those places that want to lock multiple runqueues
944  * (such as the load balancing or the thread migration code), lock
945  * acquire operations must be ordered by ascending &runqueue.
946  */
947 struct rq {
948         /* runqueue lock: */
949         raw_spinlock_t          __lock;
950
951         unsigned int            nr_running;
952 #ifdef CONFIG_NUMA_BALANCING
953         unsigned int            nr_numa_running;
954         unsigned int            nr_preferred_running;
955         unsigned int            numa_migrate_on;
956 #endif
957 #ifdef CONFIG_NO_HZ_COMMON
958 #ifdef CONFIG_SMP
959         unsigned long           last_blocked_load_update_tick;
960         unsigned int            has_blocked_load;
961         call_single_data_t      nohz_csd;
962 #endif /* CONFIG_SMP */
963         unsigned int            nohz_tick_stopped;
964         atomic_t                nohz_flags;
965 #endif /* CONFIG_NO_HZ_COMMON */
966
967 #ifdef CONFIG_SMP
968         unsigned int            ttwu_pending;
969 #endif
970         u64                     nr_switches;
971
972 #ifdef CONFIG_UCLAMP_TASK
973         /* Utilization clamp values based on CPU's RUNNABLE tasks */
974         struct uclamp_rq        uclamp[UCLAMP_CNT] ____cacheline_aligned;
975         unsigned int            uclamp_flags;
976 #define UCLAMP_FLAG_IDLE 0x01
977 #endif
978
979         struct cfs_rq           cfs;
980         struct rt_rq            rt;
981         struct dl_rq            dl;
982
983 #ifdef CONFIG_FAIR_GROUP_SCHED
984         /* list of leaf cfs_rq on this CPU: */
985         struct list_head        leaf_cfs_rq_list;
986         struct list_head        *tmp_alone_branch;
987 #endif /* CONFIG_FAIR_GROUP_SCHED */
988
989         /*
990          * This is part of a global counter where only the total sum
991          * over all CPUs matters. A task can increase this counter on
992          * one CPU and if it got migrated afterwards it may decrease
993          * it on another CPU. Always updated under the runqueue lock:
994          */
995         unsigned int            nr_uninterruptible;
996
997         struct task_struct __rcu        *curr;
998         struct task_struct      *idle;
999         struct task_struct      *stop;
1000         unsigned long           next_balance;
1001         struct mm_struct        *prev_mm;
1002
1003         unsigned int            clock_update_flags;
1004         u64                     clock;
1005         /* Ensure that all clocks are in the same cache line */
1006         u64                     clock_task ____cacheline_aligned;
1007         u64                     clock_pelt;
1008         unsigned long           lost_idle_time;
1009         u64                     clock_pelt_idle;
1010         u64                     clock_idle;
1011 #ifndef CONFIG_64BIT
1012         u64                     clock_pelt_idle_copy;
1013         u64                     clock_idle_copy;
1014 #endif
1015
1016         atomic_t                nr_iowait;
1017
1018 #ifdef CONFIG_SCHED_DEBUG
1019         u64 last_seen_need_resched_ns;
1020         int ticks_without_resched;
1021 #endif
1022
1023 #ifdef CONFIG_MEMBARRIER
1024         int membarrier_state;
1025 #endif
1026
1027 #ifdef CONFIG_SMP
1028         struct root_domain              *rd;
1029         struct sched_domain __rcu       *sd;
1030
1031         unsigned long           cpu_capacity;
1032
1033         struct balance_callback *balance_callback;
1034
1035         unsigned char           nohz_idle_balance;
1036         unsigned char           idle_balance;
1037
1038         unsigned long           misfit_task_load;
1039
1040         /* For active balancing */
1041         int                     active_balance;
1042         int                     push_cpu;
1043         struct cpu_stop_work    active_balance_work;
1044
1045         /* CPU of this runqueue: */
1046         int                     cpu;
1047         int                     online;
1048
1049         struct list_head cfs_tasks;
1050
1051         struct sched_avg        avg_rt;
1052         struct sched_avg        avg_dl;
1053 #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
1054         struct sched_avg        avg_irq;
1055 #endif
1056 #ifdef CONFIG_SCHED_THERMAL_PRESSURE
1057         struct sched_avg        avg_thermal;
1058 #endif
1059         u64                     idle_stamp;
1060         u64                     avg_idle;
1061
1062         /* This is used to determine avg_idle's max value */
1063         u64                     max_idle_balance_cost;
1064
1065 #ifdef CONFIG_HOTPLUG_CPU
1066         struct rcuwait          hotplug_wait;
1067 #endif
1068 #endif /* CONFIG_SMP */
1069
1070 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
1071         u64                     prev_irq_time;
1072 #endif
1073 #ifdef CONFIG_PARAVIRT
1074         u64                     prev_steal_time;
1075 #endif
1076 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
1077         u64                     prev_steal_time_rq;
1078 #endif
1079
1080         /* calc_load related fields */
1081         unsigned long           calc_load_update;
1082         long                    calc_load_active;
1083
1084 #ifdef CONFIG_SCHED_HRTICK
1085 #ifdef CONFIG_SMP
1086         call_single_data_t      hrtick_csd;
1087 #endif
1088         struct hrtimer          hrtick_timer;
1089         ktime_t                 hrtick_time;
1090 #endif
1091
1092 #ifdef CONFIG_SCHEDSTATS
1093         /* latency stats */
1094         struct sched_info       rq_sched_info;
1095         unsigned long long      rq_cpu_time;
1096         /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
1097
1098         /* sys_sched_yield() stats */
1099         unsigned int            yld_count;
1100
1101         /* schedule() stats */
1102         unsigned int            sched_count;
1103         unsigned int            sched_goidle;
1104
1105         /* try_to_wake_up() stats */
1106         unsigned int            ttwu_count;
1107         unsigned int            ttwu_local;
1108 #endif
1109
1110 #ifdef CONFIG_CPU_IDLE
1111         /* Must be inspected within a rcu lock section */
1112         struct cpuidle_state    *idle_state;
1113 #endif
1114
1115 #ifdef CONFIG_SMP
1116         unsigned int            nr_pinned;
1117 #endif
1118         unsigned int            push_busy;
1119         struct cpu_stop_work    push_work;
1120
1121 #ifdef CONFIG_SCHED_CORE
1122         /* per rq */
1123         struct rq               *core;
1124         struct task_struct      *core_pick;
1125         unsigned int            core_enabled;
1126         unsigned int            core_sched_seq;
1127         struct rb_root          core_tree;
1128
1129         /* shared state -- careful with sched_core_cpu_deactivate() */
1130         unsigned int            core_task_seq;
1131         unsigned int            core_pick_seq;
1132         unsigned long           core_cookie;
1133         unsigned int            core_forceidle_count;
1134         unsigned int            core_forceidle_seq;
1135         unsigned int            core_forceidle_occupation;
1136         u64                     core_forceidle_start;
1137 #endif
1138
1139         /* Scratch cpumask to be temporarily used under rq_lock */
1140         cpumask_var_t           scratch_mask;
1141
1142 #if defined(CONFIG_CFS_BANDWIDTH) && defined(CONFIG_SMP)
1143         call_single_data_t      cfsb_csd;
1144         struct list_head        cfsb_csd_list;
1145 #endif
1146 };
1147
1148 #ifdef CONFIG_FAIR_GROUP_SCHED
1149
1150 /* CPU runqueue to which this cfs_rq is attached */
1151 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
1152 {
1153         return cfs_rq->rq;
1154 }
1155
1156 #else
1157
1158 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
1159 {
1160         return container_of(cfs_rq, struct rq, cfs);
1161 }
1162 #endif
1163
1164 static inline int cpu_of(struct rq *rq)
1165 {
1166 #ifdef CONFIG_SMP
1167         return rq->cpu;
1168 #else
1169         return 0;
1170 #endif
1171 }
1172
1173 #define MDF_PUSH        0x01
1174
1175 static inline bool is_migration_disabled(struct task_struct *p)
1176 {
1177 #ifdef CONFIG_SMP
1178         return p->migration_disabled;
1179 #else
1180         return false;
1181 #endif
1182 }
1183
1184 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
1185
1186 #define cpu_rq(cpu)             (&per_cpu(runqueues, (cpu)))
1187 #define this_rq()               this_cpu_ptr(&runqueues)
1188 #define task_rq(p)              cpu_rq(task_cpu(p))
1189 #define cpu_curr(cpu)           (cpu_rq(cpu)->curr)
1190 #define raw_rq()                raw_cpu_ptr(&runqueues)
1191
1192 struct sched_group;
1193 #ifdef CONFIG_SCHED_CORE
1194 static inline struct cpumask *sched_group_span(struct sched_group *sg);
1195
1196 DECLARE_STATIC_KEY_FALSE(__sched_core_enabled);
1197
1198 static inline bool sched_core_enabled(struct rq *rq)
1199 {
1200         return static_branch_unlikely(&__sched_core_enabled) && rq->core_enabled;
1201 }
1202
1203 static inline bool sched_core_disabled(void)
1204 {
1205         return !static_branch_unlikely(&__sched_core_enabled);
1206 }
1207
1208 /*
1209  * Be careful with this function; not for general use. The return value isn't
1210  * stable unless you actually hold a relevant rq->__lock.
1211  */
1212 static inline raw_spinlock_t *rq_lockp(struct rq *rq)
1213 {
1214         if (sched_core_enabled(rq))
1215                 return &rq->core->__lock;
1216
1217         return &rq->__lock;
1218 }
1219
1220 static inline raw_spinlock_t *__rq_lockp(struct rq *rq)
1221 {
1222         if (rq->core_enabled)
1223                 return &rq->core->__lock;
1224
1225         return &rq->__lock;
1226 }
1227
1228 bool cfs_prio_less(const struct task_struct *a, const struct task_struct *b,
1229                         bool fi);
1230 void task_vruntime_update(struct rq *rq, struct task_struct *p, bool in_fi);
1231
1232 /*
1233  * Helpers to check if the CPU's core cookie matches with the task's cookie
1234  * when core scheduling is enabled.
1235  * A special case is that the task's cookie always matches with CPU's core
1236  * cookie if the CPU is in an idle core.
1237  */
1238 static inline bool sched_cpu_cookie_match(struct rq *rq, struct task_struct *p)
1239 {
1240         /* Ignore cookie match if core scheduler is not enabled on the CPU. */
1241         if (!sched_core_enabled(rq))
1242                 return true;
1243
1244         return rq->core->core_cookie == p->core_cookie;
1245 }
1246
1247 static inline bool sched_core_cookie_match(struct rq *rq, struct task_struct *p)
1248 {
1249         bool idle_core = true;
1250         int cpu;
1251
1252         /* Ignore cookie match if core scheduler is not enabled on the CPU. */
1253         if (!sched_core_enabled(rq))
1254                 return true;
1255
1256         for_each_cpu(cpu, cpu_smt_mask(cpu_of(rq))) {
1257                 if (!available_idle_cpu(cpu)) {
1258                         idle_core = false;
1259                         break;
1260                 }
1261         }
1262
1263         /*
1264          * A CPU in an idle core is always the best choice for tasks with
1265          * cookies.
1266          */
1267         return idle_core || rq->core->core_cookie == p->core_cookie;
1268 }
1269
1270 static inline bool sched_group_cookie_match(struct rq *rq,
1271                                             struct task_struct *p,
1272                                             struct sched_group *group)
1273 {
1274         int cpu;
1275
1276         /* Ignore cookie match if core scheduler is not enabled on the CPU. */
1277         if (!sched_core_enabled(rq))
1278                 return true;
1279
1280         for_each_cpu_and(cpu, sched_group_span(group), p->cpus_ptr) {
1281                 if (sched_core_cookie_match(cpu_rq(cpu), p))
1282                         return true;
1283         }
1284         return false;
1285 }
1286
1287 static inline bool sched_core_enqueued(struct task_struct *p)
1288 {
1289         return !RB_EMPTY_NODE(&p->core_node);
1290 }
1291
1292 extern void sched_core_enqueue(struct rq *rq, struct task_struct *p);
1293 extern void sched_core_dequeue(struct rq *rq, struct task_struct *p, int flags);
1294
1295 extern void sched_core_get(void);
1296 extern void sched_core_put(void);
1297
1298 #else /* !CONFIG_SCHED_CORE */
1299
1300 static inline bool sched_core_enabled(struct rq *rq)
1301 {
1302         return false;
1303 }
1304
1305 static inline bool sched_core_disabled(void)
1306 {
1307         return true;
1308 }
1309
1310 static inline raw_spinlock_t *rq_lockp(struct rq *rq)
1311 {
1312         return &rq->__lock;
1313 }
1314
1315 static inline raw_spinlock_t *__rq_lockp(struct rq *rq)
1316 {
1317         return &rq->__lock;
1318 }
1319
1320 static inline bool sched_cpu_cookie_match(struct rq *rq, struct task_struct *p)
1321 {
1322         return true;
1323 }
1324
1325 static inline bool sched_core_cookie_match(struct rq *rq, struct task_struct *p)
1326 {
1327         return true;
1328 }
1329
1330 static inline bool sched_group_cookie_match(struct rq *rq,
1331                                             struct task_struct *p,
1332                                             struct sched_group *group)
1333 {
1334         return true;
1335 }
1336 #endif /* CONFIG_SCHED_CORE */
1337
1338 static inline void lockdep_assert_rq_held(struct rq *rq)
1339 {
1340         lockdep_assert_held(__rq_lockp(rq));
1341 }
1342
1343 extern void raw_spin_rq_lock_nested(struct rq *rq, int subclass);
1344 extern bool raw_spin_rq_trylock(struct rq *rq);
1345 extern void raw_spin_rq_unlock(struct rq *rq);
1346
1347 static inline void raw_spin_rq_lock(struct rq *rq)
1348 {
1349         raw_spin_rq_lock_nested(rq, 0);
1350 }
1351
1352 static inline void raw_spin_rq_lock_irq(struct rq *rq)
1353 {
1354         local_irq_disable();
1355         raw_spin_rq_lock(rq);
1356 }
1357
1358 static inline void raw_spin_rq_unlock_irq(struct rq *rq)
1359 {
1360         raw_spin_rq_unlock(rq);
1361         local_irq_enable();
1362 }
1363
1364 static inline unsigned long _raw_spin_rq_lock_irqsave(struct rq *rq)
1365 {
1366         unsigned long flags;
1367         local_irq_save(flags);
1368         raw_spin_rq_lock(rq);
1369         return flags;
1370 }
1371
1372 static inline void raw_spin_rq_unlock_irqrestore(struct rq *rq, unsigned long flags)
1373 {
1374         raw_spin_rq_unlock(rq);
1375         local_irq_restore(flags);
1376 }
1377
1378 #define raw_spin_rq_lock_irqsave(rq, flags)     \
1379 do {                                            \
1380         flags = _raw_spin_rq_lock_irqsave(rq);  \
1381 } while (0)
1382
1383 #ifdef CONFIG_SCHED_SMT
1384 extern void __update_idle_core(struct rq *rq);
1385
1386 static inline void update_idle_core(struct rq *rq)
1387 {
1388         if (static_branch_unlikely(&sched_smt_present))
1389                 __update_idle_core(rq);
1390 }
1391
1392 #else
1393 static inline void update_idle_core(struct rq *rq) { }
1394 #endif
1395
1396 #ifdef CONFIG_FAIR_GROUP_SCHED
1397 static inline struct task_struct *task_of(struct sched_entity *se)
1398 {
1399         SCHED_WARN_ON(!entity_is_task(se));
1400         return container_of(se, struct task_struct, se);
1401 }
1402
1403 static inline struct cfs_rq *task_cfs_rq(struct task_struct *p)
1404 {
1405         return p->se.cfs_rq;
1406 }
1407
1408 /* runqueue on which this entity is (to be) queued */
1409 static inline struct cfs_rq *cfs_rq_of(const struct sched_entity *se)
1410 {
1411         return se->cfs_rq;
1412 }
1413
1414 /* runqueue "owned" by this group */
1415 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
1416 {
1417         return grp->my_q;
1418 }
1419
1420 #else
1421
1422 #define task_of(_se)    container_of(_se, struct task_struct, se)
1423
1424 static inline struct cfs_rq *task_cfs_rq(const struct task_struct *p)
1425 {
1426         return &task_rq(p)->cfs;
1427 }
1428
1429 static inline struct cfs_rq *cfs_rq_of(const struct sched_entity *se)
1430 {
1431         const struct task_struct *p = task_of(se);
1432         struct rq *rq = task_rq(p);
1433
1434         return &rq->cfs;
1435 }
1436
1437 /* runqueue "owned" by this group */
1438 static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
1439 {
1440         return NULL;
1441 }
1442 #endif
1443
1444 extern void update_rq_clock(struct rq *rq);
1445
1446 /*
1447  * rq::clock_update_flags bits
1448  *
1449  * %RQCF_REQ_SKIP - will request skipping of clock update on the next
1450  *  call to __schedule(). This is an optimisation to avoid
1451  *  neighbouring rq clock updates.
1452  *
1453  * %RQCF_ACT_SKIP - is set from inside of __schedule() when skipping is
1454  *  in effect and calls to update_rq_clock() are being ignored.
1455  *
1456  * %RQCF_UPDATED - is a debug flag that indicates whether a call has been
1457  *  made to update_rq_clock() since the last time rq::lock was pinned.
1458  *
1459  * If inside of __schedule(), clock_update_flags will have been
1460  * shifted left (a left shift is a cheap operation for the fast path
1461  * to promote %RQCF_REQ_SKIP to %RQCF_ACT_SKIP), so you must use,
1462  *
1463  *      if (rq-clock_update_flags >= RQCF_UPDATED)
1464  *
1465  * to check if %RQCF_UPDATED is set. It'll never be shifted more than
1466  * one position though, because the next rq_unpin_lock() will shift it
1467  * back.
1468  */
1469 #define RQCF_REQ_SKIP           0x01
1470 #define RQCF_ACT_SKIP           0x02
1471 #define RQCF_UPDATED            0x04
1472
1473 static inline void assert_clock_updated(struct rq *rq)
1474 {
1475         /*
1476          * The only reason for not seeing a clock update since the
1477          * last rq_pin_lock() is if we're currently skipping updates.
1478          */
1479         SCHED_WARN_ON(rq->clock_update_flags < RQCF_ACT_SKIP);
1480 }
1481
1482 static inline u64 rq_clock(struct rq *rq)
1483 {
1484         lockdep_assert_rq_held(rq);
1485         assert_clock_updated(rq);
1486
1487         return rq->clock;
1488 }
1489
1490 static inline u64 rq_clock_task(struct rq *rq)
1491 {
1492         lockdep_assert_rq_held(rq);
1493         assert_clock_updated(rq);
1494
1495         return rq->clock_task;
1496 }
1497
1498 /**
1499  * By default the decay is the default pelt decay period.
1500  * The decay shift can change the decay period in
1501  * multiples of 32.
1502  *  Decay shift         Decay period(ms)
1503  *      0                       32
1504  *      1                       64
1505  *      2                       128
1506  *      3                       256
1507  *      4                       512
1508  */
1509 extern int sched_thermal_decay_shift;
1510
1511 static inline u64 rq_clock_thermal(struct rq *rq)
1512 {
1513         return rq_clock_task(rq) >> sched_thermal_decay_shift;
1514 }
1515
1516 static inline void rq_clock_skip_update(struct rq *rq)
1517 {
1518         lockdep_assert_rq_held(rq);
1519         rq->clock_update_flags |= RQCF_REQ_SKIP;
1520 }
1521
1522 /*
1523  * See rt task throttling, which is the only time a skip
1524  * request is canceled.
1525  */
1526 static inline void rq_clock_cancel_skipupdate(struct rq *rq)
1527 {
1528         lockdep_assert_rq_held(rq);
1529         rq->clock_update_flags &= ~RQCF_REQ_SKIP;
1530 }
1531
1532 /*
1533  * During cpu offlining and rq wide unthrottling, we can trigger
1534  * an update_rq_clock() for several cfs and rt runqueues (Typically
1535  * when using list_for_each_entry_*)
1536  * rq_clock_start_loop_update() can be called after updating the clock
1537  * once and before iterating over the list to prevent multiple update.
1538  * After the iterative traversal, we need to call rq_clock_stop_loop_update()
1539  * to clear RQCF_ACT_SKIP of rq->clock_update_flags.
1540  */
1541 static inline void rq_clock_start_loop_update(struct rq *rq)
1542 {
1543         lockdep_assert_rq_held(rq);
1544         SCHED_WARN_ON(rq->clock_update_flags & RQCF_ACT_SKIP);
1545         rq->clock_update_flags |= RQCF_ACT_SKIP;
1546 }
1547
1548 static inline void rq_clock_stop_loop_update(struct rq *rq)
1549 {
1550         lockdep_assert_rq_held(rq);
1551         rq->clock_update_flags &= ~RQCF_ACT_SKIP;
1552 }
1553
1554 struct rq_flags {
1555         unsigned long flags;
1556         struct pin_cookie cookie;
1557 #ifdef CONFIG_SCHED_DEBUG
1558         /*
1559          * A copy of (rq::clock_update_flags & RQCF_UPDATED) for the
1560          * current pin context is stashed here in case it needs to be
1561          * restored in rq_repin_lock().
1562          */
1563         unsigned int clock_update_flags;
1564 #endif
1565 };
1566
1567 extern struct balance_callback balance_push_callback;
1568
1569 /*
1570  * Lockdep annotation that avoids accidental unlocks; it's like a
1571  * sticky/continuous lockdep_assert_held().
1572  *
1573  * This avoids code that has access to 'struct rq *rq' (basically everything in
1574  * the scheduler) from accidentally unlocking the rq if they do not also have a
1575  * copy of the (on-stack) 'struct rq_flags rf'.
1576  *
1577  * Also see Documentation/locking/lockdep-design.rst.
1578  */
1579 static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf)
1580 {
1581         rf->cookie = lockdep_pin_lock(__rq_lockp(rq));
1582
1583 #ifdef CONFIG_SCHED_DEBUG
1584         rq->clock_update_flags &= (RQCF_REQ_SKIP|RQCF_ACT_SKIP);
1585         rf->clock_update_flags = 0;
1586 #ifdef CONFIG_SMP
1587         SCHED_WARN_ON(rq->balance_callback && rq->balance_callback != &balance_push_callback);
1588 #endif
1589 #endif
1590 }
1591
1592 static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
1593 {
1594 #ifdef CONFIG_SCHED_DEBUG
1595         if (rq->clock_update_flags > RQCF_ACT_SKIP)
1596                 rf->clock_update_flags = RQCF_UPDATED;
1597 #endif
1598
1599         lockdep_unpin_lock(__rq_lockp(rq), rf->cookie);
1600 }
1601
1602 static inline void rq_repin_lock(struct rq *rq, struct rq_flags *rf)
1603 {
1604         lockdep_repin_lock(__rq_lockp(rq), rf->cookie);
1605
1606 #ifdef CONFIG_SCHED_DEBUG
1607         /*
1608          * Restore the value we stashed in @rf for this pin context.
1609          */
1610         rq->clock_update_flags |= rf->clock_update_flags;
1611 #endif
1612 }
1613
1614 struct rq *__task_rq_lock(struct task_struct *p, struct rq_flags *rf)
1615         __acquires(rq->lock);
1616
1617 struct rq *task_rq_lock(struct task_struct *p, struct rq_flags *rf)
1618         __acquires(p->pi_lock)
1619         __acquires(rq->lock);
1620
1621 static inline void __task_rq_unlock(struct rq *rq, struct rq_flags *rf)
1622         __releases(rq->lock)
1623 {
1624         rq_unpin_lock(rq, rf);
1625         raw_spin_rq_unlock(rq);
1626 }
1627
1628 static inline void
1629 task_rq_unlock(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
1630         __releases(rq->lock)
1631         __releases(p->pi_lock)
1632 {
1633         rq_unpin_lock(rq, rf);
1634         raw_spin_rq_unlock(rq);
1635         raw_spin_unlock_irqrestore(&p->pi_lock, rf->flags);
1636 }
1637
1638 DEFINE_LOCK_GUARD_1(task_rq_lock, struct task_struct,
1639                     _T->rq = task_rq_lock(_T->lock, &_T->rf),
1640                     task_rq_unlock(_T->rq, _T->lock, &_T->rf),
1641                     struct rq *rq; struct rq_flags rf)
1642
1643 static inline void
1644 rq_lock_irqsave(struct rq *rq, struct rq_flags *rf)
1645         __acquires(rq->lock)
1646 {
1647         raw_spin_rq_lock_irqsave(rq, rf->flags);
1648         rq_pin_lock(rq, rf);
1649 }
1650
1651 static inline void
1652 rq_lock_irq(struct rq *rq, struct rq_flags *rf)
1653         __acquires(rq->lock)
1654 {
1655         raw_spin_rq_lock_irq(rq);
1656         rq_pin_lock(rq, rf);
1657 }
1658
1659 static inline void
1660 rq_lock(struct rq *rq, struct rq_flags *rf)
1661         __acquires(rq->lock)
1662 {
1663         raw_spin_rq_lock(rq);
1664         rq_pin_lock(rq, rf);
1665 }
1666
1667 static inline void
1668 rq_unlock_irqrestore(struct rq *rq, struct rq_flags *rf)
1669         __releases(rq->lock)
1670 {
1671         rq_unpin_lock(rq, rf);
1672         raw_spin_rq_unlock_irqrestore(rq, rf->flags);
1673 }
1674
1675 static inline void
1676 rq_unlock_irq(struct rq *rq, struct rq_flags *rf)
1677         __releases(rq->lock)
1678 {
1679         rq_unpin_lock(rq, rf);
1680         raw_spin_rq_unlock_irq(rq);
1681 }
1682
1683 static inline void
1684 rq_unlock(struct rq *rq, struct rq_flags *rf)
1685         __releases(rq->lock)
1686 {
1687         rq_unpin_lock(rq, rf);
1688         raw_spin_rq_unlock(rq);
1689 }
1690
1691 DEFINE_LOCK_GUARD_1(rq_lock, struct rq,
1692                     rq_lock(_T->lock, &_T->rf),
1693                     rq_unlock(_T->lock, &_T->rf),
1694                     struct rq_flags rf)
1695
1696 DEFINE_LOCK_GUARD_1(rq_lock_irq, struct rq,
1697                     rq_lock_irq(_T->lock, &_T->rf),
1698                     rq_unlock_irq(_T->lock, &_T->rf),
1699                     struct rq_flags rf)
1700
1701 DEFINE_LOCK_GUARD_1(rq_lock_irqsave, struct rq,
1702                     rq_lock_irqsave(_T->lock, &_T->rf),
1703                     rq_unlock_irqrestore(_T->lock, &_T->rf),
1704                     struct rq_flags rf)
1705
1706 static inline struct rq *
1707 this_rq_lock_irq(struct rq_flags *rf)
1708         __acquires(rq->lock)
1709 {
1710         struct rq *rq;
1711
1712         local_irq_disable();
1713         rq = this_rq();
1714         rq_lock(rq, rf);
1715         return rq;
1716 }
1717
1718 #ifdef CONFIG_NUMA
1719 enum numa_topology_type {
1720         NUMA_DIRECT,
1721         NUMA_GLUELESS_MESH,
1722         NUMA_BACKPLANE,
1723 };
1724 extern enum numa_topology_type sched_numa_topology_type;
1725 extern int sched_max_numa_distance;
1726 extern bool find_numa_distance(int distance);
1727 extern void sched_init_numa(int offline_node);
1728 extern void sched_update_numa(int cpu, bool online);
1729 extern void sched_domains_numa_masks_set(unsigned int cpu);
1730 extern void sched_domains_numa_masks_clear(unsigned int cpu);
1731 extern int sched_numa_find_closest(const struct cpumask *cpus, int cpu);
1732 #else
1733 static inline void sched_init_numa(int offline_node) { }
1734 static inline void sched_update_numa(int cpu, bool online) { }
1735 static inline void sched_domains_numa_masks_set(unsigned int cpu) { }
1736 static inline void sched_domains_numa_masks_clear(unsigned int cpu) { }
1737 static inline int sched_numa_find_closest(const struct cpumask *cpus, int cpu)
1738 {
1739         return nr_cpu_ids;
1740 }
1741 #endif
1742
1743 #ifdef CONFIG_NUMA_BALANCING
1744 /* The regions in numa_faults array from task_struct */
1745 enum numa_faults_stats {
1746         NUMA_MEM = 0,
1747         NUMA_CPU,
1748         NUMA_MEMBUF,
1749         NUMA_CPUBUF
1750 };
1751 extern void sched_setnuma(struct task_struct *p, int node);
1752 extern int migrate_task_to(struct task_struct *p, int cpu);
1753 extern int migrate_swap(struct task_struct *p, struct task_struct *t,
1754                         int cpu, int scpu);
1755 extern void init_numa_balancing(unsigned long clone_flags, struct task_struct *p);
1756 #else
1757 static inline void
1758 init_numa_balancing(unsigned long clone_flags, struct task_struct *p)
1759 {
1760 }
1761 #endif /* CONFIG_NUMA_BALANCING */
1762
1763 #ifdef CONFIG_SMP
1764
1765 static inline void
1766 queue_balance_callback(struct rq *rq,
1767                        struct balance_callback *head,
1768                        void (*func)(struct rq *rq))
1769 {
1770         lockdep_assert_rq_held(rq);
1771
1772         /*
1773          * Don't (re)queue an already queued item; nor queue anything when
1774          * balance_push() is active, see the comment with
1775          * balance_push_callback.
1776          */
1777         if (unlikely(head->next || rq->balance_callback == &balance_push_callback))
1778                 return;
1779
1780         head->func = func;
1781         head->next = rq->balance_callback;
1782         rq->balance_callback = head;
1783 }
1784
1785 #define rcu_dereference_check_sched_domain(p) \
1786         rcu_dereference_check((p), \
1787                               lockdep_is_held(&sched_domains_mutex))
1788
1789 /*
1790  * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
1791  * See destroy_sched_domains: call_rcu for details.
1792  *
1793  * The domain tree of any CPU may only be accessed from within
1794  * preempt-disabled sections.
1795  */
1796 #define for_each_domain(cpu, __sd) \
1797         for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
1798                         __sd; __sd = __sd->parent)
1799
1800 /* A mask of all the SD flags that have the SDF_SHARED_CHILD metaflag */
1801 #define SD_FLAG(name, mflags) (name * !!((mflags) & SDF_SHARED_CHILD)) |
1802 static const unsigned int SD_SHARED_CHILD_MASK =
1803 #include <linux/sched/sd_flags.h>
1804 0;
1805 #undef SD_FLAG
1806
1807 /**
1808  * highest_flag_domain - Return highest sched_domain containing flag.
1809  * @cpu:        The CPU whose highest level of sched domain is to
1810  *              be returned.
1811  * @flag:       The flag to check for the highest sched_domain
1812  *              for the given CPU.
1813  *
1814  * Returns the highest sched_domain of a CPU which contains @flag. If @flag has
1815  * the SDF_SHARED_CHILD metaflag, all the children domains also have @flag.
1816  */
1817 static inline struct sched_domain *highest_flag_domain(int cpu, int flag)
1818 {
1819         struct sched_domain *sd, *hsd = NULL;
1820
1821         for_each_domain(cpu, sd) {
1822                 if (sd->flags & flag) {
1823                         hsd = sd;
1824                         continue;
1825                 }
1826
1827                 /*
1828                  * Stop the search if @flag is known to be shared at lower
1829                  * levels. It will not be found further up.
1830                  */
1831                 if (flag & SD_SHARED_CHILD_MASK)
1832                         break;
1833         }
1834
1835         return hsd;
1836 }
1837
1838 static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
1839 {
1840         struct sched_domain *sd;
1841
1842         for_each_domain(cpu, sd) {
1843                 if (sd->flags & flag)
1844                         break;
1845         }
1846
1847         return sd;
1848 }
1849
1850 DECLARE_PER_CPU(struct sched_domain __rcu *, sd_llc);
1851 DECLARE_PER_CPU(int, sd_llc_size);
1852 DECLARE_PER_CPU(int, sd_llc_id);
1853 DECLARE_PER_CPU(int, sd_share_id);
1854 DECLARE_PER_CPU(struct sched_domain_shared __rcu *, sd_llc_shared);
1855 DECLARE_PER_CPU(struct sched_domain __rcu *, sd_numa);
1856 DECLARE_PER_CPU(struct sched_domain __rcu *, sd_asym_packing);
1857 DECLARE_PER_CPU(struct sched_domain __rcu *, sd_asym_cpucapacity);
1858 extern struct static_key_false sched_asym_cpucapacity;
1859 extern struct static_key_false sched_cluster_active;
1860
1861 static __always_inline bool sched_asym_cpucap_active(void)
1862 {
1863         return static_branch_unlikely(&sched_asym_cpucapacity);
1864 }
1865
1866 struct sched_group_capacity {
1867         atomic_t                ref;
1868         /*
1869          * CPU capacity of this group, SCHED_CAPACITY_SCALE being max capacity
1870          * for a single CPU.
1871          */
1872         unsigned long           capacity;
1873         unsigned long           min_capacity;           /* Min per-CPU capacity in group */
1874         unsigned long           max_capacity;           /* Max per-CPU capacity in group */
1875         unsigned long           next_update;
1876         int                     imbalance;              /* XXX unrelated to capacity but shared group state */
1877
1878 #ifdef CONFIG_SCHED_DEBUG
1879         int                     id;
1880 #endif
1881
1882         unsigned long           cpumask[];              /* Balance mask */
1883 };
1884
1885 struct sched_group {
1886         struct sched_group      *next;                  /* Must be a circular list */
1887         atomic_t                ref;
1888
1889         unsigned int            group_weight;
1890         unsigned int            cores;
1891         struct sched_group_capacity *sgc;
1892         int                     asym_prefer_cpu;        /* CPU of highest priority in group */
1893         int                     flags;
1894
1895         /*
1896          * The CPUs this group covers.
1897          *
1898          * NOTE: this field is variable length. (Allocated dynamically
1899          * by attaching extra space to the end of the structure,
1900          * depending on how many CPUs the kernel has booted up with)
1901          */
1902         unsigned long           cpumask[];
1903 };
1904
1905 static inline struct cpumask *sched_group_span(struct sched_group *sg)
1906 {
1907         return to_cpumask(sg->cpumask);
1908 }
1909
1910 /*
1911  * See build_balance_mask().
1912  */
1913 static inline struct cpumask *group_balance_mask(struct sched_group *sg)
1914 {
1915         return to_cpumask(sg->sgc->cpumask);
1916 }
1917
1918 extern int group_balance_cpu(struct sched_group *sg);
1919
1920 #ifdef CONFIG_SCHED_DEBUG
1921 void update_sched_domain_debugfs(void);
1922 void dirty_sched_domain_sysctl(int cpu);
1923 #else
1924 static inline void update_sched_domain_debugfs(void)
1925 {
1926 }
1927 static inline void dirty_sched_domain_sysctl(int cpu)
1928 {
1929 }
1930 #endif
1931
1932 extern int sched_update_scaling(void);
1933
1934 static inline const struct cpumask *task_user_cpus(struct task_struct *p)
1935 {
1936         if (!p->user_cpus_ptr)
1937                 return cpu_possible_mask; /* &init_task.cpus_mask */
1938         return p->user_cpus_ptr;
1939 }
1940 #endif /* CONFIG_SMP */
1941
1942 #include "stats.h"
1943
1944 #if defined(CONFIG_SCHED_CORE) && defined(CONFIG_SCHEDSTATS)
1945
1946 extern void __sched_core_account_forceidle(struct rq *rq);
1947
1948 static inline void sched_core_account_forceidle(struct rq *rq)
1949 {
1950         if (schedstat_enabled())
1951                 __sched_core_account_forceidle(rq);
1952 }
1953
1954 extern void __sched_core_tick(struct rq *rq);
1955
1956 static inline void sched_core_tick(struct rq *rq)
1957 {
1958         if (sched_core_enabled(rq) && schedstat_enabled())
1959                 __sched_core_tick(rq);
1960 }
1961
1962 #else
1963
1964 static inline void sched_core_account_forceidle(struct rq *rq) {}
1965
1966 static inline void sched_core_tick(struct rq *rq) {}
1967
1968 #endif /* CONFIG_SCHED_CORE && CONFIG_SCHEDSTATS */
1969
1970 #ifdef CONFIG_CGROUP_SCHED
1971
1972 /*
1973  * Return the group to which this tasks belongs.
1974  *
1975  * We cannot use task_css() and friends because the cgroup subsystem
1976  * changes that value before the cgroup_subsys::attach() method is called,
1977  * therefore we cannot pin it and might observe the wrong value.
1978  *
1979  * The same is true for autogroup's p->signal->autogroup->tg, the autogroup
1980  * core changes this before calling sched_move_task().
1981  *
1982  * Instead we use a 'copy' which is updated from sched_move_task() while
1983  * holding both task_struct::pi_lock and rq::lock.
1984  */
1985 static inline struct task_group *task_group(struct task_struct *p)
1986 {
1987         return p->sched_task_group;
1988 }
1989
1990 /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
1991 static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
1992 {
1993 #if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED)
1994         struct task_group *tg = task_group(p);
1995 #endif
1996
1997 #ifdef CONFIG_FAIR_GROUP_SCHED
1998         set_task_rq_fair(&p->se, p->se.cfs_rq, tg->cfs_rq[cpu]);
1999         p->se.cfs_rq = tg->cfs_rq[cpu];
2000         p->se.parent = tg->se[cpu];
2001         p->se.depth = tg->se[cpu] ? tg->se[cpu]->depth + 1 : 0;
2002 #endif
2003
2004 #ifdef CONFIG_RT_GROUP_SCHED
2005         p->rt.rt_rq  = tg->rt_rq[cpu];
2006         p->rt.parent = tg->rt_se[cpu];
2007 #endif
2008 }
2009
2010 #else /* CONFIG_CGROUP_SCHED */
2011
2012 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
2013 static inline struct task_group *task_group(struct task_struct *p)
2014 {
2015         return NULL;
2016 }
2017
2018 #endif /* CONFIG_CGROUP_SCHED */
2019
2020 static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
2021 {
2022         set_task_rq(p, cpu);
2023 #ifdef CONFIG_SMP
2024         /*
2025          * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
2026          * successfully executed on another CPU. We must ensure that updates of
2027          * per-task data have been completed by this moment.
2028          */
2029         smp_wmb();
2030         WRITE_ONCE(task_thread_info(p)->cpu, cpu);
2031         p->wake_cpu = cpu;
2032 #endif
2033 }
2034
2035 /*
2036  * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
2037  */
2038 #ifdef CONFIG_SCHED_DEBUG
2039 # define const_debug __read_mostly
2040 #else
2041 # define const_debug const
2042 #endif
2043
2044 #define SCHED_FEAT(name, enabled)       \
2045         __SCHED_FEAT_##name ,
2046
2047 enum {
2048 #include "features.h"
2049         __SCHED_FEAT_NR,
2050 };
2051
2052 #undef SCHED_FEAT
2053
2054 #ifdef CONFIG_SCHED_DEBUG
2055
2056 /*
2057  * To support run-time toggling of sched features, all the translation units
2058  * (but core.c) reference the sysctl_sched_features defined in core.c.
2059  */
2060 extern const_debug unsigned int sysctl_sched_features;
2061
2062 #ifdef CONFIG_JUMP_LABEL
2063 #define SCHED_FEAT(name, enabled)                                       \
2064 static __always_inline bool static_branch_##name(struct static_key *key) \
2065 {                                                                       \
2066         return static_key_##enabled(key);                               \
2067 }
2068
2069 #include "features.h"
2070 #undef SCHED_FEAT
2071
2072 extern struct static_key sched_feat_keys[__SCHED_FEAT_NR];
2073 #define sched_feat(x) (static_branch_##x(&sched_feat_keys[__SCHED_FEAT_##x]))
2074
2075 #else /* !CONFIG_JUMP_LABEL */
2076
2077 #define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
2078
2079 #endif /* CONFIG_JUMP_LABEL */
2080
2081 #else /* !SCHED_DEBUG */
2082
2083 /*
2084  * Each translation unit has its own copy of sysctl_sched_features to allow
2085  * constants propagation at compile time and compiler optimization based on
2086  * features default.
2087  */
2088 #define SCHED_FEAT(name, enabled)       \
2089         (1UL << __SCHED_FEAT_##name) * enabled |
2090 static const_debug __maybe_unused unsigned int sysctl_sched_features =
2091 #include "features.h"
2092         0;
2093 #undef SCHED_FEAT
2094
2095 #define sched_feat(x) !!(sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
2096
2097 #endif /* SCHED_DEBUG */
2098
2099 extern struct static_key_false sched_numa_balancing;
2100 extern struct static_key_false sched_schedstats;
2101
2102 static inline u64 global_rt_period(void)
2103 {
2104         return (u64)sysctl_sched_rt_period * NSEC_PER_USEC;
2105 }
2106
2107 static inline u64 global_rt_runtime(void)
2108 {
2109         if (sysctl_sched_rt_runtime < 0)
2110                 return RUNTIME_INF;
2111
2112         return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
2113 }
2114
2115 static inline int task_current(struct rq *rq, struct task_struct *p)
2116 {
2117         return rq->curr == p;
2118 }
2119
2120 static inline int task_on_cpu(struct rq *rq, struct task_struct *p)
2121 {
2122 #ifdef CONFIG_SMP
2123         return p->on_cpu;
2124 #else
2125         return task_current(rq, p);
2126 #endif
2127 }
2128
2129 static inline int task_on_rq_queued(struct task_struct *p)
2130 {
2131         return p->on_rq == TASK_ON_RQ_QUEUED;
2132 }
2133
2134 static inline int task_on_rq_migrating(struct task_struct *p)
2135 {
2136         return READ_ONCE(p->on_rq) == TASK_ON_RQ_MIGRATING;
2137 }
2138
2139 /* Wake flags. The first three directly map to some SD flag value */
2140 #define WF_EXEC         0x02 /* Wakeup after exec; maps to SD_BALANCE_EXEC */
2141 #define WF_FORK         0x04 /* Wakeup after fork; maps to SD_BALANCE_FORK */
2142 #define WF_TTWU         0x08 /* Wakeup;            maps to SD_BALANCE_WAKE */
2143
2144 #define WF_SYNC         0x10 /* Waker goes to sleep after wakeup */
2145 #define WF_MIGRATED     0x20 /* Internal use, task got migrated */
2146 #define WF_CURRENT_CPU  0x40 /* Prefer to move the wakee to the current CPU. */
2147
2148 #ifdef CONFIG_SMP
2149 static_assert(WF_EXEC == SD_BALANCE_EXEC);
2150 static_assert(WF_FORK == SD_BALANCE_FORK);
2151 static_assert(WF_TTWU == SD_BALANCE_WAKE);
2152 #endif
2153
2154 /*
2155  * To aid in avoiding the subversion of "niceness" due to uneven distribution
2156  * of tasks with abnormal "nice" values across CPUs the contribution that
2157  * each task makes to its run queue's load is weighted according to its
2158  * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
2159  * scaled version of the new time slice allocation that they receive on time
2160  * slice expiry etc.
2161  */
2162
2163 #define WEIGHT_IDLEPRIO         3
2164 #define WMULT_IDLEPRIO          1431655765
2165
2166 extern const int                sched_prio_to_weight[40];
2167 extern const u32                sched_prio_to_wmult[40];
2168
2169 /*
2170  * {de,en}queue flags:
2171  *
2172  * DEQUEUE_SLEEP  - task is no longer runnable
2173  * ENQUEUE_WAKEUP - task just became runnable
2174  *
2175  * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks
2176  *                are in a known state which allows modification. Such pairs
2177  *                should preserve as much state as possible.
2178  *
2179  * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
2180  *        in the runqueue.
2181  *
2182  * ENQUEUE_HEAD      - place at front of runqueue (tail if not specified)
2183  * ENQUEUE_REPLENISH - CBS (replenish runtime and postpone deadline)
2184  * ENQUEUE_MIGRATED  - the task was migrated during wakeup
2185  *
2186  */
2187
2188 #define DEQUEUE_SLEEP           0x01
2189 #define DEQUEUE_SAVE            0x02 /* Matches ENQUEUE_RESTORE */
2190 #define DEQUEUE_MOVE            0x04 /* Matches ENQUEUE_MOVE */
2191 #define DEQUEUE_NOCLOCK         0x08 /* Matches ENQUEUE_NOCLOCK */
2192
2193 #define ENQUEUE_WAKEUP          0x01
2194 #define ENQUEUE_RESTORE         0x02
2195 #define ENQUEUE_MOVE            0x04
2196 #define ENQUEUE_NOCLOCK         0x08
2197
2198 #define ENQUEUE_HEAD            0x10
2199 #define ENQUEUE_REPLENISH       0x20
2200 #ifdef CONFIG_SMP
2201 #define ENQUEUE_MIGRATED        0x40
2202 #else
2203 #define ENQUEUE_MIGRATED        0x00
2204 #endif
2205 #define ENQUEUE_INITIAL         0x80
2206
2207 #define RETRY_TASK              ((void *)-1UL)
2208
2209 struct affinity_context {
2210         const struct cpumask *new_mask;
2211         struct cpumask *user_mask;
2212         unsigned int flags;
2213 };
2214
2215 struct sched_class {
2216
2217 #ifdef CONFIG_UCLAMP_TASK
2218         int uclamp_enabled;
2219 #endif
2220
2221         void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
2222         void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
2223         void (*yield_task)   (struct rq *rq);
2224         bool (*yield_to_task)(struct rq *rq, struct task_struct *p);
2225
2226         void (*wakeup_preempt)(struct rq *rq, struct task_struct *p, int flags);
2227
2228         struct task_struct *(*pick_next_task)(struct rq *rq);
2229
2230         void (*put_prev_task)(struct rq *rq, struct task_struct *p);
2231         void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
2232
2233 #ifdef CONFIG_SMP
2234         int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
2235         int  (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);
2236
2237         struct task_struct * (*pick_task)(struct rq *rq);
2238
2239         void (*migrate_task_rq)(struct task_struct *p, int new_cpu);
2240
2241         void (*task_woken)(struct rq *this_rq, struct task_struct *task);
2242
2243         void (*set_cpus_allowed)(struct task_struct *p, struct affinity_context *ctx);
2244
2245         void (*rq_online)(struct rq *rq);
2246         void (*rq_offline)(struct rq *rq);
2247
2248         struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);
2249 #endif
2250
2251         void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
2252         void (*task_fork)(struct task_struct *p);
2253         void (*task_dead)(struct task_struct *p);
2254
2255         /*
2256          * The switched_from() call is allowed to drop rq->lock, therefore we
2257          * cannot assume the switched_from/switched_to pair is serialized by
2258          * rq->lock. They are however serialized by p->pi_lock.
2259          */
2260         void (*switched_from)(struct rq *this_rq, struct task_struct *task);
2261         void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
2262         void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
2263                               int oldprio);
2264
2265         unsigned int (*get_rr_interval)(struct rq *rq,
2266                                         struct task_struct *task);
2267
2268         void (*update_curr)(struct rq *rq);
2269
2270 #ifdef CONFIG_FAIR_GROUP_SCHED
2271         void (*task_change_group)(struct task_struct *p);
2272 #endif
2273
2274 #ifdef CONFIG_SCHED_CORE
2275         int (*task_is_throttled)(struct task_struct *p, int cpu);
2276 #endif
2277 };
2278
2279 static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
2280 {
2281         WARN_ON_ONCE(rq->curr != prev);
2282         prev->sched_class->put_prev_task(rq, prev);
2283 }
2284
2285 static inline void set_next_task(struct rq *rq, struct task_struct *next)
2286 {
2287         next->sched_class->set_next_task(rq, next, false);
2288 }
2289
2290
2291 /*
2292  * Helper to define a sched_class instance; each one is placed in a separate
2293  * section which is ordered by the linker script:
2294  *
2295  *   include/asm-generic/vmlinux.lds.h
2296  *
2297  * *CAREFUL* they are laid out in *REVERSE* order!!!
2298  *
2299  * Also enforce alignment on the instance, not the type, to guarantee layout.
2300  */
2301 #define DEFINE_SCHED_CLASS(name) \
2302 const struct sched_class name##_sched_class \
2303         __aligned(__alignof__(struct sched_class)) \
2304         __section("__" #name "_sched_class")
2305
2306 /* Defined in include/asm-generic/vmlinux.lds.h */
2307 extern struct sched_class __sched_class_highest[];
2308 extern struct sched_class __sched_class_lowest[];
2309
2310 #define for_class_range(class, _from, _to) \
2311         for (class = (_from); class < (_to); class++)
2312
2313 #define for_each_class(class) \
2314         for_class_range(class, __sched_class_highest, __sched_class_lowest)
2315
2316 #define sched_class_above(_a, _b)       ((_a) < (_b))
2317
2318 extern const struct sched_class stop_sched_class;
2319 extern const struct sched_class dl_sched_class;
2320 extern const struct sched_class rt_sched_class;
2321 extern const struct sched_class fair_sched_class;
2322 extern const struct sched_class idle_sched_class;
2323
2324 static inline bool sched_stop_runnable(struct rq *rq)
2325 {
2326         return rq->stop && task_on_rq_queued(rq->stop);
2327 }
2328
2329 static inline bool sched_dl_runnable(struct rq *rq)
2330 {
2331         return rq->dl.dl_nr_running > 0;
2332 }
2333
2334 static inline bool sched_rt_runnable(struct rq *rq)
2335 {
2336         return rq->rt.rt_queued > 0;
2337 }
2338
2339 static inline bool sched_fair_runnable(struct rq *rq)
2340 {
2341         return rq->cfs.nr_running > 0;
2342 }
2343
2344 extern struct task_struct *pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
2345 extern struct task_struct *pick_next_task_idle(struct rq *rq);
2346
2347 #define SCA_CHECK               0x01
2348 #define SCA_MIGRATE_DISABLE     0x02
2349 #define SCA_MIGRATE_ENABLE      0x04
2350 #define SCA_USER                0x08
2351
2352 #ifdef CONFIG_SMP
2353
2354 extern void update_group_capacity(struct sched_domain *sd, int cpu);
2355
2356 extern void trigger_load_balance(struct rq *rq);
2357
2358 extern void set_cpus_allowed_common(struct task_struct *p, struct affinity_context *ctx);
2359
2360 static inline struct task_struct *get_push_task(struct rq *rq)
2361 {
2362         struct task_struct *p = rq->curr;
2363
2364         lockdep_assert_rq_held(rq);
2365
2366         if (rq->push_busy)
2367                 return NULL;
2368
2369         if (p->nr_cpus_allowed == 1)
2370                 return NULL;
2371
2372         if (p->migration_disabled)
2373                 return NULL;
2374
2375         rq->push_busy = true;
2376         return get_task_struct(p);
2377 }
2378
2379 extern int push_cpu_stop(void *arg);
2380
2381 #endif
2382
2383 #ifdef CONFIG_CPU_IDLE
2384 static inline void idle_set_state(struct rq *rq,
2385                                   struct cpuidle_state *idle_state)
2386 {
2387         rq->idle_state = idle_state;
2388 }
2389
2390 static inline struct cpuidle_state *idle_get_state(struct rq *rq)
2391 {
2392         SCHED_WARN_ON(!rcu_read_lock_held());
2393
2394         return rq->idle_state;
2395 }
2396 #else
2397 static inline void idle_set_state(struct rq *rq,
2398                                   struct cpuidle_state *idle_state)
2399 {
2400 }
2401
2402 static inline struct cpuidle_state *idle_get_state(struct rq *rq)
2403 {
2404         return NULL;
2405 }
2406 #endif
2407
2408 extern void schedule_idle(void);
2409 asmlinkage void schedule_user(void);
2410
2411 extern void sysrq_sched_debug_show(void);
2412 extern void sched_init_granularity(void);
2413 extern void update_max_interval(void);
2414
2415 extern void init_sched_dl_class(void);
2416 extern void init_sched_rt_class(void);
2417 extern void init_sched_fair_class(void);
2418
2419 extern void reweight_task(struct task_struct *p, int prio);
2420
2421 extern void resched_curr(struct rq *rq);
2422 extern void resched_cpu(int cpu);
2423
2424 extern struct rt_bandwidth def_rt_bandwidth;
2425 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
2426 extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
2427
2428 extern void init_dl_task_timer(struct sched_dl_entity *dl_se);
2429 extern void init_dl_inactive_task_timer(struct sched_dl_entity *dl_se);
2430
2431 #define BW_SHIFT                20
2432 #define BW_UNIT                 (1 << BW_SHIFT)
2433 #define RATIO_SHIFT             8
2434 #define MAX_BW_BITS             (64 - BW_SHIFT)
2435 #define MAX_BW                  ((1ULL << MAX_BW_BITS) - 1)
2436 unsigned long to_ratio(u64 period, u64 runtime);
2437
2438 extern void init_entity_runnable_average(struct sched_entity *se);
2439 extern void post_init_entity_util_avg(struct task_struct *p);
2440
2441 #ifdef CONFIG_NO_HZ_FULL
2442 extern bool sched_can_stop_tick(struct rq *rq);
2443 extern int __init sched_tick_offload_init(void);
2444
2445 /*
2446  * Tick may be needed by tasks in the runqueue depending on their policy and
2447  * requirements. If tick is needed, lets send the target an IPI to kick it out of
2448  * nohz mode if necessary.
2449  */
2450 static inline void sched_update_tick_dependency(struct rq *rq)
2451 {
2452         int cpu = cpu_of(rq);
2453
2454         if (!tick_nohz_full_cpu(cpu))
2455                 return;
2456
2457         if (sched_can_stop_tick(rq))
2458                 tick_nohz_dep_clear_cpu(cpu, TICK_DEP_BIT_SCHED);
2459         else
2460                 tick_nohz_dep_set_cpu(cpu, TICK_DEP_BIT_SCHED);
2461 }
2462 #else
2463 static inline int sched_tick_offload_init(void) { return 0; }
2464 static inline void sched_update_tick_dependency(struct rq *rq) { }
2465 #endif
2466
2467 static inline void add_nr_running(struct rq *rq, unsigned count)
2468 {
2469         unsigned prev_nr = rq->nr_running;
2470
2471         rq->nr_running = prev_nr + count;
2472         if (trace_sched_update_nr_running_tp_enabled()) {
2473                 call_trace_sched_update_nr_running(rq, count);
2474         }
2475
2476 #ifdef CONFIG_SMP
2477         if (prev_nr < 2 && rq->nr_running >= 2) {
2478                 if (!READ_ONCE(rq->rd->overload))
2479                         WRITE_ONCE(rq->rd->overload, 1);
2480         }
2481 #endif
2482
2483         sched_update_tick_dependency(rq);
2484 }
2485
2486 static inline void sub_nr_running(struct rq *rq, unsigned count)
2487 {
2488         rq->nr_running -= count;
2489         if (trace_sched_update_nr_running_tp_enabled()) {
2490                 call_trace_sched_update_nr_running(rq, -count);
2491         }
2492
2493         /* Check if we still need preemption */
2494         sched_update_tick_dependency(rq);
2495 }
2496
2497 extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
2498 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
2499
2500 extern void wakeup_preempt(struct rq *rq, struct task_struct *p, int flags);
2501
2502 #ifdef CONFIG_PREEMPT_RT
2503 #define SCHED_NR_MIGRATE_BREAK 8
2504 #else
2505 #define SCHED_NR_MIGRATE_BREAK 32
2506 #endif
2507
2508 extern const_debug unsigned int sysctl_sched_nr_migrate;
2509 extern const_debug unsigned int sysctl_sched_migration_cost;
2510
2511 extern unsigned int sysctl_sched_base_slice;
2512
2513 #ifdef CONFIG_SCHED_DEBUG
2514 extern int sysctl_resched_latency_warn_ms;
2515 extern int sysctl_resched_latency_warn_once;
2516
2517 extern unsigned int sysctl_sched_tunable_scaling;
2518
2519 extern unsigned int sysctl_numa_balancing_scan_delay;
2520 extern unsigned int sysctl_numa_balancing_scan_period_min;
2521 extern unsigned int sysctl_numa_balancing_scan_period_max;
2522 extern unsigned int sysctl_numa_balancing_scan_size;
2523 extern unsigned int sysctl_numa_balancing_hot_threshold;
2524 #endif
2525
2526 #ifdef CONFIG_SCHED_HRTICK
2527
2528 /*
2529  * Use hrtick when:
2530  *  - enabled by features
2531  *  - hrtimer is actually high res
2532  */
2533 static inline int hrtick_enabled(struct rq *rq)
2534 {
2535         if (!cpu_active(cpu_of(rq)))
2536                 return 0;
2537         return hrtimer_is_hres_active(&rq->hrtick_timer);
2538 }
2539
2540 static inline int hrtick_enabled_fair(struct rq *rq)
2541 {
2542         if (!sched_feat(HRTICK))
2543                 return 0;
2544         return hrtick_enabled(rq);
2545 }
2546
2547 static inline int hrtick_enabled_dl(struct rq *rq)
2548 {
2549         if (!sched_feat(HRTICK_DL))
2550                 return 0;
2551         return hrtick_enabled(rq);
2552 }
2553
2554 void hrtick_start(struct rq *rq, u64 delay);
2555
2556 #else
2557
2558 static inline int hrtick_enabled_fair(struct rq *rq)
2559 {
2560         return 0;
2561 }
2562
2563 static inline int hrtick_enabled_dl(struct rq *rq)
2564 {
2565         return 0;
2566 }
2567
2568 static inline int hrtick_enabled(struct rq *rq)
2569 {
2570         return 0;
2571 }
2572
2573 #endif /* CONFIG_SCHED_HRTICK */
2574
2575 #ifndef arch_scale_freq_tick
2576 static __always_inline
2577 void arch_scale_freq_tick(void)
2578 {
2579 }
2580 #endif
2581
2582 #ifndef arch_scale_freq_capacity
2583 /**
2584  * arch_scale_freq_capacity - get the frequency scale factor of a given CPU.
2585  * @cpu: the CPU in question.
2586  *
2587  * Return: the frequency scale factor normalized against SCHED_CAPACITY_SCALE, i.e.
2588  *
2589  *     f_curr
2590  *     ------ * SCHED_CAPACITY_SCALE
2591  *     f_max
2592  */
2593 static __always_inline
2594 unsigned long arch_scale_freq_capacity(int cpu)
2595 {
2596         return SCHED_CAPACITY_SCALE;
2597 }
2598 #endif
2599
2600 #ifdef CONFIG_SCHED_DEBUG
2601 /*
2602  * In double_lock_balance()/double_rq_lock(), we use raw_spin_rq_lock() to
2603  * acquire rq lock instead of rq_lock(). So at the end of these two functions
2604  * we need to call double_rq_clock_clear_update() to clear RQCF_UPDATED of
2605  * rq->clock_update_flags to avoid the WARN_DOUBLE_CLOCK warning.
2606  */
2607 static inline void double_rq_clock_clear_update(struct rq *rq1, struct rq *rq2)
2608 {
2609         rq1->clock_update_flags &= (RQCF_REQ_SKIP|RQCF_ACT_SKIP);
2610         /* rq1 == rq2 for !CONFIG_SMP, so just clear RQCF_UPDATED once. */
2611 #ifdef CONFIG_SMP
2612         rq2->clock_update_flags &= (RQCF_REQ_SKIP|RQCF_ACT_SKIP);
2613 #endif
2614 }
2615 #else
2616 static inline void double_rq_clock_clear_update(struct rq *rq1, struct rq *rq2) {}
2617 #endif
2618
2619 #define DEFINE_LOCK_GUARD_2(name, type, _lock, _unlock, ...)            \
2620 __DEFINE_UNLOCK_GUARD(name, type, _unlock, type *lock2; __VA_ARGS__) \
2621 static inline class_##name##_t class_##name##_constructor(type *lock, type *lock2) \
2622 { class_##name##_t _t = { .lock = lock, .lock2 = lock2 }, *_T = &_t;    \
2623   _lock; return _t; }
2624
2625 #ifdef CONFIG_SMP
2626
2627 static inline bool rq_order_less(struct rq *rq1, struct rq *rq2)
2628 {
2629 #ifdef CONFIG_SCHED_CORE
2630         /*
2631          * In order to not have {0,2},{1,3} turn into into an AB-BA,
2632          * order by core-id first and cpu-id second.
2633          *
2634          * Notably:
2635          *
2636          *      double_rq_lock(0,3); will take core-0, core-1 lock
2637          *      double_rq_lock(1,2); will take core-1, core-0 lock
2638          *
2639          * when only cpu-id is considered.
2640          */
2641         if (rq1->core->cpu < rq2->core->cpu)
2642                 return true;
2643         if (rq1->core->cpu > rq2->core->cpu)
2644                 return false;
2645
2646         /*
2647          * __sched_core_flip() relies on SMT having cpu-id lock order.
2648          */
2649 #endif
2650         return rq1->cpu < rq2->cpu;
2651 }
2652
2653 extern void double_rq_lock(struct rq *rq1, struct rq *rq2);
2654
2655 #ifdef CONFIG_PREEMPTION
2656
2657 /*
2658  * fair double_lock_balance: Safely acquires both rq->locks in a fair
2659  * way at the expense of forcing extra atomic operations in all
2660  * invocations.  This assures that the double_lock is acquired using the
2661  * same underlying policy as the spinlock_t on this architecture, which
2662  * reduces latency compared to the unfair variant below.  However, it
2663  * also adds more overhead and therefore may reduce throughput.
2664  */
2665 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
2666         __releases(this_rq->lock)
2667         __acquires(busiest->lock)
2668         __acquires(this_rq->lock)
2669 {
2670         raw_spin_rq_unlock(this_rq);
2671         double_rq_lock(this_rq, busiest);
2672
2673         return 1;
2674 }
2675
2676 #else
2677 /*
2678  * Unfair double_lock_balance: Optimizes throughput at the expense of
2679  * latency by eliminating extra atomic operations when the locks are
2680  * already in proper order on entry.  This favors lower CPU-ids and will
2681  * grant the double lock to lower CPUs over higher ids under contention,
2682  * regardless of entry order into the function.
2683  */
2684 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
2685         __releases(this_rq->lock)
2686         __acquires(busiest->lock)
2687         __acquires(this_rq->lock)
2688 {
2689         if (__rq_lockp(this_rq) == __rq_lockp(busiest) ||
2690             likely(raw_spin_rq_trylock(busiest))) {
2691                 double_rq_clock_clear_update(this_rq, busiest);
2692                 return 0;
2693         }
2694
2695         if (rq_order_less(this_rq, busiest)) {
2696                 raw_spin_rq_lock_nested(busiest, SINGLE_DEPTH_NESTING);
2697                 double_rq_clock_clear_update(this_rq, busiest);
2698                 return 0;
2699         }
2700
2701         raw_spin_rq_unlock(this_rq);
2702         double_rq_lock(this_rq, busiest);
2703
2704         return 1;
2705 }
2706
2707 #endif /* CONFIG_PREEMPTION */
2708
2709 /*
2710  * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
2711  */
2712 static inline int double_lock_balance(struct rq *this_rq, struct rq *busiest)
2713 {
2714         lockdep_assert_irqs_disabled();
2715
2716         return _double_lock_balance(this_rq, busiest);
2717 }
2718
2719 static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
2720         __releases(busiest->lock)
2721 {
2722         if (__rq_lockp(this_rq) != __rq_lockp(busiest))
2723                 raw_spin_rq_unlock(busiest);
2724         lock_set_subclass(&__rq_lockp(this_rq)->dep_map, 0, _RET_IP_);
2725 }
2726
2727 static inline void double_lock(spinlock_t *l1, spinlock_t *l2)
2728 {
2729         if (l1 > l2)
2730                 swap(l1, l2);
2731
2732         spin_lock(l1);
2733         spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
2734 }
2735
2736 static inline void double_lock_irq(spinlock_t *l1, spinlock_t *l2)
2737 {
2738         if (l1 > l2)
2739                 swap(l1, l2);
2740
2741         spin_lock_irq(l1);
2742         spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
2743 }
2744
2745 static inline void double_raw_lock(raw_spinlock_t *l1, raw_spinlock_t *l2)
2746 {
2747         if (l1 > l2)
2748                 swap(l1, l2);
2749
2750         raw_spin_lock(l1);
2751         raw_spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
2752 }
2753
2754 static inline void double_raw_unlock(raw_spinlock_t *l1, raw_spinlock_t *l2)
2755 {
2756         raw_spin_unlock(l1);
2757         raw_spin_unlock(l2);
2758 }
2759
2760 DEFINE_LOCK_GUARD_2(double_raw_spinlock, raw_spinlock_t,
2761                     double_raw_lock(_T->lock, _T->lock2),
2762                     double_raw_unlock(_T->lock, _T->lock2))
2763
2764 /*
2765  * double_rq_unlock - safely unlock two runqueues
2766  *
2767  * Note this does not restore interrupts like task_rq_unlock,
2768  * you need to do so manually after calling.
2769  */
2770 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
2771         __releases(rq1->lock)
2772         __releases(rq2->lock)
2773 {
2774         if (__rq_lockp(rq1) != __rq_lockp(rq2))
2775                 raw_spin_rq_unlock(rq2);
2776         else
2777                 __release(rq2->lock);
2778         raw_spin_rq_unlock(rq1);
2779 }
2780
2781 extern void set_rq_online (struct rq *rq);
2782 extern void set_rq_offline(struct rq *rq);
2783 extern bool sched_smp_initialized;
2784
2785 #else /* CONFIG_SMP */
2786
2787 /*
2788  * double_rq_lock - safely lock two runqueues
2789  *
2790  * Note this does not disable interrupts like task_rq_lock,
2791  * you need to do so manually before calling.
2792  */
2793 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
2794         __acquires(rq1->lock)
2795         __acquires(rq2->lock)
2796 {
2797         WARN_ON_ONCE(!irqs_disabled());
2798         WARN_ON_ONCE(rq1 != rq2);
2799         raw_spin_rq_lock(rq1);
2800         __acquire(rq2->lock);   /* Fake it out ;) */
2801         double_rq_clock_clear_update(rq1, rq2);
2802 }
2803
2804 /*
2805  * double_rq_unlock - safely unlock two runqueues
2806  *
2807  * Note this does not restore interrupts like task_rq_unlock,
2808  * you need to do so manually after calling.
2809  */
2810 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
2811         __releases(rq1->lock)
2812         __releases(rq2->lock)
2813 {
2814         WARN_ON_ONCE(rq1 != rq2);
2815         raw_spin_rq_unlock(rq1);
2816         __release(rq2->lock);
2817 }
2818
2819 #endif
2820
2821 DEFINE_LOCK_GUARD_2(double_rq_lock, struct rq,
2822                     double_rq_lock(_T->lock, _T->lock2),
2823                     double_rq_unlock(_T->lock, _T->lock2))
2824
2825 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq);
2826 extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq);
2827
2828 #ifdef  CONFIG_SCHED_DEBUG
2829 extern bool sched_debug_verbose;
2830
2831 extern void print_cfs_stats(struct seq_file *m, int cpu);
2832 extern void print_rt_stats(struct seq_file *m, int cpu);
2833 extern void print_dl_stats(struct seq_file *m, int cpu);
2834 extern void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq);
2835 extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
2836 extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
2837
2838 extern void resched_latency_warn(int cpu, u64 latency);
2839 #ifdef CONFIG_NUMA_BALANCING
2840 extern void
2841 show_numa_stats(struct task_struct *p, struct seq_file *m);
2842 extern void
2843 print_numa_stats(struct seq_file *m, int node, unsigned long tsf,
2844         unsigned long tpf, unsigned long gsf, unsigned long gpf);
2845 #endif /* CONFIG_NUMA_BALANCING */
2846 #else
2847 static inline void resched_latency_warn(int cpu, u64 latency) {}
2848 #endif /* CONFIG_SCHED_DEBUG */
2849
2850 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
2851 extern void init_rt_rq(struct rt_rq *rt_rq);
2852 extern void init_dl_rq(struct dl_rq *dl_rq);
2853
2854 extern void cfs_bandwidth_usage_inc(void);
2855 extern void cfs_bandwidth_usage_dec(void);
2856
2857 #ifdef CONFIG_NO_HZ_COMMON
2858 #define NOHZ_BALANCE_KICK_BIT   0
2859 #define NOHZ_STATS_KICK_BIT     1
2860 #define NOHZ_NEWILB_KICK_BIT    2
2861 #define NOHZ_NEXT_KICK_BIT      3
2862
2863 /* Run rebalance_domains() */
2864 #define NOHZ_BALANCE_KICK       BIT(NOHZ_BALANCE_KICK_BIT)
2865 /* Update blocked load */
2866 #define NOHZ_STATS_KICK         BIT(NOHZ_STATS_KICK_BIT)
2867 /* Update blocked load when entering idle */
2868 #define NOHZ_NEWILB_KICK        BIT(NOHZ_NEWILB_KICK_BIT)
2869 /* Update nohz.next_balance */
2870 #define NOHZ_NEXT_KICK          BIT(NOHZ_NEXT_KICK_BIT)
2871
2872 #define NOHZ_KICK_MASK  (NOHZ_BALANCE_KICK | NOHZ_STATS_KICK | NOHZ_NEXT_KICK)
2873
2874 #define nohz_flags(cpu) (&cpu_rq(cpu)->nohz_flags)
2875
2876 extern void nohz_balance_exit_idle(struct rq *rq);
2877 #else
2878 static inline void nohz_balance_exit_idle(struct rq *rq) { }
2879 #endif
2880
2881 #if defined(CONFIG_SMP) && defined(CONFIG_NO_HZ_COMMON)
2882 extern void nohz_run_idle_balance(int cpu);
2883 #else
2884 static inline void nohz_run_idle_balance(int cpu) { }
2885 #endif
2886
2887 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
2888 struct irqtime {
2889         u64                     total;
2890         u64                     tick_delta;
2891         u64                     irq_start_time;
2892         struct u64_stats_sync   sync;
2893 };
2894
2895 DECLARE_PER_CPU(struct irqtime, cpu_irqtime);
2896
2897 /*
2898  * Returns the irqtime minus the softirq time computed by ksoftirqd.
2899  * Otherwise ksoftirqd's sum_exec_runtime is subtracted its own runtime
2900  * and never move forward.
2901  */
2902 static inline u64 irq_time_read(int cpu)
2903 {
2904         struct irqtime *irqtime = &per_cpu(cpu_irqtime, cpu);
2905         unsigned int seq;
2906         u64 total;
2907
2908         do {
2909                 seq = __u64_stats_fetch_begin(&irqtime->sync);
2910                 total = irqtime->total;
2911         } while (__u64_stats_fetch_retry(&irqtime->sync, seq));
2912
2913         return total;
2914 }
2915 #endif /* CONFIG_IRQ_TIME_ACCOUNTING */
2916
2917 #ifdef CONFIG_CPU_FREQ
2918 DECLARE_PER_CPU(struct update_util_data __rcu *, cpufreq_update_util_data);
2919
2920 /**
2921  * cpufreq_update_util - Take a note about CPU utilization changes.
2922  * @rq: Runqueue to carry out the update for.
2923  * @flags: Update reason flags.
2924  *
2925  * This function is called by the scheduler on the CPU whose utilization is
2926  * being updated.
2927  *
2928  * It can only be called from RCU-sched read-side critical sections.
2929  *
2930  * The way cpufreq is currently arranged requires it to evaluate the CPU
2931  * performance state (frequency/voltage) on a regular basis to prevent it from
2932  * being stuck in a completely inadequate performance level for too long.
2933  * That is not guaranteed to happen if the updates are only triggered from CFS
2934  * and DL, though, because they may not be coming in if only RT tasks are
2935  * active all the time (or there are RT tasks only).
2936  *
2937  * As a workaround for that issue, this function is called periodically by the
2938  * RT sched class to trigger extra cpufreq updates to prevent it from stalling,
2939  * but that really is a band-aid.  Going forward it should be replaced with
2940  * solutions targeted more specifically at RT tasks.
2941  */
2942 static inline void cpufreq_update_util(struct rq *rq, unsigned int flags)
2943 {
2944         struct update_util_data *data;
2945
2946         data = rcu_dereference_sched(*per_cpu_ptr(&cpufreq_update_util_data,
2947                                                   cpu_of(rq)));
2948         if (data)
2949                 data->func(data, rq_clock(rq), flags);
2950 }
2951 #else
2952 static inline void cpufreq_update_util(struct rq *rq, unsigned int flags) {}
2953 #endif /* CONFIG_CPU_FREQ */
2954
2955 #ifdef arch_scale_freq_capacity
2956 # ifndef arch_scale_freq_invariant
2957 #  define arch_scale_freq_invariant()   true
2958 # endif
2959 #else
2960 # define arch_scale_freq_invariant()    false
2961 #endif
2962
2963 #ifdef CONFIG_SMP
2964 /**
2965  * enum cpu_util_type - CPU utilization type
2966  * @FREQUENCY_UTIL:     Utilization used to select frequency
2967  * @ENERGY_UTIL:        Utilization used during energy calculation
2968  *
2969  * The utilization signals of all scheduling classes (CFS/RT/DL) and IRQ time
2970  * need to be aggregated differently depending on the usage made of them. This
2971  * enum is used within effective_cpu_util() to differentiate the types of
2972  * utilization expected by the callers, and adjust the aggregation accordingly.
2973  */
2974 enum cpu_util_type {
2975         FREQUENCY_UTIL,
2976         ENERGY_UTIL,
2977 };
2978
2979 unsigned long effective_cpu_util(int cpu, unsigned long util_cfs,
2980                                  enum cpu_util_type type,
2981                                  struct task_struct *p);
2982
2983 /*
2984  * Verify the fitness of task @p to run on @cpu taking into account the
2985  * CPU original capacity and the runtime/deadline ratio of the task.
2986  *
2987  * The function will return true if the original capacity of @cpu is
2988  * greater than or equal to task's deadline density right shifted by
2989  * (BW_SHIFT - SCHED_CAPACITY_SHIFT) and false otherwise.
2990  */
2991 static inline bool dl_task_fits_capacity(struct task_struct *p, int cpu)
2992 {
2993         unsigned long cap = arch_scale_cpu_capacity(cpu);
2994
2995         return cap >= p->dl.dl_density >> (BW_SHIFT - SCHED_CAPACITY_SHIFT);
2996 }
2997
2998 static inline unsigned long cpu_bw_dl(struct rq *rq)
2999 {
3000         return (rq->dl.running_bw * SCHED_CAPACITY_SCALE) >> BW_SHIFT;
3001 }
3002
3003 static inline unsigned long cpu_util_dl(struct rq *rq)
3004 {
3005         return READ_ONCE(rq->avg_dl.util_avg);
3006 }
3007
3008
3009 extern unsigned long cpu_util_cfs(int cpu);
3010 extern unsigned long cpu_util_cfs_boost(int cpu);
3011
3012 static inline unsigned long cpu_util_rt(struct rq *rq)
3013 {
3014         return READ_ONCE(rq->avg_rt.util_avg);
3015 }
3016 #endif
3017
3018 #ifdef CONFIG_UCLAMP_TASK
3019 unsigned long uclamp_eff_value(struct task_struct *p, enum uclamp_id clamp_id);
3020
3021 static inline unsigned long uclamp_rq_get(struct rq *rq,
3022                                           enum uclamp_id clamp_id)
3023 {
3024         return READ_ONCE(rq->uclamp[clamp_id].value);
3025 }
3026
3027 static inline void uclamp_rq_set(struct rq *rq, enum uclamp_id clamp_id,
3028                                  unsigned int value)
3029 {
3030         WRITE_ONCE(rq->uclamp[clamp_id].value, value);
3031 }
3032
3033 static inline bool uclamp_rq_is_idle(struct rq *rq)
3034 {
3035         return rq->uclamp_flags & UCLAMP_FLAG_IDLE;
3036 }
3037
3038 /**
3039  * uclamp_rq_util_with - clamp @util with @rq and @p effective uclamp values.
3040  * @rq:         The rq to clamp against. Must not be NULL.
3041  * @util:       The util value to clamp.
3042  * @p:          The task to clamp against. Can be NULL if you want to clamp
3043  *              against @rq only.
3044  *
3045  * Clamps the passed @util to the max(@rq, @p) effective uclamp values.
3046  *
3047  * If sched_uclamp_used static key is disabled, then just return the util
3048  * without any clamping since uclamp aggregation at the rq level in the fast
3049  * path is disabled, rendering this operation a NOP.
3050  *
3051  * Use uclamp_eff_value() if you don't care about uclamp values at rq level. It
3052  * will return the correct effective uclamp value of the task even if the
3053  * static key is disabled.
3054  */
3055 static __always_inline
3056 unsigned long uclamp_rq_util_with(struct rq *rq, unsigned long util,
3057                                   struct task_struct *p)
3058 {
3059         unsigned long min_util = 0;
3060         unsigned long max_util = 0;
3061
3062         if (!static_branch_likely(&sched_uclamp_used))
3063                 return util;
3064
3065         if (p) {
3066                 min_util = uclamp_eff_value(p, UCLAMP_MIN);
3067                 max_util = uclamp_eff_value(p, UCLAMP_MAX);
3068
3069                 /*
3070                  * Ignore last runnable task's max clamp, as this task will
3071                  * reset it. Similarly, no need to read the rq's min clamp.
3072                  */
3073                 if (uclamp_rq_is_idle(rq))
3074                         goto out;
3075         }
3076
3077         min_util = max_t(unsigned long, min_util, uclamp_rq_get(rq, UCLAMP_MIN));
3078         max_util = max_t(unsigned long, max_util, uclamp_rq_get(rq, UCLAMP_MAX));
3079 out:
3080         /*
3081          * Since CPU's {min,max}_util clamps are MAX aggregated considering
3082          * RUNNABLE tasks with _different_ clamps, we can end up with an
3083          * inversion. Fix it now when the clamps are applied.
3084          */
3085         if (unlikely(min_util >= max_util))
3086                 return min_util;
3087
3088         return clamp(util, min_util, max_util);
3089 }
3090
3091 /* Is the rq being capped/throttled by uclamp_max? */
3092 static inline bool uclamp_rq_is_capped(struct rq *rq)
3093 {
3094         unsigned long rq_util;
3095         unsigned long max_util;
3096
3097         if (!static_branch_likely(&sched_uclamp_used))
3098                 return false;
3099
3100         rq_util = cpu_util_cfs(cpu_of(rq)) + cpu_util_rt(rq);
3101         max_util = READ_ONCE(rq->uclamp[UCLAMP_MAX].value);
3102
3103         return max_util != SCHED_CAPACITY_SCALE && rq_util >= max_util;
3104 }
3105
3106 /*
3107  * When uclamp is compiled in, the aggregation at rq level is 'turned off'
3108  * by default in the fast path and only gets turned on once userspace performs
3109  * an operation that requires it.
3110  *
3111  * Returns true if userspace opted-in to use uclamp and aggregation at rq level
3112  * hence is active.
3113  */
3114 static inline bool uclamp_is_used(void)
3115 {
3116         return static_branch_likely(&sched_uclamp_used);
3117 }
3118 #else /* CONFIG_UCLAMP_TASK */
3119 static inline unsigned long uclamp_eff_value(struct task_struct *p,
3120                                              enum uclamp_id clamp_id)
3121 {
3122         if (clamp_id == UCLAMP_MIN)
3123                 return 0;
3124
3125         return SCHED_CAPACITY_SCALE;
3126 }
3127
3128 static inline
3129 unsigned long uclamp_rq_util_with(struct rq *rq, unsigned long util,
3130                                   struct task_struct *p)
3131 {
3132         return util;
3133 }
3134
3135 static inline bool uclamp_rq_is_capped(struct rq *rq) { return false; }
3136
3137 static inline bool uclamp_is_used(void)
3138 {
3139         return false;
3140 }
3141
3142 static inline unsigned long uclamp_rq_get(struct rq *rq,
3143                                           enum uclamp_id clamp_id)
3144 {
3145         if (clamp_id == UCLAMP_MIN)
3146                 return 0;
3147
3148         return SCHED_CAPACITY_SCALE;
3149 }
3150
3151 static inline void uclamp_rq_set(struct rq *rq, enum uclamp_id clamp_id,
3152                                  unsigned int value)
3153 {
3154 }
3155
3156 static inline bool uclamp_rq_is_idle(struct rq *rq)
3157 {
3158         return false;
3159 }
3160 #endif /* CONFIG_UCLAMP_TASK */
3161
3162 #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
3163 static inline unsigned long cpu_util_irq(struct rq *rq)
3164 {
3165         return rq->avg_irq.util_avg;
3166 }
3167
3168 static inline
3169 unsigned long scale_irq_capacity(unsigned long util, unsigned long irq, unsigned long max)
3170 {
3171         util *= (max - irq);
3172         util /= max;
3173
3174         return util;
3175
3176 }
3177 #else
3178 static inline unsigned long cpu_util_irq(struct rq *rq)
3179 {
3180         return 0;
3181 }
3182
3183 static inline
3184 unsigned long scale_irq_capacity(unsigned long util, unsigned long irq, unsigned long max)
3185 {
3186         return util;
3187 }
3188 #endif
3189
3190 #if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
3191
3192 #define perf_domain_span(pd) (to_cpumask(((pd)->em_pd->cpus)))
3193
3194 DECLARE_STATIC_KEY_FALSE(sched_energy_present);
3195
3196 static inline bool sched_energy_enabled(void)
3197 {
3198         return static_branch_unlikely(&sched_energy_present);
3199 }
3200
3201 extern struct cpufreq_governor schedutil_gov;
3202
3203 #else /* ! (CONFIG_ENERGY_MODEL && CONFIG_CPU_FREQ_GOV_SCHEDUTIL) */
3204
3205 #define perf_domain_span(pd) NULL
3206 static inline bool sched_energy_enabled(void) { return false; }
3207
3208 #endif /* CONFIG_ENERGY_MODEL && CONFIG_CPU_FREQ_GOV_SCHEDUTIL */
3209
3210 #ifdef CONFIG_MEMBARRIER
3211 /*
3212  * The scheduler provides memory barriers required by membarrier between:
3213  * - prior user-space memory accesses and store to rq->membarrier_state,
3214  * - store to rq->membarrier_state and following user-space memory accesses.
3215  * In the same way it provides those guarantees around store to rq->curr.
3216  */
3217 static inline void membarrier_switch_mm(struct rq *rq,
3218                                         struct mm_struct *prev_mm,
3219                                         struct mm_struct *next_mm)
3220 {
3221         int membarrier_state;
3222
3223         if (prev_mm == next_mm)
3224                 return;
3225
3226         membarrier_state = atomic_read(&next_mm->membarrier_state);
3227         if (READ_ONCE(rq->membarrier_state) == membarrier_state)
3228                 return;
3229
3230         WRITE_ONCE(rq->membarrier_state, membarrier_state);
3231 }
3232 #else
3233 static inline void membarrier_switch_mm(struct rq *rq,
3234                                         struct mm_struct *prev_mm,
3235                                         struct mm_struct *next_mm)
3236 {
3237 }
3238 #endif
3239
3240 #ifdef CONFIG_SMP
3241 static inline bool is_per_cpu_kthread(struct task_struct *p)
3242 {
3243         if (!(p->flags & PF_KTHREAD))
3244                 return false;
3245
3246         if (p->nr_cpus_allowed != 1)
3247                 return false;
3248
3249         return true;
3250 }
3251 #endif
3252
3253 extern void swake_up_all_locked(struct swait_queue_head *q);
3254 extern void __prepare_to_swait(struct swait_queue_head *q, struct swait_queue *wait);
3255
3256 extern int try_to_wake_up(struct task_struct *tsk, unsigned int state, int wake_flags);
3257
3258 #ifdef CONFIG_PREEMPT_DYNAMIC
3259 extern int preempt_dynamic_mode;
3260 extern int sched_dynamic_mode(const char *str);
3261 extern void sched_dynamic_update(int mode);
3262 #endif
3263
3264 static inline void update_current_exec_runtime(struct task_struct *curr,
3265                                                 u64 now, u64 delta_exec)
3266 {
3267         curr->se.sum_exec_runtime += delta_exec;
3268         account_group_exec_runtime(curr, delta_exec);
3269
3270         curr->se.exec_start = now;
3271         cgroup_account_cputime(curr, delta_exec);
3272 }
3273
3274 #ifdef CONFIG_SCHED_MM_CID
3275
3276 #define SCHED_MM_CID_PERIOD_NS  (100ULL * 1000000)      /* 100ms */
3277 #define MM_CID_SCAN_DELAY       100                     /* 100ms */
3278
3279 extern raw_spinlock_t cid_lock;
3280 extern int use_cid_lock;
3281
3282 extern void sched_mm_cid_migrate_from(struct task_struct *t);
3283 extern void sched_mm_cid_migrate_to(struct rq *dst_rq, struct task_struct *t);
3284 extern void task_tick_mm_cid(struct rq *rq, struct task_struct *curr);
3285 extern void init_sched_mm_cid(struct task_struct *t);
3286
3287 static inline void __mm_cid_put(struct mm_struct *mm, int cid)
3288 {
3289         if (cid < 0)
3290                 return;
3291         cpumask_clear_cpu(cid, mm_cidmask(mm));
3292 }
3293
3294 /*
3295  * The per-mm/cpu cid can have the MM_CID_LAZY_PUT flag set or transition to
3296  * the MM_CID_UNSET state without holding the rq lock, but the rq lock needs to
3297  * be held to transition to other states.
3298  *
3299  * State transitions synchronized with cmpxchg or try_cmpxchg need to be
3300  * consistent across cpus, which prevents use of this_cpu_cmpxchg.
3301  */
3302 static inline void mm_cid_put_lazy(struct task_struct *t)
3303 {
3304         struct mm_struct *mm = t->mm;
3305         struct mm_cid __percpu *pcpu_cid = mm->pcpu_cid;
3306         int cid;
3307
3308         lockdep_assert_irqs_disabled();
3309         cid = __this_cpu_read(pcpu_cid->cid);
3310         if (!mm_cid_is_lazy_put(cid) ||
3311             !try_cmpxchg(&this_cpu_ptr(pcpu_cid)->cid, &cid, MM_CID_UNSET))
3312                 return;
3313         __mm_cid_put(mm, mm_cid_clear_lazy_put(cid));
3314 }
3315
3316 static inline int mm_cid_pcpu_unset(struct mm_struct *mm)
3317 {
3318         struct mm_cid __percpu *pcpu_cid = mm->pcpu_cid;
3319         int cid, res;
3320
3321         lockdep_assert_irqs_disabled();
3322         cid = __this_cpu_read(pcpu_cid->cid);
3323         for (;;) {
3324                 if (mm_cid_is_unset(cid))
3325                         return MM_CID_UNSET;
3326                 /*
3327                  * Attempt transition from valid or lazy-put to unset.
3328                  */
3329                 res = cmpxchg(&this_cpu_ptr(pcpu_cid)->cid, cid, MM_CID_UNSET);
3330                 if (res == cid)
3331                         break;
3332                 cid = res;
3333         }
3334         return cid;
3335 }
3336
3337 static inline void mm_cid_put(struct mm_struct *mm)
3338 {
3339         int cid;
3340
3341         lockdep_assert_irqs_disabled();
3342         cid = mm_cid_pcpu_unset(mm);
3343         if (cid == MM_CID_UNSET)
3344                 return;
3345         __mm_cid_put(mm, mm_cid_clear_lazy_put(cid));
3346 }
3347
3348 static inline int __mm_cid_try_get(struct mm_struct *mm)
3349 {
3350         struct cpumask *cpumask;
3351         int cid;
3352
3353         cpumask = mm_cidmask(mm);
3354         /*
3355          * Retry finding first zero bit if the mask is temporarily
3356          * filled. This only happens during concurrent remote-clear
3357          * which owns a cid without holding a rq lock.
3358          */
3359         for (;;) {
3360                 cid = cpumask_first_zero(cpumask);
3361                 if (cid < nr_cpu_ids)
3362                         break;
3363                 cpu_relax();
3364         }
3365         if (cpumask_test_and_set_cpu(cid, cpumask))
3366                 return -1;
3367         return cid;
3368 }
3369
3370 /*
3371  * Save a snapshot of the current runqueue time of this cpu
3372  * with the per-cpu cid value, allowing to estimate how recently it was used.
3373  */
3374 static inline void mm_cid_snapshot_time(struct rq *rq, struct mm_struct *mm)
3375 {
3376         struct mm_cid *pcpu_cid = per_cpu_ptr(mm->pcpu_cid, cpu_of(rq));
3377
3378         lockdep_assert_rq_held(rq);
3379         WRITE_ONCE(pcpu_cid->time, rq->clock);
3380 }
3381
3382 static inline int __mm_cid_get(struct rq *rq, struct mm_struct *mm)
3383 {
3384         int cid;
3385
3386         /*
3387          * All allocations (even those using the cid_lock) are lock-free. If
3388          * use_cid_lock is set, hold the cid_lock to perform cid allocation to
3389          * guarantee forward progress.
3390          */
3391         if (!READ_ONCE(use_cid_lock)) {
3392                 cid = __mm_cid_try_get(mm);
3393                 if (cid >= 0)
3394                         goto end;
3395                 raw_spin_lock(&cid_lock);
3396         } else {
3397                 raw_spin_lock(&cid_lock);
3398                 cid = __mm_cid_try_get(mm);
3399                 if (cid >= 0)
3400                         goto unlock;
3401         }
3402
3403         /*
3404          * cid concurrently allocated. Retry while forcing following
3405          * allocations to use the cid_lock to ensure forward progress.
3406          */
3407         WRITE_ONCE(use_cid_lock, 1);
3408         /*
3409          * Set use_cid_lock before allocation. Only care about program order
3410          * because this is only required for forward progress.
3411          */
3412         barrier();
3413         /*
3414          * Retry until it succeeds. It is guaranteed to eventually succeed once
3415          * all newcoming allocations observe the use_cid_lock flag set.
3416          */
3417         do {
3418                 cid = __mm_cid_try_get(mm);
3419                 cpu_relax();
3420         } while (cid < 0);
3421         /*
3422          * Allocate before clearing use_cid_lock. Only care about
3423          * program order because this is for forward progress.
3424          */
3425         barrier();
3426         WRITE_ONCE(use_cid_lock, 0);
3427 unlock:
3428         raw_spin_unlock(&cid_lock);
3429 end:
3430         mm_cid_snapshot_time(rq, mm);
3431         return cid;
3432 }
3433
3434 static inline int mm_cid_get(struct rq *rq, struct mm_struct *mm)
3435 {
3436         struct mm_cid __percpu *pcpu_cid = mm->pcpu_cid;
3437         struct cpumask *cpumask;
3438         int cid;
3439
3440         lockdep_assert_rq_held(rq);
3441         cpumask = mm_cidmask(mm);
3442         cid = __this_cpu_read(pcpu_cid->cid);
3443         if (mm_cid_is_valid(cid)) {
3444                 mm_cid_snapshot_time(rq, mm);
3445                 return cid;
3446         }
3447         if (mm_cid_is_lazy_put(cid)) {
3448                 if (try_cmpxchg(&this_cpu_ptr(pcpu_cid)->cid, &cid, MM_CID_UNSET))
3449                         __mm_cid_put(mm, mm_cid_clear_lazy_put(cid));
3450         }
3451         cid = __mm_cid_get(rq, mm);
3452         __this_cpu_write(pcpu_cid->cid, cid);
3453         return cid;
3454 }
3455
3456 static inline void switch_mm_cid(struct rq *rq,
3457                                  struct task_struct *prev,
3458                                  struct task_struct *next)
3459 {
3460         /*
3461          * Provide a memory barrier between rq->curr store and load of
3462          * {prev,next}->mm->pcpu_cid[cpu] on rq->curr->mm transition.
3463          *
3464          * Should be adapted if context_switch() is modified.
3465          */
3466         if (!next->mm) {                                // to kernel
3467                 /*
3468                  * user -> kernel transition does not guarantee a barrier, but
3469                  * we can use the fact that it performs an atomic operation in
3470                  * mmgrab().
3471                  */
3472                 if (prev->mm)                           // from user
3473                         smp_mb__after_mmgrab();
3474                 /*
3475                  * kernel -> kernel transition does not change rq->curr->mm
3476                  * state. It stays NULL.
3477                  */
3478         } else {                                        // to user
3479                 /*
3480                  * kernel -> user transition does not provide a barrier
3481                  * between rq->curr store and load of {prev,next}->mm->pcpu_cid[cpu].
3482                  * Provide it here.
3483                  */
3484                 if (!prev->mm)                          // from kernel
3485                         smp_mb();
3486                 /*
3487                  * user -> user transition guarantees a memory barrier through
3488                  * switch_mm() when current->mm changes. If current->mm is
3489                  * unchanged, no barrier is needed.
3490                  */
3491         }
3492         if (prev->mm_cid_active) {
3493                 mm_cid_snapshot_time(rq, prev->mm);
3494                 mm_cid_put_lazy(prev);
3495                 prev->mm_cid = -1;
3496         }
3497         if (next->mm_cid_active)
3498                 next->last_mm_cid = next->mm_cid = mm_cid_get(rq, next->mm);
3499 }
3500
3501 #else
3502 static inline void switch_mm_cid(struct rq *rq, struct task_struct *prev, struct task_struct *next) { }
3503 static inline void sched_mm_cid_migrate_from(struct task_struct *t) { }
3504 static inline void sched_mm_cid_migrate_to(struct rq *dst_rq, struct task_struct *t) { }
3505 static inline void task_tick_mm_cid(struct rq *rq, struct task_struct *curr) { }
3506 static inline void init_sched_mm_cid(struct task_struct *t) { }
3507 #endif
3508
3509 extern u64 avg_vruntime(struct cfs_rq *cfs_rq);
3510 extern int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se);
3511
3512 #endif /* _KERNEL_SCHED_SCHED_H */