From 00ed452c210a0bc1ff3ee79e1ce6b199f00a0638 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Sun, 12 Jan 2020 15:54:10 -0500 Subject: XArray: Add xa_for_each_range This function supports iterating over a range of an array. Also add documentation links for xa_for_each_start(). Signed-off-by: Matthew Wilcox (Oracle) --- Documentation/core-api/xarray.rst | 10 ++++++---- include/linux/xarray.h | 37 ++++++++++++++++++++++++++++++++----- 2 files changed, 38 insertions(+), 9 deletions(-) diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst index 39b61ade7355..640934b6f7b4 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -82,10 +82,10 @@ at that index is ``NULL``, you can use xa_insert() which returns ``-EBUSY`` if the entry is not empty. You can copy entries out of the XArray into a plain array by calling -xa_extract(). Or you can iterate over the present entries in -the XArray by calling xa_for_each(). You may prefer to use -xa_find() or xa_find_after() to move to the next present -entry in the XArray. +xa_extract(). Or you can iterate over the present entries in the XArray +by calling xa_for_each(), xa_for_each_start() or xa_for_each_range(). +You may prefer to use xa_find() or xa_find_after() to move to the next +present entry in the XArray. Calling xa_store_range() stores the same entry in a range of indices. If you do this, some of the other operations will behave @@ -193,6 +193,8 @@ No lock needed: Takes RCU read lock: * xa_load() * xa_for_each() + * xa_for_each_start() + * xa_for_each_range() * xa_find() * xa_find_after() * xa_extract() diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 736afd3aa56f..f73e1775ded0 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -416,6 +416,36 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark) return xa->xa_flags & XA_FLAGS_MARK(mark); } +/** + * xa_for_each_range() - Iterate over a portion of an XArray. + * @xa: XArray. + * @index: Index of @entry. + * @entry: Entry retrieved from array. + * @start: First index to retrieve from array. + * @last: Last index to retrieve from array. + * + * During the iteration, @entry will have the value of the entry stored + * in @xa at @index. You may modify @index during the iteration if you + * want to skip or reprocess indices. It is safe to modify the array + * during the iteration. At the end of the iteration, @entry will be set + * to NULL and @index will have a value less than or equal to max. + * + * xa_for_each_range() is O(n.log(n)) while xas_for_each() is O(n). You have + * to handle your own locking with xas_for_each(), and if you have to unlock + * after each iteration, it will also end up being O(n.log(n)). + * xa_for_each_range() will spin if it hits a retry entry; if you intend to + * see retry entries, you should use the xas_for_each() iterator instead. + * The xas_for_each() iterator will expand into more inline code than + * xa_for_each_range(). + * + * Context: Any context. Takes and releases the RCU lock. + */ +#define xa_for_each_range(xa, index, entry, start, last) \ + for (index = start, \ + entry = xa_find(xa, &index, last, XA_PRESENT); \ + entry; \ + entry = xa_find_after(xa, &index, last, XA_PRESENT)) + /** * xa_for_each_start() - Iterate over a portion of an XArray. * @xa: XArray. @@ -439,11 +469,8 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark) * * Context: Any context. Takes and releases the RCU lock. */ -#define xa_for_each_start(xa, index, entry, start) \ - for (index = start, \ - entry = xa_find(xa, &index, ULONG_MAX, XA_PRESENT); \ - entry; \ - entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT)) +#define xa_for_each_start(xa, index, entry, start) \ + xa_for_each_range(xa, index, entry, start, ULONG_MAX) /** * xa_for_each() - Iterate over present entries in an XArray. -- cgit v1.2.3