[PATCH hotfix 6.12 v3 0/2] maple_tree: correct tree corruption on spanning store

[PATCH hotfix 6.12 v3 0/2] maple_tree: correct tree corruption on spanning store

[Lorenzo Stoakes]

There has been a nasty yet subtle maple tree corruption bug that appears to
have been in existence since the inception of the algorithm.

This bug seems far more likely to happen since commit f8d112a4e657
("mm/mmap: avoid zeroing vma tree in mmap_region()"), which is the point at
which reports started to be submitted concerning this bug.

We were made definitely aware of the bug thanks to the kind efforts of Bert
Karwatzki who helped enormously in my being able to track this down and
identify the cause of it.

The bug arises when an attempt is made to perform a spanning store across
two leaf nodes, where the right leaf node is the rightmost child of the
shared parent, AND the store completely consumes the right-mode node.

This results in mas_wr_spanning_store() mitakenly duplicating the new and
existing entries at the maximum pivot within the range, and thus maple tree
corruption.

The fix patch corrects this by detecting this scenario and disallowing the
mistaken duplicate copy.

The fix patch commit message goes into great detail as to how this occurs.

This series also includes a test which reliably reproduces the issue, and
asserts that the fix works correctly.

Bert has kindly tested the fix and confirmed it resolved his issues. Also
Mikhail Gavrilov kindly reported what appears to be precisely the same bug,
which this fix should also resolve.

Please note - I am intentionally holding off on cc'ing stable until we've
had a chance to be satisfied the series has stabilised in 6.12 as this is a
highly subtle change.

v3:
* Significantly simplify the solution to a one-liner as suggested by Liam.
* Eliminate incorrect boolean return type in mas_wr_walk_index().

v2:
* Majorly improve clarity of commit message describing the problem.
* Add a reproducable test.
* Add missing maple tree mailing list to cc- list.
https://lore.kernel.org/linux-mm/cover.1728223996.git.lorenzo.stoakes@oracle.com/

v1:
https://lore.kernel.org/linux-mm/20241005064114.42770-1-lorenzo.stoakes@oracle.com/

Lorenzo Stoakes (2):
  maple_tree: correct tree corruption on spanning store
  maple_tree: add regression test for spanning store bug

 lib/maple_tree.c                 | 12 ++---
 tools/testing/radix-tree/maple.c | 84 ++++++++++++++++++++++++++++++++
 2 files changed, 90 insertions(+), 6 deletions(-)

--
2.46.2

[PATCH hotfix 6.12 v3 1/2] maple_tree: correct tree corruption on spanning store

[Lorenzo Stoakes]

There has been a subtle bug present in the maple tree implementation from
its inception.

This arises from how stores are performed - when a store occurs, it will
overwrite overlapping ranges and adjust the tree as necessary to
accommodate this.

A range may always ultimately span two leaf nodes. In this instance we walk
the two leaf nodes, determine which elements are not overwritten to the
left and to the right of the start and end of the ranges respectively and
then rebalance the tree to contain these entries and the newly inserted
one.

This kind of store is dubbed a 'spanning store' and is implemented by
mas_wr_spanning_store().

In order to reach this stage, mas_store_gfp() invokes mas_wr_preallocate(),
mas_wr_store_type() and mas_wr_walk() in turn to walk the tree and update
the object (mas) to traverse to the location where the write should be
performed, determining its store type.

When a spanning store is required, this function returns false stopping at
the parent node which contains the target range, and mas_wr_store_type()
marks the mas->store_type as wr_spanning_store to denote this fact.

When we go to perform the store in mas_wr_spanning_store(), we first
determine the elements AFTER the END of the range we wish to store (that
is, to the right of the entry to be inserted) - we do this by walking to
the NEXT pivot in the tree (i.e. r_mas.last + 1), starting at the node we
have just determined contains the range over which we intend to write.

We then turn our attention to the entries to the left of the entry we are
inserting, whose state is represented by l_mas, and copy these into a 'big
node', which is a special node which contains enough slots to contain two
leaf node's worth of data.

We then copy the entry we wish to store immediately after this - the copy
and the insertion of the new entry is performed by mas_store_b_node().

After this we copy the elements to the right of the end of the range which
we are inserting, if we have not exceeded the length of the node
(i.e. r_mas.offset <= r_mas.end).

