Re: your mail on mmap() to the kernel list

[Andrea Arcangeli <andrea@suse.de>]

On Tue, Dec 04, 2001 at 02:42:28PM -0200, Rik van Riel wrote:
> On Tue, 4 Dec 2001, Peter Zaitsev wrote:
> > Tuesday, December 04, 2001, 5:15:49 PM, you wrote:
> 
> > AA> You can fix the problem in userspace by using a meaningful 'addr' as
> > AA> hint to mmap(2), or by using MAP_FIXED from userspace, then the kernel
> > AA> won't waste time searching the first available mapping over
> > AA> TASK_UNMAPPED_BASE.
> 
> > Well. Really you can't do this, because you can not really track all of
> > the mappings in user program as glibc and probably other libraries
> > use mmap for their purposes.
> 
> There's no reason we couldn't do this hint in kernel space.
> 
> In arch_get_unmapped_area we can simply keep track of the
> lowest address where we found free space, while on munmap()
> we can adjust this hint if needed.
>
> OTOH, I doubt it would help real-world workloads where the
> application maps and unmaps areas of different sizes and
> actually does something with the memory instead of just
> mapping and unmapping it ;)))

exactly, while that would be simple to implement and very lightweight at
runtime, that's not enough to mathematically drop the complexity of the
get_unmapped_area algorithm. It would optimize only the case where
there's no fragmentation of the mapped virtual address space.

For finding the best fit in the heap with O(log(N)) complexity (rather
than the current O(N) complexity of the linked list) one tree indexed by
the size of each hole would be necessary.

Andrea