linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Morten Rasmussen <morten.rasmussen@arm.com>
To: peterz@infradead.org, mingo@redhat.com
Cc: valentin.schneider@arm.com, dietmar.eggemann@arm.com,
	vincent.guittot@linaro.org, gaku.inami.xh@renesas.com,
	linux-kernel@vger.kernel.org,
	Morten Rasmussen <morten.rasmussen@arm.com>
Subject: [PATCHv4 04/12] sched/fair: Consider misfit tasks when load-balancing
Date: Wed,  4 Jul 2018 11:17:42 +0100	[thread overview]
Message-ID: <1530699470-29808-5-git-send-email-morten.rasmussen@arm.com> (raw)
In-Reply-To: <1530699470-29808-1-git-send-email-morten.rasmussen@arm.com>

On asymmetric cpu capacity systems load intensive tasks can end up on
cpus that don't suit their compute demand.  In this scenarios 'misfit'
tasks should be migrated to cpus with higher compute capacity to ensure
better throughput. group_misfit_task indicates this scenario, but tweaks
to the load-balance code are needed to make the migrations happen.

Misfit balancing only makes sense between a source group of lower
per-cpu capacity and destination group of higher compute capacity.
Otherwise, misfit balancing is ignored. group_misfit_task has lowest
priority so any imbalance due to overload is dealt with first.

The modifications are:

1. Only pick a group containing misfit tasks as the busiest group if the
   destination group has higher capacity and has spare capacity.
2. When the busiest group is a 'misfit' group, skip the usual average
   load and group capacity checks.
3. Set the imbalance for 'misfit' balancing sufficiently high for a task
   to be pulled ignoring average load.
4. Pick the cpu with the highest misfit load as the source cpu.
5. If the misfit task is alone on the source cpu, go for active
   balancing.

cc: Ingo Molnar <mingo@redhat.com>
cc: Peter Zijlstra <peterz@infradead.org>

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
 kernel/sched/fair.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 49 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 09ede4321a3d..6e885d92fad2 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7285,6 +7285,7 @@ struct lb_env {
 	unsigned int		loop_max;
 
 	enum fbq_type		fbq_type;
+	enum group_type		src_grp_type;
 	struct list_head	tasks;
 };
 
@@ -8243,6 +8244,17 @@ static bool update_sd_pick_busiest(struct lb_env *env,
 {
 	struct sg_lb_stats *busiest = &sds->busiest_stat;
 
+	/*
+	 * Don't try to pull misfit tasks we can't help.
+	 * We can use max_capacity here as reduction in capacity on some
+	 * cpus in the group should either be possible to resolve
+	 * internally or be covered by avg_load imbalance (eventually).
+	 */
+	if (sgs->group_type == group_misfit_task &&
+	    (!group_smaller_max_cpu_capacity(sg, sds->local) ||
+	     !group_has_capacity(env, &sds->local_stat)))
+		return false;
+
 	if (sgs->group_type > busiest->group_type)
 		return true;
 
@@ -8265,6 +8277,13 @@ static bool update_sd_pick_busiest(struct lb_env *env,
 	    group_smaller_min_cpu_capacity(sds->local, sg))
 		return false;
 
+	/*
+	 * If we have more than one misfit sg go with the biggest misfit.
+	 */
+	if (sgs->group_type == group_misfit_task &&
+	    sgs->group_misfit_task_load < busiest->group_misfit_task_load)
+		return false;
+
 asym_packing:
 	/* This is the busiest node in its class. */
 	if (!(env->sd->flags & SD_ASYM_PACKING))
@@ -8562,8 +8581,9 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 	 * factors in sg capacity and sgs with smaller group_type are
 	 * skipped when updating the busiest sg:
 	 */
-	if (busiest->avg_load <= sds->avg_load ||
-	    local->avg_load >= sds->avg_load) {
+	if (busiest->group_type != group_misfit_task &&
+	    (busiest->avg_load <= sds->avg_load ||
+	     local->avg_load >= sds->avg_load)) {
 		env->imbalance = 0;
 		return fix_small_imbalance(env, sds);
 	}
@@ -8597,6 +8617,12 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 		(sds->avg_load - local->avg_load) * local->group_capacity
 	) / SCHED_CAPACITY_SCALE;
 
+	/* Boost imbalance to allow misfit task to be balanced. */
+	if (busiest->group_type == group_misfit_task) {
+		env->imbalance = max_t(long, env->imbalance,
+				       busiest->group_misfit_task_load);
+	}
+
 	/*
 	 * if *imbalance is less than the average load per runnable task
 	 * there is no guarantee that any tasks will be moved so we'll have
@@ -8663,6 +8689,10 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
 	    busiest->group_no_capacity)
 		goto force_balance;
 
+	/* Misfit tasks should be dealt with regardless of the avg load */
+	if (busiest->group_type == group_misfit_task)
+		goto force_balance;
+
 	/*
 	 * If the local group is busier than the selected busiest group
 	 * don't try and pull any tasks.
@@ -8700,6 +8730,7 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
 
 force_balance:
 	/* Looks like there is an imbalance. Compute it */
+	env->src_grp_type = busiest->group_type;
 	calculate_imbalance(env, &sds);
 	return sds.busiest;
 
@@ -8747,6 +8778,19 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 		if (rt > env->fbq_type)
 			continue;
 
+		/*
+		 * For ASYM_CPUCAPACITY domains with misfit tasks we simply
+		 * seek the "biggest" misfit task.
+		 */
+		if (env->src_grp_type == group_misfit_task) {
+			if (rq->misfit_task_load > busiest_load) {
+				busiest_load = rq->misfit_task_load;
+				busiest = rq;
+			}
+
+			continue;
+		}
+
 		capacity = capacity_of(i);
 
 		wl = weighted_cpuload(rq);
@@ -8816,6 +8860,9 @@ static int need_active_balance(struct lb_env *env)
 			return 1;
 	}
 
+	if (env->src_grp_type == group_misfit_task)
+		return 1;
+
 	return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
 }
 
