kfifo: move struct kfifo in place
[linux-2.6.git] / kernel / sched_fair.c
index 9ffb2b2..42ac3c9 100644 (file)
  */
 
 #include <linux/latencytop.h>
+#include <linux/sched.h>
 
 /*
  * Targeted preemption latency for CPU-bound tasks:
- * (default: 20ms * (1 + ilog(ncpus)), units: nanoseconds)
+ * (default: 5ms * (1 + ilog(ncpus)), units: nanoseconds)
  *
  * NOTE: this latency value is not the same as the concept of
  * 'timeslice length' - timeslices in CFS are of variable length
  * (to see the precise effective timeslice length of your workload,
  *  run vmstat and monitor the context-switches (cs) field)
  */
-unsigned int sysctl_sched_latency = 20000000ULL;
+unsigned int sysctl_sched_latency = 5000000ULL;
+unsigned int normalized_sysctl_sched_latency = 5000000ULL;
+
+/*
+ * The initial- and re-scaling of tunables is configurable
+ * (default SCHED_TUNABLESCALING_LOG = *(1+ilog(ncpus))
+ *
+ * Options are:
+ * SCHED_TUNABLESCALING_NONE - unscaled, always *1
+ * SCHED_TUNABLESCALING_LOG - scaled logarithmical, *1+ilog(ncpus)
+ * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
+ */
+enum sched_tunable_scaling sysctl_sched_tunable_scaling
+       = SCHED_TUNABLESCALING_LOG;
 
 /*
  * Minimal preemption granularity for CPU-bound tasks:
- * (default: 4 msec * (1 + ilog(ncpus)), units: nanoseconds)
+ * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
  */
-unsigned int sysctl_sched_min_granularity = 4000000ULL;
+unsigned int sysctl_sched_min_granularity = 1000000ULL;
+unsigned int normalized_sysctl_sched_min_granularity = 1000000ULL;
 
 /*
  * is kept at sysctl_sched_latency / sysctl_sched_min_granularity
@@ -48,10 +63,10 @@ unsigned int sysctl_sched_min_granularity = 4000000ULL;
 static unsigned int sched_nr_latency = 5;
 
 /*
- * After fork, child runs first. (default) If set to 0 then
+ * After fork, child runs first. If set to 0 (default) then
  * parent will (try to) run first.
  */
-const_debug unsigned int sysctl_sched_child_runs_first = 1;
+unsigned int sysctl_sched_child_runs_first __read_mostly;
 
 /*
  * sys_sched_yield() compat mode
@@ -63,13 +78,14 @@ unsigned int __read_mostly sysctl_sched_compat_yield;
 
 /*
  * SCHED_OTHER wake-up granularity.
- * (default: 5 msec * (1 + ilog(ncpus)), units: nanoseconds)
+ * (default: 1 msec * (1 + ilog(ncpus)), units: nanoseconds)
  *
  * This option delays the preemption effects of decoupled workloads
  * and reduces their over-scheduling. Synchronous workloads will still
  * have immediate wakeup/sleep latencies.
  */
-unsigned int sysctl_sched_wakeup_granularity = 5000000UL;
+unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
+unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
 
 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
 
@@ -79,11 +95,6 @@ static const struct sched_class fair_sched_class;
  * CFS operations on generic schedulable entities:
  */
 
-static inline struct task_struct *task_of(struct sched_entity *se)
-{
-       return container_of(se, struct task_struct, se);
-}
-
 #ifdef CONFIG_FAIR_GROUP_SCHED
 
 /* cpu runqueue to which this cfs_rq is attached */
@@ -95,6 +106,14 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
 /* An entity is a task if it doesn't "own" a runqueue */
 #define entity_is_task(se)     (!se->my_q)
 
+static inline struct task_struct *task_of(struct sched_entity *se)
+{
+#ifdef CONFIG_SCHED_DEBUG
+       WARN_ON_ONCE(!entity_is_task(se));
+#endif
+       return container_of(se, struct task_struct, se);
+}
+
 /* Walk up scheduling entities hierarchy */
 #define for_each_sched_entity(se) \
                for (; se; se = se->parent)
@@ -186,7 +205,12 @@ find_matching_se(struct sched_entity **se, struct sched_entity **pse)
        }
 }
 
