mm: page_alloc: speed up fallbacks in rmqueue_bulk()

find_suitable_fallback() is not as efficient as it could be, and somewhat difficult to follow.

1. should_try_claim_block() is a loop invariant. There is no point in checking fallback areas if the caller is interested in claimable blocks but the order and the migratetype don't allow for that.

2. __rmqueue_steal() doesn't care about claimability, so it shouldn't have to run those tests.

Different callers want different things from this helper:

1. __compact_finished() scans orders up until it finds a claimable block
2. __rmqueue_claim() scans orders down as long as blocks are claimable
3. __rmqueue_steal() doesn't care about claimability at all

Move should_try_claim_block() out of the loop. Only test it for the two callers who care in the first place. Distinguish "no blocks" from "order + mt are not claimable" in the return value; __rmqueue_claim() can stop once order becomes unclaimable, __compact_finished() can keep advancing until order becomes claimable.

Before:

Performance counter stats for './run case-lru-file-mmap-read' (5 runs):

	 85,294.85 msec task-clock                       #    5.644 CPUs utilized               ( +-  0.32% )
	    15,968      context-switches                 #  187.209 /sec                        ( +-  3.81% )
	       153      cpu-migrations                   #    1.794 /sec                        ( +-  3.29% )
	   801,808      page-faults                      #    9.400 K/sec                       ( +-  0.10% )
   733,358,331,786      instructions                     #    1.87  insn per cycle              ( +-  0.20% )  (64.94%)
   392,622,904,199      cycles                           #    4.603 GHz                         ( +-  0.31% )  (64.84%)
   148,563,488,531      branches                         #    1.742 G/sec                       ( +-  0.18% )  (63.86%)
       152,143,228      branch-misses                    #    0.10% of all branches             ( +-  1.19% )  (62.82%)

	   15.1128 +- 0.0637 seconds time elapsed  ( +-  0.42% )

After:

Performance counter stats for './run case-lru-file-mmap-read' (5 runs):

         84,380.21 msec task-clock                       #    5.664 CPUs utilized               ( +-  0.21% )
            16,656      context-switches                 #  197.392 /sec                        ( +-  3.27% )
               151      cpu-migrations                   #    1.790 /sec                        ( +-  3.28% )
           801,703      page-faults                      #    9.501 K/sec                       ( +-  0.09% )
   731,914,183,060      instructions                     #    1.88  insn per cycle              ( +-  0.38% )  (64.90%)
   388,673,535,116      cycles                           #    4.606 GHz                         ( +-  0.24% )  (65.06%)
   148,251,482,143      branches                         #    1.757 G/sec                       ( +-  0.37% )  (63.92%)
       149,766,550      branch-misses                    #    0.10% of all branches             ( +-  1.22% )  (62.88%)

           14.8968 +- 0.0486 seconds time elapsed  ( +-  0.33% )

Signed-off-by Johannes Weiner <[email protected]>

find_suitable_fallback() is not as efficient as it could be, and somewhat difficult to follow.

1. should_try_claim_block() is a loop invariant. There is no point in checking fallback areas if the caller is interested in claimable blocks but the order and the migratetype don't allow for that.

2. __rmqueue_steal() doesn't care about claimability, so it shouldn't have to run those tests.

Different callers want different things from this helper:

1. __compact_finished() scans orders up until it finds a claimable block
2. __rmqueue_claim() scans orders down as long as blocks are claimable
3. __rmqueue_steal() doesn't care about claimability at all

Move should_try_claim_block() out of the loop. Only test it for the two callers who care in the first place. Distinguish "no blocks" from "order + mt are not claimable" in the return value; __rmqueue_claim() can stop once order becomes unclaimable, __compact_finished() can keep advancing until order becomes claimable.

Before:

Performance counter stats for './run case-lru-file-mmap-read' (5 runs):

	 85,294.85 msec task-clock                       #    5.644 CPUs utilized               ( +-  0.32% )
	    15,968      context-switches                 #  187.209 /sec                        ( +-  3.81% )
	       153      cpu-migrations                   #    1.794 /sec                        ( +-  3.29% )
	   801,808      page-faults                      #    9.400 K/sec                       ( +-  0.10% )
   733,358,331,786      instructions                     #    1.87  insn per cycle              ( +-  0.20% )  (64.94%)
   392,622,904,199      cycles                           #    4.603 GHz                         ( +-  0.31% )  (64.84%)
   148,563,488,531      branches                         #    1.742 G/sec                       ( +-  0.18% )  (63.86%)
       152,143,228      branch-misses                    #    0.10% of all branches             ( +-  1.19% )  (62.82%)

	   15.1128 +- 0.0637 seconds time elapsed  ( +-  0.42% )

After:

Performance counter stats for './run case-lru-file-mmap-read' (5 runs):

         84,380.21 msec task-clock                       #    5.664 CPUs utilized               ( +-  0.21% )
            16,656      context-switches                 #  197.392 /sec                        ( +-  3.27% )
               151      cpu-migrations                   #    1.790 /sec                        ( +-  3.28% )
           801,703      page-faults                      #    9.501 K/sec                       ( +-  0.09% )
   731,914,183,060      instructions                     #    1.88  insn per cycle              ( +-  0.38% )  (64.90%)
   388,673,535,116      cycles                           #    4.606 GHz                         ( +-  0.24% )  (65.06%)
   148,251,482,143      branches                         #    1.757 G/sec                       ( +-  0.37% )  (63.92%)
       149,766,550      branch-misses                    #    0.10% of all branches             ( +-  1.22% )  (62.88%)

           14.8968 +- 0.0486 seconds time elapsed  ( +-  0.33% )

Signed-off-by Johannes Weiner <[email protected]>

