From a47662b5d1b8bc45bdbb25e16b003f5613f47cac Mon Sep 17 00:00:00 2001 From: Morten Rasmussen Date: Fri, 17 Jul 2015 16:45:07 +0100 Subject: [PATCH] ANDROID: sched: Add group_misfit_task load-balance type To maximize throughput in systems with asymmetric cpu capacities (e.g. high RT/IRQ load and/or ARM big.LITTLE) load-balancing has to consider task and cpu utilization as well as per-cpu compute capacity when load-balancing in addition to the current average load based load-balancing policy. Tasks that are scheduled on a lower capacity cpu need to be identified and migrated to a higher capacity cpu if possible to maximize throughput. To implement this additional policy an additional group_type (load-balance scenario) is added: group_misfit_task. This represents scenarios where a sched_group has one or more tasks that are not suitable for its per-cpu capacity. group_misfit_task is only considered if the system is not overloaded in any other way (group_imbalanced or group_overloaded). Identifying misfit tasks requires the rq lock to be held. To avoid taking remote rq locks to examine source sched_groups for misfit tasks, each cpu is responsible for tracking misfit tasks themselves and update the rq->misfit_task flag. This means checking task utilization when tasks are scheduled and on sched_tick. cc: Ingo Molnar cc: Peter Zijlstra Signed-off-by: Morten Rasmussen Change-Id: I9e3ccd5c3bde1102e5121c83ec3561cf90b684b7 (fixup for !SMP platforms) Signed-off-by: Chris Redpath --- kernel/sched/fair.c | 58 ++++++++++++++++++++++++++++++++++++++------ kernel/sched/sched.h | 2 ++ 2 files changed, 53 insertions(+), 7 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 65fd571f4917..2677eada93c0 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5901,6 +5901,11 @@ static int cpu_util_wake(int cpu, struct task_struct *p) return (util >= capacity) ? capacity : util; } +static inline int task_fits_capacity(struct task_struct *p, long capacity) +{ + return capacity * 1024 > task_util(p) * capacity_margin; +} + /* * Disable WAKE_AFFINE in the case where task @p doesn't fit in the * capacity of either the waking CPU @cpu or the previous CPU @prev_cpu. @@ -5922,7 +5927,7 @@ static int wake_cap(struct task_struct *p, int cpu, int prev_cpu) /* Bring task utilization in sync with prev_cpu */ sync_entity_load_avg(&p->se); - return min_cap * 1024 < task_util(p) * capacity_margin; + return task_fits_capacity(p, min_cap); } static bool cpu_overutilized(int cpu) @@ -6252,6 +6257,29 @@ preempt: set_last_buddy(se); } +static inline void update_misfit_task(struct rq *rq, struct task_struct *p) +{ +#ifdef CONFIG_SMP + rq->misfit_task = !task_fits_capacity(p, capacity_of(rq->cpu)); +#endif +} + +static inline void clear_rq_misfit(struct rq *rq) +{ +#ifdef CONFIG_SMP + rq->misfit_task = 0; +#endif +} + +static inline unsigned int rq_has_misfit(struct rq *rq) +{ +#ifdef CONFIG_SMP + return rq->misfit_task; +#else + return 0; +#endif +} + static struct task_struct * pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) { @@ -6342,6 +6370,8 @@ again: if (hrtick_enabled(rq)) hrtick_start_fair(rq, p); + update_misfit_task(rq, p); + return p; simple: #endif @@ -6359,9 +6389,12 @@ simple: if (hrtick_enabled(rq)) hrtick_start_fair(rq, p); + update_misfit_task(rq, p); + return p; idle: + clear_rq_misfit(rq); new_tasks = idle_balance(rq, rf); /* @@ -6567,6 +6600,13 @@ static unsigned long __read_mostly max_load_balance_interval = HZ/10; enum fbq_type { regular, remote, all }; +enum group_type { + group_other = 0, + group_misfit_task, + group_imbalanced, + group_overloaded, +}; + #define LBF_ALL_PINNED 0x01 #define LBF_NEED_BREAK 0x02 #define LBF_DST_PINNED 0x04 @@ -7079,12 +7119,6 @@ static unsigned long task_h_load(struct task_struct *p) /********** Helpers for find_busiest_group ************************/ -enum group_type { - group_other = 0, - group_imbalanced, - group_overloaded, -}; - /* * sg_lb_stats - stats of a sched_group required for load_balancing */ @@ -7100,6 +7134,7 @@ struct sg_lb_stats { unsigned int group_weight; enum group_type group_type; int group_no_capacity; + int group_misfit_task; /* A cpu has a task too big for its capacity */ #ifdef CONFIG_NUMA_BALANCING unsigned int nr_numa_running; unsigned int nr_preferred_running; @@ -7399,6 +7434,9 @@ group_type group_classify(struct sched_group *group, if (sg_imbalanced(group)) return group_imbalanced; + if (sgs->group_misfit_task) + return group_misfit_task; + return group_other; } @@ -7448,6 +7486,10 @@ static inline void update_sg_lb_stats(struct lb_env *env, */ if (!nr_running && idle_cpu(i)) sgs->idle_cpus++; + + if (env->sd->flags & SD_ASYM_CPUCAPACITY && + !sgs->group_misfit_task && rq->misfit_task) + sgs->group_misfit_task = capacity_of(i); } /* Adjust by relative CPU capacity of the group */ @@ -9069,6 +9111,8 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) if (static_branch_unlikely(&sched_numa_balancing)) task_tick_numa(rq, curr); + + update_misfit_task(rq, curr); } /* diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 3b448ba82225..35575c25bd41 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -731,6 +731,8 @@ struct rq { struct callback_head *balance_callback; unsigned char idle_balance; + + unsigned int misfit_task; /* For active balancing */ int active_balance; int push_cpu; -- 2.20.1