Skip to contentSkip to conversation

maple_tree: Fix a few documentation issues

PATCH Superseded Thomas Gleixner 2 participants 7 messages May 10, 2023 – May 24, 2023

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 maple_tree: Fix a few documentation issues

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.

---
 include/linux/maple_tree.h |    4 +---
 lib/maple_tree.c           |   23 ++++++++++++++++++-----
 2 files changed, 19 insertions(+), 8 deletions(-)
include/linux/maple_tree.h +1 -3
@@ -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); \
lib/maple_tree.c +18 -5
@@ -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
  */
#1 lore raw

Re: your mail

Quoted 6 lines · Thomas Gleixner

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.

Quoted 3 lines

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.

Quoted 5 lines

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" ?

Quoted 10 lines
---
 include/linux/maple_tree.h |    4 +---
 lib/maple_tree.c           |   23 ++++++++++++++++++-----
 2 files changed, 19 insertions(+), 8 deletions(-)

include/linux/maple_tree.h void *mt_next(struct maple_tree *mt, uns · line 665

Quoted 8 lines
include/linux/maple_tree.h +1 -3
@@ -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).

Quoted 33 lines
include/linux/maple_tree.h +0 -0
  */
 #define mt_for_each(__tree, __entry, __index, __max) \
 	for (__entry = mt_find(__tree, &(__index), __max); \
lib/maple_tree.c +8 -2
@@ -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

lib/maple_tree.c EXPORT_SYMBOL(mtree_destroy); · line 6503

Quoted 10 lines
lib/maple_tree.c +7 -2
- * @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"

Quoted 14 lines
lib/maple_tree.c +3 -1
  *
  * 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
  */
#2 lore raw

Re: your mail

Liam!

Quoted 11 lines · Liam R. Howlett
Quoted 3 lines · Thomas Gleixner

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

Quoted 11 lines
Quoted 5 lines

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.

Quoted 6 lines
Quoted 6 lines
include/linux/maple_tree.h +0 -0
@@ -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
Quoted 8 lines

include/linux/maple_tree.h void *mt_next(struct maple_tree *mt, uns · line 665

Quoted 5 lines
include/linux/maple_tree.h +1 -3
- * @__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.

Quoted 11 lines

include/linux/maple_tree.h void *mt_next(struct maple_tree *mt, uns

Quoted 7 lines
include/linux/maple_tree.h +5 -1
+ * 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

#3 lore raw

Re: your mail

In reply to Liam R. Howlett
Quoted 11 lines · Liam R. Howlett
Quoted 6 lines · Thomas Gleixner

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.

Quoted 11 lines
Quoted 4 lines

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" ?

Quoted 1 line
Quoted 5 lines
Quoted 2 lines

- *
- * 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?

Quoted 10 lines
Quoted 10 lines
lib/maple_tree.c +4 -1
@@ -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.
  *
Quoted 8 lines

lib/maple_tree.c EXPORT_SYMBOL(mtree_destroy); · line 6503

Quoted 4 lines
lib/maple_tree.c +3 -1
- * 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

#4 lore raw

Re: your mail

Quoted 9 lines · Thomas Gleixner
Quoted 8 lines · Liam R. Howlett
Quoted 6 lines · Thomas Gleixner

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.

Quoted 6 lines
Quoted 3 lines

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.

Quoted 18 lines
Quoted 12 lines
Quoted 5 lines

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" ?

Quoted 1 line
Quoted 5 lines
Quoted 2 lines

- *
- * 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).

Quoted 6 lines

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?

Quoted 20 lines
Quoted 11 lines
Quoted 11 lines
lib/maple_tree.c +4 -1
@@ -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.
  *
Quoted 8 lines

lib/maple_tree.c EXPORT_SYMBOL(mtree_destroy); · line 6503

Quoted 4 lines
lib/maple_tree.c +3 -1
- * 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"

Quoted 7 lines

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

#5 lore raw

PATCH v2 1/1 maple_tree: Fix a few documentation issues

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().

Reword the confusing "Note: Will not return the zero entry." comment on mt_for_each() and document @__index correctly.

---
V2: Address review feedback. Add pointer to documentation, reword the
zero entry and the index explanations. - Liam

---
 include/linux/maple_tree.h |    5 +++--
 lib/maple_tree.c           |   26 +++++++++++++++++++++-----
 2 files changed, 24 insertions(+), 7 deletions(-)
include/linux/maple_tree.h +3 -2
@@ -659,10 +659,11 @@ 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 iterator skips all entries, which resolve to a NULL pointer,
+ * e.g. entries which has been reserved with XA_ZERO_ENTRY.
  */
 #define mt_for_each(__tree, __entry, __index, __max) \
 	for (__entry = mt_find(__tree, &(__index), __max); \
lib/maple_tree.c +21 -5
@@ -5947,7 +5947,11 @@ 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.
+ * See also: Documentation/core-api/maple_tree.rst
+ *
+ * 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 +6016,11 @@ 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.
+ * See also: Documentation/core-api/maple_tree.rst
+ *
+ * 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 +6495,15 @@ 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
  *
- * Handles locking.  @index will be incremented to one beyond the range.
+ * Takes RCU read lock internally to protect the search, which does not
+ * protect the returned pointer after dropping RCU read lock.
+ * See also: Documentation/core-api/maple_tree.rst
+ *
+ * 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.
  *
  * Return: The entry at or after the @index or %NULL
  */
@@ -6548,7 +6562,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
  */
Reviewed-by on v2 1/1
#6 lore raw
Quoted 9 lines · Thomas Gleixner

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.

Quoted 6 lines

Fix similar issues for mt_find_after() and mt_prev().

Reword the confusing "Note: Will not return the zero entry." comment on mt_for_each() and document @__index correctly.

Quoted 81 lines

---
V2: Address review feedback. Add pointer to documentation, reword the
zero entry and the index explanations. - Liam

---
 include/linux/maple_tree.h |    5 +++--
 lib/maple_tree.c           |   26 +++++++++++++++++++++-----
 2 files changed, 24 insertions(+), 7 deletions(-)
include/linux/maple_tree.h +3 -2
@@ -659,10 +659,11 @@ 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 iterator skips all entries, which resolve to a NULL pointer,
+ * e.g. entries which has been reserved with XA_ZERO_ENTRY.
  */
 #define mt_for_each(__tree, __entry, __index, __max) \
 	for (__entry = mt_find(__tree, &(__index), __max); \
lib/maple_tree.c +21 -5
@@ -5947,7 +5947,11 @@ 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.
+ * See also: Documentation/core-api/maple_tree.rst
+ *
+ * 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 +6016,11 @@ 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.
+ * See also: Documentation/core-api/maple_tree.rst
+ *
+ * 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 +6495,15 @@ 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
  *
- * Handles locking.  @index will be incremented to one beyond the range.
+ * Takes RCU read lock internally to protect the search, which does not
+ * protect the returned pointer after dropping RCU read lock.
+ * See also: Documentation/core-api/maple_tree.rst
+ *
+ * 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.
  *
  * Return: The entry at or after the @index or %NULL
  */
@@ -6548,7 +6562,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
  */