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