mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
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


  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 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

all inboxes | Powered by JetHome®