[PATCH v2 2/4] idr: support optional id tagging

From: Brian Foster
Date: Mon Jul 11 2022 - 09:52:44 EST


Certain idr users can benefit from generic tagging support of the
underlying radix-tree (or xarray) data structure. For example, a
readdir of the /proc root dir performs an inefficient walk of the
pid namespace idr tree. This involves checking the entry of every
allocated id for a group leader task association. Expose a simple,
single tag interface for idr users to facilitate more efficient
scans in situations like this.

Signed-off-by: Brian Foster <bfoster@xxxxxxxxxx>
---
include/linux/idr.h | 26 ++++++++++++++++++++++++++
1 file changed, 26 insertions(+)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index a0dce14090a9..44e8bb287d0e 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -27,6 +27,7 @@ struct idr {
* to users. Use tag 0 to track whether a node has free space below it.
*/
#define IDR_FREE 0
+#define IDR_TAG 1

/* Set the IDR flag and the IDR_FREE tag */
#define IDR_RT_MARKER (ROOT_IS_IDR | (__force gfp_t) \
@@ -174,6 +175,31 @@ static inline void idr_preload_end(void)
local_unlock(&radix_tree_preloads.lock);
}

+static inline void idr_set_tag(struct idr *idr, unsigned long id)
+{
+ radix_tree_tag_set(&idr->idr_rt, id - idr->idr_base, IDR_TAG);
+}
+
+static inline bool idr_get_tag(struct idr *idr, unsigned long id)
+{
+ return radix_tree_tag_get(&idr->idr_rt, id - idr->idr_base, IDR_TAG);
+}
+
+/*
+ * Find the next id with the internal tag set.
+ */
+static inline void *idr_get_next_tag(struct idr *idr, unsigned long id)
+{
+ unsigned int ret;
+ void *entry;
+
+ ret = radix_tree_gang_lookup_tag(&idr->idr_rt, &entry,
+ id - idr->idr_base, 1, IDR_TAG);
+ if (ret != 1)
+ return NULL;
+ return entry;
+}
+
/**
* idr_for_each_entry() - Iterate over an IDR's elements of a given type.
* @idr: IDR handle.
--
2.35.3