[PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[Abel Wu]

Now when updating core state, there are two main problems that could
pollute the SIS filter:

  - The updating is before task migration, so if dst_cpu is
    selected to be propagated which might be fed with tasks
    soon, the efforts we paid is no more than setting a busy
    cpu into the SIS filter. While on the other hand it is
    important that we update as early as possible to keep the
    filter fresh, so it's not wise to delay the update to the
    end of load balancing.

  - False negative propagation hurts performance since some
    idle cpus could be out of reach. So in general we will
    aggressively propagate idle cpus but allow false positive
    continue to exist for a while, which may lead to filter
    being fully polluted.

Pains can be relieved by a force correction when false positive
continuously detected.

Signed-off-by: Abel Wu <wuyun.abel@bytedance.com>
---
 include/linux/sched/topology.h |  7 +++++
 kernel/sched/fair.c            | 51 ++++++++++++++++++++++++++++++++--
 2 files changed, 55 insertions(+), 3 deletions(-)

diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index b93edf587d84..e3552ce192a9 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -91,6 +91,12 @@ struct sched_group;
  *	search, and is also used as a fallback state of the other
  *	states.
  *
+ * - sd_may_idle
+ *	This state implies the unstableness of the SIS filter, and
+ *	some bits of it may out of date. This state is only used in
+ *	SMT domains as an intermediate state between sd_has_icpus
+ *	and sd_is_busy.
+ *
  * - sd_is_busy
  *	This state indicates there are no unoccupied cpus in this
  *	domain. So for LLC domains, it gives the hint on whether
@@ -111,6 +117,7 @@ struct sched_group;
 enum sd_state {
 	sd_has_icores,
 	sd_has_icpus,
+	sd_may_idle,
 	sd_is_busy
 };
 
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d55fdcedf2c0..9713d183d35e 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8768,6 +8768,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 
 	for_each_cpu_and(i, sched_group_span(group), env->cpus) {
 		struct rq *rq = cpu_rq(i);
+		bool update = update_core && (env->dst_cpu != i);
 
 		sgs->group_load += cpu_load(rq);
 		sgs->group_util += cpu_util_cfs(i);
@@ -8777,7 +8778,11 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 		nr_running = rq->nr_running;
 		sgs->sum_nr_running += nr_running;
 
-		if (update_core)
+		/*
+		 * The dst_cpu is not preferred since it might
+		 * be fed with tasks soon.
+		 */
+		if (update)
 			sd_classify(sds, rq, i);
 
 		if (nr_running > 1)
@@ -8801,7 +8806,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 			 * and fed with tasks, so we'd better choose
 			 * a candidate in an opposite way.
 			 */
-			sds->idle_cpu = i;
+			if (update)
+				sds->idle_cpu = i;
 			sgs->idle_cpus++;
 
 			/* Idle cpu can't have misfit task */
@@ -9321,7 +9327,7 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
 {
 	struct sched_domain_shared *sd_smt_shared = env->sd->shared;
 	enum sd_state new = sds->sd_state;
-	int this = env->dst_cpu;
+	int icpu = sds->idle_cpu, this = env->dst_cpu;
 
 	/*
 	 * Parallel updating can hardly contribute accuracy to
@@ -9331,6 +9337,22 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
 	if (cmpxchg(&sd_smt_shared->updating, 0, 1))
 		return;
 
+	/*
+	 * The dst_cpu is likely to be fed with tasks soon.
+	 * If it is the only unoccupied cpu in this domain,
+	 * we still handle it the same way as as_has_icpus
+	 * but turn the SMT into the unstable state, rather
+	 * than waiting to the end of load balancing since
+	 * it's also important that update the filter as
+	 * early as possible to keep it fresh.
+	 */
+	if (new == sd_is_busy) {
+		if (idle_cpu(this) || sched_idle_cpu(this)) {
+			new = sd_may_idle;
+			icpu = this;
+		}
+	}
+
 	/*
 	 * There is at least one unoccupied cpu available, so
 	 * propagate it to the filter to avoid false negative
@@ -9338,6 +9360,12 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
 	 * idle cpus thus throughupt downgraded.
 	 */
 	if (new != sd_is_busy) {
+		/*
+		 * The sd_may_idle state is taken into
+		 * consideration as well because from
+		 * here we couldn't actually know task
+		 * migrations would happen or not.
+		 */
 		if (!test_idle_cpus(this))
 			set_idle_cpus(this, true);
 	} else {
@@ -9347,9 +9375,26 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
 		 */
 		if (sd_smt_shared->state == sd_is_busy)
 			goto out;
+
+		/*
+		 * Allow false positive to exist for some time
+		 * to make a tradeoff of accuracy of the filter
+		 * for relieving cache traffic.
+		 */
+		if (sd_smt_shared->state == sd_has_icpus) {
+			new = sd_may_idle;
+			goto update;
+		}
+
+		/*
+		 * If the false positive issue has already been
+		 * there for a while, a correction of the filter
+		 * is needed.
+		 */
 	}
 
 	sd_update_icpus(this, sds->idle_cpu);
+update:
 	sd_smt_shared->state = new;
 out:
 	xchg(&sd_smt_shared->updating, 0);
-- 
2.31.1

Re: [PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[kernel test robot]

[-- Attachment #1: Type: text/plain, Size: 20768 bytes --]

:::::: 
:::::: Manual check reason: "low confidence static check warning: kernel/sched/fair.c:9330:6: warning: Value stored to 'icpu' during its initialization is never read [clang-analyzer-deadcode.DeadStores]"
:::::: 

CC: llvm(a)lists.linux.dev
CC: kbuild-all(a)lists.01.org
BCC: lkp(a)intel.com
In-Reply-To: <20220619120451.95251-8-wuyun.abel@bytedance.com>
References: <20220619120451.95251-8-wuyun.abel@bytedance.com>
TO: Abel Wu <wuyun.abel@bytedance.com>
TO: Peter Zijlstra <peterz@infradead.org>
TO: Mel Gorman <mgorman@suse.de>
TO: Vincent Guittot <vincent.guittot@linaro.org>
CC: Josh Don <joshdon@google.com>
CC: Chen Yu <yu.c.chen@intel.com>
CC: Tim Chen <tim.c.chen@linux.intel.com>
CC: K Prateek Nayak <kprateek.nayak@amd.com>
CC: "Gautham R . Shenoy" <gautham.shenoy@amd.com>
CC: linux-kernel(a)vger.kernel.org
CC: Abel Wu <wuyun.abel@bytedance.com>

Hi Abel,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on tip/sched/core]
[also build test WARNING on linus/master v5.19-rc2 next-20220617]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/intel-lab-lkp/linux/commits/Abel-Wu/sched-fair-improve-scan-efficiency-of-SIS/20220619-200743
base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git f3dd3f674555bd9455c5ae7fafce0696bd9931b3
:::::: branch date: 2 days ago
:::::: commit date: 2 days ago
config: s390-randconfig-c005-20220619 (https://download.01.org/0day-ci/archive/20220621/202206211517.bchsifSF-lkp(a)intel.com/config)
compiler: clang version 15.0.0 (https://github.com/llvm/llvm-project af6d2a0b6825e71965f3e2701a63c239fa0ad70f)
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # install s390 cross compiling tool for clang build
        # apt-get install binutils-s390x-linux-gnu
        # https://github.com/intel-lab-lkp/linux/commit/32fe13cd7aa184ed349d698ebf6f420fa426dd73
        git remote add linux-review https://github.com/intel-lab-lkp/linux
        git fetch --no-tags linux-review Abel-Wu/sched-fair-improve-scan-efficiency-of-SIS/20220619-200743
        git checkout 32fe13cd7aa184ed349d698ebf6f420fa426dd73
        # save the config file
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross ARCH=s390 clang-analyzer 

If you fix the issue, kindly add following tag where applicable
Reported-by: kernel test robot <lkp@intel.com>


clang-analyzer warnings: (new ones prefixed by >>)
           ^~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:9670:2: note: Calling 'update_sd_lb_stats'
           update_sd_lb_stats(env, &sds);
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:9422:7: note: Assuming 'local_group' is 0
                   if (local_group) {
                       ^~~~~~~~~~~
   kernel/sched/fair.c:9422:3: note: Taking false branch
                   if (local_group) {
                   ^
   kernel/sched/fair.c:9431:3: note: Calling 'update_sg_lb_stats'
                   update_sg_lb_stats(env, sds, sg, sgs, &sg_status);
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8766:16: note: Assuming 'group' is not equal to field 'local'
           local_group = group == sds->local;
                         ^~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8769:2: note: Assuming 'i' is >= 'nr_cpu_ids'
           for_each_cpu_and(i, sched_group_span(group), env->cpus) {
           ^
   include/linux/cpumask.h:326:3: note: expanded from macro 'for_each_cpu_and'
                   (cpu) < nr_cpu_ids;)
                   ^~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8769:2: note: Loop condition is false. Execution continues on line 8828
           for_each_cpu_and(i, sched_group_span(group), env->cpus) {
           ^
   include/linux/cpumask.h:324:2: note: expanded from macro 'for_each_cpu_and'
           for ((cpu) = -1;                                                \
           ^
   kernel/sched/fair.c:8833:7: note: 'local_group' is 0
           if (!local_group && env->sd->flags & SD_ASYM_PACKING &&
                ^~~~~~~~~~~
   kernel/sched/fair.c:8833:6: note: Left side of '&&' is true
           if (!local_group && env->sd->flags & SD_ASYM_PACKING &&
               ^
   kernel/sched/fair.c:8833:22: note: Assuming the condition is true
           if (!local_group && env->sd->flags & SD_ASYM_PACKING &&
                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8833:6: note: Left side of '&&' is true
           if (!local_group && env->sd->flags & SD_ASYM_PACKING &&
               ^
   kernel/sched/fair.c:8834:6: note: Assuming field 'idle' is not equal to CPU_NOT_IDLE
               env->idle != CPU_NOT_IDLE && sgs->sum_h_nr_running &&
               ^~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8833:6: note: Left side of '&&' is true
           if (!local_group && env->sd->flags & SD_ASYM_PACKING &&
               ^
   kernel/sched/fair.c:8834:35: note: Assuming field 'sum_h_nr_running' is not equal to 0
               env->idle != CPU_NOT_IDLE && sgs->sum_h_nr_running &&
                                            ^~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8833:6: note: Left side of '&&' is true
           if (!local_group && env->sd->flags & SD_ASYM_PACKING &&
               ^
   kernel/sched/fair.c:8835:6: note: Calling 'sched_asym'
               sched_asym(env, sds, sgs, group)) {
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8727:7: note: Access to field 'flags' results in a dereference of a null pointer (loaded from field 'local')
           if ((sds->local->flags & SD_SHARE_CPUCAPACITY) ||
                ^    ~~~~~
   kernel/sched/fair.c:8828:24: warning: Access to field 'sgc' results in a dereference of a null pointer (loaded from variable 'group') [clang-analyzer-core.NullDereference]
           sgs->group_capacity = group->sgc->capacity;
                                 ^
   kernel/sched/fair.c:9670:2: note: Calling 'update_sd_lb_stats'
           update_sd_lb_stats(env, &sds);
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:9412:2: note: 'sg' initialized here
           struct sched_group *sg = env->sd->groups;
           ^~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:9422:7: note: Assuming 'local_group' is 0
                   if (local_group) {
                       ^~~~~~~~~~~
   kernel/sched/fair.c:9422:3: note: Taking false branch
                   if (local_group) {
                   ^
   kernel/sched/fair.c:9431:32: note: Passing 'sg' via 3rd parameter 'group'
                   update_sg_lb_stats(env, sds, sg, sgs, &sg_status);
                                                ^~
   kernel/sched/fair.c:9431:3: note: Calling 'update_sg_lb_stats'
                   update_sg_lb_stats(env, sds, sg, sgs, &sg_status);
                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8766:16: note: Assuming 'group' is equal to field 'local'
           local_group = group == sds->local;
                         ^~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8766:16: note: Assuming pointer value is null
           local_group = group == sds->local;
                         ^~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8769:2: note: Assuming 'i' is >= 'nr_cpu_ids'
           for_each_cpu_and(i, sched_group_span(group), env->cpus) {
           ^
   include/linux/cpumask.h:326:3: note: expanded from macro 'for_each_cpu_and'
                   (cpu) < nr_cpu_ids;)
                   ^~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:8769:2: note: Loop condition is false. Execution continues on line 8828
           for_each_cpu_and(i, sched_group_span(group), env->cpus) {
           ^
   include/linux/cpumask.h:324:2: note: expanded from macro 'for_each_cpu_and'
           for ((cpu) = -1;                                                \
           ^
   kernel/sched/fair.c:8828:24: note: Access to field 'sgc' results in a dereference of a null pointer (loaded from variable 'group')
           sgs->group_capacity = group->sgc->capacity;
                                 ^~~~~
>> kernel/sched/fair.c:9330:6: warning: Value stored to 'icpu' during its initialization is never read [clang-analyzer-deadcode.DeadStores]
           int icpu = sds->idle_cpu, this = env->dst_cpu;
               ^~~~   ~~~~~~~~~~~~~
   kernel/sched/fair.c:9330:6: note: Value stored to 'icpu' during its initialization is never read
           int icpu = sds->idle_cpu, this = env->dst_cpu;
               ^~~~   ~~~~~~~~~~~~~
>> kernel/sched/fair.c:9352:4: warning: Value stored to 'icpu' is never read [clang-analyzer-deadcode.DeadStores]
                           icpu = this;
                           ^      ~~~~
   kernel/sched/fair.c:9352:4: note: Value stored to 'icpu' is never read
                           icpu = this;
                           ^      ~~~~
   kernel/sched/fair.c:10040:25: warning: Dereference of null pointer [clang-analyzer-core.NullDereference]
           struct cpumask *cpus = this_cpu_cpumask_var_ptr(load_balance_mask);
                                  ^
   include/linux/cpumask.h:761:37: note: expanded from macro 'this_cpu_cpumask_var_ptr'
   #define this_cpu_cpumask_var_ptr(x) this_cpu_ptr(x)
                                       ^
   include/linux/percpu-defs.h:252:27: note: expanded from macro 'this_cpu_ptr'
   #define this_cpu_ptr(ptr) raw_cpu_ptr(ptr)
                             ^
   include/linux/percpu-defs.h:242:2: note: expanded from macro 'raw_cpu_ptr'
           arch_raw_cpu_ptr(ptr);                                          \
           ^
   include/asm-generic/percpu.h:44:31: note: expanded from macro 'arch_raw_cpu_ptr'
   #define arch_raw_cpu_ptr(ptr) SHIFT_PERCPU_PTR(ptr, __my_cpu_offset)
                                 ^
   include/linux/percpu-defs.h:231:2: note: expanded from macro 'SHIFT_PERCPU_PTR'
           RELOC_HIDE((typeof(*(__p)) __kernel __force *)(__p), (__offset))
           ^
   include/linux/compiler.h:170:28: note: expanded from macro 'RELOC_HIDE'
       (typeof(ptr)) (__ptr + (off)); })
                              ^
   kernel/sched/fair.c:10462:13: note: Assuming 'idle' is equal to CPU_IDLE
           int busy = idle != CPU_IDLE && !sched_idle_cpu(cpu);
                      ^~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10462:30: note: Left side of '&&' is false
           int busy = idle != CPU_IDLE && !sched_idle_cpu(cpu);
                                       ^
   kernel/sched/fair.c:10472:2: note: Left side of '||' is false
           for_each_domain(cpu, sd) {
           ^
   kernel/sched/sched.h:1716:14: note: expanded from macro 'for_each_domain'
           for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
                       ^
   kernel/sched/sched.h:1705:2: note: expanded from macro 'rcu_dereference_check_sched_domain'
           rcu_dereference_check((p), \
           ^
   include/linux/rcupdate.h:532:2: note: expanded from macro 'rcu_dereference_check'
           __rcu_dereference_check((p), __UNIQUE_ID(rcu), \
           ^
   note: (skipping 1 expansions in backtrace; use -fmacro-backtrace-limit=0 to see all)
   include/asm-generic/rwonce.h:49:2: note: expanded from macro 'READ_ONCE'
           compiletime_assert_rwonce_type(x);                              \
           ^
   include/asm-generic/rwonce.h:36:21: note: expanded from macro 'compiletime_assert_rwonce_type'
           compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
                              ^
   include/linux/compiler_types.h:319:3: note: expanded from macro '__native_word'
           (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
            ^
   kernel/sched/fair.c:10472:2: note: Left side of '||' is false
           for_each_domain(cpu, sd) {
           ^
   kernel/sched/sched.h:1716:14: note: expanded from macro 'for_each_domain'
           for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
                       ^
   kernel/sched/sched.h:1705:2: note: expanded from macro 'rcu_dereference_check_sched_domain'
           rcu_dereference_check((p), \
           ^
   include/linux/rcupdate.h:532:2: note: expanded from macro 'rcu_dereference_check'
           __rcu_dereference_check((p), __UNIQUE_ID(rcu), \
           ^
   note: (skipping 1 expansions in backtrace; use -fmacro-backtrace-limit=0 to see all)
   include/asm-generic/rwonce.h:49:2: note: expanded from macro 'READ_ONCE'
           compiletime_assert_rwonce_type(x);                              \
           ^
   include/asm-generic/rwonce.h:36:21: note: expanded from macro 'compiletime_assert_rwonce_type'
           compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
                              ^
   include/linux/compiler_types.h:319:3: note: expanded from macro '__native_word'
           (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
            ^
   kernel/sched/fair.c:10472:2: note: Left side of '||' is false
           for_each_domain(cpu, sd) {
           ^
   kernel/sched/sched.h:1716:14: note: expanded from macro 'for_each_domain'
           for (__sd = rcu_dereference_check_sched_domain(cpu_rq(cpu)->sd); \
                       ^
   kernel/sched/sched.h:1705:2: note: expanded from macro 'rcu_dereference_check_sched_domain'
           rcu_dereference_check((p), \
           ^
   include/linux/rcupdate.h:532:2: note: expanded from macro 'rcu_dereference_check'
           __rcu_dereference_check((p), __UNIQUE_ID(rcu), \
           ^
   note: (skipping 1 expansions in backtrace; use -fmacro-backtrace-limit=0 to see all)
   include/asm-generic/rwonce.h:49:2: note: expanded from macro 'READ_ONCE'
           compiletime_assert_rwonce_type(x);                              \
           ^
   include/asm-generic/rwonce.h:36:21: note: expanded from macro 'compiletime_assert_rwonce_type'
           compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
                              ^
   include/linux/compiler_types.h:319:3: note: expanded from macro '__native_word'
           (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
            ^
   kernel/sched/fair.c:10472:2: note: Left side of '||' is true
           for_each_domain(cpu, sd) {

vim +/icpu +9330 kernel/sched/fair.c

57abff067a0848 Vincent Guittot 2019-10-18  9325  
ba6ee6cee1ed2f Abel Wu         2022-06-19  9326  static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
ba6ee6cee1ed2f Abel Wu         2022-06-19  9327  {
fcc108377a7cf7 Abel Wu         2022-06-19  9328  	struct sched_domain_shared *sd_smt_shared = env->sd->shared;
fcc108377a7cf7 Abel Wu         2022-06-19  9329  	enum sd_state new = sds->sd_state;
32fe13cd7aa184 Abel Wu         2022-06-19 @9330  	int icpu = sds->idle_cpu, this = env->dst_cpu;
fcc108377a7cf7 Abel Wu         2022-06-19  9331  
fcc108377a7cf7 Abel Wu         2022-06-19  9332  	/*
fcc108377a7cf7 Abel Wu         2022-06-19  9333  	 * Parallel updating can hardly contribute accuracy to
fcc108377a7cf7 Abel Wu         2022-06-19  9334  	 * the filter, besides it can be one of the burdens on
fcc108377a7cf7 Abel Wu         2022-06-19  9335  	 * cache traffic.
fcc108377a7cf7 Abel Wu         2022-06-19  9336  	 */
fcc108377a7cf7 Abel Wu         2022-06-19  9337  	if (cmpxchg(&sd_smt_shared->updating, 0, 1))
fcc108377a7cf7 Abel Wu         2022-06-19  9338  		return;
fcc108377a7cf7 Abel Wu         2022-06-19  9339  
32fe13cd7aa184 Abel Wu         2022-06-19  9340  	/*
32fe13cd7aa184 Abel Wu         2022-06-19  9341  	 * The dst_cpu is likely to be fed with tasks soon.
32fe13cd7aa184 Abel Wu         2022-06-19  9342  	 * If it is the only unoccupied cpu in this domain,
32fe13cd7aa184 Abel Wu         2022-06-19  9343  	 * we still handle it the same way as as_has_icpus
32fe13cd7aa184 Abel Wu         2022-06-19  9344  	 * but turn the SMT into the unstable state, rather
32fe13cd7aa184 Abel Wu         2022-06-19  9345  	 * than waiting to the end of load balancing since
32fe13cd7aa184 Abel Wu         2022-06-19  9346  	 * it's also important that update the filter as
32fe13cd7aa184 Abel Wu         2022-06-19  9347  	 * early as possible to keep it fresh.
32fe13cd7aa184 Abel Wu         2022-06-19  9348  	 */
32fe13cd7aa184 Abel Wu         2022-06-19  9349  	if (new == sd_is_busy) {
32fe13cd7aa184 Abel Wu         2022-06-19  9350  		if (idle_cpu(this) || sched_idle_cpu(this)) {
32fe13cd7aa184 Abel Wu         2022-06-19  9351  			new = sd_may_idle;
32fe13cd7aa184 Abel Wu         2022-06-19 @9352  			icpu = this;
32fe13cd7aa184 Abel Wu         2022-06-19  9353  		}
32fe13cd7aa184 Abel Wu         2022-06-19  9354  	}
32fe13cd7aa184 Abel Wu         2022-06-19  9355  
fcc108377a7cf7 Abel Wu         2022-06-19  9356  	/*
fcc108377a7cf7 Abel Wu         2022-06-19  9357  	 * There is at least one unoccupied cpu available, so
fcc108377a7cf7 Abel Wu         2022-06-19  9358  	 * propagate it to the filter to avoid false negative
fcc108377a7cf7 Abel Wu         2022-06-19  9359  	 * issue which could result in lost tracking of some
fcc108377a7cf7 Abel Wu         2022-06-19  9360  	 * idle cpus thus throughupt downgraded.
fcc108377a7cf7 Abel Wu         2022-06-19  9361  	 */
fcc108377a7cf7 Abel Wu         2022-06-19  9362  	if (new != sd_is_busy) {
32fe13cd7aa184 Abel Wu         2022-06-19  9363  		/*
32fe13cd7aa184 Abel Wu         2022-06-19  9364  		 * The sd_may_idle state is taken into
32fe13cd7aa184 Abel Wu         2022-06-19  9365  		 * consideration as well because from
32fe13cd7aa184 Abel Wu         2022-06-19  9366  		 * here we couldn't actually know task
32fe13cd7aa184 Abel Wu         2022-06-19  9367  		 * migrations would happen or not.
32fe13cd7aa184 Abel Wu         2022-06-19  9368  		 */
fcc108377a7cf7 Abel Wu         2022-06-19  9369  		if (!test_idle_cpus(this))
fcc108377a7cf7 Abel Wu         2022-06-19  9370  			set_idle_cpus(this, true);
fcc108377a7cf7 Abel Wu         2022-06-19  9371  	} else {
fcc108377a7cf7 Abel Wu         2022-06-19  9372  		/*
fcc108377a7cf7 Abel Wu         2022-06-19  9373  		 * Nothing changes so nothing to update or
fcc108377a7cf7 Abel Wu         2022-06-19  9374  		 * propagate.
fcc108377a7cf7 Abel Wu         2022-06-19  9375  		 */
fcc108377a7cf7 Abel Wu         2022-06-19  9376  		if (sd_smt_shared->state == sd_is_busy)
fcc108377a7cf7 Abel Wu         2022-06-19  9377  			goto out;
32fe13cd7aa184 Abel Wu         2022-06-19  9378  
32fe13cd7aa184 Abel Wu         2022-06-19  9379  		/*
32fe13cd7aa184 Abel Wu         2022-06-19  9380  		 * Allow false positive to exist for some time
32fe13cd7aa184 Abel Wu         2022-06-19  9381  		 * to make a tradeoff of accuracy of the filter
32fe13cd7aa184 Abel Wu         2022-06-19  9382  		 * for relieving cache traffic.
32fe13cd7aa184 Abel Wu         2022-06-19  9383  		 */
32fe13cd7aa184 Abel Wu         2022-06-19  9384  		if (sd_smt_shared->state == sd_has_icpus) {
32fe13cd7aa184 Abel Wu         2022-06-19  9385  			new = sd_may_idle;
32fe13cd7aa184 Abel Wu         2022-06-19  9386  			goto update;
32fe13cd7aa184 Abel Wu         2022-06-19  9387  		}
32fe13cd7aa184 Abel Wu         2022-06-19  9388  
32fe13cd7aa184 Abel Wu         2022-06-19  9389  		/*
32fe13cd7aa184 Abel Wu         2022-06-19  9390  		 * If the false positive issue has already been
32fe13cd7aa184 Abel Wu         2022-06-19  9391  		 * there for a while, a correction of the filter
32fe13cd7aa184 Abel Wu         2022-06-19  9392  		 * is needed.
32fe13cd7aa184 Abel Wu         2022-06-19  9393  		 */
fcc108377a7cf7 Abel Wu         2022-06-19  9394  	}
fcc108377a7cf7 Abel Wu         2022-06-19  9395  
fcc108377a7cf7 Abel Wu         2022-06-19  9396  	sd_update_icpus(this, sds->idle_cpu);
32fe13cd7aa184 Abel Wu         2022-06-19  9397  update:
fcc108377a7cf7 Abel Wu         2022-06-19  9398  	sd_smt_shared->state = new;
fcc108377a7cf7 Abel Wu         2022-06-19  9399  out:
fcc108377a7cf7 Abel Wu         2022-06-19  9400  	xchg(&sd_smt_shared->updating, 0);
ba6ee6cee1ed2f Abel Wu         2022-06-19  9401  }
ba6ee6cee1ed2f Abel Wu         2022-06-19  9402  

-- 
0-DAY CI Kernel Test Service
https://01.org/lkp

Re: [PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[Chen Yu]

On Sun, Jun 19, 2022 at 08:04:51PM +0800, Abel Wu wrote:
> Now when updating core state, there are two main problems that could
> pollute the SIS filter:
> 
>   - The updating is before task migration, so if dst_cpu is
>     selected to be propagated which might be fed with tasks
>     soon, the efforts we paid is no more than setting a busy
>     cpu into the SIS filter. While on the other hand it is
>     important that we update as early as possible to keep the
>     filter fresh, so it's not wise to delay the update to the
>     end of load balancing.
> 
>   - False negative propagation hurts performance since some
>     idle cpus could be out of reach. So in general we will
>     aggressively propagate idle cpus but allow false positive
>     continue to exist for a while, which may lead to filter
>     being fully polluted.
> 
> Pains can be relieved by a force correction when false positive
> continuously detected.
> 
> Signed-off-by: Abel Wu <wuyun.abel@bytedance.com>
> ---
>  include/linux/sched/topology.h |  7 +++++
>  kernel/sched/fair.c            | 51 ++++++++++++++++++++++++++++++++--
>  2 files changed, 55 insertions(+), 3 deletions(-)
> 
> diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
> index b93edf587d84..e3552ce192a9 100644
> --- a/include/linux/sched/topology.h
> +++ b/include/linux/sched/topology.h
> @@ -91,6 +91,12 @@ struct sched_group;
>   *	search, and is also used as a fallback state of the other
>   *	states.
>   *
> + * - sd_may_idle
> + *	This state implies the unstableness of the SIS filter, and
> + *	some bits of it may out of date. This state is only used in
> + *	SMT domains as an intermediate state between sd_has_icpus
> + *	and sd_is_busy.
> + *
>   * - sd_is_busy
>   *	This state indicates there are no unoccupied cpus in this
>   *	domain. So for LLC domains, it gives the hint on whether
> @@ -111,6 +117,7 @@ struct sched_group;
>  enum sd_state {
>  	sd_has_icores,
>  	sd_has_icpus,
> +	sd_may_idle,
>  	sd_is_busy
>  };
>  
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d55fdcedf2c0..9713d183d35e 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8768,6 +8768,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>  
>  	for_each_cpu_and(i, sched_group_span(group), env->cpus) {
>  		struct rq *rq = cpu_rq(i);
> +		bool update = update_core && (env->dst_cpu != i);
>  
>  		sgs->group_load += cpu_load(rq);
>  		sgs->group_util += cpu_util_cfs(i);
> @@ -8777,7 +8778,11 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>  		nr_running = rq->nr_running;
>  		sgs->sum_nr_running += nr_running;
>  
> -		if (update_core)
> +		/*
> +		 * The dst_cpu is not preferred since it might
> +		 * be fed with tasks soon.
> +		 */
> +		if (update)
maybe if (update_core && (env->dst_cpu != i)) so that the comment would
be near the code logic and meanwhile without introducing a update variable?
>  			sd_classify(sds, rq, i);
>  
>  		if (nr_running > 1)
> @@ -8801,7 +8806,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>  			 * and fed with tasks, so we'd better choose
>  			 * a candidate in an opposite way.
>  			 */
> -			sds->idle_cpu = i;
> +			if (update)
> +				sds->idle_cpu = i;
>  			sgs->idle_cpus++;
>  
>  			/* Idle cpu can't have misfit task */
> @@ -9321,7 +9327,7 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  {
>  	struct sched_domain_shared *sd_smt_shared = env->sd->shared;
>  	enum sd_state new = sds->sd_state;
> -	int this = env->dst_cpu;
> +	int icpu = sds->idle_cpu, this = env->dst_cpu;
>  
>  	/*
>  	 * Parallel updating can hardly contribute accuracy to
> @@ -9331,6 +9337,22 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  	if (cmpxchg(&sd_smt_shared->updating, 0, 1))
>  		return;
>  
> +	/*
> +	 * The dst_cpu is likely to be fed with tasks soon.
> +	 * If it is the only unoccupied cpu in this domain,
> +	 * we still handle it the same way as as_has_icpus
> +	 * but turn the SMT into the unstable state, rather
> +	 * than waiting to the end of load balancing since
> +	 * it's also important that update the filter as
> +	 * early as possible to keep it fresh.
> +	 */
> +	if (new == sd_is_busy) {
> +		if (idle_cpu(this) || sched_idle_cpu(this)) {
available_idle_cpu()?

thanks,
Chenyu
> +			new = sd_may_idle;
> +			icpu = this;
> +		}
> +	}
> +
>  	/*
>  	 * There is at least one unoccupied cpu available, so
>  	 * propagate it to the filter to avoid false negative
> @@ -9338,6 +9360,12 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  	 * idle cpus thus throughupt downgraded.
>  	 */
>  	if (new != sd_is_busy) {
> +		/*
> +		 * The sd_may_idle state is taken into
> +		 * consideration as well because from
> +		 * here we couldn't actually know task
> +		 * migrations would happen or not.
> +		 */
>  		if (!test_idle_cpus(this))
>  			set_idle_cpus(this, true);
>  	} else {
> @@ -9347,9 +9375,26 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  		 */
>  		if (sd_smt_shared->state == sd_is_busy)
>  			goto out;
> +
> +		/*
> +		 * Allow false positive to exist for some time
> +		 * to make a tradeoff of accuracy of the filter
> +		 * for relieving cache traffic.
> +		 */
> +		if (sd_smt_shared->state == sd_has_icpus) {
> +			new = sd_may_idle;
> +			goto update;
> +		}
> +
> +		/*
> +		 * If the false positive issue has already been
> +		 * there for a while, a correction of the filter
> +		 * is needed.
> +		 */
>  	}
>  
>  	sd_update_icpus(this, sds->idle_cpu);
> +update:
>  	sd_smt_shared->state = new;
>  out:
>  	xchg(&sd_smt_shared->updating, 0);
> -- 
> 2.31.1
> 

Re: [PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[Abel Wu]

On 6/22/22 2:23 AM, Chen Yu Wrote:
> On Sun, Jun 19, 2022 at 08:04:51PM +0800, Abel Wu wrote:
>> ...
>> @@ -8777,7 +8778,11 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>>   		nr_running = rq->nr_running;
>>   		sgs->sum_nr_running += nr_running;
>>   
>> -		if (update_core)
>> +		/*
>> +		 * The dst_cpu is not preferred since it might
>> +		 * be fed with tasks soon.
>> +		 */
>> +		if (update)
> maybe if (update_core && (env->dst_cpu != i)) so that the comment would
> be near the code logic and meanwhile without introducing a update variable?

Makes sense.

>> ...
>> @@ -9331,6 +9337,22 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>>   	if (cmpxchg(&sd_smt_shared->updating, 0, 1))
>>   		return;
>>   
>> +	/*
>> +	 * The dst_cpu is likely to be fed with tasks soon.
>> +	 * If it is the only unoccupied cpu in this domain,
>> +	 * we still handle it the same way as as_has_icpus
>> +	 * but turn the SMT into the unstable state, rather
>> +	 * than waiting to the end of load balancing since
>> +	 * it's also important that update the filter as
>> +	 * early as possible to keep it fresh.
>> +	 */
>> +	if (new == sd_is_busy) {
>> +		if (idle_cpu(this) || sched_idle_cpu(this)) {
> available_idle_cpu()?
> 

It is used for choosing an idle cpu that will be immediately used,
so generally inside the wakeup path. But here we just want to know
the idle state of the cpus (and later inside wakeup path these cpus
will still be re-checked to see if they are preempted).

Thanks & BR,
Abel

Re: [PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[Abel Wu]

On 6/19/22 8:04 PM, Abel Wu Wrote:
> Now when updating core state, there are two main problems that could
> pollute the SIS filter:
> 
>    - The updating is before task migration, so if dst_cpu is
>      selected to be propagated which might be fed with tasks
>      soon, the efforts we paid is no more than setting a busy
>      cpu into the SIS filter. While on the other hand it is
>      important that we update as early as possible to keep the
>      filter fresh, so it's not wise to delay the update to the
>      end of load balancing.
> 
>    - False negative propagation hurts performance since some
>      idle cpus could be out of reach. So in general we will
>      aggressively propagate idle cpus but allow false positive
>      continue to exist for a while, which may lead to filter
>      being fully polluted.
> 
> Pains can be relieved by a force correction when false positive
> continuously detected.
> 
> Signed-off-by: Abel Wu <wuyun.abel@bytedance.com>
> ---
>   include/linux/sched/topology.h |  7 +++++
>   kernel/sched/fair.c            | 51 ++++++++++++++++++++++++++++++++--
>   2 files changed, 55 insertions(+), 3 deletions(-)
> 
> diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
> index b93edf587d84..e3552ce192a9 100644
> --- a/include/linux/sched/topology.h
> +++ b/include/linux/sched/topology.h
> @@ -91,6 +91,12 @@ struct sched_group;
>    *	search, and is also used as a fallback state of the other
>    *	states.
>    *
> + * - sd_may_idle
> + *	This state implies the unstableness of the SIS filter, and
> + *	some bits of it may out of date. This state is only used in
> + *	SMT domains as an intermediate state between sd_has_icpus
> + *	and sd_is_busy.
> + *
>    * - sd_is_busy
>    *	This state indicates there are no unoccupied cpus in this
>    *	domain. So for LLC domains, it gives the hint on whether
> @@ -111,6 +117,7 @@ struct sched_group;
>   enum sd_state {
>   	sd_has_icores,
>   	sd_has_icpus,
> +	sd_may_idle,
>   	sd_is_busy
>   };
>   
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d55fdcedf2c0..9713d183d35e 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8768,6 +8768,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>   
>   	for_each_cpu_and(i, sched_group_span(group), env->cpus) {
>   		struct rq *rq = cpu_rq(i);
> +		bool update = update_core && (env->dst_cpu != i);
>   
>   		sgs->group_load += cpu_load(rq);
>   		sgs->group_util += cpu_util_cfs(i);
> @@ -8777,7 +8778,11 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>   		nr_running = rq->nr_running;
>   		sgs->sum_nr_running += nr_running;
>   
> -		if (update_core)
> +		/*
> +		 * The dst_cpu is not preferred since it might
> +		 * be fed with tasks soon.
> +		 */
> +		if (update)
>   			sd_classify(sds, rq, i);
>   
>   		if (nr_running > 1)
> @@ -8801,7 +8806,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
>   			 * and fed with tasks, so we'd better choose
>   			 * a candidate in an opposite way.
>   			 */
> -			sds->idle_cpu = i;
> +			if (update)
> +				sds->idle_cpu = i;
>   			sgs->idle_cpus++;
>   
>   			/* Idle cpu can't have misfit task */
> @@ -9321,7 +9327,7 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>   {
>   	struct sched_domain_shared *sd_smt_shared = env->sd->shared;
>   	enum sd_state new = sds->sd_state;
> -	int this = env->dst_cpu;
> +	int icpu = sds->idle_cpu, this = env->dst_cpu;
>   
>   	/*
>   	 * Parallel updating can hardly contribute accuracy to
> @@ -9331,6 +9337,22 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>   	if (cmpxchg(&sd_smt_shared->updating, 0, 1))
>   		return;
>   
> +	/*
> +	 * The dst_cpu is likely to be fed with tasks soon.
> +	 * If it is the only unoccupied cpu in this domain,
> +	 * we still handle it the same way as as_has_icpus
> +	 * but turn the SMT into the unstable state, rather
> +	 * than waiting to the end of load balancing since
> +	 * it's also important that update the filter as
> +	 * early as possible to keep it fresh.
> +	 */
> +	if (new == sd_is_busy) {
> +		if (idle_cpu(this) || sched_idle_cpu(this)) {
> +			new = sd_may_idle;
> +			icpu = this;
> +		}
> +	}
> +
>   	/*
>   	 * There is at least one unoccupied cpu available, so
>   	 * propagate it to the filter to avoid false negative
> @@ -9338,6 +9360,12 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>   	 * idle cpus thus throughupt downgraded.
>   	 */
>   	if (new != sd_is_busy) {
> +		/*
> +		 * The sd_may_idle state is taken into
> +		 * consideration as well because from
> +		 * here we couldn't actually know task
> +		 * migrations would happen or not.
> +		 */
>   		if (!test_idle_cpus(this))
>   			set_idle_cpus(this, true);
>   	} else {
> @@ -9347,9 +9375,26 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>   		 */
>   		if (sd_smt_shared->state == sd_is_busy)
>   			goto out;
> +
> +		/*
> +		 * Allow false positive to exist for some time
> +		 * to make a tradeoff of accuracy of the filter
> +		 * for relieving cache traffic.
> +		 */
> +		if (sd_smt_shared->state == sd_has_icpus) {
> +			new = sd_may_idle;
> +			goto update;
> +		}
> +
> +		/*
> +		 * If the false positive issue has already been
> +		 * there for a while, a correction of the filter
> +		 * is needed.
> +		 */
>   	}
>   
>   	sd_update_icpus(this, sds->idle_cpu);

The @icpu should be used here rather than 'sds->idle_cpu'..
Will be fixed in next version.

> +update:
>   	sd_smt_shared->state = new;
>   out:
>   	xchg(&sd_smt_shared->updating, 0);

Re: [PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[Gautham R. Shenoy]

Hello Abel,

On Sun, Jun 19, 2022 at 08:04:51PM +0800, Abel Wu wrote:
> Now when updating core state, there are two main problems that could
> pollute the SIS filter:
> 
>   - The updating is before task migration, so if dst_cpu is
>     selected to be propagated which might be fed with tasks
>     soon, the efforts we paid is no more than setting a busy
>     cpu into the SIS filter. While on the other hand it is
>     important that we update as early as possible to keep the
>     filter fresh, so it's not wise to delay the update to the
>     end of load balancing.
> 
>   - False negative propagation hurts performance since some
>     idle cpus could be out of reach. So in general we will
>     aggressively propagate idle cpus but allow false positive
>     continue to exist for a while, which may lead to filter
>     being fully polluted.

Ok, so the false positive case is being addressed in this patch.

> 
> Pains can be relieved by a force correction when false positive
> continuously detected.
> 
[..snip..]

> @@ -111,6 +117,7 @@ struct sched_group;
>  enum sd_state {
>  	sd_has_icores,
>  	sd_has_icpus,
> +	sd_may_idle,
>  	sd_is_busy
>  };
>  
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d55fdcedf2c0..9713d183d35e 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c

[...snip..]

> @@ -9321,7 +9327,7 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  {
>  	struct sched_domain_shared *sd_smt_shared = env->sd->shared;
>  	enum sd_state new = sds->sd_state;
> -	int this = env->dst_cpu;
> +	int icpu = sds->idle_cpu, this = env->dst_cpu;
>  
>  	/*
>  	 * Parallel updating can hardly contribute accuracy to
> @@ -9331,6 +9337,22 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  	if (cmpxchg(&sd_smt_shared->updating, 0, 1))
>  		return;
>  
> +	/*
> +	 * The dst_cpu is likely to be fed with tasks soon.
> +	 * If it is the only unoccupied cpu in this domain,
> +	 * we still handle it the same way as as_has_icpus
                                              ^^^^^^^^^^^^^
Nit:                                          sd_has_icpus

> +	 * but turn the SMT into the unstable state, rather
> +	 * than waiting to the end of load balancing since
> +	 * it's also important that update the filter as
> +	 * early as possible to keep it fresh.
> +	 */
> +	if (new == sd_is_busy) {
> +		if (idle_cpu(this) || sched_idle_cpu(this)) {
> +			new = sd_may_idle;
> +			icpu = this;
> +		}
> +	}
> +
>  	/*
>  	 * There is at least one unoccupied cpu available, so
>  	 * propagate it to the filter to avoid false negative
> @@ -9338,6 +9360,12 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  	 * idle cpus thus throughupt downgraded.
>  	 */
>  	if (new != sd_is_busy) {
> +		/*
> +		 * The sd_may_idle state is taken into
> +		 * consideration as well because from
> +		 * here we couldn't actually know task
> +		 * migrations would happen or not.
> +		 */
>  		if (!test_idle_cpus(this))
>  			set_idle_cpus(this, true);
>  	} else {
> @@ -9347,9 +9375,26 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>  		 */
>  		if (sd_smt_shared->state == sd_is_busy)
>  			goto out;
> +
> +		/*
> +		 * Allow false positive to exist for some time
> +		 * to make a tradeoff of accuracy of the filter
> +		 * for relieving cache traffic.
> +		 */

I can understand allowing the false positive to exist when there are
no other idle CPUs in this SMT domain other than this CPU, which is
handled by the case where new != sd_is_busy in the current
load-balance round and will be handled by the "else" clause in the
subsequent round if env->dst_cpu ends up becoming busy.


However, when we know that new == sd_is_busy and the previous state of
this SMT domain was sd_has_icpus, should we not immediately clear this
core's cpumask from the LLCs icpus mask? What is the need for the
intermediate sd_may_idle state transition between sd_has_icpus and
sd_is_busy in this case ?



> +		if (sd_smt_shared->state == sd_has_icpus) {
> +			new = sd_may_idle;
> +			goto update;
> +		}
> +
> +		/*
> +		 * If the false positive issue has already been
> +		 * there for a while, a correction of the filter
> +		 * is needed.
> +		 */
>  	}
>  
>  	sd_update_icpus(this, sds->idle_cpu);
                              ^^^^^^^^^^^^^^

I think you meant to use icpu here ?  sds->idle_cpu == -1 in the case
when new == sd_may_idle. Which will end up clearing this core's
cpumask from this LLC's icpus mask. This defeats the
"allow-false-positive" heuristic.




> +update:
>  	sd_smt_shared->state = new;
>  out:
>  	xchg(&sd_smt_shared->updating, 0);
> -- 
> 2.31.1
>

--
Thanks and Regards
gautham.

Re: [PATCH v4 7/7] sched/fair: de-entropy for SIS filter

[Abel Wu]

On 7/21/22 1:08 AM, Gautham R. Shenoy Wrote:
> Hello Abel,
> 
> On Sun, Jun 19, 2022 at 08:04:51PM +0800, Abel Wu wrote:
>> Now when updating core state, there are two main problems that could
>> pollute the SIS filter:
>>
>>    - The updating is before task migration, so if dst_cpu is
>>      selected to be propagated which might be fed with tasks
>>      soon, the efforts we paid is no more than setting a busy
>>      cpu into the SIS filter. While on the other hand it is
>>      important that we update as early as possible to keep the
>>      filter fresh, so it's not wise to delay the update to the
>>      end of load balancing.
>>
>>    - False negative propagation hurts performance since some
>>      idle cpus could be out of reach. So in general we will
>>      aggressively propagate idle cpus but allow false positive
>>      continue to exist for a while, which may lead to filter
>>      being fully polluted.
> 
> Ok, so the false positive case is being addressed in this patch.
> 
>>
>> Pains can be relieved by a force correction when false positive
>> continuously detected.
>>
> [..snip..]
> 
>> @@ -111,6 +117,7 @@ struct sched_group;
>>   enum sd_state {
>>   	sd_has_icores,
>>   	sd_has_icpus,
>> +	sd_may_idle,
>>   	sd_is_busy
>>   };
>>   
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d55fdcedf2c0..9713d183d35e 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
> 
> [...snip..]
> 
>> @@ -9321,7 +9327,7 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>>   {
>>   	struct sched_domain_shared *sd_smt_shared = env->sd->shared;
>>   	enum sd_state new = sds->sd_state;
>> -	int this = env->dst_cpu;
>> +	int icpu = sds->idle_cpu, this = env->dst_cpu;
>>   
>>   	/*
>>   	 * Parallel updating can hardly contribute accuracy to
>> @@ -9331,6 +9337,22 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>>   	if (cmpxchg(&sd_smt_shared->updating, 0, 1))
>>   		return;
>>   
>> +	/*
>> +	 * The dst_cpu is likely to be fed with tasks soon.
>> +	 * If it is the only unoccupied cpu in this domain,
>> +	 * we still handle it the same way as as_has_icpus
>                                                ^^^^^^^^^^^^^
> Nit:                                          sd_has_icpus

Will fix.

> 
>> +	 * but turn the SMT into the unstable state, rather
>> +	 * than waiting to the end of load balancing since
>> +	 * it's also important that update the filter as
>> +	 * early as possible to keep it fresh.
>> +	 */
>> +	if (new == sd_is_busy) {
>> +		if (idle_cpu(this) || sched_idle_cpu(this)) {
>> +			new = sd_may_idle;
>> +			icpu = this;
>> +		}
>> +	}
>> +
>>   	/*
>>   	 * There is at least one unoccupied cpu available, so
>>   	 * propagate it to the filter to avoid false negative
>> @@ -9338,6 +9360,12 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>>   	 * idle cpus thus throughupt downgraded.
>>   	 */
>>   	if (new != sd_is_busy) {
>> +		/*
>> +		 * The sd_may_idle state is taken into
>> +		 * consideration as well because from
>> +		 * here we couldn't actually know task
>> +		 * migrations would happen or not.
>> +		 */
>>   		if (!test_idle_cpus(this))
>>   			set_idle_cpus(this, true);
>>   	} else {
>> @@ -9347,9 +9375,26 @@ static void sd_update_state(struct lb_env *env, struct sd_lb_stats *sds)
>>   		 */
>>   		if (sd_smt_shared->state == sd_is_busy)
>>   			goto out;
>> +
>> +		/*
>> +		 * Allow false positive to exist for some time
>> +		 * to make a tradeoff of accuracy of the filter
>> +		 * for relieving cache traffic.
>> +		 */
> 
> I can understand allowing the false positive to exist when there are
> no other idle CPUs in this SMT domain other than this CPU, which is
> handled by the case where new != sd_is_busy in the current
> load-balance round and will be handled by the "else" clause in the
> subsequent round if env->dst_cpu ends up becoming busy.
> 

Yes.

> 
> However, when we know that new == sd_is_busy and the previous state of
> this SMT domain was sd_has_icpus, should we not immediately clear this
> core's cpumask from the LLCs icpus mask? What is the need for the
> intermediate sd_may_idle state transition between sd_has_icpus and
> sd_is_busy in this case ?
> 

The thought was to make addition more aggressive than deletion to the
filter to try to avoid real idle cpus being out of reach. Take short
running tasks for example, the cpus in this newly-busy SMT domain can
become idle multiple times during next balancing period, which won't
be selected if update to sd_is_busy intermediately. While for the non-
short running workloads, the only downside is sacrificing the filter's
accuracy for a short while.

IOW, temporarily containing false positive cpus in the filter is more
acceptable than missing some real idle ones which would cause throughput
reduced. Besides, in this way the cache traffic can be relieved more
or less.

> 
> 
>> +		if (sd_smt_shared->state == sd_has_icpus) {
>> +			new = sd_may_idle;
>> +			goto update;
>> +		}
>> +
>> +		/*
>> +		 * If the false positive issue has already been
>> +		 * there for a while, a correction of the filter
>> +		 * is needed.
>> +		 */
>>   	}
>>   
>>   	sd_update_icpus(this, sds->idle_cpu);
>                                ^^^^^^^^^^^^^^
> 
> I think you meant to use icpu here ?  sds->idle_cpu == -1 in the case
> when new == sd_may_idle. Which will end up clearing this core's
> cpumask from this LLC's icpus mask. This defeats the
> "allow-false-positive" heuristic.
> 

Nice catch, will fix.

Thanks & Best Regards,
Abel