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/[email protected]/
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
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 <[email protected]>
---
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
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 <[email protected]>
---
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
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 <[email protected]>
---
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
* Peng Zhang <[email protected]> [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 <[email protected]>
> ---
> 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
>
* Peng Zhang <[email protected]> [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 <[email protected]>
> ---
> 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/[email protected]/
* Peng Zhang <[email protected]> [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 <[email protected]>
> ---
> 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
>
在 2023/4/26 00:45, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [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 <[email protected]>
>> ---
>> 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/[email protected]/