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

Yajun Deng
2023-09-29T10:11:04Z

On 2023/9/29 17:04, Mike Rapoport wrote:
> On Thu, Sep 28, 2023 at 04:47:59PM +0800, Yajun Deng wrote:
>> On 2023/9/28 14:16, Mike Rapoport wrote:
>>> On Wed, Sep 27, 2023 at 09:37:52AM +0800, 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 calling memblock_insert_region(). If the count is
>>>> equal to the maximum value, it needs to resize the array. Otherwise,
>>>> insert it directly.
>>>>
>>>> To avoid nested calls to memblock_add_range(), we need to call
>>>> memblock_reserve() out of memblock_double_array().
>>> memblock_add_range() does an extra loop once in a while, but I don't think
>>> removing it will have any actual effect on the boot time.
>>
>> Yes, it has no obvious actual effect on the boot time,  but it does reduce
>> the number of unnecessary loop.
>>
>> The actual effect on the boot time should not be the only criterion for
>> whether a patch is accepted or not.
>>
>> Since the comment in the previous code, it tells the user that it would be
>> executed twice, this can be misleading to users.
>>
>> So the new code will be simpler and clearer. It not just change the code,
>> but also remove the comment
> Adding return-by-pointer parameters to memblock_double_array() and pulling
> memblock_reserve() out of this function is in no way simpler and clearer
> that having an extra loop.

If memblock_reserve() in memblock_double_array(),  there will be nested
calls to memblock_add_range().

memblock_add_range(A)->memblock_double_array(A)->memblock_reserve(B)->memblock_add_range(B)

->memblock_insert_region(B)->memblock_merge_regions(B)->memblock_insert_region(A)->memblock_merge_regions(A)

It's hard to see that and debug.

If memblock_reserve() out of memblock_double_array(),  there wouldn't
have a nested calls.

memblock_add_range(A)->memblock_double_array(A)->memblock_insert_region(A)->memblock_merge_regions(A)->

memblock_reserve(B)->memblock_add_range(B)->memblock_insert_region(B)->memblock_merge_regions(B)

We should make memblock_add_range is done, and do another
memblock_add_range.

> If the comment is wrong, just fix the comment.
>
>> about "executed twice",  it obviously tells the user only resize the array
>> if it is equal to the maximum value
>>
>> and doesn't need to be executed twice.
>>
>>>> Signed-off-by: Yajun Deng <yajun.deng@linux.dev>
>>>> ---
>>>> mm/memblock.c | 117 ++++++++++++++++++++++++--------------------------
>>>> 1 file changed, 57 insertions(+), 60 deletions(-)
>>>>
>>>> diff --git a/mm/memblock.c b/mm/memblock.c
>>>> index 5a88d6d24d79..3f44c84f5d0b 100644
>>>> --- a/mm/memblock.c
>>>> +++ b/mm/memblock.c
>>>> @@ -400,6 +400,8 @@ void __init memblock_discard(void)
>>>> * @type: memblock type of the regions array being doubled
>>>> * @new_area_start: starting address of memory range to avoid overlap with
>>>> * @new_area_size: size of memory range to avoid overlap with
>>>> + * @new_reserve_base: starting address of new array
>>>> + * @new_reserve_size: size of new array
>>>> *
>>>> * Double the size of the @type regions array. If memblock is being used to
>>>> * allocate memory for a new reserved regions array and there is a previously
>>>> @@ -412,7 +414,9 @@ void __init memblock_discard(void)
>>>> */
>>>> static int __init_memblock memblock_double_array(struct memblock_type *type,
>>>> phys_addr_t new_area_start,
>>>> - phys_addr_t new_area_size)
>>>> + phys_addr_t new_area_size,
>>>> + phys_addr_t *new_reserve_base,
>>>> + phys_addr_t *new_reserve_size)
>>>> {
>>>> struct memblock_region *new_array, *old_array;
>>>> phys_addr_t old_alloc_size, new_alloc_size;
>>>> @@ -490,11 +494,13 @@ static int __init_memblock memblock_double_array(struct memblock_type *type,
>>>> memblock_free(old_array, old_alloc_size);
>>>> /*
>>>> - * Reserve the new array if that comes from the memblock. Otherwise, we
>>>> - * needn't do it
>>>> + * Keep the address and size if that comes from the memblock. Otherwise,
>>>> + * we needn't do it.
>>>> */
>>>> - if (!use_slab)
>>>> - BUG_ON(memblock_reserve(addr, new_alloc_size));
>>>> + if (!use_slab) {
>>>> + *new_reserve_base = addr;
>>>> + *new_reserve_size = new_alloc_size;
>>>> + }
>>>> /* Update slab flag */
>>>> *in_slab = use_slab;
>>>> @@ -588,11 +594,12 @@ 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;
>>>> + phys_addr_t new_base = 0, new_size;
>>>> + int idx, start_rgn = -1, end_rgn;
>>>> struct memblock_region *rgn;
>>>> + unsigned long ocnt = type->cnt;
>>>> if (!size)
>>>> return 0;
>>>> @@ -608,25 +615,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;
>>>> @@ -644,15 +632,23 @@ 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 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 == type->max) &&
>>>> + memblock_double_array(type, obase, size,
>>>> + &new_base, &new_size))
>>>> + 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);
>>>> @@ -660,33 +656,28 @@ 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) &&
>>>> + memblock_double_array(type, obase, size,
>>>> + &new_base, &new_size))
>>>> + return -ENOMEM;
>>>> +
>>>> + if (start_rgn == -1)
>>>> + start_rgn = idx;
>>>> + end_rgn = idx + 1;
>>>> + 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, start_rgn, end_rgn);
>>>> - return 0;
>>>> - }
>>>> + memblock_merge_regions(type, start_rgn, end_rgn);
>>>> +
>>>> + /* Reserve the new array */
>>>> + if (new_base)
>>>> + memblock_reserve(new_base, new_size);
>>>> +
>>>> + return 0;
>>>> }
>>>> /**
>>>> @@ -755,6 +746,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);
>>>> + phys_addr_t new_base = 0, new_size;
>>>> int idx;
>>>> struct memblock_region *rgn;
>>>> @@ -764,10 +756,15 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type,
>>>> return 0;
>>>> /* we'll create at most two more regions */
>>>> - while (type->cnt + 2 > type->max)
>>>> - if (memblock_double_array(type, base, size) < 0)
>>>> + if (type->cnt + 2 > type->max) {
>>>> + if (memblock_double_array(type, base, size,
>>>> + &new_base, &new_size))
>>>> return -ENOMEM;
>>>> + if (new_base)
>>>> + memblock_reserve(new_base, new_size);
>>>> + }
>>>> +
>>>> for_each_memblock_type(idx, type, rgn) {
>>>> phys_addr_t rbase = rgn->base;
>>>> phys_addr_t rend = rbase + rgn->size;
>>>> --
>>>> 2.25.1
>>>>