Merge branch 'mpi-master' into wip-k-fmlpwip-k-fmlp

Conflicts:
	litmus/sched_cedf.c

1 files changed, 1801 insertions, 1636 deletions

diff --git a/kernel/sched.c b/kernel/sched.c
index c5d775079027..baaca61bc3a3 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -32,7 +32,6 @@
 #include <linux/init.h>
 #include <linux/uaccess.h>
 #include <linux/highmem.h>
-#include <linux/smp_lock.h>
 #include <asm/mmu_context.h>
 #include <linux/interrupt.h>
 #include <linux/capability.h>
@@ -75,9 +74,11 @@
 
 #include <asm/tlb.h>
 #include <asm/irq_regs.h>
+#include <asm/mutex.h>
 
 #include "sched_cpupri.h"
 #include "workqueue_sched.h"
+#include "sched_autogroup.h"
 
 #include <litmus/sched_trace.h>
 #include <litmus/trace.h>
@@ -235,7 +236,7 @@ static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b)
 #endif
 
 /*
- * sched_domains_mutex serializes calls to arch_init_sched_domains,
+ * sched_domains_mutex serializes calls to init_sched_domains,
  * detach_destroy_domains and partition_sched_domains.
  */
 static DEFINE_MUTEX(sched_domains_mutex);
@@ -258,6 +259,8 @@ struct task_group {
         /* runqueue "owned" by this group on each cpu */
         struct cfs_rq **cfs_rq;
         unsigned long shares;
+
+        atomic_t load_weight;
 #endif
 
 #ifdef CONFIG_RT_GROUP_SCHED
@@ -273,25 +276,18 @@ struct task_group {
         struct task_group *parent;
         struct list_head siblings;
         struct list_head children;
-};
 
-#define root_task_group init_task_group
+#ifdef CONFIG_SCHED_AUTOGROUP
+        struct autogroup *autogroup;
+#endif
+};
 
-/* task_group_lock serializes add/remove of task groups and also changes to
- * a task group's cpu shares.
- */
+/* task_group_lock serializes the addition/removal of task groups */
 static DEFINE_SPINLOCK(task_group_lock);
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 
-#ifdef CONFIG_SMP
-static int root_task_group_empty(void)
-{
-        return list_empty(&root_task_group.children);
-}
-#endif
-
-# define INIT_TASK_GROUP_LOAD   NICE_0_LOAD
+# define ROOT_TASK_GROUP_LOAD   NICE_0_LOAD
 
 /*
  * A weight of 0 or 1 can cause arithmetics problems.
@@ -301,16 +297,16 @@ static int root_task_group_empty(void)
  * (The default weight is 1024 - so there's no practical
  *  limitation from this.)
  */
-#define MIN_SHARES      2
+#define MIN_SHARES      (1UL <<  1)
 #define MAX_SHARES      (1UL << 18)
 
-static int init_task_group_load = INIT_TASK_GROUP_LOAD;
+static int root_task_group_load = ROOT_TASK_GROUP_LOAD;
 #endif
 
 /* Default task group.
  *      Every task in system belong to this group at bootup.
  */
-struct task_group init_task_group;
+struct task_group root_task_group;
 
 #endif  /* CONFIG_CGROUP_SCHED */
 
