linuxkpi: Add tag support to radix tree

[dumbbell]

Summary

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.

This is part of the update of DRM drivers to Linux 6.10.

Sponsored by: The FreeBSD Foundation

[bz]

I'll likely not be able to review this before next week; I hope someone else will pick it up so v6.10 can go in.

sys/compat/linuxkpi/common/include/linux/radix-tree.h

103

This changes the KPI but I cannot easily find a consumer outside sys/compat/linuxkpi so it's likely fine. Despite its name it is likely not a public KPI function anyway.

[christos]

sys/compat/linuxkpi/common/src/linux_radix.c

178

In Linux code I see this block here:

		if (radix_tree_is_internal_node(results[ret])) {
			slot = radix_tree_iter_retry(&iter);
			continue;
		}

We don't need it?

204

Ditto.

[emaste]

sys/compat/linuxkpi/common/src/linux_radix.c

178

Looking at Linux history this is fixing a race that doesn't apply to us (or, we're even more fundamentally broken), either way this is OK.

[dumbbell]

sys/compat/linuxkpi/common/include/linux/radix-tree.h

103

Correct, it doesn’t exist on Linux.

sys/compat/linuxkpi/common/src/linux_radix.c

178

Yeah, our implementation never had this notion of "internal node".

[minsoochoo0122_proton.me]

sys/compat/linuxkpi/common/src/linux_radix.c

56

Trivial, but this could be const. Unlike test_bit which shouldn't have const to match signature, root_tag_get is static so adding const wouldn't be problematic. This also applies to other parameters in functions below.

[dumbbell]

sys/compat/linuxkpi/common/src/linux_radix.c

56

I know it’s an internal private function but it matches signature on Linux.