From nobody Wed Jan 28 22:11:32 2026 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4f1c1k4pZ4z6Phn2 for ; Wed, 28 Jan 2026 22:11:38 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R13" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4f1c1k2Czrz4K1r for ; Wed, 28 Jan 2026 22:11:38 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1769638298; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=fkoUQcfSGMKoLq04jRnbh8K1kM/4PCEWiVUbK66gk0A=; b=KBvRDSztl/4zKfpfdfUjNqKrYhcWv5A8tkvrosspeH2DMNHbkcLBOCGWV5zQlJPoiYSrxG Ep9UNxHpsKwPKvxiH05EDVjlkla98QhfvxR5I+NOh6vhZ/5dAV7+jeYuTUGxPU9jJY3CJv ydNPg//PHjv31zqV67kwncpc7goV+GFAQD4ho4iwSb/u+AuMV1LrqA12wF2fXzKf8eQdfJ wbc/RqKYoMKOm3zXg4PAiiy+0xnNquIyH3Yhd97zqD2+am7534VgJ5mh8DnxMRWpG21gP1 oTRCpfz9RrApEbSWdG/rJa2nBLp3GrnzmA6OjWXb5vJzWtRYtSFsQkbJWdXZIw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1769638298; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=fkoUQcfSGMKoLq04jRnbh8K1kM/4PCEWiVUbK66gk0A=; b=euOyJAU8eS03SBkWZsUfxgF15ZKGbVq/UVHIuACelr/uZ+gqiJJpaCGDd5yduUJ9uFfpTw JIsYrRUeL+srC97QB3fcYDcxEuDXj9lzZcDHBmWkIcS35fP4/kaM5zWtwK/2Mlt80z/bnG I8S0N1ez0R6u/Nsi5vhMkfCy3GmmFZ9mwpp+pVACLw4Z2nvA/nQpTVsgFkJq/lYw6GptUq o/SMTx9OBxHvWEySFZes2KtI6fTkB6Iu6UXBvMJxfpZWDqY0mQnC0H2Oj8hfp7rZsDrhqc pyDQjZWCsu8/ju4rchnmpSOWWODIu1D9lOKNWSbCx9AQk5PhleK8/N8LgaL7qg== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1769638298; a=rsa-sha256; cv=none; b=nRCRAL3hHuc2m2t8jNrFBVb5+zhiv8RIZsSy8zc0HO+YniDLEdhKJ2s8d9ZV+4druIfWVz StsEs1tSJV5sXNNLO+xfbRxx1B9AeZKlkj5VbfulavU2ubQd/0lv4G0KV4u96O8Lf/vg3V IpuBqOpk4LrvgHP8Y2zEWdwODwxQPXUSKdpvC9ofaKTTdx8i8R8FtWnrWMo6OWitC99SsM iMX5zKZ77eMdzkd4/zvD9CWf9FdCxVAtVR7M11JsQVsEvZoGIxm5tQ/s4670hVFTwFODvt f+VDWZx+L90Co0BgDgY1JvJhsCyOIBSkIk5KH8GlJ5XfMXmh7VhYLogW8nUYpg== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) by mxrelay.nyi.freebsd.org (Postfix) with ESMTP id 4f1c1k1m5Mz19fL for ; Wed, 28 Jan 2026 22:11:38 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from git (uid 1279) (envelope-from git@FreeBSD.org) id 3b3ea by gitrepo.freebsd.org (DragonFly Mail Agent v0.13+ on gitrepo.freebsd.org); Wed, 28 Jan 2026 22:11:32 +0000 To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Jean-=?utf-8?Q?S=C3=A9bast?==?utf-8?Q?ien P=C3=A9?=dron Subject: git: 79b05e7f80eb - main - linuxkpi: Add tag support to radix tree List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-all@freebsd.org Sender: owner-dev-commits-src-all@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dumbbell X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 79b05e7f80eb482287c700f10da9084824199a05 Auto-Submitted: auto-generated Date: Wed, 28 Jan 2026 22:11:32 +0000 Message-Id: <697a8994.3b3ea.7aad1e71@gitrepo.freebsd.org> 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 AuthorDate: 2025-09-07 20:53:09 +0000 Commit: Jean-Sébastien Pédron 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)