@@ -321,6 +317,9 @@ struct cfs_rq {
 
         u64 exec_clock;
         u64 min_vruntime;
+#ifndef CONFIG_64BIT
+        u64 min_vruntime_copy;
+#endif
 
         struct rb_root tasks_timeline;
         struct rb_node *rb_leftmost;
@@ -332,9 +331,11 @@ struct cfs_rq {
          * 'curr' points to currently running entity on this cfs_rq.
          * It is set to NULL otherwise (i.e when none are currently running).
          */
-        struct sched_entity *curr, *next, *last;
+        struct sched_entity *curr, *next, *last, *skip;
 
+#ifdef  CONFIG_SCHED_DEBUG
         unsigned int nr_spread_over;
+#endif
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
         struct rq *rq;  /* cpu runqueue to which this cfs_rq is attached */
@@ -347,6 +348,7 @@ struct cfs_rq {
          * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
          * list is used during load balance.
          */
+        int on_list;
         struct list_head leaf_cfs_rq_list;
         struct task_group *tg;  /* group that "owns" this runqueue */
 
@@ -365,14 +367,17 @@ struct cfs_rq {
         unsigned long h_load;
 
         /*
-         * this cpu's part of tg->shares
+         * Maintaining per-cpu shares distribution for group scheduling
+         *
+         * load_stamp is the last time we updated the load average
+         * load_last is the last time we updated the load average and saw load
+         * load_unacc_exec_time is currently unaccounted execution time
          */
-        unsigned long shares;
+        u64 load_avg;
+        u64 load_period;
+        u64 load_stamp, load_last, load_unacc_exec_time;
 
-        /*
-         * load.weight at the time we set shares
-         */
-        unsigned long rq_weight;
+        unsigned long load_contribution;
 #endif
 #endif
 };
@@ -428,6 +433,7 @@ struct litmus_rq {
  */
 struct root_domain {
         atomic_t refcount;
+        struct rcu_head rcu;
         cpumask_var_t span;
         cpumask_var_t online;
 
@@ -437,9 +443,7 @@ struct root_domain {
          */
         cpumask_var_t rto_mask;
         atomic_t rto_count;
-#ifdef CONFIG_SMP
         struct cpupri cpupri;
-#endif
 };
 
 /*
@@ -448,7 +452,7 @@ struct root_domain {
  */
 static struct root_domain def_root_domain;
 
-#endif
+#endif /* CONFIG_SMP */
 
 /*
  * This is the main, per-CPU runqueue data structure.
@@ -473,7 +477,7 @@ struct rq {
         u64 nohz_stamp;
         unsigned char nohz_balance_kick;
 #endif
-        unsigned int skip_clock_update;
+        int skip_clock_update;
 
         /* capture load from *all* tasks on this cpu: */
         struct load_weight load;
@@ -500,11 +504,12 @@ struct rq {
          */
         unsigned long nr_uninterruptible;
 
-        struct task_struct *curr, *idle;
+        struct task_struct *curr, *idle, *stop;
         unsigned long next_balance;
         struct mm_struct *prev_mm;
 
         u64 clock;
+        u64 clock_task;
 
         atomic_t nr_iowait;
 
@@ -532,6 +537,10 @@ struct rq {
         u64 avg_idle;
 #endif
 
+#ifdef CONFIG_IRQ_TIME_ACCOUNTING
+        u64 prev_irq_time;
+#endif
+
         /* calc_load related fields */
         unsigned long calc_load_update;
         long calc_load_active;
@@ -561,32 +570,17 @@ struct rq {
         /* try_to_wake_up() stats */
         unsigned int ttwu_count;
         unsigned int ttwu_local;
+#endif
 
-        /* BKL stats */
-        unsigned int bkl_count;
+#ifdef CONFIG_SMP
+        struct task_struct *wake_list;
 #endif
 };
 
 static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
 
-static inline
-void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
-{
-        rq->curr->sched_class->check_preempt_curr(rq, p, flags);
 
-        /*
-         * A queue event has occurred, and we're going to schedule.  In
-         * this case, we can save a useless back to back clock update.
-         */
-        /* LITMUS^RT: turning off the clock update is buggy in Linux 2.6.36;
-         * the scheduler can "forget" to renable the runqueue clock in some
-         * cases. LITMUS^RT amplifies the effects of this problem. Hence, we
-         * turn it off to avoid stalling clocks. */
-        /*
-        if (test_tsk_need_resched(p))
-                rq->skip_clock_update = 1;
-        */
-}
+static void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags);
 
 static inline int cpu_of(struct rq *rq)
 {
@@ -599,7 +593,7 @@ static inline int cpu_of(struct rq *rq)
 
 #define rcu_dereference_check_sched_domain(p) \
         rcu_dereference_check((p), \
-                              rcu_read_lock_sched_held() || \
+                              rcu_read_lock_held() || \
                               lockdep_is_held(&sched_domains_mutex))
 
 /*
@@ -623,18 +617,22 @@ static inline int cpu_of(struct rq *rq)
 /*
  * Return the group to which this tasks belongs.
  *
- * We use task_subsys_state_check() and extend the RCU verification
- * with lockdep_is_held(&task_rq(p)->lock) because cpu_cgroup_attach()
- * holds that lock for each task it moves into the cgroup. Therefore
- * by holding that lock, we pin the task to the current cgroup.
+ * We use task_subsys_state_check() and extend the RCU verification with
+ * pi->lock and rq->lock because cpu_cgroup_attach() holds those locks for each
+ * task it moves into the cgroup. Therefore by holding either of those locks,
+ * we pin the task to the current cgroup.
  */
 static inline struct task_group *task_group(struct task_struct *p)
 {
+        struct task_group *tg;
         struct cgroup_subsys_state *css;
 
         css = task_subsys_state_check(p, cpu_cgroup_subsys_id,
+                        lockdep_is_held(&p->pi_lock) ||
                         lockdep_is_held(&task_rq(p)->lock));
-        return container_of(css, struct task_group, css);
+        tg = container_of(css, struct task_group, css);
+
+        return autogroup_task_group(p, tg);
 }
 
 /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
@@ -661,10 +659,18 @@ static inline struct task_group *task_group(struct task_struct *p)
 
 #endif /* CONFIG_CGROUP_SCHED */
 
-inline void update_rq_clock(struct rq *rq)
+static void update_rq_clock_task(struct rq *rq, s64 delta);
+
+static void update_rq_clock(struct rq *rq)
 {
-        if (!rq->skip_clock_update)
-                rq->clock = sched_clock_cpu(cpu_of(rq));
+        s64 delta;
+
+        if (rq->skip_clock_update > 0)
+                return;
+
+        delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
+        rq->clock += delta;
+        update_rq_clock_task(rq, delta);
 }
 
 /*
@@ -677,10 +683,9 @@ inline void update_rq_clock(struct rq *rq)
 #endif
 
 /**
- * runqueue_is_locked
+ * runqueue_is_locked - Returns true if the current cpu runqueue is locked
  * @cpu: the processor in question.
  *
- * Returns true if the current cpu runqueue is locked.
  * This interface allows printk to be called with the runqueue lock
  * held and know whether or not it is OK to wake up the klogd.
  */
@@ -741,7 +746,7 @@ sched_feat_write(struct file *filp, const char __user *ubuf,
                 size_t cnt, loff_t *ppos)
 {
         char buf[64];
-        char *cmp = buf;
+        char *cmp;
         int neg = 0;
         int i;
 
@@ -752,16 +757,15 @@ sched_feat_write(struct file *filp, const char __user *ubuf,
                 return -EFAULT;
 
         buf[cnt] = 0;
+        cmp = strstrip(buf);
 
-        if (strncmp(buf, "NO_", 3) == 0) {
+        if (strncmp(cmp, "NO_", 3) == 0) {
                 neg = 1;
                 cmp += 3;
         }
 
         for (i = 0; sched_feat_names[i]; i++) {
-                int len = strlen(sched_feat_names[i]);
-
-                if (strncmp(cmp, sched_feat_names[i], len) == 0) {
+                if (strcmp(cmp, sched_feat_names[i]) == 0) {
                         if (neg)
                                 sysctl_sched_features &= ~(1UL << i);
                         else
@@ -811,20 +815,6 @@ late_initcall(sched_init_debug);
 const_debug unsigned int sysctl_sched_nr_migrate = 32;
 
 /*
- * ratelimit for updating the group shares.
- * default: 0.25ms
- */
-unsigned int sysctl_sched_shares_ratelimit = 250000;
-unsigned int normalized_sysctl_sched_shares_ratelimit = 250000;
-
-/*
- * Inject some fuzzyness into changing the per-cpu group shares
- * this avoids remote rq-locks at the expense of fairness.
- * default: 4
- */
-unsigned int sysctl_sched_shares_thresh = 4;
-
-/*
  * period over which we average the RT time consumption, measured
  * in ms.
  *
@@ -871,18 +861,39 @@ static inline int task_current(struct rq *rq, struct task_struct *p)
         return rq->curr == p;
 }
 
-#ifndef __ARCH_WANT_UNLOCKED_CTXSW
 static inline int task_running(struct rq *rq, struct task_struct *p)
 {
+#ifdef CONFIG_SMP
+        return p->on_cpu;
+#else
         return task_current(rq, p);
+#endif
 }
 
+#ifndef __ARCH_WANT_UNLOCKED_CTXSW
 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 {
+#ifdef CONFIG_SMP
+        /*
+         * We can optimise this out completely for !SMP, because the
+         * SMP rebalancing from interrupt is the only thing that cares
+         * here.
+         */
+        next->on_cpu = 1;
+#endif
 }
 
 static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 {
+#ifdef CONFIG_SMP
+        /*
+         * After ->on_cpu is cleared, the task can be moved to a different CPU.
+         * We must ensure this doesn't happen until the switch is completely
+         * finished.
+         */
+        smp_wmb();
+        prev->on_cpu = 0;
+#endif
 #ifdef CONFIG_DEBUG_SPINLOCK
         /* this is a valid case when another task releases the spinlock */
         rq->lock.owner = current;
@@ -898,15 +909,6 @@ static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 }
 
 #else /* __ARCH_WANT_UNLOCKED_CTXSW */
-static inline int task_running(struct rq *rq, struct task_struct *p)
-{
-#ifdef CONFIG_SMP
-        return p->oncpu;
-#else
-        return task_current(rq, p);
-#endif
-}
-
 static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
 {
 #ifdef CONFIG_SMP
@@ -915,7 +917,7 @@ static inline void prepare_lock_switch(struct rq *rq, struct task_struct *next)
          * SMP rebalancing from interrupt is the only thing that cares
          * here.
          */
-        next->oncpu = 1;
+        next->on_cpu = 1;
 #endif
 #ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
         raw_spin_unlock_irq(&rq->lock);
@@ -928,12 +930,12 @@ static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 {
 #ifdef CONFIG_SMP
         /*
-         * After ->oncpu is cleared, the task can be moved to a different CPU.
+         * After ->on_cpu is cleared, the task can be moved to a different CPU.
          * We must ensure this doesn't happen until the switch is completely
          * finished.
          */
         smp_wmb();
-        prev->oncpu = 0;
+        prev->on_cpu = 0;
 #endif
 #ifndef __ARCH_WANT_INTERRUPTS_ON_CTXSW
         local_irq_enable();
@@ -942,23 +944,15 @@ static inline void finish_lock_switch(struct rq *rq, struct task_struct *prev)
 #endif /* __ARCH_WANT_UNLOCKED_CTXSW */
 
 /*
- * Check whether the task is waking, we use this to synchronize ->cpus_allowed
- * against ttwu().
- */
-static inline int task_is_waking(struct task_struct *p)
-{
-        return unlikely(p->state == TASK_WAKING);
-}
-
-/*
- * __task_rq_lock - lock the runqueue a given task resides on.
- * Must be called interrupts disabled.
+ * __task_rq_lock - lock the rq @p resides on.
  */
 static inline struct rq *__task_rq_lock(struct task_struct *p)
         __acquires(rq->lock)
 {
         struct rq *rq;
 
+        lockdep_assert_held(&p->pi_lock);
+
         for (;;) {
                 rq = task_rq(p);
                 raw_spin_lock(&rq->lock);
@@ -969,22 +963,22 @@ static inline struct rq *__task_rq_lock(struct task_struct *p)
 }
 
 /*
- * task_rq_lock - lock the runqueue a given task resides on and disable
- * interrupts. Note the ordering: we can safely lookup the task_rq without
- * explicitly disabling preemption.
+ * task_rq_lock - lock p->pi_lock and lock the rq @p resides on.
  */
 static struct rq *task_rq_lock(struct task_struct *p, unsigned long *flags)
+        __acquires(p->pi_lock)
         __acquires(rq->lock)
 {
         struct rq *rq;
 
         for (;;) {
-                local_irq_save(*flags);
+                raw_spin_lock_irqsave(&p->pi_lock, *flags);
                 rq = task_rq(p);
                 raw_spin_lock(&rq->lock);
                 if (likely(rq == task_rq(p)))
                         return rq;
-                raw_spin_unlock_irqrestore(&rq->lock, *flags);
+                raw_spin_unlock(&rq->lock);
+                raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
         }
 }
 
@@ -994,10 +988,13 @@ static void __task_rq_unlock(struct rq *rq)
         raw_spin_unlock(&rq->lock);
 }
 
-static inline void task_rq_unlock(struct rq *rq, unsigned long *flags)
+static inline void
+task_rq_unlock(struct rq *rq, struct task_struct *p, unsigned long *flags)
         __releases(rq->lock)
+        __releases(p->pi_lock)
 {
-        raw_spin_unlock_irqrestore(&rq->lock, *flags);
+        raw_spin_unlock(&rq->lock);
+        raw_spin_unlock_irqrestore(&p->pi_lock, *flags);
 }
 
 /*
@@ -1227,11 +1224,17 @@ int get_nohz_timer_target(void)
         int i;
         struct sched_domain *sd;
 
+        rcu_read_lock();
         for_each_domain(cpu, sd) {
-                for_each_cpu(i, sched_domain_span(sd))
-                        if (!idle_cpu(i))
-                                return i;
+                for_each_cpu(i, sched_domain_span(sd)) {
+                        if (!idle_cpu(i)) {
+                                cpu = i;
+                                goto unlock;
+                        }
+                }
         }
+unlock:
+        rcu_read_unlock();
         return cpu;
 }
 /*
@@ -1341,15 +1344,27 @@ calc_delta_mine(unsigned long delta_exec, unsigned long weight,
 {
         u64 tmp;
 
+        /*
+         * weight can be less than 2^SCHED_LOAD_RESOLUTION for task group sched
+         * entities since MIN_SHARES = 2. Treat weight as 1 if less than
+         * 2^SCHED_LOAD_RESOLUTION.
+         */
+        if (likely(weight > (1UL << SCHED_LOAD_RESOLUTION)))
+                tmp = (u64)delta_exec * scale_load_down(weight);
+        else
+                tmp = (u64)delta_exec;
+
         if (!lw->inv_weight) {
-                if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))
+                unsigned long w = scale_load_down(lw->weight);
+
+                if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
                         lw->inv_weight = 1;
+                else if (unlikely(!w))
+                        lw->inv_weight = WMULT_CONST;
                 else
-                        lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2)
-                                / (lw->weight+1);
+                        lw->inv_weight = WMULT_CONST / w;
         }
 
-        tmp = (u64)delta_exec * weight;
         /*
          * Check whether we'd overflow the 64-bit multiplication:
          */
@@ -1374,6 +1389,12 @@ static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
         lw->inv_weight = 0;
 }
 
+static inline void update_load_set(struct load_weight *lw, unsigned long w)
+{
+        lw->weight = w;
+        lw->inv_weight = 0;
+}
+
 /*
  * To aid in avoiding the subversion of "niceness" due to uneven distribution
  * of tasks with abnormal "nice" values across CPUs the contribution that
@@ -1562,101 +1583,6 @@ static unsigned long cpu_avg_load_per_task(int cpu)
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 
-static __read_mostly unsigned long __percpu *update_shares_data;
-
-static void __set_se_shares(struct sched_entity *se, unsigned long shares);
-
-/*
- * Calculate and set the cpu's group shares.
- */
-static void update_group_shares_cpu(struct task_group *tg, int cpu,
-                                    unsigned long sd_shares,
-                                    unsigned long sd_rq_weight,
-                                    unsigned long *usd_rq_weight)
-{
-        unsigned long shares, rq_weight;
-        int boost = 0;
-
-        rq_weight = usd_rq_weight[cpu];
-        if (!rq_weight) {
-                boost = 1;
-                rq_weight = NICE_0_LOAD;
-        }
-
-        /*
-         *             \Sum_j shares_j * rq_weight_i
-         * shares_i =  -----------------------------
-         *                  \Sum_j rq_weight_j
-         */
-        shares = (sd_shares * rq_weight) / sd_rq_weight;
-        shares = clamp_t(unsigned long, shares, MIN_SHARES, MAX_SHARES);
-
-        if (abs(shares - tg->se[cpu]->load.weight) >
-                        sysctl_sched_shares_thresh) {
-                struct rq *rq = cpu_rq(cpu);
-                unsigned long flags;
-
-                raw_spin_lock_irqsave(&rq->lock, flags);
-                tg->cfs_rq[cpu]->rq_weight = boost ? 0 : rq_weight;
-                tg->cfs_rq[cpu]->shares = boost ? 0 : shares;
-                __set_se_shares(tg->se[cpu], shares);
-                raw_spin_unlock_irqrestore(&rq->lock, flags);
-        }
-}
-
-/*
- * Re-compute the task group their per cpu shares over the given domain.
- * This needs to be done in a bottom-up fashion because the rq weight of a
- * parent group depends on the shares of its child groups.
- */
-static int tg_shares_up(struct task_group *tg, void *data)
-{
-        unsigned long weight, rq_weight = 0, sum_weight = 0, shares = 0;
-        unsigned long *usd_rq_weight;
-        struct sched_domain *sd = data;
-        unsigned long flags;
-        int i;
-
-        if (!tg->se[0])
-                return 0;
-
-        local_irq_save(flags);
-        usd_rq_weight = per_cpu_ptr(update_shares_data, smp_processor_id());
-
-        for_each_cpu(i, sched_domain_span(sd)) {
-                weight = tg->cfs_rq[i]->load.weight;
-                usd_rq_weight[i] = weight;
-
-                rq_weight += weight;
-                /*
-                 * If there are currently no tasks on the cpu pretend there
-                 * is one of average load so that when a new task gets to
-                 * run here it will not get delayed by group starvation.
-                 */
-                if (!weight)
-                        weight = NICE_0_LOAD;
-
-                sum_weight += weight;
-                shares += tg->cfs_rq[i]->shares;
-        }
-
-        if (!rq_weight)
-                rq_weight = sum_weight;
-
-        if ((!shares && rq_weight) || shares > tg->shares)
-                shares = tg->shares;
-
-        if (!sd->parent || !(sd->parent->flags & SD_LOAD_BALANCE))
-                shares = tg->shares;
-
-        for_each_cpu(i, sched_domain_span(sd))
-                update_group_shares_cpu(tg, i, shares, rq_weight, usd_rq_weight);
-
-        local_irq_restore(flags);
-
-        return 0;
-}
-
 /*
  * Compute the cpu's hierarchical load factor for each task group.
  * This needs to be done in a top-down fashion because the load of a child
@@ -1671,7 +1597,7 @@ static int tg_load_down(struct task_group *tg, void *data)
                 load = cpu_rq(cpu)->load.weight;
         } else {
                 load = tg->parent->cfs_rq[cpu]->h_load;
-                load *= tg->cfs_rq[cpu]->shares;
+                load *= tg->se[cpu]->load.weight;
                 load /= tg->parent->cfs_rq[cpu]->load.weight + 1;
         }
 
@@ -1680,34 +1606,11 @@ static int tg_load_down(struct task_group *tg, void *data)
         return 0;
 }
 
-static void update_shares(struct sched_domain *sd)
-{
-        s64 elapsed;
-        u64 now;
-
-        if (root_task_group_empty())
-                return;
-
-        now = local_clock();
-        elapsed = now - sd->last_update;
-
-        if (elapsed >= (s64)(u64)sysctl_sched_shares_ratelimit) {
-                sd->last_update = now;
-                walk_tg_tree(tg_nop, tg_shares_up, sd);
-        }
-}
-
 static void update_h_load(long cpu)
 {
         walk_tg_tree(tg_load_down, tg_nop, (void *)cpu);
 }
 
-#else
-
-static inline void update_shares(struct sched_domain *sd)
-{
-}
-
 #endif
 
 #ifdef CONFIG_PREEMPT
@@ -1827,15 +1730,39 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
                 __release(rq2->lock);
 }
 
-#endif
+#else /* CONFIG_SMP */
 
-#ifdef CONFIG_FAIR_GROUP_SCHED
-static void cfs_rq_set_shares(struct cfs_rq *cfs_rq, unsigned long shares)
+/*
+ * double_rq_lock - safely lock two runqueues
+ *
+ * Note this does not disable interrupts like task_rq_lock,
+ * you need to do so manually before calling.
+ */
+static void double_rq_lock(struct rq *rq1, struct rq *rq2)
+        __acquires(rq1->lock)
+        __acquires(rq2->lock)
 {
-#ifdef CONFIG_SMP
-        cfs_rq->shares = shares;
-#endif
+        BUG_ON(!irqs_disabled());
+        BUG_ON(rq1 != rq2);
+        raw_spin_lock(&rq1->lock);
+        __acquire(rq2->lock);   /* Fake it out ;) */
 }
+
+/*
+ * double_rq_unlock - safely unlock two runqueues
+ *
+ * Note this does not restore interrupts like task_rq_unlock,
+ * you need to do so manually after calling.
+ */
+static void double_rq_unlock(struct rq *rq1, struct rq *rq2)
+        __releases(rq1->lock)
+        __releases(rq2->lock)
+{
+        BUG_ON(rq1 != rq2);
+        raw_spin_unlock(&rq1->lock);
+        __release(rq2->lock);
+}
+
 #endif
 
 static void calc_load_account_idle(struct rq *this_rq);
@@ -1877,23 +1804,20 @@ static void dec_nr_running(struct rq *rq)
 
 static void set_load_weight(struct task_struct *p)
 {
-        if (task_has_rt_policy(p)) {
-                p->se.load.weight = 0;
-                p->se.load.inv_weight = WMULT_CONST;
-                return;
-        }
+        int prio = p->static_prio - MAX_RT_PRIO;
+        struct load_weight *load = &p->se.load;
 
         /*
          * SCHED_IDLE tasks get minimal weight:
          */
         if (p->policy == SCHED_IDLE) {
-                p->se.load.weight = WEIGHT_IDLEPRIO;
-                p->se.load.inv_weight = WMULT_IDLEPRIO;
+                load->weight = scale_load(WEIGHT_IDLEPRIO);
+                load->inv_weight = WMULT_IDLEPRIO;
                 return;
         }
 
-        p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
-        p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
+        load->weight = scale_load(prio_to_weight[prio]);
+        load->inv_weight = prio_to_wmult[prio];
 }
 
 static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
@@ -1901,7 +1825,6 @@ static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
         update_rq_clock(rq);
         sched_info_queued(p);
         p->sched_class->enqueue_task(rq, p, flags);
-        p->se.on_rq = 1;
 }
 
 static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
@@ -1909,7 +1832,6 @@ static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
         update_rq_clock(rq);
         sched_info_dequeued(p);
         p->sched_class->dequeue_task(rq, p, flags);
-        p->se.on_rq = 0;
 }
 
 /*
@@ -1936,14 +1858,227 @@ static void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
         dec_nr_running(rq);
 }
 
+#ifdef CONFIG_IRQ_TIME_ACCOUNTING
+
+/*
+ * There are no locks covering percpu hardirq/softirq time.
+ * They are only modified in account_system_vtime, on corresponding CPU
+ * with interrupts disabled. So, writes are safe.
+ * They are read and saved off onto struct rq in update_rq_clock().
+ * This may result in other CPU reading this CPU's irq time and can
+ * race with irq/account_system_vtime on this CPU. We would either get old
+ * or new value with a side effect of accounting a slice of irq time to wrong
+ * task when irq is in progress while we read rq->clock. That is a worthy
+ * compromise in place of having locks on each irq in account_system_time.
+ */
+static DEFINE_PER_CPU(u64, cpu_hardirq_time);
+static DEFINE_PER_CPU(u64, cpu_softirq_time);
+
+static DEFINE_PER_CPU(u64, irq_start_time);
+static int sched_clock_irqtime;
+
+void enable_sched_clock_irqtime(void)
+{
+        sched_clock_irqtime = 1;
+}
+
+void disable_sched_clock_irqtime(void)
+{
+        sched_clock_irqtime = 0;
+}
+
+#ifndef CONFIG_64BIT
+static DEFINE_PER_CPU(seqcount_t, irq_time_seq);
+
+static inline void irq_time_write_begin(void)
+{
+        __this_cpu_inc(irq_time_seq.sequence);
+        smp_wmb();
+}
+
+static inline void irq_time_write_end(void)
+{
+        smp_wmb();
+        __this_cpu_inc(irq_time_seq.sequence);
+}
+
+static inline u64 irq_time_read(int cpu)
+{
+        u64 irq_time;
+        unsigned seq;
+
+        do {
+                seq = read_seqcount_begin(&per_cpu(irq_time_seq, cpu));
+                irq_time = per_cpu(cpu_softirq_time, cpu) +
+                           per_cpu(cpu_hardirq_time, cpu);
+        } while (read_seqcount_retry(&per_cpu(irq_time_seq, cpu), seq));
+
+        return irq_time;
+}
+#else /* CONFIG_64BIT */
+static inline void irq_time_write_begin(void)
+{
+}
+
+static inline void irq_time_write_end(void)
+{
+}
+
+static inline u64 irq_time_read(int cpu)
+{
+        return per_cpu(cpu_softirq_time, cpu) + per_cpu(cpu_hardirq_time, cpu);
+}
+#endif /* CONFIG_64BIT */
+
+/*
+ * Called before incrementing preempt_count on {soft,}irq_enter
+ * and before decrementing preempt_count on {soft,}irq_exit.
+ */
+void account_system_vtime(struct task_struct *curr)
+{
+        unsigned long flags;
+        s64 delta;
+        int cpu;
+
+        if (!sched_clock_irqtime)
+                return;
+
+        local_irq_save(flags);
+
+        cpu = smp_processor_id();
+        delta = sched_clock_cpu(cpu) - __this_cpu_read(irq_start_time);
+        __this_cpu_add(irq_start_time, delta);
+
+        irq_time_write_begin();
+        /*
+         * We do not account for softirq time from ksoftirqd here.
+         * We want to continue accounting softirq time to ksoftirqd thread
+         * in that case, so as not to confuse scheduler with a special task
+         * that do not consume any time, but still wants to run.
+         */
+        if (hardirq_count())
+                __this_cpu_add(cpu_hardirq_time, delta);
+        else if (in_serving_softirq() && curr != this_cpu_ksoftirqd())
+                __this_cpu_add(cpu_softirq_time, delta);
+
+        irq_time_write_end();
+        local_irq_restore(flags);
+}
+EXPORT_SYMBOL_GPL(account_system_vtime);
+
+static void update_rq_clock_task(struct rq *rq, s64 delta)
+{
+        s64 irq_delta;
+
+        irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;
+
+        /*
+         * Since irq_time is only updated on {soft,}irq_exit, we might run into
+         * this case when a previous update_rq_clock() happened inside a
+         * {soft,}irq region.
+         *
+         * When this happens, we stop ->clock_task and only update the
+         * prev_irq_time stamp to account for the part that fit, so that a next
+         * update will consume the rest. This ensures ->clock_task is
+         * monotonic.
+         *
+         * It does however cause some slight miss-attribution of {soft,}irq
+         * time, a more accurate solution would be to update the irq_time using
+         * the current rq->clock timestamp, except that would require using
+         * atomic ops.
+         */
+        if (irq_delta > delta)
+                irq_delta = delta;
+
+        rq->prev_irq_time += irq_delta;
+        delta -= irq_delta;
+        rq->clock_task += delta;
+
+        if (irq_delta && sched_feat(NONIRQ_POWER))
+                sched_rt_avg_update(rq, irq_delta);
+}
+
+static int irqtime_account_hi_update(void)
+{
+        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+        unsigned long flags;
+        u64 latest_ns;
+        int ret = 0;
+
+        local_irq_save(flags);
+        latest_ns = this_cpu_read(cpu_hardirq_time);
+        if (cputime64_gt(nsecs_to_cputime64(latest_ns), cpustat->irq))
+                ret = 1;
+        local_irq_restore(flags);
+        return ret;
+}
+
+static int irqtime_account_si_update(void)
+{
+        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+        unsigned long flags;
+        u64 latest_ns;
+        int ret = 0;
+
+        local_irq_save(flags);
+        latest_ns = this_cpu_read(cpu_softirq_time);
+        if (cputime64_gt(nsecs_to_cputime64(latest_ns), cpustat->softirq))
+                ret = 1;
+        local_irq_restore(flags);
+        return ret;
+}
+
+#else /* CONFIG_IRQ_TIME_ACCOUNTING */
+
+#define sched_clock_irqtime     (0)
+
+static void update_rq_clock_task(struct rq *rq, s64 delta)
+{
+        rq->clock_task += delta;
+}
+
+#endif /* CONFIG_IRQ_TIME_ACCOUNTING */
+
 #include "sched_idletask.c"
 #include "sched_fair.c"
 #include "sched_rt.c"
+#include "sched_autogroup.c"
+#include "sched_stoptask.c"
 #include "../litmus/sched_litmus.c"
 #ifdef CONFIG_SCHED_DEBUG
 # include "sched_debug.c"
 #endif
 
+void sched_set_stop_task(int cpu, struct task_struct *stop)
+{
+        struct sched_param param = { .sched_priority = MAX_RT_PRIO - 1 };
+        struct task_struct *old_stop = cpu_rq(cpu)->stop;
+
+        if (stop) {
+                /*
+                 * Make it appear like a SCHED_FIFO task, its something
+                 * userspace knows about and won't get confused about.
+                 *
+                 * Also, it will make PI more or less work without too
+                 * much confusion -- but then, stop work should not
+                 * rely on PI working anyway.
+                 */
+                sched_setscheduler_nocheck(stop, SCHED_FIFO, &param);
+
+                stop->sched_class = &stop_sched_class;
+        }
+
+        cpu_rq(cpu)->stop = stop;
+
+        if (old_stop) {
+                /*
+                 * Reset it back to a normal scheduling class so that
+                 * it can die in pieces.
+                 */
+                old_stop->sched_class = &rt_sched_class;
+        }
+}
+
 /*
  * __normal_prio - return the priority that is based on the static prio
  */
@@ -2001,14 +2136,43 @@ inline int task_curr(const struct task_struct *p)
 
 static inline void check_class_changed(struct rq *rq, struct task_struct *p,
                                        const struct sched_class *prev_class,
-                                       int oldprio, int running)
+                                       int oldprio)
 {
         if (prev_class != p->sched_class) {
                 if (prev_class->switched_from)
-                        prev_class->switched_from(rq, p, running);
-                p->sched_class->switched_to(rq, p, running);
-        } else
-                p->sched_class->prio_changed(rq, p, oldprio, running);
+                        prev_class->switched_from(rq, p);
+                p->sched_class->switched_to(rq, p);
+        } else if (oldprio != p->prio)
+                p->sched_class->prio_changed(rq, p, oldprio);
+}
+
+static void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
+{
+        const struct sched_class *class;
+
+        if (p->sched_class == rq->curr->sched_class) {
+                rq->curr->sched_class->check_preempt_curr(rq, p, flags);
+        } else {
+                for_each_class(class) {
+                        if (class == rq->curr->sched_class)
+                                break;
+                        if (class == p->sched_class) {
+                                resched_task(rq->curr);
+                                break;
+                        }
+                }
+        }
+
+        /*
+         * A queue event has occurred, and we're going to schedule.  In
+         * this case, we can save a useless back to back clock update.
+         */
+        /* LITMUS^RT:
+         * The "disable-clock-update" approach was buggy in Linux 2.6.36.
+         * The issue has been solved in 2.6.37.
+         */
+        if (rq->curr->on_rq && test_tsk_need_resched(rq->curr))
+                rq->skip_clock_update = 1;
 }
 
 #ifdef CONFIG_SMP
@@ -2023,6 +2187,9 @@ task_hot(struct task_struct *p, u64 now, struct sched_domain *sd)
         if (p->sched_class != &fair_sched_class)
                 return 0;
 
+        if (unlikely(p->policy == SCHED_IDLE))
+                return 0;
+
         /*
          * Buddy candidates are cache hot:
          */
@@ -2050,6 +2217,21 @@ void set_task_cpu(struct task_struct *p, unsigned int new_cpu)
          */
         WARN_ON_ONCE(p->state != TASK_RUNNING && p->state != TASK_WAKING &&
                         !(task_thread_info(p)->preempt_count & PREEMPT_ACTIVE));
+
+#ifdef CONFIG_LOCKDEP
+        /*
+         * The caller should hold either p->pi_lock or rq->lock, when changing
+         * a task's CPU. ->pi_lock for waking tasks, rq->lock for runnable tasks.
+         *
+         * sched_move_task() holds both and thus holding either pins the cgroup,
+         * see set_task_rq().
+         *
+         * Furthermore, all task_rq users should acquire both locks, see
+         * task_rq_lock().
+         */
+        WARN_ON_ONCE(debug_locks && !(lockdep_is_held(&p->pi_lock) ||
+                                      lockdep_is_held(&task_rq(p)->lock)));
+#endif
 #endif
 
         trace_sched_migrate_task(p, new_cpu);
@@ -2070,21 +2252,6 @@ struct migration_arg {
 static int migration_cpu_stop(void *data);
 
 /*
- * The task's runqueue lock must be held.
- * Returns true if you have to wait for migration thread.
- */
-static bool migrate_task(struct task_struct *p, int dest_cpu)
-{
-        struct rq *rq = task_rq(p);
-
-        /*
-         * If the task is not on a runqueue (and not running), then
-         * the next wake-up will properly place the task.
-         */
-        return p->se.on_rq || task_running(rq, p);
-}
-
-/*
  * wait_task_inactive - wait for a thread to unschedule.
  *
  * If @match_state is nonzero, it's the @p->state value just checked and
@@ -2141,11 +2308,11 @@ unsigned long wait_task_inactive(struct task_struct *p, long match_state)
                 rq = task_rq_lock(p, &flags);
                 trace_sched_wait_task(p);
                 running = task_running(rq, p);
-                on_rq = p->se.on_rq;
+                on_rq = p->on_rq;
                 ncsw = 0;
                 if (!match_state || p->state == match_state)
                         ncsw = p->nvcsw | LONG_MIN; /* sets MSB */
-                task_rq_unlock(rq, &flags);
+                task_rq_unlock(rq, p, &flags);
 
                 /*
                  * If it changed from the expected state, bail out now.
@@ -2174,7 +2341,10 @@ unsigned long wait_task_inactive(struct task_struct *p, long match_state)
                  * yield - it could be a while.
                  */
                 if (unlikely(on_rq)) {
-                        schedule_timeout_uninterruptible(1);
+                        ktime_t to = ktime_set(0, NSEC_PER_SEC/HZ);
+
+                        set_current_state(TASK_UNINTERRUPTIBLE);
+                        schedule_hrtimeout(&to, HRTIMER_MODE_REL);
                         continue;
                 }
 
@@ -2196,7 +2366,7 @@ unsigned long wait_task_inactive(struct task_struct *p, long match_state)
  * Cause a process which is running on another CPU to enter
  * kernel-mode, without any delay. (to get signals handled.)
  *
- * NOTE: this function doesnt have to take the runqueue lock,
+ * NOTE: this function doesn't have to take the runqueue lock,
  * because all it wants to ensure is that the remote task enters
  * the kernel. If the IPI races and the task has been migrated
  * to another CPU then no harm is done and the purpose has been
@@ -2215,30 +2385,9 @@ void kick_process(struct task_struct *p)
 EXPORT_SYMBOL_GPL(kick_process);
 #endif /* CONFIG_SMP */
 
-/**
- * task_oncpu_function_call - call a function on the cpu on which a task runs
- * @p:          the task to evaluate
- * @func:       the function to be called
- * @info:       the function call argument
- *
- * Calls the function @func when the task is currently running. This might
- * be on the current CPU, which just calls the function directly
- */
-void task_oncpu_function_call(struct task_struct *p,
-                              void (*func) (void *info), void *info)
-{
-        int cpu;
-
-        preempt_disable();
-        cpu = task_cpu(p);
-        if (task_curr(p))
-                smp_call_function_single(cpu, func, info, 1);
-        preempt_enable();
-}
-
 #ifdef CONFIG_SMP
 /*
- * ->cpus_allowed is protected by either TASK_WAKING or rq->lock held.
+ * ->cpus_allowed is protected by both rq->lock and p->pi_lock
  */
 static int select_fallback_rq(int cpu, struct task_struct *p)
 {
@@ -2256,30 +2405,27 @@ static int select_fallback_rq(int cpu, struct task_struct *p)
                 return dest_cpu;
 
         /* No more Mr. Nice Guy. */
-        if (unlikely(dest_cpu >= nr_cpu_ids)) {
-                dest_cpu = cpuset_cpus_allowed_fallback(p);
-                /*
-                 * Don't tell them about moving exiting tasks or
-                 * kernel threads (both mm NULL), since they never
-                 * leave kernel.
-                 */
-                if (p->mm && printk_ratelimit()) {
-                        printk(KERN_INFO "process %d (%s) no "
-                               "longer affine to cpu%d\n",
-                               task_pid_nr(p), p->comm, cpu);
-                }
+        dest_cpu = cpuset_cpus_allowed_fallback(p);
+        /*
+         * Don't tell them about moving exiting tasks or
+         * kernel threads (both mm NULL), since they never
+         * leave kernel.
+         */
+        if (p->mm && printk_ratelimit()) {
+                printk(KERN_INFO "process %d (%s) no longer affine to cpu%d\n",
+                                task_pid_nr(p), p->comm, cpu);
         }
 
         return dest_cpu;
 }
 
 /*
- * The caller (fork, wakeup) owns TASK_WAKING, ->cpus_allowed is stable.
+ * The caller (fork, wakeup) owns p->pi_lock, ->cpus_allowed is stable.
  */
 static inline
-int select_task_rq(struct rq *rq, struct task_struct *p, int sd_flags, int wake_flags)
+int select_task_rq(struct task_struct *p, int sd_flags, int wake_flags)
 {
-        int cpu = p->sched_class->select_task_rq(rq, p, sd_flags, wake_flags);
+        int cpu = p->sched_class->select_task_rq(p, sd_flags, wake_flags);
 
         /*
          * In order not to call set_task_cpu() on a blocking task we need
@@ -2305,27 +2451,63 @@ static void update_avg(u64 *avg, u64 sample)
 }
 #endif
 
-static inline void ttwu_activate(struct task_struct *p, struct rq *rq,
-                                 bool is_sync, bool is_migrate, bool is_local,
-                                 unsigned long en_flags)
+static void
+ttwu_stat(struct task_struct *p, int cpu, int wake_flags)
 {
-        schedstat_inc(p, se.statistics.nr_wakeups);
-        if (is_sync)
-                schedstat_inc(p, se.statistics.nr_wakeups_sync);
-        if (is_migrate)
-                schedstat_inc(p, se.statistics.nr_wakeups_migrate);
-        if (is_local)
+#ifdef CONFIG_SCHEDSTATS
+        struct rq *rq = this_rq();
+
+#ifdef CONFIG_SMP
+        int this_cpu = smp_processor_id();
+
+        if (cpu == this_cpu) {
+                schedstat_inc(rq, ttwu_local);
                 schedstat_inc(p, se.statistics.nr_wakeups_local);
-        else
+        } else {
+                struct sched_domain *sd;
+
                 schedstat_inc(p, se.statistics.nr_wakeups_remote);
+                rcu_read_lock();
+                for_each_domain(this_cpu, sd) {
+                        if (cpumask_test_cpu(cpu, sched_domain_span(sd))) {
+                                schedstat_inc(sd, ttwu_wake_remote);
+                                break;
+                        }
+                }
+                rcu_read_unlock();
+        }
+
+        if (wake_flags & WF_MIGRATED)
+                schedstat_inc(p, se.statistics.nr_wakeups_migrate);
+
+#endif /* CONFIG_SMP */
+
+        schedstat_inc(rq, ttwu_count);
+        schedstat_inc(p, se.statistics.nr_wakeups);
+
+        if (wake_flags & WF_SYNC)
+                schedstat_inc(p, se.statistics.nr_wakeups_sync);
+
+#endif /* CONFIG_SCHEDSTATS */
+}
 
+static void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
+{
         activate_task(rq, p, en_flags);
+        p->on_rq = 1;
+
+        /* if a worker is waking up, notify workqueue */
+        if (p->flags & PF_WQ_WORKER)
+                wq_worker_waking_up(p, cpu_of(rq));
 }
 
-static inline void ttwu_post_activation(struct task_struct *p, struct rq *rq,
-                                        int wake_flags, bool success)
+/*
+ * Mark the task runnable and perform wakeup-preemption.
+ */
+static void
+ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
 {
-        trace_sched_wakeup(p, success);
+        trace_sched_wakeup(p, true);
         check_preempt_curr(rq, p, wake_flags);
 
         p->state = TASK_RUNNING;
@@ -2344,9 +2526,156 @@ static inline void ttwu_post_activation(struct task_struct *p, struct rq *rq,
                 rq->idle_stamp = 0;
         }
 #endif
-        /* if a worker is waking up, notify workqueue */
-        if ((p->flags & PF_WQ_WORKER) && success)
-                wq_worker_waking_up(p, cpu_of(rq));
+}
+
+static void
+ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags)
+{
+#ifdef CONFIG_SMP
+        if (p->sched_contributes_to_load)
+                rq->nr_uninterruptible--;
+#endif
+
+        ttwu_activate(rq, p, ENQUEUE_WAKEUP | ENQUEUE_WAKING);
+        ttwu_do_wakeup(rq, p, wake_flags);
+}
+
+/*
+ * Called in case the task @p isn't fully descheduled from its runqueue,
+ * in this case we must do a remote wakeup. Its a 'light' wakeup though,
+ * since all we need to do is flip p->state to TASK_RUNNING, since
+ * the task is still ->on_rq.
+ */
+static int ttwu_remote(struct task_struct *p, int wake_flags)
+{
+        struct rq *rq;
+        int ret = 0;
+
+        rq = __task_rq_lock(p);
+        if (p->on_rq) {
+                ttwu_do_wakeup(rq, p, wake_flags);
+                ret = 1;
+        }
+        __task_rq_unlock(rq);
+
+        return ret;
+}
+
+#ifdef CONFIG_SMP
+static void sched_ttwu_do_pending(struct task_struct *list)
+{
+        struct rq *rq = this_rq();
+
+        raw_spin_lock(&rq->lock);
+
+        while (list) {
+                struct task_struct *p = list;
+                list = list->wake_entry;
+                ttwu_do_activate(rq, p, 0);
+        }
+
+        raw_spin_unlock(&rq->lock);
+}
+
+#ifdef CONFIG_HOTPLUG_CPU
+
+static void sched_ttwu_pending(void)
+{
+        struct rq *rq = this_rq();
+        struct task_struct *list = xchg(&rq->wake_list, NULL);
+
+        if (!list)
+                return;
+
+        sched_ttwu_do_pending(list);
+}
+
+#endif /* CONFIG_HOTPLUG_CPU */
+
+void scheduler_ipi(void)
+{
+        struct rq *rq = this_rq();
+        struct task_struct *list = xchg(&rq->wake_list, NULL);
+
+        if (!list)
+                return;
+
+        /*
+         * Not all reschedule IPI handlers call irq_enter/irq_exit, since
+         * traditionally all their work was done from the interrupt return
+         * path. Now that we actually do some work, we need to make sure
+         * we do call them.
+         *
+         * Some archs already do call them, luckily irq_enter/exit nest
+         * properly.
+         *
+         * Arguably we should visit all archs and update all handlers,
+         * however a fair share of IPIs are still resched only so this would
+         * somewhat pessimize the simple resched case.
+         */
+        irq_enter();
+        sched_ttwu_do_pending(list);
+        irq_exit();
+}
+
+static void ttwu_queue_remote(struct task_struct *p, int cpu)
+{
+        struct rq *rq = cpu_rq(cpu);
+        struct task_struct *next = rq->wake_list;
+
+        for (;;) {
+                struct task_struct *old = next;
+
+                p->wake_entry = next;
+                next = cmpxchg(&rq->wake_list, old, p);
+                if (next == old)
+                        break;
+        }
+
+        if (!next)
+                smp_send_reschedule(cpu);
+}
+
+#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
+static int ttwu_activate_remote(struct task_struct *p, int wake_flags)
+{
+        struct rq *rq;
+        int ret = 0;
+
+        rq = __task_rq_lock(p);
+        if (p->on_cpu) {
+                ttwu_activate(rq, p, ENQUEUE_WAKEUP);
+                ttwu_do_wakeup(rq, p, wake_flags);
+                ret = 1;
+        }
+        __task_rq_unlock(rq);
+
+        return ret;
+
+}
+#endif /* __ARCH_WANT_INTERRUPTS_ON_CTXSW */
+#endif /* CONFIG_SMP */
+
+static void ttwu_queue(struct task_struct *p, int cpu)
+{
+        struct rq *rq = cpu_rq(cpu);
+
+#if defined(CONFIG_SMP)
+        /*
+         * LITMUS^RT: whether to send an IPI to the remote CPU
+         * is plugin specific.
+         */
+        if (!is_realtime(p) &&
+                        sched_feat(TTWU_QUEUE) && cpu != smp_processor_id()) {
+                sched_clock_cpu(cpu); /* sync clocks x-cpu */
+                ttwu_queue_remote(p, cpu);
+                return;
+        }
+#endif
+
+        raw_spin_lock(&rq->lock);
+        ttwu_do_activate(rq, p, 0);
+        raw_spin_unlock(&rq->lock);
 }
 
 /**
@@ -2364,97 +2693,79 @@ static inline void ttwu_post_activation(struct task_struct *p, struct rq *rq,
  * Returns %true if @p was woken up, %false if it was already running
  * or @state didn't match @p's state.
  */
-static int try_to_wake_up(struct task_struct *p, unsigned int state,
-                          int wake_flags)
+static int
+try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 {
-        int cpu, orig_cpu, this_cpu, success = 0;
         unsigned long flags;
-        unsigned long en_flags = ENQUEUE_WAKEUP;
-        struct rq *rq;
+        int cpu, success = 0;
 
         if (is_realtime(p))
                 TRACE_TASK(p, "try_to_wake_up() state:%d\n", p->state);
 
-        this_cpu = get_cpu();
-
         smp_wmb();
-        rq = task_rq_lock(p, &flags);
+        raw_spin_lock_irqsave(&p->pi_lock, flags);
         if (!(p->state & state))
                 goto out;
 
-        if (p->se.on_rq)
-                goto out_running;
-
+        success = 1; /* we're going to change ->state */
         cpu = task_cpu(p);
-        orig_cpu = cpu;
 
-#ifdef CONFIG_SMP
-        if (unlikely(task_running(rq, p)) || is_realtime(p))
-                goto out_activate;
+        if (p->on_rq && ttwu_remote(p, wake_flags))
+                goto stat;
 
+#ifdef CONFIG_SMP
         /*
-         * In order to handle concurrent wakeups and release the rq->lock
-         * we put the task in TASK_WAKING state.
-         *
-         * First fix up the nr_uninterruptible count:
+         * If the owning (remote) cpu is still in the middle of schedule() with
+         * this task as prev, wait until its done referencing the task.
          */
-        if (task_contributes_to_load(p)) {
-                if (likely(cpu_online(orig_cpu)))
-                        rq->nr_uninterruptible--;
-                else
-                        this_rq()->nr_uninterruptible--;
-        }
-        p->state = TASK_WAKING;
-
-        if (p->sched_class->task_waking) {
-                p->sched_class->task_waking(rq, p);
-                en_flags |= ENQUEUE_WAKING;
+        while (p->on_cpu) {
+#ifdef __ARCH_WANT_INTERRUPTS_ON_CTXSW
+                /*
+                 * In case the architecture enables interrupts in
+                 * context_switch(), we cannot busy wait, since that
+                 * would lead to deadlocks when an interrupt hits and
+                 * tries to wake up @prev. So bail and do a complete
+                 * remote wakeup.
+                 */
+                if (ttwu_activate_remote(p, wake_flags))
+                        goto stat;
+#else
+                cpu_relax();
+#endif
         }
+        /*
+         * Pairs with the smp_wmb() in finish_lock_switch().
+         */
+        smp_rmb();
 
-        cpu = select_task_rq(rq, p, SD_BALANCE_WAKE, wake_flags);
-        if (cpu != orig_cpu)
-                set_task_cpu(p, cpu);
-        __task_rq_unlock(rq);
+        /* LITMUS^RT: once the task can be safely referenced by this
+         * CPU, don't mess up with Linux load balancing stuff.
+         */
+        if (is_realtime(p))
+                goto litmus_out_activate;
 
-        rq = cpu_rq(cpu);
-        raw_spin_lock(&rq->lock);
+        p->sched_contributes_to_load = !!task_contributes_to_load(p);
+        p->state = TASK_WAKING;
 
-        /*
-         * We migrated the task without holding either rq->lock, however
-         * since the task is not on the task list itself, nobody else
-         * will try and migrate the task, hence the rq should match the
-         * cpu we just moved it to.
-         */
-        WARN_ON(task_cpu(p) != cpu);
-        WARN_ON(p->state != TASK_WAKING);
+        if (p->sched_class->task_waking)
+                p->sched_class->task_waking(p);
 
-#ifdef CONFIG_SCHEDSTATS
-        schedstat_inc(rq, ttwu_count);
-        if (cpu == this_cpu)
-                schedstat_inc(rq, ttwu_local);
-        else {
-                struct sched_domain *sd;
-                for_each_domain(this_cpu, sd) {
-                        if (cpumask_test_cpu(cpu, sched_domain_span(sd))) {
-                                schedstat_inc(sd, ttwu_wake_remote);
-                                break;
-                        }
-                }
+        cpu = select_task_rq(p, SD_BALANCE_WAKE, wake_flags);
+        if (task_cpu(p) != cpu) {
+                wake_flags |= WF_MIGRATED;
+                set_task_cpu(p, cpu);
         }
-#endif /* CONFIG_SCHEDSTATS */
 
-out_activate:
+litmus_out_activate:
 #endif /* CONFIG_SMP */
-        ttwu_activate(p, rq, wake_flags & WF_SYNC, orig_cpu != cpu,
-                      cpu == this_cpu, en_flags);
-        success = 1;
-out_running:
-        ttwu_post_activation(p, rq, wake_flags, success);
+
+        ttwu_queue(p, cpu);
+stat:
+        ttwu_stat(p, cpu, wake_flags);
 out:
         if (is_realtime(p))
                 TRACE_TASK(p, "try_to_wake_up() done state:%d\n", p->state);
-        task_rq_unlock(rq, &flags);
-        put_cpu();
+        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
 
         return success;
 }
@@ -2463,31 +2774,34 @@ out:
  * try_to_wake_up_local - try to wake up a local task with rq lock held
  * @p: the thread to be awakened
  *
- * Put @p on the run-queue if it's not alredy there.  The caller must
+ * Put @p on the run-queue if it's not already there. The caller must
  * ensure that this_rq() is locked, @p is bound to this_rq() and not
- * the current task.  this_rq() stays locked over invocation.
+ * the current task.
  */
 static void try_to_wake_up_local(struct task_struct *p)
 {
         struct rq *rq = task_rq(p);
-        bool success = false;
 
         BUG_ON(rq != this_rq());
         BUG_ON(p == current);
         lockdep_assert_held(&rq->lock);
 
+        if (!raw_spin_trylock(&p->pi_lock)) {
+                raw_spin_unlock(&rq->lock);
+                raw_spin_lock(&p->pi_lock);
+                raw_spin_lock(&rq->lock);
+        }
+
         if (!(p->state & TASK_NORMAL))
-                return;
+                goto out;
 
-        if (!p->se.on_rq) {
-                if (likely(!task_running(rq, p))) {
-                        schedstat_inc(rq, ttwu_count);
-                        schedstat_inc(rq, ttwu_local);
-                }
-                ttwu_activate(p, rq, false, false, true, ENQUEUE_WAKEUP);
-                success = true;
-        }
-        ttwu_post_activation(p, rq, 0, success);
+        if (!p->on_rq)
+                ttwu_activate(rq, p, ENQUEUE_WAKEUP);
+
+        ttwu_do_wakeup(rq, p, 0);
+        ttwu_stat(p, smp_processor_id(), 0);
+out:
+        raw_spin_unlock(&p->pi_lock);
 }
 
 /**
@@ -2520,18 +2834,21 @@ int wake_up_state(struct task_struct *p, unsigned int state)
  */
 static void __sched_fork(struct task_struct *p)
 {
+        p->on_rq                        = 0;
+
+        p->se.on_rq                     = 0;
         p->se.exec_start                = 0;
         p->se.sum_exec_runtime          = 0;
         p->se.prev_sum_exec_runtime     = 0;
         p->se.nr_migrations             = 0;
+        p->se.vruntime                  = 0;
+        INIT_LIST_HEAD(&p->se.group_node);
 
 #ifdef CONFIG_SCHEDSTATS
         memset(&p->se.statistics, 0, sizeof(p->se.statistics));
 #endif
 
         INIT_LIST_HEAD(&p->rt.run_list);
-        p->se.on_rq = 0;
-        INIT_LIST_HEAD(&p->se.group_node);
 
 #ifdef CONFIG_PREEMPT_NOTIFIERS
         INIT_HLIST_HEAD(&p->preempt_notifiers);
@@ -2541,8 +2858,9 @@ static void __sched_fork(struct task_struct *p)
 /*
  * fork()/clone()-time setup:
  */
-void sched_fork(struct task_struct *p, int clone_flags)
+void sched_fork(struct task_struct *p)
 {
+        unsigned long flags;
         int cpu = get_cpu();
 
         __sched_fork(p);
@@ -2594,22 +2912,24 @@ void sched_fork(struct task_struct *p, int clone_flags)
          *
          * Silence PROVE_RCU.
          */
-        rcu_read_lock();
+        raw_spin_lock_irqsave(&p->pi_lock, flags);
         set_task_cpu(p, cpu);
-        rcu_read_unlock();
+        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
 
 #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT)
         if (likely(sched_info_on()))
                 memset(&p->sched_info, 0, sizeof(p->sched_info));
 #endif
-#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
-        p->oncpu = 0;
+#if defined(CONFIG_SMP)
+        p->on_cpu = 0;
 #endif
 #ifdef CONFIG_PREEMPT
         /* Want to start with kernel preemption disabled. */
         task_thread_info(p)->preempt_count = 1;
 #endif
+#ifdef CONFIG_SMP
         plist_node_init(&p->pushable_tasks, MAX_PRIO);
+#endif
 
         put_cpu();
 }
@@ -2621,41 +2941,31 @@ void sched_fork(struct task_struct *p, int clone_flags)
  * that must be done for every newly created context, then puts the task
  * on the runqueue and wakes it.
  */
-void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
+void wake_up_new_task(struct task_struct *p)
 {
         unsigned long flags;
         struct rq *rq;
-        int cpu __maybe_unused = get_cpu();
 
+        raw_spin_lock_irqsave(&p->pi_lock, flags);
 #ifdef CONFIG_SMP
-        rq = task_rq_lock(p, &flags);
-        p->state = TASK_WAKING;
-
         /*
          * Fork balancing, do it here and not earlier because:
          *  - cpus_allowed can change in the fork path
          *  - any previously selected cpu might disappear through hotplug
-         *
-         * We set TASK_WAKING so that select_task_rq() can drop rq->lock
-         * without people poking at ->cpus_allowed.
          */
-        cpu = select_task_rq(rq, p, SD_BALANCE_FORK, 0);
-        set_task_cpu(p, cpu);
-
-        p->state = TASK_RUNNING;
-        task_rq_unlock(rq, &flags);
+        set_task_cpu(p, select_task_rq(p, SD_BALANCE_FORK, 0));
 #endif
 
-        rq = task_rq_lock(p, &flags);
+        rq = __task_rq_lock(p);
         activate_task(rq, p, 0);
-        trace_sched_wakeup_new(p, 1);
+        p->on_rq = 1;
+        trace_sched_wakeup_new(p, true);
         check_preempt_curr(rq, p, WF_FORK);
 #ifdef CONFIG_SMP
         if (p->sched_class->task_woken)
                 p->sched_class->task_woken(rq, p);
 #endif
-        task_rq_unlock(rq, &flags);
-        put_cpu();
+        task_rq_unlock(rq, p, &flags);
 }
 
 #ifdef CONFIG_PREEMPT_NOTIFIERS
@@ -2733,9 +3043,12 @@ static inline void
 prepare_task_switch(struct rq *rq, struct task_struct *prev,
                     struct task_struct *next)
 {
+        sched_info_switch(prev, next);
+        perf_event_task_sched_out(prev, next);
         fire_sched_out_preempt_notifiers(prev, next);
         prepare_lock_switch(rq, next);
         prepare_arch_switch(next);
+        trace_sched_switch(prev, next);
 }
 
 /**
@@ -2879,7 +3192,7 @@ context_switch(struct rq *rq, struct task_struct *prev,
         struct mm_struct *mm, *oldmm;
 
         prepare_task_switch(rq, prev, next);
-        trace_sched_switch(prev, next);
+
         mm = next->mm;
         oldmm = prev->active_mm;
         /*
@@ -2889,14 +3202,14 @@ context_switch(struct rq *rq, struct task_struct *prev,
          */
         arch_start_context_switch(prev);
 
-        if (likely(!mm)) {
+        if (!mm) {
                 next->active_mm = oldmm;
                 atomic_inc(&oldmm->mm_count);
                 enter_lazy_tlb(oldmm, next);
         } else
                 switch_mm(oldmm, mm, next);
 
-        if (likely(!prev->mm)) {
+        if (!prev->mm) {
                 prev->active_mm = NULL;
                 rq->prev_mm = oldmm;
         }
@@ -3011,6 +3324,15 @@ static long calc_load_fold_active(struct rq *this_rq)
         return delta;
 }
 
+static unsigned long
+calc_load(unsigned long load, unsigned long exp, unsigned long active)
+{
+        load *= exp;
+        load += active * (FIXED_1 - exp);
+        load += 1UL << (FSHIFT - 1);
+        return load >> FSHIFT;
+}
+
 #ifdef CONFIG_NO_HZ
 /*
  * For NO_HZ we delay the active fold to the next LOAD_FREQ update.
@@ -3040,6 +3362,128 @@ static long calc_load_fold_idle(void)
 
         return delta;
 }
+
+/**
+ * fixed_power_int - compute: x^n, in O(log n) time
+ *
+ * @x:         base of the power
+ * @frac_bits: fractional bits of @x
+ * @n:         power to raise @x to.
+ *
+ * By exploiting the relation between the definition of the natural power
+ * function: x^n := x*x*...*x (x multiplied by itself for n times), and
+ * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
+ * (where: n_i \elem {0, 1}, the binary vector representing n),
+ * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
+ * of course trivially computable in O(log_2 n), the length of our binary
+ * vector.
+ */
+static unsigned long
+fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
+{
+        unsigned long result = 1UL << frac_bits;
+
+        if (n) for (;;) {
+                if (n & 1) {
+                        result *= x;
+                        result += 1UL << (frac_bits - 1);
+                        result >>= frac_bits;
+                }
+                n >>= 1;
+                if (!n)
+                        break;
+                x *= x;
+                x += 1UL << (frac_bits - 1);
+                x >>= frac_bits;
+        }
+
+        return result;
+}
+
+/*
+ * a1 = a0 * e + a * (1 - e)
+ *
+ * a2 = a1 * e + a * (1 - e)
+ *    = (a0 * e + a * (1 - e)) * e + a * (1 - e)
+ *    = a0 * e^2 + a * (1 - e) * (1 + e)
+ *
+ * a3 = a2 * e + a * (1 - e)
+ *    = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
+ *    = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
+ *
+ *  ...
+ *
+ * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
+ *    = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
+ *    = a0 * e^n + a * (1 - e^n)
+ *
+ * [1] application of the geometric series:
+ *
+ *              n         1 - x^(n+1)
+ *     S_n := \Sum x^i = -------------
+ *             i=0          1 - x
+ */
+static unsigned long
+calc_load_n(unsigned long load, unsigned long exp,
+            unsigned long active, unsigned int n)
+{
+
+        return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
+}
+
+/*
+ * NO_HZ can leave us missing all per-cpu ticks calling
+ * calc_load_account_active(), but since an idle CPU folds its delta into
+ * calc_load_tasks_idle per calc_load_account_idle(), all we need to do is fold
+ * in the pending idle delta if our idle period crossed a load cycle boundary.
+ *
+ * Once we've updated the global active value, we need to apply the exponential
+ * weights adjusted to the number of cycles missed.
+ */
+static void calc_global_nohz(unsigned long ticks)
+{
+        long delta, active, n;
+
+        if (time_before(jiffies, calc_load_update))
+                return;
+
+        /*
+         * If we crossed a calc_load_update boundary, make sure to fold
+         * any pending idle changes, the respective CPUs might have
+         * missed the tick driven calc_load_account_active() update
+         * due to NO_HZ.
+         */
+        delta = calc_load_fold_idle();
+        if (delta)
+                atomic_long_add(delta, &calc_load_tasks);
+
+        /*
+         * If we were idle for multiple load cycles, apply them.
+         */
+        if (ticks >= LOAD_FREQ) {
+                n = ticks / LOAD_FREQ;
+
+                active = atomic_long_read(&calc_load_tasks);
+                active = active > 0 ? active * FIXED_1 : 0;
+
+                avenrun[0] = calc_load_n(avenrun[0], EXP_1, active, n);
+                avenrun[1] = calc_load_n(avenrun[1], EXP_5, active, n);
+                avenrun[2] = calc_load_n(avenrun[2], EXP_15, active, n);
+
+                calc_load_update += n * LOAD_FREQ;
+        }
+
+        /*
+         * Its possible the remainder of the above division also crosses
+         * a LOAD_FREQ period, the regular check in calc_global_load()
+         * which comes after this will take care of that.
+         *
+         * Consider us being 11 ticks before a cycle completion, and us
+         * sleeping for 4*LOAD_FREQ + 22 ticks, then the above code will
+         * age us 4 cycles, and the test in calc_global_load() will
+         * pick up the final one.
+         */
+}
 #else
 static void calc_load_account_idle(struct rq *this_rq)
 {
@@ -3049,6 +3493,10 @@ static inline long calc_load_fold_idle(void)
 {
         return 0;
 }
+
+static void calc_global_nohz(unsigned long ticks)
+{
+}
 #endif
 
 /**
@@ -3066,24 +3514,17 @@ void get_avenrun(unsigned long *loads, unsigned long offset, int shift)
         loads[2] = (avenrun[2] + offset) << shift;
 }
 
-static unsigned long
-calc_load(unsigned long load, unsigned long exp, unsigned long active)
-{
-        load *= exp;
-        load += active * (FIXED_1 - exp);
-        return load >> FSHIFT;
-}
-
 /*
  * calc_load - update the avenrun load estimates 10 ticks after the
  * CPUs have updated calc_load_tasks.
  */
-void calc_global_load(void)
+void calc_global_load(unsigned long ticks)
 {
-        unsigned long upd = calc_load_update + 10;
         long active;
 
-        if (time_before(jiffies, upd))
+        calc_global_nohz(ticks);
+
+        if (time_before(jiffies, calc_load_update + 10))
                 return;
 
         active = atomic_long_read(&calc_load_tasks);
@@ -3244,27 +3685,22 @@ void sched_exec(void)
 {
         struct task_struct *p = current;
         unsigned long flags;
-        struct rq *rq;
         int dest_cpu;
 
-        rq = task_rq_lock(p, &flags);
-        dest_cpu = p->sched_class->select_task_rq(rq, p, SD_BALANCE_EXEC, 0);
+        raw_spin_lock_irqsave(&p->pi_lock, flags);
+        dest_cpu = p->sched_class->select_task_rq(p, SD_BALANCE_EXEC, 0);
         if (dest_cpu == smp_processor_id())
                 goto unlock;
 
-        /*
-         * select_task_rq() can race against ->cpus_allowed
-         */
-        if (cpumask_test_cpu(dest_cpu, &p->cpus_allowed) &&
-            likely(cpu_active(dest_cpu)) && migrate_task(p, dest_cpu)) {
+        if (likely(cpu_active(dest_cpu))) {
                 struct migration_arg arg = { p, dest_cpu };
 
-                task_rq_unlock(rq, &flags);
-                stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
+                raw_spin_unlock_irqrestore(&p->pi_lock, flags);
+                stop_one_cpu(task_cpu(p), migration_cpu_stop, &arg);
                 return;
         }
 unlock:
-        task_rq_unlock(rq, &flags);
+        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
 }
 
 #endif
@@ -3285,7 +3721,7 @@ static u64 do_task_delta_exec(struct task_struct *p, struct rq *rq)
 
         if (task_current(rq, p)) {
                 update_rq_clock(rq);
-                ns = rq->clock - p->se.exec_start;
+                ns = rq->clock_task - p->se.exec_start;
                 if ((s64)ns < 0)
                         ns = 0;
         }
@@ -3301,7 +3737,7 @@ unsigned long long task_delta_exec(struct task_struct *p)
 
         rq = task_rq_lock(p, &flags);
         ns = do_task_delta_exec(p, rq);
-        task_rq_unlock(rq, &flags);
+        task_rq_unlock(rq, p, &flags);
 
         return ns;
 }
@@ -3319,7 +3755,7 @@ unsigned long long task_sched_runtime(struct task_struct *p)
 
         rq = task_rq_lock(p, &flags);
         ns = p->se.sum_exec_runtime + do_task_delta_exec(p, rq);
-        task_rq_unlock(rq, &flags);
+        task_rq_unlock(rq, p, &flags);
 
         return ns;
 }
@@ -3343,7 +3779,7 @@ unsigned long long thread_group_sched_runtime(struct task_struct *p)
         rq = task_rq_lock(p, &flags);
         thread_group_cputime(p, &totals);
         ns = totals.sum_exec_runtime + do_task_delta_exec(p, rq);
-        task_rq_unlock(rq, &flags);
+        task_rq_unlock(rq, p, &flags);
 
         return ns;
 }
@@ -3408,6 +3844,32 @@ static void account_guest_time(struct task_struct *p, cputime_t cputime,
 }
 
 /*
+ * Account system cpu time to a process and desired cpustat field
+ * @p: the process that the cpu time gets accounted to
+ * @cputime: the cpu time spent in kernel space since the last update
+ * @cputime_scaled: cputime scaled by cpu frequency
+ * @target_cputime64: pointer to cpustat field that has to be updated
+ */
+static inline
+void __account_system_time(struct task_struct *p, cputime_t cputime,
+                        cputime_t cputime_scaled, cputime64_t *target_cputime64)
+{
+        cputime64_t tmp = cputime_to_cputime64(cputime);
+
+        /* Add system time to process. */
+        p->stime = cputime_add(p->stime, cputime);
+        p->stimescaled = cputime_add(p->stimescaled, cputime_scaled);
+        account_group_system_time(p, cputime);
+
+        /* Add system time to cpustat. */
+        *target_cputime64 = cputime64_add(*target_cputime64, tmp);
+        cpuacct_update_stats(p, CPUACCT_STAT_SYSTEM, cputime);
+
+        /* Account for system time used */
+        acct_update_integrals(p);
+}
+
+/*
  * Account system cpu time to a process.
  * @p: the process that the cpu time gets accounted to
  * @hardirq_offset: the offset to subtract from hardirq_count()
@@ -3418,36 +3880,26 @@ void account_system_time(struct task_struct *p, int hardirq_offset,
                          cputime_t cputime, cputime_t cputime_scaled)
 {
         struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
-        cputime64_t tmp;
+        cputime64_t *target_cputime64;
 
         if ((p->flags & PF_VCPU) && (irq_count() - hardirq_offset == 0)) {
                 account_guest_time(p, cputime, cputime_scaled);
                 return;
         }
 
-        /* Add system time to process. */
-        p->stime = cputime_add(p->stime, cputime);
-        p->stimescaled = cputime_add(p->stimescaled, cputime_scaled);
-        account_group_system_time(p, cputime);
-
-        /* Add system time to cpustat. */
-        tmp = cputime_to_cputime64(cputime);
         if (hardirq_count() - hardirq_offset)
-                cpustat->irq = cputime64_add(cpustat->irq, tmp);
-        else if (softirq_count())
-                cpustat->softirq = cputime64_add(cpustat->softirq, tmp);
+                target_cputime64 = &cpustat->irq;
+        else if (in_serving_softirq())
+                target_cputime64 = &cpustat->softirq;
         else
-                cpustat->system = cputime64_add(cpustat->system, tmp);
-
-        cpuacct_update_stats(p, CPUACCT_STAT_SYSTEM, cputime);
+                target_cputime64 = &cpustat->system;
 
-        /* Account for system time used */
-        acct_update_integrals(p);
+        __account_system_time(p, cputime, cputime_scaled, target_cputime64);
 }
 
 /*
  * Account for involuntary wait time.
- * @steal: the cpu time spent in involuntary wait
+ * @cputime: the cpu time spent in involuntary wait
  */
 void account_steal_time(cputime_t cputime)
 {
@@ -3475,6 +3927,73 @@ void account_idle_time(cputime_t cputime)
 
 #ifndef CONFIG_VIRT_CPU_ACCOUNTING
 
+#ifdef CONFIG_IRQ_TIME_ACCOUNTING
+/*
+ * Account a tick to a process and cpustat
+ * @p: the process that the cpu time gets accounted to
+ * @user_tick: is the tick from userspace
+ * @rq: the pointer to rq
+ *
+ * Tick demultiplexing follows the order
+ * - pending hardirq update
+ * - pending softirq update
+ * - user_time
+ * - idle_time
+ * - system time
+ *   - check for guest_time
+ *   - else account as system_time
+ *
+ * Check for hardirq is done both for system and user time as there is
+ * no timer going off while we are on hardirq and hence we may never get an
+ * opportunity to update it solely in system time.
+ * p->stime and friends are only updated on system time and not on irq
+ * softirq as those do not count in task exec_runtime any more.
+ */
+static void irqtime_account_process_tick(struct task_struct *p, int user_tick,
+                                                struct rq *rq)
+{
+        cputime_t one_jiffy_scaled = cputime_to_scaled(cputime_one_jiffy);
+        cputime64_t tmp = cputime_to_cputime64(cputime_one_jiffy);
+        struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+
+        if (irqtime_account_hi_update()) {
+                cpustat->irq = cputime64_add(cpustat->irq, tmp);
+        } else if (irqtime_account_si_update()) {
+                cpustat->softirq = cputime64_add(cpustat->softirq, tmp);
+        } else if (this_cpu_ksoftirqd() == p) {
+                /*
+                 * ksoftirqd time do not get accounted in cpu_softirq_time.
+                 * So, we have to handle it separately here.
+                 * Also, p->stime needs to be updated for ksoftirqd.
+                 */
+                __account_system_time(p, cputime_one_jiffy, one_jiffy_scaled,
+                                        &cpustat->softirq);
+        } else if (user_tick) {
+                account_user_time(p, cputime_one_jiffy, one_jiffy_scaled);
+        } else if (p == rq->idle) {
+                account_idle_time(cputime_one_jiffy);
+        } else if (p->flags & PF_VCPU) { /* System time or guest time */
+                account_guest_time(p, cputime_one_jiffy, one_jiffy_scaled);
+        } else {
+                __account_system_time(p, cputime_one_jiffy, one_jiffy_scaled,
+                                        &cpustat->system);
+        }
+}
+
+static void irqtime_account_idle_ticks(int ticks)
+{
+        int i;
+        struct rq *rq = this_rq();
+
+        for (i = 0; i < ticks; i++)
+                irqtime_account_process_tick(current, 0, rq);
+}
+#else /* CONFIG_IRQ_TIME_ACCOUNTING */
+static void irqtime_account_idle_ticks(int ticks) {}
+static void irqtime_account_process_tick(struct task_struct *p, int user_tick,
+                                                struct rq *rq) {}
+#endif /* CONFIG_IRQ_TIME_ACCOUNTING */
+
 /*
  * Account a single tick of cpu time.
  * @p: the process that the cpu time gets accounted to
@@ -3485,6 +4004,11 @@ void account_process_tick(struct task_struct *p, int user_tick)
         cputime_t one_jiffy_scaled = cputime_to_scaled(cputime_one_jiffy);
         struct rq *rq = this_rq();
 
+        if (sched_clock_irqtime) {
+                irqtime_account_process_tick(p, user_tick, rq);
+                return;
+        }
+
         if (user_tick)
                 account_user_time(p, cputime_one_jiffy, one_jiffy_scaled);
         else if ((p != rq->idle) || (irq_count() != HARDIRQ_OFFSET))
@@ -3510,6 +4034,12 @@ void account_steal_ticks(unsigned long ticks)
  */
 void account_idle_ticks(unsigned long ticks)
 {
+
+        if (sched_clock_irqtime) {
+                irqtime_account_idle_ticks(ticks);
+                return;
+        }
+
         account_idle_time(jiffies_to_cputime(ticks));
 }
 
@@ -3603,9 +4133,6 @@ void thread_group_times(struct task_struct *p, cputime_t *ut, cputime_t *st)
 /*
  * This function gets called by the timer code, with HZ frequency.
  * We call it with interrupts disabled.
- *
- * It also gets called by the fork code, when changing the parent's
- * timeslices.
  */
 void scheduler_tick(void)
 {
@@ -3627,7 +4154,7 @@ void scheduler_tick(void)
 
         raw_spin_unlock(&rq->lock);
 
-        perf_event_task_tick(curr);
+        perf_event_task_tick();
 
 #ifdef CONFIG_SMP
         rq->idle_at_tick = idle_cpu(cpu);
@@ -3733,19 +4260,12 @@ static inline void schedule_debug(struct task_struct *prev)
         profile_hit(SCHED_PROFILING, __builtin_return_address(0));
 
         schedstat_inc(this_rq(), sched_count);
-#ifdef CONFIG_SCHEDSTATS
-        if (unlikely(prev->lock_depth >= 0)) {
-                schedstat_inc(this_rq(), bkl_count);
-                schedstat_inc(prev, sched_info.bkl_count);
-        }
-#endif
 }
 
 static void put_prev_task(struct rq *rq, struct task_struct *prev)
 {
-        if (prev->se.on_rq)
+        if (prev->on_rq || rq->skip_clock_update < 0)
                 update_rq_clock(rq);
-        rq->skip_clock_update = 0;
         prev->sched_class->put_prev_task(rq, prev);
 }
 
@@ -3776,17 +4296,13 @@ pick_next_task(struct rq *rq)
         }
         */
 
-        class = sched_class_highest;
-        for ( ; ; ) {
+        for_each_class(class) {
                 p = class->pick_next_task(rq);
                 if (p)
                         return p;
-                /*
-                 * Will never be NULL as the idle class always
-                 * returns a non-NULL p:
-                 */
-                class = class->next;
         }
+
+        BUG(); /* the idle class will always have a runnable task */
 }
 
 /*
@@ -3807,8 +4323,10 @@ need_resched:
         rcu_note_context_switch(cpu);
         prev = rq->curr;
 
-        release_kernel_lock(prev);
-need_resched_nonpreemptible:
+        /* LITMUS^RT: quickly re-evaluate the scheduling decision
+         * if the previous one is no longer valid after CTX.
+         */
+litmus_need_resched_nonpreemptible:
         TS_SCHED_START;
         sched_trace_task_switch_away(prev);
 
@@ -3818,18 +4336,19 @@ need_resched_nonpreemptible:
                 hrtick_clear(rq);
 
         raw_spin_lock_irq(&rq->lock);
-        clear_tsk_need_resched(prev);
 
         switch_count = &prev->nivcsw;
         if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
                 if (unlikely(signal_pending_state(prev->state, prev))) {
                         prev->state = TASK_RUNNING;
                 } else {
+                        deactivate_task(rq, prev, DEQUEUE_SLEEP);
+                        prev->on_rq = 0;
+
                         /*
-                         * If a worker is going to sleep, notify and
-                         * ask workqueue whether it wants to wake up a
-                         * task to maintain concurrency.  If so, wake
-                         * up the task.
+                         * If a worker went to sleep, notify and ask workqueue
+                         * whether it wants to wake up a task to maintain
+                         * concurrency.
                          */
                         if (prev->flags & PF_WQ_WORKER) {
                                 struct task_struct *to_wakeup;
@@ -3838,7 +4357,16 @@ need_resched_nonpreemptible:
                                 if (to_wakeup)
                                         try_to_wake_up_local(to_wakeup);
                         }
-                        deactivate_task(rq, prev, DEQUEUE_SLEEP);
+
+                        /*
+                         * If we are going to sleep and we have plugged IO
+                         * queued, make sure to submit it to avoid deadlocks.
+                         */
+                        if (blk_needs_flush_plug(prev)) {
+                                raw_spin_unlock(&rq->lock);
+                                blk_schedule_flush_plug(prev);
+                                raw_spin_lock(&rq->lock);
+                        }
                 }
                 switch_count = &prev->nvcsw;
         }
@@ -3850,11 +4378,10 @@ need_resched_nonpreemptible:
 
         put_prev_task(rq, prev);
         next = pick_next_task(rq);
+        clear_tsk_need_resched(prev);
+        rq->skip_clock_update = 0;
 
         if (likely(prev != next)) {
-                sched_info_switch(prev, next);
-                perf_event_task_sched_out(prev, next);
-
                 rq->nr_switches++;
                 rq->curr = next;
                 ++*switch_count;
@@ -3880,8 +4407,8 @@ need_resched_nonpreemptible:
 
         post_schedule(rq);
 
-        if (sched_state_validate_switch() || unlikely(reacquire_kernel_lock(prev)))
-                goto need_resched_nonpreemptible;
+        if (sched_state_validate_switch())
+                goto litmus_need_resched_nonpreemptible;
 
         preempt_enable_no_resched();
         if (need_resched())
@@ -3892,70 +4419,53 @@ need_resched_nonpreemptible:
 EXPORT_SYMBOL(schedule);
 
 #ifdef CONFIG_MUTEX_SPIN_ON_OWNER
+
+static inline bool owner_running(struct mutex *lock, struct task_struct *owner)
+{
+        bool ret = false;
+
+        rcu_read_lock();
+        if (lock->owner != owner)
+                goto fail;
+
+        /*
+         * Ensure we emit the owner->on_cpu, dereference _after_ checking
+         * lock->owner still matches owner, if that fails, owner might
+         * point to free()d memory, if it still matches, the rcu_read_lock()
+         * ensures the memory stays valid.
+         */
+        barrier();
+
+        ret = owner->on_cpu;
+fail:
+        rcu_read_unlock();
+
+        return ret;
+}
+
 /*
  * Look out! "owner" is an entirely speculative pointer
  * access and not reliable.
  */
-int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
+int mutex_spin_on_owner(struct mutex *lock, struct task_struct *owner)
 {
-        unsigned int cpu;
-        struct rq *rq;
-
         if (!sched_feat(OWNER_SPIN))
                 return 0;
 
-#ifdef CONFIG_DEBUG_PAGEALLOC
-        /*
-         * Need to access the cpu field knowing that
-         * DEBUG_PAGEALLOC could have unmapped it if
-         * the mutex owner just released it and exited.
-         */
-        if (probe_kernel_address(&owner->cpu, cpu))
-                return 0;
-#else
-        cpu = owner->cpu;
-#endif
+        while (owner_running(lock, owner)) {
+                if (need_resched())
+                        return 0;
 
-        /*
-         * Even if the access succeeded (likely case),
-         * the cpu field may no longer be valid.
-         */
-        if (cpu >= nr_cpumask_bits)
-                return 0;
+                arch_mutex_cpu_relax();
+        }
 
         /*
-         * We need to validate that we can do a
-         * get_cpu() and that we have the percpu area.
+         * If the owner changed to another task there is likely
+         * heavy contention, stop spinning.
          */
-        if (!cpu_online(cpu))
+        if (lock->owner)
                 return 0;
 
-        rq = cpu_rq(cpu);
-
-        for (;;) {
-                /*
-                 * Owner changed, break to re-assess state.
-                 */
-                if (lock->owner != owner) {
-                        /*
-                         * If the lock has switched to a different owner,
-                         * we likely have heavy contention. Return 0 to quit
-                         * optimistic spinning and not contend further:
-                         */
-                        if (lock->owner)
-                                return 0;
-                        break;
-                }
-
-                /*
-                 * Is that owner really running on that cpu?
-                 */
-                if (task_thread_info(rq->curr) != owner || need_resched())
-                        return 0;
-
-                cpu_relax();
-        }
-
         return 1;
 }
 #endif
@@ -4085,6 +4595,7 @@ void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)
 {
         __wake_up_common(q, mode, 1, 0, key);
 }
+EXPORT_SYMBOL_GPL(__wake_up_locked_key);
 
 /**
  * __wake_up_sync_key - wake up threads blocked on a waitqueue.
@@ -4276,7 +4787,7 @@ EXPORT_SYMBOL(wait_for_completion_interruptible);
  * This waits for either a completion of a specific task to be signaled or for a
  * specified timeout to expire. It is interruptible. The timeout is in jiffies.
  */
-unsigned long __sched
+long __sched
 wait_for_completion_interruptible_timeout(struct completion *x,
                                           unsigned long timeout)
 {
@@ -4309,7 +4820,7 @@ EXPORT_SYMBOL(wait_for_completion_killable);
  * signaled or for a specified timeout to expire. It can be
  * interrupted by a kill signal. The timeout is in jiffies.
  */
-unsigned long __sched
+long __sched
 wait_for_completion_killable_timeout(struct completion *x,
                                      unsigned long timeout)
 {
@@ -4425,18 +4936,18 @@ EXPORT_SYMBOL(sleep_on_timeout);
  */
 void rt_mutex_setprio(struct task_struct *p, int prio)
 {
-        unsigned long flags;
         int oldprio, on_rq, running;
         struct rq *rq;
         const struct sched_class *prev_class;
 
         BUG_ON(prio < 0 || prio > MAX_PRIO);
 
-        rq = task_rq_lock(p, &flags);
+        rq = __task_rq_lock(p);
 
+        trace_sched_pi_setprio(p, prio);
         oldprio = p->prio;
         prev_class = p->sched_class;
-        on_rq = p->se.on_rq;
+        on_rq = p->on_rq;
         running = task_current(rq, p);
         if (on_rq)
                 dequeue_task(rq, p, 0);
@@ -4452,12 +4963,11 @@ void rt_mutex_setprio(struct task_struct *p, int prio)
 
         if (running)
                 p->sched_class->set_curr_task(rq);
-        if (on_rq) {
+        if (on_rq)
                 enqueue_task(rq, p, oldprio < prio ? ENQUEUE_HEAD : 0);
 
-                check_class_changed(rq, p, prev_class, oldprio, running);
-        }
-        task_rq_unlock(rq, &flags);
+        check_class_changed(rq, p, prev_class, oldprio);
+        __task_rq_unlock(rq);
 }
 
 #endif
@@ -4485,7 +4995,7 @@ void set_user_nice(struct task_struct *p, long nice)
                 p->static_prio = NICE_TO_PRIO(nice);
                 goto out_unlock;
         }
-        on_rq = p->se.on_rq;
+        on_rq = p->on_rq;
         if (on_rq)
                 dequeue_task(rq, p, 0);
 
@@ -4505,7 +5015,7 @@ void set_user_nice(struct task_struct *p, long nice)
                         resched_task(rq->curr);
         }
 out_unlock:
-        task_rq_unlock(rq, &flags);
+        task_rq_unlock(rq, p, &flags);
 }
 EXPORT_SYMBOL(set_user_nice);
 
@@ -4619,8 +5129,6 @@ static struct task_struct *find_process_by_pid(pid_t pid)
 static void
 __setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
 {
-        BUG_ON(p->se.on_rq);
-
         p->policy = policy;
         p->rt_priority = prio;
         p->normal_prio = normal_prio(p);
@@ -4645,14 +5153,17 @@ static bool check_same_owner(struct task_struct *p)
 
         rcu_read_lock();
         pcred = __task_cred(p);
-        match = (cred->euid == pcred->euid ||
-                 cred->euid == pcred->uid);
+        if (cred->user->user_ns == pcred->user->user_ns)
+                match = (cred->euid == pcred->euid ||
+                         cred->euid == pcred->uid);
+        else
+                match = false;
         rcu_read_unlock();
         return match;
 }
 
 static int __sched_setscheduler(struct task_struct *p, int policy,
-                                struct sched_param *param, bool user)
+                                const struct sched_param *param, bool user)
 {
         int retval, oldprio, oldpolicy = -1, on_rq, running;
         unsigned long flags;
@@ -4708,12 +5219,15 @@ recheck:
                             param->sched_priority > rlim_rtprio)
                                 return -EPERM;
                 }
+
                 /*
-                 * Like positive nice levels, dont allow tasks to
-                 * move out of SCHED_IDLE either:
+                 * Treat SCHED_IDLE as nice 20. Only allow a switch to
+                 * SCHED_NORMAL if the RLIMIT_NICE would normally permit it.
                  */
-                if (p->policy == SCHED_IDLE && policy != SCHED_IDLE)
-                        return -EPERM;
+                if (p->policy == SCHED_IDLE && policy != SCHED_IDLE) {
+                        if (!can_nice(p, TASK_NICE(p)))
+                                return -EPERM;
+                }
 
                 /* can't change other user's priorities */
                 if (!check_same_owner(p))
@@ -4725,7 +5239,7 @@ recheck:
         }
 
         if (user) {
-                retval = security_task_setscheduler(p, policy, param);
+                retval = security_task_setscheduler(p);
                 if (retval)
                         return retval;
         }
@@ -4739,13 +5253,30 @@ recheck:
         /*
          * make sure no PI-waiters arrive (or leave) while we are
          * changing the priority of the task:
+         *
+         * To be able to change p->policy safely, the appropriate
+         * runqueue lock must be held.
          */
-        raw_spin_lock_irqsave(&p->pi_lock, flags);
+        rq = task_rq_lock(p, &flags);
+
         /*
-         * To be able to change p->policy safely, the apropriate
-         * runqueue lock must be held.
+         * Changing the policy of the stop threads its a very bad idea
          */
-        rq = __task_rq_lock(p);
+        if (p == rq->stop) {
+                task_rq_unlock(rq, p, &flags);
+                return -EINVAL;
+        }
+
+        /*
+         * If not changing anything there's no need to proceed further:
+         */
+        if (unlikely(policy == p->policy && (!rt_policy(policy) ||
+                        param->sched_priority == p->rt_priority))) {
+
+                __task_rq_unlock(rq);
+                raw_spin_unlock_irqrestore(&p->pi_lock, flags);
+                return 0;
+        }
 
 #ifdef CONFIG_RT_GROUP_SCHED
         if (user) {
@@ -4754,9 +5285,9 @@ recheck:
                  * assigned.
                  */
                 if (rt_bandwidth_enabled() && rt_policy(policy) &&
-                                task_group(p)->rt_bandwidth.rt_runtime == 0) {
-                        __task_rq_unlock(rq);
-                        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
+                                task_group(p)->rt_bandwidth.rt_runtime == 0 &&
+                                !task_group_is_autogroup(task_group(p))) {
+                        task_rq_unlock(rq, p, &flags);
                         return -EPERM;
                 }
         }
@@ -4765,11 +5296,10 @@ recheck:
         /* recheck policy now with rq lock held */
         if (unlikely(oldpolicy != -1 && oldpolicy != p->policy)) {
                 policy = oldpolicy = -1;
-                __task_rq_unlock(rq);
-                raw_spin_unlock_irqrestore(&p->pi_lock, flags);
+                task_rq_unlock(rq, p, &flags);
                 goto recheck;
         }
-        on_rq = p->se.on_rq;
+        on_rq = p->on_rq;
         running = task_current(rq, p);
         if (on_rq)
                 deactivate_task(rq, p, 0);
@@ -4793,13 +5323,11 @@ recheck:
 
         if (running)
                 p->sched_class->set_curr_task(rq);
-        if (on_rq) {
+        if (on_rq)
                 activate_task(rq, p, 0);
 
-                check_class_changed(rq, p, prev_class, oldprio, running);
-        }
-        __task_rq_unlock(rq);
-        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
+        check_class_changed(rq, p, prev_class, oldprio);
+        task_rq_unlock(rq, p, &flags);
 
         rt_mutex_adjust_pi(p);
 
@@ -4815,7 +5343,7 @@ recheck:
  * NOTE that the task may be already dead.
  */
 int sched_setscheduler(struct task_struct *p, int policy,
-                       struct sched_param *param)
+                       const struct sched_param *param)
 {
         return __sched_setscheduler(p, policy, param, true);
 }
@@ -4833,7 +5361,7 @@ EXPORT_SYMBOL_GPL(sched_setscheduler);
  * but our caller might not have that capability.
  */
 int sched_setscheduler_nocheck(struct task_struct *p, int policy,
-                               struct sched_param *param)
+                               const struct sched_param *param)
 {
         return __sched_setscheduler(p, policy, param, false);
 }
@@ -4980,16 +5508,16 @@ long sched_setaffinity(pid_t pid, const struct cpumask *in_mask)
                 goto out_free_cpus_allowed;
         }
         retval = -EPERM;
-        if (!check_same_owner(p) && !capable(CAP_SYS_NICE))
+        if (!check_same_owner(p) && !task_ns_capable(p, CAP_SYS_NICE))
                 goto out_unlock;
 
-        retval = security_task_setscheduler(p, 0, NULL);
+        retval = security_task_setscheduler(p);
         if (retval)
                 goto out_unlock;
 
         cpuset_cpus_allowed(p, cpus_allowed);
         cpumask_and(new_mask, in_mask, cpus_allowed);
- again:
+again:
         retval = set_cpus_allowed_ptr(p, new_mask);
 
         if (!retval) {
@@ -5051,7 +5579,6 @@ long sched_getaffinity(pid_t pid, struct cpumask *mask)
 {
         struct task_struct *p;
         unsigned long flags;
-        struct rq *rq;
         int retval;
 
         get_online_cpus();
@@ -5066,9 +5593,9 @@ long sched_getaffinity(pid_t pid, struct cpumask *mask)
         if (retval)
                 goto out_unlock;
 
-        rq = task_rq_lock(p, &flags);
+        raw_spin_lock_irqsave(&p->pi_lock, flags);
         cpumask_and(mask, &p->cpus_allowed, cpu_online_mask);
-        task_rq_unlock(rq, &flags);
+        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
 
 out_unlock:
         rcu_read_unlock();
@@ -5215,6 +5742,67 @@ void __sched yield(void)
 }
 EXPORT_SYMBOL(yield);
 
+/**
+ * yield_to - yield the current processor to another thread in
+ * your thread group, or accelerate that thread toward the
+ * processor it's on.
+ * @p: target task
+ * @preempt: whether task preemption is allowed or not
+ *
+ * It's the caller's job to ensure that the target task struct
+ * can't go away on us before we can do any checks.
+ *
+ * Returns true if we indeed boosted the target task.
+ */
+bool __sched yield_to(struct task_struct *p, bool preempt)
+{
+        struct task_struct *curr = current;
+        struct rq *rq, *p_rq;
+        unsigned long flags;
+        bool yielded = 0;
+
+        local_irq_save(flags);
+        rq = this_rq();
+
+again:
+        p_rq = task_rq(p);
+        double_rq_lock(rq, p_rq);
+        while (task_rq(p) != p_rq) {
+                double_rq_unlock(rq, p_rq);
+                goto again;
+        }
+
+        if (!curr->sched_class->yield_to_task)
+                goto out;
+
+        if (curr->sched_class != p->sched_class)
+                goto out;
+
+        if (task_running(p_rq, p) || p->state)
+                goto out;
+
+        yielded = curr->sched_class->yield_to_task(rq, p, preempt);
+        if (yielded) {
+                schedstat_inc(rq, yld_count);
+                /*
+                 * Make p's CPU reschedule; pick_next_entity takes care of
+                 * fairness.
+                 */
+                if (preempt && rq != p_rq)
+                        resched_task(p_rq->curr);
+        }
+
+out:
+        double_rq_unlock(rq, p_rq);
+        local_irq_restore(flags);
+
+        if (yielded)
+                schedule();
+
+        return yielded;
+}
+EXPORT_SYMBOL_GPL(yield_to);
+
 /*
  * This task is about to go to sleep on IO. Increment rq->nr_iowait so
  * that process accounting knows that this is a task in IO wait state.
@@ -5225,6 +5813,7 @@ void __sched io_schedule(void)
 
         delayacct_blkio_start();
         atomic_inc(&rq->nr_iowait);
+        blk_flush_plug(current);
         current->in_iowait = 1;
         schedule();
         current->in_iowait = 0;
@@ -5240,6 +5829,7 @@ long __sched io_schedule_timeout(long timeout)
 
         delayacct_blkio_start();
         atomic_inc(&rq->nr_iowait);
+        blk_flush_plug(current);
         current->in_iowait = 1;
         ret = schedule_timeout(timeout);
         current->in_iowait = 0;
@@ -5330,7 +5920,7 @@ SYSCALL_DEFINE2(sched_rr_get_interval, pid_t, pid,
 
         rq = task_rq_lock(p, &flags);
         time_slice = p->sched_class->get_rr_interval(rq, p);
-        task_rq_unlock(rq, &flags);
+        task_rq_unlock(rq, p, &flags);
 
         rcu_read_unlock();
         jiffies_to_timespec(time_slice, &t);
@@ -5350,7 +5940,7 @@ void sched_show_task(struct task_struct *p)
         unsigned state;
 
         state = p->state ? __ffs(p->state) + 1 : 0;
-        printk(KERN_INFO "%-13.13s %c", p->comm,
+        printk(KERN_INFO "%-15.15s %c", p->comm,
                 state < sizeof(stat_nam) - 1 ? stat_nam[state] : '?');
 #if BITS_PER_LONG == 32
         if (state == TASK_RUNNING)
@@ -5388,7 +5978,7 @@ void show_state_filter(unsigned long state_filter)
         do_each_thread(g, p) {
                 /*
                  * reset the NMI-timeout, listing all files on a slow
-                 * console might take alot of time:
+                 * console might take a lot of time:
                  */
                 touch_nmi_watchdog();
                 if (!state_filter || (p->state & state_filter))
@@ -5432,26 +6022,35 @@ void __cpuinit init_idle(struct task_struct *idle, int cpu)
         idle->state = TASK_RUNNING;
         idle->se.exec_start = sched_clock();
 
-        cpumask_copy(&idle->cpus_allowed, cpumask_of(cpu));
+        do_set_cpus_allowed(idle, cpumask_of(cpu));
+        /*
+         * We're having a chicken and egg problem, even though we are
+         * holding rq->lock, the cpu isn't yet set to this cpu so the
+         * lockdep check in task_group() will fail.
+         *
+         * Similar case to sched_fork(). / Alternatively we could
+         * use task_rq_lock() here and obtain the other rq->lock.
+         *
+         * Silence PROVE_RCU
+         */
+        rcu_read_lock();
         __set_task_cpu(idle, cpu);
+        rcu_read_unlock();
 
         rq->curr = rq->idle = idle;
-#if defined(CONFIG_SMP) && defined(__ARCH_WANT_UNLOCKED_CTXSW)
-        idle->oncpu = 1;
+#if defined(CONFIG_SMP)
+        idle->on_cpu = 1;
 #endif
         raw_spin_unlock_irqrestore(&rq->lock, flags);
 
         /* Set the preempt count _outside_ the spinlocks! */
-#if defined(CONFIG_PREEMPT)
-        task_thread_info(idle)->preempt_count = (idle->lock_depth >= 0);
-#else
         task_thread_info(idle)->preempt_count = 0;
-#endif
+
         /*
          * The idle tasks have their own, simple scheduling class:
          */
         idle->sched_class = &idle_sched_class;
-        ftrace_graph_init_task(idle);
+        ftrace_graph_init_idle_task(idle, cpu);
 }
 
 /*
@@ -5502,7 +6101,6 @@ static void update_sysctl(void)
         SET_SYSCTL(sched_min_granularity);
         SET_SYSCTL(sched_latency);
         SET_SYSCTL(sched_wakeup_granularity);
-        SET_SYSCTL(sched_shares_ratelimit);
 #undef SET_SYSCTL
 }
 
@@ -5512,6 +6110,16 @@ static inline void sched_init_granularity(void)
 }
 
 #ifdef CONFIG_SMP
+void do_set_cpus_allowed(struct task_struct *p, const struct cpumask *new_mask)
+{
+        if (p->sched_class && p->sched_class->set_cpus_allowed)
+                p->sched_class->set_cpus_allowed(p, new_mask);
+        else {
+                cpumask_copy(&p->cpus_allowed, new_mask);
+                p->rt.nr_cpus_allowed = cpumask_weight(new_mask);
+        }
+}
+
 /*
  * This is how migration works:
  *
@@ -5542,52 +6150,38 @@ int set_cpus_allowed_ptr(struct task_struct *p, const struct cpumask *new_mask)
         unsigned int dest_cpu;
         int ret = 0;
 
-        /*
-         * Serialize against TASK_WAKING so that ttwu() and wunt() can
-         * drop the rq->lock and still rely on ->cpus_allowed.
-         */
-again:
-        while (task_is_waking(p))
-                cpu_relax();
         rq = task_rq_lock(p, &flags);
-        if (task_is_waking(p)) {
-                task_rq_unlock(rq, &flags);
-                goto again;
-        }
+
+        if (cpumask_equal(&p->cpus_allowed, new_mask))
+                goto out;
 
         if (!cpumask_intersects(new_mask, cpu_active_mask)) {
                 ret = -EINVAL;
                 goto out;
         }
 
-        if (unlikely((p->flags & PF_THREAD_BOUND) && p != current &&
-                     !cpumask_equal(&p->cpus_allowed, new_mask))) {
+        if (unlikely((p->flags & PF_THREAD_BOUND) && p != current)) {
                 ret = -EINVAL;
                 goto out;
         }
 
-        if (p->sched_class->set_cpus_allowed)
-                p->sched_class->set_cpus_allowed(p, new_mask);
-        else {
-                cpumask_copy(&p->cpus_allowed, new_mask);
-                p->rt.nr_cpus_allowed = cpumask_weight(new_mask);
-        }
+        do_set_cpus_allowed(p, new_mask);
 
         /* Can the task run on the task's current CPU? If so, we're done */
         if (cpumask_test_cpu(task_cpu(p), new_mask))
                 goto out;
 
         dest_cpu = cpumask_any_and(cpu_active_mask, new_mask);
-        if (migrate_task(p, dest_cpu)) {
+        if (p->on_rq) {
                 struct migration_arg arg = { p, dest_cpu };
                 /* Need help from migration thread: drop lock and wait. */
-                task_rq_unlock(rq, &flags);
+                task_rq_unlock(rq, p, &flags);
                 stop_one_cpu(cpu_of(rq), migration_cpu_stop, &arg);
                 tlb_migrate_finish(p->mm);
                 return 0;
         }
 out:
-        task_rq_unlock(rq, &flags);
+        task_rq_unlock(rq, p, &flags);
 
         return ret;
 }
@@ -5615,6 +6209,7 @@ static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
         rq_src = cpu_rq(src_cpu);
         rq_dest = cpu_rq(dest_cpu);
 
+        raw_spin_lock(&p->pi_lock);
         double_rq_lock(rq_src, rq_dest);
         /* Already moved. */
         if (task_cpu(p) != src_cpu)
@@ -5627,7 +6222,7 @@ static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
          * If we're not on a rq, the next wake-up will ensure we're
          * placed properly.
          */
-        if (p->se.on_rq) {
+        if (p->on_rq) {
                 deactivate_task(rq_src, p, 0);
                 set_task_cpu(p, dest_cpu);
                 activate_task(rq_dest, p, 0);
@@ -5637,6 +6232,7 @@ done:
         ret = 1;
 fail:
         double_rq_unlock(rq_src, rq_dest);
+        raw_spin_unlock(&p->pi_lock);
         return ret;
 }
 
@@ -5660,29 +6256,20 @@ static int migration_cpu_stop(void *data)
 }
 
 #ifdef CONFIG_HOTPLUG_CPU
+
 /*
- * Figure out where task on dead CPU should go, use force if necessary.
+ * Ensures that the idle task is using init_mm right before its cpu goes
+ * offline.
  */
-void move_task_off_dead_cpu(int dead_cpu, struct task_struct *p)
+void idle_task_exit(void)
 {
-        struct rq *rq = cpu_rq(dead_cpu);
-        int needs_cpu, uninitialized_var(dest_cpu);
-        unsigned long flags;
+        struct mm_struct *mm = current->active_mm;
 
-        local_irq_save(flags);
+        BUG_ON(cpu_online(smp_processor_id()));
 
-        raw_spin_lock(&rq->lock);
-        needs_cpu = (task_cpu(p) == dead_cpu) && (p->state != TASK_WAKING);
-        if (needs_cpu)
-                dest_cpu = select_fallback_rq(dead_cpu, p);
-        raw_spin_unlock(&rq->lock);
-        /*
-         * It can only fail if we race with set_cpus_allowed(),
-         * in the racer should migrate the task anyway.
-         */
-        if (needs_cpu)
-                __migrate_task(p, dead_cpu, dest_cpu);
-        local_irq_restore(flags);
+        if (mm != &init_mm)
+                switch_mm(mm, &init_mm, current);
+        mmdrop(mm);
 }
 
 /*
@@ -5695,128 +6282,69 @@ void move_task_off_dead_cpu(int dead_cpu, struct task_struct *p)
 static void migrate_nr_uninterruptible(struct rq *rq_src)
 {
         struct rq *rq_dest = cpu_rq(cpumask_any(cpu_active_mask));
-        unsigned long flags;
 
-        local_irq_save(flags);
-        double_rq_lock(rq_src, rq_dest);
         rq_dest->nr_uninterruptible += rq_src->nr_uninterruptible;
         rq_src->nr_uninterruptible = 0;
-        double_rq_unlock(rq_src, rq_dest);
-        local_irq_restore(flags);
-}
-
-/* Run through task list and migrate tasks from the dead cpu. */
-static void migrate_live_tasks(int src_cpu)
-{
-        struct task_struct *p, *t;
-
-        read_lock(&tasklist_lock);
-
-        do_each_thread(t, p) {
-                if (p == current)
-                        continue;
-
-                if (task_cpu(p) == src_cpu)
-                        move_task_off_dead_cpu(src_cpu, p);
-        } while_each_thread(t, p);
-
-        read_unlock(&tasklist_lock);
 }
 
 /*
- * Schedules idle task to be the next runnable task on current CPU.
- * It does so by boosting its priority to highest possible.
- * Used by CPU offline code.
+ * remove the tasks which were accounted by rq from calc_load_tasks.
  */
-void sched_idle_next(void)
+static void calc_global_load_remove(struct rq *rq)
 {
-        int this_cpu = smp_processor_id();
-        struct rq *rq = cpu_rq(this_cpu);
-        struct task_struct *p = rq->idle;
-        unsigned long flags;
-
-        /* cpu has to be offline */
-        BUG_ON(cpu_online(this_cpu));
-
-        /*
-         * Strictly not necessary since rest of the CPUs are stopped by now
-         * and interrupts disabled on the current cpu.
-         */
-        raw_spin_lock_irqsave(&rq->lock, flags);
-
-        __setscheduler(rq, p, SCHED_FIFO, MAX_RT_PRIO-1);
-
-        activate_task(rq, p, 0);
-
-        raw_spin_unlock_irqrestore(&rq->lock, flags);
+        atomic_long_sub(rq->calc_load_active, &calc_load_tasks);
+        rq->calc_load_active = 0;
 }
 
 /*
- * Ensures that the idle task is using init_mm right before its cpu goes
- * offline.
+ * Migrate all tasks from the rq, sleeping tasks will be migrated by
+ * try_to_wake_up()->select_task_rq().
+ *
+ * Called with rq->lock held even though we'er in stop_machine() and
+ * there's no concurrency possible, we hold the required locks anyway
+ * because of lock validation efforts.
  */
-void idle_task_exit(void)
-{
-        struct mm_struct *mm = current->active_mm;
-
-        BUG_ON(cpu_online(smp_processor_id()));
-
-        if (mm != &init_mm)
-                switch_mm(mm, &init_mm, current);
-        mmdrop(mm);
-}
-
-/* called under rq->lock with disabled interrupts */
-static void migrate_dead(unsigned int dead_cpu, struct task_struct *p)
+static void migrate_tasks(unsigned int dead_cpu)
 {
         struct rq *rq = cpu_rq(dead_cpu);
-
-        /* Must be exiting, otherwise would be on tasklist. */
-        BUG_ON(!p->exit_state);
-
-        /* Cannot have done final schedule yet: would have vanished. */
-        BUG_ON(p->state == TASK_DEAD);
-
-        get_task_struct(p);
+        struct task_struct *next, *stop = rq->stop;
+        int dest_cpu;
 
         /*
-         * Drop lock around migration; if someone else moves it,
-         * that's OK. No task can be added to this CPU, so iteration is
-         * fine.
+         * Fudge the rq selection such that the below task selection loop
+         * doesn't get stuck on the currently eligible stop task.
+         *
+         * We're currently inside stop_machine() and the rq is either stuck
+         * in the stop_machine_cpu_stop() loop, or we're executing this code,
+         * either way we should never end up calling schedule() until we're
+         * done here.
          */
-        raw_spin_unlock_irq(&rq->lock);
-        move_task_off_dead_cpu(dead_cpu, p);
-        raw_spin_lock_irq(&rq->lock);
-
-        put_task_struct(p);
-}
-
-/* release_task() removes task from tasklist, so we won't find dead tasks. */
-static void migrate_dead_tasks(unsigned int dead_cpu)
-{
-        struct rq *rq = cpu_rq(dead_cpu);
-        struct task_struct *next;
+        rq->stop = NULL;
 
         for ( ; ; ) {
-                if (!rq->nr_running)
+                /*
+                 * There's this thread running, bail when that's the only
+                 * remaining thread.
+                 */
+                if (rq->nr_running == 1)
                         break;
+
                 next = pick_next_task(rq);
-                if (!next)
-                        break;
+                BUG_ON(!next);
                 next->sched_class->put_prev_task(rq, next);
-                migrate_dead(dead_cpu, next);
 
+                /* Find suitable destination for @next, with force if needed. */
+                dest_cpu = select_fallback_rq(dead_cpu, next);
+                raw_spin_unlock(&rq->lock);
+
+                __migrate_task(next, dead_cpu, dest_cpu);
+
+                raw_spin_lock(&rq->lock);
         }
-}
 
-/*
- * remove the tasks which were accounted by rq from calc_load_tasks.
- */
-static void calc_global_load_remove(struct rq *rq)
-{
-        atomic_long_sub(rq->calc_load_active, &calc_load_tasks);
-        rq->calc_load_active = 0;
+        rq->stop = stop;
 }
+
 #endif /* CONFIG_HOTPLUG_CPU */
 
 #if defined(CONFIG_SCHED_DEBUG) && defined(CONFIG_SYSCTL)
@@ -6026,15 +6554,13 @@ migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
         unsigned long flags;
         struct rq *rq = cpu_rq(cpu);
 
-        switch (action) {
+        switch (action & ~CPU_TASKS_FROZEN) {
 
         case CPU_UP_PREPARE:
-        case CPU_UP_PREPARE_FROZEN:
                 rq->calc_load_update = calc_load_update;
                 break;
 
         case CPU_ONLINE:
-        case CPU_ONLINE_FROZEN:
                 /* Update our root-domain */
                 raw_spin_lock_irqsave(&rq->lock, flags);
                 if (rq->rd) {
@@ -6046,33 +6572,26 @@ migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
                 break;
 
 #ifdef CONFIG_HOTPLUG_CPU
-        case CPU_DEAD:
-        case CPU_DEAD_FROZEN:
-                migrate_live_tasks(cpu);
-                /* Idle task back to normal (off runqueue, low prio) */
-                raw_spin_lock_irq(&rq->lock);
-                deactivate_task(rq, rq->idle, 0);
-                __setscheduler(rq, rq->idle, SCHED_NORMAL, 0);
-                rq->idle->sched_class = &idle_sched_class;
-                migrate_dead_tasks(cpu);
-                raw_spin_unlock_irq(&rq->lock);
-                migrate_nr_uninterruptible(rq);
-                BUG_ON(rq->nr_running != 0);
-                calc_global_load_remove(rq);
-                break;
-
         case CPU_DYING:
-        case CPU_DYING_FROZEN:
+                sched_ttwu_pending();
                 /* Update our root-domain */
                 raw_spin_lock_irqsave(&rq->lock, flags);
                 if (rq->rd) {
                         BUG_ON(!cpumask_test_cpu(cpu, rq->rd->span));
                         set_rq_offline(rq);
                 }
+                migrate_tasks(cpu);
+                BUG_ON(rq->nr_running != 1); /* the migration thread */
                 raw_spin_unlock_irqrestore(&rq->lock, flags);
+
+                migrate_nr_uninterruptible(rq);
+                calc_global_load_remove(rq);
                 break;
 #endif
         }
+
+        update_max_interval();
+
         return NOTIFY_OK;
 }
 
@@ -6133,6 +6652,8 @@ early_initcall(migration_init);
 
 #ifdef CONFIG_SMP
 
+static cpumask_var_t sched_domains_tmpmask; /* sched_domains_mutex */
+
 #ifdef CONFIG_SCHED_DEBUG
 
 static __read_mostly int sched_domain_debug_enabled;
@@ -6183,7 +6704,7 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
                         break;
                 }
 
-                if (!group->cpu_power) {
+                if (!group->sgp->power) {
                         printk(KERN_CONT "\n");
                         printk(KERN_ERR "ERROR: domain->cpu_power not "
                                         "set\n");
@@ -6207,9 +6728,9 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
                 cpulist_scnprintf(str, sizeof(str), sched_group_cpus(group));
 
                 printk(KERN_CONT " %s", str);
-                if (group->cpu_power != SCHED_LOAD_SCALE) {
+                if (group->sgp->power != SCHED_POWER_SCALE) {
                         printk(KERN_CONT " (cpu_power = %d)",
-                                group->cpu_power);
+                                group->sgp->power);
                 }
 
                 group = group->next;
@@ -6228,7 +6749,6 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
 
 static void sched_domain_debug(struct sched_domain *sd, int cpu)
 {
-        cpumask_var_t groupmask;
         int level = 0;
 
         if (!sched_domain_debug_enabled)
@@ -6241,20 +6761,14 @@ static void sched_domain_debug(struct sched_domain *sd, int cpu)
 
         printk(KERN_DEBUG "CPU%d attaching sched-domain:\n", cpu);
 
-        if (!alloc_cpumask_var(&groupmask, GFP_KERNEL)) {
-                printk(KERN_DEBUG "Cannot load-balance (out of memory)\n");
-                return;
-        }
-
         for (;;) {
-                if (sched_domain_debug_one(sd, cpu, level, groupmask))
+                if (sched_domain_debug_one(sd, cpu, level, sched_domains_tmpmask))
                         break;
                 level++;
                 sd = sd->parent;
                 if (!sd)
                         break;
         }
-        free_cpumask_var(groupmask);
 }
 #else /* !CONFIG_SCHED_DEBUG */
 # define sched_domain_debug(sd, cpu) do { } while (0)
@@ -6311,12 +6825,11 @@ sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
         return 1;
 }
 
-static void free_rootdomain(struct root_domain *rd)
+static void free_rootdomain(struct rcu_head *rcu)
 {
-        synchronize_sched();
+        struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
 
         cpupri_cleanup(&rd->cpupri);
-
         free_cpumask_var(rd->rto_mask);
         free_cpumask_var(rd->online);
         free_cpumask_var(rd->span);
@@ -6357,7 +6870,7 @@ static void rq_attach_root(struct rq *rq, struct root_domain *rd)
         raw_spin_unlock_irqrestore(&rq->lock, flags);
 
         if (old_rd)
-                free_rootdomain(old_rd);
+                call_rcu_sched(&old_rd->rcu, free_rootdomain);
 }
 
 static int init_rootdomain(struct root_domain *rd)
@@ -6408,6 +6921,53 @@ static struct root_domain *alloc_rootdomain(void)
         return rd;
 }
 
+static void free_sched_groups(struct sched_group *sg, int free_sgp)
+{
+        struct sched_group *tmp, *first;
+
+        if (!sg)
+                return;
+
+        first = sg;
+        do {
+                tmp = sg->next;
+
+                if (free_sgp && atomic_dec_and_test(&sg->sgp->ref))
+                        kfree(sg->sgp);
+
+                kfree(sg);
+                sg = tmp;
+        } while (sg != first);
+}
+
+static void free_sched_domain(struct rcu_head *rcu)
+{
+        struct sched_domain *sd = container_of(rcu, struct sched_domain, rcu);
+
+        /*
+         * If its an overlapping domain it has private groups, iterate and
+         * nuke them all.
+         */
+        if (sd->flags & SD_OVERLAP) {
+                free_sched_groups(sd->groups, 1);
+        } else if (atomic_dec_and_test(&sd->groups->ref)) {
+                kfree(sd->groups->sgp);
+                kfree(sd->groups);
+        }
+        kfree(sd);
+}
+
+static void destroy_sched_domain(struct sched_domain *sd, int cpu)
+{
+        call_rcu(&sd->rcu, free_sched_domain);
+}
+
+static void destroy_sched_domains(struct sched_domain *sd, int cpu)
+{
+        for (; sd; sd = sd->parent)
+                destroy_sched_domain(sd, cpu);
+}
+
 /*
  * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
  * hold the hotplug lock.
@@ -6418,9 +6978,6 @@ cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
         struct rq *rq = cpu_rq(cpu);
         struct sched_domain *tmp;
 
-        for (tmp = sd; tmp; tmp = tmp->parent)
-                tmp->span_weight = cpumask_weight(sched_domain_span(tmp));
-
         /* Remove the sched domains which do not contribute to scheduling. */
         for (tmp = sd; tmp; ) {
                 struct sched_domain *parent = tmp->parent;
@@ -6431,12 +6988,15 @@ cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
                         tmp->parent = parent->parent;
                         if (parent->parent)
                                 parent->parent->child = tmp;
+                        destroy_sched_domain(parent, cpu);
                 } else
                         tmp = tmp->parent;
         }
 
         if (sd && sd_degenerate(sd)) {
+                tmp = sd;
                 sd = sd->parent;
+                destroy_sched_domain(tmp, cpu);
                 if (sd)
                         sd->child = NULL;
         }
@@ -6444,7 +7004,9 @@ cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
         sched_domain_debug(sd, cpu);
 
         rq_attach_root(rq, rd);
+        tmp = rq->sd;
         rcu_assign_pointer(rq->sd, sd);
+        destroy_sched_domains(tmp, cpu);
 }
 
 /* cpus with isolated domains */
@@ -6460,56 +7022,6 @@ static int __init isolated_cpu_setup(char *str)
 
 __setup("isolcpus=", isolated_cpu_setup);
 
-/*
- * init_sched_build_groups takes the cpumask we wish to span, and a pointer
- * to a function which identifies what group(along with sched group) a CPU
- * belongs to. The return value of group_fn must be a >= 0 and < nr_cpu_ids
- * (due to the fact that we keep track of groups covered with a struct cpumask).
- *
- * init_sched_build_groups will build a circular linked list of the groups
- * covered by the given span, and will set each group's ->cpumask correctly,
- * and ->cpu_power to 0.
- */
-static void
-init_sched_build_groups(const struct cpumask *span,
-                        const struct cpumask *cpu_map,
-                        int (*group_fn)(int cpu, const struct cpumask *cpu_map,
-                                        struct sched_group **sg,
-                                        struct cpumask *tmpmask),
-                        struct cpumask *covered, struct cpumask *tmpmask)
-{
-        struct sched_group *first = NULL, *last = NULL;
-        int i;
-
-        cpumask_clear(covered);
-
-        for_each_cpu(i, span) {
-                struct sched_group *sg;
-                int group = group_fn(i, cpu_map, &sg, tmpmask);
-                int j;
-
-                if (cpumask_test_cpu(i, covered))
-                        continue;
-
-                cpumask_clear(sched_group_cpus(sg));
-                sg->cpu_power = 0;
-
-                for_each_cpu(j, span) {
-                        if (group_fn(j, cpu_map, NULL, tmpmask) != group)
-                                continue;
-
-                        cpumask_set_cpu(j, covered);
-                        cpumask_set_cpu(j, sched_group_cpus(sg));
-                }
-                if (!first)
-                        first = sg;
-                if (last)
-                        last->next = sg;
-                last = sg;
-        }
-        last->next = first;
-}
-
 #define SD_NODES_PER_DOMAIN 16
 
 #ifdef CONFIG_NUMA
@@ -6526,7 +7038,7 @@ init_sched_build_groups(const struct cpumask *span,
  */
 static int find_next_best_node(int node, nodemask_t *used_nodes)
 {
-        int i, n, val, min_val, best_node = 0;
+        int i, n, val, min_val, best_node = -1;
 
         min_val = INT_MAX;
 
@@ -6550,7 +7062,8 @@ static int find_next_best_node(int node, nodemask_t *used_nodes)
                 }
         }
 
-        node_set(best_node, *used_nodes);
+        if (best_node != -1)
+                node_set(best_node, *used_nodes);
         return best_node;
 }
 
