From patchwork Tue Mar 20 09:43:09 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dietmar Eggemann X-Patchwork-Id: 132141 Delivered-To: patch@linaro.org Received: by 10.46.84.29 with SMTP id i29csp632434ljb; Tue, 20 Mar 2018 02:46:05 -0700 (PDT) X-Google-Smtp-Source: AG47ELveD/KXO21Yw/JgYUpgm45JHctDoy/FNgxmLtdweECfo9w/WRe1xtXQN5fWpHK/momIADSC X-Received: by 10.98.7.68 with SMTP id b65mr13017708pfd.39.1521539165076; Tue, 20 Mar 2018 02:46:05 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1521539165; cv=none; d=google.com; s=arc-20160816; b=ne4VS79oPU4n7HEoBkHAsYftookE6Fj6ARq52dbYhPVLZ+chNiDEHsUO0OVYRJ9VJr hedA+Qr0h3ENATOWzDNu2bCDoqsesxkUxDPz7kcLf0o25ywwPwoDun8NRouUcJl4y5Tz 25xy4g4yDRpX/YCrTEvm+mp3ByROGtFmSL3oA3U9+iGkkBKn7My/BuH7HydYRF5L0Bg7 LfN1QWUzms0G8VEWUx0SNsogb6/0tNtILfEjgyRVxnl/ScXG/NctZ8bz9EPtUnYaIkDD IjajoGXTdaN8HRpkz0i5brw9bboJCck6nwsJh73rRbEVrBwP9MMadFBkkYTg44xuQq+f AFRQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:arc-authentication-results; bh=Qt6SuAl082TpmDH3pVNGUYn/j6/B1uwW1lo2S3ymx4U=; b=BKfF6JdGwHbba0dY7kBGJee6m9AmIgV7wPvBsGUICfsmd6BPLDEwhpnEL8N4C8FDc2 7kgjopjgy2Mm34rE0m+KzGINcmFzQfhvKqtSu/BpLfkGZDOpoAKhq36hUgh8L68/gqpr mjbGnr2iiX6MEwCztgvd3YNKTH/8UQxGceMHTiqBlssyTWFWxd0Ig/1Fk/cVSgwveIvp lfToPVrGf694bavYydX9CV8lS5TflhSzUP8lNSAL/zsY5xLsex0cXNuxhn3p++z5dyYr m45++E56Ej92reFGcqtkeCTYMcaXz5+gcE9OUpgddBcYs2Y3iCscWHZpDCnThlBr6ktO kghQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id h190si957878pge.13.2018.03.20.02.46.04; Tue, 20 Mar 2018 02:46:05 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752684AbeCTJp7 (ORCPT + 28 others); Tue, 20 Mar 2018 05:45:59 -0400 Received: from foss.arm.com ([217.140.101.70]:37880 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752449AbeCTJoP (ORCPT ); Tue, 20 Mar 2018 05:44:15 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 3B15D15AD; Tue, 20 Mar 2018 02:44:15 -0700 (PDT) Received: from e107985-lin.cambridge.arm.com (e107985-lin.cambridge.arm.com [10.1.210.41]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id B1B7E3F487; Tue, 20 Mar 2018 02:44:12 -0700 (PDT) From: Dietmar Eggemann To: linux-kernel@vger.kernel.org, Peter Zijlstra , Quentin Perret , Thara Gopinath Cc: linux-pm@vger.kernel.org, Morten Rasmussen , Chris Redpath , Patrick Bellasi , Valentin Schneider , "Rafael J . Wysocki" , Greg Kroah-Hartman , Vincent Guittot , Viresh Kumar , Todd Kjos , Joel Fernandes Subject: [RFC PATCH 3/6] sched: Add over-utilization/tipping point indicator Date: Tue, 20 Mar 2018 09:43:09 +0000 Message-Id: <20180320094312.24081-4-dietmar.eggemann@arm.com> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20180320094312.24081-1-dietmar.eggemann@arm.com> References: <20180320094312.24081-1-dietmar.eggemann@arm.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Thara Gopinath Energy-aware scheduling should only operate when the system is not overutilized. There must be cpu time available to place tasks based on utilization in an energy-aware fashion, i.e. to pack tasks on energy-efficient cpus without harming the overall throughput. In case the system operates above this tipping point the tasks have to be placed based on task and cpu load in the classical way of spreading tasks across as many cpus as possible. The point in which a system switches from being not overutilized to being overutilized is called the tipping point. Such a tipping point indicator on a sched domain as the system boundary is introduced here. As soon as one cpu of a sched domain is overutilized the whole sched domain is declared overutilized as well. A cpu becomes overutilized when its utilization is higher that 80% (capacity_margin) of its capacity. The implementation takes advantage of the shared sched domain which is shared across all per-cpu views of a sched domain level. The new overutilized flag is placed in this shared sched domain. Load balancing is skipped in case the energy model is present and the sched domain is not overutilized because under this condition the predominantly load-per-capacity driven load-balancer should not interfere with the energy-aware wakeup placement based on utilization. In case the total utilization of a sched domain is greater than the total sched domain capacity the overutilized flag is set at the parent sched domain level to let other sched groups help getting rid of the overutilization of cpus. Signed-off-by: Thara Gopinath Signed-off-by: Dietmar Eggemann --- include/linux/sched/topology.h | 1 + kernel/sched/fair.c | 64 ++++++++++++++++++++++++++++++++++++++++-- kernel/sched/sched.h | 1 + kernel/sched/topology.c | 12 +++----- 4 files changed, 67 insertions(+), 11 deletions(-) -- 2.11.0 diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h index 26347741ba50..dd001c232646 100644 --- a/include/linux/sched/topology.h +++ b/include/linux/sched/topology.h @@ -72,6 +72,7 @@ struct sched_domain_shared { atomic_t ref; atomic_t nr_busy_cpus; int has_idle_cores; + int overutilized; }; struct sched_domain { diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index bf7b485ddf60..6c72a5e7b1b0 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5197,6 +5197,28 @@ static inline void hrtick_update(struct rq *rq) } #endif +#ifdef CONFIG_SMP +static inline int cpu_overutilized(int cpu); + +static inline int sd_overutilized(struct sched_domain *sd) +{ + return READ_ONCE(sd->shared->overutilized); +} + +static inline void update_overutilized_status(struct rq *rq) +{ + struct sched_domain *sd; + + rcu_read_lock(); + sd = rcu_dereference(rq->sd); + if (sd && !sd_overutilized(sd) && cpu_overutilized(rq->cpu)) + WRITE_ONCE(sd->shared->overutilized, 1); + rcu_read_unlock(); +} +#else +static inline void update_overutilized_status(struct rq *rq) {} +#endif /* CONFIG_SMP */ + /* * The enqueue_task method is called before nr_running is * increased. Here we update the fair scheduling stats and @@ -5246,8 +5268,10 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) update_cfs_group(se); } - if (!se) + if (!se) { add_nr_running(rq, 1); + update_overutilized_status(rq); + } hrtick_update(rq); } @@ -6379,6 +6403,11 @@ static inline int util_fits_capacity(unsigned long util, unsigned long capacity) return capacity * 1024 > util * capacity_margin; } +static inline int cpu_overutilized(int cpu) +{ + return !util_fits_capacity(cpu_util(cpu), capacity_of(cpu)); +} + /* * 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. @@ -7617,6 +7646,7 @@ struct sd_lb_stats { unsigned long total_running; unsigned long total_load; /* Total load of all groups in sd */ unsigned long total_capacity; /* Total capacity of all groups in sd */ + unsigned long total_util; /* Total util of all groups in sd */ unsigned long avg_load; /* Average load across all groups in sd */ struct sg_lb_stats busiest_stat;/* Statistics of the busiest group */ @@ -7637,6 +7667,7 @@ static inline void init_sd_lb_stats(struct sd_lb_stats *sds) .total_running = 0UL, .total_load = 0UL, .total_capacity = 0UL, + .total_util = 0UL, .busiest_stat = { .avg_load = 0UL, .sum_nr_running = 0, @@ -7933,11 +7964,12 @@ static bool update_nohz_stats(struct rq *rq, bool force) * @local_group: Does group contain this_cpu. * @sgs: variable to hold the statistics for this group. * @overload: Indicate more than one runnable task for any CPU. + * @overutilized: Indicate overutilization for any CPU. */ static inline void update_sg_lb_stats(struct lb_env *env, struct sched_group *group, int load_idx, int local_group, struct sg_lb_stats *sgs, - bool *overload) + bool *overload, int *overutilized) { unsigned long load; int i, nr_running; @@ -7974,6 +8006,9 @@ static inline void update_sg_lb_stats(struct lb_env *env, */ if (!nr_running && idle_cpu(i)) sgs->idle_cpus++; + + if (cpu_overutilized(i)) + *overutilized = 1; } /* Adjust by relative CPU capacity of the group */ @@ -8101,6 +8136,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd struct sg_lb_stats tmp_sgs; int load_idx, prefer_sibling = 0; bool overload = false; + int overutilized = 0; if (child && child->flags & SD_PREFER_SIBLING) prefer_sibling = 1; @@ -8127,7 +8163,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd } update_sg_lb_stats(env, sg, load_idx, local_group, sgs, - &overload); + &overload, &overutilized); if (local_group) goto next_group; @@ -8159,6 +8195,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd sds->total_running += sgs->sum_nr_running; sds->total_load += sgs->group_load; sds->total_capacity += sgs->group_capacity; + sds->total_util += sgs->group_util; sg = sg->next; } while (sg != env->sd->groups); @@ -8180,6 +8217,17 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd if (env->dst_rq->rd->overload != overload) env->dst_rq->rd->overload = overload; } + + if (READ_ONCE(env->sd->shared->overutilized) != overutilized) + WRITE_ONCE(env->sd->shared->overutilized, overutilized); + + /* + * If the domain util is greater that domain capacity, load balancing + * needs to be done at the next sched domain level as well. + */ + if (env->sd->parent && + !util_fits_capacity(sds->total_util, sds->total_capacity)) + WRITE_ONCE(env->sd->parent->shared->overutilized, 1); } /** @@ -9055,6 +9103,10 @@ static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle) } max_cost += sd->max_newidle_lb_cost; + if (static_branch_unlikely(&sched_energy_present) && + !sd_overutilized(sd)) + continue; + if (!(sd->flags & SD_LOAD_BALANCE)) continue; @@ -9622,6 +9674,10 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf) break; } + if (static_branch_unlikely(&sched_energy_present) && + !sd_overutilized(sd)) + continue; + if (sd->flags & SD_BALANCE_NEWIDLE) { t0 = sched_clock_cpu(this_cpu); @@ -9755,6 +9811,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_overutilized_status(rq); } /* diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index 22909ffc04fb..55ec6a4c4712 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -11,6 +11,7 @@ #include #include #include +#include #include #include #include diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c index 64cc564f5255..c8b7c7665ab2 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -1184,15 +1184,11 @@ sd_init(struct sched_domain_topology_level *tl, sd->idle_idx = 1; } - /* - * For all levels sharing cache; connect a sched_domain_shared - * instance. - */ - if (sd->flags & SD_SHARE_PKG_RESOURCES) { - sd->shared = *per_cpu_ptr(sdd->sds, sd_id); - atomic_inc(&sd->shared->ref); + sd->shared = *per_cpu_ptr(sdd->sds, sd_id); + atomic_inc(&sd->shared->ref); + + if (sd->flags & SD_SHARE_PKG_RESOURCES) atomic_set(&sd->shared->nr_busy_cpus, sd_weight); - } sd->private = sdd;