XXX pmm from x15, userspace crashes soon

9 files changed, 500 insertions, 873 deletions

diff --git a/vm/pmap.h b/vm/pmap.h
index 134f9c6..3dece5e 100644
--- a/vm/pmap.h
+++ b/vm/pmap.h
@@ -63,13 +63,10 @@
  *	but it is not part of the interface.
  */
 
-/* During VM initialization, steal a chunk of memory.  */
-extern vm_offset_t	pmap_steal_memory(vm_size_t);
-/* During VM initialization, report remaining unused physical pages.  */
-extern unsigned int	pmap_free_pages(void);
 /* During VM initialization, use remaining physical pages to allocate page
  * frames.  */
 extern void		pmap_startup(vm_offset_t *, vm_offset_t *);
+
 /* Initialization, after kernel runs in virtual memory.  */
 extern void		pmap_init(void);
 
@@ -78,20 +75,12 @@ extern void		pmap_init(void);
  *	If machine/pmap.h defines MACHINE_PAGES, it must implement
  *	the above functions.  The pmap module has complete control.
  *	Otherwise, it must implement
- *		pmap_free_pages
  *		pmap_virtual_space
- *		pmap_next_page
  *		pmap_init
- *	and vm/vm_resident.c implements pmap_steal_memory and pmap_startup
- *	using pmap_free_pages, pmap_next_page, pmap_virtual_space,
- *	and pmap_enter.  pmap_free_pages may over-estimate the number
- *	of unused physical pages, and pmap_next_page may return FALSE
- *	to indicate that there are no more unused pages to return.
- *	However, for best performance pmap_free_pages should be accurate.
+ *	and vm/vm_resident.c implements pmap_startup using
+ *	pmap_virtual_space, and pmap_enter.
  */
 
-/* During VM initialization, return the next unused physical page.  */
-extern boolean_t	pmap_next_page(vm_offset_t *);
 /* During VM initialization, report virtual space available for the kernel.  */
 extern void		pmap_virtual_space(vm_offset_t *, vm_offset_t *);
 #endif	/* MACHINE_PAGES */
diff --git a/vm/vm_debug.c b/vm/vm_debug.c
index 227090e..1248da7 100644
--- a/vm/vm_debug.c
+++ b/vm/vm_debug.c
@@ -48,6 +48,7 @@
 #include <vm/vm_object.h>
 #include <kern/task.h>
 #include <kern/host.h>
+#include <kern/rdxtree.h>
 #include <ipc/ipc_port.h>
 
 
