From patchwork Tue Oct 24 08:32: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: 13434035 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 8AE06C00A8F for ; Tue, 24 Oct 2023 08:33:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0B8316B0199; Tue, 24 Oct 2023 04:33:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0401B6B019A; Tue, 24 Oct 2023 04:33:20 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DFD406B019B; Tue, 24 Oct 2023 04:33:20 -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 C6F006B0199 for ; Tue, 24 Oct 2023 04:33:20 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 4F8B8140E7E for ; Tue, 24 Oct 2023 08:33:20 +0000 (UTC) X-FDA: 81379690560.16.C2C7C97 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) by imf02.hostedemail.com (Postfix) with ESMTP id 884BA80002 for ; Tue, 24 Oct 2023 08:33:18 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="X7/H3+v/"; spf=pass (imf02.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 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=1698136398; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=IMtnlgo/n9WaDE3utqwhkIz9Nlf0UaRzQ16KIVMUWP0c63DhctgDnUo68h265JlCvGyKkg 5Lop6kidAsVsIPyMDC6nTMQeUQPhC5WKQrTKRQnOQ2oMwhxBQHd8pGCjZQuyNUXPjm0u1k CPoXlv4E6ICeyuiSgkZ+NSndZnPkeZg= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136398; a=rsa-sha256; cv=none; b=ZslhssSx+nOI+WWI0TVctRUwFQTrrDiWAfv6eCl3ZBCdI9vai+m6MVHXcfsJ2qUM0C/hDb BaHr/UdgEXSW+8lzqyMd3ZgqOO+LswJGffxO8IM9nGKKOb0TjAqXtra0u8+7QswokM6dj3 ZPx1Ke0QCv1PQ54eAxNxNfmAAeg8ozI= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="X7/H3+v/"; spf=pass (imf02.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-692c02adeefso3266479b3a.3 for ; Tue, 24 Oct 2023 01:33:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136397; x=1698741197; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=X7/H3+v/FXHPtOj7sCaOYPo4m3CHIcVh23W1t273iBSDfsSx8j7YEzV2Lp1dwEdlPT DVPqoPeCHXAl7j+c5WO+81T82ta0xlPND+cF/p4rCnjpJ3NBFKwBUUE2PVL1ivspLuUq HKT5rYEe9HKKpB8BXERStpG+kxCISzUe1YKIwRnmvolkybTnG+xZEawuP3UY6XgYRuxu mhvxWaXPjSuW+5iPxGvTFjMWP0xtrEFNJQs9pQWr5dyJeWKRtDQbpQpsYxmpU1l6v+M4 1tkYmnt/GmAG1et49+X7d7AqZA+egbAs30/iZIlGbwjEYCAQQnP45BRGBSFyqnXyZkuN dTSw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136397; x=1698741197; 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=7MLK4HxQMsxrLAQzNmdHMtQCN++SQMztyyHR1MHkRQQ=; b=Ttw7CKPBIDwCc2OWPjXQ8wS/KwbmSR07W+HPb8cXl2N+SQrLVQVa0AeqiXbv+YEKtG X8+W8mo97oe/9PibrPc8ywDQL6D0YGcCRLICxPc6S/Kng9NhlkrUtt/K7LIyBNPfJgSt UcO/yb++wAdLRVmnUzDHHMILQnpKJDc1fNaHPeiB6oog0akiYo5Q6fPlGmqZ3qZbBdEr s3n02WUVlG1VaWYsPVDkJE+zyscGOiCQ2JHkoBW90lbc46ORcrgafQiTVdOqPbLMCOgq ErXgtpvoir5v4/aeSR21h58gTp1Ajd7L82KXvJT3h6qemXWjDPx9ZiYp9ru7x7qfgq5Z hKbQ== X-Gm-Message-State: AOJu0Yzg7J8r15WZscI0GVH07MjAdKXMA4CyCzl2ZDKd/XfvPiXg/2Cx WM3u3Ka1mIv2jfBThLa1V+kUjx5nvtYSu8iDXlA= X-Google-Smtp-Source: AGHT+IHB77N08kpQP3kK7g9QlYWTNYn9tfxBH6TdMNcz14U0iu/fhKvY168Jlzr+1CThhjfwCpOJUw== X-Received: by 2002:a05:6a00:2292:b0:6bd:7cbd:15a2 with SMTP id f18-20020a056a00229200b006bd7cbd15a2mr10659966pfe.26.1698136397397; Tue, 24 Oct 2023 01:33:17 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.11 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:17 -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, mst@redhat.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 v6 01/10] maple_tree: Add mt_free_one() and mt_attr() helpers Date: Tue, 24 Oct 2023 16:32:49 +0800 Message-Id: <20231024083258.65750-2-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Stat-Signature: x8po6qhaqsuopb1jyjxpkye96acnwxar X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 884BA80002 X-Rspam-User: X-HE-Tag: 1698136398-731431 X-HE-Meta: U2FsdGVkX18Mnh/eaa6HYEDzWn91OorAYVYedDNwnhECcuuM10DaVh57vkp7DOGrO53kh+YxjChf8mMjGmaIkf4VJRaYppBwZ57RTSWXYyViMoSyiSKfC34hQCaHHPKGoZJIB0fK68JhjGEPn1RYSJsONNPVERi4s4ZaxyIJh3JIYXLz9BCVE3cU3YUbNcxxy1LvNmoQJa854ETVjFTrt+l1abuE/Rf1Hf3llMT2VEOyOn9lRxq/4QwZX/Nbipug/bDa5UspwJV6cxgXvtrDPVQTWT/WnmRxRfueqL2vZAOTQl2ZNSq/Uc45c6ZN1f2C/9N6wC5+Xo3BjCSmeC4m6ff/lk6/p+IwXdkxByaZkyQtetlZuhYBDdbq8WuDS4213bHxtktfwx26i3om7F+tn0lZTRrmtGG9rB0WZ+fJC/iLAL75XbcElTN+tJfpcqIXkk+2eFehmsrowVvbB473mkfvnLbd3j0i7lXic24i0gRUhDhTxaEoKfx8wca3t6cLZzeeZZW1o5NhamxQu44yO/XNEHBrRDYXguXY4vEjh1iUGEubTQCPSFuFew32qQ1arp6rD2CnEpMX0MQeg7seTv7f14BVIa1AWGPR/GPRfo8qfXf/rMQ33P5j9FVz4kydv0JfrUCnGFLtTWVu1Mw7I0Ok5b9CT1AcjNF7dvaykHFNG5jKYujpc43TQNnhiUQoa5nSr5lQO14qt0xQtsP4Ef6s0NGaVcUhMHTy5cazqYYuOYFatHeXCCdFmCXl95DLMcKkVZ4vvmzV4xAZtmYYqeRNrhMVJexN3Qn72WxzKCN1U3XXW4YnYWsYhtGYx5r+jzbYFOpyl1LJ7PfXF2Z+pOmM5HQ+Ci9c1KKx6Noqtxc9JwP1b5qsTUE+WZsAq7RlTOUfAfOknjqjp+coyOVfA1ee09u036DTZJIp90A0dsp7XPga0A8qvKfy4h9dxWZm3Fbr8jbrVQMonzUSRzq iO4HmfL2 uM0J/NrOnVKoaAuD4uRvxKitnSZxp0TcFEdrOw93iOtSGdVX9Nyg92eyZ+qe8K8G5jk42ECylfUfLMXrJ4f2WFBNn873qFARGlxt8zyylQdF1yRKfDUgq7wd6FQmZd77gFxIFQl9y8kKqCWM7kBUzlyXbzTrCuGpkEmEXIcNW4NtFoNcpVLE+kjXgq5UhgisQTQDlLB6R5cvZr2JAdiqCfXB02slQue2xUBuZuue0RfidKUz1OBZt+odBheh4M48Y/kFBPlzvdS0CKCcSvp/HxgSqbLjubRKYyVEh34zlbso3+DwT3qQ6ojdGKxdM9+1/r1uq0hybKPwiDXemyJ6N1zw2tLb2teC1vmBpqWCFm4mfkqPjBgrSsa8WPcuDGONq/wS84jVwGNa2AlQH3exzII0LzJ7MkxsCRgXT/zZpE00iNVZUDQLKE/znbcsjkkxREzf8uLvsRlkWbwih1FFEBlg2IQ== 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: List-Subscribe: List-Unsubscribe: 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 bb24d84a4922..ca7039633844 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) & @@ -5573,7 +5583,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 Tue Oct 24 08:32: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: 13434036 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 79E45C07545 for ; Tue, 24 Oct 2023 08:33:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1A0F36B019B; Tue, 24 Oct 2023 04:33:27 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 12A506B019C; Tue, 24 Oct 2023 04:33:27 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id F0CE76B019D; Tue, 24 Oct 2023 04:33:26 -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 DC0D36B019B for ; Tue, 24 Oct 2023 04:33:26 -0400 (EDT) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id B5741C0DA7 for ; Tue, 24 Oct 2023 08:33:26 +0000 (UTC) X-FDA: 81379690812.29.8ADAFA4 Received: from mail-pg1-f177.google.com (mail-pg1-f177.google.com [209.85.215.177]) by imf21.hostedemail.com (Postfix) with ESMTP id E0C2B1C0009 for ; Tue, 24 Oct 2023 08:33:24 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CsDg1x+b; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136404; a=rsa-sha256; cv=none; b=DSkd83RoaFgaf+2dq72h4a5b5x4jK85n4il8iyRJ8n2C24L9SHj5xtsmxRDlJ3b6e0umO7 ncP9HicR+pUEcdZsJ0fyZKjGaGzQnV+1reVfK4+jOuOD30EPW1I+Y2BCyGHNk5xWPE3pr2 orbi6qT3T27DTzAdbIgFVjVqcyOlvHE= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=CsDg1x+b; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf21.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.177 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=1698136404; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=0zbWsMLZgPiFvam9C2htkH4jfsW3fYF7wd4ETkNcUpaEO+MZNhiVobilQ3/Wjd0OVJCM+B tq62QBS8hveD5hEaTV6FXtK2TmFnuB5ox8MxDfZz1VwGmkl/wxA8d8BWNf+ZtEBTWO1mmZ +LYGvQwKY5HBxogs6hN87xZCBtTReA4= Received: by mail-pg1-f177.google.com with SMTP id 41be03b00d2f7-5b8ece0f440so207194a12.1 for ; Tue, 24 Oct 2023 01:33:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136404; x=1698741204; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=CsDg1x+bIXCmKVgU+3nAeaXjrjfl+e2LsT/qCvnGqAJ1B3vKIUtUne8cYHfyZr4qJf B8Ik9Aj+6iUZQSseZl9hZLm/tA1S9Alduiqr0XHanNfMYeeAWzpw8eSUCz5nP0VYFJZG L2gR189qOJVXMOarR76WZJ6NSbepz4NcL0YApltKc8Bnfo/MSKw9fGU5zP54z7kMceaJ aBCIcokGyCdISxPQkmR0/E1uSorwG7gH2OkeDTGU/L1Z7X1tCr5CWe9mcq/RHfg3z/MU hdYmdpf/rWmcak2d4akrDAPoZvU+3IiOtkr8G+oiK/mndyJSY99170T/PJuolCXREoZw CjjQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136404; x=1698741204; 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=r3L72Q2C0A6XyhsC7UMGOLSZK5Azm/i+GpPRU3MZq4Q=; b=slq80IWF023LppLW08obY7Y/UeHUz1Dilmobq0/zQc2rWKpUTXl7+KggLkfS8PVsGa P+gZmcz+Jg6JNf4d/n6R+hLAeOO/5QYiHXolSQLIncxN4CiZDaFy0t7swB8LMMV0glFS IK2+oHpFVzjfkKnr7lXf6KJagwWHqwLl8riAwAQ8xL3JBsZE2+uZzDPR9oy7baq/u2Ff 5IQfIGLttngjlh4aQWDVYuZlsTh4WIWF8xOXDunswyYzZ0BkqZKc4LmTQiifV6mfj4Py 6Ez6f9k88Vw+z8WMU0Xm4JGN04zfMq4/8uMxIUwzpZAelW+jWhc7BPrkwlBQQXLMK7fV RdEw== X-Gm-Message-State: AOJu0YxWpoAjIXGaK3Z5whqFxBroGrftPCsW5Oiq/MWUxvmfLR4Fy+3K +BDQPcsJJUNec8IfMyODfXLzKg== X-Google-Smtp-Source: AGHT+IFRF2d7NaEqXWWjz92Xh2LjjQSzD8bGo9Dbzm/HViEErv6yA9g/lWFc+D2a7eTh24RKV68/bg== X-Received: by 2002:a05:6a21:a108:b0:17a:e79c:c5ab with SMTP id aq8-20020a056a21a10800b0017ae79cc5abmr1692896pzc.48.1698136403796; Tue, 24 Oct 2023 01:33:23 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.17 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:23 -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, mst@redhat.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 v6 02/10] maple_tree: Introduce {mtree,mas}_lock_nested() Date: Tue, 24 Oct 2023 16:32:50 +0800 Message-Id: <20231024083258.65750-3-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: E0C2B1C0009 X-Stat-Signature: pacxckkpdamiadcfzy48r8k9dxa5j71t X-HE-Tag: 1698136404-268375 X-HE-Meta: U2FsdGVkX19LiEDx5EvCGVgyxnmppaBLK91EV2TpUTqYIrAGYj/VNuaPRuGQeIwli5Lqd9SKH6B+C4qJSLHE/eJtNI+xjhhFyLpOLYO14nNWsfpighNhbIHTL7gieJwVgLblkL4QirJ4Az4wLY/q+UjPZX7NRbMu2xJngPwyNNztfSm+rH/89+5oDocytzQd6FvjQs1I4L+r7bRmjIZL4x+3tR6JUhh3rU7B7PJ5FFc+6z0pYZeJHkV2OF0yAxrrMpQZJtUZP1bJLvUZg5glG6fTcZ8T+dJpybgR/gPLECm2BKGBNizu5Ch4mP/qY3P5CkjMoznUq/7A3SwHbI6ORssymA24KsnpszIQ5iYCgdpgvi/d8ZrZktarKETe1c1PIKR22gjBex7mvUS4K3LBTH/DGB1bzD9WMuaPvVMWLLxUIZYDr5IAA0kI2oTmjLkiu8kG7TYnAq3jckudJEhcO5zzvtS175ZSUOTKa69Ysk1pHgSouV/JuMNl68ISwSD76mg7TjRZUZIDB9CUMGxHu+3xrBPnixcXxBcvemXt+voZ6RiGVQDw3kurPRD9wEXm5MxHVwhnsfnqucr2p1+o/s78f+gyLxB1T4XxOZPcykiBNWKZzPr1D65LM4YhLokUEjglsyUCLOTr+5IDi5dYKUysYCC3FtP/nHmmFP5Ojx+w54eDlBwEk2v7ehuF6AlStzvclrm15syFR73C2qtsZBzBmUgIuBIy5fG6SDa0dExUzTqqtl01qQWWdWZCivgJblttSzS8sXUEKjfnkpkYSH/deVlrxB0a83EIMn3sqAA9M/xQ76uCz+FqK2idn13HKEiv6EiuiL77syXXMhKE+1dOr0WMFiSkea8FHcF/WjmXAfmM9Sj0kse2ZSSeeEztn4zo8jbR7qN84EXgaW+xFBl2PzgXQTBGnjMymHGvhPffl9ztrVv5YExcxzZXftcx4C/u8lYGh0eJVL+8z5I HWR3nPWg Im8OO/zVn2cqL/t+CXc+Ukj9uHdTwFw+QQHPsflPCdW23//Atwmaz1KHmpdhrC/YWjdr/JXN5QlSBJ6B1VbwKsEhxK57BtBYKZbfS8OE0KLht1h/xqQyo2AYqjx7VLO3mSRtuxnOTVw0RIAA4jLhClPt2M95DkdlycYZLcf9wdXA83A5VRuysz7xdFnUuazYAQaSnQ1ZcriGC/rZC9bXDwttYa/BQuIMhsE2Nm9oWDPsI/t5OVdAfh+LCsqolLaCaTG/7wL8FAmfIebApzjg0SjEup9OFkqrdopEjMO5JlrSzxTbP9C7nWhNhmi3CqlUPB/OKB+jGJqPc9V3F0FWizka+2aQmf92kAB/sxeuPNA3lKPt4a1tgF5FQvplmm2/zJFLRIoRYAiDZOeanXyDdBuERcpE7fFTImr+HVzncOecVmD12Mibma1qqOR2PhngrvsPLrPE6B5t3yA1wcqY/LBp8uA== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000012, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 d01e850b570f..f91dbc7fe091 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 Tue Oct 24 08:32: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: 13434037 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 26520C00A8F for ; Tue, 24 Oct 2023 08:33:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B3E286B019D; Tue, 24 Oct 2023 04:33:33 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id AC8766B019E; Tue, 24 Oct 2023 04:33:33 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 942F66B019F; Tue, 24 Oct 2023 04:33:33 -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 7CA1E6B019D for ; Tue, 24 Oct 2023 04:33:33 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 4D68240528 for ; Tue, 24 Oct 2023 08:33:33 +0000 (UTC) X-FDA: 81379691106.08.4444D2A Received: from mail-oo1-f50.google.com (mail-oo1-f50.google.com [209.85.161.50]) by imf07.hostedemail.com (Postfix) with ESMTP id 5B07B40014 for ; Tue, 24 Oct 2023 08:33:31 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=fFIPV0iM; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.50 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=1698136411; 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; b=25ai0Y5pisRR0HhOQAMtBBMm6jMRZCsWP39nZmX7f1sPEHohLvOlc9LqmfsFl0Z4gxN6rS 36KMmFyp1pS5/rUcZU7jxtbc5GcP/6GHemHR8zLyebJopNXKPxEiV8FZsX4GgW8L4fgq1t 1nwXYjREcwyCNDRjKSctGrqbabmg0CQ= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=fFIPV0iM; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.50 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136411; a=rsa-sha256; cv=none; b=bXBden6uM5PGKZjQvH1HOlJR8QVsbv/vqvxjE0vNjOMEox+IOt/Fb8ujqf7nJiTpBFWeij bEOwv6DUG90edfA2kvSLl3RCkc8k7wLZKca5lQVIfUK4pfxv7r3odP0rYX9bS10IYDGXOL fEhCpiuMb4cTHrC1lkF2UT5bB3BJvzY= Received: by mail-oo1-f50.google.com with SMTP id 006d021491bc7-5840bb16101so2495009eaf.3 for ; Tue, 24 Oct 2023 01:33:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136410; x=1698741210; 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; b=fFIPV0iM2o+gaV5YZGlRUKEt3BDm9o1wRsTbwaQZH8+RKSEnxsbxsppIyWCbo+CsxW +wg+gzaY8wOWONz78otgOwhcu0xlbi1nY5gaBshatH9L6rJyIN9PNYsGlwSlhzQ7ujog lhux8RO880QEfEv40cFgRQE5TPbSaAOK4nDLj+bdWw/3O0QGpejxYPeegfOkN5/k/yjc r5V7BboxwDgf5tSrguQUWMOU7B/hs8fD3kGiSdjl6SgWz2daBtqZyKDerJYUAN7HaozR 5zkGAwYc4EkkxCEzmsN+0LrAjmT8Vyw23U712QbFXBNRbPtOnNzDPmY7p/+sYl14tBro k53w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136410; x=1698741210; 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=lHQENXHqQ4J1FF/RY259IZhkjTrimWDCVwtt+ghNomI=; b=r0EitLaCMwI4FIRB1aAbRG/V4wBEdd98GiO33cEATeVhqipkHh5jmFvNe9FICsb7ML V9E/b/7BRZRMt51io2jl6jAZnmDB25PJe/Tcf77FmbIYrGjtmT0B6bML5R+6EYAGD5yT IFO9iN26XR/iuCoiwnr0FfBIWL+/GDKZd9SFAio7LUYo1CiEDxcbeK92AwFWyGfQXOjA KXeHziEahbdJv5IsItFX1tMEp3qTC1GfseWm0R6z1u99Opd7eApFxHsGCDkqZBixa3FK CCuPSpn2Qo/koDJCFld+WxM8blZfjocmxz8mHHijQUFQhIhBdiVudmjYwVFaLLgmZufQ XH3A== X-Gm-Message-State: AOJu0Yz0FsBVWf+ZfgdPzeM3hXmHs7odUAl8K/d3ZwnQMy+qjmmiM97Q NmxC8bVBsWRrK/qJgvHpd9LPWw== X-Google-Smtp-Source: AGHT+IFrekRN/XNA6lcRh2LlIUyaj0w4/DqtKzTvG93hVgHB9Sh5vAVyOLcohkcwlswlYTz79UBU+A== X-Received: by 2002:a05:6359:8003:b0:168:dbfd:cec8 with SMTP id rc3-20020a056359800300b00168dbfdcec8mr4800441rwb.13.1698136410342; Tue, 24 Oct 2023 01:33:30 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.24 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:30 -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, mst@redhat.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 v6 03/10] maple_tree: Introduce interfaces __mt_dup() and mtree_dup() Date: Tue, 24 Oct 2023 16:32:51 +0800 Message-Id: <20231024083258.65750-4-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 5B07B40014 X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: irazae3eims6g7smdu3fotruqxia75qk X-HE-Tag: 1698136411-338498 X-HE-Meta: U2FsdGVkX1+oAlXFEus/xLI1NkDOW6cDowdxS4NIC8GCxLq2Z1QMXhu1hfcuAWJPwR/1zTidT1C755+JEBdlOMDeYhr/xw6IrRbMo5ghDNcmHcwrtpqObME3WH5NNFK2kXwUYSrd+kxvNOIXYzsPK8ZiEVQ0AYJRvNKUeZJoDSiQ4azWUL2bfoyN3Cjfvew7dkWUoAEHroHwEa6PKLoZvpnc/P3dt58S0K71D8Xet4fOAjw5Z46yRu4fngvZdV5NRyyYESudG5gdhrqBYDSi8Qfv8DxESYozRwvBFGc/AqxrFdgeoABt4sg/KobkJbbJBR2bdgac/AMX+OexT3h72hYK9IjCWr+kYVGhJjPDDWAgPc/7HPA0oioTnfjT/Wf9kHC6XcW4b5HT3S+K2qrIb4PCHTTxyTOVuZE/DKKI/iTIwG2LZZKx2XSxOUnY/6XKgL3eDs0scv/urgnQ0DSwPyig41h+SgyStytig7tzw7VfLzTeYkzc7+281GSumFN09om1SQfHwef3Tex2xkSYSQcq5pxgVr4FAcBD0JDslR7+ctD3f8qJtdb8oaIRbxPqs6c6eZzomXV8iSh9NIQZPq3XG5NbJrgonpVrC5fYAtL+vFQhq4Ou86tODjQ3l4PkJea1O5xM17jSJGLvPZtr9KCZiG33W5cUpIQU3hyqjlMgCxVqzWoNszZqINKn9sicreNH4UuM1T9q5jFadd69eVdc5bOpN2eVHTfM6mP+ggE9whjCc5k9Cas4a92vEjM6+gso+8vzWmOHNEqHF5MmZqHgzY/w1HneVPYyYev04bHWxfCvsx69escbf5ymGkVJS2EiXUL1KO30QDktBJJB6QXJA+7k2pkrYw04APYYvHTEfq7RI/5otN7Q7tBBm+SUjQGD0Ygm0DV11vBqy8Vl4o+qVKGuBjelvepLpqls+MwQgWGClOZDkkzGCDebUdtM3k7vOHp0naNW/b9SKQA eG4i3Two kiDp4h2dDrwA+zDRmY0CVOKV31aO3xWMMMvvb13bbo1nUtCOd07GD7XiVF/EHzilzT3Ue/hD+79KrIs27VTBMVgBR73GFCmxWMWwjr2307ZhG7LpI2mPZLanTLnZcEX9WyRGUUJIVDBt2RiuZopRVAxZZ8wTnlcDSORdYJou5B8YpgevoL1kLUazHmAJfqKGL1K7GRCM4oM2WBiVpI199aWsK72z9MmZ59HKS/Q1UfnQibuNBjMhiCbNeFz6Uw6dICIR7J1D0T3UaTUUo8rBaQTLageZ23j/6ev0WouxO2Xkqc6YLKYdoBJ6POHferYM9h6o/S1WtTAcIcl2utwEmpl7rdmKsNT1tjFDtv/tMlkswLaqgA3NFKaW50rYAzm8ZDEPtyrb84Hh3AXZ5UKNWm1a9ZBj8ule+4sImfLuQrerXnxytYYw2QwgyWklSpOyeApoy8r8PS/5UqUfwiASSE32O7BI+Q9Xc/6eYprZ3LZ4OdEles37FVBQrDnpKAYRsdGn1Dp2c8TpC/XhrxYAly6Yf3XM8HLNJZKonVHCPm0WrZwM= 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: List-Subscribe: List-Unsubscribe: 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. Analysis of the average time complexity of this algorithm: For simplicity, let's assume that the maximum branching factor of all non-leaf nodes is 16 (in allocation mode, it is 10), and the tree is a full tree. Under the given conditions, if there is a maple tree with n elements, the number of its leaves is n/16. From bottom to top, the number of nodes in each level is 1/16 of the number of nodes in the level below. So the total number of nodes in the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1. This is a geometric series, and it has log(n) terms with base 16. According to the formula for the sum of a geometric series, the sum of this series can be calculated as (n-1)/15. Each node has only one parent node pointer, which can be considered as an edge. In total, there are (n-1)/15-1 edges. This algorithm consists of two operations: 1. Traversing all nodes in DFS order. 2. For each node, making a copy and performing necessary modifications to create a new node. For the first part, DFS traversal will visit each edge twice. Let T(ascend) represent the cost of taking one step downwards, and T(descend) represent the cost of taking one step upwards. And both of them are constants (although mas_ascend() may not be, as it contains a loop, but here we ignore it and treat it as a constant). So the time spent on the first part can be represented as ((n-1)/15-1) * (T(ascend) + T(descend)). For the second part, each node will be copied, and the cost of copying a node is denoted as T(copy_node). For each non-leaf node, it is necessary to reallocate all child nodes, and the cost of this operation is denoted as T(dup_alloc). The behavior behind memory allocation is complex and not specific to the maple tree operation. Here, we assume that the time required for a single allocation is constant. Since the size of a node is fixed, both of these symbols are also constants. We can calculate that the time spent on the second part is ((n-1)/15) * T(copy_node) + ((n-1)/15 - n/16) * T(dup_alloc). Adding both parts together, the total time spent by the algorithm can be represented as: ((n-1)/15) * (T(ascend) + T(descend) + T(copy_node) + T(dup_alloc)) - n/16 * T(dup_alloc) - (T(ascend) + T(descend)) Let C1 = T(ascend) + T(descend) + T(copy_node) + T(dup_alloc) Let C2 = T(dup_alloc) Let C3 = T(ascend) + T(descend) Finally, the expression can be simplified as: ((16 * C1 - 15 * C2) / (15 * 16)) * n - (C1 / 15 + C3). This is a linear function, so the average time complexity is O(n). Signed-off-by: Peng Zhang Suggested-by: Liam R. Howlett --- include/linux/maple_tree.h | 3 + lib/maple_tree.c | 276 +++++++++++++++++++++++++++++++++++++ 2 files changed, 279 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index f91dbc7fe091..a452dd8a1e5c 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 ca7039633844..6704b5c507b2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4,6 +4,10 @@ * Copyright (c) 2018-2022 Oracle Corporation * Authors: Liam R. Howlett * Matthew Wilcox + * + * Implementation of algorithm for duplicating Maple Tree + * Copyright (c) 2023 ByteDance + * Author: Peng Zhang */ /* @@ -6475,6 +6479,278 @@ 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)) { + memset(new_slots, 0, request * sizeof(void *)); + 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, need to be in MAS_START state. + * @new_mas: The maple state of new tree, need to be in MAS_START state. + * @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; + } + + root = mas_start(mas); + if (mas_is_ptr(mas) || mas_is_none(mas)) + 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 an entire 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 memcpy() 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 an entire 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 memcpy() 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 Tue Oct 24 08:32: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: 13434038 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 98602C07545 for ; Tue, 24 Oct 2023 08:33:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 328036B019F; Tue, 24 Oct 2023 04:33:40 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2B22B6B01A0; Tue, 24 Oct 2023 04:33:40 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 12A786B01A1; Tue, 24 Oct 2023 04:33:40 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id EEFB56B019F for ; Tue, 24 Oct 2023 04:33:39 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id C4B94B61DC for ; Tue, 24 Oct 2023 08:33:39 +0000 (UTC) X-FDA: 81379691358.16.DA0DC26 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) by imf07.hostedemail.com (Postfix) with ESMTP id E00C74001C for ; Tue, 24 Oct 2023 08:33:37 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Ux7EtGhL; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.181 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136417; a=rsa-sha256; cv=none; b=5C2jC1D7IIebtHpJEdLb28mDZuHxyx86UagIfykdmYoxR1zb2ZQr5NWuBURByXcj1KLoWs CPYMF+z8mD48xIgIMNQ1TSEV5P/IvrOsNP5c+m+ErJjf+Yy3uNGH6cv5+HtWPFg7bEXrdn 2LD84tj1CEN/Jp05t8p2k/W7HrqOy8U= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Ux7EtGhL; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf07.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.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=1698136417; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=DEyX9JV21yehil04quHrmZ5C0HWoajTObKW+Ao6vkDjovIu6PvStSMvjsI9g+4OsvkHJet 8pdbA6XQ4o15h+KQgshai9qPtz9Vi8OnkzYEvzgzb7b5snCFo0aIoYzfNBam7HVR/RV76i /nIE4zc3bIkz7SoBq8ozp0YwSHGJc5M= Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-6be840283ceso3421627b3a.3 for ; Tue, 24 Oct 2023 01:33:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136417; x=1698741217; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=Ux7EtGhLU2/DIoTShEYeQ81ZwmaOot4uf1qtqGHrh8g68kHnNkmOyxoFicfYRqlwjG 9tbWZx+vNWMsGIyaSqg4GvzUn9WiAPUAee9hSbSULmui7eC4O/xXz8pQ/UdiCQiaRj2+ Egd5Kiw1uJrAl0BDwPTj9gMonjZ8531armAgsUv6dHj76amgT2IYB4blXYuBtD0LGGn6 5s5SLjPy137nNmvkekdOHiM0LvdfKC6R13fVo4hPaqYjBxIuTKgdoH98YgXuPYu1ahit U4GAbIq0gMaX14+c/CcY7c0crRf5ZQ7EXTEOsoEl7srXRLiR463DGQrkA/XsRg4j6MqT etog== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136417; x=1698741217; 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=XXZWHgZHrQ6fRhi1dWH8Hwu+H4KBhNEo2ODkb4cUdHA=; b=qBpcfndrRErlTKgKkWY4cc7UgzB/EGgpZxTXSXEI+mOJjyvIlZdj7tB4ZU9vqNFf7l 186y5TdKoQHmNOiEa52kbjd39gVbhQHs8Wos6F/ZI3qLKXnW8J6wAbTLTf8Xk5XCs2/+ UZSwR5I4x1Fi+G8JEBxpp5ALXd8X5vVmXykcZTEmJlOnCjXEmaWJzu6El9TiR8+YhOAM aFZif4em7J4EvTqtfwHZdkvjZDxj+k49pIoeXwuA4itphPIFd+hdlY7vYUpAJoXdLiT9 Y1LycOfxBnTvNVoVOL/uzNrNANBMFsdzDH7/ow5MqZTQEMjsEUawXhXFw9Fcxem3MfLC Ybhw== X-Gm-Message-State: AOJu0Yy5m1T0Td9Tvfx54sNvR2OXq6I2YpU3FT0BQ3NRznhX1jZ+XvGb loYJm3a+xazIw4gRCOT2MGbvEg== X-Google-Smtp-Source: AGHT+IF7YgpjhTzyLSokdtvDXNfCbJQY3JWpF75jJ39WYAp97AHtn6ttEhmwYaz4RKxtcXMftuCXLw== X-Received: by 2002:a05:6a20:9381:b0:130:d5a:e40e with SMTP id x1-20020a056a20938100b001300d5ae40emr2254231pzh.7.1698136416831; Tue, 24 Oct 2023 01:33:36 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.30 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:36 -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, mst@redhat.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 v6 04/10] radix tree test suite: Align kmem_cache_alloc_bulk() with kernel behavior. Date: Tue, 24 Oct 2023 16:32:52 +0800 Message-Id: <20231024083258.65750-5-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam06 X-Rspamd-Queue-Id: E00C74001C X-Stat-Signature: 8jib4gr5nkfmuphuiiir1css6doyzocy X-HE-Tag: 1698136417-173759 X-HE-Meta: U2FsdGVkX1+vz+yC82gEQ6NsFae3PQOy8Yuyuz8AbiC2DadboouEtE0+xpUWwKPYku8GMEOtdrZTmPRlwBEmq2poq1EoJ9wf76kD97HPl3KPjcbaP5AlANvxoqZEkusuUVQKpiPVyOtA4Fm/vYQ3Bgak8aad1hBAat4QnXp8UHSrveUYJvYIj1LN8QJp1mGtDZKCJxIc3Yf/i04pfp1rhyL9YH9LB0dyM34xupmJ7/aKQswhkTx3iP30y4zanbw+JXutnQjL+GupXDML/mx7Z24jc5YyhSVL1rpUUkAXhHHqFmdqfXjzl0se4PrKg7yKCLWnymtj7An+wr4k0SPzDW5XCZzL4mbJ5xgjN0mWYIPHYKnouwbci0EwdJ3GohCLWKMOPi2/WJRdOgv4BDTYkNarLeMpua2oveX+hydFMPySY0AzUD7INwwdl9aESzv4CAQG9fqmGEj9GB4poyuHU7IFeS0G8Ijk/ZxHqFI0y4VgmabuDGC/Hrcns70PkWC4kPUMjYp0gwNUenu6MO8F4ZqdVG2H+wieE6n7HCfWzSjDiQ6jvgo2Hfq8fYp/LAhYnDJ228cW36gxEVUPA9/30LmaEHMZoKygMM3vCoxBkbpwXwmDXkqittOpHwTAw1PtgjCY70Q9UpyGr6QvIv4nccQkVV+lqyGyp6HXnP71rkuqiZRHkTxAWiuTNPOQIct6WKeyDsu2OM9AWUb3oOOteOy24z405Sqjej4iTMFTh2sF8Kl3sswsvXLogET9fECHukRRv6VCmhL9ysqfYVf8GGbRkchiNRrOmSo2VKrRUT5Xcp2wY7iRzvErdOiEqPD6923DHCJBt5Muc5YXn/EAgGka+xbG1l9DA7kmy7NnUul+hXxrTyX3MU63Z6iD8wZjvTbVigWn4Z3kZIsPLvwT41pFvXK7YLdd/xYIQjFiwo9UvLCZSslLNNSMY5930EPTieiOKNou4D07kCcQhYK VEcB+yTj zN5NsLEn8iWzQj668RtWQiMjc3p8ol/vXw+znSXWsnoKzee2ZmRCiZJrvZUShohXNL5mPa2YPzHo8nZtTBpb9v11BzX2d42zuRl/INovueddUHCaNGyB8lycYIqFFeB7KCDr3HzG2ihrKoDLSFuwygi9ttVxSjd+16gWPbNlZgkg8/C/a8/+LhhuPCQ0CWfSiTPqnwquAIy47IE4nXnVA4DKeE3tBwD3pKdIc3cDIyz3UbwdCd4IkGGf36aji2XUt3bI+ze1NmnV/Y2PZbaWIE2zgbwHVkiOfKN9JLjWZZOVsknj16Ad1/9Xhb7SGPeS6rEtaFEedQJQVUQzlGeVKJJQ4CC/zXXBACSN43gMZs7TA8wfq7HsMKFRMPjP60IOrrQm2HPTPzh5cQinuQBGLw9+98FAf36RIYWynUtgVrNM2abga/QtuyP182xmSVjYseEqAFXqgRs6Gmn6dRkkQD9yEKQ== 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: List-Subscribe: List-Unsubscribe: When kmem_cache_alloc_bulk() fails to allocate, leave the freed pointers in the array. This enables a more accurate simulation of the kernel's behavior and allows for testing potential double-free scenarios. Signed-off-by: Peng Zhang --- tools/testing/radix-tree/linux.c | 45 +++++++++++++++++++++++--------- 1 file changed, 33 insertions(+), 12 deletions(-) diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c index 61fe2601cb3a..4eb442206d01 100644 --- a/tools/testing/radix-tree/linux.c +++ b/tools/testing/radix-tree/linux.c @@ -93,13 +93,9 @@ void *kmem_cache_alloc_lru(struct kmem_cache *cachep, struct list_lru *lru, return p; } -void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +void __kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) { assert(objp); - uatomic_dec(&nr_allocated); - uatomic_dec(&cachep->nr_allocated); - if (kmalloc_verbose) - printf("Freeing %p to slab\n", objp); if (cachep->nr_objs > 10 || cachep->align) { memset(objp, POISON_FREE, cachep->size); free(objp); @@ -111,6 +107,15 @@ void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) } } +void kmem_cache_free_locked(struct kmem_cache *cachep, void *objp) +{ + uatomic_dec(&nr_allocated); + uatomic_dec(&cachep->nr_allocated); + if (kmalloc_verbose) + printf("Freeing %p to slab\n", objp); + __kmem_cache_free_locked(cachep, objp); +} + void kmem_cache_free(struct kmem_cache *cachep, void *objp) { pthread_mutex_lock(&cachep->lock); @@ -141,18 +146,17 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, if (kmalloc_verbose) pr_debug("Bulk alloc %lu\n", size); - if (!(gfp & __GFP_DIRECT_RECLAIM)) { - if (cachep->non_kernel < size) - return 0; - - cachep->non_kernel -= size; - } - pthread_mutex_lock(&cachep->lock); if (cachep->nr_objs >= size) { struct radix_tree_node *node; for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + node = cachep->objs; cachep->nr_objs--; cachep->objs = node->parent; @@ -163,11 +167,19 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } else { pthread_mutex_unlock(&cachep->lock); for (i = 0; i < size; i++) { + if (!(gfp & __GFP_DIRECT_RECLAIM)) { + if (!cachep->non_kernel) + break; + cachep->non_kernel--; + } + if (cachep->align) { posix_memalign(&p[i], cachep->align, cachep->size); } else { p[i] = malloc(cachep->size); + if (!p[i]) + break; } if (cachep->ctor) cachep->ctor(p[i]); @@ -176,6 +188,15 @@ int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size, } } + if (i < size) { + size = i; + pthread_mutex_lock(&cachep->lock); + for (i = 0; i < size; i++) + __kmem_cache_free_locked(cachep, p[i]); + pthread_mutex_unlock(&cachep->lock); + return 0; + } + for (i = 0; i < size; i++) { uatomic_inc(&nr_allocated); uatomic_inc(&cachep->nr_allocated); From patchwork Tue Oct 24 08:32: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: 13434039 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 6EC24C00A8F for ; Tue, 24 Oct 2023 08:33:47 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0B6A66B01A1; Tue, 24 Oct 2023 04:33:47 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 03FEB6B01A2; Tue, 24 Oct 2023 04:33:46 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DFCF26B01A3; Tue, 24 Oct 2023 04:33:46 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id CB1946B01A1 for ; Tue, 24 Oct 2023 04:33:46 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id AA5EB1CBB44 for ; Tue, 24 Oct 2023 08:33:46 +0000 (UTC) X-FDA: 81379691652.19.9F70557 Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) by imf25.hostedemail.com (Postfix) with ESMTP id BCA9FA0018 for ; Tue, 24 Oct 2023 08:33:44 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AelP+El+; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 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=1698136424; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=LzQGea3ThiOhtLZ2mIsjKtOcp/u+5n93y7Uk/pu7ucQ57moT3GEdhBEMtnTfP603wDVpWV BwAGc1/f7iXEwjj5A8yuFWu/egDNciuFyn+1BdGVAsHObMiLWwarxuR3j6mj+myRAeuyIa RNyA2SxWpgRJULQdHUH4yGDspzaQuwg= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136424; a=rsa-sha256; cv=none; b=jXdWQqkYLG9686yR5pNj8t/8D+fC2W/9WBPm62I/2prEgyfuJCyxLrSUXxRSfR0ixaL/cF R6D2fp4lNHiyex2FGbrH386PH+BdJG9pI+l7KG7vDLO5oVTWwMCIwvDTHBjCqBGio73s6e LAQuwZFk18BL4x0F+CTTt7hzihVfa3Q= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=AelP+El+; spf=pass (imf25.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.177 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-6b77ab73c6fso3055079b3a.1 for ; Tue, 24 Oct 2023 01:33:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136423; x=1698741223; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=F9a2wn71CT7l6jmeDgx5GiWCiAo5KcsAe/ofRJgEyKw=; b=AelP+El+/OnyWwKO7kLCyzJ91yiZVtT3K4BmNXUnuKYhcBrD2ZddQJ6+tcDLLa2Xck uCPN9bd1T43+RBcFftg4aeNUyHj3LvQK6lAe2e/CJt4UmLxpaqUPldXNkvHZSB+aft5r 2awvD0FNwSL0KrVnfArNsLEFmvc91m30fiP0WqAGS3mwIMGIvAC5fxhB2k6zTc2Fud1G gnhSiAC7Cdj4Mgf8PjvrY0N0eq9LdN9ESlQ1K6F0AXe/cDYVdcnPeS/edmzJx8fTS+HU aVMQPlpLEeULUaz/K4M2+JPtFPdmuEGhg7FIU4oMBerJ72n8g3S0jZLu3Rlpxwsv+X0v 6qoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136423; x=1698741223; 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=HbOvsWKuVoUdgegynDkAaEuq4QH4fOJHU7lhfXDgOOhJx0Rp6x2bhPtd7BIfj1bBOK F9Fbu6mMsi1vZMRkES92K3ZailG8McLroPdGASqzcvQobxCa/wuhiCy1cm5aplr0by4Q zxIRwkKwvCBocRbrEv4NxB8z1WEyqrqpTS/PqQT4dVy1qxqcI38kSZr+bPfavtFts6br K//y6wQi5TO0hSmSMVLYxCrv0hPdI8K4voXLZphqIUYINS9wYZe0iF+gEwEzqbdXAzTg f/I5m/HDTj2rIyFuBrH7sZxZgTyLsjeTcsfyXMbJ92P8prb3LmUYvf0atB0Nbv7hdcht qmLg== X-Gm-Message-State: AOJu0Ywt2on3c+Da4lHnkRc2X8PfBt7SZ9N3YWwFXOdhwAOSLPxi1Gsb BZpgrWuPmJBG5ExPjmCNKxCuxg== X-Google-Smtp-Source: AGHT+IFzRPxA82XWrAQS8Sn4M56zSVzHTehtJ70fiMLI3XrPkvHNR56M5baqh4DLBP8UwYKZghrJfA== X-Received: by 2002:a05:6a00:10c5:b0:68f:b5a3:5ec6 with SMTP id d5-20020a056a0010c500b0068fb5a35ec6mr14426161pfu.0.1698136423347; Tue, 24 Oct 2023 01:33:43 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.37 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:43 -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, mst@redhat.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 v6 05/10] maple_tree: Add test for mtree_dup() Date: Tue, 24 Oct 2023 16:32:53 +0800 Message-Id: <20231024083258.65750-6-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: BCA9FA0018 X-Rspam-User: X-Stat-Signature: afidx95hab1jq4c3xag53tx8ktqn3k8h X-Rspamd-Server: rspam03 X-HE-Tag: 1698136424-107308 X-HE-Meta: U2FsdGVkX19yvgVb0Fx/QChGYWc4We+yxSt4aZawm/TudlyJ7akR7HGWgCUaSlgh4Ul69nvEUgPdDiVqSyhDN/iFkwUDFaJp+RC2HvaKTcNHANXd+uHmaKOCxpDjwgnu1seZJHaNJgtzCVE0LbzLT+HCwk2m4zhD3TW1QHu6VG7oe0jrnkx+FrvWHLIMeoZ1NjJ0B4gWN61nrd7CX937+g3VFVcP+RaATu8mQfq7on6wHpiArKXOrXqQFXsU4DJ4OrPleDKkEmbrOVF2B/afcB9FbY5cP8Ist7MzAq9/qFDiiHZKBDZB50Hpr+N4S4FBzaub1t6M3mEOPtu8qhSNRA7BW6eojoPYWI3sDcI9oST/CfTcNW8zfgcLotJRSNGIxdqxwoWqwcVA1gtbstMJIHCSC2MkMLW8mlKAwTrHBn9zSsW37ZEzQIWBQHz5pxuea33UMLzaVKWbhTpfuAIt77jrv3dUmeuR/FQ9wjQCQ+YEk8R1Xu+0pPT1P30M6/e0W2EZiQ4eom5KRyf69hqfwPb5wRWQLrbfMYrdQptMkcNgkoisjOSfFCGnh3glA2ferYMN0/5+isZmfE5B0t3rORMevH2BssyFh3s6lgDnMd1dETEtxXQtuoaFZzIE6cn8UWe1342pNVgSqbFkgS6DTBWg8IT1x2dyDrCAp1JW/rsH0Qur78Qy4F0lDu2FugrGAJL7/q6idcRNKqLLdXoOYrnN/rPyD1Ds2F63560ZNnrEmwlSQPSvwkBRTvU9SbpCPvPugOFadoKeQTPZ1vxL8aXqYfYpi7/faR+hYbLgpKoaQPqQTjY/TYLIQggKSvlMti4xj16Bd9W7g9qHherczl0cWG+k21IZmLNtqBI6I5UHLJD1vB6BearMbsn96ADemPVPgCQKKa+kwegkwKlH+cjCRDxQNyk5KzBy+jdN4UoYxoeZ7+7mTbDTO6fPEwDOXuxaScNY6qa0pA+MB3T tcqI2qZi 4yWY8tZCuPVVbn0me7HT36ZSI898e6nhEfc/9H9ZuUkXyEYJ/CVtJWgdIEgWXP+7Ln6ZoE82CpYFCp9a3/BLHgaCbSo59Kk1Gp5H9gte68M/WkVs2oV91arjbPw9MCd/pR1nj2fzxTzwJ7UtRozbiHBzKcn/JZqF930HWTjF3BTqeuiNw4cXT2mUsliuMfn+sPXMUec7G4g4ZCHF5iIfyf6cXwUP4Mr8g52gGvJRxpp2zgHN5cGNvtES0TMTUHVe3/TUitlzoTUZEMCWuLtdFKz5ShsnyAVbySRrCA7+m8RWDZR5ieIVWZeKM+t0Mrw13GZgVCd2zoxMYF8yJ6ramIR1gbo8g2DPpEoCatX38G5O+R8u5/cgU6iw0jRE7QOga11HC69Cx2JvQ3sDJtWCqUch+ItVNTUoZtSSTU6cIutHrlGi6FRNCM6Bd0al1kGhjDpR2yj9cL8SiMO8xCSVmgxKvrg== 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: List-Subscribe: List-Unsubscribe: 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 Tue Oct 24 08:32: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: 13434040 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 730C9C07545 for ; Tue, 24 Oct 2023 08:33:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 12BE36B01A3; Tue, 24 Oct 2023 04:33:53 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0B5856B01A4; Tue, 24 Oct 2023 04:33:53 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E71A66B01A5; Tue, 24 Oct 2023 04:33:52 -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 CFEC46B01A3 for ; Tue, 24 Oct 2023 04:33:52 -0400 (EDT) Received: from smtpin24.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id A0A13140E71 for ; Tue, 24 Oct 2023 08:33:52 +0000 (UTC) X-FDA: 81379691904.24.6924D19 Received: from mail-pf1-f179.google.com (mail-pf1-f179.google.com [209.85.210.179]) by imf24.hostedemail.com (Postfix) with ESMTP id D28A1180006 for ; Tue, 24 Oct 2023 08:33:50 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=eIvWP2R5; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf24.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1698136430; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=R/yo1rd1hMhsSjZF13O+yDvfO0lhQRWl28rGn2KkzN8n8ii4o0enRj1ngNEzbmzL3uONq5 c0J1gQrfsOdDnYMqL5Pb4wtbRW/Hl08l90tAPbkRKW6Iabd0rtE/AphAAKafGVI+mue1kN qcFBI7GBJU05Bvxf6bElbc1nz/QbP84= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=eIvWP2R5; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf24.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.179 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136430; a=rsa-sha256; cv=none; b=LzdUQaUDk5m6scJCdseyIaz6ZxYmMmtAoAqda/MWFaLJpOPZoTV/y699xKOqZrDT94xodn PM+K3YL6twnU+WCM7Tbrf9g0rRD1a/2zLUa9ibmgY54Foe8+I5y+SpgdfAUrirxQKmy4tR cOl+0cZFw9e9OKsODS6UPh3IFrJVmBY= Received: by mail-pf1-f179.google.com with SMTP id d2e1a72fcca58-6b77ab73c6fso3055137b3a.1 for ; Tue, 24 Oct 2023 01:33:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136430; x=1698741230; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=eIvWP2R5GFg23PKpQMt/tCqFdilyKkGl6A9yrCxz7be0+I7WLR/dUfMqyfa4Iqx4Q7 dXF0slWiYtEjhH/OowytcE2ZMLVyCoNhb9bMRpC8k4XAlwg71HVRL5AWPd3t/dE966VA PB4rC6/r+WOmAddxKS56qDjqpDTc8vloExqiNrjLnD6z3RiEI/1rklagN/zTyk5iS20y QRknQIxvj7O9uzEBtcWq+OS8L/6lHimWlTQB2b0ywlOE0hfS3umZUdbkAwWO5n1UNCAm /o2BQvxONR9E+8InyMqFGjpIfIPKHqvWveYcUYzQAJ3+IsUrjtchHtrQk/wN+qsnFEQp ljoA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136430; x=1698741230; 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=mFyp/FJQdSo4OvDS2koRMpNI0AcMCWskpm09jBYSG+0=; b=XAPeXXcpAIzM1sk/W7wRcDmXAYBHPaZUrKuM0CJBASNZp7l/PQ/QGI3Mcl7vjduAfU AADCgkOj3E6RM8rnJWTjYMOmjmdQI3wSsvhZgqSp6xM6zrqsXPiPaZmKOjNxcLEZY/MF iQao2ozUjnD/zgJrp0Z4W/wGjhv8J1GTLf7+jdAIdZSWHnS8DzJgWAuN7IuyG9ySeUaO Vw40DpR0sJtFvZFSpRI4jtozPD+QJry5YoxkB+9JWpjg4ha1u3/5V8oONtwNIrnLfOA/ VdlkSZ/gJ0Exfhb24oAZdgV7ATZ5iGTmCv2PkndYSfv9ObYnFavfbc5Id4Nk1gNcKIji sETQ== X-Gm-Message-State: AOJu0YxDJxeHvnXDAlalzxDd3AiL10KK6/MkvSiF2YgbzfFVyN9xJRta VkA75m8XBTeH+kp2mLEilWCtew== X-Google-Smtp-Source: AGHT+IFGRqPLSl0xQjtZhF9R2vYQNinwziWDialz1aZ2psT6bnUbvTADzmyVrOS+Nnq8WOBVXot69w== X-Received: by 2002:aa7:8885:0:b0:68e:2c2a:5172 with SMTP id z5-20020aa78885000000b0068e2c2a5172mr16021661pfe.6.1698136429778; Tue, 24 Oct 2023 01:33:49 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.43 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:49 -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, mst@redhat.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 v6 06/10] maple_tree: Update the documentation of maple tree Date: Tue, 24 Oct 2023 16:32:54 +0800 Message-Id: <20231024083258.65750-7-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: D28A1180006 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: z1doof17z3k3ytfkfki9ohtbtm36u63w X-HE-Tag: 1698136430-727317 X-HE-Meta: U2FsdGVkX1/Srojmt7r32zPQ6iUIAVSyqn44wt7EN3gEFQ0hYj0Qkt3pV98lLvkp1LCn64yN54MHNu8jcTDtvkqIFsgxZD/lpsjE+I7KBjMgXI+J16JMHxEpUyOOxamN8XldR7venzWYxk1AimW91oztqIfkMczzGrcGye4id9eIW41mFNv8Mnu0Hbmrq5aB4/uG4qhBTRawNkYT0UQ1IVlqYudffojI+XQnQhktGV/v46BBrlRs5dN6bGT3D4Mw96wcfxaOX5qcOxWuJDyncDo7pbi4f02om3j2kfy6uBWKSk7lFxYF4cfyh0rdysuuNpghbpvFjbRB46ZNfWebvREIp2QEfeYwhRevwqSlnPS+KCPv0/7Z71CP9/55/CQWDuemdUMF+MpgEcD+BGWEyErh+QXxakQRgpj6UM86/3xyXbKsV4/ZKB64lsesORl3GrGh39OhkkFHV+Ys0FrETzMDOuObrovXOwoLMXIJkjeKIptFQBe+jKsqcVaiMfRAO8cZ0mXW3K4TCFqL3KmLsmDdDvhVepyty3jP2cNIuFw5nhWvnma6Oi6IALlrI818isAu2vNTW1TiLCSnjI814AHDKugMHl8T2Xi2FsDINJala9GdhUPtz97BDDuysj72FTfL1mxWhIMxWdBtwMyTkGx8doyp/amGmU9b7ESkSljzG4WvUavO17/NAAaLBConSZHn3VoNhOxJkmYbYNgkphtd9McEqebhQczKmdAjAYFfS5TaeUFO6kM074HAQo+Fi2kT5mPp4kWqCoK5B9UVN601nLfFvKJRtRI3LqNEgPRTfzjmhqUdhW/re3dkQ+mGFP3w6XpERWN3+1J5MpiJi9wn83LieAKI2QpKAT7gtohrOHzQ+N3WlNTJwHs6WZikNm8nMxSxTbrXM+M0Acio44CJIejz67PjaV30IDDhkGSBc1HMx/2LOq84Wik70FX4r6ebs/mubYBjy3m9c/S ZCBEjmgy NOzjKPpTqQ8fnwle0Qv/VyY79J5TS1Y+2w/pjAZ+XizvI3FaFwkiAPYLl90CYsuOx3DCwupsWQN2aYB/uvRmZkCPHJbFQyIAn0RazpH7sX90+w0YUcLjU9Rc0wxuusT49A6qXJFYH6pxKTQfsg6KFifvgqeumQFG0PTkpoOUR49AvOJAPCpChfmlSxzmh1Ra7fpjwM8C9DI6/52b3ZbuJsXiMHTxSsNjoCpEN9WnWuz1XRheX7PAKy78XwOGMSY2cQzTTv6f3GpBvwEHor8eUWbA5iOO/YbFsuNQnhpxMK79O7mYurhId6fLdP3QqbhHVfRa8TLFZT5WwsJfPp0zU4t+aqqZy5aBtiJbTFthZ0y2Jo/a5ynn30LJZiJVXCOFL7+McvBkxVICGLhjbVQ1aBRXchcyCDGFDZbYA70XtSKIvwbJPsNwi9LFiOTGFwpA7Yp41mqnRBWiHerOp78zB6jmcCQ== 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: List-Subscribe: List-Unsubscribe: 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..285e2d2b21ae 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 entire maple 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 Tue Oct 24 08:32:55 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13434041 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 14C15C00A8F for ; Tue, 24 Oct 2023 08:34:00 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A554F6B01A5; Tue, 24 Oct 2023 04:33:59 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 9DD556B01A6; Tue, 24 Oct 2023 04:33:59 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 87F216B01A7; Tue, 24 Oct 2023 04:33:59 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 723D66B01A5 for ; Tue, 24 Oct 2023 04:33:59 -0400 (EDT) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id 465E7120279 for ; Tue, 24 Oct 2023 08:33:59 +0000 (UTC) X-FDA: 81379692198.29.8DE7300 Received: from mail-pg1-f175.google.com (mail-pg1-f175.google.com [209.85.215.175]) by imf20.hostedemail.com (Postfix) with ESMTP id 6F4B41C000C for ; Tue, 24 Oct 2023 08:33:57 +0000 (UTC) Authentication-Results: imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="InKBAy/Z"; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.175 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136437; a=rsa-sha256; cv=none; b=1lsyf3PwRGJWDPv047SioRPVhxcpcotZ/v7PwlcBkwqfn8KeMTyw4sI+aLBucUibNpg780 Vzrz+tAO4BGO/D6olQPswPBXGNWaTz06o+05CCs21C3c+OHBAa0E5PNSgbEhR+/ktTKLRa Sh6HxEbSAkLbn1XVUeb44s5IgRjLK0k= ARC-Authentication-Results: i=1; imf20.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b="InKBAy/Z"; spf=pass (imf20.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.215.175 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=1698136437; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=btzWJkDt/sXWoM1oXiL6nb1Jx/Gt9cecfiPwyLhry8Z4mwF1wNtX6a3DhXEYR2CXzpKjmW EATVBolKP0gMHr6fIBbtLrMLFBShyc7VDI5BcSonDunu8KNHkIy31yghRnLHFoOsW3Jupm iTF0lsBD6R45b50ueQgf+gwb4VEWV3E= Received: by mail-pg1-f175.google.com with SMTP id 41be03b00d2f7-5a1d89ff4b9so2314196a12.0 for ; Tue, 24 Oct 2023 01:33:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136436; x=1698741236; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=InKBAy/ZmMDZu1Mg/v8UME1fHUaFt5pVctojr/YDmAR7YAqz68JM+RYWHXwhO1cryO Tqtir38yszjnIxtfvTxDvS6LBIolDQy1eiGXuWLhmpi37V5DGJMlSmyrmNNX+U3ku9qV GOXzRpxXDPDba4mk8V0Y0psaFjxHa3Nor5egjEa00G2Mdlp9JX03xcwq7D3z820pSZsW zt5oRYLV3VniULvVUJ4MntES26n9wqi+qJ9UseNZHAXZoX14v4pXIiZQ2GlPNTDGs/k3 qvhwsEr2ELPOQRn3uuNA5BFJsENNzLzFRJR8N1cG+tCVXMMWIJwDxSs5xKeFL92Hbpot R9Aw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136436; x=1698741236; 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=QmT9t2gNl7JC/Wj/BeBLe/fYUtz3EaMSD0bTELVUlD4=; b=OsOddeUqiZQ++b2kUX6ufU1lnwCW74bsnPaWnHHZo/evjNu5FKvchDJTKlvJXvcvFh Ct3ZSO4NJ17HqGJYX1XEErFS71fHuTZXfuHNaDKMIzh6856FtQtzkbBOvwre4fyeUz4C Ga8uqHFYU2Zw60DTirz1xPee6jPOQK1saX7WHva6Mg8mMALdEi91AQX0MjFQtYwK4kZ5 L2E7CY4D+H1FyeXdAMFFr/LomrdxQVLO4AUehU51wAmsIELnAbRZsOfMhSia95R5Tit8 /X3tBUA2UNwjDVmlHW31TmTkWB2qGidK7qTUgvXl3Jdtg8KaWOZEe17c3aVEjpgAXbKM Ctdg== X-Gm-Message-State: AOJu0YxpLE8SBEfszsG3aNkI7n2flkSFookPtA25YDNl7MeVYQ+ICvs4 j7qsGDdNWbFzfErVXniwyDNNAg== X-Google-Smtp-Source: AGHT+IF878eTLhy6MBaFtUQubSuP7YPQ3APPj4js3z/kylyjvhAgv4iCwOSuEsZvOnsr4GHMJn44lw== X-Received: by 2002:a05:6a20:6a28:b0:161:28e0:9abd with SMTP id p40-20020a056a206a2800b0016128e09abdmr2218020pzk.16.1698136436387; Tue, 24 Oct 2023 01:33:56 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.50 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:33:56 -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, mst@redhat.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 v6 07/10] maple_tree: Skip other tests when BENCH is enabled Date: Tue, 24 Oct 2023 16:32:55 +0800 Message-Id: <20231024083258.65750-8-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 6F4B41C000C X-Stat-Signature: uh1robcc9gsmrj744h9x3rzr78wp7rta X-Rspam-User: X-HE-Tag: 1698136437-652017 X-HE-Meta: U2FsdGVkX1/jNbA4kfNQzUWNyegUbF4kpIWGWafHZgoE1jfdufDaMo6qmvSS+AldhNr1brsmR86RD7VY1F4QungxcrP58u1S7U9/IMlmkNtp+XOxQMMIaIwK0mBKPciumH1zYrRVIXhFc9P2xtW7hLLw6RvduVS/w5UloSfTjWouuv2RECfo3S9Hyfz3/qZWpv6b3LcfWL+TSRPtESdyGeGPx5U2quN3hOl2NAXaKmhaagrJcEYiSiVz3SNLrQNYgtU6Bl6F8q3hk8O/Xud6ONYeOG9HTcJBi2pSZeAmBGL2N2k89e5h93G5UqK/GjNgkupV4wLorex5zi3KGeIlkFDMZ4V4q5RMYXERw9X2xzSZKIUczZmNqrntscoMez/lekiDfNd4Gt7F3SFlf4AbYelG5BAOAx+glYHRYbG5kpG5Fjm/0JV0b6w71nYNzE2g69mzHq/pI3gvhIPD/Y/YOsb48HOHkBIp7EIxypGRDvnN81tKLDdGQPqvj9a11vZ1FCuZNrZp994S2OAuwEvYHqTSC6b5KVnrq6gVd9yTV5wzI+ExCMZ3F3agpemqXpRWs15pGL6YRyW4Lk3XaPBS7wXfpbUPiT6BwZPQQV1ZKGuqwfxdYdBeGWOq19cwItk++WHdufePWADx3IenVj636V1uCSGTdAD39rjSNzCx30gadF9y9LSUds0PrIZDWVvLRsy1XSQUDeL6ua/GzplungXUswYdcOvHYqfrUOrEQOIQqvIiHq/Po/f/+e4erkZB+xK1gynUc7hFTtLTRGRcDPjEnoNIqgeCmGPpn5P6yT2Ma5TVFYvDwDZp6Jsbl+opyardoBpptN+mRxM+rWGn8YRYxbrnjq/4SU8YrpaFg3vcydLySnn1l7tdOh8nT8z2k386NekKK5fJC09y775LObhHkqZNFnAOadgLt2/uvqA7kWr/LArsojMMb0v/I5/9gSDUwFp1H2ZqWDYFNRr GCOdtPOl Acv/2vTkK1sdnM08NqubLW7a9A+z5acR3ABSBaeLKuaJEBMJwh2kvP2e9g5Wjen11MexbofwVTK4720h+FOv6k0a4QY1QiDM4hixYHd2Na4rkOVyOcxnviIO5+GcdpHL26qhpjWVclFK2ISF5/cod01EYXxyIM5XgI5Q6bXSpcgDZw6U/sA6ZDM5BdogZJU7kNmvoVXEPrqvlPGjlpNcf7BW3rkNc1vrlA8FR5MHa2rgjrx2mnEFpaK1EWGEUeJ5OuC9GDSzqlhDJzmRiII0gZ2vOT2GhWoOB7FJ/UrR+nh3bnT5ubRDx75mzjiwILijT+bCyWiWEivOg3WY2MXtsJ19PlV/HsrEs3/McT8dN9zs2+ctkt7yjj1643uJo2gjlXeccpVdltM58FeeMo+wDxUcKE3OQhFHNA2hhg3ktsQLAEgxzhMpsEJ1qVSAfGRgxc34Dixku8Cpmb3F/v/bFpLTsfQ== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000001, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 464eeb90d5ad..de470950714f 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3585,10 +3585,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); @@ -3646,6 +3642,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 Tue Oct 24 08:32:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13434042 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 7B3D0C00A8F for ; Tue, 24 Oct 2023 08:34:06 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1A4776B01A7; Tue, 24 Oct 2023 04:34:06 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 12B406B01A8; Tue, 24 Oct 2023 04:34:06 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id EE68A6B01A9; Tue, 24 Oct 2023 04:34:05 -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 DB42E6B01A7 for ; Tue, 24 Oct 2023 04:34:05 -0400 (EDT) Received: from smtpin16.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id BC07FB6204 for ; Tue, 24 Oct 2023 08:34:05 +0000 (UTC) X-FDA: 81379692450.16.6297C06 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) by imf09.hostedemail.com (Postfix) with ESMTP id EF2DA140008 for ; Tue, 24 Oct 2023 08:34:03 +0000 (UTC) Authentication-Results: imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Lwd93EhB; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.170 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=1698136444; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=QwqsKLAiMvomAN0vTsqdIWiPf38jtNbDJ2kONRioKd787l7hJlbCs1PsVJguaQhFwxYWNh haKkLzjToLv1jeakrsS/Ho6tyb/TUcMK8PUqGkaAHGxzEzDV9piBakuQ+CC0KLNUz2bvBp bLxZzd+J0GWDY/a4izDNw6k9Z0JOVCg= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136444; a=rsa-sha256; cv=none; b=sfu3nl2UlvKYF/HKceed4SenbXoA2XRwEIyekBBOidGXpcukogE0RSopq/7Y4D2V+7thJJ 0zSO3k6PWfilGRS4mZm0f1VbxhZEAUEGHMX3PftN9Qq9F8QMMGln1CU0tfmej/iyQXtbAy YXPU3ytAIXx+e5W9HDITM8YyrMBEVV0= ARC-Authentication-Results: i=1; imf09.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=Lwd93EhB; spf=pass (imf09.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.170 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=quarantine) header.from=bytedance.com Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-6b3c2607d9bso3468859b3a.1 for ; Tue, 24 Oct 2023 01:34:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136443; x=1698741243; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=Lwd93EhBwTRM/N5sMbIpi9y6kTgVYv+9amz8yRDLdmhVxYHNgMwUoRfqd/5QYtRhud eE+LSNGE/ffYWh4ZXjRzai1EheZ+LbmgOUUnXB90ylzyMbW6WoM31i3a5ioV1TLz1JI4 HOG5S+Rehp9ZfFas+QpV/ROne/9nZxqforJADHu6mXOPZpeJrjm4pfQXglX+G1aiaGAS Y2ZKrT+bcM+OIXvpO6s8BSXDQ2dpX1MhVYX3GqRG1z+ScIarIiCFA462u9n21h0fVa6e zuWYdk8lSd/o79rmsB15ov9O2st0mWkeasPjitRR2tw5FMZo1LVDGLFh7WET9mTJ1tTq l+Aw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136443; x=1698741243; 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=dqxLSD3NSY9H2G/bHFoEqq0XRO6Fu01n0ZJ8sfPfXdw=; b=F9+Jeg1GvikJAgXdSfPcHjguB6auHL2WKTW21podgzeJYDWbktz1Fjpru7GzHHqi9t TzYB9RFCXf7wOO0gew3eRO/uNb1gKrLtR56zCrTFChEzR30h5or3PlAH1oMx6uEj5cPg ielhgCsBob5g4Gx7z1v8Esp8Eh6Wam8AcaV6FOs5GUTflL74z0yijnNc3eJGSGmxfa4M GPhmo4dhTyrrw5p42/T7gp1YJMK7IGvRRJu6kfJ98xUMtOMizaXcGXeg1utVAobiM1Wg j3K6G2u7ahHvyqbQOlw0k2EbL8V7EDPcu85b6Scu5sIy9sds+NH5RJH3Bf5Qr021DKdl x2IA== X-Gm-Message-State: AOJu0Yy2quyt7WJr9rcB2UNIMfkZKXWOFRv+asVrqV8YHstU4wIJWfR9 oxygDlzv8QRJ3VX4BX7RWqX1RA== X-Google-Smtp-Source: AGHT+IF1zVX8K4BNNs+Nh2lZHYWJzbNrBQiw86QsHKAu8PhANHP4KGmdCF4Yx599tMqieIVTxj5igQ== X-Received: by 2002:a05:6a21:7189:b0:17b:4b61:a907 with SMTP id wq9-20020a056a21718900b0017b4b61a907mr1679463pzb.50.1698136442907; Tue, 24 Oct 2023 01:34:02 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.33.56 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:02 -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, mst@redhat.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 v6 08/10] maple_tree: Update check_forking() and bench_forking() Date: Tue, 24 Oct 2023 16:32:56 +0800 Message-Id: <20231024083258.65750-9-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: EF2DA140008 X-Rspam-User: X-Stat-Signature: j5bjc837fbm8f59pqfrcrbjzts3rqzj6 X-Rspamd-Server: rspam03 X-HE-Tag: 1698136443-959779 X-HE-Meta: U2FsdGVkX1/Gp2dF/cFLRTtIQPf+27vN7+uWfrqN7jn3aIRdjrxP76Px0MwJiXSFECFcvwN/vZn5Oijp5Aw+5+7wXhAKTfuvtWPzWFecc7NX8RoNbayZevP+42wbFPJnsQ7uIzbv/MDLlhcK73hScIAdwoHX9YCcA3DB1XAEbj8V5p5exf6JG1cvxRVJGh1ARspWRIi8YkaOZWRO+7+c6SB/pZFt0ccia1IDkr8YeZHuqd53wqAiRqEe8W/vdLFnle21uVVqBu5BIYYEz28LeYFblJzIqs9sgs0wVpmpFoSzfuqre/HHcYNP7mMEn0gp4t5KzgRRUWLsIejmUcuIUA5Ss+g5tEK+//1IjyuW/UOsweD+7mwkYjcRBul7IQb8F1PStKOfP2HDeF3XHI/Kszctu5oiScfp41p7Wl2ZXviAKYfCyJZ+U8xkn4m0vjtha6snbX/yZmfUi7g+CGK21UDtBLgw9BQM7QZ3JEkk3wS6MIKqfNOgVMOpwSkzrhe4ob93YR89eIFnkdHgmZe6Y59kwejuAmikkgHlViWUYkoJegbYOqHhtDN0opQyst0JnyhyIk1iIOTCafl7LcDF1wK7k92yxUcgaTr5Nh1o/CXQD4UI1I3Ty+TYhn8E6VapksFsy+v2JxyqGVfyXaRk5iHsJ/RiH8qoIMvOd4gGdBNlxza/Q3vQrlcdROkhJpbJwbHgWaYDLXTSs+8QBwIcmejTwnm78Em+u5I0IG0UwJk6UKpoeFmh0Jvwj1GYToMfL5ivde2fh5GsaxmzeUrtaYmYLw8HT4uSRjyitfO5wD5Mj7S+4iFJNx4RAORz9v+pmzl2e+c99IqiWdDZRgkDLCp3tm5z6ASRt21zVMQ9vc1pVly2yX6KdegJmOF8d8BgufjB07f/k1Pp2ORpA07ldzlVx5lQYFsXWT9CCxvRwa9oW+kwL1KJtgQwmdI10rfUNjn7RVbECVov3EJObas jmdk72OT O3dnQc6nQXU+d+B5YatMR3ZE65chANGdD1e41NZmUB50Rgff4iudZfjVV9Jfnl5G/P0+RYBZcxRkBMVFnGKaAPX69C3+TSsnrXzuZDUqMU0W4pOp6FGBbjtR9i/q6/WMWTTGWlT9w8Rto4Iqtn9FPTRR8d46jkIWxOFYcpJbYfexE8cN+Dq2t/x3DkRk23ayfU4JPI31MMqZ5m9KQJyGMv4dsfVFMqq/tmVMDuH8iUlVsCiRWflFC8PkrFkbql/VC+bDGvpiIFa/gOVUSpNPBTTij0m5WLEM4aqGl6TKqPV36g0mUNmkgRz7eITFwJUe2pgRlYT+XCwZ1ffLkNDFWR6poHPxD7gGhuxUkusdH2mL8GNlHjPOXVguskKkZ/EKLTyLdVPFh6dNbussE909D/51JqedHQsQA/emmQ/wz7wKH5h4EpkerWSOF+LHNnBGB7DQV1HdHtjsEkoqSQTwTl1+WSA== 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: List-Subscribe: List-Unsubscribe: Updated check_forking() and bench_forking() to use __mt_dup() to duplicate maple tree. Signed-off-by: Peng Zhang --- lib/test_maple_tree.c | 117 ++++++++++++++++++------------------ tools/include/linux/rwsem.h | 4 ++ 2 files changed, 62 insertions(+), 59 deletions(-) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index de470950714f..3e4597fb49d3 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1834,47 +1834,48 @@ static noinline void __init bench_mas_prev(struct maple_tree *mt) } #endif /* check_forking - simulate the kernel forking sequence with the tree. */ -static noinline void __init check_forking(struct maple_tree *mt) +static noinline void __init check_forking(void) { - - struct maple_tree newmt; - int i, nr_entries = 134; + struct maple_tree mt, newmt; + int i, nr_entries = 134, ret; void *val; - MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); - for (i = 0; i <= nr_entries; i++) - mtree_store_range(mt, i*10, i*10 + 5, - xa_mk_value(i), GFP_KERNEL); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); - mt_set_non_kernel(99999); mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); mt_set_external_lock(&newmt, &newmt_lock); - newmas.tree = &newmt; - mas_reset(&newmas); - mas_reset(&mas); - down_write(&newmt_lock); - mas.index = 0; - mas.last = 0; - if (mas_expected_entries(&newmas, nr_entries)) { + + down_write(&mt_lock); + for (i = 0; i <= nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret = __mt_dup(&mt, &newmt, GFP_KERNEL); + 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_destroy(&mas); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); + __mt_destroy(&mt); up_write(&newmt_lock); + up_write(&mt_lock); } static noinline void __init check_iteration(struct maple_tree *mt) @@ -1977,49 +1978,51 @@ 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) +static noinline void __init bench_forking(void) { - - struct maple_tree newmt; - int i, nr_entries = 134, nr_fork = 80000; + struct maple_tree mt, newmt; + int i, nr_entries = 134, nr_fork = 80000, ret; void *val; - MA_STATE(mas, mt, 0, 0); - MA_STATE(newmas, mt, 0, 0); - struct rw_semaphore newmt_lock; + MA_STATE(mas, &mt, 0, 0); + MA_STATE(newmas, &newmt, 0, 0); + struct rw_semaphore mt_lock, newmt_lock; + init_rwsem(&mt_lock); init_rwsem(&newmt_lock); - mt_set_external_lock(&newmt, &newmt_lock); - for (i = 0; i <= nr_entries; i++) - mtree_store_range(mt, i*10, i*10 + 5, - xa_mk_value(i), GFP_KERNEL); + mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&mt, &mt_lock); + + down_write(&mt_lock); + for (i = 0; i <= nr_entries; i++) { + mas_set_range(&mas, i*10, i*10 + 5); + mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL); + } 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(); - down_write(&newmt_lock); - if (mas_expected_entries(&newmas, nr_entries)) { - printk("OOM!"); + mt_init_flags(&newmt, + MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN); + mt_set_external_lock(&newmt, &newmt_lock); + + down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING); + ret = __mt_dup(&mt, &newmt, GFP_KERNEL); + 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); - rcu_read_unlock(); mt_validate(&newmt); - mt_set_non_kernel(0); __mt_destroy(&newmt); up_write(&newmt_lock); } + mas_destroy(&mas); + __mt_destroy(&mt); + up_write(&mt_lock); } #endif @@ -3615,9 +3618,7 @@ static int __init maple_tree_seed(void) #endif #if defined(BENCH_FORK) #define BENCH - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - bench_forking(&tree); - mtree_destroy(&tree); + bench_forking(); goto skip; #endif #if defined(BENCH_MT_FOR_EACH) @@ -3650,9 +3651,7 @@ static int __init maple_tree_seed(void) check_iteration(&tree); mtree_destroy(&tree); - mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); - check_forking(&tree); - mtree_destroy(&tree); + check_forking(); mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_mas_store_gfp(&tree); diff --git a/tools/include/linux/rwsem.h b/tools/include/linux/rwsem.h index 83971b3cbfce..f8bffd4a987c 100644 --- a/tools/include/linux/rwsem.h +++ b/tools/include/linux/rwsem.h @@ -37,4 +37,8 @@ static inline int up_write(struct rw_semaphore *sem) { return pthread_rwlock_unlock(&sem->lock); } + +#define down_read_nested(sem, subclass) down_read(sem) +#define down_write_nested(sem, subclass) down_write(sem) + #endif /* _TOOLS_RWSEM_H */ From patchwork Tue Oct 24 08:32:57 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13434043 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 1D785C25B48 for ; Tue, 24 Oct 2023 08:34:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AA3076B01A9; Tue, 24 Oct 2023 04:34:12 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A2C896B01AA; Tue, 24 Oct 2023 04:34:12 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8A6406B01AB; Tue, 24 Oct 2023 04:34:12 -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 7562E6B01A9 for ; Tue, 24 Oct 2023 04:34:12 -0400 (EDT) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 54D9540DFE for ; Tue, 24 Oct 2023 08:34:12 +0000 (UTC) X-FDA: 81379692744.25.B917513 Received: from mail-oo1-f44.google.com (mail-oo1-f44.google.com [209.85.161.44]) by imf04.hostedemail.com (Postfix) with ESMTP id 861674000E for ; Tue, 24 Oct 2023 08:34:10 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ZsgSwtKu; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf04.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.44 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=1698136450; 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; b=cFr0Jk/m0ahaTlieUWIvp/HYNIfJF3cDIhmU0p4VOymBH/1VDobGE2mhjzWE5if5E15rCT FdA1JOd81Gd9mGvMYTC1cAdGVidILjbgZOxGcX/xhbJ/i7Dni4m1aUcAo14hAAVez3xiU9 NjZLIZ2EuJmx/csBipVRx1jt9ELS3DI= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=ZsgSwtKu; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf04.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.161.44 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136450; a=rsa-sha256; cv=none; b=CmzOuQAeoQC33A1RUZDKeGBu4hzh+wj6ALo/JcGqikZGFCfQ4EhDIZRPA4FGjNg3Cn0qSb Tjb5VRIeL+YSVYrWwpVObcTVwovhc2fLHuGEPsjOJOviyMkrj+AnyrZbGl08tNQ1AsO+Op ErbBqRwnM/UiZR0RuG6B3Pry4CALW20= Received: by mail-oo1-f44.google.com with SMTP id 006d021491bc7-5849fc56c62so1102739eaf.3 for ; Tue, 24 Oct 2023 01:34:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136449; x=1698741249; 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; b=ZsgSwtKuS73ekDR6zVLPXWXN/TL4H5UT1xUedpMdjKJd2oZlxWOBmhkEBQw6jQjW/Z nn8+MGenltJokjTg/jjcmqpCTSLPq92ezbphIiwfutgMEhrgXF27ZGtcz/qCovVgGnnP x+xGp5B5OmErTqrmaLeMf0iVZAU3xIgQU4CS7YYhK+bylqSVSsdWzjwzr4cpJ4EDjt6b MyEt9ikpUx7sX7/mTl6In1jh5U+Z3XKCb2ycPHu4T4GdBBzAqf+RSK6RgkoXIFrGDVhO ihIGyNVGM78ic0ZiCrExQ8cVxFklFVMoChKAZMdJfvDk4tM6swHJm9M4nLrGnEr+2vW4 gQUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136449; x=1698741249; 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=bzccM6C4HLhaCIv/SAdijHFdTidMSXBWQyZ1w5RDJYw=; b=GG/+cb6S818xDRnHXm48UCS2T54M9HSJXFMiimuz/uyBuD8bpICFGb+Tx+YnhRRipW cSIz7RfXNJVSpJlqCGixG9yS2uZKwSbkMYsGeKWVQMZxC8HVH5U+Og88p1vJZt0qPZyT pXzdZj7VUsCaApZA0GgUSRFfpSLbNDsZgca/2oujWwVJUghIV5aWQSvnYdBX/J7oh9JO ujpWmDCa8RZBbHCbISIKNtOyOb0YHcjg/SpjFzhIH+abqR0KXCYCGYrjKRpMTBq51ZWW jG0fyjByGOb869ERQQrH2lNpx3BiAnPKD1RMBhmTiiUJoQELRVsFU8NUPytUgYOeZ5Lg 2H0g== X-Gm-Message-State: AOJu0YxAnB8qdTix7N3v8b9a7h4bSODRqdwJOTYcFkkGyr1U9f4VbWaa t4zldx2rWSgO9Mzx/ISmUSQLpA== X-Google-Smtp-Source: AGHT+IFL9wgTTdwcf5iN1EU6ZDwg7/3PqxSbUY7aeR+GMticX3N3Q7oIRaxH4CtsM5Y8o0vT2v0b1Q== X-Received: by 2002:a05:6358:810c:b0:168:d6cd:7b2e with SMTP id p12-20020a056358810c00b00168d6cd7b2emr7924030rwk.29.1698136449463; Tue, 24 Oct 2023 01:34:09 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.34.03 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:09 -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, mst@redhat.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 v6 09/10] maple_tree: Preserve the tree attributes when destroying maple tree Date: Tue, 24 Oct 2023 16:32:57 +0800 Message-Id: <20231024083258.65750-10-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspamd-Queue-Id: 861674000E X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: dh9m7gi5ua8r47fomm6y9noh1jq84frz X-HE-Tag: 1698136450-659578 X-HE-Meta: U2FsdGVkX19xuozDhoI47poYn9z5rVIs9rTK/eo+tdiIUF907sDUNYtg5TUPF5aLnQifllY0wFqbTuI59txoOUzi4LdboSIXWb8M1tkdJvruNSpmoXy0hNTttZRNTnpnpzBGINTpYM09ONNHn+ueiBXUFJjuyZnIaR9/5HqS9zG24iq1kWfU1EPJiXlOt8rJEh4S06BAFwzkVQwhSstLNaj9+1EcmkaUxQy4R3drWeP+HyaTqZeT93e+cWPMLr6vhaCSKwqegOd4ocToVA3nKqesV39+916REcHBZWDsc+zL7k6F6PM+0aQefjPpgNz/4hkLiC9Smz1nJa9SyxjakzN7XHVTN+o6y3eVEOW8vAttVLLzOW416EfOF5c5PxklMiigx4WfI1JjI+xB9RGuKMr+m/fNtnliasGx2fCVvDfT/t6sIYAttCrpKox6+supNW482iQeBhK+Z0pq3vNZdpVSjrRajhkCBG8YvmUuF4UyW8lI8p/jRfR7hO/OClqGTVSLRl9bKBXovGv7EWdxbpUgZQv0KJ8aqj4iZvtiHWW4vjDT+1eYx0qjeIjwumThAHyL4GWX7dFCE+tT9ns9cKxHyo+q9cMvUGZOGHOS+FteRnIqWOm1z/VYQbsluqBpH6zILI5nYavMrdlsSRShFtuoaL2+fBcdsh9EZskxsBkyubrLdbNXIaCfoURMal83lS4WyFpjTje8ouSogomIra+LCuwLGec0ZO0yfWmOoOqNAVtv4fcDZMrBZ2rZ1oQ+db6mTJHpCdWAyRFFTph/vhHX+vGBkq5X3WfQVMYRii345bi+XYrs57E1PjxwAYrOC9YB9SA4byrhZGHgIpfGnDaXEtSwkj5nX7SECpfNGV7TumHyA3+gKWoRxx2bXCYBGSlf+XSc7CBJuIgv3WSvsLqXQkYhY/wgXoOGhprQaxaw0VjY1ZEUrhAOZLFJ+9hJl0Fu/GcjJfY2UiNwg5K NGEJzTYL jY74C48hEOEJrsL6nPI1wIBYZcrx+WwkePThuq24DCl/BceIVBA4wZ9VyVZgUT/H0MyOOOAJl7AODUEcsEIlcbi7cBfDSHc5iPlTXBPPWByRQ0cuPO1O9GzpwttkLe68nk6YSG9ba2q1Nbg3FOiSJyU3C+fHVOWwvjtK6euQgiWrZPNHDaXfQ/lmLQQz1MsJr3oOMpFBd0vbRQ3ZopKz1/jWehu4p0sE6ca0pYiBbYX/e6zdlp+tyW31T30r5eDu3JghHWDpA7B2zhWKMAXeDVY/clBTQ8NrIfKuwz4uM+MlsuErJ7cqERCfuw6KxeMATNDvl5pWJNx6i504sTs2mBc0guAoDjwPH3jD3hJcrvkTS1SjztQV/nnEHB5jsbH8C3sQ1NvIOv3/AIsaGR/7gDI1H1+YhDfHbui6QUf1keCi79M0Xt4wLsAeckPnfa1tf1OIyNhZ3ajQ58MJ/eKm4BeM/pQ== 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: List-Subscribe: List-Unsubscribe: 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 6704b5c507b2..b9e238e7a7af 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6765,7 +6765,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 Tue Oct 24 08:32:58 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13434044 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 1E790C00A8F for ; Tue, 24 Oct 2023 08:34:20 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B17686B01AB; Tue, 24 Oct 2023 04:34:19 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id AA1D76B01AE; Tue, 24 Oct 2023 04:34:19 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 91A746B01B1; Tue, 24 Oct 2023 04:34:19 -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 7E7046B01AB for ; Tue, 24 Oct 2023 04:34:19 -0400 (EDT) Received: from smtpin01.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 606291A0E45 for ; Tue, 24 Oct 2023 08:34:19 +0000 (UTC) X-FDA: 81379693038.01.FF3E9CE Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) by imf14.hostedemail.com (Postfix) with ESMTP id 886D010002D for ; Tue, 24 Oct 2023 08:34:17 +0000 (UTC) Authentication-Results: imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=GnL2azD4; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.172 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=1698136457; 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; b=m0pYnyu586dz5ceHJ+mS3lTx48Rk7kby6hw7eQGdUizH5t3afBT5KwzRKeakJCVpNMM6P+ KWK5oMlOMSJGcgEGrMlTLO7YwXt1YWQeUBt+ET4qVHUHkUl55AyBqCDekwGZ004BQqa65W AZm2IjLDrmEFjlMenc05m4P9LBluJnU= ARC-Authentication-Results: i=1; imf14.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=GnL2azD4; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf14.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.172 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1698136457; a=rsa-sha256; cv=none; b=Yvs0pudrH03+SvD3P6bu9vLAkvzOcC6dE6JwfkW3SqeRNOko+rPYUus948st5EyrzqKfia 0+hSduYiK2rT+u3zj6lZlF168dEHLdRQXTRyizMEVOtxmBv7yKeqv6ME87HsSMlN69ufOt uF3VGBOjjxRkcOWHsdTkrgYYZL3RlR0= Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-6b89ab5ddb7so4180725b3a.0 for ; Tue, 24 Oct 2023 01:34:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1698136456; x=1698741256; 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; b=GnL2azD46ppTj88YVMqxIJ0LX6MS1LhMYH0nTlrFQClCOFLYoQogekF5rm0tHwbgam /ZTDLvjiKA+M3eEj9avUc6gEJi8x/kfA+wBCMLD3VbpCXi63zkSb92rnFTdGIz3V53tj +nXHCVMDdWhcUnwrQIkj0IgOBfqhPxbgpm5kf9tSF8VdfN7nCZQyFiEPgTaLOc7rzK83 KXn2K7upmbvc/bLZ2SkUrA51bgrEDh5ZaRwXgYxFnBNPzyFZByQQk2uzWa8JEVOguW8X owgzNiWAmYwgZJkMTlDYzDf9eX5fvj7P1rKrcZiOM8vqVd9gxFXnak0RoUzOviraKiEq g4MA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698136456; x=1698741256; 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=NhuvPcTMRDCD3VOBYhVRa0kZDnR2cgXp2fXq7JVV3pE=; b=G1UNtmQ2m3tGDzF1YJI+ItnRutvuKQ6Ao5shanGFoDE9w/6ZrEIwYNuqii/enzpbrj o8DfnSpclXEEu+8DwdbeOFiPkNLk/zYP3iTteYf7bDnOVumMqiSBB5gIBROn6kLH42Ky yAc02FnEysjEgCaJKr/r5XWRyQku4ltUSps4EHAAZUKepqr6LcL3RO9eEMw6zOA2EvVn 5jf3Tqs+xY8wrcySbufkw8eSE2uXLcJ/7xx8KHGeBO7vSTUe368jvkDNyyf6/89suXGz KNyj1XGyHUkC1jiHYiC0zzPh69TSwdGwbDlpT4mEtxaXlKaVuwQpPRyelos8o+ofL7tT k/wg== X-Gm-Message-State: AOJu0YyxlrUlmqqdqS4bNjl/oSeDX08oOY+aPYnzhP3DBlKGZbmNLcPB bOkru3BmuS4m34HxsQaGotiu1Q== X-Google-Smtp-Source: AGHT+IE1bFuZc+mJSxD+pVgtIXeCVNo3r5g8GwiOKV1aPw1h19MOC16mxaJFq0Q2g2TOYWxaSa9TjA== X-Received: by 2002:a05:6a00:c8b:b0:6be:5a1a:3bb8 with SMTP id a11-20020a056a000c8b00b006be5a1a3bb8mr14049796pfv.28.1698136456363; Tue, 24 Oct 2023 01:34:16 -0700 (PDT) Received: from GL4FX4PXWL.bytedance.net ([203.208.167.147]) by smtp.gmail.com with ESMTPSA id y21-20020aa79af5000000b0068be348e35fsm7236977pfp.166.2023.10.24.01.34.09 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 24 Oct 2023 01:34:16 -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, mst@redhat.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 v6 10/10] fork: Use __mt_dup() to duplicate maple tree in dup_mmap() Date: Tue, 24 Oct 2023 16:32:58 +0800 Message-Id: <20231024083258.65750-11-zhangpeng.00@bytedance.com> X-Mailer: git-send-email 2.39.3 (Apple Git-145) In-Reply-To: <20231024083258.65750-1-zhangpeng.00@bytedance.com> References: <20231024083258.65750-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 X-Rspam-User: X-Stat-Signature: jtri86mnmrhxe79r85936hmhqgyxdp61 X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: 886D010002D X-HE-Tag: 1698136457-848681 X-HE-Meta: U2FsdGVkX1/KZWMK4He+9qD2bjQl1kq4Bp4Yzq0TVcQPfnZ8GQYwrVTLDfQiBak/utNN9rtUEMcUD+M36v9X8WVNEj8JtI3ygr7IbQiZvw1zm6TrZS3FXQrvJkCsiUPGkTJkHpFnWajJmM9d9Wih54MLIflJf5AFKffXE2pdUbbJN23aI62esWvYJ4ACsUwtHS+Pabyokr/FOpFVliv5PUxGIMGYfm7G2EJ3b2zNeapctXyRkXzTzJAHZS715JU4zaIVw44FBL85CdIm1nldyK/5fu8N+lVFxvc7gkLeAsvVJjHypAiUt803TIBuHvmSLEKvwggyNrKRDwOXi96vKC+Af9vWbxlAHxZGzIG6/Oyx/YSpbO8GC125HQxYz8PLm4/qDGNb49SFFgsEOlE8fuOhVQjJvlyG1L2jz6KZ3icLZaZN8Z+E/EEZahOWyl+Qmx+TC64OjRUyqIbkHXBuUPkg3M/B2NSEYyAHSPAdPXWRozn834VJD3EqZOYnudrXIP3uAGBGMFvkVTqZ0hTAioLHj4/ATlWQKalyMesNDumclPn8KbXY64TEJtYjmx7GWh80axjsm2ZG9iq88N6iUQbX0iorctEq/HYmPpDsWPMIHLH4FSbXwgc/iKcMrxHnTwQimq1H3gcgIa3q5jm+5ehZrFRXXbbEV9r942AEnoHt6W1HaoJmu3jaW+kw4yImZWGhFmhX2477NJVo3fwK2hFyBMuIVCjlmJyAPcfTMlimeXuFLzMp/n8YWkSO7R9blwrZHjC6oFilgIEl2s9m+gUp1FjKG9uT4h+Q3l6ojk1yUuAgXqr9z+v4fB3ZbUefGsVCGmlSAFHGqydjdOCO4AXvBrt9ExfN0keo4wfIezeBgM8nY5TKVCdw77SAdN1d9+ZIdOQ3H/OErhFg/7IYTrMokmDxYZmvw6LTNjdRLnrOf8dYTJAB2wpUs/p2fcucHKigMDTYif8NCoBf0aC kBPlHm2q vmruyt6rnJh0407WfomuTRPf5FY8Lv4TBcHFEMmVz3exWVyw0Dv58DXD/W+NuSR7/4OcuGgqinylCSSNXTFQvoVV02Ftrb9Fd14vHPurpy1W2mH8xLAT0o3GykmJCAnIpnh/Sp12BGWVgPY90JDzANNu6IsD4Noh3a27bWQm32FM4xesm6xqKnHKJgz37BetFov7R8xdjCLgwGpohSGr8Nl4EFcWwg38wv0DKLb0lhf+0cBdcp7boKydqEmpu4NQp+JiPVIjb/LJF+aOx93Md2kanwimbEZ8YN3dbrnddoanIu9ABjNzD6QCYsKQxqM4fUCTW+KiRB0gDWwRD7Lzfh/UknMkVdi1/0TjQCVErf9PgJubAPZCziv4dCH1YMYgPOnohnD/dVMrCiNEUfdVZA6mMgyZjZM0Y45SnqWV67naWvO7A3iw+CdtDUIStDEJeK0Gq9f5egj63dIZVtltLARgZGPTh3uglEOwGTXWqmmkDyAPis4vdKLMATv5f70GeU8qf8FUZCmvbzm8BzXFowKKn8TrkkFisuFOgpWNgifEExrQstyNrWhsfWK+kTkP9EaH/ 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: List-Subscribe: List-Unsubscribe: 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 efficient. The average time complexity of __mt_dup() is O(n), where n is the number of VMAs. The proof of the time complexity is provided in the commit log that introduces __mt_dup(). After duplicating the maple tree, each element is traversed and replaced (ignoring the cases of deletion, which are rare). Since it is only a replacement operation for each element, this process is also O(n). Analyzing the exact time complexity of the previous algorithm is challenging because each insertion can involve appending to a node, pushing data to adjacent nodes, or even splitting nodes. The frequency of each action is difficult to calculate. The worst-case scenario for a single insertion is when the tree undergoes splitting at every level. If we consider each insertion as the worst-case scenario, we can determine that the upper bound of the time complexity is O(n*log(n)), although this is a loose upper bound. However, based on the test data, it appears that the actual time complexity is likely to be O(n). 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. To handle this, we mark the failure point with XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, stop releasing VMAs that have not been duplicated after this point. 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. The first row shows the number of VMAs. The second and third rows show the number of fork() calls per ten seconds, corresponding to next-20231006 and the this patchset, respectively. 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. 21 121 221 421 821 1621 3221 6421 12821 25621 51221 112100 76261 54227 34035 20195 11112 6017 3161 1606 802 393 114558 83067 65008 45824 28751 16072 8922 4747 2436 1233 599 2.19% 8.92% 19.88% 34.64% 42.37% 44.64% 48.28% 50.17% 51.68% 53.74% 52.42% [1] https://github.com/kdlucas/byte-unixbench/tree/master Signed-off-by: Peng Zhang Suggested-by: Liam R. Howlett --- include/linux/mm.h | 11 +++++++++++ kernel/fork.c | 40 +++++++++++++++++++++++++++++----------- mm/internal.h | 11 ----------- mm/memory.c | 7 ++++++- mm/mmap.c | 9 ++++++--- 5 files changed, 52 insertions(+), 26 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 14d5aaff96d0..e9111ec5808c 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -996,6 +996,17 @@ static inline int vma_iter_bulk_alloc(struct vma_iterator *vmi, return mas_expected_entries(&vmi->mas, count); } +static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, + unsigned long start, unsigned long end, gfp_t gfp) +{ + __mas_set_range(&vmi->mas, start, end - 1); + mas_store_gfp(&vmi->mas, NULL, gfp); + if (unlikely(mas_is_err(&vmi->mas))) + return -ENOMEM; + + return 0; +} + /* Free any unused preallocations */ static inline void vma_iter_free(struct vma_iterator *vmi) { diff --git a/kernel/fork.c b/kernel/fork.c index 1e6c656e0857..1552ee66517b 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,22 @@ 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) { + retval = vma_iter_clear_gfp(&vmi, mpnt->vm_start, + mpnt->vm_end, GFP_KERNEL); + if (retval) + goto loop_out; + vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt)); continue; } @@ -749,9 +754,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. + */ + vma_iter_bulk_store(&vmi, tmp); mm->map_count++; if (!(tmp->vm_flags & VM_WIPEONFORK)) @@ -760,15 +767,28 @@ 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 (!retval) { mt_set_in_rcu(vmi.mas.tree); + } else if (mpnt) { + /* + * The entire maple tree has already been duplicated. If the + * mmap duplication fails, mark the failure point with + * XA_ZERO_ENTRY. In exit_mmap(), if this marker is encountered, + * stop releasing VMAs that have not been duplicated after this + * point. + */ + mas_set_range(&vmi.mas, mpnt->vm_start, mpnt->vm_end - 1); + mas_store(&vmi.mas, XA_ZERO_ENTRY); + } out: mmap_write_unlock(mm); flush_tlb_mm(oldmm); @@ -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/internal.h b/mm/internal.h index b52a526d239d..1825c3b2e15c 100644 --- a/mm/internal.h +++ b/mm/internal.h @@ -1154,17 +1154,6 @@ static inline void vma_iter_clear(struct vma_iterator *vmi) mas_store_prealloc(&vmi->mas, NULL); } -static inline int vma_iter_clear_gfp(struct vma_iterator *vmi, - unsigned long start, unsigned long end, gfp_t gfp) -{ - __mas_set_range(&vmi->mas, start, end - 1); - mas_store_gfp(&vmi->mas, NULL, gfp); - if (unlikely(mas_is_err(&vmi->mas))) - return -ENOMEM; - - return 0; -} - static inline struct vm_area_struct *vma_iter_load(struct vma_iterator *vmi) { return mas_walk(&vmi->mas); diff --git a/mm/memory.c b/mm/memory.c index 4f0dfbd5e4bf..163d8f09dafc 100644 --- a/mm/memory.c +++ b/mm/memory.c @@ -374,6 +374,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, * be 0. This will underflow and is okay. */ next = mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next = NULL; /* * Hide vma from rmap and truncate_pagecache before freeing @@ -395,6 +397,8 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas, && !is_vm_hugetlb_page(next)) { vma = next; next = mas_find(mas, ceiling - 1); + if (unlikely(xa_is_zero(next))) + next = NULL; if (mm_wr_locked) vma_start_write(vma); unlink_anon_vmas(vma); @@ -1743,7 +1747,8 @@ void unmap_vmas(struct mmu_gather *tlb, struct ma_state *mas, unmap_single_vma(tlb, vma, start, end, &details, mm_wr_locked); hugetlb_zap_end(vma, &details); - } while ((vma = mas_find(mas, tree_end - 1)) != NULL); + vma = mas_find(mas, tree_end - 1); + } while (vma && likely(!xa_is_zero(vma))); mmu_notifier_invalidate_range_end(&range); } diff --git a/mm/mmap.c b/mm/mmap.c index 8b57e42fd980..9d9f124ef38b 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -3300,10 +3300,11 @@ void exit_mmap(struct mm_struct *mm) arch_exit_mmap(mm); vma = mas_find(&mas, ULONG_MAX); - if (!vma) { + if (!vma || unlikely(xa_is_zero(vma))) { /* Can happen if dup_mmap() received an OOM */ mmap_read_unlock(mm); - return; + mmap_write_lock(mm); + goto destroy; } lru_add_drain(); @@ -3338,11 +3339,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); + } while (vma && likely(!xa_is_zero(vma))); BUG_ON(count != mm->map_count); trace_exit_mmap(mm); +destroy: __mt_destroy(&mm->mm_mt); mmap_write_unlock(mm); vm_unacct_memory(nr_accounted);