[PATCH v2] memblock: don't run loop in memblock_add_range() twice

[PATCH v2] memblock: don't run loop in memblock_add_range() twice

[Yajun Deng]

There is no need round twice in memblock_add_range().

We can call memblock_double_array() to extend the size if type->cnt
greater or equal to type->max before memblock_insert_region(); otherwise,
we can insert the new region directly.

v2:
 - Add a comment when the allocation is required.

Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
---
 mm/memblock.c | 69 ++++++++++++++++++---------------------------------
 1 file changed, 24 insertions(+), 45 deletions(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index 511d4783dcf1..602fa8ee9b71 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -578,10 +578,10 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 				phys_addr_t base, phys_addr_t size,
 				int nid, enum memblock_flags flags)
 {
-	bool insert = false;
 	phys_addr_t obase = base;
 	phys_addr_t end = base + memblock_cap_size(base, &size);
-	int idx, nr_new;
+	unsigned long ocnt = type->cnt;
+	int idx;
 	struct memblock_region *rgn;
 
 	if (!size)
@@ -598,25 +598,6 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 		return 0;
 	}
 
-	/*
-	 * The worst case is when new range overlaps all existing regions,
-	 * then we'll need type->cnt + 1 empty regions in @type. So if
-	 * type->cnt * 2 + 1 is less than type->max, we know
-	 * that there is enough empty regions in @type, and we can insert
-	 * regions directly.
-	 */
-	if (type->cnt * 2 + 1 < type->max)
-		insert = true;
-
-repeat:
-	/*
-	 * The following is executed twice.  Once with %false @insert and
-	 * then with %true.  The first counts the number of regions needed
-	 * to accommodate the new area.  The second actually inserts them.
-	 */
-	base = obase;
-	nr_new = 0;
-
 	for_each_memblock_type(idx, type, rgn) {
 		phys_addr_t rbase = rgn->base;
 		phys_addr_t rend = rbase + rgn->size;
@@ -634,11 +615,18 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 			WARN_ON(nid != memblock_get_region_node(rgn));
 #endif
 			WARN_ON(flags != rgn->flags);
-			nr_new++;
-			if (insert)
-				memblock_insert_region(type, idx++, base,
-						       rbase - base, nid,
-						       flags);
+
+			/*
+			 * if type->cnt greater or equal to type->max,
+			 * resize array; otherwise, insert directly.
+			 */
+			if ((type->cnt >= type->max) &&
+			    memblock_double_array(type, obase, size))
+				return -ENOMEM;
+
+			memblock_insert_region(type, idx++, base,
+					       rbase - base, nid,
+					       flags);
 		}
 		/* area below @rend is dealt with, forget about it */
 		base = min(rend, end);
@@ -646,29 +634,20 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 
 	/* insert the remaining portion */
 	if (base < end) {
-		nr_new++;
-		if (insert)
-			memblock_insert_region(type, idx, base, end - base,
-					       nid, flags);
+		if ((type->cnt >= type->max) &&
+		    memblock_double_array(type, obase, size))
+			return -ENOMEM;
+
+		memblock_insert_region(type, idx, base, end - base,
+				       nid, flags);
 	}
 
-	if (!nr_new)
+	if (ocnt == type->cnt)
 		return 0;
 