@@ -6576,293 +7089,197 @@ static void sched_domain_node_span(int node, struct cpumask *span)
 
         for (i = 1; i < SD_NODES_PER_DOMAIN; i++) {
                 int next_node = find_next_best_node(node, &used_nodes);
-
+                if (next_node < 0)
+                        break;
                 cpumask_or(span, span, cpumask_of_node(next_node));
         }
 }
+
+static const struct cpumask *cpu_node_mask(int cpu)
+{
+        lockdep_assert_held(&sched_domains_mutex);
+
+        sched_domain_node_span(cpu_to_node(cpu), sched_domains_tmpmask);
+
+        return sched_domains_tmpmask;
+}
+
+static const struct cpumask *cpu_allnodes_mask(int cpu)
+{
+        return cpu_possible_mask;
+}
 #endif /* CONFIG_NUMA */
 
-int sched_smt_power_savings = 0, sched_mc_power_savings = 0;
+static const struct cpumask *cpu_cpu_mask(int cpu)
+{
+        return cpumask_of_node(cpu_to_node(cpu));
+}
 
-/*
- * The cpus mask in sched_group and sched_domain hangs off the end.
- *
- * ( See the the comments in include/linux/sched.h:struct sched_group
- *   and struct sched_domain. )
- */
-struct static_sched_group {
-        struct sched_group sg;
-        DECLARE_BITMAP(cpus, CONFIG_NR_CPUS);
-};
+int sched_smt_power_savings = 0, sched_mc_power_savings = 0;
 
