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: 144226 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp1012281vqu; Sun, 24 Sep 2023 23:29:11 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEinbc9LTWAPakvqS6zHNdiZSkB40TNLOnKiMJm9UPoy6Qj2RFe8bFmQSRjqDcPrH85p+7+ X-Received: by 2002:a1f:4dc3:0:b0:48f:dc94:1b37 with SMTP id a186-20020a1f4dc3000000b0048fdc941b37mr2301184vkb.5.1695623351477; Sun, 24 Sep 2023 23:29:11 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695623351; cv=none; d=google.com; s=arc-20160816; b=GTFNeR/6Hw7I5aD/q+pwcA5UaVojvnbYOYQj0G6Adpqzch7rVSAKcuWyLYGa30wb15 ROikC0swZHhdVS7wb2TmEDMSlo/n85DRm/mQ2LfSJCO/LXY6du+eephhE/itKaLi1FrI BakEkOUcsLtH6XdQn5jXnIqSQ0aD/a8moPZ9WRtMW1p3aGEXe+tO0kEjlGIOWO8DziE4 B8BURsDMpkI/3krfOUn5J/cigtq5s0RhyKtbi9GDHcBSw3Y2Q3/wqb7jUl1MnYPAu9r8 30SraMAOf7MLkX8Wxai4zArFXIf9ATN7o1bltG9brqM3Y2NPoGAoDOY3yQg4vvnpngIB ki5w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=N+yL99gNcpn5/1bA5Ytv+b9WTtrbhVjUMVj2M753OVQ=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=n3x/GBvHlFLM5uSRZ7i75/clZ9mtX2mUv/AQcpuptAZw4zBs5Gj58//ZFF/GInR0zl kZrETEajrBbDoSIEj4Un8C0GmY3tfzHo3h+sH0b4mP63Wqo49xeSW/vQ2KRrUNiX1kHi M6JaedpFaThJ3t+4xdvZek5ywttAjh5vRIe2EwAjN6E/zG+ZyHasSdgqcz92ruqDY3mQ AUsrZCCFrVltkPf1jzkQpKC/ov84Z+kWUj9zrQZdHhrprMc9nuuO67SpuFZETdDjyJBx TSeWulfLuSHUSVMKpVfnxfv7sHdV91P7cAEKvLfZfuxxGRuAPHXXkAoL14h8tasc+n3u UP6w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Xhc8+8CC; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from howler.vger.email (howler.vger.email. [2620:137:e000::3:4]) by mx.google.com with ESMTPS id t5-20020aa79385000000b00690a77be748si8756527pfe.235.2023.09.24.23.29.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 24 Sep 2023 23:29:11 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) client-ip=2620:137:e000::3:4; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=Xhc8+8CC; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by howler.vger.email (Postfix) with ESMTP id CC28481143D1; Sun, 24 Sep 2023 20:58:00 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at howler.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231393AbjIYD6C (ORCPT + 30 others); Sun, 24 Sep 2023 23:58:02 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39846 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230194AbjIYD6A (ORCPT ); Sun, 24 Sep 2023 23:58:00 -0400 Received: from mail-oi1-x235.google.com (mail-oi1-x235.google.com [IPv6:2607:f8b0:4864:20::235]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9AE1AFF for ; Sun, 24 Sep 2023 20:57:52 -0700 (PDT) Received: by mail-oi1-x235.google.com with SMTP id 5614622812f47-3aca1543608so3779882b6e.0 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=vger.kernel.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=Xhc8+8CCFVgq8M4fkhioYGXr0xqfY4HsZHOyHLy8IDVBp3L8OA7eySBcvMY2qitjwc KLJMzPgkSFwtG+oM5PTp4X+0ct2tqU1Wk1C31UZdGp9euwLA5yiinszOmB+z9Z3HJwi/ qlXpqj1mxWKgrUBk89XLRypOpBrjPyilwCsGF+NprTTt3sKuRuqoP7fmUcuaLiPVbxcD TWFy8/CtNGwVzVY/fyS0odH/DOvEfCASLl7UaJWuSPAvTufb00yMzq2zSjifdjjJdui1 PEiW7JlK8xpmd/oVDigBc9MMsAj5HvoTonyZCLNkXG7m0ge/2Lvz+n0Kr0rXSMojmI0Z 0ToQ== 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=V0pGTwL3ijt7/kyLD7/1oSYZEhli0tH+jTMRifqOlyi1CKZg+WvUHnCfiIV5MPMsmS FbZNrskG9jPM15WVwIH4vi6i974vRxwcQTI2cw+BcBwUhKvVaugfMmj+1iRV7MsLxT6g cBxjMnvmjbmAQ2A95aZFbadZk6fGHfaeIhdOWlvY86lYIHgxOvILlZH0oefChwq/S5Tw A9AF2kW7fH98vXLRgwVZqGVZ+pvqO1Ua4nMihtoWeslnJPaTjSoGGZdMC0RvJJWKkjM3 NRWOIHzwiK/HhNrWy3pE81kHTTk7qyjggnCJ0kjBCf8uRx8uy2G5Jdz8P6KVR9rx8Zbn gbPA== X-Gm-Message-State: AOJu0YxIt+d5EdD6s4teY7tdmlWfpPA3/e/WM6i/0UxTDVaIZY9NGKYN o/A2j9RmeAIhOFV5F7E3+5pPAA== 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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_NONE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:58:01 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1777989951245694427 X-GMAIL-MSGID: 1777989951245694427 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: 144191 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp964002vqu; Sun, 24 Sep 2023 20:59:07 -0700 (PDT) X-Google-Smtp-Source: AGHT+IHJVCsaFTj9RSxzshgSUHdUR5xauZFWpVzu+60869rCFf1fUIR05tospw/iVC5Yy6ZNQj61 X-Received: by 2002:a17:902:7443:b0:1bb:b86e:8d60 with SMTP id e3-20020a170902744300b001bbb86e8d60mr3659485plt.46.1695614347067; Sun, 24 Sep 2023 20:59:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695614347; cv=none; d=google.com; s=arc-20160816; b=U+ksfq0QO87DThjP84wBJcMkFS0pMj0actbq5KxIeGFAeHV0ExD3EOs4aEODe3Gifz rRS/b5h6IFHwA65HEESLw69GRijo0h8NeaiaAXUpeQ/y91wV5vSRGv50d9/bzL6BKf/U 4N4xxVtxuP3e73jEdFxTaak7OLMWOh4DK3DOvJqi8k4u6N3O2o1KgyxgtLih1b3z1IeL ymPisQjUrD78nyBSbrmXoE0OVZmIT0123HCeIAw6cahLQCgE8yMCLquwE9Smxn/wwjbr 4QelZUTHkMOuk1Toux5RCJp3VYhXFhvXKLvTpaQ3fquBBKn8xJG6rC3it1X39ZtB5crl FUfQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=KhsUxrKihKzaZBkbG2I3+KMiT6cOrZp7m1AFdT6cq6c=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=u8ApPi1ZvdVHfymfYrerA+zExeSA6O9tu2o/YmmyuOl9hAjnod1wD6UbMXkt8Lye+0 PGDidxxNrMrMFGrfV0csDTbhYiFpElvbRUJSWlpc9xbYwDKdjfQ3E2I2MTvzpCcRGTQC 7Z6zEnkY4wP//pmRyzKnVSYQr53nkk3oThLtqoTrq9NjrKNfBZbd5yqIrvWmdp2VMTf3 OswADI2Sz81QV7KW/Rzqnta/D8UM0KG0oNhDDNdHUNZC30Pw0z04eArXZVCdYeAma0vv FSlx845+Mlm5AtAsCrpT/ABJIdlzuJTMG2esQhYeynCAfwAkswMdnm+8LQHRN1xZc6HT W8fA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=ZPQmF96q; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from agentk.vger.email (agentk.vger.email. [2620:137:e000::3:2]) by mx.google.com with ESMTPS id j10-20020a170902da8a00b001b9be39eaa8si9612166plx.348.2023.09.24.20.59.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 24 Sep 2023 20:59:07 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) client-ip=2620:137:e000::3:2; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=ZPQmF96q; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by agentk.vger.email (Postfix) with ESMTP id ECEEE819D1C4; Sun, 24 Sep 2023 20:59:02 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at agentk.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231843AbjIYD6r (ORCPT + 30 others); Sun, 24 Sep 2023 23:58:47 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:44402 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231717AbjIYD62 (ORCPT ); Sun, 24 Sep 2023 23:58:28 -0400 Received: from mail-ot1-x32f.google.com (mail-ot1-x32f.google.com [IPv6:2607:f8b0:4864:20::32f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9E4ABFB for ; Sun, 24 Sep 2023 20:57:59 -0700 (PDT) Received: by mail-ot1-x32f.google.com with SMTP id 46e09a7af769-6bdcbde9676so3825674a34.3 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=vger.kernel.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=ZPQmF96qpQll08vJTACYLiEM7GLH8jK+X1xhokrCi95QzjiE8lgpr5xme4gHjh2eTs J8L/qGV9laUgwmXS3fCTv7RttW//NZCB/ScJi771r7ZaV7pUxIfZ6f9bb5XfAeWNVDSx f7YuSyHvdjQ0PIgNW6V6Q/DYKaor7cxcafFoNUccBBnMgJhcM725BGWvxxwRCkrB/nVd 9ERQqSBYw0r6PXU/fAWuGzSN7zEORZ5qVI4Islu1tS/3cb0e2KpJ/S6FYa4IWprwIZU8 IOQ2fErQgHZlNBUgCja0V+z8sl/fAv6Q59w5pILdTZsOYMyhVNLJzS9ux1vFX/gZ54NX rFGw== 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=gqg+E77xs2/700Jm//kQt98l0VfAdES5dqekTjlVelExkeL7cdnihrkLxpKXpTN35F gqknp71k+ZJA66czSHjpfFTUiBpuz/C1TfKmledELHnuV2HuvL6fJZtL8GQfrFTScbuh 2FyValJRTTpFGgnaT0c0ln7D8dD82TxcVEKhsrw0dQ8cPO0gB/6/TRre0/ikHY2T0KL8 84scB48JEyHybo3kHS+RxG2YbC5jlT0c/bCMLqqHT+yCMzPaxc0d3Ruh945uD9NayT7z trscqzMf+iV4ZKmLqb7KQalyZpJR0Ajw37wgu4YsRFYGJBjINVzicKEqfwqGMo3uBpJx 5KCg== X-Gm-Message-State: AOJu0YyYeZE4a9MH+DhOV4uSbB28UciA5+MO9Q9Hm9VkAabXLd+z8IC2 kuH9stBpo+LonOJJWvU0H0JutQ== 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-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on agentk.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (agentk.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:59:03 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1777980509263155318 X-GMAIL-MSGID: 1777980509263155318 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: 144384 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp1133087vqu; Mon, 25 Sep 2023 04:19:45 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEAK3KGD5GqETkFE5GbfUjUTpXRqnhqkvTGh/LObmEw1pQj0U3HvCwmVLhrxkOZ3wuIuSwq X-Received: by 2002:a05:6358:428e:b0:142:d62c:78e5 with SMTP id s14-20020a056358428e00b00142d62c78e5mr8055849rwc.15.1695640784795; Mon, 25 Sep 2023 04:19:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695640784; cv=none; d=google.com; s=arc-20160816; b=QW0FQd6tPA+UjqgaIdHjK+05aZMYa5mkfXdzWrl7/slWy1vWZjQPEtTfSmL4EqHKMR 5sStwm0Cj2jONcapzcIQbC2SGZ0eMMdE4jkgUa6WFgDcacrNq+Zk6bTd91rBjN8HdWO2 pChVNjcbmAG07rfTLBvSCb4lmok2wy4U9ryxa8eOKKzcl9zbcUPNEbYKUkdL+rrKAyjF 0182KjD6mF0ff8iUpP6wI8KVQWJh0dp5wBvyyg6533baUinVrUGrN0LDn8L7dzkNwVl8 p9/oLuGUr7Y8Wl1gHbYFvxqCrLTg1sfp3KOFte88zikUIcYSYDvTtm9B3RUqrzFcauXa XXPg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=rqwnnGV2scv+mYD40c0RyHprYCvZzM/H9rjqAIwjogQ=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=sut5eQI9CpR/xTLpeFGXTRkLxj3kTvPsCG2h7TBZWvwsnICFnR4SSc40Ec/oHFU4XC FZRL6JSMLUXscTD7UVahfWofIbCqqGgVmxjsz/X+AQXTmXDuG2FKB3jZnTUkGIQfH+ot NjZ61bIpDbh7fSJWs3yWuExInypgtaErHMkcvAHCnAy7Sz0V7KPo34hOF8Yblt5Co08u 4MkOqvy9TI9TRS4JFi1S7hy0famYpsjwqQyQnLi+I82Hi7eqXuIkG94eGuvGcTXcJQUf Vbt9B+5aaX0lyaYMsZM4jCDtWdTd3mHY8q9zWan/tpXxN2MJrr7jc0oJ/SbyCUMTo97r s2ug== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=c6JUMLka; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from howler.vger.email (howler.vger.email. [23.128.96.34]) by mx.google.com with ESMTPS id m1-20020a656a01000000b0055379a7131csi10435763pgu.721.2023.09.25.04.19.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Sep 2023 04:19:44 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) client-ip=23.128.96.34; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=c6JUMLka; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by howler.vger.email (Postfix) with ESMTP id D48CF828E8FB; Sun, 24 Sep 2023 20:59:00 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at howler.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231737AbjIYD6w (ORCPT + 30 others); Sun, 24 Sep 2023 23:58:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47686 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230300AbjIYD62 (ORCPT ); Sun, 24 Sep 2023 23:58:28 -0400 Received: from mail-pf1-x433.google.com (mail-pf1-x433.google.com [IPv6:2607:f8b0:4864:20::433]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9325F116 for ; Sun, 24 Sep 2023 20:58:06 -0700 (PDT) Received: by mail-pf1-x433.google.com with SMTP id d2e1a72fcca58-6907e44665bso4925998b3a.1 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=vger.kernel.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=c6JUMLkacUSWZZJF44kHBg4S7bgbH0khGCnH4N0zOvJtfHFjD3NT73Bvs1m11XgOWz tkndx2ArElMkZVCtWMm/Km2dwDmhew3iIYNQ8qe3KT6zIRUMrvakMBgJvW4gh4w7DHwp NFkXXn0KdoAnPW5l6c1TvMHlpjImEU0IPhZ4sMHhVKmM/fJwtDa5fxsNoMlcgBPKNzwg LzoqmOPQSIk/WsphOeXst+CL2JyamFeXw4Ga8zkF+Rj2hWP7+Z4qmaEuVpD/NxbMNnu7 b82Fr52dYsHDYHF0fBmygfALYNIpdjrgpGtt4MZeN0HRIIPP8aAaXDbOMRSpAO0NdxCp MK0g== 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=iv8N/dN3Wx2rkDIVpsS7bvKwPDL8djtUKM19p55euxiC4KtaDWjG5jGULAuLw4WxXh ip04DqfENdAPvgEkl/AbHfVoSObzGRF+PzNTkQ59yihlJfMsXoGk2WiJCfnAhv1UDgOn c09iOaZks+nFFHExeidUdHb1Ou/1v/nZ+29rfleeiM4xJpa+2Cvm1/Gpw9Ft5JYI/0sm IS89AS1NDwyXl0ckaWPMvwx/ruiHRq67W6G2uDIJD29igYKFjgTNkLHoHqVtAPMgO0aZ ecyWlRaIAlC9pHiXXmoUp5oc/TA/VoCEUWEzaAWQKWgDKtJ36w11MoRjZAXTkRfZciOM /PRg== X-Gm-Message-State: AOJu0YxA+gFsGjTJxXEsVo1pmzVq6Ld2KiuxzUCgd4/FvWkqFTl7yS2E RYizcE2bhJWtQahaecKfJZf9KQ== 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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_NONE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:59:00 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1778008231156830402 X-GMAIL-MSGID: 1778008231156830402 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: 144304 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp1064435vqu; Mon, 25 Sep 2023 01:47:16 -0700 (PDT) X-Google-Smtp-Source: AGHT+IE8HayJOKHk8b8TJK/u7lW3EsLVk8yPqWt/XL7QagTWpDCwAdeKFA9Qyvc/GKIh2rgKuHuD X-Received: by 2002:a17:90a:71c2:b0:263:1f1c:ef4d with SMTP id m2-20020a17090a71c200b002631f1cef4dmr3729892pjs.10.1695631636420; Mon, 25 Sep 2023 01:47:16 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695631636; cv=none; d=google.com; s=arc-20160816; b=YF9oto/MdsJ6r9SiwCjFNvXKHc5Gql48hV08KGzzkUhNW1cDosxW1nmUuMlEFQG4rZ V+uakB1bAhbzUJQdswQ3g9Vbajwet3Tmqlmy2KWJiWtjx8ug8wr79lZGLhbK5rAUt8tM JOSnu6QSfwTwECYaeHKQNCzD50OZ2twJQMvdW3ciJrNmcHFUyb0ZGZU1jYD4G8IuQMGC 6lmPAhbRQ3IS+sdJTNdd37SvQUWd9mf453Qe9oPNve6g4ivj3rfVHHOApKZqTEo5ncWf 8cmD3eVk9Je8sappePKVCaHs5XaAgIR3Onz00eaDW5vAUx4DnqCcSGksCaFu85IJHn1/ oGtA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=BW35kxFpM5nzQ+paC5awg40HeSFDMCn6AOfZrv3Q48s58G7tKBTa31XuKw9wRQjc4N EqtRZPyk4O1kQbwlURRILyyv9ga/RI7CqZ9aJOsWtf4eqgFHE0zL5S1mCYSpD4eWBCkk Fh5niBhlZLGAnwVWOLn+XJdjh/a1vqsSAIImHymMLaM8YmD1/BXxU6qY1jmvEXBa34HU nxKKJExjTE8dJNhsQosy8HWMR6EOPnGc+5jyBXMH1/w0SCx6Mxv2hKXYZMpGWjVJj9b0 vet2TQnQegbvSGKkqKjqEg1zO/e9v9pwzAi1oAi/apWeSNPWMLIF3G/Fp06ALFIi4y4a UvVA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=DtpxWjs5; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from lipwig.vger.email (lipwig.vger.email. [23.128.96.33]) by mx.google.com with ESMTPS id a17-20020a17090ad81100b00273edf4d3a5si11851627pjv.68.2023.09.25.01.47.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Sep 2023 01:47:16 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) client-ip=23.128.96.33; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=DtpxWjs5; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by lipwig.vger.email (Postfix) with ESMTP id 81D2A8167D81; Sun, 24 Sep 2023 20:58:42 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at lipwig.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231775AbjIYD63 (ORCPT + 30 others); Sun, 24 Sep 2023 23:58:29 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47778 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231767AbjIYD6U (ORCPT ); Sun, 24 Sep 2023 23:58:20 -0400 Received: from mail-oi1-x22f.google.com (mail-oi1-x22f.google.com [IPv6:2607:f8b0:4864:20::22f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C2F6110B for ; Sun, 24 Sep 2023 20:58:13 -0700 (PDT) Received: by mail-oi1-x22f.google.com with SMTP id 5614622812f47-3a76d882080so4059715b6e.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=vger.kernel.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=DtpxWjs5NRdJj9SV5ErH6k4Yv/eGDATvhKB0dldjew/9OQ+SujLxPnk746EZfSLgk4 FeotcqJYd+1UPRWenPVnVAoB7wJ1NAx/lQMQbvNKlco1e16bgkC3mOi/NBYSibpk/cDB hFHdieruZsKzGmUDDf3ZqQtOM2Eg34stUNv2iZSHonBRsH1Vlt7ZDOKpW4in84gp4QJz wp9mxfZkIBAl5rYA5WrdO2HapHHF/8N+bnI0Lb86JJO+rcP6hVutsGBTA2anUpshUCvn wnAZLIS6hwcjmRAKbnMh9HjjJOycKyiBuWcOJUcDY5Sq09zc2oOXL8C4jWpN3m+0D7/D Wncg== 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=cTMY/OOzXxzVT0wKhNB/vG/+K3Ra9N4WG+tzXW2bOcU77sElbPETC5wo3BZqRGEZJl qWMgfO5zv/ViXRxDPL28pkOhHXwuAKhw6HEPAcuEWsdAuefapvt2pwgezOh1RV89ZTYA hJA/9vlAmY2doXA2FESmCblO4s9aZjWqrAcOxUTX56CW1MK3yzQc17g8eAlVth8Vap+R t+iq+ki2NdExiF4mhMHw0lE1vpLDQzVJkBU1Pb7BMDxy74/7Pk9HCPaOwCoh/vYWHhwy kG0v2LPc8qCIKad6lMLGuo+duZn/Y4li/6JxvOlFmzp4jG5+NcIFhWKC5T4hp7AK+mVl KusA== X-Gm-Message-State: AOJu0Yx8azqyFcFVq8fqslF+b723ywQgh2D9dx9zwHdASFI+Z2GKKiWN FlEkJdkLq6cbplE7tXe8QmoZgA== 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-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lipwig.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (lipwig.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:58:42 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1777998638559803037 X-GMAIL-MSGID: 1777998638559803037 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: 144192 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp964030vqu; Sun, 24 Sep 2023 20:59:14 -0700 (PDT) X-Google-Smtp-Source: AGHT+IF1Q139GdgsDEzjKbJqrUyi8ojWSgC0s47DMUgQM9vhBf9TQ1KHA24b8cJE5+4jrXQIV2z4 X-Received: by 2002:a05:620a:1a87:b0:76f:f64:58bf with SMTP id bl7-20020a05620a1a8700b0076f0f6458bfmr7175906qkb.18.1695614354595; Sun, 24 Sep 2023 20:59:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695614354; cv=none; d=google.com; s=arc-20160816; b=GP+IhYycoItYSIGwlkcqrMX0miTfRlRBZRr4LiHHoTkQ6A+qgPc8vxmt15ijQate4n eoTMMqldxS/3LMnnFQJL3yGFCYXtSyvkEBmw4JnGurj+FJWDCfCK1hgEZPy6RJwIZrFl cBvPqPAOwiWVnevgxQOYMyeAf4S2yHr89I8lToxBSLmtKcqqZWlfk6F2L3vuY/c+hJyg 7DaC3dMS2FfYKnWu+Njnj9r9cons/WVoGzI2Pxwpil7IgePcvUJDCFANThc/zNY0LQpE u1Yaaxim5TypSRuuQ/x9Jjh8LpUaN58pG3z5QKMrnG3VaoBhTIF2WidYtoFQdzcJBSfm Zszg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=hww7oOWxGKb7qmsb0mmM2P/enCFKvkDkB3bMeqs1n3g=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=nodiPz66jqCzd9tRdL/GN2DrP4W2s0AwSCihgB9IXfnOXWgr0Ek3JeqEIcKZ3LTiww QG+3m7PcENrIabcKMuUjxIWhXbyMwEPfQr5vOKbmyUrYpmDFjxbZaKwU3Xdh+JIylXww +3Vsi0dvf59dPWWJiv5AVBdxhHxH6egfzKyCc205ud3x1jPJ8PwYX4fhSPalhds7PC21 Dv9S3GM0wUBA305zRcknJ2OE27KP3Fj298x0EPJqoQ+3xCDLOxh5AlkudUInG2M7Oerl sdHG/fk0pZ32gudb/B2GPZ+iAxhxwdTqfGOZSEUMlguMGSBe8WotDvPSckHR3Y6tkjDT Db/w== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=RRArD+lq; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from morse.vger.email (morse.vger.email. [2620:137:e000::3:1]) by mx.google.com with ESMTPS id ea25-20020a056a004c1900b00690ba709d02si9046891pfb.381.2023.09.24.20.59.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 24 Sep 2023 20:59:14 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 as permitted sender) client-ip=2620:137:e000::3:1; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=RRArD+lq; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by morse.vger.email (Postfix) with ESMTP id B5E16801CEEA; Sun, 24 Sep 2023 20:59:10 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at morse.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232040AbjIYD7H (ORCPT + 30 others); Sun, 24 Sep 2023 23:59:07 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39822 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231820AbjIYD6q (ORCPT ); Sun, 24 Sep 2023 23:58:46 -0400 Received: from mail-qk1-x72f.google.com (mail-qk1-x72f.google.com [IPv6:2607:f8b0:4864:20::72f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3FE10196 for ; Sun, 24 Sep 2023 20:58:20 -0700 (PDT) Received: by mail-qk1-x72f.google.com with SMTP id af79cd13be357-7742da399a2so112891685a.0 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=vger.kernel.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=RRArD+lq7BAqvn+uNyaKKRU/d7BtdrC2ePuy6kCotmdPQirRoJkgG7oR+E9Y3wf2J/ oRPJK3BsKoN6SBn/k45+yWcoqfLgeM9NU906qIli0i5PvUp4pdzWjG7Gv5cSXLoKpGa+ UxOYVavUcrag2xB434jAOsZz/js39Xk/6dBWE0SkBylMjMsAYChYR8XbZEdxCG56MXn4 1+Ne3+C6M10pZCMmDdK5NMIizrHXkAMICm7EJjfMmTjci4vUVRRic9nasg1MKIin7hK4 N/GngCG870M5cItWkLwyuB3yFcowXnr0+evOV3w0Q4sJd9NWfGfqDF0tiuxsnUyGDQdd B0Pw== 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=nZAHp01xE3ac/v94wPdJhKovawkQiMroPLyvPL3r1LC7AT5wENT6bjPpYI34ycpyOt ZgbKiPpNh94Sr00Pl0lOhbq5oK/7FvpO5IwfNVZSaeuRuBbpmTy/thbVzM9myrhRZ/VE KlIrZ0V2aunaiTpYxEHSFAZ2ne2zfXdeeb2k7QOKN3nZ5ZLcbRY1kRWjwupz3DlxqxqT LtMj5nTOpZwZesjGftzdI2pMhMC4CUhs/KdkBXMrIIm2uTLK2KCWNPuwL/bJfNEkuswh 6POsiOuPyb4l2VvEzXdHyZXP6Gyjihjl88mUik41cXwKoS73y0wsUyvWIMzSe51NMKso DvvA== X-Gm-Message-State: AOJu0YyyVEn2TXTlDOwzyRTNwiYb/Nio65vqjDt7eG3UR7/40lQR//lw PMrlYIrCoN036l6hGO0g6bxeFw== 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-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on morse.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (morse.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:59:10 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1777980517717579869 X-GMAIL-MSGID: 1777980517717579869 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: 144506 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp1367296vqu; Mon, 25 Sep 2023 10:21:08 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEry4GdCXyAspgWKxkjIFs3URe3yndZby57ChetIR42tk1rRSCej3K6cIDHl782h6+PIeFH X-Received: by 2002:a17:903:41c3:b0:1c5:70d3:f193 with SMTP id u3-20020a17090341c300b001c570d3f193mr5919661ple.10.1695662468466; Mon, 25 Sep 2023 10:21:08 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695662468; cv=none; d=google.com; s=arc-20160816; b=PYmYpTdMseCi34SrUw8lGvGsQFq0+wGzWRPLd6FEziE1BFT5tA4saa2VDZUJgCJg1Y hy100lChiOGG+gu/ZkNGmRho+/KiMZSrguW9IKwgYW5RgFWi95YOtTqYZ6EjQLaFH8yw CBbf2QTy2OVajO+twY8yv5mNud24yUatQuu4nN9HSb9XmfCM6uPtQB9kQgRdTD80TjNX ITOQ/6es9KhV6ORkeKAQTP6HBM3SL78+/UNxv2n/5W5juyKyfLbqRcZ9El+dJGpGXYcN s6Ao7tILrobMInWhZ4H4kYpuAoZqBe7nl0dtrq/h8RJz8aZ0dkg3DO7+dgWzssumvdir og3w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=D4LS/TFttl0uhdXEX5m8lwn2u6CezP5DBiTdl/qFdZ8=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=ckMnwAYxkwoYqI1R9Bb8LSpwBcHu/scGCAjZtBwdnFozsNNpDrXPCJjtcCjxYwgrBA +HUjeAGxNrIOQDkfydxBFAGWQ08hQh+pjTxDOzhMpyMiZ/sFvziJA7K0CL8HdWnhwadU +8gmgFUY/F0vW/Rsq/vYnGAfyYxYn4yg8PZlGQXsC/PaMGHFLkm5Er9omwfrrx4MEIgd LZrJnsVNF17OkMc+YyG0TZuB7zsrWSvPlBgaWhIISj4R0yhKjd/wgdqzVs77ds8Hcemz Za7bqZpiNse15eZxd1m/1iLjVDnR3VFSrlAnLYTVJ4pCCLSUKOhwUy7VJV/0i8+0mud8 ataA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=RbkY5du3; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from howler.vger.email (howler.vger.email. [23.128.96.34]) by mx.google.com with ESMTPS id u15-20020a170902714f00b001b8ae9058d3si8454532plm.516.2023.09.25.10.21.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Sep 2023 10:21:08 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) client-ip=23.128.96.34; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=RbkY5du3; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by howler.vger.email (Postfix) with ESMTP id A65AA828F497; Sun, 24 Sep 2023 20:59:10 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at howler.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231835AbjIYD64 (ORCPT + 30 others); Sun, 24 Sep 2023 23:58:56 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:46988 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231797AbjIYD6o (ORCPT ); Sun, 24 Sep 2023 23:58:44 -0400 Received: from mail-qk1-x736.google.com (mail-qk1-x736.google.com [IPv6:2607:f8b0:4864:20::736]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 12F891A7 for ; Sun, 24 Sep 2023 20:58:27 -0700 (PDT) Received: by mail-qk1-x736.google.com with SMTP id af79cd13be357-7742be66bd3so135378885a.3 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=vger.kernel.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=RbkY5du3e8f5L6fTOBHDl/rIqGkpPP2l8STPrbSNtDdnszFsq7XS55GmpE6aCoMb4m /PAe0Jbt3rNynoYGefUf2h19aaaZTUJwD/YIna/14Z9XrI7Nnl7sBv8jFqwEUYcHpxZJ 7Ffg+9ZR/0bvoJ0/5Pqq1tmQVH2kpkSoO6pAMcTq7v/ih+UDoCbCXwaaTgapd2YWd7o/ poPLVdgDxazK6cCWC5Lvwu2hgFJBw7t8K887WboLqR7GHztnXMvodHaOTTy4RgrLKfyc p23QohmyTgDEMuGOrl/OV5CZIEcwLBH26RguVZ378W7KUuMpiPb1XNJMhW3AGFu0DVKf vcAg== 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=E1LUnuRQ9ui2lq1jbRm0hLS3qWM/+Q1AmaSQ6ESEwFiofm4C7ez9dyFqiAkbgbKZnK E9HLwjbzxNHKW3EwX2/K4DTORAsUpOrSJS2g3ajy+lK8g/wN+j/+d1TzAl95SYrYK1qA gqD60S0HzZIOaQN9Gnq95Lgd8Pwrxh7bdxQOYzvz97y9l5UJl1MxN7osW20/F2ZdZJFB EkA77Fku04neADgZVYKu+b4EV7clMtnZykgKzGYkWVAgizWRHFSUpp/wUtCMIXL9rPoz YLUBnsxv9qa2tYcGJvl1yf5X9YDv4rHWC8da8QbJJqxWws42obbwEWC3pK4fUmcAtabt pJyQ== X-Gm-Message-State: AOJu0Yzw4QuKGWaJnenrZFEeX2qt7wAlM1gyT+TeEZWX36YBC+QB1cWC ZrAj2cZqSZHYVE9ZQCARV5TqdQ== 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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_NONE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:59:10 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1778030968159707073 X-GMAIL-MSGID: 1778030968159707073 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: 144208 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp993509vqu; Sun, 24 Sep 2023 22:34:27 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGpvveBAMlXyA9H7VOM1izinQ2fd9Y7fbzbu8x/UV7mzubQF7JYjh0H052Rk8AIepvh24AV X-Received: by 2002:a17:90a:dac4:b0:268:1354:7b03 with SMTP id g4-20020a17090adac400b0026813547b03mr5351667pjx.12.1695620067209; Sun, 24 Sep 2023 22:34:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695620067; cv=none; d=google.com; s=arc-20160816; b=AJl0ifN5igy2CRQCOLRi/Ufl/mJF8ApK5+4urli5gS5I614ekElENyTxgEdwIP0xFx msUR5coc3PtgWtttEI8gFlbEd79/83dKen8gI/cq+QzvUCHmgcTW42UD/wtgQQViLRgV e/LH7S00axWXVyLy1eOTNlGYDfZ0AOupioU3M7iJpedqdyxSSQIEYmZBpux+c7POyIF3 Fx8j4ZZwwHJziWnvU8RtVAfhb8m6ZYpa6zHldAC/0xYnuSbHbxwuktrgi+EC6qsPzzCp hwHYEZAr8SLI0PSzbVPGhvLOpfJxVve3axj/WMqHubiGH6a4J49+w3hYULM46qntVaLe vKPA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=WdG6oUlthPIzD1rC2JhHIaoZzeLYPv1w9Sr7ZAA5CbQ=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=QiNcg6aX8e9+6WQ//V8KgRotfGhZzcxvUjziGIEjwMXvKthNymDT9iMTMM0imWUS91 jpqegXeBBQhxQkjhmgAjjNHQWUN+2hnalOOhI+irOwuaooZFFkU6iLBEO4aEJx/IRNMm 8B3OAeaQonxDeCDf5DyN6dq2O/E9z4/v1F2WhOF11wmSLxTo7JVsxPnLImJEcTr7jSub BLZvc4J6FsZK09pTOPhnMmdLdFHslC0yA678Dmj7MBhoTKCEzZyqDe65WkxDjI02oHtf knOIbpGAIbp98Z7PN4atQ2J1Sf0DsEtwON+Wfh5U3MtTrZG08qNzAJEuFlkyvnf8TlXP PKTQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=LlVLwZHD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from howler.vger.email (howler.vger.email. [2620:137:e000::3:4]) by mx.google.com with ESMTPS id mp12-20020a17090b190c00b0027686905e79si9260644pjb.146.2023.09.24.22.34.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 24 Sep 2023 22:34:27 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) client-ip=2620:137:e000::3:4; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=LlVLwZHD; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by howler.vger.email (Postfix) with ESMTP id 696F4828F4EF; Sun, 24 Sep 2023 20:59:13 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at howler.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231800AbjIYD7K (ORCPT + 30 others); Sun, 24 Sep 2023 23:59:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47104 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231916AbjIYD6q (ORCPT ); Sun, 24 Sep 2023 23:58:46 -0400 Received: from mail-oi1-x229.google.com (mail-oi1-x229.google.com [IPv6:2607:f8b0:4864:20::229]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D2E6ECD1 for ; Sun, 24 Sep 2023 20:58:34 -0700 (PDT) Received: by mail-oi1-x229.google.com with SMTP id 5614622812f47-3a76d882052so3685966b6e.0 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=vger.kernel.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=LlVLwZHDoqwPOjeARJF8Qy6YzqVf5S1F9wYejmpyJOh0i4Ty+8HWLrpj19OYtBBjhR 6/6Zi61zITjAVOGWwwnwoOHVrw5DZ0Trui88wM17rdfGUMDAe11T/La0Kcu4SGTBuSuW 6Qszwv51Oe9dx+/kDkBCrWjC9Z0JBEpMDj5gszNZsjI1aPObTG+c2ApzJQM+Y3EbXjO4 sV2XrQA5JQyeZVcednY9aJsTPZr0ExWQeiJVqYxERPpcjBXO1V8lLQ9lclvU+EDRrhrW 8UtJk5NmN54NoAcFjJmlFOCwKmVm1HbKNDhvtovHXeT3O94Z03hESQgQkzqXxsqFSz3W wD8A== 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=XCNwaYWgaPAVWwRNeIwXjTyhwC8bMdpM8XzSwx0l3MhoqTgeEVOFIsgLx/uzug/skR GO1J6y6oKBLqz5MBhtVShP2AZaPsdhktqjlmcYEw+lkI8m3WXuagjl4XKo0TuPAKh7Mt noBysmnobmjgM68XLHQK/ajvGlT+GTV3JOFOIAUlnoLq3hXnMJXVANRgKpO3b6yg1O1J fUz5xxr78Ep7W0P4IM5KXqNDPgiTVVdLVJcuKpgNovpPU8qePYrpULtn0MJvoHgXh9xd qJsrarpVyiKW6d0s7IoS71mgTiRu67I4yqJCJFHmSI9ukEYUentkz/b1Pgbu7yEbHKUC IShQ== X-Gm-Message-State: AOJu0Yx7l0+iGCBtOxXwCGY9t/vy9bo2LsQM8TLcBZrxfjNivaskpbrk gnYrQoPCzK/6Q2YqL0fi2Eklow== 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-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_BLOCKED, SPF_HELO_NONE,SPF_NONE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (howler.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:59:13 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1777986507308996795 X-GMAIL-MSGID: 1777986507308996795 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: 144387 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp1136196vqu; Mon, 25 Sep 2023 04:25:39 -0700 (PDT) X-Google-Smtp-Source: AGHT+IEvV8oU99MxGcGC3qBn0Hmltv3DV9p/iHG506L/nSRwbBuD+85bweZJqyWGHuprsBk5HTs5 X-Received: by 2002:a05:6808:1395:b0:3ab:859c:7c6c with SMTP id c21-20020a056808139500b003ab859c7c6cmr7962275oiw.37.1695641138805; Mon, 25 Sep 2023 04:25:38 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695641138; cv=none; d=google.com; s=arc-20160816; b=ep50ESaZ+2BePdqW0h6ZpGvUlLh6ulZziNM14me5cYpw2TCukJP7RMJEwta+aQm8S+ ihwgrGj7H3PVGqlZQO+GuRQyUAgMpkrGrqyabyd2wqKb1nPrsu14E+nAB7WcyP1ROiZ1 6RIBa/UyBqri2N5hq0NlaM33VwQo8VJ/hELrQJgyD7O3E8VByZerQxjrTNd0i3+lM9No Igy8RJ3Q717sQ9QsB27QnGgLJMo57MJuTEyDMMi1ryO4F8m12ZR0zYyiV0wqIuGiPLm+ eEkKTXF+tgse41a20ZWm9xYguhNRM61u0o0P4acN5DjAkvbbtX5rgivf1v91blpxb+rV I1kw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=mGF6lWn34y725CVIBLiDuCLlZ/D9mfCg2VPUJce9YQs=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=Q0Kp1PQkr9QU3GjE1Ac1/RaxLgSnnvpnz3DfUmRlrNwnyySowXKDRXKKGC7YlLYPgC szoeLZEWCWoycFm59PZrBhoQryY+ai3m4DeWwCDm4xyTg984W9pKbrOYco8WyaU2B3o5 6YBjWXz01FL0xgLzybDqLuSPskzi94IBtentP8QLJ0gD52a7Utc//HG74RX+F0jhlIhZ gZSouTthCopLLlHIdaX3WZ8sjiOZuP/FSUxC3xJfd6f8WqfEGVXuGv7U4xgrGTD+P68l CKBx8sapFfR4Q3lzfIgZBWDqJOFZYe7MqZNLhQgm0KaRLEUKD3PRDF7eW9uObk+KSym3 aAcw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b="M/v/vjTr"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from morse.vger.email (morse.vger.email. [2620:137:e000::3:1]) by mx.google.com with ESMTPS id e26-20020a63545a000000b0057828b85ae6si9751167pgm.281.2023.09.25.04.25.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 25 Sep 2023 04:25:38 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 as permitted sender) client-ip=2620:137:e000::3:1; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b="M/v/vjTr"; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:1 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by morse.vger.email (Postfix) with ESMTP id D3812801CEE0; Sun, 24 Sep 2023 20:59:57 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at morse.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231977AbjIYD7v (ORCPT + 30 others); Sun, 24 Sep 2023 23:59:51 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37008 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231799AbjIYD7Y (ORCPT ); Sun, 24 Sep 2023 23:59:24 -0400 Received: from mail-pf1-x435.google.com (mail-pf1-x435.google.com [IPv6:2607:f8b0:4864:20::435]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F221210D for ; Sun, 24 Sep 2023 20:58:41 -0700 (PDT) Received: by mail-pf1-x435.google.com with SMTP id d2e1a72fcca58-690d8fb3b7eso4946932b3a.1 for ; Sun, 24 Sep 2023 20:58:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1695614321; x=1696219121; darn=vger.kernel.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=M/v/vjTrVyE+W85fdWa0awcxSStSWeglGcdH015ydpFVQEh4YokywwsZPSRplczS6s kZrsuIanxSb1vmhLk6aIFRWc0+NvuYshY7BLiPJ94xHxcm3SHiXR3l84vbUT4jIZgiDz kiFYJaP7UcFP5Hf1iseif2xwPz/9hB2j1+oUZX/0QXBQ+3sg0hfwvCMfbchrypuKa9SE 4Wj+MqmJxuQ5ikjNi4bDoNTaQjDXP5XlfJkPbzdQqhekugZIUBtJiph/PiiJsfgmUN3i XwN4nTIiDSETUudLS69n9v+6jRBMk35f3BRE2sdh/mxcKX7b2P4Ef+LDBEbcNoSVjviz difg== 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=MT3BfMUdQNrefQCaze+9dY7Sa5mmdzINRyorduTuGMZQo97cmT5dTS7vHI2Er5BisZ kIuO6NsTNOGbgWa6geCf+MgDg2tWfh8TQDJndURFNOrHNZ2BZ2Sk8L61l20VV28092Ku 4kPZgYlnWjbMEdLo/q03rzqrRyD/QHTa2hEVDdLeAQVObbByxTlulKiETBJXFnQFgqQk x2leH9+QZC42rF8Uxljsm2z7HDPiTXfX0TgXe4lNvXn32BcEz0AHqJkvbryreSefjBee yYvaXwogH/NdztalODHKvL4fPCofQ5ig+IwwmHOtRSgpXQoAK6xeXKavSl5IE91Mhz7i Gz6w== X-Gm-Message-State: AOJu0Yy0pBi35pMCNAIcLrxbTkW69ez3i1Bd7IPK8tGQ28aqYwTzY6rr HKDTC34EtzsCKXuDMLSpwPFoOQ== 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-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on morse.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (morse.vger.email [0.0.0.0]); Sun, 24 Sep 2023 20:59:57 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1778008602840966734 X-GMAIL-MSGID: 1778008602840966734 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: 144229 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:cae8:0:b0:403:3b70:6f57 with SMTP id r8csp1013497vqu; Sun, 24 Sep 2023 23:32:21 -0700 (PDT) X-Google-Smtp-Source: AGHT+IENbJrwVpDKFLOwim4NHjSgdpI+m59Vnfsz5BDcbnC0jYTdBq/Sehb4qj8P6qUwb3ss+7e+ X-Received: by 2002:a17:90b:180f:b0:26f:392f:f901 with SMTP id lw15-20020a17090b180f00b0026f392ff901mr8904756pjb.14.1695623540640; Sun, 24 Sep 2023 23:32:20 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1695623540; cv=none; d=google.com; s=arc-20160816; b=CmwZQO+CpupQV9PboWa/ex4Vvkdp/ZCvsIDJtInBT7wsZH0s0Iy0gj0qUc3iMFD7Ut lZe0zOSWKaI4VvFVhUOwXIyMlv7h5vYlz3+kMnZryhpIGp7g/C4jWC0zUTYjNJZ6FyJ5 RqlprOaIAlwAzzjVu7+BvJ6s/Gu9puWWjKNLQnj+CVXr2l3bnIyqpAX0yxMEh6lozGyq AdvSAPIL07AtQm7UEDM3sLel/9mf+jBaZ3lQea+sZzhJjF15s/7ZgRsmZ4SjRr0GiG8n 9bLEzIobZbn9P+Z+FAvT8BmHqJ5Q3PWlgiyV54nztQZiudu+RlSM3ZtNWoES9odZpHgR ugAA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=TuxzCiUZ2DltVBwaDerHzUDGuv+dY7UUUi86i/t9rYc=; fh=uq6KVc+CzZ80ucpwrp8f3d+Fe7Ue0w5J0Au2lk064nU=; b=AY0NUzDoe7YZRc9Ap2jd4YL+gLZKgdVnCv6wJfdy2nxvMW/xUE4jIJRiX5YR7Gff4v 3bq9F2n0MuxDbQiBV/cncYBysmwZUvuf4xO1WgeUBAA9Cl9HcDQYe++CS7z/L/Z7yz92 xdgFfP2LUUwkkAtckBcE3fjXpYlfiguee3DA1QCnDmuo0Ux7pOvNSjdOULf0ckU9acGF +Vq84o0D39g8wNh6gVgKjAtfd3dMan/F5ISZINWKM2N98PgF0jC9oPze+NOG2n1wWcbE wjwMsMKo390OiuN+swhiDXJCLWSOjsCQKDtupKwYJ66V8jcg3AVDzAoIV0F47+aH6uDs u+cA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=LoUYQ7SU; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from groat.vger.email (groat.vger.email. [23.128.96.35]) by mx.google.com with ESMTPS id w11-20020a17090aea0b00b002774f38c8f6si2285522pjy.29.2023.09.24.23.32.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 24 Sep 2023 23:32:20 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) client-ip=23.128.96.35; Authentication-Results: mx.google.com; dkim=pass header.i=@bytedance.com header.s=google header.b=LoUYQ7SU; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.35 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=bytedance.com Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by groat.vger.email (Postfix) with ESMTP id 113FE80CFD5D; Sun, 24 Sep 2023 21:00:09 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at groat.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232060AbjIYD7z (ORCPT + 30 others); Sun, 24 Sep 2023 23:59:55 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34576 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231874AbjIYD7Z (ORCPT ); Sun, 24 Sep 2023 23:59:25 -0400 Received: from mail-pf1-x434.google.com (mail-pf1-x434.google.com [IPv6:2607:f8b0:4864:20::434]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 55114CF5 for ; Sun, 24 Sep 2023 20:58:49 -0700 (PDT) Received: by mail-pf1-x434.google.com with SMTP id d2e1a72fcca58-68fdcc37827so4757515b3a.0 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=vger.kernel.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=LoUYQ7SUJa5qtkdfo5OKFD8pcWi+jh2Zuw7XbbU7mTJci+zvHt/nEep1nMXyFsuEpJ brpx+K7N14v4f7k4fMqEB+u42rcGdiMRfUf/l7p9jp2Pq+etUAxeTLjP20C0vEWGhKyJ kSBZcAphexmKzUtMJRqk138sW1Sr9Nun7XuHgbZN4zPBPLP+mb4KVhs02ceM/1I2SCR1 nIlG5BdzoW8s7s9f4ojeSNVQMe+jYUdHyaOUO2XwMmDvRv51gvuizbZZ/SPqAsjsmdPV 7po03mPpTsMvQWxCIej1rcV1Fkvu943ciSoAn9JODnuDJ5tffx7xEzOpZhq9DUwRCNLD uSJw== 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=hfuLuVGmnRzfk5YRuhRJTrNh4YLIHyh0y8J2PSnM2n0xS8d3N7b3X/hLadS1bm2PyQ 5zpkS1U06X2tfWcYJcXe2mm83HCkxN+UmT63PDVpzYShMCKDsZge17YeWTFtqNy1XLnR GQYf9KId0aiEStSCY74cntmgT2t2bwRd2WAyzfXRBhkkjNTU4EotmBMZcM9qEELhcsQO v8w4aXicVc/f/d5timF+1qphG+0oclGuRWC4lfXhrD7df2urIJWD+Z4VB4UwQXJnfzao rmDTofub01RckuWctXHpD3QlY7Pgz8pApQPr8q0QCnojIYiLqYpFpvVoTPRnIerI0DZo NXyg== X-Gm-Message-State: AOJu0YylmdfcHZdcV6YRFwIJNjS1zKY85RcGWTDjyGCzf7v1q0lUjd6q rCd8F0O1om/u4/LnjgJfu+7eMQ== 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-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on groat.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (groat.vger.email [0.0.0.0]); Sun, 24 Sep 2023 21:00:09 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1777990149505454921 X-GMAIL-MSGID: 1777990149505454921 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); /*