Re: [PATCH] radix-tree: drop 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 <[email protected]>
> Signed-off-by: Jan Beulich <[email protected]>

Reviewed-by: Andrew Cooper <[email protected]>

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