Re: [RFC PATCH 0/5] KHO map
From: Pratyush Yadav
Date: Tue Nov 17 2026 - 07:27:07 EST
On Mon, Nov 16 2026, Pasha Tatashin wrote:
>> From: "Pratyush Yadav (Google)" <pratyush@xxxxxxxxxx>
>>
>> Hi,
>>
>> This series introduces the KHO map. It is a sparse map from integer keys
>> to u64 values. It is implemented as a radix tree of fixed depth.
>> Currently the tree depth is 6, so it can support keys up to 54 bits
>> wide.
>>
>> The main user of the map is memfd. Currently memfd uses a vmalloc buffer
>> that has a pair of {index,pfn} to track the folios in the file. That
>> uses 16 bytes per page. The KHO map uses only 8 bytes per page with some
>> overhead. So for a 1 GiB memfd, it uses roughly half the memory.
>>
>> In addition, it is a more versatile data structure. For example, it
>> allows for adding or removing pages from a memfd after preserve more
>> efficiently than the vmalloc array.
>>
>> Post-LPC 2026, the plan is for KHO to maintain backwards compatibility
>> as much as possible. So this data structure allows the serialization
>> format to be more flexible to future changes. It can also be used by the
>> upcoming HugeTLB and guest_memfd preservation.
>>
>> I have talked about this as "KHO xarray" before, but I think using
>> "xarray" is just going to confuse everyone since it isn't really a
>> xarray, and the API works a fair bit differently. So I renamed it to
>> "KHO map".
>>
>> This series isn't complete yet, but it is in fairly good shape so I want
>> to share it to get some early feedback.
>>
>> Things that are missing and planned in the future:
>>
>> - Multi-index entry support: currently, while the map is very efficient
>> with 4k folios, it is horribly inefficient with 2M folios. Each folio
>> in the memfd takes up a full page to track. Multi-index entry support
>> can fix this by tracking entries that cover a whole page in the
>> previous level, similar to page tables.
>
> Let's fix it, see below.
>
>>
>> - LUO versioning support: LUO versioning headers are still in
>> discussion. This data structure should use them for future
>> extensibility. I am mainly waiting for things to settle down there.
>
> I would not worry about this. If versioning lands first, this series can
> be updated then; if this series lands first, Tarun will update his
> series.
Sure, fair enough.
>
>>
>> - Dynamic depth support: Currently the depth is static, so it can only
>> support keys up to 54 bits wide. Adding support for multiple depth
>
> Let's allow keys to cover the full 64-bit space from day 1, and make
> values 63-bit (like XArray), using bit 0 to distinguish a child node
> pointer from a leaf value.
>
> By making it generic from the beginning, we won't need to worry about
> ABI churn for these features later.
Right, that makes sense. I didn't want to over-complicate things, but
you have a point. Taking the ABI complexity up-front is better than the
churn later down the line.
> Instead of caller-chosen depth, the tree should grow (and shrink?)
> dynamically bottom-up based on the widest key.
>
> Plus, with bit 0 tagging leaf values, 2M entries can be stored directly
> at L1 and 1G at L2 (on 4K pages). Even for huge memfds, the pgoff space
> is much smaller than 64 bits, so in practice the tree stays tiny in
> depth.
I think it is a good idea to allow dynamic depth in the ABI, but I am
not sure if we should deal with the automatic resizing just yet. How
about we start with making callers specify the depth (max index/pgoff)
up-front for now? The ABI stays the same, so we can add support for
dynamic resizing later if needed.
The reason for this is to keep things simpler to begin with. That said,
I don't have a _strong_ opinion about this, so if you insist, I can add
dynamic resizing from the get go.
--
Regards,
Pratyush Yadav