Re: [PATCH 05/19] mm: when adding a region, merge with region after as well as before

[Daniel Kiper]

On Tue, Oct 12, 2021 at 06:29:54PM +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.
>
> Signed-off-by: Daniel Axtens <dja@axtens.net>
> ---
>  grub-core/kern/mm.c       | 55 +++++++++++++++++++++++++--------------
>  include/grub/mm_private.h | 15 +++++++++++
>  2 files changed, 51 insertions(+), 19 deletions(-)
>
> diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
> index c070afc621f8..835ed8a8f6f9 100644
> --- a/grub-core/kern/mm.c
> +++ b/grub-core/kern/mm.c
> @@ -129,25 +129,41 @@ grub_mm_init_region (void *addr, grub_size_t size)
>      size = ((grub_addr_t) -0x1000) - (grub_addr_t) addr;
>
>    for (p = &grub_mm_base, q = *p; q; p = &(q->next), q = *p)
> -    if ((grub_uint8_t *) addr + size + q->pre_size == (grub_uint8_t *) q)
> -      {
> -     r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN);
> -     *r = *q;
> -     r->pre_size += size;
> -
> -     if (r->pre_size >> GRUB_MM_ALIGN_LOG2)
> -       {
> -         h = (grub_mm_header_t) (r + 1);
> -         h->size = (r->pre_size >> GRUB_MM_ALIGN_LOG2);
> -         h->magic = GRUB_MM_ALLOC_MAGIC;
> -         r->size += h->size << GRUB_MM_ALIGN_LOG2;
> -         r->pre_size &= (GRUB_MM_ALIGN - 1);
> -         *p = r;
> -         grub_free (h + 1);
> -       }
> -     *p = r;
> -     return;
> -      }
> +    {
> +      /* Does this region come _before_ an existing region? */
> +      if ((grub_uint8_t *) addr + size + q->pre_size == (grub_uint8_t *) q)
> +     {
> +       r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN);
> +       *r = *q;
> +       r->pre_size += size;
> +
> +       if (r->pre_size >> GRUB_MM_ALIGN_LOG2)
> +         {
> +           h = (grub_mm_header_t) (r + 1);
> +           h->size = (r->pre_size >> GRUB_MM_ALIGN_LOG2);
> +           h->magic = GRUB_MM_ALLOC_MAGIC;
> +           r->size += h->size << GRUB_MM_ALIGN_LOG2;
> +           r->pre_size &= (GRUB_MM_ALIGN - 1);
> +           *p = r;
> +           grub_free (h + 1);
> +         }
> +       *p = r;
> +       return;
> +     }
> +
> +      /* Does this region come _after_ an existing region? */
> +      if ((grub_uint8_t *)q + sizeof(*q) + q->size + q->post_size ==
> +       (grub_uint8_t *) addr)
> +     {
> +       h = (grub_mm_header_t) ((grub_uint8_t *)addr - q->post_size);
> +       h->size = (size + q->post_size) >> GRUB_MM_ALIGN_LOG2;
> +       h->magic = GRUB_MM_ALLOC_MAGIC;
> +       q->size += h->size << GRUB_MM_ALIGN_LOG2;
> +       q->post_size = (q->post_size + size) & (GRUB_MM_ALIGN - 1);
> +       grub_free (h + 1);
> +       return;

The code itself LGTM. However, I would be more than happy if you add
bunch of comments and maybe some ASCII drawings explaining what is
happening here. This should save a lot time of our successors... :-)

> +     }
> +    }
>
>    /* Allocate a region from the head.  */
>    r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN);
> @@ -166,6 +182,7 @@ grub_mm_init_region (void *addr, grub_size_t size)
>    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;
>
>    /* Find where to insert this region. Put a smaller one before bigger ones,
>       to prevent fragmentation.  */
> diff --git a/include/grub/mm_private.h b/include/grub/mm_private.h
> index 533b47173e18..0effbc45a668 100644
> --- a/include/grub/mm_private.h
> +++ b/include/grub/mm_private.h
> @@ -74,8 +74,23 @@ typedef struct grub_mm_region
>     */
>    grub_size_t pre_size;
>
> +  /* Likewise, the post-size is the number of bytes we wasted at the end
> +     of the allocation because it wasn't a multiple of GRUB_MM_ALIGN
> +   */

Please fix the formatting of this comment.

> +  grub_size_t post_size;
> +
>    /* How many bytes are in this region? (free and allocated) */
>    grub_size_t size;
> +
> +  /* pad to a multiple of cell size */
> +#if GRUB_CPU_SIZEOF_VOID_P == 4
> +  char padding[4+4+4];
> +#elif GRUB_CPU_SIZEOF_VOID_P == 8
> +  char padding[8+8+8];
> +#else
> +# error "unknown word size"
> +#endif

grub_uint8_t padding[3 * GRUB_CPU_SIZEOF_VOID_P];?

Or do not we have a construct in the C which allows us to add paddings
like that one in smarter way?

Daniel