From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 185E0C00A8F for ; Tue, 24 Oct 2023 08:40:31 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A817B6B01B1; Tue, 24 Oct 2023 04:40:30 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A30496B01B3; Tue, 24 Oct 2023 04:40:30 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8F7CD6B01F0; Tue, 24 Oct 2023 04:40:30 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 7F4EB6B01B1 for ; Tue, 24 Oct 2023 04:40:30 -0400 (EDT) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 4564B140B73 for ; Tue, 24 Oct 2023 08:40:30 +0000 (UTC) X-FDA: 81379708620.06.C2F191A Received: from mail-pg1-f169.google.com (mail-pg1-f169.google.com [209.85.215.169]) by imf27.hostedemail.com (Postfix) with ESMTP id 5A9254001A for ; Tue, 24 Oct 2023 08:40:28 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=cSUUKpuf; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.169 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1698136828; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=zSG6ROOKpnRlrNHG2D2oK681AndEjmNyO2Hoar4kc5w=; b=vYkeVzkWnf6nc3R25KjHXj5FLfMr05KdSIbiBdituASnIfJCt5+aUBSxFmkf3POBT/8N0S l38x1qdw1+DojTQfu1w1xnukcycrLGBFPhAeuDYf9bU3Yt9DifCvBwUtkXxEgoxMUqus+V 96sRPJWUZ46lhMOFh7G28lLAaJJS06Y= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=cSUUKpuf; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.169 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136828; a=rsa-sha256; cv=none; b=3flprJC+klEbbYBORxYK+r5ghtQqrH8HNKkNN2xekevcUh0IT0IsVJLfQf992Y08gTEvyb x/f/GvqLsvotYi4LcYhPh6mfTmOhjl325X6Vzekiz1opYIvZPCgRKECSffaJtCKkWWUBb9 FnRas7tKIpj4q+psRu5NeZX1BY6lq3M= Received: by mail-pg1-f169.google.com with SMTP id 41be03b00d2f7-564b6276941so3310952a12.3 for ; Tue, 24 Oct 2023 01:40:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136827; x=1698741627; darn=kvack.org; h=content-transfer-encoding:in-reply-to:from:cc:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=zSG6ROOKpnRlrNHG2D2oK681AndEjmNyO2Hoar4kc5w=; b=cSUUKpufy2GzhoLGqMr2fhCRKf18jDIISMzIPCZynGLNA35K0jspz6C/KTu7vel8fj Af86zG1eguw6VJFOSFkGLgNCCs1eBUuk2WJq2JFB+4JA48Y7mgrgjND8xU6fSI4Pg5u5 WDS6Kg/tqst719MMUU64e4TPcDSp1CZN1X8fKAV0Bk84aQiZ2MmksJ4n9lii3R7a5RYx bc/HuAb4SJXQBRwZkKVkEjHqQk9vtGReW+i2uOwUOUVp8y7JgZNhaOYSodhuir9RLZmO jVZ9CEKkqUgh5sakkva2bj1otH92pwrEKZyArka9OQnoEEKh2ucAA9jVnSsjS8UM0hZy Nhww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136827; x=1698741627; h=content-transfer-encoding:in-reply-to:from:cc:references:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=zSG6ROOKpnRlrNHG2D2oK681AndEjmNyO2Hoar4kc5w=; b=sRAIMkULwmwczJ6zGos2cFO1TSZpt9mpMEE7SXM25Cm5zxNzquAklff2NyrZtWJOQl 7wbrGpW6YbjvT02QULpLv3iX4jn/G2znymXiRQYaEWvjr6FCh76ubVQWlhz8zCO6NKVI zOUBc2S7qjILDuUXu6HL3+dbSVAAqO+2rN3AJYApsFP4+k4oOr7BpLI4b7uosfOMiy4S 5wIyVCwE9ZwqBiYYebPzKXEmhSHCo4JQW8T4vsJA89NXA5PinXLZkgh0tykDbHR9JlVv r/4fNOO2t+hGxRFE3pOmaNqSWuXtLis3B8IsE00h0n4VQErnY6TRqfWYfevtr+64zlER Oogw== X-Gm-Message-State: AOJu0YyGy+DGzfei92h458/BYbveMwIZzmBy8ZHkpcMz2mWKJ8jsfQYx 18DKGoN7HLAfVz40FduPYR1x1g== X-Google-Smtp-Source: AGHT+IGURmvy2ClG8b6odREsOJTJiqJT69btchx33ACRPCyTsPITc/3dGZcAFFMZVRmUpERsVb/VJQ== X-Received: by 2002:a05:6a21:7983:b0:15e:ab6:6e24 with SMTP id bh3-20020a056a21798300b0015e0ab66e24mr1565162pzc.27.1698136827017; Tue, 24 Oct 2023 01:40:27 -0700 (PDT) Received: from [10.84.146.196] ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id 24-20020a17090a191800b00279479e9105sm9543416pjg.2.2023.10.24.01.40.20 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 24 Oct 2023 01:40:26 -0700 (PDT) Message-ID: Date: Tue, 24 Oct 2023 16:40:18 +0800 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v5 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() To: "Liam R. Howlett" References: <20231016032226.59199-1-zhangpeng.00@bytedance.com> <20231016032226.59199-4-zhangpeng.00@bytedance.com> <20231017135717.2iipnd37pgaswzdc@revolver> Cc: Peng Zhang , 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, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org From: Peng Zhang In-Reply-To: <20231017135717.2iipnd37pgaswzdc@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 5A9254001A X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: i8q4mxzt3s3imggngm645a1gjj1wt8cx X-HE-Tag: 1698136828-853920 X-HE-Meta: U2FsdGVkX18v2cBPfhF9QnLMfOAo738mkpLNIvgq0SnzU6B4IUwrPAo6K9hq2fh5tVYr+LjICj6tD3mMwgNXqEHCXe+g8U9MBlbFBfq7ZoRZ1n4fpASSko+7rFNrcuLHZknl5SoaRgbDhdFv1njiEFWp3rNTUL/ccMaFwAC4v13UlgD2Ghz7aMD2LWSW3dqBGSqUBuzxyaegsBdnlscuwrZu9rw5EGMOTm88DDBpJch2YD+gRS+sZWx5seHLJ0JDuZHOnQMmiRqqPhYG1DuyYKxBoyDMlTEPtxSn3i8XjoZ9dSwlasRO24+IjsZ3I26H+xt01huUiRDfow1b7OBkv76rOSr9n5Ps9RusnsqaXo7mRZoYBbHN6+PT2+P7USN9vO6Untb7UJtWeldfCVhqb63G2Mr9Ju145dUeVVklq8DMoAkVZ59MT3Gp7waZVOwuGllYbFU8exVfaf/tWdDYiqTUFwdL1WVusUtiKJ8KXlN6W1xIaVugfbSGAftUxWWWCmGkV7XYXL7IkrzJTXxmF/XTRgZeSm7hAU36QZZaUDYw/Uk8F9WbPPTPhs+k4Y2c2aM7PXPl5yn42MonLEOTucJp1TgJbu9kUFm3mze6a0oZMBf+DZTtL1xgGyBxcivJztMClMkE7LgLaPzlOO12XVMDuJkCOIlHJaYIXJ0A8Y/gt8GQmkhTdL77YjevDYLlToyB7Xb8qtTtrf7V9xt96PFQ07D8clgmYQh1BoChefWy2Pjd+jXwTTG4bVqZKcWkL2weT2xCe9gj+00ZdigWnmzD76xj0KRdR2xfGkclvI76S9wDAVzlFLxvG/Q3xAzUat5nbcSVjyHVGj6zcUmsnkIymJFXBc+qH/KRnB8Dw6yBRoyWbogHeK5ZI4G++YHPK3DrCmYZd9l8uWc8b3sj+vSSPX+ZmhISS1ssTFXQEnABiufYbtncPq7GNzEQ0rc0nZkZKOarhgz6NGFj87r FcqX6S90 H9Ry1PmCwRgCVIqjd3cFmy03KDy7ak+6cPg0Dv24SNb3bstSZPk4VXDT0pj8n39yIaanKpjncuktn2xCFrPUFIsQKYgnGUUZIXUvB7LsmqBtpCzMG2vuNXbyHiTYwyvC5tVJFILWobIsRBavvt+OO5rYnxhMaV8+Q9PzKb/YGaEdC6CHbmzUPwp0S0Ku0ZBjtgdAcnHXRNWZVsJAO8rs53/v3q8YaeL3q1oDbcMfaiRSMtOE+rLCgaPPAwGRd4YV0slJgY8fvLcx+TszXiLE2TBU6MEBnJjkEW6kfinlk20Z1ZPozf8jNzzTfM7KDwg3rR0SeJdJeGywsyJiRG+BeHOd2aYfG5o1RwtQ+CfKbWzm03aH1yuZHnleQ6K5cO8CaNFd0P9b9yxuvcAv5/q9TjYceEHsngJfZvZPykOvYQLC9arF2llAWkGtHT32VrCu9RQas5J1a5fl/nBlaigZn4JQAntdyx0zoCgkOa5yd9GHhwvSJ64D+o+K1LYoOB9BgSiCvjtgajLK1uJzrPX7J0xM9sD34VKNmVqApdI+bGasAqlFonRJnEXWJGGF/vtBnO+fjX0s9paAmcyMbNWW5o6D0S1EqqcTdCbWy0T8nUcp3sJjAbltiEvUG9qcC4lBF12Oahp/fW43CFOh/vmd+4XvGEg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 在 2023/10/17 21:57, Liam R. Howlett 写道: > * Peng Zhang [231015 23:23]: >> 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 = T(ascend) + T(descend) + T(copy_node) + T(dup_alloc) >> Let C2 = T(dup_alloc) >> Let C3 = 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 >> --- >> include/linux/maple_tree.h | 3 + >> lib/maple_tree.c | 290 +++++++++++++++++++++++++++++++++++++ >> 2 files changed, 293 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 index, >> void *entry, gfp_t gfp); >> void *mtree_erase(struct maple_tree *mt, unsigned long index); >> >> +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); >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index ca7039633844..6e0ad83f14e3 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 >> + * >> + * Algorithm for duplicating Maple Tree >> + * Copyright (c) 2023 ByteDance >> + * Author: Peng Zhang >> */ >> >> /* >> @@ -6475,6 +6479,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) >> } >> EXPORT_SYMBOL(mtree_erase); >> >> +/* >> + * 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 tree >> + * 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); >> + > > Please watch the extra whitespace. There are a few in this patch. Done in v6, thank you. > >> + if (mas->offset) { >> + mas->offset--; >> + do { >> + mas_descend(mas); >> + mas->offset = mas_data_end(mas); >> + } while (!mte_is_leaf(mas->node)); >> + >> + mas_ascend(mas); >> + } >> + >> + node = mte_to_node(mas->node); >> + type = mte_node_type(mas->node); >> + slots = ma_slots(node, type); >> + count = mas_data_end(mas) + 1; >> + for (i = 0; i < count; i++) >> + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; >> + >> + mt_free_bulk(count, slots); >> + } >> + >> + node = 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 *new_mas, >> + struct maple_pnode *parent) >> +{ >> + struct maple_node *node = mte_to_node(mas->node); >> + struct maple_node *new_node = 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 = (unsigned long)node->parent & MAPLE_NODE_MASK; >> + new_node->parent = 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 duplication >> + * process. If memory allocation fails, @mas is set to -ENOMEM. >> + */ >> +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas, >> + gfp_t gfp) >> +{ >> + struct maple_node *node = mte_to_node(mas->node); >> + struct maple_node *new_node = 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 = mte_node_type(mas->node); >> + new_slots = ma_slots(new_node, type); >> + request = mas_data_end(mas) + 1; >> + count = mt_alloc_bulk(gfp, request, (void **)new_slots); >> + if (unlikely(count < request)) { >> + if (count) >> + mt_free_bulk(count, new_slots); > > We were dropping this mt_free_bulk() call as discussed in [1]. Did I > miss something? It seems that I misunderstood earlier, I thought it needed to be kept. It has been deleted in v6, thank you. > >> + >> + memset(new_slots, 0, request * sizeof(void *)); >> + mas_set_err(mas, -ENOMEM); >> + return; >> + } >> + >> + /* Restore node type information in slots. */ >> + slots = ma_slots(node, type); >> + for (i = 0; i < count; i++) { >> + val = (unsigned long)mt_slot_locked(mas->tree, slots, i); >> + val &= MAPLE_NODE_MASK; >> + ((unsigned long *)new_slots)[i] |= 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 allocation >> + * 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 tree. >> + * >> + * 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 *new_mas, >> + gfp_t gfp) >> +{ >> + struct maple_node *node; >> + struct maple_pnode *parent = NULL; >> + struct maple_enode *root; >> + enum maple_type type; >> + >> + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) || >> + unlikely(!mtree_empty(new_mas->tree))) { >> + mas_set_err(mas, -EINVAL); >> + return; >> + } >> + >> + mas_start(mas); >> + if (mas_is_ptr(mas) || mas_is_none(mas)) { >> + root = mt_root_locked(mas->tree); > > mas_start(mas) would return the root entry if it's a pointer and NULL if > the tree is empty, so this can be written: > root = mas_start(mas); > if (mas_is_ptry() || mas_is_none() > goto set_new_tree; Done in v6, thank you. > > >> + goto set_new_tree; >> + } >> + >> + node = mt_alloc_one(gfp); >> + if (!node) { >> + new_mas->node = MAS_NONE; >> + mas_set_err(mas, -ENOMEM); >> + return; >> + } >> + >> + type = mte_node_type(mas->node); >> + root = mt_mk_node(node, type); >> + new_mas->node = root; >> + new_mas->min = 0; >> + new_mas->max = ULONG_MAX; >> + root = 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 == 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 == mas_data_end(mas)); >> + >> + /* Move to the next subtree. */ >> + mas->offset++; >> + new_mas->offset++; >> + } >> + >> + mas_descend(mas); >> + parent = ma_parent_ptr(mte_to_node(new_mas->node)); >> + mas_descend(new_mas); >> + mas->offset = 0; >> + new_mas->offset = 0; >> + } >> +done: >> + /* Specially handle the parent of the root node. */ >> + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas)); >> +set_new_tree: >> + /* Make them the same height */ >> + new_mas->tree->ma_flags = 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-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 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 tree. >> + * >> + * 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 = 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 = xa_err(mas.node); >> + if (ret == -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-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 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 = 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 = xa_err(mas.node); >> + if (ret == -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 >> -- >> 2.20.1 >> > > [1]. https://lore.kernel.org/lkml/20231004142500.gz2552r74aiphl4z@revolver/ > > Thanks, > Liam