kernel/sched/sched.h

   1
   2 #include <linux/sched.h>
   3 #include <linux/sched/sysctl.h>
   4 #include <linux/mutex.h>
   5 #include <linux/spinlock.h>
   6 #include <linux/stop_machine.h>
   7
   8 #include "cpupri.h"
   9
  10 extern __read_mostly int scheduler_running;
  11
  12 /*
  13  * Convert user-nice values [ -20 ... 0 ... 19 ]
  14  * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
  15  * and back.
  16  */
  17 #define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
  18 #define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
  19 #define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)
  20
  21 /*
  22  * 'User priority' is the nice value converted to something we
  23  * can work with better when scaling various scheduler parameters,
  24  * it's a [ 0 ... 39 ] range.
  25  */
  26 #define USER_PRIO(p)            ((p)-MAX_RT_PRIO)
  27 #define TASK_USER_PRIO(p)       USER_PRIO((p)->static_prio)
  28 #define MAX_USER_PRIO           (USER_PRIO(MAX_PRIO))
  29
  30 /*
  31  * Helpers for converting nanosecond timing to jiffy resolution
  32  */
  33 #define NS_TO_JIFFIES(TIME)     ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))
  34
  35 #define NICE_0_LOAD             SCHED_LOAD_SCALE
  36 #define NICE_0_SHIFT            SCHED_LOAD_SHIFT
  37
  38 /*
  39  * These are the 'tuning knobs' of the scheduler:
  40  */
  41
  42 /*
  43  * single value that denotes runtime == period, ie unlimited time.
  44  */
  45 #define RUNTIME_INF     ((u64)~0ULL)
  46
  47 static inline int rt_policy(int policy)
  48 {
  49         if (policy == SCHED_FIFO || policy == SCHED_RR)
  50                 return 1;
  51         return 0;
  52 }
  53
  54 static inline int task_has_rt_policy(struct task_struct *p)
  55 {
  56         return rt_policy(p->policy);
  57 }
  58
  59 /*
  60  * This is the priority-queue data structure of the RT scheduling class:
  61  */
  62 struct rt_prio_array {
  63         DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
  64         struct list_head queue[MAX_RT_PRIO];
  65 };
  66
  67 struct rt_bandwidth {
  68         /* nests inside the rq lock: */
  69         raw_spinlock_t          rt_runtime_lock;
  70         ktime_t                 rt_period;
  71         u64                     rt_runtime;
  72         struct hrtimer          rt_period_timer;
  73 };
  74
  75 extern struct mutex sched_domains_mutex;
  76
  77 #ifdef CONFIG_CGROUP_SCHED
  78
  79 #include <linux/cgroup.h>
  80
  81 struct cfs_rq;
  82 struct rt_rq;
  83
  84 extern struct list_head task_groups;
  85
  86 struct cfs_bandwidth {
  87 #ifdef CONFIG_CFS_BANDWIDTH
  88         raw_spinlock_t lock;
  89         ktime_t period;
  90         u64 quota, runtime;
  91         s64 hierarchal_quota;
  92         u64 runtime_expires;
  93
  94         int idle, timer_active;
  95         struct hrtimer period_timer, slack_timer;
  96         struct list_head throttled_cfs_rq;
  97
  98         /* statistics */
  99         int nr_periods, nr_throttled;
 100         u64 throttled_time;
 101 #endif
 102 };
 103
 104 /* task group related information */
 105 struct task_group {
 106         struct cgroup_subsys_state css;
 107
 108 #ifdef CONFIG_FAIR_GROUP_SCHED
 109         /* schedulable entities of this group on each cpu */
 110         struct sched_entity **se;
 111         /* runqueue "owned" by this group on each cpu */
 112         struct cfs_rq **cfs_rq;
 113         unsigned long shares;
 114
 115         atomic_t load_weight;
 116         atomic64_t load_avg;
 117         atomic_t runnable_avg;
 118 #endif
 119
 120 #ifdef CONFIG_RT_GROUP_SCHED
 121         struct sched_rt_entity **rt_se;
 122         struct rt_rq **rt_rq;
 123
 124         struct rt_bandwidth rt_bandwidth;
 125 #endif
 126
 127         struct rcu_head rcu;
 128         struct list_head list;
 129
 130         struct task_group *parent;
 131         struct list_head siblings;
 132         struct list_head children;
 133
 134 #ifdef CONFIG_SCHED_AUTOGROUP
 135         struct autogroup *autogroup;
 136 #endif
 137
 138         struct cfs_bandwidth cfs_bandwidth;
 139 };
 140
 141 #ifdef CONFIG_FAIR_GROUP_SCHED
 142 #define ROOT_TASK_GROUP_LOAD    NICE_0_LOAD
 143
 144 /*
 145  * A weight of 0 or 1 can cause arithmetics problems.
 146  * A weight of a cfs_rq is the sum of weights of which entities
 147  * are queued on this cfs_rq, so a weight of a entity should not be
 148  * too large, so as the shares value of a task group.
 149  * (The default weight is 1024 - so there's no practical
 150  *  limitation from this.)
 151  */
 152 #define MIN_SHARES      (1UL <<  1)
 153 #define MAX_SHARES      (1UL << 18)
 154 #endif
 155
 156 /* Default task group.
 157  *      Every task in system belong to this group at bootup.
 158  */
 159 extern struct task_group root_task_group;
 160
 161 typedef int (*tg_visitor)(struct task_group *, void *);
 162
 163 extern int walk_tg_tree_from(struct task_group *from,
 164                              tg_visitor down, tg_visitor up, void *data);
 165
 166 /*
 167  * Iterate the full tree, calling @down when first entering a node and @up when
 168  * leaving it for the final time.
 169  *
 170  * Caller must hold rcu_lock or sufficient equivalent.
 171  */
 172 static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data)
 173 {
 174         return walk_tg_tree_from(&root_task_group, down, up, data);
 175 }
 176
 177 extern int tg_nop(struct task_group *tg, void *data);
 178
 179 extern void free_fair_sched_group(struct task_group *tg);
 180 extern int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent);
 181 extern void unregister_fair_sched_group(struct task_group *tg, int cpu);
 182 extern void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
 183                         struct sched_entity *se, int cpu,
 184                         struct sched_entity *parent);
 185 extern void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
 186 extern int sched_group_set_shares(struct task_group *tg, unsigned long shares);
 187
 188 extern void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b);
 189 extern void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b);
 190 extern void unthrottle_cfs_rq(struct cfs_rq *cfs_rq);
 191
 192 extern void free_rt_sched_group(struct task_group *tg);
 193 extern int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent);
 194 extern void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
 195                 struct sched_rt_entity *rt_se, int cpu,
 196                 struct sched_rt_entity *parent);
 197
 198 #else /* CONFIG_CGROUP_SCHED */
 199
 200 struct cfs_bandwidth { };
 201
 202 #endif  /* CONFIG_CGROUP_SCHED */
 203
 204 /* CFS-related fields in a runqueue */
 205 struct cfs_rq {
 206         struct load_weight load;
 207         unsigned int nr_running, h_nr_running;
 208
 209         u64 exec_clock;
 210         u64 min_vruntime;
 211 #ifndef CONFIG_64BIT
 212         u64 min_vruntime_copy;
 213 #endif
 214
 215         struct rb_root tasks_timeline;
 216         struct rb_node *rb_leftmost;
 217
 218         /*
 219          * 'curr' points to currently running entity on this cfs_rq.
 220          * It is set to NULL otherwise (i.e when none are currently running).
 221          */
 222         struct sched_entity *curr, *next, *last, *skip;
 223
 224 #ifdef  CONFIG_SCHED_DEBUG
 225         unsigned int nr_spread_over;
 226 #endif
 227
 228 #ifdef CONFIG_SMP
 229 /*
 230  * Load-tracking only depends on SMP, FAIR_GROUP_SCHED dependency below may be
 231  * removed when useful for applications beyond shares distribution (e.g.
 232  * load-balance).
 233  */
 234 #ifdef CONFIG_FAIR_GROUP_SCHED
 235         /*
 236          * CFS Load tracking
 237          * Under CFS, load is tracked on a per-entity basis and aggregated up.
 238          * This allows for the description of both thread and group usage (in
 239          * the FAIR_GROUP_SCHED case).
 240          */
 241         u64 runnable_load_avg, blocked_load_avg;
 242         atomic64_t decay_counter, removed_load;
 243         u64 last_decay;
 244 #endif /* CONFIG_FAIR_GROUP_SCHED */
 245 /* These always depend on CONFIG_FAIR_GROUP_SCHED */
 246 #ifdef CONFIG_FAIR_GROUP_SCHED
 247         u32 tg_runnable_contrib;
 248         u64 tg_load_contrib;
 249 #endif /* CONFIG_FAIR_GROUP_SCHED */
 250
 251         /*
 252          *   h_load = weight * f(tg)
 253          *
 254          * Where f(tg) is the recursive weight fraction assigned to
 255          * this group.
 256          */
 257         unsigned long h_load;
 258 #endif /* CONFIG_SMP */
 259
 260 #ifdef CONFIG_FAIR_GROUP_SCHED
 261         struct rq *rq;  /* cpu runqueue to which this cfs_rq is attached */
 262
 263         /*
 264          * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
 265          * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
 266          * (like users, containers etc.)
 267          *
 268          * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
 269          * list is used during load balance.
 270          */
 271         int on_list;
 272         struct list_head leaf_cfs_rq_list;
 273         struct task_group *tg;  /* group that "owns" this runqueue */
 274
 275 #ifdef CONFIG_CFS_BANDWIDTH
 276         int runtime_enabled;
 277         u64 runtime_expires;
 278         s64 runtime_remaining;
 279
 280         u64 throttled_clock, throttled_clock_task;
 281         u64 throttled_clock_task_time;
 282         int throttled, throttle_count;
 283         struct list_head throttled_list;
 284 #endif /* CONFIG_CFS_BANDWIDTH */
 285 #endif /* CONFIG_FAIR_GROUP_SCHED */
 286 };
 287
 288 static inline int rt_bandwidth_enabled(void)
 289 {
 290         return sysctl_sched_rt_runtime >= 0;
 291 }
 292
 293 /* Real-Time classes' related field in a runqueue: */
 294 struct rt_rq {
 295         struct rt_prio_array active;
 296         unsigned int rt_nr_running;
 297 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
 298         struct {
 299                 int curr; /* highest queued rt task prio */
 300 #ifdef CONFIG_SMP
 301                 int next; /* next highest */
 302 #endif
 303         } highest_prio;
 304 #endif
 305 #ifdef CONFIG_SMP
 306         unsigned long rt_nr_migratory;
 307         unsigned long rt_nr_total;
 308         int overloaded;
 309         struct plist_head pushable_tasks;
 310 #endif
 311         int rt_throttled;
 312         u64 rt_time;
 313         u64 rt_runtime;
 314         /* Nests inside the rq lock: */
 315         raw_spinlock_t rt_runtime_lock;
 316
 317 #ifdef CONFIG_RT_GROUP_SCHED
 318         unsigned long rt_nr_boosted;
 319
 320         struct rq *rq;
 321         struct list_head leaf_rt_rq_list;
 322         struct task_group *tg;
 323 #endif
 324 };
 325
 326 #ifdef CONFIG_SMP
 327
 328 /*
 329  * We add the notion of a root-domain which will be used to define per-domain
 330  * variables. Each exclusive cpuset essentially defines an island domain by
 331  * fully partitioning the member cpus from any other cpuset. Whenever a new
 332  * exclusive cpuset is created, we also create and attach a new root-domain
 333  * object.
 334  *
 335  */
 336 struct root_domain {
 337         atomic_t refcount;
 338         atomic_t rto_count;
 339         struct rcu_head rcu;
 340         cpumask_var_t span;
 341         cpumask_var_t online;
 342
 343         /*
 344          * The "RT overload" flag: it gets set if a CPU has more than
 345          * one runnable RT task.
 346          */
 347         cpumask_var_t rto_mask;
 348         struct cpupri cpupri;
 349 };
 350
 351 extern struct root_domain def_root_domain;
 352
 353 #endif /* CONFIG_SMP */
 354
 355 /*
 356  * This is the main, per-CPU runqueue data structure.
 357  *
 358  * Locking rule: those places that want to lock multiple runqueues
 359  * (such as the load balancing or the thread migration code), lock
 360  * acquire operations must be ordered by ascending &runqueue.
 361  */
 362 struct rq {
 363         /* runqueue lock: */
 364         raw_spinlock_t lock;
 365
 366         /*
 367          * nr_running and cpu_load should be in the same cacheline because
 368          * remote CPUs use both these fields when doing load calculation.
 369          */
 370         unsigned int nr_running;
 371         #define CPU_LOAD_IDX_MAX 5
 372         unsigned long cpu_load[CPU_LOAD_IDX_MAX];
 373         unsigned long last_load_update_tick;
 374 #ifdef CONFIG_NO_HZ
 375         u64 nohz_stamp;
 376         unsigned long nohz_flags;
 377 #endif
 378         int skip_clock_update;
 379
 380         /* capture load from *all* tasks on this cpu: */
 381         struct load_weight load;
 382         unsigned long nr_load_updates;
 383         u64 nr_switches;
 384
 385         struct cfs_rq cfs;
 386         struct rt_rq rt;
 387
 388 #ifdef CONFIG_FAIR_GROUP_SCHED
 389         /* list of leaf cfs_rq on this cpu: */
 390         struct list_head leaf_cfs_rq_list;
 391 #ifdef CONFIG_SMP
 392         unsigned long h_load_throttle;
 393 #endif /* CONFIG_SMP */
 394 #endif /* CONFIG_FAIR_GROUP_SCHED */
 395
 396 #ifdef CONFIG_RT_GROUP_SCHED
 397         struct list_head leaf_rt_rq_list;
 398 #endif
 399
 400         /*
 401          * This is part of a global counter where only the total sum
 402          * over all CPUs matters. A task can increase this counter on
 403          * one CPU and if it got migrated afterwards it may decrease
 404          * it on another CPU. Always updated under the runqueue lock:
 405          */
 406         unsigned long nr_uninterruptible;
 407
 408         struct task_struct *curr, *idle, *stop;
 409         unsigned long next_balance;
 410         struct mm_struct *prev_mm;
 411
 412         u64 clock;
 413         u64 clock_task;
 414
 415         atomic_t nr_iowait;
 416
 417 #ifdef CONFIG_SMP
 418         struct root_domain *rd;
 419         struct sched_domain *sd;
 420
 421         unsigned long cpu_power;
 422
 423         unsigned char idle_balance;
 424         /* For active balancing */
 425         int post_schedule;
 426         int active_balance;
 427         int push_cpu;
 428         struct cpu_stop_work active_balance_work;
 429         /* cpu of this runqueue: */
 430         int cpu;
 431         int online;
 432
 433         struct list_head cfs_tasks;
 434
 435         u64 rt_avg;
 436         u64 age_stamp;
 437         u64 idle_stamp;
 438         u64 avg_idle;
 439 #endif
 440
 441 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
 442         u64 prev_irq_time;
 443 #endif
 444 #ifdef CONFIG_PARAVIRT
 445         u64 prev_steal_time;
 446 #endif
 447 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
 448         u64 prev_steal_time_rq;
 449 #endif
 450
 451         /* calc_load related fields */
 452         unsigned long calc_load_update;
 453         long calc_load_active;
 454
 455 #ifdef CONFIG_SCHED_HRTICK
 456 #ifdef CONFIG_SMP
 457         int hrtick_csd_pending;
 458         struct call_single_data hrtick_csd;
 459 #endif
 460         struct hrtimer hrtick_timer;
 461 #endif
 462
 463 #ifdef CONFIG_SCHEDSTATS
 464         /* latency stats */
 465         struct sched_info rq_sched_info;
 466         unsigned long long rq_cpu_time;
 467         /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
 468
 469         /* sys_sched_yield() stats */
 470         unsigned int yld_count;
 471
 472         /* schedule() stats */
 473         unsigned int sched_count;
 474         unsigned int sched_goidle;
 475
 476         /* try_to_wake_up() stats */
 477         unsigned int ttwu_count;
 478         unsigned int ttwu_local;
 479 #endif
 480
 481 #ifdef CONFIG_SMP
 482         struct llist_head wake_list;
 483 #endif
 484
 485         struct sched_avg avg;
 486 };
 487
 488 static inline int cpu_of(struct rq *rq)
 489 {
 490 #ifdef CONFIG_SMP
 491         return rq->cpu;
 492 #else
 493         return 0;
 494 #endif
 495 }
 496
 497 DECLARE_PER_CPU(struct rq, runqueues);
 498
 499 #define cpu_rq(cpu)             (&per_cpu(runqueues, (cpu)))
 500 #define this_rq()               (&__get_cpu_var(runqueues))
 501 #define task_rq(p)              cpu_rq(task_cpu(p))
 502 #define cpu_curr(cpu)           (cpu_rq(cpu)->curr)
 503 #define raw_rq()                (&__raw_get_cpu_var(runqueues))
 504
 505 #ifdef CONFIG_SMP
 506
 507 #define rcu_dereference_check_sched_domain(p) \
 508         rcu_dereference_check((p), \
 509                               lockdep_is_held(&sched_domains_mutex))
 510
 511 /*
 512  * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
 513  * See detach_destroy_domains: synchronize_sched for details.
 514  *
 515  * The domain tree of any CPU may only be accessed from within
 516  * preempt-disabled sections.
 517  */
 518 #define for_each_domain(cpu, __sd) \
 519         for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
 520                         __sd; __sd = __sd->parent)
 521
 522 #define for_each_lower_domain(sd) for (; sd; sd = sd->child)
 523
 524 /**
 525  * highest_flag_domain - Return highest sched_domain containing flag.
 526  * @cpu:        The cpu whose highest level of sched domain is to
 527  *              be returned.
 528  * @flag:       The flag to check for the highest sched_domain
 529  *              for the given cpu.
 530  *
 531  * Returns the highest sched_domain of a cpu which contains the given flag.
 532  */
 533 static inline struct sched_domain *highest_flag_domain(int cpu, int flag)
 534 {
 535         struct sched_domain *sd, *hsd = NULL;
 536
 537         for_each_domain(cpu, sd) {
 538                 if (!(sd->flags & flag))
 539                         break;
 540                 hsd = sd;
 541         }
 542
 543         return hsd;
 544 }
 545
 546 DECLARE_PER_CPU(struct sched_domain *, sd_llc);
 547 DECLARE_PER_CPU(int, sd_llc_id);
 548
 549 extern int group_balance_cpu(struct sched_group *sg);
 550
 551 #endif /* CONFIG_SMP */
 552
 553 #include "stats.h"
 554 #include "auto_group.h"
 555
 556 #ifdef CONFIG_CGROUP_SCHED
 557
 558 /*
 559  * Return the group to which this tasks belongs.
 560  *
 561  * We cannot use task_subsys_state() and friends because the cgroup
 562  * subsystem changes that value before the cgroup_subsys::attach() method
 563  * is called, therefore we cannot pin it and might observe the wrong value.
 564  *
 565  * The same is true for autogroup's p->signal->autogroup->tg, the autogroup
 566  * core changes this before calling sched_move_task().
 567  *
 568  * Instead we use a 'copy' which is updated from sched_move_task() while
 569  * holding both task_struct::pi_lock and rq::lock.
 570  */
 571 static inline struct task_group *task_group(struct task_struct *p)
 572 {
 573         return p->sched_task_group;
 574 }
 575
 576 /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
 577 static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
 578 {
 579 #if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED)
 580         struct task_group *tg = task_group(p);
 581 #endif
 582
 583 #ifdef CONFIG_FAIR_GROUP_SCHED
 584         p->se.cfs_rq = tg->cfs_rq[cpu];
 585         p->se.parent = tg->se[cpu];
 586 #endif
 587
 588 #ifdef CONFIG_RT_GROUP_SCHED
 589         p->rt.rt_rq  = tg->rt_rq[cpu];
 590         p->rt.parent = tg->rt_se[cpu];
 591 #endif
 592 }
 593
 594 #else /* CONFIG_CGROUP_SCHED */
 595
 596 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
 597 static inline struct task_group *task_group(struct task_struct *p)
 598 {
 599         return NULL;
 600 }
 601
 602 #endif /* CONFIG_CGROUP_SCHED */
 603
 604 static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
 605 {
 606         set_task_rq(p, cpu);
 607 #ifdef CONFIG_SMP
 608         /*
 609          * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
 610          * successfuly executed on another CPU. We must ensure that updates of
 611          * per-task data have been completed by this moment.
 612          */
 613         smp_wmb();
 614         task_thread_info(p)->cpu = cpu;
 615 #endif
 616 }
 617
 618 /*
 619  * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
 620  */
 621 #ifdef CONFIG_SCHED_DEBUG
 622 # include <linux/static_key.h>
 623 # define const_debug __read_mostly
 624 #else
 625 # define const_debug const
 626 #endif
 627
 628 extern const_debug unsigned int sysctl_sched_features;
 629
 630 #define SCHED_FEAT(name, enabled)       \
 631         __SCHED_FEAT_##name ,
 632
 633 enum {
 634 #include "features.h"
 635         __SCHED_FEAT_NR,
 636 };
 637
 638 #undef SCHED_FEAT
 639
 640 #if defined(CONFIG_SCHED_DEBUG) && defined(HAVE_JUMP_LABEL)
 641 static __always_inline bool static_branch__true(struct static_key *key)
 642 {
 643         return static_key_true(key); /* Not out of line branch. */
 644 }
 645
 646 static __always_inline bool static_branch__false(struct static_key *key)
 647 {
 648         return static_key_false(key); /* Out of line branch. */
 649 }
 650
 651 #define SCHED_FEAT(name, enabled)                                       \
 652 static __always_inline bool static_branch_##name(struct static_key *key) \
 653 {                                                                       \
 654         return static_branch__##enabled(key);                           \
 655 }
 656
 657 #include "features.h"
 658
 659 #undef SCHED_FEAT
 660
 661 extern struct static_key sched_feat_keys[__SCHED_FEAT_NR];
 662 #define sched_feat(x) (static_branch_##x(&sched_feat_keys[__SCHED_FEAT_##x]))
 663 #else /* !(SCHED_DEBUG && HAVE_JUMP_LABEL) */
 664 #define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
 665 #endif /* SCHED_DEBUG && HAVE_JUMP_LABEL */
 666
 667 #ifdef CONFIG_NUMA_BALANCING
 668 #define sched_feat_numa(x) sched_feat(x)
 669 #ifdef CONFIG_SCHED_DEBUG
 670 #define numabalancing_enabled sched_feat_numa(NUMA)
 671 #else
 672 extern bool numabalancing_enabled;
 673 #endif /* CONFIG_SCHED_DEBUG */
 674 #else
 675 #define sched_feat_numa(x) (0)
 676 #define numabalancing_enabled (0)
 677 #endif /* CONFIG_NUMA_BALANCING */
 678
 679 static inline u64 global_rt_period(void)
 680 {
 681         return (u64)sysctl_sched_rt_period * NSEC_PER_USEC;
 682 }
 683
 684 static inline u64 global_rt_runtime(void)
 685 {
 686         if (sysctl_sched_rt_runtime < 0)
 687                 return RUNTIME_INF;
 688
 689         return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
 690 }
 691
 692
 693
 694 static inline int task_current(struct rq *rq, struct task_struct *p)
 695 {
 696         return rq->curr == p;
 697 }
 698
 699 static inline int task_running(struct rq *rq, struct task_struct *p)
 700 {
 701 #ifdef CONFIG_SMP
 702         return p->on_cpu;
 703 #else
 704         return task_current(rq, p);
 705 #endif
 706 }
 707
 708
 709 #ifndef prepare_arch_switch
 710 # define prepare_arch_switch(next)      do { } while (0)
 711 #endif
 712 #ifndef finish_arch_switch
 713 # define finish_arch_switch(prev)       do { } while (0)
 714 #endif
 715 #ifndef finish_arch_post_lock_switch
 716 # define finish_arch_post_lock_switch() do { } while (0)
 717 #endif
 718
 719 #ifndef __ARCH_WANT_UNLOCKED_CTXSW
 720 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 721 {
 722 #ifdef CONFIG_SMP
 723         /*
 724          * We can optimise this out completely for !SMP, because the
 725          * SMP rebalancing from interrupt is the only thing that cares
 726          * here.
 727          */
 728         next->on_cpu = 1;
 729 #endif
 730 }
 731
 732 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 733 {
 734 #ifdef CONFIG_SMP
 735         /*
 736          * After ->on_cpu is cleared, the task can be moved to a different CPU.
 737          * We must ensure this doesn't happen until the switch is completely
 738          * finished.
 739          */
 740         smp_wmb();
 741         prev->on_cpu = 0;
 742 #endif
 743 #ifdef CONFIG_DEBUG_SPINLOCK
 744         /* this is a valid case when another task releases the spinlock */
 745         rq->lock.owner = current;
 746 #endif
 747         /*
 748          * If we are tracking spinlock dependencies then we have to
 749          * fix up the runqueue lock - which gets 'carried over' from
 750          * prev into current:
 751          */
 752         spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);
 753
 754         raw_spin_unlock_irq(&rq->lock);
 755 }
 756
 757 #else /* __ARCH_WANT_UNLOCKED_CTXSW */
 758 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 759 {
 760 #ifdef CONFIG_SMP
 761         /*
 762          * We can optimise this out completely for !SMP, because the
 763          * SMP rebalancing from interrupt is the only thing that cares
 764          * here.
 765          */
 766         next->on_cpu = 1;
 767 #endif
 768         raw_spin_unlock(&rq->lock);
 769 }
 770
 771 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 772 {
 773 #ifdef CONFIG_SMP
 774         /*
 775          * After ->on_cpu is cleared, the task can be moved to a different CPU.
 776          * We must ensure this doesn't happen until the switch is completely
 777          * finished.
 778          */
 779         smp_wmb();
 780         prev->on_cpu = 0;
 781 #endif
 782         local_irq_enable();
 783 }
 784 #endif /* __ARCH_WANT_UNLOCKED_CTXSW */
 785
 786
 787 static inline void update_load_add(struct load_weight *lw, unsigned long inc)
 788 {
 789         lw->weight += inc;
 790         lw->inv_weight = 0;
 791 }
 792
 793 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
 794 {
 795         lw->weight -= dec;
 796         lw->inv_weight = 0;
 797 }
 798
 799 static inline void update_load_set(struct load_weight *lw, unsigned long w)
 800 {
 801         lw->weight = w;
 802         lw->inv_weight = 0;
 803 }
 804
 805 /*
 806  * To aid in avoiding the subversion of "niceness" due to uneven distribution
 807  * of tasks with abnormal "nice" values across CPUs the contribution that
 808  * each task makes to its run queue's load is weighted according to its
 809  * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
 810  * scaled version of the new time slice allocation that they receive on time
 811  * slice expiry etc.
 812  */
 813
 814 #define WEIGHT_IDLEPRIO                3
 815 #define WMULT_IDLEPRIO         1431655765
 816
 817 /*
 818  * Nice levels are multiplicative, with a gentle 10% change for every
 819  * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 820  * nice 1, it will get ~10% less CPU time than another CPU-bound task
 821  * that remained on nice 0.
 822  *
 823  * The "10% effect" is relative and cumulative: from _any_ nice level,
 824  * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 825  * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 826  * If a task goes up by ~10% and another task goes down by ~10% then
 827  * the relative distance between them is ~25%.)
 828  */
 829 static const int prio_to_weight[40] = {
 830  /* -20 */     88761,     71755,     56483,     46273,     36291,
 831  /* -15 */     29154,     23254,     18705,     14949,     11916,
 832  /* -10 */      9548,      7620,      6100,      4904,      3906,
 833  /*  -5 */      3121,      2501,      1991,      1586,      1277,
 834  /*   0 */      1024,       820,       655,       526,       423,
 835  /*   5 */       335,       272,       215,       172,       137,
 836  /*  10 */       110,        87,        70,        56,        45,
 837  /*  15 */        36,        29,        23,        18,        15,
 838 };
 839
 840 /*
 841  * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated.
 842  *
 843  * In cases where the weight does not change often, we can use the
 844  * precalculated inverse to speed up arithmetics by turning divisions
 845  * into multiplications:
 846  */
 847 static const u32 prio_to_wmult[40] = {
 848  /* -20 */     48388,     59856,     76040,     92818,    118348,
 849  /* -15 */    147320,    184698,    229616,    287308,    360437,
 850  /* -10 */    449829,    563644,    704093,    875809,   1099582,
 851  /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 852  /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 853  /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 854  /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 855  /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
 856 };
 857
 858 /* Time spent by the tasks of the cpu accounting group executing in ... */
 859 enum cpuacct_stat_index {
 860         CPUACCT_STAT_USER,      /* ... user mode */
 861         CPUACCT_STAT_SYSTEM,    /* ... kernel mode */
 862
 863         CPUACCT_STAT_NSTATS,
 864 };
 865
 866
 867 #define sched_class_highest (&stop_sched_class)
 868 #define for_each_class(class) \
 869    for (class = sched_class_highest; class; class = class->next)
 870
 871 extern const struct sched_class stop_sched_class;
 872 extern const struct sched_class rt_sched_class;
 873 extern const struct sched_class fair_sched_class;
 874 extern const struct sched_class idle_sched_class;
 875
 876
 877 #ifdef CONFIG_SMP
 878
 879 extern void trigger_load_balance(struct rq *rq, int cpu);
 880 extern void idle_balance(int this_cpu, struct rq *this_rq);
 881
 882 #else   /* CONFIG_SMP */
 883
 884 static inline void idle_balance(int cpu, struct rq *rq)
 885 {
 886 }
 887
 888 #endif
 889
 890 extern void sysrq_sched_debug_show(void);
 891 extern void sched_init_granularity(void);
 892 extern void update_max_interval(void);
 893 extern void update_group_power(struct sched_domain *sd, int cpu);
 894 extern int update_runtime(struct notifier_block *nfb, unsigned long action, void *hcpu);
 895 extern void init_sched_rt_class(void);
 896 extern void init_sched_fair_class(void);
 897
 898 extern void resched_task(struct task_struct *p);
 899 extern void resched_cpu(int cpu);
 900
 901 extern struct rt_bandwidth def_rt_bandwidth;
 902 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
 903
 904 extern void update_idle_cpu_load(struct rq *this_rq);
 905
 906 #ifdef CONFIG_CGROUP_CPUACCT
 907 #include <linux/cgroup.h>
 908 /* track cpu usage of a group of tasks and its child groups */
 909 struct cpuacct {
 910         struct cgroup_subsys_state css;
 911         /* cpuusage holds pointer to a u64-type object on every cpu */
 912         u64 __percpu *cpuusage;
 913         struct kernel_cpustat __percpu *cpustat;
 914 };
 915
 916 extern struct cgroup_subsys cpuacct_subsys;
 917 extern struct cpuacct root_cpuacct;
 918
 919 /* return cpu accounting group corresponding to this container */
 920 static inline struct cpuacct *cgroup_ca(struct cgroup *cgrp)
 921 {
 922         return container_of(cgroup_subsys_state(cgrp, cpuacct_subsys_id),
 923                             struct cpuacct, css);
 924 }
 925
 926 /* return cpu accounting group to which this task belongs */
 927 static inline struct cpuacct *task_ca(struct task_struct *tsk)
 928 {
 929         return container_of(task_subsys_state(tsk, cpuacct_subsys_id),
 930                             struct cpuacct, css);
 931 }
 932
 933 static inline struct cpuacct *parent_ca(struct cpuacct *ca)
 934 {
 935         if (!ca || !ca->css.cgroup->parent)
 936                 return NULL;
 937         return cgroup_ca(ca->css.cgroup->parent);
 938 }
 939
 940 extern void cpuacct_charge(struct task_struct *tsk, u64 cputime);
 941 #else
 942 static inline void cpuacct_charge(struct task_struct *tsk, u64 cputime) {}
 943 #endif
 944
 945 #ifdef CONFIG_PARAVIRT
 946 static inline u64 steal_ticks(u64 steal)
 947 {
 948         if (unlikely(steal > NSEC_PER_SEC))
 949                 return div_u64(steal, TICK_NSEC);
 950
 951         return __iter_div_u64_rem(steal, TICK_NSEC, &steal);
 952 }
 953 #endif
 954
 955 static inline void inc_nr_running(struct rq *rq)
 956 {
 957         rq->nr_running++;
 958 }
 959
 960 static inline void dec_nr_running(struct rq *rq)
 961 {
 962         rq->nr_running--;
 963 }
 964
 965 extern void update_rq_clock(struct rq *rq);
 966
 967 extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
 968 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
 969
 970 extern void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags);
 971
 972 extern const_debug unsigned int sysctl_sched_time_avg;
 973 extern const_debug unsigned int sysctl_sched_nr_migrate;
 974 extern const_debug unsigned int sysctl_sched_migration_cost;
 975
 976 static inline u64 sched_avg_period(void)
 977 {
 978         return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2;
 979 }
 980
 981 #ifdef CONFIG_SCHED_HRTICK
 982
 983 /*
 984  * Use hrtick when:
 985  *  - enabled by features
 986  *  - hrtimer is actually high res
 987  */
 988 static inline int hrtick_enabled(struct rq *rq)
 989 {
 990         if (!sched_feat(HRTICK))
 991                 return 0;
 992         if (!cpu_active(cpu_of(rq)))
 993                 return 0;
 994         return hrtimer_is_hres_active(&rq->hrtick_timer);
 995 }
 996
 997 void hrtick_start(struct rq *rq, u64 delay);
 998
 999 #else
