From nobody Sat Nov 23 02:20:17 2024 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 3DC53433C4 for ; Thu, 14 Nov 2024 17:05:38 +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=1731603941; cv=none; b=pwV3r20fQik3MhHpYeeN88qRxdz672NGEqsTCizNxWzmRpAmUU26Tbela/+c+dKVrcb82oedeeWnm+KQERrmhfXiXcl3YZW/J0RIhMEEjL5IgufO7HQbZKQAp/xufnLBGp8s09jerdY4NUBRMXIMmISQ0ClzCF89opvqgOdURsU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1731603941; c=relaxed/simple; bh=abI3WQbZEvzWAbPSPOuqh8UqU2IA51aJ50UHAArz0Hg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=naevxx5vd4lfrp61nXJ7qlcNUzSpX7k4TzAEYu7PtYEKFdqGTSZ4hQ75cjTOFCeA2Q75KDw1wivEtruIwuMx5B0lc4w9yXcbytzZcERUo2ttRXxF1mydXSHCA+imVMUMoKeFkx9xjHHPo7ZaKAH8qGAHydfJczm8ud8XPIlmjO0= 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=cLGVRprn; 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="cLGVRprn" 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> 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.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 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. 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 *entr= y) { + struct ma_state *mas =3D wr_mas->mas; int ret =3D mas_mt_height(mas) * 3 + 1; =20 switch (mas->store_type) { @@ -4258,16 +4259,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 /** @@ -5441,7 +5441,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 @@ -5538,7 +5538,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 Sat Nov 23 02:20:17 2024 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 56D1C191466 for ; Thu, 14 Nov 2024 17:05:47 +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=1731603949; cv=none; b=kyi0u4NwUqhukVyZ22eHbTpqbf/5YaXRNzm9Q2vSkphOZ5CferZy/hq0lfka2aSH9X0om6Ovk9SWCKmcnc+Gs2TgSimGntEGxVXXokvXGe2akoBa5AQq+Xy0/RlveTjXvBlipyvx8mf1dDSUn1+dS+KCYtOEQbuLiyCmJ6h67dc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1731603949; c=relaxed/simple; bh=aiSQGLZdsShs18zs/5u0wpRsw4lzli0lMRikfWavT78=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=mbx/USbBD2a7dr9i2eZzUXlqFRjeWRbatbtPReW5go96TuU2M4HXIOfOrNZeTXox0kGFycHOFcJSMipdNQDH40dZ7hebCcQ/WDlTZy25JlGOf0MYMT55xxsBdI+ZxiTTNGjXPqB0i4TlE3V4S4cRb4WJ/xBcuhkvVNbUMwGwmTc= 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=Z1GCbDs1; 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="Z1GCbDs1" 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> 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.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 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. 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); } =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) @@ -1375,7 +1375,6 @@ 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->status =3D ma_active; mas->node =3D mte_safe_root(root); mas->offset =3D 0; @@ -1727,7 +1726,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, mas->depth + 1); } else { =20 offset =3D 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 =3D mte_node_type(left); - l_mas.depth++; =20 /* Root already stored in l->node. */ if (mas_is_root_limits(mast->l)) goto new_root; =20 + l_mas.depth++; mast_ascend(mast); mast_combine_cp_left(mast); l_mas.offset =3D mast->bn->b_end; @@ -3141,7 +3140,7 @@ 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; + mas->depth =3D 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 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 @@ -3334,7 +3334,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; @@ -3342,7 +3341,7 @@ 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); break; @@ -3439,8 +3438,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)); @@ -3684,8 +3682,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; @@ -3699,8 +3696,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: --=20 2.43.0 From nobody Sat Nov 23 02:20:17 2024 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 58A40188714 for ; Thu, 14 Nov 2024 17:05:40 +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=1731603942; cv=none; b=gnNJjwfm7pl+otxhgsKhsdk94BYqmWYadkgKIhAzGtLak4PA7poaf1cDGMGEelrdBnIazWbxWfBHCLAFv4WvzNK9wMBCmvlqEZlsUN+UJPBw5i9xyz73pRUDmDbgr7Aaoye9h0MQJ92wkOlDmMZ1blG1IpjegcnYBGLu+SzUqHM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1731603942; c=relaxed/simple; bh=rQcWZRD3lVxY8BrXWw5zPiMYwjsCZV8VDbmmp4ZFVLE=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=XprPldSC3mLF0fBuCjqtUKQm0TaPXyXUjOeOYc/Jfxy9guIUQvIyQBOkOM6eJCdjUZ/Giums3+i7yDIEdte6Jh73qalHqlyYDalVRszMx0bIZmnRD7TtxQenMP1qdEXkvp4mJBvly8UIRgcTRNePKWcJl/hkOBDC4DeWntx5gLE= 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=G6OHosqv; 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="G6OHosqv" 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> 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.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 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 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 */ }; =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 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; =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 @@ -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 *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: @@ -4177,13 +4182,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; + ret =3D delta * 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 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 */ =20 +/* 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 =3D r_max; + unsigned long last =3D mas->last; + + /* Contained in this pivot, fast path */ + if (last < max) + return false; + + if (ma_is_leaf(type)) { + max =3D mas->max; + if (last < max) + return false; + } + + if (last =3D=3D 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 =3D=3D 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 =3D 0; + enum maple_type type; + unsigned long *pivots; + unsigned long min =3D 0; + unsigned long max =3D ULONG_MAX; + + /* start traversal */ + mas_reset(mas); + mas_start(mas); + if (!xa_is_node(mas_root(mas))) + return 0; + + type =3D mte_node_type(mas->node); + while (!ma_is_leaf(type)) { + mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max); + mas->end =3D mas_data_end(mas); + pivots =3D ma_pivots(mte_to_node(mas->node), type); + + if (pivots) { + if (mas->offset) + min =3D pivots[mas->offset - 1]; + if (mas->offset < mas->end) + max =3D 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 =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); @@ -35494,8 +35567,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(&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 +35577,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(&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 +35589,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(&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 +35603,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(&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 +35617,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(&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 +35631,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(&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 +35657,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(&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 +35675,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(&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_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 Sat Nov 23 02:20:17 2024 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 589E5188708 for ; Thu, 14 Nov 2024 17:05:39 +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=1731603942; cv=none; b=G2XAWa9376bEaQPXMaYGXQqhc+BkzxoJfHBIK2tCBCa+63JLS+CHaSi4OMUFH6Gzuzh8yAWbnRogquVJgU9ihpyQ50k9vWXhCrdMBFi+IlRgra5II+ihC8pk1uA4oumBD4PsV2ui/vrN5y4WyWSC9bwhlS/zs5nz697RYxWA0ec= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1731603942; c=relaxed/simple; bh=XcRT0zbjVfzNnZATSr6fZ9vc5Z1zY4bCUm7s0FzRid0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=RKFZS0E0WQsXMDp3QQGRhQcLdKJ4Bc3rqf80NGnsesm8Dkce3zrL8gIoNY0R/b4t3CCQFQRJZV1Yh9FOACSWZyErjX6jpfGxFbZiAPqeW8nnmn7SCdBoIQVEu5+3kJEyKe3iCJR0RVGxrL5p7fB13t61/LZvvbON+52pWQ62vrw= 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=I15HK8i7; 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="I15HK8i7" 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> 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.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 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 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 =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 Sat Nov 23 02:20:17 2024 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 0977F188A15 for ; Thu, 14 Nov 2024 17:05:40 +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=1731603942; cv=none; b=RXjV+h5QZpDlQVvewrSTWFyZri8F2nVa18QorynOQooAUBfZPMe1PvZAPssg0WEm6zfZoBHP0PH260NaLA9cxuniGB8Ds1+f3jC6MsotJIdtoCI7kmdT1Z4g0LoXKC34FxXuCAy/F37kQcTsswr4aKjuGvV9hwc+915tUANLOmA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1731603942; c=relaxed/simple; bh=7nlDCyySdr8N5wOBTpeEwUUUmZ7mni5cFGtHr8tlGfI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=lNuMXBAzIa+bMKpz1PA6bjMZ1issbOGOX4yjG4NNd2CKWCDTQwUbMCyBtglnU4wJGQqGQc9PKmfNAyC4dBOffReB7OEogulYBIETpREEGF5fqWLYYalcAMZHUBf7oMbzvLAzn7NCCnn8oxTjdHRrwoTLr+hvdRONFQcAPoK/b2c= 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=e5sEXTDf; 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="e5sEXTDf" 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> 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.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 Content-Type: text/plain; charset="utf-8" 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 sufficie= ncy + 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 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 =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; + + 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 @@ -4198,7 +4206,11 @@ static inline int mas_prealloc_calc(struct ma_wr_sta= te *wr_mas, void *entry) 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; + break; + } + 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 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) =20 extern void test_kmem_cache_bulk(void); =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 4 tree */ + while (mt_height(mt) < 4) { + 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) { @@ -36495,6 +36519,10 @@ void farmer_tests(void) check_spanning_write(&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