[PATCHSET v10 sched_ext/for-6.15] sched_ext: split global idle cpumask into per-NUMA cpumasks

[PATCHSET v10 sched_ext/for-6.15] sched_ext: split global idle cpumask into per-NUMA cpumasks

[Andrea Righi]

= Overview =

As discussed during the sched_ext office hours, using a global cpumask to
keep track of the idle CPUs can be inefficient and it may not scale really
well on large NUMA systems.

Therefore, split the idle cpumask into multiple per-NUMA node cpumasks to
improve scalability and performance on such large systems.

Scalability issues seem to be more noticeable on Intel Sapphire Rapids
dual-socket architectures.

= Test =

Hardware:
 - System: DGX B200
    - CPUs: 224 SMT threads (112 physical cores)
    - Processor: INTEL(R) XEON(R) PLATINUM 8570
    - 2 NUMA nodes

Scheduler:
 - scx_simple [1] (so that we can focus at the built-in idle selection
   policy and not at the scheduling policy itself)

Test:
 - Run a parallel kernel build `make -j $(nproc)` and measure the average
   elapsed time over 10 runs:

          avg time | stdev
          ---------+------
 before:   52.431s | 2.895
  after:   50.342s | 2.895

= Conclusion =

Splitting the global cpumask into multiple per-NUMA cpumasks helped to
achieve a speedup of approximately +4% with this particular architecture
and test case.

The same test on a DGX-1 (40 physical cores, Intel Xeon E5-2698 v4 @
2.20GHz, 2 NUMA nodes) shows a speedup of around 1.5-3%.

On smaller systems, I haven't noticed any measurable regressions or
improvements with the same test (parallel kernel build) and scheduler
(scx_simple).

Moreover, with a modified scx_bpfland that uses the new NUMA-aware APIs I
observed an additional +2-2.5% performance improvement in the same test.

NOTE: splitting the global cpumask into multiple cpumasks may increase the
overhead of scx_bpf_pick_idle_cpu() or ops.select_cpu() (for schedulers
relying on the built-in CPU idle selection policy) in presence of multiple
NUMA nodes, particularly under high system load, since we may have to
access multiple cpumasks to find an idle CPU.

However, this increased overhead seems to be highly compensated by a lower
overhead when updating the idle state and by the fact that CPUs are more
likely operating within their local idle cpumask, reducing the stress on
the cache coherency protocol.

= References =

[1] https://github.com/sched-ext/scx/blob/main/scheds/c/scx_simple.bpf.c

ChangeLog v9 -> v10:
 - introduce for_each_numa_node() and numa_nearest_nodemask() helpers

ChangeLog v8 -> v9:
 - drop some preliminary refactoring patches that are now applied to
   sched_ext/for-6.15
 - rename SCX_PICK_IDLE_NODE -> SCX_PICK_IDLE_IN_NODE
 - use NUMA_NO_NODE to reference to the global idle cpumask and drop
   NUMA_FLAT_NODE (which was quite confusing)
 - NUMA_NO_NODE is not implicitly translated to the current node
 - rename struct idle_cpumask -> idle_cpus
 - drop "get_" prefix from the idle cpumask helpers
 - rename for_each_numa_hop_node() -> for_each_numa_node()
 - for_each_numa_node() returns MAX_NUMNODES at the end of the loop
   (for coherency with other node iterators)
 - do not get rid of the scx_selcpu_topo_numa logic (since it can still be
   used when per-node cpumasks are not enabled)

ChangeLog v7 -> v8:
 - patch set refactoring: move ext_idle.c as first patch and introduce more
   preparation patches
 - introduce SCX_PICK_IDLE_NODE to restrict idle CPU selection to a single
   specified node
 - trigger scx_ops_error() when the *_node() kfunc's are used without
   enbling SCX_OPS_NODE_BUILTIN_IDLE
 - check for node_possible() in validate_node()
 - do node validation in the kfunc's (instead of the internal kernel
   functions) and trigger scx_ops_error in case of failure
 - rename idle_masks -> scx_idle_masks
 - drop unused CL_ALIGNED_IF_ONSTACK
 - drop unnecessary rcu_read_lock/unlock() when iterating NUMA nodes

ChangeLog v6 -> v7:
 - addressed some issues based on Yury's review (thanks!)
 - introduced a new iterator to navigate the NUMA nodes in order of
   increasing distance

ChangeLog v5 -> v6:
 - refactor patch set to introduce SCX_OPS_NODE_BUILTIN_IDLE before
   the per-node cpumasks
 - move idle CPU selection policy to a separate file (ext_idle.c)
   (no functional change, just some code shuffling)

ChangeLog v4 -> v5:
 - introduce new scx_bpf_cpu_to_node() kfunc
 - provide __COMPAT_*() helpers for the new kfunc's

ChangeLog v3 -> v4:
 - introduce SCX_OPS_NODE_BUILTIN_IDLE to select multiple per-node
   cpumasks or single flat cpumask
 - introduce new kfuncs to access per-node idle cpumasks information
 - use for_each_numa_hop_mask() to traverse NUMA nodes in increasing
   distance
 - dropped nodemask helpers (not needed anymore)
 - rebase to sched_ext/for-6.14

ChangeLog v2 -> v3:
  - introduce for_each_online_node_wrap()
  - re-introduce cpumask_intersects() in test_and_clear_cpu_idle() (to
    reduce memory writes / cache coherence pressure)
  - get rid of the redundant scx_selcpu_topo_numa logic
  [test results are pretty much identical, so I haven't updated them from v2]

ChangeLog v1 -> v2:
  - renamed for_each_node_mask|state_from() -> for_each_node_mask|state_wrap()
  - misc cpumask optimizations (thanks to Yury)

Andrea Righi (6):
      mm/numa: Introduce numa_nearest_nodemask()
      sched/topology: Introduce for_each_numa_node() iterator
      sched_ext: idle: Introduce SCX_OPS_BUILTIN_IDLE_PER_NODE
      sched_ext: idle: introduce SCX_PICK_IDLE_IN_NODE
      sched_ext: idle: Per-node idle cpumasks
      sched_ext: idle: Introduce node-aware idle cpu kfunc helpers

 include/linux/nodemask_types.h           |   6 +-
 include/linux/numa.h                     |   8 +
 include/linux/topology.h                 |  28 +++
 kernel/sched/ext.c                       |  22 +-
 kernel/sched/ext_idle.c                  | 396 ++++++++++++++++++++++++++-----
 kernel/sched/ext_idle.h                  |  17 +-
 mm/mempolicy.c                           |  38 +++
 tools/sched_ext/include/scx/common.bpf.h |   4 +
 tools/sched_ext/include/scx/compat.bpf.h |  19 ++
 9 files changed, 475 insertions(+), 63 deletions(-)

[PATCH 1/6] mm/numa: Introduce numa_nearest_nodemask()

[Andrea Righi]

Introduce the new helper numa_nearest_nodemask() to find the closest
node, in a specified nodemask and state, from a given starting node.

Returns MAX_NUMNODES if no node is found.

Cc: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 include/linux/nodemask_types.h |  6 +++++-
 include/linux/numa.h           |  8 +++++++
 mm/mempolicy.c                 | 38 ++++++++++++++++++++++++++++++++++
 3 files changed, 51 insertions(+), 1 deletion(-)

diff --git a/include/linux/nodemask_types.h b/include/linux/nodemask_types.h
index 6b28d97ea6ed0..8d0b7a66c3a49 100644
--- a/include/linux/nodemask_types.h
+++ b/include/linux/nodemask_types.h
@@ -5,6 +5,10 @@
 #include <linux/bitops.h>
 #include <linux/numa.h>
 
-typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;
+struct nodemask {
+	DECLARE_BITMAP(bits, MAX_NUMNODES);
+};
+
+typedef struct nodemask nodemask_t;
 
 #endif /* __LINUX_NODEMASK_TYPES_H */
diff --git a/include/linux/numa.h b/include/linux/numa.h
index 3567e40329ebc..a549b87d1fca5 100644
--- a/include/linux/numa.h
+++ b/include/linux/numa.h
@@ -27,6 +27,8 @@ static inline bool numa_valid_node(int nid)
 #define __initdata_or_meminfo __initdata
 #endif
 
+struct nodemask;
+
 #ifdef CONFIG_NUMA
 #include <asm/sparsemem.h>
 
@@ -38,6 +40,7 @@ void __init alloc_offline_node_data(int nid);
 
 /* Generic implementation available */
 int numa_nearest_node(int node, unsigned int state);
+int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask);
 
 #ifndef memory_add_physaddr_to_nid
 int memory_add_physaddr_to_nid(u64 start);
@@ -55,6 +58,11 @@ static inline int numa_nearest_node(int node, unsigned int state)
 	return NUMA_NO_NODE;
 }
 
+static inline int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask)
+{
+	return NUMA_NO_NODE;
+}
+
 static inline int memory_add_physaddr_to_nid(u64 start)
 {
 	return 0;
diff --git a/mm/mempolicy.c b/mm/mempolicy.c
index 162407fbf2bc7..1cfee509c7229 100644
--- a/mm/mempolicy.c
+++ b/mm/mempolicy.c
@@ -196,6 +196,44 @@ int numa_nearest_node(int node, unsigned int state)
 }
 EXPORT_SYMBOL_GPL(numa_nearest_node);
 
+/**
+ * numa_nearest_nodemask - Find the node in @mask at the nearest distance
+ *			   from @node.
+ *
+ * @node: the node to start the search from.
+ * @state: the node state to filter nodes by.
+ * @mask: a pointer to a nodemask representing the allowed nodes.
+ *
+ * This function iterates over all nodes in the given state and calculates
+ * the distance to the starting node.
+ *
+ * Returns the node ID in @mask that is the closest in terms of distance
+ * from @node, or MAX_NUMNODES if no node is found.
+ */
+int numa_nearest_nodemask(int node, unsigned int state, nodemask_t *mask)
+{
+	int dist, n, min_dist = INT_MAX, min_node = MAX_NUMNODES;
+
+	if (node == NUMA_NO_NODE)
+		return MAX_NUMNODES;
+
+	if (node_state(node, state) && node_isset(node, *mask))
+		return node;
+
+	for_each_node_state(n, state) {
+		if (!node_isset(n, *mask))
+			continue;
+		dist = node_distance(node, n);
+		if (dist < min_dist) {
+			min_dist = dist;
+			min_node = n;
+		}
+	}
+
+	return min_node;
+}
+EXPORT_SYMBOL_GPL(numa_nearest_nodemask);
+
 struct mempolicy *get_task_policy(struct task_struct *p)
 {
 	struct mempolicy *pol = p->mempolicy;
-- 
2.48.1

Re: [PATCH 1/6] mm/numa: Introduce numa_nearest_nodemask()

[Yury Norov]

On Fri, Feb 07, 2025 at 09:40:48PM +0100, Andrea Righi wrote:
> Introduce the new helper numa_nearest_nodemask() to find the closest
> node, in a specified nodemask and state, from a given starting node.
> 
> Returns MAX_NUMNODES if no node is found.
> 
> Cc: Yury Norov <yury.norov@gmail.com>
> Signed-off-by: Andrea Righi <arighi@nvidia.com>
> ---
>  include/linux/nodemask_types.h |  6 +++++-
>  include/linux/numa.h           |  8 +++++++
>  mm/mempolicy.c                 | 38 ++++++++++++++++++++++++++++++++++
>  3 files changed, 51 insertions(+), 1 deletion(-)
> 
> diff --git a/include/linux/nodemask_types.h b/include/linux/nodemask_types.h
> index 6b28d97ea6ed0..8d0b7a66c3a49 100644
> --- a/include/linux/nodemask_types.h
> +++ b/include/linux/nodemask_types.h
> @@ -5,6 +5,10 @@
>  #include <linux/bitops.h>
>  #include <linux/numa.h>
>  
> -typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;
> +struct nodemask {
> +	DECLARE_BITMAP(bits, MAX_NUMNODES);
> +};
> +
> +typedef struct nodemask nodemask_t;
>  
>  #endif /* __LINUX_NODEMASK_TYPES_H */
> diff --git a/include/linux/numa.h b/include/linux/numa.h
> index 3567e40329ebc..a549b87d1fca5 100644
> --- a/include/linux/numa.h
> +++ b/include/linux/numa.h
> @@ -27,6 +27,8 @@ static inline bool numa_valid_node(int nid)
>  #define __initdata_or_meminfo __initdata
>  #endif
>  
> +struct nodemask;

Numa should include this via linux/nodemask_types.h, or maybe
nodemask.h.

> +
>  #ifdef CONFIG_NUMA
>  #include <asm/sparsemem.h>
>  
> @@ -38,6 +40,7 @@ void __init alloc_offline_node_data(int nid);
>  
>  /* Generic implementation available */
>  int numa_nearest_node(int node, unsigned int state);
> +int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask);
>  
>  #ifndef memory_add_physaddr_to_nid
>  int memory_add_physaddr_to_nid(u64 start);
> @@ -55,6 +58,11 @@ static inline int numa_nearest_node(int node, unsigned int state)
>  	return NUMA_NO_NODE;
>  }
>  
> +static inline int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask)
> +{
> +	return NUMA_NO_NODE;
> +}
> +
>  static inline int memory_add_physaddr_to_nid(u64 start)
>  {
>  	return 0;
> diff --git a/mm/mempolicy.c b/mm/mempolicy.c
> index 162407fbf2bc7..1cfee509c7229 100644
> --- a/mm/mempolicy.c
> +++ b/mm/mempolicy.c
> @@ -196,6 +196,44 @@ int numa_nearest_node(int node, unsigned int state)
>  }
>  EXPORT_SYMBOL_GPL(numa_nearest_node);
>  
> +/**
> + * numa_nearest_nodemask - Find the node in @mask at the nearest distance
> + *			   from @node.
> + *

So, I have a feeling about this whole naming scheme. At first, this
function (and the existing numa_nearest_node()) searches for something,
but doesn't begin with find_, search_ or similar. Second, the naming
of existing numa_nearest_node() doesn't reflect that it searches
against the state. Should we always include some state for search? If
so, we can skip mentioning the state, otherwise it should be in the
name, I guess...

The problem is that I have no idea for better naming, and I have no
understanding about the future of this functions family. If it's just
numa_nearest_node() and numa_nearest_nodemask(), I'm OK to go this
way. If we'll add more flavors similarly to find_bit() family, we
could probably discuss a naming scheme.

Also, mm/mempolicy.c is a historical place for them, but maybe we need
to move it somewhere else?

Any thoughts appreciated.

> + * @node: the node to start the search from.
> + * @state: the node state to filter nodes by.
> + * @mask: a pointer to a nodemask representing the allowed nodes.
> + *
> + * This function iterates over all nodes in the given state and calculates
> + * the distance to the starting node.
> + *
> + * Returns the node ID in @mask that is the closest in terms of distance
> + * from @node, or MAX_NUMNODES if no node is found.
> + */
> +int numa_nearest_nodemask(int node, unsigned int state, nodemask_t *mask)

Your only user calls the function with N_POSSIBLE:

  s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
  {
        nodemask_t unvisited = NODE_MASK_ALL;

        if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
               return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);


        for_each_numa_node(node, unvisited, N_POSSIBLE)
                do_something();
  }

Which means you don't need the state at all. Even more, you don't
need to initialize the unvisited mask before checking the static
branch:

  s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
  {
        nodemask_t unvisited;

        if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
               return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);

        nodes_clear(unvisited);

        for_each_numa_node(node, unvisited)
                do_something();
  }


If you need some state other than N_POSSIBLE, you can do it similarly:
        
        nodemask_complement(unvisited, N_CPU);

        /* Only N_CPU nodes iterated */
        for_each_numa_node(node, unvisited)
                do_something();


> +{
> +	int dist, n, min_dist = INT_MAX, min_node = MAX_NUMNODES;
> +
> +	if (node == NUMA_NO_NODE)
> +		return MAX_NUMNODES;
> +
> +	if (node_state(node, state) && node_isset(node, *mask))
> +		return node;

This is correct, but why do we need this special case? If distance to
local node is always 0, and distance to remote node is always greater
than 0, the normal search will return local node, right? Is that a
performance trick? If so, can you put a comment please? Otherwise,
maybe just drop it? 

> +
> +	for_each_node_state(n, state) {
> +		if (!node_isset(n, *mask))
> +			continue;

for_each_node_state_and_mask(n, state, mask)

Or if you take the above consideration, just
        for_each_node_mask(n, mask)       

> +		dist = node_distance(node, n);
> +		if (dist < min_dist) {
> +			min_dist = dist;
> +			min_node = n;
> +		}
> +	}
> +
> +	return min_node;
> +}
> +EXPORT_SYMBOL_GPL(numa_nearest_nodemask);
> +
>  struct mempolicy *get_task_policy(struct task_struct *p)
>  {
>  	struct mempolicy *pol = p->mempolicy;
> -- 
> 2.48.1

Re: [PATCH 1/6] mm/numa: Introduce numa_nearest_nodemask()

[Andrea Righi]

Hi Yury,

On Sun, Feb 09, 2025 at 12:40:15PM -0500, Yury Norov wrote:
> On Fri, Feb 07, 2025 at 09:40:48PM +0100, Andrea Righi wrote:
> > Introduce the new helper numa_nearest_nodemask() to find the closest
> > node, in a specified nodemask and state, from a given starting node.
> > 
> > Returns MAX_NUMNODES if no node is found.
> > 
> > Cc: Yury Norov <yury.norov@gmail.com>
> > Signed-off-by: Andrea Righi <arighi@nvidia.com>
> > ---
> >  include/linux/nodemask_types.h |  6 +++++-
> >  include/linux/numa.h           |  8 +++++++
> >  mm/mempolicy.c                 | 38 ++++++++++++++++++++++++++++++++++
> >  3 files changed, 51 insertions(+), 1 deletion(-)
> > 
> > diff --git a/include/linux/nodemask_types.h b/include/linux/nodemask_types.h
> > index 6b28d97ea6ed0..8d0b7a66c3a49 100644
> > --- a/include/linux/nodemask_types.h
> > +++ b/include/linux/nodemask_types.h
> > @@ -5,6 +5,10 @@
> >  #include <linux/bitops.h>
> >  #include <linux/numa.h>
> >  
> > -typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;
> > +struct nodemask {
> > +	DECLARE_BITMAP(bits, MAX_NUMNODES);
> > +};
> > +
> > +typedef struct nodemask nodemask_t;
> >  
> >  #endif /* __LINUX_NODEMASK_TYPES_H */
> > diff --git a/include/linux/numa.h b/include/linux/numa.h
> > index 3567e40329ebc..a549b87d1fca5 100644
> > --- a/include/linux/numa.h
> > +++ b/include/linux/numa.h
> > @@ -27,6 +27,8 @@ static inline bool numa_valid_node(int nid)
> >  #define __initdata_or_meminfo __initdata
> >  #endif
> >  
> > +struct nodemask;
> 
> Numa should include this via linux/nodemask_types.h, or maybe
> nodemask.h.

Hm... nodemask_types.h needs to include numa.h to resolve MAX_NUMNODES,
Maybe we can move numa_nearest_nodemask() to linux/nodemask.h?

> 
> > +
> >  #ifdef CONFIG_NUMA
> >  #include <asm/sparsemem.h>
> >  
> > @@ -38,6 +40,7 @@ void __init alloc_offline_node_data(int nid);
> >  
> >  /* Generic implementation available */
> >  int numa_nearest_node(int node, unsigned int state);
> > +int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask);
> >  
> >  #ifndef memory_add_physaddr_to_nid
> >  int memory_add_physaddr_to_nid(u64 start);
> > @@ -55,6 +58,11 @@ static inline int numa_nearest_node(int node, unsigned int state)
> >  	return NUMA_NO_NODE;
> >  }
> >  
> > +static inline int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask)
> > +{
> > +	return NUMA_NO_NODE;
> > +}
> > +
> >  static inline int memory_add_physaddr_to_nid(u64 start)
> >  {
> >  	return 0;
> > diff --git a/mm/mempolicy.c b/mm/mempolicy.c
> > index 162407fbf2bc7..1cfee509c7229 100644
> > --- a/mm/mempolicy.c
> > +++ b/mm/mempolicy.c
> > @@ -196,6 +196,44 @@ int numa_nearest_node(int node, unsigned int state)
> >  }
> >  EXPORT_SYMBOL_GPL(numa_nearest_node);
> >  
> > +/**
> > + * numa_nearest_nodemask - Find the node in @mask at the nearest distance
> > + *			   from @node.
> > + *
> 
> So, I have a feeling about this whole naming scheme. At first, this
> function (and the existing numa_nearest_node()) searches for something,
> but doesn't begin with find_, search_ or similar. Second, the naming
> of existing numa_nearest_node() doesn't reflect that it searches
> against the state. Should we always include some state for search? If
> so, we can skip mentioning the state, otherwise it should be in the
> name, I guess...
> 
> The problem is that I have no idea for better naming, and I have no
> understanding about the future of this functions family. If it's just
> numa_nearest_node() and numa_nearest_nodemask(), I'm OK to go this
> way. If we'll add more flavors similarly to find_bit() family, we
> could probably discuss a naming scheme.
> 
> Also, mm/mempolicy.c is a historical place for them, but maybe we need
> to move it somewhere else?
> 
> Any thoughts appreciated.

Personally I think adding "find_" to the name would be a bit redundant, as
it seems quite obvious that it's finding the nearest node. It sounds a bit
like the get_something() discussion and we can just use something().

About adding "_state" to the name, it'd make sense since we have
for_each_node_state/for_each_node(), but we would need to change
numa_nearest_node() -> numa_nearest_node_state((), that is beyond the scope
of this patch set.

If I had to design this completely from scratch I'd probably propose
something like this:
 - nearest_node_state(node, state)
 - nearest_node(node) -> nearest_node_state(node, N_POSSIBLE)
 - nearest_node_nodemask(node, nodemask) -> here the state can be managed
   with the nodemask (as you suggested below)

But again, this is probably a more generic discussion that can be addressed
in a separate thread.

> 
> > + * @node: the node to start the search from.
> > + * @state: the node state to filter nodes by.
> > + * @mask: a pointer to a nodemask representing the allowed nodes.
> > + *
> > + * This function iterates over all nodes in the given state and calculates
> > + * the distance to the starting node.
> > + *
> > + * Returns the node ID in @mask that is the closest in terms of distance
> > + * from @node, or MAX_NUMNODES if no node is found.
> > + */
> > +int numa_nearest_nodemask(int node, unsigned int state, nodemask_t *mask)
> 
> Your only user calls the function with N_POSSIBLE:
> 
>   s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
>   {
>         nodemask_t unvisited = NODE_MASK_ALL;
> 
>         if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
>                return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);
> 
> 
>         for_each_numa_node(node, unvisited, N_POSSIBLE)
>                 do_something();
>   }
> 
> Which means you don't need the state at all. Even more, you don't
> need to initialize the unvisited mask before checking the static
> branch:
> 
>   s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
>   {
>         nodemask_t unvisited;
> 
>         if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
>                return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);
> 
>         nodes_clear(unvisited);
> 
>         for_each_numa_node(node, unvisited)
>                 do_something();
>   }
> 
> 
> If you need some state other than N_POSSIBLE, you can do it similarly:
>         
>         nodemask_complement(unvisited, N_CPU);
> 
>         /* Only N_CPU nodes iterated */
>         for_each_numa_node(node, unvisited)
>                 do_something();

Good point. I think we can implicitly assume N_POSSIBLE and if we need to
filter only a certain state in the future, we can enforce that via the
nodemask.

> 
> 
> > +{
> > +	int dist, n, min_dist = INT_MAX, min_node = MAX_NUMNODES;
> > +
> > +	if (node == NUMA_NO_NODE)
> > +		return MAX_NUMNODES;
> > +
> > +	if (node_state(node, state) && node_isset(node, *mask))
> > +		return node;
> 
> This is correct, but why do we need this special case? If distance to
> local node is always 0, and distance to remote node is always greater
> than 0, the normal search will return local node, right? Is that a
> performance trick? If so, can you put a comment please? Otherwise,
> maybe just drop it? 

Yeah we can probably just drop it, I don't it gives much benefit in terms
of performance. And the special optimiation case of searching only in one
node can be managed already by the caller via SCX_PICK_IDLE_IN_NODE.

> 
> > +
> > +	for_each_node_state(n, state) {
> > +		if (!node_isset(n, *mask))
> > +			continue;
> 
> for_each_node_state_and_mask(n, state, mask)
> 
> Or if you take the above consideration, just
>         for_each_node_mask(n, mask)       

Ok, that's much better.

Thanks,
-Andrea

Re: [PATCH 1/6] mm/numa: Introduce numa_nearest_nodemask()

[Yury Norov]

On Mon, Feb 10, 2025 at 09:28:36AM +0100, Andrea Righi wrote:
> Hi Yury,
> 
> On Sun, Feb 09, 2025 at 12:40:15PM -0500, Yury Norov wrote:
> > On Fri, Feb 07, 2025 at 09:40:48PM +0100, Andrea Righi wrote:
> > > Introduce the new helper numa_nearest_nodemask() to find the closest
> > > node, in a specified nodemask and state, from a given starting node.
> > > 
> > > Returns MAX_NUMNODES if no node is found.
> > > 
> > > Cc: Yury Norov <yury.norov@gmail.com>
> > > Signed-off-by: Andrea Righi <arighi@nvidia.com>
> > > ---
> > >  include/linux/nodemask_types.h |  6 +++++-
> > >  include/linux/numa.h           |  8 +++++++
> > >  mm/mempolicy.c                 | 38 ++++++++++++++++++++++++++++++++++
> > >  3 files changed, 51 insertions(+), 1 deletion(-)
> > > 
> > > diff --git a/include/linux/nodemask_types.h b/include/linux/nodemask_types.h
> > > index 6b28d97ea6ed0..8d0b7a66c3a49 100644
> > > --- a/include/linux/nodemask_types.h
> > > +++ b/include/linux/nodemask_types.h
> > > @@ -5,6 +5,10 @@
> > >  #include <linux/bitops.h>
> > >  #include <linux/numa.h>
> > >  
> > > -typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;
> > > +struct nodemask {
> > > +	DECLARE_BITMAP(bits, MAX_NUMNODES);
> > > +};
> > > +
> > > +typedef struct nodemask nodemask_t;
> > >  
> > >  #endif /* __LINUX_NODEMASK_TYPES_H */
> > > diff --git a/include/linux/numa.h b/include/linux/numa.h
> > > index 3567e40329ebc..a549b87d1fca5 100644
> > > --- a/include/linux/numa.h
> > > +++ b/include/linux/numa.h
> > > @@ -27,6 +27,8 @@ static inline bool numa_valid_node(int nid)
> > >  #define __initdata_or_meminfo __initdata
> > >  #endif
> > >  
> > > +struct nodemask;
> > 
> > Numa should include this via linux/nodemask_types.h, or maybe
> > nodemask.h.
> 
> Hm... nodemask_types.h needs to include numa.h to resolve MAX_NUMNODES,
> Maybe we can move numa_nearest_nodemask() to linux/nodemask.h?

Maybe yes, but it's generally wrong. nodemask.h is a library, and
numa.h (generally, NUMA code) is one user. The right way to go is when
client code includes all necessary libs, not vise-versa.

Regarding MAX_NUMNODES, it's a natural property of nodemasks, and
should be declared in nodemask.h. The attached patch reverts the
inclusion paths dependency. I build-tested it against today's master
and x86_64 defconfig. Can you consider taking it and prepending your
series?
 
> > >  #ifdef CONFIG_NUMA
> > >  #include <asm/sparsemem.h>
> > >  
> > > @@ -38,6 +40,7 @@ void __init alloc_offline_node_data(int nid);
> > >  
> > >  /* Generic implementation available */
> > >  int numa_nearest_node(int node, unsigned int state);
> > > +int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask);
> > >  
> > >  #ifndef memory_add_physaddr_to_nid
> > >  int memory_add_physaddr_to_nid(u64 start);
> > > @@ -55,6 +58,11 @@ static inline int numa_nearest_node(int node, unsigned int state)
> > >  	return NUMA_NO_NODE;
> > >  }
> > >  
> > > +static inline int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask)
> > > +{
> > > +	return NUMA_NO_NODE;
> > > +}
> > > +
> > >  static inline int memory_add_physaddr_to_nid(u64 start)
> > >  {
> > >  	return 0;
> > > diff --git a/mm/mempolicy.c b/mm/mempolicy.c
> > > index 162407fbf2bc7..1cfee509c7229 100644
> > > --- a/mm/mempolicy.c
> > > +++ b/mm/mempolicy.c
> > > @@ -196,6 +196,44 @@ int numa_nearest_node(int node, unsigned int state)
> > >  }
> > >  EXPORT_SYMBOL_GPL(numa_nearest_node);
> > >  
> > > +/**
> > > + * numa_nearest_nodemask - Find the node in @mask at the nearest distance
> > > + *			   from @node.
> > > + *
> > 
> > So, I have a feeling about this whole naming scheme. At first, this
> > function (and the existing numa_nearest_node()) searches for something,
> > but doesn't begin with find_, search_ or similar. Second, the naming
> > of existing numa_nearest_node() doesn't reflect that it searches
> > against the state. Should we always include some state for search? If
> > so, we can skip mentioning the state, otherwise it should be in the
> > name, I guess...
> > 
> > The problem is that I have no idea for better naming, and I have no
> > understanding about the future of this functions family. If it's just
> > numa_nearest_node() and numa_nearest_nodemask(), I'm OK to go this
> > way. If we'll add more flavors similarly to find_bit() family, we
> > could probably discuss a naming scheme.
> > 
> > Also, mm/mempolicy.c is a historical place for them, but maybe we need
> > to move it somewhere else?
> > 
> > Any thoughts appreciated.
> 
> Personally I think adding "find_" to the name would be a bit redundant, as
> it seems quite obvious that it's finding the nearest node. It sounds a bit
> like the get_something() discussion and we can just use something().
> 
> About adding "_state" to the name, it'd make sense since we have
> for_each_node_state/for_each_node(), but we would need to change
> numa_nearest_node() -> numa_nearest_node_state((), that is beyond the scope
> of this patch set.
> 
> If I had to design this completely from scratch I'd probably propose
> something like this:
>  - nearest_node_state(node, state)
>  - nearest_node(node) -> nearest_node_state(node, N_POSSIBLE)
>  - nearest_node_nodemask(node, nodemask) -> here the state can be managed
>    with the nodemask (as you suggested below)
> 
> But again, this is probably a more generic discussion that can be addressed
> in a separate thread.

Yes, it's not related to your series. Please just introduce
nearest_node_nodemask(node, nodemask) as your minimal required change.
I will do a necessary cleanup later, if needed.

Thanks,
Yury

From 3ad589b371d671485d61d7debcb7526283a2f703 Mon Sep 17 00:00:00 2001
From: Yury Norov <yury.norov@gmail.com>
Date: Mon, 10 Feb 2025 10:56:04 -0500
Subject: [PATCH] nodemask: numa: reorganize inclusion path

Nodemasks now pull linux/numa.h for MAX_NUMNODES and NUMA_NO_NODE
macros. This series makes numa.h depending on nodemasks, so we hit
a circular dependency.

Nodemasks library is highly employed by NUMA code, and it would be
logical to resolve the circular dependency by making NUMA headers
dependent nodemask.h.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 include/linux/nodemask.h       |  1 -
 include/linux/nodemask_types.h | 11 ++++++++++-
 include/linux/numa.h           | 10 +---------
 3 files changed, 11 insertions(+), 11 deletions(-)

diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
index 9fd7a0ce9c1a..27644a6edc6e 100644
--- a/include/linux/nodemask.h
+++ b/include/linux/nodemask.h
@@ -94,7 +94,6 @@
 #include <linux/bitmap.h>
 #include <linux/minmax.h>
 #include <linux/nodemask_types.h>
-#include <linux/numa.h>
 #include <linux/random.h>
 
 extern nodemask_t _unused_nodemask_arg_;
diff --git a/include/linux/nodemask_types.h b/include/linux/nodemask_types.h
index 6b28d97ea6ed..f850a48742f1 100644
--- a/include/linux/nodemask_types.h
+++ b/include/linux/nodemask_types.h
@@ -3,7 +3,16 @@
 #define __LINUX_NODEMASK_TYPES_H
 
 #include <linux/bitops.h>
-#include <linux/numa.h>
+
+#ifdef CONFIG_NODES_SHIFT
+#define NODES_SHIFT     CONFIG_NODES_SHIFT
+#else
+#define NODES_SHIFT     0
+#endif
+
+#define MAX_NUMNODES    (1 << NODES_SHIFT)
+
+#define	NUMA_NO_NODE	(-1)
 
 typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;
 
diff --git a/include/linux/numa.h b/include/linux/numa.h
index 3567e40329eb..31d8bf8a951a 100644
--- a/include/linux/numa.h
+++ b/include/linux/numa.h
@@ -3,16 +3,8 @@
 #define _LINUX_NUMA_H
 #include <linux/init.h>
 #include <linux/types.h>
+#include <linux/nodemask.h>
 
-#ifdef CONFIG_NODES_SHIFT
-#define NODES_SHIFT     CONFIG_NODES_SHIFT
-#else
-#define NODES_SHIFT     0
-#endif
-
-#define MAX_NUMNODES    (1 << NODES_SHIFT)
-
-#define	NUMA_NO_NODE	(-1)
 #define	NUMA_NO_MEMBLK	(-1)
 
 static inline bool numa_valid_node(int nid)
-- 
2.43.0

Re: [PATCH 1/6] mm/numa: Introduce numa_nearest_nodemask()

[Andrea Righi]

On Mon, Feb 10, 2025 at 11:41:48AM -0500, Yury Norov wrote:
...
> > > Numa should include this via linux/nodemask_types.h, or maybe
> > > nodemask.h.
> > 
> > Hm... nodemask_types.h needs to include numa.h to resolve MAX_NUMNODES,
> > Maybe we can move numa_nearest_nodemask() to linux/nodemask.h?
> 
> Maybe yes, but it's generally wrong. nodemask.h is a library, and
> numa.h (generally, NUMA code) is one user. The right way to go is when
> client code includes all necessary libs, not vise-versa.

Ok, makes sense.

> 
> Regarding MAX_NUMNODES, it's a natural property of nodemasks, and
> should be declared in nodemask.h. The attached patch reverts the
> inclusion paths dependency. I build-tested it against today's master
> and x86_64 defconfig. Can you consider taking it and prepending your
> series?

Sure, I'll test it and include it in the next version.

>  
> > > >  #ifdef CONFIG_NUMA
> > > >  #include <asm/sparsemem.h>
> > > >  
> > > > @@ -38,6 +40,7 @@ void __init alloc_offline_node_data(int nid);
> > > >  
> > > >  /* Generic implementation available */
> > > >  int numa_nearest_node(int node, unsigned int state);
> > > > +int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask);
> > > >  
> > > >  #ifndef memory_add_physaddr_to_nid
> > > >  int memory_add_physaddr_to_nid(u64 start);
> > > > @@ -55,6 +58,11 @@ static inline int numa_nearest_node(int node, unsigned int state)
> > > >  	return NUMA_NO_NODE;
> > > >  }
> > > >  
> > > > +static inline int numa_nearest_nodemask(int node, unsigned int state, struct nodemask *mask)
> > > > +{
> > > > +	return NUMA_NO_NODE;
> > > > +}
> > > > +
> > > >  static inline int memory_add_physaddr_to_nid(u64 start)
> > > >  {
> > > >  	return 0;
> > > > diff --git a/mm/mempolicy.c b/mm/mempolicy.c
> > > > index 162407fbf2bc7..1cfee509c7229 100644
> > > > --- a/mm/mempolicy.c
> > > > +++ b/mm/mempolicy.c
> > > > @@ -196,6 +196,44 @@ int numa_nearest_node(int node, unsigned int state)
> > > >  }
> > > >  EXPORT_SYMBOL_GPL(numa_nearest_node);
> > > >  
> > > > +/**
> > > > + * numa_nearest_nodemask - Find the node in @mask at the nearest distance
> > > > + *			   from @node.
> > > > + *
> > > 
> > > So, I have a feeling about this whole naming scheme. At first, this
> > > function (and the existing numa_nearest_node()) searches for something,
> > > but doesn't begin with find_, search_ or similar. Second, the naming
> > > of existing numa_nearest_node() doesn't reflect that it searches
> > > against the state. Should we always include some state for search? If
> > > so, we can skip mentioning the state, otherwise it should be in the
> > > name, I guess...
> > > 
> > > The problem is that I have no idea for better naming, and I have no
> > > understanding about the future of this functions family. If it's just
> > > numa_nearest_node() and numa_nearest_nodemask(), I'm OK to go this
> > > way. If we'll add more flavors similarly to find_bit() family, we
> > > could probably discuss a naming scheme.
> > > 
> > > Also, mm/mempolicy.c is a historical place for them, but maybe we need
> > > to move it somewhere else?
> > > 
> > > Any thoughts appreciated.
> > 
> > Personally I think adding "find_" to the name would be a bit redundant, as
> > it seems quite obvious that it's finding the nearest node. It sounds a bit
> > like the get_something() discussion and we can just use something().
> > 
> > About adding "_state" to the name, it'd make sense since we have
> > for_each_node_state/for_each_node(), but we would need to change
> > numa_nearest_node() -> numa_nearest_node_state((), that is beyond the scope
> > of this patch set.
> > 
> > If I had to design this completely from scratch I'd probably propose
> > something like this:
> >  - nearest_node_state(node, state)
> >  - nearest_node(node) -> nearest_node_state(node, N_POSSIBLE)
> >  - nearest_node_nodemask(node, nodemask) -> here the state can be managed
> >    with the nodemask (as you suggested below)
> > 
> > But again, this is probably a more generic discussion that can be addressed
> > in a separate thread.
> 
> Yes, it's not related to your series. Please just introduce
> nearest_node_nodemask(node, nodemask) as your minimal required change.
> I will do a necessary cleanup later, if needed.

Ok, thanks!

-Andrea

[PATCH 2/6] sched/topology: Introduce for_each_numa_node() iterator

[Andrea Righi]

Introduce the new helper for_each_numa_node() to iterate over node IDs
in order of increasing NUMA distance from a given starting node.

This iterator is similar to for_each_numa_hop_mask(), but instead of
providing a cpumask at each iteration, it provides a node ID.

Example usage:

  nodemask_t unvisited = NODE_MASK_ALL;
  int node, start = cpu_to_node(smp_processor_id());

  node = start;
  for_each_numa_node(node, unvisited, N_ONLINE)
  	pr_info("node (%d, %d) -> %d\n",
  		 start, node, node_distance(start, node));

On a system with equidistant nodes:

 $ numactl -H
 ...
 node distances:
 node     0    1    2    3
    0:   10   20   20   20
    1:   20   10   20   20
    2:   20   20   10   20
    3:   20   20   20   10

Output of the example above (on node 0):

[    7.367022] node (0, 0) -> 10
[    7.367151] node (0, 1) -> 20
[    7.367186] node (0, 2) -> 20
[    7.367247] node (0, 3) -> 20

On a system with non-equidistant nodes (simulated using virtme-ng):

 $ numactl -H
 ...
 node distances:
 node     0    1    2    3
    0:   10   51   31   41
    1:   51   10   21   61
    2:   31   21   10   11
    3:   41   61   11   10

Output of the example above (on node 0):

 [    8.953644] node (0, 0) -> 10
 [    8.953712] node (0, 2) -> 31
 [    8.953764] node (0, 3) -> 41
 [    8.953817] node (0, 1) -> 51

Cc: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 include/linux/topology.h | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

diff --git a/include/linux/topology.h b/include/linux/topology.h
index 52f5850730b3e..09c18ee8be0eb 100644
--- a/include/linux/topology.h
+++ b/include/linux/topology.h
@@ -261,6 +261,34 @@ sched_numa_hop_mask(unsigned int node, unsigned int hops)
 }
 #endif	/* CONFIG_NUMA */
 
