Radix trees are in principle usable as soon as memory allocation works.
(Radix trees with only index 0 populated are usable even earlier.) If only
there wasn't height_to_maxindex[], which is filled only by a pre-SMP
initcall. The benefit of this array is rather limited - the calculations
done by __maxindex() can as well be done by radix_tree_maxindex(); the
overhead isn't all this high.
Fixes: 21844b0e32e7 ("PCI multi-seg: introduce notion of PCI segments")
Fixes: 8dc6738dbb3c ("Update radix-tree.[ch] from upstream Linux to gain RCU awareness")
Reported-by: Andrew Cooper <andrew.cooper3@citrix.com>
Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
Two Fixes: tags because the use of a pre-SMP initcall was clearly setting
up a trap for later code to fall into.
I know for certain that I've seen logs of Xen running on multi-segment
systems. I can't quite explain how that ended up working.
--- a/xen/common/radix-tree.c
+++ b/xen/common/radix-tree.c
@@ -32,12 +32,6 @@ struct radix_tree_path {
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
RADIX_TREE_MAP_SHIFT))
-/*
- * The height_to_maxindex array needs to be one deeper than the maximum
- * path as height 0 holds only 1 entry.
- */
-static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
-
static inline void *ptr_to_indirect(void *ptr)
{
return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
@@ -80,7 +74,16 @@ static void radix_tree_node_free(struct
*/
static inline unsigned long radix_tree_maxindex(unsigned int height)
{
- return height_to_maxindex[height];
+ unsigned int width = height * RADIX_TREE_MAP_SHIFT;
+ int shift = RADIX_TREE_INDEX_BITS - width;
+
+ if (shift < 0)
+ return ~0UL;
+
+ if (shift >= BITS_PER_LONG)
+ return 0UL;
+
+ return ~0UL >> shift;
}
/*
@@ -705,27 +708,3 @@ void radix_tree_init(struct radix_tree_r
{
*root = (struct radix_tree_root)RADIX_TREE_INIT();
}
-
-static __init unsigned long __maxindex(unsigned int height)
-{
- unsigned int width = height * RADIX_TREE_MAP_SHIFT;
- int shift = RADIX_TREE_INDEX_BITS - width;
-
- if (shift < 0)
- return ~0UL;
- if (shift >= BITS_PER_LONG)
- return 0UL;
- return ~0UL >> shift;
-}
-
-static int __init cf_check radix_tree_init_maxindex(void)
-{
- unsigned int i;
-
- for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
- height_to_maxindex[i] = __maxindex(i);
-
- return 0;
-}
-/* pre-SMP just so it runs before 'normal' initcalls */
-presmp_initcall(radix_tree_init_maxindex);On 04/08/2026 1:30 pm, Jan Beulich wrote:
> Radix trees are in principle usable as soon as memory allocation works.
> (Radix trees with only index 0 populated are usable even earlier.) If only
> there wasn't height_to_maxindex[], which is filled only by a pre-SMP
> initcall. The benefit of this array is rather limited - the calculations
> done by __maxindex() can as well be done by radix_tree_maxindex(); the
> overhead isn't all this high.
It's quite possibly lower overhead. Some simple integer arithmetic vs a
memory read.
I think it's worth noting that this was found by UBSAN on a
multi-segment system:
(XEN) UBSAN: Undefined behaviour in common/radix-tree.c:83:27
(XEN) index 12 is out of range for type 'long unsigned int [12]'
...
(XEN) Xen call trace:
(XEN) [<ffff82d040323f9c>] R common/ubsan/ubsan.c#ubsan_epilogue+0xa/0xd5
(XEN) [<ffff82d040324d91>] F __ubsan_handle_out_of_bounds+0x9d/0xd4
(XEN) [<ffff82d04029265a>] F radix_tree_insert+0x24d/0x570
(XEN) [<ffff82d04037ac3e>] F drivers/passthrough/pci.c#alloc_pseg+0xc4/0x165
(XEN) [<ffff82d040a3b526>] F pci_add_segment+0xc/0x1b
(XEN) [<ffff82d040a5ad1b>] F acpi_parse_mcfg+0x29b/0x344
(XEN) [<ffff82d040a3f612>] F acpi_table_parse+0x5d/0x92
(XEN) [<ffff82d040a5bf55>] F acpi_mmcfg_init+0x3a2/0x71d
(XEN) [<ffff82d040a71ba6>] F pci_setup+0x17/0x29
(XEN) [<ffff82d040a784d0>] F __start_xen+0x394c/0x4ed8
(XEN) [<ffff82d040423057>] F __high_start+0xb7/0xb8
>
> Fixes: 21844b0e32e7 ("PCI multi-seg: introduce notion of PCI segments")
> Fixes: 8dc6738dbb3c ("Update radix-tree.[ch] from upstream Linux to gain RCU awareness")
> Reported-by: Andrew Cooper <andrew.cooper3@citrix.com>
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
All the UBSAN violations are gone.
> ---
> Two Fixes: tags because the use of a pre-SMP initcall was clearly setting
> up a trap for later code to fall into.
>
> I know for certain that I've seen logs of Xen running on multi-segment
> systems. I can't quite explain how that ended up working.
At a guess, we limp along with only segment 0 until dom0 reports the
other segments.
This particular system is set up for GPU testing and the GPU is in
segment 1, so something was working well enough for that to function.
FWIW, there are still issues on this box, even after the fix:
(XEN) setup 0000:fe:00.0 for d0 failed (-19)
(XEN) setup 0000:fe:00.1 for d0 failed (-19)
...
(XEN) setup 0000:ff:19.0 for d0 failed (-19)
(XEN) setup 0000:ff:1a.0 for d0 failed (-19)
(XEN) setup 0001:fe:00.0 for d0 failed (-19)
(XEN) setup 0001:fe:00.1 for d0 failed (-19)
...
(XEN) setup 0001:ff:19.0 for d0 failed (-19)
(XEN) setup 0001:ff:1a.0 for d0 failed (-19)
These are the PCI devices for aspects of the uncore, mostly performance
counters it seems. Despite the lack of information, I think the
complaint is about setting up the IOMMU context for them.
~Andrew
On 04.08.2026 14:58, Andrew Cooper wrote:
> On 04/08/2026 1:30 pm, Jan Beulich wrote:
>> Radix trees are in principle usable as soon as memory allocation works.
>> (Radix trees with only index 0 populated are usable even earlier.) If only
>> there wasn't height_to_maxindex[], which is filled only by a pre-SMP
>> initcall. The benefit of this array is rather limited - the calculations
>> done by __maxindex() can as well be done by radix_tree_maxindex(); the
>> overhead isn't all this high.
>
> It's quite possibly lower overhead. Some simple integer arithmetic vs a
> memory read.
>
> I think it's worth noting that this was found by UBSAN on a
> multi-segment system:
>
> (XEN) UBSAN: Undefined behaviour in common/radix-tree.c:83:27
> (XEN) index 12 is out of range for type 'long unsigned int [12]'
> ...
> (XEN) Xen call trace:
> (XEN) [<ffff82d040323f9c>] R common/ubsan/ubsan.c#ubsan_epilogue+0xa/0xd5
> (XEN) [<ffff82d040324d91>] F __ubsan_handle_out_of_bounds+0x9d/0xd4
> (XEN) [<ffff82d04029265a>] F radix_tree_insert+0x24d/0x570
> (XEN) [<ffff82d04037ac3e>] F drivers/passthrough/pci.c#alloc_pseg+0xc4/0x165
> (XEN) [<ffff82d040a3b526>] F pci_add_segment+0xc/0x1b
> (XEN) [<ffff82d040a5ad1b>] F acpi_parse_mcfg+0x29b/0x344
> (XEN) [<ffff82d040a3f612>] F acpi_table_parse+0x5d/0x92
> (XEN) [<ffff82d040a5bf55>] F acpi_mmcfg_init+0x3a2/0x71d
> (XEN) [<ffff82d040a71ba6>] F pci_setup+0x17/0x29
> (XEN) [<ffff82d040a784d0>] F __start_xen+0x394c/0x4ed8
> (XEN) [<ffff82d040423057>] F __high_start+0xb7/0xb8
Added in.
>> Fixes: 21844b0e32e7 ("PCI multi-seg: introduce notion of PCI segments")
>> Fixes: 8dc6738dbb3c ("Update radix-tree.[ch] from upstream Linux to gain RCU awareness")
>> Reported-by: Andrew Cooper <andrew.cooper3@citrix.com>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>
> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Thanks.
> All the UBSAN violations are gone.
Good.
> FWIW, there are still issues on this box, even after the fix:
>
> (XEN) setup 0000:fe:00.0 for d0 failed (-19)
> (XEN) setup 0000:fe:00.1 for d0 failed (-19)
> ...
> (XEN) setup 0000:ff:19.0 for d0 failed (-19)
> (XEN) setup 0000:ff:1a.0 for d0 failed (-19)
> (XEN) setup 0001:fe:00.0 for d0 failed (-19)
> (XEN) setup 0001:fe:00.1 for d0 failed (-19)
> ...
> (XEN) setup 0001:ff:19.0 for d0 failed (-19)
> (XEN) setup 0001:ff:1a.0 for d0 failed (-19)
>
> These are the PCI devices for aspects of the uncore, mostly performance
> counters it seems. Despite the lack of information, I think the
> complaint is about setting up the IOMMU context for them.
This looks vaguely familiar. Are these devices properly covered by the ACPI
DMAR table? (In the instance where I think I saw such before, they weren't.)
Jan
© 2016 - 2026 Red Hat, Inc.