-#else  /* CONFIG_FAIR_GROUP_SCHED */
+#else  /* !CONFIG_FAIR_GROUP_SCHED */
+
+static inline struct task_struct *task_of(struct sched_entity *se)
+{
+       return container_of(se, struct task_struct, se);
+}
 
 static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
 {
@@ -375,11 +399,12 @@ static struct sched_entity *__pick_last_entity(struct cfs_rq *cfs_rq)
  */
 
 #ifdef CONFIG_SCHED_DEBUG
-int sched_nr_latency_handler(struct ctl_table *table, int write,
-               struct file *filp, void __user *buffer, size_t *lenp,
+int sched_proc_update_handler(struct ctl_table *table, int write,
+               void __user *buffer, size_t *lenp,
                loff_t *ppos)
 {
-       int ret = proc_dointvec_minmax(table, write, filp, buffer, lenp, ppos);
+       int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
+       int factor = get_update_sysctl_factor();
 
        if (ret || !write)
                return ret;
@@ -387,6 +412,14 @@ int sched_nr_latency_handler(struct ctl_table *table, int write,
        sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
                                        sysctl_sched_min_granularity);
 
+#define WRT_SYSCTL(name) \
+       (normalized_sysctl_##name = sysctl_##name / (factor))
+       WRT_SYSCTL(sched_min_granularity);
+       WRT_SYSCTL(sched_latency);
+       WRT_SYSCTL(sched_wakeup_granularity);
+       WRT_SYSCTL(sched_shares_ratelimit);
+#undef WRT_SYSCTL
+
        return 0;
 }
 #endif
@@ -477,6 +510,7 @@ __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
        curr->sum_exec_runtime += delta_exec;
        schedstat_add(cfs_rq, exec_clock, delta_exec);
        delta_exec_weighted = calc_delta_fair(delta_exec, curr);
+
        curr->vruntime += delta_exec_weighted;
        update_min_vruntime(cfs_rq);
 }
@@ -505,6 +539,7 @@ static void update_curr(struct cfs_rq *cfs_rq)
        if (entity_is_task(curr)) {
                struct task_struct *curtask = task_of(curr);
 
+               trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
                cpuacct_charge(curtask, delta_exec);
                account_group_exec_runtime(curtask, delta_exec);
        }
@@ -537,6 +572,12 @@ update_stats_wait_end(struct cfs_rq *cfs_rq, struct sched_entity *se)
        schedstat_set(se->wait_count, se->wait_count + 1);
        schedstat_set(se->wait_sum, se->wait_sum +
                        rq_of(cfs_rq)->clock - se->wait_start);
+#ifdef CONFIG_SCHEDSTATS
+       if (entity_is_task(se)) {
+               trace_sched_stat_wait(task_of(se),
+                       rq_of(cfs_rq)->clock - se->wait_start);
+       }
+#endif
        schedstat_set(se->wait_start, 0);
 }
 
@@ -611,9 +652,13 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
 static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 #ifdef CONFIG_SCHEDSTATS
+       struct task_struct *tsk = NULL;
+
+       if (entity_is_task(se))
+               tsk = task_of(se);
+
        if (se->sleep_start) {
                u64 delta = rq_of(cfs_rq)->clock - se->sleep_start;
-               struct task_struct *tsk = task_of(se);
 
                if ((s64)delta < 0)
                        delta = 0;
@@ -624,11 +669,13 @@ static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
                se->sleep_start = 0;
                se->sum_sleep_runtime += delta;
 
-               account_scheduler_latency(tsk, delta >> 10, 1);
+               if (tsk) {
+                       account_scheduler_latency(tsk, delta >> 10, 1);
+                       trace_sched_stat_sleep(tsk, delta);
+               }
        }
        if (se->block_start) {
                u64 delta = rq_of(cfs_rq)->clock - se->block_start;
-               struct task_struct *tsk = task_of(se);
 
                if ((s64)delta < 0)
                        delta = 0;
@@ -639,17 +686,25 @@ static void enqueue_sleeper(struct cfs_rq *cfs_rq, struct sched_entity *se)
                se->block_start = 0;
                se->sum_sleep_runtime += delta;
 
-               /*
-                * Blocking time is in units of nanosecs, so shift by 20 to
-                * get a milliseconds-range estimation of the amount of
-                * time that the task spent sleeping:
-                */
-               if (unlikely(prof_on == SLEEP_PROFILING)) {
+               if (tsk) {
+                       if (tsk->in_iowait) {
+                               se->iowait_sum += delta;
+                               se->iowait_count++;
+                               trace_sched_stat_iowait(tsk, delta);
+                       }
 
-                       profile_hits(SLEEP_PROFILING, (void *)get_wchan(tsk),
-                                    delta >> 20);
+                       /*
+                        * Blocking time is in units of nanosecs, so shift by
+                        * 20 to get a milliseconds-range estimation of the
+                        * amount of time that the task spent sleeping:
+                        */
+                       if (unlikely(prof_on == SLEEP_PROFILING)) {
+                               profile_hits(SLEEP_PROFILING,
+                                               (void *)get_wchan(tsk),
+                                               delta >> 20);
+                       }
+                       account_scheduler_latency(tsk, delta >> 10, 0);
                }
-               account_scheduler_latency(tsk, delta >> 10, 0);
        }
 #endif
 }
@@ -681,42 +736,56 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
        if (initial && sched_feat(START_DEBIT))
                vruntime += sched_vslice(cfs_rq, se);
 
-       if (!initial) {
-               /* sleeps upto a single latency don't count. */
-               if (sched_feat(NEW_FAIR_SLEEPERS)) {
-                       unsigned long thresh = sysctl_sched_latency;
+       /* sleeps up to a single latency don't count. */
+       if (!initial && sched_feat(FAIR_SLEEPERS)) {
+               unsigned long thresh = sysctl_sched_latency;
 
-                       /*
-                        * Convert the sleeper threshold into virtual time.
-                        * SCHED_IDLE is a special sub-class.  We care about
-                        * fairness only relative to other SCHED_IDLE tasks,
-                        * all of which have the same weight.
-                        */
-                       if (sched_feat(NORMALIZED_SLEEPER) &&
-                                       (!entity_is_task(se) ||
-                                        task_of(se)->policy != SCHED_IDLE))
-                               thresh = calc_delta_fair(thresh, se);
+               /*
+                * Convert the sleeper threshold into virtual time.
+                * SCHED_IDLE is a special sub-class.  We care about
+                * fairness only relative to other SCHED_IDLE tasks,
+                * all of which have the same weight.
+                */
+               if (sched_feat(NORMALIZED_SLEEPER) && (!entity_is_task(se) ||
+                                task_of(se)->policy != SCHED_IDLE))
+                       thresh = calc_delta_fair(thresh, se);
 
-                       vruntime -= thresh;
-               }
+               /*
+                * Halve their sleep time's effect, to allow
+                * for a gentler effect of sleepers:
+                */
+               if (sched_feat(GENTLE_FAIR_SLEEPERS))
+                       thresh >>= 1;
 
-               /* ensure we never gain time by being placed backwards. */
-               vruntime = max_vruntime(se->vruntime, vruntime);
+               vruntime -= thresh;
        }
 
+       /* ensure we never gain time by being placed backwards. */
+       vruntime = max_vruntime(se->vruntime, vruntime);
+
        se->vruntime = vruntime;
 }
 
+#define ENQUEUE_WAKEUP 1
+#define ENQUEUE_MIGRATE 2
+
 static void
-enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
+enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
        /*
+        * Update the normalized vruntime before updating min_vruntime
+        * through callig update_curr().
+        */
+       if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
+               se->vruntime += cfs_rq->min_vruntime;
+
+       /*
         * Update run-time statistics of the 'current'.
         */
        update_curr(cfs_rq);
        account_entity_enqueue(cfs_rq, se);
 
-       if (wakeup) {
+       if (flags & ENQUEUE_WAKEUP) {
                place_entity(cfs_rq, se, 0);
                enqueue_sleeper(cfs_rq, se);
        }
@@ -729,10 +798,10 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
 
 static void __clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-       if (cfs_rq->last == se)
+       if (!se || cfs_rq->last == se)
                cfs_rq->last = NULL;
 
-       if (cfs_rq->next == se)
+       if (!se || cfs_rq->next == se)
                cfs_rq->next = NULL;
 }
 
@@ -770,6 +839,14 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
                __dequeue_entity(cfs_rq, se);
        account_entity_dequeue(cfs_rq, se);
        update_min_vruntime(cfs_rq);
+
+       /*
+        * Normalize the entity after updating the min_vruntime because the
+        * update can refer to the ->curr item and we need to reflect this
+        * movement in our normalized position.
+        */
+       if (!sleep)
+               se->vruntime -= cfs_rq->min_vruntime;
 }
 
 /*
@@ -789,6 +866,26 @@ check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
                 * re-elected due to buddy favours.
                 */
                clear_buddies(cfs_rq, curr);
