Skip to contentSkip to conversation

mm: refactor zonelist constructors and iterators

PATCH Superseded Gregory Price 2 participants 8 messages Sep 2 – Sep 3

Subsystems (4)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Gregory Price

author maintainer
#0 lore raw

cover mm: refactor zonelist constructors and iterators

find_next_best_node() picks the next-closest node when building a fallback list, and hardcodes N_MEMORY as the set it picks from.

Refactor it into find_next_best_node_in(), which takes the candidate set explicitly.

This makes the existing behaviour explicit at both mm/memory-tiers.c call sites - they select demotion targets in fallback order from N_MEMORY - and lets callers narrow that set.

Then extract the per-node construction loop out of build_zonelists() into build_node_zonelist(), parameterised on the candidate nodemask and on the destination zonelist index.

Together these allow a zonelist to be built over a candidate set other than N_MEMORY, into a zonelist other than FALLBACK, and iterated in fallback order over a caller-defined subset.

These are prerequisites for generating a private node zonelist (nodes unreachable by default), but are otherwise general improvements to the existing interfaces so I'm proposing them separately.

No functional change intended - purely refactor commits.

Verified on x86_64:

- find_next_best_node_in() compiles to the same 319 bytes as

    find_next_best_node().

- Both mm/memory-tiers.c callers grow a single instruction - the added argument.
- Boot-time fallback orders are identical on a 4-node guest with an asymmetric distance matrix.

Gregory Price (2):
mm: refactor find_next_best_node to find_next_best_node_in mm/page_alloc: refactor build_node_zonelist() out of build_zonelists()

 mm/internal.h     |  6 ++++--
 mm/memory-tiers.c |  7 +++---
 mm/page_alloc.c   | 55 +++++++++++++++++++++++++++++++----------------
 3 files changed, 45 insertions(+), 23 deletions(-)
Signature · 1 line
2.53.0-Meta
author maintainer
#1 lore raw

PATCH 1/2 mm: refactor find_next_best_node to find_next_best_node_in

find_next_best_node() picks the next-closest node for a fallback list from the full N_MEMORY set. Refactor it into find_next_best_node_in(), which takes an explicit candidates nodemask.

This enables building fallback lists with non-N_MEMORY candidates.

No functional change: every caller still selects from N_MEMORY.

---
 mm/internal.h     |  6 ++++--
 mm/memory-tiers.c |  7 ++++---
 mm/page_alloc.c   | 13 ++++++++-----
 3 files changed, 16 insertions(+), 10 deletions(-)
mm/internal.h +4 -2
index e16f1250b25c8..18d041ff5c52c 100644
@@ -1130,7 +1130,8 @@ extern int node_reclaim_mode;
 
 extern unsigned long node_reclaim(struct pglist_data *pgdat,
 				  gfp_t gfp_mask, unsigned int order);
-extern int find_next_best_node(int node, nodemask_t *used_node_mask);
+extern int find_next_best_node_in(int node, nodemask_t *used_node_mask,
+				  const nodemask_t *candidates);
 #else
 #define node_reclaim_mode 0
 
@@ -1139,7 +1140,8 @@ static inline unsigned long node_reclaim(struct pglist_data *pgdat,
 {
 	return 0;
 }
-static inline int find_next_best_node(int node, nodemask_t *used_node_mask)
+static inline int find_next_best_node_in(int node, nodemask_t *used_node_mask,
+					 const nodemask_t *candidates)
 {
 	return NUMA_NO_NODE;
 }
mm/memory-tiers.c +4 -3
index 54851d8a195b0..25e121851b586 100644
@@ -370,7 +370,7 @@ int next_demotion_node(int node, const nodemask_t *allowed_mask)
 	 * closest demotion target.
 	 */
 	nodes_complement(mask, *allowed_mask);
-	return find_next_best_node(node, &mask);
+	return find_next_best_node_in(node, &mask, &node_states[N_MEMORY]);
 }
 
 static void disable_all_demotion_targets(void)
