sched: sched.h: make rq locking and clock functions available in stats.h
[muen/linux.git] / kernel / sched / sched.h
1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3  * Scheduler internal types and methods:
4  */
5 #include <linux/sched.h>
6
7 #include <linux/sched/autogroup.h>
8 #include <linux/sched/clock.h>
9 #include <linux/sched/coredump.h>
10 #include <linux/sched/cpufreq.h>
11 #include <linux/sched/cputime.h>
12 #include <linux/sched/deadline.h>
13 #include <linux/sched/debug.h>
14 #include <linux/sched/hotplug.h>
15 #include <linux/sched/idle.h>
16 #include <linux/sched/init.h>
17 #include <linux/sched/isolation.h>
18 #include <linux/sched/jobctl.h>
19 #include <linux/sched/loadavg.h>
20 #include <linux/sched/mm.h>
21 #include <linux/sched/nohz.h>
22 #include <linux/sched/numa_balancing.h>
23 #include <linux/sched/prio.h>
24 #include <linux/sched/rt.h>
25 #include <linux/sched/signal.h>
26 #include <linux/sched/stat.h>
27 #include <linux/sched/sysctl.h>
28 #include <linux/sched/task.h>
29 #include <linux/sched/task_stack.h>
30 #include <linux/sched/topology.h>
31 #include <linux/sched/user.h>
32 #include <linux/sched/wake_q.h>
33 #include <linux/sched/xacct.h>
34
35 #include <uapi/linux/sched/types.h>
36
37 #include <linux/binfmts.h>
38 #include <linux/blkdev.h>
39 #include <linux/compat.h>
40 #include <linux/context_tracking.h>
41 #include <linux/cpufreq.h>
42 #include <linux/cpuidle.h>
43 #include <linux/cpuset.h>
44 #include <linux/ctype.h>
45 #include <linux/debugfs.h>
46 #include <linux/delayacct.h>
47 #include <linux/init_task.h>
48 #include <linux/kprobes.h>
49 #include <linux/kthread.h>
50 #include <linux/membarrier.h>
51 #include <linux/migrate.h>
52 #include <linux/mmu_context.h>
53 #include <linux/nmi.h>
54 #include <linux/proc_fs.h>
55 #include <linux/prefetch.h>
56 #include <linux/profile.h>
57 #include <linux/rcupdate_wait.h>
58 #include <linux/security.h>
59 #include <linux/stop_machine.h>
60 #include <linux/suspend.h>
61 #include <linux/swait.h>
62 #include <linux/syscalls.h>
63 #include <linux/task_work.h>
64 #include <linux/tsacct_kern.h>
65
66 #include <asm/tlb.h>
67
68 #ifdef CONFIG_PARAVIRT
69 # include <asm/paravirt.h>
70 #endif
71
72 #include "cpupri.h"
73 #include "cpudeadline.h"
74
75 #ifdef CONFIG_SCHED_DEBUG
76 # define SCHED_WARN_ON(x)       WARN_ONCE(x, #x)
77 #else
78 # define SCHED_WARN_ON(x)       ({ (void)(x), 0; })
79 #endif
80
81 struct rq;
82 struct cpuidle_state;
83
84 /* task_struct::on_rq states: */
85 #define TASK_ON_RQ_QUEUED       1
86 #define TASK_ON_RQ_MIGRATING    2
87
88 extern __read_mostly int scheduler_running;
89
90 extern unsigned long calc_load_update;
91 extern atomic_long_t calc_load_tasks;
92
93 extern void calc_global_load_tick(struct rq *this_rq);
94 extern long calc_load_fold_active(struct rq *this_rq, long adjust);
95
96 #ifdef CONFIG_SMP
97 extern void cpu_load_update_active(struct rq *this_rq);
98 #else
99 static inline void cpu_load_update_active(struct rq *this_rq) { }
100 #endif
101
102 /*
103  * Helpers for converting nanosecond timing to jiffy resolution
104  */
105 #define NS_TO_JIFFIES(TIME)     ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))
106
107 /*
108  * Increase resolution of nice-level calculations for 64-bit architectures.
109  * The extra resolution improves shares distribution and load balancing of
110  * low-weight task groups (eg. nice +19 on an autogroup), deeper taskgroup
111  * hierarchies, especially on larger systems. This is not a user-visible change
112  * and does not change the user-interface for setting shares/weights.
113  *
114  * We increase resolution only if we have enough bits to allow this increased
115  * resolution (i.e. 64-bit). The costs for increasing resolution when 32-bit
116  * are pretty high and the returns do not justify the increased costs.
117  *
118  * Really only required when CONFIG_FAIR_GROUP_SCHED=y is also set, but to
119  * increase coverage and consistency always enable it on 64-bit platforms.
120  */
121 #ifdef CONFIG_64BIT
122 # define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT)
123 # define scale_load(w)          ((w) << SCHED_FIXEDPOINT_SHIFT)
124 # define scale_load_down(w)     ((w) >> SCHED_FIXEDPOINT_SHIFT)
125 #else
126 # define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT)
127 # define scale_load(w)          (w)
128 # define scale_load_down(w)     (w)
129 #endif
130
131 /*
132  * Task weight (visible to users) and its load (invisible to users) have
133  * independent resolution, but they should be well calibrated. We use
134  * scale_load() and scale_load_down(w) to convert between them. The
135  * following must be true:
136  *
137  *  scale_load(sched_prio_to_weight[USER_PRIO(NICE_TO_PRIO(0))]) == NICE_0_LOAD
138  *
139  */
140 #define NICE_0_LOAD             (1L << NICE_0_LOAD_SHIFT)
141
142 /*
143  * Single value that decides SCHED_DEADLINE internal math precision.
144  * 10 -> just above 1us
145  * 9  -> just above 0.5us
146  */
147 #define DL_SCALE                10
148
149 /*
150  * Single value that denotes runtime == period, ie unlimited time.
151  */
152 #define RUNTIME_INF             ((u64)~0ULL)
153
154 static inline int idle_policy(int policy)
155 {
156         return policy == SCHED_IDLE;
157 }
158 static inline int fair_policy(int policy)
159 {
160         return policy == SCHED_NORMAL || policy == SCHED_BATCH;
161 }
162
163 static inline int rt_policy(int policy)
164 {
165         return policy == SCHED_FIFO || policy == SCHED_RR;
166 }
167
168 static inline int dl_policy(int policy)
169 {
170         return policy == SCHED_DEADLINE;
171 }
172 static inline bool valid_policy(int policy)
173 {
174         return idle_policy(policy) || fair_policy(policy) ||
175                 rt_policy(policy) || dl_policy(policy);
176 }
177
178 static inline int task_has_rt_policy(struct task_struct *p)
179 {
180         return rt_policy(p->policy);
181 }
182
183 static inline int task_has_dl_policy(struct task_struct *p)
184 {
185         return dl_policy(p->policy);
186 }
187
188 #define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
189
190 /*
191  * !! For sched_setattr_nocheck() (kernel) only !!
192  *
193  * This is actually gross. :(
194  *
195  * It is used to make schedutil kworker(s) higher priority than SCHED_DEADLINE
196  * tasks, but still be able to sleep. We need this on platforms that cannot
197  * atomically change clock frequency. Remove once fast switching will be
198  * available on such platforms.
199  *
200  * SUGOV stands for SchedUtil GOVernor.
201  */
202 #define SCHED_FLAG_SUGOV        0x10000000
203
204 static inline bool dl_entity_is_special(struct sched_dl_entity *dl_se)
205 {
206 #ifdef CONFIG_CPU_FREQ_GOV_SCHEDUTIL
207         return unlikely(dl_se->flags & SCHED_FLAG_SUGOV);
208 #else
209         return false;
210 #endif
211 }
212
213 /*
214  * Tells if entity @a should preempt entity @b.
215  */
216 static inline bool
217 dl_entity_preempt(struct sched_dl_entity *a, struct sched_dl_entity *b)
218 {
219         return dl_entity_is_special(a) ||
220                dl_time_before(a->deadline, b->deadline);
221 }
222
223 /*
224  * This is the priority-queue data structure of the RT scheduling class:
225  */
226 struct rt_prio_array {
227         DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
228         struct list_head queue[MAX_RT_PRIO];
229 };
230
231 struct rt_bandwidth {
232         /* nests inside the rq lock: */
233         raw_spinlock_t          rt_runtime_lock;
234         ktime_t                 rt_period;
235         u64                     rt_runtime;
236         struct hrtimer          rt_period_timer;
237         unsigned int            rt_period_active;
238 };
239
240 void __dl_clear_params(struct task_struct *p);
241
242 /*
243  * To keep the bandwidth of -deadline tasks and groups under control
244  * we need some place where:
245  *  - store the maximum -deadline bandwidth of the system (the group);
246  *  - cache the fraction of that bandwidth that is currently allocated.
247  *
248  * This is all done in the data structure below. It is similar to the
249  * one used for RT-throttling (rt_bandwidth), with the main difference
250  * that, since here we are only interested in admission control, we
251  * do not decrease any runtime while the group "executes", neither we
252  * need a timer to replenish it.
253  *
254  * With respect to SMP, the bandwidth is given on a per-CPU basis,
255  * meaning that:
256  *  - dl_bw (< 100%) is the bandwidth of the system (group) on each CPU;
257  *  - dl_total_bw array contains, in the i-eth element, the currently
258  *    allocated bandwidth on the i-eth CPU.
259  * Moreover, groups consume bandwidth on each CPU, while tasks only
260  * consume bandwidth on the CPU they're running on.
261  * Finally, dl_total_bw_cpu is used to cache the index of dl_total_bw
262  * that will be shown the next time the proc or cgroup controls will
263  * be red. It on its turn can be changed by writing on its own
264  * control.
265  */
266 struct dl_bandwidth {
267         raw_spinlock_t          dl_runtime_lock;
268         u64                     dl_runtime;
269         u64                     dl_period;
270 };
271
272 static inline int dl_bandwidth_enabled(void)
273 {
274         return sysctl_sched_rt_runtime >= 0;
275 }
276
277 struct dl_bw {
278         raw_spinlock_t          lock;
279         u64                     bw;
280         u64                     total_bw;
281 };
282
283 static inline void __dl_update(struct dl_bw *dl_b, s64 bw);
284
285 static inline
286 void __dl_sub(struct dl_bw *dl_b, u64 tsk_bw, int cpus)
287 {
288         dl_b->total_bw -= tsk_bw;
289         __dl_update(dl_b, (s32)tsk_bw / cpus);
290 }
291
292 static inline
293 void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)
294 {
295         dl_b->total_bw += tsk_bw;
296         __dl_update(dl_b, -((s32)tsk_bw / cpus));
297 }
298
299 static inline
300 bool __dl_overflow(struct dl_bw *dl_b, int cpus, u64 old_bw, u64 new_bw)
301 {
302         return dl_b->bw != -1 &&
303                dl_b->bw * cpus < dl_b->total_bw - old_bw + new_bw;
304 }
305
306 extern void dl_change_utilization(struct task_struct *p, u64 new_bw);
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_task_can_attach(struct task_struct *p, const struct cpumask *cs_cpus_allowed);
316 extern int  dl_cpuset_cpumask_can_shrink(const struct cpumask *cur, const struct cpumask *trial);
317 extern bool dl_cpu_busy(unsigned int cpu);
318
319 #ifdef CONFIG_CGROUP_SCHED
320
321 #include <linux/cgroup.h>
322
323 struct cfs_rq;
324 struct rt_rq;
325
326 extern struct list_head task_groups;
327
328 struct cfs_bandwidth {
329 #ifdef CONFIG_CFS_BANDWIDTH
330         raw_spinlock_t          lock;
331         ktime_t                 period;
332         u64                     quota;
333         u64                     runtime;
334         s64                     hierarchical_quota;
335         u64                     runtime_expires;
336         int                     expires_seq;
337
338         short                   idle;
339         short                   period_active;
340         struct hrtimer          period_timer;
341         struct hrtimer          slack_timer;
342         struct list_head        throttled_cfs_rq;
343
344         /* Statistics: */
345         int                     nr_periods;
346         int                     nr_throttled;
347         u64                     throttled_time;
348
349         bool                    distribute_running;
350 #endif
351 };
352
353 /* Task group related information */
354 struct task_group {
355         struct cgroup_subsys_state css;
356
357 #ifdef CONFIG_FAIR_GROUP_SCHED
358         /* schedulable entities of this group on each CPU */
359         struct sched_entity     **se;
360         /* runqueue "owned" by this group on each CPU */
361         struct cfs_rq           **cfs_rq;
362         unsigned long           shares;
363
364 #ifdef  CONFIG_SMP
365         /*
366          * load_avg can be heavily contended at clock tick time, so put
367          * it in its own cacheline separated from the fields above which
368          * will also be accessed at each tick.
369          */
370         atomic_long_t           load_avg ____cacheline_aligned;
371 #endif
372 #endif
373
374 #ifdef CONFIG_RT_GROUP_SCHED
375         struct sched_rt_entity  **rt_se;
376         struct rt_rq            **rt_rq;
377
378         struct rt_bandwidth     rt_bandwidth;
379 #endif
380
381         struct rcu_head         rcu;
382         struct list_head        list;
383
384         struct task_group       *parent;
385         struct list_head        siblings;
386         struct list_head        children;
387
388 #ifdef CONFIG_SCHED_AUTOGROUP
389         struct autogroup        *autogroup;
390 #endif
391
392         struct cfs_bandwidth    cfs_bandwidth;
393 };
394
395 #ifdef CONFIG_FAIR_GROUP_SCHED
396 #define ROOT_TASK_GROUP_LOAD    NICE_0_LOAD
397
398 /*
399  * A weight of 0 or 1 can cause arithmetics problems.
400  * A weight of a cfs_rq is the sum of weights of which entities
401  * are queued on this cfs_rq, so a weight of a entity should not be
402  * too large, so as the shares value of a task group.
403  * (The default weight is 1024 - so there's no practical
404  *  limitation from this.)
405  */
406 #define MIN_SHARES              (1UL <<  1)
407 #define MAX_SHARES              (1UL << 18)
408 #endif
409
410 typedef int (*tg_visitor)(struct task_group *, void *);
411
412 extern int walk_tg_tree_from(struct task_group *from,
413                              tg_visitor down, tg_visitor up, void *data);
414
415 /*
416  * Iterate the full tree, calling @down when first entering a node and @up when
417  * leaving it for the final time.
418  *
419  * Caller must hold rcu_lock or sufficient equivalent.
420  */
421 static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data)
422 {
423         return walk_tg_tree_from(&root_task_group, down, up, data);
424 }
425
426 extern int tg_nop(struct task_group *tg, void *data);
427
428 extern void free_fair_sched_group(struct task_group *tg);
429 extern int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent);
430 extern void online_fair_sched_group(struct task_group *tg);
431 extern void unregister_fair_sched_group(struct task_group *tg);
432 extern void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
433                         struct sched_entity *se, int cpu,
434                         struct sched_entity *parent);
435 extern void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
436
437 extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b);
438 extern void start_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
439 extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq);
440
441 extern void free_rt_sched_group(struct task_group *tg);
442 extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent);
443 extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
444                 struct sched_rt_entity *rt_se, int cpu,
445                 struct sched_rt_entity *parent);
446 extern int sched_group_set_rt_runtime(struct task_group *tg, long rt_runtime_us);
447 extern int sched_group_set_rt_period(struct task_group *tg, u64 rt_period_us);
448 extern long sched_group_rt_runtime(struct task_group *tg);
449 extern long sched_group_rt_period(struct task_group *tg);
450 extern int sched_rt_can_attach(struct task_group *tg, struct task_struct *tsk);
451
452 extern struct task_group *sched_create_group(struct task_group *parent);
453 extern void sched_online_group(struct task_group *tg,
454                                struct task_group *parent);
455 extern void sched_destroy_group(struct task_group *tg);
456 extern void sched_offline_group(struct task_group *tg);
457
458 extern void sched_move_task(struct task_struct *tsk);
459
460 #ifdef CONFIG_FAIR_GROUP_SCHED
461 extern int sched_group_set_shares(struct task_group *tg, unsigned long shares);
462
463 #ifdef CONFIG_SMP
464 extern void set_task_rq_fair(struct sched_entity *se,
465                              struct cfs_rq *prev, struct cfs_rq *next);
466 #else /* !CONFIG_SMP */
467 static inline void set_task_rq_fair(struct sched_entity *se,
468                              struct cfs_rq *prev, struct cfs_rq *next) { }
469 #endif /* CONFIG_SMP */
470 #endif /* CONFIG_FAIR_GROUP_SCHED */
471
472 #else /* CONFIG_CGROUP_SCHED */
473
474 struct cfs_bandwidth { };
475
476 #endif  /* CONFIG_CGROUP_SCHED */
477
478 /* CFS-related fields in a runqueue */
479 struct cfs_rq {
480         struct load_weight      load;
481         unsigned long           runnable_weight;
482         unsigned int            nr_running;
483         unsigned int            h_nr_running;
484
485         u64                     exec_clock;
486         u64                     min_vruntime;
487 #ifndef CONFIG_64BIT
488         u64                     min_vruntime_copy;
489 #endif
490
491         struct rb_root_cached   tasks_timeline;
492
493         /*
494          * 'curr' points to currently running entity on this cfs_rq.
495          * It is set to NULL otherwise (i.e when none are currently running).
496          */
497         struct sched_entity     *curr;
498         struct sched_entity     *next;
499         struct sched_entity     *last;
500         struct sched_entity     *skip;
501
502 #ifdef  CONFIG_SCHED_DEBUG
503         unsigned int            nr_spread_over;
504 #endif
505
506 #ifdef CONFIG_SMP
507         /*
508          * CFS load tracking
509          */
510         struct sched_avg        avg;
511 #ifndef CONFIG_64BIT
512         u64                     load_last_update_time_copy;
513 #endif
514         struct {
515                 raw_spinlock_t  lock ____cacheline_aligned;
516                 int             nr;
517                 unsigned long   load_avg;
518                 unsigned long   util_avg;
519                 unsigned long   runnable_sum;
520         } removed;
521
522 #ifdef CONFIG_FAIR_GROUP_SCHED
523         unsigned long           tg_load_avg_contrib;
524         long                    propagate;
525         long                    prop_runnable_sum;
526
527         /*
528          *   h_load = weight * f(tg)
529          *
530          * Where f(tg) is the recursive weight fraction assigned to
531          * this group.
532          */
533         unsigned long           h_load;
534         u64                     last_h_load_update;
535         struct sched_entity     *h_load_next;
536 #endif /* CONFIG_FAIR_GROUP_SCHED */
537 #endif /* CONFIG_SMP */
538
539 #ifdef CONFIG_FAIR_GROUP_SCHED
540         struct rq               *rq;    /* CPU runqueue to which this cfs_rq is attached */
541
542         /*
543          * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
544          * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
545          * (like users, containers etc.)
546          *
547          * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a CPU.
548          * This list is used during load balance.
549          */
550         int                     on_list;
551         struct list_head        leaf_cfs_rq_list;
552         struct task_group       *tg;    /* group that "owns" this runqueue */
553
554 #ifdef CONFIG_CFS_BANDWIDTH
555         int                     runtime_enabled;
556         int                     expires_seq;
557         u64                     runtime_expires;
558         s64                     runtime_remaining;
559
560         u64                     throttled_clock;
561         u64                     throttled_clock_task;
562         u64                     throttled_clock_task_time;
563         int                     throttled;
564         int                     throttle_count;
565         struct list_head        throttled_list;
566 #endif /* CONFIG_CFS_BANDWIDTH */
567 #endif /* CONFIG_FAIR_GROUP_SCHED */
568 };
569
570 static inline int rt_bandwidth_enabled(void)
571 {
572         return sysctl_sched_rt_runtime >= 0;
573 }
574
575 /* RT IPI pull logic requires IRQ_WORK */
576 #if defined(CONFIG_IRQ_WORK) && defined(CONFIG_SMP)
577 # define HAVE_RT_PUSH_IPI
578 #endif
579
580 /* Real-Time classes' related field in a runqueue: */
581 struct rt_rq {
582         struct rt_prio_array    active;
583         unsigned int            rt_nr_running;
584         unsigned int            rr_nr_running;
585 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
586         struct {
587                 int             curr; /* highest queued rt task prio */
588 #ifdef CONFIG_SMP
589                 int             next; /* next highest */
590 #endif
591         } highest_prio;
592 #endif
593 #ifdef CONFIG_SMP
594         unsigned long           rt_nr_migratory;
595         unsigned long           rt_nr_total;
596         int                     overloaded;
597         struct plist_head       pushable_tasks;
598
599 #endif /* CONFIG_SMP */
600         int                     rt_queued;
601
602         int                     rt_throttled;
603         u64                     rt_time;
604         u64                     rt_runtime;
605         /* Nests inside the rq lock: */
606         raw_spinlock_t          rt_runtime_lock;
607
608 #ifdef CONFIG_RT_GROUP_SCHED
609         unsigned long           rt_nr_boosted;
610
611         struct rq               *rq;
612         struct task_group       *tg;
613 #endif
614 };
615
616 static inline bool rt_rq_is_runnable(struct rt_rq *rt_rq)
617 {
618         return rt_rq->rt_queued && rt_rq->rt_nr_running;
619 }
620
621 /* Deadline class' related fields in a runqueue */
622 struct dl_rq {
623         /* runqueue is an rbtree, ordered by deadline */
624         struct rb_root_cached   root;
625
626         unsigned long           dl_nr_running;
627
628 #ifdef CONFIG_SMP
629         /*
630          * Deadline values of the currently executing and the
631          * earliest ready task on this rq. Caching these facilitates
632          * the decision wether or not a ready but not running task
633          * should migrate somewhere else.
634          */
635         struct {
636                 u64             curr;
637                 u64             next;
638         } earliest_dl;
639
640         unsigned long           dl_nr_migratory;
641         int                     overloaded;
642
643         /*
644          * Tasks on this rq that can be pushed away. They are kept in
645          * an rb-tree, ordered by tasks' deadlines, with caching
646          * of the leftmost (earliest deadline) element.
647          */
648         struct rb_root_cached   pushable_dl_tasks_root;
649 #else
650         struct dl_bw            dl_bw;
651 #endif
652         /*
653          * "Active utilization" for this runqueue: increased when a
654          * task wakes up (becomes TASK_RUNNING) and decreased when a
655          * task blocks
656          */
657         u64                     running_bw;
658
659         /*
660          * Utilization of the tasks "assigned" to this runqueue (including
661          * the tasks that are in runqueue and the tasks that executed on this
662          * CPU and blocked). Increased when a task moves to this runqueue, and
663          * decreased when the task moves away (migrates, changes scheduling
664          * policy, or terminates).
665          * This is needed to compute the "inactive utilization" for the
666          * runqueue (inactive utilization = this_bw - running_bw).
667          */
668         u64                     this_bw;
669         u64                     extra_bw;
670
671         /*
672          * Inverse of the fraction of CPU utilization that can be reclaimed
673          * by the GRUB algorithm.
674          */
675         u64                     bw_ratio;
676 };
677
678 #ifdef CONFIG_FAIR_GROUP_SCHED
679 /* An entity is a task if it doesn't "own" a runqueue */
680 #define entity_is_task(se)      (!se->my_q)
681 #else
682 #define entity_is_task(se)      1
683 #endif
684
685 #ifdef CONFIG_SMP
686 /*
687  * XXX we want to get rid of these helpers and use the full load resolution.
688  */
689 static inline long se_weight(struct sched_entity *se)
690 {
691         return scale_load_down(se->load.weight);
692 }
693
694 static inline long se_runnable(struct sched_entity *se)
695 {
696         return scale_load_down(se->runnable_weight);
697 }
698
699 static inline bool sched_asym_prefer(int a, int b)
700 {
701         return arch_asym_cpu_priority(a) > arch_asym_cpu_priority(b);
702 }
703
704 /*
705  * We add the notion of a root-domain which will be used to define per-domain
706  * variables. Each exclusive cpuset essentially defines an island domain by
707  * fully partitioning the member CPUs from any other cpuset. Whenever a new
708  * exclusive cpuset is created, we also create and attach a new root-domain
709  * object.
710  *
711  */
712 struct root_domain {
713         atomic_t                refcount;
714         atomic_t                rto_count;
715         struct rcu_head         rcu;
716         cpumask_var_t           span;
717         cpumask_var_t           online;
718
719         /*
720          * Indicate pullable load on at least one CPU, e.g:
721          * - More than one runnable task
722          * - Running task is misfit
723          */
724         int                     overload;
725
726         /*
727          * The bit corresponding to a CPU gets set here if such CPU has more
728          * than one runnable -deadline task (as it is below for RT tasks).
729          */
730         cpumask_var_t           dlo_mask;
731         atomic_t                dlo_count;
732         struct dl_bw            dl_bw;
733         struct cpudl            cpudl;
734
735 #ifdef HAVE_RT_PUSH_IPI
736         /*
737          * For IPI pull requests, loop across the rto_mask.
738          */
739         struct irq_work         rto_push_work;
740         raw_spinlock_t          rto_lock;
741         /* These are only updated and read within rto_lock */
742         int                     rto_loop;
743         int                     rto_cpu;
744         /* These atomics are updated outside of a lock */
745         atomic_t                rto_loop_next;
746         atomic_t                rto_loop_start;
747 #endif
748         /*
749          * The "RT overload" flag: it gets set if a CPU has more than
750          * one runnable RT task.
751          */
752         cpumask_var_t           rto_mask;
753         struct cpupri           cpupri;
754
755         unsigned long           max_cpu_capacity;
756 };
757
758 extern struct root_domain def_root_domain;
759 extern struct mutex sched_domains_mutex;
760
761 extern void init_defrootdomain(void);
762 extern int sched_init_domains(const struct cpumask *cpu_map);
763 extern void rq_attach_root(struct rq *rq, struct root_domain *rd);
764 extern void sched_get_rd(struct root_domain *rd);
765 extern void sched_put_rd(struct root_domain *rd);
766
767 #ifdef HAVE_RT_PUSH_IPI
768 extern void rto_push_irq_work_func(struct irq_work *work);
769 #endif
770 #endif /* CONFIG_SMP */
771
772 /*
773  * This is the main, per-CPU runqueue data structure.
774  *
775  * Locking rule: those places that want to lock multiple runqueues
776  * (such as the load balancing or the thread migration code), lock
777  * acquire operations must be ordered by ascending &runqueue.
778  */
779 struct rq {
780         /* runqueue lock: */
781         raw_spinlock_t          lock;
782
783         /*
784          * nr_running and cpu_load should be in the same cacheline because
785          * remote CPUs use both these fields when doing load calculation.
786          */
787         unsigned int            nr_running;
788 #ifdef CONFIG_NUMA_BALANCING
789         unsigned int            nr_numa_running;
790         unsigned int            nr_preferred_running;
791         unsigned int            numa_migrate_on;
792 #endif
793         #define CPU_LOAD_IDX_MAX 5
794         unsigned long           cpu_load[CPU_LOAD_IDX_MAX];
795 #ifdef CONFIG_NO_HZ_COMMON
796 #ifdef CONFIG_SMP
797         unsigned long           last_load_update_tick;
798         unsigned long           last_blocked_load_update_tick;
799         unsigned int            has_blocked_load;
800 #endif /* CONFIG_SMP */
801         unsigned int            nohz_tick_stopped;
802         atomic_t nohz_flags;
803 #endif /* CONFIG_NO_HZ_COMMON */
804
805         /* capture load from *all* tasks on this CPU: */
806         struct load_weight      load;
807         unsigned long           nr_load_updates;
808         u64                     nr_switches;
809
810         struct cfs_rq           cfs;
811         struct rt_rq            rt;
812         struct dl_rq            dl;
813
814 #ifdef CONFIG_FAIR_GROUP_SCHED
815         /* list of leaf cfs_rq on this CPU: */
816         struct list_head        leaf_cfs_rq_list;
817         struct list_head        *tmp_alone_branch;
818 #endif /* CONFIG_FAIR_GROUP_SCHED */
819
820         /*
821          * This is part of a global counter where only the total sum
822          * over all CPUs matters. A task can increase this counter on
823          * one CPU and if it got migrated afterwards it may decrease
824          * it on another CPU. Always updated under the runqueue lock:
825          */
826         unsigned long           nr_uninterruptible;
827
828         struct task_struct      *curr;
829         struct task_struct      *idle;
830         struct task_struct      *stop;
831         unsigned long           next_balance;
832         struct mm_struct        *prev_mm;
833
834         unsigned int            clock_update_flags;
835         u64                     clock;
836         u64                     clock_task;
837
838         atomic_t                nr_iowait;
839
840 #ifdef CONFIG_SMP
841         struct root_domain      *rd;
842         struct sched_domain     *sd;
843
844         unsigned long           cpu_capacity;
845         unsigned long           cpu_capacity_orig;
846
847         struct callback_head    *balance_callback;
848
849         unsigned char           idle_balance;
850
851         unsigned long           misfit_task_load;
852
853         /* For active balancing */
854         int                     active_balance;
855         int                     push_cpu;
856         struct cpu_stop_work    active_balance_work;
857
858         /* CPU of this runqueue: */
859         int                     cpu;
860         int                     online;
861
862         struct list_head cfs_tasks;
863
864         struct sched_avg        avg_rt;
865         struct sched_avg        avg_dl;
866 #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
867         struct sched_avg        avg_irq;
868 #endif
869         u64                     idle_stamp;
870         u64                     avg_idle;
871
872         /* This is used to determine avg_idle's max value */
873         u64                     max_idle_balance_cost;
874 #endif
875
876 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
877         u64                     prev_irq_time;
878 #endif
879 #ifdef CONFIG_PARAVIRT
880         u64                     prev_steal_time;
881 #endif
882 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
883         u64                     prev_steal_time_rq;
884 #endif
885
886         /* calc_load related fields */
887         unsigned long           calc_load_update;
888         long                    calc_load_active;
889
890 #ifdef CONFIG_SCHED_HRTICK
891 #ifdef CONFIG_SMP
892         int                     hrtick_csd_pending;
893         call_single_data_t      hrtick_csd;
894 #endif
895         struct hrtimer          hrtick_timer;
896 #endif
897
898 #ifdef CONFIG_SCHEDSTATS
899         /* latency stats */
900         struct sched_info       rq_sched_info;
901         unsigned long long      rq_cpu_time;
902         /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
903
904         /* sys_sched_yield() stats */
905         unsigned int            yld_count;
906
907         /* schedule() stats */
908         unsigned int            sched_count;
909         unsigned int            sched_goidle;
910
911         /* try_to_wake_up() stats */
912         unsigned int            ttwu_count;
913         unsigned int            ttwu_local;
914 #endif
915
916 #ifdef CONFIG_SMP
917         struct llist_head       wake_list;
918 #endif
919
920 #ifdef CONFIG_CPU_IDLE
921         /* Must be inspected within a rcu lock section */
922         struct cpuidle_state    *idle_state;
923 #endif
924 };
925
926 static inline int cpu_of(struct rq *rq)
927 {
928 #ifdef CONFIG_SMP
929         return rq->cpu;
930 #else
931         return 0;
932 #endif
933 }
934
935
936 #ifdef CONFIG_SCHED_SMT
937
938 extern struct static_key_false sched_smt_present;
939
940 extern void __update_idle_core(struct rq *rq);
941
942 static inline void update_idle_core(struct rq *rq)
943 {
944         if (static_branch_unlikely(&sched_smt_present))
945                 __update_idle_core(rq);
946 }
947
948 #else
949 static inline void update_idle_core(struct rq *rq) { }
950 #endif
951
952 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
953
954 #define cpu_rq(cpu)             (&per_cpu(runqueues, (cpu)))
955 #define this_rq()               this_cpu_ptr(&runqueues)
956 #define task_rq(p)              cpu_rq(task_cpu(p))
957 #define cpu_curr(cpu)           (cpu_rq(cpu)->curr)
958 #define raw_rq()                raw_cpu_ptr(&runqueues)
959
960 extern void update_rq_clock(struct rq *rq);
961
962 static inline u64 __rq_clock_broken(struct rq *rq)
963 {
964         return READ_ONCE(rq->clock);
965 }
966
967 /*
968  * rq::clock_update_flags bits
969  *
970  * %RQCF_REQ_SKIP - will request skipping of clock update on the next
971  *  call to __schedule(). This is an optimisation to avoid
972  *  neighbouring rq clock updates.
973  *
974  * %RQCF_ACT_SKIP - is set from inside of __schedule() when skipping is
975  *  in effect and calls to update_rq_clock() are being ignored.
976  *
977  * %RQCF_UPDATED - is a debug flag that indicates whether a call has been
978  *  made to update_rq_clock() since the last time rq::lock was pinned.
979  *
980  * If inside of __schedule(), clock_update_flags will have been
981  * shifted left (a left shift is a cheap operation for the fast path
982  * to promote %RQCF_REQ_SKIP to %RQCF_ACT_SKIP), so you must use,
983  *
984  *      if (rq-clock_update_flags >= RQCF_UPDATED)
985  *
986  * to check if %RQCF_UPADTED is set. It'll never be shifted more than
987  * one position though, because the next rq_unpin_lock() will shift it
988  * back.
989  */
990 #define RQCF_REQ_SKIP           0x01
991 #define RQCF_ACT_SKIP           0x02
992 #define RQCF_UPDATED            0x04
993
994 static inline void assert_clock_updated(struct rq *rq)
995 {
996         /*
997          * The only reason for not seeing a clock update since the
998          * last rq_pin_lock() is if we're currently skipping updates.
999          */
1000         SCHED_WARN_ON(rq->clock_update_flags < RQCF_ACT_SKIP);
1001 }
1002
1003 static inline u64 rq_clock(struct rq *rq)
1004 {
1005         lockdep_assert_held(&rq->lock);
1006         assert_clock_updated(rq);
1007
1008         return rq->clock;
1009 }
1010
1011 static inline u64 rq_clock_task(struct rq *rq)
1012 {
1013         lockdep_assert_held(&rq->lock);
1014         assert_clock_updated(rq);
1015
1016         return rq->clock_task;
1017 }
1018
1019 static inline void rq_clock_skip_update(struct rq *rq)
1020 {
1021         lockdep_assert_held(&rq->lock);
1022         rq->clock_update_flags |= RQCF_REQ_SKIP;
1023 }
1024
1025 /*
1026  * See rt task throttling, which is the only time a skip
1027  * request is cancelled.
1028  */
1029 static inline void rq_clock_cancel_skipupdate(struct rq *rq)
1030 {
1031         lockdep_assert_held(&rq->lock);
1032         rq->clock_update_flags &= ~RQCF_REQ_SKIP;
1033 }
1034
1035 struct rq_flags {
1036         unsigned long flags;
1037         struct pin_cookie cookie;
1038 #ifdef CONFIG_SCHED_DEBUG
1039         /*
1040          * A copy of (rq::clock_update_flags & RQCF_UPDATED) for the
1041          * current pin context is stashed here in case it needs to be
1042          * restored in rq_repin_lock().
1043          */
1044         unsigned int clock_update_flags;
1045 #endif
1046 };
1047
1048 static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf)
1049 {
1050         rf->cookie = lockdep_pin_lock(&rq->lock);
1051
1052 #ifdef CONFIG_SCHED_DEBUG
1053         rq->clock_update_flags &= (RQCF_REQ_SKIP|RQCF_ACT_SKIP);
1054         rf->clock_update_flags = 0;
1055 #endif
1056 }
1057
1058 static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
1059 {
1060 #ifdef CONFIG_SCHED_DEBUG
1061         if (rq->clock_update_flags > RQCF_ACT_SKIP)
1062                 rf->clock_update_flags = RQCF_UPDATED;
1063 #endif
1064
1065         lockdep_unpin_lock(&rq->lock, rf->cookie);
1066 }
1067
1068 static inline void rq_repin_lock(struct rq *rq, struct rq_flags *rf)
1069 {
1070         lockdep_repin_lock(&rq->lock, rf->cookie);
1071
1072 #ifdef CONFIG_SCHED_DEBUG
1073         /*
1074          * Restore the value we stashed in @rf for this pin context.
1075          */
1076         rq->clock_update_flags |= rf->clock_update_flags;
1077 #endif
1078 }
1079
1080 struct rq *__task_rq_lock(struct task_struct *p, struct rq_flags *rf)
1081         __acquires(rq->lock);
1082
1083 struct rq *task_rq_lock(struct task_struct *p, struct rq_flags *rf)
1084         __acquires(p->pi_lock)
1085         __acquires(rq->lock);
1086
1087 static inline void __task_rq_unlock(struct rq *rq, struct rq_flags *rf)
1088         __releases(rq->lock)
1089 {
1090         rq_unpin_lock(rq, rf);
1091         raw_spin_unlock(&rq->lock);
1092 }
1093
1094 static inline void
1095 task_rq_unlock(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
1096         __releases(rq->lock)
1097         __releases(p->pi_lock)
1098 {
1099         rq_unpin_lock(rq, rf);
1100         raw_spin_unlock(&rq->lock);
1101         raw_spin_unlock_irqrestore(&p->pi_lock, rf->flags);
1102 }
1103
1104 static inline void
1105 rq_lock_irqsave(struct rq *rq, struct rq_flags *rf)
1106         __acquires(rq->lock)
1107 {
1108         raw_spin_lock_irqsave(&rq->lock, rf->flags);
1109         rq_pin_lock(rq, rf);
1110 }
1111
1112 static inline void
1113 rq_lock_irq(struct rq *rq, struct rq_flags *rf)
1114         __acquires(rq->lock)
1115 {
1116         raw_spin_lock_irq(&rq->lock);
1117         rq_pin_lock(rq, rf);
1118 }
1119
1120 static inline void
1121 rq_lock(struct rq *rq, struct rq_flags *rf)
1122         __acquires(rq->lock)
1123 {
1124         raw_spin_lock(&rq->lock);
1125         rq_pin_lock(rq, rf);
1126 }
1127
1128 static inline void
1129 rq_relock(struct rq *rq, struct rq_flags *rf)
1130         __acquires(rq->lock)
1131 {
1132         raw_spin_lock(&rq->lock);
1133         rq_repin_lock(rq, rf);
1134 }
1135
1136 static inline void
1137 rq_unlock_irqrestore(struct rq *rq, struct rq_flags *rf)
1138         __releases(rq->lock)
1139 {
1140         rq_unpin_lock(rq, rf);
1141         raw_spin_unlock_irqrestore(&rq->lock, rf->flags);
1142 }
1143
1144 static inline void
1145 rq_unlock_irq(struct rq *rq, struct rq_flags *rf)
1146         __releases(rq->lock)
1147 {
1148         rq_unpin_lock(rq, rf);
1149         raw_spin_unlock_irq(&rq->lock);
1150 }
1151
1152 static inline void
1153 rq_unlock(struct rq *rq, struct rq_flags *rf)
1154         __releases(rq->lock)
1155 {
1156         rq_unpin_lock(rq, rf);
1157         raw_spin_unlock(&rq->lock);
1158 }
1159
1160 #ifdef CONFIG_NUMA
1161 enum numa_topology_type {
1162         NUMA_DIRECT,
1163         NUMA_GLUELESS_MESH,
1164         NUMA_BACKPLANE,
1165 };
1166 extern enum numa_topology_type sched_numa_topology_type;
1167 extern int sched_max_numa_distance;
1168 extern bool find_numa_distance(int distance);
1169 #endif
1170
1171 #ifdef CONFIG_NUMA
1172 extern void sched_init_numa(void);
1173 extern void sched_domains_numa_masks_set(unsigned int cpu);
1174 extern void sched_domains_numa_masks_clear(unsigned int cpu);
1175 #else
1176 static inline void sched_init_numa(void) { }
1177 static inline void sched_domains_numa_masks_set(unsigned int cpu) { }
1178 static inline void sched_domains_numa_masks_clear(unsigned int cpu) { }
1179 #endif
1180
1181 #ifdef CONFIG_NUMA_BALANCING
1182 /* The regions in numa_faults array from task_struct */
1183 enum numa_faults_stats {
1184         NUMA_MEM = 0,
1185         NUMA_CPU,
1186         NUMA_MEMBUF,
1187         NUMA_CPUBUF
1188 };
1189 extern void sched_setnuma(struct task_struct *p, int node);
1190 extern int migrate_task_to(struct task_struct *p, int cpu);
1191 extern int migrate_swap(struct task_struct *p, struct task_struct *t,
1192                         int cpu, int scpu);
1193 extern void init_numa_balancing(unsigned long clone_flags, struct task_struct *p);
1194 #else
1195 static inline void
1196 init_numa_balancing(unsigned long clone_flags, struct task_struct *p)
1197 {
1198 }
1199 #endif /* CONFIG_NUMA_BALANCING */
1200
1201 #ifdef CONFIG_SMP
1202
1203 static inline void
1204 queue_balance_callback(struct rq *rq,
1205                        struct callback_head *head,
1206                        void (*func)(struct rq *rq))
1207 {
1208         lockdep_assert_held(&rq->lock);
1209
1210         if (unlikely(head->next))
1211                 return;
1212
1213         head->func = (void (*)(struct callback_head *))func;
1214         head->next = rq->balance_callback;
1215         rq->balance_callback = head;
1216 }
1217
1218 extern void sched_ttwu_pending(void);
1219
1220 #define rcu_dereference_check_sched_domain(p) \
1221         rcu_dereference_check((p), \
1222                               lockdep_is_held(&sched_domains_mutex))
1223
1224 /*
1225  * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
1226  * See detach_destroy_domains: synchronize_sched for details.
1227  *
1228  * The domain tree of any CPU may only be accessed from within
1229  * preempt-disabled sections.
1230  */
1231 #define for_each_domain(cpu, __sd) \
1232         for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
1233                         __sd; __sd = __sd->parent)
1234
1235 #define for_each_lower_domain(sd) for (; sd; sd = sd->child)
1236
1237 /**
1238  * highest_flag_domain - Return highest sched_domain containing flag.
1239  * @cpu:        The CPU whose highest level of sched domain is to
1240  *              be returned.
1241  * @flag:       The flag to check for the highest sched_domain
1242  *              for the given CPU.
1243  *
1244  * Returns the highest sched_domain of a CPU which contains the given flag.
1245  */
1246 static inline struct sched_domain *highest_flag_domain(int cpu, int flag)
1247 {
1248         struct sched_domain *sd, *hsd = NULL;
1249
1250         for_each_domain(cpu, sd) {
1251                 if (!(sd->flags & flag))
1252                         break;
1253                 hsd = sd;
1254         }
1255
1256         return hsd;
1257 }
1258
1259 static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
1260 {
1261         struct sched_domain *sd;
1262
1263         for_each_domain(cpu, sd) {
1264                 if (sd->flags & flag)
1265                         break;
1266         }
1267
1268         return sd;
1269 }
1270
1271 DECLARE_PER_CPU(struct sched_domain *, sd_llc);
1272 DECLARE_PER_CPU(int, sd_llc_size);
1273 DECLARE_PER_CPU(int, sd_llc_id);
1274 DECLARE_PER_CPU(struct sched_domain_shared *, sd_llc_shared);
1275 DECLARE_PER_CPU(struct sched_domain *, sd_numa);
1276 DECLARE_PER_CPU(struct sched_domain *, sd_asym);
1277 extern struct static_key_false sched_asym_cpucapacity;
1278
1279 struct sched_group_capacity {
1280         atomic_t                ref;
1281         /*
1282          * CPU capacity of this group, SCHED_CAPACITY_SCALE being max capacity
1283          * for a single CPU.
1284          */
1285         unsigned long           capacity;
1286         unsigned long           min_capacity;           /* Min per-CPU capacity in group */
1287         unsigned long           max_capacity;           /* Max per-CPU capacity in group */
1288         unsigned long           next_update;
1289         int                     imbalance;              /* XXX unrelated to capacity but shared group state */
1290
1291 #ifdef CONFIG_SCHED_DEBUG
1292         int                     id;
1293 #endif
1294
1295         unsigned long           cpumask[0];             /* Balance mask */
1296 };
1297
1298 struct sched_group {
1299         struct sched_group      *next;                  /* Must be a circular list */
1300         atomic_t                ref;
1301
1302         unsigned int            group_weight;
1303         struct sched_group_capacity *sgc;
1304         int                     asym_prefer_cpu;        /* CPU of highest priority in group */
1305
1306         /*
1307          * The CPUs this group covers.
1308          *
1309          * NOTE: this field is variable length. (Allocated dynamically
1310          * by attaching extra space to the end of the structure,
1311          * depending on how many CPUs the kernel has booted up with)
1312          */
1313         unsigned long           cpumask[0];
1314 };
1315
1316 static inline struct cpumask *sched_group_span(struct sched_group *sg)
1317 {
1318         return to_cpumask(sg->cpumask);
1319 }
1320
1321 /*
1322  * See build_balance_mask().
1323  */
1324 static inline struct cpumask *group_balance_mask(struct sched_group *sg)
1325 {
1326         return to_cpumask(sg->sgc->cpumask);
1327 }
1328
1329 /**
1330  * group_first_cpu - Returns the first CPU in the cpumask of a sched_group.
1331  * @group: The group whose first CPU is to be returned.
1332  */
1333 static inline unsigned int group_first_cpu(struct sched_group *group)
1334 {
1335         return cpumask_first(sched_group_span(group));
1336 }
1337
1338 extern int group_balance_cpu(struct sched_group *sg);
1339
1340 #if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL)
1341 void register_sched_domain_sysctl(void);
1342 void dirty_sched_domain_sysctl(int cpu);
1343 void unregister_sched_domain_sysctl(void);
1344 #else
1345 static inline void register_sched_domain_sysctl(void)
1346 {
1347 }
1348 static inline void dirty_sched_domain_sysctl(int cpu)
1349 {
1350 }
1351 static inline void unregister_sched_domain_sysctl(void)
1352 {
1353 }
1354 #endif
1355
1356 #else
1357
1358 static inline void sched_ttwu_pending(void) { }
1359
1360 #endif /* CONFIG_SMP */
1361
1362 #include "stats.h"
1363 #include "autogroup.h"
1364
1365 #ifdef CONFIG_CGROUP_SCHED
1366
1367 /*
1368  * Return the group to which this tasks belongs.
1369  *
1370  * We cannot use task_css() and friends because the cgroup subsystem
1371  * changes that value before the cgroup_subsys::attach() method is called,
1372  * therefore we cannot pin it and might observe the wrong value.
1373  *
1374  * The same is true for autogroup's p->signal->autogroup->tg, the autogroup
1375  * core changes this before calling sched_move_task().
1376  *
1377  * Instead we use a 'copy' which is updated from sched_move_task() while
1378  * holding both task_struct::pi_lock and rq::lock.
1379  */
1380 static inline struct task_group *task_group(struct task_struct *p)
1381 {
1382         return p->sched_task_group;
1383 }
1384
1385 /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
1386 static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
1387 {
1388 #if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED)
1389         struct task_group *tg = task_group(p);
1390 #endif
1391
1392 #ifdef CONFIG_FAIR_GROUP_SCHED
1393         set_task_rq_fair(&p->se, p->se.cfs_rq, tg->cfs_rq[cpu]);
1394         p->se.cfs_rq = tg->cfs_rq[cpu];
1395         p->se.parent = tg->se[cpu];
1396 #endif
1397
1398 #ifdef CONFIG_RT_GROUP_SCHED
1399         p->rt.rt_rq  = tg->rt_rq[cpu];
1400         p->rt.parent = tg->rt_se[cpu];
1401 #endif
1402 }
1403
1404 #else /* CONFIG_CGROUP_SCHED */
1405
1406 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
1407 static inline struct task_group *task_group(struct task_struct *p)
1408 {
1409         return NULL;
1410 }
1411
1412 #endif /* CONFIG_CGROUP_SCHED */
1413
1414 static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
1415 {
1416         set_task_rq(p, cpu);
1417 #ifdef CONFIG_SMP
1418         /*
1419          * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
1420          * successfuly executed on another CPU. We must ensure that updates of
1421          * per-task data have been completed by this moment.
1422          */
1423         smp_wmb();
1424 #ifdef CONFIG_THREAD_INFO_IN_TASK
1425         p->cpu = cpu;
1426 #else
1427         task_thread_info(p)->cpu = cpu;
1428 #endif
1429         p->wake_cpu = cpu;
1430 #endif
1431 }
1432
1433 /*
1434  * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
1435  */
1436 #ifdef CONFIG_SCHED_DEBUG
1437 # include <linux/static_key.h>
1438 # define const_debug __read_mostly
1439 #else
1440 # define const_debug const
1441 #endif
1442
1443 #define SCHED_FEAT(name, enabled)       \
1444         __SCHED_FEAT_##name ,
1445
1446 enum {
1447 #include "features.h"
1448         __SCHED_FEAT_NR,
1449 };
1450
1451 #undef SCHED_FEAT
1452
1453 #if defined(CONFIG_SCHED_DEBUG) && defined(HAVE_JUMP_LABEL)
1454
1455 /*
1456  * To support run-time toggling of sched features, all the translation units
1457  * (but core.c) reference the sysctl_sched_features defined in core.c.
1458  */
1459 extern const_debug unsigned int sysctl_sched_features;
1460
1461 #define SCHED_FEAT(name, enabled)                                       \
1462 static __always_inline bool static_branch_##name(struct static_key *key) \
1463 {                                                                       \
1464         return static_key_##enabled(key);                               \
1465 }
1466
1467 #include "features.h"
1468 #undef SCHED_FEAT
1469
1470 extern struct static_key sched_feat_keys[__SCHED_FEAT_NR];
1471 #define sched_feat(x) (static_branch_##x(&sched_feat_keys[__SCHED_FEAT_##x]))
1472
1473 #else /* !(SCHED_DEBUG && HAVE_JUMP_LABEL) */
1474
1475 /*
1476  * Each translation unit has its own copy of sysctl_sched_features to allow
1477  * constants propagation at compile time and compiler optimization based on
1478  * features default.
1479  */
1480 #define SCHED_FEAT(name, enabled)       \
1481         (1UL << __SCHED_FEAT_##name) * enabled |
1482 static const_debug __maybe_unused unsigned int sysctl_sched_features =
1483 #include "features.h"
1484         0;
1485 #undef SCHED_FEAT
1486
1487 #define sched_feat(x) !!(sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
1488
1489 #endif /* SCHED_DEBUG && HAVE_JUMP_LABEL */
1490
1491 extern struct static_key_false sched_numa_balancing;
1492 extern struct static_key_false sched_schedstats;
1493
1494 static inline u64 global_rt_period(void)
1495 {
1496         return (u64)sysctl_sched_rt_period * NSEC_PER_USEC;
1497 }
1498
1499 static inline u64 global_rt_runtime(void)
1500 {
1501         if (sysctl_sched_rt_runtime < 0)
1502                 return RUNTIME_INF;
1503
1504         return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
1505 }
1506
1507 static inline int task_current(struct rq *rq, struct task_struct *p)
1508 {
1509         return rq->curr == p;
1510 }
1511
1512 static inline int task_running(struct rq *rq, struct task_struct *p)
1513 {
1514 #ifdef CONFIG_SMP
1515         return p->on_cpu;
1516 #else
1517         return task_current(rq, p);
1518 #endif
1519 }
1520
1521 static inline int task_on_rq_queued(struct task_struct *p)
1522 {
1523         return p->on_rq == TASK_ON_RQ_QUEUED;
1524 }
1525
1526 static inline int task_on_rq_migrating(struct task_struct *p)
1527 {
1528         return p->on_rq == TASK_ON_RQ_MIGRATING;
1529 }
1530
1531 /*
1532  * wake flags
1533  */
1534 #define WF_SYNC                 0x01            /* Waker goes to sleep after wakeup */
1535 #define WF_FORK                 0x02            /* Child wakeup after fork */
1536 #define WF_MIGRATED             0x4             /* Internal use, task got migrated */
1537
1538 /*
1539  * To aid in avoiding the subversion of "niceness" due to uneven distribution
1540  * of tasks with abnormal "nice" values across CPUs the contribution that
1541  * each task makes to its run queue's load is weighted according to its
1542  * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
1543  * scaled version of the new time slice allocation that they receive on time
1544  * slice expiry etc.
1545  */
1546
1547 #define WEIGHT_IDLEPRIO         3
1548 #define WMULT_IDLEPRIO          1431655765
1549
1550 extern const int                sched_prio_to_weight[40];
1551 extern const u32                sched_prio_to_wmult[40];
1552
1553 /*
1554  * {de,en}queue flags:
1555  *
1556  * DEQUEUE_SLEEP  - task is no longer runnable
1557  * ENQUEUE_WAKEUP - task just became runnable
1558  *
1559  * SAVE/RESTORE - an otherwise spurious dequeue/enqueue, done to ensure tasks
1560  *                are in a known state which allows modification. Such pairs
1561  *                should preserve as much state as possible.
1562  *
1563  * MOVE - paired with SAVE/RESTORE, explicitly does not preserve the location
1564  *        in the runqueue.
1565  *
1566  * ENQUEUE_HEAD      - place at front of runqueue (tail if not specified)
1567  * ENQUEUE_REPLENISH - CBS (replenish runtime and postpone deadline)
1568  * ENQUEUE_MIGRATED  - the task was migrated during wakeup
1569  *
1570  */
1571
1572 #define DEQUEUE_SLEEP           0x01
1573 #define DEQUEUE_SAVE            0x02 /* Matches ENQUEUE_RESTORE */
1574 #define DEQUEUE_MOVE            0x04 /* Matches ENQUEUE_MOVE */
1575 #define DEQUEUE_NOCLOCK         0x08 /* Matches ENQUEUE_NOCLOCK */
1576
1577 #define ENQUEUE_WAKEUP          0x01
1578 #define ENQUEUE_RESTORE         0x02
1579 #define ENQUEUE_MOVE            0x04
1580 #define ENQUEUE_NOCLOCK         0x08
1581
1582 #define ENQUEUE_HEAD            0x10
1583 #define ENQUEUE_REPLENISH       0x20
1584 #ifdef CONFIG_SMP
1585 #define ENQUEUE_MIGRATED        0x40
1586 #else
1587 #define ENQUEUE_MIGRATED        0x00
1588 #endif
1589
1590 #define RETRY_TASK              ((void *)-1UL)
1591
1592 struct sched_class {
1593         const struct sched_class *next;
1594
1595         void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
1596         void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
1597         void (*yield_task)   (struct rq *rq);
1598         bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);
1599
1600         void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
1601
1602         /*
1603          * It is the responsibility of the pick_next_task() method that will
1604          * return the next task to call put_prev_task() on the @prev task or
1605          * something equivalent.
1606          *
1607          * May return RETRY_TASK when it finds a higher prio class has runnable
1608          * tasks.
1609          */
1610         struct task_struct * (*pick_next_task)(struct rq *rq,
1611                                                struct task_struct *prev,
1612                                                struct rq_flags *rf);
1613         void (*put_prev_task)(struct rq *rq, struct task_struct *p);
1614
1615 #ifdef CONFIG_SMP
1616         int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
1617         void (*migrate_task_rq)(struct task_struct *p, int new_cpu);
1618
1619         void (*task_woken)(struct rq *this_rq, struct task_struct *task);
1620
1621         void (*set_cpus_allowed)(struct task_struct *p,
1622                                  const struct cpumask *newmask);
1623
1624         void (*rq_online)(struct rq *rq);
1625         void (*rq_offline)(struct rq *rq);
1626 #endif
1627
1628         void (*set_curr_task)(struct rq *rq);
1629         void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
1630         void (*task_fork)(struct task_struct *p);
1631         void (*task_dead)(struct task_struct *p);
1632
1633         /*
1634          * The switched_from() call is allowed to drop rq->lock, therefore we
1635          * cannot assume the switched_from/switched_to pair is serliazed by
1636          * rq->lock. They are however serialized by p->pi_lock.
1637          */
1638         void (*switched_from)(struct rq *this_rq, struct task_struct *task);
1639         void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
1640         void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
1641                               int oldprio);
1642
1643         unsigned int (*get_rr_interval)(struct rq *rq,
1644                                         struct task_struct *task);
1645
1646         void (*update_curr)(struct rq *rq);
1647
1648 #define TASK_SET_GROUP          0
1649 #define TASK_MOVE_GROUP         1
1650
1651 #ifdef CONFIG_FAIR_GROUP_SCHED
1652         void (*task_change_group)(struct task_struct *p, int type);
1653 #endif
1654 };
1655
1656 static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
1657 {
1658         prev->sched_class->put_prev_task(rq, prev);
1659 }
1660
1661 static inline void set_curr_task(struct rq *rq, struct task_struct *curr)
1662 {
1663         curr->sched_class->set_curr_task(rq);
1664 }
1665
1666 #ifdef CONFIG_SMP
1667 #define sched_class_highest (&stop_sched_class)
1668 #else
1669 #define sched_class_highest (&dl_sched_class)
1670 #endif
1671 #define for_each_class(class) \
1672    for (class = sched_class_highest; class; class = class->next)
1673
1674 extern const struct sched_class stop_sched_class;
1675 extern const struct sched_class dl_sched_class;
1676 extern const struct sched_class rt_sched_class;
1677 extern const struct sched_class fair_sched_class;
1678 extern const struct sched_class idle_sched_class;
1679
1680
1681 #ifdef CONFIG_SMP
1682
1683 extern void update_group_capacity(struct sched_domain *sd, int cpu);
1684
1685 extern void trigger_load_balance(struct rq *rq);
1686
1687 extern void set_cpus_allowed_common(struct task_struct *p, const struct cpumask *new_mask);
1688
1689 #endif
1690
1691 #ifdef CONFIG_CPU_IDLE
1692 static inline void idle_set_state(struct rq *rq,
1693                                   struct cpuidle_state *idle_state)
1694 {
1695         rq->idle_state = idle_state;
1696 }
1697
1698 static inline struct cpuidle_state *idle_get_state(struct rq *rq)
1699 {
1700         SCHED_WARN_ON(!rcu_read_lock_held());
1701
1702         return rq->idle_state;
1703 }
1704 #else
1705 static inline void idle_set_state(struct rq *rq,
1706                                   struct cpuidle_state *idle_state)
1707 {
1708 }
1709
1710 static inline struct cpuidle_state *idle_get_state(struct rq *rq)
1711 {
1712         return NULL;
1713 }
1714 #endif
1715
1716 extern void schedule_idle(void);
1717
1718 extern void sysrq_sched_debug_show(void);
1719 extern void sched_init_granularity(void);
1720 extern void update_max_interval(void);
1721
1722 extern void init_sched_dl_class(void);
1723 extern void init_sched_rt_class(void);
1724 extern void init_sched_fair_class(void);
1725
1726 extern void reweight_task(struct task_struct *p, int prio);
1727
1728 extern void resched_curr(struct rq *rq);
1729 extern void resched_cpu(int cpu);
1730
1731 extern struct rt_bandwidth def_rt_bandwidth;
1732 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
1733
1734 extern struct dl_bandwidth def_dl_bandwidth;
1735 extern void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime);
1736 extern void init_dl_task_timer(struct sched_dl_entity *dl_se);
1737 extern void init_dl_inactive_task_timer(struct sched_dl_entity *dl_se);
1738 extern void init_dl_rq_bw_ratio(struct dl_rq *dl_rq);
1739
1740 #define BW_SHIFT                20
1741 #define BW_UNIT                 (1 << BW_SHIFT)
1742 #define RATIO_SHIFT             8
1743 unsigned long to_ratio(u64 period, u64 runtime);
1744
1745 extern void init_entity_runnable_average(struct sched_entity *se);
1746 extern void post_init_entity_util_avg(struct sched_entity *se);
1747
1748 #ifdef CONFIG_NO_HZ_FULL
1749 extern bool sched_can_stop_tick(struct rq *rq);
1750 extern int __init sched_tick_offload_init(void);
1751
1752 /*
1753  * Tick may be needed by tasks in the runqueue depending on their policy and
1754  * requirements. If tick is needed, lets send the target an IPI to kick it out of
1755  * nohz mode if necessary.
1756  */
1757 static inline void sched_update_tick_dependency(struct rq *rq)
1758 {
1759         int cpu;
1760
1761         if (!tick_nohz_full_enabled())
1762                 return;
1763
1764         cpu = cpu_of(rq);
1765
1766         if (!tick_nohz_full_cpu(cpu))
1767                 return;
1768
1769         if (sched_can_stop_tick(rq))
1770                 tick_nohz_dep_clear_cpu(cpu, TICK_DEP_BIT_SCHED);
1771         else
1772                 tick_nohz_dep_set_cpu(cpu, TICK_DEP_BIT_SCHED);
1773 }
1774 #else
1775 static inline int sched_tick_offload_init(void) { return 0; }
1776 static inline void sched_update_tick_dependency(struct rq *rq) { }
1777 #endif
1778
1779 static inline void add_nr_running(struct rq *rq, unsigned count)
1780 {
1781         unsigned prev_nr = rq->nr_running;
1782
1783         rq->nr_running = prev_nr + count;
1784
1785         if (prev_nr < 2 && rq->nr_running >= 2) {
1786 #ifdef CONFIG_SMP
1787                 if (!READ_ONCE(rq->rd->overload))
1788                         WRITE_ONCE(rq->rd->overload, 1);
1789 #endif
1790         }
1791
1792         sched_update_tick_dependency(rq);
1793 }
1794
1795 static inline void sub_nr_running(struct rq *rq, unsigned count)
1796 {
1797         rq->nr_running -= count;
1798         /* Check if we still need preemption */
1799         sched_update_tick_dependency(rq);
1800 }
1801
1802 extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
1803 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
1804
1805 extern void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags);
1806
1807 extern const_debug unsigned int sysctl_sched_nr_migrate;
1808 extern const_debug unsigned int sysctl_sched_migration_cost;
1809
1810 #ifdef CONFIG_SCHED_HRTICK
1811
1812 /*
1813  * Use hrtick when:
1814  *  - enabled by features
1815  *  - hrtimer is actually high res
1816  */
1817 static inline int hrtick_enabled(struct rq *rq)
1818 {
1819         if (!sched_feat(HRTICK))
1820                 return 0;
1821         if (!cpu_active(cpu_of(rq)))
1822                 return 0;
1823         return hrtimer_is_hres_active(&rq->hrtick_timer);
1824 }
1825
1826 void hrtick_start(struct rq *rq, u64 delay);
1827
1828 #else
1829
1830 static inline int hrtick_enabled(struct rq *rq)
1831 {
1832         return 0;
1833 }
1834
1835 #endif /* CONFIG_SCHED_HRTICK */
1836
1837 #ifndef arch_scale_freq_capacity
1838 static __always_inline
1839 unsigned long arch_scale_freq_capacity(int cpu)
1840 {
1841         return SCHED_CAPACITY_SCALE;
1842 }
1843 #endif
1844
1845 #ifdef CONFIG_SMP
1846 #ifndef arch_scale_cpu_capacity
1847 static __always_inline
1848 unsigned long arch_scale_cpu_capacity(struct sched_domain *sd, int cpu)
1849 {
1850         if (sd && (sd->flags & SD_SHARE_CPUCAPACITY) && (sd->span_weight > 1))
1851                 return sd->smt_gain / sd->span_weight;
1852
1853         return SCHED_CAPACITY_SCALE;
1854 }
1855 #endif
1856 #else
1857 #ifndef arch_scale_cpu_capacity
1858 static __always_inline
1859 unsigned long arch_scale_cpu_capacity(void __always_unused *sd, int cpu)
1860 {
1861         return SCHED_CAPACITY_SCALE;
1862 }
1863 #endif
1864 #endif
1865
1866 #ifdef CONFIG_SMP
1867 #ifdef CONFIG_PREEMPT
1868
1869 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2);
1870
1871 /*
1872  * fair double_lock_balance: Safely acquires both rq->locks in a fair
1873  * way at the expense of forcing extra atomic operations in all
1874  * invocations.  This assures that the double_lock is acquired using the
1875  * same underlying policy as the spinlock_t on this architecture, which
1876  * reduces latency compared to the unfair variant below.  However, it
1877  * also adds more overhead and therefore may reduce throughput.
1878  */
1879 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
1880         __releases(this_rq->lock)
1881         __acquires(busiest->lock)
1882         __acquires(this_rq->lock)
1883 {
1884         raw_spin_unlock(&this_rq->lock);
1885         double_rq_lock(this_rq, busiest);
1886
1887         return 1;
1888 }
1889
1890 #else
1891 /*
1892  * Unfair double_lock_balance: Optimizes throughput at the expense of
1893  * latency by eliminating extra atomic operations when the locks are
1894  * already in proper order on entry.  This favors lower CPU-ids and will
1895  * grant the double lock to lower CPUs over higher ids under contention,
1896  * regardless of entry order into the function.
1897  */
1898 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
1899         __releases(this_rq->lock)
1900         __acquires(busiest->lock)
1901         __acquires(this_rq->lock)
1902 {
1903         int ret = 0;
1904
1905         if (unlikely(!raw_spin_trylock(&busiest->lock))) {
1906                 if (busiest < this_rq) {
1907                         raw_spin_unlock(&this_rq->lock);
1908                         raw_spin_lock(&busiest->lock);
1909                         raw_spin_lock_nested(&this_rq->lock,
1910                                               SINGLE_DEPTH_NESTING);
1911                         ret = 1;
1912                 } else
1913                         raw_spin_lock_nested(&busiest->lock,
1914                                               SINGLE_DEPTH_NESTING);
1915         }
1916         return ret;
1917 }
1918
1919 #endif /* CONFIG_PREEMPT */
1920
1921 /*
1922  * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
1923  */
1924 static inline int double_lock_balance(struct rq *this_rq, struct rq *busiest)
1925 {
1926         if (unlikely(!irqs_disabled())) {
1927                 /* printk() doesn't work well under rq->lock */
1928                 raw_spin_unlock(&this_rq->lock);
1929                 BUG_ON(1);
1930         }
1931
1932         return _double_lock_balance(this_rq, busiest);
1933 }
1934
1935 static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
1936         __releases(busiest->lock)
1937 {
1938         raw_spin_unlock(&busiest->lock);
1939         lock_set_subclass(&this_rq->lock.dep_map, 0, _RET_IP_);
1940 }
1941
1942 static inline void double_lock(spinlock_t *l1, spinlock_t *l2)
1943 {
1944         if (l1 > l2)
1945                 swap(l1, l2);
1946
1947         spin_lock(l1);
1948         spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
1949 }
1950
1951 static inline void double_lock_irq(spinlock_t *l1, spinlock_t *l2)
1952 {
1953         if (l1 > l2)
1954                 swap(l1, l2);
1955
1956         spin_lock_irq(l1);
1957         spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
1958 }
1959
1960 static inline void double_raw_lock(raw_spinlock_t *l1, raw_spinlock_t *l2)
1961 {
1962         if (l1 > l2)
1963                 swap(l1, l2);
1964
1965         raw_spin_lock(l1);
1966         raw_spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
1967 }
1968
1969 /*
1970  * double_rq_lock - safely lock two runqueues
1971  *
1972  * Note this does not disable interrupts like task_rq_lock,
1973  * you need to do so manually before calling.
1974  */
1975 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
1976         __acquires(rq1->lock)
1977         __acquires(rq2->lock)
1978 {
1979         BUG_ON(!irqs_disabled());
1980         if (rq1 == rq2) {
1981                 raw_spin_lock(&rq1->lock);
1982                 __acquire(rq2->lock);   /* Fake it out ;) */
1983         } else {
1984                 if (rq1 < rq2) {
1985                         raw_spin_lock(&rq1->lock);
1986                         raw_spin_lock_nested(&rq2->lock, SINGLE_DEPTH_NESTING);
1987                 } else {
1988                         raw_spin_lock(&rq2->lock);
1989                         raw_spin_lock_nested(&rq1->lock, SINGLE_DEPTH_NESTING);
1990                 }
1991         }
1992 }
1993
1994 /*
1995  * double_rq_unlock - safely unlock two runqueues
1996  *
1997  * Note this does not restore interrupts like task_rq_unlock,
1998  * you need to do so manually after calling.
1999  */
2000 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
2001         __releases(rq1->lock)
2002         __releases(rq2->lock)
2003 {
2004         raw_spin_unlock(&rq1->lock);
2005         if (rq1 != rq2)
2006                 raw_spin_unlock(&rq2->lock);
2007         else
2008                 __release(rq2->lock);
2009 }
2010
2011 extern void set_rq_online (struct rq *rq);
2012 extern void set_rq_offline(struct rq *rq);
2013 extern bool sched_smp_initialized;
2014
2015 #else /* CONFIG_SMP */
2016
2017 /*
2018  * double_rq_lock - safely lock two runqueues
2019  *
2020  * Note this does not disable interrupts like task_rq_lock,
2021  * you need to do so manually before calling.
2022  */
2023 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
2024         __acquires(rq1->lock)
2025         __acquires(rq2->lock)
2026 {
2027         BUG_ON(!irqs_disabled());
2028         BUG_ON(rq1 != rq2);
2029         raw_spin_lock(&rq1->lock);
2030         __acquire(rq2->lock);   /* Fake it out ;) */
2031 }
2032
2033 /*
2034  * double_rq_unlock - safely unlock two runqueues
2035  *
2036  * Note this does not restore interrupts like task_rq_unlock,
2037  * you need to do so manually after calling.
2038  */
2039 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
2040         __releases(rq1->lock)
2041         __releases(rq2->lock)
2042 {
2043         BUG_ON(rq1 != rq2);
2044         raw_spin_unlock(&rq1->lock);
2045         __release(rq2->lock);
2046 }
2047
2048 #endif
2049
2050 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq);
2051 extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq);
2052
2053 #ifdef  CONFIG_SCHED_DEBUG
2054 extern bool sched_debug_enabled;
2055
2056 extern void print_cfs_stats(struct seq_file *m, int cpu);
2057 extern void print_rt_stats(struct seq_file *m, int cpu);
2058 extern void print_dl_stats(struct seq_file *m, int cpu);
2059 extern void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq);
2060 extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq);
2061 extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq);
2062 #ifdef CONFIG_NUMA_BALANCING
2063 extern void
2064 show_numa_stats(struct task_struct *p, struct seq_file *m);
2065 extern void
2066 print_numa_stats(struct seq_file *m, int node, unsigned long tsf,
2067         unsigned long tpf, unsigned long gsf, unsigned long gpf);
2068 #endif /* CONFIG_NUMA_BALANCING */
2069 #endif /* CONFIG_SCHED_DEBUG */
2070
2071 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
2072 extern void init_rt_rq(struct rt_rq *rt_rq);
2073 extern void init_dl_rq(struct dl_rq *dl_rq);
2074
2075 extern void cfs_bandwidth_usage_inc(void);
2076 extern void cfs_bandwidth_usage_dec(void);
2077
2078 #ifdef CONFIG_NO_HZ_COMMON
2079 #define NOHZ_BALANCE_KICK_BIT   0
2080 #define NOHZ_STATS_KICK_BIT     1
2081
2082 #define NOHZ_BALANCE_KICK       BIT(NOHZ_BALANCE_KICK_BIT)
2083 #define NOHZ_STATS_KICK         BIT(NOHZ_STATS_KICK_BIT)
2084
2085 #define NOHZ_KICK_MASK  (NOHZ_BALANCE_KICK | NOHZ_STATS_KICK)
2086
2087 #define nohz_flags(cpu) (&cpu_rq(cpu)->nohz_flags)
2088
2089 extern void nohz_balance_exit_idle(struct rq *rq);
2090 #else
2091 static inline void nohz_balance_exit_idle(struct rq *rq) { }
2092 #endif
2093
2094
2095 #ifdef CONFIG_SMP
2096 static inline
2097 void __dl_update(struct dl_bw *dl_b, s64 bw)
2098 {
2099         struct root_domain *rd = container_of(dl_b, struct root_domain, dl_bw);
2100         int i;
2101
2102         RCU_LOCKDEP_WARN(!rcu_read_lock_sched_held(),
2103                          "sched RCU must be held");
2104         for_each_cpu_and(i, rd->span, cpu_active_mask) {
2105                 struct rq *rq = cpu_rq(i);
2106
2107                 rq->dl.extra_bw += bw;
2108         }
2109 }
2110 #else
2111 static inline
2112 void __dl_update(struct dl_bw *dl_b, s64 bw)
2113 {
2114         struct dl_rq *dl = container_of(dl_b, struct dl_rq, dl_bw);
2115
2116         dl->extra_bw += bw;
2117 }
2118 #endif
2119
2120
2121 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
2122 struct irqtime {
2123         u64                     total;
2124         u64                     tick_delta;
2125         u64                     irq_start_time;
2126         struct u64_stats_sync   sync;
2127 };
2128
2129 DECLARE_PER_CPU(struct irqtime, cpu_irqtime);
2130
2131 /*
2132  * Returns the irqtime minus the softirq time computed by ksoftirqd.
2133  * Otherwise ksoftirqd's sum_exec_runtime is substracted its own runtime
2134  * and never move forward.
2135  */
2136 static inline u64 irq_time_read(int cpu)
2137 {
2138         struct irqtime *irqtime = &per_cpu(cpu_irqtime, cpu);
2139         unsigned int seq;
2140         u64 total;
2141
2142         do {
2143                 seq = __u64_stats_fetch_begin(&irqtime->sync);
2144                 total = irqtime->total;
2145         } while (__u64_stats_fetch_retry(&irqtime->sync, seq));
2146
2147         return total;
2148 }
2149 #endif /* CONFIG_IRQ_TIME_ACCOUNTING */
2150
2151 #ifdef CONFIG_CPU_FREQ
2152 DECLARE_PER_CPU(struct update_util_data *, cpufreq_update_util_data);
2153
2154 /**
2155  * cpufreq_update_util - Take a note about CPU utilization changes.
2156  * @rq: Runqueue to carry out the update for.
2157  * @flags: Update reason flags.
2158  *
2159  * This function is called by the scheduler on the CPU whose utilization is
2160  * being updated.
2161  *
2162  * It can only be called from RCU-sched read-side critical sections.
2163  *
2164  * The way cpufreq is currently arranged requires it to evaluate the CPU
2165  * performance state (frequency/voltage) on a regular basis to prevent it from
2166  * being stuck in a completely inadequate performance level for too long.
2167  * That is not guaranteed to happen if the updates are only triggered from CFS
2168  * and DL, though, because they may not be coming in if only RT tasks are
2169  * active all the time (or there are RT tasks only).
2170  *
2171  * As a workaround for that issue, this function is called periodically by the
2172  * RT sched class to trigger extra cpufreq updates to prevent it from stalling,
2173  * but that really is a band-aid.  Going forward it should be replaced with
2174  * solutions targeted more specifically at RT tasks.
2175  */
2176 static inline void cpufreq_update_util(struct rq *rq, unsigned int flags)
2177 {
2178         struct update_util_data *data;
2179
2180         data = rcu_dereference_sched(*per_cpu_ptr(&cpufreq_update_util_data,
2181                                                   cpu_of(rq)));
2182         if (data)
2183                 data->func(data, rq_clock(rq), flags);
2184 }
2185 #else
2186 static inline void cpufreq_update_util(struct rq *rq, unsigned int flags) {}
2187 #endif /* CONFIG_CPU_FREQ */
2188
2189 #ifdef arch_scale_freq_capacity
2190 # ifndef arch_scale_freq_invariant
2191 #  define arch_scale_freq_invariant()   true
2192 # endif
2193 #else
2194 # define arch_scale_freq_invariant()    false
2195 #endif
2196
2197 #ifdef CONFIG_CPU_FREQ_GOV_SCHEDUTIL
2198 static inline unsigned long cpu_bw_dl(struct rq *rq)
2199 {
2200         return (rq->dl.running_bw * SCHED_CAPACITY_SCALE) >> BW_SHIFT;
2201 }
2202
2203 static inline unsigned long cpu_util_dl(struct rq *rq)
2204 {
2205         return READ_ONCE(rq->avg_dl.util_avg);
2206 }
2207
2208 static inline unsigned long cpu_util_cfs(struct rq *rq)
2209 {
2210         unsigned long util = READ_ONCE(rq->cfs.avg.util_avg);
2211
2212         if (sched_feat(UTIL_EST)) {
2213                 util = max_t(unsigned long, util,
2214                              READ_ONCE(rq->cfs.avg.util_est.enqueued));
2215         }
2216
2217         return util;
2218 }
2219
2220 static inline unsigned long cpu_util_rt(struct rq *rq)
2221 {
2222         return READ_ONCE(rq->avg_rt.util_avg);
2223 }
2224 #endif
2225
2226 #ifdef CONFIG_HAVE_SCHED_AVG_IRQ
2227 static inline unsigned long cpu_util_irq(struct rq *rq)
2228 {
2229         return rq->avg_irq.util_avg;
2230 }
2231
2232 static inline
2233 unsigned long scale_irq_capacity(unsigned long util, unsigned long irq, unsigned long max)
2234 {
2235         util *= (max - irq);
2236         util /= max;
2237
2238         return util;
2239
2240 }
2241 #else
2242 static inline unsigned long cpu_util_irq(struct rq *rq)
2243 {
2244         return 0;
2245 }
2246
2247 static inline
2248 unsigned long scale_irq_capacity(unsigned long util, unsigned long irq, unsigned long max)
2249 {
2250         return util;
2251 }
2252 #endif