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