sched/fair: Cache NUMA node statistics to avoid O(N) scanning
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
@@ -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
@@ -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
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
@@ -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
@@ -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
PATCH v2 1/1 sched/fair: Cache NUMA node statistics to avoid O(N) scanning
In reply to Qiliang YuanOptimize 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
@@ -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
@@ -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
K Prateek Nayak
reviewerHello 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 fromO(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.
Signed-off-by Qiliang Yuan <[email protected]>Signed-off-by Qiliang Yuan <[email protected]>--- kernel/sched/fair.c | 35 +++++++++++++++++++++++++++++++++++ kernel/sched/sched.h | 7 +++++++ 2 files changed, 42 insertions(+)kernel/sched/fair.c +1
-0@@ -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
-0ns->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
-0sgs->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
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
-0unsigned long cpumask[];/* Balance mask */ };
Signature · 2 lines
Thanks and Regards, Prateek
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
@@ -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
kernel test robot
build botkernel 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
kernel test robot
build botkernel 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
K Prateek Nayak
reviewerHello 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 fromO(CPUs_per_node)to O(1) when statistics for the source node are fresh.Signed-off-by Qiliang Yuan <[email protected]>Signed-off-by Qiliang Yuan <[email protected]>---
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@@ -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