Skip to contentSkip to conversation

sched/fair: Cache NUMA node statistics to avoid O(N) scanning

PATCH Superseded Qiliang Yuan 3 participants 8 messages Jan 22 – Jan 27 Scheduler

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched/fair: Cache NUMA node statistics to avoid O(N) scanning

Optimize update_numa_stats() by leveraging pre-calculated group statistics from the load balancer hierarchy. This reduces the complexity of NUMA balancing overhead from O(CPUs_per_node) to O(1) in the hot path when stats are fresh.

---
 kernel/sched/fair.c  | 35 +++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h |  7 +++++++
 2 files changed, 42 insertions(+)
kernel/sched/fair.c +35 -0
index e71302282671..dc46262bd227 100644
@@ -2099,11 +2099,36 @@ static void update_numa_stats(struct task_numa_env *env,
 			      bool find_idle)
 {
 	int cpu, idle_core = -1;
+	struct sched_domain *sd;
+	struct sched_group *sg;
 
 	memset(ns, 0, sizeof(*ns));
 	ns->idle_cpu = -1;
 
 	rcu_read_lock();
+	/* Algorithmic Optimization: Avoid O(N) scan by using cached stats from load balancer */
+	sd = rcu_dereference(per_cpu(sd_numa, env->src_cpu));
+	if (sd && !find_idle) {
+		sg = sd->groups;
+		do {
+			/* Check if this group corresponds to the node we are interested in */
+			if (cpumask_test_cpu(cpumask_first(cpumask_of_node(nid)), sched_group_span(sg))) {
+				/* Use cached stats if they are recent enough (e.g. within 10ms) */
+				if (time_before(jiffies, sg->sgc->stats_update + msecs_to_jiffies(10))) {
+					ns->load = sg->sgc->load;
+					ns->runnable = sg->sgc->runnable;
+					ns->util = sg->sgc->util;
+					ns->nr_running = sg->sgc->nr_running;
+					ns->compute_capacity = sg->sgc->capacity;
+					rcu_read_unlock();
+					goto skip_scan;
+				}
+				break;
+			}
+			sg = sg->next;
+		} while (sg != sd->groups);
+	}
+
 	for_each_cpu(cpu, cpumask_of_node(nid)) {
 		struct rq *rq = cpu_rq(cpu);
 
@@ -2126,6 +2151,7 @@ static void update_numa_stats(struct task_numa_env *env,
 	}
 	rcu_read_unlock();
 
+skip_scan:
 	ns->weight = cpumask_weight(cpumask_of_node(nid));
 
 	ns->node_type = numa_classify(env->imbalance_pct, ns);
@@ -10488,6 +10514,15 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	if (sgs->group_type == group_overloaded)
 		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
 				sgs->group_capacity;
+
+	/* Algorithmic Optimization: Cache group stats for O(1) NUMA lookups */
+	if (env->sd->flags & SD_NUMA) {
+		group->sgc->nr_running = sgs->sum_h_nr_running;
+		group->sgc->load = sgs->group_load;
+		group->sgc->util = sgs->group_util;
+		group->sgc->runnable = sgs->group_runnable;
+		WRITE_ONCE(group->sgc->stats_update, jiffies);
+	}
 }
 
 /**
kernel/sched/sched.h +7 -0
index d30cca6870f5..81160790993e 100644
@@ -2105,6 +2105,13 @@ struct sched_group_capacity {
 
 	int			id;
 
+	/* O(1) NUMA stats cache */
+	unsigned long		nr_running;
+	unsigned long		load;
+	unsigned long		util;
+	unsigned long		runnable;
+	unsigned long		stats_update;
+
 	unsigned long		cpumask[];		/* Balance mask */
 };
 
Signature · 1 line
2.51.0
#1 lore raw

PATCH 1/1 sched/numa: Optimize NUMA placement algorithm complexity from O(Nodes) to O(Active_Nodes)

On systems with a large number of NUMA nodes, periodic scanning of all online nodes for fault decay and task placement becomes a bottleneck.

This patch introduces 'numa_faults_nodes_mask' in task_struct to track nodes where the task has actually incurred faults. By replacing for_each_online_node() with for_each_node_mask(), we reduce the search space and decay overhead, especially for tasks whose memory footprint is localized to a few nodes.

---
 include/linux/sched.h |  1 +
 kernel/sched/fair.c   | 18 +++++++++++++++---
 2 files changed, 16 insertions(+), 3 deletions(-)
