[Patch v3 0/3] maple_tree: Fix the replacement of a root leaf node

[Patch v3 0/3] maple_tree: Fix the replacement of a root leaf node

[Wei Yang]

On destroy we should set each node dead. But current
code miss this when the maple tree has only the root node.

The reason is mt_destroy_walk() leverage mte_destroy_descend() to set
node dead, but this is skipped since the only root node is a leaf.

Patch 1 fixes this.

When adding a test case, I found we always get the new value even we leave the
old root node not dead. It turns out we always re-walk the tree in mas_walk().
It looks like a typo on the status check of mas_walk().

Patch 2 fixes this.

Patch 3 add a test case to assert retrieving new value when overwriting the
whole range to a tree with only root node.

V3 rebase on latest mm-unstable with base commit eba4438e2296.

Wei Yang (3):
  maple_tree: Fix mt_destroy_walk() on root leaf node
  maple_tree: restart walk on correct status
  maple_tree: assert retrieving new value on a tree containing just a
    leaf node

 lib/maple_tree.c                 |  3 ++-
 tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
 2 files changed, 26 insertions(+), 1 deletion(-)

-- 
2.34.1

[Patch v3 1/3] maple_tree: Fix mt_destroy_walk() on root leaf node

[Wei Yang]

On destroy, we should set each node dead. But current code miss this
when the maple tree has only the root node.

The reason is mt_destroy_walk() leverage mte_destroy_descend() to set
node dead, but this is skipped since the only root node is a leaf.

Fixes this by setting the node dead if it is a leaf.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Liam R. Howlett <Liam.Howlett@Oracle.com>
Cc: <stable@vger.kernel.org>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

---
v2:
  * move the operation into mt_destroy_walk()
  * adjust the title accordingly
---
 lib/maple_tree.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index affe979bd14d..b0c345b6e646 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5319,6 +5319,7 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
 	struct maple_enode *start;
 
 	if (mte_is_leaf(enode)) {
+		mte_set_node_dead(enode);
 		node->type = mte_node_type(enode);
 		goto free_leaf;
 	}
-- 
2.34.1

[Patch v3 2/3] maple_tree: restart walk on correct status

[Wei Yang]

Commit a8091f039c1e ("maple_tree: add MAS_UNDERFLOW and MAS_OVERFLOW
states") adds more status during maple tree walk. But it introduce a
typo on the status check during walk.

It expects to mean neither active nor start, we would restart the walk,
while current code means we would always restart the walk.

Fixes: a8091f039c1e ("maple_tree: add MAS_UNDERFLOW and MAS_OVERFLOW states")
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Liam R. Howlett <Liam.Howlett@Oracle.com>
Cc: <stable@vger.kernel.org>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b0c345b6e646..7144dbbc3481 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4930,7 +4930,7 @@ void *mas_walk(struct ma_state *mas)
 {
 	void *entry;
 
-	if (!mas_is_active(mas) || !mas_is_start(mas))
+	if (!mas_is_active(mas) && !mas_is_start(mas))
 		mas->status = ma_start;
 retry:
 	entry = mas_state_walk(mas);
-- 
2.34.1

[Patch v3 3/3] maple_tree: assert retrieving new value on a tree containing just a leaf node

[Wei Yang]

Original code may not get the new value after overwriting the whole
range on a maple tree containing just a leaf node. The reason is we didn't
set the only root node dead during destroy.

Add a test case to ensure the new value is returned when overwriting a
tree containing just a leaf node.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
Cc: Liam R. Howlett <Liam.Howlett@Oracle.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

---
v2: adjust the changelog according to Liam's suggestion
---
 tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 2c0b38301253..8b97aac1084e 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35256,6 +35256,30 @@ static noinline void __init check_rcu_simulated(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_prev(&mas_reader, 0) != xa_mk_value(val));
 	rcu_read_unlock();
 
+	/* Clear out tree & create one with only root node */
+	mas_lock(&mas_writer);
+	mas_set_range(&mas_writer, 0, ULONG_MAX);
+	mas_store_gfp(&mas_writer, NULL, GFP_KERNEL);
+	mas_set_range(&mas_writer, 0, 0);
+	for (i = 0; i <= 5; i++) {
+		mas_writer.index = i * 10;
+		mas_writer.last = i * 10 + 5;
+		mas_store_gfp(&mas_writer, xa_mk_value(i), GFP_KERNEL);
+	}
+	mas_unlock(&mas_writer);
+	target = 10;
+	mas_set_range(&mas_reader, target, target);
+	rcu_read_lock();
+	MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
+
+	/* Overwrite the whole range */
+	mas_lock(&mas_writer);
+	mas_set_range(&mas_writer, 0, ULONG_MAX);
+	mas_store_gfp(&mas_writer, xa_mk_value(val), GFP_KERNEL);
+	mas_unlock(&mas_writer);
+	MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val));
+	rcu_read_unlock();
+
 	rcu_unregister_thread();
 }
 
