[PATCH Fix 0/2] Underflow in mas_spanning_rebalance() and test

[PATCH Fix 0/2] Underflow in mas_spanning_rebalance() and test

[Liam Howlett]

Fixes the bug found by Yu Zhao running stress-ng on a large system
(512gb of ram).

Patches against mm-unstable.

Liam R. Howlett (2):
  maple_tree: Fix underflow in mas_spanning_rebalance()
  test_maple_tree: Add test for spanning store of entire range.

 lib/maple_tree.c      |  6 ++++--
 lib/test_maple_tree.c | 13 +++++++++++++
 2 files changed, 17 insertions(+), 2 deletions(-)

-- 
2.35.1

[PATCH Fix 1/2] maple_tree: Fix underflow in mas_spanning_rebalance()

[Liam Howlett]

When rebalancing a spanning store that spans the entire address space,
the big node end is not expanded the extra position that
mas_spanning_rebalance() expects.  Fix this by expanding on such cases.
Also change mab_mas_cp() from assuming there are at least two entries to
ensure the correct metadata is written.

Fixes: f8acc5e9581e (Maple Tree: add new data structure)
Reported-by: Yu Zhao <yuzhao@google.com>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index a968948b3e3e..d8457122ca5d 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1977,7 +1977,6 @@ static inline void mab_mas_cp(struct maple_big_node *b_node,
 		slots[mt_pivots[mt]] = NULL;
 
 	i = mab_start;
-	pivots[j++] = b_node->pivot[i++];
 	do {
 		pivots[j++] = b_node->pivot[i++];
 	} while (i <= mab_end && likely(b_node->pivot[i]));
@@ -2970,7 +2969,7 @@ static int mas_spanning_rebalance(struct ma_state *mas,
 	mast->free = &free;
 	mast->destroy = &destroy;
 	l_mas.node = r_mas.node = m_mas.node = MAS_NONE;
-	if (!mas_is_root_limits(mast->orig_l) &&
+	if (!(mast->orig_l->min && mast->orig_r->max == ULONG_MAX) &&
 	    unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
 		mast_spanning_rebalance(mast);
 
@@ -4004,6 +4003,9 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
 	if (r_mas.offset <= r_wr_mas.node_end)
 		mas_mab_cp(&r_mas, r_mas.offset, r_wr_mas.node_end,
 			   &b_node, b_node.b_end + 1);
+	else
+		b_node.b_end++;
+
 	/* Stop spanning searches by searching for just index. */
 	l_mas.index = l_mas.last = mas->index;
 
-- 
2.35.1

[PATCH Fix 2/2] test_maple_tree: Add test for spanning store of entire range.

[Liam Howlett]

Entire range store over an existing tree would cause an underflow in
mas_spanning_store() when the tree is multiple levels.  Add a testcase
to ensure it doesn't happen again.

Fixes: 51282228cdd4 (lib/test_maple_tree: add testing for maple tree)
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/test_maple_tree.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 9fc0618f4ae7..8de5705b7b9b 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -35676,6 +35676,19 @@ static noinline void check_spanning_write(struct maple_tree *mt)
 	mtree_unlock(mt);
 	mtree_destroy(mt);
 
+	for (i = 1; i <= max; i++)
+		mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
+
+	mtree_lock(mt);
+	mas_set_range(&mas, 9, 50006); /* Will expand to 0 - ULONG_MAX */
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	mas_set(&mas, 1205);
+	MT_BUG_ON(mt, mas_walk(&mas) != NULL);
+	mtree_unlock(mt);
+	mt_dump(mt);
+	mt_validate(mt);
+	mtree_destroy(mt);
+
 	/* Test spanning store that requires a right cousin rebalance */
 	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 	for (i = 0; i <= max; i++)
-- 
2.35.1