From patchwork Wed Aug 30 12:56:49 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13370228 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 73A6BC6FA8F for ; Wed, 30 Aug 2023 12:57:29 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F241E44014C; Wed, 30 Aug 2023 08:57:28 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id ED4B2440009; Wed, 30 Aug 2023 08:57:28 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D754744014C; Wed, 30 Aug 2023 08:57:28 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0016.hostedemail.com [216.40.44.16]) by kanga.kvack.org (Postfix) with ESMTP id C73CD440009 for ; Wed, 30 Aug 2023 08:57:28 -0400 (EDT) Received: from smtpin13.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 900CE40172 for ; Wed, 30 Aug 2023 12:57:28 +0000 (UTC) X-FDA: 81180772176.13.A636ECB Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) by imf15.hostedemail.com (Postfix) with ESMTP id AFF17A0020 for ; Wed, 30 Aug 2023 12:57:26 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=UYKHqVgE; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1693400246; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=MP6g95MTpMxGO+X1eOP4Lih7hj+Gz/gWGNfVacVPrOc=; b=HAT1d1yNMjSXqkeikmceGbxWUtakt+sW9z83+0Yy9k96Xhdt+VQgRiPgD9wIqQkwR4ei4o I4hEQUoryspYaeCQM50PsA/cFkNbZBQaxzXYFkJjfnASkSjnKmqI5ZmWeFm3GiyV6Vh3Cs 8s56h/KS+L2k7CFugSVeOtERIe7VsxQ= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400246; a=rsa-sha256; cv=none; b=x/CfJ8//O1bpBE0oGnV47wKVL4F4w4nYfihdebEUkQRsZt3/3zI+cWPaxO23qHW9rgx2GW ChVq5g1Tf8dXwMWkv87oMcQyLVsG39BVZatsBvM2x1imPz/Gl+FGkEfYSTLNJ2qTaiZcqk IsTxvXInpsm8kPP2LFSP9wRTp+W8aJw= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=UYKHqVgE; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pl1-f171.google.com with SMTP id d9443c01a7336-1c0d5b16aacso33504165ad.1 for ; Wed, 30 Aug 2023 05:57:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400245; x=1694005045; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=MP6g95MTpMxGO+X1eOP4Lih7hj+Gz/gWGNfVacVPrOc=; b=UYKHqVgEKV4sBpHSk2Vpf8sz3jfOaLPtBIotgvn/0Sdcz+jjeH8f+JXlrgS6uM/PLq FArwOEpYbk4tIhywHKP/2LERC+NldlY25gdoUdhY3VS1aGcoZrDybwJGOhq/pTiqRG5F 8DiR+ItFk5xqTTNzxMMTYf1A2UziPn5YtmSqvJ/MN9ry7cIIiKHK3JhjQT58FnBxiC3x 9XBhe1m14oxw7/gtpdGI6ZeXQYrnFu4a9EG2Mu646OnNm+srDaIaDcdy4UB8Sgw2AYz9 cjik5yasieUqw3WJtUOCd4Nra6m4uOCRsrcGvqOEEyXtrr1GcpOkMn6K1bYDmNp2UM6L MVkw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400245; x=1694005045; 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=MP6g95MTpMxGO+X1eOP4Lih7hj+Gz/gWGNfVacVPrOc=; b=POfdqI54jIkF93vfJEXjtSmwlMuzPkEe1cl+KBOWfrOGPt7v1pupTyti9Ot1MhuFfq GsgwKDMkShfATcP9N2b5ir9RoE4s+eKJfoRvC4dfPG2yYll0PSy3o/6cdEqYIuiArfEx NsZem//mCFAuI4c4Ku6oZjQ6Tb0hfMB2XAeRHRDiuDzF6o/nxJqO7fNFZ+tl8XCRs6Xw RVgwRldQ71/Xlw37pN//GgjySQABkZnJPWMBpCXKNn5DCTciv2tPCZ01jAuDaHBn3sOq IEIvyjZPokVazgOipEFTpN+aeKZ/JOZagWQI6V5LTBqT1qKE/2DqB75FK54ykxpv6bma nOzA== X-Gm-Message-State: AOJu0YwkOYzsk0EgJJQ4SuZhS/NKdL8yT6dqrEMFGJYmAQdBlt7P7/nU q3S4N6PHCYwUwFg5t90SgT+tCQ== X-Google-Smtp-Source: AGHT+IE0rSvilLu9O36gttI/TkP4I00cCFIGMgIKwGw6O7fql+LFdULSrt81PWAZjYw7XwKOPHgFQA== X-Received: by 2002:a17:903:487:b0:1bd:ccee:8f26 with SMTP id jj7-20020a170903048700b001bdccee8f26mr1802973plb.15.1693400245360; Wed, 30 Aug 2023 05:57:25 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.19 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:25 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 1/6] maple_tree: Add two helpers Date: Wed, 30 Aug 2023 20:56:49 +0800 Message-Id: <20230830125654.21257-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: AFF17A0020 X-Rspam-User: X-Rspamd-Server: rspam11 X-Stat-Signature: xc6p1sq85mbgrtpgh84yu1f9xd6d75ye X-HE-Tag: 1693400246-159847 X-HE-Meta: U2FsdGVkX18Ysy0v8BJrqaXHi1/vJeRA7IEPa5U9qh1JRYEJzTsbPZNsPAMokwdcY1t0fycxSWd8cqbMsw88jag7wEwHbNYQR4aevxxgeraY701RyMw0sEiOlEChYb9sJ7ORC0BrA3pOB4CcadPxT0Vd7bqpSrIc2zcxva6MU7DOMA8mqIOTwQkWQEwNU09o05Il0vmpkTzXQivya+KZ9QjxyAWW2Sb5Kf8mg7/OQUJ6jy90bL6axXZLq8W+pqdSVhhHUdrGdxGdKctCFxVYUyU5q8ucLjyyYuKQXM9Nn9/wxHm8joruzsD9cSZ5oudtR4uHdwSZh0W6oLYsFdVZNR8L1CejjlHkCUS7PWGfaIsfwr9SswJMdBg4UzeBtQfzyIty6lqFvDYJ65Bm03VSZNa8fEa7k+A2ZWqWbJy0UWfErZ9X/GmU3MLcqK1cHbmo7IkvJb/x6ZhpxNQ1TtKOVt2qnOzA41/7RFp4wq0xHqzfOnfHHMahvF86yansdRbKGgxMLYDpjAAqYGzNNeUMdQQDuPpQnwXLhbTGfvrvqhKA+VvtGSHQ9dELqObzXn2AxeUPvkKfZwcH9ASpbSBcTt9ms9SqoDT9D1m2Fqvab3jISrYiNpw/dswpaIT+06P5lc5D7ok4akQe1MdCzZCQS9UaNaf1bJDMHiz3AfUpbV2UR/vOHa8r84JyAzBr9iDupR1w9b4uS3LQOtI9ecQfMVAksyRABofnOUL8jiSjwQy/NdzHy0q109Y1JT0MzSvoq9mcMCd7nNyu+Dn9KPfdBC+jAZmMkICYVy+MD1dyJ+JQ4c7c2+FLgowrEFJ9TqPnatjlqRWwGULdIfkT3snwCUXEXKaR7B2GGxZ6oN+u+cOXHC+gVvJA4i2ub/j0ykdFQGUEb42S0VGdmTxq/xP3RwB9y5JGxaNlL9edmA6y0z3veAK6ShwuZWV+iy1siW5ZK3b037WU/p1Nq1SCd+1 o9tQS2H/ IijiOOdpsPvkQXiVsMp5klxbSBTAAYRZEYwjiOjLTRHsGpQx8RqVRL38xtGyQLKSNnWfGZdzhNu4BRUNMsSj2NmPhMzOC88TgF2dGbvBmTIqCGF5B3vGM/a05MRa4FONQ6C2+Q3x3CZll7LCqNkZVbWY1sjX+n7pxOfJk25DlGXpqdB6Xgk521aK3zQbYj4icV9jDqjveKmlPgC9u2LKcRwevOr2eygf4Gw8MqQoW/TwLwh+PzenyH281bqRZToCKVifLXnLLk/SwJfhrrkn0bAZ4I0waW1j0O7wHql6TZSfgtcm0ecml1imYZC5xrh4HsywY8JmMs1NyUijN2RRuxc7MEgcKN055lWAJeHSuzJ2QabdqfuI7Ni+CC85sZwVdefUBIuupd4Z191Rc1uyIot3UX5zYU9aohKE+ZZ/MYz72GvoTFNsoCJ1S9syOOtKMPmhmZ1F3d52fhIAyvBeH22MODw== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add two helpers, which will be used later. 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 ee1ff0c59fd7..ef234cf02e3e 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 Wed Aug 30 12:56:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13370229 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2B4A9C6FA8F for ; Wed, 30 Aug 2023 12:57:36 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AB68E44014D; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A6798440009; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 908AD44014D; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id 7CBDC440009 for ; Wed, 30 Aug 2023 08:57:35 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 5505B1A019C for ; Wed, 30 Aug 2023 12:57:35 +0000 (UTC) X-FDA: 81180772470.24.82EB404 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) by imf08.hostedemail.com (Postfix) with ESMTP id 7BBBE16000A for ; Wed, 30 Aug 2023 12:57:33 +0000 (UTC) Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AjHTsoVl; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1693400253; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=wkxl/SiilOD2E8l96oDEorbeTyBu3XhFltMGMQpoxTJMicZL4IOuCXFjG6aks+Mb7nEkPs z6pSp7UIQjm7CoO6UXr06puUP0GRGceNJRKYw7bHUnSOQFYauBEdGIrVGVhK0bdKBxeICf tKnwvbCsOYxOhiBQqXci0soGgmaGHMw= ARC-Authentication-Results: i=1; imf08.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AjHTsoVl; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf08.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400253; a=rsa-sha256; cv=none; b=oGBq0HpnbTrm4NoRSokCoZafkONvBtJlDRuDuNNxSgqDioANEPhXh3yR7FkzZru+33Xvpx zdtrQUL9xUA1N/4gOKLBOKEZcGvDouPDvvP2FUAFststokGn5+gpkAPXuWxoCi4Fb5PIyN gIlO9E8h8aiY9m/dN8d16rOmau8ecWg= Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1c1f7f7151fso17617885ad.1 for ; Wed, 30 Aug 2023 05:57:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400252; x=1694005052; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=AjHTsoVlLA7deCqkT93bvT9sfRVkNHMc87rl77ytbWGAV5ANZblxIksVpIYJlPv5cX 7iaVoR9InO+omG7zNny0J02TcnhgLnryHS09zW6MJho8X23XVFbGD/d+2vfyKX8kgu0k C059On8hPGz1ZfMX4O4SFUWKoQHje8C/BUfGCk8AGOniVZpycC1JeeYffATOuFrog0E7 SmGH7wCAiybTGpzknEednk8qkhU43nxNbqXX7YTuNNdqQxeUKIdU8v+cnOaRrSJKwEJk IOiW1Yfgz7F4EjhUCHyKqO6y5FYdbu0sVpwroW6IuMj4CiIgEnGoaX9MW2akrCTA9p52 6DvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400252; x=1694005052; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=d26r5h0CmoNOET0LiIs8p2rIU7MrnWiXaRawIuYer7M=; b=JDP6AGRrpX3/XJATWdPb71iixPDTPh+vEHxsor5r/6QCLiH5quFdo/SUHKXC4v8G2J ylX5OZVinDOb9OPHQuLunGuZBYC01y0lbVslhJ0735yE7BEt8AVE+Wb4V+PyFsvsieKw kpHPhwMGQKZBGDpTSYp7iOJlPjjPQLDmyjpiAdrvoDL+z3dDlDCSLVq15OWkamT+v681 7ojg6w3DNhMP/5oRHGeA+kdLzwTkskTAf5GXfwZLSXAGKFv+yqhLg9WQQNcIDsPacNJS 3SXgNcFw+S7kKrsrc7q0qru0pdA+gYnCuWvsCoUZlPWu9IHNwQJ44N3V15E9MYvntkOO pk/Q== X-Gm-Message-State: AOJu0YwBxHTWaNrVKOlou0CiR5W75hADID8X+YpCgLlhDV8gmG/mxxcC agtIu5YOE6Yqm84bt/2kv4yYWg== X-Google-Smtp-Source: AGHT+IFlsKJ4gsggMjq3Qups2gBw5dyyMz0AGXGO84i6jUNMN2vnjaDbpUxjVunPZt/9zXz+SwW1rQ== X-Received: by 2002:a17:902:edc7:b0:1bb:c5a9:6b26 with SMTP id q7-20020a170902edc700b001bbc5a96b26mr1834665plk.5.1693400252383; Wed, 30 Aug 2023 05:57:32 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.26 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:32 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 2/6] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Wed, 30 Aug 2023 20:56:50 +0800 Message-Id: <20230830125654.21257-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 7BBBE16000A X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: x9ig373wn3ipc7pdpa4a89z6xr74htii X-HE-Tag: 1693400253-341767 X-HE-Meta: U2FsdGVkX19UMUlKHUcO6otD3NIiBnJVLykKaRzmMS9fdMn+vfgKpu+Y+APufcjBtRFEo6SBuZZ8AUxQKMO+S9U3QDpKURU0Lsesh4eNluczuAZ5i2bgcGna3poYT22TWiX6eFSP2JcOEhaxbq73hA+Y1geH4A4qzpja97EvaRUz5T1yudewPF8JX/ppA+dnrLwBnBtTbO9eSlv2rcurN7aIVcW258Sq+SLvhIl9Xn3+FjKNm3QhDOioVjMohQi1Yame1M9fDqbnzcGjDKE3d7Fpzy1OQPpl7dzHk205n8WFD45GklnjM+GLt7AFV52JMCl9aIEr8nOBoktQkh48qSirMrhGU713Z4y2YVQf+F49wOwc5k5AjBChR99BiBW9gbIFgFslL5VwnZh+UJCnYL2rb0wMRdLU9gDEX3hP9M1Ri82ay0oRbDydRGGlJsL6eGAXxQ982szyCg/m44Cj3IedPZLfpi+uO2Ziba7D1uB8ZX569yTzvWGNPYm3VpChxPKQZmInWG9+d9g0nhXuIm1GWh4fycS3EdI7LxQVUF4gw3EeO6Lwe0Rg7MIkme1roIa815IhyLneeChAc+dUwkm9NLVmQjKMe5J7LleJfXk5pZiRqlGDT9x2P2TW6n9Z222MKvTpH43BHnBDnsKmDoDnCp8ZMxHQLftalxLLZx325WNh52dw9Rrq97bmcrCKfghOzFmfZNdad4e7eOymzTeZLrsLjAKlSPj5OGXZFt5GIuRlt1bgzr+2T87OFthOcGqMSUCDvKC4yExm/6FyU5iBmNAwMcuUWrt5G8Ut1a4Iz5DAJmKaVMYQB5Ov/TmxNVTcM0zEFyXsp+Up7jfcz+6tfnEtZmFkTLSDRfQx8Jov27nOTo+DCyNnZEmto7Ga0F1EmP7sseOreloxztjXTkRBUnWbDTso0mgR3/uFKn6PVHb2e9YvigOKjhUzsH5w7BTrDsLvX/bKe6ABek8 xeoGduSw pn08SmQbfJBVk3tcIZoV3JOrGMytGUySJ8c6n+iP7h/dHWWZOqpGVtcr/NLj5qshsU0PdWvBKhXu8VSg0XJaNHx+1WkUCPf32hzG6K1awbGrwnBL2/QRqdhpSflev7waM6Lu0U6ZDBFR2ClQ4LDNofDb3YLUZlBsfVMIpi0CngRyBlCYl4G3vK0NnTVObj7Topii/LZPfQpKcNdZMjXP4fSutOU5aORtVhcG9qJTG08kJ+15H+IyU5TyBnY5ZUjB8mWabAIF8r43kSwVHFFOlYngVy49mmGZEAwWz+ns6lsgY+tIYCe+KnYy2JlETngTz2CK/nzCZ2BeV8F2e5MDU8A5wUlj6pZ6n7wHqW/AtxWuGP8qEtXOq/KnLSNN/G8VUIwDD6hM3HmtdGEgKoTsB4phR5dW9B3/QbU5eVanPjGyPqSGhgsaxSdC9TZWCD/mV30X61NDyJOuxWT6IWyLS546/nA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Introduce interfaces __mt_dup() and mtree_dup(), which are used to duplicate a maple tree. Compared with traversing the source tree and reinserting entry by entry in the new tree, it has better performance. The difference between __mt_dup() and mtree_dup() is that mtree_dup() handles locks internally. Signed-off-by: Peng Zhang --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 265 +++++++++++++++++++++++++++++++++++++ 2 files changed, 268 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index e41c70ac7744..44fe8a57ecbd 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -327,6 +327,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp); void *mtree_erase(struct maple_tree *mt, unsigned long index); +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp); + void mtree_destroy(struct maple_tree *mt); void __mt_destroy(struct maple_tree *mt); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ef234cf02e3e..8f841682269c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6370,6 +6370,271 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) } EXPORT_SYMBOL(mtree_erase); +/* + * mas_dup_free() - Free a half-constructed tree. + * @mas: Points to the last node of the half-constructed tree. + * + * This function frees all nodes starting from @mas->node in the reverse order + * of mas_dup_build(). There is no need to hold the source tree lock at this + * time. + */ +static void mas_dup_free(struct ma_state *mas) +{ + struct maple_node *node; + enum maple_type type; + void __rcu **slots; + unsigned char count, i; + + /* Maybe the first node allocation failed. */ + if (!mas->node) + return; + + while (!mte_is_root(mas->node)) { + mas_ascend(mas); + + if (mas->offset) { + mas->offset--; + do { + mas_descend(mas); + mas->offset = mas_data_end(mas); + } while (!mte_is_leaf(mas->node)); + + mas_ascend(mas); + } + + node = mte_to_node(mas->node); + type = mte_node_type(mas->node); + slots = (void **)ma_slots(node, type); + count = mas_data_end(mas) + 1; + for (i = 0; i < count; i++) + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK; + + mt_free_bulk(count, slots); + } + + node = mte_to_node(mas->node); + mt_free_one(node); +} + +/* + * mas_copy_node() - Copy a maple node and allocate child nodes. + * @mas: Points to the source node. + * @new_mas: Points to the new node. + * @parent: The parent node of the new node. + * @gfp: The GFP_FLAGS to use for allocations. + * + * Copy @mas->node to @new_mas->node, set @parent to be the parent of + * @new_mas->node and allocate new child nodes for @new_mas->node. + * If memory allocation fails, @mas is set to -ENOMEM. + */ +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas, + struct maple_node *parent, gfp_t gfp) +{ + struct maple_node *node = mte_to_node(mas->node); + struct maple_node *new_node = mte_to_node(new_mas->node); + enum maple_type type; + unsigned long val; + unsigned char request, count, i; + void __rcu **slots; + void __rcu **new_slots; + + /* Copy the node completely. */ + memcpy(new_node, node, sizeof(struct maple_node)); + + /* Update the parent node pointer. */ + if (unlikely(ma_is_root(node))) + val = MA_ROOT_PARENT; + else + val = (unsigned long)node->parent & MAPLE_NODE_MASK; + + new_node->parent = ma_parent_ptr(val | (unsigned long)parent); + + if (mte_is_leaf(mas->node)) + return; + + /* Allocate memory for child nodes. */ + type = mte_node_type(mas->node); + new_slots = ma_slots(new_node, type); + request = mas_data_end(mas) + 1; + count = mt_alloc_bulk(gfp, request, new_slots); + if (unlikely(count < request)) { + if (count) + mt_free_bulk(count, new_slots); + mas_set_err(mas, -ENOMEM); + return; + } + + /* Restore node type information in slots. */ + slots = ma_slots(node, type); + for (i = 0; i < count; i++) + ((unsigned long *)new_slots)[i] |= + ((unsigned long)mt_slot_locked(mas->tree, slots, i) & + MAPLE_NODE_MASK); +} + +/* + * mas_dup_build() - Build a new maple tree from a source tree + * @mas: The maple state of source tree. + * @new_mas: The maple state of new tree. + * @gfp: The GFP_FLAGS to use for allocations. + * + * This function builds a new tree in DFS preorder. If the memory allocation + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the + * last node. mas_dup_free() will free the half-constructed tree. + * + * Note that the attributes of the two trees must be exactly the same, and the + * new tree must be empty, otherwise -EINVAL will be returned. + */ +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas, + gfp_t gfp) +{ + struct maple_node *node, *parent; + struct maple_enode *root; + enum maple_type type; + + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) || + unlikely(!mtree_empty(new_mas->tree))) { + mas_set_err(mas, -EINVAL); + return; + } + + mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) { + /* + * The attributes of the two trees must be the same before this. + * The following assignment makes them the same height. + */ + new_mas->tree->ma_flags = mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, mas->tree->ma_root); + return; + } + + node = mt_alloc_one(gfp); + if (!node) { + new_mas->node = NULL; + mas_set_err(mas, -ENOMEM); + return; + } + + type = mte_node_type(mas->node); + root = mt_mk_node(node, type); + new_mas->node = root; + new_mas->min = 0; + new_mas->max = ULONG_MAX; + parent = ma_mnode_ptr(new_mas->tree); + + while (1) { + mas_copy_node(mas, new_mas, parent, gfp); + + if (unlikely(mas_is_err(mas))) + return; + + /* Once we reach a leaf, we need to ascend, or end the loop. */ + if (mte_is_leaf(mas->node)) { + if (mas->max == ULONG_MAX) { + new_mas->tree->ma_flags = mas->tree->ma_flags; + rcu_assign_pointer(new_mas->tree->ma_root, + mte_mk_root(root)); + break; + } + + do { + /* + * Must not at the root node, because we've + * already end the loop when we reach the last + * leaf. + */ + mas_ascend(mas); + mas_ascend(new_mas); + } while (mas->offset == mas_data_end(mas)); + + mas->offset++; + new_mas->offset++; + } + + mas_descend(mas); + parent = mte_to_node(new_mas->node); + mas_descend(new_mas); + mas->offset = 0; + new_mas->offset = 0; + } +} + +/** + * __mt_dup(): Duplicate a maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree using a faster method than traversing + * the source tree and inserting entries into the new tree one by one. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * Note that the user needs to manually lock the source tree and the new tree. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_dup_build(&mas, &new_mas, gfp); + + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + return ret; +} +EXPORT_SYMBOL(__mt_dup); + +/** + * mtree_dup(): Duplicate a maple tree + * @mt: The source maple tree + * @new: The new maple tree + * @gfp: The GFP_FLAGS to use for allocations + * + * This function duplicates a maple tree using a faster method than traversing + * the source tree and inserting entries into the new tree one by one. + * The user needs to ensure that the attributes of the source tree and the new + * tree are the same, and the new tree needs to be an empty tree, otherwise + * -EINVAL will be returned. + * + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If + * the attributes of the two trees are different or the new tree is not an empty + * tree. + */ +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) +{ + int ret = 0; + MA_STATE(mas, mt, 0, 0); + MA_STATE(new_mas, new, 0, 0); + + mas_lock(&new_mas); + mas_lock(&mas); + + mas_dup_build(&mas, &new_mas, gfp); + mas_unlock(&mas); + + if (unlikely(mas_is_err(&mas))) { + ret = xa_err(mas.node); + if (ret == -ENOMEM) + mas_dup_free(&new_mas); + } + + mas_unlock(&new_mas); + + return ret; +} +EXPORT_SYMBOL(mtree_dup); + /** * __mt_destroy() - Walk and free all nodes of a locked maple tree. * @mt: The maple tree From patchwork Wed Aug 30 12:56:51 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13370230 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id A909DC83F14 for ; Wed, 30 Aug 2023 12:57:43 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 44F3F440150; Wed, 30 Aug 2023 08:57:43 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 3FFCB440009; Wed, 30 Aug 2023 08:57:43 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 29F95440150; Wed, 30 Aug 2023 08:57:43 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 1603D440009 for ; Wed, 30 Aug 2023 08:57:43 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id D1AE78016B for ; Wed, 30 Aug 2023 12:57:42 +0000 (UTC) X-FDA: 81180772764.30.047A4AC Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) by imf17.hostedemail.com (Postfix) with ESMTP id 045984000D for ; Wed, 30 Aug 2023 12:57:40 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=aMSkNN9a; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1693400261; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=q/ZpDcXIY2uplQWCw9dEjDeDQjyl2gwHXqRgJ65MCOs=; b=xi2JZF6xI0jlScXS09fI6GCg6K3BODRDf3xKG7vHkpeGGNh626azDz23OMSLL1bPTB6iGN sGFehk63l7M+12nV1HE5JFcWfSKrcce/yWB+AqXdJdlX6tojFvludHomJc3cUqIqUnS0+g 5Vk+6IE5WdGUIk5kQLMtvA8HdiSmVho= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=aMSkNN9a; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf17.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.182 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400261; a=rsa-sha256; cv=none; b=WQayS3dgCh1CeagE5usDGD4nrGSJM77pBJxDIm4m1HefFvquejqvPMZhkVa8bS9kVQRmwc r7kJh48yeQE/kOOAIcBtbP4TCqfyB+3LOzuvhHVCj+7mRH3OPb0VP5qUw0HpR0ZZI1ZG8m X9rigavjW4/Ix0jLWvmnil6RDEfwEw4= Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-1bf55a81eeaso29804475ad.0 for ; Wed, 30 Aug 2023 05:57:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400259; x=1694005059; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=q/ZpDcXIY2uplQWCw9dEjDeDQjyl2gwHXqRgJ65MCOs=; b=aMSkNN9arxQRndakQSlJZ/yiZmatm2sNIBcp9WlPzRdJCSIC0r34MWCWQRiJGUDfcV Kc5V1DiPJHY2aebKhTHPtVU1/prERfCUdXHMRocSjDCUr+4oTq1b31FAvXzC6Alxrs12 2wW3sv1BhFx6Ty8GVeMfCcWV47lDIWAQB3nJVBWaKX2qW2dxPZeSO87LlJKIvnKgLA5a CliJw0D29QOQe3DoBV7wtNWR1iIhgjNVg8UUOML2QNvQgmlyTPyizoiG+C52YHL71NbS xS19WHe2yqbMsTrgEElB4HAPynFQAG4s1shYCLJZJloJZQFC8J3a5ktxHzNn89g5Tpm3 Pbyw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400259; x=1694005059; 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=q/ZpDcXIY2uplQWCw9dEjDeDQjyl2gwHXqRgJ65MCOs=; b=K5nZP3RX1pVoATlPy+b/Sp3zIVw0qzpeUkVB7fK5r6BbXF2zN9bY+qCUwnxO77YByz m5GFggCfc33AlAJJzdJE0fK/GX4TZUSq+mq1z9DbeDUSsNScbteN0XIGXwkBE/hNM9m3 zpYrXCxijobuYGWdJxEWu9Zu54YLlw4zDNJTAjofN25R2BJdQdo0qULADAL4wIkXgFAA k77W1UjpPZDhzOi8ydLr3TpgwQFpgXZgV5Qym4CD1zxQ/jZa0SKqQ+33aTnQeVBkGU2P U7oJgl+A9CPFkxaNvGXNvdRIc/IAS0QhM1EJLedG0a2CevRTCtO76KCx1QjGslmu70no NSJw== X-Gm-Message-State: AOJu0YxAXn5S7+kBOu7gJejxadqnCUr2cMrPOqSN0ZxyhsPMjLrcWSYq Dmpsg2BmseKttPvD/VCP9kpqww== X-Google-Smtp-Source: AGHT+IGJ6wl3h1zU1EZ8Va876ePXGOkXhL6Bg48jGTnNAf5hacvqb0Z714nNSA6Bq7dqCI/W67lR4Q== X-Received: by 2002:a17:902:ee84:b0:1bf:63c0:ae79 with SMTP id a4-20020a170902ee8400b001bf63c0ae79mr1769233pld.33.1693400259641; Wed, 30 Aug 2023 05:57:39 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.32 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:39 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 3/6] maple_tree: Add test for mtree_dup() Date: Wed, 30 Aug 2023 20:56:51 +0800 Message-Id: <20230830125654.21257-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 045984000D X-Stat-Signature: bsh6jm14cqhjy76pojfjrxc6jdck9t4p X-HE-Tag: 1693400260-729291 X-HE-Meta: U2FsdGVkX183IkaOq65F6/6UNr4sjreTFJRlrwoUgB5mk7CX5CT0OfoSs8HIfQRpndsA2P+JZFWs3qGlB4dE/34QGWJfVy1btBfovdL6M2khNaLpodtFRE/zXNfbMPcip230EzF6k3e6rQ+1R9AXd1Vo9wdq9pnoVTzUzUwMsuOxC6Gu76Ii7R9GfUtt+m+UWXKRsnvn5fMejhmfsvj4hGNaIYgTW2nsdz50ag7a6Av83ZJyq1xNC2XFXCC38r0zM0lvmuQT2eeOoRZVaV/qGIQdLE0E9rwgXwvgjtpF4KG2ZCMP+x2Mcf7wiu6CCldFq4+W3vOwe3s+Nfw7hnNwPjySNzaosXkMA/taBkUoD0TNsDUvE1u5/spvTfHiIhw8/kw0CEAYBNEQS0ZR0omH9lKcdXdaUPE9QRL2lVrlUPWC8+is9a9tnzuv4TufToLavw0u+7u8qScSOpuG98Pp/CyO2Y+Q4coa0+vSgD7cg7+ofFC/baJ5NFbc3NmJmlMO22MvfQWmUTwuKJa2vNkP3+vZD/JFQNLULk58P9RPvEAYIItpCXejvNlikAP9romSU7XC33XfWqgZpxyKsgtC+VydgG9TxA6C+Ubh/nt0zjY96ABb8ny1QKTKEhVpdCNFC0ZtIEyJBs8vxaqbzjphlKq/3zmfxfFNonsH9nRGBoSDp/rkkrDq7rYOJWZsHpq25F1Z3IlkZsRylkKtuVFAfIJi4paw5MsoTymUF5UNAjL6lnBJYUrrUqtVhn+MxSaxovUu4bIMRDbnvFs2U/1pfaXBT+Dpu2C/g1310EJBfiPG8EVXuxacWI/K+k9k/toPYa8j4hVOuQzzfig58YyX8uFWjnVMz+AktjvfeYAnehm269q8EmUG+FKARkoYB4t4SD9kZdTrhB/Yfg8bQlbulLBnAa22560enLzXe1dFfDzwXrdM1UVqXP7MQChZKpqT8wzFlNHU6UV5eKZ+P+M 6IYFQEVL yAtEpL0xJh3cZ15Lcu+GSlVzwJjbL2NeiIuPLSXnWojXypTFNKg1BF4zuzPLejJkYf0/EGFh4YVqOyNknqkfq44P0P/kzXlcFrOdZ3Gf1RFcv0cECl2gdT20hRG7y0x70SG/2sj5styyquHTCuWZtw1rUnDf74/mrEK/tbeboB2htufrXuM/+68huK3kqdxETJUQB9Rk4oVmIUoIJTbxUIOGHwau896Y/MW8dONhu5H8Pjq1e18hvtElW7EMsK50STe4hevwUrQe4Al1Rx9BWzjxpdafwo2/SjZQn230PxOL/cCMdpSbX/CNdhsHp4afNiY2+NFGAzRlmcOs1Gmh+DhsvPzk1HKLvYDtaTlQuIuhm5eAa9VC96qRNqcrdOnw5WAGaRzgCqzTKcuWcZmUO3FwHVxrGg7D9zhkD9K4nBV7EOnA/Fgu66OfnVALOYeQP4rWxioiOU4uE5+vyg1AFofdjDA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add test for mtree_dup(). Signed-off-by: Peng Zhang --- tools/testing/radix-tree/maple.c | 344 +++++++++++++++++++++++++++++++ 1 file changed, 344 insertions(+) diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index e5da1cad70ba..38455916331e 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35857,6 +35857,346 @@ static noinline void __init check_locky(struct maple_tree *mt) mt_clear_in_rcu(mt); } +/* + * Compare two nodes and return 0 if they are the same, non-zero otherwise. + */ +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(&tree, 0); + mtree_store_range(&tree, 0, 0, xa_mk_value(0), GFP_KERNEL); + ret = mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + + /* The two trees have different attributes. */ + mt_init_flags(&tree, 0); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + ret = mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(&tree); + mtree_destroy(&new); + + /* The new tree is not empty */ + mt_init_flags(&tree, 0); + mt_init_flags(&new, 0); + mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL); + ret = mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret != -EINVAL); + mtree_destroy(&tree); + mtree_destroy(&new); + + /* Test for duplicating full trees. */ + for (i = 1; i <= 3; i++) { + ret = build_full_tree(&tree, 0, i); + MT_BUG_ON(&tree, ret); + mt_init_flags(&new, 0); + + ret = mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + } + + for (i = 1; i <= 3; i++) { + ret = build_full_tree(&tree, MT_FLAGS_ALLOC_RANGE, i); + MT_BUG_ON(&tree, ret); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + + ret = mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + } + + /* Test for normal duplicating. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(&tree, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(&tree, j * 10, j * 10 + 5, + xa_mk_value(j), GFP_KERNEL); + } + + ret = mtree_dup(&tree, &new, GFP_KERNEL); + MT_BUG_ON(&new, ret); + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + mtree_destroy(&new); + } + + /* Test memory allocation failed. */ + for (i = 0; i < 1000; i += 3) { + if (i & 1) { + mt_init_flags(&tree, 0); + mt_init_flags(&new, 0); + } else { + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE); + } + + for (j = 0; j < i; j++) { + mtree_store_range(&tree, 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(&tree, &new, GFP_NOWAIT); + mt_set_non_kernel(0); + if (ret != 0) { + MT_BUG_ON(&new, ret != -ENOMEM); + count++; + mtree_destroy(&tree); + continue; + } + + mt_validate(&new); + if (compare_tree(&tree, &new)) + MT_BUG_ON(&new, 1); + + mtree_destroy(&tree); + 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 +36244,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 Wed Aug 30 12:56:52 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13370231 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id ECDB2C83F14 for ; Wed, 30 Aug 2023 12:57:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7D134440151; Wed, 30 Aug 2023 08:57:49 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 781A8440009; Wed, 30 Aug 2023 08:57:49 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 62277440151; Wed, 30 Aug 2023 08:57:49 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 4F3BF440009 for ; Wed, 30 Aug 2023 08:57:49 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id E008E1C931F for ; Wed, 30 Aug 2023 12:57:48 +0000 (UTC) X-FDA: 81180773016.09.0BFFA75 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) by imf30.hostedemail.com (Postfix) with ESMTP id 1682180018 for ; Wed, 30 Aug 2023 12:57:46 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=UEJoTn1F; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1693400267; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=2nBO87JODOc2vxfEDdYbEmz2onn6zs2zxUKCCOpJdk0=; b=ZRrx4RVuHwkhclRaY64/4u0lMInI7JZXErSoViwuWgPoAccmYPQ9rRw5ADDeeqWK5xMDfo X3gBUYqsGJqbNKg45TLD9lzrrJC3V9o066VZkiPd61V7wX5PqoY6wXIucfaTsI425AZNdj OIc6Fl+a4sh/aqoruMFfbQSaXJPSTcU= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=UEJoTn1F; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf30.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.178 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400267; a=rsa-sha256; cv=none; b=j4gVqVMWuXtGbrJaB8Z/fo0qbTO6exQf+ZbzxrV+pE4GpJCWMtysMzbCFOAVuNmL+pcwt2 MkgTXpNh+PdUSNzV8q3fwXKX7DL9mQCQWHsypzlIKqakMIAnXbvenKd3A6LBh5+j1tc5Oi 5sJ84nXbpXIuqTVS2lcSNYTHrPJaeYk= Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1bc3d94d40fso41942115ad.3 for ; Wed, 30 Aug 2023 05:57:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400266; x=1694005066; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=2nBO87JODOc2vxfEDdYbEmz2onn6zs2zxUKCCOpJdk0=; b=UEJoTn1Fy2jY/5L0izMCSfDk0yhsV4lxP79hqoNMlRdLjYcpv1WxW/rfEPxCUoEhy7 BoPSampUo/SHI5n2bWirmdyEYTr3qIYARjYYB85kXEHUVTH9+wXCWvJTAAzAf0wGWUB9 d3JfqBK1HpBOA3U/3gNWh93QnqRPXYz2XALLgk4Cf9eMh56/3wWE06CdI3z9t7c99QqQ QO025pq/T5bfTaPXRB44zY0e3vPlRBCWoDLQkMOU+tcAl49LpuKicLEzMtU9MP0dWL0e RqRmM8TeLaEjDyvqvBA98wiMAwUAVf03lFaefI45Ry3c5Yo9qN7wDUero9R24R/5wKvP JSvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400266; x=1694005066; 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=2nBO87JODOc2vxfEDdYbEmz2onn6zs2zxUKCCOpJdk0=; b=JzEnG5MNLqksm4EG/Gs7EwdfUgUZeYBSCwrojLDwa0nLqtnp2NlVgvMbfnOIhFP3wH SLIlfAcsTPjcbFZzdX+REHtZ+rXylWAjbjWwFc5+9pdaXjsl8KIZf76EmMoi3BaPVq+n 0WogbP+LBOUQ9S4jq6xltwSZ64kM9sctf8ggvwsAde5e6QJfxpxYBDfokbKaraAi22Qh n5TMN3L3PMLyIahj0xPWx9DViDgsqakvTBDpJx8Iir9X8hi1N4rDlPDrzRwAH9vTiz8N y8b45H2FttFRGXtJY8VJvwM4QP5i5UJtNQDtuRDKau0n3S91GXVbZjlo5IiCBvo7GSr3 jBmA== X-Gm-Message-State: AOJu0YyBrz2BOmArCqaeO8mn/6IM//cnXY7SZpzwSvqKVSypPRYzV1vF GSjJlBHFhnRolC3toRjacgSzxw== X-Google-Smtp-Source: AGHT+IGx3EmrDiZTTIfJpOeK4JOagyqHaEyqo+fM7q0DuUUO076LoLX7sVQJgZT4uYkTB/BqJlAAiQ== X-Received: by 2002:a17:903:268a:b0:1b8:7e53:704 with SMTP id jf10-20020a170903268a00b001b87e530704mr1893310plb.27.1693400265985; Wed, 30 Aug 2023 05:57:45 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.40 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05:57:45 -0700 (PDT) From: Peng Zhang To: Liam.Howlett@oracle.com, corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org, surenb@google.com, michael.christie@oracle.com, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 4/6] maple_tree: Skip other tests when BENCH is enabled Date: Wed, 30 Aug 2023 20:56:52 +0800 Message-Id: <20230830125654.21257-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam12 X-Rspamd-Queue-Id: 1682180018 X-Stat-Signature: rkbdi5ew11qunmjgncr8qmawqd9c5ebm X-HE-Tag: 1693400266-505763 X-HE-Meta: U2FsdGVkX1/btM1CsKuesPL0VB8LT9YizMbWLOSbK+KU6D0novM9Nqu8DMswvYcANhD42hUu+z9kUjX2EIVKJtUEdkPCWPfAvnJOBjQQYbZoOOt+CGXAiTpR1e6ZydWiwvbD8l9XwJSNx3CD8L3Vd/hIPBMX4XR/H4dbqeVg1si6qdRmFqlnJ3SQH2NAKMyl0mIvWvAgLRUmXOdZ8W2gHKhHHyL+kW8KWkCMyyLSEWixKlHKiwfIYJHH9QM+I6hcrbuLtUEATFRYiTZKfmkO8ee7fHhS3ZmUjiwRLfHBIJsBiApLANPn9TAUDos859C+6F4Cv4ErR3vARjXDxq3i6FImETfT9OfWFFfTgn5C2z4TQ5NFOispsyBtcU6UfqBLp/ueekuWxyC3PbfbQn+LVtyv23/X4aYKeHGz5AD/9EBGBcS9rMjzobrqI22OJleC/aE4PdRdBBJ42UPFtDMc7KKBY4fwHMXSdE73/s/3W0LhWuuxkcLMciHC8dCzaRjxIpN8AsOAx97MnXtUWMcWIqEyLtKXgbBAaXzgRpwG81U5HJ4KmJKZuyJZb0o5reANc71WA4XvJIOp98fhknK0ivdwSy3LtLQlROuKYSEz6oAt5z/2BvW9Uy/g7vwo6lhOccupgdXBuX6j7DFKLTztAE6gx4/YXeux0e9ks2HOxsOkeTfmfQMxHl3WmzbD+sAV8UGJK7cjdlNbKHBJhDxsLRYM9ZLDuPdGBZ+fCrEHxQhkIzXeDYP9w2lfUKqd7L7FXUgdRBbAZ/22mnc9/TXWAqs8PWDHxiunFEkuW2C3Qvyx6kF/OAUO8X1Ol3ea3J8kmgQlv/EQqOMsC4PWEL1+Gge2ILERmtyC9S/hz99Ch3BVlBMlF9662Vn6p4uiPmhS3gKvMQld7KkB9lyI8B2opVbL4fVZh/bHUNd6v2C84ILKMiCHfEx3w1PKawr+d3fk+z6hmxc2MXpOOXM7bS0 kxcY6g22 aZh+GAxKi2dRJjpmhVQ0FfQ3IkjMqtHi8gCe3JCYUHQ/N90NgZS+ZrGt3ToaEXBtsWAfGwXn6lOWLEjkL30J22xrKSFG/a6TqEnUEXRJsXs3d4BBqs362rGT9C1zRXWQeCzIfpTtLLCKFgNkRGgQhcnwkp8xYf0Nd/r38PXUxZuLjDd784eoDrtaGdLMXf5uU6PL5BnNU3R1EYeqaLhH4bloHohG5LB/3IDw7WNmkrrGZ6FRZhO7lllDOPz8Ix/s4+bqW49eTnLLGjjIu10fvOxLYoh94azRMSpFNKSOqmUaSt0EPuDgtmGCa8MfW4zuvjPYkdOIgVPzL3Gq3/bhbo8HTPrMlEr0oNSh5THRbzQH7TuNNpxD9efLXzlILVPIYUoCmeyIN/K6UdcwfNl5Q9/QW10uzYzB9m2DbAFqbuVPBofUm3Kfxh3/VRu41hV8S5zE/FAFDktkHvCrU6du9Rl26Bg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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 38455916331e..57f153b8bf4b 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36282,7 +36282,9 @@ void farmer_tests(void) void maple_tree_tests(void) { +#if !defined(BENCH) farmer_tests(); +#endif maple_tree_seed(); maple_tree_harvest(); } From patchwork Wed Aug 30 12:56:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13370232 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id DD051C6FA8F for ; Wed, 30 Aug 2023 12:57:55 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 75CF7440154; Wed, 30 Aug 2023 08:57:55 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 70C65440152; Wed, 30 Aug 2023 08:57:55 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5AD54440154; Wed, 30 Aug 2023 08:57:55 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 47D5A440152 for ; Wed, 30 Aug 2023 08:57:55 -0400 (EDT) Received: from smtpin22.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 264EDC0154 for ; Wed, 30 Aug 2023 12:57:55 +0000 (UTC) X-FDA: 81180773310.22.ABAA061 Received: from mail-pl1-f181.google.com (mail-pl1-f181.google.com [209.85.214.181]) by imf25.hostedemail.com (Postfix) with ESMTP id 2CC89A0024 for ; Wed, 30 Aug 2023 12:57:52 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bHI7jP9P; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400273; a=rsa-sha256; cv=none; b=LeC+bqGskupq63myhAXY4vgcaUm3vnmjOSIMsmVzySIIsQTlyJfp42MvUemXq8XY0wOZB4 Ex3YlJOH54UPxtyCZTfGqS7MsuWIXGJkEySf7hs6pEn9Y6I9n5hQXFyysgt7SGMJCUARG7 stAlKsbgsK621kKnyrL37gbwLxSB29A= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=bHI7jP9P; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1693400273; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=likGmWzdcl79JyC0G273JC8fCg1Z1MuweBHmHeu5k34=; b=LnjOUzKkgZw7ApJ1Kj2A8HE2I5MAoSZtlL8BORxKEL+PxUdAaDqwlDF5RPs9mkfyzyc1kl Jiyl/Ea8MEHMkEcUqC4qMICV8HBXJht57cP/PqHI4R0MeZlzJbal+qlhAQlWG5+8nZsXh+ rvonGFCFN58MYGmLe4i0cjx/dN8qL/Y= Received: by mail-pl1-f181.google.com with SMTP id d9443c01a7336-1bf57366ccdso5872415ad.1 for ; Wed, 30 Aug 2023 05:57:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400272; x=1694005072; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=likGmWzdcl79JyC0G273JC8fCg1Z1MuweBHmHeu5k34=; b=bHI7jP9PDSTQjPdckHP+nVE2smx30uCrB4kwSVUYfICmldmczu5MF/ljYQ6gscQKn7 B2C0xLyB1tu+WquJKTp5xZ66HML47L9spWgUDr9lALd93hp7n03iNJjEDkOSU5/IIFzk TUWIxNxmUMicaUmQOEEw6pMOcTb/kiqE8fJT75Iozrna2T/fY+oNjEmo6ywrSnNrEWuM v7vk/G68Z1nK7vMA/+jjziQCVW2jQVRojg7426PcuCCz2tTsp/GWPwRqUO4A/ZkmpgSU h9huv3eJmGHQmdJgJL2zHkYMz9FkDgiEYg6N+fjnt+xZlu9QcrgAtgDsIHcDHTKtamtZ UNdA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400272; x=1694005072; 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=likGmWzdcl79JyC0G273JC8fCg1Z1MuweBHmHeu5k34=; b=QZ+WfARhwrvYH+g3/7Gf0MNtJ5NseHFkPyrbBKQL23WWUUJ/p8UM2txuWR2waIVwVs qVvYFV8srOJ8la5aSUWYQ/HrM2TrjEt22FhpfoaA1pwXXe9hXvxx4RMdiPWiAX0Blp2G pygsWmMfz28Z/jk2+QMtiacYtgqiYFFG1qEQlMm1zHutnp2WzNuiUl61srpUhfIZOusJ c4QcUXHiq/FPdmXtUPB/nT6QLTnd4cQUvb2jg+XS4tzD0qQeG5MtbKxKw+rfaiWCFJlp CuR1pjSqovFg1Ia4hmAn8i4ltwfFLr+pKdtDs8kvzGXGPmugAydNXvTbRcGYtobJE2H0 e7rQ== X-Gm-Message-State: AOJu0Yx8zfwNkszZAQTsxwK+/9+mX+WdHTOC1nVhDJExE2/X/ytUw48e hStluZhY/yM8irowHppDxzAVYQ== X-Google-Smtp-Source: AGHT+IHEZW1hekFijghmb4eDJa5CJeFIwOgrvu16t1pBzdglsm2NfGWuHdAFed9GN5ly19C8PHDQDQ== X-Received: by 2002:a17:903:228f:b0:1bc:4415:3c1 with SMTP id b15-20020a170903228f00b001bc441503c1mr8693507plh.7.1693400272035; Wed, 30 Aug 2023 05:57:52 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.46 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05: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, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 5/6] maple_tree: Update check_forking() and bench_forking() Date: Wed, 30 Aug 2023 20:56:53 +0800 Message-Id: <20230830125654.21257-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: 2CC89A0024 X-Stat-Signature: ws4deqf3rx98baebmfhnhk4q7ocawt45 X-HE-Tag: 1693400272-498839 X-HE-Meta: U2FsdGVkX19YnL21GJXPavzXvcBsWff5BNluCg6sayd3tJMMlbPG+pmS6fDjQ9Qw30Li9YQG+nfbtX62nkh0j/24pwhYvYxISyhXsc+wXoJx+ELUjowQ03DKlxUiUJnp2gyeHsmZvfIsqwg4505L6D5v8dS6m4QwGP1W9HJ2HklBAvhfk9n4BIbMPZvy4ArN7iY84oTdQbzbhzZ4qQMe6OBzXYKkstZkHosn33qabCWui22yf/uhOftXb8ZwPuFK3Qkm0Ekp5GZHAVIefe5Ijhn9eus8AgBf1rCBrJjtOuKNihjz27f+ib1X9rQ57SmCxT7/gk41mJXmgO711uTPP5srqkMqRbHPQvu5y5xhJdD1fala8cAKD9TEekTesonMFSTW0NhIkYjiSwe0u9hQG2jauix9DaVRTJtNMmrOaSQY2WCIRwt9CHOUiIecetAq02q2GnGe3bux6QihrWAvxYbuSs8BUGgAWrcqLYpTEAmX/5AmKiYGx9XAPjly0uol6Su+41M6qQKyC8yB2vKHFhfK1scqqYsJVoofbKZ9kwHOLdgohs/o6KyhYKTpaaZCOwF88pgTiQC24jOI+aP/mMXQPMMHj8wQ9S4rVuzTeM5G6BANlIXdcx8m9H4mtoIgZtv6EUIirupX0bALHbqUzFhlahcH6KeHFLwkacLWfZ5O7q48BHNRc5JBUIIWlkEULlXISHIreXG5Ljeb1N026LOJpBNZwaA1pKbtUOyVVE1xOaCc/0cqMPQHZEhVax1y4VHKwV+ULQSW3TYAsvMOQsQ020eb75tnPZX5KjTDlktEIpkUgNv8SaPmCAueSELTp5c8DsIza9lWGx9bkpaRwkKnwiqmZKi0wY0reY+FwhfiMnzswqGgEnj6RF3vqpY0lvcMYHcq9E4QbfTMysx82r0pQoIPRj5Hcjb/t+jTUAB2yV83KjjzumO44XrkGI3C4EX0aXi1tlq+N7JBopQ qSdabgEu YiHXeienUGA26n7qgrX4KqCC1PyW3lmRnqcHa+vB0qnGMcpaFzF1SSogvwNZJH1xkcDQkXjKwZJsKsEi7LjDpv/sGjrugYn27MbILN1pf4j1ld3VK48Uh27r/ZEGZ7iF7R83cDgW8Y1gTwVLC5rEuMcfX8mvp3YcQzveX6cHvBRGPGomXi5RNDdHYopJVpzVGdcTHsr0Bpa1Z5TbOSPLdXK+HAcoJWEhmBomoKp2kBxmvyscc1lIIZIoD5zW7MGQLGNKMhe84pgEaaBznpKooqJRHwcV0E1xUIRp14jJJmGDNRRArq2DGZjHi2CdcToHObbtGSwHJk36Nr4Y5rqVf8ZJC6UuZZaJLsJd6dRNViuAvuGBItOHhAhMzEsxdoVKHKCeKxrmMTDIFe2M4hSAVf73pvzn73nsNNk+ahS+UBnEQ8VSFWO2hKXWJf64GrhYL2SdvXzSnyi/Zw5FCG0FJFnw8aQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Also increased the number of VMAs, because the new way is faster. 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..72fba7cce148 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 = 300, 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(&mas); + + 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 = 300, 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(&mas); + 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 Wed Aug 30 12:56:54 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13370233 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 506F0C83F14 for ; Wed, 30 Aug 2023 12:58:02 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D019D440156; Wed, 30 Aug 2023 08:58:01 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id CB160440155; Wed, 30 Aug 2023 08:58:01 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B797B440156; Wed, 30 Aug 2023 08:58:01 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id A7997440155 for ; Wed, 30 Aug 2023 08:58:01 -0400 (EDT) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 746EA80150 for ; Wed, 30 Aug 2023 12:58:01 +0000 (UTC) X-FDA: 81180773562.04.00068D7 Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) by imf20.hostedemail.com (Postfix) with ESMTP id 9639F1C002D for ; Wed, 30 Aug 2023 12:57:59 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=XWJCoNj1; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1693400279; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=0yWpUOFFGV0pFtikzJZ55MStl9p8vL9hqNAbNokJEAE=; b=05tzIGbWpzdkXqtjmzl2ok3LKt4BFHlNBsokvS2AbeTwtkQdgQDyEcbB+cF9OPdKNNG2gw SnEquE7n5wGluX/IMf2KwgEFlemR/HR0HJi+ZvcuNqJI8fZUC05s5LzY20SX7vPfFM/j95 WFWH0C4GaJSJHu7uZpYjdYzno6CB0o8= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=XWJCoNj1; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.214.171 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1693400279; a=rsa-sha256; cv=none; b=ZN0NPhZ+pr8xWiFBBN2vzo/g0UjKh2oIYlw6c6FCtkxBpbpCYaPB4wrM3gcTsPuUJsRcyw 4+nJDAXe8BJJuF9LUnZrm4eYepz7aoRIcpW+ivZirv0SG9Vlx9u223LHwluKS5R40ClCAg HI3vB4bAb9XR8HUNeMLlXuOe5z90IYg= Received: by mail-pl1-f171.google.com with SMTP id d9443c01a7336-1bdc19b782aso35314675ad.0 for ; Wed, 30 Aug 2023 05:57:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1693400278; x=1694005078; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=0yWpUOFFGV0pFtikzJZ55MStl9p8vL9hqNAbNokJEAE=; b=XWJCoNj1+fYxjDEE/7KFwYVu5JFsQk/TlWHBB5L6hTsH45HAa2+ourfkUD3kAwfSIH 15xc6WlWtv4EqsLCy6gc+OA5LfA2BWs8osJ0BMFKBktwIXGQgM2VkJH+7D527ielgFCV yhU3N6SVht55SS1mp3w58XpZdrj4H+bkY/yoijUtdOxx5yQJiNHTnKBeuIsi+ZsKC/CK 92p96yp9k6rEE03vdBN+NlPC6yPteZSzEKN0a+sUEE9/DIhxBsL6sQuMNKN/YP4HxgdV E+tlZ+AtpVQiQzuTC1EunTKj2hQguZu0ni/oOm2OkUK4BiS6pI8B7kEpnTW8+4YSZVx7 m9Lw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1693400278; x=1694005078; 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=0yWpUOFFGV0pFtikzJZ55MStl9p8vL9hqNAbNokJEAE=; b=RiVcNqRR3Z8IKzG/hahXk4yarxiowgXgH6p9+G7BvOqqaMtBuHtSKPufDnIAkSfcNQ Pa852ijec+uGAZSYX04G0ZjhyEc2UQk+GTOWXwWo263RM9PkvQtjZrAx8NJjwGtXW+Pp YyIaWuYq+A7VPH1odOo5RYH+chjx+HtGXAo1kNLb21nTBTKjYI9NdDy4GQqdfjGTimTg dJ8IYryipg3OcFMk9RNm6WX0ebFIfE748HqkAsiURJUB/FFTgZamzSEXUu7BbouepwS3 Mqgosd7hhb8X23xdx5it4NHNtGhKie1IuDwZyhkTskmKmcyvd1YQ7pSoj2t5W+KWNRZB a/1Q== X-Gm-Message-State: AOJu0YwA2ZwM3c7Vgr2yvJnAkN0UzB17a9rIX+ofU9uqX6uI2+lPysWS taBPR+sW6HkZ4FNB9iL+Fjepkw== X-Google-Smtp-Source: AGHT+IHrE4rTvkXO7RwqgnTEvxw+lDK+ANzha4IBQF+qFVxQo+OdsPaqgZdwuRA69Q5Iw9LfoqglQw== X-Received: by 2002:a17:902:da8c:b0:1bf:78d:5cde with SMTP id j12-20020a170902da8c00b001bf078d5cdemr1986513plx.59.1693400278469; Wed, 30 Aug 2023 05:57:58 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.247]) by smtp.gmail.com with ESMTPSA id iw1-20020a170903044100b001bbd8cf6b57sm11023265plb.230.2023.08.30.05.57.52 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Wed, 30 Aug 2023 05: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, peterz@infradead.org, mathieu.desnoyers@efficios.com, npiggin@gmail.com, avagin@gmail.com Cc: linux-mm@kvack.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, Peng Zhang Subject: [PATCH v2 6/6] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Wed, 30 Aug 2023 20:56:54 +0800 Message-Id: <20230830125654.21257-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.37.0 (Apple Git-136) In-Reply-To: <20230830125654.21257-1-zhangpeng.00@bytedance.com> References: <20230830125654.21257-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 9639F1C002D X-Stat-Signature: c3xd4391bxpbb1hn6mkdjgzbbnt9y4cn X-Rspam-User: X-HE-Tag: 1693400279-76832 X-HE-Meta: U2FsdGVkX18QRQRuM7MVKZfPqQIMB1jFPk7Ef5v55dj31/IBsCScmTKN18/E4a6rw4o/AL/gs3OlwgKCvaHDW+XMgNb7+frkoSFtErB7lN/7xcGeffocayVcRqzS2Pxrp0jf4Cd5WR8WY5QYbS8tfWTSWXZ2ymnG0t/3M8EpJzr5dM4MMOlERQZs2AOECyfzfzPf7pSHilHs66QfHZHF9/B5m3d6WRCi5pwo5rjmNaKkOkKRlWvh0YycKYLQU77opEp7ZVB/vzsyrZvNZFVd1fHN/q6oR5SvQVJb+00HsQvGpTF+6cj/K+PeagXG3exnv31X2TYxDdLOpKCyQzNIq1sP5zYaBQKsQJzi74SCixdBGIgoBqlHN2cYKBsShbfSraX0hcVP/MJmv6Dc4QIs9M6QPk40BIM8gJhxR5gSPpvjHBif8gCApjTDF1ocT7j9DGeW9zRYlzb6l0HRr3/s26vhm/cM9OtOvznXMFCfgKv/O1AxccuC7uTUelxyHA2ioDHLNwDuapEnmqbMe/hIwqdd0arJnim65LF9n7tR5UGgbWRrcLxNv6m/kKx3xX50hL+pujiFq8YZaquCFBl2lqSUVr/lblF4OBgBr7nqnIG1SPXGjEXqcCAxDI6oy7cv2RfhCGpdvQf44Q/sZzGOyG+HxoNUrmH/vf+C3XX/bQsVVQedTpMDHy4Gx7IIvNuBvnOHpvjplhvl/9UDThZ42qug+0EbxUqLLlAgds9358IKduFZOL0hW80ub+cQSs5cTVbiGczYNSG5IzdsCTBOluolxySnMf0PpqlGkhkG1vMFpoJU8QZhcrbOtio+Cc+vAgoxOJyfeuZHNNIYw3FHIV6XRqnuh7nW4TT/YRSv+jW2tSB9Z9SGq7tcV2XpEHOrCKAxXE48IBbg7QMIugFJEmh/HL8ChSNT69aKoavGHqsoOXsg6zOjJhGD1b0N22bKssgxZ1swbaRzgcfASv7 URL/vNPG i7boC7bJkynJtCcVS1+OzQX6rABXIGUxYhHDR86mJHoXCveDH2bePM8NkXYOABT/LC1/maJuJsG4DpICHRd4EtuAzS+aEpkkS0obmolp+Ga+KoLAEZ2Hpxhb6U9fN/2UwAbfFRG3cBoDw1epSyqAicZmYs0yEZwsLgWr+FwfazHT9hmVDEQzL/m5T2gyU9zfKPo6CZNNEwLjlRDl9hmRSFpcc18HX1sK7cGShOrrgAfGmi2fawzbK1dekTyJlYmV15bRb1qEmpM/SjcsScUCebFIe3GPfnXYOmJr+EdGrhVwK+GGxXuBQAWCbhIj/uHwkRIwTs/ZucIv91lBoQUQnWblZoVerrut/GxeIn0WH38iLqn71Did+VBS9cOtT36Zj7eSZKxRmy8RUMOn8xvdFcGSVo9309gDwBa1wHRzjNmRsBTQJxrQBOotIVc/fyhuQyExU9Ry+O5DkfMegWOkiPaZ4FPnJJeUyPnQgndDUXwvyqi3Bgsdv/cJW8XlPiqDvvvxO X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Use __mt_dup() to duplicate the old maple tree in dup_mmap(), and then directly modify the entries of VMAs in the new maple tree, which can get better performance. The optimization effect is proportional to the number of VMAs. 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 numbers. There are 21 VMAs by default. The first row indicates the number of added VMAs. The following two lines are the number of fork() calls every 10 seconds. These numbers are different from the test results in v1 because this time the benchmark is bound to a CPU. This way the numbers are more stable. Increment of VMAs: 0 100 200 400 800 1600 3200 6400 6.5.0-next-20230829: 111878 75531 53683 35282 20741 11317 6110 3158 Apply this patchset: 114531 85420 64541 44592 28660 16371 9038 4831 +2.37% +13.09% +20.23% +26.39% +38.18% +44.66% +47.92% +52.98% [1] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang --- kernel/fork.c | 34 ++++++++++++++++++++++++++-------- mm/mmap.c | 14 ++++++++++++-- 2 files changed, 38 insertions(+), 10 deletions(-) diff --git a/kernel/fork.c b/kernel/fork.c index 3b6d20dfb9a8..e6299adefbd8 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,17 +677,39 @@ 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_NOWAIT | __GFP_NOWARN); + 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) { vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); + + /* + * Since the new tree is exactly the same as the old one, + * we need to remove the unneeded VMAs. + */ + mas_store(&vmi.mas, NULL); + + /* + * Even removing an entry may require memory allocation, + * and if removal fails, we use XA_ZERO_ENTRY to mark + * from which VMA it failed. The case of encountering + * XA_ZERO_ENTRY will be handled in exit_mmap(). + */ + if (unlikely(mas_is_err(&vmi.mas))) { + retval = xa_err(vmi.mas.node); + mas_reset(&vmi.mas); + if (mas_find(&vmi.mas, ULONG_MAX)) + mas_store(&vmi.mas, XA_ZERO_ENTRY); + goto loop_out; + } + continue; } charge = 0; @@ -750,8 +771,7 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm, hugetlb_dup_vma_private(tmp); /* Link the vma into the MT */ - if (vma_iter_bulk_store(&vmi, tmp)) - goto fail_nomem_vmi_store; + mas_store(&vmi.mas, tmp); mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -778,8 +798,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/mmap.c b/mm/mmap.c index b56a7f0c9f85..dfc6881be81c 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3196,7 +3196,11 @@ void exit_mmap(struct mm_struct *mm) arch_exit_mmap(mm); vma = mas_find(&mas, ULONG_MAX); - if (!vma) { + /* + * If dup_mmap() fails to remove a VMA marked VM_DONTCOPY, + * xa_is_zero(vma) may be true. + */ + if (!vma || xa_is_zero(vma)) { /* Can happen if dup_mmap() received an OOM */ mmap_read_unlock(mm); return; @@ -3234,7 +3238,13 @@ void exit_mmap(struct mm_struct *mm) remove_vma(vma, true); count++; cond_resched(); - } while ((vma = mas_find(&mas, ULONG_MAX)) != NULL); + vma = mas_find(&mas, ULONG_MAX); + /* + * If xa_is_zero(vma) is true, it means that subsequent VMAs + * donot need to be removed. Can happen if dup_mmap() fails to + * remove a VMA marked VM_DONTCOPY. + */ + } while (vma != NULL && !xa_is_zero(vma)); BUG_ON(count != mm->map_count);