From patchwork Wed Jul 26 08:09:09 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13327567 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 B6ED3C001DE for ; Wed, 26 Jul 2023 08:10:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 448ED6B0071; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3D0C36B007B; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 24AF28D0001; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 127316B0071 for ; Wed, 26 Jul 2023 04:10:16 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id D7C9CC0D9A for ; Wed, 26 Jul 2023 08:10:15 +0000 (UTC) X-FDA: 81053040390.03.FF6EB31 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) by imf20.hostedemail.com (Postfix) with ESMTP id EB1071C0011 for ; Wed, 26 Jul 2023 08:10:13 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AxvO2W8W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 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=1690359014; 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=Q9dsUg7Mi/WzTn56TpcYztC53dUlO7YtHGzVyJj2ahA=; b=Zys5pMWcxWmSRKAep0PfhcjRpqp0m6KKoX97KX7HoXGPLxIcxLswZBACUJfEa7l0FLkEiK RQP13uasfy3ziTRbfNlbQ+3hQDvNq848ZIpuTDyfn8FSWBct91CDFA0vftXCqQVfShhXVf dfwZ7p7HSfMDZ5Vm39Zy1ahfOtFo3rg= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AxvO2W8W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.48 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1690359014; a=rsa-sha256; cv=none; b=ybocZRlqVMntqjP6aztuWrZMJrympRFnIbZacUQIIRutqhmwO9gomaBv292ehQuuiLb9HP V5YgXsSIL4ECAE+JZE4l0bXpTuu1nyXorDxTNPuDny6s57/C7AnzCvyWxgg/b6HoCRNXcy rNTNyWu/LXvAXpwznBDvqYJZWgpP/lY= Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2680182bc21so1745406a91.2 for ; Wed, 26 Jul 2023 01:10:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1690359013; x=1690963813; 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=Q9dsUg7Mi/WzTn56TpcYztC53dUlO7YtHGzVyJj2ahA=; b=AxvO2W8WmVjCl+8rJI4ixbPJPEirwx12lLH3TIqpROUBNuTlBFTpwIzvimh0rKV5GO jl53Qb/ksDM+V8W/GLFWjp+RoSYw3jS+hUC4AqvaYFObpV+KEgG/doJAkaO3KYxj67D3 hGPB/vbqL0FvtkEDKiSP2uFPrG+vqg6MD9oePIzWQfrkyb9NfNm5I1GxlLLwR2jNR5xw PYqQU1CDGlNTqFeTUH9EsCbpxb5Yp/asxXO7fyvKXIG2Sip5Qaq5nthqVKfov9s0UZnU nig8GQjrdik29VC+VZghqXGcKhCir4shFIkMGLbvr/P68Zz7mLMG8OhUaIsqqlWUdBPz BlrQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690359013; x=1690963813; 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=Q9dsUg7Mi/WzTn56TpcYztC53dUlO7YtHGzVyJj2ahA=; b=KehKSlYo4xh07CzVORXwEMro6kXwEw2oJ57nDFatcIpNjrGSevgl3UXpqjngndvFa8 O9tvwDFSk6K+omABzsDP3/eKaukVTIPDKEptZN604e+3jubkMNX2I/gs1keGWK+OIOaE lJoCUhxkBvrepxGqqSvlVE0HHO5YCkYosikkBvap6tSXzu2LazaOnAk5bOORn3Mbovl/ 7hJL0DnSo45RBQkaEdvI7HSTo/KHbmUUDPiB+zqMB5W/VwN1yk9DFltaGL733af0sLtO wM1OsPN4sBEowTO02kc0zVWww8e82GZAnZCxbMDoJ3FpE/qfOQ+VDlO5bQ3WZJ9MNR7z Rpbw== X-Gm-Message-State: ABy/qLb2AOTfqfJPT7ILSwNSOmr1BgYU+fgVy547BifD7GBt5OKfOQme Hmsvu9bQOw98caSTY0ibTFpNXw== X-Google-Smtp-Source: APBJJlGkN+ndt02hEH/zEFcGhY2t+fQ0s2aGudRsTkYsXiwqyld2+wz2kPDM4ySgqmSJx8lp4VguSA== X-Received: by 2002:a17:90b:1498:b0:268:f56:a2d6 with SMTP id js24-20020a17090b149800b002680f56a2d6mr947545pjb.22.1690359012722; Wed, 26 Jul 2023 01:10:12 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id gc17-20020a17090b311100b002680b2d2ab6sm756540pjb.19.2023.07.26.01.10.07 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 26 Jul 2023 01:10:12 -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 04/11] maple_tree: Introduce interfaces __mt_dup() and mt_dup() Date: Wed, 26 Jul 2023 16:09:09 +0800 Message-Id: <20230726080916.17454-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230726080916.17454-1-zhangpeng.00@bytedance.com> References: <20230726080916.17454-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: 6mrfrtxp4smwq6z666f3h5b9mg5b7u5t X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: EB1071C0011 X-HE-Tag: 1690359013-276898 X-HE-Meta: U2FsdGVkX19VYCuuvzX+h9oeeZ72X2gfWBvsmGLwW2B6GcYNxoI8Am/7b5EruyOVG0SwJNaGz1Tev/Z7EV+WoyA0970UXjXL/k9v/b5WEUUxjrDccpOu1zHUAYqKAh3Ju2fjE751Dj/mZwnHxTrb5jsW9P9u9uXZhb2R4xRWjKyJXgm9V/N8yIClgVpJUk09Qd8+eSfgl2lMAAue/ZJLap/J1qCQEKa0XsTiMhti5XTVLC982DJ9U0KO3GUQDhzy4PzhmiOaSji5qFtFFfDsycn2peYatVBiPbgOh5MRvvheh6g/3ZFhEY4ZExttQIfVDqLgtMET45l2r4TChZVZM+em2O0knubgo84nGPJlXZFoUEUJUdStNN7r6w1xa7Rcv4BXpGP+6+HayQtLc9qB1G/tDAzPdQwaHVIHS9BvScTYmNI0Se/6hUgxPKbQT9yLV12hWmxrN16ZiC4CohAriFlx7WXmQ6JCJqFnKNDj1G/hKg8bWk9QtKdFZOai/g4Lrpxm2GRndRUn4yfZUkre+mGwgXqFDdXwm2WLciE3cE+hx3qIigWmrhfTDK/S1njlHOU6Kg2yQzpinb6yYFFpNMABfXaELORoRiwZBLD4q8shNfJxZ2ZufjJvbds+TFXhs3vZV5kwrFj6EFMXov8iFsqjhW45Wyuj022/kPYP8xQUpjJ35TZdhl0/6EMhU/kIMhtiecd58cqZ1LTtJjdMISD4uUysdMovql9m+KdhXZA6lA3oFWBObFUOpzKokpIbhCMXYeWJ6QpXpoyoek6QBDbLBH6ycIS4BUG35v/kSXX6GPVqhTGhUnGlGGbU2iQ1/taxtYu8KI9UOD/HyOFBZLV2QLBBekPZBdMj7hAy5bQbOX7Vn0grPigXKbYqk9taKxZifJA8p9g2MilCF0UDPOrT4BHdyYqsBtjrtynvTb7Kzio66qY9CdiM+ESnmZwNvOnUclXFOAa61PkZIxe TKFOge+H qXyT4U4wQJt26RQch1eRjbwnvho8Ib2Bd8HM01hofKjNhhKiLtSqO8bTYEJKeEHHAPWSMAaORIQVXpTFLtN3M1yutGZFAJpZ6eLFI5ENV8aTglqQb3HkOOp8ye2D1UDacp0C6ENF4wMW/lCyM/xKpPMsYSZvhXpZwqzHADRPpAH4yknW/ekBcPoj0oUF1EkdeuF9V5/pftUTS1HixX/jqkQderXdNA+RSvBQpHv9/k1GSVroVlAMguiaz0uMzQClNzH4QbqhLsDXIaiJjKa4oBUjLOamLHiiwGI4YJXhoRGJ7ltqmzR/Jd1s9bzFnbaoVKbIvaQWQn7bU+0ldNdsBb5GoiSJ7XJ6abjgvhP9zdWmLw483SWbeCfW57UNIYF8UpOqwILwzVsR0dzS0Cm6qg84JLEut0HCVoe5+bJ7HfQYckmHphJPygku+2jSAJgrRGc0A99eiiWpmQ4C1W/Cxi2LyCg== 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 mt_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 mt_dup() is that mt_dup() holds an internal lock. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 211 +++++++++++++++++++++++++++++++++++++ 2 files changed, 214 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index c962af188681..229fe78e4c89 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 mt_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 da3a2fb405c0..efac6761ae37 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6595,6 +6595,217 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mt_dup_free() - Free the nodes of a incomplete maple tree. + * @mt: The incomplete maple tree + * @node: Free nodes from @node + * + * This function frees all nodes starting from @node in the reverse order of + * mt_dup_build(). At this point we don't need to hold the source tree lock. + */ +static void mt_dup_free(struct maple_tree *mt, struct maple_node *node) +{ + void **slots; + unsigned char offset; + struct maple_enode *enode; + enum maple_type type; + unsigned char count = 0, i; + +try_ascend: + if (ma_is_root(node)) { + mt_free_one(node); + return; + } + + offset = ma_parent_slot(node); + type = ma_parent_type(mt, node); + node = ma_parent(node); + if (!offset) + goto free; + + offset--; + +descend: + slots = (void **)ma_slots(node, type); + enode = slots[offset]; + if (mte_is_leaf(enode)) + goto free; + + type = mte_node_type(enode); + node = mte_to_node(enode); + offset = ma_nonleaf_data_end_nocheck(node, type); + goto descend; + +free: + slots = (void **)ma_slots(node, type); + count = ma_nonleaf_data_end_nocheck(node, type) + 1; + for (i = 0; i < count; i++) + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; + + /* Cast to __rcu to avoid sparse checker complaining. */ + mt_free_bulk(count, (void __rcu **)slots); + goto try_ascend; +} + +/* + * mt_dup_build() - Build a new maple tree from a source tree + * @mt: The source maple tree to copy from + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * @to_free: Free nodes starting from @to_free if the build fails + * + * This function builds a new tree in DFS preorder. If it fails due to memory + * allocation, @to_free will store the last failed node to free the incomplete + * tree. Use mt_dup_free() to free nodes. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated. + */ +static inline int mt_dup_build(struct maple_tree *mt, struct maple_tree *new, + gfp_t gfp, struct maple_node **to_free) +{ + struct maple_enode *enode; + struct maple_node *new_node, *new_parent = NULL, *node; + enum maple_type type; + void __rcu **slots; + void **new_slots; + unsigned char count, request, i, offset; + unsigned long *set_parent; + unsigned long new_root; + + mt_init_flags(new, mt->ma_flags); + enode = mt_root_locked(mt); + if (unlikely(!xa_is_node(enode))) { + rcu_assign_pointer(new->ma_root, enode); + return 0; + } + + new_node = mt_alloc_one(gfp); + if (!new_node) + return -ENOMEM; + + new_root = (unsigned long)new_node; + new_root |= (unsigned long)enode & MAPLE_NODE_MASK; + +copy_node: + node = mte_to_node(enode); + type = mte_node_type(enode); + memcpy(new_node, node, sizeof(struct maple_node)); + + set_parent = (unsigned long *)&(new_node->parent); + *set_parent &= MAPLE_NODE_MASK; + *set_parent |= (unsigned long)new_parent; + if (ma_is_leaf(type)) + goto ascend; + + new_slots = (void **)ma_slots(new_node, type); + slots = ma_slots(node, type); + request = ma_nonleaf_data_end(mt, node, type) + 1; + count = mt_alloc_bulk(gfp, request, new_slots); + if (!count) { + *to_free = new_node; + return -ENOMEM; + } + + for (i = 0; i < count; i++) + ((unsigned long *)new_slots)[i] |= + ((unsigned long)mt_slot_locked(mt, slots, i) & + MAPLE_NODE_MASK); + offset = 0; + +descend: + new_parent = new_node; + enode = mt_slot_locked(mt, slots, offset); + new_node = mte_to_node(new_slots[offset]); + goto copy_node; + +ascend: + if (ma_is_root(node)) { + new_node = mte_to_node((void *)new_root); + new_node->parent = ma_parent_ptr((unsigned long)new | + MA_ROOT_PARENT); + rcu_assign_pointer(new->ma_root, (void *)new_root); + return 0; + } + + offset = ma_parent_slot(node); + type = ma_parent_type(mt, node); + node = ma_parent(node); + new_node = ma_parent(new_node); + if (offset < ma_nonleaf_data_end(mt, node, type)) { + offset++; + new_slots = (void **)ma_slots(new_node, type); + slots = ma_slots(node, type); + goto descend; + } + + goto ascend; +} + +/** + * __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 lock the source tree manually. Before calling this function, @new + * must be an empty tree or an uninitialized tree. If @mt uses an external lock, + * we may also need to manually set @new's external lock using + * mt_set_external_lock(). + * + * Return: 0 on success, -ENOMEM if memory could not be allocated. + */ +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret; + struct maple_node *to_free = NULL; + + ret = mt_dup_build(mt, new, gfp, &to_free); + + if (unlikely(ret == -ENOMEM)) { + if (to_free) + mt_dup_free(new, to_free); + } + + return ret; +} +EXPORT_SYMBOL(__mt_dup); + +/** + * 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 + * function will lock the source tree with an internal lock, and the user does + * not need to manually handle the lock. Before calling this function, @new must + * be an empty tree or an uninitialized tree. If @mt uses an external lock, we + * may also need to manually set @new's external lock using + * mt_set_external_lock(). + * + * Return: 0 on success, -ENOMEM if memory could not be allocated. + */ +int mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret; + struct maple_node *to_free = NULL; + + mtree_lock(mt); + ret = mt_dup_build(mt, new, gfp, &to_free); + mtree_unlock(mt); + + if (unlikely(ret == -ENOMEM)) { + if (to_free) + mt_dup_free(new, to_free); + } + + return ret; +} +EXPORT_SYMBOL(mt_dup); + /** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree