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: 13100244 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 3C9DAC61DB3 for ; Fri, 13 Jan 2023 08:27:14 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C01E78E0003; Fri, 13 Jan 2023 03:27:13 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B3C218E0001; Fri, 13 Jan 2023 03:27:13 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 98E8A8E0003; Fri, 13 Jan 2023 03:27:13 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 7EF648E0001 for ; Fri, 13 Jan 2023 03:27:13 -0500 (EST) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 560E3AB22A for ; Fri, 13 Jan 2023 08:27:13 +0000 (UTC) X-FDA: 80349095946.24.83E2F91 Received: from mail-pf1-f178.google.com (mail-pf1-f178.google.com [209.85.210.178]) by imf08.hostedemail.com (Postfix) with ESMTP id ADD2916000A for ; Fri, 13 Jan 2023 08:27:11 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=f4WyK3Xl; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 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=1673598431; 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=1iTd5byfBOgh9LVNuYuoOV6hXCYzXq9gAf1csxesg8Y=; b=3OhhUbrcyzSS/GBb8tbj3iJ8KoTx7RQiQs2hDprQSxSV6h2VX20qjW2NpilRN6tKdbrDh0 QpecNSTVIpudjbR5fPtcN+4HN4OB48l0yQLgz2nIXJQPfMhqYzyfM3tHXbgkanPQ+KxgQB NWKCO23BY0t1FY64Idq9i9mjzwoDkvI= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=f4WyK3Xl; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 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=1673598431; a=rsa-sha256; cv=none; b=t9ZoahCilKh29V9S38Kzr8Tdsrqk0VdxIxYi/hVBJxToErenlEJ2wCr+99fJiQSz3egWnB uZ5uM/OhvZ5EX4QDq2vnuGX6ZQ/v88JNpr/qQv85JBHamlbH1LGv5/jGxB87kOq97poGD8 b485+El8gj3FclQaAIRFDQiK3cSMFi0= Received: by mail-pf1-f178.google.com with SMTP id 200so9484303pfx.7 for ; Fri, 13 Jan 2023 00:27:11 -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=XYnJI4VkWM5zXx7md/Eas7FobAXbIECXXovpME/CVASrLvTsjNtUtCVGQgk2dh6IYO twvK4Tabx9b0c9syujBViLrOTB/Z0Fj8R9RiHEcJswMZ0jwEK48ej7oN8MlI6rDOZp8l jdOtXfYIjtH+ZUJNlsgGcVfuVifYX5UuJZn3tSiY2QbZq3R8jiNgGHhDCSeS1+R/hNiC gN5Ak1JvzR0Irm2hZRQpuLsb/x1bQfd4l6GDBWuFA5jRqrmZBGWU0zfDIJhJiREDaaXz pEtYw3lRi9zERnc2xYdauZZeNhLGOEl76m4V/tHI/GY98JBxUqcKdQNflhNUxC0GFmSI ib0A== X-Gm-Message-State: AFqh2koxB54dEwIFE4fcx2YxTFT0ZI/vXPIDCge6ycPixYk4V53SW86F juIl1E0ALzXb7xWlrWA7BAoSzQ== X-Google-Smtp-Source: AMrXdXsx5JHY+ED58MLqqtW4K6Yducj8FoqsJMzI/rev6xhsXOh0KNm1J6lTIgHBLlpTVaL9EMJ4ug== 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-Rspam-User: X-Rspamd-Server: rspam03 X-Stat-Signature: 7fkxdtty1fbsxwe7uw31wikwyb89nkno X-Rspamd-Queue-Id: ADD2916000A X-HE-Tag: 1673598431-569085 X-HE-Meta: U2FsdGVkX18jD0S38WdH5rS9BbQr8lRSTJ0lB14pnHXmlLWhV2fK4vJ4fT6jsodfgzAhFWG7gwGXlQsuR+TBdbSca1P9m8ZhHjZ9HGT/xH9kpf2vv/haowW0+Oid/uXLLDR+bADW4djVoIZX8Fnabq+J1+vouroau4mfWUpfmWq5l2YxFSUXGkJLmu/Qyqp7mAGf2kGr+DyAgDKWckaIM2M+ZUNOYeGhcUSaeR9imPS5xF9FlL5TU05QtbsHLpcp64h3d925wNJJJNCCW6gp1cMi8nXaqsHPwtzSh8rVvoL3kn8bYPHNYhITCQuHbc85sPG/+BhsHMSlSulZRzzo6AOgMvjeta0qNCnljpvNoEPFc95lYZqp571jW/agB14TVnLJCYUnQ45ZkjEpRd5cVRBsMn4uO/XHBIRQs5lb8DFO+immtbk5WGVIy4nb2FYa1RYwCDM8VqwbeQv9c4wJV4jedDMtcKDTh1eZ8QdQ+nN5OrmD/SvhjLT7+Yl2ieGiTXHXCAwcLeJQIsJnB+VfK13SCfE36lhWwLEuWx+GGrWpK+IZ0eD2gYzTQY+Cjdlh0ZNBAmF6N3AQhm8shKVDvi+vTMOJnx7Zl32O984DUsgaLIDip4VFEygnQzdiAt61ui6Hjfj0exrj4f2fCt2ti0BBZfgFFx95j9o+YisEBQTJlakVzXvsioilN4RYMf7RsauJBmmlGHhN6T/Avq9OmMHX8G1PKK8+L3xaFXkaVLD8pPj02J9InPeW/e5mtHsV6TDD9+FOnHkgs6XP8sQBz1ExERValjwMKi5iZWAKZibQ4meJiRA9moE9QejtEczbT9jBunqkZN9wfkEffd7HR+nDtepgIAPAtBY1K1u7TNuhb13GRSHSZrFrgeTPmZZEPTzojKlvVgtJkWBeL9R2CERLAbnjWpZ3XVDs7kaKFF0wWjUnsxGqjk19lqlvP8aJabi5txMDvaPeyahMFF7 cjpKICLr qM3FajNhKW6/tsJ2FK0is7ZOKejC5+ljbF06uJCpdi4jSSMasLjmS1oj58Rg8fGp9vxSBqcaPSN7WM5PCEN4JCxDaiR03p4odU8i+LNcAuyb8dkKM7NB77cZPwSGCAuV0a+tQUBTJ+GaMtyI6e6Y41u4Slw0HwFLHy2TnV6LcDUU723iJ0qzU+Vk+svlRg2BhmKVPdFaGn5+tL5YeQ2J3VAg588nhyOogv4StUwF8OmJH0bx5Y69kJnDLFg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000012, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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: 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; 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: 13100246 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 D9E8CC678D8 for ; Fri, 13 Jan 2023 08:27:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6835B8E0006; Fri, 13 Jan 2023 03:27:19 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 6332D8E0001; Fri, 13 Jan 2023 03:27:19 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 4FAA48E0006; Fri, 13 Jan 2023 03:27:19 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 42FDB8E0001 for ; Fri, 13 Jan 2023 03:27:19 -0500 (EST) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 223B11C5C10 for ; Fri, 13 Jan 2023 08:27:19 +0000 (UTC) X-FDA: 80349096198.14.C885791 Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.174]) by imf11.hostedemail.com (Postfix) with ESMTP id 7A31B40002 for ; Fri, 13 Jan 2023 08:27:17 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=MpnWYaJF; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf11.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1673598437; 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=Q4Az0GQIpAo5qLK4eslBRX7WJSl1cxutE/mioG/uZxc=; b=1IyRgvzIsO/ZeD1hSkOPgXHgeEHlmhN5DCGxt20QDabpDmV0m1SNTHoO8kbxYJYMGVIcXv ViTVZkFne5oV/DUxo5yruw0cnDe/7A3DTZmTTVGu1A9GOV+48jmifGzHirQ1+zfhkl7x78 gYjjJttkHDqsPVpZky/iinmspizukXQ= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=MpnWYaJF; dmarc=pass (policy=none) header.from=bytedance.com; spf=pass (imf11.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1673598437; a=rsa-sha256; cv=none; b=uBkKlCU7OKtQuPbVtb2VNILGEzk7Ts3WJxpmDRbzMdZ0fxUWSTd/4Skuwbu/f7stTcgEb7 DEBn6Bf+fXtbCBSjCgcVd1XHanzO7RvrSz+WalIGJV3zhLLZ1bXQUItK7Ljv4m9tmXtUnu IlhmQtG6jxHiAcmwYaHsW2oAH4TeIUU= Received: by mail-pl1-f174.google.com with SMTP id d9so22733423pll.9 for ; Fri, 13 Jan 2023 00:27:17 -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=B1IaLww+JGRxWhdSsC5SCGfuD5lBNvRLh6Dc8DUaww4gO/Mauwbg28hu+RGr3zlnqf uTJsMWLtnmU7cVZZjoIVZ6y0cuezrEZQ2xj99nsVf1UBOCSwWmQO9CisKsFEgVeyu75W /4qjxnmUVeU7n8fxPHcv+sFtCplq/qdZWoReIik9Xs5frMNvvm4pYv5VhIYVCCBt40es ABpMITMPg6BWeH6QNNqZYek1EdvAdfI7o+n5qDamXFZ3Fl7qIXP1bgY/SvkKkxAbDwY7 oLTpo9WHV8XtiFhVwvT/UaucseB9VSrxUeo9ZVj+HRq4LFXhsFLeLnNHA1NLWqF+XRsZ JCPg== X-Gm-Message-State: AFqh2kqaVBn/FSmHloWTdXnj7n4JhOH8fTaXop3TOq1l8g8QjQ2h/am+ gKAgcON+lWMzMud9UJhs0WFAQQ== X-Google-Smtp-Source: AMrXdXvRnSFAvuVDnwL5a9P9gCpjSMEYNO2QmBFJKhOEtNTetuC8pqV8Qm9f2UXHHySTaHSwQvLUag== 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-Rspamd-Queue-Id: 7A31B40002 X-Rspamd-Server: rspam09 X-Rspam-User: X-Stat-Signature: iwoqefwcryjpdw1c73gfnrxpobd8r7fz X-HE-Tag: 1673598437-355427 X-HE-Meta: U2FsdGVkX1/w9KbA9VylYWrTwSvPwabRECVwdD++CqofRcWcptFFVWHN69lVGzsKABj/P8U4xdET2wwPitOwMW1wujKpfHl7fvoPglw/uqjr0QmbOW64vU+RmTnU0JF+xpJY5Tv+D+f0Ygv8aaOKKTJpafed4XIzERIoEoWO7lUqgvdOae+HQrJnrKfaCeLPna5BHG5NdvXBTelS4qaDcE0TjgQLuDfTfVHmqKaUj95Wfbo5MUyMfc1+9iVCpuHMLsMEdKlsdQ0O4K9Hid78WpZcm41pqElJa6ORS2rZpn+SXU4qTnNAynx+k/3XauvbrmtQSNiZAOMMtVN/zX/6Gf0tZr03Ma/8FIzTRmwpxTedaaZmUj1BA0+49zs2bBKz82QTYXjYsG2SfJdSNvOFplr/mhPRSFY8Z37ofXbGAPSXDhXJ8z+IZ3JFdTdJg9O5qIADi7qQMdxiALTwkqTQFLJgy91xVmiadLKSUx1ak7r3naLVr6ZT9cU2DRjfogbj8UbO1yGY4lGK0Zi3LVBlBkAiqFMxudhJ4QAinSqqZX80huxdMejP+IxoOHnRE1C8aYb1WTly5Jls0gAptwIWvTt2HjK5PymPKQi05DhUgJAGFuBz2L4PV+qrv9Y9CbA2EKr901pL+4Yw1NBc14i+Im7W0qaw9cbiJr/Bhrpe2QY9fAEz//s/4EMlCLI339MKIVeZcUQsQsIMH7t+F/VCOUIYF09XNxMJHEvZWLCJwB6BRLZzU3mbHH30eGrEJey1X7F9n3jRUO5n+LsghiQuCDx8sY2Y8KzIvf3KJCZsFFmQWMX+pl1C10cHuC7DE5Q3gjG+NH8TqZlxZ0jy69q94D3TyVCvs5Bcnsb7n6PGe03QM/0C+947PKRfxy7fW7yWPLQXNMyPUMH3H8UkBT5IQgVvLY2UEYaQ3kRj13SiF2dHYQfPI70i86vezNBN8Tf7vH2dKgEv9juWzLSRkkr mBD8urNv QDLj2XtvK7AQTbqTPbEoeR5Ymm1V5LO7W2AheSVrC5sj+sYLOCuUCpc6ruVI2SWbF8rMFaDHZDJTNDI/C58qGuLYsw15ctYCvjbg5tDYZCfKY11WQnZYE5vHb+5AbGFrUCBXY/op2krqGuxtr2qjbn3bvpJtrBpaYq1MqnXHru1iRMYamX1NcBbRYdxK11Am70uZGH/Ha20Kz+KjXYHgc4r9AVGfA958nJvY+UsGVLI9ouImTNeYQbL3gzA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.006505, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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; }