[PATCH RESEND] maple: fix incorrect rewinding in mas_empty_area_rev

[PATCH RESEND] maple: fix incorrect rewinding in mas_empty_area_rev

[Gladyshev Ilya]

Previously, mas_empty_area_rev was rewinding to the previous node if
some offset was cached. This could lead to incorrect results because a
useful gap could be skipped. However, this was never triggered in the
kernel because mm subsystem calls mas_empty_area_rev on non cached mas.

This patch unifies the rewind logic between mas_empty_area_rev and
mas_empty_area, so they both rewind in their correct directions.

Signed-off-by: Gladyshev Ilya <foxido@foxido.dev>
---
 lib/maple_tree.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b4ee2d29d7a9..c7790fff4825 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5138,15 +5138,15 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 
 	if (mas_is_start(mas))
 		mas_start(mas);
-	else if ((mas->offset < 2) && (!mas_rewind_node(mas)))
-		return -EBUSY;
 
 	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
 		return mas_sparse_area(mas, min, max, size, false);
-	else if (mas->offset >= 2)
-		mas->offset -= 2;
-	else
+	else if (!mas->offset)
 		mas->offset = mas_data_end(mas);
+	else if (mas->offset <= mas_data_end(mas) - 2)
+		mas->offset = mas->offset + 2;
+	else if (!mas_skip_node(mas))
+		return -EBUSY;
 
 
 	/* The start of the window can only be within these values. */

base-commit: cbf658dd09419f1ef9de11b9604e950bdd5c170b
-- 
2.51.0

Re: [PATCH RESEND] maple: fix incorrect rewinding in mas_empty_area_rev

[Liam R. Howlett]

* Gladyshev Ilya <foxido@foxido.dev> [250918 14:26]:
> Previously, mas_empty_area_rev was rewinding to the previous node if
> some offset was cached. This could lead to incorrect results because a
> useful gap could be skipped. However, this was never triggered in the
> kernel because mm subsystem calls mas_empty_area_rev on non cached mas.

Can you please produce a test case, ideally in lib/test_maple_tree.c or
tools/testing/radix_tree/maple.c that triggers your issue?  I add all
new tests to one of these places so the error does not return.

You can build maple in tools/testing/radix_tree/ and run it to run the
tests.

It also helps understand the issue.

> 
> This patch unifies the rewind logic between mas_empty_area_rev and
> mas_empty_area, so they both rewind in their correct directions.

How are these unified?  They are still different functions..?  What is
the correct direction, in your opinion?

> 
> Signed-off-by: Gladyshev Ilya <foxido@foxido.dev>
> ---
>  lib/maple_tree.c | 10 +++++-----
>  1 file changed, 5 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index b4ee2d29d7a9..c7790fff4825 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5138,15 +5138,15 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
>  
>  	if (mas_is_start(mas))
>  		mas_start(mas);
> -	else if ((mas->offset < 2) && (!mas_rewind_node(mas)))
> -		return -EBUSY;
>  
>  	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>  		return mas_sparse_area(mas, min, max, size, false);
> -	else if (mas->offset >= 2)
> -		mas->offset -= 2;
> -	else

This does not make sense to me by inspection.
> +	else if (!mas->offset)
>  		mas->offset = mas_data_end(mas);

If we are at the start of the node, go to the end of the node.  If we
are continuing the search, why are we restarting the same node?

> +	else if (mas->offset <= mas_data_end(mas) - 2)
> +		mas->offset = mas->offset + 2;

If we are at the offset less than or equal 2 of the end of the node, we
advance two slots.  This is supposed to be going down but you are going
up?

> +	else if (!mas_skip_node(mas))
> +		return -EBUSY;

Go to the next node, which would be larger addresses or return -EBUSY?

>  
>  
>  	/* The start of the window can only be within these values. */
> 
> base-commit: cbf658dd09419f1ef9de11b9604e950bdd5c170b

This function is to find a gap from top (highest) down (to lower)
addresses.  On entry, it needs to decrement the offset or go to the
previous node.  You are resetting to start from the end of the node or
incrementing two slots.  Failing that (which will only happen when we
are within two of the end of a node), you will go to the NEXT node
which seems the wrong direction?

Can you produce a test case that shows that we are skipping a gap?

Thanks,
Liam

