From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1nYimP-0005bR-PJ for mharc-grub-devel@gnu.org; Mon, 28 Mar 2022 02:23:06 -0400 Received: from eggs.gnu.org ([209.51.188.92]:50192) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nYimL-0005Z2-B1 for grub-devel@gnu.org; Mon, 28 Mar 2022 02:23:01 -0400 Received: from [2607:f8b0:4864:20::1032] (port=39888 helo=mail-pj1-x1032.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nYimJ-0005GD-JL for grub-devel@gnu.org; Mon, 28 Mar 2022 02:23:01 -0400 Received: by mail-pj1-x1032.google.com with SMTP id mr5-20020a17090b238500b001c67366ae93so17719614pjb.4 for ; Sun, 27 Mar 2022 23:22:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=axtens.net; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=VfOy8LUSiO2JquI8aeAqUC85FdWyCYHCE7jTccNBL/U=; b=e9ZSIYocNT6KExTIEsgcKT4uQkwNilOAL7CCCSHqxhRJbDxHz8Y6oJ91QwiKESfKHG R9WLAteiH2iDB8oO1vs+CMZzUXNBz1vOw5JFnYo/gW/SoXmKSQmZPtBinjyNFhrXbMDT SokwwPtG0mG1p21XFmsGDWq16YT98zemczCz8= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=VfOy8LUSiO2JquI8aeAqUC85FdWyCYHCE7jTccNBL/U=; b=Mr3cEiptVAuiXA/xSihWwuCz46RVhIist4sVgOBRUtMlp8Of6VS+ogNX/YPMSni/iC 6OoOurohP99eVOmwIhBb4fa3hMr9cOUf2Z6m3hZ5i67tDpBxgUBFhq8VJNGZdFwECpEA ybdP9XNjwEZkP/reTjnKD+ZZnwJK19MZRRNjuBY4AXGrkvdhcsN4CypbQNolJOgdv7G3 pyJQj3TmOGj5tGxZdLP1PrWlyab9M2ykUSXYFNyAQzdVCBwWrSUqPSrVpvAHJpu+vGQE IWXP95B1az67d9VZ6pNg6tOWpsRoKqWFg3JuFJolvdZ3kLFQs1q9S4jWlme+ahZfIX/Y PC9w== X-Gm-Message-State: AOAM533eG2Biwj5rrEbcVCY46OE/efowZH+MSQTBe4wekamD0y9/N+e5 n8deMP1TzsynJ/9l8XslFnt1XeCD8bjvPg== X-Google-Smtp-Source: ABdhPJwhKWGEAhCQmxYdF9KveZ7/pDn0kJtNEpCMjRy1PwJ2Ep4spwzVofxpmY8rfqZ9K7PD2evmQA== X-Received: by 2002:a17:902:f243:b0:154:57eb:c748 with SMTP id j3-20020a170902f24300b0015457ebc748mr24523020plc.164.1648448578069; Sun, 27 Mar 2022 23:22:58 -0700 (PDT) Received: from localhost ([2001:4479:e000:e400:743e:bc3e:ec72:bf20]) by smtp.gmail.com with ESMTPSA id j6-20020a17090a588600b001c699d77503sm12532537pji.2.2022.03.27.23.22.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 27 Mar 2022 23:22:57 -0700 (PDT) From: Daniel Axtens To: grub-devel@gnu.org Cc: leif@nuviainc.com, stefanb@linux.ibm.com, ps@pks.im, dkiper@net-space.pl, Daniel Axtens Subject: [PATCH v2 03/15] mm: when adding a region, merge with region after as well as before Date: Mon, 28 Mar 2022 17:22:28 +1100 Message-Id: <20220328062240.878781-4-dja@axtens.net> X-Mailer: git-send-email 2.32.0 In-Reply-To: <20220328062240.878781-1-dja@axtens.net> References: <20220328062240.878781-1-dja@axtens.net> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::1032 (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::1032; envelope-from=dja@axtens.net; helo=mail-pj1-x1032.google.com X-Spam_score_int: -6 X-Spam_score: -0.7 X-Spam_bar: / X-Spam_report: (-0.7 / 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, PDS_HP_HELO_NORDNS=0.659, RCVD_IN_DNSWL_NONE=-0.0001, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no 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: Mon, 28 Mar 2022 06:23:01 -0000 On x86_64-efi (at least) regions seem to be added from top down. The mm code will merge a new region with an existing region that comes immediately before the new region. This allows larger allocations to be satisfied that would otherwise be the case. On powerpc-ieee1275, however, regions are added from bottom up. So if we add 3x 32MB regions, we can still only satisfy a 32MB allocation, rather than the 96MB allocation we might otherwise be able to satisfy. * Define 'post_size' as being bytes lost to the end of an allocation due to being given weird sizes from firmware that are not multiples of GRUB_MM_ALIGN. * Allow merging of regions immediately _after_ existing regions, not just before. As with the other approach, we create an allocated block to represent the new space and the pass it to grub_free() to get the metadata right. Tested-by: Stefan Berger Signed-off-by: Daniel Axtens --- v2: Thanks Daniel K for feedback. --- grub-core/kern/mm.c | 123 +++++++++++++++++++++++--------------- include/grub/mm_private.h | 9 +++ 2 files changed, 85 insertions(+), 47 deletions(-) diff --git a/grub-core/kern/mm.c b/grub-core/kern/mm.c index 079c28da7cdf..94e78f9a910d 100644 --- a/grub-core/kern/mm.c +++ b/grub-core/kern/mm.c @@ -130,53 +130,81 @@ grub_mm_init_region (void *addr, grub_size_t size) /* Attempt to merge this region with every existing region */ for (p = &grub_mm_base, q = *p; q; p = &(q->next), q = *p) - /* - * Is the new region immediately below an existing region? That - * is, is the address of the memory we're adding now (addr) + size - * of the memory we're adding (size) + the bytes we couldn't use - * at the start of the region we're considering (q->pre_size) - * equal to the address of q? In other words, does the memory - * looks like this? - * - * addr q - * |----size-----|-q->pre_size-|| - */ - if ((grub_uint8_t *) addr + size + q->pre_size == (grub_uint8_t *) q) - { - /* - * Yes, we can merge the memory starting at addr into the - * existing region from below. Align up addr to GRUB_MM_ALIGN - * so that our new region has proper alignment. - */ - r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN); - /* Copy the region data across */ - *r = *q; - /* Consider all the new size as pre-size */ - r->pre_size += size; - - /* - * If we have enough pre-size to create a block, create a - * block with it. Mark it as allocated and pass it to - * grub_free (), which will sort out getting it into the free - * list. - */ - if (r->pre_size >> GRUB_MM_ALIGN_LOG2) - { - h = (grub_mm_header_t) (r + 1); - /* block size is pre-size converted to cells */ - h->size = (r->pre_size >> GRUB_MM_ALIGN_LOG2); - h->magic = GRUB_MM_ALLOC_MAGIC; - /* region size grows by block size converted back to bytes */ - r->size += h->size << GRUB_MM_ALIGN_LOG2; - /* adjust pre_size to be accurate */ - r->pre_size &= (GRUB_MM_ALIGN - 1); - *p = r; - grub_free (h + 1); - } - /* Replace the old region with the new region */ - *p = r; - return; - } + { + /* + * Is the new region immediately below an existing region? That + * is, is the address of the memory we're adding now (addr) + size + * of the memory we're adding (size) + the bytes we couldn't use + * at the start of the region we're considering (q->pre_size) + * equal to the address of q? In other words, does the memory + * looks like this? + * + * addr q + * |----size-----|-q->pre_size-|| + */ + if ((grub_uint8_t *) addr + size + q->pre_size == (grub_uint8_t *) q) + { + /* + * Yes, we can merge the memory starting at addr into the + * existing region from below. Align up addr to GRUB_MM_ALIGN + * so that our new region has proper alignment. + */ + r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN); + /* Copy the region data across */ + *r = *q; + /* Consider all the new size as pre-size */ + r->pre_size += size; + + /* + * If we have enough pre-size to create a block, create a + * block with it. Mark it as allocated and pass it to + * grub_free (), which will sort out getting it into the free + * list. + */ + if (r->pre_size >> GRUB_MM_ALIGN_LOG2) + { + h = (grub_mm_header_t) (r + 1); + /* block size is pre-size converted to cells */ + h->size = (r->pre_size >> GRUB_MM_ALIGN_LOG2); + h->magic = GRUB_MM_ALLOC_MAGIC; + /* region size grows by block size converted back to bytes */ + r->size += h->size << GRUB_MM_ALIGN_LOG2; + /* adjust pre_size to be accurate */ + r->pre_size &= (GRUB_MM_ALIGN - 1); + *p = r; + grub_free (h + 1); + } + /* Replace the old region with the new region */ + *p = r; + return; + } + + /* + * Is the new region immediately above an existing region? That + * is: + * q addr + * ||-q->post_size-|----size-----| + */ + if ((grub_uint8_t *)q + sizeof(*q) + q->size + q->post_size == + (grub_uint8_t *) addr) + { + /* + * Yes! Follow a similar pattern to above, but simpler. + * Our header starts at address - post_size, which should align us + * to a cell boundary. + */ + h = (grub_mm_header_t) ((grub_uint8_t *)addr - q->post_size); + /* our size is the allocated size plus post_size, in cells */ + h->size = (size + q->post_size) >> GRUB_MM_ALIGN_LOG2; + h->magic = GRUB_MM_ALLOC_MAGIC; + /* region size grows by block size converted back to bytes */ + q->size += h->size << GRUB_MM_ALIGN_LOG2; + /* adjust new post_size to be accurate */ + q->post_size = (q->post_size + size) & (GRUB_MM_ALIGN - 1); + grub_free (h + 1); + return; + } + } /* Allocate a region from the head. */ r = (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN); @@ -195,6 +223,7 @@ grub_mm_init_region (void *addr, grub_size_t size) 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; /* Find where to insert this region. Put a smaller one before bigger ones, to prevent fragmentation. */ diff --git a/include/grub/mm_private.h b/include/grub/mm_private.h index d3f2321e14fb..64d88ee86915 100644 --- a/include/grub/mm_private.h +++ b/include/grub/mm_private.h @@ -81,8 +81,17 @@ typedef struct grub_mm_region */ grub_size_t pre_size; + /* + * Likewise, the post-size is the number of bytes we wasted at the end + * of the allocation because it wasn't a multiple of GRUB_MM_ALIGN + */ + grub_size_t post_size; + /* How many bytes are in this region? (free and allocated) */ grub_size_t size; + + /* pad to a multiple of cell size */ + char padding[3 * GRUB_CPU_SIZEOF_VOID_P]; } *grub_mm_region_t; -- 2.32.0