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

[Zhang Boyang]

Previously, there are two problems of the handling of adding new
regions. First, it doesn't take region management cost into account.
Adding a memory area of `x` bytes will result in a heap region of less
than `x` bytes avaliable. Thus, the new region might not adequate for
current allocation request. Second, it doesn't pre-allocate a big region
for small allocations, so it might be slow for many small allocations.

This patch introduces GRUB_MM_MAX_COST to address the cost of region
management. The value of this constant should make
`grub_mm_init_region (addr, size + GRUB_MM_MAX_COST)` initialize a
region of at least `size` free bytes available. The size of heap growth
is now adjusted according this value before calling
grub_mm_add_region_fn ().

This patch also introduces GRUB_MM_HEAP_GROW to address the minimal heap
growth granularity. When a small allocation encounters heap space
exhaustion, the size of heap growth is now expended to this value, and a
new region of bigger size will be added. Thus subsequent allocations can
use the remaining space of that new region.

Signed-off-by: Zhang Boyang <zhangboyang.id@gmail.com>
---
 grub-core/kern/mm.c       | 18 +++++++++++++++---
 include/grub/mm_private.h | 12 ++++++++++++
 2 files changed, 27 insertions(+), 3 deletions(-)

diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
index ae2279133..fe630f061 100644
--- a/grub-core/kern/mm.c
+++ b/grub-core/kern/mm.c
@@ -410,7 +410,9 @@ 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 guarantee;
   int count = 0;
+  grub_size_t grow;
 
   if (!grub_mm_base)
     goto fail;
@@ -418,10 +420,13 @@ grub_memalign (grub_size_t align, grub_size_t size)
   if (size > ~(grub_size_t) align)
     goto fail;
 
+  /* Allocation can always success if max continuous free chunk >= guarantee */
+  guarantee = 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 (guarantee > ~(grub_size_t) 0x100000)
     goto fail;
 
   align = (align >> GRUB_MM_ALIGN_LOG2);
@@ -443,11 +448,18 @@ grub_memalign (grub_size_t align, grub_size_t size)
   switch (count)
     {
     case 0:
+      /* Calculate optimal size of heap growth. */
+      grow = grub_max(guarantee, GRUB_MM_HEAP_GROW);
+
+      /* Adjust heap growth to address the cost of region management. */
+      if (grub_add(grow, GRUB_MM_MAX_COST, &grow))
+       goto fail;
+
       /* Request additional pages, contiguous */
       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 +474,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;
         }
 
diff --git a/include/grub/mm_private.h b/include/grub/mm_private.h
index 96c2d816b..a01ba2507 100644
--- a/include/grub/mm_private.h
+++ b/include/grub/mm_private.h
@@ -95,6 +95,18 @@ typedef struct grub_mm_region
 }
 *grub_mm_region_t;
 
+/*
+ * Set an upper bound of management cost of each region,
+ * with sizeof(struct grub_mm_region), sizeof(struct grub_mm_header) and
+ * any possible alignment or padding taken into account.
+ * The value should make `grub_mm_init_region (addr, size + GRUB_MM_MAX_COST)`
+ * initialize a region of at least `size` free bytes available.
+ */
+#define GRUB_MM_MAX_COST 0x1000
+
+/* Minimal heap growth granularity, when existing heap space is exhausted. */
+#define GRUB_MM_HEAP_GROW 0x100000
+
 #ifndef GRUB_MACHINE_EMU
 extern grub_mm_region_t EXPORT_VAR (grub_mm_base);
 #endif
-- 
2.30.2