11 files changed, 690 insertions, 235 deletions
diff --git a/arch/x86/include/asm/mwait.h b/arch/x86/include/asm/mwait.h
index a1410db38a1a..653dfa7662e1 100644
--- a/arch/x86/include/asm/mwait.h
+++ b/arch/x86/include/asm/mwait.h
@@ -30,6 +30,14 @@ static inline void __mwait(unsigned long eax, unsigned long ecx)
                     :: "a" (eax), "c" (ecx));
 }
+static inline void __sti_mwait(unsigned long eax, unsigned long ecx)
+{
+        trace_hardirqs_on();
+        /* "mwait %eax, %ecx;" */
+        asm volatile("sti; .byte 0x0f, 0x01, 0xc9;"
+                     :: "a" (eax), "c" (ecx));
+}
 /*
 * This uses new MONITOR/MWAIT instructions on P4 processors with PNI,
 * which can obviate IPI to trigger checking of need_resched.
diff --git a/arch/x86/kernel/process.c b/arch/x86/kernel/process.c
index 046e2d620bbe..a388bb883128 100644
--- a/arch/x86/kernel/process.c
+++ b/arch/x86/kernel/process.c
@@ -24,6 +24,7 @@
 #include <asm/syscalls.h>
 #include <asm/idle.h>
 #include <asm/uaccess.h>
+#include <asm/mwait.h>
 #include <asm/i387.h>
 #include <asm/fpu-internal.h>
 #include <asm/debugreg.h>
@@ -399,6 +400,53 @@ static void amd_e400_idle(void)
                default_idle();
 }
+/*
+ * Intel Core2 and older machines prefer MWAIT over HALT for C1.
+ * We can't rely on cpuidle installing MWAIT, because it will not load
+ * on systems that support only C1 -- so the boot default must be MWAIT.
+ *
+ * Some AMD machines are the opposite, they depend on using HALT.
+ *
+ * So for default C1, which is used during boot until cpuidle loads,
+ * use MWAIT-C1 on Intel HW that has it, else use HALT.
+ */
+static int prefer_mwait_c1_over_halt(const struct cpuinfo_x86 *c)
+{
+        if (c->x86_vendor != X86_VENDOR_INTEL)
+                return 0;
+        if (!cpu_has(c, X86_FEATURE_MWAIT))
+                return 0;
+        return 1;
+}
+/*
+ * MONITOR/MWAIT with no hints, used for default default C1 state.
+ * This invokes MWAIT with interrutps enabled and no flags,
+ * which is backwards compatible with the original MWAIT implementation.
+ */
+static void mwait_idle(void)
+{
+        if (!current_set_polling_and_test()) {
+                if (this_cpu_has(X86_BUG_CLFLUSH_MONITOR)) {
+                        smp_mb(); /* quirk */
+                        clflush((void *)&current_thread_info()->flags);
+                        smp_mb(); /* quirk */
+                }
+                __monitor((void *)&current_thread_info()->flags, 0, 0);
+                if (!need_resched())
+                        __sti_mwait(0, 0);
+                else
+                        local_irq_enable();
+        } else {
+                local_irq_enable();
+        }
+        __current_clr_polling();
+}
 void select_idle_routine(const struct cpuinfo_x86 *c)
 {
 #ifdef CONFIG_SMP
@@ -412,6 +460,9 @@ void select_idle_routine(const struct cpuinfo_x86 *c)
                /* E400: APIC timer interrupt does not wake up CPU from C1e */
                pr_info("using AMD E400 aware idle routine\n");
                x86_idle = amd_e400_idle;
+        } else if (prefer_mwait_c1_over_halt(c)) {
+                pr_info("using mwait in idle threads\n");
+                x86_idle = mwait_idle;
        } else
                x86_idle = default_idle;
 }
diff --git a/include/linux/irq_work.h b/include/linux/irq_work.h
index bf3fe719c7ce..47b9ebd4a74f 100644
--- a/include/linux/irq_work.h
+++ b/include/linux/irq_work.h
@@ -38,16 +38,17 @@ bool irq_work_queue(struct irq_work *work);
 bool irq_work_queue_on(struct irq_work *work, int cpu);
 #endif
-void irq_work_run(void);
 void irq_work_tick(void);
 void irq_work_sync(struct irq_work *work);
 #ifdef CONFIG_IRQ_WORK
 #include <asm/irq_work.h>
+void irq_work_run(void);
 bool irq_work_needs_cpu(void);
 #else
 static inline bool irq_work_needs_cpu(void) { return false; }
+static inline void irq_work_run(void) { }
 #endif
 #endif /* _LINUX_IRQ_WORK_H */
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 51348f77e431..3f3308824fa4 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1123,15 +1123,28 @@ struct load_weight {
 };
 struct sched_avg {
+        u64 last_runnable_update;
+        s64 decay_count;
+        /*
+         * utilization_avg_contrib describes the amount of time that a
+         * sched_entity is running on a CPU. It is based on running_avg_sum
+         * and is scaled in the range [0..SCHED_LOAD_SCALE].
+         * load_avg_contrib described the amount of time that a sched_entity
+         * is runnable on a rq. It is based on both runnable_avg_sum and the
+         * weight of the task.
+         */
+        unsigned long load_avg_contrib, utilization_avg_contrib;
        /*
         * These sums represent an infinite geometric series and so are bound
         * above by 1024/(1-y).  Thus we only need a u32 to store them for all
         * choices of y < 1-2^(-32)*1024.
+         * running_avg_sum reflects the time that the sched_entity is
+         * effectively running on the CPU.
+         * runnable_avg_sum represents the amount of time a sched_entity is on
+         * a runqueue which includes the running time that is monitored by
+         * running_avg_sum.
         */
-        u32 runnable_avg_sum, runnable_avg_period;
+        u32 runnable_avg_sum, avg_period, running_avg_sum;
-        u64 last_runnable_update;
-        s64 decay_count;
-        unsigned long load_avg_contrib;
 };
 #ifdef CONFIG_SCHEDSTATS
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 3d5f6f6d14c2..261af7bfcb67 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -690,6 +690,23 @@ static inline bool got_nohz_idle_kick(void)
 bool sched_can_stop_tick(void)
 {
        /*
+         * FIFO realtime policy runs the highest priority task. Other runnable
+         * tasks are of a lower priority. The scheduler tick does nothing.
+         */
+        if (current->policy == SCHED_FIFO)
+                return true;
+        /*
+         * Round-robin realtime tasks time slice with other tasks at the same
+         * realtime priority. Is this task the only one at this priority?
+         */
+        if (current->policy == SCHED_RR) {
+                struct sched_rt_entity *rt_se = &current->rt;
+                return rt_se->run_list.prev == rt_se->run_list.next;
+        }
+        /*
         * More than one running task need preemption.
         * nr_running update is assumed to be visible
         * after IPI is sent from wakers.
@@ -5335,36 +5352,13 @@ static int sched_cpu_active(struct notifier_block *nfb,
 static int sched_cpu_inactive(struct notifier_block *nfb,
                                        unsigned long action, void *hcpu)
 {
-        unsigned long flags;
-        long cpu = (long)hcpu;
-        struct dl_bw *dl_b;
        switch (action & ~CPU_TASKS_FROZEN) {
        case CPU_DOWN_PREPARE:
-                set_cpu_active(cpu, false);
+                set_cpu_active((long)hcpu, false);
-                /* explicitly allow suspend */
-                if (!(action & CPU_TASKS_FROZEN)) {
-                        bool overflow;
-                        int cpus;
-                        rcu_read_lock_sched();
-                        dl_b = dl_bw_of(cpu);
-                        raw_spin_lock_irqsave(&dl_b->lock, flags);
-                        cpus = dl_bw_cpus(cpu);
-                        overflow = __dl_overflow(dl_b, cpus, 0, 0);
-                        raw_spin_unlock_irqrestore(&dl_b->lock, flags);
-                        rcu_read_unlock_sched();
-                        if (overflow)
-                                return notifier_from_errno(-EBUSY);
-                }
                return NOTIFY_OK;
+        default:
+                return NOTIFY_DONE;
        }
