Subject: None
To: John S. Dyson <>
From: Jonathan Stone <jonathan@DSG.Stanford.EDU>
List: tech-kern
Date: 07/15/1997 02:44:07
>> 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,

Hey, I never said they were *needed*, just that Linux *does* have
them.  (And it does.)  And they avoid this particular class of
problems rather well.  I never actually suggested using them myself.

>but the original BSD VM map entry coalesce code needs
>work to handle lots of mmaping/munmaping. 

Yes, I know, that's why I suggested this as a potential problem for an
Linux binary application that's running under emulation mode and which
is performing very badly over time.

> 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.

John, I never said they were *needed*, just that Linux *does* have
them.  (And it does.)  But they do avoid this particular class of
problems rather well.  But if you read a bit more carefully you'd
notice that I never, ever suggested that we use AVL trees as a
solution: just that this wasn't a problem for Linux, which seemed a
vaguely relevant comparison, given that Jukka's problem shows up up
with a commerical Linux binary running on NetBSD in Linux emulation

Of course out *I* didn't read Jukka's post carefully enough at first,
either: the problem is in the XFree86 Xserver on NetBSD, not in the
ApplixWare client at all.  But still, I haven't (yet) suggested that
NetBSD use AVL trees.

How do you feel when when people misquote or misrepresent what you write?

And if you missed the emulation-mode context (Jukka Marin has brought
this up, before, as a LInux-emulation problem), there's there's some
similar FreeBSD-specific context about AVL trees here -- sorry, but I
had absolutely no idea.

>FreeBSD has some improvements in this area, but there
>are still uncommon pathelogical cases where the VM map can get fragmented.
>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.)

Umm, yes, I know, that's why I suggested this as a potential cause,
when I saw Jukka's mmap() trace.  (And why I thought the _comparison_
to AVL trees was apropos.)

The FreeBSD VM system is really pretty good, and I really do
appreciate suggestions and observations from someone who's worked on
the BSD VM code.  (Your fix for the paging problem in NetBSD 1.2 was
spot-on, once you actually beleived to what I told you about the
paging and the audible 1Hz disk-write behaviour :)).
And I don't pretend to know as much about the BSD VM system (either
before your rewrite or after) as you, and the performance numbers from
after look very competitive.  But some of the rest of us have
implemented and tuned VM systems, and have some clue also.

You haven't lived until you've TeXed large documents using a four-page
resident set :).