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.

2 files changed, 76 insertions, 52 deletions

diff --git a/vm/vm_map.c b/vm/vm_map.c
index 8012bcf..c46afc0 100644
--- a/vm/vm_map.c
+++ b/vm/vm_map.c
@@ -42,6 +42,7 @@
 #include <kern/assert.h>
 #include <kern/debug.h>
 #include <kern/kalloc.h>
+#include <kern/rbtree.h>
 #include <kern/slab.h>
 #include <vm/pmap.h>
 #include <vm/vm_fault.h>
@@ -95,7 +96,7 @@ MACRO_END
  *	Synchronization is required prior to most operations.
  *
  *	Maps consist of an ordered doubly-linked list of simple
- *	entries; a single hint is used to speed up lookups.
+ *	entries; a hint and a red-black tree are used to speed up lookups.
  *
  *	Sharing maps have been deleted from this version of Mach.
  *	All shared objects are now mapped directly into the respective
@@ -213,6 +214,7 @@ void vm_map_setup(map, pmap, min, max, pageable)
 	vm_map_last_entry(map)  = vm_map_to_entry(map);
 	map->hdr.nentries = 0;
 	map->hdr.entries_pageable = pageable;
+	rbtree_init(&map->hdr.tree);
 
 	map->size = 0;
 	map->ref_count = 1;
@@ -307,9 +309,39 @@ void _vm_map_entry_dispose(map_header, entry)
 }
 
 /*
+ *	Red-black tree lookup/insert comparison functions
+ */
+static inline int vm_map_entry_cmp_lookup(vm_offset_t addr,
+                                          const struct rbtree_node *node)
+{
+	struct vm_map_entry *entry;
+
+	entry = rbtree_entry(node, struct vm_map_entry, tree_node);
+
+	if (addr < entry->vme_start)
+		return -1;
+	else if (addr < entry->vme_end)
+		return 0;
+	else
+		return 1;
+}
+
+static inline int vm_map_entry_cmp_insert(const struct rbtree_node *a,
+                                          const struct rbtree_node *b)
+{
+	struct vm_map_entry *entry;
+
+	entry = rbtree_entry(a, struct vm_map_entry, tree_node);
+	return vm_map_entry_cmp_lookup(entry->vme_start, b);
+}
+
+/*
  *	vm_map_entry_{un,}link:
  *
  *	Insert/remove entries from maps (or map copies).
+ *
+ *	The start and end addresses of the entries must be properly set
+ *	before using these macros.
  */
 #define vm_map_entry_link(map, after_where, entry)	\
 	_vm_map_entry_link(&(map)->hdr, after_where, entry)
@@ -324,6 +356,8 @@ void _vm_map_entry_dispose(map_header, entry)
 	(entry)->vme_next = (after_where)->vme_next;	\
 	(entry)->vme_prev->vme_next =			\
 	 (entry)->vme_next->vme_prev = (entry);		\
+	rbtree_insert(&(hdr)->tree, &(entry)->tree_node,	\
+		      vm_map_entry_cmp_insert);		\
 	MACRO_END
 
 #define vm_map_entry_unlink(map, entry)			\
@@ -337,6 +371,7 @@ void _vm_map_entry_dispose(map_header, entry)
 	(hdr)->nentries--;				\
 	(entry)->vme_next->vme_prev = (entry)->vme_prev; \
 	(entry)->vme_prev->vme_next = (entry)->vme_next; \
