From patchwork Fri Jan 13 08:26:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 43072 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp152487wrt; Fri, 13 Jan 2023 00:32:04 -0800 (PST) X-Google-Smtp-Source: AMrXdXtY6ed55dV57G/LVes4kl/nVCoip6/fv3XRkbE0OhCwv1IrZEXyQliXhZKeqjDh3zvO+Hd0 X-Received: by 2002:a17:903:32d1:b0:191:3b7b:3c2c with SMTP id i17-20020a17090332d100b001913b7b3c2cmr13363422plr.22.1673598724607; Fri, 13 Jan 2023 00:32:04 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673598724; cv=none; d=google.com; s=arc-20160816; b=leBXI/rzXq8d6iCdPoJVcrNATDXNFSrlowAM6n5jCuw7SqIKZvjjs2vJt1TCYgMwjy hJddcw/pIuuei+hIMildCqZWbk8IzWf7T1ulyUgp/mcUS7HsBy64HL4aDtzdsbxnTqM6 FqXKkpGC/hgE0hrztq/tYLAaNygsUH+WQ6hBpI0rYPRC3GF1sZXq0SEyGO4o/9ngHGkV QNOEh1kmSOvAPSt9KW7oQ1iMw5+307gHqwzdQ602qvOiNK8Y/Vq+C3lyIdAzF9BUoSar vrZ9RL1TJbw7AKsM+hb3Iofz1YsRBsHgq8A7JHZkDuqTg8RkeWpcihHwV94YJSEgk2Qh EO8w== 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=1iTd5byfBOgh9LVNuYuoOV6hXCYzXq9gAf1csxesg8Y=; b=WCrDAsUjI5GBIWToUxc5J1HfSkgtPjghioI63i1vWh9by+Tyy8XvRNWENiHXQAsWkb /xXchQJig9KepkP4iO8dKtN/EidSYpOo2kJEW0ZJ4ZYT7zdJThxd/hCOlNkvyYxsBlTK Nh4lAJFAo1U0itL6vkQMXyx5ha6VNAaQemqK9mp9jcolo6clES8wv8KSzPJ+1WiHcOCs 7n/pnDmGA6cIHciL860O6WamBnqh1UfisigZh+uRmNGRLJ53ziAILh1hObGAwqhAgLV/ hudk5AAMucbmtr9W+pKG3fHiwiZVyNvT4lw5DNspVxi6+zDoQk3X0vGGCZZZBR6vNZOK vbzg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=f4WyK3Xl; 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 x14-20020a170902ec8e00b001925dbac333si9581278plg.312.2023.01.13.00.31.51; Fri, 13 Jan 2023 00:32:04 -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=f4WyK3Xl; 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 S240835AbjAMI15 (ORCPT + 99 others); Fri, 13 Jan 2023 03:27:57 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38142 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S240676AbjAMI1f (ORCPT ); Fri, 13 Jan 2023 03:27:35 -0500 Received: from mail-pg1-x52e.google.com (mail-pg1-x52e.google.com [IPv6:2607:f8b0:4864:20::52e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EE32A55652 for ; Fri, 13 Jan 2023 00:27:10 -0800 (PST) Received: by mail-pg1-x52e.google.com with SMTP id 7so14515584pga.1 for ; Fri, 13 Jan 2023 00:27:10 -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=1iTd5byfBOgh9LVNuYuoOV6hXCYzXq9gAf1csxesg8Y=; b=f4WyK3XlBgkV1829d+TSRcqYiXtgsgVc0lzyFga2JdKfICjv+2pvnWx/fysrvWeeqp 4g4zEITqfzVovBMOaYMAZfTvSO8H0c30bfGjbfVneHfX96pffYg/4NNwdDubQkeAXGF+ NXmTN8SrCcmw3gbQvFXSjxxTysiPyVQmreTuYBlhfVs9xmkwxs4MkOfz4DJBkJC0m96G 9NAYz8PdGTXGdRsRIKvcQmaKr69fppmU74LXLcB/u1qvpzBHYeMFSGM7lViEsSM8g4UK Z+Km4VvT4nxgGfATWUcbqR40opiVVYy4VerfXH1aB0dTKhgNsB/JAyzzeVrL9rENC0lA U9eA== 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=1iTd5byfBOgh9LVNuYuoOV6hXCYzXq9gAf1csxesg8Y=; b=qwAAW5MOdg+KA3x4fS/11OJdgn/GhJlB9f9Ut25ZcpXbPUcrsQc3kIl5WvJlYJvoSF cvzghw9vIJOtqoj7Q9ht3NfhCZBSGB8B/MWtVNSRteOS+AO4unlufBNbU50FsKq3xS27 vuvfiAyucAlDX2N/TrmyTTCfuVoC75ZS+VBPanjNO1xY/HhhjT8qypkF1ZjTqh1JReeq 852EPBXkgCUg2LoXFEqo3VYATs347qPudwhauQe5dkp0m92MUhjFY4FLqh4ZemjCrrxb f8vnQGQjY6YHW1gjjiOFTsexLHBRQcpIC9SA+gzpDtaAMZDZbqzvezMrXQt/6HCaALf6 HTmg== X-Gm-Message-State: AFqh2krThuUM2lP3d3sJ9zU1aDjFhsLNcg+EtLs0GXCD0OyV+9OISkel 7cCQvufD3WxlBeceE1AL2AgOIw== X-Received: by 2002:a62:e703:0:b0:577:7cfb:a896 with SMTP id s3-20020a62e703000000b005777cfba896mr9537441pfh.31.1673598430465; Fri, 13 Jan 2023 00:27:10 -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.08 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 13 Jan 2023 00:27:10 -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 1/3] memblock: Make a boundary tighter in memblock_add_range(). Date: Fri, 13 Jan 2023 16:26:57 +0800 Message-Id: <20230113082659.65276-2-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?1754895456041413743?= X-GMAIL-MSGID: =?utf-8?q?1754895456041413743?= When type->cnt * 2 + 1 is less than or equal to type->max, there is enough empty regions to insert. Signed-off-by: Peng Zhang --- mm/memblock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/mm/memblock.c b/mm/memblock.c index 511d4783dcf1..6eedcfc5dcc1 100644 --- a/mm/memblock.c +++ b/mm/memblock.c @@ -601,11 +601,11 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, /* * 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 type->max, we know + * 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) + if (type->cnt * 2 + 1 <= type->max) insert = true; repeat: 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; From patchwork Fri Jan 13 08:26:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 43071 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4e01:0:0:0:0:0 with SMTP id p1csp151809wrt; Fri, 13 Jan 2023 00:30:02 -0800 (PST) X-Google-Smtp-Source: AMrXdXtemfgBJ3L+69mKXZ+Ol1FPSvCcIpD5kcTTs8ZEgbTrCyqtBSawO2odFwVrxCodMuTcVxOy X-Received: by 2002:a05:6a00:4c8c:b0:581:61a7:c8f0 with SMTP id eb12-20020a056a004c8c00b0058161a7c8f0mr58452439pfb.4.1673598601867; Fri, 13 Jan 2023 00:30:01 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673598601; cv=none; d=google.com; s=arc-20160816; b=EBeqD2MsvzyKkeFGBhGIqVjkN5i1zs2x7Cm5ZVX1bnQynXWrIrST+RRLx3wYUwmyO7 hVTGaKRIeO+TJzJx9o4s7uGJcMSyXRkcErJQFozs1u0sNp3JsKENKc8gvacNuEwrRUg6 5ybuLUUcFHXaIcyaq9KSkYF61YDSsEPIPyXzGToKDMP0BhwZRArz1tXcbt8MSYpweM08 7vjZmvA6MgxZujSTFNgqu90OYAU63EPiR+l9zbVIhRpeUFzFlpNveXYTu+xKCFchEEmT SigrLNEezKCNuG9j8sYXniRfSdGahq//gtVeoc3tha8rKpAiBjg0SEg33Lz+uQe8SOr+ i+0A== 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=Q4Az0GQIpAo5qLK4eslBRX7WJSl1cxutE/mioG/uZxc=; b=bD5rIkKpOeboqdDflHRv0haD/l6zFmbgZDGrmTPF3IiliuKaSSppPugCdG5PGU8Vnj pkQ3KfyPY/9CEqm9JzpkaGB976f+pvpS1s6CLmhxn1su1+D+G7efH4vtXjufUYMZMjEI itJcuYAbUpKjvbfwH11hTQJ7dpcoAxXhn5r2f68w0dBJzCk+IKJD1b6aLgx4XLIOTkTh jzu59k41yxpcofVS4Drw6HwVyufaYh+n78A00KclM2DDHlhk2mbbxCbsDNE1GyvmIG7V uHHxiJouwueGQWGYUVXgkCY2LZZ9hmXMG1inFWc2G/5P3dsh4nEimm5P8m/WKf8CigXB EOMg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=MpnWYaJF; 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 u17-20020a056a00099100b00581e4ef2df9si20080206pfg.207.2023.01.13.00.29.49; Fri, 13 Jan 2023 00:30:01 -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=MpnWYaJF; 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 S234853AbjAMI2N (ORCPT + 99 others); Fri, 13 Jan 2023 03:28:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38882 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232007AbjAMI1l (ORCPT ); Fri, 13 Jan 2023 03:27:41 -0500 Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D10B342633 for ; Fri, 13 Jan 2023 00:27:16 -0800 (PST) Received: by mail-pj1-x102e.google.com with SMTP id z1-20020a17090a66c100b00226f05b9595so8584942pjl.0 for ; Fri, 13 Jan 2023 00:27:16 -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=Q4Az0GQIpAo5qLK4eslBRX7WJSl1cxutE/mioG/uZxc=; b=MpnWYaJF2T4qlC9e913gYzl9AiD8aMnsvQKAqLMg1yjsF0soBswn5aF6VSp72MhgAY 2g1ioFdZFpeEptHS5Sm2x3Qgtz45T3zAYavuNbvTxLAbmG/8Up0DSPdD6FjIMBbuf++z dD5W8xWo6PA1QZ67Tit3KfPwWe/sqvW96xIpG/jn+owrIeO3WTd3MetvHFgZ7sDV1+XV owF5gECfqxzfyOuGrjseOKHUtJEzOhq02ccaTKLB5WdzfWOYT3DnaniY/u5eJALne30V 10JMG9ugSSxV3R/E/LOj1nLFQefTA2CuZIUEfsE/GV68ojR8OnoK2zg8HWRRwTnyD2+X KyaQ== 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=Q4Az0GQIpAo5qLK4eslBRX7WJSl1cxutE/mioG/uZxc=; b=d9hQ4vS4MuvQht4ZNC/IAefBEcNzhBp6A/Z+Y7y67Sip6pDa7BIfmcZ7u19SHP9Yaj oBUJN/lHG0eV7+uif0XdXqEBsLK9UCQczOSwdGayt6dTzJQgMzX1Naptp80fFpeu4nw4 4o5Th3VYH5/2K21GAkVowrDoK0bHBFnTJhRauRBAM+Hy7QW8jdtDNMUDtSCd8MhPDMC1 PHg7m3VXN6a26mVOGiA45CgWhCpRypAgGzeJAqHtaaGqXGoFLMbNpdglrURubYSqRrlA xFqhSs4E602SFw0RDvY7xcRU84jUqPNfb/xFNcCOt/mKX7hVP+0Dmi7h6xO9B4YxT6Xq Z6zg== X-Gm-Message-State: AFqh2krucnsPYF8AdF0Q7VWKXTwp+U/SYYZggjfo/x9zPVQppQyVu+ja 0/w3s03a7y0nw35YgzoJF/WNUA== X-Received: by 2002:a05:6a20:9f48:b0:ac:29b6:a235 with SMTP id ml8-20020a056a209f4800b000ac29b6a235mr91778538pzb.54.1673598436328; Fri, 13 Jan 2023 00:27:16 -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.13 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Fri, 13 Jan 2023 00:27:16 -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 3/3] memblock: Avoid useless checks in memblock_merge_regions(). Date: Fri, 13 Jan 2023 16:26:59 +0800 Message-Id: <20230113082659.65276-4-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?1754895327655124432?= X-GMAIL-MSGID: =?utf-8?q?1754895327655124432?= memblock_merge_regions() is called after regions have been modified to merge the neighboring compatible regions. That will check all regions but most checks is useless. Most of the time we only insert one or a few new regions, or modify one or a few regions. At this time, we don't need to check all regions. We only need to check the changed regions, because other not related regions cannot be merged. So this patch add two parameters to memblock_merge_regions() to indicate the lower and upper boundary to scan. Signed-off-by: Peng Zhang --- mm/memblock.c | 36 ++++++++++++++++++++++++------------ 1 file changed, 24 insertions(+), 12 deletions(-) diff --git a/mm/memblock.c b/mm/memblock.c index cb92770ac22e..e19eb08efc73 100644 --- a/mm/memblock.c +++ b/mm/memblock.c @@ -523,15 +523,18 @@ static int __init_memblock memblock_double_array(struct memblock_type *type, /** * memblock_merge_regions - merge neighboring compatible regions * @type: memblock type to scan - * - * Scan @type and merge neighboring compatible regions. + * @start_rgn: start scanning from (@start_rgn - 1) + * @end_rgn: end scanning at (@end_rgn - 1) + * Scan @type and merge neighboring compatible regions in [@start_rgn - 1, @end_rgn) */ -static void __init_memblock memblock_merge_regions(struct memblock_type *type) +static void __init_memblock memblock_merge_regions(struct memblock_type *type, + int start_rgn, + int end_rgn) { - int i = 0; + int i = max(start_rgn - 1, 0); - /* cnt never goes below 1 */ - while (i < type->cnt - 1) { + end_rgn = min(end_rgn, (int)type->cnt - 1); + while (i < end_rgn) { struct memblock_region *this = &type->regions[i]; struct memblock_region *next = &type->regions[i + 1]; @@ -548,6 +551,7 @@ static void __init_memblock memblock_merge_regions(struct memblock_type *type) /* move forward from next + 1, index of which is i + 2 */ memmove(next, next + 1, (type->cnt - (i + 2)) * sizeof(*next)); type->cnt--; + end_rgn--; } } @@ -604,7 +608,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, start_idx, nr_new; + int idx, start_idx, nr_new, start_rgn = -1, end_rgn; struct memblock_region *rgn; if (!size) @@ -659,10 +663,14 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, #endif WARN_ON(flags != rgn->flags); nr_new++; - if (insert) + if (insert) { + 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); @@ -671,9 +679,13 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, /* insert the remaining portion */ if (base < end) { nr_new++; - if (insert) + if (insert) { + if (start_rgn == -1) + start_rgn = idx; + end_rgn = idx + 1; memblock_insert_region(type, idx, base, end - base, nid, flags); + } } if (!nr_new) @@ -690,7 +702,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, insert = true; goto repeat; } else { - memblock_merge_regions(type); + memblock_merge_regions(type, start_rgn, end_rgn); return 0; } } @@ -927,7 +939,7 @@ static int __init_memblock memblock_setclr_flag(phys_addr_t base, r->flags &= ~flag; } - memblock_merge_regions(type); + memblock_merge_regions(type, start_rgn, end_rgn); return 0; } @@ -1300,7 +1312,7 @@ int __init_memblock memblock_set_node(phys_addr_t base, phys_addr_t size, for (i = start_rgn; i < end_rgn; i++) memblock_set_region_node(&type->regions[i], nid); - memblock_merge_regions(type); + memblock_merge_regions(type, start_rgn, end_rgn); #endif return 0; }