| Message ID | 20230414145728.4067069-1-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | [1/3] maple_tree: Make maple state reusable after mas_empty_area_rev() | expand |
在 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@oracle.com> > --- > 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) > + 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. > + 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); if (max < mas->last) /* The equal sign here can be removed */ mas->last = max; > > mas->index = mas->last - size + 1; > return 0;
* Peng Zhang <zhangpeng.00@bytedance.com> [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@oracle.com> > > --- > > 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? 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. > > + 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. > > + 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. > 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;
在 2023/4/20 06:54, Liam R. Howlett 写道: > * Peng Zhang <zhangpeng.00@bytedance.com> [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@oracle.com> >>> --- >>> 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;
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) + 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) + 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; mas->index = mas->last - size + 1; return 0;
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@oracle.com> --- lib/maple_tree.c | 27 +++++++++++++-------------- 1 file changed, 13 insertions(+), 14 deletions(-)