[PATCH v3 0/6] Track node vacancy to reduce worst case allocation counts

[PATCH v3 0/6] Track node vacancy to reduce worst case allocation counts

[Sidhartha Kumar]

v2[2] -> v3:
  - add r-b to patches 1,4, and 6
  
  - update function parameter comments in patch 2 

  - remove line that sets mas->depth in patch 2

  - remove redundant code for checking for a spanning write in patch 3

  - rewrite commit message of patch 5 for additonal context and clarity


v1[1] -> v2:
  - fix comment for vacant_height which refers to depth per Wei 

  - add a patch to reorder switch case statements in mas_prealloc_calc and
    mas_wr_store_entry

  - use sufficient height in spanning stores

  - modify patch 2 to use a counter to track ascending the tree rather
    than overloading mas->depth to have this function.

================ overview ========================
Currently, the maple tree preallocates the worst case number of nodes for
given store type by taking into account the whole height of the tree. This
comes from a worst case scenario of every node in the tree being full and
having to propagate node allocation upwards until we reach the root of the
tree. This can be optimized if there are vacancies in nodes that are at a
lower depth than the root node. This series implements tracking the level
at which there is a vacant node so we only need to allocate until this
level is reached, rather than always using the full height of the tree.
The ma_wr_state struct is modified to add a field which keeps track of the
vacant height and is updated during walks of the tree. This value is then
read in mas_prealloc_calc() when we decide how many nodes to allocate.

For rebalancing and spanning stores, we also need to track the lowest
height at which a node has 1 more entry than the minimum sufficient number
of entries. This is because rebalancing can cause a parent node to become
insufficient which results in further node allocations. In this case, we
need to use the sufficient height as the worst case rather than the vacant
height.

patch 1-2: preparatory patches
patch 3: implement vacant height tracking + update the tests
patch 4: support vacant height tracking for rebalancing writes
patch 5: implement sufficient height tracking
patch 6: reorder switch case statements

================ results =========================
Bpftrace was used to profile the allocation path for requesting new maple
nodes while running stress-ng mmap 120s. The histograms below represent
requests to kmem_cache_alloc_bulk() and show the count argument. This
represnts how many maple nodes the caller is requesting in
kmem_cache_alloc_bulk()

command: stress-ng --mmap 4 --timeout 120

mm-unstable 

@bulk_alloc_req:
[3, 4)                 4 |                                                    |
[4, 5)             54170 |@                                                   |
[5, 6)                 0 |                                                    |
[6, 7)            893057 |@@@@@@@@@@@@@@@@@@@@                                |
[7, 8)                 4 |                                                    |
[8, 9)           2230287 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[9, 10)            55811 |@                                                   |
[10, 11)           77834 |@                                                   |
[11, 12)               0 |                                                    |
[12, 13)         1368684 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@                     |
[13, 14)               0 |                                                    |
[14, 15)               0 |                                                    |
[15, 16)          367197 |@@@@@@@@                                            |


@maple_node_total: 46,630,160
@total_vmas: 46184591

mm-unstable + this series

@bulk_alloc_req:
[2, 3)               198 |                                                    |
[3, 4)                 4 |                                                    |
[4, 5)                43 |                                                    |
[5, 6)                 0 |                                                    |
[6, 7)           1069503 |@@@@@@@@@@@@@@@@@@@@@                               |
[7, 8)                 4 |                                                    |
[8, 9)           2597268 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[9, 10)           472191 |@@@@@@@@@                                           |
[10, 11)          191904 |@@@                                                 |
[11, 12)               0 |                                                    |
[12, 13)          247316 |@@@@                                                |
[13, 14)               0 |                                                    |
[14, 15)               0 |                                                    |
[15, 16)           98769 |@                                                   |


@maple_node_total: 37,813,856
@total_vmas: 43493287

This represents a ~19% reduction in the number of bulk maple nodes allocated.

For more reproducible results, a historgram of the return value of
mas_prealloc_calc() is displayed while running the maple_tree_tests
whcih have a deterministic store pattern

mas_prealloc_calc() return value mm-unstable
1   :                                                    (12068)
3   :                                                    (11836)
5   : *****                                              (271192)
7   : ************************************************** (2329329)
9   : ***********                                        (534186)
10  :                                                    (435)
11  : ***************                                    (704306)
13  : ********                                           (409781)

mas_prealloc_calc() return value mm-unstable + this series
1   :                                                    (12070)
3   : ************************************************** (3548777)
5   : ********                                           (633458)
7   :                                                    (65081)
9   :                                                    (11224)
10  :                                                    (341)
11  :                                                    (2973)
13  :                                                    (68)

do_mmap latency was also measured for regressions:
command: stress-ng --mmap 4 --timeout 120

mm-unstable:
avg = 7162 nsecs, total: 16101821292 nsecs, count: 2248034

mm-unstable + this series:
avg = 6689 nsecs, total: 15135391764 nsecs, count: 2262726


[1]: https://lore.kernel.org/lkml/20241114170524.64391-1-sidhartha.kumar@oracle.com/T/
[2]: https://lore.kernel.org/lkml/20250221163610.578409-1-sidhartha.kumar@oracle.com/

Sidhartha Kumar (6):
  maple_tree: convert mas_prealloc_calc() to take in a maple write state
  maple_tree: use height and depth consistently
  maple_tree: use vacant nodes to reduce worst case allocations
  maple_tree: break on convergence in mas_spanning_rebalance()
  maple_tree: add sufficient height
  maple_tree: reorder mas->store_type case statements

 include/linux/maple_tree.h       |   4 +
 lib/maple_tree.c                 | 193 ++++++++++++++++++-------------
 tools/testing/radix-tree/maple.c | 107 +++++++++++++++--
 3 files changed, 218 insertions(+), 86 deletions(-)

-- 
2.43.0

[PATCH v3 1/6] maple_tree: convert mas_prealloc_calc() to take in a maple write state

[Sidhartha Kumar]

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 <Liam.Howlett@Oracle.com>
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 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 42c65974a56c..0410e13a099e 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4144,13 +4144,14 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
 /**
  * mas_prealloc_calc() - Calculate number of nodes needed for a
  * given store oepration
- * @mas: The maple state
+ * @wr_mas: The maple write state
  * @entry: The entry to store into the tree
  *
  * Return: Number of nodes required for preallocation.
  */
-static inline int mas_prealloc_calc(struct ma_state *mas, void *entry)
+static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
 {
+	struct ma_state *mas = wr_mas->mas;
 	int ret = mas_mt_height(mas) * 3 + 1;
 
 	switch (mas->store_type) {
@@ -4247,16 +4248,15 @@ static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas)
  */
 static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry)
 {
-	struct ma_state *mas = wr_mas->mas;
 	int request;
 
 	mas_wr_prealloc_setup(wr_mas);
-	mas->store_type = mas_wr_store_type(wr_mas);
-	request = mas_prealloc_calc(mas, entry);
+	wr_mas->mas->store_type = mas_wr_store_type(wr_mas);
+	request = mas_prealloc_calc(wr_mas, entry);
 	if (!request)
 		return;
 
-	mas_node_count(mas, request);
+	mas_node_count(wr_mas->mas, request);
 }
 
 /**
@@ -5401,7 +5401,7 @@ void *mas_store(struct ma_state *mas, void *entry)
 		return wr_mas.content;
 	}
 
-	request = mas_prealloc_calc(mas, entry);
+	request = mas_prealloc_calc(&wr_mas, entry);
 	if (!request)
 		goto store;
 
@@ -5498,7 +5498,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 
 	mas_wr_prealloc_setup(&wr_mas);
 	mas->store_type = mas_wr_store_type(&wr_mas);
-	request = mas_prealloc_calc(mas, entry);
+	request = mas_prealloc_calc(&wr_mas, entry);
 	if (!request)
 		return ret;
 
-- 
2.43.0

[PATCH v3 2/6] maple_tree: use height and depth consistently

[Sidhartha Kumar]

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 <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 85 ++++++++++++++++++++++++++----------------------
 1 file changed, 46 insertions(+), 39 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0410e13a099e..a37837d6f3eb 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -211,14 +211,14 @@ static void ma_free_rcu(struct maple_node *node)
 	call_rcu(&node->rcu, mt_free_rcu);
 }
 
-static void mas_set_height(struct ma_state *mas)
+static void mt_set_height(struct maple_tree *mt, unsigned char height)
 {
-	unsigned int new_flags = mas->tree->ma_flags;
+	unsigned int new_flags = mt->ma_flags;
 
 	new_flags &= ~MT_FLAGS_HEIGHT_MASK;
-	MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX);
-	new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET;
-	mas->tree->ma_flags = new_flags;
+	MT_BUG_ON(mt, height > MAPLE_HEIGHT_MAX);
+	new_flags |= height << MT_FLAGS_HEIGHT_OFFSET;
+	mt->ma_flags = new_flags;
 }
 
 static unsigned int mas_mt_height(struct ma_state *mas)
@@ -1375,7 +1375,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas)
 		root = mas_root(mas);
 		/* Tree with nodes */
 		if (likely(xa_is_node(root))) {
-			mas->depth = 1;
+			mas->depth = 0;
 			mas->status = ma_active;
 			mas->node = mte_safe_root(root);
 			mas->offset = 0;
@@ -1716,9 +1716,10 @@ static inline void mas_adopt_children(struct ma_state *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;
@@ -1727,7 +1728,7 @@ static inline void mas_put_in_tree(struct ma_state *mas,
 	if (mte_is_root(mas->node)) {
 		mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas));
 		rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
-		mas_set_height(mas);
+		mt_set_height(mas->tree, new_height);
 	} else {
 
 		offset = mte_parent_slot(mas->node);
@@ -1745,12 +1746,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);
 }
 
