Re: [PATCH 1/2] mm: Adjust new region size to take management cost into account

[Daniel Kiper]

On Tue, Nov 29, 2022 at 10:17:33PM +0800, Zhang Boyang wrote:
> When grub_memalign() encounters out-of-memory, it will try
> grub_mm_add_region_fn() to request more memory from system firmware.
> However, the size passed to it doesn't take region management cost into

s/cost/overhead/? If yes then please fix everything below too...

> account. Adding a memory area of `size` bytes will result in a heap

s/`/"/ Same below if needed...

> region of less than `size` bytes truely avaliable. Thus, the new region
> might not adequate for current allocation request, confusing

s/might not/may not be/

> out-of-memory handling code.
>
> This patch introduces GRUB_MM_MAX_COST to address the region management

s/GRUB_MM_MAX_COST/GRUB_MM_MGMT_OVERHEAD/?

> cost (e.g. metadata, alignment). The value of this new constant should
> make `grub_malloc (size)` always success after a successful call to

s/`grub_malloc (size)`/grub_malloc(size)/

> `grub_mm_init_region (addr, size + GRUB_MM_MAX_COST)`.

s/`grub_mm_init_region (addr, size + 
GRUB_MM_MAX_COST)`/grub_mm_init_region(addr, size + GRUB_MM_MAX_COST)/

> The new region size is now set to `size + GRUB_MM_MAX_COST`, thus if
> grub_mm_add_region_fn() succeeded, current allocation request can always
> success.
>
> Signed-off-by: Zhang Boyang <zhangboyang.id@gmail.com>
> ---
>  grub-core/kern/mm.c       | 15 ++++++++++++---
>  include/grub/mm_private.h |  9 +++++++++
>  2 files changed, 21 insertions(+), 3 deletions(-)
>
> diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
> index ae2279133..973cb6b15 100644
> --- a/grub-core/kern/mm.c
> +++ b/grub-core/kern/mm.c
> @@ -410,7 +410,9 @@ grub_memalign (grub_size_t align, grub_size_t size)
>  {
>    grub_mm_region_t r;
>    grub_size_t n = ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) + 1;
> +  grub_size_t bound;
>    int count = 0;
> +  grub_size_t grow;

grub_size_t bound, grow;

>    if (!grub_mm_base)
>      goto fail;
> @@ -418,10 +420,13 @@ grub_memalign (grub_size_t align, grub_size_t size)
>    if (size > ~(grub_size_t) align)
>      goto fail;
>
> +  /* If largest free chunk in region >= bound, allocation can always success 
> */

I am not sure I understand. Could you expand this comment a bit?

> +  bound = size + align;

I think you should use grub_add() here too...

And doing this you change the allocation behavior below. In original
algorithm we allocate only size bytes below. I think this should
not be changed.

>    /* We currently assume at least a 32-bit grub_size_t,
>       so limiting allocations to <adress space size> - 1MiB
>       in name of sanity is beneficial. */
> -  if ((size + align) > ~(grub_size_t) 0x100000)
> +  if (bound > ~(grub_size_t) 0x100000)

s/bound/limit/?

>      goto fail;
>
>    align = (align >> GRUB_MM_ALIGN_LOG2);
> @@ -443,11 +448,15 @@ grub_memalign (grub_size_t align, grub_size_t size)
>    switch (count)
>      {
>      case 0:
> +      /* Adjust heap growth to address the region management cost. */
> +      if (grub_add (bound, GRUB_MM_MAX_COST, &grow))

I think this should happen before limit check above.

> +     goto fail;
> +
>        /* Request additional pages, contiguous */
>        count++;
>
>        if (grub_mm_add_region_fn != NULL &&
> -          grub_mm_add_region_fn (size, GRUB_MM_ADD_REGION_CONSECUTIVE) == 
> GRUB_ERR_NONE)
> +          grub_mm_add_region_fn (grow, GRUB_MM_ADD_REGION_CONSECUTIVE) == 
> GRUB_ERR_NONE)
>       goto again;
>
>        /* fallthrough  */
> @@ -462,7 +471,7 @@ grub_memalign (grub_size_t align, grub_size_t size)
>             * Try again even if this fails, in case it was able to partially
>             * satisfy the request
>             */
> -          grub_mm_add_region_fn (size, GRUB_MM_ADD_REGION_NONE);
> +          grub_mm_add_region_fn (grow, GRUB_MM_ADD_REGION_NONE);
>            goto again;
>          }
>
> diff --git a/include/grub/mm_private.h b/include/grub/mm_private.h
> index 96c2d816b..f212110e4 100644
> --- a/include/grub/mm_private.h
> +++ b/include/grub/mm_private.h
> @@ -95,6 +95,15 @@ typedef struct grub_mm_region
>  }
>  *grub_mm_region_t;
>
> +/*
> + * Set an upper bound of management cost of each region,
> + * with sizeof(struct grub_mm_region), sizeof(struct grub_mm_header) and
> + * any possible alignment or padding taken into account.
> + * The value should make `grub_malloc (size)` always success after a 
> successful
> + * call to `grub_mm_init_region (addr, size + GRUB_MM_MAX_COST)`.
> + */
> +#define GRUB_MM_MAX_COST 0x1000
> +

I would define this variable in the following way even if the result
is the same:

#define GRUB_MM_MGMT_OVERHEAD ALIGN_UP (ALIGN_UP (sizeof (*grub_mm_region_t), 
GRUB_MM_ALIGN) +
                                        10 * ALIGN_UP (sizeof 
(*grub_mm_header), GRUB_MM_ALIGN), 0x1000)

This way it will be more readable what is happening here, i.e. size of
header of memory region plus size of 10, this is quite arbitrary figure,
memory block headers aligned to page size (it would be nice to have
a constant here but it would require more work to make it happen for
all archs; so, let's use a number for this for time being). It would
be nice to have relevant comment before GRUB_MM_MGMT_OVERHEAD
definition too.

And probably it can be defined in grub-core/kern/mm.c instead of
include/grub/mm_private.h.

Daniel