Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Chen Yu <yu.c.chen@intel.com>
To:     linux-kernel@vger.kernel.org
Cc:     Tim Chen <tim.c.chen@intel.com>,
        Peter Zijlstra <peterz@infradead.org>,
        Ingo Molnar <mingo@redhat.com>,
        Juri Lelli <juri.lelli@redhat.com>,
        Vincent Guittot <vincent.guittot@linaro.org>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Mel Gorman <mgorman@suse.de>,
        Viresh Kumar <viresh.kumar@linaro.org>,
        Barry Song <21cnbao@gmail.com>,
        Barry Song <song.bao.hua@hisilicon.com>,
        Yicong Yang <yangyicong@hisilicon.com>,
        Srikar Dronamraju <srikar@linux.vnet.ibm.com>,
        Len Brown <len.brown@intel.com>,
        Ben Segall <bsegall@google.com>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Aubrey Li <aubrey.li@intel.com>, Chen Yu <yu.c.chen@intel.com>,
        K Prateek Nayak <kprateek.nayak@amd.com>
Subject: [PATCH v2][RFC] sched/fair: Change SIS_PROP to search idle CPU based on sum of util_avg
Date:   Thu, 10 Mar 2022 08:52:28 +0800
Message-Id: <20220310005228.11737-1-yu.c.chen@intel.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

[Problem Statement]
Currently select_idle_cpu() uses the percpu average idle time to
estimate the total LLC domain idle time, and calculate the number
of CPUs to be scanned. This might be inconsistent because idle time
of a CPU does not necessarily correlate with idle time of a domain.
As a result, the load could be underestimated and causes over searching
when the system is very busy.

The following histogram is the time spent in select_idle_cpu(),
when running 224 instance of netperf on a system with 112 CPUs
per LLC domain:

@usecs:
[0]                  533 |                                                    |
[1]                 5495 |                                                    |
[2, 4)             12008 |                                                    |
[4, 8)            239252 |                                                    |
[8, 16)          4041924 |@@@@@@@@@@@@@@                                      |
[16, 32)        12357398 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@         |
[32, 64)        14820255 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[64, 128)       13047682 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@       |
[128, 256)       8235013 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@                        |
[256, 512)       4507667 |@@@@@@@@@@@@@@@                                     |
[512, 1K)        2600472 |@@@@@@@@@                                           |
[1K, 2K)          927912 |@@@                                                 |
[2K, 4K)          218720 |                                                    |
[4K, 8K)           98161 |                                                    |
[8K, 16K)          37722 |                                                    |
[16K, 32K)          6715 |                                                    |
[32K, 64K)           477 |                                                    |
[64K, 128K)            7 |                                                    |

netperf latency:
=======
case            	load    	    Lat_99th	    std%
TCP_RR          	thread-224	      257.39	(  0.21)
UDP_RR          	thread-224	      242.83	(  6.29)

The netperf 99th latency(usec) above is comparable with the time spent in
select_idle_cpu(). That is to say, when the system is overloaded, searching
for idle CPU could be a bottleneck.

[Proposal]
The main idea is to replace percpu average idle time with the domain
based metric. Choose average CPU utilization(util_avg) as the candidate.
In general, the number of CPUs to be scanned should be inversely
proportional to the sum of util_avg in this domain. That is, the lower
the util_avg is, the more select_idle_cpu() should scan for idle CPU,
and vice versa. The benefit of choosing util_avg is that, it is a metric
of accumulated historic activity, which seems to be more accurate than
instantaneous metrics(such as rq->nr_running).

Furthermore, borrow the util_avg from periodic load balance,
which could offload the overhead of select_idle_cpu().

According to last discussion[1], introduced the linear function
for experimental purpose:

f(x) = a - bx

     llc_size
x = \Sum      util_avg[cpu] / llc_cpu_capacity
     1
f(x) is the number of CPUs to be scanned, x is the sum util_avg.
To decide a and b, the following condition should be met:

[1] f(0) = llc_size
[2] f(x) = 4,  x >= 50%

That is to say, when the util_avg is 0, we should search for
the whole LLC domain. And if util_avg ratio reaches 50% or higher,
it should search at most 4 CPUs.

Yes, there would be questions like:
Why using this linear function to calculate the number of CPUs to
be scanned? Why choosing 50% as the threshold? These questions will
be discussed in the [Limitations] section.

[Benchmark]
netperf, hackbench, schbench, tbench
were tested with 25% 50% 75% 100% 125% 150% 175% 200% instance
of CPU number (these ratios are not CPU utilization). Each test lasts
for 100 seconds, and repeats 3 times. The system would reboot into a
fresh environment for each benchmark.