+	rbtree_remove(&(hdr)->tree, &(entry)->tree_node);	\
 	MACRO_END
 
 /*
@@ -413,70 +448,49 @@ boolean_t vm_map_lookup_entry(map, address, entry)
 	register vm_offset_t	address;
 	vm_map_entry_t		*entry;		/* OUT */
 {
-	register vm_map_entry_t		cur;
-	register vm_map_entry_t		last;
+	register struct rbtree_node	*node;
+	register vm_map_entry_t		hint;
 
 	/*
-	 *	Start looking either from the head of the
-	 *	list, or from the hint.
+	 *	First, make a quick check to see if we are already
+	 *	looking at the entry we want (which is often the case).
 	 */
 
 	simple_lock(&map->hint_lock);
-	cur = map->hint;
+	hint = map->hint;
 	simple_unlock(&map->hint_lock);
 
-	if (cur == vm_map_to_entry(map))
-		cur = cur->vme_next;
-
-	if (address >= cur->vme_start) {
-	    	/*
-		 *	Go from hint to end of list.
-		 *
-		 *	But first, make a quick check to see if
-		 *	we are already looking at the entry we
-		 *	want (which is usually the case).
-		 *	Note also that we don't need to save the hint
-		 *	here... it is the same hint (unless we are
-		 *	at the header, in which case the hint didn't
-		 *	buy us anything anyway).
-		 */
-		last = vm_map_to_entry(map);
-		if ((cur != last) && (cur->vme_end > address)) {
-			*entry = cur;
+	if ((hint != vm_map_to_entry(map)) && (address >= hint->vme_start)) {
+		if (address < hint->vme_end) {
+			*entry = hint;
 			return(TRUE);
+		} else {
+			vm_map_entry_t next = hint->vme_next;
+
+			if ((next == vm_map_to_entry(map))
+			    || (address < next->vme_start)) {
+				*entry = hint;
+				return(FALSE);
+			}
 		}
 	}
-	else {
-	    	/*
-		 *	Go from start to hint, *inclusively*
-		 */
-		last = cur->vme_next;
-		cur = vm_map_first_entry(map);
-	}
 
 	/*
-	 *	Search linearly
+	 *	If the hint didn't help, use the red-black tree.
 	 */
 
-	while (cur != last) {
-		if (cur->vme_end > address) {
-			if (address >= cur->vme_start) {
-			    	/*
-				 *	Save this lookup for future
-				 *	hints, and return
-				 */
+	node = rbtree_lookup_nearest(&map->hdr.tree, address,
+				     vm_map_entry_cmp_lookup, RBTREE_LEFT);
 
-				*entry = cur;
-				SAVE_HINT(map, cur);
-				return(TRUE);
-			}
-			break;
-		}
-		cur = cur->vme_next;
+	if (node == NULL) {
+		*entry = vm_map_to_entry(map);
+		SAVE_HINT(map, *entry);
+		return(FALSE);
+	} else {
+		*entry = rbtree_entry(node, struct vm_map_entry, tree_node);
+		SAVE_HINT(map, *entry);
+		return((address < (*entry)->vme_end) ? TRUE : FALSE);
 	}
-	*entry = cur->vme_prev;
-	SAVE_HINT(map, *entry);
-	return(FALSE);
 }
 
 /*
@@ -2414,6 +2428,10 @@ start_pass_1:
  */
 #define	vm_map_copy_insert(map, where, copy)				\
 	MACRO_BEGIN							\
+	struct rbtree_node *node, *tmp;					\
+	rbtree_for_each_remove(&(copy)->cpy_hdr.tree, node, tmp)	\
+		rbtree_insert(&(map)->hdr.tree, node,			\
+			      vm_map_entry_cmp_insert);			\
 	(((where)->vme_next)->vme_prev = vm_map_copy_last_entry(copy))	\
 		->vme_next = ((where)->vme_next);			\
 	((where)->vme_next = vm_map_copy_first_entry(copy))		\
@@ -3138,6 +3156,7 @@ kern_return_t vm_map_copyin(src_map, src_addr, len, src_destroy, copy_result)
 	copy->type = VM_MAP_COPY_ENTRY_LIST;
 	copy->cpy_hdr.nentries = 0;
 	copy->cpy_hdr.entries_pageable = TRUE;
+	rbtree_init(&copy->cpy_hdr.tree);
 
 	copy->offset = src_addr;
 	copy->size = len;
diff --git a/vm/vm_map.h b/vm/vm_map.h
index 381c7cf..d5bcf96 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 {