Re: [PATCH -next] mm: usercopy: add a debugfs interface to bypass the vmalloc check.

[Matthew Wilcox <willy@infradead.org>]

On Wed, Dec 04, 2024 at 09:51:07AM +0100, Uladzislau Rezki wrote:
> I think, when i have more free cycles, i will check it from performance
> point of view. Because i do not know how much a maple tree is efficient
> when it comes to lookups, insert and removing.

Maple tree has a fanout of around 8-12 at each level, while an rbtree has
a fanout of two (arguably 3, since we might find the node).  Let's say you
have 1000 vmalloc areas.  A perfectly balanced rbtree would have 9 levels
(and might well be 11+ levels if imperfectly balanced -- and part of the
advantage of rbtrees over AVL trees is that they can be less balanced
so need fewer rotations).  A perfectly balanced maple tree would have
only 3 levels.

Addition/removal is more expensive.  We biased the implementation heavily
towards lookup, so we chose to keep it very compact.  Most users (and
particularly the VMA tree which was our first client) do more lookups
than modifications; a real application takes many more pagefaults than
it does calls to mmap/munmap/mprotect/etc.

> As an RCU safe data structure, yes, a searching is improved in a way there
> is no need in taking spinlock. As a noted earlier i do not know if a maple 
> tree allows to find a data when instead of key, it is associated with, we
> pass something that is withing a searchable area: [va_start:va_end].

That's what maple trees do; they store non-overlapping ranges.  So you
can look up any address in a range and it will return you the pointer
associated with that range.  Just like you'd want for a page fault ;-)