Skip to contentSkip to conversation

mm: page_alloc: simplify pageblock migratetype check in __free_one_page().

PATCH Superseded Zi Yan 4 participants 8 messages Apr 1, 2022

Subsystems (3)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Zi Yan

author
#0 lore raw

PATCH v2 1/2 mm: page_alloc: simplify pageblock migratetype check in __free_one_page().

From: Zi Yan <[email protected]>

Move pageblock migratetype check code in the while loop to simplify the logic. It also saves redundant buddy page checking code.

---
 mm/page_alloc.c | 46 +++++++++++++++++-----------------------------
 1 file changed, 17 insertions(+), 29 deletions(-)
mm/page_alloc.c +17 -29
index 856473e54155..2ea106146686 100644
@@ -1054,7 +1054,6 @@ static inline void __free_one_page(struct page *page,
 		int migratetype, fpi_t fpi_flags)
 {
 	struct capture_control *capc = task_capc(zone);
-	unsigned int max_order = pageblock_order;
 	unsigned long buddy_pfn;
 	unsigned long combined_pfn;
 	struct page *buddy;
@@ -1070,8 +1069,7 @@ static inline void __free_one_page(struct page *page,
 	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
 	VM_BUG_ON_PAGE(bad_range(zone, page), page);
 
-continue_merging:
-	while (order < max_order) {
+	while (order < MAX_ORDER - 1) {
 		if (compaction_capture(capc, page, order, migratetype)) {
 			__mod_zone_freepage_state(zone, -(1 << order),
 								migratetype);
@@ -1082,6 +1080,22 @@ static inline void __free_one_page(struct page *page,
 
 		if (!page_is_buddy(page, buddy, order))
 			goto done_merging;
+
+		if (unlikely(order >= pageblock_order)) {
+			/*
+			 * We want to prevent merge between freepages on pageblock
+			 * without fallbacks and normal pageblock. Without this,
+			 * pageblock isolation could cause incorrect freepage or CMA
+			 * accounting or HIGHATOMIC accounting.
+			 */
+			int buddy_mt = get_pageblock_migratetype(buddy);
+
+			if (migratetype != buddy_mt
+					&& (!migratetype_is_mergeable(migratetype) ||
+						!migratetype_is_mergeable(buddy_mt)))
+				goto done_merging;
+		}
+
 		/*
 		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
 		 * merge with it and move up one order.
@@ -1095,32 +1109,6 @@ static inline void __free_one_page(struct page *page,
 		pfn = combined_pfn;
 		order++;
 	}
-	if (order < MAX_ORDER - 1) {
-		/* If we are here, it means order is >= pageblock_order.
-		 * We want to prevent merge between freepages on pageblock
-		 * without fallbacks and normal pageblock. Without this,
-		 * pageblock isolation could cause incorrect freepage or CMA
-		 * accounting or HIGHATOMIC accounting.
-		 *
-		 * We don't want to hit this code for the more frequent
-		 * low-order merging.
-		 */
-		int buddy_mt;
-
-		buddy_pfn = __find_buddy_pfn(pfn, order);
-		buddy = page + (buddy_pfn - pfn);
-
-		if (!page_is_buddy(page, buddy, order))
-			goto done_merging;
-		buddy_mt = get_pageblock_migratetype(buddy);
-
-		if (migratetype != buddy_mt
-				&& (!migratetype_is_mergeable(migratetype) ||
-					!migratetype_is_mergeable(buddy_mt)))
-			goto done_merging;
-		max_order = order + 1;
-		goto continue_merging;
-	}
 
 done_merging:
 	set_buddy_order(page, order);
Signature · 1 line
2.35.1
author
#1 lore raw

PATCH v2 2/2 mm: wrap __find_buddy_pfn() with a necessary buddy page validation.

From: Zi Yan <[email protected]>

Whenever the buddy of a page is found from __find_buddy_pfn(), page_is_buddy() should be used to check its validity. Add a helper function find_buddy_page_pfn() to find the buddy page and do the check together.

---
 mm/internal.h       | 23 +----------------
 mm/page_alloc.c     | 63 ++++++++++++++++++++++++++++++++++++++-------
 mm/page_isolation.c |  8 ++----
 3 files changed, 56 insertions(+), 38 deletions(-)
mm/internal.h +1 -22
index 876e66237c89..f43565ed5ff6 100644
@@ -211,28 +211,7 @@ struct alloc_context {
 	bool spread_dirty_pages;
 };
 
-/*
- * Locate the struct page for both the matching buddy in our
- * pair (buddy1) and the combined O(n+1) page they form (page).
- *
- * 1) Any buddy B1 will have an order O twin B2 which satisfies
- * the following equation:
- *     B2 = B1 ^ (1 << O)
- * For example, if the starting buddy (buddy2) is #8 its order
- * 1 buddy is #10:
- *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
- *
- * 2) Any buddy B will have an order O+1 parent P which
- * satisfies the following equation:
- *     P = B & ~(1 << O)
- *
- * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
- */
-static inline unsigned long
-__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
-{
-	return page_pfn ^ (1 << order);
-}
+extern struct page *find_buddy_page_pfn(struct page *page, unsigned int order);
 
 extern struct page *__pageblock_pfn_to_page(unsigned long start_pfn,
 				unsigned long end_pfn, struct zone *zone);
mm/page_alloc.c +53 -10

88 lines not on this page · raw message

mm/page_isolation.c +2 -6
index f67c4c70f17f..7326c9f57d55 100644
@@ -70,7 +70,6 @@ static void unset_migratetype_isolate(struct page *page, unsigned migratetype)
 	unsigned long flags, nr_pages;
 	bool isolated_page = false;
 	unsigned int order;
-	unsigned long pfn, buddy_pfn;
 	struct page *buddy;
 
 	zone = page_zone(page);
@@ -89,11 +88,8 @@ static void unset_migratetype_isolate(struct page *page, unsigned migratetype)
 	if (PageBuddy(page)) {
 		order = buddy_order(page);
 		if (order >= pageblock_order && order < MAX_ORDER - 1) {
-			pfn = page_to_pfn(page);
-			buddy_pfn = __find_buddy_pfn(pfn, order);
-			buddy = page + (buddy_pfn - pfn);
-
-			if (!is_migrate_isolate_page(buddy)) {
+			buddy = find_buddy_page_pfn(page, order);
+			if (buddy && !is_migrate_isolate_page(buddy)) {
 				isolated_page = !!__isolate_free_page(page, order);
 				/*
 				 * Isolating a free page in an isolated pageblock
Signature · 1 line
2.35.1
#2 lore raw

Re: [PATCH v2 2/2] mm: wrap __find_buddy_pfn() with a necessary buddy page validation.

Quoted 5 lines · Zi Yan

Whenever the buddy of a page is found from __find_buddy_pfn(), page_is_buddy() should be used to check its validity. Add a helper function find_buddy_page_pfn() to find the buddy page and do the check together.

Well, this certainly looks nicer, except now:

Quoted 1 line

+extern struct page *find_buddy_page_pfn(struct page *page, unsigned int order);

that 'pfn' no longer makes sense in the name, and

mm/page_alloc.c static inline void __free_one_page(struct page *page, · line 1125

Quoted 12 lines
mm/page_alloc.c +3 -3
@@ -1075,11 +1118,11 @@ static inline void __free_one_page(struct page *page,
                                                                migratetype);
                        return;
                }
-               buddy_pfn = __find_buddy_pfn(pfn, order);
-               buddy = page + (buddy_pfn - pfn);
 
-               if (!page_is_buddy(page, buddy, order))
+               buddy = find_buddy_page_pfn(page, order);
+               if (!buddy)
                        goto done_merging;
+               buddy_pfn = page_to_pfn(buddy);

This case now does two "page_to_pfn()" calls (one inside find_buddy_page_pfn(), and one explicitly on the buddy).

And those page_to_pfn() things can actually be fairly expensive. It *looks* like just a subtraction, but it's a pointer subtraction that can end up generating a divide by a non-power-of-two size.

NORMALLY we try very hard to make 'sizeof struct page' be exactly 8 words, but I do not believe this is actually guaranteed.

And yeah, the divide-by-a-constant can be turned into a multiply, but even that is not necessarily always cheap.

Now, two out of three use-cases didn't actually want the buddy_pfn(), but this one use-case does look like it might be performance-critical and a problem.

Linus

reviewer
#3 lore raw

Re: [PATCH v2 2/2] mm: wrap __find_buddy_pfn() with a necessary buddy page validation.

Quoted 36 lines · Linus Torvalds
Quoted 5 lines · Zi Yan

Whenever the buddy of a page is found from __find_buddy_pfn(), page_is_buddy() should be used to check its validity. Add a helper function find_buddy_page_pfn() to find the buddy page and do the check together.

Well, this certainly looks nicer, except now:

Quoted 1 line

+extern struct page *find_buddy_page_pfn(struct page *page, unsigned int order);

that 'pfn' no longer makes sense in the name, and

Review static inline void __free_one_page(struct page *page, · line 1125

Quoted 12 lines
(quoted diff) +3 -3
@@ -1075,11 +1118,11 @@ static inline void __free_one_page(struct page *page,
                                                                migratetype);
                        return;
                }
-               buddy_pfn = __find_buddy_pfn(pfn, order);
-               buddy = page + (buddy_pfn - pfn);
 
-               if (!page_is_buddy(page, buddy, order))
+               buddy = find_buddy_page_pfn(page, order);
+               if (!buddy)
                        goto done_merging;
+               buddy_pfn = page_to_pfn(buddy);

This case now does two "page_to_pfn()" calls (one inside find_buddy_page_pfn(), and one explicitly on the buddy).

And those page_to_pfn() things can actually be fairly expensive. It *looks* like just a subtraction, but it's a pointer subtraction that can end up generating a divide by a non-power-of-two size.

NORMALLY we try very hard to make 'sizeof struct page' be exactly 8 words, but I do not believe this is actually guaranteed.

Quoted 6 lines

And yeah, the divide-by-a-constant can be turned into a multiply, but even that is not necessarily always cheap.

Now, two out of three use-cases didn't actually want the buddy_pfn(), but this one use-case does look like it might be performance-critical and a problem.

Yeah, I should have listened to your initial suggestion. Thanks for the explanation.

How about the patch below? If it looks good, I will send v3.

mm/internal.h +2 -22
index 876e66237c89..754a666e5785 100644
@@ -211,28 +211,8 @@ struct alloc_context {
 	bool spread_dirty_pages;
 };
 
-/*
- * Locate the struct page for both the matching buddy in our
- * pair (buddy1) and the combined O(n+1) page they form (page).
- *
- * 1) Any buddy B1 will have an order O twin B2 which satisfies
- * the following equation:
- *     B2 = B1 ^ (1 << O)
- * For example, if the starting buddy (buddy2) is #8 its order
- * 1 buddy is #10:
- *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
- *
- * 2) Any buddy B will have an order O+1 parent P which
- * satisfies the following equation:
- *     P = B & ~(1 << O)
- *
- * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
- */
-static inline unsigned long
-__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
-{
-	return page_pfn ^ (1 << order);
-}
+extern struct page *find_buddy_page_pfn(struct page *page, unsigned long pfn,
+				unsigned int order, unsigned long *buddy_pfn);
 
 extern struct page *__pageblock_pfn_to_page(unsigned long start_pfn,
 				unsigned long end_pfn, struct zone *zone);
mm/page_alloc.c +58 -10

92 lines not on this page · raw message

mm/page_isolation.c +4 -6
index f67c4c70f17f..4fbd27ba91c6 100644
@@ -70,7 +70,7 @@ static void unset_migratetype_isolate(struct page *page, unsigned migratetype)
 	unsigned long flags, nr_pages;
 	bool isolated_page = false;
 	unsigned int order;
-	unsigned long pfn, buddy_pfn;
+	unsigned long buddy_pfn;
 	struct page *buddy;
 
 	zone = page_zone(page);
@@ -89,11 +89,9 @@ static void unset_migratetype_isolate(struct page *page, unsigned migratetype)
 	if (PageBuddy(page)) {
 		order = buddy_order(page);
 		if (order >= pageblock_order && order < MAX_ORDER - 1) {
-			pfn = page_to_pfn(page);
-			buddy_pfn = __find_buddy_pfn(pfn, order);
-			buddy = page + (buddy_pfn - pfn);
-
-			if (!is_migrate_isolate_page(buddy)) {
+			buddy = find_buddy_page_pfn(page, page_to_pfn(page),
+						    order, &buddy_pfn);
+			if (buddy && !is_migrate_isolate_page(buddy)) {
 				isolated_page = !!__isolate_free_page(page, order);
 				/*
 				 * Isolating a free page in an isolated pageblock

--
Best Regards,
Yan, Zi

#4 lore raw

Re: [PATCH v2 2/2] mm: wrap __find_buddy_pfn() with a necessary buddy page validation.

Quoted 2 lines · Zi Yan

How about the patch below? If it looks good, I will send v3.

I can't see anything worrisome, but by now I've looked at several versions and who knows what I'm missing.

Making it inline and allowing a NULL 'buddy_pfn' pointer for the cases that don't care might be an option, but I don't think it matters hugely.

Linus

reviewer
#5 lore raw

Re: [PATCH v2 2/2] mm: wrap __find_buddy_pfn() with a necessary buddy page validation.

Quoted 10 lines · Linus Torvalds
Quoted 2 lines · Zi Yan

How about the patch below? If it looks good, I will send v3.

I can't see anything worrisome, but by now I've looked at several versions and who knows what I'm missing.

Making it inline and allowing a NULL 'buddy_pfn' pointer for the cases that don't care might be an option, but I don't think it matters hugely.

What do you mean by inlining it? Moving the function and __find_buddy_pfn() to mm/internal.h and mark both inline?

Something like below to allow a NULL 'buddy_pfn'? buddy_pfn is needed to store the result of __find_buddy_pfn(). The code does not look as nice as before.

struct page *find_buddy_page_pfn(struct page *page, unsigned long pfn,
unsigned int order, unsigned long *buddy_pfn)

{
        struct page *buddy;

        if (buddy_pfn) {
                *buddy_pfn = __find_buddy_pfn(pfn, order);
                buddy = page + (*buddy_pfn - pfn);
        } else
                buddy = page + (__find_buddy_pfn(pfn, order) - pfn);

        if (page_is_buddy(page, buddy, order))
                return buddy;
        return NULL;
}

or

struct page *find_buddy_page_pfn(struct page *page, unsigned long pfn,
unsigned int order, unsigned long *buddy_pfn)

{
        struct page *buddy;
        unsigned long local_buddy_pfn = __find_buddy_pfn(pfn, order);

        buddy = page + (local_buddy_pfn - pfn);
        if (buddy_pfn)
                *buddy_pfn = local_buddy_pfn;

        if (page_is_buddy(page, buddy, order))
                return buddy;
        return NULL;
}

--
Best Regards,
Yan, Zi

#6 lore raw

Re: [PATCH v2 2/2] mm: wrap __find_buddy_pfn() with a necessary buddy page validation.

Quoted 9 lines · Zi Yan
Quoted 7 lines · Linus Torvalds
Quoted 2 lines · Zi Yan

How about the patch below? If it looks good, I will send v3.

I can't see anything worrisome, but by now I've looked at several versions and who knows what I'm missing.

Quoted 6 lines
Quoted 3 lines

Making it inline and allowing a NULL 'buddy_pfn' pointer for the cases that don't care might be an option, but I don't think it matters hugely.

What do you mean by inlining it? Moving the function and __find_buddy_pfn() to mm/internal.h and mark both inline?

I would prefer that for the sake of __free_one_page().

Quoted 24 lines

Something like below to allow a NULL 'buddy_pfn'? buddy_pfn is needed to store the result of __find_buddy_pfn(). The code does not look as nice as before.

struct page *find_buddy_page_pfn(struct page *page, unsigned long pfn,
unsigned int order, unsigned long *buddy_pfn)

{
        struct page *buddy;

        if (buddy_pfn) {
                *buddy_pfn = __find_buddy_pfn(pfn, order);
                buddy = page + (*buddy_pfn - pfn);
        } else
                buddy = page + (__find_buddy_pfn(pfn, order) - pfn);

        if (page_is_buddy(page, buddy, order))
                return buddy;
        return NULL;
}

or

struct page *find_buddy_page_pfn(struct page *page, unsigned long pfn,
unsigned int order, unsigned long *buddy_pfn)

Quoted 12 lines
{
        struct page *buddy;
        unsigned long local_buddy_pfn = __find_buddy_pfn(pfn, order);

        buddy = page + (local_buddy_pfn - pfn);
        if (buddy_pfn)
                *buddy_pfn = local_buddy_pfn;

        if (page_is_buddy(page, buddy, order))
                return buddy;
        return NULL;
}

The latter looks better. I would also use a name e.g. '__buddy_pfn' instead of 'local_'.

Thanks.

Quoted 4 lines

--
Best Regards,
Yan, Zi

Acked-by on v2 1/2
#7 lore raw
In reply to Zi Yan
Quoted 8 lines · Zi Yan

From: Zi Yan <[email protected]>

Move pageblock migratetype check code in the while loop to simplify the logic. It also saves redundant buddy page checking code.

Quoted 82 lines
---
 mm/page_alloc.c | 46 +++++++++++++++++-----------------------------
 1 file changed, 17 insertions(+), 29 deletions(-)
mm/page_alloc.c +17 -29
index 856473e54155..2ea106146686 100644
@@ -1054,7 +1054,6 @@ static inline void __free_one_page(struct page *page,
 		int migratetype, fpi_t fpi_flags)
 {
 	struct capture_control *capc = task_capc(zone);
-	unsigned int max_order = pageblock_order;
 	unsigned long buddy_pfn;
 	unsigned long combined_pfn;
 	struct page *buddy;
@@ -1070,8 +1069,7 @@ static inline void __free_one_page(struct page *page,
 	VM_BUG_ON_PAGE(pfn & ((1 << order) - 1), page);
 	VM_BUG_ON_PAGE(bad_range(zone, page), page);
 
-continue_merging:
-	while (order < max_order) {
+	while (order < MAX_ORDER - 1) {
 		if (compaction_capture(capc, page, order, migratetype)) {
 			__mod_zone_freepage_state(zone, -(1 << order),
 								migratetype);
@@ -1082,6 +1080,22 @@ static inline void __free_one_page(struct page *page,
 
 		if (!page_is_buddy(page, buddy, order))
 			goto done_merging;
+
+		if (unlikely(order >= pageblock_order)) {
+			/*
+			 * We want to prevent merge between freepages on pageblock
+			 * without fallbacks and normal pageblock. Without this,
+			 * pageblock isolation could cause incorrect freepage or CMA
+			 * accounting or HIGHATOMIC accounting.
+			 */
+			int buddy_mt = get_pageblock_migratetype(buddy);
+
+			if (migratetype != buddy_mt
+					&& (!migratetype_is_mergeable(migratetype) ||
+						!migratetype_is_mergeable(buddy_mt)))
+				goto done_merging;
+		}
+
 		/*
 		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
 		 * merge with it and move up one order.
@@ -1095,32 +1109,6 @@ static inline void __free_one_page(struct page *page,
 		pfn = combined_pfn;
 		order++;
 	}
-	if (order < MAX_ORDER - 1) {
-		/* If we are here, it means order is >= pageblock_order.
-		 * We want to prevent merge between freepages on pageblock
-		 * without fallbacks and normal pageblock. Without this,
-		 * pageblock isolation could cause incorrect freepage or CMA
-		 * accounting or HIGHATOMIC accounting.
-		 *
-		 * We don't want to hit this code for the more frequent
-		 * low-order merging.
-		 */
-		int buddy_mt;
-
-		buddy_pfn = __find_buddy_pfn(pfn, order);
-		buddy = page + (buddy_pfn - pfn);
-
-		if (!page_is_buddy(page, buddy, order))
-			goto done_merging;
-		buddy_mt = get_pageblock_migratetype(buddy);
-
-		if (migratetype != buddy_mt
-				&& (!migratetype_is_mergeable(migratetype) ||
-					!migratetype_is_mergeable(buddy_mt)))
-			goto done_merging;
-		max_order = order + 1;
-		goto continue_merging;
-	}
 
 done_merging:
 	set_buddy_order(page, order);