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

[Pratyush Yadav]

On Fri, Jun 05 2026, Jork Loeser wrote:

> On Fri, 5 Jun 2026, Pratyush Yadav wrote:
>
>> From: "Pratyush Yadav (Google)" <pratyush@xxxxxxxxxx>
>>
>> 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@xxxxxxxxxx>
>> ---
>> 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.

The main idea was that if you delve into the details, the value is a
combination of other values, and doesn't directly influence the binary
structure. For example, KHO_ORDER_0_LOG2 (64 - PAGE_SHIFT) influences it
directly. It decides the width of the keys that can be supported.

But now that I think of this again, I think this patch is kind of
stupid. The equation for KHO_RADIX_KEY_WIDTH is exactly the inverse of
the equation KHO_TREE_MAX_DEPTH. The max key width is (KHO_ORDER_0_LOG2
+ 1), and the equation for KHO_TREE_MAX_DEPTH uses that to arrive at the
tree depth.

All this is very obscure unfortunately. First of all, KHO_ORDER_0_LOG2
is a very undescriptive name. I have no idea what it is supposed to mean
or represent. The comment above doesn't help much either and I think is
misleading.

Second, the equation for KHO_TREE_MAX_DEPTH hides in itself the fact
that we need one extra bit on top of KHO_ORDER_0_LOG2. KHO_ORDER_0_LOG2
is essentially the width of PFN. And we need one more bit for the order.
That +1 is hidden in

    DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2 + 1, ...),

I think we should to the following:

1. Rename KHO_ORDER_0_LOG2 to KHO_RADIX_KEY_WIDTH and make its equation
   (64 - PAGE_SHIFT + 1) with the comment above clearly explaining the
   reasoning.

2. Now that the +1 is in the key width itself, the equation for tree
   depth can be simplified to:

       ((KHO_RADIX_KEY_WIDTH - KHO_BITMAP_SIZE_LOG2) / KHO_TABLE_SIZE_LOG2) + 1

   ... which is an improvement I think.

I've been tripped by this radix tree math before, so I think this might
help out a bit. Will fix that in the next version.

>
> 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?

Good idea. Will do.

[...]

-- 
Regards,
Pratyush Yadav