linux/kernel/sched.c
<<
>>
Prefs
   1/*
   2 *  kernel/sched.c
   3 *
   4 *  Kernel scheduler and related syscalls
   5 *
   6 *  Copyright (C) 1991-2002  Linus Torvalds
   7 *
   8 *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and
   9 *              make semaphores SMP safe
  10 *  1998-11-19  Implemented schedule_timeout() and related stuff
  11 *              by Andrea Arcangeli
  12 *  2002-01-04  New ultra-scalable O(1) scheduler by Ingo Molnar:
  13 *              hybrid priority-list and round-robin design with
  14 *              an array-switch method of distributing timeslices
  15 *              and per-CPU runqueues.  Cleanups and useful suggestions
  16 *              by Davide Libenzi, preemptible kernel bits by Robert Love.
  17 *  2003-09-03  Interactivity tuning by Con Kolivas.
  18 *  2004-04-02  Scheduler domains code by Nick Piggin
  19 *  2007-04-15  Work begun on replacing all interactivity tuning with a
  20 *              fair scheduling design by Con Kolivas.
  21 *  2007-05-05  Load balancing (smp-nice) and other improvements
  22 *              by Peter Williams
  23 *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith
  24 *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
  25 *  2007-11-29  RT balancing improvements by Steven Rostedt, Gregory Haskins,
  26 *              Thomas Gleixner, Mike Kravetz
  27 */
  28
  29#include <linux/mm.h>
  30#include <linux/module.h>
  31#include <linux/nmi.h>
  32#include <linux/init.h>
  33#include <linux/uaccess.h>
  34#include <linux/highmem.h>
  35#include <linux/smp_lock.h>
  36#include <asm/mmu_context.h>
  37#include <linux/interrupt.h>
  38#include <linux/capability.h>
  39#include <linux/completion.h>
  40#include <linux/kernel_stat.h>
  41#include <linux/debug_locks.h>
  42#include <linux/perf_event.h>
  43#include <linux/security.h>
  44#include <linux/notifier.h>
  45#include <linux/profile.h>
  46#include <linux/freezer.h>
  47#include <linux/vmalloc.h>
  48#include <linux/blkdev.h>
  49#include <linux/delay.h>
  50#include <linux/pid_namespace.h>
  51#include <linux/smp.h>
  52#include <linux/threads.h>
  53#include <linux/timer.h>
  54#include <linux/rcupdate.h>
  55#include <linux/cpu.h>
  56#include <linux/cpuset.h>
  57#include <linux/percpu.h>
  58#include <linux/proc_fs.h>
  59#include <linux/seq_file.h>
  60#include <linux/stop_machine.h>
  61#include <linux/sysctl.h>
  62#include <linux/syscalls.h>
  63#include <linux/times.h>
  64#include <linux/tsacct_kern.h>
  65#include <linux/kprobes.h>
  66#include <linux/delayacct.h>
  67#include <linux/unistd.h>
  68#include <linux/pagemap.h>
  69#include <linux/hrtimer.h>
  70#include <linux/tick.h>
  71#include <linux/debugfs.h>
  72#include <linux/ctype.h>
  73#include <linux/ftrace.h>
  74#include <linux/slab.h>
  75
  76#include <asm/tlb.h>
  77#include <asm/irq_regs.h>
  78
  79#include "sched_cpupri.h"
  80
  81#define CREATE_TRACE_POINTS
  82#include <trace/events/sched.h>
  83
  84/*
  85 * Convert user-nice values [ -20 ... 0 ... 19 ]
  86 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
  87 * and back.
  88 */
  89#define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
  90#define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
  91#define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)
  92
  93/*
  94 * 'User priority' is the nice value converted to something we
  95 * can work with better when scaling various scheduler parameters,
  96 * it's a [ 0 ... 39 ] range.
  97 */
  98#define USER_PRIO(p)            ((p)-MAX_RT_PRIO)
  99#define TASK_USER_PRIO(p)       USER_PRIO((p)->static_prio)
 100#define MAX_USER_PRIO           (USER_PRIO(MAX_PRIO))
 101
 102/*
 103 * Helpers for converting nanosecond timing to jiffy resolution
 104 */
 105#define NS_TO_JIFFIES(TIME)     ((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))
 106
 107#define NICE_0_LOAD             SCHED_LOAD_SCALE
 108#define NICE_0_SHIFT            SCHED_LOAD_SHIFT
 109
 110/*
 111 * These are the 'tuning knobs' of the scheduler:
 112 *
 113 * default timeslice is 100 msecs (used only for SCHED_RR tasks).
 114 * Timeslices get refilled after they expire.
 115 */
 116#define DEF_TIMESLICE           (100 * HZ / 1000)
 117
 118/*
 119 * single value that denotes runtime == period, ie unlimited time.
 120 */
 121#define RUNTIME_INF     ((u64)~0ULL)
 122
 123static inline int rt_policy(int policy)
 124{
 125        if (unlikely(policy == SCHED_FIFO || policy == SCHED_RR))
 126                return 1;
 127        return 0;
 128}
 129
 130static inline int task_has_rt_policy(struct task_struct *p)
 131{
 132        return rt_policy(p->policy);
 133}
 134
 135/*
 136 * This is the priority-queue data structure of the RT scheduling class:
 137 */
 138struct rt_prio_array {
 139        DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
 140        struct list_head queue[MAX_RT_PRIO];
 141};
 142
 143struct rt_bandwidth {
 144        /* nests inside the rq lock: */
 145        raw_spinlock_t          rt_runtime_lock;
 146        ktime_t                 rt_period;
 147        u64                     rt_runtime;
 148        struct hrtimer          rt_period_timer;
 149};
 150
 151static struct rt_bandwidth def_rt_bandwidth;
 152
 153static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun);
 154
 155static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
 156{
 157        struct rt_bandwidth *rt_b =
 158                container_of(timer, struct rt_bandwidth, rt_period_timer);
 159        ktime_t now;
 160        int overrun;
 161        int idle = 0;
 162
 163        for (;;) {
 164                now = hrtimer_cb_get_time(timer);
 165                overrun = hrtimer_forward(timer, now, rt_b->rt_period);
 166
 167                if (!overrun)
 168                        break;
 169
 170                idle = do_sched_rt_period_timer(rt_b, overrun);
 171        }
 172
 173        return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
 174}
 175
 176static
 177void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
 178{
 179        rt_b->rt_period = ns_to_ktime(period);
 180        rt_b->rt_runtime = runtime;
 181
 182        raw_spin_lock_init(&rt_b->rt_runtime_lock);
 183
 184        hrtimer_init(&rt_b->rt_period_timer,
 185                        CLOCK_MONOTONIC, HRTIMER_MODE_REL);
 186        rt_b->rt_period_timer.function = sched_rt_period_timer;
 187}
 188
 189static inline int rt_bandwidth_enabled(void)
 190{
 191        return sysctl_sched_rt_runtime >= 0;
 192}
 193
 194static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
 195{
 196        ktime_t now;
 197
 198        if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
 199                return;
 200
 201        if (hrtimer_active(&rt_b->rt_period_timer))
 202                return;
 203
 204        raw_spin_lock(&rt_b->rt_runtime_lock);
 205        for (;;) {
 206                unsigned long delta;
 207                ktime_t soft, hard;
 208
 209                if (hrtimer_active(&rt_b->rt_period_timer))
 210                        break;
 211
 212                now = hrtimer_cb_get_time(&rt_b->rt_period_timer);
 213                hrtimer_forward(&rt_b->rt_period_timer, now, rt_b->rt_period);
 214
 215                soft = hrtimer_get_softexpires(&rt_b->rt_period_timer);
 216                hard = hrtimer_get_expires(&rt_b->rt_period_timer);
 217                delta = ktime_to_ns(ktime_sub(hard, soft));
 218                __hrtimer_start_range_ns(&rt_b->rt_period_timer, soft, delta,
 219                                HRTIMER_MODE_ABS_PINNED, 0);
 220        }
 221        raw_spin_unlock(&rt_b->rt_runtime_lock);
 222}
 223
 224#ifdef CONFIG_RT_GROUP_SCHED
 225static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b)
 226{
 227        hrtimer_cancel(&rt_b->rt_period_timer);
 228}
 229#endif
 230
 231/*
 232 * sched_domains_mutex serializes calls to arch_init_sched_domains,
 233 * detach_destroy_domains and partition_sched_domains.
 234 */
 235static DEFINE_MUTEX(sched_domains_mutex);
 236
 237#ifdef CONFIG_CGROUP_SCHED
 238
 239#include <linux/cgroup.h>
 240
 241struct cfs_rq;
 242
 243static LIST_HEAD(task_groups);
 244
 245/* task group related information */
 246struct task_group {
 247        struct cgroup_subsys_state css;
 248
 249#ifdef CONFIG_FAIR_GROUP_SCHED
 250        /* schedulable entities of this group on each cpu */
 251        struct sched_entity **se;
 252        /* runqueue "owned" by this group on each cpu */
 253        struct cfs_rq **cfs_rq;
 254        unsigned long shares;
 255#endif
 256
 257#ifdef CONFIG_RT_GROUP_SCHED
 258        struct sched_rt_entity **rt_se;
 259        struct rt_rq **rt_rq;
 260
 261        struct rt_bandwidth rt_bandwidth;
 262#endif
 263
 264        struct rcu_head rcu;
 265        struct list_head list;
 266
 267        struct task_group *parent;
 268        struct list_head siblings;
 269        struct list_head children;
 270};
 271
 272#define root_task_group init_task_group
 273
 274/* task_group_lock serializes add/remove of task groups and also changes to
 275 * a task group's cpu shares.
 276 */
 277static DEFINE_SPINLOCK(task_group_lock);
 278
 279#ifdef CONFIG_FAIR_GROUP_SCHED
 280
 281#ifdef CONFIG_SMP
 282static int root_task_group_empty(void)
 283{
 284        return list_empty(&root_task_group.children);
 285}
 286#endif
 287
 288# define INIT_TASK_GROUP_LOAD   NICE_0_LOAD
 289
 290/*
 291 * A weight of 0 or 1 can cause arithmetics problems.
 292 * A weight of a cfs_rq is the sum of weights of which entities
 293 * are queued on this cfs_rq, so a weight of a entity should not be
 294 * too large, so as the shares value of a task group.
 295 * (The default weight is 1024 - so there's no practical
 296 *  limitation from this.)
 297 */
 298#define MIN_SHARES      2
 299#define MAX_SHARES      (1UL << 18)
 300
 301static int init_task_group_load = INIT_TASK_GROUP_LOAD;
 302#endif
 303
 304/* Default task group.
 305 *      Every task in system belong to this group at bootup.
 306 */
 307struct task_group init_task_group;
 308
 309#endif  /* CONFIG_CGROUP_SCHED */
 310
 311/* CFS-related fields in a runqueue */
 312struct cfs_rq {
 313        struct load_weight load;
 314        unsigned long nr_running;
 315
 316        u64 exec_clock;
 317        u64 min_vruntime;
 318
 319        struct rb_root tasks_timeline;
 320        struct rb_node *rb_leftmost;
 321
 322        struct list_head tasks;
 323        struct list_head *balance_iterator;
 324
 325        /*
 326         * 'curr' points to currently running entity on this cfs_rq.
 327         * It is set to NULL otherwise (i.e when none are currently running).
 328         */
 329        struct sched_entity *curr, *next, *last;
 330
 331        unsigned int nr_spread_over;
 332
 333#ifdef CONFIG_FAIR_GROUP_SCHED
 334        struct rq *rq;  /* cpu runqueue to which this cfs_rq is attached */
 335
 336        /*
 337         * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
 338         * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
 339         * (like users, containers etc.)
 340         *
 341         * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
 342         * list is used during load balance.
 343         */
 344        struct list_head leaf_cfs_rq_list;
 345        struct task_group *tg;  /* group that "owns" this runqueue */
 346
 347#ifdef CONFIG_SMP
 348        /*
 349         * the part of load.weight contributed by tasks
 350         */
 351        unsigned long task_weight;
 352
 353        /*
 354         *   h_load = weight * f(tg)
 355         *
 356         * Where f(tg) is the recursive weight fraction assigned to
 357         * this group.
 358         */
 359        unsigned long h_load;
 360
 361        /*
 362         * this cpu's part of tg->shares
 363         */
 364        unsigned long shares;
 365
 366        /*
 367         * load.weight at the time we set shares
 368         */
 369        unsigned long rq_weight;
 370#endif
 371#endif
 372};
 373
 374/* Real-Time classes' related field in a runqueue: */
 375struct rt_rq {
 376        struct rt_prio_array active;
 377        unsigned long rt_nr_running;
 378#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
 379        struct {
 380                int curr; /* highest queued rt task prio */
 381#ifdef CONFIG_SMP
 382                int next; /* next highest */
 383#endif
 384        } highest_prio;
 385#endif
 386#ifdef CONFIG_SMP
 387        unsigned long rt_nr_migratory;
 388        unsigned long rt_nr_total;
 389        int overloaded;
 390        struct plist_head pushable_tasks;
 391#endif
 392        int rt_throttled;
 393        u64 rt_time;
 394        u64 rt_runtime;
 395        /* Nests inside the rq lock: */
 396        raw_spinlock_t rt_runtime_lock;
 397
 398#ifdef CONFIG_RT_GROUP_SCHED
 399        unsigned long rt_nr_boosted;
 400
 401        struct rq *rq;
 402        struct list_head leaf_rt_rq_list;
 403        struct task_group *tg;
 404#endif
 405};
 406
 407#ifdef CONFIG_SMP
 408
 409/*
 410 * We add the notion of a root-domain which will be used to define per-domain
 411 * variables. Each exclusive cpuset essentially defines an island domain by
 412 * fully partitioning the member cpus from any other cpuset. Whenever a new
 413 * exclusive cpuset is created, we also create and attach a new root-domain
 414 * object.
 415 *
 416 */
 417struct root_domain {
 418        atomic_t refcount;
 419        cpumask_var_t span;
 420        cpumask_var_t online;
 421
 422        /*
 423         * The "RT overload" flag: it gets set if a CPU has more than
 424         * one runnable RT task.
 425         */
 426        cpumask_var_t rto_mask;
 427        atomic_t rto_count;
 428#ifdef CONFIG_SMP
 429        struct cpupri cpupri;
 430#endif
 431};
 432
 433/*
 434 * By default the system creates a single root-domain with all cpus as
 435 * members (mimicking the global state we have today).
 436 */
 437static struct root_domain def_root_domain;
 438
 439#endif
 440
 441/*
 442 * This is the main, per-CPU runqueue data structure.
 443 *
 444 * Locking rule: those places that want to lock multiple runqueues
 445 * (such as the load balancing or the thread migration code), lock
 446 * acquire operations must be ordered by ascending &runqueue.
 447 */
 448struct rq {
 449        /* runqueue lock: */
 450        raw_spinlock_t lock;
 451
 452        /*
 453         * nr_running and cpu_load should be in the same cacheline because
 454         * remote CPUs use both these fields when doing load calculation.
 455         */
 456        unsigned long nr_running;
 457        #define CPU_LOAD_IDX_MAX 5
 458        unsigned long cpu_load[CPU_LOAD_IDX_MAX];
 459#ifdef CONFIG_NO_HZ
 460        u64 nohz_stamp;
 461        unsigned char in_nohz_recently;
 462#endif
 463        unsigned int skip_clock_update;
 464
 465        /* capture load from *all* tasks on this cpu: */
 466        struct load_weight load;
 467        unsigned long nr_load_updates;
 468        u64 nr_switches;
 469
 470        struct cfs_rq cfs;
 471        struct rt_rq rt;
 472
 473#ifdef CONFIG_FAIR_GROUP_SCHED
 474        /* list of leaf cfs_rq on this cpu: */
 475        struct list_head leaf_cfs_rq_list;
 476#endif
 477#ifdef CONFIG_RT_GROUP_SCHED
 478        struct list_head leaf_rt_rq_list;
 479#endif
 480
 481        /*
 482         * This is part of a global counter where only the total sum
 483         * over all CPUs matters. A task can increase this counter on
 484         * one CPU and if it got migrated afterwards it may decrease
 485         * it on another CPU. Always updated under the runqueue lock:
 486         */
 487        unsigned long nr_uninterruptible;
 488
 489        struct task_struct *curr, *idle;
 490        unsigned long next_balance;
 491        struct mm_struct *prev_mm;
 492
 493        u64 clock;
 494
 495        atomic_t nr_iowait;
 496
 497#ifdef CONFIG_SMP
 498        struct root_domain *rd;
 499        struct sched_domain *sd;
 500
 501        unsigned long cpu_power;
 502
 503        unsigned char idle_at_tick;
 504        /* For active balancing */
 505        int post_schedule;
 506        int active_balance;
 507        int push_cpu;
 508        struct cpu_stop_work active_balance_work;
 509        /* cpu of this runqueue: */
 510        int cpu;
 511        int online;
 512
 513        unsigned long avg_load_per_task;
 514
 515        u64 rt_avg;
 516        u64 age_stamp;
 517        u64 idle_stamp;
 518        u64 avg_idle;
 519#endif
 520
 521        /* calc_load related fields */
 522        unsigned long calc_load_update;
 523        long calc_load_active;
 524
 525#ifdef CONFIG_SCHED_HRTICK
 526#ifdef CONFIG_SMP
 527        int hrtick_csd_pending;
 528        struct call_single_data hrtick_csd;
 529#endif
 530        struct hrtimer hrtick_timer;
 531#endif
 532
 533#ifdef CONFIG_SCHEDSTATS
 534        /* latency stats */
 535        struct sched_info rq_sched_info;
 536        unsigned long long rq_cpu_time;
 537        /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
 538
 539        /* sys_sched_yield() stats */
 540        unsigned int yld_count;
 541
 542        /* schedule() stats */
 543        unsigned int sched_switch;
 544        unsigned int sched_count;
 545        unsigned int sched_goidle;
 546
 547        /* try_to_wake_up() stats */
 548        unsigned int ttwu_count;
 549        unsigned int ttwu_local;
 550
 551        /* BKL stats */
 552        unsigned int bkl_count;
 553#endif
 554};
 555
 556static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
 557
 558static inline
 559void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
 560{
 561        rq->curr->sched_class->check_preempt_curr(rq, p, flags);
 562
 563        /*
 564         * A queue event has occurred, and we're going to schedule.  In
 565         * this case, we can save a useless back to back clock update.
 566         */
 567        if (test_tsk_need_resched(p))
 568                rq->skip_clock_update = 1;
 569}
 570
 571static inline int cpu_of(struct rq *rq)
 572{
 573#ifdef CONFIG_SMP
 574        return rq->cpu;
 575#else
 576        return 0;
 577#endif
 578}
 579
 580#define rcu_dereference_check_sched_domain(p) \
 581        rcu_dereference_check((p), \
 582                              rcu_read_lock_sched_held() || \
 583                              lockdep_is_held(&sched_domains_mutex))
 584
 585/*
 586 * The domain tree (rq->sd) is protected by RCU's quiescent state transition.
 587 * See detach_destroy_domains: synchronize_sched for details.
 588 *
 589 * The domain tree of any CPU may only be accessed from within
 590 * preempt-disabled sections.
 591 */
 592#define for_each_domain(cpu, __sd) \
 593        for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent)
 594
 595#define cpu_rq(cpu)             (&per_cpu(runqueues, (cpu)))
 596#define this_rq()               (&__get_cpu_var(runqueues))
 597#define task_rq(p)              cpu_rq(task_cpu(p))
 598#define cpu_curr(cpu)           (cpu_rq(cpu)->curr)
 599#define raw_rq()                (&__raw_get_cpu_var(runqueues))
 600
 601#ifdef CONFIG_CGROUP_SCHED
 602
 603/*
 604 * Return the group to which this tasks belongs.
 605 *
 606 * We use task_subsys_state_check() and extend the RCU verification
 607 * with lockdep_is_held(&task_rq(p)->lock) because cpu_cgroup_attach()
 608 * holds that lock for each task it moves into the cgroup. Therefore
 609 * by holding that lock, we pin the task to the current cgroup.
 610 */
 611static inline struct task_group *task_group(struct task_struct *p)
 612{
 613        struct cgroup_subsys_state *css;
 614
 615        css = task_subsys_state_check(p, cpu_cgroup_subsys_id,
 616                        lockdep_is_held(&task_rq(p)->lock));
 617        return container_of(css, struct task_group, css);
 618}
 619
 620/* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
 621static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
 622{
 623#ifdef CONFIG_FAIR_GROUP_SCHED
 624        p->se.cfs_rq = task_group(p)->cfs_rq[cpu];
 625        p->se.parent = task_group(p)->se[cpu];
 626#endif
 627
 628#ifdef CONFIG_RT_GROUP_SCHED
 629        p->rt.rt_rq  = task_group(p)->rt_rq[cpu];
 630        p->rt.parent = task_group(p)->rt_se[cpu];
 631#endif
 632}
 633
 634#else /* CONFIG_CGROUP_SCHED */
 635
 636static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
 637static inline struct task_group *task_group(struct task_struct *p)
 638{
 639        return NULL;
 640}
 641
 642#endif /* CONFIG_CGROUP_SCHED */
 643
 644inline void update_rq_clock(struct rq *rq)
 645{
 646        if (!rq->skip_clock_update)
 647                rq->clock = sched_clock_cpu(cpu_of(rq));
 648}
 649
 650/*
 651 * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
 652 */
 653#ifdef CONFIG_SCHED_DEBUG
 654# define const_debug __read_mostly
 655#else
 656# define const_debug static const
 657#endif
 658
 659/**
 660 * runqueue_is_locked
 661 * @cpu: the processor in question.
 662 *
 663 * Returns true if the current cpu runqueue is locked.
 664 * This interface allows printk to be called with the runqueue lock
 665 * held and know whether or not it is OK to wake up the klogd.
 666 */
 667int runqueue_is_locked(int cpu)
 668{
 669        return raw_spin_is_locked(&cpu_rq(cpu)->lock);
 670}
 671
 672/*
 673 * Debugging: various feature bits
 674 */
 675
 676#define SCHED_FEAT(name, enabled)       \
 677        __SCHED_FEAT_##name ,
 678
 679enum {
 680#include "sched_features.h"
 681};
 682
 683#undef SCHED_FEAT
 684
 685#define SCHED_FEAT(name, enabled)       \
 686        (1UL << __SCHED_FEAT_##name) * enabled |
 687
 688const_debug unsigned int sysctl_sched_features =
 689#include "sched_features.h"
 690        0;
 691
 692#undef SCHED_FEAT
 693
 694#ifdef CONFIG_SCHED_DEBUG
 695#define SCHED_FEAT(name, enabled)       \
 696        #name ,
 697
 698static __read_mostly char *sched_feat_names[] = {
 699#include "sched_features.h"
 700        NULL
 701};
 702
 703#undef SCHED_FEAT
 704
 705static int sched_feat_show(struct seq_file *m, void *v)
 706{
 707        int i;
 708
 709        for (i = 0; sched_feat_names[i]; i++) {
 710                if (!(sysctl_sched_features & (1UL << i)))
 711                        seq_puts(m, "NO_");
 712                seq_printf(m, "%s ", sched_feat_names[i]);
 713        }
 714        seq_puts(m, "\n");
 715
 716        return 0;
 717}
 718
 719static ssize_t
 720sched_feat_write(struct file *filp, const char __user *ubuf,
 721                size_t cnt, loff_t *ppos)
 722{
 723        char buf[64];
 724        char *cmp = buf;
 725        int neg = 0;
 726        int i;
 727
 728        if (cnt > 63)
 729                cnt = 63;
 730
 731        if (copy_from_user(&buf, ubuf, cnt))
 732                return -EFAULT;
 733
 734        buf[cnt] = 0;
 735
 736        if (strncmp(buf, "NO_", 3) == 0) {
 737                neg = 1;
 738                cmp += 3;
 739        }
 740
 741        for (i = 0; sched_feat_names[i]; i++) {
 742                int len = strlen(sched_feat_names[i]);
 743
 744                if (strncmp(cmp, sched_feat_names[i], len) == 0) {
 745                        if (neg)
 746                                sysctl_sched_features &= ~(1UL << i);
 747                        else
 748                                sysctl_sched_features |= (1UL << i);
 749                        break;
 750                }
 751        }
 752
 753        if (!sched_feat_names[i])
 754                return -EINVAL;
 755
 756        *ppos += cnt;
 757
 758        return cnt;
 759}
 760
 761static int sched_feat_open(struct inode *inode, struct file *filp)
 762{
 763        return single_open(filp, sched_feat_show, NULL);
 764}
 765
 766static const struct file_operations sched_feat_fops = {
 767        .open           = sched_feat_open,
 768        .write          = sched_feat_write,
 769        .read           = seq_read,
 770        .llseek         = seq_lseek,
 771        .release        = single_release,
 772};
 773
 774static __init int sched_init_debug(void)
 775{
 776        debugfs_create_file("sched_features", 0644, NULL, NULL,
 777                        &sched_feat_fops);
 778
 779        return 0;
 780}
 781late_initcall(sched_init_debug);
 782
 783#endif
 784
 785#define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x))
 786
 787/*
 788 * Number of tasks to iterate in a single balance run.
 789 * Limited because this is done with IRQs disabled.
 790 */
 791const_debug unsigned int sysctl_sched_nr_migrate = 32;
 792
 793/*
 794 * ratelimit for updating the group shares.
 795 * default: 0.25ms
 796 */
 797unsigned int sysctl_sched_shares_ratelimit = 250000;
 798unsigned int normalized_sysctl_sched_shares_ratelimit = 250000;
 799
 800/*
 801 * Inject some fuzzyness into changing the per-cpu group shares
 802 * this avoids remote rq-locks at the expense of fairness.
 803 * default: 4
 804 */
 805unsigned int sysctl_sched_shares_thresh = 4;
 806
 807/*
 808 * period over which we average the RT time consumption, measured
 809 * in ms.
 810 *
 811 * default: 1s
 812 */
 813const_debug unsigned int sysctl_sched_time_avg = MSEC_PER_SEC;
 814
 815/*
 816 * period over which we measure -rt task cpu usage in us.
 817 * default: 1s
 818 */
 819unsigned int sysctl_sched_rt_period = 1000000;
 820
 821static __read_mostly int scheduler_running;
 822
 823/*
 824 * part of the period that we allow rt tasks to run in us.
 825 * default: 0.95s
 826 */
 827int sysctl_sched_rt_runtime = 950000;
 828
 829static inline u64 global_rt_period(void)
 830{
 831        return (u64)sysctl_sched_rt_period * NSEC_PER_USEC;
 832}
 833
 834static inline u64 global_rt_runtime(void)
 835{
 836        if (sysctl_sched_rt_runtime < 0)
 837                return RUNTIME_INF;
 838
 839        return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
 840}
 841
 842#ifndef prepare_arch_switch
 843# define prepare_arch_switch(next)      do { } while (0)
 844#endif
 845#ifndef finish_arch_switch
 846# define finish_arch_switch(prev)       do { } while (0)
 847#endif
 848
 849static inline int task_current(struct rq *rq, struct task_struct *p)
 850{
 851        return rq->curr == p;
 852}
 853
 854#ifndef __ARCH_WANT_UNLOCKED_CTXSW
 855static inline int task_running(struct rq *rq, struct task_struct *p)
 856{
 857        return task_current(rq, p);
 858}
 859
 860static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 861{
 862}
 863
 864static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 865{
 866#ifdef CONFIG_DEBUG_SPINLOCK
 867        /* this is a valid case when another task releases the spinlock */
 868        rq->lock.owner = current;
 869#endif
 870        /*
 871         * If we are tracking spinlock dependencies then we have to
 872         * fix up the runqueue lock - which gets 'carried over' from
 873         * prev into current:
 874         */
 875        spin_acquire(&rq->lock.dep_map, 0, 0, _THIS_IP_);
 876
 877        raw_spin_unlock_irq(&rq->lock);
 878}
 879
 880#else /* __ARCH_WANT_UNLOCKED_CTXSW */
 881static inline int task_running(struct rq *rq, struct task_struct *p)
 882{
 883#ifdef CONFIG_SMP
 884        return p->oncpu;
 885#else
 886        return task_current(rq, p);
 887#endif
 888}
 889
 890static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 891{
 892#ifdef CONFIG_SMP
 893        /*
 894         * We can optimise this out completely for !SMP, because the
 895         * SMP rebalancing from interrupt is the only thing that cares
 896         * here.
 897         */
 898        next->oncpu = 1;
 899#endif
 900#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
 901        raw_spin_unlock_irq(&rq->lock);
 902#else
 903        raw_spin_unlock(&rq->lock);
 904#endif
 905}
 906
 907static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 908{
 909#ifdef CONFIG_SMP
 910        /*
 911         * After ->oncpu is cleared, the task can be moved to a different CPU.
 912         * We must ensure this doesn't happen until the switch is completely
 913         * finished.
 914         */
 915        smp_wmb();
 916        prev->oncpu = 0;
 917#endif
 918#ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW
 919        local_irq_enable();
 920#endif
 921}
 922#endif /* __ARCH_WANT_UNLOCKED_CTXSW */
 923
 924/*
 925 * Check whether the task is waking, we use this to synchronize ->cpus_allowed
 926 * against ttwu().
 927 */
 928static inline int task_is_waking(struct task_struct *p)
 929{
 930        return unlikely(p->state == TASK_WAKING);
 931}
 932
 933/*
 934 * __task_rq_lock - lock the runqueue a given task resides on.
 935 * Must be called interrupts disabled.
 936 */
 937static inline struct rq *__task_rq_lock(struct task_struct *p)
 938        __acquires(rq->lock)
 939{
 940        struct rq *rq;
 941
 942        for (;;) {
 943                rq = task_rq(p);
 944                raw_spin_lock(&rq->lock);
 945                if (likely(rq == task_rq(p)))
 946                        return rq;
 947                raw_spin_unlock(&rq->lock);
 948        }
 949}
 950
 951/*
 952 * task_rq_lock - lock the runqueue a given task resides on and disable
 953 * interrupts. Note the ordering: we can safely lookup the task_rq without
 954 * explicitly disabling preemption.
 955 */
 956static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
 957        __acquires(rq->lock)
 958{
 959        struct rq *rq;
 960
 961        for (;;) {
 962                local_irq_save(*flags);
 963                rq = task_rq(p);
 964                raw_spin_lock(&rq->lock);
 965                if (likely(rq == task_rq(p)))
 966                        return rq;
 967                raw_spin_unlock_irqrestore(&rq->lock, *flags);
 968        }
 969}
 970
 971static void __task_rq_unlock(struct rq *rq)
 972        __releases(rq->lock)
 973{
 974        raw_spin_unlock(&rq->lock);
 975}
 976
 977static inline void task_rq_unlock(struct rq *rq, unsigned long *flags)
 978        __releases(rq->lock)
 979{
 980        raw_spin_unlock_irqrestore(&rq->lock, *flags);
 981}
 982
 983/*
 984 * this_rq_lock - lock this runqueue and disable interrupts.
 985 */
 986static struct rq *this_rq_lock(void)
 987        __acquires(rq->lock)
 988{
 989        struct rq *rq;
 990
 991        local_irq_disable();
 992        rq = this_rq();
 993        raw_spin_lock(&rq->lock);
 994
 995        return rq;
 996}
 997
 998#ifdef CONFIG_SCHED_HRTICK
 999/*
1000 * Use HR-timers to deliver accurate preemption points.
1001 *
1002 * Its all a bit involved since we cannot program an hrt while holding the
1003 * rq->lock. So what we do is store a state in in rq->hrtick_* and ask for a
1004 * reschedule event.
1005 *
1006 * When we get rescheduled we reprogram the hrtick_timer outside of the
1007 * rq->lock.
1008 */
1009
1010/*
1011 * Use hrtick when:
1012 *  - enabled by features
1013 *  - hrtimer is actually high res
1014 */
1015static inline int hrtick_enabled(struct rq *rq)
1016{
1017        if (!sched_feat(HRTICK))
1018                return 0;
1019        if (!cpu_active(cpu_of(rq)))
1020                return 0;
1021        return hrtimer_is_hres_active(&rq->hrtick_timer);
1022}
1023
1024static void hrtick_clear(struct rq *rq)
1025{
1026        if (hrtimer_active(&rq->hrtick_timer))
1027                hrtimer_cancel(&rq->hrtick_timer);
1028}
1029
1030/*
1031 * High-resolution timer tick.
1032 * Runs from hardirq context with interrupts disabled.
1033 */
1034static enum hrtimer_restart hrtick(struct hrtimer *timer)
1035{
1036        struct rq *rq = container_of(timer, struct rq, hrtick_timer);
1037
1038        WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());
1039
1040        raw_spin_lock(&rq->lock);
1041        update_rq_clock(rq);
1042        rq->curr->sched_class->task_tick(rq, rq->curr, 1);
1043        raw_spin_unlock(&rq->lock);
1044
1045        return HRTIMER_NORESTART;
1046}
1047
1048#ifdef CONFIG_SMP
1049/*
1050 * called from hardirq (IPI) context
1051 */
1052static void __hrtick_start(void *arg)
1053{
1054        struct rq *rq = arg;
1055
1056        raw_spin_lock(&rq->lock);
1057        hrtimer_restart(&rq->hrtick_timer);
1058        rq->hrtick_csd_pending = 0;
1059        raw_spin_unlock(&rq->lock);
1060}
1061
1062/*
1063 * Called to set the hrtick timer state.
1064 *
1065 * called with rq->lock held and irqs disabled
1066 */
1067static void hrtick_start(struct rq *rq, u64 delay)
1068{
1069        struct hrtimer *timer = &rq->hrtick_timer;
1070        ktime_t time = ktime_add_ns(timer->base->get_time(), delay);
1071
1072        hrtimer_set_expires(timer, time);
1073
1074        if (rq == this_rq()) {
1075                hrtimer_restart(timer);
1076        } else if (!rq->hrtick_csd_pending) {
1077                __smp_call_function_single(cpu_of(rq), &rq->hrtick_csd, 0);
1078                rq->hrtick_csd_pending = 1;
1079        }
1080}
1081
1082static int
1083hotplug_hrtick(struct notifier_block *nfb, unsigned long action, void *hcpu)
1084{
1085        int cpu = (int)(long)hcpu;
1086
1087        switch (action) {
1088        case CPU_UP_CANCELED:
1089        case CPU_UP_CANCELED_FROZEN:
1090        case CPU_DOWN_PREPARE:
1091        case CPU_DOWN_PREPARE_FROZEN:
1092        case CPU_DEAD:
1093        case CPU_DEAD_FROZEN:
1094                hrtick_clear(cpu_rq(cpu));
1095                return NOTIFY_OK;
1096        }
1097
1098        return NOTIFY_DONE;
1099}
1100
1101static __init void init_hrtick(void)
1102{
1103        hotcpu_notifier(hotplug_hrtick, 0);
1104}
1105#else
1106/*
1107 * Called to set the hrtick timer state.
1108 *
1109 * called with rq->lock held and irqs disabled
1110 */
1111static void hrtick_start(struct rq *rq, u64 delay)
1112{
1113        __hrtimer_start_range_ns(&rq->hrtick_timer, ns_to_ktime(delay), 0,
1114                        HRTIMER_MODE_REL_PINNED, 0);
1115}
1116
1117static inline void init_hrtick(void)
1118{
1119}
1120#endif /* CONFIG_SMP */
1121
1122static void init_rq_hrtick(struct rq *rq)
1123{
1124#ifdef CONFIG_SMP
1125        rq->hrtick_csd_pending = 0;
1126
1127        rq->hrtick_csd.flags = 0;
1128        rq->hrtick_csd.func = __hrtick_start;
1129        rq->hrtick_csd.info = rq;
1130#endif
1131
1132        hrtimer_init(&rq->hrtick_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
1133        rq->hrtick_timer.function = hrtick;
1134}
1135#else   /* CONFIG_SCHED_HRTICK */
1136static inline void hrtick_clear(struct rq *rq)
1137{
1138}
1139
1140static inline void init_rq_hrtick(struct rq *rq)
1141{
1142}
1143
1144static inline void init_hrtick(void)
1145{
1146}
1147#endif  /* CONFIG_SCHED_HRTICK */
1148
1149/*
1150 * resched_task - mark a task 'to be rescheduled now'.
1151 *
1152 * On UP this means the setting of the need_resched flag, on SMP it
1153 * might also involve a cross-CPU call to trigger the scheduler on
1154 * the target CPU.
1155 */
1156#ifdef CONFIG_SMP
1157
1158#ifndef tsk_is_polling
1159#define tsk_is_polling(t) test_tsk_thread_flag(t, TIF_POLLING_NRFLAG)
1160#endif
1161
1162static void resched_task(struct task_struct *p)
1163{
1164        int cpu;
1165
1166        assert_raw_spin_locked(&task_rq(p)->lock);
1167
1168        if (test_tsk_need_resched(p))
1169                return;
1170
1171        set_tsk_need_resched(p);
1172
1173        cpu = task_cpu(p);
1174        if (cpu == smp_processor_id())
1175                return;
1176
1177        /* NEED_RESCHED must be visible before we test polling */
1178        smp_mb();
1179        if (!tsk_is_polling(p))
1180                smp_send_reschedule(cpu);
1181}
1182
1183static void resched_cpu(int cpu)
1184{
1185        struct rq *rq = cpu_rq(cpu);
1186        unsigned long flags;
1187
1188        if (!raw_spin_trylock_irqsave(&rq->lock, flags))
1189                return;
1190        resched_task(cpu_curr(cpu));
1191        raw_spin_unlock_irqrestore(&rq->lock, flags);
1192}
1193
1194#ifdef CONFIG_NO_HZ
1195/*
1196 * When add_timer_on() enqueues a timer into the timer wheel of an
1197 * idle CPU then this timer might expire before the next timer event
1198 * which is scheduled to wake up that CPU. In case of a completely
1199 * idle system the next event might even be infinite time into the
1200 * future. wake_up_idle_cpu() ensures that the CPU is woken up and
1201 * leaves the inner idle loop so the newly added timer is taken into
1202 * account when the CPU goes back to idle and evaluates the timer
1203 * wheel for the next timer event.
1204 */
1205void wake_up_idle_cpu(int cpu)
1206{
1207        struct rq *rq = cpu_rq(cpu);
1208
1209        if (cpu == smp_processor_id())
1210                return;
1211
1212        /*
1213         * This is safe, as this function is called with the timer
1214         * wheel base lock of (cpu) held. When the CPU is on the way
1215         * to idle and has not yet set rq->curr to idle then it will
1216         * be serialized on the timer wheel base lock and take the new
1217         * timer into account automatically.
1218         */
1219        if (rq->curr != rq->idle)
1220                return;
1221
1222        /*
1223         * We can set TIF_RESCHED on the idle task of the other CPU
1224         * lockless. The worst case is that the other CPU runs the
1225         * idle task through an additional NOOP schedule()
1226         */
1227        set_tsk_need_resched(rq->idle);
1228
1229        /* NEED_RESCHED must be visible before we test polling */
1230        smp_mb();
1231        if (!tsk_is_polling(rq->idle))
1232                smp_send_reschedule(cpu);
1233}
1234
1235int nohz_ratelimit(int cpu)
1236{
1237        struct rq *rq = cpu_rq(cpu);
1238        u64 diff = rq->clock - rq->nohz_stamp;
1239
1240        rq->nohz_stamp = rq->clock;
1241
1242        return diff < (NSEC_PER_SEC / HZ) >> 1;
1243}
1244
1245#endif /* CONFIG_NO_HZ */
1246
1247static u64 sched_avg_period(void)
1248{
1249        return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2;
1250}
1251
1252static void sched_avg_update(struct rq *rq)
1253{
1254        s64 period = sched_avg_period();
1255
1256        while ((s64)(rq->clock - rq->age_stamp) > period) {
1257                /*
1258                 * Inline assembly required to prevent the compiler
1259                 * optimising this loop into a divmod call.
1260                 * See __iter_div_u64_rem() for another example of this.
1261                 */
1262                asm("" : "+rm" (rq->age_stamp));
1263                rq->age_stamp += period;
1264                rq->rt_avg /= 2;
1265        }
1266}
1267
1268static void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
1269{
1270        rq->rt_avg += rt_delta;
1271        sched_avg_update(rq);
1272}
1273
1274#else /* !CONFIG_SMP */
1275static void resched_task(struct task_struct *p)
1276{
1277        assert_raw_spin_locked(&task_rq(p)->lock);
1278        set_tsk_need_resched(p);
1279}
1280
1281static void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
1282{
1283}
1284#endif /* CONFIG_SMP */
1285
1286#if BITS_PER_LONG == 32
1287# define WMULT_CONST    (~0UL)
1288#else
1289# define WMULT_CONST    (1UL << 32)
1290#endif
1291
1292#define WMULT_SHIFT     32
1293
1294/*
1295 * Shift right and round:
1296 */
1297#define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))
1298
1299/*
1300 * delta *= weight / lw
1301 */
1302static unsigned long
1303calc_delta_mine(unsigned long delta_exec, unsigned long weight,
1304                struct load_weight *lw)
1305{
1306        u64 tmp;
1307
1308        if (!lw->inv_weight) {
1309                if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))
1310                        lw->inv_weight = 1;
1311                else
1312                        lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2)
1313                                / (lw->weight+1);
1314        }
1315
1316        tmp = (u64)delta_exec * weight;
1317        /*
1318         * Check whether we'd overflow the 64-bit multiplication:
1319         */
1320        if (unlikely(tmp > WMULT_CONST))
1321                tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,
1322                        WMULT_SHIFT/2);
1323        else
1324                tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);
1325
1326        return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);
1327}
1328
1329static inline void update_load_add(struct load_weight *lw, unsigned long inc)
1330{
1331        lw->weight += inc;
1332        lw->inv_weight = 0;
1333}
1334
1335static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
1336{
1337        lw->weight -= dec;
1338        lw->inv_weight = 0;
1339}
1340
1341/*
1342 * To aid in avoiding the subversion of "niceness" due to uneven distribution
1343 * of tasks with abnormal "nice" values across CPUs the contribution that
1344 * each task makes to its run queue's load is weighted according to its
1345 * scheduling class and "nice" value. For SCHED_NORMAL tasks this is just a
1346 * scaled version of the new time slice allocation that they receive on time
1347 * slice expiry etc.
1348 */
1349
1350#define WEIGHT_IDLEPRIO                3
1351#define WMULT_IDLEPRIO         1431655765
1352
1353/*
1354 * Nice levels are multiplicative, with a gentle 10% change for every
1355 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
1356 * nice 1, it will get ~10% less CPU time than another CPU-bound task
1357 * that remained on nice 0.
1358 *
1359 * The "10% effect" is relative and cumulative: from _any_ nice level,
1360 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
1361 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
1362 * If a task goes up by ~10% and another task goes down by ~10% then
1363 * the relative distance between them is ~25%.)
1364 */
1365static const int prio_to_weight[40] = {
1366 /* -20 */     88761,     71755,     56483,     46273,     36291,
1367 /* -15 */     29154,     23254,     18705,     14949,     11916,
1368 /* -10 */      9548,      7620,      6100,      4904,      3906,
1369 /*  -5 */      3121,      2501,      1991,      1586,      1277,
1370 /*   0 */      1024,       820,       655,       526,       423,
1371 /*   5 */       335,       272,       215,       172,       137,
1372 /*  10 */       110,        87,        70,        56,        45,
1373 /*  15 */        36,        29,        23,        18,        15,
1374};
1375
1376/*
1377 * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated.
1378 *
1379 * In cases where the weight does not change often, we can use the
1380 * precalculated inverse to speed up arithmetics by turning divisions
1381 * into multiplications:
1382 */
1383static const u32 prio_to_wmult[40] = {
1384 /* -20 */     48388,     59856,     76040,     92818,    118348,
1385 /* -15 */    147320,    184698,    229616,    287308,    360437,
1386 /* -10 */    449829,    563644,    704093,    875809,   1099582,
1387 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
1388 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
1389 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
1390 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
1391 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
1392};
1393
1394/* Time spent by the tasks of the cpu accounting group executing in ... */
1395enum cpuacct_stat_index {
1396        CPUACCT_STAT_USER,      /* ... user mode */
1397        CPUACCT_STAT_SYSTEM,    /* ... kernel mode */
1398
1399        CPUACCT_STAT_NSTATS,
1400};
1401
1402#ifdef CONFIG_CGROUP_CPUACCT
1403static void cpuacct_charge(struct task_struct *tsk, u64 cputime);
1404static void cpuacct_update_stats(struct task_struct *tsk,
1405                enum cpuacct_stat_index idx, cputime_t val);
1406#else
1407static inline void cpuacct_charge(struct task_struct *tsk, u64 cputime) {}
1408static inline void cpuacct_update_stats(struct task_struct *tsk,
1409                enum cpuacct_stat_index idx, cputime_t val) {}
1410#endif
1411
1412static inline void inc_cpu_load(struct rq *rq, unsigned long load)
1413{
1414        update_load_add(&rq->load, load);
1415}
1416
1417static inline void dec_cpu_load(struct rq *rq, unsigned long load)
1418{
1419        update_load_sub(&rq->load, load);
1420}
1421
1422#if (defined(CONFIG_SMP) && defined(CONFIG_FAIR_GROUP_SCHED)) || defined(CONFIG_RT_GROUP_SCHED)
1423typedef int (*tg_visitor)(struct task_group *, void *);
1424
1425/*
1426 * Iterate the full tree, calling @down when first entering a node and @up when
1427 * leaving it for the final time.
1428 */
1429static int walk_tg_tree(tg_visitor down, tg_visitor up, void *data)
1430{
1431        struct task_group *parent, *child;
1432        int ret;
1433
1434        rcu_read_lock();
1435        parent = &root_task_group;
1436down:
1437        ret = (*down)(parent, data);
1438        if (ret)
1439                goto out_unlock;
1440        list_for_each_entry_rcu(child, &parent->children, siblings) {
1441                parent = child;
1442                goto down;
1443
1444up:
1445                continue;
1446        }
1447        ret = (*up)(parent, data);
1448        if (ret)
1449                goto out_unlock;
1450
1451        child = parent;
1452        parent = parent->parent;
1453        if (parent)
1454                goto up;
1455out_unlock:
1456        rcu_read_unlock();
1457
1458        return ret;
1459}
1460
1461static int tg_nop(struct task_group *tg, void *data)
1462{
1463        return 0;
1464}
1465#endif
1466
1467#ifdef CONFIG_SMP
1468/* Used instead of source_load when we know the type == 0 */
1469static unsigned long weighted_cpuload(const int cpu)
1470{
1471        return cpu_rq(cpu)->load.weight;
1472}
1473
1474/*
1475 * Return a low guess at the load of a migration-source cpu weighted
1476 * according to the scheduling class and "nice" value.
1477 *
1478 * We want to under-estimate the load of migration sources, to
1479 * balance conservatively.
1480 */
1481static unsigned long source_load(int cpu, int type)
1482{
1483        struct rq *rq = cpu_rq(cpu);
1484        unsigned long total = weighted_cpuload(cpu);
1485
1486        if (type == 0 || !sched_feat(LB_BIAS))
1487                return total;
1488
1489        return min(rq->cpu_load[type-1], total);
1490}
1491
1492/*
1493 * Return a high guess at the load of a migration-target cpu weighted
1494 * according to the scheduling class and "nice" value.
1495 */
1496static unsigned long target_load(int cpu, int type)
1497{
1498        struct rq *rq = cpu_rq(cpu);
1499        unsigned long total = weighted_cpuload(cpu);
1500
1501        if (type == 0 || !sched_feat(LB_BIAS))
1502                return total;
1503
1504        return max(rq->cpu_load[type-1], total);
1505}
1506
1507static unsigned long power_of(int cpu)
1508{
1509        return cpu_rq(cpu)->cpu_power;
1510}
1511
1512static int task_hot(struct task_struct *p, u64 now, struct sched_domain *sd);
1513
1514static unsigned long cpu_avg_load_per_task(int cpu)
1515{
1516        struct rq *rq = cpu_rq(cpu);
1517        unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
1518
1519        if (nr_running)
1520                rq->avg_load_per_task = rq->load.weight / nr_running;
1521        else
1522                rq->avg_load_per_task = 0;
1523
1524        return rq->avg_load_per_task;
1525}
1526
1527#ifdef CONFIG_FAIR_GROUP_SCHED
1528
1529static __read_mostly unsigned long __percpu *update_shares_data;
1530
1531static void __set_se_shares(struct sched_entity *se, unsigned long shares);
1532
1533/*
1534 * Calculate and set the cpu's group shares.
1535 */
1536static void update_group_shares_cpu(struct task_group *tg, int cpu,
1537                                    unsigned long sd_shares,
1538                                    unsigned long sd_rq_weight,
1539                                    unsigned long *usd_rq_weight)
1540{
1541        unsigned long shares, rq_weight;
1542        int boost = 0;
1543
1544        rq_weight = usd_rq_weight[cpu];
1545        if (!rq_weight) {
1546                boost = 1;
1547                rq_weight = NICE_0_LOAD;
1548        }
1549
1550        /*
1551         *             \Sum_j shares_j * rq_weight_i
1552         * shares_i =  -----------------------------
1553         *                  \Sum_j rq_weight_j
1554         */
1555        shares = (sd_shares * rq_weight) / sd_rq_weight;
1556        shares = clamp_t(unsigned long, shares, MIN_SHARES, MAX_SHARES);
1557
1558        if (abs(shares - tg->se[cpu]->load.weight) >
1559                        sysctl_sched_shares_thresh) {
1560                struct rq *rq = cpu_rq(cpu);
1561                unsigned long flags;
1562
1563                raw_spin_lock_irqsave(&rq->lock, flags);
1564                tg->cfs_rq[cpu]->rq_weight = boost ? 0 : rq_weight;
1565                tg->cfs_rq[cpu]->shares = boost ? 0 : shares;
1566                __set_se_shares(tg->se[cpu], shares);
1567                raw_spin_unlock_irqrestore(&rq->lock, flags);
1568        }
1569}
1570
1571/*
1572 * Re-compute the task group their per cpu shares over the given domain.
1573 * This needs to be done in a bottom-up fashion because the rq weight of a
1574 * parent group depends on the shares of its child groups.
1575 */
1576static int tg_shares_up(struct task_group *tg, void *data)
1577{
1578        unsigned long weight, rq_weight = 0, sum_weight = 0, shares = 0;
1579        unsigned long *usd_rq_weight;
1580        struct sched_domain *sd = data;
1581        unsigned long flags;
1582        int i;
1583
1584        if (!tg->se[0])
1585                return 0;
1586
1587        local_irq_save(flags);
1588        usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
1589
1590        for_each_cpu(i, sched_domain_span(sd)) {
1591                weight = tg->cfs_rq[i]->load.weight;
1592                usd_rq_weight[i] = weight;
1593
1594                rq_weight += weight;
1595                /*
1596                 * If there are currently no tasks on the cpu pretend there
1597                 * is one of average load so that when a new task gets to
1598                 * run here it will not get delayed by group starvation.
1599                 */
1600                if (!weight)
1601                        weight = NICE_0_LOAD;
1602
1603                sum_weight += weight;
1604                shares += tg->cfs_rq[i]->shares;
1605        }
1606
1607        if (!rq_weight)
1608                rq_weight = sum_weight;
1609
1610        if ((!shares && rq_weight) || shares > tg->shares)
1611                shares = tg->shares;
1612
1613        if (!sd->parent || !(sd->parent->flags & SD_LOAD_BALANCE))
1614                shares = tg->shares;
1615
1616        for_each_cpu(i, sched_domain_span(sd))
1617                update_group_shares_cpu(tg, i, shares, rq_weight, usd_rq_weight);
1618
1619        local_irq_restore(flags);
1620
1621        return 0;
1622}
1623
1624/*
1625 * Compute the cpu's hierarchical load factor for each task group.
1626 * This needs to be done in a top-down fashion because the load of a child
1627 * group is a fraction of its parents load.
1628 */
1629static int tg_load_down(struct task_group *tg, void *data)
1630{
1631        unsigned long load;
1632        long cpu = (long)data;
1633
1634        if (!tg->parent) {
1635                load = cpu_rq(cpu)->load.weight;
1636        } else {
1637                load = tg->parent->cfs_rq[cpu]->h_load;
1638                load *= tg->cfs_rq[cpu]->shares;
1639                load /= tg->parent->cfs_rq[cpu]->load.weight + 1;
1640        }
1641
1642        tg->cfs_rq[cpu]->h_load = load;
1643
1644        return 0;
1645}
1646
1647static void update_shares(struct sched_domain *sd)
1648{
1649        s64 elapsed;
1650        u64 now;
1651
1652        if (root_task_group_empty())
1653                return;
1654
1655        now = cpu_clock(raw_smp_processor_id());
1656        elapsed = now - sd->last_update;
1657
1658        if (elapsed >= (s64)(u64)sysctl_sched_shares_ratelimit) {
1659                sd->last_update = now;
1660                walk_tg_tree(tg_nop, tg_shares_up, sd);
1661        }
1662}
1663
1664static void update_h_load(long cpu)
1665{
1666        walk_tg_tree(tg_load_down, tg_nop, (void *)cpu);
1667}
1668
1669#else
1670
1671static inline void update_shares(struct sched_domain *sd)
1672{
1673}
1674
1675#endif
1676
1677#ifdef CONFIG_PREEMPT
1678
1679static void double_rq_lock(struct rq *rq1, struct rq *rq2);
1680
1681/*
1682 * fair double_lock_balance: Safely acquires both rq->locks in a fair
1683 * way at the expense of forcing extra atomic operations in all
1684 * invocations.  This assures that the double_lock is acquired using the
1685 * same underlying policy as the spinlock_t on this architecture, which
1686 * reduces latency compared to the unfair variant below.  However, it
1687 * also adds more overhead and therefore may reduce throughput.
1688 */
1689static inline int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
1690        __releases(this_rq->lock)
1691        __acquires(busiest->lock)
1692        __acquires(this_rq->lock)
1693{
1694        raw_spin_unlock(&this_rq->lock);
1695        double_rq_lock(this_rq, busiest);
1696
1697        return 1;
1698}
1699
1700#else
1701/*
1702 * Unfair double_lock_balance: Optimizes throughput at the expense of
1703 * latency by eliminating extra atomic operations when the locks are
1704 * already in proper order on entry.  This favors lower cpu-ids and will
1705 * grant the double lock to lower cpus over higher ids under contention,
1706 * regardless of entry order into the function.
1707 */
1708static int _double_lock_balance(struct rq *this_rq, struct rq *busiest)
1709        __releases(this_rq->lock)
1710        __acquires(busiest->lock)
1711        __acquires(this_rq->lock)
1712{
1713        int ret = 0;
1714
1715        if (unlikely(!raw_spin_trylock(&busiest->lock))) {
1716                if (busiest < this_rq) {
1717                        raw_spin_unlock(&this_rq->lock);
1718                        raw_spin_lock(&busiest->lock);
1719                        raw_spin_lock_nested(&this_rq->lock,
1720                                              SINGLE_DEPTH_NESTING);
1721                        ret = 1;
1722                } else
1723                        raw_spin_lock_nested(&busiest->lock,
1724                                              SINGLE_DEPTH_NESTING);
1725        }
1726        return ret;
1727}
1728
1729#endif /* CONFIG_PREEMPT */
1730
1731/*
1732 * double_lock_balance - lock the busiest runqueue, this_rq is locked already.
1733 */
1734static int double_lock_balance(struct rq *this_rq, struct rq *busiest)
1735{
1736        if (unlikely(!irqs_disabled())) {
1737                /* printk() doesn't work good under rq->lock */
1738                raw_spin_unlock(&this_rq->lock);
1739                BUG_ON(1);
1740        }
1741
1742        return _double_lock_balance(this_rq, busiest);
1743}
1744
1745static inline void double_unlock_balance(struct rq *this_rq, struct rq *busiest)
1746        __releases(busiest->lock)
1747{
1748        raw_spin_unlock(&busiest->lock);
1749        lock_set_subclass(&this_rq->lock.dep_map, 0, _RET_IP_);
1750}
1751
1752/*
1753 * double_rq_lock - safely lock two runqueues
1754 *
1755 * Note this does not disable interrupts like task_rq_lock,
1756 * you need to do so manually before calling.
1757 */
1758static void double_rq_lock(struct rq *rq1, struct rq *rq2)
1759        __acquires(rq1->lock)
1760        __acquires(rq2->lock)
1761{
1762        BUG_ON(!irqs_disabled());
1763        if (rq1 == rq2) {
1764                raw_spin_lock(&rq1->lock);
1765                __acquire(rq2->lock);   /* Fake it out ;) */
1766        } else {
1767                if (rq1 < rq2) {
1768                        raw_spin_lock(&rq1->lock);
1769                        raw_spin_lock_nested(&rq2->lock, SINGLE_DEPTH_NESTING);
1770                } else {
1771                        raw_spin_lock(&rq2->lock);
1772                        raw_spin_lock_nested(&rq1->lock, SINGLE_DEPTH_NESTING);
1773                }
1774        }
1775}
1776
1777/*
1778 * double_rq_unlock - safely unlock two runqueues
1779 *
1780 * Note this does not restore interrupts like task_rq_unlock,
1781 * you need to do so manually after calling.
1782 */
1783static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
1784        __releases(rq1->lock)
1785        __releases(rq2->lock)
1786{
1787        raw_spin_unlock(&rq1->lock);
1788        if (rq1 != rq2)
1789                raw_spin_unlock(&rq2->lock);
1790        else
1791                __release(rq2->lock);
1792}
1793
1794#endif
1795
1796#ifdef CONFIG_FAIR_GROUP_SCHED
1797static void cfs_rq_set_shares(struct cfs_rq *cfs_rq, unsigned long shares)
1798{
1799#ifdef CONFIG_SMP
1800        cfs_rq->shares = shares;
1801#endif
1802}
1803#endif
1804
1805static void calc_load_account_idle(struct rq *this_rq);
1806static void update_sysctl(void);
1807static int get_update_sysctl_factor(void);
1808
1809static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
1810{
1811        set_task_rq(p, cpu);
1812#ifdef CONFIG_SMP
1813        /*
1814         * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
1815         * successfuly executed on another CPU. We must ensure that updates of
1816         * per-task data have been completed by this moment.
1817         */
1818        smp_wmb();
1819        task_thread_info(p)->cpu = cpu;
1820#endif
1821}
1822
1823static const struct sched_class rt_sched_class;
1824
1825#define sched_class_highest (&rt_sched_class)
1826#define for_each_class(class) \
1827   for (class = sched_class_highest; class; class = class->next)
1828
1829#include "sched_stats.h"
1830
1831static void inc_nr_running(struct rq *rq)
1832{
1833        rq->nr_running++;
1834}
1835
1836static void dec_nr_running(struct rq *rq)
1837{
1838        rq->nr_running--;
1839}
1840
1841static void set_load_weight(struct task_struct *p)
1842{
1843        if (task_has_rt_policy(p)) {
1844                p->se.load.weight = 0;
1845                p->se.load.inv_weight = WMULT_CONST;
1846                return;
1847        }
1848
1849        /*
1850         * SCHED_IDLE tasks get minimal weight:
1851         */
1852        if (p->policy == SCHED_IDLE) {
1853                p->se.load.weight = WEIGHT_IDLEPRIO;
1854                p->se.load.inv_weight = WMULT_IDLEPRIO;
1855                return;
1856        }
1857
1858        p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
1859        p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
1860}
1861
1862static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
1863{
1864        update_rq_clock(rq);
1865        sched_info_queued(p);
1866        p->sched_class->enqueue_task(rq, p, flags);
1867        p->se.on_rq = 1;
1868}
1869
1870static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
1871{
1872        update_rq_clock(rq);
1873        sched_info_dequeued(p);
1874        p->sched_class->dequeue_task(rq, p, flags);
1875        p->se.on_rq = 0;
1876}
1877
1878/*
1879 * activate_task - move a task to the runqueue.
1880 */
1881static void activate_task(struct rq *rq, struct task_struct *p, int flags)
1882{
1883        if (task_contributes_to_load(p))
1884                rq->nr_uninterruptible--;
1885
1886        enqueue_task(rq, p, flags);
1887        inc_nr_running(rq);
1888}
1889
1890/*
1891 * deactivate_task - remove a task from the runqueue.
1892 */
1893static void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
1894{
1895        if (task_contributes_to_load(p))
1896                rq->nr_uninterruptible++;
1897
1898        dequeue_task(rq, p, flags);
1899        dec_nr_running(rq);
1900}
1901
1902#include "sched_idletask.c"
1903#include "sched_fair.c"
1904#include "sched_rt.c"
1905#ifdef CONFIG_SCHED_DEBUG
1906# include "sched_debug.c"
1907#endif
1908
1909/*
1910 * __normal_prio - return the priority that is based on the static prio
1911 */
1912static inline int __normal_prio(struct task_struct *p)
1913{
1914        return p->static_prio;
1915}
1916
1917/*
1918 * Calculate the expected normal priority: i.e. priority
1919 * without taking RT-inheritance into account. Might be
1920 * boosted by interactivity modifiers. Changes upon fork,
1921 * setprio syscalls, and whenever the interactivity
1922 * estimator recalculates.
1923 */
1924static inline int normal_prio(struct task_struct *p)
1925{
1926        int prio;
1927
1928        if (task_has_rt_policy(p))
1929                prio = MAX_RT_PRIO-1 - p->rt_priority;
1930        else
1931                prio = __normal_prio(p);
1932        return prio;
1933}
1934
1935/*
1936 * Calculate the current priority, i.e. the priority
1937 * taken into account by the scheduler. This value might
1938 * be boosted by RT tasks, or might be boosted by
1939 * interactivity modifiers. Will be RT if the task got
1940 * RT-boosted. If not then it returns p->normal_prio.
1941 */
1942static int effective_prio(struct task_struct *p)
1943{
1944        p->normal_prio = normal_prio(p);
1945        /*
1946         * If we are RT tasks or we were boosted to RT priority,
1947         * keep the priority unchanged. Otherwise, update priority
1948         * to the normal priority:
1949         */
1950        if (!rt_prio(p->prio))
1951                return p->normal_prio;
1952        return p->prio;
1953}
1954
1955/**
1956 * task_curr - is this task currently executing on a CPU?
1957 * @p: the task in question.
1958 */
1959inline int task_curr(const struct task_struct *p)
1960{
1961        return cpu_curr(task_cpu(p)) == p;
1962}
1963
1964static inline void check_class_changed(struct rq *rq, struct task_struct *p,
1965                                       const struct sched_class *prev_class,
1966                                       int oldprio, int running)
1967{
1968        if (prev_class != p->sched_class) {
1969                if (prev_class->switched_from)
1970                        prev_class->switched_from(rq, p, running);
1971                p->sched_class->switched_to(rq, p, running);
1972        } else
1973                p->sched_class->prio_changed(rq, p, oldprio, running);
1974}
1975
1976#ifdef CONFIG_SMP
1977/*
1978 * Is this task likely cache-hot:
1979 */
1980static int
1981task_hot(struct task_struct *p, u64 now, struct sched_domain *sd)
1982{
1983        s64 delta;
1984
1985        if (p->sched_class != &fair_sched_class)
1986                return 0;
1987
1988        /*
1989         * Buddy candidates are cache hot:
1990         */
1991        if (sched_feat(CACHE_HOT_BUDDY) && this_rq()->nr_running &&
1992                        (&p->se == cfs_rq_of(&p->se)->next ||
1993                         &p->se == cfs_rq_of(&p->se)->last))
1994                return 1;
1995
1996        if (sysctl_sched_migration_cost == -1)
1997                return 1;
1998        if (sysctl_sched_migration_cost == 0)
1999                return 0;
2000
2001        delta = now - p->se.exec_start;
2002
2003        return delta < (s64)sysctl_sched_migration_cost;
2004}
2005
2006void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
2007{
2008#ifdef CONFIG_SCHED_DEBUG
2009        /*
2010         * We should never call set_task_cpu() on a blocked task,
2011         * ttwu() will sort out the placement.
2012         */
2013        WARN_ON_ONCE(p->state != TASK_RUNNING && p->state != TASK_WAKING &&
2014                        !(task_thread_info(p)->preempt_count & PREEMPT_ACTIVE));
2015#endif
2016
2017        trace_sched_migrate_task(p, new_cpu);
2018
2019        if (task_cpu(p) != new_cpu) {
2020                p->se.nr_migrations++;
2021                perf_sw_event(PERF_COUNT_SW_CPU_MIGRATIONS, 1, 1, NULL, 0);
2022        }
2023
2024        __set_task_cpu(p, new_cpu);
2025}
2026
2027struct migration_arg {
2028        struct task_struct *task;
2029        int dest_cpu;
2030};
2031
2032static int migration_cpu_stop(void *data);
2033
2034/*
2035 * The task's runqueue lock must be held.
2036 * Returns true if you have to wait for migration thread.
2037 */
2038static bool migrate_task(struct task_struct *p, int dest_cpu)
2039{
2040        struct rq *rq = task_rq(p);
2041
2042        /*
2043         * If the task is not on a runqueue (and not running), then
2044         * the next wake-up will properly place the task.
2045         */
2046        return p->se.on_rq || task_running(rq, p);
2047}
2048
2049/*
2050 * wait_task_inactive - wait for a thread to unschedule.
2051 *
2052 * If @match_state is nonzero, it's the @p->state value just checked and
2053 * not expected to change.  If it changes, i.e. @p might have woken up,
2054 * then return zero.  When we succeed in waiting for @p to be off its CPU,
2055 * we return a positive number (its total switch count).  If a second call
2056 * a short while later returns the same number, the caller can be sure that
2057 * @p has remained unscheduled the whole time.
2058 *
2059 * The caller must ensure that the task *will* unschedule sometime soon,
2060 * else this function might spin for a *long* time. This function can't
2061 * be called with interrupts off, or it may introduce deadlock with
2062 * smp_call_function() if an IPI is sent by the same process we are
2063 * waiting to become inactive.
2064 */
2065unsigned long wait_task_inactive(struct task_struct *p, long match_state)
2066{
2067        unsigned long flags;
2068        int running, on_rq;
2069        unsigned long ncsw;
2070        struct rq *rq;
2071
2072        for (;;) {
2073                /*
2074                 * We do the initial early heuristics without holding
2075                 * any task-queue locks at all. We'll only try to get
2076                 * the runqueue lock when things look like they will
2077                 * work out!
2078                 */
2079                rq = task_rq(p);
2080
2081                /*
2082                 * If the task is actively running on another CPU
2083                 * still, just relax and busy-wait without holding
2084                 * any locks.
2085                 *
2086                 * NOTE! Since we don't hold any locks, it's not
2087                 * even sure that "rq" stays as the right runqueue!
2088                 * But we don't care, since "task_running()" will
2089                 * return false if the runqueue has changed and p
2090                 * is actually now running somewhere else!
2091                 */
2092                while (task_running(rq, p)) {
2093                        if (match_state && unlikely(p->state != match_state))
2094                                return 0;
2095                        cpu_relax();
2096                }
2097
2098                /*
2099                 * Ok, time to look more closely! We need the rq
2100                 * lock now, to be *sure*. If we're wrong, we'll
2101                 * just go back and repeat.
2102                 */
2103                rq = task_rq_lock(p, &flags);
2104                trace_sched_wait_task(p);
2105                running = task_running(rq, p);
2106                on_rq = p->se.on_rq;
2107                ncsw = 0;
2108                if (!match_state || p->state == match_state)
2109                        ncsw = p->nvcsw | LONG_MIN; /* sets MSB */
2110                task_rq_unlock(rq, &flags);
2111
2112                /*
2113                 * If it changed from the expected state, bail out now.
2114                 */
2115                if (unlikely(!ncsw))
2116                        break;
2117
2118                /*
2119                 * Was it really running after all now that we
2120                 * checked with the proper locks actually held?
2121                 *
2122                 * Oops. Go back and try again..
2123                 */
2124                if (unlikely(running)) {
2125                        cpu_relax();
2126                        continue;
2127                }
2128
2129                /*
2130                 * It's not enough that it's not actively running,
2131                 * it must be off the runqueue _entirely_, and not
2132                 * preempted!
2133                 *
2134                 * So if it was still runnable (but just not actively
2135                 * running right now), it's preempted, and we should
2136                 * yield - it could be a while.
2137                 */
2138                if (unlikely(on_rq)) {
2139                        schedule_timeout_uninterruptible(1);
2140                        continue;
2141                }
2142
2143                /*
2144                 * Ahh, all good. It wasn't running, and it wasn't
2145                 * runnable, which means that it will never become
2146                 * running in the future either. We're all done!
2147                 */
2148                break;
2149        }
2150
2151        return ncsw;
2152}
2153
2154/***
2155 * kick_process - kick a running thread to enter/exit the kernel
2156 * @p: the to-be-kicked thread
2157 *
2158 * Cause a process which is running on another CPU to enter
2159 * kernel-mode, without any delay. (to get signals handled.)
2160 *
2161 * NOTE: this function doesnt have to take the runqueue lock,
2162 * because all it wants to ensure is that the remote task enters
2163 * the kernel. If the IPI races and the task has been migrated
2164 * to another CPU then no harm is done and the purpose has been
2165 * achieved as well.
2166 */
2167void kick_process(struct task_struct *p)
2168{
2169        int cpu;
2170
2171        preempt_disable();
2172        cpu = task_cpu(p);
2173        if ((cpu != smp_processor_id()) && task_curr(p))
2174                smp_send_reschedule(cpu);
2175        preempt_enable();
2176}
2177EXPORT_SYMBOL_GPL(kick_process);
2178#endif /* CONFIG_SMP */
2179
2180/**
2181 * task_oncpu_function_call - call a function on the cpu on which a task runs
2182 * @p:          the task to evaluate
2183 * @func:       the function to be called
2184 * @info:       the function call argument
2185 *
2186 * Calls the function @func when the task is currently running. This might
2187 * be on the current CPU, which just calls the function directly
2188 */
2189void task_oncpu_function_call(struct task_struct *p,
2190                              void (*func) (void *info), void *info)
2191{
2192        int cpu;
2193
2194        preempt_disable();
2195        cpu = task_cpu(p);
2196        if (task_curr(p))
2197                smp_call_function_single(cpu, func, info, 1);
2198        preempt_enable();
2199}
2200
2201#ifdef CONFIG_SMP
2202/*
2203 * ->cpus_allowed is protected by either TASK_WAKING or rq->lock held.
2204 */
2205static int select_fallback_rq(int cpu, struct task_struct *p)
2206{
2207        int dest_cpu;
2208        const struct cpumask *nodemask = cpumask_of_node(cpu_to_node(cpu));
2209
2210        /* Look for allowed, online CPU in same node. */
2211        for_each_cpu_and(dest_cpu, nodemask, cpu_active_mask)
2212                if (cpumask_test_cpu(dest_cpu, &p->cpus_allowed))
2213                        return dest_cpu;
2214
2215        /* Any allowed, online CPU? */
2216        dest_cpu = cpumask_any_and(&p->cpus_allowed, cpu_active_mask);
2217        if (dest_cpu < nr_cpu_ids)
2218                return dest_cpu;
2219
2220        /* No more Mr. Nice Guy. */
2221        if (unlikely(dest_cpu >= nr_cpu_ids)) {
2222                dest_cpu = cpuset_cpus_allowed_fallback(p);
2223                /*
2224                 * Don't tell them about moving exiting tasks or
2225                 * kernel threads (both mm NULL), since they never
2226                 * leave kernel.
2227                 */
2228                if (p->mm && printk_ratelimit()) {
2229                        printk(KERN_INFO "process %d (%s) no "
2230                               "longer affine to cpu%d\n",
2231                               task_pid_nr(p), p->comm, cpu);
2232                }
2233        }
2234
2235        return dest_cpu;
2236}
2237
2238/*
2239 * The caller (fork, wakeup) owns TASK_WAKING, ->cpus_allowed is stable.
2240 */
2241static inline
2242int select_task_rq(struct rq *rq, struct task_struct *p, int sd_flags, int wake_flags)
2243{
2244        int cpu = p->sched_class->select_task_rq(rq, p, sd_flags, wake_flags);
2245
2246        /*
2247         * In order not to call set_task_cpu() on a blocking task we need
2248         * to rely on ttwu() to place the task on a valid ->cpus_allowed
2249         * cpu.
2250         *
2251         * Since this is common to all placement strategies, this lives here.
2252         *
2253         * [ this allows ->select_task() to simply return task_cpu(p) and
2254         *   not worry about this generic constraint ]
2255         */
2256        if (unlikely(!cpumask_test_cpu(cpu, &p->cpus_allowed) ||
2257                     !cpu_online(cpu)))
2258                cpu = select_fallback_rq(task_cpu(p), p);
2259
2260        return cpu;
2261}
2262
2263static void update_avg(u64 *avg, u64 sample)
2264{
2265        s64 diff = sample - *avg;
2266        *avg += diff >> 3;
2267}
2268#endif
2269
2270/***
2271 * try_to_wake_up - wake up a thread
2272 * @p: the to-be-woken-up thread
2273 * @state: the mask of task states that can be woken
2274 * @sync: do a synchronous wakeup?
2275 *
2276 * Put it on the run-queue if it's not already there. The "current"
2277 * thread is always on the run-queue (except when the actual
2278 * re-schedule is in progress), and as such you're allowed to do
2279 * the simpler "current->state = TASK_RUNNING" to mark yourself
2280 * runnable without the overhead of this.
2281 *
2282 * returns failure only if the task is already active.
2283 */
2284static int try_to_wake_up(struct task_struct *p, unsigned int state,
2285                          int wake_flags)
2286{
2287        int cpu, orig_cpu, this_cpu, success = 0;
2288        unsigned long flags;
2289        unsigned long en_flags = ENQUEUE_WAKEUP;
2290        struct rq *rq;
2291
2292        this_cpu = get_cpu();
2293
2294        smp_wmb();
2295        rq = task_rq_lock(p, &flags);
2296        if (!(p->state & state))
2297                goto out;
2298
2299        if (p->se.on_rq)
2300                goto out_running;
2301
2302        cpu = task_cpu(p);
2303        orig_cpu = cpu;
2304
2305#ifdef CONFIG_SMP
2306        if (unlikely(task_running(rq, p)))
2307                goto out_activate;
2308
2309        /*
2310         * In order to handle concurrent wakeups and release the rq->lock
2311         * we put the task in TASK_WAKING state.
2312         *
2313         * First fix up the nr_uninterruptible count:
2314         */
2315        if (task_contributes_to_load(p)) {
2316                if (likely(cpu_online(orig_cpu)))
2317                        rq->nr_uninterruptible--;
2318                else
2319                        this_rq()->nr_uninterruptible--;
2320        }
2321        p->state = TASK_WAKING;
2322
2323        if (p->sched_class->task_waking) {
2324                p->sched_class->task_waking(rq, p);
2325                en_flags |= ENQUEUE_WAKING;
2326        }
2327
2328        cpu = select_task_rq(rq, p, SD_BALANCE_WAKE, wake_flags);
2329        if (cpu != orig_cpu)
2330                set_task_cpu(p, cpu);
2331        __task_rq_unlock(rq);
2332
2333        rq = cpu_rq(cpu);
2334        raw_spin_lock(&rq->lock);
2335
2336        /*
2337         * We migrated the task without holding either rq->lock, however
2338         * since the task is not on the task list itself, nobody else
2339         * will try and migrate the task, hence the rq should match the
2340         * cpu we just moved it to.
2341         */
2342        WARN_ON(task_cpu(p) != cpu);
2343        WARN_ON(p->state != TASK_WAKING);
2344
2345#ifdef CONFIG_SCHEDSTATS
2346        schedstat_inc(rq, ttwu_count);
2347        if (cpu == this_cpu)
2348                schedstat_inc(rq, ttwu_local);
2349        else {
2350                struct sched_domain *sd;
2351                for_each_domain(this_cpu, sd) {
2352                        if (cpumask_test_cpu(cpu, sched_domain_span(sd))) {
2353                                schedstat_inc(sd, ttwu_wake_remote);
2354                                break;
2355                        }
2356                }
2357        }
2358#endif /* CONFIG_SCHEDSTATS */
2359
2360out_activate:
2361#endif /* CONFIG_SMP */
2362        schedstat_inc(p, se.statistics.nr_wakeups);
2363        if (wake_flags & WF_SYNC)
2364                schedstat_inc(p, se.statistics.nr_wakeups_sync);
2365        if (orig_cpu != cpu)
2366                schedstat_inc(p, se.statistics.nr_wakeups_migrate);
2367        if (cpu == this_cpu)
2368                schedstat_inc(p, se.statistics.nr_wakeups_local);
2369        else
2370                schedstat_inc(p, se.statistics.nr_wakeups_remote);
2371        activate_task(rq, p, en_flags);
2372        success = 1;
2373
2374out_running:
2375        trace_sched_wakeup(p, success);
2376        check_preempt_curr(rq, p, wake_flags);
2377
2378        p->state = TASK_RUNNING;
2379#ifdef CONFIG_SMP
2380        if (p->sched_class->task_woken)
2381                p->sched_class->task_woken(rq, p);
2382
2383        if (unlikely(rq->idle_stamp)) {
2384                u64 delta = rq->clock - rq->idle_stamp;
2385                u64 max = 2*sysctl_sched_migration_cost;
2386
2387                if (delta > max)
2388                        rq->avg_idle = max;
2389                else
2390                        update_avg(&rq->avg_idle, delta);
2391                rq->idle_stamp = 0;
2392        }
2393#endif
2394out:
2395        task_rq_unlock(rq, &flags);
2396        put_cpu();
2397
2398        return success;
2399}
2400
2401/**
2402 * wake_up_process - Wake up a specific process
2403 * @p: The process to be woken up.
2404 *
2405 * Attempt to wake up the nominated process and move it to the set of runnable
2406 * processes.  Returns 1 if the process was woken up, 0 if it was already
2407 * running.
2408 *
2409 * It may be assumed that this function implies a write memory barrier before
2410 * changing the task state if and only if any tasks are woken up.
2411 */
2412int wake_up_process(struct task_struct *p)
2413{
2414        return try_to_wake_up(p, TASK_ALL, 0);
2415}
2416EXPORT_SYMBOL(wake_up_process);
2417
2418int wake_up_state(struct task_struct *p, unsigned int state)
2419{
2420        return try_to_wake_up(p, state, 0);
2421}
2422
2423/*
2424 * Perform scheduler related setup for a newly forked process p.
2425 * p is forked by current.
2426 *
2427 * __sched_fork() is basic setup used by init_idle() too:
2428 */
2429static void __sched_fork(struct task_struct *p)
2430{
2431        p->se.exec_start                = 0;
2432        p->se.sum_exec_runtime          = 0;
2433        p->se.prev_sum_exec_runtime     = 0;
2434        p->se.nr_migrations             = 0;
2435
2436#ifdef CONFIG_SCHEDSTATS
2437        memset(&p->se.statistics, 0, sizeof(p->se.statistics));
2438#endif
2439
2440        INIT_LIST_HEAD(&p->rt.run_list);
2441        p->se.on_rq = 0;
2442        INIT_LIST_HEAD(&p->se.group_node);
2443
2444#ifdef CONFIG_PREEMPT_NOTIFIERS
2445        INIT_HLIST_HEAD(&p->preempt_notifiers);
2446#endif
2447}
2448
2449/*
2450 * fork()/clone()-time setup:
2451 */
2452void sched_fork(struct task_struct *p, int clone_flags)
2453{
2454        int cpu = get_cpu();
2455
2456        __sched_fork(p);
2457        /*
2458         * We mark the process as running here. This guarantees that
2459         * nobody will actually run it, and a signal or other external
2460         * event cannot wake it up and insert it on the runqueue either.
2461         */
2462        p->state = TASK_RUNNING;
2463
2464        /*
2465         * Revert to default priority/policy on fork if requested.
2466         */
2467        if (unlikely(p->sched_reset_on_fork)) {
2468                if (p->policy == SCHED_FIFO || p->policy == SCHED_RR) {
2469                        p->policy = SCHED_NORMAL;
2470                        p->normal_prio = p->static_prio;
2471                }
2472
2473                if (PRIO_TO_NICE(p->static_prio) < 0) {
2474                        p->static_prio = NICE_TO_PRIO(0);
2475                        p->normal_prio = p->static_prio;
2476                        set_load_weight(p);
2477                }
2478
2479                /*
2480                 * We don't need the reset flag anymore after the fork. It has
2481                 * fulfilled its duty:
2482                 */
2483                p->sched_reset_on_fork = 0;
2484        }
2485
2486        /*
2487         * Make sure we do not leak PI boosting priority to the child.
2488         */
2489        p->prio = current->normal_prio;
2490
2491        if (!rt_prio(p->prio))
2492                p->sched_class = &fair_sched_class;
2493
2494        if (p->sched_class->task_fork)
2495                p->sched_class->task_fork(p);
2496
2497        /*
2498         * The child is not yet in the pid-hash so no cgroup attach races,
2499         * and the cgroup is pinned to this child due to cgroup_fork()
2500         * is ran before sched_fork().
2501         *
2502         * Silence PROVE_RCU.
2503         */
2504        rcu_read_lock();
2505        set_task_cpu(p, cpu);
2506        rcu_read_unlock();
2507
2508#if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
2509        if (likely(sched_info_on()))
2510                memset(&p->sched_info, 0, sizeof(p->sched_info));
2511#endif
2512#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
2513        p->oncpu = 0;
2514#endif
2515#ifdef CONFIG_PREEMPT
2516        /* Want to start with kernel preemption disabled. */
2517        task_thread_info(p)->preempt_count = 1;
2518#endif
2519        plist_node_init(&p->pushable_tasks, MAX_PRIO);
2520
2521        put_cpu();
2522}
2523
2524/*
2525 * wake_up_new_task - wake up a newly created task for the first time.
2526 *
2527 * This function will do some initial scheduler statistics housekeeping
2528 * that must be done for every newly created context, then puts the task
2529 * on the runqueue and wakes it.
2530 */
2531void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
2532{
2533        unsigned long flags;
2534        struct rq *rq;
2535        int cpu __maybe_unused = get_cpu();
2536
2537#ifdef CONFIG_SMP
2538        rq = task_rq_lock(p, &flags);
2539        p->state = TASK_WAKING;
2540
2541        /*
2542         * Fork balancing, do it here and not earlier because:
2543         *  - cpus_allowed can change in the fork path
2544         *  - any previously selected cpu might disappear through hotplug
2545         *
2546         * We set TASK_WAKING so that select_task_rq() can drop rq->lock
2547         * without people poking at ->cpus_allowed.
2548         */
2549        cpu = select_task_rq(rq, p, SD_BALANCE_FORK, 0);
2550        set_task_cpu(p, cpu);
2551
2552        p->state = TASK_RUNNING;
2553        task_rq_unlock(rq, &flags);
2554#endif
2555
2556        rq = task_rq_lock(p, &flags);
2557        activate_task(rq, p, 0);
2558        trace_sched_wakeup_new(p, 1);
2559        check_preempt_curr(rq, p, WF_FORK);
2560#ifdef CONFIG_SMP
2561        if (p->sched_class->task_woken)
2562                p->sched_class->task_woken(rq, p);
2563#endif
2564        task_rq_unlock(rq, &flags);
2565        put_cpu();
2566}
2567
2568#ifdef CONFIG_PREEMPT_NOTIFIERS
2569
2570/**
2571 * preempt_notifier_register - tell me when current is being preempted & rescheduled
2572 * @notifier: notifier struct to register
2573 */
2574void preempt_notifier_register(struct preempt_notifier *notifier)
2575{
2576        hlist_add_head(&notifier->link, &current->preempt_notifiers);
2577}
2578EXPORT_SYMBOL_GPL(preempt_notifier_register);
2579
2580/**
2581 * preempt_notifier_unregister - no longer interested in preemption notifications
2582 * @notifier: notifier struct to unregister
2583 *
2584 * This is safe to call from within a preemption notifier.
2585 */
2586void preempt_notifier_unregister(struct preempt_notifier *notifier)
2587{
2588        hlist_del(&notifier->link);
2589}
2590EXPORT_SYMBOL_GPL(preempt_notifier_unregister);
2591
2592static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
2593{
2594        struct preempt_notifier *notifier;
2595        struct hlist_node *node;
2596
2597        hlist_for_each_entry(notifier, node, &curr->preempt_notifiers, link)
2598                notifier->ops->sched_in(notifier, raw_smp_processor_id());
2599}
2600
2601static void
2602fire_sched_out_preempt_notifiers(struct task_struct *curr,
2603                                 struct task_struct *next)
2604{
2605        struct preempt_notifier *notifier;
2606        struct hlist_node *node;
2607
2608        hlist_for_each_entry(notifier, node, &curr->preempt_notifiers, link)
2609                notifier->ops->sched_out(notifier, next);
2610}
2611
2612#else /* !CONFIG_PREEMPT_NOTIFIERS */
2613
2614static void fire_sched_in_preempt_notifiers(struct task_struct *curr)
2615{
2616}
2617
2618static void
2619fire_sched_out_preempt_notifiers(struct task_struct *curr,
2620                                 struct task_struct *next)
2621{
2622}
2623
2624#endif /* CONFIG_PREEMPT_NOTIFIERS */
2625
2626/**
2627 * prepare_task_switch - prepare to switch tasks
2628 * @rq: the runqueue preparing to switch
2629 * @prev: the current task that is being switched out
2630 * @next: the task we are going to switch to.
2631 *
2632 * This is called with the rq lock held and interrupts off. It must
2633 * be paired with a subsequent finish_task_switch after the context
2634 * switch.
2635 *
2636 * prepare_task_switch sets up locking and calls architecture specific
2637 * hooks.
2638 */
2639static inline void
2640prepare_task_switch(struct rq *rq, struct task_struct *prev,
2641                    struct task_struct *next)
2642{
2643        fire_sched_out_preempt_notifiers(prev, next);
2644        prepare_lock_switch(rq, next);
2645        prepare_arch_switch(next);
2646}
2647
2648/**
2649 * finish_task_switch - clean up after a task-switch
2650 * @rq: runqueue associated with task-switch
2651 * @prev: the thread we just switched away from.
2652 *
2653 * finish_task_switch must be called after the context switch, paired
2654 * with a prepare_task_switch call before the context switch.
2655 * finish_task_switch will reconcile locking set up by prepare_task_switch,
2656 * and do any other architecture-specific cleanup actions.
2657 *
2658 * Note that we may have delayed dropping an mm in context_switch(). If
2659 * so, we finish that here outside of the runqueue lock. (Doing it
2660 * with the lock held can cause deadlocks; see schedule() for
2661 * details.)
2662 */
2663static void finish_task_switch(struct rq *rq, struct task_struct *prev)
2664        __releases(rq->lock)
2665{
2666        struct mm_struct *mm = rq->prev_mm;
2667        long prev_state;
2668
2669        rq->prev_mm = NULL;
2670
2671        /*
2672         * A task struct has one reference for the use as "current".
2673         * If a task dies, then it sets TASK_DEAD in tsk->state and calls
2674         * schedule one last time. The schedule call will never return, and
2675         * the scheduled task must drop that reference.
2676         * The test for TASK_DEAD must occur while the runqueue locks are
2677         * still held, otherwise prev could be scheduled on another cpu, die
2678         * there before we look at prev->state, and then the reference would
2679         * be dropped twice.
2680         *              Manfred Spraul <manfred@colorfullife.com>
2681         */
2682        prev_state = prev->state;
2683        finish_arch_switch(prev);
2684#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
2685        local_irq_disable();
2686#endif /* __ARCH_WANT_INTERRUPTS_ON_CTXSW */
2687        perf_event_task_sched_in(current);
2688#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
2689        local_irq_enable();
2690#endif /* __ARCH_WANT_INTERRUPTS_ON_CTXSW */
2691        finish_lock_switch(rq, prev);
2692
2693        fire_sched_in_preempt_notifiers(current);
2694        if (mm)
2695                mmdrop(mm);
2696        if (unlikely(prev_state == TASK_DEAD)) {
2697                /*
2698                 * Remove function-return probe instances associated with this
2699                 * task and put them back on the free list.
2700                 */
2701                kprobe_flush_task(prev);
2702                put_task_struct(prev);
2703        }
2704}
2705
2706#ifdef CONFIG_SMP
2707
2708/* assumes rq->lock is held */
2709static inline void pre_schedule(struct rq *rq, struct task_struct *prev)
2710{
2711        if (prev->sched_class->pre_schedule)
2712                prev->sched_class->pre_schedule(rq, prev);
2713}
2714
2715/* rq->lock is NOT held, but preemption is disabled */
2716static inline void post_schedule(struct rq *rq)
2717{
2718        if (rq->post_schedule) {
2719                unsigned long flags;
2720
2721                raw_spin_lock_irqsave(&rq->lock, flags);
2722                if (rq->curr->sched_class->post_schedule)
2723                        rq->curr->sched_class->post_schedule(rq);
2724                raw_spin_unlock_irqrestore(&rq->lock, flags);
2725
2726                rq->post_schedule = 0;
2727        }
2728}
2729
2730#else
2731
2732static inline void pre_schedule(struct rq *rq, struct task_struct *p)
2733{
2734}
2735
2736static inline void post_schedule(struct rq *rq)
2737{
2738}
2739
2740#endif
2741
2742/**
2743 * schedule_tail - first thing a freshly forked thread must call.
2744 * @prev: the thread we just switched away from.
2745 */
2746asmlinkage void schedule_tail(struct task_struct *prev)
2747        __releases(rq->lock)
2748{
2749        struct rq *rq = this_rq();
2750
2751        finish_task_switch(rq, prev);
2752
2753        /*
2754         * FIXME: do we need to worry about rq being invalidated by the
2755         * task_switch?
2756         */
2757        post_schedule(rq);
2758
2759#ifdef __ARCH_WANT_UNLOCKED_CTXSW
2760        /* In this case, finish_task_switch does not reenable preemption */
2761        preempt_enable();
2762#endif
2763        if (current->set_child_tid)
2764                put_user(task_pid_vnr(current), current->set_child_tid);
2765}
2766
2767/*
2768 * context_switch - switch to the new MM and the new
2769 * thread's register state.
2770 */
2771static inline void
2772context_switch(struct rq *rq, struct task_struct *prev,
2773               struct task_struct *next)
2774{
2775        struct mm_struct *mm, *oldmm;
2776
2777        prepare_task_switch(rq, prev, next);
2778        trace_sched_switch(prev, next);
2779        mm = next->mm;
2780        oldmm = prev->active_mm;
2781        /*
2782         * For paravirt, this is coupled with an exit in switch_to to
2783         * combine the page table reload and the switch backend into
2784         * one hypercall.
2785         */
2786        arch_start_context_switch(prev);
2787
2788        if (likely(!mm)) {
2789                next->active_mm = oldmm;
2790                atomic_inc(&oldmm->mm_count);
2791                enter_lazy_tlb(oldmm, next);
2792        } else
2793                switch_mm(oldmm, mm, next);
2794
2795        if (likely(!prev->mm)) {
2796                prev->active_mm = NULL;
2797                rq->prev_mm = oldmm;
2798        }
2799        /*
2800         * Since the runqueue lock will be released by the next
2801         * task (which is an invalid locking op but in the case
2802         * of the scheduler it's an obvious special-case), so we
2803         * do an early lockdep release here:
2804         */
2805#ifndef __ARCH_WANT_UNLOCKED_CTXSW
2806        spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
2807#endif
2808
2809        /* Here we just switch the register state and the stack. */
2810        switch_to(prev, next, prev);
2811
2812        barrier();
2813        /*
2814         * this_rq must be evaluated again because prev may have moved
2815         * CPUs since it called schedule(), thus the 'rq' on its stack
2816         * frame will be invalid.
2817         */
2818        finish_task_switch(this_rq(), prev);
2819}
2820
2821/*
2822 * nr_running, nr_uninterruptible and nr_context_switches:
2823 *
2824 * externally visible scheduler statistics: current number of runnable
2825 * threads, current number of uninterruptible-sleeping threads, total
2826 * number of context switches performed since bootup.
2827 */
2828unsigned long nr_running(void)
2829{
2830        unsigned long i, sum = 0;
2831
2832        for_each_online_cpu(i)
2833                sum += cpu_rq(i)->nr_running;
2834
2835        return sum;
2836}
2837
2838unsigned long nr_uninterruptible(void)
2839{
2840        unsigned long i, sum = 0;
2841
2842        for_each_possible_cpu(i)
2843                sum += cpu_rq(i)->nr_uninterruptible;
2844
2845        /*
2846         * Since we read the counters lockless, it might be slightly
2847         * inaccurate. Do not allow it to go below zero though:
2848         */
2849        if (unlikely((long)sum < 0))
2850                sum = 0;
2851
2852        return sum;
2853}
2854
2855unsigned long long nr_context_switches(void)
2856{
2857        int i;
2858        unsigned long long sum = 0;
2859
2860        for_each_possible_cpu(i)
2861                sum += cpu_rq(i)->nr_switches;
2862
2863        return sum;
2864}
2865
2866unsigned long nr_iowait(void)
2867{
2868        unsigned long i, sum = 0;
2869
2870        for_each_possible_cpu(i)
2871                sum += atomic_read(&cpu_rq(i)->nr_iowait);
2872
2873        return sum;
2874}
2875
2876unsigned long nr_iowait_cpu(int cpu)
2877{
2878        struct rq *this = cpu_rq(cpu);
2879        return atomic_read(&this->nr_iowait);
2880}
2881
2882unsigned long this_cpu_load(void)
2883{
2884        struct rq *this = this_rq();
2885        return this->cpu_load[0];
2886}
2887
2888
2889/* Variables and functions for calc_load */
2890static atomic_long_t calc_load_tasks;
2891static unsigned long calc_load_update;
2892unsigned long avenrun[3];
2893EXPORT_SYMBOL(avenrun);
2894
2895static long calc_load_fold_active(struct rq *this_rq)
2896{
2897        long nr_active, delta = 0;
2898
2899        nr_active = this_rq->nr_running;
2900        nr_active += (long) this_rq->nr_uninterruptible;
2901
2902        if (nr_active != this_rq->calc_load_active) {
2903                delta = nr_active - this_rq->calc_load_active;
2904                this_rq->calc_load_active = nr_active;
2905        }
2906
2907        return delta;
2908}
2909
2910#ifdef CONFIG_NO_HZ
2911/*
2912 * For NO_HZ we delay the active fold to the next LOAD_FREQ update.
2913 *
2914 * When making the ILB scale, we should try to pull this in as well.
2915 */
2916static atomic_long_t calc_load_tasks_idle;
2917
2918static void calc_load_account_idle(struct rq *this_rq)
2919{
2920        long delta;
2921
2922        delta = calc_load_fold_active(this_rq);
2923        if (delta)
2924                atomic_long_add(delta, &calc_load_tasks_idle);
2925}
2926
2927static long calc_load_fold_idle(void)
2928{
2929        long delta = 0;
2930
2931        /*
2932         * Its got a race, we don't care...
2933         */
2934        if (atomic_long_read(&calc_load_tasks_idle))
2935                delta = atomic_long_xchg(&calc_load_tasks_idle, 0);
2936
2937        return delta;
2938}
2939#else
2940static void calc_load_account_idle(struct rq *this_rq)
2941{
2942}
2943
2944static inline long calc_load_fold_idle(void)
2945{
2946        return 0;
2947}
2948#endif
2949
2950/**
2951 * get_avenrun - get the load average array
2952 * @loads:      pointer to dest load array
2953 * @offset:     offset to add
2954 * @shift:      shift count to shift the result left
2955 *
2956 * These values are estimates at best, so no need for locking.
2957 */
2958void get_avenrun(unsigned long *loads, unsigned long offset, int shift)
2959{
2960        loads[0] = (avenrun[0] + offset) << shift;
2961        loads[1] = (avenrun[1] + offset) << shift;
2962        loads[2] = (avenrun[2] + offset) << shift;
2963}
2964
2965static unsigned long
2966calc_load(unsigned long load, unsigned long exp, unsigned long active)
2967{
2968        load *= exp;
2969        load += active * (FIXED_1 - exp);
2970        return load >> FSHIFT;
2971}
2972
2973/*
2974 * calc_load - update the avenrun load estimates 10 ticks after the
2975 * CPUs have updated calc_load_tasks.
2976 */
2977void calc_global_load(void)
2978{
2979        unsigned long upd = calc_load_update + 10;
2980        long active;
2981
2982        if (time_before(jiffies, upd))
2983                return;
2984
2985        active = atomic_long_read(&calc_load_tasks);
2986        active = active > 0 ? active * FIXED_1 : 0;
2987
2988        avenrun[0] = calc_load(avenrun[0], EXP_1, active);
2989        avenrun[1] = calc_load(avenrun[1], EXP_5, active);
2990        avenrun[2] = calc_load(avenrun[2], EXP_15, active);
2991
2992        calc_load_update += LOAD_FREQ;
2993}
2994
2995/*
2996 * Called from update_cpu_load() to periodically update this CPU's
2997 * active count.
2998 */
2999static void calc_load_account_active(struct rq *this_rq)
3000{
3001        long delta;
3002
3003        if (time_before(jiffies, this_rq->calc_load_update))
3004                return;
3005
3006        delta  = calc_load_fold_active(this_rq);
3007        delta += calc_load_fold_idle();
3008        if (delta)
3009                atomic_long_add(delta, &calc_load_tasks);
3010
3011        this_rq->calc_load_update += LOAD_FREQ;
3012}
3013
3014/*
3015 * Update rq->cpu_load[] statistics. This function is usually called every
3016 * scheduler tick (TICK_NSEC).
3017 */
3018static void update_cpu_load(struct rq *this_rq)
3019{
3020        unsigned long this_load = this_rq->load.weight;
3021        int i, scale;
3022
3023        this_rq->nr_load_updates++;
3024
3025        /* Update our load: */
3026        for (i = 0, scale = 1; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
3027                unsigned long old_load, new_load;
3028
3029                /* scale is effectively 1 << i now, and >> i divides by scale */
3030
3031                old_load = this_rq->cpu_load[i];
3032                new_load = this_load;
3033                /*
3034                 * Round up the averaging division if load is increasing. This
3035                 * prevents us from getting stuck on 9 if the load is 10, for
3036                 * example.
3037                 */
3038                if (new_load > old_load)
3039                        new_load += scale-1;
3040                this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
3041        }
3042
3043        calc_load_account_active(this_rq);
3044}
3045
3046#ifdef CONFIG_SMP
3047
3048/*
3049 * sched_exec - execve() is a valuable balancing opportunity, because at
3050 * this point the task has the smallest effective memory and cache footprint.
3051 */
3052void sched_exec(void)
3053{
3054        struct task_struct *p = current;
3055        unsigned long flags;
3056        struct rq *rq;
3057        int dest_cpu;
3058
3059        rq = task_rq_lock(p, &flags);
3060        dest_cpu = p->sched_class->select_task_rq(rq, p, SD_BALANCE_EXEC, 0);
3061        if (dest_cpu == smp_processor_id())
3062                goto unlock;
3063
3064        /*
3065         * select_task_rq() can race against ->cpus_allowed
3066         */
3067        if (cpumask_test_cpu(dest_cpu, &p->cpus_allowed) &&
3068            likely(cpu_active(dest_cpu)) && migrate_task(p, dest_cpu)) {
3069                struct migration_arg arg = { p, dest_cpu };
3070
3071                task_rq_unlock(rq, &flags);
3072                stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
3073                return;
3074        }
3075unlock:
3076        task_rq_unlock(rq, &flags);
3077}
3078
3079#endif
3080
3081DEFINE_PER_CPU(struct kernel_stat, kstat);
3082
3083EXPORT_PER_CPU_SYMBOL(kstat);
3084
3085/*
3086 * Return any ns on the sched_clock that have not yet been accounted in
3087 * @p in case that task is currently running.
3088 *
3089 * Called with task_rq_lock() held on @rq.
3090 */
3091static u64 do_task_delta_exec(struct task_struct *p, struct rq *rq)
3092{
3093        u64 ns = 0;
3094
3095        if (task_current(rq, p)) {
3096                update_rq_clock(rq);
3097                ns = rq->clock - p->se.exec_start;
3098                if ((s64)ns < 0)
3099                        ns = 0;
3100        }
3101
3102        return ns;
3103}
3104
3105unsigned long long task_delta_exec(struct task_struct *p)
3106{
3107        unsigned long flags;
3108        struct rq *rq;
3109        u64 ns = 0;
3110
3111        rq = task_rq_lock(p, &flags);
3112        ns = do_task_delta_exec(p, rq);
3113        task_rq_unlock(rq, &flags);
3114
3115        return ns;
3116}
3117
3118/*
3119 * Return accounted runtime for the task.
3120 * In case the task is currently running, return the runtime plus current's
3121 * pending runtime that have not been accounted yet.
3122 */
3123unsigned long long task_sched_runtime(struct task_struct *p)
3124{
3125        unsigned long flags;
3126        struct rq *rq;
3127        u64 ns = 0;
3128
3129        rq = task_rq_lock(p, &flags);
3130        ns = p->se.sum_exec_runtime + do_task_delta_exec(p, rq);
3131        task_rq_unlock(rq, &flags);
3132
3133        return ns;
3134}
3135
3136/*
3137 * Return sum_exec_runtime for the thread group.
3138 * In case the task is currently running, return the sum plus current's
3139 * pending runtime that have not been accounted yet.
3140 *
3141 * Note that the thread group might have other running tasks as well,
3142 * so the return value not includes other pending runtime that other
3143 * running tasks might have.
3144 */
3145unsigned long long thread_group_sched_runtime(struct task_struct *p)
3146{
3147        struct task_cputime totals;
3148        unsigned long flags;
3149        struct rq *rq;
3150        u64 ns;
3151
3152        rq = task_rq_lock(p, &flags);
3153        thread_group_cputime(p, &totals);
3154        ns = totals.sum_exec_runtime + do_task_delta_exec(p, rq);
3155        task_rq_unlock(rq, &flags);
3156
3157        return ns;
3158}
3159
3160/*
3161 * Account user cpu time to a process.
3162 * @p: the process that the cpu time gets accounted to
3163 * @cputime: the cpu time spent in user space since the last update
3164 * @cputime_scaled: cputime scaled by cpu frequency
3165 */
3166void account_user_time(struct task_struct *p, cputime_t cputime,
3167                       cputime_t cputime_scaled)
3168{
3169        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3170        cputime64_t tmp;
3171
3172        /* Add user time to process. */
3173        p->utime = cputime_add(p->utime, cputime);
3174        p->utimescaled = cputime_add(p->utimescaled, cputime_scaled);
3175        account_group_user_time(p, cputime);
3176
3177        /* Add user time to cpustat. */
3178        tmp = cputime_to_cputime64(cputime);
3179        if (TASK_NICE(p) > 0)
3180                cpustat->nice = cputime64_add(cpustat->nice, tmp);
3181        else
3182                cpustat->user = cputime64_add(cpustat->user, tmp);
3183
3184        cpuacct_update_stats(p, CPUACCT_STAT_USER, cputime);
3185        /* Account for user time used */
3186        acct_update_integrals(p);
3187}
3188
3189/*
3190 * Account guest cpu time to a process.
3191 * @p: the process that the cpu time gets accounted to
3192 * @cputime: the cpu time spent in virtual machine since the last update
3193 * @cputime_scaled: cputime scaled by cpu frequency
3194 */
3195static void account_guest_time(struct task_struct *p, cputime_t cputime,
3196                               cputime_t cputime_scaled)
3197{
3198        cputime64_t tmp;
3199        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3200
3201        tmp = cputime_to_cputime64(cputime);
3202
3203        /* Add guest time to process. */
3204        p->utime = cputime_add(p->utime, cputime);
3205        p->utimescaled = cputime_add(p->utimescaled, cputime_scaled);
3206        account_group_user_time(p, cputime);
3207        p->gtime = cputime_add(p->gtime, cputime);
3208
3209        /* Add guest time to cpustat. */
3210        if (TASK_NICE(p) > 0) {
3211                cpustat->nice = cputime64_add(cpustat->nice, tmp);
3212                cpustat->guest_nice = cputime64_add(cpustat->guest_nice, tmp);
3213        } else {
3214                cpustat->user = cputime64_add(cpustat->user, tmp);
3215                cpustat->guest = cputime64_add(cpustat->guest, tmp);
3216        }
3217}
3218
3219/*
3220 * Account system cpu time to a process.
3221 * @p: the process that the cpu time gets accounted to
3222 * @hardirq_offset: the offset to subtract from hardirq_count()
3223 * @cputime: the cpu time spent in kernel space since the last update
3224 * @cputime_scaled: cputime scaled by cpu frequency
3225 */
3226void account_system_time(struct task_struct *p, int hardirq_offset,
3227                         cputime_t cputime, cputime_t cputime_scaled)
3228{
3229        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3230        cputime64_t tmp;
3231
3232        if ((p->flags & PF_VCPU) && (irq_count() - hardirq_offset == 0)) {
3233                account_guest_time(p, cputime, cputime_scaled);
3234                return;
3235        }
3236
3237        /* Add system time to process. */
3238        p->stime = cputime_add(p->stime, cputime);
3239        p->stimescaled = cputime_add(p->stimescaled, cputime_scaled);
3240        account_group_system_time(p, cputime);
3241
3242        /* Add system time to cpustat. */
3243        tmp = cputime_to_cputime64(cputime);
3244        if (hardirq_count() - hardirq_offset)
3245                cpustat->irq = cputime64_add(cpustat->irq, tmp);
3246        else if (softirq_count())
3247                cpustat->softirq = cputime64_add(cpustat->softirq, tmp);
3248        else
3249                cpustat->system = cputime64_add(cpustat->system, tmp);
3250
3251        cpuacct_update_stats(p, CPUACCT_STAT_SYSTEM, cputime);
3252
3253        /* Account for system time used */
3254        acct_update_integrals(p);
3255}
3256
3257/*
3258 * Account for involuntary wait time.
3259 * @steal: the cpu time spent in involuntary wait
3260 */
3261void account_steal_time(cputime_t cputime)
3262{
3263        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3264        cputime64_t cputime64 = cputime_to_cputime64(cputime);
3265
3266        cpustat->steal = cputime64_add(cpustat->steal, cputime64);
3267}
3268
3269/*
3270 * Account for idle time.
3271 * @cputime: the cpu time spent in idle wait
3272 */
3273void account_idle_time(cputime_t cputime)
3274{
3275        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
3276        cputime64_t cputime64 = cputime_to_cputime64(cputime);
3277        struct rq *rq = this_rq();
3278
3279        if (atomic_read(&rq->nr_iowait) > 0)
3280                cpustat->iowait = cputime64_add(cpustat->iowait, cputime64);
3281        else
3282                cpustat->idle = cputime64_add(cpustat->idle, cputime64);
3283}
3284
3285#ifndef CONFIG_VIRT_CPU_ACCOUNTING
3286
3287/*
3288 * Account a single tick of cpu time.
3289 * @p: the process that the cpu time gets accounted to
3290 * @user_tick: indicates if the tick is a user or a system tick
3291 */
3292void account_process_tick(struct task_struct *p, int user_tick)
3293{
3294        cputime_t one_jiffy_scaled = cputime_to_scaled(cputime_one_jiffy);
3295        struct rq *rq = this_rq();
3296
3297        if (user_tick)
3298                account_user_time(p, cputime_one_jiffy, one_jiffy_scaled);
3299        else if ((p != rq->idle) || (irq_count() != HARDIRQ_OFFSET))
3300                account_system_time(p, HARDIRQ_OFFSET, cputime_one_jiffy,
3301                                    one_jiffy_scaled);
3302        else
3303                account_idle_time(cputime_one_jiffy);
3304}
3305
3306/*
3307 * Account multiple ticks of steal time.
3308 * @p: the process from which the cpu time has been stolen
3309 * @ticks: number of stolen ticks
3310 */
3311void account_steal_ticks(unsigned long ticks)
3312{
3313        account_steal_time(jiffies_to_cputime(ticks));
3314}
3315
3316/*
3317 * Account multiple ticks of idle time.
3318 * @ticks: number of stolen ticks
3319 */
3320void account_idle_ticks(unsigned long ticks)
3321{
3322        account_idle_time(jiffies_to_cputime(ticks));
3323}
3324
3325#endif
3326
3327/*
3328 * Use precise platform statistics if available:
3329 */
3330#ifdef CONFIG_VIRT_CPU_ACCOUNTING
3331void task_times(struct task_struct *p, cputime_t *ut, cputime_t *st)
3332{
3333        *ut = p->utime;
3334        *st = p->stime;
3335}
3336
3337void thread_group_times(struct task_struct *p, cputime_t *ut, cputime_t *st)
3338{
3339        struct task_cputime cputime;
3340
3341        thread_group_cputime(p, &cputime);
3342
3343        *ut = cputime.utime;
3344        *st = cputime.stime;
3345}
3346#else
3347
3348#ifndef nsecs_to_cputime
3349# define nsecs_to_cputime(__nsecs)      nsecs_to_jiffies(__nsecs)
3350#endif
3351
3352void task_times(struct task_struct *p, cputime_t *ut, cputime_t *st)
3353{
3354        cputime_t rtime, utime = p->utime, total = cputime_add(utime, p->stime);
3355
3356        /*
3357         * Use CFS's precise accounting:
3358         */
3359        rtime = nsecs_to_cputime(p->se.sum_exec_runtime);
3360
3361        if (total) {
3362                u64 temp;
3363
3364                temp = (u64)(rtime * utime);
3365                do_div(temp, total);
3366                utime = (cputime_t)temp;
3367        } else
3368                utime = rtime;
3369
3370        /*
3371         * Compare with previous values, to keep monotonicity:
3372         */
3373        p->prev_utime = max(p->prev_utime, utime);
3374        p->prev_stime = max(p->prev_stime, cputime_sub(rtime, p->prev_utime));
3375
3376        *ut = p->prev_utime;
3377        *st = p->prev_stime;
3378}
3379
3380/*
3381 * Must be called with siglock held.
3382 */
3383void thread_group_times(struct task_struct *p, cputime_t *ut, cputime_t *st)
3384{
3385        struct signal_struct *sig = p->signal;
3386        struct task_cputime cputime;
3387        cputime_t rtime, utime, total;
3388
3389        thread_group_cputime(p, &cputime);
3390
3391        total = cputime_add(cputime.utime, cputime.stime);
3392        rtime = nsecs_to_cputime(cputime.sum_exec_runtime);
3393
3394        if (total) {
3395                u64 temp;
3396
3397                temp = (u64)(rtime * cputime.utime);
3398                do_div(temp, total);
3399                utime = (cputime_t)temp;
3400        } else
3401                utime = rtime;
3402
3403        sig->prev_utime = max(sig->prev_utime, utime);
3404        sig->prev_stime = max(sig->prev_stime,
3405                              cputime_sub(rtime, sig->prev_utime));
3406
3407        *ut = sig->prev_utime;
3408        *st = sig->prev_stime;
3409}
3410#endif
3411
3412/*
3413 * This function gets called by the timer code, with HZ frequency.
3414 * We call it with interrupts disabled.
3415 *
3416 * It also gets called by the fork code, when changing the parent's
3417 * timeslices.
3418 */
3419void scheduler_tick(void)
3420{
3421        int cpu = smp_processor_id();
3422        struct rq *rq = cpu_rq(cpu);
3423        struct task_struct *curr = rq->curr;
3424
3425        sched_clock_tick();
3426
3427        raw_spin_lock(&rq->lock);
3428        update_rq_clock(rq);
3429        update_cpu_load(rq);
3430        curr->sched_class->task_tick(rq, curr, 0);
3431        raw_spin_unlock(&rq->lock);
3432
3433        perf_event_task_tick(curr);
3434
3435#ifdef CONFIG_SMP
3436        rq->idle_at_tick = idle_cpu(cpu);
3437        trigger_load_balance(rq, cpu);
3438#endif
3439}
3440
3441notrace unsigned long get_parent_ip(unsigned long addr)
3442{
3443        if (in_lock_functions(addr)) {
3444                addr = CALLER_ADDR2;
3445                if (in_lock_functions(addr))
3446                        addr = CALLER_ADDR3;
3447        }
3448        return addr;
3449}
3450
3451#if defined(CONFIG_PREEMPT) && (defined(CONFIG_DEBUG_PREEMPT) || \
3452                                defined(CONFIG_PREEMPT_TRACER))
3453
3454void __kprobes add_preempt_count(int val)
3455{
3456#ifdef CONFIG_DEBUG_PREEMPT
3457        /*
3458         * Underflow?
3459         */
3460        if (DEBUG_LOCKS_WARN_ON((preempt_count() < 0)))
3461                return;
3462#endif
3463        preempt_count() += val;
3464#ifdef CONFIG_DEBUG_PREEMPT
3465        /*
3466         * Spinlock count overflowing soon?
3467         */
3468        DEBUG_LOCKS_WARN_ON((preempt_count() & PREEMPT_MASK) >=
3469                                PREEMPT_MASK - 10);
3470#endif
3471        if (preempt_count() == val)
3472                trace_preempt_off(CALLER_ADDR0, get_parent_ip(CALLER_ADDR1));
3473}
3474EXPORT_SYMBOL(add_preempt_count);
3475
3476void __kprobes sub_preempt_count(int val)
3477{
3478#ifdef CONFIG_DEBUG_PREEMPT
3479        /*
3480         * Underflow?
3481         */
3482        if (DEBUG_LOCKS_WARN_ON(val > preempt_count()))
3483                return;
3484        /*
3485         * Is the spinlock portion underflowing?
3486         */
3487        if (DEBUG_LOCKS_WARN_ON((val < PREEMPT_MASK) &&
3488                        !(preempt_count() & PREEMPT_MASK)))
3489                return;
3490#endif
3491
3492        if (preempt_count() == val)
3493                trace_preempt_on(CALLER_ADDR0, get_parent_ip(CALLER_ADDR1));
3494        preempt_count() -= val;
3495}
3496EXPORT_SYMBOL(sub_preempt_count);
3497
3498#endif
3499
3500/*
3501 * Print scheduling while atomic bug:
3502 */
3503static noinline void __schedule_bug(struct task_struct *prev)
3504{
3505        struct pt_regs *regs = get_irq_regs();
3506
3507        printk(KERN_ERR "BUG: scheduling while atomic: %s/%d/0x%08x\n",
3508                prev->comm, prev->pid, preempt_count());
3509
3510        debug_show_held_locks(prev);
3511        print_modules();
3512        if (irqs_disabled())
3513                print_irqtrace_events(prev);
3514
3515        if (regs)
3516                show_regs(regs);
3517        else
3518                dump_stack();
3519}
3520
3521/*
3522 * Various schedule()-time debugging checks and statistics:
3523 */
3524static inline void schedule_debug(struct task_struct *prev)
3525{
3526        /*
3527         * Test if we are atomic. Since do_exit() needs to call into
3528         * schedule() atomically, we ignore that path for now.
3529         * Otherwise, whine if we are scheduling when we should not be.
3530         */
3531        if (unlikely(in_atomic_preempt_off() && !prev->exit_state))
3532                __schedule_bug(prev);
3533
3534        profile_hit(SCHED_PROFILING, __builtin_return_address(0));
3535
3536        schedstat_inc(this_rq(), sched_count);
3537#ifdef CONFIG_SCHEDSTATS
3538        if (unlikely(prev->lock_depth >= 0)) {
3539                schedstat_inc(this_rq(), bkl_count);
3540                schedstat_inc(prev, sched_info.bkl_count);
3541        }
3542#endif
3543}
3544
3545static void put_prev_task(struct rq *rq, struct task_struct *prev)
3546{
3547        if (prev->se.on_rq)
3548                update_rq_clock(rq);
3549        rq->skip_clock_update = 0;
3550        prev->sched_class->put_prev_task(rq, prev);
3551}
3552
3553/*
3554 * Pick up the highest-prio task:
3555 */
3556static inline struct task_struct *
3557pick_next_task(struct rq *rq)
3558{
3559        const struct sched_class *class;
3560        struct task_struct *p;
3561
3562        /*
3563         * Optimization: we know that if all tasks are in
3564         * the fair class we can call that function directly:
3565         */
3566        if (likely(rq->nr_running == rq->cfs.nr_running)) {
3567                p = fair_sched_class.pick_next_task(rq);
3568                if (likely(p))
3569                        return p;
3570        }
3571
3572        class = sched_class_highest;
3573        for ( ; ; ) {
3574                p = class->pick_next_task(rq);
3575                if (p)
3576                        return p;
3577                /*
3578                 * Will never be NULL as the idle class always
3579                 * returns a non-NULL p:
3580                 */
3581                class = class->next;
3582        }
3583}
3584
3585/*
3586 * schedule() is the main scheduler function.
3587 */
3588asmlinkage void __sched schedule(void)
3589{
3590        struct task_struct *prev, *next;
3591        unsigned long *switch_count;
3592        struct rq *rq;
3593        int cpu;
3594
3595need_resched:
3596        preempt_disable();
3597        cpu = smp_processor_id();
3598        rq = cpu_rq(cpu);
3599        rcu_note_context_switch(cpu);
3600        prev = rq->curr;
3601        switch_count = &prev->nivcsw;
3602
3603        release_kernel_lock(prev);
3604need_resched_nonpreemptible:
3605
3606        schedule_debug(prev);
3607
3608        if (sched_feat(HRTICK))
3609                hrtick_clear(rq);
3610
3611        raw_spin_lock_irq(&rq->lock);
3612        clear_tsk_need_resched(prev);
3613
3614        if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
3615                if (unlikely(signal_pending_state(prev->state, prev)))
3616                        prev->state = TASK_RUNNING;
3617                else
3618                        deactivate_task(rq, prev, DEQUEUE_SLEEP);
3619                switch_count = &prev->nvcsw;
3620        }
3621
3622        pre_schedule(rq, prev);
3623
3624        if (unlikely(!rq->nr_running))
3625                idle_balance(cpu, rq);
3626
3627        put_prev_task(rq, prev);
3628        next = pick_next_task(rq);
3629
3630        if (likely(prev != next)) {
3631                sched_info_switch(prev, next);
3632                perf_event_task_sched_out(prev, next);
3633
3634                rq->nr_switches++;
3635                rq->curr = next;
3636                ++*switch_count;
3637
3638                context_switch(rq, prev, next); /* unlocks the rq */
3639                /*
3640                 * the context switch might have flipped the stack from under
3641                 * us, hence refresh the local variables.
3642                 */
3643                cpu = smp_processor_id();
3644                rq = cpu_rq(cpu);
3645        } else
3646                raw_spin_unlock_irq(&rq->lock);
3647
3648        post_schedule(rq);
3649
3650        if (unlikely(reacquire_kernel_lock(current) < 0)) {
3651                prev = rq->curr;
3652                switch_count = &prev->nivcsw;
3653                goto need_resched_nonpreemptible;
3654        }
3655
3656        preempt_enable_no_resched();
3657        if (need_resched())
3658                goto need_resched;
3659}
3660EXPORT_SYMBOL(schedule);
3661
3662#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
3663/*
3664 * Look out! "owner" is an entirely speculative pointer
3665 * access and not reliable.
3666 */
3667int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
3668{
3669        unsigned int cpu;
3670        struct rq *rq;
3671
3672        if (!sched_feat(OWNER_SPIN))
3673                return 0;
3674
3675#ifdef CONFIG_DEBUG_PAGEALLOC
3676        /*
3677         * Need to access the cpu field knowing that
3678         * DEBUG_PAGEALLOC could have unmapped it if
3679         * the mutex owner just released it and exited.
3680         */
3681        if (probe_kernel_address(&owner->cpu, cpu))
3682                return 0;
3683#else
3684        cpu = owner->cpu;
3685#endif
3686
3687        /*
3688         * Even if the access succeeded (likely case),
3689         * the cpu field may no longer be valid.
3690         */
3691        if (cpu >= nr_cpumask_bits)
3692                return 0;
3693
3694        /*
3695         * We need to validate that we can do a
3696         * get_cpu() and that we have the percpu area.
3697         */
3698        if (!cpu_online(cpu))
3699                return 0;
3700
3701        rq = cpu_rq(cpu);
3702
3703        for (;;) {
3704                /*
3705                 * Owner changed, break to re-assess state.
3706                 */
3707                if (lock->owner != owner)
3708                        break;
3709
3710                /*
3711                 * Is that owner really running on that cpu?
3712                 */
3713                if (task_thread_info(rq->curr) != owner || need_resched())
3714                        return 0;
3715
3716                cpu_relax();
3717        }
3718
3719        return 1;
3720}
3721#endif
3722
3723#ifdef CONFIG_PREEMPT
3724/*
3725 * this is the entry point to schedule() from in-kernel preemption
3726 * off of preempt_enable. Kernel preemptions off return from interrupt
3727 * occur there and call schedule directly.
3728 */
3729asmlinkage void __sched preempt_schedule(void)
3730{
3731        struct thread_info *ti = current_thread_info();
3732
3733        /*
3734         * If there is a non-zero preempt_count or interrupts are disabled,
3735         * we do not want to preempt the current task. Just return..
3736         */
3737        if (likely(ti->preempt_count || irqs_disabled()))
3738                return;
3739
3740        do {
3741                add_preempt_count(PREEMPT_ACTIVE);
3742                schedule();
3743                sub_preempt_count(PREEMPT_ACTIVE);
3744
3745                /*
3746                 * Check again in case we missed a preemption opportunity
3747                 * between schedule and now.
3748                 */
3749                barrier();
3750        } while (need_resched());
3751}
3752EXPORT_SYMBOL(preempt_schedule);
3753
3754/*
3755 * this is the entry point to schedule() from kernel preemption
3756 * off of irq context.
3757 * Note, that this is called and return with irqs disabled. This will
3758 * protect us against recursive calling from irq.
3759 */
3760asmlinkage void __sched preempt_schedule_irq(void)
3761{
3762        struct thread_info *ti = current_thread_info();
3763
3764        /* Catch callers which need to be fixed */
3765        BUG_ON(ti->preempt_count || !irqs_disabled());
3766
3767        do {
3768                add_preempt_count(PREEMPT_ACTIVE);
3769                local_irq_enable();
3770                schedule();
3771                local_irq_disable();
3772                sub_preempt_count(PREEMPT_ACTIVE);
3773
3774                /*
3775                 * Check again in case we missed a preemption opportunity
3776                 * between schedule and now.
3777                 */
3778                barrier();
3779        } while (need_resched());
3780}
3781
3782#endif /* CONFIG_PREEMPT */
3783
3784int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
3785                          void *key)
3786{
3787        return try_to_wake_up(curr->private, mode, wake_flags);
3788}
3789EXPORT_SYMBOL(default_wake_function);
3790
3791/*
3792 * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
3793 * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
3794 * number) then we wake all the non-exclusive tasks and one exclusive task.
3795 *
3796 * There are circumstances in which we can try to wake a task which has already
3797 * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
3798 * zero in this (rare) case, and we handle it by continuing to scan the queue.
3799 */
3800static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
3801                        int nr_exclusive, int wake_flags, void *key)
3802{
3803        wait_queue_t *curr, *next;
3804
3805        list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
3806                unsigned flags = curr->flags;
3807
3808                if (curr->func(curr, mode, wake_flags, key) &&
3809                                (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
3810                        break;
3811        }
3812}
3813
3814/**
3815 * __wake_up - wake up threads blocked on a waitqueue.
3816 * @q: the waitqueue
3817 * @mode: which threads
3818 * @nr_exclusive: how many wake-one or wake-many threads to wake up
3819 * @key: is directly passed to the wakeup function
3820 *
3821 * It may be assumed that this function implies a write memory barrier before
3822 * changing the task state if and only if any tasks are woken up.
3823 */
3824void __wake_up(wait_queue_head_t *q, unsigned int mode,
3825                        int nr_exclusive, void *key)
3826{
3827        unsigned long flags;
3828
3829        spin_lock_irqsave(&q->lock, flags);
3830        __wake_up_common(q, mode, nr_exclusive, 0, key);
3831        spin_unlock_irqrestore(&q->lock, flags);
3832}
3833EXPORT_SYMBOL(__wake_up);
3834
3835/*
3836 * Same as __wake_up but called with the spinlock in wait_queue_head_t held.
3837 */
3838void __wake_up_locked(wait_queue_head_t *q, unsigned int mode)
3839{
3840        __wake_up_common(q, mode, 1, 0, NULL);
3841}
3842EXPORT_SYMBOL_GPL(__wake_up_locked);
3843
3844void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)
3845{
3846        __wake_up_common(q, mode, 1, 0, key);
3847}
3848
3849/**
3850 * __wake_up_sync_key - wake up threads blocked on a waitqueue.
3851 * @q: the waitqueue
3852 * @mode: which threads
3853 * @nr_exclusive: how many wake-one or wake-many threads to wake up
3854 * @key: opaque value to be passed to wakeup targets
3855 *
3856 * The sync wakeup differs that the waker knows that it will schedule
3857 * away soon, so while the target thread will be woken up, it will not
3858 * be migrated to another CPU - ie. the two threads are 'synchronized'
3859 * with each other. This can prevent needless bouncing between CPUs.
3860 *
3861 * On UP it can prevent extra preemption.
3862 *
3863 * It may be assumed that this function implies a write memory barrier before
3864 * changing the task state if and only if any tasks are woken up.
3865 */
3866void __wake_up_sync_key(wait_queue_head_t *q, unsigned int mode,
3867                        int nr_exclusive, void *key)
3868{
3869        unsigned long flags;
3870        int wake_flags = WF_SYNC;
3871
3872        if (unlikely(!q))
3873                return;
3874
3875        if (unlikely(!nr_exclusive))
3876                wake_flags = 0;
3877
3878        spin_lock_irqsave(&q->lock, flags);
3879        __wake_up_common(q, mode, nr_exclusive, wake_flags, key);
3880        spin_unlock_irqrestore(&q->lock, flags);
3881}
3882EXPORT_SYMBOL_GPL(__wake_up_sync_key);
3883
3884/*
3885 * __wake_up_sync - see __wake_up_sync_key()
3886 */
3887void __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
3888{
3889        __wake_up_sync_key(q, mode, nr_exclusive, NULL);
3890}
3891EXPORT_SYMBOL_GPL(__wake_up_sync);      /* For internal use only */
3892
3893/**
3894 * complete: - signals a single thread waiting on this completion
3895 * @x:  holds the state of this particular completion
3896 *
3897 * This will wake up a single thread waiting on this completion. Threads will be
3898 * awakened in the same order in which they were queued.
3899 *
3900 * See also complete_all(), wait_for_completion() and related routines.
3901 *
3902 * It may be assumed that this function implies a write memory barrier before
3903 * changing the task state if and only if any tasks are woken up.
3904 */
3905void complete(struct completion *x)
3906{
3907        unsigned long flags;
3908
3909        spin_lock_irqsave(&x->wait.lock, flags);
3910        x->done++;
3911        __wake_up_common(&x->wait, TASK_NORMAL, 1, 0, NULL);
3912        spin_unlock_irqrestore(&x->wait.lock, flags);
3913}
3914EXPORT_SYMBOL(complete);
3915
3916/**
3917 * complete_all: - signals all threads waiting on this completion
3918 * @x:  holds the state of this particular completion
3919 *
3920 * This will wake up all threads waiting on this particular completion event.
3921 *
3922 * It may be assumed that this function implies a write memory barrier before
3923 * changing the task state if and only if any tasks are woken up.
3924 */
3925void complete_all(struct completion *x)
3926{
3927        unsigned long flags;
3928
3929        spin_lock_irqsave(&x->wait.lock, flags);
3930        x->done += UINT_MAX/2;
3931        __wake_up_common(&x->wait, TASK_NORMAL, 0, 0, NULL);
3932        spin_unlock_irqrestore(&x->wait.lock, flags);
3933}
3934EXPORT_SYMBOL(complete_all);
3935
3936static inline long __sched
3937do_wait_for_common(struct completion *x, long timeout, int state)
3938{
3939        if (!x->done) {
3940                DECLARE_WAITQUEUE(wait, current);
3941
3942                __add_wait_queue_tail_exclusive(&x->wait, &wait);
3943                do {
3944                        if (signal_pending_state(state, current)) {
3945                                timeout = -ERESTARTSYS;
3946                                break;
3947                        }
3948                        __set_current_state(state);
3949                        spin_unlock_irq(&x->wait.lock);
3950                        timeout = schedule_timeout(timeout);
3951                        spin_lock_irq(&x->wait.lock);
3952                } while (!x->done && timeout);
3953                __remove_wait_queue(&x->wait, &wait);
3954                if (!x->done)
3955                        return timeout;
3956        }
3957        x->done--;
3958        return timeout ?: 1;
3959}
3960
3961static long __sched
3962wait_for_common(struct completion *x, long timeout, int state)
3963{
3964        might_sleep();
3965
3966        spin_lock_irq(&x->wait.lock);
3967        timeout = do_wait_for_common(x, timeout, state);
3968        spin_unlock_irq(&x->wait.lock);
3969        return timeout;
3970}
3971
3972/**
3973 * wait_for_completion: - waits for completion of a task
3974 * @x:  holds the state of this particular completion
3975 *
3976 * This waits to be signaled for completion of a specific task. It is NOT
3977 * interruptible and there is no timeout.
3978 *
3979 * See also similar routines (i.e. wait_for_completion_timeout()) with timeout
3980 * and interrupt capability. Also see complete().
3981 */
3982void __sched wait_for_completion(struct completion *x)
3983{
3984        wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_UNINTERRUPTIBLE);
3985}
3986EXPORT_SYMBOL(wait_for_completion);
3987
3988/**
3989 * wait_for_completion_timeout: - waits for completion of a task (w/timeout)
3990 * @x:  holds the state of this particular completion
3991 * @timeout:  timeout value in jiffies
3992 *
3993 * This waits for either a completion of a specific task to be signaled or for a
3994 * specified timeout to expire. The timeout is in jiffies. It is not
3995 * interruptible.
3996 */
3997unsigned long __sched
3998wait_for_completion_timeout(struct completion *x, unsigned long timeout)
3999{
4000        return wait_for_common(x, timeout, TASK_UNINTERRUPTIBLE);
4001}
4002EXPORT_SYMBOL(wait_for_completion_timeout);
4003
4004/**
4005 * wait_for_completion_interruptible: - waits for completion of a task (w/intr)
4006 * @x:  holds the state of this particular completion
4007 *
4008 * This waits for completion of a specific task to be signaled. It is
4009 * interruptible.
4010 */
4011int __sched wait_for_completion_interruptible(struct completion *x)
4012{
4013        long t = wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_INTERRUPTIBLE);
4014        if (t == -ERESTARTSYS)
4015                return t;
4016        return 0;
4017}
4018EXPORT_SYMBOL(wait_for_completion_interruptible);
4019
4020/**
4021 * wait_for_completion_interruptible_timeout: - waits for completion (w/(to,intr))
4022 * @x:  holds the state of this particular completion
4023 * @timeout:  timeout value in jiffies
4024 *
4025 * This waits for either a completion of a specific task to be signaled or for a
4026 * specified timeout to expire. It is interruptible. The timeout is in jiffies.
4027 */
4028unsigned long __sched
4029wait_for_completion_interruptible_timeout(struct completion *x,
4030                                          unsigned long timeout)
4031{
4032        return wait_for_common(x, timeout, TASK_INTERRUPTIBLE);
4033}
4034EXPORT_SYMBOL(wait_for_completion_interruptible_timeout);
4035
4036/**
4037 * wait_for_completion_killable: - waits for completion of a task (killable)
4038 * @x:  holds the state of this particular completion
4039 *
4040 * This waits to be signaled for completion of a specific task. It can be
4041 * interrupted by a kill signal.
4042 */
4043int __sched wait_for_completion_killable(struct completion *x)
4044{
4045        long t = wait_for_common(x, MAX_SCHEDULE_TIMEOUT, TASK_KILLABLE);
4046        if (t == -ERESTARTSYS)
4047                return t;
4048        return 0;
4049}
4050EXPORT_SYMBOL(wait_for_completion_killable);
4051
4052/**
4053 * wait_for_completion_killable_timeout: - waits for completion of a task (w/(to,killable))
4054 * @x:  holds the state of this particular completion
4055 * @timeout:  timeout value in jiffies
4056 *
4057 * This waits for either a completion of a specific task to be
4058 * signaled or for a specified timeout to expire. It can be
4059 * interrupted by a kill signal. The timeout is in jiffies.
4060 */
4061unsigned long __sched
4062wait_for_completion_killable_timeout(struct completion *x,
4063                                     unsigned long timeout)
4064{
4065        return wait_for_common(x, timeout, TASK_KILLABLE);
4066}
4067EXPORT_SYMBOL(wait_for_completion_killable_timeout);
4068
4069/**
4070 *      try_wait_for_completion - try to decrement a completion without blocking
4071 *      @x:     completion structure
4072 *
4073 *      Returns: 0 if a decrement cannot be done without blocking
4074 *               1 if a decrement succeeded.
4075 *
4076 *      If a completion is being used as a counting completion,
4077 *      attempt to decrement the counter without blocking. This
4078 *      enables us to avoid waiting if the resource the completion
4079 *      is protecting is not available.
4080 */
4081bool try_wait_for_completion(struct completion *x)
4082{
4083        unsigned long flags;
4084        int ret = 1;
4085
4086        spin_lock_irqsave(&x->wait.lock, flags);
4087        if (!x->done)
4088                ret = 0;
4089        else
4090                x->done--;
4091        spin_unlock_irqrestore(&x->wait.lock, flags);
4092        return ret;
4093}
4094EXPORT_SYMBOL(try_wait_for_completion);
4095
4096/**
4097 *      completion_done - Test to see if a completion has any waiters
4098 *      @x:     completion structure
4099 *
4100 *      Returns: 0 if there are waiters (wait_for_completion() in progress)
4101 *               1 if there are no waiters.
4102 *
4103 */
4104bool completion_done(struct completion *x)
4105{
4106        unsigned long flags;
4107        int ret = 1;
4108
4109        spin_lock_irqsave(&x->wait.lock, flags);
4110        if (!x->done)
4111                ret = 0;
4112        spin_unlock_irqrestore(&x->wait.lock, flags);
4113        return ret;
4114}
4115EXPORT_SYMBOL(completion_done);
4116
4117static long __sched
4118sleep_on_common(wait_queue_head_t *q, int state, long timeout)
4119{
4120        unsigned long flags;
4121        wait_queue_t wait;
4122
4123        init_waitqueue_entry(&wait, current);
4124
4125        __set_current_state(state);
4126
4127        spin_lock_irqsave(&q->lock, flags);
4128        __add_wait_queue(q, &wait);
4129        spin_unlock(&q->lock);
4130        timeout = schedule_timeout(timeout);
4131        spin_lock_irq(&q->lock);
4132        __remove_wait_queue(q, &wait);
4133        spin_unlock_irqrestore(&q->lock, flags);
4134
4135        return timeout;
4136}
4137
4138void __sched interruptible_sleep_on(wait_queue_head_t *q)
4139{
4140        sleep_on_common(q, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
4141}
4142EXPORT_SYMBOL(interruptible_sleep_on);
4143
4144long __sched
4145interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
4146{
4147        return sleep_on_common(q, TASK_INTERRUPTIBLE, timeout);
4148}
4149EXPORT_SYMBOL(interruptible_sleep_on_timeout);
4150
4151void __sched sleep_on(wait_queue_head_t *q)
4152{
4153        sleep_on_common(q, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
4154}
4155EXPORT_SYMBOL(sleep_on);
4156
4157long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
4158{
4159        return sleep_on_common(q, TASK_UNINTERRUPTIBLE, timeout);
4160}
4161EXPORT_SYMBOL(sleep_on_timeout);
4162
4163#ifdef CONFIG_RT_MUTEXES
4164
4165/*
4166 * rt_mutex_setprio - set the current priority of a task
4167 * @p: task
4168 * @prio: prio value (kernel-internal form)
4169 *
4170 * This function changes the 'effective' priority of a task. It does
4171 * not touch ->normal_prio like __setscheduler().
4172 *
4173 * Used by the rt_mutex code to implement priority inheritance logic.
4174 */
4175void rt_mutex_setprio(struct task_struct *p, int prio)
4176{
4177        unsigned long flags;
4178        int oldprio, on_rq, running;
4179        struct rq *rq;
4180        const struct sched_class *prev_class;
4181
4182        BUG_ON(prio < 0 || prio > MAX_PRIO);
4183
4184        rq = task_rq_lock(p, &flags);
4185
4186        oldprio = p->prio;
4187        prev_class = p->sched_class;
4188        on_rq = p->se.on_rq;
4189        running = task_current(rq, p);
4190        if (on_rq)
4191                dequeue_task(rq, p, 0);
4192        if (running)
4193                p->sched_class->put_prev_task(rq, p);
4194
4195        if (rt_prio(prio))
4196                p->sched_class = &rt_sched_class;
4197        else
4198                p->sched_class = &fair_sched_class;
4199
4200        p->prio = prio;
4201
4202        if (running)
4203                p->sched_class->set_curr_task(rq);
4204        if (on_rq) {
4205                enqueue_task(rq, p, oldprio < prio ? ENQUEUE_HEAD : 0);
4206
4207                check_class_changed(rq, p, prev_class, oldprio, running);
4208        }
4209        task_rq_unlock(rq, &flags);
4210}
4211
4212#endif
4213
4214void set_user_nice(struct task_struct *p, long nice)
4215{
4216        int old_prio, delta, on_rq;
4217        unsigned long flags;
4218        struct rq *rq;
4219
4220        if (TASK_NICE(p) == nice || nice < -20 || nice > 19)
4221                return;
4222        /*
4223         * We have to be careful, if called from sys_setpriority(),
4224         * the task might be in the middle of scheduling on another CPU.
4225         */
4226        rq = task_rq_lock(p, &flags);
4227        /*
4228         * The RT priorities are set via sched_setscheduler(), but we still
4229         * allow the 'normal' nice value to be set - but as expected
4230         * it wont have any effect on scheduling until the task is
4231         * SCHED_FIFO/SCHED_RR:
4232         */
4233        if (task_has_rt_policy(p)) {
4234                p->static_prio = NICE_TO_PRIO(nice);
4235                goto out_unlock;
4236        }
4237        on_rq = p->se.on_rq;
4238        if (on_rq)
4239                dequeue_task(rq, p, 0);
4240
4241        p->static_prio = NICE_TO_PRIO(nice);
4242        set_load_weight(p);
4243        old_prio = p->prio;
4244        p->prio = effective_prio(p);
4245        delta = p->prio - old_prio;
4246
4247        if (on_rq) {
4248                enqueue_task(rq, p, 0);
4249                /*
4250                 * If the task increased its priority or is running and
4251                 * lowered its priority, then reschedule its CPU:
4252                 */
4253                if (delta < 0 || (delta > 0 && task_running(rq, p)))
4254                        resched_task(rq->curr);
4255        }
4256out_unlock:
4257        task_rq_unlock(rq, &flags);
4258}
4259EXPORT_SYMBOL(set_user_nice);
4260
4261/*
4262 * can_nice - check if a task can reduce its nice value
4263 * @p: task
4264 * @nice: nice value
4265 */
4266int can_nice(const struct task_struct *p, const int nice)
4267{
4268        /* convert nice value [19,-20] to rlimit style value [1,40] */
4269        int nice_rlim = 20 - nice;
4270
4271        return (nice_rlim <= task_rlimit(p, RLIMIT_NICE) ||
4272                capable(CAP_SYS_NICE));
4273}
4274
4275#ifdef __ARCH_WANT_SYS_NICE
4276
4277/*
4278 * sys_nice - change the priority of the current process.
4279 * @increment: priority increment
4280 *
4281 * sys_setpriority is a more generic, but much slower function that
4282 * does similar things.
4283 */
4284SYSCALL_DEFINE1(nice, int, increment)
4285{
4286        long nice, retval;
4287
4288        /*
4289         * Setpriority might change our priority at the same moment.
4290         * We don't have to worry. Conceptually one call occurs first
4291         * and we have a single winner.
4292         */
4293        if (increment < -40)
4294                increment = -40;
4295        if (increment > 40)
4296                increment = 40;
4297
4298        nice = TASK_NICE(current) + increment;
4299        if (nice < -20)
4300                nice = -20;
4301        if (nice > 19)
4302                nice = 19;
4303
4304        if (increment < 0 && !can_nice(current, nice))
4305                return -EPERM;
4306
4307        retval = security_task_setnice(current, nice);
4308        if (retval)
4309                return retval;
4310
4311        set_user_nice(current, nice);
4312        return 0;
4313}
4314
4315#endif
4316
4317/**
4318 * task_prio - return the priority value of a given task.
4319 * @p: the task in question.
4320 *
4321 * This is the priority value as seen by users in /proc.
4322 * RT tasks are offset by -200. Normal tasks are centered
4323 * around 0, value goes from -16 to +15.
4324 */
4325int task_prio(const struct task_struct *p)
4326{
4327        return p->prio - MAX_RT_PRIO;
4328}
4329
4330/**
4331 * task_nice - return the nice value of a given task.
4332 * @p: the task in question.
4333 */
4334int task_nice(const struct task_struct *p)
4335{
4336        return TASK_NICE(p);
4337}
4338EXPORT_SYMBOL(task_nice);
4339
4340/**
4341 * idle_cpu - is a given cpu idle currently?
4342 * @cpu: the processor in question.
4343 */
4344int idle_cpu(int cpu)
4345{
4346        return cpu_curr(cpu) == cpu_rq(cpu)->idle;
4347}
4348
4349/**
4350 * idle_task - return the idle task for a given cpu.
4351 * @cpu: the processor in question.
4352 */
4353struct task_struct *idle_task(int cpu)
4354{
4355        return cpu_rq(cpu)->idle;
4356}
4357
4358/**
4359 * find_process_by_pid - find a process with a matching PID value.
4360 * @pid: the pid in question.
4361 */
4362static struct task_struct *find_process_by_pid(pid_t pid)
4363{
4364        return pid ? find_task_by_vpid(pid) : current;
4365}
4366
4367/* Actually do priority change: must hold rq lock. */
4368static void
4369__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
4370{
4371        BUG_ON(p->se.on_rq);
4372
4373        p->policy = policy;
4374        p->rt_priority = prio;
4375        p->normal_prio = normal_prio(p);
4376        /* we are holding p->pi_lock already */
4377        p->prio = rt_mutex_getprio(p);
4378        if (rt_prio(p->prio))
4379                p->sched_class = &rt_sched_class;
4380        else
4381                p->sched_class = &fair_sched_class;
4382        set_load_weight(p);
4383}
4384
4385/*
4386 * check the target process has a UID that matches the current process's
4387 */
4388static bool check_same_owner(struct task_struct *p)
4389{
4390        const struct cred *cred = current_cred(), *pcred;
4391        bool match;
4392
4393        rcu_read_lock();
4394        pcred = __task_cred(p);
4395        match = (cred->euid == pcred->euid ||
4396                 cred->euid == pcred->uid);
4397        rcu_read_unlock();
4398        return match;
4399}
4400
4401static int __sched_setscheduler(struct task_struct *p, int policy,
4402                                struct sched_param *param, bool user)
4403{
4404        int retval, oldprio, oldpolicy = -1, on_rq, running;
4405        unsigned long flags;
4406        const struct sched_class *prev_class;
4407        struct rq *rq;
4408        int reset_on_fork;
4409
4410        /* may grab non-irq protected spin_locks */
4411        BUG_ON(in_interrupt());
4412recheck:
4413        /* double check policy once rq lock held */
4414        if (policy < 0) {
4415                reset_on_fork = p->sched_reset_on_fork;
4416                policy = oldpolicy = p->policy;
4417        } else {
4418                reset_on_fork = !!(policy & SCHED_RESET_ON_FORK);
4419                policy &= ~SCHED_RESET_ON_FORK;
4420
4421                if (policy != SCHED_FIFO && policy != SCHED_RR &&
4422                                policy != SCHED_NORMAL && policy != SCHED_BATCH &&
4423                                policy != SCHED_IDLE)
4424                        return -EINVAL;
4425        }
4426
4427        /*
4428         * Valid priorities for SCHED_FIFO and SCHED_RR are
4429         * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
4430         * SCHED_BATCH and SCHED_IDLE is 0.
4431         */
4432        if (param->sched_priority < 0 ||
4433            (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
4434            (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
4435                return -EINVAL;
4436        if (rt_policy(policy) != (param->sched_priority != 0))
4437                return -EINVAL;
4438
4439        /*
4440         * Allow unprivileged RT tasks to decrease priority:
4441         */
4442        if (user && !capable(CAP_SYS_NICE)) {
4443                if (rt_policy(policy)) {
4444                        unsigned long rlim_rtprio;
4445
4446                        if (!lock_task_sighand(p, &flags))
4447                                return -ESRCH;
4448                        rlim_rtprio = task_rlimit(p, RLIMIT_RTPRIO);
4449                        unlock_task_sighand(p, &flags);
4450
4451                        /* can't set/change the rt policy */
4452                        if (policy != p->policy && !rlim_rtprio)
4453                                return -EPERM;
4454
4455                        /* can't increase priority */
4456                        if (param->sched_priority > p->rt_priority &&
4457                            param->sched_priority > rlim_rtprio)
4458                                return -EPERM;
4459                }
4460                /*
4461                 * Like positive nice levels, dont allow tasks to
4462                 * move out of SCHED_IDLE either:
4463                 */
4464                if (p->policy == SCHED_IDLE && policy != SCHED_IDLE)
4465                        return -EPERM;
4466
4467                /* can't change other user's priorities */
4468                if (!check_same_owner(p))
4469                        return -EPERM;
4470
4471                /* Normal users shall not reset the sched_reset_on_fork flag */
4472                if (p->sched_reset_on_fork && !reset_on_fork)
4473                        return -EPERM;
4474        }
4475
4476        if (user) {
4477                retval = security_task_setscheduler(p, policy, param);
4478                if (retval)
4479                        return retval;
4480        }
4481
4482        /*
4483         * make sure no PI-waiters arrive (or leave) while we are
4484         * changing the priority of the task:
4485         */
4486        raw_spin_lock_irqsave(&p->pi_lock, flags);
4487        /*
4488         * To be able to change p->policy safely, the apropriate
4489         * runqueue lock must be held.
4490         */
4491        rq = __task_rq_lock(p);
4492
4493#ifdef CONFIG_RT_GROUP_SCHED
4494        if (user) {
4495                /*
4496                 * Do not allow realtime tasks into groups that have no runtime
4497                 * assigned.
4498                 */
4499                if (rt_bandwidth_enabled() && rt_policy(policy) &&
4500                                task_group(p)->rt_bandwidth.rt_runtime == 0) {
4501                        __task_rq_unlock(rq);
4502                        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
4503                        return -EPERM;
4504                }
4505        }
4506#endif
4507
4508        /* recheck policy now with rq lock held */
4509        if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
4510                policy = oldpolicy = -1;
4511                __task_rq_unlock(rq);
4512                raw_spin_unlock_irqrestore(&p->pi_lock, flags);
4513                goto recheck;
4514        }
4515        on_rq = p->se.on_rq;
4516        running = task_current(rq, p);
4517        if (on_rq)
4518                deactivate_task(rq, p, 0);
4519        if (running)
4520                p->sched_class->put_prev_task(rq, p);
4521
4522        p->sched_reset_on_fork = reset_on_fork;
4523
4524        oldprio = p->prio;
4525        prev_class = p->sched_class;
4526        __setscheduler(rq, p, policy, param->sched_priority);
4527
4528        if (running)
4529                p->sched_class->set_curr_task(rq);
4530        if (on_rq) {
4531                activate_task(rq, p, 0);
4532
4533                check_class_changed(rq, p, prev_class, oldprio, running);
4534        }
4535        __task_rq_unlock(rq);
4536        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
4537
4538        rt_mutex_adjust_pi(p);
4539
4540        return 0;
4541}
4542
4543/**
4544 * sched_setscheduler - change the scheduling policy and/or RT priority of a thread.
4545 * @p: the task in question.
4546 * @policy: new policy.
4547 * @param: structure containing the new RT priority.
4548 *
4549 * NOTE that the task may be already dead.
4550 */
4551int sched_setscheduler(struct task_struct *p, int policy,
4552                       struct sched_param *param)
4553{
4554        return __sched_setscheduler(p, policy, param, true);
4555}
4556EXPORT_SYMBOL_GPL(sched_setscheduler);
4557
4558/**
4559 * sched_setscheduler_nocheck - change the scheduling policy and/or RT priority of a thread from kernelspace.
4560 * @p: the task in question.
4561 * @policy: new policy.
4562 * @param: structure containing the new RT priority.
4563 *
4564 * Just like sched_setscheduler, only don't bother checking if the
4565 * current context has permission.  For example, this is needed in
4566 * stop_machine(): we create temporary high priority worker threads,
4567 * but our caller might not have that capability.
4568 */
4569int sched_setscheduler_nocheck(struct task_struct *p, int policy,
4570                               struct sched_param *param)
4571{
4572        return __sched_setscheduler(p, policy, param, false);
4573}
4574
4575static int
4576do_sched_setscheduler(pid_t pid, int policy, struct sched_param __user *param)
4577{
4578        struct sched_param lparam;
4579        struct task_struct *p;
4580        int retval;
4581
4582        if (!param || pid < 0)
4583                return -EINVAL;
4584        if (copy_from_user(&lparam, param, sizeof(struct sched_param)))
4585                return -EFAULT;
4586
4587        rcu_read_lock();
4588        retval = -ESRCH;
4589        p = find_process_by_pid(pid);
4590        if (p != NULL)
4591                retval = sched_setscheduler(p, policy, &lparam);
4592        rcu_read_unlock();
4593
4594        return retval;
4595}
4596
4597/**
4598 * sys_sched_setscheduler - set/change the scheduler policy and RT priority
4599 * @pid: the pid in question.
4600 * @policy: new policy.
4601 * @param: structure containing the new RT priority.
4602 */
4603SYSCALL_DEFINE3(sched_setscheduler, pid_t, pid, int, policy,
4604                struct sched_param __user *, param)
4605{
4606        /* negative values for policy are not valid */
4607        if (policy < 0)
4608                return -EINVAL;
4609
4610        return do_sched_setscheduler(pid, policy, param);
4611}
4612
4613/**
4614 * sys_sched_setparam - set/change the RT priority of a thread
4615 * @pid: the pid in question.
4616 * @param: structure containing the new RT priority.
4617 */
4618SYSCALL_DEFINE2(sched_setparam, pid_t, pid, struct sched_param __user *, param)
4619{
4620        return do_sched_setscheduler(pid, -1, param);
4621}
4622
4623/**
4624 * sys_sched_getscheduler - get the policy (scheduling class) of a thread
4625 * @pid: the pid in question.
4626 */
4627SYSCALL_DEFINE1(sched_getscheduler, pid_t, pid)
4628{
4629        struct task_struct *p;
4630        int retval;
4631
4632        if (pid < 0)
4633                return -EINVAL;
4634
4635        retval = -ESRCH;
4636        rcu_read_lock();
4637        p = find_process_by_pid(pid);
4638        if (p) {
4639                retval = security_task_getscheduler(p);
4640                if (!retval)
4641                        retval = p->policy
4642                                | (p->sched_reset_on_fork ? SCHED_RESET_ON_FORK : 0);
4643        }
4644        rcu_read_unlock();
4645        return retval;
4646}
4647
4648/**
4649 * sys_sched_getparam - get the RT priority of a thread
4650 * @pid: the pid in question.
4651 * @param: structure containing the RT priority.
4652 */
4653SYSCALL_DEFINE2(sched_getparam, pid_t, pid, struct sched_param __user *, param)
4654{
4655        struct sched_param lp;
4656        struct task_struct *p;
4657        int retval;
4658
4659        if (!param || pid < 0)
4660                return -EINVAL;
4661
4662        rcu_read_lock();
4663        p = find_process_by_pid(pid);
4664        retval = -ESRCH;
4665        if (!p)
4666                goto out_unlock;
4667
4668        retval = security_task_getscheduler(p);
4669        if (retval)
4670                goto out_unlock;
4671
4672        lp.sched_priority = p->rt_priority;
4673        rcu_read_unlock();
4674
4675        /*
4676         * This one might sleep, we cannot do it with a spinlock held ...
4677         */
4678        retval = copy_to_user(param, &lp, sizeof(*param)) ? -EFAULT : 0;
4679
4680        return retval;
4681
4682out_unlock:
4683        rcu_read_unlock();
4684        return retval;
4685}
4686
4687long sched_setaffinity(pid_t pid, const struct cpumask *in_mask)
4688{
4689        cpumask_var_t cpus_allowed, new_mask;
4690        struct task_struct *p;
4691        int retval;
4692
4693        get_online_cpus();
4694        rcu_read_lock();
4695
4696        p = find_process_by_pid(pid);
4697        if (!p) {
4698                rcu_read_unlock();
4699                put_online_cpus();
4700                return -ESRCH;
4701        }
4702
4703        /* Prevent p going away */
4704        get_task_struct(p);
4705        rcu_read_unlock();
4706
4707        if (!alloc_cpumask_var(&cpus_allowed, GFP_KERNEL)) {
4708                retval = -ENOMEM;
4709                goto out_put_task;
4710        }
4711        if (!alloc_cpumask_var(&new_mask, GFP_KERNEL)) {
4712                retval = -ENOMEM;
4713                goto out_free_cpus_allowed;
4714        }
4715        retval = -EPERM;
4716        if (!check_same_owner(p) && !capable(CAP_SYS_NICE))
4717                goto out_unlock;
4718
4719        retval = security_task_setscheduler(p, 0, NULL);
4720        if (retval)
4721                goto out_unlock;
4722
4723        cpuset_cpus_allowed(p, cpus_allowed);
4724        cpumask_and(new_mask, in_mask, cpus_allowed);
4725 again:
4726        retval = set_cpus_allowed_ptr(p, new_mask);
4727
4728        if (!retval) {
4729                cpuset_cpus_allowed(p, cpus_allowed);
4730                if (!cpumask_subset(new_mask, cpus_allowed)) {
4731                        /*
4732                         * We must have raced with a concurrent cpuset
4733                         * update. Just reset the cpus_allowed to the
4734                         * cpuset's cpus_allowed
4735                         */
4736                        cpumask_copy(new_mask, cpus_allowed);
4737                        goto again;
4738                }
4739        }
4740out_unlock:
4741        free_cpumask_var(new_mask);
4742out_free_cpus_allowed:
4743        free_cpumask_var(cpus_allowed);
4744out_put_task:
4745        put_task_struct(p);
4746        put_online_cpus();
4747        return retval;
4748}
4749
4750static int get_user_cpu_mask(unsigned long __user *user_mask_ptr, unsigned len,
4751                             struct cpumask *new_mask)
4752{
4753        if (len < cpumask_size())
4754                cpumask_clear(new_mask);
4755        else if (len > cpumask_size())
4756                len = cpumask_size();
4757
4758        return copy_from_user(new_mask, user_mask_ptr, len) ? -EFAULT : 0;
4759}
4760
4761/**
4762 * sys_sched_setaffinity - set the cpu affinity of a process
4763 * @pid: pid of the process
4764 * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4765 * @user_mask_ptr: user-space pointer to the new cpu mask
4766 */
4767SYSCALL_DEFINE3(sched_setaffinity, pid_t, pid, unsigned int, len,
4768                unsigned long __user *, user_mask_ptr)
4769{
4770        cpumask_var_t new_mask;
4771        int retval;
4772
4773        if (!alloc_cpumask_var(&new_mask, GFP_KERNEL))
4774                return -ENOMEM;
4775
4776        retval = get_user_cpu_mask(user_mask_ptr, len, new_mask);
4777        if (retval == 0)
4778                retval = sched_setaffinity(pid, new_mask);
4779        free_cpumask_var(new_mask);
4780        return retval;
4781}
4782
4783long sched_getaffinity(pid_t pid, struct cpumask *mask)
4784{
4785        struct task_struct *p;
4786        unsigned long flags;
4787        struct rq *rq;
4788        int retval;
4789
4790        get_online_cpus();
4791        rcu_read_lock();
4792
4793        retval = -ESRCH;
4794        p = find_process_by_pid(pid);
4795        if (!p)
4796                goto out_unlock;
4797
4798        retval = security_task_getscheduler(p);
4799        if (retval)
4800                goto out_unlock;
4801
4802        rq = task_rq_lock(p, &flags);
4803        cpumask_and(mask, &p->cpus_allowed, cpu_online_mask);
4804        task_rq_unlock(rq, &flags);
4805
4806out_unlock:
4807        rcu_read_unlock();
4808        put_online_cpus();
4809
4810        return retval;
4811}
4812
4813/**
4814 * sys_sched_getaffinity - get the cpu affinity of a process
4815 * @pid: pid of the process
4816 * @len: length in bytes of the bitmask pointed to by user_mask_ptr
4817 * @user_mask_ptr: user-space pointer to hold the current cpu mask
4818 */
4819SYSCALL_DEFINE3(sched_getaffinity, pid_t, pid, unsigned int, len,
4820                unsigned long __user *, user_mask_ptr)
4821{
4822        int ret;
4823        cpumask_var_t mask;
4824
4825        if ((len * BITS_PER_BYTE) < nr_cpu_ids)
4826                return -EINVAL;
4827        if (len & (sizeof(unsigned long)-1))
4828                return -EINVAL;
4829
4830        if (!alloc_cpumask_var(&mask, GFP_KERNEL))
4831                return -ENOMEM;
4832
4833        ret = sched_getaffinity(pid, mask);
4834        if (ret == 0) {
4835                size_t retlen = min_t(size_t, len, cpumask_size());
4836
4837                if (copy_to_user(user_mask_ptr, mask, retlen))
4838                        ret = -EFAULT;
4839                else
4840                        ret = retlen;
4841        }
4842        free_cpumask_var(mask);
4843
4844        return ret;
4845}
4846
4847/**
4848 * sys_sched_yield - yield the current processor to other threads.
4849 *
4850 * This function yields the current CPU to other tasks. If there are no
4851 * other threads running on this CPU then this function will return.
4852 */
4853SYSCALL_DEFINE0(sched_yield)
4854{
4855        struct rq *rq = this_rq_lock();
4856
4857        schedstat_inc(rq, yld_count);
4858        current->sched_class->yield_task(rq);
4859
4860        /*
4861         * Since we are going to call schedule() anyway, there's
4862         * no need to preempt or enable interrupts:
4863         */
4864        __release(rq->lock);
4865        spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
4866        do_raw_spin_unlock(&rq->lock);
4867        preempt_enable_no_resched();
4868
4869        schedule();
4870
4871        return 0;
4872}
4873
4874static inline int should_resched(void)
4875{
4876        return need_resched() && !(preempt_count() & PREEMPT_ACTIVE);
4877}
4878
4879static void __cond_resched(void)
4880{
4881        add_preempt_count(PREEMPT_ACTIVE);
4882        schedule();
4883        sub_preempt_count(PREEMPT_ACTIVE);
4884}
4885
4886int __sched _cond_resched(void)
4887{
4888        if (should_resched()) {
4889                __cond_resched();
4890                return 1;
4891        }
4892        return 0;
4893}
4894EXPORT_SYMBOL(_cond_resched);
4895
4896/*
4897 * __cond_resched_lock() - if a reschedule is pending, drop the given lock,
4898 * call schedule, and on return reacquire the lock.
4899 *
4900 * This works OK both with and without CONFIG_PREEMPT. We do strange low-level
4901 * operations here to prevent schedule() from being called twice (once via
4902 * spin_unlock(), once by hand).
4903 */
4904int __cond_resched_lock(spinlock_t *lock)
4905{
4906        int resched = should_resched();
4907        int ret = 0;
4908
4909        lockdep_assert_held(lock);
4910
4911        if (spin_needbreak(lock) || resched) {
4912                spin_unlock(lock);
4913                if (resched)
4914                        __cond_resched();
4915                else
4916                        cpu_relax();
4917                ret = 1;
4918                spin_lock(lock);
4919        }
4920        return ret;
4921}
4922EXPORT_SYMBOL(__cond_resched_lock);
4923
4924int __sched __cond_resched_softirq(void)
4925{
4926        BUG_ON(!in_softirq());
4927
4928        if (should_resched()) {
4929                local_bh_enable();
4930                __cond_resched();
4931                local_bh_disable();
4932                return 1;
4933        }
4934        return 0;
4935}
4936EXPORT_SYMBOL(__cond_resched_softirq);
4937
4938/**
4939 * yield - yield the current processor to other threads.
4940 *
4941 * This is a shortcut for kernel-space yielding - it marks the
4942 * thread runnable and calls sys_sched_yield().
4943 */
4944void __sched yield(void)
4945{
4946        set_current_state(TASK_RUNNING);
4947        sys_sched_yield();
4948}
4949EXPORT_SYMBOL(yield);
4950
4951/*
4952 * This task is about to go to sleep on IO. Increment rq->nr_iowait so
4953 * that process accounting knows that this is a task in IO wait state.
4954 */
4955void __sched io_schedule(void)
4956{
4957        struct rq *rq = raw_rq();
4958
4959        delayacct_blkio_start();
4960        atomic_inc(&rq->nr_iowait);
4961        current->in_iowait = 1;
4962        schedule();
4963        current->in_iowait = 0;
4964        atomic_dec(&rq->nr_iowait);
4965        delayacct_blkio_end();
4966}
4967EXPORT_SYMBOL(io_schedule);
4968
4969long __sched io_schedule_timeout(long timeout)
4970{
4971        struct rq *rq = raw_rq();
4972        long ret;
4973
4974        delayacct_blkio_start();
4975        atomic_inc(&rq->nr_iowait);
4976        current->in_iowait = 1;
4977        ret = schedule_timeout(timeout);
4978        current->in_iowait = 0;
4979        atomic_dec(&rq->nr_iowait);
4980        delayacct_blkio_end();
4981        return ret;
4982}
4983
4984/**
4985 * sys_sched_get_priority_max - return maximum RT priority.
4986 * @policy: scheduling class.
4987 *
4988 * this syscall returns the maximum rt_priority that can be used
4989 * by a given scheduling class.
4990 */
4991SYSCALL_DEFINE1(sched_get_priority_max, int, policy)
4992{
4993        int ret = -EINVAL;
4994
4995        switch (policy) {
4996        case SCHED_FIFO:
4997        case SCHED_RR:
4998                ret = MAX_USER_RT_PRIO-1;
4999                break;
5000        case SCHED_NORMAL:
5001        case SCHED_BATCH:
5002        case SCHED_IDLE:
5003                ret = 0;
5004                break;
5005        }
5006        return ret;
5007}
5008
5009/**
5010 * sys_sched_get_priority_min - return minimum RT priority.
5011 * @policy: scheduling class.
5012 *
5013 * this syscall returns the minimum rt_priority that can be used
5014 * by a given scheduling class.
5015 */
5016SYSCALL_DEFINE1(sched_get_priority_min, int, policy)
5017{
5018        int ret = -EINVAL;
5019
5020        switch (policy) {
5021        case SCHED_FIFO:
5022        case SCHED_RR:
5023                ret = 1;
5024                break;
5025        case SCHED_NORMAL:
5026        case SCHED_BATCH:
5027        case SCHED_IDLE:
5028                ret = 0;
5029        }
5030        return ret;
5031}
5032
5033/**
5034 * sys_sched_rr_get_interval - return the default timeslice of a process.
5035 * @pid: pid of the process.
5036 * @interval: userspace pointer to the timeslice value.
5037 *
5038 * this syscall writes the default timeslice value of a given process
5039 * into the user-space timespec buffer. A value of '0' means infinity.
5040 */
5041SYSCALL_DEFINE2(sched_rr_get_interval, pid_t, pid,
5042                struct timespec __user *, interval)
5043{
5044        struct task_struct *p;
5045        unsigned int time_slice;
5046        unsigned long flags;
5047        struct rq *rq;
5048        int retval;
5049        struct timespec t;
5050
5051        if (pid < 0)
5052                return -EINVAL;
5053
5054        retval = -ESRCH;
5055        rcu_read_lock();
5056        p = find_process_by_pid(pid);
5057        if (!p)
5058                goto out_unlock;
5059
5060        retval = security_task_getscheduler(p);
5061        if (retval)
5062                goto out_unlock;
5063
5064        rq = task_rq_lock(p, &flags);
5065        time_slice = p->sched_class->get_rr_interval(rq, p);
5066        task_rq_unlock(rq, &flags);
5067
5068        rcu_read_unlock();
5069        jiffies_to_timespec(time_slice, &t);
5070        retval = copy_to_user(interval, &t, sizeof(t)) ? -EFAULT : 0;
5071        return retval;
5072
5073out_unlock:
5074        rcu_read_unlock();
5075        return retval;
5076}
5077
5078static const char stat_nam[] = TASK_STATE_TO_CHAR_STR;
5079
5080void sched_show_task(struct task_struct *p)
5081{
5082        unsigned long free = 0;
5083        unsigned state;
5084
5085        state = p->state ? __ffs(p->state) + 1 : 0;
5086        printk(KERN_INFO "%-13.13s %c", p->comm,
5087                state < sizeof(stat_nam) - 1 ? stat_nam[state] : '?');
5088#if BITS_PER_LONG == 32
5089        if (state == TASK_RUNNING)
5090                printk(KERN_CONT " running  ");
5091        else
5092                printk(KERN_CONT " %08lx ", thread_saved_pc(p));
5093#else
5094        if (state == TASK_RUNNING)
5095                printk(KERN_CONT "  running task    ");
5096        else
5097                printk(KERN_CONT " %016lx ", thread_saved_pc(p));
5098#endif
5099#ifdef CONFIG_DEBUG_STACK_USAGE
5100        free = stack_not_used(p);
5101#endif
5102        printk(KERN_CONT "%5lu %5d %6d 0x%08lx\n", free,
5103                task_pid_nr(p), task_pid_nr(p->real_parent),
5104                (unsigned long)task_thread_info(p)->flags);
5105
5106        show_stack(p, NULL);
5107}
5108
5109void show_state_filter(unsigned long state_filter)
5110{
5111        struct task_struct *g, *p;
5112
5113#if BITS_PER_LONG == 32
5114        printk(KERN_INFO
5115                "  task                PC stack   pid father\n");
5116#else
5117        printk(KERN_INFO
5118                "  task                        PC stack   pid father\n");
5119#endif
5120        read_lock(&tasklist_lock);
5121        do_each_thread(g, p) {
5122                /*
5123                 * reset the NMI-timeout, listing all files on a slow
5124                 * console might take alot of time:
5125                 */
5126                touch_nmi_watchdog();
5127                if (!state_filter || (p->state & state_filter))
5128                        sched_show_task(p);
5129        } while_each_thread(g, p);
5130
5131        touch_all_softlockup_watchdogs();
5132
5133#ifdef CONFIG_SCHED_DEBUG
5134        sysrq_sched_debug_show();
5135#endif
5136        read_unlock(&tasklist_lock);
5137        /*
5138         * Only show locks if all tasks are dumped:
5139         */
5140        if (!state_filter)
5141                debug_show_all_locks();
5142}
5143
5144void __cpuinit init_idle_bootup_task(struct task_struct *idle)
5145{
5146        idle->sched_class = &idle_sched_class;
5147}
5148
5149/**
5150 * init_idle - set up an idle thread for a given CPU
5151 * @idle: task in question
5152 * @cpu: cpu the idle task belongs to
5153 *
5154 * NOTE: this function does not set the idle thread's NEED_RESCHED
5155 * flag, to make booting more robust.
5156 */
5157void __cpuinit init_idle(struct task_struct *idle, int cpu)
5158{
5159        struct rq *rq = cpu_rq(cpu);
5160        unsigned long flags;
5161
5162        raw_spin_lock_irqsave(&rq->lock, flags);
5163
5164        __sched_fork(idle);
5165        idle->state = TASK_RUNNING;
5166        idle->se.exec_start = sched_clock();
5167
5168        cpumask_copy(&idle->cpus_allowed, cpumask_of(cpu));
5169        __set_task_cpu(idle, cpu);
5170
5171        rq->curr = rq->idle = idle;
5172#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
5173        idle->oncpu = 1;
5174#endif
5175        raw_spin_unlock_irqrestore(&rq->lock, flags);
5176
5177        /* Set the preempt count _outside_ the spinlocks! */
5178#if defined(CONFIG_PREEMPT)
5179        task_thread_info(idle)->preempt_count = (idle->lock_depth >= 0);
5180#else
5181        task_thread_info(idle)->preempt_count = 0;
5182#endif
5183        /*
5184         * The idle tasks have their own, simple scheduling class:
5185         */
5186        idle->sched_class = &idle_sched_class;
5187        ftrace_graph_init_task(idle);
5188}
5189
5190/*
5191 * In a system that switches off the HZ timer nohz_cpu_mask
5192 * indicates which cpus entered this state. This is used
5193 * in the rcu update to wait only for active cpus. For system
5194 * which do not switch off the HZ timer nohz_cpu_mask should
5195 * always be CPU_BITS_NONE.
5196 */
5197cpumask_var_t nohz_cpu_mask;
5198
5199/*
5200 * Increase the granularity value when there are more CPUs,
5201 * because with more CPUs the 'effective latency' as visible
5202 * to users decreases. But the relationship is not linear,
5203 * so pick a second-best guess by going with the log2 of the
5204 * number of CPUs.
5205 *
5206 * This idea comes from the SD scheduler of Con Kolivas:
5207 */
5208static int get_update_sysctl_factor(void)
5209{
5210        unsigned int cpus = min_t(int, num_online_cpus(), 8);
5211        unsigned int factor;
5212
5213        switch (sysctl_sched_tunable_scaling) {
5214        case SCHED_TUNABLESCALING_NONE:
5215                factor = 1;
5216                break;
5217        case SCHED_TUNABLESCALING_LINEAR:
5218                factor = cpus;
5219                break;
5220        case SCHED_TUNABLESCALING_LOG:
5221        default:
5222                factor = 1 + ilog2(cpus);
5223                break;
5224        }
5225
5226        return factor;
5227}
5228
5229static void update_sysctl(void)
5230{
5231        unsigned int factor = get_update_sysctl_factor();
5232
5233#define SET_SYSCTL(name) \
5234        (sysctl_##name = (factor) * normalized_sysctl_##name)
5235        SET_SYSCTL(sched_min_granularity);
5236        SET_SYSCTL(sched_latency);
5237        SET_SYSCTL(sched_wakeup_granularity);
5238        SET_SYSCTL(sched_shares_ratelimit);
5239#undef SET_SYSCTL
5240}
5241
5242static inline void sched_init_granularity(void)
5243{
5244        update_sysctl();
5245}
5246
5247#ifdef CONFIG_SMP
5248/*
5249 * This is how migration works:
5250 *
5251 * 1) we invoke migration_cpu_stop() on the target CPU using
5252 *    stop_one_cpu().
5253 * 2) stopper starts to run (implicitly forcing the migrated thread
5254 *    off the CPU)
5255 * 3) it checks whether the migrated task is still in the wrong runqueue.
5256 * 4) if it's in the wrong runqueue then the migration thread removes
5257 *    it and puts it into the right queue.
5258 * 5) stopper completes and stop_one_cpu() returns and the migration
5259 *    is done.
5260 */
5261
5262/*
5263 * Change a given task's CPU affinity. Migrate the thread to a
5264 * proper CPU and schedule it away if the CPU it's executing on
5265 * is removed from the allowed bitmask.
5266 *
5267 * NOTE: the caller must have a valid reference to the task, the
5268 * task must not exit() & deallocate itself prematurely. The
5269 * call is not atomic; no spinlocks may be held.
5270 */
5271int set_cpus_allowed_ptr(struct task_struct *p, const struct cpumask *new_mask)
5272{
5273        unsigned long flags;
5274        struct rq *rq;
5275        unsigned int dest_cpu;
5276        int ret = 0;
5277
5278        /*
5279         * Serialize against TASK_WAKING so that ttwu() and wunt() can
5280         * drop the rq->lock and still rely on ->cpus_allowed.
5281         */
5282again:
5283        while (task_is_waking(p))
5284                cpu_relax();
5285        rq = task_rq_lock(p, &flags);
5286        if (task_is_waking(p)) {
5287                task_rq_unlock(rq, &flags);
5288                goto again;
5289        }
5290
5291        if (!cpumask_intersects(new_mask, cpu_active_mask)) {
5292                ret = -EINVAL;
5293                goto out;
5294        }
5295
5296        if (unlikely((p->flags & PF_THREAD_BOUND) && p != current &&
5297                     !cpumask_equal(&p->cpus_allowed, new_mask))) {
5298                ret = -EINVAL;
5299                goto out;
5300        }
5301
5302        if (p->sched_class->set_cpus_allowed)
5303                p->sched_class->set_cpus_allowed(p, new_mask);
5304        else {
5305                cpumask_copy(&p->cpus_allowed, new_mask);
5306                p->rt.nr_cpus_allowed = cpumask_weight(new_mask);
5307        }
5308
5309        /* Can the task run on the task's current CPU? If so, we're done */
5310        if (cpumask_test_cpu(task_cpu(p), new_mask))
5311                goto out;
5312
5313        dest_cpu = cpumask_any_and(cpu_active_mask, new_mask);
5314        if (migrate_task(p, dest_cpu)) {
5315                struct migration_arg arg = { p, dest_cpu };
5316                /* Need help from migration thread: drop lock and wait. */
5317                task_rq_unlock(rq, &flags);
5318                stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
5319                tlb_migrate_finish(p->mm);
5320                return 0;
5321        }
5322out:
5323        task_rq_unlock(rq, &flags);
5324
5325        return ret;
5326}
5327EXPORT_SYMBOL_GPL(set_cpus_allowed_ptr);
5328
5329/*
5330 * Move (not current) task off this cpu, onto dest cpu. We're doing
5331 * this because either it can't run here any more (set_cpus_allowed()
5332 * away from this CPU, or CPU going down), or because we're
5333 * attempting to rebalance this task on exec (sched_exec).
5334 *
5335 * So we race with normal scheduler movements, but that's OK, as long
5336 * as the task is no longer on this CPU.
5337 *
5338 * Returns non-zero if task was successfully migrated.
5339 */
5340static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
5341{
5342        struct rq *rq_dest, *rq_src;
5343        int ret = 0;
5344
5345        if (unlikely(!cpu_active(dest_cpu)))
5346                return ret;
5347
5348        rq_src = cpu_rq(src_cpu);
5349        rq_dest = cpu_rq(dest_cpu);
5350
5351        double_rq_lock(rq_src, rq_dest);
5352        /* Already moved. */
5353        if (task_cpu(p) != src_cpu)
5354                goto done;
5355        /* Affinity changed (again). */
5356        if (!cpumask_test_cpu(dest_cpu, &p->cpus_allowed))
5357                goto fail;
5358
5359        /*
5360         * If we're not on a rq, the next wake-up will ensure we're
5361         * placed properly.
5362         */
5363        if (p->se.on_rq) {
5364                deactivate_task(rq_src, p, 0);
5365                set_task_cpu(p, dest_cpu);
5366                activate_task(rq_dest, p, 0);
5367                check_preempt_curr(rq_dest, p, 0);
5368        }
5369done:
5370        ret = 1;
5371fail:
5372        double_rq_unlock(rq_src, rq_dest);
5373        return ret;
5374}
5375
5376/*
5377 * migration_cpu_stop - this will be executed by a highprio stopper thread
5378 * and performs thread migration by bumping thread off CPU then
5379 * 'pushing' onto another runqueue.
5380 */
5381static int migration_cpu_stop(void *data)
5382{
5383        struct migration_arg *arg = data;
5384
5385        /*
5386         * The original target cpu might have gone down and we might
5387         * be on another cpu but it doesn't matter.
5388         */
5389        local_irq_disable();
5390        __migrate_task(arg->task, raw_smp_processor_id(), arg->dest_cpu);
5391        local_irq_enable();
5392        return 0;
5393}
5394
5395#ifdef CONFIG_HOTPLUG_CPU
5396/*
5397 * Figure out where task on dead CPU should go, use force if necessary.
5398 */
5399void move_task_off_dead_cpu(int dead_cpu, struct task_struct *p)
5400{
5401        struct rq *rq = cpu_rq(dead_cpu);
5402        int needs_cpu, uninitialized_var(dest_cpu);
5403        unsigned long flags;
5404
5405        local_irq_save(flags);
5406
5407        raw_spin_lock(&rq->lock);
5408        needs_cpu = (task_cpu(p) == dead_cpu) && (p->state != TASK_WAKING);
5409        if (needs_cpu)
5410                dest_cpu = select_fallback_rq(dead_cpu, p);
5411        raw_spin_unlock(&rq->lock);
5412        /*
5413         * It can only fail if we race with set_cpus_allowed(),
5414         * in the racer should migrate the task anyway.
5415         */
5416        if (needs_cpu)
5417                __migrate_task(p, dead_cpu, dest_cpu);
5418        local_irq_restore(flags);
5419}
5420
5421/*
5422 * While a dead CPU has no uninterruptible tasks queued at this point,
5423 * it might still have a nonzero ->nr_uninterruptible counter, because
5424 * for performance reasons the counter is not stricly tracking tasks to
5425 * their home CPUs. So we just add the counter to another CPU's counter,
5426 * to keep the global sum constant after CPU-down:
5427 */
5428static void migrate_nr_uninterruptible(struct rq *rq_src)
5429{
5430        struct rq *rq_dest = cpu_rq(cpumask_any(cpu_active_mask));
5431        unsigned long flags;
5432
5433        local_irq_save(flags);
5434        double_rq_lock(rq_src, rq_dest);
5435        rq_dest->nr_uninterruptible += rq_src->nr_uninterruptible;
5436        rq_src->nr_uninterruptible = 0;
5437        double_rq_unlock(rq_src, rq_dest);
5438        local_irq_restore(flags);
5439}
5440
5441/* Run through task list and migrate tasks from the dead cpu. */
5442static void migrate_live_tasks(int src_cpu)
5443{
5444        struct task_struct *p, *t;
5445
5446        read_lock(&tasklist_lock);
5447
5448        do_each_thread(t, p) {
5449                if (p == current)
5450                        continue;
5451
5452                if (task_cpu(p) == src_cpu)
5453                        move_task_off_dead_cpu(src_cpu, p);
5454        } while_each_thread(t, p);
5455
5456        read_unlock(&tasklist_lock);
5457}
5458
5459/*
5460 * Schedules idle task to be the next runnable task on current CPU.
5461 * It does so by boosting its priority to highest possible.
5462 * Used by CPU offline code.
5463 */
5464void sched_idle_next(void)
5465{
5466        int this_cpu = smp_processor_id();
5467        struct rq *rq = cpu_rq(this_cpu);
5468        struct task_struct *p = rq->idle;
5469        unsigned long flags;
5470
5471        /* cpu has to be offline */
5472        BUG_ON(cpu_online(this_cpu));
5473
5474        /*
5475         * Strictly not necessary since rest of the CPUs are stopped by now
5476         * and interrupts disabled on the current cpu.
5477         */
5478        raw_spin_lock_irqsave(&rq->lock, flags);
5479
5480        __setscheduler(rq, p, SCHED_FIFO, MAX_RT_PRIO-1);
5481
5482        activate_task(rq, p, 0);
5483
5484        raw_spin_unlock_irqrestore(&rq->lock, flags);
5485}
5486
5487/*
5488 * Ensures that the idle task is using init_mm right before its cpu goes
5489 * offline.
5490 */
5491void idle_task_exit(void)
5492{
5493        struct mm_struct *mm = current->active_mm;
5494
5495        BUG_ON(cpu_online(smp_processor_id()));
5496
5497        if (mm != &init_mm)
5498                switch_mm(mm, &init_mm, current);
5499        mmdrop(mm);
5500}
5501
5502/* called under rq->lock with disabled interrupts */
5503static void migrate_dead(unsigned int dead_cpu, struct task_struct *p)
5504{
5505        struct rq *rq = cpu_rq(dead_cpu);
5506
5507        /* Must be exiting, otherwise would be on tasklist. */
5508        BUG_ON(!p->exit_state);
5509
5510        /* Cannot have done final schedule yet: would have vanished. */
5511        BUG_ON(p->state == TASK_DEAD);
5512
5513        get_task_struct(p);
5514
5515        /*
5516         * Drop lock around migration; if someone else moves it,
5517         * that's OK. No task can be added to this CPU, so iteration is
5518         * fine.
5519         */
5520        raw_spin_unlock_irq(&rq->lock);
5521        move_task_off_dead_cpu(dead_cpu, p);
5522        raw_spin_lock_irq(&rq->lock);
5523
5524        put_task_struct(p);
5525}
5526
5527/* release_task() removes task from tasklist, so we won't find dead tasks. */
5528static void migrate_dead_tasks(unsigned int dead_cpu)
5529{
5530        struct rq *rq = cpu_rq(dead_cpu);
5531        struct task_struct *next;
5532
5533        for ( ; ; ) {
5534                if (!rq->nr_running)
5535                        break;
5536                next = pick_next_task(rq);
5537                if (!next)
5538                        break;
5539                next->sched_class->put_prev_task(rq, next);
5540                migrate_dead(dead_cpu, next);
5541
5542        }
5543}
5544
5545/*
5546 * remove the tasks which were accounted by rq from calc_load_tasks.
5547 */
5548static void calc_global_load_remove(struct rq *rq)
5549{
5550        atomic_long_sub(rq->calc_load_active, &calc_load_tasks);
5551        rq->calc_load_active = 0;
5552}
5553#endif /* CONFIG_HOTPLUG_CPU */
5554
5555#if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL)
5556
5557static struct ctl_table sd_ctl_dir[] = {
5558        {
5559                .procname       = "sched_domain",
5560                .mode           = 0555,
5561        },
5562        {}
5563};
5564
5565static struct ctl_table sd_ctl_root[] = {
5566        {
5567                .procname       = "kernel",
5568                .mode           = 0555,
5569                .child          = sd_ctl_dir,
5570        },
5571        {}
5572};
5573
5574static struct ctl_table *sd_alloc_ctl_entry(int n)
5575{
5576        struct ctl_table *entry =
5577                kcalloc(n, sizeof(struct ctl_table), GFP_KERNEL);
5578
5579        return entry;
5580}
5581
5582static void sd_free_ctl_entry(struct ctl_table **tablep)
5583{
5584        struct ctl_table *entry;
5585
5586        /*
5587         * In the intermediate directories, both the child directory and
5588         * procname are dynamically allocated and could fail but the mode
5589         * will always be set. In the lowest directory the names are
5590         * static strings and all have proc handlers.
5591         */
5592        for (entry = *tablep; entry->mode; entry++) {
5593                if (entry->child)
5594                        sd_free_ctl_entry(&entry->child);
5595                if (entry->proc_handler == NULL)
5596                        kfree(entry->procname);
5597        }
5598
5599        kfree(*tablep);
5600        *tablep = NULL;
5601}
5602
5603static void
5604set_table_entry(struct ctl_table *entry,
5605                const char *procname, void *data, int maxlen,
5606                mode_t mode, proc_handler *proc_handler)
5607{
5608        entry->procname = procname;
5609        entry->data = data;
5610        entry->maxlen = maxlen;
5611        entry->mode = mode;
5612        entry->proc_handler = proc_handler;
5613}
5614
5615static struct ctl_table *
5616sd_alloc_ctl_domain_table(struct sched_domain *sd)
5617{
5618        struct ctl_table *table = sd_alloc_ctl_entry(13);
5619
5620        if (table == NULL)
5621                return NULL;
5622
5623        set_table_entry(&table[0], "min_interval", &sd->min_interval,
5624                sizeof(long), 0644, proc_doulongvec_minmax);
5625        set_table_entry(&table[1], "max_interval", &sd->max_interval,
5626                sizeof(long), 0644, proc_doulongvec_minmax);
5627        set_table_entry(&table[2], "busy_idx", &sd->busy_idx,
5628                sizeof(int), 0644, proc_dointvec_minmax);
5629        set_table_entry(&table[3], "idle_idx", &sd->idle_idx,
5630                sizeof(int), 0644, proc_dointvec_minmax);
5631        set_table_entry(&table[4], "newidle_idx", &sd->newidle_idx,
5632                sizeof(int), 0644, proc_dointvec_minmax);
5633        set_table_entry(&table[5], "wake_idx", &sd->wake_idx,
5634                sizeof(int), 0644, proc_dointvec_minmax);
5635        set_table_entry(&table[6], "forkexec_idx", &sd->forkexec_idx,
5636                sizeof(int), 0644, proc_dointvec_minmax);
5637        set_table_entry(&table[7], "busy_factor", &sd->busy_factor,
5638                sizeof(int), 0644, proc_dointvec_minmax);
5639        set_table_entry(&table[8], "imbalance_pct", &sd->imbalance_pct,
5640                sizeof(int), 0644, proc_dointvec_minmax);
5641        set_table_entry(&table[9], "cache_nice_tries",
5642                &sd->cache_nice_tries,
5643                sizeof(int), 0644, proc_dointvec_minmax);
5644        set_table_entry(&table[10], "flags", &sd->flags,
5645                sizeof(int), 0644, proc_dointvec_minmax);
5646        set_table_entry(&table[11], "name", sd->name,
5647                CORENAME_MAX_SIZE, 0444, proc_dostring);
5648        /* &table[12] is terminator */
5649
5650        return table;
5651}
5652
5653static ctl_table *sd_alloc_ctl_cpu_table(int cpu)
5654{
5655        struct ctl_table *entry, *table;
5656        struct sched_domain *sd;
5657        int domain_num = 0, i;
5658        char buf[32];
5659
5660        for_each_domain(cpu, sd)
5661                domain_num++;
5662        entry = table = sd_alloc_ctl_entry(domain_num + 1);
5663        if (table == NULL)
5664                return NULL;
5665
5666        i = 0;
5667        for_each_domain(cpu, sd) {
5668                snprintf(buf, 32, "domain%d", i);
5669                entry->procname = kstrdup(buf, GFP_KERNEL);
5670                entry->mode = 0555;
5671                entry->child = sd_alloc_ctl_domain_table(sd);
5672                entry++;
5673                i++;
5674        }
5675        return table;
5676}
5677
5678static struct ctl_table_header *sd_sysctl_header;
5679static void register_sched_domain_sysctl(void)
5680{
5681        int i, cpu_num = num_possible_cpus();
5682        struct ctl_table *entry = sd_alloc_ctl_entry(cpu_num + 1);
5683        char buf[32];
5684
5685        WARN_ON(sd_ctl_dir[0].child);
5686        sd_ctl_dir[0].child = entry;
5687
5688        if (entry == NULL)
5689                return;
5690
5691        for_each_possible_cpu(i) {
5692                snprintf(buf, 32, "cpu%d", i);
5693                entry->procname = kstrdup(buf, GFP_KERNEL);
5694                entry->mode = 0555;
5695                entry->child = sd_alloc_ctl_cpu_table(i);
5696                entry++;
5697        }
5698
5699        WARN_ON(sd_sysctl_header);
5700        sd_sysctl_header = register_sysctl_table(sd_ctl_root);
5701}
5702
5703/* may be called multiple times per register */
5704static void unregister_sched_domain_sysctl(void)
5705{
5706        if (sd_sysctl_header)
5707                unregister_sysctl_table(sd_sysctl_header);
5708        sd_sysctl_header = NULL;
5709        if (sd_ctl_dir[0].child)
5710                sd_free_ctl_entry(&sd_ctl_dir[0].child);
5711}
5712#else
5713static void register_sched_domain_sysctl(void)
5714{
5715}
5716static void unregister_sched_domain_sysctl(void)
5717{
5718}
5719#endif
5720
5721static void set_rq_online(struct rq *rq)
5722{
5723        if (!rq->online) {
5724                const struct sched_class *class;
5725
5726                cpumask_set_cpu(rq->cpu, rq->rd->online);
5727                rq->online = 1;
5728
5729                for_each_class(class) {
5730                        if (class->rq_online)
5731                                class->rq_online(rq);
5732                }
5733        }
5734}
5735
5736static void set_rq_offline(struct rq *rq)
5737{
5738        if (rq->online) {
5739                const struct sched_class *class;
5740
5741                for_each_class(class) {
5742                        if (class->rq_offline)
5743                                class->rq_offline(rq);
5744                }
5745
5746                cpumask_clear_cpu(rq->cpu, rq->rd->online);
5747                rq->online = 0;
5748        }
5749}
5750
5751/*
5752 * migration_call - callback that gets triggered when a CPU is added.
5753 * Here we can start up the necessary migration thread for the new CPU.
5754 */
5755static int __cpuinit
5756migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
5757{
5758        int cpu = (long)hcpu;
5759        unsigned long flags;
5760        struct rq *rq = cpu_rq(cpu);
5761
5762        switch (action) {
5763
5764        case CPU_UP_PREPARE:
5765        case CPU_UP_PREPARE_FROZEN:
5766                rq->calc_load_update = calc_load_update;
5767                break;
5768
5769        case CPU_ONLINE:
5770        case CPU_ONLINE_FROZEN:
5771                /* Update our root-domain */
5772                raw_spin_lock_irqsave(&rq->lock, flags);
5773                if (rq->rd) {
5774                        BUG_ON(!cpumask_test_cpu(cpu, rq->rd->span));
5775
5776                        set_rq_online(rq);
5777                }
5778                raw_spin_unlock_irqrestore(&rq->lock, flags);
5779                break;
5780
5781#ifdef CONFIG_HOTPLUG_CPU
5782        case CPU_DEAD:
5783        case CPU_DEAD_FROZEN:
5784                migrate_live_tasks(cpu);
5785                /* Idle task back to normal (off runqueue, low prio) */
5786                raw_spin_lock_irq(&rq->lock);
5787                deactivate_task(rq, rq->idle, 0);
5788                __setscheduler(rq, rq->idle, SCHED_NORMAL, 0);
5789                rq->idle->sched_class = &idle_sched_class;
5790                migrate_dead_tasks(cpu);
5791                raw_spin_unlock_irq(&rq->lock);
5792                migrate_nr_uninterruptible(rq);
5793                BUG_ON(rq->nr_running != 0);
5794                calc_global_load_remove(rq);
5795                break;
5796
5797        case CPU_DYING:
5798        case CPU_DYING_FROZEN:
5799                /* Update our root-domain */
5800                raw_spin_lock_irqsave(&rq->lock, flags);
5801                if (rq->rd) {
5802                        BUG_ON(!cpumask_test_cpu(cpu, rq->rd->span));
5803                        set_rq_offline(rq);
5804                }
5805                raw_spin_unlock_irqrestore(&rq->lock, flags);
5806                break;
5807#endif
5808        }
5809        return NOTIFY_OK;
5810}
5811
5812/*
5813 * Register at high priority so that task migration (migrate_all_tasks)
5814 * happens before everything else.  This has to be lower priority than
5815 * the notifier in the perf_event subsystem, though.
5816 */
5817static struct notifier_block __cpuinitdata migration_notifier = {
5818        .notifier_call = migration_call,
5819        .priority = 10
5820};
5821
5822static int __init migration_init(void)
5823{
5824        void *cpu = (void *)(long)smp_processor_id();
5825        int err;
5826
5827        /* Start one for the boot CPU: */
5828        err = migration_call(&migration_notifier, CPU_UP_PREPARE, cpu);
5829        BUG_ON(err == NOTIFY_BAD);
5830        migration_call(&migration_notifier, CPU_ONLINE, cpu);
5831        register_cpu_notifier(&migration_notifier);
5832
5833        return 0;
5834}
5835early_initcall(migration_init);
5836#endif
5837
5838#ifdef CONFIG_SMP
5839
5840#ifdef CONFIG_SCHED_DEBUG
5841
5842static __read_mostly int sched_domain_debug_enabled;
5843
5844static int __init sched_domain_debug_setup(char *str)
5845{
5846        sched_domain_debug_enabled = 1;
5847
5848        return 0;
5849}
5850early_param("sched_debug", sched_domain_debug_setup);
5851
5852static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
5853                                  struct cpumask *groupmask)
5854{
5855        struct sched_group *group = sd->groups;
5856        char str[256];
5857
5858        cpulist_scnprintf(str, sizeof(str), sched_domain_span(sd));
5859        cpumask_clear(groupmask);
5860
5861        printk(KERN_DEBUG "%*s domain %d: ", level, "", level);
5862
5863        if (!(sd->flags & SD_LOAD_BALANCE)) {
5864                printk("does not load-balance\n");
5865                if (sd->parent)
5866                        printk(KERN_ERR "ERROR: !SD_LOAD_BALANCE domain"
5867                                        " has parent");
5868                return -1;
5869        }
5870
5871        printk(KERN_CONT "span %s level %s\n", str, sd->name);
5872
5873        if (!cpumask_test_cpu(cpu, sched_domain_span(sd))) {
5874                printk(KERN_ERR "ERROR: domain->span does not contain "
5875                                "CPU%d\n", cpu);
5876        }
5877        if (!cpumask_test_cpu(cpu, sched_group_cpus(group))) {
5878                printk(KERN_ERR "ERROR: domain->groups does not contain"
5879                                " CPU%d\n", cpu);
5880        }
5881
5882        printk(KERN_DEBUG "%*s groups:", level + 1, "");
5883        do {
5884                if (!group) {
5885                        printk("\n");
5886                        printk(KERN_ERR "ERROR: group is NULL\n");
5887                        break;
5888                }
5889
5890                if (!group->cpu_power) {
5891                        printk(KERN_CONT "\n");
5892                        printk(KERN_ERR "ERROR: domain->cpu_power not "
5893                                        "set\n");
5894                        break;
5895                }
5896
5897                if (!cpumask_weight(sched_group_cpus(group))) {
5898                        printk(KERN_CONT "\n");
5899                        printk(KERN_ERR "ERROR: empty group\n");
5900                        break;
5901                }
5902
5903                if (cpumask_intersects(groupmask, sched_group_cpus(group))) {
5904                        printk(KERN_CONT "\n");
5905                        printk(KERN_ERR "ERROR: repeated CPUs\n");
5906                        break;
5907                }
5908
5909                cpumask_or(groupmask, groupmask, sched_group_cpus(group));
5910
5911                cpulist_scnprintf(str, sizeof(str), sched_group_cpus(group));
5912
5913                printk(KERN_CONT " %s", str);
5914                if (group->cpu_power != SCHED_LOAD_SCALE) {
5915                        printk(KERN_CONT " (cpu_power = %d)",
5916                                group->cpu_power);
5917                }
5918
5919                group = group->next;
5920        } while (group != sd->groups);
5921        printk(KERN_CONT "\n");
5922
5923        if (!cpumask_equal(sched_domain_span(sd), groupmask))
5924                printk(KERN_ERR "ERROR: groups don't span domain->span\n");
5925
5926        if (sd->parent &&
5927            !cpumask_subset(groupmask, sched_domain_span(sd->parent)))
5928                printk(KERN_ERR "ERROR: parent span is not a superset "
5929                        "of domain->span\n");
5930        return 0;
5931}
5932
5933static void sched_domain_debug(struct sched_domain *sd, int cpu)
5934{
5935        cpumask_var_t groupmask;
5936        int level = 0;
5937
5938        if (!sched_domain_debug_enabled)
5939                return;
5940
5941        if (!sd) {
5942                printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
5943                return;
5944        }
5945
5946        printk(KERN_DEBUG "CPU%d attaching sched-domain:\n", cpu);
5947
5948        if (!alloc_cpumask_var(&groupmask, GFP_KERNEL)) {
5949                printk(KERN_DEBUG "Cannot load-balance (out of memory)\n");
5950                return;
5951        }
5952
5953        for (;;) {
5954                if (sched_domain_debug_one(sd, cpu, level, groupmask))
5955                        break;
5956                level++;
5957                sd = sd->parent;
5958                if (!sd)
5959                        break;
5960        }
5961        free_cpumask_var(groupmask);
5962}
5963#else /* !CONFIG_SCHED_DEBUG */
5964# define sched_domain_debug(sd, cpu) do { } while (0)
5965#endif /* CONFIG_SCHED_DEBUG */
5966
5967static int sd_degenerate(struct sched_domain *sd)
5968{
5969        if (cpumask_weight(sched_domain_span(sd)) == 1)
5970                return 1;
5971
5972        /* Following flags need at least 2 groups */
5973        if (sd->flags & (SD_LOAD_BALANCE |
5974                         SD_BALANCE_NEWIDLE |
5975                         SD_BALANCE_FORK |
5976                         SD_BALANCE_EXEC |
5977                         SD_SHARE_CPUPOWER |
5978                         SD_SHARE_PKG_RESOURCES)) {
5979                if (sd->groups != sd->groups->next)
5980                        return 0;
5981        }
5982
5983        /* Following flags don't use groups */
5984        if (sd->flags & (SD_WAKE_AFFINE))
5985                return 0;
5986
5987        return 1;
5988}
5989
5990static int
5991sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
5992{
5993        unsigned long cflags = sd->flags, pflags = parent->flags;
5994
5995        if (sd_degenerate(parent))
5996                return 1;
5997
5998        if (!cpumask_equal(sched_domain_span(sd), sched_domain_span(parent)))
5999                return 0;
6000
6001        /* Flags needing groups don't count if only 1 group in parent */
6002        if (parent->groups == parent->groups->next) {
6003                pflags &= ~(SD_LOAD_BALANCE |
6004                                SD_BALANCE_NEWIDLE |
6005                                SD_BALANCE_FORK |
6006                                SD_BALANCE_EXEC |
6007                                SD_SHARE_CPUPOWER |
6008                                SD_SHARE_PKG_RESOURCES);
6009                if (nr_node_ids == 1)
6010                        pflags &= ~SD_SERIALIZE;
6011        }
6012        if (~cflags & pflags)
6013                return 0;
6014
6015        return 1;
6016}
6017
6018static void free_rootdomain(struct root_domain *rd)
6019{
6020        synchronize_sched();
6021
6022        cpupri_cleanup(&rd->cpupri);
6023
6024        free_cpumask_var(rd->rto_mask);
6025        free_cpumask_var(rd->online);
6026        free_cpumask_var(rd->span);
6027        kfree(rd);
6028}
6029
6030static void rq_attach_root(struct rq *rq, struct root_domain *rd)
6031{
6032        struct root_domain *old_rd = NULL;
6033        unsigned long flags;
6034
6035        raw_spin_lock_irqsave(&rq->lock, flags);
6036
6037        if (rq->rd) {
6038                old_rd = rq->rd;
6039
6040                if (cpumask_test_cpu(rq->cpu, old_rd->online))
6041                        set_rq_offline(rq);