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

[Daniel Kiper]

Please do not send your new sets of patches as a reply to previous
discussions. If you do that then it is more difficult to find them
in threaded views.

On Thu, Dec 15, 2022 at 07:19:23PM +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 overhead
> into account. Adding a memory area of "size" bytes will result in a heap
> region of less than "size" bytes truely avaliable. Thus, the new region
> may not be adequate for current allocation request, confusing
> out-of-memory handling code.
>
> This patch introduces GRUB_MM_MGMT_OVERHEAD to address the region
> management overhead (e.g. metadata, padding). The value of this new
> constant should make grub_malloc(size) always success after a successful
> call to grub_mm_init_region(addr, size + GRUB_MM_MGMT_OVERHEAD).
>
> The new region size is now set to "size + GRUB_MM_MGMT_OVERHEAD", 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 | 37 ++++++++++++++++++++++++++++++++++---
>  1 file changed, 34 insertions(+), 3 deletions(-)
>
> diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
> index ae2279133..20bb54dde 100644
> --- a/grub-core/kern/mm.c
> +++ b/grub-core/kern/mm.c
> @@ -232,6 +232,7 @@ grub_mm_init_region (void *addr, grub_size_t size)
>               addr, size);
>    /* Allocate a region from the head.  */
>    r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN);
> +#define GRUB_MM_MGMT_OVERHEAD_HEAD_PADDING   (GRUB_MM_ALIGN - 1)
>
>    /* If this region is too small, ignore it.  */
>    if (size < GRUB_MM_ALIGN + (char *) r - (char *) addr + sizeof (*r))
> @@ -239,15 +240,18 @@ grub_mm_init_region (void *addr, grub_size_t size)
>
>    size -= (char *) r - (char *) addr + sizeof (*r);
>
> +#define GRUB_MM_MGMT_OVERHEAD_MM_HEADER              sizeof (struct 
> grub_mm_header)
>    h = (grub_mm_header_t) (r + 1);
>    h->next = h;
>    h->magic = GRUB_MM_FREE_MAGIC;
>    h->size = (size >> GRUB_MM_ALIGN_LOG2);
>
> +#define GRUB_MM_MGMT_OVERHEAD_REGION_HEADER  sizeof (struct grub_mm_region)
>    r->first = h;
>    r->pre_size = (grub_addr_t) r - (grub_addr_t) addr;
>    r->size = (h->size << GRUB_MM_ALIGN_LOG2);
>    r->post_size = size - r->size;
> +#define GRUB_MM_MGMT_OVERHEAD_TAIL_PADDING   (GRUB_MM_ALIGN - 1)

Please do not sprinkle constants definitions over the code. This does
not help in reading. Additionally, I think these extra constants
make code less readable.

>    /* Find where to insert this region. Put a smaller one before bigger ones,
>       to prevent fragmentation.  */
> @@ -259,6 +263,17 @@ grub_mm_init_region (void *addr, grub_size_t size)
>    r->next = q;
>  }
>
> +/*
> + * GRUB_MM_MGMT_OVERHEAD is an upper bound of management overhead of
> + * each region, with any possible 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_MGMT_OVERHEAD).
> + */
> +#define GRUB_MM_MGMT_OVERHEAD (GRUB_MM_MGMT_OVERHEAD_HEAD_PADDING + \
> +                            GRUB_MM_MGMT_OVERHEAD_REGION_HEADER + \
> +                            GRUB_MM_MGMT_OVERHEAD_MM_HEADER + \
> +                            GRUB_MM_MGMT_OVERHEAD_TAIL_PADDING)

I do not think this math is correct. Please use mine from previous
reply. When it is wrong please say where exactly it is wrong. OK, I can
agree using "sizeof (struct grub_mm_region)" is more readable than
"sizeof (*grub_mm_region_t)". Anything else?

And I would define GRUB_MM_MGMT_OVERHEAD constant at the beginning of
the grub-core/kern/mm.c file before grub_mm_base definition.

>  /* Allocate the number of units N with the alignment ALIGN from the ring
>   * buffer given in *FIRST.  ALIGN must be a power of two. Both N and
>   * ALIGN are in units of GRUB_MM_ALIGN.  Return a non-NULL if successful,
> @@ -410,6 +425,7 @@ 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, grow;

I think you do not need bound at all. Just use grow...

>    int count = 0;
>
>    if (!grub_mm_base)
> @@ -418,10 +434,25 @@ grub_memalign (grub_size_t align, grub_size_t size)
>    if (size > ~(grub_size_t) align)
>      goto fail;
>
> +  /*
> +   * If we have a free chunk whose real size is bigger than or equal to
> +   * "size + align", the alignment requirement can always be satisfied.
> +   * However, this is an overestimate. The allocation may still success even 
> if
> +   * all free chunks are smaller than "size + align".
> +   */
> +  bound = size + align;
> +
>    /* 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)
> +    goto fail;
> +
> +  /*
> +   * Pre-calculate the size of heap growth (if applicable),
> +   * with region management overhead taken into account.
> +   */
> +  if (grub_add (bound, GRUB_MM_MGMT_OVERHEAD, &grow))
>      goto fail;
>
>    align = (align >> GRUB_MM_ALIGN_LOG2);
> @@ -447,7 +478,7 @@ grub_memalign (grub_size_t align, grub_size_t size)
>        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 +493,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;
>          }

Daniel