Re: [PATCH 1/3] maple_tree: Make maple state reusable after mas_empty_area_rev()

From: Peng Zhang
Date: Thu Apr 20 2023 - 00:21:13 EST



在 2023/4/20 06:54, Liam R. Howlett 写道:
* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230419 05:02]:
在 2023/4/14 22:57, Liam R. Howlett 写道:
Stop using maple state min/max for the range by passing through pointers
for those values. This will allow the maple state to be reused without
resetting.

Also add some logic to fail out early on searching with invalid
arguments.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
---
lib/maple_tree.c | 27 +++++++++++++--------------
1 file changed, 13 insertions(+), 14 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4df6a0ce1c1b..ed350aa293b2 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4938,7 +4938,8 @@ static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min)
* Return: True if found in a leaf, false otherwise.
*
*/
-static bool mas_rev_awalk(struct ma_state *mas, unsigned long size)
+static bool mas_rev_awalk(struct ma_state *mas, unsigned long size,
+ unsigned long *gap_min, unsigned long *gap_max)
{
enum maple_type type = mte_node_type(mas->node);
struct maple_node *node = mas_mn(mas);
@@ -5003,8 +5004,8 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size)
if (unlikely(ma_is_leaf(type))) {
mas->offset = offset;
- mas->min = min;
- mas->max = min + gap - 1;
+ *gap_min = min;
+ *gap_max = min + gap - 1;
return true;
}
@@ -5280,6 +5281,9 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
unsigned long *pivots;
enum maple_type mt;
+ if (min >= max)
This can lead to errors, min == max is valid.
I think it's better to change it to this:
if (min > max || size == 0 || max - min < size - 1)
I am not sure what it means to search within a range of one. I guess
you would expect it to just return that value if it's empty?
Yes, if min==max, and the value pointed to by this index is empty,
we should return it.

In any case, since we are dealing with pages of data for the VMAs,
having min == max really makes no sense, even with the subtraction of
one in the caller to reduce the max, the min and max should be at least
PAGE_SIZE - 1 apart here.

I think you are right, and I think this needs to be looked at for the
tree on its own, but I don't think it's a problem for the VMA user. I'll
write a testcase and ensure a search for a single entry in a single
entry window works separately. Thanks for pointing this out.
Yes, it's a problem with the tree itself.

+ return -EINVAL;
+
if (mas_is_start(mas))
mas_start(mas);
else if (mas->offset >= 2)
@@ -5334,6 +5338,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
{
struct maple_enode *last = mas->node;
+ if (min >= max)
ditto.
I'll do the search in both directions.
Here is also the same problem with the tree itself as above.
Maybe I didn't understand what you mean. I think the case of
min==max should still be considered in mas_empty_area_rev(),
because mas_empty_area_rev() is a separate interface.

+ return -EINVAL;
+
if (mas_is_start(mas)) {
mas_start(mas);
mas->offset = mas_data_end(mas);
@@ -5353,7 +5360,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
mas->index = min;
mas->last = max;
- while (!mas_rev_awalk(mas, size)) {
+ while (!mas_rev_awalk(mas, size, &min, &max)) {
if (last == mas->node) {
if (!mas_rewind_node(mas))
return -EBUSY;
@@ -5368,17 +5375,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
if (unlikely(mas->offset == MAPLE_NODE_SLOTS))
return -EBUSY;
- /*
- * mas_rev_awalk() has set mas->min and mas->max to the gap values. If
- * the maximum is outside the window we are searching, then use the last
- * location in the search.
- * mas->max and mas->min is the range of the gap.
- * mas->index and mas->last are currently set to the search range.
- */
-
/* Trim the upper limit to the max. */
- if (mas->max <= mas->last)
- mas->last = mas->max;
+ if (max <= mas->last)
+ mas->last = max;
We can get max as follows, without using pointers to track min, max in
mas_rev_awalk().

mt = mte_node_type(mas->node); pivots = ma_pivots(mas_mn(mas), mt); max =
mas_logical_pivot(mas, pivots, mas->offset, mt);
Yes, but why would we do this? We have done all this work already in
mas_rev_awalk(), and we have to do it there to get the offset in the
first place.
Yes, both methods will work.

if (max < mas->last) /* The equal sign here can be removed */
Thanks. I'll keep this in mind when I revisit the function. I don't
want to re-spin the patch for this alone.

mas->last = max;

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