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

Andrea Righi
2025-02-07T21:11:32Z

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