[PATCH 0/3] Fix MA_STATE_PREALLOC issue

[PATCH 0/3] Fix MA_STATE_PREALLOC issue

[Liam R. Howlett]

Address the issue of reusing the same maple state for multiple
preallocations calls caused by MA_STATE_PREALLOC, and add a test for
this use case.

Included is a change to the testing code to reduce false positives in
the rcu race testing on faster machines.


Liam R. Howlett (3):
  testing/raix-tree/maple: Increase readers and reduce delay for faster
    machines
  maple_tree: Fix MA_STATE_PREALLOC flag in mas_preallocate()
  tools/testing/radix-tree: Test maple tree chaining mas_preallocate()
    calls

 lib/maple_tree.c                 |  4 +++-
 tools/testing/radix-tree/maple.c | 19 ++++++++++++++++---
 2 files changed, 19 insertions(+), 4 deletions(-)

-- 
2.47.2

[PATCH 1/3] testing/raix-tree/maple: Increase readers and reduce delay for faster machines

[Liam R. Howlett]

From: "Liam R. Howlett" <howlett@gmail.com>

Faster machines may not see the initial or updated value in the race
condition.  Reduce the delay so that faster machines are less likely to
fail testing of the race conditions.

Signed-off-by: Liam R. Howlett <howlett@gmail.com>
---
 tools/testing/radix-tree/maple.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 8b97aac1084e9..6a5b0342941c4 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35062,7 +35062,7 @@ void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
 
 	int i;
 	void *(*function)(void *);
-	pthread_t readers[20];
+	pthread_t readers[30];
 	unsigned int index = vals->index;
 
 	mt_set_in_rcu(mt);
@@ -35080,14 +35080,14 @@ void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
 		}
 	}
 
-	usleep(5); /* small yield to ensure all threads are at least started. */
+	usleep(3); /* small yield to ensure all threads are at least started. */
 
 	while (index <= vals->last) {
 		mtree_store(mt, index,
 			    (index % 2 ? vals->entry2 : vals->entry3),
 			    GFP_KERNEL);
 		index++;
-		usleep(5);
+		usleep(2);
 	}
 
 	while (i--)
@@ -35098,6 +35098,7 @@ void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
 	MT_BUG_ON(mt, !vals->seen_entry3);
 	MT_BUG_ON(mt, !vals->seen_both);
 }
+
 static noinline void __init check_rcu_simulated(struct maple_tree *mt)
 {
 	unsigned long i, nr_entries = 1000;
-- 
2.47.2

[PATCH 2/3] maple_tree: Fix MA_STATE_PREALLOC flag in mas_preallocate()

[Liam R. Howlett]

Temporarily clear the preallocation flag when explicitly requesting
allocations.  Pre-existing allocations are already counted against the
request through mas_node_count_gfp(), but the allocations will not
happen if the MA_STATE_PREALLOC flag is set.  This flag is meant to
avoid re-allocating in bulk allocation mode, and to detect issues with
preallocation calculations.

The MA_STATE_PREALLOC flag should also always be set on zero allocations
so that detection of underflow allocations will print a WARN_ON() during
consumption.

User visible effect of this flaw is a WARN_ON() followed by a null
pointer dereference when subsequent requests for larger number of nodes
is ignored, such as the vma merge retry in mmap_region() caused by
drivers altering the vma flags (which happens in v6.6, at least)

Reported-by: Zhaoyang Huang <zhaoyang.huang@unisoc.com>
Reported-by: Hailong Liu <hailong.liu@oppo.com>
Fixes: 54a611b605901 ("Maple Tree: add new data structure")
Link: https://lore.kernel.org/all/1652f7eb-a51b-4fee-8058-c73af63bacd1@oppo.com/
Link: https://lore.kernel.org/all/20250428184058.1416274-1-Liam.Howlett@oracle.com/
Link: https://lore.kernel.org/all/20250429014754.1479118-1-Liam.Howlett@oracle.com/
Cc: stable@kernel.org
Cc: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
Cc: Suren Baghdasaryan <surenb@google.com>
Cc: Hailong Liu <hailong.liu@oppo.com>
Cc: zhangpeng.00@bytedance.com <zhangpeng.00@bytedance.com>
Cc: Steve Kang <Steve.Kang@unisoc.com>
Cc: Matthew Wilcox <willy@infradead.org>
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 7144dbbc34813..54a09c26edf96 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5528,8 +5528,9 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 	mas->store_type = mas_wr_store_type(&wr_mas);
 	request = mas_prealloc_calc(&wr_mas, entry);
 	if (!request)
-		return ret;
+		goto set_flag;
 
+	mas->mas_flags &= ~MA_STATE_PREALLOC;
 	mas_node_count_gfp(mas, request, gfp);
 	if (mas_is_err(mas)) {
 		mas_set_alloc_req(mas, 0);
@@ -5539,6 +5540,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 		return ret;
 	}
 
+set_flag:
 	mas->mas_flags |= MA_STATE_PREALLOC;
 	return ret;
 }
