From patchwork Thu Oct 24 13:22:15 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yu Kuai X-Patchwork-Id: 13849010 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 16C60CE8E75 for ; Thu, 24 Oct 2024 13:25:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id C03C86B0099; Thu, 24 Oct 2024 09:25:17 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id AEEBC6B009C; Thu, 24 Oct 2024 09:25:17 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8A3026B009D; Thu, 24 Oct 2024 09:25:17 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 664D86B009C for ; Thu, 24 Oct 2024 09:25:17 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id F003C1A0AF0 for ; Thu, 24 Oct 2024 13:24:43 +0000 (UTC) X-FDA: 82708566612.15.EF79851 Received: from dggsgout12.his.huawei.com (dggsgout12.his.huawei.com [45.249.212.56]) by imf07.hostedemail.com (Postfix) with ESMTP id 02EEC40012 for ; Thu, 24 Oct 2024 13:24:48 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf07.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=1729776146; 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=zt5F6jt59kFkxKeRBANwkTX5x1oNFddxO6trAt9QbnM=; b=JDrZH6Ey5JsR0qNNYAxF/ZizZIcw2oe5ve/0oEZQ2xPPrLgyjC/o9M/goRiX5Pqz3L0w7h 5q0nGmaVtP3u+kWdxMuVOen6YdE4lcVT6NFQtnjAPqnio3C5mjbJf6z1ynx3+q2Ugzo3eg MUFTrYlGotXijfuxtwKZDMIkL+Bee98= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729776146; a=rsa-sha256; cv=none; b=5fk+nIgS7Ob+bCVJ1FRwBlGTpNKMnx0MenIDe34a65JHCtAe7E8Iu/koheZGtB+Ms85IVp d9h87GooDZIdlf83Re21C6cgfVqM+vAlv9CRlH4KccFXcy/HrWFPlpiXwJB3Zcm9naESOy WMSqrR4J3aBiswxETQ6DOxyqWfv5qpo= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf07.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 4XZ68j1kYNz4f3jHn for ; Thu, 24 Oct 2024 21:24:53 +0800 (CST) Received: from mail02.huawei.com (unknown [10.116.40.128]) by mail.maildlp.com (Postfix) with ESMTP id B19671A0196 for ; Thu, 24 Oct 2024 21:25:10 +0800 (CST) Received: from huaweicloud.com (unknown [10.175.104.67]) by APP4 (Coremail) with SMTP id gCh0CgD3LMmxShpnmfz6Ew--.42902S6; Thu, 24 Oct 2024 21:25:10 +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 18/28] maple_tree: don't find node end in mtree_lookup_walk() Date: Thu, 24 Oct 2024 21:22:15 +0800 Message-Id: <20241024132225.2271667-3-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--.42902S6 X-Coremail-Antispam: 1UD129KBjvJXoWxAry3tryUGF4kCw43Gw1DGFg_yoW5Cw4fp3 ZrGFy5tFyfAF4xWrWfKa18X34fXFs3Gr17t3yDGryrZFyUGw1Igr1rCryfurWagayxu3Wf Aa1Yqw18W3Z7JFJanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDU0xBIdaVrnRJUUUmY14x267AKxVWrJVCq3wAFc2x0x2IEx4CE42xK8VAvwI8IcIk0 rVWrJVCq3wAFIxvE14AKwVWUJVWUGwA2048vs2IY020E87I2jVAFwI0_Jryl82xGYIkIc2 x26xkF7I0E14v26ryj6s0DM28lY4IEw2IIxxk0rwA2F7IY1VAKz4vEj48ve4kI8wA2z4x0 Y4vE2Ix0cI8IcVAFwI0_Ar0_tr1l84ACjcxK6xIIjxv20xvEc7CjxVAFwI0_Cr1j6rxdM2 8EF7xvwVC2z280aVAFwI0_GcCE3s1l84ACjcxK6I8E87Iv6xkF7I0E14v26rxl6s0DM2AI xVAIcxkEcVAq07x20xvEncxIr21l5I8CrVACY4xI64kE6c02F40Ex7xfMcIj6xIIjxv20x vE14v26r1Y6r17McIj6I8E87Iv67AKxVWUJVW8JwAm72CE4IkC6x0Yz7v_Jr0_Gr1lF7xv r2IYc2Ij64vIr41lF7I21c0EjII2zVCS5cI20VAGYxC7M4IIrI8v6xkF7I0E8cxan2IY04 v7MxkF7I0En4kS14v26rWY6Fy7MxAIw28IcxkI7VAKI48JMxC20s026xCaFVCjc4AY6r1j 6r4UMI8I3I0E5I8CrVAFwI0_Jr0_Jr4lx2IqxVCjr7xvwVAFwI0_JrI_JrWlx4CE17CEb7 AF67AKxVWrXVW8Jr1lIxkGc2Ij64vIr41lIxAIcVC0I7IYx2IY67AKxVW5JVW7JwCI42IY 6xIIjxv20xvEc7CjxVAFwI0_Cr1j6rxdMIIF0xvE42xK8VAvwI8IcIk0rVWUJVWUCwCI42 IY6I8E87Iv67AKxVW8JVWxJwCI42IY6I8E87Iv6xkF7I0E14v26F4UJVW0obIYCTnIWIev Ja73UjIFyTuYvjTRGApnUUUUU X-CM-SenderInfo: 51xn3trlr6x35dzhxuhorxvhhfrp/ X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 02EEC40012 X-Stat-Signature: yig3i6q1c6fqmcgj61qhmqoze1fcdyec X-Rspam-User: X-HE-Tag: 1729776288-916425 X-HE-Meta: U2FsdGVkX1+QKCcMXCBh8kVruDRPEn3WsNBySNjvNH5WOHW7u5GfrZHWbM2O9KOsFKHsSZBX6jGPg2xfQwaWNVxPaj1YHMjpQiNF48mkJHRhuGvNUSKkojM3PRwv4NG9QTQNtp9o4TpOxmi3+m7bHzYsVKgCrVwpb/eboXNm5jXsBu74AdF6UcWkTpZ6Qh8xXzH17UfqnRCwMJ2eRh4t3TTijFEuI8ELJIAXihYdiZ9FtPjep8WXNfBZOSbgUqp/jOG5KFkQZ4eHA2g5Ia5Kkohu1wdlNak88JKT8jaI8JJHgYzF1ROzZQzl1iCk0zZItZ/CuM8t5lLmSjMwmxDJiM+ZuahLQobQWySi5Q5+NW6yxF/eexQmlitAF1gFQEXfRnyNTVPBuT78A/0V5F3mu/1F/jUnsGqlGXKP4feemOQjOzynAWFq9hOkOACCn87L7C1le7LiVEb86RFwnl2bhY6gvXQ7f4Af3MGIJlXQpr/bEok7YWMx3goN2B6F7BAN7G/OpIv1XdaEPML0GLdu6BQjear2rD+rqmrIg/FBtF2sbzeDMtnNO7HX8pGhpKvj/M+kylHSqt0d3ytoCGRrZDUZfsj0M6krnRP7T1QIv6Mewwxbe7HvwiIWeFxZrErxFx20125uwvYo/TDwu6C/qk6JmtmhyX0AKVaJEgvlBIqJfEuyjkBuwYCretionyOAslzktskFNH5rDNq0cT6Zy/DdmcbWyFXDXLljKyRjtjyqmydY8vGHw3Qres/2eNqF61q0Ia3dwGqLsIn5ccTsjPvdOBkj6DdcUHwLxQn25zF5+xyMdHqGC+P8vdBTYZVCJoIIHKtkFo5uIPGfGlqoFGjXRLwIB8SplVgzKa2IiKP/A9Z1vGqNyaaeJCIFAXWoCfIpNUdFiJWerFw4g6ybcLWZ1Y/b63LR7aAJcpXurRmubN3sJFLkjdP4ppjTXpHfiEze4JGSOS4Jkku06z8 m4kXYKfa rl9Vx3ytL5QYHrGrsLlK//8ECgJ/JzW/6VN4+OL+PE0KBv52TPKBi6klZxrxvev97nO3gqeYjc62SAX9Uhj68tqnoZLT0UdN94Ip4We0YXsiLv354tF7qRJFzz3zSUnRL4Y+abUNbkm0Ow2lBdYJLwPVmKBE382MuiqVvWBxG5rJLzt6fKlR/lDsBnMIw5ByZFUAfaMTryw2wsxTPNvQzcdrejOe+KN6/ncGlphDyQR6XGY29MKuj/+eBYtSCgVgEywYDwwloyFx5BH4nc/1orQniOhG6veZMSZFsJRg1VTADfmF/+IrUgmUt4Q== 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: "Liam R. Howlett" commit 24662decdd44645e8f027d7912be962dd461d1aa upstream. Since the pivot being set is now reliable, the optimized loop no longer needs to find the node end. The redundant check for a dead node can also be avoided as there is no danger of using the wrong pivot since the results will be thrown out in the case of a dead node by the later check. This patch also adds a benchmark test for the function to the maple tree test framework. The benchmark shows an average increase performance of 5.98% over 3 runs with this commit. Link: https://lkml.kernel.org/r/20231101171629.3612299-12-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Peng Zhang Signed-off-by: Andrew Morton Signed-off-by: Yu Kuai --- lib/maple_tree.c | 12 +++--------- lib/test_maple_tree.c | 21 +++++++++++++++++++++ 2 files changed, 24 insertions(+), 9 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 472aef7a3d5c..ad8bf3413889 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3742,23 +3742,17 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) enum maple_type type; void __rcu **slots; unsigned char end; - unsigned long max; next = mas->node; - max = ULONG_MAX; do { - offset = 0; node = mte_to_node(next); type = mte_node_type(next); pivots = ma_pivots(node, type); - end = ma_data_end(node, type, pivots, max); - if (unlikely(ma_dead_node(node))) - goto dead_node; + end = mt_pivots[type]; + offset = 0; do { - if (pivots[offset] >= mas->index) { - max = pivots[offset]; + if (pivots[offset] >= mas->index) break; - } } while (++offset < end); slots = ma_slots(node, type); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index f9acc6ef0728..26991888da14 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -43,6 +43,7 @@ atomic_t maple_tree_tests_passed; /* #define BENCH_NODE_STORE */ /* #define BENCH_AWALK */ /* #define BENCH_WALK */ +/* #define BENCH_LOAD */ /* #define BENCH_MT_FOR_EACH */ /* #define BENCH_FORK */ /* #define BENCH_MAS_FOR_EACH */ @@ -1754,6 +1755,19 @@ static noinline void __init bench_walk(struct maple_tree *mt) } #endif +#if defined(BENCH_LOAD) +static noinline void __init bench_load(struct maple_tree *mt) +{ + int i, max = 2500, count = 550000000; + + for (i = 0; i < max; i += 10) + mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL); + + for (i = 0; i < count; i++) + mtree_load(mt, 1470); +} +#endif + #if defined(BENCH_MT_FOR_EACH) static noinline void __init bench_mt_for_each(struct maple_tree *mt) { @@ -3620,6 +3634,13 @@ static int __init maple_tree_seed(void) mtree_destroy(&tree); goto skip; #endif +#if defined(BENCH_LOAD) +#define BENCH + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + bench_load(&tree); + mtree_destroy(&tree); + goto skip; +#endif #if defined(BENCH_FORK) #define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);