[PATCH] maple_tree: Fix allocation in mas_sparse_area()

[PATCH] maple_tree: Fix allocation in mas_sparse_area()

[Peng Zhang]

In the case of reverse allocation, mas->index and mas->last do not point
to the correct allocation range, which will cause users to get incorrect
allocation results, so fix it. If the user does not use it in a specific
way, this bug will not be triggered.

Also re-checks whether the size is still satisfied after the lower bound
was increased, which is a corner case and is incorrect in previous versions.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 41 ++++++++++++++++++++---------------------
 1 file changed, 20 insertions(+), 21 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 9172bcee94b48..110a36479dced 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5250,25 +5250,28 @@ static inline void mas_fill_gap(struct ma_state *mas, void *entry,
  * @size: The size of the gap
  * @fwd: Searching forward or back
  */
-static inline void mas_sparse_area(struct ma_state *mas, unsigned long min,
+static inline int mas_sparse_area(struct ma_state *mas, unsigned long min,
 				unsigned long max, unsigned long size, bool fwd)
 {
-	unsigned long start = 0;
-
-	if (!unlikely(mas_is_none(mas)))
-		start++;
+	if (!unlikely(mas_is_none(mas)) && min == 0) {
+		min++;
+		/*
+		 * At this time, min is increased, we need to recheck whether
+		 * the size is satisfied.
+		 */
+		if (min > max || max - min + 1 < size)
+			return -EBUSY;
+	}
 	/* mas_is_ptr */
 
-	if (start < min)
-		start = min;
-
 	if (fwd) {
-		mas->index = start;
-		mas->last = start + size - 1;
-		return;
+		mas->index = min;
+		mas->last = min + size - 1;
+	} else {
+		mas->last = max;
+		mas->index = max - size + 1;
 	}
-
-	mas->index = max;
+	return 0;
 }
 
 /*
@@ -5297,10 +5300,8 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
 		return -EBUSY;
 
 	/* Empty set */
-	if (mas_is_none(mas) || mas_is_ptr(mas)) {
-		mas_sparse_area(mas, min, max, size, true);
-		return 0;
-	}
+	if (mas_is_none(mas) || mas_is_ptr(mas))
+		return mas_sparse_area(mas, min, max, size, true);
 
 	/* The start of the window can only be within these values */
 	mas->index = min;
@@ -5356,10 +5357,8 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 	}
 
 	/* Empty set. */
-	if (mas_is_none(mas) || mas_is_ptr(mas)) {
-		mas_sparse_area(mas, min, max, size, false);
-		return 0;
-	}
+	if (mas_is_none(mas) || mas_is_ptr(mas))
+		return mas_sparse_area(mas, min, max, size, false);
 
 	/* The start of the window can only be within these values. */
 	mas->index = min;
-- 
2.20.1

Re: [PATCH] maple_tree: Fix allocation in mas_sparse_area()

[Andrew Morton]

On Wed, 19 Apr 2023 17:36:25 +0800 Peng Zhang <zhangpeng.00@bytedance.com> wrote:

> In the case of reverse allocation, mas->index and mas->last do not point
> to the correct allocation range, which will cause users to get incorrect
> allocation results, so fix it. If the user does not use it in a specific
> way, this bug will not be triggered.

Please describe the user-visible effects of the bug.  I assume "none",
because there are presently no callers which can trigger it?

> Also re-checks whether the size is still satisfied after the lower bound
> was increased, which is a corner case and is incorrect in previous versions.

Again, what are the user-visible effects of the bug?

Re: [PATCH] maple_tree: Fix allocation in mas_sparse_area()

[Liam R. Howlett]

* Andrew Morton <akpm@linux-foundation.org> [230419 15:49]:
> On Wed, 19 Apr 2023 17:36:25 +0800 Peng Zhang <zhangpeng.00@bytedance.com> wrote:
> 
> > In the case of reverse allocation, mas->index and mas->last do not point
> > to the correct allocation range, which will cause users to get incorrect
> > allocation results, so fix it. If the user does not use it in a specific
> > way, this bug will not be triggered.
> 
> Please describe the user-visible effects of the bug.  I assume "none",
> because there are presently no callers which can trigger it?

Yes, sparse nodes are not enabled at this time.

> 
> > Also re-checks whether the size is still satisfied after the lower bound
> > was increased, which is a corner case and is incorrect in previous versions.
> 
> Again, what are the user-visible effects of the bug?

Correct, none.

Re: [PATCH] maple_tree: Fix allocation in mas_sparse_area()

[Peng Zhang]

在 2023/4/20 03:49, Andrew Morton 写道:
> On Wed, 19 Apr 2023 17:36:25 +0800 Peng Zhang <zhangpeng.00@bytedance.com> wrote:
>
>> In the case of reverse allocation, mas->index and mas->last do not point
>> to the correct allocation range, which will cause users to get incorrect
>> allocation results, so fix it. If the user does not use it in a specific
>> way, this bug will not be triggered.
> Please describe the user-visible effects of the bug.  I assume "none",
> because there are presently no callers which can trigger it?
>
>> Also re-checks whether the size is still satisfied after the lower bound
>> was increased, which is a corner case and is incorrect in previous versions.
> Again, what are the user-visible effects of the bug?
>
>
This is indeed a bug, but only VMA uses it now, the way VMA is used
now will not trigger it. There is a possibility that a user will
trigger it in the future. As a general-purpose data structure library,
Maple tree is treated as an opaque box by its users. I think that
as long as users use the API provided by Maple tree correctly,
there should be no errors in maple tree. Just like other data structure
libraries (such as rbtree). So I fixed it. It's easy to write test
cases to trigger this bug, but I haven't written test code yet.

Sorry I didn't describe it in detail. In the future I will describe
user-visible effects in detail.

Thanks.