vm_map: back allocations with a red-black tree

This change augments VM maps with a gap tree, sorted by gap size, to
use for non-fixed allocations.

* vm/vm_map.c: Include kern/list.h.
(vm_map_entry_gap_cmp_lookup, vm_map_entry_gap_cmp_insert,
vm_map_gap_valid, vm_map_gap_compute, vm_map_gap_insert_single,
vm_map_gap_remove_single, vm_map_gap_update, vm_map_gap_insert,
vm_map_gap_remove, vm_map_find_entry_anywhere): New functions.
(vm_map_setup): Initialize gap tree.
(_vm_map_entry_link): Call vm_map_gap_insert.
(_vm_map_entry_unlink): Call vm_map_gap_remove.
(vm_map_find_entry, vm_map_enter, vm_map_copyout,
vm_map_copyout_page_list, vm_map_copyin): Replace look up loop with
a call to vm_map_find_entry_anywhere. Call vm_map_gap_update and
initialize gap tree where relevant.
(vm_map_copy_insert): Turn macro into an inline function and rewrite.
(vm_map_simplify): Reorder call to vm_map_entry_unlink so that previous
entry is suitable for use with gap management functions.
* vm/vm_map.h: Include kern/list.h.
(struct vm_map_entry): New members `gap_node`, `gap_list`,
`gap_size` and `in_gap_tree`.
(struct vm_map_header): New member `gap_tree`.

0 files changed, 0 insertions, 0 deletions