From patchwork Mon Sep 25 03:56: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: 13397201 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 CD39BCE7A81 for ; Mon, 25 Sep 2023 03:57:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 26C066B0146; Sun, 24 Sep 2023 23:57:56 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1F6EE6B0148; Sun, 24 Sep 2023 23:57:56 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 020056B014B; Sun, 24 Sep 2023 23:57:55 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id E81A96B0146 for ; Sun, 24 Sep 2023 23:57:55 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id B6DD5B3C16 for ; Mon, 25 Sep 2023 03:57:55 +0000 (UTC) X-FDA: 81273761310.28.DC573AD Received: from mail-oi1-f175.google.com (mail-oi1-f175.google.com [209.85.167.175]) by imf28.hostedemail.com (Postfix) with ESMTP id E5941C000A for ; Mon, 25 Sep 2023 03:57:52 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=gYKA56bw; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.175 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695614272; a=rsa-sha256; cv=none; b=OQ9Efvuo0lkIbJQZ159jITc5I7f9cP3kVEOWA/nU1ibgmjx9bun4SA5YXZ8jy6tkfCfseE yzA6xnOO/fyvEQmPm21Oa1IYI+xQ8xFkyaNkGmsoeYvQ8ZQcJYSILjowI0tSJkZBx3eQxr 9EPdxw5M1peDozxdII0b5FRwVrKbHno= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=gYKA56bw; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf28.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.175 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=1695614272; 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=N+yL99gNcpn5/1bA5Ytv+b9WTtrbhVjUMVj2M753OVQ=; b=fmYzhuwPotT/rvtPyyKbGVdAg6XHb2EH81Y7fhqBnoI9VACm8psWKJzSm3w/ydAlZ7iQB8 3D+me/Q0zhSMSfK23p5IebByadHtpeyBRojymkmTg1F+aQeWauE/KOtYG2V9rckgL2u2Xw RVvmxDd54OXpuqz/aidU6w4oTQLH9ec= Received: by mail-oi1-f175.google.com with SMTP id 5614622812f47-3a7f4f7a8easo2562485b6e.2 for ; Sun, 24 Sep 2023 20:57:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614272; x=1696219072; 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=N+yL99gNcpn5/1bA5Ytv+b9WTtrbhVjUMVj2M753OVQ=; b=gYKA56bwn7wraWUXuDd/v4njYpQTxHMSMfHSQUWZjsswAu/xlf9rGKyJY0qGdMZTdk lEokJL38Bec2ctgJhVQnA9tIQKh31o2fdtNF7pwL3UN0fIJme5UIa+MmDBoxyGDAN53J lTBBO5T0nfBmZDr2qLBWrY2JuiatcG+KRqbyw0KgKvK8e0y6lveosBc/L6leFgBrI9uv 0IuKsWaBfLzDV1LWF017tOIGclLk/0JduMWgeYzAcnGR3ObX3i4ZKbfNrxOaoVFT3c0o jmEgABjdF0+OGIK4pwa0I9/Pq64QWTH2Jy0np/C5Tf9xI8HyOLKVo8So/mHcdO8q8rtF 6QsQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614272; x=1696219072; 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=N+yL99gNcpn5/1bA5Ytv+b9WTtrbhVjUMVj2M753OVQ=; b=H9bP6D/OWZk2Rm53/7iAQEm248orKthRP5JhkffRRx4pzJInCioMxXiehWFggVxxr+ qcA1e87D9EswpA+dNU4qSNEUE+5UnfmK7XNk8Vi8C/GaNeIjvHX7Isq5aslkwCeGZWxh gBtmuYzxpEU4smIJBxNL4iQ7umxVeeh5UZpsSbxD8d6LrKA/Gix71Q6UfnXuMgdFDyLG XpakE4QMNwTC3xRHVA5ha0MGmiTK70Og+B9JEnzYjwk/IRTMdmzfhksjvsYS4URH9Ti0 pjoB4kBOmWVjQLM5gClo5AfD/+JYvXA01ZkvZ54IqEbrMA7NvRI1sgu6RWyZkzYx9rPj KHAg== X-Gm-Message-State: AOJu0YyETA0ITu8cvx2/sMsWrA7TnR4FX9ppcESQ50+70x5OwLmMvPGy ERT4c2iMOCQiw1dYCziWgGIssw== X-Google-Smtp-Source: AGHT+IGG/pGqZzmPoaP75aVcvq8nPu3sTd6h1U/TptNp61/MFYSLV+D+w14uPTsm2angOH/I6VmfIA== X-Received: by 2002:a05:6808:4d8:b0:3ae:2b43:dd52 with SMTP id a24-20020a05680804d800b003ae2b43dd52mr7344221oie.22.1695614271943; Sun, 24 Sep 2023 20:57:51 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.57.45 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:57:51 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 1/9] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Mon, 25 Sep 2023 11:56:09 +0800 Message-Id: <20230925035617.84767-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: E5941C000A X-Stat-Signature: 4oppggxd1u81zy18mwy11f5q6a6hkw6s X-HE-Tag: 1695614272-943308 X-HE-Meta: U2FsdGVkX18ve2GA6Ad+APy/XI+Pw48gSAspzICpDhW59phF3dKc5e0lObz8JwxWyiK3fj9re94OIgbSvTK7PhzBzd5h5wGyex22jfEyz12281C60lxkzN8MvkLZ+GU7M1YbpZovIqxOz7TPfLn5wPJAuJ/9+AhsbVQet/urVUC7L6NCnoOch/PahDH+P+QBx91V3Ro62SSg5pCWmTf72hqQa7CmICBHyMnu4/hEJlQsSR3JaGcf7g2gIDuRkDUKhzP/T6eUUgANnQgHKhK94aLIBPidC1lBklxXJiGSdHYu4tR8UMP8Hbwbgi4CeYY0u1cghnw5T61JbWtzq4w6NGy+fl0hKgmoKj1c9UdHqwcePp1m0WA31n1ZeNFs4XD/JIKYen1MN6XPFXM+QOCyfPZ4c0da6rW+NGQb9++aIhoh8NlB2gxSXgZIN6pBj/zPG6ekQBlTW2bh5bYHFGXzZ1p3XrkwJG+tLKL07uQRobYT5aw7zfUReSUyaqnsZvVrIgmxB8iaSFp9x8hAByXBBrKaOkLRDIhXyEL3AsIP7l+us2dvag0y3X2SWivaQKNk1HpUINCcEzp2v/7vdxCKjDkHhor3HjdpOq4NqZ/YTd80xaCd8uS2lehyA+AnCtQdQnYXzQFCGMhbmR/xw4keVaAmfLdPQ301PyWf4imvRpAwx3sIifnL068wIs5XfCKY+PYve51+WcQXIP50jHRDopXBJdann+l3Y2EnnGfo6hMYM4YKwUEhcXvkEq2bFfZhwxdpxLD/vRG5uNKtlQqVqRlJhgoVdDfMxLFRZvXljkQdqOtlL4cJtEaiDk/ibIVY6VZl6KkTPc1TII5X+nJVP2O1qbQNIbaH1QgsqXz2uN4J8j0Y9NqgT6dZUo+BF1gvExxHXaXo/nSF8ckPwmprdoX6Y7xcA0e8GXH3sE9R+YT5jEEYpB0+2H//pPkPI2q8LX3+EUZxc85ML5qnbGB DxqVXwJq tda+4xe34fuL6kdg6AdIlNJTkckpGEJc1pxFzN0S2GIgitTdvQB+F1HROC4k7J9wXjTo8xnrs6UWO8sl/gJEvuPAq032lWAc0RHTuDirQYq99ZXNMj/Yb4bdfFULE+9o4+GX35C1m8foju/oqNWwWlFXKMNKwukKjpf5XEUKD4JTaXwLSQYohAdmTanlXLxCg+aihaxhq1IKagm6WM7IRK4W+katIsvs1WJxNzBLtqhZJoF1RsHAJe33RWhwmgVCN1IYD85a2vXNRUxSzxGwN+vo4KeWpz/9MipKeOmgGP7HFjxYSjx0CKKeo/OyIxK6Ns36ncEHHJetpBU5vN2GfUsfIIpTlQFakGwIpzlK+LvfWxcp5lzJlRNMkpda9YpANYhlvpsWDUSBhoqRLV/XI9f8Va1+VwUGyoDs5IJnz4GWW9RjFEhZq2aF+airdyAK3eKkEoYSHEqKD1/+l5bZduoNhig== 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: Add two helpers: 1. mt_free_one(), used to free a maple node. 2. mt_attr(), used to obtain the attributes of maple tree. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b0229271c24e..3fe5652a8c6c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -165,6 +165,11 @@ static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes) return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes); } +static inline void mt_free_one(struct maple_node *node) +{ + kmem_cache_free(maple_node_cache, node); +} + static inline void mt_free_bulk(size_t size, void __rcu **nodes) { kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes); @@ -205,6 +210,11 @@ static unsigned int mas_mt_height(struct ma_state *mas) return mt_height(mas->tree); } +static inline unsigned int mt_attr(struct maple_tree *mt) +{ + return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; +} + static inline enum maple_type mte_node_type(const struct maple_enode *entry) { return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) & @@ -5520,7 +5530,7 @@ void mas_destroy(struct ma_state *mas) mt_free_bulk(count, (void __rcu **)&node->slot[1]); total -= count; } - kmem_cache_free(maple_node_cache, node); + mt_free_one(ma_mnode_ptr(node)); total--; } From patchwork Mon Sep 25 03:56:10 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397202 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 6EA7DCE7A81 for ; Mon, 25 Sep 2023 03:58:03 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F3E556B0167; Sun, 24 Sep 2023 23:58:02 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id E9E6F6B016D; Sun, 24 Sep 2023 23:58:02 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D196B6B016E; Sun, 24 Sep 2023 23:58:02 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id BA0856B0167 for ; Sun, 24 Sep 2023 23:58:02 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 95DA21CA61E for ; Mon, 25 Sep 2023 03:58:02 +0000 (UTC) X-FDA: 81273761604.07.AC72D7D Received: from mail-ot1-f43.google.com (mail-ot1-f43.google.com [209.85.210.43]) by imf03.hostedemail.com (Postfix) with ESMTP id CB9EE2000D for ; Mon, 25 Sep 2023 03:57:59 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Q2S3K4GP; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.43 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=1695614279; 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=KhsUxrKihKzaZBkbG2I3+KMiT6cOrZp7m1AFdT6cq6c=; b=UDuNouBghYIUuSTyrS9kLk/k5R3u1Gf5rGQlVao5Eknymu67KO9tuTVd7kX2k0k0U2e/QE XFXaSkMbqbClCPEkmBj82cSJ3Ke/p7IgByffLGWqnITF4Vn0yVWcW2eD8zNgOVdQg+Ddd2 g9jSvWniTdNNZZ98j0nUDQEBwpsgjF4= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Q2S3K4GP; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.43 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695614279; a=rsa-sha256; cv=none; b=ZSssm4Ex+6wwVfEXVV8X+HNp6wKDchA8b+RJO0MIau1JPmVYNEgCShJYzPIXJ3zcZQMNur MryQzulNm/BXH9sBAzBPbmlFkHepd7S9n4UT8Py4x7Uy+hinCfh961kre0ZNr48z7CDvZt qY9dzs8Q3wHl9RDt4abP0eC7sOQip40= Received: by mail-ot1-f43.google.com with SMTP id 46e09a7af769-6c0b727c1caso3842662a34.0 for ; Sun, 24 Sep 2023 20:57:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614279; x=1696219079; 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=KhsUxrKihKzaZBkbG2I3+KMiT6cOrZp7m1AFdT6cq6c=; b=Q2S3K4GPlAOqHBIEDKditOnLfwDXFrZAJgCXFhsbRaJWZwTYZCQ116j1aa/JBHa5qz Rzh2517teSYwSeO4+x2TEH5x51U99ncFH4Pgf2KZm6qEJHhGL2NA+7HIp/FTc4tefTen Jz2V0737qJoLI5CVwUoe2NZU/eRqOGEsyrjGltySsXA0YLXwcDGoIIhIIqs+/8FKy9zL I47tD0N1hQa1Ezw7jFGOf92HDHFWv7aapcGQbx6kq/ChscnwLgn4jLi23Enn/4IIR5ta lmfm+JLuwbXvZd5xGLJ/m1cEf3wADJxMmDGK9a0cqkq+ysamF1aCPcL4j6YMb6xSCm7t Yd7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614279; x=1696219079; 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=KhsUxrKihKzaZBkbG2I3+KMiT6cOrZp7m1AFdT6cq6c=; b=OcmnOUVg4T3pZLm9QQ+nE/mknYTJBIdYaaudnuNMAFni5rTb8qfLIvw7mS7brqFhoI GReB8jalS95BNYnS0O+vwYMEO1y7ee4DCkq1/Um0wlZOIeuCrJ4RafEbFCLZmuZM90Yd O/JDgFIGgoGuES5yHONW7UkpyUi5xb+5IL130hDeRyiDkGl92gMeEFtm53scf3f94h6x KlFWRO0YYvxF7VFuDdblSPnb6465A5sOPN/onUD48O2gq4JYF2NwEFR63pLaahm1iSk5 EHWNlcv+1z0fu3UYVXcN7kIVW1ZX2tgWeXzr72yPI+gnaOswKhwNMUZleEq0Govd7avs cnlw== X-Gm-Message-State: AOJu0YzeSa37CCidwnn5Y23+QrgVmL9HkgDnz2VNl9YdDkRAcTRWtf7J HjaqsVDJiv1cYPt0BIqNbcTnbA== X-Google-Smtp-Source: AGHT+IG8xnTwlDvRtAL4fQiYcDiBP4rCNQWClFYM4caq3KQYqXYKOXAxVngsN9hzhjRjKjwKQB0C3A== X-Received: by 2002:a05:6830:2012:b0:6b9:c4b1:7a86 with SMTP id e18-20020a056830201200b006b9c4b17a86mr6335137otp.3.1695614278969; Sun, 24 Sep 2023 20:57:58 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.57.52 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:57:58 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 2/9] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Mon, 25 Sep 2023 11:56:10 +0800 Message-Id: <20230925035617.84767-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: CB9EE2000D X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: h1my4uxep1gbk59j5r5uxnsuqfcfdcpg X-HE-Tag: 1695614279-461408 X-HE-Meta: U2FsdGVkX1+wXJlVU0qsN89XZUgGU/Nbs9n+B1iG4BSKP11ez/oDDz7iTYEO24I2GSbuFr7ThAHeid35yknLczM/htImldyRFnwWYv+ixIbM9aHtuRPIYoTm/AzcGp1Rel6zr02o3U9io4DQxp86IQ/ZUslufE9DyXezKlJhiXimV75Zq7qpZmrwWi0Ts9hPW98TsYdxuqBzttsf9BhhZBVNUkRwRNveXQY2Sso8e6AQDGIjVILTzU+6IZ725AM3cxba9cHVQBsl0HbmU4KIi6HiIjpGBsRYH3RaBSrZSMDJdSt5Tzuxa9h3jQ1gk8PnfLqWjaRZR8BR0EmOidwCha0MzYpg9CT/QK0DZlGVPx3kdpdgLqz3auZiOnOi094TndLvxix4QNzjN5YG4U6nnus4KwOcEpi6kARc4fpAXDx7mJKCAllqxN6r2XgfC2WQwaIpGzLyM7j56EZFaQ+0s3uug+wWph6fynPWt8N9jIosXdMBoc9/Ox78mQrCP25U01waDMO8/nAkAxu1IAzLN/07hPdnIDh3UyQx5oWAe2iXcWTb5bCRa+CUrG3pzca6VkKQSDrmtGaDc0Dmwg1T0zUnguKgjeOekb0GR+N1pq1hljxbatdcuyTEkWsFA4yQVUL4cIjadBsbZkbNrMiKYX6pemZJ0P0KI/TuAz96VUMoZPCj9Anvy8HnXVyQU2fMYLrBNhfA1bLpS/OfwQtRqkIfWA+dKYHk4uLJbWl65sxs/1zdq/aa+fZPiqwtarfecXFkqVXcMCiU/gPTGv2MAabqH1lDUVQMosw+aJ1ruVhk01OtjmZY2SyMrxU7hMd0iNTtPiSRUqEgCGkNxW02yVo8P/6lGXthTrFR88eTaxXTGrLUslSiPhpNDjK/r4BM2kWseWFBhb51dTyD8KCsGyjCjc2Un5t2XXd6o1tuHPfJ8gqg4UIO9utWVS+H2+ybm+K4C54RxMHWIGJ9UKY jVhV1jif +IGdY5ThlZyFVxRGtdZw/B5FEj7I+isFht08IA5JO6MJL2XZtF1Z5viq78RrnyWsfD7tALFyCo7Y2kBAiEdCHx9NJP7bhKXF7cpu5W39ZBSjiHNBAIVqJbH5Vpajp8wZTPTuWW9rxt0pq+LV35GMneue2pQW904YVl7ya6Y17awtC85KAImTly1IvOQuoQ3rO17NfPBkgAs/yabI9MrDl0f1tw1MqI5xaSRiOTxWUCz3IXkSkReZCic7baOC75+l6N3AmUgiFDz7B50s0TSIdl5KX+HztyIb4RfKvH9wHKba+ZMGl1xZojPLKyuJBHMWWrdlbju5uDQKmTjCmCoOgZABc3cDpao9hF/pMA6jJOMLVUCA9+AUtM4MuAy8E+inq21QEiQrCagez4Y2JccqcStVw7zxUiyJ3idKOETtspekRwPyEIFVQQMRZiwHv7p3wKwB+1wc7uDpnNXHHDLxtR6xLHg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000372, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: In some cases, nested locks may be needed, so {mtree,mas}_lock_nested is introduced. For example, when duplicating maple tree, we need to hold the locks of two trees, in which case nested locks are needed. At the same time, add the definition of spin_lock_nested() in tools for testing. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 4 ++++ tools/include/linux/spinlock.h | 1 + 2 files changed, 5 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e41c70ac7744..666a3764ed89 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -256,6 +256,8 @@ struct maple_tree { struct maple_tree name = MTREE_INIT(name, 0) #define mtree_lock(mt) spin_lock((&(mt)->ma_lock)) +#define mtree_lock_nested(mas, subclass) \ + spin_lock_nested((&(mt)->ma_lock), subclass) #define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock)) /* @@ -406,6 +408,8 @@ struct ma_wr_state { }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) +#define mas_lock_nested(mas, subclass) \ + spin_lock_nested(&((mas)->tree->ma_lock), subclass) #define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock)) diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h index 622266b197d0..a6cdf25b6b9d 100644 --- a/tools/include/linux/spinlock.h +++ b/tools/include/linux/spinlock.h @@ -11,6 +11,7 @@ #define spin_lock_init(x) pthread_mutex_init(x, NULL) #define spin_lock(x) pthread_mutex_lock(x) +#define spin_lock_nested(x, subclass) pthread_mutex_lock(x) #define spin_unlock(x) pthread_mutex_unlock(x) #define spin_lock_bh(x) pthread_mutex_lock(x) #define spin_unlock_bh(x) pthread_mutex_unlock(x) From patchwork Mon Sep 25 03:56:11 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397203 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 DF3F2CE7A89 for ; Mon, 25 Sep 2023 03:58:09 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 615F96B016E; Sun, 24 Sep 2023 23:58:09 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 59E616B016F; Sun, 24 Sep 2023 23:58:09 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 419A16B0170; Sun, 24 Sep 2023 23:58:09 -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 286326B016E for ; Sun, 24 Sep 2023 23:58:09 -0400 (EDT) Received: from smtpin11.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id F04DF1CA5E1 for ; Mon, 25 Sep 2023 03:58:08 +0000 (UTC) X-FDA: 81273761856.11.582BD47 Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) by imf19.hostedemail.com (Postfix) with ESMTP id 292111A0006 for ; Mon, 25 Sep 2023 03:58:06 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=F8Yh2fgC; spf=pass (imf19.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.174 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=1695614287; a=rsa-sha256; cv=none; b=VbeVS77VNl1MXKnZcm47gwfW9fc5kabzbgk1Uif8JO46wG8nnjCwggta6+NTotosSF7giC 998IS1zpNYz7vWpHB259aRwab7MvWx/1VR3RQrovFEFBFhkk2wwteP135e9W1hqmrLCMv/ q8xcfmOGN1xkETaQHt3/gT1/VcDJmLE= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=F8Yh2fgC; spf=pass (imf19.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.174 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=1695614287; 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=rqwnnGV2scv+mYD40c0RyHprYCvZzM/H9rjqAIwjogQ=; b=cBT7NH5bZQZn0izN/9QPulaS6Oh0ES9eLnwde85uNhieWVbieSHCr0nWBI2Ojp5dcx3avG rJIghE+G+efy07kLpIg7EcHboLGO+2r083jiiRZX8JkbEjUFFBbGwnrw2y4x07xo9tpFM0 s8hzW1SpXsDbo0ao1tIFGB6Vd47Y5Go= Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-690fa0eea3cso4948321b3a.0 for ; Sun, 24 Sep 2023 20:58:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614286; x=1696219086; 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=rqwnnGV2scv+mYD40c0RyHprYCvZzM/H9rjqAIwjogQ=; b=F8Yh2fgCqZ8bLWOd9OTlYAKqd0ysIWILIx3845VUMXmXnIRTyolHMgB+rRnQz5QF8j lFYW/k+gIwq4DIV34HrdU4cTWTPS6tSZ13ZnDGD9HsaIyz6LpTmDgRDc4VVrcfP/lWyL yn7BgfOPn1C7vAayrgY1nDIrQnEhdfbB9qqVCXKhTfj9faiVeBcZvswL3X5L78irNbfa 2yF9IlgbT/fstQgerT2XiZUVUn3ZI6D4QPgxUkvW5qAnDGTnEyAMvcMOuDG5g9PHQes9 HblW2jHzapyg0GTdLCt7DhVhC/xDRllufk6qI9JD7nSkpHWsKy7+E1NucK+wQK9HBvB3 jz6Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614286; x=1696219086; 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=rqwnnGV2scv+mYD40c0RyHprYCvZzM/H9rjqAIwjogQ=; b=E/zaWt6fgydmkDEMrJp4ArFW1A9gqYdTnMqe5V5nB4jfalr3F9g/m1fYyy8wgaUPTa f43uTGcNACEmcnxlU5aquqeB9Uyj9gScTUznmX4dAVrL8lwba6di/zPPybxNglNoyCQt cSdcmjcpwZrJ20Np4mMYGbLEDBvdLxZaXt7FdFqb58l3OUt73ukdkiXNA898YB2lEGad lx7Qd+xfWCYWR7SdbMdkd3YmHH8/rNVm4sA2Nb9AWPWGK3udVC+RljFCFk8mi8WyI0Wp X14mZIgsIxrAUr9wFN9mRIfp4MhwOMeOHfKy/Rr4jdMrMyGdOklNK81UT7DkRNWMQWGP pe2Q== X-Gm-Message-State: AOJu0YwLZvwziQ+ugEDRwbD82Y8pSxrzKK8Gx+o9odF2qEahdmVkkVDc 4M0N0F3HR0zKyTz8K/X/KEmheA== X-Google-Smtp-Source: AGHT+IE58iLj0C9ujlEHYGqDbCDoboDOWSlTrYmTiPD667rmcXzbIL7UFJlnOP3psq32+9fQw786jw== X-Received: by 2002:a05:6a00:1407:b0:68a:6305:a4cc with SMTP id l7-20020a056a00140700b0068a6305a4ccmr7516464pfu.5.1695614285962; Sun, 24 Sep 2023 20:58:05 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.57.59 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:58:05 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 3/9] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Mon, 25 Sep 2023 11:56:11 +0800 Message-Id: <20230925035617.84767-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 292111A0006 X-Stat-Signature: kwtm4kcyo6kxihhez7hyjrk61mdgdq4a X-Rspam-User: X-HE-Tag: 1695614286-239586 X-HE-Meta: U2FsdGVkX18xgMxE6AyrJklZTZmhj8t79nc2ZS31XWgC9OiOG3iPBhi72iU5yNb0Hnh4WR8uKIZLtBiBXZqmipbH1x0mR1MhtqYlhAqUDIYuZ7AXn02U5gOxrfSUnh5jgHpMaYdoltzqCQztwf+/22jd2KpKfMyR8sqEI3bTADInvZC+/TL3PcceOQpVTik+mHLuYO2FNEXU3CefXBe0bJuCWPGsGRyrnmbPC70YZSTB5hpYhpLt4YldmtzJJCoGfMVByHJ9AuLsuKZGCWt2ak24GYFaSY5ZeJB5fCaEvG3x9as6IyTE/K+geJC7lKUHwelppXOtx+UIYkRPcvvfqdzJuH1hmptdrmgQqul/JYYodz/KoWSsdSnhu/XxaMScJGXObWqdhRPn5SqwbBMOlPXzgAhuu9TKNsucoQpkAsa4sNc2RXc8woNMQ+2bYXTQVsM3J9f0KG410LBaO3OBGLKR07WzIQmM5FkvU7I9jYrXgX+nJO7ciCPH02haDsfx2rHSJISX6gZJb85IVYdS/9o74ixHYvEtEwmuPoOFDRUM+KAom3/if3NfZVUoZo+NWyyP4uEqCxuMyztUqyKG2l04braSPZ6jiWsrOdVkgzZepIkSVvMKSPyiqf65sfjMZIzFz3niGJxuUUAjchxaIfUudodjOunxewxiFSoDs6ordE5H8PjHR8mwEf9qYT58xotNxrAjjeNlxZCuc0GhOrV0JquZm1RRhU2PwqSMM9CmtNCfUjT7J+I4U0HwauiNB4k8ZrgE4BV0MVTNb+3vfzAZD0mlgzTL1DjMfRn0U43EXsr1IQYaXoVAfDNCCdPt3wgXYExAPwqg3gKMS96SRywhwMdIPCVapuPHQIGI1XGnK+W7lERv6RYtAV5uByyGRV2L35EkEkF/nBiFJrb67GV/37aiJ1xvQI3DcZO8A0sBw/XontFL0FhcmzffpdELv6Z2qj83/zPmEdBQGRP XGENTCu1 flBT1VWCNIzhjeIntrk97fULuTlc/epZejNmmL/s42gSG3yX3sVySDTMf0n3e3SNjYSlLO9258uiH+UdIl4o++gfl8oCwlviiFR1363Z3NqkLpPoVxSupBiKlIuzFh1Hvg/FaptmfZw9ilC7hrgLeh2XP7zvht57KIlkyZtJoXqq0sDPL0GOo/UqnDuW3lfIgYTVWUqV7xZdBSLli30oPaJOK9H6+XeSmswh9dQOh1u0T/JLzBXA4gwEz2yK2xN0MMBkK9eOF/XBzCxOTRQY/08BI14Dj7v4+3XWcLRrySgMQWwrApv+N762h8p6/E+gogC9uNCHTdwk2pqWWTDO9N53nEmReuzNnTJXGjwpTR5PVTcoQWJJ7T3ELIuoZRG0sEFCWhhPaoxgsPiLKfaPOkgVsjbguFfrct/W+6Ek/tRdE0FalRyRiDBUmfnRD6pIidfLBYDoba7ttkvTAAf5QudmS/Q== 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. 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); + 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))) { + 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. + * + * 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 From patchwork Mon Sep 25 03:56:12 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397204 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 92E8ECE7A89 for ; Mon, 25 Sep 2023 03:58:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 26C8F6B0170; Sun, 24 Sep 2023 23:58:16 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1F6246B0172; Sun, 24 Sep 2023 23:58:16 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 06EEA6B0173; Sun, 24 Sep 2023 23:58:15 -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 E65BF6B0170 for ; Sun, 24 Sep 2023 23:58:15 -0400 (EDT) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id B52261A09B7 for ; Mon, 25 Sep 2023 03:58:15 +0000 (UTC) X-FDA: 81273762150.23.701293E Received: from mail-oi1-f169.google.com (mail-oi1-f169.google.com [209.85.167.169]) by imf26.hostedemail.com (Postfix) with ESMTP id DE0A7140003 for ; Mon, 25 Sep 2023 03:58:13 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Lvog2iQC; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.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=1695614293; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=d0zJSRMrlzJX5Yrn+/PECWBgqjUHYTgmpj1Bb/mnR0KUtPDpUYBREvg8Tpau4yUwS8rqso rdBG9PgsduwRCO/ZYy0+cpPcINN8443EFCaHTsSm/awALp7ZVaRSGATWn+Aa1bQbL+EDSr un90dvbFqIfyH6RiaghHNCkRfpoDL/8= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Lvog2iQC; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf26.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.169 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695614293; a=rsa-sha256; cv=none; b=zwozst0z3tEqm2P9kP57otBPKkra4I7RUPDjnLp6XGspQLPoXjgqnqWfA43yNP8xHb1lwC Hyel56ChOS8xSXBQGiT4GvggY6nLHyHWR+argr9D3JbvXdTFPLHAu1AT9H1drI9dxL7QiP v/aCWokSaqdRkBIvmKbJpxSNemfyiRk= Received: by mail-oi1-f169.google.com with SMTP id 5614622812f47-3a76d882080so4059714b6e.2 for ; Sun, 24 Sep 2023 20:58:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614293; x=1696219093; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=Lvog2iQCnS07NPsEaPQVtBIVZRdX9MF1VFitZ/9HytdWzZwlr/j+qdm1fJNnCDUYTn o84MSNzyxK2sg/UY3VHVSK3YEokngdr5CD5axV88Wjuo4ftTouzR5F2jaf9vT11BPCHd G2vwgxYRBerVJhObOqEvs5yAgmjBMk6XUm89pippTk9Svb18y08s2i2jgWgbdS/AhjCN 0RDa2WUx0/A644eKYCpaaXJ4ORB+nQA9UJxxBTBmL30h17aXOcOzQGb7vkj7nOSy5e0w SzsKqrGOR9QaQuKFMmLCEFUXpvyZbf/izKpfrJV4qGfU6+Ok/ZxPamlk+OCsehfT/oZ6 SHUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614293; x=1696219093; 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=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=ZDURrqikYkMqWasavC8YIAjDsq6+A6Lh/PP3OLSoTr4zMNw/+9KmuW4kY4dcLcD3L1 3TMd4EH84qofItnbkBXVU95yQ8UbNKHdl7HDOnKP0Mgmkb+GcJ5gvpXQED1VAonyFaLg jE1uN2yysS4nX0TyXJmhoYl+wZFG6uluxfR7AhzQYTi2qnaW50VHiaPboJimciFT+vD9 FMmdmyQgKCpcnnzntmBQyLbqQtdSibGD35H9BEKgx4EHK5KpGcZXXzXk0z0VcMuYO5AB MfrzLAXRPg5cvdJO8PcdEWICF0NIcwOhMKIaq4z6EWxMQZaVWErI5h3JYwcL5kDCtX0Y f3sg== X-Gm-Message-State: AOJu0YydiVxD/PwYQFHl1Kf2MybI+a7AQXPkTojll1XYgfbrnGLyV55g 9pXj+CVc6Rrm1daGS6CIAkZ4ew== X-Google-Smtp-Source: AGHT+IHd1Pu1jcgTttSe7sFRwiGzS3UAk4+xEgzmMAEerGfTYzKcYv0T2Mw2kSYstvH9RBeTT2rVsQ== X-Received: by 2002:a05:6808:308d:b0:3a5:cc7d:3d66 with SMTP id bl13-20020a056808308d00b003a5cc7d3d66mr8190041oib.49.1695614293016; Sun, 24 Sep 2023 20:58:13 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.58.06 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:58: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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 4/9] maple_tree: Add test for mtree_dup() Date: Mon, 25 Sep 2023 11:56:12 +0800 Message-Id: <20230925035617.84767-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: DE0A7140003 X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: i5zi1eayh4ihq3yzot8pi1oid75mfqfs X-HE-Tag: 1695614293-944320 X-HE-Meta: U2FsdGVkX18L4XEgRO535G6RFxepM2iH27FmVDfujiV9O09ZkEGWhEh2MUW4E8hDNLLYhuJCu9yVzO0jueL7sqofWosmlXe6K7bdTOH3wfVgWYgm2kHWgOEFycwBCAhBBKBPvB2S38q7jBXY0kkx9oU3IFdJ+hc+LsCh4JTlbcaqqNdlA3mG7R+K5H+zljNE7YCb9Bj618zVaZpQkc4DiBLmPAm0kaXHyqsGlqDp6e3lb35qjFaEEzwAdle3+SkNiv1jHcLDSwdfqIozzSaRpEpjDCoRCHh+qLJ3QESKX+2yZvjB6kS1sxveRfjgzTilNvQUqo8OenZk+WZX5uYFEinxZ/Sp8QAVrFWCt1z2NjMVJsQ8WYYKwiZZPGu7ZlsXtqFpoX0fDly/EgD8heKwSvwev4Wwf1Uk/C4sWAgpqI9VhCemfJg6mH6y7nhaEdPVgbiRoWm2vHBCiR1r9+1FRlb36vlFqaYhZ7g9qOpOzTx+xkbYn8NjPNEVI+qQ6MNTjMUPgHUx8oELJDISTLwnxlZSGi9K4v86q1dsMJ4BiquF5CNuWTuaWcnWgf4aGefGAdtvJLtK0l9ignxQsJidK3TgWqFQt9Qf/K/p+3w+A9HZDIpiSES+0K1U2klbzM6JAwtfZsIO6dffht3CnEvyG3G4XrMyO9bHXX8c1M0TQjKKb9yH3vjPJf3YssZqyHTTwvN7gFuE1gsZgU6cqaXr11KLDTA54nbUabI2FyVLz5Z0UKTlwzX7NnLs0tbjSkflDUbL616pdEG8/HzbEihA5H6niQUvzM+pQWlZRgbkTsKocewhqiojc6cudEX9iVoFeBSqgIwzZWYivDCC59Xqha6fyI2RQmqEeQ5/E/KLJiRJn+wpnrQRikGP36rPM6ZdWM4JJ2NjzZkqbMrAaDmVpTMedHiq1+SzGRnV0ZTjs6htnJU3PaZ6a90tZY7Eq7aYZ/+alhpos/QEiCHkClx CbeGeOv+ gv3LRzAwFDp05qzuC2a89pCXL6EBHXdV8w+qMQJv83OFj+3OWGpR7MLKFfKTceqxW1jKDwzZFytWrL/Q3xIgwsLBsDOAs+oB4IYIz36I7UgIRXtVlcmmTGrQTuRZ9kK/RSNCsGc9h7ESe5O1WZtxZfx7lKCE0jAd/+neW0uiwJ6N3iIZarRztXJ6T3oyLGOBwRY/alqE6PL5nFLYC5HkxeKgRaXesEU/C+MHkUcn04vVfy/L8oxZvgW9byPfHckETpJSSqXfrAPj1Gv3Tu3x/D0zEkt5I9RupvBsA+qNYRyZyaBjIjGWNkO8RRgbSD0EqAdG1lESbI6ZCugwT+qxxSk80JCoeHx9hL2uFlmuqMbcOGhOehffLJ6Iw3PXPGHocjvvf/MJTJXhwzu/zCPStrLtnNCeLTMOMNZDjhPD5NSrmGLAV5SnN2S+flQVWW9Tv+T/mMwF9SoJ22SoWLYEhmrl3HQ== 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: Add test for mtree_dup(). Test by duplicating different maple trees and then comparing the two trees. Includes tests for duplicating full trees and memory allocation failures on different nodes. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 361 +++++++++++++++++++++++++++++++ 1 file changed, 361 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index e5da1cad70ba..12b3390e9591 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,363 @@ static noinline void __init check_locky(struct maple_tree *mt) mt_clear_in_rcu(mt); } +/* + * Compares two nodes except for the addresses stored in the nodes. + * Returns zero if they are the same, otherwise returns non-zero. + */ +static int __init compare_node(struct maple_enode *enode_a, + struct maple_enode *enode_b) +{ + struct maple_node *node_a, *node_b; + struct maple_node a, b; + void **slots_a, **slots_b; /* Do not use the rcu tag. */ + enum maple_type type; + int i; + + if (((unsigned long)enode_a & MAPLE_NODE_MASK) != + ((unsigned long)enode_b & MAPLE_NODE_MASK)) { + pr_err("The lower 8 bits of enode are different.\n"); + return -1; + } + + type = mte_node_type(enode_a); + node_a = mte_to_node(enode_a); + node_b = mte_to_node(enode_b); + a = *node_a; + b = *node_b; + + /* Do not compare addresses. */ + if (ma_is_root(node_a) || ma_is_root(node_b)) { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MA_ROOT_PARENT); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MA_ROOT_PARENT); + } else { + a.parent = (struct maple_pnode *)((unsigned long)a.parent & + MAPLE_NODE_MASK); + b.parent = (struct maple_pnode *)((unsigned long)b.parent & + MAPLE_NODE_MASK); + } + + if (a.parent != b.parent) { + pr_err("The lower 8 bits of parents are different. %p %p\n", + a.parent, b.parent); + return -1; + } + + /* + * If it is a leaf node, the slots do not contain the node address, and + * no special processing of slots is required. + */ + if (ma_is_leaf(type)) + goto cmp; + + slots_a = ma_slots(&a, type); + slots_b = ma_slots(&b, type); + + for (i = 0; i < mt_slots[type]; i++) { + if (!slots_a[i] && !slots_b[i]) + break; + + if (!slots_a[i] || !slots_b[i]) { + pr_err("The number of slots is different.\n"); + return -1; + } + + /* Do not compare addresses in slots. */ + ((unsigned long *)slots_a)[i] &= MAPLE_NODE_MASK; + ((unsigned long *)slots_b)[i] &= MAPLE_NODE_MASK; + } + +cmp: + /* + * Compare all contents of two nodes, including parent (except address), + * slots (except address), pivots, gaps and metadata. + */ + return memcmp(&a, &b, sizeof(struct maple_node)); +} + +/* + * Compare two trees and return 0 if they are the same, non-zero otherwise. + */ +static int __init compare_tree(struct maple_tree *mt_a, struct maple_tree *mt_b) +{ + MA_STATE(mas_a, mt_a, 0, 0); + MA_STATE(mas_b, mt_b, 0, 0); + + if (mt_a->ma_flags != mt_b->ma_flags) { + pr_err("The flags of the two trees are different.\n"); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + + if (mas_is_ptr(&mas_a) || mas_is_ptr(&mas_b)) { + if (!(mas_is_ptr(&mas_a) && mas_is_ptr(&mas_b))) { + pr_err("One is MAS_ROOT and the other is not.\n"); + return -1; + } + return 0; + } + + while (!mas_is_none(&mas_a) || !mas_is_none(&mas_b)) { + + if (mas_is_none(&mas_a) || mas_is_none(&mas_b)) { + pr_err("One is MAS_NONE and the other is not.\n"); + return -1; + } + + if (mas_a.min != mas_b.min || + mas_a.max != mas_b.max) { + pr_err("mas->min, mas->max do not match.\n"); + return -1; + } + + if (compare_node(mas_a.node, mas_b.node)) { + pr_err("The contents of nodes %p and %p are different.\n", + mas_a.node, mas_b.node); + mt_dump(mt_a, mt_dump_dec); + mt_dump(mt_b, mt_dump_dec); + return -1; + } + + mas_dfs_preorder(&mas_a); + mas_dfs_preorder(&mas_b); + } + + return 0; +} + +static __init void mas_subtree_max_range(struct ma_state *mas) +{ + unsigned long limit = mas->max; + MA_STATE(newmas, mas->tree, 0, 0); + void *entry; + + mas_for_each(mas, entry, limit) { + if (mas->last - mas->index >= + newmas.last - newmas.index) { + newmas = *mas; + } + } + + *mas = newmas; +} + +/* + * build_full_tree() - Build a full tree. + * @mt: The tree to build. + * @flags: Use @flags to build the tree. + * @height: The height of the tree to build. + * + * Build a tree with full leaf nodes and internal nodes. Note that the height + * should not exceed 3, otherwise it will take a long time to build. + * Return: zero if the build is successful, non-zero if it fails. + */ +static __init int build_full_tree(struct maple_tree *mt, unsigned int flags, + int height) +{ + MA_STATE(mas, mt, 0, 0); + unsigned long step; + int ret = 0, cnt = 1; + enum maple_type type; + + mt_init_flags(mt, flags); + mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL); + + mtree_lock(mt); + + while (1) { + mas_set(&mas, 0); + if (mt_height(mt) < height) { + mas.max = ULONG_MAX; + goto store; + } + + while (1) { + mas_dfs_preorder(&mas); + if (mas_is_none(&mas)) + goto unlock; + + type = mte_node_type(mas.node); + if (mas_data_end(&mas) + 1 < mt_slots[type]) { + mas_set(&mas, mas.min); + goto store; + } + } +store: + mas_subtree_max_range(&mas); + step = mas.last - mas.index; + if (step < 1) { + ret = -1; + goto unlock; + } + + step /= 2; + mas.last = mas.index + step; + mas_store_gfp(&mas, xa_mk_value(5), + GFP_KERNEL); + ++cnt; + } +unlock: + mtree_unlock(mt); + + MT_BUG_ON(mt, mt_height(mt) != height); + /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */ + return ret; +} + +static noinline void __init check_mtree_dup(struct maple_tree *mt) +{ + DEFINE_MTREE(new); + int i, j, ret, count = 0; + unsigned int rand_seed = 17, rand; + + /* store a value at [0, 0] */ + mt_init_flags(mt, 0); + mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + + /* The two trees have different attributes. */ + mt_init_flags(mt, 0); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* The new tree is not empty */ + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Test for duplicating full trees. */ + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, 0, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, 0); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + for (i = 1; i <= 3; i++) { + ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i); + MT_BUG_ON(mt, ret); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test for normal duplicating. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret = mtree_dup(mt, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* Test memory allocation failed. */ + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (i = 0; i < 30; i += 3) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + /* Failed at the first node. */ + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + mt_set_non_kernel(0); + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + MT_BUG_ON(&new, ret != -ENOMEM); + mtree_destroy(mt); + mtree_destroy(&new); + + /* Random maple tree fails at a random node. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(mt, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(mt, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + /* + * The rand() library function is not used, so we can generate + * the same random numbers on any platform. + */ + rand_seed = rand_seed * 1103515245 + 12345; + rand = rand_seed / 65536 % 128; + mt_set_non_kernel(rand); + + ret = mtree_dup(mt, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret != 0) { + MT_BUG_ON(&new, ret != -ENOMEM); + count++; + mtree_destroy(mt); + continue; + } + + mt_validate(&new); + if (compare_tree(mt, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(mt); + mtree_destroy(&new); + } + + /* pr_info("mtree_dup() fail %d times\n", count); */ + BUG_ON(!count); +} + extern void test_kmem_cache_bulk(void); void farmer_tests(void) @@ -35904,6 +36261,10 @@ void farmer_tests(void) check_null_expand(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, 0); + check_mtree_dup(&tree); + mtree_destroy(&tree); + /* RCU testing */ mt_init_flags(&tree, 0); check_erase_testset(&tree); From patchwork Mon Sep 25 03:56:13 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397205 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 DFD2ECE7A81 for ; Mon, 25 Sep 2023 03:58:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 74F7B6B0173; Sun, 24 Sep 2023 23:58:23 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6D68E6B0174; Sun, 24 Sep 2023 23:58:23 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 550186B0177; Sun, 24 Sep 2023 23:58:23 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 3C34C6B0173 for ; Sun, 24 Sep 2023 23:58:23 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 0DEE21606DE for ; Mon, 25 Sep 2023 03:58:23 +0000 (UTC) X-FDA: 81273762486.28.19D9BEC Received: from mail-qk1-f180.google.com (mail-qk1-f180.google.com [209.85.222.180]) by imf15.hostedemail.com (Postfix) with ESMTP id 3F48CA002F for ; Mon, 25 Sep 2023 03:58:21 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="UShm4i0/"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.222.180 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=1695614301; 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=hww7oOWxGKb7qmsb0mmM2P/enCFKvkDkB3bMeqs1n3g=; b=FZJRZfamEaQ+kpQRWfDrdyD/xn3yCZ696WJFoIX8FRtm0ASFzv+B5bc3zwDED2u0CbV3wo BryebvuQ6eRfGCZ1YOH7vW3UPQwg9deKHoD00I2cgVioBZ1A7T1YMbSyRyUFZTvY4UMD/w uiF6rohXEVdRgXB+zXxpfxdO0T4bXiE= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="UShm4i0/"; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.222.180 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695614301; a=rsa-sha256; cv=none; b=CCfkvWi6j5Kh6xQw95gq3kbC8LX04EYWST0M7d5o1A/YhGDfSeqMLdV9jbgdxYy4601Ykg aogKiAAx9VRUQonN3lmppf7qhqKYcTXxB5ldmcx62OJEiRqOrcREvXDCknUkn8yiYR/9N5 r+QOVSkOYCThdheVoU67Y4BajV+V36o= Received: by mail-qk1-f180.google.com with SMTP id af79cd13be357-77410032cedso346434485a.1 for ; Sun, 24 Sep 2023 20:58:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614300; x=1696219100; 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=hww7oOWxGKb7qmsb0mmM2P/enCFKvkDkB3bMeqs1n3g=; b=UShm4i0/hLL/ag+MPLuqPHzFXUE9HIiioMDWZzqAbPoUSCQSa2tDb+hW4Dimc2ulF9 xFRCKx5EOuPlqVsOGD5c0sitgI4RnGnZyqpSIJIF0UmFNOOIIU5fji2bBfJCfzGaMW34 5P8LKfcFNzjovWyPfFeZhOaR6KeZ7waBva7/nr7WQANPIm4UVRaP8Q1aHbYQhrOtuJTw mUIDLcTnhehA9MDRIcBv2ClY7XfogGbZY/4DKUILCwS+n6nYzWd0HmSXeJw5DsO1JrF9 2jIZZegR2L61rPsertvHbvwowQ4N+BSoFdRGdMEkKBqoTT6n0W4lCnRVPMEO5WB6lcL5 T3WQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614300; x=1696219100; 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=hww7oOWxGKb7qmsb0mmM2P/enCFKvkDkB3bMeqs1n3g=; b=rLHszcC0bk416hf3FLPaa81K5zom816X6HS4KQOCVBqFilNWw+V5J+cq1zZXMWmpGY 8dvf8Eq4zZNi+hfZ5O8OQ9V5OO+nkjpK7wRlQKqe4aSPPsl17LTCghnwQ36EOopnvTLK Q9i6R9h3PZJiK7e4IzwlF8/eZo13reXrMxjFFqKI8LnujsAG7GtoP8sc3mH0f/1/ST0u drPk4duqOxQFG3O+J2eZYj2MyqAsQU+UqJLYW4lWFmbxod0QJ3L/S/1i/aVQjywHuG1+ n6T7l65Yx/cYxBs95P2ylB23SYMtMPlMFxDz4aZR+1Jt/J7j+j3J643NQOu1sVWLD2Yq WTsQ== X-Gm-Message-State: AOJu0YwBPYzPVQtq9BEJvenSwN4gjxCopCaCj/w6csympqCmKXZ5EKa5 rMuNJcpi83JN2xovbXgog+V+Tg== X-Google-Smtp-Source: AGHT+IF83HXgYz6hKs16v3Oy5RBkvjlke2ZYjx8DNaVcWabWxUJCzfLznLiorxxWRtU2DFZTy6RRoQ== X-Received: by 2002:a05:620a:1987:b0:774:2c35:3796 with SMTP id bm7-20020a05620a198700b007742c353796mr3484182qkb.34.1695614300078; Sun, 24 Sep 2023 20:58:20 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.58.13 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:58:19 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 5/9] maple_tree: Update the documentation of maple tree Date: Mon, 25 Sep 2023 11:56:13 +0800 Message-Id: <20230925035617.84767-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 3F48CA002F X-Stat-Signature: qwp55ckcjcrcgbstwzun9o9wwsobihue X-HE-Tag: 1695614301-376134 X-HE-Meta: U2FsdGVkX1+Ix+eW4sHzIqXqJbDLCKW0ps/bYNuzeZe/jd5NuAym6eQgpXEPaWXmnrFnR/S/LnKOKw4R4URDR4MY8Ejv4t5UMd+coPS2xeX59iQ70AJt1CCFagW6vfgyieq1FAfHqAZ7y0X0KB5jFH0ZyClhY94QX4mDFhhGFa7g92mUqbYuX7b4PKGo5vW2T6f7YIOUfq2MUHDHiWKrN930mSW5pyGCzPgidKJTYZjQo1PqGp2mmXvpbSDbGL/mwnDjXdmyF0x5cbTV+I+hdOgs2itxri+W1XLIMFv6gSOA8kGpe/FHNG9JtmWrCC2bxDbw50eruHFNUrmS3X9P0IdZR6OF1yPdnNyqQq1OGmyRqokJ/fU/qxR4KExwcm1WVqSCyZEyPtkLVClG+zwbp9UKQLAzpH0UywlwV9PdAs2N74CIyHHXVvomYUHLtJVcXHAeH8yn9mricAF95Ri+2mabxRHHUjVLC0NJJAJs/OGgwJf/dKBMd3vI5mtRo2zTGx6h4IgPqVwey9gGGfu2YAHWEgiudt7fJNNGPdV0KNZaG/PJ2eDfTD/ZLbTg/9FxcU8xpOTwEVtUd+RdQPAfQZeF7oXkE9eLaVeMd3dsbqlbofxVUiWE8qstcvQEzAiS3E5xuDhdG/K6FH8pl61JzZDVQbB+jL5ng4K+x+sMUJOQ9z7ztw3AWMN70bTNLIgBCb/59a9+KqfORQlcqBbnsJUoq8zH3XSDBJXH+gYm70pLdAPMB3KI9r+i9MvFTQh0bVY/Wf1VT6rM+IZ3FpE3efh3rAtgIvCYdOZf1slHghEMLuMgbyPEkbK1aDKV35sMBAd+cIxN6DYh/w9TJg4MyZB4U7E719jIgVG0aQa/T/h34NsWO9QnNyqqi+J5TVPZwKueGCysdDIAxoAA/XX5hTRC7sGQKV7ypGC6GR/73ewPQHirYovoItXA6E7KNMP0TITI1PRoWv6dXKbsqNd 2XBYJls5 hJSvLwdiAGYTeea+KtKqEw2xT4D5o8ZH0sJ5TVGxS/OHNVZTPOovapjN/pjEYHRjF47KJcVPjx5x79RbT4bs1ngJd2CDzUZ3Zyjh3XHsSe/geWDK3DZogv6pAOKUCFO7skLUlKJrULdM4HsS52zI4hux84OqcvCwtYSEbehs7fst8LeFAXSPS5ovu8Y2goKsVRsZulvrvO8mEYRZV6ncIN0Y0ZtR2GBZXtQ2a2euoJX2xCjpVFI4PN89mA/2F7pTSCOuY0dZNVunAiP4gDrPBmCIuI0DSUi7hbvlYxsC5TYrt5z5Z5vhE7G3XQOcARlurNEiR4wbBFtDQvl9Jhybol30L/0R9VrX8Eb0UURzOV4ItBy2It+onx1YKa+O58fWOmQBK6GGmrvPx7xU/XNb/l9VQvQMZ27eEUOj57E5EjjE8wRfKaWzfNrAG3DU7cLCwGEaFDL9FJYmApCBFd1z7dMMd4Q== 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 the new interface mtree_dup() in the documentation. Signed-off-by: Peng Zhang --- Documentation/core-api/maple_tree.rst | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst index 45defcf15da7..3d8a1edf6d04 100644 --- a/Documentation/core-api/maple_tree.rst +++ b/Documentation/core-api/maple_tree.rst @@ -81,6 +81,9 @@ section. Sometimes it is necessary to ensure the next call to store to a maple tree does not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case. +You can use mtree_dup() to duplicate an identical tree. It is a more efficient +way than inserting all elements one by one into a new tree. + Finally, you can remove all entries from a maple tree by calling mtree_destroy(). If the maple tree entries are pointers, you may wish to free the entries first. @@ -112,6 +115,7 @@ Takes ma_lock internally: * mtree_insert() * mtree_insert_range() * mtree_erase() + * mtree_dup() * mtree_destroy() * mt_set_in_rcu() * mt_clear_in_rcu() From patchwork Mon Sep 25 03:56:14 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397206 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 63A16CE7A89 for ; Mon, 25 Sep 2023 03:58:30 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F157C8D0002; Sun, 24 Sep 2023 23:58:29 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id EA03B8D0001; Sun, 24 Sep 2023 23:58:29 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D40008D0002; Sun, 24 Sep 2023 23:58:29 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id C04988D0001 for ; Sun, 24 Sep 2023 23:58:29 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 9F3991CA64C for ; Mon, 25 Sep 2023 03:58:29 +0000 (UTC) X-FDA: 81273762738.13.9171F67 Received: from mail-qv1-f46.google.com (mail-qv1-f46.google.com [209.85.219.46]) by imf14.hostedemail.com (Postfix) with ESMTP id E629A10000C for ; Mon, 25 Sep 2023 03:58:27 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bkKh2gnU; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.219.46 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=1695614307; 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=D4LS/TFttl0uhdXEX5m8lwn2u6CezP5DBiTdl/qFdZ8=; b=IX2E/Fz1bMvf09w1PsprP3EPC8p9WPmn1/Xgy8KfHLa5VOoiZrWNQk1aCSe85FuPnOVlba tjkGzuKYK9Sifxk3XvG3FQjYKzNDpquCMvBCuuqlW8RCFw4/aozDmGUbutELCzfNiMGmA+ xP7cMTcAUytaFjtpPAbfXRg9awTAXxc= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bkKh2gnU; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.219.46 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695614307; a=rsa-sha256; cv=none; b=uvNRb/Jd+fUuWwDlSupxTEqlBT1jv1rAekT4HbsGIYnqUpMDrZwCTVzE8QFRz1imEhz32z h23BqwtrkK68JG9bVUQvHDrPN6xgRf1sAZtx898XUk5hd6lR0AXX2rhtBZiDtMVhxHFdtt xV0O2tNjVldnB9hlbDfyQdPvMeGDa4A= Received: by mail-qv1-f46.google.com with SMTP id 6a1803df08f44-65af18cac71so23324296d6.1 for ; Sun, 24 Sep 2023 20:58:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614307; x=1696219107; 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=D4LS/TFttl0uhdXEX5m8lwn2u6CezP5DBiTdl/qFdZ8=; b=bkKh2gnUjGT+FMSpWrEJj9vLSfNiV26PCikiXhh7V4kBwjMXCmit+NaCGW//H3G4l4 sN1+vOGY0pzZf5bKDaXIeacqp/1uH/o0WMpriNuRbpKBLZEcpzN0OPaMcNW/HSOil+py aXEbfkPNbxL1en/FgoGLUj7k1F6b9vB/3RBXY5l2dMLhyLZZuXSJ+zUfG2EHhtD9Zw1e DLXnKK5BpJesQYqmQRsYqCXrmFQ8TK/4mbX1D+UBI6hc3+NWxg6xIovpQgNPwK83HHSS mB0cqve4QrrxJYK//DqMSlpgXrRmR2u1eEDoZUCahp5KYo3j7tzJrbUHepgB3Juqnzf/ hqvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614307; x=1696219107; 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=D4LS/TFttl0uhdXEX5m8lwn2u6CezP5DBiTdl/qFdZ8=; b=urIIFE+ath7gyKxqSAgQe1n/+h1RQcHIO0vYu5alMVpsNRXKi0nqC+0YieNsUDhdPD uc/LwAFRJa4IhW7yPIg6UaspeGa0EnQ5FwP8giM6e9gDD5+ap4nfGcXi61hMk75WIKJ/ YoW0D3Amt/2K/UzRLTzZWWvdZRA3eBMhhkz1KaiavOyBWeMdbM8/h82js4dCwHu4tQfh py3RZEoZHQuE2t2qdKeQjR6O9Dei64fl+AEQMy6RMyj57jCo9+Va9Dmuw0e/Ryrdcmd6 dG0SrfgjeiGGP30kttL6FWrtyBZ1LvZj82EE/5iNsaD6ZBHH1YbBEY6CjoawIZUtnNz5 /F5w== X-Gm-Message-State: AOJu0YzZZ3PvWIzg71i466/v7deDnONSCKaWBDCms/F+A2NgAatgtCyB /c4nnx8S4aj5/pIeTbHNQBn1xQ== X-Google-Smtp-Source: AGHT+IFyPjYxuSfNgvsS9Z7GkNZ6srfa0PNzA2kN76VBzGnCz9+3nPN5C/SDQMLJt6pMfLPc2iPj9w== X-Received: by 2002:a0c:ab82:0:b0:64f:8994:792d with SMTP id j2-20020a0cab82000000b0064f8994792dmr4730466qvb.38.1695614307072; Sun, 24 Sep 2023 20:58:27 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.58.20 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:58:26 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 6/9] maple_tree: Skip other tests when BENCH is enabled Date: Mon, 25 Sep 2023 11:56:14 +0800 Message-Id: <20230925035617.84767-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: E629A10000C X-Stat-Signature: xabpz1ou5zqi6h7oxxtzkm9q3pm56ggk X-Rspam-User: X-HE-Tag: 1695614307-133081 X-HE-Meta: U2FsdGVkX18QxLfniG3DWRNQZk7D/QOBkyKE+RYoIiioGb7vLR97qs+r58r/lBFR422wQMBFO/WLGffbDCO76Rdysh39jhWz2NdxUWQ74ZuXLKCl9XmoRptSAIWkuMTd67CiI8z7D9Ml6imT6JiimAaMlue8TqlSO7FCjkRhsHuvn6Jxtydc6mQN3No7OFuikxIE7l8jB2/wgGgfBHIPk2QmQdWdm9OwUBgk/LiV7Kl9YcAiyxqDFvL5OILjmk7ce4bfMLcuoPpmy//CkzAdmenhDrZSF27BJtf5K402n0UEfSD4wbHjOq1wPHXC3ijD5q20Fo8fdQWqpnI32Y5yNYvsfizY9sjne3W7QPwp5kKvZR+hjcqnm1XvtrM6qsktjtdO5ckWqRh86aSu9d8hYzOW+yL8ZCwM5p80KzXEdKnjb0/uLETT0ha5ZI/UxrpWs3jW/HW9yu6oyis59JhT7t5t3rCpFVyfoRfK/hLCTkWMzQ9/vVyAl6ExOe59RENYrA7Kde4bQY4tW9pnAoLNH4+Z3fjOxWk7HCBPtW1AHdm5OgdKHNGj/zLkbmtWq0ShIrcY425ho2HoAFRRXSLQ3V6JYDpEkB1XCmNTtVsvXBuaYkNxMrREm+AoLvjzUmm7gdMEKDEkOQbJq2Jgolanphan3eZJdvOQzLxmAFzzO05L8lcnLkswops4aIU1Drv1sVCyZCyMsAhktoOJ+ukKr0bNP0g/9Mf3aqEllL+0XAy98XUpcnlNkYobp3RVODOtA8tjYS4pGbgIpPYLjuyg/xn62vrZmx3GVh04jEK2FrtO6Bn3Q7sojF+WqGQJkjvcBGGH4nIDkdDrmw7gzVI+7SaJA1PjOjeU/6dFWrOA9qqK1Yh2Rcx+SzNyTNz2xTKYFbHANoDweEuvbFpqHlO/1UmuKqnBGBImm6fJAKmpUHh8QKTBJTMfiT7EK8rQ0ziWfApPFJ8427gkLY+wlnj ORr3q6kf 6g56JGEw1ORts36cXwyg2LrSOBaihgOh7ww+4qrune7CUueOKGFIof/Lov/yUPZ3pVQ/ukc2mRL1aEynpI9z0fQw0eVu/fmBpMJdAw+a/8V4pd5a2J2HSiSV45nTyGPEOnVhIGQ/ZeEykLkpS6I7iQQKKAhv3ttHs3Ld3liOlqSYtHABTs3pc60fBHWYoyu3tbMq+S6L1WqBbC3EboPXU0c05CXVnb/e4LRWpwQIaAroAUV9nAKGYaBm+Jq44BCf3tEdSEdCc7UXfARnnXP6uBp5y1QlGQ8OuchcripQF0aXGkBwjYA/JcINViW3Evm0pGY8ZfAeJOEFnMgbiGfRWCEQRe3R6j7S0OUcQoeBHeWNKBAbes6zIRiI6ce2K3pOQlIy5/esp/WZ3ioSoI2fQM5/d/cdamY7IJGpbKsJo6nqZukDkwrt2Yj4uOhWzQeuDgIPzDAqccHjEtKtKy0LeLE0/2w== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000001, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Skip other tests when BENCH is enabled so that performance can be measured in user space. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 8 ++++---- tools/testing/radix-tree/maple.c | 2 ++ 2 files changed, 6 insertions(+), 4 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0674aebd4423..0ec0c6a7c0b5 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3514,10 +3514,6 @@ static int __init maple_tree_seed(void) pr_info("\nTEST STARTING\n\n"); - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_root_expand(&tree); - mtree_destroy(&tree); - #if defined(BENCH_SLOT_STORE) #define BENCH mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); @@ -3575,6 +3571,10 @@ static int __init maple_tree_seed(void) goto skip; #endif + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_root_expand(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_iteration(&tree); mtree_destroy(&tree); diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 12b3390e9591..cb5358674521 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36299,7 +36299,9 @@ void farmer_tests(void) void maple_tree_tests(void) { +#if !defined(BENCH) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } From patchwork Mon Sep 25 03:56:15 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397207 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 A6297CE7A89 for ; Mon, 25 Sep 2023 03:58:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 48FB58D0003; Sun, 24 Sep 2023 23:58:37 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 4185E8D0001; Sun, 24 Sep 2023 23:58:37 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 292308D0003; Sun, 24 Sep 2023 23:58:37 -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 0FB4D8D0001 for ; Sun, 24 Sep 2023 23:58:37 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id C3BF814097D for ; Mon, 25 Sep 2023 03:58:36 +0000 (UTC) X-FDA: 81273763032.18.CFCBD2D Received: from mail-oi1-f179.google.com (mail-oi1-f179.google.com [209.85.167.179]) by imf03.hostedemail.com (Postfix) with ESMTP id ECAE420004 for ; Mon, 25 Sep 2023 03:58:34 +0000 (UTC) Authentication-Results: imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ZgJpC9bV; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.179 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=1695614315; 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=WdG6oUlthPIzD1rC2JhHIaoZzeLYPv1w9Sr7ZAA5CbQ=; b=w58Z94G7b/U5M6zShLkb6zh4Ru9RQ3wTvD1fz7U80mC9uvVkU1g7YVkVfHFFWy0LLB/ssp GV4sD7vN8MI16PgYIdRWgT+SIkuhldnOrmppTkGon2iefW/fVEH8TfCDYa21xJovmehmgI Q90TbsTCrev1lULDSXVi01UeqKOr4V4= ARC-Authentication-Results: i=1; imf03.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ZgJpC9bV; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf03.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.167.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695614315; a=rsa-sha256; cv=none; b=LctdHf6CLERJTovsZP280YQB/vEYMynT6YBgWq2ag6BuKlgRkObSSawtRDoOQjVT+uEoui yBRR3nnm11atnWjqPRqME/nyBNlle3E+wttfpwIalJ+PRtihHTqQM+MDl6o7J35s/HlPSM PO3L1h8MaaWwBfpDxeJzSy1V5slLRnU= Received: by mail-oi1-f179.google.com with SMTP id 5614622812f47-3ab244e7113so3668526b6e.3 for ; Sun, 24 Sep 2023 20:58:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614314; x=1696219114; 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=WdG6oUlthPIzD1rC2JhHIaoZzeLYPv1w9Sr7ZAA5CbQ=; b=ZgJpC9bVUV5AxIKRsN46zlbNtJuVZCY7PgxdrS9ANttSBQUV8dFwLP+rvYFmKEc+GP Iw1qHlhmImm+4ho8foLv85/Qtb0yrQI/mJ8bXi+ZKkO37gneHs23W2+tftYUjk+2bWxi 9rE+dZsVGCGd/z8/iecEUP+CicKxnmSVB6UWXlss4eG/CG+7sLTQ8I7fV15/loWVh3Iy 3wi6ba262LKIQ4sy67JU+4OFr17JrCFP9bfS3bQorzs5EYs7Rdc1PsL1dzmyvaT7ZdsN sr+4zmkHBA9QhnKnwMupVEFwlOWzClT6CyLgcDtXKq25nNEu6Kt/hImlb0gM7b/Ds9xD nvXw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614314; x=1696219114; 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=WdG6oUlthPIzD1rC2JhHIaoZzeLYPv1w9Sr7ZAA5CbQ=; b=CAgHW/TvT7AhKdzZAhnBGDSzgS/GB4z/uTU3pcG0JRRksfbwwEOJSS6a2G0ViBEHuI H/F/byco5wyE3YaHYdH7GoKHotWl33JaswwWmvwCRwmlUjAX740T1SD3bnLqdXZ6KihA iGh8uJa3viIZAfq9FxHLMZTxQsI8V/y3i4wv91a31nzrnuLdr2JJeQcMnTyb41WMscsx T/Z3nlveSEdoWoKwcDGGaNd2WE9sGbDFN+0/G93QgqmtDfDl5SWL2YybSUtAjFkQWwHe 4q8J1G84eB6+E/NTIXzupYHzudtWoXVaW5xo0NLygfrdTyd7407h3ySijP024mdCyHkR VR/g== X-Gm-Message-State: AOJu0Yx8q5ZaFpFNUVmP5N+GhTnv39n5tWi69GpmmqdgvY8KCa1J9Rgr NfyUGCFjYFhLxAKGxO/xHv2PJg== X-Google-Smtp-Source: AGHT+IHz2ndjLi4p0Gje1YthvgpBIruj0G0SKyaU/Zdnp5MehEAkCxmAplzbTbydiUzzRnW+WyU8Mg== X-Received: by 2002:a05:6808:130e:b0:3a9:cfb5:4641 with SMTP id y14-20020a056808130e00b003a9cfb54641mr7842375oiv.48.1695614314045; Sun, 24 Sep 2023 20:58:34 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.58.27 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:58:33 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 7/9] maple_tree: Update check_forking() and bench_forking() Date: Mon, 25 Sep 2023 11:56:15 +0800 Message-Id: <20230925035617.84767-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: ECAE420004 X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: g18mjxgg8atwg48sw5dtnsawjds6s9r7 X-HE-Tag: 1695614314-675928 X-HE-Meta: U2FsdGVkX1+AYDf8yw5zyOEwgrc9JHiFyirprtnCPgOR+vHmHX6pP3S1h6FDluWJ2AXzGxbIsbGd6oR98Jd92y84spt0+N7XSvlyFWhl7doCVJi7qDgmQUaHftmMDH7xC76di/9uAcwKKxcMdOY9eWyUGjkOrwumS2fnMNfsojFeIlpCWsflbYAbsP/8XyR/dnhUpnMMioibQCd0TiLvIPDtDEe7l78hT2WAHRMVcPkwJ5PN6m8+g4mQpGhqol4vsEgyXGKKXpHpmDCo5vxGQCTak/jo9L+e/iyDIXHk1ku4T6rjKw7AB4ILFx1X1u/FB2Nbycs6OPDl0dgJfPNkScmXVH8j9FxMYO3rYfK2uz/iuqzN5rpdSaFc1C1hlNCoPOIDek3HDSl2lD+FmvcnGslx6bz5VKdH6LUtWEx/nRQV+ZBGRPq+IbV/DjI6Nsf84ldbbHBtgmMifzHnAYzp3QtSHOsIUJeeofkqaWM99hycXTDAfU5NLP1Ko/N0+EaRxJxnSWXp/vTLuDoA04K0AVB2JUi5tVc5pOAQXXZIqI0TrjwkJflcUEMYvdndnFBfqYdZ6NoctTencZiCjLZi6L3HFsnwCKuYle48BDLkey9t084z8xdhm4o13F7fhjkvyQQiviDMETvp/8W4VAtFOp+VaDv5REbzst0mQ0lvv3QPi11XUf2VeXg4fWxzHDHHGY0JRaBNZAQUpB01FHDa2Hg7RLh0ic9YY7dtTfeJbU86MfxO0AWSjwkSYG+ylA9K/Ua6SpqadVPolzO1UwD6WBqD3I6Gam2fcLDYCGtkn0OwUYib7LjSqgpDs1ns+DDd8wvS+qZgZizji6HsAZyhJY4vG8sqZQ6xixRiZ5aigxz+gP0h9c2oOfTEr8sIRZ6F30j/HDlGJLh/bPkTX4B+ewmwIAfR8TMibZxmIQkhmx4zkENoxsjuWQjqKn1O/YCr7PTdMUmxGYa1LK6A+5c fgzqcfYD Nh7b/naqLVNRHg8/gY084WXbl9aBZla0JrC4PvrPNo+uDt1QxdttskUyImdPJTxjsQL3qXDbRCi+EqRYeQrpLpDfs36hRpWOT4lPfxlNvNk2ktmm21CzTb3OfrcBMMmoeRyUD6DJ/BUZXGejW9SK2Gioac29D4HU/Ul+ipfpMeLx02hyt5Mvl/J94FhapMQypxyeNtWrWfZpVZCioXD9rPHfBx7SEWeA6zmQZn7AEV5eYqS7x4FmXvbNA+YofYLQU7D+wH0GKUQu+uA8hysAdHOM5K+TBVmT/U1MWBIx/pZQ2ZaEcuyijH14XC94NawxFezhykHuioifrPmiWKmGmFUyNY8Hx3kIPGeJCo3aUBgDGHCwDVO0wTHBouWQ/WXbELxe4FQ4d8+5rF966EFkO5Yc3BmiZWjnmlEwdl/oascZ49qKtsf3nko6z5e6CXKZunVy7v/AthPKYzOj/f3HwJn5TEg== 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: Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 61 +++++++++++++++++++++---------------------- 1 file changed, 30 insertions(+), 31 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0ec0c6a7c0b5..485d308a1ca7 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1837,36 +1837,37 @@ static noinline void __init check_forking(struct maple_tree *mt) { struct maple_tree newmt; - int i, nr_entries = 134; + int i, nr_entries = 134, ret; void *val; MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + + mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, xa_mk_value(i), GFP_KERNEL); + mt_set_non_kernel(99999); - mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); mas_lock(&newmas); - mas.index = 0; - mas.last = 0; - if (mas_expected_entries(&newmas, nr_entries)) { + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); + + ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN); + if (ret) { pr_err("OOM!"); BUG_ON(1); } - rcu_read_lock(); - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) { mas_store(&newmas, val); } - rcu_read_unlock(); - mas_destroy(&newmas); + + mas_unlock(&mas); mas_unlock(&newmas); + + mas_destroy(&newmas); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); @@ -1974,12 +1975,11 @@ static noinline void __init check_mas_store_gfp(struct maple_tree *mt) #if defined(BENCH_FORK) static noinline void __init bench_forking(struct maple_tree *mt) { - struct maple_tree newmt; - int i, nr_entries = 134, nr_fork = 80000; + int i, nr_entries = 134, nr_fork = 80000, ret; void *val; MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); for (i = 0; i <= nr_entries; i++) mtree_store_range(mt, i*10, i*10 + 5, @@ -1988,25 +1988,24 @@ static noinline void __init bench_forking(struct maple_tree *mt) for (i = 0; i < nr_fork; i++) { mt_set_non_kernel(99999); mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - mas.index = 0; - mas.last = 0; - rcu_read_lock(); + mas_lock(&newmas); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); + ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN); + if (ret) { + pr_err("OOM!"); BUG_ON(1); } - mas_for_each(&mas, val, ULONG_MAX) { - newmas.index = mas.index; - newmas.last = mas.last; + + mas_set(&newmas, 0); + mas_for_each(&newmas, val, ULONG_MAX) { mas_store(&newmas, val); } - mas_destroy(&newmas); + + mas_unlock(&mas); mas_unlock(&newmas); - rcu_read_unlock(); + + mas_destroy(&newmas); mt_validate(&newmt); mt_set_non_kernel(0); mtree_destroy(&newmt); From patchwork Mon Sep 25 03:56:16 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397208 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 2E702CE7A9B for ; Mon, 25 Sep 2023 03:58:45 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B94FC8D0005; Sun, 24 Sep 2023 23:58:44 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id B1E6E8D0001; Sun, 24 Sep 2023 23:58:44 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 996108D0005; Sun, 24 Sep 2023 23:58:44 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 81FFE8D0001 for ; Sun, 24 Sep 2023 23:58:44 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 5A35EA0ADD for ; Mon, 25 Sep 2023 03:58:44 +0000 (UTC) X-FDA: 81273763368.26.A1E501C Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) by imf27.hostedemail.com (Postfix) with ESMTP id 89DFE4002A for ; Mon, 25 Sep 2023 03:58:42 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=i9E6ft5W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 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=1695614322; 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=mGF6lWn34y725CVIBLiDuCLlZ/D9mfCg2VPUJce9YQs=; b=uAPN/dcH0tEUNdXui9qvp25YB6M3aiD3jgDUo5iKq0QDcRZqDxivWgb3nnNeCN1bWp+yx8 do2Tfff2N75KHivsWeN5BlIbQ2fs3JTw9u4aD9wMKnueLp+vhzp9+3Dg2yKRwwOnbUqZmT gzTSCyKrqpeGsApVNR9zj8hvUbxE+l4= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=i9E6ft5W; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1695614322; a=rsa-sha256; cv=none; b=5fgjY6ihiUMmSDNRVzt8IDhwVEXd6iYGinZJNEwyAMCFA8NyhzJylwFRibdAduWkyI49aC vD1litC8PYf33xYUAKPtbjPeX0FyOSVYKJJxNoOBjVTi2WlPqN9IrcbGPk8LHqhFHqL4gT gQBT+dTjOXtngblAKd4rcJSPkX4OFVw= Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-69101022969so4942980b3a.3 for ; Sun, 24 Sep 2023 20:58:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614321; x=1696219121; 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=mGF6lWn34y725CVIBLiDuCLlZ/D9mfCg2VPUJce9YQs=; b=i9E6ft5WJ0YIZ2B7ZHvs4H3lwek/psuoaSX7FaGqwWDDyntvpOegGVr+1hnzkk44AC FN909mXHd15jw9eyUHItdDa+t4WSh46Hz13900xZNyF+F8oGkg0nb8YlAn58nlHB8Sff 8WR8vXdRV4G522IAh9qIBRZDwSOCUnPaSHiUt+PtpkkPs/MjQHlYpjGbZaT+QdjXg07Y zjsKUNMMueZUZFR5dzmEzFZfYnFx3nc0WBjtyoBQ2Uv2R3NigWUpyVp5rX2BPy9qEU5q JYEEwdXQOWmwySC58YjpJ8Gyf3j3uYwkrAHx2nqGKS6In/w/npUTNbYl9dwingPgyiIr 1Hgg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614321; x=1696219121; 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=mGF6lWn34y725CVIBLiDuCLlZ/D9mfCg2VPUJce9YQs=; b=JS+nPQLWm/n2wS0yud7aP+kzuDKsSDrN9NaGdnXwQoA9YxNtivcF5a4mWBswEfInA0 0hsLRQsjjGs0o5Istr/XHZjaOoq4bF8Gt6LsQmA//zecE+D7DlpIJ65D2vU89g3ABGCd n/GQ2XknPhTdYM3WlapWsuuAG0fiBL/qDlV/2rP8kSGtKkbjqt2TZF6+RaZ49ZAf1ky1 oAMhUziENZ5wkdYghHQu8fmAQC3o3aJKYZOx1V+//W4llwSA6HyBiwPgXbgYxQfYiD37 WI6VrySW2zZJaqZeADykZv0x0A3mxt68toKI6QGcUk9m90N2C/dzBDshpFkKvtUiigM0 EKag== X-Gm-Message-State: AOJu0YwN1+7OQY36BLh8IT5g6DcL5Sx7OaJXHuVxqbJ9rkgzyPYRvu5W UuulewKQ6J9bU2rTN1bB1sSAWg== X-Google-Smtp-Source: AGHT+IHoddrSbePl0h4D+bftYrSW0wEgeAhFg5zR31drbaOxp/x1GgBhKmsKHC902H8CQivLgFilqQ== X-Received: by 2002:a05:6a00:228a:b0:692:b8b9:f728 with SMTP id f10-20020a056a00228a00b00692b8b9f728mr7716486pfe.30.1695614321440; Sun, 24 Sep 2023 20:58:41 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.58.34 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:58:40 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 8/9] maple_tree: Preserve the tree attributes when destroying maple tree Date: Mon, 25 Sep 2023 11:56:16 +0800 Message-Id: <20230925035617.84767-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: uu8ijpmcmumj5xbw3zbnrurnagj1yqm9 X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 89DFE4002A X-HE-Tag: 1695614322-403878 X-HE-Meta: U2FsdGVkX1/CU0AGeKrQdhIdzzzfXQSssOMMx/78Gwxx2OegBOJJLMlnQXt9KUwrAiK/+ksQC3nRFpxoqRsPR2VBYLCrRC1GST70uxDTCe1+o0VM4aawRRGzx9IcKgokZhTCwUgNNIy5ErXPNzfeG7Qbvawnto4Y6iW+us64K7sPTP7nkuXOAcRMM2+uRUqvfOYHDMmKN05bFkD3GMH1XxzOanPJ5psaqYBQfnw8iTqgzFiJxRSdHAbWHgPEX7tUG/I/pXMya0OJ1hf+ykSpohMznyQQHZ7P/HCDNJw+1YtYLQkIThd6gTnsqExRetCTkVPMc5wPaq5ngWtBh0GZEhpqT9GWiy3LTKJJj2g+8kujydqFrT7REmP5K7nZUIAaU1FBEIEwHQhKAZd/PyWjDioir2vWUbDSdCZueUNDVyPiyXWmHzEdInxxRD6LHYTJ0++uxZEh+/mrdC9jYNKCauL66i0zspuYVsQDc9u3kf9me7ffJ0e2ozRhiLSdJ2LBEwb8PgLA1Awxc0/T5cRxhAi2/TPz8O75Ysu0XmVyKC3yGSh/sOX290m+EjTWBivyMI9ppcR1hfmQYRgzJJSFHRI/Gio48tJRMn3xlRTg1KnZHkt4kpTcZcdoy1FUReoNJX01BVRLlfivcSk062o4vMjDEOIg/ZNBJ8t4p8qXm5fZbuWb2iTr/BvKvJyGXNxOSi3hE4jwTY+bDTmSDjUrFSPmzegcH/ODnqfzovW+b33Y9LGbQYA4FgMTWw++s8/oTniKapAAIWVupJsXqbh8PXyRIJV1LlEwqvPUcI8MlfWUOFrtPiT2C9HXZYozkw8QwxW+YGT8OKnH949u5xGF6WRc14UM3OlPvcd9+67Sevg7qZqwifmCbnMjJIvNEiynpo52P+CaUVnHAY097gIpBLn0vagYyBhTPPD3yhYDnllKTEZTyph7VEKfr34ToGY/UEqEOwONglf2hQuAZq1 c8P0/+iv D9e9jxm2Lz6FCFcWhrRwp5yj7mLBMwJWWhwoUZLxAlwDv3WaNqa5I4mgoHh8Fei37d2jucc9oQoQFHVkII9zQ2H8baVasGr8cVS8mlSHPuDodbOqHJdHpvRLXoONofHyVEtuWrv7979iRGsJ6Ff8Lbsv3PlAg7rnFaWG/46SKf8wtvHf7M7+DeW4GMw62wuf8gVe7pquvG8yzONKtwdpuhbpaFAO8SW60JaaYRCLRZRU1L9BvpFULHDIPD7rdkZlpunuD2j3rABU9zSp85Y5+BBE2uYL3plwC3FFDa20sIdPod4MzrCZ2GXZU2hbJCy6CujSsJqYWs15NtlLfMWTaniwyLIXi/Q7JHxttaqatF2FsahDURZPmOR/YoZ+83H6yxaDkdFfcCRUlmCd0RqYMSZ3HusQUob1DVN9Mljlv5y/H5S36qj38G/QF02xYgBiKLMHoxm6lV5KCy1hfV8VLc/QWFw== 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: When destroying maple tree, preserve its attributes and then turn it into an empty tree. This allows it to be reused without needing to be reinitialized. Signed-off-by: Peng Zhang --- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ed8847b4f1ff..ad06105f1a54 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6670,7 +6670,7 @@ void __mt_destroy(struct maple_tree *mt) if (xa_is_node(root)) mte_destroy_walk(root, mt); - mt->ma_flags = 0; + mt->ma_flags = mt_attr(mt); } EXPORT_SYMBOL_GPL(__mt_destroy); From patchwork Mon Sep 25 03:56:17 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13397209 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 AFEA8CE7A81 for ; Mon, 25 Sep 2023 03:58:54 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0E6A58D0006; Sun, 24 Sep 2023 23:58:54 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 06F1A8D0001; Sun, 24 Sep 2023 23:58:54 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E2BD28D0006; Sun, 24 Sep 2023 23:58:53 -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 CD72F8D0001 for ; Sun, 24 Sep 2023 23:58:53 -0400 (EDT) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 94D321206B7 for ; Mon, 25 Sep 2023 03:58:52 +0000 (UTC) X-FDA: 81273763704.04.3651132 Received: from mail-pf1-f178.google.com (mail-pf1-f178.google.com [209.85.210.178]) by imf30.hostedemail.com (Postfix) with ESMTP id A3CBB80011 for ; Mon, 25 Sep 2023 03:58:49 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Er4iNnGB; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 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=1695614329; 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=TuxzCiUZ2DltVBwaDerHzUDGuv+dY7UUUi86i/t9rYc=; b=GSnVtrDYrgKmP11RMgu6uLGGB/GohZY19iC2bZQydJahLZc6C/LBw+c5N2rrMtcdespVeF l3t479ifT6AHw9dFwcrSBvFgg1/oh8MuzOmi8nC+QKMGIQFBhnE4grmqc4njw8mU36lEj9 ajvvDda+d0PK5We5TqxMqzM0dtZmuhY= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Er4iNnGB; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.178 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=1695614329; a=rsa-sha256; cv=none; b=F+QGcYFubiH7ajDc9qp/re6lC2QyYpmFhsv5SdoXeMR7qucftwPuBVFO7WtzcBu+jg1nO1 lxcDBZaYKv4N4VyoQsfoWA0I1K8Y5o9KhxMm/WPW5mwoDCPfPeYsBzTs9aIK8FdzhDRjr3 xMn9hUdGCxen99D5ThI/W3sJV7r5ouA= Received: by mail-pf1-f178.google.com with SMTP id d2e1a72fcca58-692d2e8c003so1177048b3a.1 for ; Sun, 24 Sep 2023 20:58:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614328; x=1696219128; 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=TuxzCiUZ2DltVBwaDerHzUDGuv+dY7UUUi86i/t9rYc=; b=Er4iNnGBSrSNPoTytbwYlIRJTVzW0Oyr23/TcJLH0ExWsezWr55UUxfQ+GylJsPU4m ftVx0tEFbkwR9GBiE1tv7GxtrTS/0/NiVcwjz8jEWciUgIe922kSx6zPWlkw4Ujjyh7/ WpYIS5yPPIzyBltkPyUB/l6XnJRvIUvWXwR7w60/tOpYhdcUnmD85GeBwIIq4och20FA HnyU/NbJYmpW80d0hYZ8iFfOb2rvCwPF6v8/dmvWuL2TCTipxvLFt3GmnUrCHGcdzbI9 EZZhEO1n9kWpE1DFjocJJf1qf6VYWKCdOuPDZoP4kMQrdfpVNK4VWCICMmQ99f294rt6 xRjQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1695614328; x=1696219128; 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=TuxzCiUZ2DltVBwaDerHzUDGuv+dY7UUUi86i/t9rYc=; b=aI4i9tQ76FjsM7GMBUlSlZlru/oMXZ86r9iUCyLYRC+swTuf2evd2NPWy9zzl5MUEv LNSLsMVqWs1ZF3q0BgpsR96tRv4GPWC3wHEZKBDDtmbY6IoxByisVMeg9GSOJy9IeW1U T4xa2aQvUGnK4qlX5gyKsTCSnk0tWW+SOBbA2uOJEITB5dg0VtyB2h9vGTmstmcLFh1E kYVdbIcAG35gC0aAqEDT14cFQDazEzjAabqupkPId+KmHcdACpWAbgoLiNygPYnaAyth 7sAvzUS42uUp4l39utjEgsMYBRC29MVT70lmZyXHBzR7nBwy68bbgynYIEIKS54NUB3t wWzQ== X-Gm-Message-State: AOJu0Yw/UfiF3KxOOh/NKw9QnINJ3UZ0JfBFNwVtGS3jxxSlPP0rAu2J 1IyZqIZMVu+JD7K1966+zTNowA== X-Google-Smtp-Source: AGHT+IHw8XcQ7+xdyaLtlqVJu3dj2MsTxRgYeF9x/JPrG30bCLmD6fzrqcUdIisXeiq7bW/XX9H8sQ== X-Received: by 2002:a05:6a20:7486:b0:159:c07d:66f0 with SMTP id p6-20020a056a20748600b00159c07d66f0mr8362964pzd.6.1695614328529; Sun, 24 Sep 2023 20:58:48 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.146]) by smtp.gmail.com with ESMTPSA id fm1-20020a056a002f8100b00679a4b56e41sm7025387pfb.43.2023.09.24.20.58.41 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Sun, 24 Sep 2023 20:58:47 -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, mjguzik@gmail.com, mathieu.desnoyers@efficios.com, npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com Cc: zhangpeng.00@bytedance.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 Subject: [PATCH v3 9/9] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Mon, 25 Sep 2023 11:56:17 +0800 Message-Id: <20230925035617.84767-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230925035617.84767-1-zhangpeng.00@bytedance.com> References: <20230925035617.84767-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: A3CBB80011 X-Rspam-User: X-Stat-Signature: f9f5ufp1gqjequck5kfybcn6p16ubbu3 X-Rspamd-Server: rspam01 X-HE-Tag: 1695614329-608867 X-HE-Meta: U2FsdGVkX19yCSFOtI0P//tWGc9Q/RqGPHU3K3d1C8/e7SYmpRCnI0w7CKN5N1zy22lExMh1auXZlC5s0y4xcuRN8VJ974lZseI5rbZmp82GmkFY+GJDy5x174GU6EYq2ExNXoQMOsP/UBpGKydlxnQhnfCkz9o35yScQT8Tc9J3oLw4nvlXIvfAm8JCX2iEQJdhs6IqOmK3pCX31yCRXeFdWq0PeSLTjDKMV3ijSiPGemimrQBdZLi6rLJ5SfjgTGh+5yTMirJeAPXYbhRn5dNUGksu0rXH/BVriLdRKjuKrfLsP7BCLC3k2YmWtGtIFIrCLLMz97ZmP7GjvrMaUeicenKq0yJoWB6wb5mFzVS6LJbr31mQd8noEWGjbpgjxFbRlSsGcnIdr2EpTwnsv/dzAuvP72TNBiLA/nXKixjUnekm3Nd2pyDhSGmunQUbZdmYlUSQplkt7KTLl2StFBqxo2djKdJ2Rv6Ue5GTK85I5sMRJZAqrk1OSgKPCCzMydYAI31RuVFrS6SjLhYode1uRzOmyWZaaA5YmM6ibGCxxNnwatFWK7s86/IwT6H89dJIvnJVjEk2Cjsm3N3x1c44UE8ge0stolim4plAImIs0cCa4OdmnlcpPLaqh6HxYO4Vygc8gDhy0smwandt8lkZQgmrWY7YsRnJu06ALYhSsiSZLJ4Sb2/G8uaFR5iYInL8V902cB86xpi2kwF3VjibcvivZZ2L5+ojbGcd1wqYfwcbbKh2DjUqc5XH6/WeEfzbqTgfLpWOd2pjNCmxUeLpH2ChvTSEVT2gzKp6VZEdtlnMOM6XVXOgFHCiG1YOX2c8ttFdGwCbVtrdi+tWTlXk1Hxg9Mvp5T6DLsFG++b+SEgJFwxr8RmXp0/JdggM5UqaaPFNyh0kAEGgWXM7TSI7FTgbaBkm7YiOXoqbNbyxLYT072l/oNada/suwtlbyfEDNVtok3XfIanRo+N 8pqPeaes q2VXTns8pWJvOQjbgfFiTklSk/vM2EsobMaX7m+iDc4m1ZK6R4oG4rs+9FBfLtgvmfIrwC0JCLA83wcsq5idsKxDKv0QRU5ob8RVB+0AFp5OMCIB38piw7DCDlQVLEZCQTcvnMk8pDm1mOmslSp6sjDMnjQ3O3oFbp8VcgNnbx506nNukud6HXIxNvT7dF5nSCioJkmDCaelaSgLCE7xL+VWxWhnD7SiRAY3Hjlla2qMlYGpFgQ83NHpC/Rt/JIos1DlAl0/6hUoLEwOCHQf/VWlLNO/rkTw+RtmBfb31BgZL/nnDQ0QNa00iNUZELIaDOyI5B7TM3Pabl4sNodCo47VTiZLEb9JY9H0Fv3dLjGoYSZ2mEkrdys78BdaOe+Lgn17/Ti9he/ogF8E8FPRXO7ISf8sQuL17tdtlxKbTNAUZCwa++aYJI7oND5b5TMplfibwvqbtok6jRyPlgU7Bc62iEtmjyefw+sqGiy2J+ZvyNKir44wyXIRNUJ9eHUaySomu 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: In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then directly replacing the entries of VMAs in the new maple tree can result in better performance. __mt_dup() uses DFS pre-order to duplicate the maple tree, so it is very efficient. The average time complexity of duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization effect is proportional to the number of VMAs. As the entire maple tree is duplicated using __mt_dup(), if dup_mmap() fails, there will be a portion of VMAs that have not been duplicated in the maple tree. This makes it impossible to unmap all VMAs in exit_mmap(). To solve this problem, undo_dup_mmap() is introduced to handle the failure of dup_mmap(). I have carefully tested the failure path and so far it seems there are no issues. There is a "spawn" in byte-unixbench[1], which can be used to test the performance of fork(). I modified it slightly to make it work with different number of VMAs. Below are the test results. By default, there are 21 VMAs. The first row shows the number of additional VMAs added on top of the default. The last two rows show the number of fork() calls per ten seconds. The test results were obtained with CPU binding to avoid scheduler load balancing that could cause unstable results. There are still some fluctuations in the test results, but at least they are better than the original performance. Increment of VMAs: 0 100 200 400 800 1600 3200 6400 next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183 Apply this: 116505 85971 67121 46080 29722 16665 9050 4805 +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96% [1] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang --- include/linux/mm.h | 1 + kernel/fork.c | 34 ++++++++++++++++++++---------- mm/internal.h | 3 ++- mm/memory.c | 7 ++++--- mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 80 insertions(+), 17 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 1f1d0d6b8f20..10c59dc7ffaa 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *); extern struct vm_area_struct *copy_vma(struct vm_area_struct **, unsigned long addr, unsigned long len, pgoff_t pgoff, bool *need_rmap_locks); +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end); extern void exit_mmap(struct mm_struct *); static inline int check_data_rlimit(unsigned long rlim, diff --git a/kernel/fork.c b/kernel/fork.c index 7ae36c2e7290..2f3d83e89fe6 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, int retval; unsigned long charge = 0; LIST_HEAD(uf); - VMA_ITERATOR(old_vmi, oldmm, 0); VMA_ITERATOR(vmi, mm, 0); uprobe_start_dup_mmap(); @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, goto out; khugepaged_fork(mm, oldmm); - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count); - if (retval) + /* Use __mt_dup() to efficiently build an identical maple tree. */ + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL); + if (unlikely(retval)) goto out; mt_clear_in_rcu(vmi.mas.tree); - for_each_vma(old_vmi, mpnt) { + for_each_vma(vmi, mpnt) { struct file *file; vma_start_write(mpnt); if (mpnt->vm_flags & VM_DONTCOPY) { + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL); + + /* If failed, undo all completed duplications. */ + if (unlikely(mas_is_err(&vmi.mas))) { + retval = xa_err(vmi.mas.node); + goto loop_out; + } + vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); continue; } @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, if (is_vm_hugetlb_page(tmp)) hugetlb_dup_vma_private(tmp); - /* Link the vma into the MT */ - if (vma_iter_bulk_store(&vmi, tmp)) - goto fail_nomem_vmi_store; + /* + * Link the vma into the MT. After using __mt_dup(), memory + * allocation is not necessary here, so it cannot fail. + */ + mas_store(&vmi.mas, tmp); mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, if (tmp->vm_ops && tmp->vm_ops->open) tmp->vm_ops->open(tmp); - if (retval) + if (retval) { + mpnt = vma_next(&vmi); goto loop_out; + } } /* a new mm has just been created */ retval = arch_dup_mmap(oldmm, mm); loop_out: vma_iter_free(&vmi); - if (!retval) + if (likely(!retval)) mt_set_in_rcu(vmi.mas.tree); + else + undo_dup_mmap(mm, mpnt); out: mmap_write_unlock(mm); flush_tlb_mm(oldmm); @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, uprobe_end_dup_mmap(); return retval; -fail_nomem_vmi_store: - unlink_anon_vmas(tmp); fail_nomem_anon_vma_fork: mpol_put(vma_policy(tmp)); fail_nomem_policy: diff --git a/mm/internal.h b/mm/internal.h index 7a961d12b088..288ec81770cb 100644 --- a/mm/internal.h +++ b/mm/internal.h @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio); void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, struct vm_area_struct *start_vma, unsigned long floor, - unsigned long ceiling, bool mm_wr_locked); + unsigned long ceiling, unsigned long tree_end, + bool mm_wr_locked); void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte); struct zap_details; diff --git a/mm/memory.c b/mm/memory.c index 983a40f8ee62..1fd66a0d5838 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb, void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, struct vm_area_struct *vma, unsigned long floor, - unsigned long ceiling, bool mm_wr_locked) + unsigned long ceiling, unsigned long tree_end, + bool mm_wr_locked) { do { unsigned long addr = vma->vm_start; @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, * Note: USER_PGTABLES_CEILING may be passed as ceiling and may * be 0. This will underflow and is okay. */ - next = mas_find(mas, ceiling - 1); + next = mas_find(mas, tree_end - 1); /* * Hide vma from rmap and truncate_pagecache before freeing @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, while (next && next->vm_start <= vma->vm_end + PMD_SIZE && !is_vm_hugetlb_page(next)) { vma = next; - next = mas_find(mas, ceiling - 1); + next = mas_find(mas, tree_end - 1); if (mm_wr_locked) vma_start_write(vma); unlink_anon_vmas(vma); diff --git a/mm/mmap.c b/mm/mmap.c index 2ad950f773e4..daed3b423124 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas, mas_set(mas, mt_start); free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS, next ? next->vm_start : USER_PGTABLES_CEILING, - mm_wr_locked); + tree_end, mm_wr_locked); tlb_finish_mmu(&tlb); } @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len) } EXPORT_SYMBOL(vm_brk); +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end) +{ + unsigned long tree_end; + VMA_ITERATOR(vmi, mm, 0); + struct vm_area_struct *vma; + unsigned long nr_accounted = 0; + int count = 0; + + /* + * vma_end points to the first VMA that has not been duplicated. We need + * to unmap all VMAs before it. + * If vma_end is NULL, it means that all VMAs in the maple tree have + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX + * when using it. + */ + if (vma_end) { + tree_end = vma_end->vm_start; + if (tree_end == 0) + goto destroy; + } else + tree_end = 0; + + vma = mas_find(&vmi.mas, tree_end - 1); + + if (vma) { + arch_unmap(mm, vma->vm_start, tree_end); + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end, + tree_end, true); + + mas_set(&vmi.mas, vma->vm_end); + do { + if (vma->vm_flags & VM_ACCOUNT) + nr_accounted += vma_pages(vma); + remove_vma(vma, true); + count++; + cond_resched(); + vma = mas_find(&vmi.mas, tree_end - 1); + } while (vma != NULL); + + BUG_ON(count != mm->map_count); + + vm_unacct_memory(nr_accounted); + } + +destroy: + __mt_destroy(&mm->mm_mt); +} + /* Release all mmaps. */ void exit_mmap(struct mm_struct *mm) { @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm) mt_clear_in_rcu(&mm->mm_mt); mas_set(&mas, vma->vm_end); free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS, - USER_PGTABLES_CEILING, true); + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true); tlb_finish_mmu(&tlb); /*