+/**
+ * for_each_numa_node - iterate over nodes at increasing distances from a
+ *			given starting node.
+ * @node: the iteration variable and the starting node.
+ * @unvisited: a nodemask to keep track of the unvisited nodes.
+ * @state: state of NUMA nodes to iterate.
+ *
+ * This macro iterates over NUMA node IDs in increasing distance from the
+ * starting @node and yields MAX_NUMNODES when all the nodes have been
+ * visited.
+ *
+ * The difference between for_each_node() and for_each_numa_node() is that
+ * the former allows to iterate over nodes in numerical order, whereas the
+ * latter iterates over nodes in increasing order of distance.
+ *
+ * This complexity of this iterator is O(N^2), where N represents the
+ * number of nodes, as each iteration involves scanning all nodes to
+ * find the one with the shortest distance.
+ *
+ * Requires rcu_lock to be held.
+ */
+#define for_each_numa_node(node, unvisited, state)				\
+	for (int start = (node),						\
+	     node = numa_nearest_nodemask((start), (state), &(unvisited));	\
+	     node < MAX_NUMNODES;						\
+	     node_clear(node, (unvisited)),					\
+	     node = numa_nearest_nodemask((start), (state), &(unvisited)))
+
 /**
  * for_each_numa_hop_mask - iterate over cpumasks of increasing NUMA distance
  *                          from a given node.
-- 
2.48.1

Re: [PATCH 2/6] sched/topology: Introduce for_each_numa_node() iterator

[Tejun Heo]

On Fri, Feb 07, 2025 at 09:40:49PM +0100, Andrea Righi wrote:
> +/**
> + * for_each_numa_node - iterate over nodes at increasing distances from a
> + *			given starting node.
> + * @node: the iteration variable and the starting node.
> + * @unvisited: a nodemask to keep track of the unvisited nodes.
> + * @state: state of NUMA nodes to iterate.
> + *
> + * This macro iterates over NUMA node IDs in increasing distance from the
> + * starting @node and yields MAX_NUMNODES when all the nodes have been
> + * visited.
> + *
> + * The difference between for_each_node() and for_each_numa_node() is that
> + * the former allows to iterate over nodes in numerical order, whereas the
> + * latter iterates over nodes in increasing order of distance.
> + *
> + * This complexity of this iterator is O(N^2), where N represents the
> + * number of nodes, as each iteration involves scanning all nodes to
> + * find the one with the shortest distance.
> + *
> + * Requires rcu_lock to be held.
> + */
> +#define for_each_numa_node(node, unvisited, state)				\
> +	for (int start = (node),						\
> +	     node = numa_nearest_nodemask((start), (state), &(unvisited));	\
> +	     node < MAX_NUMNODES;						\
> +	     node_clear(node, (unvisited)),					\
> +	     node = numa_nearest_nodemask((start), (state), &(unvisited)))
> +
>  /**
>   * for_each_numa_hop_mask - iterate over cpumasks of increasing NUMA distance
>   *                          from a given node.

Bikeshedding: Maybe this has already been argued back and forth but I find
the distinction between for_each_node() and for_each_numa_node() way too
subtle. I wouldn't suspect that they are doing different things when
glancing through their usages in isolation. Can we add *something* to the
name that indicates that this is iteration by distance? The next one uses
"hop" which is fine, "_by_dist" can be fine too, or even "_from_nearest". I
don't really care which but let's make the name clearly signal what it's
doing.

Thanks.

-- 
tejun

Re: [PATCH 2/6] sched/topology: Introduce for_each_numa_node() iterator

[Andrea Righi]

On Fri, Feb 07, 2025 at 11:46:51AM -1000, Tejun Heo wrote:
> On Fri, Feb 07, 2025 at 09:40:49PM +0100, Andrea Righi wrote:
> > +/**
> > + * for_each_numa_node - iterate over nodes at increasing distances from a
> > + *			given starting node.
> > + * @node: the iteration variable and the starting node.
> > + * @unvisited: a nodemask to keep track of the unvisited nodes.
> > + * @state: state of NUMA nodes to iterate.
> > + *
> > + * This macro iterates over NUMA node IDs in increasing distance from the
> > + * starting @node and yields MAX_NUMNODES when all the nodes have been
> > + * visited.
> > + *
> > + * The difference between for_each_node() and for_each_numa_node() is that
> > + * the former allows to iterate over nodes in numerical order, whereas the
> > + * latter iterates over nodes in increasing order of distance.
> > + *
> > + * This complexity of this iterator is O(N^2), where N represents the
> > + * number of nodes, as each iteration involves scanning all nodes to
> > + * find the one with the shortest distance.
> > + *
> > + * Requires rcu_lock to be held.
> > + */
> > +#define for_each_numa_node(node, unvisited, state)				\
> > +	for (int start = (node),						\
> > +	     node = numa_nearest_nodemask((start), (state), &(unvisited));	\
> > +	     node < MAX_NUMNODES;						\
> > +	     node_clear(node, (unvisited)),					\
> > +	     node = numa_nearest_nodemask((start), (state), &(unvisited)))
> > +
> >  /**
> >   * for_each_numa_hop_mask - iterate over cpumasks of increasing NUMA distance
> >   *                          from a given node.
> 
> Bikeshedding: Maybe this has already been argued back and forth but I find
> the distinction between for_each_node() and for_each_numa_node() way too
> subtle. I wouldn't suspect that they are doing different things when
> glancing through their usages in isolation. Can we add *something* to the
> name that indicates that this is iteration by distance? The next one uses
> "hop" which is fine, "_by_dist" can be fine too, or even "_from_nearest". I
> don't really care which but let's make the name clearly signal what it's
> doing.
> 
> Thanks.

How about for_each_node_state_by_dist()? It's essentialy a variant of
for_each_node_state(), as it also accepts a state, with the only difference
that node IDs are returned in increasing distance order.

-Andrea

Re: [PATCH 2/6] sched/topology: Introduce for_each_numa_node() iterator

[Tejun Heo]

On Fri, Feb 07, 2025 at 10:55:18PM +0100, Andrea Righi wrote:
> How about for_each_node_state_by_dist()? It's essentialy a variant of
> for_each_node_state(), as it also accepts a state, with the only difference
> that node IDs are returned in increasing distance order.

Sounds fine by me. Yury?

Thanks.

-- 
tejun

Re: [PATCH 2/6] sched/topology: Introduce for_each_numa_node() iterator

[Yury Norov]

On Fri, Feb 07, 2025 at 11:56:30AM -1000, Tejun Heo wrote:
> On Fri, Feb 07, 2025 at 10:55:18PM +0100, Andrea Righi wrote:
> > How about for_each_node_state_by_dist()? It's essentialy a variant of
> > for_each_node_state(), as it also accepts a state, with the only difference
> > that node IDs are returned in increasing distance order.
> 
> Sounds fine by me. Yury?

for_each_node_numadist() maybe? Whichever you choose is good to me.

Re: [PATCH 2/6] sched/topology: Introduce for_each_numa_node() iterator

[Yury Norov]

On Fri, Feb 07, 2025 at 09:40:49PM +0100, Andrea Righi wrote:
> Introduce the new helper for_each_numa_node() to iterate over node IDs
> in order of increasing NUMA distance from a given starting node.
> 
> This iterator is similar to for_each_numa_hop_mask(), but instead of
> providing a cpumask at each iteration, it provides a node ID.
> 
> Example usage:
> 
>   nodemask_t unvisited = NODE_MASK_ALL;
>   int node, start = cpu_to_node(smp_processor_id());
> 
>   node = start;
>   for_each_numa_node(node, unvisited, N_ONLINE)
>   	pr_info("node (%d, %d) -> %d\n",
>   		 start, node, node_distance(start, node));
> 
> On a system with equidistant nodes:
> 
>  $ numactl -H
>  ...
>  node distances:
>  node     0    1    2    3
>     0:   10   20   20   20
>     1:   20   10   20   20
>     2:   20   20   10   20
>     3:   20   20   20   10
> 
> Output of the example above (on node 0):
> 
> [    7.367022] node (0, 0) -> 10
> [    7.367151] node (0, 1) -> 20
> [    7.367186] node (0, 2) -> 20
> [    7.367247] node (0, 3) -> 20
> 
> On a system with non-equidistant nodes (simulated using virtme-ng):

Great to see virtme-ng maturing!
 
>  $ numactl -H
>  ...
>  node distances:
>  node     0    1    2    3
>     0:   10   51   31   41
>     1:   51   10   21   61
>     2:   31   21   10   11
>     3:   41   61   11   10
> 
> Output of the example above (on node 0):
> 
>  [    8.953644] node (0, 0) -> 10
>  [    8.953712] node (0, 2) -> 31
>  [    8.953764] node (0, 3) -> 41
>  [    8.953817] node (0, 1) -> 51
> 
> Cc: Yury Norov <yury.norov@gmail.com>
> Signed-off-by: Andrea Righi <arighi@nvidia.com>
> ---
>  include/linux/topology.h | 28 ++++++++++++++++++++++++++++
>  1 file changed, 28 insertions(+)
> 
> diff --git a/include/linux/topology.h b/include/linux/topology.h
> index 52f5850730b3e..09c18ee8be0eb 100644
> --- a/include/linux/topology.h
> +++ b/include/linux/topology.h
> @@ -261,6 +261,34 @@ sched_numa_hop_mask(unsigned int node, unsigned int hops)
>  }
>  #endif	/* CONFIG_NUMA */
>  
> +/**
> + * for_each_numa_node - iterate over nodes at increasing distances from a
> + *			given starting node.

Nit: in increasing distance order, starting from a given node

> + * @node: the iteration variable and the starting node.
> + * @unvisited: a nodemask to keep track of the unvisited nodes.
> + * @state: state of NUMA nodes to iterate.
> + *
> + * This macro iterates over NUMA node IDs in increasing distance from the
> + * starting @node and yields MAX_NUMNODES when all the nodes have been
> + * visited.

Please also mention that the unvisited nodemask will be empty when it finish.

> + *
> + * The difference between for_each_node() and for_each_numa_node() is that
> + * the former allows to iterate over nodes in numerical order, whereas the
> + * latter iterates over nodes in increasing order of distance.
> + *
> + * This complexity of this iterator is O(N^2), where N represents the
> + * number of nodes, as each iteration involves scanning all nodes to
> + * find the one with the shortest distance.
> + *
> + * Requires rcu_lock to be held.
> + */
> +#define for_each_numa_node(node, unvisited, state)				\
> +	for (int start = (node),						\
> +	     node = numa_nearest_nodemask((start), (state), &(unvisited));	\
> +	     node < MAX_NUMNODES;						\
> +	     node_clear(node, (unvisited)),					\
> +	     node = numa_nearest_nodemask((start), (state), &(unvisited)))
> +
>  /**
>   * for_each_numa_hop_mask - iterate over cpumasks of increasing NUMA distance
>   *                          from a given node.
> -- 
> 2.48.1

[PATCH 3/6] sched_ext: idle: Introduce SCX_OPS_BUILTIN_IDLE_PER_NODE

[Andrea Righi]

Add the new scheduler flag SCX_OPS_BUILTIN_IDLE_PER_NODE, which allows
scx schedulers to select between using a global flat idle cpumask or
multiple per-node cpumasks.

This only introduces the flag and the mechanism to enable/disable this
feature without affecting any scheduling behavior.

Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 kernel/sched/ext.c      | 21 +++++++++++++++++++--
 kernel/sched/ext_idle.c | 33 +++++++++++++++++++++++++--------
 kernel/sched/ext_idle.h |  6 ++++--
 3 files changed, 48 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 8a9a30895381a..0063a646124bc 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -125,6 +125,12 @@ enum scx_ops_flags {
 	 */
 	SCX_OPS_SWITCH_PARTIAL	= 1LLU << 3,
 
+	/*
+	 * If set, enable per-node idle cpumasks. If clear, use a single global
+	 * flat idle cpumask.
+	 */
+	SCX_OPS_BUILTIN_IDLE_PER_NODE = 1LLU << 4,
+
 	/*
 	 * CPU cgroup support flags
 	 */
@@ -134,6 +140,7 @@ enum scx_ops_flags {
 				  SCX_OPS_ENQ_LAST |
 				  SCX_OPS_ENQ_EXITING |
 				  SCX_OPS_SWITCH_PARTIAL |
+				  SCX_OPS_BUILTIN_IDLE_PER_NODE |
 				  SCX_OPS_HAS_CGROUP_WEIGHT,
 };
 
@@ -3344,7 +3351,7 @@ static void handle_hotplug(struct rq *rq, bool online)
 	atomic_long_inc(&scx_hotplug_seq);
 
 	if (scx_enabled())
-		scx_idle_update_selcpu_topology();
+		scx_idle_update_selcpu_topology(&scx_ops);
 
 	if (online && SCX_HAS_OP(cpu_online))
 		SCX_CALL_OP(SCX_KF_UNLOCKED, cpu_online, cpu);
@@ -5116,6 +5123,16 @@ static int validate_ops(const struct sched_ext_ops *ops)
 		return -EINVAL;
 	}
 
+	/*
+	 * SCX_OPS_BUILTIN_IDLE_PER_NODE requires built-in CPU idle
+	 * selection policy to be enabled.
+	 */
+	if ((ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE) &&
+	    (ops->update_idle && !(ops->flags & SCX_OPS_KEEP_BUILTIN_IDLE))) {
+		scx_ops_error("SCX_OPS_BUILTIN_IDLE_PER_NODE requires CPU idle selection enabled");
+		return -EINVAL;
+	}
+
 	return 0;
 }
 
@@ -5240,7 +5257,7 @@ static int scx_ops_enable(struct sched_ext_ops *ops, struct bpf_link *link)
 			static_branch_enable_cpuslocked(&scx_has_op[i]);
 
 	check_hotplug_seq(ops);
-	scx_idle_update_selcpu_topology();
+	scx_idle_update_selcpu_topology(ops);
 
 	cpus_read_unlock();
 
diff --git a/kernel/sched/ext_idle.c b/kernel/sched/ext_idle.c
index cb981956005b4..a3f2b00903ac2 100644
--- a/kernel/sched/ext_idle.c
+++ b/kernel/sched/ext_idle.c
@@ -14,6 +14,9 @@
 /* Enable/disable built-in idle CPU selection policy */
 DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_enabled);
 
+/* Enable/disable per-node idle cpumasks */
+DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_per_node);
+
 #ifdef CONFIG_SMP
 #ifdef CONFIG_CPUMASK_OFFSTACK
 #define CL_ALIGNED_IF_ONSTACK
@@ -204,9 +207,9 @@ static bool llc_numa_mismatch(void)
  * CPU belongs to a single LLC domain, and that each LLC domain is entirely
  * contained within a single NUMA node.
  */
-void scx_idle_update_selcpu_topology(void)
+void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops)
 {
-	bool enable_llc = false, enable_numa = false;
+	bool enable_llc = false, enable_numa = false, enable_idle_node = false;
 	unsigned int nr_cpus;
 	s32 cpu = cpumask_first(cpu_online_mask);
 
@@ -237,13 +240,21 @@ void scx_idle_update_selcpu_topology(void)
 	 * If all CPUs belong to the same NUMA node and the same LLC domain,
 	 * enabling both NUMA and LLC optimizations is unnecessary, as checking
 	 * for an idle CPU in the same domain twice is redundant.
+	 *
+	 * If SCX_OPS_BUILTIN_IDLE_PER_NODE is enabled ignore the NUMA
+	 * optimization, as we would naturally select idle CPUs within
+	 * specific NUMA nodes querying the corresponding per-node cpumask.
 	 */
-	nr_cpus = numa_weight(cpu);
-	if (nr_cpus > 0) {
-		if (nr_cpus < num_online_cpus() && llc_numa_mismatch())
-			enable_numa = true;
-		pr_debug("sched_ext: NUMA=%*pb weight=%u\n",
-			 cpumask_pr_args(numa_span(cpu)), numa_weight(cpu));
+	if (ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE) {
+		enable_idle_node = true;
+	} else {
+		nr_cpus = numa_weight(cpu);
+		if (nr_cpus > 0) {
+			if (nr_cpus < num_online_cpus() && llc_numa_mismatch())
+				enable_numa = true;
+			pr_debug("sched_ext: NUMA=%*pb weight=%u\n",
+				 cpumask_pr_args(numa_span(cpu)), numa_weight(cpu));
+		}
 	}
 	rcu_read_unlock();
 
@@ -251,6 +262,8 @@ void scx_idle_update_selcpu_topology(void)
 		 str_enabled_disabled(enable_llc));
 	pr_debug("sched_ext: NUMA idle selection %s\n",
 		 str_enabled_disabled(enable_numa));
+	pr_debug("sched_ext: per-node idle cpumask %s\n",
+		 str_enabled_disabled(enable_idle_node));
 
 	if (enable_llc)
 		static_branch_enable_cpuslocked(&scx_selcpu_topo_llc);
@@ -260,6 +273,10 @@ void scx_idle_update_selcpu_topology(void)
 		static_branch_enable_cpuslocked(&scx_selcpu_topo_numa);
 	else
 		static_branch_disable_cpuslocked(&scx_selcpu_topo_numa);
+	if (enable_idle_node)
+		static_branch_enable_cpuslocked(&scx_builtin_idle_per_node);
+	else
+		static_branch_disable_cpuslocked(&scx_builtin_idle_per_node);
 }
 
 /*
diff --git a/kernel/sched/ext_idle.h b/kernel/sched/ext_idle.h
index 7a13a74815ba7..d005bd22c19a5 100644
--- a/kernel/sched/ext_idle.h
+++ b/kernel/sched/ext_idle.h
@@ -10,19 +10,21 @@
 #ifndef _KERNEL_SCHED_EXT_IDLE_H
 #define _KERNEL_SCHED_EXT_IDLE_H
 
+struct sched_ext_ops;
+
 extern struct static_key_false scx_builtin_idle_enabled;
 
 #ifdef CONFIG_SMP
 extern struct static_key_false scx_selcpu_topo_llc;
 extern struct static_key_false scx_selcpu_topo_numa;
 
-void scx_idle_update_selcpu_topology(void);
+void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops);
 void scx_idle_reset_masks(void);
 void scx_idle_init_masks(void);
 bool scx_idle_test_and_clear_cpu(int cpu);
 s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags);
 #else /* !CONFIG_SMP */
