~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/kernel/sched/sched.h

Version: ~ [ linux-4.15-rc8 ] ~ [ linux-4.14.13 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.76 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.111 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.48 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.91 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.53 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.98 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.27.62 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp