[PATCH Fix 0/2] Null expansion bug

[PATCH Fix 0/2] Null expansion bug

[Liam Howlett]

Andrew,

Please apply these two fixes to v9 of the maple tree.

The first should be applied to [01/69] "Maple Tree: add new data
structure" to fix the bug.

The second should be applied to [07/69] "lib/test_maple_tree: add
testing for maple tree" to test for the bug in the future.

Thanks,
Liam

*** BLURB HERE ***

Liam R. Howlett (2):
  maple_tree: Fix expanding null off the end of the data.
  test_maple_tree: Add null expansion tests

 lib/maple_tree.c      |  8 ++-----
 lib/test_maple_tree.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+), 6 deletions(-)

-- 
2.35.1

[PATCH Fix 1/2] maple_tree: Fix expanding null off the end of the data.

[Liam Howlett]

When expanding a write of null to another null, the metadata for the end
of the node may be off by one.  Fix this issue by setting the write end
pivot (wr_mas->end_piv) in mas_wr_extend_null().  Also use the saved
value for the end pivot during node stores instead of looking up the
same entry again.

There is also unnecessary code in mas_wr_extend_null() that can be
dropped.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index c7b7a10b15d5..967631055210 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3981,8 +3981,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
 
 		new_end++;
 	} else {
-		if (mas_safe_pivot(mas, wr_mas->pivots, wr_mas->offset_end,
-				   wr_mas->type) == mas->last)
+		if (wr_mas->end_piv == mas->last)
 			wr_mas->offset_end++;
 
 		new_end -= wr_mas->offset_end - offset - 1;
@@ -4146,10 +4145,7 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
 			mas->last = mas->max;
 		else
 			mas->last = wr_mas->pivots[wr_mas->offset_end];
-	} else if ((mas->last > wr_mas->end_piv) &&
-		   !wr_mas->slots[wr_mas->offset_end]) {
-		mas->last = wr_mas->end_piv;
-		wr_mas->offset_end++;
+		wr_mas->end_piv = mas->last;
 	}
 
 	if (!wr_mas->content) {
-- 
2.35.1

[PATCH Fix 2/2] test_maple_tree: Add null expansion tests

[Liam Howlett]

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/test_maple_tree.c | 55 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 7c377b6e0905..8277464e182c 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -35537,6 +35537,57 @@ static noinline void check_root_expand(struct maple_tree *mt)
 	mas_unlock(&mas);
 }
 
+static noinline void check_null_expand(struct maple_tree *mt)
+{
+	unsigned long i, max = 100;
+	unsigned char data_end;
+	MA_STATE(mas, mt, 959, 959);
+
+	for (i = 0; i <= max; i++)
+		mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
+	/* Test expanding null at start. */
+	mas_walk(&mas);
+	data_end = mas_data_end(&mas);
+	mas_set_range(&mas, 959, 963);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, mtree_load(mt, 963) != NULL);
+	MT_BUG_ON(mt, data_end != mas_data_end(&mas));
+
+	/* Test expanding null at end. */
+	mas_set(&mas, 880);
+	mas_walk(&mas);
+	data_end = mas_data_end(&mas);
+	mas_set_range(&mas, 884, 887);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, mtree_load(mt, 884) != NULL);
+	MT_BUG_ON(mt, mtree_load(mt, 889) != NULL);
+	MT_BUG_ON(mt, data_end != mas_data_end(&mas));
+
+	/* Test expanding null at start and end. */
+	mas_set(&mas, 890);
+	mas_walk(&mas);
+	data_end = mas_data_end(&mas);
+	mas_set_range(&mas, 900, 905);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, mtree_load(mt, 899) != NULL);
+	MT_BUG_ON(mt, mtree_load(mt, 900) != NULL);
+	MT_BUG_ON(mt, mtree_load(mt, 905) != NULL);
+	MT_BUG_ON(mt, mtree_load(mt, 906) != NULL);
+	MT_BUG_ON(mt, data_end - 2 != mas_data_end(&mas));
+
+	/* Test expanding null across multiple slots. */
+	mas_set(&mas, 800);
+	mas_walk(&mas);
+	data_end = mas_data_end(&mas);
+	mas_set_range(&mas, 810, 825);
+	mas_store_gfp(&mas, NULL, GFP_KERNEL);
+	MT_BUG_ON(mt, mtree_load(mt, 809) != NULL);
+	MT_BUG_ON(mt, mtree_load(mt, 810) != NULL);
+	MT_BUG_ON(mt, mtree_load(mt, 825) != NULL);
+	MT_BUG_ON(mt, mtree_load(mt, 826) != NULL);
+	MT_BUG_ON(mt, data_end - 4 != mas_data_end(&mas));
+}
+
 static noinline void check_gap_combining(struct maple_tree *mt)
 {
 	struct maple_enode *mn1, *mn2;
@@ -37627,6 +37678,10 @@ static int maple_tree_seed(void)
 	check_new_node(&tree);
 	mtree_destroy(&tree);
 
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	check_null_expand(&tree);
+	mtree_destroy(&tree);
+
 	mt_init_flags(&tree, 0);
 	check_dfs_preorder(&tree);
 	mtree_destroy(&tree);
-- 
2.35.1