1000
1001 static inline int hrtick_enabled(struct rq *rq)
1002 {
1003         return 0;
1004 }
1005
1006 #endif /* CONFIG_SCHED_HRTICK */
1007
1008 #ifdef CONFIG_SMP
1009 extern void sched_avg_update(struct rq *rq);
1010 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
1011 {
1012         rq->rt_avg += rt_delta;
1013         sched_avg_update(rq);
1014 }
1015 #else
1016 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { }
1017 static inline void sched_avg_update(struct rq *rq) { }
1018 #endif
1019
1020 extern void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period);
1021
1022 #ifdef CONFIG_SMP
1023 #ifdef CONFIG_PREEMPT
1024
1025 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2);
1026
1027 /*
1028  * fair double_lock_balance: Safely acquires both rq->locks in a fair
1029  * way at the expense of forcing extra atomic operations in all
1030  * invocations.  This assures that the double_lock is acquired using the
1031  * same underlying policy as the spinlock_t on this architecture, which
1032  * reduces latency compared to the unfair variant below.  However, it
1033  * also adds more overhead and therefore may reduce throughput.
1034  */
1035 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
1036         __releases(this_rq->lock)
1037         __acquires(busiest->lock)
1038         __acquires(this_rq->lock)
1039 {
1040         raw_spin_unlock(&this_rq->lock);
1041         double_rq_lock(this_rq, busiest);
1042
1043         return 1;
1044 }
1045
1046 #else
1047 /*
1048  * Unfair double_lock_balance: Optimizes throughput at the expense of
1049  * latency by eliminating extra atomic operations when the locks are
1050  * already in proper order on entry.  This favors lower cpu-ids and will
1051  * grant the double lock to lower cpus over higher ids under contention,
1052  * regardless of entry order into the function.
1053  */
1054 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
1055         __releases(this_rq->lock)
1056         __acquires(busiest->lock)
1057         __acquires(this_rq->lock)
1058 {
1059         int ret = 0;
1060
1061         if (unlikely(!raw_spin_trylock(&busiest->lock))) {
1062                 if (busiest < this_rq) {
1063                         raw_spin_unlock(&this_rq->lock);
1064                         raw_spin_lock(&busiest->lock);
1065                         raw_spin_lock_nested(&this_rq->lock,
1066                                               SINGLE_DEPTH_NESTING);
1067                         ret = 1;
1068                 } else
1069                         raw_spin_lock_nested(&busiest->lock,
1070                                               SINGLE_DEPTH_NESTING);
1071         }
1072         return ret;
1073 }
1074
1075 #endif /* CONFIG_PREEMPT */
1076
1077 /*
1078  * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
1079  */
1080 static inline int double_lock_balance(struct rq *this_rq, struct rq *busiest)
1081 {
1082         if (unlikely(!irqs_disabled())) {
1083                 /* printk() doesn't work good under rq->lock */
1084                 raw_spin_unlock(&this_rq->lock);
1085                 BUG_ON(1);
1086         }
1087
1088         return _double_lock_balance(this_rq, busiest);
1089 }
1090
1091 static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
1092         __releases(busiest->lock)
1093 {
1094         raw_spin_unlock(&busiest->lock);
1095         lock_set_subclass(&this_rq->lock.dep_map, 0, _RET_IP_);
1096 }
1097
1098 /*
1099  * double_rq_lock - safely lock two runqueues
1100  *
1101  * Note this does not disable interrupts like task_rq_lock,
1102  * you need to do so manually before calling.
1103  */
1104 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
1105         __acquires(rq1->lock)
1106         __acquires(rq2->lock)
1107 {
1108         BUG_ON(!irqs_disabled());
1109         if (rq1 == rq2) {
1110                 raw_spin_lock(&rq1->lock);
1111                 __acquire(rq2->lock);   /* Fake it out ;) */
1112         } else {
1113                 if (rq1 < rq2) {
1114                         raw_spin_lock(&rq1->lock);
1115                         raw_spin_lock_nested(&rq2->lock, SINGLE_DEPTH_NESTING);
1116                 } else {
1117                         raw_spin_lock(&rq2->lock);
1118                         raw_spin_lock_nested(&rq1->lock, SINGLE_DEPTH_NESTING);
1119                 }
1120         }
1121 }
1122
1123 /*
1124  * double_rq_unlock - safely unlock two runqueues
1125  *
1126  * Note this does not restore interrupts like task_rq_unlock,
1127  * you need to do so manually after calling.
1128  */
1129 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
1130         __releases(rq1->lock)
1131         __releases(rq2->lock)
1132 {
1133         raw_spin_unlock(&rq1->lock);
1134         if (rq1 != rq2)
1135                 raw_spin_unlock(&rq2->lock);
1136         else
1137                 __release(rq2->lock);
1138 }
1139
1140 #else /* CONFIG_SMP */
1141
1142 /*
1143  * double_rq_lock - safely lock two runqueues
1144  *
1145  * Note this does not disable interrupts like task_rq_lock,
1146  * you need to do so manually before calling.
1147  */
1148 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
1149         __acquires(rq1->lock)
1150         __acquires(rq2->lock)
1151 {
1152         BUG_ON(!irqs_disabled());
1153         BUG_ON(rq1 != rq2);
1154         raw_spin_lock(&rq1->lock);
1155         __acquire(rq2->lock);   /* Fake it out ;) */
1156 }
1157
1158 /*
1159  * double_rq_unlock - safely unlock two runqueues
1160  *
1161  * Note this does not restore interrupts like task_rq_unlock,
1162  * you need to do so manually after calling.
1163  */
1164 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
1165         __releases(rq1->lock)
1166         __releases(rq2->lock)
1167 {
1168         BUG_ON(rq1 != rq2);
1169         raw_spin_unlock(&rq1->lock);
1170         __release(rq2->lock);
1171 }
1172
1173 #endif
1174
1175 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq);
1176 extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq);
1177 extern void print_cfs_stats(struct seq_file *m, int cpu);
1178 extern void print_rt_stats(struct seq_file *m, int cpu);
1179
1180 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
1181 extern void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq);
1182
1183 extern void account_cfs_bandwidth_used(int enabled, int was_enabled);
1184
1185 #ifdef CONFIG_NO_HZ
1186 enum rq_nohz_flag_bits {
1187         NOHZ_TICK_STOPPED,
1188         NOHZ_BALANCE_KICK,
1189         NOHZ_IDLE,
1190 };
1191
1192 #define nohz_flags(cpu) (&cpu_rq(cpu)->nohz_flags)
1193 #endif
1194
1195 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
1196
1197 DECLARE_PER_CPU(u64, cpu_hardirq_time);
1198 DECLARE_PER_CPU(u64, cpu_softirq_time);
1199
1200 #ifndef CONFIG_64BIT
1201 DECLARE_PER_CPU(seqcount_t, irq_time_seq);
1202
1203 static inline void irq_time_write_begin(void)
1204 {
1205         __this_cpu_inc(irq_time_seq.sequence);
1206         smp_wmb();
1207 }
1208
1209 static inline void irq_time_write_end(void)
1210 {
1211         smp_wmb();
1212         __this_cpu_inc(irq_time_seq.sequence);
1213 }
1214
1215 static inline u64 irq_time_read(int cpu)
1216 {
1217         u64 irq_time;
1218         unsigned seq;
1219
1220         do {
1221                 seq = read_seqcount_begin(&per_cpu(irq_time_seq, cpu));
1222                 irq_time = per_cpu(cpu_softirq_time, cpu) +
1223                            per_cpu(cpu_hardirq_time, cpu);
1224         } while (read_seqcount_retry(&per_cpu(irq_time_seq, cpu), seq));
1225
1226         return irq_time;
1227 }
1228 #else /* CONFIG_64BIT */
1229 static inline void irq_time_write_begin(void)
1230 {
1231 }
1232
1233 static inline void irq_time_write_end(void)
1234 {
1235 }
1236
1237 static inline u64 irq_time_read(int cpu)
1238 {
1239         return per_cpu(cpu_softirq_time, cpu) + per_cpu(cpu_hardirq_time, cpu);
1240 }
1241 #endif /* CONFIG_64BIT */
1242 #endif /* CONFIG_IRQ_TIME_ACCOUNTING */