Merge branch 'master' into master-gdb_stubs

1 files changed, 15 insertions, 4 deletions

diff --git a/vm/vm_map.h b/vm/vm_map.h
index 567fe933..a15e681b 100644
--- a/vm/vm_map.h
+++ b/vm/vm_map.h
@@ -51,8 +51,12 @@
 #include <vm/vm_page.h>
 #include <vm/vm_types.h>
 #include <kern/lock.h>
+#include <kern/rbtree.h>
 #include <kern/macro_help.h>
 
+/* TODO: make it dynamic */
+#define KENTRY_DATA_SIZE (64*PAGE_SIZE)
+
 /*
  *	Types defined:
  *
@@ -100,6 +104,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
@@ -135,6 +140,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? */
@@ -150,9 +156,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 {
@@ -352,11 +360,14 @@ MACRO_END
  */
 
 extern vm_offset_t	kentry_data;
-extern vm_offset_t	kentry_data_size;
+extern vm_size_t	kentry_data_size;
 extern int		kentry_count;
 /* Initialize the module */
 extern void		vm_map_init(void);
 
+/* Initialize an empty map */
+extern void		vm_map_setup(vm_map_t, pmap_t, vm_offset_t, vm_offset_t,
+				     boolean_t);
 /* Create an empty map */
 extern vm_map_t		vm_map_create(pmap_t, vm_offset_t, vm_offset_t,
 				      boolean_t);