From nobody Thu Jan 1 09:00:26 2026 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 0C740C07545 for ; Tue, 24 Oct 2023 08:33:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233981AbjJXIds (ORCPT ); Tue, 24 Oct 2023 04:33:48 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55288 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233928AbjJXIdl (ORCPT ); Tue, 24 Oct 2023 04:33:41 -0400 Received: from mail-pf1-x42c.google.com (mail-pf1-x42c.google.com [IPv6:2607:f8b0:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EA64E99 for ; Tue, 24 Oct 2023 01:33:17 -0700 (PDT) Received: by mail-pf1-x42c.google.com with SMTP id d2e1a72fcca58-6be0277c05bso3277371b3a.0 for ; Tue, 24 Oct 2023 01:33:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136397; x=1698741197; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=B94SZKzSqsawfuayEI/UehMSGtS4IxKFKCX0IwoUmRF+6j0ja4TTqt59k0u7TDRF1p v8R7VVFKp8LBp57ATeW2It8DKLS65pyhb/4rSN1Fuow/XilrMzprvcYO9Ib6AryUsYvt YNxAebFQw7nuEBiyji2mdf1YCtIejq8msAXlzACmiB0SxmPyLjHzQ+MhHyFxUncgRaNY ET7bPkppLatdrhxoRPCaGsHcAf3WK9yj1xKa7paPjkbbjhvUENO6mKi7Wn9+gnuaK01H k5wygUCn0Bb+cF+rTWWBJX3aTMOhgtQZfmuJc8fNMRgGXEcKy9AQYfv8VFC5ClTASV/b OPpA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136397; x=1698741197; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=Po8hkhLgdT11zcGD1J746JWFuw482mcI5gZ8Dv79Ub7LsT9XJtFdMeWM77cuINTKQ+ KYKqLpYStSFxlwWKmdd3lHnsSIoD4Bm57Mb52JAeajKd5n6HhCs/uYY5uMUc0M455nv3 nv05JMqjRpHQJSAK2cv9he/t103fsU7BFFpff0nd/IAcU2evpgK6cuUXUmwz8HUfl5B1 K7AlCYireDI0O7wteykmu1qSYu3MYhRLQsaJuVRH/RA6xwLLwrFhCjHQrzmnu/XrvKJG MWb9ZdhcWzDxhuIeZS12ke+AlefOfsusuOesDbCJAiA2m4KOSQ1dMcTYS3z7xqDlwI/A a/yw== X-Gm-Message-State: AOJu0Yz6T33oI/jsy3To7uFkmef2VVHzHFZkGN65TJDFflUMXAoTpug9 EOHVxh4DYTq1IO+E0F89eCbdMA== X-Google-Smtp-Source: AGHT+IHB77N08kpQP3kK7g9QlYWTNYn9tfxBH6TdMNcz14U0iu/fhKvY168Jlzr+1CThhjfwCpOJUw== X-Received: by 2002:a05:6a00:2292:b0:6bd:7cbd:15a2 with SMTP id f18-20020a056a00229200b006bd7cbd15a2mr10659966pfe.26.1698136397397; Tue, 24 Oct 2023 01:33:17 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.11 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:17 -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 v6 01/10] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Tue, 24 Oct 2023 16:32:49 +0800 Message-Id: <20231024083258.65750-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 Thu Jan 1 09:00:26 2026 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 F2C72C00A8F for ; Tue, 24 Oct 2023 08:33:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233917AbjJXId2 (ORCPT ); Tue, 24 Oct 2023 04:33:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55294 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232620AbjJXId0 (ORCPT ); Tue, 24 Oct 2023 04:33:26 -0400 Received: from mail-pf1-x42e.google.com (mail-pf1-x42e.google.com [IPv6:2607:f8b0:4864:20::42e]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 54E4F120 for ; Tue, 24 Oct 2023 01:33:24 -0700 (PDT) Received: by mail-pf1-x42e.google.com with SMTP id d2e1a72fcca58-6b36e1fcea0so3271569b3a.1 for ; Tue, 24 Oct 2023 01:33:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136404; x=1698741204; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=kuVRWVg+GOfFDNXgWomsTeaxeDK5DweWacq3Eh7wQKXo50OjyMnBfSUMh2r9xGvEfT 5cOPGlpVkPwNjL5sT+eqGivC285OAWO8LyWrQejCOA69F4FNVQSJZesTTLXPm5Z7jVf0 83RE/i4wmr4jYUpiwAG5MjzsexAlzEWSxlHjM7teRNWIqujqCbSdIzKR61K71/dOJOXm Ezu6Uj0oBQqxu7nSaliDAlNU2sROr908almnzcXk7xG/Hbj5dCZiS/sDebWuYuaDGMQh IwWnYpTQWHDBYu9DMf9ChpeGRgyLtAAncNwBf4dpxn3UARsGA4r93f7Mbmj6w+OyVbZW Ubeg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136404; x=1698741204; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=BNYfmdconYl863i4K598x44j7q7naRViVC7lvn4vym6O9AtDxyeVEmBPTlSWdZQrEw k8/Mqd3wdrKwEY+t/xAmxMINr0r+UjoGHObEGXq9YcqsIb3/Sce2Fr7tDBo+huDKEyd3 c+UlWb3esqgurE/5LCB46xmQ1vvJsWZZCpbMR24NhofGdkuK+fA+d3LN0k56BpWV5VBu YT89JkErKN0OM02PsGbkLF5gRLSTIWcDXJWY3+60eXbgR9PsWCbz8G8yDT9Rbp4G10eH W0M4NnReGTSQ2f8+TrBdik77fieHxRC6TuRm6MFxeHegfLnIekRlQjH8IoH1BuZRA7jW SHVQ== X-Gm-Message-State: AOJu0YxbmlmhrAKpFwiqhXHppIQWbucDteg2utf7V+mEOJMv0Fptvei7 uGfakq1pkWWahsvZlCA6+4hRfw== X-Google-Smtp-Source: AGHT+IFRF2d7NaEqXWWjz92Xh2LjjQSzD8bGo9Dbzm/HViEErv6yA9g/lWFc+D2a7eTh24RKV68/bg== X-Received: by 2002:a05:6a21:a108:b0:17a:e79c:c5ab with SMTP id aq8-20020a056a21a10800b0017ae79cc5abmr1692896pzc.48.1698136403796; Tue, 24 Oct 2023 01:33:23 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.17 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:23 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, 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 v6 02/10] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Tue, 24 Oct 2023 16:32:50 +0800 Message-Id: <20231024083258.65750-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 Thu Jan 1 09:00:26 2026 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 27EFCC07545 for ; Tue, 24 Oct 2023 08:34:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234028AbjJXIeJ (ORCPT ); Tue, 24 Oct 2023 04:34:09 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44442 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234103AbjJXId7 (ORCPT ); Tue, 24 Oct 2023 04:33:59 -0400 Received: from mail-oo1-xc2b.google.com (mail-oo1-xc2b.google.com [IPv6:2607:f8b0:4864:20::c2b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 38CF5D78 for ; Tue, 24 Oct 2023 01:33:31 -0700 (PDT) Received: by mail-oo1-xc2b.google.com with SMTP id 006d021491bc7-581e5a9413bso2494217eaf.1 for ; Tue, 24 Oct 2023 01:33:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136410; x=1698741210; 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; b=CRCwxaG40xfFuG+dF24NNvdOixTbkaWt+bc4Eey/MsONgmDw7KGdZ+lB6Ij5/OTiai UPdwSqULccRu5AHv1HuSZciXVdfQcAWkUs//OGBMHBqyQ5/r9KzizZChkwQt7Vts9nDE +Rx97bkGz3D38xFthui5vqZaqa+Mr5TkYBAYKn6hbSSHPhJQHDTyD9Fu890tFN64VM6K Qhtsr5D35FBEjDmnwu7oLAc+iw2Xns1FjdfBdKpwUOTZ9Z0sIE6FQ+w8YuatwWS3XgZC jFoFwrOc1ZqaA4hBMssMdeJ9dXwXajdse0YS34JlTH+3BLbTrEhBhOIZHmDL/e+UHunQ xcaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136410; x=1698741210; 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; b=n9LGsz3QgGwEL8RSKjYewPPy17aYnpRm+G7aBhbbUxdaOgisyecGpkSuLlG7e/hjRL 3aCKOwLNP+yThNZAk+Anb3ITik2Folx4GSyKTXs3rOkWxOiwUK5I50Spw4NuPGk1qnon SqCxpCDZYsIn3WuD3gkAWhVA1BZV8osKwuawSaYhzFUardgSOESlYmpcyReaRNEUggCG 4tAoYdTaI5JdpmR1cjhIKrxMpXh7zHVHYOpTDPg60bh+1PTdlu+AYVdIeEqdC0L4m3Hj F+c0//FJkJ6+FF+uJb5LAz96C44AZB+9Mw9fShcF8CGTF2MwmXPdWoMdC4/7PcYMUs1e 3WLw== X-Gm-Message-State: AOJu0YziVIQQZtQgzj17yCDqB4dl7T3sP/Fa319fuD6HhCLGYWuuHH96 ahHz8QkP/V0pzX694sUNm9SKXw== X-Google-Smtp-Source: AGHT+IFrekRN/XNA6lcRh2LlIUyaj0w4/DqtKzTvG93hVgHB9Sh5vAVyOLcohkcwlswlYTz79UBU+A== X-Received: by 2002:a05:6359:8003:b0:168:dbfd:cec8 with SMTP id rc3-20020a056359800300b00168dbfdcec8mr4800441rwb.13.1698136410342; Tue, 24 Oct 2023 01:33:30 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.24 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:30 -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 v6 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Tue, 24 Oct 2023 16:32:51 +0800 Message-Id: <20231024083258.65750-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 Reviewed-by: Liam R. Howlett --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 276 +++++++++++++++++++++++++++++++++++++ 2 files changed, 279 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..6704b5c507b2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4,6 +4,10 @@ * Copyright (c) 2018-2022 Oracle Corporation * Authors: Liam R. Howlett * Matthew Wilcox + * + * Implementation of algorithm for duplicating Maple Tree + * Copyright (c) 2023 ByteDance + * Author: Peng Zhang */ =20 /* @@ -6475,6 +6479,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 Thu Jan 1 09:00:26 2026 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 7875DC07545 for ; Tue, 24 Oct 2023 08:33:46 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233966AbjJXIdp (ORCPT ); Tue, 24 Oct 2023 04:33:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38438 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233950AbjJXIdj (ORCPT ); Tue, 24 Oct 2023 04:33:39 -0400 Received: from mail-pf1-x42c.google.com (mail-pf1-x42c.google.com [IPv6:2607:f8b0:4864:20::42c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7310510C9 for ; Tue, 24 Oct 2023 01:33:37 -0700 (PDT) Received: by mail-pf1-x42c.google.com with SMTP id d2e1a72fcca58-6b6f4c118b7so3441708b3a.0 for ; Tue, 24 Oct 2023 01:33:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136417; x=1698741217; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=ad9/LY11n2zGMzPzBh4fY7fh5YoLYIO5lCS4THCEnf8iUXJ1ZkmiVmkcUJb1y10BzE e+rVe/nmlQlI9e2ayDW0UK87kqxTxHttxQtNLOeiOZbb9KnkdD1x2uJBmWayO9W/PRsH G5EqV1WubywAOgxPDuo6rpmT4UFqWQG655cFP+PUjHwk8yVGJvYuejXvehc6CYnJtzoP DUpvCc7VZWchpLThQCmQCvpBkPOQjpNePY5uuDdUu0Mn9p1d0ovgO5DPc9vWLyuBH0zW 5GMVjg87SGZ9EP+Yt2U6CD3lpkGPnMCNPyd7pl715oa+bCKYQFCN7nQcUDXTcJ1XjPgG 79pA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136417; x=1698741217; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=vqbfSJf6E4btPUZN6/nOjuFBm8zcgWRSJ6H2IMJBUNLAOhS+ChkWv/VoY+IlPrZCCb cPxzd4RdyC6w3me0FAO8hvlBeHiOmzR2y6u6AtBqeHCAVnyzyLHzUiD//p+y1nHrogob YuCcF7KgntLXbz2eanvUESHUP/hZASCbTh8CCbAHurSHz3uCqXiC4cJ8qSJamN66s0tt wh7XqXH9XxiK7ILaceQSNlVslTuMo9kEMrdDh1hX8/ZcutRTGwaiMsm9Au25RlBRSWSF 0U8lB2nxSv3zg0lrjYKhwHDX1D2aZ1+V3CC5j4aw/qKotrtkMUlMjFeyZXLb4wJsPzpK kUYw== X-Gm-Message-State: AOJu0YyYTMNhkQuu/byFMf1u+r86zd+LnSqS7bBmHqjr5eMX25DJxsw7 ilbzLWqnL2+zTbRVhp7p3KAfFQ== X-Google-Smtp-Source: AGHT+IF7YgpjhTzyLSokdtvDXNfCbJQY3JWpF75jJ39WYAp97AHtn6ttEhmwYaz4RKxtcXMftuCXLw== X-Received: by 2002:a05:6a20:9381:b0:130:d5a:e40e with SMTP id x1-20020a056a20938100b001300d5ae40emr2254231pzh.7.1698136416831; Tue, 24 Oct 2023 01:33:36 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:36 -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 v6 04/10] radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. Date: Tue, 24 Oct 2023 16:32:52 +0800 Message-Id: <20231024083258.65750-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 Thu Jan 1 09:00:26 2026 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 810DFC07545 for ; Tue, 24 Oct 2023 08:34:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234051AbjJXIea (ORCPT ); Tue, 24 Oct 2023 04:34:30 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44486 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234054AbjJXIeP (ORCPT ); Tue, 24 Oct 2023 04:34:15 -0400 Received: from mail-pf1-x42f.google.com (mail-pf1-x42f.google.com [IPv6:2607:f8b0:4864:20::42f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 16A5F10D3 for ; Tue, 24 Oct 2023 01:33:44 -0700 (PDT) Received: by mail-pf1-x42f.google.com with SMTP id d2e1a72fcca58-6b77ab73c6fso3055083b3a.1 for ; Tue, 24 Oct 2023 01:33:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136423; x=1698741223; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=BpaBI1sOF3Vg2KWjcsoFc4eim7j4goubh7vr5fO7yf2OFD6D9u1NMFfP02JsctFh3f RjrZj7xmjaiO8WKTinKenvS1pnIthT7wHbInAcO7wdsbdIhKDKeUIuW6Xnw7chgSF5c3 XUut4DcoOKbHzPiTQ7ipTErqYzgTUULhl7DKqTNX3TM5umNYe8+F2J0Kz5ecZDYi2/Fb VJHfFf5fDFJv6327DGsR7BcKcTU6gvuJepgnJBqv6u6pGAdWDFmAhIcEyt3V61K4hrxZ 6JtRRJW/9f9AoyfBktlOtv5y48UHGSVpAlB9XJ2pk4PkG2toX8WTfRP8De1y7EGYoXCE 2/hg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136423; x=1698741223; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=TTOqf5L+9+bfRkOwXiSMMksIzKdzWwFf+ISo5rZ9RwVLv0+JDsSQ8Qfxk34g60UDvG aWufTiyGWQ8VuLhgPtSRgCUkH1cKJpu6JAV29gxWKk1TplCa/zKdC/ljaQr92WWJw8kX HtB9p7EGu7U+POyU/c5QbJ0Y32PSBCYzYg+4UGbazmPcN6yVShBvoIPOQ2XuV+ZEUUvK cD7kPvNRXN/2kGYnXnH6x+Sp7YSzO9vQCva73efOcuOb+03rtlnU998rn5rxt0PesdS2 18v5ySL5VKCa9aY3WFgmrF2n5vKnHlNReO9rE+52DZsB1pzZ0wXgRpq4mC6I3amgkH4p FsRg== X-Gm-Message-State: AOJu0YzNIekEhhLCHnzZG1N+o7ENbL+ttrkIWl9hoPjUADU9CszBJK6K SIuVARAgCVnz+TxbFxA0+n17ig== X-Google-Smtp-Source: AGHT+IFzRPxA82XWrAQS8Sn4M56zSVzHTehtJ70fiMLI3XrPkvHNR56M5baqh4DLBP8UwYKZghrJfA== X-Received: by 2002:a05:6a00:10c5:b0:68f:b5a3:5ec6 with SMTP id d5-20020a056a0010c500b0068fb5a35ec6mr14426161pfu.0.1698136423347; Tue, 24 Oct 2023 01:33:43 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.37 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:43 -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 v6 05/10] maple_tree: Add test for mtree_dup() Date: Tue, 24 Oct 2023 16:32:53 +0800 Message-Id: <20231024083258.65750-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 Thu Jan 1 09:00:26 2026 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 C1283C00A8F for ; Tue, 24 Oct 2023 08:34:38 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234110AbjJXIei (ORCPT ); Tue, 24 Oct 2023 04:34:38 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40354 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233991AbjJXIeR (ORCPT ); Tue, 24 Oct 2023 04:34:17 -0400 Received: from mail-pf1-x432.google.com (mail-pf1-x432.google.com [IPv6:2607:f8b0:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 59B711713 for ; Tue, 24 Oct 2023 01:33:50 -0700 (PDT) Received: by mail-pf1-x432.google.com with SMTP id d2e1a72fcca58-6bd73395bceso3079606b3a.0 for ; Tue, 24 Oct 2023 01:33:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136430; x=1698741230; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=DFkldGMdV2JxmJtnJ2BwYAUGwWXjuXpH7vMPy9/txF2bmv7IAxzKNlda7tFnfBzhrE Z7pWAxLLI6z0aHZ9pJ3N4u2AiEcqqd0J3CzRIyyASI7VkE997XKLXtrWN/KMGzl6av5r K61YgrGTJA97Gs5yThZ1YggtD87zhHjGzq3XRBF6NsJJmB5vU7VO8WVUOgCFtdEmY59z gKN0xeDUcGgkUDHBiU3yxZ6jGIF25XZdFLc9dSDO4DrexPZo7pV+xNoy957cUer4tTwN HjNj3vtdAQ99teS4CFZ1Sv3c107vn+9NFYi0Iykdk3lkVbogEJdgilgF7oAvh6u0h1fC xP2Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136430; x=1698741230; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=Wv7rHIXXCiqwvyLEWhzSakM3XB/m59b/ro9UZ+NXxqE+NgwSn6SJoQ62/onxXpVR3l 9+WuUIThEBqtr1UucogZZ0TT75wX06o0pGHITQQ77HlWo27spIa3UczqbjOKH2XdCwyt ZMdS9+6VWkjJCfUPIiu2F/9E8hMtoJC6c/EE/GCjT1vEkbLF2dKt1YAwyL9Jgw5dIRwy tmlbKv8fREYGjMw00RWvGBBr4p+36fj4zM/jjz3UOjpg3ETYGUsu42HWGvWKMForRNhU WeM4XrKLgD8sm9b0Nbpvat0UtCyAUEHCf3+j8Uq5uEOT27cC1RgF9MmnIhqvuUSZ0ejm 1KlA== X-Gm-Message-State: AOJu0YzuPu6TyYBiUs2NqspoldqqWuoUPw4Kds1BxJtJO5hvT3pfKiEq VF+exTi1wb578gEWfcxkqBauEA== X-Google-Smtp-Source: AGHT+IFGRqPLSl0xQjtZhF9R2vYQNinwziWDialz1aZ2psT6bnUbvTADzmyVrOS+Nnq8WOBVXot69w== X-Received: by 2002:aa7:8885:0:b0:68e:2c2a:5172 with SMTP id z5-20020aa78885000000b0068e2c2a5172mr16021661pfe.6.1698136429778; Tue, 24 Oct 2023 01:33:49 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.43 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:49 -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 v6 06/10] maple_tree: Update the documentation of maple tree Date: Tue, 24 Oct 2023 16:32:54 +0800 Message-Id: <20231024083258.65750-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 45defcf15da7..285e2d2b21ae 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 Thu Jan 1 09:00:26 2026 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 4934BC00A8F for ; Tue, 24 Oct 2023 08:34:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233932AbjJXIeL (ORCPT ); Tue, 24 Oct 2023 04:34:11 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40546 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234127AbjJXIeB (ORCPT ); Tue, 24 Oct 2023 04:34:01 -0400 Received: from mail-pg1-x529.google.com (mail-pg1-x529.google.com [IPv6:2607:f8b0:4864:20::529]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9BDCBD7E for ; Tue, 24 Oct 2023 01:33:57 -0700 (PDT) Received: by mail-pg1-x529.google.com with SMTP id 41be03b00d2f7-5a1d89ff4b9so2314198a12.0 for ; Tue, 24 Oct 2023 01:33:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136436; x=1698741236; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=GqvjHc99IbEBZlveybU0D8fTBBlqe+5Ky0UCXDZB8PFwd279bHDMYd6DNStGBbmDYj ZrF/X5gQG3+6FzoP+wo6/xV+JHpxmEVyFE/bEp5FlnONxxEArr8+kVhdgW6brSJdenIc rW3fn0k6u9xzNZJQuCfokK9CMcg+LzehC2U6+Rnq6+97/iB8CKp+vYDsQDzvwpJOLMOK x9axsO7Bj0h7Qd5rjO9oW3CQVyvmNFRhqhcONU818lCuH7DkZswcSOL+lib8Zy33LKI3 dMjmrg6dEawPdgMnDNO0ezM0C20fT2vrXjVCQ/ElhZpQc0LbBrg6MmtMQutR1LgExcSM 4dSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136436; x=1698741236; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=GFMzOYwWd+Dj+n67yd76VMaI6bt2Z62fFC+fGHXaQRDgWIcljFPt6C7NF+inZCahu7 jWo6h45Zy2es7tF0KYTIevN4lGRV8vfqPFMuApN0tTzDlNbJ+G9CLdpFG6LXN4U/DpaM +46V03llrZ/isVwAUSCr8465weTj5gInSNL+Hs6kfN1xtg2KPbgSEKwI85ED5yM30pW9 PSnn0Llvyq89NNoOxbTOOVfEbFHdQhPpBYpJ72R9AxztFMECEr2Rba7vakEZKjRuDfkj I5k/OwBlQaitPFcBsnhZjzveECPXAzk2o+58tn41UHjyAhQAhtiUCTJ2jtXqVOqsU9Mi bVUw== X-Gm-Message-State: AOJu0YzJ98Cyp+cKlfc+JlhArbF0JIK0S3NN2/fBvsv+wHGjIWab8F+M 3IpDT1H5V5TyYFoK5yLQIG01QA== X-Google-Smtp-Source: AGHT+IF878eTLhy6MBaFtUQubSuP7YPQ3APPj4js3z/kylyjvhAgv4iCwOSuEsZvOnsr4GHMJn44lw== X-Received: by 2002:a05:6a20:6a28:b0:161:28e0:9abd with SMTP id p40-20020a056a206a2800b0016128e09abdmr2218020pzk.16.1698136436387; Tue, 24 Oct 2023 01:33:56 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.50 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:56 -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 v6 07/10] maple_tree: Skip other tests when BENCH is enabled Date: Tue, 24 Oct 2023 16:32:55 +0800 Message-Id: <20231024083258.65750-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 Thu Jan 1 09:00:26 2026 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 1F28FC07545 for ; Tue, 24 Oct 2023 08:34:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233949AbjJXIeu (ORCPT ); Tue, 24 Oct 2023 04:34:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34056 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233939AbjJXIeY (ORCPT ); Tue, 24 Oct 2023 04:34:24 -0400 Received: from mail-pf1-x42b.google.com (mail-pf1-x42b.google.com [IPv6:2607:f8b0:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6A0ECBD for ; Tue, 24 Oct 2023 01:34:03 -0700 (PDT) Received: by mail-pf1-x42b.google.com with SMTP id d2e1a72fcca58-6ba172c5f3dso3475584b3a.0 for ; Tue, 24 Oct 2023 01:34:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136443; x=1698741243; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=MKdirIRHDWMXrZldlkKkyv45rQvdYsahrjj3ySkW2re3bNgn/usFmkmjrvG1A+X+ZG Qa5pbzWhIglQAdjMGoVOBRt/GbewDXZcBnd/3Pu4lnhtnEpe+BJhpKA6bl+30m1oADFQ xmWMo77z9vSOk/4u6n5+BSJbc0gARiBvOANsFOpOK/YcaC/pvckjLtimdFLQ/ieVBoLD qyyzEo85Mhg95wBbyVrRot7Q+mk4K511nB+XeamATfWM8ndtfOLpjP79DeDsI5wkvMJz 3fE9AjE0p8Vu87Y/KuNMfvSEhISNhN1Zl6LXXcGi69ONJY7MmRE2cl3hBeuTH78rTUok U3nA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136443; x=1698741243; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=u/U0voDEeuyPQREfUMeVjV0HJlqpEg3OMReAS3GG46xtg0y8wKCXI2FAblZy6Zy6nw YQemqvxyOW1Hp+LO+fEQGRWKC5xHw3sElpmqOnHTNgdYXsFq/W7L8w0+ZcorBpIGy0dG lOO9q+RoBkZ8QJ4c4yNAe5Q8wpvhiEH21NZ6lFdQfeg42QKHgL3rhQk8LSjVZC4eUJJ0 7YgZ5F/KHF++LDlniabD/6e/JgPEsxSxrE7xPi4/YIqLvEOQM0Ngedbk5TOIG3x8EX+J SGWY5qDHn46QCwFMriPza++YRQFQ2rKoBHC9hxjAuvsd2sEC4NGrN8eHKnISb1zafDjb CzKA== X-Gm-Message-State: AOJu0YxMWqS1ORyM2iTON34jAwo8eKyRJ0Wusca2NkRGOR8mNuSDSrQG Uf42lajJ7U39on60S56C08PACw== X-Google-Smtp-Source: AGHT+IF1zVX8K4BNNs+Nh2lZHYWJzbNrBQiw86QsHKAu8PhANHP4KGmdCF4Yx599tMqieIVTxj5igQ== X-Received: by 2002:a05:6a21:7189:b0:17b:4b61:a907 with SMTP id wq9-20020a056a21718900b0017b4b61a907mr1679463pzb.50.1698136442907; Tue, 24 Oct 2023 01:34:02 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.56 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:02 -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 v6 08/10] maple_tree: Update check_forking() and bench_forking() Date: Tue, 24 Oct 2023 16:32:56 +0800 Message-Id: <20231024083258.65750-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 Thu Jan 1 09:00:26 2026 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 A712CC07545 for ; Tue, 24 Oct 2023 08:34:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234018AbjJXIe1 (ORCPT ); Tue, 24 Oct 2023 04:34:27 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37992 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234058AbjJXIeN (ORCPT ); Tue, 24 Oct 2023 04:34:13 -0400 Received: from mail-oi1-x235.google.com (mail-oi1-x235.google.com [IPv6:2607:f8b0:4864:20::235]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CAA1210E2 for ; Tue, 24 Oct 2023 01:34:10 -0700 (PDT) Received: by mail-oi1-x235.google.com with SMTP id 5614622812f47-3b2ec5ee2e4so2865068b6e.3 for ; Tue, 24 Oct 2023 01:34:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136449; x=1698741249; 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; b=SNEB0fqkUuNyllJMMihVQAlGEvxlD846I1ZA7TkiLKmn/zyiO9QTOKglOHgTOcy7cw YaQlyKeiffS0uBl0lsyehChNpguuAEKJpZsQ442epIy4bfYmwaCX82TCvQ9KN0h3NGUV mxBJaH2rWV1QYqjdWxijJtnCIpnOTP9hu7rIzjFqVqMUYJZUP42NmhsYjTqDZpdFVIa2 rH4ZlQYIjLZVgBGvDx1lkWCUz+ETFTNWdf3q5XYEi5MWtUfNqfG7SY9kwJI6VQ7LHvzy ccFB3SBBXl2A7Qla4vYnkGr+P0ogb5fKONd6b26qNaUv4Jvq4fW3EDpC0hAgGT5zTGbV NUcg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136449; x=1698741249; 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; b=DJuO2ePYeNl5jQu59XzFHLr1A8ZrQj+1aZgHPNHhVyYaNiQMUEY2MoYJuiHWe3ql0W a8oGaNqSZUtBD4OAxMddPZkPhbOUamLmz0HTxNHWiHK/H/BoNCOZ5EQgpuW3IsLi41Cw qXCtO6WN9XtwfB9xP6hB/9G8q7xR1PiN6VVLBjv+TYuMWIfhbfayvR/XXRTyJ5xC7pGe xUlRJv5GUBXry7Xo48w4BnU9LAVYmawf4TGBBPk6FJQ7bvTOqiuZJauAk/g4koPii6Uj 90gYTSdwiZMjjClZ66KW3cZC4e4yx5mj6jQV6/cAcUkOoh/yBP4TTJPfCeiwiE1QTc93 c+Mw== X-Gm-Message-State: AOJu0YwrlXDyUMfTBSoXIUgHWcyyO5oojOJmGJ/YAGQIbsAXqLCWNbLX XSezpLY84AcTaZpNr9m5SMU2pQ== X-Google-Smtp-Source: AGHT+IFL9wgTTdwcf5iN1EU6ZDwg7/3PqxSbUY7aeR+GMticX3N3Q7oIRaxH4CtsM5Y8o0vT2v0b1Q== X-Received: by 2002:a05:6358:810c:b0:168:d6cd:7b2e with SMTP id p12-20020a056358810c00b00168d6cd7b2emr7924030rwk.29.1698136449463; Tue, 24 Oct 2023 01:34:09 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.34.03 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:09 -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 v6 09/10] maple_tree: Preserve the tree attributes when destroying maple tree Date: Tue, 24 Oct 2023 16:32:57 +0800 Message-Id: <20231024083258.65750-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 6704b5c507b2..b9e238e7a7af 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6765,7 +6765,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 Thu Jan 1 09:00:26 2026 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 7A47BC07545 for ; Tue, 24 Oct 2023 08:35:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233998AbjJXIfS (ORCPT ); Tue, 24 Oct 2023 04:35:18 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40486 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233988AbjJXIem (ORCPT ); Tue, 24 Oct 2023 04:34:42 -0400 Received: from mail-pf1-x432.google.com (mail-pf1-x432.google.com [IPv6:2607:f8b0:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 166AA172C for ; Tue, 24 Oct 2023 01:34:16 -0700 (PDT) Received: by mail-pf1-x432.google.com with SMTP id d2e1a72fcca58-6b497c8575aso4179705b3a.1 for ; Tue, 24 Oct 2023 01:34:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136456; x=1698741256; 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; b=cDbOB552h6db4BuaCuIYz243RmuvKZ+aUfLpkVe4LVKmgFYFETTGlPNrIudPP4bmyk tM1Z0+r+O6TOBOTZzRqW6ltrR1KLFBeBpH95P1RcxfyZH7CNhaEMacg8J7qJY6fAGnS4 lKV7c5ei7X9V6noPFGKsDC5Af4uJybdUrpfMdS6F8sEfeOcFJwnL9xlFjg4wEjHfP2sN JNQ8uaCcx2IggFkZPhw3iA4Sxvq25BF3Lvo+RFc45gMVneG/TF7vSQWrbkl6FbcMds08 Tt7bP2JrFPC8saqs1nDuF6PVUfTgYuDedyXL45QxuUV2Y9FMjDS0BE6z8QfoZekY8Y5M 94BQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136456; x=1698741256; 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; b=iDgnFN6m1EAZPa69rrKphuCmdP+buJn6+c0kmZuvApOE1Nfjky9OEGfOeq+mNwto4K IDkAwirVe6044Mzez7J4lRwQRyt9omLXceJVtcGt4pKnN479Jp6WP1SuI6td7KPpUnVT VUxzyM5yy8nLRzpqRuHfoDMmOhGMBUv5zKn44H8m/dc5L0ymX4Ou+B3/IIPjYMmHl3YB edHTPXjarE6nxeYKaCaEcoKlJgeHV33JEpUo4hyMtEU1lfjsTkfDHr5iCO4zrK1iv2n2 3aMfXXelHuv7diGau/GQNX7PYVooW3Uc5V6W10ucbOOU442I/H85USeC1bCmJ1g2MFyW 7uUw== X-Gm-Message-State: AOJu0Yz2b9cBk1+HU2qyqzwg1rOYaqehOYXty3TOyttg/aGcDWO67jPX DFb7JMH17ehx7Vvy94z9GZCjRA== X-Google-Smtp-Source: AGHT+IE1bFuZc+mJSxD+pVgtIXeCVNo3r5g8GwiOKV1aPw1h19MOC16mxaJFq0Q2g2TOYWxaSa9TjA== X-Received: by 2002:a05:6a00:c8b:b0:6be:5a1a:3bb8 with SMTP id a11-20020a056a000c8b00b006be5a1a3bb8mr14049796pfv.28.1698136456363; Tue, 24 Oct 2023 01:34:16 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.34.09 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:16 -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 v6 10/10] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Tue, 24 Oct 2023 16:32:58 +0800 Message-Id: <20231024083258.65750-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-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 b52a526d239d..1825c3b2e15c 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 4f0dfbd5e4bf..163d8f09dafc 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 8b57e42fd980..9d9f124ef38b 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