From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.90_1) id 1pI2cI-0005Pk-F2 for mharc-grub-devel@gnu.org; Wed, 18 Jan 2023 02:12:14 -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 1pI2cF-0005Of-JK for grub-devel@gnu.org; Wed, 18 Jan 2023 02:12:12 -0500 Received: from wout2-smtp.messagingengine.com ([64.147.123.25]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pI2cB-0004CK-Mr for grub-devel@gnu.org; Wed, 18 Jan 2023 02:12:10 -0500 Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailout.west.internal (Postfix) with ESMTP id 9CF6D320025E; Wed, 18 Jan 2023 02:12:02 -0500 (EST) Received: from mailfrontend2 ([10.202.2.163]) by compute5.internal (MEProxy); Wed, 18 Jan 2023 02:12:02 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pks.im; h=cc:cc :content-type:date:date:from:from:in-reply-to:in-reply-to :message-id:mime-version:references:reply-to:sender:subject :subject:to:to; s=fm3; t=1674025922; x=1674112322; bh=kA+BKlv6Tm p1Q/05bqYN9g32LSTJdVJ4M7fk66XGBcM=; b=KIPvLY2J+wR5GITDSkRRhjS8RR 3aNE0n2mMMmEd/PKzjxY1US1CksUV56oTwPAOiA616O+Bfu3CfIGvMwVrn5km8SN KKkG5LPgH5zdRIeKM/rodm201TcaVt0g6z9b2/ZLPBiB+n928hC2OCJsYZ/Ql6C4 xG890x8G289ofkyJSRf/ZOSJBdgd9JHY89BCEHwv+ZCc8TDow0Mln5VijVVg5A0G 2j3zJXsWcsdy1tauiYV52Nhhg6bzWxtQaSRyx1ZH0N1Zo3oTuCfZ+V97elvGOs8p 6RMYyGnrezfWXiVjWaRtdvFzdDTrHnF9/eqAZFfqfsTi7FPNgVH1DGqVoLVw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-type:date:date:feedback-id :feedback-id:from:from:in-reply-to:in-reply-to:message-id :mime-version:references:reply-to:sender:subject:subject:to:to :x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s= fm3; t=1674025922; x=1674112322; bh=kA+BKlv6Tmp1Q/05bqYN9g32LSTJ dVJ4M7fk66XGBcM=; b=hubaPKThGixtZZel2l8bF64wDqtRwGRBcbdny3Dw83Xz dOTb+RBQw8uxKIQaKAG9lrijdeey1OHtSVf4ZDygVCZahiy+82b3YcmfRF2aE8p4 v1mal7Pv2RhMPf5k8EkfMcL2oFi5VJv7Bja+Q4r3dio3ExR/v6dkZ3RUWutsGV1o ZosHNkS8XH8W5lEsB58pJEaEChpgkhMhin7/q7SKaith7OvySMH+a4Dis3SXbJsb ikU7Qlby0SjdmMSdXi7lC6ZRKU0vUv0PdJ7Lx2kncH2yrn4cCHqVvBTVatkBGA40 sBUCdx20AuQ2W9lFnbqQ+R6mDeqgEVXyZy4upjJG9A== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvhedruddtjedguddtjecutefuodetggdotefrod ftvfcurfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfgh necuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmd enucfjughrpeffhffvvefukfhfgggtuggjsehgtderredttddvnecuhfhrohhmpefrrght rhhitghkucfuthgvihhnhhgrrhguthcuoehpshesphhkshdrihhmqeenucggtffrrghtth gvrhhnpeeukedtvedtffevleejtefgheehieegkeeluddvfeefgeehgfeltddtheejleff teenucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehpsh esphhkshdrihhm X-ME-Proxy: Feedback-ID: i197146af:Fastmail Received: by mail.messagingengine.com (Postfix) with ESMTPA; Wed, 18 Jan 2023 02:12:01 -0500 (EST) Received: by pks.im (OpenSMTPD) with ESMTPSA id 7d97d18a (TLSv1.3:TLS_AES_256_GCM_SHA384:256:NO); Wed, 18 Jan 2023 07:11:36 +0000 (UTC) Date: Wed, 18 Jan 2023 08:11:55 +0100 From: Patrick Steinhardt To: The development of GNU GRUB Cc: Zhang Boyang Subject: Re: [PATCH v4 1/2] mm: Adjust new region size to take management overhead into account Message-ID: References: <20230114132323.132210-1-zhangboyang.id@gmail.com> <20230114132323.132210-2-zhangboyang.id@gmail.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="lMq3qfLi540ZzJHC" Content-Disposition: inline In-Reply-To: <20230114132323.132210-2-zhangboyang.id@gmail.com> Received-SPF: pass client-ip=64.147.123.25; envelope-from=ps@pks.im; helo=wout2-smtp.messagingengine.com X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 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, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-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: Wed, 18 Jan 2023 07:12:12 -0000 --lMq3qfLi540ZzJHC Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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. >=20 > 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). >=20 > 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. >=20 > Signed-off-by: Zhang Boyang > --- > grub-core/kern/mm.c | 64 ++++++++++++++++++++++++++++++++++++++++++--- > 1 file changed, 61 insertions(+), 3 deletions(-) >=20 > 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 @@ > =20 > =0C > =20 > +/* > + * 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 s/success/succeeds > + * 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 belo= w: > + * > + * +-- addr > + * v |<- size ->| > + * +---------+----------------+----------------+--------------+---------+ > + * | padding | grub_mm_region | grub_mm_header | usable bytes | padding | > + * +---------+----------------+----------------+--------------+---------+ > + * |<- a ->|<- b ->|<- c ->|<- d ->|<- e ->| > + * ^ > + * b =3D=3D sizeof (struct grub_mm_region) +--/ This will be the= pointer > + * c =3D=3D sizeof (struct grub_mm_header) | returned by next > + * d =3D=3D size | grub_malloc(size= ), > + * | if no other suitable= free > + * Assuming addr % GRUB_MM_ALIGN =3D=3D 1, then \ block is availab= le. > + * a =3D=3D GRUB_MM_ALIGN - 1 > + * > + * Assuming size % GRUB_MM_ALIGN =3D=3D 1, then > + * e =3D=3D GRUB_MM_ALIGN - 1 > + * > + * Therefore, the maximum overhead is: > + * a + b + c + e =3D=3D (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)) Great explanation! > +/* The size passed to grub_mm_add_region_fn() is aligned up by this valu= e. */ > +#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; > =20 > @@ -230,6 +270,11 @@ grub_mm_init_region (void *addr, grub_size_t size) > =20 > 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 cod= e. > + */ > + > /* Allocate a region from the head. */ > r =3D (grub_mm_region_t) ALIGN_UP ((grub_addr_t) addr, GRUB_MM_ALIGN); > =20 > @@ -410,6 +455,7 @@ grub_memalign (grub_size_t align, grub_size_t size) > { > grub_mm_region_t r; > grub_size_t n =3D ((size + GRUB_MM_ALIGN - 1) >> GRUB_MM_ALIGN_LOG2) += 1; > + grub_size_t grow; > int count =3D 0; > =20 > 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; > =20 > + /* > + * 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 =3D ALIGN_UP (grow, GRUB_MM_HEAP_GROW_ALIGN); > + > /* 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; > =20 > align =3D (align >> GRUB_MM_ALIGN_LOG2); > @@ -447,7 +505,7 @@ grub_memalign (grub_size_t align, grub_size_t size) > count++; > =20 > if (grub_mm_add_region_fn !=3D NULL && > - grub_mm_add_region_fn (size, GRUB_MM_ADD_REGION_CONSECUTIVE) = =3D=3D GRUB_ERR_NONE) > + grub_mm_add_region_fn (grow, GRUB_MM_ADD_REGION_CONSECUTIVE) = =3D=3D GRUB_ERR_NONE) > goto again; > =20 > /* 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 partia= lly > * 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; > } Regardless of the one grammar fix: Reviewed-by: Patrick Steinhardt Patrick --lMq3qfLi540ZzJHC Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAABCgAdFiEEF9hrgiFbCdvenl/rVbJhu7ckPpQFAmPHm7oACgkQVbJhu7ck PpReeRAAof98CmihDpu3l0AxnTFFz4g0FGBMNE0QijL5DSsg/m0W9ZjDUal/8gLR f8fa+Ptm6UkP+WgMfxlBcDO4EK1IfYOW8imIcHLuEQ+Ci8iYJ6CbSAAysgyx8J3P mxmE0wJYzxrTQ/rGPozjxY53FWUhJNe9Kqo72Oj5hxC03b99TCM/Tpx/viETxaIc 95KdyEZMuimduOpEt//HeuxT75vkYk3uTCW3Wrley4ebLy8HyKwQgY5hIM6PKIom RfnAGTISn/kEb+v1uaeM23dBWjLLcfB5Qp3w498m3Gc4eKju8s6ymd0TGAQDHMlP P4KhdafTu9Zx8ptWqKaTC19sLwPLyFDc/A8WEuXbHQdvH8NOG9jf/iTjOmziK5sr rALvmqewJKojeSeFzRcZqDEIgA1jpSyRWykjWQJJo8s/D9Tl2B+DqoE8G/ksNiOb LG2yq58++AFulO/u9oT+M0gJiEN991QM3hVQzQGgtV3RkhCbPsjURciZBXyE1vNH GV0jtSAKLpGQeqE3+mnMrZzdSRt1VkXeBYtRot4zOiOx+oDKYIiK+cpqeFpkdtme CUy8K5M2eH+VWrVsFeOrpKcojcUiKUGufZVdE0yfYwlIzel407mSOoyXKEYXTyl9 iVR7qVepQN+blSqf8n7MKzocVB/XZ4D87Hhj7tyOhJf1uqtbmq0= =nrSR -----END PGP SIGNATURE----- --lMq3qfLi540ZzJHC--