[PATCH 2/3] memblock: Make finding index faster when modify regions.

[Peng Zhang <zhangpeng.00@bytedance.com>]

We can use binary search to find the index to modify regions in
memblock_add_range() and memblock_isolate_range(). Because the
arrangement of regions is ordered. It may be faster when there are
many regions. So implemented a binary search and a new macro to walk
regions.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 mm/memblock.c | 33 +++++++++++++++++++++++++++++----
 1 file changed, 29 insertions(+), 4 deletions(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index 6eedcfc5dcc1..cb92770ac22e 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -149,6 +149,11 @@ static __refdata struct memblock_type *memblock_memory = &memblock.memory;
 	     i < memblock_type->cnt;					\
 	     i++, rgn = &memblock_type->regions[i])
 
+#define for_each_memblock_type_start(i, start, memblock_type, rgn)	\
+	for (i = start, rgn = &memblock_type->regions[i];		\
+	     i < memblock_type->cnt;					\
+	     i++, rgn = &memblock_type->regions[i])
+
 #define memblock_dbg(fmt, ...)						\
 	do {								\
 		if (memblock_debug)					\
@@ -181,6 +186,24 @@ static unsigned long __init_memblock memblock_addrs_overlap(phys_addr_t base1, p
 	return ((base1 < (base2 + size2)) && (base2 < (base1 + size1)));
 }
 
+/*
+ * Binary search for the first region not to the left of @base.
+ */
+static unsigned long __init_memblock memblock_lower_bound_region(struct memblock_type *type,
+								 phys_addr_t base)
+{
+	unsigned long idx, low_idx = 0, high_idx = type->cnt;
+
+	while (low_idx < high_idx) {
+		idx = (low_idx + high_idx) >> 1;
+		if (type->regions[idx].base + type->regions[idx].size <= base)
+			low_idx = idx + 1;
+		else
+			high_idx = idx;
+	}
+	return low_idx;
+}
+
 bool __init_memblock memblock_overlaps_region(struct memblock_type *type,
 					phys_addr_t base, phys_addr_t size)
 {
@@ -581,7 +604,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 	bool insert = false;
 	phys_addr_t obase = base;
 	phys_addr_t end = base + memblock_cap_size(base, &size);
-	int idx, nr_new;
+	int idx, start_idx, nr_new;
 	struct memblock_region *rgn;
 
 	if (!size)
@@ -607,6 +630,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 	 */
 	if (type->cnt * 2 + 1 <= type->max)
 		insert = true;
+	start_idx = memblock_lower_bound_region(type, base);
 
 repeat:
 	/*
@@ -617,7 +641,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 	base = obase;
 	nr_new = 0;
 
-	for_each_memblock_type(idx, type, rgn) {
+	for_each_memblock_type_start(idx, start_idx, type, rgn) {
 		phys_addr_t rbase = rgn->base;
 		phys_addr_t rend = rbase + rgn->size;
 
@@ -737,7 +761,7 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
 					int *start_rgn, int *end_rgn)
 {
 	phys_addr_t end = base + memblock_cap_size(base, &size);
-	int idx;
+	int idx, start_idx;
 	struct memblock_region *rgn;
 
 	*start_rgn = *end_rgn = 0;
@@ -750,7 +774,8 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
 		if (memblock_double_array(type, base, size) < 0)
 			return -ENOMEM;
 
-	for_each_memblock_type(idx, type, rgn) {
+	start_idx = memblock_lower_bound_region(type, base);
+	for_each_memblock_type_start(idx, start_idx, type, rgn) {
 		phys_addr_t rbase = rgn->base;
 		phys_addr_t rend = rbase + rgn->size;
 
-- 
2.20.1