+               return;
+       }
+
+       /*
+        * Ensure that a task that missed wakeup preemption by a
+        * narrow margin doesn't have to wait for a full slice.
+        * This also mitigates buddy induced latencies under load.
+        */
+       if (!sched_feat(WAKEUP_PREEMPT))
+               return;
+
+       if (delta_exec < sysctl_sched_min_granularity)
+               return;
+
+       if (cfs_rq->nr_running > 1) {
+               struct sched_entity *se = __pick_next_entity(cfs_rq);
+               s64 delta = curr->vruntime - se->vruntime;
+
+               if (delta > ideal_runtime)
+                       resched_task(rq_of(cfs_rq)->curr);
        }
 }
 
@@ -828,12 +925,18 @@ wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se);
 static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
 {
        struct sched_entity *se = __pick_next_entity(cfs_rq);
+       struct sched_entity *left = se;
 
-       if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)
-               return cfs_rq->next;
+       if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
+               se = cfs_rq->next;
 
-       if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)
-               return cfs_rq->last;
+       /*
+        * Prefer last buddy, try to return the CPU to a preempted task.
+        */
+       if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
+               se = cfs_rq->last;
+
+       clear_buddies(cfs_rq, se);
 
        return se;
 }
@@ -954,13 +1057,19 @@ static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
 {
        struct cfs_rq *cfs_rq;
        struct sched_entity *se = &p->se;
+       int flags = 0;
+
+       if (wakeup)
+               flags |= ENQUEUE_WAKEUP;
+       if (p->state == TASK_WAKING)
+               flags |= ENQUEUE_MIGRATE;
 
        for_each_sched_entity(se) {
                if (se->on_rq)
                        break;
                cfs_rq = cfs_rq_of(se);
-               enqueue_entity(cfs_rq, se, wakeup);
-               wakeup = 1;
+               enqueue_entity(cfs_rq, se, flags);
+               flags = ENQUEUE_WAKEUP;
        }
 
        hrtick_update(rq);
@@ -1034,80 +1143,15 @@ static void yield_task_fair(struct rq *rq)
        se->vruntime = rightmost->vruntime + 1;
 }
 