@@ -450,7 +450,7 @@ static void establish_demotion_targets(void)
 		memtier = list_next_entry(memtier, list);
 		tier_nodes = get_memtier_nodemask(memtier);
 		/*
-		 * find_next_best_node, use 'used' nodemask as a skip list.
+		 * find_next_best_node_in, use 'used' nodemask as a skip list.
 		 * Add all memory nodes except the selected memory tier
 		 * nodelist to skip list so that we find the best node from the
 		 * memtier nodelist.
@@ -463,7 +463,8 @@ static void establish_demotion_targets(void)
 		 * in the preferred mask when allocating pages during demotion.
 		 */
 		do {
-			target = find_next_best_node(node, &tier_nodes);
+			target = find_next_best_node_in(node, &tier_nodes,
+							&node_states[N_MEMORY]);
 			if (target == NUMA_NO_NODE)
 				break;
 
mm/page_alloc.c +8 -5
index c4dc61ec663ee..4dde1cbe2fd43 100644
@@ -5779,9 +5779,10 @@ static int numa_zonelist_order_handler(const struct ctl_table *table, int write,
 static int node_load[MAX_NUMNODES];
 
 /**
- * find_next_best_node - find the next node that should appear in a given node's fallback list
+ * find_next_best_node_in - find the next node that should appear in a given node's fallback list
  * @node: node whose fallback list we're appending
  * @used_node_mask: nodemask_t of already used nodes
+ * @candidates: nodemask_t of nodes eligible for selection
  *
  * We use a number of factors to determine which is the next node that should
  * appear on a given node's fallback list.  The node should not have appeared
@@ -5793,7 +5794,8 @@ static int node_load[MAX_NUMNODES];
  *
  * Return: node id of the found node or %NUMA_NO_NODE if no node is found.
  */
-int find_next_best_node(int node, nodemask_t *used_node_mask)
+int find_next_best_node_in(int node, nodemask_t *used_node_mask,
+			   const nodemask_t *candidates)
 {
 	int n, val;
 	int min_val = INT_MAX;
@@ -5803,12 +5805,12 @@ int find_next_best_node(int node, nodemask_t *used_node_mask)
 	 * Use the local node if we haven't already, but for memoryless local
 	 * node, we should skip it and fall back to other nodes.
 	 */
-	if (!node_isset(node, *used_node_mask) && node_state(node, N_MEMORY)) {
+	if (!node_isset(node, *used_node_mask) && node_isset(node, *candidates)) {
 		node_set(node, *used_node_mask);
 		return node;
 	}
 
-	for_each_node_state(n, N_MEMORY) {
+	for_each_node_mask(n, *candidates) {
 
 		/* Don't want a node to appear more than once */
 		if (node_isset(n, *used_node_mask))
@@ -5893,7 +5895,8 @@ static void build_zonelists(pg_data_t *pgdat)
 	prev_node = local_node;
 
 	memset(node_order, 0, sizeof(node_order));
-	while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
+	while ((node = find_next_best_node_in(local_node, &used_mask,
+					      &node_states[N_MEMORY])) >= 0) {
 		/*
 		 * We don't want to pressure a particular node.
 		 * So adding penalty to the first node in same
Signature · 1 line
2.53.0-Meta
author maintainer Acked-by Balbir Singh on v1 1/2
#2 lore raw

Re: [PATCH 1/2] mm: refactor find_next_best_node to find_next_best_node_in

Quoted 9 lines · Gregory Price

find_next_best_node() picks the next-closest node for a fallback list from the full N_MEMORY set. Refactor it into find_next_best_node_in(), which takes an explicit candidates nodemask.

This enables building fallback lists with non-N_MEMORY candidates.

No functional change: every caller still selects from N_MEMORY.

Just realized this should carry an Ack from Balbir

see - https://lore.kernel.org/linux-mm/[email protected]/

maintainer Reviewed-by on v1 1/2
#3 lore raw

Re: [PATCH 1/2] mm: refactor find_next_best_node to find_next_best_node_in

In reply to Gregory Price
Quoted 9 lines · Gregory Price

find_next_best_node() picks the next-closest node for a fallback list from the full N_MEMORY set. Refactor it into find_next_best_node_in(), which takes an explicit candidates nodemask.

This enables building fallback lists with non-N_MEMORY candidates.

No functional change: every caller still selects from N_MEMORY.

Nit:

Quoted 11 lines
---
 mm/internal.h     |  6 ++++--
 mm/memory-tiers.c |  7 ++++---
 mm/page_alloc.c   | 13 ++++++++-----
 3 files changed, 16 insertions(+), 10 deletions(-)
mm/internal.h +0 -0
index e16f1250b25c8..18d041ff5c52c 100644

mm/internal.h extern int node_reclaim_mode; · line 1134

Quoted 6 lines
mm/internal.h +2 -1
@@ -1130,7 +1130,8 @@ extern int node_reclaim_mode;
 
 extern unsigned long node_reclaim(struct pglist_data *pgdat,
 				  gfp_t gfp_mask, unsigned int order);
-extern int find_next_best_node(int node, nodemask_t *used_node_mask);
+extern int find_next_best_node_in(int node, nodemask_t *used_node_mask,
+				  const nodemask_t *candidates);

Drop the extern while touching a line.

Quoted 96 lines
mm/internal.h +2 -1
 #else
 #define node_reclaim_mode 0
 
@@ -1139,7 +1140,8 @@ static inline unsigned long node_reclaim(struct pglist_data *pgdat,
 {
 	return 0;
 }
-static inline int find_next_best_node(int node, nodemask_t *used_node_mask)
+static inline int find_next_best_node_in(int node, nodemask_t *used_node_mask,
+					 const nodemask_t *candidates)
 {
 	return NUMA_NO_NODE;
 }
mm/memory-tiers.c +4 -3
index 54851d8a195b0..25e121851b586 100644
@@ -370,7 +370,7 @@ int next_demotion_node(int node, const nodemask_t *allowed_mask)
 	 * closest demotion target.
 	 */
 	nodes_complement(mask, *allowed_mask);
-	return find_next_best_node(node, &mask);
+	return find_next_best_node_in(node, &mask, &node_states[N_MEMORY]);
 }
 
 static void disable_all_demotion_targets(void)
@@ -450,7 +450,7 @@ static void establish_demotion_targets(void)
 		memtier = list_next_entry(memtier, list);
 		tier_nodes = get_memtier_nodemask(memtier);
 		/*
-		 * find_next_best_node, use 'used' nodemask as a skip list.
+		 * find_next_best_node_in, use 'used' nodemask as a skip list.
 		 * Add all memory nodes except the selected memory tier
 		 * nodelist to skip list so that we find the best node from the
 		 * memtier nodelist.
@@ -463,7 +463,8 @@ static void establish_demotion_targets(void)
 		 * in the preferred mask when allocating pages during demotion.
 		 */
 		do {
-			target = find_next_best_node(node, &tier_nodes);
+			target = find_next_best_node_in(node, &tier_nodes,
+							&node_states[N_MEMORY]);
 			if (target == NUMA_NO_NODE)
 				break;
 
mm/page_alloc.c +8 -5
index c4dc61ec663ee..4dde1cbe2fd43 100644
@@ -5779,9 +5779,10 @@ static int numa_zonelist_order_handler(const struct ctl_table *table, int write,
 static int node_load[MAX_NUMNODES];
 
 /**
- * find_next_best_node - find the next node that should appear in a given node's fallback list
+ * find_next_best_node_in - find the next node that should appear in a given node's fallback list
  * @node: node whose fallback list we're appending
  * @used_node_mask: nodemask_t of already used nodes
+ * @candidates: nodemask_t of nodes eligible for selection
  *
  * We use a number of factors to determine which is the next node that should
  * appear on a given node's fallback list.  The node should not have appeared
@@ -5793,7 +5794,8 @@ static int node_load[MAX_NUMNODES];
  *
  * Return: node id of the found node or %NUMA_NO_NODE if no node is found.
  */
-int find_next_best_node(int node, nodemask_t *used_node_mask)
+int find_next_best_node_in(int node, nodemask_t *used_node_mask,
+			   const nodemask_t *candidates)
 {
 	int n, val;
 	int min_val = INT_MAX;
@@ -5803,12 +5805,12 @@ int find_next_best_node(int node, nodemask_t *used_node_mask)
 	 * Use the local node if we haven't already, but for memoryless local
 	 * node, we should skip it and fall back to other nodes.
 	 */
-	if (!node_isset(node, *used_node_mask) && node_state(node, N_MEMORY)) {
+	if (!node_isset(node, *used_node_mask) && node_isset(node, *candidates)) {
 		node_set(node, *used_node_mask);
 		return node;
 	}
 
-	for_each_node_state(n, N_MEMORY) {
+	for_each_node_mask(n, *candidates) {
 
 		/* Don't want a node to appear more than once */
 		if (node_isset(n, *used_node_mask))
@@ -5893,7 +5895,8 @@ static void build_zonelists(pg_data_t *pgdat)
 	prev_node = local_node;
 
 	memset(node_order, 0, sizeof(node_order));
-	while ((node = find_next_best_node(local_node, &used_mask)) >= 0) {
+	while ((node = find_next_best_node_in(local_node, &used_mask,
+					      &node_states[N_MEMORY])) >= 0) {
 		/*
 		 * We don't want to pressure a particular node.
 		 * So adding penalty to the first node in same
author maintainer
#4 lore raw

Re: [PATCH 1/2] mm: refactor find_next_best_node to find_next_best_node_in

Quoted 27 lines · Vlastimil Babka (SUSE)
Quoted 9 lines · Gregory Price

find_next_best_node() picks the next-closest node for a fallback list from the full N_MEMORY set. Refactor it into find_next_best_node_in(), which takes an explicit candidates nodemask.

This enables building fallback lists with non-N_MEMORY candidates.

No functional change: every caller still selects from N_MEMORY.

Nit:

Quoted 12 lines
---
 mm/internal.h     |  6 ++++--
 mm/memory-tiers.c |  7 ++++---
 mm/page_alloc.c   | 13 ++++++++-----
 3 files changed, 16 insertions(+), 10 deletions(-)
mm/internal.h +0 -0
index e16f1250b25c8..18d041ff5c52c 100644
@@ -1130,7 +1130,8 @@ extern int node_reclaim_mode;
 
Quoted 8 lines

mm/internal.h extern int node_reclaim_mode; · line 1134

Quoted 5 lines
mm/internal.h +2 -1
 extern unsigned long node_reclaim(struct pglist_data *pgdat,
 				  gfp_t gfp_mask, unsigned int order);
-extern int find_next_best_node(int node, nodemask_t *used_node_mask);
+extern int find_next_best_node_in(int node, nodemask_t *used_node_mask,
+				  const nodemask_t *candidates);

Drop the extern while touching a line.

ack.

author maintainer
#5 lore raw

PATCH 2/2 mm/page_alloc: refactor build_node_zonelist() out of build_zonelists()

In reply to Gregory Price

Extract per-node fallback-list construction into build_node_zonelist().

This lets us build new zonelists from candidate nodemasks instead of just the default N_MEMORY node state list.

No functional change: build_zonelists() builds the same FALLBACK list over N_MEMORY with node_load updates as before.

---
 mm/page_alloc.c | 44 ++++++++++++++++++++++++++++++--------------
 1 file changed, 30 insertions(+), 14 deletions(-)
mm/page_alloc.c +30 -14
index 4dde1cbe2fd43..e1d7c8b221d0d 100644
@@ -5849,12 +5849,12 @@ int find_next_best_node_in(int node, nodemask_t *used_node_mask,
  * DMA zone, if any--but risks exhausting DMA zone.
  */
 static void build_zonelists_in_node_order(pg_data_t *pgdat, int *node_order,
-		unsigned nr_nodes)
+		unsigned int nr_nodes, int zlidx)
 {
 	struct zoneref *zonerefs;
 	int i;
 
-	zonerefs = pgdat->node_zonelists[ZONELIST_FALLBACK]._zonerefs;
+	zonerefs = pgdat->node_zonelists[zlidx]._zonerefs;
 
 	for (i = 0; i < nr_nodes; i++) {
 		int nr_zones;
@@ -5883,26 +5883,28 @@ static void build_thisnode_zonelists(pg_data_t *pgdat)
 	zonerefs->zone_idx = 0;
 }
 
-static void build_zonelists(pg_data_t *pgdat)
+/*
+ * Build one node-ordered fallback list from a candidate nodemask.
+ * update_load round-robins node_load across equidistant nodes.
+ */
+static void build_node_zonelist(pg_data_t *pgdat, const nodemask_t *candidates,
+				int zlidx, bool update_load,
+				int *node_order, int *nr)
 {
-	static int node_order[MAX_NUMNODES];
-	int node, nr_nodes = 0;
 	nodemask_t used_mask = NODE_MASK_NONE;
-	int local_node, prev_node;
-
-	/* NUMA-aware ordering of nodes */
-	local_node = pgdat->node_id;
-	prev_node = local_node;
+	int local_node = pgdat->node_id;
+	int prev_node = local_node;
+	int node, nr_nodes = 0;
 
-	memset(node_order, 0, sizeof(node_order));
 	while ((node = find_next_best_node_in(local_node, &used_mask,
-					      &node_states[N_MEMORY])) >= 0) {
+					      candidates)) >= 0) {
 		/*
 		 * We don't want to pressure a particular node.
 		 * So adding penalty to the first node in same
 		 * distance group to make it round-robin.
 		 */
-		if (node_distance(local_node, node) !=
+		if (update_load &&
+		    node_distance(local_node, node) !=
 		    node_distance(local_node, prev_node))
 			node_load[node] += 1;
 
@@ -5910,8 +5912,22 @@ static void build_zonelists(pg_data_t *pgdat)
 		prev_node = node;
 	}
 
-	build_zonelists_in_node_order(pgdat, node_order, nr_nodes);
+	build_zonelists_in_node_order(pgdat, node_order, nr_nodes, zlidx);
+	*nr = nr_nodes;
+}
+
+static void build_zonelists(pg_data_t *pgdat)
+{
+	static int node_order[MAX_NUMNODES];
+	int local_node = pgdat->node_id;
+	int node, nr_nodes = 0;
+
+	memset(node_order, 0, sizeof(node_order));
+
+	build_node_zonelist(pgdat, &node_states[N_MEMORY], ZONELIST_FALLBACK,
+			    true, node_order, &nr_nodes);
 	build_thisnode_zonelists(pgdat);
+
 	pr_info("Fallback order for Node %d: ", local_node);
 	for (node = 0; node < nr_nodes; node++)
 		pr_cont("%d ", node_order[node]);
Signature · 1 line
2.53.0-Meta
#6 lore raw

Re: [PATCH 2/2] mm/page_alloc: refactor build_node_zonelist() out of build_zonelists()

Quoted 9 lines · Gregory Price

Extract per-node fallback-list construction into build_node_zonelist().

This lets us build new zonelists from candidate nodemasks instead of just the default N_MEMORY node state list.

No functional change: build_zonelists() builds the same FALLBACK list over N_MEMORY with node_load updates as before.

LGTM, but, while we're at it, could we just do the pr_cont() printing in build_node_zonelist() itself (maybe behind a flag if you don't want to print from future new caller) so it doesn't need to pass nr_nodes back to build_zonelists(). Then also the node_order array could live in build_node_zonelist() itself?

Actually I wonder if we could get ride of the node_order array completely. It would mean the loop processing in build_zonelists_in_node_order() would have to be done piece-meal in build_node_zonelist() itself. But seems feasible? Depends on how you intend to reuse/extend the new functions later, I guess...

Quoted 87 lines
---
 mm/page_alloc.c | 44 ++++++++++++++++++++++++++++++--------------
 1 file changed, 30 insertions(+), 14 deletions(-)
mm/page_alloc.c +30 -14
index 4dde1cbe2fd43..e1d7c8b221d0d 100644
@@ -5849,12 +5849,12 @@ int find_next_best_node_in(int node, nodemask_t *used_node_mask,
  * DMA zone, if any--but risks exhausting DMA zone.
  */
 static void build_zonelists_in_node_order(pg_data_t *pgdat, int *node_order,
-		unsigned nr_nodes)
+		unsigned int nr_nodes, int zlidx)
 {
 	struct zoneref *zonerefs;
 	int i;
 
-	zonerefs = pgdat->node_zonelists[ZONELIST_FALLBACK]._zonerefs;
+	zonerefs = pgdat->node_zonelists[zlidx]._zonerefs;
 
 	for (i = 0; i < nr_nodes; i++) {
 		int nr_zones;
@@ -5883,26 +5883,28 @@ static void build_thisnode_zonelists(pg_data_t *pgdat)
 	zonerefs->zone_idx = 0;
 }
 
-static void build_zonelists(pg_data_t *pgdat)
+/*
+ * Build one node-ordered fallback list from a candidate nodemask.
+ * update_load round-robins node_load across equidistant nodes.
+ */
+static void build_node_zonelist(pg_data_t *pgdat, const nodemask_t *candidates,
+				int zlidx, bool update_load,
+				int *node_order, int *nr)
 {
-	static int node_order[MAX_NUMNODES];
-	int node, nr_nodes = 0;
 	nodemask_t used_mask = NODE_MASK_NONE;
-	int local_node, prev_node;
-
-	/* NUMA-aware ordering of nodes */
-	local_node = pgdat->node_id;
-	prev_node = local_node;
+	int local_node = pgdat->node_id;
+	int prev_node = local_node;
+	int node, nr_nodes = 0;
 
-	memset(node_order, 0, sizeof(node_order));
 	while ((node = find_next_best_node_in(local_node, &used_mask,
-					      &node_states[N_MEMORY])) >= 0) {
+					      candidates)) >= 0) {
 		/*
 		 * We don't want to pressure a particular node.
 		 * So adding penalty to the first node in same
 		 * distance group to make it round-robin.
 		 */
-		if (node_distance(local_node, node) !=
+		if (update_load &&
+		    node_distance(local_node, node) !=
 		    node_distance(local_node, prev_node))
 			node_load[node] += 1;
 
@@ -5910,8 +5912,22 @@ static void build_zonelists(pg_data_t *pgdat)
 		prev_node = node;
 	}
 
-	build_zonelists_in_node_order(pgdat, node_order, nr_nodes);
+	build_zonelists_in_node_order(pgdat, node_order, nr_nodes, zlidx);
+	*nr = nr_nodes;
+}
+
+static void build_zonelists(pg_data_t *pgdat)
+{
+	static int node_order[MAX_NUMNODES];
+	int local_node = pgdat->node_id;
+	int node, nr_nodes = 0;
+
+	memset(node_order, 0, sizeof(node_order));
+
+	build_node_zonelist(pgdat, &node_states[N_MEMORY], ZONELIST_FALLBACK,
+			    true, node_order, &nr_nodes);
 	build_thisnode_zonelists(pgdat);
+
 	pr_info("Fallback order for Node %d: ", local_node);
 	for (node = 0; node < nr_nodes; node++)
 		pr_cont("%d ", node_order[node]);
author maintainer
#7 lore raw

Re: [PATCH 2/2] mm/page_alloc: refactor build_node_zonelist() out of build_zonelists()

Quoted 9 lines · Vlastimil Babka (SUSE)
Quoted 8 lines · Gregory Price

Extract per-node fallback-list construction into build_node_zonelist().

This lets us build new zonelists from candidate nodemasks instead of just the default N_MEMORY node state list.

No functional change: build_zonelists() builds the same FALLBACK list over N_MEMORY with node_load updates as before.

Quoted 8 lines
Quoted 1 line

LGTM, but, while we're at it, could we just do the pr_cont() printing in build_node_zonelist() itself (maybe behind a flag if you don't want to print from future new caller) so it doesn't need to pass nr_nodes back to build_zonelists(). Then also the node_order array could live in build_node_zonelist() itself?

Seems trivial enough, will let this sit for a minute and spin a v2.

Quoted 6 lines

Actually I wonder if we could get ride of the node_order array completely. It would mean the loop processing in build_zonelists_in_node_order() would have to be done piece-meal in build_node_zonelist() itself. But seems feasible? Depends on how you intend to reuse/extend the new functions later, I guess...

I can take a look. We've been testing a couple different things, will see how well things generalize (private node fallback lists, inverted fallback lists for proactive reclaim node ordering, some other stuff).

~Gregory