-static inline void scx_idle_update_selcpu_topology(void) {}
+static inline void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops) {}
 static inline void scx_idle_reset_masks(void) {}
 static inline void scx_idle_init_masks(void) {}
 static inline bool scx_idle_test_and_clear_cpu(int cpu) { return false; }
-- 
2.48.1

[PATCH 4/6] sched_ext: idle: introduce SCX_PICK_IDLE_IN_NODE

[Andrea Righi]

Introduce a new flag to restrict the selection of an idle CPU to a
single specific NUMA node.

Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 kernel/sched/ext.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 0063a646124bc..8dbe22167c158 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -775,6 +775,7 @@ enum scx_deq_flags {
 
 enum scx_pick_idle_cpu_flags {
 	SCX_PICK_IDLE_CORE	= 1LLU << 0,	/* pick a CPU whose SMT siblings are also idle */
+	SCX_PICK_IDLE_IN_NODE	= 1LLU << 1,	/* pick a CPU in the same target NUMA node */
 };
 
 enum scx_kick_flags {
-- 
2.48.1

Re: [PATCH 4/6] sched_ext: idle: introduce SCX_PICK_IDLE_IN_NODE

[Tejun Heo]

On Fri, Feb 07, 2025 at 09:40:51PM +0100, Andrea Righi wrote:
> Introduce a new flag to restrict the selection of an idle CPU to a
> single specific NUMA node.
> 
> Signed-off-by: Andrea Righi <arighi@nvidia.com>
> ---
>  kernel/sched/ext.c | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
> index 0063a646124bc..8dbe22167c158 100644
> --- a/kernel/sched/ext.c
> +++ b/kernel/sched/ext.c
> @@ -775,6 +775,7 @@ enum scx_deq_flags {
>  
>  enum scx_pick_idle_cpu_flags {
>  	SCX_PICK_IDLE_CORE	= 1LLU << 0,	/* pick a CPU whose SMT siblings are also idle */
> +	SCX_PICK_IDLE_IN_NODE	= 1LLU << 1,	/* pick a CPU in the same target NUMA node */
>  };

Please merge this into the patch which actually uses the flag.

Thanks.

-- 
tejun

[PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

Using a single global idle mask can lead to inefficiencies and a lot of
stress on the cache coherency protocol on large systems with multiple
NUMA nodes, since all the CPUs can create a really intense read/write
activity on the single global cpumask.

Therefore, split the global cpumask into multiple per-NUMA node cpumasks
to improve scalability and performance on large systems.

The concept is that each cpumask will track only the idle CPUs within
its corresponding NUMA node, treating CPUs in other NUMA nodes as busy.
In this way concurrent access to the idle cpumask will be restricted
within each NUMA node.

The split of multiple per-node idle cpumasks can be controlled using the
SCX_OPS_BUILTIN_IDLE_PER_NODE flag.

By default SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled and a global
host-wide idle cpumask is used, maintaining the previous behavior.

NOTE: if a scheduler explicitly enables the per-node idle cpumasks (via
SCX_OPS_BUILTIN_IDLE_PER_NODE), scx_bpf_get_idle_cpu/smtmask() will
trigger an scx error, since there are no system-wide cpumasks.

Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 kernel/sched/ext_idle.c | 242 ++++++++++++++++++++++++++++++++--------
 kernel/sched/ext_idle.h |  11 +-
 2 files changed, 203 insertions(+), 50 deletions(-)

diff --git a/kernel/sched/ext_idle.c b/kernel/sched/ext_idle.c
index a3f2b00903ac2..4b90ec9018c1a 100644
--- a/kernel/sched/ext_idle.c
+++ b/kernel/sched/ext_idle.c
@@ -18,25 +18,88 @@ DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_enabled);
 DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_per_node);
 
 #ifdef CONFIG_SMP
-#ifdef CONFIG_CPUMASK_OFFSTACK
-#define CL_ALIGNED_IF_ONSTACK
-#else
-#define CL_ALIGNED_IF_ONSTACK __cacheline_aligned_in_smp
-#endif
-
 /* Enable/disable LLC aware optimizations */
 DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_llc);
 
 /* Enable/disable NUMA aware optimizations */
 DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_numa);
 
-static struct {
+/*
+ * cpumasks to track idle CPUs within each NUMA node.
+ *
+ * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask
+ * from is used to track all the idle CPUs in the system.
+ */
+struct idle_cpus {
 	cpumask_var_t cpu;
 	cpumask_var_t smt;
-} idle_masks CL_ALIGNED_IF_ONSTACK;
+};
+
+/*
+ * Global host-wide idle cpumasks (used when SCX_OPS_BUILTIN_IDLE_PER_NODE
+ * is not enabled).
+ */
+static struct idle_cpus scx_idle_global_masks;
+
+/*
+ * Per-node idle cpumasks.
+ */
+static struct idle_cpus **scx_idle_node_masks;
+
+/*
+ * Initialize per-node idle cpumasks.
+ *
+ * In case of a single NUMA node or if NUMA support is disabled, only a
+ * single global host-wide cpumask will be initialized.
+ */
+void scx_idle_init_masks(void)
+{
+	int node;
+
+	/* Allocate global idle cpumasks */
+	BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.cpu, GFP_KERNEL));
+	BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.smt, GFP_KERNEL));
+
+	/* Allocate per-node idle cpumasks */
+	scx_idle_node_masks = kcalloc(num_possible_nodes(),
+				      sizeof(*scx_idle_node_masks), GFP_KERNEL);
+	BUG_ON(!scx_idle_node_masks);
+
+	for_each_node(node) {
+		scx_idle_node_masks[node] = kzalloc_node(sizeof(**scx_idle_node_masks),
+							 GFP_KERNEL, node);
+		BUG_ON(!scx_idle_node_masks[node]);
+
+		BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->cpu, GFP_KERNEL, node));
+		BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->smt, GFP_KERNEL, node));
+	}
+}
+
+/*
+ * Return the idle masks associated to a target @node.
+ */
+static struct idle_cpus *idle_cpumask(int node)
+{
+	return node == NUMA_NO_NODE ? &scx_idle_global_masks : scx_idle_node_masks[node];
+}
+
+/*
+ * Return the node id associated to a target idle CPU (used to determine
+ * the proper idle cpumask).
+ */
+static int idle_cpu_to_node(int cpu)
+{
+	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
+		return NUMA_NO_NODE;
+
+	return cpu_to_node(cpu);
+}
 
 bool scx_idle_test_and_clear_cpu(int cpu)
 {
+	int node = idle_cpu_to_node(cpu);
+	struct cpumask *idle_cpus = idle_cpumask(node)->cpu;
+
 #ifdef CONFIG_SCHED_SMT
 	/*
 	 * SMT mask should be cleared whether we can claim @cpu or not. The SMT
@@ -45,33 +108,38 @@ bool scx_idle_test_and_clear_cpu(int cpu)
 	 */
 	if (sched_smt_active()) {
 		const struct cpumask *smt = cpu_smt_mask(cpu);
+		struct cpumask *idle_smts = idle_cpumask(node)->smt;
 
 		/*
 		 * If offline, @cpu is not its own sibling and
 		 * scx_pick_idle_cpu() can get caught in an infinite loop as
-		 * @cpu is never cleared from idle_masks.smt. Ensure that @cpu
-		 * is eventually cleared.
+		 * @cpu is never cleared from the idle SMT mask. Ensure that
+		 * @cpu is eventually cleared.
 		 *
 		 * NOTE: Use cpumask_intersects() and cpumask_test_cpu() to
 		 * reduce memory writes, which may help alleviate cache
 		 * coherence pressure.
 		 */
-		if (cpumask_intersects(smt, idle_masks.smt))
-			cpumask_andnot(idle_masks.smt, idle_masks.smt, smt);
-		else if (cpumask_test_cpu(cpu, idle_masks.smt))
-			__cpumask_clear_cpu(cpu, idle_masks.smt);
+		if (cpumask_intersects(smt, idle_smts))
+			cpumask_andnot(idle_smts, idle_smts, smt);
+		else if (cpumask_test_cpu(cpu, idle_smts))
+			__cpumask_clear_cpu(cpu, idle_smts);
 	}
 #endif
-	return cpumask_test_and_clear_cpu(cpu, idle_masks.cpu);
+
+	return cpumask_test_and_clear_cpu(cpu, idle_cpus);
 }
 
-s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
+/*
+ * Pick an idle CPU in a specific NUMA node.
+ */
+s32 pick_idle_cpu_from_node(const struct cpumask *cpus_allowed, int node, u64 flags)
 {
 	int cpu;
 
 retry:
 	if (sched_smt_active()) {
-		cpu = cpumask_any_and_distribute(idle_masks.smt, cpus_allowed);
+		cpu = cpumask_any_and_distribute(idle_cpumask(node)->smt, cpus_allowed);
 		if (cpu < nr_cpu_ids)
 			goto found;
 
@@ -79,7 +147,7 @@ s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
 			return -EBUSY;
 	}
 
-	cpu = cpumask_any_and_distribute(idle_masks.cpu, cpus_allowed);
+	cpu = cpumask_any_and_distribute(idle_cpumask(node)->cpu, cpus_allowed);
 	if (cpu >= nr_cpu_ids)
 		return -EBUSY;
 
@@ -90,6 +158,55 @@ s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
 		goto retry;
 }
 
+/*
+ * Find the best idle CPU in the system, relative to @node.
+ */
+s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
+{
+	nodemask_t unvisited = NODE_MASK_ALL;
+	s32 cpu = -EBUSY;
+
+	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
+		return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);
+
+	/*
+	 * If an initial node is not specified, start with the current
+	 * node.
+	 */
+	if (node == NUMA_NO_NODE)
+		node = numa_node_id();
+
+	/*
+	 * Traverse all nodes in order of increasing distance, starting
+	 * from @node.
+	 *
+	 * This loop is O(N^2), with N being the amount of NUMA nodes,
+	 * which might be quite expensive in large NUMA systems. However,
+	 * this complexity comes into play only when a scheduler enables
+	 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU
+	 * without specifying a target NUMA node, so it shouldn't be a
+	 * bottleneck is most cases.
+	 *
+	 * As a future optimization we may want to cache the list of hop
+	 * nodes in a per-node array, instead of actually traversing them
+	 * every time.
+	 */
+	for_each_numa_node(node, unvisited, N_POSSIBLE) {
+		cpu = pick_idle_cpu_from_node(cpus_allowed, node, flags);
+		if (cpu >= 0)
+			break;
+
+		/*
+		 * Check if the search is restricted to the same core or
+		 * the same node.
+		 */
+		if (flags & SCX_PICK_IDLE_IN_NODE)
+			break;
+	}
+
+	return cpu;
+}
+
 /*
  * Return the amount of CPUs in the same LLC domain of @cpu (or zero if the LLC
  * domain is not defined).
@@ -310,6 +427,7 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 {
 	const struct cpumask *llc_cpus = NULL;
 	const struct cpumask *numa_cpus = NULL;
+	int node = idle_cpu_to_node(prev_cpu);
 	s32 cpu;
 
 	*found = false;
@@ -367,9 +485,9 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 		 * piled up on it even if there is an idle core elsewhere on
 		 * the system.
 		 */
