Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.38 as permitted sender) client-ip=23.128.96.38;
From:   Sidhartha Kumar <sidhartha.kumar@oracle.com>
To:     linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        maple-tree@lists.infradead.org
Cc:     akpm@linux-foundation.org, willy@infradead.org,
        liam.howlett@oracle.com, zhangpeng.00@bytedance.com,
        Sidhartha Kumar <sidhartha.kumar@oracle.com>
Subject: [PATCH 1/3] maple_tree: introduce mas_prealloc_calc()
Date:   Mon,  9 Oct 2023 13:16:37 -0700
Message-ID: <20231009201639.920512-2-sidhartha.kumar@oracle.com>
In-Reply-To: <20231009201639.920512-1-sidhartha.kumar@oracle.com>
References: <20231009201639.920512-1-sidhartha.kumar@oracle.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?PHrn/oGpVDfRLf6LgwB2mZSwCwbyH6VIcPYMw72IjnqunncrNx1OgCH8bzMM?=
 =?us-ascii?Q?S+PIemHjGU/cKVnHqbRCy5MsvTatP46j4Wz6y8P4m6CGE2KaNOUt2v9RMgMB?=
 =?us-ascii?Q?lYUUs/e1hOszScnEQkmUyz+ZwW/n0dU5pkZlPJQgV8sD1DWaSr/zRB7EG/CS?=
 =?us-ascii?Q?GWsI7qEgxNZYg/Tn/sXujofZQiXfnvIZ54gzQph9OeTQ1ruD1D2ttKxG8ext?=
 =?us-ascii?Q?dyeGHn6CN49f0xP83WRwiU1x+RzwgApjeZN0bxfoWNbJ/vwblGckEeuZqhJM?=
 =?us-ascii?Q?/B6yy9NbO83LfuxqVBLgvkZGZrGzOmLQOn8k636XclRL4gvEFa085wzagXNm?=
 =?us-ascii?Q?aqqV+J+BLQVYBQhT1Xzp6dYAIu8F5Iy1nqbvpe8g3WQrKTSaw5vNqlftsjev?=
 =?us-ascii?Q?awiAJiG7glcLn0RhAwCnKnrThqv7Kqkxs9NF8okf6HDJmB5xDgP+6qNk6jv/?=
 =?us-ascii?Q?RQTJaeva7d14YmUDhK1jBR/am36j3smn8Cw1QBH/3JhyHmagVAU8bNlNUKTo?=
 =?us-ascii?Q?F31RoXQCSbAf9WRk7cLQslJ2N1NoneJJIZSJUZE4LZWs/vZFSfdsfaYenOSE?=
 =?us-ascii?Q?pbyQj3M/wGZQvlZ+Wu7MmDn1vIsEbNoOT4BU5eZagqone84fmceAqHsRtXGy?=
 =?us-ascii?Q?LP6jxvQHVacy4VbhfDjIeAay7Erckbbw0l17EYOqI4yMdG+iePozX3N/gv0x?=
 =?us-ascii?Q?lYzuFmusrYWiWgGVpcbe4Goeg7/nFvXfIrp1AcGvaWvaQRWedY4kFcxGvQHl?=
 =?us-ascii?Q?7ib6qNJebwValaYCV+gvlj086+rYuxb8CXZIar39TGII3iHnV10OZD3aIZ9h?=
 =?us-ascii?Q?h3+FG7h0NOAEGk7lww2hanRTMLEQBDuTtBYK4gBV/korjtjYA5xmzUXSNwM1?=
 =?us-ascii?Q?TSZuZ5+gzCpAtAa5Qsaw6sOdxlIwIBGoXtW5PNaZZHiosVgH8eeAIN/zu+Kw?=
 =?us-ascii?Q?TcNWpaIHz4gWn9YT0aRZ692sgBRaTfMC9hv0gO5H7rE02a8p0ehy3MHGcd1U?=
 =?us-ascii?Q?uGCVedSM4kCHBmyZnV5SC5k+tKtQDNPu73ACAgSkG9sZQgsHqnTarQBZ39VL?=
 =?us-ascii?Q?WQWcnxR+OG5lNnpG6bJKGwCHibEj56xDSayHP7RtAPXdTdIr+8ZYG/wqDEYK?=
 =?us-ascii?Q?h/U+0aszR6ne9wwJfD4ZJ3scP+yU9fpxH0qfZxIwqsa63qH/2Ah9uUT4rsrX?=
 =?us-ascii?Q?0Z6P48plFuRfN66opm1FCtD5NmaKwB+7gsglPx96T+EdozTpT7yI7seNmQ2P?=
 =?us-ascii?Q?9JzBqbsFXa/sg4HfrTpVQCOud7g7PAD7mXj2aDih3qH+IqrycJ0ZyhgtqGpC?=
 =?us-ascii?Q?ssuQXZE3mAbt/F/V87vuZbUtEXDshtGhAv/5/HbIIaRM7+aKf3GYSCUbvsYZ?=
 =?us-ascii?Q?OJx7vH5n7vIw3E+c+HjCh8JX9IGTWi3Ne3+kxeTbkHILaCCad6wCbcRWcJRM?=
 =?us-ascii?Q?aEdY46qpoQfDc7u3VOGE0ysdoS0udVDhwyz72A7bALnlBkb3Rj/dV7Nq+w6u?=
 =?us-ascii?Q?qiLTr7ZvGng5XI0Fk3kYKp6Hychs9exNhL3t0BLdw2fXLwidWjLkMuP0JdAK?=
 =?us-ascii?Q?Fw1wKqg+eSLUHA+Yvr4tdHnYyD1sXD1ATYw8LRBjV/zj6mGDTaphDDklWotA?=
 =?us-ascii?Q?NI/qTKpkCEOtJtJiFoxbrOk=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?DptAObLX1cHO2srMUWhRSJxUZUKueChK4kEuX8EukmhD1A5147A+O26nxP1a?=
 =?us-ascii?Q?kOMirhbxXHsmC80+XBpHyAnPcxLub8/bEIBLoYw1gxJUKEQJ+i9/LK1Elq/2?=
 =?us-ascii?Q?bC9m5CpLsMcqjIEApJwAYzv54XwsmJDIEYXNzYg/bt0bmPX51D1mY7WA6oX7?=
 =?us-ascii?Q?FFesvAApMA4e43QMnPT/8zjovvHYcKgt8g8sWOLNpzyY1uHxfv+M8Bzzx9pw?=
 =?us-ascii?Q?wj9Os0sZRPpDfqZC5CGmLIWQM3EGUQZDpKja11KK7FbwoR0mUU/p5K0jkhj6?=
 =?us-ascii?Q?NVUETnGgTqJ+RpylcIgABjPeYFpRVMw99m15NYr758luIaXpHVuLnLSbkdxk?=
 =?us-ascii?Q?lF1GIrrNiiZx+8SWqPLdCmDrW9TmAa3JwlbtP9GcBrfbkBB3ZOndDNYqtvne?=
 =?us-ascii?Q?szWxIRtpkqNzGTIVB9MZsktweY904X4e1KHn1Dv7nGKTdGQ07/4RU8oDyySQ?=
 =?us-ascii?Q?9YbgYANW0KALJEws0evnuXfgzlvSUP7KSdNcIdRKH8W7M2zZYZaL+NK8VK2t?=
 =?us-ascii?Q?2+fBs7Qct2MZX8bAI4GiSK3IbGmuDajIKY8An4twFJ5oUuKGMiCtpBXmuHga?=
 =?us-ascii?Q?hE4VkyKyPXkIOCaahNU5Q3vYGE2qiu1ld45YQGhJbCVutmN43wm4fSNGyuXV?=
 =?us-ascii?Q?NKq4TuvMYhZBCFdJcY5bgopQ+bS84IJlyxr9lVrtyRj+a7ShkKbJIrTbL/xp?=
 =?us-ascii?Q?KugSVehek2krg8mIe4FfjuKBi9M8ElT+WY153xVy6fx5hn9EyOmGv+hkRpTP?=
 =?us-ascii?Q?OzBTwn/wBuaK3nAoQ8RRHkp+9myC6FOhuF8K+8pzTCyYu32R7c/BS9t0w2+r?=
 =?us-ascii?Q?95wkMKYTQE0vzExmtc9NksY12/Ich7cxVLSKfyNYRbZTqbKlX/wHJ7LNGFFk?=
 =?us-ascii?Q?ht2y/XBZMxF2pERCqoHMFmhjHgbiGeXMNwWbIoj99Kk0RQQV259Ulbb21mTc?=
 =?us-ascii?Q?CVO3O/jzL45Ro2yoVAMqaA=3D=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 7a0dccca-548c-4159-5d9d-08dbc904aba0
