[PATCH 0/9] fix, rework and clean up for maple tree

[PATCH 0/9] fix, rework and clean up for maple tree

[Peng Zhang]

I noticed that Liam R. Howlett's v2 patch set[1] has been merged. Merging v3
will have conflicts, so I included the extra parts of v3 relative to v2 into my
patch set. In this way, v3 can be ignored.

I made some changes to [4/9] from Liam R. Howlett, because it was not fully
fixed before, causing the test to fail.

Refactored mtree_alloc_range/rrange() to fix bugs and improve maintainability.
This makes the three functions mas_fill_gap(), mas_rev_alloc() and mas_alloc()
no longer used. But I did not delete them, because maple tree is still under
development. This refactoring is worth discussing. And I don't understand why
these three functions are needed because there are functions similar to them.

[1]: https://lore.kernel.org/lkml/20230421135559.2163923-1-Liam.Howlett@oracle.com/

Liam R. Howlett (1):
  maple_tree: Update mtree_alloc_rrange() and mtree_alloc_range()
    testing

Peng Zhang (8):
  maple_tree: Fix allocation when min is equal to max in
    mas_empty_area/_area_rev()
  maple_tree: Make maple state reusable after mas_empty_area()
  maple_tree: Modify the allocation method of mtree_alloc_range/rrange()
  maple_tree: Remove an if statement that cannot be true
  maple_tree: Remove a confusing check
  maple_tree: Delete redundant code in mas_next_node()
  maple_tree: Remove the redundant check of mas->offset in
    mas_empty_area/area_rev()
  maple_tree: Move declaration of mas_empty_area_rev() to a better place

 include/linux/maple_tree.h | 12 ++---
 lib/maple_tree.c           | 89 +++++++++++---------------------------
 lib/test_maple_tree.c      | 30 +++++++++----
 3 files changed, 53 insertions(+), 78 deletions(-)

-- 
2.20.1

[PATCH 1/9] maple_tree: Fix allocation when min is equal to max in mas_empty_area/_area_rev()

[Peng Zhang]

Make the allocation valid when min is equal to max in mas_empty_area()
and mas_empty_area_rev(). As Liam R. Howlett said, VMA doesn't make this
allocation, so now this bug won't trigger.

Also add some checks for invalid parameters.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 110a36479dced..72099b4b32169 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5289,7 +5289,10 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
 	unsigned long *pivots;
 	enum maple_type mt;
 
-	if (min >= max)
+	if (unlikely(min > max))
+		return -EINVAL;
+
+	if (unlikely(size == 0) || unlikely(max - min < size - 1))
 		return -EINVAL;
 
 	if (mas_is_start(mas))
@@ -5344,7 +5347,10 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 {
 	struct maple_enode *last = mas->node;
 
-	if (min >= max)
+	if (unlikely(min > max))
+		return -EINVAL;
+
+	if (unlikely(size == 0) || unlikely(max - min < size - 1))
 		return -EINVAL;
 
 	if (mas_is_start(mas)) {
@@ -5380,7 +5386,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 		return -EBUSY;
 
 	/* Trim the upper limit to the max. */
-	if (max <= mas->last)
+	if (max < mas->last)
 		mas->last = max;
 
 	mas->index = mas->last - size + 1;
-- 
2.20.1

[PATCH 2/9] maple_tree: Make maple state reusable after mas_empty_area()

[Peng Zhang]

Make mas->min and mas->max point to a node range instead of a leaf entry
range. This allows mas to still be usable after mas_empty_area() returns.
This currently has no user impact because no one use mas after
mas_empty_area() now.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 72099b4b32169..aa55c914818a0 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5320,14 +5320,7 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
 
 	mt = mte_node_type(mas->node);
 	pivots = ma_pivots(mas_mn(mas), mt);
-	if (offset)
-		mas->min = pivots[offset - 1] + 1;
-
-	if (offset < mt_pivots[mt])
-		mas->max = pivots[offset];
-
-	if (mas->index < mas->min)
-		mas->index = mas->min;
+	mas->index = max(mas->index, mas_safe_min(mas, pivots, offset));
 
 	mas->last = mas->index + size - 1;
 	return 0;
-- 
2.20.1

[PATCH 3/9] maple_tree: Modify the allocation method of mtree_alloc_range/rrange()

[Peng Zhang]

Let mtree_alloc_range() and mtree_alloc_rrange() use mas_empty_area()
and mas_empty_area_rev() respectively for allocation to reduce code
redundancy. And after doing this, we don't need to maintain two logically
identical codes to improve maintainability.

In fact, mtree_alloc_range/rrange() has some bugs. For example, when
dealing with min equals to max (mas_empty_area/area_rev() has been fixed),
the allocation will fail.
There are still some other bugs in it, I saw it with my naked eyes, but
I didn't test it, for example:
When mtree_alloc_range()->mas_alloc()->mas_awalk(), we set mas.index = min,
mas.last = max - size. However, mas_awalk() requires mas.index = min,
mas.last = max, which may lead to allocation failures.

Right now no users are using these two functions so the bug won't trigger,
but this might trigger in the future.

Also use mas_store_gfp() instead of mas_fill_gap() as I don't see any
difference between them.

After doing this, we no longer need the three functions
mas_fill_gap(), mas_alloc(), and mas_rev_alloc().

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index aa55c914818a0..294d4c8668323 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6362,32 +6362,20 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, max - size);
+	MA_STATE(mas, mt, 0, 0);
 	if (!mt_is_alloc(mt))
 		return -EINVAL;
 
 	if (WARN_ON_ONCE(mt_is_reserved(entry)))
 		return -EINVAL;
 
-	if (min > max)
-		return -EINVAL;
-
-	if (max < size)
-		return -EINVAL;
-
-	if (!size)
-		return -EINVAL;
-
 	mtree_lock(mt);
-retry:
-	mas.offset = 0;
-	mas.index = min;
-	mas.last = max - size;
-	ret = mas_alloc(&mas, entry, size, startp);
-	if (mas_nomem(&mas, gfp))
-		goto retry;
-
+	ret = mas_empty_area(&mas, min, max, size);
+	if (!ret)
+		ret = mas_store_gfp(&mas, entry, gfp);
 	mtree_unlock(mt);
+	if (!ret)
+		*startp = mas.index;
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_range);
@@ -6398,29 +6386,20 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, max - size);
+	MA_STATE(mas, mt, 0, 0);
 	if (!mt_is_alloc(mt))
 		return -EINVAL;
 
 	if (WARN_ON_ONCE(mt_is_reserved(entry)))
 		return -EINVAL;
 