-- 
2.47.2

[PATCH 3/3] tools/testing/radix-tree: Test maple tree chaining mas_preallocate() calls

[Liam R. Howlett]

Testing calling multiple mas_preallocate() calls in a row after
adjusting the maple state.  Ensures new calls to mas_preallocate() will
change the number of allocated nodes.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 tools/testing/radix-tree/maple.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 6a5b0342941c4..49e89dfad950c 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35693,6 +35693,18 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated != 0);
+
+	/* Chaining multiple preallocations */
+	mt_set_in_rcu(mt);
+	mas_set_range(&mas, 800, 805); /* Slot store, should be 0 allocations */
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
+	allocated = mas_allocated(&mas);
+	MT_BUG_ON(mt, allocated != 0);
+	mas.last = 809; /* Node store */
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
+	allocated = mas_allocated(&mas);
+	MT_BUG_ON(mt, allocated != 1);
+	mas_store_prealloc(&mas, ptr);
 }
 /* End of preallocation testing */
 
-- 
2.47.2

Re: [PATCH 0/3] Fix MA_STATE_PREALLOC issue

[Andrew Morton]

On Mon, 16 Jun 2025 14:45:18 -0400 "Liam R. Howlett" <Liam.Howlett@oracle.com> wrote:

> Address the issue of reusing the same maple state for multiple
> preallocations calls caused by MA_STATE_PREALLOC, and add a test for
> this use case.
> 
> Included is a change to the testing code to reduce false positives in
> the rcu race testing on faster machines.

I split this series into

- a standalone fix for 6.16-rcX and -stable.

- two standalone selftests patches for 6.17-rc1.

Is that OK?

Re: [PATCH 1/3] testing/raix-tree/maple: Increase readers and reduce delay for faster machines

[Lorenzo Stoakes]

On Mon, Jun 16, 2025 at 02:45:19PM -0400, Liam R. Howlett wrote:
> From: "Liam R. Howlett" <howlett@gmail.com>
>
> Faster machines may not see the initial or updated value in the race
> condition.  Reduce the delay so that faster machines are less likely to
> fail testing of the race conditions.
>
> Signed-off-by: Liam R. Howlett <howlett@gmail.com>

Seems reasonable so:

Reviewed-by: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>