-/*
- * wake_idle() will wake a task on an idle cpu if task->cpu is
- * not idle and an idle cpu is available.  The span of cpus to
- * search starts with cpus closest then further out as needed,
- * so we always favor a closer, idle cpu.
- * Domains may include CPUs that are not usable for migration,
- * hence we need to mask them out (cpu_active_mask)
- *
- * Returns the CPU we should wake onto.
- */
-#if defined(ARCH_HAS_SCHED_WAKE_IDLE)
-static int wake_idle(int cpu, struct task_struct *p)
-{
-       struct sched_domain *sd;
-       int i;
-       unsigned int chosen_wakeup_cpu;
-       int this_cpu;
-
-       /*
-        * At POWERSAVINGS_BALANCE_WAKEUP level, if both this_cpu and prev_cpu
-        * are idle and this is not a kernel thread and this task's affinity
-        * allows it to be moved to preferred cpu, then just move!
-        */
-
-       this_cpu = smp_processor_id();
-       chosen_wakeup_cpu =
-               cpu_rq(this_cpu)->rd->sched_mc_preferred_wakeup_cpu;
-
-       if (sched_mc_power_savings >= POWERSAVINGS_BALANCE_WAKEUP &&
-               idle_cpu(cpu) && idle_cpu(this_cpu) &&
-               p->mm && !(p->flags & PF_KTHREAD) &&
-               cpu_isset(chosen_wakeup_cpu, p->cpus_allowed))
-               return chosen_wakeup_cpu;
-
-       /*
-        * If it is idle, then it is the best cpu to run this task.
-        *
-        * This cpu is also the best, if it has more than one task already.
-        * Siblings must be also busy(in most cases) as they didn't already
-        * pickup the extra load from this cpu and hence we need not check
-        * sibling runqueue info. This will avoid the checks and cache miss
-        * penalities associated with that.
-        */
-       if (idle_cpu(cpu) || cpu_rq(cpu)->cfs.nr_running > 1)
-               return cpu;
+#ifdef CONFIG_SMP
 
-       for_each_domain(cpu, sd) {
-               if ((sd->flags & SD_WAKE_IDLE)
-                   || ((sd->flags & SD_WAKE_IDLE_FAR)
-                       && !task_hot(p, task_rq(p)->clock, sd))) {
-                       for_each_cpu_and(i, sched_domain_span(sd),
-                                        &p->cpus_allowed) {
-                               if (cpu_active(i) && idle_cpu(i)) {
-                                       if (i != task_cpu(p)) {
-                                               schedstat_inc(p,
-                                                      se.nr_wakeups_idle);
-                                       }
-                                       return i;
-                               }
-                       }
-               } else {
-                       break;
-               }
-       }
-       return cpu;
-}
-#else /* !ARCH_HAS_SCHED_WAKE_IDLE*/
-static inline int wake_idle(int cpu, struct task_struct *p)
+static void task_waking_fair(struct rq *rq, struct task_struct *p)
 {
-       return cpu;
-}
-#endif
+       struct sched_entity *se = &p->se;
+       struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
-#ifdef CONFIG_SMP
+       se->vruntime -= cfs_rq->min_vruntime;
+}
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 /*
@@ -1193,25 +1237,34 @@ static inline unsigned long effective_load(struct task_group *tg, int cpu,
 
 #endif
 
-static int
-wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
-           struct task_struct *p, int prev_cpu, int this_cpu, int sync,
-           int idx, unsigned long load, unsigned long this_load,
-           unsigned int imbalance)
+static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 {
-       struct task_struct *curr = this_rq->curr;
-       struct task_group *tg;
-       unsigned long tl = this_load;
+       struct task_struct *curr = current;
+       unsigned long this_load, load;
+       int idx, this_cpu, prev_cpu;
        unsigned long tl_per_task;
+       unsigned int imbalance;
+       struct task_group *tg;
        unsigned long weight;
        int balanced;
 
-       if (!(this_sd->flags & SD_WAKE_AFFINE) || !sched_feat(AFFINE_WAKEUPS))
-               return 0;
+       idx       = sd->wake_idx;
+       this_cpu  = smp_processor_id();
+       prev_cpu  = task_cpu(p);
+       load      = source_load(prev_cpu, idx);
+       this_load = target_load(this_cpu, idx);
 
-       if (sync && (curr->se.avg_overlap > sysctl_sched_migration_cost ||
-                       p->se.avg_overlap > sysctl_sched_migration_cost))
-               sync = 0;
+       if (sync) {
+              if (sched_feat(SYNC_LESS) &&
+                  (curr->se.avg_overlap > sysctl_sched_migration_cost ||
+                   p->se.avg_overlap > sysctl_sched_migration_cost))
+                      sync = 0;
+       } else {
+               if (sched_feat(SYNC_MORE) &&
+                   (curr->se.avg_overlap < sysctl_sched_migration_cost &&
+                    p->se.avg_overlap < sysctl_sched_migration_cost))
+                       sync = 1;
+       }
 
        /*
         * If sync wakeup then subtract the (maximum possible)
@@ -1222,14 +1275,26 @@ wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
                tg = task_group(current);
                weight = current->se.load.weight;
 
-               tl += effective_load(tg, this_cpu, -weight, -weight);
+               this_load += effective_load(tg, this_cpu, -weight, -weight);
                load += effective_load(tg, prev_cpu, 0, -weight);
        }
 
        tg = task_group(p);
        weight = p->se.load.weight;
 
-       balanced = 100*(tl + effective_load(tg, this_cpu, weight, weight)) <=
+       imbalance = 100 + (sd->imbalance_pct - 100) / 2;
+
+       /*
+        * In low-load situations, where prev_cpu is idle and this_cpu is idle
+        * due to the sync cause above having dropped this_load to 0, we'll
+        * always have an imbalance, but there's really nothing you can do
+        * about that, so that's good too.
+        *
+        * Otherwise check if either cpus are near enough in load to allow this
+        * task to be woken on this_cpu.
+        */
+       balanced = !this_load ||
+               100*(this_load + effective_load(tg, this_cpu, weight, weight)) <=
                imbalance*(load + effective_load(tg, prev_cpu, 0, weight));
 
        /*
@@ -1243,14 +1308,15 @@ wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
        schedstat_inc(p, se.nr_wakeups_affine_attempts);
        tl_per_task = cpu_avg_load_per_task(this_cpu);
 
-       if (balanced || (tl <= load && tl + target_load(prev_cpu, idx) <=
-                       tl_per_task)) {
+       if (balanced ||
+           (this_load <= load &&
+            this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
                /*
                 * This domain has SD_WAKE_AFFINE and
                 * p is cache cold in this domain, and
                 * there is no bad imbalance.
                 */