The following is the benchmark result comparison between
baseline:vanilla and compare:patched kernel. Positive compare%
indicates better performance.

netperf
=======
case            	load    	baseline(std%)	compare%( std%)
TCP_RR          	28 threads	 1.00 (  0.30)	 -1.26 (  0.32)
TCP_RR          	56 threads	 1.00 (  0.35)	 -1.26 (  0.41)
TCP_RR          	84 threads	 1.00 (  0.46)	 -0.15 (  0.60)
TCP_RR          	112 threads	 1.00 (  0.36)	 +0.44 (  0.41)
TCP_RR          	140 threads	 1.00 (  0.23)	 +0.95 (  0.21)
TCP_RR          	168 threads	 1.00 (  0.20)	+177.77 (  3.78)
TCP_RR          	196 threads	 1.00 (  0.18)	+185.43 ( 10.08)
TCP_RR          	224 threads	 1.00 (  0.16)	+187.86 (  7.32)
UDP_RR          	28 threads	 1.00 (  0.43)	 -0.93 (  0.27)
UDP_RR          	56 threads	 1.00 (  0.17)	 -0.39 ( 10.91)
UDP_RR          	84 threads	 1.00 (  6.36)	 +1.03 (  0.92)
UDP_RR          	112 threads	 1.00 (  5.55)	 +1.47 ( 17.67)
UDP_RR          	140 threads	 1.00 ( 18.17)	 +0.31 ( 15.48)
UDP_RR          	168 threads	 1.00 ( 15.00)	+153.87 ( 13.20)
UDP_RR          	196 threads	 1.00 ( 16.26)	+169.19 ( 13.78)
UDP_RR          	224 threads	 1.00 ( 51.81)	+76.72 ( 10.95)

hackbench
=========
(each group has 1/4 * 112 tasks)
case            	load    	baseline(std%)	compare%( std%)
process-pipe    	1 group 	 1.00 (  0.47)	 -0.46 (  0.16)
process-pipe    	2 groups 	 1.00 (  0.42)	 -0.61 (  0.74)
process-pipe    	3 groups 	 1.00 (  0.42)	 +0.38 (  0.20)
process-pipe    	4 groups 	 1.00 (  0.15)	 -0.36 (  0.56)
process-pipe    	5 groups 	 1.00 (  0.20)	 -5.08 (  0.01)
process-pipe    	6 groups 	 1.00 (  0.28)	 -2.98 (  0.29)
process-pipe    	7 groups 	 1.00 (  0.08)	 -1.18 (  0.28)
process-pipe    	8 groups 	 1.00 (  0.11)	 -0.40 (  0.07)
process-sockets 	1 group 	 1.00 (  0.43)	 -1.93 (  0.58)
process-sockets 	2 groups 	 1.00 (  0.23)	 -1.10 (  0.49)
process-sockets 	3 groups 	 1.00 (  1.10)	 -0.96 (  1.12)
process-sockets 	4 groups 	 1.00 (  0.59)	 -0.08 (  0.88)
process-sockets 	5 groups 	 1.00 (  0.45)	 +0.31 (  0.34)
process-sockets 	6 groups 	 1.00 (  0.23)	 +0.06 (  0.66)
process-sockets 	7 groups 	 1.00 (  0.12)	 +1.72 (  0.20)
process-sockets 	8 groups 	 1.00 (  0.11)	 +1.98 (  0.02)
threads-pipe    	1 group 	 1.00 (  1.07)	 +0.03 (  0.40)
threads-pipe    	2 groups 	 1.00 (  1.05)	 +0.19 (  1.27)
threads-pipe    	3 groups 	 1.00 (  0.32)	 -0.42 (  0.48)
threads-pipe    	4 groups 	 1.00 (  0.42)	 -0.76 (  0.79)
threads-pipe    	5 groups 	 1.00 (  0.19)	 -4.97 (  0.07)
threads-pipe    	6 groups 	 1.00 (  0.05)	 -4.11 (  0.04)
threads-pipe    	7 groups 	 1.00 (  0.10)	 -1.13 (  0.16)
threads-pipe    	8 groups 	 1.00 (  0.03)	 -0.08 (  0.05)
threads-sockets 	1 group 	 1.00 (  0.33)	 -1.93 (  0.69)
threads-sockets 	2 groups 	 1.00 (  0.20)	 -1.55 (  0.30)
threads-sockets 	3 groups 	 1.00 (  0.37)	 -1.29 (  0.59)
threads-sockets 	4 groups 	 1.00 (  1.83)	 +0.31 (  1.17)
threads-sockets 	5 groups 	 1.00 (  0.28)	+15.73 (  0.24)
threads-sockets 	6 groups 	 1.00 (  0.15)	 +5.02 (  0.34)
threads-sockets 	7 groups 	 1.00 (  0.10)	 +2.29 (  0.14)
threads-sockets 	8 groups 	 1.00 (  0.17)	 +2.22 (  0.12)

