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

[Peng Zhang <zhangpeng.00@bytedance.com>]

在 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;