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

[Dag-Erling Smørgrav]

Alan Cox <alc at FreeBSD.org> writes:
>   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.

Great!  I've been meaning to do this for a while, but the complexity
was a bit beyond me.  This should greatly increase pipe performance,
by the way, because pipe buffers are allocated from a single vm_map,
which accumulates many more entries and much more fragmentation than
(probably) most other maps in the kernel.

DES
-- 
Dag-Erling Smørgrav - des at des.no