On Thu, Jul 24, 2025 at 03:28:35PM +0200, Claudio Jeker wrote:
> On Tue, Jul 22, 2025 at 04:29:18PM +0200, Martin Pieuchot wrote:
> > The use of a rb-tree in the current vmmap implementation is responsible
> > for the poor page fault performances we're all experiencing.
> > 
> > To reduce wasted memory in UVM large anonymous segments are chunked into
> > 64k ones.  For example the main firefox process, after starting it, on
> > this laptop has the following:
> > 
> > $ doas procmap -p 9434|wc -l              
> >     6849
> > $ doas procmap -p 9434|grep " 64k"|wc -l
> >     457
> > 
> > Chunking a segment via UVM_MAP_CLIP_START/END was O(1) before using a
> > rbtree and now it requires rebalancing the tree.  This is not only bad
> > for single-threaded performances, it completely kills multi-threaded
> > performances because this operation requires an exclusive lock.
> 
> Why do we clip entries? I thought this is only needed to create submaps
> when things like mlock() or madjust() are called on a part of a larger
> map.

Answering my own question, amap do this if the map is larger than
UVM_AMAP_LARGE (256 slots). Since amaps are very inefficent for storing
sparse allocations (like the stack). Instead of solving this at the amap
layer UVM splits maps into smaller submaps. All of this happens at
uvm_fault time.

I think the bits below still hold. You can replace the rb trie with
something that allows the map splitting without too much pain.
Now fixing this at the amap level would also be interesting, time to
reread that part of UVM again and think about other options.
 
> > Diff below allows multi-threaded process to perform CoW in parallel.
> > Sadly it doesn't gain much because chunking a segment needs an exclusive
> > lock.
> > 
> > Clearly segment chunking is not compatible with the use of a rbtree to
> > store addresses.  Getting rid of chunking would mean follow the Solaris
> > way and allocate a page-table for every segment or follow the
> > Linux/FreeBSD way and go back to a tree of anonymous objects.  Do you
> > see another option?
> 
> I'm certain the there is a datastructure that works well here. To me this
> looks like something a btree could be good at.
>  
> > On the other hand why did we pick a rbtree for vmmap?  Is this really
> > needed?  I really doubt it makes sense to keep this data structure with
> > memory spaces that become bigger and bigger.
> > 
> > Comments?  Ideas?  Inputs?
>  
> From my understanding the rbtree was added because random mmap caused an
> explosion of entries in the vmmap. In original UVM the vmmap is a sorted
> linear list and to improve lookup speed a single cache entry was used
> The idea was that you fault around the same address again. This only works
> if the number of map entries is low. Our processes can have many many
> thousend map entries so a linear search really does not cut it.
> Also the map hint cache is not effective with aggressivly randomized
> address space and multi-threaded applications.
> 
> In general there are other data structures to hold such information. In
> the end the vm_map_entry is all about start and end address of a range.
> 
> -- 
> :wq Claudio
> 

-- 
:wq Claudio