@@ -2540,10 +2542,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);
@@ -2551,7 +2554,7 @@ static inline void mas_topiary_replace(struct ma_state *mas,
 	int i, n;
 
 	/* 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);
 
 	/* Update the parent pointers in the tree */
 	tmp[0] = *mas;
@@ -2635,14 +2638,15 @@ static inline void mas_topiary_replace(struct ma_state *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);
 
 	if (mte_is_leaf(mas->node))
 		return;
@@ -2828,6 +2832,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
 {
 	unsigned char split, mid_split;
 	unsigned char slot = 0;
+	unsigned char new_height = 0; /* used if node is a new root */
 	struct maple_enode *left = NULL, *middle = NULL, *right = NULL;
 	struct maple_enode *old_enode;
 
@@ -2877,7 +2882,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
 		 */
 		memset(mast->bn, 0, sizeof(struct maple_big_node));
 		mast->bn->type = mte_node_type(left);
-		l_mas.depth++;
+		new_height++;
 
 		/* Root already stored in l->node. */
 		if (mas_is_root_limits(mast->l))
@@ -2901,8 +2906,10 @@ static void mas_spanning_rebalance(struct ma_state *mas,
 			continue;
 
 		/* May be a new root stored in mast->bn */
-		if (mas_is_root_limits(mast->orig_l))
+		if (mas_is_root_limits(mast->orig_l)) {
+			new_height++;
 			break;
+		}
 
 		mast_spanning_rebalance(mast);
 
@@ -2913,7 +2920,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
 
 	l_mas.node = 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);
 	mas_set_parent(mas, left, l_mas.node, slot);
 	if (middle)
@@ -2937,7 +2944,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
 	mas->min = l_mas.min;
 	mas->max = l_mas.max;
 	mas->offset = l_mas.offset;
-	mas_wmb_replace(mas, old_enode);
+	mas_wmb_replace(mas, old_enode, new_height);
 	mtree_range_walk(mas);
 	return;
 }
@@ -3013,6 +3020,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end
 	void __rcu **l_slots, **slots;
 	unsigned long *l_pivs, *pivs, gap;
 	bool in_rcu = mt_in_rcu(mas->tree);
+	unsigned char new_height = mas_mt_height(mas);
 
 	MA_STATE(l_mas, mas->tree, mas->index, mas->last);
 
@@ -3107,7 +3115,7 @@ static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end
 	mas_ascend(mas);
 
 	if (in_rcu) {
-		mas_replace_node(mas, old_eparent);
+		mas_replace_node(mas, old_eparent, new_height);
 		mas_adopt_children(mas, mas->node);
 	}
 
@@ -3118,10 +3126,9 @@ static inline void mas_destroy_rebalance(struct ma_state *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;
 
@@ -3130,7 +3137,6 @@ static inline void mas_split_final_node(struct maple_subtree_state *mast,
 			mast->bn->type = maple_arange_64;
 		else
 			mast->bn->type = maple_range_64;
-		mas->depth = height;
 	}
 	/*
 	 * Only a single node is used here, could be root.
@@ -3218,7 +3224,6 @@ static inline void mast_split_data(struct maple_subtree_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.
  *
@@ -3226,8 +3231,8 @@ static inline void mast_split_data(struct maple_subtree_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 = mast->bn->b_end;
 	unsigned char end, space, split;
@@ -3284,7 +3289,7 @@ static inline bool mas_push_data(struct ma_state *mas, int height,
 
 	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;
 }
 
@@ -3297,6 +3302,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
 {
 	struct maple_subtree_state mast;
 	int height = 0;
+	unsigned int orig_height = mas_mt_height(mas);
 	unsigned char mid_split, split = 0;
 	struct maple_enode *old;
 
@@ -3323,7 +3329,6 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
 	MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last);
 
 	trace_ma_op(__func__, mas);
-	mas->depth = mas_mt_height(mas);
 
 	mast.l = &l_mas;
 	mast.r = &r_mas;
@@ -3331,9 +3336,9 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
 	mast.orig_r = &prev_r_mas;
 	mast.bn = b_node;
 
-	while (height++ <= mas->depth) {
+	while (height++ <= orig_height) {
 		if (mt_slots[b_node->type] > b_node->b_end) {
-			mas_split_final_node(&mast, mas, height);
+			mas_split_final_node(&mast, mas);
 			break;
 		}
 
@@ -3348,11 +3353,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;
+		}
 
 		split = mab_calc_split(mas, b_node, &mid_split);
 		mast_split_data(&mast, mas, split);
@@ -3369,7 +3378,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
 	/* Set the original node as dead */
 	old = mas->node;
 	mas->node = l_mas.node;
-	mas_wmb_replace(mas, old);
+	mas_wmb_replace(mas, old, height);
 	mtree_range_walk(mas);
 	return;
 }
@@ -3428,8 +3437,7 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
 	if (mas->last != ULONG_MAX)
 		pivots[++slot] = ULONG_MAX;
 
-	mas->depth = 1;
-	mas_set_height(mas);
+	mt_set_height(mas->tree, 1);
 	ma_set_meta(node, maple_leaf_64, 0, slot);
 	/* swap the new root into the tree */
 	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
@@ -3673,8 +3681,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
 	WARN_ON_ONCE(mas->index || mas->last != ULONG_MAX);
 
 	if (!entry) {
-		mas->depth = 0;
-		mas_set_height(mas);
+		mt_set_height(mas->tree, 0);
 		rcu_assign_pointer(mas->tree->ma_root, entry);
 		mas->status = ma_start;
 		goto done;
@@ -3688,8 +3695,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
 	mas->status = ma_active;
 	rcu_assign_pointer(slots[0], entry);
 	pivots[0] = mas->last;
-	mas->depth = 1;
-	mas_set_height(mas);
+	mt_set_height(mas->tree, 1);
 	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
 
 done:
@@ -3808,6 +3814,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas,
 	struct maple_node reuse, *newnode;
 	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
 	bool in_rcu = mt_in_rcu(mas->tree);
+	unsigned char height = mas_mt_height(mas);
 
 	if (mas->last == wr_mas->end_piv)
 		offset_end++; /* don't copy this offset */
@@ -3864,7 +3871,7 @@ static inline void mas_wr_node_store(struct ma_wr_state *wr_mas,
 		struct maple_enode *old_enode = mas->node;
 
 		mas->node = 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));
 	}
-- 
2.43.0