-- 
2.34.1

Re: [Patch v3 0/3] maple_tree: Fix the replacement of a root leaf node

[Andrew Morton]

On Wed, 11 Jun 2025 01:12:50 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:

> On destroy we should set each node dead. But current
> code miss this when the maple tree has only the root node.
> 
> The reason is mt_destroy_walk() leverage mte_destroy_descend() to set
> node dead, but this is skipped since the only root node is a leaf.

Thanks.  You added cc:stable to two of the patches and that's great,
thanks for remembering.  But the changelogs didn't tell us why you made
this choice.

So, as always, please always describe the userspace-visible impact of a
bug when fixing that bug!

Re: [Patch v3 0/3] maple_tree: Fix the replacement of a root leaf node

[Wei Yang]

On Tue, Jun 10, 2025 at 06:37:27PM -0700, Andrew Morton wrote:
>On Wed, 11 Jun 2025 01:12:50 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
>
>> On destroy we should set each node dead. But current
>> code miss this when the maple tree has only the root node.
>> 
>> The reason is mt_destroy_walk() leverage mte_destroy_descend() to set
>> node dead, but this is skipped since the only root node is a leaf.
>
>Thanks.  You added cc:stable to two of the patches and that's great,
>thanks for remembering.  But the changelogs didn't tell us why you made
>this choice.
>
>So, as always, please always describe the userspace-visible impact of a
>bug when fixing that bug!

Thanks for reminding.

Do you prefer to have a new version with the description in changelog?

-- 
Wei Yang
Help you, Help me

Re: [Patch v3 0/3] maple_tree: Fix the replacement of a root leaf node

[Andrew Morton]

On Wed, 11 Jun 2025 02:54:36 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:

> On Tue, Jun 10, 2025 at 06:37:27PM -0700, Andrew Morton wrote:
> >On Wed, 11 Jun 2025 01:12:50 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
> >
> >> On destroy we should set each node dead. But current
> >> code miss this when the maple tree has only the root node.
> >> 
> >> The reason is mt_destroy_walk() leverage mte_destroy_descend() to set
> >> node dead, but this is skipped since the only root node is a leaf.
> >
> >Thanks.  You added cc:stable to two of the patches and that's great,
> >thanks for remembering.  But the changelogs didn't tell us why you made
> >this choice.
> >
> >So, as always, please always describe the userspace-visible impact of a
> >bug when fixing that bug!
> 
> Thanks for reminding.
> 
> Do you prefer to have a new version with the description in changelog?

No, that's fine - please just send it in reply to this email.  

Re: [Patch v3 0/3] maple_tree: Fix the replacement of a root leaf node

[Wei Yang]

On Tue, Jun 10, 2025 at 08:55:39PM -0700, Andrew Morton wrote:
>On Wed, 11 Jun 2025 02:54:36 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
>
>> On Tue, Jun 10, 2025 at 06:37:27PM -0700, Andrew Morton wrote:
>> >On Wed, 11 Jun 2025 01:12:50 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
>> >
>> >> On destroy we should set each node dead. But current
>> >> code miss this when the maple tree has only the root node.
>> >> 
>> >> The reason is mt_destroy_walk() leverage mte_destroy_descend() to set
>> >> node dead, but this is skipped since the only root node is a leaf.
>> >
>> >Thanks.  You added cc:stable to two of the patches and that's great,
>> >thanks for remembering.  But the changelogs didn't tell us why you made
>> >this choice.
>> >
>> >So, as always, please always describe the userspace-visible impact of a
>> >bug when fixing that bug!
>> 
>> Thanks for reminding.
>> 
>> Do you prefer to have a new version with the description in changelog?
>
>No, that's fine - please just send it in reply to this email.

Below is my understanding about the impact of the bug.

---

Without the fix, maple tree user may see old value after overwriting the whole
range [0, ULONG_MAX] on a tree containing just one leaf node. If it happens,
kernel may access some invalid data and be crashed.

Since we rarely overwrite the whole range of a maple tree, we don't expect it
to have userspace-visible impact in practise.

-- 
Wei Yang
Help you, Help me