Re: [PATCH RFC 00/12] mm/vmalloc: migrate vmap_area indexing from rb-tree to maple-tree

[Pranjal Arya <pranjal.arya@oss.qualcomm.com>]

[-- Attachment #1: Type: text/plain, Size: 1713 bytes --]


On 6/14/2026 4:45 AM, Matthew Wilcox wrote:
> On Sat, Jun 13, 2026 at 10:49:42PM +0530, Pranjal Arya wrote:
>> vmalloc's free/busy/lazy area tracking is one of the last remaining
>> augmented-rb_tree consumers in the core mm allocators. The rest of
>> mm/ has been gradually consolidating range-keyed indexing around
>> maple_tree (notably the per-process VMA tree in mm/mmap.c), and
>> the underlying reason is a structural mismatch between rb_tree and
>> range tracking:
> First, and most importantly, I love this.  The maple tree is undoubtedly
> the right data structure to use for this purpose.
>
> What I don't understand is why you maintain a separate "free" tree.
> It should not be necessary any more, but maybe you tried removing it
> already and found a performance problem?

Thank you Matthew, that is very encouraging to hear :).  The maple tree's
native range primitives and built in RCU support do make it a much
cleaner fit for vmalloc than the augmented rb tree was.

You are right, and I'm going to remove free tree next patch. Allocation will
use occupied maple tree which will walk the gap space of the
occupied index directly.

The concern that motivated keeping the separate index in the RFC was
lock contention separation. Uladzislau had originally structured things so
that the alloc path could touch the free tree while unrelated readers could
access the occupied tree without blocking each other. Your follow up explanation
of how the maple tree's RCU contract makes a separate free index unnecessary
is the key insight with MT_FLAGS_USE_RCU set on the occupied tree and
call rcu deferred vmap_area free, the same contention reduction is achievable
without maintaining a second index.

[-- Attachment #2: Type: text/html, Size: 2310 bytes --]