include/linux/sched.h +1 -0
index d395f2810fac..2c426e10c9d5 100644
@@ -1397,6 +1397,7 @@ struct task_struct {
 	 */
 	unsigned long			*numa_faults;
 	unsigned long			total_numa_faults;
+	nodemask_t			numa_faults_nodes_mask;
 
 	/*
 	 * numa_faults_locality tracks if faults recorded during the last
kernel/sched/fair.c +15 -3
index e71302282671..44cf35c43684 100644
@@ -2538,8 +2538,9 @@ static int task_numa_migrate(struct task_struct *p)
 	 */
 	ng = deref_curr_numa_group(p);
 	if (env.best_cpu == -1 || (ng && ng->active_nodes > 1)) {
-		for_each_node_state(nid, N_CPU) {
-			if (nid == env.src_nid || nid == p->numa_preferred_nid)
+		for_each_node_mask(nid, p->numa_faults_nodes_mask) {
+			if (nid == env.src_nid || nid == p->numa_preferred_nid ||
+			    !node_state(nid, N_CPU))
 				continue;
 
 			dist = node_distance(env.src_nid, env.dst_nid);
@@ -2892,11 +2893,12 @@ static void task_numa_placement(struct task_struct *p)
 	}
 
 	/* Find the node with the highest number of faults */
-	for_each_online_node(nid) {
+	for_each_node_mask(nid, p->numa_faults_nodes_mask) {
 		/* Keep track of the offsets in numa_faults array */
 		int mem_idx, membuf_idx, cpu_idx, cpubuf_idx;
 		unsigned long faults = 0, group_faults = 0;
 		int priv;
+		bool node_has_faults = false;
 
 		for (priv = 0; priv < NR_NUMA_HINT_FAULT_TYPES; priv++) {
 			long diff, f_diff, f_weight;
@@ -2928,6 +2930,10 @@ static void task_numa_placement(struct task_struct *p)
 			p->numa_faults[cpu_idx] += f_diff;
 			faults += p->numa_faults[mem_idx];
 			p->total_numa_faults += diff;
+
+			if (p->numa_faults[mem_idx] || p->numa_faults[cpu_idx])
+				node_has_faults = true;
+
 			if (ng) {
 				/*
 				 * safe because we can only change our own group
@@ -2952,6 +2958,9 @@ static void task_numa_placement(struct task_struct *p)
 			max_faults = group_faults;
 			max_nid = nid;
 		}
+
+		if (!node_has_faults)
+			node_clear(nid, p->numa_faults_nodes_mask);
 	}
 
 	/* Cannot migrate task to CPU-less node */
@@ -3209,6 +3218,8 @@ void task_numa_fault(int last_cpupid, int mem_node, int pages, int flags)
 
 	p->numa_faults[task_faults_idx(NUMA_MEMBUF, mem_node, priv)] += pages;
 	p->numa_faults[task_faults_idx(NUMA_CPUBUF, cpu_node, priv)] += pages;
+	node_set(mem_node, p->numa_faults_nodes_mask);
+	node_set(cpu_node, p->numa_faults_nodes_mask);
 	p->numa_faults_locality[local] += pages;
 }
 
@@ -3545,6 +3556,7 @@ void init_numa_balancing(u64 clone_flags, struct task_struct *p)
 	/* Protect against double add, see task_tick_numa and task_numa_work */
 	p->numa_work.next		= &p->numa_work;
 	p->numa_faults			= NULL;
+	nodes_clear(p->numa_faults_nodes_mask);
 	p->numa_pages_migrated		= 0;
 	p->total_numa_faults		= 0;
 	RCU_INIT_POINTER(p->numa_group, NULL);
Signature · 1 line
2.51.0
#2 lore raw

PATCH v2 1/1 sched/fair: Cache NUMA node statistics to avoid O(N) scanning

In reply to Qiliang Yuan

Optimize update_numa_stats() by leveraging pre-calculated group statistics from the load balancer hierarchy. This reduces the complexity of NUMA balancing overhead from O(CPUs_per_node) to O(1) in the hot path when stats are fresh.

---
 kernel/sched/fair.c  | 35 +++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h |  7 +++++++
 2 files changed, 42 insertions(+)
kernel/sched/fair.c +35 -0
index e71302282671..dc46262bd227 100644
@@ -2099,11 +2099,36 @@ static void update_numa_stats(struct task_numa_env *env,
 			      bool find_idle)
 {
 	int cpu, idle_core = -1;
+	struct sched_domain *sd;
+	struct sched_group *sg;
 
 	memset(ns, 0, sizeof(*ns));
 	ns->idle_cpu = -1;
 
 	rcu_read_lock();
+	/* Algorithmic Optimization: Avoid O(N) scan by using cached stats from load balancer */
+	sd = rcu_dereference(per_cpu(sd_numa, env->src_cpu));
+	if (sd && !find_idle) {
+		sg = sd->groups;
+		do {
+			/* Check if this group corresponds to the node we are interested in */
+			if (cpumask_test_cpu(cpumask_first(cpumask_of_node(nid)), sched_group_span(sg))) {
+				/* Use cached stats if they are recent enough (e.g. within 10ms) */
+				if (time_before(jiffies, sg->sgc->stats_update + msecs_to_jiffies(10))) {
+					ns->load = sg->sgc->load;
+					ns->runnable = sg->sgc->runnable;
+					ns->util = sg->sgc->util;
+					ns->nr_running = sg->sgc->nr_running;
+					ns->compute_capacity = sg->sgc->capacity;
+					rcu_read_unlock();
+					goto skip_scan;
+				}
+				break;
+			}
+			sg = sg->next;
+		} while (sg != sd->groups);
+	}
+
 	for_each_cpu(cpu, cpumask_of_node(nid)) {
 		struct rq *rq = cpu_rq(cpu);
 
@@ -2126,6 +2151,7 @@ static void update_numa_stats(struct task_numa_env *env,
 	}
 	rcu_read_unlock();
 
+skip_scan:
 	ns->weight = cpumask_weight(cpumask_of_node(nid));
 
 	ns->node_type = numa_classify(env->imbalance_pct, ns);
@@ -10488,6 +10514,15 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	if (sgs->group_type == group_overloaded)
 		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
 				sgs->group_capacity;
+
+	/* Algorithmic Optimization: Cache group stats for O(1) NUMA lookups */
+	if (env->sd->flags & SD_NUMA) {
+		group->sgc->nr_running = sgs->sum_h_nr_running;
+		group->sgc->load = sgs->group_load;
+		group->sgc->util = sgs->group_util;
+		group->sgc->runnable = sgs->group_runnable;
+		WRITE_ONCE(group->sgc->stats_update, jiffies);
+	}
 }
 
 /**
kernel/sched/sched.h +7 -0
index d30cca6870f5..81160790993e 100644
@@ -2105,6 +2105,13 @@ struct sched_group_capacity {
 
 	int			id;
 
+	/* O(1) NUMA stats cache */
+	unsigned long		nr_running;
+	unsigned long		load;
+	unsigned long		util;
+	unsigned long		runnable;
+	unsigned long		stats_update;
+
 	unsigned long		cpumask[];		/* Balance mask */
 };
 
Signature · 1 line
2.51.0
#3 lore raw

Hello Qiliang,

Quoted 3 lines · Qiliang Yuan

Optimize update_numa_stats() by leveraging pre-calculated group statistics from the load balancer hierarchy. This reduces the complexity of NUMA balancing overhead from O(CPUs_per_node) to O(1) in the hot path

Is it a hot-path? How much of a difference does this make? Some benchmark numbers to support this would be good.

Quoted 18 lines

when stats are fresh.

---
 kernel/sched/fair.c  | 35 +++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h |  7 +++++++
 2 files changed, 42 insertions(+)
kernel/sched/fair.c +1 -0
index e71302282671..dc46262bd227 100644
@@ -2099,11 +2099,36 @@ static void update_numa_stats(struct task_numa_env *env,
 			      bool find_idle)
 {
 	int cpu, idle_core = -1;
+	struct sched_domain *sd;

kernel/sched/fair.c static void update_numa_stats(struct task_numa_env *env, · line 2112

Quoted 10 lines
kernel/sched/fair.c +5 -0
+	struct sched_group *sg;
 
 	memset(ns, 0, sizeof(*ns));
 	ns->idle_cpu = -1;
 
 	rcu_read_lock();
+	/* Algorithmic Optimization: Avoid O(N) scan by using cached stats from load balancer */
+	sd = rcu_dereference(per_cpu(sd_numa, env->src_cpu));
+	if (sd && !find_idle) {
+		sg = sd->groups;

The first group is always the local group and should contain the CPU you are are looking at. No need for the do-while.

kernel/sched/fair.c static void update_numa_stats(struct task_numa_env *env, · line 2115

Quoted 3 lines
kernel/sched/fair.c +3 -0
+		do {
+			/* Check if this group corresponds to the node we are interested in */
+			if (cpumask_test_cpu(cpumask_first(cpumask_of_node(nid)), sched_group_span(sg))) {

How often is this true? How much benefit are you seeing from this?

kernel/sched/fair.c static void update_numa_stats(struct task_numa_env *env, · line 2122

Quoted 7 lines
kernel/sched/fair.c +7 -0
+				/* Use cached stats if they are recent enough (e.g. within 10ms) */
+				if (time_before(jiffies, sg->sgc->stats_update + msecs_to_jiffies(10))) {
+					ns->load = sg->sgc->load;
+					ns->runnable = sg->sgc->runnable;
+					ns->util = sg->sgc->util;
+					ns->nr_running = sg->sgc->nr_running;
+					ns->compute_capacity = sg->sgc->capacity;

Nothing protects a parallel updates to these variables from say a newidle balance and you can see some inconsistent state here.

Quoted 13 lines
kernel/sched/fair.c +9 -0
+					rcu_read_unlock();
+					goto skip_scan;
+				}
+				break;
+			}
+			sg = sg->next;
+		} while (sg != sd->groups);
+	}
+
 	for_each_cpu(cpu, cpumask_of_node(nid)) {
 		struct rq *rq = cpu_rq(cpu);
 

kernel/sched/fair.c static void update_numa_stats(struct task_numa_env *env, · line 2154

Quoted 4 lines
kernel/sched/fair.c +1 -0
@@ -2126,6 +2151,7 @@ static void update_numa_stats(struct task_numa_env *env,
 	}
 	rcu_read_unlock();
 
+skip_scan:

You can move that label before the unlock and save on that unlock before jump.

Quoted 5 lines
kernel/sched/fair.c +0 -0
 	ns->weight = cpumask_weight(cpumask_of_node(nid));
 
 	ns->node_type = numa_classify(env->imbalance_pct, ns);
@@ -10488,6 +10514,15 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	if (sgs->group_type == group_overloaded)

kernel/sched/fair.c static inline void update_sg_lb_stats(struct lb_env *env, · line 10524

Quoted 10 lines
kernel/sched/fair.c +8 -0
 		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
 				sgs->group_capacity;
+
+	/* Algorithmic Optimization: Cache group stats for O(1) NUMA lookups */
+	if (env->sd->flags & SD_NUMA) {
+		group->sgc->nr_running = sgs->sum_h_nr_running;
+		group->sgc->load = sgs->group_load;
+		group->sgc->util = sgs->group_util;
+		group->sgc->runnable = sgs->group_runnable;
+		WRITE_ONCE(group->sgc->stats_update, jiffies);

Again, nothing protects concurrent updates from newidle context. Is it okay to see some intermediate state at update_numa_stats()?

Quoted 9 lines
kernel/sched/fair.c +1 -0
+	}
 }
 
 /**
kernel/sched/sched.h +0 -0
index d30cca6870f5..81160790993e 100644

kernel/sched/sched.h struct sched_group_capacity { · line 2114

Quoted 10 lines
kernel/sched/sched.h +7 -0
@@ -2105,6 +2105,13 @@ struct sched_group_capacity {
 
 	int			id;
 
+	/* O(1) NUMA stats cache */
+	unsigned long		nr_running;
+	unsigned long		load;
+	unsigned long		util;
+	unsigned long		runnable;
+	unsigned long		stats_update;
+

40 more bytes that'll only be used by the groups of one SD_NUMA domain. I believe there should be a better way to do this than burdening everyone.

Quoted 3 lines
kernel/sched/sched.h +0 -0
 	unsigned long		cpumask[];		/* Balance mask */
 };
 
Signature · 2 lines
Thanks and Regards,
Prateek
#4 lore raw

PATCH v3 1/1 sched/fair: Cache NUMA node statistics to avoid O(N) scanning

Optimize update_numa_stats() by leveraging pre-calculated node statistics cached during the load balancing process. This reduces the complexity of NUMA balancing overhead from O(CPUs_per_node) to O(1) when statistics for the source node are fresh.

---
 kernel/sched/fair.c | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
kernel/sched/fair.c +44 -0
index e71302282671..070b61f65b6d 100644
@@ -2094,6 +2094,17 @@ static inline int numa_idle_core(int idle_core, int cpu)
  * borrows code and logic from update_sg_lb_stats but sharing a
  * common implementation is impractical.
  */
+struct numa_stats_cache {
+	unsigned long load;
+	unsigned long runnable;
+	unsigned long util;
+	unsigned long nr_running;
+	unsigned long capacity;
+	unsigned long last_update;
+};
+
+static struct numa_stats_cache node_stats_cache[MAX_NUMNODES];
+
 static void update_numa_stats(struct task_numa_env *env,
 			      struct numa_stats *ns, int nid,
 			      bool find_idle)
@@ -2104,6 +2115,24 @@ static void update_numa_stats(struct task_numa_env *env,
 	ns->idle_cpu = -1;
 
 	rcu_read_lock();
+	/*
+	 * Algorithmic Optimization: Avoid O(N) scan by using cached stats.
+	 * Only applicable for the source node where we don't need to find
+	 * an idle CPU.
+	 */
+	if (!find_idle && nid == env->src_nid) {
+		struct numa_stats_cache *cache = &node_stats_cache[nid];
+
+		if (time_before(jiffies, cache->last_update + msecs_to_jiffies(10))) {
+			ns->load = READ_ONCE(cache->load);
+			ns->runnable = READ_ONCE(cache->runnable);
+			ns->util = READ_ONCE(cache->util);
+			ns->nr_running = READ_ONCE(cache->nr_running);
+			ns->compute_capacity = READ_ONCE(cache->capacity);
+			goto skip_scan;
+		}
+	}
+
 	for_each_cpu(cpu, cpumask_of_node(nid)) {
 		struct rq *rq = cpu_rq(cpu);
 
@@ -2124,6 +2153,8 @@ static void update_numa_stats(struct task_numa_env *env,
 			idle_core = numa_idle_core(idle_core, cpu);
 		}
 	}
+
+skip_scan:
 	rcu_read_unlock();
 
 	ns->weight = cpumask_weight(cpumask_of_node(nid));
@@ -10488,6 +10519,19 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	if (sgs->group_type == group_overloaded)
 		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
 				sgs->group_capacity;
+
+	/* Algorithmic Optimization: Cache node stats for O(1) NUMA lookups */
+	if (env->sd->flags & SD_NUMA) {
+		int nid = cpu_to_node(cpumask_first(sched_group_span(group)));
+		struct numa_stats_cache *cache = &node_stats_cache[nid];
+
+		WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
+		WRITE_ONCE(cache->load, sgs->group_load);
+		WRITE_ONCE(cache->util, sgs->group_util);
+		WRITE_ONCE(cache->runnable, sgs->group_runnable);
+		WRITE_ONCE(cache->capacity, sgs->group_capacity);
+		WRITE_ONCE(cache->last_update, jiffies);
+	}
 }
 
 /**
Signature · 1 line
2.51.0
#5 lore raw
kernel test robot noticed the following build errors:

Hi Qiliang,

kernel test robot noticed the following build errors:

[auto build test ERROR on tip/sched/core]
[also build test ERROR on linus/master v6.19-rc7 next-20260123] [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#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Qiliang-Yuan/sched-fair-Cache-NUMA-node-statistics-to-avoid-O-N-scanning/20260126-190546
base:   tip/sched/core
patch link:    https://lore.kernel.org/r/20260126110250.1060512-1-realwujing%40gmail.com
patch subject: [PATCH v3] sched/fair: Cache NUMA node statistics to avoid O(N) scanning
config: nios2-allnoconfig (https://download.01.org/0day-ci/archive/20260126/[email protected]/config)
compiler: nios2-linux-gcc (GCC) 11.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260126/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

kernel/sched/fair.c: In function 'update_sg_lb_stats':

>> kernel/sched/fair.c:10524:51: error: 'node_stats_cache' undeclared (first use in this function); did you mean 'numa_stats_cache'?
   10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
         |                                                   ^~~~~~~~~~~~~~~~
         |                                                   numa_stats_cache
   kernel/sched/fair.c:10524:51: note: each undeclared identifier is reported only once for each function it appears in
   In file included from <command-line>:
>> kernel/sched/fair.c:10526:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10526:17: note: in expansion of macro 'WRITE_ONCE'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                 ^~~~~~~~~~
>> kernel/sched/fair.c:10526:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10526:17: note: in expansion of macro 'WRITE_ONCE'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                 ^~~~~~~~~~
>> kernel/sched/fair.c:10526:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10526:17: note: in expansion of macro 'WRITE_ONCE'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                 ^~~~~~~~~~
>> kernel/sched/fair.c:10526:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10526:17: note: in expansion of macro 'WRITE_ONCE'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                 ^~~~~~~~~~
>> kernel/sched/fair.c:10526:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10526:17: note: in expansion of macro 'WRITE_ONCE'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                 ^~~~~~~~~~
   In file included from ./arch/nios2/include/generated/asm/rwonce.h:1,
                    from include/linux/compiler.h:380,
                    from include/linux/cleanup.h:5,
                    from include/linux/irqflags.h:17,
                    from include/asm-generic/cmpxchg.h:15,
                    from ./arch/nios2/include/generated/asm/cmpxchg.h:1,
                    from include/asm-generic/atomic.h:12,
                    from ./arch/nios2/include/generated/asm/atomic.h:1,
                    from include/linux/atomic.h:7,
                    from include/linux/cpumask.h:10,
                    from include/linux/energy_model.h:4,
                    from kernel/sched/fair.c:23:
>> kernel/sched/fair.c:10526:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                                 ^~
   include/asm-generic/rwonce.h:55:27: note: in definition of macro '__WRITE_ONCE'
      55 |         *(volatile typeof(x) *)&(x) = (val);                            \
         |                           ^
   kernel/sched/fair.c:10526:17: note: in expansion of macro 'WRITE_ONCE'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                 ^~~~~~~~~~
>> kernel/sched/fair.c:10526:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                                 ^~
   include/asm-generic/rwonce.h:55:34: note: in definition of macro '__WRITE_ONCE'
      55 |         *(volatile typeof(x) *)&(x) = (val);                            \
         |                                  ^
   kernel/sched/fair.c:10526:17: note: in expansion of macro 'WRITE_ONCE'
   10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
         |                 ^~~~~~~~~~
   In file included from <command-line>:
   kernel/sched/fair.c:10527:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10527:17: note: in expansion of macro 'WRITE_ONCE'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                 ^~~~~~~~~~
   kernel/sched/fair.c:10527:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10527:17: note: in expansion of macro 'WRITE_ONCE'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                 ^~~~~~~~~~
   kernel/sched/fair.c:10527:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10527:17: note: in expansion of macro 'WRITE_ONCE'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                 ^~~~~~~~~~
   kernel/sched/fair.c:10527:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |         ^~~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:9: note: in expansion of macro 'compiletime_assert'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |         ^~~~~~~~~~~~~~~~~~
   include/asm-generic/rwonce.h:36:28: note: in expansion of macro '__native_word'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                            ^~~~~~~~~~~~~
   include/asm-generic/rwonce.h:60:9: note: in expansion of macro 'compiletime_assert_rwonce_type'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   kernel/sched/fair.c:10527:17: note: in expansion of macro 'WRITE_ONCE'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                 ^~~~~~~~~~
   kernel/sched/fair.c:10527:33: error: invalid use of undefined type 'struct numa_stats_cache'
   10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
         |                                 ^~
   include/linux/compiler_types.h:629:23: note: in definition of macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~

include/linux/compiler_types.h:649:9: note: in expansion of macro '_compiletime_assert'

vim +10524 kernel/sched/fair.c

10426
10427 /**
10428 * update_sg_lb_stats - Update sched_group's statistics for load balancing.
10429 * @env: The load balancing environment.
10430 * @sds: Load-balancing data with statistics of the local group.
10431 * @group: sched_group whose statistics are to be updated.
10432 * @sgs: variable to hold the statistics for this group.
10433 * @sg_overloaded: sched_group is overloaded
10434 * @sg_overutilized: sched_group is overutilized
10435 */
10436 static inline void update_sg_lb_stats(struct lb_env *env,

 10437					      struct sd_lb_stats *sds,
 10438					      struct sched_group *group,
 10439					      struct sg_lb_stats *sgs,
 10440					      bool *sg_overloaded,
 10441					      bool *sg_overutilized)

10442 {
10443 int i, nr_running, local_group, sd_flags = env->sd->flags;
10444 bool balancing_at_rd = !env->sd->parent;
10445
10446 memset(sgs, 0, sizeof(*sgs));
10447
10448 local_group = group == sds->local;
10449
10450 for_each_cpu_and(i, sched_group_span(group), env->cpus) {
10451 struct rq *rq = cpu_rq(i);
10452 unsigned long load = cpu_load(rq);
10453
10454 sgs->group_load += load;
10455 sgs->group_util += cpu_util_cfs(i);
10456 sgs->group_runnable += cpu_runnable(rq);
10457 sgs->sum_h_nr_running += rq->cfs.h_nr_runnable;
10458
10459 nr_running = rq->nr_running;
10460 sgs->sum_nr_running += nr_running;
10461
10462 if (cpu_overutilized(i))
10463 *sg_overutilized = 1;
10464
10465 /*
10466 * No need to call idle_cpu() if nr_running is not 0
10467 */
10468 if (!nr_running && idle_cpu(i)) {
10469 sgs->idle_cpus++;
10470 /* Idle cpu can't have misfit task */
10471 continue;
10472 }
10473
10474 /* Overload indicator is only updated at root domain */
10475 if (balancing_at_rd && nr_running > 1)
10476 *sg_overloaded = 1;
10477
10478 #ifdef CONFIG_NUMA_BALANCING
10479 /* Only fbq_classify_group() uses this to classify NUMA groups */
10480 if (sd_flags & SD_NUMA) {
10481 sgs->nr_numa_running += rq->nr_numa_running;
10482 sgs->nr_preferred_running += rq->nr_preferred_running;
10483 }
10484 #endif
10485 if (local_group)
10486 continue;
10487
10488 if (sd_flags & SD_ASYM_CPUCAPACITY) {
10489 /* Check for a misfit task on the cpu */
10490 if (sgs->group_misfit_task_load < rq->misfit_task_load) {
10491 sgs->group_misfit_task_load = rq->misfit_task_load;
10492 *sg_overloaded = 1;
10493 }
10494 } else if (env->idle && sched_reduced_capacity(rq, env->sd)) {
10495 /* Check for a task running on a CPU with reduced capacity */
10496 if (sgs->group_misfit_task_load < load)
10497 sgs->group_misfit_task_load = load;
10498 }
10499 }
10500
10501 sgs->group_capacity = group->sgc->capacity;
10502
10503 sgs->group_weight = group->group_weight;
10504
10505 /* Check if dst CPU is idle and preferred to this group */
10506 if (!local_group && env->idle && sgs->sum_h_nr_running &&
10507 sched_group_asym(env, sgs, group))
10508 sgs->group_asym_packing = 1;
10509
10510 /* Check for loaded SMT group to be balanced to dst CPU */
10511 if (!local_group && smt_balance(env, sgs, group))
10512 sgs->group_smt_balance = 1;
10513
10514 sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs);
10515
10516 /* Computing avg_load makes sense only when group is overloaded */
10517 if (sgs->group_type == group_overloaded)
10518 sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
10519 sgs->group_capacity;
10520
10521 /* Algorithmic Optimization: Cache node stats for O(1) NUMA lookups */
10522 if (env->sd->flags & SD_NUMA) {
10523 int nid = cpu_to_node(cpumask_first(sched_group_span(group)));
10524 struct numa_stats_cache *cache = &node_stats_cache[nid];
10525
10526 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
10527 WRITE_ONCE(cache->load, sgs->group_load);
10528 WRITE_ONCE(cache->util, sgs->group_util);
10529 WRITE_ONCE(cache->runnable, sgs->group_runnable);
10530 WRITE_ONCE(cache->capacity, sgs->group_capacity);
10531 WRITE_ONCE(cache->last_update, jiffies);
10532 }
10533 }
10534

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#6 lore raw
In reply to Qiliang Yuan
kernel test robot noticed the following build errors:

Hi Qiliang,

kernel test robot noticed the following build errors:

[auto build test ERROR on tip/sched/core]
[also build test ERROR on linus/master v6.19-rc7 next-20260123] [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#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Qiliang-Yuan/sched-fair-Cache-NUMA-node-statistics-to-avoid-O-N-scanning/20260126-190546
base:   tip/sched/core
patch link:    https://lore.kernel.org/r/20260126110250.1060512-1-realwujing%40gmail.com
patch subject: [PATCH v3] sched/fair: Cache NUMA node statistics to avoid O(N) scanning
config: x86_64-allnoconfig (https://download.01.org/0day-ci/archive/20260127/[email protected]/config)
compiler: clang version 20.1.8 (https://github.com/llvm/llvm-project 87f0227cb60147a26a1eeb4fb06e3b505e9c7261)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260127/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

>> kernel/sched/fair.c:10524:37: error: use of undeclared identifier 'node_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                                                   ^
>> kernel/sched/fair.c:10526:19: error: incomplete definition of type 'struct numa_stats_cache'
    10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:610:10: note: expanded from macro '__native_word'
     610 |         (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
         |                 ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
>> kernel/sched/fair.c:10526:19: error: incomplete definition of type 'struct numa_stats_cache'
    10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:610:39: note: expanded from macro '__native_word'
     610 |         (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
         |                                              ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
>> kernel/sched/fair.c:10526:19: error: incomplete definition of type 'struct numa_stats_cache'
    10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:611:10: note: expanded from macro '__native_word'
     611 |          sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
         |                 ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
>> kernel/sched/fair.c:10526:19: error: incomplete definition of type 'struct numa_stats_cache'
    10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:611:38: note: expanded from macro '__native_word'
     611 |          sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
         |                                             ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
>> kernel/sched/fair.c:10526:19: error: incomplete definition of type 'struct numa_stats_cache'
    10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:48: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                                       ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
>> kernel/sched/fair.c:10526:19: error: incomplete definition of type 'struct numa_stats_cache'
    10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:61:15: note: expanded from macro 'WRITE_ONCE'
      61 |         __WRITE_ONCE(x, val);                                           \
         |                      ^
   include/asm-generic/rwonce.h:55:20: note: expanded from macro '__WRITE_ONCE'
      55 |         *(volatile typeof(x) *)&(x) = (val);                            \
         |                           ^
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
>> kernel/sched/fair.c:10526:19: error: incomplete definition of type 'struct numa_stats_cache'
    10526 |                 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:61:15: note: expanded from macro 'WRITE_ONCE'
      61 |         __WRITE_ONCE(x, val);                                           \
         |                      ^
   include/asm-generic/rwonce.h:55:27: note: expanded from macro '__WRITE_ONCE'
      55 |         *(volatile typeof(x) *)&(x) = (val);                            \
         |                                  ^
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
   kernel/sched/fair.c:10527:19: error: incomplete definition of type 'struct numa_stats_cache'
    10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:610:10: note: expanded from macro '__native_word'
     610 |         (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
         |                 ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
   kernel/sched/fair.c:10527:19: error: incomplete definition of type 'struct numa_stats_cache'
    10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:610:39: note: expanded from macro '__native_word'
     610 |         (sizeof(t) == sizeof(char) || sizeof(t) == sizeof(short) || \
         |                                              ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
   kernel/sched/fair.c:10527:19: error: incomplete definition of type 'struct numa_stats_cache'
    10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:611:10: note: expanded from macro '__native_word'
     611 |          sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
         |                 ^
   include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
     649 |         _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
         |                             ^~~~~~~~~
   include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
     637 |         __compiletime_assert(condition, msg, prefix, suffix)
         |                              ^~~~~~~~~
   include/linux/compiler_types.h:629:9: note: expanded from macro '__compiletime_assert'
     629 |                 if (!(condition))                                       \
         |                       ^~~~~~~~~
   kernel/sched/fair.c:10524:10: note: forward declaration of 'struct numa_stats_cache'
    10524 |                 struct numa_stats_cache *cache = &node_stats_cache[nid];
          |                        ^
   kernel/sched/fair.c:10527:19: error: incomplete definition of type 'struct numa_stats_cache'
    10527 |                 WRITE_ONCE(cache->load, sgs->group_load);
          |                            ~~~~~^
   include/asm-generic/rwonce.h:60:33: note: expanded from macro 'WRITE_ONCE'
      60 |         compiletime_assert_rwonce_type(x);                              \
         |                                        ^
   include/asm-generic/rwonce.h:36:35: note: expanded from macro 'compiletime_assert_rwonce_type'
      36 |         compiletime_assert(__native_word(t) || sizeof(t) == sizeof(long long),  \
         |                                          ^
   include/linux/compiler_types.h:611:38: note: expanded from macro '__native_word'
     611 |          sizeof(t) == sizeof(int) || sizeof(t) == sizeof(long))
         |                                             ^

include/linux/compiler_types.h:649:22: note: expanded from macro 'compiletime_assert'
649 | _compiletime_assert(condition, msg, __compiletime_assert_, __COUNTER__)
| ^~~~~~~~~
include/linux/compiler_types.h:637:23: note: expanded from macro '_compiletime_assert'
637 | __compiletime_assert(condition, msg, prefix, suffix)

vim +/node_stats_cache +10524 kernel/sched/fair.c

10426
10427 /**
10428 * update_sg_lb_stats - Update sched_group's statistics for load balancing.
10429 * @env: The load balancing environment.
10430 * @sds: Load-balancing data with statistics of the local group.
10431 * @group: sched_group whose statistics are to be updated.
10432 * @sgs: variable to hold the statistics for this group.
10433 * @sg_overloaded: sched_group is overloaded
10434 * @sg_overutilized: sched_group is overutilized
10435 */
10436 static inline void update_sg_lb_stats(struct lb_env *env,

 10437					      struct sd_lb_stats *sds,
 10438					      struct sched_group *group,
 10439					      struct sg_lb_stats *sgs,
 10440					      bool *sg_overloaded,
 10441					      bool *sg_overutilized)

10442 {
10443 int i, nr_running, local_group, sd_flags = env->sd->flags;
10444 bool balancing_at_rd = !env->sd->parent;
10445
10446 memset(sgs, 0, sizeof(*sgs));
10447
10448 local_group = group == sds->local;
10449
10450 for_each_cpu_and(i, sched_group_span(group), env->cpus) {
10451 struct rq *rq = cpu_rq(i);
10452 unsigned long load = cpu_load(rq);
10453
10454 sgs->group_load += load;
10455 sgs->group_util += cpu_util_cfs(i);
10456 sgs->group_runnable += cpu_runnable(rq);
10457 sgs->sum_h_nr_running += rq->cfs.h_nr_runnable;
10458
10459 nr_running = rq->nr_running;
10460 sgs->sum_nr_running += nr_running;
10461
10462 if (cpu_overutilized(i))
10463 *sg_overutilized = 1;
10464
10465 /*
10466 * No need to call idle_cpu() if nr_running is not 0
10467 */
10468 if (!nr_running && idle_cpu(i)) {
10469 sgs->idle_cpus++;
10470 /* Idle cpu can't have misfit task */
10471 continue;
10472 }
10473
10474 /* Overload indicator is only updated at root domain */
10475 if (balancing_at_rd && nr_running > 1)
10476 *sg_overloaded = 1;
10477
10478 #ifdef CONFIG_NUMA_BALANCING
10479 /* Only fbq_classify_group() uses this to classify NUMA groups */
10480 if (sd_flags & SD_NUMA) {
10481 sgs->nr_numa_running += rq->nr_numa_running;
10482 sgs->nr_preferred_running += rq->nr_preferred_running;
10483 }
10484 #endif
10485 if (local_group)
10486 continue;
10487
10488 if (sd_flags & SD_ASYM_CPUCAPACITY) {
10489 /* Check for a misfit task on the cpu */
10490 if (sgs->group_misfit_task_load < rq->misfit_task_load) {
10491 sgs->group_misfit_task_load = rq->misfit_task_load;
10492 *sg_overloaded = 1;
10493 }
10494 } else if (env->idle && sched_reduced_capacity(rq, env->sd)) {
10495 /* Check for a task running on a CPU with reduced capacity */
10496 if (sgs->group_misfit_task_load < load)
10497 sgs->group_misfit_task_load = load;
10498 }
10499 }
10500
10501 sgs->group_capacity = group->sgc->capacity;
10502
10503 sgs->group_weight = group->group_weight;
10504
10505 /* Check if dst CPU is idle and preferred to this group */
10506 if (!local_group && env->idle && sgs->sum_h_nr_running &&
10507 sched_group_asym(env, sgs, group))
10508 sgs->group_asym_packing = 1;
10509
10510 /* Check for loaded SMT group to be balanced to dst CPU */
10511 if (!local_group && smt_balance(env, sgs, group))
10512 sgs->group_smt_balance = 1;
10513
10514 sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs);
10515
10516 /* Computing avg_load makes sense only when group is overloaded */
10517 if (sgs->group_type == group_overloaded)
10518 sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
10519 sgs->group_capacity;
10520
10521 /* Algorithmic Optimization: Cache node stats for O(1) NUMA lookups */
10522 if (env->sd->flags & SD_NUMA) {
10523 int nid = cpu_to_node(cpumask_first(sched_group_span(group)));
10524 struct numa_stats_cache *cache = &node_stats_cache[nid];
10525
10526 WRITE_ONCE(cache->nr_running, sgs->sum_h_nr_running);
10527 WRITE_ONCE(cache->load, sgs->group_load);
10528 WRITE_ONCE(cache->util, sgs->group_util);
10529 WRITE_ONCE(cache->runnable, sgs->group_runnable);
10530 WRITE_ONCE(cache->capacity, sgs->group_capacity);
10531 WRITE_ONCE(cache->last_update, jiffies);
10532 }
10533 }
10534

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#7 lore raw
In reply to Qiliang Yuan

Hello Qiliang,

Quoted 8 lines · Qiliang Yuan

Optimize update_numa_stats() by leveraging pre-calculated node statistics cached during the load balancing process. This reduces the complexity of NUMA balancing overhead from O(CPUs_per_node) to O(1) when statistics for the source node are fresh.

---

Missing a changelog and the performance numbers that justify this change.

Quoted 11 lines
 kernel/sched/fair.c | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
kernel/sched/fair.c +0 -0
index e71302282671..070b61f65b6d 100644
@@ -2094,6 +2094,17 @@ static inline int numa_idle_core(int idle_core, int cpu)
  * borrows code and logic from update_sg_lb_stats but sharing a
  * common implementation is impractical.
  */

kernel/sched/fair.c static inline int numa_idle_core(int idle_core, int cpu) · line 2106

Quoted 10 lines
kernel/sched/fair.c +10 -0
+struct numa_stats_cache {
+	unsigned long load;
+	unsigned long runnable;
+	unsigned long util;
+	unsigned long nr_running;
+	unsigned long capacity;
+	unsigned long last_update;
+};
+
+static struct numa_stats_cache node_stats_cache[MAX_NUMNODES];

MAX_NUMNODES is a very large value. Why do you need to have this all up front and not dynamically allocate it during sched domain build.

Speaking of sched domains, partitioning the system can make it so that the NUMA domain is split across multiple partition which makes these numbers partition specific. Tasks running in one partition cannot use the cached values from another partition.

If there is really a noticeable benefit, I would suggest using the previous method to cache it somewhere in the sched domain hierarchy - but only if there is a noticeable benefit.

Quoted 12 lines
kernel/sched/fair.c +5 -0
+
 static void update_numa_stats(struct task_numa_env *env,
 			      struct numa_stats *ns, int nid,
 			      bool find_idle)
@@ -2104,6 +2115,24 @@ static void update_numa_stats(struct task_numa_env *env,
 	ns->idle_cpu = -1;
 
 	rcu_read_lock();
+	/*
+	 * Algorithmic Optimization: Avoid O(N) scan by using cached stats.
+	 * Only applicable for the source node where we don't need to find
+	 * an idle CPU.

kernel/sched/fair.c static void update_numa_stats(struct task_numa_env *env, · line 2131

Quoted 10 lines
kernel/sched/fair.c +10 -0
+	 */
+	if (!find_idle && nid == env->src_nid) {
+		struct numa_stats_cache *cache = &node_stats_cache[nid];
+
+		if (time_before(jiffies, cache->last_update + msecs_to_jiffies(10))) {
+			ns->load = READ_ONCE(cache->load);
+			ns->runnable = READ_ONCE(cache->runnable);
+			ns->util = READ_ONCE(cache->util);
+			ns->nr_running = READ_ONCE(cache->nr_running);
+			ns->compute_capacity = READ_ONCE(cache->capacity);

So READ_ONCE()/WRITE_ONCE() doesn't solve the issue I was highlighting in the last version. Say the following happens:

    CPU0                                            CPU1
    ====                                            ====
  update_numa_stats()
    /* Working on current numa_stats_cache */
    ns->load = READ_ONCE(cache->load);
    ns->runnable = READ_ONCE(cache->runnable);
    ... interrupted                               update_sg_lb_stats()
    ...                                           ... updates the entire numa_stats_cache
    ...
    ns->util = READ_ONCE(cache->util); /* Sees new data. */

Can this cause an issue? If not, please highlight in the commit log why it is not an issue. There can be cases where we see util > capacity, util > runnable, etc. which might lead to incorrect calculations later on.

Quoted 17 lines
kernel/sched/fair.c +6 -0
+			goto skip_scan;
+		}
+	}
+
 	for_each_cpu(cpu, cpumask_of_node(nid)) {
 		struct rq *rq = cpu_rq(cpu);
 
@@ -2124,6 +2153,8 @@ static void update_numa_stats(struct task_numa_env *env,
 			idle_core = numa_idle_core(idle_core, cpu);
 		}
 	}
+
+skip_scan:
 	rcu_read_unlock();
 
 	ns->weight = cpumask_weight(cpumask_of_node(nid));

kernel/sched/fair.c static inline void update_sg_lb_stats(struct lb_env *env, · line 10524

Quoted 6 lines
kernel/sched/fair.c +3 -0
@@ -10488,6 +10519,19 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	if (sgs->group_type == group_overloaded)
 		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
 				sgs->group_capacity;
+
+	/* Algorithmic Optimization: Cache node stats for O(1) NUMA lookups */
+	if (env->sd->flags & SD_NUMA) {

Also you'll need to think about partitions.

Signature · 2 lines
Thanks and Regards,
Prateek