git: 79b05e7f80eb - main - linuxkpi: Add tag support to radix tree
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Wed, 28 Jan 2026 22:11:32 UTC
The branch main has been updated by dumbbell:
URL: https://cgit.FreeBSD.org/src/commit/?id=79b05e7f80eb482287c700f10da9084824199a05
commit 79b05e7f80eb482287c700f10da9084824199a05
Author: Jean-Sébastien Pédron <dumbbell@FreeBSD.org>
AuthorDate: 2025-09-07 20:53:09 +0000
Commit: Jean-Sébastien Pédron <dumbbell@FreeBSD.org>
CommitDate: 2026-01-28 22:06:56 +0000
linuxkpi: Add tag support to radix tree
The tag is used to perform lookup in a different way.
New functions were introduced:
* to set, check and clear a tag
* to walk through a radix tree based on a given tag
Furthermore, the `radix_tree_delete()` function was modified to clear
tags on deletion.
The amdgpu DRM driver started to use this in Linux 6.10.
While here, the `radix_tree_gang_lookup()` function was added because it
is very close to `radix_tree_gang_lookup_tag()`, but it is not used by
the DRM drivers as of this commit.
Reviewed by: emaste
Sponsored by: The FreeBSD Foundation
Differential Revision: https://reviews.freebsd.org/D54503
---
.../linuxkpi/common/include/linux/radix-tree.h | 29 ++-
sys/compat/linuxkpi/common/src/linux_radix.c | 219 ++++++++++++++++++++-
sys/compat/linuxkpi/common/src/linux_xarray.c | 4 +-
3 files changed, 242 insertions(+), 10 deletions(-)
diff --git a/sys/compat/linuxkpi/common/include/linux/radix-tree.h b/sys/compat/linuxkpi/common/include/linux/radix-tree.h
index 55f0fc949807..7182f4a9e407 100644
--- a/sys/compat/linuxkpi/common/include/linux/radix-tree.h
+++ b/sys/compat/linuxkpi/common/include/linux/radix-tree.h
@@ -38,12 +38,19 @@
#define RADIX_TREE_MAX_HEIGHT \
howmany(sizeof(long) * NBBY, RADIX_TREE_MAP_SHIFT)
+#define RADIX_TREE_MAX_TAGS 3
+#define RADIX_TREE_TAG_LONGS RADIX_TREE_MAP_SIZE
+
#define RADIX_TREE_ENTRY_MASK 3UL
#define RADIX_TREE_EXCEPTIONAL_ENTRY 2UL
#define RADIX_TREE_EXCEPTIONAL_SHIFT 2
+#define RADIX_TREE_ITER_TAG_MASK 0x0f
+#define RADIX_TREE_ITER_TAGGED 0x10
+
struct radix_tree_node {
void *slots[RADIX_TREE_MAP_SIZE];
+ unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
int count;
};
@@ -51,6 +58,8 @@ struct radix_tree_root {
struct radix_tree_node *rnode;
gfp_t gfp_mask;
int height;
+ /* Linux stores root tags inside `gfp_mask`. */
+ unsigned long tags[RADIX_TREE_MAX_TAGS];
};
struct radix_tree_iter {
@@ -64,9 +73,16 @@ struct radix_tree_iter {
#define RADIX_TREE(name, mask) \
struct radix_tree_root name = RADIX_TREE_INIT(mask)
-#define radix_tree_for_each_slot(slot, root, iter, start) \
- for ((iter)->index = (start); \
- radix_tree_iter_find(root, iter, &(slot)); (iter)->index++)
+#define radix_tree_for_each_slot(slot, root, iter, start) \
+ for ((iter)->index = (start); \
+ radix_tree_iter_find(root, iter, &(slot), 0); \
+ (iter)->index++)
+
+#define radix_tree_for_each_slot_tagged(slot, root, iter, start, tag) \
+ for ((iter)->index = (start); \
+ radix_tree_iter_find(root, iter, &(slot), \
+ RADIX_TREE_ITER_TAGGED | tag); \
+ (iter)->index++)
static inline void *
radix_tree_deref_slot(void **slot)
@@ -84,7 +100,12 @@ void *radix_tree_lookup(const struct radix_tree_root *, unsigned long);
void *radix_tree_delete(struct radix_tree_root *, unsigned long);
int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
int radix_tree_store(struct radix_tree_root *, unsigned long, void **);
-bool radix_tree_iter_find(const struct radix_tree_root *, struct radix_tree_iter *, void ***);
+bool radix_tree_iter_find(const struct radix_tree_root *, struct radix_tree_iter *, void ***, int);
void radix_tree_iter_delete(struct radix_tree_root *, struct radix_tree_iter *, void **);
+void *radix_tree_tag_set(struct radix_tree_root *root, unsigned long index, unsigned int tag);
+void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, unsigned int tag);
+int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag);
+unsigned int radix_tree_gang_lookup(const struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items);
+unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag);
#endif /* _LINUXKPI_LINUX_RADIX_TREE_H_ */
diff --git a/sys/compat/linuxkpi/common/src/linux_radix.c b/sys/compat/linuxkpi/common/src/linux_radix.c
index ee6b3a63c370..760f583f25c8 100644
--- a/sys/compat/linuxkpi/common/src/linux_radix.c
+++ b/sys/compat/linuxkpi/common/src/linux_radix.c
@@ -52,6 +52,81 @@ radix_pos(long id, int height)
return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
}
+static inline int
+root_tag_get(const struct radix_tree_root *root, unsigned tag)
+{
+ return (test_bit(tag, root->tags));
+}
+
+static inline void
+root_tag_set(struct radix_tree_root *root, unsigned tag)
+{
+ set_bit(tag, root->tags);
+}
+
+static inline void
+root_tag_clear(struct radix_tree_root *root, unsigned tag)
+{
+ clear_bit(tag, root->tags);
+}
+
+static inline int
+tag_get(const struct radix_tree_node *node, unsigned int tag, int pos)
+{
+ return (test_bit(pos, node->tags[tag]));
+}
+
+static inline void
+tag_set(struct radix_tree_node *node, unsigned int tag, int pos)
+{
+ set_bit(pos, node->tags[tag]);
+}
+
+static inline void
+tag_clear(struct radix_tree_node *node, unsigned int tag, int pos)
+{
+ clear_bit(pos, node->tags[tag]);
+}
+
+static inline bool
+any_tag_set(const struct radix_tree_node *node, unsigned int tag)
+{
+ unsigned int pos;
+
+ for (pos = 0; pos < RADIX_TREE_TAG_LONGS; pos++)
+ if (node->tags[tag][pos])
+ return (true);
+
+ return (false);
+}
+
+static void
+node_tag_clear(struct radix_tree_root *root, struct radix_tree_node *stack[],
+ unsigned long index, unsigned int tag)
+{
+ struct radix_tree_node *node;
+ int height, pos;
+
+ height = 1;
+ node = stack[height];
+
+ while (node && height <= root->height - 1) {
+ pos = radix_pos(index, height);
+ if (!tag_get(node, tag, pos))
+ return;
+
+ tag_clear(node, tag, pos);
+ if (any_tag_set(node, tag))
+ return;
+
+ height++;
+ node = stack[height];
+ }
+
+ if (root_tag_get(root, tag))
+ root_tag_clear(root, tag);
+}
+
static void
radix_tree_clean_root_node(struct radix_tree_root *root)
{
@@ -84,14 +159,70 @@ out:
return (item);
}
+unsigned int
+radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,
+ unsigned long first_index, unsigned int max_items)
+{
+ struct radix_tree_iter iter;
+ void **slot;
+ int count;
+
+ count = 0;
+ if (max_items == 0)
+ return (count);
+
+ radix_tree_for_each_slot(slot, root, &iter, first_index) {
+ results[count] = *slot;
+ if (results[count] == NULL)
+ continue;
+
+ count++;
+ if (count == max_items)
+ break;
+ }
+
+ return (count);
+}
+
+unsigned int
+radix_tree_gang_lookup_tag(const struct radix_tree_root *root,
+ void **results, unsigned long first_index, unsigned int max_items,
+ unsigned int tag)
+{
+ struct radix_tree_iter iter;
+ void **slot;
+ int count;
+
+ count = 0;
+ if (max_items == 0)
+ return (count);
+
+ radix_tree_for_each_slot_tagged(slot, root, &iter, first_index, tag) {
+ results[count] = *slot;
+ if (results[count] == NULL)
+ continue;
+
+ count++;
+ if (count == max_items)
+ break;
+ }
+
+ return (count);
+}
+
bool
radix_tree_iter_find(const struct radix_tree_root *root,
- struct radix_tree_iter *iter, void ***pppslot)
+ struct radix_tree_iter *iter, void ***pppslot, int flags)
{
struct radix_tree_node *node;
unsigned long index = iter->index;
+ unsigned int tag;
int height;
+ tag = flags & RADIX_TREE_ITER_TAG_MASK;
+ if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
+ return (false);
+
restart:
node = root->rnode;
if (node == NULL)
@@ -109,7 +240,9 @@ restart:
*pppslot = node->slots + pos;
next = node->slots[pos];
- if (next == NULL) {
+ if (next == NULL ||
+ (flags & RADIX_TREE_ITER_TAGGED &&
+ !tag_get(next, tag, pos))) {
index += step;
index &= -step;
if ((index & mask) == 0)
@@ -131,6 +264,7 @@ radix_tree_delete(struct radix_tree_root *root, unsigned long index)
void *item;
int height;
int idx;
+ int tag;
item = NULL;
node = root->rnode;
@@ -144,9 +278,15 @@ radix_tree_delete(struct radix_tree_root *root, unsigned long index)
stack[height] = node;
node = node->slots[radix_pos(index, height--)];
}
- idx = radix_pos(index, 0);
- if (node)
+
+ if (node) {
+ idx = radix_pos(index, 0);
item = node->slots[idx];
+
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ node_tag_clear(root, stack, index, tag);
+ }
+
/*
* If we removed something reduce the height of the tree.
*/
@@ -380,3 +520,74 @@ radix_tree_store(struct radix_tree_root *root, unsigned long index, void **ppite
node->count++;
return (0);
}
+
+void *
+radix_tree_tag_set(struct radix_tree_root *root, unsigned long index,
+ unsigned int tag)
+{
+ struct radix_tree_node *node;
+ void *item;
+ int height, pos;
+
+ item = NULL;
+ node = root->rnode;
+ height = root->height - 1;
+ if (index > radix_max(root))
+ goto out;
+
+ while (height) {
+ KASSERT(
+ node != NULL,
+ ("Node at index %lu does not exist in radix tree %p",
+ index, root));
+
+ pos = radix_pos(index, height--);
+ node = node->slots[pos];
+
+ if (!tag_get(node, tag, pos))
+ tag_set(node, tag, pos);
+ }
+
+ item = node->slots[radix_pos(index, 0)];
+
+ root_tag_set(root, tag);
+
+out:
+ return (item);
+}
+
+void *
+radix_tree_tag_clear(struct radix_tree_root *root,
+ unsigned long index, unsigned int tag)
+{
+ struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
+ struct radix_tree_node *node;
+ void *item;
+ int height;
+
+ item = NULL;
+ node = root->rnode;
+ height = root->height - 1;
+ if (index > radix_max(root))
+ goto out;
+
+ while (height && node) {
+ stack[height] = node;
+ node = node->slots[radix_pos(index, height--)];
+ }
+
+ if (node) {
+ item = node->slots[radix_pos(index, 0)];
+
+ node_tag_clear(root, stack, index, tag);
+ }
+
+out:
+ return (item);
+}
+
+int
+radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)
+{
+ return (root_tag_get(root, tag));
+}
diff --git a/sys/compat/linuxkpi/common/src/linux_xarray.c b/sys/compat/linuxkpi/common/src/linux_xarray.c
index 3f07f6d7c59f..8caefbaf7e50 100644
--- a/sys/compat/linuxkpi/common/src/linux_xarray.c
+++ b/sys/compat/linuxkpi/common/src/linux_xarray.c
@@ -389,7 +389,7 @@ __xa_empty(struct xarray *xa)
XA_ASSERT_LOCKED(xa);
- return (!radix_tree_iter_find(&xa->xa_head, &iter, &temp));
+ return (!radix_tree_iter_find(&xa->xa_head, &iter, &temp, 0));
}
bool
@@ -426,7 +426,7 @@ __xa_next(struct xarray *xa, unsigned long *pindex, bool not_first)
return (NULL);
}
- found = radix_tree_iter_find(&xa->xa_head, &iter, &ppslot);
+ found = radix_tree_iter_find(&xa->xa_head, &iter, &ppslot, 0);
if (likely(found)) {
retval = *ppslot;
if (retval == NULL_VALUE)