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 2B4A9C6FA8F for ; Wed, 30 Aug 2023 12:57:36 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AB68E44014D; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A6798440009; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 908AD44014D; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 7CBDC440009 for ; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 5505B1A019C for ; Wed, 30 Aug 2023 12:57:35 +0000 (UTC) X-FDA: 81180772470.24.82EB404 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) by imf08.hostedemail.com (Postfix) with ESMTP id 7BBBE16000A for ; Wed, 30 Aug 2023 12:57:33 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AjHTsoVl; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 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=1693400253; 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-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=wkxl/SiilOD2E8l96oDEorbeTyBu3XhFltMGMQpoxTJMicZL4IOuCXFjG6aks+Mb7nEkPs z6pSp7UIQjm7CoO6UXr06puUP0GRGceNJRKYw7bHUnSOQFYauBEdGIrVGVhK0bdKBxeICf tKnwvbCsOYxOhiBQqXci0soGgmaGHMw= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AjHTsoVl; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400253; a=rsa-sha256; cv=none; b=oGBq0HpnbTrm4NoRSokCoZafkONvBtJlDRuDuNNxSgqDioANEPhXh3yR7FkzZru+33Xvpx zdtrQUL9xUA1N/4gOKLBOKEZcGvDouPDvvP2FUAFststokGn5+gpkAPXuWxoCi4Fb5PIyN gIlO9E8h8aiY9m/dN8d16rOmau8ecWg= Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1c1f7f7151fso17617885ad.1 for ; Wed, 30 Aug 2023 05:57:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400252; x=1694005052; darn=kvack.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=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=AjHTsoVlLA7deCqkT93bvT9sfRVkNHMc87rl77ytbWGAV5ANZblxIksVpIYJlPv5cX 7iaVoR9InO+omG7zNny0J02TcnhgLnryHS09zW6MJho8X23XVFbGD/d+2vfyKX8kgu0k C059On8hPGz1ZfMX4O4SFUWKoQHje8C/BUfGCk8AGOniVZpycC1JeeYffATOuFrog0E7 SmGH7wCAiybTGpzknEednk8qkhU43nxNbqXX7YTuNNdqQxeUKIdU8v+cnOaRrSJKwEJk IOiW1Yfgz7F4EjhUCHyKqO6y5FYdbu0sVpwroW6IuMj4CiIgEnGoaX9MW2akrCTA9p52 6DvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400252; x=1694005052; 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=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=JDP6AGRrpX3/XJATWdPb71iixPDTPh+vEHxsor5r/6QCLiH5quFdo/SUHKXC4v8G2J ylX5OZVinDOb9OPHQuLunGuZBYC01y0lbVslhJ0735yE7BEt8AVE+Wb4V+PyFsvsieKw kpHPhwMGQKZBGDpTSYp7iOJlPjjPQLDmyjpiAdrvoDL+z3dDlDCSLVq15OWkamT+v681 7ojg6w3DNhMP/5oRHGeA+kdLzwTkskTAf5GXfwZLSXAGKFv+yqhLg9WQQNcIDsPacNJS 3SXgNcFw+S7kKrsrc7q0qru0pdA+gYnCuWvsCoUZlPWu9IHNwQJ44N3V15E9MYvntkOO pk/Q== X-Gm-Message-State: AOJu0YwBxHTWaNrVKOlou0CiR5W75hADID8X+YpCgLlhDV8gmG/mxxcC agtIu5YOE6Yqm84bt/2kv4yYWg== X-Google-Smtp-Source: AGHT+IFlsKJ4gsggMjq3Qups2gBw5dyyMz0AGXGO84i6jUNMN2vnjaDbpUxjVunPZt/9zXz+SwW1rQ== X-Received: by 2002:a17:902:edc7:b0:1bb:c5a9:6b26 with SMTP id q7-20020a170902edc700b001bbc5a96b26mr1834665plk.5.1693400252383; Wed, 30 Aug 2023 05:57:32 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.26 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:32 -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, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 2/6] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Wed, 30 Aug 2023 20:56:50 +0800 Message-Id: <20230830125654.21257-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 7BBBE16000A X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: x9ig373wn3ipc7pdpa4a89z6xr74htii X-HE-Tag: 1693400253-341767 X-HE-Meta: U2FsdGVkX19UMUlKHUcO6otD3NIiBnJVLykKaRzmMS9fdMn+vfgKpu+Y+APufcjBtRFEo6SBuZZ8AUxQKMO+S9U3QDpKURU0Lsesh4eNluczuAZ5i2bgcGna3poYT22TWiX6eFSP2JcOEhaxbq73hA+Y1geH4A4qzpja97EvaRUz5T1yudewPF8JX/ppA+dnrLwBnBtTbO9eSlv2rcurN7aIVcW258Sq+SLvhIl9Xn3+FjKNm3QhDOioVjMohQi1Yame1M9fDqbnzcGjDKE3d7Fpzy1OQPpl7dzHk205n8WFD45GklnjM+GLt7AFV52JMCl9aIEr8nOBoktQkh48qSirMrhGU713Z4y2YVQf+F49wOwc5k5AjBChR99BiBW9gbIFgFslL5VwnZh+UJCnYL2rb0wMRdLU9gDEX3hP9M1Ri82ay0oRbDydRGGlJsL6eGAXxQ982szyCg/m44Cj3IedPZLfpi+uO2Ziba7D1uB8ZX569yTzvWGNPYm3VpChxPKQZmInWG9+d9g0nhXuIm1GWh4fycS3EdI7LxQVUF4gw3EeO6Lwe0Rg7MIkme1roIa815IhyLneeChAc+dUwkm9NLVmQjKMe5J7LleJfXk5pZiRqlGDT9x2P2TW6n9Z222MKvTpH43BHnBDnsKmDoDnCp8ZMxHQLftalxLLZx325WNh52dw9Rrq97bmcrCKfghOzFmfZNdad4e7eOymzTeZLrsLjAKlSPj5OGXZFt5GIuRlt1bgzr+2T87OFthOcGqMSUCDvKC4yExm/6FyU5iBmNAwMcuUWrt5G8Ut1a4Iz5DAJmKaVMYQB5Ov/TmxNVTcM0zEFyXsp+Up7jfcz+6tfnEtZmFkTLSDRfQx8Jov27nOTo+DCyNnZEmto7Ga0F1EmP7sseOreloxztjXTkRBUnWbDTso0mgR3/uFKn6PVHb2e9YvigOKjhUzsH5w7BTrDsLvX/bKe6ABek8 xeoGduSw pn08SmQbfJBVk3tcIZoV3JOrGMytGUySJ8c6n+iP7h/dHWWZOqpGVtcr/NLj5qshsU0PdWvBKhXu8VSg0XJaNHx+1WkUCPf32hzG6K1awbGrwnBL2/QRqdhpSflev7waM6Lu0U6ZDBFR2ClQ4LDNofDb3YLUZlBsfVMIpi0CngRyBlCYl4G3vK0NnTVObj7Topii/LZPfQpKcNdZMjXP4fSutOU5aORtVhcG9qJTG08kJ+15H+IyU5TyBnY5ZUjB8mWabAIF8r43kSwVHFFOlYngVy49mmGZEAwWz+ns6lsgY+tIYCe+KnYy2JlETngTz2CK/nzCZ2BeV8F2e5MDU8A5wUlj6pZ6n7wHqW/AtxWuGP8qEtXOq/KnLSNN/G8VUIwDD6hM3HmtdGEgKoTsB4phR5dW9B3/QbU5eVanPjGyPqSGhgsaxSdC9TZWCD/mV30X61NDyJOuxWT6IWyLS546/nA== 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: Introduce interfaces __mt_dup() and mtree_dup(), which are used to duplicate a maple tree. Compared with traversing the source tree and reinserting entry by entry in the new tree, it has better performance. 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 | 265 +++++++++++++++++++++++++++++++++++++ 2 files changed, 268 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e41c70ac7744..44fe8a57ecbd 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -327,6 +327,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 ef234cf02e3e..8f841682269c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6370,6 +6370,271 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mas_dup_free() - Free a half-constructed tree. + * @mas: Points to the last node of the half-constructed tree. + * + * 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->node) + 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 = (void **)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 allocate child nodes. + * @mas: Points to the source node. + * @new_mas: Points to the new node. + * @parent: The parent node of the new node. + * @gfp: The GFP_FLAGS to use for allocations. + * + * Copy @mas->node to @new_mas->node, set @parent to be the parent of + * @new_mas->node and allocate new child nodes for @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_node *parent, 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 long val; + unsigned char request, count, i; + void __rcu **slots; + void __rcu **new_slots; + + /* Copy the node completely. */ + memcpy(new_node, node, sizeof(struct maple_node)); + + /* Update the parent node pointer. */ + if (unlikely(ma_is_root(node))) + val = MA_ROOT_PARENT; + else + val = (unsigned long)node->parent & MAPLE_NODE_MASK; + + new_node->parent = ma_parent_ptr(val | (unsigned long)parent); + + if (mte_is_leaf(mas->node)) + return; + + /* 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, new_slots); + if (unlikely(count < request)) { + if (count) + mt_free_bulk(count, new_slots); + mas_set_err(mas, -ENOMEM); + return; + } + + /* Restore node type information in slots. */ + slots = ma_slots(node, type); + for (i = 0; i < count; i++) + ((unsigned long *)new_slots)[i] |= + ((unsigned long)mt_slot_locked(mas->tree, slots, i) & + MAPLE_NODE_MASK); +} + +/* + * 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 half-constructed tree. + * + * Note that the attributes of the two trees must be exactly the same, and the + * new tree must be empty, otherwise -EINVAL will be returned. + */ +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node, *parent; + 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)) { + /* + * The attributes of the two trees must be the same before this. + * The following assignment makes them the same height. + */ + new_mas->tree->ma_flags = mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, mas->tree->ma_root); + return; + } + + node = mt_alloc_one(gfp); + if (!node) { + new_mas->node = NULL; + 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; + parent = ma_mnode_ptr(new_mas->tree); + + while (1) { + mas_copy_node(mas, new_mas, parent, gfp); + + if (unlikely(mas_is_err(mas))) + return; + + /* Once we reach a leaf, we need to ascend, or end the loop. */ + if (mte_is_leaf(mas->node)) { + if (mas->max == ULONG_MAX) { + new_mas->tree->ma_flags = mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, + mte_mk_root(root)); + break; + } + + do { + /* + * Must not at the root node, because we've + * already end the loop when we reach the last + * leaf. + */ + mas_ascend(mas); + mas_ascend(new_mas); + } while (mas->offset == mas_data_end(mas)); + + mas->offset++; + new_mas->offset++; + } + + mas_descend(mas); + parent = mte_to_node(new_mas->node); + mas_descend(new_mas); + mas->offset = 0; + new_mas->offset = 0; + } +} + +/** + * __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 using a faster method than traversing + * the source tree and inserting entries into the new tree one by one. + * 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 using a faster method than traversing + * the source tree and inserting entries into the new tree one by one. + * 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(&mas); + + 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