* Thomas Gleixner <tglx@xxxxxxxxxxxxx> [230510 15:01]:
> The documentation of mt_next() claims that it starts the search at the
> provided index. That's incorrect as it starts the search after the provided
> index.
>
> The documentation of mt_find() is slightly confusing. "Handles locking" is
> not really helpful as it does not explain how the "locking" works.
More locking notes can be found in Documentation/core-api/maple_tree.rst
which lists mt_find() under the "Takes RCU read lock" list. I'm okay
with duplicating the comment of taking the RCU read lock in here.
>Also the
> documentation of index talks about a range, while in reality the index
> is updated on a succesful search to the index of the found entry plus one.
This is a range based tree, so the index is incremented beyond the last
entry which would return the entry. That is, if you search for 5 and
there is an entry at 4-100, the index would be 101 after the search -
or, one beyond the range. If you have single entries at a specific
index, then index would be equal to last and it would be one beyond the
index you found - but only because index == last in this case.
>
> Fix similar issues for mt_find_after() and mt_prev().
>
> Remove the completely confusing and pointless "Note: Will not return the
> zero entry." comment from mt_for_each() and document @__index correctly.
The zero entry concept is an advanced API concept which allows you to
store something that cannot be seen by the mt_* family of users, so it
will not be returned and, instead, it will return NULL. Think of it as
a reservation for an entry that isn't fully initialized. Perhaps it
should read "Will not return the XA_ZERO_ENTRY" ?
>
> Signed-off-by: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
> ---
> include/linux/maple_tree.h | 4 +---
> lib/maple_tree.c | 23 ++++++++++++++++++-----
> 2 files changed, 19 insertions(+), 8 deletions(-)
>
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -659,10 +659,8 @@ void *mt_next(struct maple_tree *mt, uns
> * mt_for_each - Iterate over each entry starting at index until max.
> * @__tree: The Maple Tree
> * @__entry: The current entry
> - * @__index: The index to update to track the location in the tree
> + * @__index: The index to start the search from. Subsequently used as iterator.
> * @__max: The maximum limit for @index
> - *
> - * Note: Will not return the zero entry.
This function "will not return the zero entry", meaning it will return
NULL if xa_is_zero(entry).
> */
> #define mt_for_each(__tree, __entry, __index, __max) \
> for (__entry = mt_find(__tree, &(__index), __max); \
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5947,7 +5947,10 @@ EXPORT_SYMBOL_GPL(mas_next);
> * @index: The start index
> * @max: The maximum index to check
> *
> - * Return: The entry at @index or higher, or %NULL if nothing is found.
> + * Takes RCU read lock internally to protect the search, which does not
> + * protect the returned pointer after dropping RCU read lock.
> + *
> + * Return: The entry higher than @index or %NULL if nothing is found.
> */
> void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)
> {
> @@ -6012,7 +6015,10 @@ EXPORT_SYMBOL_GPL(mas_prev);
> * @index: The start index
> * @min: The minimum index to check
> *
> - * Return: The entry at @index or lower, or %NULL if nothing is found.
> + * Takes RCU read lock internally to protect the search, which does not
> + * protect the returned pointer after dropping RCU read lock.
> + *
> + * Return: The entry before @index or %NULL if nothing is found.
> */
> void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min)
> {
> @@ -6487,9 +6493,14 @@ EXPORT_SYMBOL(mtree_destroy);
> * mt_find() - Search from the start up until an entry is found.
> * @mt: The maple tree
> * @index: Pointer which contains the start location of the search
> - * @max: The maximum value to check
> + * @max: The maximum value of the search range
> + *
> + * Takes RCU read lock internally to protect the search, which does not
> + * protect the returned pointer after dropping RCU read lock.
> *
> - * Handles locking. @index will be incremented to one beyond the range.
> + * In case that an entry is found @index contains the index of the found
> + * entry plus one, so it can be used as iterator index to find the next
> + * entry.
What about:
"In case that an entry is found @index contains the last index of the
found entry plus one"
> *
> * Return: The entry at or after the @index or %NULL
> */
> @@ -6548,7 +6559,9 @@ EXPORT_SYMBOL(mt_find);
> * @index: Pointer which contains the start location of the search
> * @max: The maximum value to check
> *
> - * Handles locking, detects wrapping on index == 0
> + * Same as mt_find() except that it checks @index for 0 before
> + * searching. If @index == 0, the search is aborted. This covers a wrap
> + * around of @index to 0 in an iterator loop.
> *
> * Return: The entry at or after the @index or %NULL
> */