-struct static_sched_domain {
-        struct sched_domain sd;
-        DECLARE_BITMAP(span, CONFIG_NR_CPUS);
+struct sd_data {
+        struct sched_domain **__percpu sd;
+        struct sched_group **__percpu sg;
+        struct sched_group_power **__percpu sgp;
 };
 
 struct s_data {
-#ifdef CONFIG_NUMA
-        int                     sd_allnodes;
-        cpumask_var_t           domainspan;
-        cpumask_var_t           covered;
-        cpumask_var_t           notcovered;
-#endif
-        cpumask_var_t           nodemask;
-        cpumask_var_t           this_sibling_map;
-        cpumask_var_t           this_core_map;
-        cpumask_var_t           send_covered;
-        cpumask_var_t           tmpmask;
-        struct sched_group      **sched_group_nodes;
+        struct sched_domain ** __percpu sd;
         struct root_domain      *rd;
 };
 
 enum s_alloc {
-        sa_sched_groups = 0,
         sa_rootdomain,
-        sa_tmpmask,
-        sa_send_covered,
-        sa_this_core_map,
-        sa_this_sibling_map,
-        sa_nodemask,
-        sa_sched_group_nodes,
-#ifdef CONFIG_NUMA
-        sa_notcovered,
-        sa_covered,
-        sa_domainspan,
-#endif
+        sa_sd,
+        sa_sd_storage,
         sa_none,
 };
 
-/*
- * SMT sched-domains:
- */
-#ifdef CONFIG_SCHED_SMT
-static DEFINE_PER_CPU(struct static_sched_domain, cpu_domains);
-static DEFINE_PER_CPU(struct static_sched_group, sched_groups);
+struct sched_domain_topology_level;
 
-static int
-cpu_to_cpu_group(int cpu, const struct cpumask *cpu_map,
-                 struct sched_group **sg, struct cpumask *unused)
-{
-        if (sg)
-                *sg = &per_cpu(sched_groups, cpu).sg;
-        return cpu;
-}
-#endif /* CONFIG_SCHED_SMT */
+typedef struct sched_domain *(*sched_domain_init_f)(struct sched_domain_topology_level *tl, int cpu);
+typedef const struct cpumask *(*sched_domain_mask_f)(int cpu);
 
-/*
- * multi-core sched-domains:
- */
-#ifdef CONFIG_SCHED_MC
-static DEFINE_PER_CPU(struct static_sched_domain, core_domains);
-static DEFINE_PER_CPU(struct static_sched_group, sched_group_core);
-#endif /* CONFIG_SCHED_MC */
+#define SDTL_OVERLAP    0x01
 
-#if defined(CONFIG_SCHED_MC) && defined(CONFIG_SCHED_SMT)
-static int
-cpu_to_core_group(int cpu, const struct cpumask *cpu_map,
-                  struct sched_group **sg, struct cpumask *mask)
-{
-        int group;
+struct sched_domain_topology_level {
+        sched_domain_init_f init;
+        sched_domain_mask_f mask;
+        int                 flags;
+        struct sd_data      data;
+};
 
-        cpumask_and(mask, topology_thread_cpumask(cpu), cpu_map);
-        group = cpumask_first(mask);
-        if (sg)
-                *sg = &per_cpu(sched_group_core, group).sg;
-        return group;
-}
-#elif defined(CONFIG_SCHED_MC)
 static int
-cpu_to_core_group(int cpu, const struct cpumask *cpu_map,
-                  struct sched_group **sg, struct cpumask *unused)
+build_overlap_sched_groups(struct sched_domain *sd, int cpu)
 {
-        if (sg)
-                *sg = &per_cpu(sched_group_core, cpu).sg;
-        return cpu;
-}
-#endif
+        struct sched_group *first = NULL, *last = NULL, *groups = NULL, *sg;
+        const struct cpumask *span = sched_domain_span(sd);
+        struct cpumask *covered = sched_domains_tmpmask;
+        struct sd_data *sdd = sd->private;
+        struct sched_domain *child;
+        int i;
 
-static DEFINE_PER_CPU(struct static_sched_domain, phys_domains);
-static DEFINE_PER_CPU(struct static_sched_group, sched_group_phys);
+        cpumask_clear(covered);
 
-static int
-cpu_to_phys_group(int cpu, const struct cpumask *cpu_map,
-                  struct sched_group **sg, struct cpumask *mask)
-{
-        int group;
-#ifdef CONFIG_SCHED_MC
-        cpumask_and(mask, cpu_coregroup_mask(cpu), cpu_map);
-        group = cpumask_first(mask);
-#elif defined(CONFIG_SCHED_SMT)
-        cpumask_and(mask, topology_thread_cpumask(cpu), cpu_map);
-        group = cpumask_first(mask);
-#else
-        group = cpu;
-#endif
-        if (sg)
-                *sg = &per_cpu(sched_group_phys, group).sg;
-        return group;
-}
+        for_each_cpu(i, span) {
+                struct cpumask *sg_span;
 
-#ifdef CONFIG_NUMA
-/*
- * The init_sched_build_groups can't handle what we want to do with node
- * groups, so roll our own. Now each node has its own list of groups which
- * gets dynamically allocated.
- */
-static DEFINE_PER_CPU(struct static_sched_domain, node_domains);
-static struct sched_group ***sched_group_nodes_bycpu;
+                if (cpumask_test_cpu(i, covered))
+                        continue;
 
-static DEFINE_PER_CPU(struct static_sched_domain, allnodes_domains);
-static DEFINE_PER_CPU(struct static_sched_group, sched_group_allnodes);
+                sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
+                                GFP_KERNEL, cpu_to_node(i));
 
-static int cpu_to_allnodes_group(int cpu, const struct cpumask *cpu_map,
-                                 struct sched_group **sg,
-                                 struct cpumask *nodemask)
-{
-        int group;
+                if (!sg)
+                        goto fail;
 
-        cpumask_and(nodemask, cpumask_of_node(cpu_to_node(cpu)), cpu_map);
-        group = cpumask_first(nodemask);
+                sg_span = sched_group_cpus(sg);
 
-        if (sg)
-                *sg = &per_cpu(sched_group_allnodes, group).sg;
-        return group;
-}
+                child = *per_cpu_ptr(sdd->sd, i);
+                if (child->child) {
+                        child = child->child;
+                        cpumask_copy(sg_span, sched_domain_span(child));
+                } else
+                        cpumask_set_cpu(i, sg_span);
 
-static void init_numa_sched_groups_power(struct sched_group *group_head)
-{
-        struct sched_group *sg = group_head;
-        int j;
+                cpumask_or(covered, covered, sg_span);
 
-        if (!sg)
-                return;
-        do {
-                for_each_cpu(j, sched_group_cpus(sg)) {
-                        struct sched_domain *sd;
+                sg->sgp = *per_cpu_ptr(sdd->sgp, cpumask_first(sg_span));
+                atomic_inc(&sg->sgp->ref);
 
-                        sd = &per_cpu(phys_domains, j).sd;
-                        if (j != group_first_cpu(sd->groups)) {
-                                /*
-                                 * Only add "power" once for each
-                                 * physical package.
-                                 */
-                                continue;
-                        }
+                if (cpumask_test_cpu(cpu, sg_span))
+                        groups = sg;
 
-                        sg->cpu_power += sd->groups->cpu_power;
-                }
-                sg = sg->next;
-        } while (sg != group_head);
+                if (!first)
+                        first = sg;
+                if (last)
+                        last->next = sg;
+                last = sg;
+                last->next = first;
+        }
+        sd->groups = groups;
+
+        return 0;
+
+fail:
+        free_sched_groups(first, 0);
+
+        return -ENOMEM;
 }
 
