@@ -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.
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@redhat.com> --- include/linux/idr.h | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+)