-        return NOTIFY_DONE;
 }
 static int __init migration_init(void)
@@ -5445,17 +5439,6 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
                        break;
                }
-                /*
-                 * Even though we initialize ->capacity to something semi-sane,
-                 * we leave capacity_orig unset. This allows us to detect if
-                 * domain iteration is still funny without causing /0 traps.
-                 */
-                if (!group->sgc->capacity_orig) {
-                        printk(KERN_CONT "\n");
-                        printk(KERN_ERR "ERROR: domain->cpu_capacity not set\n");
-                        break;
-                }
                if (!cpumask_weight(sched_group_cpus(group))) {
                        printk(KERN_CONT "\n");
                        printk(KERN_ERR "ERROR: empty group\n");
@@ -5939,7 +5922,6 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
                 * die on a /0 trap.
                 */
                sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
-                sg->sgc->capacity_orig = sg->sgc->capacity;
                /*
                 * Make sure the first group of this domain contains the
@@ -6250,6 +6232,7 @@ sd_init(struct sched_domain_topology_level *tl, int cpu)
         */
        if (sd->flags & SD_SHARE_CPUCAPACITY) {
+                sd->flags |= SD_PREFER_SIBLING;
                sd->imbalance_pct = 110;
                sd->smt_gain = 1178; /* ~15% */
@@ -7015,7 +6998,6 @@ static int cpuset_cpu_active(struct notifier_block *nfb, unsigned long action,
                 */
        case CPU_ONLINE:
-        case CPU_DOWN_FAILED:
                cpuset_update_active_cpus(true);
                break;
        default:
@@ -7027,8 +7009,30 @@ static int cpuset_cpu_active(struct notifier_block *nfb, unsigned long action,
 static int cpuset_cpu_inactive(struct notifier_block *nfb, unsigned long action,
                               void *hcpu)
 {
-        switch (action) {
+        unsigned long flags;
+        long cpu = (long)hcpu;
+        struct dl_bw *dl_b;
+        switch (action & ~CPU_TASKS_FROZEN) {
        case CPU_DOWN_PREPARE:
+                /* explicitly allow suspend */
+                if (!(action & CPU_TASKS_FROZEN)) {
+                        bool overflow;
+                        int cpus;
+                        rcu_read_lock_sched();
+                        dl_b = dl_bw_of(cpu);
+                        raw_spin_lock_irqsave(&dl_b->lock, flags);
+                        cpus = dl_bw_cpus(cpu);
+                        overflow = __dl_overflow(dl_b, cpus, 0, 0);
+                        raw_spin_unlock_irqrestore(&dl_b->lock, flags);
+                        rcu_read_unlock_sched();
+                        if (overflow)
+                                return notifier_from_errno(-EBUSY);
+                }
                cpuset_update_active_cpus(false);
                break;
        case CPU_DOWN_PREPARE_FROZEN:
@@ -7173,8 +7177,8 @@ void __init sched_init(void)
                rq->calc_load_active = 0;
                rq->calc_load_update = jiffies + LOAD_FREQ;
                init_cfs_rq(&rq->cfs);
-                init_rt_rq(&rq->rt, rq);
+                init_rt_rq(&rq->rt);
-                init_dl_rq(&rq->dl, rq);
+                init_dl_rq(&rq->dl);
 #ifdef CONFIG_FAIR_GROUP_SCHED
                root_task_group.shares = ROOT_TASK_GROUP_LOAD;
                INIT_LIST_HEAD(&rq->leaf_cfs_rq_list);
@@ -7214,7 +7218,7 @@ void __init sched_init(void)
 #ifdef CONFIG_SMP
                rq->sd = NULL;
                rq->rd = NULL;
-                rq->cpu_capacity = SCHED_CAPACITY_SCALE;
+                rq->cpu_capacity = rq->cpu_capacity_orig = SCHED_CAPACITY_SCALE;
                rq->post_schedule = 0;
                rq->active_balance = 0;
                rq->next_balance = jiffies;
@@ -7813,7 +7817,7 @@ static int sched_rt_global_constraints(void)
 }
 #endif /* CONFIG_RT_GROUP_SCHED */
-static int sched_dl_global_constraints(void)
+static int sched_dl_global_validate(void)
 {
        u64 runtime = global_rt_runtime();
        u64 period = global_rt_period();
@@ -7914,11 +7918,11 @@ int sched_rt_handler(struct ctl_table *table, int write,
                if (ret)
                        goto undo;
-                ret = sched_rt_global_constraints();
+                ret = sched_dl_global_validate();
                if (ret)
                        goto undo;
-                ret = sched_dl_global_constraints();
+                ret = sched_rt_global_constraints();
                if (ret)
                        goto undo;
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 3fa8fa6d9403..5e95145088fd 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -69,7 +69,7 @@ void init_dl_bw(struct dl_bw *dl_b)
        dl_b->total_bw = 0;
 }
-void init_dl_rq(struct dl_rq *dl_rq, struct rq *rq)
+void init_dl_rq(struct dl_rq *dl_rq)
 {
        dl_rq->rb_root = RB_ROOT;
@@ -218,6 +218,52 @@ static inline void set_post_schedule(struct rq *rq)
        rq->post_schedule = has_pushable_dl_tasks(rq);
 }
+static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq);
+static void dl_task_offline_migration(struct rq *rq, struct task_struct *p)
+{
+        struct rq *later_rq = NULL;
+        bool fallback = false;
+        later_rq = find_lock_later_rq(p, rq);
+        if (!later_rq) {
+                int cpu;
+                /*
+                 * If we cannot preempt any rq, fall back to pick any
+                 * online cpu.
+                 */
+                fallback = true;
+                cpu = cpumask_any_and(cpu_active_mask, tsk_cpus_allowed(p));
+                if (cpu >= nr_cpu_ids) {
+                        /*
+                         * Fail to find any suitable cpu.
+                         * The task will never come back!
+                         */
+                        BUG_ON(dl_bandwidth_enabled());
+                        /*
+                         * If admission control is disabled we
+                         * try a little harder to let the task
+                         * run.
+                         */
+                        cpu = cpumask_any(cpu_active_mask);
+                }
+                later_rq = cpu_rq(cpu);
+                double_lock_balance(rq, later_rq);
+        }
+        deactivate_task(rq, p, 0);
+        set_task_cpu(p, later_rq->cpu);
+        activate_task(later_rq, p, ENQUEUE_REPLENISH);
+        if (!fallback)
+                resched_curr(later_rq);
+        double_unlock_balance(rq, later_rq);
+}
 #else
 static inline
@@ -514,7 +560,7 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
        unsigned long flags;
        struct rq *rq;
-        rq = task_rq_lock(current, &flags);
+        rq = task_rq_lock(p, &flags);
        /*
         * We need to take care of several possible races here:
@@ -536,6 +582,17 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
        sched_clock_tick();
        update_rq_clock(rq);
+#ifdef CONFIG_SMP
+        /*
+         * If we find that the rq the task was on is no longer
+         * available, we need to select a new rq.
+         */
+        if (unlikely(!rq->online)) {
+                dl_task_offline_migration(rq, p);
+                goto unlock;
+        }
+#endif
        /*
         * If the throttle happened during sched-out; like:
         *
@@ -569,7 +626,7 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
                push_dl_task(rq);
 #endif
 unlock:
-        task_rq_unlock(rq, current, &flags);
+        task_rq_unlock(rq, p, &flags);
        return HRTIMER_NORESTART;
 }
@@ -914,6 +971,12 @@ static void yield_task_dl(struct rq *rq)
        }
        update_rq_clock(rq);
        update_curr_dl(rq);
+        /*
+         * Tell update_rq_clock() that we've just updated,
+         * so we don't do microscopic update in schedule()
+         * and double the fastpath cost.
+         */
+        rq_clock_skip_update(rq, true);
 }
 #ifdef CONFIG_SMP
@@ -1659,14 +1722,6 @@ static void switched_to_dl(struct rq *rq, struct task_struct *p)
 {
        int check_resched = 1;
-        /*
-         * If p is throttled, don't consider the possibility
-         * of preempting rq->curr, the check will be done right
-         * after its runtime will get replenished.
-         */
-        if (unlikely(p->dl.dl_throttled))
-                return;
        if (task_on_rq_queued(p) && rq->curr != p) {
 #ifdef CONFIG_SMP
                if (p->nr_cpus_allowed > 1 && rq->dl.overloaded &&
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 8baaf858d25c..a245c1fc6f0a 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -71,7 +71,7 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group
        if (!se) {
                struct sched_avg *avg = &cpu_rq(cpu)->avg;
                P(avg->runnable_avg_sum);
-                P(avg->runnable_avg_period);
+                P(avg->avg_period);
                return;
        }
@@ -94,8 +94,10 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group
        P(se->load.weight);
 #ifdef CONFIG_SMP
        P(se->avg.runnable_avg_sum);
-        P(se->avg.runnable_avg_period);
+        P(se->avg.running_avg_sum);
+        P(se->avg.avg_period);
        P(se->avg.load_avg_contrib);
+        P(se->avg.utilization_avg_contrib);
        P(se->avg.decay_count);
 #endif
 #undef PN
@@ -214,6 +216,8 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
                        cfs_rq->runnable_load_avg);
        SEQ_printf(m, "  .%-30s: %ld\n", "blocked_load_avg",
                        cfs_rq->blocked_load_avg);
+        SEQ_printf(m, "  .%-30s: %ld\n", "utilization_load_avg",
+                        cfs_rq->utilization_load_avg);
 #ifdef CONFIG_FAIR_GROUP_SCHED
        SEQ_printf(m, "  .%-30s: %ld\n", "tg_load_contrib",
                        cfs_rq->tg_load_contrib);
@@ -636,8 +640,10 @@ void proc_sched_show_task(struct task_struct *p, struct seq_file *m)
        P(se.load.weight);
 #ifdef CONFIG_SMP
        P(se.avg.runnable_avg_sum);
-        P(se.avg.runnable_avg_period);
+        P(se.avg.running_avg_sum);
+        P(se.avg.avg_period);
        P(se.avg.load_avg_contrib);
+        P(se.avg.utilization_avg_contrib);
        P(se.avg.decay_count);
 #endif
        P(policy);
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 241213be507c..ffeaa4105e48 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -670,6 +670,7 @@ static int select_idle_sibling(struct task_struct *p, int cpu);
 static unsigned long task_h_load(struct task_struct *p);
 static inline void __update_task_entity_contrib(struct sched_entity *se);
+static inline void __update_task_entity_utilization(struct sched_entity *se);
 /* Give new task start runnable values to heavy its load in infant time */
 void init_task_runnable_average(struct task_struct *p)
@@ -677,9 +678,10 @@ void init_task_runnable_average(struct task_struct *p)
        u32 slice;
        slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
-        p->se.avg.runnable_avg_sum = slice;
+        p->se.avg.runnable_avg_sum = p->se.avg.running_avg_sum = slice;
-        p->se.avg.runnable_avg_period = slice;
+        p->se.avg.avg_period = slice;
        __update_task_entity_contrib(&p->se);
+        __update_task_entity_utilization(&p->se);
 }
 #else
 void init_task_runnable_average(struct task_struct *p)
@@ -1196,9 +1198,11 @@ static void task_numa_assign(struct task_numa_env *env,
 static bool load_too_imbalanced(long src_load, long dst_load,
                                struct task_numa_env *env)
 {
-        long imb, old_imb;
-        long orig_src_load, orig_dst_load;
        long src_capacity, dst_capacity;
+        long orig_src_load;
+        long load_a, load_b;
+        long moved_load;
+        long imb;
        /*
         * The load is corrected for the CPU capacity available on each node.
@@ -1211,30 +1215,39 @@ static bool load_too_imbalanced(long src_load, long dst_load,
        dst_capacity = env->dst_stats.compute_capacity;
        /* We care about the slope of the imbalance, not the direction. */
-        if (dst_load < src_load)
+        load_a = dst_load;
-                swap(dst_load, src_load);
+        load_b = src_load;
+        if (load_a < load_b)
+                swap(load_a, load_b);
        /* Is the difference below the threshold? */
-        imb = dst_load * src_capacity * 100 -
+        imb = load_a * src_capacity * 100 -
-              src_load * dst_capacity * env->imbalance_pct;
+                load_b * dst_capacity * env->imbalance_pct;
        if (imb <= 0)
                return false;
        /*
         * The imbalance is above the allowed threshold.
-         * Compare it with the old imbalance.
+         * Allow a move that brings us closer to a balanced situation,
+         * without moving things past the point of balance.
         */
        orig_src_load = env->src_stats.load;
-        orig_dst_load = env->dst_stats.load;
-        if (orig_dst_load < orig_src_load)
+        /*
-                swap(orig_dst_load, orig_src_load);
+         * In a task swap, there will be one load moving from src to dst,
+         * and another moving back. This is the net sum of both moves.
-        old_imb = orig_dst_load * src_capacity * 100 -
+         * A simple task move will always have a positive value.
-                  orig_src_load * dst_capacity * env->imbalance_pct;
+         * Allow the move if it brings the system closer to a balanced
+         * situation, without crossing over the balance point.
+         */
+        moved_load = orig_src_load - src_load;
-        /* Would this change make things worse? */
+        if (moved_load > 0)
-        return (imb > old_imb);
+                /* Moving src -> dst. Did we overshoot balance? */
+                return src_load * dst_capacity < dst_load * src_capacity;
+        else
+                /* Moving dst -> src. Did we overshoot balance? */
+                return dst_load * src_capacity < src_load * dst_capacity;
 }
 /*
@@ -1675,7 +1688,7 @@ static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
                *period = now - p->last_task_numa_placement;
        } else {
                delta = p->se.avg.runnable_avg_sum;
-                *period = p->se.avg.runnable_avg_period;
+                *period = p->se.avg.avg_period;
        }
        p->last_sum_exec_runtime = runtime;
@@ -1765,6 +1778,8 @@ static int preferred_group_nid(struct task_struct *p, int nid)
                        }
                }
                /* Next round, evaluate the nodes within max_group. */
+                if (!max_faults)
+                        break;
                nodes = max_group;
        }
        return nid;
@@ -2503,13 +2518,15 @@ static u32 __compute_runnable_contrib(u64 n)
 *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
 *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
 */
-static __always_inline int __update_entity_runnable_avg(u64 now,
+static __always_inline int __update_entity_runnable_avg(u64 now, int cpu,
                                                        struct sched_avg *sa,
-                                                        int runnable)
+                                                        int runnable,
+                                                        int running)
 {
        u64 delta, periods;
        u32 runnable_contrib;
        int delta_w, decayed = 0;
+        unsigned long scale_freq = arch_scale_freq_capacity(NULL, cpu);
        delta = now - sa->last_runnable_update;
        /*
@@ -2531,7 +2548,7 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
        sa->last_runnable_update = now;
        /* delta_w is the amount already accumulated against our next period */
-        delta_w = sa->runnable_avg_period % 1024;
+        delta_w = sa->avg_period % 1024;
        if (delta + delta_w >= 1024) {
                /* period roll-over */
                decayed = 1;
@@ -2544,7 +2561,10 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
                delta_w = 1024 - delta_w;
                if (runnable)
                        sa->runnable_avg_sum += delta_w;
-                sa->runnable_avg_period += delta_w;
+                if (running)
+                        sa->running_avg_sum += delta_w * scale_freq
+                                >> SCHED_CAPACITY_SHIFT;
+                sa->avg_period += delta_w;
                delta -= delta_w;
@@ -2554,20 +2574,28 @@ static __always_inline int __update_entity_runnable_avg(u64 now,
                sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
                                                  periods + 1);
-                sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
+                sa->running_avg_sum = decay_load(sa->running_avg_sum,
+                                                  periods + 1);
+                sa->avg_period = decay_load(sa->avg_period,
                                                     periods + 1);
                /* Efficiently calculate \sum (1..n_period) 1024*y^i */
                runnable_contrib = __compute_runnable_contrib(periods);
                if (runnable)
                        sa->runnable_avg_sum += runnable_contrib;
-                sa->runnable_avg_period += runnable_contrib;
+                if (running)
+                        sa->running_avg_sum += runnable_contrib * scale_freq
+                                >> SCHED_CAPACITY_SHIFT;
+                sa->avg_period += runnable_contrib;
        }
        /* Remainder of delta accrued against u_0` */
        if (runnable)
                sa->runnable_avg_sum += delta;
-        sa->runnable_avg_period += delta;
+        if (running)
+                sa->running_avg_sum += delta * scale_freq
+                        >> SCHED_CAPACITY_SHIFT;
+        sa->avg_period += delta;
        return decayed;
 }
@@ -2584,6 +2612,8 @@ static inline u64 __synchronize_entity_decay(struct sched_entity *se)
                return 0;
        se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);
+        se->avg.utilization_avg_contrib =
+                decay_load(se->avg.utilization_avg_contrib, decays);
        return decays;
 }
@@ -2619,7 +2649,7 @@ static inline void __update_tg_runnable_avg(struct sched_avg *sa,
        /* The fraction of a cpu used by this cfs_rq */
        contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
-                          sa->runnable_avg_period + 1);
+                          sa->avg_period + 1);
        contrib -= cfs_rq->tg_runnable_contrib;
        if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
@@ -2672,7 +2702,8 @@ static inline void __update_group_entity_contrib(struct sched_entity *se)
 static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
 {
-        __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
+        __update_entity_runnable_avg(rq_clock_task(rq), cpu_of(rq), &rq->avg,
+                        runnable, runnable);
        __update_tg_runnable_avg(&rq->avg, &rq->cfs);
 }
 #else /* CONFIG_FAIR_GROUP_SCHED */
@@ -2690,7 +2721,7 @@ static inline void __update_task_entity_contrib(struct sched_entity *se)
        /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
        contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
-        contrib /= (se->avg.runnable_avg_period + 1);
+        contrib /= (se->avg.avg_period + 1);
        se->avg.load_avg_contrib = scale_load(contrib);
 }
@@ -2709,6 +2740,30 @@ static long __update_entity_load_avg_contrib(struct sched_entity *se)
        return se->avg.load_avg_contrib - old_contrib;
 }
+static inline void __update_task_entity_utilization(struct sched_entity *se)
+{
+        u32 contrib;
+        /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
+        contrib = se->avg.running_avg_sum * scale_load_down(SCHED_LOAD_SCALE);
+        contrib /= (se->avg.avg_period + 1);
+        se->avg.utilization_avg_contrib = scale_load(contrib);
+}
+static long __update_entity_utilization_avg_contrib(struct sched_entity *se)
+{
+        long old_contrib = se->avg.utilization_avg_contrib;
+        if (entity_is_task(se))
+                __update_task_entity_utilization(se);
+        else
+                se->avg.utilization_avg_contrib =
+                                        group_cfs_rq(se)->utilization_load_avg;
+        return se->avg.utilization_avg_contrib - old_contrib;
+}
 static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
                                                 long load_contrib)
 {
@@ -2725,7 +2780,8 @@ static inline void update_entity_load_avg(struct sched_entity *se,
                                          int update_cfs_rq)
 {
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
-        long contrib_delta;
+        long contrib_delta, utilization_delta;
+        int cpu = cpu_of(rq_of(cfs_rq));
        u64 now;
        /*
@@ -2737,18 +2793,22 @@ static inline void update_entity_load_avg(struct sched_entity *se,
        else
                now = cfs_rq_clock_task(group_cfs_rq(se));
-        if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
+        if (!__update_entity_runnable_avg(now, cpu, &se->avg, se->on_rq,
+                                        cfs_rq->curr == se))
                return;
        contrib_delta = __update_entity_load_avg_contrib(se);
+        utilization_delta = __update_entity_utilization_avg_contrib(se);
        if (!update_cfs_rq)
                return;
-        if (se->on_rq)
+        if (se->on_rq) {
                cfs_rq->runnable_load_avg += contrib_delta;
-        else
+                cfs_rq->utilization_load_avg += utilization_delta;
+        } else {
                subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
+        }
 }
 /*
@@ -2823,6 +2883,7 @@ static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
        }
        cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
+        cfs_rq->utilization_load_avg += se->avg.utilization_avg_contrib;
        /* we force update consideration on load-balancer moves */
        update_cfs_rq_blocked_load(cfs_rq, !wakeup);
 }
@@ -2841,6 +2902,7 @@ static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
        update_cfs_rq_blocked_load(cfs_rq, !sleep);
        cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
+        cfs_rq->utilization_load_avg -= se->avg.utilization_avg_contrib;
        if (sleep) {
                cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
                se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
@@ -3178,6 +3240,7 @@ set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
                 */
                update_stats_wait_end(cfs_rq, se);
                __dequeue_entity(cfs_rq, se);
+                update_entity_load_avg(se, 1);
        }
        update_stats_curr_start(cfs_rq, se);
@@ -4304,6 +4367,11 @@ static unsigned long capacity_of(int cpu)
        return cpu_rq(cpu)->cpu_capacity;
 }
