| Message ID | 87mt2cxb7y.ffs@tglx (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | maple_tree: Fix a few documentation issues | expand |
* Thomas Gleixner <tglx@linutronix.de> [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@linutronix.de> > --- > 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 > */
Liam! On Mon, May 15 2023 at 15:27, Liam R. Howlett wrote: > * Thomas Gleixner <tglx@linutronix.de> [230510 15:01]: >>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. Thanks for the explanation >> >> 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" ? That makes actually sense. >> --- 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). Ack. >> + * 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" Something like that, yes. Let me try again. Thanks, tglx
On Mon, May 15 2023 at 15:27, Liam R. Howlett wrote: > * Thomas Gleixner <tglx@linutronix.de> [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. Without a reference to the actual locking documentation such comments are not super helpful. >> 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" ? >> >> - * >> - * 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). If I understand correctly, this translates to: This iterator skips entries, which have been reserved for future use but have not yet been fully initialized. Right? >> @@ -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" Still confusing to the casual reader like me :) "In case that an entry is found @index is updated to point to the next possible entry independent whether the found entry is occupying a single index or a range if indices." Hmm? Thanks, tglx
* Thomas Gleixner <tglx@linutronix.de> [230516 18:48]: > On Mon, May 15 2023 at 15:27, Liam R. Howlett wrote: > > * Thomas Gleixner <tglx@linutronix.de> [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. > > Without a reference to the actual locking documentation such comments > are not super helpful. Noted. A reference to the larger document should probably be added. Thanks. > > >> 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" ? > >> > >> - * > >> - * 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). > > If I understand correctly, this translates to: > > This iterator skips entries, which have been reserved for future use > but have not yet been fully initialized. > > Right? Well, that's one use of using the XA_ZERO_ENTRY, but it's really up to the user to decide why they are adding something that returns NULL in a specific range for the not-advanced API. It might be worth adding the XA_ZERO_ENTRY in here, since that's the only special value right now? > > >> @@ -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" > > Still confusing to the casual reader like me :) > > "In case that an entry is found @index is updated to point to the next > possible entry independent whether the found entry is occupying a > single index or a range if indices." > > Hmm? That makes sense to me. Thanks, Liam
--- 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. */ #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. * * 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 */
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. 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. 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. Signed-off-by: Thomas Gleixner <tglx@linutronix.de> --- include/linux/maple_tree.h | 4 +--- lib/maple_tree.c | 23 ++++++++++++++++++----- 2 files changed, 19 insertions(+), 8 deletions(-)