-static int build_numa_sched_groups(struct s_data *d,
-                                   const struct cpumask *cpu_map, int num)
+static int get_group(int cpu, struct sd_data *sdd, struct sched_group **sg)
 {
-        struct sched_domain *sd;
-        struct sched_group *sg, *prev;
-        int n, j;
+        struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
+        struct sched_domain *child = sd->child;
 
-        cpumask_clear(d->covered);
-        cpumask_and(d->nodemask, cpumask_of_node(num), cpu_map);
-        if (cpumask_empty(d->nodemask)) {
-                d->sched_group_nodes[num] = NULL;
-                goto out;
+        if (child)
+                cpu = cpumask_first(sched_domain_span(child));
+
+        if (sg) {
+                *sg = *per_cpu_ptr(sdd->sg, cpu);
+                (*sg)->sgp = *per_cpu_ptr(sdd->sgp, cpu);
+                atomic_set(&(*sg)->sgp->ref, 1); /* for claim_allocations */
         }
 
-        sched_domain_node_span(num, d->domainspan);
-        cpumask_and(d->domainspan, d->domainspan, cpu_map);
+        return cpu;
+}
 
-        sg = kmalloc_node(sizeof(struct sched_group) + cpumask_size(),
-                          GFP_KERNEL, num);
-        if (!sg) {
-                printk(KERN_WARNING "Can not alloc domain group for node %d\n",
-                       num);
-                return -ENOMEM;
-        }
-        d->sched_group_nodes[num] = sg;
+/*
+ * build_sched_groups will build a circular linked list of the groups
+ * covered by the given span, and will set each group's ->cpumask correctly,
+ * and ->cpu_power to 0.
+ *
+ * Assumes the sched_domain tree is fully constructed
+ */
+static int
+build_sched_groups(struct sched_domain *sd, int cpu)
+{
+        struct sched_group *first = NULL, *last = NULL;
+        struct sd_data *sdd = sd->private;
+        const struct cpumask *span = sched_domain_span(sd);
+        struct cpumask *covered;
+        int i;
 
-        for_each_cpu(j, d->nodemask) {
-                sd = &per_cpu(node_domains, j).sd;
-                sd->groups = sg;
-        }
+        get_group(cpu, sdd, &sd->groups);
+        atomic_inc(&sd->groups->ref);
 
-        sg->cpu_power = 0;
-        cpumask_copy(sched_group_cpus(sg), d->nodemask);
-        sg->next = sg;
-        cpumask_or(d->covered, d->covered, d->nodemask);
+        if (cpu != cpumask_first(sched_domain_span(sd)))
+                return 0;
 
-        prev = sg;
-        for (j = 0; j < nr_node_ids; j++) {
-                n = (num + j) % nr_node_ids;
-                cpumask_complement(d->notcovered, d->covered);
-                cpumask_and(d->tmpmask, d->notcovered, cpu_map);
-                cpumask_and(d->tmpmask, d->tmpmask, d->domainspan);
-                if (cpumask_empty(d->tmpmask))
-                        break;
-                cpumask_and(d->tmpmask, d->tmpmask, cpumask_of_node(n));
-                if (cpumask_empty(d->tmpmask))
-                        continue;
-                sg = kmalloc_node(sizeof(struct sched_group) + cpumask_size(),
-                                  GFP_KERNEL, num);
-                if (!sg) {
-                        printk(KERN_WARNING
-                               "Can not alloc domain group for node %d\n", j);
-                        return -ENOMEM;
-                }
-                sg->cpu_power = 0;
-                cpumask_copy(sched_group_cpus(sg), d->tmpmask);
-                sg->next = prev->next;
-                cpumask_or(d->covered, d->covered, d->tmpmask);
-                prev->next = sg;
-                prev = sg;
-        }
-out:
-        return 0;
-}
-#endif /* CONFIG_NUMA */
+        lockdep_assert_held(&sched_domains_mutex);
+        covered = sched_domains_tmpmask;
 
-#ifdef CONFIG_NUMA
-/* Free memory allocated for various sched_group structures */
-static void free_sched_groups(const struct cpumask *cpu_map,
-                              struct cpumask *nodemask)
-{
-        int cpu, i;
+        cpumask_clear(covered);
 
-        for_each_cpu(cpu, cpu_map) {
-                struct sched_group **sched_group_nodes
-                        = sched_group_nodes_bycpu[cpu];
+        for_each_cpu(i, span) {
+                struct sched_group *sg;
+                int group = get_group(i, sdd, &sg);
+                int j;
 
-                if (!sched_group_nodes)
+                if (cpumask_test_cpu(i, covered))
                         continue;
 
-                for (i = 0; i < nr_node_ids; i++) {
-                        struct sched_group *oldsg, *sg = sched_group_nodes[i];
+                cpumask_clear(sched_group_cpus(sg));
+                sg->sgp->power = 0;
 
-                        cpumask_and(nodemask, cpumask_of_node(i), cpu_map);
-                        if (cpumask_empty(nodemask))
+                for_each_cpu(j, span) {
+                        if (get_group(j, sdd, NULL) != group)
                                 continue;
 
-                        if (sg == NULL)
-                                continue;
-                        sg = sg->next;
-next_sg:
-                        oldsg = sg;
-                        sg = sg->next;
-                        kfree(oldsg);
-                        if (oldsg != sched_group_nodes[i])
-                                goto next_sg;
+                        cpumask_set_cpu(j, covered);
+                        cpumask_set_cpu(j, sched_group_cpus(sg));
                 }
-                kfree(sched_group_nodes);
-                sched_group_nodes_bycpu[cpu] = NULL;
+
+                if (!first)
+                        first = sg;
+                if (last)
+                        last->next = sg;
+                last = sg;
         }
+        last->next = first;
+
+        return 0;
 }
-#else /* !CONFIG_NUMA */
-static void free_sched_groups(const struct cpumask *cpu_map,
-                              struct cpumask *nodemask)
-{
-}
-#endif /* CONFIG_NUMA */
 
 /*
  * Initialize sched groups cpu_power.
@@ -6876,46 +7293,19 @@ static void free_sched_groups(const struct cpumask *cpu_map,
  */
 static void init_sched_groups_power(int cpu, struct sched_domain *sd)
 {
-        struct sched_domain *child;
-        struct sched_group *group;
-        long power;
-        int weight;
-
-        WARN_ON(!sd || !sd->groups);
+        struct sched_group *sg = sd->groups;
 
-        if (cpu != group_first_cpu(sd->groups))
-                return;
-
-        child = sd->child;
+        WARN_ON(!sd || !sg);
 
-        sd->groups->cpu_power = 0;
+        do {
+                sg->group_weight = cpumask_weight(sched_group_cpus(sg));
+                sg = sg->next;
+        } while (sg != sd->groups);
 
-        if (!child) {
-                power = SCHED_LOAD_SCALE;
-                weight = cpumask_weight(sched_domain_span(sd));
-                /*
-                 * SMT siblings share the power of a single core.
-                 * Usually multiple threads get a better yield out of
-                 * that one core than a single thread would have,
-                 * reflect that in sd->smt_gain.
-                 */
-                if ((sd->flags & SD_SHARE_CPUPOWER) && weight > 1) {
-                        power *= sd->smt_gain;
-                        power /= weight;
-                        power >>= SCHED_LOAD_SHIFT;
-                }
-                sd->groups->cpu_power += power;
+        if (cpu != group_first_cpu(sg))
                 return;
-        }
 
-        /*
-         * Add cpu_power of each child group to this groups cpu_power.
-         */
-        group = child->groups;
-        do {
-                sd->groups->cpu_power += group->cpu_power;
-                group = group->next;
-        } while (group != child->groups);
+        update_group_power(sd, cpu);
 }
 
 /*
@@ -6929,15 +7319,15 @@ static void init_sched_groups_power(int cpu, struct sched_domain *sd)
 # define SD_INIT_NAME(sd, type)         do { } while (0)
 #endif
 
-#define SD_INIT(sd, type)       sd_init_##type(sd)
-
-#define SD_INIT_FUNC(type)      \
-static noinline void sd_init_##type(struct sched_domain *sd)    \
-{                                                               \
-        memset(sd, 0, sizeof(*sd));                             \
-        *sd = SD_##type##_INIT;                                 \
-        sd->level = SD_LV_##type;                               \
-        SD_INIT_NAME(sd, type);                                 \
+#define SD_INIT_FUNC(type)                                              \
+static noinline struct sched_domain *                                   \
+sd_init_##type(struct sched_domain_topology_level *tl, int cpu)         \
+{                                                                       \
+        struct sched_domain *sd = *per_cpu_ptr(tl->data.sd, cpu);       \
+        *sd = SD_##type##_INIT;                                         \
+        SD_INIT_NAME(sd, type);                                         \
+        sd->private = &tl->data;                                        \
+        return sd;                                                      \
 }
 
 SD_INIT_FUNC(CPU)
@@ -6951,15 +7341,19 @@ SD_INIT_FUNC(CPU)
 #ifdef CONFIG_SCHED_MC
  SD_INIT_FUNC(MC)
 #endif
+#ifdef CONFIG_SCHED_BOOK
+ SD_INIT_FUNC(BOOK)
+#endif
 
 static int default_relax_domain_level = -1;
+int sched_domain_level_max;
 
 static int __init setup_relax_domain_level(char *str)
 {
         unsigned long val;
 
         val = simple_strtoul(str, NULL, 0);
-        if (val < SD_LV_MAX)
+        if (val < sched_domain_level_max)
                 default_relax_domain_level = val;
 
         return 1;
@@ -6987,35 +7381,20 @@ static void set_domain_attribute(struct sched_domain *sd,
         }
 }
 
+static void __sdt_free(const struct cpumask *cpu_map);
+static int __sdt_alloc(const struct cpumask *cpu_map);
+
 static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
                                  const struct cpumask *cpu_map)
 {
         switch (what) {
-        case sa_sched_groups:
-                free_sched_groups(cpu_map, d->tmpmask); /* fall through */
-                d->sched_group_nodes = NULL;
         case sa_rootdomain:
-                free_rootdomain(d->rd); /* fall through */
-        case sa_tmpmask:
-                free_cpumask_var(d->tmpmask); /* fall through */
-        case sa_send_covered:
-                free_cpumask_var(d->send_covered); /* fall through */
-        case sa_this_core_map:
-                free_cpumask_var(d->this_core_map); /* fall through */
-        case sa_this_sibling_map:
-                free_cpumask_var(d->this_sibling_map); /* fall through */
-        case sa_nodemask:
-                free_cpumask_var(d->nodemask); /* fall through */
-        case sa_sched_group_nodes:
-#ifdef CONFIG_NUMA
-                kfree(d->sched_group_nodes); /* fall through */
-        case sa_notcovered:
-                free_cpumask_var(d->notcovered); /* fall through */
-        case sa_covered:
-                free_cpumask_var(d->covered); /* fall through */
-        case sa_domainspan:
-                free_cpumask_var(d->domainspan); /* fall through */
-#endif
+                if (!atomic_read(&d->rd->refcount))
+                        free_rootdomain(&d->rd->rcu); /* fall through */
+        case sa_sd:
+                free_percpu(d->sd); /* fall through */
+        case sa_sd_storage:
+                __sdt_free(cpu_map); /* fall through */
         case sa_none:
                 break;
         }
@@ -7024,270 +7403,233 @@ static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
 static enum s_alloc __visit_domain_allocation_hell(struct s_data *d,
                                                    const struct cpumask *cpu_map)
 {
-#ifdef CONFIG_NUMA
-        if (!alloc_cpumask_var(&d->domainspan, GFP_KERNEL))
-                return sa_none;
-        if (!alloc_cpumask_var(&d->covered, GFP_KERNEL))
-                return sa_domainspan;
-        if (!alloc_cpumask_var(&d->notcovered, GFP_KERNEL))
-                return sa_covered;
-        /* Allocate the per-node list of sched groups */
-        d->sched_group_nodes = kcalloc(nr_node_ids,
-                                      sizeof(struct sched_group *), GFP_KERNEL);
-        if (!d->sched_group_nodes) {
-                printk(KERN_WARNING "Can not alloc sched group node list\n");
-                return sa_notcovered;
-        }
-        sched_group_nodes_bycpu[cpumask_first(cpu_map)] = d->sched_group_nodes;
-#endif
-        if (!alloc_cpumask_var(&d->nodemask, GFP_KERNEL))
-                return sa_sched_group_nodes;
-        if (!alloc_cpumask_var(&d->this_sibling_map, GFP_KERNEL))
-                return sa_nodemask;
-        if (!alloc_cpumask_var(&d->this_core_map, GFP_KERNEL))
-                return sa_this_sibling_map;
-        if (!alloc_cpumask_var(&d->send_covered, GFP_KERNEL))
-                return sa_this_core_map;
-        if (!alloc_cpumask_var(&d->tmpmask, GFP_KERNEL))
-                return sa_send_covered;
+        memset(d, 0, sizeof(*d));
+
+        if (__sdt_alloc(cpu_map))
+                return sa_sd_storage;
+        d->sd = alloc_percpu(struct sched_domain *);
+        if (!d->sd)
+                return sa_sd_storage;
         d->rd = alloc_rootdomain();
-        if (!d->rd) {
-                printk(KERN_WARNING "Cannot alloc root domain\n");
-                return sa_tmpmask;
-        }
+        if (!d->rd)
+                return sa_sd;
         return sa_rootdomain;
 }
 
-static struct sched_domain *__build_numa_sched_domains(struct s_data *d,
-        const struct cpumask *cpu_map, struct sched_domain_attr *attr, int i)
+/*
+ * NULL the sd_data elements we've used to build the sched_domain and
+ * sched_group structure so that the subsequent __free_domain_allocs()
+ * will not free the data we're using.
+ */
+static void claim_allocations(int cpu, struct sched_domain *sd)
 {
-        struct sched_domain *sd = NULL;
-#ifdef CONFIG_NUMA
-        struct sched_domain *parent;
-
-        d->sd_allnodes = 0;
-        if (cpumask_weight(cpu_map) >
-            SD_NODES_PER_DOMAIN * cpumask_weight(d->nodemask)) {
-                sd = &per_cpu(allnodes_domains, i).sd;
-                SD_INIT(sd, ALLNODES);
-                set_domain_attribute(sd, attr);
-                cpumask_copy(sched_domain_span(sd), cpu_map);
-                cpu_to_allnodes_group(i, cpu_map, &sd->groups, d->tmpmask);
-                d->sd_allnodes = 1;
-        }
-        parent = sd;
-
-        sd = &per_cpu(node_domains, i).sd;
-        SD_INIT(sd, NODE);
-        set_domain_attribute(sd, attr);
-        sched_domain_node_span(cpu_to_node(i), sched_domain_span(sd));
-        sd->parent = parent;
-        if (parent)
-                parent->child = sd;
-        cpumask_and(sched_domain_span(sd), sched_domain_span(sd), cpu_map);
-#endif
-        return sd;
-}
+        struct sd_data *sdd = sd->private;
 
-static struct sched_domain *__build_cpu_sched_domain(struct s_data *d,
-        const struct cpumask *cpu_map, struct sched_domain_attr *attr,
-        struct sched_domain *parent, int i)
-{
-        struct sched_domain *sd;
-        sd = &per_cpu(phys_domains, i).sd;
-        SD_INIT(sd, CPU);
-        set_domain_attribute(sd, attr);
-        cpumask_copy(sched_domain_span(sd), d->nodemask);
-        sd->parent = parent;
-        if (parent)
-                parent->child = sd;
-        cpu_to_phys_group(i, cpu_map, &sd->groups, d->tmpmask);
-        return sd;
-}
+        WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
+        *per_cpu_ptr(sdd->sd, cpu) = NULL;
 
-static struct sched_domain *__build_mc_sched_domain(struct s_data *d,
-        const struct cpumask *cpu_map, struct sched_domain_attr *attr,
-        struct sched_domain *parent, int i)
-{
-        struct sched_domain *sd = parent;
-#ifdef CONFIG_SCHED_MC
-        sd = &per_cpu(core_domains, i).sd;
-        SD_INIT(sd, MC);
-        set_domain_attribute(sd, attr);
-        cpumask_and(sched_domain_span(sd), cpu_map, cpu_coregroup_mask(i));
-        sd->parent = parent;
-        parent->child = sd;
-        cpu_to_core_group(i, cpu_map, &sd->groups, d->tmpmask);
-#endif
-        return sd;
+        if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
+                *per_cpu_ptr(sdd->sg, cpu) = NULL;
+
+        if (atomic_read(&(*per_cpu_ptr(sdd->sgp, cpu))->ref))
+                *per_cpu_ptr(sdd->sgp, cpu) = NULL;
 }
 
-static struct sched_domain *__build_smt_sched_domain(struct s_data *d,
-        const struct cpumask *cpu_map, struct sched_domain_attr *attr,
-        struct sched_domain *parent, int i)
-{
-        struct sched_domain *sd = parent;
 #ifdef CONFIG_SCHED_SMT
-        sd = &per_cpu(cpu_domains, i).sd;
-        SD_INIT(sd, SIBLING);
-        set_domain_attribute(sd, attr);
-        cpumask_and(sched_domain_span(sd), cpu_map, topology_thread_cpumask(i));
-        sd->parent = parent;
-        parent->child = sd;
-        cpu_to_cpu_group(i, cpu_map, &sd->groups, d->tmpmask);
-#endif
-        return sd;
+static const struct cpumask *cpu_smt_mask(int cpu)
+{
+        return topology_thread_cpumask(cpu);
 }
+#endif
 
-static void build_sched_groups(struct s_data *d, enum sched_domain_level l,
-                               const struct cpumask *cpu_map, int cpu)
-{
-        switch (l) {
+/*
+ * Topology list, bottom-up.
+ */
+static struct sched_domain_topology_level default_topology[] = {
 #ifdef CONFIG_SCHED_SMT
-        case SD_LV_SIBLING: /* set up CPU (sibling) groups */
-                cpumask_and(d->this_sibling_map, cpu_map,
-                            topology_thread_cpumask(cpu));
-                if (cpu == cpumask_first(d->this_sibling_map))
-                        init_sched_build_groups(d->this_sibling_map, cpu_map,
-                                                &cpu_to_cpu_group,
-                                                d->send_covered, d->tmpmask);
-                break;
+        { sd_init_SIBLING, cpu_smt_mask, },
 #endif
 #ifdef CONFIG_SCHED_MC
-        case SD_LV_MC: /* set up multi-core groups */
-                cpumask_and(d->this_core_map, cpu_map, cpu_coregroup_mask(cpu));
-                if (cpu == cpumask_first(d->this_core_map))
-                        init_sched_build_groups(d->this_core_map, cpu_map,
-                                                &cpu_to_core_group,
-                                                d->send_covered, d->tmpmask);
-                break;
+        { sd_init_MC, cpu_coregroup_mask, },
 #endif
-        case SD_LV_CPU: /* set up physical groups */
-                cpumask_and(d->nodemask, cpumask_of_node(cpu), cpu_map);
-                if (!cpumask_empty(d->nodemask))
-                        init_sched_build_groups(d->nodemask, cpu_map,
-                                                &cpu_to_phys_group,
-                                                d->send_covered, d->tmpmask);
-                break;
+#ifdef CONFIG_SCHED_BOOK
+        { sd_init_BOOK, cpu_book_mask, },
+#endif
+        { sd_init_CPU, cpu_cpu_mask, },
 #ifdef CONFIG_NUMA
-        case SD_LV_ALLNODES:
-                init_sched_build_groups(cpu_map, cpu_map, &cpu_to_allnodes_group,
-                                        d->send_covered, d->tmpmask);
-                break;
+        { sd_init_NODE, cpu_node_mask, SDTL_OVERLAP, },
+        { sd_init_ALLNODES, cpu_allnodes_mask, },
 #endif
-        default:
-                break;
+        { NULL, },
+};
+
+static struct sched_domain_topology_level *sched_domain_topology = default_topology;
+
+static int __sdt_alloc(const struct cpumask *cpu_map)
+{
+        struct sched_domain_topology_level *tl;
+        int j;
+
+        for (tl = sched_domain_topology; tl->init; tl++) {
+                struct sd_data *sdd = &tl->data;
+
+                sdd->sd = alloc_percpu(struct sched_domain *);
+                if (!sdd->sd)
+                        return -ENOMEM;
+
+                sdd->sg = alloc_percpu(struct sched_group *);
+                if (!sdd->sg)
+                        return -ENOMEM;
+
+                sdd->sgp = alloc_percpu(struct sched_group_power *);
+                if (!sdd->sgp)
+                        return -ENOMEM;
+
+                for_each_cpu(j, cpu_map) {
+                        struct sched_domain *sd;
+                        struct sched_group *sg;
+                        struct sched_group_power *sgp;
+
+                        sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(),
+                                        GFP_KERNEL, cpu_to_node(j));
+                        if (!sd)
+                                return -ENOMEM;
+
+                        *per_cpu_ptr(sdd->sd, j) = sd;
+
+                        sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
+                                        GFP_KERNEL, cpu_to_node(j));
+                        if (!sg)
+                                return -ENOMEM;
+
+                        *per_cpu_ptr(sdd->sg, j) = sg;
+
+                        sgp = kzalloc_node(sizeof(struct sched_group_power),
+                                        GFP_KERNEL, cpu_to_node(j));
+                        if (!sgp)
+                                return -ENOMEM;
+
+                        *per_cpu_ptr(sdd->sgp, j) = sgp;
+                }
+        }
+
+        return 0;
+}
+
+static void __sdt_free(const struct cpumask *cpu_map)
+{
+        struct sched_domain_topology_level *tl;
+        int j;
+
+        for (tl = sched_domain_topology; tl->init; tl++) {
+                struct sd_data *sdd = &tl->data;
+
+                for_each_cpu(j, cpu_map) {
+                        struct sched_domain *sd = *per_cpu_ptr(sdd->sd, j);
+                        if (sd && (sd->flags & SD_OVERLAP))
+                                free_sched_groups(sd->groups, 0);
+                        kfree(*per_cpu_ptr(sdd->sg, j));
+                        kfree(*per_cpu_ptr(sdd->sgp, j));
+                }
+                free_percpu(sdd->sd);
+                free_percpu(sdd->sg);
+                free_percpu(sdd->sgp);
+        }
+}
+
+struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
+                struct s_data *d, const struct cpumask *cpu_map,
+                struct sched_domain_attr *attr, struct sched_domain *child,
+                int cpu)
+{
+        struct sched_domain *sd = tl->init(tl, cpu);
+        if (!sd)
+                return child;
+
+        set_domain_attribute(sd, attr);
+        cpumask_and(sched_domain_span(sd), cpu_map, tl->mask(cpu));
+        if (child) {
+                sd->level = child->level + 1;
+                sched_domain_level_max = max(sched_domain_level_max, sd->level);
+                child->parent = sd;
         }
+        sd->child = child;
+
+        return sd;
 }
 
 /*
  * Build sched domains for a given set of cpus and attach the sched domains
  * to the individual cpus
  */
-static int __build_sched_domains(const struct cpumask *cpu_map,
-                                 struct sched_domain_attr *attr)
+static int build_sched_domains(const struct cpumask *cpu_map,
+                               struct sched_domain_attr *attr)
 {
         enum s_alloc alloc_state = sa_none;
-        struct s_data d;
         struct sched_domain *sd;
-        int i;
-#ifdef CONFIG_NUMA
-        d.sd_allnodes = 0;
-#endif
+        struct s_data d;
+        int i, ret = -ENOMEM;
 
         alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
         if (alloc_state != sa_rootdomain)
                 goto error;
-        alloc_state = sa_sched_groups;
-
-        /*
-         * Set up domains for cpus specified by the cpu_map.
-         */
-        for_each_cpu(i, cpu_map) {
-                cpumask_and(d.nodemask, cpumask_of_node(cpu_to_node(i)),
-                            cpu_map);
-
-                sd = __build_numa_sched_domains(&d, cpu_map, attr, i);
-                sd = __build_cpu_sched_domain(&d, cpu_map, attr, sd, i);
-                sd = __build_mc_sched_domain(&d, cpu_map, attr, sd, i);
-                sd = __build_smt_sched_domain(&d, cpu_map, attr, sd, i);
-        }
 
+        /* Set up domains for cpus specified by the cpu_map. */
         for_each_cpu(i, cpu_map) {
-                build_sched_groups(&d, SD_LV_SIBLING, cpu_map, i);
-                build_sched_groups(&d, SD_LV_MC, cpu_map, i);
-        }
-
-        /* Set up physical groups */
-        for (i = 0; i < nr_node_ids; i++)
-                build_sched_groups(&d, SD_LV_CPU, cpu_map, i);
-
-#ifdef CONFIG_NUMA
-        /* Set up node groups */
-        if (d.sd_allnodes)
-                build_sched_groups(&d, SD_LV_ALLNODES, cpu_map, 0);
+                struct sched_domain_topology_level *tl;
+
+                sd = NULL;
+                for (tl = sched_domain_topology; tl->init; tl++) {
+                        sd = build_sched_domain(tl, &d, cpu_map, attr, sd, i);
+                        if (tl->flags & SDTL_OVERLAP || sched_feat(FORCE_SD_OVERLAP))
+                                sd->flags |= SD_OVERLAP;
+                        if (cpumask_equal(cpu_map, sched_domain_span(sd)))
+                                break;
+                }
 
-        for (i = 0; i < nr_node_ids; i++)
-                if (build_numa_sched_groups(&d, cpu_map, i))
-                        goto error;
-#endif
+                while (sd->child)
+                        sd = sd->child;
 
-        /* Calculate CPU power for physical packages and nodes */
-#ifdef CONFIG_SCHED_SMT
-        for_each_cpu(i, cpu_map) {
-                sd = &per_cpu(cpu_domains, i).sd;
-                init_sched_groups_power(i, sd);
-        }
-#endif
-#ifdef CONFIG_SCHED_MC
-        for_each_cpu(i, cpu_map) {
-                sd = &per_cpu(core_domains, i).sd;
-                init_sched_groups_power(i, sd);
+                *per_cpu_ptr(d.sd, i) = sd;
         }
-#endif
 
+        /* Build the groups for the domains */
         for_each_cpu(i, cpu_map) {
-                sd = &per_cpu(phys_domains, i).sd;
-                init_sched_groups_power(i, sd);
+                for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+                        sd->span_weight = cpumask_weight(sched_domain_span(sd));
+                        if (sd->flags & SD_OVERLAP) {
+                                if (build_overlap_sched_groups(sd, i))
+                                        goto error;
+                        } else {
+                                if (build_sched_groups(sd, i))
+                                        goto error;
+                        }
+                }
         }
 
-#ifdef CONFIG_NUMA
-        for (i = 0; i < nr_node_ids; i++)
-                init_numa_sched_groups_power(d.sched_group_nodes[i]);
-
-        if (d.sd_allnodes) {
-                struct sched_group *sg;
+        /* Calculate CPU power for physical packages and nodes */
+        for (i = nr_cpumask_bits-1; i >= 0; i--) {
+                if (!cpumask_test_cpu(i, cpu_map))
+                        continue;
 
-                cpu_to_allnodes_group(cpumask_first(cpu_map), cpu_map, &sg,
-                                                                d.tmpmask);
-                init_numa_sched_groups_power(sg);
+                for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
+                        claim_allocations(i, sd);
+                        init_sched_groups_power(i, sd);
+                }
         }
-#endif
 
         /* Attach the domains */
+        rcu_read_lock();
         for_each_cpu(i, cpu_map) {
-#ifdef CONFIG_SCHED_SMT
-                sd = &per_cpu(cpu_domains, i).sd;
-#elif defined(CONFIG_SCHED_MC)
-                sd = &per_cpu(core_domains, i).sd;
-#else
-                sd = &per_cpu(phys_domains, i).sd;
-#endif
+                sd = *per_cpu_ptr(d.sd, i);
                 cpu_attach_domain(sd, d.rd, i);
         }
+        rcu_read_unlock();
 
-        d.sched_group_nodes = NULL; /* don't free this we still need it */
-        __free_domain_allocs(&d, sa_tmpmask, cpu_map);
-        return 0;
-
+        ret = 0;
 error:
         __free_domain_allocs(&d, alloc_state, cpu_map);
-        return -ENOMEM;
-}
-
-static int build_sched_domains(const struct cpumask *cpu_map)
-{
-        return __build_sched_domains(cpu_map, NULL);
+        return ret;
 }
 
 static cpumask_var_t *doms_cur; /* current sched domains */
@@ -7342,7 +7684,7 @@ void free_sched_domains(cpumask_var_t doms[], unsigned int ndoms)
  * For now this just excludes isolated cpus, but could be used to
  * exclude other special cases in the future.
  */
-static int arch_init_sched_domains(const struct cpumask *cpu_map)
+static int init_sched_domains(const struct cpumask *cpu_map)
 {
         int err;
 
@@ -7353,32 +7695,24 @@ static int arch_init_sched_domains(const struct cpumask *cpu_map)
                 doms_cur = &fallback_doms;
         cpumask_andnot(doms_cur[0], cpu_map, cpu_isolated_map);
         dattr_cur = NULL;
-        err = build_sched_domains(doms_cur[0]);
+        err = build_sched_domains(doms_cur[0], NULL);
         register_sched_domain_sysctl();
 
         return err;
 }
 
-static void arch_destroy_sched_domains(const struct cpumask *cpu_map,
-                                       struct cpumask *tmpmask)
-{
-        free_sched_groups(cpu_map, tmpmask);
-}
-
 /*
  * Detach sched domains from a group of cpus specified in cpu_map
  * These cpus will now be attached to the NULL domain
  */
 static void detach_destroy_domains(const struct cpumask *cpu_map)
 {
-        /* Save because hotplug lock held. */
-        static DECLARE_BITMAP(tmpmask, CONFIG_NR_CPUS);
         int i;
 
+        rcu_read_lock();
         for_each_cpu(i, cpu_map)
                 cpu_attach_domain(NULL, &def_root_domain, i);
-        synchronize_sched();
-        arch_destroy_sched_domains(cpu_map, to_cpumask(tmpmask));
+        rcu_read_unlock();
 }
 
 /* handle null as "default" */
@@ -7467,8 +7801,7 @@ match1:
                                 goto match2;
                 }
                 /* no match - add a new doms_new */