+static unsigned long capacity_orig_of(int cpu)
+{
+        return cpu_rq(cpu)->cpu_capacity_orig;
+}
 static unsigned long cpu_avg_load_per_task(int cpu)
 {
        struct rq *rq = cpu_rq(cpu);
@@ -4717,6 +4785,33 @@ next:
 done:
        return target;
 }
+/*
+ * get_cpu_usage returns the amount of capacity of a CPU that is used by CFS
+ * tasks. The unit of the return value must be the one of capacity so we can
+ * compare the usage with the capacity of the CPU that is available for CFS
+ * task (ie cpu_capacity).
+ * cfs.utilization_load_avg is the sum of running time of runnable tasks on a
+ * CPU. It represents the amount of utilization of a CPU in the range
+ * [0..SCHED_LOAD_SCALE].  The usage of a CPU can't be higher than the full
+ * capacity of the CPU because it's about the running time on this CPU.
+ * Nevertheless, cfs.utilization_load_avg can be higher than SCHED_LOAD_SCALE
+ * because of unfortunate rounding in avg_period and running_load_avg or just
+ * after migrating tasks until the average stabilizes with the new running
+ * time. So we need to check that the usage stays into the range
+ * [0..cpu_capacity_orig] and cap if necessary.
+ * Without capping the usage, a group could be seen as overloaded (CPU0 usage
+ * at 121% + CPU1 usage at 80%) whereas CPU1 has 20% of available capacity
+ */
+static int get_cpu_usage(int cpu)
+{
+        unsigned long usage = cpu_rq(cpu)->cfs.utilization_load_avg;
+        unsigned long capacity = capacity_orig_of(cpu);
+        if (usage >= SCHED_LOAD_SCALE)
+                return capacity;
+        return (usage * capacity) >> SCHED_LOAD_SHIFT;
+}
 /*
 * select_task_rq_fair: Select target runqueue for the waking task in domains
@@ -5843,12 +5938,12 @@ struct sg_lb_stats {
        unsigned long sum_weighted_load; /* Weighted load of group's tasks */
        unsigned long load_per_task;
        unsigned long group_capacity;
