Subject: Re: X server as a Unix system process
To: Jonathan Stone <jonathan@DSG.Stanford.EDU>
From: John S. Dyson <>
List: tech-kern
Date: 07/15/1997 03:54:32
> Linux uses an AVL tree to keep track of the popuulated portions of a
> process's address space.  mmap()ing and un-mmap()ing lots of tiny
> regions works okay there.
AVL trees aren't needed, but the original BSD VM map entry coalesce code needs
work to handle lots of mmaping/munmaping.  I would guess that the AVL trees
could be useful, but I don't think that they are needed to solve the problem
that you are seeing.  FreeBSD has some improvements in this area, but there
are still uncommon pathelogical cases where the VM map can get fragmented.

> Your data suggests that on NetBSD, this runs into a performance bug.
> It looks to me like you're gettin a different chunk of address space
> each time, which is also consistent with a slowly-growing linked list.
> (Where else would the state be kept?)
There are several VM scalability issues that make the system slow down
under various conditions.  The pmap (at least on the X86) from the
original BSD VM code has some problems with scalability also.  Significant
pmap restructuring is needed to improve that situation.  (Micro level
improvements like simple code optimizations don't address the problems.)