-		if (!cpumask_empty(idle_masks.cpu) &&
-		    !(current->flags & PF_EXITING) &&
-		    cpu_rq(cpu)->scx.local_dsq.nr == 0) {
+		if (!(current->flags & PF_EXITING) &&
+		    cpu_rq(cpu)->scx.local_dsq.nr == 0 &&
+		    !cpumask_empty(idle_cpumask(cpu_to_node(cpu))->cpu)) {
 			if (cpumask_test_cpu(cpu, p->cpus_ptr))
 				goto cpu_found;
 		}
@@ -383,7 +501,7 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 		/*
 		 * Keep using @prev_cpu if it's part of a fully idle core.
 		 */
-		if (cpumask_test_cpu(prev_cpu, idle_masks.smt) &&
+		if (cpumask_test_cpu(prev_cpu, idle_cpumask(node)->smt) &&
 		    scx_idle_test_and_clear_cpu(prev_cpu)) {
 			cpu = prev_cpu;
 			goto cpu_found;
@@ -393,7 +511,7 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 		 * Search for any fully idle core in the same LLC domain.
 		 */
 		if (llc_cpus) {
-			cpu = scx_pick_idle_cpu(llc_cpus, SCX_PICK_IDLE_CORE);
+			cpu = pick_idle_cpu_from_node(llc_cpus, node, SCX_PICK_IDLE_CORE);
 			if (cpu >= 0)
 				goto cpu_found;
 		}
@@ -402,15 +520,19 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 		 * Search for any fully idle core in the same NUMA node.
 		 */
 		if (numa_cpus) {
-			cpu = scx_pick_idle_cpu(numa_cpus, SCX_PICK_IDLE_CORE);
+			cpu = pick_idle_cpu_from_node(numa_cpus, node, SCX_PICK_IDLE_CORE);
 			if (cpu >= 0)
 				goto cpu_found;
 		}
 
 		/*
 		 * Search for any full idle core usable by the task.
+		 *
+		 * If NUMA aware idle selection is enabled, the search will
+		 * begin in prev_cpu's node and proceed to other nodes in
+		 * order of increasing distance.
 		 */
-		cpu = scx_pick_idle_cpu(p->cpus_ptr, SCX_PICK_IDLE_CORE);
+		cpu = scx_pick_idle_cpu(p->cpus_ptr, node, SCX_PICK_IDLE_CORE);
 		if (cpu >= 0)
 			goto cpu_found;
 	}
@@ -427,7 +549,7 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 	 * Search for any idle CPU in the same LLC domain.
 	 */
 	if (llc_cpus) {
-		cpu = scx_pick_idle_cpu(llc_cpus, 0);
+		cpu = pick_idle_cpu_from_node(llc_cpus, node, 0);
 		if (cpu >= 0)
 			goto cpu_found;
 	}
@@ -436,7 +558,7 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 	 * Search for any idle CPU in the same NUMA node.
 	 */
 	if (numa_cpus) {
-		cpu = scx_pick_idle_cpu(numa_cpus, 0);
+		cpu = pick_idle_cpu_from_node(numa_cpus, node, 0);
 		if (cpu >= 0)
 			goto cpu_found;
 	}
@@ -444,7 +566,7 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 	/*
 	 * Search for any idle CPU usable by the task.
 	 */
-	cpu = scx_pick_idle_cpu(p->cpus_ptr, 0);
+	cpu = scx_pick_idle_cpu(p->cpus_ptr, node, 0);
 	if (cpu >= 0)
 		goto cpu_found;
 
@@ -460,38 +582,50 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
 
 void scx_idle_reset_masks(void)
 {
+	int node;
+
+	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) {
+		cpumask_copy(idle_cpumask(NUMA_NO_NODE)->cpu, cpu_online_mask);
+		cpumask_copy(idle_cpumask(NUMA_NO_NODE)->smt, cpu_online_mask);
+		return;
+	}
+
 	/*
 	 * Consider all online cpus idle. Should converge to the actual state
 	 * quickly.
 	 */
-	cpumask_copy(idle_masks.cpu, cpu_online_mask);
-	cpumask_copy(idle_masks.smt, cpu_online_mask);
-}
+	for_each_node(node) {
+		const struct cpumask *node_mask = cpumask_of_node(node);
+		struct cpumask *idle_cpus = idle_cpumask(node)->cpu;
+		struct cpumask *idle_smts = idle_cpumask(node)->smt;
 
-void scx_idle_init_masks(void)
-{
-	BUG_ON(!alloc_cpumask_var(&idle_masks.cpu, GFP_KERNEL));
-	BUG_ON(!alloc_cpumask_var(&idle_masks.smt, GFP_KERNEL));
+		cpumask_and(idle_cpus, cpu_online_mask, node_mask);
+		cpumask_copy(idle_smts, idle_cpus);
+	}
 }
 
 static void update_builtin_idle(int cpu, bool idle)
 {
-	assign_cpu(cpu, idle_masks.cpu, idle);
+	int node = idle_cpu_to_node(cpu);
+	struct cpumask *idle_cpus = idle_cpumask(node)->cpu;
+
+	assign_cpu(cpu, idle_cpus, idle);
 
 #ifdef CONFIG_SCHED_SMT
 	if (sched_smt_active()) {
 		const struct cpumask *smt = cpu_smt_mask(cpu);
+		struct cpumask *idle_smts = idle_cpumask(node)->smt;
 
 		if (idle) {
 			/*
-			 * idle_masks.smt handling is racy but that's fine as
-			 * it's only for optimization and self-correcting.
+			 * idle_smt handling is racy but that's fine as it's
+			 * only for optimization and self-correcting.
 			 */
-			if (!cpumask_subset(smt, idle_masks.cpu))
+			if (!cpumask_subset(smt, idle_cpus))
 				return;
-			cpumask_or(idle_masks.smt, idle_masks.smt, smt);
+			cpumask_or(idle_smts, idle_smts, smt);
 		} else {
-			cpumask_andnot(idle_masks.smt, idle_masks.smt, smt);
+			cpumask_andnot(idle_smts, idle_smts, smt);
 		}
 	}
 #endif
@@ -599,15 +733,21 @@ __bpf_kfunc s32 scx_bpf_select_cpu_dfl(struct task_struct *p, s32 prev_cpu,
  * scx_bpf_get_idle_cpumask - Get a referenced kptr to the idle-tracking
  * per-CPU cpumask.
  *
- * Returns NULL if idle tracking is not enabled, or running on a UP kernel.
+ * Returns an empty mask if idle tracking is not enabled, or running on a
+ * UP kernel.
  */
 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_cpumask(void)
 {
 	if (!check_builtin_idle_enabled())
 		return cpu_none_mask;
 
+	if (static_branch_unlikely(&scx_builtin_idle_per_node)) {
+		scx_ops_error("SCX_OPS_BUILTIN_IDLE_PER_NODE enabled");
+		return cpu_none_mask;
+	}
+
 #ifdef CONFIG_SMP
-	return idle_masks.cpu;
+	return idle_cpumask(NUMA_NO_NODE)->cpu;
 #else
 	return cpu_none_mask;
 #endif
@@ -618,18 +758,24 @@ __bpf_kfunc const struct cpumask *scx_bpf_get_idle_cpumask(void)
  * per-physical-core cpumask. Can be used to determine if an entire physical
  * core is free.
  *
- * Returns NULL if idle tracking is not enabled, or running on a UP kernel.
+ * Returns an empty mask if idle tracking is not enabled, or running on a
+ * UP kernel.
  */
 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_smtmask(void)
 {
 	if (!check_builtin_idle_enabled())
 		return cpu_none_mask;
 
+	if (static_branch_unlikely(&scx_builtin_idle_per_node)) {
+		scx_ops_error("SCX_OPS_BUILTIN_IDLE_PER_NODE enabled");
+		return cpu_none_mask;
+	}
+
 #ifdef CONFIG_SMP
 	if (sched_smt_active())
-		return idle_masks.smt;
+		return idle_cpumask(NUMA_NO_NODE)->smt;
 	else
-		return idle_masks.cpu;
+		return idle_cpumask(NUMA_NO_NODE)->cpu;
 #else
 	return cpu_none_mask;
 #endif
@@ -696,7 +842,7 @@ __bpf_kfunc s32 scx_bpf_pick_idle_cpu(const struct cpumask *cpus_allowed,
 	if (!check_builtin_idle_enabled())
 		return -EBUSY;
 
-	return scx_pick_idle_cpu(cpus_allowed, flags);
+	return scx_pick_idle_cpu(cpus_allowed, NUMA_NO_NODE, flags);
 }
 
 /**
@@ -719,7 +865,7 @@ __bpf_kfunc s32 scx_bpf_pick_any_cpu(const struct cpumask *cpus_allowed,
 	s32 cpu;
 
 	if (static_branch_likely(&scx_builtin_idle_enabled)) {
-		cpu = scx_pick_idle_cpu(cpus_allowed, flags);
+		cpu = scx_pick_idle_cpu(cpus_allowed, NUMA_NO_NODE, flags);
 		if (cpu >= 0)
 			return cpu;
 	}
diff --git a/kernel/sched/ext_idle.h b/kernel/sched/ext_idle.h
index d005bd22c19a5..b00ed5ad48e89 100644
--- a/kernel/sched/ext_idle.h
+++ b/kernel/sched/ext_idle.h
@@ -13,6 +13,7 @@
 struct sched_ext_ops;
 
 extern struct static_key_false scx_builtin_idle_enabled;
+extern struct static_key_false scx_builtin_idle_per_node;
 
 #ifdef CONFIG_SMP
 extern struct static_key_false scx_selcpu_topo_llc;
@@ -22,13 +23,18 @@ void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops);
 void scx_idle_reset_masks(void);
 void scx_idle_init_masks(void);
 bool scx_idle_test_and_clear_cpu(int cpu);
-s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags);
+s32 pick_idle_cpu_from_node(const struct cpumask *cpus_allowed, int node, u64 flags);
+s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags);
 #else /* !CONFIG_SMP */
 static inline void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops) {}
 static inline void scx_idle_reset_masks(void) {}
 static inline void scx_idle_init_masks(void) {}
 static inline bool scx_idle_test_and_clear_cpu(int cpu) { return false; }
-static inline s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
+static inline s32 pick_idle_cpu_from_node(const struct cpumask *cpus_allowed, int node, u64 flags)
+{
+	return -EBUSY;
+}
+static inline s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
 {
 	return -EBUSY;
 }
@@ -36,6 +42,7 @@ static inline s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flag
 
 s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool *found);
 
+extern void scx_idle_init_masks(void);
 extern int scx_idle_init(void);
 
 #endif /* _KERNEL_SCHED_EXT_IDLE_H */
-- 
2.48.1

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Tejun Heo]

Hello,

On Fri, Feb 07, 2025 at 09:40:52PM +0100, Andrea Righi wrote:
> +/*
> + * cpumasks to track idle CPUs within each NUMA node.
> + *
> + * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask
> + * from is used to track all the idle CPUs in the system.
> + */
> +struct idle_cpus {
>  	cpumask_var_t cpu;
>  	cpumask_var_t smt;
> -} idle_masks CL_ALIGNED_IF_ONSTACK;
> +};

Can you prefix the type name with scx_?

Unrelated to this series but I wonder whether we can replace "smt" with
"core" in the future to become more consistent with how the terms are used
in the kernel:

  struct scx_idle_masks {
          cpumask_var_t   cpus;
          cpumask_var_t   cores;
  };

We expose "smt" name through kfuncs but we can rename that to "core" through
compat macros later too.

> +/*
> + * Find the best idle CPU in the system, relative to @node.
> + */
> +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> +{
> +	nodemask_t unvisited = NODE_MASK_ALL;
> +	s32 cpu = -EBUSY;
> +
> +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
> +		return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);
> +
> +	/*
> +	 * If an initial node is not specified, start with the current
> +	 * node.
> +	 */
> +	if (node == NUMA_NO_NODE)
> +		node = numa_node_id();
> +
> +	/*
> +	 * Traverse all nodes in order of increasing distance, starting
> +	 * from @node.
> +	 *
> +	 * This loop is O(N^2), with N being the amount of NUMA nodes,
> +	 * which might be quite expensive in large NUMA systems. However,
> +	 * this complexity comes into play only when a scheduler enables
> +	 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU
> +	 * without specifying a target NUMA node, so it shouldn't be a
> +	 * bottleneck is most cases.
> +	 *
> +	 * As a future optimization we may want to cache the list of hop
> +	 * nodes in a per-node array, instead of actually traversing them
> +	 * every time.
> +	 */
> +	for_each_numa_node(node, unvisited, N_POSSIBLE) {
> +		cpu = pick_idle_cpu_from_node(cpus_allowed, node, flags);

Maybe rename pick_idle_cpu_in_node() to stay in sync with
SCX_PICK_IDLE_IN_NODE? It's not like pick_idle_cpu_from_node() walks from
the node, right? It just picks within the node.

> @@ -460,38 +582,50 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
>  
>  void scx_idle_reset_masks(void)
>  {
> +	int node;
> +
> +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) {
> +		cpumask_copy(idle_cpumask(NUMA_NO_NODE)->cpu, cpu_online_mask);
> +		cpumask_copy(idle_cpumask(NUMA_NO_NODE)->smt, cpu_online_mask);
> +		return;
> +	}
> +
>  	/*
>  	 * Consider all online cpus idle. Should converge to the actual state
>  	 * quickly.
>  	 */
> -	cpumask_copy(idle_masks.cpu, cpu_online_mask);
> -	cpumask_copy(idle_masks.smt, cpu_online_mask);
> -}
> +	for_each_node(node) {
> +		const struct cpumask *node_mask = cpumask_of_node(node);
> +		struct cpumask *idle_cpus = idle_cpumask(node)->cpu;
> +		struct cpumask *idle_smts = idle_cpumask(node)->smt;
> -void scx_idle_init_masks(void)
> -{
> -	BUG_ON(!alloc_cpumask_var(&idle_masks.cpu, GFP_KERNEL));
> -	BUG_ON(!alloc_cpumask_var(&idle_masks.smt, GFP_KERNEL));
> +		cpumask_and(idle_cpus, cpu_online_mask, node_mask);
> +		cpumask_copy(idle_smts, idle_cpus);
> +	}

nitpick: Maybe something like the following is more symmetric with the
global case and easier to read?

  for_each_node(node) {
        const struct cpumask *node_mask = cpumask_of_node(node);
        cpumask_and(idle_cpumask(node)->cpu, cpu_online_mask, node_mask);
        cpumask_and(idle_cpumask(node)->smt, cpu_online_mask, node_mask);
  }

>  }
>  
>  static void update_builtin_idle(int cpu, bool idle)
>  {
> -	assign_cpu(cpu, idle_masks.cpu, idle);
> +	int node = idle_cpu_to_node(cpu);

minor: I wonder whether idle_cpu_to_node() name is a bit confusing - why
does a CPU being idle have anything to do with its node mapping? If there is
a better naming convention, great. If not, it is what it is.

Thanks.

-- 
tejun

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

On Fri, Feb 07, 2025 at 12:30:37PM -1000, Tejun Heo wrote:
> Hello,
> 
> On Fri, Feb 07, 2025 at 09:40:52PM +0100, Andrea Righi wrote:
> > +/*
> > + * cpumasks to track idle CPUs within each NUMA node.
> > + *
> > + * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask
> > + * from is used to track all the idle CPUs in the system.
> > + */
> > +struct idle_cpus {
> >  	cpumask_var_t cpu;
> >  	cpumask_var_t smt;
> > -} idle_masks CL_ALIGNED_IF_ONSTACK;
> > +};
> 
> Can you prefix the type name with scx_?
> 
> Unrelated to this series but I wonder whether we can replace "smt" with
> "core" in the future to become more consistent with how the terms are used
> in the kernel:
> 
>   struct scx_idle_masks {
>           cpumask_var_t   cpus;
>           cpumask_var_t   cores;
>   };
> 
> We expose "smt" name through kfuncs but we can rename that to "core" through
> compat macros later too.
> 
> > +/*
> > + * Find the best idle CPU in the system, relative to @node.
> > + */
> > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > +{
> > +	nodemask_t unvisited = NODE_MASK_ALL;
> > +	s32 cpu = -EBUSY;
> > +
> > +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
> > +		return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);
> > +
> > +	/*
> > +	 * If an initial node is not specified, start with the current
> > +	 * node.
> > +	 */
> > +	if (node == NUMA_NO_NODE)
> > +		node = numa_node_id();
> > +
> > +	/*
> > +	 * Traverse all nodes in order of increasing distance, starting
> > +	 * from @node.
> > +	 *
> > +	 * This loop is O(N^2), with N being the amount of NUMA nodes,
> > +	 * which might be quite expensive in large NUMA systems. However,
> > +	 * this complexity comes into play only when a scheduler enables
> > +	 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU
> > +	 * without specifying a target NUMA node, so it shouldn't be a
> > +	 * bottleneck is most cases.
> > +	 *
> > +	 * As a future optimization we may want to cache the list of hop
> > +	 * nodes in a per-node array, instead of actually traversing them
> > +	 * every time.
> > +	 */
> > +	for_each_numa_node(node, unvisited, N_POSSIBLE) {
> > +		cpu = pick_idle_cpu_from_node(cpus_allowed, node, flags);
> 
> Maybe rename pick_idle_cpu_in_node() to stay in sync with
> SCX_PICK_IDLE_IN_NODE? It's not like pick_idle_cpu_from_node() walks from
> the node, right? It just picks within the node.
> 
> > @@ -460,38 +582,50 @@ s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, bool
> >  
> >  void scx_idle_reset_masks(void)
> >  {
> > +	int node;
> > +
> > +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) {
> > +		cpumask_copy(idle_cpumask(NUMA_NO_NODE)->cpu, cpu_online_mask);
> > +		cpumask_copy(idle_cpumask(NUMA_NO_NODE)->smt, cpu_online_mask);
> > +		return;
> > +	}
> > +
> >  	/*
> >  	 * Consider all online cpus idle. Should converge to the actual state
> >  	 * quickly.
> >  	 */
> > -	cpumask_copy(idle_masks.cpu, cpu_online_mask);
> > -	cpumask_copy(idle_masks.smt, cpu_online_mask);
> > -}
> > +	for_each_node(node) {
> > +		const struct cpumask *node_mask = cpumask_of_node(node);
> > +		struct cpumask *idle_cpus = idle_cpumask(node)->cpu;
> > +		struct cpumask *idle_smts = idle_cpumask(node)->smt;
> > -void scx_idle_init_masks(void)
> > -{
> > -	BUG_ON(!alloc_cpumask_var(&idle_masks.cpu, GFP_KERNEL));
> > -	BUG_ON(!alloc_cpumask_var(&idle_masks.smt, GFP_KERNEL));
> > +		cpumask_and(idle_cpus, cpu_online_mask, node_mask);
> > +		cpumask_copy(idle_smts, idle_cpus);
> > +	}
> 
> nitpick: Maybe something like the following is more symmetric with the
> global case and easier to read?
> 
>   for_each_node(node) {
>         const struct cpumask *node_mask = cpumask_of_node(node);
>         cpumask_and(idle_cpumask(node)->cpu, cpu_online_mask, node_mask);
>         cpumask_and(idle_cpumask(node)->smt, cpu_online_mask, node_mask);
>   }
> 
> >  }
> >  
> >  static void update_builtin_idle(int cpu, bool idle)
> >  {
> > -	assign_cpu(cpu, idle_masks.cpu, idle);
> > +	int node = idle_cpu_to_node(cpu);

Ok to all of the above.

> 
> minor: I wonder whether idle_cpu_to_node() name is a bit confusing - why
> does a CPU being idle have anything to do with its node mapping? If there is
> a better naming convention, great. If not, it is what it is.

Maybe scx_cpu_to_node()? At the end it's just a wrapper to cpu_to_node(),
but from the scx perspective, so if NUMA-awareness is not enabled in scx,
it'd return NUMA_NO_NODE.

Thanks,
-Andrea

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Yury Norov]

On Fri, Feb 07, 2025 at 09:40:52PM +0100, Andrea Righi wrote:
> Using a single global idle mask can lead to inefficiencies and a lot of
> stress on the cache coherency protocol on large systems with multiple
> NUMA nodes, since all the CPUs can create a really intense read/write
> activity on the single global cpumask.

Can you put your perf numbers here too?
 
> Therefore, split the global cpumask into multiple per-NUMA node cpumasks
> to improve scalability and performance on large systems.
> 
> The concept is that each cpumask will track only the idle CPUs within
> its corresponding NUMA node, treating CPUs in other NUMA nodes as busy.
> In this way concurrent access to the idle cpumask will be restricted
> within each NUMA node.
> 
> The split of multiple per-node idle cpumasks can be controlled using the
> SCX_OPS_BUILTIN_IDLE_PER_NODE flag.
> 
> By default SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled and a global
> host-wide idle cpumask is used, maintaining the previous behavior.
> 
> NOTE: if a scheduler explicitly enables the per-node idle cpumasks (via
> SCX_OPS_BUILTIN_IDLE_PER_NODE), scx_bpf_get_idle_cpu/smtmask() will
> trigger an scx error, since there are no system-wide cpumasks.
> 
> Signed-off-by: Andrea Righi <arighi@nvidia.com>
> ---
>  kernel/sched/ext_idle.c | 242 ++++++++++++++++++++++++++++++++--------
>  kernel/sched/ext_idle.h |  11 +-
>  2 files changed, 203 insertions(+), 50 deletions(-)
> 
> diff --git a/kernel/sched/ext_idle.c b/kernel/sched/ext_idle.c
> index a3f2b00903ac2..4b90ec9018c1a 100644
> --- a/kernel/sched/ext_idle.c
> +++ b/kernel/sched/ext_idle.c
> @@ -18,25 +18,88 @@ DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_enabled);
>  DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_per_node);
>  
>  #ifdef CONFIG_SMP
> -#ifdef CONFIG_CPUMASK_OFFSTACK
> -#define CL_ALIGNED_IF_ONSTACK
> -#else
> -#define CL_ALIGNED_IF_ONSTACK __cacheline_aligned_in_smp
> -#endif
> -
>  /* Enable/disable LLC aware optimizations */
>  DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_llc);
>  
>  /* Enable/disable NUMA aware optimizations */
>  DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_numa);
>  
> -static struct {
> +/*
> + * cpumasks to track idle CPUs within each NUMA node.
> + *
> + * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask
> + * from is used to track all the idle CPUs in the system.
> + */
> +struct idle_cpus {
>  	cpumask_var_t cpu;
>  	cpumask_var_t smt;
> -} idle_masks CL_ALIGNED_IF_ONSTACK;
> +};
> +
> +/*
> + * Global host-wide idle cpumasks (used when SCX_OPS_BUILTIN_IDLE_PER_NODE
> + * is not enabled).
> + */
> +static struct idle_cpus scx_idle_global_masks;
> +
> +/*
> + * Per-node idle cpumasks.
> + */
> +static struct idle_cpus **scx_idle_node_masks;
> +
> +/*
> + * Initialize per-node idle cpumasks.
> + *
> + * In case of a single NUMA node or if NUMA support is disabled, only a
> + * single global host-wide cpumask will be initialized.
> + */
> +void scx_idle_init_masks(void)
> +{
> +	int node;
> +
> +	/* Allocate global idle cpumasks */
> +	BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.cpu, GFP_KERNEL));
> +	BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.smt, GFP_KERNEL));
> +
> +	/* Allocate per-node idle cpumasks */
> +	scx_idle_node_masks = kcalloc(num_possible_nodes(),
> +				      sizeof(*scx_idle_node_masks), GFP_KERNEL);
> +	BUG_ON(!scx_idle_node_masks);
> +
> +	for_each_node(node) {
> +		scx_idle_node_masks[node] = kzalloc_node(sizeof(**scx_idle_node_masks),
> +							 GFP_KERNEL, node);
> +		BUG_ON(!scx_idle_node_masks[node]);
> +
> +		BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->cpu, GFP_KERNEL, node));
> +		BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->smt, GFP_KERNEL, node));
> +	}
> +}
> +
> +/*
> + * Return the idle masks associated to a target @node.
> + */
> +static struct idle_cpus *idle_cpumask(int node)
> +{
> +	return node == NUMA_NO_NODE ? &scx_idle_global_masks : scx_idle_node_masks[node];
> +}
> +
> +/*
> + * Return the node id associated to a target idle CPU (used to determine
> + * the proper idle cpumask).
> + */
> +static int idle_cpu_to_node(int cpu)
> +{
> +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
> +		return NUMA_NO_NODE;
> +
> +	return cpu_to_node(cpu);
> +}
>  
>  bool scx_idle_test_and_clear_cpu(int cpu)
>  {
> +	int node = idle_cpu_to_node(cpu);
> +	struct cpumask *idle_cpus = idle_cpumask(node)->cpu;
> +
>  #ifdef CONFIG_SCHED_SMT
>  	/*
>  	 * SMT mask should be cleared whether we can claim @cpu or not. The SMT
> @@ -45,33 +108,38 @@ bool scx_idle_test_and_clear_cpu(int cpu)
>  	 */
>  	if (sched_smt_active()) {
>  		const struct cpumask *smt = cpu_smt_mask(cpu);
> +		struct cpumask *idle_smts = idle_cpumask(node)->smt;
>  
>  		/*
>  		 * If offline, @cpu is not its own sibling and
>  		 * scx_pick_idle_cpu() can get caught in an infinite loop as
> -		 * @cpu is never cleared from idle_masks.smt. Ensure that @cpu
> -		 * is eventually cleared.
> +		 * @cpu is never cleared from the idle SMT mask. Ensure that
> +		 * @cpu is eventually cleared.
>  		 *
>  		 * NOTE: Use cpumask_intersects() and cpumask_test_cpu() to
>  		 * reduce memory writes, which may help alleviate cache
>  		 * coherence pressure.
>  		 */
> -		if (cpumask_intersects(smt, idle_masks.smt))
> -			cpumask_andnot(idle_masks.smt, idle_masks.smt, smt);
> -		else if (cpumask_test_cpu(cpu, idle_masks.smt))
> -			__cpumask_clear_cpu(cpu, idle_masks.smt);
> +		if (cpumask_intersects(smt, idle_smts))
> +			cpumask_andnot(idle_smts, idle_smts, smt);
> +		else if (cpumask_test_cpu(cpu, idle_smts))
> +			__cpumask_clear_cpu(cpu, idle_smts);
>  	}
>  #endif
> -	return cpumask_test_and_clear_cpu(cpu, idle_masks.cpu);
> +
> +	return cpumask_test_and_clear_cpu(cpu, idle_cpus);
>  }
>  
> -s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
> +/*
> + * Pick an idle CPU in a specific NUMA node.
> + */
> +s32 pick_idle_cpu_from_node(const struct cpumask *cpus_allowed, int node, u64 flags)
>  {
>  	int cpu;
>  
>  retry:
>  	if (sched_smt_active()) {
> -		cpu = cpumask_any_and_distribute(idle_masks.smt, cpus_allowed);
> +		cpu = cpumask_any_and_distribute(idle_cpumask(node)->smt, cpus_allowed);
>  		if (cpu < nr_cpu_ids)
>  			goto found;
>  
> @@ -79,7 +147,7 @@ s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
>  			return -EBUSY;
>  	}
>  
> -	cpu = cpumask_any_and_distribute(idle_masks.cpu, cpus_allowed);
> +	cpu = cpumask_any_and_distribute(idle_cpumask(node)->cpu, cpus_allowed);
>  	if (cpu >= nr_cpu_ids)
>  		return -EBUSY;
>  
> @@ -90,6 +158,55 @@ s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
>  		goto retry;
>  }
>  
> +/*
> + * Find the best idle CPU in the system, relative to @node.
> + */
> +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> +{
> +	nodemask_t unvisited = NODE_MASK_ALL;
> +	s32 cpu = -EBUSY;
> +
> +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
> +		return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);
> +
> +	/*
> +	 * If an initial node is not specified, start with the current
> +	 * node.
> +	 */
> +	if (node == NUMA_NO_NODE)
> +		node = numa_node_id();
> +
> +	/*
> +	 * Traverse all nodes in order of increasing distance, starting
> +	 * from @node.
> +	 *
> +	 * This loop is O(N^2), with N being the amount of NUMA nodes,
> +	 * which might be quite expensive in large NUMA systems. However,
> +	 * this complexity comes into play only when a scheduler enables
> +	 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU
> +	 * without specifying a target NUMA node, so it shouldn't be a
> +	 * bottleneck is most cases.
> +	 *
> +	 * As a future optimization we may want to cache the list of hop
> +	 * nodes in a per-node array, instead of actually traversing them
> +	 * every time.
> +	 */
> +	for_each_numa_node(node, unvisited, N_POSSIBLE) {
> +		cpu = pick_idle_cpu_from_node(cpus_allowed, node, flags);
> +		if (cpu >= 0)
> +			break;
> +
> +		/*
> +		 * Check if the search is restricted to the same core or
> +		 * the same node.
> +		 */
> +		if (flags & SCX_PICK_IDLE_IN_NODE)
> +			break;

If SCX_PICK_IDLE_IN_NODE is set, you can avoid the loop at all, right?
Just:
	if (flags & SCX_PICK_IDLE_IN_NODE)
	        return pick_idle_cpu_from_node(cpus_allowed, node, flags);

	for_each_numa_node(node, unvisited, N_POSSIBLE) {
		cpu = pick_idle_cpu_from_node(cpus_allowed, node, flags);
		if (cpu >= 0)
			return cpu;
        }

Thanks,
Yury

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Yury Norov]

