All of lore.kernel.org
 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 [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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.