-	if (min >= max)
-		return -EINVAL;
-
-	if (max < size - 1)
-		return -EINVAL;
-
-	if (!size)
-		return -EINVAL;
-
 	mtree_lock(mt);
-retry:
-	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
-	if (mas_nomem(&mas, gfp))
-		goto retry;
-
+	ret = mas_empty_area_rev(&mas, min, max, size);
+	if (!ret)
+		ret = mas_store_gfp(&mas, entry, gfp);
 	mtree_unlock(mt);
+	if (!ret)
+		*startp = mas.index;
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_rrange);
-- 
2.20.1

[PATCH 4/9] maple_tree: Update mtree_alloc_rrange() and mtree_alloc_range() testing

[Peng Zhang]

From: "Liam R. Howlett" <Liam.Howlett@oracle.com>

The previous changes to the gap searching made this testing fail.
Unfortunately, there was not a safe update order, so fix the testing
now.

Fixes: e15e06a83923 ("lib/test_maple_tree: add testing for maple tree")
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Co-developed-by: Peng Zhang <zhangpeng.00@bytedance.com>
Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/test_maple_tree.c | 30 ++++++++++++++++++++++--------
 1 file changed, 22 insertions(+), 8 deletions(-)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index f1db333270e9f..30f2ebff95d75 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -102,7 +102,7 @@ static noinline void check_mtree_alloc_rrange(struct maple_tree *mt,
 	unsigned long result = expected + 1;
 	int ret;
 
-	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end - 1,
+	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
 			GFP_KERNEL);
 	MT_BUG_ON(mt, ret != eret);
 	if (ret)
@@ -680,7 +680,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
 		0,              /* Return value success. */
 
 		0x0,            /* Min */
-		0x565234AF1 << 12,    /* Max */
+		0x565234AF0 << 12,    /* Max */
 		0x3000,         /* Size */
 		0x565234AEE << 12,  /* max - 3. */
 		0,              /* Return value success. */
@@ -692,14 +692,14 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
 		0,              /* Return value success. */
 
 		0x0,            /* Min */
-		0x7F36D510A << 12,    /* Max */
+		0x7F36D5109 << 12,    /* Max */
 		0x4000,         /* Size */
 		0x7F36D5106 << 12,    /* First rev hole of size 0x4000 */
 		0,              /* Return value success. */
 
 		/* Ascend test. */
 		0x0,
-		34148798629 << 12,
+		34148798628 << 12,
 		19 << 12,
 		34148797418 << 12,
 		0x0,
@@ -711,6 +711,12 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
 		0x0,
 		-EBUSY,
 
+		/* Single space test. */
+		34148798725 << 12,
+		34148798725 << 12,
+		1 << 12,
+		34148798725 << 12,
+		0,
 	};
 
 	int i, range_count = ARRAY_SIZE(range);
@@ -759,9 +765,9 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
 	mas_unlock(&mas);
 	for (i = 0; i < req_range_count; i += 5) {
 #if DEBUG_REV_RANGE
-		pr_debug("\tReverse request between %lu-%lu size %lu, should get %lu\n",
-				req_range[i] >> 12,
-				(req_range[i + 1] >> 12) - 1,
+		pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
+				i, req_range[i] >> 12,
+				(req_range[i + 1] >> 12),
 				req_range[i+2] >> 12,
 				req_range[i+3] >> 12);
 #endif
@@ -777,6 +783,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
 
 	mt_set_non_kernel(1);
 	mtree_erase(mt, 34148798727); /* create a deleted range. */
+	mtree_erase(mt, 34148798725);
 	check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
 			34148798725, 0, mt);
 
@@ -880,6 +887,13 @@ static noinline void check_alloc_range(struct maple_tree *mt)
 		4503599618982063UL << 12,  /* Size */
 		34359052178 << 12,  /* Expected location */
 		-EBUSY,             /* Return failure. */
+
+		/* Test a single entry */
+		34148798648 << 12,		/* Min */
+		34148798648 << 12,		/* Max */
+		4096,			/* Size of 1 */
+		34148798648 << 12,	/* Location is the same as min/max */
+		0,			/* Success */
 	};
 	int i, range_count = ARRAY_SIZE(range);
 	int req_range_count = ARRAY_SIZE(req_range);