tbench
======
case            	load    	baseline(std%)	compare%( std%)
loopback        	28 threads	 1.00 (  0.05)	 -1.39 (  0.04)
loopback        	56 threads	 1.00 (  0.08)	 -0.37 (  0.04)
loopback        	84 threads	 1.00 (  0.03)	 +0.20 (  0.13)
loopback        	112 threads	 1.00 (  0.04)	 +0.69 (  0.04)
loopback        	140 threads	 1.00 (  0.13)	 +1.15 (  0.21)
loopback        	168 threads	 1.00 (  0.03)	 +1.62 (  0.08)
loopback        	196 threads	 1.00 (  0.08)	 +1.50 (  0.30)
loopback        	224 threads	 1.00 (  0.05)	 +1.62 (  0.05)

schbench
========
(each mthread group has 1/4 * 112 tasks)
case            	load    	baseline(std%)	compare%( std%)
normal          	1 mthread group	 1.00 ( 17.92)	+19.23 ( 23.67)
normal          	2 mthread groups 1.00 ( 21.10)	 +8.32 ( 16.92)
normal          	3 mthread groups 1.00 ( 10.80)	+10.03 (  9.21)
normal          	4 mthread groups 1.00 (  2.67)	 +0.11 (  3.00)
normal          	5 mthread groups 1.00 (  0.08)	 +0.00 (  0.13)
normal          	6 mthread groups 1.00 (  2.99)	 -2.66 (  3.87)
normal          	7 mthread groups 1.00 (  2.16)	 -0.83 (  2.24)
normal          	8 mthread groups 1.00 (  1.75)	 +0.18 (  3.18)

According to the results above, when the workloads is heavy, the throughput
of netperf improves a lot. It might be interesting to look into the reason
why this patch benefits netperf significantly. Further investigation has
shown that, this might be a 'side effect' of this patch. It is found that,
the CPU utilization is around 90% on vanilla kernel, while it is nearly
100% on patched kernel. According to the perf profile, with the patch
applied, the scheduler would likely to choose previous running CPU for the
waking task, thus reduces runqueue lock contention, so the CPU utilization
is higher and get better performance.

[Limitations]
Q:Why using 50% as the util_avg/capacity threshold to search at most 4 CPUs?

A: 50% is chosen as that corresponds to almost full CPU utilization, when
   the CPU is fixed to run at its base frequency, with turbo enabled.
   4 is the minimal number of CPUs to be scanned in current select_idle_cpu().

   A synthetic workload was used to simulate different level of
   load. This workload takes every 10ms as the sample period, and in
   each sample period:

   while (!timeout_10ms) {
        loop(busy_pct_ms);
   	sleep(10ms-busy_pct_ms)
   }

   to simulate busy_pct% of CPU utilization. When the workload is
   running, the percpu runqueue util_avg was monitored. The
   following is the result from turbostat's Busy% on CPU2 and
   cfs_rq[2].util_avg from /sys/kernel/debug/sched/debug:

   Busy%    util_avg   util_avg/cpu_capacity%
   10.06    35         3.42
   19.97    99         9.67
   29.93    154        15.04
   39.86    213        20.80
   49.79    256        25.00
   59.73    325        31.74
   69.77    437        42.68
   79.69    458        44.73
   89.62    519        50.68
   99.54    598        58.39

   The reason why util_avg ratio is not consistent with Busy% might be due
   to CPU frequency invariance. The CPU is running at fixed lower frequency
   than the turbo frequency, then the util_avg scales lower than
   SCHED_CAPACITY_SCALE. In our test platform, the base frequency is 1.9GHz,
   and the max turbo frequency is 3.7GHz, so 1.9/3.7 is around 50%.
   In the future maybe we could use arch_scale_freq_capacity()
   instead of sds->total_capacity, so as to remove the impact from frequency.
   Then the 50% could be adjusted higher. For now, 50% is an aggressive
   threshold to restric the idle CPU searching and shows benchmark
   improvement.

