From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 598CCC001DE for ; Wed, 26 Jul 2023 08:22:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232732AbjGZIWv (ORCPT ); Wed, 26 Jul 2023 04:22:51 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:33382 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231720AbjGZIWI (ORCPT ); Wed, 26 Jul 2023 04:22:08 -0400 Received: from mail-pj1-x1030.google.com (mail-pj1-x1030.google.com [IPv6:2607:f8b0:4864:20::1030]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E6DB12715 for ; Wed, 26 Jul 2023 01:09:55 -0700 (PDT) Received: by mail-pj1-x1030.google.com with SMTP id 98e67ed59e1d1-267eee7ecebso1852097a91.1 for ; Wed, 26 Jul 2023 01:09:55 -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=b8ABl5SifuEXI0OQWWV5P2I+xlB/oJ3DcjafWiDYtaC0zo0VN5nk8DpFXlWBRDV2bL V8dEcBp9FKr88q0wXHGIFhRi/J/eINzHelyXR9dz4qI2eRGME+kjpowiqJxxmclmu7H/ +z5/tn+IufLtUWiJymE2nTQ+7UmO3fByg4Rrl+fc9m+aNSbUkUP8cohfoioNxFvA1qCO F/PXLhY436GAqHSWvnw0CyOVjnzvUe0hoP8zd817AGVA/TwA5Efb+yhZ2RGiASXHBTOf n6EHEB6XNXiFC3oF4aI++/GhLkcvKa2DB4/jPW4oXv/DlAKw3o2Ezv0kFBFgsvBFJwf3 UUuQ== X-Gm-Message-State: ABy/qLYmJoUPIX/BJXrsdmNe7o2miOPH3Ry8tWQPUoNrZqtStny8bGVE iZfsGqySpD1Ed5TiGpEUreHknQ== X-Google-Smtp-Source: APBJJlGTCbgSnoEUEY2Im4b6IteSzBL20T2KsQb6OtigwSGhrzItecI4bNmqd6Se4OFmw5iiEF2MyQ== X-Received: by 2002:a17:90a:c002:b0:268:2500:b17e with SMTP id p2-20020a17090ac00200b002682500b17emr1115938pjt.23.1690358995399; Wed, 26 Jul 2023 01:09:55 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id gc17-20020a17090b311100b002680b2d2ab6sm756540pjb.19.2023.07.26.01.09.49 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:09:55 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH 01/11] maple_tree: Introduce ma_nonleaf_data_end{_nocheck}() Date: Wed, 26 Jul 2023 16:09:06 +0800 Message-Id: <20230726080916.17454-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230726080916.17454-1-zhangpeng.00@bytedance.com> References: <20230726080916.17454-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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_eno= de *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; +} =20 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); } =20 static inline void *mte_mk_root(const struct maple_enode *node) @@ -1411,6 +1418,65 @@ static inline struct maple_enode *mas_start(struct m= a_state *mas) return NULL; } =20 +/* + * 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 =3D ma_slots(node, type); + slot =3D (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 lockd= ep + * 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 =3D ma_slots(node, type); + slot =3D (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 --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id E832DC001DE for ; Wed, 26 Jul 2023 08:23:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233135AbjGZIWz (ORCPT ); Wed, 26 Jul 2023 04:22:55 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60308 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232950AbjGZIWL (ORCPT ); Wed, 26 Jul 2023 04:22:11 -0400 Received: from mail-ot1-x333.google.com (mail-ot1-x333.google.com [IPv6:2607:f8b0:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3C9844C13 for ; Wed, 26 Jul 2023 01:10:02 -0700 (PDT) Received: by mail-ot1-x333.google.com with SMTP id 46e09a7af769-6b9c434fe75so5317097a34.0 for ; Wed, 26 Jul 2023 01:10:02 -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=bfVoGm7k8Cpk1pXl1ecNlOjAsPts8ptA9pNKiw6TfHPYoUPh9Q16EDe4m7kJEyzlCo rktko8wfJjPQ4BsadNqPOxSEtwCzUB6mWyT3Auo1q8nsCpv8dRwY4PWxCXoJkuu08ZDo djdqTOU1SmBzYWJvui+jfO5nza8mGSHZD46iEqHhXx+IUc8s5KWMCUqS71YaUXVMumlL a8+zPHgjJa+p5deX62i7A54bnyu2JwIwHW9D4zrr2HmnLoUSrqTFTVaXSpZUPhJSve5N I2IfAS0MAi0r0tVlhs61ChsfVwtTLW8Ju+/yPazm5GkbEdukRDEtyW2sl5Fog3+nMBvr UfsA== X-Gm-Message-State: ABy/qLYA39rEC1VVVfMWouznzgAmX0gOTFxI/6fbHxhwMjXRgbe/RxQ1 lZyAiI89o/6jEVs/E1KIU+Zwag== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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); } =20 + 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) !=3D 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); } =20 + if (!mte_is_leaf(mas->node) && + mas_data_end(mas) !=3D mte_nonleaf_data_end(mas->tree, mas->node)) { + pr_err("node:%p mas_data_end() !=3D mte_nonleaf_data_end()\n", + mas_mn(mas)); + MT_BUG_ON(mas->tree, 1); + } + for (i +=3D 1; i < mt_slots[type]; i++) { void *entry =3D mas_slot(mas, slots, i); =20 --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C1A31C001DE for ; Wed, 26 Jul 2023 08:22:32 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233062AbjGZIWb (ORCPT ); Wed, 26 Jul 2023 04:22:31 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60422 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230143AbjGZIVx (ORCPT ); Wed, 26 Jul 2023 04:21:53 -0400 Received: from mail-oo1-xc2a.google.com (mail-oo1-xc2a.google.com [IPv6:2607:f8b0:4864:20::c2a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DBECE559A for ; Wed, 26 Jul 2023 01:10:07 -0700 (PDT) Received: by mail-oo1-xc2a.google.com with SMTP id 006d021491bc7-565f2567422so3860174eaf.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=iN1GF0ma8Wbx6+0uw5PruHmc6hW+1CeMdO4dPrmwe0xFCZLUNOe67mzSXHSQkIaaFn OjVqSMXSD8cOvW/N6dHAKrqehB4echCEzo3W4dPgMP8rO+dfY7i8c/F0CLUBC4yEA36t RPLZvXnPGt5J0VeUYa2SUzWvwXIfvKtUVWR+jeKEjBOkho0IiljJjY/TCeEFftuw0ntA v7yrooUEcd+03c+6TH51bdWbCoeDNo0UWSs3TY7A0I5C70aAyNXLTodqYYnEiAhK9cce 8s+3/ZqwG+qvmgk8BgfiAOrXaz+7wi9s8syRIeDtefXie7wsej16NpIjjjyTYEt7nF5l Phhw== X-Gm-Message-State: ABy/qLYX+b49FICBnLJ6yH8dpsM0j2C66L9O/DHtVG9ifhJ+EDcl6qNm qTgPNi3Vm75+rVKfQpOVknp5ZA== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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); } =20 +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(unsi= gned long parent) } =20 /* - * 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 *n= ode) { unsigned long p_type; =20 - p_type =3D (unsigned long)mte_to_node(enode)->parent; + p_type =3D (unsigned long)node->parent; if (WARN_ON(p_type & MAPLE_PARENT_ROOT)) return 0; =20 @@ -451,7 +456,7 @@ enum maple_type mas_parent_type(struct ma_state *mas, s= truct maple_enode *enode) p_type &=3D ~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; } =20 +/* + * 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 mapl= e_enode *enode, } =20 /* - * 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 =3D (unsigned long)mte_to_node(enode)->parent; + unsigned long val =3D (unsigned long)node->parent; =20 if (val & MA_ROOT_PARENT) return 0; @@ -519,15 +537,36 @@ static inline unsigned int mte_parent_slot(const stru= ct maple_enode *enode) } =20 /* - * 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 *enod= e) { - return (void *)((unsigned long) - (mte_to_node(enode)->parent) & ~MAPLE_NODE_MASK); + return ma_parent(mte_to_node(enode)); } =20 /* --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 1A337C41513 for ; Wed, 26 Jul 2023 08:23:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231808AbjGZIXP (ORCPT ); Wed, 26 Jul 2023 04:23:15 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60704 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231840AbjGZIWY (ORCPT ); Wed, 26 Jul 2023 04:22:24 -0400 Received: from mail-pj1-x1031.google.com (mail-pj1-x1031.google.com [IPv6:2607:f8b0:4864:20::1031]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 794B26A6D for ; Wed, 26 Jul 2023 01:10:13 -0700 (PDT) Received: by mail-pj1-x1031.google.com with SMTP id 98e67ed59e1d1-2680ccc1d52so1608492a91.0 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=IKlrQAtPWQQiDTaGob0MP2WoDMDqBZyI/H4WAjjZcJa/LL/a9zXvF5grA6U1p7JMyz vWKA3YXkkROE8oZnGyPWUQ+qBd2UNCJShO7d9H9muAsa4OlPlufr/5FaKIeCaFgEg29F seY+nJoUdyno01AyXRgb7Pt9VMwfH/IlR4xBNdsYFwMJRuQHeSSLc1JhYdW09xJcmkCB rjtaziXcoRI3izxBa1qZCmBYFjeENzPILMomrEsg6KGdc1weSKYFwn6I35N/6CaMtfaq tkP3OYcLO3WWt8GS2l2efl2xIjMKf+GK7m5EouBy8nFDpngklY0BOXcx2hWM8CAjxwyH 0YZw== X-Gm-Message-State: ABy/qLaoMNrU9uBVVvdk3mLJRPZEWicXK0yGtjmHCMIKAeNs0TetOKsx bVYmKudN5fVnCUOyfW8G6Ml/NA== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 in= dex, void *entry, gfp_t gfp); void *mtree_erase(struct maple_tree *mt, unsigned long index); =20 +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); =20 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 l= ong index) } EXPORT_SYMBOL(mtree_erase); =20 +/* + * 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 loc= k. + */ +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 =3D 0, i; + +try_ascend: + if (ma_is_root(node)) { + mt_free_one(node); + return; + } + + offset =3D ma_parent_slot(node); + type =3D ma_parent_type(mt, node); + node =3D ma_parent(node); + if (!offset) + goto free; + + offset--; + +descend: + slots =3D (void **)ma_slots(node, type); + enode =3D slots[offset]; + if (mte_is_leaf(enode)) + goto free; + + type =3D mte_node_type(enode); + node =3D mte_to_node(enode); + offset =3D ma_nonleaf_data_end_nocheck(node, type); + goto descend; + +free: + slots =3D (void **)ma_slots(node, type); + count =3D ma_nonleaf_data_end_nocheck(node, type) + 1; + for (i =3D 0; i < count; i++) + ((unsigned long *)slots)[i] &=3D ~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 mem= ory + * allocation, @to_free will store the last failed node to free the incomp= lete + * 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 *n= ew, + gfp_t gfp, struct maple_node **to_free) +{ + struct maple_enode *enode; + struct maple_node *new_node, *new_parent =3D 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 =3D mt_root_locked(mt); + if (unlikely(!xa_is_node(enode))) { + rcu_assign_pointer(new->ma_root, enode); + return 0; + } + + new_node =3D mt_alloc_one(gfp); + if (!new_node) + return -ENOMEM; + + new_root =3D (unsigned long)new_node; + new_root |=3D (unsigned long)enode & MAPLE_NODE_MASK; + +copy_node: + node =3D mte_to_node(enode); + type =3D mte_node_type(enode); + memcpy(new_node, node, sizeof(struct maple_node)); + + set_parent =3D (unsigned long *)&(new_node->parent); + *set_parent &=3D MAPLE_NODE_MASK; + *set_parent |=3D (unsigned long)new_parent; + if (ma_is_leaf(type)) + goto ascend; + + new_slots =3D (void **)ma_slots(new_node, type); + slots =3D ma_slots(node, type); + request =3D ma_nonleaf_data_end(mt, node, type) + 1; + count =3D mt_alloc_bulk(gfp, request, new_slots); + if (!count) { + *to_free =3D new_node; + return -ENOMEM; + } + + for (i =3D 0; i < count; i++) + ((unsigned long *)new_slots)[i] |=3D + ((unsigned long)mt_slot_locked(mt, slots, i) & + MAPLE_NODE_MASK); + offset =3D 0; + +descend: + new_parent =3D new_node; + enode =3D mt_slot_locked(mt, slots, offset); + new_node =3D mte_to_node(new_slots[offset]); + goto copy_node; + +ascend: + if (ma_is_root(node)) { + new_node =3D mte_to_node((void *)new_root); + new_node->parent =3D ma_parent_ptr((unsigned long)new | + MA_ROOT_PARENT); + rcu_assign_pointer(new->ma_root, (void *)new_root); + return 0; + } + + offset =3D ma_parent_slot(node); + type =3D ma_parent_type(mt, node); + node =3D ma_parent(node); + new_node =3D ma_parent(new_node); + if (offset < ma_nonleaf_data_end(mt, node, type)) { + offset++; + new_slots =3D (void **)ma_slots(new_node, type); + slots =3D 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 traver= sing + * 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 =3D NULL; + + ret =3D mt_dup_build(mt, new, gfp, &to_free); + + if (unlikely(ret =3D=3D -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 traver= sing + * 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, @ne= w 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 =3D NULL; + + mtree_lock(mt); + ret =3D mt_dup_build(mt, new, gfp, &to_free); + mtree_unlock(mt); + + if (unlikely(ret =3D=3D -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 --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 9572AC00528 for ; Wed, 26 Jul 2023 08:23:21 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231580AbjGZIXT (ORCPT ); Wed, 26 Jul 2023 04:23:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34968 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231778AbjGZIWU (ORCPT ); Wed, 26 Jul 2023 04:22:20 -0400 Received: from mail-il1-x136.google.com (mail-il1-x136.google.com [IPv6:2607:f8b0:4864:20::136]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2B7456E99 for ; Wed, 26 Jul 2023 01:10:19 -0700 (PDT) Received: by mail-il1-x136.google.com with SMTP id e9e14a558f8ab-348c03de0e7so16509305ab.1 for ; Wed, 26 Jul 2023 01:10:19 -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=aWtrxjF1kCpeTRpF9u6Rgcqbc3rRKslqBQcTAO64Xha2JuLo9TrVHs2a9Ad7WlFp2d qNRZ6oymkX5NjgKhIfIjvf4ykwKpPNOppEc2YfKb/4rUcxrDeYlu/cNIKPdUSCviaOAD XA8BSjgCw+O/Xefwmb0gcohkxV83nIZe0Ucenj0T/zsWsN9OY/Vlexe8jxT/BcOai/bu cEneq9jtMp8RiIP/B7iIXH+kXuL9QhpwbGrI4L8jS8HlavrIzLyCszaL/SH8ABiLWM/4 ejZ/QcEPwMHJXpqexTLGz04eWpAI/tL7gz59SqpzV00dP2WZbhnU0OITPw70ZaPM/2MM B14Q== X-Gm-Message-State: ABy/qLYHE5sYr+lENtiiOhNdjuB7c6xssiGslyKnj2Wnw54FbUAJKddc M7qkZoG56MxafSUCzH3iZ7sczw== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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/ma= ple.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 ma= ple_tree *mt) mt_clear_in_rcu(mt); } =20 +/* + * 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) !=3D + ((unsigned long)enode_b & MAPLE_NODE_MASK)) { + pr_err("The lower 8 bits of enode are different.\n"); + return -1; + } + + type =3D mte_node_type(enode_a); + node_a =3D mte_to_node(enode_a); + node_b =3D mte_to_node(enode_b); + a =3D *node_a; + b =3D *node_b; + + /* Do not compare addresses. */ + if (ma_is_root(node_a) || ma_is_root(node_b)) { + a.parent =3D (struct maple_pnode *)((unsigned long)a.parent & + MA_ROOT_PARENT); + b.parent =3D (struct maple_pnode *)((unsigned long)b.parent & + MA_ROOT_PARENT); + } else { + a.parent =3D (struct maple_pnode *)((unsigned long)a.parent & + MAPLE_NODE_MASK); + b.parent =3D (struct maple_pnode *)((unsigned long)b.parent & + MAPLE_NODE_MASK); + } + + if (a.parent !=3D 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 =3D ma_slots(&a, type); + slots_b =3D ma_slots(&b, type); + + for (i =3D 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] &=3D MAPLE_NODE_MASK; + ((unsigned long *)slots_b)[i] &=3D 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 !=3D 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 !=3D mas_b.min || + mas_a.max !=3D 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 =3D 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 =3D 0; i < 1000; i +=3D 3) { + if (i & 1) + mt_init_flags(&tree, 0); + else + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + + for (j =3D 0; j < i; j++) { + mtree_store_range(&tree, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret =3D mt_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret !=3D 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 =3D 0; i < 1000; i +=3D 3) { + if (i & 1) + mt_init_flags(&tree, 0); + else + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + + for (j =3D 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 =3D mt_dup(&tree, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret !=3D 0) { + MT_BUG_ON(&new, ret !=3D -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); =20 void farmer_tests(void) @@ -35904,6 +36102,10 @@ void farmer_tests(void) check_null_expand(&tree); mtree_destroy(&tree); =20 + mt_init_flags(&tree, 0); + check_mt_dup(&tree); + mtree_destroy(&tree); + /* RCU testing */ mt_init_flags(&tree, 0); check_erase_testset(&tree); --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 7C77DC001E0 for ; Wed, 26 Jul 2023 08:24:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231550AbjGZIYB (ORCPT ); Wed, 26 Jul 2023 04:24:01 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35006 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233117AbjGZIWx (ORCPT ); Wed, 26 Jul 2023 04:22:53 -0400 Received: from mail-pg1-x52d.google.com (mail-pg1-x52d.google.com [IPv6:2607:f8b0:4864:20::52d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 951426EA2 for ; Wed, 26 Jul 2023 01:10:24 -0700 (PDT) Received: by mail-pg1-x52d.google.com with SMTP id 41be03b00d2f7-563dfffea87so495581a12.2 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=ST/ygb2omoo2B6YbOZKvUc5nx+mLRb6IPoBNbqDZyALeOhHYNtYqlmTQyAw/jFNqOi 5f5QIOp9E31x0/nFaipam3h7+g3cGWmn/2TwMZa9j/IE69PhIGMBvPteuQcv0qOjgSFt pBsE25Gf+9lBqljidDe7FENBt0eAqo7DHYUUkdz3IaMMzJGWS4cHpCcvFuG97ZPVr/4H 5mcP+efKuIP7IW0LUKY3Y1fNCVI8afPKKPrDBUG3T9rQ+BezIE4kZMpBH3ejpFVOwnlw er6G+aegHrml2/PyLCate0JqC4+g10d7w7srFpfcdy6jwetCSrKmrKLS0FEFe3Gg8E6Q xrZw== X-Gm-Message-State: ABy/qLaageP8CtDHOnnTtJLdMbHfV+MfbNwx/gS9DLdw49mdk2CNMz6x jnRsruW9UAhvLeHpQ63xfv56Bg== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 { =20 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); =20 +/** + * 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 succee= d. + */ +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 >=3D mt_slots[mte_node_type(mas->node)]); +#endif + + slots =3D 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 --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 642F7C41513 for ; Wed, 26 Jul 2023 08:24:16 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233172AbjGZIYP (ORCPT ); Wed, 26 Jul 2023 04:24:15 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35074 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233197AbjGZIXC (ORCPT ); Wed, 26 Jul 2023 04:23:02 -0400 Received: from mail-oi1-x232.google.com (mail-oi1-x232.google.com [IPv6:2607:f8b0:4864:20::232]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CCF8E6EB5 for ; Wed, 26 Jul 2023 01:10:30 -0700 (PDT) Received: by mail-oi1-x232.google.com with SMTP id 5614622812f47-3a43cbb432aso4468802b6e.3 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=GhND8y0QX/1y/JqADFWzvfY59Y4c2/pbLuJeOdjBZ19Z6VUpKmHoM18guKIg6eZ5ZB k1jMrt4Kr6xv2ZOzrHWbA91NinLaTUme/Ba5v3nwosyMbm0yxpXC3IZWwSlBbgoA3zU0 rXhAcPsGXtLxeRV7zl6aHIhVtbYJVb0n+T+7gzVrcNt/QpJEvfVSwrjm/cX5H5KV9dMA kKp8RjgnFLdqkZm3gAcopxinuEcaaPOm3WH7Ppx5++zGHpdmAvyIev8g1pGnLtoEoG62 7Eqnzb6eIhUS8fQ4mPF/LpJu9mGSt/QQB86V89dwOuryyukntZ6y49vi91hPqb8aU+MF d2MA== X-Gm-Message-State: ABy/qLblFcU3Y5VREasqwwAc9PLV+vMDub3cXjprnj+Hy1oBUr6mBoM9 BaXPqqy0IHRNW/TWHBXJsxZsrQ== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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. =20 You can search for an entry from an index upwards by using mt_find(). =20 +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() =20 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() wi= ll 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. =20 +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 efficie= nt +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 --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 0E331C001DE for ; Wed, 26 Jul 2023 08:24:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233189AbjGZIYS (ORCPT ); Wed, 26 Jul 2023 04:24:18 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35122 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233212AbjGZIXD (ORCPT ); Wed, 26 Jul 2023 04:23:03 -0400 Received: from mail-pj1-x102c.google.com (mail-pj1-x102c.google.com [IPv6:2607:f8b0:4864:20::102c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 42D87729A for ; Wed, 26 Jul 2023 01:10:35 -0700 (PDT) Received: by mail-pj1-x102c.google.com with SMTP id 98e67ed59e1d1-267fc19280bso471286a91.1 for ; Wed, 26 Jul 2023 01:10:35 -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=FHXA37mzyhXAKsMZqjPSXfkY5MeIzs/lgtgyH5NFzqdYj8/j7KH8HTim7tO1HAydZG 7XxncsKSHVVmer5wf6oh6fFixAO0Px1BPLwZgpwmvtcGM7xooahENJglKm36V9uj9ogD YIAlLNXsUKQGLS7z5K4tfVRMTZeul+5A6HPBSI0dLrDwu/6+jrOV0stkGCtk7A79ZO8Q JcDq9ipWLYE+vMYBO+kIbCxjH+gz+4q/KYSLmIJM3HIjXFDzBghV6z08wkF1pwesBqW5 uPlMlAs7HFHytFnX7UXCIRsv5xT7CYC3drr71se0O7dGmq81jc3zX5YhRnTIeMXGhtxh tgdQ== X-Gm-Message-State: ABy/qLapj4zxuOPLoawN+ZI+0+l4dJrESL5NvLz+uUTG5hJ68bAKEFQN Ckck6za3Oo5FOBYjPSCFxDkRiA== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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) =20 pr_info("\nTEST STARTING\n\n"); =20 - 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 =20 + 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/ma= ple.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) =20 void maple_tree_tests(void) { +#if !defined(BENCH_FORK) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 203AEC001DE for ; Wed, 26 Jul 2023 08:24:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233202AbjGZIYW (ORCPT ); Wed, 26 Jul 2023 04:24:22 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34772 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233232AbjGZIXG (ORCPT ); Wed, 26 Jul 2023 04:23:06 -0400 Received: from mail-pj1-x1031.google.com (mail-pj1-x1031.google.com [IPv6:2607:f8b0:4864:20::1031]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 767354C29 for ; Wed, 26 Jul 2023 01:10:41 -0700 (PDT) Received: by mail-pj1-x1031.google.com with SMTP id 98e67ed59e1d1-267fc19280bso471349a91.1 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=cV8szWzFIKAFTG6jKyy9Qbf8JIrX/7XTAP4Gyk1wiJJBqA8mgRemntoHzhVvsDzjk7 lxEDR4FCPZ/pH/NrJxt1qwtPTy4kx6sp6tRPvRwNQUb3CJ7YSx74e1mIXWyU71nnegVq VAIX9+2tTB8CpFLxt+MWwywJOZQ/mjmOG1c6vVsm54J01+YfmitXkwUu0+126dgW/T4q IukYhk90SjN+2Roxcz6vcMsKz87QdV1K/TrDpxyrcKfMRpFUB2bKrzWSOf5awkAbYJzP +UOnYobqL7aAEj+wSfzRgxPori6Xpi5nkiE7Wvvfov1wciTMv+eRARyOUb78onE+N4pi 6vyw== X-Gm-Message-State: ABy/qLZXSMg8NGOyOlW0f47nxTRr6AW/TtzWktIQqbyKi8Pk605O0/uW hJr7CXY5VdpgXaMBpPprPafS2g== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 mapl= e_tree *mt) { =20 struct maple_tree newmt; - int i, nr_entries =3D 134; + int i, nr_entries =3D 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 ma= ple_tree *mt) xa_mk_value(i), GFP_KERNEL); =20 mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree =3D &newmt; - mas_reset(&newmas); - mas_reset(&mas); - mas_lock(&newmas); - mas.index =3D 0; - mas.last =3D 0; - if (mas_expected_entries(&newmas, nr_entries)) { + mas_lock(&mas); + + ret =3D __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 =3D mas.index; - newmas.last =3D 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(struc= t 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 =3D 134, nr_fork =3D 80000; + int i, nr_entries =3D 134, nr_fork =3D 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 ma= ple_tree *mt) =20 for (i =3D 0; i < nr_fork; i++) { mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree =3D &newmt; - mas_reset(&newmas); - mas_reset(&mas); - mas.index =3D 0; - mas.last =3D 0; - rcu_read_lock(); - mas_lock(&newmas); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + + mas_lock(&mas); + ret =3D __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 =3D mas.index; - newmas.last =3D 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); --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 701E6C001DC for ; Wed, 26 Jul 2023 08:24:05 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233126AbjGZIYE (ORCPT ); Wed, 26 Jul 2023 04:24:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60762 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233141AbjGZIWz (ORCPT ); Wed, 26 Jul 2023 04:22:55 -0400 Received: from mail-pj1-x102f.google.com (mail-pj1-x102f.google.com [IPv6:2607:f8b0:4864:20::102f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1E1187293 for ; Wed, 26 Jul 2023 01:10:47 -0700 (PDT) Received: by mail-pj1-x102f.google.com with SMTP id 98e67ed59e1d1-26814e27a9eso1424339a91.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=Z7whO3wjFjmhOSFup48HchiHOm1Dx1nVHJu/v/mbDs5+LS0gvHjceokOJ/21O91qGQ z2w97bYAbwcR071+OvXHSn7KinzgxSfu/klnHPpMtb680ij6YWpAmBldr0DrE5WS7Itc Kf+4V6NIZsLY+gszQkGiYit9eMZnqeJDQ/yx9jciS6AJ9cTJxP0WfPtzVErnug0r/AGx qlEt1v/t14ChX8qPakZLD9UHfaoGABZHd13Fn7qYWuu4j0DAUr1XotyrC2rFdW6uH2Ix VSJIEtqpbPAbDoXQZTrGO37jNql2bg3A3c7GNhq+2+9s7Tnk1KBkyPlQuwkPbNQjI7IF D9SA== X-Gm-Message-State: ABy/qLaIgQWERJ3BB7UNg3pbjEtq8WgfMZxiLfRQdYuNgKXhUYUNfJ2/ 2Umu1NkrTuQd4toEUy0wuBBGDw== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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/ =20 MAPLE TREE M: Liam R. Howlett +M: Peng Zhang L: linux-mm@kvack.org S: Supported F: Documentation/core-api/maple_tree.rst --=20 2.20.1 From nobody Tue Sep 9 12:56:55 2025 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 vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id D7EECC001E0 for ; Wed, 26 Jul 2023 08:24:41 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233221AbjGZIYk (ORCPT ); Wed, 26 Jul 2023 04:24:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35020 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232091AbjGZIX2 (ORCPT ); Wed, 26 Jul 2023 04:23:28 -0400 Received: from mail-pj1-x1034.google.com (mail-pj1-x1034.google.com [IPv6:2607:f8b0:4864:20::1034]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BDBEE72BC for ; Wed, 26 Jul 2023 01:10:52 -0700 (PDT) Received: by mail-pj1-x1034.google.com with SMTP id 98e67ed59e1d1-2680a031283so1983666a91.3 for ; Wed, 26 Jul 2023 01:10:52 -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=E1CyTe1fmk5AAR8lwHcG4JV4ACgIkyI7hSfFI8kQHbszlchlMFHzU5Wk1b2Qb0+qsU yp9/dqBr+QRMRj5tiU4tHyKzjiQHky5F67Cs7C3As4inKRm6/gT8IHIdgBZlBdnVt6D0 hjpEZU0eAlNvaafQ11GLrrsMY4JxaVR8Png3qb8SaOSUk7CXBTspDIyRSaSSfWt3I54j nrL6SwnNcYVcwfN0CXF6ZoS70/T49Byx379U/DUIaHCWyFJrZvXHMQ5EZHmpimpN4F0M DJg1vuzFNkhEL1EsvUX7DitzjZ8qk4vPnBbNmzO+XYMVeTcNLrON/NKWTVpFxPO7foLM 97tQ== X-Gm-Message-State: ABy/qLYz8t0jJ1apN9yo2XgVzsDYRr3UWcBHEL6g607A071Mb9YV0PFr GdCqaIX0Lk/GDnCuYaDWiuYyrQ== 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 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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 =3D 0; i < 200; ++i) { size_t size =3D 10 * getpagesize(); void *addr; if (i & 1) { addr =3D mmap(NULL, size, PROT_READ, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); } else { addr =3D mmap(NULL, size, PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); } if (addr =3D=3D 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@byteda= nce.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 =3D 0; LIST_HEAD(uf); - VMA_ITERATOR(old_vmi, oldmm, 0); VMA_ITERATOR(vmi, mm, 0); =20 uprobe_start_dup_mmap(); @@ -678,17 +677,40 @@ static __latent_entropy int dup_mmap(struct mm_struct= *mm, goto out; khugepaged_fork(mm, oldmm); =20 - retval =3D vma_iter_bulk_alloc(&vmi, oldmm->map_count); - if (retval) + /* Use __mt_dup() to efficiently build an identical maple tree. */ + retval =3D __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_NOWAIT | __GFP_NOWARN); + if (unlikely(retval)) goto out; =20 mt_clear_in_rcu(vmi.mas.tree); - for_each_vma(old_vmi, mpnt) { + for_each_vma(vmi, mpnt) { struct file *file; =20 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 =3D 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 =3D 0; @@ -750,8 +772,7 @@ static __latent_entropy int dup_mmap(struct mm_struct *= mm, hugetlb_dup_vma_private(tmp); =20 /* Link the vma into the MT */ - if (vma_iter_bulk_store(&vmi, tmp)) - goto fail_nomem_vmi_store; + mas_replace_entry(&vmi.mas, tmp); =20 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; =20 -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); =20 vma =3D 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 =3D mas_find(&mas, ULONG_MAX)) !=3D NULL); + vma =3D 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 !=3D NULL && !xa_is_zero(vma)); =20 BUG_ON(count !=3D mm->map_count); =20 --=20 2.20.1