[PATCH v2 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 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)
 
   /* 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)
+
 /* 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;
   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;
         }
 
-- 
2.30.2