Date: Sun, 26 Oct 2003 17:09:37 -0600 From: Alan Cox <alc@cs.rice.edu> To: Q <q@onthenet.com.au>, hackers@freebsd.org Cc: dillon@apollo.backplane.com Subject: Re: [Fwd: Some mmap observations compared to Linux 2.6/OpenBSD] Message-ID: <20031026230937.GF20658@cs.rice.edu> In-Reply-To: <1066793641.22245.12.camel@boxster.onthenet.com.au> References: <1066793641.22245.12.camel@boxster.onthenet.com.au>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, Oct 22, 2003 at 01:34:01PM +1000, Q wrote:
> It has been suggested that I should direct this question to the VM
> system guru's. Your comments on this would be appreciated.
>
An address space is represented by a data structure that we call a
vm_map. A vm_map is, in the abstact, an ordered collection of in-use
address ranges.
FreeBSD 4.x implements the vm_map as a doubly-linked list of address
ranges with a hint pointing to the last accessed entry. Thus, if the
hint fails, the expected time to lookup an in-use address is O(n).
FreeBSD 5.x overlays a balanced binary search tree over this
structure. This accelerates the lookup to an (amortized) O(log n).
In fact, for the kind of balanced binary search tree that we use, the
last accessed entry is at the root of the tree. Thus, any locality in
the pattern of lookups will produce even better results.
Linux and OpenBSD are similar to FreeBSD 5.x. The differences lie in
the details, like the kind of balanced binary tree that is used.
That said, having a balanced binary tree to represent the address
space does NOT inherently make finding unallocated space any faster.
Instead, OpenBSD augments an address space entry with extra
information to speed up this process:
struct vm_map_entry {
...
vaddr_t ownspace; /* free space after */
vaddr_t space; /* space in subtree */
...
The same could be done in FreeBSD, and you don't need a red-black tree
in order to do it.
If someone, especially a junior kernel hacker with a commit bit, is
serious about trying this, I'll gladly mentor them. Recognize,
however, that this approach may produce great results for a
microbenchmark, but pessimize other more interesting workloads,
like say, "buildworld", making it a poor choice. Nonetheless, I think
we should strive to get better results in this area.
Regards,
Alan
>
> -----Forwarded Message-----
> From: Q <q@onthenet.com.au>
> To: freebsd-hackers@freebsd.org
> Subject: Some mmap observations compared to Linux 2.6/OpenBSD
> Date: Wed, 22 Oct 2003 12:22:35 +1000
>
> 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.
>
> --
> Seeya...Q
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> _____ / Quinton Dolan - q@OntheNet.com.au
> __ __/ / / __/ / /
> / __ / _/ / / Gold Coast, QLD, Australia
> __/ __/ __/ ____/ / - / Ph: +61 419 729 806
> _______ /
> _\
>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20031026230937.GF20658>