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 BCE6AE9270D for ; Thu, 5 Oct 2023 15:55:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 36C026B025A; Thu, 5 Oct 2023 11:55:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2F4326B025B; Thu, 5 Oct 2023 11:55:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1480D6B025C; Thu, 5 Oct 2023 11:55:37 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id F0A806B025A for ; Thu, 5 Oct 2023 11:55:36 -0400 (EDT) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id BB08680263 for ; Thu, 5 Oct 2023 15:55:36 +0000 (UTC) X-FDA: 81311857872.04.11B6D0F Received: from mail-pl1-f172.google.com (mail-pl1-f172.google.com [209.85.214.172]) by imf24.hostedemail.com (Postfix) with ESMTP id 065F4180002 for ; Thu, 5 Oct 2023 15:55:32 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=HNkiE6Ds; spf=pass (imf24.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 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=1696521333; a=rsa-sha256; cv=none; b=8ZnQyEsP9Jh6OEmDj7dN41acBAI9RYZNHmumc28XJOaVZ5/4v8pdkkUo3b/giV7WfZPb0M SbF+gPCj68PYYGbq5cGY1Xn3Tgx5MM65tNwxZPnYpXgP+fhU42YXJvCpkM9crl78uavayy BfAkSB4aK4FCEE8H4I/9TcT9xazSrE0= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=HNkiE6Ds; spf=pass (imf24.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.172 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=1696521333; 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=B6GHvHXKLye63Z2R6AMbTUCNlNMN2TmHvg6aKokNpG8=; b=pXpQ0uwnDp6FLJFlSNSEiA6c8MSZIHBXejybKQoWNa+OmAGsdAxpu/fIT9o4mYKn1xIPTf GgaO2bp4kUdyKwQYur63jbB+iVj/8It9iNL8lrY5/BUmutRlZtdVG3J8AEeUqih7/JXvqv xTloCWhpwIwm6YU89vnPDdPoUsmQXwM= Received: by mail-pl1-f172.google.com with SMTP id d9443c01a7336-1c62d61dc96so8177045ad.0 for ; Thu, 05 Oct 2023 08:55:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1696521331; x=1697126131; 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=B6GHvHXKLye63Z2R6AMbTUCNlNMN2TmHvg6aKokNpG8=; b=HNkiE6DsI7Qun1ADMw3UyAkT4WOMEG93R6eOHHigYbsqgswqbj4s0HmFVWbi7W/7O6 VmbX3UBUPAh9RcjeLsOT4MQp19simh1DzkS6H0nBwdWJxtUJhhcjXHw9RV3CmvWISmj5 Bwo5USQfdZgl/zCOfhM4QJArTwOM1uDWsSQcwQMBcdoD6iTbL6wQvbwagf50Hk55Wggi FONkx4ecJey9hIMPHfKHKYgwEOoQoic26xtRDj6JX1pY7M+pGckgNPjqTrb1IbQWazxP 3+kB+maUB0T9/kxthxKD/nrr2m3J0Ule6Be+5SjQBli0K7+wDcu/BB0bLTkkgc108SZ9 K79g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1696521331; x=1697126131; 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=B6GHvHXKLye63Z2R6AMbTUCNlNMN2TmHvg6aKokNpG8=; b=Xog23c9Nggw1k7KrpjFpotm51sdDUKndyPACeQlPfirZrQSQRorFkQgNhx5L1UXknY B4VO+eLbMweMYz5g+NsE/SWY16yC/JqNB/FNHq/6TbOc90z2MH4YHgcHadU9PuwenJuK uKIw6B8eD47gB611C1k+xVr42MWUheTGtzKx58x8GHPTPm9TMjbGkm7sUmtjbrUgtf7f oMCUS5DH8ZkHVXX1CcZEpf5XWuGvK6rHu9NT7OdbTTSMhcEbqKLu08McCkV4rs68p4Mg 9lyn9URDd/7k3eJDAhoFYkpNKU1U1h3Ua3xX8H9J3AitLyaLt1TXxgJ8K/1dF1mPw+8r deWA== X-Gm-Message-State: AOJu0YxDc9l1R6awi1vtY7WALA/a5N6GblXqetpCE14CDtt0nWyxWHyv 0vT13qnf/ntrSqCG6zXwpKanSQ== X-Google-Smtp-Source: AGHT+IEOViGN39UMjclSP3DfBqLU0u0lFVPf+gDHbh32+/GNI49pMCk7rJKE37AKWFZVV7HpGA7kbw== X-Received: by 2002:a17:902:bb84:b0:1c1:fafd:d169 with SMTP id m4-20020a170902bb8400b001c1fafdd169mr5031257pls.3.1696521331324; Thu, 05 Oct 2023 08:55:31 -0700 (PDT) Received: from [10.254.225.239] ([139.177.225.225]) by smtp.gmail.com with ESMTPSA id q4-20020a170902788400b001c611e9a5fdsm1860502pll.306.2023.10.05.08.55.25 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 05 Oct 2023 08:55:31 -0700 (PDT) Message-ID: <867f3fb6-22c5-4dd1-479d-5b148163f2d0@bytedance.com> Date: Thu, 5 Oct 2023 23:55:22 +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: 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, maple-tree@lists.infradead.org, linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> <20230925035617.84767-4-zhangpeng.00@bytedance.com> <20231003184542.svldlilhgjc4nct4@revolver> <7be3abc1-1db0-35a0-0a42-2415674effb1@bytedance.com> <20231004142500.gz2552r74aiphl4z@revolver> In-Reply-To: <20231004142500.gz2552r74aiphl4z@revolver> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 065F4180002 X-Stat-Signature: 4yucumf6wsx1ycu1ekhumebuh3jiab76 X-Rspam-User: X-HE-Tag: 1696521332-3917 X-HE-Meta: U2FsdGVkX1/FmkJAqPN17zcZNL9O/g63ZzAIEbEMEj/cQIu6y2zU7vJck6+u6e/JZrtgwO+vQRM2GPwm2qwZexkVcafmLYoEPNquz32WdxnG7d+FJB8fS+xPv9q1ONVcUhXHTz99xlWT5fHoG7s0Y1NgDje8Aja0UkzaB9Y6n/ypZqtcjrTSUFkD53VHAaHK//RUdPGxq0uK6svlekZMqN5QbqxQZg3TzqlmJ0GwhwrHW0CpP2DBKFEZanMg3yvmJkYTJYRAlDxDdMhnVjnXM4Yt3GGcJ3+cn1Rpt0QR0/KdGflWbN+tQaSoEpKRYfBmoo8riHbLs/i/PAm/gypt+YVCBeuwEhXy+M8CNhnpzjsiKswW5apQKvIr/XaKl86F+wtr4tGUCOdAnyOH3XLiTCuH1OZA+RCu63SePDfNkTfpLTasALFrJA8RZb30RdAHGbO38SQRfG7LmQXxCUFCViT9p1xTVe3TWwlfv5+hz71Jd7xT7n2ozRV0lfYKEw+59913LG4M+3x0Sd3sFyVv+TCo0F6GC2FO68gq9aOLCTyQ/qJI4no++tIVXJsgbbn6ya4oJ5SKQLQ1uQzZAmWA0DgHGVh1D4M2MAqgnQjRXHEi/zwzE/QnWm7q6573FGnWAGxGVYJuGhAcqxMnWHsEisnZzJrSLigo6yteyrjv3LRz4UCy0hc6v7TsqPcK82EZBMK0ixdH9u4o05+N89BhagLHS2zwAOLlY6UFd/hChYdfbOxTyqNrBIqKNfIwX2z2ixSYgnTEPvMNndCJWundMtr2+dXfl+g/56gQ9uMS5LahTzMTXxmm1NykAJ134Kkv2rt6Ek57S8KcsF0e+kgt5Or0+gzNnbe862lzhB1seR+6/C7fMPGzTHzbu8hymsUqkTaaF4sgDRExf8OgjXdNaA6bJS5UD3tPtB2WfSgUnconMKoiVqMBib5nrL8loV87DY362fnKb9HJRIe7ai3 3iHnG4jS SiQ+pT51r5Z2Kd1QOSZ2SI3OpAH+92INn85BWKgZxk97xgb1fxqZSQ4sFa1FMClkessDt3OTBHPPQVeyM4uBdDtz3FdKcNvSRrA7QTH8IBh751ouI708ZCsSEGdxFtL3mOSxoYMcPqbXcfc9kAMU1OFdgZT57+7HcJXnsmRKef4SiJPafCowZOmr8C2g8SGzLKU66ZX9fDkz8xk4bqUj4jVvZohjXYtk6GZ49aVGQ7OGVAkjy64BzY4fuGc+hSyOWDf2b187heDQIVfXTE6Kw1AKWlhBtp9JpFGwqWmwW30W690x4IyR+1W6HKjQr7XyjNuUUhoGDUzRFqpv0fHYQDvZNSjU7+oEykmeCcbJ5svDgeXK0mIMoKhLjE1+yHqwD+8fkV0jbVsfvDVSLxCDplU9VLqmg+dzgDjpfM6RgGvKnl0cLLDhZPcE1Z5E0KKMiNQpZfVO1+WPkUnqPY9dZv4ncEGAnIp6X1nAEAWqxo7NTTbvbqlu5itFe/MpiLosVkPOhPuI3dSLaRdgtrD7VmX3ELKEEzzPF1KVM 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 22:25, Liam R. Howlett 写道: > * Peng Zhang [231004 05:09]: >> >> >> 在 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/ > > Ah, I see. > > We should keep the same functionality as before. The code you are > referencing is an RFC and won't be merged as-is. We should be sure to > keep an eye on this happening. > > I think the code you have there is correct. > >>> >>> 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. > > Yeah :/ I think we should update the test code at some point to behave > the same as the real code. Don't worry about it here though. If we want to test this here, we need to modify the kmem_cache_alloc_bulk() in the user space to allocate a portion of memory. This will cause it to behave differently from the corresponding function in the kernel space. I'm not sure if this modification is acceptable. Also, I might need to move the memset() outside of the if statement (if (unlikely(count < request)){}) to use it for cleaning up residual pointers. > >>> >>>> + 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? > > Yes, just document that it is expected to be MAS_START. > >>> >>>> + 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()'. > > Oh right, thanks. > >>> >>> 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 >>>> >>> >