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