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 <[email protected]> AuthorDate: 2025-09-07 20:53:09 +0000 Commit: Jean-Sébastien Pédron <[email protected]> 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)