+        unsigned long group_usage; /* Total usage of the group */
        unsigned int sum_nr_running; /* Nr tasks running in the group */
-        unsigned int group_capacity_factor;
        unsigned int idle_cpus;
        unsigned int group_weight;
        enum group_type group_type;
-        int group_has_free_capacity;
+        int group_no_capacity;
 #ifdef CONFIG_NUMA_BALANCING
        unsigned int nr_numa_running;
        unsigned int nr_preferred_running;
@@ -5919,16 +6014,6 @@ static inline int get_sd_load_idx(struct sched_domain *sd,
        return load_idx;
 }
-static unsigned long default_scale_capacity(struct sched_domain *sd, int cpu)
-{
-        return SCHED_CAPACITY_SCALE;
-}
-unsigned long __weak arch_scale_freq_capacity(struct sched_domain *sd, int cpu)
-{
-        return default_scale_capacity(sd, cpu);
-}
 static unsigned long default_scale_cpu_capacity(struct sched_domain *sd, int cpu)
 {
        if ((sd->flags & SD_SHARE_CPUCAPACITY) && (sd->span_weight > 1))
@@ -5945,7 +6030,7 @@ unsigned long __weak arch_scale_cpu_capacity(struct sched_domain *sd, int cpu)
 static unsigned long scale_rt_capacity(int cpu)
 {
        struct rq *rq = cpu_rq(cpu);
-        u64 total, available, age_stamp, avg;
+        u64 total, used, age_stamp, avg;
        s64 delta;
        /*
@@ -5961,19 +6046,12 @@ static unsigned long scale_rt_capacity(int cpu)
        total = sched_avg_period() + delta;
-        if (unlikely(total < avg)) {
+        used = div_u64(avg, total);
-                /* Ensures that capacity won't end up being negative */
-                available = 0;
-        } else {
-                available = total - avg;
-        }
-        if (unlikely((s64)total < SCHED_CAPACITY_SCALE))
+        if (likely(used < SCHED_CAPACITY_SCALE))
-                total = SCHED_CAPACITY_SCALE;
+                return SCHED_CAPACITY_SCALE - used;
-        total >>= SCHED_CAPACITY_SHIFT;
+        return 1;
-        return div_u64(available, total);
 }
 static void update_cpu_capacity(struct sched_domain *sd, int cpu)
