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 5AD8DE78480 for ; Sun, 1 Oct 2023 19:09:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A8AA96B0188; Sun, 1 Oct 2023 15:09:53 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A3B196B0189; Sun, 1 Oct 2023 15:09:53 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 902216B018B; Sun, 1 Oct 2023 15:09:53 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 818806B0188 for ; Sun, 1 Oct 2023 15:09:53 -0400 (EDT) Received: from smtpin21.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 477C512020F for ; Sun, 1 Oct 2023 19:09:53 +0000 (UTC) X-FDA: 81297832266.21.A4F7D8C Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by imf13.hostedemail.com (Postfix) with ESMTP id DBA2920005 for ; Sun, 1 Oct 2023 19:09:50 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=N3LbuQqr; spf=pass (imf13.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-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696187391; a=rsa-sha256; cv=none; b=KNHS59tLg4jFSUEyj9UPUcX2s+MHOqXg19gLbxbC7MVZ58lq2M9nTgKrrYPBOHqq6y5Q9g r8B+EBI8awv4MmbVTVzE2vxwlToB3SAkkmAWvvSjamcaSusEEzvlS4dlvH0AK0M20knsaf PljT1CUkw1J/mRNXioLkAQ9XPI5vBZU= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=N3LbuQqr; spf=pass (imf13.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=1696187391; 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:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=rzNa+yFRZPsImSw8R8zFGrvn2PGk/APuc3mTf953Zfo=; b=m6/KpYWhPX6UK4Mu0TZWIJLTenKw2RWHubaiwVGdAS+gal9EizxFbrxE+KRKq+yzpQwvTY oTO1+UC3gLXLNA03A2L2vEVkmTI56s07l4oZldIv6H/GBj/xEQ+d1XK43VFQcu0FVhDQet bria4YuTYj6PDPyhQBLv5K0T1jgdCuI= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id 7A3C5CE0ACB; Sun, 1 Oct 2023 19:09:47 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 0C705C433C8; Sun, 1 Oct 2023 19:09:44 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1696187386; bh=RCtF0SAyhjrnird/rD2v5mjxI/QUyWsCL5YSlocwGqo=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=N3LbuQqrLDlJN73wm++LycnNJwYfQGJQg6r/ILbdkPXJGJ4/jyGrrszR1X1PPmgPo H7JUgStMOcz8/gi8qz5fZtf8+5HFqE7fYIF/4LI60E7OHMJHvqQEmpt2b4hKXo/nuv 73W3j+mueX7vRUcl3sq8YNencUWDqrF4enOkdWJI9xDl/vIXoiRlc1O6dOCfSG7f2o 77PzRRcCqBTyZjfRp7XCKVuZVXjOq8maPidE4ioQHAqoyrhx3ai/gOChXZGkyCBEP6 2rR5NSyzww+ORi182nQj9ex2dHsJVoczbxHAuuHq8T87RINag5YXyRwEGKb7e5amsx XXOerre0vZViQ== Date: Sun, 1 Oct 2023 22:08:46 +0300 From: Mike Rapoport To: Yajun Deng Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH] memblock: don't run loop in memblock_add_range() twice Message-ID: <20231001190846.GY3303@kernel.org> References: <20230927013752.2515238-1-yajun.deng@linux.dev> <20230928061619.GS3303@kernel.org> <3ee9c8e4-870c-4ab0-906a-7d214031d1a6@linux.dev> <20230929090406.GV3303@kernel.org> <812f0818-9658-3107-3a45-a913b7afc3c3@linux.dev> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <812f0818-9658-3107-3a45-a913b7afc3c3@linux.dev> X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: DBA2920005 X-Stat-Signature: 55htj1t9uto9pqnui3rs59d5ucts7jsp X-Rspam-User: X-HE-Tag: 1696187390-514351 X-HE-Meta: U2FsdGVkX19kEoCZTS0uAL/B0eSv8CTIfyOQxFW+EYM1zREDcIIGIM1KgOKftA0mGqukAnrLnIUC+94b7Ebfgm1CeQkF4IO8z1aSJNirurQyIiv+BYVgeutZyHH7kFcZvXnrRGgPw6l7j5s1LxXg2fhFPGmSD4jv655/+1yGuY/uoHD4at1/2Ibeu4z2EskahwJgd00FciC9XY4kJh57lBqOijxYGx4lK+ZnXSsiFfpoH0hOekFLuX/Aph8yauQrCz0PuRokxcok+meOIObT4PLPap4QCCbkTIrP/k+rsJ+M8c1/ktUdrvoO+Jksw5FyjAOB3Ot0ueCnXBJiS6CFND+mrQItlS8tomm9Oy3u8XfHubhchTSQa51lye8wCfw+dBHPgQYhoa0kiZ4Vu/rdbn8lOV4MmYlLLXxIu6nQMOoPC/kC2yUMXWszJnB2WaA7/NSLwzxYX/Tk/277Nm73zAixi8sf6P30qXPSywnhnXLfKaYfgyiw0paKDqN1flnZLcLqCqF+HRClcc+aP7TtbpsYzRsmV1Ux/JhgM8ONWf8K7jhTeY19n5Kg+XJHY1EJY9RBGz+yZlujQNhPHKFaspp3YO2OuejRtp4PYvsMnTNKakTq0QRz6pMRlx7/Y+kcGu8sG33XBiV8ctHi9tbTlNqam6r+lGPqO2jjEks/Idr/q1lMaMdPlqt4t17MpgV4HEbo2pMirz/DMCMkI7zT7F+wiZb565Nv5PTmKMn2fDub472hzqb+3XWxbf9pLYwMttHlOn4SW35IlaO69J2yiG37W8o1Hj64JqVh6qRlylHsFifPcIhHIE+L++WfqzTd2jXnBfDwv/QmVKNQwGaFLWX0g2wzgNlZ489BU1/Z4oq7sPentGxbtrq0LgRMq1LWMrX93GOmWy1fYAShpCeM/4V6gWY5JLFMTSCLb6vAHMdxLNiQLX5FNOVRPTAQXVIk5IdycoA0MufulvNUj9L 4nJDWmNa rwUkp2xOcBIKq92EDYjSTP5I4ZtxoIkWg0ioZhNXoehKxVwRmvDho/EwoHFd54a5e1adoOZGOrIfcIeFRer1t0+844c2LcqUyZO/qAoTywNhTtQY4SvwC1/2A3RUZKKA9zFEkX8MZ9iugCZdjJ8NGr40Ly36T7Q12KBl9tuyzij9501qwTOmpy3KGG40rZDvvX6UiNaXMkRPX5FbzqON+movux0yS532fdna0QgRhMxsQfrAl2gGLop3HvQ== 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: On Fri, Sep 29, 2023 at 06:10:50PM +0800, Yajun Deng wrote: > > On 2023/9/29 17:04, Mike Rapoport wrote: > > On Thu, Sep 28, 2023 at 04:47:59PM +0800, Yajun Deng wrote: > > > On 2023/9/28 14:16, Mike Rapoport wrote: > > > > On Wed, Sep 27, 2023 at 09:37:52AM +0800, Yajun Deng wrote: > > > > > There is round twice in memblock_add_range(). The first counts the number > > > > > of regions needed to accommodate the new area. The second actually inserts > > > > > them. But the first round isn't really needed, we just need to check the > > > > > counts before inserting them. > > > > > > > > > > Check the count before calling memblock_insert_region(). If the count is > > > > > equal to the maximum value, it needs to resize the array. Otherwise, > > > > > insert it directly. > > > > > > > > > > To avoid nested calls to memblock_add_range(), we need to call > > > > > memblock_reserve() out of memblock_double_array(). > > > > memblock_add_range() does an extra loop once in a while, but I don't think > > > > removing it will have any actual effect on the boot time. > > > > > > Yes, it has no obvious actual effect on the boot time,  but it does reduce > > > the number of unnecessary loop. > > > > > > The actual effect on the boot time should not be the only criterion for > > > whether a patch is accepted or not. > > > > > > Since the comment in the previous code, it tells the user that it would be > > > executed twice, this can be misleading to users. > > > > > > So the new code will be simpler and clearer. It not just change the code, > > > but also remove the comment > > Adding return-by-pointer parameters to memblock_double_array() and pulling > > memblock_reserve() out of this function is in no way simpler and clearer > > that having an extra loop. > > If memblock_reserve() in memblock_double_array(),  there will be nested > calls to memblock_add_range(). > > memblock_add_range(A)->memblock_double_array(A)->memblock_reserve(B)->memblock_add_range(B) > > ->memblock_insert_region(B)->memblock_merge_regions(B)->memblock_insert_region(A)->memblock_merge_regions(A) > > It's hard to see that and debug. > > If memblock_reserve() out of memblock_double_array(),  there wouldn't have a > nested calls. With memblock_reserve() out of memblock_double_array(), the latter stops being self-contained, which makes the code less readable and less maintainable. > memblock_add_range(A)->memblock_double_array(A)->memblock_insert_region(A)->memblock_merge_regions(A)-> > > memblock_reserve(B)->memblock_add_range(B)->memblock_insert_region(B)->memblock_merge_regions(B) > > We should make memblock_add_range is done, and do another > memblock_add_range. Sorry, I do not follow you here. > > If the comment is wrong, just fix the comment. > > > about "executed twice",  it obviously tells the user only resize the array > > > if it is equal to the maximum value > > > > > > and doesn't need to be executed twice. > > > > > > > > Signed-off-by: Yajun Deng > > > > > --- > > > > > mm/memblock.c | 117 ++++++++++++++++++++++++-------------------------- > > > > > 1 file changed, 57 insertions(+), 60 deletions(-) > > > > > > > > > > diff --git a/mm/memblock.c b/mm/memblock.c > > > > > index 5a88d6d24d79..3f44c84f5d0b 100644 > > > > > --- a/mm/memblock.c > > > > > +++ b/mm/memblock.c > > > > > @@ -400,6 +400,8 @@ void __init memblock_discard(void) > > > > > * @type: memblock type of the regions array being doubled > > > > > * @new_area_start: starting address of memory range to avoid overlap with > > > > > * @new_area_size: size of memory range to avoid overlap with > > > > > + * @new_reserve_base: starting address of new array > > > > > + * @new_reserve_size: size of new array > > > > > * > > > > > * Double the size of the @type regions array. If memblock is being used to > > > > > * allocate memory for a new reserved regions array and there is a previously > > > > > @@ -412,7 +414,9 @@ void __init memblock_discard(void) > > > > > */ > > > > > static int __init_memblock memblock_double_array(struct memblock_type *type, > > > > > phys_addr_t new_area_start, > > > > > - phys_addr_t new_area_size) > > > > > + phys_addr_t new_area_size, > > > > > + phys_addr_t *new_reserve_base, > > > > > + phys_addr_t *new_reserve_size) > > > > > { > > > > > struct memblock_region *new_array, *old_array; > > > > > phys_addr_t old_alloc_size, new_alloc_size; > > > > > @@ -490,11 +494,13 @@ static int __init_memblock memblock_double_array(struct memblock_type *type, > > > > > memblock_free(old_array, old_alloc_size); > > > > > /* > > > > > - * Reserve the new array if that comes from the memblock. Otherwise, we > > > > > - * needn't do it > > > > > + * Keep the address and size if that comes from the memblock. Otherwise, > > > > > + * we needn't do it. > > > > > */ > > > > > - if (!use_slab) > > > > > - BUG_ON(memblock_reserve(addr, new_alloc_size)); > > > > > + if (!use_slab) { > > > > > + *new_reserve_base = addr; > > > > > + *new_reserve_size = new_alloc_size; > > > > > + } > > > > > /* Update slab flag */ > > > > > *in_slab = use_slab; > > > > > @@ -588,11 +594,12 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > > > > > phys_addr_t base, phys_addr_t size, > > > > > int nid, enum memblock_flags flags) > > > > > { > > > > > - bool insert = false; > > > > > phys_addr_t obase = base; > > > > > phys_addr_t end = base + memblock_cap_size(base, &size); > > > > > - int idx, nr_new, start_rgn = -1, end_rgn; > > > > > + phys_addr_t new_base = 0, new_size; > > > > > + int idx, start_rgn = -1, end_rgn; > > > > > struct memblock_region *rgn; > > > > > + unsigned long ocnt = type->cnt; > > > > > if (!size) > > > > > return 0; > > > > > @@ -608,25 +615,6 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > > > > > return 0; > > > > > } > > > > > - /* > > > > > - * The worst case is when new range overlaps all existing regions, > > > > > - * then we'll need type->cnt + 1 empty regions in @type. So if > > > > > - * type->cnt * 2 + 1 is less than or equal to type->max, we know > > > > > - * that there is enough empty regions in @type, and we can insert > > > > > - * regions directly. > > > > > - */ > > > > > - if (type->cnt * 2 + 1 <= type->max) > > > > > - insert = true; > > > > > - > > > > > -repeat: > > > > > - /* > > > > > - * The following is executed twice. Once with %false @insert and > > > > > - * then with %true. The first counts the number of regions needed > > > > > - * to accommodate the new area. The second actually inserts them. > > > > > - */ > > > > > - base = obase; > > > > > - nr_new = 0; > > > > > - > > > > > for_each_memblock_type(idx, type, rgn) { > > > > > phys_addr_t rbase = rgn->base; > > > > > phys_addr_t rend = rbase + rgn->size; > > > > > @@ -644,15 +632,23 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > > > > > WARN_ON(nid != memblock_get_region_node(rgn)); > > > > > #endif > > > > > WARN_ON(flags != rgn->flags); > > > > > - nr_new++; > > > > > - if (insert) { > > > > > - if (start_rgn == -1) > > > > > - start_rgn = idx; > > > > > - end_rgn = idx + 1; > > > > > - memblock_insert_region(type, idx++, base, > > > > > - rbase - base, nid, > > > > > - flags); > > > > > - } > > > > > + > > > > > + /* > > > > > + * If type->cnt is equal to type->max, it means there's > > > > > + * not enough empty region and the array needs to be > > > > > + * resized. Otherwise, insert it directly. > > > > > + */ > > > > > + if ((type->cnt == type->max) && > > > > > + memblock_double_array(type, obase, size, > > > > > + &new_base, &new_size)) > > > > > + return -ENOMEM; > > > > > + > > > > > + if (start_rgn == -1) > > > > > + start_rgn = idx; > > > > > + end_rgn = idx + 1; > > > > > + memblock_insert_region(type, idx++, base, > > > > > + rbase - base, nid, > > > > > + flags); > > > > > } > > > > > /* area below @rend is dealt with, forget about it */ > > > > > base = min(rend, end); > > > > > @@ -660,33 +656,28 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > > > > > /* insert the remaining portion */ > > > > > if (base < end) { > > > > > - nr_new++; > > > > > - if (insert) { > > > > > - if (start_rgn == -1) > > > > > - start_rgn = idx; > > > > > - end_rgn = idx + 1; > > > > > - memblock_insert_region(type, idx, base, end - base, > > > > > - nid, flags); > > > > > - } > > > > > + if ((type->cnt == type->max) && > > > > > + memblock_double_array(type, obase, size, > > > > > + &new_base, &new_size)) > > > > > + return -ENOMEM; > > > > > + > > > > > + if (start_rgn == -1) > > > > > + start_rgn = idx; > > > > > + end_rgn = idx + 1; > > > > > + memblock_insert_region(type, idx, base, end - base, > > > > > + nid, flags); > > > > > } > > > > > - if (!nr_new) > > > > > + if (ocnt == type->cnt) > > > > > return 0; > > > > > - /* > > > > > - * If this was the first round, resize array and repeat for actual > > > > > - * insertions; otherwise, merge and return. > > > > > - */ > > > > > - if (!insert) { > > > > > - while (type->cnt + nr_new > type->max) > > > > > - if (memblock_double_array(type, obase, size) < 0) > > > > > - return -ENOMEM; > > > > > - insert = true; > > > > > - goto repeat; > > > > > - } else { > > > > > - memblock_merge_regions(type, start_rgn, end_rgn); > > > > > - return 0; > > > > > - } > > > > > + memblock_merge_regions(type, start_rgn, end_rgn); > > > > > + > > > > > + /* Reserve the new array */ > > > > > + if (new_base) > > > > > + memblock_reserve(new_base, new_size); > > > > > + > > > > > + return 0; > > > > > } > > > > > /** > > > > > @@ -755,6 +746,7 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type, > > > > > int *start_rgn, int *end_rgn) > > > > > { > > > > > phys_addr_t end = base + memblock_cap_size(base, &size); > > > > > + phys_addr_t new_base = 0, new_size; > > > > > int idx; > > > > > struct memblock_region *rgn; > > > > > @@ -764,10 +756,15 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type, > > > > > return 0; > > > > > /* we'll create at most two more regions */ > > > > > - while (type->cnt + 2 > type->max) > > > > > - if (memblock_double_array(type, base, size) < 0) > > > > > + if (type->cnt + 2 > type->max) { > > > > > + if (memblock_double_array(type, base, size, > > > > > + &new_base, &new_size)) > > > > > return -ENOMEM; > > > > > + if (new_base) > > > > > + memblock_reserve(new_base, new_size); > > > > > + } > > > > > + > > > > > for_each_memblock_type(idx, type, rgn) { > > > > > phys_addr_t rbase = rgn->base; > > > > > phys_addr_t rend = rbase + rgn->size; > > > > > -- > > > > > 2.25.1 > > > > > -- Sincerely yours, Mike.