Skip to contentSkip to conversation

sched/fair: select idle cpu from idle cpumask for task wakeup

RFC PATCH Superseded Aubrey Li 6 participants 15 messages Oct 21, 2020 – Nov 12, 2020 Scheduler

v3 of 8 Superseded Latest is v8 →

lore
Share & tools
lore

Aubrey Li

author
#0 lore raw

RFC PATCH v3 1/1 sched/fair: select idle cpu from idle cpumask for task wakeup

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask to nohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- set SCHED_IDLE cpu in idle cpumask to allow it as a wakeup target.

v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask with sched_domain_span(sd), nohz=off case remains the original behavior.

Cc Mel Gorman <[email protected]>
Cc Vincent Guittot <[email protected]>
Cc Qais Yousef <[email protected]>
Cc Valentin Schneider <[email protected]>
Cc Jiang Biao <[email protected]>
Cc Tim Chen <[email protected]>
---
 include/linux/sched/topology.h | 13 ++++++++++
 kernel/sched/fair.c            | 45 +++++++++++++++++++++++++++++++++-
 kernel/sched/idle.c            |  1 +
 kernel/sched/sched.h           |  1 +
 kernel/sched/topology.c        |  3 ++-
 5 files changed, 61 insertions(+), 2 deletions(-)
include/linux/sched/topology.h +13 -0
index fb11091129b3..43a641d26154 100644
@@ -65,8 +65,21 @@ struct sched_domain_shared {
 	atomic_t	ref;
 	atomic_t	nr_busy_cpus;
 	int		has_idle_cores;
+	/*
+	 * Span of all idle CPUs in this domain.
+	 *
+	 * NOTE: this field is variable length. (Allocated dynamically
+	 * by attaching extra space to the end of the structure,
+	 * depending on how many CPUs the kernel has booted up with)
+	 */
+	unsigned long	idle_cpus_span[];
 };
 