@@ -5988,14 +6066,7 @@ static void update_cpu_capacity(struct sched_domain *sd, int cpu)
        capacity >>= SCHED_CAPACITY_SHIFT;
-        sdg->sgc->capacity_orig = capacity;
+        cpu_rq(cpu)->cpu_capacity_orig = capacity;
-        if (sched_feat(ARCH_CAPACITY))
-                capacity *= arch_scale_freq_capacity(sd, cpu);
-        else
-                capacity *= default_scale_capacity(sd, cpu);
-        capacity >>= SCHED_CAPACITY_SHIFT;
        capacity *= scale_rt_capacity(cpu);
        capacity >>= SCHED_CAPACITY_SHIFT;
@@ -6011,7 +6082,7 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
 {
        struct sched_domain *child = sd->child;
        struct sched_group *group, *sdg = sd->groups;
-        unsigned long capacity, capacity_orig;
+        unsigned long capacity;
        unsigned long interval;
        interval = msecs_to_jiffies(sd->balance_interval);
@@ -6023,7 +6094,7 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
                return;
        }
-        capacity_orig = capacity = 0;
+        capacity = 0;
        if (child->flags & SD_OVERLAP) {
                /*
@@ -6043,19 +6114,15 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
                         * Use capacity_of(), which is set irrespective of domains
                         * in update_cpu_capacity().
                         *
-                         * This avoids capacity/capacity_orig from being 0 and
+                         * This avoids capacity from being 0 and
                         * causing divide-by-zero issues on boot.
-                         *
-                         * Runtime updates will correct capacity_orig.
                         */
                        if (unlikely(!rq->sd)) {
-                                capacity_orig += capacity_of(cpu);
                                capacity += capacity_of(cpu);
                                continue;
                        }
                        sgc = rq->sd->groups->sgc;
-                        capacity_orig += sgc->capacity_orig;
                        capacity += sgc->capacity;
                }
        } else  {
@@ -6066,39 +6133,24 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
                group = child->groups;
                do {
-                        capacity_orig += group->sgc->capacity_orig;
                        capacity += group->sgc->capacity;
                        group = group->next;
                } while (group != child->groups);
        }
-        sdg->sgc->capacity_orig = capacity_orig;
        sdg->sgc->capacity = capacity;
 }
 /*
- * Try and fix up capacity for tiny siblings, this is needed when
+ * Check whether the capacity of the rq has been noticeably reduced by side
- * things like SD_ASYM_PACKING need f_b_g to select another sibling
+ * activity. The imbalance_pct is used for the threshold.
- * which on its own isn't powerful enough.
+ * Return true is the capacity is reduced
- *
- * See update_sd_pick_busiest() and check_asym_packing().
 */
 static inline int
-fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
+check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
 {
-        /*
+        return ((rq->cpu_capacity * sd->imbalance_pct) <
-         * Only siblings can have significantly less than SCHED_CAPACITY_SCALE
+                                (rq->cpu_capacity_orig * 100));
-         */
-        if (!(sd->flags & SD_SHARE_CPUCAPACITY))
-                return 0;
-        /*
-         * If ~90% of the cpu_capacity is still there, we're good.
-         */
-        if (group->sgc->capacity * 32 > group->sgc->capacity_orig * 29)
-                return 1;
-        return 0;
 }
 /*
@@ -6136,37 +6188,56 @@ static inline int sg_imbalanced(struct sched_group *group)
 }
 /*
- * Compute the group capacity factor.
+ * group_has_capacity returns true if the group has spare capacity that could
- *
+ * be used by some tasks.
- * Avoid the issue where N*frac(smt_capacity) >= 1 creates 'phantom' cores by
+ * We consider that a group has spare capacity if the  * number of task is
- * first dividing out the smt factor and computing the actual number of cores
+ * smaller than the number of CPUs or if the usage is lower than the available
- * and limit unit capacity with that.
+ * capacity for CFS tasks.
+ * For the latter, we use a threshold to stabilize the state, to take into
+ * account the variance of the tasks' load and to return true if the available
+ * capacity in meaningful for the load balancer.
+ * As an example, an available capacity of 1% can appear but it doesn't make
+ * any benefit for the load balance.
 */