@@ -2660,7 +2674,7 @@ static noinline void check_empty_area_window(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
 
 	mas_reset(&mas);
-	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EBUSY);
+	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
 
 	mas_reset(&mas);
 	mas_empty_area(&mas, 100, 165, 3);
-- 
2.20.1

[PATCH 5/9] maple_tree: Remove an if statement that cannot be true

[Peng Zhang]

Because the commit 06e8fd999334b ("maple_tree: fix mas_empty_area() search")
is merged, this if statement cannot be true, so delete it.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 294d4c8668323..7f4b2ce84ce61 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5084,9 +5084,6 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
 			return true;
 		}
 	}
-
-	if (mte_is_root(mas->node))
-		found = true;
 done:
 	mas->offset = offset;
 	return found;
-- 
2.20.1

[PATCH 6/9] maple_tree: Remove a confusing check

[Peng Zhang]

After this loop, we are at the last slot of a node. Our purpose is to
find an entry that is not NULL, but the pivot is checked here, delete
it, and change to mas_logical_pivot() to get the pivot. Finally, only
check whether the entry is NULL.

Why is this confusing? If the pivot is equal to 0, but if the entry is
not NULL at this time, it will return NULL because of the pivot, but it
should not do this, the entry is valid.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 7f4b2ce84ce61..83441ef2e1f57 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4742,17 +4742,13 @@ static inline void *mas_next_nentry(struct ma_state *mas,
 		return NULL;
 	}
 
-	pivot = mas_safe_pivot(mas, pivots, mas->offset, type);
+	pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
 	entry = mas_slot(mas, slots, mas->offset);
 	if (ma_dead_node(node))
 		return NULL;
 
-	if (!pivot)
-		return NULL;
-
 	if (!entry)
 		return NULL;
-
 found:
 	mas->last = pivot;
 	return entry;
-- 
2.20.1

[PATCH 7/9] maple_tree: Delete redundant code in mas_next_node()

[Peng Zhang]

When offset == node_end is satisfied, go to the parent node, mas->max
will not change. So there is no need to update min on the move.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 7 ++-----
 1 file changed, 2 insertions(+), 5 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 83441ef2e1f57..8bfa837b7b752 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4616,7 +4616,8 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
 	enum maple_type mt;
 	void __rcu **slots;
 
-	if (mas->max >= max)
+	min = mas->max + 1;
+	if (min > max)
 		goto no_entry;
 
 	level = 0;
@@ -4624,10 +4625,6 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
 		if (ma_is_root(node))
 			goto no_entry;
 
-		min = mas->max + 1;
-		if (min > max)
-			goto no_entry;
-
 		if (unlikely(mas_ascend(mas)))
 			return 1;
 
-- 
2.20.1

[PATCH 8/9] maple_tree: Remove the redundant check of mas->offset in mas_empty_area/area_rev()

[Peng Zhang]

In mas_empty_area(), after mas_awalk() returns, if EBUSY is not set,
then mas->offset must be valid, no need to check. Same in
mas_empty_area_rev(), so delete it.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 7 -------
 1 file changed, 7 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 8bfa837b7b752..964214de2ed18 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5305,13 +5305,9 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
 		return xa_err(mas->node);
 
 	offset = mas->offset;
-	if (unlikely(offset == MAPLE_NODE_SLOTS))
-		return -EBUSY;
-
 	mt = mte_node_type(mas->node);
 	pivots = ma_pivots(mas_mn(mas), mt);
 	mas->index = max(mas->index, mas_safe_min(mas, pivots, offset));
-
 	mas->last = mas->index + size - 1;
 	return 0;
 }
@@ -5365,9 +5361,6 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 	if (mas_is_err(mas))
 		return xa_err(mas->node);
 
-	if (unlikely(mas->offset == MAPLE_NODE_SLOTS))
-		return -EBUSY;
-
 	/* Trim the upper limit to the max. */
 	if (max < mas->last)
 		mas->last = max;
-- 
2.20.1

[PATCH 9/9] maple_tree: Move declaration of mas_empty_area_rev() to a better place

[Peng Zhang]

mas_empty_area() and mas_empty_area_rev() are a pair, move
mas_empty_area_rev() so that their declarations are together.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 include/linux/maple_tree.h | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 1fadb5f5978b6..3130c1f822ddf 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -470,6 +470,12 @@ void *mas_next(struct ma_state *mas, unsigned long max);
 
 int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max,
 		   unsigned long size);
+/*
+ * This finds an empty area from the highest address to the lowest.
+ * AKA "Topdown" version,
+ */
+int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
+		       unsigned long max, unsigned long size);
 
 static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,
 			    unsigned long addr)
@@ -493,12 +499,6 @@ static inline bool mas_is_paused(struct ma_state *mas)
 	return mas->node == MAS_PAUSE;
 }
 