Q: Why using nr_scan = a - b * sum_util_avg to do linear search?

A: Ideally the nr_scan could be:

   nr_scan = sum_util_avg / pelt_avg_scan_cost

   However consider the overhead of calculating pelt on avg_scan_cost
   in each wake up, choosing heuristic search for evaluation seems to
   be an acceptable trade-off.

   The f(sum_util_avg) could be of any form, as long as it is a monotonically
   decreasing function. At first f(x) = a - 2^(bx) was chosen. Because when the
   sum_util_avg is low, the system should try very hard to find an idle CPU. And
   if sum_util_avg goes higher, the system dramatically lose its interest to search
   for the idle CPU. But exponential function does have its drawback:

   Consider a system with 112 CPUs, let f(x) =  112 when x = 0,
   f(x) = 4 when x = 50, x belongs to [0, 100], then we have:

   f1(x) = 113 - 2^(x / 7.35)
   and
   f2(x) = 112 - 2.16 * x

   Since kernel does not support floating point, above functions are converted into:
   nr_scan1(x) = 113 - 2^(x / 7)
   and
   nr_scan2(x) = 112 - 2 * x

   util_avg%      0     1     2  ...   8     9   ... 47   48   49
   nr_scan1     112   112   112      111   111       49   49    4
   nr_scan2     112   110   108       96    94       18   16   14

   According to above result, the granularity of exponential function
   is coarse-grained, while the linear function is fine-grained.

   So finally choose linear function. After all, it has shown benchmark
   benefit without noticeable regression so far.

Q: How to deal with the following corner case:

   It is possible that there is unbalanced tasks among CPUs due to CPU affinity.
   For example, suppose the LLC domain is composed of 6 CPUs, and 5 tasks are bound
   to CPU0~CPU4, while CPU5 is idle:

		CPU0	CPU1	CPU2	CPU3	CPU4	CPU5
   util_avg	1024	1024	1024	1024	1024	0

   Since the util_avg ratio is 83%( = 5/6 ), which is higher than 50%, select_idle_cpu()
   only searches 4 CPUs starting from CPU0, thus leaves idle CPU5 undetected.

   A possible workaround to mitigate this problem is that, the nr_scan should
   be increased by the number of idle CPUs found during periodic load balance
   in update_sd_lb_stats(). In above example, the nr_scan will be adjusted to
   4 + 1 = 5. Currently I don't have better solution in mind to deal with it
   gracefully.

Any comment is appreciated.

Link: https://lore.kernel.org/lkml/20220207135253.GF23216@worktop.programming.kicks-ass.net/ # [1]
Suggested-by: Tim Chen <tim.c.chen@intel.com>
Suggested-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Chen Yu <yu.c.chen@intel.com>
---
 include/linux/sched/topology.h |   1 +
 kernel/sched/fair.c            | 107 +++++++++++++++++++--------------
 2 files changed, 63 insertions(+), 45 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index 8054641c0a7b..aae558459f00 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -81,6 +81,7 @@ struct sched_domain_shared {
 	atomic_t	ref;
 	atomic_t	nr_busy_cpus;
 	int		has_idle_cores;
+	int		nr_idle_scan;
 };
 
 struct sched_domain {
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 5146163bfabb..59f5f8432c21 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6271,43 +6271,14 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
 {
 	struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_idle_mask);
 	int i, cpu, idle_cpu = -1, nr = INT_MAX;
-	struct rq *this_rq = this_rq();
-	int this = smp_processor_id();
-	struct sched_domain *this_sd;
-	u64 time = 0;
-
-	this_sd = rcu_dereference(*this_cpu_ptr(&sd_llc));
-	if (!this_sd)
-		return -1;
+	struct sched_domain_shared *sd_share;
 
 	cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
 
 	if (sched_feat(SIS_PROP) && !has_idle_core) {
-		u64 avg_cost, avg_idle, span_avg;
-		unsigned long now = jiffies;
-
-		/*
-		 * If we're busy, the assumption that the last idle period
-		 * predicts the future is flawed; age away the remaining
-		 * predicted idle time.
-		 */
-		if (unlikely(this_rq->wake_stamp < now)) {
-			while (this_rq->wake_stamp < now && this_rq->wake_avg_idle) {
-				this_rq->wake_stamp++;
-				this_rq->wake_avg_idle >>= 1;
-			}
-		}
-
-		avg_idle = this_rq->wake_avg_idle;
-		avg_cost = this_sd->avg_scan_cost + 1;
-
-		span_avg = sd->span_weight * avg_idle;
-		if (span_avg > 4*avg_cost)
-			nr = div_u64(span_avg, avg_cost);
-		else
-			nr = 4;
-
-		time = cpu_clock(this);
+		sd_share = rcu_dereference(per_cpu(sd_llc_shared, target));
+		if (sd_share)
+			nr = READ_ONCE(sd_share->nr_idle_scan);
 	}
 
 	for_each_cpu_wrap(cpu, cpus, target + 1) {
@@ -6328,18 +6299,6 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
 	if (has_idle_core)
 		set_idle_cores(target, false);
 
-	if (sched_feat(SIS_PROP) && !has_idle_core) {
-		time = cpu_clock(this) - time;
-
-		/*
-		 * Account for the scan cost of wakeups against the average
-		 * idle time.
-		 */
-		this_rq->wake_avg_idle -= min(this_rq->wake_avg_idle, time);
-
-		update_avg(&this_sd->avg_scan_cost, time);
-	}
-
 	return idle_cpu;
 }
 
@@ -9199,6 +9158,60 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu)
 	return idlest;
 }
 
