From patchwork Mon Apr 7 18:40:57 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 14041520 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 D49DDC36010 for ; Mon, 7 Apr 2025 18:41:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A9E906B0006; Mon, 7 Apr 2025 14:41:15 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id A4DA06B0008; Mon, 7 Apr 2025 14:41:15 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 93AAD6B000A; Mon, 7 Apr 2025 14:41:15 -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 746456B0006 for ; Mon, 7 Apr 2025 14:41:15 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id D81A4BB54E for ; Mon, 7 Apr 2025 18:41:15 +0000 (UTC) X-FDA: 83308115310.30.46E6185 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf24.hostedemail.com (Postfix) with ESMTP id D03A3180009 for ; Mon, 7 Apr 2025 18:41:13 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=J5+STbyq; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf24.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.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=1744051273; 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=xifEaGxLrCosb9AknfMROurmyL6jhk0BySHE36IGbs0=; b=r5i7tdQrnMDoLQpiOD/4fs/xa/ut7cBLyvtEFi/KdK+hk90l/a2konJCqjTyoP/pvW2/h6 sUyJwVUJaqsu++tcpZbEGOwqEp/XgdWxJbegPPPwzIRdEPXFXIuix7xoOElN/koN87g5i1 TxskEdfvtrvnfUkaoQ4rAWilOJ08PZc= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=J5+STbyq; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf24.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1744051273; a=rsa-sha256; cv=none; b=jOSAjst8p2P6Y4wlYSB5myfLDpYIkHQmagoc7yDeye7JdKxMWlZfg1IWBMLC+b641WPBAf GnHI8mltreuI7lj1+ycsrVrCSh6SY10VJMXeteVRYq7GN2Avhb46qKK5BnbfzaKcSjM7Lx 1MOiMCjtAjr51sOl1XEhp8ca06UeLqs= 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 537H0ihp029680; Mon, 7 Apr 2025 18:41:07 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=xifEa GxLrCosb9AknfMROurmyL6jhk0BySHE36IGbs0=; b=J5+STbyq/ZJOEaT+XDikd 8Z/XTQs3dk3GWdUI+8zyptFFX0zInhPjVAT6/6+KsI1v1d1wREdiQvDCTFqJn5ln 8+7rjZ/T5ElFsLg0jm+HTVCUO1pAWN8IN3CGttmMAFzBjuArUNwW0YlRz7NnpZ47 gddpoxOJEn6QkzBf75qT1LkuJBZWWPnKd5+Fm8VUYCJ3sodJNZdy9k+YorKN+Xuw +si55jbOMAXf4Gd6GgcPDANd2FL0lSd+3K+fZsplEtcXfMKy4+hlTHP0TpCUZklE 7cQwYzKJPyZ+oULmwGN5JKbqsG76KvKmrsqMoFRpqkr3TmtpOdWL7TfvMabd5k2n Q== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45tua2ua1t-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:07 +0000 (GMT) Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 537I0VB0023792; Mon, 7 Apr 2025 18:41:06 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyefwrv-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:06 +0000 Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 537IY5DR038909; Mon, 7 Apr 2025 18:41:06 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 45ttyefwqr-2; Mon, 07 Apr 2025 18:41:06 +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, willy@infradead.org, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v4 1/6] maple_tree: convert mas_prealloc_calc() to take in a maple write state Date: Mon, 7 Apr 2025 18:40:57 +0000 Message-ID: <20250407184102.2155415-2-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> References: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1095,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-04-07_05,2025-04-07_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 mlxscore=0 mlxlogscore=999 suspectscore=0 adultscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502280000 definitions=main-2504070130 X-Proofpoint-GUID: YVHIWhmhFpr19K0Q-elXIcN-oqF4NoLv X-Proofpoint-ORIG-GUID: YVHIWhmhFpr19K0Q-elXIcN-oqF4NoLv X-Rspamd-Server: rspam01 X-Stat-Signature: az5gb6y8omk8nsytybc875fqx41iuypx X-Rspam-User: X-Rspamd-Queue-Id: D03A3180009 X-HE-Tag: 1744051273-78718 X-HE-Meta: U2FsdGVkX18jUYKZKHPi9I4fWRaKTlWDRHMtkim+ubLpPdRmdkdyuuFk6RgaD0k6rmS2cEXMBoQP0aVOQ+vmztUzVxLyU8cTD+RzB05ckxboz7/hapaN8L4j8l3SlJBBw3H5c5/Qpr2+kPWKDH3CP66FaiCPEJiXpjTxs1J/+vEO+BwgDmhkCVflQLvSRJpLefOjbtCNasek9Dm1c1kWx/WiSJxHoiVCzV/r16hw8n4z+jrXfGZlkUACPRGy9fflDoDMoldp9RWoz9c8SvfvoW9+hRq65W4cN5POEXrCbr/HMeYSRexLB4eRUdh8MV51+7HQjGTob/J+YGCTb1mEv6FRkQLfVJVz7i1We2yN+SA3GtXZsjpibYNkVve0XAR+SfBCvAmhPtMoMsS5AvbZIjNfIzGFDZvK2F38rg2Hz51kVWGaRW/ss8WqCwdaQTsKalugZZBFzsFwvWs8hl7kR/YfO8w/Cpurrqv237LWDBxjcehqFavChUPWgSp3E0CuXY/meHspCzakCelTFIXBGraHsuitym+NiFHFbKJWSTpno9Ay420FGocLdzKMPzYZ+OPM7kMl7qFvZGklwAmv/htvwQnZncPxVG2vOoAMi2X00v7MlN3eWMvi0I9lfKNw5kqfbvcodAniF7ZrJ6dxIM1gfwjzRvwZc1GfnppAafs5azQGVaIK4IZ+pqmhZxZR4s/RqJ7ESuhzQWaIp/28ZCqW92oEH7ZU9AYJPF87Vdb6sz+NdFN4png6hB550hMnXjwiLEjDl57bUlWkj494Xu5FYISxuMeyaCcBGwGgoHfapks8pdElo200JW/2jkoCRD/ZJdsKH/F4B4vAml3KBddVb0aNzZlaggAO0PIGJg6tVV/D/iEKXQKT+B2LWWcw9WaeCvnMhGx+4R5w++T8OxJsIv1qts+Pd95dA+86ObbFLmoNbK8yiFgF2vpgm3Ru5JvlSGUoCsQV/NywKb6 PWDiIOsL ovUHSC40Vm5kcVsh7NHU/CtjdyzmFlVpL5nW0WUQSuVp9uqgy7h4f8Mt9zwFahugRIAaMUC86R0IBGiyAeUQXt09mpFkUkIeORgSS+mD6HefClCnpyCbmIzzV0q6SAwG9HmX4rXPRmJ4gG8o52pqNApOTP4sMLDia91P2LSYyaste0j+xcqDK8gSllqp4MezFdqGRt/BD7e08+lT0iUeUxFjEV3LoW6zoXirT6qTVoAtsNONdWpXKoqewUJThS0rnMwa4SKfsMH6iSzpvKwwOjPk6kq2DDIzeyLYC 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 d0bea23fa4bc..f25ee210d495 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4140,13 +4140,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) { @@ -4243,16 +4244,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); } /** @@ -5397,7 +5397,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; @@ -5494,7 +5494,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 Mon Apr 7 18:40:58 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 14041526 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 2989BC369A1 for ; Mon, 7 Apr 2025 18:41:30 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 7032F6B0022; Mon, 7 Apr 2025 14:41:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 5F98F6B0025; Mon, 7 Apr 2025 14:41:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1DE636B0023; Mon, 7 Apr 2025 14:41:21 -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 E57D76B0022 for ; Mon, 7 Apr 2025 14:41:20 -0400 (EDT) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 5F984C14C4 for ; Mon, 7 Apr 2025 18:41:21 +0000 (UTC) X-FDA: 83308115562.20.4CEF78E Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf21.hostedemail.com (Postfix) with ESMTP id 5716D1C0004 for ; Mon, 7 Apr 2025 18:41:19 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=lt6twRPJ; spf=pass (imf21.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=1744051279; 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=WksMBE9ucCYEKSc5GJh7iDK/gye2kn0iObdcPGfaozU=; b=QHL3u1sJyfpLOYTGmjYQQ8HmZ7l89ywjEfDlHR11FlXk9pMfu9o0UEgie2j+0UnTqyi1eu /uNKvyvZNQNtssIgQIZeE6He/OhfLzSPgbhVqNilDgFK0PNdqGoIdssiyiVhXp5gbjkHXZ vWl530P0p0Mio/JfVQTRN23g5zNPLwE= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=lt6twRPJ; spf=pass (imf21.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-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1744051279; a=rsa-sha256; cv=none; b=QKJFdAz83jHQcnRl0++GPNoox3x9tbWbrE3e1s1g5CVSbYMZ667nCFUKI4tBPZBlX4Jj0l JxHFXwGZHTY2wfn/Av8T9KiSZIFuZfEnZLSrP9ixCNR83C8FXTShAyb2fAtnSfgCz+Yq4U n+IfYD5pAo48rmPgixQ56oVdRuRwPLw= 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 537H0kSQ029772; Mon, 7 Apr 2025 18:41:08 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=WksMB E9ucCYEKSc5GJh7iDK/gye2kn0iObdcPGfaozU=; b=lt6twRPJSEgibpWBmz52y p1cXvkwoQBWxlK+bWAFFY2FCC+rHadn2RE+xQLc4QUGAzyglqCc94zGNTh64wT43 VZfaw11NpPFJzZnHJnaNMasvPf15gkQ2R4dCWhlEUs5hm84kJ5KI4wUQ7CIAHPp/ UWIvZXOwPVcVoVXk5iEWATbPpjja2JY4epKPc3UCZIYX0ioEKQdiMPG/XrEnY6HR sPI9ogvi3Je5ppLddIwUweIRxJirHQKBXv0wyGIS8lSr1newpR5fbZxf0ZRWmm8L Vf1Q6rkz5sd0lOaXSo1PI3dkIcjKfPTEY1kEm7wyOzV41SDLec4IQ+qkpSYs4NKl w== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45tua2ua1u-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:07 +0000 (GMT) Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 537IHXZc023814; Mon, 7 Apr 2025 18:41:07 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyefws0-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:07 +0000 Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 537IY5DT038909; Mon, 7 Apr 2025 18:41:06 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 45ttyefwqr-3; Mon, 07 Apr 2025 18:41:06 +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, willy@infradead.org, Sidhartha Kumar Subject: [PATCH v4 2/6] maple_tree: use height and depth consistently Date: Mon, 7 Apr 2025 18:40:58 +0000 Message-ID: <20250407184102.2155415-3-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> References: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1095,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-04-07_05,2025-04-07_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 mlxscore=0 mlxlogscore=999 suspectscore=0 adultscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502280000 definitions=main-2504070130 X-Proofpoint-GUID: dyWCUE4UW_KVnhsPho7eTtlt1s7CfN86 X-Proofpoint-ORIG-GUID: dyWCUE4UW_KVnhsPho7eTtlt1s7CfN86 X-Rspamd-Queue-Id: 5716D1C0004 X-Stat-Signature: bxzx7ws7nytpir3idgbbnsmnwcztsix6 X-Rspam-User: X-Rspamd-Server: rspam12 X-HE-Tag: 1744051279-940834 X-HE-Meta: U2FsdGVkX18CDPKCq6hsthc1MnuSMJstl/mtjSCO7yb/4hOar85l2FO9z7H6v+NdLN6H2LfrXJi/xX7gZyhVl1EFAWJh/b6KfGM4DuexoMGctGqpFtryUx3D+a/lt+g4hZQWXkAU2+LXT7WQRwusI1SOkHNMwgryFSDxWFzBUoK3xCTFHvVx6MCPpxqYmlCfbEGPb+uAbfBm/34roUeml67Ge3PjzyoFzyCI7dZCk0sRHJhAF6bI8fLnk7C0YiFszB9jU7UeYeBMNSrOKeDH8C8RDxzBCWy7Gzdzeff2srpk1MrIHgc7BBaBVq7fxQprZoLrGOneaVGvIZoBlrKh2cXhhnNrJV/Ol8xKA+Au6G7m1/TVx0aOU0XwL9K0gr9GwcOFxR3oec4bdBsomx5nO+YmmPXeQZg0j3Qb7emTpG6hoZkpI+qcoxKDHUIaBc9VUS9hTFJgKn09hLa6gOQvjXbRRS5IROcwmLEOcOxubFQPxoPa4mzrMaEQVk79fYx3ulXxybKEsXBJ3Lx66gb7rOWSAOoqnd5l7b8/sDxbleInzN6qB0KVwjUc9JLY8pxfTmVaADlXlErdo4EHnPCtxLswB8XS3nXMHNn8Wnf+e7T82S7AKuDIU8Tl4Jjk/2n7ONlBTrWA3quvvN3UU5OdCmeQkM/rb7mshKbIrJnEJXB+Pa1k0ArhEnaBl62wbPyEqg1l40owRZLDGXyvIqarUupSPG+chuJ1Tpu4yYd7k+C+Xu2/INXJWsGrPVCvEXCwT86i6Q27N8pGI+/OV/Nk0LPDLDxf4dICZdpG0dp46CUofj4VXYDPlQhA+DuT5zwBRrqnmSlTHL0/s4QOhIk4e6ROmqk5mnXx6rEOat+jx7kFxY4p7KMUVGlM6jd/CMQR9tZVweGGLTqII9brU1OwptggeqbfCuKLNJsYTlGE2USmG8OVmtUxrSQgER3iobLuIy9De3coM/v0XipmNOJ FAvsp/bx k1MMVPnFo5Gkmgs7mSTFvfDPL+TRUD16Y7rXybkSAsk1zuqMmU3U7o8apso//uHfP0ugTuiFjNczU5q4laO3uJz+JHRHeynJdXVNZpSAd8co/pq3pWww3HJZZiMrwjSX3H/o3SGykThPY+HBT3EdXF7d02TXcJpd6a41R2TVBj7k35GK0R8K24fe5SHlDasEK+21xiJ2F0TDGSYoAnuxhqzOP93UIlxmEQCpN8A7W7s12T8WEsa6ij/XlFJvtaEYErGbzgza7OxpmLN0ArPgOyYKgXmd44tSqT+Ax 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 | 82 +++++++++++++++++--------------- tools/testing/radix-tree/maple.c | 19 ++++++++ 2 files changed, 63 insertions(+), 38 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f25ee210d495..236f0579ca53 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) @@ -1371,7 +1371,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; @@ -1712,9 +1712,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; @@ -1723,7 +1724,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); @@ -1741,12 +1742,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); } @@ -2536,10 +2538,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); @@ -2547,7 +2550,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; @@ -2631,14 +2634,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; @@ -2824,6 +2828,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; @@ -2866,6 +2871,7 @@ static void mas_spanning_rebalance(struct ma_state *mas, mast_set_split_parents(mast, left, middle, right, split, mid_split); mast_cp_to_nodes(mast, left, middle, right, split, mid_split); + new_height++; /* * Copy data from next level in the tree to mast->bn from next @@ -2873,7 +2879,6 @@ 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++; /* Root already stored in l->node. */ if (mas_is_root_limits(mast->l)) @@ -2909,8 +2914,9 @@ 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); + new_height++; mas_set_parent(mas, left, l_mas.node, slot); if (middle) mas_set_parent(mas, middle, l_mas.node, ++slot); @@ -2933,7 +2939,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; } @@ -3009,6 +3015,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); @@ -3103,7 +3110,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); } @@ -3114,10 +3121,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; @@ -3126,7 +3132,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. @@ -3214,7 +3219,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. * @@ -3222,8 +3226,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; @@ -3280,7 +3284,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; } @@ -3293,6 +3297,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; @@ -3319,7 +3324,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; @@ -3327,9 +3331,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; } @@ -3344,11 +3348,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); @@ -3365,7 +3373,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; } @@ -3424,8 +3432,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)); @@ -3669,8 +3676,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; @@ -3684,8 +3690,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: @@ -3804,6 +3809,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 */ @@ -3860,7 +3866,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)); } diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index bc30050227fd..e0f8fabe8821 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36248,6 +36248,21 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt) extern void test_kmem_cache_bulk(void); +static inline void check_spanning_store_height(struct maple_tree *mt) +{ + int index = 0; + MA_STATE(mas, mt, 0, 0); + mas_lock(&mas); + while (mt_height(mt) != 3) { + mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL); + mas_set(&mas, ++index); + } + mas_set_range(&mas, 90, 140); + mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL); + MT_BUG_ON(mt, mas_mt_height(&mas) != 2); + mas_unlock(&mas); +} + /* callback function used for check_nomem_writer_race() */ static void writer2(void *maple_tree) { @@ -36414,6 +36429,10 @@ void farmer_tests(void) check_spanning_write(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_spanning_store_height(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_null_expand(&tree); mtree_destroy(&tree); From patchwork Mon Apr 7 18:40:59 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 14041525 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 93AB3C36010 for ; Mon, 7 Apr 2025 18:41:27 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3CF326B0012; Mon, 7 Apr 2025 14:41:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 358D16B0022; Mon, 7 Apr 2025 14:41:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 112B96B0024; Mon, 7 Apr 2025 14:41:20 -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 C5C896B0012 for ; Mon, 7 Apr 2025 14:41:20 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 4C395B2545 for ; Mon, 7 Apr 2025 18:41:21 +0000 (UTC) X-FDA: 83308115562.03.39B2F34 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf24.hostedemail.com (Postfix) with ESMTP id 50C71180009 for ; Mon, 7 Apr 2025 18:41:19 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=FmgqflRL; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf24.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1744051279; a=rsa-sha256; cv=none; b=IVhB/u44SKvnx+ZqROO5lnLXbefQG/+NbYoyOdu4jc7L5M0O0Z9pNIVTcILBlxOaPnKQLK ZilOTHtO9kj5FpB8DS5kF/UQf0q/s3ehK2ma5DwOchSm6/BnOO4OChhbypHyOsVyoxEb/c dsLNa8lTLtxio4KNxy7LgWZW9FMLQwM= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=FmgqflRL; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf24.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.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=1744051279; 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=zPgIHOrW9aCWrw2poxjwCKw+rbRXEoMh5Fvuqu6qsfk=; b=7c2Ug+m5hEzpZLRscUt+afKYs0+A5Jx+JZPNexv8CKScgChfL4nyhQsq4VItIADXIQYi1R J/vR7ETNqttibvvvmeQ0A6Ee9qpOmkH7AMe0jYJmb6V5nKTYbs3O5iED6rYBkm1+dvCwBa G6CSJtmlpTNWxUFuO0r9FJMTub1uNbI= Received: from pps.filterd (m0333520.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 537H0hOE016137; Mon, 7 Apr 2025 18:41:09 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=zPgIH OrW9aCWrw2poxjwCKw+rbRXEoMh5Fvuqu6qsfk=; b=FmgqflRLGZ01AF1WQxeCw 6nOrQn69vTM6/PlfYpTGMY0GR1PqwV81HHaxF967xp4x8m3RHFqjaD2qJh7839cb rReMg0OND20tn5mHZ9/cueRZZ1Aef9gGhck++AVU4bau6tzMzEEKkAe8W4xQAiqX x9QQJaxcYMp5pQ0SLewr2+9HEbR3OdQlfQ+ac1Za8qtkHsTaflG2k5jb4kNqZpgS KSO8m8gHXOcVDVNk7wj3NdKIVvKrERTolNqLWmBYOzOH6v6uVbxYyCGd9aLb7qcY OIfs8tqOA3wEU3MLOBnQW/3B4fTgLPWsOZ/Q6vWg2mjvRKR6cfDhBmYUYG7AOwiv A== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45tvjcua7d-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:08 +0000 (GMT) Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 537I5Qfn023786; Mon, 7 Apr 2025 18:41:08 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyefwsm-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:07 +0000 Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 537IY5DV038909; Mon, 7 Apr 2025 18:41:07 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 45ttyefwqr-4; Mon, 07 Apr 2025 18:41:07 +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, willy@infradead.org, Sidhartha Kumar Subject: [PATCH v4 3/6] maple_tree: use vacant nodes to reduce worst case allocations Date: Mon, 7 Apr 2025 18:40:59 +0000 Message-ID: <20250407184102.2155415-4-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> References: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1095,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-04-07_05,2025-04-07_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 mlxscore=0 mlxlogscore=999 suspectscore=0 adultscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502280000 definitions=main-2504070130 X-Proofpoint-ORIG-GUID: adnJPjtgQpvg9TEHIQY65ZKPPW9--LxP X-Proofpoint-GUID: adnJPjtgQpvg9TEHIQY65ZKPPW9--LxP X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 50C71180009 X-Stat-Signature: ajzg9h94qwawq31q44feosmh99su5waj X-Rspam-User: X-HE-Tag: 1744051279-644702 X-HE-Meta: U2FsdGVkX18yaF5fPHVXFBW31n2nTlcDo0uLlv7Em/TrYGMyzqtloLACQKIwJVALkApaPwUTd+DGRvHYxWzzzHO4KbNZKbEdcymiWiK0oCTvPmaRSDOJcTyWlj7393x1K1ZNEMsB3IByPe1TI/SKo8HDihLsR1ZB/94lRMb1inERZdQUx2XZPplcGnQZAbjgLMuOXPfOwrNudxU2IaP/hF5HHuRL6xU9hnBth1guDxeVhkPajnGGVChwgsbUJXh2Nhn4N7+alQpGweEQJlU64SgQ4c8lislShwKjarmQZbdefNHm0/oMsqApLhfXxCQl1ieRZT12xivIbL3QSuNn/bbnIc+Sdu1kmdQNHcZvPzDH/iRHfw0Sx1CSvt9tf7Vv6XCRd4rnfC2RWsziLrcZMVZF6L5pO5d2AGh9q8J8V36BE/HzL13Hef9CNq5DP/wKc4Xi+CwLVfx3PXpzMwXA4LSUOLf9DsV0W2VZyJ2ouHq/3ooNzKgsg6R6rvsSOV4XIQ7ShLGbpKgmYzt46pm/9kln9MNkhY27ck6vAoznJAAMr2MDaUSMGE8eWTWSpOp5ZE8Trvi5yDU0FdiQQxJgdhpRqeC1YomhLAQhnCOQoQ0JfRz6xGr+rfBKHquX/xm2NqwZTS+pqJnh22qMQF+tmFEtv9ZEYC3UlxbBrG1jWdpZTHqchfC21OYlPqhWuHR6uL3Yh6/pN8sOfv7FRoZykPOrRA7A29lgnq7Um4E2gQv+OD4RmNU9FVALQp7QpaB2h39rzK0G9OwC61ZVkr4BBEtS2mUQejGr/Mk3wvYBQpWc1sX9Qk4uwYRRLjSnER/epL2jnYGdDJioDLeqvEiFCcOZLl0PNDky2NXtSkeMhwzzOhoufjCzfacfZLFdUHJULLg+yfuqkVlAQ33co4UJvz1WukFZFk/4xzhBVomiUgA0i9HeBx9wPgBRfHfXQGF77+0cgkfy1PRxI4yW7ym WM78W20A 27SiRUsNv1sC/l9wb+/FV4X7Tzy3V/3ryIyvb0ImXdiBk8jJY969SRiJ6Eod+yYR6jWQ8JpAESY7NsJ0qvv91n5Zr1eRvGwi+ErNI5GH9bxKa2CC9ATMKFyRfmuUxSfMDLS3G3vb7XxS4A7+6tQKfjHEhmBI1W09uJrU2HRYsDRpoK9YQFsi8rFaLxI1KgzwcV/HLL2JuemiR4iMQtSpQ+BfibbE/Ni5FnRqy7AoNkswE9VzPgwzI3QkZvwTRabDHz7WAvhSx7e/51spN5dvNUADZ432i8BsEiXsA 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 Kumar Reviewed-by: Liam R. Howlett --- 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 236f0579ca53..203a1a529884 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3539,6 +3539,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); } @@ -4154,7 +4157,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: @@ -4172,13 +4177,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 e0f8fabe8821..e37a3ab2e921 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 Mon Apr 7 18:41:00 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 14041523 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 A8419C36018 for ; Mon, 7 Apr 2025 18:41:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D22EB6B0011; Mon, 7 Apr 2025 14:41:19 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C81616B0022; Mon, 7 Apr 2025 14:41:19 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 9BBA96B0012; Mon, 7 Apr 2025 14:41:19 -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 75B066B000E for ; Mon, 7 Apr 2025 14:41:19 -0400 (EDT) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id D3F72AF7A0 for ; Mon, 7 Apr 2025 18:41:19 +0000 (UTC) X-FDA: 83308115478.18.C035A8C Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf29.hostedemail.com (Postfix) with ESMTP id D6BB1120015 for ; Mon, 7 Apr 2025 18:41:17 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=BhL4SIzl; spf=pass (imf29.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=1744051277; 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=EcVeW3eFU2ClmEtFd30xm3FtUPKd3pdiQSzgw/fblBc=; b=iaF/Ni7wqQv5py1VEuUVgzm9epxctlkfk5e6DE+tbsCjtJa8ngasLzxUsS3TsiD2uU3bcJ 3gWe4e+MxhgwrIw4fRRkVFzQYDVUPS4YBvCL32VQ6+dd49Zk8R9PQYr+NykXwu1owue87s X/w0RoZpzecslxwvSBbXOqVYlAoh740= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1744051277; a=rsa-sha256; cv=none; b=63MO8UZ8csiqGWCvV8XVIpf+0Zyz21RFQbzyoQxTCp7dASEl1WN7ypXM6IIORzIFluWrao 7OUsrV5j/BW/5eJ01ocYB7iYpS0Z+a3bYI4CU9ZPtKAxm5zuSfZF0rpTPEs2sLzJt1u3qt I3Uz+qSjPetadB9hkpqPsLgYHGir4Js= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=BhL4SIzl; spf=pass (imf29.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 (m0333520.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 537H0vkg016513; Mon, 7 Apr 2025 18:41:09 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=EcVeW 3eFU2ClmEtFd30xm3FtUPKd3pdiQSzgw/fblBc=; b=BhL4SIzl59d7zOiRob1po zizBb6ocwIP924Q40aoxFHWPEYbJc5eR3p/GRvegxELNMPl6Hr89qESh01qT0NE9 YgC4GP6ZUzmN+gJEsO7sqie3ZgFrp1OejeNIjvPf8b1BA2ZMSd6GOcsWGjZZth5q /Nku+BN3siIYHby7xUP5HEKiaYRR/nqGuX9vkYzq0u0sNr+De7kZ6T24gbCQil2H h0JarxHjclDfgqs3cc5XGVwfgOtvLzk3NyM2t+sH7Hi9IBMGPgjjxE/QdUc9+3hi VHE3RrTSU7CYbParP4Rh62go4F2D8o2dsqaUi7hV641XzLDA77w2WtU+ABbom82K g== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45tvjcua7e-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:09 +0000 (GMT) Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 537HGJL7023953; Mon, 7 Apr 2025 18:41:08 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyefwsw-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:08 +0000 Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 537IY5DX038909; Mon, 7 Apr 2025 18:41:07 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 45ttyefwqr-5; Mon, 07 Apr 2025 18:41:07 +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, willy@infradead.org, Sidhartha Kumar , Wei Yang , "Liam R . Howlett" Subject: [PATCH v4 4/6] maple_tree: break on convergence in mas_spanning_rebalance() Date: Mon, 7 Apr 2025 18:41:00 +0000 Message-ID: <20250407184102.2155415-5-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> References: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1095,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-04-07_05,2025-04-07_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 mlxscore=0 mlxlogscore=999 suspectscore=0 adultscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502280000 definitions=main-2504070130 X-Proofpoint-ORIG-GUID: U05rjn_-aW1IcL7szSOtuziPGQPgEfqg X-Proofpoint-GUID: U05rjn_-aW1IcL7szSOtuziPGQPgEfqg X-Stat-Signature: r1saj1rpdrys61144ej1thyrx4n8k37o X-Rspam-User: X-Rspamd-Queue-Id: D6BB1120015 X-Rspamd-Server: rspam08 X-HE-Tag: 1744051277-362403 X-HE-Meta: U2FsdGVkX1+MZGHrnLcTFJjX2wFMW0R/5ccdCPOiS3etrQUezh7FZGwn2tGYgBNYcAPPu3YZlTJ67syH03Tq0/WuVrfDTCnq6YihAqaGG5VXipgEIvs5/ZmhcJznyBfWp1f/1UpPJTMSQKNGiLI3GI6rVy2D0wcmy5mAz7eWok5eS+x+ant6wnKidIyozq8SAhprB274pex2HYUFPblraA48gdD/jIcQNvjOIDlX2Jo1C7En5t9TUx+ENJNwvsEGlvgyWJkyj5xRL4WkP4RV3o11LhoDNo3IAaG6o1YoWqE3bRIHwW58Y383ecT3J9x+uzF/2C9uT4qg1bMPPEP1ehkTX0DLqtNRrBBP7rgcT8JYZjyysg1B734HA/8/3KmNOZ7NAWoytyIdD//l+jqoboMJd5s1RvjQtCoQfpGZ80umyDtftmriR4lL3bArfB3rbkybcdQVgQbJbNtKMOyscTIiTzIlxtPRIqfcwFn6Ih+R0oTPOsf2ZQo9i+iuTS6SZ1nDvLasuhM4ycwqh7mgHSIkmy4umnT3XSz0z07Egrn8GAmgETVnppaeY71CFv0M4FGxjPNOiK2RrcXgjk8hPWi6fRBJV+pCHLjpThOnS/uKNrMLId66BWLkLlOeXzncdP2u+LCz0a/j+UUTGdgniX2UA0Xjklx+pd2DQFoUdmTQk8fZRq51FViieLQc9JaaW+i75M0V+GG0B85PFhf5nuZMTN5m5IAmO7W54DZWEu0DO2tixwOem9LaQ2/cgqJtNw4FbWjSzKXRf0PxuSDgpKA/BRElAypEdYshFI5tu6HlL3HY/mrbCoeqAEcOp6DFhXxVkw8JNzHQwLlSZvSwwasY4ijzPebJLDZW/CAGMRwK8+bTqeTbf1mX1IEbP1U/WPJRrt9qs0BSvTHExG+nONUTgwBLI2WLQ8S4VFUJ4lgPmBDbvTFUVeY1XOIgi3W7JW90XAr+GvoNABqKV3C fo73fcLu eos7zf4tPNi9t2VGxcMcsFM9V2rFHeTtwi3rNKIUDtqhFJ7gm1AOSXh88Zz6MEnhzwxtx4SeUWQcsGbvKVKlltuhZVTBCx0ZJecQZMt1SxIk+a1miS6vdZ1VZVlGO0pNGYyPrPyE5OkEb3bkmizWE/FOV1uRMVnIuG5JDWp2usncV34qL4QLBCxmuuaircaQKmTU7DEXqYMbvq1lz+WVx34CLxIZ52d254mHCq4ZpXlYZWnIm/9Dm1okCe2SirMFjEvp6eTPDGb0nBYTVq9JWA9uLoRsiK26rSDcxCJ+BYGFsIDj6+OCAYvLO3qDAD4eP/gCNPINoDmanZKWirPGiqKpsmcCVE0ZfmUl2iNtT65iQlU2RqSTVj4N9pICzWYrHYM03 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 | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 203a1a529884..acecd4e8a6a0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2895,11 +2895,21 @@ 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; + 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 Mon Apr 7 18:41:01 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 14041521 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 EDD2CC36018 for ; Mon, 7 Apr 2025 18:41:17 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0D8A26B0008; Mon, 7 Apr 2025 14:41:16 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 08B466B000A; Mon, 7 Apr 2025 14:41:16 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E6C0A6B000D; Mon, 7 Apr 2025 14:41:15 -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 C32506B000A for ; Mon, 7 Apr 2025 14:41:15 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id 3D2C71CD511 for ; Mon, 7 Apr 2025 18:41:16 +0000 (UTC) X-FDA: 83308115352.19.302BB41 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf18.hostedemail.com (Postfix) with ESMTP id 3A1B01C0006 for ; Mon, 7 Apr 2025 18:41:14 +0000 (UTC) Authentication-Results: imf18.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Le3wEsMy; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf18.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=sidhartha.kumar@oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1744051274; a=rsa-sha256; cv=none; b=Ot2vYS86GhewTItrShGagXF1j9pMkAA++v2PSKwH73MjoU99smEM0f3iFoZvTd2NQjU9NX B1tY/nh0A9nj4xTkjyQsUrRa187FfwkEmAdPj2TXcgZkqy+niwDEUglosSfm690dqT9Yys 9SHLpZllwZvB90fZVLf/1+azDG3lB28= ARC-Authentication-Results: i=1; imf18.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Le3wEsMy; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf18.hostedemail.com: domain of sidhartha.kumar@oracle.com designates 205.220.177.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=1744051274; 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=BEyayAD0n5OcCAz/yUgOyP7rLNtsr3FbNg29L/u+Tug=; b=ZLU1CqOQf1ZAYyvWTbWCU7aecpT20l9Q/K4nC1et/yxXmSTVo/UsTWy443XJ82iGjw+Euv Q3gG9bp7zgmndJ8p43oHoOMfTiXcQwutO7ZIHom4ELlFweEGxXuzrLqo6Y4ZAVXI46XgYL E8MvJIucYT/jgHZnYP9yBbH6g6NwwjE= Received: from pps.filterd (m0246632.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 537H0iZX003422; Mon, 7 Apr 2025 18:41:09 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=BEyay AD0n5OcCAz/yUgOyP7rLNtsr3FbNg29L/u+Tug=; b=Le3wEsMy5235U8G+otW6r CMSpM0WxFMzUXv+eQ9tDaGvKVSJmJYfWh9ew+qDmUU1DP3gRK1xkWcx8wOgo9zf2 yPHJhNFIh9IVIxm2NLajqXSsSWLVePC9ecTC95t6+1q/wFLqoW4P1i9h/3LMonWr uYGdcjY+BXGzSie8vNADxUb53gDYfQIKZg/LpLGei7GffzOUsyYezVtmpUl7n2Bq 06N0uepefw16NizkdirvQYtSVd14TA4kZjp4FuPcfRIMXtBnimM+dsmcMi+6PY5K aI8CXYLoWGi8meWxQP8rwktTUp4j3GkrJJFl/LokC8JyF/UC4YVGiP3qLxWlWuvH w== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45tv4su9ux-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:09 +0000 (GMT) Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 537I0VB1023792; Mon, 7 Apr 2025 18:41:08 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyefwt8-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:08 +0000 Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 537IY5DZ038909; Mon, 7 Apr 2025 18:41:08 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 45ttyefwqr-6; Mon, 07 Apr 2025 18:41:08 +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, willy@infradead.org, Sidhartha Kumar Subject: [PATCH v4 5/6] maple_tree: add sufficient height Date: Mon, 7 Apr 2025 18:41:01 +0000 Message-ID: <20250407184102.2155415-6-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> References: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1095,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-04-07_05,2025-04-07_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 mlxscore=0 mlxlogscore=999 suspectscore=0 adultscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502280000 definitions=main-2504070130 X-Proofpoint-ORIG-GUID: auY2qp1JnqR0C1Y8Ld-Vefhdvcmn2wNM X-Proofpoint-GUID: auY2qp1JnqR0C1Y8Ld-Vefhdvcmn2wNM X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 3A1B01C0006 X-Stat-Signature: 9hn4qrrc8xsaybtnrwpmsc5ttchehodp X-Rspam-User: X-HE-Tag: 1744051274-275150 X-HE-Meta: U2FsdGVkX1/AftVn79G8xlt5SZgw8agx80e9fv69e26S5d8LPdJI5hXdF0fQ6rE28IsjhR4DbfYcEYwBwK//KxFDxzVYGb/p0XnlzULme2gAqYU+BpwJw5aqkoWkK2VW8+rvLQ0pHVOBsU3OFy38hwL9UdZHb2yiDUNfOkvcf7p3m4mMOrunFTvH3jLHEm4D4scxUKDSrUkYlOWi8l9uQyrx8P7b5/FGnlgaCDIihZ9nF5FssJx1e1BExWUYA8qbrUXR2uUS+psroJOm4f71ypYOMCSSGOunXoDaUWmc6HZj0VxFP32hUhGJpOAbfG4C8RsMc3CloxYolbd4axxHXq99EMfcuq07t7qGnUbYstDj3eXdQpTHEImqvkawfmwpBP66xxi6fj9XchBwld/l3/5QG7V9mVXyzbcXaZ1vvbox8NhbBdwPDWsi17ACSvr8A975EXMan0CFdcWtJjjYUa/msFYqpoALw8tIb54dX2FOAqvNzwrjDB/W03d9lY+BT8DjWVM/GeEl9rgILAnOqzc2YiBgxWCm63iyueGcpKcSEskeOJEtpSyxG604t996aEaK9VdIaGn+U40JAZJvK8k4yitcEQFvqojD+R61N315Tt+ftRxBpLro9G3Sfp9EOlbPKjjy44svFpJLZzGIG6Uj/9WxuXYkyHoOfnoxC6D43yY6fKUesAaODuEenHshR3VTlBB5ck2XyXAymWiWG0uLGxsRBzz/9gsMD0PLeKaPkdviIskumDcKdrYPFEX4Cg1IKNA+J9bSJX75qzYPpVjwsD5JFpZ07ADu40OW/TFVv10QHvA9za+VI0MQznCZL946oUmhrTFWfLwUxwehN5buq57VzqiEAd3/oFIflsasm/6xxXih3f7pbs37d+OA4Ds0hNje6qiOtDwOJsDv0RykLO9PTcTNZiCxZjYEp91xlDBSWs0tQP1QRKNt7uGLLCCv8iS7MgEzdUora8q EYhGVngN 2gtsWE0hJOChGh5eKTGwUS0Fe4CnFOYws0UPZcVvjk2g+GKGSte1dmFZ+BPIxJ6dzMNmpnvqcjBAL/RKnjL6AbLuYaRHCbKrTwDjxcQKS0eZQxz/h0u2gOV2BfZAVgIgATmDJ1QDtjHyZ0iUyJSCOUYr9DdvKVZidCyEaYDoA7nmajeTnbkaijm/sTZ2VwGj8twmlQZvhubBk8F6qlWoMeivxup6kYS4tvplel2c05fAMu/LkgV+wtVgm4CDjRvqg82nj0G2tEdf/ZFLcx47m8j/VcU9csocig0vT 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 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. An off by one bug was also discovered in mast_overflow() where it is using >= rather than >. This caused extra iterations of the mas_spanning_rebalance() loop and lead to unneeded allocations. A test is also added to check the number of allocations is correct. Signed-off-by: Sidhartha Kumar --- include/linux/maple_tree.h | 4 +++- lib/maple_tree.c | 19 ++++++++++++++++--- tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 47 insertions(+), 4 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 acecd4e8a6a0..98b06709d864 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2741,7 +2741,7 @@ static inline bool mast_sufficient(struct maple_subtree_state *mast) */ static inline bool mast_overflow(struct maple_subtree_state *mast) { - if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) + if (mast->bn->b_end > mt_slot_count(mast->orig_l->node)) return true; return false; @@ -3552,6 +3552,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); } @@ -4187,13 +4194,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 e37a3ab2e921..2c0b38301253 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36326,6 +36326,30 @@ static inline void check_spanning_store_height(struct maple_tree *mt) mas_unlock(&mas); } +/* + * 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 6 tree */ + while (mt_height(mt) < 6) { + 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) { @@ -36496,6 +36520,10 @@ void farmer_tests(void) check_spanning_store_height(&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 Mon Apr 7 18:41:02 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 14041524 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 1B97FC36010 for ; Mon, 7 Apr 2025 18:41:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 173026B000E; Mon, 7 Apr 2025 14:41:20 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 1087A6B0012; Mon, 7 Apr 2025 14:41:20 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D1C496B000E; Mon, 7 Apr 2025 14:41:19 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 927A86B0011 for ; Mon, 7 Apr 2025 14:41:19 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id CEE50578EF for ; Mon, 7 Apr 2025 18:41:19 +0000 (UTC) X-FDA: 83308115478.19.A1EDF5A Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf11.hostedemail.com (Postfix) with ESMTP id D3D5040007 for ; Mon, 7 Apr 2025 18:41:17 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Ja+q7cue; spf=pass (imf11.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=1744051277; 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=+W7ISdG8szb9zeJ330uZlJcsSPgv9PK2sFXgns5vqWg=; b=cnFqg3Iy9oLVoCPCS9c9Mz/kVTZi40noQSPsBjrsOl+2vQSyN+LiDuNgZYzo4Jxa6PjPH1 3eYNfCdhlyEzO9RjVQeXwtXEBOX4Q+zDmC9J2Z7Lk/2J0fnPeTq8u0M/odrH9RujrtDER0 0MhGiROf2TAkHqE/OFLeYKx9L0XC8l4= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Ja+q7cue; spf=pass (imf11.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-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1744051277; a=rsa-sha256; cv=none; b=bljbNrGyHtAYdU/M5a73n5ZWyAY8L4twByT11muXbHLhHt4dRI/zlVczEZUnStqj0tFu06 gPkwh6f5WLoWa1H+2DZf6xbfJr3aVdftsTlQV7wGOr8IyLmU6pKBHcaS4zMvktyg9+3+p3 lfNrqp/PZVRVXW4ZGBiZWojwO5aG9Ho= Received: from pps.filterd (m0333520.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 537H127F016641; Mon, 7 Apr 2025 18:41:09 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=+W7IS dG8szb9zeJ330uZlJcsSPgv9PK2sFXgns5vqWg=; b=Ja+q7cueKl5J+zWvTjdt9 8eAZR1+yo0XRy5GEVRw3njJXDoAMZXHgkVTzHhvjDprVluZo9N57QsGSKyWLey3y dv+p+ag9up2cDcgR/6OO652Z/GqhRk12sgfmuaiKC791SY4cnoBwiKzc4RpiucAl 5dqdKzgvV0SVeFA3RwFMKEHJBtYcYgXzVJR7dOhilu1VN1Bk4lBCbQ5OBtxUUOiC kYa7SXnDAkUeTXEdPxSxQ3uYHLYltpHGcigllgUasoYlZX+cN1Sk/4x+6+dpaX/c XfKORTv1RSOhriGLM68X/fs6NsogDfBb9ird6/P7BVpMz28OJAb5Fh6FRA3e5a8A w== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45tvjcua7g-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:09 +0000 (GMT) Received: from pps.filterd (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 537IbAYh023937; Mon, 7 Apr 2025 18:41:09 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyefwte-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 07 Apr 2025 18:41:08 +0000 Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 537IY5Db038909; Mon, 7 Apr 2025 18:41:08 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 45ttyefwqr-7; Mon, 07 Apr 2025 18:41:08 +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, willy@infradead.org, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v4 6/6] maple_tree: reorder mas->store_type case statements Date: Mon, 7 Apr 2025 18:41:02 +0000 Message-ID: <20250407184102.2155415-7-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> References: <20250407184102.2155415-1-sidhartha.kumar@oracle.com> MIME-Version: 1.0 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1095,Hydra:6.0.680,FMLib:17.12.68.34 definitions=2025-04-07_05,2025-04-07_01,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 bulkscore=0 mlxscore=0 mlxlogscore=999 suspectscore=0 adultscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502280000 definitions=main-2504070130 X-Proofpoint-ORIG-GUID: BfDzaKACSBh63y6jvwJTyYULhApBmvAO X-Proofpoint-GUID: BfDzaKACSBh63y6jvwJTyYULhApBmvAO X-Rspamd-Queue-Id: D3D5040007 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: 3j6xfiga7pan6w97hicwfwa67rpcato4 X-HE-Tag: 1744051277-619081 X-HE-Meta: U2FsdGVkX1+JomvS9s7Mnws5JqPofvW/BXhndOeQlX+EkTO6q6hn0C6D6X/hBTt1Fwanb03sMVCYnPsLgiUEQiD7Z288LqYKBLlXP0gNvD+I0acuI7T3SMZwqRQDmks125qQCWmIKI5EojGLC2JY4oZDJP595kvXwrf6HCsZVkhd+R9YlfuN/2ElDfL5LzcpJ6uUiXkYEB8zCl5PecH4zspwM1J+D1FN8s9TY+PCgHYuaNIML29EQo77SzTj3QOmllnnnXowdv33TA+GG1xzJeMBDvlY5Ik0XdI1Wucxbwn3qBouhevb9WIC5RWYH3A5+E0Zzr3owm0/0N65wpCiImQrewhV9iDXIpjJ9nGjGCCV9LquYim6d4Ndk11/xZPm1Y0qBTYpYLSy007V9rOpuzg9sbcSDgitOvCTXkIWVQkuoef5/rRw78hc8h7JZfZT8WSeD95VXVrVfLsqC5WjWrgW3VNnfT9OjyA8EtIhrFCJmbbZLASYKY7iwawP9EftYHieIr7LWtLJc9yALK2gGDkKtordg7XGRQ5s6yBrVR9gr5H00MJhDkeUaUmCqXhcrNsio3B+bKPZo+H4DzSwayJFB5DuiOPfKAvHuVWQUKgMlDZXbOe8+W15VW6WBnrTCnZJSBP2Ksvm/4ZG6nFwrVrYovhIcVzWTmk44LhdHLluBUB0yRLrBQz7STnHoS5OIy8a01UTWeuuC7g8P7D7VC9dqiw7dCvA17d0YpMEg/HVa83Eq2XDuZ5X4g8ndR+Xlm3baKdkbAj8uYsUweHRAirwlYJiunFHk8WJrm9pfXsflW7PgUu6/6l11skPU85/NNiHtlvxw0iCDoKopEV+aJpwnlrCkZSGNJLOwQTlly3SbcUu+uLpnxIln9F0mQGPR2h2fZb6Q/vMNLAKxmyGw3aDghkCls8+ZkxH8uZwb9+9bZ8x35Ue04Yf8kgZkLjQ552EwsuYrIwl1dC+eO7 skeGbp8y wUQAaup6Rbe2YOOJNAoTptZw8TNrm+DNfZkmIsTCnKILQGtRDsKBpdTDtlv7cfcQhAPz8RpotH5Nc2WT5Xt7mPpoK8IA5/8bvIxeRnPb8t5QjSQ4alD1737+n/UmcsxioBtYK+hd2f1PXU8nyBaSxzlrl+lw9gPriUS469xDihJihcadHFuTpZot2M+UwvnTtlLmn0TOLJjUcI0AaRNtnTQLOwdooCLMVjamn+BAv7ONC2+bIEUBHdtSp+JnG0ccmSnMGoxG8h6VlCVxaKEw8Z8NRW3b/Cc0XEKnvPHa69K++cCYAoaUuHyL9RQ28Cws7WO3azWgAjJAoaqU= 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 98b06709d864..8425728e3c5a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4085,15 +4085,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) @@ -4115,6 +4106,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; @@ -4179,19 +4178,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) @@ -4211,10 +4201,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;