[PATCH v3 3/6] maple_tree: use vacant nodes to reduce worst case allocations

[Sidhartha Kumar]

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.

Signed-off-by: Sidhartha <sidhartha.kumar@oracle.com>
---
 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..7d777aa2d9ed 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -463,6 +463,7 @@ struct ma_wr_state {
 	void __rcu **slots;		/* mas->node->slots pointer */
 	void *entry;			/* The entry to write */
 	void *content;			/* The existing entry that is being overwritten */
+	unsigned char vacant_height;	/* Depth of lowest node with free space */
 };
 
 #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
@@ -498,6 +499,7 @@ struct ma_wr_state {
 		.mas = ma_state,					\
 		.content = NULL,					\
 		.entry = wr_entry,					\
+		.vacant_height = 0					\
 	}
 
 #define MA_TOPIARY(name, tree)						\
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index a37837d6f3eb..878a7740628c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3544,6 +3544,9 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas)
 		if (ma_is_leaf(wr_mas->type))
 			return true;
 
+		if (mas->end < mt_slots[wr_mas->type] - 1)
+			wr_mas->vacant_height = mas->depth + 1;
+
 		mas_wr_walk_traverse(wr_mas);
 	}
 
@@ -4159,7 +4162,9 @@ static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)
 static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
 {
 	struct ma_state *mas = wr_mas->mas;
-	int ret = mas_mt_height(mas) * 3 + 1;
+	unsigned char height = mas_mt_height(mas);
+	int ret = height * 3 + 1;
+	unsigned char delta = height - wr_mas->vacant_height;
 
 	switch (mas->store_type) {
 	case wr_invalid:
@@ -4177,13 +4182,13 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
 			ret = 0;
 		break;
 	case wr_spanning_store:
-		ret =  mas_mt_height(mas) * 3 + 1;
+		WARN_ON_ONCE(ret != height * 3 + 1);
 		break;
 	case wr_split_store:
-		ret =  mas_mt_height(mas) * 2 + 1;
+		ret = delta * 2 + 1;
 		break;
 	case wr_rebalance:
-		ret =  mas_mt_height(mas) * 2 - 1;
+		ret = height * 2 + 1;
 		break;
 	case wr_node_store:
 		ret = mt_in_rcu(mas->tree) ? 1 : 0;
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index bc30050227fd..5950a7c9b27f 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 */
 
+/* get height of the lowest non-leaf node with free space */
+static unsigned char get_vacant_height(struct ma_wr_state *wr_mas, void *entry)
+{
+	struct ma_state *mas = wr_mas->mas;
+	char vacant_height = 0;
+	enum maple_type type;
+	unsigned long *pivots;
+	unsigned long min = 0;
+	unsigned long max = ULONG_MAX;
+	unsigned char offset;
+
+	/* start traversal */
+	mas_reset(mas);
+	mas_start(mas);
+	if (!xa_is_node(mas_root(mas)))
+		return 0;
+
+	type = mte_node_type(mas->node);
+	wr_mas->type = type;
+	while (!ma_is_leaf(type)) {
+		mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max);
+		offset = mas->offset;
+		mas->end = mas_data_end(mas);
+		pivots = ma_pivots(mte_to_node(mas->node), type);
+
+		if (pivots) {
+			if (offset)
+				min = pivots[mas->offset - 1];
+			if (offset < mas->end)
+				max = pivots[mas->offset];
+		}
+		wr_mas->r_max = 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 = mas->depth + 1;
+
+		mas_descend(mas);
+		type = mte_node_type(mas->node);
+		mas->depth++;
+	}
+
+	return vacant_height;
+}
+
 /* Preallocation testing */
 static noinline void __init check_prealloc(struct maple_tree *mt)
 {
 	unsigned long i, max = 100;
 	unsigned long allocated;
 	unsigned char height;
+	unsigned char vacant_height;
 	struct maple_node *mn;
 	void *ptr = check_prealloc;
 	MA_STATE(mas, mt, 10, 20);
+	MA_WR_STATE(wr_mas, &mas, ptr);
 
 	mt_set_non_kernel(1000);
 	for (i = 0; i <= max; i++)
@@ -35494,8 +35544,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
 	MT_BUG_ON(mt, allocated == 0);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
 	mas_destroy(&mas);
 	allocated = mas_allocated(&mas);
 	MT_BUG_ON(mt, allocated != 0);
@@ -35503,8 +35554,9 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
 	MT_BUG_ON(mt, allocated == 0);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	mas_destroy(&mas);
 	allocated = mas_allocated(&mas);
@@ -35514,7 +35566,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
+	MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
 	mn = mas_pop_node(&mas);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
 	mn->parent = ma_parent_ptr(mn);
@@ -35527,7 +35580,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
+	MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
 	mn = mas_pop_node(&mas);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
@@ -35540,7 +35594,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
+	MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
 	mn = mas_pop_node(&mas);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
 	mas_push_node(&mas, mn);
@@ -35553,7 +35608,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
+	MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 3);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 
@@ -35578,7 +35634,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated != 1 + height * 2);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
+	MT_BUG_ON(mt, allocated != 1 + (height - vacant_height) * 2);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 	mt_set_non_kernel(1);
@@ -35595,8 +35652,14 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
+	vacant_height = get_vacant_height(&wr_mas, ptr);
 	MT_BUG_ON(mt, allocated == 0);
-	MT_BUG_ON(mt, allocated != 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 != height * 3 + 1);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 	mas_set_range(&mas, 0, 200);
-- 
2.43.0

[PATCH v3 4/6] maple_tree: break on convergence in mas_spanning_rebalance()

