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: 43070 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp151342wrt; Fri, 13 Jan 2023 00:28:18 -0800 (PST) X-Google-Smtp-Source: AMrXdXsEJ61CpC27Cdrm/vVn+odZRD7sRPgOYuFXzED1TPiJ5I1uKVBuHbQLLcIXqjfeN3efiyC3 X-Received: by 2002:a17:90a:460a:b0:223:ed96:e3ca with SMTP id w10-20020a17090a460a00b00223ed96e3camr82279925pjg.28.1673598498147; Fri, 13 Jan 2023 00:28:18 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673598498; cv=none; d=google.com; s=arc-20160816; b=d9RtohwclxPGNeyAuSczvua7/8mWxfTlUnER/EbnaRmoH66lgFg4DuxBLuCrY4ocSK kKRHqGNvfz5/u+LfOIEAavnvDXuOoJKaQA+oIOd3r8957zD2CReyBWiefuISwcC0zvBV gPN3VxB63nyHbDgLoj5ubwUHkXTyfS+n/Sh7gg7+sA0BpQX38JUqEdm96CWk+4v2437+ EduoByHgsaU5mEJwz7GW08WiC6JT60Vh4Ji/p6S4v5bbp8DX/7DBCGjvJEgQrUXRxN2N rzzz5EZGWZk6C9ZTDaXZbJcAJfvIU0piBczPqymuELBR6XmPbzwtDUIecmaBmvNsYyjD kI5g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=xOTLi2okEkFS/8sRuephFsj+ueiTQYPyzZu8sNnyp7c=; b=Z8rKHTV2QFqHCVilD4oZZYNbe5IOPj0Y9ALqIXDPf3TXaQbfqn3kfCl180vF9sH1uz BAql3jwO9n6LsK/P0sbJia0Qee9axhPP6DR/eXizmV5mlnU5z3re7dHBa3GcqQEyYDnV 5vm+R0OvZxl7GZb5NwMP7g6d06Bjwrce8iv5QNEcBffeoCJ4xg76Cp608uqJOHB9OQgm /nkn/7nGJyCr0g2FxZyuAU20XiGbXPa1lFdwTQ+FqfxO9KeXBwIM+R0dDAMX26HCeTUE ZMjc3rc8dIZZqjhlTIwsBcCES+X6pSU3ZkiRKoHz+e+Bw3u37ezpWBtf4P5t2+nzcG6B Zhlw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=DB756DEl; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id y64-20020a638a43000000b004b6ab2e4d01si8700722pgd.358.2023.01.13.00.28.05; Fri, 13 Jan 2023 00:28:18 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=DB756DEl; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=bytedance.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229458AbjAMI1g (ORCPT + 99 others); Fri, 13 Jan 2023 03:27:36 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38376 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240560AbjAMI1P (ORCPT ); Fri, 13 Jan 2023 03:27:15 -0500 Received: from mail-pf1-x431.google.com (mail-pf1-x431.google.com [IPv6:2607:f8b0:4864:20::431]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EB0D632254 for ; Fri, 13 Jan 2023 00:27:13 -0800 (PST) Received: by mail-pf1-x431.google.com with SMTP id x4so11506005pfj.1 for ; Fri, 13 Jan 2023 00:27:13 -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=O3SfVIqkhg4bhiUN+tKn5swoB1deTxoKucW1g7aLboW3/4Uuc6UMkdPuVMe5wVycly dYBMXqGrGiot0yZMNZZyFyEUTHB7wcdjGZrjIAGa+9sBxeTJzXje6F9/O/6hcgBn+Q5H F13VNliMalfg9zWzUd+xMMSIoQkJtKk9KZo7bS/ehoCWe701OXUBeOBt6pf/yQi+8zWd vmNL6VlY55zQbNmXdxw75HIaX54fvmtShs4jlDL5dq91ruB4v5z4dlO88WQ4SDD0rcoj zpbV7Hwfd2XtM0pQHBbq3CIwxAbSVQbXSN+8TAdSs149Kzcq/26EDfgKiTa0Q5AELy9o CvDw== X-Gm-Message-State: AFqh2kp0vGPs6mVoaaeaGLmu7rJkK/ocfO3QBW4301fAPsAKnTC9GZei sZ4naRbIs+kF9GiWmkEyUe8rlA== 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-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1754895218737573502?= X-GMAIL-MSGID: =?utf-8?q?1754895218737573502?= 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;