Re: [PATCH v2 31/36] maple_tree: Add mas_prev_range() and mas_find_range_rev interface

[Vernon Yang <vernon2gm@gmail.com>]

On Fri, May 05, 2023 at 01:41:59PM -0400, Liam R. Howlett wrote:
> Some users of the maple tree may want to move to the previous range
> regardless of the value stored there.  Add this interface as well as the
> 'find' variant to support walking to the first value, then iterating
> over the previous ranges.
>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> ---
>  include/linux/maple_tree.h |   1 +
>  lib/maple_tree.c           | 160 +++++++++++++++++++++++++++----------
>  2 files changed, 121 insertions(+), 40 deletions(-)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index a4cd8f891a090..542b09118a09f 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -467,6 +467,7 @@ void mas_destroy(struct ma_state *mas);
>  int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries);
>
>  void *mas_prev(struct ma_state *mas, unsigned long min);
> +void *mas_prev_range(struct ma_state *mas, unsigned long max);
>  void *mas_next(struct ma_state *mas, unsigned long max);
>  void *mas_next_range(struct ma_state *mas, unsigned long max);
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index e050fd1f7cce8..f060c71965c0d 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5924,18 +5924,8 @@ void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)
>  }
>  EXPORT_SYMBOL_GPL(mt_next);
>
> -/**
> - * mas_prev() - Get the previous entry
> - * @mas: The maple state
> - * @min: The minimum value to check.
> - *
> - * Must hold rcu_read_lock or the write lock.
> - * Will reset mas to MAS_START if the node is MAS_NONE.  Will stop on not
> - * searchable nodes.
> - *
> - * Return: the previous value or %NULL.
> - */
> -void *mas_prev(struct ma_state *mas, unsigned long min)
> +static inline bool mas_prev_setup(struct ma_state *mas, unsigned long min,
> +		void **entry)
>  {
>  	if (mas->index <= min)
>  		goto none;
> @@ -5953,7 +5943,8 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
>  		if (!mas->index)
>  			goto none;
>  		mas->index = mas->last = 0;
> -		return mas_root(mas);
> +		*entry = mas_root(mas);
> +		return true;
>  	}
>
>  	if (mas_is_none(mas)) {
> @@ -5961,18 +5952,64 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
>  			/* Walked to out-of-range pointer? */
>  			mas->index = mas->last = 0;
>  			mas->node = MAS_ROOT;
> -			return mas_root(mas);
> +			*entry = mas_root(mas);
> +			return true;
>  		}
> -		return NULL;
> +		return true;
>  	}
> -	return mas_prev_slot(mas, min, false);
> +
> +	return false;
>
>  none:
>  	mas->node = MAS_NONE;
> -	return NULL;
> +	return true;
> +}
> +
> +/**
> + * mas_prev() - Get the previous entry
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Must hold rcu_read_lock or the write lock.
> + * Will reset mas to MAS_START if the node is MAS_NONE.  Will stop on not
> + * searchable nodes.
> + *
> + * Return: the previous value or %NULL.
> + */
> +void *mas_prev(struct ma_state *mas, unsigned long min)
> +{
> +	void *entry = NULL;
> +
> +	if (mas_prev_setup(mas, min, &entry))
> +		return entry;
> +
> +	return mas_prev_slot(mas, min, false);
>  }
>  EXPORT_SYMBOL_GPL(mas_prev);
>
> +/**
> + * mas_prev_range() - Advance to the previous range
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Sets @mas->index and @mas->last to the range.
> + * Must hold rcu_read_lock or the write lock.
> + * Will reset mas to MAS_START if the node is MAS_NONE.  Will stop on not
> + * searchable nodes.
> + *
> + * Return: the previous value or %NULL.
> + */
> +void *mas_prev_range(struct ma_state *mas, unsigned long min)
> +{
> +	void *entry = NULL;
> +
> +	if (mas_prev_setup(mas, min, &entry))
> +		return entry;
> +
> +	return mas_prev_slot(mas, min, true);
> +}
> +EXPORT_SYMBOL_GPL(mas_prev_slot);

Hi Liam,

I guess you want to export mas_prev_range symbol instead of mas_prev_slot.

