From mboxrd@z Thu Jan 1 00:00:00 1970 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 70FAFC001DC for ; Wed, 26 Jul 2023 08:09:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D214D6B0074; Wed, 26 Jul 2023 04:09:58 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CAB6D8D0001; Wed, 26 Jul 2023 04:09:58 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B4C6B6B0078; Wed, 26 Jul 2023 04:09:58 -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 A22026B0074 for ; Wed, 26 Jul 2023 04:09:58 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 726461201A8 for ; Wed, 26 Jul 2023 08:09:58 +0000 (UTC) X-FDA: 81053039676.26.4747471 Received: from mail-pg1-f178.google.com (mail-pg1-f178.google.com [209.85.215.178]) by imf20.hostedemail.com (Postfix) with ESMTP id 9C8281C0003 for ; Wed, 26 Jul 2023 08:09:56 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Hi4bTAj2; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.178 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=1690358996; 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=GIT4erJsSQIWC2QtZ169UhvGSIUrHQbWmspV6b3RxCk=; b=CPGq7Q8lOgyPcA6TBnieB3mRgpdB5cCxWi4Qh316AQFam/qLjmCwdZkWcqj58epTZO3OXM gNSYX1Ya2JC07RH9eFeJ0HPgtssXAb2SPFOc5ZXX1EZpHwTcyMASPJns4abefFg7xpb5tg pekd6l+7ZGA07db9OsOkFFJoKMzBEUM= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Hi4bTAj2; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690358996; a=rsa-sha256; cv=none; b=qrlhfVkYwOA/QQgZi1id+MoGz77uKd0VyN2FAgelV8wv0DLPcYdioAmU8Pz+ZooVhXCC9A cdHfKBzBhRmcBmx+L0IA7nh3TOabhA8PbPN7RQ7XXpX7LQ5sIZ9aY7BlDodM5XmL7QMhnA 2HrHE/0GYZXcmLgXb6lVgZ6kc2eA+5Q= Received: by mail-pg1-f178.google.com with SMTP id 41be03b00d2f7-55b5a3915f5so3256112a12.0 for ; Wed, 26 Jul 2023 01:09:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690358995; x=1690963795; 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=GIT4erJsSQIWC2QtZ169UhvGSIUrHQbWmspV6b3RxCk=; b=Hi4bTAj2w5H2xNQiLID4Hia2qzuatOrdKEXuIHwgfQq4h5TogE8UlYPLPr4GbRqm0t bir4kr6IwT4SUpGIrXSZ4kUtFow9YDCvc0PSsNFaFKeVcnfY/tlQui4eRr3KN7eX274n u6Al0q6bZSrERi3GamYqKl9Z2w0C884Shf+SlR3209WA6vvKX5T7a5zszboxPBvYa9QQ gz6TciUgktOetIsNxr9d7qgzK6KCCnMoSiwCmg8JTNl2AOqjwe/mUswmU4FcnPJ0zNg4 SOPE/TJNK04LNOIeKt6aNMQU4jIO/Np2hanV3cU01WxmakYXecUILeywfx6kY/dSyQ0p Jxgw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690358995; x=1690963795; 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=GIT4erJsSQIWC2QtZ169UhvGSIUrHQbWmspV6b3RxCk=; b=XMZBqXWXsnDsN/5Uma2qvRTblY6RqMYF5Q/GFwzX8Uv5Bl+Yq03dLgSt9KlnGJCqzz NNxjewQCsutUVZLjuKKLGZ59iSSaJfxzeMbz4+g/U/rlSglYkh+phDkVUXK6z9KuaX1B wjxPvKR5sPaLqQ87waIji3ZvPENuwyX1M//O8zFXKIzFNnnb5C1+vRCk8SlS0oQeEzRq yB9dZ8H/sf8gPICeQasEhhWH359Dynn3PUt5M9ofP8zOLf1gIaZMLgcy7pv8U6ALMEXd Izpr3yNVFcV/VEAAcRtQXyp8PdvlvwAC/sOLt+/KEFGP6pYrMlgSEgRfs9QxX6FDm2HU RZPQ== X-Gm-Message-State: ABy/qLa7bGxXvcrjdi+uPm5agocLnorgfbO+DJAr5UjYmgeD5TE5CDZ7 yFBZix5z0lKU4uOklgH0YGqA0g== X-Google-Smtp-Source: APBJJlGTCbgSnoEUEY2Im4b6IteSzBL20T2KsQb6OtigwSGhrzItecI4bNmqd6Se4OFmw5iiEF2MyQ== X-Received: by 2002:a17:90a:c002:b0:268:2500:b17e with SMTP id p2-20020a17090ac00200b002682500b17emr1115938pjt.23.1690358995399; Wed, 26 Jul 2023 01:09:55 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id gc17-20020a17090b311100b002680b2d2ab6sm756540pjb.19.2023.07.26.01.09.49 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:09:55 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH 01/11] maple_tree: Introduce ma_nonleaf_data_end{_nocheck}() Date: Wed, 26 Jul 2023 16:09:06 +0800 Message-Id: <20230726080916.17454-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230726080916.17454-1-zhangpeng.00@bytedance.com> References: <20230726080916.17454-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Rspam-User: X-Stat-Signature: mzij1whj8j1wmqyazhe6jnf58ue3pyfz X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 9C8281C0003 X-HE-Tag: 1690358996-170857 X-HE-Meta: U2FsdGVkX1+ODeQNMT6NuhF9hdqlURNmlTc1BqMQn101WEHOAGjZJcXKoueKmCNdfOyCUNjA9XgFEzN+AFZE6vW1X1/1k3bk5mpSImftZdKuT0hj5qjscU0uEMKq5Ke6F0R7tnR3IVYoFCOKjluTyViQFgL3FTgNfaVNrMCTGbV962LGUCUi/NvGeY5WBN2yp7VQBaCGa8+k1o/Tp1cspHtFmlm0nnASPRVJsAJJeAp/80oCyECHJK3HJNzgrI2e67MzuZSSBKktFQh7uj/3c7VGiWK98L0Eh43JyRgak+BbCvqqqvo2XcWrp0vYz1C5mY8rQR2nfvmDzBol3xfvUt4LugF68sNTD/QksGwXAncmypxIDaHAAfmoZDGFTCBO8A7aCInjoFs/qFktbVSis52nJ1XO1VQ8kKepug33upCrq3Do6Ogk/iAUyRag6xWxUvyLdtE3BBvHba7VJzkMX7qN7jluEMUR2rclshsgn8ZE3K7yH2RAkt0yGrKgwYbXGQ6Et56KofOIAyWmm1NzsMJU3oJvTfwoPBBkgN5WMu8RPx21EJDh2ycLf1YxrgChA396RQVjvWqBeNlo5poz9+N+uVmfhesFIWaek9hZ6ysTyycGd7Fx61vd+sjYaTqq0gjiujpSw7qERb/ZpAQ55XdUStPU/JVJ3Aa+HN/tzCaPqzSLxGqEsIpelvCAbPhjBPPc0jgZ6GLV4onZsMqE9H86PR7nni/jZmjvjT2lYmd7gMuMVfV30e1MTpffvv3sfNzh8hEnGTpNhtbFzFrgyMG9cHAxzab+3El58+Ub54iDR/RyWyBcX69eYF8SNtQXHb1XccIcfyqvqKE547kbaNtc6/T8LPGa2W8TfvfGX/KCNZxt9K3gYZFqxicR1aL9OTu8jhAYeRKoEimTOswq0SiyT3r0PxDdyNDrfOfK0U8fI3ghfEp75Ho4l6xG9Y26NAEQY5B+BIgkiArbrkE PXrqGv8I 5ax7oNTggL6J05+djX2mAqpcEGoD9cz2en5sTXcLtq19r6BXmyg90uA+0RVl6FID5i/6zH9AosNNFeQIc2MQwgeYxSEI69oE95VHNFEHU8dkv1cSg9Qx7jk+glZmUrX7FnPkvz0tSR1bDsxFc8QI6Y4FR3JVsMnhHnavFadSYvi05Xe3jUMsCJzmK756uNlc49bTdvACYm9jUtmAi3ROPmhRKzEii63ZEko5pmZmVkbi9mscFxweGpaHpPSvP3WCKvcfFe84+ZCHM74tInbN6IfE4HL8XCpBs9ig4b2Ncxt1/H6lMVT2t07RZGgr9ebkLMpB6mOP2aXL+TYjDZpZOcwhisiDh105Db341Xd0RyBb4R6ebq6pUJxhT1ePQATJ1rnOx+wsJBse6Ewylu41iCEuGHW+Vlbqum3nGRf4+soVyRi8WHFTN4hTMZRzPit6IF7qGs4HPfD4astXB4yiY0/OC6w== 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: Introduce ma_nonleaf_data_end{_nocheck}() to get the data end of non-leaf nodes without knowing the maximum value of nodes, so that any ascending can be avoided even if the maximum value of nodes is not known. The principle is that we introduce MAPLE_ENODE to mark an ENODE, which cannot be used by metadata, so we can distinguish whether it is ENODE or metadata. The nocheck version is to avoid lockdep complaining in some scenarios where no locks are held. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 68 insertions(+), 2 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a3d602cfd030..98e4fdf6f4b9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -310,12 +310,19 @@ static inline void mte_set_node_dead(struct maple_enode *mn) #define MAPLE_ENODE_TYPE_SHIFT 0x03 /* Bit 2 means a NULL somewhere below */ #define MAPLE_ENODE_NULL 0x04 +/* Bit 7 means this is an ENODE, instead of metadata */ +#define MAPLE_ENODE 0x80 + +static inline bool slot_is_mte(unsigned long slot) +{ + return slot & MAPLE_ENODE; +} static inline struct maple_enode *mt_mk_node(const struct maple_node *node, enum maple_type type) { - return (void *)((unsigned long)node | - (type << MAPLE_ENODE_TYPE_SHIFT) | MAPLE_ENODE_NULL); + return (void *)((unsigned long)node | (type << MAPLE_ENODE_TYPE_SHIFT) | + MAPLE_ENODE_NULL | MAPLE_ENODE); } static inline void *mte_mk_root(const struct maple_enode *node) @@ -1411,6 +1418,65 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) return NULL; } +/* + * ma_nonleaf_data_end() - Find the end of the data in a non-leaf node. + * @mt: The maple tree + * @node: The maple node + * @type: The maple node type + * + * Uses metadata to find the end of the data when possible without knowing the + * node maximum. + * + * Return: The zero indexed last slot with child. + */ +static inline unsigned char ma_nonleaf_data_end(struct maple_tree *mt, + struct maple_node *node, + enum maple_type type) +{ + void __rcu **slots; + unsigned long slot; + + slots = ma_slots(node, type); + slot = (unsigned long)mt_slot(mt, slots, mt_pivots[type]); + if (unlikely(slot_is_mte(slot))) + return mt_pivots[type]; + + return ma_meta_end(node, type); +} + +/* + * ma_nonleaf_data_end_nocheck() - Find the end of the data in a non-leaf node. + * @node: The maple node + * @type: The maple node type + * + * Uses metadata to find the end of the data when possible without knowing the + * node maximum. This is the version of ma_nonleaf_data_end() that does not + * check for lock held. This particular version is designed to avoid lockdep + * complaining in some scenarios. + * + * Return: The zero indexed last slot with child. + */ +static inline unsigned char ma_nonleaf_data_end_nocheck(struct maple_node *node, + enum maple_type type) +{ + void __rcu **slots; + unsigned long slot; + + slots = ma_slots(node, type); + slot = (unsigned long)rcu_dereference_raw(slots[mt_pivots[type]]); + if (unlikely(slot_is_mte(slot))) + return mt_pivots[type]; + + return ma_meta_end(node, type); +} + +/* See ma_nonleaf_data_end() */ +static inline unsigned char mte_nonleaf_data_end(struct maple_tree *mt, + struct maple_enode *enode) +{ + return ma_nonleaf_data_end(mt, mte_to_node(enode), mte_node_type(enode)); +} + /* * ma_data_end() - Find the end of the data in a node. * @node: The maple node -- 2.20.1