X-MS-Exchange-CrossTenant-AuthSource: CH0PR10MB5113.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 09 Oct 2023 20:16:50.1200
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: yvqlpW2FLWSjrN85OXYZe7RgOdQJqSrHXuuxxG10Ii4z0SpjIREhAtiJ406U6Rh4hvrkTcvA/47XsB5kQ5Hl2HxfMljtaiobIVjxR31q5DY=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA3PR10MB6998
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.267,Aquarius:18.0.980,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2023-10-09_18,2023-10-09_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 malwarescore=0 spamscore=0
 mlxlogscore=999 adultscore=0 phishscore=0 bulkscore=0 suspectscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2309180000
 definitions=main-2310090163
X-Proofpoint-GUID: tBPHSQ_DDvz0WgzcexM5jbV7pd205Ghk
X-Proofpoint-ORIG-GUID: tBPHSQ_DDvz0WgzcexM5jbV7pd205Ghk
X-Spam-Status: No, score=2.7 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	RCVD_IN_SBL_CSS,SPF_HELO_NONE,SPF_PASS autolearn=no autolearn_force=no
	version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on fry.vger.email
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (fry.vger.email [0.0.0.0]); Mon, 09 Oct 2023 13:17:47 -0700 (PDT)
X-Spam-Level: **

