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 @@
+/*
+ * 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