Linux Kernel Selftest development
 help / color / mirror / Atom feed
From: Pratyush Yadav <pratyush@kernel.org>
To: Pasha Tatashin <pasha.tatashin@soleen.com>
Cc: Pratyush Yadav <pratyush@kernel.org>,
	 Mike Rapoport <rppt@kernel.org>,
	Alexander Graf <graf@amazon.com>,
	 Jonathan Corbet <corbet@lwn.net>,
	Shuah Khan <skhan@linuxfoundation.org>,
	 Randy Dunlap <rdunlap@infradead.org>,
	 Andrew Morton <akpm@linux-foundation.org>,
	Tarun Sahu <tarunsahu@google.com>,
	 David Matlack <dmatlack@google.com>,
	Samiullah Khawaja <skhawaja@google.com>,
	 kexec@lists.infradead.org, linux-mm@kvack.org,
	 linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
	 linux-kselftest@vger.kernel.org
Subject: Re: [RFC PATCH 0/5] KHO map
Date: Tue, 17 Nov 2026 13:26:52 +0100	[thread overview]
Message-ID: <2vxzwlqbfxtf.fsf@kernel.org> (raw)
In-Reply-To: <179486913878.127049.11178890384802388709.b4-review@b4> (Pasha Tatashin's message of "Mon, 16 Nov 2026 17:45:38 -0500")

On Mon, Nov 16 2026, Pasha Tatashin wrote:

>> From: "Pratyush Yadav (Google)" <pratyush@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.

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

  reply	other threads:[~2026-11-17 12:26 UTC|newest]

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16 13:40 [RFC PATCH 0/5] KHO map Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 1/5] kho: add KHOSER_CLEAR_PTR() Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 2/5] kho: build KHO objects into a single kho.o Pratyush Yadav
2026-11-16 20:13   ` Pasha Tatashin
2026-11-17 10:41     ` Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 3/5] kho: add KHO map Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 4/5] kho: test: add KHO map test Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 5/5] mm/memfd_luo: use KHO map for tracking folios Pratyush Yadav
2026-11-16 22:45 ` [RFC PATCH 0/5] KHO map Pasha Tatashin
2026-11-17 12:26   ` Pratyush Yadav [this message]
2026-11-17 15:35     ` Pratyush Yadav
2026-11-17 10:10 ` Chris Down
2026-11-17 12:19   ` Pratyush Yadav

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=2vxzwlqbfxtf.fsf@kernel.org \
    --to=pratyush@kernel.org \
    --cc=akpm@linux-foundation.org \
    --cc=corbet@lwn.net \
    --cc=dmatlack@google.com \
    --cc=graf@amazon.com \
    --cc=kexec@lists.infradead.org \
    --cc=linux-doc@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-kselftest@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=pasha.tatashin@soleen.com \
    --cc=rdunlap@infradead.org \
    --cc=rppt@kernel.org \
    --cc=skhan@linuxfoundation.org \
    --cc=skhawaja@google.com \
    --cc=tarunsahu@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox