PERFORCE change 145048 for review

[Mayur Shardul]

http://perforce.freebsd.org/chv.cgi?CH=145048

Change 145048 by mayur at mayur_freebsd_vm on 2008/07/11 03:41:35

	radix tree integrated in the kernel. Memory for nodes is preallocated
	at the boot time.

Affected files ...

.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/conf/files#2 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.c#2 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.h#2 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#2 edit

Differences ...

==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/conf/files#2 (text+ko) ====

@@ -2194,6 +2194,7 @@
 vm/vm_unix.c			standard
 vm/vm_zeroidle.c		standard
 vm/vnode_pager.c		standard
+vm/radix_tree.c			standard
 xdr/xdr.c			optional krpc | nfslockd
 xdr/xdr_array.c			optional krpc | nfslockd
 xdr/xdr_mbuf.c			optional krpc | nfslockd

==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.c#2 (text+ko) ====

@@ -216,6 +216,11 @@
 	TAILQ_INIT(&object->memq);
 	LIST_INIT(&object->shadow_head);
 
+	object->rtree.rt_bits_per_level = 4;
+	object->rtree.rt_height = 0;
+	object->rtree.rt_root = NULL;
+	object->rtree.rt_max_height = (8*sizeof(rtidx_t))/4;
+	object->rtree.rt_max_index = ~((rtidx_t)0);
 	object->root = NULL;
 	object->type = type;
 	object->size = size;
@@ -691,6 +696,7 @@
 #endif
 	if (__predict_false(object->cache != NULL))
 		vm_page_cache_free(object, 0, 0);
+	radix_tree_shrink(&object->rtree);
 
 	/*
 	 * Let the pager know object is dead.

==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.h#2 (text+ko) ====

@@ -67,6 +67,8 @@
 #ifndef	_VM_OBJECT_
 #define	_VM_OBJECT_
 
+#include "radix_tree.h"
+
 #include <sys/queue.h>
 #include <sys/_lock.h>
 #include <sys/_mutex.h>
@@ -88,6 +90,7 @@
 	LIST_ENTRY(vm_object) shadow_list; /* chain of shadow objects */
 	TAILQ_HEAD(, vm_page) memq;	/* list of resident pages */
 	vm_page_t root;			/* root of the resident page splay tree */
+	struct radix_tree rtree;	/* root of the resident page radix tree */
 	vm_pindex_t size;		/* Object size */
 	int generation;			/* generation ID */
 	int ref_count;			/* How many refs?? */

==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#2 (text+ko) ====

@@ -137,6 +137,9 @@
 struct mtx vm_page_queue_mtx;
 struct mtx vm_page_queue_free_mtx;
 
+extern SLIST_HEAD(, radix_node) res_rnodes_head;
+extern int rnode_size;
+
 vm_page_t vm_page_array = 0;
 int vm_page_array_size = 0;
 long first_page = 0;
@@ -269,6 +272,24 @@
 	vm_page_queues[PQ_ACTIVE].cnt = &cnt.v_active_count;
 	vm_page_queues[PQ_HOLD].cnt = &cnt.v_active_count;
 
+	/* reserve memory for radix nodes. */
+	rnode_size = sizeof(struct radix_node) +
+	    (sizeof(void *) * (0xf + 1));
+	new_end = end - (RESERVED_NODE_COUNT * rnode_size);
+	new_end = trunc_page(new_end);
+	mapped = pmap_map(&vaddr, new_end, end,
+	    VM_PROT_READ | VM_PROT_WRITE);
+	bzero((void *)mapped, end - new_end);
+	printf("Total number of pages reserved for radix nodes : %u\n",
+	    (end - new_end)/PAGE_SIZE);
+	end = new_end;
+	for(i = 0; i < RESERVED_NODE_COUNT; i++)
+	{
+		SLIST_INSERT_HEAD(&res_rnodes_head, (struct radix_node *)mapped,
+		    next);
+		mapped += rnode_size;
+	}
+
 	/*
 	 * Allocate memory for use when boot strapping the kernel memory
 	 * allocator.
@@ -672,6 +693,7 @@
 	}
 	object->root = m;
 	object->generation++;
+	radix_tree_insert(pindex,&object->rtree,m);
 
 	/*
 	 * show that the object has one more resident page.
@@ -730,6 +752,7 @@
 		root->right = m->right;
 	}
 	object->root = root;
+	radix_tree_remove(m->pindex,&object->rtree);
 	TAILQ_REMOVE(&object->memq, m, listq);
 
 	/*
@@ -1648,6 +1671,7 @@
 	TAILQ_REMOVE(&object->memq, m, listq);
 	object->resident_page_count--;
 	object->generation++;
+	radix_tree_remove(m->pindex,&object->rtree);
 
 	/*
 	 * Insert the page into the object's collection of cached pages