[PATCH 01/12] kho: generalize radix tree APIs

[Pratyush Yadav]

On Mon, May 11 2026, Mike Rapoport wrote:

> On Wed, Apr 29, 2026 at 03:39:03PM +0200, Pratyush Yadav wrote:
>> From: "Pratyush Yadav (Google)" <pratyush at kernel.org>
>> 
>> The KHO radix tree is a data structure that can track the presence or
>> absence of an arbitrary key, with nothing inherently tied to KHO memory
>> preservation tracking. This was one of the design goals of the radix
>> tree. This was done to enable it to be re-used by other users of KHO.
>> 
>> Despite that, the radix tree APIs are very closely tied to KHO memory
>> preservation tracking. Adding a key is done by kho_radix_add_page(),
>> which encodes it as a page tracking operation and takes in PFN and
>> order. kho_radix_del_page() does the same. These functions encode the
>> key internally that goes into the radix tree. kho_radix_walk_tree() does
>> the same by baking the PFN and order into the callback arguments.
>> 
>> Generalize the APIs by taking the key directly and doing the encoding at
>> the callers. Rename the functions to kho_radix_add_key() and
>> kho_radix_del_key(). In practice, this removes a line each from the
>> functions and moves the encoding function call to the callers.
>> Similarly, update kho_radix_tree_walk_callback_t to take the key
>> directly.
>> 
>> To keep the naming convention clearer, rename
>> kho_radix_{encode,decode}_key() to kho_{encode,decode}_radix_key().
>> 
>> Signed-off-by: Pratyush Yadav (Google) <pratyush at kernel.org>
>> ---
>>  include/linux/kho_radix_tree.h     | 18 +++----
>>  kernel/liveupdate/kexec_handover.c | 76 ++++++++++++++----------------
>>  2 files changed, 42 insertions(+), 52 deletions(-)
>> 
>> diff --git a/include/linux/kho_radix_tree.h b/include/linux/kho_radix_tree.h
>> index 84e918b96e53..f368f3b9f923 100644
>> --- a/include/linux/kho_radix_tree.h
>> +++ b/include/linux/kho_radix_tree.h
>> @@ -85,7 +85,7 @@ static struct kho_out kho_out = {
>>  };
>>  
>>  /**
>> - * kho_radix_encode_key - Encodes a physical address and order into a radix key.
>> + * kho_encode_radix_key - Encodes a physical address and order into a radix key.
>
> Let's keep kho_radix_ prefix for namespasing please.
> This is the common practice these days.

I am keeping the namespacing, just moving it out of the "kho_radix"
namespace to "kho" namespace. The mental model is that this function has
nothing to do with the radix tree. It is just something KHO uses for one
of its radix tree, so it should live in the "kho" namespace not
"kho_radix".

Does that make sense? I can add this explanation to the commit message
as well.

>
>>   * @phys: The physical address of the page.
>>   * @order: The order of the page.
>>   *
>
> ...
>
>> @@ -144,24 +144,21 @@ static unsigned long kho_radix_get_table_index(unsigned long key,
>>  }
>>  
>>  /**
>> - * kho_radix_add_page - Marks a page as preserved in the radix tree.
>> + * kho_radix_add_key - Add a key to the radix tree.
>>   * @tree: The KHO radix tree.
>> - * @pfn: The page frame number of the page to preserve.
>> - * @order: The order of the page.
>> + * @key: The key to add.
>>   *
>> - * This function traverses the radix tree based on the key derived from @pfn
>> - * and @order. It sets the corresponding bit in the leaf bitmap to mark the
>> - * page for preservation. If intermediate nodes do not exist along the path,
>> - * they are allocated and added to the tree.
>> + * This function traverses the radix tree based on the key provided. It sets the
>
> Nit:                                                     @key here and in
> the comments below.

ACK.

>
>> + * corresponding bit in the leaf bitmap to mark the key as present. If
>> + * intermediate nodes do not exist along the path, they are allocated and added
>> + * to the tree.
>>   *
>>   * Return: 0 on success, or a negative error code on failure.
>>   */

-- 
Regards,
Pratyush Yadav