Re: [RFC PATCH 0/5] KHO map

From: Pratyush Yadav

Date: Tue Nov 17 2026 - 10:35:43 EST


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