From nobody Tue Dec 16 19:40:40 2025 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EBCED28F938 for ; Thu, 10 Apr 2025 19:15:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.177.32 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312507; cv=none; b=GoYPKGQ1ys1kRyK3KDwJfAbVTpDfD15MKaGmKL1OTL4PZ6x0VQ3PM85Y64puBgTJVo8DHeUBcnMULms/WxWeNE2UuYNSon2jDP0QDthF9UPRnCS0bTyXxHzoxyrEo+nYCQWqJbMLFwgwjBAsRfQ7hlwdcGsfiJaNZJueS6edyow= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312507; c=relaxed/simple; bh=5FmvgLwUgefF/15jQPZPuLOR7HLUsegiYz+SY3v7WMM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=mO1LpKYnxa3oI68TDZ/lSv6AHaH0hW1SkrNTvbYmoG5RyHS/cuz3qlSSBPJLOWf93MqT/JkV82YysybBpT+w+MdEi7KSX3M7YyliyMR4Hu6i4oA4cLDQgsLZ9N0ZCFp6lx6bJpCSwk1BrhruCSnlAkpwOgG7QteUK1jqrqVir08= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com; spf=pass smtp.mailfrom=oracle.com; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b=hRFyQ+uF; arc=none smtp.client-ip=205.220.177.32 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=oracle.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="hRFyQ+uF" 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 53AIH4ZK012989; Thu, 10 Apr 2025 19:14:54 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=cc :content-transfer-encoding:date:from:in-reply-to:message-id :mime-version:references:subject:to; s=corp-2023-11-20; bh=xifEa GxLrCosb9AknfMROurmyL6jhk0BySHE36IGbs0=; b=hRFyQ+uF6NWCF7Hj3dR9L ICXRyfv0BPgx+0NVG/vKsxa+OE7cMzOody/1zxBtzDLqreW0LBPO3YLNOch5XCzB bmsgBq3F7Fkh1tjS8IzHk5pbFAn2MyYYKcdoCxU0HGzoZdr9MB1mc14uCJNuNxYc jSTbtwBGk+38iSNsBV40LOAvN08BoMNsLM+XNqaIxF9sGo1ZPqDWfWRojVJt+sT2 1DH0JXjF7fk6wnNPyqI1Sv2FCbcnHzQECW4kJHyvz3sA2L+81DsGTadOs7AS5QV6 txUQbqj+7Qu7X7K81OeZjqm0AbsLtAB2FlkSzMDJPuseaKtX99El2MLWlWV9ZvEA A== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45xk4hr4qh-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:54 +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 53AIwiO4023934; Thu, 10 Apr 2025 19:14:53 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyk1ghq-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:53 +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 53AJEn8w040606; Thu, 10 Apr 2025 19:14:52 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-2; Thu, 10 Apr 2025 19:14:52 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, willy@infradead.org, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v5 1/6] maple_tree: convert mas_prealloc_calc() to take in a maple write state Date: Thu, 10 Apr 2025 19:14:41 +0000 Message-ID: <20250410191446.2474640-2-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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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: lb46VRQHj5gIiT6ZeVph2vTkQyPfrviy X-Proofpoint-ORIG-GUID: lb46VRQHj5gIiT6ZeVph2vTkQyPfrviy Content-Type: text/plain; charset="utf-8" In a subsequent patch, mas_prealloc_calc() will need to access fields only in the ma_wr_state. Convert the function to take in a ma_wr_state and modify all callers. There is no functional change. Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d0bea23fa4bc..f25ee210d495 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4140,13 +4140,14 @@ static inline void mas_wr_prealloc_setup(struct ma_= wr_state *wr_mas) /** * mas_prealloc_calc() - Calculate number of nodes needed for a * given store oepration - * @mas: The maple state + * @wr_mas: The maple write state * @entry: The entry to store into the tree * * Return: Number of nodes required for preallocation. */ -static inline int mas_prealloc_calc(struct ma_state *mas, void *entry) +static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entr= y) { + struct ma_state *mas =3D wr_mas->mas; int ret =3D mas_mt_height(mas) * 3 + 1; =20 switch (mas->store_type) { @@ -4243,16 +4244,15 @@ static inline enum store_type mas_wr_store_type(str= uct ma_wr_state *wr_mas) */ static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *en= try) { - struct ma_state *mas =3D wr_mas->mas; int request; =20 mas_wr_prealloc_setup(wr_mas); - mas->store_type =3D mas_wr_store_type(wr_mas); - request =3D mas_prealloc_calc(mas, entry); + wr_mas->mas->store_type =3D mas_wr_store_type(wr_mas); + request =3D mas_prealloc_calc(wr_mas, entry); if (!request) return; =20 - mas_node_count(mas, request); + mas_node_count(wr_mas->mas, request); } =20 /** @@ -5397,7 +5397,7 @@ void *mas_store(struct ma_state *mas, void *entry) return wr_mas.content; } =20 - request =3D mas_prealloc_calc(mas, entry); + request =3D mas_prealloc_calc(&wr_mas, entry); if (!request) goto store; =20 @@ -5494,7 +5494,7 @@ int mas_preallocate(struct ma_state *mas, void *entry= , gfp_t gfp) =20 mas_wr_prealloc_setup(&wr_mas); mas->store_type =3D mas_wr_store_type(&wr_mas); - request =3D mas_prealloc_calc(mas, entry); + request =3D mas_prealloc_calc(&wr_mas, entry); if (!request) return ret; =20 --=20 2.43.0 From nobody Tue Dec 16 19:40:40 2025 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 19BFC28F937 for ; Thu, 10 Apr 2025 19:15:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.177.32 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312509; cv=none; b=JkrVnWrPuvgAvr3pzGy/3lAZEpbFlNexB8shC/V7ml5VAhZgS0nsz5ONnKrfng0X8I5AlDVot5SYOw3FeDuraghYjbBY5C3uQ0JKM5bNX7yMxWVKv/H1ebxDDdl4ajvVzTdmYr+pieKdhsCLjFUUfZ/42V+r0FzQCNYYa/KFL6s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312509; c=relaxed/simple; bh=E1JCvNFvhIW5rQnJSnsvMj2n6146/fPOT9LCQu8SHjc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=fE09Y9YT8ZehnYTeRYv40l0tka9HUQ47brNSIChHXVT04scZzHCbpeZQA0hMphj4VYgSQ/bOUR5QSqkLvFMMMB31/c/+QUlb6uiCz2tYBcUvyV34+BMLSDC0gIYsKFt4MaXI9XsLYX0cQw002LGUd/RUUuFOJkD8sJBXoRMKrKE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com; spf=pass smtp.mailfrom=oracle.com; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b=aV23hR8+; arc=none smtp.client-ip=205.220.177.32 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=oracle.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="aV23hR8+" Received: from pps.filterd (m0246632.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 53AJ6xVB029250; Thu, 10 Apr 2025 19:14:55 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=KmKo7 /PrYVRtzCvlS678dWbHpbDnEMGXArxjp/d3Igg=; b=aV23hR8+ElPHylSxrLoKR rCtE0GiQlA4Ps0/8ZNz35NCEsuXFwevE5M47RlzXTavAwK+bAXyWWxBeKUhH3KU7 yASR3C6vuVYPAqvdq5T44HDXSEdGWX9IDq87f4MdBrcrrI558bchdnBlVGfZs7B8 MNkqOdWayWymlohFFjPU0vV9kfILiBRLUtVZeK+BkWtsGipzUe18poD4i/GsM0JT p3OcnAj7TXfWbL6Sf8bb7Ol5fP3AO8LujsKZYgeSOYfESR7Vm4jyPLtA/UD3qZVh rsdw5zwyoTjCrICkG2qhcSb3D+9OdIEFytFhEaeVkM1TH0HYpcd7pv7vvAAg9re7 A== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45xkuy00h5-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:55 +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 53AHXse3023885; Thu, 10 Apr 2025 19:14:54 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyk1gj6-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:54 +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 53AJEn90040606; Thu, 10 Apr 2025 19:14:53 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-3; Thu, 10 Apr 2025 19:14:53 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, willy@infradead.org, Sidhartha Kumar Subject: [PATCH v5 2/6] maple_tree: use height and depth consistently Date: Thu, 10 Apr 2025 19:14:42 +0000 Message-ID: <20250410191446.2474640-3-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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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: Nn30Y82tv1P5kLvL676yEX99mkhp459F X-Proofpoint-ORIG-GUID: Nn30Y82tv1P5kLvL676yEX99mkhp459F Content-Type: text/plain; charset="utf-8" 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. In mas_spanning_rebalance(), l_mas.depth was being used to track the height based on the number of iterations done in the main loop. This information was then used in mas_put_in_tree() to set the height. Rather than overload the l_mas.depth field to track height, simply keep track of height in the local variable new_height and directly pass this to mas_wmb_replace() which will be passed into mas_put_in_tree(). This allows up to remove writes to l_mas.depth. Signed-off-by: Sidhartha Kumar Reviewed-by: Liam R. Howlett --- lib/maple_tree.c | 84 +++++++++++++++++--------------- tools/testing/radix-tree/maple.c | 19 ++++++++ 2 files changed, 63 insertions(+), 40 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f25ee210d495..195b19505b39 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); } =20 -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 =3D mas->tree->ma_flags; + unsigned int new_flags =3D mt->ma_flags; =20 new_flags &=3D ~MT_FLAGS_HEIGHT_MASK; - MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX); - new_flags |=3D mas->depth << MT_FLAGS_HEIGHT_OFFSET; - mas->tree->ma_flags =3D new_flags; + MT_BUG_ON(mt, height > MAPLE_HEIGHT_MAX); + new_flags |=3D height << MT_FLAGS_HEIGHT_OFFSET; + mt->ma_flags =3D new_flags; } =20 static unsigned int mas_mt_height(struct ma_state *mas) @@ -1371,7 +1371,7 @@ static inline struct maple_enode *mas_start(struct ma= _state *mas) root =3D mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { - mas->depth =3D 1; + mas->depth =3D 0; mas->status =3D ma_active; mas->node =3D mte_safe_root(root); mas->offset =3D 0; @@ -1712,9 +1712,10 @@ static inline void mas_adopt_children(struct ma_stat= e *mas, * node as dead. * @mas: the maple state with the new node * @old_enode: The old maple encoded node to replace. + * @new_height: if we are inserting a root node, update the height of the = tree */ static inline void mas_put_in_tree(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, char new_height) __must_hold(mas->tree->ma_lock) { unsigned char offset; @@ -1723,7 +1724,7 @@ static inline void mas_put_in_tree(struct ma_state *m= as, if (mte_is_root(mas->node)) { mas_mn(mas)->parent =3D 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 { =20 offset =3D mte_parent_slot(mas->node); @@ -1741,12 +1742,13 @@ static inline void mas_put_in_tree(struct ma_state = *mas, * the parent encoding to locate the maple node in the tree. * @mas: the ma_state with @mas->node pointing to the new node. * @old_enode: The old maple encoded node. + * @new_height: The new height of the tree as a result of the operation */ static inline void mas_replace_node(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, unsigned char new_height) __must_hold(mas->tree->ma_lock) { - mas_put_in_tree(mas, old_enode); + mas_put_in_tree(mas, old_enode, new_height); mas_free(mas, old_enode); } =20 @@ -2536,10 +2538,11 @@ static inline void mas_topiary_node(struct ma_state= *mas, * * @mas: The maple state pointing at the new data * @old_enode: The maple encoded node being replaced + * @new_height: The new height of the tree as a result of the operation * */ static inline void mas_topiary_replace(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, unsigned char new_height) { struct ma_state tmp[3], tmp_next[3]; MA_TOPIARY(subtrees, mas->tree); @@ -2547,7 +2550,7 @@ static inline void mas_topiary_replace(struct ma_stat= e *mas, int i, n; =20 /* 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); =20 /* Update the parent pointers in the tree */ tmp[0] =3D *mas; @@ -2631,14 +2634,15 @@ static inline void mas_topiary_replace(struct ma_st= ate *mas, * mas_wmb_replace() - Write memory barrier and replace * @mas: The maple state * @old_enode: The old maple encoded node that is being replaced. + * @new_height: The new height of the tree as a result of the operation * * Updates gap as necessary. */ static inline void mas_wmb_replace(struct ma_state *mas, - struct maple_enode *old_enode) + struct maple_enode *old_enode, unsigned char new_height) { /* Insert the new data in the tree */ - mas_topiary_replace(mas, old_enode); + mas_topiary_replace(mas, old_enode, new_height); =20 if (mte_is_leaf(mas->node)) return; @@ -2824,6 +2828,7 @@ static void mas_spanning_rebalance(struct ma_state *m= as, { unsigned char split, mid_split; unsigned char slot =3D 0; + unsigned char new_height =3D 0; /* used if node is a new root */ struct maple_enode *left =3D NULL, *middle =3D NULL, *right =3D NULL; struct maple_enode *old_enode; =20 @@ -2845,8 +2850,6 @@ static void mas_spanning_rebalance(struct ma_state *m= as, unlikely(mast->bn->b_end <=3D mt_min_slots[mast->bn->type])) mast_spanning_rebalance(mast); =20 - l_mas.depth =3D 0; - /* * Each level of the tree is examined and balanced, pushing data to the l= eft or * right, or rebalancing against left or right nodes is employed to avoid @@ -2866,6 +2869,7 @@ static void mas_spanning_rebalance(struct ma_state *m= as, mast_set_split_parents(mast, left, middle, right, split, mid_split); mast_cp_to_nodes(mast, left, middle, right, split, mid_split); + new_height++; =20 /* * Copy data from next level in the tree to mast->bn from next @@ -2873,7 +2877,6 @@ static void mas_spanning_rebalance(struct ma_state *m= as, */ memset(mast->bn, 0, sizeof(struct maple_big_node)); mast->bn->type =3D mte_node_type(left); - l_mas.depth++; =20 /* Root already stored in l->node. */ if (mas_is_root_limits(mast->l)) @@ -2909,8 +2912,9 @@ static void mas_spanning_rebalance(struct ma_state *m= as, =20 l_mas.node =3D mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), mte_node_type(mast->orig_l->node)); - l_mas.depth++; + mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, &l_mas, true); + new_height++; mas_set_parent(mas, left, l_mas.node, slot); if (middle) mas_set_parent(mas, middle, l_mas.node, ++slot); @@ -2933,7 +2937,7 @@ static void mas_spanning_rebalance(struct ma_state *m= as, mas->min =3D l_mas.min; mas->max =3D l_mas.max; mas->offset =3D l_mas.offset; - mas_wmb_replace(mas, old_enode); + mas_wmb_replace(mas, old_enode, new_height); mtree_range_walk(mas); return; } @@ -3009,6 +3013,7 @@ static inline void mas_destroy_rebalance(struct ma_st= ate *mas, unsigned char end void __rcu **l_slots, **slots; unsigned long *l_pivs, *pivs, gap; bool in_rcu =3D mt_in_rcu(mas->tree); + unsigned char new_height =3D mas_mt_height(mas); =20 MA_STATE(l_mas, mas->tree, mas->index, mas->last); =20 @@ -3103,7 +3108,7 @@ static inline void mas_destroy_rebalance(struct ma_st= ate *mas, unsigned char end mas_ascend(mas); =20 if (in_rcu) { - mas_replace_node(mas, old_eparent); + mas_replace_node(mas, old_eparent, new_height); mas_adopt_children(mas, mas->node); } =20 @@ -3114,10 +3119,9 @@ static inline void mas_destroy_rebalance(struct ma_s= tate *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; =20 @@ -3126,7 +3130,6 @@ static inline void mas_split_final_node(struct maple_= subtree_state *mast, mast->bn->type =3D maple_arange_64; else mast->bn->type =3D maple_range_64; - mas->depth =3D height; } /* * Only a single node is used here, could be root. @@ -3214,7 +3217,6 @@ static inline void mast_split_data(struct maple_subtr= ee_state *mast, * mas_push_data() - Instead of splitting a node, it is beneficial to push= the * data to the right or left node if there is room. * @mas: The maple state - * @height: The current height of the maple state * @mast: The maple subtree state * @left: Push left or not. * @@ -3222,8 +3224,8 @@ static inline void mast_split_data(struct maple_subtr= ee_state *mast, * * Return: True if pushed, false otherwise. */ -static inline bool mas_push_data(struct ma_state *mas, int height, - struct maple_subtree_state *mast, bool left) +static inline bool mas_push_data(struct ma_state *mas, + struct maple_subtree_state *mast, bool left) { unsigned char slot_total =3D mast->bn->b_end; unsigned char end, space, split; @@ -3280,7 +3282,7 @@ static inline bool mas_push_data(struct ma_state *mas= , int height, =20 mast_split_data(mast, mas, split); mast_fill_bnode(mast, mas, 2); - mas_split_final_node(mast, mas, height + 1); + mas_split_final_node(mast, mas); return true; } =20 @@ -3293,6 +3295,7 @@ static void mas_split(struct ma_state *mas, struct ma= ple_big_node *b_node) { struct maple_subtree_state mast; int height =3D 0; + unsigned int orig_height =3D mas_mt_height(mas); unsigned char mid_split, split =3D 0; struct maple_enode *old; =20 @@ -3319,7 +3322,6 @@ static void mas_split(struct ma_state *mas, struct ma= ple_big_node *b_node) MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); =20 trace_ma_op(__func__, mas); - mas->depth =3D mas_mt_height(mas); =20 mast.l =3D &l_mas; mast.r =3D &r_mas; @@ -3327,9 +3329,9 @@ static void mas_split(struct ma_state *mas, struct ma= ple_big_node *b_node) mast.orig_r =3D &prev_r_mas; mast.bn =3D b_node; =20 - while (height++ <=3D mas->depth) { + while (height++ <=3D orig_height) { if (mt_slots[b_node->type] > b_node->b_end) { - mas_split_final_node(&mast, mas, height); + mas_split_final_node(&mast, mas); break; } =20 @@ -3344,11 +3346,15 @@ static void mas_split(struct ma_state *mas, struct = maple_big_node *b_node) * is a significant savings. */ /* Try to push left. */ - if (mas_push_data(mas, height, &mast, true)) + if (mas_push_data(mas, &mast, true)) { + height++; break; + } /* Try to push right. */ - if (mas_push_data(mas, height, &mast, false)) + if (mas_push_data(mas, &mast, false)) { + height++; break; + } =20 split =3D mab_calc_split(mas, b_node, &mid_split); mast_split_data(&mast, mas, split); @@ -3365,7 +3371,7 @@ static void mas_split(struct ma_state *mas, struct ma= ple_big_node *b_node) /* Set the original node as dead */ old =3D mas->node; mas->node =3D l_mas.node; - mas_wmb_replace(mas, old); + mas_wmb_replace(mas, old, height); mtree_range_walk(mas); return; } @@ -3424,8 +3430,7 @@ static inline void mas_root_expand(struct ma_state *m= as, void *entry) if (mas->last !=3D ULONG_MAX) pivots[++slot] =3D ULONG_MAX; =20 - mas->depth =3D 1; - mas_set_height(mas); + mt_set_height(mas->tree, 1); ma_set_meta(node, maple_leaf_64, 0, slot); /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); @@ -3669,8 +3674,7 @@ static inline void mas_new_root(struct ma_state *mas,= void *entry) WARN_ON_ONCE(mas->index || mas->last !=3D ULONG_MAX); =20 if (!entry) { - mas->depth =3D 0; - mas_set_height(mas); + mt_set_height(mas->tree, 0); rcu_assign_pointer(mas->tree->ma_root, entry); mas->status =3D ma_start; goto done; @@ -3684,8 +3688,7 @@ static inline void mas_new_root(struct ma_state *mas,= void *entry) mas->status =3D ma_active; rcu_assign_pointer(slots[0], entry); pivots[0] =3D mas->last; - mas->depth =3D 1; - mas_set_height(mas); + mt_set_height(mas->tree, 1); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); =20 done: @@ -3804,6 +3807,7 @@ static inline void mas_wr_node_store(struct ma_wr_sta= te *wr_mas, struct maple_node reuse, *newnode; unsigned char copy_size, node_pivots =3D mt_pivots[wr_mas->type]; bool in_rcu =3D mt_in_rcu(mas->tree); + unsigned char height =3D mas_mt_height(mas); =20 if (mas->last =3D=3D wr_mas->end_piv) offset_end++; /* don't copy this offset */ @@ -3860,7 +3864,7 @@ static inline void mas_wr_node_store(struct ma_wr_sta= te *wr_mas, struct maple_enode *old_enode =3D mas->node; =20 mas->node =3D mt_mk_node(newnode, wr_mas->type); - mas_replace_node(mas, old_enode); + mas_replace_node(mas, old_enode, height); } else { memcpy(wr_mas->node, newnode, sizeof(struct maple_node)); } diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/ma= ple.c index bc30050227fd..e0f8fabe8821 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36248,6 +36248,21 @@ static noinline void __init check_mtree_dup(struct= maple_tree *mt) =20 extern void test_kmem_cache_bulk(void); =20 +static inline void check_spanning_store_height(struct maple_tree *mt) +{ + int index =3D 0; + MA_STATE(mas, mt, 0, 0); + mas_lock(&mas); + while (mt_height(mt) !=3D 3) { + mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL); + mas_set(&mas, ++index); + } + mas_set_range(&mas, 90, 140); + mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL); + MT_BUG_ON(mt, mas_mt_height(&mas) !=3D 2); + mas_unlock(&mas); +} + /* callback function used for check_nomem_writer_race() */ static void writer2(void *maple_tree) { @@ -36414,6 +36429,10 @@ void farmer_tests(void) check_spanning_write(&tree); mtree_destroy(&tree); =20 + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_spanning_store_height(&tree); + mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_null_expand(&tree); mtree_destroy(&tree); --=20 2.43.0 From nobody Tue Dec 16 19:40:40 2025 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id ED48D28F93F for ; Thu, 10 Apr 2025 19:15:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.177.32 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312507; cv=none; b=gdE/x9eX2ZSrhrxZ+kTZH3B2xALun+xIjmcB82oENMhN1vnEizXoEz0tRTttN+n5q0a3orTaxv3Jkamvw8GnEJj+fpvN5eZx6e6nOTKB0nZWV1nGng4M3VR7t7k5H3LZ99IP5yREmuPQX5CdFOxB3QiC3RiiTKNHc26BorVKH9c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312507; c=relaxed/simple; bh=TKstUrLqXP5gAXXhXRa22rZF7ZrpYN0ErtNqmn8L6Pg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Myhkmuizf8rEdPVc+IaNMrBEqEbA26RU94g0nTrV64crwwfVQFUsjO+A0HPL1uwVs9xujKwQBEzoGegv4OpsIBt70uNoFHTasxGa3wK3otqFceLihA2KPJIuuuiD9IGYMdZ/vaqCnyqF1iLsvOrtZ44FrFmVGx+qtB7O28H2krA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com; spf=pass smtp.mailfrom=oracle.com; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b=CMQZDzdw; arc=none smtp.client-ip=205.220.177.32 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=oracle.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="CMQZDzdw" 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 53AJ7ApT023189; 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=HZV89 /87me5vO2rrtx5oiznojRMUfJzE0drJ0U7p2nE=; b=CMQZDzdwJQA4DFqAHaJJS fOzQ9tJtLbtaLSDr7E2chz+9sxm2dVbqSijnZU1cEV+rqkyHzjNyTdmrtlW/J+jN VRaqVo8GjByo14VxE6i7uzsftMBX9lrJXzt/Ete3X/h5lKe27pgePZpMfA461O2x 600eTGjTHMb4/oUeHe2+C2Y+Ie8JhzAO9w63FiRb7icdUYAc4NavJA6gVCgd7UXw LaknZuHLMZ466i7k5jNuKIKzT8NitZ+kEV7iZ1DVcT88ovrwVVWHI+R/gPfk7Lej EODaL/zD73aYHZKyhlbDZRlllt9X6dJYJeBwtmuwWBU6sOcoC1CqGwxMV1ff+zid g== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45xkuy00g0-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:55 +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 53AIwiO7023934; 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 45ttyk1gjp-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 53AJEn92040606; Thu, 10 Apr 2025 19:14:54 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-4; Thu, 10 Apr 2025 19:14:54 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, willy@infradead.org, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v5 3/6] maple_tree: use vacant nodes to reduce worst case allocations Date: Thu, 10 Apr 2025 19:14:43 +0000 Message-ID: <20250410191446.2474640-4-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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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: HKoDVbyOLI-CV0R6je0n84BL7VEbT_My X-Proofpoint-ORIG-GUID: HKoDVbyOLI-CV0R6je0n84BL7VEbT_My Content-Type: text/plain; charset="utf-8" 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. Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- include/linux/maple_tree.h | 2 + lib/maple_tree.c | 13 ++++-- tools/testing/radix-tree/maple.c | 79 ++++++++++++++++++++++++++++---- 3 files changed, 82 insertions(+), 12 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index cbbcd18d4186..657adb33e61e 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 */ }; =20 #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) @@ -498,6 +499,7 @@ struct ma_wr_state { .mas =3D ma_state, \ .content =3D NULL, \ .entry =3D wr_entry, \ + .vacant_height =3D 0 \ } =20 #define MA_TOPIARY(name, tree) \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 195b19505b39..3f794ef072f4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3537,6 +3537,9 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas) if (ma_is_leaf(wr_mas->type)) return true; =20 + if (mas->end < mt_slots[wr_mas->type] - 1) + wr_mas->vacant_height =3D mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } =20 @@ -4152,7 +4155,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 *entr= y) { struct ma_state *mas =3D wr_mas->mas; - int ret =3D mas_mt_height(mas) * 3 + 1; + unsigned char height =3D mas_mt_height(mas); + int ret =3D height * 3 + 1; + unsigned char delta =3D height - wr_mas->vacant_height; =20 switch (mas->store_type) { case wr_invalid: @@ -4170,13 +4175,13 @@ static inline int mas_prealloc_calc(struct ma_wr_st= ate *wr_mas, void *entry) ret =3D 0; break; case wr_spanning_store: - ret =3D mas_mt_height(mas) * 3 + 1; + WARN_ON_ONCE(ret !=3D height * 3 + 1); break; case wr_split_store: - ret =3D mas_mt_height(mas) * 2 + 1; + ret =3D delta * 2 + 1; break; case wr_rebalance: - ret =3D mas_mt_height(mas) * 2 - 1; + ret =3D height * 2 + 1; break; case wr_node_store: ret =3D mt_in_rcu(mas->tree) ? 1 : 0; diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/ma= ple.c index e0f8fabe8821..e37a3ab2e921 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -35475,15 +35475,65 @@ static void check_dfs_preorder(struct maple_tree = *mt) } /* End of depth first search tests */ =20 +/* get height of the lowest non-leaf node with free space */ +static unsigned char get_vacant_height(struct ma_wr_state *wr_mas, void *e= ntry) +{ + struct ma_state *mas =3D wr_mas->mas; + char vacant_height =3D 0; + enum maple_type type; + unsigned long *pivots; + unsigned long min =3D 0; + unsigned long max =3D ULONG_MAX; + unsigned char offset; + + /* start traversal */ + mas_reset(mas); + mas_start(mas); + if (!xa_is_node(mas_root(mas))) + return 0; + + type =3D mte_node_type(mas->node); + wr_mas->type =3D type; + while (!ma_is_leaf(type)) { + mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max); + offset =3D mas->offset; + mas->end =3D mas_data_end(mas); + pivots =3D ma_pivots(mte_to_node(mas->node), type); + + if (pivots) { + if (offset) + min =3D pivots[mas->offset - 1]; + if (offset < mas->end) + max =3D pivots[mas->offset]; + } + wr_mas->r_max =3D offset < mas->end ? pivots[offset] : mas->max; + + /* detect spanning write */ + if (mas_is_span_wr(wr_mas)) + break; + + if (mas->end < mt_slot_count(mas->node) - 1) + vacant_height =3D mas->depth + 1; + + mas_descend(mas); + type =3D 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 =3D 100; unsigned long allocated; unsigned char height; + unsigned char vacant_height; struct maple_node *mn; void *ptr =3D check_prealloc; MA_STATE(mas, mt, 10, 20); + MA_WR_STATE(wr_mas, &mas, ptr); =20 mt_set_non_kernel(1000); for (i =3D 0; i <=3D max; i++) @@ -35494,8 +35544,9 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); + vacant_height =3D get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated =3D=3D 0); - MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + MT_BUG_ON(mt, allocated !=3D 1 + (height - vacant_height) * 3); mas_destroy(&mas); allocated =3D mas_allocated(&mas); MT_BUG_ON(mt, allocated !=3D 0); @@ -35503,8 +35554,9 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); + vacant_height =3D get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated =3D=3D 0); - MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + MT_BUG_ON(mt, allocated !=3D 1 + (height - vacant_height) * 3); MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); mas_destroy(&mas); allocated =3D mas_allocated(&mas); @@ -35514,7 +35566,8 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); - MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + vacant_height =3D get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated !=3D 1 + (height - vacant_height) * 3); mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated - 1); mn->parent =3D ma_parent_ptr(mn); @@ -35527,7 +35580,8 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); - MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + vacant_height =3D get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated !=3D 1 + (height - vacant_height) * 3); mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated - 1); MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); @@ -35540,7 +35594,8 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); - MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + vacant_height =3D get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated !=3D 1 + (height - vacant_height) * 3); mn =3D mas_pop_node(&mas); MT_BUG_ON(mt, mas_allocated(&mas) !=3D allocated - 1); mas_push_node(&mas, mn); @@ -35553,7 +35608,8 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); - MT_BUG_ON(mt, allocated !=3D 1 + height * 3); + vacant_height =3D get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated !=3D 1 + (height - vacant_height) * 3); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); =20 @@ -35578,7 +35634,8 @@ static noinline void __init check_prealloc(struct m= aple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); - MT_BUG_ON(mt, allocated !=3D 1 + height * 2); + vacant_height =3D get_vacant_height(&wr_mas, ptr); + MT_BUG_ON(mt, allocated !=3D 1 + (height - vacant_height) * 2); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); mt_set_non_kernel(1); @@ -35595,8 +35652,14 @@ static noinline void __init check_prealloc(struct = maple_tree *mt) MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) !=3D 0); allocated =3D mas_allocated(&mas); height =3D mas_mt_height(&mas); + vacant_height =3D get_vacant_height(&wr_mas, ptr); MT_BUG_ON(mt, allocated =3D=3D 0); - MT_BUG_ON(mt, allocated !=3D 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 !=3D height * 3 + 1); mas_store_prealloc(&mas, ptr); MT_BUG_ON(mt, mas_allocated(&mas) !=3D 0); mas_set_range(&mas, 0, 200); --=20 2.43.0 From nobody Tue Dec 16 19:40:40 2025 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C9B4B1BF37 for ; Thu, 10 Apr 2025 19:15:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.177.32 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312506; cv=none; b=dCDILv0fgpn3p3+03Cl1XsPBmIwcS2u7Nt6IiJ6R9kiHSLujBO/o0C+qSPOgjkQNt5a4OkswJYQCoajYLYVdWiBnrraSRAHr1yRAYAihiPPWfcMWLbArndfGFsrKqFpuHT6wPQfALBEPyyUIviWj6N8i4nzDnS1oqAeAZKfFrCQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312506; c=relaxed/simple; bh=bN/wby9GJTyHNrfTR8MR87g9+BbHW99FSM7/16TluMM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=BcGJuP+eaC7xGYko20sNXR6CdgSuEMUPbYictypuP0e7Xdd5LMwBUUGYZ5E+EDLw3dND6D9QApy+KnyGwQHNh1f9I8RGhP9cU188l9xQVQ+mzPleuT7WfdRviepXimb2e59GlyrUhJfEolnaraUYP6RJx/uYd8fpjXXly1nZhF8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com; spf=pass smtp.mailfrom=oracle.com; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b=Ta1Y01ti; arc=none smtp.client-ip=205.220.177.32 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=oracle.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="Ta1Y01ti" 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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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 Content-Type: text/plain; charset="utf-8" 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 =3D mast->orig_l->max; =20 - if (mast_sufficient(mast)) - continue; + if (mast_sufficient(mast)) { + if (mast_overflow(mast)) + continue; + + if (mast->orig_l->node =3D=3D mast->orig_r->node) { + /* + * The data in b_node should be stored in one + * node and in the tree + */ + slot =3D mast->l->offset; + break; + } =20 - if (mast_overflow(mast)) continue; + } =20 /* May be a new root stored in mast->bn */ if (mas_is_root_limits(mast->orig_l)) --=20 2.43.0 From nobody Tue Dec 16 19:40:40 2025 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 19C6A28F940 for ; Thu, 10 Apr 2025 19:15:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.177.32 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312509; cv=none; b=ANcInDB6mGmV9BGSe9kIcUB1i91YCJTaWS7vtHjYtqXrBa7GjOv89I6p1Zhaw2BtKDkwn2M5Ni8vs9K49LrZDIDvl3fJcJrLf6bCQHsHmGTikJwDtqhQSd0AQ/JFwNlAen5qsPNPLIYiclXZQfkccNTJMYIxX79I33ZAFRmaN3M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312509; c=relaxed/simple; bh=FpbIUhCv7atBmm0vYG5NQifCGtOyvmCz06IGpnrJlfI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=FY8xtB7bNjZz/y49W8sXNGZiwLzpMUlW7P1L7aEWjpntcFKvKPjhTTFkyn1D0tdH756B8BBNvXuYS4yFdddAA9UWYMtOovbOf+krTcD7C3+EcsCeyC1P0NDe4fcPSa/ANLVOnKz6CkSTgCz24dq4n4MvkqS1Dpa0ahn3R+pl2aQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com; spf=pass smtp.mailfrom=oracle.com; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b=MThG02bR; arc=none smtp.client-ip=205.220.177.32 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=oracle.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="MThG02bR" 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 53AIHKGF013307; Thu, 10 Apr 2025 19:14:57 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=KLkUy BHaMZVC9+qD8yDzzxR1ZYrBXGTE6UAP8midVt8=; b=MThG02bRWYxKUM7S/DBmJ NbGp43ECs1/SMJs4crLRbNRCaCGpfro5ESYwoMlnCgZsA/PW6JfU+qnuWyKw2eSc 7MSWBd5KRCqnwhCxctrvWd1x3HLp54ATgMRb7925/XRsiENEFbruzki7IOYTlH+2 QIvCu7O/DfpDO4uwrZXYNKhi32RROqMGwF+yy5fbt0tqpp2Kf1RzT6xU/2H7V1UF 9ZQYc0Xb4lvaTk+olda6Rp3tWtbPLBWXVshrwLVnbpkSKrYUCfL/wEr6OV83VrWw yO17GiPBk+Za7GuUgdVMSRsPGDYaCwJgeg8xfyStJNABB1iH+LtsIX5iMUR+vDei A== Received: from iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta01.appoci.oracle.com [130.35.100.223]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 45xk4hr4qw-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 53AHeMNv023937; Thu, 10 Apr 2025 19:14:56 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyk1gk7-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:56 +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 53AJEn96040606; 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-6; 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 Subject: [PATCH v5 5/6] maple_tree: add sufficient height Date: Thu, 10 Apr 2025 19:14:45 +0000 Message-ID: <20250410191446.2474640-6-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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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: v74hJGjVc4d4q4On2K_pMwAFYoOSPv19 X-Proofpoint-ORIG-GUID: v74hJGjVc4d4q4On2K_pMwAFYoOSPv19 Content-Type: text/plain; charset="utf-8" In order to support rebalancing and spanning stores using less than the worst case number of nodes, we need to track more than just the vacant height. Using only vacant height to reduce the worst case maple node allocation count can lead to a shortcoming of nodes in the following scenarios. For rebalancing writes, when a leaf node becomes insufficient, it may be combined with a sibling into a single node. This means that the parent node which has entries for this children will lose one entry. If this parent node was just meeting the minimum entries, losing one entry will now cause this parent node to be insufficient. This leads to a cascading operation of rebalancing at different levels and can lead to more node allocations than simply using vacant height can return. For spanning writes, a similar situation occurs. At the location at which a spanning write is detected, the number of ancestor nodes may similarly need to rebalanced into a smaller number of nodes and the same cascading situation could occur. To use less than the full height of the tree for the number of allocations, we also need to track the height at which a non-leaf node cannot become insufficient. This means even if a rebalance occurs to a child of this node, it currently has enough entries that it can lose one without any further action. This field is stored in the maple write state as sufficient height. In mas_prealloc_calc() when figuring out how many nodes to allocate, we check if the vacant node is lower in the tree than a sufficient node (has a larger value). If it is, we cannot use the vacant height and must use the difference in the height and sufficient height as the basis for the number of nodes needed. An off by one bug was also discovered in mast_overflow() where it is using >=3D rather than >. This caused extra iterations of the mas_spanning_rebalance() loop and lead to unneeded allocations. A test is also added to check the number of allocations is correct. Signed-off-by: Sidhartha Kumar Reviewed-by: Liam R. Howlett --- include/linux/maple_tree.h | 4 +++- lib/maple_tree.c | 19 ++++++++++++++++--- tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 47 insertions(+), 4 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 657adb33e61e..9ef129038224 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; /* Height of lowest node with free space */ + unsigned char sufficient_height;/* Height of lowest node with min suffici= ency + 1 nodes */ }; =20 #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) @@ -499,7 +500,8 @@ struct ma_wr_state { .mas =3D ma_state, \ .content =3D NULL, \ .entry =3D wr_entry, \ - .vacant_height =3D 0 \ + .vacant_height =3D 0, \ + .sufficient_height =3D 0 \ } =20 #define MA_TOPIARY(name, tree) \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5610b3742a79..aa139668bcae 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2741,7 +2741,7 @@ static inline bool mast_sufficient(struct maple_subtr= ee_state *mast) */ static inline bool mast_overflow(struct maple_subtree_state *mast) { - if (mast->bn->b_end >=3D mt_slot_count(mast->orig_l->node)) + if (mast->bn->b_end > mt_slot_count(mast->orig_l->node)) return true; =20 return false; @@ -3550,6 +3550,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 =3D mas->depth + 1; =20 + 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 =3D 1; + } else if (mas->end > mt_min_slots[wr_mas->type] + 1) + wr_mas->sufficient_height =3D mas->depth + 1; + mas_wr_walk_traverse(wr_mas); } =20 @@ -4185,13 +4192,19 @@ static inline int mas_prealloc_calc(struct ma_wr_st= ate *wr_mas, void *entry) ret =3D 0; break; case wr_spanning_store: - WARN_ON_ONCE(ret !=3D height * 3 + 1); + if (wr_mas->sufficient_height < wr_mas->vacant_height) + ret =3D (height - wr_mas->sufficient_height) * 3 + 1; + else + ret =3D delta * 3 + 1; break; case wr_split_store: ret =3D delta * 2 + 1; break; case wr_rebalance: - ret =3D height * 2 + 1; + if (wr_mas->sufficient_height < wr_mas->vacant_height) + ret =3D (height - wr_mas->sufficient_height) * 2 + 1; + else + ret =3D delta * 2 + 1; break; case wr_node_store: ret =3D mt_in_rcu(mas->tree) ? 1 : 0; diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/ma= ple.c index e37a3ab2e921..2c0b38301253 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36326,6 +36326,30 @@ static inline void check_spanning_store_height(str= uct maple_tree *mt) mas_unlock(&mas); } =20 +/* + * 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 =3D 0; + MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); + + /* create a height 6 tree */ + while (mt_height(mt) < 6) { + mtree_store_range(mt, i, i + 10, xa_mk_value(i), GFP_KERNEL); + i +=3D 9; + } + + /* delete all entries one at a time, starting from the right */ + do { + mas_erase(&mas); + } while (mas_prev(&mas, 0) !=3D NULL); + + mtree_unlock(mt); +} + /* callback function used for check_nomem_writer_race() */ static void writer2(void *maple_tree) { @@ -36496,6 +36520,10 @@ void farmer_tests(void) check_spanning_store_height(&tree); mtree_destroy(&tree); =20 + 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); --=20 2.43.0 From nobody Tue Dec 16 19:40:40 2025 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4F71828FFCC for ; Thu, 10 Apr 2025 19:15:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=205.220.177.32 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312510; cv=none; b=tfZsUuwNQmtfrHgNlNi4MrRCqUmEEH1wVM4enFXw1JQRfSB+2zOjr7uOSriK45mRmC4fTTQBdt1003lx4AVzNn1JSsaO5iNW/3MiUAIfHzDtIVKFLx2b5sWJk4vW3yCnfWkprU7bpB/tP/JjrBurx4cA7sAoWQHFJfXisOiHH7Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1744312510; c=relaxed/simple; bh=jaBwtcIvdXOI214Lt+jj3N7iNSjZP2AHKebTyoAaGvU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Gj9D9AihxFAp2Lql7iesplBAq5MancjxvacUTfdQvBwwRHJQBld8zfuS/rUnpKDZTQDQSLx36Mqj/hvQhnFxbeINLoLlo7rfuBrcWe5ZR1P4TPdP/HEcWe/j/bv812VK+h3D1mV+se7/FAOIfk6o48ejHAMYnEc1SPlV3y2YDTU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com; spf=pass smtp.mailfrom=oracle.com; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b=fj9P3Wg7; arc=none smtp.client-ip=205.220.177.32 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=oracle.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=oracle.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=oracle.com header.i=@oracle.com header.b="fj9P3Wg7" Received: from pps.filterd (m0246632.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.18.1.2/8.18.1.2) with ESMTP id 53AJ71BN029309; Thu, 10 Apr 2025 19:14:57 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=zWlQ0 xIqmwybEu+J7v33mBZJCqNRUP8L6NFstG34c08=; b=fj9P3Wg7WQF9LKYDJwqO1 Um0VyKZvueVYbtKgCajE2cIuBVTzk+J57OFgSaVWeKjcmWmnicVCeWwLMo2dOpmZ R9xxiW4hlactsgtxbqyM7aTaWDaedAvBuOYZYRq+2xAfW5Dui6SwOcCGERTYUlsH +V28WGh69JztY/cSzzJvCoM0P4TUVvFNOq+ryjWH1W+dq6hQsH+j2b86F4ARWJZ7 eTb6VPUi/B8rGGH8TS0zqxR+HoBDIRKeP3eO3nMYsaD1MwDOw5WNNcUKQbYxKo6r mz0ivu4ERPoB6H7s9kqFHuyfE50GoFQHGVlmcvzkSV43rDlHTIDpgA4XXzxYUkWE 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 45xkuy00h9-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:57 +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 53AHe4Fc023813; Thu, 10 Apr 2025 19:14:56 GMT Received: from pps.reinject (localhost [127.0.0.1]) by iadpaimrmta01.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 45ttyk1gkc-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 10 Apr 2025 19:14:56 +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 53AJEn98040606; Thu, 10 Apr 2025 19:14:56 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-7; Thu, 10 Apr 2025 19:14:56 +0000 From: Sidhartha Kumar To: linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org Cc: linux-mm@kvack.org, akpm@linux-foundation.org, liam.howlett@oracle.com, willy@infradead.org, Sidhartha Kumar , "Liam R . Howlett" Subject: [PATCH v5 6/6] maple_tree: reorder mas->store_type case statements Date: Thu, 10 Apr 2025 19:14:46 +0000 Message-ID: <20250410191446.2474640-7-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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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: AuQSBcultmD_cCUSWfwdXLuB5k9yBpJM X-Proofpoint-ORIG-GUID: AuQSBcultmD_cCUSWfwdXLuB5k9yBpJM Content-Type: text/plain; charset="utf-8" Move the unlikely case that mas->store_type is invalid to be the last evaluated case and put liklier cases higher up. Suggested-by: Liam R. Howlett Reviewed-by: Liam R. Howlett Signed-off-by: Sidhartha Kumar --- lib/maple_tree.c | 51 ++++++++++++++++++++++++------------------------ 1 file changed, 25 insertions(+), 26 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index aa139668bcae..affe979bd14d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4083,15 +4083,6 @@ static inline void mas_wr_store_entry(struct ma_wr_s= tate *wr_mas) unsigned char new_end =3D mas_wr_new_end(wr_mas); =20 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) @@ -4113,6 +4104,14 @@ static inline void mas_wr_store_entry(struct ma_wr_s= tate *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); } =20 return; @@ -4177,19 +4176,10 @@ static inline int mas_prealloc_calc(struct ma_wr_st= ate *wr_mas, void *entry) unsigned char delta =3D height - wr_mas->vacant_height; =20 switch (mas->store_type) { - case wr_invalid: - WARN_ON_ONCE(1); - break; - case wr_new_root: - ret =3D 1; - break; - case wr_store_root: - if (likely((mas->last !=3D 0) || (mas->index !=3D 0))) - ret =3D 1; - else if (((unsigned long) (entry) & 3) =3D=3D 2) - ret =3D 1; - else - ret =3D 0; + case wr_exact_fit: + case wr_append: + case wr_slot_store: + ret =3D 0; break; case wr_spanning_store: if (wr_mas->sufficient_height < wr_mas->vacant_height) @@ -4209,10 +4199,19 @@ static inline int mas_prealloc_calc(struct ma_wr_st= ate *wr_mas, void *entry) case wr_node_store: ret =3D mt_in_rcu(mas->tree) ? 1 : 0; break; - case wr_append: - case wr_exact_fit: - case wr_slot_store: - ret =3D 0; + case wr_new_root: + ret =3D 1; + break; + case wr_store_root: + if (likely((mas->last !=3D 0) || (mas->index !=3D 0))) + ret =3D 1; + else if (((unsigned long) (entry) & 3) =3D=3D 2) + ret =3D 1; + else + ret =3D 0; + break; + case wr_invalid: + WARN_ON_ONCE(1); } =20 return ret; --=20 2.43.0