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

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]

Date:   Mon, 11 Jul 2022 09:52:35 -0400
From:   Brian Foster <bfoster@...hat.com>
To:     linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org
Cc:     ikent@...hat.com, onestero@...hat.com, willy@...radead.org
Subject: [PATCH v2 2/4] idr: support optional id tagging

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@...hat.com>
---
 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