-/*
- * This finds an empty area from the highest address to the lowest.
- * AKA "Topdown" version,
- */
-int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
-		       unsigned long max, unsigned long size);
 /**
  * mas_reset() - Reset a Maple Tree operation state.
  * @mas: Maple Tree operation state.
-- 
2.20.1

Re: [PATCH 2/9] maple_tree: Make maple state reusable after mas_empty_area()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
> Make mas->min and mas->max point to a node range instead of a leaf entry
> range. This allows mas to still be usable after mas_empty_area() returns.
> This currently has no user impact because no one use mas after
> mas_empty_area() now.
> 
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 9 +--------
>  1 file changed, 1 insertion(+), 8 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 72099b4b32169..aa55c914818a0 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5320,14 +5320,7 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
>  
>  	mt = mte_node_type(mas->node);
>  	pivots = ma_pivots(mas_mn(mas), mt);
> -	if (offset)
> -		mas->min = pivots[offset - 1] + 1;
> -
> -	if (offset < mt_pivots[mt])
> -		mas->max = pivots[offset];
> -
> -	if (mas->index < mas->min)
> -		mas->index = mas->min;
> +	mas->index = max(mas->index, mas_safe_min(mas, pivots, offset));

It is better to have a few extra lines of code than a complex statement
combined into one line.  Things tend to get missed this way.

>  
>  	mas->last = mas->index + size - 1;
>  	return 0;
> -- 
> 2.20.1
> 

Re: [PATCH 3/9] maple_tree: Modify the allocation method of mtree_alloc_range/rrange()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
> Let mtree_alloc_range() and mtree_alloc_rrange() use mas_empty_area()
> and mas_empty_area_rev() respectively for allocation to reduce code
> redundancy. And after doing this, we don't need to maintain two logically
> identical codes to improve maintainability.
> 
> In fact, mtree_alloc_range/rrange() has some bugs. For example, when
> dealing with min equals to max (mas_empty_area/area_rev() has been fixed),
> the allocation will fail.
> There are still some other bugs in it, I saw it with my naked eyes, but
> I didn't test it, for example:
> When mtree_alloc_range()->mas_alloc()->mas_awalk(), we set mas.index = min,
> mas.last = max - size. However, mas_awalk() requires mas.index = min,
> mas.last = max, which may lead to allocation failures.

Please don't re-state code in your commit messages.

Try to focus on what you did, and not why.

ie: Aligned mtree_alloc_range() to use the same internal function as
mas_empty_area().

> 
> Right now no users are using these two functions so the bug won't trigger,
> but this might trigger in the future.
> 
> Also use mas_store_gfp() instead of mas_fill_gap() as I don't see any
> difference between them.

Yeah, evolution of the code converged on the same design.  Thanks for
seeing this.

> 
> After doing this, we no longer need the three functions
> mas_fill_gap(), mas_alloc(), and mas_rev_alloc().

Let's just drop mtree_alloc_range() and mtree_alloc_rrange() and
whatever else you found here.  They were planned to simplify the mmap
code allocations, but since there would need to be arch involvement
(coloring, etc) and alignment, etc; it is better to leave this job to
the mm code itself.

> 
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 45 ++++++++++++---------------------------------
>  1 file changed, 12 insertions(+), 33 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index aa55c914818a0..294d4c8668323 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6362,32 +6362,20 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
>  {
>  	int ret = 0;
>  
> -	MA_STATE(mas, mt, min, max - size);
> +	MA_STATE(mas, mt, 0, 0);
>  	if (!mt_is_alloc(mt))
>  		return -EINVAL;
>  
>  	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>  		return -EINVAL;
>  
> -	if (min > max)
> -		return -EINVAL;
> -
> -	if (max < size)
> -		return -EINVAL;
> -
> -	if (!size)
> -		return -EINVAL;
> -
>  	mtree_lock(mt);
> -retry:
> -	mas.offset = 0;
> -	mas.index = min;
> -	mas.last = max - size;
> -	ret = mas_alloc(&mas, entry, size, startp);
> -	if (mas_nomem(&mas, gfp))
> -		goto retry;
> -
> +	ret = mas_empty_area(&mas, min, max, size);
> +	if (!ret)
> +		ret = mas_store_gfp(&mas, entry, gfp);
>  	mtree_unlock(mt);
> +	if (!ret)
> +		*startp = mas.index;
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_range);
> @@ -6398,29 +6386,20 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
>  {
>  	int ret = 0;
>  
> -	MA_STATE(mas, mt, min, max - size);
> +	MA_STATE(mas, mt, 0, 0);
>  	if (!mt_is_alloc(mt))
>  		return -EINVAL;
>  
>  	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>  		return -EINVAL;
>  
> -	if (min >= max)
> -		return -EINVAL;
> -
> -	if (max < size - 1)
> -		return -EINVAL;
> -
> -	if (!size)
> -		return -EINVAL;
> -
>  	mtree_lock(mt);
> -retry:
> -	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
> -	if (mas_nomem(&mas, gfp))
> -		goto retry;
> -
> +	ret = mas_empty_area_rev(&mas, min, max, size);
> +	if (!ret)
> +		ret = mas_store_gfp(&mas, entry, gfp);
>  	mtree_unlock(mt);
> +	if (!ret)
> +		*startp = mas.index;
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_rrange);
> -- 
> 2.20.1
> 

Re: [PATCH 4/9] maple_tree: Update mtree_alloc_rrange() and mtree_alloc_range() testing

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
> From: "Liam R. Howlett" <Liam.Howlett@oracle.com>
> 
> The previous changes to the gap searching made this testing fail.
> Unfortunately, there was not a safe update order, so fix the testing
> now.

The testing will need to be updated to use the mas_ family of functions
instead when the mtree_alloc_*() is dropped.

> 
> Fixes: e15e06a83923 ("lib/test_maple_tree: add testing for maple tree")
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> Co-developed-by: Peng Zhang <zhangpeng.00@bytedance.com>
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/test_maple_tree.c | 30 ++++++++++++++++++++++--------
>  1 file changed, 22 insertions(+), 8 deletions(-)
> 
> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> index f1db333270e9f..30f2ebff95d75 100644
> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -102,7 +102,7 @@ static noinline void check_mtree_alloc_rrange(struct maple_tree *mt,
>  	unsigned long result = expected + 1;
>  	int ret;
>  
> -	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end - 1,
> +	ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
>  			GFP_KERNEL);
>  	MT_BUG_ON(mt, ret != eret);
>  	if (ret)
> @@ -680,7 +680,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
>  		0,              /* Return value success. */
>  
>  		0x0,            /* Min */
> -		0x565234AF1 << 12,    /* Max */
> +		0x565234AF0 << 12,    /* Max */
>  		0x3000,         /* Size */
>  		0x565234AEE << 12,  /* max - 3. */
>  		0,              /* Return value success. */
> @@ -692,14 +692,14 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
>  		0,              /* Return value success. */
>  
>  		0x0,            /* Min */
> -		0x7F36D510A << 12,    /* Max */
> +		0x7F36D5109 << 12,    /* Max */
>  		0x4000,         /* Size */
>  		0x7F36D5106 << 12,    /* First rev hole of size 0x4000 */
>  		0,              /* Return value success. */
>  
>  		/* Ascend test. */
>  		0x0,
> -		34148798629 << 12,
> +		34148798628 << 12,
>  		19 << 12,
>  		34148797418 << 12,
>  		0x0,
> @@ -711,6 +711,12 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
>  		0x0,
>  		-EBUSY,
>  
> +		/* Single space test. */
> +		34148798725 << 12,
> +		34148798725 << 12,
> +		1 << 12,
> +		34148798725 << 12,
> +		0,
>  	};
>  
>  	int i, range_count = ARRAY_SIZE(range);
> @@ -759,9 +765,9 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
>  	mas_unlock(&mas);
>  	for (i = 0; i < req_range_count; i += 5) {
>  #if DEBUG_REV_RANGE
> -		pr_debug("\tReverse request between %lu-%lu size %lu, should get %lu\n",
> -				req_range[i] >> 12,
> -				(req_range[i + 1] >> 12) - 1,
> +		pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
> +				i, req_range[i] >> 12,
> +				(req_range[i + 1] >> 12),
>  				req_range[i+2] >> 12,
>  				req_range[i+3] >> 12);
>  #endif
> @@ -777,6 +783,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt)
>  
>  	mt_set_non_kernel(1);
>  	mtree_erase(mt, 34148798727); /* create a deleted range. */
> +	mtree_erase(mt, 34148798725);
>  	check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
>  			34148798725, 0, mt);
>  
> @@ -880,6 +887,13 @@ static noinline void check_alloc_range(struct maple_tree *mt)
>  		4503599618982063UL << 12,  /* Size */
>  		34359052178 << 12,  /* Expected location */
>  		-EBUSY,             /* Return failure. */
> +
> +		/* Test a single entry */
> +		34148798648 << 12,		/* Min */
> +		34148798648 << 12,		/* Max */
> +		4096,			/* Size of 1 */
> +		34148798648 << 12,	/* Location is the same as min/max */
> +		0,			/* Success */
>  	};
>  	int i, range_count = ARRAY_SIZE(range);
>  	int req_range_count = ARRAY_SIZE(req_range);
> @@ -2660,7 +2674,7 @@ static noinline void check_empty_area_window(struct maple_tree *mt)
>  	MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
>  
>  	mas_reset(&mas);
> -	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EBUSY);
> +	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
>  
>  	mas_reset(&mas);
>  	mas_empty_area(&mas, 100, 165, 3);
> -- 
> 2.20.1
> 

