[PATCH v4 0/2] mm: Better handling of adding new regions

[PATCH v4 0/2] mm: Better handling of adding new regions

[Zhang Boyang]

Hi,

This is the V4 patchset.

V3 is at:
https://lists.gnu.org/archive/html/grub-devel/2022-12/msg00271.html

V2 is at:
https://lists.gnu.org/archive/html/grub-devel/2022-12/msg00164.html

V1 is at:
https://lists.gnu.org/archive/html/grub-devel/2022-11/msg00147.html

For changes in V3->V4, please see my reply at:
https://lists.gnu.org/archive/html/grub-devel/2023-01/msg00099.html

Best Regards,
Zhang Boyang


Zhang Boyang (2):
  mm: Adjust new region size to take management overhead into account
  mm: Preallocate some space when adding new regions

 grub-core/kern/mm.c | 70 +++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 67 insertions(+), 3 deletions(-)

-- 
2.30.2

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

[Zhang Boyang]

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  ->|
+ *                                             ^
+ *    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);
+
   /* 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;
 
   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;
         }
 
-- 
2.30.2

[PATCH v4 2/2] mm: Preallocate some space when adding new regions

[Zhang Boyang]

When grub_memalign() encounters out-of-memory, it will try
grub_mm_add_region_fn() to request more memory from system firmware.
However, it doesn't preallocate memory space for future allocation
requests. In extreme cases, it requires one call to
grub_mm_add_region_fn() for each memory allocation request. This can be
very slow.

This patch introduces GRUB_MM_HEAP_GROW_EXTRA, the minimal heap growth
granularity. The new region size is now set to the bigger one of its
original value and GRUB_MM_HEAP_GROW_EXTRA. Thus, it will result in some
memory space preallocated if current allocations request is small.

The value of GRUB_MM_HEAP_GROW_EXTRA is set to 1MB. If this value is
smaller, the cost of small memory allocations will be higher. If this
value is larger, more memory will be wasted and it might cause
out-of-memory on machines with small amount of RAM.

Signed-off-by: Zhang Boyang <zhangboyang.id@gmail.com>
---
 grub-core/kern/mm.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
index 278756dea..4e220bbff 100644
--- a/grub-core/kern/mm.c
+++ b/grub-core/kern/mm.c
@@ -123,6 +123,9 @@
 /* The size passed to grub_mm_add_region_fn() is aligned up by this value. */
 #define GRUB_MM_HEAP_GROW_ALIGN	4096
 
+/* Minimal heap growth granularity when existing heap space is exhausted. */
+#define GRUB_MM_HEAP_GROW_EXTRA	0x100000
+
 grub_mm_region_t grub_mm_base;
 grub_mm_add_region_func_t grub_mm_add_region_fn;
 
@@ -471,6 +474,9 @@ grub_memalign (grub_size_t align, grub_size_t size)
   if (grub_add (size + align, GRUB_MM_MGMT_OVERHEAD, &grow))
     goto fail;
 
+  /* Preallocate some extra space if heap growth is small. */
+  grow = grub_max (grow, GRUB_MM_HEAP_GROW_EXTRA);
+
   /* Align up heap growth to make it friendly to CPU/MMU. */
   if (grow > ~(grub_size_t) (GRUB_MM_HEAP_GROW_ALIGN - 1))
     goto fail;
-- 
2.30.2

Re: [PATCH v4 0/2] mm: Better handling of adding new regions

[Daniel Kiper]

On Sat, Jan 14, 2023 at 09:23:21PM +0800, Zhang Boyang wrote:
> Hi,
>
> This is the V4 patchset.
>
> V3 is at:
> https://lists.gnu.org/archive/html/grub-devel/2022-12/msg00271.html
>
> V2 is at:
> https://lists.gnu.org/archive/html/grub-devel/2022-12/msg00164.html
>
> V1 is at:
> https://lists.gnu.org/archive/html/grub-devel/2022-11/msg00147.html
>
> For changes in V3->V4, please see my reply at:
> https://lists.gnu.org/archive/html/grub-devel/2023-01/msg00099.html
>
> Best Regards,
> Zhang Boyang
>
>
> Zhang Boyang (2):
>   mm: Adjust new region size to take management overhead into account
>   mm: Preallocate some space when adding new regions

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

