kernel/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 "sched_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 char nohz_balance_kick;
 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 cpu_rq(cpu)             (&per_cpu(runqueues, (cpu)))
 505 #define this_rq()               (&__get_cpu_var(runqueues))
 506 #define task_rq(p)              cpu_rq(task_cpu(p))
 507 #define cpu_curr(cpu)           (cpu_rq(cpu)->curr)
 508 #define raw_rq()                (&__raw_get_cpu_var(runqueues))
 509
 510 #include "sched_stats.h"
 511 #include "sched_autogroup.h"
 512
 513 #ifdef CONFIG_CGROUP_SCHED
 514
 515 /*
 516  * Return the group to which this tasks belongs.
 517  *
 518  * We use task_subsys_state_check() and extend the RCU verification with
 519  * pi->lock and rq->lock because cpu_cgroup_attach() holds those locks for each
 520  * task it moves into the cgroup. Therefore by holding either of those locks,
 521  * we pin the task to the current cgroup.
 522  */
 523 static inline struct task_group *task_group(struct task_struct *p)
 524 {
 525         struct task_group *tg;
 526         struct cgroup_subsys_state *css;
 527
 528         css = task_subsys_state_check(p, cpu_cgroup_subsys_id,
 529                         lockdep_is_held(&p->pi_lock) ||
 530                         lockdep_is_held(&task_rq(p)->lock));
 531         tg = container_of(css, struct task_group, css);
 532
 533         return autogroup_task_group(p, tg);
 534 }
 535
 536 /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
 537 static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
 538 {
 539 #if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED)
 540         struct task_group *tg = task_group(p);
 541 #endif
 542
 543 #ifdef CONFIG_FAIR_GROUP_SCHED
 544         p->se.cfs_rq = tg->cfs_rq[cpu];
 545         p->se.parent = tg->se[cpu];
 546 #endif
 547
 548 #ifdef CONFIG_RT_GROUP_SCHED
 549         p->rt.rt_rq  = tg->rt_rq[cpu];
 550         p->rt.parent = tg->rt_se[cpu];
 551 #endif
 552 }
 553
 554 #else /* CONFIG_CGROUP_SCHED */
 555
 556 static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
 557 static inline struct task_group *task_group(struct task_struct *p)
 558 {
 559         return NULL;
 560 }
 561
 562 #endif /* CONFIG_CGROUP_SCHED */
 563
 564 static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
 565 {
 566         set_task_rq(p, cpu);
 567 #ifdef CONFIG_SMP
 568         /*
 569          * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
 570          * successfuly executed on another CPU. We must ensure that updates of
 571          * per-task data have been completed by this moment.
 572          */
 573         smp_wmb();
 574         task_thread_info(p)->cpu = cpu;
 575 #endif
 576 }
 577
 578 /*
 579  * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
 580  */
 581 #ifdef CONFIG_SCHED_DEBUG
 582 # define const_debug __read_mostly
 583 #else
 584 # define const_debug const
 585 #endif
 586
 587 extern const_debug unsigned int sysctl_sched_features;
 588
 589 #define SCHED_FEAT(name, enabled)       \
 590         __SCHED_FEAT_##name ,
 591
 592 enum {
 593 #include "sched_features.h"
 594 };
 595
 596 #undef SCHED_FEAT
 597
 598 #define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
 599
 600 static inline u64 global_rt_period(void)
 601 {
 602         return (u64)sysctl_sched_rt_period * NSEC_PER_USEC;
 603 }
 604
 605 static inline u64 global_rt_runtime(void)
 606 {
 607         if (sysctl_sched_rt_runtime < 0)
 608                 return RUNTIME_INF;
 609
 610         return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
 611 }
 612
 613
 614
 615 static inline int task_current(struct rq *rq, struct task_struct *p)
 616 {
 617         return rq->curr == p;
 618 }
 619
 620 static inline int task_running(struct rq *rq, struct task_struct *p)
 621 {
 622 #ifdef CONFIG_SMP
 623         return p->on_cpu;
 624 #else
 625         return task_current(rq, p);
 626 #endif
 627 }
 628
 629
 630 #ifndef prepare_arch_switch
 631 # define prepare_arch_switch(next)      do { } while (0)
 632 #endif
 633 #ifndef finish_arch_switch
 634 # define finish_arch_switch(prev)       do { } while (0)
 635 #endif
 636
 637 #ifndef __ARCH_WANT_UNLOCKED_CTXSW
 638 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 639 {
 640 #ifdef CONFIG_SMP
 641         /*
 642          * We can optimise this out completely for !SMP, because the
 643          * SMP rebalancing from interrupt is the only thing that cares
 644          * here.
 645          */
 646         next->on_cpu = 1;
 647 #endif
 648 }
 649
 650 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 651 {
 652 #ifdef CONFIG_SMP
 653         /*
 654          * After ->on_cpu is cleared, the task can be moved to a different CPU.
 655          * We must ensure this doesn't happen until the switch is completely
 656          * finished.
 657          */
 658         smp_wmb();
 659         prev->on_cpu = 0;
 660 #endif
 661 #ifdef CONFIG_DEBUG_SPINLOCK
 662         /* this is a valid case when another task releases the spinlock */
 663         rq->lock.owner = current;
 664 #endif
 665         /*
 666          * If we are tracking spinlock dependencies then we have to
 667          * fix up the runqueue lock - which gets 'carried over' from
 668          * prev into current:
 669          */
 670         spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);
 671
 672         raw_spin_unlock_irq(&rq->lock);
 673 }
 674
 675 #else /* __ARCH_WANT_UNLOCKED_CTXSW */
 676 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 677 {
 678 #ifdef CONFIG_SMP
 679         /*
 680          * We can optimise this out completely for !SMP, because the
 681          * SMP rebalancing from interrupt is the only thing that cares
 682          * here.
 683          */
 684         next->on_cpu = 1;
 685 #endif
 686 #ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
 687         raw_spin_unlock_irq(&rq->lock);
 688 #else
 689         raw_spin_unlock(&rq->lock);
 690 #endif
 691 }
 692
 693 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 694 {
 695 #ifdef CONFIG_SMP
 696         /*
 697          * After ->on_cpu is cleared, the task can be moved to a different CPU.
 698          * We must ensure this doesn't happen until the switch is completely
 699          * finished.
 700          */
 701         smp_wmb();
 702         prev->on_cpu = 0;
 703 #endif
 704 #ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW
 705         local_irq_enable();
 706 #endif
 707 }
 708 #endif /* __ARCH_WANT_UNLOCKED_CTXSW */
 709
 710
 711 static inline void update_load_add(struct load_weight *lw, unsigned long inc)
 712 {
 713         lw->weight += inc;
 714         lw->inv_weight = 0;
 715 }
 716
 717 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
 718 {
 719         lw->weight -= dec;
 720         lw->inv_weight = 0;
 721 }
 722
 723 static inline void update_load_set(struct load_weight *lw, unsigned long w)
 724 {
 725         lw->weight = w;
 726         lw->inv_weight = 0;
 727 }
 728
 729 /*
 730  * To aid in avoiding the subversion of "niceness" due to uneven distribution
 731  * of tasks with abnormal "nice" values across CPUs the contribution that
 732  * each task makes to its run queue's load is weighted according to its
 733  * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
 734  * scaled version of the new time slice allocation that they receive on time
 735  * slice expiry etc.
 736  */
 737
 738 #define WEIGHT_IDLEPRIO                3
 739 #define WMULT_IDLEPRIO         1431655765
 740
 741 /*
 742  * Nice levels are multiplicative, with a gentle 10% change for every
 743  * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 744  * nice 1, it will get ~10% less CPU time than another CPU-bound task
 745  * that remained on nice 0.
 746  *
 747  * The "10% effect" is relative and cumulative: from _any_ nice level,
 748  * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 749  * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 750  * If a task goes up by ~10% and another task goes down by ~10% then
 751  * the relative distance between them is ~25%.)
 752  */
 753 static const int prio_to_weight[40] = {
 754  /* -20 */     88761,     71755,     56483,     46273,     36291,
 755  /* -15 */     29154,     23254,     18705,     14949,     11916,
 756  /* -10 */      9548,      7620,      6100,      4904,      3906,
 757  /*  -5 */      3121,      2501,      1991,      1586,      1277,
 758  /*   0 */      1024,       820,       655,       526,       423,
 759  /*   5 */       335,       272,       215,       172,       137,
 760  /*  10 */       110,        87,        70,        56,        45,
 761  /*  15 */        36,        29,        23,        18,        15,
 762 };
 763
 764 /*
 765  * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated.
 766  *
 767  * In cases where the weight does not change often, we can use the
 768  * precalculated inverse to speed up arithmetics by turning divisions
 769  * into multiplications:
 770  */
 771 static const u32 prio_to_wmult[40] = {
 772  /* -20 */     48388,     59856,     76040,     92818,    118348,
 773  /* -15 */    147320,    184698,    229616,    287308,    360437,
 774  /* -10 */    449829,    563644,    704093,    875809,   1099582,
 775  /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 776  /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 777  /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 778  /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 779  /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
 780 };
 781
 782 /* Time spent by the tasks of the cpu accounting group executing in ... */
 783 enum cpuacct_stat_index {
 784         CPUACCT_STAT_USER,      /* ... user mode */
 785         CPUACCT_STAT_SYSTEM,    /* ... kernel mode */
 786
 787         CPUACCT_STAT_NSTATS,
 788 };
 789
 790
 791 #define sched_class_highest (&stop_sched_class)
 792 #define for_each_class(class) \
 793    for (class = sched_class_highest; class; class = class->next)
 794
 795 extern const struct sched_class stop_sched_class;
 796 extern const struct sched_class rt_sched_class;
 797 extern const struct sched_class fair_sched_class;
 798 extern const struct sched_class idle_sched_class;
 799
 800
 801 #ifdef CONFIG_SMP
 802
 803 extern void trigger_load_balance(struct rq *rq, int cpu);
 804 extern void idle_balance(int this_cpu, struct rq *this_rq);
 805
 806 #else   /* CONFIG_SMP */
 807
 808 static inline void idle_balance(int cpu, struct rq *rq)
 809 {
 810 }
 811
 812 #endif
 813
 814 extern void sysrq_sched_debug_show(void);
 815 extern void sched_init_granularity(void);
 816 extern void update_max_interval(void);
 817 extern void update_group_power(struct sched_domain *sd, int cpu);
 818 extern int update_runtime(struct notifier_block *nfb, unsigned long action, void *hcpu);
 819 extern void init_sched_rt_class(void);
 820 extern void init_sched_fair_class(void);
 821
 822 extern void resched_task(struct task_struct *p);
 823 extern void resched_cpu(int cpu);
 824
 825 extern struct rt_bandwidth def_rt_bandwidth;
 826 extern void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime);
 827
 828 extern void update_cpu_load(struct rq *this_rq);
 829
 830 #ifdef CONFIG_CGROUP_CPUACCT
 831 extern void cpuacct_charge(struct task_struct *tsk, u64 cputime);
 832 extern void cpuacct_update_stats(struct task_struct *tsk,
 833                 enum cpuacct_stat_index idx, cputime_t val);
 834 #else
 835 static inline void cpuacct_charge(struct task_struct *tsk, u64 cputime) {}
 836 static inline void cpuacct_update_stats(struct task_struct *tsk,
 837                 enum cpuacct_stat_index idx, cputime_t val) {}
 838 #endif
 839
 840 static inline void inc_nr_running(struct rq *rq)
 841 {
 842         rq->nr_running++;
 843 }
 844
 845 static inline void dec_nr_running(struct rq *rq)
 846 {
 847         rq->nr_running--;
 848 }
 849
 850 extern void update_rq_clock(struct rq *rq);
 851
 852 extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
 853 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
 854
 855 extern void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags);
 856
 857 extern const_debug unsigned int sysctl_sched_time_avg;
 858 extern const_debug unsigned int sysctl_sched_nr_migrate;
 859 extern const_debug unsigned int sysctl_sched_migration_cost;
 860
 861 static inline u64 sched_avg_period(void)
 862 {
 863         return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2;
 864 }
 865
 866 void calc_load_account_idle(struct rq *this_rq);
 867
 868 #ifdef CONFIG_SCHED_HRTICK
 869
 870 /*
 871  * Use hrtick when:
 872  *  - enabled by features
 873  *  - hrtimer is actually high res
 874  */
 875 static inline int hrtick_enabled(struct rq *rq)
 876 {
 877         if (!sched_feat(HRTICK))
 878                 return 0;
 879         if (!cpu_active(cpu_of(rq)))
 880                 return 0;
 881         return hrtimer_is_hres_active(&rq->hrtick_timer);
 882 }
 883
 884 void hrtick_start(struct rq *rq, u64 delay);
 885
 886 #endif /* CONFIG_SCHED_HRTICK */
 887
 888 #ifdef CONFIG_SMP
 889 extern void sched_avg_update(struct rq *rq);
 890 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
 891 {
 892         rq->rt_avg += rt_delta;
 893         sched_avg_update(rq);
 894 }
 895 #else
 896 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta) { }
 897 static inline void sched_avg_update(struct rq *rq) { }
 898 #endif
 899
 900 extern void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period);
 901
 902 #ifdef CONFIG_SMP
 903 #ifdef CONFIG_PREEMPT
 904
 905 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2);
 906
 907 /*
 908  * fair double_lock_balance: Safely acquires both rq->locks in a fair
 909  * way at the expense of forcing extra atomic operations in all
 910  * invocations.  This assures that the double_lock is acquired using the
 911  * same underlying policy as the spinlock_t on this architecture, which
 912  * reduces latency compared to the unfair variant below.  However, it
 913  * also adds more overhead and therefore may reduce throughput.
 914  */
 915 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
 916         __releases(this_rq->lock)
 917         __acquires(busiest->lock)
 918         __acquires(this_rq->lock)
 919 {
 920         raw_spin_unlock(&this_rq->lock);
 921         double_rq_lock(this_rq, busiest);
 922
 923         return 1;
 924 }
 925
 926 #else
 927 /*
 928  * Unfair double_lock_balance: Optimizes throughput at the expense of
 929  * latency by eliminating extra atomic operations when the locks are
 930  * already in proper order on entry.  This favors lower cpu-ids and will
 931  * grant the double lock to lower cpus over higher ids under contention,
 932  * regardless of entry order into the function.
 933  */
 934 static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
 935         __releases(this_rq->lock)
 936         __acquires(busiest->lock)
 937         __acquires(this_rq->lock)
 938 {
 939         int ret = 0;
 940
 941         if (unlikely(!raw_spin_trylock(&busiest->lock))) {
 942                 if (busiest < this_rq) {
 943                         raw_spin_unlock(&this_rq->lock);
 944                         raw_spin_lock(&busiest->lock);
 945                         raw_spin_lock_nested(&this_rq->lock,
 946                                               SINGLE_DEPTH_NESTING);
 947                         ret = 1;
 948                 } else
 949                         raw_spin_lock_nested(&busiest->lock,
 950                                               SINGLE_DEPTH_NESTING);
 951         }
 952         return ret;
 953 }
 954
 955 #endif /* CONFIG_PREEMPT */
 956
 957 /*
 958  * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
 959  */
 960 static inline int double_lock_balance(struct rq *this_rq, struct rq *busiest)
 961 {
 962         if (unlikely(!irqs_disabled())) {
 963                 /* printk() doesn't work good under rq->lock */
 964                 raw_spin_unlock(&this_rq->lock);
 965                 BUG_ON(1);
 966         }
 967
 968         return _double_lock_balance(this_rq, busiest);
 969 }
 970
 971 static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
 972         __releases(busiest->lock)
 973 {
 974         raw_spin_unlock(&busiest->lock);
 975         lock_set_subclass(&this_rq->lock.dep_map, 0, _RET_IP_);
 976 }
 977
 978 /*
 979  * double_rq_lock - safely lock two runqueues
 980  *
 981  * Note this does not disable interrupts like task_rq_lock,
 982  * you need to do so manually before calling.
 983  */
 984 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
 985         __acquires(rq1->lock)
 986         __acquires(rq2->lock)
 987 {
 988         BUG_ON(!irqs_disabled());
 989         if (rq1 == rq2) {
 990                 raw_spin_lock(&rq1->lock);
 991                 __acquire(rq2->lock);   /* Fake it out ;) */
 992         } else {
 993                 if (rq1 < rq2) {
 994                         raw_spin_lock(&rq1->lock);
 995                         raw_spin_lock_nested(&rq2->lock, SINGLE_DEPTH_NESTING);
 996                 } else {
 997                         raw_spin_lock(&rq2->lock);
 998                         raw_spin_lock_nested(&rq1->lock, SINGLE_DEPTH_NESTING);
 999                 }
1000         }
1001 }
1002
1003 /*
1004  * double_rq_unlock - safely unlock two runqueues
1005  *
1006  * Note this does not restore interrupts like task_rq_unlock,
1007  * you need to do so manually after calling.
1008  */
1009 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
1010         __releases(rq1->lock)
1011         __releases(rq2->lock)
1012 {
1013         raw_spin_unlock(&rq1->lock);
1014         if (rq1 != rq2)
1015                 raw_spin_unlock(&rq2->lock);
1016         else
1017                 __release(rq2->lock);
1018 }
1019
1020 #else /* CONFIG_SMP */
1021
1022 /*
1023  * double_rq_lock - safely lock two runqueues
1024  *
1025  * Note this does not disable interrupts like task_rq_lock,
1026  * you need to do so manually before calling.
1027  */
1028 static inline void double_rq_lock(struct rq *rq1, struct rq *rq2)
1029         __acquires(rq1->lock)
1030         __acquires(rq2->lock)
1031 {
1032         BUG_ON(!irqs_disabled());
1033         BUG_ON(rq1 != rq2);
1034         raw_spin_lock(&rq1->lock);
1035         __acquire(rq2->lock);   /* Fake it out ;) */
1036 }
1037
1038 /*
1039  * double_rq_unlock - safely unlock two runqueues
1040  *
1041  * Note this does not restore interrupts like task_rq_unlock,
1042  * you need to do so manually after calling.
1043  */
1044 static inline void double_rq_unlock(struct rq *rq1, struct rq *rq2)
1045         __releases(rq1->lock)
1046         __releases(rq2->lock)
1047 {
1048         BUG_ON(rq1 != rq2);
1049         raw_spin_unlock(&rq1->lock);
1050         __release(rq2->lock);
1051 }
1052
1053 #endif
1054
1055 extern struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq);
1056 extern struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq);
1057 extern void print_cfs_stats(struct seq_file *m, int cpu);
1058 extern void print_rt_stats(struct seq_file *m, int cpu);
1059
1060 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
1061 extern void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq);
1062 extern void unthrottle_offline_cfs_rqs(struct rq *rq);
1063
1064 extern void account_cfs_bandwidth_used(int enabled, int was_enabled);