-static inline int sg_capacity_factor(struct lb_env *env, struct sched_group *group)
+static inline bool
+group_has_capacity(struct lb_env *env, struct sg_lb_stats *sgs)
 {
-        unsigned int capacity_factor, smt, cpus;
+        if (sgs->sum_nr_running < sgs->group_weight)
-        unsigned int capacity, capacity_orig;
+                return true;
-        capacity = group->sgc->capacity;
+        if ((sgs->group_capacity * 100) >
-        capacity_orig = group->sgc->capacity_orig;
+                        (sgs->group_usage * env->sd->imbalance_pct))
-        cpus = group->group_weight;
+                return true;
-        /* smt := ceil(cpus / capacity), assumes: 1 < smt_capacity < 2 */
+        return false;
-        smt = DIV_ROUND_UP(SCHED_CAPACITY_SCALE * cpus, capacity_orig);
+}
-        capacity_factor = cpus / smt; /* cores */
+/*
+ *  group_is_overloaded returns true if the group has more tasks than it can
+ *  handle.
+ *  group_is_overloaded is not equals to !group_has_capacity because a group
+ *  with the exact right number of tasks, has no more spare capacity but is not
+ *  overloaded so both group_has_capacity and group_is_overloaded return
+ *  false.
+ */
+static inline bool
+group_is_overloaded(struct lb_env *env, struct sg_lb_stats *sgs)
+{
+        if (sgs->sum_nr_running <= sgs->group_weight)
+                return false;
-        capacity_factor = min_t(unsigned,
+        if ((sgs->group_capacity * 100) <
-                capacity_factor, DIV_ROUND_CLOSEST(capacity, SCHED_CAPACITY_SCALE));
+                        (sgs->group_usage * env->sd->imbalance_pct))
-        if (!capacity_factor)
+                return true;
-                capacity_factor = fix_small_capacity(env->sd, group);
-        return capacity_factor;
+        return false;
 }
-static enum group_type
+static enum group_type group_classify(struct lb_env *env,
-group_classify(struct sched_group *group, struct sg_lb_stats *sgs)
+                struct sched_group *group,
+                struct sg_lb_stats *sgs)
 {
-        if (sgs->sum_nr_running > sgs->group_capacity_factor)
+        if (sgs->group_no_capacity)
                return group_overloaded;
        if (sg_imbalanced(group))
@@ -6204,6 +6275,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,
                        load = source_load(i, load_idx);
                sgs->group_load += load;
+                sgs->group_usage += get_cpu_usage(i);
                sgs->sum_nr_running += rq->cfs.h_nr_running;
                if (rq->nr_running > 1)
@@ -6226,11 +6298,9 @@ static inline void update_sg_lb_stats(struct lb_env *env,
                sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
        sgs->group_weight = group->group_weight;
-        sgs->group_capacity_factor = sg_capacity_factor(env, group);
-        sgs->group_type = group_classify(group, sgs);
-        if (sgs->group_capacity_factor > sgs->sum_nr_running)
+        sgs->group_no_capacity = group_is_overloaded(env, sgs);
-                sgs->group_has_free_capacity = 1;
+        sgs->group_type = group_classify(env, group, sgs);
 }
 /**
@@ -6352,18 +6422,19 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
                /*
                 * In case the child domain prefers tasks go to siblings
-                 * first, lower the sg capacity factor to one so that we'll try
+                 * first, lower the sg capacity so that we'll try
                 * and move all the excess tasks away. We lower the capacity
                 * of a group only if the local group has the capacity to fit
-                 * these excess tasks, i.e. nr_running < group_capacity_factor. The
+                 * these excess tasks. The extra check prevents the case where
-                 * extra check prevents the case where you always pull from the
+                 * you always pull from the heaviest group when it is already
-                 * heaviest group when it is already under-utilized (possible
+                 * under-utilized (possible with a large weight task outweighs
-                 * with a large weight task outweighs the tasks on the system).
+                 * the tasks on the system).
                 */
                if (prefer_sibling && sds->local &&
-                    sds->local_stat.group_has_free_capacity) {
+                    group_has_capacity(env, &sds->local_stat) &&
-                        sgs->group_capacity_factor = min(sgs->group_capacity_factor, 1U);
+                    (sgs->sum_nr_running > 1)) {
-                        sgs->group_type = group_classify(sg, sgs);
+                        sgs->group_no_capacity = 1;
+                        sgs->group_type = group_overloaded;
                }
                if (update_sd_pick_busiest(env, sds, sg, sgs)) {
@@ -6543,11 +6614,12 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
         */
        if (busiest->group_type == group_overloaded &&
            local->group_type   == group_overloaded) {
-                load_above_capacity =
+                load_above_capacity = busiest->sum_nr_running *
-                        (busiest->sum_nr_running - busiest->group_capacity_factor);
+                                        SCHED_LOAD_SCALE;
+                if (load_above_capacity > busiest->group_capacity)
-                load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE);
+                        load_above_capacity -= busiest->group_capacity;
-                load_above_capacity /= busiest->group_capacity;
+                else
+                        load_above_capacity = ~0UL;
        }
        /*
@@ -6610,6 +6682,7 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
        local = &sds.local_stat;
        busiest = &sds.busiest_stat;
+        /* ASYM feature bypasses nice load balance check */
        if ((env->idle == CPU_IDLE || env->idle == CPU_NEWLY_IDLE) &&
            check_asym_packing(env, &sds))
                return sds.busiest;
@@ -6630,8 +6703,8 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
                goto force_balance;
        /* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */
-        if (env->idle == CPU_NEWLY_IDLE && local->group_has_free_capacity &&
+        if (env->idle == CPU_NEWLY_IDLE && group_has_capacity(env, local) &&
-            !busiest->group_has_free_capacity)
+            busiest->group_no_capacity)
                goto force_balance;
        /*
@@ -6690,7 +6763,7 @@ static struct rq *find_busiest_queue(struct lb_env *env,
        int i;
        for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
-                unsigned long capacity, capacity_factor, wl;
+                unsigned long capacity, wl;
                enum fbq_type rt;
                rq = cpu_rq(i);
@@ -6719,9 +6792,6 @@ static struct rq *find_busiest_queue(struct lb_env *env,
                        continue;
                capacity = capacity_of(i);
-                capacity_factor = DIV_ROUND_CLOSEST(capacity, SCHED_CAPACITY_SCALE);
-                if (!capacity_factor)
-                        capacity_factor = fix_small_capacity(env->sd, group);
                wl = weighted_cpuload(i);
@@ -6729,7 +6799,9 @@ static struct rq *find_busiest_queue(struct lb_env *env,
                 * When comparing with imbalance, use weighted_cpuload()
                 * which is not scaled with the cpu capacity.
                 */
-                if (capacity_factor && rq->nr_running == 1 && wl > env->imbalance)
+                if (rq->nr_running == 1 && wl > env->imbalance &&
+                    !check_cpu_capacity(rq, env->sd))
                        continue;
                /*
@@ -6777,6 +6849,19 @@ static int need_active_balance(struct lb_env *env)
                        return 1;
        }
+        /*
+         * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
+         * It's worth migrating the task if the src_cpu's capacity is reduced
+         * because of other sched_class or IRQs if more capacity stays
+         * available on dst_cpu.
+         */
+        if ((env->idle != CPU_NOT_IDLE) &&
+            (env->src_rq->cfs.h_nr_running == 1)) {
+                if ((check_cpu_capacity(env->src_rq, sd)) &&
+                    (capacity_of(env->src_cpu)*sd->imbalance_pct < capacity_of(env->dst_cpu)*100))
+                        return 1;
+        }
        return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
 }
@@ -6876,6 +6961,9 @@ redo:
        schedstat_add(sd, lb_imbalance[idle], env.imbalance);
+        env.src_cpu = busiest->cpu;
+        env.src_rq = busiest;
        ld_moved = 0;
        if (busiest->nr_running > 1) {
                /*
@@ -6885,8 +6973,6 @@ redo:
                 * correctly treated as an imbalance.
                 */
                env.flags |= LBF_ALL_PINNED;
-                env.src_cpu   = busiest->cpu;
-                env.src_rq    = busiest;
                env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);
 more_balance:
@@ -7586,22 +7672,25 @@ end:
 /*
 * Current heuristic for kicking the idle load balancer in the presence
- * of an idle cpu is the system.
+ * of an idle cpu in the system.
 *   - This rq has more than one task.
- *   - At any scheduler domain level, this cpu's scheduler group has multiple
+ *   - This rq has at least one CFS task and the capacity of the CPU is
- *     busy cpu's exceeding the group's capacity.
+ *     significantly reduced because of RT tasks or IRQs.
+ *   - At parent of LLC scheduler domain level, this cpu's scheduler group has
+ *     multiple busy cpu.
 *   - For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler
 *     domain span are idle.
 */
