[PATCH 1/6] mm/memblock: reduce the two round insertion of memblock_add_range()

[Wei Yang <richard.weiyang@gmail.com>]

Current memblock_add_range() does the insertion with two round
iteration.

First round does the calculation of new region required, and second
round does the actual insertion. Between them, if current max can't meet
new region requirement, it is expanded.

The worst case is:

1. cnt == max
2. new range overlaps all existing region

This means the final cnt should be (2 * max + 1). Since we always double
the array size, this means we only need to double the array twice at the
worst case, which is fairly rare. For other cases, only once array
double is enough.

Let's double the array immediately when there is no room for new region.
This simplify the code a little.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Jinyu Tang <tjytimi@163.com>
CC: Peng Zhang <zhangpeng.00@bytedance.com>
---
 mm/memblock.c | 74 +++++++++++++++------------------------------------
 1 file changed, 22 insertions(+), 52 deletions(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index 98d25689cf10..b46109300927 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -585,10 +585,9 @@ 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;
 
 	if (!size)
@@ -606,25 +605,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 or equal to 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;
@@ -642,15 +622,17 @@ 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 (type->cnt >= type->max) {
+				if (memblock_double_array(type, obase, size) < 0)
+					return -ENOMEM;
 			}
+
+			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);
@@ -658,33 +640,21 @@ 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 (type->cnt >= type->max) {
+			if (memblock_double_array(type, obase, size) < 0)
+				return -ENOMEM;
 		}
-	}
 
-	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 (start_rgn != -1)
 		memblock_merge_regions(type, start_rgn, end_rgn);
-		return 0;
-	}
+	return 0;
 }
 
 /**
-- 
2.34.1