Thank you for improving the mm code!

Daniel

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

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 6131 bytes --]

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

s/success/succeeds

> + * 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  ->|
> + *                                             ^
> + *    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))

Great explanation!

> +/* 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);
> +
>    /* 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;
>  
>    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;
>          }

Regardless of the one grammar fix:

    Reviewed-by: Patrick Steinhardt <ps@pks.im>

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v4 2/2] mm: Preallocate some space when adding new regions

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 2176 bytes --]

On Sat, Jan 14, 2023 at 09:23: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, it doesn't preallocate memory space for future allocation
> requests. In extreme cases, it requires one call to
> grub_mm_add_region_fn() for each memory allocation request. This can be
> very slow.
> 
> This patch introduces GRUB_MM_HEAP_GROW_EXTRA, the minimal heap growth
> granularity. The new region size is now set to the bigger one of its
> original value and GRUB_MM_HEAP_GROW_EXTRA. Thus, it will result in some
> memory space preallocated if current allocations request is small.
> 
> The value of GRUB_MM_HEAP_GROW_EXTRA is set to 1MB. If this value is
> smaller, the cost of small memory allocations will be higher. If this
> value is larger, more memory will be wasted and it might cause
> out-of-memory on machines with small amount of RAM.
> 
> Signed-off-by: Zhang Boyang <zhangboyang.id@gmail.com>
> ---
>  grub-core/kern/mm.c | 6 ++++++
>  1 file changed, 6 insertions(+)
> 
> diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
> index 278756dea..4e220bbff 100644
> --- a/grub-core/kern/mm.c
> +++ b/grub-core/kern/mm.c
> @@ -123,6 +123,9 @@
>  /* The size passed to grub_mm_add_region_fn() is aligned up by this value. */
>  #define GRUB_MM_HEAP_GROW_ALIGN	4096
>  
> +/* Minimal heap growth granularity when existing heap space is exhausted. */
> +#define GRUB_MM_HEAP_GROW_EXTRA	0x100000
> +
>  grub_mm_region_t grub_mm_base;
>  grub_mm_add_region_func_t grub_mm_add_region_fn;
>  
> @@ -471,6 +474,9 @@ grub_memalign (grub_size_t align, grub_size_t size)
>    if (grub_add (size + align, GRUB_MM_MGMT_OVERHEAD, &grow))
>      goto fail;
>  
> +  /* Preallocate some extra space if heap growth is small. */
> +  grow = grub_max (grow, GRUB_MM_HEAP_GROW_EXTRA);
> +
>    /* Align up heap growth to make it friendly to CPU/MMU. */
>    if (grow > ~(grub_size_t) (GRUB_MM_HEAP_GROW_ALIGN - 1))
>      goto fail;

    Reviewed-by: Patrick Steinhardt <ps@pks.im>

Thanks for both patches!

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Daniel Kiper]

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... :-)

> + *    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.

>    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

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

[Zhang Boyang]

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

[PATCH v4 0/2] mm: Better handling of adding new regions

[Zhang Boyang]

Hi,

Changes in V3 -> V4:

* [PATCH v4 1/2] mm: Try invalidate disk caches last when out of memory
  Added "Reviewed-by" tags.

* [PATCH v4 2/2] mm: Better handling of adding new regions
  Made this patch standalone.
  Moved (and renamed back) new constants to "mm_private.h" from "mm.h".
  Documented more details in comments.

* The allocation type patch will be posted later.

Best Regards,
Zhang Boyang

----

Changes in V2 -> V3:

1. Splited into two patches. One deal with the disk cache problem. The
other is focused on improvement.
2. Add types to regions. So small and large allocations are effectively
seperated into different heaps. This facility can also seperate module
segments and plain data chunks.
3. Region management costs are now denoted by GRUB_MM_MAX_COST,
seperated from GRUB_MM_GROW_SMALL ( =GRUB_MM_HEAP_GROW in previous
patch).

Some notes for the size of heap growth:

In order to guarantee the success of allocation when heap exhausted, the
new region size should be at least (size + align + GRUB_MM_MAX_COST).
For small chunks, it's adjusted to (GRUB_MM_GROW_SMALL +
GRUB_MM_MAX_COST) to improve performance.