From patchwork Thu Nov 14 17:05:20 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13875508 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 44CC5D68B3F for ; Thu, 14 Nov 2024 17:06:36 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id B59A96B0083; Thu, 14 Nov 2024 12:06:35 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id AE1D26B009D; Thu, 14 Nov 2024 12:06:35 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 95CD46B00AE; Thu, 14 Nov 2024 12:06:35 -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 71EB96B0083 for ; Thu, 14 Nov 2024 12:06:35 -0500 (EST) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 58322C125D for ; Thu, 14 Nov 2024 17:06:34 +0000 (UTC) X-FDA: 82785327030.09.BED1B44 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf04.hostedemail.com (Postfix) with ESMTP id 2DCF94033D for ; Thu, 14 Nov 2024 17:04:33 +0000 (UTC) Authentication-Results: imf04.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=cLGVRprn; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf04.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=1731603843; 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=iPoSja3pKgizYaVyOF/YvV4XNpYb6HkD1dOoOPDQ6d4=; b=6g1un/kzxMPO+r7l0zFfS4elXFlrLUVOdEOr/leakHsyVfjV4yVkAGLLSkI8VVT7YMvahn ju9iAbyCV0krYgykrRn6inBZCfltEv83inAcMXUQmj4HH3g9N4hq4LsouNk7SHVjZRFGkD R42VvodCBmDRTb6SS2DEpEGpfZC5tjw= ARC-Authentication-Results: i=1; imf04.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=cLGVRprn; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf04.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=1731603843; a=rsa-sha256; cv=none; b=7xiiN8OxxBnW2pmoi9PeqUBzXsQ8V5VGX/3cw8HTCeCye9t20wGOxobeBkZ0+1j/juJ1NY nqk3xAVSGYNjDPTAouMZdiQhOg/DgtIVDN32IfxJz1FP0sN7IxPaGCOXpO1mUN4MynIaX5 LkUfdY805QrMTvYoLbs6SYMmb0UUUHI= 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 4AEChijk015748; Thu, 14 Nov 2024 17:05:29 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=iPoSj a3pKgizYaVyOF/YvV4XNpYb6HkD1dOoOPDQ6d4=; b=cLGVRprnu/d6Wv7+rrIQs MGhWgFO8PnbqxVbdyQ7DxF2ScfBfznRxwZWRG8IIN1B+cvn3QAeRlJVxJeFC0Mm4 gR7/EQP1RrgwRWm4jdOHUPxAkGAy9CbPAEg0CdczprY+chvnG0UQ54M2qVHQDBFx DzNTM5UqjRHf2VBHcrjS17rGgGfDecDJ8kWW5AgR7WuSnByKV7LBQYPX2Wg6M419 n9OtMufXJ4wcRhH+mYeg+z8iO6LNYrPOAgDu40QO95/EE+wrIiAA/6EsZVAW+LHT e3qSCjxk30JZLVUKtKl4RzpNpV+n+VxFpzpLtWb/3vb/wROp22++Q4PZ4kYhZo2h Q== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42t0k29phn-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:29 +0000 (GMT) Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEFZCp1022682; Thu, 14 Nov 2024 17:05:28 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 42vuw1jy7e-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:28 +0000 Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 4AEH5QmJ032739; Thu, 14 Nov 2024 17:05:27 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-39-201-66.vpn.oracle.com [10.39.201.66]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 42vuw1jy5w-2; Thu, 14 Nov 2024 17:05:27 +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, Sidhartha Kumar Subject: [PATCH 1/5] maple_tree: convert mas_prealloc_calc() to take in a maple write state Date: Thu, 14 Nov 2024 12:05:20 -0500 Message-ID: <20241114170524.64391-2-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 In-Reply-To: <20241114170524.64391-1-sidhartha.kumar@oracle.com> References: <20241114170524.64391-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.62.30 definitions=2024-11-14_05,2024-11-13_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 malwarescore=0 mlxlogscore=999 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2411140134 X-Proofpoint-ORIG-GUID: Pi8ej0-RcmxcKFwAiABK4IAlpu_VRTgd X-Proofpoint-GUID: Pi8ej0-RcmxcKFwAiABK4IAlpu_VRTgd X-Rspam-User: X-Rspamd-Server: rspam03 X-Rspamd-Queue-Id: 2DCF94033D X-Stat-Signature: rz3ksyben81gnepanz7yy9wtifrnysnd X-HE-Tag: 1731603873-397993 X-HE-Meta: U2FsdGVkX19UaSJowNn8x0VYOYkUaIoGZHTvUCLQVlZthpvlgbZYm+3MUNLPNu9WbNMssEcaLXZuMPJYkrqQqrVipzhuCPGmGV6nANA2Alhs+eDiuMm+VFeG7jaDbHw2Kq4qEwgTnmjMH4Nrm0QOB87l2IjBKkGdl2r9tYaYeSBwt2Y9IJ0UxhJy34zNLEmUC8G6j2z4EGshjtJRWZ8Bf4ZDGTgkkWUWPfYCSXR8BxY/DKF+ejEEdQnzmgg84XvoONspl6iWx8G5n/Dz0IqNejQF8LnAK3YX8MaOxbbI0Xr74+XlE+W+HU68dIBXx+c+U4Cl/atbFNpGt2TP3FieaLvfCUgrBSsLVuUPoV1pXRB4Lpik41GgeFJOezMKPpuTwG/QfJbsH9PwTAVsqd8u3h+lUE5Ob+/+PnKGStB3WmESt4/n3dFVBqKJJBPGKhchN9Y+pFfqtgx55Yd1OFnLWumXc0wSzki/r4lxm338OnCdmKk5xPBrFHVBItEtTEfe71eh8/W0i5o7DigGMe46JjeWzLdJ8mc9CUB7tvASTfnKMnWjkVzL0rWAItCZ1HGFD9973Fon8+yieCB5lVrxD7DAHu8jkZ9K3Ql90Y7TT2WQ76yCskVkr5O8+T+cAsN8Vrry5FZ43j6mWUw6MBk2YhD0fpslT/gt79+moTQmB2naOD3XvYa8VjVyfRltlYKoFLFlZy3RpFCDuqNZenB7TruY4LTMnhRRZ0QPKQIVVEy78POM1zgwnRkbDuU5O2xFJL/2yJkZyxFqROmi1ULeRmtqlamUEzqOHjMrFkg7SbCdy2kJgBsf+dyyGSvk4o9ZXtCdj53dUx4wUwmU82Uvz537ogu4/jVsdveFo65An8IddxrlF56Evwib7N5aUlwGMW3AZb6acmlVMlpPLRWezRb564d6HN3ovUq5piUvrKvtDudfztDBPCvlycXOWeubt5iexaUN1rbBlCTw6xG gPAhULu7 BGCusS8wTerEjPC3gIRRsxJrN1ugbeK3VD+4TdhL1DJ0iMEjHtFu/yPz19rogFe3wMu1+70cVFtt7fbB8Kh9K7Tg1j1kfy+infbyxAJq3bAwEIwYmTT1JZwJFitJnMjxKrDrfvf/Qw+a1cjB4pI5zKCbc8Hj68/lM5qR/AHE4mEwkA1dX8G43rHaiMsvpqwTBBS9lKCDKprpg9OfHhTCwCJRIE5p3DzPRMWPMqxtiDlMeVHQb2Dy5WzSDSEUvVYVEhT9mI5TBycXP2vT2ZNM5IJMHLw== 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. 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 d0ae808f3a14..318d496debd7 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4155,13 +4155,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) { @@ -4258,16 +4259,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); } /** @@ -5441,7 +5441,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; @@ -5538,7 +5538,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) mas_wr_prealloc_setup(&wr_mas); mas->store_type = mas_wr_store_type(&wr_mas); - request = mas_prealloc_calc(mas, entry); + request = mas_prealloc_calc(&wr_mas, entry); if (!request) return ret; From patchwork Thu Nov 14 17:05:21 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13875510 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 ABDD8D637D4 for ; Thu, 14 Nov 2024 17:07:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2A81E6B00A3; Thu, 14 Nov 2024 12:07:53 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 257896B00B3; Thu, 14 Nov 2024 12:07:53 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 11F956B00B4; Thu, 14 Nov 2024 12:07:53 -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 E58B06B00A3 for ; Thu, 14 Nov 2024 12:07:52 -0500 (EST) Received: from smtpin22.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 9D048ACB5D for ; Thu, 14 Nov 2024 17:07:52 +0000 (UTC) X-FDA: 82785331482.22.DBF95C7 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf22.hostedemail.com (Postfix) with ESMTP id CEF2EC0095 for ; Thu, 14 Nov 2024 17:04:36 +0000 (UTC) Authentication-Results: imf22.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Z1GCbDs1; spf=pass (imf22.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=1731603738; 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=DRxKYAZcCAMW15klVCiRiGLQ4sjCSB7uPPfv42IObWU=; b=8V5hr4vkz5OFUFybuN1ov+ffyWyqkq+u6k7+ZSDEchWy25lZEBH9dj2yFKzkXGowuQlUNj 4CRA0gO8HV0l1OZ91NWm+BNX0wNZUODM5bw5XJBXyZptZWbc9iCdilbJB97FBIerne/n+0 Nbhi1/pVzK/BtGq82I9nJI+gjLYd+ag= ARC-Authentication-Results: i=1; imf22.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=Z1GCbDs1; spf=pass (imf22.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=1731603738; a=rsa-sha256; cv=none; b=0PaJdLhyWcMZOSV5Sk1cHeV89zPCU2y5e6f8HcY5TVZ+tq8WnnEdH1TK8BURIquRCwWLtL 8irEe4DuoyoUCTnXPXFfRb92d60qZ8EcfnNbUy+smCGaTtzVRG50dLG7NXF57dcn4kSI3h qiZ6nRBrweV704WVRtUBKf71QlWNGw4= 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 4AECXUrQ006704; Thu, 14 Nov 2024 17:05:30 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=DRxKY AZcCAMW15klVCiRiGLQ4sjCSB7uPPfv42IObWU=; b=Z1GCbDs1t6Vnl15y76+He YuuuRLWsnt6ujrK8hIL0wKm6QgjMSzD6h7Tjgc1Xm7khuxNP+Hgjayvnbjt8xKnU DxFL/DSVy9o5tug+xlQ9747gU6GyPoTnz20jD062hvdhwd3rASi+9JS3sbhJmPMT UvIJ8pnD/Azc0C+zp0CMhjozcMPgY4RLb/dhMZkRG4nj5tK4y0dy/hexXmcY4VD0 4WDFWvEEgHkU0R4NfJ1MMhzmAas7WkucuXgxfEgjTu6n8ouz8unaoGARYjd6tcUv CUPHMFKg6WA4SDhfolG/ZWrnQcfr7mId9fiDCROu6av6cPGOdFyBHNDY800JbZ2o g== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42t0nwsr6n-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:30 +0000 (GMT) Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEGGpAX022744; Thu, 14 Nov 2024 17:05:29 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 42vuw1jy83-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:29 +0000 Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 4AEH5QmL032739; Thu, 14 Nov 2024 17:05:28 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-39-201-66.vpn.oracle.com [10.39.201.66]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 42vuw1jy5w-3; Thu, 14 Nov 2024 17:05:28 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, Sidhartha Kumar Subject: [PATCH 2/5] maple_tree: use height and depth consistently Date: Thu, 14 Nov 2024 12:05:21 -0500 Message-ID: <20241114170524.64391-3-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 In-Reply-To: <20241114170524.64391-1-sidhartha.kumar@oracle.com> References: <20241114170524.64391-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.62.30 definitions=2024-11-14_05,2024-11-13_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 malwarescore=0 mlxlogscore=975 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2411140134 X-Proofpoint-GUID: 7jgAwCWQElIyqGhjSvDnTmTu9MQckSbD X-Proofpoint-ORIG-GUID: 7jgAwCWQElIyqGhjSvDnTmTu9MQckSbD X-Rspamd-Server: rspam07 X-Rspamd-Queue-Id: CEF2EC0095 X-Stat-Signature: k5t111hyp9sru845wyhxtcrsp1ftrmtx X-Rspam-User: X-HE-Tag: 1731603876-85094 X-HE-Meta: U2FsdGVkX18xVBYBRVVnbS12o4svfwAFej/sAStyOiUq4zKMA3bfIBoWNRupRbaAf/LHv8tBiVA3zioEyhPxb+lstjNOXo+fNsAX6kp7B6ExMT7kfsTP7HRcN5V3IjZdixzQS2OqBlf1AJBr6M5In29HX1D/QJQu8qZJVzfRFh20Ym98+kVIQmoDToZswqcYmhPIlB4Z4bBQAMoaqRJLqwz/QSDB0fwFkdirSGjieCmdBKny8SwSP80opHlm3JfPe7lszlXHTXGgSWFXUTUlfo/txeZjBoU1QTeObeKqZokpEBEqg28HU8P/2WmAbydl/JktHLUemmMsO3tBND9uGluZLNBJ7BLf1Pof6le03HoJVcfivoEH48vzUjTeBhV5K6EBW+w/v53/v0JqDfFcCKGygRT9y2jzrKK9n9/2JdUwd5/NgHfoAS2vGhHW51t0l6sLLX//96Z3X+bXNJyZdab11y2rPWWEt+IIrhzTfo90fA9F3mw1CLRfXuyBKplgcmbIkRHs3WdNUUqaG+erpRUuagNmJpW1zAZtuvcNzcQDKDyycH8Gheh0zIr8ZIoH4CJtHaJ2N5a9M4ZXis9SO/7tiYvZgfIpAhUXYeawDppJT5+dH0umk3tGQfuOvX3scnbXdmKnRSBf1m5eRKs6URw2u14/tlfzx0FiafS+WY7S0OqHKB4dpxyTPRWf9ODtbx2IAzRR7MWYcGhStKIbJSSSn1PhsMRRPg/imn4scmqcxfwhyhX/gMseUrAa4FzJzveoLG8fS9j/VGblD99owsbNwhfAobcLTDClhnLDfkc3dQ29ui0w3UdaQmNiIU1Xy74JxDWSBzFlYg2fYdfF8PMyJv0TrhMfWeZmnW2pkN6Y0t6F/Ebd4NKFPLhZCqsBxsJIyqFn8sDM/WZwUxMcM0edVGza8UaYTTE95MfWdeEXvy2EROlYeT3+kg7mDNJOveMe2nP3mb7Ay8tK1wo /bHVW1ok YWMPLHNSQvMCGhWhAMF0asd0Qvzx70zPndcX07FjnANKPT5q6ldKo2cR83GXsRDqmRM7P4oK5Wg6JFjjha0uGdF+OCPb0P2eCzOwSBK6h0unsLzzeduHgv/D3BIZfrjUotGbxiKNWQLurxU6AhpkAZ2DRnxdQoLZTZoZ1lVThB63PH7CyibFEr7C9pYsZLg8xiLZJReArV8i35E7hsR+AYdsY7TW/GlykB6hCsZe7XCwIci66g5MyT4oXiaMjnvkPByrb3jg3ldW00sE2YVXosWeirg== 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 | 30 +++++++++++++----------------- 1 file changed, 13 insertions(+), 17 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 318d496debd7..21289e350382 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,6 @@ 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->status = ma_active; mas->node = mte_safe_root(root); mas->offset = 0; @@ -1727,7 +1726,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, mas->depth + 1); } else { offset = mte_parent_slot(mas->node); @@ -2888,12 +2887,12 @@ 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)) goto new_root; + l_mas.depth++; mast_ascend(mast); mast_combine_cp_left(mast); l_mas.offset = mast->bn->b_end; @@ -3141,7 +3140,7 @@ 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; + mas->depth = height - 1; } /* * Only a single node is used here, could be root. @@ -3308,6 +3307,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; @@ -3334,7 +3334,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; @@ -3342,7 +3341,7 @@ 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); break; @@ -3439,8 +3438,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)); @@ -3684,8 +3682,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; @@ -3699,8 +3696,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: From patchwork Thu Nov 14 17:05:22 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13875506 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 DAC4DD637D4 for ; Thu, 14 Nov 2024 17:06:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4A5F06B00A5; Thu, 14 Nov 2024 12:06:24 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 42EC26B00AB; Thu, 14 Nov 2024 12:06:24 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 25C546B00AD; Thu, 14 Nov 2024 12:06:24 -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 A01A56B00A5 for ; Thu, 14 Nov 2024 12:06:23 -0500 (EST) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id D5BB4ACBCC for ; Thu, 14 Nov 2024 17:06:22 +0000 (UTC) X-FDA: 82785328080.18.8384B4B Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf11.hostedemail.com (Postfix) with ESMTP id AC1B4400CF for ; Thu, 14 Nov 2024 17:04:38 +0000 (UTC) Authentication-Results: imf11.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=G6OHosqv; dmarc=pass (policy=reject) header.from=oracle.com; 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 ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731603871; a=rsa-sha256; cv=none; b=rtsbJdAv2TcXp5egrTRjLjqBJ1+RPFKjjMi1Kbc+lRlcT3aWxX759KGpQT1Fk++q4k3rav Xgrg6EYBCZBQPs07Ub+FrJn03b1VkaHMHp3BBoFJ0fuEFB0R/MgTum2pFyNgLAk7kN2Dx3 4Bbf97kcin6/XbxembN6bU57S4LeXDQ= ARC-Authentication-Results: i=1; imf11.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=G6OHosqv; dmarc=pass (policy=reject) header.from=oracle.com; 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 ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1731603871; 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=0hRvHf4WYhJpauYsodnpVxyrZ6H8VFblaBb1i/nTs4o=; b=YxgfojQ7HUF+oe/voaObz7D6WDvfNyopsNe3Lwg1godAlPPUSj2jjvyydXTz5x6MPblzIU v6qxzvN13lyhlPt8/n6e8L2Lq194kxv283MA9kx471knl1PmNUilb6lj6QQyExv1SNBkpd 4ajRCDnLphOjDNJW2I6+sWwpIALRmCE= Received: from pps.filterd (m0246630.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 4AED1WDu002323; Thu, 14 Nov 2024 17:05:32 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=0hRvH f4WYhJpauYsodnpVxyrZ6H8VFblaBb1i/nTs4o=; b=G6OHosqvZkJnCWf6jHUrb NwhFfSoai/Hig7KBp0w3wzMRndPi0lQ9cqUgRQFN40EW+h4G5u4cDzr5a4IJ2rQe 0I70AC5P6LYqQ9P/Fc3H/m5rqmVgEO1kc/erOsOodeiJIM44C4UVcJ+8puFc7SZM OKPTlZ9+NeMxCQ63CLdTuIfdI21tCqhkdrUG3UKG5/1anActW74rQGYeDG9fMJ02 l+PK4orL2cCOfi8Ek2KoAJXUVZGzFfKdpsgpHf/Xp5z63J1z7b1O09o131FHmAvS GqPyrl5+phBu6MpY+pbLZfTwMrSCE6aSuefVG+j59RrXl6II2Ijkrbhv1GLd9QZU Q== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42t0k5hkcj-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:31 +0000 (GMT) Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEGVnJE023937; Thu, 14 Nov 2024 17:05:30 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 42vuw1jy8n-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:30 +0000 Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 4AEH5QmN032739; Thu, 14 Nov 2024 17:05:29 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-39-201-66.vpn.oracle.com [10.39.201.66]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 42vuw1jy5w-4; Thu, 14 Nov 2024 17:05:29 +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, Sidhartha Kumar Subject: [PATCH 3/5] maple_tree: use vacant nodes to reduce worst case allocations Date: Thu, 14 Nov 2024 12:05:22 -0500 Message-ID: <20241114170524.64391-4-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 In-Reply-To: <20241114170524.64391-1-sidhartha.kumar@oracle.com> References: <20241114170524.64391-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.62.30 definitions=2024-11-14_05,2024-11-13_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 malwarescore=0 mlxlogscore=999 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2411140134 X-Proofpoint-ORIG-GUID: NhYnhKZPdGkfi9L220eXnIAw8JqYObD6 X-Proofpoint-GUID: NhYnhKZPdGkfi9L220eXnIAw8JqYObD6 X-Rspam-User: X-Rspamd-Queue-Id: AC1B4400CF X-Rspamd-Server: rspam11 X-Stat-Signature: sjx38fpo4oyjzhq76ime7xb96p94bxf9 X-HE-Tag: 1731603878-763163 X-HE-Meta: U2FsdGVkX18Lhg9WYK733p/JLKVbUemop6a8/imCSGx6aeNDP1gd8Ea/Wb1w/BfrH98Tc4HClV6Kt0jI0LU56nPIuBhZqbI6X2OwUHaiyx7SG47wr+CPsefKcgppF3lYuTJZHdC5nK72TWyvPo++sLnJygdYyTvmm5sCB/aeoVWYiKsQ6YdJ1pFBfQte8rXxWrdXAiu1oXSLFXKWVBYiA66IcfLdM1z6ySZ6ChadaUtzOsW1HiE7vZOLJXBvB/pMYGXKnC/c/otsaTQPlGtE36YPB8NxK4JjXa4T+cOy8aWKoUjm0fwgIA8HnTcvcMlgsGyzrYMRboIIixleBVHGGWDV2gVjdSHp7N6GFOs7vjRdg0qzSppjSfJeyhmDvYDsMpetpvDQqn/9Mx88zXQ3IdqFhKYPPJemmAYaayAs22WN3RNXHex4tKq+luY6VzcKHYIkS/UuPL8+f/lpxLHDQrl6RXea5vE/oOx96LF7dbsro37VhJ9VMEc4Y1ryBJgEjrjipQLFx+RxAp1WQC702x+rIZjQO01hHpIEsRmqga43xbaOJdV9VoFGMzqMy3hLBkP4RAYA0fLEF2A+GSAxGaNpOkn6BldybOgUrkdk1RPY8UxN7hyykgGYlPpxX3fTIkewIAlHjhP/lvmU1cAHVylycoziD6m5STtS0SKisXcCUfA6iAfW4842ppm9OrKQ2Hine7h7CulmZrYMj/37gCpv8iyA3pJcUSAN13NI2H5bTfRAB6ReJtxLOyb2dl0anVmmvhCbZA4eB68yCQz9e2NCeZ6cDwB5/dsv1ardCs7vAlis1lPp805dTljPFLMuLRGHGVcU3IzC1hGZfbwNLduUOqmXPmURaRBlY3q8kFSlrKgLf2AVYyR3nmVeu1RMFJg3Kb+BEqDkGRhlXZnDmMGdo8dy2sV/zYoD1PReFjjIQthQMB596IltYZix8w1V/psRCtUqpMOCH+Ri8Hb CHuwPPPY FByZbXX2s+DI3fK/oOWv1KJFJBJoWE9E9aTDfhHK/1wWWGQ/OgNPhhocjgH7/bsIcL70tVde2jSI0JDAoiod7jKgr2qclBf4woB+WGnUrt7zvYKwgAlWgPFwoJx3vSijWjOSycLIWVJlNq+QRWurkmleQUnE8ggQMTNvIO0STFZQr/NN/nSzjnjn+bCUo6l2o5QbKcBdzvZrh7xq/+pL5QaWH5NQ7mYif+3p53jnXS5VQZbqbs2DlzBiISU34ybW/MdKF+cvnGmH7PLgrKQB2y9TheA== 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 allocations. Rebalancing 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 | 97 +++++++++++++++++++++++++++++--- 3 files changed, 100 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 21289e350382..f14d70c171c2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3545,6 +3545,9 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) if (ma_is_leaf(wr_mas->type)) return true; + if (mas->end < mt_slots[wr_mas->type] - 1) + wr_mas->vacant_height = mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } @@ -4159,7 +4162,9 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas) static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) { struct ma_state *mas = wr_mas->mas; - int ret = mas_mt_height(mas) * 3 + 1; + unsigned char height = mas_mt_height(mas); + int ret = height * 3 + 1; + unsigned char delta = height - wr_mas->vacant_height; switch (mas->store_type) { case wr_invalid: @@ -4177,13 +4182,13 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) ret = 0; break; case wr_spanning_store: - ret = mas_mt_height(mas) * 3 + 1; + ret = delta * 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..bc8b107e0177 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,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_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) != 0); mas_set_range(&mas, 0, 200); From patchwork Thu Nov 14 17:05:23 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13875507 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 8FAEED68B3F for ; Thu, 14 Nov 2024 17:06:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1E3B66B00AC; Thu, 14 Nov 2024 12:06:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 16DAF6B00AD; Thu, 14 Nov 2024 12:06:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id F2ABD6B00AE; Thu, 14 Nov 2024 12:06:31 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id CA1666B00AC for ; Thu, 14 Nov 2024 12:06:31 -0500 (EST) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 7CF3C1A123C for ; Thu, 14 Nov 2024 17:06:31 +0000 (UTC) X-FDA: 82785327114.07.D4AED75 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf01.hostedemail.com (Postfix) with ESMTP id F19EF40074 for ; Thu, 14 Nov 2024 17:04:58 +0000 (UTC) Authentication-Results: imf01.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=I15HK8i7; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf01.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=1731603869; a=rsa-sha256; cv=none; b=1zF1lPuF5bQafHSKe9E8Rp5R60ZR1FMiE5OS46Bwl2IPla5KHe9m7NphxZxOtknrcjnJrS Bojr1IINaHma7L8AHakSsPSH91tzxEVhH8/PO9ynSxBRyuDvxm6tMXVICXv1n5s+WPF7R1 S9KECoZhh/L/7PF4gKMeHjooujVGPF8= ARC-Authentication-Results: i=1; imf01.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=I15HK8i7; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf01.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=1731603869; 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=7n8i7NEm1gSxP0N4uiNn0lAGElW5oeiIKP+aNCEbcoY=; b=KhW9GBJtPDQFNhcO3aYZMfBzY/KNJ39MhMyr22iKHf6SVGHLSsYbkUvFxHLh7rm+5ZU2Oy bcr82xPvB5ETCJEuJwTCe+zuAsdShTDlNLZ/5H+a2BOabbkJah6vBi4WjK4k92zdOmoaNh DwZqCiScaSGmmM/e+4Cqu3M3DAa7ftk= 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 4AECwwRQ015665; Thu, 14 Nov 2024 17:05:32 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=7n8i7 NEm1gSxP0N4uiNn0lAGElW5oeiIKP+aNCEbcoY=; b=I15HK8i7hsG0PDKMeAozq TJ2kPd9fpgiRXiYPzyKxxlpgyDqPVrKSFKp8h2zOrWIPVwyphFppHW5Qu1Pur2NJ ix4Jn8CmrY2exq7D7H9XKqXAmkLhd5Ki9AVzxTbKrKQXcVfFzNH46z3VjDz8ZmlO FqhwjuFfGWVX4OL/D3JuhGVrTeF/Dx+7vL4wa/1nEQ8QmNmct+xzFPodRbiH2Zdr scueIvKDFPbHHHUuvEW3MdYdMI8zisB6FoF3Ag2+aaOKIj571qdJA4AsQ81G6HdZ r5WXszi0fXuIxB6SCIIh5uO9Y7niRG0Q5vDBpUPMxipu2KxjsXuu28mCcdFfGsYz w== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42t0k29phr-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:31 +0000 (GMT) Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEFZCp4022682; Thu, 14 Nov 2024 17:05:31 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 42vuw1jy98-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:30 +0000 Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 4AEH5QmP032739; Thu, 14 Nov 2024 17:05:30 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-39-201-66.vpn.oracle.com [10.39.201.66]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 42vuw1jy5w-5; Thu, 14 Nov 2024 17:05:30 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, Sidhartha Kumar Subject: [PATCH 4/5] maple_tree: break on convergence in mas_spanning_rebalance() Date: Thu, 14 Nov 2024 12:05:23 -0500 Message-ID: <20241114170524.64391-5-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 In-Reply-To: <20241114170524.64391-1-sidhartha.kumar@oracle.com> References: <20241114170524.64391-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.62.30 definitions=2024-11-14_05,2024-11-13_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 malwarescore=0 mlxlogscore=871 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2411140134 X-Proofpoint-ORIG-GUID: hAce8W2brrC5ZjcaybhLTlN17kwCsQrq X-Proofpoint-GUID: hAce8W2brrC5ZjcaybhLTlN17kwCsQrq X-Rspam-User: X-Rspamd-Queue-Id: F19EF40074 X-Rspamd-Server: rspam11 X-Stat-Signature: n5jymsurpeijhb8iixrk4ibpixe97oby X-HE-Tag: 1731603898-787364 X-HE-Meta: U2FsdGVkX1/Si+PSa2hYdpXymWEwkwf57w5StRZ/tvWpZegoP87V0fYYD1Ip4twqMy9Xtvxy9bSCXpvVI6Gx8DbB6t61CTJl5ET3S72npeaLCyavrDidUNYj0u23y1U88KhgjNco3pyaQ2og3eFdQd9IX1N21O1REaH2pqCDjb4e14yD/0J+OHZVudnHwLRstJpJlD/iNbnMyjv/bDZOa4lGeZlO4cFUgagAyhx9tYekZwQosLq6dopE44T9EgkHrev4DbPaI8xNGR3LvMIF4JJZ+alYyNNRNgL+1w7+vwjq8l0kVyk4/2Gf+U0aqM2NHK3GJh+DcJdDK18YjlCSoy1mGx0JQnDQCBle30rqU8VCNEo1PjFvBcJQeUTiUlhQBjYWK9c1Fh8mfSgzBxyVVnwIznVgGZfdAI8v8Rjru2W7p+ZMkLggiH/ZFXs0p2ESFST8xUW2vVtBihvEyghfk5L/8URnaXM2xdyUbYc8SZVrcZwMxhT7QGmd51zpXETMtCFmZaPrF3cW/xiS5eeWJp8W1hMi0U9ytMeEaRm7NXgipdx1EsA45SPgSIoW5QFgxBAkDQZpJGAme9W1MY/i7mtQfUPw2j7fdp6UIo/R0GLLWgqieEd/Ei5E2hq0Mlcb1+yrgzyTM5UTUXHc4qHNqKMKW0K/xglptvghXFscrjnX5xz18Nzp8Z7Pdae1xdEFfSNTD0CFsfRSV46Iw9r6GSbGuYHlyF+gOnTL87e61i1biEWBOa9jCVy4Ds0FlPAMjN5ijoIOUKhHes/kRmzbpm0WzxFnUnre+1fszOfQjKUrTVrGoKR3RNzw5KGclSNYbiWONU+KRNsQoGjAwYNHVVCHsxD4CPNeLBSI/KN0DahKMLDHp/VZoB7x9HVfPAh/q3a+bOzxsjN8FOQkdClWnX1UtpahFYX0Lyy611zQ6+eSus82ZNr8q49qZSbvtdwkv9m7KH7f9ndc24qrjWX bKqetoNJ lHrwUJaEU3gq42QH43XYNKYlu9vmrVuN5Sy3gasJ37KANXifQLAvxW7Kfhg8iUc/HoiTD+3BveU6vooeIc4FgR4MKXSRE0vcJ6YpFEgm6kseCNzYyrMfRWDiQC93In4nw+8M4Acrsuk0sxc+pf1BqfKgD3C7bCNA88oYJXrtppm4s0jklrKUDfyeaCqeSPPICaE0XWiCGlh+GWEtVWIqrz9I9gu9aBS1dMSs7MdOdvEaOP+/70y7/wneSL1xnmidEr6bOv6O1Hng/c3CM5N7e0mkxIQ== 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 Signed-off-by: Sidhartha Kumar Reviewed-by: Wei Yang --- 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 f14d70c171c2..59c5c3f8db30 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2904,11 +2904,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 Thu Nov 14 17:05:24 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sidhartha Kumar X-Patchwork-Id: 13875509 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 7C1A4D637D4 for ; Thu, 14 Nov 2024 17:07:32 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0FA936B0096; Thu, 14 Nov 2024 12:07:32 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 083786B00B1; Thu, 14 Nov 2024 12:07:32 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E3FB96B00B2; Thu, 14 Nov 2024 12:07:31 -0500 (EST) 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 BDFD56B0096 for ; Thu, 14 Nov 2024 12:07:31 -0500 (EST) Received: from smtpin20.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 7528D8137E for ; Thu, 14 Nov 2024 17:07:31 +0000 (UTC) X-FDA: 82785328836.20.4C141C8 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf06.hostedemail.com (Postfix) with ESMTP id 7436F1800EC for ; Thu, 14 Nov 2024 17:05:03 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=e5sEXTDf; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf06.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=1731603872; a=rsa-sha256; cv=none; b=jTrCW9crt6AevTvwgaoc1MU+i0MNp29QR/qhbGZRa1mM/spFiBWBvFH4ZGYBKyNer/ONEo IWSLhldyvxy+BbMxWvuL5vDQPCWNcgD6c+G3YblMMCut35+sz+uTXK18ntTzwojqPiNBNy JsW+/C60chDxUT9DlmDHuKLqwbdp+RQ= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=e5sEXTDf; dmarc=pass (policy=reject) header.from=oracle.com; spf=pass (imf06.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=1731603872; 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=ynPl9gjds2k6dEiCMO+N2WSsdWiMIGwmXOvf0GpdocM=; b=IvZI4v92TR2M5G5LAscNjNQ3CwoJhWBQF8Dw9AwdUCCUArsfFpwOj3o/H0kCg+pSYa7w1z 5bbNhZqpgD8ykMtpxrWu8xCqTuBeaejXHuxPXvr5lBtc19VOpRk9KOEqLSS59nY98mvKCI FzCOEdZNT8AkzPQe9W0JoSyZN/yLmjw= 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 4AECsbMo014973; Thu, 14 Nov 2024 17:05:34 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=ynPl9 gjds2k6dEiCMO+N2WSsdWiMIGwmXOvf0GpdocM=; b=e5sEXTDfO+9txCvBL2gaO PseoX1Eu4WM0EXd5Ua2tbRQFg21bv7KA3iM8o1O9Ft/JnW2n7NXbXDLVd2ziBk4b HscKR7HmWMTNgTGw3TQqz9OnMETwj0az+WHOz0BSHqUZBkEKrL3b7mgPxFwOP6wr fb7ChzvfT+YXJa30KiBDpU5nzGBWGHT4IaHV+vZZS3M6rdnwaoW9YKxnTtHw21XG ynTRsJtRJV7yyXi9d37B+uPJBA1l58W9KM3JE+Vib6QPzG0qEzJUJC/GrrVUq941 kPpJLdtycht+uHqGQqLt5B4LUBADwoePYA/GJvskSxqxsD5PWrafIOr1CUicb/6Q A== Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.appoci.oracle.com [138.1.37.129]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 42t0k29phu-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:32 +0000 (GMT) Received: from pps.filterd (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (8.18.1.2/8.18.1.2) with ESMTP id 4AEGqCFR022850; Thu, 14 Nov 2024 17:05:31 GMT Received: from pps.reinject (localhost [127.0.0.1]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTPS id 42vuw1jy9u-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 14 Nov 2024 17:05:31 +0000 Received: from phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com [127.0.0.1]) by pps.reinject (8.17.1.5/8.17.1.5) with ESMTP id 4AEH5QmR032739; Thu, 14 Nov 2024 17:05:31 GMT Received: from sidkumar-mac.us.oracle.com (dhcp-10-39-201-66.vpn.oracle.com [10.39.201.66]) by phxpaimrmta03.imrmtpd1.prodappphxaev1.oraclevcn.com (PPS) with ESMTP id 42vuw1jy5w-6; Thu, 14 Nov 2024 17:05:31 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, Sidhartha Kumar Subject: [PATCH 5/5] maple_tree: add sufficient height Date: Thu, 14 Nov 2024 12:05:24 -0500 Message-ID: <20241114170524.64391-6-sidhartha.kumar@oracle.com> X-Mailer: git-send-email 2.46.0 In-Reply-To: <20241114170524.64391-1-sidhartha.kumar@oracle.com> References: <20241114170524.64391-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.62.30 definitions=2024-11-14_05,2024-11-13_01,2024-09-30_01 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 mlxscore=0 spamscore=0 adultscore=0 phishscore=0 malwarescore=0 mlxlogscore=999 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2409260000 definitions=main-2411140134 X-Proofpoint-ORIG-GUID: Y-Yt0maQHdk3t4xGXgbaBnY9e5HIwRyM X-Proofpoint-GUID: Y-Yt0maQHdk3t4xGXgbaBnY9e5HIwRyM X-Rspam-User: X-Rspamd-Queue-Id: 7436F1800EC X-Rspamd-Server: rspam01 X-Stat-Signature: p9fw148r43zkoqe3e1awkxpknj3dy4k8 X-HE-Tag: 1731603903-638366 X-HE-Meta: U2FsdGVkX1+U+LIsQHdhEi6sJCp83Zzuo+hOhX2T1tvjL0eGsxurAPLQQXC0leAxaHcyX3crGAags/2vCBReq1qSrr5sUKNE51v+AqShisqWTnbYdAvT6T4jilATIsZuev2wwUiyRihGDnfeQuPnIOTsDXNU6gUA9MU6g2UgYjJzjEyzQWjLNzhI7nxgC45xz/7TtjMcCJsZQ8CTV03Fk4+hOq+0+4YSEvhy40LFaOq54EwqhU2XVUQJR3rhZpnXLUPBWazDhuHYieGAGf/w6LtCxgl4x1E8TW0CKXIiJ8e4zMpDOJhaniGn9fysk4XYQUNR/16JOEbGnembkob6onW1iXNfXdWwH6wHrqnkFzwFVlJhyE38Ze9VvdLxM8qHfj4CvcBH4ER5RLZ666y84bIAm5DYXoN13cAgtpc7DyZXLWWLFtTpVn/OZ0sxvLwID7VJS9eOseQfRu8h2Yhs3/qDKjoek9a3bfEbg1R2iGFtlK207q5VnovDr1TZ6EMwQBw5Zxw6pKx8kAJRtPSQTQDIJuF25jjWVA2+8qwrKlxPv2rMxBAa8b9Q3Rd6VfKwlelEDyp/XbQlHmv4Yv72jKT9hnZPMLg3Gw10zbB+KldFUgN4aoIA11bY9x73n8GrV76u7sXuOxb7O745Q/rZv9J2O2apWAQb90H/AGxTG7AvwmjG3hNjqRJq844vIvb+UepCsik+G2y/kbAROk+B6W129yXPtTFMKqmuP60BWaN+K+9KS5Xm6yohFjfPmEXh23rq3lFYoQ4X+g/vp0LiPD1+6/XnOltRG6KkxvAMxKw5M6mvbSgpCFyUqq01vo+gO8fJWXNUJEcH5dM73z8nyEdy23lfJJsFVo5YaqgLetF4OlcNReEBx8Qp93RboAtOo1BzZvVkI+Gj5KY5RVNA3mn/zEAXWBngI0dfnUF3OQ0QOHtRGbIpVF5+jYZ1nk+WSVsqbYcQa7bohZJiCZ0 iD6Kb6fz McoFhDqvuEodIC/1mweAQ6qAUGckI0HRC7wi/ozf8HUorTkzAFrRFeQQn23o5myLP+oh/Z4zTxpvUBJvzWUnMpAEjAEpkbN7Fls5DeXRrrMpVMD7cv/ZGnHH4Sk/5erSZyuVCJDl+/XpvPqHW5BBh6+DjMpyutmnWmp+UbSXsHghL1J3XGkoVZBWbfELveGRFGRLrxAW83sY7ykw7SHW0F60ZbP+0AEZipTQg5y8b0Kuf8EQK99vkph2W6YqskOn2hgFBQ6pheTa5WLul0blGEstYLQ== 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 wr_rebalance case. Signed-off-by: Sidhartha Kumar --- include/linux/maple_tree.h | 4 +++- lib/maple_tree.c | 14 +++++++++++++- tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 44 insertions(+), 2 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 59c5c3f8db30..3d39773601d3 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3558,6 +3558,14 @@ 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; + + if (mas->end > mt_min_slots[wr_mas->type] + 1) + wr_mas->sufficient_height = mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } @@ -4198,7 +4206,11 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry) 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; + break; + } + 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 bc8b107e0177..f55ab8c8b491 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36329,6 +36329,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) { @@ -36495,6 +36519,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);