From patchwork Thu Dec 3 14:11:15 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mel Gorman X-Patchwork-Id: 11948949 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-18.2 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED, USER_AGENT_GIT autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id C0FDEC43211 for ; Thu, 3 Dec 2020 14:13:29 +0000 (UTC) Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 56F1B20705 for ; Thu, 3 Dec 2020 14:13:29 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 56F1B20705 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=techsingularity.net Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=merlin.20170209; h=Sender:Content-Transfer-Encoding: Content-Type:Cc:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To:Message-Id:Date: Subject:To:From:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=e625aBYYoF6f0hO0ac6Iil8TVpBUh36qEXUyEFdaUSM=; b=toZOTSHofTkqjxabkS7XMVKLR JExnFpYZ7zVOT03mjXQkGCOxHYuQsIuE4Oh/IYuWApiMnodUrhKK1l6su61k1Vc1REdDdnB2H0TXZ jb52ze5nK06aEczDixIBCuJDG0HOCFe/sbDvLAFFg35bgETMR0Lynn3McpGaCubvsRgnNTrnljtON 8woKMiGVelHY/adtSIkoteqEIhbbBMAnv64+azlpkAsBkElJYc2qREUqGo/+89vqyVxiHGZwyqywj nELoRJQQT0Kc2wzfUL3K827cXyu+FwOCxuDAu4JZIRYSbPENfgvjJiCcZfi93FmaYdcx4edBOz+gM cPtSgSxDw==; Received: from localhost ([::1] helo=merlin.infradead.org) by merlin.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1kkpKv-0003rh-JZ; Thu, 03 Dec 2020 14:11:57 +0000 Received: from casper.infradead.org ([2001:8b0:10b:1236::1]) by merlin.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1kkpKZ-0003ly-Ah for linux-arm-kernel@merlin.infradead.org; Thu, 03 Dec 2020 14:11:35 +0000 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=Content-Transfer-Encoding:MIME-Version: References:In-Reply-To:Message-Id:Date:Subject:Cc:To:From:Sender:Reply-To: Content-Type:Content-ID:Content-Description; bh=0QZAHnSLXr8NA84NYT7K190k0jIimN150iWEiUbF3ko=; b=Q4bKGaAC9YCAJVE7Eq4w1ImKFV fMCeNq8GhumDpsqmxJFJ1XitkgkuTJdE5oCWIzkuV6cmMl+v3jkYaL84xTo9Q5CVa6WEDcfOUFpzy EEAuUovrGZoTqBhxXx2ZwWkWAJUyrRIHcT8VQgJ1Cf9Za7i9qr5sPCf/rwbMS2q3IcY/bUODtsgAO NVh0HDP03JFYXfjpt5uTG2jbq7BBusJIfw3Q56+D4cxLHPa4mC1BOBtRGnQI6Rqn/I7pVMAmUPhJ6 tFfWmJxlar3yiXJrOk5tMgmb4+fbHE7dyfuEUuQ2eGWcPNwRma9nz4PZOnCeTDXv5aYKTcc5rgQ/O DFOpj+AQ==; Received: from outbound-smtp54.blacknight.com ([46.22.136.238]) by casper.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1kkpKT-0005fL-Ue for linux-arm-kernel@lists.infradead.org; Thu, 03 Dec 2020 14:11:34 +0000 Received: from mail.blacknight.com (pemlinmail03.blacknight.ie [81.17.254.16]) by outbound-smtp54.blacknight.com (Postfix) with ESMTPS id F309EFA8F1 for ; Thu, 3 Dec 2020 14:11:24 +0000 (GMT) Received: (qmail 22661 invoked from network); 3 Dec 2020 14:11:24 -0000 Received: from unknown (HELO stampy.112glenside.lan) (mgorman@techsingularity.net@[84.203.22.4]) by 81.17.254.9 with ESMTPA; 3 Dec 2020 14:11:24 -0000 From: Mel Gorman To: LKML Subject: [PATCH 01/10] sched/fair: Track efficiency of select_idle_sibling Date: Thu, 3 Dec 2020 14:11:15 +0000 Message-Id: <20201203141124.7391-2-mgorman@techsingularity.net> X-Mailer: git-send-email 2.26.2 In-Reply-To: <20201203141124.7391-1-mgorman@techsingularity.net> References: <20201203141124.7391-1-mgorman@techsingularity.net> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20201203_141130_292324_8A4D1AE6 X-CRM114-Status: GOOD ( 19.09 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Barry Song , Juri Lelli , Vincent Guittot , Peter Ziljstra , Aubrey Li , Ingo Molnar , Mel Gorman , Valentin Schneider , Linux-ARM Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org select_idle_sibling is an important path that finds a nearby idle CPU on wakeup. As it is examining other CPUs state, it can be expensive in terms of cache usage. This patch tracks the search efficiency if schedstats are enabled. In general, this is only useful for kernel developers but schedstats are typically disabled by default so it is convenient for development and mostly free otherwise. It is not required that this patch be merged with the series but if we are looking at time or search complexity, the stats generate hard data on what the search costs actually are. SIS Search: Number of calls to select_idle_sibling SIS Domain Search: Number of times the domain was searched because the fast path failed. SIS Scanned: Generally the number of runqueues scanned but the fast path counts as 1 regardless of the values for target, prev and recent. SIS Domain Scanned: Number of runqueues scanned during a search of the LLC domain. SIS Failures: Number of SIS calls that failed to find an idle CPU SIS Search Efficiency: A ratio expressed as a percentage of runqueues scanned versus idle CPUs found. A 100% efficiency indicates that the target, prev or recent CPU of a task was idle at wakeup. The lower the efficiency, the more runqueues were scanned before an idle CPU was found. SIS Domain Search Efficiency: Similar, except only for the slower SIS patch. SIS Fast Success Rate: Percentage of SIS that used target, prev or recent CPUs. SIS Success rate: Percentage of scans that found an idle CPU. Signed-off-by: Mel Gorman --- kernel/sched/debug.c | 4 ++++ kernel/sched/fair.c | 14 ++++++++++++++ kernel/sched/sched.h | 6 ++++++ kernel/sched/stats.c | 8 +++++--- 4 files changed, 29 insertions(+), 3 deletions(-) diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c index 2357921580f9..2386cc5e79e5 100644 --- a/kernel/sched/debug.c +++ b/kernel/sched/debug.c @@ -714,6 +714,10 @@ do { \ P(sched_goidle); P(ttwu_count); P(ttwu_local); + P(sis_search); + P(sis_domain_search); + P(sis_scanned); + P(sis_failed); } #undef P diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 98075f9ea9a8..494ba01f3414 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6081,6 +6081,7 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, int bool idle = true; for_each_cpu(cpu, cpu_smt_mask(core)) { + schedstat_inc(this_rq()->sis_scanned); if (!available_idle_cpu(cpu)) { idle = false; break; @@ -6112,6 +6113,7 @@ static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int t return -1; for_each_cpu(cpu, cpu_smt_mask(target)) { + schedstat_inc(this_rq()->sis_scanned); if (!cpumask_test_cpu(cpu, p->cpus_ptr) || !cpumask_test_cpu(cpu, sched_domain_span(sd))) continue; @@ -6177,6 +6179,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr); for_each_cpu_wrap(cpu, cpus, target) { + schedstat_inc(this_rq()->sis_scanned); if (!--nr) return -1; if (available_idle_cpu(cpu) || sched_idle_cpu(cpu)) @@ -6240,6 +6243,15 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target) unsigned long task_util; int i, recent_used_cpu; + schedstat_inc(this_rq()->sis_search); + + /* + * Checking if prev, target and recent is treated as one scan. A + * perfect hit on one of those is considered 100% efficiency. + * Further scanning impairs efficiency. + */ + schedstat_inc(this_rq()->sis_scanned); + /* * On asymmetric system, update task utilization because we will check * that the task fits with cpu's capacity. @@ -6315,6 +6327,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target) if (!sd) return target; + schedstat_inc(this_rq()->sis_domain_search); i = select_idle_core(p, sd, target); if ((unsigned)i < nr_cpumask_bits) return i; @@ -6327,6 +6340,7 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target) if ((unsigned)i < nr_cpumask_bits) return i; + schedstat_inc(this_rq()->sis_failed); return target; } diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index f5acb6c5ce49..90a62dd9293d 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -1049,6 +1049,12 @@ struct rq { /* try_to_wake_up() stats */ unsigned int ttwu_count; unsigned int ttwu_local; + + /* select_idle_sibling stats */ + unsigned int sis_search; + unsigned int sis_domain_search; + unsigned int sis_scanned; + unsigned int sis_failed; #endif #ifdef CONFIG_CPU_IDLE diff --git a/kernel/sched/stats.c b/kernel/sched/stats.c index 750fb3c67eed..390bfcc3842c 100644 --- a/kernel/sched/stats.c +++ b/kernel/sched/stats.c @@ -10,7 +10,7 @@ * Bump this up when changing the output format or the meaning of an existing * format, so that tools can adapt (or abort) */ -#define SCHEDSTAT_VERSION 15 +#define SCHEDSTAT_VERSION 16 static int show_schedstat(struct seq_file *seq, void *v) { @@ -30,12 +30,14 @@ static int show_schedstat(struct seq_file *seq, void *v) /* runqueue-specific stats */ seq_printf(seq, - "cpu%d %u 0 %u %u %u %u %llu %llu %lu", + "cpu%d %u 0 %u %u %u %u %llu %llu %lu %u %u %u %u", cpu, rq->yld_count, rq->sched_count, rq->sched_goidle, rq->ttwu_count, rq->ttwu_local, rq->rq_cpu_time, - rq->rq_sched_info.run_delay, rq->rq_sched_info.pcount); + rq->rq_sched_info.run_delay, rq->rq_sched_info.pcount, + rq->sis_search, rq->sis_domain_search, + rq->sis_scanned, rq->sis_failed); seq_printf(seq, "\n");