From patchwork Sun Apr 14 00:45:26 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Wei Yang X-Patchwork-Id: 13628859 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 7665FC4345F for ; Sun, 14 Apr 2024 00:46:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AA91A6B007B; Sat, 13 Apr 2024 20:46:03 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A32696B0082; Sat, 13 Apr 2024 20:46:03 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8FA2A6B0083; Sat, 13 Apr 2024 20:46:03 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 6938F6B007B for ; Sat, 13 Apr 2024 20:46:03 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id C12BD801CB for ; Sun, 14 Apr 2024 00:46:02 +0000 (UTC) X-FDA: 82006295364.20.65551E8 Received: from mail-ej1-f52.google.com (mail-ej1-f52.google.com [209.85.218.52]) by imf22.hostedemail.com (Postfix) with ESMTP id 2DBE0C0006 for ; Sun, 14 Apr 2024 00:46:00 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b="BPcxq4/6"; spf=pass (imf22.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1713055561; a=rsa-sha256; cv=none; b=5oWBiwzadK6/gO+pLSc8ZzuBfUheXGJtCowYYxqw8yB5zx+9UttY9zkJVGVBDzHTHwVv4T hrgPhYOP1SrCQAy/tojE54etLJPLrMG6m0w3bUGPRcIWle8iCkpGYvcZHuSTQ8gSWWdf8W IovdIrfPQhctoSPX6WpZe9GlOStpC6A= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b="BPcxq4/6"; spf=pass (imf22.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1713055561; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:references:dkim-signature; bh=z/lzrBdBq7d/KGMB51apJ9EvGc0eMJ+chjRrOdSDWt4=; b=CUHZrxUVlVTlAJwU4jhsNPZuAq/tMMxHj2mfM3v/NuJikZhZQ9DYp7jSC64t2L2a9nqtUB Q6x5s6XKssWGB5SEKK3d7IV8EvZ9MLmxqZbAzk0QwYHrwiXPFNxt3ME18VFMNF+QiWheZF UIMty69hcOu0+7cJw+ia0Csu9ikHGug= Received: by mail-ej1-f52.google.com with SMTP id a640c23a62f3a-a51b008b3aeso245275566b.3 for ; Sat, 13 Apr 2024 17:46:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1713055559; x=1713660359; darn=kvack.org; h=message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=z/lzrBdBq7d/KGMB51apJ9EvGc0eMJ+chjRrOdSDWt4=; b=BPcxq4/6anMoFlQMvKm+TaQzNIPnzOwBiTsaIqfvTddxaKzl9MU8xwZBef96LIw4rk 25goNMj6NTbFVkhqyFf3rREpErLhoTTQfxCye/1al5NMRpq8OboXTKi6kfgbdHQG4Q4y DNkOrXy6CDJSH8MaZOxwmPNHmXB3+UxElV0dTlUQwjXSk6J+7ELzuB1g2xYGUCJj1/3o 42NVtwTp2YItudat8zNMsgGuGGQXPHYN6Qkp8g1lQttVOLt3CZbdRGPkvYZbXPLK8pmf wOo7fJuJc1e9P0E7x7CQ9XqJ+TH9Dl+WVSJ4PWzyrkUatFecuhTTEhsiZdO8LGTDXX4m NydQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1713055559; x=1713660359; h=message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=z/lzrBdBq7d/KGMB51apJ9EvGc0eMJ+chjRrOdSDWt4=; b=YTg5I6lNkXmB9inUozzWh2pvOTjxdB8hOGESMv3c1oMsNIvTnA47PkaQOjxGtT7fqK dZi1cp5wLhWVJ/B8Jba1eXCsd0D18sspV9D7uPpmZoiinosK26SoFNSNWAy0hNc50rhp KVlKiCjfCuuCj5C+U6I9/xThBvbF31R+jxwkb/WV/IT4kyzEyW7ZWHenpxOU9yBVCuJb BOUoAOvGuuX9wbIBV42vd5tc8WrSy58w9ffAWZkHs+HIYoDALS0x1QO9J+0VedCu27Qv hWWbbBupZcsGTdLeLfD6JNWev9xKJJ/HyTy1bmxp4lNB1MbGq10x0g15KpGF1rnFa08C oEIw== X-Gm-Message-State: AOJu0Ywxaic/+ZgrUR2hufLC8p70NDvlctkklD2TKx/UpLWdoXWE7tBF yiwK6RWBT6UknC7lRhr2+Iw9H+C6aO4GcxqtzSYccTcQC1JySiSE X-Google-Smtp-Source: AGHT+IF+05A4jUJAv+Nc2l2jEKu9CswGqCbxMaxeeF88lVc/hyKc2NgpE1T1kGYYAhg9MRfs/D3IlQ== X-Received: by 2002:a17:906:dc8f:b0:a51:af7d:4652 with SMTP id cs15-20020a170906dc8f00b00a51af7d4652mr6073214ejc.32.1713055559238; Sat, 13 Apr 2024 17:45:59 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id k11-20020a1709067acb00b00a524b33fd9asm1354337ejo.68.2024.04.13.17.45.58 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 13 Apr 2024 17:45:58 -0700 (PDT) From: Wei Yang To: rppt@kernel.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, Wei Yang , Jinyu Tang , Peng Zhang Subject: [PATCH 1/6] mm/memblock: reduce the two round insertion of memblock_add_range() Date: Sun, 14 Apr 2024 00:45:26 +0000 Message-Id: <20240414004531.6601-1-richard.weiyang@gmail.com> X-Mailer: git-send-email 2.11.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 2DBE0C0006 X-Stat-Signature: 561zfso9ttieoqihcxsanwcntoekpetd X-Rspam-User: X-HE-Tag: 1713055560-959414 X-HE-Meta: U2FsdGVkX1/7W0wLuTjK8CMqT47YpuYQKsU7G8aK52w3U+FJTDdCliC3P+NET2HJ0MY58uvxiUw7vXtLdFuGSPEInfWWnDb/lft3Y992RMUqogZjL6G0dSyushhhLHSbQjf0cMiLIMeVzsDm9QaRQlSVgdPogQcsFzKIWcL2o3I5Av97E8eo8D3zHOOqQuS+xzcK8Zz0KS+Ex1x7axfUWyTv0Csh6AqpWzYsbreYUVPvqvodl1lUrJMdwFVRpx46R8/M/JT9sUHUykGkNycSG6vqtu8EPlANbANWK6BT1SRZeU8UAnaXokp/f3eYsp/UX+h1l8S4Ww4MsSAHIDDOnL7yrvBuRbZ/hypYer2mwXrVM9eOdfXqp0L6uWS+YUa6UqSnKYOcgQZbeR25uCPXTQVwFW76RNigrgg7X3NOWSMRhHmm1ynTV3U7GpKyEtWpvdbuTjaOwdbIJr5L96Rlv+zFpKhu8L8JHl7pjVsvfPZOB6lcvVTwOCc5/Pbm14oH6ahUU4MxkjcssEezQdklJ3IZIU+iEwoQmqtxULMhE0nSt9wp/JdHhBKsdyOY9JVbmMi4PaO5Gy4KdurDi3G+AcPmNTW3wWZ6DFgNaQRrODdXUQcq249yufHByEArPH7qwnFuoawKxlP+pVsN4r3M9++nW7FYtx0qhh8S8cNt/1BuJEr9AMPmOjirNovkY4hLXarPaTW5Exm0wf1y3YxZ6ZQvV1hT12Z7LiZK+V7njEOTsAM8keP05uDAo9nivS1qsIIChnytCy7/SRbxnwcb1uW1/pL3Sabikwy8lf2nDVcR/ccx2j3IQbs+fduHfxIAlhwHyVsjr7jJmAtUkRL/IR+eP64tEN1kX+rnBAf7+aSvSebQfihSHToi04Fjl5JzNZ9T0v2C2TIQ4G1sj96gtM+gO6e3H/jaHQP9yw7tcbRUx8cdDQ5GSfFdD+v8ZnAnFIPwnjR7fay49JbzRuI AHK57tCA mGTysesE0eO0iiEyt3gqChJmLUMKXDVVoGalneUeQOzab32URRynmaUn5W6N65ej7/2jJhoSFYoFg/9rgDNk4o51evI4TP8xEDPIZF01AFDbqk7DtzhljR7jRyZxKMzK0Y8Q57KAuTX27vDEbXYUpxOYi7fFHUyab4tQuci7i8HPntRmWFPFF6Woo73rfNKbJkPc+LGcxyJ14Z/m68ZcfduLUVs1YDryL2NT0U7CnWBoUBlhXG6O4fUmUvqFWxszLVLNf1VbyAvUD9bWU5Yeeh0pGnSkK6Cte2YjWfrlgfdkdUtjzTU2hC6u5c3D+zKGXBf129xcRWosKiVIHsgXelmKCVeYbivjPjqA5FwWuGHLKE660WArsLgILa05JHBczOTqGWC5Vs9J0QtTOU9uAdbN60OxMsaiea/FbG+TTqqUD5pUITV0dghxHXDZZVV3iO6mTq5Au5OCQS0PwlTksHc+J18uWCsza0BlWjqXxlfAbebE/2EzIWYAYr3l7JzXQKElMaXIn5mHTxT7z9xrxnELiU+yqNtLsN+QVDY58v1bSrrbuaervqhczGQPRpLiG/xa4MwiR+mv8OG1iowCi2p67fmXNQmY7o/yWwux50N/1fC7f9nTttbMBnclWeugYxNZ7l5yjn1oUHz97l7qnQ8kHf5BojJkTh8daIEvYWgloqPluBeK4CSO6Fg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000070, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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. 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; } /**