-               schedstat_inc(this_sd, ttwu_move_affine);
+               schedstat_inc(sd, ttwu_move_affine);
                schedstat_inc(p, se.nr_wakeups_affine);
 
                return 1;
@@ -1258,67 +1324,269 @@ wake_affine(struct sched_domain *this_sd, struct rq *this_rq,
        return 0;
 }
 
-static int select_task_rq_fair(struct task_struct *p, int sync)
+/*
+ * find_idlest_group finds and returns the least busy CPU group within the
+ * domain.
+ */
+static struct sched_group *
+find_idlest_group(struct sched_domain *sd, struct task_struct *p,
+                 int this_cpu, int load_idx)
 {
-       struct sched_domain *sd, *this_sd = NULL;
-       int prev_cpu, this_cpu, new_cpu;
-       unsigned long load, this_load;
-       struct rq *this_rq;
-       unsigned int imbalance;
-       int idx;
+       struct sched_group *idlest = NULL, *this = NULL, *group = sd->groups;
+       unsigned long min_load = ULONG_MAX, this_load = 0;
+       int imbalance = 100 + (sd->imbalance_pct-100)/2;
+
+       do {
+               unsigned long load, avg_load;
+               int local_group;
+               int i;
+
+               /* Skip over this group if it has no CPUs allowed */
+               if (!cpumask_intersects(sched_group_cpus(group),
+                                       &p->cpus_allowed))
+                       continue;
+
+               local_group = cpumask_test_cpu(this_cpu,
+                                              sched_group_cpus(group));
+
+               /* Tally up the load of all CPUs in the group */
+               avg_load = 0;
 
-       prev_cpu        = task_cpu(p);
-       this_cpu        = smp_processor_id();
-       this_rq         = cpu_rq(this_cpu);
-       new_cpu         = prev_cpu;
+               for_each_cpu(i, sched_group_cpus(group)) {
+                       /* Bias balancing toward cpus of our domain */
+                       if (local_group)
+                               load = source_load(i, load_idx);
+                       else
+                               load = target_load(i, load_idx);
+
+                       avg_load += load;
+               }
+
+               /* Adjust by relative CPU power of the group */
+               avg_load = (avg_load * SCHED_LOAD_SCALE) / group->cpu_power;
+
+               if (local_group) {
+                       this_load = avg_load;
+                       this = group;
+               } else if (avg_load < min_load) {
+                       min_load = avg_load;
+                       idlest = group;
+               }
+       } while (group = group->next, group != sd->groups);
+
+       if (!idlest || 100*this_load < imbalance*min_load)
+               return NULL;
+       return idlest;
+}
+
+/*
+ * find_idlest_cpu - find the idlest cpu among the cpus in group.
+ */
+static int
+find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
+{
+       unsigned long load, min_load = ULONG_MAX;
+       int idlest = -1;
+       int i;
+
+       /* Traverse only the allowed CPUs */
+       for_each_cpu_and(i, sched_group_cpus(group), &p->cpus_allowed) {
+               load = weighted_cpuload(i);
+
+               if (load < min_load || (load == min_load && i == this_cpu)) {
+                       min_load = load;
+                       idlest = i;
+               }
+       }
+
+       return idlest;
+}
+
+/*
+ * Try and locate an idle CPU in the sched_domain.
+ */
+static int
+select_idle_sibling(struct task_struct *p, struct sched_domain *sd, int target)
+{
+       int cpu = smp_processor_id();
+       int prev_cpu = task_cpu(p);
+       int i;
+
+       /*
+        * If this domain spans both cpu and prev_cpu (see the SD_WAKE_AFFINE
+        * test in select_task_rq_fair) and the prev_cpu is idle then that's
+        * always a better target than the current cpu.
+        */
+       if (target == cpu && !cpu_rq(prev_cpu)->cfs.nr_running)
+               return prev_cpu;
 
-       if (prev_cpu == this_cpu)
-               goto out;
        /*
-        * 'this_sd' is the first domain that both
-        * this_cpu and prev_cpu are present in:
+        * Otherwise, iterate the domain and find an elegible idle cpu.
         */
-       for_each_domain(this_cpu, sd) {
-               if (cpumask_test_cpu(prev_cpu, sched_domain_span(sd))) {
-                       this_sd = sd;
+       for_each_cpu_and(i, sched_domain_span(sd), &p->cpus_allowed) {
+               if (!cpu_rq(i)->cfs.nr_running) {
+                       target = i;
                        break;
                }
        }
 
-       if (unlikely(!cpumask_test_cpu(this_cpu, &p->cpus_allowed)))
-               goto out;
+       return target;
+}
 
-       /*
-        * Check for affine wakeup and passive balancing possibilities.
-        */
-       if (!this_sd)
-               goto out;
+/*
+ * sched_balance_self: balance the current task (running on cpu) in domains
+ * that have the 'flag' flag set. In practice, this is SD_BALANCE_FORK and
+ * SD_BALANCE_EXEC.
+ *
+ * Balance, ie. select the least loaded group.
+ *
+ * Returns the target CPU number, or the same CPU if no balancing is needed.
+ *
+ * preempt must be disabled.
+ */
+static int select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)
+{
+       struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
+       int cpu = smp_processor_id();
+       int prev_cpu = task_cpu(p);
+       int new_cpu = cpu;
+       int want_affine = 0;
+       int want_sd = 1;
+       int sync = wake_flags & WF_SYNC;
+
+       if (sd_flag & SD_BALANCE_WAKE) {
+               if (sched_feat(AFFINE_WAKEUPS) &&
+                   cpumask_test_cpu(cpu, &p->cpus_allowed))
+                       want_affine = 1;
+               new_cpu = prev_cpu;
+       }
 
-       idx = this_sd->wake_idx;
+       for_each_domain(cpu, tmp) {
+               if (!(tmp->flags & SD_LOAD_BALANCE))
+                       continue;
 
-       imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
+               /*
+                * If power savings logic is enabled for a domain, see if we
+                * are not overloaded, if so, don't balance wider.
+                */
+               if (tmp->flags & (SD_POWERSAVINGS_BALANCE|SD_PREFER_LOCAL)) {
+                       unsigned long power = 0;
+                       unsigned long nr_running = 0;
+                       unsigned long capacity;
+                       int i;
+
+                       for_each_cpu(i, sched_domain_span(tmp)) {
+                               power += power_of(i);
+                               nr_running += cpu_rq(i)->cfs.nr_running;
+                       }
 
-       load = source_load(prev_cpu, idx);
-       this_load = target_load(this_cpu, idx);
+                       capacity = DIV_ROUND_CLOSEST(power, SCHED_LOAD_SCALE);
 
-       if (wake_affine(this_sd, this_rq, p, prev_cpu, this_cpu, sync, idx,
-                                    load, this_load, imbalance))
-               return this_cpu;
+                       if (tmp->flags & SD_POWERSAVINGS_BALANCE)
+                               nr_running /= 2;
 
-       /*
-        * Start passive balancing when half the imbalance_pct
-        * limit is reached.
-        */
-       if (this_sd->flags & SD_WAKE_BALANCE) {
-               if (imbalance*this_load <= 100*load) {
-                       schedstat_inc(this_sd, ttwu_move_balance);
-                       schedstat_inc(p, se.nr_wakeups_passive);
-                       return this_cpu;
+                       if (nr_running < capacity)
+                               want_sd = 0;
+               }
+
+               /*
+                * While iterating the domains looking for a spanning
+                * WAKE_AFFINE domain, adjust the affine target to any idle cpu
+                * in cache sharing domains along the way.
+                */
+               if (want_affine) {
+                       int target = -1;
+
+                       /*
+                        * If both cpu and prev_cpu are part of this domain,
+                        * cpu is a valid SD_WAKE_AFFINE target.
+                        */
+                       if (cpumask_test_cpu(prev_cpu, sched_domain_span(tmp)))
+                               target = cpu;
+
+                       /*
+                        * If there's an idle sibling in this domain, make that
+                        * the wake_affine target instead of the current cpu.
+                        */
+                       if (tmp->flags & SD_PREFER_SIBLING)
+                               target = select_idle_sibling(p, tmp, target);
+
+                       if (target >= 0) {
+                               if (tmp->flags & SD_WAKE_AFFINE) {
+                                       affine_sd = tmp;
+                                       want_affine = 0;
+                               }
+                               cpu = target;
+                       }
+               }
+
+               if (!want_sd && !want_affine)
+                       break;
+
+               if (!(tmp->flags & sd_flag))
+                       continue;
+
+               if (want_sd)
+                       sd = tmp;
+       }
+
+       if (sched_feat(LB_SHARES_UPDATE)) {
+               /*
+                * Pick the largest domain to update shares over
+                */
+               tmp = sd;
+               if (affine_sd && (!tmp ||
+                                 cpumask_weight(sched_domain_span(affine_sd)) >
+                                 cpumask_weight(sched_domain_span(sd))))
+                       tmp = affine_sd;
+
+               if (tmp)
+                       update_shares(tmp);
+       }
+
+       if (affine_sd && wake_affine(affine_sd, p, sync))
+               return cpu;
+
+       while (sd) {
+               int load_idx = sd->forkexec_idx;
+               struct sched_group *group;
+               int weight;
+
+               if (!(sd->flags & sd_flag)) {
+                       sd = sd->child;
+                       continue;
+               }
+
+               if (sd_flag & SD_BALANCE_WAKE)
+                       load_idx = sd->wake_idx;
+
+               group = find_idlest_group(sd, p, cpu, load_idx);
+               if (!group) {
+                       sd = sd->child;
+                       continue;
+               }
+
+               new_cpu = find_idlest_cpu(group, p, cpu);
+               if (new_cpu == -1 || new_cpu == cpu) {
+                       /* Now try balancing at a lower domain level of cpu */
+                       sd = sd->child;
+                       continue;
                }
+
+               /* Now try balancing at a lower domain level of new_cpu */
+               cpu = new_cpu;
+               weight = cpumask_weight(sched_domain_span(sd));
+               sd = NULL;
+               for_each_domain(cpu, tmp) {
+                       if (weight <= cpumask_weight(sched_domain_span(tmp)))
+                               break;
+                       if (tmp->flags & sd_flag)
+                               sd = tmp;
+               }
+               /* while loop will break here if sd == NULL */
        }
 
-out:
-       return wake_idle(new_cpu, p);
+       return new_cpu;
 }
 #endif /* CONFIG_SMP */
 
@@ -1431,18 +1699,16 @@ static void set_next_buddy(struct sched_entity *se)
 /*
  * Preempt the current task with a newly woken task if needed:
  */
-static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
+static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
 {
        struct task_struct *curr = rq->curr;
        struct sched_entity *se = &curr->se, *pse = &p->se;
        struct cfs_rq *cfs_rq = task_cfs_rq(curr);
+       int sync = wake_flags & WF_SYNC;
+       int scale = cfs_rq->nr_running >= sched_nr_latency;
 
-       update_curr(cfs_rq);
-
-       if (unlikely(rt_prio(p->prio))) {
-               resched_task(curr);
-               return;
-       }
+       if (unlikely(rt_prio(p->prio)))
+               goto preempt;
 
        if (unlikely(p->sched_class != &fair_sched_class))
                return;
@@ -1450,18 +1716,8 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
        if (unlikely(se == pse))
                return;
 
-       /*
-        * Only set the backward buddy when the current task is still on the
-        * rq. This can happen when a wakeup gets interleaved with schedule on
-        * the ->pre_schedule() or idle_balance() point, either of which can
-        * drop the rq lock.
-        *
-        * Also, during early boot the idle thread is in the fair class, for
-        * obvious reasons its a bad idea to schedule back to the idle thread.
-        */
-       if (sched_feat(LAST_BUDDY) && likely(se->on_rq && curr != rq->idle))
-               set_last_buddy(se);
-       set_next_buddy(pse);
+       if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK))
+               set_next_buddy(pse);
 
        /*
         * We can come here with TIF_NEED_RESCHED already set from new task
@@ -1478,27 +1734,44 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)
                return;
 
        /* Idle tasks are by definition preempted by everybody. */
-       if (unlikely(curr->policy == SCHED_IDLE)) {
-               resched_task(curr);
-               return;
-       }
+       if (unlikely(curr->policy == SCHED_IDLE))
+               goto preempt;
+
+       if (sched_feat(WAKEUP_SYNC) && sync)
+               goto preempt;
+
+       if (sched_feat(WAKEUP_OVERLAP) &&
+                       se->avg_overlap < sysctl_sched_migration_cost &&
+                       pse->avg_overlap < sysctl_sched_migration_cost)
+               goto preempt;
 
        if (!sched_feat(WAKEUP_PREEMPT))
                return;
 
-       if (sched_feat(WAKEUP_OVERLAP) && (sync ||
-                       (se->avg_overlap < sysctl_sched_migration_cost &&
-                        pse->avg_overlap < sysctl_sched_migration_cost))) {
-               resched_task(curr);
-               return;
-       }
-
+       update_curr(cfs_rq);
        find_matching_se(&se, &pse);
-
        BUG_ON(!pse);
-
        if (wakeup_preempt_entity(se, pse) == 1)
-               resched_task(curr);
+               goto preempt;
+
+       return;
+
+preempt:
+       resched_task(curr);
+       /*
+        * Only set the backward buddy when the current task is still
+        * on the rq. This can happen when a wakeup gets interleaved
+        * with schedule on the ->pre_schedule() or idle_balance()
+        * point, either of which can * drop the rq lock.
+        *
+        * Also, during early boot the idle thread is in the fair class,
+        * for obvious reasons its a bad idea to schedule back to it.
+        */
+       if (unlikely(!se->on_rq || curr == rq->idle))
+               return;
+
+       if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
+               set_last_buddy(se);
 }
 
 static struct task_struct *pick_next_task_fair(struct rq *rq)
@@ -1507,16 +1780,11 @@ static struct task_struct *pick_next_task_fair(struct rq *rq)
        struct cfs_rq *cfs_rq = &rq->cfs;
        struct sched_entity *se;
 
-       if (unlikely(!cfs_rq->nr_running))
+       if (!cfs_rq->nr_running)
                return NULL;
 
        do {
                se = pick_next_entity(cfs_rq);
-               /*
-                * If se was a buddy, clear it so that it will have to earn
-                * the favour again.
-                */
-               __clear_buddies(cfs_rq, se);
                set_next_entity(cfs_rq, se);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);
@@ -1683,6 +1951,17 @@ move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest,
 
        return 0;
 }
