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 5683FE8FDDE for ; Wed, 4 Oct 2023 09:09:48 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 918586B027C; Wed, 4 Oct 2023 05:09:47 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8C7A66B027E; Wed, 4 Oct 2023 05:09:47 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 790246B027F; Wed, 4 Oct 2023 05:09:47 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 670ED6B027C for ; Wed, 4 Oct 2023 05:09:47 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 3E37CC027A for ; Wed, 4 Oct 2023 09:09:47 +0000 (UTC) X-FDA: 81307206414.28.AA78F68 Received: from mail-pf1-f175.google.com (mail-pf1-f175.google.com [209.85.210.175]) by imf06.hostedemail.com (Postfix) with ESMTP id CD0E518000B for ; Wed, 4 Oct 2023 09:09:42 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=az5RISAS; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.175 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1696410585; a=rsa-sha256; cv=none; b=wrVRBdvLU+oMCwwFf4hZv5OAUtLCt4MeTHOvlo8vNLXGqodQfup/+NOxDmJf8eIX2Yh/eT 1QZQrTKx1b5k4Hwy4fxo3SVorxNRRKWs3u6DVVvmC5CmRq1K/q0iTU66Bmb2mMiMQkALb3 rqgW0K5co9ZjZ4P6dImo8Qx6Xp2/KJg= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=az5RISAS; spf=pass (imf06.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.175 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1696410585; 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=4Mlg3qmdzGa2/sOSr+GySj5uG6qeYzpAKzoJclP2pzI=; b=4DvfAeQsZfiK2lVCBnyh4b3q4G5/PV57ltxh94aI6hrUelRXcgrAKB5bun/51I31VyhpSG Qj1Yx4Dg6JeMHUIMu669rA6y6YjC9VxK2U1Vetia4n7eypVbofYWaKVJdZ6MNIcoCgah3I mhaqQD8rlNOM95Ep94vAC5wgndonZMQ= Received: by mail-pf1-f175.google.com with SMTP id d2e1a72fcca58-69101d33315so1542761b3a.3 for ; Wed, 04 Oct 2023 02:09:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696410581; x=1697015381; darn=kvack.org; h=content-transfer-encoding:in-reply-to:references:cc:to:subject:from :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=4Mlg3qmdzGa2/sOSr+GySj5uG6qeYzpAKzoJclP2pzI=; b=az5RISASQEtKcGqpyJCTYkUDAoaHI+lgC+FwPivNHpInzpOrnOdgRf8EtFwJURcLDI HCUIIxZV6htrkFMCKGE/zHNTQJC7FvipCpJJKGfZbKpl6XpsZrQheZG8PWCR+EeCnkYd 2zBk4YjmyYcfJwu1KJCgQgLubV5D9vCSkdEY85OY9JC3PU80mI5Ec8mJNc0dDLnpd6TE 2+9qRq0tGSy6Ik36/SXs6J4d0gmQHo2aO1Hzlf/l6ONc3Ia+RO/BQq2U4DRP/S/be2Tv /nItY3X8ByJ5wkCWaOirLhIF20/HumvaFLArHk/WuW+9hyjG9Qr9GWlsufbJVJYzcYMv pPFA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696410581; x=1697015381; h=content-transfer-encoding:in-reply-to:references:cc:to:subject:from :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=4Mlg3qmdzGa2/sOSr+GySj5uG6qeYzpAKzoJclP2pzI=; b=miX0s+hRWJJZH5nsBWwNSaXE0cZ2XPB8/dDkvzjoaJftL2ewQmSw97zxrYeFFZzc5x HUAI26WxsSdpkw0NxgILPJ8qFwFSEpTAGvr5tnElhXo5g984URKA5hm3ReCxXsI6k5eh 6W5rASukaISM5tbCIMpItibSBZsbjM7X5ngbToqxajR/Wuohl4WCzR5tUWVga0aXqP5B 8YTSWIZ+fMi+a3xE8UyWDRr6XScCLjxQHt7Qfm/g5P+ct+/CP2LGTWwaWKTE3siOanOY BGKVt8hV2XJ2RXfYq22swoLFmOfXnmPeeUKBDl8S0+2SXv+nl/Jkq4UbPDmTlySXO68x crog== X-Gm-Message-State: AOJu0YxgW3NcPpz+z+b38IUCvlrghgb4mlm9NEakQiTEPjwC1/68j0uF DKFxQde68T6/dZOpzlAStExgdQ== X-Google-Smtp-Source: AGHT+IGzYX1ZcA7LZgT1KuL+GqkQkKAigEf6i09R4CzkfEMrdRimdzIvgBUqIQyaG+yeNg827B0+1g== X-Received: by 2002:a05:6a00:244b:b0:68f:b3ed:7d56 with SMTP id d11-20020a056a00244b00b0068fb3ed7d56mr1985020pfj.34.1696410581181; Wed, 04 Oct 2023 02:09:41 -0700 (PDT) Received: from [10.254.225.239] ([139.177.225.225]) by smtp.gmail.com with ESMTPSA id i8-20020aa79088000000b00690c9fda0fesm2742626pfa.169.2023.10.04.02.09.35 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 04 Oct 2023 02:09:40 -0700 (PDT) Message-ID: <7be3abc1-1db0-35a0-0a42-2415674effb1@bytedance.com> Date: Wed, 4 Oct 2023 17:09:32 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.15.1 From: Peng Zhang Subject: Re: [PATCH v3 3/9] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() To: "Liam R. Howlett" Cc: 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, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> <20230925035617.84767-4-zhangpeng.00@bytedance.com> <20231003184542.svldlilhgjc4nct4@revolver> In-Reply-To: <20231003184542.svldlilhgjc4nct4@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: CD0E518000B X-Stat-Signature: wrcgtnu9bi7bczs8ca9dxgqdi9myrumy X-Rspam-User: X-HE-Tag: 1696410582-231394 X-HE-Meta: U2FsdGVkX1+CyH7zTY9aZtnATnx4JGRg/bRW8l8xdUV6ZbyL2JHbSs0Uk62cp+r2YSqO1kPHR8FpxJLFfRe8um9HLXveRQAtjeQXiVxqIdnyYnFyIZTPcA7ba8PmeMitL+CtNNIvoJygbgnTyORAYlq4lG0JpU3BV/Rl5wEspbW+ABBOmoufDkcZ8U7Sx+vEYiL3KYZL39dmrtHdBITLNds/mQujWXwEnzxB/yhYZJurxl/wJT18aS9R+GH6v/MAfXtpLC77IXYcduDpQ7LRAVNHjKKDse205t4hgdw6298doHm19iqWQjSUo963EWl94IG4PuP4hoScvi1cmcSjEl+rPg6reL/YizOT4MlEItAyU6JJjfqC2VSvhC9//+1DBar4TtSdb8pvqQuVofLCJs3i540GJeSj9AReAr+XAu1z8jbdPGBiiE4bZmA9hkK8sMvw9F2NZIky36hT5TpbxyCA9qX2naBD4y5QEKlLf3NziECLM0YGJ58Js1GYfiAnbQzrxzY23WMhk3eVYB/eL53ipOPDQuzc8Jnj8tKXPeryXpYTCboMYtHLg+Au1vyOXQ43+gZPjjNGIZ8UpZhYVIm4AiZlJm9i67oci82YNy7x2yI0lwFFq7+/e2qEBZU69qWFo+0Vl7oSIe0/3YHAckzHR5cnDgaf0B88C5cohsTpblMan7sUstYE3bRIxHAHfY/G8TcGz5Iy3zptuGJv2YjmQoYVl5FR2z0aEjoq5kPniMTQ1/Ns4+A2cZCbdjlLY9ykb6KiqeCr6IkDal+2jh3qlJj2VrcxOKfUr35HKCSO2bk5Dlcq3l/dU849vgpVrC6OrZnWeFiyQlOV8XNJto+S/n0vIFGt/iSEcfcJIbZzVS1xCnvostIQG4jcmo8BV/vJnZUonzPI4UvxXG0A1hzL9WlU7vurG/nBIUlDcCPUncndPgRiPbhUiC0fxcjvcI3svAhq7IIQA+y4YqZ JUrnuTOO poR/sKFBJiQ08gYUfDB6zf0zrpZWL0+eiolel/5q6J/yaDoIvZ1lntMfPBB2uLBFTvxHDueP5p00+xSHNs1lq3mn1KfcTHpd6LO5pNUSID8d44onuIPm49+1wd99gMa7zuBXTTQuluhDyiGwcZHxCzmsJ7u8VJOjQe/Wkt1EcmNqvNh6m3n/i3sfaYHuI5xIwVEF4dCH3R/1Rv2BRVrmPyW8ATjxBh7FyRQXV0JC5Tsrw1uS8J6zDr1tu+RbIsNIvnES+q5kcCpLxxO+1sl6MpV/3EAsFqaG7v8zBHt5jLUChxyaL4g26ZJ2DALd4BMKOFNOYG2iOw4vYu23NplDyOmRVVYtL9DIBJrbZ5ojhnvo6FR7nA5uC/zdvTX1Cg4dtc4oiMJtb2Qlj/+OOFphshYJD5cSSh7D5malRIhtvsdJtQda/be78FB7aqHs42un5cBW/gRKQiMTH5PUCdHpzfDyX0t867aVWuu2GoaylkrYbt5S0uL8ZCmk6uKT9+U56QTcaDL20X3FesFEAQmzWvGgsMHqTJ8pM3Zrr 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: 在 2023/10/4 02:45, Liam R. Howlett 写道: > * Peng Zhang [230924 23:58]: >> 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. >> >> Signed-off-by: Peng Zhang >> --- >> include/linux/maple_tree.h | 3 + >> lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++ >> 2 files changed, 289 insertions(+) >> >> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h >> index 666a3764ed89..de5a4056503a 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 3fe5652a8c6c..ed8847b4f1ff 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -6370,6 +6370,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); >> + >> + 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); > > If you look at mm/slab.c: kmem_cache_alloc(), you will see that the > error path already bulk frees for you - but does not zero the array. > This bulk free will lead to double free, but you do need the below > memset(). Also, it will return !count or request. So, I think this code > is never executed as it is written. If kmem_cache_alloc() is called to allocate memory in mt_alloc_bulk(), then this code will not be executed because it only returns 0 or request. However, I am concerned that changes to mt_alloc_bulk() like [1] may be merged, which could potentially lead to memory leaks. To improve robustness, I wrote it this way. How do you think it should be handled? Is it okay to do this like the code below? if (unlikely(count < request)) { memset(new_slots, 0, request * sizeof(unsigned long)); mas_set_err(mas, -ENOMEM); return; } [1] https://lore.kernel.org/lkml/20230810163627.6206-13-vbabka@suse.cz/ > > I don't think this will show up in your testcases because the test code > doesn't leave dangling pointers and simply returns 0 if there isn't > enough nodes. Yes, no testing here. > >> + memset(new_slots, 0, count * sizeof(unsigned long)); >> + } >> + 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. >> + * @new_mas: The maple state of new tree. >> + * @gfp: The GFP_FLAGS to use for allocations. >> + * >> + * This function builds a new tree in DFS preorder. If the memory 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))) { > > Would it be worth checking mas_is_start() for both mas and new_mas here? > Otherwise mas_start() will not do what you want below. I think it is > implied that both are at MAS_START but never checked? This function is an internal function and is currently only called by {mtree,__mt}_dup(). It is ensured that both 'mas' and 'new_mas' are MAS_START when called. Do you think we really need to check it? Maybe we just need to explain it in the comments? > >> + mas_set_err(mas, -EINVAL); >> + return; >> + } >> + >> + mas_start(mas); >> + if (mas_is_ptr(mas) || mas_is_none(mas)) { >> + root = mt_root_locked(mas->tree); >> + 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 a maple tree >> + * @mt: The source maple tree >> + * @new: The new maple tree >> + * @gfp: The GFP_FLAGS to use for allocations >> + * >> + * This function duplicates a maple tree 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 a maple tree >> + * @mt: The source maple tree >> + * @new: The new maple tree >> + * @gfp: The GFP_FLAGS to use for allocations >> + * >> + * This function duplicates a maple tree 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. > > The requirement to duplicate the entire tree should be mentioned and > maybe the mas_is_start() requirement (as I asked about above?) Okay, I will add a comment saying 'This duplicates the entire tree'. But 'mas_is_start()' is not a requirement for calling this function because the function's parameter is 'maple_tree', not 'ma_state'. I think 'mas_is_start()' should be added to the comment for 'mas_dup_build()'. > > I can see someone thinking they are going to make a super fast sub-tree > of existing data using this - which won't (always?) work. > >> + * >> + * 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 >> >