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

[Mike Rapoport <rppt@kernel.org>]

On Sun, Apr 14, 2024 at 12:45:26AM +0000, Wei Yang wrote:
> 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.

Very similar patch was posted a while ago:
https://lore.kernel.org/all/20221025070943.363578-1-yajun.deng@linux.dev

and it caused boot regression:
https://lore.kernel.org/linux-mm/Y2oLYB7Tu7J91tVm@linux.ibm.com

> 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
> 

-- 
Sincerely yours,
Mike.