Date: Wed, 27 Aug 2008 20:00:42 GMT From: Mayur Shardul <mayur@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 148646 for review Message-ID: <200808272000.m7RK0gVR040519@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=148646 Change 148646 by mayur@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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200808272000.m7RK0gVR040519>