> ---
>  tools/testing/radix-tree/maple.c | 7 ++++---
>  1 file changed, 4 insertions(+), 3 deletions(-)
>
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index 8b97aac1084e9..6a5b0342941c4 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35062,7 +35062,7 @@ void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
>
>  	int i;
>  	void *(*function)(void *);
> -	pthread_t readers[20];
> +	pthread_t readers[30];
>  	unsigned int index = vals->index;
>
>  	mt_set_in_rcu(mt);
> @@ -35080,14 +35080,14 @@ void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
>  		}
>  	}
>
> -	usleep(5); /* small yield to ensure all threads are at least started. */
> +	usleep(3); /* small yield to ensure all threads are at least started. */
>
>  	while (index <= vals->last) {
>  		mtree_store(mt, index,
>  			    (index % 2 ? vals->entry2 : vals->entry3),
>  			    GFP_KERNEL);
>  		index++;
> -		usleep(5);
> +		usleep(2);

Just one question... have you considered hibernation at all?

>  	}
>
>  	while (i--)
> @@ -35098,6 +35098,7 @@ void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
>  	MT_BUG_ON(mt, !vals->seen_entry3);
>  	MT_BUG_ON(mt, !vals->seen_both);
>  }
> +
>  static noinline void __init check_rcu_simulated(struct maple_tree *mt)
>  {
>  	unsigned long i, nr_entries = 1000;
> --
> 2.47.2
>

Re: [PATCH 2/3] maple_tree: Fix MA_STATE_PREALLOC flag in mas_preallocate()

[Lorenzo Stoakes]

On Mon, Jun 16, 2025 at 02:45:20PM -0400, Liam R. Howlett wrote:
> Temporarily clear the preallocation flag when explicitly requesting
> allocations.  Pre-existing allocations are already counted against the
> request through mas_node_count_gfp(), but the allocations will not
> happen if the MA_STATE_PREALLOC flag is set.  This flag is meant to
> avoid re-allocating in bulk allocation mode, and to detect issues with
> preallocation calculations.
>
> The MA_STATE_PREALLOC flag should also always be set on zero allocations
> so that detection of underflow allocations will print a WARN_ON() during
> consumption.
>
> User visible effect of this flaw is a WARN_ON() followed by a null
> pointer dereference when subsequent requests for larger number of nodes
> is ignored, such as the vma merge retry in mmap_region() caused by
> drivers altering the vma flags (which happens in v6.6, at least)

Oh interesting, this was a deep one (Lovecraftian pun fully intended)!

>
> Reported-by: Zhaoyang Huang <zhaoyang.huang@unisoc.com>
> Reported-by: Hailong Liu <hailong.liu@oppo.com>
> Fixes: 54a611b605901 ("Maple Tree: add new data structure")
> Link: https://lore.kernel.org/all/1652f7eb-a51b-4fee-8058-c73af63bacd1@oppo.com/
> Link: https://lore.kernel.org/all/20250428184058.1416274-1-Liam.Howlett@oracle.com/
> Link: https://lore.kernel.org/all/20250429014754.1479118-1-Liam.Howlett@oracle.com/
> Cc: stable@kernel.org
> Cc: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> Cc: Suren Baghdasaryan <surenb@google.com>
> Cc: Hailong Liu <hailong.liu@oppo.com>
> Cc: zhangpeng.00@bytedance.com <zhangpeng.00@bytedance.com>
> Cc: Steve Kang <Steve.Kang@unisoc.com>
> Cc: Matthew Wilcox <willy@infradead.org>
> Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

This looks reasonable, but because I am not quite au fait with all the details
on a deeper level:

Acked-by: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>

> ---
>  lib/maple_tree.c | 4 +++-
>  1 file changed, 3 insertions(+), 1 deletion(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 7144dbbc34813..54a09c26edf96 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5528,8 +5528,9 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>  	mas->store_type = mas_wr_store_type(&wr_mas);
>  	request = mas_prealloc_calc(&wr_mas, entry);
>  	if (!request)
> -		return ret;
> +		goto set_flag;
>
> +	mas->mas_flags &= ~MA_STATE_PREALLOC;
>  	mas_node_count_gfp(mas, request, gfp);
>  	if (mas_is_err(mas)) {
>  		mas_set_alloc_req(mas, 0);
> @@ -5539,6 +5540,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>  		return ret;
>  	}
>
> +set_flag:
>  	mas->mas_flags |= MA_STATE_PREALLOC;
>  	return ret;
>  }
> --
> 2.47.2
>

Re: [PATCH 3/3] tools/testing/radix-tree: Test maple tree chaining mas_preallocate() calls

[Lorenzo Stoakes]

On Mon, Jun 16, 2025 at 02:45:21PM -0400, Liam R. Howlett wrote:
> Testing calling multiple mas_preallocate() calls in a row after
> adjusting the maple state.  Ensures new calls to mas_preallocate() will
> change the number of allocated nodes.

Really helpful to have a regression test for such a fiddly thing!

>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

Acked-by: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>

> ---
>  tools/testing/radix-tree/maple.c | 12 ++++++++++++
>  1 file changed, 12 insertions(+)
>
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index 6a5b0342941c4..49e89dfad950c 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35693,6 +35693,18 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
>  	allocated = mas_allocated(&mas);
>  	height = mas_mt_height(&mas);
>  	MT_BUG_ON(mt, allocated != 0);
> +
> +	/* Chaining multiple preallocations */
> +	mt_set_in_rcu(mt);
> +	mas_set_range(&mas, 800, 805); /* Slot store, should be 0 allocations */
> +	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> +	allocated = mas_allocated(&mas);
> +	MT_BUG_ON(mt, allocated != 0);
> +	mas.last = 809; /* Node store */
> +	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
> +	allocated = mas_allocated(&mas);
> +	MT_BUG_ON(mt, allocated != 1);
> +	mas_store_prealloc(&mas, ptr);
>  }
>  /* End of preallocation testing */
>
> --
> 2.47.2
>

Re: [PATCH 0/3] Fix MA_STATE_PREALLOC issue

[Liam R. Howlett]

* Andrew Morton <akpm@linux-foundation.org> [250616 19:24]:
> On Mon, 16 Jun 2025 14:45:18 -0400 "Liam R. Howlett" <Liam.Howlett@oracle.com> wrote:
> 
> > Address the issue of reusing the same maple state for multiple
> > preallocations calls caused by MA_STATE_PREALLOC, and add a test for
> > this use case.
> > 
> > Included is a change to the testing code to reduce false positives in
> > the rcu race testing on faster machines.
> 
> I split this series into
> 
> - a standalone fix for 6.16-rcX and -stable.
> 
> - two standalone selftests patches for 6.17-rc1.
> 
> Is that OK?


Yes, should be fine.

Thanks for checking.
Liam