From: "Pasha Tatashin" <pasha.tatashin@soleen.com>
To: "Pratyush Yadav" <pratyush@kernel.org>
Cc: "Pasha Tatashin" <pasha.tatashin@soleen.com>,
"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 11:05:46 -0500 [thread overview]
Message-ID: <DMXM4P4NQ6DH.15QJ2AU95YJRT@soleen.com> (raw)
In-Reply-To: <2vxzpkw3fp2y.fsf@kernel.org>
On Tue Nov 17, 2026 at 10:35 AM EST, Pratyush Yadav wrote:
> On Tue, Nov 17 2026, Pratyush Yadav wrote:
>
>> On Mon, Nov 16 2026, Pasha Tatashin wrote:
> [...]
>>> 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.
>
> I take this back. I went and looked at how xarray does it, and it is
> pretty elegant. I thought some sort of rebalancing would be needed, but
> all that is needed is to add a level above the root tree, and demote it
> to a subtree. Similarly, for pruning, the subtree at index 0 can be
> promoted if all other slots of the root are free.
>
> So I'll add dynamic sizing and reparenting logic in v2.
I agree; let's implement this properly from the start. Growing from the
bottom up is the right approach. I am not sure whether support for
shrinking is needed, so that can be added later.
--
Pasha
next prev parent reply other threads:[~2026-11-17 16:05 UTC|newest]
Thread overview: 14+ 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
2026-11-17 15:35 ` Pratyush Yadav
2026-11-17 16:05 ` Pasha Tatashin [this message]
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=DMXM4P4NQ6DH.15QJ2AU95YJRT@soleen.com \
--to=pasha.tatashin@soleen.com \
--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=pratyush@kernel.org \
--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