Some mmap observations compared to Linux 2.6/OpenBSD

[David Schultz]

On Wed, Oct 22, 2003, Q wrote:
> As an effort to get more acquainted with the FreeBSD kernel, I have been
> looking through how mmap works. I don't yet understand how it all fits
> together, or of the exact implications things may have in the wild, but
> I have noticed under some synthetic conditions, ie. mmaping small
> non-contiguous pages of a file, mmap allocation scales much more poorly
> on FreeBSD than on OpenBSD and Linux 2.6.
> 
> After investigating this further I have observed that vm_map_findspace()
> traverses a linked list to find the next region (O(n) cost), whereas
> OpenBSD and Linux 2.6 both use Red-Black trees for the same purpose
> (O(log n) cost). Profiling the FreeBSD kernel appears to confirm this.
> 
> Can someone comment on whether this is something that has been done
> intentionally, or avoided in favour of some other yet to be implemented
> solution? Or is it still on someones todo list.

This is not, to my knowledge, on anyone's todo list.  Using
red-black trees for VM space allocation is likely to be slower for
the common case where there aren't very many mappings in the first
place, so it's not clear that this ``optimization'' should be a
priority.  I have never seen any real applications that are
mmap-bound as a result of mmapping thousands of tiny regions.
However, if some exist, I'm sure there would be interest in
patches to improve scalability in this area.