cvs commit: src/sys/vm vm_map.c vm_map.h

[Alan Cox]

alc         2004-08-13 08:06:34 UTC

  FreeBSD src repository

  Modified files:
    sys/vm               vm_map.c vm_map.h 
  Log:
  Replace the linear search in vm_map_findspace() with an O(log n)
  algorithm built into the map entry splay tree.  This replaces the
  first_free hint in struct vm_map with two fields in vm_map_entry:
  adj_free, the amount of free space following a map entry, and
  max_free, the maximum amount of free space in the entry's subtree.
  These fields make it possible to find a first-fit free region of a
  given size in one pass down the tree, so O(log n) amortized using
  splay trees.
  
  This significantly reduces the overhead in vm_map_findspace() for
  applications that mmap() many hundreds or thousands of regions, and
  has a negligible slowdown (0.1%) on buildworld.  See, for example, the
  discussion of a micro-benchmark titled "Some mmap observations
  compared to Linux 2.6/OpenBSD" on -hackers in late October 2003.
  
  OpenBSD adopted this approach in March 2002, and NetBSD added it in
  November 2003, both with Red-Black trees.
  
  Submitted by: Mark W. Krentel
  
  Revision  Changes    Path
  1.357     +212 -98   src/sys/vm/vm_map.c
  1.116     +2 -1      src/sys/vm/vm_map.h