From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6521DC07E8E for ; Wed, 24 Apr 2024 13:16:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E72396B0286; Wed, 24 Apr 2024 09:16:52 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E218F6B0287; Wed, 24 Apr 2024 09:16:52 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id CC2A56B0288; Wed, 24 Apr 2024 09:16:52 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id AF8176B0286 for ; Wed, 24 Apr 2024 09:16:52 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 6126216107D for ; Wed, 24 Apr 2024 13:16:52 +0000 (UTC) X-FDA: 82044475464.14.9CBE324 Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by imf08.hostedemail.com (Postfix) with ESMTP id 0014716002A for ; Wed, 24 Apr 2024 13:16:49 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=b0BWl7hq; spf=pass (imf08.hostedemail.com: domain of rppt@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1713964610; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=dwYPijUyOfiR/D2DegszwsIljzoF8rcS78pqHNW5ikg=; b=0XQBG95NHgh7tf3WnrxNZ/Mvy0YZ5R9kyidw4TcOnEOnZvDEmcJj634A0XgSCqpBceG5Zf LLfDXvFmAv+AIH8vWBmYvcaPfPMZ4eXqe9S4toWzDEYT0msLPevt/yn4AkJcknDIB1hGIP mfZKIN3U34jI3WMhvw/COFxCmxBFkSQ= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1713964610; a=rsa-sha256; cv=none; b=AKWESlJ470QMYvHdUqHT7cm+4lkIV5Tfpc4mx8bRJHFmjrbHq7h8Z58AyjATKa+AfAfQCz AKWIKXpv1+2P7gxF6wTdgYeBOVMyyhYlwRfdm1qxEq4jf9Q9qGJO4J78LyzYh9EgaxieK7 URuvkXbH7vmXEBeqiF9cT8jU2rxGWp8= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=b0BWl7hq; spf=pass (imf08.hostedemail.com: domain of rppt@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=none) header.from=kernel.org Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id 1D3C0CE16DE; Wed, 24 Apr 2024 13:16:47 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 5574EC113CE; Wed, 24 Apr 2024 13:16:44 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713964606; bh=7WI8t7njgtIwfyuvzKF21Z/Q8ZvYdf8gQhNcEMIlE68=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=b0BWl7hq2dHdENTr9y1i4vlmEJ4LkgA7jFU6jaCs5idWDFEkrNCR5gOBNqbXS7QMK iYIKrD/VLTX807yK1STmfPzhtf7tCi4RYt6MCgwgfatsWe39oyp+WSkpiyWKy0bpbU X3EtFEioB1CVXuSky5RSvTJF8zm/1Tj+yQ6ryu1q/vXrHN3CgRqiPb/vLQIz+BJj3y kTKrQrCExkKyQZbxqTK9RGa1yvGE9OkgD6UrhNHuGksEM50TAc4EYjaCeFIANrOWqw Jsp8K67PqMnglTgpwl569wbvqUvBa3YiBuuXBvZqTb3RGI2dqy2ALyTn01ot/oTyzD fma5d+tClXeCQ== Date: Wed, 24 Apr 2024 16:15:30 +0300 From: Mike Rapoport To: Wei Yang Cc: akpm@linux-foundation.org, linux-mm@kvack.org, Jinyu Tang , Peng Zhang Subject: Re: [PATCH 1/6] mm/memblock: reduce the two round insertion of memblock_add_range() Message-ID: References: <20240414004531.6601-1-richard.weiyang@gmail.com> <20240422025500.n5542xmrc3zy4qgb@master> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20240422025500.n5542xmrc3zy4qgb@master> X-Rspam-User: X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: 0014716002A X-Stat-Signature: f4a1n4jk8g51yj9g1396qsj9wkhkeiig X-HE-Tag: 1713964609-821042 X-HE-Meta: U2FsdGVkX19WketfRBRSef2TsiFKp8JawPOudE7rHS8Lyf9pkPYsZcz73ZZFyqAEhUEtXFNymgDN3F+silbZm0YunoIejfk/cWPGSQFG8f/N+kqYkhKdXXWkpbML421k1bAHZAUpibuwMtXFaIYQOKmF8Yfy747f4GvjOlGbrMfv38IP61vmbpZ8Jdz+8bIWKpRewse8uxJSTGV8+xVr/Scp2IS6+D4UF7GOaRsGkPKwRagR91sH7u8Mpte24SfvJXjji/v37uSExAY78MQDnjWyL0GrD5ItWZ7gb85nbq5T6kpaSz0Tr0ZlSegpdNt7wxtnlWgU+QreyRMP9GWWxm/ooFFV236JEDrmugT5IJiJyaJDM0jQKqIaha3khua10IpGu/mnW0LrIJPac39T/ghD971p7TdYxJNO1qi4N6jazv1wPP6R060FcLoxNLPr7BIMQdHKWWeUOFVrx7fpoYZfgz9JGvgKgC70aa6DBesmk8yqIm2I6OBzuo4PDs5DQSZEmEj16IlSbtpSnhK9z3m9GEpaQmN+NgkHjIb/BIzs+19xls5Bze0PpZG9AzVHI4sF3ggo+z0GN/f5anStLYciHKOGeA32ba+q2MPMnzAnxyD8hW9wD02NrskfY2EihXsaBIEU6r7d7LpJsiKpI8cLdoAijtGDT+dBWcOqVGy+GSl536irGW7QWr6b2u/WFBB0Q7ExL6/45gGE37WcULhLkPTJn4nxCMyKdOvqkyo5vcMfjdV8xl2lrXWidDhAJeJK+a8ix/od0IVrBpyOyXYypD0mftkc0Ai+zax7PX5n9rUiEeeoW9DkQ2POFzngARhDf2D6mRltQ7tC8loI6ZcRM6Mt5qCowyZdMqsiY5dE8qfhaXtxRk08KNnvJjiL08435mz1C0dR0GHN6JIyDjyg84c9j3aFeKzKzdHMXPOcO5M85avTo78E6tXez27K6Rc55YRludmGCGF0UWz IYCVMPkc /rc9wZPdmLgR3sTY1b07RS5o8++AgCwy30sbDCxl6E/Jl9rKAmnhtPrgryp1MoLWBeI72pqdShUXcZM05vacFXK1i+WMJacWrgV0wLO/4KK1WHkkxYXu/2bgW99jLhHOx4c5HC9c7EhOem47aUnqXBfK8QcVe5PkX4l+BdQ/pov2eSQl8shdt3Pepr+9C538iAoehUUjiuAwuo8WLGpBhQIKm3nJS0HHyApizfqTBeg1mluenRopDq9MCEqhO1QOpEIPToLWjAmyo7B8VfLYH3jt7xfCAje6O/TsjJCn8ocNpUU9oQMxGR6CAE8DvJBWyRS7+30QheUhaUupA3kxUkscsXBjTubQ+7FYLfAux0+WyJYyRopZGYiTv4pCUGJBp7ee/ X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Mon, Apr 22, 2024 at 02:55:00AM +0000, Wei Yang wrote: > On Mon, Apr 15, 2024 at 06:17:56PM +0300, Mike Rapoport wrote: > >On Sun, Apr 14, 2024 at 12:45:26AM +0000, Wei Yang wrote: > >> Current memblock_add_range() does the insertion with two round > >> iteration. > >> > >> First round does the calculation of new region required, and second > >> round does the actual insertion. Between them, if current max can't meet > >> new region requirement, it is expanded. > >> > >> The worst case is: > >> > >> 1. cnt == max > >> 2. new range overlaps all existing region > >> > >> This means the final cnt should be (2 * max + 1). Since we always double > >> the array size, this means we only need to double the array twice at the > >> worst case, which is fairly rare. For other cases, only once array > >> double is enough. > >> > >> Let's double the array immediately when there is no room for new region. > >> This simplify the code a little. > > > >Very similar patch was posted a while ago: > >https://lore.kernel.org/all/20221025070943.363578-1-yajun.deng@linux.dev > > > >and it caused boot regression: > >https://lore.kernel.org/linux-mm/Y2oLYB7Tu7J91tVm@linux.ibm.com > > > > Got the reason for the error. > > When we add range to reserved and need double array, following call happends: > > memblock_add_range() > idx <- where we want to insert new range > memblock_double_array() > find available range for new regions > memblock_reserve() available range > memblock_insert_region() at idx > > The error case happens when find available range below what we want to add, > the idx may change after memblock_reserve(). > > The following change looks could fix it. I don't think the micro-optimization of the second loop in memblock_add_range() worth the churn and potential bugs. > diff --git a/mm/memblock.c b/mm/memblock.c > index 98d25689cf10..52bc9a4b20da 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -395,6 +395,7 @@ void __init memblock_discard(void) > /** > * memblock_double_array - double the size of the memblock regions array > * @type: memblock type of the regions array being doubled > + * @idx: current region index if we are iterating > * @new_area_start: starting address of memory range to avoid overlap with > * @new_area_size: size of memory range to avoid overlap with > * > @@ -408,6 +409,7 @@ void __init memblock_discard(void) > * 0 on success, -1 on failure. > */ > static int __init_memblock memblock_double_array(struct memblock_type *type, > + int *idx, > phys_addr_t new_area_start, > phys_addr_t new_area_size) > { > @@ -490,8 +492,24 @@ static int __init_memblock memblock_double_array(struct memblock_type *type, > * Reserve the new array if that comes from the memblock. Otherwise, we > * needn't do it > */ > - if (!use_slab) > + if (!use_slab) { > + /* > + * When double array for reserved.regions, we may need to > + * adjust the index on finding new_array below > + * new_area_start. This is because memblock_reserve() below > + * will insert the range ahead of us. > + * While the insertion may result into three cases: > + * 1. not adjacent any region, increase one index > + * 2. adjacent one region, not change index > + * 3. adjacent two regions, reduce one index > + */ > + int ocnt = -1; > + if (idx && type == &memblock.reserved && addr <= new_area_start) > + ocnt = type->cnt; > BUG_ON(memblock_reserve(addr, new_alloc_size)); > + if (ocnt >= 0) > + *idx += type->cnt - ocnt; > + } > > /* Update slab flag */ > *in_slab = use_slab; > > > -- > Wei Yang > Help you, Help me -- Sincerely yours, Mike.