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 <lorenzo.stoakes@oracle.com>
Acked-by: Vlastimil Babka <vbabka@suse.cz>
---
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.2On Mon, Oct 07, 2024 at 04:28:33PM +0100, 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 <lorenzo.stoakes@oracle.com> >Acked-by: Vlastimil Babka <vbabka@suse.cz> Reviewed-by: Wei Yang <richard.weiyang@gmail.com> -- Wei Yang Help you, Help me
* Lorenzo Stoakes <lorenzo.stoakes@oracle.com> [241007 11:28]:
> 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 <lorenzo.stoakes@oracle.com>
> Acked-by: Vlastimil Babka <vbabka@suse.cz>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
> ---
> 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
© 2016 - 2024 Red Hat, Inc.