+static inline void update_nr_idle_scan(struct lb_env *env, struct sd_lb_stats *sds,
+				       unsigned long sum_util)
+{
+	struct sched_domain_shared *sd_share;
+	int llc_size = per_cpu(sd_llc_size, env->dst_cpu);
+	int nr_scan;
+
+	/*
+	 * Update the number of CPUs to scan in LLC domain, which could
+	 * be used as a hint in select_idle_cpu(). The update of this hint
+	 * occurs during periodic load balancing, rather than frequent
+	 * newidle balance.
+	 */
+	if (env->idle == CPU_NEWLY_IDLE || env->sd->span_weight != llc_size)
+		return;
+
+	sd_share = rcu_dereference(per_cpu(sd_llc_shared, env->dst_cpu));
+	if (!sd_share)
+		return;
+
+	/*
+	 * In general, the number of cpus to be scanned should be
+	 * inversely proportional to the sum_util. That is, the lower
+	 * the sum_util is, the harder select_idle_cpu() should scan
+	 * for idle CPU, and vice versa. Let x be the sum_util ratio
+	 * [0-100] of the LLC domain, f(x) be the number of CPUs scanned:
+	 *
+	 * f(x) = a - bx                                              [1]
+	 *
+	 * Consider that f(x) = nr_llc when x = 0, and f(x) = 4 when
+	 * x >= threshold('h' below) then:
+	 *
+	 * a = llc_size;
+	 * b = (nr_llc - 4) / h                                       [2]
+	 *
+	 * then [2] becomes:
+	 *
+	 * f(x) = llc_size - (llc_size -4)x/h                         [3]
+	 *
+	 * Choose 50 (50%) for h as the threshold from experiment result.
+	 * And since x = 100 * sum_util / total_cap, [3] becomes:
+	 *
+	 * f(sum_util)
+	 *  = llc_size - (llc_size - 4) * 100 * sum_util / total_cap * 50
+	 *  = llc_size - (llc_size - 4) * 2 * sum_util / total_cap
+	 *
+	 */
+	nr_scan = llc_size - (llc_size - 4) * 2 * sum_util / sds->total_capacity;
+	if (nr_scan < 4)
+		nr_scan = 4;
+
+	WRITE_ONCE(sd_share->nr_idle_scan, nr_scan);
+}
+
 /**
  * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
  * @env: The load balancing environment.
@@ -9212,6 +9225,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 	struct sg_lb_stats *local = &sds->local_stat;
 	struct sg_lb_stats tmp_sgs;
 	int sg_status = 0;
+	unsigned long sum_util = 0;
 
 	do {
 		struct sg_lb_stats *sgs = &tmp_sgs;
@@ -9242,6 +9256,7 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 		/* Now, start updating sd_lb_stats */
 		sds->total_load += sgs->group_load;
 		sds->total_capacity += sgs->group_capacity;
+		sum_util += sgs->group_util;
 
 		sg = sg->next;
 	} while (sg != env->sd->groups);
@@ -9268,6 +9283,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
 		WRITE_ONCE(rd->overutilized, SG_OVERUTILIZED);
 		trace_sched_overutilized_tp(rd, SG_OVERUTILIZED);
 	}
+
+	update_nr_idle_scan(env, sds, sum_util);
 }
 
 #define NUMA_IMBALANCE_MIN 2
-- 
2.25.1