Re: [PATCH 5/9] maple_tree: Remove an if statement that cannot be true

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
> Because the commit 06e8fd999334b ("maple_tree: fix mas_empty_area() search")
> is merged, this if statement cannot be true, so delete it.

Please try to focus on what you did and not why you did the change.  You
did the change "Because of the commit..", but that's in the git history if
someone cares to find out.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 3 ---
>  1 file changed, 3 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 294d4c8668323..7f4b2ce84ce61 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5084,9 +5084,6 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size)
>  			return true;
>  		}
>  	}
> -
> -	if (mte_is_root(mas->node))
> -		found = true;
>  done:
>  	mas->offset = offset;
>  	return found;
> -- 
> 2.20.1
> 

Re: [PATCH 6/9] maple_tree: Remove a confusing check

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
> After this loop, we are at the last slot of a node. Our purpose is to
> find an entry that is not NULL, but the pivot is checked here, delete
> it, and change to mas_logical_pivot() to get the pivot. Finally, only
> check whether the entry is NULL.
> 
> Why is this confusing? If the pivot is equal to 0, but if the entry is
> not NULL at this time, it will return NULL because of the pivot, but it
> should not do this, the entry is valid.

Please avoid titles that don't say much at all.. and it's borderline
insulting. I could go into the reasons this was written this way, but
that would be a waste of time.. which is another reason to focus on what
you did in your commit message.