Re: [PATCH RESEND] maple: fix incorrect rewinding in mas_empty_area_rev

[Gladyshev Ilya]

On 9/18/25 23:20, Liam R. Howlett wrote:

Sorry, I kinda overrushed with this patch and it turned out it wasn't 
complete. I apologize for that

Below you can find new patch with regression tests. I'll ignore some of 
your comments (and some of them are fixed) for now, so we can find 
common ground about semantics of empty_area* functions and later, if 
it's really is a bug and not my misunderstanding, I will send v2 for review.

 > * Gladyshev Ilya <foxido@foxido.dev> [250918 14:26]:
 >> Previously, mas_empty_area_rev was rewinding to the previous node if
 >> some offset was cached. This could lead to incorrect results because a
 >> useful gap could be skipped. However, this was never triggered in the
 >> kernel because mm subsystem calls mas_empty_area_rev on non cached mas.
 >
 > Can you please produce a test case, ideally in lib/test_maple_tree.c or
 > tools/testing/radix_tree/maple.c that triggers your issue?  I add all
 > new tests to one of these places so the error does not return.
 >
 > You can build maple in tools/testing/radix_tree/ and run it to run the
 > tests.
 >
 > It also helps understand the issue.
 >
 >>
 >> This patch unifies the rewind logic between mas_empty_area_rev and
 >> mas_empty_area, so they both rewind in their correct directions.
 >
 > How are these unified?  They are still different functions..?  What is
 > the correct direction, in your opinion?

For mas_empty_area we should move towards first slot, for 
mas_empty_area_rev we should move towards last slot. In both cases 
empty_area function will rescan last saved child / gap and won't miss 
anything.
 From 17707e1117a4d4be23f257c3b911c0a36f55b116 Mon Sep 17 00:00:00 2001
From: Gladyshev Ilya <foxido@foxido.dev>
Date: Fri, 19 Sep 2025 20:00:26 +0300
Subject: [PATCH] maple: fix incorrect rewinding in empty_area functions

