Skip to contentSkip to conversation

mm/page_alloc: optimize the loop in find_suitable_fallback()

PATCH In review Yajun Deng 2 participants 4 messages Feb 9, 2023

Subsystems (2)
lore
Share & tools
lore

Yajun Deng

author
#0 lore raw

PATCH 1/1 mm/page_alloc: optimize the loop in find_suitable_fallback()

There is no need to execute the next loop if it not return in the first loop. So add a break at the end of the loop.

There are only three rows in fallbacks, so reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES.

---
 mm/page_alloc.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)
mm/page_alloc.c +5 -6
index 1113483fa6c5..536e8d838fb5 100644
@@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
  *
  * The other migratetypes do not have fallbacks.
  */
-static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
+static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
 	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE   },
 	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
 	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE   },
@@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 	int i;
 	int fallback_mt;
 
-	if (area->nr_free == 0)
+	if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))
 		return -1;
 
 	*can_steal = false;
@@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 		if (can_steal_fallback(order, migratetype))
 			*can_steal = true;
 
-		if (!only_stealable)
-			return fallback_mt;
-
-		if (*can_steal)
+		if (!only_stealable || *can_steal)
 			return fallback_mt;
+		else
+			break;
 	}
 
 	return -1;
Signature · 1 line
2.25.1
Acked-by on v1 1/1
#1 lore raw
Quoted 7 lines · Yajun Deng

There is no need to execute the next loop if it not return in the first loop. So add a break at the end of the loop.

There are only three rows in fallbacks, so reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES.

Quoted 18 lines
---
 mm/page_alloc.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)
mm/page_alloc.c +1 -1
index 1113483fa6c5..536e8d838fb5 100644
@@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
  *
  * The other migratetypes do not have fallbacks.
  */
-static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
+static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
 	[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE   },
 	[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
 	[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE   },

mm/page_alloc.c int find_suitable_fallback(struct free_area *area, unsigned int order, · line 2864

Quoted 5 lines
mm/page_alloc.c +1 -1
@@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 	int i;
 	int fallback_mt;
 
-	if (area->nr_free == 0)
+	if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))

Just curious, did you the check for extra safety or did you find (by running or code inspection) that this can be indeed called with a non-mergeable migratetype, and cause out of bounds access of the shrinked fallbacks array?

BTW, I noticed the commment on migratetype_is_mergeable() contains:

"See fallbacks[MIGRATE_TYPES][3] in page_alloc.c. "

Should probably change it to e.g. "See fallbacks[][] array ..." so we don't have to keep it in exact sync...

Quoted 18 lines
mm/page_alloc.c +3 -4
 		return -1;
 
 	*can_steal = false;
@@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 		if (can_steal_fallback(order, migratetype))
 			*can_steal = true;
 
-		if (!only_stealable)
-			return fallback_mt;
-
-		if (*can_steal)
+		if (!only_stealable || *can_steal)
 			return fallback_mt;
+		else
+			break;
 	}
 
 	return -1;
author
#2 lore raw
Quoted 33 lines · Vlastimil Babka
Quoted 7 lines · Yajun Deng

There is no need to execute the next loop if it not return in the first loop. So add a break at the end of the loop.

There are only three rows in fallbacks, so reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES.

Quoted 21 lines

---
mm/page_alloc.c | 11 +++++------

1 file changed, 5 insertions(+), 6 deletions(-)
mm/page_alloc.c +1 -1
index 1113483fa6c5..536e8d838fb5 100644
@@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
 *
 * The other migratetypes do not have fallbacks.
 */
-static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
+static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
 [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE },
 [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
 [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE },
@@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 int i;
 int fallback_mt;
 
Quoted 7 lines

mm/page_alloc.c int find_suitable_fallback(struct free_area *area, unsigned int order, · line 2864

Quoted 2 lines
mm/page_alloc.c +1 -1
- if (area->nr_free == 0)
+ if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))

Just curious, did you the check for extra safety or did you find (by running or code inspection) that this can be indeed called with a non-mergeable migratetype, and cause out of bounds access of the shrinked fallbacks array?

No, I'm not sure if it is called with a non-mergeable migratetype. It is just for extra safety.

Quoted 7 lines

BTW, I noticed the commment on migratetype_is_mergeable() contains:

"See fallbacks[MIGRATE_TYPES][3] in page_alloc.c. "

Should probably change it to e.g. "See fallbacks[][] array ..." so we don't have to keep it in exact sync...

Yes, this comment should be changed.
So do I need to submit a v2 patch?

Quoted 18 lines
Quoted 18 lines
mm/page_alloc.c +3 -4
 return -1;
 
 *can_steal = false;
@@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 if (can_steal_fallback(order, migratetype))
 *can_steal = true;
 
- if (!only_stealable)
- return fallback_mt;
-
- if (*can_steal)
+ if (!only_stealable || *can_steal)
 return fallback_mt;
+ else
+ break;
 }
 
 return -1;
#3 lore raw
Quoted 43 lines · Yajun Deng
Quoted 33 lines · Vlastimil Babka
Quoted 7 lines · Yajun Deng

There is no need to execute the next loop if it not return in the first loop. So add a break at the end of the loop.

There are only three rows in fallbacks, so reduce the first index size from MIGRATE_TYPES to MIGRATE_PCPTYPES.

Quoted 21 lines

---
mm/page_alloc.c | 11 +++++------

1 file changed, 5 insertions(+), 6 deletions(-)
mm/page_alloc.c +1 -1
index 1113483fa6c5..536e8d838fb5 100644
@@ -2603,7 +2603,7 @@ struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
 *
 * The other migratetypes do not have fallbacks.
 */
-static int fallbacks[MIGRATE_TYPES][MIGRATE_PCPTYPES - 1] = {
+static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
 [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE },
 [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
 [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE },
@@ -2861,7 +2861,7 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 int i;
 int fallback_mt;
 
Quoted 7 lines

mm/page_alloc.c int find_suitable_fallback(struct free_area *area, unsigned int order, · line 2864

Quoted 2 lines
mm/page_alloc.c +1 -1
- if (area->nr_free == 0)
+ if (area->nr_free == 0 || !migratetype_is_mergeable(migratetype))

Just curious, did you the check for extra safety or did you find (by running or code inspection) that this can be indeed called with a non-mergeable migratetype, and cause out of bounds access of the shrinked fallbacks array?

Quoted 2 lines

No, I'm not sure if it is called with a non-mergeable migratetype. It is just for extra safety.

OK, I agree with that.

Quoted 10 lines
Quoted 7 lines

BTW, I noticed the commment on migratetype_is_mergeable() contains:

"See fallbacks[MIGRATE_TYPES][3] in page_alloc.c. "

Should probably change it to e.g. "See fallbacks[][] array ..." so we don't have to keep it in exact sync...

Yes, this comment should be changed.
So do I need to submit a v2 patch?

Please do, with my acked-by.

Quoted 18 lines
Quoted 18 lines
Quoted 18 lines
mm/page_alloc.c +3 -4
 return -1;
 
 *can_steal = false;
@@ -2873,11 +2873,10 @@ int find_suitable_fallback(struct free_area *area, unsigned int order,
 if (can_steal_fallback(order, migratetype))
 *can_steal = true;
 
- if (!only_stealable)
- return fallback_mt;
-
- if (*can_steal)
+ if (!only_stealable || *can_steal)
 return fallback_mt;
+ else
+ break;
 }
 
 return -1;