+static inline struct cpumask *sds_idle_cpus(struct sched_domain_shared *sds)
+{
+	return to_cpumask(sds->idle_cpus_span);
+}
+
 struct sched_domain {
 	/* These fields must be setup */
 	struct sched_domain __rcu *parent;	/* top domain must be null terminated */
kernel/sched/fair.c +44 -1

63 lines not on this page · raw message

kernel/sched/idle.c +1 -0
index 1ae95b9150d3..ce1f929d7fbb 100644
@@ -405,6 +405,7 @@ static void put_prev_task_idle(struct rq *rq, struct task_struct *prev)
 static void set_next_task_idle(struct rq *rq, struct task_struct *next, bool first)
 {
 	update_idle_core(rq);
+	update_idle_cpumask(rq, true);
 	schedstat_inc(rq->sched_goidle);
 }
 
kernel/sched/sched.h +1 -0
index c82857e2e288..2d1655039ed5 100644
@@ -1069,6 +1069,7 @@ static inline void update_idle_core(struct rq *rq)
 #else
 static inline void update_idle_core(struct rq *rq) { }
 #endif
+void update_idle_cpumask(struct rq *rq, bool idle_state);
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
 
kernel/sched/topology.c +2 -1
index 9079d865a935..f14a6ef4de57 100644
@@ -1407,6 +1407,7 @@ sd_init(struct sched_domain_topology_level *tl,
 		sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
 		atomic_inc(&sd->shared->ref);
 		atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
+		cpumask_copy(sds_idle_cpus(sd->shared), sched_domain_span(sd));
 	}
 
 	sd->private = sdd;
@@ -1769,7 +1770,7 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
 
 			*per_cpu_ptr(sdd->sd, j) = sd;
 
-			sds = kzalloc_node(sizeof(struct sched_domain_shared),
+			sds = kzalloc_node(sizeof(struct sched_domain_shared) + cpumask_size(),
 					GFP_KERNEL, cpu_to_node(j));
 			if (!sds)
 				return -ENOMEM;
Signature · 1 line
2.25.1
#1 lore raw
[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]

Hi Aubrey,

[FYI, it's a private test report for your RFC patch.]
[auto build test ERROR on tip/sched/core]
[also build test ERROR on tip/master linus/master linux/master v5.9] [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/0day-ci/linux/commits/Aubrey-Li/sched-fair-select-idle-cpu-from-idle-cpumask-for-task-wakeup/20201021-230800
base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git feff2e65efd8d84cf831668e182b2ce73c604bbb
config: nds32-allnoconfig (attached as .config)
compiler: nds32le-linux-gcc (GCC) 9.3.0

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
# https://github.com/0day-ci/linux/commit/dbfb0d54ab82b9a27e28a8b850cfe1f1f542991a
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Aubrey-Li/sched-fair-select-idle-cpu-from-idle-cpumask-for-task-wakeup/20201021-230800 git checkout dbfb0d54ab82b9a27e28a8b850cfe1f1f542991a
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-9.3.0 make.cross ARCH=nds32

If you fix the issue, kindly add following tag as appropriate

All errors (new ones prefixed by >>):

nds32le-linux-ld: kernel/sched/idle.o: in function `set_next_task_idle':
idle.c:(.text+0x30): undefined reference to `update_idle_cpumask'

>> nds32le-linux-ld: idle.c:(.text+0x34): undefined reference to `update_idle_cpumask'

nds32le-linux-ld: kernel/sched/idle.o: in function `pick_next_task_idle':
idle.c:(.text+0x46): undefined reference to `update_idle_cpumask'
nds32le-linux-ld: idle.c:(.text+0x4a): undefined reference to `update_idle_cpumask'

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

#2 lore raw
Quoted 6 lines · kernel test robot

Hi Aubrey,

[FYI, it's a private test report for your RFC patch.]
[auto build test ERROR on tip/sched/core]
[also build test ERROR on tip/master linus/master linux/master v5.9] [If your patch is applied to the wrong git tree, kindly drop us a note.

Yes this PATCH is based on 5.8.10 and I don't expect it works on v5.9. I posted it as a RFC to request more discussion from the community.

Thanks,
-Aubrey

Quoted 33 lines

And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

url:    https://github.com/0day-ci/linux/commits/Aubrey-Li/sched-fair-select-idle-cpu-from-idle-cpumask-for-task-wakeup/20201021-230800
base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git feff2e65efd8d84cf831668e182b2ce73c604bbb
config: nds32-allnoconfig (attached as .config)
compiler: nds32le-linux-gcc (GCC) 9.3.0

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
# https://github.com/0day-ci/linux/commit/dbfb0d54ab82b9a27e28a8b850cfe1f1f542991a
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Aubrey-Li/sched-fair-select-idle-cpu-from-idle-cpumask-for-task-wakeup/20201021-230800 git checkout dbfb0d54ab82b9a27e28a8b850cfe1f1f542991a
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-9.3.0 make.cross ARCH=nds32

If you fix the issue, kindly add following tag as appropriate

All errors (new ones prefixed by >>):

nds32le-linux-ld: kernel/sched/idle.o: in function `set_next_task_idle':

   idle.c:(.text+0x30): undefined reference to `update_idle_cpumask'
Quoted 1 line
Quoted 1 line

nds32le-linux-ld: idle.c:(.text+0x34): undefined reference to `update_idle_cpumask'

nds32le-linux-ld: kernel/sched/idle.o: in function `pick_next_task_idle':

   idle.c:(.text+0x46): undefined reference to `update_idle_cpumask'
   nds32le-linux-ld: idle.c:(.text+0x4a): undefined reference to `update_idle_cpumask'

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

#3 lore raw
In reply to Aubrey Li
[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]

Hi Aubrey,

[FYI, it's a private test report for your RFC patch.]
[auto build test ERROR on tip/sched/core]
[also build test ERROR on tip/master linus/master linux/master v5.9] [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/0day-ci/linux/commits/Aubrey-Li/sched-fair-select-idle-cpu-from-idle-cpumask-for-task-wakeup/20201021-230800
base:   https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git feff2e65efd8d84cf831668e182b2ce73c604bbb
config: arc-defconfig (attached as .config)
compiler: arc-elf-gcc (GCC) 9.3.0

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
# https://github.com/0day-ci/linux/commit/dbfb0d54ab82b9a27e28a8b850cfe1f1f542991a
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Aubrey-Li/sched-fair-select-idle-cpu-from-idle-cpumask-for-task-wakeup/20201021-230800 git checkout dbfb0d54ab82b9a27e28a8b850cfe1f1f542991a
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-9.3.0 make.cross ARCH=arc

If you fix the issue, kindly add following tag as appropriate

All errors (new ones prefixed by >>):

arc-elf-ld: kernel/sched/fair.o: in function `trigger_load_balance':

>> fair.c:(.text+0x764e): undefined reference to `update_idle_cpumask'
>> arc-elf-ld: fair.c:(.text+0x764e): undefined reference to `update_idle_cpumask'

arc-elf-ld: fair.c:(.text+0x7694): undefined reference to `update_idle_cpumask'
arc-elf-ld: fair.c:(.text+0x7694): undefined reference to `update_idle_cpumask'
arc-elf-ld: kernel/sched/idle.o: in function `set_next_task_idle':
idle.c:(.text+0x30): undefined reference to `update_idle_cpumask'
arc-elf-ld: kernel/sched/idle.o:idle.c:(.text+0x30): more undefined references to `update_idle_cpumask' follow

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

#4 lore raw
In reply to Aubrey Li

Hi,

kernel/sched/fair.c void __update_idle_core(struct rq *rq) · line 6026

Quoted 9 lines · Aubrey Li
kernel/sched/fair.c +1 -0
index 6b3b59cc51d6..088d1995594f 100644
@@ -6023,6 +6023,38 @@ void __update_idle_core(struct rq *rq)
      rcu_read_unlock();
 }
 
+static DEFINE_PER_CPU(bool, cpu_idle_state);

I would've expected this to be far less compact than a cpumask, but that's not the story readelf is telling me. Objdump tells me this is recouping some of the padding in .data..percpu, at least with the arm64 defconfig.

In any case this ought to be better wrt cacheline bouncing, which I suppose is what we ultimately want here.

Also, see rambling about init value below.

kernel/sched/fair.c static void nohz_balancer_kick(struct rq *rq) · line 10115

Quoted 10 lines
kernel/sched/fair.c +6 -0
@@ -10070,6 +10107,12 @@ static void nohz_balancer_kick(struct rq *rq)
      if (unlikely(rq->idle_balance))
              return;
 
+	/* The CPU is not in idle, update idle cpumask */
+	if (unlikely(sched_idle_cpu(cpu))) {
+		/* Allow SCHED_IDLE cpu as a wakeup target */
+		update_idle_cpumask(rq, true);
+	} else
+		update_idle_cpumask(rq, false);

This means that without CONFIG_NO_HZ_COMMON, a CPU going into idle will never be accounted as going out of it, right? Eventually the cpumask should end up full, which conceptually implements the previous behaviour of select_idle_cpu() but in a fairly roundabout way...

kernel/sched/topology.c sd_init(struct sched_domain_topology_level *tl, · line 1410

Quoted 9 lines
kernel/sched/topology.c +1 -0
index 9079d865a935..f14a6ef4de57 100644
@@ -1407,6 +1407,7 @@ sd_init(struct sched_domain_topology_level *tl,
              sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
              atomic_inc(&sd->shared->ref);
              atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
+		cpumask_copy(sds_idle_cpus(sd->shared), sched_domain_span(sd));

So at init you would have (single LLC for sake of simplicity):

\all cpu : cpu_idle_state[cpu] == false
cpumask_full(sds_idle_cpus) == true

IOW it'll require all CPUs to go idle at some point for these two states to be properly aligned. Should cpu_idle_state not then be init'd to 1?

This then happens again for hotplug, except that cpu_idle_state[cpu] may be either true or false when the sds_idle_cpus mask is reset to 1's.

author
#5 lore raw

Hi Valentin,

Thanks for your reply.

Quoted 12 lines · Valentin Schneider

Hi,

Quoted 8 lines · Aubrey Li
kernel/sched/fair.c +0 -0
index 6b3b59cc51d6..088d1995594f 100644
@@ -6023,6 +6023,38 @@ void __update_idle_core(struct rq *rq)
      rcu_read_unlock();
 }
 
Quoted 8 lines

kernel/sched/fair.c void __update_idle_core(struct rq *rq) · line 6026

Quoted 1 line
kernel/sched/fair.c +1 -0
+static DEFINE_PER_CPU(bool, cpu_idle_state);

I would've expected this to be far less compact than a cpumask, but that's not the story readelf is telling me. Objdump tells me this is recouping some of the padding in .data..percpu, at least with the arm64 defconfig.

In any case this ought to be better wrt cacheline bouncing, which I suppose is what we ultimately want here.

Yes, every CPU has a byte, so it may not be less than a cpumask. Probably I can put it into struct rq, do you have any better suggestions?

Quoted 7 lines

Also, see rambling about init value below.

Quoted 4 lines
kernel/sched/fair.c +0 -0
@@ -10070,6 +10107,12 @@ static void nohz_balancer_kick(struct rq *rq)
      if (unlikely(rq->idle_balance))
              return;
 
Quoted 11 lines

kernel/sched/fair.c static void nohz_balancer_kick(struct rq *rq) · line 10115

Quoted 6 lines
kernel/sched/fair.c +6 -0
+	/* The CPU is not in idle, update idle cpumask */
+	if (unlikely(sched_idle_cpu(cpu))) {
+		/* Allow SCHED_IDLE cpu as a wakeup target */
+		update_idle_cpumask(rq, true);
+	} else
+		update_idle_cpumask(rq, false);

This means that without CONFIG_NO_HZ_COMMON, a CPU going into idle will never be accounted as going out of it, right? Eventually the cpumask should end up full, which conceptually implements the previous behaviour of select_idle_cpu() but in a fairly roundabout way...

Maybe I can move it to scheduler_tick().

Quoted 13 lines

kernel/sched/topology.c sd_init(struct sched_domain_topology_level *tl, · line 1410

Quoted 10 lines
kernel/sched/topology.c +1 -0
index 9079d865a935..f14a6ef4de57 100644
@@ -1407,6 +1407,7 @@ sd_init(struct sched_domain_topology_level *tl,
              sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
              atomic_inc(&sd->shared->ref);
              atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
+		cpumask_copy(sds_idle_cpus(sd->shared), sched_domain_span(sd));

So at init you would have (single LLC for sake of simplicity):

Quoted 9 lines

\all cpu : cpu_idle_state[cpu] == false
cpumask_full(sds_idle_cpus) == true

IOW it'll require all CPUs to go idle at some point for these two states to be properly aligned. Should cpu_idle_state not then be init'd to 1?

This then happens again for hotplug, except that cpu_idle_state[cpu] may be either true or false when the sds_idle_cpus mask is reset to 1's.

okay, will refine this in the next version.

Thanks,
-Aubrey

#6 lore raw
Quoted 7 lines · Aubrey
Quoted 6 lines · Valentin Schneider
Quoted 1 line

+static DEFINE_PER_CPU(bool, cpu_idle_state);

I would've expected this to be far less compact than a cpumask, but that's not the story readelf is telling me. Objdump tells me this is recouping some of the padding in .data..percpu, at least with the arm64 defconfig.

Quoted 6 lines
Quoted 2 lines

In any case this ought to be better wrt cacheline bouncing, which I suppose is what we ultimately want here.

Yes, every CPU has a byte, so it may not be less than a cpumask. Probably I can put it into struct rq, do you have any better suggestions?

Not really, I'm afraid.

maintainer
#7 lore raw
In reply to Aubrey Li
Quoted 122 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask to nohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- set SCHED_IDLE cpu in idle cpumask to allow it as a wakeup target.

v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask with sched_domain_span(sd), nohz=off case remains the original behavior.

Cc Mel Gorman <[email protected]>
Cc Vincent Guittot <[email protected]>
Cc Qais Yousef <[email protected]>
Cc Valentin Schneider <[email protected]>
Cc Jiang Biao <[email protected]>
Cc Tim Chen <[email protected]>
---
 include/linux/sched/topology.h | 13 ++++++++++
 kernel/sched/fair.c            | 45 +++++++++++++++++++++++++++++++++-
 kernel/sched/idle.c            |  1 +
 kernel/sched/sched.h           |  1 +
 kernel/sched/topology.c        |  3 ++-
 5 files changed, 61 insertions(+), 2 deletions(-)
include/linux/sched/topology.h +13 -0
index fb11091129b3..43a641d26154 100644
@@ -65,8 +65,21 @@ struct sched_domain_shared {
        atomic_t        ref;
        atomic_t        nr_busy_cpus;
        int             has_idle_cores;
+       /*
+        * Span of all idle CPUs in this domain.
+        *
+        * NOTE: this field is variable length. (Allocated dynamically
+        * by attaching extra space to the end of the structure,
+        * depending on how many CPUs the kernel has booted up with)
+        */
+       unsigned long   idle_cpus_span[];
 };
 
+static inline struct cpumask *sds_idle_cpus(struct sched_domain_shared *sds)
+{
+       return to_cpumask(sds->idle_cpus_span);
+}
+
 struct sched_domain {
        /* These fields must be setup */
        struct sched_domain __rcu *parent;      /* top domain must be null terminated */
kernel/sched/fair.c +38 -1
index 6b3b59cc51d6..088d1995594f 100644
@@ -6023,6 +6023,38 @@ void __update_idle_core(struct rq *rq)
        rcu_read_unlock();
 }
 
+static DEFINE_PER_CPU(bool, cpu_idle_state);
+/*
+ * Update cpu idle state and record this information
+ * in sd_llc_shared->idle_cpus_span.
+ */
+void update_idle_cpumask(struct rq *rq, bool idle_state)
+{
+       struct sched_domain *sd;
+       int cpu = cpu_of(rq);
+
+       /*
+        * No need to update idle cpumask if the state
+        * does not change.
+        */
+       if (per_cpu(cpu_idle_state, cpu) == idle_state)
+               return;
+
+       per_cpu(cpu_idle_state, cpu) = idle_state;
+
+       rcu_read_lock();
+
+       sd = rcu_dereference(per_cpu(sd_llc, cpu));
+       if (!sd || !sd->shared)
+               goto unlock;
+       if (idle_state)
+               cpumask_set_cpu(cpu, sds_idle_cpus(sd->shared));
+       else
+               cpumask_clear_cpu(cpu, sds_idle_cpus(sd->shared));
+unlock:
+       rcu_read_unlock();
+}
+
 /*
  * Scan the entire LLC domain for idle cores; this dynamically switches off if
  * there are no idle cores left in the system; tracked through
@@ -6136,7 +6168,12 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
 
        time = cpu_clock(this);
 
-       cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
+       /*
+        * sched_domain_shared is set only at shared cache level,
+        * this works only because select_idle_cpu is called with
+        * sd_llc.
+        */
+       cpumask_and(cpus, sds_idle_cpus(sd->shared), p->cpus_ptr);
 
        for_each_cpu_wrap(cpu, cpus, target) {
                if (!--nr)

kernel/sched/fair.c static void nohz_balancer_kick(struct rq *rq) · line 10115

Quoted 9 lines
kernel/sched/fair.c +6 -0
@@ -10070,6 +10107,12 @@ static void nohz_balancer_kick(struct rq *rq)
        if (unlikely(rq->idle_balance))
                return;
 
+       /* The CPU is not in idle, update idle cpumask */
+       if (unlikely(sched_idle_cpu(cpu))) {
+               /* Allow SCHED_IDLE cpu as a wakeup target */
+               update_idle_cpumask(rq, true);
+       } else
+               update_idle_cpumask(rq, false);

update_idle_cpumask(rq, sched_idle_cpu(cpu)); ?

Quoted 51 lines
kernel/sched/fair.c +0 -0
        /*
         * We may be recently in ticked or tickless idle mode. At the first
         * busy tick after returning from idle, we will update the busy stats.
kernel/sched/idle.c +1 -0
index 1ae95b9150d3..ce1f929d7fbb 100644
@@ -405,6 +405,7 @@ static void put_prev_task_idle(struct rq *rq, struct task_struct *prev)
 static void set_next_task_idle(struct rq *rq, struct task_struct *next, bool first)
 {
        update_idle_core(rq);
+       update_idle_cpumask(rq, true);
        schedstat_inc(rq->sched_goidle);
 }
 
kernel/sched/sched.h +1 -0
index c82857e2e288..2d1655039ed5 100644
@@ -1069,6 +1069,7 @@ static inline void update_idle_core(struct rq *rq)
 #else
 static inline void update_idle_core(struct rq *rq) { }
 #endif
+void update_idle_cpumask(struct rq *rq, bool idle_state);
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
 
kernel/sched/topology.c +2 -2
index 9079d865a935..f14a6ef4de57 100644
@@ -1407,6 +1407,7 @@ sd_init(struct sched_domain_topology_level *tl,
                sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
                atomic_inc(&sd->shared->ref);
                atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
+               cpumask_copy(sds_idle_cpus(sd->shared), sched_domain_span(sd));
        }
 
        sd->private = sdd;
@@ -1769,7 +1770,7 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
 
                        *per_cpu_ptr(sdd->sd, j) = sd;
 
-                       sds = kzalloc_node(sizeof(struct sched_domain_shared),
+                       sds = kzalloc_node(sizeof(struct sched_domain_shared) + cpumask_size(),
                                        GFP_KERNEL, cpu_to_node(j));
                        if (!sds)
                                return -ENOMEM;
--

2.25.1

author
#8 lore raw
Quoted 126 lines · Vincent Guittot
Quoted 125 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask to nohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- set SCHED_IDLE cpu in idle cpumask to allow it as a wakeup target.

v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask with sched_domain_span(sd), nohz=off case remains the original behavior.

Cc Mel Gorman <[email protected]>
Cc Vincent Guittot <[email protected]>
Cc Qais Yousef <[email protected]>
Cc Valentin Schneider <[email protected]>
Cc Jiang Biao <[email protected]>
Cc Tim Chen <[email protected]>
---
 include/linux/sched/topology.h | 13 ++++++++++
 kernel/sched/fair.c            | 45 +++++++++++++++++++++++++++++++++-
 kernel/sched/idle.c            |  1 +
 kernel/sched/sched.h           |  1 +
 kernel/sched/topology.c        |  3 ++-
 5 files changed, 61 insertions(+), 2 deletions(-)
include/linux/sched/topology.h +13 -0
index fb11091129b3..43a641d26154 100644
@@ -65,8 +65,21 @@ struct sched_domain_shared {
        atomic_t        ref;
        atomic_t        nr_busy_cpus;
        int             has_idle_cores;
+       /*
+        * Span of all idle CPUs in this domain.
+        *
+        * NOTE: this field is variable length. (Allocated dynamically
+        * by attaching extra space to the end of the structure,
+        * depending on how many CPUs the kernel has booted up with)
+        */
+       unsigned long   idle_cpus_span[];
 };
 
+static inline struct cpumask *sds_idle_cpus(struct sched_domain_shared *sds)
+{
+       return to_cpumask(sds->idle_cpus_span);
+}
+
 struct sched_domain {
        /* These fields must be setup */
        struct sched_domain __rcu *parent;      /* top domain must be null terminated */
kernel/sched/fair.c +38 -1
index 6b3b59cc51d6..088d1995594f 100644
@@ -6023,6 +6023,38 @@ void __update_idle_core(struct rq *rq)
        rcu_read_unlock();
 }
 
+static DEFINE_PER_CPU(bool, cpu_idle_state);
+/*
+ * Update cpu idle state and record this information
+ * in sd_llc_shared->idle_cpus_span.
+ */
+void update_idle_cpumask(struct rq *rq, bool idle_state)
+{
+       struct sched_domain *sd;
+       int cpu = cpu_of(rq);
+
+       /*
+        * No need to update idle cpumask if the state
+        * does not change.
+        */
+       if (per_cpu(cpu_idle_state, cpu) == idle_state)
+               return;
+
+       per_cpu(cpu_idle_state, cpu) = idle_state;
+
+       rcu_read_lock();
+
+       sd = rcu_dereference(per_cpu(sd_llc, cpu));
+       if (!sd || !sd->shared)
+               goto unlock;
+       if (idle_state)
+               cpumask_set_cpu(cpu, sds_idle_cpus(sd->shared));
+       else
+               cpumask_clear_cpu(cpu, sds_idle_cpus(sd->shared));
+unlock:
+       rcu_read_unlock();
+}
+
 /*
  * Scan the entire LLC domain for idle cores; this dynamically switches off if
  * there are no idle cores left in the system; tracked through
@@ -6136,7 +6168,12 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
 
        time = cpu_clock(this);
 
-       cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
+       /*
+        * sched_domain_shared is set only at shared cache level,
+        * this works only because select_idle_cpu is called with
+        * sd_llc.
+        */
+       cpumask_and(cpus, sds_idle_cpus(sd->shared), p->cpus_ptr);
 
        for_each_cpu_wrap(cpu, cpus, target) {
                if (!--nr)
@@ -10070,6 +10107,12 @@ static void nohz_balancer_kick(struct rq *rq)
        if (unlikely(rq->idle_balance))
                return;
 
Quoted 8 lines

kernel/sched/fair.c static void nohz_balancer_kick(struct rq *rq) · line 10115

Quoted 6 lines
kernel/sched/fair.c +6 -0
+       /* The CPU is not in idle, update idle cpumask */
+       if (unlikely(sched_idle_cpu(cpu))) {
+               /* Allow SCHED_IDLE cpu as a wakeup target */
+               update_idle_cpumask(rq, true);
+       } else
+               update_idle_cpumask(rq, false);

update_idle_cpumask(rq, sched_idle_cpu(cpu)); ?

This looks much better, thanks! :)

#9 lore raw
In reply to Aubrey Li
Quoted 10 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

FWIW I gave this a spin on my arm64 desktop (Ampere eMAG, 32 core). I get some barely noticeable (AIUI not statistically significant for bench sched) changes for 100 iterations of:

| bench                              | metric   |   mean |     std |    q90 |    q99 |
|------------------------------------+----------+--------+---------+--------+--------|
| hackbench --loops 5000 --groups 1  | duration | -1.07% |  -2.23% | -0.88% | -0.25% |
| hackbench --loops 5000 --groups 2  | duration | -0.79% | +30.60% | -0.49% | -0.74% |
| hackbench --loops 5000 --groups 4  | duration | -0.54% |  +6.99% | -0.21% | -0.12% |
| perf bench sched pipe -T -l 100000 | ops/sec  | +1.05% |  -2.80% | -0.17% | +0.39% |

q90 & q99 being the 90th and 99th percentile.

Base was tip/sched/core at:
d8fcb81f1acf ("sched/fair: Check for idle core in wake_affine")

Quoted 19 lines

v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask to nohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- set SCHED_IDLE cpu in idle cpumask to allow it as a wakeup target.

v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask with sched_domain_span(sd), nohz=off case remains the original behavior.

Cc Mel Gorman <[email protected]>
Cc Vincent Guittot <[email protected]>
Cc Qais Yousef <[email protected]>
Cc Valentin Schneider <[email protected]>
Cc Jiang Biao <[email protected]>
Cc Tim Chen <[email protected]>
author
#10 lore raw
Quoted 24 lines · Valentin Schneider
Quoted 10 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

FWIW I gave this a spin on my arm64 desktop (Ampere eMAG, 32 core). I get some barely noticeable (AIUI not statistically significant for bench sched) changes for 100 iterations of:

| bench                              | metric   |   mean |     std |    q90 |    q99 |
|------------------------------------+----------+--------+---------+--------+--------|
| hackbench --loops 5000 --groups 1  | duration | -1.07% |  -2.23% | -0.88% | -0.25% |
| hackbench --loops 5000 --groups 2  | duration | -0.79% | +30.60% | -0.49% | -0.74% |
| hackbench --loops 5000 --groups 4  | duration | -0.54% |  +6.99% | -0.21% | -0.12% |
| perf bench sched pipe -T -l 100000 | ops/sec  | +1.05% |  -2.80% | -0.17% | +0.39% |
Quoted 4 lines

q90 & q99 being the 90th and 99th percentile.

Base was tip/sched/core at:
d8fcb81f1acf ("sched/fair: Check for idle core in wake_affine")

Thanks for the data, Valentin! So does the negative value mean improvement?

If so the data looks expected to me. As we set idle cpumask every time we enter idle, but only clear it at the tick frequency, so if the workload is not heavy enough, there could be a lot of idle during two ticks, so idle cpumask is almost equal to sched_domain_span(sd), which makes no difference.

But if the system load is heavy enough, CPU has few/no chance to enter idle, then idle cpumask can be cleared during tick, which makes the bit number in sds_idle_cpus(sd->shared) far less than the bit number in sched_domain_span(sd) if llc domain has large count of CPUs.

For example, if I run 4 x overcommit uperf on a system with 192 CPUs, I observed:
- default, the average of this_sd->avg_scan_cost is 223.12ns
- patch, the average of this_sd->avg_scan_cost is 63.4ns

And select_idle_cpu is called 7670253 times per second, so for every CPU the scan cost is saved (223.12 - 63.4) * 7670253 / 192 = 6.4ms. As a result, I saw uperf thoughput improved by 60+%.

Thanks,
-Aubrey

#11 lore raw
Quoted 25 lines · Aubrey
Quoted 24 lines · Valentin Schneider
Quoted 10 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

FWIW I gave this a spin on my arm64 desktop (Ampere eMAG, 32 core). I get some barely noticeable (AIUI not statistically significant for bench sched) changes for 100 iterations of:

| bench                              | metric   |   mean |     std |    q90 |    q99 |
|------------------------------------+----------+--------+---------+--------+--------|
| hackbench --loops 5000 --groups 1  | duration | -1.07% |  -2.23% | -0.88% | -0.25% |
| hackbench --loops 5000 --groups 2  | duration | -0.79% | +30.60% | -0.49% | -0.74% |
| hackbench --loops 5000 --groups 4  | duration | -0.54% |  +6.99% | -0.21% | -0.12% |
| perf bench sched pipe -T -l 100000 | ops/sec  | +1.05% |  -2.80% | -0.17% | +0.39% |
Quoted 7 lines
Quoted 4 lines

q90 & q99 being the 90th and 99th percentile.

Base was tip/sched/core at:
d8fcb81f1acf ("sched/fair: Check for idle core in wake_affine")

Thanks for the data, Valentin! So does the negative value mean improvement?

For hackbench yes (shorter is better); for perf bench sched no, since the metric here is ops/sec so higher is better.

That said, I (use a tool that) run a 2-sample Kolmogorov–Smirnov test against the two sample sets (tip/sched/core vs tip/sched/core+patch), and the p-value for perf sched bench is quite high (~0.9) which means we can't reject that both sample sets come from the same distribution; long story short we can't say whether the patch had a noticeable impact for that benchmark.

Quoted 10 lines

If so the data looks expected to me. As we set idle cpumask every time we enter idle, but only clear it at the tick frequency, so if the workload is not heavy enough, there could be a lot of idle during two ticks, so idle cpumask is almost equal to sched_domain_span(sd), which makes no difference.

But if the system load is heavy enough, CPU has few/no chance to enter idle, then idle cpumask can be cleared during tick, which makes the bit number in sds_idle_cpus(sd->shared) far less than the bit number in sched_domain_span(sd) if llc domain has large count of CPUs.

With hackbench -g 4 that's 160 tasks (against 32 CPUs, all under same LLC), although the work done by each task isn't much. I'll try bumping that a notch, or increasing the size of the messages.

Quoted 9 lines

For example, if I run 4 x overcommit uperf on a system with 192 CPUs, I observed:
- default, the average of this_sd->avg_scan_cost is 223.12ns
- patch, the average of this_sd->avg_scan_cost is 63.4ns

And select_idle_cpu is called 7670253 times per second, so for every CPU the scan cost is saved (223.12 - 63.4) * 7670253 / 192 = 6.4ms. As a result, I saw uperf thoughput improved by 60+%.

That's ~1.2s of "extra" CPU time per second, which sounds pretty cool.

I don't think I've ever played with uperf. I'll give that a shot someday.

Quoted 5 lines

Thanks,
-Aubrey

author
#12 lore raw
Quoted 56 lines · Valentin Schneider
Quoted 25 lines · Aubrey
Quoted 24 lines · Valentin Schneider
Quoted 10 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

FWIW I gave this a spin on my arm64 desktop (Ampere eMAG, 32 core). I get some barely noticeable (AIUI not statistically significant for bench sched) changes for 100 iterations of:

| bench                              | metric   |   mean |     std |    q90 |    q99 |
|------------------------------------+----------+--------+---------+--------+--------|
| hackbench --loops 5000 --groups 1  | duration | -1.07% |  -2.23% | -0.88% | -0.25% |
| hackbench --loops 5000 --groups 2  | duration | -0.79% | +30.60% | -0.49% | -0.74% |
| hackbench --loops 5000 --groups 4  | duration | -0.54% |  +6.99% | -0.21% | -0.12% |
| perf bench sched pipe -T -l 100000 | ops/sec  | +1.05% |  -2.80% | -0.17% | +0.39% |
Quoted 7 lines
Quoted 4 lines

q90 & q99 being the 90th and 99th percentile.

Base was tip/sched/core at:
d8fcb81f1acf ("sched/fair: Check for idle core in wake_affine")

Thanks for the data, Valentin! So does the negative value mean improvement?

For hackbench yes (shorter is better); for perf bench sched no, since the metric here is ops/sec so higher is better.

That said, I (use a tool that) run a 2-sample Kolmogorov–Smirnov test against the two sample sets (tip/sched/core vs tip/sched/core+patch), and the p-value for perf sched bench is quite high (~0.9) which means we can't reject that both sample sets come from the same distribution; long story short we can't say whether the patch had a noticeable impact for that benchmark.

Quoted 10 lines

If so the data looks expected to me. As we set idle cpumask every time we enter idle, but only clear it at the tick frequency, so if the workload is not heavy enough, there could be a lot of idle during two ticks, so idle cpumask is almost equal to sched_domain_span(sd), which makes no difference.

But if the system load is heavy enough, CPU has few/no chance to enter idle, then idle cpumask can be cleared during tick, which makes the bit number in sds_idle_cpus(sd->shared) far less than the bit number in sched_domain_span(sd) if llc domain has large count of CPUs.

Quoted 3 lines

With hackbench -g 4 that's 160 tasks (against 32 CPUs, all under same LLC), although the work done by each task isn't much. I'll try bumping that a notch, or increasing the size of the messages.

As long as the system is busy enough and not schedule on idle thread, then idle cpu mask will shrink tick by tick, and we'll see lower sd->avg_scan_cost.

This version of patch sets idle cpu bit every time it enters idle, so need heavy load for scheduler to not switch idle thread in.

I personally like the logic in the previous version, because in those versions,
- when cpu enters idle, cpuidle governor returns a flag "stop_tick"
- if tick is stopped, which indicates the CPU is not busy, and can be set idle in idle cpumask
- otherwise, the CPU is likely going to work very soon, so not set it in idle cpumask.

But apparently I missed "nohz=off" case in the previous implementation. For "nohz=off" case I selected to keep original behavior, which didn't content Mel. Probably I can refine it in the next version.

Do you have any suggestions?

Thanks,
-Aubrey

#13 lore raw
In reply to Aubrey Li
Quoted 17 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask to nohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- set SCHED_IDLE cpu in idle cpumask to allow it as a wakeup target.

Quoted 4 lines

v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask with sched_domain_span(sd), nohz=off case remains the original behavior.

Did you intend to put the patch version history in the commit message?

I started looking at this last week but got distracted. I see you already got enough reviews, so my 2p is that I faced some compilation issues:

aarch64-linux-gnu-ld: kernel/sched/idle.o: in function `set_next_task_idle':
/mnt/data/src/linux/kernel/sched/idle.c:405: undefined reference to `update_idle_cpumask'
aarch64-linux-gnu-ld: kernel/sched/fair.o: in function `nohz_balancer_kick':
/mnt/data/src/linux/kernel/sched/fair.c:10150: undefined reference to `update_idle_cpumask'
aarch64-linux-gnu-ld: /mnt/data/src/linux/kernel/sched/fair.c:10148: undefined reference to `update_idle_cpumask'

Because of the missing CONFIG_SCHED_SMT in my .config. I think update_idle_cpumask() should be defined unconditionally.

Thanks

--
Qais Yousef

Quoted 160 lines
Cc Mel Gorman <[email protected]>
Cc Vincent Guittot <[email protected]>
Cc Qais Yousef <[email protected]>
Cc Valentin Schneider <[email protected]>
Cc Jiang Biao <[email protected]>
Cc Tim Chen <[email protected]>
---
 include/linux/sched/topology.h | 13 ++++++++++
 kernel/sched/fair.c            | 45 +++++++++++++++++++++++++++++++++-
 kernel/sched/idle.c            |  1 +
 kernel/sched/sched.h           |  1 +
 kernel/sched/topology.c        |  3 ++-
 5 files changed, 61 insertions(+), 2 deletions(-)
include/linux/sched/topology.h +13 -0
index fb11091129b3..43a641d26154 100644
@@ -65,8 +65,21 @@ struct sched_domain_shared {
 	atomic_t	ref;
 	atomic_t	nr_busy_cpus;
 	int		has_idle_cores;
+	/*
+	 * Span of all idle CPUs in this domain.
+	 *
+	 * NOTE: this field is variable length. (Allocated dynamically
+	 * by attaching extra space to the end of the structure,
+	 * depending on how many CPUs the kernel has booted up with)
+	 */
+	unsigned long	idle_cpus_span[];
 };
 
+static inline struct cpumask *sds_idle_cpus(struct sched_domain_shared *sds)
+{
+	return to_cpumask(sds->idle_cpus_span);
+}
+
 struct sched_domain {
 	/* These fields must be setup */
 	struct sched_domain __rcu *parent;	/* top domain must be null terminated */
kernel/sched/fair.c +44 -1
index 6b3b59cc51d6..088d1995594f 100644
@@ -6023,6 +6023,38 @@ void __update_idle_core(struct rq *rq)
 	rcu_read_unlock();
 }
 
+static DEFINE_PER_CPU(bool, cpu_idle_state);
+/*
+ * Update cpu idle state and record this information
+ * in sd_llc_shared->idle_cpus_span.
+ */
+void update_idle_cpumask(struct rq *rq, bool idle_state)
+{
+	struct sched_domain *sd;
+	int cpu = cpu_of(rq);
+
+	/*
+	 * No need to update idle cpumask if the state
+	 * does not change.
+	 */
+	if (per_cpu(cpu_idle_state, cpu) == idle_state)
+		return;
+
+	per_cpu(cpu_idle_state, cpu) = idle_state;
+
+	rcu_read_lock();
+
+	sd = rcu_dereference(per_cpu(sd_llc, cpu));
+	if (!sd || !sd->shared)
+		goto unlock;
+	if (idle_state)
+		cpumask_set_cpu(cpu, sds_idle_cpus(sd->shared));
+	else
+		cpumask_clear_cpu(cpu, sds_idle_cpus(sd->shared));
+unlock:
+	rcu_read_unlock();
+}
+
 /*
  * Scan the entire LLC domain for idle cores; this dynamically switches off if
  * there are no idle cores left in the system; tracked through
@@ -6136,7 +6168,12 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
 
 	time = cpu_clock(this);
 
-	cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
+	/*
+	 * sched_domain_shared is set only at shared cache level,
+	 * this works only because select_idle_cpu is called with
+	 * sd_llc.
+	 */
+	cpumask_and(cpus, sds_idle_cpus(sd->shared), p->cpus_ptr);
 
 	for_each_cpu_wrap(cpu, cpus, target) {
 		if (!--nr)
@@ -10070,6 +10107,12 @@ static void nohz_balancer_kick(struct rq *rq)
 	if (unlikely(rq->idle_balance))
 		return;
 
+	/* The CPU is not in idle, update idle cpumask */
+	if (unlikely(sched_idle_cpu(cpu))) {
+		/* Allow SCHED_IDLE cpu as a wakeup target */
+		update_idle_cpumask(rq, true);
+	} else
+		update_idle_cpumask(rq, false);
 	/*
 	 * We may be recently in ticked or tickless idle mode. At the first
 	 * busy tick after returning from idle, we will update the busy stats.
kernel/sched/idle.c +1 -0
index 1ae95b9150d3..ce1f929d7fbb 100644
@@ -405,6 +405,7 @@ static void put_prev_task_idle(struct rq *rq, struct task_struct *prev)
 static void set_next_task_idle(struct rq *rq, struct task_struct *next, bool first)
 {
 	update_idle_core(rq);
+	update_idle_cpumask(rq, true);
 	schedstat_inc(rq->sched_goidle);
 }
 
kernel/sched/sched.h +1 -0
index c82857e2e288..2d1655039ed5 100644
@@ -1069,6 +1069,7 @@ static inline void update_idle_core(struct rq *rq)
 #else
 static inline void update_idle_core(struct rq *rq) { }
 #endif
+void update_idle_cpumask(struct rq *rq, bool idle_state);
 
 DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
 
kernel/sched/topology.c +2 -1
index 9079d865a935..f14a6ef4de57 100644
@@ -1407,6 +1407,7 @@ sd_init(struct sched_domain_topology_level *tl,
 		sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
 		atomic_inc(&sd->shared->ref);
 		atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
+		cpumask_copy(sds_idle_cpus(sd->shared), sched_domain_span(sd));
 	}
 
 	sd->private = sdd;
@@ -1769,7 +1770,7 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
 
 			*per_cpu_ptr(sdd->sd, j) = sd;
 
-			sds = kzalloc_node(sizeof(struct sched_domain_shared),
+			sds = kzalloc_node(sizeof(struct sched_domain_shared) + cpumask_size(),
 					GFP_KERNEL, cpu_to_node(j));
 			if (!sds)
 				return -ENOMEM;
Signature · 1 line
2.25.1
author
#14 lore raw
Quoted 28 lines · Qais Yousef
Quoted 17 lines · Aubrey Li

From: Aubrey Li <[email protected]>

Added idle cpumask to track idle cpus in sched domain. When a CPU enters idle, its corresponding bit in the idle cpumask will be set, and when the CPU exits idle, its bit will be cleared.

When a task wakes up to select an idle cpu, scanning idle cpumask has low cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.

v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask to nohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- set SCHED_IDLE cpu in idle cpumask to allow it as a wakeup target.

Quoted 4 lines

v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask with sched_domain_span(sd), nohz=off case remains the original behavior.

Did you intend to put the patch version history in the commit message?

I started looking at this last week but got distracted. I see you already got enough reviews, so my 2p is that I faced some compilation issues:

Quoted 8 lines

aarch64-linux-gnu-ld: kernel/sched/idle.o: in function `set_next_task_idle':
/mnt/data/src/linux/kernel/sched/idle.c:405: undefined reference to `update_idle_cpumask'
aarch64-linux-gnu-ld: kernel/sched/fair.o: in function `nohz_balancer_kick':
/mnt/data/src/linux/kernel/sched/fair.c:10150: undefined reference to `update_idle_cpumask'
aarch64-linux-gnu-ld: /mnt/data/src/linux/kernel/sched/fair.c:10148: undefined reference to `update_idle_cpumask'

Because of the missing CONFIG_SCHED_SMT in my .config. I think update_idle_cpumask() should be defined unconditionally.

Thanks to point this out timely, :), I'll fix it in the next version.

-Aubrey