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

[Zhang Boyang <zhangboyang.id@gmail.com>]

Hi,

Sorry for late reply...

On 2023/1/19 23:36, Daniel Kiper wrote:
> I looked at this patch again and found a few more (minor) issues...
> 
> On Sat, Jan 14, 2023 at 09:23:22PM +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 may 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 must be large enough to make sure grub_malloc(size) always
>> success after a successful call to grub_mm_init_region(addr, size +
>> GRUB_MM_MGMT_OVERHEAD), for any given addr and size (assuming no
>> interger overflow).
>>
>> The size passed to grub_mm_add_region_fn() is now correctly adjusted,
>> 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 | 64 ++++++++++++++++++++++++++++++++++++++++++---
>>   1 file changed, 61 insertions(+), 3 deletions(-)
>>
>> diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
>> index ae2279133..278756dea 100644
>> --- a/grub-core/kern/mm.c
>> +++ b/grub-core/kern/mm.c
>> @@ -83,6 +83,46 @@
>>
>>   \f
>>
>> +/*
>> + * GRUB_MM_MGMT_OVERHEAD is an upper bound of management overhead of
>> + * each region, with any possible padding taken into account.
>> + *
>> + * The value must be large enough to make sure grub_malloc(size) always
>> + * success after a successful call to
>> + * grub_mm_init_region(addr, size + GRUB_MM_MGMT_OVERHEAD), for any given
>> + * addr and size (assuming no interger overflow).
>> + *
>> + * The worst case which has maximum overhead is shown in the figure below:
>> + *
>> + * +-- addr
>> + * v                                           |<-   size   ->|
>> + * +---------+----------------+----------------+--------------+---------+
>> + * | padding | grub_mm_region | grub_mm_header | usable bytes | padding |
>> + * +---------+----------------+----------------+--------------+---------+
>> + * |<-  a  ->|<-     b      ->|<-     c      ->|<-    d     ->|<-  e  ->|
> 
> This drawing is missing grub_memalign() align argument. It should be
> put between "c" and "d". Though the code below of course takes it into
> account... :-)

Fixed in V5.

> 
>> + *    b == sizeof (struct grub_mm_region)      +--/ This will be the pointer
>> + *    c == sizeof (struct grub_mm_header)         | returned by next
>> + *    d == size                                   | grub_malloc(size),
>> + *                                                | if no other suitable free
>> + * Assuming addr % GRUB_MM_ALIGN == 1, then       \ block is available.
>> + *    a == GRUB_MM_ALIGN - 1
>> + *
>> + * Assuming size % GRUB_MM_ALIGN == 1, then
>> + *    e == GRUB_MM_ALIGN - 1
>> + *
>> + * Therefore, the maximum overhead is:
>> + *    a + b + c + e == (GRUB_MM_ALIGN - 1) + sizeof (struct grub_mm_region)
>> + *                     + sizeof (struct grub_mm_header) + (GRUB_MM_ALIGN - 1)
>> + */
>> +#define GRUB_MM_MGMT_OVERHEAD	((GRUB_MM_ALIGN - 1) \
>> +				 + sizeof (struct grub_mm_region) \
>> +				 + sizeof (struct grub_mm_header) \
>> +				 + (GRUB_MM_ALIGN - 1))
>> +
>> +/* The size passed to grub_mm_add_region_fn() is aligned up by this value. */
>> +#define GRUB_MM_HEAP_GROW_ALIGN	4096
>> +
>>   grub_mm_region_t grub_mm_base;
>>   grub_mm_add_region_func_t grub_mm_add_region_fn;
>>
>> @@ -230,6 +270,11 @@ grub_mm_init_region (void *addr, grub_size_t size)
>>
>>     grub_dprintf ("regions", "No: considering a new region at %p of size %" PRIxGRUB_SIZE "\n",
>>   		addr, size);
>> +  /*
>> +   * If you want to modify the code below, please also take a look at
>> +   * GRUB_MM_MGMT_OVERHEAD and make sure it is synchronized with the code.
>> +   */
>> +
>>     /* Allocate a region from the head.  */
>>     r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN);
>>
>> @@ -410,6 +455,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 grow;
>>     int count = 0;
>>
>>     if (!grub_mm_base)
>> @@ -418,10 +464,22 @@ grub_memalign (grub_size_t align, grub_size_t size)
>>     if (size > ~(grub_size_t) align)
>>       goto fail;
>>
>> +  /*
>> +   * Pre-calculate the necessary size of heap growth (if applicable),
>> +   * with region management overhead taken into account.
>> +   */
>> +  if (grub_add (size + align, GRUB_MM_MGMT_OVERHEAD, &grow))
>> +    goto fail;
>> +
>> +  /* Align up heap growth to make it friendly to CPU/MMU. */
>> +  if (grow > ~(grub_size_t) (GRUB_MM_HEAP_GROW_ALIGN - 1))
>> +    goto fail;
>> +  grow = ALIGN_UP (grow, GRUB_MM_HEAP_GROW_ALIGN);
> 
> ALIGN_UP() from here should be last thing of the math which is happening
> above and below. Otherwise it may not give us what we expect...
> 
>>     /* 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 (grow > ~(grub_size_t) 0x100000)
>>       goto fail;
> 
> We do a lot of math here which we very often ditch later almost
> immediately. I would do small optimization here like:
> 
>    /* If failed, increase free memory somehow.  */
>    switch (count)
>      {
>      case 0:
>        /* Request additional pages, contiguous */
>        count++;
> 
>        <our_math_from_above> <----------- MOVE IT HERE...
> 
>        if (grub_mm_add_region_fn != NULL &&
>            grub_mm_add_region_fn (size, GRUB_MM_ADD_REGION_CONSECUTIVE) == GRUB_ERR_NONE)
>          goto again;
> 
>        /* fallthrough  */
> 
>      case 1:
>        /* Request additional pages, anything at all */
>        count++;
>    ...
> 
> Of course this should be a separate patch in this series. I think last one.
> 

I added another patch in V5. Please check if that is what you expected.

Best Regards,
Zhang Boyang

>>     align = (align >> GRUB_MM_ALIGN_LOG2);
>> @@ -447,7 +505,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 +520,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