Re: [patch] mmap-speedup-2.5.42-C3

[Andrew Morton <akpm@digeo.com>]

Ingo Molnar wrote:
> 
> ...
> 
> Saurabh reported a slowdown after the first couple of thousands of
> threads, which i can reproduce as well. The reason for this slowdown is
> the get_unmapped_area() implementation, which tries to achieve the most
> compact virtual memory allocation, by searching for the vma at
> TASK_UNMAPPED_BASE, and then linearly searching for a hole. With thousands
> of linearly allocated vmas this is an increasingly painful thing to do ...

We've had reports of problems with that linear search before - for
a single-threaded application which was mapping a lot of little windows
into a huge file.
 
> ...
> 
> there are various solutions to this problem, none of which solve the
> problem in a 100% sufficient way, so i went for the simplest approach: i
> added code to cache the 'last known hole' address in mm->free_area_cache,
> which is used as a hint to get_unmapped_area().

This will have no effect on current kernel behaviour other than speeding
it up.  Looks good.
 
> ...
> The most generic and still perfectly-compact VM allocation solution would
> be to have a vma tree for the 'inverse virtual memory space', ie. a tree
> of free virtual memory ranges, which could be searched and iterated like
> the space of allocated vmas. I think we could do this by extending vmas,
> but the drawback is larger vmas. This does not save us from having to scan
> vmas linearly still, because the size constraint is still present, but at
> least most of the anon-mmap activities are constant sized. (both malloc()
> and the thread-stack allocator uses mostly fixed sizes.)

Yup.  We'd need to be able to perform a search based on "size of hole"
rather than virtual address.  That really needs a whole new data structure
and supporting search code, I think...  It also may have side effects
to do with fragmentation of the virtual address space.