Augment VM maps with a red-black tree

* vm/vm_map.c: Add #include <kern/rbtree.h>.
(vm_map_setup): Initialize the map red-black tree.
(vm_map_entry_cmp_lookup): New function.
(vm_map_entry_cmp_insert): Likewise.
(_vm_map_entry_link): Insert map entry in the red-black tree.
(_vm_map_entry_unlink): Remove map entry from the red-black tree.
(vm_map_lookup_entry): Rework the way the VM map hint is used, and
replace the linear search with a binary search tree lookup.
(vm_map_copy_insert): Move map entries from the map copy tree to the
destination map tree.
(vm_map_copyin): Initialize the map copy red-black tree.
* vm/vm_map.h: Add #include <kern/rbtree.h>.
(vm_map_entry): Add `tree_node' member.
(vm_map_header): Add `tree' member.

1 files changed, 8 insertions, 3 deletions

diff --git a/vm/vm_map.h b/vm/vm_map.h
index 381c7cfd..d5bcf96b 100644
--- a/vm/vm_map.h
+++ b/vm/vm_map.h
@@ -51,6 +51,7 @@
 #include <vm/vm_page.h>
 #include <vm/vm_types.h>
 #include <kern/lock.h>
+#include <kern/rbtree.h>
 #include <kern/macro_help.h>
 
 #define KENTRY_DATA_SIZE (32*PAGE_SIZE)
@@ -102,6 +103,7 @@ struct vm_map_entry {
 #define vme_next		links.next
 #define vme_start		links.start
 #define vme_end			links.end
+	struct rbtree_node	tree_node;	/* links to other entries in tree */
 	union vm_map_object	object;		/* object I point to */
 	vm_offset_t		offset;		/* offset into object */
 	unsigned int
@@ -137,6 +139,7 @@ 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 */
 	int			nentries;	/* Number of entries */
 	boolean_t		entries_pageable;
 						/* are map entries pageable? */
@@ -152,9 +155,11 @@ struct vm_map_header {
  *
  *	Implementation:
  *		Maps are doubly-linked lists of map entries, sorted
- *		by address.  One hint is used to start
- *		searches again from the last successful search,
- *		insertion, or removal.  Another hint is used to
+ *		by address.  They're also contained in a red-black tree.
+ *		One hint is used to start searches again at the last
+ *		successful search, insertion, or removal.  If the hint
+ *		lookup failed (i.e. the hint didn't refer to the requested
+ *		entry), a BST lookup is performed.  Another hint is used to
  *		quickly find free space.
  */
 struct vm_map {