-static inline int nohz_kick_needed(struct rq *rq)
+static inline bool nohz_kick_needed(struct rq *rq)
 {
        unsigned long now = jiffies;
        struct sched_domain *sd;
        struct sched_group_capacity *sgc;
        int nr_busy, cpu = rq->cpu;
+        bool kick = false;
        if (unlikely(rq->idle_balance))
-                return 0;
+                return false;
       /*
        * We may be recently in ticked or tickless idle mode. At the first
@@ -7615,38 +7704,46 @@ static inline int nohz_kick_needed(struct rq *rq)
         * balancing.
         */
        if (likely(!atomic_read(&nohz.nr_cpus)))
-                return 0;
+                return false;
        if (time_before(now, nohz.next_balance))
-                return 0;
+                return false;
        if (rq->nr_running >= 2)
-                goto need_kick;
+                return true;
        rcu_read_lock();
        sd = rcu_dereference(per_cpu(sd_busy, cpu));
        if (sd) {
                sgc = sd->groups->sgc;
                nr_busy = atomic_read(&sgc->nr_busy_cpus);
-                if (nr_busy > 1)
+                if (nr_busy > 1) {
-                        goto need_kick_unlock;
+                        kick = true;
+                        goto unlock;
+                }
        }
-        sd = rcu_dereference(per_cpu(sd_asym, cpu));
+        sd = rcu_dereference(rq->sd);
+        if (sd) {
+                if ((rq->cfs.h_nr_running >= 1) &&
+                                check_cpu_capacity(rq, sd)) {
+                        kick = true;
+                        goto unlock;
+                }
+        }
+        sd = rcu_dereference(per_cpu(sd_asym, cpu));
        if (sd && (cpumask_first_and(nohz.idle_cpus_mask,
-                                  sched_domain_span(sd)) < cpu))
+                                  sched_domain_span(sd)) < cpu)) {
-                goto need_kick_unlock;
+                kick = true;
+                goto unlock;
-        rcu_read_unlock();
+        }
-        return 0;
-need_kick_unlock:
+unlock:
        rcu_read_unlock();
-need_kick:
+        return kick;
-        return 1;
 }
 #else
 static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) { }
@@ -7662,14 +7759,16 @@ static void run_rebalance_domains(struct softirq_action *h)
        enum cpu_idle_type idle = this_rq->idle_balance ?
                                                CPU_IDLE : CPU_NOT_IDLE;
-        rebalance_domains(this_rq, idle);
        /*
         * If this cpu has a pending nohz_balance_kick, then do the
         * balancing on behalf of the other idle cpus whose ticks are
-         * stopped.
+         * stopped. Do nohz_idle_balance *before* rebalance_domains to
+         * give the idle cpus a chance to load balance. Else we may
+         * load balance only within the local sched_domain hierarchy
+         * and abort nohz_idle_balance altogether if we pull some load.
         */
        nohz_idle_balance(this_rq, idle);
+        rebalance_domains(this_rq, idle);
 }
 /*
diff --git a/kernel/sched/features.h b/kernel/sched/features.h
index 90284d117fe6..91e33cd485f6 100644
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -56,6 +56,19 @@ SCHED_FEAT(NONTASK_CAPACITY, true)
 */
 SCHED_FEAT(TTWU_QUEUE, true)
+#ifdef HAVE_RT_PUSH_IPI
+/*
+ * In order to avoid a thundering herd attack of CPUs that are
+ * lowering their priorities at the same time, and there being
+ * a single CPU that has an RT task that can migrate and is waiting
+ * to run, where the other CPUs will try to take that CPUs
+ * rq lock and possibly create a large contention, sending an
+ * IPI to that CPU and let that CPU push the RT task to where
+ * it should go may be a better scenario.
+ */
+SCHED_FEAT(RT_PUSH_IPI, true)
+#endif
 SCHED_FEAT(FORCE_SD_OVERLAP, false)
 SCHED_FEAT(RT_RUNTIME_SHARE, true)
 SCHED_FEAT(LB_MIN, false)
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index f4d4b077eba0..575da76a3874 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -6,6 +6,7 @@
 #include "sched.h"
 #include <linux/slab.h>
+#include <linux/irq_work.h>
 int sched_rr_timeslice = RR_TIMESLICE;
@@ -59,7 +60,11 @@ static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
        raw_spin_unlock(&rt_b->rt_runtime_lock);
 }
-void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
+#ifdef CONFIG_SMP
+static void push_irq_work_func(struct irq_work *work);
+#endif
+void init_rt_rq(struct rt_rq *rt_rq)
 {
        struct rt_prio_array *array;
        int i;
@@ -78,7 +83,14 @@ void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
        rt_rq->rt_nr_migratory = 0;
        rt_rq->overloaded = 0;
        plist_head_init(&rt_rq->pushable_tasks);
+#ifdef HAVE_RT_PUSH_IPI
+        rt_rq->push_flags = 0;
+        rt_rq->push_cpu = nr_cpu_ids;
+        raw_spin_lock_init(&rt_rq->push_lock);
+        init_irq_work(&rt_rq->push_work, push_irq_work_func);
 #endif
+#endif /* CONFIG_SMP */
        /* We start is dequeued state, because no RT tasks are queued */
        rt_rq->rt_queued = 0;
@@ -193,7 +205,7 @@ int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent)
                if (!rt_se)
                        goto err_free_rq;
-                init_rt_rq(rt_rq, cpu_rq(i));
+                init_rt_rq(rt_rq);
                rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime;
                init_tg_rt_entry(tg, rt_rq, rt_se, i, parent->rt_se[i]);
        }
@@ -1778,6 +1790,164 @@ static void push_rt_tasks(struct rq *rq)
                ;
 }