[Sidhartha Kumar]

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 <liam.howlett@oracle.com>
Reviewed-by: Wei Yang <richard.weiyang@gmail.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 lib/maple_tree.c | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 878a7740628c..c859c7253d69 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2899,11 +2899,24 @@ static void mas_spanning_rebalance(struct ma_state *mas,
 		mast_combine_cp_right(mast);
 		mast->orig_l->last = mast->orig_l->max;
 
-		if (mast_sufficient(mast))
-			continue;
+		if (mast_sufficient(mast)) {
+			if (mast_overflow(mast))
+				continue;
+
+			if (mast->orig_l->node == mast->orig_r->node) {
+			       /*
+				* The data in b_node should be stored in one
+				* node and in the tree
+				*/
+				slot = mast->l->offset;
+				/* May be a new root stored in mast->bn */
+				if (mas_is_root_limits(mast->orig_l))
+					new_height++;
+				break;
+			}
 
-		if (mast_overflow(mast))
 			continue;
+		}
 
 		/* May be a new root stored in mast->bn */
 		if (mas_is_root_limits(mast->orig_l)) {
-- 
2.43.0

[PATCH v3 5/6] maple_tree: add sufficient height

[Sidhartha Kumar]

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 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.

Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 include/linux/maple_tree.h       |  4 +++-
 lib/maple_tree.c                 | 17 +++++++++++++++--
 tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++
 3 files changed, 46 insertions(+), 3 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 7d777aa2d9ed..37dc9525dff6 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -464,6 +464,7 @@ struct ma_wr_state {
 	void *entry;			/* The entry to write */
 	void *content;			/* The existing entry that is being overwritten */
 	unsigned char vacant_height;	/* Depth of lowest node with free space */
+	unsigned char sufficient_height;/* Depth of lowest node with min sufficiency + 1 nodes */
 };
 
 #define mas_lock(mas)           spin_lock(&((mas)->tree->ma_lock))
@@ -499,7 +500,8 @@ struct ma_wr_state {
 		.mas = ma_state,					\
 		.content = NULL,					\
 		.entry = wr_entry,					\
-		.vacant_height = 0					\
+		.vacant_height = 0,					\
+		.sufficient_height = 0					\
 	}
 
 #define MA_TOPIARY(name, tree)						\
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index c859c7253d69..d3aa5241166b 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3560,6 +3560,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 = mas->depth + 1;
 
+		if (ma_is_root(mas_mn(mas))) {
+			/* root needs more than 2 entries to be sufficient + 1 */
+			if (mas->end > 2)
+				wr_mas->sufficient_height = 1;
+		} else if (mas->end > mt_min_slots[wr_mas->type] + 1)
+			wr_mas->sufficient_height = mas->depth + 1;
+
 		mas_wr_walk_traverse(wr_mas);
 	}
 
@@ -4195,13 +4202,19 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
 			ret = 0;
 		break;
 	case wr_spanning_store:
-		WARN_ON_ONCE(ret != height * 3 + 1);
+		if (wr_mas->sufficient_height < wr_mas->vacant_height)
+			ret = (height - wr_mas->sufficient_height) * 3 + 1;
+		else
+			ret = delta * 3 + 1;
 		break;
 	case wr_split_store:
 		ret = delta * 2 + 1;
 		break;
 	case wr_rebalance:
-		ret = height * 2 + 1;
+		if (wr_mas->sufficient_height < wr_mas->vacant_height)
+			ret = (height - wr_mas->sufficient_height) * 2 + 1;
+		else
+			ret = delta * 2 + 1;
 		break;
 	case wr_node_store:
 		ret = mt_in_rcu(mas->tree) ? 1 : 0;
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 5950a7c9b27f..dc8e40b94c3f 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -36311,6 +36311,30 @@ static noinline void __init check_mtree_dup(struct maple_tree *mt)
 
 extern void test_kmem_cache_bulk(void);
 
+/*
+ * Test to check the path of a spanning rebalance which results in
+ * a collapse where the rebalancing of the child node leads to
+ * insufficieny in the parent node.
+ */
+static void check_collapsing_rebalance(struct maple_tree *mt)
+{
+	int i = 0;
+	MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX);
+
+	/* create a height 4 tree */
+	while (mt_height(mt) < 4) {
+		mtree_store_range(mt, i, i + 10, xa_mk_value(i), GFP_KERNEL);
+		i += 9;
+	}
+
+	/* delete all entries one at a time, starting from the right */
+	do {
+		mas_erase(&mas);
+	} while (mas_prev(&mas, 0) != NULL);
+
+	mtree_unlock(mt);
+}
+
 /* callback function used for check_nomem_writer_race() */
 static void writer2(void *maple_tree)
 {
@@ -36477,6 +36501,10 @@ void farmer_tests(void)
 	check_spanning_write(&tree);
 	mtree_destroy(&tree);
 
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	check_collapsing_rebalance(&tree);
+	mtree_destroy(&tree);
+
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
 	check_null_expand(&tree);
 	mtree_destroy(&tree);
-- 
2.43.0

[PATCH v3 6/6] maple_tree: reorder mas->store_type case statements

[Sidhartha Kumar]

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 <liam.howlett@oracle.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
 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 d3aa5241166b..776693593ab9 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4093,15 +4093,6 @@ static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas)
 	unsigned char new_end = mas_wr_new_end(wr_mas);
 
 	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)
@@ -4123,6 +4114,14 @@ static inline void mas_wr_store_entry(struct ma_wr_state *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);
 	}
 
 	return;
@@ -4187,19 +4186,10 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
 	unsigned char delta = height - wr_mas->vacant_height;
 
 	switch (mas->store_type) {
-	case wr_invalid:
-		WARN_ON_ONCE(1);
-		break;
-	case wr_new_root:
-		ret = 1;
-		break;
-	case wr_store_root:
-		if (likely((mas->last != 0) || (mas->index != 0)))
-			ret = 1;
-		else if (((unsigned long) (entry) & 3) == 2)
-			ret = 1;
-		else
-			ret = 0;
+	case wr_exact_fit:
+	case wr_append:
+	case wr_slot_store:
+		ret = 0;
 		break;
 	case wr_spanning_store:
 		if (wr_mas->sufficient_height < wr_mas->vacant_height)
@@ -4219,10 +4209,19 @@ static inline int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)
 	case wr_node_store:
 		ret = mt_in_rcu(mas->tree) ? 1 : 0;
 		break;
-	case wr_append:
-	case wr_exact_fit:
-	case wr_slot_store:
-		ret = 0;
+	case wr_new_root:
+		ret = 1;
+		break;
+	case wr_store_root:
+		if (likely((mas->last != 0) || (mas->index != 0)))
+			ret = 1;
+		else if (((unsigned long) (entry) & 3) == 2)
+			ret = 1;
+		else
+			ret = 0;
+		break;
+	case wr_invalid:
+		WARN_ON_ONCE(1);
 	}
 
 	return ret;
-- 
2.43.0

Re: [PATCH v3 5/6] maple_tree: add sufficient height

[Vasily Gorbik]

On Thu, Feb 27, 2025 at 08:48:22PM +0000, Sidhartha Kumar wrote:
> 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.
...
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
>  include/linux/maple_tree.h       |  4 +++-
>  lib/maple_tree.c                 | 17 +++++++++++++++--
>  tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++
>  3 files changed, 46 insertions(+), 3 deletions(-)

Hi Sidhartha,

Starting from this commit, the LTP test "linkat02" consistently triggers
a kernel WARNING followed by a crash, at least on s390 (and probably on
other big-endian architectures as well). The maple tree selftest passes
successfully.