-- 
2.7.4


  parent reply	other threads:[~2018-07-04 10:18 UTC|newest]

Thread overview: 49+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-07-04 10:17 [PATCHv4 00/12] sched/fair: Migrate 'misfit' tasks on asymmetric capacity systems Morten Rasmussen
2018-07-04 10:17 ` [PATCHv4 01/12] sched: Add static_key for asymmetric cpu capacity optimizations Morten Rasmussen
2018-07-31 10:59   ` Peter Zijlstra
2018-08-02 15:15     ` Morten Rasmussen
2018-09-10 10:13   ` [tip:sched/core] sched/topology: Add static_key for asymmetric CPU " tip-bot for Morten Rasmussen
2018-07-04 10:17 ` [PATCHv4 02/12] sched/fair: Add group_misfit_task load-balance type Morten Rasmussen
2018-09-10 10:13   ` [tip:sched/core] sched/fair: Add 'group_misfit_task' " tip-bot for Morten Rasmussen
2018-07-04 10:17 ` [PATCHv4 03/12] sched: Add sched_group per-cpu max capacity Morten Rasmussen
2018-09-10 10:14   ` [tip:sched/core] sched/fair: Add sched_group per-CPU " tip-bot for Morten Rasmussen
2018-07-04 10:17 ` Morten Rasmussen [this message]
2018-09-10 10:14   ` [tip:sched/core] sched/fair: Consider misfit tasks when load-balancing tip-bot for Morten Rasmussen
2018-07-04 10:17 ` [PATCHv4 05/12] sched/fair: Kick nohz balance if rq->misfit_task_load Morten Rasmussen
2018-09-10 10:15   ` [tip:sched/core] " tip-bot for Valentin Schneider
2018-07-04 10:17 ` [PATCHv4 06/12] sched/fair: Change prefer_sibling type to bool Morten Rasmussen
2018-09-10 10:15   ` [tip:sched/core] sched/fair: Change 'prefer_sibling' " tip-bot for Valentin Schneider
2018-07-04 10:17 ` [PATCHv4 07/12] sched: Change root_domain->overload type to int Morten Rasmussen
2018-09-10 10:16   ` [tip:sched/core] sched/core: " tip-bot for Valentin Schneider
2018-07-04 10:17 ` [PATCHv4 08/12] sched: Wrap rq->rd->overload accesses with READ/WRITE_ONCE Morten Rasmussen
2018-09-10 10:17   ` [tip:sched/core] sched/fair: Wrap rq->rd->overload accesses with READ/WRITE_ONCE() tip-bot for Valentin Schneider
2018-07-04 10:17 ` [PATCHv4 09/12] sched/fair: Set rq->rd->overload when misfit Morten Rasmussen
2018-09-10 10:17   ` [tip:sched/core] " tip-bot for Valentin Schneider
2018-07-04 10:17 ` [PATCHv4 10/12] sched/fair: Don't move tasks to lower capacity cpus unless necessary Morten Rasmussen
2018-09-10 10:18   ` [tip:sched/core] sched/fair: Don't move tasks to lower capacity CPUs " tip-bot for Chris Redpath
2018-07-04 10:17 ` [PATCHv4 11/12] sched/core: Disable SD_ASYM_CPUCAPACITY for root_domains without asymmetry Morten Rasmussen
2018-07-05 13:31   ` Quentin Perret
2018-07-05 14:13     ` Morten Rasmussen
2018-07-05 15:03       ` Quentin Perret
2018-07-20 13:54         ` Morten Rasmussen
2018-07-04 10:17 ` [PATCHv4 12/12] sched/core: Disable SD_PREFER_SIBLING on asymmetric cpu capacity domains Morten Rasmussen
2018-07-06 10:18   ` Vincent Guittot
2018-07-06 14:31     ` Morten Rasmussen
2018-07-31 12:17       ` Vincent Guittot
2018-07-31 12:33         ` Valentin Schneider
2018-08-06 10:20           ` Vincent Guittot
2018-08-06 10:53             ` Valentin Schneider
2018-08-10  9:30               ` Vincent Guittot
2018-09-10 10:18   ` [tip:sched/core] sched/core: Disable SD_PREFER_SIBLING on asymmetric CPU " tip-bot for Morten Rasmussen
2018-07-06 10:18 ` [PATCHv4 00/12] sched/fair: Migrate 'misfit' tasks on asymmetric capacity systems Vincent Guittot
2018-07-09 15:08   ` Morten Rasmussen
2018-07-26 17:14     ` Valentin Schneider
2018-07-30 14:30       ` Dietmar Eggemann
2018-07-31 12:13         ` Vincent Guittot
2018-07-31 12:14           ` Dietmar Eggemann
2018-07-31 12:11     ` Vincent Guittot
2018-07-31 12:00 ` Peter Zijlstra
2018-07-31 12:10   ` Valentin Schneider
2018-07-31 12:50     ` Morten Rasmussen
2018-08-17  1:57 ` Joel Fernandes
2018-08-20  2:50 ` Gaku Inami

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1530699470-29808-5-git-send-email-morten.rasmussen@arm.com \
    --to=morten.rasmussen@arm.com \
    --cc=dietmar.eggemann@arm.com \
    --cc=gaku.inami.xh@renesas.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=valentin.schneider@arm.com \
    --cc=vincent.guittot@linaro.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).