-	/*
-	 * If this was the first round, resize array and repeat for actual
-	 * insertions; otherwise, merge and return.
-	 */
-	if (!insert) {
-		while (type->cnt + nr_new > type->max)
-			if (memblock_double_array(type, obase, size) < 0)
-				return -ENOMEM;
-		insert = true;
-		goto repeat;
-	} else {
-		memblock_merge_regions(type);
-		return 0;
-	}
+	memblock_merge_regions(type);
+
+	return 0;
 }
 
 /**
-- 
2.25.1

Re: [PATCH v2] memblock: don't run loop in memblock_add_range() twice

[Mike Rapoport]

On Tue, Oct 25, 2022 at 03:09:43PM +0800, Yajun Deng wrote:
> There is no need round twice in memblock_add_range().
> 
> We can call memblock_double_array() to extend the size if type->cnt
> greater or equal to type->max before memblock_insert_region(); otherwise,
> we can insert the new region directly.
> 
> v2:
>  - Add a comment when the allocation is required.
> 
> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
> ---
>  mm/memblock.c | 69 ++++++++++++++++++---------------------------------
>  1 file changed, 24 insertions(+), 45 deletions(-)

Applied, thanks!

Re: [PATCH v2] memblock: don't run loop in memblock_add_range() twice

[Yeah Yeah]

Re: [PATCH v2] memblock: don't run loop in memblock_add_range() twice

[Yajun Deng]

Sorry, there is a bug in this version, please ignore it.

On 2023/10/2 18:56, Yajun Deng wrote:
> There is round twice in memblock_add_range(). The first counts the number
> of regions needed to accommodate the new area. The second actually inserts
> them. But the first round isn't really needed, we just need to check the
> counts before inserting them.
>
> Check the count before iterate memblock. If the count is equal to the
> maximum, it needs to resize the array. Otherwise, insert it directly.
> After that, it's similar logic to memblock_isolate_range.
>
> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
> ---
> v2: remove the changes of memblock_double_array.
> v1: https://lore.kernel.org/all/20230927013752.2515238-1-yajun.deng@linux.dev/
> ---
>   mm/memblock.c | 75 +++++++++++++++++----------------------------------
>   1 file changed, 24 insertions(+), 51 deletions(-)
>
> diff --git a/mm/memblock.c b/mm/memblock.c
> index 5a88d6d24d79..655d8e82f90a 100644
> --- a/mm/memblock.c
> +++ b/mm/memblock.c
> @@ -588,11 +588,11 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>   				phys_addr_t base, phys_addr_t size,
>   				int nid, enum memblock_flags flags)
>   {
> -	bool insert = false;
>   	phys_addr_t obase = base;
>   	phys_addr_t end = base + memblock_cap_size(base, &size);
> -	int idx, nr_new, start_rgn = -1, end_rgn;
> +	int idx, start_rgn = -1, end_rgn;
>   	struct memblock_region *rgn;
> +	unsigned long ocnt = type->cnt;
>   
>   	if (!size)
>   		return 0;
> @@ -609,23 +609,13 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>   	}
>   
>   	/*
> -	 * The worst case is when new range overlaps all existing regions,
> -	 * then we'll need type->cnt + 1 empty regions in @type. So if
> -	 * type->cnt * 2 + 1 is less than or equal to type->max, we know
> -	 * that there is enough empty regions in @type, and we can insert
> -	 * regions directly.
> +	 * If type->cnt is equal to type->max, it means there's
> +	 * not enough empty region and the array needs to be
> +	 * resized. Otherwise, insert it directly.
>   	 */
> -	if (type->cnt * 2 + 1 <= type->max)
> -		insert = true;
> -
> -repeat:
> -	/*
> -	 * The following is executed twice.  Once with %false @insert and
> -	 * then with %true.  The first counts the number of regions needed
> -	 * to accommodate the new area.  The second actually inserts them.
> -	 */
> -	base = obase;
> -	nr_new = 0;
> +	if ((type->cnt == type->max) &&
> +	    memblock_double_array(type, obase, size))
> +		return -ENOMEM;
>   
>   	for_each_memblock_type(idx, type, rgn) {
>   		phys_addr_t rbase = rgn->base;
> @@ -644,15 +634,13 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>   			WARN_ON(nid != memblock_get_region_node(rgn));
>   #endif
>   			WARN_ON(flags != rgn->flags);
> -			nr_new++;
> -			if (insert) {
> -				if (start_rgn == -1)
> -					start_rgn = idx;
> -				end_rgn = idx + 1;
> -				memblock_insert_region(type, idx++, base,
> -						       rbase - base, nid,
> -						       flags);
> -			}
> +
> +			if (start_rgn == -1)
> +				start_rgn = idx;
> +			end_rgn = idx + 1;
> +			memblock_insert_region(type, idx++, base,
> +					       rbase - base, nid,
> +					       flags);
>   		}
>   		/* area below @rend is dealt with, forget about it */
>   		base = min(rend, end);
> @@ -660,33 +648,18 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>   
>   	/* insert the remaining portion */
>   	if (base < end) {
> -		nr_new++;
> -		if (insert) {
> -			if (start_rgn == -1)
> -				start_rgn = idx;
> -			end_rgn = idx + 1;
> -			memblock_insert_region(type, idx, base, end - base,
> -					       nid, flags);
> -		}
> -	}
>   
> -	if (!nr_new)
> -		return 0;
> +		if (start_rgn == -1)
> +			start_rgn = idx;
> +		end_rgn = idx + 1;
> +		memblock_insert_region(type, idx, base, end - base,
> +				       nid, flags);
> +	}
>   
> -	/*
> -	 * If this was the first round, resize array and repeat for actual
> -	 * insertions; otherwise, merge and return.
> -	 */
> -	if (!insert) {
> -		while (type->cnt + nr_new > type->max)
> -			if (memblock_double_array(type, obase, size) < 0)
> -				return -ENOMEM;
> -		insert = true;
> -		goto repeat;
> -	} else {
> +	if (ocnt != type->cnt)
>   		memblock_merge_regions(type, start_rgn, end_rgn);
> -		return 0;
> -	}
> +
> +	return 0;
>   }
>   
>   /**

[PATCH v2] memblock: don't run loop in memblock_add_range() twice

[Yajun Deng]

There is round twice in memblock_add_range(). The first counts the number
of regions needed to accommodate the new area. The second actually inserts
them. But the first round isn't really needed, we just need to check the
counts before inserting them.

Check the count before iterate memblock. If the count is equal to the
maximum, it needs to resize the array. Otherwise, insert it directly.
After that, it's similar logic to memblock_isolate_range.

Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
---
v2: remove the changes of memblock_double_array.
v1: https://lore.kernel.org/all/20230927013752.2515238-1-yajun.deng@linux.dev/
---
 mm/memblock.c | 75 +++++++++++++++++----------------------------------
 1 file changed, 24 insertions(+), 51 deletions(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index 5a88d6d24d79..655d8e82f90a 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -588,11 +588,11 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 				phys_addr_t base, phys_addr_t size,
 				int nid, enum memblock_flags flags)
 {
-	bool insert = false;
 	phys_addr_t obase = base;
 	phys_addr_t end = base + memblock_cap_size(base, &size);
-	int idx, nr_new, start_rgn = -1, end_rgn;
+	int idx, start_rgn = -1, end_rgn;
 	struct memblock_region *rgn;
+	unsigned long ocnt = type->cnt;
 
 	if (!size)
 		return 0;
@@ -609,23 +609,13 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 	}
 
 	/*
-	 * The worst case is when new range overlaps all existing regions,
-	 * then we'll need type->cnt + 1 empty regions in @type. So if
-	 * type->cnt * 2 + 1 is less than or equal to type->max, we know
-	 * that there is enough empty regions in @type, and we can insert
-	 * regions directly.
+	 * If type->cnt is equal to type->max, it means there's
+	 * not enough empty region and the array needs to be
+	 * resized. Otherwise, insert it directly.
 	 */
