From patchwork Fri Jan 13 08:26:58 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13100245 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 E79E9C678DC for ; Fri, 13 Jan 2023 08:27:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 858698E0005; Fri, 13 Jan 2023 03:27:16 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 807878E0001; Fri, 13 Jan 2023 03:27:16 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 6A8A88E0005; Fri, 13 Jan 2023 03:27:16 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 588B58E0001 for ; Fri, 13 Jan 2023 03:27:16 -0500 (EST) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 3647C80140 for ; Fri, 13 Jan 2023 08:27:16 +0000 (UTC) X-FDA: 80349096072.04.DA38214 Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.171]) by imf06.hostedemail.com (Postfix) with ESMTP id 798D2180013 for ; Fri, 13 Jan 2023 08:27:14 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=DB756DEl; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1673598434; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=xOTLi2okEkFS/8sRuephFsj+ueiTQYPyzZu8sNnyp7c=; b=ckw9Ir6YuLFMHHYmSCBoRMLHwCMuYB1E0CuqxiDmZdxc85Fa1m6ndE64UFW7xX/O5Gu7mI 9a7l6cmqI5ubAWKLAExv33ovSwz9113Yew911n6tAIFQXIZjQN8KICONGRmzcu7Xix7Lmq nA4DfaBzyRXisjdeLj+V1XKoHNRVeLg= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=DB756DEl; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1673598434; a=rsa-sha256; cv=none; b=7S6DSDE6izzGjRtITMbdxwxK3FB4JAH8nacbL6gY7IkQgwXpAr3lCfwgJJeRsQKqccd3GH ZkPQTKFahw+yTOl8KSeT04tlw1hVoq1GXCCeIXfpLkNWau6p28Sf3TVQscsSh7A/efLhgR TAyrvsH/VpRLt7qxrX3hghJibnaFOwk= Received: by mail-pf1-f171.google.com with SMTP id 20so10234304pfu.13 for ; Fri, 13 Jan 2023 00:27:14 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=xOTLi2okEkFS/8sRuephFsj+ueiTQYPyzZu8sNnyp7c=; b=DB756DEl2kGDqQ5rfDMa3lVd8k2XMke/NAVPJCDgsCtDEJg13Xz/fxlQsi6ARGID5t AQKoMIXe1XHUCwkTq9BXngkwHZsjAvHYQw0/pBvoLWIAEFrdypdAQctxhOs3ZzbtSDnn 7DZfqdI4g8uFLqxGcSwnoMhj3WqPhdv9CrCy+9WNKhZSJZVoxzmhL4NWqFvbkenHT0Mi 9pkheDnafz8YWI8jh6trHGmClw/7B1W1AvE6X2nkS4DKN0wRSCJqrxvfLdNofZxAu2HN 3zQ3tSWjWchr7jZNG4+z5VYau6pQ5Dl5MVnyLHPrM1lnWYHZ0YoNQ9moxdvHbP9w8KmJ ph1Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=xOTLi2okEkFS/8sRuephFsj+ueiTQYPyzZu8sNnyp7c=; b=ny9lPuV4Z4m9UjqHAL18puBWrCLqbRiJ5p6IPD/Q6gax+6bDcmmWyIDXgyoX0Kcrty Ozrt8CPfvhDPkduwcwL1GtK3mCdTAnveYxIMZVCD6Z2ai10EP8TNqixwhScNHF1D7M0h 8/qiVYq6SeJT2maSwAkr4A7dzFUCTFtF0BZeYGQZbRvJHaDB56g9ECYyHLYBR3SHMzPa TKoc13Z0xwB6Wrb8KdFMmZ/NtZiRfVWuioR+1+De/vllLwiLBK2AQUTIZViEvsl2lG1R z42VyRZ6iEUS6AuEXv5Iisb5+eW5RpuE/BtyjxALjSKFLN6FAnsmvcFIg9wYSniKnljd jzcQ== X-Gm-Message-State: AFqh2krJfVSiXR2coppMpgLbNp6Xo5Y8BOspGlM6NKMq3RU9FAc2F0EI AKPDM+h7AoO/57OrzNS8ER2xFg== X-Google-Smtp-Source: AMrXdXulkzNesHhKgvQj9Q1syqtv8lKl4izjylagJ5dv+ZcAuCj2UKPdGjaoAGBSze8FhPfemMlcsQ== X-Received: by 2002:a05:6a00:706:b0:580:d409:396c with SMTP id 6-20020a056a00070600b00580d409396cmr72502746pfl.6.1673598433479; Fri, 13 Jan 2023 00:27:13 -0800 (PST) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.251]) by smtp.gmail.com with ESMTPSA id l123-20020a622581000000b005818d429d98sm13092738pfl.136.2023.01.13.00.27.10 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 13 Jan 2023 00:27:13 -0800 (PST) From: Peng Zhang To: rppt@kernel.org, akpm@linux-foundation.org Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, Peng Zhang Subject: [PATCH 2/3] memblock: Make finding index faster when modify regions. Date: Fri, 13 Jan 2023 16:26:58 +0800 Message-Id: <20230113082659.65276-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230113082659.65276-1-zhangpeng.00@bytedance.com> References: <20230113082659.65276-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 798D2180013 X-Rspam-User: X-Stat-Signature: trkqdmz3fxugqmb4c8qa9hhob8dd4oy4 X-HE-Tag: 1673598434-220517 X-HE-Meta: U2FsdGVkX1+u650oaTFHQMfouXORs4CGV9eMNAgymiTj3SQQe8gofIcRMjw1+Rfh3EQWVY8T5oJZ/HXBUmWblPdYrk7YRIwj0KDLn3O5jJVAB9p3sl1gYw62yRZjS2sCbnEzv37jiRHe/rS17Q4bI5uSL1a6OmdQoxME+goIXHYwNtVNV3KifirUGyUNMpK7hG89gFEZBB8brj4e3ys2PW4UtXz+rbYXj1Ik3FOllZrZI2h/greFjjIMbmdUhwxsj+auL7Ml6/3lfacpHvpO3hpX+j8we5lSIsJmfiIXpPTXrFd4f7VGHM4uv1MbrzuC40cZqW9ap7yDPKp3hJfsX6GFLfi3UJSqlpBG0pHVeq1CRt7mCjCVhoodS81zL0GY5iG861uqvkEa3lMSPy7UEJAy59EEbF7/s7kpUBqmquQcdBXgICHFI5bkKXZUntW69hT8H6n9uATyBV/xUmaOBLI2cpPpV7nBdH7YykUmaoelNAK7AIhSy3LMFQhK1MKfcGdPW93gWnSC4jScnO3SzV97vsnLi704WtxvwaxKQzgo3CxZ/Ah2HuvZalo0/xQy9Tciactse4/niGLfu3EgCgdj3+bspBQDbXCxoehYNhQ1uUZwSj3S+K7hnWO5p7eJhJchQ3w1Nsox7a6bjB8hh1KunbUTeV0YyY7X2LXq0QNZaCEXLqeBAldC9CujkToCwusxXEozRpWrdOEnFkePsL5TxxSMM7yZp2a4kouKdsiLh9+S4g4tIlfkW042UtyrSU5EQrgy4OApTaj+YdLYP96euhkq0J0n32lH69RP7moxcBgfZwcU/x6Q6OruvKLltOTRxTHGGYfQ5IhsDBoixQyJdK77qLoW/crXGNLBQKNFZ9p/TI6KUVhS7Z/mdUUb7IQdM3fMXNlXeVg8gU8m8Ws6UjBPUakEabI/BvOPNWXMSz1eav0wAnJUYga1WLfZmcIgQSHDrXS3E2pIsXd T825GRVT +6qGNX1mjkBh48YK+p/1wA7XnOx57A00Gq98uncQeTzsR8+1+oumcmnKyOdbcKQbNEy69GmmwCL8mZGovs4DCTBVzIPAUU91Pu0Sj2xkdcZRhyNFcftycm2ycw3hZuGksJpJkjY/lionmQd8WVfPwmpm705wc3FdTZ+DGpTG54Bg7B2kGd1sLAnOghXt3ukFlS9++qxLCV8tTSBg= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000328, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: We can use binary search to find the index to modify regions in memblock_add_range() and memblock_isolate_range(). Because the arrangement of regions is ordered. It may be faster when there are many regions. So implemented a binary search and a new macro to walk regions. Signed-off-by: Peng Zhang --- mm/memblock.c | 33 +++++++++++++++++++++++++++++---- 1 file changed, 29 insertions(+), 4 deletions(-) diff --git a/mm/memblock.c b/mm/memblock.c index 6eedcfc5dcc1..cb92770ac22e 100644 --- a/mm/memblock.c +++ b/mm/memblock.c @@ -149,6 +149,11 @@ static __refdata struct memblock_type *memblock_memory = &memblock.memory; i < memblock_type->cnt; \ i++, rgn = &memblock_type->regions[i]) +#define for_each_memblock_type_start(i, start, memblock_type, rgn) \ + for (i = start, rgn = &memblock_type->regions[i]; \ + i < memblock_type->cnt; \ + i++, rgn = &memblock_type->regions[i]) + #define memblock_dbg(fmt, ...) \ do { \ if (memblock_debug) \ @@ -181,6 +186,24 @@ static unsigned long __init_memblock memblock_addrs_overlap(phys_addr_t base1, p return ((base1 < (base2 + size2)) && (base2 < (base1 + size1))); } +/* + * Binary search for the first region not to the left of @base. + */ +static unsigned long __init_memblock memblock_lower_bound_region(struct memblock_type *type, + phys_addr_t base) +{ + unsigned long idx, low_idx = 0, high_idx = type->cnt; + + while (low_idx < high_idx) { + idx = (low_idx + high_idx) >> 1; + if (type->regions[idx].base + type->regions[idx].size <= base) + low_idx = idx + 1; + else + high_idx = idx; + } + return low_idx; +} + bool __init_memblock memblock_overlaps_region(struct memblock_type *type, phys_addr_t base, phys_addr_t size) { @@ -581,7 +604,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, bool insert = false; phys_addr_t obase = base; phys_addr_t end = base + memblock_cap_size(base, &size); - int idx, nr_new; + int idx, start_idx, nr_new; struct memblock_region *rgn; if (!size) @@ -607,6 +630,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, */ if (type->cnt * 2 + 1 <= type->max) insert = true; + start_idx = memblock_lower_bound_region(type, base); repeat: /* @@ -617,7 +641,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, base = obase; nr_new = 0; - for_each_memblock_type(idx, type, rgn) { + for_each_memblock_type_start(idx, start_idx, type, rgn) { phys_addr_t rbase = rgn->base; phys_addr_t rend = rbase + rgn->size; @@ -737,7 +761,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); - int idx; + int idx, start_idx; struct memblock_region *rgn; *start_rgn = *end_rgn = 0; @@ -750,7 +774,8 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type, if (memblock_double_array(type, base, size) < 0) return -ENOMEM; - for_each_memblock_type(idx, type, rgn) { + start_idx = memblock_lower_bound_region(type, base); + for_each_memblock_type_start(idx, start_idx, type, rgn) { phys_addr_t rbase = rgn->base; phys_addr_t rend = rbase + rgn->size;