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