Herein lies the bug - under very specific circumstances, this logic can
break and corrupt the maple tree.

Consider the following tree:

Height
  0                             Root Node
                                 /      \
                 pivot = 0xffff /        \ pivot = ULONG_MAX
                               /          \
  1                       A [-----]       ...
                             /   \
             pivot = 0x4fff /     \ pivot = 0xffff
                           /       \
  2 (LEAVES)          B [-----]  [-----] C
                                      ^--- Last pivot 0xffff.

Now imagine we wish to store an entry in the range [0x4000, 0xffff] (note
that all ranges expressed in maple tree code are inclusive):

1. mas_store_gfp() descends the tree, finds node A at <=0xffff, then
   determines that this is a spanning store across nodes B and C. The mas
   state is set such that the current node from which we traverse further
   is node A.

2. In mas_wr_spanning_store() we try to find elements to the right of pivot
   0xffff by searching for an index of 0x10000:

    - mas_wr_walk_index() invokes mas_wr_walk_descend() and
      mas_wr_node_walk() in turn.

        - mas_wr_node_walk() loops over entries in node A until EITHER it
          finds an entry whose pivot equals or exceeds 0x10000 OR it
          reaches the final entry.

        - Since no entry has a pivot equal to or exceeding 0x10000, pivot
          0xffff is selected, leading to node C.

    - mas_wr_walk_traverse() resets the mas state to traverse node C. We
      loop around and invoke mas_wr_walk_descend() and mas_wr_node_walk()
      in turn once again.

         - Again, we reach the last entry in node C, which has a pivot of
           0xffff.

3. We then copy the elements to the left of 0x4000 in node B to the big
   node via mas_store_b_node(), and insert the new [0x4000, 0xffff] entry
   too.

4. We determine whether we have any entries to copy from the right of the
   end of the range via - and with r_mas set up at the entry at pivot
   0xffff, r_mas.offset <= r_mas.end, and then we DUPLICATE the entry at
   pivot 0xffff.

5. BUG! The maple tree is corrupted with a duplicate entry.

This requires a very specific set of circumstances - we must be spanning
the last element in a leaf node, which is the last element in the parent
node.

spanning store across two leaf nodes with a range that ends at that shared
pivot.

A potential solution to this problem would simply be to reset the walk each
time we traverse r_mas, however given the rarity of this situation it seems
that would be rather inefficient.

Instead, this patch detects if the right hand node is populated, i.e. has
anything we need to copy.

We do so by only copying elements from the right of the entry being inserted
when the maximum value present exceeds the last, rather than basing this on
offset position.

The patch also updates some comments and eliminates the unused bool return
value in mas_wr_walk_index().