+#ifdef HAVE_RT_PUSH_IPI
+/*
+ * The search for the next cpu always starts at rq->cpu and ends
+ * when we reach rq->cpu again. It will never return rq->cpu.
+ * This returns the next cpu to check, or nr_cpu_ids if the loop
+ * is complete.
+ *
+ * rq->rt.push_cpu holds the last cpu returned by this function,
+ * or if this is the first instance, it must hold rq->cpu.
+ */
+static int rto_next_cpu(struct rq *rq)
+{
+        int prev_cpu = rq->rt.push_cpu;
+        int cpu;
+        cpu = cpumask_next(prev_cpu, rq->rd->rto_mask);
+        /*
+         * If the previous cpu is less than the rq's CPU, then it already
+         * passed the end of the mask, and has started from the beginning.
+         * We end if the next CPU is greater or equal to rq's CPU.
+         */
+        if (prev_cpu < rq->cpu) {
+                if (cpu >= rq->cpu)
+                        return nr_cpu_ids;
+        } else if (cpu >= nr_cpu_ids) {
+                /*
+                 * We passed the end of the mask, start at the beginning.
+                 * If the result is greater or equal to the rq's CPU, then
+                 * the loop is finished.
+                 */
+                cpu = cpumask_first(rq->rd->rto_mask);
+                if (cpu >= rq->cpu)
+                        return nr_cpu_ids;
+        }
+        rq->rt.push_cpu = cpu;
+        /* Return cpu to let the caller know if the loop is finished or not */
+        return cpu;
+}
+static int find_next_push_cpu(struct rq *rq)
+{
+        struct rq *next_rq;
+        int cpu;
+        while (1) {
+                cpu = rto_next_cpu(rq);
+                if (cpu >= nr_cpu_ids)
+                        break;
+                next_rq = cpu_rq(cpu);
+                /* Make sure the next rq can push to this rq */
+                if (next_rq->rt.highest_prio.next < rq->rt.highest_prio.curr)
+                        break;
+        }
+        return cpu;
+}
+#define RT_PUSH_IPI_EXECUTING           1
+#define RT_PUSH_IPI_RESTART             2
+static void tell_cpu_to_push(struct rq *rq)
+{
+        int cpu;
+        if (rq->rt.push_flags & RT_PUSH_IPI_EXECUTING) {
+                raw_spin_lock(&rq->rt.push_lock);
+                /* Make sure it's still executing */
+                if (rq->rt.push_flags & RT_PUSH_IPI_EXECUTING) {
+                        /*
+                         * Tell the IPI to restart the loop as things have
+                         * changed since it started.
+                         */
+                        rq->rt.push_flags |= RT_PUSH_IPI_RESTART;
+                        raw_spin_unlock(&rq->rt.push_lock);
+                        return;
+                }
+                raw_spin_unlock(&rq->rt.push_lock);
+        }
+        /* When here, there's no IPI going around */
+        rq->rt.push_cpu = rq->cpu;
+        cpu = find_next_push_cpu(rq);
+        if (cpu >= nr_cpu_ids)
+                return;
+        rq->rt.push_flags = RT_PUSH_IPI_EXECUTING;
+        irq_work_queue_on(&rq->rt.push_work, cpu);
+}
+/* Called from hardirq context */
+static void try_to_push_tasks(void *arg)
+{
+        struct rt_rq *rt_rq = arg;
+        struct rq *rq, *src_rq;
+        int this_cpu;
+        int cpu;
+        this_cpu = rt_rq->push_cpu;
+        /* Paranoid check */
+        BUG_ON(this_cpu != smp_processor_id());
+        rq = cpu_rq(this_cpu);
+        src_rq = rq_of_rt_rq(rt_rq);
+again:
+        if (has_pushable_tasks(rq)) {
+                raw_spin_lock(&rq->lock);
+                push_rt_task(rq);
+                raw_spin_unlock(&rq->lock);
+        }
+        /* Pass the IPI to the next rt overloaded queue */
+        raw_spin_lock(&rt_rq->push_lock);
+        /*
+         * If the source queue changed since the IPI went out,
+         * we need to restart the search from that CPU again.
+         */
+        if (rt_rq->push_flags & RT_PUSH_IPI_RESTART) {
+                rt_rq->push_flags &= ~RT_PUSH_IPI_RESTART;
+                rt_rq->push_cpu = src_rq->cpu;
+        }
+        cpu = find_next_push_cpu(src_rq);
+        if (cpu >= nr_cpu_ids)
+                rt_rq->push_flags &= ~RT_PUSH_IPI_EXECUTING;
+        raw_spin_unlock(&rt_rq->push_lock);
+        if (cpu >= nr_cpu_ids)
+                return;
+        /*
+         * It is possible that a restart caused this CPU to be
+         * chosen again. Don't bother with an IPI, just see if we
+         * have more to push.
+         */
+        if (unlikely(cpu == rq->cpu))
+                goto again;
+        /* Try the next RT overloaded CPU */
+        irq_work_queue_on(&rt_rq->push_work, cpu);
+}
+static void push_irq_work_func(struct irq_work *work)
+{
+        struct rt_rq *rt_rq = container_of(work, struct rt_rq, push_work);
+        try_to_push_tasks(rt_rq);
+}
+#endif /* HAVE_RT_PUSH_IPI */
 static int pull_rt_task(struct rq *this_rq)
 {
        int this_cpu = this_rq->cpu, ret = 0, cpu;
@@ -1793,6 +1963,13 @@ static int pull_rt_task(struct rq *this_rq)
         */
        smp_rmb();
+#ifdef HAVE_RT_PUSH_IPI
+        if (sched_feat(RT_PUSH_IPI)) {
+                tell_cpu_to_push(this_rq);
+                return 0;
+        }
+#endif
        for_each_cpu(cpu, this_rq->rd->rto_mask) {
                if (this_cpu == cpu)
                        continue;
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index dc0f435a2779..e0e129993958 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -6,6 +6,7 @@
 #include <linux/mutex.h>
 #include <linux/spinlock.h>
 #include <linux/stop_machine.h>
+#include <linux/irq_work.h>
 #include <linux/tick.h>
 #include <linux/slab.h>
@@ -362,8 +363,14 @@ struct cfs_rq {
         * Under CFS, load is tracked on a per-entity basis and aggregated up.
         * This allows for the description of both thread and group usage (in
         * the FAIR_GROUP_SCHED case).
+         * runnable_load_avg is the sum of the load_avg_contrib of the
+         * sched_entities on the rq.
+         * blocked_load_avg is similar to runnable_load_avg except that its
+         * the blocked sched_entities on the rq.
+         * utilization_load_avg is the sum of the average running time of the
+         * sched_entities on the rq.
         */
-        unsigned long runnable_load_avg, blocked_load_avg;
+        unsigned long runnable_load_avg, blocked_load_avg, utilization_load_avg;
        atomic64_t decay_counter;
        u64 last_decay;
        atomic_long_t removed_load;
@@ -418,6 +425,11 @@ static inline int rt_bandwidth_enabled(void)
        return sysctl_sched_rt_runtime >= 0;
 }
+/* RT IPI pull logic requires IRQ_WORK */
+#ifdef CONFIG_IRQ_WORK
+# define HAVE_RT_PUSH_IPI
+#endif
 /* Real-Time classes' related field in a runqueue: */
 struct rt_rq {
        struct rt_prio_array active;
@@ -435,7 +447,13 @@ struct rt_rq {
        unsigned long rt_nr_total;
        int overloaded;
        struct plist_head pushable_tasks;
+#ifdef HAVE_RT_PUSH_IPI
+        int push_flags;
+        int push_cpu;
+        struct irq_work push_work;
+        raw_spinlock_t push_lock;
 #endif
+#endif /* CONFIG_SMP */
        int rt_queued;
        int rt_throttled;
@@ -597,6 +615,7 @@ struct rq {
        struct sched_domain *sd;
        unsigned long cpu_capacity;
+        unsigned long cpu_capacity_orig;
        unsigned char idle_balance;
        /* For active balancing */
@@ -807,7 +826,7 @@ struct sched_group_capacity {
         * CPU capacity of this group, SCHED_LOAD_SCALE being max capacity
         * for a single CPU.
         */
-        unsigned int capacity, capacity_orig;
+        unsigned int capacity;
        unsigned long next_update;
        int imbalance; /* XXX unrelated to capacity but shared group state */
        /*
@@ -1368,9 +1387,18 @@ static inline int hrtick_enabled(struct rq *rq)
 #ifdef CONFIG_SMP
 extern void sched_avg_update(struct rq *rq);
+#ifndef arch_scale_freq_capacity
+static __always_inline
+unsigned long arch_scale_freq_capacity(struct sched_domain *sd, int cpu)
+{
+        return SCHED_CAPACITY_SCALE;
+}
+#endif
 static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
 {
-        rq->rt_avg += rt_delta;
+        rq->rt_avg += rt_delta * arch_scale_freq_capacity(NULL, cpu_of(rq));
        sched_avg_update(rq);
 }
 #else
@@ -1643,8 +1671,8 @@ extern void print_rt_stats(struct seq_file *m, int cpu);
 extern void print_dl_stats(struct seq_file *m, int cpu);
 extern void init_cfs_rq(struct cfs_rq *cfs_rq);
-extern void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq);
+extern void init_rt_rq(struct rt_rq *rt_rq);
-extern void init_dl_rq(struct dl_rq *dl_rq, struct rq *rq);
+extern void init_dl_rq(struct dl_rq *dl_rq);
 extern void cfs_bandwidth_usage_inc(void);
 extern void cfs_bandwidth_usage_dec(void);