From patchwork Fri Feb 21 16:36:05 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13985960 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 27B47C021B3 for ; Fri, 21 Feb 2025 16:36:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 97422280020; Fri, 21 Feb 2025 11:36:33 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 8FB3328001E; Fri, 21 Feb 2025 11:36:33 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7275E280020; Fri, 21 Feb 2025 11:36:33 -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 551ED28001E for ; Fri, 21 Feb 2025 11:36:33 -0500 (EST) Received: from smtpin10.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id BA2D41C54CD for ; Fri, 21 Feb 2025 16:36:32 +0000 (UTC) X-FDA: 83144505024.10.F118966 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf07.hostedemail.com (Postfix) with ESMTP id A74C740015 for ; Fri, 21 Feb 2025 16:36:17 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Ei8HKgFY; spf=pass (imf07.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=1740155777; 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=OSOzaBP2cohPw2EjUEbuKxDUw/Doi0XEbeFRJ2RbVEY=; b=cwt9guGmxRTmedB3uzjTU0j1wi/wGuYPVA+0BnJCa+GNMny0cE7JU7PrlFm1CfBuIUxeQh YKY/XFf9ubnqOpcOsnaIWe11LW32tq6ygsHdcgWA1rn3UxAAc9ZtI4z9S9NcluRqcFhRih uT5UQoJtSxcWqDjKwer+8CXXeM3M6sQ= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Ei8HKgFY; spf=pass (imf07.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=1740155777; a=rsa-sha256; cv=none; b=7PqIT4n1XVFBpYYhMkmL27eDBmK5Bh+R04dlnheWvi8LIggpWFGuAmnfk8JdOAcybX906/ y/zB7u81mHM+gS/YFZ3lH8gO7wu8+VBX/6n82PIRuWtu3Tzp9Qqzu/j2Eq6+xA0qjZAQVY QT0j9nJNXZ3NNo7UDAabOOuJOwsRk4E= 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 51L8fcjB027789; Fri, 21 Feb 2025 16:36:15 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=OSOza BP2cohPw2EjUEbuKxDUw/Doi0XEbeFRJ2RbVEY=; b=Ei8HKgFYYeNWmmDPvjg9B uxS5b9LyQpXJBrZOjtYjq2p67cIBhQPktSsvONrPvgNiZxtA/chdsRIzd14HGAd+ LYazWaMTqguu2wbMtCCe4IXYCMn1bC4/sUfuYxTKjUlAYO1deIGQJv/SKrHOeBh2 3hqmw5Vkbn8T/yw2hwrWZYv2WsEDR2cu0Kwab6KoIjUJTaWTd9kvN22mY/2RB/pY oiYPyMhmTctbQKrTYPkLF/GzyqSJ5tC6SHL/4j0FOaNdV9WqLnq7cThPSo18pbnu 9lD/hN4+8w+cjHzMUGnEfiiCoXEjjr41ofSq3cOig0Ebe5fpPr9kwocRLcYB7qRK Q== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 44w00pxkrp-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:15 +0000 (GMT) Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51LG8tCv010613; Fri, 21 Feb 2025 16:36:14 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 44w07gxm75-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:13 +0000 Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51LGUIXD005786; Fri, 21 Feb 2025 16:36:13 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 44w07gxm69-2; Fri, 21 Feb 2025 16:36:13 +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 v2 1/6] maple_tree: convert mas_prealloc_calc() to take in a maple write state Date: Fri, 21 Feb 2025 16:36:05 +0000 Message-ID: <20250221163610.578409-2-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250221163610.578409-1-sidhartha.kumar@oracle.com> References: <20250221163610.578409-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-21_05,2025-02-20_02,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502210118 X-Proofpoint-ORIG-GUID: QQWwevtEjJ6ySVkZGd0LJ4o6jKJpWsOs X-Proofpoint-GUID: QQWwevtEjJ6ySVkZGd0LJ4o6jKJpWsOs X-Rspam-User: X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: A74C740015 X-Stat-Signature: fooht65c1ttijz15gy4sgrh5dazfxres X-HE-Tag: 1740155777-553773 X-HE-Meta: U2FsdGVkX1+RldUyUpgewk7bG54cjL8Txr6G2byYbogLo+3dYeJ+mbqiLACeQ149uaNveLaZAlrR4PqJav3oZ5vPAga9OxlCHL+oON5B1J1Vx1Pw8hBAFO3rYmwXOEHFbj/I9eHcAq/L3uy/FAuH9NA75XF5UJeafF9rKEO27NArD9igaDeadH5SGTkVQtMMmumWExKs+jqVQ6v2ZGGbuOhQC46Z9wVn30JF96JmeZhs3N3U0Xhdvf0CoT4BsIYhTp9GQxV5bF+27Chl19RvCryPWYEWCWgqvjR2ArvsiAuVeRqVs1jRGjXQdWNTE20jkSkTIsjw363/0FSOC1npEAu6/7levczj+zgXu/gY0t7OtRkjMAvzJKHeRT7EUDS2ORu7r5S/xNIbUT5EDPxOwcAQR9osSkRkxCcLgfm9nqu5oriQqV4Gg211HGylOmGnnrh0Yw5wYrGYCCeXyj8xGeeS/3Uv1mIg5tDWegM5lKHabrVSKiYi5BtDT1R7raVv4qg2I++oBomN5O69I2ZL/KnD57DKOleSj4VDv64VTLIYqMrnlR2z3orylwA/e8tUa81G0+eP8rRke6Z/mknw6dfg+1wz5A+IbTsux6zJCk2Px80fTcG9sWdx+yBN1FgGoi/OAC/85Oy/DQzBkbspJbc5lBP211OKvBm9RdhYjUmvSxw8Omzs3Y8t2RcaDMAjJE/ijroGH8uNlMJTT4IjyVqF17VZc1SqTODzbpgqmYB3nxBtb2cE7xnNFdJNI28+mLK9s3t0M+TfFrcIcxl7r478Z+aKax0AlBajwNerCEEEIaHy6+26o+bUEG+FYckSHSYxAwMQ4vdAki6AZQK+pT0vURHJlQmsobDgGEiGta2Vzkq5d7CH7LSBetdRxB6Vs0GBykDLlXu5sAQZ7qdFUwC0gOkgkV3yxy5TDIgdgiTd539cJfRnoc/f2WrXIKTMMoEuuDGD7DRsbUWbQtG k4PVvJHS Nw9SV5zk8Fe60QrX8p1YMWK6MAXns+fWgrrmJy2A7+EXX1Q/DrGKAZ+9BbnWRBBnXKO2Ov7gWbxYqLc6Ygd5tJWsW+QGMLf1tpHjEC93suhU/uHT/HP/YBp+TSTLbHdiO6xSMwpZPMrIIRkg204AF84pWReGdSn3kGV12H9jjXvpLJ3Y3LfOsvBdTnRqk/bkt5kIdgy/O/rTjjek8YBEYFY9zBA+Wq1Emd/a9b84IT6bHo4d2i0s5FgSiXBVc4Ht4uZaNc2dWDz7GO4+tuebZpoaiLZmGvjzTp4g/ldZ+TvpxRFjEj69KDYLWyOwYrePHRyjHXKXGzUi3OTllNlSV8EWbPC6upLdjOFG0TnO6H0QOdP8= 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. 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 Fri Feb 21 16:36:06 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13985957 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 212EEC021B3 for ; Fri, 21 Feb 2025 16:36:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AAC4B28001C; Fri, 21 Feb 2025 11:36:31 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id A5B6E28001D; Fri, 21 Feb 2025 11:36:31 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8D50428001C; Fri, 21 Feb 2025 11:36:31 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id 6ED8F28001B for ; Fri, 21 Feb 2025 11:36:31 -0500 (EST) Received: from smtpin29.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 090DA817F7 for ; Fri, 21 Feb 2025 16:36:30 +0000 (UTC) X-FDA: 83144504982.29.6B8D12A Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf07.hostedemail.com (Postfix) with ESMTP id 3905940013 for ; Fri, 21 Feb 2025 16:36:28 +0000 (UTC) Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=LAKdgRLr; spf=pass (imf07.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=1740155788; 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=WkuiNF0/htL3Jy07AyGdjLbsziOaDecoGSXXo42RYFY=; b=qB9zdo/ojyzZHgGS6OVMY8ERVG8AkP6rUDRKHm/Ec8qfkEcfHjSP909QEnIE7z1VWUmJQv VgNVYByiC812fjSDYjZRsR8qCDd9/otHxUpLFnPDLPqOfy+P6Y2X3YjSXHKtZEtqRoIP4W QuRKWY/9hb283iuP56RZEg+cfLx1u80= ARC-Authentication-Results: i=1; imf07.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=LAKdgRLr; spf=pass (imf07.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=1740155788; a=rsa-sha256; cv=none; b=55le06cAK4SmmHaTw2aRLCv0smgegMQztxYTshJnXS2jiqMf1732L2tN6IJRKCTNv3Iunj aC2bIVGrr/KJcttTkwtMQUHdIkUDaYHX7LFQyFnV8rD5Zcw+yZcGdyPYZ5AB+PrpQneR6u Hc/oN1Qt20wc+UTnpxqBDbSdXNwPmrw= 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 51L8fgYH002408; Fri, 21 Feb 2025 16:36:27 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=WkuiN F0/htL3Jy07AyGdjLbsziOaDecoGSXXo42RYFY=; b=LAKdgRLrAC/BSfmweyAhL ya1amcbQw3cznBRma0R/DfX92CL8ROQ6X1DGFY0ggSy2HMqBVtFlfxZeTRFCwMJZ N1L6RQNzUSfbAFW1D8VkvdJ8s3UzHU76xWrw12G7dwF1Yag+2+buX+y1scPYtupx +AiRYx+VC4ECIg8VkC5cEq0zuajx2A1zR3a57OT6BPkLLJFosSMdzkBnWtCvyUEw 9cZs1XCcAqz1dZYzM86Dy55EGyImkFZq8u8WdP0kQsNgMtMy/xEUID1LehRw9v/q i6a2h6amX/RWUWFRyQS0NLuFQ9OiipbkxrpQDDUM8K0fT3OUhj6LkBDYUzjoII7k A== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 44w00m6r2e-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:26 +0000 (GMT) Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51LFOUD9010486; Fri, 21 Feb 2025 16:36:14 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 44w07gxm7j-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:14 +0000 Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51LGUIXF005786; Fri, 21 Feb 2025 16:36:13 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 44w07gxm69-3; Fri, 21 Feb 2025 16:36:13 +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 v2 2/6] maple_tree: use height and depth consistently Date: Fri, 21 Feb 2025 16:36:06 +0000 Message-ID: <20250221163610.578409-3-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250221163610.578409-1-sidhartha.kumar@oracle.com> References: <20250221163610.578409-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-21_05,2025-02-20_02,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502210118 X-Proofpoint-ORIG-GUID: GV-IRD0oti9QoMeOwwqxiCKfSKm9TC2A X-Proofpoint-GUID: GV-IRD0oti9QoMeOwwqxiCKfSKm9TC2A X-Rspam-User: X-Stat-Signature: 9aiy435z4ofk1i19f4p59x3k6a7jbur4 X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: 3905940013 X-HE-Tag: 1740155788-188125 X-HE-Meta: U2FsdGVkX185QCrahwJlL5VVSw8WSPM211kKZy5uH4u5cq2OITfiv2b8HR8bcQXZGinm2+bUTI4BSWVTX5BUYW5ApJV63E3AaOpjHurtSWrWf+ObRtNQdX65NZ9V9IvfDkYmq7fMsFwJtaQtmhpnEY/CiQtWkmjbH7/1y6Lzjtep3WD5ETNhGJFBGv8wga+IG9P9dwbb7QREqRI/RKtF6pvoAFIoMupwNRrNcaQHyi4ldZlF9HOZYe+FofL3pxmksktG3RO3S3XzUxG6UtEIIKOhU74xzkzCb3ckA9pATOC8LKzLG/+uzk5TqDaFLzFVrfmm6cy4U0H1Hsk2UXCVvCWWore9zGDS5qUnF7ixg5snTQAFtLXHnvF7f01j4kJ2ArMxrvWM/wv8BvxrRWpZiDL5raWNEwX0Gvky6aN62wU3Z1gUsakvbGbUL/6RHg5mVqKAp13lN6Y3LSZD8mp/iBESpk0yZDpW1jyyUg8/6qPhQOo0TiHGC7ELF2oekWl+sQP5qFmgcdHPHsnT3tpMy8iTXi80R93oTwfBfhE2fwauo7zWrjE8HMsouwc3oCTNxbxqTmRz2sxUc6EwzoVTYt2v5Y26LdcTgOLKRSj/3qE4u2irzJ448Qo0PboukoGnMK9a64Y1+TyRTZgZJb8uPZsFodbKmswsEd9f1eWnNtp/OjaG0fmeh1ZtvzG7BHi2oVjM3stbDyfuYTv7szeLeZ5THaWcHe4IknnBLgiz/TO4b6SzdXKXLo9X9qHTrIwvM+rZQP7kosS07MNKQ0w1dT9IyUtQQl0+0DhBC33va86RukVyUy+tfd9gEe6dmzeBUTOkUyp5HocOx+uu35/NWxCEPd6GYgYyfP5Wo2b0oGT/dIbA++3d4ts2mBB3L+t3aLlL0TdBbBQfx7p5V9APpnbjTOfrt5gmWz267HcELLCn5J1sa3l20jrJjOIJh4sB+sR5/Yv0xRqm3HLlGx0 mC3uVmzP j3DF9RS15crFrmRqmw6NaujLb10ii1F3t4cHuOIWDhsbeEPz1W7StDvMBQ0j/d/M+WHVqoqr+4ishFLgUV8PFvokzJk0a+vkf3s0uYxyPuiQ7/uuIQ4OCUG97xMR46oJ077J+xgZbE1GQgS3XgjfKWufSnN3fqQh7AS9N5Cd2OAVfr1J3AIyQfmLfJKvax/NGqo4S4g0te5yV2c/e6mKY9cJm+AL/IGudF/SUhyR4mH90eRAYRD3QiJINyRJzNKRCW1CeF/Y0mNO0Gth6zbjsualQWxlOGeo6dDHQjhsSEpi7GGgKjUn2m7AHJFXGBcpZiGHlewoILKzZz0TCKkcpMjFpuIzZhrFqekl+QsenXFSXv4c= 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, 45 insertions(+), 40 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 0410e13a099e..d7dac3119748 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); @@ -1747,10 +1748,10 @@ static inline void mas_put_in_tree(struct ma_state *mas, * @old_enode: The old maple encoded node. */ 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); } @@ -2543,7 +2544,7 @@ static inline void mas_topiary_node(struct ma_state *mas, * */ 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 +2552,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; @@ -2639,10 +2640,10 @@ static inline void mas_topiary_replace(struct ma_state *mas, * 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 +2829,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 +2879,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 +2903,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 +2917,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 +2941,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 +3017,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 +3112,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 +3123,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 +3134,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. @@ -3153,8 +3156,7 @@ static inline void mas_split_final_node(struct maple_subtree_state *mast, * @skip: The number of entries to skip for new nodes insertion. */ static inline void mast_fill_bnode(struct maple_subtree_state *mast, - struct ma_state *mas, - unsigned char skip) + struct ma_state *mas, unsigned char skip, int *height) { bool cp = true; unsigned char split; @@ -3226,7 +3228,7 @@ 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, +static inline bool mas_push_data(struct ma_state *mas, int *height, struct maple_subtree_state *mast, bool left) { unsigned char slot_total = mast->bn->b_end; @@ -3283,8 +3285,8 @@ static inline bool mas_push_data(struct ma_state *mas, int height, mast->orig_l->offset += end + 1; mast_split_data(mast, mas, split); - mast_fill_bnode(mast, mas, 2); - mas_split_final_node(mast, mas, height + 1); + mast_fill_bnode(mast, mas, 2, height); + mas_split_final_node(mast, mas); return true; } @@ -3297,6 +3299,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 +3326,7 @@ 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); + mas->depth = orig_height; mast.l = &l_mas; mast.r = &r_mas; @@ -3333,7 +3336,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) while (height++ <= mas->depth) { 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 +3351,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, &height, &mast, true)) { + height++; break; + } /* Try to push right. */ - if (mas_push_data(mas, height, &mast, false)) + if (mas_push_data(mas, &height, &mast, false)) { + height++; break; + } split = mab_calc_split(mas, b_node, &mid_split); mast_split_data(&mast, mas, split); @@ -3361,7 +3368,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) * r->max. */ mast.r->max = mas->max; - mast_fill_bnode(&mast, mas, 1); + mast_fill_bnode(&mast, mas, 1, &height); prev_l_mas = *mast.l; prev_r_mas = *mast.r; } @@ -3369,7 +3376,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 +3435,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 +3679,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 +3693,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 +3812,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 +3869,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 Fri Feb 21 16:36:07 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13985959 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 6DF01C021B3 for ; Fri, 21 Feb 2025 16:36:37 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 310CE28001B; Fri, 21 Feb 2025 11:36:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 26CA3280020; Fri, 21 Feb 2025 11:36:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E099128001E; Fri, 21 Feb 2025 11:36:31 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 9550128001B for ; Fri, 21 Feb 2025 11:36:31 -0500 (EST) Received: from smtpin23.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 4C695C1884 for ; Fri, 21 Feb 2025 16:36:31 +0000 (UTC) X-FDA: 83144504982.23.96AD443 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf26.hostedemail.com (Postfix) with ESMTP id 2E3FE140018 for ; Fri, 21 Feb 2025 16:36:28 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=JoGgR1i4; spf=pass (imf26.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=1740155789; 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=mppvmtBExwjVqSXhlL1cgO1sMv2taYNKWRxQFhLDs2w=; b=CoMV+5aHuE4bbDvcwl64Sv14G2PYC+C5YUHHcdD5RSN6J7ElgsTmvaIjEKeJaaGppr3oj5 MrUEZkM4QWFZ0IwMUeb3R3EG/2lrN3SUhj7+ivw2SQ5pWxHo+FLZqEPKeQSP0oWi6Ftjt6 /dXNPkAzm+LeBj+5p5aIWOxGqvARUa0= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=JoGgR1i4; spf=pass (imf26.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=1740155789; a=rsa-sha256; cv=none; b=XlgHXbxxkI2fbjGIF1Zcuui1xdeB9eSshisAJYZo6Oj5gxcekKSs/mioZ6dXexa8TiVC6M whOUeSeuk9om3NkkWaihLXfSrJz/aGPsgjipw3wNBffr7gXxws6UTFBsKeSyM+dq6IN3uE ocWGtpIpPvD56Vo8lv362MMUgOJPTBA= 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 51L8fZVI017431; Fri, 21 Feb 2025 16:36:28 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=mppvm tBExwjVqSXhlL1cgO1sMv2taYNKWRxQFhLDs2w=; b=JoGgR1i4L28o0kKgwk964 VWPtzToikPnIW5xr3ml3z8sTsV71nXJ6gnbv4tCrtpA7lzugPsa1aldglDVAUfSU lFCdwkjvyAlI8h+92eeOvB2YaPXT8CLOGN7NH4Ao2SZtjfcEnG0ye6i7LrSpyL+2 jjKfajKrrcwqJtnVSFCRaxAp7kM1l1VVflUmudgXrCrsBfeIrkF2WxLSTKFzid72 eYtjH2m/CiI4htI6+CGW4MaSqy/qf/jTQ3pG0YBRTT+fRFKO75Njh3x8h6p+ox4M HDUlIAZK5YgkhSMi7LT747q3Rh6Qg2AbtUvED8K4f/iBz0yrVbCuVoJKAZXGF2WR w== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 44w00kpmwr-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:27 +0000 (GMT) Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51LFex62010624; Fri, 21 Feb 2025 16:36:14 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 44w07gxm7v-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:14 +0000 Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51LGUIXH005786; Fri, 21 Feb 2025 16:36:14 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 44w07gxm69-4; Fri, 21 Feb 2025 16:36:14 +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 v2 3/6] maple_tree: use vacant nodes to reduce worst case allocations Date: Fri, 21 Feb 2025 16:36:07 +0000 Message-ID: <20250221163610.578409-4-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250221163610.578409-1-sidhartha.kumar@oracle.com> References: <20250221163610.578409-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-21_05,2025-02-20_02,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502210118 X-Proofpoint-ORIG-GUID: XiQ8wTaETKHof91B1TGOXJmkKayqD82w X-Proofpoint-GUID: XiQ8wTaETKHof91B1TGOXJmkKayqD82w X-Rspam-User: X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 2E3FE140018 X-Stat-Signature: gnt5o4z38df9a1kyiq33s6myiigmwi6h X-HE-Tag: 1740155788-105092 X-HE-Meta: U2FsdGVkX19/vqaz99o1LUV9EbfpzGGroFYCw7ILEsWUSFW+uXTXc0BQJWG63z5WU3mU5DjkhQGM1Cc18gC6MnIGexb9FE3h6LI8wuAzJijKJpzJADgY7aLR5u2zWiNvnGLsjdTYfr6d1Fp9V5wfo7COtxn77bAz/hNjMZSoHYtz7nEUlEtRjUD6cux7Egxvc+fKann9cbsh4RBdASHcE4/lDfy2Va0OYiV5VM64zG+ngkVkkmp164gGS3Sr0xE7k+VuYzTSnjcIUIRv77ZvMueDHSw0gV1++ySgxMkDtUBnddqfiUkReKfda7axtI28LP5+aZujmGgqm88mFiLBQrttoQah1s5B7jo7rszIfMYIEhS3NrnT1G8+hfLD3QHmMy5XwkFoibHtPBVYHf6K4jx2Wb4nQpDxP/22htd08VbVRsjYuSavV7Zprlh4J0JCV6htR/0j77JReLpXcPPWEB+TMvyNFC0AtoQx82PaWeNDBQDAjgF6BWATUF63Of9S9KBz/Zki7JPVvTREYSXVe8ek8CYCmmZ/xRM6ZaPGZKR+kcWZTjxLW/Oi47J1Th3akYrGt+d5d3A51sZ5BY8FMU7reewDiItOYPEgBSdLrw1rLzL/I8fwfuFFuC/qyk43zKER1OP/o94iN8k+NlWHKjrM7IOgO6+JPoVhwrY6XHjv54VDHTmHreHXYkVnX4SPaP7T9iO4R8wj0QuY785gAahcO7Ja/Vwbqvxd3gGLHtqEoMRI0zz9H9brY+He7uu46kLFPQZmalQwj3WsPZi8hIQ/D0O5yPuoy3W9+OQ9NDuoDh5QT/k0Jm6oWO1WSjoNcedALzMnEpcR4VFvZAyr0H2gwzJcGugCMz9VNJ3REb3YmOGb5sbo9Wq87J0Wiuv7+Te0RBA8RvAd+lBm85jJ/8ApkEfiNk/e8jceDZa0kAet5roeNLDFdbJBggovijvzwIc+/RSElDzidpoz7O2 /qA1O9U0 hCc34GyGvYIQ9PLqgT5XFAa9rWgMYCqGAOueuZf8EYk98AS5wdee/+xbM2ABuFdlwDDDs8sDEBWKAmNyaRa8n+SRqZXvWTGD8cRTtEMNAY+ev3L0NbGJvZDV8HA3Shed6CpWwLJ/3xlOB+sRb7Z4r5d406eq/5NDy+xpv/g2rR6xZ9oYwZA2X4a56//RaA3Tfp+Y7E5i0kclR4l4oRHem1f62jem55kL7pQVaewQnDkPhrtphKQ1t8ywtfbVpgsNgqS6H4xuEM++oo4tyyL6MAOgUGV1G9AQ4Utpt/DC7MWeq8t7s2nG0FKXPkOqrXtf1lo6FKPVyx/VMLEPfxm1XbOxj+Y/SRzSrbGcXEYUIulEeXmU= 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 | 102 ++++++++++++++++++++++++++++--- 3 files changed, 105 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; /* Height 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 d7dac3119748..ef71af0529f4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3542,6 +3542,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); } @@ -4157,7 +4160,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: @@ -4175,13 +4180,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; + 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..d22c1008dffe 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35475,12 +35475,85 @@ static void check_dfs_preorder(struct maple_tree *mt) } /* End of depth first search tests */ +/* same implementation as mas_is_span_wr() in lib/maple_tree.c */ +static bool is_span_wr(struct ma_state *mas, unsigned long r_max, + enum maple_type type, void *entry) +{ + unsigned long max = r_max; + unsigned long last = mas->last; + + /* Contained in this pivot, fast path */ + if (last < max) + return false; + + if (ma_is_leaf(type)) { + max = mas->max; + if (last < max) + return false; + } + + if (last == max) { + /* + * The last entry of leaf node cannot be NULL unless it is the + * rightmost node (writing ULONG_MAX), otherwise it spans slots. + */ + if (entry || last == ULONG_MAX) + return false; + } + + return true; +} + +/* get height of the lowest non-leaf node with free space */ +static unsigned char get_vacant_height(struct ma_state *mas, void *entry) +{ + char vacant_height = 0; + enum maple_type type; + unsigned long *pivots; + unsigned long min = 0; + unsigned long max = ULONG_MAX; + + /* start traversal */ + mas_reset(mas); + mas_start(mas); + if (!xa_is_node(mas_root(mas))) + return 0; + + type = mte_node_type(mas->node); + while (!ma_is_leaf(type)) { + mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max); + mas->end = mas_data_end(mas); + pivots = ma_pivots(mte_to_node(mas->node), type); + + if (pivots) { + if (mas->offset) + min = pivots[mas->offset - 1]; + if (mas->offset < mas->end) + max = pivots[mas->offset]; + } + + /* detect spanning write */ + if (is_span_wr(mas, max, type, entry)) + 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); @@ -35494,8 +35567,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(&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 +35577,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(&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 +35589,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(&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 +35603,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(&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 +35617,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(&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 +35631,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(&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 +35657,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(&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 +35675,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(&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 Fri Feb 21 16:36:08 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13985955 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 32A04C021B7 for ; Fri, 21 Feb 2025 16:36:22 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 443F328001A; Fri, 21 Feb 2025 11:36:21 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 3D6EE280016; Fri, 21 Feb 2025 11:36:21 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1D1D528001A; Fri, 21 Feb 2025 11:36:21 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id F0CAA280016 for ; Fri, 21 Feb 2025 11:36:20 -0500 (EST) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 6052614105B for ; Fri, 21 Feb 2025 16:36:20 +0000 (UTC) X-FDA: 83144504520.03.38D1157 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf19.hostedemail.com (Postfix) with ESMTP id 48B101A0019 for ; Fri, 21 Feb 2025 16:36:18 +0000 (UTC) Authentication-Results: imf19.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=a8KFEYqE; spf=pass (imf19.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=1740155778; 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=lxM6DO0F+QyIrP48GZ8DBI2u4dV0evq288ua9Mia9+E=; b=mlhBf2uBlOwYZu/NqB5af2URNYgOg+zoBdqFp/ju7LUwAMHlK2gt1iOrYZHpE32DzatEZ2 VJw/Nlyrsfp0HwHOReKKPdtQFEqL8KskPlx4jUkm5d5omRJP57FoJRUS5lqBQ15sGrRThV B/rmvZ4GYoJdR1F3L1Eysvu5Oms7x0s= ARC-Authentication-Results: i=1; imf19.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=a8KFEYqE; spf=pass (imf19.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=1740155778; a=rsa-sha256; cv=none; b=ferJbT9yXuo9A3Xi7cXaE4e0UmqjLe0EGQxpzj/0JmvabF0pBosFLwVAr+dWm5y+34ZJg7 edbM9aO8zPWlrrUEtS8QqQyFn8IuHhlHSnNc4Ms8vOV55ocQ3P6xNNaeez77X0SX7Ji/ng oOO+6csPDKAYGjgtKgI/rvtj30k8Pl8= 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 51L8fdxP018610; Fri, 21 Feb 2025 16:36:16 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=lxM6D O0F+QyIrP48GZ8DBI2u4dV0evq288ua9Mia9+E=; b=a8KFEYqEeW8eplIs2Msn5 pkzpGFdBiXIwFTCQDVhx4QZEKsV2JSLYT4lOhay5/My24NI6pySR1A4Ektsapg3b gZ1fgraCtqM6n+FfM/PTuA+7mewmFkMd77rVoHdovagks/yEjHOIK3/royPziLt+ 1PQ3BYgVp6oZFIe5Qmj/vlIAZ4toi/wTiG7beITS9XNlXA/6toFTJnyN/fGlDybX ZXSP3cQoq+Y4UDozAQOz7YXeTEf43vPGiP1DcmdFIkLEaccDL6BTwnyFWpA8JOz0 MgPg6gsD6+YPaENrlGWtYj66bFHZVsmJwO3A1eEGL0FbpQbXO4fgJ6IDIIPGdlLR g== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 44w00npq59-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:16 +0000 (GMT) Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51LFZ5xe010490; Fri, 21 Feb 2025 16:36:15 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 44w07gxm87-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:14 +0000 Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51LGUIXJ005786; Fri, 21 Feb 2025 16:36:14 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 44w07gxm69-5; Fri, 21 Feb 2025 16:36:14 +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 v2 4/6] maple_tree: break on convergence in mas_spanning_rebalance() Date: Fri, 21 Feb 2025 16:36:08 +0000 Message-ID: <20250221163610.578409-5-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250221163610.578409-1-sidhartha.kumar@oracle.com> References: <20250221163610.578409-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-21_05,2025-02-20_02,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502210118 X-Proofpoint-GUID: fIvW1rKDgQFpsnCwJqLXXVV9ltBKwsOr X-Proofpoint-ORIG-GUID: fIvW1rKDgQFpsnCwJqLXXVV9ltBKwsOr X-Rspam-User: X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 48B101A0019 X-Stat-Signature: pepq74tyt6xin7agoq4ogweit9c7go7t X-HE-Tag: 1740155778-431186 X-HE-Meta: U2FsdGVkX1+RrS0ukbLiEJ8+h7EAMi9NW4mXn0wPigwnXfkw0KXhQqKQWCnofb3fHTgqxcNscnNgze+hVSY3nCVhEZq9nL3U1V9/TlysBCPQdhBFutR+VK/jA5qEJVAfR+OidXVLbXxtq/OU72gftqkqWCtEbx0bHWjvF+uQf9y3HzA20qCariD5FaxJ+NtE0Ig6+kBDKcuo95z4kLMzT2/5GXziNsEpLhT02GMZQlie4HCi407QbjO7ishQbyzTx4/JfS1E0FUbFkh64Lvnr2CAeOM4wqipdYtk95zGfbTlFAzKRNsOG36cU/V6gimXP4xqmZrTrRNf3vUil9yr/ceP1uLz4yBMHBQdPk7sbUxA5y5NzjC3Fou3R1i3y5iA1KvT0VABr+ZxZ9CW0S9dlbfRj9qhyoyISHz1dM1auxwXKLthFAC609LDLNfYnhw7O4IRII2ps/G9pyF/QYD+p1nThbig5M+YPHvaqwkRBDs2T37583i0m+En7hvos27LZkmLAeTGJ+tvZwiwBYt7SiIYAOAPvnwahGZCvqEUupF/kC51IAm8006t+3bgtly2UKTmuVNg/m053N/o1NjuWHmYxLhLiCzYIfJgjLbEbfRTM769oR9BxqFV3wbwa8zg4HqBQLsMShr8mEyeBnhpXczJKN+AAz6ROlVGR2Dkia1NGghkFBi62/b3ETyNUyLJvDdp3fXnQYxb1FP9c6pmJ5BtH3ceZchUSFGW8SQka8zhdjrxwwde9Ejm2qiCNA/UYUNRTjfN5Sj9hN/SvzAmxFqcVoeJxTf5/gpNWBFNWGQg5LnVQYJ2C8FBbhY4bnY5HHcqqbZef4S8zh7QLm0bTzxijgvI1A5lmK5nV+sOusm9fcgIkTw72eP2axTNeXK9FaGFhZ2ib/qpYjA1u/sLSJKxKzr03iTrxLqiZPHlj6KiUhnPScc6ll41dDvBKRHFq9OVtUGbRlvM7+GGEQR TLRqn++X c8mdbGjAkVRJZobWA9kLoqEgnE3wu+HmgjCmaNJKxmldAuTmqbPsFNGjMdyKC3LUDwq6MZUYEEsfNVwun45glOH4aCSg75ZI1U9A7WaKGEf/Ffz0Zq903rF+KqBJSqedpgCSYonnZURurHuz4z0hn7nnTzDo0OEcloTaOLfipJ5IRwO2DLelFDD0UYcYDf6spMHbHPAt5wwu0g2hWTDMcEDB7kADjBl+iNdTMjhR1VoDnNF6PvPKkbAeoe74oblX+6/0Zbxl+yFXhEDexBLn8Rlmae8mS4UN+cyt79NtLvnmwCgWuoVr7bys39cWcvInG7/0Gu92Mx2Xnfp9z1u36TRBpsEBqy7kgB+uRX5C5LpRmDLtspr5aNBJ3yz+LdvcwNxwZ 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 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 ef71af0529f4..4de257003251 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2896,11 +2896,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 Fri Feb 21 16:36:09 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13985958 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 4FF33C021B6 for ; Fri, 21 Feb 2025 16:36:34 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 09AE128001D; Fri, 21 Feb 2025 11:36:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id F159928001B; Fri, 21 Feb 2025 11:36:31 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id D6AAF28001D; Fri, 21 Feb 2025 11:36:31 -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 AC7DF28001E for ; Fri, 21 Feb 2025 11:36:31 -0500 (EST) Received: from smtpin25.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id 3582916190D for ; Fri, 21 Feb 2025 16:36:31 +0000 (UTC) X-FDA: 83144504982.25.B6F7271 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf24.hostedemail.com (Postfix) with ESMTP id 20491180021 for ; Fri, 21 Feb 2025 16:36:28 +0000 (UTC) Authentication-Results: imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=eAbp4WFU; 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; 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=1740155789; 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=m5qZMtJyHxKtlfah8mpfmJ81/MTbcNVeb2GVVQ6Wzio=; b=hbHQ62aME+WM3MYE4tcYTNWCjhClqlK2NU2Aak70Z2lAEFfxNZWHraJ+AVkgoQVD+REgxa uIGnlQxNG0S8emqRvciDqpHRJkd39QgajMEqXP7cSknSQlRq0i72YM2p8TgEseXyLXrdfw iTRXqt7CCuxDAi0GClltuHt04AuXm0I= ARC-Authentication-Results: i=1; imf24.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=eAbp4WFU; 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; dmarc=pass (policy=reject) header.from=oracle.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1740155789; a=rsa-sha256; cv=none; b=s5LY7k/kLrFYWGZAodHgelB9JyjxnXIyZNYjgTuV1085fx/twykXGItG0tRoEYQ9ByzPfR gxe8hfdtocSoM9EJfiMYg+QVrIqQt7an/VxJOTcrrb9YOmUNpZfgPNgVUYSmlQXpmyw3EP X1JgKN4TYmB4v1AaJtaH24kvhHvGEKw= 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 51L8fcXp002374; Fri, 21 Feb 2025 16:36:27 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=m5qZM tJyHxKtlfah8mpfmJ81/MTbcNVeb2GVVQ6Wzio=; b=eAbp4WFUVNS4ckfmwdP25 L+81aVdS5CGUwwQqIh58kVtfnD9cs0ALZogF+oW/zWrVKkkYBqTny2HvwErWZJGl /FIhRY0dnqiNRCAO1I3zag+H1EHw8BZd9c+Ab/zI/VwGvTodNN1NEJbYUPaJ5hUe vhiiHtQlVzpxGVtZ/CDPtVVshErMj/Tq0RENcTUViiC3OhMt6KrJvatyFAtRiYYZ LvuOkpY7NH3OgTFE9UnvFeh1Ab4/tFPuBGSl6eZS4siORXUwQldxpIZVHku3QzKm FoVo+fEzdDIDqgrawYrtGPDNbJ8+i6wAu1cMyGF2/iemcYql0FYSPL0k6cTivhox A== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 44w00m6r2h-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:27 +0000 (GMT) Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51LFaxtO010538; Fri, 21 Feb 2025 16:36:15 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 44w07gxm8n-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:15 +0000 Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51LGUIXL005786; Fri, 21 Feb 2025 16:36:14 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 44w07gxm69-6; Fri, 21 Feb 2025 16:36:14 +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 v2 5/6] maple_tree: add sufficient height Date: Fri, 21 Feb 2025 16:36:09 +0000 Message-ID: <20250221163610.578409-6-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250221163610.578409-1-sidhartha.kumar@oracle.com> References: <20250221163610.578409-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-21_05,2025-02-20_02,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502210118 X-Proofpoint-ORIG-GUID: XYYj4G4kU-p-4171gN7Xba356-yhrB6z X-Proofpoint-GUID: XYYj4G4kU-p-4171gN7Xba356-yhrB6z X-Rspam-User: X-Rspamd-Queue-Id: 20491180021 X-Stat-Signature: trwnbae6xbzzs49da9fp6siyuze4gii1 X-Rspamd-Server: rspam03 X-HE-Tag: 1740155788-382238 X-HE-Meta: U2FsdGVkX18Oq2HpKGm8517RiU9bhGuJUDd1C3Tt3+p7Myin6QiyqHiZBMObXdyWTCV+6H9pharYCTajrXWT1o4x8ip014Exz/dbMDBRgAvhg3wHE03xzv+Pf6Nqb8zQN4tEk55NhIVzETEHVtxZfc+Q0InCYn2v80GxjNKu/p3ZrlAoAXdRL79agkfjAvjcuWLKaNQYBBKu7AE0JxJQRW2WDFbgiAdNBJJ3beQ6dvGO5KU3p9kTgPSRvlFUB6vocqIZKcapp7OpRTF+PTYAvelK3vIcYK1HADPJW1GbHypDaWDA1TNp0TbyWhtp/fag4ONN4INyLlpSj8i0IM4fQa86MjQr1rRQ2RX35h7GwoQKNd1hyh9WpaF771naPHd1HYjVGMI+5hbv5RyyAfpEb8zPeO+Js7U48iCZCWOi2BwTgTvvJgze5jK89NtxXJH1JXszO3TrRNh7oT8UsGArQzi2tiiRo9BZJHWok0JipkW4rIxR2qSjUOLcdKuNOzwuE186QKG4TG9pvUQ9GUIXiimSbwaLRzmgNgLcCcw5SGFpIcJ8+O6K+63Twbo8baSGTyFPGomFU+OBnnfsivEDFCgyl833zjb6HAo9tK7pTRmkkV7dW1v1sO5ukcJBs+jcH4t3wXY0x7gmZ6hFzBXH1//x7YhD++yYLderZj9LwoVmv8yn/jUQnOWmH6UPfW6E3gD9MV9Mi19sxlKBq4slPXXuq1+jJy3dx8bESp8iyDhu07kDOOZEE9hTWRySMtkBVKZprX1Y41tETE2wmFP0PCTYo0DDTz2NchfabFQT/dWuJUm+qSOhxpu9iGquM9+NDh6H50cU1PcMyqDAq/xj9z7DgPYaR8FrEdkTxfUWC/1nlK8CYxeAeRKIB//bwNh3MiC3kzGjFUiWqkNq7gRzYXHAYbItqgHnQInSs/ldDi3TER1JuvOn/P/um9WnaRI/70VXjAyIU7+v6dm1BQM HrhPPgQX XvK9hDP1mvOQ0h/gvzYWw7snmEFkFQNF7jvVmjLRpIqsFKnU8XaJ+/m075mGc1R/dJz+l9zU4mvsPkVNDUCINB2LSDPI8v2bQcsHFZ31vczLxk/t2LWSfYKFZAR+JGuZiaQ2BPD+oVI8yKphvoyjZcHM7p6knF+TFGLWRgeB2Dm2cHJSCEsgVkARjmLD1cqOyaqFnJu9iYk/XAGxSUuekW3gh2/gz5Pjre0sai5dKAJ1+uKOfLH2/IkkI+3ObppfSbtR+fMdeOPvZx5Im48vGHCHx6bRGVIA2ca5Y1GtfCnBX4atN34WfEZy9+5hp4CqWsjxmfH+RARm91dCyVxtl9AzS07F4ZjqjlpCJMyNNAXUsIIE= 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: If a parent node is vacant but holds mt_min_slots + 1 entries, rebalancing with a leaf node could cause this parent node to become insufficient. This will lead to another level of rebalancing in the tree and requires more node allocations. Therefore, we also have to track the level at which there is a node with > mt_min_slots entries. We can use this as the worst case for the spanning and rebalacning stores. 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 4de257003251..8fdd3f477198 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3558,6 +3558,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); } @@ -4193,13 +4200,19 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) ret = 0; break; case wr_spanning_store: - 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 d22c1008dffe..d40f70671cb8 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36334,6 +36334,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) { @@ -36500,6 +36524,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 Fri Feb 21 16:36:10 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13985956 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 936E0C021B5 for ; Fri, 21 Feb 2025 16:36:24 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 999DA280016; Fri, 21 Feb 2025 11:36:21 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 9218C28001B; Fri, 21 Feb 2025 11:36:21 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 79CE1280016; Fri, 21 Feb 2025 11:36:21 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 52A0A28001B for ; Fri, 21 Feb 2025 11:36:21 -0500 (EST) Received: from smtpin04.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 13FBDC1863 for ; Fri, 21 Feb 2025 16:36:21 +0000 (UTC) X-FDA: 83144504562.04.24E55B2 Received: from mx0a-00069f02.pphosted.com (mx0a-00069f02.pphosted.com [205.220.165.32]) by imf13.hostedemail.com (Postfix) with ESMTP id E2ABF20019 for ; Fri, 21 Feb 2025 16:36:18 +0000 (UTC) Authentication-Results: imf13.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b="UDUou/wa"; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf13.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=1740155779; a=rsa-sha256; cv=none; b=VVKHlS5Jf4YhF/5ajrOBOmUriDzlAVWzeRa7Uk5W2Cp4t/Qi/BvjOhT+FU0jewGMrKlA7y bm/3phkj5vsf+Of1PfpO5JJjLWYUAhjcVK3yP0AcQ+vnuxm1FIwaYO7rwDfSxNvQam3o3R J60CPwTiT1356JoLva/EmF8tPQ0+tPQ= ARC-Authentication-Results: i=1; imf13.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b="UDUou/wa"; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf13.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=1740155779; 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=Qas138Lb390XmRj9bcmiwXwau4wNel66xSmLqMbrZnQ=; b=bvSAIVH4S4uuG4WB+FkXJy+agGnS8CuHDfwcv1vsbFsXbiWT0n+iVCAtAYhLGNqQrV0rf6 ja4XtJoSgad01v1y8dGAIcnzFuNbtQGxUa5fWXS02HU/qWsB6CdD+wVxqxGlm4xJXEExE0 gGst9sCjXBPgkhN1MvcicSur5R3x+Bg= Received: from pps.filterd (m0333521.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 51L8ffb9016642; Fri, 21 Feb 2025 16:36:17 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=Qas13 8Lb390XmRj9bcmiwXwau4wNel66xSmLqMbrZnQ=; b=UDUou/wao6D0tTHRZf2ud oy9fa4P3FIJEoE8a/7gu30ltSLHv4RDE1afSZm2FDB2ZwfsL0VJmFQMP+0OpsTK5 YRucFDuch8EebCYq/fB1c0tY0WrHc3+9EMzHVOEIbX55o/D8CJ8t5xoEn8ZWbn4R m/X4BK60rMrcFMmhFRSjhXXm3ASqyU0oqq3oJkwDn4tKaX+4Oj6whCY7llfH36qP Ai4kTntWW15NdB0oPKQUS7b0P3pSNMaPeJ6iLsT9SfBdsB8O5K9WFNTMWkvhgIrn NonI0NQP3JTlxru2TTada43mrFQheWKFs4kC4KmSoJccOKj0Fakuymcm6vJUB+Z4 Q== Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.appoci.oracle.com [130.35.103.27]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 44w00npkv9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:16 +0000 (GMT) Received: from pps.filterd (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 51LFnZkJ010522; Fri, 21 Feb 2025 16:36:15 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 44w07gxm99-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 21 Feb 2025 16:36:15 +0000 Received: from iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 51LGUIXN005786; Fri, 21 Feb 2025 16:36:15 GMT Received: from sidhakum-ubuntu.osdevelopmeniad.oraclevcn.com (sidhakum-ubuntu.allregionaliads.osdevelopmeniad.oraclevcn.com [100.100.250.108]) by iadpaimrmta03.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTP id 44w07gxm69-7; Fri, 21 Feb 2025 16:36:15 +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 v2 6/6] maple_tree: reorder mas->store_type case statements Date: Fri, 21 Feb 2025 16:36:10 +0000 Message-ID: <20250221163610.578409-7-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250221163610.578409-1-sidhartha.kumar@oracle.com> References: <20250221163610.578409-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-21_05,2025-02-20_02,2024-11-22_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 adultscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0 suspectscore=0 spamscore=0 phishscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2502100000 definitions=main-2502210118 X-Proofpoint-ORIG-GUID: XIKLV5z05go6Yij8Q-abTzXMl6Qq-NEQ X-Proofpoint-GUID: XIKLV5z05go6Yij8Q-abTzXMl6Qq-NEQ X-Rspam-User: X-Rspamd-Queue-Id: E2ABF20019 X-Rspamd-Server: rspam12 X-Stat-Signature: xkex6eyeew1wahccnzih3o3gnr3pgnxk X-HE-Tag: 1740155778-204389 X-HE-Meta: U2FsdGVkX18WzzlkKyKu7uB6n7KROs0tLoh2SUfjXfhtFDUaDdsixISsYPYFhaU4aNI+69i7dCT3Iju3QjcPHziOJRy7Dv0yn7zX5XV3ftN1lnxj2OppAGpEIFEhwLOpejUFECNUq4dJW8nPl+So+SW3ndDq0SvOaTrpWmWPKyAr8GJH+CE9XdUkanaS0Md6eo7OZlXhJJTB/9cZKSmjnB5+liUiVlmxxJ0zAjvsNWgLS3EW6Rs+ByaxKjOM8zMvQnLI07puE0N8pFqjOSQn/TDka8gTiWgPZoMN7LgDcSTc/MI6ZYbB+LDsz2FPlXdAkL0if1JwqMVx651TEbHn0Sxmt0JYFknE3uJHD5OSkMoWAKG7a1nt7TzTKZDcm913NqAJnfnffzvGHjsSs/gUNkCQiv1KoIuZEiUE9RpHZFmmW46d/MfCO2UEPPuDbvHza5DUPxUwiopw5mMCbPCnXxZhCrwYtU7WWHfjIPYoCeM3mDMZzwz1DPPlWo3pF8t1uFhaKV/WH9GoaoU0eMHlXPg0dhoipLQ5ZTT0Qw2jGR6cI5mc0BiEoWXc/Jx44SQWp/auvnYOzqzMpSiGkHnqp8Wu2l3M69ctMQINXkSYwQNqNWavEiomdipcKcT7I6/eVTzBvmSNXchBv/Ec3fk6WfALelCjN1XwngG2bNEqKNkQoZkYXjUyPBG29x3DXtHYvxw6tuJ51ID2QY4DBye6YoRjEmU9rbo+MWeDe2D9yRUp+6HjhEfMDPa6uXqsTwX0oNHG0FH0HH9OhUVmLU2vJPzPns5tjc0KdeHN7CCsAAep0LosjLIDckh6QlH1ouygAXN/AuInfsbTP+dR5GYj1dpasQLBREyCMSrtJ+Qy1X+kN4+2CUfG7ZgK6fA2pNRADmMDt2LPKPqk4ZgKhmyo9WAjnpK7xUSEJUKp8bS9r4YqEnbsXkRhwI50/nGFWoftVdmgzdowhVExHL5a/e+ Nq9jZjND ezzAW8Ds6pZHlLVa5zrAUtTwO5Eknu+VIKdQ+4iBjIu9kRkrngWShBcZYKuQzmX/b34Lc9csz2kzzaJex37vQv0nEt48hN8plJvbrYFiIfQMcURJt3rgK+K3KwJZPewFaMSEEs0yyia0qxgcsYUZMvUnWnxCM1eal6VINWYTzoZ9//OoU1B0ysGr4/6dE7ZnL0NxXmgRRA4BK2pVuQDu4U9T+p2a1VDgQkSPE7qyPKqSHM+G+jkbP7y+BjQB8Ti4G5bzufsVZiQfInV1ByUCP6xQusdxG0udQKS8PhCK97qISrntSjoLzytMLQnOvgLbN51ks5CkxnVrG6aaMD7q+AMv/gvp4f/CYnUeQWyffikeRSx4= X-Bogosity: Ham, tests=bogofilter, spamicity=0.000001, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 Howlett Signed-off-by: Sidhartha --- 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 8fdd3f477198..36d7d7a27e32 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4091,15 +4091,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) @@ -4121,6 +4112,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; @@ -4185,19 +4184,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) @@ -4217,10 +4207,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;