todo: full description
Signed-off-by: Gladyshev Ilya <foxido@foxido.dev>
---
  lib/maple_tree.c                 | 40 ++++++++++++++--------
  tools/testing/radix-tree/maple.c | 57 ++++++++++++++++++++++++++++++++
  2 files changed, 84 insertions(+), 13 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b4ee2d29d7a9..3cc1596e231b 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4985,13 +4985,10 @@ static inline bool mas_rewind_node(struct 
ma_state *mas)
   */
  static inline bool mas_skip_node(struct ma_state *mas)
  {
-	if (mas_is_err(mas))
-		return false;
-
  	do {
  		if (mte_is_root(mas->node)) {
  			if (mas->offset >= mas_data_end(mas)) {
-				mas_set_err(mas, -EBUSY);
+				mas->offset = mas_data_end(mas);
  				return false;
  			}
  		} else {
@@ -5003,6 +5000,22 @@ static inline bool mas_skip_node(struct ma_state 
*mas)
  	return true;
  }

+/*
+ * mas_skip_node_err() - Wraps mas_skip_node and errors if there is no 
next node
+ */
+static inline bool mas_skip_node_err(struct ma_state *mas)
+{
+	if (mas_is_err(mas))
+		return false;
+
+	if (!mas_skip_node(mas)) {
+		mas_set_err(mas, -EBUSY);
+		return false;
+	}
+
+	return true;
+}
+
  /*
   * mas_awalk() - Allocation walk.  Search from low address to high, 
for a gap of
   * @size
@@ -5024,7 +5037,7 @@ static inline void mas_awalk(struct ma_state *mas, 
unsigned long size)
  	 */
  	while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) {
  		if (last == mas->node)
-			mas_skip_node(mas);
+			mas_skip_node_err(mas);
  		else
  			last = mas->node;
  	}
@@ -5089,8 +5102,8 @@ int mas_empty_area(struct ma_state *mas, unsigned 
long min,
  		mas_start(mas);
  	else if (mas->offset >= 2)
  		mas->offset -= 2;
-	else if (!mas_skip_node(mas))
-		return -EBUSY;
+	else
+		mas_rewind_node(mas);

  	/* Empty set */
  	if (mas_is_none(mas) || mas_is_ptr(mas))
@@ -5128,7 +5141,7 @@ EXPORT_SYMBOL_GPL(mas_empty_area);
  int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
  		unsigned long max, unsigned long size)
  {
-	struct maple_enode *last = mas->node;
+	struct maple_enode *last;

  	if (min > max)
  		return -EINVAL;
@@ -5138,21 +5151,22 @@ int mas_empty_area_rev(struct ma_state *mas, 
unsigned long min,

  	if (mas_is_start(mas))
  		mas_start(mas);
-	else if ((mas->offset < 2) && (!mas_rewind_node(mas)))
-		return -EBUSY;

  	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
  		return mas_sparse_area(mas, min, max, size, false);
-	else if (mas->offset >= 2)
-		mas->offset -= 2;
-	else
+	else if (!mas->offset)
  		mas->offset = mas_data_end(mas);
+	else if (mas->offset <= mas_data_end(mas) - 2)
+		mas->offset = mas->offset + 2;
+	else
+		mas_skip_node(mas);


  	/* The start of the window can only be within these values. */
  	mas->index = min;
  	mas->last = max;

+	last = mas->node;
  	while (!mas_rev_awalk(mas, size, &min, &max)) {
  		if (last == mas->node) {
  			if (!mas_rewind_node(mas))
diff --git a/tools/testing/radix-tree/maple.c 
b/tools/testing/radix-tree/maple.c
index 172700fb7784..bb424f94de1b 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -36655,9 +36655,66 @@ static void test_spanning_store_regression(void)
  	__mt_destroy(&tree);
  }

+static void test_cached_empty_area_rev_regression(void)
+{
+	struct maple_tree tree = MTREE_INIT(&tree, MT_FLAGS_ALLOC_RANGE);
+	MA_STATE(mas, &tree, 0, 0);
+	void *const dataptr = (void *)0x13370;
+
+	for (int i = 1; i <= 10; ++i) {
+		unsigned long start = i * 10000;
+		unsigned long end = start + 1000;
+		mas_set_range(&mas, start, end);
+		mas_store_gfp(&mas, dataptr, GFP_KERNEL);
+	}
+
+	/* NOTE: Still looks unneccecarry for me, but without it cached offset 
in mas::offset is too incorrect.
+	 * Probably couldn't be allowed without disabling caching at all
+	*/
+	mas_reset(&mas);
+
+	for (int i = 1; i < 10; ++i) {
+		/* NOTE: Wasn't working here without mas_reset */
+		// mas_reset(&mas);
+		mas_empty_area_rev(&mas, 0, 200000, 10);
+		BUG_ON(mas.index != 199991);
+	}
+
+	/* Cleanup. */
+	__mt_destroy(&tree);
+}
+
+static void test_cached_empty_area_regression(void)
+{
+	struct maple_tree tree = MTREE_INIT(&tree, MT_FLAGS_ALLOC_RANGE);
+	MA_STATE(mas, &tree, 0, 0);
+	void *const dataptr = (void *)0x13370;
+
+	for (int i = 1; i <= 10; ++i) {
+		unsigned long start = i * 10000;
+		unsigned long end = start + 1000;
+		mas_set_range(&mas, start, end);
+		mas_store_gfp(&mas, dataptr, GFP_KERNEL);
+	}
+
+	mas_reset(&mas);
+
+	for (int i = 1; i < 10; ++i) {
+		/* NOTE: Wasn't working here without mas_reset */
+		// mas_reset(&mas);
+		int res = mas_empty_area(&mas, 0, 200000, 10);
+		BUG_ON(mas.index != 0);
+		BUG_ON(res);
+	}
+
+	/* Cleanup. */
+	__mt_destroy(&tree);
+}
  static void regression_tests(void)
  {
  	test_spanning_store_regression();
+	test_cached_empty_area_regression();
+	test_cached_empty_area_rev_regression();
  }

  void maple_tree_tests(void)

base-commit: cbf658dd09419f1ef9de11b9604e950bdd5c170b
-- 
2.51.0

Re: [PATCH RESEND] maple: fix incorrect rewinding in mas_empty_area_rev

[Liam R. Howlett]

* Gladyshev Ilya <foxido@foxido.dev> [250919 13:14]:
> On 9/18/25 23:20, Liam R. Howlett wrote:
> 
> Sorry, I kinda overrushed with this patch and it turned out it wasn't
> complete. I apologize for that

Well, don't expect me to spend much time on this either, then.

Your testcases are wrong.  You are not using the interface correctly and
have broken the tree with this patch to pass an invalid test.

> 
> Below you can find new patch with regression tests. I'll ignore some of your
> comments (and some of them are fixed) for now, so we can find common ground
> about semantics of empty_area* functions and later, if it's really is a bug
> and not my misunderstanding, I will send v2 for review.
> 
> > * Gladyshev Ilya <foxido@foxido.dev> [250918 14:26]:
> >> Previously, mas_empty_area_rev was rewinding to the previous node if
> >> some offset was cached. This could lead to incorrect results because a
> >> useful gap could be skipped. However, this was never triggered in the
> >> kernel because mm subsystem calls mas_empty_area_rev on non cached mas.
> >
> > Can you please produce a test case, ideally in lib/test_maple_tree.c or
> > tools/testing/radix_tree/maple.c that triggers your issue?  I add all
> > new tests to one of these places so the error does not return.
> >
> > You can build maple in tools/testing/radix_tree/ and run it to run the
> > tests.
> >
> > It also helps understand the issue.
> >
> >>
> >> This patch unifies the rewind logic between mas_empty_area_rev and
> >> mas_empty_area, so they both rewind in their correct directions.
> >
> > How are these unified?  They are still different functions..?  What is
> > the correct direction, in your opinion?
> 
> For mas_empty_area we should move towards first slot, for mas_empty_area_rev
> we should move towards last slot. In both cases empty_area function will
> rescan last saved child / gap and won't miss anything.
> From 17707e1117a4d4be23f257c3b911c0a36f55b116 Mon Sep 17 00:00:00 2001
> From: Gladyshev Ilya <foxido@foxido.dev>
> Date: Fri, 19 Sep 2025 20:00:26 +0300
> Subject: [PATCH] maple: fix incorrect rewinding in empty_area functions
> 
> todo: full description
> Signed-off-by: Gladyshev Ilya <foxido@foxido.dev>
> ---
>  lib/maple_tree.c                 | 40 ++++++++++++++--------
>  tools/testing/radix-tree/maple.c | 57 ++++++++++++++++++++++++++++++++
>  2 files changed, 84 insertions(+), 13 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index b4ee2d29d7a9..3cc1596e231b 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4985,13 +4985,10 @@ static inline bool mas_rewind_node(struct ma_state
> *mas)
>   */
>  static inline bool mas_skip_node(struct ma_state *mas)
>  {
> -	if (mas_is_err(mas))
> -		return false;
> -
>  	do {
>  		if (mte_is_root(mas->node)) {
>  			if (mas->offset >= mas_data_end(mas)) {
> -				mas_set_err(mas, -EBUSY);
> +				mas->offset = mas_data_end(mas);
>  				return false;
>  			}
>  		} else {
> @@ -5003,6 +5000,22 @@ static inline bool mas_skip_node(struct ma_state
> *mas)
>  	return true;
>  }
> 
> +/*
> + * mas_skip_node_err() - Wraps mas_skip_node and errors if there is no next
> node
> + */
> +static inline bool mas_skip_node_err(struct ma_state *mas)
> +{
> +	if (mas_is_err(mas))
> +		return false;
> +
> +	if (!mas_skip_node(mas)) {
> +		mas_set_err(mas, -EBUSY);
> +		return false;
> +	}
> +
> +	return true;
> +}
> +
>  /*
>   * mas_awalk() - Allocation walk.  Search from low address to high, for a
> gap of
>   * @size
> @@ -5024,7 +5037,7 @@ static inline void mas_awalk(struct ma_state *mas,
> unsigned long size)
>  	 */
>  	while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) {
>  		if (last == mas->node)
> -			mas_skip_node(mas);
> +			mas_skip_node_err(mas);
>  		else
>  			last = mas->node;
>  	}
> @@ -5089,8 +5102,8 @@ int mas_empty_area(struct ma_state *mas, unsigned long
> min,
>  		mas_start(mas);
>  	else if (mas->offset >= 2)
>  		mas->offset -= 2;
> -	else if (!mas_skip_node(mas))
> -		return -EBUSY;
> +	else
> +		mas_rewind_node(mas);
> 
>  	/* Empty set */
>  	if (mas_is_none(mas) || mas_is_ptr(mas))
> @@ -5128,7 +5141,7 @@ EXPORT_SYMBOL_GPL(mas_empty_area);
>  int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
>  		unsigned long max, unsigned long size)
>  {
> -	struct maple_enode *last = mas->node;
> +	struct maple_enode *last;
> 
>  	if (min > max)
>  		return -EINVAL;
> @@ -5138,21 +5151,22 @@ int mas_empty_area_rev(struct ma_state *mas,
> unsigned long min,
> 
>  	if (mas_is_start(mas))
>  		mas_start(mas);
> -	else if ((mas->offset < 2) && (!mas_rewind_node(mas)))
> -		return -EBUSY;
> 
>  	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
>  		return mas_sparse_area(mas, min, max, size, false);
> -	else if (mas->offset >= 2)
> -		mas->offset -= 2;
> -	else
> +	else if (!mas->offset)
>  		mas->offset = mas_data_end(mas);
> +	else if (mas->offset <= mas_data_end(mas) - 2)
> +		mas->offset = mas->offset + 2;
> +	else
> +		mas_skip_node(mas);
> 
> 
>  	/* The start of the window can only be within these values. */
>  	mas->index = min;
>  	mas->last = max;
> 
> +	last = mas->node;
>  	while (!mas_rev_awalk(mas, size, &min, &max)) {
>  		if (last == mas->node) {
>  			if (!mas_rewind_node(mas))
> diff --git a/tools/testing/radix-tree/maple.c
> b/tools/testing/radix-tree/maple.c
> index 172700fb7784..bb424f94de1b 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -36655,9 +36655,66 @@ static void test_spanning_store_regression(void)
>  	__mt_destroy(&tree);
>  }
> 
> +static void test_cached_empty_area_rev_regression(void)
> +{
> +	struct maple_tree tree = MTREE_INIT(&tree, MT_FLAGS_ALLOC_RANGE);
> +	MA_STATE(mas, &tree, 0, 0);
> +	void *const dataptr = (void *)0x13370;
> +
> +	for (int i = 1; i <= 10; ++i) {
> +		unsigned long start = i * 10000;
> +		unsigned long end = start + 1000;
> +		mas_set_range(&mas, start, end);
> +		mas_store_gfp(&mas, dataptr, GFP_KERNEL);
> +	}
> +
> +	/* NOTE: Still looks unneccecarry for me, but without it cached offset in
> mas::offset is too incorrect.
> +	 * Probably couldn't be allowed without disabling caching at all
> +	*/
> +	mas_reset(&mas);
> +
> +	for (int i = 1; i < 10; ++i) {
> +		/* NOTE: Wasn't working here without mas_reset */
> +		// mas_reset(&mas);
> +		mas_empty_area_rev(&mas, 0, 200000, 10);
> +		BUG_ON(mas.index != 199991);
> +	}
> +
> +	/* Cleanup. */
> +	__mt_destroy(&tree);
> +}
> +
> +static void test_cached_empty_area_regression(void)
> +{
> +	struct maple_tree tree = MTREE_INIT(&tree, MT_FLAGS_ALLOC_RANGE);
> +	MA_STATE(mas, &tree, 0, 0);
> +	void *const dataptr = (void *)0x13370;
> +
> +	for (int i = 1; i <= 10; ++i) {
> +		unsigned long start = i * 10000;
> +		unsigned long end = start + 1000;
> +		mas_set_range(&mas, start, end);
> +		mas_store_gfp(&mas, dataptr, GFP_KERNEL);
> +	}
> +
> +	mas_reset(&mas);
> +
> +	for (int i = 1; i < 10; ++i) {
> +		/* NOTE: Wasn't working here without mas_reset */
> +		// mas_reset(&mas);
> +		int res = mas_empty_area(&mas, 0, 200000, 10);
> +		BUG_ON(mas.index != 0);
> +		BUG_ON(res);
> +	}
> +
> +	/* Cleanup. */
> +	__mt_destroy(&tree);
> +}
>  static void regression_tests(void)
>  {
>  	test_spanning_store_regression();
> +	test_cached_empty_area_regression();
> +	test_cached_empty_area_rev_regression();
>  }
> 
>  void maple_tree_tests(void)
> 
> base-commit: cbf658dd09419f1ef9de11b9604e950bdd5c170b
> -- 
> 2.51.0
>