From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1pM66g-0002oS-3c for mharc-grub-devel@gnu.org; Sun, 29 Jan 2023 06:44:22 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pM66e-0002oG-OZ for grub-devel@gnu.org; Sun, 29 Jan 2023 06:44:20 -0500 Received: from mail-pj1-x1032.google.com ([2607:f8b0:4864:20::1032]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pM66c-0001Sh-M6 for grub-devel@gnu.org; Sun, 29 Jan 2023 06:44:20 -0500 Received: by mail-pj1-x1032.google.com with SMTP id m11so8757337pji.0 for ; Sun, 29 Jan 2023 03:44:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:content-language :references:cc:to:subject:user-agent:mime-version:date:message-id :from:to:cc:subject:date:message-id:reply-to; bh=RWPqgSTZeZnE4zrVyrsf2Ea6cA+MwuAgCgXS7mfgMxQ=; b=cPmD/8vwz1zhcVmQgzRmPPaCoyLIUyDwtI2viLNXrMs9WndBinmfX4RiLO053N664j I5gG/tNzg7g9hzsgM6HIbdglB8Ownw2HGcR43qVQP7WVL881bPJ8yxB2xSzvs0N2WA1q 5P+MAIrU5ZnOk5/hXKLXN4LhG/YfpuEBCJ0HpEuUzIB98jOV1SfwsljfclSsOgqi/fmk racpTPW7yL5FonEPyMCxnLBUrcuJGlBhAdoxg916FoUCVPzDG105OtKMuM+OZ3KwHRom Anwt6bEK+D6VmP5RMm7/racDfPxdB1xun7Uz5e9afXSuxRM6sp7tz9ZwJz8LICTiCwM/ KeJg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:content-language :references:cc:to:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=RWPqgSTZeZnE4zrVyrsf2Ea6cA+MwuAgCgXS7mfgMxQ=; b=LEeDn/VnVSCiNfkISJSE1QjJS2l9mJbUGDLtdlzvtfvQd9Ct3Ej/huW+0vXK3t0L6T qs9W19ANmRI8XxbVstBVsdL5cK0Xepk3R703ti7RBN7+guDw8e4zBGWU9TaLc2Yr3rpR GSFI64tpG+m6hqZnsLER5jG6KhW3vrM6UgUmW0Xk8NQWCdV8vyZrgsv39K+AiFdkCRfS pgAVNxVVNLZGkl51p8WyfnjkhphHUaFA/bz6D32idmpypUQorlJAtm5ZD/sLUUyZ24dZ Stbu8cfVLsmFdqn1Qod32K+YkBLjZcRrqUR3XXGUaJlv3S8wHEH1t16lYfCU5HJI0Mov 2n9Q== X-Gm-Message-State: AO0yUKWcrGYmNd3EZqVGhTP8P+nI4NoPBihVfYFCJZNGL++ux25Os5LT 9PDAgX3Q6e7SUIwQBhPxRllBAAjWJTA= X-Google-Smtp-Source: AK7set/m0B6EPsdnFL4PxIHGyfjQMa1YQohKZmasv3RiJ4+NNfGWHCix3xdv1SPNLiFtJIqGIPcxGw== X-Received: by 2002:a17:903:2447:b0:196:7d67:e193 with SMTP id l7-20020a170903244700b001967d67e193mr1540900pls.47.1674992656864; Sun, 29 Jan 2023 03:44:16 -0800 (PST) Received: from [0.0.0.0] (ec2-13-113-80-70.ap-northeast-1.compute.amazonaws.com. [13.113.80.70]) by smtp.gmail.com with ESMTPSA id e3-20020a17090301c300b00177faf558b5sm5763875plh.250.2023.01.29.03.44.15 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 29 Jan 2023 03:44:16 -0800 (PST) Message-ID: Date: Sun, 29 Jan 2023 19:44:13 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.6.1 Subject: Re: [PATCH v4 1/2] mm: Adjust new region size to take management overhead into account To: Daniel Kiper Cc: grub-devel@gnu.org References: <20230114132323.132210-1-zhangboyang.id@gmail.com> <20230114132323.132210-2-zhangboyang.id@gmail.com> <20230119153608.fxecuaktnxuumy52@tomti.i.net-space.pl> Content-Language: en-US From: Zhang Boyang In-Reply-To: <20230119153608.fxecuaktnxuumy52@tomti.i.net-space.pl> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Received-SPF: pass client-ip=2607:f8b0:4864:20::1032; envelope-from=zhangboyang.id@gmail.com; helo=mail-pj1-x1032.google.com X-Spam_score_int: -21 X-Spam_score: -2.2 X-Spam_bar: -- X-Spam_report: (-2.2 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, NICE_REPLY_A=-0.092, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: The development of GNU GRUB List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 29 Jan 2023 11:44:21 -0000 Hi, Sorry for late reply... On 2023/1/19 23:36, Daniel Kiper wrote: > 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 >> --- >> 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... :-) Fixed in V5. > >> + * 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 - 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++; > > <----------- 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. > I added another patch in V5. Please check if that is what you expected. Best Regards, Zhang Boyang >> 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