kernel/sched/sched.h

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