On Sun, Feb 09, 2025 at 01:07:44PM -0500, Yury Norov wrote:
> On Fri, Feb 07, 2025 at 09:40:52PM +0100, Andrea Righi wrote:
> > Using a single global idle mask can lead to inefficiencies and a lot of
> > stress on the cache coherency protocol on large systems with multiple
> > NUMA nodes, since all the CPUs can create a really intense read/write
> > activity on the single global cpumask.
> 
> Can you put your perf numbers here too?
>  
> > Therefore, split the global cpumask into multiple per-NUMA node cpumasks
> > to improve scalability and performance on large systems.
> > 
> > The concept is that each cpumask will track only the idle CPUs within
> > its corresponding NUMA node, treating CPUs in other NUMA nodes as busy.
> > In this way concurrent access to the idle cpumask will be restricted
> > within each NUMA node.
> > 
> > The split of multiple per-node idle cpumasks can be controlled using the
> > SCX_OPS_BUILTIN_IDLE_PER_NODE flag.
> > 
> > By default SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled and a global
> > host-wide idle cpumask is used, maintaining the previous behavior.
> > 
> > NOTE: if a scheduler explicitly enables the per-node idle cpumasks (via
> > SCX_OPS_BUILTIN_IDLE_PER_NODE), scx_bpf_get_idle_cpu/smtmask() will
> > trigger an scx error, since there are no system-wide cpumasks.
> > 
> > Signed-off-by: Andrea Righi <arighi@nvidia.com>
> > ---
> >  kernel/sched/ext_idle.c | 242 ++++++++++++++++++++++++++++++++--------
> >  kernel/sched/ext_idle.h |  11 +-
> >  2 files changed, 203 insertions(+), 50 deletions(-)
> > 
> > diff --git a/kernel/sched/ext_idle.c b/kernel/sched/ext_idle.c
> > index a3f2b00903ac2..4b90ec9018c1a 100644
> > --- a/kernel/sched/ext_idle.c
> > +++ b/kernel/sched/ext_idle.c
> > @@ -18,25 +18,88 @@ DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_enabled);
> >  DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_per_node);
> >  
> >  #ifdef CONFIG_SMP
> > -#ifdef CONFIG_CPUMASK_OFFSTACK
> > -#define CL_ALIGNED_IF_ONSTACK
> > -#else
> > -#define CL_ALIGNED_IF_ONSTACK __cacheline_aligned_in_smp
> > -#endif
> > -
> >  /* Enable/disable LLC aware optimizations */
> >  DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_llc);
> >  
> >  /* Enable/disable NUMA aware optimizations */
> >  DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_numa);
> >  
> > -static struct {
> > +/*
> > + * cpumasks to track idle CPUs within each NUMA node.
> > + *
> > + * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask
> > + * from is used to track all the idle CPUs in the system.
> > + */
> > +struct idle_cpus {
> >  	cpumask_var_t cpu;
> >  	cpumask_var_t smt;
> > -} idle_masks CL_ALIGNED_IF_ONSTACK;
> > +};
> > +
> > +/*
> > + * Global host-wide idle cpumasks (used when SCX_OPS_BUILTIN_IDLE_PER_NODE
> > + * is not enabled).
> > + */
> > +static struct idle_cpus scx_idle_global_masks;
> > +
> > +/*
> > + * Per-node idle cpumasks.
> > + */
> > +static struct idle_cpus **scx_idle_node_masks;
> > +
> > +/*
> > + * Initialize per-node idle cpumasks.
> > + *
> > + * In case of a single NUMA node or if NUMA support is disabled, only a
> > + * single global host-wide cpumask will be initialized.
> > + */
> > +void scx_idle_init_masks(void)
> > +{
> > +	int node;
> > +
> > +	/* Allocate global idle cpumasks */
> > +	BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.cpu, GFP_KERNEL));
> > +	BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.smt, GFP_KERNEL));
> > +
> > +	/* Allocate per-node idle cpumasks */
> > +	scx_idle_node_masks = kcalloc(num_possible_nodes(),
> > +				      sizeof(*scx_idle_node_masks), GFP_KERNEL);
> > +	BUG_ON(!scx_idle_node_masks);
> > +
> > +	for_each_node(node) {
> > +		scx_idle_node_masks[node] = kzalloc_node(sizeof(**scx_idle_node_masks),
> > +							 GFP_KERNEL, node);
> > +		BUG_ON(!scx_idle_node_masks[node]);
> > +
> > +		BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->cpu, GFP_KERNEL, node));
> > +		BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->smt, GFP_KERNEL, node));
> > +	}
> > +}
> > +
> > +/*
> > + * Return the idle masks associated to a target @node.
> > + */
> > +static struct idle_cpus *idle_cpumask(int node)
> > +{
> > +	return node == NUMA_NO_NODE ? &scx_idle_global_masks : scx_idle_node_masks[node];
> > +}
> > +
> > +/*
> > + * Return the node id associated to a target idle CPU (used to determine
> > + * the proper idle cpumask).
> > + */
> > +static int idle_cpu_to_node(int cpu)
> > +{
> > +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
> > +		return NUMA_NO_NODE;
> > +
> > +	return cpu_to_node(cpu);
> > +}
> >  
> >  bool scx_idle_test_and_clear_cpu(int cpu)
> >  {
> > +	int node = idle_cpu_to_node(cpu);
> > +	struct cpumask *idle_cpus = idle_cpumask(node)->cpu;
> > +
> >  #ifdef CONFIG_SCHED_SMT
> >  	/*
> >  	 * SMT mask should be cleared whether we can claim @cpu or not. The SMT
> > @@ -45,33 +108,38 @@ bool scx_idle_test_and_clear_cpu(int cpu)
> >  	 */
> >  	if (sched_smt_active()) {
> >  		const struct cpumask *smt = cpu_smt_mask(cpu);
> > +		struct cpumask *idle_smts = idle_cpumask(node)->smt;
> >  
> >  		/*
> >  		 * If offline, @cpu is not its own sibling and
> >  		 * scx_pick_idle_cpu() can get caught in an infinite loop as
> > -		 * @cpu is never cleared from idle_masks.smt. Ensure that @cpu
> > -		 * is eventually cleared.
> > +		 * @cpu is never cleared from the idle SMT mask. Ensure that
> > +		 * @cpu is eventually cleared.
> >  		 *
> >  		 * NOTE: Use cpumask_intersects() and cpumask_test_cpu() to
> >  		 * reduce memory writes, which may help alleviate cache
> >  		 * coherence pressure.
> >  		 */
> > -		if (cpumask_intersects(smt, idle_masks.smt))
> > -			cpumask_andnot(idle_masks.smt, idle_masks.smt, smt);
> > -		else if (cpumask_test_cpu(cpu, idle_masks.smt))
> > -			__cpumask_clear_cpu(cpu, idle_masks.smt);
> > +		if (cpumask_intersects(smt, idle_smts))
> > +			cpumask_andnot(idle_smts, idle_smts, smt);
> > +		else if (cpumask_test_cpu(cpu, idle_smts))
> > +			__cpumask_clear_cpu(cpu, idle_smts);
> >  	}
> >  #endif
> > -	return cpumask_test_and_clear_cpu(cpu, idle_masks.cpu);
> > +
> > +	return cpumask_test_and_clear_cpu(cpu, idle_cpus);
> >  }
> >  
> > -s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
> > +/*
> > + * Pick an idle CPU in a specific NUMA node.
> > + */
> > +s32 pick_idle_cpu_from_node(const struct cpumask *cpus_allowed, int node, u64 flags)
> >  {
> >  	int cpu;
> >  
> >  retry:
> >  	if (sched_smt_active()) {
> > -		cpu = cpumask_any_and_distribute(idle_masks.smt, cpus_allowed);
> > +		cpu = cpumask_any_and_distribute(idle_cpumask(node)->smt, cpus_allowed);
> >  		if (cpu < nr_cpu_ids)
> >  			goto found;
> >  
> > @@ -79,7 +147,7 @@ s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
> >  			return -EBUSY;
> >  	}
> >  
> > -	cpu = cpumask_any_and_distribute(idle_masks.cpu, cpus_allowed);
> > +	cpu = cpumask_any_and_distribute(idle_cpumask(node)->cpu, cpus_allowed);
> >  	if (cpu >= nr_cpu_ids)
> >  		return -EBUSY;
> >  
> > @@ -90,6 +158,55 @@ s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, u64 flags)
> >  		goto retry;
> >  }
> >  
> > +/*
> > + * Find the best idle CPU in the system, relative to @node.
> > + */
> > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > +{
> > +	nodemask_t unvisited = NODE_MASK_ALL;

This should be a NODEMASK_ALLOC(). We don't want to eat up too much of the
stack, right?

> > +	s32 cpu = -EBUSY;
> > +
> > +	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))
> > +		return pick_idle_cpu_from_node(cpus_allowed, NUMA_NO_NODE, flags);
> > +
> > +	/*
> > +	 * If an initial node is not specified, start with the current
> > +	 * node.
> > +	 */
> > +	if (node == NUMA_NO_NODE)
> > +		node = numa_node_id();
> > +
> > +	/*
> > +	 * Traverse all nodes in order of increasing distance, starting
> > +	 * from @node.
> > +	 *
> > +	 * This loop is O(N^2), with N being the amount of NUMA nodes,
> > +	 * which might be quite expensive in large NUMA systems. However,
> > +	 * this complexity comes into play only when a scheduler enables
> > +	 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU
> > +	 * without specifying a target NUMA node, so it shouldn't be a
> > +	 * bottleneck is most cases.
> > +	 *
> > +	 * As a future optimization we may want to cache the list of hop
> > +	 * nodes in a per-node array, instead of actually traversing them
> > +	 * every time.
> > +	 */
> > +	for_each_numa_node(node, unvisited, N_POSSIBLE) {
> > +		cpu = pick_idle_cpu_from_node(cpus_allowed, node, flags);
> > +		if (cpu >= 0)
> > +			break;
> > +
> > +		/*
> > +		 * Check if the search is restricted to the same core or
> > +		 * the same node.
> > +		 */
> > +		if (flags & SCX_PICK_IDLE_IN_NODE)
> > +			break;
> 
> If SCX_PICK_IDLE_IN_NODE is set, you can avoid the loop at all, right?
> Just:
> 	if (flags & SCX_PICK_IDLE_IN_NODE)
> 	        return pick_idle_cpu_from_node(cpus_allowed, node, flags);
> 
> 	for_each_numa_node(node, unvisited, N_POSSIBLE) {
> 		cpu = pick_idle_cpu_from_node(cpus_allowed, node, flags);
> 		if (cpu >= 0)
> 			return cpu;
>         }
> 
> Thanks,
> Yury

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

On Mon, Feb 10, 2025 at 11:57:42AM -0500, Yury Norov wrote:
...
> > > +/*
> > > + * Find the best idle CPU in the system, relative to @node.
> > > + */
> > > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > > +{
> > > +	nodemask_t unvisited = NODE_MASK_ALL;
> 
> This should be a NODEMASK_ALLOC(). We don't want to eat up too much of the
> stack, right?

Ok, and if I want to initialize unvisited to all online nodes, is there a
better than doing:

  nodemask_clear(*unvisited);
  nodemask_or(*unvisited, *unvisited, node_states[N_ONLINE]);

We don't have nodemask_copy() right?

Thanks,
-Andrea

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

On Tue, Feb 11, 2025 at 08:32:51AM +0100, Andrea Righi wrote:
> On Mon, Feb 10, 2025 at 11:57:42AM -0500, Yury Norov wrote:
> ...
> > > > +/*
> > > > + * Find the best idle CPU in the system, relative to @node.
> > > > + */
> > > > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > > > +{
> > > > +	nodemask_t unvisited = NODE_MASK_ALL;
> > 
> > This should be a NODEMASK_ALLOC(). We don't want to eat up too much of the
> > stack, right?
> 
> Ok, and if I want to initialize unvisited to all online nodes, is there a
> better than doing:
> 
>   nodemask_clear(*unvisited);
>   nodemask_or(*unvisited, *unvisited, node_states[N_ONLINE]);
> 
> We don't have nodemask_copy() right?

Sorry, and with that I mean nodes_clear() / nodes_or() / nodes_copy().

-Andrea

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

On Tue, Feb 11, 2025 at 08:41:45AM +0100, Andrea Righi wrote:
> On Tue, Feb 11, 2025 at 08:32:51AM +0100, Andrea Righi wrote:
> > On Mon, Feb 10, 2025 at 11:57:42AM -0500, Yury Norov wrote:
> > ...
> > > > > +/*
> > > > > + * Find the best idle CPU in the system, relative to @node.
> > > > > + */
> > > > > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > > > > +{
> > > > > +	nodemask_t unvisited = NODE_MASK_ALL;
> > > 
> > > This should be a NODEMASK_ALLOC(). We don't want to eat up too much of the
> > > stack, right?
> > 
> > Ok, and if I want to initialize unvisited to all online nodes, is there a
> > better than doing:
> > 
> >   nodemask_clear(*unvisited);
> >   nodemask_or(*unvisited, *unvisited, node_states[N_ONLINE]);
> > 
> > We don't have nodemask_copy() right?
> 
> Sorry, and with that I mean nodes_clear() / nodes_or() / nodes_copy().

Also, it might be problematic to use NODEMASK_ALLOC() here, since we're
potentially holding raw spinlocks. Maybe we could use per-cpu nodemask_t,
but then we need to preempt_disable() the entire loop, since
scx_pick_idle_cpu() can be be called potentially from any context.

Considering that the maximum value for NODE_SHIFT is 10 with CONFIG_MAXSMP,
nodemask_t should be 128 bytes at most, that doesn't seem too bad... Maybe
we can accept to have it on the stack in this case?

Thanks,
-Andrea

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Yury Norov]

On Tue, Feb 11, 2025 at 10:50:46AM +0100, Andrea Righi wrote:
> On Tue, Feb 11, 2025 at 08:41:45AM +0100, Andrea Righi wrote:
> > On Tue, Feb 11, 2025 at 08:32:51AM +0100, Andrea Righi wrote:
> > > On Mon, Feb 10, 2025 at 11:57:42AM -0500, Yury Norov wrote:
> > > ...
> > > > > > +/*
> > > > > > + * Find the best idle CPU in the system, relative to @node.
> > > > > > + */
> > > > > > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > > > > > +{
> > > > > > +	nodemask_t unvisited = NODE_MASK_ALL;
> > > > 
> > > > This should be a NODEMASK_ALLOC(). We don't want to eat up too much of the
> > > > stack, right?
> > > 
> > > Ok, and if I want to initialize unvisited to all online nodes, is there a
> > > better than doing:
> > > 
> > >   nodemask_clear(*unvisited);
> > >   nodemask_or(*unvisited, *unvisited, node_states[N_ONLINE]);
> > > 
> > > We don't have nodemask_copy() right?
> > 
> > Sorry, and with that I mean nodes_clear() / nodes_or() / nodes_copy().
> 
> Also, it might be problematic to use NODEMASK_ALLOC() here, since we're
> potentially holding raw spinlocks. Maybe we could use per-cpu nodemask_t,
> but then we need to preempt_disable() the entire loop, since
> scx_pick_idle_cpu() can be be called potentially from any context.
> 
> Considering that the maximum value for NODE_SHIFT is 10 with CONFIG_MAXSMP,
> nodemask_t should be 128 bytes at most, that doesn't seem too bad... Maybe
> we can accept to have it on the stack in this case?

If you expect calling this in strict SMP lock-held or IRQ contexts, You
need to be careful about stack overflow even mode. We've got GFP_ATOMIC
for that:
     non sleeping allocation with an expensive fallback so it can access
     some portion of memory reserves. Usually used from interrupt/bottom-half
     context with an expensive slow path fallback.

Check Documentation/core-api/memory-allocation.rst for other options.
You may be interested in __GFP_NORETRY as well.

Thanks,
Yury

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

On Tue, Feb 11, 2025 at 09:19:52AM -0500, Yury Norov wrote:
> On Tue, Feb 11, 2025 at 10:50:46AM +0100, Andrea Righi wrote:
> > On Tue, Feb 11, 2025 at 08:41:45AM +0100, Andrea Righi wrote:
> > > On Tue, Feb 11, 2025 at 08:32:51AM +0100, Andrea Righi wrote:
> > > > On Mon, Feb 10, 2025 at 11:57:42AM -0500, Yury Norov wrote:
> > > > ...
> > > > > > > +/*
> > > > > > > + * Find the best idle CPU in the system, relative to @node.
> > > > > > > + */
> > > > > > > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > > > > > > +{
> > > > > > > +	nodemask_t unvisited = NODE_MASK_ALL;
> > > > > 
> > > > > This should be a NODEMASK_ALLOC(). We don't want to eat up too much of the
> > > > > stack, right?
> > > > 
> > > > Ok, and if I want to initialize unvisited to all online nodes, is there a
> > > > better than doing:
> > > > 
> > > >   nodemask_clear(*unvisited);
> > > >   nodemask_or(*unvisited, *unvisited, node_states[N_ONLINE]);
> > > > 
> > > > We don't have nodemask_copy() right?
> > > 
> > > Sorry, and with that I mean nodes_clear() / nodes_or() / nodes_copy().
> > 
> > Also, it might be problematic to use NODEMASK_ALLOC() here, since we're
> > potentially holding raw spinlocks. Maybe we could use per-cpu nodemask_t,
> > but then we need to preempt_disable() the entire loop, since
> > scx_pick_idle_cpu() can be be called potentially from any context.
> > 
> > Considering that the maximum value for NODE_SHIFT is 10 with CONFIG_MAXSMP,
> > nodemask_t should be 128 bytes at most, that doesn't seem too bad... Maybe
> > we can accept to have it on the stack in this case?
> 
> If you expect calling this in strict SMP lock-held or IRQ contexts, You
> need to be careful about stack overflow even mode. We've got GFP_ATOMIC
> for that:
>      non sleeping allocation with an expensive fallback so it can access
>      some portion of memory reserves. Usually used from interrupt/bottom-half
>      context with an expensive slow path fallback.
> 
> Check Documentation/core-api/memory-allocation.rst for other options.
> You may be interested in __GFP_NORETRY as well.

I know about GFP_ATOMIC, but even with that I'm hitting some bugs.
Will try with __GFP_NORETRY.

Thanks,
-Andrea

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

On Tue, Feb 11, 2025 at 03:34:11PM +0100, Andrea Righi wrote:
> On Tue, Feb 11, 2025 at 09:19:52AM -0500, Yury Norov wrote:
> > On Tue, Feb 11, 2025 at 10:50:46AM +0100, Andrea Righi wrote:
> > > On Tue, Feb 11, 2025 at 08:41:45AM +0100, Andrea Righi wrote:
> > > > On Tue, Feb 11, 2025 at 08:32:51AM +0100, Andrea Righi wrote:
> > > > > On Mon, Feb 10, 2025 at 11:57:42AM -0500, Yury Norov wrote:
> > > > > ...
> > > > > > > > +/*
> > > > > > > > + * Find the best idle CPU in the system, relative to @node.
> > > > > > > > + */
> > > > > > > > +s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags)
> > > > > > > > +{
> > > > > > > > +	nodemask_t unvisited = NODE_MASK_ALL;
> > > > > > 
> > > > > > This should be a NODEMASK_ALLOC(). We don't want to eat up too much of the
> > > > > > stack, right?
> > > > > 
> > > > > Ok, and if I want to initialize unvisited to all online nodes, is there a
> > > > > better than doing:
> > > > > 
> > > > >   nodemask_clear(*unvisited);
> > > > >   nodemask_or(*unvisited, *unvisited, node_states[N_ONLINE]);
> > > > > 
> > > > > We don't have nodemask_copy() right?
> > > > 
> > > > Sorry, and with that I mean nodes_clear() / nodes_or() / nodes_copy().
> > > 
> > > Also, it might be problematic to use NODEMASK_ALLOC() here, since we're
> > > potentially holding raw spinlocks. Maybe we could use per-cpu nodemask_t,
> > > but then we need to preempt_disable() the entire loop, since
> > > scx_pick_idle_cpu() can be be called potentially from any context.
> > > 
> > > Considering that the maximum value for NODE_SHIFT is 10 with CONFIG_MAXSMP,
> > > nodemask_t should be 128 bytes at most, that doesn't seem too bad... Maybe
> > > we can accept to have it on the stack in this case?
> > 
> > If you expect calling this in strict SMP lock-held or IRQ contexts, You
> > need to be careful about stack overflow even mode. We've got GFP_ATOMIC
> > for that:
> >      non sleeping allocation with an expensive fallback so it can access
> >      some portion of memory reserves. Usually used from interrupt/bottom-half
> >      context with an expensive slow path fallback.
> > 
> > Check Documentation/core-api/memory-allocation.rst for other options.
> > You may be interested in __GFP_NORETRY as well.
> 
> I know about GFP_ATOMIC, but even with that I'm hitting some bugs.
> Will try with __GFP_NORETRY.

...which is basically this (with GFP_ATOMIC):

[   11.829079] =============================
[   11.829109] [ BUG: Invalid wait context ]
[   11.829146] 6.13.0-virtme #51 Not tainted
[   11.829185] -----------------------------
[   11.829243] fish/344 is trying to lock:
[   11.829285] ffff9659bec450b0 (&c->lock){..-.}-{3:3}, at: ___slab_alloc+0x66/0x1510
[   11.829380] other info that might help us debug this:
[   11.829450] context-{5:5}
[   11.829494] 8 locks held by fish/344:
[   11.829534]  #0: ffff965a409c70a0 (&tty->ldisc_sem){++++}-{0:0}, at: tty_ldisc_ref_wait+0x28/0x60
[   11.829643]  #1: ffff965a409c7130 (&tty->atomic_write_lock){+.+.}-{4:4}, at: file_tty_write.isra.0+0xa1/0x330
[   11.829765]  #2: ffff965a409c72e8 (&tty->termios_rwsem/1){++++}-{4:4}, at: n_tty_write+0x9e/0x510
[   11.829871]  #3: ffffbc6d01433380 (&ldata->output_lock){+.+.}-{4:4}, at: n_tty_write+0x1f1/0x510
[   11.829979]  #4: ffffffffb556b5c0 (rcu_read_lock){....}-{1:3}, at: __queue_work+0x59/0x680
[   11.830173]  #5: ffff9659800f0018 (&pool->lock){-.-.}-{2:2}, at: __queue_work+0xd7/0x680
[   11.830286]  #6: ffff9659801bcf60 (&p->pi_lock){-.-.}-{2:2}, at: try_to_wake_up+0x56/0x920
[   11.830396]  #7: ffffffffb556b5c0 (rcu_read_lock){....}-{1:3}, at: scx_select_cpu_dfl+0x56/0x460

And I think that's because:

 * %GFP_ATOMIC users can not sleep and need the allocation to succeed. A lower
 * watermark is applied to allow access to "atomic reserves".
 * The current implementation doesn't support NMI and few other strict
 * non-preemptive contexts (e.g. raw_spin_lock). The same applies to %GFP_NOWAIT.

So I guess we the only viable option is to preallocate nodemask_t and
protect it somehow, hoping that it doesn't add too much overhead...

-Andrea

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Steven Rostedt]

On Tue, 11 Feb 2025 15:45:15 +0100
Andrea Righi <arighi@nvidia.com> wrote:

> ...which is basically this (with GFP_ATOMIC):
> 
> [   11.829079] =============================
> [   11.829109] [ BUG: Invalid wait context ]
> [   11.829146] 6.13.0-virtme #51 Not tainted
> [   11.829185] -----------------------------
> [   11.829243] fish/344 is trying to lock:
> [   11.829285] ffff9659bec450b0 (&c->lock){..-.}-{3:3}, at: ___slab_alloc+0x66/0x1510
> [   11.829380] other info that might help us debug this:
> [   11.829450] context-{5:5}
> [   11.829494] 8 locks held by fish/344:
> [   11.829534]  #0: ffff965a409c70a0 (&tty->ldisc_sem){++++}-{0:0}, at: tty_ldisc_ref_wait+0x28/0x60
> [   11.829643]  #1: ffff965a409c7130 (&tty->atomic_write_lock){+.+.}-{4:4}, at: file_tty_write.isra.0+0xa1/0x330
> [   11.829765]  #2: ffff965a409c72e8 (&tty->termios_rwsem/1){++++}-{4:4}, at: n_tty_write+0x9e/0x510
> [   11.829871]  #3: ffffbc6d01433380 (&ldata->output_lock){+.+.}-{4:4}, at: n_tty_write+0x1f1/0x510
> [   11.829979]  #4: ffffffffb556b5c0 (rcu_read_lock){....}-{1:3}, at: __queue_work+0x59/0x680
> [   11.830173]  #5: ffff9659800f0018 (&pool->lock){-.-.}-{2:2}, at: __queue_work+0xd7/0x680
> [   11.830286]  #6: ffff9659801bcf60 (&p->pi_lock){-.-.}-{2:2}, at: try_to_wake_up+0x56/0x920
> [   11.830396]  #7: ffffffffb556b5c0 (rcu_read_lock){....}-{1:3}, at: scx_select_cpu_dfl+0x56/0x460
> 
> And I think that's because:
> 
>  * %GFP_ATOMIC users can not sleep and need the allocation to succeed. A lower
>  * watermark is applied to allow access to "atomic reserves".
>  * The current implementation doesn't support NMI and few other strict
>  * non-preemptive contexts (e.g. raw_spin_lock). The same applies to %GFP_NOWAIT.
> 
> So I guess we the only viable option is to preallocate nodemask_t and
> protect it somehow, hoping that it doesn't add too much overhead...

I believe it's because you have p->pi_lock which is a raw_spin_lock() and
you are trying to take a lock in ___slab_alloc() which I bet is a normal
spin_lock(). In PREEMPT_RT() that turns into a mutex, and you can not take
a spin_lock while holding a raw_spin_lock.

-- Steve

Re: [PATCH 5/6] sched_ext: idle: Per-node idle cpumasks

[Andrea Righi]

On Tue, Feb 11, 2025 at 11:38:27AM -0500, Steven Rostedt wrote:
> On Tue, 11 Feb 2025 15:45:15 +0100
> Andrea Righi <arighi@nvidia.com> wrote:
> 
> > ...which is basically this (with GFP_ATOMIC):
> > 
> > [   11.829079] =============================
> > [   11.829109] [ BUG: Invalid wait context ]
> > [   11.829146] 6.13.0-virtme #51 Not tainted
> > [   11.829185] -----------------------------
> > [   11.829243] fish/344 is trying to lock:
> > [   11.829285] ffff9659bec450b0 (&c->lock){..-.}-{3:3}, at: ___slab_alloc+0x66/0x1510
> > [   11.829380] other info that might help us debug this:
> > [   11.829450] context-{5:5}
> > [   11.829494] 8 locks held by fish/344:
> > [   11.829534]  #0: ffff965a409c70a0 (&tty->ldisc_sem){++++}-{0:0}, at: tty_ldisc_ref_wait+0x28/0x60
> > [   11.829643]  #1: ffff965a409c7130 (&tty->atomic_write_lock){+.+.}-{4:4}, at: file_tty_write.isra.0+0xa1/0x330
> > [   11.829765]  #2: ffff965a409c72e8 (&tty->termios_rwsem/1){++++}-{4:4}, at: n_tty_write+0x9e/0x510
> > [   11.829871]  #3: ffffbc6d01433380 (&ldata->output_lock){+.+.}-{4:4}, at: n_tty_write+0x1f1/0x510
> > [   11.829979]  #4: ffffffffb556b5c0 (rcu_read_lock){....}-{1:3}, at: __queue_work+0x59/0x680
> > [   11.830173]  #5: ffff9659800f0018 (&pool->lock){-.-.}-{2:2}, at: __queue_work+0xd7/0x680
> > [   11.830286]  #6: ffff9659801bcf60 (&p->pi_lock){-.-.}-{2:2}, at: try_to_wake_up+0x56/0x920
> > [   11.830396]  #7: ffffffffb556b5c0 (rcu_read_lock){....}-{1:3}, at: scx_select_cpu_dfl+0x56/0x460
> > 
> > And I think that's because:
> > 
> >  * %GFP_ATOMIC users can not sleep and need the allocation to succeed. A lower
> >  * watermark is applied to allow access to "atomic reserves".
> >  * The current implementation doesn't support NMI and few other strict
> >  * non-preemptive contexts (e.g. raw_spin_lock). The same applies to %GFP_NOWAIT.
> > 
> > So I guess we the only viable option is to preallocate nodemask_t and
> > protect it somehow, hoping that it doesn't add too much overhead...
> 
> I believe it's because you have p->pi_lock which is a raw_spin_lock() and
> you are trying to take a lock in ___slab_alloc() which I bet is a normal
> spin_lock(). In PREEMPT_RT() that turns into a mutex, and you can not take
> a spin_lock while holding a raw_spin_lock.

Exactly that, thanks Steve. I'll run some tests using per-cpu nodemask_t,
given that most of the times this is called with p->pi_lock held, it should
be safe and we shouldn't introduce any overhead.

-Andrea

[PATCH 6/6] sched_ext: idle: Introduce node-aware idle cpu kfunc helpers

[Andrea Righi]

Add the following kfunc's to provide scx schedulers direct access to
per-node idle cpumasks information:

 int scx_bpf_cpu_to_node(s32 cpu)
 const struct cpumask *scx_bpf_get_idle_cpumask_node(int node)
 const struct cpumask *scx_bpf_get_idle_smtmask_node(int node)
 s32 scx_bpf_pick_idle_cpu_node(const cpumask_t *cpus_allowed,
				int node, u64 flags)

Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 kernel/sched/ext_idle.c                  | 121 +++++++++++++++++++++++
 tools/sched_ext/include/scx/common.bpf.h |   4 +
 tools/sched_ext/include/scx/compat.bpf.h |  19 ++++
 3 files changed, 144 insertions(+)

diff --git a/kernel/sched/ext_idle.c b/kernel/sched/ext_idle.c
index 4b90ec9018c1a..260a26c6cb0b8 100644
--- a/kernel/sched/ext_idle.c
+++ b/kernel/sched/ext_idle.c
@@ -686,6 +686,33 @@ void __scx_update_idle(struct rq *rq, bool idle, bool do_notify)
 /********************************************************************************
  * Helpers that can be called from the BPF scheduler.
  */
+
+static int validate_node(int node)
+{
+	if (!static_branch_likely(&scx_builtin_idle_per_node)) {
+		scx_ops_error("per-node idle tracking is disabled");
+		return -EOPNOTSUPP;
+	}
+
+	/* Return no entry for NUMA_NO_NODE (not a critical scx error) */
+	if (node == NUMA_NO_NODE)
+		return -ENOENT;
+
+	/* Make sure node is in a valid range */
+	if (node < 0 || node >= nr_node_ids) {
+		scx_ops_error("invalid node %d", node);
+		return -EINVAL;
+	}
+
+	/* Make sure the node is part of the set of possible nodes */
+	if (!node_possible(node)) {
+		scx_ops_error("unavailable node %d", node);
+		return -EINVAL;
+	}
+
+	return node;
+}
+
 __bpf_kfunc_start_defs();
 
 static bool check_builtin_idle_enabled(void)
@@ -697,6 +724,21 @@ static bool check_builtin_idle_enabled(void)
 	return false;
 }
 
+/**
+ * scx_bpf_cpu_to_node - Return the NUMA node the given @cpu belongs to
+ */
+__bpf_kfunc int scx_bpf_cpu_to_node(s32 cpu)
+{
+#ifdef CONFIG_NUMA
+	if (cpu < 0 || cpu >= nr_cpu_ids)
+		return -EINVAL;
+
+	return idle_cpu_to_node(cpu);
+#else
+	return 0;
+#endif
+}
+
 /**
  * scx_bpf_select_cpu_dfl - The default implementation of ops.select_cpu()
  * @p: task_struct to select a CPU for
@@ -729,6 +771,27 @@ __bpf_kfunc s32 scx_bpf_select_cpu_dfl(struct task_struct *p, s32 prev_cpu,
 	return prev_cpu;
 }
 
+/**
+ * scx_bpf_get_idle_cpumask_node - Get a referenced kptr to the
+ * idle-tracking per-CPU cpumask of a target NUMA node.
+ *
+ * Returns an empty cpumask if idle tracking is not enabled, if @node is
+ * not valid, or running on a UP kernel. In this case the actual error will
+ * be reported to the BPF scheduler via scx_ops_error().
+ */
+__bpf_kfunc const struct cpumask *scx_bpf_get_idle_cpumask_node(int node)
+{
+	node = validate_node(node);
+	if (node < 0)
+		return cpu_none_mask;
+
+#ifdef CONFIG_SMP
+	return idle_cpumask(node)->cpu;
+#else
+	return cpu_none_mask;
+#endif
+}
+
 /**
  * scx_bpf_get_idle_cpumask - Get a referenced kptr to the idle-tracking
  * per-CPU cpumask.
@@ -753,6 +816,31 @@ __bpf_kfunc const struct cpumask *scx_bpf_get_idle_cpumask(void)
 #endif
 }
 
+/**
+ * scx_bpf_get_idle_smtmask_node - Get a referenced kptr to the
+ * idle-tracking, per-physical-core cpumask of a target NUMA node. Can be
+ * used to determine if an entire physical core is free.
+ *
+ * Returns an empty cpumask if idle tracking is not enabled, if @node is
+ * not valid, or running on a UP kernel. In this case the actual error will
+ * be reported to the BPF scheduler via scx_ops_error().
+ */
+__bpf_kfunc const struct cpumask *scx_bpf_get_idle_smtmask_node(int node)
+{
+	node = validate_node(node);
+	if (node < 0)
+		return cpu_none_mask;
+
+#ifdef CONFIG_SMP
+	if (sched_smt_active())
+		return idle_cpumask(node)->smt;
+	else
+		return idle_cpumask(node)->cpu;
+#else
+	return cpu_none_mask;
+#endif
+}
+
 /**
  * scx_bpf_get_idle_smtmask - Get a referenced kptr to the idle-tracking,
  * per-physical-core cpumask. Can be used to determine if an entire physical
@@ -817,6 +905,35 @@ __bpf_kfunc bool scx_bpf_test_and_clear_cpu_idle(s32 cpu)
 		return false;
 }
 
+/**
+ * scx_bpf_pick_idle_cpu_node - Pick and claim an idle cpu from a NUMA node
+ * @cpus_allowed: Allowed cpumask
+ * @node: target NUMA node
+ * @flags: %SCX_PICK_IDLE_* flags
+ *
+ * Pick and claim an idle cpu in @cpus_allowed from the NUMA node @node.
+ *
+ * Returns the picked idle cpu number on success, or -%EBUSY if no matching
+ * cpu was found.
+ *
+ * The search starts from @node and proceeds to other online NUMA nodes in
+ * order of increasing distance (unless SCX_PICK_IDLE_IN_NODE is specified,
+ * in which case the search is limited to the target @node).
+ *
+ * Always returns an error if ops.update_idle() is implemented and
+ * %SCX_OPS_KEEP_BUILTIN_IDLE is not set, or if
+ * %SCX_OPS_BUILTIN_IDLE_PER_NODE is not set.
+ */
+__bpf_kfunc s32 scx_bpf_pick_idle_cpu_node(const struct cpumask *cpus_allowed,
+					   int node, u64 flags)
+{
+	node = validate_node(node);
+	if (node < 0)
+		return node;
+
+	return scx_pick_idle_cpu(cpus_allowed, node, flags);
+}
+
 /**
  * scx_bpf_pick_idle_cpu - Pick and claim an idle cpu
  * @cpus_allowed: Allowed cpumask
@@ -880,10 +997,14 @@ __bpf_kfunc s32 scx_bpf_pick_any_cpu(const struct cpumask *cpus_allowed,
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(scx_kfunc_ids_idle)
+BTF_ID_FLAGS(func, scx_bpf_cpu_to_node)
+BTF_ID_FLAGS(func, scx_bpf_get_idle_cpumask_node, KF_ACQUIRE)
 BTF_ID_FLAGS(func, scx_bpf_get_idle_cpumask, KF_ACQUIRE)
+BTF_ID_FLAGS(func, scx_bpf_get_idle_smtmask_node, KF_ACQUIRE)
 BTF_ID_FLAGS(func, scx_bpf_get_idle_smtmask, KF_ACQUIRE)
 BTF_ID_FLAGS(func, scx_bpf_put_idle_cpumask, KF_RELEASE)
 BTF_ID_FLAGS(func, scx_bpf_test_and_clear_cpu_idle)
+BTF_ID_FLAGS(func, scx_bpf_pick_idle_cpu_node, KF_RCU)
 BTF_ID_FLAGS(func, scx_bpf_pick_idle_cpu, KF_RCU)
 BTF_ID_FLAGS(func, scx_bpf_pick_any_cpu, KF_RCU)
 BTF_KFUNCS_END(scx_kfunc_ids_idle)
diff --git a/tools/sched_ext/include/scx/common.bpf.h b/tools/sched_ext/include/scx/common.bpf.h
index 7055400030241..7dd8ba2964553 100644
--- a/tools/sched_ext/include/scx/common.bpf.h
+++ b/tools/sched_ext/include/scx/common.bpf.h
@@ -63,13 +63,17 @@ u32 scx_bpf_cpuperf_cap(s32 cpu) __ksym __weak;
 u32 scx_bpf_cpuperf_cur(s32 cpu) __ksym __weak;
 void scx_bpf_cpuperf_set(s32 cpu, u32 perf) __ksym __weak;
 u32 scx_bpf_nr_cpu_ids(void) __ksym __weak;
+int scx_bpf_cpu_to_node(s32 cpu) __ksym __weak;
 const struct cpumask *scx_bpf_get_possible_cpumask(void) __ksym __weak;
 const struct cpumask *scx_bpf_get_online_cpumask(void) __ksym __weak;
 void scx_bpf_put_cpumask(const struct cpumask *cpumask) __ksym __weak;
+const struct cpumask *scx_bpf_get_idle_cpumask_node(int node) __ksym __weak;
 const struct cpumask *scx_bpf_get_idle_cpumask(void) __ksym;
+const struct cpumask *scx_bpf_get_idle_smtmask_node(int node) __ksym __weak;
 const struct cpumask *scx_bpf_get_idle_smtmask(void) __ksym;
 void scx_bpf_put_idle_cpumask(const struct cpumask *cpumask) __ksym;
 bool scx_bpf_test_and_clear_cpu_idle(s32 cpu) __ksym;
+s32 scx_bpf_pick_idle_cpu_node(const cpumask_t *cpus_allowed, int node, u64 flags) __ksym __weak;
 s32 scx_bpf_pick_idle_cpu(const cpumask_t *cpus_allowed, u64 flags) __ksym;
 s32 scx_bpf_pick_any_cpu(const cpumask_t *cpus_allowed, u64 flags) __ksym;
 bool scx_bpf_task_running(const struct task_struct *p) __ksym;
diff --git a/tools/sched_ext/include/scx/compat.bpf.h b/tools/sched_ext/include/scx/compat.bpf.h
index 50e1499ae0935..caa1a80f9a60c 100644
--- a/tools/sched_ext/include/scx/compat.bpf.h
+++ b/tools/sched_ext/include/scx/compat.bpf.h
@@ -130,6 +130,25 @@ bool scx_bpf_dispatch_vtime_from_dsq___compat(struct bpf_iter_scx_dsq *it__iter,
 	 scx_bpf_now() :							\
 	 bpf_ktime_get_ns())
 
+#define __COMPAT_scx_bpf_cpu_to_node(cpu)					\
+	(bpf_ksym_exists(scx_bpf_cpu_to_node) ?					\
+	 scx_bpf_cpu_to_node(cpu) : 0)
+
+#define __COMPAT_scx_bpf_get_idle_cpumask_node(node)				\
+	(bpf_ksym_exists(scx_bpf_get_idle_cpumask_node) ?			\
+	 scx_bpf_get_idle_cpumask_node(node) :					\
+	 scx_bpf_get_idle_cpumask())						\
+
+#define __COMPAT_scx_bpf_get_idle_smtmask_node(node)				\
+	(bpf_ksym_exists(scx_bpf_get_idle_smtmask_node) ?			\
+	 scx_bpf_get_idle_smtmask_node(node) :					\
+	 scx_bpf_get_idle_smtmask())
+
+#define __COMPAT_scx_bpf_pick_idle_cpu_node(cpus_allowed, node, flags)		\
+	(bpf_ksym_exists(scx_bpf_pick_idle_cpu_node) ?				\
+	 scx_bpf_pick_idle_cpu_node(cpus_allowed, node, flags) :		\
+	 scx_bpf_pick_idle_cpu(cpus_allowed, flags))
+
 /*
  * Define sched_ext_ops. This may be expanded to define multiple variants for
  * backward compatibility. See compat.h::SCX_OPS_LOAD/ATTACH().
-- 
2.48.1

Re: [PATCH 6/6] sched_ext: idle: Introduce node-aware idle cpu kfunc helpers

[Tejun Heo]

Hello,

On Fri, Feb 07, 2025 at 09:40:53PM +0100, Andrea Righi wrote:
> +/**
> + * scx_bpf_cpu_to_node - Return the NUMA node the given @cpu belongs to
> + */
> +__bpf_kfunc int scx_bpf_cpu_to_node(s32 cpu)

Maybe scx_bpf_cpu_node() to be in line with scx_bpf_task_cpu/cgroup()?

> +{
> +#ifdef CONFIG_NUMA
> +	if (cpu < 0 || cpu >= nr_cpu_ids)
> +		return -EINVAL;

Use ops_cpu_valid()? Otherwise, we can end up calling cpu_to_node() with an
impossible CPU. Also, I don't think CPU -> node mapping function should be
able to return an error value. It should just trigger ops error.

> +
> +	return idle_cpu_to_node(cpu);

This is contingent on scx_builtin_idle_per_node, right? It's confusing for
CPU -> node mapping function to return NUMA_NO_NODE depending on an ops
flag. Shouldn't this be a generic mapping function?

> index 50e1499ae0935..caa1a80f9a60c 100644
> --- a/tools/sched_ext/include/scx/compat.bpf.h
> +++ b/tools/sched_ext/include/scx/compat.bpf.h
> @@ -130,6 +130,25 @@ bool scx_bpf_dispatch_vtime_from_dsq___compat(struct bpf_iter_scx_dsq *it__iter,
>  	 scx_bpf_now() :							\
>  	 bpf_ktime_get_ns())
>  
> +#define __COMPAT_scx_bpf_cpu_to_node(cpu)					\
> +	(bpf_ksym_exists(scx_bpf_cpu_to_node) ?					\
> +	 scx_bpf_cpu_to_node(cpu) : 0)
> +
> +#define __COMPAT_scx_bpf_get_idle_cpumask_node(node)				\
> +	(bpf_ksym_exists(scx_bpf_get_idle_cpumask_node) ?			\
> +	 scx_bpf_get_idle_cpumask_node(node) :					\
> +	 scx_bpf_get_idle_cpumask())						\
> +
> +#define __COMPAT_scx_bpf_get_idle_smtmask_node(node)				\
> +	(bpf_ksym_exists(scx_bpf_get_idle_smtmask_node) ?			\
> +	 scx_bpf_get_idle_smtmask_node(node) :					\
> +	 scx_bpf_get_idle_smtmask())
> +
> +#define __COMPAT_scx_bpf_pick_idle_cpu_node(cpus_allowed, node, flags)		\
> +	(bpf_ksym_exists(scx_bpf_pick_idle_cpu_node) ?				\
> +	 scx_bpf_pick_idle_cpu_node(cpus_allowed, node, flags) :		\
> +	 scx_bpf_pick_idle_cpu(cpus_allowed, flags))

Can you please document when these compat macros can be dropped? Also,
shouldn't it also provide a compat macro for the new ops flag using
__COMPAT_ENUM_OR_ZERO()? Otherwise, trying to load new binary using the new
flag on an older kernel will fail, right?

Thanks.

-- 
tejun

Re: [PATCH 6/6] sched_ext: idle: Introduce node-aware idle cpu kfunc helpers

[Andrea Righi]

On Fri, Feb 07, 2025 at 12:39:57PM -1000, Tejun Heo wrote:
> Hello,
> 
> On Fri, Feb 07, 2025 at 09:40:53PM +0100, Andrea Righi wrote:
> > +/**
> > + * scx_bpf_cpu_to_node - Return the NUMA node the given @cpu belongs to
> > + */
> > +__bpf_kfunc int scx_bpf_cpu_to_node(s32 cpu)
> 
> Maybe scx_bpf_cpu_node() to be in line with scx_bpf_task_cpu/cgroup()?

Ok, then maybe we can have scx_bpf_cpu_node() for the kfunc, that wraps
scx_cpu_node() for internal use.

> 
> > +{
> > +#ifdef CONFIG_NUMA
> > +	if (cpu < 0 || cpu >= nr_cpu_ids)
> > +		return -EINVAL;
> 
> Use ops_cpu_valid()? Otherwise, we can end up calling cpu_to_node() with an
> impossible CPU. Also, I don't think CPU -> node mapping function should be
> able to return an error value. It should just trigger ops error.

Ok.

> 
> > +
> > +	return idle_cpu_to_node(cpu);
> 
> This is contingent on scx_builtin_idle_per_node, right? It's confusing for
> CPU -> node mapping function to return NUMA_NO_NODE depending on an ops
> flag. Shouldn't this be a generic mapping function?

The idea is that BPF schedulers can use this kfunc to determine the right
idle cpumask to use, for example a typical usage could be:

  int node = scx_bpf_cpu_node(prev_cpu);
  s32 cpu = scx_bpf_pick_idle_cpu_in_node(p->cpus_ptr, node, SCX_PICK_IDLE_IN_NODE);

Or:

  int node = scx_bpf_cpu_node(prev_cpu);
  const struct cpumask *idle_cpumask = scx_bpf_get_idle_cpumask_node(node);

When SCX_OPS_BUILTIN_IDLE_PER_NODE is disabled, we need to point to the
global idle cpumask, that is identified by NUMA_NO_NODE, so this is why we
can return NUMA_NO_NODE fro scx_bpf_cpu_node().

Do you think we should make this more clear / document this better. Or do
you think we should use a different API?

> 
> > index 50e1499ae0935..caa1a80f9a60c 100644
> > --- a/tools/sched_ext/include/scx/compat.bpf.h
> > +++ b/tools/sched_ext/include/scx/compat.bpf.h
> > @@ -130,6 +130,25 @@ bool scx_bpf_dispatch_vtime_from_dsq___compat(struct bpf_iter_scx_dsq *it__iter,
> >  	 scx_bpf_now() :							\
> >  	 bpf_ktime_get_ns())
> >  
> > +#define __COMPAT_scx_bpf_cpu_to_node(cpu)					\
> > +	(bpf_ksym_exists(scx_bpf_cpu_to_node) ?					\
> > +	 scx_bpf_cpu_to_node(cpu) : 0)
> > +
> > +#define __COMPAT_scx_bpf_get_idle_cpumask_node(node)				\
> > +	(bpf_ksym_exists(scx_bpf_get_idle_cpumask_node) ?			\
> > +	 scx_bpf_get_idle_cpumask_node(node) :					\
> > +	 scx_bpf_get_idle_cpumask())						\
> > +
> > +#define __COMPAT_scx_bpf_get_idle_smtmask_node(node)				\
> > +	(bpf_ksym_exists(scx_bpf_get_idle_smtmask_node) ?			\
> > +	 scx_bpf_get_idle_smtmask_node(node) :					\
> > +	 scx_bpf_get_idle_smtmask())
> > +
> > +#define __COMPAT_scx_bpf_pick_idle_cpu_node(cpus_allowed, node, flags)		\
> > +	(bpf_ksym_exists(scx_bpf_pick_idle_cpu_node) ?				\
> > +	 scx_bpf_pick_idle_cpu_node(cpus_allowed, node, flags) :		\
> > +	 scx_bpf_pick_idle_cpu(cpus_allowed, flags))
> 
> Can you please document when these compat macros can be dropped? Also,
> shouldn't it also provide a compat macro for the new ops flag using
> __COMPAT_ENUM_OR_ZERO()? Otherwise, trying to load new binary using the new
> flag on an older kernel will fail, right?

Right. Will add that.

Thanks,
-Andrea

Re: [PATCH 6/6] sched_ext: idle: Introduce node-aware idle cpu kfunc helpers

[Tejun Heo]

Hello,

On Sat, Feb 08, 2025 at 10:19:38AM +0100, Andrea Righi wrote:
...
> > This is contingent on scx_builtin_idle_per_node, right? It's confusing for
> > CPU -> node mapping function to return NUMA_NO_NODE depending on an ops
> > flag. Shouldn't this be a generic mapping function?
> 
> The idea is that BPF schedulers can use this kfunc to determine the right
> idle cpumask to use, for example a typical usage could be:
> 
>   int node = scx_bpf_cpu_node(prev_cpu);
>   s32 cpu = scx_bpf_pick_idle_cpu_in_node(p->cpus_ptr, node, SCX_PICK_IDLE_IN_NODE);
> 
> Or:
> 
>   int node = scx_bpf_cpu_node(prev_cpu);
>   const struct cpumask *idle_cpumask = scx_bpf_get_idle_cpumask_node(node);
> 
> When SCX_OPS_BUILTIN_IDLE_PER_NODE is disabled, we need to point to the
> global idle cpumask, that is identified by NUMA_NO_NODE, so this is why we
> can return NUMA_NO_NODE fro scx_bpf_cpu_node().
> 
> Do you think we should make this more clear / document this better. Or do
> you think we should use a different API?

I think this is too error-prone. It'd be really easy for users to assume
that scx_bpf_cpu_node() always returns the NUMA node for the given CPU which
can lead to really subtle surprises. Why even allow e.g.
scx_bpf_get_idle_cpumask_node() if IDLE_PER_NODE is not enabled?

Thanks.

-- 
tejun

Re: [PATCH 6/6] sched_ext: idle: Introduce node-aware idle cpu kfunc helpers

[Andrea Righi]

On Sat, Feb 08, 2025 at 08:31:27PM -1000, Tejun Heo wrote:
> Hello,
> 
> On Sat, Feb 08, 2025 at 10:19:38AM +0100, Andrea Righi wrote:
> ...
> > > This is contingent on scx_builtin_idle_per_node, right? It's confusing for
> > > CPU -> node mapping function to return NUMA_NO_NODE depending on an ops
> > > flag. Shouldn't this be a generic mapping function?
> > 
> > The idea is that BPF schedulers can use this kfunc to determine the right
> > idle cpumask to use, for example a typical usage could be:
> > 
> >   int node = scx_bpf_cpu_node(prev_cpu);
> >   s32 cpu = scx_bpf_pick_idle_cpu_in_node(p->cpus_ptr, node, SCX_PICK_IDLE_IN_NODE);
> > 
> > Or:
> > 
> >   int node = scx_bpf_cpu_node(prev_cpu);
> >   const struct cpumask *idle_cpumask = scx_bpf_get_idle_cpumask_node(node);
> > 
> > When SCX_OPS_BUILTIN_IDLE_PER_NODE is disabled, we need to point to the
> > global idle cpumask, that is identified by NUMA_NO_NODE, so this is why we
> > can return NUMA_NO_NODE fro scx_bpf_cpu_node().
> > 
> > Do you think we should make this more clear / document this better. Or do
> > you think we should use a different API?
> 
> I think this is too error-prone. It'd be really easy for users to assume
> that scx_bpf_cpu_node() always returns the NUMA node for the given CPU which
> can lead to really subtle surprises. Why even allow e.g.
> scx_bpf_get_idle_cpumask_node() if IDLE_PER_NODE is not enabled?

Ok, for the kfuncs I agree that we should just trigger an scx_ops_error()
if any of the scx_*_node() are used when SCX_OPS_BUILTIN_IDLE_PER_NODE is
disabled (will change this).

About scx_cpu_node(), which is used internally, I think it's convenient to
return NUMA_NO_NODE when idle-per-node is disabled, just to avoid repeating
the same check for scx_builtin_idle_per_node everywhere, and NUMA_NO_NODE
internally always means "use the global cpumask".

Do you think this is still error-prone? Or should I try to refactor the
code to get rid of this NUMA_NO_NODE == global cpumask logic?

Thanks,
-Andrea

Re: [PATCH 6/6] sched_ext: idle: Introduce node-aware idle cpu kfunc helpers

[Tejun Heo]

Hello,

On Sun, Feb 09, 2025 at 09:11:15AM +0100, Andrea Righi wrote:
...
> About scx_cpu_node(), which is used internally, I think it's convenient to
> return NUMA_NO_NODE when idle-per-node is disabled, just to avoid repeating
> the same check for scx_builtin_idle_per_node everywhere, and NUMA_NO_NODE
> internally always means "use the global cpumask".
> 
> Do you think this is still error-prone? Or should I try to refactor the
> code to get rid of this NUMA_NO_NODE == global cpumask logic?

I think that's fine as long as the name clearly indicates that the function
is doing something special other than mapping CPU to node. It can get pretty
confusing if something with a really generic name doesn't behave in a
generic manner.

Thanks.

-- 
tejun