Hi,

This patch is intended to provide better support for allocations done with
mmap. As mentioned by Ingo Molnar, keeping the last hole doesn't save us
from scanning vmas because of size constraint.

The following patch implements a simple scheme. The goal is to quickly
return virtual addresses but without scanning the address space at all. It
also works for fixed mappings by reserving areas of virtual addresses.

A global (per mm) cache is maintained from which we can peek ranges of
addresses. There is no link towards vmas. When addresses are cached out they
are simply forgotten. It is then up to the vma users to explicitly cache
out/back areas.

Two of the main functions used for allocations are:

vma_cache_detach(len) returns the first available range of this length
starting from the first block in the cache. The overhead is still very low
since only the cache is scanned (using a first-fit scheme).

vma_cache_area(addr, len) is used to reserve an area from addr to addr+len.
This gives also the possibility to reserve in advance a bunch of virtual
addresses without explicitly mapping them.

Caches are also accessible from /proc/<pid>/freemaps showing free areas
along with their length. Applications willing to map to fixed addresses can
check what is available before doing a mmap().

I guess it could probably give more control on the fragmentation of the
virtual address space too. I successfully ran this patch in a desktop
environment. I also did some simple testing to see how get_unmapped_area()
reacts. Running the kernel 2.5.50 I get
100000 mmaps, mmap=2545 msec munmap=59 msec
100000 mmaps, mmap=2545 msec munmap=58 msec
100000 mmaps, mmap=2544 msec munmap=60 msec
100000 mmaps, mmap=2547 msec munmap=60 msec

and with freemaps I get
100000 mmaps, mmap=79 msec munmap=60 msec
100000 mmaps, mmap=79 msec munmap=60 msec
100000 mmaps, mmap=80 msec munmap=60 msec
100000 mmaps, mmap=79 msec munmap=60 msec

Since there is quite an amazing difference I really would like to have your
comments on this.

I joined a patch against 2.5.50.

Regards,
Frederic