From patchwork Wed Jul 26 08:09:06 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327564 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 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 From patchwork Wed Jul 26 08:09:07 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327565 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 478ACC001DE for ; Wed, 26 Jul 2023 08:10:05 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DE4E26B0075; Wed, 26 Jul 2023 04:10:04 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id D6D8B6B0078; Wed, 26 Jul 2023 04:10:04 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id BE7806B007B; Wed, 26 Jul 2023 04:10:04 -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 AE59F6B0075 for ; Wed, 26 Jul 2023 04:10:04 -0400 (EDT) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 75FC412019C for ; Wed, 26 Jul 2023 08:10:04 +0000 (UTC) X-FDA: 81053039928.10.F0B12BB Received: from mail-ot1-f49.google.com (mail-ot1-f49.google.com [209.85.210.49]) by imf09.hostedemail.com (Postfix) with ESMTP id 63120140015 for ; Wed, 26 Jul 2023 08:10:02 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="RXB/luIX"; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.49 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359002; a=rsa-sha256; cv=none; b=PuKwzPZYi1NrYHD0OxwY2KtB914x+FHvnLPADq8X2TEx/hNVj/zo3pxhVrC0c5/VIVIB0p /LVIwcZcULX8jB79BhtJ9g8XfM2cQgd+rPFN15maIy7BT2bdEbRfKKApRGX92W200Kt+a0 K5FolUnexjtliMNU1fxUFasVc+ahAog= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="RXB/luIX"; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.49 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1690359002; 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=CBWhUMSjOCubXY+PC9p9DMz2fuhl5l7G2DCnpXKXi44=; b=IH1lNnLiQZ7HhkTSxmSYFjpsMXYHuVkKzOBmt0CJuF6gWCF6bPFF3kBqZ6664B2yrTdfpB hwvnuwuwv3eBVxPQ+X3YqBM7FIG3v7sM7CZKK5hIkIsjBkinb9aTHKRwmH8f7qsC/B8daJ oawLQZzSU66qQe4xDoX1He4AmhtlJAw= Received: by mail-ot1-f49.google.com with SMTP id 46e09a7af769-6bb2ce4f9f8so2518774a34.3 for ; Wed, 26 Jul 2023 01:10:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359001; x=1690963801; 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=CBWhUMSjOCubXY+PC9p9DMz2fuhl5l7G2DCnpXKXi44=; b=RXB/luIXuwGwXY6rqH5frdTWpd6w9LTeUKn410+nFpUsNaJ23LLavNegSawCjRQMgP olOEFVPrbE0jXarH32neIg973IiVObAB37RV1Je7V6W6onAegs08yBYLMxWW4j27U03B hRTru99Vp9e2P5P7I1yZCu3hCHl6eDVSN3p1/mQN5OYlpRyyeZZmDVUBbwGJZaY20H4v +Q7yDQfwWSqQdd6nsa9TBmh2ADavZejwsPqQ3zGHYBIy3WOGxQ8Wc0Mt+U6dEDUIIa22 6tz1eEu1O31YEPOltcFul+d3p84JJlOgzZQar6fOQqG8Qibwy5TwOeiRi3r4Mzrf/Aam nPTQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359001; x=1690963801; 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=CBWhUMSjOCubXY+PC9p9DMz2fuhl5l7G2DCnpXKXi44=; b=KXjZZV86/cnOSYpk6EWxzrIaulckieWmZpOjwWnvLdXoy3L+LXLHyPAlXTMlF3d3tT nRxaI2kvuYcV2hgBmVfFYNmaCz8pA8ic8CMDOSc759FStz6w28o81uNGIGlNbitkEfUG v6yrG07soAoiiXMslxJAhpguqCoSUm6G+stD2lmdkGPPUWSKNy8921V7MXS8ilFTMFuv WXV4K0U7zoNU49aW9ZQn8Ddjjivke0Spht8OsnFWY6fAkOky9syMv8umM022spOn7rn3 RNwXLuf8K2/eqSzqKsyTPw6RlbTGhERDUnn4TK+kFmyueHKSympPnYR5ahyjRKmwOM0w JTpw== X-Gm-Message-State: ABy/qLbt6vBfiv9W6lHgeTzMFlp+pWmfbqxED9v6IIFhzokXXQiyLOuE yfkpSvK2wupPOpvOcju2hUG9Zw== X-Google-Smtp-Source: APBJJlHPh1Z40rOPA8hPV6aBOaHB64sfPxEqqnj6neuzGgAVDkJcfp/eL+6OtW5OBvbdU9FuJRRJcQ== X-Received: by 2002:a05:6830:1e39:b0:6b9:ae94:c664 with SMTP id t25-20020a0568301e3900b006b9ae94c664mr1651229otr.13.1690359001292; Wed, 26 Jul 2023 01:10:01 -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.55 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:00 -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 02/11] maple_tree: Validate MAPLE_ENODE and ma_nonleaf_data_end() Date: Wed, 26 Jul 2023 16:09:07 +0800 Message-Id: <20230726080916.17454-3-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 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 63120140015 X-Stat-Signature: p8heikypyiab1uxcn4gwjqd94nj6wyrk X-Rspam-User: X-HE-Tag: 1690359002-26883 X-HE-Meta: U2FsdGVkX19ZlZ5Cj4XdWiF3r4tJBOTdjPzwmyx4B4AzPmQaiJT2WCTJ5DwSA9IjYiKj/kNTp6QzWtpYHoj9xdNaalM1PAYkNyf9H044MDp8ySHaOheGoNdlIeZfvmCB+1egf41KO+SkvCc86SzIlNmB1gRx8RyGaOoUUpGoS32Q4I0eVyVI9kV+cmk1pcjmkwQArT2TLbsq1FMxUs3HIjyVkGU9AUo5nPkbyo87E4HOfNOBWa5pSYeIsZdlo0WX/nhHyeRa+oUVseRWi37WHxNhbnX3+RHc6blxRTH3M3tdb3KA15wkj01bGQZoUu3LLpb17g7hTdT6q/wLKsQFSLEdsmta6oJCFYq51BwPHDKu096RS5zMJUSKm9/AYS7dMCanHlaghqIdfHU3BXx5iFxgOEj94fH24JkDYJk/7fgbey/7mAHFcG81mVTJEd7n4MSI+53g2yZndySjm5d4r1gnoTj2YkIFJx1pepFTcfKUcIZzKl6NrJ4pmSTvTHTJ/MWTfxqIQ6K9l/MlZA+R9EQyIifjScjpyBge/PtejTDt6EbCOAaP7rzZhbp0CJ8pvdt3Qk1oPw+vxR3gOUdxJ74Eyn2XvfIlbnktNJM+xfXOVfv3ObUd+SaQ4eUD9tWBq7u0eCB8fp3xeQR/B/MRx5POhadkDTGAqqCvIvDvgbfG8QprusabcaWIFoRUqXkOByB8bD28DBUbaJq39N0I+ecQG6I0vKJRUxZZxWbdHNcUWG5fvbT8isOiF/MiaukB9gsaAlRmmNoaZwgiHgav6X3X/WsdfLj+Qe+/STeJhAIKz8XHT5NsV7IPE31/5Vkn6TOckTWM9TEp4/f8t76Gv9/MvNv0ZPCAycAU3atnbCrRa5fOv+tkcR2dXdWOGgP8vRXB1J4XtnoY/6DH8HMMYm1fI3dsMCrVT57pTC+v27qXUpZQ3dV90kT7O3DqdK6S+WY9m1IdtCPjvoovY00 sgEE6NU8 zA/+5dN+BF/BPz9NYYo3Fd79J3q3PZOHLWv+D7KGAXavEQ7lcY0fgMGPRTivyhiUk0DPTMK+GxHEo+TFJ9bY79IdElewGYqiCLZqa3OcosqrjfB3Pbyj+sRpD7XA6u4aNo9tzY44yXHzPjK9p0cIVPNr1TKtGdoIU9YIsBESFBGlIk752ZehO9xTyJOOKUqjm66q1uF5iqXySppF2HD+guAekSFaKSMOhrY3RDzwoiWRLFYcs6VUxZNJdCCzMh9pBsPJMcpaM7gxXcHu6XForFZQIZFChT0djrw242p8Jrr9F6scSehMLXFVzn8rH0zDry6Dnwr2DbU7kTpuvnoVXHTyLANaor9WqxI0DitLOwKOD3CU56NjoyzMFojLZBSE/CkzOfgEU0k9iS6lIqy5NSz/vlcgnQsyBh6igsCqosvXdQMIBdh5kETuwZwIIe3E5C7npzE9GA1Q9RdgLuwy1gGhZGg== 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: Updated mt_validate() to validate MAPLE_ENODE and ma_nonleaf_data_end(). Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 98e4fdf6f4b9..e0e9a87bdb43 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7130,6 +7130,11 @@ static void mas_validate_child_slot(struct ma_state *mas) MT_BUG_ON(mas->tree, 1); } + if (!slot_is_mte((unsigned long)child)) { + pr_err("Slot is not mte %p[%u]\n", mas_mn(mas), i); + MT_BUG_ON(mas->tree, 1); + } + if (mte_parent_slot(child) != i) { pr_err("Slot error at %p[%u]: child %p has pslot %u\n", mas_mn(mas), i, mte_to_node(child), @@ -7200,6 +7205,13 @@ static void mas_validate_limits(struct ma_state *mas) MT_BUG_ON(mas->tree, 1); } + if (!mte_is_leaf(mas->node) && + mas_data_end(mas) != mte_nonleaf_data_end(mas->tree, mas->node)) { + pr_err("node:%p mas_data_end() != mte_nonleaf_data_end()\n", + mas_mn(mas)); + MT_BUG_ON(mas->tree, 1); + } + for (i += 1; i < mt_slots[type]; i++) { void *entry = mas_slot(mas, slots, i); From patchwork Wed Jul 26 08:09:08 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327566 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 ADD93C001DC for ; Wed, 26 Jul 2023 08:10:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4E4496B0078; Wed, 26 Jul 2023 04:10:10 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 46D886B007B; Wed, 26 Jul 2023 04:10:10 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 30ECE6B007D; Wed, 26 Jul 2023 04:10:10 -0400 (EDT) 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 1FBCA6B0078 for ; Wed, 26 Jul 2023 04:10:10 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id E784A1C8D4D for ; Wed, 26 Jul 2023 08:10:09 +0000 (UTC) X-FDA: 81053040138.23.FF52374 Received: from mail-oo1-f42.google.com (mail-oo1-f42.google.com [209.85.161.42]) by imf08.hostedemail.com (Postfix) with ESMTP id 1BF75160008 for ; Wed, 26 Jul 2023 08:10:07 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=kOcNz33W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.42 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=1690359008; 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=qZrshQXwnAab1vq3lU/ajvCxU9+VU+QRXf7AvvzKBtQ=; b=RLkHHb7s7/V2eSzAQepnsv0tV8ZsmzkHhrZsuCgfXvG/NlTTJomJNqUwS9R5b+aJOEIOIb 5F7DKAS4lWMar1JLGMcieexUe21w4HMyQklbGZy5z95iZS4wDOJvSWHfhTr/mO+RWTLpr3 4Moj8lmy1lsK7tBdbkQbvZHAHA7Q+s4= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=kOcNz33W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.42 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359008; a=rsa-sha256; cv=none; b=5EoyNKr8nUxx/lfPkNxCNA15put25opveObateDtdze29lkM/5lZEJJ71Kg6ia0Pjo6BH7 ouP31rmmR7ClQIg0hPP2/0pVA1H6uEMVMUpfi7xmJ7gCIsMWYJwVM9wR6Vp8b7vXBN05W6 oE8SJw03oRxF/5lGjmu2XNj8ZZVnxS0= Received: by mail-oo1-f42.google.com with SMTP id 006d021491bc7-565f2567422so3860172eaf.2 for ; Wed, 26 Jul 2023 01:10:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359007; x=1690963807; 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=qZrshQXwnAab1vq3lU/ajvCxU9+VU+QRXf7AvvzKBtQ=; b=kOcNz33W7J/uTghRxfKlgF2t8o8j/nb23QuZ5yZKbuyUJEAo08ew/cyJIJar+ZMNgI tgX5YgFX3m0skq8DC+gLxzllvMuDg70EjDBiGJDh1Mpz7+05ViTUmcEq2WUbohgItCxV YzHy4oRBemHEGHrvA5A3alCBAqXAz65/Txxwwd4nWao7MA8/0+hF3gmQ7txN/UghIKky 8G26vNuHfNxrsQXaTfctaOFa7a6rjySrzwk2OVDEFJEhTEGkky1CjAN/cm37djIrSV0x 6o0qqSUTea0zqTSaIEA6OD8+/F51B8lA3bJ3ibFJVMxXHbff0W8kAffd204aDfDk8A1R +z4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359007; x=1690963807; 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=qZrshQXwnAab1vq3lU/ajvCxU9+VU+QRXf7AvvzKBtQ=; b=apl6mPYQ2Ml8V1ESdBUYfm7vDKaavMA9xnAq6zQPA0E7aK2yQyw5CM1fhAby3lj22F PUnGsqUM+mtUZaRmBFWZCdSl+O02G/8u0ihObEHcXp3e/Wm/DrM1PT2k7JBaj8uVa0MK T/eiIUR4EQ62+Rni7zmkb3tV8CMfL6zBM9GzTu9Nr3Xewavy3XnQ9YZMZ+SRDODXLFQu yVLx3JkPgFeEiZ50i20bHkjEFDi/iJKOfJ+zu+kOShD8BqkS4kSSWYRlkkYWDr17uu9t T1jTf8/B2n65uby9gYk4hY5gJVfG6QVJzof7EHksHZ01LWnQ+8Ah3FQ3YZEU5M69YjvA wJMA== X-Gm-Message-State: ABy/qLYhrQh1Zhx1MhvLw5HSKiWozWu8Le1caBbMGuixpSwStiYaBbSH zCZTJQTxy/sBK2bp3Reh3uhPFg== X-Google-Smtp-Source: APBJJlFLmfT+cuxvJMJSvIXCYHo32FQ7ykqGokpbQY3Wi2ttJPt4o99SYQCfgC/jOX0M+MMpT8vadQ== X-Received: by 2002:a05:6358:2794:b0:133:b33:3b9a with SMTP id l20-20020a056358279400b001330b333b9amr1284440rwb.3.1690359006957; Wed, 26 Jul 2023 01:10:06 -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.10.01 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:06 -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 03/11] maple_tree: Add some helper functions Date: Wed, 26 Jul 2023 16:09:08 +0800 Message-Id: <20230726080916.17454-4-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 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 1BF75160008 X-Stat-Signature: zfnrg3ch9kmw3bm38sbpo77s8pwkeq7b X-Rspam-User: X-HE-Tag: 1690359007-337126 X-HE-Meta: U2FsdGVkX18OViYDDCRxxqZAsKNkYV4w3bcWgHm2v0K/KeOw1caewqQKD0I3zuqXTz9YZePTUdrXWko7PxhQyBbF4kr5kYb/oaysT/A6t1mHIjKpA37/lrgVD4rAjxXlQeryAvYRwk7cqCkvLNVOYR2C1oEt+xbFf6VrtwdPmMM4MbB2Xvd7KdnJ2akGno2RWgC5kJcXXV6JH4bz7woYuEMNC4L1lC+bQ30xKZPc5N5EGBQ+wfGFwmmrV4LOy1MsdbtthD1jyAijp+8htp+WzZEHZ+q3Og0pDNeEHya2BMF1d7cIvQ020o4cCH2XwpFlYUFHxYcpGgFB+0UcexyASq7EZVKy+YVsBV2wOJSVeAODdKsOBSD43b4+CwRFGqJC66udOk1jMaI9lAAG3TUecmPKN9ilTtdp9VuujWqG6plcjWXzkR7xrPzEalyIGhuSw+Bm8PdxAmJEr5hAv5bmdp0e9zGPLgaZqiHnBKGJeDz0EZ8hZhsB8JjBLPf3NNGiF60v+Ho78RbNK2UaWXR0VF10FxtjeDr2CbBizFaWm5x+b7/xy9QJGW3dcyKLn5cqdHx8Ce1iQdd+TnZzPrZ8d4k3q15qdACv5Gk85zGBj0Ud+ih2DGU6mvUrxjzF0f27FauWT/Ai/JpF9iv0JuRWdIHVaXhA7T+bKKTPO/EpNmSy/9hht3bUYuxO7sInS7qVr+olS94rIbhEQSV3Td9sNwnVRV/9d9spkpQiXp22ZjM4FI485BDocZyFQ6oHSJcq2B0nqb2YuIvO5rQDozv0VyByX2mHI1lsjMs/sbz0XYZprldN6hrEh3aduj9jClFgeksV/W5aXH51vPDv7/ki0vkxJuKyuVKQvE704GAbVARJGufSgHiiO/W1L/luJnphHLIrlrY/b7IWY34lwvYB2zcxLjjXQDuk0XpGYBzpcxzz0XTw6GWpEzChr7foeoV0o+K7zC4M5hbqds7Qvpq uMy5B8iV g8xot4zI9Z4jATD5UhsJ82QtQTMu7AWIONByWiub1k1MNFQh2pBRYyzYmG+oFhU8MJqgGiPLx7LhSOaIcMKBQ6Zw2CvzS7Kc9FAvRPo0EDjwvihxhXQ6i/Etp0Ea7H+hrsPNRo3QvTDmamBN6EwAiX6aYwVN3TmIRz1nyZWPTmKaz5NcBPNj1/nloyQmV65QSGTgU86ENuA7z+ZXwicYHuO8VI43RX1uqSqJBXMAeq42B5KMlIi2rkU1Ea5fRZZc7pjxqtVw4zltFCkfwNv+ly3Am5WEhj8Y9zrNJ76mAtMPfLcCL0dxUJ3UYcKKvCRHwapEhOwtguoRBXLecfXtSrRCehXH5yqBHPZCmEYZuUlpWqTWHreiUXc0sqQ3FwiPNiMHFkT1VIWBlrX1AA5vVAbYImlx80u+ovULxJf370Gjf+mRBnhgpzatb524bTXsarWFqSMczo0gtmu/aoMfYFRbMxg== 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: Add some helper functions so that their parameters are maple node instead of maple enode, these functions will be used later. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 71 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 55 insertions(+), 16 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e0e9a87bdb43..da3a2fb405c0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -164,6 +164,11 @@ static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes) return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes); } +static inline void mt_free_one(struct maple_node *node) +{ + kmem_cache_free(maple_node_cache, node); +} + static inline void mt_free_bulk(size_t size, void __rcu **nodes) { kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes); @@ -432,18 +437,18 @@ static inline unsigned long mte_parent_slot_mask(unsigned long parent) } /* - * mas_parent_type() - Return the maple_type of the parent from the stored - * parent type. - * @mas: The maple state - * @enode: The maple_enode to extract the parent's enum + * ma_parent_type() - Return the maple_type of the parent from the stored parent + * type. + * @mt: The maple tree + * @node: The maple_node to extract the parent's enum * Return: The node->parent maple_type */ static inline -enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) +enum maple_type ma_parent_type(struct maple_tree *mt, struct maple_node *node) { unsigned long p_type; - p_type = (unsigned long)mte_to_node(enode)->parent; + p_type = (unsigned long)node->parent; if (WARN_ON(p_type & MAPLE_PARENT_ROOT)) return 0; @@ -451,7 +456,7 @@ enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) p_type &= ~mte_parent_slot_mask(p_type); switch (p_type) { case MAPLE_PARENT_RANGE64: /* or MAPLE_PARENT_ARANGE64 */ - if (mt_is_alloc(mas->tree)) + if (mt_is_alloc(mt)) return maple_arange_64; return maple_range_64; } @@ -459,6 +464,19 @@ enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) return 0; } +/* + * mas_parent_type() - Return the maple_type of the parent from the stored + * parent type. + * @mas: The maple state + * @enode: The maple_enode to extract the parent's enum + * Return: The node->parent maple_type + */ +static inline +enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) +{ + return ma_parent_type(mas->tree, mte_to_node(enode)); +} + /* * mas_set_parent() - Set the parent node and encode the slot * @enode: The encoded maple node. @@ -499,14 +517,14 @@ void mas_set_parent(struct ma_state *mas, struct maple_enode *enode, } /* - * mte_parent_slot() - get the parent slot of @enode. - * @enode: The encoded maple node. + * ma_parent_slot() - get the parent slot of @node. + * @node: The maple node. * - * Return: The slot in the parent node where @enode resides. + * Return: The slot in the parent node where @node resides. */ -static inline unsigned int mte_parent_slot(const struct maple_enode *enode) +static inline unsigned int ma_parent_slot(const struct maple_node *node) { - unsigned long val = (unsigned long)mte_to_node(enode)->parent; + unsigned long val = (unsigned long)node->parent; if (val & MA_ROOT_PARENT) return 0; @@ -519,15 +537,36 @@ static inline unsigned int mte_parent_slot(const struct maple_enode *enode) } /* - * mte_parent() - Get the parent of @node. - * @node: The encoded maple node. + * mte_parent_slot() - get the parent slot of @enode. + * @enode: The encoded maple node. + * + * Return: The slot in the parent node where @enode resides. + */ +static inline unsigned int mte_parent_slot(const struct maple_enode *enode) +{ + return ma_parent_slot(mte_to_node(enode)); +} + +/* + * ma_parent() - Get the parent of @node. + * @node: The maple node. + * + * Return: The parent maple node. + */ +static inline struct maple_node *ma_parent(const struct maple_node *node) +{ + return (void *)((unsigned long)(node->parent) & ~MAPLE_NODE_MASK); +} + +/* + * mte_parent() - Get the parent of @enode. + * @enode: The encoded maple node. * * Return: The parent maple node. */ static inline struct maple_node *mte_parent(const struct maple_enode *enode) { - return (void *)((unsigned long) - (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK); + return ma_parent(mte_to_node(enode)); } /* From patchwork Wed Jul 26 08:09:09 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327567 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 B6ED3C001DE for ; Wed, 26 Jul 2023 08:10:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 448ED6B0071; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3D0C36B007B; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 24AF28D0001; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) 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 127316B0071 for ; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id D7C9CC0D9A for ; Wed, 26 Jul 2023 08:10:15 +0000 (UTC) X-FDA: 81053040390.03.FF6EB31 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) by imf20.hostedemail.com (Postfix) with ESMTP id EB1071C0011 for ; Wed, 26 Jul 2023 08:10:13 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AxvO2W8W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 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=1690359014; 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=Q9dsUg7Mi/WzTn56TpcYztC53dUlO7YtHGzVyJj2ahA=; b=Zys5pMWcxWmSRKAep0PfhcjRpqp0m6KKoX97KX7HoXGPLxIcxLswZBACUJfEa7l0FLkEiK RQP13uasfy3ziTRbfNlbQ+3hQDvNq848ZIpuTDyfn8FSWBct91CDFA0vftXCqQVfShhXVf dfwZ7p7HSfMDZ5Vm39Zy1ahfOtFo3rg= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AxvO2W8W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359014; a=rsa-sha256; cv=none; b=ybocZRlqVMntqjP6aztuWrZMJrympRFnIbZacUQIIRutqhmwO9gomaBv292ehQuuiLb9HP V5YgXsSIL4ECAE+JZE4l0bXpTuu1nyXorDxTNPuDny6s57/C7AnzCvyWxgg/b6HoCRNXcy rNTNyWu/LXvAXpwznBDvqYJZWgpP/lY= Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2680182bc21so1745406a91.2 for ; Wed, 26 Jul 2023 01:10:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359013; x=1690963813; 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=Q9dsUg7Mi/WzTn56TpcYztC53dUlO7YtHGzVyJj2ahA=; b=AxvO2W8WmVjCl+8rJI4ixbPJPEirwx12lLH3TIqpROUBNuTlBFTpwIzvimh0rKV5GO jl53Qb/ksDM+V8W/GLFWjp+RoSYw3jS+hUC4AqvaYFObpV+KEgG/doJAkaO3KYxj67D3 hGPB/vbqL0FvtkEDKiSP2uFPrG+vqg6MD9oePIzWQfrkyb9NfNm5I1GxlLLwR2jNR5xw PYqQU1CDGlNTqFeTUH9EsCbpxb5Yp/asxXO7fyvKXIG2Sip5Qaq5nthqVKfov9s0UZnU nig8GQjrdik29VC+VZghqXGcKhCir4shFIkMGLbvr/P68Zz7mLMG8OhUaIsqqlWUdBPz BlrQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359013; x=1690963813; 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=Q9dsUg7Mi/WzTn56TpcYztC53dUlO7YtHGzVyJj2ahA=; b=KehKSlYo4xh07CzVORXwEMro6kXwEw2oJ57nDFatcIpNjrGSevgl3UXpqjngndvFa8 O9tvwDFSk6K+omABzsDP3/eKaukVTIPDKEptZN604e+3jubkMNX2I/gs1keGWK+OIOaE lJoCUhxkBvrepxGqqSvlVE0HHO5YCkYosikkBvap6tSXzu2LazaOnAk5bOORn3Mbovl/ 7hJL0DnSo45RBQkaEdvI7HSTo/KHbmUUDPiB+zqMB5W/VwN1yk9DFltaGL733af0sLtO wM1OsPN4sBEowTO02kc0zVWww8e82GZAnZCxbMDoJ3FpE/qfOQ+VDlO5bQ3WZJ9MNR7z Rpbw== X-Gm-Message-State: ABy/qLb2AOTfqfJPT7ILSwNSOmr1BgYU+fgVy547BifD7GBt5OKfOQme Hmsvu9bQOw98caSTY0ibTFpNXw== X-Google-Smtp-Source: APBJJlGkN+ndt02hEH/zEFcGhY2t+fQ0s2aGudRsTkYsXiwqyld2+wz2kPDM4ySgqmSJx8lp4VguSA== X-Received: by 2002:a17:90b:1498:b0:268:f56:a2d6 with SMTP id js24-20020a17090b149800b002680f56a2d6mr947545pjb.22.1690359012722; Wed, 26 Jul 2023 01:10:12 -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.10.07 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:12 -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 04/11] maple_tree: Introduce interfaces __mt_dup() and mt_dup() Date: Wed, 26 Jul 2023 16:09:09 +0800 Message-Id: <20230726080916.17454-5-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 X-Rspam-User: X-Stat-Signature: 6mrfrtxp4smwq6z666f3h5b9mg5b7u5t X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: EB1071C0011 X-HE-Tag: 1690359013-276898 X-HE-Meta: U2FsdGVkX19VYCuuvzX+h9oeeZ72X2gfWBvsmGLwW2B6GcYNxoI8Am/7b5EruyOVG0SwJNaGz1Tev/Z7EV+WoyA0970UXjXL/k9v/b5WEUUxjrDccpOu1zHUAYqKAh3Ju2fjE751Dj/mZwnHxTrb5jsW9P9u9uXZhb2R4xRWjKyJXgm9V/N8yIClgVpJUk09Qd8+eSfgl2lMAAue/ZJLap/J1qCQEKa0XsTiMhti5XTVLC982DJ9U0KO3GUQDhzy4PzhmiOaSji5qFtFFfDsycn2peYatVBiPbgOh5MRvvheh6g/3ZFhEY4ZExttQIfVDqLgtMET45l2r4TChZVZM+em2O0knubgo84nGPJlXZFoUEUJUdStNN7r6w1xa7Rcv4BXpGP+6+HayQtLc9qB1G/tDAzPdQwaHVIHS9BvScTYmNI0Se/6hUgxPKbQT9yLV12hWmxrN16ZiC4CohAriFlx7WXmQ6JCJqFnKNDj1G/hKg8bWk9QtKdFZOai/g4Lrpxm2GRndRUn4yfZUkre+mGwgXqFDdXwm2WLciE3cE+hx3qIigWmrhfTDK/S1njlHOU6Kg2yQzpinb6yYFFpNMABfXaELORoRiwZBLD4q8shNfJxZ2ZufjJvbds+TFXhs3vZV5kwrFj6EFMXov8iFsqjhW45Wyuj022/kPYP8xQUpjJ35TZdhl0/6EMhU/kIMhtiecd58cqZ1LTtJjdMISD4uUysdMovql9m+KdhXZA6lA3oFWBObFUOpzKokpIbhCMXYeWJ6QpXpoyoek6QBDbLBH6ycIS4BUG35v/kSXX6GPVqhTGhUnGlGGbU2iQ1/taxtYu8KI9UOD/HyOFBZLV2QLBBekPZBdMj7hAy5bQbOX7Vn0grPigXKbYqk9taKxZifJA8p9g2MilCF0UDPOrT4BHdyYqsBtjrtynvTb7Kzio66qY9CdiM+ESnmZwNvOnUclXFOAa61PkZIxe TKFOge+H qXyT4U4wQJt26RQch1eRjbwnvho8Ib2Bd8HM01hofKjNhhKiLtSqO8bTYEJKeEHHAPWSMAaORIQVXpTFLtN3M1yutGZFAJpZ6eLFI5ENV8aTglqQb3HkOOp8ye2D1UDacp0C6ENF4wMW/lCyM/xKpPMsYSZvhXpZwqzHADRPpAH4yknW/ekBcPoj0oUF1EkdeuF9V5/pftUTS1HixX/jqkQderXdNA+RSvBQpHv9/k1GSVroVlAMguiaz0uMzQClNzH4QbqhLsDXIaiJjKa4oBUjLOamLHiiwGI4YJXhoRGJ7ltqmzR/Jd1s9bzFnbaoVKbIvaQWQn7bU+0ldNdsBb5GoiSJ7XJ6abjgvhP9zdWmLw483SWbeCfW57UNIYF8UpOqwILwzVsR0dzS0Cm6qg84JLEut0HCVoe5+bJ7HfQYckmHphJPygku+2jSAJgrRGc0A99eiiWpmQ4C1W/Cxi2LyCg== 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 interfaces __mt_dup() and mt_dup(), which are used to duplicate a maple tree. Compared with traversing the source tree and reinserting entry by entry in the new tree, it has better performance. The difference between __mt_dup() and mt_dup() is that mt_dup() holds an internal lock. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 211 +++++++++++++++++++++++++++++++++++++ 2 files changed, 214 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index c962af188681..229fe78e4c89 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -327,6 +327,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp); void *mtree_erase(struct maple_tree *mt, unsigned long index); +int mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); + void mtree_destroy(struct maple_tree *mt); void __mt_destroy(struct maple_tree *mt); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index da3a2fb405c0..efac6761ae37 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6595,6 +6595,217 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mt_dup_free() - Free the nodes of a incomplete maple tree. + * @mt: The incomplete maple tree + * @node: Free nodes from @node + * + * This function frees all nodes starting from @node in the reverse order of + * mt_dup_build(). At this point we don't need to hold the source tree lock. + */ +static void mt_dup_free(struct maple_tree *mt, struct maple_node *node) +{ + void **slots; + unsigned char offset; + struct maple_enode *enode; + enum maple_type type; + unsigned char count = 0, i; + +try_ascend: + if (ma_is_root(node)) { + mt_free_one(node); + return; + } + + offset = ma_parent_slot(node); + type = ma_parent_type(mt, node); + node = ma_parent(node); + if (!offset) + goto free; + + offset--; + +descend: + slots = (void **)ma_slots(node, type); + enode = slots[offset]; + if (mte_is_leaf(enode)) + goto free; + + type = mte_node_type(enode); + node = mte_to_node(enode); + offset = ma_nonleaf_data_end_nocheck(node, type); + goto descend; + +free: + slots = (void **)ma_slots(node, type); + count = ma_nonleaf_data_end_nocheck(node, type) + 1; + for (i = 0; i < count; i++) + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; + + /* Cast to __rcu to avoid sparse checker complaining. */ + mt_free_bulk(count, (void __rcu **)slots); + goto try_ascend; +} + +/* + * mt_dup_build() - Build a new maple tree from a source tree + * @mt: The source maple tree to copy from + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * @to_free: Free nodes starting from @to_free if the build fails + * + * This function builds a new tree in DFS preorder. If it fails due to memory + * allocation, @to_free will store the last failed node to free the incomplete + * tree. Use mt_dup_free() to free nodes. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated. + */ +static inline int mt_dup_build(struct maple_tree *mt, struct maple_tree *new, + gfp_t gfp, struct maple_node **to_free) +{ + struct maple_enode *enode; + struct maple_node *new_node, *new_parent = NULL, *node; + enum maple_type type; + void __rcu **slots; + void **new_slots; + unsigned char count, request, i, offset; + unsigned long *set_parent; + unsigned long new_root; + + mt_init_flags(new, mt->ma_flags); + enode = mt_root_locked(mt); + if (unlikely(!xa_is_node(enode))) { + rcu_assign_pointer(new->ma_root, enode); + return 0; + } + + new_node = mt_alloc_one(gfp); + if (!new_node) + return -ENOMEM; + + new_root = (unsigned long)new_node; + new_root |= (unsigned long)enode & MAPLE_NODE_MASK; + +copy_node: + node = mte_to_node(enode); + type = mte_node_type(enode); + memcpy(new_node, node, sizeof(struct maple_node)); + + set_parent = (unsigned long *)&(new_node->parent); + *set_parent &= MAPLE_NODE_MASK; + *set_parent |= (unsigned long)new_parent; + if (ma_is_leaf(type)) + goto ascend; + + new_slots = (void **)ma_slots(new_node, type); + slots = ma_slots(node, type); + request = ma_nonleaf_data_end(mt, node, type) + 1; + count = mt_alloc_bulk(gfp, request, new_slots); + if (!count) { + *to_free = new_node; + return -ENOMEM; + } + + for (i = 0; i < count; i++) + ((unsigned long *)new_slots)[i] |= + ((unsigned long)mt_slot_locked(mt, slots, i) & + MAPLE_NODE_MASK); + offset = 0; + +descend: + new_parent = new_node; + enode = mt_slot_locked(mt, slots, offset); + new_node = mte_to_node(new_slots[offset]); + goto copy_node; + +ascend: + if (ma_is_root(node)) { + new_node = mte_to_node((void *)new_root); + new_node->parent = ma_parent_ptr((unsigned long)new | + MA_ROOT_PARENT); + rcu_assign_pointer(new->ma_root, (void *)new_root); + return 0; + } + + offset = ma_parent_slot(node); + type = ma_parent_type(mt, node); + node = ma_parent(node); + new_node = ma_parent(new_node); + if (offset < ma_nonleaf_data_end(mt, node, type)) { + offset++; + new_slots = (void **)ma_slots(new_node, type); + slots = ma_slots(node, type); + goto descend; + } + + goto ascend; +} + +/** + * __mt_dup(): Duplicate a maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree using a faster method than traversing + * the source tree and inserting entries into the new tree one by one. The user + * needs to lock the source tree manually. Before calling this function, @new + * must be an empty tree or an uninitialized tree. If @mt uses an external lock, + * we may also need to manually set @new's external lock using + * mt_set_external_lock(). + * + * Return: 0 on success, -ENOMEM if memory could not be allocated. + */ +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret; + struct maple_node *to_free = NULL; + + ret = mt_dup_build(mt, new, gfp, &to_free); + + if (unlikely(ret == -ENOMEM)) { + if (to_free) + mt_dup_free(new, to_free); + } + + return ret; +} +EXPORT_SYMBOL(__mt_dup); + +/** + * mt_dup(): Duplicate a maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree using a faster method than traversing + * the source tree and inserting entries into the new tree one by one. The + * function will lock the source tree with an internal lock, and the user does + * not need to manually handle the lock. Before calling this function, @new must + * be an empty tree or an uninitialized tree. If @mt uses an external lock, we + * may also need to manually set @new's external lock using + * mt_set_external_lock(). + * + * Return: 0 on success, -ENOMEM if memory could not be allocated. + */ +int mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret; + struct maple_node *to_free = NULL; + + mtree_lock(mt); + ret = mt_dup_build(mt, new, gfp, &to_free); + mtree_unlock(mt); + + if (unlikely(ret == -ENOMEM)) { + if (to_free) + mt_dup_free(new, to_free); + } + + return ret; +} +EXPORT_SYMBOL(mt_dup); + /** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree From patchwork Wed Jul 26 08:09:10 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327568 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 0C22EC001DC for ; Wed, 26 Jul 2023 08:10:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 88E876B0074; Wed, 26 Jul 2023 04:10:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 817416B007B; Wed, 26 Jul 2023 04:10:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 66A1E6B007D; Wed, 26 Jul 2023 04:10:21 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 54EA86B0074 for ; Wed, 26 Jul 2023 04:10:21 -0400 (EDT) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 1E1DFC0D9A for ; Wed, 26 Jul 2023 08:10:21 +0000 (UTC) X-FDA: 81053040642.27.D847B6F Received: from mail-il1-f174.google.com (mail-il1-f174.google.com [209.85.166.174]) by imf25.hostedemail.com (Postfix) with ESMTP id 3C1EEA0002 for ; Wed, 26 Jul 2023 08:10:19 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=edqfz4k4; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.166.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359019; a=rsa-sha256; cv=none; b=1qI8iQ75/GORMdluAla9cQaIdqJSAUhH+XNrKhVZGR1hUluUbsmHcABxwqGluFfyaqQjKt SUYv7pYnbSLSBjzo/d67IPsIVpsmkYQgmO3zislC6lchThxEKNm8HB7IA/OD6SsQf3bI6b xN3alY5xWN9PsfLUH+yrIsxn07737Ws= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=edqfz4k4; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.166.174 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1690359019; 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=zLmPRatqLaPjNdFSIOQqmfdfgzRaFIKbs75zNZxQM3k=; b=axklaMtUQv3ty4XgcMMcxrGOzqrqTpTWYr5eqAxhFoEpX+VV0ESzlV6P121+Bq62PGSpWA QUeRv9Y1Kfr1e9T+VDZtLLS9GoRRS1+0GbBDAbn3q+Qmo4ZpUkAxRKodiZeAAosjLvrf92 fmJqh2vrZEimSzpgyRbftZJLMJCZKnk= Received: by mail-il1-f174.google.com with SMTP id e9e14a558f8ab-348c03de0e7so16509295ab.1 for ; Wed, 26 Jul 2023 01:10:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359018; x=1690963818; 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=zLmPRatqLaPjNdFSIOQqmfdfgzRaFIKbs75zNZxQM3k=; b=edqfz4k42nCM4mbt3rgbm433jEQgkgjdf50ULvk8j2xYHjezVeSFt1oZ907tUkLq6H ow/CoVkmA5DqlFbF8xELCu7XeAPlG3bTVmgL6D3d33T+UtZlMVWJMJvrYHZ4nrda3KuW Pp+6+h0GCAVyTF84xW6NaL1Yy0kreE4NvfODNzLeX1FkzSpYfE4EDIGnEfkgGSLFIcf/ JNvbkrZvHx4x5rq0B03sAvUSxcYYjCKmiCcAjvYEtA5Y4uzZBxgt5r99KZvcg2AJ4Ce2 mlpfpAvootB9ZFpXGuoGEyHBwrOZDmHKQMbdKy+9I1mars1V4N4rHoRVXeHhHak5dgDV uiPw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359018; x=1690963818; 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=zLmPRatqLaPjNdFSIOQqmfdfgzRaFIKbs75zNZxQM3k=; b=k/+O1d1ChqvrAbFPbZDJ+NyiWkVCQgIC1Gy+/ezWMBJUTVK96Rkzuid4twni3UQMA9 8O2Ff3eBWwpd6YaRkqgOY/9eaigDPGpIUM2shjxv/FvhEFyO6rB095nsm3Mmh7qZAzfJ LQOkZ+UOSh0HPujg526TVFSA6copP0wgrHg5SA023f47W74HoabQczAo0VILutXDUuQm lsWBhDSgD4CJPIX9zJMtY5fdGXdAXbw2o458C303NKsaQPZNL4S02gTVe8L9LuIy+kOz 0g9vUoOvOWbSwmG/z5hiKrRD+rNiL89G8/paXEij4uxK5ZaipFB0FbZ5XK4kdJUF7N7N 5jpw== X-Gm-Message-State: ABy/qLabk+2CwASK6czl1R/4EMt3Kzot8QCuNqSpTSbB79RemvehFIXX K15BEhXx5T4BjUF52I3Gij0NVQ== X-Google-Smtp-Source: APBJJlGa1sI8Ot6wDuAGAIzbtMGaPwlxOu08ayCD0nVOoODHEZRjd9Ytl9786BZoeyT8Q0+YuiMnMQ== X-Received: by 2002:a05:6e02:92d:b0:348:c57f:b016 with SMTP id o13-20020a056e02092d00b00348c57fb016mr1153348ilt.3.1690359018367; Wed, 26 Jul 2023 01:10:18 -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.10.13 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:18 -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 05/11] maple_tree: Add test for mt_dup() Date: Wed, 26 Jul 2023 16:09:10 +0800 Message-Id: <20230726080916.17454-6-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 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 3C1EEA0002 X-Stat-Signature: icywgkfxa4zarjjhw69im5thzj8mppo6 X-Rspam-User: X-HE-Tag: 1690359019-348473 X-HE-Meta: U2FsdGVkX19kCtx6r9fALkM+SeKkJ1r9EYp9K1b9O4MbdAOT1ZJ60kjKUK+6mTCwJXk8Wf4Cn+vHs18U1vNyM9Zlrcb02S+rU1baBdZ1l9PI6AgFFW17/8v2H841OhyXLriGIjfh7zOeD8Vh/MfSeJVhiEnKP9KeW4MqxQ0DuDlIhapQ6DTG38C5JYTEa3I72VENn19oPOYJxksYMou51i7NmzcixFIB9oeGuWuZB3QkGriXCiFs7FCvExzNyQU/GLNFSLQ+5X6hLjdTrQ+kubohhP+3gyk8sngV4LneT5IGqU1Fo1WNdO180qmfRcWPuZJV8mvJaJINfQ5d3/OGShrB2CXhbWc3pg4jVnSQfbMbO4vzr5hX8hZt2k0p+SYZ9a3ngQ5dSXWemME903X5/PffEssoCTGRhBR3inb7Btt42XCpxZD1E0rjf1ALTqr0xSii03NFWv/n9ax/4z7H7RD9UdGg9fYHm5b0zro+RkJ9x18j6wMBXahNDGPlLV+YgRCEElmvoZ8EnWDQgIi7hz/OWYzk8GKPgIxUskyLsieA6SN131wTIFlZg345ElQDVk+OCDcH9WaW6cmLLSFXBFVvNxvamezs3NrLbJqNI2GS231KGDKTk7zxF2YddEV4Yr97+DQ0hA/gU5dG9wCNYrOlLB+R+uXk415qdBXvjYlBRAp7zl8jgX7gGInEcnRdzlZtO8i3o+zPQSBFL/sH7+x/tbQjSwSGYfX8Y8doDKCM3qn+qwF5Ghnzqunx8ha5Fvx6l3zi6iU655n/Sx4f3iROTeImUxOnO11mTmTyYYn2ka75/Dnz1/kb3rjVgDtTVSRL/3hNBfBdQHlh8z6PS19lPK3Ft8R6Hfx89IO3jsd9I6kvRybsZLy/NantNd5w991WMXsn5S2HxwbQi5liKHX0y42nMfZV4HkL7wyB6tZPAx0c72tuRhApagD2jUU+PXdCUMYe6dOpEXzm3b9 k48IvURG W5j4MaTg4vwdOWBJKdbKcIO+PZwUXh+YoivLv+QO00G6OHTLuOvRwwN5M9nacd7C84kYJCf1ZKfXTNl49EQ1L7EQ8QzOA7mkBQ69v79iQ/JvJBZHvWIIEETNFkK6+DU3m6ysg0/05Ryv/nQ7yDokXgjFP4tfXHqfwDlhpq2IVIYp/K1SZsQY8KD/Axl1xKddRoKplpjzib/9q6m6uxUp9/hlWdlN5Z/1+Wn0sMu6uHPfbdx3rWpcwpjZLiOujgEzqgvKh1alQ1so7lNJcqAMGS+ro0G557KUpqrASyp4w5NNyTUI8UTECPzsMmrkhEYXhSJ/5jDzttGw7jB91+B4ukGDQfq3K39em3pYjGo2w25IpILCNH4kFJiMRVZYaUmGLB3/rpaHxHRhEefkr03geky4yP86bBci3pVi/Z6USZr5G0NvRlOnN2Yu6veb894lXV1HQpKm19k6y5zMc6LUJcbasMw== 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: Add test for mt_dup(). Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 202 +++++++++++++++++++++++++++++++ 1 file changed, 202 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index e5da1cad70ba..3052e899e5df 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,204 @@ static noinline void __init check_locky(struct maple_tree *mt) mt_clear_in_rcu(mt); } +/* + * Compare two nodes and return 0 if they are the same, non-zero otherwise. + */ +static int __init compare_node(struct maple_enode *enode_a, + struct maple_enode *enode_b) +{ + struct maple_node *node_a, *node_b; + struct maple_node a, b; + void **slots_a, **slots_b; /* Do not use the rcu tag. */ + enum maple_type type; + int i; + + if (((unsigned long)enode_a & MAPLE_NODE_MASK) != + ((unsigned long)enode_b & MAPLE_NODE_MASK)) { + pr_err("The lower 8 bits of enode are different.\n"); + return -1; + } + + type = mte_node_type(enode_a); + node_a = mte_to_node(enode_a); + node_b = mte_to_node(enode_b); + a = *node_a; + b = *node_b; + + /* Do not compare addresses. */ + if (ma_is_root(node_a) || ma_is_root(node_b)) { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MA_ROOT_PARENT); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MA_ROOT_PARENT); + } else { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MAPLE_NODE_MASK); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MAPLE_NODE_MASK); + } + + if (a.parent != b.parent) { + pr_err("The lower 8 bits of parents are different. %p %p\n", + a.parent, b.parent); + return -1; + } + + /* + * If it is a leaf node, the slots do not contain the node address, and + * no special processing of slots is required. + */ + if (ma_is_leaf(type)) + goto cmp; + + slots_a = ma_slots(&a, type); + slots_b = ma_slots(&b, type); + + for (i = 0; i < mt_slots[type]; i++) { + if (!slots_a[i] && !slots_b[i]) + break; + + if (!slots_a[i] || !slots_b[i]) { + pr_err("The number of slots is different.\n"); + return -1; + } + + /* Do not compare addresses in slots. */ + ((unsigned long *)slots_a)[i] &= MAPLE_NODE_MASK; + ((unsigned long *)slots_b)[i] &= MAPLE_NODE_MASK; + } + +cmp: + /* + * Compare all contents of two nodes, including parent (except address), + * slots (except address), pivots, gaps and metadata. + */ + return memcmp(&a, &b, sizeof(struct maple_node)); +} + +/* + * Compare two trees and return 0 if they are the same, non-zero otherwise. + */ +static int __init compare_tree(struct maple_tree *mt_a, struct maple_tree *mt_b) +{ + MA_STATE(mas_a, mt_a, 0, 0); + MA_STATE(mas_b, mt_b, 0, 0); + + if (mt_a->ma_flags != mt_b->ma_flags) { + pr_err("The flags of the two trees are different.\n"); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + + if (mas_is_ptr(&mas_a) || mas_is_ptr(&mas_b)) { + if (!(mas_is_ptr(&mas_a) && mas_is_ptr(&mas_b))) { + pr_err("One is MAS_ROOT and the other is not.\n"); + return -1; + } + return 0; + } + + while (!mas_is_none(&mas_a) || !mas_is_none(&mas_b)) { + + if (mas_is_none(&mas_a) || mas_is_none(&mas_b)) { + pr_err("One is MAS_NONE and the other is not.\n"); + return -1; + } + + if (mas_a.min != mas_b.min || + mas_a.max != mas_b.max) { + pr_err("mas->min, mas->max do not match.\n"); + return -1; + } + + if (compare_node(mas_a.node, mas_b.node)) { + pr_err("The contents of nodes %p and %p are different.\n", + mas_a.node, mas_b.node); + mt_dump(mt_a, mt_dump_dec); + mt_dump(mt_b, mt_dump_dec); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + } + + return 0; +} + +static noinline void __init check_mt_dup(struct maple_tree *mt) +{ + DEFINE_MTREE(new); + int i, j, ret, count = 0; + + /* stored in the root pointer*/ + mt_init_flags(&tree, 0); + mtree_store_range(&tree, 0, 0, xa_mk_value(0), GFP_KERNEL); + mt_dup(&tree, &new, GFP_KERNEL); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + + for (i = 0; i < 1000; i += 3) { + if (i & 1) + mt_init_flags(&tree, 0); + else + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + + for (j = 0; j < i; j++) { + mtree_store_range(&tree, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret = mt_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != 0); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + } + + /* Test memory allocation failed. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) + mt_init_flags(&tree, 0); + else + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + + for (j = 0; j < i; j++) { + mtree_store_range(&tree, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + mt_set_non_kernel(50); + ret = mt_dup(&tree, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret != 0) { + MT_BUG_ON(&new, ret != -ENOMEM); + count++; + mtree_destroy(&tree); + continue; + } + + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + } + + /* pr_info("mt_dup() fail %d times\n", count); */ + BUG_ON(!count); +} + extern void test_kmem_cache_bulk(void); void farmer_tests(void) @@ -35904,6 +36102,10 @@ void farmer_tests(void) check_null_expand(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, 0); + check_mt_dup(&tree); + mtree_destroy(&tree); + /* RCU testing */ mt_init_flags(&tree, 0); check_erase_testset(&tree); From patchwork Wed Jul 26 08:09:11 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327569 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 DAE87C001DC for ; Wed, 26 Jul 2023 08:10:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7A7216B007B; Wed, 26 Jul 2023 04:10:27 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 72DAE6B007D; Wed, 26 Jul 2023 04:10:27 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5A6546B007E; Wed, 26 Jul 2023 04:10:27 -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 487BD6B007B for ; Wed, 26 Jul 2023 04:10:27 -0400 (EDT) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 113AB401D2 for ; Wed, 26 Jul 2023 08:10:27 +0000 (UTC) X-FDA: 81053040894.14.194D5CB Received: from mail-pj1-f54.google.com (mail-pj1-f54.google.com [209.85.216.54]) by imf21.hostedemail.com (Postfix) with ESMTP id 44A081C0019 for ; Wed, 26 Jul 2023 08:10:25 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="P+/0rgLt"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.54 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=1690359025; 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=oxj+btiC5bp07i0raCrQCISm2j0evx87VB7Ft6vQm0Y=; b=hdx0wLua97eNOdVYUbxo0kvSNeC/QtxCgORpn56lWpSybtQstIn6fsyGyDjD/gCcNk+fDp NdkVQy2ssxTkKEiER4VtPwGW9xtpbEKnKgaZ4e1puDFRi0VRf7NGLPEucE9Izdg7PKh9di R/87Bj42zZxd55SugxSSQMougcR+UQw= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="P+/0rgLt"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.54 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359025; a=rsa-sha256; cv=none; b=31TyLjLBfrKw7HjzGm6Rx17FvZR1+nFC8ETBlgoMPvTCv2I07L09VkG1GiWVlb94K4r0LE CIQ6+cnIYUO20oH29vHQjWwpIfyVrNZEU0Ichy2iHR4noMOanGbpQ9wSjy5q+5v3ljMZ37 BdqsJDRyczlFeQ+xgo6oyGYLcaF4r/8= Received: by mail-pj1-f54.google.com with SMTP id 98e67ed59e1d1-26826f93a1fso1646943a91.3 for ; Wed, 26 Jul 2023 01:10:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359024; x=1690963824; 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=oxj+btiC5bp07i0raCrQCISm2j0evx87VB7Ft6vQm0Y=; b=P+/0rgLtEdpbjzKqmA02o57JAFTpubjCpSW6mbosOnpFa92pkdk6Jcgr2NP/7Cwuqv X704pWI/GcFkT+iYFHPSJB4sqKMdrdQDbQO40IHz8iIVf4GjaTiv6wZEnyXnNguWrM+W x4jUL97/rQ4GOieM5c2xzpBxvTkZ6DSetuV5zIGVZqGZ2sm4rHt43AqEx6Fkn8k50sjH SRru4KNzIIA6FNTeYMNPz5gIVMHzVscuHdHd4gtKTsN9OUrOXGyDqcUS5HBnD3L+NgwX G5eGekoi/fvhPV5mfSGu8zzazu4u7WPmnD8TUvnKm5P2igUsV6DLAbGfvYr5+JXeQ9DH sPGg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359024; x=1690963824; 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=oxj+btiC5bp07i0raCrQCISm2j0evx87VB7Ft6vQm0Y=; b=MHleY4pVoSSgKPZ7/CKezHltlav90m9vdTQckcEtSdEzdrKCyG89UgcRVDCKFWH4rc yofjAq7ho30aaOTCZI86W5tj0Az8qgqr+1LzVfFf8FedE7t9gTtPENS2ZGgrhl7jMzfe yJ5VsJZXsZMjXxmdj/5sk7OCm8v6ar2AbtL1k8wQhTYYrgJv+WWGlxIooegGa1p7cE5n S6ktOEdSqVwn0axnim9rymq6inBzUMbU8MFxSelW+k+OmsEvUBCxu5WZk4gRsrepVOD7 lxCDppN0lRw6equcX77sHbot6jRWJgEhgxH6IsB97hlUUnI1hjrNlvsbK5a5xCRFyreT 7pKA== X-Gm-Message-State: ABy/qLb3TBksktmRivA8Y0NbDuUFE+Ob66dlb53VxgfnduExZZDrV0RU LHuNROHm2wyXPZ1mqZh1WPuZsQ== X-Google-Smtp-Source: APBJJlGlSCxdEfq1BDlME7pPijSE799iYFshp/KuL1hJgcfxhw5EPTeKsWGCQw9soPRWN5f9bpFYXQ== X-Received: by 2002:a17:90b:1b4f:b0:25b:f66c:35a9 with SMTP id nv15-20020a17090b1b4f00b0025bf66c35a9mr1209893pjb.48.1690359024079; Wed, 26 Jul 2023 01:10:24 -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.10.18 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:23 -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 06/11] maple_tree: Introduce mas_replace_entry() to directly replace an entry Date: Wed, 26 Jul 2023 16:09:11 +0800 Message-Id: <20230726080916.17454-7-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 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 44A081C0019 X-Stat-Signature: deig3kgaaeezueoup7ua8zaghzezcpqo X-Rspam-User: X-HE-Tag: 1690359025-606092 X-HE-Meta: U2FsdGVkX1+MjM7w/hZWi+XpwjLQm1z/5ak8ZkfaPGMVnnfqNfUca5tW0mOcG1ky8XLN4os9e2Q+B475eLw1Yj2h3vWVIG+jAGtIxKhmg92aEMBxnnboq5w2QWmMUT7zlA4iENVhpu5+VTTtA2zZbxC/9+qlGWroisXlHcKPJSbHgwNafXuK6DpyAWXzr7oOyF3u075cchCz7raq1pUqgXTMPEwTA/dm23BmA0nt8eHJJYzWwWU6NKxALb8pmk5lLxq6eus1NEXfBHNmBsx92YQhTzvDj3KKgEtQp6YSxR6yTS5EKxTzYBMuwjlcNzSwrvVPu9oAZZMD7EEhKhIoncedUAMH2I6jjARDT//4bXZ88zufgPI/2AIUU5BcLTmOZDQ6rgkEyHB1J97p7mwrGhu/PdG4ejbV+l7j2DbJQD+TeGGtjVO/v9esw9qpJxVE0+S2/BSa/H8Snrh6mwzYBnZmdtuRSDhPxX1+hn8I6SKgFJJilO6SodAttaRiQT+FzPofhOkzsu5+KEUPcVzpWw0rpZiUYDNl15I4G5i02jGnfZEXGGtM1PM1FUvc9cMjothK1JUiMUmnUi2OFIIjc3s7n1ZPPQQe4CDixOHsHAvtXGoklO3ihzOTjywfoXluQmdAYSW4dT3DfFPMLUBXmFhepJH5bHKojtdc4XF3b52bW8d0MoVt+zEbJult0LJTeobpgi/66zV4sdMHmbYAlIwG6NgFNwSMZvamXkiUHNZD+LguTDXgarCLjslg0hsIEgrQkp4yrQnDSVWnnuU+Ljv5Sff4PvydqFB2V6hcd5yHCNtzqkHBSFwOPZ8p62ZxPw5an2sSY8gfspTBzjRL7E6ptiiCtkKTQreoywBJgDBj/8wABLrUAX/E4yDxnOEd/pkwohTize3zgX76IwtPh010i2vNDzIB6QxfuXA/Dsg3fN9AfGag6z9vhvQmuv60R1FNUYN2uk7puYe2Frs JWkEIkHE MHSHB/eOczTJW/G1F7/Y+gGKQKf8TBBBuPHXVR3ZdMWd2pWZObRIj5YAymQKGd7BObVO4zemFJ+xdaUU2ccwSVETQWE/pFIjHj+JSN71m53r1Tt9SfWoct+HtcCsglvL3lK8J8mc1Hxa6E8E58gBH7AL7/FbDLX3DHW/FN7d9dtazuFK+AYr3kwtCLdMsLulP8kRPSzrHqSfuEGOXy1D2nkiMdlv85lre9PvhVFl97SiNH6lrytWMaJ+hC2Cwn6Z+szG7tawk4JToyElNfFSFi8cE9b9D/SVJD84p1ghhHZHr39GZMyX8g/3bZzY4yr72R7177k+nRFBLXF/Vl0QKWktEwkCG47FdS6Rns+NPnwztUFDS4acL4nbvyUiJNY80p9O0UUaQ5dyqjHw6UE4QOPor0eMMuwV9Z/2nt1MDSdWUjFWJjN/HKP0Ylwxw6xU0uKWniQ2BBPifMVjHy9O7+rR7gw== 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: If mas has located a specific entry, it may be need to replace this entry, so introduce mas_replace_entry() to do this. mas_replace_entry() will be more efficient than mas_store*() because it doesn't do many unnecessary checks. This function should be inline, but more functions need to be moved to the header file, so I didn't do it for the time being. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 25 +++++++++++++++++++++++++ 2 files changed, 26 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 229fe78e4c89..a05e9827d761 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -462,6 +462,7 @@ struct ma_wr_state { void *mas_walk(struct ma_state *mas); void *mas_store(struct ma_state *mas, void *entry); +void mas_replace_entry(struct ma_state *mas, void *entry); void *mas_erase(struct ma_state *mas); int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp); void mas_store_prealloc(struct ma_state *mas, void *entry); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index efac6761ae37..d58572666a00 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5600,6 +5600,31 @@ void *mas_store(struct ma_state *mas, void *entry) } EXPORT_SYMBOL_GPL(mas_store); +/** + * mas_replace_entry() - Replace an entry that already exists in the maple tree + * @mas: The maple state + * @entry: The entry to store + * + * Please note that mas must already locate an existing entry, and the new entry + * must not be NULL. If these two points cannot be guaranteed, please use + * mas_store*() instead, otherwise it will cause an internal error in the maple + * tree. This function does not need to allocate memory, so it must succeed. + */ +void mas_replace_entry(struct ma_state *mas, void *entry) +{ + void __rcu **slots; + +#ifdef CONFIG_DEBUG_MAPLE_TREE + MAS_WARN_ON(mas, !mte_is_leaf(mas->node)); + MAS_WARN_ON(mas, !entry); + MAS_WARN_ON(mas, mas->offset >= mt_slots[mte_node_type(mas->node)]); +#endif + + slots = ma_slots(mte_to_node(mas->node), mte_node_type(mas->node)); + rcu_assign_pointer(slots[mas->offset], entry); +} +EXPORT_SYMBOL_GPL(mas_replace_entry); + /** * mas_store_gfp() - Store a value into the tree. * @mas: The maple state From patchwork Wed Jul 26 08:09:12 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327570 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 3C06EC001DC for ; Wed, 26 Jul 2023 08:10:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D49AC6B007D; Wed, 26 Jul 2023 04:10:32 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CD3146B007E; Wed, 26 Jul 2023 04:10:32 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B4CF48D0001; Wed, 26 Jul 2023 04:10:32 -0400 (EDT) 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 A0DF76B007D for ; Wed, 26 Jul 2023 04:10:32 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 780D3409BA for ; Wed, 26 Jul 2023 08:10:32 +0000 (UTC) X-FDA: 81053041104.03.256380A Received: from mail-oi1-f178.google.com (mail-oi1-f178.google.com [209.85.167.178]) by imf09.hostedemail.com (Postfix) with ESMTP id 9EE8814000C for ; Wed, 26 Jul 2023 08:10:30 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CrBUyHbK; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359030; a=rsa-sha256; cv=none; b=wPqQVIDi2JxKrKY0yRC/fEOAHxAw9mABkkHfDiad/dwMgopfL5idHt3X+QdgJtL0jX3MIb 9eeVZTJfkGzujgPRRNAoDuJN+NR8sg461MeUSwP87ZbpJu5aKbH0TPPAwg/SJvtmdHkmgx mPssPXQqrVI25D1hS5PLJfQ0DCFVjaE= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CrBUyHbK; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1690359030; 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=v8uNs+P31bvWCjQDHXfNwA0J1eeKVpGhA2UwqZlpI48=; b=LuEN6yUEtTFMzV0nXB2HiBHL1bLeurDoGpAMKWpw6agBk62A4LnBSEd/5kt+bmwv7rF4CP 3ulZrHyI3M7Gbhg5lTF9+FaJpoU1sYWZ8wGT3T8NtYzo97QKjsvAhyRHKFC0P1cj+yb0RK wtBZuG/aolRlmRHvEHaqXW5G/pzcVWg= Received: by mail-oi1-f178.google.com with SMTP id 5614622812f47-3a3e1152c23so4462586b6e.2 for ; Wed, 26 Jul 2023 01:10:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359029; x=1690963829; 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=v8uNs+P31bvWCjQDHXfNwA0J1eeKVpGhA2UwqZlpI48=; b=CrBUyHbKlHgI9bJ+PDdaaetEcpHr3E/W2ZfSeQBeKeVprTl52WIKA+JT3TW5+Ml/Vt ddWID0Zgv01crS6rbjypqKita+JfgnUG4tKAb+l2OFoy32E4s/A8cPZuepcKPkIfxCqK 2Ve0brfKitPbiuM5fkRL7lSTRVdwqr/fwvAm0+bDvcAYv7+oX/fJ7rugbAx694yPbS8C y79T2h1uzsi7M/59p+ojtXI3BlaoZ2svHDneAsizA7/Q0qzjd2Tay0M7mOc+/5KMlRpf Wyv+4A63YfHdc49RtDmJ13nR93qde273z4c2bCDXtCk6qfm/zbcgPqnD0ZeDszcCz3JY T0dg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359029; x=1690963829; 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=v8uNs+P31bvWCjQDHXfNwA0J1eeKVpGhA2UwqZlpI48=; b=fWV4dpe5wOKXkcb26xuHKMHGV/I2TE5h5AUijaGbwGuG7Ecz8f1pq2dftR66QRUhLW xAP2eZ4qr2xvi/6Z3PbmvG/oBnluGrX1jEL/kPi4Qi3SG6D+Io1xuM3mt0Ywf7djOJ2K 1lsVlCwYSwgShrpfrQD8xZPUpAUxAkWM6HSWZcqmq0nTm1bVA79o78v8kJO4bL9OJpPg cypuH8BewXUHbI+WWpVkqlGvi2XBT62YkrvM8MKCWVNV7gWzOQRwgaQkcVdbATwncCxa dU7V9ozu11fi0Yi/73LK69m80zbD58sQg3qB1gZuw/65lA4WUV/8KO3EiGFKfaqxDs17 a46Q== X-Gm-Message-State: ABy/qLb+IDQdrsa+XFSqQXseC07r6cfNUsakDRI+HkayHXUGLS3zpG/T RXyjS2/sg4SgU0wfYQUJvL8sLQ== X-Google-Smtp-Source: APBJJlGhAux4gsHuRlskWB+2hAoyUd2LMLZZMtlCIKrNxAMe0PgykyqeVppW19z8AHH0EfD4FyyaJQ== X-Received: by 2002:a05:6808:1599:b0:3a1:e3ee:742a with SMTP id t25-20020a056808159900b003a1e3ee742amr1872990oiw.8.1690359029699; Wed, 26 Jul 2023 01:10:29 -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.10.24 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:29 -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 07/11] maple_tree: Update the documentation of maple tree Date: Wed, 26 Jul 2023 16:09:12 +0800 Message-Id: <20230726080916.17454-8-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 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 9EE8814000C X-Stat-Signature: xeew38zf4z6sj5qxo897tmrztbps5q14 X-Rspam-User: X-HE-Tag: 1690359030-662159 X-HE-Meta: U2FsdGVkX18IVpzw6l6NOhuwIMeHhcd9WI+yH5LiK9oi2+BK5bjjDB/jIP1p0Hj3SLHDClBf+7VQnwAjgY00TUvdxwJx0kLvNxwMCW3Prbg1SZT8HN9H/BU7Dyi0fg5hMrU4tfrxG8Zy3J91AlmssaAoKQ3xNJ3wGirbkaI/8cXyZIeI7dVyGu/jG+HesnwgJqeAxUjsoiZBqbhCaoDhGDD7FSs4n0xVaKv6bCFey5iDw3rCHDDnu8cJTkIdVprhaLNuYPFN3wCVG2yI1eH90MM+GoAK5S+ix9vWz/L0lmF3zyZ3cmVowT23VFIeWMhFm5ZqmKPZRSuPxxrY23x5y46Pnor5X3DjFioefUgwqdNaPZTTOSjs6TULFNKjfHgyg+Sh4/y9wl6QAEBROemdM8c1TWTSYsOtDejmqO4YU012vFaRkdo5Ka1iMGM/O7wqhQckJSsUtAkVF7xWXwcCNo7ARnRSZFB9LyOU/rzJhqLX+8rBGoOXDwkP852SfCGZkcoHar1sUXfL35ciKwpZTPAkn4pXtfxntREO42VHjxOm6HlS5uxjyyjbx42g+tfcTDN4kvs3DYd+Dou/Xi7LOVRABI9UGqSVVWYgSKG/I62pur5/ADoPtr/etqh8fs+gVY8OL8oeCKL1H2k6bCL+GjkcPVUpgX83s5L2XpgE5jGzzeOe+oGH0tRz5r12eUTGwNxBxJSs5yYkQsZ8ZQAZFywEKqlSsYGBgbEw+wlKcreS1v0lyIxYuakE3anDz/HzM0LnTjYGjd7sas3chf8vccsoybf0oTv40XH5IG3WJyXXtyzK28/8P0JPgpR8huNWh/BXrnWC14SDnOFb3bMqncqlOFCkNHNeM6dk1Brn34/JZM6KO/SsWhvBlX6mEUqanv4rzTEDWt0yFvyR72nasfTT0+UxYU/Fz0yD01z7zLQS3UqT+TZV+639JhN3eN7oeoUFEg30/IOhwaf8Rkz CHyDplj2 f9/e2zvcfbzRWCxr9jErS8z+3IJAPQy4FzNVwMT802clnbBGjlhxGduPOEie31Hd92++fR8o7h73T4N/zV/6yeNEt2jsZtBnKd65glrxudXv5NQxjItq6V0WSXQrr+6fDcqrxwVD7F7IDpwapA7uGSOQDStxnAeVNJeeEHvMiFP9eu7nDUytfCJ5LdFWOdLLVcY2B0HaAQumQumuPDyoKcr1tJOxAcIqgGWJG69JpPyViPfZuV8rWkM2mmHQhrVOAgcxRtkQIcA7ENhMfvF5c0JYcQwg7C3PBZB7uvHUOhd490Pp23FUUgE+ZfazsUyc4SppsYOLNQF8azbCfsqinSTP/y6gPZ/jNqObfp7Vbbw3n9FvicbGEaZlbA8LWLYcSBuhTgzePvuljTyzxI9u8ODuMNG+pXv1BAXGMNkuUDup21YXdL9xcf1QeEpHDqQCd57g0oRXBn9OH09KnTF2xuFDjfg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000132, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Introduces the newly introduced mt_dup() and mas_replace_entry(). Signed-off-by: Peng Zhang --- Documentation/core-api/maple_tree.rst | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst index 45defcf15da7..a4fa991277c7 100644 --- a/Documentation/core-api/maple_tree.rst +++ b/Documentation/core-api/maple_tree.rst @@ -71,6 +71,11 @@ return -EEXIST if the range is not empty. You can search for an entry from an index upwards by using mt_find(). +If you want to duplicate a tree, you can use mt_dup(). It will build a new tree +that is exactly the same as the source tree, and it uses an efficient +implementation, so it is much faster than traversing the source tree and +inserting into the new tree one by one. + You can walk each entry within a range by calling mt_for_each(). You must provide a temporary variable to store a cursor. If you want to walk each element of the tree then ``0`` and ``ULONG_MAX`` may be used as the range. If @@ -115,6 +120,7 @@ Takes ma_lock internally: * mtree_destroy() * mt_set_in_rcu() * mt_clear_in_rcu() + * mt_dup() If you want to take advantage of the internal lock to protect the data structures that you are storing in the Maple Tree, you can call mtree_lock() @@ -155,6 +161,10 @@ You can set entries using mas_store(). mas_store() will overwrite any entry with the new entry and return the first existing entry that is overwritten. The range is passed in as members of the maple state: index and last. +If you have located an entry using something like mas_find(), and want to +replace this entry, you can use mas_replace_entry(), which is more efficient +than mas_store*(). + You can use mas_erase() to erase an entire range by setting index and last of the maple state to the desired range to erase. This will erase the first range that is found in that range, set the maple state index From patchwork Wed Jul 26 08:09:13 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327571 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 0E2FDC001DE for ; Wed, 26 Jul 2023 08:10:39 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A149E6B0078; Wed, 26 Jul 2023 04:10:38 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 99E318D0001; Wed, 26 Jul 2023 04:10:38 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 817766B0080; Wed, 26 Jul 2023 04:10:38 -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 702136B0078 for ; Wed, 26 Jul 2023 04:10:38 -0400 (EDT) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 464E180D39 for ; Wed, 26 Jul 2023 08:10:38 +0000 (UTC) X-FDA: 81053041356.29.FF226F8 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) by imf14.hostedemail.com (Postfix) with ESMTP id 75F4E10001A for ; Wed, 26 Jul 2023 08:10:36 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=UY37TDKu; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.170 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=1690359036; 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=LYZiuBqx6ckWFl98anzbTzEwZ+z/345ZUTz3W5AilLA=; b=msBxuHY/v9B0mNKwBWbCZqFXXw6dGCaQBCOVEpffqHm3C/2KYEKAtp73QpTZKU+MBuukLO 9rmJSq7/eNuTCup6J2ephkGPffTHCWXrp8Lol8J4mspCf06vHcfIDwNqhE4bWEVHZAf1KY YKUQJaYbqf3sz0wiE9bnz54YqKjwlDg= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=UY37TDKu; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359036; a=rsa-sha256; cv=none; b=ZhvQ6731iUL5OBhn96PS6nCkqrxffFmH3eumC6Z/mEuBweWQFm6iHsZhFu1X2kZooU57RX QevGZ95CUZy2oqVuI+8EoUt32Ag6j2hW9zEPdqXlnYSIX5OlygdVUBUObsX5ZyfgsYHURj XvoqscI5BcnmZqdMtQ7qo6Bzc02iO88= Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-686be3cbea0so446084b3a.0 for ; Wed, 26 Jul 2023 01:10:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359035; x=1690963835; 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=LYZiuBqx6ckWFl98anzbTzEwZ+z/345ZUTz3W5AilLA=; b=UY37TDKu0twvwszgVhYceWMnSiyklSFwgsOVGywjtmrkLJSXFOYwHm0cFLDDibc+Sl +1VrunZVuLNYwXFEBJceFr/7cl/UxJ701yJbZmlFmHYaho6pTuZIdVh8kohzGqcox2X/ G/9/XrffPAYdh6AMJtIBZLDgcWQHQgF+7I+/jXOXF4gZsOmJ2EzpCo899MIPIqRyjIiP tBX/VyS7r4sbEogmJzWTzn/+sREeVGT8Bo+KzycwKdiq633va22OBvw2p+4WStXY6yXA Dq0qJbqciYrp/oNwDyzcp9LvnNAVegjxOI8T0ucLR/8q2ebzgfcWV3JK4fIhAIhQI8u4 kIiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359035; x=1690963835; 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=LYZiuBqx6ckWFl98anzbTzEwZ+z/345ZUTz3W5AilLA=; b=RrJ1EoGjJ1bGoIOdlvkU0LeKMvio1rMgL/N9pwnhguu7H+TDgPFTEsOyKwE41+SnwV 82HVQqOoaKvAen4NqhHr/icXxDm4EOujMFmija26iN562qOToqSPGak+gyhYlqrTV71U 60B6O59JbXp0zZZW8CJ/+ysxttKz+z9E2xKEtQiffV37VoqHYv/WEXcB/0+9m8OO5lO/ aYEeQVd61BCYAxz+w7GYwpEShnN/mysGwXqCOgP6qTlELeEWrCW2tcrHJEhLrkEO2+Tc /NDsahUT/lP3zHBiyWxrKGm5g8rUL8mEszMMtuyHe65HHtE4L1YbHxKvCsKUZC7LyWB3 tmJQ== X-Gm-Message-State: ABy/qLaqIjKtNvUFIQtdNjZzygzMixneHSM7q0EVtWuVJnWDBslS09+W WRW+1jda7HgUEr7jCSN7Y6WWWg== X-Google-Smtp-Source: APBJJlF8Oq29jicXQ7LZzSR8Tvg8Z3f0r8jXoW+wL7thrKSoHpxajUTRtxGMChVZFla02C1R6Weu5w== X-Received: by 2002:a17:90a:1b6c:b0:268:535f:7c15 with SMTP id q99-20020a17090a1b6c00b00268535f7c15mr1294451pjq.0.1690359035369; Wed, 26 Jul 2023 01:10:35 -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.10.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:35 -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 08/11] maple_tree: Skip other tests when BENCH is enabled Date: Wed, 26 Jul 2023 16:09:13 +0800 Message-Id: <20230726080916.17454-9-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 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 75F4E10001A X-Stat-Signature: aot5x36b38ecps4rws5yanpqx93umrcw X-HE-Tag: 1690359036-991096 X-HE-Meta: U2FsdGVkX1+pKUV4CWl99AIVm162gGN4uPMbFRPI9mwJS78Ze9PWwJhL7TbTmGzmYHefh4/N+FC7+t4G+bYk2XyOYr94vbu85y4RVhx4V9JfeG8vyaqu9fv8rzQV5NO4gje4/zIAUX/2C36aFn/DwFFp10gz6KRia1aq0eIyMeNCMHsX6HfOOiJsYZ8kW25OcQ9WDMJbsXJrSsGMCsQin46ODYsv+t446W0rSZDklXHzvcNwGv/rJJt+UilBHWnKNiw/hAwaF7OPir1db/7spyHmqhJwb14XnHDlTx2kxoaozVD0QRtEOMgVHxxgc83IDHIGxzgkQ5ab8FJe7fVx7Lvovn/rIG4e24uVkYWG+XPiWS0aorBYaazLjUz5XNeOXQbXSqmMzNAVIfbgEVzSy8Cn57pKv5hkyGts/NvsOvQUTQFKF4W543ljvYhrKZ36gQOmXqyQK6h3ktkdinfu9yAyn7TilGgv1MzY+eoQ/zQnRhSvGmXpDUFxn83xfgGNCvUiv3CSJzHgeS+PKZ7BPuMm9bluzrABsj32IBNbHVkPp5wl9d8vp/n6Fmtad5Q0xh1dG0T8ivS9aqYRqmrtcmahn0PKEI8YTOmmWuXOINU0H8mjxyGFvqgzuRECSXlqUuRPkRpWa3c9e5d8RTMKY4/j4/+hPo+aj3eATpN8vnP4B9BU9shOJjCOKJqUtbRGiY2Os2UrXdSpvupFnhj73SufUOXir5K9E+ylHWqG0p3PrCyurMlfhpAqzAcncV9rAP9L9P+l5KR1y+1lqc0AHcghju0mKRWxaJWpsJSejKzw2FFrUL0rTikwdtLKGf7GL7b/pC5Q9OiJsjJUpqlyzlbjW39mH/Dh7XtdNg7EKgZl17c8e2alcdw9OMyw7gyVyPBy5IHnVTMjsqb6fnkZFDLE9BOvZCFd5d5Bn/lTiH2xm2+Gl87A4w+LhKKjOne6eVK6VuZbF+YvJdeUois HRSrmdQW LMmWlsl3RizzQdxHK8clnNyHxbyeTDQBxUZ7gIvoAyKw/j53EoSnt0+3BkLPb1TqcZG1xCbrG7L5nVF0r/qGwJRY9eIAcOELJouvc3bur+/tb5M+sS4nPgIOc8f5MMeFVAKIoO13ZYMFW694vpwAKOdf4HHV6cQFV4Ysr2YchlSFYQHtjXiEHa2lLIUWEpwExhbZtmdZDklm90H4Xhl+gCvpgDie0WpSH5llA9xfl1ND/fZLsM/nXm/gUAWq1OH6fs3MTnkrm0T7WOQP3u8SAuNshF23KZsy7YdGdiX4sbaMPSGHbIyjSED4n/6BkLIp+pvFhkucWgslgzCqBSvDRTiDpW4DgFtVWl3eDCVHlm7/KJ1kK6B/XbKj2UsiLlmh/sDCGtRuuo4bhk0NkMyJbQQoR1AVl4DXTlDRbGAGxnghgzZO35hUMHVLynodq/vXyAMXvNIlA3n2Eq2dx5oGs/qt0SA== 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: Skip other tests when BENCH is enabled so that performance can be measured in user space. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 8 ++++---- tools/testing/radix-tree/maple.c | 2 ++ 2 files changed, 6 insertions(+), 4 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0674aebd4423..0ec0c6a7c0b5 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3514,10 +3514,6 @@ static int __init maple_tree_seed(void) pr_info("\nTEST STARTING\n\n"); - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_root_expand(&tree); - mtree_destroy(&tree); - #if defined(BENCH_SLOT_STORE) #define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); @@ -3575,6 +3571,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_root_expand(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_iteration(&tree); mtree_destroy(&tree); diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 3052e899e5df..57e6b0bc5984 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36140,7 +36140,9 @@ void farmer_tests(void) void maple_tree_tests(void) { +#if !defined(BENCH_FORK) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } From patchwork Wed Jul 26 08:09:14 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327572 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 AA504C001DC for ; Wed, 26 Jul 2023 08:10:44 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4BEA86B007E; Wed, 26 Jul 2023 04:10:44 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 447756B0080; Wed, 26 Jul 2023 04:10:44 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2E8516B0081; Wed, 26 Jul 2023 04:10:44 -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 1DD586B007E for ; Wed, 26 Jul 2023 04:10:44 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id EC0CD80CDB for ; Wed, 26 Jul 2023 08:10:43 +0000 (UTC) X-FDA: 81053041566.15.25329DA Received: from mail-pj1-f45.google.com (mail-pj1-f45.google.com [209.85.216.45]) by imf11.hostedemail.com (Postfix) with ESMTP id 16EFA4001E for ; Wed, 26 Jul 2023 08:10:41 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hDJE8eg6; spf=pass (imf11.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.45 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1690359042; 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=La30n3p8fENYrfJWqtvIRjpZvPcttyQzv7ZUcu4OWh0=; b=vLltKl03sEaRIoGphTMGOEacILEUi02p0LF/lBOp0ltxCXk1HSzrovzlgo7xTtDZVb0Bs1 8vMQausMh2cIqsJzlCtO8OhCrP5lBnAp6emjqj7WZRNz30ZVcj1S19sIGym/91BMVvrtbc VfKf1bv6zfROFqi5E2V/Jzz8eiL/0Xc= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=hDJE8eg6; spf=pass (imf11.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.45 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359042; a=rsa-sha256; cv=none; b=2sr2ytJ0dX4Ew1ZER7uSk2TplabnWtq7jDP12e3BOkmwqyADk3mF6d2FDvNrzRVe0iGknf lhAvW45y1EipWaAwN9cKt6ljVCPxnZ0uxcCOv5pyVRZ0gZA3maNB4qo6X3hRGJQKGTIn+C wqZzEN449jzw5OsChsjEZm/RYS0Myxg= Received: by mail-pj1-f45.google.com with SMTP id 98e67ed59e1d1-26598fc0825so487463a91.0 for ; Wed, 26 Jul 2023 01:10:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359041; x=1690963841; 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=La30n3p8fENYrfJWqtvIRjpZvPcttyQzv7ZUcu4OWh0=; b=hDJE8eg6JhSqyFPBgmdPFLb2NvreqZRkoQ0fdGojtOrd++HIHNVUOcYmZwlfCxm5K+ 7S9/adYQ+mg7sePuGXIBKc3RGbqqWjQTdPhVgF9gclNb+ndj+3HGIaBgnMq+mTnEsAfS nN2TDe1AymKzfNIyX0pmL+9gSFtSZWjLFgJDdDBiEQVKijpSxGzTzdDVwHZxORnAaQUU +Ccnk2vlrYUp96CC7W9TS8BkgThX3dUut8NY2hntTU6eCEHXncFT/nxcYtcUKsiEhorE tPaMsoIeutpOBq+cJKv6F4JMmekbuoNmYseftMJvCzZYYszTS4YyUs6sAV+hYDzi/ty6 YQHw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359041; x=1690963841; 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=La30n3p8fENYrfJWqtvIRjpZvPcttyQzv7ZUcu4OWh0=; b=eR/vQ9Hy6kQrUu0R597RgnEyMlo+R9Z9jMC3NcWgnK3k7pP+XprpUj0maH0NRqlTnP an38WR7X6I+vNyRJABSJh1ZfvTUE/lN7JRRvmbTVDi2nfkzbKyivXu8X+NodHml0VnNF v7782GzY6nVNZiAxxZ7lOvFuvU0G3CQs+JUmb3cbRAoGzLqnuMN9ZRk7sNKxBeQw8hV0 bDtQvJVDXREORsVql9NS0x6VS24wlHOOlh9/UPl72PSHbd4WrLahEYDHh09kEv3Hz0g0 CncXmzpiPHp0U/3YbEu6xKi/yg4ym8F3sFU22+0KrRfVk3/Tgo6i9GHkapNfs+NnVvYF 4i0A== X-Gm-Message-State: ABy/qLYID+UAFBKDBwT8/nVcBNC249TBQDdI8PwzvZudOv3am3EVNp+q xGlKYRiPSUgG/V5jfObtE4z3UQ== X-Google-Smtp-Source: APBJJlE8cIpYZ+sTitqIk/v4pR8PRlkevNUmvEDeqPpuFom8xFn2KAvQVis6NXMadCyNx4ljN105gA== X-Received: by 2002:a17:90b:8cf:b0:25c:18ad:6b82 with SMTP id ds15-20020a17090b08cf00b0025c18ad6b82mr1683093pjb.21.1690359040966; Wed, 26 Jul 2023 01:10:40 -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.10.35 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:40 -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 09/11] maple_tree: Update check_forking() and bench_forking() Date: Wed, 26 Jul 2023 16:09:14 +0800 Message-Id: <20230726080916.17454-10-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 X-Rspamd-Queue-Id: 16EFA4001E X-Rspam-User: X-Stat-Signature: 4shreagydg8ynmtiyrjzi1rhhqgj7hm4 X-Rspamd-Server: rspam01 X-HE-Tag: 1690359041-944704 X-HE-Meta: U2FsdGVkX1+vhb8qqEjgR/bfnqJ4sM0LBjp9/xQsrd6FOP8vAY0aaRzGodatim8e0raO+kh4/k77Vrqg5jfSX2SEquQWhK9yaBu/xj1MepB01bFne5DGBJBm2zqVfWAdsRwE2Tj1S59GXRje23puN14PSqjkM+7JX3ic2C7e0/oaiWnpJ+Oncw/8J2scIJA48dTSG99RUGfIPo7PoYjcjjRYoFcTifLZFRR69RpcYzczf6dzJ+e28qFaRVGPR/Z3UWQ085W1uccJ76d5uXOCI3eLbc4YtEELu1DVO2vcw8nCMyz7TOH2ZIVM6fF4V0AgSIffEj+0El/LIuEjopCOo5PYcYi22ODkZQcKLOQs6hc+nc6DllS9yw05X/HpVaGWEqPtM2oHJ7kj3dmUUqW8D5QQeOdNXkvXt2QHH+85gb5Wncy+0naMM0e0vaAhYji3ZBphSlP3JkKm016k2FFAh4qsu58neZjtU/Q4qM6g5nBQVx6+dsGLCLvB/lyg6VB1tRMTWlKHvyy6wlfzFVv1PfMPT+0hVp+WjBvJF5brZ+x063524aEsfbTg7duAE9jAo9reeiek6SJCXdSC7zrjxX8oYnYsh9pWB7kiLgy7Fp0AnWlnRciBUMq67DZhc2nXKXuxImU3MJ7z0tiEjqK89wllbdmU9q18Onz4sv6AgvTsBz5KujIcERoMhnaGG3OuK03VtpPMoyq60aoYunj3G8hsDUARbDfQpVKUsegNkqiGd9ukO4mIRSI6q/M7ydlGkGb8C8hGAlA9hODrVqvEMXmyw7sq9HYJbZ+mgdBbY0z5pY0dCHi/ZpvqTawATbSV99DVh6KEVERU86JmtQUl9NxiWBxl76xhRloil7yZip7+pKyRX2NC+Y8jBtr/boYJ4Ru/JrYCpCrX/ys6jMWV20IlD5Oq5OR5fXmKR29VgtvBNlEIGHL1pbS0+uOl7Vm5iDcPpljB9vfIFy32z3O gJYlPhpg WuRQt/rdbiqL9nHZRQwVh8SW5b0zrp1lDQLaVYA3Cx6cOWP28+zmfTh+5V3uhDizRXTXrZQOxIuvYfirxEcIehrg9TeaGsqN6qHRC2xM3HsvKCQzpyIy7KVumIQP20CeA349tYu+KmctxkHuvg9yIioG+98fOvwqME2hdUlNlUpkSpSRUunB73ZMTcW4JpHRua6olcc8kHe0an+PmfehVwlO/DrYpdLZoFE4Lc62CfBQNeSJtyScYcg04QXY4Ht5VkKnYtGNralX1J48fTq1J+P2D8o3AK9yIGcwneyuI0tijhrbHwGrmVoyfduxDEagklf3dThMdlp6XKTusSiL+p2e4AS1iGp15U4KQwMqKZEa/Usn8VapBshMJrvl/UM3wy17uR4vUdSVhTwmFU5KKbclO0kbEFGDhAaKFQ8mFFw65vBU9sKpQFLzBTJ294gA9lCzu3U95FA+sp5g5Jkf45AYubA== 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: Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 59 ++++++++++++++++++------------------------- 1 file changed, 25 insertions(+), 34 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0ec0c6a7c0b5..bbdac08927c6 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1837,7 +1837,7 @@ static noinline void __init check_forking(struct maple_tree *mt) { struct maple_tree newmt; - int i, nr_entries = 134; + int i, nr_entries = 134, ret; void *val; MA_STATE(mas, mt, 0, 0); MA_STATE(newmas, mt, 0, 0); @@ -1847,26 +1847,22 @@ static noinline void __init check_forking(struct maple_tree *mt) xa_mk_value(i), GFP_KERNEL); mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - mas_lock(&newmas); - mas.index = 0; - mas.last = 0; - if (mas_expected_entries(&newmas, nr_entries)) { + mas_lock(&mas); + + ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN); + if (ret) { pr_err("OOM!"); BUG_ON(1); } - rcu_read_lock(); - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; - mas_store(&newmas, val); + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) { + mas_replace_entry(&newmas, val); } - rcu_read_unlock(); + + mas_unlock(&mas); + mas_destroy(&newmas); - mas_unlock(&newmas); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); @@ -1974,9 +1970,8 @@ static noinline void __init check_mas_store_gfp(struct maple_tree *mt) #if defined(BENCH_FORK) static noinline void __init bench_forking(struct maple_tree *mt) { - struct maple_tree newmt; - int i, nr_entries = 134, nr_fork = 80000; + int i, nr_entries = 134, nr_fork = 80000, ret; void *val; MA_STATE(mas, mt, 0, 0); MA_STATE(newmas, mt, 0, 0); @@ -1987,26 +1982,22 @@ static noinline void __init bench_forking(struct maple_tree *mt) for (i = 0; i < nr_fork; i++) { mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - mas.index = 0; - mas.last = 0; - rcu_read_lock(); - mas_lock(&newmas); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + + mas_lock(&mas); + ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN); + if (ret) { + pr_err("OOM!"); BUG_ON(1); } - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; - mas_store(&newmas, val); + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) { + mas_replace_entry(&newmas, val); } + + mas_unlock(&mas); + mas_destroy(&newmas); - mas_unlock(&newmas); - rcu_read_unlock(); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); From patchwork Wed Jul 26 08:09:15 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327573 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 6D692C001E0 for ; Wed, 26 Jul 2023 08:10:50 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E5AA56B0080; Wed, 26 Jul 2023 04:10:49 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id DE3D36B0081; Wed, 26 Jul 2023 04:10:49 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C376B8D0001; Wed, 26 Jul 2023 04:10:49 -0400 (EDT) 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 B5B006B0080 for ; Wed, 26 Jul 2023 04:10:49 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 8ED731C9EF1 for ; Wed, 26 Jul 2023 08:10:49 +0000 (UTC) X-FDA: 81053041818.01.7A6D73F Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) by imf20.hostedemail.com (Postfix) with ESMTP id B59B11C001C for ; Wed, 26 Jul 2023 08:10:47 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Xb1tm6Zv; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359047; a=rsa-sha256; cv=none; b=hGRDhGjKsTtLNjLny/jNfMzXDfJrCQpz+aVBexSuoylRnlmzi2xUd+20368e4KS/pxGnEt gWTfWTXz0/pfDLn2sBtnxKFOe2p6E6tdXI1ysQLMhyPvXc46eIrKOQKCOx7x5bfI/nCKiK K+HAEgXtMWBlAetjUy+/DBXCZYYh43k= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Xb1tm6Zv; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.41 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1690359047; 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=RIXSYqX84CuSmVFU1GzkCcpfMb+I1xPBZiIvC+Oh4rg=; b=Yf+5FELCw3kgNw476FtmHkCnIKOR5WfqRzgV+CG8I4wvitS6tCJ89DmfHxzsjVeT8C+4Q7 F5uD+9RuadhLLPxfKkqQwvbUQYl99fvYuF4VEaYs1lPWBWaaNq/FYw9twazMMdAYYHmCJW nP1VK0eCdfI1PO7rqImowKCQff496f0= Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-26814e27a9eso1424338a91.0 for ; Wed, 26 Jul 2023 01:10:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359046; x=1690963846; 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=RIXSYqX84CuSmVFU1GzkCcpfMb+I1xPBZiIvC+Oh4rg=; b=Xb1tm6ZvxlWzJvqX93uwzRGpsT6PZkoFfclMBbf+N88CMfcBjpcHzy22/Q5ZUk0yeM RV0oqyIVZs7GGUtS6u9+54GAmKmAszOPceUrYzTN/evSZuCOY1j1CwfyHGvPZwK53pU2 7s9z/roqFedDZiv2JrBeiw4ENhNrUyKYhyjZoyd5ua4VqSKD/QkVWdJTEGiLlwYku4+D ziMxOcBUKQ5S4q1OVBLPBKmtZsvIlwQAtRpQ9SeL7B+VSGC0WZ81Bc1dctqe9DXiVAaX QPuMR+EtJiiNUa4Ac6SX9im67+cS4XerefidUFH3BFkltVwrclITfqsrZQd/2LB18kzE RCnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359046; x=1690963846; 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=RIXSYqX84CuSmVFU1GzkCcpfMb+I1xPBZiIvC+Oh4rg=; b=GAKzVoemqWGYsyjjJ0KE/1LlgS2D2g5EntnCqcgIoeyrm7retgtFhN1uDS3r5s7R97 rHxgmKscfUJPz2hu0L4Z/47WOs92GpzyW+CS2Op5ZIc/Avywz60AKdV6REFDWBCy9RKN QzLh2rhU4adtkmEGDZocUX2jzRQRVQfPYYeASDZQFc2sAbKSOL1Id523Q45+DQyQhY6N u+Za5IcjCKume3Z3R1Z5wKYT+EP1bF5mnsEH1VDns3bU1NCdlOz2clvFeA+QL0tXdr7T fiEciLgwvFluqq3egD9VMFAXQx3gp1U/t22StV78f2WsNqE0TkZdBDlqtLVN6pzSbsBe tJDw== X-Gm-Message-State: ABy/qLaeXfgR7oXnXD038oFIDPy/O5rGg1pDfxDVtvcBnCKw8dP8WXYA uQ69F8bt9UcDJkqaQ7/+jbc9Tw== X-Google-Smtp-Source: APBJJlEHomf/FPMiQ187RwZDxLz38AsGu02tOBeqsit032eLLBERo7jna6rKcRr9i0zDxFPbS5SMig== X-Received: by 2002:a17:90a:e281:b0:263:5d25:150c with SMTP id d1-20020a17090ae28100b002635d25150cmr974204pjz.29.1690359046624; Wed, 26 Jul 2023 01:10:46 -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.10.41 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:46 -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 10/11] MAINTAINERS: Add co-maintainer for maple tree Date: Wed, 26 Jul 2023 16:09:15 +0800 Message-Id: <20230726080916.17454-11-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 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: B59B11C001C X-Stat-Signature: nffo6o3bp99n4y5txqh4rsjfqyi6zua1 X-Rspam-User: X-HE-Tag: 1690359047-696258 X-HE-Meta: U2FsdGVkX1/k+3hULRILc/PHhkbictAX8l/f4sxyBltDGS5PxI32QZrySjYdrYOMQCsNOAlSJ7UQpGeDsQhR0coSdkh4iRlqusVyvO3G8QWQ6vLbKEaYu8GqkyDTiQKiAcof2wj5we+ZXnIGelIWjMCmiPA5KYyeXf6l1FoBqIoUDYzdCxau2t5GWZjnTkJG5WEp98a85EX3FkQZjGy0kUqrWUolNlyh/2+KD0GUt3p3lv9BPRU6bMDhFBcRwoxfemKW0e+s+ux3oXM+PptWSFwbXd0VBIS6oB2wdAzyDyEb9sSKLG//ghQ/TE8wUOuz3EjabopGm53Il19X/uqV3qsrG8R5sdy9Pg0viT6W9MiPn7LeGtonOlNwxhykE1oZXseFUY+ryLCudXt/lDnNaYJc0IoOHXHandw9w51rbXddHjkqA1YYVq6m77JT240Q6pR3JSCZGD1L/M3l0cFSsHU5SR6U4I5QJAMxOyPWZxJZVYro2ok0t0I5VG+rdXFffDeKHPD0K83gXoMMlBvVRmut6AnXRR+eYR5n7iO6ykqF/kvU3tdX5eSEPwrptKYYZlo7KqAq0RbmaL6YJlqKAu1kcyHgG/him/np/kj+HJ9WRAhzfy02F727NbQdr8tKGlAtJ7uq1bp+ad31iIqNnF+VH1GdBBdyLanD1GP+M8u8x8wxOe6QLEMXabkZK0glaw4oQBQ2t1LRkS975/EQ0FqjECvvlIPUoEiXraZqCyM+2mtNjtsDTg/4YY+ivdOhYUE1ptIdQRFRd8z4ens0Px6qRBYYG3iCcPpbbNR/T4mH5qyVV+hQoAPhJCmb6xe1sr+RGT0+8Tu05Cw+xuobcR/b8r+GBUHWqapNSFtigUbaDZvpr1QpH8tx7th4T8BKt6sN3b3SKe1lnLTxCbd7EoLS5OGZ17RUyhAyfD/jh80A1EXKqURnUA28+tIWpT4qma1BOPwBZq2OINW+pEg DK4WDj9i hBF5sJUeUgcDajv85+RnJJpl25bRzbKNE8EBDXKo+ayQ00n09VQX1FYH20Osvv0NBJUe1U7rJrLAS0YcaBpCz98oNyoxXM8435F3FIp8VjMuC1WR+Lia2zXIP7o6RNxcJPIkBAB5UbzOAl8QvtWINd52s+ycOqeLJmzlXEdZyoSwvfQftR7tn8wUM+/hyCNwu72erUwLKcLdNt2ah5gGn7Ky56r904s/C4xFv6Ovf/1Lz7Lt4gn6ZYxyNd1wyoCMd8SCB4U6yq1g07jhY2aN8z8icUj1S1fww3c30XHulOhdNIMfboA3NNGckQBqJSXUebi5m/3U9TQVzsgrMz+/xAFG6YtU1SaFp2Y6GPOf5c+qyeHayhDMLoHcdUSS/RAQ6tQE5D7/ZB+YcSIxIB9eE8+oel/m7LxORXsbLUSygZal7CvcPGp8PQjizmx77ub6wMPFFUoNnrPKy+0t3+NTj74gULzMgDomm2Qfog2vh5aV0V0EwzBX8YSynNw== 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: Add myself as co-maintainer for maple tree. I would like to assist Liam R. Howlett in maintaining maple tree. I will continue to contribute to the development of maple tree in the future. Signed-off-by: Peng Zhang --- MAINTAINERS | 1 + 1 file changed, 1 insertion(+) diff --git a/MAINTAINERS b/MAINTAINERS index ddc71b815791..8cfedd492509 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -12526,6 +12526,7 @@ F: net/mctp/ MAPLE TREE M: Liam R. Howlett +M: Peng Zhang L: linux-mm@kvack.org S: Supported F: Documentation/core-api/maple_tree.rst From patchwork Wed Jul 26 08:09:16 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327574 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 3AFD1C001DC for ; Wed, 26 Jul 2023 08:10:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CFA846B0081; Wed, 26 Jul 2023 04:10:55 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C85188D0001; Wed, 26 Jul 2023 04:10:55 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id AFE556B0083; Wed, 26 Jul 2023 04:10:55 -0400 (EDT) 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 9F1096B0081 for ; Wed, 26 Jul 2023 04:10:55 -0400 (EDT) Received: from smtpin15.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 7FC92A0100 for ; Wed, 26 Jul 2023 08:10:55 +0000 (UTC) X-FDA: 81053042070.15.BC0CD3E Received: from mail-pg1-f179.google.com (mail-pg1-f179.google.com [209.85.215.179]) by imf28.hostedemail.com (Postfix) with ESMTP id 98FD9C000B for ; Wed, 26 Jul 2023 08:10:53 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="kHc9/HMq"; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1690359053; 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=AgnuXatC2qbxaqbZ65LcEyHnR8tMExq1rwNTS9IK9fs=; b=O9aVTTK5Gn6VQFDTdRDK6QLVWomBW3METDta1p56dC6jhgNFBbY00/p6qcLp40Adlh8BLW nsVPtsjW/B4Aoz3bC1XyIv0MH1p5YHbkCMLK/QQEXw4yMTCeiYgifCX/0+U0Em2bYUASkM gxNqAXJYz0PH5pNOYv9nks+iy+pRtso= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359053; a=rsa-sha256; cv=none; b=hT7H6NZhfsrVvtm7lF/uSH3bIXVFQOM5Iua7Q4PMnJmHQ/G/NcmD9OuBeF420U0tFtzAEp AIyaus9pE8ECcgjBMJnPz67KSfcu0+V+n7IlyrU481OOdooqpffvlq9KPaGPVwcgxJY1lf zxQMvnUNwwE+yELh4MPeYvSg1z4xbPk= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="kHc9/HMq"; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pg1-f179.google.com with SMTP id 41be03b00d2f7-563de62f861so473371a12.1 for ; Wed, 26 Jul 2023 01:10:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359052; x=1690963852; 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=AgnuXatC2qbxaqbZ65LcEyHnR8tMExq1rwNTS9IK9fs=; b=kHc9/HMqaF9R8G/rXM59e0F3CbnZX/wdeNMwFdC4XbxVCwGzgEppqL5qnyB3vNmNVg c8cJwfifm5dQn0XdItECcYmL7213bc+olR8WIHI+oZFMOk9CMsY7zzqyGkHUyoCUbS5O dEHqxuqR01Hr6wkpXFSSeIiFRl0E2XvoCppdLpSz0jYGs9bX0Vjkjgcf/CoG7h0V+GT0 hgH6/mckjlLMtGPSbuo3RnGG1oclyUlcIARBc+DEe60f642YycPhYk3JYCpHJAImiCtD q04bJ/2nn8P7ybfvGd8hRKKdkHJCH61syEN3XyDj2vXfd5qQFV1ojWAT1xwPxp7AAMlx S/qw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359052; x=1690963852; 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=AgnuXatC2qbxaqbZ65LcEyHnR8tMExq1rwNTS9IK9fs=; b=V2dvZ0AR5cxjL5r7JRtb2l+VWutm0Pyq9whrxawBQnwADVy3eAmz5FNPHfVbkjmmnl RA4rnwe3aezBzjl+R6JG9jw0WHwiCJ5V1bSFArnrLP0YdKMDKMrfJftMdy1MqMAOhMrg mCzmNDzpEfDhsC1GBkt4men025SUYGI6+9pow7L8JFzk3jBmlyEUONmbwF/1uw0B3xR2 HEsdbevpQS6S4xaDFgEwt6+Zbz6dADawhgLfpED3G0KQS/xK9aDpusjE9qZLw27VRIV0 /pbEQFoArdBgPsSiQkS/mJzwSpLLXpnBA9SZvM4yU7csAbmojN42naPHIanzDpFhdZOj eA/w== X-Gm-Message-State: ABy/qLaddSoqfOGOEhUI2kP45YRQvhvAUydZU99cngQ76B5I1DvAhASo hyBbeWkFFShUqkMY56ZIeuaooQ== X-Google-Smtp-Source: APBJJlE/k5FlCPp9wjkDmS2lNntkmIxAcglpNb71TQX77k742PkAt1Hf8XjFuPAOgyeUv3smQ4YSOQ== X-Received: by 2002:a17:90a:6344:b0:263:e423:5939 with SMTP id v4-20020a17090a634400b00263e4235939mr1066813pjs.28.1690359052249; Wed, 26 Jul 2023 01:10:52 -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.10.47 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:52 -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 11/11] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Wed, 26 Jul 2023 16:09:16 +0800 Message-Id: <20230726080916.17454-12-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 X-Stat-Signature: yjc9yyyb34nzru4pdjk4di4pserzkj51 X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 98FD9C000B X-Rspam-User: X-HE-Tag: 1690359053-312593 X-HE-Meta: U2FsdGVkX1+hBEUd54ArMTX6GKlOaCF4tlmW7B7fA3qZitZ3KAfxnqgvuLhIOdwMfIDAIGglwBzxa7m5Et05yyiKgFQ29j2YybbxesP1v/+KGVR5v5cH/cKCYM4YqMPkUzPlRPIkAY7/5Fm4EhxsvzyfyIzVKmrrPFkLSnquH0ob6ZA3flP0bi59v4TxQWPpgns4aVVGL/GHJGv5u52CjkWeGxpfd6o8FVpbrEyrXzmSJhQmK6/78yKIxIsMF+6nyjECotxW6T2SRG62HyZZ7wIMfFctKGWSmk6nXv+fk0csfkOb40mJh9OADxPnqY6yFleJfwOrM3x16cCM9S6x8VooQsEhJcUXTBmtJDCB9+tRyvIlJvgaYISax6jnBACPa3xAcGwHyKgNZgtgwfWibce1mmy2Ux/rDgFIB+A6iwF7oWD4LetC45+PjhFASQWRkXY9FbLddJv2BCaPqFmZihjaIWwHXqcbjDwQkWv5/lc3NsRAhJ5W9tiM6vqG4cdAA0dFwyv2ACnRqoljb9JtINpJ8VwlzsHsqt+ZKw+vqjLogBT6LTMLSYz8mXRQ2f2lKOu6ctF5UWm3tBM1qZ0PHpQxPyDrjRjhSrFO966bgOARy5Dqe3buFwryAiAwDlwbuE3CrNXZB+o3v9sNwt2d+8PalPZQ27xz13cJ3vJF9KbUJppUg1pYH4mVQpkI0+IO8xHfDqt9wBjFYiWwXDWneFMNTxvCzeJiTwgQlvSsq9s+2pLrRzRtKtWWjT3g2FD31VcJlfkw9xT7hoqo9StZt2WR4uazlHziXGhyT0K9h32gbA+CrqfRZEze8m8jVaN34/KlFLyheSD7GPvqzqNUZijai3vcZv8VK4RCLvbFGlkp2rwGhccYJ7SFgIA1toKesL3iBgNPtqLdQjRb27BbSe+iNWUwx38fxGIg5PUsdRaEY+bzvQCOw4KIyEaUtgUNLRsnwVH0USU9GuMU8oF zuyXqjRG gevbUbtnvDeMQkEUUYURP/uChaVBNBuOEpYRZ2XITLSZTQpQevJx0hrYZwk5PjD9tY6a41J/fqb7cV628u3lHJLkCQp4HBSEn66bLV2+0FfIHngKLxze9HmnufhFfJ5YsGQccHx01X8T0EmYBwCxw99yaO/jtTxpv2iTphmcPaFgzZBIZ/kv8SoQpqY3M0Wemb22MxLtUm1srG1NZGUkdf0QfzYmcS6audCrvYBMb4BujbUsDyzjy4lH0pKDKneRJCJhUzKqj/JYK4EC3gwHYRKgsmnNaKmLjXF4E7mPNLOp7zUzaY4kVmcWC5vWVDhziP2UoBHUPiZnbxYZHjsqCYt0l3h0OhGv2h6YGkaN9bCrnKjJGf4YCoeBHYbWc6euZj6ktNK151NR5DxYaEek1zcl5++mlpBFpvZRYgBI8NIGEoDaj4eE374Y64wZDX6/sdx3BLbWxwbyrwGuhGOum89QnYJQwnUcEog+hxTzetJftwH18XTYe7/oyaxgleugS2xEKId7Kh0J1R9NYVOsYWckXSJzU6vcFeXYqE5bL1FvjC44= 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: Use __mt_dup() to duplicate the old maple tree in dup_mmap(), and then directly modify the entries of VMAs in the new maple tree, which can get better performance. dup_mmap() is used by fork(), so this patch optimizes fork(). The optimization effect is proportional to the number of VMAs. Due to the introduction of this method, the optimization in (maple_tree: add a fast path case in mas_wr_slot_store())[1] no longer has an effect here, but it is also an optimization of the maple tree. There is a unixbench test suite[2] where 'spawn' is used to test fork(). 'spawn' only has 23 VMAs by default, so I tweaked the benchmark code a bit to use mmap() to control the number of VMAs. Therefore, the performance under different numbers of VMAs can be measured. Insert code like below into 'spawn': for (int i = 0; i < 200; ++i) { size_t size = 10 * getpagesize(); void *addr; if (i & 1) { addr = mmap(NULL, size, PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); } else { addr = mmap(NULL, size, PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); } if (addr == MAP_FAILED) ... } Based on next-20230721, use 'spawn' under 23, 203, and 4023 VMAs, test 4 times in 30 seconds each time, and get the following numbers. These numbers are the number of fork() successes in 30s (average of the best 3 out of 4). By the way, based on next-20230725, I reverted [1], and tested it together as a comparison. In order to ensure the reliability of the test results, these tests were run on a physical machine. 23VMAs 223VMAs 4023VMAs revert [1]: 159104.00 73316.33 6787.00 +0.77% +0.42% +0.28% next-20230721: 160321.67 73624.67 6806.33 +2.77% +15.42% +29.86% apply this: 164751.67 84980.33 8838.67 It can be seen that the performance improvement is proportional to the number of VMAs. With 23 VMAs, performance improves by about 3%, with 223 VMAs, performance improves by about 15%, and with 4023 VMAs, performance improves by about 30%. [1] https://lore.kernel.org/lkml/20230628073657.75314-4-zhangpeng.00@bytedance.com/ [2] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang --- kernel/fork.c | 35 +++++++++++++++++++++++++++-------- mm/mmap.c | 14 ++++++++++++-- 2 files changed, 39 insertions(+), 10 deletions(-) diff --git a/kernel/fork.c b/kernel/fork.c index f81149739eb9..ef80025b62d6 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, int retval; unsigned long charge = 0; LIST_HEAD(uf); - VMA_ITERATOR(old_vmi, oldmm, 0); VMA_ITERATOR(vmi, mm, 0); uprobe_start_dup_mmap(); @@ -678,17 +677,40 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, goto out; khugepaged_fork(mm, oldmm); - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count); - if (retval) + /* Use __mt_dup() to efficiently build an identical maple tree. */ + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_NOWAIT | __GFP_NOWARN); + if (unlikely(retval)) goto out; mt_clear_in_rcu(vmi.mas.tree); - for_each_vma(old_vmi, mpnt) { + for_each_vma(vmi, mpnt) { struct file *file; vma_start_write(mpnt); if (mpnt->vm_flags & VM_DONTCOPY) { vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); + + /* + * Since the new tree is exactly the same as the old one, + * we need to remove the unneeded VMAs. + */ + mas_store(&vmi.mas, NULL); + + /* + * Even removing an entry may require memory allocation, + * and if removal fails, we use XA_ZERO_ENTRY to mark + * from which VMA it failed. The case of encountering + * XA_ZERO_ENTRY will be handled in exit_mmap(). + */ + if (unlikely(mas_is_err(&vmi.mas))) { + retval = xa_err(vmi.mas.node); + mas_reset(&vmi.mas); + if (mas_find(&vmi.mas, ULONG_MAX)) + mas_replace_entry(&vmi.mas, + XA_ZERO_ENTRY); + goto loop_out; + } + continue; } charge = 0; @@ -750,8 +772,7 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, hugetlb_dup_vma_private(tmp); /* Link the vma into the MT */ - if (vma_iter_bulk_store(&vmi, tmp)) - goto fail_nomem_vmi_store; + mas_replace_entry(&vmi.mas, tmp); mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -778,8 +799,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, uprobe_end_dup_mmap(); return retval; -fail_nomem_vmi_store: - unlink_anon_vmas(tmp); fail_nomem_anon_vma_fork: mpol_put(vma_policy(tmp)); fail_nomem_policy: diff --git a/mm/mmap.c b/mm/mmap.c index bc91d91261ab..5bfba2fb0e39 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3184,7 +3184,11 @@ void exit_mmap(struct mm_struct *mm) arch_exit_mmap(mm); vma = mas_find(&mas, ULONG_MAX); - if (!vma) { + /* + * If dup_mmap() fails to remove a VMA marked VM_DONTCOPY, + * xa_is_zero(vma) may be true. + */ + if (!vma || xa_is_zero(vma)) { /* Can happen if dup_mmap() received an OOM */ mmap_read_unlock(mm); return; @@ -3222,7 +3226,13 @@ void exit_mmap(struct mm_struct *mm) remove_vma(vma, true); count++; cond_resched(); - } while ((vma = mas_find(&mas, ULONG_MAX)) != NULL); + vma = mas_find(&mas, ULONG_MAX); + /* + * If xa_is_zero(vma) is true, it means that subsequent VMAs + * donot need to be removed. Can happen if dup_mmap() fails to + * remove a VMA marked VM_DONTCOPY. + */ + } while (vma != NULL && !xa_is_zero(vma)); BUG_ON(count != mm->map_count);