PERFORCE change 148646 for review

[Mayur Shardul]

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

Change 148646 by mayur at mayur_freebsd_vm on 2008/08/27 20:00:07

	Updated README and TODO, same fixes to the radix_tree.c.

Affected files ...

.. //depot/projects/soc2008/mayur_vmalgo/README#3 edit
.. //depot/projects/soc2008/mayur_vmalgo/TODO#3 edit
.. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#6 edit

Differences ...

==== //depot/projects/soc2008/mayur_vmalgo/README#3 (text+ko) ====

@@ -13,3 +13,8 @@
 both splay and radix trees are used in parallel with asserts on return 
 values. Once the integration is complete and tested the splay tree will be 
 removed.
+
+Benchmarking is done, check the wiki page for updates.
+http://wiki.freebsd.org/MayurShardul/VM_Algorithm_Improvement
+
+

==== //depot/projects/soc2008/mayur_vmalgo/TODO#3 (text+ko) ====

@@ -1,7 +1,11 @@
 1. Implement radix tree in user-space.
 	complete
 2. Test and preliminary performance evaluation.
+	complete
 3. Integrate with kernel.
 	3a. Preallocate memory for radix nodes.
 		complete
+	3b. Removal of splay trees.
+		complete
 4. Testing and performance evaluation.
+	complete

==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#6 (text+ko) ====

@@ -108,6 +108,8 @@
 put_radix_node( struct radix_node *rnode, struct radix_tree *rtree)
 {
 	//free(rnode);
+	bzero((void *)rnode, sizeof(struct radix_node) +
+		sizeof(void *) * (MASK(rtree->rt_bits_per_level) + 1));
 	SLIST_INSERT_HEAD(&res_rnodes_head,rnode,next);
 }
 
@@ -247,6 +249,7 @@
 	int level, slot;
 	struct radix_node *tmp;
 
+
 	level = rtree->rt_height - 1;
 	tmp = rtree->rt_root;
 	while (tmp){
@@ -326,8 +329,8 @@
 
 			/* cut the branch before we return*/
 			if (branch != NULL){
-				slot = get_slot(index,rtree,
-				    branch_level);
+				slot = get_slot(index, rtree,
+						 branch_level);
     				tmp = branch->rn_children[slot];
 				branch->rn_children[slot] = NULL;
 				branch->rn_children_count--;
@@ -359,6 +362,9 @@
 	SLIST_HEAD(, radix_node) rtree_path =
 	    SLIST_HEAD_INITIALIZER(rtree_path);
 
+	if(index > MASK(rtree->rt_height * rtree->rt_bits_per_level))
+		index = MASK(rtree->rt_height * rtree->rt_bits_per_level);
+	
 	level = rtree->rt_height - 1;
 	tmp = rtree->rt_root;
 	while (tmp){
@@ -378,7 +384,7 @@
 			SLIST_REMOVE_HEAD(&rtree_path, next);
 			while (1)
 			{
-		    		while(slot <= MASK(rtree->rt_bits_per_level)
+		    		while (slot <= MASK(rtree->rt_bits_per_level)
 				    && tmp->rn_children[slot] == NULL)
 					slot++;
 				if(slot > MASK(rtree->rt_bits_per_level)){
@@ -393,6 +399,12 @@
 				if(level == 0){
 					return tmp->rn_children[slot];
 				}
+				if(((struct radix_node *)
+					(tmp->rn_children[slot]))
+					->rn_children_count == 0){
+					slot++;
+					continue;
+				}
 				SLIST_INSERT_HEAD(&rtree_path, tmp, next);
 				tmp = tmp->rn_children[slot];
 				slot = 0;
@@ -415,6 +427,9 @@
 	SLIST_HEAD(, radix_node) rtree_path =
 	    SLIST_HEAD_INITIALIZER(rtree_path);
 
+	if(index > MASK(rtree->rt_height * rtree->rt_bits_per_level))
+		index = MASK(rtree->rt_height * rtree->rt_bits_per_level);
+
 	level = rtree->rt_height - 1;
 	tmp = rtree->rt_root;
 	while (tmp){
@@ -431,11 +446,13 @@
 		     */
 			tmp = SLIST_FIRST(&rtree_path);
 			SLIST_REMOVE_HEAD(&rtree_path, next);
-			while (1)
-			{
-		    		while(slot >= 0 
-				    && tmp->rn_children[slot] == NULL)
+			while (1){
+		    		while (slot > 0 
+					&& tmp->rn_children[slot] == NULL)
+					slot--;
+				if(tmp->rn_children[slot] == NULL){
 					slot--;
+				}
 				if(slot > MASK(rtree->rt_bits_per_level)){
 			    		if(level == rtree->rt_height - 1)
 						return NULL;
@@ -445,6 +462,12 @@
 					slot = get_slot(index,rtree,level) - 1;
 					continue;
 				}
+				if(((struct radix_node *)
+					(tmp->rn_children[slot]))
+					->rn_children_count == 0){
+					slot--;
+					continue;
+				}
 				if(level == 0)
 					return tmp->rn_children[slot];
 				SLIST_INSERT_HEAD(&rtree_path, tmp, next);
@@ -456,8 +479,6 @@
 		level--;
 	}
 	return NULL;
-
-
 }
 /*
  * radix_tree_shrink: if possible reduces the height of the tree.