[PATCH v2 0/2] Some small improvements for memblock.

[PATCH v2 0/2] Some small improvements for memblock.

[Peng Zhang]

Some small optimizations for memblock.

Changes since v1:
- Delete the second patch that complicate code
- Adjust the code of memblock_merge_regions()

Peng Zhang (2):
  memblock: Make a boundary tighter in memblock_add_range().
  memblock: Avoid useless checks in memblock_merge_regions().

 mm/memblock.c | 41 +++++++++++++++++++++++++++--------------
 1 file changed, 27 insertions(+), 14 deletions(-)

-- 
2.20.1

[PATCH v2 1/2] memblock: Make a boundary tighter in memblock_add_range().

[Peng Zhang]

When type->cnt * 2 + 1 is less than or equal to type->max, there is
enough empty regions to insert.

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

diff --git a/mm/memblock.c b/mm/memblock.c
index 685e30e6d27c..836eb71ea3ea 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -601,11 +601,11 @@ 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 type->max, we know
+	 * 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)
+	if (type->cnt * 2 + 1 <= type->max)
 		insert = true;
 
 repeat:
-- 
2.20.1

[PATCH v2 2/2] memblock: Avoid useless checks in memblock_merge_regions().

[Peng Zhang]

memblock_merge_regions() is called after regions have been modified to
merge the neighboring compatible regions. That will check all regions
but most checks is useless.

Most of the time we only insert one or a few new regions, or modify one
or a few regions. At this time, we don't need to check all regions. We
only need to check the changed regions, because other not related
regions cannot be merged. So this patch add two parameters to
memblock_merge_regions() to indicate the lower and upper boundary to scan.

Test this patch and get numbers like this:

void memblock_merge_regions(struct memblock_type *type) {
	static int iteration_count = 0;
	static int max_nr_regions = 0;

	max_nr_regions = max(max_nr_regions, (int)type->cnt);
	...
	while () {
		iteration_count++;
		...
	}
	pr_info("iteration_count: %d max_nr_regions %d", iteration_count,
max_nr_regions);
}

The folowing numbers is the last output tested on a physical machine
with 1T memory.

Mainline:
[2.472243] iteration_count: 45410 max_nr_regions 178

Patched:
[2.470869] iteration_count: 923 max_nr_regions 176

The actual startup speed seems to change little, but it does reduce the
scan overhead.

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

diff --git a/mm/memblock.c b/mm/memblock.c
index 836eb71ea3ea..22e48b0f57ad 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -500,15 +500,19 @@ static int __init_memblock memblock_double_array(struct memblock_type *type,
 /**
  * memblock_merge_regions - merge neighboring compatible regions
  * @type: memblock type to scan
- *
- * Scan @type and merge neighboring compatible regions.
+ * @start_rgn: start scanning from (@start_rgn - 1)
+ * @end_rgn: end scanning at (@end_rgn - 1)
+ * Scan @type and merge neighboring compatible regions in [@start_rgn - 1, @end_rgn)
  */
-static void __init_memblock memblock_merge_regions(struct memblock_type *type)
+static void __init_memblock memblock_merge_regions(struct memblock_type *type,
+						   unsigned long start_rgn,
+						   unsigned long end_rgn)
 {
 	int i = 0;
-
-	/* cnt never goes below 1 */
-	while (i < type->cnt - 1) {
+	if (start_rgn)
+		i = start_rgn - 1;
+	end_rgn = min(end_rgn, type->cnt - 1);
+	while (i < end_rgn) {
 		struct memblock_region *this = &type->regions[i];
 		struct memblock_region *next = &type->regions[i + 1];
 
@@ -525,6 +529,7 @@ static void __init_memblock memblock_merge_regions(struct memblock_type *type)
 		/* move forward from next + 1, index of which is i + 2 */
 		memmove(next, next + 1, (type->cnt - (i + 2)) * sizeof(*next));
 		type->cnt--;
+		end_rgn--;
 	}
 }
 
@@ -581,7 +586,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, nr_new, start_rgn = -1, end_rgn;
 	struct memblock_region *rgn;
 
 	if (!size)
@@ -635,10 +640,14 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 #endif
 			WARN_ON(flags != rgn->flags);
 			nr_new++;
-			if (insert)
+			if (insert) {
+				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);
@@ -647,9 +656,13 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 	/* insert the remaining portion */
 	if (base < end) {
 		nr_new++;
-		if (insert)
+		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)
@@ -666,7 +679,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
 		insert = true;
 		goto repeat;
 	} else {
-		memblock_merge_regions(type);
+		memblock_merge_regions(type, start_rgn, end_rgn);
 		return 0;
 	}
 }
