From patchwork Thu Oct 24 13:19:50 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yu Kuai X-Patchwork-Id: 13849002 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 40799CE8E74 for ; Thu, 24 Oct 2024 13:23:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 60C046B00A4; Thu, 24 Oct 2024 09:23:12 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5E6E86B00A5; Thu, 24 Oct 2024 09:23:12 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 45ED76B00A6; Thu, 24 Oct 2024 09:23:12 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 27EA86B00A4 for ; Thu, 24 Oct 2024 09:23:12 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 084DFABE7F for ; Thu, 24 Oct 2024 13:22:35 +0000 (UTC) X-FDA: 82708561236.24.A4F97C9 Received: from dggsgout11.his.huawei.com (dggsgout11.his.huawei.com [45.249.212.51]) by imf02.hostedemail.com (Postfix) with ESMTP id CE0C480010 for ; Thu, 24 Oct 2024 13:22:33 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf02.hostedemail.com: domain of yukuai1@huaweicloud.com designates 45.249.212.51 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=1729776021; 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=6yrMSZTMaUKbGiGffLG5dPC7ELvN1G+C4UVxR+KB0cs=; b=hNzqkEdHWtk6R+O8sfSowC7I3Ql4EhtkdR3TLu+3xpiWMm4ZP1rfigZZEsYvHrMl0yQL2+ Sdg1GyFByXm+c8o1mneFriojwDcwTtqahuFXBaFT+MFgBn34mJx1iJEWtFLZE/LvERX16k cylWLuV2EMXdyAb5Jzt7FzY+X0+fe/c= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1729776021; a=rsa-sha256; cv=none; b=4TRtbMfdJaM/28V+ywPUvxw/rY5l8pxhRC4zvjYfvVjAM+seAKTAXD2bW5YiQkqHlQ1SYY nVU8fSkD4eT2u/hgJqZQpdQvBdzGbmqDjE5ZH7AfLuSrZJYoAaQNq0kQS6A/3u23kdrIwX BbcLF66UPQJNxw2GqykAXyjt4IA8zSI= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=none; dmarc=none; spf=pass (imf02.hostedemail.com: domain of yukuai1@huaweicloud.com designates 45.249.212.51 as permitted sender) smtp.mailfrom=yukuai1@huaweicloud.com Received: from mail.maildlp.com (unknown [172.19.93.142]) by dggsgout11.his.huawei.com (SkyGuard) with ESMTP id 4XZ66N2FD7z4f3l88 for ; Thu, 24 Oct 2024 21:22:52 +0800 (CST) Received: from mail02.huawei.com (unknown [10.116.40.128]) by mail.maildlp.com (Postfix) with ESMTP id A9C551A0359 for ; Thu, 24 Oct 2024 21:23:04 +0800 (CST) Received: from huaweicloud.com (unknown [10.175.104.67]) by APP4 (Coremail) with SMTP id gCh0CgCHusYpShpn7tb6Ew--.444S13; Thu, 24 Oct 2024 21:23:04 +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 09/28] maple_tree: add end of node tracking to the maple state Date: Thu, 24 Oct 2024 21:19:50 +0800 Message-Id: <20241024132009.2267260-10-yukuai1@huaweicloud.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20241024132009.2267260-1-yukuai1@huaweicloud.com> References: <20241024132009.2267260-1-yukuai1@huaweicloud.com> MIME-Version: 1.0 X-CM-TRANSID: gCh0CgCHusYpShpn7tb6Ew--.444S13 X-Coremail-Antispam: 1UD129KBjvJXoWxAFW8WFyDWFyDKFWrAF4fKrg_yoW5try8pa 1kuryUKrW7tr1xKrZaka18Z348Zrn8Jr4Sq3sFkrnYvF9rt34Sqr1FyFy0vFs0v392vF43 AF4Y9r48Cws7J37anT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDU0xBIdaVrnRJUUUmq14x267AKxVWrJVCq3wAFc2x0x2IEx4CE42xK8VAvwI8IcIk0 rVWrJVCq3wAFIxvE14AKwVWUJVWUGwA2048vs2IY020E87I2jVAFwI0_JF0E3s1l82xGYI kIc2x26xkF7I0E14v26ryj6s0DM28lY4IEw2IIxxk0rwA2F7IY1VAKz4vEj48ve4kI8wA2 z4x0Y4vE2Ix0cI8IcVAFwI0_Ar0_tr1l84ACjcxK6xIIjxv20xvEc7CjxVAFwI0_Gr1j6F 4UJwA2z4x0Y4vEx4A2jsIE14v26rxl6s0DM28EF7xvwVC2z280aVCY1x0267AKxVW0oVCq 3wAS0I0E0xvYzxvE52x082IY62kv0487Mc02F40EFcxC0VAKzVAqx4xG6I80ewAv7VC0I7 IYx2IY67AKxVWUGVWUXwAv7VC2z280aVAFwI0_Jr0_Gr1lOx8S6xCaFVCjc4AY6r1j6r4U M4x0Y48IcxkI7VAKI48JM4x0x7Aq67IIx4CEVc8vx2IErcIFxwACI402YVCY1x02628vn2 kIc2xKxwCY1x0262kKe7AKxVWrXVW3AwCF04k20xvY0x0EwIxGrwCFx2IqxVCFs4IE7xkE bVWUJVW8JwC20s026c02F40E14v26r1j6r18MI8I3I0E7480Y4vE14v26r106r1rMI8E67 AF67kF1VAFwI0_Wrv_Gr1UMIIYrxkI7VAKI48JMIIF0xvE2Ix0cI8IcVAFwI0_Gr0_Xr1l IxAIcVC0I7IYx2IY6xkF7I0E14v26r4UJVWxJr1lIxAIcVCF04k26cxKx2IYs7xG6r1j6r 1xMIIF0xvEx4A2jsIE14v26r4j6F4UMIIF0xvEx4A2jsIEc7CjxVAFwI0_Gr1j6F4UJbIY CTnIWIevJa73UjIFyTuYvjTRAR6zUUUUU X-CM-SenderInfo: 51xn3trlr6x35dzhxuhorxvhhfrp/ X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: CE0C480010 X-Stat-Signature: nxzx854jfinaps9ngwidsisgwj5jzbrh X-Rspam-User: X-HE-Tag: 1729776153-187019 X-HE-Meta: U2FsdGVkX1/d9nbuKqIiFRojpgb6kjRfIBNo6x1sPjYkePri+ULzMynYs83AaxeCQekpadBicHwQA8JndqjW5E2syxxVkjko4mZD2Tin0bA7UNz/2I4kUrwIPatcd8EP89d9ECDQJYUEGp+vcf13C1PG9yeu2xUhEmtKG5hN9qOQrHySnubOnQdMMGChp8M4QCXy0A81ehWGdzKNDQxe5/1NcG6DNsHt4jV5EAWTPWrCS8w4ErNS2DlO5dyIFq3F6bBC+gZBOydPWhmJ+ryvfdtSWkKH4gf1Z3ONcjsFQWvRlZZxk5FY3NzWNgf7zv+0kwcubuZSUqHGj5oMci0ah+uOE7DFaCK/mFlLql4RL+Ey/BMDPglOP/HWwq1U1Sqegw3uf/dZBmGXNqhlcx8yeZw5UNzTeqEcJFYnsHkeEx4vqjCP/qz1L2EOiXzkgOLdacAzD4anMkV55TXDP1f7KLhaE1/7y036WZ95WNwmLjs8BKcjpAM5CJimgnblXLE+ghx+UVCdaLvClukSqcZKNAQATkWhE9KI2RuTLinGiSUcUJReZNZAYl1w9GZFG8Ngi9fAP2D/ytQBmI9OmzQ6CMOAZdiLuF+DJLF0jT5CWrBs8xEytcpWR1qobWmUhWdMSlZWqT+wh3VpqgqXqVILF2mgdXHGQ+OL42WzJwwSWWArhrpUNrQyQ/llRqUS2m5ZB7YHHz3/ysh0l4nbU/xub5Zbu10RSMv5QHztLtPVZp3DdSTFWJic2OvYOqPAWJ2Q7cmAw0mtAJBg0RI5bhKFqg6ww1lHSjtzjx3yU2akZKiZHB8Yt8RAtqferZyADat+4b+nKR6zoyJ91dooVS2khcfcqEXRscfhuAzEaRKTKUx4wNP3i6yr38blWhTywyiF/G/ZpoUOJLBZIwPs5bCGW/pq9skMk2KGNcelYItyN5H4rT5e4cLc1QdwJP04EpAX9QWXhSL8if61wRZE/cK ONBLNdB2 GUwE5XugriG51W0TqWsYkLuDD6jLCivm6rSJzEdv5hJ7rl90FynJ38xboeejlwbdY7wz0UpxJyUe+XkYYW9MNGFHehH8G94jHlRE+DLMQ6l0KxA3T8pVHRTrbGzZEyQ51mnw3dOSEu67j46jKRkWB+8Z15MlHFY3SPz1w2QgXQYRSR51N1wAdc09TmdHb23YquqXe+hjgKx73KAEHg3QgC34QvYeN8O+lMeadXcs8Mg7RZIj2z0dfmxka7nA5cqZz6quhhlhSUyRwjhw4ypBBZsOR+Cp6VnwTqo3tUcv22pR0CLBdigsyUiWiew== 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 31c532a8af57513228c2b12d281104198ff412b8 upstream. Analysis of the mas_for_each() iteration showed that there is a significant time spent finding the end of a node. This time can be greatly reduced if the end of the node is cached in the maple state. Care must be taken to update & invalidate as necessary. Link: https://lkml.kernel.org/r/20231101171629.3612299-5-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Peng Zhang Signed-off-by: Andrew Morton Signed-off-by: Yu Kuai --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 7 +++++++ tools/testing/radix-tree/maple.c | 1 + 3 files changed, 9 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index b5d5992578c9..0b82efe0cf1e 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -393,6 +393,7 @@ struct ma_state { unsigned char depth; /* depth of tree descent during write */ unsigned char offset; unsigned char mas_flags; + unsigned char end; /* The end of the node */ }; struct ma_wr_state { diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e4d0df3980e0..d19fb14a9635 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2843,6 +2843,7 @@ static inline void *mtree_range_walk(struct ma_state *mas) goto dead_node; } while (!ma_is_leaf(type)); + mas->end = end; mas->offset = offset; mas->index = min; mas->last = max; @@ -3509,6 +3510,7 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas, mas_replace_node(wr_mas->mas, old_enode); reuse_node: mas_update_gap(wr_mas->mas); + wr_mas->mas->end = b_end; return 1; } @@ -4010,6 +4012,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas, } trace_ma_write(__func__, mas, 0, wr_mas->entry); mas_update_gap(mas); + mas->end = new_end; return true; } @@ -4190,6 +4193,7 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas, if (!wr_mas->content || !wr_mas->entry) mas_update_gap(mas); + mas->end = new_end; trace_ma_write(__func__, mas, new_end, wr_mas->entry); return true; } @@ -4428,6 +4432,7 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) if (unlikely(mte_dead_node(mas->node))) return 1; + mas->end = mas->offset; return 0; no_entry: @@ -5074,6 +5079,7 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, if (mas->index < min) mas->index = min; mas->last = mas->index + size - 1; + mas->end = mas_data_end(mas); return 0; } EXPORT_SYMBOL_GPL(mas_empty_area); @@ -5134,6 +5140,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, mas->last = max; mas->index = mas->last - size + 1; + mas->end = mas_data_end(mas); return 0; } EXPORT_SYMBOL_GPL(mas_empty_area_rev); diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 576b825d6bb1..27a3a31ba662 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -945,6 +945,7 @@ static inline bool mas_tree_walk(struct ma_state *mas, unsigned long *range_min, goto retry; } + mas->end = mas_data_end(mas); return ret; not_found: