From patchwork Thu Feb 27 20:48:18 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13995206 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 7C182C1B087 for ; Thu, 27 Feb 2025 20:48:35 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A517D6B0082; Thu, 27 Feb 2025 15:48:34 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 98B516B0083; Thu, 27 Feb 2025 15:48:34 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 82E336B0085; Thu, 27 Feb 2025 15:48:34 -0500 (EST) 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 647626B0082 for ; Thu, 27 Feb 2025 15:48:34 -0500 (EST) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 20574160D9D for ; Thu, 27 Feb 2025 20:48:34 +0000 (UTC) X-FDA: 83166912948.25.C62364A Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf10.hostedemail.com (Postfix) with ESMTP id F1654C0012 for ; Thu, 27 Feb 2025 20:48:31 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=ohjIdKOS; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf10.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740689312; a=rsa-sha256; cv=none; b=mFc+gU9Wk9DXCzcn1fMDV8z7e1MXTA8AvEuT410rba1dea9miQz55uNNlGNb5vCn5YolKS 2QZ5JGrt00ou99IZzlJCoKUQiSOzlLvS1WQ0i2GbQDeVs4yahx1U59gj9qA8urTHXQSHBP UQ6WBKWFPpnczIU3Kmqlpg1seMYDWDo= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=ohjIdKOS; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf10.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740689312; 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=yx9M9UzqVwml5F8oWQIucj2N+1y3Ei0ljrqvD/e/T2I=; b=NXEQaUVlzsJaIqjvDD4Vxv6w3NsiuNpRVJjDlDGcqdrJv53b1VJ+0+rbyMec1XFRD/08pW TrwilyiFJdcZZ7rh6/DlLDo1FQn0OQqHoXZoz5hR1DIibIX9halQGLS2I7TTAjqyHg6SWw +f83zRg4DN5/tKEcjVKKInD2nUksZAk= Received: from pps.filterd (m0246629.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJiZYW016085; Thu, 27 Feb 2025 20:48:30 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=yx9M9 UzqVwml5F8oWQIucj2N+1y3Ei0ljrqvD/e/T2I=; b=ohjIdKOSsQO1tLIu9nnUn xhgz+qtJjumTeG7E97FFyIDHSheCZCosT9pJDQBx9QT2e8pKJdseL6qr+iKcWz91 BPe7G2kZHuixpGiy3WnAWOCU39AuSEtEqTNPP9ND+zlyFzFB6JvRsbbctA6ulJbQ SsWtyHBtdPUoIaQNLig6Ttulx5f7Y0/MF6pSuKFjasnfuV1M3v4x29U97FXcsaaT PICh7HFsKGHN5INARpHAADFydfV8PxQBtsujVGtT12IiuboViS2uqpNGew9qgyqY V7DvHb3I5CfO9s+4ONbApCrG2UeqoyUS/LPoiwOgH8Mj8rvm0cbFQS5aVOjVDJny Q== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 451psf49kw-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:29 +0000 (GMT) Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJHgQa012657; Thu, 27 Feb 2025 20:48:29 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 44y51dws08-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:29 +0000 Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51RKhrve030883; Thu, 27 Feb 2025 20:48:28 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 44y51dwrvc-2; Thu, 27 Feb 2025 20:48:28 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, richard.weiyang@gmail.com, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v3 1/6] maple_tree: convert mas_prealloc_calc() to take in a maple write state Date: Thu, 27 Feb 2025 20:48:18 +0000 Message-ID: <20250227204823.758784-2-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250227204823.758784-1-sidhartha.kumar@oracle.com> References: <20250227204823.758784-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-02-27_07,2025-02-27_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502270154 X-Proofpoint-ORIG-GUID: 3MQcGoUFxweh2jMn3Ee8qzJHIvxipMUo X-Proofpoint-GUID: 3MQcGoUFxweh2jMn3Ee8qzJHIvxipMUo X-Rspamd-Queue-Id: F1654C0012 X-Stat-Signature: 5nxpcpyab7eey4xh64t6r9xurh1e7u89 X-Rspam-User: X-Rspamd-Server: rspam05 X-HE-Tag: 1740689311-432675 X-HE-Meta: U2FsdGVkX1/rehTcdE6+DP0e5UgFUu3Aw1/AJP0nhXah6GnbC1rKNKbtp8tZezKZTj4hmZmTKXxMP5uLQLsBCrHmgV+960nKz8FX76Cwtqv8TqLM9JVWoSG/Dvjm8zYtaqqfBQPxtFdjwV8SdiTeHVE61IMPGRadLkiFthNbnFaXyQvTBAtGFrbIXLKI7augGKVh1aZiM9V/WK9qQsDDqnn+xi9sobis7o7Ji1RE3+l7e9ljmH3LiZaBC5O3zueclnzgMjyiOaAoPcnNhdu/fahvvSB/tBRkGisiZeLsbuJvA3YALAcg32RJswk0K28ctksLrs4yUT1Tl2wFwYGvgC8WCuQku5AIL+Oc9sw0OryB7NNJPr7PNCjZ3B9PtXaQ9R+MWGtuFLPPlh4C27Kee6Tun47ZU5b1sGK/lNkrIV3JuoyLe9Gg7vp8gf33Q+xeU0kFT48lUv3Je/29ir68HuBJV9d7iqGuTcXwHlHsJqWbsuUZXP4BtI0qcXT3WAiJuRitCUP0THzsXfsFkFg0l3MhwOWejLaC7kQ2Hx79WX1qUQ7xuJqh7ui1dMPZ6bNnzuyZq2n6DPbF5CQrHlrMjCeCHHoE50gu6IIPPiUWZ4mE6t7JTCZocaClaQgMPf0s8jZm5DKX4ER90hMacylsQBevYQbyqzW07Yu+GdqS8GTjbUu/ZZXUb9wxplTw0EEKxjQYTr7aqwnReBOT4urK5o2XIad/AzhTQioMUzKS2LRKw1V3w/T/LBebi3TbRvu4r2e8sMXWGHczlEpamxxBf7pnaX3L4hk+9rgKtf/nbZumuTzMd6KIh9YVZHhPecQlHpHpnVy4cPyEI0VfAo7ViWy0G89SSsaUa/Bg8KqOjpLtnNYT9GJajw/9NTYKRpqYJBloO5eJ90yatilsAvygMuB1u4xhFTPFa5+EQur4uNF+iYTf/qJbHc2nOYGKTm0Ufrhjg0G39BsJUMEK+eW XReJIfud AT1kOaeXtzpZ2149IlfI7bnFLGdGReWslN8oj9Tq2dbYH9mwRE0ANBGhyrFbU8holPz0d/pMxrJR6nkhO0Vxv2rl4jR3TD5EXOZXY/JSgfiVAFvqbI1IgFpZIVl3y37kM/kTphudmcUpbzS3LbvdNW+DCgF2457XU3eSB3PS3TtFcm1oeXTUX6qM0V3CmSlAmmcS9RIz7UTd/d9jSEfC8GRec0mgtH6qeFsm2a+xWlsdwy+cpBUNtvsRI5Wm/8S1BqogPOcPgYZIvxnQbiwUpwmhToUpy/0K6BazrAfqYzzVfcccUXZFN5o3N/7n1TXdW9c11ew1Vw67vyIoHMvHh+K+nOhhxLwOtT2R1 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 a subsequent patch, mas_prealloc_calc() will need to access fields only in the ma_wr_state. Convert the function to take in a ma_wr_state and modify all callers. There is no functional change. Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 42c65974a56c..0410e13a099e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4144,13 +4144,14 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) /** * mas_prealloc_calc() - Calculate number of nodes needed for a * given store oepration - * @mas: The maple state + * @wr_mas: The maple write state * @entry: The entry to store into the tree * * Return: Number of nodes required for preallocation. */ -static inline int mas_prealloc_calc(struct ma_state *mas, void *entry) +static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) { + struct ma_state *mas = wr_mas->mas; int ret = mas_mt_height(mas) * 3 + 1; switch (mas->store_type) { @@ -4247,16 +4248,15 @@ static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas) */ static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry) { - struct ma_state *mas = wr_mas->mas; int request; mas_wr_prealloc_setup(wr_mas); - mas->store_type = mas_wr_store_type(wr_mas); - request = mas_prealloc_calc(mas, entry); + wr_mas->mas->store_type = mas_wr_store_type(wr_mas); + request = mas_prealloc_calc(wr_mas, entry); if (!request) return; - mas_node_count(mas, request); + mas_node_count(wr_mas->mas, request); } /** @@ -5401,7 +5401,7 @@ void *mas_store(struct ma_state *mas, void *entry) return wr_mas.content; } - request = mas_prealloc_calc(mas, entry); + request = mas_prealloc_calc(&wr_mas, entry); if (!request) goto store; @@ -5498,7 +5498,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) mas_wr_prealloc_setup(&wr_mas); mas->store_type = mas_wr_store_type(&wr_mas); - request = mas_prealloc_calc(mas, entry); + request = mas_prealloc_calc(&wr_mas, entry); if (!request) return ret; From patchwork Thu Feb 27 20:48:19 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13995207 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 31795C197BF for ; Thu, 27 Feb 2025 20:48:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 856206B0085; Thu, 27 Feb 2025 15:48:36 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 7900A6B0088; Thu, 27 Feb 2025 15:48:36 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 5E4436B0089; Thu, 27 Feb 2025 15:48:36 -0500 (EST) 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 350A16B0085 for ; Thu, 27 Feb 2025 15:48:36 -0500 (EST) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 8865C1CBE4E for ; Thu, 27 Feb 2025 20:48:35 +0000 (UTC) X-FDA: 83166912990.09.15932F8 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf04.hostedemail.com (Postfix) with ESMTP id 7728A40003 for ; Thu, 27 Feb 2025 20:48:33 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=ahKBFIdD; spf=pass (imf04.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740689313; 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=gOwuzuTOLUCNwJAMPht/sO46yRRy3GRTeMgEldjsPnU=; b=u/N7asRw8qkG3lpQwVYuZli5gL1GJQS/3fu4LnkdfhODLU52LJJN0TI0Q/m+dplUKyujxf Icbpnah3+12/I3M3nWsDmIq6K1/5DxSwYnE/tIR3hHXZ5Go3H6SQDLMraNeJxMtgtF7XEq TCEkNkJ7cYvLPanRj5WBbtJZikWWO6s= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=ahKBFIdD; spf=pass (imf04.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740689313; a=rsa-sha256; cv=none; b=XWlRwcMOPwHPxy2Zg7FQs3R2loVBaIEOdtyfICxcACyoX2/We2Hufnh/jEAuzriVof3kc1 n4EQsiB0BWEy36IZK382/bo5oQgFktv8gwBDRizf4jQF/W3/9fT5m7QjFt1qhNog0EB0lA EjYfQY2WTkdrbJw1gkSGgYrHqHnxkx0= Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJiXvx016378; Thu, 27 Feb 2025 20:48:31 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=gOwuz uTOLUCNwJAMPht/sO46yRRy3GRTeMgEldjsPnU=; b=ahKBFIdDqMDUr0McX+3EF ZxhSy0tY5rvY2X7vdmD4Go02lQKuNCU/uVAeU63f1IJHaEXTHKIte2izLECE8bnC 04An58Q9qRXiXxPc5sxe2TbCFjve3FSRdliNI3DK8DMX4HVhzxLQEChTXVaZAFb7 HPBWl9hO1k2N+BjutKb/AL+tGKUNn4/1oIoH6LpGJmuCf/CyT+y+CDWP1FEs8n4u 1Rd7Dl3R+s/LmHkxpvYC+kAgYJvKv3uYnHkX+OYff8TnFsZrGj43SVpuD2WF3qUs UItQ8eSBrXov9Li3LjZW21s/wAoq2bxWG8uLb1cay6MTp3uNEN6yK0WZX8/B7JhP w== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 451psecbj7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:31 +0000 (GMT) Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJ30w5012629; Thu, 27 Feb 2025 20:48:30 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 44y51dws1q-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:30 +0000 Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51RKhrvg030883; Thu, 27 Feb 2025 20:48:30 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 44y51dwrvc-3; Thu, 27 Feb 2025 20:48:30 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, richard.weiyang@gmail.com, Sidhartha Kumar Subject: [PATCH v3 2/6] maple_tree: use height and depth consistently Date: Thu, 27 Feb 2025 20:48:19 +0000 Message-ID: <20250227204823.758784-3-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250227204823.758784-1-sidhartha.kumar@oracle.com> References: <20250227204823.758784-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-02-27_07,2025-02-27_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502270154 X-Proofpoint-GUID: l6ABSd6hzPhnG4lAK7HrR1bf2g6TVq8x X-Proofpoint-ORIG-GUID: l6ABSd6hzPhnG4lAK7HrR1bf2g6TVq8x X-Stat-Signature: 1m9nty6unqb165mdqw7ayrxkcdth6j3f X-Rspamd-Queue-Id: 7728A40003 X-Rspamd-Server: rspam06 X-Rspam-User: X-HE-Tag: 1740689313-197195 X-HE-Meta: U2FsdGVkX1+Rtz4Z1Xu131tVnIFvp37JSdvOYhJRUKnvOenCt3+f53Y6Tk8Fkm2hXow46UWnZ4fKakGHBEwyRLhf1iNz332/7cn03Hpp4+iCl6lB9s1Ykiqi+L/wfmjkW09SrsxLqbFuYFxklpMkn5+nyyUtduAC8HkI1GAfVhwYkahO6IBn/vZC3WWlRVwrAlRZsPmxoAk/Ii0ik92H5KHPy4fAwMpXwfhnwSlfb+HT3KEeBQ11qDoz1h9A4e+QyeZ5a6Yw53TL9AGAQJ8WUSJ5tDRh4GEDqfeHA33k8pKuht7xhcWCSRA3FdjZndB81+VB9q91FmNm479t2ikhDFFsJVLdjbdObmyWZeqpo0uglJIjeRjAwaZi0ocC5SOoBJPqywGacghFih0dhUv6xrJ72lvz3YaErjaG8Ctkvv7SzpFtvG4qxDBZTQR3FrxOn0AoZ4WDAbL/Q1JLXI4YPYGEYuII2aQWGPKtFMTueHMouO7Reh+NhJxdLQBWs1vKsTcLA07qWt7ImFNFnOMQiG8IttO+1B2XkdKkg/O2vC7NJGlMdot5D8yUOUA5SWIrpJPvQ4y7Tc+AcsXGowa0cNrlBBVRPCvqVKE7GjolS8vpRez+p9nAvA31XBP8FtL6i92cOqjhS0DM+h3xSVHJIO7JLuvejWX8TstzkRmd9CMGdDoq2/UYD5CRM1uNrlKtga/srJIuWx6nMnk4kQ3SkvPvfW5LKHuS7XWs+w29Q7vRsk7vy0GurUWN5i3bDvLA3tZ6fqwk9eZmqskQIHXZPoTa5HfsMvOig4+y5wmMeMGXdvQjJrSttZ3N8OZg4RISNELHg5LGJIImZIKXcMxvQVZKRvfXVlMQ3ZmT1tk1Z7QK4gcFSkXMejxIL/oQxKfVsU9OR+4Zrcd9E3E4Eu9eCT+kXttB7fvbF9cQwhrb3j7XP5pm97u1crIH9m2cqe1ZZw09oV6cRDIrgV0/f9T 2AW/7UUG +Ys7R4md5+9ZMl5xhG8Tk+g4Z1Kwth1++a4cDHHfgNH0RI+FcmA7E/z/FtPu5b2Y2hhiZ4t3UvH8taIpF6BmdZYCWGSBe0ibATqf6p7SYsm4WgPk2XeheecOy7q9HRQ+yY0WoU0W9gRgKc1QnqVVI79vc6CiUSH4f3M6mwErt08SgluwycsLIBFh/pNiWUxgs3Es1JiERVOQCFAcuz+88+7OGGLcuOIqmq4L6k8+m5yBjM4aG1OiEsEeOhTmhr7BfcrwIOdEGSjL3M/wDN8QSoQkYNocTC1UB/siF09KlFyUk6XgvVcIBzqPYlW+qxpPmk1EvgOKh9ciLv174TcQ24tffpVzRcfqS5Gbp 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: For the maple tree, the root node is defined to have a depth of 0 with a height of 1. Each level down from the node, these values are incremented by 1. Various code paths define a root with depth 1 which is inconsisent with the definition. Modify the code to be consistent with this definition. Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 85 ++++++++++++++++++++++++++---------------------- 1 file changed, 46 insertions(+), 39 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0410e13a099e..a37837d6f3eb 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -211,14 +211,14 @@ static void ma_free_rcu(struct maple_node *node) call_rcu(&node->rcu, mt_free_rcu); } -static void mas_set_height(struct ma_state *mas) +static void mt_set_height(struct maple_tree *mt, unsigned char height) { - unsigned int new_flags = mas->tree->ma_flags; + unsigned int new_flags = mt->ma_flags; new_flags &= ~MT_FLAGS_HEIGHT_MASK; - MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX); - new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET; - mas->tree->ma_flags = new_flags; + MT_BUG_ON(mt, height > MAPLE_HEIGHT_MAX); + new_flags |= height << MT_FLAGS_HEIGHT_OFFSET; + mt->ma_flags = new_flags; } static unsigned int mas_mt_height(struct ma_state *mas) @@ -1375,7 +1375,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) root = mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { - mas->depth = 1; + mas->depth = 0; mas->status = ma_active; mas->node = mte_safe_root(root); mas->offset = 0; @@ -1716,9 +1716,10 @@ static inline void mas_adopt_children(struct ma_state *mas, * node as dead. * @mas: the maple state with the new node * @old_enode: The old maple encoded node to replace. + * @new_height: if we are inserting a root node, update the height of the tree */ static inline void mas_put_in_tree(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, char new_height) __must_hold(mas->tree->ma_lock) { unsigned char offset; @@ -1727,7 +1728,7 @@ static inline void mas_put_in_tree(struct ma_state *mas, if (mte_is_root(mas->node)) { mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas)); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - mas_set_height(mas); + mt_set_height(mas->tree, new_height); } else { offset = mte_parent_slot(mas->node); @@ -1745,12 +1746,13 @@ static inline void mas_put_in_tree(struct ma_state *mas, * the parent encoding to locate the maple node in the tree. * @mas: the ma_state with @mas->node pointing to the new node. * @old_enode: The old maple encoded node. + * @new_height: The new height of the tree as a result of the operation */ static inline void mas_replace_node(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, unsigned char new_height) __must_hold(mas->tree->ma_lock) { - mas_put_in_tree(mas, old_enode); + mas_put_in_tree(mas, old_enode, new_height); mas_free(mas, old_enode); } @@ -2540,10 +2542,11 @@ static inline void mas_topiary_node(struct ma_state *mas, * * @mas: The maple state pointing at the new data * @old_enode: The maple encoded node being replaced + * @new_height: The new height of the tree as a result of the operation * */ static inline void mas_topiary_replace(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, unsigned char new_height) { struct ma_state tmp[3], tmp_next[3]; MA_TOPIARY(subtrees, mas->tree); @@ -2551,7 +2554,7 @@ static inline void mas_topiary_replace(struct ma_state *mas, int i, n; /* Place data in tree & then mark node as old */ - mas_put_in_tree(mas, old_enode); + mas_put_in_tree(mas, old_enode, new_height); /* Update the parent pointers in the tree */ tmp[0] = *mas; @@ -2635,14 +2638,15 @@ static inline void mas_topiary_replace(struct ma_state *mas, * mas_wmb_replace() - Write memory barrier and replace * @mas: The maple state * @old_enode: The old maple encoded node that is being replaced. + * @new_height: The new height of the tree as a result of the operation * * Updates gap as necessary. */ static inline void mas_wmb_replace(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, unsigned char new_height) { /* Insert the new data in the tree */ - mas_topiary_replace(mas, old_enode); + mas_topiary_replace(mas, old_enode, new_height); if (mte_is_leaf(mas->node)) return; @@ -2828,6 +2832,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, { unsigned char split, mid_split; unsigned char slot = 0; + unsigned char new_height = 0; /* used if node is a new root */ struct maple_enode *left = NULL, *middle = NULL, *right = NULL; struct maple_enode *old_enode; @@ -2877,7 +2882,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, */ memset(mast->bn, 0, sizeof(struct maple_big_node)); mast->bn->type = mte_node_type(left); - l_mas.depth++; + new_height++; /* Root already stored in l->node. */ if (mas_is_root_limits(mast->l)) @@ -2901,8 +2906,10 @@ static void mas_spanning_rebalance(struct ma_state *mas, continue; /* May be a new root stored in mast->bn */ - if (mas_is_root_limits(mast->orig_l)) + if (mas_is_root_limits(mast->orig_l)) { + new_height++; break; + } mast_spanning_rebalance(mast); @@ -2913,7 +2920,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), mte_node_type(mast->orig_l->node)); - l_mas.depth++; + mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); mas_set_parent(mas, left, l_mas.node, slot); if (middle) @@ -2937,7 +2944,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, mas->min = l_mas.min; mas->max = l_mas.max; mas->offset = l_mas.offset; - mas_wmb_replace(mas, old_enode); + mas_wmb_replace(mas, old_enode, new_height); mtree_range_walk(mas); return; } @@ -3013,6 +3020,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end void __rcu **l_slots, **slots; unsigned long *l_pivs, *pivs, gap; bool in_rcu = mt_in_rcu(mas->tree); + unsigned char new_height = mas_mt_height(mas); MA_STATE(l_mas, mas->tree, mas->index, mas->last); @@ -3107,7 +3115,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end mas_ascend(mas); if (in_rcu) { - mas_replace_node(mas, old_eparent); + mas_replace_node(mas, old_eparent, new_height); mas_adopt_children(mas, mas->node); } @@ -3118,10 +3126,9 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end * mas_split_final_node() - Split the final node in a subtree operation. * @mast: the maple subtree state * @mas: The maple state - * @height: The height of the tree in case it's a new root. */ static inline void mas_split_final_node(struct maple_subtree_state *mast, - struct ma_state *mas, int height) + struct ma_state *mas) { struct maple_enode *ancestor; @@ -3130,7 +3137,6 @@ static inline void mas_split_final_node(struct maple_subtree_state *mast, mast->bn->type = maple_arange_64; else mast->bn->type = maple_range_64; - mas->depth = height; } /* * Only a single node is used here, could be root. @@ -3218,7 +3224,6 @@ static inline void mast_split_data(struct maple_subtree_state *mast, * mas_push_data() - Instead of splitting a node, it is beneficial to push the * data to the right or left node if there is room. * @mas: The maple state - * @height: The current height of the maple state * @mast: The maple subtree state * @left: Push left or not. * @@ -3226,8 +3231,8 @@ static inline void mast_split_data(struct maple_subtree_state *mast, * * Return: True if pushed, false otherwise. */ -static inline bool mas_push_data(struct ma_state *mas, int height, - struct maple_subtree_state *mast, bool left) +static inline bool mas_push_data(struct ma_state *mas, + struct maple_subtree_state *mast, bool left) { unsigned char slot_total = mast->bn->b_end; unsigned char end, space, split; @@ -3284,7 +3289,7 @@ static inline bool mas_push_data(struct ma_state *mas, int height, mast_split_data(mast, mas, split); mast_fill_bnode(mast, mas, 2); - mas_split_final_node(mast, mas, height + 1); + mas_split_final_node(mast, mas); return true; } @@ -3297,6 +3302,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) { struct maple_subtree_state mast; int height = 0; + unsigned int orig_height = mas_mt_height(mas); unsigned char mid_split, split = 0; struct maple_enode *old; @@ -3323,7 +3329,6 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); trace_ma_op(__func__, mas); - mas->depth = mas_mt_height(mas); mast.l = &l_mas; mast.r = &r_mas; @@ -3331,9 +3336,9 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) mast.orig_r = &prev_r_mas; mast.bn = b_node; - while (height++ <= mas->depth) { + while (height++ <= orig_height) { if (mt_slots[b_node->type] > b_node->b_end) { - mas_split_final_node(&mast, mas, height); + mas_split_final_node(&mast, mas); break; } @@ -3348,11 +3353,15 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) * is a significant savings. */ /* Try to push left. */ - if (mas_push_data(mas, height, &mast, true)) + if (mas_push_data(mas, &mast, true)) { + height++; break; + } /* Try to push right. */ - if (mas_push_data(mas, height, &mast, false)) + if (mas_push_data(mas, &mast, false)) { + height++; break; + } split = mab_calc_split(mas, b_node, &mid_split); mast_split_data(&mast, mas, split); @@ -3369,7 +3378,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) /* Set the original node as dead */ old = mas->node; mas->node = l_mas.node; - mas_wmb_replace(mas, old); + mas_wmb_replace(mas, old, height); mtree_range_walk(mas); return; } @@ -3428,8 +3437,7 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) if (mas->last != ULONG_MAX) pivots[++slot] = ULONG_MAX; - mas->depth = 1; - mas_set_height(mas); + mt_set_height(mas->tree, 1); ma_set_meta(node, maple_leaf_64, 0, slot); /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); @@ -3673,8 +3681,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry) WARN_ON_ONCE(mas->index || mas->last != ULONG_MAX); if (!entry) { - mas->depth = 0; - mas_set_height(mas); + mt_set_height(mas->tree, 0); rcu_assign_pointer(mas->tree->ma_root, entry); mas->status = ma_start; goto done; @@ -3688,8 +3695,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry) mas->status = ma_active; rcu_assign_pointer(slots[0], entry); pivots[0] = mas->last; - mas->depth = 1; - mas_set_height(mas); + mt_set_height(mas->tree, 1); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); done: @@ -3808,6 +3814,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas, struct maple_node reuse, *newnode; unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type]; bool in_rcu = mt_in_rcu(mas->tree); + unsigned char height = mas_mt_height(mas); if (mas->last == wr_mas->end_piv) offset_end++; /* don't copy this offset */ @@ -3864,7 +3871,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas, struct maple_enode *old_enode = mas->node; mas->node = mt_mk_node(newnode, wr_mas->type); - mas_replace_node(mas, old_enode); + mas_replace_node(mas, old_enode, height); } else { memcpy(wr_mas->node, newnode, sizeof(struct maple_node)); } From patchwork Thu Feb 27 20:48:20 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13995208 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 6FF80C19F32 for ; Thu, 27 Feb 2025 20:48:40 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2138C6B0088; Thu, 27 Feb 2025 15:48:37 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 1C6516B0089; Thu, 27 Feb 2025 15:48:37 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 016806B008A; Thu, 27 Feb 2025 15:48:36 -0500 (EST) 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 D58556B0088 for ; Thu, 27 Feb 2025 15:48:36 -0500 (EST) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id 9655051192 for ; Thu, 27 Feb 2025 20:48:36 +0000 (UTC) X-FDA: 83166913032.28.A38CFB5 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf30.hostedemail.com (Postfix) with ESMTP id 95CD880004 for ; Thu, 27 Feb 2025 20:48:34 +0000 (UTC) Authentication-Results: imf30.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=NxhDk4ts; spf=pass (imf30.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740689314; 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=9LL2P3OXGfVz0nnVa8W39TneCyQ10Aw4rLIk1Wd13bw=; b=V850ryk/Itp4i1v1MlQ7uovP1U8qDBM7Otd7oaBiRkxi9xmtBu0Ud7x6pVuatr3xaYg5Lb pxjOK6QVwRQ/AbyW2V/iNV1+J5TJe/uGyCRZcGvm7QDug8bC/vsY3jd5YyqZ3EjbtXg3Oi 3+26/Hrs9H/sHN1R+yMazq5zSmo7MTE= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740689314; a=rsa-sha256; cv=none; b=aLAErJJuDAn9DpNvMV4qechFdQFrdlZvAaqgwBHFik5m2aMnLbJUSmBdA3CsQc8kORsFdA 6S09CyhO4sJQRKJpvXmU2+M2cSRwzrPck2MJ8ejL4eljo7ivf3sKZt/AhhZIknhiD4ARCt i81MdPw+c0bOclESBuOyW59rLpvztYY= ARC-Authentication-Results: i=1; imf30.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=NxhDk4ts; spf=pass (imf30.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com Received: from pps.filterd (m0246631.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJivuU020031; Thu, 27 Feb 2025 20:48:33 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=9LL2P 3OXGfVz0nnVa8W39TneCyQ10Aw4rLIk1Wd13bw=; b=NxhDk4tsxMlSEelWIb2Z7 1+IimFvRIjSRcWPOE+ynJTEEXqhNnTTIOi+VNTRkX4EDrd2g3294n36/vEpu1Ron dhYJlVYOPwWMpuUAh07HQ6K6qUhzoaikXOs8AjRn994q26oK45w+Iqw6ncOnsnbC uGamtv/x0etKgwTKzQC4527leb7F3e2o4RvgFQID3GhhDp41Ygb5cUIaPVqC3jhQ TNYv9N5hFMyH8exswQPNP3EzVM0cw7MQHhjvlc3DP2OUCLXw+k0s6vWNUXgwsWx5 7ZyMCrjfalTrP8o7ZJ6qpAK5TvAEhSPJFNTLorfpXsDHJpisYTZtGWC1JThEjZAX Q== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 451pse4bch-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:33 +0000 (GMT) Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJ5gfs012575; Thu, 27 Feb 2025 20:48:32 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 44y51dws3e-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:32 +0000 Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51RKhrvi030883; Thu, 27 Feb 2025 20:48:31 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 44y51dwrvc-4; Thu, 27 Feb 2025 20:48:31 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, richard.weiyang@gmail.com, Sidhartha Kumar Subject: [PATCH v3 3/6] maple_tree: use vacant nodes to reduce worst case allocations Date: Thu, 27 Feb 2025 20:48:20 +0000 Message-ID: <20250227204823.758784-4-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250227204823.758784-1-sidhartha.kumar@oracle.com> References: <20250227204823.758784-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-02-27_07,2025-02-27_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502270154 X-Proofpoint-ORIG-GUID: HFRumWjksH2GrIpyFTFDyBAAQ3qLdNVH X-Proofpoint-GUID: HFRumWjksH2GrIpyFTFDyBAAQ3qLdNVH X-Stat-Signature: pmd9eo9o8c63s3u8usgqbtp5a9k95crf X-Rspamd-Queue-Id: 95CD880004 X-Rspam-User: X-Rspamd-Server: rspam01 X-HE-Tag: 1740689314-938122 X-HE-Meta: U2FsdGVkX1+UZ36jG+0+2T2s8zlkUN1p+TW11qDEPSCv7pjcrph41Djg7tm3Qs8/jC4VqjgW+NH97BTVY2AySY6wJKEJUEmlHVcrk2ZrbdHl4UuSdGofpdXphauXTscV6Q5hyktOlq+sj+5MpzysOcH9xAuvrbs4nTkM7G7noCgQbZb4Jln/daETHQ9pDbvdzDYRpHm69TjbYsLdLYd+HG8QJGaV7u9mtfumlKubeQB4KyxpTslM+ndzB1dN02Ddnlnz388iZR3DGIXYvEeiO3wx6qe4YHBHTb3bVxyzLGoDqhUtcc4+P2Dbo71UGh5ToWIZh8dPPjvKPoToe3vGfayYaD8sRf4BN6/qrBas4DOQHCZ4nv+wLjqqM6RcOOuHHReSKjDYKNYFgChe++kZ6XOgInkjzpRJs3H2prg3o7m06QuNoFALG9mNZ20Dq3FukLrAJ16gzbjo2IU5bX19fr48WVsVuQPp4Ri5aye/2+tnM+WsB0mO1SDy0atotsICtXhKjzg2wNBR7J8LMz4Xp1brHWpYGCmM6MmZzz61OOj7jallaAH4E5Ku1Xto49s+KJAgEheJHozQM1UP7uh20eiXG/EI9M+fBYOKQ/Ts0AMmblhP2EouVW+Jq0m3i4/YXaJTvTdQXN1f+cEIfbyz1nP0GbtJrT0CjzSAZ3Vj+vS5ogjGMNOD0dkOiWB1Fw37zaK/oQggcbqyTkn4em+0zBIg6q5iWw3kznhdu1P/rDN2+rPYA6ZWZggJvMPPtbZnr+Cau0vmY6CKvy9HZ7bHIGmIxG4rWco9zsQsNWTcbY86RS0fl0qrZfLtmHMcaXo6Vj+5JvRKisTYYCQqx6LEiMJtfeSxEyIX6lgptzM+vuQcgINOSf5nDcxbSe3vF3dGdyoER1AwU0CeP0ubmCmz41RLTfmNeq7ZwMIICF7+OPdrAuEN5rAX89wOtCQMkt9sXDl9txdaCF0Jv1eMmBu Hb+GKDMU tDo1xwRahsRJVQx/QqR2C0vGbvxJWMxQP0C1l3Tw0lub0fU07YTlRklF8UN2L3Rfxos/2UeLdXXtEeBNMkqEl5x1MrfThCJloounLH68U3Kp5tfv+j4e19CYrMS/MAhUeW1etMq9/IQuINwKLPhbwLkLN1g6GTNB3bmOhj2ZK+W7b7xT10vJf+BQs8YSYypWD5LpXm8f1egm9VOvpRaZL/v8kMa8A0rKgR/pDsmi+CrvThw1m9U9xOIwTm3qKz7cNNUs7prw3FSLRfHbsxugen9YqYustxBHEJPNB5bCUsMcO6FTiGm4t1VaUBfl57FeVAGv1+9LUtBWdO+6Aasdcw0QqF3qEFLy/1gHW 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 order to determine the store type for a maple tree operation, a walk of the tree is done through mas_wr_walk(). This function descends the tree until a spanning write is detected or we reach a leaf node. While descending, keep track of the height at which we encounter a node with available space. This is done by checking if mas->end is less than the number of slots a given node type can fit. Now that the height of the vacant node is tracked, we can use the difference between the height of the tree and the height of the vacant node to know how many levels we will have to propagate creating new nodes. Update mas_prealloc_calc() to consider the vacant height and reduce the number of worst-case allocations. Rebalancing and spanning stores are not supported and fall back to using the full height of the tree for allocations. Update preallocation testing assertions to take into account vacant height. Signed-off-by: Sidhartha --- include/linux/maple_tree.h | 2 + lib/maple_tree.c | 13 ++++-- tools/testing/radix-tree/maple.c | 79 ++++++++++++++++++++++++++++---- 3 files changed, 82 insertions(+), 12 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index cbbcd18d4186..7d777aa2d9ed 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -463,6 +463,7 @@ struct ma_wr_state { void __rcu **slots; /* mas->node->slots pointer */ void *entry; /* The entry to write */ void *content; /* The existing entry that is being overwritten */ + unsigned char vacant_height; /* Depth of lowest node with free space */ }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) @@ -498,6 +499,7 @@ struct ma_wr_state { .mas = ma_state, \ .content = NULL, \ .entry = wr_entry, \ + .vacant_height = 0 \ } #define MA_TOPIARY(name, tree) \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a37837d6f3eb..878a7740628c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3544,6 +3544,9 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) if (ma_is_leaf(wr_mas->type)) return true; + if (mas->end < mt_slots[wr_mas->type] - 1) + wr_mas->vacant_height = mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } @@ -4159,7 +4162,9 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) { struct ma_state *mas = wr_mas->mas; - int ret = mas_mt_height(mas) * 3 + 1; + unsigned char height = mas_mt_height(mas); + int ret = height * 3 + 1; + unsigned char delta = height - wr_mas->vacant_height; switch (mas->store_type) { case wr_invalid: @@ -4177,13 +4182,13 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) ret = 0; break; case wr_spanning_store: - ret = mas_mt_height(mas) * 3 + 1; + WARN_ON_ONCE(ret != height * 3 + 1); break; case wr_split_store: - ret = mas_mt_height(mas) * 2 + 1; + ret = delta * 2 + 1; break; case wr_rebalance: - ret = mas_mt_height(mas) * 2 - 1; + ret = height * 2 + 1; break; case wr_node_store: ret = mt_in_rcu(mas->tree) ? 1 : 0; diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index bc30050227fd..5950a7c9b27f 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35475,15 +35475,65 @@ static void check_dfs_preorder(struct maple_tree *mt) } /* End of depth first search tests */ +/* get height of the lowest non-leaf node with free space */ +static unsigned char get_vacant_height(struct ma_wr_state *wr_mas, void *entry) +{ + struct ma_state *mas = wr_mas->mas; + char vacant_height = 0; + enum maple_type type; + unsigned long *pivots; + unsigned long min = 0; + unsigned long max = ULONG_MAX; + unsigned char offset; + + /* start traversal */ + mas_reset(mas); + mas_start(mas); + if (!xa_is_node(mas_root(mas))) + return 0; + + type = mte_node_type(mas->node); + wr_mas->type = type; + while (!ma_is_leaf(type)) { + mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max); + offset = mas->offset; + mas->end = mas_data_end(mas); + pivots = ma_pivots(mte_to_node(mas->node), type); + + if (pivots) { + if (offset) + min = pivots[mas->offset - 1]; + if (offset < mas->end) + max = pivots[mas->offset]; + } + wr_mas->r_max = offset < mas->end ? pivots[offset] : mas->max; + + /* detect spanning write */ + if (mas_is_span_wr(wr_mas)) + break; + + if (mas->end < mt_slot_count(mas->node) - 1) + vacant_height = mas->depth + 1; + + mas_descend(mas); + type = mte_node_type(mas->node); + mas->depth++; + } + + return vacant_height; +} + /* Preallocation testing */ static noinline void __init check_prealloc(struct maple_tree *mt) { unsigned long i, max = 100; unsigned long allocated; unsigned char height; + unsigned char vacant_height; struct maple_node *mn; void *ptr = check_prealloc; MA_STATE(mas, mt, 10, 20); + MA_WR_STATE(wr_mas, &mas, ptr); mt_set_non_kernel(1000); for (i = 0; i <= max; i++) @@ -35494,8 +35544,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); + vacant_height = get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated == 0); - MT_BUG_ON(mt, allocated != 1 + height * 3); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mas_destroy(&mas); allocated = mas_allocated(&mas); MT_BUG_ON(mt, allocated != 0); @@ -35503,8 +35554,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); + vacant_height = get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated == 0); - MT_BUG_ON(mt, allocated != 1 + height * 3); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); mas_destroy(&mas); allocated = mas_allocated(&mas); @@ -35514,7 +35566,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mn = mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); mn->parent = ma_parent_ptr(mn); @@ -35527,7 +35580,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mn = mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); @@ -35540,7 +35594,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mn = mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); mas_push_node(&mas, mn); @@ -35553,7 +35608,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 3); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) != 0); @@ -35578,7 +35634,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); - MT_BUG_ON(mt, allocated != 1 + height * 2); + vacant_height = get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 2); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) != 0); mt_set_non_kernel(1); @@ -35595,8 +35652,14 @@ static noinline void __init check_prealloc(struct maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); allocated = mas_allocated(&mas); height = mas_mt_height(&mas); + vacant_height = get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated == 0); - MT_BUG_ON(mt, allocated != 1 + height * 3); + /* + * vacant height cannot be used to compute the number of nodes needed + * as the root contains two entries which means it is on the verge of + * insufficiency. The worst case full height of the tree is needed. + */ + MT_BUG_ON(mt, allocated != height * 3 + 1); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) != 0); mas_set_range(&mas, 0, 200); From patchwork Thu Feb 27 20:48:21 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13995209 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 DD8DCC1B087 for ; Thu, 27 Feb 2025 20:48:43 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4375B6B008A; Thu, 27 Feb 2025 15:48:39 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 3C2DB6B008C; Thu, 27 Feb 2025 15:48:39 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1ECD86B0092; Thu, 27 Feb 2025 15:48:39 -0500 (EST) 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 EE2896B008A for ; Thu, 27 Feb 2025 15:48:38 -0500 (EST) Received: from smtpin27.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 96898A0462 for ; Thu, 27 Feb 2025 20:48:38 +0000 (UTC) X-FDA: 83166913116.27.575E45D Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf10.hostedemail.com (Postfix) with ESMTP id 5CFFFC000E for ; Thu, 27 Feb 2025 20:48:36 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=PBhhTmil; spf=pass (imf10.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740689316; 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=axDkgHvhakXDWLjLRooU6nhITyeHLZk+oAMXqWkly/0=; b=mXdkIa1Ox/teXt4HmvCTCstAGVYyEdEOjlc873HNOLN0L4n5vDQsXEHgFE+QqLiQjZHL6o jvtjhzRoz7UmTA+NBJz1TAuhx+Yzs/VLZB7U1lFmYjjXCDwdVwVe23WWekncrwRrBdY/nk dMNnKie8j6yp7FoWPG/AbrtFVmIsHLk= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740689316; a=rsa-sha256; cv=none; b=FT1SiiWRGRx8kqzhiGzJQY11XbXX6iwiQNanxiwWU24HMkaB5D7viN6IvL9eUFUo4yD4gq Id5XmGUGEm2GYSoiR9VwTufF+lQ75AETchPswigVz/Vhh3TkXLJUVWDWF+43geAmfxLvfi iappe6zkhj7ewiiDLZ69UYrblxC1baU= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=PBhhTmil; spf=pass (imf10.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com; dmarc=pass (policy=reject) header.from=oracle.com Received: from pps.filterd (m0246617.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJiZdN019264; Thu, 27 Feb 2025 20:48:34 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=axDkg HvhakXDWLjLRooU6nhITyeHLZk+oAMXqWkly/0=; b=PBhhTmilyd9IYSeYhZc6a iJyzgxRRaT/PeQgr/CCixYuGZZSTM3wW/Xh5sl93AC0FGP//ewS6utQZmgRMtFwl CVzMBdJfwArOQhwoppWVm9HOA8xiTDxfDWL8pjdW2sAGsAY9ZUoX6Q+eaqcH4Sm7 JRBTqv3X+vf5tcsCn23I/7bKa8/4gcTFVnH0gKlkmXAT7rIbkdGoLA9XYWuqX4hu D+vU29VZRhA8PrXUiZAU3JSQUAyOYONYTS8sTYc6durXdZkx4B6yPoMR4Lkp6squ cH70G6CK4uL573eNanO3qb4QOicjA5NkeUG5YWj7K6+mDBGwwXMusoHre7u8F919 A== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 451psf4cp0-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:34 +0000 (GMT) Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51RKV9Pl012574; Thu, 27 Feb 2025 20:48:33 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 44y51dws5b-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:33 +0000 Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51RKhrvk030883; Thu, 27 Feb 2025 20:48:33 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 44y51dwrvc-5; Thu, 27 Feb 2025 20:48:32 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, richard.weiyang@gmail.com, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v3 4/6] maple_tree: break on convergence in mas_spanning_rebalance() Date: Thu, 27 Feb 2025 20:48:21 +0000 Message-ID: <20250227204823.758784-5-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250227204823.758784-1-sidhartha.kumar@oracle.com> References: <20250227204823.758784-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-02-27_07,2025-02-27_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502270154 X-Proofpoint-ORIG-GUID: qbzTOSdHShzfMYbSFjzmfG_Qc6PIheuw X-Proofpoint-GUID: qbzTOSdHShzfMYbSFjzmfG_Qc6PIheuw X-Rspamd-Server: rspam02 X-Stat-Signature: 1bxgqwyqpjx63a64o3cnerq7p3bjh5m3 X-Rspamd-Queue-Id: 5CFFFC000E X-Rspam-User: X-HE-Tag: 1740689316-314990 X-HE-Meta: U2FsdGVkX18+FDSnhbRY+yCJfgWfLvibSviwzNTfSpESODjGzHscfsXuUo7RmO8b0zeW74XQfiWG4KaWCqpcxEHjOoDHYQxiW2qaD+/w452QAZFBGkbfnyPTt2dRwPO1blqS0tvPafwPLI79WA6f6CEnnzr2lLhZA+Y6TtEfMjahWoVHWGc0HzXXSYRAo3VX9+aJdMLdg3d81AXHnfz+/eYMKkob0gxNKjPgEAOvJWppZcOrWhn0KN+BBSyGTPnUIdlGUVhqrdBCavOvquItcM9inFp21uMsq5tOqH4FNcm+R+nQVfLJm9tmORmoXaAocL69GI8ZPvdXDdIZV9K+se7C7pvq64/90A1QScyVbCmsBQzC56GnVpDhhHYyiusbMRrQSEExV8bdPHpeWozOhzjz5eIKio/nideWsdObff7vdj/k12fOQ7ulH+iW/+d+nCRPPGaEIt8NfViZFCirkLYyzhq6o2B0fSKG7kbaag/BGo00Pn796rv3qrpIw5Ue4fXyrUWXeS1aYMaAkUMKzXUnmfE7aTYl2Vq5POvtn7v76R0lQzchhwkY4bSncGbhbZEDj2vTFhUvFHR6PCO/XIRgS1wz+oGgU6VRI41yiHdE6ReZDGNQG3twH9B30vCCE176v73gyLnxGtN/wXjUyKH91jZiXqb+c73IlYQca80tusEKgnCnOsbW/NR9Ia4oNxGPQR5tLEGa1b2RLDrUpVAxCyG6Ht548OHPCznPQBSwqfaN7s1u2UBTQH6LBQU5uFChT0cIf92DzlITq3ijtrfVGtAaDQOHgIEcrHA4qYtFZSxdt0rFvfkoa9EfCdhho9SScmYfLV3v1QgViDjChcM9td+86FWOnHewBDSLCHsiCKL5q66C8PUhCalDAkLN3uF17mM7DvzigYUYloG9yt/rp8uJYDekcXZn4NvfCQjuAjU32wv3CujO8cR0V5TNaBZa/KZ1G+teIq4Gstp QDdVcWQw ngnk890XxsaV9m6ZzHrZbOhQxaMpGTyApDYuWieCcLy/DodPz6Kb/JldxRcTHh/9G1ymjKZh/QSrmxXYwS1jSve/WvF8114khfnyxiKDdwuvc5EfSM1gHhB7c6e9NM2+eh7Lrmat/OWXxrGP3a8xAi2Ja8J10RWiWTx19FUalbslPkgEa82FxHtEHfsqIF6aC+fxKk5Rv8d+Llm/NMUPVigM/8BSm6LTNVmm+dvXRP5OX10ygkd0mMzY8PlTrAj9n413OoeBETwMFx8Rg53xr1g7rcfAMl7bfAeosGmq99d5h6Z1GVUw7Vm4ZDokrxJKUn3/031oL+flyy3DOWL5dKSQi2og9G+Kkg/UF5WFMrhSLSb48UTfYdN2yfg== 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: This allows support for using the vacant height to calculate the worst case number of nodes needed for wr_rebalance operation. mas_spanning_rebalance() was seen to perform unnecessary node allocations. We can reduce allocations by breaking early during the rebalancing loop once we realize that we have ascended to a common ancestor. Suggested-by: Liam Howlett Reviewed-by: Wei Yang Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 19 ++++++++++++++++--- 1 file changed, 16 insertions(+), 3 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 878a7740628c..c859c7253d69 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2899,11 +2899,24 @@ static void mas_spanning_rebalance(struct ma_state *mas, mast_combine_cp_right(mast); mast->orig_l->last = mast->orig_l->max; - if (mast_sufficient(mast)) - continue; + if (mast_sufficient(mast)) { + if (mast_overflow(mast)) + continue; + + if (mast->orig_l->node == mast->orig_r->node) { + /* + * The data in b_node should be stored in one + * node and in the tree + */ + slot = mast->l->offset; + /* May be a new root stored in mast->bn */ + if (mas_is_root_limits(mast->orig_l)) + new_height++; + break; + } - if (mast_overflow(mast)) continue; + } /* May be a new root stored in mast->bn */ if (mas_is_root_limits(mast->orig_l)) { From patchwork Thu Feb 27 20:48:22 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13995210 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 DCD59C19F32 for ; Thu, 27 Feb 2025 20:48:46 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 855EA6B008C; Thu, 27 Feb 2025 15:48:40 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 7E3F66B0092; Thu, 27 Feb 2025 15:48:40 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 635336B0093; Thu, 27 Feb 2025 15:48:40 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 3BAB56B008C for ; Thu, 27 Feb 2025 15:48:40 -0500 (EST) Received: from smtpin12.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay02.hostedemail.com (Postfix) with ESMTP id AE541121CDE for ; Thu, 27 Feb 2025 20:48:39 +0000 (UTC) X-FDA: 83166913158.12.4875E04 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf21.hostedemail.com (Postfix) with ESMTP id 95D251C0007 for ; Thu, 27 Feb 2025 20:48:37 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b="B/MWfCW/"; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf21.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740689317; a=rsa-sha256; cv=none; b=yf6g3qXqg0T+11xdnNRpjk0f4c6BQjDYrfaIOZ1iIGq/aBulaz8BsYPAPehOekdWEozg/q AYlQ9u/TifI6n4NiNMbMTRBaSfL0Dfu650HTu8faCzUiKb7g+UwGb3rS4+vjYNrZQWigQ6 GixTnCoap3lpYs3WklrMzZNxsKiKEfY= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b="B/MWfCW/"; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf21.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740689317; 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=JuEm0THBBAVfyITvD6DAdLmtYPg2v5ViaCoOAvJ6+pg=; b=laWwo9F/yXFF9ExpESXKNijljnPpZZ58a2K8GcBeeqo4P+93+po4iryWrPAokEflp2OL8+ C1gI8dEgGcKNeYpJZrUi2jejtDnU6ESibVqr+816aHiYpJ+5xWm6AWW7bOBf7uvN+ngCC/ ueGhfLS5cCz4/CwcORc4ui/hG+vPXBE= Received: from pps.filterd (m0246627.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJiXZv016373; Thu, 27 Feb 2025 20:48:36 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=JuEm0 THBBAVfyITvD6DAdLmtYPg2v5ViaCoOAvJ6+pg=; b=B/MWfCW/6nVzxODMI4aAh tGJYjO/x3zbgvlkDiywZwNdVfmtMgTS4rVDja7zV/B/2PQ0tuZI9Vh17GAiPz3qn tnt2776lS0aDWlgQWZE3eGq/HcwnX46ybhLlvbvcgCpctNyCPFK7r6Oi7ec9APVm 8gXgV8Um9MwSaxx0OaMa/UlKnIHiPLdcyLSSbJfNcN79i47cJsxWr9IaMWU+Z+nQ 6EXVs7mgEaZalrLDuLEOA1DNXoppK5AOGn/pWmgrhtEx3oEOlz3MUQr97xU3odtz LhNF/cSD1rF5Ll1kLEPSZKPMHGkHqXvPhJElfx7hkcsiVuL+XXHje2aqj6wCLke/ A== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 451psecbja-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:35 +0000 (GMT) Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJB2Du012641; Thu, 27 Feb 2025 20:48:35 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 44y51dws6r-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:35 +0000 Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51RKhrvm030883; Thu, 27 Feb 2025 20:48:34 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 44y51dwrvc-6; Thu, 27 Feb 2025 20:48:34 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, richard.weiyang@gmail.com, Sidhartha Kumar Subject: [PATCH v3 5/6] maple_tree: add sufficient height Date: Thu, 27 Feb 2025 20:48:22 +0000 Message-ID: <20250227204823.758784-6-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250227204823.758784-1-sidhartha.kumar@oracle.com> References: <20250227204823.758784-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-02-27_07,2025-02-27_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502270154 X-Proofpoint-GUID: -0BP64E3TDaVjZabqOuZvlV2I6UXJsU1 X-Proofpoint-ORIG-GUID: -0BP64E3TDaVjZabqOuZvlV2I6UXJsU1 X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 95D251C0007 X-Stat-Signature: po9bd5h3t3i5njeuk9w1o6t5dert84xp X-Rspam-User: X-HE-Tag: 1740689317-317662 X-HE-Meta: U2FsdGVkX1/RMCRvEs0wiNc/Oz8O7uE6/n4IB0Nbpy+MH2VxW5M5sCSv4npClejjU41b/xG3o/6a7uASAfmllIKMTib2ulum/VMJU63BkN/RoPVFCshGnGJ1i6OhA2wO89u7ZEuZKk2B4h+5bBPiX4WBw2PGLgBkt/HP2tW95q2M6zRac74QgFy3NEDcAM0Iw3h3Wkc0Y48fhsBf/T+/RqXAUvF4pyHEdJ+pn7vuRON/DkpYwy5XJ0rF57wyYmNqK1vyzXa2BfhYLi/HIjupIWMDV3qtm5U0OTbsM7lVWJVN4pn1wIfKtPJKgJlMGK0xSxtuc2knpo1/xZtpE9IdSTCVzPPftkPY4bulTyuQBofvn2h1CRkDBS6cEq0Tkl46fSwsHw2hmyQ2YLgvDX/0Bie3wRq1mGa18YEtzZnaT1Qx4McVHKYdGo/C+V6i6eAy6vXppLovxrwHRTaEl6gJp3iWsD8DkCLDIN2qzCBFnu/dSS3rvNnAsZYG0QVeqCf/G6W4ozXEoVLwBQA/eptwstnTc/uhSIM7Sex+siU/uPiB8lYH72Obx0dZniYjkhh3uY3jOu0ig114xIbhCI4Mxn1AVS5QZ/GzkTEI4G6+bzIIDrv3fbGTq2PJi2ER5qdjDw9fbwQwUn0Zbp77jaohh4P0psJEpcZgHsPqrNIG7EqC2RLKUl/Xy4qGiLaA8zuI3enedmCkUm8mQdjGnLMn3zkgG7s4gv8IXrHCYhqt7Ux35M0djFH23Nk5W13UN7Rdvp+/u4gaAZTHCu+TNgY6QXAVzOQpK72MigdmcuIfJyOgux9lm3cHPLwo8XXNDGDTsyZgioHQkftvbQ4mJcOYwu6d799TpATwQM2wzJUiVrzGMp5n5CmtbS9yFWqz9ImCim9ILMaVUwKBbVHZQnLoVZUVQ4owCfL5V9jBOt+FRxFW9cyXZtznNEpIcE5acwzBc+SYoBnxKy8h4y+5COF onW5hvPd vrkdHAz6Cr8oiY26jVqsJw4gRJkAtgX6f9abtsa/KOHRvCTxX5DYt5bL4b6A3cxba/WIcUPtutqWNvmRTky+dFmfPm2ZcSpn1KgGgLpsPMi15UvHvppX1bbH+jQQydrCvBwlISYLc0WIeI7GUiqEnrhbcgJsp29yXoTEWunAXGRQl9aYSSj8vWrCHlpaiGJ0KK64mQjBbX/XJRsWuf4Hj4megxrcg9iaHhO1rm4AL2SisDFvF5LswudE7LKDK8mNBTaYUaDbBrM/SY306hlAa6f16uksez3hp5G6a3r2XfNLY1protoQ1x3CzifFTvRgYbi4plJc/d7W8yzirJrD+KaohGazNfJxfbbTb 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 order to support rebalancing and spanning stores using less than the worst case number of nodes, we need to track more than just the vacant height. Using only vacant height to reduce the worst case maple node allocation count can lead to a shortcoming of nodes in the following scenarios. For rebalancing writes, when a leaf node becomes insufficient, it may be combined with a sibling into a single node. This means that the parent node which has entries for this children will lose one entry. If this parent node was just meeting the minimum entries, losing one entry will now cause this parent node to be insufficient. This leads to a cascading operation of rebalancing at different levels and can lead to more node allocations than simply using vacant height can return. For spanning writes, a similar situation occurs. At the location at which a spanning write is detected, the number of ancestor nodes may similarly need to rebalanced into a smaller number of nodes and the same cascading situation could occur. To use less than the full height of the tree for the number of allocations, we also need to track the height at which a non-leaf node cannot become insufficient. This means even if a rebalance occurs to a child of this node, it currently has enough entries that it can lose one without any further action. This field is stored in the maple write state as sufficient height. In mas_prealloc_calc() when figuring out how many nodes to allocate, we check if the the vacant node is lower in the tree than a sufficient node (has a larger value). If it is, we cannot use the vacant height and must use the difference in the height and sufficient height as the basis for the number of nodes needed. Signed-off-by: Sidhartha Kumar --- include/linux/maple_tree.h | 4 +++- lib/maple_tree.c | 17 +++++++++++++++-- tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 46 insertions(+), 3 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 7d777aa2d9ed..37dc9525dff6 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -464,6 +464,7 @@ struct ma_wr_state { void *entry; /* The entry to write */ void *content; /* The existing entry that is being overwritten */ unsigned char vacant_height; /* Depth of lowest node with free space */ + unsigned char sufficient_height;/* Depth of lowest node with min sufficiency + 1 nodes */ }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) @@ -499,7 +500,8 @@ struct ma_wr_state { .mas = ma_state, \ .content = NULL, \ .entry = wr_entry, \ - .vacant_height = 0 \ + .vacant_height = 0, \ + .sufficient_height = 0 \ } #define MA_TOPIARY(name, tree) \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c859c7253d69..d3aa5241166b 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3560,6 +3560,13 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) if (mas->end < mt_slots[wr_mas->type] - 1) wr_mas->vacant_height = mas->depth + 1; + if (ma_is_root(mas_mn(mas))) { + /* root needs more than 2 entries to be sufficient + 1 */ + if (mas->end > 2) + wr_mas->sufficient_height = 1; + } else if (mas->end > mt_min_slots[wr_mas->type] + 1) + wr_mas->sufficient_height = mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } @@ -4195,13 +4202,19 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) ret = 0; break; case wr_spanning_store: - WARN_ON_ONCE(ret != height * 3 + 1); + if (wr_mas->sufficient_height < wr_mas->vacant_height) + ret = (height - wr_mas->sufficient_height) * 3 + 1; + else + ret = delta * 3 + 1; break; case wr_split_store: ret = delta * 2 + 1; break; case wr_rebalance: - ret = height * 2 + 1; + if (wr_mas->sufficient_height < wr_mas->vacant_height) + ret = (height - wr_mas->sufficient_height) * 2 + 1; + else + ret = delta * 2 + 1; break; case wr_node_store: ret = mt_in_rcu(mas->tree) ? 1 : 0; diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 5950a7c9b27f..dc8e40b94c3f 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36311,6 +36311,30 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt) extern void test_kmem_cache_bulk(void); +/* + * Test to check the path of a spanning rebalance which results in + * a collapse where the rebalancing of the child node leads to + * insufficieny in the parent node. + */ +static void check_collapsing_rebalance(struct maple_tree *mt) +{ + int i = 0; + MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); + + /* create a height 4 tree */ + while (mt_height(mt) < 4) { + mtree_store_range(mt, i, i + 10, xa_mk_value(i), GFP_KERNEL); + i += 9; + } + + /* delete all entries one at a time, starting from the right */ + do { + mas_erase(&mas); + } while (mas_prev(&mas, 0) != NULL); + + mtree_unlock(mt); +} + /* callback function used for check_nomem_writer_race() */ static void writer2(void *maple_tree) { @@ -36477,6 +36501,10 @@ void farmer_tests(void) check_spanning_write(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_collapsing_rebalance(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_null_expand(&tree); mtree_destroy(&tree); From patchwork Thu Feb 27 20:48:23 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13995211 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 DED30C19F32 for ; Thu, 27 Feb 2025 20:48:49 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id F0C246B0093; Thu, 27 Feb 2025 15:48:41 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id EBC326B0095; Thu, 27 Feb 2025 15:48:41 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D3894280001; Thu, 27 Feb 2025 15:48:41 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id A998A6B0093 for ; Thu, 27 Feb 2025 15:48:41 -0500 (EST) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 577C31A1DAE for ; Thu, 27 Feb 2025 20:48:41 +0000 (UTC) X-FDA: 83166913242.29.011FA73 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf29.hostedemail.com (Postfix) with ESMTP id 3666E120005 for ; Thu, 27 Feb 2025 20:48:39 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=gRNNqAGu; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf29.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740689319; a=rsa-sha256; cv=none; b=F9KunfTRFAjvuTnzJEB6Dz3U8GJb4gYze+jP7Q6KGX0TIZjmtv3wWIcXjqGDo+Bxrq74J2 1nQDAviFHrSSd5QALiv3SkaO/dlHgPtsigZWM8fZ1L9ypzuAG17QuOywcr7tmxRpoyefzE a0af33iMdQXt+RRdq4qOA8KEv6Nd29s= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=gRNNqAGu; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf29.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.165.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1740689319; 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=9rOxR8xV/873pof+AkJuZwF4Ju77egxXek8DyN5etOw=; b=0qsxhB1owxHAZFfmd+ENaFSnjQP+DZFOgMR+aEIwyw4WR52iHBRzJXNtlj23iyubCbKd2y /iygH1Kk0XApURKYw4gV63XXgQTo/Q1Coku7YslEMqXmAzlmtJvp9qDpDGmSOgcuC9iJ5l QijaSrraXKfPyDMA3UAsMsQbCtbq93E= Received: from pps.filterd (m0246629.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJiY80016056; Thu, 27 Feb 2025 20:48:37 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=9rOxR 8xV/873pof+AkJuZwF4Ju77egxXek8DyN5etOw=; b=gRNNqAGuqrxyrzWhstSKs Ci96yqLVfG0pofsHzOswSLRK9TzfDpUMDWz5XN1sgTWv13nkL3UDSlElBumNqx9e z8xK8lW6MsJESWhaOIbRt8Wj7rpe+i4pWJTCxeDASF03lVxXpxd8Zg2ntjpI3vkv RFgUE+dBNbhv9m1EkfpnT7TK6aDS4syuYOrNrNulgwCTxA5GV+RxoyXA9H1gm4mb SSR4ZES6EujTv7pnRuC3AImP2Hloi3Yh7FP78pyE0kDwultKRTt1Mx99GGL4P2cq xY6YsqRkq2nBd9GdwTLYfQjSDrO/CMCJ4FijSpeashBdkP4xebzgVEFCpNlO8Ii/ g== Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.appoci.oracle.com [138.1.114.2]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 451psf49m0-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:37 +0000 (GMT) Received: from pps.filterd (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51RJGgfJ012623; Thu, 27 Feb 2025 20:48:36 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 44y51dws8s-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 27 Feb 2025 20:48:36 +0000 Received: from phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51RKhrvo030883; Thu, 27 Feb 2025 20:48:36 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by phxpaimrmta01.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 44y51dwrvc-7; Thu, 27 Feb 2025 20:48:35 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, richard.weiyang@gmail.com, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v3 6/6] maple_tree: reorder mas->store_type case statements Date: Thu, 27 Feb 2025 20:48:23 +0000 Message-ID: <20250227204823.758784-7-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250227204823.758784-1-sidhartha.kumar@oracle.com> References: <20250227204823.758784-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1057,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-02-27_07,2025-02-27_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 phishscore=0 spamscore=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502270154 X-Proofpoint-ORIG-GUID: lKETHqUtyLBnsXDOSH0cE46buP1f3N_E X-Proofpoint-GUID: lKETHqUtyLBnsXDOSH0cE46buP1f3N_E X-Rspamd-Server: rspam08 X-Rspamd-Queue-Id: 3666E120005 X-Stat-Signature: ugd3m13dimdzoat8znhm6n4wb9qh84ok X-Rspam-User: X-HE-Tag: 1740689319-799115 X-HE-Meta: U2FsdGVkX18gxdGoPU+1PnIL9J6TPrdfbES4kuHoefvxN7J4zXVqHJm8LXlu8XRWq+TcAvoCmaMH/KunFDfYn+vMahWXBjtbuKeUVy2OSUkAfVJzI51bMW1fKhAl0JsifGIMVjEQ3oihUGZLsR+NoCkq6gDQiWM8jdVVkQfXnkknRB9D4Va8lwsq6o/+92iQcF0hGKwWaNkv1tNKA8NN5J4ArYf8hLXkoGmkaAvXkO9KmTYs8+YiDrmkKezUdTf7yz+A+J2AHWyOwRtv4Zvaq/2nGcjaCGYAM0m8oC/avUipZt9UHPrI1fOeoKxpjbC5dee/0L0kEbVF4aYpAlYwEMwyBQZ2wr15XMXTlGMGsgcfW9Hexil5HK0qWKvxOULoVqHVGlp9mJgUqiIiEIeqcDUA9Hckp2RhpTN0oisD94r1AyrabV0Wv5sLFohoSZd04ZEiCKsIbe1/QyAT+IK1ad0sbS4n7N0QbtZDTG2wdUl/WHAPl7JpWL5lDizt6EVjEYGWa89K22Siu7FW9XE8iGsYgeBnppBLVlRdgmWjPLOsNRwl955YqEWcIduIZpL1+akeKujJGCzbXn3iQZbNVM1s+QvteGV2TtcdoPm6ILCX7xp59HMokbvzl5RIPh44QvPxjMzyHNVM4lAw7Zpr/gPLCdvs3PEy87XYcreRmvJ+gB7saOpeVg8foQr8bskPMmmIWLGWOV7Yuh8hr2X+7oppIzoJmySDnspVb5seQB4HT46TyG/hVE7xBJ9Ln4ejf/o2WGveBoo34/ympDJPFaUlNb8RcoYt93EwIV06iiNUC1dBWjJ9MyR2MeOO+RRZk+8I4t80ZbJnQQgR+WbaZrwZX4fK3QdAq1K2OAiSAjeSZLUZwD3Su65pSEa63kIGtScS1eYExVbtuLKe9PACd/Da3de1xxjnesQAwn987eMDg42awZvncX35+xMlK/csDhFFUF1D7bzdZgWyry0 f9qexzYv qju8dUTOqwE4oXju6jL1TWPqMEJm3K1EftmnkosrJCiFEdIJQk0/bKeM2IfmYQGJqBgrc8NE7mZSzmYU+y+NEK1zpoOF5oQlEozHe9G/GBxl8/hV7F2s4GurgJBRBMT8GBMuDbR1T7JqB7h5jw6TbqGJliO0yZVgx2MRJ422wDU2v49ubV6/ju27laZyglkg3cs9jtI4rxGZyROVegejbOqfple2yXTY81omfaifq92dSKtxJkdMrJhG6nofXIOL/1gz1TXS7VuH7SLlNP4FXcx5kvwCHUMHP9LNoI0Ji9lx2CzuK+oT+LTZiArlarFHIytaOA8oPLmc2hBY0A2HFSUbGnrxvNIr0aIv+5BP8Jnz2V6/JphmaMQ8b7YqLRRLVtFWVLaZNLxoDJ5E= 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: Move the unlikely case that mas->store_type is invalid to be the last evaluated case and put liklier cases higher up. Suggested-by: Liam R. Howlett Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 51 ++++++++++++++++++++++++------------------------ 1 file changed, 25 insertions(+), 26 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d3aa5241166b..776693593ab9 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4093,15 +4093,6 @@ static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) unsigned char new_end = mas_wr_new_end(wr_mas); switch (mas->store_type) { - case wr_invalid: - MT_BUG_ON(mas->tree, 1); - return; - case wr_new_root: - mas_new_root(mas, wr_mas->entry); - break; - case wr_store_root: - mas_store_root(mas, wr_mas->entry); - break; case wr_exact_fit: rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); if (!!wr_mas->entry ^ !!wr_mas->content) @@ -4123,6 +4114,14 @@ static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas) case wr_rebalance: mas_wr_bnode(wr_mas); break; + case wr_new_root: + mas_new_root(mas, wr_mas->entry); + break; + case wr_store_root: + mas_store_root(mas, wr_mas->entry); + break; + case wr_invalid: + MT_BUG_ON(mas->tree, 1); } return; @@ -4187,19 +4186,10 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) unsigned char delta = height - wr_mas->vacant_height; switch (mas->store_type) { - case wr_invalid: - WARN_ON_ONCE(1); - break; - case wr_new_root: - ret = 1; - break; - case wr_store_root: - if (likely((mas->last != 0) || (mas->index != 0))) - ret = 1; - else if (((unsigned long) (entry) & 3) == 2) - ret = 1; - else - ret = 0; + case wr_exact_fit: + case wr_append: + case wr_slot_store: + ret = 0; break; case wr_spanning_store: if (wr_mas->sufficient_height < wr_mas->vacant_height) @@ -4219,10 +4209,19 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) case wr_node_store: ret = mt_in_rcu(mas->tree) ? 1 : 0; break; - case wr_append: - case wr_exact_fit: - case wr_slot_store: - ret = 0; + case wr_new_root: + ret = 1; + break; + case wr_store_root: + if (likely((mas->last != 0) || (mas->index != 0))) + ret = 1; + else if (((unsigned long) (entry) & 3) == 2) + ret = 1; + else + ret = 0; + break; + case wr_invalid: + WARN_ON_ONCE(1); } return ret;