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 C5E4FC04FF8 for ; Mon, 15 Apr 2024 15:19:11 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 429746B009A; Mon, 15 Apr 2024 11:19:11 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3D8BF6B009B; Mon, 15 Apr 2024 11:19:11 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2A04B6B009C; Mon, 15 Apr 2024 11:19:11 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 0993C6B009A for ; Mon, 15 Apr 2024 11:19:11 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id BCF63140529 for ; Mon, 15 Apr 2024 15:19:10 +0000 (UTC) X-FDA: 82012124460.08.968F3F5 Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by imf01.hostedemail.com (Postfix) with ESMTP id 67A714000B for ; Mon, 15 Apr 2024 15:19:08 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=FYHjNuQh; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf01.hostedemail.com: domain of rppt@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=rppt@kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1713194349; 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=EEHS2f7CeM0ZkuC23Ea83nSy5ri940MyEy1UHmGfh/M=; b=azI2vOsDfQdpm273JHgurYpeeHWenBCb+8iVkH0OnYrUi1BlNTpIX1ZpRR3X+jhBkrQ4FF UAD3S3Bssn/3hahTqV1B1+Bzd5qgVcFYhKSqKigVe+AWNvyQ8gXQqT75nJM2IYH6WLtPOO pgOTkN2A6r1RhhVkaw07mhf06knp5sM= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=FYHjNuQh; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf01.hostedemail.com: domain of rppt@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=rppt@kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1713194349; a=rsa-sha256; cv=none; b=JFmgZmvo0oZupv4w5xZqvAEu3vXwcb9rnqaujp8OZhum7q1RqVqHHo1TpHC8eYNC6DQD/a EogQU2cDScKzozobh6yZRHNV2kbCzbgqmyfg8BJA3B6k9KBgzOeCIiQhQJgyQFy60XfRhQ 1Enzgh/IsVIv2F6vOycW8Yw92DDosTk= Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id EB53DCE0E1A; Mon, 15 Apr 2024 15:19:03 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 60760C2BD10; Mon, 15 Apr 2024 15:19:01 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1713194343; bh=HmbpmTkUo8zyPDel8u7NBzZ/wS+dz3as/FzQSbj8cvQ=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=FYHjNuQh1NgyRnAwmFw5asotENnDKiTeVy6R6Zwxlkwy9bWrczmKn3YBpCvZ029jO I78vy0sX76eYK6rVsvU8s0G/mGTombgeWGYk2oV/U04560J4bhymXJ5wCmDv6rVd0y a1kRSAPmoJkQGH97prO2b7hAlpHSZ62cZoIvSNy/WUdDSVPVi8uOqm3PWmdOtpLUr2 nGD8oiAGx5ZOcMlNwzSLQ2RNKrKJxQgqHgZvPsvX0OHkC6qkOZMq6mJrCb8QrMVxam 4PwPIWjlskvAtbUsoU1Z3yU5PU10s6pZF+X5QGVqIXQaIfo+t7T4zzLzeUdc9Q6GQP rPbHSVLgFjZlw== Date: Mon, 15 Apr 2024 18:17:56 +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> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20240414004531.6601-1-richard.weiyang@gmail.com> X-Rspam-User: X-Stat-Signature: xuddtuwyn1hy1wbyjckid6ak4i8j9jof X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 67A714000B X-HE-Tag: 1713194348-274780 X-HE-Meta: U2FsdGVkX194q3kWN6pnRKUWRLVgFDcCH+2CsZjI8JgxrWJMRQvpODR3P5CE2zWwGaNEfhLfvxgLJ0SS00pUkpGj+9bAH138SW64PY+t4HSa7EAAnNPQR7CUaBGElfa66Vo8tByaFPElyQ4lRIRr2oRdCj8DHsrJFLCy1NGuDIDoR25ZsTiZh/5CCdEgp+fquGKoZViuemdo3x6J/hUwv1OrTjuJCdh/wnDPMTtJYa1gSf/vyKZ253tgM2auH//OhaddOSC1YnB4SIAYxeh2cLSb9eYYRzhhVgJpKaBCHh7vRKX6NcQOlIZYo8wh2Qfw8LT26mtMVIEDBXpKKJFNU++Ez0DC+Zs+vKpNLK0KYUDT5eUjJf5qeDBNuvd2xRPQNveOL+1rMT3leqrxr8FfNvf2/akAqdFU40Lu9zt54wrPUcz6a08BoGZYe7gRSjpXH0izI9z5dzTh+ZPhSMWicsI+fegTJX5hMsjYPJmhNY38GJMUJzTyUqbF21bekGvf3sXCX1GV8G4DuhpuxD3zkl7VyW3vntoTThJAiimT2V91Q3BgvubOD6ttTQ2kLAhQeb4ETIjjODTjlr6Y89KB/VYDurm9fr9zFTu5YRpBfHLznV7yLz9wWlnFODQOdwkCqHmloQgoFoFgBCQwBYU/CCtrr5mYduTTomrd6lajybTKbQYKb4ggplxMcPCtl39pzdqGljeZ7E6gqF9OVTIRqKaeS/7YmBhoT9NDUBIcWICAEPIFTMGndb0L5aBKPIeRmWXlidANGu8k+lyqnfUCJyP5XJ4zrQywsADq7+KcDWJKm6f3FVYDjV2YGgathyfonkWsNzmQTIOQ0FFK/+y66s7aS87tbGtCrKOCk/JxbxI7vvbm0sVJVye+7XjbtuIi1kvugdKYrawk54qDVpGEn1tSy6dDBLgL+YN+B9rZVzJtjHX6Q6KXcPOL6MSF36ueeSI4cDBR62mhY3hSEyO y83wJXCm UXbJCH9vpvPb9tPzfnIMlev6aZMAsXdSrUH6963Duvn83KCtdRffAdiC7UgIm9snIbCTvi0m2Het5aCH13+ovQoAMWiXfR5uvN4y6xr2IGLUjA4Iz8WHhvFVCq/ure37eikT+pNMQDHn3KSzHVd/c36orN8CQieYBdpG8cPHgGZPYlUiCG2p+W6IJRhFxIAOQHZJOFCzrtDxte44+DPDMAZm3uZyLwIFMg/mHzY54FdtHRWK283CZgkAO4La5kDY1VgWiXD/pCK3H9Js/EoufEjV7TcLm0idXf5nw0bk3040AFtMfHhNiEze8f1gdo7Uz+6o55bP1e7959SVdlVD96fHGFZVSn9zX3HpkVL8oAZgo1o1Bo60XRr0jso1jQRMAVZQs2VbKUKjPuOLfjqoOv18H9SASxVOSbbJVZ4W3tPdDhkpHZitGhhoiEeNd+Oy9l5KLS1Du99+SXQxMgClpXUeA1t0SP4CFJp8UxAsAKI3h8b8JdXoDo0WjWLURvGvWP7HIQUIj4PF8BGb07si4enCYFxnDzeT1DMv67oD0Zg4xdHcUcC5JDTlOa0udKVAJXiTG 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 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 > Signed-off-by: Wei Yang > CC: Jinyu Tang > CC: Peng Zhang > --- > mm/memblock.c | 74 +++++++++++++++------------------------------------ > 1 file changed, 22 insertions(+), 52 deletions(-) > > diff --git a/mm/memblock.c b/mm/memblock.c > index 98d25689cf10..b46109300927 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -585,10 +585,9 @@ 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; > + int idx, start_rgn = -1, end_rgn; > struct memblock_region *rgn; > > if (!size) > @@ -606,25 +605,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; > @@ -642,15 +622,17 @@ 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 >= type->max) { > + if (memblock_double_array(type, obase, size) < 0) > + 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); > @@ -658,33 +640,21 @@ 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) { > + if (memblock_double_array(type, obase, size) < 0) > + return -ENOMEM; > } > - } > > - if (!nr_new) > - return 0; > + if (start_rgn == -1) > + start_rgn = idx; > + end_rgn = idx + 1; > + memblock_insert_region(type, idx, base, end - base, > + nid, flags); > + } > > - /* > - * 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 { > + if (start_rgn != -1) > memblock_merge_regions(type, start_rgn, end_rgn); > - return 0; > - } > + return 0; > } > > /** > -- > 2.34.1 > -- Sincerely yours, Mike.