@@ -902,7 +915,7 @@ static int __init_memblock memblock_setclr_flag(phys_addr_t base,
 			r->flags &= ~flag;
 	}
 
-	memblock_merge_regions(type);
+	memblock_merge_regions(type, start_rgn, end_rgn);
 	return 0;
 }
 
@@ -1275,7 +1288,7 @@ int __init_memblock memblock_set_node(phys_addr_t base, phys_addr_t size,
 	for (i = start_rgn; i < end_rgn; i++)
 		memblock_set_region_node(&type->regions[i], nid);
 
-	memblock_merge_regions(type);
+	memblock_merge_regions(type, start_rgn, end_rgn);
 #endif
 	return 0;
 }
-- 
2.20.1

Re: [PATCH v2 2/2] memblock: Avoid useless checks in memblock_merge_regions().

[Peng Zhang]

Hi, Mike

> @@ -581,7 +586,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, nr_new, start_rgn = -1, end_rgn;
>   	struct memblock_region *rgn;
>   
>   	if (!size)
> @@ -635,10 +640,14 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>   #endif
>   			WARN_ON(flags != rgn->flags);
>   			nr_new++;
> -			if (insert)
> +			if (insert) {
> +				if (start_rgn == -1)
We can't initialize start_rgn with 0 and use if(!start_rgn).

If start_rgn is equal to 0, it will be reassigned. It is possible that 
we will eventually need start_rgn to be equal to 0, and it may be 
reassigned to a larger value that does not meet expectations.

Thanks.

> +					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);
> @@ -647,9 +656,13 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>   	/* insert the remaining portion */
>   	if (base < end) {
>   		nr_new++;
> -		if (insert)
> +		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)
> @@ -666,7 +679,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
>   		insert = true;
>   		goto repeat;
>   	} else {
> -		memblock_merge_regions(type);
> +		memblock_merge_regions(type, start_rgn, end_rgn);
>   		return 0;
>   	}
>   }
> @@ -902,7 +915,7 @@ static int __init_memblock memblock_setclr_flag(phys_addr_t base,
>   			r->flags &= ~flag;
>   	}
>   
> -	memblock_merge_regions(type);
> +	memblock_merge_regions(type, start_rgn, end_rgn);
>   	return 0;
>   }
>   
> @@ -1275,7 +1288,7 @@ int __init_memblock memblock_set_node(phys_addr_t base, phys_addr_t size,
>   	for (i = start_rgn; i < end_rgn; i++)
>   		memblock_set_region_node(&type->regions[i], nid);
>   
> -	memblock_merge_regions(type);
> +	memblock_merge_regions(type, start_rgn, end_rgn);
>   #endif
>   	return 0;
>   }
Sincerely yours,
Peng.

Re: [PATCH v2 0/2] Some small improvements for memblock.

[Mike Rapoport]

On Sun, Jan 29, 2023 at 05:00:32PM +0800, Peng Zhang wrote:
> Some small optimizations for memblock.
> 
> Changes since v1:
> - Delete the second patch that complicate code
> - Adjust the code of memblock_merge_regions()
> 
> Peng Zhang (2):
>   memblock: Make a boundary tighter in memblock_add_range().
>   memblock: Avoid useless checks in memblock_merge_regions().
> 
>  mm/memblock.c | 41 +++++++++++++++++++++++++++--------------
>  1 file changed, 27 insertions(+), 14 deletions(-)

Applied, thanks!
 
> -- 
> 2.20.1
> 

-- 
Sincerely yours,
Mike.