+
+static void rq_online_fair(struct rq *rq)
+{
+       update_sysctl();
+}
+
+static void rq_offline_fair(struct rq *rq)
+{
+       update_sysctl();
+}
+
 #endif /* CONFIG_SMP */
 
 /*
@@ -1700,26 +1979,30 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
 }
 
 /*
- * Share the fairness runtime between parent and child, thus the
- * total amount of pressure for CPU stays equal - new tasks
- * get a chance to run but frequent forkers are not allowed to
- * monopolize the CPU. Note: the parent runqueue is locked,
- * the child is not running yet.
+ * called on fork with the child task as argument from the parent's context
+ *  - child not yet on the tasklist
+ *  - preemption disabled
  */
-static void task_new_fair(struct rq *rq, struct task_struct *p)
+static void task_fork_fair(struct task_struct *p)
 {
-       struct cfs_rq *cfs_rq = task_cfs_rq(p);
+       struct cfs_rq *cfs_rq = task_cfs_rq(current);
        struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
        int this_cpu = smp_processor_id();
+       struct rq *rq = this_rq();
+       unsigned long flags;
+
+       raw_spin_lock_irqsave(&rq->lock, flags);
 
-       sched_info_queued(p);
+       if (unlikely(task_cpu(p) != this_cpu))
+               __set_task_cpu(p, this_cpu);
 
        update_curr(cfs_rq);
+
+       if (curr)
+               se->vruntime = curr->vruntime;
        place_entity(cfs_rq, se, 1);
 
-       /* 'curr' will be NULL if the child belongs to a different group */
-       if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
-                       curr && entity_before(curr, se)) {
+       if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
                /*
                 * Upon rescheduling, sched_class::put_prev_task() will place
                 * 'current' within the tree based on its new key value.
@@ -1728,7 +2011,9 @@ static void task_new_fair(struct rq *rq, struct task_struct *p)
                resched_task(rq->curr);
        }
 
-       enqueue_task_fair(rq, p, 0);
+       se->vruntime -= cfs_rq->min_vruntime;
+
+       raw_spin_unlock_irqrestore(&rq->lock, flags);
 }
 
 /*
@@ -1781,15 +2066,31 @@ static void set_curr_task_fair(struct rq *rq)
 }
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
-static void moved_group_fair(struct task_struct *p)
+static void moved_group_fair(struct task_struct *p, int on_rq)
 {
        struct cfs_rq *cfs_rq = task_cfs_rq(p);
 
        update_curr(cfs_rq);
-       place_entity(cfs_rq, &p->se, 1);
+       if (!on_rq)
+               place_entity(cfs_rq, &p->se, 1);
 }
 #endif
 
+unsigned int get_rr_interval_fair(struct rq *rq, struct task_struct *task)
+{
+       struct sched_entity *se = &task->se;
+       unsigned int rr_interval = 0;
+
+       /*
+        * Time slice is 0 for SCHED_OTHER tasks that are on an otherwise
+        * idle runqueue:
+        */
+       if (rq->cfs.load.weight)
+               rr_interval = NS_TO_JIFFIES(sched_slice(&rq->cfs, se));
+
+       return rr_interval;
+}
+
 /*
  * All the scheduling class methods:
  */
@@ -1809,15 +2110,21 @@ static const struct sched_class fair_sched_class = {
 
        .load_balance           = load_balance_fair,
        .move_one_task          = move_one_task_fair,
+       .rq_online              = rq_online_fair,
+       .rq_offline             = rq_offline_fair,
+
+       .task_waking            = task_waking_fair,
 #endif
 
        .set_curr_task          = set_curr_task_fair,
        .task_tick              = task_tick_fair,
-       .task_new               = task_new_fair,
+       .task_fork              = task_fork_fair,
 
        .prio_changed           = prio_changed_fair,
        .switched_to            = switched_to_fair,
 
+       .get_rr_interval        = get_rr_interval_fair,
+
 #ifdef CONFIG_FAIR_GROUP_SCHED
        .moved_group            = moved_group_fair,
 #endif