From nobody Tue Dec 16 21:28:38 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 D9797C25B6E for ; Fri, 27 Oct 2023 03:39:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345225AbjJ0Djf (ORCPT ); Thu, 26 Oct 2023 23:39:35 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57152 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1345248AbjJ0Djc (ORCPT ); Thu, 26 Oct 2023 23:39:32 -0400 Received: from mail-pg1-x533.google.com (mail-pg1-x533.google.com [IPv6:2607:f8b0:4864:20::533]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 584D9198 for ; Thu, 26 Oct 2023 20:39:07 -0700 (PDT) Received: by mail-pg1-x533.google.com with SMTP id 41be03b00d2f7-5aa7172bafdso1326470a12.1 for ; Thu, 26 Oct 2023 20:39:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377947; x=1698982747; 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=tMjhw76FECkOO5zRdU6IjOHgP+3TMOQK2mZ19zJdvuE=; b=AuoT6Ymrit+ZplwF9h5pZgz5X2ydjFt5NqEFhn5MYDY6PFkj4TMwjfLxY/hqZRqWJL n+QeVjvAwwIMabb8Aof754791skcrsrIgCTxK5ZO+hn1PXRY7hhhhveeEtDOjyrk5zxn cwucZRpdPKVx3VcrxovDJnbLg0Y3Xe02GJPoiUiyi1D5zU+DY6WRDNUxm77DlBlnIK52 4RYDp/SKZ8O7jkKsUB7R4EpQjmXoP+yEm5gN97k878r/SkQebOdzl3bRAfvfOrqQ0Egd uorpPXUIZLygh/M1AVJY1Aq+EDMZUOljrEckiyiI7T53fJlpeNKuMQ187ycHOFN2bF4M 7RAw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377947; x=1698982747; 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=tMjhw76FECkOO5zRdU6IjOHgP+3TMOQK2mZ19zJdvuE=; b=QEcIT6fk79OJtTTGEXU9MuT25a1//MgcEdWtl+EyYe7r2sShLeCCL1LxvBWaaA/lhL 9i82TMJUARkf90UJxUIt4djVOsvP3nCBMh+GFM0wOLD83UGUIsvqg5tcEONf/bFrwXwt UQuxo0atA9ZgftLKeYMkfadBJUv7e+VtYfv1pLGy8w7yXnbN5l/N3B0HLeT1VNleAw/7 aZDuv/Ux03X8RjIQ++E1r6cRQLTLgF16EixYME+9z0JKgGRr8cvmThPAOdoecc/hyn4q J8xttJWLCCnekIhgSAG//8OC4YFhxJrYb+bWVZ3crsopM/B+2/9nKVoBMf6UE0VveuXK X77g== X-Gm-Message-State: AOJu0YzWYBfp0VIaE9wj7nq2hsF8noKuhO4Pw+Cd41UPKS/zqMBLeOEd HRxVSvWInzBTxCRy9Jc4KHvyhw== X-Google-Smtp-Source: AGHT+IE+9o1D6mC/tBfbhMEHSHxO+4OKy9VNzv+o8iR1rqr4G54ZqAEfL4OOVueaw3fQnMy76xQeKg== X-Received: by 2002:a05:6a21:3d89:b0:17b:3cd6:b1bc with SMTP id bj9-20020a056a213d8900b0017b3cd6b1bcmr1812360pzc.14.1698377946837; Thu, 26 Oct 2023 20:39:06 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.38.59 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39: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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 01/10] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Fri, 27 Oct 2023 11:38:36 +0800 Message-Id: <20231027033845.90608-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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: 1. mt_free_one(), used to free a maple node. 2. mt_attr(), used to obtain the attributes of maple tree. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- 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 bb24d84a4922..ca7039633844 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) & @@ -5573,7 +5583,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 Tue Dec 16 21:28:38 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 5D458C25B48 for ; Fri, 27 Oct 2023 03:39:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345246AbjJ0DjS (ORCPT ); Thu, 26 Oct 2023 23:39:18 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57188 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1345225AbjJ0DjR (ORCPT ); Thu, 26 Oct 2023 23:39:17 -0400 Received: from mail-pg1-x52b.google.com (mail-pg1-x52b.google.com [IPv6:2607:f8b0:4864:20::52b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2FEA41B4 for ; Thu, 26 Oct 2023 20:39:15 -0700 (PDT) Received: by mail-pg1-x52b.google.com with SMTP id 41be03b00d2f7-578b407045bso1344995a12.0 for ; Thu, 26 Oct 2023 20:39:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377954; x=1698982754; 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=W3VhzpPT4L+mg3QuUru0Nd/vnRDIbmeOsA1YFHm0EaI=; b=G4ESRtUhL5ol07GTs/eqldGlm81dI3Q8VHXHAFYKMuHcpYoceNCPK3kRb2T0UL6hMi C33MG5JUA8eHtM9EtQ6lHygG7qM9S2tmaUP6LQkqzESLWjNR7pEQQBQ9wJb47yxazU7f qixDqGRMLR/CondHUPZ9HFHcqvE9mISwp/xMfjgsuNIibBQLIBYt56aDjEvb2dFpo5C4 QCP/uqaMsydNF80AaoHnYppXHl5kWhYqph739nhSe3Xw36ioAdrAUxYBvfot6e1ENhgZ 18iZ8Ofe8dwXFp+wCZ3Kp6lf6wCGtkSG3rCppqgh5rNQBXb0iHeXXhnM3YLnX5gL3o5G lHiA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377954; x=1698982754; 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=W3VhzpPT4L+mg3QuUru0Nd/vnRDIbmeOsA1YFHm0EaI=; b=FfJFBun2TklhcuF4+sLivyUA754zpkryB29zIEM/OVT2CwD8xc/fw0yrypeL9TXOFd AQpY0FWV9f7SjiZdInqmH1LNLqlk+XtjJygt5kMtG8etABcI0vGptxpk/0GF0WulcPIQ 0JdA+2e9U2Hg4jtQe2r7HiIzVffX+oLJWPy2TDbI7dAElUTwhXD2bttfJ1YMvvnl+Hly HHmaGyu4BKjBvBDkxhVFtBWr4hnbfXCgcBjmMOmqbbH8d7ypU0YY4oTL6FCgCN7i8UWh svrnzjhncjSyuJzmLDf4zCw2zs5VdSuBJb81AEewmsB94cajDF5d9agbuMmWH+CsnNIb 1e0g== X-Gm-Message-State: AOJu0YxP8jw7XO1crrmIVuXNNDLyitKVgem3UtK9FrQ+fKY6j+v63pC4 F9b/FKmOT4C2DXKvgInUFTlgYQ== X-Google-Smtp-Source: AGHT+IErUxQpQyE6ZDI+WeBZM1BwVdK0VivW/g4FmIFgZocyNbqWFR+q60M1qzJpJ7pOns/5IgyeQA== X-Received: by 2002:a17:90a:bf04:b0:27f:f9e5:b8d6 with SMTP id c4-20020a17090abf0400b0027ff9e5b8d6mr1386794pjs.41.1698377954626; Thu, 26 Oct 2023 20:39:14 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.07 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:14 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 02/10] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Fri, 27 Oct 2023 11:38:37 +0800 Message-Id: <20231027033845.90608-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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" In some cases, nested locks may be needed, so {mtree,mas}_lock_nested is introduced. For example, when duplicating maple tree, we need to hold the locks of two trees, in which case nested locks are needed. At the same time, add the definition of spin_lock_nested() in tools for testing. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- include/linux/maple_tree.h | 4 ++++ tools/include/linux/spinlock.h | 1 + 2 files changed, 5 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index d01e850b570f..f91dbc7fe091 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -256,6 +256,8 @@ struct maple_tree { struct maple_tree name =3D MTREE_INIT(name, 0) =20 #define mtree_lock(mt) spin_lock((&(mt)->ma_lock)) +#define mtree_lock_nested(mas, subclass) \ + spin_lock_nested((&(mt)->ma_lock), subclass) #define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock)) =20 /* @@ -406,6 +408,8 @@ struct ma_wr_state { }; =20 #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) +#define mas_lock_nested(mas, subclass) \ + spin_lock_nested(&((mas)->tree->ma_lock), subclass) #define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock)) =20 =20 diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h index 622266b197d0..a6cdf25b6b9d 100644 --- a/tools/include/linux/spinlock.h +++ b/tools/include/linux/spinlock.h @@ -11,6 +11,7 @@ #define spin_lock_init(x) pthread_mutex_init(x, NULL) =20 #define spin_lock(x) pthread_mutex_lock(x) +#define spin_lock_nested(x, subclass) pthread_mutex_lock(x) #define spin_unlock(x) pthread_mutex_unlock(x) #define spin_lock_bh(x) pthread_mutex_lock(x) #define spin_unlock_bh(x) pthread_mutex_unlock(x) --=20 2.20.1 From nobody Tue Dec 16 21:28:39 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 259EBC25B48 for ; Fri, 27 Oct 2023 03:40:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345332AbjJ0DkG (ORCPT ); Thu, 26 Oct 2023 23:40:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37188 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1345326AbjJ0Dju (ORCPT ); Thu, 26 Oct 2023 23:39:50 -0400 Received: from mail-pg1-x532.google.com (mail-pg1-x532.google.com [IPv6:2607:f8b0:4864:20::532]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 401FE1B2 for ; Thu, 26 Oct 2023 20:39:23 -0700 (PDT) Received: by mail-pg1-x532.google.com with SMTP id 41be03b00d2f7-578b407045bso1345053a12.0 for ; Thu, 26 Oct 2023 20:39:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377962; x=1698982762; 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=/zo8HpYmb+yYCFm1lxy89mJtImc6tDFF4y7FplR5LLY=; b=J+6JMEgCtHFIW6LBDyZW/mp7LrstRK40D2X5RJ6ceVZmWOToXF6FXyYXpL0maFBsZl ZCBfAC4dSa7ij1Dn+yoK03GT9jp7V55laUXPYj+lvQim+rbrJS9qibfHXsCr4lSVLm0B +QwPTrVPf62CVATbiY6ZEIBaDIASQFVZ/TWkL4pbQbEjtj4qVHjOkLJw2oKVhdoFYfYa KqRtxLPwY7rIUwsf8CW2VC8BxU6lLIqtv0e8E98ggBtWPkIY89/a5kbrG2zLoboXfRQe hB+10zpklEA2Vl0kHhg6UDUdrQNzHKrEqJdETtxY4RdpvGvp/LU4hz+zt6YwyaadehHB 3w2g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377962; x=1698982762; 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=/zo8HpYmb+yYCFm1lxy89mJtImc6tDFF4y7FplR5LLY=; b=WEszuI7kykI5uf8xQ3Wld59alcCb/u2wxVIJVeaBDdJK8+KGAzujLv41xgiJ5ENuJ0 PmPhr2UowFwS79LTZOLxvFNkxRobXX2NJHu5tdq0UoyYug7YAw+QdgBsFtdi3ARyYkcu VjzF+sKfrMJlqKnit1au4qL+IaLfqAmsx/qOS1xkNc6mnT+GrSsCPpzumiDsdqZz4F7v Q23AvEdioiXVRueebCIpEI2QFqBVlBLGYQ9lXm/paSweomypxwNEIJXuelHL5fU75N4Y dBz0d8Zaf4ECqUjHb1xOgnz8l3oepe8FqzrL7SEwvZwS8BB1a2BpnDjc86GB1cUErO4s tlaQ== X-Gm-Message-State: AOJu0YzEtXgNDHid+QdIydw2ei3Nmw9+Fk2OgwxeunPjQrDFnEhTP/vs XokiiYm17rTxSwAFOGUp8duZOA== X-Google-Smtp-Source: AGHT+IFJyTlfaI8qKkOHCOjK/mg77WKAGEOyYjoN/vc2NbRHINXO7Ov6pwVEdyk1SfKcLLiGTsuL1A== X-Received: by 2002:a17:90b:3449:b0:27d:3f08:cc21 with SMTP id lj9-20020a17090b344900b0027d3f08cc21mr1456679pjb.5.1698377962177; Thu, 26 Oct 2023 20:39:22 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.15 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:21 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Fri, 27 Oct 2023 11:38:38 +0800 Message-Id: <20231027033845.90608-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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. They duplicate a maple tree in Depth-First Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the source tree and allocate new child nodes in non-leaf nodes. The new node is exactly the same as the source node except for all the addresses stored in it. It will be faster than traversing all elements in the source tree and inserting them one by one into the new tree. The time complexity of these two functions is O(n). The difference between __mt_dup() and mtree_dup() is that mtree_dup() handles locks internally. Analysis of the average time complexity of this algorithm: For simplicity, let's assume that the maximum branching factor of all non-leaf nodes is 16 (in allocation mode, it is 10), and the tree is a full tree. Under the given conditions, if there is a maple tree with n elements, the number of its leaves is n/16. From bottom to top, the number of nodes in each level is 1/16 of the number of nodes in the level below. So the total number of nodes in the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1. This is a geometric series, and it has log(n) terms with base 16. According to the formula for the sum of a geometric series, the sum of this series can be calculated as (n-1)/15. Each node has only one parent node pointer, which can be considered as an edge. In total, there are (n-1)/15-1 edges. This algorithm consists of two operations: 1. Traversing all nodes in DFS order. 2. For each node, making a copy and performing necessary modifications to create a new node. For the first part, DFS traversal will visit each edge twice. Let T(ascend) represent the cost of taking one step downwards, and T(descend) represent the cost of taking one step upwards. And both of them are constants (although mas_ascend() may not be, as it contains a loop, but here we ignore it and treat it as a constant). So the time spent on the first part can be represented as ((n-1)/15-1) * (T(ascend) + T(descend)). For the second part, each node will be copied, and the cost of copying a node is denoted as T(copy_node). For each non-leaf node, it is necessary to reallocate all child nodes, and the cost of this operation is denoted as T(dup_alloc). The behavior behind memory allocation is complex and not specific to the maple tree operation. Here, we assume that the time required for a single allocation is constant. Since the size of a node is fixed, both of these symbols are also constants. We can calculate that the time spent on the second part is ((n-1)/15) * T(copy_node) + ((n-1)/15 - n/16) * T(dup_alloc). Adding both parts together, the total time spent by the algorithm can be represented as: ((n-1)/15) * (T(ascend) + T(descend) + T(copy_node) + T(dup_alloc)) - n/16 * T(dup_alloc) - (T(ascend) + T(descend)) Let C1 =3D T(ascend) + T(descend) + T(copy_node) + T(dup_alloc) Let C2 =3D T(dup_alloc) Let C3 =3D T(ascend) + T(descend) Finally, the expression can be simplified as: ((16 * C1 - 15 * C2) / (15 * 16)) * n - (C1 / 15 + C3). This is a linear function, so the average time complexity is O(n). Signed-off-by: Peng Zhang Suggested-by: Liam R. Howlett --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 274 +++++++++++++++++++++++++++++++++++++ 2 files changed, 277 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index f91dbc7fe091..a452dd8a1e5c 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -329,6 +329,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 ca7039633844..718a222cc090 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4,6 +4,8 @@ * Copyright (c) 2018-2022 Oracle Corporation * Authors: Liam R. Howlett * Matthew Wilcox + * Copyright (c) 2023 ByteDance + * Author: Peng Zhang */ =20 /* @@ -6475,6 +6477,278 @@ void *mtree_erase(struct maple_tree *mt, unsigned l= ong index) } EXPORT_SYMBOL(mtree_erase); =20 +/* + * mas_dup_free() - Free an incomplete duplication of a tree. + * @mas: The maple state of a incomplete tree. + * + * The parameter @mas->node passed in indicates that the allocation failed= on + * this node. This function frees all nodes starting from @mas->node in the + * reverse order of mas_dup_build(). There is no need to hold the source t= ree + * lock at this 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_is_none(mas)) + 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 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 replace the parent. + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @parent: The parent of the new node. + * + * Copy @mas->node to @new_mas->node, set @parent to be the parent of + * @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_pnode *parent) +{ + struct maple_node *node =3D mte_to_node(mas->node); + struct maple_node *new_node =3D mte_to_node(new_mas->node); + unsigned long val; + + /* Copy the node completely. */ + memcpy(new_node, node, sizeof(struct maple_node)); + /* Update the parent node pointer. */ + val =3D (unsigned long)node->parent & MAPLE_NODE_MASK; + new_node->parent =3D ma_parent_ptr(val | (unsigned long)parent); +} + +/* + * mas_dup_alloc() - Allocate child nodes for a maple node. + * @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 allocates child nodes for @new_mas->node during the dupli= cation + * process. If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *ne= w_mas, + 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 char request, count, i; + void __rcu **slots; + void __rcu **new_slots; + unsigned long val; + + /* 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, (void **)new_slots); + if (unlikely(count < request)) { + memset(new_slots, 0, request * sizeof(void *)); + 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++) { + val =3D (unsigned long)mt_slot_locked(mas->tree, slots, i); + val &=3D MAPLE_NODE_MASK; + ((unsigned long *)new_slots)[i] |=3D val; + } +} + +/* + * mas_dup_build() - Build a new maple tree from a source tree + * @mas: The maple state of source tree, need to be in MAS_START state. + * @new_mas: The maple state of new tree, need to be in MAS_START state. + * @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 incomplete duplication of a tre= e. + * + * Note that the attributes of the two trees need to be exactly the same, = and the + * new tree needs to be empty, otherwise -EINVAL will be set in @mas. + */ +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *ne= w_mas, + gfp_t gfp) +{ + struct maple_node *node; + struct maple_pnode *parent =3D NULL; + 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; + } + + root =3D mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) + goto set_new_tree; + + node =3D mt_alloc_one(gfp); + if (!node) { + new_mas->node =3D MAS_NONE; + 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; + root =3D mte_mk_root(root); + while (1) { + mas_copy_node(mas, new_mas, parent); + if (!mte_is_leaf(mas->node)) { + /* Only allocate child nodes for non-leaf nodes. */ + mas_dup_alloc(mas, new_mas, gfp); + if (unlikely(mas_is_err(mas))) + return; + } else { + /* + * This is the last leaf node and duplication is + * completed. + */ + if (mas->max =3D=3D ULONG_MAX) + goto done; + + /* This is not the last leaf node and needs to go up. */ + do { + mas_ascend(mas); + mas_ascend(new_mas); + } while (mas->offset =3D=3D mas_data_end(mas)); + + /* Move to the next subtree. */ + mas->offset++; + new_mas->offset++; + } + + mas_descend(mas); + parent =3D ma_parent_ptr(mte_to_node(new_mas->node)); + mas_descend(new_mas); + mas->offset =3D 0; + new_mas->offset =3D 0; + } +done: + /* Specially handle the parent of the root node. */ + mte_to_node(root)->parent =3D ma_parent_ptr(mas_tree_parent(new_mas)); +set_new_tree: + /* Make them the same height */ + new_mas->tree->ma_flags =3D mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, root); +} + +/** + * __mt_dup(): Duplicate an entire 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 in Depth-First Search (DFS) pre-o= rder + * traversal. It uses memcpy() to copy nodes in the source tree and alloca= te + * new child nodes in non-leaf nodes. The new node is exactly the same as = the + * source node except for all the addresses stored in it. It will be faste= r than + * traversing all elements in the source tree and inserting them one by on= e into + * the new tree. + * 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 an entire 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 in Depth-First Search (DFS) pre-o= rder + * traversal. It uses memcpy() to copy nodes in the source tree and alloca= te + * new child nodes in non-leaf nodes. The new node is exactly the same as = the + * source node except for all the addresses stored in it. It will be faste= r than + * traversing all elements in the source tree and inserting them one by on= e into + * the new tree. + * 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_nested(&mas, SINGLE_DEPTH_NESTING); + 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 Tue Dec 16 21:28:39 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 55A91C25B47 for ; Fri, 27 Oct 2023 03:39:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345232AbjJ0Djj (ORCPT ); Thu, 26 Oct 2023 23:39:39 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37210 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1345265AbjJ0Dje (ORCPT ); Thu, 26 Oct 2023 23:39:34 -0400 Received: from mail-pj1-x1036.google.com (mail-pj1-x1036.google.com [IPv6:2607:f8b0:4864:20::1036]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C6F261BC for ; Thu, 26 Oct 2023 20:39:30 -0700 (PDT) Received: by mail-pj1-x1036.google.com with SMTP id 98e67ed59e1d1-28001f8079cso960566a91.2 for ; Thu, 26 Oct 2023 20:39:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377970; x=1698982770; 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=foGetFZ9t8EgLLDV0Dnb7jyONvdftSjfOOfLaWzQbAY=; b=dPDVGIXxB5tiOYtjHLu9Vfx2CaH0zsNL1GtKkC5mI/hUX6lT+IL2gpevS08ipl7iP/ Lc5+rODUbNg5EO6a3I60zTuS+V9pm+rcjSYuRoD8n9Vvhtkr+MxmImF87v3Ie6JgKDvK L5ChQI93IzF8Z5Sxnv37du8Cw+Gt5Xwe4rmaf41MXtJzDdZ4IUxTqccV+eAUm9Xdx1/c PaQ8zCBZHz3xVi2W9hf9Vxjm6Na2wnZjRBunIN4DTx5RIn+ohWHiAEN6At4UR1SOPu6f jt+vhh8oMscMEZrxih3nOOMHFPemh/soPovruDgqLfcZ0yq2V6CuY3hw77GyVvZloqnl 1MWw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377970; x=1698982770; 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=foGetFZ9t8EgLLDV0Dnb7jyONvdftSjfOOfLaWzQbAY=; b=Z4oHDxWus2wR3taZ1UqnCoBV40wNy/eH3HKjQ3BLTu0cRDFv/Z06BYaqo9heoNl+fS EzCk5xIbMWQhtIyCyCXrAqGEySTI6qWQIB9TfF8A6khCr3eBhLdgeLjog1ag1TaMb5ws NLeaLT4Rnkbvcln3aVYRRvarikyzh7yzpddgvi/2XxNn1Cmh7s98Hlj6UQG73cktB975 UNYgSEONn9w2vmtuK3h154pAUDrG0BiVR5e2+tN9QSLm6Xf5qa8gvzR8DdJ2tOBrcHxv 6YlS+wD4J8disBpkmL/BnpNGtuaVoDC22wxzpHkyzMOsZxVAzwmhPCg7gWbZQPWwzSAR aBEw== X-Gm-Message-State: AOJu0Yz+3PbW+YqCiIYp6HETZGFI2ve6/KtAzvVG13y/pWvJGWNgUbZK QYrhdFAJGl8gl/d9wdoQ2sI8MQ== X-Google-Smtp-Source: AGHT+IEXV//tpE9s5GCs40kvntDCcan4ON4xoFdITglGv9jOXpY7Lz29M0cQjMI93TcPesAbndJDog== X-Received: by 2002:a17:90a:1a03:b0:280:f4a:86b4 with SMTP id 3-20020a17090a1a0300b002800f4a86b4mr240851pjk.17.1698377970124; Thu, 26 Oct 2023 20:39:30 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.22 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39: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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 04/10] radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. Date: Fri, 27 Oct 2023 11:38:39 +0800 Message-Id: <20231027033845.90608-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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" When kmem_cache_alloc_bulk() fails to allocate, leave the freed pointers in the array. This enables a more accurate simulation of the kernel's behavior and allows for testing potential double-free scenarios. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- tools/testing/radix-tree/linux.c | 45 +++++++++++++++++++++++--------- 1 file changed, 33 insertions(+), 12 deletions(-) diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/li= nux.c index 61fe2601cb3a..4eb442206d01 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -93,13 +93,9 @@ void *kmem_cache_alloc_lru(struct kmem_cache *cachep, st= ruct list_lru *lru, return p; } =20 -void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +void __kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) { assert(objp); - uatomic_dec(&nr_allocated); - uatomic_dec(&cachep->nr_allocated); - if (kmalloc_verbose) - printf("Freeing %p to slab\n", objp); if (cachep->nr_objs > 10 || cachep->align) { memset(objp, POISON_FREE, cachep->size); free(objp); @@ -111,6 +107,15 @@ void kmem_cache_free_locked(struct kmem_cache *cachep,= void *objp) } } =20 +void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +{ + uatomic_dec(&nr_allocated); + uatomic_dec(&cachep->nr_allocated); + if (kmalloc_verbose) + printf("Freeing %p to slab\n", objp); + __kmem_cache_free_locked(cachep, objp); +} + void kmem_cache_free(struct kmem_cache *cachep, void *objp) { pthread_mutex_lock(&cachep->lock); @@ -141,18 +146,17 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, = gfp_t gfp, size_t size, if (kmalloc_verbose) pr_debug("Bulk alloc %lu\n", size); =20 - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (cachep->non_kernel < size) - return 0; - - cachep->non_kernel -=3D size; - } - pthread_mutex_lock(&cachep->lock); if (cachep->nr_objs >=3D size) { struct radix_tree_node *node; =20 for (i =3D 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + node =3D cachep->objs; cachep->nr_objs--; cachep->objs =3D node->parent; @@ -163,11 +167,19 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, = gfp_t gfp, size_t size, } else { pthread_mutex_unlock(&cachep->lock); for (i =3D 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + if (cachep->align) { posix_memalign(&p[i], cachep->align, cachep->size); } else { p[i] =3D malloc(cachep->size); + if (!p[i]) + break; } if (cachep->ctor) cachep->ctor(p[i]); @@ -176,6 +188,15 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, g= fp_t gfp, size_t size, } } =20 + if (i < size) { + size =3D i; + pthread_mutex_lock(&cachep->lock); + for (i =3D 0; i < size; i++) + __kmem_cache_free_locked(cachep, p[i]); + pthread_mutex_unlock(&cachep->lock); + return 0; + } + for (i =3D 0; i < size; i++) { uatomic_inc(&nr_allocated); uatomic_inc(&cachep->nr_allocated); --=20 2.20.1 From nobody Tue Dec 16 21:28:39 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 50FC7C25B48 for ; Fri, 27 Oct 2023 03:39:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345301AbjJ0Djy (ORCPT ); Thu, 26 Oct 2023 23:39:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58362 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1345279AbjJ0Djm (ORCPT ); Thu, 26 Oct 2023 23:39:42 -0400 Received: from mail-pj1-x1029.google.com (mail-pj1-x1029.google.com [IPv6:2607:f8b0:4864:20::1029]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A8E46D55 for ; Thu, 26 Oct 2023 20:39:38 -0700 (PDT) Received: by mail-pj1-x1029.google.com with SMTP id 98e67ed59e1d1-27d1fa1c787so1268972a91.3 for ; Thu, 26 Oct 2023 20:39:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377978; x=1698982778; 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=c33eXUxcaBLnS1cYMMJhWOrJpLBYqdwLmRTJuXXfNIA=; b=WsesJBnm4qFQQV+ogbW/qi/0DbTKsodtccjiAawvWJdZKvXb8egaGMnCagkM6/V8pT AzgI5ksApVw0sPIS9gtsGriZvS0z15u1GmCimwTrKEQmDcFeb4y27T7y6bT24lPkYX+X W55b12H6zupDk3eaJQE70nED7/3aq5na4u9wjkX60vvnHQJ/8Z8UPUSOqxnYBGAPcf0t OydxNFtyCExmbAH5TBT1poOD0ahlu8egv/8KOFh8TeU3FADTHny+MoVzBAMmhSklGhl9 xJN6EVIfsiIjYhLzQPMQfL3r06uJbfT/Hs1N7+Mm8Xgb2o5x415T4I9YN0ec4SJH2Odq xBYw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377978; x=1698982778; 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=c33eXUxcaBLnS1cYMMJhWOrJpLBYqdwLmRTJuXXfNIA=; b=R1MfcCYBiKunil8knNZUlNcm+9V/uxG9Q1RjFcaCn+8/RYalvWoJSo1pd7xyqv3L/6 tADTVg/WngY+aZROjx4uFFoJT2eiAV0dS0gy27aEetKUD2/zGFanWEQLqC4nL8FyjlJy rlWr/Jszj0CWAzIbKam8VfyIU5tRPKaFn+9vSvcf48e+LusnEokRG7JruZSm1fDRWuMy hgUCSMGUCCT41yR+1OM0mqa013I+2SwUYmB+YZKhcMMjAigLo7q5E+9BNK+dnFiZpQKZ MY5PmUDlwDvnuUdwnx3wjrOUD56iCuotc9feCG/nd6Cc2NP0IjpJFpD9HCacvCRepw3o AvIQ== X-Gm-Message-State: AOJu0YxJnDrhezB97D34I12xDQ24KyxCrncckI7lU0e5frMJOr7nKaKs UDkq4T5WHImXGMzO77GAEN8Kvg== X-Google-Smtp-Source: AGHT+IHa6xzp6B+Hd6qod6wThw8VgUCQkutV3uFt7t+Mr9ZaRucfgzggvrM+TvB2ROpiG0s6ITCt5A== X-Received: by 2002:a17:90a:5381:b0:27f:fe79:eb6c with SMTP id y1-20020a17090a538100b0027ffe79eb6cmr1351310pjh.29.1698377978039; Thu, 26 Oct 2023 20:39:38 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39:37 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 05/10] maple_tree: Add test for mtree_dup() Date: Fri, 27 Oct 2023 11:38:40 +0800 Message-Id: <20231027033845.90608-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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(). Test by duplicating different maple trees and then comparing the two trees. Includes tests for duplicating full trees and memory allocation failures on different nodes. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- tools/testing/radix-tree/maple.c | 361 +++++++++++++++++++++++++++++++ 1 file changed, 361 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/ma= ple.c index e5da1cad70ba..12b3390e9591 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,363 @@ static noinline void __init check_locky(struct ma= ple_tree *mt) mt_clear_in_rcu(mt); } =20 +/* + * Compares two nodes except for the addresses stored in the nodes. + * Returns zero if they are the same, otherwise returns non-zero. + */ +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(mt, 0); + mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); + ret =3D mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + + /* The two trees have different attributes. */ + mt_init_flags(mt, 0); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + ret =3D mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret !=3D -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* The new tree is not empty */ + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); + ret =3D mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret !=3D -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Test for duplicating full trees. */ + for (i =3D 1; i <=3D 3; i++) { + ret =3D build_full_tree(mt, 0, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, 0); + + ret =3D mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + for (i =3D 1; i <=3D 3; i++) { + ret =3D build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + + ret =3D mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test for normal duplicating. */ + for (i =3D 0; i < 1000; i +=3D 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j =3D 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret =3D mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test memory allocation failed. */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i =3D 0; i < 30; i +=3D 3) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + /* Failed at the first node. */ + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + mt_set_non_kernel(0); + ret =3D mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + MT_BUG_ON(&new, ret !=3D -ENOMEM); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Random maple tree fails at a random node. */ + for (i =3D 0; i < 1000; i +=3D 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j =3D 0; j < i; j++) { + mtree_store_range(mt, 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(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret !=3D 0) { + MT_BUG_ON(&new, ret !=3D -ENOMEM); + count++; + mtree_destroy(mt); + continue; + } + + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + 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 +36261,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 Tue Dec 16 21:28:39 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 B2C9CC25B48 for ; Fri, 27 Oct 2023 03:40:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345264AbjJ0Dka (ORCPT ); Thu, 26 Oct 2023 23:40:30 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58306 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234901AbjJ0DkK (ORCPT ); Thu, 26 Oct 2023 23:40:10 -0400 Received: from mail-pg1-x52b.google.com (mail-pg1-x52b.google.com [IPv6:2607:f8b0:4864:20::52b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9ECA81A5 for ; Thu, 26 Oct 2023 20:39:46 -0700 (PDT) Received: by mail-pg1-x52b.google.com with SMTP id 41be03b00d2f7-5b93ddb10b8so300723a12.0 for ; Thu, 26 Oct 2023 20:39:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377985; x=1698982785; 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=74qqxidjqyd9XulDVkugPZl+GB+TldL/DBrAezqtgJY=; b=FjPwxficg555/vc9VQXDvykvw7zH6mCk1PevNpsgcx0Ja3expzXJxa1ZA9Es80lVBn e9mn0iskHiJSVssYxDPuvnWXQAusKyNRQ/b+Cse859XGfMXgWkqNS2scD9K8s/Pfqtdj yzwDVCfjsZJPUlcvXOUqrjPqL5p1d+KJtEoMu1SArWBFPvggNKQ/ZLRG2rRAf7mCEahV ZAe6YBwnCGNBaYj20qJVzbuviJ75z8S4UFAvjddhSscfOmlt3rCYyNrKM58UpazOACQX 7tTbFB+0MzqB74413jrbiUYZzzr5TNg7xi2FbviCvNP4w6cVK5/eIGh1lZIW6a32HXAh 4mQw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377985; x=1698982785; 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=74qqxidjqyd9XulDVkugPZl+GB+TldL/DBrAezqtgJY=; b=SN5ejL/YbpxZvE5PJLHHFIEZfxyo14RDDRAUBwhcy5GbFznR6R2WwfbmVdp+OHIBSU xuWwNUUa3HZugNwxm3BDP9uP9SJHE7/aPBYE4qyourSkNJtO/UI+Gc0QfTB3YJ7+id6p KgpmCM2jkLpftyUhhuSx9OplhWGQtPT5Pv9U8o7AzBn9ltj7OECE6TRHxVbbfTQXRS+X FiJerDNK2qHDCFpHI0ubzwA0oyg1QdGbXXtCE07PaUel3pB5+SZyFEjVfo0q2OwCsW0B UMV820LF6rj8Yd5/9PB2vxtZ4Plmmpc+6Aih6GAonuMQHriHDl3tyZzlfx5NPys+uQsU fpig== X-Gm-Message-State: AOJu0Yx0NXzkUUsYa942xX3hwgCNHM6dEgkJ57Oz/GromaxaL2H9P1S/ Dhm9TCtCHkLHJ3d2YMKbsziOkA== X-Google-Smtp-Source: AGHT+IE0WBlgixccb7xQyscB6ftmdLDZ7xdSH5V+CyxdwveadRU+NlM0bptvnd1oQV9FJPaGCIUEEQ== X-Received: by 2002:a17:90a:9708:b0:268:808:8e82 with SMTP id x8-20020a17090a970800b0026808088e82mr1969715pjo.1.1698377985415; Thu, 26 Oct 2023 20:39:45 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.38 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39: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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 06/10] maple_tree: Update the documentation of maple tree Date: Fri, 27 Oct 2023 11:38:41 +0800 Message-Id: <20231027033845.90608-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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 the new interface mtree_dup() in the documentation. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- Documentation/core-api/maple_tree.rst | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api= /maple_tree.rst index 96f3d5f076b5..ccdd1615cf97 100644 --- a/Documentation/core-api/maple_tree.rst +++ b/Documentation/core-api/maple_tree.rst @@ -81,6 +81,9 @@ section. Sometimes it is necessary to ensure the next call to store to a maple tree= does not allocate memory, please see :ref:`maple-tree-advanced-api` for this us= e case. =20 +You can use mtree_dup() to duplicate an entire maple tree. It is a more +efficient way than inserting all elements one by one into a new tree. + Finally, you can remove all entries from a maple tree by calling mtree_destroy(). If the maple tree entries are pointers, you may wish to = free the entries first. @@ -112,6 +115,7 @@ Takes ma_lock internally: * mtree_insert() * mtree_insert_range() * mtree_erase() + * mtree_dup() * mtree_destroy() * mt_set_in_rcu() * mt_clear_in_rcu() --=20 2.20.1 From nobody Tue Dec 16 21:28:39 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 D9257C25B48 for ; Fri, 27 Oct 2023 03:40:17 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345401AbjJ0DkR (ORCPT ); Thu, 26 Oct 2023 23:40:17 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50430 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1345265AbjJ0DkB (ORCPT ); Thu, 26 Oct 2023 23:40:01 -0400 Received: from mail-pg1-x531.google.com (mail-pg1-x531.google.com [IPv6:2607:f8b0:4864:20::531]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 06790D6C for ; Thu, 26 Oct 2023 20:39:54 -0700 (PDT) Received: by mail-pg1-x531.google.com with SMTP id 41be03b00d2f7-565334377d0so1328741a12.2 for ; Thu, 26 Oct 2023 20:39:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698377993; x=1698982793; 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=h5YTmJUCjjpdhuy3lqQAZ858a5z7S5zSCc8pR4j7dSE=; b=L0j9qS/c52jpRdSAjdoay53+uq6mhPq/L6aRTherG9grqUTiNk3dXRoy1P2fMTtJIu CiWt//TD1MbQJqHjpXdLChz1Koc+cqTIuMfXKeGo+YtN0PFuM6HoYN0hNWJzszSKg0yB H2rAlSKBT6y/qy1KEGmt2I0N0O3bVCSzjiGxBs/hc2YVAfMgBZZ034kuUzkVKCKgJKjS wUmqlkfASKylqI2ZsxE1j61kifVLNAuFggff8XHWuSU7tWoe8dtz82ydohoymi3tqQst tEJZHrI0W4n4Ji1aJlNjd/aUVZto++1F3u6sQa0ZE0bImicsvsIg7qRu6u9zgDMuR8gL X+5Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698377993; x=1698982793; 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=h5YTmJUCjjpdhuy3lqQAZ858a5z7S5zSCc8pR4j7dSE=; b=DAtKY5vljTXpk1tuGiK/CO1lXiFW0l7Botwrtz1c49TFbmBBsezb2Wc955DXdhULoy vJS8s5rtNSWTVltUGV3QPUQhHa4/Qh/WZ5rLPbmTyFisXh7S0h/vrF8i5KudDz0yQ+PL dyReRGseeNhrUVJs022mirY8GtCloIm4jrm5XKSKbC/g5w/IAOoYvm50JrMMpYT7I0g1 6VWvLYDdltEphJ7bfq6PO/Iu8MnXDtVppal6gF0u6mDI7NiQZkXBcGSqfNElAvFOfRoQ XET9ifmOQVLGWuIFsd3rBMdeh3telPhWAtmA03hva2MolaB0pDdZc+MdsWx2olSdG9sn gMKw== X-Gm-Message-State: AOJu0YzoHAG0EE+k4xXRCI/wTro0wpK1n/9KoGBAEDsqeMPDhXCVTMZ9 ymlYNqEMRftgFbvn6Rxi3iQRdg== X-Google-Smtp-Source: AGHT+IGP7vALm36zcf78WOHdDsQMZ6gR6l+CE8E8raNCoeG3jAG7u2Ud7OkIO091/2fqWLXD+y+pYw== X-Received: by 2002:a17:90b:1486:b0:27d:e1c:5345 with SMTP id js6-20020a17090b148600b0027d0e1c5345mr1376337pjb.15.1698377993313; Thu, 26 Oct 2023 20:39:53 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.45 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:39: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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 07/10] maple_tree: Skip other tests when BENCH is enabled Date: Fri, 27 Oct 2023 11:38:42 +0800 Message-Id: <20231027033845.90608-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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 Reviewed-by: Liam R. Howlett --- 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 464eeb90d5ad..de470950714f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3585,10 +3585,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); @@ -3646,6 +3642,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 12b3390e9591..cb5358674521 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36299,7 +36299,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 Tue Dec 16 21:28:39 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 788A1C25B48 for ; Fri, 27 Oct 2023 03:40:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235124AbjJ0Dkt (ORCPT ); Thu, 26 Oct 2023 23:40:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58320 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234993AbjJ0Dk3 (ORCPT ); Thu, 26 Oct 2023 23:40:29 -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 A599E10E9 for ; Thu, 26 Oct 2023 20:40:01 -0700 (PDT) Received: by mail-pj1-x102c.google.com with SMTP id 98e67ed59e1d1-280109daaaaso31074a91.3 for ; Thu, 26 Oct 2023 20:40:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698378001; x=1698982801; 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=x6aKxmDhD/mYQG3DiCaoAvSr06SUW/o1u/OdA/jXWcA=; b=gUfK4XBiyuJQsRUSzTCgJ0rAi8hoRbfnRRzYUwFee4JHd3gSxL0kB/r1+wHssEhVLP ckxEL67mWu+skIyfMy1P2zu0cu/vk6XEIehAJf8nGIm8oz4Yaoiz0N2B0PETE14nPMqV 4Oh5EknwEM8DIdK0L88J7I4FkS+NvW6z4xiarDtpdtD9mXdEiE1uZScqz5Wf6jZOnBpv YBv7unUCdMfE5ZZrop7RhRORwG4tgaO4EBd0L3pClDInQ8VFcilPq8qY4iW5TW4s8SNG 849ZWNu5EehxcR6dwqBVbTYTLi3LETOlRpnHK/pTmTXH9xx3+wrXv99vtyKdMPy4K170 Kw/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698378001; x=1698982801; 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=x6aKxmDhD/mYQG3DiCaoAvSr06SUW/o1u/OdA/jXWcA=; b=c5SB+1hvSg3cN7tFU1n261fFuXomIfHd8Ushgip8i+24+HNR4J4DWoGX+Q295iwxc6 dFOXrqHbfX2My5YqOUvOriLG8MbUieNoQ9H23SLIFMciFSScjzlo9hM6gHAFnhWCfxPC llOqnvD+5kRUdBltE8oBN430dfL5m7HQsxMWffV2dF+KfJQtqrayZz2t37IwY/ldTY8u RkbT0rJUUL7zWDH8YoMHmZ14fYb/flGmXX/zpJZZwk6XoVRhmUIiZy19hic99eFeRs05 wwqa97d/71XExmcyA3UJBKqCC81Cv89ZmNzCIue98VufIxmsgmkIKpC7eT/i5qZwGytY Q1mQ== X-Gm-Message-State: AOJu0YwJShjvHDspDgB/A/6zVgSk0+nWUFNlsM8kwGqtnG4qscLOvCrY m5JBzchOqBf57fAvOru/+LVoAA== X-Google-Smtp-Source: AGHT+IH1injlMTgSGoHntNmgiaj1ZHobC4M78EJdUrrHo1lR+rYQIgDSUugUVcu6Xg6S9M0L5Xxffw== X-Received: by 2002:a17:90b:1912:b0:27d:3be:8e13 with SMTP id mp18-20020a17090b191200b0027d03be8e13mr1371267pjb.12.1698378000792; Thu, 26 Oct 2023 20:40:00 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.39.53 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:40: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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 08/10] maple_tree: Update check_forking() and bench_forking() Date: Fri, 27 Oct 2023 11:38:43 +0800 Message-Id: <20231027033845.90608-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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 Reviewed-by: Liam R. Howlett --- lib/test_maple_tree.c | 117 ++++++++++++++++++------------------ tools/include/linux/rwsem.h | 4 ++ 2 files changed, 62 insertions(+), 59 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index de470950714f..3e4597fb49d3 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1834,47 +1834,48 @@ static noinline void __init bench_mas_prev(struct m= aple_tree *mt) } #endif /* check_forking - simulate the kernel forking sequence with the tree. */ -static noinline void __init check_forking(struct maple_tree *mt) +static noinline void __init check_forking(void) { - - struct maple_tree newmt; - int i, nr_entries =3D 134; + struct maple_tree mt, newmt; + int i, nr_entries =3D 134, ret; void *val; - MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; =20 + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); =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); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); =20 - mt_set_non_kernel(99999); mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&newmt, &newmt_lock); - newmas.tree =3D &newmt; - mas_reset(&newmas); - mas_reset(&mas); - down_write(&newmt_lock); - mas.index =3D 0; - mas.last =3D 0; - if (mas_expected_entries(&newmas, nr_entries)) { + + down_write(&mt_lock); + for (i =3D 0; i <=3D nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret =3D __mt_dup(&mt, &newmt, GFP_KERNEL); + 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_destroy(&mas); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); + __mt_destroy(&mt); up_write(&newmt_lock); + up_write(&mt_lock); } =20 static noinline void __init check_iteration(struct maple_tree *mt) @@ -1977,49 +1978,51 @@ static noinline void __init check_mas_store_gfp(str= uct maple_tree *mt) } =20 #if defined(BENCH_FORK) -static noinline void __init bench_forking(struct maple_tree *mt) +static noinline void __init bench_forking(void) { - - struct maple_tree newmt; - int i, nr_entries =3D 134, nr_fork =3D 80000; + struct maple_tree mt, newmt; + 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); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; =20 + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); - mt_set_external_lock(&newmt, &newmt_lock); =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); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); + + down_write(&mt_lock); + for (i =3D 0; i <=3D nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } =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(); - down_write(&newmt_lock); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + mt_init_flags(&newmt, + MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&newmt, &newmt_lock); + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret =3D __mt_dup(&mt, &newmt, GFP_KERNEL); + 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); - rcu_read_unlock(); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); up_write(&newmt_lock); } + mas_destroy(&mas); + __mt_destroy(&mt); + up_write(&mt_lock); } #endif =20 @@ -3615,9 +3618,7 @@ static int __init maple_tree_seed(void) #endif #if defined(BENCH_FORK) #define BENCH - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - bench_forking(&tree); - mtree_destroy(&tree); + bench_forking(); goto skip; #endif #if defined(BENCH_MT_FOR_EACH) @@ -3650,9 +3651,7 @@ static int __init maple_tree_seed(void) check_iteration(&tree); mtree_destroy(&tree); =20 - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_forking(&tree); - mtree_destroy(&tree); + check_forking(); =20 mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_mas_store_gfp(&tree); diff --git a/tools/include/linux/rwsem.h b/tools/include/linux/rwsem.h index 83971b3cbfce..f8bffd4a987c 100644 --- a/tools/include/linux/rwsem.h +++ b/tools/include/linux/rwsem.h @@ -37,4 +37,8 @@ static inline int up_write(struct rw_semaphore *sem) { return pthread_rwlock_unlock(&sem->lock); } + +#define down_read_nested(sem, subclass) down_read(sem) +#define down_write_nested(sem, subclass) down_write(sem) + #endif /* _TOOLS_RWSEM_H */ --=20 2.20.1 From nobody Tue Dec 16 21:28:39 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 B3796C25B47 for ; Fri, 27 Oct 2023 03:41:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345380AbjJ0DlK (ORCPT ); Thu, 26 Oct 2023 23:41:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:50482 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235084AbjJ0Dkl (ORCPT ); Thu, 26 Oct 2023 23:40:41 -0400 Received: from mail-pj1-x102d.google.com (mail-pj1-x102d.google.com [IPv6:2607:f8b0:4864:20::102d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9D0CFD55 for ; Thu, 26 Oct 2023 20:40:09 -0700 (PDT) Received: by mail-pj1-x102d.google.com with SMTP id 98e67ed59e1d1-27ffa7e32feso1021876a91.3 for ; Thu, 26 Oct 2023 20:40:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698378008; x=1698982808; 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=t/TBSsqo/3PZG//kKjzBxqBhIhs+Qitm7vuazfD4aPI=; b=DDk4A7esaWB+86LNddvgqDFGUgvg28BtPxHclNVDfMg4e3q3fLwhP8/DGVObzZieaI /w7z3IrEiny0Z7GMRYS8WS6hhYXYzf6WkejXu8aJ5lzWacs4Vy8El4yX25hSWNC6YvwS utVcdaYgeReeIEfM8FE0CoUc1jCAvOpDQnw1aFpsakX6dkxB4mzjkBlghN/1ltsZPjDI If5DLS0+Jc+ER+3Swkg8YwzyumXanbouv4Q0BdgXJwIdtGdM0yDKBZWJLq8lEbVX3O7f MHODGKbBPvnAGdAVBqwrqNLi402k7beZvvnCiq6/BktDFqiId6l3XWX8sJU82Tub/OWq 1SKw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698378008; x=1698982808; 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=t/TBSsqo/3PZG//kKjzBxqBhIhs+Qitm7vuazfD4aPI=; b=CEqMV7bZX4V7ugq4PcDh2TBwpAS6CtlEUG80Wisip1mSdxX7JDpYPwN3czHPo+BzcK GORqnYPrw68lWNrvCqCFjhrs/sUlole9U8oIlcKlC3mUrgc7GUOsMyOwZqR9ZjNTho3h YRKY39ewfbYaQibUw+mBON4RJ6TxCDHjvlwWB0T5vFlGq0/6fhnGvy+5vHnAUt5N+h8j XuZE0uTQqKbKMfvbpkR+xf2Adj9SYcqAlpoGHF3xHvB7TwpD8KE5n4eUz9e6h/hvTYxJ 9SVplmuNrb04WQNvNO1ZLW+iZCD2I5DVOOuHpCg1dsqYqwjmdu65MAwqzKG/w73pLSCM pntw== X-Gm-Message-State: AOJu0YzGTvyOgwkzw9SK2sNh8OAnd5zehbJdNUS5ZYWPAdyVv4+dKxqe 5I9nWOqI+8VsTLyc6x/FXy1n3Q== X-Google-Smtp-Source: AGHT+IExlg2G7fYOUnFWtBHLrBsW1lyYgFaUWIXf6NstZ6E0c++iEGcYR48s2/F7tPuX752NBLahNg== X-Received: by 2002:a17:90b:18e:b0:27d:2663:c5f4 with SMTP id t14-20020a17090b018e00b0027d2663c5f4mr1538778pjs.47.1698378008501; Thu, 26 Oct 2023 20:40:08 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.40.01 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:40:08 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 09/10] maple_tree: Preserve the tree attributes when destroying maple tree Date: Fri, 27 Oct 2023 11:38:44 +0800 Message-Id: <20231027033845.90608-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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" When destroying maple tree, preserve its attributes and then turn it into an empty tree. This allows it to be reused without needing to be reinitialized. Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 718a222cc090..4439469442c7 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6763,7 +6763,7 @@ void __mt_destroy(struct maple_tree *mt) if (xa_is_node(root)) mte_destroy_walk(root, mt); =20 - mt->ma_flags =3D 0; + mt->ma_flags =3D mt_attr(mt); } EXPORT_SYMBOL_GPL(__mt_destroy); =20 --=20 2.20.1 From nobody Tue Dec 16 21:28:39 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 F40D3C25B47 for ; Fri, 27 Oct 2023 03:41:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1345298AbjJ0DlD (ORCPT ); Thu, 26 Oct 2023 23:41:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46486 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234902AbjJ0Dko (ORCPT ); Thu, 26 Oct 2023 23:40:44 -0400 Received: from mail-pg1-x533.google.com (mail-pg1-x533.google.com [IPv6:2607:f8b0:4864:20::533]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 94225170E for ; Thu, 26 Oct 2023 20:40:16 -0700 (PDT) Received: by mail-pg1-x533.google.com with SMTP id 41be03b00d2f7-5b93ddb10b8so300922a12.0 for ; Thu, 26 Oct 2023 20:40:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698378016; x=1698982816; 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=Ky4w3uAtFSkvxKCreCTuy48cfBYAXj8C3Bu1f6A1ISE=; b=iR7AfGiolMO0wCI8tmev6lBsE3Io897zDNZtnA1m6XQ7MxpBDOYswtpPELVgHmDrq4 dQn2l05U70mcGhTNR/4mAsJlgiTfButxyBvN3efrT8l1vqxnHaz7ZXnWp5GTzjBvUJEI 2j2w1K+OWWSNUhhxTZVMznD3ByP9z4sW/aNCggNu6pnHNFQikykqOm8PIdMewZjPbKB6 Bum0b0koucpVaK6dz8Zxy8LovNl1nvDNFDVt13i18BAp8+LjJD5vf5nF/5EDJb3g2Xyt BLmBHDbY28szVfxjrmpHOcJSB93mnj5p6w1bPIOHNMqjoHnzSJ7Um6oFqSz3EqTQcqgk bipg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698378016; x=1698982816; 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=Ky4w3uAtFSkvxKCreCTuy48cfBYAXj8C3Bu1f6A1ISE=; b=JHBXf84HF+HsaN7+B9iX+BOQGni0ZW2W7VZqW5zRSdp0HD/3l94uE+ghpP64LBlVUy u0PGFucX0K1z0vfoX58R55r1UjoZ2pQSfuykCGgxbwpm8VtP0Iabr3a4dXmJ4qT6CqK+ VVHCxmlQzSgGM00tA9r02P6ojIJ7WN9mrS8KZCQ7CSDYfYhLDsalnzBDFBY8IBpEwuVC 958kR5K9+zzp521ClK8Zob0LovP0w0PLClVWEsm1v+h4lQREGc5qA9ADlW+D91M3dzOC WhBraZ6nYrpv04QweLZC3Aj1UHk4K7zeuy451JsT+tidsi6G/8mvM4Edtek1tkIwJLNV rRkA== X-Gm-Message-State: AOJu0Yz9ODJKvFgzFc4fe9toHeX/bNJFvZxE0IbFUT6oWoE1to/GKcZ8 IzOK2GcyLo4aPPOMWQv+r5Q1zQ== X-Google-Smtp-Source: AGHT+IFJRCeA+OUFMxyndHyvFf1XFZD0IulFfw6dGetvqF75UjjqNY1IEWlGGaZ1U8Eieo7P5Fin/w== X-Received: by 2002:a17:90b:1bc6:b0:27d:4935:8d9a with SMTP id oa6-20020a17090b1bc600b0027d49358d9amr5489370pjb.4.1698378015924; Thu, 26 Oct 2023 20:40:15 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.189.7]) by smtp.gmail.com with ESMTPSA id ms19-20020a17090b235300b00267d9f4d340sm2345676pjb.44.2023.10.26.20.40.08 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 26 Oct 2023 20:40:15 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com Cc: zhangpeng.00@bytedance.com, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v7 10/10] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Fri, 27 Oct 2023 11:38:45 +0800 Message-Id: <20231027033845.90608-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com> References: <20231027033845.90608-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" In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then directly replacing the entries of VMAs in the new maple tree can result in better performance. __mt_dup() uses DFS pre-order to duplicate the maple tree, so it is efficient. The average time complexity of __mt_dup() is O(n), where n is the number of VMAs. The proof of the time complexity is provided in the commit log that introduces __mt_dup(). After duplicating the maple tree, each element is traversed and replaced (ignoring the cases of deletion, which are rare). Since it is only a replacement operation for each element, this process is also O(n). Analyzing the exact time complexity of the previous algorithm is challenging because each insertion can involve appending to a node, pushing data to adjacent nodes, or even splitting nodes. The frequency of each action is difficult to calculate. The worst-case scenario for a single insertion is when the tree undergoes splitting at every level. If we consider each insertion as the worst-case scenario, we can determine that the upper bound of the time complexity is O(n*log(n)), although this is a loose upper bound. However, based on the test data, it appears that the actual time complexity is likely to be O(n). As the entire maple tree is duplicated using __mt_dup(), if dup_mmap() fails, there will be a portion of VMAs that have not been duplicated in the maple tree. To handle this, we mark the failure point with XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, stop releasing VMAs that have not been duplicated after this point. 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 results. The first row shows the number of VMAs. The second and third rows show the number of fork() calls per ten seconds, corresponding to next-20231006 and the this patchset, respectively. The test results were obtained with CPU binding to avoid scheduler load balancing that could cause unstable results. There are still some fluctuations in the test results, but at least they are better than the original performance. 21 121 221 421 821 1621 3221 6421 12821 25621 51221 112100 76261 54227 34035 20195 11112 6017 3161 1606 802 393 114558 83067 65008 45824 28751 16072 8922 4747 2436 1233 599 2.19% 8.92% 19.88% 34.64% 42.37% 44.64% 48.28% 50.17% 51.68% 53.74% 52.42% [1] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang Suggested-by: Liam R. Howlett Reviewed-by: Liam R. Howlett --- include/linux/mm.h | 11 +++++++++++ kernel/fork.c | 40 +++++++++++++++++++++++++++++----------- mm/internal.h | 11 ----------- mm/memory.c | 7 ++++++- mm/mmap.c | 9 ++++++--- 5 files changed, 52 insertions(+), 26 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 14d5aaff96d0..e9111ec5808c 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -996,6 +996,17 @@ static inline int vma_iter_bulk_alloc(struct vma_itera= tor *vmi, return mas_expected_entries(&vmi->mas, count); } =20 +static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, + unsigned long start, unsigned long end, gfp_t gfp) +{ + __mas_set_range(&vmi->mas, start, end - 1); + mas_store_gfp(&vmi->mas, NULL, gfp); + if (unlikely(mas_is_err(&vmi->mas))) + return -ENOMEM; + + return 0; +} + /* Free any unused preallocations */ static inline void vma_iter_free(struct vma_iterator *vmi) { diff --git a/kernel/fork.c b/kernel/fork.c index 1e6c656e0857..1552ee66517b 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,16 +677,22 @@ 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_KERNEL); + 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) { + retval =3D vma_iter_clear_gfp(&vmi, mpnt->vm_start, + mpnt->vm_end, GFP_KERNEL); + if (retval) + goto loop_out; + vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); continue; } @@ -749,9 +754,11 @@ static __latent_entropy int dup_mmap(struct mm_struct = *mm, if (is_vm_hugetlb_page(tmp)) hugetlb_dup_vma_private(tmp); =20 - /* Link the vma into the MT */ - if (vma_iter_bulk_store(&vmi, tmp)) - goto fail_nomem_vmi_store; + /* + * Link the vma into the MT. After using __mt_dup(), memory + * allocation is not necessary here, so it cannot fail. + */ + vma_iter_bulk_store(&vmi, tmp); =20 mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -760,15 +767,28 @@ static __latent_entropy int dup_mmap(struct mm_struct= *mm, if (tmp->vm_ops && tmp->vm_ops->open) tmp->vm_ops->open(tmp); =20 - if (retval) + if (retval) { + mpnt =3D vma_next(&vmi); goto loop_out; + } } /* a new mm has just been created */ retval =3D arch_dup_mmap(oldmm, mm); loop_out: vma_iter_free(&vmi); - if (!retval) + if (!retval) { mt_set_in_rcu(vmi.mas.tree); + } else if (mpnt) { + /* + * The entire maple tree has already been duplicated. If the + * mmap duplication fails, mark the failure point with + * XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, + * stop releasing VMAs that have not been duplicated after this + * point. + */ + mas_set_range(&vmi.mas, mpnt->vm_start, mpnt->vm_end - 1); + mas_store(&vmi.mas, XA_ZERO_ENTRY); + } out: mmap_write_unlock(mm); flush_tlb_mm(oldmm); @@ -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/internal.h b/mm/internal.h index b61034bd50f5..89a5a794d68f 100644 --- a/mm/internal.h +++ b/mm/internal.h @@ -1154,17 +1154,6 @@ static inline void vma_iter_clear(struct vma_iterato= r *vmi) mas_store_prealloc(&vmi->mas, NULL); } =20 -static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, - unsigned long start, unsigned long end, gfp_t gfp) -{ - __mas_set_range(&vmi->mas, start, end - 1); - mas_store_gfp(&vmi->mas, NULL, gfp); - if (unlikely(mas_is_err(&vmi->mas))) - return -ENOMEM; - - return 0; -} - static inline struct vm_area_struct *vma_iter_load(struct vma_iterator *vm= i) { return mas_walk(&vmi->mas); diff --git a/mm/memory.c b/mm/memory.c index 1f18ed4a5497..20cc6e3586e7 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -374,6 +374,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_st= ate *mas, * be 0. This will underflow and is okay. */ next =3D mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next =3D NULL; =20 /* * Hide vma from rmap and truncate_pagecache before freeing @@ -395,6 +397,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_st= ate *mas, && !is_vm_hugetlb_page(next)) { vma =3D next; next =3D mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next =3D NULL; if (mm_wr_locked) vma_start_write(vma); unlink_anon_vmas(vma); @@ -1743,7 +1747,8 @@ void unmap_vmas(struct mmu_gather *tlb, struct ma_sta= te *mas, unmap_single_vma(tlb, vma, start, end, &details, mm_wr_locked); hugetlb_zap_end(vma, &details); - } while ((vma =3D mas_find(mas, tree_end - 1)) !=3D NULL); + vma =3D mas_find(mas, tree_end - 1); + } while (vma && likely(!xa_is_zero(vma))); mmu_notifier_invalidate_range_end(&range); } =20 diff --git a/mm/mmap.c b/mm/mmap.c index 984804d77ae1..e98e9715afb2 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3300,10 +3300,11 @@ void exit_mmap(struct mm_struct *mm) arch_exit_mmap(mm); =20 vma =3D mas_find(&mas, ULONG_MAX); - if (!vma) { + if (!vma || unlikely(xa_is_zero(vma))) { /* Can happen if dup_mmap() received an OOM */ mmap_read_unlock(mm); - return; + mmap_write_lock(mm); + goto destroy; } =20 lru_add_drain(); @@ -3338,11 +3339,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); + } while (vma && likely(!xa_is_zero(vma))); =20 BUG_ON(count !=3D mm->map_count); =20 trace_exit_mmap(mm); +destroy: __mt_destroy(&mm->mm_mt); mmap_write_unlock(mm); vm_unacct_memory(nr_accounted); --=20 2.20.1