[v2,hotfix,6.12,2/2] maple_tree: add regression test for spanning store bug

Commit Message

Lorenzo Stoakes Oct. 6, 2024, 2:31 p.m. UTC

Add a regression test to assert that, when performing a spanning store
which consumes the entirety of the rightmost right leaf node does not
result in maple tree corruption when doing so.

This achieves this by building a test tree of 3 levels and establishing a
store which ultimately results in a spanned store of this nature.

Signed-off-by: Lorenzo Stoakes <[e-mail]>
---
 tools/testing/radix-tree/maple.c | 84 ++++++++++++++++++++++++++++++++
 1 file changed, 84 insertions(+)

--
2.46.2

Comments

Vlastimil Babka Oct. 7, 2024, 12:15 p.m. UTC | #1

On 10/6/24 4:31 PM, Lorenzo Stoakes wrote:
> Add a regression test to assert that, when performing a spanning store
> which consumes the entirety of the rightmost right leaf node does not
> result in maple tree corruption when doing so.
> 
> This achieves this by building a test tree of 3 levels and establishing a
> store which ultimately results in a spanned store of this nature.
> 
> Signed-off-by: Lorenzo Stoakes <[e-mail]>

Acked-by: Vlastimil Babka <[e-mail]>

> ---
>  tools/testing/radix-tree/maple.c | 84 ++++++++++++++++++++++++++++++++
>  1 file changed, 84 insertions(+)
> 
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index 1873ddbe16cc..5fde09999be4 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -36406,9 +36406,93 @@ void farmer_tests(void)
>  	check_nomem(&tree);
>  }
> 
> +static unsigned long get_last_index(struct ma_state *mas)
> +{
> +	struct maple_node *node = mas_mn(mas);
> +	enum maple_type mt = mte_node_type(mas->node);
> +	unsigned long *pivots = ma_pivots(node, mt);
> +	unsigned long last_index = mas_data_end(mas);
> +
> +	BUG_ON(last_index == 0);
> +
> +	return pivots[last_index - 1] + 1;
> +}
> +
> +/*
> + * Assert that we handle spanning stores that consume the entirety of the right
> + * leaf node correctly.
> + */
> +static void test_spanning_store_regression(void)
> +{
> +	unsigned long from = 0, to = 0;
> +	DEFINE_MTREE(tree);
> +	MA_STATE(mas, &tree, 0, 0);
> +
> +	/*
> +	 * Build a 3-level tree. We require a parent node below the root node
> +	 * and 2 leaf nodes under it, so we can span the entirety of the right
> +	 * hand node.
> +	 */
> +	build_full_tree(&tree, 0, 3);
> +
> +	/* Descend into position at depth 2. */
> +	mas_reset(&mas);
> +	mas_start(&mas);
> +	mas_descend(&mas);
> +	mas_descend(&mas);
> +
> +	/*
> +	 * We need to establish a tree like the below.
> +	 *
> +	 * Then we can try a store in [from, to] which results in a spanned
> +	 * store across nodes B and C, with the maple state at the time of the
> +	 * write being such that only the subtree at A and below is considered.
> +	 *
> +	 * Height
> +	 *  0                              Root Node
> +	 *                                  /      \
> +	 *                    pivot = to   /        \ pivot = ULONG_MAX
> +	 *                                /          \
> +	 *   1                       A [-----]       ...
> +	 *                              /   \
> +	 *                pivot = from /     \ pivot = to
> +	 *                            /       \
> +	 *   2 (LEAVES)          B [-----]  [-----] C
> +	 *                                       ^--- Last pivot to.
> +	 */
> +	while (true) {
> +		unsigned long tmp = get_last_index(&mas);
> +
> +		if (mas_next_sibling(&mas)) {
> +			from = tmp;
> +			to = mas.max;
> +		} else {
> +			break;
> +		}
> +	}
> +
> +	BUG_ON(from == 0 && to == 0);
> +
> +	/* Perform the store. */
> +	mas_set_range(&mas, from, to);
> +	mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL);
> +
> +	/* If the regression occurs, the validation will fail. */
> +	mt_validate(&tree);
> +
> +	/* Cleanup. */
> +	__mt_destroy(&tree);
> +}
> +
> +static void regression_tests(void)
> +{
> +	test_spanning_store_regression();
> +}
> +
>  void maple_tree_tests(void)
>  {
>  #if !defined(BENCH)
> +	regression_tests();
>  	farmer_tests();
>  #endif
>  	maple_tree_seed();
> --
> 2.46.2

Patch

diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 1873ddbe16cc..5fde09999be4 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -36406,9 +36406,93 @@  void farmer_tests(void)
 	check_nomem(&tree);
 }

+static unsigned long get_last_index(struct ma_state *mas)
+{
+	struct maple_node *node = mas_mn(mas);
+	enum maple_type mt = mte_node_type(mas->node);
+	unsigned long *pivots = ma_pivots(node, mt);
+	unsigned long last_index = mas_data_end(mas);
+
+	BUG_ON(last_index == 0);
+
+	return pivots[last_index - 1] + 1;
+}
+
+/*
+ * Assert that we handle spanning stores that consume the entirety of the right
+ * leaf node correctly.
+ */
+static void test_spanning_store_regression(void)
+{
+	unsigned long from = 0, to = 0;
+	DEFINE_MTREE(tree);
+	MA_STATE(mas, &tree, 0, 0);
+
+	/*
+	 * Build a 3-level tree. We require a parent node below the root node
+	 * and 2 leaf nodes under it, so we can span the entirety of the right
+	 * hand node.
+	 */
+	build_full_tree(&tree, 0, 3);
+
+	/* Descend into position at depth 2. */
+	mas_reset(&mas);
+	mas_start(&mas);
+	mas_descend(&mas);
+	mas_descend(&mas);
+
+	/*
+	 * We need to establish a tree like the below.
+	 *
+	 * Then we can try a store in [from, to] which results in a spanned
+	 * store across nodes B and C, with the maple state at the time of the
+	 * write being such that only the subtree at A and below is considered.
+	 *
+	 * Height
+	 *  0                              Root Node
+	 *                                  /      \
+	 *                    pivot = to   /        \ pivot = ULONG_MAX
+	 *                                /          \
+	 *   1                       A [-----]       ...
+	 *                              /   \
+	 *                pivot = from /     \ pivot = to
+	 *                            /       \
+	 *   2 (LEAVES)          B [-----]  [-----] C
+	 *                                       ^--- Last pivot to.
+	 */
+	while (true) {
+		unsigned long tmp = get_last_index(&mas);
+
+		if (mas_next_sibling(&mas)) {
+			from = tmp;
+			to = mas.max;
+		} else {
+			break;
+		}
+	}
+
+	BUG_ON(from == 0 && to == 0);
+
+	/* Perform the store. */
+	mas_set_range(&mas, from, to);
+	mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL);
+
+	/* If the regression occurs, the validation will fail. */
+	mt_validate(&tree);
+
+	/* Cleanup. */
+	__mt_destroy(&tree);
+}
+
+static void regression_tests(void)
+{
+	test_spanning_store_regression();
+}
+
 void maple_tree_tests(void)
 {
 #if !defined(BENCH)
+	regression_tests();
 	farmer_tests();
 #endif
 	maple_tree_seed();