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

1 files changed, 11 insertions, 0 deletions

diff --git a/vm/vm_map.h b/vm/vm_map.h
index b4ba7c7b..74c86a79 100644
--- a/vm/vm_map.h
+++ b/vm/vm_map.h
@@ -50,6 +50,7 @@
 #include <vm/vm_object.h>
 #include <vm/vm_page.h>
 #include <vm/vm_types.h>
+#include <kern/list.h>
 #include <kern/lock.h>
 #include <kern/rbtree.h>
 #include <kern/macros.h>
@@ -105,9 +106,17 @@ struct vm_map_entry {
 #define vme_start		links.start
 #define vme_end			links.end
 	struct rbtree_node	tree_node;	/* links to other entries in tree */
+	struct rbtree_node	gap_node;	/* links to other entries in gap tree */
+	struct list		gap_list;	/* links to other entries with
+						   the same gap size */
+	vm_size_t		gap_size;	/* size of available memory
+						   following this entry */
 	union vm_map_object	object;		/* object I point to */
 	vm_offset_t		offset;		/* offset into object */
 	unsigned int
+	/* boolean_t */		in_gap_tree:1,	/* entry is in the gap tree if true,
+						   or linked to other entries with
+						   the same gap size if false */
 	/* boolean_t */		is_shared:1,	/* region is shared */
 	/* boolean_t */		is_sub_map:1,	/* Is "object" a submap? */
 	/* boolean_t */		in_transition:1, /* Entry being changed */
@@ -141,6 +150,8 @@ typedef struct vm_map_entry	*vm_map_entry_t;
 struct vm_map_header {
 	struct vm_map_links	links;		/* first, last, min, max */
 	struct rbtree		tree;		/* Sorted tree of entries */
+	struct rbtree		gap_tree;	/* Sorted tree of gap lists
+						   for allocations */
 	int			nentries;	/* Number of entries */
 	boolean_t		entries_pageable;
 						/* are map entries pageable? */