grub-devel
[Top][All Lists]
Advanced

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

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


From: Zhang Boyang
Subject: Re: [PATCH v3 1/2] mm: Adjust new region size to take management overhead into account
Date: Sat, 14 Jan 2023 20:51:16 +0800
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.1

Hi,

On 2023/1/12 21:52, Daniel Kiper wrote:
On Thu, Dec 22, 2022 at 05:18: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 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 set to "size + align +
GRUB_MM_MGMT_OVERHEAD", thus if grub_mm_add_region_fn() succeeded,

This comment is not in line with the code...


Fixed in v4.

current allocation request can always success.

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

diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c
index ae2279133..5c0e5bbbf 100644
--- a/grub-core/kern/mm.c
+++ b/grub-core/kern/mm.c
@@ -83,6 +83,43 @@

  

+/*
+ * 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  ->|
+ *                                             ^
+ *    addr % GRUB_MM_ALIGN == 1                +--/ This will be the pointer

s/addr % GRUB_MM_ALIGN == 1/assuming addr % GRUB_MM_ALIGN == 1/


Fixed in v4.

It took me some time to understand what do you mean by that.

+ *    a == GRUB_MM_ALIGN - 1                      | returned by next
+ *                                                | grub_malloc(size),
+ *    b == sizeof (struct grub_mm_region)         | if no other suitable free
+ *    c == sizeof (struct grub_mm_header)         \ block is available.
+ *
+ *    size % GRUB_MM_ALIGN == 1

Ditto...

+ *    d == size
+ *    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)
+ */

Thank you for this comment! It clarifies a lot...

+#define GRUB_MM_MGMT_OVERHEAD ((GRUB_MM_ALIGN - 1) \
+                              + sizeof (struct grub_mm_region) \
+                              + sizeof (struct grub_mm_header) \
+                              + (GRUB_MM_ALIGN - 1))

It is correct from math POV but the value may not be very friendly to
the CPU/MMU. Please look below for more details...

+
  grub_mm_region_t grub_mm_base;
  grub_mm_add_region_func_t grub_mm_add_region_fn;

@@ -230,6 +267,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 +452,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)
@@ -424,6 +467,13 @@ grub_memalign (grub_size_t align, grub_size_t size)
    if ((size + align) > ~(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 (size + align, GRUB_MM_MGMT_OVERHEAD, &grow))
+    goto fail;

This should go before "if ((size + align) > ~(grub_size_t) 0x100000)"
and then you should replace "size" with "grow". Additionally, as I said
above due to GRUB_MM_MGMT_OVERHEAD value final "grow" value may not be
very CPU/MMU friendly. So, I suggest to do ALIGN_UP(grow, 4096) after
grub_add() and before "if ((grow + align) > ...".


Fixed in v4. Please check if my changes matches your intention.

+
    align = (align >> GRUB_MM_ALIGN_LOG2);
    if (align == 0)
      align = 1;
@@ -447,7 +497,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 +512,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

On 2023/1/12 21:59, Daniel Kiper wrote:
> On Thu, Dec 22, 2022 at 05:18:24PM +0800, Zhang Boyang wrote:
>>     /*
>> -   * Pre-calculate the size of heap growth (if applicable),
>> +   * Pre-calculate the optimal 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;
>> +  grow = grub_max (grow, GRUB_MM_HEAP_GROW_EXTRA);
>
> If you update the #1 patch as I suggested then this should be
>
>    grow = grub_max (size, GRUB_MM_HEAP_GROW_EXTRA);
>

I think this shouldn't be changed. If "size" is used here, then "grow" will be irrelevant to GRUB_MM_MGMT_OVERHEAD.

> Daniel

Best Regards,
Zhang Boyang



reply via email to

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