-                __build_sched_domains(doms_new[i],
-                                        dattr_new ? dattr_new + i : NULL);
+                build_sched_domains(doms_new[i], dattr_new ? dattr_new + i : NULL);
 match2:
                 ;
         }
@@ -7487,7 +7820,7 @@ match2:
 }
 
 #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
-static void arch_reinit_sched_domains(void)
+static void reinit_sched_domains(void)
 {
         get_online_cpus();
 
@@ -7520,7 +7853,7 @@ static ssize_t sched_power_savings_store(const char *buf, size_t count, int smt)
         else
                 sched_mc_power_savings = level;
 
-        arch_reinit_sched_domains();
+        reinit_sched_domains();
 
         return count;
 }
@@ -7639,14 +7972,9 @@ void __init sched_init_smp(void)
         alloc_cpumask_var(&non_isolated_cpus, GFP_KERNEL);
         alloc_cpumask_var(&fallback_doms, GFP_KERNEL);
 
-#if defined(CONFIG_NUMA)
-        sched_group_nodes_bycpu = kzalloc(nr_cpu_ids * sizeof(void **),
-                                                                GFP_KERNEL);
-        BUG_ON(sched_group_nodes_bycpu == NULL);
-#endif
         get_online_cpus();
         mutex_lock(&sched_domains_mutex);
