Re: [PATCH v3 18/21] kho: extend scratch

[Pratyush Yadav]

On Wed, Jul 15 2026, Mike Rapoport wrote:

>> Motivation
>> ==========
>> 
>> The scratch space is allocated by the first kernel in the KHO chain, and
>> is reused by all subsequent kernels. The size of the space is either set
>> via the commandline by the system administrator or by calculating the
>> amount of memory used by the kernel and adding a multiplier. In either
>> case, the scratch space is a heuristic and is liable to fill up and fail
>> allocation if a kernel uses more memory than expected.
>> 
>> In addition, gigantic huge pages (usually 1 GiB) are allocated via
>> memblock, and in a KHO boot that memory comes from the scratch space. In
>> hypervisors it is common to dedicate a major part of the system's memory
>> to gigantic hugepages for VM memory.
>> 
>> If this memory needs to come from scratch space, then scratch needs to
>> be greater than the memory needed for huge pages, which is impractical.
>> In addition, hugepages can be preserved memory. Allocating them from
>> scratch violates the assumption that scratch contains no preserved
>> memory.
>> 
>> Methodology
>> ===========
>> 
>> Discover areas that don't contain any preserved memory at boot by
>> walking the preserved memory radix tree. Mark them as scratch to allow
>> allocations from them. This makes KHO more resilient to memory pressure
>> and allows supporting huge page preservation.
>> 
>> Since the preserved memory radix tree mixes both physical address and
>> order into a single key, and does not track table pages, it is difficult
>> to identify free areas from it directly. Walk the tree and digest it
>> down into another radix tree. The latter tracks blocks of
>> KHO_EXT_SHIFT (1 GiB as of now) granularity. Then walk the digested tree
>> and mark the areas between the present keys as scratch.
>> 
>> Performance
>> ===========
>> 
>> The discovery algorithm traverses the preserved memory radix tree
>> exactly once. While it does use memory for the digested radix tree,
>> since the blocks are split by 1 GiB, a single bitmap with 4k pages can
>> track up to 32 TiB of memory. So there are likely to be very few radix
>> tree pages used in this tracking. For systems with all physical memory
>> below 32 TiB, this should result in a total of 6 pages being
>> used (KHO_TREE_MAX_DEPTH == 6).
>> 
>> An alternate way of achieving this would be to call kho_mem_retrieve()
>> earlier in boot and mark all the KHO preservations as reserved. But that
>> can blow up memblock.reserved with a bunch of 4K pages scattered
>> everywhere, which will reduce performance of subsequent allocations.
>> Since the free blocks are tracked in chunks of 1 GiB, this won't blow up
>> memblock.memory as much.
>> 
>> There is no inherent reason for using 1 GiB as the discovered block
>> size. This can be changed later if needed. Currently, KHO is mainly
>> targeted for server grade systems with hundreds of gigabytes to
>> terabytes of memory. So 1 GiB is a reasonable granularity for those
>> systems. For smaller systems this doesn't work as well, but we can
>> arrive at a better heuristic when we have concrete use cases.
>> 
>> Practical evaluation
>> ====================
>> 
>> The testing is done on a x86_64 qemu VM running under KVM with 64G
>> memory and 12 CPUs. The machine pre-allocates 50 1G pages.
>> 
>> Since the performance scales with how busy the radix tree is, tests are
>> done with 2 preservation patterns: first with two 1M memfds, second with
>> two 1G memfds, both using 4k pages.
>> 
>> Test case 1 - 1M memfd
>> ~~~~~~~~~~~~~~~~~~~~~~
>> 
>> This test case has two memfds with 1M memory each in 4k pages, plus
>> other preservations from LUO core and other KHO users.
>> 
>> This is how the radix tree stats look like:
>> 
>>     radix_nodes:       0x13
>>     nr_preservations:  0x214
>>     mem_preserved:     0x227000
>> 
>>     per order preservations:
>>       order  0:  0x20f
>>       order  1:  0x4
>>       order  4:  0x1
>> 
>> and this is how long it takes to extend the scratch after KHO boot:
>> 
>>     KHO: KHO extend time: 47 us
>>     KHO: KHO extend total mem: 0xe6c17b000 (~57G)
>> 
>> Test case 2 - 1G memfd
>> ~~~~~~~~~~~~~~~~~~~~~~
>> 
>> This test case has two memfds with 1G memory each in 4k pages, plus
>> other preservations from LUO core and other KHO users.
>> 
>> This is how the radix tree stats look like:
>> 
>>     radix_nodes:       0x28
>>     nr_preservations:  0x80816
>>     mem_preserved:     0x80829000
>> 
>>     per order preservations:
>>       order  0:  0x80811
>>       order  1:  0x4
>>       order  4:  0x1
>> 
>> and this is how long it takes to extend the scratch after KHO boot:
>> 
>>     KHO: KHO extend time: 22514 us
>>     KHO: KHO extend total mem: 0xd3f200000 (~52G)
>> 
>> Signed-off-by: Pratyush Yadav (Google) <pratyush@xxxxxxxxxx>
>>
>> diff --git a/kernel/liveupdate/kexec_handover.c b/kernel/liveupdate/kexec_handover.c
>> index b400976851e76..2c48488746290 100644
>> --- a/kernel/liveupdate/kexec_handover.c
>> +++ b/kernel/liveupdate/kexec_handover.c
>> @@ -84,6 +84,23 @@ static struct kho_out kho_out = {
>>  	},
>>  };
>>  
>> +struct kho_in {
>> +	phys_addr_t fdt_phys;
>> +	phys_addr_t scratch_phys;
>> +	char previous_release[__NEW_UTS_LEN + 1];
>> +	u32 kexec_count;
>> +	struct kho_debugfs dbg;
>> +	struct kho_radix_tree radix_tree;
>> +};
>> +
>> +static struct kho_in kho_in = {
>> +};
>> +
>> +static const void *kho_get_fdt(void)
>> +{
>> +	return kho_in.fdt_phys ? phys_to_virt(kho_in.fdt_phys) : NULL;
>> +}
>> +
>>  /**
>>   * kho_encode_radix_key - Encodes a physical address and order into a radix key.
>>   * @phys: The physical address of the page.
>> @@ -895,6 +912,128 @@ static void __init kho_reserve_scratch(void)
>>  	kho_enable = false;
>>  }
>>  
>> +/*
>> + * Look for free blocks of 1G. This is a heuristic chosen to work efficiently
>> + * with large systems with hundreds of gigabytes of memory. It will work poorly
>> + * on smaller systems. The algorithm itself doesn't depend on the actual value,
>> + * so it can be changed to a different heuristic later if needed.
>> + */
>> +#define KHO_EXT_BLKSIZE		SZ_1G
>> +#define KHO_EXT_SHIFT		const_ilog2(KHO_EXT_BLKSIZE)
>
> Nit: EXT_ what? ;-)
>
>> +
>> +/* Called for the KHO preserved memory radix tree. */
>> +static int __init kho_ext_walk_leaf(unsigned long key, void *data)
>
> I have to say this function still confuses me :)

Honestly, I think this whole tree walking API makes things really hard
to reason about. I think we should replace it with something like
kho_radix_for_each(). It would improve code readability a lot.

I plan to do it at some point, but not as a part of this series.

>
>> +{
>> +	/* Radix tree tracking free blocks. */
>> +	struct kho_radix_tree *tree = data;
>> +	phys_addr_t start, end;
>> +	unsigned int order;
>> +	int err;
>> +
>> +	start = kho_decode_radix_key(key, &order);
>
> I would add a comment here, that the key is from the memory tracker and
> it is decoded to an address.

ACK, will add.

-- 
Regards,
Pratyush Yadav