[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH v2 1/2] mm: Adjust new region size to take management overhea

From: Zhang Boyang
Subject: Re: [PATCH v2 1/2] mm: Adjust new region size to take management overhead into account
Date: Thu, 22 Dec 2022 00:35:06 +0800
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.0


On 2022/12/21 01:16, Daniel Kiper wrote:
Please do not send your new sets of patches as a reply to previous
discussions. If you do that then it is more difficult to find them
in threaded views.

OK. I will not do that in future.

On Thu, Dec 15, 2022 at 07:19: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, 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 <>
  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);

    /* 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 
    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;

Please do not sprinkle constants definitions over the code. This does
not help in reading. Additionally, I think these extra constants
make code less readable.

My motivation is to force who want to modify this code notice there is a constant tightly connected to region layout. So he will not forget update the constant if he changes region layout.

I agree this will reduce readability. I will replace this with a comment in next version.

    /* 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).
+ */
+                              GRUB_MM_MGMT_OVERHEAD_REGION_HEADER + \
+                              GRUB_MM_MGMT_OVERHEAD_MM_HEADER + \
+                              GRUB_MM_MGMT_OVERHEAD_TAIL_PADDING)

I do not think this math is correct. Please use mine from previous
reply. When it is wrong please say where exactly it is wrong. OK, I can
agree using "sizeof (struct grub_mm_region)" is more readable than
"sizeof (*grub_mm_region_t)". Anything else?

I have to use "sizeof (struct grub_mm_region)", because "sizeof (*grub_mm_region_t)" won't compile.

After rethinking, I think the formula need to be refactored. The purpose of this constant, same as what's its comment says, is to make grub_malloc(size) always success after a successful call to grub_mm_init_region(addr, size + GRUB_MM_MGMT_OVERHEAD).

If new region can be merged into an existing region, all of its area can be used for forming a free block (grub_mm_header and user usable bytes). This is the most simple case. Even in this case, GRUB_MM_MGMT_OVERHEAD should be "sizeof(struct grub_mm_header) + (GRUB_MM_ALIGN-1)". This is because "size" may not be integral multiple of GRUB_MM_ALIGN. As GRUB_MM_MGMT_OVERHEAD is a constant designed to be added to "size", we can't use macros like ALIGN_UP. Therefore, we must make GRUB_MM_MGMT_OVERHEAD sufficient large, so "x + GRUB_MM_MGMT_OVERHEAD >= sizeof(struct grub_mm_header) + ALIGN_UP(x, GRUB_MM_ALIGN)" is always true for any "x". The smallest GRUB_MM_MGMT_OVERHEAD would be "sizeof(struct grub_mm_header) + (GRUB_MM_ALIGN-1)".

The complex case is, new region is independent and can't be merged into other regions. In this case, a grub_mm_header struct must be formed along with a free block. It looks like:
| padding |   grub_mm_region   |   grub_mm_header   |   usable bytes   |
If we ignore alignment/padding, using the method above, GRUB_MM_MGMT_OVERHEAD would be "sizeof (struct grub_mm_region) + sizeof(struct grub_mm_header) + (GRUB_MM_ALIGN-1)". Unfortunately, the grub_mm_region must be aligned, and the algorithm used by grub_mm_init_region(some_addr) is new_addr=ALIGN_UP(some_addr,GRUB_MM_ALIGN). So we must make GRUB_MM_MGMT_OVERHEAD sufficient large, so "x + GRUB_MM_MGMT_OVERHEAD >= (ALIGN_UP(y,GRUB_MM_ALIGN)-y) + sizeof (struct grub_mm_region) + sizeof(struct grub_mm_header) + (GRUB_MM_ALIGN-1)" is always true for any "x" and any "y". Thus, GRUB_MM_MGMT_OVERHEAD should be "(GRUB_MM_ALIGN-1) + sizeof (struct grub_mm_region) + sizeof(struct grub_mm_header) + (GRUB_MM_ALIGN-1)" (by the way, I miscalculated this component in V2, GRUB_MM_MGMT_OVERHEAD_TAIL_PADDING is not necessary)

Finally, we should take max of two GRUB_MM_MGMT_OVERHEAD from 2 cases. So the final value of GRUB_MM_MGMT_OVERHEAD shoule be:

(GRUB_MM_ALIGN-1) + sizeof (struct grub_mm_region) + sizeof(struct grub_mm_header) + (GRUB_MM_ALIGN-1)

On 2022/12/13 21:48, Daniel Kiper wrote:
> I would define this variable in the following way even if the result
> is the same:
> #define GRUB_MM_MGMT_OVERHEAD ALIGN_UP (ALIGN_UP (sizeof (*grub_mm_region_t), GRUB_MM_ALIGN) + > 10 * ALIGN_UP (sizeof (*c), GRUB_MM_ALIGN), 0x1000)
> This way it will be more readable what is happening here, i.e. size of
> header of memory region plus size of 10, this is quite arbitrary figure,

I didn't understand this formula and it is probably not what GRUB_MM_MGMT_OVERHEAD designed to be. By the way, grub_mm_header and grub_mm_region already aligned to GRUB_MM_ALIGN, so there is no need to ALIGN_UP them.

> memory block headers aligned to page size (it would be nice to have
> a constant here but it would require more work to make it happen for
> all archs; so, let's use a number for this for time being). It would
> be nice to have relevant comment before GRUB_MM_MGMT_OVERHEAD
> definition too.

I don't think it is necessary to align some value to page size. If I understand correctly, grub_mm_init_region() make no assumptions on alignment of its arguments.

And I would define GRUB_MM_MGMT_OVERHEAD constant at the beginning of
the grub-core/kern/mm.c file before grub_mm_base definition.

  /* 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;

I think you do not need bound at all. Just use grow...

OK, will fix in next version.

Best Regards,
Zhang Boyang

    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)

        if (grub_mm_add_region_fn != NULL &&
-          grub_mm_add_region_fn (size, GRUB_MM_ADD_REGION_CONSECUTIVE) == 
+          grub_mm_add_region_fn (grow, GRUB_MM_ADD_REGION_CONSECUTIVE) == 
        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;


reply via email to

[Prev in Thread] Current Thread [Next in Thread]