From 33b4eaea7f00a82a0ee986dd0e5cb11f8c05b102 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Fri, 29 Nov 2024 23:54:58 -0500
Subject: [PATCH] maple_tree: Combine mas_parent_gap() into mas_update_gap()

mas_parent_gap() is used in one location and a lot of what is needed already
exists in the calling function.  Inline the function and dropping the
duplication simplifies the code and reduces the instruction count.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c      | 113 +++++++++++++++---------------------------
 lib/test_maple_tree.c |   2 +-
 2 files changed, 40 insertions(+), 75 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index bc16cf34f378..f687ecb341b5 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1613,81 +1613,18 @@ static inline unsigned long mas_max_gap(struct ma_state *mas)
 	return gaps[offset];
 }
 
-/*
- * mas_parent_gap() - Set the parent gap and any gaps above, as needed
- * @mas: The maple state
- * @offset: The gap offset in the parent to set
- * @new: The new gap value.
- *
- * Set the parent gap then continue to set the gap upwards, using the metadata
- * of the parent to see if it is necessary to check the node above.
- */
-static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
-		unsigned long new)
-{
-	unsigned long meta_gap = 0;
-	struct maple_node *pnode;
-	struct maple_enode *penode;
-	unsigned long *pgaps;
-	unsigned char meta_offset;
-	enum maple_type pmt;
-
-	pnode = mte_parent(mas->node);
-	pmt = mas_parent_type(mas, mas->node);
-	penode = mt_mk_node(pnode, pmt);
-	pgaps = ma_gaps(pnode, pmt);
-
-ascend:
-	MAS_BUG_ON(mas, pmt != maple_arange_64);
-	meta_offset = ma_meta_gap(pnode);
-	meta_gap = pgaps[meta_offset];
-
-	pgaps[offset] = new;
-
-	if (meta_gap == new)
-		return;
-
-	if (offset != meta_offset) {
-		if (meta_gap > new)
-			return;
-
-		ma_set_meta_gap(pnode, pmt, offset);
-	} else if (new < meta_gap) {
-		unsigned char i;
-
-		/* Get the new maximum gap in the node */
-		i = meta_offset = ma_meta_end(pnode, pmt);
-		new = pgaps[i];
-		while (i--) {
-			if (pgaps[i] > new) {
-				new = pgaps[i];
-				meta_offset = i;
-			}
-		}
-		ma_set_meta_gap(pnode, pmt, meta_offset);
-	}
-
-	if (ma_is_root(pnode))
-		return;
-
-	/* Go to the parent node. */
-	pnode = mte_parent(penode);
-	pmt = mas_parent_type(mas, penode);
-	pgaps = ma_gaps(pnode, pmt);
-	offset = mte_parent_slot(penode);
-	penode = mt_mk_node(pnode, pmt);
-	goto ascend;
-}
-
 /*
  * mas_update_gap() - Update a nodes gaps and propagate up if necessary.
  * @mas: the maple state.
  */
 static inline void mas_update_gap(struct ma_state *mas)
 {
-	unsigned char pslot;
-	unsigned long p_gap;
-	unsigned long max_gap;
+	unsigned char meta_offset, offset;
+	unsigned long *pgaps;
+	unsigned long max_gap, meta_gap;
+	struct maple_node *pnode;
+	struct maple_enode *penode;
+	enum maple_type pmt;
 
 	if (!mt_is_alloc(mas->tree))
 		return;
@@ -1697,13 +1634,41 @@ static inline void mas_update_gap(struct ma_state *mas)
 
 	//printk("Updating gap for %p\n", mas->node);
 	max_gap = mas_max_gap(mas);
+	penode = mas->node;
+	do {
+		/* Ascend */
+		pnode = mte_parent(penode);
+		pmt = mas_parent_type(mas, penode);
+		offset = mte_parent_slot(penode);
+		pgaps = ma_gaps(pnode, pmt);
+
+		meta_offset = ma_meta_gap(pnode);
+		meta_gap = pgaps[meta_offset];
+		pgaps[offset] = max_gap;
+		if (meta_gap == max_gap)
+			return;
 
-	pslot = mte_parent_slot(mas->node);
-	p_gap = ma_gaps(mte_parent(mas->node),
-			mas_parent_type(mas, mas->node))[pslot];
+		if (offset != meta_offset) {
+			if (meta_gap > max_gap)
+				return;
 
-	if (p_gap != max_gap)
-		mas_parent_gap(mas, pslot, max_gap);
+			ma_set_meta_gap(pnode, pmt, offset);
+		} else {
+			unsigned char i;
+
+			/* Get the new maximum gap in the node */
+			i = meta_offset = ma_meta_end(pnode, pmt);
+			max_gap = pgaps[i];
+			while (i--) {
+				if (pgaps[i] > max_gap) {
+					max_gap = pgaps[i];
+					meta_offset = i;
+				}
+			}
+			ma_set_meta_gap(pnode, pmt, meta_offset);
+		}
+		penode = mt_mk_node(pnode, pmt);
+	} while (!ma_is_root(pnode));
 }
 
 /*
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index bf2f9982ae42..020feceb453b 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -40,7 +40,7 @@ atomic_t maple_tree_tests_passed;
 #endif
 
 /* #define BENCH_SLOT_STORE */
-#define BENCH_NODE_STORE
+/* #define BENCH_NODE_STORE */
 /* #define BENCH_AWALK */
 /* #define BENCH_WALK */
 /* #define BENCH_LOAD */
-- 
2.49.0