Abstract the calculation used to determine the number of nodes needed for
a store operation into a separate function: mas_prealloc_calc().

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 85 ++++++++++++++++++++++++++++--------------------
 1 file changed, 50 insertions(+), 35 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0e00a84e8e8f..e239197a57fc 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5418,6 +5418,54 @@ void *mas_store(struct ma_state *mas, void *entry)
 }
 EXPORT_SYMBOL_GPL(mas_store);
 
+/**
+ * mas_prealloc_calc() - Calculate number of nodes needed for a
+ * store operation.
+ * @wr_mas: The maple write state
+ *
+ * Return: Number of nodes required for preallocation.
+ */
+int mas_prealloc_calc(struct ma_wr_state *wr_mas)
+{
+	struct ma_state *mas = wr_mas->mas;
+	unsigned char node_size;
+
+	if (unlikely(!mas->index && mas->last == ULONG_MAX))
+		return 1;
+
+	/* Root expand */
+	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
+		return 1;
+
+	if (unlikely(!mas_wr_walk(wr_mas))) {
+		/* Spanning store, use worst case for now */
+		return 1 + mas_mt_height(mas) * 3;
+	}
+
+	/* At this point, we are at the leaf node that needs to be altered. */
+	/* Exact fit, no nodes needed. */
+	if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last)
+		return 0;
+
+	mas_wr_end_piv(wr_mas);
+	node_size = mas_wr_new_end(wr_mas);
+	if (node_size >= mt_slots[wr_mas->type]) {
+		/* Split, worst case for now. */
+		return 1 + mas_mt_height(mas) * 2;
+	}
+
+	/* New root needs a singe node */
+	if (unlikely(mte_is_root(mas->node)))
+		return 1;
+
+	/* Potential spanning rebalance collapsing a node, use worst-case */
+	if (node_size  - 1 <= mt_min_slots[wr_mas->type])
+		return mas_mt_height(mas) * 2 - 1;
+
+	/* node store, slot store needs one node */
+	return 1;
+}
+
 /**
  * mas_store_gfp() - Store a value into the tree.
  * @mas: The maple state
@@ -5474,49 +5522,16 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 {
 	MA_WR_STATE(wr_mas, mas, entry);
-	unsigned char node_size;
 	int request = 1;
 	int ret;
 
-
-	if (unlikely(!mas->index && mas->last == ULONG_MAX))
-		goto ask_now;
-
 	mas_wr_store_setup(&wr_mas);
 	wr_mas.content = mas_start(mas);
-	/* Root expand */
-	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
-		goto ask_now;
 
-	if (unlikely(!mas_wr_walk(&wr_mas))) {
-		/* Spanning store, use worst case for now */
-		request = 1 + mas_mt_height(mas) * 3;
-		goto ask_now;
-	}
-
-	/* At this point, we are at the leaf node that needs to be altered. */
-	/* Exact fit, no nodes needed. */
-	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
+	request = mas_prealloc_calc(&wr_mas);
+	if (!request)
 		return 0;
 
-	mas_wr_end_piv(&wr_mas);
-	node_size = mas_wr_new_end(&wr_mas);
-	if (node_size >= mt_slots[wr_mas.type]) {
-		/* Split, worst case for now. */
-		request = 1 + mas_mt_height(mas) * 2;
-		goto ask_now;
-	}
-
-	/* New root needs a singe node */
-	if (unlikely(mte_is_root(mas->node)))
-		goto ask_now;
-
-	/* Potential spanning rebalance collapsing a node, use worst-case */
-	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
-		request = mas_mt_height(mas) * 2 - 1;
-
-	/* node store, slot store needs one node */
-ask_now:
 	mas_node_count_gfp(mas, request, gfp);
 	mas->mas_flags |= MA_STATE_PREALLOC;
 	if (likely(!mas_is_err(mas)))
-- 
2.41.0