From nobody Fri Dec 19 16:06:21 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 76CF4C83F01 for ; Wed, 30 Aug 2023 18:36:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S236748AbjH3Sgu (ORCPT ); Wed, 30 Aug 2023 14:36:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53970 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244317AbjH3M5w (ORCPT ); Wed, 30 Aug 2023 08:57:52 -0400 Received: from mail-pl1-x62f.google.com (mail-pl1-x62f.google.com [IPv6:2607:f8b0:4864:20::62f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D8904194 for ; Wed, 30 Aug 2023 05:57:25 -0700 (PDT) Received: by mail-pl1-x62f.google.com with SMTP id d9443c01a7336-1c1e128135aso21813285ad.3 for ; Wed, 30 Aug 2023 05:57:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400245; x=1694005045; darn=vger.kernel.org; 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=MP6g95MTpMxGO+X1eOP4Lih7hj+Gz/gWGNfVacVPrOc=; b=D2BcaqjVPO/gzlkDGqLxR4Cu3/LnZyAeaV3VAZQQARePdLsqtmWsIITHmSPR2Rc1zS SG33/PIy8p9d1+OC82IeZaaF0nx8p5Binm5j31I/rhLP0Y5Y4ptG+iBIS8crit4PHJHR 5oKXE2TkpTbISwljRWGTNRqe3iWgsnYuw9/aG5I2GKLetUeG0/BzPco2GHrKu3+ubi/G hW5UQObQRQjPS2Qw1MM1vqQXcCqWTFYf7jq4l/soaEwneg1oNu4Ke/Pn1p8NNE+VfCs+ Il5/cJv5MpPxSsxSCoW2AmAaKQeG5EfJ9pa7oDem7ORUMkPRp/vg9k3UF3WDeHl/AMrw Kolw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400245; x=1694005045; 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=MP6g95MTpMxGO+X1eOP4Lih7hj+Gz/gWGNfVacVPrOc=; b=EQpMLok4BdLen62WG+S0DC9mrWmYM6r4tXbsJimafulaCh+VvV7SIXFMNJc047FHBc TFK3gj1bbw3XR6Te+JmMkEfc1tpF5ppJVjrTnmY1bXn21YHXOepHrAGj+1gXUXqol2CF 6mh/1xrre605E7KMxt/uk529aqK86T/+6YCSKOsPmbDsV+tEJCsYDKe5V0rz49OjmtY4 UnxwbILs5s3MYEhYO6LzLCOQSlp8jW42fF2pha/5rmUO/Y5uRLej8X0rERMGXKBrqgVP lmoncU8L3pr3tGRbVl12y7rG1+TW/kUxdvrMIOcqaRr4bm99G4/XPmwefHV117zXIRRS w8Jw== X-Gm-Message-State: AOJu0Yx4e6sycjr24TgJ5NV7g5esq5qwLdd6Wc/WrZ6RfArzCxZpQ6Lw rpSobTco1ZEG+Y9XRu6vmXZFPA== X-Google-Smtp-Source: AGHT+IE0rSvilLu9O36gttI/TkP4I00cCFIGMgIKwGw6O7fql+LFdULSrt81PWAZjYw7XwKOPHgFQA== X-Received: by 2002:a17:903:487:b0:1bd:ccee:8f26 with SMTP id jj7-20020a170903048700b001bdccee8f26mr1802973plb.15.1693400245360; Wed, 30 Aug 2023 05:57:25 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.19 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:25 -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 v2 1/6] maple_tree: Add two helpers Date: Wed, 30 Aug 2023 20:56:49 +0800 Message-Id: <20230830125654.21257-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-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 two helpers, which will be used later. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ee1ff0c59fd7..ef234cf02e3e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -165,6 +165,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); @@ -205,6 +210,11 @@ static unsigned int mas_mt_height(struct ma_state *mas) return mt_height(mas->tree); } =20 +static inline unsigned int mt_attr(struct maple_tree *mt) +{ + return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; +} + static inline enum maple_type mte_node_type(const struct maple_enode *entr= y) { return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & @@ -5520,7 +5530,7 @@ void mas_destroy(struct ma_state *mas) mt_free_bulk(count, (void __rcu **)&node->slot[1]); total -=3D count; } - kmem_cache_free(maple_node_cache, node); + mt_free_one(ma_mnode_ptr(node)); total--; } =20 --=20 2.20.1 From nobody Fri Dec 19 16:06:21 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 68059C83F01 for ; Wed, 30 Aug 2023 19:30:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239806AbjH3TaY (ORCPT ); Wed, 30 Aug 2023 15:30:24 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:48480 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244312AbjH3M5h (ORCPT ); Wed, 30 Aug 2023 08:57:37 -0400 Received: from mail-pl1-x629.google.com (mail-pl1-x629.google.com [IPv6:2607:f8b0:4864:20::629]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E6AF3CD2 for ; Wed, 30 Aug 2023 05:57:32 -0700 (PDT) Received: by mail-pl1-x629.google.com with SMTP id d9443c01a7336-1c0ecb9a075so23529295ad.2 for ; Wed, 30 Aug 2023 05:57:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400252; x=1694005052; darn=vger.kernel.org; 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=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=KweIXoJnWMLJ8OUXWAWhwDqHxJ4YL9vIQw/T006F7lfamNbqQZE9Mazy74A5aiG+09 f56KLeLkH7l0CqUWqApnlb79bsIgaSiAGxnTnPbI3UbHHKbjGs0A2r5HJ/yIAFKBBt34 0FV8gAQIHE+mtTDyvw2tLAv2/vIR3lDI2hrclPHzY7XaelCbg2cpS0C7tPHcm5YxNA4/ 5oGXC4d19e4b5MBHdVBTe6p3ENdfjJMC/gwP+k+dqdI806VGvTLONasvi4mFqaxquzsN A7Fsiu6sa3yjTaxf5JfPqtmNYsIKfpF3i9XeFI4oqz01YpEbxWxmOn6JVmRGvA2DT9/N ANxw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400252; x=1694005052; 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=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=fj0kJRLbDvmPoVtFymO8wo+XX8TXCBJU0p13HcF3vqCqKCIetBdJXtyWTmH1wCwNDB inMnV+4L2OoPZrZNYXl9uKnWOtz/KMJiPNcn82KJ4mhdlQFRCX/e30pnkTumHrJu1x9T HgXhPA38P9EtV7IvPIv92amLeba5qGUvwKGdpAt29i0C7yZmV58055E2EgbsrPXYePjY 7ccSi6ktBE71yhYmjLe94xNdwAJWA3GgWodfgUzuT5Kf3ACdHcr5IaLY+XrWvBGmFuLs qRChjKYiS/dkWWdmAkP5Kw7nsG8UMX3Z3Eg0Fn/CEBpU/+x78fyGaUSU18ePC2WnrgGg NG8A== X-Gm-Message-State: AOJu0YxsSQka1jhVtYTQ0LfCqRub8JprfFwrUrxLM/27Trglf0wFN5Xr ke2lg4S0iAHOihVUvTJcoSyivw== X-Google-Smtp-Source: AGHT+IFlsKJ4gsggMjq3Qups2gBw5dyyMz0AGXGO84i6jUNMN2vnjaDbpUxjVunPZt/9zXz+SwW1rQ== X-Received: by 2002:a17:902:edc7:b0:1bb:c5a9:6b26 with SMTP id q7-20020a170902edc700b001bbc5a96b26mr1834665plk.5.1693400252383; Wed, 30 Aug 2023 05:57:32 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.26 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:32 -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 v2 2/6] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Wed, 30 Aug 2023 20:56:50 +0800 Message-Id: <20230830125654.21257-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-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 mtree_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 mtree_dup() is that mtree_dup() handles locks internally. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 265 +++++++++++++++++++++++++++++++++++++ 2 files changed, 268 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e41c70ac7744..44fe8a57ecbd 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 mtree_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 ef234cf02e3e..8f841682269c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6370,6 +6370,271 @@ void *mtree_erase(struct maple_tree *mt, unsigned l= ong index) } EXPORT_SYMBOL(mtree_erase); =20 +/* + * mas_dup_free() - Free a half-constructed tree. + * @mas: Points to the last node of the half-constructed tree. + * + * This function frees all nodes starting from @mas->node in the reverse o= rder + * of mas_dup_build(). There is no need to hold the source tree lock at th= is + * time. + */ +static void mas_dup_free(struct ma_state *mas) +{ + struct maple_node *node; + enum maple_type type; + void __rcu **slots; + unsigned char count, i; + + /* Maybe the first node allocation failed. */ + if (!mas->node) + return; + + while (!mte_is_root(mas->node)) { + mas_ascend(mas); + + if (mas->offset) { + mas->offset--; + do { + mas_descend(mas); + mas->offset =3D mas_data_end(mas); + } while (!mte_is_leaf(mas->node)); + + mas_ascend(mas); + } + + node =3D mte_to_node(mas->node); + type =3D mte_node_type(mas->node); + slots =3D (void **)ma_slots(node, type); + count =3D mas_data_end(mas) + 1; + for (i =3D 0; i < count; i++) + ((unsigned long *)slots)[i] &=3D ~MAPLE_NODE_MASK; + + mt_free_bulk(count, slots); + } + + node =3D mte_to_node(mas->node); + mt_free_one(node); +} + +/* + * mas_copy_node() - Copy a maple node and allocate child nodes. + * @mas: Points to the source node. + * @new_mas: Points to the new node. + * @parent: The parent node of the new node. + * @gfp: The GFP_FLAGS to use for allocations. + * + * Copy @mas->node to @new_mas->node, set @parent to be the parent of + * @new_mas->node and allocate new child nodes for @new_mas->node. + * If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *ne= w_mas, + struct maple_node *parent, gfp_t gfp) +{ + struct maple_node *node =3D mte_to_node(mas->node); + struct maple_node *new_node =3D mte_to_node(new_mas->node); + enum maple_type type; + unsigned long val; + unsigned char request, count, i; + void __rcu **slots; + void __rcu **new_slots; + + /* Copy the node completely. */ + memcpy(new_node, node, sizeof(struct maple_node)); + + /* Update the parent node pointer. */ + if (unlikely(ma_is_root(node))) + val =3D MA_ROOT_PARENT; + else + val =3D (unsigned long)node->parent & MAPLE_NODE_MASK; + + new_node->parent =3D ma_parent_ptr(val | (unsigned long)parent); + + if (mte_is_leaf(mas->node)) + return; + + /* Allocate memory for child nodes. */ + type =3D mte_node_type(mas->node); + new_slots =3D ma_slots(new_node, type); + request =3D mas_data_end(mas) + 1; + count =3D mt_alloc_bulk(gfp, request, new_slots); + if (unlikely(count < request)) { + if (count) + mt_free_bulk(count, new_slots); + mas_set_err(mas, -ENOMEM); + return; + } + + /* Restore node type information in slots. */ + slots =3D ma_slots(node, type); + for (i =3D 0; i < count; i++) + ((unsigned long *)new_slots)[i] |=3D + ((unsigned long)mt_slot_locked(mas->tree, slots, i) & + MAPLE_NODE_MASK); +} + +/* + * mas_dup_build() - Build a new maple tree from a source tree + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function builds a new tree in DFS preorder. If the memory allocati= on + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points = to the + * last node. mas_dup_free() will free the half-constructed tree. + * + * Note that the attributes of the two trees must be exactly the same, and= the + * new tree must be empty, otherwise -EINVAL will be returned. + */ +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *ne= w_mas, + gfp_t gfp) +{ + struct maple_node *node, *parent; + struct maple_enode *root; + enum maple_type type; + + if (unlikely(mt_attr(mas->tree) !=3D mt_attr(new_mas->tree)) || + unlikely(!mtree_empty(new_mas->tree))) { + mas_set_err(mas, -EINVAL); + return; + } + + mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) { + /* + * The attributes of the two trees must be the same before this. + * The following assignment makes them the same height. + */ + new_mas->tree->ma_flags =3D mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, mas->tree->ma_root); + return; + } + + node =3D mt_alloc_one(gfp); + if (!node) { + new_mas->node =3D NULL; + mas_set_err(mas, -ENOMEM); + return; + } + + type =3D mte_node_type(mas->node); + root =3D mt_mk_node(node, type); + new_mas->node =3D root; + new_mas->min =3D 0; + new_mas->max =3D ULONG_MAX; + parent =3D ma_mnode_ptr(new_mas->tree); + + while (1) { + mas_copy_node(mas, new_mas, parent, gfp); + + if (unlikely(mas_is_err(mas))) + return; + + /* Once we reach a leaf, we need to ascend, or end the loop. */ + if (mte_is_leaf(mas->node)) { + if (mas->max =3D=3D ULONG_MAX) { + new_mas->tree->ma_flags =3D mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, + mte_mk_root(root)); + break; + } + + do { + /* + * Must not at the root node, because we've + * already end the loop when we reach the last + * leaf. + */ + mas_ascend(mas); + mas_ascend(new_mas); + } while (mas->offset =3D=3D mas_data_end(mas)); + + mas->offset++; + new_mas->offset++; + } + + mas_descend(mas); + parent =3D mte_to_node(new_mas->node); + mas_descend(new_mas); + mas->offset =3D 0; + new_mas->offset =3D 0; + } +} + +/** + * __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 ensure that the attributes of the source tree and the= new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * Note that the user needs to manually lock the source tree and the new t= ree. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL= If + * the attributes of the two trees are different or the new tree is not an= empty + * tree. + */ +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret =3D 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_dup_build(&mas, &new_mas, gfp); + + if (unlikely(mas_is_err(&mas))) { + ret =3D xa_err(mas.node); + if (ret =3D=3D -ENOMEM) + mas_dup_free(&new_mas); + } + + return ret; +} +EXPORT_SYMBOL(__mt_dup); + +/** + * mtree_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 ensure that the attributes of the source tree and the= new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL= If + * the attributes of the two trees are different or the new tree is not an= empty + * tree. + */ +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret =3D 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_lock(&new_mas); + mas_lock(&mas); + + mas_dup_build(&mas, &new_mas, gfp); + mas_unlock(&mas); + + if (unlikely(mas_is_err(&mas))) { + ret =3D xa_err(mas.node); + if (ret =3D=3D -ENOMEM) + mas_dup_free(&new_mas); + } + + mas_unlock(&new_mas); + + return ret; +} +EXPORT_SYMBOL(mtree_dup); + /** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree --=20 2.20.1 From nobody Fri Dec 19 16:06:21 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 1FC41C83F19 for ; Wed, 30 Aug 2023 18:53:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S244509AbjH3SvE (ORCPT ); Wed, 30 Aug 2023 14:51:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60218 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244323AbjH3M6F (ORCPT ); Wed, 30 Aug 2023 08:58:05 -0400 Received: from mail-pl1-x635.google.com (mail-pl1-x635.google.com [IPv6:2607:f8b0:4864:20::635]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2590CB9 for ; Wed, 30 Aug 2023 05:57:40 -0700 (PDT) Received: by mail-pl1-x635.google.com with SMTP id d9443c01a7336-1bf55a81eeaso29804465ad.0 for ; Wed, 30 Aug 2023 05:57:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400259; x=1694005059; darn=vger.kernel.org; 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=q/ZpDcXIY2uplQWCw9dEjDeDQjyl2gwHXqRgJ65MCOs=; b=NL34znoJJEiETTAsUKZzZo7lJr56vtSsAkuGYwO7VTXqqfUAEsZ7xcW/Mxq8SCgwo2 T7RannTuzAz2HsaTMPf71x6qNvVhzPGdWMp/bz1d+hZdLQYCuIlSY+/ysYdncgnBX7tB UyLYFMtUHRl2ZqwE7kyFPUx+31PzYsesaPMCqyUvzvHpEtj38k7H/1kLZ0pFa7P+cGd7 CbhDhYUC1+uXXTFgtRxdgPoRBQGB1+JfuRJfYxEuanhsSFnAewiBcvuod/CRg5y9DyrY eBwAzJCwfuL2tbrC4X4NywXeSIXbv84A1EvyKpWF+KscYT8iQ5EmuLt2mAnjDay3A5nY DmRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400259; x=1694005059; 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=q/ZpDcXIY2uplQWCw9dEjDeDQjyl2gwHXqRgJ65MCOs=; b=TlVlR4S7HvfmetmsFw0pdhrvoSn5YFNgpNzoU6OLYQrGme9V+qQlNqj25hCjSOkmXW GrbhsGt3+v4XNxZ4kUYNvu7n7wMPF4Voh6p4o8qe8EwkNT1gffj9vyOz6r9QYtht145/ XKPqT8ulhKEINsAW3itmCBRUVannyiGBC9K+8iWfclMjNU+93Qfp1/ObIomF/Zkle2BX gVEB9Q6fA29kVUnMkf+OHNlxf/noMh4benFotaPNEG9855+dQS2Wp6WC0AAbTZpUdPIg bCvfeEpB5pprj5GuP4NJW2yILB74/gxfrzmAjKW4mDXECeAzygOcggGzu6gR6zlDRIbG W/WQ== X-Gm-Message-State: AOJu0YxAkxm2RnLgW3szlg3Ea6mxZ39TX49cx/6kdls8Ue5ik+tlseOF CvgcayCTCPI9zf737pa7nh+HYQ== X-Google-Smtp-Source: AGHT+IGJ6wl3h1zU1EZ8Va876ePXGOkXhL6Bg48jGTnNAf5hacvqb0Z714nNSA6Bq7dqCI/W67lR4Q== X-Received: by 2002:a17:902:ee84:b0:1bf:63c0:ae79 with SMTP id a4-20020a170902ee8400b001bf63c0ae79mr1769233pld.33.1693400259641; Wed, 30 Aug 2023 05:57:39 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.32 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:39 -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 v2 3/6] maple_tree: Add test for mtree_dup() Date: Wed, 30 Aug 2023 20:56:51 +0800 Message-Id: <20230830125654.21257-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-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 mtree_dup(). Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 344 +++++++++++++++++++++++++++++++ 1 file changed, 344 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/ma= ple.c index e5da1cad70ba..38455916331e 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,346 @@ 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 __init void mas_subtree_max_range(struct ma_state *mas) +{ + unsigned long limit =3D mas->max; + MA_STATE(newmas, mas->tree, 0, 0); + void *entry; + + mas_for_each(mas, entry, limit) { + if (mas->last - mas->index >=3D + newmas.last - newmas.index) { + newmas =3D *mas; + } + } + + *mas =3D newmas; +} + +/* + * build_full_tree() - Build a full tree. + * @mt: The tree to build. + * @flags: Use @flags to build the tree. + * @height: The height of the tree to build. + * + * Build a tree with full leaf nodes and internal nodes. Note that the hei= ght + * should not exceed 3, otherwise it will take a long time to build. + * Return: zero if the build is successful, non-zero if it fails. + */ +static __init int build_full_tree(struct maple_tree *mt, unsigned int flag= s, + int height) +{ + MA_STATE(mas, mt, 0, 0); + unsigned long step; + int ret =3D 0, cnt =3D 1; + enum maple_type type; + + mt_init_flags(mt, flags); + mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); + + mtree_lock(mt); + + while (1) { + mas_set(&mas, 0); + if (mt_height(mt) < height) { + mas.max =3D ULONG_MAX; + goto store; + } + + while (1) { + mas_dfs_preorder(&mas); + if (mas_is_none(&mas)) + goto unlock; + + type =3D mte_node_type(mas.node); + if (mas_data_end(&mas) + 1 < mt_slots[type]) { + mas_set(&mas, mas.min); + goto store; + } + } +store: + mas_subtree_max_range(&mas); + step =3D mas.last - mas.index; + if (step < 1) { + ret =3D -1; + goto unlock; + } + + step /=3D 2; + mas.last =3D mas.index + step; + mas_store_gfp(&mas, xa_mk_value(5), + GFP_KERNEL); + ++cnt; + } +unlock: + mtree_unlock(mt); + + MT_BUG_ON(mt, mt_height(mt) !=3D height); + /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ + return ret; +} + +static noinline void __init check_mtree_dup(struct maple_tree *mt) +{ + DEFINE_MTREE(new); + int i, j, ret, count =3D 0; + unsigned int rand_seed =3D 17, rand; + + /* store a value at [0, 0] */ + mt_init_flags(&tree, 0); + mtree_store_range(&tree, 0, 0, xa_mk_value(0), GFP_KERNEL); + ret =3D mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + + /* The two trees have different attributes. */ + mt_init_flags(&tree, 0); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + ret =3D mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret !=3D -EINVAL); + mtree_destroy(&tree); + mtree_destroy(&new); + + /* The new tree is not empty */ + mt_init_flags(&tree, 0); + mt_init_flags(&new, 0); + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); + ret =3D mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret !=3D -EINVAL); + mtree_destroy(&tree); + mtree_destroy(&new); + + /* Test for duplicating full trees. */ + for (i =3D 1; i <=3D 3; i++) { + ret =3D build_full_tree(&tree, 0, i); + MT_BUG_ON(&tree, ret); + mt_init_flags(&new, 0); + + ret =3D mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + } + + for (i =3D 1; i <=3D 3; i++) { + ret =3D build_full_tree(&tree, MT_FLAGS_ALLOC_RANGE, i); + MT_BUG_ON(&tree, ret); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + + ret =3D mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + } + + /* Test for normal duplicating. */ + for (i =3D 0; i < 1000; i +=3D 3) { + if (i & 1) { + mt_init_flags(&tree, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, 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 mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + 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); + mt_init_flags(&new, 0); + } else { + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, 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); + } + /* + * The rand() library function is not used, so we can generate + * the same random numbers on any platform. + */ + rand_seed =3D rand_seed * 1103515245 + 12345; + rand =3D rand_seed / 65536 % 128; + mt_set_non_kernel(rand); + + ret =3D mtree_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("mtree_dup() fail %d times\n", count); */ + BUG_ON(!count); +} + extern void test_kmem_cache_bulk(void); =20 void farmer_tests(void) @@ -35904,6 +36244,10 @@ void farmer_tests(void) check_null_expand(&tree); mtree_destroy(&tree); =20 + mt_init_flags(&tree, 0); + check_mtree_dup(&tree); + mtree_destroy(&tree); + /* RCU testing */ mt_init_flags(&tree, 0); check_erase_testset(&tree); --=20 2.20.1 From nobody Fri Dec 19 16:06:21 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 8BA01C6FA8F for ; Wed, 30 Aug 2023 19:06:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232664AbjH3TG2 (ORCPT ); Wed, 30 Aug 2023 15:06:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60238 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244326AbjH3M6M (ORCPT ); Wed, 30 Aug 2023 08:58:12 -0400 Received: from mail-pl1-x630.google.com (mail-pl1-x630.google.com [IPv6:2607:f8b0:4864:20::630]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6A288132 for ; Wed, 30 Aug 2023 05:57:46 -0700 (PDT) Received: by mail-pl1-x630.google.com with SMTP id d9443c01a7336-1bc63ef9959so41955175ad.2 for ; Wed, 30 Aug 2023 05:57:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400266; x=1694005066; darn=vger.kernel.org; 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=2nBO87JODOc2vxfEDdYbEmz2onn6zs2zxUKCCOpJdk0=; b=ZrmpUQzKwPGg4ygFxX3/Sd2+3b7Vd3uIX43oPFzWowCcl8lQXHkDPyQ5MNNs9T2YgJ /TZE6L4kvi8wF8DOsbcfDENR/8yx76nsIUbdA1gtbC+LPgaADGUa2F+/M/V+ffta8BfE Hg+RPW6+dih/PTd9oIrKn9e9LuAGIKCGOAPzmRMBkMN9HC8hq7d+DW8jhn/Yh1NkOKYR yptavTQhuM7k0tqhR2Lb8YCALxsCo4KiXKdVk0s52iNLpB3GQeswP6oS0YjqP1Pq42Sr vyMLCjQuYnkU208i0gqNzhw9hNN5s2qBc2qJqwN3aJ9Gz6qZW+O/mjLDmb+6nvhKjtd2 K7Cg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400266; x=1694005066; 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=2nBO87JODOc2vxfEDdYbEmz2onn6zs2zxUKCCOpJdk0=; b=ZKWITEKH7/13DDob42ERkAK5a1Dr97FHH+4MmwybtzX3CqLz8BOv7KI8bjl+DHIB3a SLS0+JjS7MHWUMjKTc5n8WGy81kbGiJoFcSN8t5jnrpWSHomQ3hbxINnneKNduqPt9HG vMnUIKm+FzrdFpCkYVz5kmzyplMEGiOCIxwEYRR9SHpgBLbMj7Upuw/8eZDCQ22FVu9v N5GhwCDjMuVPIDPX2cCGnfSLPnPexih6vZCiaVU1+jBBTH8lYllS8xY55nCRETh8/gEK W/G34Bro5WxbGRpfjfEsWQr67MVJQOfIVb/jcIukKeLHwx6EkL6xTIuoKbnV31twKuLP K3vQ== X-Gm-Message-State: AOJu0YyrGpHydy11rpua9BZPXpTNvU5ZtE2agNTjBRGnN2bNFzrj1xej TIvAT6zffn9wmBLq/tJVennl3w== X-Google-Smtp-Source: AGHT+IGx3EmrDiZTTIfJpOeK4JOagyqHaEyqo+fM7q0DuUUO076LoLX7sVQJgZT4uYkTB/BqJlAAiQ== X-Received: by 2002:a17:903:268a:b0:1b8:7e53:704 with SMTP id jf10-20020a170903268a00b001b87e530704mr1893310plb.27.1693400265985; Wed, 30 Aug 2023 05:57:45 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.40 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:45 -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 v2 4/6] maple_tree: Skip other tests when BENCH is enabled Date: Wed, 30 Aug 2023 20:56:52 +0800 Message-Id: <20230830125654.21257-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-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 38455916331e..57f153b8bf4b 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36282,7 +36282,9 @@ void farmer_tests(void) =20 void maple_tree_tests(void) { +#if !defined(BENCH) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } --=20 2.20.1 From nobody Fri Dec 19 16:06:21 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 0BD19C83F2A for ; Wed, 30 Aug 2023 19:03:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S239318AbjH3TAb (ORCPT ); Wed, 30 Aug 2023 15:00:31 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38424 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244328AbjH3M6T (ORCPT ); Wed, 30 Aug 2023 08:58:19 -0400 Received: from mail-pl1-x633.google.com (mail-pl1-x633.google.com [IPv6:2607:f8b0:4864:20::633]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 88DB6193 for ; Wed, 30 Aug 2023 05:57:52 -0700 (PDT) Received: by mail-pl1-x633.google.com with SMTP id d9443c01a7336-1bf1935f6c2so6192005ad.1 for ; Wed, 30 Aug 2023 05:57:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400272; x=1694005072; darn=vger.kernel.org; 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=likGmWzdcl79JyC0G273JC8fCg1Z1MuweBHmHeu5k34=; b=Ff+7Y1SRwwlAHeDnqTlv4FjDGlid7oBt2NqKoj7YgCeRiMZLdZWmnHVF0a0MEgrhzm z18CNFlUF+D3HMsi8f9EpufmKyPcapSQaR96OfPKapuDvtRM0Xkz8wPxr80S251EiksE WlIZp2NNwIphwQHxJ5etCxp2/LlkA8CFpULltM4XvXkaMcXXaeoUfw21dtRB0MtYpuq6 p7DNcA8gXF8do43AWiK989vsfyT04mfqrknCXr8c9Dt23gSZ7GPTnTYJIr9j1OpIu4Vo 2+7oR9NlMezOmbnP2nfC2JOmYC6uMr3CMfHygP9Gv1jL0RtykQTJ+aWG14A30wdXWzWl 0IzA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400272; x=1694005072; 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=likGmWzdcl79JyC0G273JC8fCg1Z1MuweBHmHeu5k34=; b=buw8ES7koXIMWKwN61c3Bbt+OWns+5dPaWs7jT8xZWISFFBGasEmSLmvoweaEsihdd f6A3BYbqyZbuWqeTUtnbPb9LxGrL6vSYyEqWnCalzzvFWuGuOtWoRs1LmpOU8y3XFSty iP/YYaiVDaXIE/rEFpep+HpfTsZTFYPQiv+cp5mnsifSGB1GV2bOtd9SwH523hpHs/la 8F1ScXne6VoU9Z5XfJLzjy+UtCAMsVEhusHrRmwrRjTYu9O1ciQpF1n79PNnS30uE1mx 4q5s+6yFr7lGOApA1yuHEhe6CxKzYmshmvimSvRynBm3NOf5xu4a8fa8d4i2FJruSJA+ SEXA== X-Gm-Message-State: AOJu0YxVETPRtv1jfAZcEtUAu0Rezq0vcW16+hu4kj5iB9s1C/RPuNEP V4IKGLp60b6WXsreLG0LfFWgRg== X-Google-Smtp-Source: AGHT+IHEZW1hekFijghmb4eDJa5CJeFIwOgrvu16t1pBzdglsm2NfGWuHdAFed9GN5ly19C8PHDQDQ== X-Received: by 2002:a17:903:228f:b0:1bc:4415:3c1 with SMTP id b15-20020a170903228f00b001bc441503c1mr8693507plh.7.1693400272035; Wed, 30 Aug 2023 05:57:52 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.46 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:51 -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 v2 5/6] maple_tree: Update check_forking() and bench_forking() Date: Wed, 30 Aug 2023 20:56:53 +0800 Message-Id: <20230830125654.21257-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-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. Also increased the number of VMAs, because the new way is faster. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 61 +++++++++++++++++++++---------------------- 1 file changed, 30 insertions(+), 31 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0ec0c6a7c0b5..72fba7cce148 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1837,36 +1837,37 @@ static noinline void __init check_forking(struct ma= ple_tree *mt) { =20 struct maple_tree newmt; - int i, nr_entries =3D 134; + int i, nr_entries =3D 300, ret; void *val; MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + + mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); =20 for (i =3D 0; i <=3D nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, 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_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) { mas_store(&newmas, val); } - rcu_read_unlock(); - mas_destroy(&newmas); + + mas_unlock(&mas); mas_unlock(&newmas); + + mas_destroy(&newmas); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); @@ -1974,12 +1975,11 @@ static noinline void __init check_mas_store_gfp(str= uct 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 300, nr_fork =3D 80000, ret; void *val; MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); =20 for (i =3D 0; i <=3D nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, @@ -1988,25 +1988,24 @@ static noinline void __init bench_forking(struct ma= ple_tree *mt) 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_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) { mas_store(&newmas, val); } - mas_destroy(&newmas); + + mas_unlock(&mas); mas_unlock(&newmas); - rcu_read_unlock(); + + mas_destroy(&newmas); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); --=20 2.20.1 From nobody Fri Dec 19 16:06:21 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 4B46DC83F1F for ; Wed, 30 Aug 2023 19:05:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S236018AbjH3TFM (ORCPT ); Wed, 30 Aug 2023 15:05:12 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54222 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S244322AbjH3M6C (ORCPT ); Wed, 30 Aug 2023 08:58:02 -0400 Received: from mail-pl1-x634.google.com (mail-pl1-x634.google.com [IPv6:2607:f8b0:4864:20::634]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0413CCC5 for ; Wed, 30 Aug 2023 05:57:59 -0700 (PDT) Received: by mail-pl1-x634.google.com with SMTP id d9443c01a7336-1c1e3a4a06fso20601765ad.3 for ; Wed, 30 Aug 2023 05:57:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400278; x=1694005078; darn=vger.kernel.org; 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=0yWpUOFFGV0pFtikzJZ55MStl9p8vL9hqNAbNokJEAE=; b=VEn31CjsPWihCIC3/0e4qz3VNlKzPvkl/Rqp1B5PPv9Mang1f30xJT/J3yRfE6yh2B 3wx3t5kE1JTFKTS5dpc9Z3Bb0wdi9PlZkmB2Oul+nc5ERxNubeKn4yEZ4OBR86XbKsF4 AeF+DuYzuBNmqEUFdmmqQA9++4JI7tQ3/YacwUS3Y0Mx3X5PRwYeZluglypRvTD8FJgZ Xu0aCM8e8lo5nLJSv/TfoDa/ZXM4nY56TcPhSMj6LrO1qPW6QrwBTvKHxwSb96AN4G70 ayD1C2XoG/lD38I+4F8cskDKoKnAJ3v+/4Tsd3gzalj/b1/mO9W9XMIhLl45+yk412lA AUyQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400278; x=1694005078; 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=0yWpUOFFGV0pFtikzJZ55MStl9p8vL9hqNAbNokJEAE=; b=hkfDefnHassc0VONJoezamxT3p+atUxvxOzSqix16szsDGG7w96/3bpDSEGzzl8qYR Zq+M736jYYCRKkwJe0DZTWQUQ9BJ2kl6sjQcHfUI2lYWTYp70fbUCgWHkDvlfpz9DdGq qk7HLKB7ffsQzXzRLz90xcgmJgtNprCVoP3dh++hA9t4X+C2hjfEULMtDfbwz7Jr0+Mp FSxYeDgCGeOUOOwze9tksu2julq8IvozrVuW+EZE7tPkUfAH7D+IKhnL7d03rbJjRC8m FqtVPWDvXkdEQ1/sRJeWZVXONbc7AdhgiSuZGP00xoQq8R8zCqS9mf87LlcnESnvtmJ5 WghA== X-Gm-Message-State: AOJu0YzpKAi5we/GLl8LWMmOg2cp+QRwoFOikfV8Wn10mApUWxPjDPXo TUYHouZXxyprLvalsqw1Jy7L3w== X-Google-Smtp-Source: AGHT+IHrE4rTvkXO7RwqgnTEvxw+lDK+ANzha4IBQF+qFVxQo+OdsPaqgZdwuRA69Q5Iw9LfoqglQw== X-Received: by 2002:a17:902:da8c:b0:1bf:78d:5cde with SMTP id j12-20020a170902da8c00b001bf078d5cdemr1986513plx.59.1693400278469; Wed, 30 Aug 2023 05:57:58 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.52 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:58 -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 v2 6/6] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Wed, 30 Aug 2023 20:56:54 +0800 Message-Id: <20230830125654.21257-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-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. The optimization effect is proportional to the number of VMAs. There is a "spawn" in byte-unixbench[1], which can be used to test the performance of fork(). I modified it slightly to make it work with different number of VMAs. Below are the test numbers. There are 21 VMAs by default. The first row indicates the number of added VMAs. The following two lines are the number of fork() calls every 10 seconds. These numbers are different from the test results in v1 because this time the benchmark is bound to a CPU. This way the numbers are more stable. Increment of VMAs: 0 100 200 400 800 1600 3200 = 6400 6.5.0-next-20230829: 111878 75531 53683 35282 20741 11317 6110 = 3158 Apply this patchset: 114531 85420 64541 44592 28660 16371 9038 = 4831 +2.37% +13.09% +20.23% +26.39% +38.18% +44.66% +47.92%= +52.98% [1] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang --- kernel/fork.c | 34 ++++++++++++++++++++++++++-------- mm/mmap.c | 14 ++++++++++++-- 2 files changed, 38 insertions(+), 10 deletions(-) diff --git a/kernel/fork.c b/kernel/fork.c index 3b6d20dfb9a8..e6299adefbd8 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,39 @@ 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_store(&vmi.mas, XA_ZERO_ENTRY); + goto loop_out; + } + continue; } charge =3D 0; @@ -750,8 +771,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_store(&vmi.mas, tmp); =20 mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -778,8 +798,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 b56a7f0c9f85..dfc6881be81c 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3196,7 +3196,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; @@ -3234,7 +3238,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