From patchwork Thu Oct 24 13:22:18 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yu Kuai X-Patchwork-Id: 13849013 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 94EC6CE8E74 for ; Thu, 24 Oct 2024 13:25:29 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 067A56B00AE; Thu, 24 Oct 2024 09:25:23 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id F3ECA6B00B1; Thu, 24 Oct 2024 09:25:22 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C751F6B00B0; Thu, 24 Oct 2024 09:25:22 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id A28756B00AD for ; Thu, 24 Oct 2024 09:25:22 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 4A6D38018F for ; Thu, 24 Oct 2024 13:25:06 +0000 (UTC) X-FDA: 82708567116.14.D98A44E Received: from dggsgout12.his.huawei.com (dggsgout12.his.huawei.com [45.249.212.56]) by imf24.hostedemail.com (Postfix) with ESMTP id D3B7318001D for ; Thu, 24 Oct 2024 13:25:16 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf24.hostedemail.com: domain of yukuai1@huaweicloud.com designates 45.249.212.56 as permitted sender) smtp.mailfrom=yukuai1@huaweicloud.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1729776168; 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; bh=dxEKHoobvmwfAm//zYdEUibmC1ajojI5XQOXeJ9R3ZY=; b=ih7k6bLQNKpy8EUSXZpb9J5bdzLQ9W+i2gia6i85BTuR9EMOxLd+FifxiRBqWFQe8juk99 s9pDG6oEy0Fz4ktrLuwvxKnoyedp6hxOgEVop6+ZT+jHBfC30CNoX8Q2wNAoYoTl8AtWFv kQx4o8S/AWYPnLJt0Q8n8BKeAREht/o= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729776168; a=rsa-sha256; cv=none; b=GuRLv2cAMFfYf9Sx/TqX+C+nXmM1vwhUffabif5Po1pIh348s2THuUEQqKDe87yKvBOJh3 +lN+oeC6VZV/ElpZbhHFH1qJckrkJ0OiDwH3L7cUEiTRzjFrKF6j7zm214+S+X2VTHiTUl uK8b9QWEb+lbfyHbL5Bmm67SGT9LIWI= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf24.hostedemail.com: domain of yukuai1@huaweicloud.com designates 45.249.212.56 as permitted sender) smtp.mailfrom=yukuai1@huaweicloud.com Received: from mail.maildlp.com (unknown [172.19.163.216]) by dggsgout12.his.huawei.com (SkyGuard) with ESMTP id 4XZ68m5SbPz4f3jdY for ; Thu, 24 Oct 2024 21:24:56 +0800 (CST) Received: from mail02.huawei.com (unknown [10.116.40.128]) by mail.maildlp.com (Postfix) with ESMTP id 3C2D21A0194 for ; Thu, 24 Oct 2024 21:25:14 +0800 (CST) Received: from huaweicloud.com (unknown [10.175.104.67]) by APP4 (Coremail) with SMTP id gCh0CgD3LMmxShpnmfz6Ew--.42902S9; Thu, 24 Oct 2024 21:25:13 +0800 (CST) From: Yu Kuai To: stable@vger.kernel.org, gregkh@linuxfoundation.org, harry.wentland@amd.com, sunpeng.li@amd.com, Rodrigo.Siqueira@amd.com, alexander.deucher@amd.com, christian.koenig@amd.com, Xinhui.Pan@amd.com, airlied@gmail.com, daniel@ffwll.ch, viro@zeniv.linux.org.uk, brauner@kernel.org, Liam.Howlett@oracle.com, akpm@linux-foundation.org, hughd@google.com, willy@infradead.org, sashal@kernel.org, srinivasan.shanmugam@amd.com, chiahsuan.chung@amd.com, mingo@kernel.org, mgorman@techsingularity.net, yukuai3@huawei.com, chengming.zhou@linux.dev, zhangpeng.00@bytedance.com, chuck.lever@oracle.com Cc: amd-gfx@lists.freedesktop.org, dri-devel@lists.freedesktop.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, yukuai1@huaweicloud.com, yi.zhang@huawei.com, yangerkun@huawei.com Subject: [PATCH 6.6 21/28] maple_tree: avoid checking other gaps after getting the largest gap Date: Thu, 24 Oct 2024 21:22:18 +0800 Message-Id: <20241024132225.2271667-6-yukuai1@huaweicloud.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20241024132225.2271667-1-yukuai1@huaweicloud.com> References: <20241024132009.2267260-1-yukuai1@huaweicloud.com> <20241024132225.2271667-1-yukuai1@huaweicloud.com> MIME-Version: 1.0 X-CM-TRANSID: gCh0CgD3LMmxShpnmfz6Ew--.42902S9 X-Coremail-Antispam: 1UD129KBjvJXoW7GrW8Cw1xJw1UGFWrCw48JFb_yoW8Jr15pF WDCw1Fg34Ivr1xCryDWa1Fqa4DA3Zaqw1xtayqkrnYqr4UK3Zag34Skw1F9a13W34kCw13 Ja1av348ta4Dt37anT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDU0xBIdaVrnRJUUUmI14x267AKxVWrJVCq3wAFc2x0x2IEx4CE42xK8VAvwI8IcIk0 rVWrJVCq3wAFIxvE14AKwVWUJVWUGwA2048vs2IY020E87I2jVAFwI0_JF0E3s1l82xGYI kIc2x26xkF7I0E14v26ryj6s0DM28lY4IEw2IIxxk0rwA2F7IY1VAKz4vEj48ve4kI8wA2 z4x0Y4vE2Ix0cI8IcVAFwI0_Ar0_tr1l84ACjcxK6xIIjxv20xvEc7CjxVAFwI0_Cr1j6r xdM28EF7xvwVC2z280aVAFwI0_GcCE3s1l84ACjcxK6I8E87Iv6xkF7I0E14v26rxl6s0D M2AIxVAIcxkEcVAq07x20xvEncxIr21l5I8CrVACY4xI64kE6c02F40Ex7xfMcIj6xIIjx v20xvE14v26r1Y6r17McIj6I8E87Iv67AKxVWUJVW8JwAm72CE4IkC6x0Yz7v_Jr0_Gr1l F7xvr2IYc2Ij64vIr41lF7I21c0EjII2zVCS5cI20VAGYxC7M4IIrI8v6xkF7I0E8cxan2 IY04v7MxkF7I0En4kS14v26rWY6Fy7MxAIw28IcxkI7VAKI48JMxC20s026xCaFVCjc4AY 6r1j6r4UMI8I3I0E5I8CrVAFwI0_Jr0_Jr4lx2IqxVCjr7xvwVAFwI0_JrI_JrWlx4CE17 CEb7AF67AKxVWrXVW8Jr1lIxkGc2Ij64vIr41lIxAIcVC0I7IYx2IY67AKxVW5JVW7JwCI 42IY6xIIjxv20xvEc7CjxVAFwI0_Cr1j6rxdMIIF0xvE42xK8VAvwI8IcIk0rVWUJVWUCw CI42IY6I8E87Iv67AKxVW8JVWxJwCI42IY6I8E87Iv6xkF7I0E14v26F4UJVW0obIYCTnI WIevJa73UjIFyTuYvjTRGg4SUUUUU X-CM-SenderInfo: 51xn3trlr6x35dzhxuhorxvhhfrp/ X-Rspamd-Queue-Id: D3B7318001D X-Stat-Signature: 5z7j5au8xitririjg1hw1odotjz36q33 X-Rspamd-Server: rspam09 X-Rspam-User: X-HE-Tag: 1729776316-287129 X-HE-Meta: U2FsdGVkX18fX9UxpcvaAY8ELEyxBGs1sKFr3g4FqvKUMkA1byx/ciPU/KSazT6nxMWF7DIkiHN+xFIJEcdwNJ1J1XrNeq6jLCbOCkHdNSrqFxCtqwp/KRjPzXUd/L9wBbaFl0Ydv6aefgTcb+qurhWTTv+dOO3m/eWM/ixUJSSWJckMWbM+oxoCY1WcM53gAxhs/0LwTqn+aRGmdvlR09hEvOLj8xz63lBKviaDpk7aWVruPWCkqN9O9QsEsyaO3nNMIKKYlRnlOaDKIIG+q3ZcrjntAk91lmiy33b76bBUBpqPiS89mg0Ul/ds25iNkSsLAvPq+qJrL5+hLOQMYcXW3s1X92b50YsghtsFGbDUQ9+rEFpCznxMb4HY8BF3am+r7UfZOt48krEy1sL5eTUvIE43EF/AShFN/PxeiRbNcMxztV0GK79OaGBg3uz8kFBxDBjg2sj0HfprU0Dd0hLuxCks2b62zgxUGWAmm7npxidwBSJxQwzPIM/MTHDaLgD3XrGncpjZqbY63PNMyTYKd84A1vULrEJ+ruR9RMTAPCdFYdJiG3qR1rGxJ9NW5TJ4NRsbp7nSLyf2u/omLRtXSyuomlbzVH3+MRK1Fw12QmS4qezS2IvR85oFsQo/VspCZLjF0sYIhyy3gj5wPBZ636AuRaFxSMGCXbDM+OQ/wGaE/Xkx/m1HH7zQHbSSTySJrOK8afmwIq1UtzycNSTwqrTh5mbWIom6mCgf7iWmJarPuu5tbk2WEgu20r0gIid7hQDyI+Wx4uLnpOzFqQJCWufJXNwH6/IjOCC0+d0b6fXFMZSy83fQ1Q7ZLejraAeerKCLptuAoedQL2OA4iv/hu6ZVDU5DBGeEr+gUlmpqysxmRnbf8X78e2p2cD8u0AEyTst+ssNNlpFpLJ7wALUxBVQuZcbS/FH5EqDNS2kD+aZIM53FITTUyqEPG+NN8XZApuf5e5Vllk9KxD XHqkWMKz h2bPe3774afuL+DWD5NUrNcruwLs9avis9WkrSC+xqh0qu5eLsSDfGqx31UuR0MEVzC/7IVrJkCRQMdVQFboUaQ7cWS12J4lgadbIbsgYZYDpwFlWXPh0TK9Ll6MTvUbKLbQGXh8562MWWtYJaZ4khCoBbpcF9ByG++uAxzIiRJDLs5BiKyqRJP8f2+8BkaQJ1JU3obZK/2+pnkRLCMo2IQO1IHf7Y9oCwUPEYkY8pc34E5Q0TerB33A9hR4yBhM4NkFH7cpP+7zV4DRWnV4/oJbHJk0DzpF32l0j9hHSaZzCIHPfSKcoaGRY4Q== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: From: Peng Zhang commit 7e552dcd803f4ff60165271c573ab2e38d15769f upstream. The last range stored in maple tree is typically quite large. By checking if it exceeds the sum of the remaining ranges in that node, it is possible to avoid checking all other gaps. Running the maple tree test suite in user mode almost always results in a near 100% hit rate for this optimization. Link: https://lkml.kernel.org/r/20231215074632.82045-1-zhangpeng.00@bytedance.com Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett Signed-off-by: Andrew Morton Signed-off-by: Yu Kuai --- lib/maple_tree.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 905fa1143f8d..1af83414877a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1547,6 +1547,9 @@ static unsigned long mas_leaf_max_gap(struct ma_state *mas) gap = ULONG_MAX - pivots[max_piv]; if (gap > max_gap) max_gap = gap; + + if (max_gap > pivots[max_piv] - mas->min) + return max_gap; } for (; i <= max_piv; i++) {