linux-kernel - [PATCH 30/62] xarray: Add xas_find_any / xas_next

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20171122210739.29916-31-willy@infradead.org>
Date:   Wed, 22 Nov 2017 13:07:07 -0800
From:   Matthew Wilcox <willy@...radead.org>
To:     linux-fsdevel@...r.kernel.org, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org
Cc:     Matthew Wilcox <mawilcox@...rosoft.com>
Subject: [PATCH 30/62] xarray: Add xas_find_any / xas_next_any

From: Matthew Wilcox <mawilcox@...rosoft.com>

These variations will find any entry (whether it be NULL or an internal
entry).  The only thing they won't return is a node pointer (because it
will walk down the tree).  xas_next_any() is an inline version of
xas_find_any() which avoids making a function call for the common cases.

Signed-off-by: Matthew Wilcox <mawilcox@...rosoft.com>
---
 include/linux/xarray.h | 25 +++++++++++++++++++++++++
 lib/xarray.c           | 51 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 76 insertions(+)

diff --git a/include/linux/xarray.h b/include/linux/xarray.h
index e0cfe6944752..8ab6c4468c21 100644
--- a/include/linux/xarray.h
+++ b/include/linux/xarray.h
@@ -466,6 +466,7 @@ void *xas_load(struct xarray *, struct xa_state *);
 void *xas_store(struct xarray *, struct xa_state *, void *entry);
 void *xas_create(struct xarray *, struct xa_state *);
 void *xas_find(struct xarray *, struct xa_state *, unsigned long max);
+void *xas_find_any(struct xarray *, struct xa_state *);
 void *xas_prev_any(struct xarray *, struct xa_state *);
 
 bool xas_get_tag(const struct xarray *, const struct xa_state *, xa_tag_t);
@@ -540,6 +541,30 @@ static inline bool xa_iter_skip(void *entry)
 			(xa_is_internal(entry) && entry < XA_RETRY_ENTRY));
 }
 
+/**
+ * xas_next_any() - Advance iterator to next entry of any kind.
+ * @xa: XArray.
+ * @xas: XArray operation state.
+ *
+ * xas_next_any() is an inline function to optimise xarray traversal for speed.
+ * It is equivalent to calling xas_find_any(), and will call xas_find_any()
+ * for all the hard cases.
+ *
+ * Return: The next entry after the one currently referred to by @xas.
+ */
+static inline void *xas_next_any(struct xarray *xa, struct xa_state *xas)
+{
+	struct xa_node *node = xas->xa_node;
+
+	if (unlikely(xas_not_node(node) || node->shift ||
+				xas->xa_offset == XA_CHUNK_MASK))
+		return xas_find_any(xa, xas);
+
+	xas->xa_index++;
+	xas->xa_offset++;
+	return xa_entry(xa, node, xas->xa_offset);
+}
+
 /**
  * xas_next() - Advance iterator to next present entry.
  * @xa: XArray.
diff --git a/lib/xarray.c b/lib/xarray.c
index 202e5aae596d..38e5fe39bb97 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -805,6 +805,57 @@ void xas_pause(struct xa_state *xas)
 }
 EXPORT_SYMBOL_GPL(xas_pause);
 
+/**
+ * xas_find_any() - Find the next entry in the XArray.
+ * @xa: XArray.
+ * @xas: XArray operation state.
+ *
+ * If the xas has not yet been walked to an entry, return the entry
+ * which has an index >= xas.xa_index.  If it has been walked, the entry
+ * currently being pointed at has been processed, and so we move to the
+ * next entry.
+ *
+ * Return: The entry at that location.
+ */
+void *xas_find_any(struct xarray *xa, struct xa_state *xas)
+{
+	void *entry;
+
+	if (xas_error(xas))
+		return NULL;
+
+	if (xas->xa_node == XAS_RESTART) {
+		return xas_load(xa, xas);
+	} else if (!xas->xa_node) {
+		xas->xa_index = 1;
+		xas->xa_node = XAS_RESTART;
+		return NULL;
+	}
+
+	xas->xa_index = next_index(xas->xa_index, xas->xa_node);
+	xas->xa_offset++;
+
+	while (xas->xa_node) {
+		if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) {
+			xas->xa_offset = xas->xa_node->offset + 1;
+			xas->xa_node = xa_parent(xa, xas->xa_node);
+			continue;
+		}
+
+		entry = xa_entry(xa, xas->xa_node, xas->xa_offset);
+		if (!xa_is_node(entry))
+			return entry;
+
+		xas->xa_node = xa_to_node(entry);
+		xas->xa_offset = 0;
+	}
+
+	if (!xas->xa_node)
+		xas->xa_node = XAS_RESTART;
+	return NULL;
+}
+EXPORT_SYMBOL_GPL(xas_find_any);
+
 /**
  * xas_find() - Find the next present entry in the XArray.
  * @xa: XArray.
-- 
2.15.0