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

[Pranjal Arya]

On 6/16/2026 11:37 PM, Matthew Wilcox wrote:
> On Mon, Jun 15, 2026 at 11:52:22AM +0200, Uladzislau Rezki wrote:
>> On Sun, Jun 14, 2026 at 12:15:28AM +0100, Matthew Wilcox wrote:
>>> 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.
> 
> Sure, but there are many ways to reduce lock contention.  One is to not
> take locks at all; the maple tree is RCU-safe, so you can read the tree
> holding only the RCU read lock, as long as you obey the RCU rules.
> 
> Specifically:
>  - Write side has to RCU-free the objects that are stored in the tree
>  - Read side has to trylock the objects it finds (and retry the walk
>    if the trylock fails)
>  - Read side can see a mixture of objects if the tree is changed while
>    it is reading, but for any given index in the tree it is guaranteed
>    to see one of the objects which has been referred to by that index.
>    That is, if the write side overwrites an index that referred to
>    object A with object B, the reader will see either object A or B.
>    It will not see NULL and it will not see any other object.
>  - If the write side stores both object C and object D in the tree,
>    the read side may see neither, both, only C or only D.

Acknowledged & I'll implement this approach for find_vmap_area():

Write side:
  Every vmap_area that was previously freed with kmem_cache_free() will
  now be freed via call_rcu(&va->rcu, vmap_area_free_rcu).

Read side:
  find_vmap_area() will walk vn->busy.mt under rcu_read_lock()
  using mas_walk() (RCU safe tree traversal) & will then validate
  the found object using READ_ONCE before returning it.

The maple tree guarantees that for any single index the reader will see
either the old or the new object, not NULL. To ensure this, I'll set
MT_FLAGS_USE_RCU on vn->busy.mt in the mt_init_flags() call.

With these changes, find_vmap_area() which is called on every vfree(),
vmalloc_to_page(), vmalloc_to_pfn() will no longer acquire any
spinlock on the lookup path.

Does it sound like a good plan ?

BR,
Pranjal