> +
>  /**
>   * mt_prev() - get the previous value in the maple tree
>   * @mt: The maple tree
> @@ -6116,20 +6153,15 @@ void *mas_find_range(struct ma_state *mas, unsigned long max)
>  EXPORT_SYMBOL_GPL(mas_find_range);
>
>  /**
> - * mas_find_rev: On the first call, find the first non-null entry at or below
> - * mas->index down to %min.  Otherwise find the first non-null entry below
> - * mas->index down to %min.
> - * @mas: The maple state
> - * @min: The minimum value to check.
> + * mas_find_rev_setup() - Internal function to set up mas_find_*_rev()
>   *
> - * Must hold rcu_read_lock or the write lock.
> - * If an entry exists, last and index are updated accordingly.
> - * May set @mas->node to MAS_NONE.
> - *
> - * Return: The entry or %NULL.
> + * Returns: True if entry is the answer, false otherwise.
>   */
> -void *mas_find_rev(struct ma_state *mas, unsigned long min)
> +static inline bool mas_find_rev_setup(struct ma_state *mas, unsigned long min,
> +		void **entry)
>  {
> +	*entry = NULL;
> +
>  	if (unlikely(mas_is_none(mas))) {
>  		if (mas->index <= min)
>  			goto none;
> @@ -6141,7 +6173,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
>  	if (unlikely(mas_is_paused(mas))) {
>  		if (unlikely(mas->index <= min)) {
>  			mas->node = MAS_NONE;
> -			return NULL;
> +			return true;
>  		}
>  		mas->node = MAS_START;
>  		mas->last = --mas->index;
> @@ -6149,14 +6181,12 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
>
>  	if (unlikely(mas_is_start(mas))) {
>  		/* First run or continue */
> -		void *entry;
> -
>  		if (mas->index < min)
> -			return NULL;
> +			return true;
>
> -		entry = mas_walk(mas);
> -		if (entry)
> -			return entry;
> +		*entry = mas_walk(mas);
> +		if (*entry)
> +			return true;
>  	}
>
>  	if (unlikely(!mas_searchable(mas))) {
> @@ -6170,22 +6200,72 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min)
>  			 */
>  			mas->last = mas->index = 0;
>  			mas->node = MAS_ROOT;
> -			return mas_root(mas);
> +			*entry = mas_root(mas);
> +			return true;
>  		}
>  	}
>
>  	if (mas->index < min)
> -		return NULL;
> +		return true;
>
> -	/* Retries on dead nodes handled by mas_prev_slot */
> -	return mas_prev_slot(mas, min, false);
> +	return false;
>
>  none:
>  	mas->node = MAS_NONE;
> -	return NULL;
> +	return true;
> +}
> +
> +/**
> + * mas_find_rev: On the first call, find the first non-null entry at or below
> + * mas->index down to %min.  Otherwise find the first non-null entry below
> + * mas->index down to %min.
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Must hold rcu_read_lock or the write lock.
> + * If an entry exists, last and index are updated accordingly.
> + * May set @mas->node to MAS_NONE.
> + *
> + * Return: The entry or %NULL.
> + */
> +void *mas_find_rev(struct ma_state *mas, unsigned long min)
> +{
> +	void *entry;
> +
> +	if (mas_find_rev_setup(mas, min, &entry))
> +		return entry;
> +
> +	/* Retries on dead nodes handled by mas_prev_slot */
> +	return mas_prev_slot(mas, min, false);
> +
>  }
>  EXPORT_SYMBOL_GPL(mas_find_rev);
>
> +/**
> + * mas_find_range_rev: On the first call, find the first non-null entry at or
> + * below mas->index down to %min.  Otherwise advance to the previous slot after
> + * mas->index down to %min.
> + * @mas: The maple state
> + * @min: The minimum value to check.
> + *
> + * Must hold rcu_read_lock or the write lock.
> + * If an entry exists, last and index are updated accordingly.
> + * May set @mas->node to MAS_NONE.
> + *
> + * Return: The entry or %NULL.
> + */
> +void *mas_find_range_rev(struct ma_state *mas, unsigned long min)
> +{
> +	void *entry;
> +
> +	if (mas_find_rev_setup(mas, min, &entry))
> +		return entry;
> +
> +	/* Retries on dead nodes handled by mas_prev_slot */
> +	return mas_prev_slot(mas, min, true);
> +}
> +EXPORT_SYMBOL_GPL(mas_find_range_rev);
> +
>  /**
>   * mas_erase() - Find the range in which index resides and erase the entire
>   * range.
>
> --
> 2.39.2
>