-	if (type->cnt * 2 + 1 <= type->max)
-		insert = true;
-
-repeat:
-	/*
-	 * The following is executed twice.  Once with %false @insert and
-	 * then with %true.  The first counts the number of regions needed
-	 * to accommodate the new area.  The second actually inserts them.
-	 */
-	base = obase;
-	nr_new = 0;
+	if ((type->cnt == type->max) &&
+	    memblock_double_array(type, obase, size))
+		return -ENOMEM;
 
 	for_each_memblock_type(idx, type, rgn) {
 		phys_addr_t rbase = rgn->base;
@@ -644,15 +634,13 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 			WARN_ON(nid != memblock_get_region_node(rgn));
 #endif
 			WARN_ON(flags != rgn->flags);
-			nr_new++;
-			if (insert) {
-				if (start_rgn == -1)
-					start_rgn = idx;
-				end_rgn = idx + 1;
-				memblock_insert_region(type, idx++, base,
-						       rbase - base, nid,
-						       flags);
-			}
+
+			if (start_rgn == -1)
+				start_rgn = idx;
+			end_rgn = idx + 1;
+			memblock_insert_region(type, idx++, base,
+					       rbase - base, nid,
+					       flags);
 		}
 		/* area below @rend is dealt with, forget about it */
 		base = min(rend, end);
@@ -660,33 +648,18 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 
 	/* insert the remaining portion */
 	if (base < end) {
-		nr_new++;
-		if (insert) {
-			if (start_rgn == -1)
-				start_rgn = idx;
-			end_rgn = idx + 1;
-			memblock_insert_region(type, idx, base, end - base,
-					       nid, flags);
-		}
-	}
 
-	if (!nr_new)
-		return 0;
+		if (start_rgn == -1)
+			start_rgn = idx;
+		end_rgn = idx + 1;
+		memblock_insert_region(type, idx, base, end - base,
+				       nid, flags);
+	}
 
-	/*
-	 * If this was the first round, resize array and repeat for actual
-	 * insertions; otherwise, merge and return.
-	 */
-	if (!insert) {
-		while (type->cnt + nr_new > type->max)
-			if (memblock_double_array(type, obase, size) < 0)
-				return -ENOMEM;
-		insert = true;
-		goto repeat;
-	} else {
+	if (ocnt != type->cnt)
 		memblock_merge_regions(type, start_rgn, end_rgn);
-		return 0;
-	}
+
+	return 0;
 }
 
 /**
-- 
2.25.1