[RFC PATCH 0/5] KHO map
Pasha Tatashin
pasha.tatashin at soleen.com
Mon Nov 16 14:45:38 PST 2026
> From: "Pratyush Yadav (Google)" <pratyush at kernel.org>
>
> 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.
>
> - 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. 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.
--
Pasha
More information about the kexec
mailing list