From patchwork Thu Apr 10 19:14:44 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 14047140 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 CCC46C369A2 for ; Thu, 10 Apr 2025 19:15:02 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 72B4C28008F; Thu, 10 Apr 2025 15:15:01 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6DCCD6B037A; Thu, 10 Apr 2025 15:15:01 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 57AE028008F; Thu, 10 Apr 2025 15:15:01 -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 391EA6B0379 for ; Thu, 10 Apr 2025 15:15:01 -0400 (EDT) Received: from smtpin28.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay05.hostedemail.com (Postfix) with ESMTP id C1AB85B69C for ; Thu, 10 Apr 2025 19:15:01 +0000 (UTC) X-FDA: 83319086802.28.41919EE Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf28.hostedemail.com (Postfix) with ESMTP id B701DC000D for ; Thu, 10 Apr 2025 19:14:59 +0000 (UTC) Authentication-Results: imf28.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Ta1Y01ti; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf28.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=1744312499; a=rsa-sha256; cv=none; b=FF+DYeYKD4XO4lYhNaGTTnkTaMLskTL/noJQLYPpw+Z1skltV5MgKVhqTlph7B33+B7K5C Z8dpwfSIiBV76nPzb8GxMmtv1CTbEsDAbVtUu060hTnYsDm2IOXdSMWSE/3TLMOThDHtRJ lVjFaFNmtLPG9A62E2w+Shei02M4e+0= ARC-Authentication-Results: i=1; imf28.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Ta1Y01ti; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf28.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=1744312499; 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=bWJjw0o7BbqQgCw33nopo5k8/4LIRBtq0w5bjnsN5bc=; b=EEoDky7wib7siTb74or1clGjxLVccjp+qRIObWWylxPFvLKthRl1M4A9Jd7jEjAsj2jvjP I+qJbpUU8tWu8+kjDGcywsdbZmUEbmMMCKVECMKV36EPatFdh96cxkegT9xzH4rX4zdTQ4 2oHTt3S3ZLGfnmROH0yhJJR9f14J6i8= 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 53AHv49n030910; Thu, 10 Apr 2025 19:14:56 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=bWJjw 0o7BbqQgCw33nopo5k8/4LIRBtq0w5bjnsN5bc=; b=Ta1Y01tiixjTIg11fVb1U Vs6Un+54F1lMe1zMik+3M2GiqcBT5usJgyhS/ino/YBMgivrnwh2xxziXpVNuDl6 23ffqTidprnCeGmw/mtyd73pnJaIwR1gA4Gp0Y31UoC0jflAc+9dyWyIe7CuV7Ok 0PiSGDZ/763WI7X5amOuIM6xTI31Yz+qOpTUGgJuBgDnv/lsng/v353NR531/bEg 81FpyKAiWxjs7JTDaJ9q+7nqu597I0j4JkgMJI2p+i7kBrHG/JEk7zI2W9f4Bkp1 igVSrXogsZToJtfnz/PZQwf0hZCsDzvDpeohhi+066efCO7tIBhBpTW++akE1Gu+ 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 45xju3g6ar-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:56 +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 53AInuKw023836; Thu, 10 Apr 2025 19:14:55 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyk1gjx-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:55 +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 53AJEn94040606; Thu, 10 Apr 2025 19:14:55 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 45ttyk1gg6-5; Thu, 10 Apr 2025 19:14:55 +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 v5 4/6] maple_tree: break on convergence in mas_spanning_rebalance() Date: Thu, 10 Apr 2025 19:14:44 +0000 Message-ID: <20250410191446.2474640-5-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20250410191446.2474640-1-sidhartha.kumar@oracle.com> References: <20250410191446.2474640-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-10_05,2025-04-10_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-2504100139 X-Proofpoint-GUID: IP9YCkA5Kq5Y17sI9bPL-LaoxMXu4I7k X-Proofpoint-ORIG-GUID: IP9YCkA5Kq5Y17sI9bPL-LaoxMXu4I7k X-Rspam-User: X-Rspamd-Server: rspam03 X-Rspamd-Queue-Id: B701DC000D X-Stat-Signature: zh1r9sxq1odgi1usn8rsbe1rbafmsu4q X-HE-Tag: 1744312499-538457 X-HE-Meta: U2FsdGVkX18ZoiJVQBndBI9qoiNABMYIswd4Ot7wq+km+DZHn3i87Jch+b3HyEAbh/xtlA4leqqJbRAQinTHuG5ppK6VTgihFXYmGdhRshMMPDauL2hBEZ/gYgox2u+xgPmVQh7MAsNYSvc3SPWSHyFcE34EaP5OiJzsB4DCA9HHmq1v+aqBzGWeZ1u2EsgWgWUoaIvrn4g6gS8GXF5anOCN7/CscMiC0/9xFazeG9XBlf3suI7gJy6wom7LNDrpNKF4cvOm4qEUPMCRvKkYOAsp6rnhLUB8TWzQCZ7SDSvMygMRyVy+90gYSbWbraQ5SUV3As5uldlhRLFIO4kstNSRSEftmfuJwPB9cVZKzevE9ffuNfkzZZbkm1o74WlN2LUSVPZwUcNoZUmtxUwPdGP9QAVF8AIT8R4wVSrJx+UGK7TV4UZJppAsXXoZY3g2mOsyEZrafN+5hH8CHAv0ujv6dWBUzFsAfnadmvWpud6VnfTrkWY3M1TqV44ZEkuo/ghbygHhff4VJNk1cOYWaXwGZaqAmChKszaoQCy7c9xuf+JwXr9Z5rCmp0iPLRz+vZ1tBTtVf5iHweg7r1R9t7V+4S8M0vCmO+7FXRjMlyagmeNh9KLffBUXG3PYx6pEzUnq23ndRO3k2mFzPLb8NzoLWvFtz22C9AS8TZKLG8dLsq+otFJc7/6SU1rbFdU8davlq1DLOpGi40Gf53wulkCCA6tvMdINUL76LEYd/MPn0xizn7ecnM/V9BQQDVNFdFH3mVWv07XO8eOUdPZtrt/r53wqRgJ51lRD1WjQuvnzyyIM30VQAXJGWbKi3Iuq+EiYofuuqDjgYn2enLuMR8GTz4O520jXc31bmngV31/xpqfot8HmNodLm1H+4/D8GZ+uaFby8N6igVwYO/lggKW1uFO/Augc46XxAx5E09aBgbG/6Dh49tAW9J7+j0u9dP9J/jblICIxJ8omk5H fIuhzR64 CzVCNj1eIvNlzTZ/lhLGP/4WPTkXbd9MOcJ6Pn9WAqMxUpVr5WHSv/fkJL306BOYrumHcDIXhBJPLFYsTO9Wq9E/yMfjGYgvsLbEYsZpJDQ5o9F37Jk5rA3n++LMx4vVkWkRf1o4ybggJTHniHqXiZeUYtfUcG0VMJR4n1QUGbDCRUnDeu8U8UfhmAoFn7Db/VMr8lEuJMhI6NUartf12zFU+2hqfyk0RVmxq4F9jH4NlI8h5DtKhMdjRJJPburjwKiKMj/V7bNackTvJCFKZ/Hfrm5M8j3wAJo2U5pi8SVofoMDCyM11YCUnc59gMdJdf3bboOwNX1CflQtMF5B9YeiyEiHcgsWTEnME/mQFsKFlVc9WdlICgQ6X4x8Nwyl7fOQ7 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 3f794ef072f4..5610b3742a79 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2893,11 +2893,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))