---
 mm/compaction.c |  4 +---
 mm/internal.h   |  2 +-
 mm/page_alloc.c | 31 +++++++++++++------------------
 3 files changed, 15 insertions(+), 22 deletions(-)

mm/compaction.c +1 -3

index 139f00c0308a..7462a02802a5 100644
@@ -2348,7 +2348,6 @@ static enum compact_result __compact_finished(struct compact_control *cc)
 	ret = COMPACT_NO_SUITABLE_PAGE;
 	for (order = cc->order; order < NR_PAGE_ORDERS; order++) {
 		struct free_area *area = &cc->zone->free_area[order];
-		bool claim_block;
 
 		/* Job done if page is free of the right migratetype */
 		if (!free_area_empty(area, migratetype))

@@ -2364,8 +2363,7 @@ static enum compact_result __compact_finished(struct compact_control *cc)
 		 * Job done if allocation would steal freepages from
 		 * other migratetype buddy lists.
 		 */
-		if (find_suitable_fallback(area, order, migratetype,
-						true, &claim_block) != -1)
+		if (find_suitable_fallback(area, order, migratetype, true) >= 0)
 			/*
 			 * Movable pages are OK in any pageblock. If we are
 			 * stealing for a non-movable allocation, make sure

mm/internal.h +1 -1

index 50c2f590b2d0..55384b9971c3 100644
@@ -915,7 +915,7 @@ static inline void init_cma_pageblock(struct page *page)
 
 
 int find_suitable_fallback(struct free_area *area, unsigned int order,
-			int migratetype, bool claim_only, bool *claim_block);
+			   int migratetype, bool claimable);
 
 static inline bool free_area_empty(struct free_area *area, int migratetype)
 {

mm/page_alloc.c +12 -16

index 03b0d45ed45a..1522e3a29b16 100644
@@ -2077,31 +2077,25 @@ static bool should_try_claim_block(unsigned int order, int start_mt)
 
 /*
  * Check whether there is a suitable fallback freepage with requested order.
- * Sets *claim_block to instruct the caller whether it should convert a whole
- * pageblock to the returned migratetype.
- * If only_claim is true, this function returns fallback_mt only if
+ * If claimable is true, this function returns fallback_mt only if
  * we would do this whole-block claiming. This would help to reduce
  * fragmentation due to mixed migratetype pages in one pageblock.
  */
 int find_suitable_fallback(struct free_area *area, unsigned int order,
-			int migratetype, bool only_claim, bool *claim_block)
+			   int migratetype, bool claimable)
 {
 	int i;
-	int fallback_mt;
+
+	if (claimable && !should_try_claim_block(order, migratetype))
+		return -2;
 
 	if (area->nr_free == 0)
 		return -1;
 
-	*claim_block = false;
 	for (i = 0; i < MIGRATE_PCPTYPES - 1 ; i++) {
-		fallback_mt = fallbacks[migratetype][i];
-		if (free_area_empty(area, fallback_mt))
-			continue;
+		int fallback_mt = fallbacks[migratetype][i];
 
-		if (should_try_claim_block(order, migratetype))
-			*claim_block = true;
-
-		if (*claim_block || !only_claim)
+		if (!free_area_empty(area, fallback_mt))
 			return fallback_mt;
 	}
 

@@ -2206,7 +2200,6 @@ __rmqueue_claim(struct zone *zone, int order, int start_migratetype,
 	int min_order = order;
 	struct page *page;
 	int fallback_mt;
-	bool claim_block;
 
 	/*
 	 * Do not steal pages from freelists belonging to other pageblocks

@@ -2225,11 +2218,14 @@ __rmqueue_claim(struct zone *zone, int order, int start_migratetype,
 				--current_order) {
 		area = &(zone->free_area[current_order]);
 		fallback_mt = find_suitable_fallback(area, current_order,
-				start_migratetype, false, &claim_block);
+						     start_migratetype, true);
+
+		/* No block in that order */
 		if (fallback_mt == -1)
 			continue;
 
-		if (!claim_block)
+		/* Advanced into orders too low to claim, abort */
+		if (fallback_mt == -2)
 			break;
 
 		page = get_page_from_free_area(area, fallback_mt);

@@ -2254,12 +2250,11 @@ __rmqueue_steal(struct zone *zone, int order, int start_migratetype)
 	int current_order;
 	struct page *page;
 	int fallback_mt;

find_suitable_fallback() is not as efficient as it could be, and somewhat difficult to follow.

1. should_try_claim_block() is a loop invariant. There is no point in checking fallback areas if the caller is interested in claimable blocks but the order and the migratetype don't allow for that.

2. __rmqueue_steal() doesn't care about claimability, so it shouldn't have to run those tests.

Different callers want different things from this helper:

1. __compact_finished() scans orders up until it finds a claimable block
2. __rmqueue_claim() scans orders down as long as blocks are claimable
3. __rmqueue_steal() doesn't care about claimability at all

Move should_try_claim_block() out of the loop. Only test it for the two callers who care in the first place. Distinguish "no blocks" from "order + mt are not claimable" in the return value; __rmqueue_claim() can stop once order becomes unclaimable, __compact_finished() can keep advancing until order becomes claimable.

Quoted 16 lines · Johannes Weiner

find_suitable_fallback() is not as efficient as it could be, and somewhat difficult to follow.

1. should_try_claim_block() is a loop invariant. There is no point in checking fallback areas if the caller is interested in claimable blocks but the order and the migratetype don't allow for that.

2. __rmqueue_steal() doesn't care about claimability, so it shouldn't have to run those tests.

Different callers want different things from this helper:

1. __compact_finished() scans orders up until it finds a claimable block
2. __rmqueue_claim() scans orders down as long as blocks are claimable
3. __rmqueue_steal() doesn't care about claimability at all

Quoted 5 lines

Move should_try_claim_block() out of the loop. Only test it for the two callers who care in the first place. Distinguish "no blocks" from "order + mt are not claimable" in the return value; __rmqueue_claim() can stop once order becomes unclaimable, __compact_finished() can keep advancing until order becomes claimable.

Nice!

My initial thought was: now we can drop the boolean arg and just have the callers who care about claimability just call should_try_claim_block() themselves. Then we can also get rid of the magic -2 return value and find_suitable_fallback() becomes a pretty obvious function.

I think it's a win on balance but it does make more verbosity at the callsites, and an extra interface between page_alloc.c and compaction.c So maybe it's a wash, maybe you already considered it and decided you don't prefer it.

So, LGTM either way, I will attempt to attach the optional additional patch for your perusal, hopefully without molesting the mail encoding this time...

Reviewed-by Brendan Jackman <[email protected]>

From 25f77012674db95354fb2496bc89954b8f8b4e6c Mon Sep 17 00:00:00 2001
From: Brendan Jackman <[email protected]>
Date: Thu, 10 Apr 2025 13:22:58 +0000
Subject: [PATCH] mm: page_alloc: Split up find_suitable_fallback()

Now that it's been simplified, it's clear that the bool arg isn't needed, callers can just use should_try_claim_block(). Once that logic is stripped out, the function becomes very obvious and can get a more straightforward name and comment.

Signed-off-by Brendan Jackman <[email protected]>

---
 mm/compaction.c |  3 ++-
 mm/internal.h   |  5 +++--
 mm/page_alloc.c | 33 +++++++++++++--------------------
 3 files changed, 18 insertions(+), 23 deletions(-)

mm/compaction.c +0 -0

index 39a4d178dff3c..d735c22e71029 100644

Review

Quoted 3 lines

(quoted diff) +2 -1

-		if (find_suitable_fallback(area, order, migratetype, true) >= 0)
+		if (should_try_claim_block(order, migratetype) &&
+		    find_fallback_migratetype(area, order, migratetype) >= 0)

So I agree with pushing the test into the callers. However, I think the name "should_try_claim_block()" is not great for this. It makes sense in the alloc/fallback path, but compaction here doesn't claim anything. It just wants to know if this order + migratetype is eligible under block claiming rules.

IMO this would be more readable with the old terminology:

		if (can_claim_block(order, migratetype) &&
		    find_fallback_migratetype(area, order, migratetype) >= 0)

Quoted 10 lines · Johannes Weiner

mm/compaction.c static enum compact_result __compact_finished(struct compact_control *cc) · line 2367

Quoted 3 lines

mm/compaction.c +2 -1

-		if (find_suitable_fallback(area, order, migratetype, true) >= 0)
+		if (should_try_claim_block(order, migratetype) &&
+		    find_fallback_migratetype(area, order, migratetype) >= 0)

So I agree with pushing the test into the callers. However, I think the name "should_try_claim_block()" is not great for this. It makes sense in the alloc/fallback path, but compaction here doesn't claim anything. It just wants to know if this order + migratetype is eligible under block claiming rules.

Quoted 4 lines

IMO this would be more readable with the old terminology:

		if (can_claim_block(order, migratetype) &&
		    find_fallback_migratetype(area, order, migratetype) >= 0)

Sure, that makes sense, here's a modified version of the patch:

---

From 85be0fca4627c5b832a3382c92b6310609e14ca4 Mon Sep 17 00:00:00 2001
From: Brendan Jackman <[email protected]>
Date: Thu, 10 Apr 2025 13:22:58 +0000
Subject: [PATCH] mm: page_alloc: Split up find_suitable_fallback()

Now that it's been simplified, it's clear that the bool arg isn't needed, callers can just use should_try_claim_block(). Once that logic is stripped out, the function becomes very obvious and can get a more straightforward name and comment.

Since should_try_claim_block() is now exported to compaction.c, give it a name that makes more sense outside the context of allocation - should_claim_block() seems confusing in code that has no interest in actually claiming a block.

Signed-off-by Brendan Jackman <[email protected]>

	/*
	 * Find the largest available free page in the other list. This roughly
	 * approximates finding the pageblock with the most free pages, which
	 * would be too costly to do exactly.
	 */
	for (current_order = MAX_PAGE_ORDER; current_order >= min_order;
				--current_order) {

mm/page_alloc.c try_to_claim_block(struct zone *zone, struct page *page, · line 2197

Quoted 9 lines · Johannes Weiner

mm/page_alloc.c +0 -2

@@ -2194,11 +2194,11 @@ try_to_claim_block(struct zone *zone, struct page *page,
  * The use of signed ints for order and current_order is a deliberate
  * deviation from the rest of this file, to make the for loop
  * condition simpler.
- *
- * Return the stolen page, or NULL if none can be found.
  */

This commentary is pretty confusing now, there's a block of text that kinda vaguely applies to the aggregate of __rmqueue_steal(), __rmqueue_fallback() and half of __rmqueue(). I think this new code does a better job of speaking for itself so I think we should just delete this block comment and replace it with some more verbosity elsewhere.

mm/page_alloc.c try_to_claim_block(struct zone *zone, struct page *page, · line 2198

Quoted 1 line

mm/page_alloc.c +1 -0

+/* Try to claim a whole foreign block, take a page, expand the remainder */

Also on the commentary front, I am not a fan of "foreign" and "native":

- "Foreign" is already used in this file to mean NUMA-nonlocal.

- We already have "start" and "fallback" being used in identifiers as adjectives to describe the mitegratetype concept.

I wouldn't say those are _better_, "native" and "foreign" might be clearer, but it's not worth introducing inconsistency IMO.

mm/page_alloc.c try_to_claim_block(struct zone *zone, struct page *page, · line 2203

Quoted 6 lines

mm/page_alloc.c +1 -1

 static __always_inline struct page *
-__rmqueue_fallback(struct zone *zone, int order, int start_migratetype,
+__rmqueue_claim(struct zone *zone, int order, int start_migratetype,
 						unsigned int alloc_flags)
 {
 	struct free_area *area;

[pasting in more context that wasn't in the original diff..]

Quoted 7 lines

	/*
	 * Find the largest available free page in the other list. This roughly
	 * approximates finding the pageblock with the most free pages, which
	 * would be too costly to do exactly.
	 */
	for (current_order = MAX_PAGE_ORDER; current_order >= min_order;
				--current_order) {

IIUC we could go one step further here and also avoid repeating this iteration? Maybe something for a separate patch though?

Anyway, the approach seems like a clear improvement, thanks. I will need to take a closer look at it tomorrow, I've run out of brain juice today.

Here's what I got from redistributing the block comment and flipping the terminology:

mm/page_alloc.c +6 -11

index dfb2b3f508af..b8142d605691 100644
@@ -2183,21 +2183,13 @@ try_to_claim_block(struct zone *zone, struct page *page,
 }
 
 /*
- * Try finding a free buddy page on the fallback list.
- *
- * This will attempt to claim a whole pageblock for the requested type
- * to ensure grouping of such requests in the future.
- *
- * If a whole block cannot be claimed, steal an individual page, regressing to
- * __rmqueue_smallest() logic to at least break up as little contiguity as
- * possible.
+ * Try to allocate from some fallback migratetype by claiming the entire block,
+ * i.e. converting it to the allocation's start migratetype.
  *
  * The use of signed ints for order and current_order is a deliberate
  * deviation from the rest of this file, to make the for loop
  * condition simpler.
  */
-
-/* Try to claim a whole foreign block, take a page, expand the remainder */
 static __always_inline struct page *
 __rmqueue_claim(struct zone *zone, int order, int start_migratetype,
                                                unsigned int alloc_flags)

@@ -2247,7 +2239,10 @@ __rmqueue_claim(struct zone *zone, int order, int start_migratetype,
        return NULL;
 }
 
-/* Try to steal a single page from a foreign block */
+/*
+ * Try to steal a single page from some fallback migratetype. Leave the rest of
+ * the block as its current migratetype, potentially causing fragmentation.
+ */
 static __always_inline struct page *
 __rmqueue_steal(struct zone *zone, int order, int start_migratetype)
 {

Quoted 8 lines

Quoted 7 lines

	/*
	 * Find the largest available free page in the other list. This roughly
	 * approximates finding the pageblock with the most free pages, which
	 * would be too costly to do exactly.
	 */
	for (current_order = MAX_PAGE_ORDER; current_order >= min_order;
				--current_order) {

Quoted 2 lines

IIUC we could go one step further here and also avoid repeating this iteration? Maybe something for a separate patch though?

That might be worth a test, but agree this should be a separate patch.

AFAICS, in the most common configurations MAX_PAGE_ORDER is only one step above pageblock_order or even the same. It might not be worth the complication.

Review

Quoted 5 lines

        /*

(quoted diff) +3 -1

-        * Try the different freelists, native then foreign.
+        * First try the freelists of the requested migratetype, then try
+        * fallbacks. Roughly, each fallback stage poses more of a fragmentation
+        * risk.

How about "then try fallback modes with increasing levels of fragmentation risk."

Review __rmqueue(struct zone *zone, unsigned int order, int migratetype, · line 2333

Quoted 9 lines

* The fallback logic is expensive and rmqueue_bulk() calls in
* a loop with the zone->lock held, meaning the freelists are

(quoted diff) +1 -1

@@ -2332,7 +2329,7 @@ __rmqueue(struct zone *zone, unsigned int order, int migratetype,
        case RMQUEUE_CLAIM:
                page = __rmqueue_claim(zone, order, migratetype, alloc_flags);
                if (page) {
-                       /* Replenished native freelist, back to normal mode */
+                       /* Replenished requested migratetype's freelist, back to normal mode */
                        *mode = RMQUEUE_NORMAL;

This line is kind of long now. How about:

			/* Replenished preferred freelist, back to normal mode */

But yeah, I like your proposed changes. Would you care to send a proper patch?

Acked-by Johannes Weiner <[email protected]>

From 8ff20dbb52770d082e182482d2b47e521de028d1 Mon Sep 17 00:00:00 2001
From: Brendan Jackman <[email protected]>
Date: Wed, 9 Apr 2025 17:22:14 +000
Subject: [PATCH] page_alloc: speed up fallbacks in rmqueue_bulk() - comment updates

Tidy up some terminology and redistribute commentary.

Signed-off-by Brendan Jackman <[email protected]>

---
 mm/page_alloc.c | 22 +++++++++-------------
 1 file changed, 9 insertions(+), 13 deletions(-)

mm/page_alloc.c +9 -13

index dfb2b3f508af4..220bd0bcc38c3 100644
@@ -2183,21 +2183,13 @@ try_to_claim_block(struct zone *zone, struct page *page,
 }
 
 /*
- * Try finding a free buddy page on the fallback list.
- *
- * This will attempt to claim a whole pageblock for the requested type
- * to ensure grouping of such requests in the future.
- *
- * If a whole block cannot be claimed, steal an individual page, regressing to
- * __rmqueue_smallest() logic to at least break up as little contiguity as
- * possible.
+ * Try to allocate from some fallback migratetype by claiming the entire block,
+ * i.e. converting it to the allocation's start migratetype.
  *
  * The use of signed ints for order and current_order is a deliberate 
  * deviation from the rest of this file, to make the for loop
  * condition simpler.
  */
-
-/* Try to claim a whole foreign block, take a page, expand the remainder */
 static __always_inline struct page *
 __rmqueue_claim(struct zone *zone, int order, int start_migratetype,
                                                unsigned int alloc_flags)

@@ -2247,7 +2239,10 @@ __rmqueue_claim(struct zone *zone, int order, int start_migratetype,
        return NULL;
 }
 
-/* Try to steal a single page from a foreign block */
+/*
+ * Try to steal a single page from some fallback migratetype. Leave the rest of
+ * the block as its current migratetype, potentially causing fragmentation.
+ */
 static __always_inline struct page *
 __rmqueue_steal(struct zone *zone, int order, int start_migratetype)
 {

@@ -2307,7 +2302,8 @@ __rmqueue(struct zone *zone, unsigned int order, int migratetype,
        }
 
        /*
-        * Try the different freelists, native then foreign.
+        * First try the freelists of the requested migratetype, then try
+        * fallbacks modes with increasing levels of fragmentation risk.
         *
         * The fallback logic is expensive and rmqueue_bulk() calls in
         * a loop with the zone->lock held, meaning the freelists are

@@ -2332,7 +2328,7 @@ __rmqueue(struct zone *zone, unsigned int order, int migratetype,
        case RMQUEUE_CLAIM:
                page = __rmqueue_claim(zone, order, migratetype, alloc_flags);
                if (page) {
-                       /* Replenished native freelist, back to normal mode */
+                       /* Replenished preferred freelist, back to normal mode. */
                        *mode = RMQUEUE_NORMAL;
                        return page;
                }

base-commit: aa42382db4e2a4ed1f4ba97ffc50e2ce45accb0c

mm/page_alloc.c +1 -0

@@ -2934,6 +2981,7 @@ struct page *rmqueue_buddy(struct zone *preferred_zone, struct zone *zone,
 {
 	struct page *page;
 	unsigned long flags;
+	enum rmqueue_mode rmqm = RMQUEUE_NORMAL;
 
 	do {
 		page = NULL;

Quoted 15 lines · Johannes Weiner

(quoted diff) +2 -1

@@ -2934,6 +2981,7 @@ struct page *rmqueue_buddy(struct zone *preferred_zone, struct zone *zone,
 {
 	struct page *page;
 	unsigned long flags;
+	enum rmqueue_mode rmqm = RMQUEUE_NORMAL;
 
 	do {
 		page = NULL;

@@ -2945,7 +2993,7 @@ struct page *rmqueue_buddy(struct zone *preferred_zone, struct zone *zone,
 		if (alloc_flags & ALLOC_HIGHATOMIC)
 			page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
 		if (!page) {
-			page = __rmqueue(zone, order, migratetype, alloc_flags);
+			page = __rmqueue(zone, order, migratetype, alloc_flags, &rmqm);
 

Review struct page *rmqueue_buddy(struct zone *preferred_zone, struct zone *zone, · line 2999

Quoted 2 lines

(quoted diff) +0 -0

 			/*
 			 * If the allocation fails, allow OOM handling and

It was not in the diff, but it seems the zone->lock is held inside the do..while loop, doesn't it mean that the freelists are subject to outside changes and rmqm is stale?

The test robot identified c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest buddy") as the root cause of a 56.4% regression in vm-scalability::lru-file-mmap-read.

Carlos reports an earlier patch, c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block conversion"), as the root cause for a regression in worst-case zone->lock+irqoff hold times.

Both of these patches modify the page allocator's fallback path to be less greedy in an effort to stave off fragmentation. The flip side of this is that fallbacks are also less productive each time around, which means the fallback search can run much more frequently.

Carlos' traces point to rmqueue_bulk() specifically, which tries to refill the percpu cache by allocating a large batch of pages in a loop. It highlights how once the native freelists are exhausted, the fallback code first scans orders top-down for whole blocks to claim, then falls back to a bottom-up search for the smallest buddy to steal. For the next batch page, it goes through the same thing again.

This can be made more efficient. Since rmqueue_bulk() holds the zone->lock over the entire batch, the freelists are not subject to outside changes; when the search for a block to claim has already failed, there is no point in trying again for the next page.

Modify __rmqueue() to remember the last successful fallback mode, and restart directly from there on the next rmqueue_bulk() iteration.

Oliver confirms that this improves beyond the regression that the test robot reported against c2f6ea38fc1b:

commit:
f3b92176f4 ("tools/selftests: add guard region test for /proc/$pid/pagemap") c2f6ea38fc ("mm: page_alloc: don't steal single pages from biggest buddy") acc4d5ff0b ("Merge tag 'net-6.15-rc0' of git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net")
2c847f27c3 ("mm: page_alloc: speed up fallbacks in rmqueue_bulk()") <--- your patch

f3b92176f4f7100f c2f6ea38fc1b640aa7a2e155cc1 acc4d5ff0b61eb1715c498b6536 2c847f27c37da65a93d23c237c5 ---------------- --------------------------- --------------------------- ---------------------------
%stddev %change %stddev %change %stddev %change %stddev
\ | \ | \ | \
25525364 ± 3% -56.4% 11135467 -57.8% 10779336 +31.6% 33581409 vm-scalability.throughput

Carlos confirms that worst-case times are almost fully recovered compared to before the earlier culprit patch:

2dd482ba627d (before freelist hygiene): 1ms
c0cd6f557b90 (after freelist hygiene): 90ms
next-20250319 (steal smallest buddy): 280ms
this patch : 8ms

Reported-by kernel test robot <[email protected]>

Reported-by Carlos Song <[email protected]>

Tested-by kernel test robot <[email protected]>

Fixes c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block conversion")

Fixes c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest buddy")

Closes https://lore.kernel.org/oe-lkp/[email protected] open here

Cc [email protected] # 6.10+

Signed-off-by Johannes Weiner <[email protected]>

---
 mm/page_alloc.c | 100 +++++++++++++++++++++++++++++++++++-------------
 1 file changed, 74 insertions(+), 26 deletions(-)

-----Original Message-----
From: Johannes Weiner <[email protected]>
Sent: Tuesday, April 8, 2025 2:02 AM
To: Andrew Morton <[email protected]>
Cc: Vlastimil Babka <[email protected]>; Brendan Jackman <[email protected]>; Mel Gorman <[email protected]>; Carlos Song <[email protected]>; [email protected]; [email protected]; kernel test robot <[email protected]>; [email protected]
Subject: [EXT] [PATCH 1/2] mm: page_alloc: speed up fallbacks in rmqueue_bulk()

Caution: This is an external email. Please take care when clicking links or opening attachments. When in doubt, report the message using the 'Report this email' button

The test robot identified c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest buddy") as the root cause of a 56.4% regression in vm-scalability::lru-file-mmap-read.

Carlos reports an earlier patch, c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block conversion"), as the root cause for a regression in worst-case zone->lock+irqoff hold times.

Both of these patches modify the page allocator's fallback path to be less greedy in an effort to stave off fragmentation. The flip side of this is that fallbacks are also less productive each time around, which means the fallback search can run much more frequently.

Carlos' traces point to rmqueue_bulk() specifically, which tries to refill the percpu cache by allocating a large batch of pages in a loop. It highlights how once the native freelists are exhausted, the fallback code first scans orders top-down for whole blocks to claim, then falls back to a bottom-up search for the smallest buddy to steal.
For the next batch page, it goes through the same thing again.

This can be made more efficient. Since rmqueue_bulk() holds the zone->lock over the entire batch, the freelists are not subject to outside changes; when the search for a block to claim has already failed, there is no point in trying again for the next page.

Modify __rmqueue() to remember the last successful fallback mode, and restart directly from there on the next rmqueue_bulk() iteration.

Oliver confirms that this improves beyond the regression that the test robot reported against c2f6ea38fc1b:

commit:
f3b92176f4 ("tools/selftests: add guard region test for /proc/$pid/pagemap") c2f6ea38fc ("mm: page_alloc: don't steal single pages from biggest buddy") acc4d5ff0b ("Merge tag 'net-6.15-rc0' of
git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net")
2c847f27c3 ("mm: page_alloc: speed up fallbacks in rmqueue_bulk()") <---
your patch

f3b92176f4f7100f c2f6ea38fc1b640aa7a2e155cc1
acc4d5ff0b61eb1715c498b6536 2c847f27c37da65a93d23c237c5
---------------- --------------------------- --------------------------- ---------------------------
%stddev %change %stddev %change
%stddev %change %stddev
\ | \ |
\ | \
25525364 ± 3% -56.4% 11135467 -57.8%
10779336 +31.6% 33581409
vm-scalability.throughput

Carlos confirms that worst-case times are almost fully recovered compared to before the earlier culprit patch:

2dd482ba627d (before freelist hygiene): 1ms
c0cd6f557b90 (after freelist hygiene): 90ms
next-20250319 (steal smallest buddy): 280ms
this patch : 8ms

Reported-by kernel test robot <[email protected]>

Reported-by Carlos Song <[email protected]>

Tested-by kernel test robot <[email protected]>

Fixes c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block

conversion")

Fixes c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest

buddy")
Closes:
https://lore.kern/
el.org%2Foe-lkp%2F202503271547.fc08b188-lkp%40intel.com&data=05%7C02 %7Ccarlos.song%40nxp.com%7C3325bfa02b7942cca36508dd75fe4a3d%7C686 ea1d3bc2b4c6fa92cd99c5c301635%7C0%7C0%7C638796457225141027%7CUn known%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCI sIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdat a=gl5xQ8OLJNIccLDsYgVejUC%2B9ZQrxmt%2FxkfQXsmDuNY%3D&reserved=0

Cc [email protected] # 6.10+

Signed-off-by Johannes Weiner <[email protected]>

---
 mm/page_alloc.c | 100 +++++++++++++++++++++++++++++++++++-------------
 1 file changed, 74 insertions(+), 26 deletions(-)

mm/page_alloc.c index renamed from mm/page_alloc.c +0 -0

f51aa6051a99..03b0d45ed45a 100644

mm/page_alloc.c +4 -3

@@ -2194,11 +2194,11 @@ try_to_claim_block(struct zone *zone, struct page
 *page,
  * The use of signed ints for order and current_order is a deliberate
  * deviation from the rest of this file, to make the for loop
  * condition simpler.
- *
- * Return the stolen page, or NULL if none can be found.
  */
+
+/* Try to claim a whole foreign block, take a page, expand the
+remainder */
 static __always_inline struct page *
-__rmqueue_fallback(struct zone *zone, int order, int start_migratetype,
+__rmqueue_claim(struct zone *zone, int order, int start_migratetype,
                                                unsigned int

alloc_flags)  {
        struct free_area *area;

mm/page_alloc.c +16 -5

@@ -2236,14 +2236,26 @@ __rmqueue_fallback(struct zone *zone, int order,
 int start_migratetype,
                page = try_to_claim_block(zone, page, current_order, order,
                                          start_migratetype,
 fallback_mt,
                                          alloc_flags);
-               if (page)
-                       goto got_one;
+               if (page) {
+                       trace_mm_page_alloc_extfrag(page, order,
 current_order,
+
 start_migratetype, fallback_mt);
+                       return page;
+               }
        }
 
-       if (alloc_flags & ALLOC_NOFRAGMENT)
-               return NULL;
+       return NULL;
+}
+
+/* Try to steal a single page from a foreign block */ static
+__always_inline struct page * __rmqueue_steal(struct zone *zone, int
+order, int start_migratetype) {
+       struct free_area *area;
+       int current_order;
+       struct page *page;
+       int fallback_mt;
+       bool claim_block;
 
-       /* No luck claiming pageblock. Find the smallest fallback page */
        for (current_order = order; current_order < NR_PAGE_ORDERS;

current_order++) {
area = &(zone->free_area[current_order]); fallback_mt = find_suitable_fallback(area, current_order,

mm/page_alloc.c +10 -8

@@ -2253,25 +2265,28 @@ __rmqueue_fallback(struct zone *zone, int order,
 int start_migratetype,
 
                page = get_page_from_free_area(area, fallback_mt);
                page_del_and_expand(zone, page, order, current_order,
 fallback_mt);
-               goto got_one;
+               trace_mm_page_alloc_extfrag(page, order, current_order,
+                                           start_migratetype,
 fallback_mt);
+               return page;
        }
 
        return NULL;
-
-got_one:
-       trace_mm_page_alloc_extfrag(page, order, current_order,
-               start_migratetype, fallback_mt);
-
-       return page;
 }
 
+enum rmqueue_mode {
+       RMQUEUE_NORMAL,
+       RMQUEUE_CMA,
+       RMQUEUE_CLAIM,
+       RMQUEUE_STEAL,
+};
+
 /*
  * Do the hard work of removing an element from the buddy allocator.
  * Call me with the zone->lock already held.
  */
 static __always_inline struct page *
 __rmqueue(struct zone *zone, unsigned int order, int migratetype,
-                                               unsigned int

alloc_flags)

mm/page_alloc.c +27 -7

+         unsigned int alloc_flags, enum rmqueue_mode *mode)
 {
        struct page *page;

@@ -2290,16 +2305,47 @@ __rmqueue(struct zone *zone, unsigned int order,
 int migratetype,
                }
        }
 
-       page = __rmqueue_smallest(zone, order, migratetype);
-       if (unlikely(!page)) {
-               if (alloc_flags & ALLOC_CMA)
+       /*
+        * Try the different freelists, native then foreign.
+        *
+        * The fallback logic is expensive and rmqueue_bulk() calls in
+        * a loop with the zone->lock held, meaning the freelists are
+        * not subject to any outside changes. Remember in *mode where
+        * we found pay dirt, to save us the search on the next call.
+        */
+       switch (*mode) {
+       case RMQUEUE_NORMAL:
+               page = __rmqueue_smallest(zone, order, migratetype);
+               if (page)
+                       return page;
+               fallthrough;
+       case RMQUEUE_CMA:
+               if (alloc_flags & ALLOC_CMA) {
                        page = __rmqueue_cma_fallback(zone, order);
-
-               if (!page)
-                       page = __rmqueue_fallback(zone, order,
 migratetype,
-                                                 alloc_flags);
+                       if (page) {
+                               *mode = RMQUEUE_CMA;
+                               return page;
+                       }
+               }
+               fallthrough;
+       case RMQUEUE_CLAIM:
+               page = __rmqueue_claim(zone, order, migratetype,
 alloc_flags);
+               if (page) {
+                       /* Replenished native freelist, back to normal

mode */

mm/page_alloc.c +7 -0

+                       *mode = RMQUEUE_NORMAL;
+                       return page;
+               }
+               fallthrough;
+       case RMQUEUE_STEAL:
+               if (!(alloc_flags & ALLOC_NOFRAGMENT)) {
+                       page = __rmqueue_steal(zone, order,

migratetype);

mm/page_alloc.c +8 -2

+                       if (page) {
+                               *mode = RMQUEUE_STEAL;
+                               return page;
+                       }
+               }
        }
-       return page;
+       return NULL;
 }
 
 /*

@@ -2311,6 +2357,7 @@ static int rmqueue_bulk(struct zone *zone, unsigned
 int order,
                        unsigned long count, struct list_head *list,
                        int migratetype, unsigned int alloc_flags)  {
+       enum rmqueue_mode rmqm = RMQUEUE_NORMAL;
        unsigned long flags;
        int i;
 

@@ -2321,7 +2368,7 @@ static int rmqueue_bulk(struct zone *zone, unsigned
 int order,
        }
        for (i = 0; i < count; ++i) {
                struct page *page = __rmqueue(zone, order, migratetype,
-
 alloc_flags);
+                                             alloc_flags, &rmqm);
                if (unlikely(page == NULL))

                        break;

mm/page_alloc.c +3 -2

@@ -2934,6 +2981,7 @@ struct page *rmqueue_buddy(struct zone
 *preferred_zone, struct zone *zone,  {
        struct page *page;
        unsigned long flags;
+       enum rmqueue_mode rmqm = RMQUEUE_NORMAL;
 
        do {
                page = NULL;

@@ -2945,7 +2993,7 @@ struct page *rmqueue_buddy(struct zone
 *preferred_zone, struct zone *zone,
                if (alloc_flags & ALLOC_HIGHATOMIC)
                        page = __rmqueue_smallest(zone, order,
 MIGRATE_HIGHATOMIC);
                if (!page) {
-                       page = __rmqueue(zone, order, migratetype,
 alloc_flags);
+                       page = __rmqueue(zone, order, migratetype,
+ alloc_flags, &rmqm);
 
                        /*
                         * If the allocation fails, allow OOM handling and
--

2.49.0

The test robot identified c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest buddy") as the root cause of a 56.4% regression in vm-scalability::lru-file-mmap-read.

Carlos reports an earlier patch, c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block conversion"), as the root cause for a regression in worst-case zone->lock+irqoff hold times.

Both of these patches modify the page allocator's fallback path to be less greedy in an effort to stave off fragmentation. The flip side of this is that fallbacks are also less productive each time around, which means the fallback search can run much more frequently.

Carlos' traces point to rmqueue_bulk() specifically, which tries to refill the percpu cache by allocating a large batch of pages in a loop. It highlights how once the native freelists are exhausted, the fallback code first scans orders top-down for whole blocks to claim, then falls back to a bottom-up search for the smallest buddy to steal. For the next batch page, it goes through the same thing again.

This can be made more efficient. Since rmqueue_bulk() holds the zone->lock over the entire batch, the freelists are not subject to outside changes; when the search for a block to claim has already failed, there is no point in trying again for the next page.

Modify __rmqueue() to remember the last successful fallback mode, and restart directly from there on the next rmqueue_bulk() iteration.

Oliver confirms that this improves beyond the regression that the test robot reported against c2f6ea38fc1b:

commit:
f3b92176f4 ("tools/selftests: add guard region test for /proc/$pid/pagemap") c2f6ea38fc ("mm: page_alloc: don't steal single pages from biggest buddy") acc4d5ff0b ("Merge tag 'net-6.15-rc0' of git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net")
2c847f27c3 ("mm: page_alloc: speed up fallbacks in rmqueue_bulk()") <--- your patch

f3b92176f4f7100f c2f6ea38fc1b640aa7a2e155cc1 acc4d5ff0b61eb1715c498b6536 2c847f27c37da65a93d23c237c5 ---------------- --------------------------- --------------------------- ---------------------------
%stddev %change %stddev %change %stddev %change %stddev
\ | \ | \ | \
25525364 ± 3% -56.4% 11135467 -57.8% 10779336 +31.6% 33581409 vm-scalability.throughput

Carlos confirms that worst-case times are almost fully recovered compared to before the earlier culprit patch:

2dd482ba627d (before freelist hygiene): 1ms
c0cd6f557b90 (after freelist hygiene): 90ms
next-20250319 (steal smallest buddy): 280ms
this patch : 8ms

Reported-by kernel test robot <[email protected]>

Reported-by Carlos Song <[email protected]>

Tested-by kernel test robot <[email protected]>

Fixes c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block conversion")

Fixes c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest buddy")

Closes https://lore.kernel.org/oe-lkp/[email protected] open here

Cc [email protected] # 6.10+

Signed-off-by Johannes Weiner <[email protected]>

The test robot identified c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest buddy") as the root cause of a 56.4% regression in vm-scalability::lru-file-mmap-read.

Carlos reports an earlier patch, c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block conversion"), as the root cause for a regression in worst-case zone->lock+irqoff hold times.

Both of these patches modify the page allocator's fallback path to be less greedy in an effort to stave off fragmentation. The flip side of this is that fallbacks are also less productive each time around, which means the fallback search can run much more frequently.

Carlos' traces point to rmqueue_bulk() specifically, which tries to refill the percpu cache by allocating a large batch of pages in a loop. It highlights how once the native freelists are exhausted, the fallback code first scans orders top-down for whole blocks to claim, then falls back to a bottom-up search for the smallest buddy to steal. For the next batch page, it goes through the same thing again.

This can be made more efficient. Since rmqueue_bulk() holds the zone->lock over the entire batch, the freelists are not subject to outside changes; when the search for a block to claim has already failed, there is no point in trying again for the next page.

Modify __rmqueue() to remember the last successful fallback mode, and restart directly from there on the next rmqueue_bulk() iteration.

Oliver confirms that this improves beyond the regression that the test robot reported against c2f6ea38fc1b:

commit:
f3b92176f4 ("tools/selftests: add guard region test for /proc/$pid/pagemap") c2f6ea38fc ("mm: page_alloc: don't steal single pages from biggest buddy") acc4d5ff0b ("Merge tag 'net-6.15-rc0' of git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net")
2c847f27c3 ("mm: page_alloc: speed up fallbacks in rmqueue_bulk()") <--- your patch

f3b92176f4f7100f c2f6ea38fc1b640aa7a2e155cc1 acc4d5ff0b61eb1715c498b6536 2c847f27c37da65a93d23c237c5 ---------------- --------------------------- --------------------------- ---------------------------
%stddev %change %stddev %change %stddev %change %stddev
\ | \ | \ | \
25525364 ± 3% -56.4% 11135467 -57.8% 10779336 +31.6% 33581409 vm-scalability.throughput

Carlos confirms that worst-case times are almost fully recovered compared to before the earlier culprit patch:

2dd482ba627d (before freelist hygiene): 1ms
c0cd6f557b90 (after freelist hygiene): 90ms
next-20250319 (steal smallest buddy): 280ms
this patch : 8ms

Reported-by kernel test robot <[email protected]>

Reported-by Carlos Song <[email protected]>

Tested-by kernel test robot <[email protected]>

Fixes c0cd6f557b90 ("mm: page_alloc: fix freelist movement during block conversion")

Fixes c2f6ea38fc1b ("mm: page_alloc: don't steal single pages from biggest buddy")

Closes https://lore.kernel.org/oe-lkp/[email protected] open here

Cc [email protected] # 6.10+

Signed-off-by Johannes Weiner <[email protected]>

---