I've removed this function entirely in my patch set, so this isn't
needed.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 6 +-----
>  1 file changed, 1 insertion(+), 5 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 7f4b2ce84ce61..83441ef2e1f57 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4742,17 +4742,13 @@ static inline void *mas_next_nentry(struct ma_state *mas,
>  		return NULL;
>  	}
>  
> -	pivot = mas_safe_pivot(mas, pivots, mas->offset, type);
> +	pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
>  	entry = mas_slot(mas, slots, mas->offset);
>  	if (ma_dead_node(node))
>  		return NULL;
>  
> -	if (!pivot)
> -		return NULL;
> -
>  	if (!entry)
>  		return NULL;
> -
>  found:
>  	mas->last = pivot;
>  	return entry;
> -- 
> 2.20.1
> 

Re: [PATCH 7/9] maple_tree: Delete redundant code in mas_next_node()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:

The title of the patch seems wrong.

This isn't redundant code and you aren't deleting it.. you are moving a
block of code outside a loop.  You did modify the check though, is that
the redundant code?

> When offset == node_end is satisfied, go to the parent node, mas->max
> will not change. So there is no need to update min on the move.

Please try not to state the code in your commit message.

I have moved this block of code in patch 27/34 [1]

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 7 ++-----
>  1 file changed, 2 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 83441ef2e1f57..8bfa837b7b752 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4616,7 +4616,8 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
>  	enum maple_type mt;
>  	void __rcu **slots;
>  
> -	if (mas->max >= max)
> +	min = mas->max + 1;
> +	if (min > max)
>  		goto no_entry;

What happens on overflow?

>  
>  	level = 0;
> @@ -4624,10 +4625,6 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
>  		if (ma_is_root(node))
>  			goto no_entry;
>  
> -		min = mas->max + 1;
> -		if (min > max)
> -			goto no_entry;
> -
>  		if (unlikely(mas_ascend(mas)))
>  			return 1;
>  
> -- 
> 2.20.1
> 

[1] https://lore.kernel.org/linux-mm/20230425140955.3834476-28-Liam.Howlett@oracle.com/

Re: [PATCH 8/9] maple_tree: Remove the redundant check of mas->offset in mas_empty_area/area_rev()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:

The subject doesn't need this much detail.  If mas->offset means
something to people reading through the git logs, they will already be
looking into the change.

> In mas_empty_area(), after mas_awalk() returns, if EBUSY is not set,
> then mas->offset must be valid, no need to check. Same in
> mas_empty_area_rev(), so delete it.

There is a lot of code in this message as well.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 7 -------
>  1 file changed, 7 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 8bfa837b7b752..964214de2ed18 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5305,13 +5305,9 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
>  		return xa_err(mas->node);
>  
>  	offset = mas->offset;
> -	if (unlikely(offset == MAPLE_NODE_SLOTS))
> -		return -EBUSY;
> -
>  	mt = mte_node_type(mas->node);
>  	pivots = ma_pivots(mas_mn(mas), mt);
>  	mas->index = max(mas->index, mas_safe_min(mas, pivots, offset));
> -
>  	mas->last = mas->index + size - 1;
>  	return 0;
>  }
> @@ -5365,9 +5361,6 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
>  	if (mas_is_err(mas))
>  		return xa_err(mas->node);
>  
> -	if (unlikely(mas->offset == MAPLE_NODE_SLOTS))
> -		return -EBUSY;
> -
>  	/* Trim the upper limit to the max. */
>  	if (max < mas->last)
>  		mas->last = max;
> -- 
> 2.20.1
> 

Re: [PATCH 9/9] maple_tree: Move declaration of mas_empty_area_rev() to a better place

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:

Can you change the subject of the patch to remove 'to a better place'?
It sounds like you are killing the declaration and not relocating it.

