mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Pratyush Yadav <pratyush@kernel.org>
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 16:35:33 +0100	[thread overview]
Message-ID: <2vxzpkw3fp2y.fsf@kernel.org> (raw)
In-Reply-To: <2vxzwlqbfxtf.fsf@kernel.org> (Pratyush Yadav's message of "Tue, 17 Nov 2026 13:26:52 +0100")

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.

-- 
Regards,
Pratyush Yadav

  reply	other threads:[~2026-11-17 15:35 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 [this message]
2026-11-17 16:05       ` Pasha Tatashin
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=2vxzpkw3fp2y.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

all inboxes | Powered by JetHome®