mm/page_alloc: find_large_buddy() from start_pfn aligned order
Subsystems (2)
PATCH 1/1 mm/page_alloc: find_large_buddy() from start_pfn aligned order
We iterate pfn from order 0 to MAX_PAGE_ORDER aligned to find large buddy. While if the order is less than start_pfn aligned order, we would get the same pfn and do the same check again.
Iterate from start_pfn aligned order to reduce duplicated work.
---
I build this and run, but not sure how fully test this.
--- mm/page_alloc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
mm/page_alloc.c +1 -1
@@ -2033,7 +2033,7 @@ static int move_freepages_block(struct zone *zone, struct page *page,/* Look for a buddy that straddles start_pfn */ static unsigned long find_large_buddy (unsigned long start_pfn) { -int order =0 ; +int order = start_pfn ?__ffs (start_pfn) :MAX_PAGE_ORDER ;struct page *page;unsigned long pfn = start_pfn;
Signature · 1 line
2.34.1
Zi Yan
reviewerQuoted 23 lines · Wei Yang
We iterate pfn from order 0 to
MAX_PAGE_ORDERaligned to find large buddy. While if the order is less thanstart_pfnaligned order, we would get the same pfn and do the same check again.Iterate from
start_pfnaligned order to reduce duplicated work.Signed-off-by Wei Yang <[email protected]>Cc Johannes Weiner <[email protected]>Cc Zi Yan <[email protected]>Cc Vlastimil Babka <[email protected]>Cc David Hildenbrand <[email protected]>---
I build this and run, but not sure how fully test this.--- mm/page_alloc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)mm/page_alloc.c +0
-0
mm/page_alloc.c static int move_freepages_block(struct zone *zone, struct page *page, · line 2038
Quoted 7 lines
mm/page_alloc.c +1
-1@@ -2033,7 +2033,7 @@ static int move_freepages_block(struct zone *zone, struct page *page,/* Look for a buddy that straddles start_pfn */ static unsigned long find_large_buddy (unsigned long start_pfn) { -int order =0 ; +int order = start_pfn ?__ffs (start_pfn) :MAX_PAGE_ORDER ;struct page *page;unsigned long pfn = start_pfn;
I think it is right, but the code is very subtle and hard to understand after the change. It is better to add comment to explain it.
Paste the code below for more context:
while (!PageBuddy(page = pfn_to_page(pfn))) {
/* Nothing found */
if (++order > MAX_PAGE_ORDER)
return start_pfn;
pfn &= ~0UL << order;
}The code tries to find a PageBuddy starting from start_pfn starting from order=0. When entering the while loop, it means PageBuddy cannot be order-0 and ++order increases the order by 1. Your change fast forwards the process based on start_pfn. If start_pfn is not an order-0 page, based on first set bit in start_pfn and how buddy page is chosen, the next possible PageBuddy order can only be __ffs(start_pfn) + 1. Your code starts order at __ffs(start_pfn) and it works because "if (++order > MAX_PAGE_ORDER)" increases order to __ffs(start_pfn) + 1.
Can you add a comment on your "int order = ..."? Something like:
If start_pfn is not an order-0 PageBuddy, next PageBuddy containing start_pfn has minimal order of __ffs(start_pfn) + 1. Fastforward order to __ffs(start_pfn) to remove unnecessary work in the while below.
Feel free to reword the above.
With the added comment, feel free to add Reviewed-by: Zi Yan <[email protected]>
BTW, I also notice that when start_pfn is an order-0 PageBuddy, the "if (pfn + (1 << buddy_order(page)) > start_pfn)" check below would be true even if there is no buddy straddles start_pfn, although "return pfn" gives the same results as "return start_pfn" (no straddle). The original code before the addition of find_large_buddy() (commit fd919a85cd55 ("mm:page_isolation: prepare for hygienic freelists")) checks start_pfn == pfn before the straddle check, so the correct code should check start_pfn == pfn and return early. But since current code is functionally equivalent. Maybe adding a comment about it would be sufficient. Something like:
When the found buddy order is 0, the check would give false positive, but the returned result is still correct, since pfn is the same as start_pfn.
--
Best Regards,
Yan, Zi
Quoted 20 lines · Zi Yan
Quoted 18 lines · Wei Yang
We iterate pfn from order 0 to
MAX_PAGE_ORDERaligned to find large buddy. While if the order is less thanstart_pfnaligned order, we would get the same pfn and do the same check again.Iterate from
start_pfnaligned order to reduce duplicated work.Signed-off-by Wei Yang <[email protected]>Cc Johannes Weiner <[email protected]>Cc Zi Yan <[email protected]>Cc Vlastimil Babka <[email protected]>Cc David Hildenbrand <[email protected]>---
I build this and run, but not sure how fully test this.--- mm/page_alloc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
Quoted 13 lines
mm/page_alloc.c static int move_freepages_block(struct zone *zone, struct page *page, · line 2038
Quoted 12 lines
mm/page_alloc.c +1
-1@@ -2033,7 +2033,7 @@ static int move_freepages_block(struct zone *zone, struct page *page,/* Look for a buddy that straddles start_pfn */ static unsigned long find_large_buddy (unsigned long start_pfn) { -int order =0 ; +int order = start_pfn ?__ffs (start_pfn) :MAX_PAGE_ORDER ;struct page *page;unsigned long pfn = start_pfn;
Hi, Zi Yan
Thanks for the review.
Quoted 2 lines
I think it is right, but the code is very subtle and hard to understand after the change. It is better to add comment to explain it.
One thing I want to point out is in __move_freepages_block_isolate(), find_large_buddy() is always given a pageblock aligned start_pfn. This means if start_pfn is not a free page, it would always try 10 times until give up.
Quoted 21 lines
Paste the code below for more context:
while (!PageBuddy(page = pfn_to_page(pfn))) { /* Nothing found */ if (++order > MAX_PAGE_ORDER) return start_pfn; pfn &= ~0UL << order; }The code tries to find a PageBuddy starting from
start_pfnstarting from order=0. When entering the while loop, it means PageBuddy cannot be order-0 and ++order increases the order by 1. Your change fast forwards the process based onstart_pfn. Ifstart_pfnis not an order-0 page, based on first set bit instart_pfnand how buddy page is chosen, the next possible PageBuddy order can only be__ffs(start_pfn)+ 1. Your code starts order at__ffs(start_pfn)and it works because "if (++order >MAX_PAGE_ORDER)" increases order to__ffs(start_pfn)+ 1.
Quoted 5 lines
Can you add a comment on your "int order = ..."? Something like:
If
start_pfnis not an order-0 PageBuddy, next PageBuddy containingstart_pfnhas minimal order of__ffs(start_pfn)+ 1. Fastforward order to__ffs(start_pfn)to remove unnecessary work in the while below.
Sure, I would add a comment above the assignment.
But in my mind, we are not farst forward order, but start check from order of __ffs(start_pfn).
How about: (not good at commento)
/* * We start find large buddy from start_pfn order, since a * !PageBuddy() means all lower order page is !PageBuddy(). */
Quoted 6 lines
Feel free to reword the above.
With the added comment, feel free to add Reviewed-by: Zi Yan <[email protected]>
Quoted 9 lines
BTW, I also notice that when
start_pfnis an order-0 PageBuddy, the "if (pfn + (1 <<buddy_order(page)) >start_pfn)" check below would be true even if there is no buddy straddlesstart_pfn, although "return pfn" gives the same results as "returnstart_pfn" (no straddle). The original code before the addition offind_large_buddy()(commitfd919a85cd55("mm:page_isolation: prepare for hygienic freelists")) checksstart_pfn== pfn before the straddle check, so the correct code should checkstart_pfn== pfn and return early. But since current code is functionally equivalent. Maybe adding a comment about it would be sufficient. Something like:
The comment above this function says "a buddy that straddles start_pfn", this looks good to me. An order-0 page that start from start_pfn also means straddle start_pfn.
This may differ from original logic, but seems not wrong.
Quoted 4 lines
When the found buddy order is 0, the check would give false positive, but the returned result is still correct, since pfn is the same as
start_pfn.
I prefer not adding this.
Quoted 5 lines
--
Best Regards,
Yan, Zi
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 56 lines · Wei Yang
Quoted 14 lines · Zi Yan
Quoted 12 lines · Wei Yang
We iterate pfn from order 0 to
MAX_PAGE_ORDERaligned to find large buddy. While if the order is less thanstart_pfnaligned order, we would get the same pfn and do the same check again.Iterate from
start_pfnaligned order to reduce duplicated work.Signed-off-by Wei Yang <[email protected]>Cc Johannes Weiner <[email protected]>Cc Zi Yan <[email protected]>Cc Vlastimil Babka <[email protected]>Cc David Hildenbrand <[email protected]>Quoted 3 lines
Quoted 1 line
---
I think it is right, but the code is very subtle and hard to understand after the change. It is better to add comment to explain it.
One thing I want to point out is in
__move_freepages_block_isolate(),find_large_buddy()is always given a pageblock alignedstart_pfn. This means ifstart_pfnis not a free page, it would always try 10 times until give up.Quoted 21 lines
Paste the code below for more context:
while (!PageBuddy(page = pfn_to_page(pfn))) { /* Nothing found */ if (++order > MAX_PAGE_ORDER) return start_pfn; pfn &= ~0UL << order; }The code tries to find a PageBuddy starting from
start_pfnstarting from order=0. When entering the while loop, it means PageBuddy cannot be order-0 and ++order increases the order by 1. Your change fast forwards the process based onstart_pfn. Ifstart_pfnis not an order-0 page, based on first set bit instart_pfnand how buddy page is chosen, the next possible PageBuddy order can only be__ffs(start_pfn)+ 1. Your code starts order at__ffs(start_pfn)and it works because "if (++order >MAX_PAGE_ORDER)" increases order to__ffs(start_pfn)+ 1.Quoted 5 lines
Can you add a comment on your "int order = ..."? Something like:
If
start_pfnis not an order-0 PageBuddy, next PageBuddy containingstart_pfnhas minimal order of__ffs(start_pfn)+ 1. Fastforward order to__ffs(start_pfn)to remove unnecessary work in the while below.Sure, I would add a comment above the assignment.
But in my mind, we are not farst forward order, but start check from order of
__ffs(start_pfn).
Quoted 6 lines
How about: (not good at commento)
/* * We start find large buddy from start_pfn order, since a * !PageBuddy() means all lower order page is !PageBuddy(). */
Personally, the way Zi worded it makes more sense to me. Maybe replacing the second sentence with your comment is fine, but I think Zi's first sentence provides important context in a clear way.
Quoted 59 lines · Vishal Moola (Oracle)
Quoted 58 lines · Wei Yang
Quoted 14 lines · Zi Yan
Quoted 12 lines · Wei Yang
We iterate pfn from order 0 to
MAX_PAGE_ORDERaligned to find large buddy. While if the order is less thanstart_pfnaligned order, we would get the same pfn and do the same check again.Iterate from
start_pfnaligned order to reduce duplicated work.Signed-off-by Wei Yang <[email protected]>Cc Johannes Weiner <[email protected]>Cc Zi Yan <[email protected]>Cc Vlastimil Babka <[email protected]>Cc David Hildenbrand <[email protected]>Quoted 3 lines
Quoted 1 line
---
I think it is right, but the code is very subtle and hard to understand after the change. It is better to add comment to explain it.
One thing I want to point out is in
__move_freepages_block_isolate(),find_large_buddy()is always given a pageblock alignedstart_pfn. This means ifstart_pfnis not a free page, it would always try 10 times until give up.Quoted 21 lines
Paste the code below for more context:
while (!PageBuddy(page = pfn_to_page(pfn))) { /* Nothing found */ if (++order > MAX_PAGE_ORDER) return start_pfn; pfn &= ~0UL << order; }The code tries to find a PageBuddy starting from
start_pfnstarting from order=0. When entering the while loop, it means PageBuddy cannot be order-0 and ++order increases the order by 1. Your change fast forwards the process based onstart_pfn. Ifstart_pfnis not an order-0 page, based on first set bit instart_pfnand how buddy page is chosen, the next possible PageBuddy order can only be__ffs(start_pfn)+ 1. Your code starts order at__ffs(start_pfn)and it works because "if (++order >MAX_PAGE_ORDER)" increases order to__ffs(start_pfn)+ 1.Quoted 5 lines
Can you add a comment on your "int order = ..."? Something like:
If
start_pfnis not an order-0 PageBuddy, next PageBuddy containingstart_pfnhas minimal order of__ffs(start_pfn)+ 1. Fastforward order to__ffs(start_pfn)to remove unnecessary work in the while below.Sure, I would add a comment above the assignment.
But in my mind, we are not farst forward order, but start check from order of
__ffs(start_pfn).How about: (not good at commento)
Quoted 8 lines
Quoted 4 lines
/* * We start find large buddy from start_pfn order, since a * !PageBuddy() means all lower order page is !PageBuddy(). */Personally, the way Zi worded it makes more sense to me. Maybe replacing the second sentence with your comment is fine, but I think Zi's first sentence provides important context in a clear way.
Hi, Vishal
Thanks for your comment. I am ok with it. Let's see Zi's opnion. And I will send a new version. :-)
Signature · 2 lines
Wei Yang Help you, Help me
Zi Yan
reviewerQuoted 37 lines · Wei Yang
Quoted 20 lines · Zi Yan
Quoted 18 lines · Wei Yang
We iterate pfn from order 0 to
MAX_PAGE_ORDERaligned to find large buddy. While if the order is less thanstart_pfnaligned order, we would get the same pfn and do the same check again.Iterate from
start_pfnaligned order to reduce duplicated work.Signed-off-by Wei Yang <[email protected]>Cc Johannes Weiner <[email protected]>Cc Zi Yan <[email protected]>Cc Vlastimil Babka <[email protected]>Cc David Hildenbrand <[email protected]>---
I build this and run, but not sure how fully test this.--- mm/page_alloc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)Quoted 13 lines
mm/page_alloc.c static int move_freepages_block(struct zone *zone, struct page *page, · line 2038
Quoted 12 lines
mm/page_alloc.c +1
-1@@ -2033,7 +2033,7 @@ static int move_freepages_block(struct zone *zone, struct page *page,/* Look for a buddy that straddles start_pfn */ static unsigned long find_large_buddy (unsigned long start_pfn) { -int order =0 ; +int order = start_pfn ?__ffs (start_pfn) :MAX_PAGE_ORDER ;struct page *page;unsigned long pfn = start_pfn;Hi, Zi Yan
Quoted 8 lines
Thanks for the review.
Quoted 2 lines
I think it is right, but the code is very subtle and hard to understand after the change. It is better to add comment to explain it.
One thing I want to point out is in
__move_freepages_block_isolate(),find_large_buddy()is always given a pageblock alignedstart_pfn. This means ifstart_pfnis not a free page, it would always try 10 times until give up.
find_large_buddy() is used to deal with free pages, so start_pfn is likely to be a free page.
Quoted 24 lines
Quoted 24 lines
Paste the code below for more context:
while (!PageBuddy(page = pfn_to_page(pfn))) { /* Nothing found */ if (++order > MAX_PAGE_ORDER) return start_pfn; pfn &= ~0UL << order; }The code tries to find a PageBuddy starting from
start_pfnstarting from order=0. When entering the while loop, it means PageBuddy cannot be order-0 and ++order increases the order by 1. Your change fast forwards the process based onstart_pfn. Ifstart_pfnis not an order-0 page, based on first set bit instart_pfnand how buddy page is chosen, the next possible PageBuddy order can only be__ffs(start_pfn)+ 1. Your code starts order at__ffs(start_pfn)and it works because "if (++order >MAX_PAGE_ORDER)" increases order to__ffs(start_pfn)+ 1.Can you add a comment on your "int order = ..."? Something like:
Quoted 8 lines
Quoted 3 lines
If
start_pfnis not an order-0 PageBuddy, next PageBuddy containingstart_pfnhas minimal order of__ffs(start_pfn)+ 1. Fastforward order to__ffs(start_pfn)to remove unnecessary work in the while below.Sure, I would add a comment above the assignment.
But in my mind, we are not farst forward order, but start check from order of
__ffs(start_pfn).
Sure.
Quoted 6 lines
How about: (not good at commento)
/* * We start find large buddy from start_pfn order, since a
It is unclear what start_pfn order means.
Quoted 2 lines
* !PageBuddy() means all lower order page is !PageBuddy(). */
Here you assume start_pfn is not PageBuddy() already, but it can be an order-0 PageBuddy(). That is why my comment explicitly excluded the case to begin with.
How about?
If start_pfn is not an order-0 PageBuddy, next PageBuddy containing start_pfn has minimal order of __ffs(start_pfn) + 1. Start checking the order with __ffs(start_pfn). If start_pfn is order-0, the starting order does not matter.
Quoted 17 lines
Quoted 7 lines
Feel free to reword the above.
With the added comment, feel free to add Reviewed-by: Zi Yan <[email protected]>
Quoted 9 lines
BTW, I also notice that when
start_pfnis an order-0 PageBuddy, the "if (pfn + (1 <<buddy_order(page)) >start_pfn)" check below would be true even if there is no buddy straddlesstart_pfn, although "return pfn" gives the same results as "returnstart_pfn" (no straddle). The original code before the addition offind_large_buddy()(commitfd919a85cd55("mm:page_isolation: prepare for hygienic freelists")) checksstart_pfn== pfn before the straddle check, so the correct code should checkstart_pfn== pfn and return early. But since current code is functionally equivalent. Maybe adding a comment about it would be sufficient. Something like:
Quoted 5 lines
The comment above this function says "a buddy that straddles
start_pfn", this looks good to me. An order-0 page that start fromstart_pfnalso means straddlestart_pfn.This may differ from original logic, but seems not wrong.
Straddle means a buddy page has start_pfn in the middle and the caller in __move_freepages_block_isolate() needs to split the buddy page.
Quoted 7 lines
Quoted 5 lines
When the found buddy order is 0, the check would give false positive, but the returned result is still correct, since pfn is the same as
start_pfn.I prefer not adding this.
No strong opinion about it.
--
Best Regards,
Yan, Zi
Quoted 44 lines · Zi Yan
Quoted 42 lines · Wei Yang
Quoted 20 lines · Zi Yan
Quoted 18 lines · Wei Yang
We iterate pfn from order 0 to
MAX_PAGE_ORDERaligned to find large buddy. While if the order is less thanstart_pfnaligned order, we would get the same pfn and do the same check again.Iterate from
start_pfnaligned order to reduce duplicated work.Signed-off-by Wei Yang <[email protected]>Cc Johannes Weiner <[email protected]>Cc Zi Yan <[email protected]>Cc Vlastimil Babka <[email protected]>Cc David Hildenbrand <[email protected]>---
I build this and run, but not sure how fully test this.--- mm/page_alloc.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)Quoted 13 lines
mm/page_alloc.c static int move_freepages_block(struct zone *zone, struct page *page, · line 2038
Quoted 12 lines
mm/page_alloc.c +1
-1@@ -2033,7 +2033,7 @@ static int move_freepages_block(struct zone *zone, struct page *page,/* Look for a buddy that straddles start_pfn */ static unsigned long find_large_buddy (unsigned long start_pfn) { -int order =0 ; +int order = start_pfn ?__ffs (start_pfn) :MAX_PAGE_ORDER ;struct page *page;unsigned long pfn = start_pfn;Hi, Zi Yan
Thanks for the review.
Quoted 2 lines
I think it is right, but the code is very subtle and hard to understand after the change. It is better to add comment to explain it.
Quoted 7 lines
Quoted 3 lines
One thing I want to point out is in
__move_freepages_block_isolate(),find_large_buddy()is always given a pageblock alignedstart_pfn. This means ifstart_pfnis not a free page, it would always try 10 times until give up.
find_large_buddy()is used to deal with free pages, sostart_pfnis likely to be a free page.
I am not that familiar with the background, my question here.
I see the call flow is:
alloc_contig_pages_noprof()
__alloc_contig_pages(pfn, ) <-- start_pfn
start_isolate_page_range()
isolate_single_pageblock()
set_migratetype_isolate()
pageblock_isolate_and_move_free_pages()
find_large_buddy()
If my understanding is correct, the start_pfn comes from __alloc_contig_pages(), which is get from zone's pfn iteration.
I don't see it filter non-free page. So the possibility of free/non-free is equal to me.
Maybe I missed something?
[...]
Quoted 14 lines
Quoted 4 lines
How about: (not good at commento)
/* * We start find large buddy from start_pfn order, since aIt is unclear what
start_pfnorder means.Quoted 2 lines
* !PageBuddy() means all lower order page is !PageBuddy(). */Here you assume
start_pfnis notPageBuddy()already, but it can be an order-0PageBuddy(). That is why my comment explicitly excluded the case to begin with.
Quoted 6 lines
How about?
If
start_pfnis not an order-0 PageBuddy, next PageBuddy containingstart_pfnhas minimal order of__ffs(start_pfn)+ 1. Start checking the order with__ffs(start_pfn). Ifstart_pfnis order-0, the starting order does not matter.
Thanks, will use this one.
Quoted 17 lines
Quoted 17 lines
Quoted 16 lines
Feel free to reword the above.
With the added comment, feel free to add Reviewed-by: Zi Yan <[email protected]>
BTW, I also notice that when
start_pfnis an order-0 PageBuddy, the "if (pfn + (1 <<buddy_order(page)) >start_pfn)" check below would be true even if there is no buddy straddlesstart_pfn, although "return pfn" gives the same results as "returnstart_pfn" (no straddle). The original code before the addition offind_large_buddy()(commitfd919a85cd55("mm:page_isolation: prepare for hygienic freelists")) checksstart_pfn== pfn before the straddle check, so the correct code should checkstart_pfn== pfn and return early. But since current code is functionally equivalent. Maybe adding a comment about it would be sufficient. Something like:
Quoted 7 lines
Quoted 5 lines
The comment above this function says "a buddy that straddles
start_pfn", this looks good to me. An order-0 page that start fromstart_pfnalso means straddlestart_pfn.This may differ from original logic, but seems not wrong.
Straddle means a buddy page has
start_pfnin the middle and the caller
Ok, maybe the word "straddle" literally means it. If so, it really confuse.
Quoted 1 line
in
__move_freepages_block_isolate()needs to split the buddy page.
Do you mean if start_pfn is the head of a large buddy page, we don't split it in __move_freepages_block_isolate()?
Per my understanding, if this pageblock is a part of a large buddy, no matter it is at the beginning or end, we should split it.
Just want to confirm the behavior with you in case I misunderstand.
Signature · 2 lines
Wei Yang Help you, Help me
On Thu, Aug 28, 2025 at 11:02:33PM -0400, Zi Yan wrote:
[...]
Quoted 11 lines
BTW, I also notice that when
start_pfnis an order-0 PageBuddy, the "if (pfn + (1 <<buddy_order(page)) >start_pfn)" check below would be true even if there is no buddy straddlesstart_pfn, although "return pfn" gives the same results as "returnstart_pfn" (no straddle). The original code before the addition offind_large_buddy()(commitfd919a85cd55("mm:page_isolation: prepare for hygienic freelists")) checksstart_pfn== pfn before the straddle check, so the correct code should checkstart_pfn== pfn and return early. But since current code is functionally equivalent. Maybe adding a comment about it would be sufficient. Something like:
Quoted 2 lines
When the found buddy order is 0, the check would give false positive, but the returned result is still correct, since pfn is the same as
start_pfn.
Hm... found another thing.
In __move_freepages_block_isolate(), when checking "We're the starting block of a large buddy", variable "page" may not be the large buddy page we found from find_large_buddy(). Since prep_move_freepages_block() set start_pfn to pageblock_start_pfn(page_to_pfn(page)), which may be different.
Signature · 2 lines
Wei Yang Help you, Help me