> mas_empty_area() and mas_empty_area_rev() are a pair, move
> mas_empty_area_rev() so that their declarations are together.
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  include/linux/maple_tree.h | 12 ++++++------
>  1 file changed, 6 insertions(+), 6 deletions(-)
> 
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index 1fadb5f5978b6..3130c1f822ddf 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -470,6 +470,12 @@ void *mas_next(struct ma_state *mas, unsigned long max);
>  
>  int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max,
>  		   unsigned long size);
> +/*
> + * This finds an empty area from the highest address to the lowest.
> + * AKA "Topdown" version,
> + */
> +int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
> +		       unsigned long max, unsigned long size);
>  
>  static inline void mas_init(struct ma_state *mas, struct maple_tree *tree,
>  			    unsigned long addr)
> @@ -493,12 +499,6 @@ static inline bool mas_is_paused(struct ma_state *mas)
>  	return mas->node == MAS_PAUSE;
>  }
>  
> -/*
> - * This finds an empty area from the highest address to the lowest.
> - * AKA "Topdown" version,
> - */
> -int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
> -		       unsigned long max, unsigned long size);
>  /**
>   * mas_reset() - Reset a Maple Tree operation state.
>   * @mas: Maple Tree operation state.
> -- 
> 2.20.1
> 

Re: [PATCH 7/9] maple_tree: Delete redundant code in mas_next_node()

[Peng Zhang]

在 2023/4/26 00:45, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
>
> The title of the patch seems wrong.
>
> This isn't redundant code and you aren't deleting it.. you are moving a
> block of code outside a loop.  You did modify the check though, is that
> the redundant code?
>
>> When offset == node_end is satisfied, go to the parent node, mas->max
>> will not change. So there is no need to update min on the move.
> Please try not to state the code in your commit message.
>
> I have moved this block of code in patch 27/34 [1]
>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 7 ++-----
>>   1 file changed, 2 insertions(+), 5 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 83441ef2e1f57..8bfa837b7b752 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4616,7 +4616,8 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
>>   	enum maple_type mt;
>>   	void __rcu **slots;
>>   
>> -	if (mas->max >= max)
>> +	min = mas->max + 1;
>> +	if (min > max)
>>   		goto no_entry;
> What happens on overflow?
Yes, I made a mistake.
I will drop this patch since you have updated the code in patch 27/34.
>
>>   
>>   	level = 0;
>> @@ -4624,10 +4625,6 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
>>   		if (ma_is_root(node))
>>   			goto no_entry;
>>   
>> -		min = mas->max + 1;
>> -		if (min > max)
>> -			goto no_entry;
>> -
>>   		if (unlikely(mas_ascend(mas)))
>>   			return 1;
>>   
>> -- 
>> 2.20.1
>>
> [1] https://lore.kernel.org/linux-mm/20230425140955.3834476-28-Liam.Howlett@oracle.com/

Re: [PATCH 3/9] maple_tree: Modify the allocation method of mtree_alloc_range/rrange()

[Peng Zhang]

在 2023/4/26 00:08, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
>> Let mtree_alloc_range() and mtree_alloc_rrange() use mas_empty_area()
>> and mas_empty_area_rev() respectively for allocation to reduce code
>> redundancy. And after doing this, we don't need to maintain two logically
>> identical codes to improve maintainability.
>>
>> In fact, mtree_alloc_range/rrange() has some bugs. For example, when
>> dealing with min equals to max (mas_empty_area/area_rev() has been fixed),
>> the allocation will fail.
>> There are still some other bugs in it, I saw it with my naked eyes, but
>> I didn't test it, for example:
>> When mtree_alloc_range()->mas_alloc()->mas_awalk(), we set mas.index = min,
>> mas.last = max - size. However, mas_awalk() requires mas.index = min,
>> mas.last = max, which may lead to allocation failures.
> 
> Please don't re-state code in your commit messages.
> 
> Try to focus on what you did, and not why.
> 
> ie: Aligned mtree_alloc_range() to use the same internal function as
> mas_empty_area().
> 
>>
>> Right now no users are using these two functions so the bug won't trigger,
>> but this might trigger in the future.
>>
>> Also use mas_store_gfp() instead of mas_fill_gap() as I don't see any
>> difference between them.
> 
> Yeah, evolution of the code converged on the same design.  Thanks for
> seeing this.
> 
>>
>> After doing this, we no longer need the three functions
>> mas_fill_gap(), mas_alloc(), and mas_rev_alloc().
> 
> Let's just drop mtree_alloc_range() and mtree_alloc_rrange() and
> whatever else you found here.  They were planned to simplify the mmap
> code allocations, but since there would need to be arch involvement
> (coloring, etc) and alignment, etc; it is better to leave this job to
> the mm code itself.
Ok, I will remove some useless functions here.
But mtree_alloc_range() and mtree_alloc_rrange() really don't need to be 
reserved? Because I don't know if there will be users using it in other 
scenarios in the future.

Thank you for all your suggestions on this patch set, I will update them.
> 
>>
>> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 45 ++++++++++++---------------------------------
>>   1 file changed, 12 insertions(+), 33 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index aa55c914818a0..294d4c8668323 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -6362,32 +6362,20 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
>>   {
>>   	int ret = 0;
>>   
>> -	MA_STATE(mas, mt, min, max - size);
>> +	MA_STATE(mas, mt, 0, 0);
>>   	if (!mt_is_alloc(mt))
>>   		return -EINVAL;
>>   
>>   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>>   		return -EINVAL;
>>   
>> -	if (min > max)
>> -		return -EINVAL;
>> -
>> -	if (max < size)
>> -		return -EINVAL;
>> -
>> -	if (!size)
>> -		return -EINVAL;
>> -
>>   	mtree_lock(mt);
>> -retry:
>> -	mas.offset = 0;
>> -	mas.index = min;
>> -	mas.last = max - size;
>> -	ret = mas_alloc(&mas, entry, size, startp);
>> -	if (mas_nomem(&mas, gfp))
>> -		goto retry;
>> -
>> +	ret = mas_empty_area(&mas, min, max, size);
>> +	if (!ret)
>> +		ret = mas_store_gfp(&mas, entry, gfp);
>>   	mtree_unlock(mt);
>> +	if (!ret)
>> +		*startp = mas.index;
>>   	return ret;
>>   }
>>   EXPORT_SYMBOL(mtree_alloc_range);
>> @@ -6398,29 +6386,20 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
>>   {
>>   	int ret = 0;
>>   
>> -	MA_STATE(mas, mt, min, max - size);
>> +	MA_STATE(mas, mt, 0, 0);
>>   	if (!mt_is_alloc(mt))
>>   		return -EINVAL;
>>   
>>   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>>   		return -EINVAL;
>>   
>> -	if (min >= max)
>> -		return -EINVAL;
>> -
>> -	if (max < size - 1)
>> -		return -EINVAL;
>> -
>> -	if (!size)
>> -		return -EINVAL;
>> -
>>   	mtree_lock(mt);
>> -retry:
>> -	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
>> -	if (mas_nomem(&mas, gfp))
>> -		goto retry;
>> -
>> +	ret = mas_empty_area_rev(&mas, min, max, size);
>> +	if (!ret)
>> +		ret = mas_store_gfp(&mas, entry, gfp);
>>   	mtree_unlock(mt);
>> +	if (!ret)
>> +		*startp = mas.index;
>>   	return ret;
>>   }
>>   EXPORT_SYMBOL(mtree_alloc_rrange);
>> -- 
>> 2.20.1
>>

Re: [PATCH 3/9] maple_tree: Modify the allocation method of mtree_alloc_range/rrange()

[Liam R. Howlett]

* Peng Zhang <perlyzhang@gmail.com> [230426 08:34]:
> 
> 
> 在 2023/4/26 00:08, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230425 07:05]:
> > > Let mtree_alloc_range() and mtree_alloc_rrange() use mas_empty_area()
> > > and mas_empty_area_rev() respectively for allocation to reduce code
> > > redundancy. And after doing this, we don't need to maintain two logically
> > > identical codes to improve maintainability.
> > > 
> > > In fact, mtree_alloc_range/rrange() has some bugs. For example, when
> > > dealing with min equals to max (mas_empty_area/area_rev() has been fixed),
> > > the allocation will fail.
> > > There are still some other bugs in it, I saw it with my naked eyes, but
> > > I didn't test it, for example:
> > > When mtree_alloc_range()->mas_alloc()->mas_awalk(), we set mas.index = min,
> > > mas.last = max - size. However, mas_awalk() requires mas.index = min,
> > > mas.last = max, which may lead to allocation failures.
> > 
> > Please don't re-state code in your commit messages.
> > 
> > Try to focus on what you did, and not why.
> > 
> > ie: Aligned mtree_alloc_range() to use the same internal function as
> > mas_empty_area().
> > 
> > > 
> > > Right now no users are using these two functions so the bug won't trigger,
> > > but this might trigger in the future.
> > > 
> > > Also use mas_store_gfp() instead of mas_fill_gap() as I don't see any
> > > difference between them.
> > 
> > Yeah, evolution of the code converged on the same design.  Thanks for
> > seeing this.
> > 
> > > 
> > > After doing this, we no longer need the three functions
> > > mas_fill_gap(), mas_alloc(), and mas_rev_alloc().
> > 
> > Let's just drop mtree_alloc_range() and mtree_alloc_rrange() and
> > whatever else you found here.  They were planned to simplify the mmap
> > code allocations, but since there would need to be arch involvement
> > (coloring, etc) and alignment, etc; it is better to leave this job to
> > the mm code itself.
> Ok, I will remove some useless functions here.
> But mtree_alloc_range() and mtree_alloc_rrange() really don't need to be
> reserved? Because I don't know if there will be users using it in other
> scenarios in the future.

As you showed, a lot of the code is now the same elsewhere, so it
wouldn't take much to make a version of this outside of the tree if
someone needs the functionality.

> 
> Thank you for all your suggestions on this patch set, I will update them.
> > 
> > > 
> > > Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > ---
> > >   lib/maple_tree.c | 45 ++++++++++++---------------------------------
> > >   1 file changed, 12 insertions(+), 33 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index aa55c914818a0..294d4c8668323 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -6362,32 +6362,20 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
> > >   {
> > >   	int ret = 0;
> > > -	MA_STATE(mas, mt, min, max - size);
> > > +	MA_STATE(mas, mt, 0, 0);
> > >   	if (!mt_is_alloc(mt))
> > >   		return -EINVAL;
> > >   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
> > >   		return -EINVAL;
> > > -	if (min > max)
> > > -		return -EINVAL;
> > > -
> > > -	if (max < size)
> > > -		return -EINVAL;
> > > -
> > > -	if (!size)
> > > -		return -EINVAL;
> > > -
> > >   	mtree_lock(mt);
> > > -retry:
> > > -	mas.offset = 0;
> > > -	mas.index = min;
> > > -	mas.last = max - size;
> > > -	ret = mas_alloc(&mas, entry, size, startp);
> > > -	if (mas_nomem(&mas, gfp))
> > > -		goto retry;
> > > -
> > > +	ret = mas_empty_area(&mas, min, max, size);
> > > +	if (!ret)
> > > +		ret = mas_store_gfp(&mas, entry, gfp);
> > >   	mtree_unlock(mt);
> > > +	if (!ret)
> > > +		*startp = mas.index;
> > >   	return ret;
> > >   }
> > >   EXPORT_SYMBOL(mtree_alloc_range);
> > > @@ -6398,29 +6386,20 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
> > >   {
> > >   	int ret = 0;
> > > -	MA_STATE(mas, mt, min, max - size);
> > > +	MA_STATE(mas, mt, 0, 0);
> > >   	if (!mt_is_alloc(mt))
> > >   		return -EINVAL;
> > >   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
> > >   		return -EINVAL;
> > > -	if (min >= max)
> > > -		return -EINVAL;
> > > -
> > > -	if (max < size - 1)
> > > -		return -EINVAL;
> > > -
> > > -	if (!size)
> > > -		return -EINVAL;
> > > -
> > >   	mtree_lock(mt);
> > > -retry:
> > > -	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
> > > -	if (mas_nomem(&mas, gfp))
> > > -		goto retry;
> > > -
> > > +	ret = mas_empty_area_rev(&mas, min, max, size);
> > > +	if (!ret)
> > > +		ret = mas_store_gfp(&mas, entry, gfp);
> > >   	mtree_unlock(mt);
> > > +	if (!ret)
> > > +		*startp = mas.index;
> > >   	return ret;
> > >   }
> > >   EXPORT_SYMBOL(mtree_alloc_rrange);
> > > -- 
> > > 2.20.1
> > >