-        arch_init_sched_domains(cpu_active_mask);
+        init_sched_domains(cpu_active_mask);
         cpumask_andnot(non_isolated_cpus, cpu_possible_mask, cpu_isolated_map);
         if (cpumask_empty(non_isolated_cpus))
                 cpumask_set_cpu(smp_processor_id(), non_isolated_cpus);
@@ -7691,8 +8019,15 @@ static void init_cfs_rq(struct cfs_rq *cfs_rq, struct rq *rq)
         INIT_LIST_HEAD(&cfs_rq->tasks);
 #ifdef CONFIG_FAIR_GROUP_SCHED
         cfs_rq->rq = rq;
+        /* allow initial update_cfs_load() to truncate */
+#ifdef CONFIG_SMP
+        cfs_rq->load_stamp = 1;
+#endif
 #endif
         cfs_rq->min_vruntime = (u64)(-(1LL << 20));
+#ifndef CONFIG_64BIT
+        cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
+#endif
 }
 
 static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
@@ -7733,18 +8068,16 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 static void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
-                                struct sched_entity *se, int cpu, int add,
+                                struct sched_entity *se, int cpu,
                                 struct sched_entity *parent)
 {
         struct rq *rq = cpu_rq(cpu);
         tg->cfs_rq[cpu] = cfs_rq;
         init_cfs_rq(cfs_rq, rq);
         cfs_rq->tg = tg;
-        if (add)
-                list_add(&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list);
 
         tg->se[cpu] = se;
-        /* se could be NULL for init_task_group */
+        /* se could be NULL for root_task_group */
         if (!se)
                 return;
 
@@ -7754,15 +8087,14 @@ static void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq,
                 se->cfs_rq = parent->my_q;
 
         se->my_q = cfs_rq;
-        se->load.weight = tg->shares;
-        se->load.inv_weight = 0;
+        update_load_set(&se->load, 0);
         se->parent = parent;
 }
 #endif
 
 #ifdef CONFIG_RT_GROUP_SCHED
 static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
