From: Matthew Wilcox <willy@infradead.org>
To: linux-xfs@vger.kernel.org, linux-fsdevel@vger.kernel.org,
linux-mm@kvack.org
Cc: "Matthew Wilcox (Oracle)" <willy@infradead.org>,
Jeff Layton <jlayton@kernel.org>,
Christoph Hellwig <hch@infradead.org>, Chris Mason <clm@fb.com>
Subject: [PATCH v2 3/9] XArray: Add xarray_for_each_range
Date: Tue, 14 Jan 2020 18:38:37 -0800 [thread overview]
Message-ID: <20200115023843.31325-4-willy@infradead.org> (raw)
In-Reply-To: <20200115023843.31325-1-willy@infradead.org>
From: "Matthew Wilcox (Oracle)" <willy@infradead.org>
This function supports iterating over a range of an array. Also add
documentation links for xarray_for_each_start().
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>
---
Documentation/core-api/xarray.rst | 10 ++++++----
include/linux/xarray.h | 30 ++++++++++++++++++++++++++++++
2 files changed, 36 insertions(+), 4 deletions(-)
diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/xarray.rst
index fcedc5349ace..95a732b5c848 100644
--- a/Documentation/core-api/xarray.rst
+++ b/Documentation/core-api/xarray.rst
@@ -94,10 +94,10 @@ calling xa_clear_mark(). You can ask whether any entry in the
XArray has a particular mark set by calling xa_marked().
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
@@ -180,6 +180,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 86eecbd98e84..a06cb555fe23 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -445,6 +445,36 @@ static inline bool xa_marked(const struct xarray *xa, xa_mark_t mark)
entry; \
entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT))
+/**
+ * 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() - Iterate over present entries in an XArray.
* @xa: XArray.
--
2.24.1
next prev parent reply other threads:[~2020-01-15 2:38 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-01-15 2:38 [RFC v2 0/9] Replacing the readpages a_op Matthew Wilcox
2020-01-15 2:38 ` [PATCH v2 1/9] mm: Fix the return type of __do_page_cache_readahead Matthew Wilcox
2020-01-15 2:38 ` [PATCH v2 2/9] readahead: Ignore return value of ->readpages Matthew Wilcox
2020-01-15 2:38 ` Matthew Wilcox [this message]
2020-01-15 2:38 ` [PATCH v2 4/9] readahead: Put pages in cache earlier Matthew Wilcox
2020-01-15 2:38 ` [PATCH v2 5/9] mm: Add readahead address space operation Matthew Wilcox
2020-01-15 2:38 ` [PATCH v2 6/9] iomap,xfs: Convert from readpages to readahead Matthew Wilcox
2020-01-15 7:16 ` Christoph Hellwig
2020-01-15 7:42 ` Matthew Wilcox
2020-01-24 22:53 ` Matthew Wilcox
2020-01-15 2:38 ` [PATCH v2 7/9] cifs: " Matthew Wilcox
2020-01-15 2:38 ` [PATCH v2 8/9] mm: Remove add_to_page_cache_locked Matthew Wilcox
2020-01-15 2:38 ` [PATCH v2 9/9] mm: Unify all add_to_page_cache variants Matthew Wilcox
2020-01-15 7:20 ` Christoph Hellwig
2020-01-15 7:44 ` Matthew Wilcox
2020-01-18 23:13 ` [RFC v2 0/9] Replacing the readpages a_op Matthew Wilcox
2020-01-21 11:36 ` Jan Kara
2020-01-21 21:48 ` Matthew Wilcox
2020-01-22 9:44 ` Jan Kara
2020-01-23 10:31 ` Jan Kara
2020-01-22 23:47 ` Dave Chinner
2020-01-23 10:21 ` Jan Kara
2020-01-23 22:29 ` Dave Chinner
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200115023843.31325-4-willy@infradead.org \
--to=willy@infradead.org \
--cc=clm@fb.com \
--cc=hch@infradead.org \
--cc=jlayton@kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=linux-xfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).