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