Re: [PATCH v2 03/15] mm: when adding a region, merge with region after as well as before

[Daniel Kiper]

On Mon, Mar 28, 2022 at 05:22:28PM +1100, Daniel Axtens wrote:
> On x86_64-efi (at least) regions seem to be added from top down. The mm
> code will merge a new region with an existing region that comes
> immediately before the new region. This allows larger allocations to be
> satisfied that would otherwise be the case.
>
> On powerpc-ieee1275, however, regions are added from bottom up. So if
> we add 3x 32MB regions, we can still only satisfy a 32MB allocation,
> rather than the 96MB allocation we might otherwise be able to satisfy.
>
>  * Define 'post_size' as being bytes lost to the end of an allocation
>    due to being given weird sizes from firmware that are not multiples
>    of GRUB_MM_ALIGN.
>
>  * Allow merging of regions immediately _after_ existing regions, not
>    just before. As with the other approach, we create an allocated
>    block to represent the new space and the pass it to grub_free() to
>    get the metadata right.
>
> Tested-by: Stefan Berger <stefanb@linux.ibm.com>

This tag should be added by Stefan in a reply to the email(s) send to
the grub-devel. Though I will accept it this time. And it should be
behind SOB.

> Signed-off-by: Daniel Axtens <dja@axtens.net>

Reviewed-by: Daniel Kiper <daniel.kiper@oracle.com>

But there some nits below...

> ---
> v2: Thanks Daniel K for feedback.
> ---
>  grub-core/kern/mm.c       | 123 +++++++++++++++++++++++---------------
>  include/grub/mm_private.h |   9 +++
>  2 files changed, 85 insertions(+), 47 deletions(-)
>
> diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
> index 079c28da7cdf..94e78f9a910d 100644
> --- a/grub-core/kern/mm.c
> +++ b/grub-core/kern/mm.c
> @@ -130,53 +130,81 @@ grub_mm_init_region (void *addr, grub_size_t size)
>
>    /* Attempt to merge this region with every existing region */
>    for (p = &grub_mm_base, q = *p; q; p = &(q->next), q = *p)
> -    /*
> -     * Is the new region immediately below an existing region? That
> -     * is, is the address of the memory we're adding now (addr) + size
> -     * of the memory we're adding (size) + the bytes we couldn't use
> -     * at the start of the region we're considering (q->pre_size)
> -     * equal to the address of q? In other words, does the memory
> -     * looks like this?
> -     *
> -     * addr                          q
> -     *   |----size-----|-q->pre_size-|<q region>|
> -     */
> -    if ((grub_uint8_t *) addr + size + q->pre_size == (grub_uint8_t *) q)
> -      {
> -     /*
> -      * Yes, we can merge the memory starting at addr into the
> -      * existing region from below. Align up addr to GRUB_MM_ALIGN
> -      * so that our new region has proper alignment.
> -      */
> -     r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN);
> -     /* Copy the region data across */
> -     *r = *q;
> -     /* Consider all the new size as pre-size */
> -     r->pre_size += size;
> -
> -     /*
> -      * If we have enough pre-size to create a block, create a
> -      * block with it. Mark it as allocated and pass it to
> -      * grub_free (), which will sort out getting it into the free
> -      * list.
> -      */
> -     if (r->pre_size >> GRUB_MM_ALIGN_LOG2)
> -       {
> -         h = (grub_mm_header_t) (r + 1);
> -         /* block size is pre-size converted to cells */
> -         h->size = (r->pre_size >> GRUB_MM_ALIGN_LOG2);
> -         h->magic = GRUB_MM_ALLOC_MAGIC;
> -         /* region size grows by block size converted back to bytes */
> -         r->size += h->size << GRUB_MM_ALIGN_LOG2;
> -         /* adjust pre_size to be accurate */
> -         r->pre_size &= (GRUB_MM_ALIGN - 1);
> -         *p = r;
> -         grub_free (h + 1);
> -       }
> -     /* Replace the old region with the new region */
> -     *p = r;
> -     return;
> -      }
> +    {
> +      /*
> +       * Is the new region immediately below an existing region? That
> +       * is, is the address of the memory we're adding now (addr) + size
> +       * of the memory we're adding (size) + the bytes we couldn't use
> +       * at the start of the region we're considering (q->pre_size)
> +       * equal to the address of q? In other words, does the memory
> +       * looks like this?
> +       *
> +       * addr                          q
> +       *   |----size-----|-q->pre_size-|<q region>|
> +       */
> +      if ((grub_uint8_t *) addr + size + q->pre_size == (grub_uint8_t *) q)
> +        {
> +          /*
> +           * Yes, we can merge the memory starting at addr into the
> +           * existing region from below. Align up addr to GRUB_MM_ALIGN
> +           * so that our new region has proper alignment.
> +           */
> +          r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, 
> GRUB_MM_ALIGN);
> +          /* Copy the region data across */
> +          *r = *q;
> +          /* Consider all the new size as pre-size */
> +          r->pre_size += size;
> +
> +          /*
> +           * If we have enough pre-size to create a block, create a
> +           * block with it. Mark it as allocated and pass it to
> +           * grub_free (), which will sort out getting it into the free
> +           * list.
> +           */
> +          if (r->pre_size >> GRUB_MM_ALIGN_LOG2)
> +            {
> +              h = (grub_mm_header_t) (r + 1);
> +              /* block size is pre-size converted to cells */
> +              h->size = (r->pre_size >> GRUB_MM_ALIGN_LOG2);
> +              h->magic = GRUB_MM_ALLOC_MAGIC;
> +              /* region size grows by block size converted back to bytes */
> +              r->size += h->size << GRUB_MM_ALIGN_LOG2;
> +              /* adjust pre_size to be accurate */
> +              r->pre_size &= (GRUB_MM_ALIGN - 1);
> +              *p = r;
> +              grub_free (h + 1);
> +            }
> +          /* Replace the old region with the new region */
> +          *p = r;
> +          return;
> +        }
> +
> +      /*
> +       * Is the new region immediately above an existing region? That
> +       * is:
> +       *   q                       addr
> +       *   |<q region>|-q->post_size-|----size-----|
> +       */
> +      if ((grub_uint8_t *)q + sizeof(*q) + q->size + q->post_size ==
> +       (grub_uint8_t *) addr)
> +     {
> +          /*
> +           * Yes! Follow a similar pattern to above, but simpler.
> +           * Our header starts at address - post_size, which should align us
> +           * to a cell boundary.
> +           */
> +       h = (grub_mm_header_t) ((grub_uint8_t *)addr - q->post_size);
> +          /* our size is the allocated size plus post_size, in cells */
> +       h->size = (size + q->post_size) >> GRUB_MM_ALIGN_LOG2;
> +       h->magic = GRUB_MM_ALLOC_MAGIC;
> +          /* region size grows by block size converted back to bytes */
> +       q->size += h->size << GRUB_MM_ALIGN_LOG2;
> +          /* adjust new post_size to be accurate */

Comments and code are incorrectly aligned...

Anyway, I can fix this before committing.

Daniel