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@xxxxxxxxxx>
> > ---
> > 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