[  233.489583] LTP: starting linkat02
linkat02    0  TINFO  :  Using /tmp/ltp-8P2ZJL0mgN/LTP_lin3flG7N as tmpdir (tmpfs filesystem)
linkat02    0  TINFO  :  Found free device 0 '/dev/loop0'
[  234.187957] loop0: detected capacity change from 0 to 614400
linkat02    0  TINFO  :  Formatting /dev/loop0 with ext2 opts='' extra opts=''
mke2fs 1.47.1 (20-May-2024)
[  234.571157] operation not supported error, dev loop0, sector 614272 op 0x9:(WRITE_ZEROES) flags 0x10000800 phys_seg 0 prio class 0
linkat02    0  TINFO  :  Mounting /dev/loop0 to /tmp/ltp-8P2ZJL0mgN/LTP_lin3flG7N/mntpoint fstyp=ext2 flags=0
[  234.690816] EXT4-fs (loop0): mounting ext2 file system using the ext4 subsystem
[  234.696090] EXT4-fs (loop0): mounted filesystem 29120d07-e10b-43b8-bfb0-6156683a2769 r/w without journal. Quota mode: none.
linkat02    0  TINFO  :  Failed reach the hardlinks limit
[  239.616047] ------------[ cut here ]------------
[  239.616231] WARNING: CPU: 0 PID: 669 at lib/maple_tree.c:1156 mas_pop_node+0x220/0x290
[  239.616252] Modules linked in:
[  239.616292] CPU: 0 UID: 0 PID: 669 Comm: linkat02 Not tainted 6.14.0-rc5-next-20250307 #29
[  239.616305] Hardware name: IBM 3931 A01 704 (KVM/Linux)
[  239.616315] Krnl PSW : 0704c00180000000 00007fffe2b6c314 (mas_pop_node+0x224/0x290)
[  239.616334]            R:0 T:1 IO:1 EX:1 Key:0 M:1 W:0 P:0 AS:3 CC:0 PM:0 RI:0 EA:3
[  239.616349] Krnl GPRS: 0000000000000005 001c0feffc355f67 00007f7fe1aafb38 001c000000000000
[  239.616360]            001c000000000000 001c0fef00007f05 0000000000000000 ffffffffffffffff
[  239.616371]            00007f7fe1aaf3e0 00007f7fe1aafb08 001c000000000000 0000000000000000
[  239.616381]            0000000001026838 0000000000000005 00007f7fe1aaf020 00007f7fe1aaefc8
[  239.616399] Krnl Code: 00007fffe2b6c306: e370a0000024        stg     %r7,0(%r10)
[  239.616399]            00007fffe2b6c30c: a7f4ff83            brc     15,00007fffe2b6c212
[  239.616399]           #00007fffe2b6c310: af000000            mc      0,0
[  239.616399]           >00007fffe2b6c314: a7b90000            lghi    %r11,0
[  239.616399]            00007fffe2b6c318: a7f4ff89            brc     15,00007fffe2b6c22a
[  239.616399]            00007fffe2b6c31c: c0e5fefc1f8a        brasl   %r14,00007fffe0af0230
[  239.616399]            00007fffe2b6c322: a7f4ff4b            brc     15,00007fffe2b6c1b8
[  239.616399]            00007fffe2b6c326: c0e5fefc1fa5        brasl   %r14,00007fffe0af0270
[  239.616454] Call Trace:
[  239.616463]  [<00007fffe2b6c314>] mas_pop_node+0x224/0x290
[  239.616475]  [<00007fffe2b85ab6>] mas_spanning_rebalance+0x3006/0x4e90
[  239.616487]  [<00007fffe2b87e7a>] mas_rebalance+0x53a/0x9c0
[  239.616627]  [<00007fffe2b8c10a>] mas_wr_bnode+0x14a/0x1a0
[  239.616639]  [<00007fffe2b9a87c>] mas_erase+0xd9c/0x1120
[  239.616650]  [<00007fffe2b9acbe>] mtree_erase+0xbe/0xf0
[  239.616661]  [<00007fffe0c3b4d2>] simple_offset_remove+0x52/0x90
[  239.616674]  [<00007fffe093dc16>] shmem_unlink+0xb6/0x320
[  239.616686]  [<00007fffe0bc0830>] vfs_unlink+0x270/0x760
[  239.616698]  [<00007fffe0bd473a>] do_unlinkat+0x40a/0x5c0
[  239.616709]  [<00007fffe0bd4a48>] __s390x_sys_unlink+0x58/0x70
[  239.616720]  [<00007fffe0155356>] do_syscall+0x2f6/0x430
[  239.616733]  [<00007fffe2bd3668>] __do_syscall+0xc8/0x1c0
[  239.616746]  [<00007fffe2bf70d4>] system_call+0x74/0x98
[  239.616758] 4 locks held by linkat02/669:
[  239.616769]  #0: 0000780097e89450 (sb_writers#8){.+.+}-{0:0}, at: mnt_want_write+0x4c/0xc0
[  239.616799]  #1: 00007800a7de6cd0 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: do_unlinkat+0x1f8/0x5c0
[  239.616831]  #2: 00007800a7de7ac0 (&sb->s_type->i_mutex_key#12){+.+.}-{3:3}, at: vfs_unlink+0xc6/0x760
[  239.616860]  #3: 00007800a7de6a58 (&simple_offset_lock_class){+.+.}-{2:2}, at: mtree_erase+0xb4/0xf0
[  239.616886] Last Breaking-Event-Address:
[  239.616895]  [<00007fffe2b6c12a>] mas_pop_node+0x3a/0x290
[  239.616909] irq event stamp: 5205821
[  239.616918] hardirqs last  enabled at (5205831): [<00007fffe03d2be8>] __up_console_sem+0xe8/0x130
[  239.616931] hardirqs last disabled at (5205840): [<00007fffe03d2bc6>] __up_console_sem+0xc6/0x130
[  239.616943] softirqs last  enabled at (5200824): [<00007fffe0246b6c>] handle_softirqs+0x6dc/0xe30
[  239.616955] softirqs last disabled at (5200687): [<00007fffe024508a>] __irq_exit_rcu+0x34a/0x3f0
[  239.616994] ---[ end trace 0000000000000000 ]---
[  239.617009] Unable to handle kernel pointer dereference in virtual kernel address space
[  239.617019] Failing address: 0000000000000000 TEID: 0000000000000483
[  239.617029] Fault in home space mode while using kernel ASCE.
[  239.617049] AS:0000000005dac00b R2:00000001ffffc00b R3:00000001ffff8007 S:00000001ffff7801 P:000000000000013d
[  239.617150] Oops: 0004 ilc:3 [#1] PREEMPT SMP
[  239.617162] Modules linked in:
[  239.617170] CPU: 0 UID: 0 PID: 669 Comm: linkat02 Tainted: G        W           6.14.0-rc5-next-20250307 #29
[  239.617243] Tainted: [W]=WARN
[  239.617248] Hardware name: IBM 3931 A01 704 (KVM/Linux)
[  239.617253] Krnl PSW : 0704c00180000000 00007fffe2b6a988 (mab_mas_cp+0x168/0x640)
[  239.617264]            R:0 T:1 IO:1 EX:1 Key:0 M:1 W:0 P:0 AS:3 CC:0 PM:0 RI:0 EA:3
[  239.617272] Krnl GPRS: 0000000000000008 0000000000000000 00007fff00000008 00007f7f00000009
[  239.617279]            0000000000000008 001c000000000000 0000000000000008 0000000000000048
[  239.617285]            001c0ffffc638e09 001c000000000009 0000000000000098 001c000000000000
[  239.617292]            0000000001026838 00007f7fe1aaf608 001c000000000013 00007f7fe1aaef68
[  239.617302] Krnl Code: 00007fffe2b6a97c: b90800e5            agr     %r14,%r5
[  239.617302]            00007fffe2b6a980: 9500e000            cli     0(%r14),0
[  239.617302]           #00007fffe2b6a984: a7740262            brc     7,00007fffe2b6ae48
[  239.617302]           >00007fffe2b6a988: e548a0000000        mvghi   0(%r10),0
[  239.617302]            00007fffe2b6a98e: e3a0f0c00004        lg      %r10,192(%r15)
[  239.617302]            00007fffe2b6a994: a7b80000            lhi     %r11,0
[  239.617302]            00007fffe2b6a998: eb2a0003000d        sllg    %r2,%r10,3
[  239.617302]            00007fffe2b6a99e: e320f0f00024        stg     %r2,240(%r15)
[  239.617350] Call Trace:
[  239.617354]  [<00007fffe2b6a988>] mab_mas_cp+0x168/0x640
[  239.617362]  [<00007fffe2b85bcc>] mas_spanning_rebalance+0x311c/0x4e90
[  239.617369]  [<00007fffe2b87e7a>] mas_rebalance+0x53a/0x9c0
[  239.617376]  [<00007fffe2b8c10a>] mas_wr_bnode+0x14a/0x1a0
[  239.617383]  [<00007fffe2b9a87c>] mas_erase+0xd9c/0x1120
[  239.617389]  [<00007fffe2b9acbe>] mtree_erase+0xbe/0xf0
[  239.617396]  [<00007fffe0c3b4d2>] simple_offset_remove+0x52/0x90
[  239.617403]  [<00007fffe093dc16>] shmem_unlink+0xb6/0x320
[  239.617410]  [<00007fffe0bc0830>] vfs_unlink+0x270/0x760
[  239.617416]  [<00007fffe0bd473a>] do_unlinkat+0x40a/0x5c0
[  239.617422]  [<00007fffe0bd4a48>] __s390x_sys_unlink+0x58/0x70
[  239.617429]  [<00007fffe0155356>] do_syscall+0x2f6/0x430
[  239.617436]  [<00007fffe2bd3668>] __do_syscall+0xc8/0x1c0
[  239.617443]  [<00007fffe2bf70d4>] system_call+0x74/0x98
[  239.617450] INFO: lockdep is turned off.
[  239.617454] Last Breaking-Event-Address:
[  239.617458]  [<00007fffe2b6a8f4>] mab_mas_cp+0xd4/0x640
[  239.617468] Kernel panic - not syncing: Fatal exception: panic_on_oops

Re: [PATCH v3 5/6] maple_tree: add sufficient height

[Sidhartha Kumar]

On 3/10/25 2:13 PM, Vasily Gorbik wrote:
> On Thu, Feb 27, 2025 at 08:48:22PM +0000, Sidhartha Kumar wrote:
>> 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.
> ...
>> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
>> ---
>>   include/linux/maple_tree.h       |  4 +++-
>>   lib/maple_tree.c                 | 17 +++++++++++++++--
>>   tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++
>>   3 files changed, 46 insertions(+), 3 deletions(-)
> 
> Hi Sidhartha,
> 
> Starting from this commit, the LTP test "linkat02" consistently triggers
> a kernel WARNING followed by a crash, at least on s390 (and probably on
> other big-endian architectures as well). The maple tree selftest passes
> successfully.
> 

Hi,

Thanks for reporting this, it looks like it doesn't reproduce on x86 so 
I'll try to virtualize s390 to reproduce. Andrew, could you revert this 
series from mm-unstable as I work on fixing this?

Thanks,
Sid




> [  233.489583] LTP: starting linkat02
> linkat02    0  TINFO  :  Using /tmp/ltp-8P2ZJL0mgN/LTP_lin3flG7N as tmpdir (tmpfs filesystem)
> linkat02    0  TINFO  :  Found free device 0 '/dev/loop0'
> [  234.187957] loop0: detected capacity change from 0 to 614400
> linkat02    0  TINFO  :  Formatting /dev/loop0 with ext2 opts='' extra opts=''
> mke2fs 1.47.1 (20-May-2024)
> [  234.571157] operation not supported error, dev loop0, sector 614272 op 0x9:(WRITE_ZEROES) flags 0x10000800 phys_seg 0 prio class 0
> linkat02    0  TINFO  :  Mounting /dev/loop0 to /tmp/ltp-8P2ZJL0mgN/LTP_lin3flG7N/mntpoint fstyp=ext2 flags=0
> [  234.690816] EXT4-fs (loop0): mounting ext2 file system using the ext4 subsystem
> [  234.696090] EXT4-fs (loop0): mounted filesystem 29120d07-e10b-43b8-bfb0-6156683a2769 r/w without journal. Quota mode: none.
> linkat02    0  TINFO  :  Failed reach the hardlinks limit
> [  239.616047] ------------[ cut here ]------------
> [  239.616231] WARNING: CPU: 0 PID: 669 at lib/maple_tree.c:1156 mas_pop_node+0x220/0x290
> [  239.616252] Modules linked in:
> [  239.616292] CPU: 0 UID: 0 PID: 669 Comm: linkat02 Not tainted 6.14.0-rc5-next-20250307 #29
> [  239.616305] Hardware name: IBM 3931 A01 704 (KVM/Linux)
> [  239.616315] Krnl PSW : 0704c00180000000 00007fffe2b6c314 (mas_pop_node+0x224/0x290)
> [  239.616334]            R:0 T:1 IO:1 EX:1 Key:0 M:1 W:0 P:0 AS:3 CC:0 PM:0 RI:0 EA:3
> [  239.616349] Krnl GPRS: 0000000000000005 001c0feffc355f67 00007f7fe1aafb38 001c000000000000
> [  239.616360]            001c000000000000 001c0fef00007f05 0000000000000000 ffffffffffffffff
> [  239.616371]            00007f7fe1aaf3e0 00007f7fe1aafb08 001c000000000000 0000000000000000
> [  239.616381]            0000000001026838 0000000000000005 00007f7fe1aaf020 00007f7fe1aaefc8
> [  239.616399] Krnl Code: 00007fffe2b6c306: e370a0000024        stg     %r7,0(%r10)
> [  239.616399]            00007fffe2b6c30c: a7f4ff83            brc     15,00007fffe2b6c212
> [  239.616399]           #00007fffe2b6c310: af000000            mc      0,0
> [  239.616399]           >00007fffe2b6c314: a7b90000            lghi    %r11,0
> [  239.616399]            00007fffe2b6c318: a7f4ff89            brc     15,00007fffe2b6c22a
> [  239.616399]            00007fffe2b6c31c: c0e5fefc1f8a        brasl   %r14,00007fffe0af0230
> [  239.616399]            00007fffe2b6c322: a7f4ff4b            brc     15,00007fffe2b6c1b8
> [  239.616399]            00007fffe2b6c326: c0e5fefc1fa5        brasl   %r14,00007fffe0af0270
> [  239.616454] Call Trace:
> [  239.616463]  [<00007fffe2b6c314>] mas_pop_node+0x224/0x290
> [  239.616475]  [<00007fffe2b85ab6>] mas_spanning_rebalance+0x3006/0x4e90
> [  239.616487]  [<00007fffe2b87e7a>] mas_rebalance+0x53a/0x9c0
> [  239.616627]  [<00007fffe2b8c10a>] mas_wr_bnode+0x14a/0x1a0
> [  239.616639]  [<00007fffe2b9a87c>] mas_erase+0xd9c/0x1120
> [  239.616650]  [<00007fffe2b9acbe>] mtree_erase+0xbe/0xf0
> [  239.616661]  [<00007fffe0c3b4d2>] simple_offset_remove+0x52/0x90
> [  239.616674]  [<00007fffe093dc16>] shmem_unlink+0xb6/0x320
> [  239.616686]  [<00007fffe0bc0830>] vfs_unlink+0x270/0x760
> [  239.616698]  [<00007fffe0bd473a>] do_unlinkat+0x40a/0x5c0
> [  239.616709]  [<00007fffe0bd4a48>] __s390x_sys_unlink+0x58/0x70
> [  239.616720]  [<00007fffe0155356>] do_syscall+0x2f6/0x430
> [  239.616733]  [<00007fffe2bd3668>] __do_syscall+0xc8/0x1c0
> [  239.616746]  [<00007fffe2bf70d4>] system_call+0x74/0x98
> [  239.616758] 4 locks held by linkat02/669:
> [  239.616769]  #0: 0000780097e89450 (sb_writers#8){.+.+}-{0:0}, at: mnt_want_write+0x4c/0xc0
> [  239.616799]  #1: 00007800a7de6cd0 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: do_unlinkat+0x1f8/0x5c0
> [  239.616831]  #2: 00007800a7de7ac0 (&sb->s_type->i_mutex_key#12){+.+.}-{3:3}, at: vfs_unlink+0xc6/0x760
> [  239.616860]  #3: 00007800a7de6a58 (&simple_offset_lock_class){+.+.}-{2:2}, at: mtree_erase+0xb4/0xf0
> [  239.616886] Last Breaking-Event-Address:
> [  239.616895]  [<00007fffe2b6c12a>] mas_pop_node+0x3a/0x290
> [  239.616909] irq event stamp: 5205821
> [  239.616918] hardirqs last  enabled at (5205831): [<00007fffe03d2be8>] __up_console_sem+0xe8/0x130
> [  239.616931] hardirqs last disabled at (5205840): [<00007fffe03d2bc6>] __up_console_sem+0xc6/0x130
> [  239.616943] softirqs last  enabled at (5200824): [<00007fffe0246b6c>] handle_softirqs+0x6dc/0xe30
> [  239.616955] softirqs last disabled at (5200687): [<00007fffe024508a>] __irq_exit_rcu+0x34a/0x3f0
> [  239.616994] ---[ end trace 0000000000000000 ]---
> [  239.617009] Unable to handle kernel pointer dereference in virtual kernel address space
> [  239.617019] Failing address: 0000000000000000 TEID: 0000000000000483
> [  239.617029] Fault in home space mode while using kernel ASCE.
> [  239.617049] AS:0000000005dac00b R2:00000001ffffc00b R3:00000001ffff8007 S:00000001ffff7801 P:000000000000013d
> [  239.617150] Oops: 0004 ilc:3 [#1] PREEMPT SMP
> [  239.617162] Modules linked in:
> [  239.617170] CPU: 0 UID: 0 PID: 669 Comm: linkat02 Tainted: G        W           6.14.0-rc5-next-20250307 #29
> [  239.617243] Tainted: [W]=WARN
> [  239.617248] Hardware name: IBM 3931 A01 704 (KVM/Linux)
> [  239.617253] Krnl PSW : 0704c00180000000 00007fffe2b6a988 (mab_mas_cp+0x168/0x640)
> [  239.617264]            R:0 T:1 IO:1 EX:1 Key:0 M:1 W:0 P:0 AS:3 CC:0 PM:0 RI:0 EA:3
> [  239.617272] Krnl GPRS: 0000000000000008 0000000000000000 00007fff00000008 00007f7f00000009
> [  239.617279]            0000000000000008 001c000000000000 0000000000000008 0000000000000048
> [  239.617285]            001c0ffffc638e09 001c000000000009 0000000000000098 001c000000000000
> [  239.617292]            0000000001026838 00007f7fe1aaf608 001c000000000013 00007f7fe1aaef68
> [  239.617302] Krnl Code: 00007fffe2b6a97c: b90800e5            agr     %r14,%r5
> [  239.617302]            00007fffe2b6a980: 9500e000            cli     0(%r14),0
> [  239.617302]           #00007fffe2b6a984: a7740262            brc     7,00007fffe2b6ae48
> [  239.617302]           >00007fffe2b6a988: e548a0000000        mvghi   0(%r10),0
> [  239.617302]            00007fffe2b6a98e: e3a0f0c00004        lg      %r10,192(%r15)
> [  239.617302]            00007fffe2b6a994: a7b80000            lhi     %r11,0
> [  239.617302]            00007fffe2b6a998: eb2a0003000d        sllg    %r2,%r10,3
> [  239.617302]            00007fffe2b6a99e: e320f0f00024        stg     %r2,240(%r15)
> [  239.617350] Call Trace:
> [  239.617354]  [<00007fffe2b6a988>] mab_mas_cp+0x168/0x640
> [  239.617362]  [<00007fffe2b85bcc>] mas_spanning_rebalance+0x311c/0x4e90
> [  239.617369]  [<00007fffe2b87e7a>] mas_rebalance+0x53a/0x9c0
> [  239.617376]  [<00007fffe2b8c10a>] mas_wr_bnode+0x14a/0x1a0
> [  239.617383]  [<00007fffe2b9a87c>] mas_erase+0xd9c/0x1120
> [  239.617389]  [<00007fffe2b9acbe>] mtree_erase+0xbe/0xf0
> [  239.617396]  [<00007fffe0c3b4d2>] simple_offset_remove+0x52/0x90
> [  239.617403]  [<00007fffe093dc16>] shmem_unlink+0xb6/0x320
> [  239.617410]  [<00007fffe0bc0830>] vfs_unlink+0x270/0x760
> [  239.617416]  [<00007fffe0bd473a>] do_unlinkat+0x40a/0x5c0
> [  239.617422]  [<00007fffe0bd4a48>] __s390x_sys_unlink+0x58/0x70
> [  239.617429]  [<00007fffe0155356>] do_syscall+0x2f6/0x430
> [  239.617436]  [<00007fffe2bd3668>] __do_syscall+0xc8/0x1c0
> [  239.617443]  [<00007fffe2bf70d4>] system_call+0x74/0x98
> [  239.617450] INFO: lockdep is turned off.
> [  239.617454] Last Breaking-Event-Address:
> [  239.617458]  [<00007fffe2b6a8f4>] mab_mas_cp+0xd4/0x640
> [  239.617468] Kernel panic - not syncing: Fatal exception: panic_on_oops
> 

Re: [PATCH v3 5/6] maple_tree: add sufficient height

[Andrew Morton]

On Mon, 10 Mar 2025 17:01:28 -0400 Sidhartha Kumar <sidhartha.kumar@oracle.com> wrote:

> Andrew, could you revert this 
> series from mm-unstable as I work on fixing this?

I have done so, thanks.

Re: [PATCH v3 5/6] maple_tree: add sufficient height

[Sidhartha Kumar]

On 3/10/25 2:13 PM, Vasily Gorbik wrote:
> On Thu, Feb 27, 2025 at 08:48:22PM +0000, Sidhartha Kumar wrote:
>> 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.
> ...
>> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
>> ---
>>   include/linux/maple_tree.h       |  4 +++-
>>   lib/maple_tree.c                 | 17 +++++++++++++++--
>>   tools/testing/radix-tree/maple.c | 28 ++++++++++++++++++++++++++++
>>   3 files changed, 46 insertions(+), 3 deletions(-)
> 
> Hi Sidhartha,
> 
> Starting from this commit, the LTP test "linkat02" consistently triggers
> a kernel WARNING followed by a crash, at least on s390 (and probably on
> other big-endian architectures as well). The maple tree selftest passes
> successfully.
> 

Would you be able to rerun this test with the following diff applied and 
CONFIG_DEBUG_MAPLE_TREE=y so I can check the state of the tree to easier 
reproduce the error?

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index ea1f0acac118..74a4b1924a55 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1153,8 +1153,11 @@ static inline struct maple_node 
*mas_pop_node(struct ma_state *mas)
         unsigned int req = mas_alloc_req(mas);

         /* nothing or a request pending. */
-       if (WARN_ON(!total))
+       if (WARN_ON(!total)) {
+               mas_dump(mas);
+               mt_dump(mas->tree, mt_dump_hex);
                 return NULL;
+       }

         if (total == 1) {
                 /* single allocation in this ma_state */


> [  233.489583] LTP: starting linkat02
> linkat02    0  TINFO  :  Using /tmp/ltp-8P2ZJL0mgN/LTP_lin3flG7N as tmpdir (tmpfs filesystem)
> linkat02    0  TINFO  :  Found free device 0 '/dev/loop0'
> [  234.187957] loop0: detected capacity change from 0 to 614400
> linkat02    0  TINFO  :  Formatting /dev/loop0 with ext2 opts='' extra opts=''
> mke2fs 1.47.1 (20-May-2024)
> [  234.571157] operation not supported error, dev loop0, sector 614272 op 0x9:(WRITE_ZEROES) flags 0x10000800 phys_seg 0 prio class 0
> linkat02    0  TINFO  :  Mounting /dev/loop0 to /tmp/ltp-8P2ZJL0mgN/LTP_lin3flG7N/mntpoint fstyp=ext2 flags=0
> [  234.690816] EXT4-fs (loop0): mounting ext2 file system using the ext4 subsystem
> [  234.696090] EXT4-fs (loop0): mounted filesystem 29120d07-e10b-43b8-bfb0-6156683a2769 r/w without journal. Quota mode: none.
> linkat02    0  TINFO  :  Failed reach the hardlinks limit
> [  239.616047] ------------[ cut here ]------------
> [  239.616231] WARNING: CPU: 0 PID: 669 at lib/maple_tree.c:1156 mas_pop_node+0x220/0x290
> [  239.616252] Modules linked in:
> [  239.616292] CPU: 0 UID: 0 PID: 669 Comm: linkat02 Not tainted 6.14.0-rc5-next-20250307 #29
> [  239.616305] Hardware name: IBM 3931 A01 704 (KVM/Linux)
> [  239.616315] Krnl PSW : 0704c00180000000 00007fffe2b6c314 (mas_pop_node+0x224/0x290)
> [  239.616334]            R:0 T:1 IO:1 EX:1 Key:0 M:1 W:0 P:0 AS:3 CC:0 PM:0 RI:0 EA:3
> [  239.616349] Krnl GPRS: 0000000000000005 001c0feffc355f67 00007f7fe1aafb38 001c000000000000
> [  239.616360]            001c000000000000 001c0fef00007f05 0000000000000000 ffffffffffffffff
> [  239.616371]            00007f7fe1aaf3e0 00007f7fe1aafb08 001c000000000000 0000000000000000
> [  239.616381]            0000000001026838 0000000000000005 00007f7fe1aaf020 00007f7fe1aaefc8
> [  239.616399] Krnl Code: 00007fffe2b6c306: e370a0000024        stg     %r7,0(%r10)
> [  239.616399]            00007fffe2b6c30c: a7f4ff83            brc     15,00007fffe2b6c212
> [  239.616399]           #00007fffe2b6c310: af000000            mc      0,0
> [  239.616399]           >00007fffe2b6c314: a7b90000            lghi    %r11,0
> [  239.616399]            00007fffe2b6c318: a7f4ff89            brc     15,00007fffe2b6c22a
> [  239.616399]            00007fffe2b6c31c: c0e5fefc1f8a        brasl   %r14,00007fffe0af0230
> [  239.616399]            00007fffe2b6c322: a7f4ff4b            brc     15,00007fffe2b6c1b8
> [  239.616399]            00007fffe2b6c326: c0e5fefc1fa5        brasl   %r14,00007fffe0af0270
> [  239.616454] Call Trace:
> [  239.616463]  [<00007fffe2b6c314>] mas_pop_node+0x224/0x290
> [  239.616475]  [<00007fffe2b85ab6>] mas_spanning_rebalance+0x3006/0x4e90
> [  239.616487]  [<00007fffe2b87e7a>] mas_rebalance+0x53a/0x9c0
> [  239.616627]  [<00007fffe2b8c10a>] mas_wr_bnode+0x14a/0x1a0
> [  239.616639]  [<00007fffe2b9a87c>] mas_erase+0xd9c/0x1120
> [  239.616650]  [<00007fffe2b9acbe>] mtree_erase+0xbe/0xf0
> [  239.616661]  [<00007fffe0c3b4d2>] simple_offset_remove+0x52/0x90
> [  239.616674]  [<00007fffe093dc16>] shmem_unlink+0xb6/0x320
> [  239.616686]  [<00007fffe0bc0830>] vfs_unlink+0x270/0x760
> [  239.616698]  [<00007fffe0bd473a>] do_unlinkat+0x40a/0x5c0
> [  239.616709]  [<00007fffe0bd4a48>] __s390x_sys_unlink+0x58/0x70
> [  239.616720]  [<00007fffe0155356>] do_syscall+0x2f6/0x430
> [  239.616733]  [<00007fffe2bd3668>] __do_syscall+0xc8/0x1c0
> [  239.616746]  [<00007fffe2bf70d4>] system_call+0x74/0x98
> [  239.616758] 4 locks held by linkat02/669:
> [  239.616769]  #0: 0000780097e89450 (sb_writers#8){.+.+}-{0:0}, at: mnt_want_write+0x4c/0xc0
> [  239.616799]  #1: 00007800a7de6cd0 (&type->i_mutex_dir_key#5/1){+.+.}-{3:3}, at: do_unlinkat+0x1f8/0x5c0
> [  239.616831]  #2: 00007800a7de7ac0 (&sb->s_type->i_mutex_key#12){+.+.}-{3:3}, at: vfs_unlink+0xc6/0x760
> [  239.616860]  #3: 00007800a7de6a58 (&simple_offset_lock_class){+.+.}-{2:2}, at: mtree_erase+0xb4/0xf0
> [  239.616886] Last Breaking-Event-Address:
> [  239.616895]  [<00007fffe2b6c12a>] mas_pop_node+0x3a/0x290
> [  239.616909] irq event stamp: 5205821
> [  239.616918] hardirqs last  enabled at (5205831): [<00007fffe03d2be8>] __up_console_sem+0xe8/0x130
> [  239.616931] hardirqs last disabled at (5205840): [<00007fffe03d2bc6>] __up_console_sem+0xc6/0x130
> [  239.616943] softirqs last  enabled at (5200824): [<00007fffe0246b6c>] handle_softirqs+0x6dc/0xe30
> [  239.616955] softirqs last disabled at (5200687): [<00007fffe024508a>] __irq_exit_rcu+0x34a/0x3f0
> [  239.616994] ---[ end trace 0000000000000000 ]---
> [  239.617009] Unable to handle kernel pointer dereference in virtual kernel address space
> [  239.617019] Failing address: 0000000000000000 TEID: 0000000000000483
> [  239.617029] Fault in home space mode while using kernel ASCE.
> [  239.617049] AS:0000000005dac00b R2:00000001ffffc00b R3:00000001ffff8007 S:00000001ffff7801 P:000000000000013d
> [  239.617150] Oops: 0004 ilc:3 [#1] PREEMPT SMP
> [  239.617162] Modules linked in:
> [  239.617170] CPU: 0 UID: 0 PID: 669 Comm: linkat02 Tainted: G        W           6.14.0-rc5-next-20250307 #29
> [  239.617243] Tainted: [W]=WARN
> [  239.617248] Hardware name: IBM 3931 A01 704 (KVM/Linux)
> [  239.617253] Krnl PSW : 0704c00180000000 00007fffe2b6a988 (mab_mas_cp+0x168/0x640)
> [  239.617264]            R:0 T:1 IO:1 EX:1 Key:0 M:1 W:0 P:0 AS:3 CC:0 PM:0 RI:0 EA:3
> [  239.617272] Krnl GPRS: 0000000000000008 0000000000000000 00007fff00000008 00007f7f00000009
> [  239.617279]            0000000000000008 001c000000000000 0000000000000008 0000000000000048
> [  239.617285]            001c0ffffc638e09 001c000000000009 0000000000000098 001c000000000000
> [  239.617292]            0000000001026838 00007f7fe1aaf608 001c000000000013 00007f7fe1aaef68
> [  239.617302] Krnl Code: 00007fffe2b6a97c: b90800e5            agr     %r14,%r5
> [  239.617302]            00007fffe2b6a980: 9500e000            cli     0(%r14),0
> [  239.617302]           #00007fffe2b6a984: a7740262            brc     7,00007fffe2b6ae48
> [  239.617302]           >00007fffe2b6a988: e548a0000000        mvghi   0(%r10),0
> [  239.617302]            00007fffe2b6a98e: e3a0f0c00004        lg      %r10,192(%r15)
> [  239.617302]            00007fffe2b6a994: a7b80000            lhi     %r11,0
> [  239.617302]            00007fffe2b6a998: eb2a0003000d        sllg    %r2,%r10,3
> [  239.617302]            00007fffe2b6a99e: e320f0f00024        stg     %r2,240(%r15)
> [  239.617350] Call Trace:
> [  239.617354]  [<00007fffe2b6a988>] mab_mas_cp+0x168/0x640
> [  239.617362]  [<00007fffe2b85bcc>] mas_spanning_rebalance+0x311c/0x4e90
> [  239.617369]  [<00007fffe2b87e7a>] mas_rebalance+0x53a/0x9c0
> [  239.617376]  [<00007fffe2b8c10a>] mas_wr_bnode+0x14a/0x1a0
> [  239.617383]  [<00007fffe2b9a87c>] mas_erase+0xd9c/0x1120
> [  239.617389]  [<00007fffe2b9acbe>] mtree_erase+0xbe/0xf0
> [  239.617396]  [<00007fffe0c3b4d2>] simple_offset_remove+0x52/0x90
> [  239.617403]  [<00007fffe093dc16>] shmem_unlink+0xb6/0x320
> [  239.617410]  [<00007fffe0bc0830>] vfs_unlink+0x270/0x760
> [  239.617416]  [<00007fffe0bd473a>] do_unlinkat+0x40a/0x5c0
> [  239.617422]  [<00007fffe0bd4a48>] __s390x_sys_unlink+0x58/0x70
> [  239.617429]  [<00007fffe0155356>] do_syscall+0x2f6/0x430
> [  239.617436]  [<00007fffe2bd3668>] __do_syscall+0xc8/0x1c0
> [  239.617443]  [<00007fffe2bf70d4>] system_call+0x74/0x98
> [  239.617450] INFO: lockdep is turned off.
> [  239.617454] Last Breaking-Event-Address:
> [  239.617458]  [<00007fffe2b6a8f4>] mab_mas_cp+0xd4/0x640
> [  239.617468] Kernel panic - not syncing: Fatal exception: panic_on_oops
> 

Re: [PATCH v3 5/6] maple_tree: add sufficient height

[Vasily Gorbik]

[-- Attachment #1: Type: text/plain, Size: 816 bytes --]

On Tue, Mar 11, 2025 at 10:40:17AM -0400, Sidhartha Kumar wrote:
> Would you be able to rerun this test with the following diff applied and
> CONFIG_DEBUG_MAPLE_TREE=y so I can check the state of the tree to easier
> reproduce the error?
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index ea1f0acac118..74a4b1924a55 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1153,8 +1153,11 @@ static inline struct maple_node *mas_pop_node(struct
> ma_state *mas)
>         unsigned int req = mas_alloc_req(mas);
> 
>         /* nothing or a request pending. */
> -       if (WARN_ON(!total))
> +       if (WARN_ON(!total)) {
> +               mas_dump(mas);
> +               mt_dump(mas->tree, mt_dump_hex);
>                 return NULL;
> +       }

Sure, please find vmcore-dmesg.txt.xz attached

[-- Attachment #2: vmcore-dmesg.txt.xz --]
[-- Type: application/x-xz, Size: 508568 bytes --]