-                struct sched_rt_entity *rt_se, int cpu, int add,
+                struct sched_rt_entity *rt_se, int cpu,
                 struct sched_rt_entity *parent)
 {
         struct rq *rq = cpu_rq(cpu);
@@ -7771,8 +8103,6 @@ static void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq,
         init_rt_rq(rt_rq, rq);
         rt_rq->tg = tg;
         rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime;
-        if (add)
-                list_add(&rt_rq->leaf_rt_rq_list, &rq->leaf_rt_rq_list);
 
         tg->rt_se[cpu] = rt_se;
         if (!rt_se)
@@ -7807,18 +8137,18 @@ void __init sched_init(void)
                 ptr = (unsigned long)kzalloc(alloc_size, GFP_NOWAIT);
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
-                init_task_group.se = (struct sched_entity **)ptr;
+                root_task_group.se = (struct sched_entity **)ptr;
                 ptr += nr_cpu_ids * sizeof(void **);
 
-                init_task_group.cfs_rq = (struct cfs_rq **)ptr;
+                root_task_group.cfs_rq = (struct cfs_rq **)ptr;
                 ptr += nr_cpu_ids * sizeof(void **);
 
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 #ifdef CONFIG_RT_GROUP_SCHED
-                init_task_group.rt_se = (struct sched_rt_entity **)ptr;
+                root_task_group.rt_se = (struct sched_rt_entity **)ptr;
                 ptr += nr_cpu_ids * sizeof(void **);
 
-                init_task_group.rt_rq = (struct rt_rq **)ptr;
+                root_task_group.rt_rq = (struct rt_rq **)ptr;
                 ptr += nr_cpu_ids * sizeof(void **);
 
 #endif /* CONFIG_RT_GROUP_SCHED */
@@ -7838,20 +8168,16 @@ void __init sched_init(void)
                         global_rt_period(), global_rt_runtime());
 
 #ifdef CONFIG_RT_GROUP_SCHED
-        init_rt_bandwidth(&init_task_group.rt_bandwidth,
+        init_rt_bandwidth(&root_task_group.rt_bandwidth,
                         global_rt_period(), global_rt_runtime());
 #endif /* CONFIG_RT_GROUP_SCHED */
 
 #ifdef CONFIG_CGROUP_SCHED
-        list_add(&init_task_group.list, &task_groups);
-        INIT_LIST_HEAD(&init_task_group.children);
-
+        list_add(&root_task_group.list, &task_groups);
+        INIT_LIST_HEAD(&root_task_group.children);
+        autogroup_init(&init_task);
 #endif /* CONFIG_CGROUP_SCHED */
 
-#if defined CONFIG_FAIR_GROUP_SCHED && defined CONFIG_SMP
-        update_shares_data = __alloc_percpu(nr_cpu_ids * sizeof(unsigned long),
-                                            __alignof__(unsigned long));
-#endif
         for_each_possible_cpu(i) {
                 struct rq *rq;
 
@@ -7863,38 +8189,34 @@ void __init sched_init(void)
                 init_cfs_rq(&rq->cfs, rq);
                 init_rt_rq(&rq->rt, rq);
 #ifdef CONFIG_FAIR_GROUP_SCHED
-                init_task_group.shares = init_task_group_load;
+                root_task_group.shares = root_task_group_load;
                 INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
-#ifdef CONFIG_CGROUP_SCHED
                 /*
-                 * How much cpu bandwidth does init_task_group get?
+                 * How much cpu bandwidth does root_task_group get?
                  *
                  * In case of task-groups formed thr' the cgroup filesystem, it
                  * gets 100% of the cpu resources in the system. This overall
                  * system cpu resource is divided among the tasks of
-                 * init_task_group and its child task-groups in a fair manner,
+                 * root_task_group and its child task-groups in a fair manner,
                  * based on each entity's (task or task-group's) weight
                  * (se->load.weight).
                  *
-                 * In other words, if init_task_group has 10 tasks of weight
+                 * In other words, if root_task_group has 10 tasks of weight
                  * 1024) and two child groups A0 and A1 (of weight 1024 each),
                  * then A0's share of the cpu resource is:
                  *
                  *      A0's bandwidth = 1024 / (10*1024 + 1024 + 1024) = 8.33%
                  *
-                 * We achieve this by letting init_task_group's tasks sit
-                 * directly in rq->cfs (i.e init_task_group->se[] = NULL).
+                 * We achieve this by letting root_task_group's tasks sit
+                 * directly in rq->cfs (i.e root_task_group->se[] = NULL).
                  */
-                init_tg_cfs_entry(&init_task_group, &rq->cfs, NULL, i, 1, NULL);
-#endif
+                init_tg_cfs_entry(&root_task_group, &rq->cfs, NULL, i, NULL);
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
                 rq->rt.rt_runtime = def_rt_bandwidth.rt_runtime;
 #ifdef CONFIG_RT_GROUP_SCHED
                 INIT_LIST_HEAD(&rq->leaf_rt_rq_list);
-#ifdef CONFIG_CGROUP_SCHED
-                init_tg_rt_entry(&init_task_group, &rq->rt, NULL, i, 1, NULL);
-#endif
+                init_tg_rt_entry(&root_task_group, &rq->rt, NULL, i, NULL);
 #endif
 
                 for (j = 0; j < CPU_LOAD_IDX_MAX; j++)
@@ -7905,7 +8227,7 @@ void __init sched_init(void)
 #ifdef CONFIG_SMP
                 rq->sd = NULL;
                 rq->rd = NULL;
-                rq->cpu_power = SCHED_LOAD_SCALE;
+                rq->cpu_power = SCHED_POWER_SCALE;
                 rq->post_schedule = 0;
                 rq->active_balance = 0;
                 rq->next_balance = jiffies;
@@ -7962,6 +8284,7 @@ void __init sched_init(void)
         /* Allocate the nohz_cpu_mask if CONFIG_CPUMASK_OFFSTACK */
         zalloc_cpumask_var(&nohz_cpu_mask, GFP_NOWAIT);
 #ifdef CONFIG_SMP
+        zalloc_cpumask_var(&sched_domains_tmpmask, GFP_NOWAIT);
 #ifdef CONFIG_NO_HZ
         zalloc_cpumask_var(&nohz.idle_cpus_mask, GFP_NOWAIT);
         alloc_cpumask_var(&nohz.grp_idle_mask, GFP_NOWAIT);
@@ -7974,8 +8297,6 @@ void __init sched_init(void)
                 zalloc_cpumask_var(&cpu_isolated_map, GFP_NOWAIT);
 #endif /* SMP */
 
-        perf_event_init();
-
         scheduler_running = 1;
 }
 
@@ -7984,7 +8305,7 @@ static inline int preempt_count_equals(int preempt_offset)
 {
         int nested = (preempt_count() & ~PREEMPT_ACTIVE) + rcu_preempt_depth();
 
-        return (nested == PREEMPT_INATOMIC_BASE + preempt_offset);
+        return (nested == preempt_offset);
 }
 
 void __might_sleep(const char *file, int line, int preempt_offset)
@@ -8019,9 +8340,11 @@ EXPORT_SYMBOL(__might_sleep);
 #ifdef CONFIG_MAGIC_SYSRQ
 static void normalize_task(struct rq *rq, struct task_struct *p)
 {
+        const struct sched_class *prev_class = p->sched_class;
+        int old_prio = p->prio;
         int on_rq;
 
-        on_rq = p->se.on_rq;
+        on_rq = p->on_rq;
         if (on_rq)
                 deactivate_task(rq, p, 0);
         __setscheduler(rq, p, SCHED_NORMAL, 0);
@@ -8029,6 +8352,8 @@ static void normalize_task(struct rq *rq, struct task_struct *p)
                 activate_task(rq, p, 0);
                 resched_task(rq->curr);
         }
+
+        check_class_changed(rq, p, prev_class, old_prio);
 }
 
 void normalize_rt_tasks(void)
@@ -8144,7 +8469,6 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
 {
         struct cfs_rq *cfs_rq;
         struct sched_entity *se;
-        struct rq *rq;
         int i;
 
         tg->cfs_rq = kzalloc(sizeof(cfs_rq) * nr_cpu_ids, GFP_KERNEL);
@@ -8157,8 +8481,6 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
         tg->shares = NICE_0_LOAD;
 
         for_each_possible_cpu(i) {
-                rq = cpu_rq(i);
-
                 cfs_rq = kzalloc_node(sizeof(struct cfs_rq),
                                       GFP_KERNEL, cpu_to_node(i));
                 if (!cfs_rq)
@@ -8169,26 +8491,32 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
                 if (!se)
                         goto err_free_rq;
 
-                init_tg_cfs_entry(tg, cfs_rq, se, i, 0, parent->se[i]);
+                init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]);
         }
 
         return 1;
 
- err_free_rq:
+err_free_rq:
         kfree(cfs_rq);
- err:
+err:
         return 0;
 }
 
-static inline void register_fair_sched_group(struct task_group *tg, int cpu)
-{
-        list_add_rcu(&tg->cfs_rq[cpu]->leaf_cfs_rq_list,
-                        &cpu_rq(cpu)->leaf_cfs_rq_list);
-}
-
 static inline void unregister_fair_sched_group(struct task_group *tg, int cpu)
 {
-        list_del_rcu(&tg->cfs_rq[cpu]->leaf_cfs_rq_list);
+        struct rq *rq = cpu_rq(cpu);
+        unsigned long flags;
+
+        /*
+        * Only empty task groups can be destroyed; so we can speculatively
+        * check on_list without danger of it being re-added.
+        */
+        if (!tg->cfs_rq[cpu]->on_list)
+                return;
+
+        raw_spin_lock_irqsave(&rq->lock, flags);
+        list_del_leaf_cfs_rq(tg->cfs_rq[cpu]);
+        raw_spin_unlock_irqrestore(&rq->lock, flags);
 }
 #else /* !CONFG_FAIR_GROUP_SCHED */
 static inline void free_fair_sched_group(struct task_group *tg)
@@ -8201,10 +8529,6 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
         return 1;
 }
 
-static inline void register_fair_sched_group(struct task_group *tg, int cpu)
-{
-}
-
 static inline void unregister_fair_sched_group(struct task_group *tg, int cpu)
 {
 }
@@ -8233,7 +8557,6 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
 {
         struct rt_rq *rt_rq;
         struct sched_rt_entity *rt_se;
-        struct rq *rq;
         int i;
 
         tg->rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids, GFP_KERNEL);
@@ -8247,8 +8570,6 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
                         ktime_to_ns(def_rt_bandwidth.rt_period), 0);
 
         for_each_possible_cpu(i) {
-                rq = cpu_rq(i);
-
                 rt_rq = kzalloc_node(sizeof(struct rt_rq),
                                      GFP_KERNEL, cpu_to_node(i));
                 if (!rt_rq)
@@ -8259,27 +8580,16 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
                 if (!rt_se)
                         goto err_free_rq;
 
-                init_tg_rt_entry(tg, rt_rq, rt_se, i, 0, parent->rt_se[i]);
+                init_tg_rt_entry(tg, rt_rq, rt_se, i, parent->rt_se[i]);
         }
 
         return 1;
 
- err_free_rq:
+err_free_rq:
         kfree(rt_rq);
- err:
+err:
         return 0;
 }
-
-static inline void register_rt_sched_group(struct task_group *tg, int cpu)
-{
-        list_add_rcu(&tg->rt_rq[cpu]->leaf_rt_rq_list,
-                        &cpu_rq(cpu)->leaf_rt_rq_list);
-}
-
-static inline void unregister_rt_sched_group(struct task_group *tg, int cpu)
-{
-        list_del_rcu(&tg->rt_rq[cpu]->leaf_rt_rq_list);
-}
 #else /* !CONFIG_RT_GROUP_SCHED */
 static inline void free_rt_sched_group(struct task_group *tg)
 {
@@ -8290,14 +8600,6 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
 {
         return 1;
 }
-
-static inline void register_rt_sched_group(struct task_group *tg, int cpu)
-{
-}
-
-static inline void unregister_rt_sched_group(struct task_group *tg, int cpu)
-{
-}
 #endif /* CONFIG_RT_GROUP_SCHED */
 
 #ifdef CONFIG_CGROUP_SCHED
@@ -8305,6 +8607,7 @@ static void free_sched_group(struct task_group *tg)
 {
         free_fair_sched_group(tg);
         free_rt_sched_group(tg);
+        autogroup_free(tg);
         kfree(tg);
 }
 
@@ -8313,7 +8616,6 @@ struct task_group *sched_create_group(struct task_group *parent)
 {
         struct task_group *tg;
         unsigned long flags;
-        int i;
 
         tg = kzalloc(sizeof(*tg), GFP_KERNEL);
         if (!tg)
@@ -8326,10 +8628,6 @@ struct task_group *sched_create_group(struct task_group *parent)
                 goto err;
 
         spin_lock_irqsave(&task_group_lock, flags);
-        for_each_possible_cpu(i) {
-                register_fair_sched_group(tg, i);
-                register_rt_sched_group(tg, i);
-        }
         list_add_rcu(&tg->list, &task_groups);
 
         WARN_ON(!parent); /* root should already exist */
@@ -8359,11 +8657,11 @@ void sched_destroy_group(struct task_group *tg)
         unsigned long flags;
         int i;
 
-        spin_lock_irqsave(&task_group_lock, flags);
-        for_each_possible_cpu(i) {
+        /* end participation in shares distribution */
+        for_each_possible_cpu(i)
                 unregister_fair_sched_group(tg, i);
-                unregister_rt_sched_group(tg, i);
-        }
+
+        spin_lock_irqsave(&task_group_lock, flags);
         list_del_rcu(&tg->list);
         list_del_rcu(&tg->siblings);
         spin_unlock_irqrestore(&task_group_lock, flags);
@@ -8386,57 +8684,30 @@ void sched_move_task(struct task_struct *tsk)
         rq = task_rq_lock(tsk, &flags);
 
         running = task_current(rq, tsk);
-        on_rq = tsk->se.on_rq;
+        on_rq = tsk->on_rq;
 
         if (on_rq)
                 dequeue_task(rq, tsk, 0);
         if (unlikely(running))
                 tsk->sched_class->put_prev_task(rq, tsk);
 
-        set_task_rq(tsk, task_cpu(tsk));
-
 #ifdef CONFIG_FAIR_GROUP_SCHED
-        if (tsk->sched_class->moved_group)
-                tsk->sched_class->moved_group(tsk, on_rq);
+        if (tsk->sched_class->task_move_group)
+                tsk->sched_class->task_move_group(tsk, on_rq);
+        else
 #endif
+                set_task_rq(tsk, task_cpu(tsk));
 
         if (unlikely(running))
                 tsk->sched_class->set_curr_task(rq);
         if (on_rq)
                 enqueue_task(rq, tsk, 0);
 
-        task_rq_unlock(rq, &flags);
+        task_rq_unlock(rq, tsk, &flags);
 }
 #endif /* CONFIG_CGROUP_SCHED */
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
-static void __set_se_shares(struct sched_entity *se, unsigned long shares)
-{
-        struct cfs_rq *cfs_rq = se->cfs_rq;
-        int on_rq;
-
-        on_rq = se->on_rq;
-        if (on_rq)
-                dequeue_entity(cfs_rq, se, 0);
-
-        se->load.weight = shares;
-        se->load.inv_weight = 0;
-
-        if (on_rq)
-                enqueue_entity(cfs_rq, se, 0);
-}
-
-static void set_se_shares(struct sched_entity *se, unsigned long shares)
-{
-        struct cfs_rq *cfs_rq = se->cfs_rq;
-        struct rq *rq = cfs_rq->rq;
-        unsigned long flags;
-
-        raw_spin_lock_irqsave(&rq->lock, flags);
-        __set_se_shares(se, shares);
-        raw_spin_unlock_irqrestore(&rq->lock, flags);
-}
-
 static DEFINE_MUTEX(shares_mutex);
 
 int sched_group_set_shares(struct task_group *tg, unsigned long shares)
@@ -8450,46 +8721,25 @@ int sched_group_set_shares(struct task_group *tg, unsigned long shares)
         if (!tg->se[0])
                 return -EINVAL;
 
-        if (shares < MIN_SHARES)
-                shares = MIN_SHARES;
-        else if (shares > MAX_SHARES)
-                shares = MAX_SHARES;
+        shares = clamp(shares, scale_load(MIN_SHARES), scale_load(MAX_SHARES));
 
         mutex_lock(&shares_mutex);
         if (tg->shares == shares)
                 goto done;
 
-        spin_lock_irqsave(&task_group_lock, flags);
-        for_each_possible_cpu(i)
-                unregister_fair_sched_group(tg, i);
-        list_del_rcu(&tg->siblings);
-        spin_unlock_irqrestore(&task_group_lock, flags);
-
-        /* wait for any ongoing reference to this group to finish */
-        synchronize_sched();
-
-        /*
-         * Now we are free to modify the group's share on each cpu
-         * w/o tripping rebalance_share or load_balance_fair.
-         */
         tg->shares = shares;
         for_each_possible_cpu(i) {
-                /*
-                 * force a rebalance
-                 */
-                cfs_rq_set_shares(tg->cfs_rq[i], 0);
-                set_se_shares(tg->se[i], shares);
+                struct rq *rq = cpu_rq(i);
+                struct sched_entity *se;
+
+                se = tg->se[i];
+                /* Propagate contribution to hierarchy */
+                raw_spin_lock_irqsave(&rq->lock, flags);
+                for_each_sched_entity(se)
+                        update_cfs_shares(group_cfs_rq(se));
+                raw_spin_unlock_irqrestore(&rq->lock, flags);
         }
 
-        /*
-         * Enable load balance activity on this group, by inserting it back on
-         * each cpu's rq->leaf_cfs_rq_list.
-         */
-        spin_lock_irqsave(&task_group_lock, flags);
-        for_each_possible_cpu(i)
-                register_fair_sched_group(tg, i);
-        list_add_rcu(&tg->siblings, &tg->parent->children);
-        spin_unlock_irqrestore(&task_group_lock, flags);
 done:
         mutex_unlock(&shares_mutex);
         return 0;
@@ -8624,7 +8874,7 @@ static int tg_set_bandwidth(struct task_group *tg,
                 raw_spin_unlock(&rt_rq->rt_runtime_lock);
         }
         raw_spin_unlock_irq(&tg->rt_bandwidth.rt_runtime_lock);
- unlock:
+unlock:
         read_unlock(&tasklist_lock);
         mutex_unlock(&rt_constraints_mutex);
 
@@ -8788,7 +9038,7 @@ cpu_cgroup_create(struct cgroup_subsys *ss, struct cgroup *cgrp)
 
         if (!cgrp->parent) {
                 /* This is early initialization for the top cgroup */
-                return &init_task_group.css;
+                return &root_task_group.css;
         }
 
         parent = cgroup_tg(cgrp->parent);
@@ -8821,56 +9071,39 @@ cpu_cgroup_can_attach_task(struct cgroup *cgrp, struct task_struct *tsk)
         return 0;
 }
 
-static int
-cpu_cgroup_can_attach(struct cgroup_subsys *ss, struct cgroup *cgrp,
-                      struct task_struct *tsk, bool threadgroup)
+static void
+cpu_cgroup_attach_task(struct cgroup *cgrp, struct task_struct *tsk)
 {
-        int retval = cpu_cgroup_can_attach_task(cgrp, tsk);
-        if (retval)
-                return retval;
-        if (threadgroup) {
-                struct task_struct *c;
-                rcu_read_lock();
-                list_for_each_entry_rcu(c, &tsk->thread_group, thread_group) {
-                        retval = cpu_cgroup_can_attach_task(cgrp, c);
-                        if (retval) {
-                                rcu_read_unlock();
-                                return retval;
-                        }
-                }
-                rcu_read_unlock();
-        }
-        return 0;
+        sched_move_task(tsk);
 }
 
 static void
-cpu_cgroup_attach(struct cgroup_subsys *ss, struct cgroup *cgrp,
-                  struct cgroup *old_cont, struct task_struct *tsk,
-                  bool threadgroup)
+cpu_cgroup_exit(struct cgroup_subsys *ss, struct cgroup *cgrp,
+                struct cgroup *old_cgrp, struct task_struct *task)
 {
-        sched_move_task(tsk);
-        if (threadgroup) {
-                struct task_struct *c;
-                rcu_read_lock();
-                list_for_each_entry_rcu(c, &tsk->thread_group, thread_group) {
-                        sched_move_task(c);
-                }
-                rcu_read_unlock();
-        }
+        /*
+         * cgroup_exit() is called in the copy_process() failure path.
+         * Ignore this case since the task hasn't ran yet, this avoids
+         * trying to poke a half freed task state from generic code.
+         */
+        if (!(task->flags & PF_EXITING))
+                return;
+
+        sched_move_task(task);
 }
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 static int cpu_shares_write_u64(struct cgroup *cgrp, struct cftype *cftype,
                                 u64 shareval)
 {
-        return sched_group_set_shares(cgroup_tg(cgrp), shareval);
+        return sched_group_set_shares(cgroup_tg(cgrp), scale_load(shareval));
 }
 
 static u64 cpu_shares_read_u64(struct cgroup *cgrp, struct cftype *cft)
 {
         struct task_group *tg = cgroup_tg(cgrp);
 
-        return (u64) tg->shares;
+        return (u64) scale_load_down(tg->shares);
 }
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
@@ -8929,8 +9162,9 @@ struct cgroup_subsys cpu_cgroup_subsys = {
         .name           = "cpu",
         .create         = cpu_cgroup_create,
         .destroy        = cpu_cgroup_destroy,
-        .can_attach     = cpu_cgroup_can_attach,
-        .attach         = cpu_cgroup_attach,
+        .can_attach_task = cpu_cgroup_can_attach_task,
+        .attach_task    = cpu_cgroup_attach_task,
+        .exit           = cpu_cgroup_exit,
         .populate       = cpu_cgroup_populate,
         .subsys_id      = cpu_cgroup_subsys_id,
         .early_init     = 1,
@@ -9215,72 +9449,3 @@ struct cgroup_subsys cpuacct_subsys = {
 };
 #endif  /* CONFIG_CGROUP_CPUACCT */
 
-#ifndef CONFIG_SMP
-
-void synchronize_sched_expedited(void)
-{
-        barrier();
-}
-EXPORT_SYMBOL_GPL(synchronize_sched_expedited);
-
-#else /* #ifndef CONFIG_SMP */
-
-static atomic_t synchronize_sched_expedited_count = ATOMIC_INIT(0);
-
-static int synchronize_sched_expedited_cpu_stop(void *data)
-{
-        /*
-         * There must be a full memory barrier on each affected CPU
-         * between the time that try_stop_cpus() is called and the
-         * time that it returns.
-         *
-         * In the current initial implementation of cpu_stop, the
-         * above condition is already met when the control reaches
-         * this point and the following smp_mb() is not strictly
-         * necessary.  Do smp_mb() anyway for documentation and
-         * robustness against future implementation changes.
-         */
-        smp_mb(); /* See above comment block. */
-        return 0;
-}
-
-/*
- * Wait for an rcu-sched grace period to elapse, but use "big hammer"
- * approach to force grace period to end quickly.  This consumes
- * significant time on all CPUs, and is thus not recommended for
- * any sort of common-case code.
- *
- * Note that it is illegal to call this function while holding any
- * lock that is acquired by a CPU-hotplug notifier.  Failing to
- * observe this restriction will result in deadlock.
- */
-void synchronize_sched_expedited(void)
-{
-        int snap, trycount = 0;
-
-        smp_mb();  /* ensure prior mod happens before capturing snap. */
-        snap = atomic_read(&synchronize_sched_expedited_count) + 1;
-        get_online_cpus();
-        while (try_stop_cpus(cpu_online_mask,
-                             synchronize_sched_expedited_cpu_stop,
-                             NULL) == -EAGAIN) {
-                put_online_cpus();
-                if (trycount++ < 10)
-                        udelay(trycount * num_online_cpus());
-                else {
-                        synchronize_sched();
-                        return;
-                }
-                if (atomic_read(&synchronize_sched_expedited_count) - snap > 0) {
-                        smp_mb(); /* ensure test happens before caller kfree */
-                        return;
-                }
-                get_online_cpus();
-        }
-        atomic_inc(&synchronize_sched_expedited_count);
-        smp_mb__after_atomic_inc(); /* ensure post-GP actions seen after GP. */
-        put_online_cpus();
-}
-EXPORT_SYMBOL_GPL(synchronize_sched_expedited);
-
-#endif /* #else #ifndef CONFIG_SMP */