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

[Pranjal Arya]

On 6/15/2026 3:22 PM, Uladzislau Rezki wrote:
> On Sun, Jun 14, 2026 at 12:15:28AM +0100, 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?
>>
> We maintain it in order to split several entities. That prevents
> interfering between allocated data and vmap-free-space manager.
> So in that case one context can easily access allocated data, for
> example vread iterator, etc., whereas another can do an allocation.
> 
> So by splitting parts i minimize lock-contention.
> 
> --
> Uladzislau Rezki

The lock contention concern makes sense, and in the next patch I will
incorporate the suggested changes.

1. find_vmap_area() will be converted to a fully lockless RCU walk.
   With MT_FLAGS_USE_RCU set on vn->busy.mt and call_rcu-deferred
   vmap_area free, callers such as vread_iter and vmalloc_info_show will
   traverse the occupied tree without taking vn->busy.lock.  This will
   eliminate the contention.

2. The global allocator lock will serialise only the gap find & range publish
   pair on the occupied tree. Per node busy lock will be a separate, finer grained
   lock will only need to be held for the busy tree insert after an address
   gets selected.

3. As Matthew noted in his follow up, the maple tree's own RCU safe node
   retirement will need readers holding only rcu_read_lock() giving a consistent
   view of the tree at every index. So the contention reduction goal will be
   met without a separate free index.

BR,
Pranjal