[PATCH v2 02/18] kho: disallow wide keys in radix tree

[Jork Loeser]

On Fri, 5 Jun 2026, Pratyush Yadav wrote:

> From: "Pratyush Yadav (Google)" <pratyush at kernel.org>
>
> The KHO radix tree was designed to track preserved pages. So it does not
> provide the capability to track any 64-bit key. Instead, it limits the
> key width to how much it needs for tracking PFNs and their orders.
> Limiting the width reduces the number of levels in the tree.
>
> KHO is not expected to be the only user of the radix tree. With the API
> generalized to allow other users, now it is possible to add any key to
> the tree.
>
> Check the key width at kho_radix_add_key(), and error out if it exceeds
> what the tree can handle. Do this instead of increasing the tree depth
> since right now there are no users that need to use wider keys, so this
> avoids memory overhead and ABI breakage.
>
> Signed-off-by: Pratyush Yadav (Google) <pratyush at kernel.org>
> ---
> include/linux/kho/abi/kexec_handover.h |  8 ++++++++
> kernel/liveupdate/kexec_handover.c     | 12 ++++++++++++
> 2 files changed, 20 insertions(+)
>
> diff --git a/include/linux/kho/abi/kexec_handover.h b/include/linux/kho/abi/kexec_handover.h
> index fb2d37417ad9..6dbb98bfb586 100644
> --- a/include/linux/kho/abi/kexec_handover.h
> +++ b/include/linux/kho/abi/kexec_handover.h
> @@ -278,6 +278,14 @@ enum kho_radix_consts {
> 			     KHO_TABLE_SIZE_LOG2) + 1,
> };
>
> +/*
> + * The maximum key width this radix tree can track.
> + *
> + * This value isn't ABI itself, but it is derived from values that are ABI.
> + */
> +#define KHO_RADIX_KEY_WIDTH (((KHO_TREE_MAX_DEPTH - 1) * KHO_TABLE_SIZE_LOG2) + \
> +			     KHO_BITMAP_SIZE_LOG2)

Love the auto-derivation of these values, this totally makes sense. That 
said, my lazy brain complained a bit when I asked it "so how many bits can 
a consumer actually use?". So I wonder:

1) Why is the value not "ABI itself"; it feels like it should as it
    determines client behavior.

2) Would you consider expanding the actual values for the most relevant
    architectures (x86-64 w/ 4kb pages, arm64 w/ 4k/16/64k page-sizes) and
    put it in a block-comment?


> + * NOTE: Currently only keys of width up to %KHO_RADIX_KEY_WIDTH are supported.
> + * This limit only exists because current users of the radix tree don't use more
> + * than that. Changing the maximum width requires changing the tree depth, which
> + * needs bumping the ABI version.

It takes longer to walk the tree. The current implementation is a good 
tradeoff.

Best,
Jork