The work performed in commit f8d112a4e657 ("mm/mmap: avoid zeroing vma tree
in mmap_region()") seems to have made the probability of this event much
more likely, which is the point at which reports started to be submitted
concerning this bug.

The motivation for this change arose from Bert Karwatzki's report of
encountering mm instability after the release of kernel v6.12-rc1 which,
after the use of CONFIG_DEBUG_VM_MAPLE_TREE and similar configuration
options, was identified as maple tree corruption.

After Bert very generously provided his time and ability to reproduce this
event consistently, I was able to finally identify that the issue discussed
in this commit message was occurring for him.

Reported-and-tested-by: Bert Karwatzki <spasswolf@web.de>
Closes: https://lore.kernel.org/all/20241001023402.3374-1-spasswolf@web.de/
Reported-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
Closes: https://lore.kernel.org/all/CABXGCsOPwuoNOqSMmAvWO2Fz4TEmPnjFj-b7iF+XFRu1h7-+Dg@mail.gmail.com/
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
Acked-by: Vlastimil Babka <vbabka@suse.cz>
---
 lib/maple_tree.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 20990ecba2dd..2fe59c534328 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2196,6 +2196,8 @@ static inline void mas_node_or_none(struct ma_state *mas,

 /*
  * mas_wr_node_walk() - Find the correct offset for the index in the @mas.
+ *                      If @mas->index cannot be found within the containing
+ *                      node, we traverse to the last entry in the node.
  * @wr_mas: The maple write state
  *
  * Uses mas_slot_locked() and does not need to worry about dead nodes.
@@ -3532,7 +3534,7 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas)
 	return true;
 }

-static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
+static void mas_wr_walk_index(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;

@@ -3541,11 +3543,9 @@ static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
 		wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
 						  mas->offset);
 		if (ma_is_leaf(wr_mas->type))
-			return true;
+			return;
 		mas_wr_walk_traverse(wr_mas);
-
 	}
-	return true;
 }
 /*
  * mas_extend_spanning_null() - Extend a store of a %NULL to include surrounding %NULLs.
@@ -3765,8 +3765,8 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
 	memset(&b_node, 0, sizeof(struct maple_big_node));
 	/* Copy l_mas and store the value in b_node. */
 	mas_store_b_node(&l_wr_mas, &b_node, l_mas.end);
-	/* Copy r_mas into b_node. */
-	if (r_mas.offset <= r_mas.end)
+	/* Copy r_mas into b_node if there is anything to copy. */
+	if (r_mas.max > r_mas.last)
 		mas_mab_cp(&r_mas, r_mas.offset, r_mas.end,
 			   &b_node, b_node.b_end + 1);
 	else
--
2.46.2

[PATCH hotfix 6.12 v3 2/2] maple_tree: add regression test for spanning store bug

[Lorenzo Stoakes]

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

Re: [PATCH hotfix 6.12 v3 1/2] maple_tree: correct tree corruption on spanning store

[Liam R. Howlett]

* Lorenzo Stoakes <lorenzo.stoakes@oracle.com> [241007 11:28]:
> There has been a subtle bug present in the maple tree implementation from
> its inception.
> 
> This arises from how stores are performed - when a store occurs, it will
> overwrite overlapping ranges and adjust the tree as necessary to
> accommodate this.
> 
> A range may always ultimately span two leaf nodes. In this instance we walk
> the two leaf nodes, determine which elements are not overwritten to the
> left and to the right of the start and end of the ranges respectively and
> then rebalance the tree to contain these entries and the newly inserted
> one.
> 
> This kind of store is dubbed a 'spanning store' and is implemented by
> mas_wr_spanning_store().
> 
> In order to reach this stage, mas_store_gfp() invokes mas_wr_preallocate(),
> mas_wr_store_type() and mas_wr_walk() in turn to walk the tree and update
> the object (mas) to traverse to the location where the write should be
> performed, determining its store type.
> 
> When a spanning store is required, this function returns false stopping at
> the parent node which contains the target range, and mas_wr_store_type()
> marks the mas->store_type as wr_spanning_store to denote this fact.
> 
> When we go to perform the store in mas_wr_spanning_store(), we first
> determine the elements AFTER the END of the range we wish to store (that
> is, to the right of the entry to be inserted) - we do this by walking to
> the NEXT pivot in the tree (i.e. r_mas.last + 1), starting at the node we
> have just determined contains the range over which we intend to write.
> 
> We then turn our attention to the entries to the left of the entry we are
> inserting, whose state is represented by l_mas, and copy these into a 'big
> node', which is a special node which contains enough slots to contain two
> leaf node's worth of data.
> 
> We then copy the entry we wish to store immediately after this - the copy
> and the insertion of the new entry is performed by mas_store_b_node().
> 
> After this we copy the elements to the right of the end of the range which
> we are inserting, if we have not exceeded the length of the node
> (i.e. r_mas.offset <= r_mas.end).
> 
> Herein lies the bug - under very specific circumstances, this logic can
> break and corrupt the maple tree.
> 
> Consider the following tree:
> 
> Height
>   0                             Root Node
>                                  /      \
>                  pivot = 0xffff /        \ pivot = ULONG_MAX
>                                /          \
>   1                       A [-----]       ...
>                              /   \
>              pivot = 0x4fff /     \ pivot = 0xffff
>                            /       \
>   2 (LEAVES)          B [-----]  [-----] C
>                                       ^--- Last pivot 0xffff.
> 
> Now imagine we wish to store an entry in the range [0x4000, 0xffff] (note
> that all ranges expressed in maple tree code are inclusive):
> 
> 1. mas_store_gfp() descends the tree, finds node A at <=0xffff, then
>    determines that this is a spanning store across nodes B and C. The mas
>    state is set such that the current node from which we traverse further
>    is node A.
> 
> 2. In mas_wr_spanning_store() we try to find elements to the right of pivot
>    0xffff by searching for an index of 0x10000:
> 
>     - mas_wr_walk_index() invokes mas_wr_walk_descend() and
>       mas_wr_node_walk() in turn.
> 
>         - mas_wr_node_walk() loops over entries in node A until EITHER it
>           finds an entry whose pivot equals or exceeds 0x10000 OR it
>           reaches the final entry.
> 
>         - Since no entry has a pivot equal to or exceeding 0x10000, pivot
>           0xffff is selected, leading to node C.
> 
>     - mas_wr_walk_traverse() resets the mas state to traverse node C. We
>       loop around and invoke mas_wr_walk_descend() and mas_wr_node_walk()
>       in turn once again.
> 
>          - Again, we reach the last entry in node C, which has a pivot of
>            0xffff.
> 
> 3. We then copy the elements to the left of 0x4000 in node B to the big
>    node via mas_store_b_node(), and insert the new [0x4000, 0xffff] entry
>    too.
> 
> 4. We determine whether we have any entries to copy from the right of the
>    end of the range via - and with r_mas set up at the entry at pivot
>    0xffff, r_mas.offset <= r_mas.end, and then we DUPLICATE the entry at
>    pivot 0xffff.
> 
> 5. BUG! The maple tree is corrupted with a duplicate entry.
> 
> This requires a very specific set of circumstances - we must be spanning
> the last element in a leaf node, which is the last element in the parent
> node.
> 
> spanning store across two leaf nodes with a range that ends at that shared
> pivot.
> 
> A potential solution to this problem would simply be to reset the walk each
> time we traverse r_mas, however given the rarity of this situation it seems
> that would be rather inefficient.
> 
> Instead, this patch detects if the right hand node is populated, i.e. has
> anything we need to copy.
> 
> We do so by only copying elements from the right of the entry being inserted
> when the maximum value present exceeds the last, rather than basing this on
> offset position.
> 
> The patch also updates some comments and eliminates the unused bool return
> value in mas_wr_walk_index().
> 
> The work performed in commit f8d112a4e657 ("mm/mmap: avoid zeroing vma tree
> in mmap_region()") seems to have made the probability of this event much
> more likely, which is the point at which reports started to be submitted
> concerning this bug.
> 
> The motivation for this change arose from Bert Karwatzki's report of
> encountering mm instability after the release of kernel v6.12-rc1 which,
> after the use of CONFIG_DEBUG_VM_MAPLE_TREE and similar configuration
> options, was identified as maple tree corruption.
> 
> After Bert very generously provided his time and ability to reproduce this
> event consistently, I was able to finally identify that the issue discussed
> in this commit message was occurring for him.
> 
> Reported-and-tested-by: Bert Karwatzki <spasswolf@web.de>
> Closes: https://lore.kernel.org/all/20241001023402.3374-1-spasswolf@web.de/
> Reported-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
> Closes: https://lore.kernel.org/all/CABXGCsOPwuoNOqSMmAvWO2Fz4TEmPnjFj-b7iF+XFRu1h7-+Dg@mail.gmail.com/
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> 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>

> ---
>  lib/maple_tree.c | 12 ++++++------
>  1 file changed, 6 insertions(+), 6 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 20990ecba2dd..2fe59c534328 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -2196,6 +2196,8 @@ static inline void mas_node_or_none(struct ma_state *mas,
> 
>  /*
>   * mas_wr_node_walk() - Find the correct offset for the index in the @mas.
> + *                      If @mas->index cannot be found within the containing
> + *                      node, we traverse to the last entry in the node.
>   * @wr_mas: The maple write state
>   *
>   * Uses mas_slot_locked() and does not need to worry about dead nodes.
> @@ -3532,7 +3534,7 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas)
>  	return true;
>  }
> 
> -static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
> +static void mas_wr_walk_index(struct ma_wr_state *wr_mas)
>  {
>  	struct ma_state *mas = wr_mas->mas;
> 
> @@ -3541,11 +3543,9 @@ static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
>  		wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
>  						  mas->offset);
>  		if (ma_is_leaf(wr_mas->type))
> -			return true;
> +			return;
>  		mas_wr_walk_traverse(wr_mas);
> -
>  	}
> -	return true;
>  }
>  /*
>   * mas_extend_spanning_null() - Extend a store of a %NULL to include surrounding %NULLs.
> @@ -3765,8 +3765,8 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
>  	memset(&b_node, 0, sizeof(struct maple_big_node));
>  	/* Copy l_mas and store the value in b_node. */
>  	mas_store_b_node(&l_wr_mas, &b_node, l_mas.end);
> -	/* Copy r_mas into b_node. */
> -	if (r_mas.offset <= r_mas.end)
> +	/* Copy r_mas into b_node if there is anything to copy. */
> +	if (r_mas.max > r_mas.last)
>  		mas_mab_cp(&r_mas, r_mas.offset, r_mas.end,
>  			   &b_node, b_node.b_end + 1);
>  	else
> --
> 2.46.2

Re: [PATCH hotfix 6.12 v3 2/2] maple_tree: add regression test for spanning store bug

[Liam R. Howlett]

* 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

Re: [PATCH hotfix 6.12 v3 1/2] maple_tree: correct tree corruption on spanning store

[Mikhail Gavrilov]

On Mon, Oct 7, 2024 at 8:28 PM Lorenzo Stoakes
<lorenzo.stoakes@oracle.com> wrote:
>
> There has been a subtle bug present in the maple tree implementation from
> its inception.
>
> This arises from how stores are performed - when a store occurs, it will
> overwrite overlapping ranges and adjust the tree as necessary to
> accommodate this.
>
> A range may always ultimately span two leaf nodes. In this instance we walk
> the two leaf nodes, determine which elements are not overwritten to the
> left and to the right of the start and end of the ranges respectively and
> then rebalance the tree to contain these entries and the newly inserted
> one.
>
> This kind of store is dubbed a 'spanning store' and is implemented by
> mas_wr_spanning_store().
>
> In order to reach this stage, mas_store_gfp() invokes mas_wr_preallocate(),
> mas_wr_store_type() and mas_wr_walk() in turn to walk the tree and update
> the object (mas) to traverse to the location where the write should be
> performed, determining its store type.
>
> When a spanning store is required, this function returns false stopping at
> the parent node which contains the target range, and mas_wr_store_type()
> marks the mas->store_type as wr_spanning_store to denote this fact.
>
> When we go to perform the store in mas_wr_spanning_store(), we first
> determine the elements AFTER the END of the range we wish to store (that
> is, to the right of the entry to be inserted) - we do this by walking to
> the NEXT pivot in the tree (i.e. r_mas.last + 1), starting at the node we
> have just determined contains the range over which we intend to write.
>
> We then turn our attention to the entries to the left of the entry we are
> inserting, whose state is represented by l_mas, and copy these into a 'big
> node', which is a special node which contains enough slots to contain two
> leaf node's worth of data.
>
> We then copy the entry we wish to store immediately after this - the copy
> and the insertion of the new entry is performed by mas_store_b_node().
>
> After this we copy the elements to the right of the end of the range which
> we are inserting, if we have not exceeded the length of the node
> (i.e. r_mas.offset <= r_mas.end).
>
> Herein lies the bug - under very specific circumstances, this logic can
> break and corrupt the maple tree.
>
> Consider the following tree:
>
> Height
>   0                             Root Node
>                                  /      \
>                  pivot = 0xffff /        \ pivot = ULONG_MAX
>                                /          \
>   1                       A [-----]       ...
>                              /   \
>              pivot = 0x4fff /     \ pivot = 0xffff
>                            /       \
>   2 (LEAVES)          B [-----]  [-----] C
>                                       ^--- Last pivot 0xffff.
>
> Now imagine we wish to store an entry in the range [0x4000, 0xffff] (note
> that all ranges expressed in maple tree code are inclusive):
>
> 1. mas_store_gfp() descends the tree, finds node A at <=0xffff, then
>    determines that this is a spanning store across nodes B and C. The mas
>    state is set such that the current node from which we traverse further
>    is node A.
>
> 2. In mas_wr_spanning_store() we try to find elements to the right of pivot
>    0xffff by searching for an index of 0x10000:
>
>     - mas_wr_walk_index() invokes mas_wr_walk_descend() and
>       mas_wr_node_walk() in turn.
>
>         - mas_wr_node_walk() loops over entries in node A until EITHER it
>           finds an entry whose pivot equals or exceeds 0x10000 OR it
>           reaches the final entry.
>
>         - Since no entry has a pivot equal to or exceeding 0x10000, pivot
>           0xffff is selected, leading to node C.
>
>     - mas_wr_walk_traverse() resets the mas state to traverse node C. We
>       loop around and invoke mas_wr_walk_descend() and mas_wr_node_walk()
>       in turn once again.
>
>          - Again, we reach the last entry in node C, which has a pivot of
>            0xffff.
>
> 3. We then copy the elements to the left of 0x4000 in node B to the big
>    node via mas_store_b_node(), and insert the new [0x4000, 0xffff] entry
>    too.
>
> 4. We determine whether we have any entries to copy from the right of the
>    end of the range via - and with r_mas set up at the entry at pivot
>    0xffff, r_mas.offset <= r_mas.end, and then we DUPLICATE the entry at
>    pivot 0xffff.
>
> 5. BUG! The maple tree is corrupted with a duplicate entry.
>
> This requires a very specific set of circumstances - we must be spanning
> the last element in a leaf node, which is the last element in the parent
> node.
>
> spanning store across two leaf nodes with a range that ends at that shared
> pivot.
>
> A potential solution to this problem would simply be to reset the walk each
> time we traverse r_mas, however given the rarity of this situation it seems
> that would be rather inefficient.
>
> Instead, this patch detects if the right hand node is populated, i.e. has
> anything we need to copy.
>
> We do so by only copying elements from the right of the entry being inserted
> when the maximum value present exceeds the last, rather than basing this on
> offset position.
>
> The patch also updates some comments and eliminates the unused bool return
> value in mas_wr_walk_index().
>
> The work performed in commit f8d112a4e657 ("mm/mmap: avoid zeroing vma tree
> in mmap_region()") seems to have made the probability of this event much
> more likely, which is the point at which reports started to be submitted
> concerning this bug.
>
> The motivation for this change arose from Bert Karwatzki's report of
> encountering mm instability after the release of kernel v6.12-rc1 which,
> after the use of CONFIG_DEBUG_VM_MAPLE_TREE and similar configuration
> options, was identified as maple tree corruption.
>
> After Bert very generously provided his time and ability to reproduce this
> event consistently, I was able to finally identify that the issue discussed
> in this commit message was occurring for him.
>
> Reported-and-tested-by: Bert Karwatzki <spasswolf@web.de>
> Closes: https://lore.kernel.org/all/20241001023402.3374-1-spasswolf@web.de/
> Reported-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
> Closes: https://lore.kernel.org/all/CABXGCsOPwuoNOqSMmAvWO2Fz4TEmPnjFj-b7iF+XFRu1h7-+Dg@mail.gmail.com/
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Signed-off-by: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> Acked-by: Vlastimil Babka <vbabka@suse.cz>
> ---
>  lib/maple_tree.c | 12 ++++++------
>  1 file changed, 6 insertions(+), 6 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 20990ecba2dd..2fe59c534328 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -2196,6 +2196,8 @@ static inline void mas_node_or_none(struct ma_state *mas,
>
>  /*
>   * mas_wr_node_walk() - Find the correct offset for the index in the @mas.
> + *                      If @mas->index cannot be found within the containing
> + *                      node, we traverse to the last entry in the node.
>   * @wr_mas: The maple write state
>   *
>   * Uses mas_slot_locked() and does not need to worry about dead nodes.
> @@ -3532,7 +3534,7 @@ static bool mas_wr_walk(struct ma_wr_state *wr_mas)
>         return true;
>  }
>
> -static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
> +static void mas_wr_walk_index(struct ma_wr_state *wr_mas)
>  {
>         struct ma_state *mas = wr_mas->mas;
>
> @@ -3541,11 +3543,9 @@ static bool mas_wr_walk_index(struct ma_wr_state *wr_mas)
>                 wr_mas->content = mas_slot_locked(mas, wr_mas->slots,
>                                                   mas->offset);
>                 if (ma_is_leaf(wr_mas->type))
> -                       return true;
> +                       return;
>                 mas_wr_walk_traverse(wr_mas);
> -
>         }
> -       return true;
>  }
>  /*
>   * mas_extend_spanning_null() - Extend a store of a %NULL to include surrounding %NULLs.
> @@ -3765,8 +3765,8 @@ static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas)
>         memset(&b_node, 0, sizeof(struct maple_big_node));
>         /* Copy l_mas and store the value in b_node. */
>         mas_store_b_node(&l_wr_mas, &b_node, l_mas.end);
> -       /* Copy r_mas into b_node. */
> -       if (r_mas.offset <= r_mas.end)
> +       /* Copy r_mas into b_node if there is anything to copy. */
> +       if (r_mas.max > r_mas.last)
>                 mas_mab_cp(&r_mas, r_mas.offset, r_mas.end,
>                            &b_node, b_node.b_end + 1);
>         else
> --
> 2.46.2

Tested-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>

-- 
Best Regards,
Mike Gavrilov.

Re: [PATCH hotfix 6.12 v3 1/2] maple_tree: correct tree corruption on spanning store

[Wei Yang]

On Mon, Oct 07, 2024 at 04:28:32PM +0100, Lorenzo Stoakes wrote:
>There has been a subtle bug present in the maple tree implementation from
>its inception.
>
>This arises from how stores are performed - when a store occurs, it will
>overwrite overlapping ranges and adjust the tree as necessary to
>accommodate this.
>
>A range may always ultimately span two leaf nodes. In this instance we walk
>the two leaf nodes, determine which elements are not overwritten to the
>left and to the right of the start and end of the ranges respectively and
>then rebalance the tree to contain these entries and the newly inserted
>one.
>
>This kind of store is dubbed a 'spanning store' and is implemented by
>mas_wr_spanning_store().
>
>In order to reach this stage, mas_store_gfp() invokes mas_wr_preallocate(),
>mas_wr_store_type() and mas_wr_walk() in turn to walk the tree and update
>the object (mas) to traverse to the location where the write should be
>performed, determining its store type.
>
>When a spanning store is required, this function returns false stopping at
>the parent node which contains the target range, and mas_wr_store_type()
>marks the mas->store_type as wr_spanning_store to denote this fact.
>
>When we go to perform the store in mas_wr_spanning_store(), we first
>determine the elements AFTER the END of the range we wish to store (that
>is, to the right of the entry to be inserted) - we do this by walking to
>the NEXT pivot in the tree (i.e. r_mas.last + 1), starting at the node we
>have just determined contains the range over which we intend to write.
>
>We then turn our attention to the entries to the left of the entry we are
>inserting, whose state is represented by l_mas, and copy these into a 'big
>node', which is a special node which contains enough slots to contain two
>leaf node's worth of data.
>
>We then copy the entry we wish to store immediately after this - the copy
>and the insertion of the new entry is performed by mas_store_b_node().
>
>After this we copy the elements to the right of the end of the range which
>we are inserting, if we have not exceeded the length of the node
>(i.e. r_mas.offset <= r_mas.end).
>
>Herein lies the bug - under very specific circumstances, this logic can
>break and corrupt the maple tree.
>
>Consider the following tree:
>
>Height
>  0                             Root Node
>                                 /      \
>                 pivot = 0xffff /        \ pivot = ULONG_MAX
>                               /          \
>  1                       A [-----]       ...
>                             /   \
>             pivot = 0x4fff /     \ pivot = 0xffff
>                           /       \
>  2 (LEAVES)          B [-----]  [-----] C
>                                      ^--- Last pivot 0xffff.
>
>Now imagine we wish to store an entry in the range [0x4000, 0xffff] (note
>that all ranges expressed in maple tree code are inclusive):
>
>1. mas_store_gfp() descends the tree, finds node A at <=0xffff, then
>   determines that this is a spanning store across nodes B and C. The mas
>   state is set such that the current node from which we traverse further
>   is node A.
>
>2. In mas_wr_spanning_store() we try to find elements to the right of pivot
>   0xffff by searching for an index of 0x10000:
>
>    - mas_wr_walk_index() invokes mas_wr_walk_descend() and
>      mas_wr_node_walk() in turn.
>
>        - mas_wr_node_walk() loops over entries in node A until EITHER it
>          finds an entry whose pivot equals or exceeds 0x10000 OR it
>          reaches the final entry.
>
>        - Since no entry has a pivot equal to or exceeding 0x10000, pivot
>          0xffff is selected, leading to node C.
>
>    - mas_wr_walk_traverse() resets the mas state to traverse node C. We
>      loop around and invoke mas_wr_walk_descend() and mas_wr_node_walk()
>      in turn once again.
>
>         - Again, we reach the last entry in node C, which has a pivot of
>           0xffff.
>
>3. We then copy the elements to the left of 0x4000 in node B to the big
>   node via mas_store_b_node(), and insert the new [0x4000, 0xffff] entry
>   too.
>
>4. We determine whether we have any entries to copy from the right of the
>   end of the range via - and with r_mas set up at the entry at pivot
>   0xffff, r_mas.offset <= r_mas.end, and then we DUPLICATE the entry at
>   pivot 0xffff.
>
>5. BUG! The maple tree is corrupted with a duplicate entry.
>
>This requires a very specific set of circumstances - we must be spanning
>the last element in a leaf node, which is the last element in the parent
>node.
>
>spanning store across two leaf nodes with a range that ends at that shared
>pivot.
>
>A potential solution to this problem would simply be to reset the walk each
>time we traverse r_mas, however given the rarity of this situation it seems
>that would be rather inefficient.
>
>Instead, this patch detects if the right hand node is populated, i.e. has
>anything we need to copy.
>
>We do so by only copying elements from the right of the entry being inserted
>when the maximum value present exceeds the last, rather than basing this on
>offset position.
>
>The patch also updates some comments and eliminates the unused bool return
>value in mas_wr_walk_index().
>
>The work performed in commit f8d112a4e657 ("mm/mmap: avoid zeroing vma tree
>in mmap_region()") seems to have made the probability of this event much
>more likely, which is the point at which reports started to be submitted
>concerning this bug.
>
>The motivation for this change arose from Bert Karwatzki's report of
>encountering mm instability after the release of kernel v6.12-rc1 which,
>after the use of CONFIG_DEBUG_VM_MAPLE_TREE and similar configuration
>options, was identified as maple tree corruption.
>
>After Bert very generously provided his time and ability to reproduce this
>event consistently, I was able to finally identify that the issue discussed
>in this commit message was occurring for him.
>
>Reported-and-tested-by: Bert Karwatzki <spasswolf@web.de>
>Closes: https://lore.kernel.org/all/20241001023402.3374-1-spasswolf@web.de/
>Reported-by: Mikhail Gavrilov <mikhail.v.gavrilov@gmail.com>
>Closes: https://lore.kernel.org/all/CABXGCsOPwuoNOqSMmAvWO2Fz4TEmPnjFj-b7iF+XFRu1h7-+Dg@mail.gmail.com/
>Fixes: 54a611b60590 ("Maple Tree: add new data structure")
>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

Re: [PATCH hotfix 6.12 v3 2/2] maple_tree: add regression test for spanning store bug

[Wei Yang]

On 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

Re: [PATCH hotfix 6.12 v3 0/2] maple_tree: correct tree corruption on spanning store

[Andrew Morton]

On Mon,  7 Oct 2024 16:28:31 +0100 Lorenzo Stoakes <lorenzo.stoakes@oracle.com> wrote:

> Please note - I am intentionally holding off on cc'ing stable until we've
> had a chance to be satisfied the series has stabilised in 6.12 as this is a
> highly subtle change.

What's the status here?  Should I upstream this?  With cc:stable?

Re: [PATCH hotfix 6.12 v3 0/2] maple_tree: correct tree corruption on spanning store

[Lorenzo Stoakes]

On Thu, Oct 17, 2024 at 12:17:23AM -0700, Andrew Morton wrote:
> On Mon,  7 Oct 2024 16:28:31 +0100 Lorenzo Stoakes <lorenzo.stoakes@oracle.com> wrote:
>
> > Please note - I am intentionally holding off on cc'ing stable until we've
> > had a chance to be satisfied the series has stabilised in 6.12 as this is a
> > highly subtle change.
>
> What's the status here?  Should I upstream this?  With cc:stable?

Yes please, this very much needs upstreaming, and seems stable so please cc stable also.

Thanks!