@@ -318,7 +319,8 @@ mach_vm_object_pages(
 	/* object is locked, we have enough wired memory */
 
 	count = 0;
-	queue_iterate(&object->memq, p, vm_page_t, listq) {
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&object->memt, &iter, p) {
 		vm_page_info_t *info = &pages[count++];
 		vm_page_info_state_t state = 0;
 
@@ -362,8 +364,6 @@ mach_vm_object_pages(
 			state |= VPI_STATE_ACTIVE;
 		if (p->laundry)
 			state |= VPI_STATE_LAUNDRY;
-		if (p->free)
-			state |= VPI_STATE_FREE;
 		if (p->reference)
 			state |= VPI_STATE_REFERENCE;
 
@@ -418,82 +418,3 @@ mach_vm_object_pages(
 }
 
 #endif	/* MACH_VM_DEBUG */
-
-/*
- *	Routine:	host_virtual_physical_table_info
- *	Purpose:
- *		Return information about the VP table.
- *	Conditions:
- *		Nothing locked.  Obeys CountInOut protocol.
- *	Returns:
- *		KERN_SUCCESS		Returned information.
- *		KERN_INVALID_HOST	The host is null.
- *		KERN_RESOURCE_SHORTAGE	Couldn't allocate memory.
- */
-
-kern_return_t
-host_virtual_physical_table_info(host, infop, countp)
-	const host_t host;
-	hash_info_bucket_array_t *infop;
-	natural_t *countp;
-{
-	vm_offset_t addr;
-	vm_size_t size = 0;/* '=0' to quiet gcc warnings */
-	hash_info_bucket_t *info;
-	unsigned int potential, actual;
-	kern_return_t kr;
-
-	if (host == HOST_NULL)
-		return KERN_INVALID_HOST;
-
-	/* start with in-line data */
-
-	info = *infop;
-	potential = *countp;
-
-	for (;;) {
-		actual = vm_page_info(info, potential);
-		if (actual <= potential)
-			break;
-
-		/* allocate more memory */
-
-		if (info != *infop)
-			kmem_free(ipc_kernel_map, addr, size);
-
-		size = round_page(actual * sizeof *info);
-		kr = kmem_alloc_pageable(ipc_kernel_map, &addr, size);
-		if (kr != KERN_SUCCESS)
-			return KERN_RESOURCE_SHORTAGE;
-
-		info = (hash_info_bucket_t *) addr;
-		potential = size/sizeof *info;
-	}
-
-	if (info == *infop) {
-		/* data fit in-line; nothing to deallocate */
-
-		*countp = actual;
-	} else if (actual == 0) {
-		kmem_free(ipc_kernel_map, addr, size);
-
-		*countp = 0;
-	} else {
-		vm_map_copy_t copy;
-		vm_size_t used;
-
-		used = round_page(actual * sizeof *info);
-
-		if (used != size)
-			kmem_free(ipc_kernel_map, addr + used, size - used);
-
-		kr = vm_map_copyin(ipc_kernel_map, addr, used,
-				   TRUE, &copy);
-		assert(kr == KERN_SUCCESS);
-
-		*infop = (hash_info_bucket_t *) copy;
-		*countp = actual;
-	}
-
-	return KERN_SUCCESS;
-}
diff --git a/vm/vm_fault.c b/vm/vm_fault.c
index aa5febc..96f53fb 100644
--- a/vm/vm_fault.c
+++ b/vm/vm_fault.c
@@ -609,7 +609,7 @@ vm_fault_return_t vm_fault_page(
 				 *	won't block for pages.
 				 */
 
-				if (m->fictitious && !vm_page_convert(m, FALSE)) {
+				if (m->fictitious && !vm_page_convert(&m, FALSE)) {
 					VM_PAGE_FREE(m);
 					vm_fault_cleanup(object, first_m);
 					return(VM_FAULT_MEMORY_SHORTAGE);
@@ -727,7 +727,7 @@ vm_fault_return_t vm_fault_page(
 			assert(m->object == object);
 			first_m = VM_PAGE_NULL;
 
-			if (m->fictitious && !vm_page_convert(m, !object->internal)) {
+			if (m->fictitious && !vm_page_convert(&m, !object->internal)) {
 				VM_PAGE_FREE(m);
 				vm_fault_cleanup(object, VM_PAGE_NULL);
 				return(VM_FAULT_MEMORY_SHORTAGE);
diff --git a/vm/vm_init.c b/vm/vm_init.c
index 4fdcd83..6563410 100644
--- a/vm/vm_init.c
+++ b/vm/vm_init.c
@@ -66,12 +66,10 @@ void vm_mem_bootstrap(void)
 	 *	Initialize other VM packages
 	 */
 
-	slab_bootstrap();
 	vm_object_bootstrap();
 	vm_map_init();
 	kmem_init(start, end);
 	pmap_init();
-	slab_init();
 	vm_fault_init();
 	vm_page_module_init();
 	memory_manager_default_init();
diff --git a/vm/vm_object.c b/vm/vm_object.c
index ee09e3b..3c7d73c 100644
--- a/vm/vm_object.c
+++ b/vm/vm_object.c
@@ -48,6 +48,7 @@
 #include <kern/queue.h>
 #include <kern/xpr.h>
 #include <kern/slab.h>
+#include <kern/rdxtree.h>
 #include <vm/memory_object.h>
 #include <vm/vm_fault.h>
 #include <vm/vm_map.h>
@@ -219,7 +220,7 @@ static void _vm_object_setup(
 	vm_size_t	size)
 {
 	*object = vm_object_template;
-	queue_init(&object->memq);
+	rdxtree_init(&object->memt);
 	vm_object_lock_init(object);
 	object->size = size;
 }
@@ -585,18 +586,15 @@ void vm_object_terminate(
 	 *	It is possible for us to find busy/absent pages,
 	 *	if some faults on this object were aborted.
 	 */
-
+	struct rdxtree_iter iter;
 	if ((object->temporary) || (object->pager == IP_NULL)) {
-		while (!queue_empty(&object->memq)) {
-			p = (vm_page_t) queue_first(&object->memq);
-
+		rdxtree_for_each(&object->memt, &iter, p) {
 			VM_PAGE_CHECK(p);
 
 			VM_PAGE_FREE(p);
+			rdxtree_iter_init(&iter);
 		}
-	} else while (!queue_empty(&object->memq)) {
-		p = (vm_page_t) queue_first(&object->memq);
-
+	} else rdxtree_for_each(&object->memt, &iter, p) {
 		VM_PAGE_CHECK(p);
 
 		vm_page_lock_queues();
@@ -625,6 +623,7 @@ void vm_object_terminate(
 		} else {
 		    free_page:
 		    	VM_PAGE_FREE(p);
+			rdxtree_iter_init(&iter);
 		}
 	}
 
@@ -737,7 +736,6 @@ void vm_object_abort_activity(
 	vm_object_t	object)
 {
 	vm_page_t	p;
-	vm_page_t	next;
 
 	/*
 	 *	Abort all activity that would be waiting
@@ -748,10 +746,8 @@ void vm_object_abort_activity(
 	 *	we don't.
 	 */
 
-	p = (vm_page_t) queue_first(&object->memq);
-	while (!queue_end(&object->memq, (queue_entry_t) p)) {
-		next = (vm_page_t) queue_next(&p->listq);
-
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&object->memt, &iter, p) {
 		/*
 		 *	If it's being paged in, destroy it.
 		 *	If an unlock has been requested, start it again.
@@ -765,8 +761,7 @@ void vm_object_abort_activity(
 			 	p->unlock_request = VM_PROT_NONE;
 			PAGE_WAKEUP(p);
 		}
-		
-		p = next;
+		rdxtree_iter_init(&iter);
 	}
 
 	/*
@@ -874,7 +869,8 @@ void vm_object_deactivate_pages(
 {
 	vm_page_t	p;
 
-	queue_iterate(&object->memq, p, vm_page_t, listq) {
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&object->memt, &iter, p) {
 		vm_page_lock_queues();
 		if (!p->busy)
 			vm_page_deactivate(p);
@@ -937,7 +933,8 @@ void vm_object_pmap_protect(
 
 		end = offset + size;
 
-		queue_iterate(&object->memq, p, vm_page_t, listq) {
+		struct rdxtree_iter iter;
+		rdxtree_for_each(&object->memt, &iter, p) {
 		    if (!p->fictitious &&
 			(offset <= p->offset) &&
 			(p->offset < end)) {
@@ -1011,7 +1008,8 @@ void vm_object_pmap_remove(
 		return;
 
 	vm_object_lock(object);
-	queue_iterate(&object->memq, p, vm_page_t, listq) {
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&object->memt, &iter, p) {
 		if (!p->fictitious &&
 		    (start <= p->offset) &&
 		    (p->offset < end))
@@ -1381,7 +1379,8 @@ kern_return_t vm_object_copy_call(
 	 *	the old memory object that we can.
 	 */
 
-	queue_iterate(&src_object->memq, p, vm_page_t, listq) {
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&src_object->memt, &iter, p) {
 	    if (!p->fictitious &&
 		(src_offset <= p->offset) &&
 		(p->offset < src_end) &&
@@ -1570,7 +1569,8 @@ vm_object_t vm_object_copy_delayed(
 	 *	those pages will already be marked copy-on-write.
 	 */
 
-	queue_iterate(&src_object->memq, p, vm_page_t, listq) {
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&src_object->memt, &iter, p) {
 	    if (!p->fictitious)
 		pmap_page_protect(p->phys_addr, 
 				  (VM_PROT_ALL & ~VM_PROT_WRITE &
@@ -2437,12 +2437,8 @@ void vm_object_collapse(
 			 *	will be overwritten by any of the parent's
 			 *	pages that shadow them.
 			 */
-
-			while (!queue_empty(&backing_object->memq)) {
-
-				p = (vm_page_t)
-					queue_first(&backing_object->memq);
-
+			struct rdxtree_iter iter;
+			rdxtree_for_each(&backing_object->memt, &iter, p) {
 				new_offset = (p->offset - backing_offset);
 
 				assert(!p->busy || p->absent);
@@ -2504,6 +2500,7 @@ void vm_object_collapse(
 					vm_page_rename(p, object, new_offset);
 				    }
 				}
+				rdxtree_iter_init(&iter);
 			}
 
 			/*
@@ -2637,8 +2634,8 @@ void vm_object_collapse(
 			 *	of pages here.
 			 */
 
-			queue_iterate(&backing_object->memq, p,
-				      vm_page_t, listq)
+			struct rdxtree_iter iter;
+			rdxtree_for_each(&backing_object->memt, &iter, p)
 			{
 				new_offset = (p->offset - backing_offset);
 
@@ -2710,47 +2707,21 @@ void vm_object_collapse(
  *	In/out conditions:
  *		The object must be locked.
  */
-unsigned int vm_object_page_remove_lookup = 0;
-unsigned int vm_object_page_remove_iterate = 0;
 
 void vm_object_page_remove(
 	vm_object_t	object,
 	vm_offset_t	start,
 	vm_offset_t	end)
 {
-	vm_page_t	p, next;
-
-	/*
-	 *	One and two page removals are most popular.
-	 *	The factor of 16 here is somewhat arbitrary.
-	 *	It balances vm_object_lookup vs iteration.
-	 */
-
-	if (atop(end - start) < (unsigned)object->resident_page_count/16) {
-		vm_object_page_remove_lookup++;
-
-		for (; start < end; start += PAGE_SIZE) {
-			p = vm_page_lookup(object, start);
-			if (p != VM_PAGE_NULL) {
-				if (!p->fictitious)
-					pmap_page_protect(p->phys_addr,
-							  VM_PROT_NONE);
-				VM_PAGE_FREE(p);
-			}
-		}
-	} else {
-		vm_object_page_remove_iterate++;
-
-		p = (vm_page_t) queue_first(&object->memq);
-		while (!queue_end(&object->memq, (queue_entry_t) p)) {
-			next = (vm_page_t) queue_next(&p->listq);
-			if ((start <= p->offset) && (p->offset < end)) {
-				if (!p->fictitious)
-				    pmap_page_protect(p->phys_addr,
-						      VM_PROT_NONE);
-				VM_PAGE_FREE(p);
-			}
-			p = next;
+	vm_page_t	p;
+	struct rdxtree_iter iter;
+	rdxtree_for_each(&object->memt, &iter, p) {
+		if ((start <= p->offset) && (p->offset < end)) {
+			if (!p->fictitious)
+				pmap_page_protect(p->phys_addr,
+						  VM_PROT_NONE);
+			VM_PAGE_FREE(p);
+			rdxtree_iter_init(&iter);
 		}
 	}
 }
@@ -2977,15 +2948,14 @@ void vm_object_print(
 
 	if (vm_object_print_pages) {
 		count = 0;
-		p = (vm_page_t) queue_first(&object->memq);
-		while (!queue_end(&object->memq, (queue_entry_t) p)) {
+		struct rdxtree_iter iter;
+		rdxtree_for_each(&object->memt, &iter, p) {
 			if (count == 0) iprintf("memory:=");
 			else if (count == 4) {printf("\n"); iprintf(" ..."); count = 0;}
 			else printf(",");
 			count++;
 
 			printf("(off=0x%X,page=0x%X)", p->offset, (vm_offset_t) p);
-			p = (vm_page_t) queue_next(&p->listq);
 		}
 		if (count != 0)
 			printf("\n");
diff --git a/vm/vm_object.h b/vm/vm_object.h
index 3c9055f..142404a 100644
--- a/vm/vm_object.h
+++ b/vm/vm_object.h
@@ -46,6 +46,7 @@
 #include <kern/assert.h>
 #include <kern/debug.h>
 #include <kern/macros.h>
+#include <kern/rdxtree.h>
 #include <vm/pmap.h>
 #include <ipc/ipc_types.h>
 
@@ -62,7 +63,8 @@ typedef struct ipc_port *	pager_request_t;
  */
 
 struct vm_object {
-	queue_chain_t		memq;		/* Resident memory */
+	/* Resident memory indexed by offset.  Protected by LOCK.  */
+	struct rdxtree		memt;
 	struct lock		Lock;		/* Synchronization */
 #if	VM_OBJECT_DEBUG
 	thread_t		LockHolder;	/* Thread holding Lock */
diff --git a/vm/vm_page.c b/vm/vm_page.c
index cc184ca..f2a11e1 100644
--- a/vm/vm_page.c
+++ b/vm/vm_page.c
@@ -29,24 +29,27 @@
  * The symmetric case is handled likewise.
  */
 
+#include <string.h>
 #include <kern/assert.h>
-#include <kern/init.h>
 #include <kern/list.h>
 #include <kern/macros.h>
-#include <kern/mutex.h>
-#include <kern/panic.h>
-#include <kern/param.h>
-#include <kern/printk.h>
-#include <kern/sprintf.h>
-#include <kern/stddef.h>
-#include <kern/string.h>
+#include <kern/lock.h>
+#include <kern/printf.h>
 #include <kern/thread.h>
-#include <kern/types.h>
-#include <machine/cpu.h>
 #include <machine/pmap.h>
-#include <vm/vm_kmem.h>
 #include <vm/vm_page.h>
 
+/* XXX Mach glue.  */
+#define CPU_L1_SIZE (1 << CPU_L1_SHIFT)
+#define MAX_CPUS NCPUS
+#define __read_mostly
+#define __initdata
+#define __init
+#define cpu_id() cpu_number()
+#define thread_pin()
+#define thread_unpin()
+#define printk printf
+
 /*
  * Number of free block lists per segment.
  */
@@ -73,7 +76,7 @@
  * Per-processor cache of pages.
  */
 struct vm_page_cpu_pool {
-    struct mutex lock;
+    decl_simple_lock_data(,lock);
     int size;
     int transfer_size;
     int nr_pages;
@@ -109,7 +112,7 @@ struct vm_page_seg {
     phys_addr_t end;
     struct vm_page *pages;
     struct vm_page *pages_end;
-    struct mutex lock;
+    decl_simple_lock_data(,lock);
     struct vm_page_free_list free_lists[VM_PAGE_NR_FREE_LISTS];
     unsigned long nr_free_pages;
 };
@@ -154,16 +157,66 @@ static struct vm_page_boot_seg vm_page_boot_segs[VM_PAGE_MAX_SEGS] __initdata;
  */
 static unsigned int vm_page_segs_size __read_mostly;
 
+/*
+ *	Resident page structures are initialized from
+ *	a template (see vm_page_initialize).
+ */
+static struct vm_page	vm_page_template =
+	{
+		.type = VM_PAGE_RESERVED,
+		.order = VM_PAGE_ORDER_UNLISTED,
+                .object = VM_OBJECT_NULL,	/* reset later */
+		.offset = 0,			/* reset later */
+		.wire_count = 0,
+
+		.inactive = FALSE,
+		.active = FALSE,
+		.laundry = FALSE,
+		.external = FALSE,
+
+		.busy = TRUE,
+		.wanted = FALSE,
+		.tabled = FALSE,
+		.fictitious = FALSE,
+		.private = FALSE,
+		.absent = FALSE,
+		.error = FALSE,
+		.dirty = FALSE,
+		.precious = FALSE,
+		.reference = FALSE,
+
+		.phys_addr = 0,		/* reset later */
+
+		.page_lock = VM_PROT_NONE,
+		.unlock_request = VM_PROT_NONE,
+	};
+
+
 static void __init
-vm_page_init(struct vm_page *page, unsigned short seg_index, phys_addr_t pa)
+vm_page_initialize(struct vm_page *page, unsigned short seg_index,
+                   phys_addr_t pa)
 {
-    memset(page, 0, sizeof(*page));
-    page->type = VM_PAGE_RESERVED;
+    memcpy(page, &vm_page_template, VM_PAGE_HEADER_SIZE);
     page->seg_index = seg_index;
-    page->order = VM_PAGE_ORDER_UNLISTED;
     page->phys_addr = pa;
 }
 
+/* XXX legacy mach interface  */
+void
+vm_page_init_mach(struct vm_page *page)
+{
+    memcpy(&page->vm_page_header,
+           &vm_page_template.vm_page_header,
+           sizeof *page - VM_PAGE_HEADER_SIZE);
+}
+
+void
+vm_page_init(vm_page_t mem,
+             vm_offset_t phys_addr)
+{
+    vm_page_initialize(mem, mem->seg_index, phys_addr);
+}
+
 void
 vm_page_set_type(struct vm_page *page, unsigned int order, unsigned short type)
 {
@@ -278,7 +331,7 @@ vm_page_seg_free_to_buddy(struct vm_page_seg *seg, struct vm_page *page,
 static void __init
 vm_page_cpu_pool_init(struct vm_page_cpu_pool *cpu_pool, int size)
 {
-    mutex_init(&cpu_pool->lock);
+    simple_lock_init(&cpu_pool->lock);
     cpu_pool->size = size;
     cpu_pool->transfer_size = (size + VM_PAGE_CPU_POOL_TRANSFER_RATIO - 1)
                               / VM_PAGE_CPU_POOL_TRANSFER_RATIO;
@@ -321,7 +374,7 @@ vm_page_cpu_pool_fill(struct vm_page_cpu_pool *cpu_pool,
 
     assert(cpu_pool->nr_pages == 0);
 
-    mutex_lock(&seg->lock);
+    simple_lock(&seg->lock);
 
     for (i = 0; i < cpu_pool->transfer_size; i++) {
         page = vm_page_seg_alloc_from_buddy(seg, 0);
@@ -332,7 +385,7 @@ vm_page_cpu_pool_fill(struct vm_page_cpu_pool *cpu_pool,
         vm_page_cpu_pool_push(cpu_pool, page);
     }
 
-    mutex_unlock(&seg->lock);
+    simple_unlock(&seg->lock);
 
     return i;
 }
@@ -346,14 +399,14 @@ vm_page_cpu_pool_drain(struct vm_page_cpu_pool *cpu_pool,
 
     assert(cpu_pool->nr_pages == cpu_pool->size);
 
-    mutex_lock(&seg->lock);
+    simple_lock(&seg->lock);
 
     for (i = cpu_pool->transfer_size; i > 0; i--) {
         page = vm_page_cpu_pool_pop(cpu_pool);
         vm_page_seg_free_to_buddy(seg, page, 0);
     }
 
-    mutex_unlock(&seg->lock);
+    simple_unlock(&seg->lock);
 }
 
 static phys_addr_t __init
@@ -394,7 +447,7 @@ vm_page_seg_init(struct vm_page_seg *seg, phys_addr_t start, phys_addr_t end,
 
     seg->pages = pages;
     seg->pages_end = pages + vm_page_atop(vm_page_seg_size(seg));
-    mutex_init(&seg->lock);
+    simple_lock_init(&seg->lock);
 
     for (i = 0; i < ARRAY_SIZE(seg->free_lists); i++)
         vm_page_free_list_init(&seg->free_lists[i]);
@@ -403,7 +456,7 @@ vm_page_seg_init(struct vm_page_seg *seg, phys_addr_t start, phys_addr_t end,
     i = seg - vm_page_segs;
 
     for (pa = seg->start; pa < seg->end; pa += PAGE_SIZE)
-        vm_page_init(&pages[vm_page_atop(pa - seg->start)], i, pa);
+        vm_page_initialize(&pages[vm_page_atop(pa - seg->start)], i, pa);
 }
 
 static struct vm_page *
@@ -419,29 +472,30 @@ vm_page_seg_alloc(struct vm_page_seg *seg, unsigned int order,
     if (order == 0) {
         thread_pin();
         cpu_pool = vm_page_cpu_pool_get(seg);
-        mutex_lock(&cpu_pool->lock);
+        simple_lock(&cpu_pool->lock);
 
         if (cpu_pool->nr_pages == 0) {
             filled = vm_page_cpu_pool_fill(cpu_pool, seg);
 
             if (!filled) {
-                mutex_unlock(&cpu_pool->lock);
+                simple_unlock(&cpu_pool->lock);
                 thread_unpin();
                 return NULL;
             }
         }
 
         page = vm_page_cpu_pool_pop(cpu_pool);
-        mutex_unlock(&cpu_pool->lock);
+        simple_unlock(&cpu_pool->lock);
         thread_unpin();
     } else {
-        mutex_lock(&seg->lock);
+        simple_lock(&seg->lock);
         page = vm_page_seg_alloc_from_buddy(seg, order);
-        mutex_unlock(&seg->lock);
+        simple_unlock(&seg->lock);
     }
 
-    assert(page->type == VM_PAGE_FREE);
+    assert(page->type == VM_PAGE_UNUSED);
     vm_page_set_type(page, order, type);
+    update_vm_page_counts();
     return page;
 }
 
@@ -451,27 +505,28 @@ vm_page_seg_free(struct vm_page_seg *seg, struct vm_page *page,
 {
     struct vm_page_cpu_pool *cpu_pool;
 
-    assert(page->type != VM_PAGE_FREE);
+    assert(page->type != VM_PAGE_UNUSED);
     assert(order < VM_PAGE_NR_FREE_LISTS);
 
-    vm_page_set_type(page, order, VM_PAGE_FREE);
+    vm_page_set_type(page, order, VM_PAGE_UNUSED);
 
     if (order == 0) {
         thread_pin();
         cpu_pool = vm_page_cpu_pool_get(seg);
-        mutex_lock(&cpu_pool->lock);
+        simple_lock(&cpu_pool->lock);
 
         if (cpu_pool->nr_pages == cpu_pool->size)
             vm_page_cpu_pool_drain(cpu_pool, seg);
 
         vm_page_cpu_pool_push(cpu_pool, page);
-        mutex_unlock(&cpu_pool->lock);
+        simple_unlock(&cpu_pool->lock);
         thread_unpin();
     } else {
-        mutex_lock(&seg->lock);
+        simple_lock(&seg->lock);
         vm_page_seg_free_to_buddy(seg, page, order);
-        mutex_unlock(&seg->lock);
+        simple_unlock(&seg->lock);
     }
+    update_vm_page_counts();
 }
 
 void __init
@@ -610,7 +665,7 @@ vm_page_setup(void)
         nr_pages += vm_page_atop(vm_page_boot_seg_size(&vm_page_boot_segs[i]));
 
     table_size = vm_page_round(nr_pages * sizeof(struct vm_page));
-    printk("vm_page: page table size: %zu entries (%zuk)\n", nr_pages,
+    printk("vm_page: page table size: %u entries (%uk)\n", nr_pages,
            table_size >> 10);
     table = vm_page_bootalloc(table_size);
     va = (unsigned long)table;
@@ -630,7 +685,7 @@ vm_page_setup(void)
                                         - boot_seg->start);
 
         while (page < end) {
-            page->type = VM_PAGE_FREE;
+            page->type = VM_PAGE_UNUSED;
             vm_page_seg_free_to_buddy(seg, page, 0);
             page++;
         }
@@ -640,7 +695,7 @@ vm_page_setup(void)
 
     while (va < (unsigned long)table) {
         pa = vm_page_direct_pa(va);
-        page = vm_page_lookup(pa);
+        page = vm_page_lookup_pa(pa);
         assert((page != NULL) && (page->type == VM_PAGE_RESERVED));
         page->type = VM_PAGE_TABLE;
         va += PAGE_SIZE;
@@ -655,12 +710,12 @@ vm_page_manage(struct vm_page *page)
     assert(page->seg_index < ARRAY_SIZE(vm_page_segs));
     assert(page->type == VM_PAGE_RESERVED);
 
-    vm_page_set_type(page, 0, VM_PAGE_FREE);
+    vm_page_set_type(page, 0, VM_PAGE_UNUSED);
     vm_page_seg_free_to_buddy(&vm_page_segs[page->seg_index], page, 0);
 }
 
 struct vm_page *
-vm_page_lookup(phys_addr_t pa)
+vm_page_lookup_pa(phys_addr_t pa)
 {
     struct vm_page_seg *seg;
     unsigned int i;
@@ -676,7 +731,7 @@ vm_page_lookup(phys_addr_t pa)
 }
 
 struct vm_page *
-vm_page_alloc(unsigned int order, unsigned int selector, unsigned short type)
+vm_page_alloc_p(unsigned int order, unsigned int selector, unsigned short type)
 {
     struct vm_page *page;
     unsigned int i;
@@ -695,7 +750,7 @@ vm_page_alloc(unsigned int order, unsigned int selector, unsigned short type)
 }
 
 void
-vm_page_free(struct vm_page *page, unsigned int order)
+vm_page_free_p(struct vm_page *page, unsigned int order)
 {
     assert(page->seg_index < ARRAY_SIZE(vm_page_segs));
 
@@ -733,3 +788,14 @@ vm_page_info(void)
                seg->nr_free_pages, seg->nr_free_pages >> (20 - PAGE_SHIFT));
     }
 }
+
+void
+update_vm_page_counts(void)
+{
+    unsigned long pages;
+    unsigned int i;
+
+    for (i = 0, pages = 0; i < vm_page_segs_size; i++)
+        pages += vm_page_segs[i].nr_free_pages;
+    vm_page_free_count = pages;
+}
diff --git a/vm/vm_page.h b/vm/vm_page.h
index 23c8c47..c401b25 100644
--- a/vm/vm_page.h
+++ b/vm/vm_page.h
@@ -25,11 +25,23 @@
 #include <kern/list.h>
 #include <kern/log2.h>
 #include <kern/macros.h>
-//#include <kern/param.h>
-//#include <kern/stddef.h>
-//#include <kern/types.h>
+#include <mach/vm_param.h>
+#include <machine/vm_param.h>
 #include <machine/pmap.h>
 
+#include <kern/queue.h>
+#include <kern/lock.h>
+
+#include <mach/boolean.h>
+#include <mach/vm_prot.h>
+#include <mach/vm_param.h>
+#include <vm/vm_object.h>
+#include <vm/vm_types.h>
+#include <kern/queue.h>
+#include <kern/lock.h>
+
+#include <kern/sched_prim.h>	/* definitions of wait/wakeup */
+
 /*
  * Address/page conversion and rounding macros (not inline functions to
  * be easily usable on both virtual and physical addresses, which may not
@@ -62,7 +74,7 @@
  * TODO Obviously, this needs to be addressed, e.g. with a reserved pool of
  * pages.
  */
-#define VM_PAGE_FREE        0   /* Page unused */
+#define VM_PAGE_UNUSED      0   /* Page unused */
 #define VM_PAGE_RESERVED    1   /* Page reserved at boot time */
 #define VM_PAGE_TABLE       2   /* Page is part of the page table */
 #define VM_PAGE_PMAP        3   /* Page stores pmap-specific data */
@@ -74,12 +86,51 @@
  * Physical page descriptor.
  */
 struct vm_page {
-    struct list node;
-    unsigned short type;
-    unsigned short seg_index;
-    unsigned short order;
-    phys_addr_t phys_addr;
-    void *slab_priv;
+	/* This is the data used by the vm_page module.  */
+	struct list node;
+	unsigned short type;
+	unsigned short seg_index;
+	unsigned short order;
+	phys_addr_t phys_addr;
+	void *slab_priv;
+
+	/* We use an empty struct as the delimiter.  */
+	struct {} vm_page_header;
+#define VM_PAGE_HEADER_SIZE	offsetof(struct vm_page, vm_page_header)
+
+	/* This is the data used by vm_resident and friends.  */
+	queue_chain_t	pageq;		/* queue info for FIFO queue */
+
+	vm_object_t	object;		/* which object am I in (O,P) */
+	vm_offset_t	offset;		/* offset into that object (O,P) */
+
+	unsigned int	wire_count:16,	/* how many wired down maps use me?
+					   (O&P) */
+	/* boolean_t */	inactive:1,	/* page is in inactive list (P) */
+			active:1,	/* page is in active list (P) */
+			laundry:1,	/* page is being cleaned now (P)*/
+			reference:1,	/* page has been used (P) */
+			external:1,	/* page considered external (P) */
+			extcounted:1,   /* page counted in ext counts (P) */
+			busy:1,		/* page is in transit (O) */
+			wanted:1,	/* someone is waiting for page (O) */
+			tabled:1,	/* page is in VP table (O) */
+			fictitious:1,	/* Physical page doesn't exist (O) */
+			private:1,	/* Page should not be returned to
+					 *  the free list (O) */
+			absent:1,	/* Data has been requested, but is
+					 *  not yet available (O) */
+			error:1,	/* Data manager was unable to provide
+					 *  data due to error (O) */
+			dirty:1,	/* Page must be cleaned (O) */
+			precious:1,	/* Page is precious; data must be
+					 *  returned even if clean (O) */
+			overwriting:1;	/* Request to unlock has been made
+					 * without having data. (O)
+					 * [See vm_object_overwrite] */
+
+	vm_prot_t	page_lock;	/* Uses prohibited by data manager (O) */
+	vm_prot_t	unlock_request;	/* Outstanding unlock request (O) */
 };
 
 static inline unsigned short
@@ -166,7 +217,7 @@ void vm_page_manage(struct vm_page *page);
 /*
  * Return the page descriptor for the given physical address.
  */
-struct vm_page * vm_page_lookup(phys_addr_t pa);
+struct vm_page * vm_page_lookup_pa(phys_addr_t pa);
 
 /*
  * Allocate a block of 2^order physical pages.
@@ -174,13 +225,13 @@ struct vm_page * vm_page_lookup(phys_addr_t pa);
  * The selector is used to determine the segments from which allocation can
  * be attempted.
  */
-struct vm_page * vm_page_alloc(unsigned int order, unsigned int selector,
+struct vm_page * vm_page_alloc_p(unsigned int order, unsigned int selector,
                                unsigned short type);
 
 /*
  * Release a block of 2^order physical pages.
  */
-void vm_page_free(struct vm_page *page, unsigned int order);
+void vm_page_free_p(struct vm_page *page, unsigned int order);
 
 /*
  * Return the name of the given segment.
@@ -192,4 +243,212 @@ const char * vm_page_seg_name(unsigned int seg_index);
  */
 void vm_page_info(void);
 
+/* Mach stuff follows.  */
+
+/*
+ * Glue code.
+ */
+#define CPU_L1_SIZE (1 << CPU_L1_SHIFT)
+#define MAX_CPUS NCPUS
+#define __read_mostly
+#define __initdata
+#define __init
+#define cpu_id() cpu_number()
+#define thread_pin()
+#define thread_unpin()
+#define printk printf
+
+void update_vm_page_counts(void);
+
+/*
+ *	For debugging, this macro can be defined to perform
+ *	some useful check on a page structure.
+ */
+
+#define VM_PAGE_CHECK(mem)
+
+/*
+ *	Each pageable resident page falls into one of three lists:
+ *
+ *	free	
+ *		Available for allocation now.
+ *	inactive
+ *		Not referenced in any map, but still has an
+ *		object/offset-page mapping, and may be dirty.
+ *		This is the list of pages that should be
+ *		paged out next.
+ *	active
+ *		A list of pages which have been placed in
+ *		at least one physical map.  This list is
+ *		ordered, in LRU-like fashion.
+ */
+
+extern
+vm_page_t	vm_page_queue_free;	/* memory free queue */
+extern
+vm_page_t	vm_page_queue_fictitious;	/* fictitious free queue */
+extern
+queue_head_t	vm_page_queue_active;	/* active memory queue */
+extern
+queue_head_t	vm_page_queue_inactive;	/* inactive memory queue */
+
+extern
+int	vm_page_free_count;	/* How many pages are free? */
+extern
+int	vm_page_fictitious_count;/* How many fictitious pages are free? */
+extern
+int	vm_page_active_count;	/* How many pages are active? */
+extern
+int	vm_page_inactive_count;	/* How many pages are inactive? */
+extern
+int	vm_page_wire_count;	/* How many pages are wired? */
+extern
+int	vm_page_free_target;	/* How many do we want free? */
+extern
+int	vm_page_free_min;	/* When to wakeup pageout */
+extern
+int	vm_page_inactive_target;/* How many do we want inactive? */
+extern
+int	vm_page_free_reserved;	/* How many pages reserved to do pageout */
+extern
+int	vm_page_laundry_count;	/* How many pages being laundered? */
+extern
+int	vm_page_external_limit;	/* Max number of pages for external objects  */
+
+/* Only objects marked with the extcounted bit are included in this total.
+   Pages which we scan for possible pageout, but which are not actually
+   dirty, don't get considered against the external page limits any more
+   in this way.  */
+extern
+int	vm_page_external_count;	/* How many pages for external objects? */
+
+
+
+decl_simple_lock_data(extern,vm_page_queue_lock)/* lock on active and inactive
+						   page queues */
+decl_simple_lock_data(extern,vm_page_queue_free_lock)
+						/* lock on free page queue */
+
+extern unsigned int	vm_page_free_wanted;
+				/* how many threads are waiting for memory */
+
+extern vm_offset_t	vm_page_fictitious_addr;
+				/* (fake) phys_addr of fictitious pages */
+
+extern void		vm_page_bootstrap(
+	vm_offset_t	*startp,
+	vm_offset_t	*endp);
+extern void		vm_page_module_init(void);
+
+extern void		vm_page_create(
+	vm_offset_t	start,
+	vm_offset_t	end);
+extern vm_page_t	vm_page_lookup(
+	vm_object_t	object,
+	vm_offset_t	offset);
+extern vm_page_t	vm_page_grab_fictitious(void);
+extern void		vm_page_release_fictitious(vm_page_t);
+extern boolean_t	vm_page_convert(vm_page_t *, boolean_t);
+extern void		vm_page_more_fictitious(void);
+extern vm_page_t	vm_page_grab(boolean_t);
+extern void		vm_page_release(vm_page_t, boolean_t);
+extern void		vm_page_wait(void (*)(void));
+extern vm_page_t	vm_page_alloc(
+	vm_object_t	object,
+	vm_offset_t	offset);
+extern void		vm_page_init(
+	vm_page_t	mem,
+	vm_offset_t	phys_addr);
+extern void		vm_page_init_mach(struct vm_page *);
+extern void		vm_page_free(vm_page_t);
+extern void		vm_page_activate(vm_page_t);
+extern void		vm_page_deactivate(vm_page_t);
+extern void		vm_page_rename(
+	vm_page_t	mem,
+	vm_object_t	new_object,
+	vm_offset_t	new_offset);
+extern void		vm_page_insert(
+	vm_page_t	mem,
+	vm_object_t	object,
+	vm_offset_t	offset);
+extern void		vm_page_remove(
+	vm_page_t	mem);
+
+extern void		vm_page_zero_fill(vm_page_t);
+extern void		vm_page_copy(vm_page_t src_m, vm_page_t dest_m);
+
+extern void		vm_page_wire(vm_page_t);
+extern void		vm_page_unwire(vm_page_t);
+
+/*
+ *	Functions implemented as macros
+ */
+
+#define PAGE_ASSERT_WAIT(m, interruptible)			\
+		MACRO_BEGIN					\
+		(m)->wanted = TRUE;				\
+		assert_wait((event_t) (m), (interruptible));	\
+		MACRO_END
+
+#define PAGE_WAKEUP_DONE(m)					\
+		MACRO_BEGIN					\
+		(m)->busy = FALSE;				\
+		if ((m)->wanted) {				\
+			(m)->wanted = FALSE;			\
+			thread_wakeup(((event_t) m));		\
+		}						\
+		MACRO_END
+
+#define PAGE_WAKEUP(m)						\
+		MACRO_BEGIN					\
+		if ((m)->wanted) {				\
+			(m)->wanted = FALSE;			\
+			thread_wakeup((event_t) (m));		\
+		}						\
+		MACRO_END
+
+#define VM_PAGE_FREE(p) 			\
+		MACRO_BEGIN			\
+		vm_page_lock_queues();		\
+		vm_page_free(p);		\
+		vm_page_unlock_queues();	\
+		MACRO_END
+
+/*
+ *	Macro to be used in place of pmap_enter()
+ */
+
+#define PMAP_ENTER(pmap, virtual_address, page, protection, wired) \
+		MACRO_BEGIN					\
+		pmap_enter(					\
+			(pmap),					\
+			(virtual_address),			\
+			(page)->phys_addr,			\
+			(protection) & ~(page)->page_lock,	\
+			(wired)					\
+		 );						\
+		MACRO_END
+
+#define	VM_PAGE_WAIT(continuation)	vm_page_wait(continuation)
+
+#define vm_page_lock_queues()	simple_lock(&vm_page_queue_lock)
+#define vm_page_unlock_queues()	simple_unlock(&vm_page_queue_lock)
+
+#define VM_PAGE_QUEUES_REMOVE(mem)				\
+	MACRO_BEGIN						\
+	if (mem->active) {					\
+		queue_remove(&vm_page_queue_active,		\
+			mem, vm_page_t, pageq);			\
+		mem->active = FALSE;				\
+		vm_page_active_count--;				\
+	}							\
+								\
+	if (mem->inactive) {					\
+		queue_remove(&vm_page_queue_inactive,		\
+			mem, vm_page_t, pageq);			\
+		mem->inactive = FALSE;				\
+		vm_page_inactive_count--;			\
+	}							\
+	MACRO_END
+
 #endif /* _VM_VM_PAGE_H */
diff --git a/vm/vm_resident.c b/vm/vm_resident.c
index d3b5a8e..88880ef 100644
--- a/vm/vm_resident.c
+++ b/vm/vm_resident.c
@@ -46,6 +46,7 @@
 #include <machine/vm_param.h>
 #include <kern/xpr.h>
 #include <kern/slab.h>
+#include <kern/rdxtree.h>
 #include <vm/pmap.h>
 #include <vm/vm_map.h>
 #include <vm/vm_page.h>
@@ -54,7 +55,6 @@
 
 #if	MACH_VM_DEBUG
 #include <mach/kern_return.h>
-#include <mach_debug/hash_info.h>
 #include <vm/vm_user.h>
 #endif
 
@@ -79,33 +79,6 @@ vm_offset_t virtual_space_start;
 vm_offset_t virtual_space_end;
 
 /*
- *	The vm_page_lookup() routine, which provides for fast
- *	(virtual memory object, offset) to page lookup, employs
- *	the following hash table.  The vm_page_{insert,remove}
- *	routines install and remove associations in the table.
- *	[This table is often called the virtual-to-physical,
- *	or VP, table.]
- */
-typedef struct {
-	decl_simple_lock_data(,lock)
-	vm_page_t pages;
-} vm_page_bucket_t;
-
-vm_page_bucket_t *vm_page_buckets;		/* Array of buckets */
-unsigned int	vm_page_bucket_count = 0;	/* How big is array? */
-unsigned int	vm_page_hash_mask;		/* Mask for hash function */
-
-/*
- *	Resident page structures are initialized from
- *	a template (see vm_page_alloc).
- *
- *	When adding a new field to the virtual memory
- *	object structure, be sure to add initialization
- *	(see vm_page_bootstrap).
- */
-struct vm_page	vm_page_template;
-
-/*
  *	Resident pages that represent real memory
  *	are allocated from a free list.
  */
@@ -117,8 +90,6 @@ int		vm_page_free_count;
 int		vm_page_fictitious_count;
 int		vm_page_external_count;
 
-unsigned int	vm_page_free_count_minimum;	/* debugging */
-
 /*
  *	Occasionally, the virtual memory system uses
  *	resident page structures that do not refer to
@@ -182,9 +153,6 @@ boolean_t vm_page_deactivate_hint = TRUE;
  *
  *	Initializes the resident memory module.
  *
- *	Allocates memory for the page cells, and
- *	for the object/offset-to-page hash table headers.
- *	Each page cell is initialized and placed on the free list.
  *	Returns the range of available kernel virtual memory.
  */
 
@@ -192,40 +160,6 @@ void vm_page_bootstrap(
 	vm_offset_t *startp,
 	vm_offset_t *endp)
 {
-	vm_page_t m;
-	int i;
-
-	/*
-	 *	Initialize the vm_page template.
-	 */
-
-	m = &vm_page_template;
-	m->object = VM_OBJECT_NULL;	/* reset later */
-	m->offset = 0;			/* reset later */
-	m->wire_count = 0;
-
-	m->inactive = FALSE;
-	m->active = FALSE;
-	m->laundry = FALSE;
-	m->free = FALSE;
-	m->external = FALSE;
-
-	m->busy = TRUE;
-	m->wanted = FALSE;
-	m->tabled = FALSE;
-	m->fictitious = FALSE;
-	m->private = FALSE;
-	m->absent = FALSE;
-	m->error = FALSE;
-	m->dirty = FALSE;
-	m->precious = FALSE;
-	m->reference = FALSE;
-
-	m->phys_addr = 0;		/* reset later */
-
-	m->page_lock = VM_PROT_NONE;
-	m->unlock_request = VM_PROT_NONE;
-
 	/*
 	 *	Initialize the page queues.
 	 */
@@ -241,46 +175,6 @@ void vm_page_bootstrap(
 	vm_page_free_wanted = 0;
 
 	/*
-	 *	Steal memory for the kernel map entries.
-	 */
-
-	kentry_data = pmap_steal_memory(kentry_data_size);
-
-	/*
-	 *	Allocate (and initialize) the virtual-to-physical
-	 *	table hash buckets.
-	 *
-	 *	The number of buckets should be a power of two to
-	 *	get a good hash function.  The following computation
-	 *	chooses the first power of two that is greater
-	 *	than the number of physical pages in the system.
-	 */
-
-	if (vm_page_bucket_count == 0) {
-		unsigned int npages = pmap_free_pages();
-
-		vm_page_bucket_count = 1;
-		while (vm_page_bucket_count < npages)
-			vm_page_bucket_count <<= 1;
-	}
-
-	vm_page_hash_mask = vm_page_bucket_count - 1;
-
-	if (vm_page_hash_mask & vm_page_bucket_count)
-		printf("vm_page_bootstrap: WARNING -- strange page hash\n");
-
-	vm_page_buckets = (vm_page_bucket_t *)
-		pmap_steal_memory(vm_page_bucket_count *
-				  sizeof(vm_page_bucket_t));
-
-	for (i = 0; i < vm_page_bucket_count; i++) {
-		vm_page_bucket_t *bucket = &vm_page_buckets[i];
-
-		bucket->pages = VM_PAGE_NULL;
-		simple_lock_init(&bucket->lock);
-	}
-
-	/*
 	 *	Machine-dependent code allocates the resident page table.
 	 *	It uses vm_page_init to initialize the page frames.
 	 *	The code also returns to us the virtual space available
@@ -296,125 +190,20 @@ void vm_page_bootstrap(
 	*endp = virtual_space_end;
 
 	/*	printf("vm_page_bootstrap: %d free pages\n", vm_page_free_count);*/
-	vm_page_free_count_minimum = vm_page_free_count;
 }
 
 #ifndef	MACHINE_PAGES
-/*
- *	We implement pmap_steal_memory and pmap_startup with the help
- *	of two simpler functions, pmap_virtual_space and pmap_next_page.
- */
-
-vm_offset_t pmap_steal_memory(
-	vm_size_t size)
-{
-	vm_offset_t addr, vaddr, paddr;
-
-	/*
-	 *	We round the size to an integer multiple.
-	 */
-
-	size = (size + 3) &~ 3;
-
-	/*
-	 *	If this is the first call to pmap_steal_memory,
-	 *	we have to initialize ourself.
-	 */
-
-	if (virtual_space_start == virtual_space_end) {
-		pmap_virtual_space(&virtual_space_start, &virtual_space_end);
-
-		/*
-		 *	The initial values must be aligned properly, and
-		 *	we don't trust the pmap module to do it right.
-		 */
-
-		virtual_space_start = round_page(virtual_space_start);
-		virtual_space_end = trunc_page(virtual_space_end);
-	}
-
-	/*
-	 *	Allocate virtual memory for this request.
-	 */
-
-	addr = virtual_space_start;
-	virtual_space_start += size;
-
-	/*
-	 *	Allocate and map physical pages to back new virtual pages.
-	 */
-
-	for (vaddr = round_page(addr);
-	     vaddr < addr + size;
-	     vaddr += PAGE_SIZE) {
-		if (!pmap_next_page(&paddr))
-			panic("pmap_steal_memory");
-
-		/*
-		 *	XXX Logically, these mappings should be wired,
-		 *	but some pmap modules barf if they are.
-		 */
-
-		pmap_enter(kernel_pmap, vaddr, paddr,
-			   VM_PROT_READ|VM_PROT_WRITE, FALSE);
-	}
-
-	return addr;
-}
-
 void pmap_startup(
 	vm_offset_t *startp,
 	vm_offset_t *endp)
 {
-	unsigned int i, npages, pages_initialized;
-	vm_page_t pages;
-	vm_offset_t paddr;
-
-	/*
-	 *	We calculate how many page frames we will have
-	 *	and then allocate the page structures in one chunk.
-	 */
-
-	npages = ((PAGE_SIZE * pmap_free_pages() +
-		   (round_page(virtual_space_start) - virtual_space_start)) /
-		  (PAGE_SIZE + sizeof *pages));
-
-	pages = (vm_page_t) pmap_steal_memory(npages * sizeof *pages);
-
-	/*
-	 *	Initialize the page frames.
-	 */
-
-	for (i = 0, pages_initialized = 0; i < npages; i++) {
-		if (!pmap_next_page(&paddr))
-			break;
-
-		vm_page_init(&pages[i], paddr);
-		pages_initialized++;
-	}
-	i = 0;
-	while (pmap_next_page(&paddr))
-		i++;
-	if (i)
-		printf("%u memory page(s) left away\n", i);
-
-	/*
-	 * Release pages in reverse order so that physical pages
-	 * initially get allocated in ascending addresses. This keeps
-	 * the devices (which must address physical memory) happy if
-	 * they require several consecutive pages.
-	 */
-
-	for (i = pages_initialized; i > 0; i--) {
-		vm_page_release(&pages[i - 1], FALSE);
-	}
-
+	pmap_virtual_space(&virtual_space_start, &virtual_space_end);
 	/*
-	 *	We have to re-align virtual_space_start,
-	 *	because pmap_steal_memory has been using it.
+	 *	The initial values must be aligned properly, and
+	 *	we don't trust the pmap module to do it right.
 	 */
-
 	virtual_space_start = round_page(virtual_space_start);
+	virtual_space_end = trunc_page(virtual_space_end);
 
 	*startp = virtual_space_start;
 	*endp = virtual_space_end;
@@ -448,6 +237,8 @@ void vm_page_create(
 	vm_offset_t	start,
 	vm_offset_t	end)
 {
+	printf ("XXX: vm_page_create stubbed out\n");
+	return;
 	vm_offset_t paddr;
 	vm_page_t m;
 
@@ -463,17 +254,11 @@ void vm_page_create(
 	}
 }
 
-/*
- *	vm_page_hash:
- *
- *	Distributes the object/offset key pair among hash buckets.
- *
- *	NOTE:	To get a good hash function, the bucket count should
- *		be a power of two.
- */
-#define vm_page_hash(object, offset) \
-	(((unsigned int)(vm_offset_t)object + (unsigned int)atop(offset)) \
-		& vm_page_hash_mask)
+static rdxtree_key_t
+offset_key(vm_offset_t offset)
+{
+	return (rdxtree_key_t) atop(offset);
+}
 
 /*
  *	vm_page_insert:		[ internal use only ]
@@ -489,8 +274,6 @@ void vm_page_insert(
 	vm_object_t	object,
 	vm_offset_t	offset)
 {
-	vm_page_bucket_t *bucket;
-
 	VM_PAGE_CHECK(mem);
 
 	if (mem->tabled)
@@ -504,20 +287,10 @@ void vm_page_insert(
 	mem->offset = offset;
 
 	/*
-	 *	Insert it into the object_object/offset hash table
-	 */
-
-	bucket = &vm_page_buckets[vm_page_hash(object, offset)];
-	simple_lock(&bucket->lock);
-	mem->next = bucket->pages;
-	bucket->pages = mem;
-	simple_unlock(&bucket->lock);
-
-	/*
-	 *	Now link into the object's list of backed pages.
+	 *	Insert it into the objects radix tree.
 	 */
 
-	queue_enter(&object->memq, mem, vm_page_t, listq);
+	rdxtree_insert(&object->memt, offset_key(offset), mem);
 	mem->tabled = TRUE;
 
 	/*
@@ -561,7 +334,8 @@ void vm_page_replace(
 	vm_object_t	object,
 	vm_offset_t	offset)
 {
-	vm_page_bucket_t *bucket;
+	struct vm_page *old;
+	void **slot;
 
 	VM_PAGE_CHECK(mem);
 
@@ -576,54 +350,23 @@ void vm_page_replace(
 	mem->offset = offset;
 
 	/*
-	 *	Insert it into the object_object/offset hash table,
-	 *	replacing any page that might have been there.
+	 *	Insert it into the objects radix tree, replacing any
+	 *	page that might have been there.
 	 */
+	slot = rdxtree_lookup_slot(&object->memt, offset_key(offset));
+	old = rdxtree_replace_slot(slot, mem);
+	if (old != VM_PAGE_NULL) {
+		old->tabled = FALSE;
+		object->resident_page_count--;
 
-	bucket = &vm_page_buckets[vm_page_hash(object, offset)];
-	simple_lock(&bucket->lock);
-	if (bucket->pages) {
-		vm_page_t *mp = &bucket->pages;
-		vm_page_t m = *mp;
-		do {
-			if (m->object == object && m->offset == offset) {
-				/*
-				 * Remove page from bucket and from object,
-				 * and return it to the free list.
-				 */
-				*mp = m->next;
-				queue_remove(&object->memq, m, vm_page_t,
-					     listq);
-				m->tabled = FALSE;
-				object->resident_page_count--;
-
-				if (object->can_persist
-				    && (object->ref_count == 0))
-					vm_object_cached_pages_update(-1);
-
-				/*
-				 * Return page to the free list.
-				 * Note the page is not tabled now, so this
-				 * won't self-deadlock on the bucket lock.
-				 */
-
-				vm_page_free(m);
-				break;
-			}
-			mp = &m->next;
-		} while ((m = *mp) != 0);
-		mem->next = bucket->pages;
-	} else {
-		mem->next = VM_PAGE_NULL;
-	}
-	bucket->pages = mem;
-	simple_unlock(&bucket->lock);
+		if (object->can_persist
+		    && (object->ref_count == 0))
+			vm_object_cached_pages_update(-1);
 
-	/*
-	 *	Now link into the object's list of backed pages.
-	 */
+		/* And free it.  */
+		vm_page_free(old);
+	}
 
-	queue_enter(&object->memq, mem, vm_page_t, listq);
 	mem->tabled = TRUE;
 
 	/*
@@ -650,38 +393,11 @@ void vm_page_replace(
 void vm_page_remove(
 	vm_page_t		mem)
 {
-	vm_page_bucket_t	*bucket;
-	vm_page_t		this;
-
 	assert(mem->tabled);
 	VM_PAGE_CHECK(mem);
 
-	/*
-	 *	Remove from the object_object/offset hash table
-	 */
-
-	bucket = &vm_page_buckets[vm_page_hash(mem->object, mem->offset)];
-	simple_lock(&bucket->lock);
-	if ((this = bucket->pages) == mem) {
-		/* optimize for common case */
-
-		bucket->pages = mem->next;
-	} else {
-		vm_page_t	*prev;
-
-		for (prev = &this->next;
-		     (this = *prev) != mem;
-		     prev = &this->next)
-			continue;
-		*prev = this->next;
-	}
-	simple_unlock(&bucket->lock);
-
-	/*
-	 *	Now remove from the object's list of backed pages.
-	 */
-
-	queue_remove(&mem->object->memq, mem, vm_page_t, listq);
+	/* Remove from the objects radix tree.  */
+	rdxtree_remove(&mem->object->memt, offset_key(mem->offset));
 
 	/*
 	 *	And show that the object has one fewer resident
@@ -709,23 +425,7 @@ vm_page_t vm_page_lookup(
 	vm_object_t		object,
 	vm_offset_t		offset)
 {
-	vm_page_t		mem;
-	vm_page_bucket_t 	*bucket;
-
-	/*
-	 *	Search the hash table for this object/offset pair
-	 */
-
-	bucket = &vm_page_buckets[vm_page_hash(object, offset)];
-
-	simple_lock(&bucket->lock);
-	for (mem = bucket->pages; mem != VM_PAGE_NULL; mem = mem->next) {
-		VM_PAGE_CHECK(mem);
-		if ((mem->object == object) && (mem->offset == offset))
-			break;
-	}
-	simple_unlock(&bucket->lock);
-	return mem;
+	return rdxtree_lookup(&object->memt, offset_key(offset));
 }
 
 /*
@@ -753,21 +453,6 @@ void vm_page_rename(
 }
 
 /*
- *	vm_page_init:
- *
- *	Initialize the fields in a new page.
- *	This takes a structure with random values and initializes it
- *	so that it can be given to vm_page_release or vm_page_insert.
- */
-void vm_page_init(
-	vm_page_t	mem,
-	vm_offset_t	phys_addr)
-{
-	*mem = vm_page_template;
-	mem->phys_addr = phys_addr;
-}
-
-/*
  *	vm_page_grab_fictitious:
  *
  *	Remove a fictitious page from the free list.
@@ -783,10 +468,10 @@ vm_page_t vm_page_grab_fictitious(void)
 	if (m != VM_PAGE_NULL) {
 		vm_page_fictitious_count--;
 		vm_page_queue_fictitious = (vm_page_t) m->pageq.next;
-		m->free = FALSE;
+		assert(m->fictitious);
+		assert(! m->tabled);
 	}
 	simple_unlock(&vm_page_queue_free_lock);
-
 	return m;
 }
 
@@ -799,10 +484,9 @@ vm_page_t vm_page_grab_fictitious(void)
 void vm_page_release_fictitious(
 	vm_page_t m)
 {
+	assert(m->fictitious);
+	assert(! m->tabled);
 	simple_lock(&vm_page_queue_free_lock);
-	if (m->free)
-		panic("vm_page_release_fictitious");
-	m->free = TRUE;
 	m->pageq.next = (queue_entry_t) vm_page_queue_fictitious;
 	vm_page_queue_fictitious = m;
 	vm_page_fictitious_count++;
@@ -841,22 +525,43 @@ void vm_page_more_fictitious(void)
  */
 
 boolean_t vm_page_convert(
-	vm_page_t m,
+	struct vm_page **mp,
 	boolean_t external)
 {
-	vm_page_t real_m;
+	struct vm_page *real_m, *fict_m, *old;
+	void **slot;
+
+	fict_m = *mp;
+
+	assert(fict_m->fictitious);
+	assert(fict_m->phys_addr == vm_page_fictitious_addr);
+	assert(! fict_m->active);
+	assert(! fict_m->inactive);
 
 	real_m = vm_page_grab(external);
 	if (real_m == VM_PAGE_NULL)
 		return FALSE;
 
-	m->phys_addr = real_m->phys_addr;
-	m->fictitious = FALSE;
+	memcpy(&real_m->vm_page_header,
+	       &fict_m->vm_page_header,
+	       sizeof *fict_m - VM_PAGE_HEADER_SIZE);
+
+	real_m->fictitious = FALSE;
+	fict_m->tabled = FALSE;
+
+	/* Fix radix tree entry.  */
+	/* XXX is the object locked? */
+	slot = rdxtree_lookup_slot(&fict_m->object->memt,
+				   offset_key(fict_m->offset));
+	old = rdxtree_replace_slot(slot, real_m);
+	assert(old == fict_m);
 
-	real_m->phys_addr = vm_page_fictitious_addr;
-	real_m->fictitious = TRUE;
+	assert(real_m->phys_addr != vm_page_fictitious_addr);
+	assert(fict_m->fictitious);
+	assert(fict_m->phys_addr == vm_page_fictitious_addr);
 
-	vm_page_release_fictitious(real_m);
+	vm_page_release_fictitious(fict_m);
+	*mp = real_m;
 	return TRUE;
 }
 
@@ -888,16 +593,15 @@ vm_page_t vm_page_grab(
 		return VM_PAGE_NULL;
 	}
 
-	if (vm_page_queue_free == VM_PAGE_NULL)
-		panic("vm_page_grab");
-
-	if (--vm_page_free_count < vm_page_free_count_minimum)
-		vm_page_free_count_minimum = vm_page_free_count;
 	if (external)
 		vm_page_external_count++;
-	mem = vm_page_queue_free;
-	vm_page_queue_free = (vm_page_t) mem->pageq.next;
-	mem->free = FALSE;
+
+	mem = vm_page_alloc_p(0, VM_PAGE_SEL_DIRECTMAP, VM_PAGE_OBJECT);
+	if (! mem) {
+		simple_unlock(&vm_page_queue_free_lock);
+		return VM_PAGE_NULL;
+	}
+	vm_page_init_mach(mem);
 	mem->extcounted = mem->external = external;
 	simple_unlock(&vm_page_queue_free_lock);
 
@@ -930,237 +634,6 @@ vm_offset_t vm_page_grab_phys_addr(void)
 }
 
 /*
- *	vm_page_grab_contiguous_pages:
- *
- *	Take N pages off the free list, the pages should
- *	cover a contiguous range of physical addresses.
- *	[Used by device drivers to cope with DMA limitations]
- *
- *	Returns the page descriptors in ascending order, or
- *	Returns KERN_RESOURCE_SHORTAGE if it could not.
- */
-
-/* Biggest phys page number for the pages we handle in VM */
-
-vm_size_t	vm_page_big_pagenum = 0;	/* Set this before call! */
-
-kern_return_t
-vm_page_grab_contiguous_pages(
-	int		npages,
-	vm_page_t	pages[],
-	natural_t	*bits,
-	boolean_t	external)
-{
-	int		first_set;
-	int		size, alloc_size;
-	kern_return_t	ret;
-	vm_page_t       mem, *prevmemp;
-
-#ifndef	NBBY
-#define	NBBY	8	/* size in bits of sizeof()`s unity */
-#endif
-
-#define	NBPEL	(sizeof(natural_t)*NBBY)
-
-	size = (vm_page_big_pagenum + NBPEL - 1)
-		& ~(NBPEL - 1);				/* in bits */
-
-	size = size / NBBY;				/* in bytes */
-
-	/*
-	 * If we are called before the VM system is fully functional
-	 * the invoker must provide us with the work space. [one bit
-	 * per page starting at phys 0 and up to vm_page_big_pagenum]
-	 */
-	if (bits == 0) {
-		alloc_size = round_page(size);
-		if (kmem_alloc_wired(kernel_map,
-				     (vm_offset_t *)&bits,
-				     alloc_size)
-			!= KERN_SUCCESS)
-		    return KERN_RESOURCE_SHORTAGE;
-	} else
-		alloc_size = 0;
-
-	memset(bits, 0, size);
-
-	/*
-	 * A very large granularity call, its rare so that is ok
-	 */
-	simple_lock(&vm_page_queue_free_lock);
-
-	/*
-	 *	Do not dip into the reserved pool.
-	 */
-
-	if ((vm_page_free_count < vm_page_free_reserved)
-	    || (vm_page_external_count >= vm_page_external_limit)) {
-		printf_once("no more room for vm_page_grab_contiguous_pages");
-		simple_unlock(&vm_page_queue_free_lock);
-		return KERN_RESOURCE_SHORTAGE;
-	}
-
-	/*
-	 *	First pass through, build a big bit-array of
-	 *	the pages that are free.  It is not going to
-	 *	be too large anyways, in 4k we can fit info
-	 *	for 32k pages.
-	 */
-	mem = vm_page_queue_free;
-	while (mem) {
-		int word_index, bit_index;
-
-		bit_index = (mem->phys_addr >> PAGE_SHIFT);
-		word_index = bit_index / NBPEL;
-		bit_index = bit_index - (word_index * NBPEL);
-		bits[word_index] |= 1 << bit_index;
-
-		mem = (vm_page_t) mem->pageq.next;
-	}
-
-	/*
-	 *	Second loop. Scan the bit array for NPAGES
-	 *	contiguous bits.  That gives us, if any,
-	 *	the range of pages we will be grabbing off
-	 *	the free list.
-	 */
-	{
-	    int	bits_so_far = 0, i;
-
-		first_set = 0;
-
-		for (i = 0; i < size; i += sizeof(natural_t)) {
-
-		    natural_t	v = bits[i / sizeof(natural_t)];
-		    int		bitpos;
-
-		    /*
-		     * Bitscan this one word
-		     */
-		    if (v) {
-			/*
-			 * keep counting them beans ?
-			 */
-			bitpos = 0;
-
-			if (bits_so_far) {
-count_ones:
-			    while (v & 1) {
-				bitpos++;
-				/*
-				 * got enough beans ?
-				 */
-				if (++bits_so_far == npages)
-				    goto found_em;
-				v >>= 1;
-			    }
-			    /* if we are being lucky, roll again */
-			    if (bitpos == NBPEL)
-			    	continue;
-			}
-
-			/*
-			 * search for beans here
-			 */
-			bits_so_far = 0;
-			while ((bitpos < NBPEL) && ((v & 1) == 0)) {
-			    bitpos++;
-			    v >>= 1;
-			}
-			if (v & 1) {
-			    first_set = (i * NBBY) + bitpos;
-			    goto count_ones;
-			}
-		    }
-		    /*
-		     * No luck
-		     */
-		    bits_so_far = 0;
-		}
-	}
-
-	/*
-	 *	We could not find enough contiguous pages.
-	 */
-	simple_unlock(&vm_page_queue_free_lock);
-
-	printf_once("no contiguous room for vm_page_grab_contiguous_pages");
-	ret = KERN_RESOURCE_SHORTAGE;
-	goto out;
-
-	/*
-	 *	Final pass. Now we know which pages we want.
-	 *	Scan the list until we find them all, grab
-	 *	pages as we go.  FIRST_SET tells us where
-	 *	in the bit-array our pages start.
-	 */
-found_em:
-	vm_page_free_count -= npages;
-	if (vm_page_free_count < vm_page_free_count_minimum)
-		vm_page_free_count_minimum = vm_page_free_count;
-	if (external)
-		vm_page_external_count += npages;
-	{
-	    vm_offset_t	first_phys, last_phys;
-
-	    /* cache values for compare */
-	    first_phys = first_set << PAGE_SHIFT;
-	    last_phys = first_phys + (npages << PAGE_SHIFT);/* not included */
-
-	    /* running pointers */
-	    mem = vm_page_queue_free;
-	    prevmemp = &vm_page_queue_free;
-
-	    while (mem) {
-
-		vm_offset_t	addr;
-
-		addr = mem->phys_addr;
-
-		if ((addr >= first_phys) &&
-		    (addr <  last_phys)) {
-		    *prevmemp = (vm_page_t) mem->pageq.next;
-		    pages[(addr - first_phys) >> PAGE_SHIFT] = mem;
-		    mem->free = FALSE;
-		    mem->extcounted = mem->external = external;
-		    /*
-		     * Got them all ?
-		     */
-		    if (--npages == 0) break;
-		} else
-		    prevmemp = (vm_page_t *) &mem->pageq.next;
-
-		mem = (vm_page_t) mem->pageq.next;
-	    }
-	}
-
-	simple_unlock(&vm_page_queue_free_lock);
-
-	/*
-	 *	Decide if we should poke the pageout daemon.
-	 *	We do this if the free count is less than the low
-	 *	water mark, or if the free count is less than the high
-	 *	water mark (but above the low water mark) and the inactive
-	 *	count is less than its target.
-	 *
-	 *	We don't have the counts locked ... if they change a little,
-	 *	it doesn't really matter.
-	 */
-
-	if ((vm_page_free_count < vm_page_free_min) ||
-	    ((vm_page_free_count < vm_page_free_target) &&
-	     (vm_page_inactive_count < vm_page_inactive_target)))
-		thread_wakeup(&vm_page_free_wanted);
-
-	ret = KERN_SUCCESS;
-out:
-	if (alloc_size)
-		kmem_free(kernel_map, (vm_offset_t) bits, alloc_size);
-
-	return ret;
-}
-
-/*
  *	vm_page_release:
  *
  *	Return a page to the free list.
@@ -1171,12 +644,7 @@ void vm_page_release(
 	boolean_t 	external)
 {
 	simple_lock(&vm_page_queue_free_lock);
-	if (mem->free)
-		panic("vm_page_release");
-	mem->free = TRUE;
-	mem->pageq.next = (queue_entry_t) vm_page_queue_free;
-	vm_page_queue_free = mem;
-	vm_page_free_count++;
+	vm_page_free_p(mem, 0);
 	if (external)
 		vm_page_external_count--;
 
@@ -1283,9 +751,6 @@ vm_page_t vm_page_alloc(
 void vm_page_free(
 	vm_page_t	mem)
 {
-	if (mem->free)
-		panic("vm_page_free");
-
 	if (mem->tabled)
 		vm_page_remove(mem);
 	VM_PAGE_QUEUES_REMOVE(mem);
@@ -1459,47 +924,6 @@ void vm_page_copy(
 	pmap_copy_page(src_m->phys_addr, dest_m->phys_addr);
 }
 
-#if	MACH_VM_DEBUG
-/*
- *	Routine:	vm_page_info
- *	Purpose:
- *		Return information about the global VP table.
- *		Fills the buffer with as much information as possible
- *		and returns the desired size of the buffer.
- *	Conditions:
- *		Nothing locked.  The caller should provide
- *		possibly-pageable memory.
- */
-
-unsigned int
-vm_page_info(
-	hash_info_bucket_t *info,
-	unsigned int	count)
-{
-	int i;
-
-	if (vm_page_bucket_count < count)
-		count = vm_page_bucket_count;
-
-	for (i = 0; i < count; i++) {
-		vm_page_bucket_t *bucket = &vm_page_buckets[i];
-		unsigned int bucket_count = 0;
-		vm_page_t m;
-
-		simple_lock(&bucket->lock);
-		for (m = bucket->pages; m != VM_PAGE_NULL; m = m->next)
-			bucket_count++;
-		simple_unlock(&bucket->lock);
-
-		/* don't touch pageable memory while holding locks */
-		info[i].hib_count = bucket_count;
-	}
-
-	return vm_page_bucket_count;
-}
-#endif	/* MACH_VM_DEBUG */
-
-
 #if	MACH_KDB
 #define	printf	kdbprintf
 
@@ -1514,8 +938,6 @@ void		vm_page_print(p)
 	 printf("wire_count %d,", p->wire_count);
 	 printf(" %s",
 		(p->active ? "active" : (p->inactive ? "inactive" : "loose")));
-	 printf("%s",
-		(p->free ? " free" : ""));
 	 printf("%s ",
 		(p->laundry ? " laundry" : ""));
 	 printf("%s",