Date: Thu, 14 Aug 2008 04:37:34 GMT From: Mayur Shardul <mayur@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 147361 for review Message-ID: <200808140437.m7E4bYjS099754@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=147361 Change 147361 by mayur@mayur_freebsd_vm on 2008/08/14 04:37:01 Code not working. Affected files ... .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.c#2 edit .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.h#2 edit .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_map.c#2 edit .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.c#3 edit .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.h#3 edit .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#3 edit .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.h#2 edit .. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_reserv.c#2 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/Makefile#2 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#2 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.h#2 edit .. //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_test.c#2 edit Differences ... ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.c#2 (text+ko) ==== @@ -9,6 +9,7 @@ #include <sys/param.h> #include <sys/systm.h> #include <sys/malloc.h> +#include <sys/queue.h> #include "radix_tree.h" @@ -256,20 +257,132 @@ tmp = rtree->rt_root; while (tmp){ slot = get_slot(index,rtree,level); + if (level == 0) + return tmp->rn_children[slot]; + tmp = (struct radix_node *)tmp->rn_children[slot]; + level--; + } + return NULL; +} + +/* + * radix_tree_lookup_ge: Will lookup index greater than or equal + * to given index + */ +void * +radix_tree_lookup_ge(rtidx_t index, struct radix_tree *rtree) +{ + int level; + rtidx_t slot; + struct radix_node *tmp; + SLIST_HEAD(, radix_node) rtree_path = + SLIST_HEAD_INITIALIZER(rtree_path); + + level = rtree->rt_height - 1; + tmp = rtree->rt_root; + while (tmp){ + SLIST_INSERT_HEAD(&rtree_path, tmp,next); + slot = get_slot(index,rtree,level); if (level == 0){ - if (tmp->rn_children[slot] == NULL) - printf("radix_tree_lookup: index %lu not present\n" - ,(u_long)index); - - return tmp->rn_children[slot]; + if(NULL != tmp->rn_children[slot]) + return tmp->rn_children[slot]; } tmp = (struct radix_node *)tmp->rn_children[slot]; + while (tmp == NULL){ + /* index not present, see if there is something + * greater than index + */ + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + while (level != 0) + { + while(slot <= MASK(rtree->rt_bits_per_level) + && tmp->rn_children[slot] == NULL) + slot++; + if(slot > MASK(rtree->rt_bits_per_level)){ + if(level == rtree->rt_height - 1) + return NULL; + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + level++; + slot = get_slot(index,rtree,level) + 1; + continue; + } + if(level == 0){ + return tmp->rn_children[slot]; + } + SLIST_INSERT_HEAD(&rtree_path, tmp, next); + tmp = tmp->rn_children[slot]; + slot = 0; + level--; + } + return tmp; + } level--; } return NULL; + } /* + * radix_tree_lookup_le: Will lookup index less than or equal to given index + */ +void * +radix_tree_lookup_le(rtidx_t index, struct radix_tree *rtree) +{ + int level; + rtidx_t slot; + struct radix_node *tmp; + SLIST_HEAD(, radix_node) rtree_path = + SLIST_HEAD_INITIALIZER(rtree_path); + + level = rtree->rt_height - 1; + tmp = rtree->rt_root; + while (tmp){ + SLIST_INSERT_HEAD(&rtree_path, tmp,next); + slot = get_slot(index,rtree,level); + if (level == 0){ + if( NULL != tmp->rn_children[slot]) + return tmp->rn_children[slot]; + } + tmp = (struct radix_node *)tmp->rn_children[slot]; + while (tmp == NULL){ + /* index not present, see if there is something + * less than index + */ + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + while (level != 0) + { + while(slot >= 0 + && tmp->rn_children[slot] == NULL) + slot--; + if(slot > MASK(rtree->rt_bits_per_level)){ + if(level == rtree->rt_height - 1) + return NULL; + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + level++; + slot = get_slot(index,rtree,level) - 1; + continue; + } + if(level == 0){ + return tmp->rn_children[slot]; + } + SLIST_INSERT_HEAD(&rtree_path, tmp, next); + tmp = tmp->rn_children[slot]; + slot = MASK(rtree->rt_bits_per_level); + level--; + } + return tmp; + } + level--; + } + return NULL; + + +} +/* * radix_tree_remove: * * removes the specified index from the tree. If possible the height of the ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.h#2 (text+ko) ==== @@ -8,7 +8,7 @@ #ifndef _RADIX_TREE_ #define _RADIX_TREE_ -#define RESERVED_NODE_COUNT 0x1000 +#define RESERVED_NODE_COUNT 0xffff0 typedef vm_pindex_t rtidx_t; @@ -22,16 +22,17 @@ struct radix_node *rt_root; /* root node of the radix tree*/ int rt_height; /* number of levels + 1*/ int rt_max_height; /* number of levels defined*/ - rtidx_t rt_max_index; /* maximum possible value of the index*/ + rtidx_t rt_max_index; /* maximum possible value of the index*/ int rt_bits_per_level; /*Number of bits involved at each level*/ }; -struct radix_tree *create_radix_tree(int bits_per_level); -int radix_tree_insert(rtidx_t index, struct radix_tree *rtree, - void *val); -void *radix_tree_remove(rtidx_t index, struct radix_tree *rtree); -void *radix_tree_lookup(rtidx_t index, struct radix_tree *rtree); -void radix_tree_shrink(struct radix_tree *rtree); +struct radix_tree *create_radix_tree(int ); +int radix_tree_insert(rtidx_t , struct radix_tree *, void *); +void *radix_tree_remove(rtidx_t , struct radix_tree *); +void *radix_tree_lookup(rtidx_t , struct radix_tree *); +void *radix_tree_lookup_ge(rtidx_t , struct radix_tree *); +void *radix_tree_lookup_le(rtidx_t , struct radix_tree *); +void radix_tree_shrink(struct radix_tree *); #endif /* !_RADIX_TREE_ */ ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_map.c#2 (text+ko) ==== @@ -1503,9 +1503,10 @@ if ((p = TAILQ_FIRST(&object->memq)) != NULL) { if (p->pindex < pindex) { - p = vm_page_splay(pindex, object->root); - if ((object->root = p)->pindex < pindex) - p = TAILQ_NEXT(p, listq); + p = vm_page_lookup_geidx(pindex, object); + //p = vm_page_splay(pindex, object->root); + //if ((object->root = p)->pindex < pindex) + // p = TAILQ_NEXT(p, listq); } } /* ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.c#3 (text+ko) ==== @@ -221,7 +221,7 @@ 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->root = NULL; object->type = type; object->size = size; object->generation = 1; @@ -697,6 +697,9 @@ if (__predict_false(object->cache != NULL)) vm_page_cache_free(object, 0, 0); radix_tree_shrink(&object->rtree); + if(object->rtree.rt_root != NULL) + panic("VM_ALGO: rt_root != NULL\n"); + /* * Let the pager know object is dead. @@ -1362,9 +1365,10 @@ retry: if ((m = TAILQ_FIRST(&orig_object->memq)) != NULL) { if (m->pindex < offidxstart) { - m = vm_page_splay(offidxstart, orig_object->root); - if ((orig_object->root = m)->pindex < offidxstart) - m = TAILQ_NEXT(m, listq); + m = vm_page_lookup_geidx(offidxstart, orig_object); + //m = vm_page_splay(offidxstart, orig_object->root); + //if ((orig_object->root = m)->pindex < offidxstart) + // m = TAILQ_NEXT(m, listq); } } vm_page_lock_queues(); @@ -1884,9 +1888,10 @@ vm_page_lock_queues(); if ((p = TAILQ_FIRST(&object->memq)) != NULL) { if (p->pindex < start) { - p = vm_page_splay(start, object->root); - if ((object->root = p)->pindex < start) - p = TAILQ_NEXT(p, listq); + p = vm_page_lookup_geidx(start,object); + //p = vm_page_splay(start, object->root); + //if ((object->root = p)->pindex < start) + // p = TAILQ_NEXT(p, listq); } } /* ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.h#3 (text+ko) ==== @@ -89,7 +89,7 @@ LIST_HEAD(, vm_object) shadow_head; /* objects that this is a shadow for */ 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 */ + //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 */ ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#3 (text+ko) ==== @@ -280,7 +280,7 @@ 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", + printf("VM_ALGO:Total number of pages reserved for radix nodes : %x\n", (end - new_end)/PAGE_SIZE); end = new_end; for(i = 0; i < RESERVED_NODE_COUNT; i++) @@ -655,7 +655,7 @@ void vm_page_insert(vm_page_t m, vm_object_t object, vm_pindex_t pindex) { - vm_page_t root; + //vm_page_t root; VM_OBJECT_LOCK_ASSERT(object, MA_OWNED); if (m->object != NULL) @@ -670,6 +670,7 @@ /* * Now link into the object's ordered list of backed pages. */ + /* root = object->root; if (root == NULL) { m->left = NULL; @@ -691,7 +692,7 @@ TAILQ_INSERT_AFTER(&object->memq, root, m, listq); } } - object->root = m; + object->root = m;*/ object->generation++; radix_tree_insert(pindex,&object->rtree,m); @@ -729,7 +730,7 @@ vm_page_remove(vm_page_t m) { vm_object_t object; - vm_page_t root; + //vm_page_t root; if ((object = m->object) == NULL) return; @@ -743,6 +744,7 @@ /* * Now remove from the object's list of backed pages. */ + /* if (m != object->root) vm_page_splay(m->pindex, object->root); if (m->left == NULL) @@ -751,7 +753,8 @@ root = vm_page_splay(m->pindex, m->left); root->right = m->right; } - object->root = root; + object->root = root;*/ + radix_tree_remove(m->pindex,&object->rtree); TAILQ_REMOVE(&object->memq, m, listq); @@ -782,14 +785,19 @@ vm_page_t vm_page_lookup(vm_object_t object, vm_pindex_t pindex) { + vm_page_t m; - + /* VM_OBJECT_LOCK_ASSERT(object, MA_OWNED); if ((m = object->root) != NULL && m->pindex != pindex) { m = vm_page_splay(pindex, m); if ((object->root = m)->pindex != pindex) m = NULL; } + */ + m = radix_tree_lookup(pindex,&object->rtree); + //if(r != m && m != NULL && m->pindex == pindex) + // panic("VM_ALGO: vm_page_lookup r != m\n"); return (m); } @@ -1659,6 +1667,7 @@ * Remove the page from the object's collection of resident * pages. */ + /* if (m != object->root) vm_page_splay(m->pindex, object->root); if (m->left == NULL) @@ -1668,6 +1677,7 @@ root->right = m->right; } object->root = root; + */ TAILQ_REMOVE(&object->memq, m, listq); object->resident_page_count--; object->generation++; @@ -2134,6 +2144,33 @@ pmap_remove_write(m); } +/* + * vm_page_lookup_geidx: + * returns index which is grater than or equal to given index from the tree. + * + */ + +vm_page_t +vm_page_lookup_geidx(vm_pindex_t index, vm_object_t object) +{ + vm_pindex_t i = 0; + vm_page_t p; + + do{ + p = (vm_page_t) radix_tree_lookup(index - i, + &object->rtree); + i++; + }while (i <= index); + if(i > index) + return NULL; + if(p != NULL){ + if(i == 0) + return p; + return TAILQ_NEXT(p, listq); + } + return p; +} + #include "opt_ddb.h" #ifdef DDB #include <sys/kernel.h> ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.h#2 (text+ko) ==== @@ -325,6 +325,7 @@ void vm_page_deactivate (vm_page_t); void vm_page_insert (vm_page_t, vm_object_t, vm_pindex_t); vm_page_t vm_page_lookup (vm_object_t, vm_pindex_t); +vm_page_t vm_page_lookup_geidx (vm_pindex_t , vm_object_t); void vm_page_remove (vm_page_t); void vm_page_rename (vm_page_t, vm_object_t, vm_pindex_t); void vm_page_requeue(vm_page_t m); ==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_reserv.c#2 (text+ko) ==== @@ -312,14 +312,43 @@ * Look for an existing reservation. */ msucc = NULL; - mpred = object->root; - while (mpred != NULL) { + //mpred = object->root; + mpred = radix_tree_lookup_le(pindex, &object->rtree); + if(mpred != NULL){ + KASSERT(mpred->pindex != pindex, + ("vm_reserv_alloc_page: pindex already allocated")); + rv = vm_reserv_from_page(mpred); + if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) { + m = &rv->pages[VM_RESERV_INDEX(object, pindex)]; + //Handle vm_page_rename(m, new_object, ...). + if ((m->flags & (PG_CACHED | PG_FREE)) == 0) + return (NULL); + vm_reserv_populate(rv); + return (m); + } + } + msucc = radix_tree_lookup_ge(pindex, &object->rtree); + if(msucc != NULL){ + KASSERT(msucc->pindex != pindex, + ("vm_reserv_alloc_page: pindex already allocated")); + rv = vm_reserv_from_page(msucc); + if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) { + m = &rv->pages[VM_RESERV_INDEX(object, pindex)]; + //Handle vm_page_rename(m, new_object, ...). + if ((m->flags & (PG_CACHED | PG_FREE)) == 0) + return (NULL); + vm_reserv_populate(rv); + return (m); + } + } + /* + while (mpred != NULL) { KASSERT(mpred->pindex != pindex, ("vm_reserv_alloc_page: pindex already allocated")); rv = vm_reserv_from_page(mpred); if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) { m = &rv->pages[VM_RESERV_INDEX(object, pindex)]; - /* Handle vm_page_rename(m, new_object, ...). */ + Handle vm_page_rename(m, new_object, ...). if ((m->flags & (PG_CACHED | PG_FREE)) == 0) return (NULL); vm_reserv_populate(rv); @@ -334,7 +363,7 @@ if (rv->object == object && vm_reserv_has_pindex(rv, pindex)) { m = &rv->pages[VM_RESERV_INDEX(object, pindex)]; - /* Handle vm_page_rename(m, new_object, ...). */ + Handle vm_page_rename(m, new_object, ...). if ((m->flags & (PG_CACHED | PG_FREE)) == 0) return (NULL); vm_reserv_populate(rv); @@ -349,6 +378,7 @@ msucc = NULL; mpred = object->root = vm_page_splay(pindex, object->root); } + */ /* * Determine the first index to the left that can be used. ==== //depot/projects/soc2008/mayur_vmalgo/uspace/Makefile#2 (text+ko) ==== ==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.c#2 (text+ko) ==== @@ -329,6 +329,115 @@ return NULL; } +void * +radix_tree_lookup_ge(rtidx_t index, struct radix_tree *rtree) +{ + int level; + rtidx_t slot; + struct radix_node *tmp; + SLIST_HEAD(, radix_node) rtree_path = + SLIST_HEAD_INITIALIZER(rtree_path); + + level = rtree->rt_height - 1; + tmp = rtree->rt_root; + while (tmp){ + SLIST_INSERT_HEAD(&rtree_path, tmp,next); + slot = get_slot(index,rtree,level); + if (level == 0){ + if(NULL != tmp->rn_children[slot]){ + return tmp->rn_children[slot]; + } + } + tmp = (struct radix_node *)tmp->rn_children[slot]; + while (tmp == NULL){ + /* index not present, see if there is something + * greater than index + */ + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + while (1) + { + while(slot <= MASK(rtree->rt_bits_per_level) + && tmp->rn_children[slot] == NULL) + slot++; + if(slot > MASK(rtree->rt_bits_per_level)){ + if(level == rtree->rt_height - 1) + return NULL; + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + level++; + slot = get_slot(index,rtree,level) + 1; + continue; + } + if(level == 0){ + return tmp->rn_children[slot]; + } + SLIST_INSERT_HEAD(&rtree_path, tmp, next); + tmp = tmp->rn_children[slot]; + slot = 0; + level--; + } + } + level--; + } + return NULL; + +} + + +void * +radix_tree_lookup_le(rtidx_t index, struct radix_tree *rtree) +{ + int level; + rtidx_t slot; + struct radix_node *tmp; + SLIST_HEAD(, radix_node) rtree_path = + SLIST_HEAD_INITIALIZER(rtree_path); + + level = rtree->rt_height - 1; + tmp = rtree->rt_root; + while (tmp){ + SLIST_INSERT_HEAD(&rtree_path, tmp,next); + slot = get_slot(index,rtree,level); + if (level == 0){ + if(NULL != tmp->rn_children[slot]) + return tmp->rn_children[slot]; + } + tmp = (struct radix_node *)tmp->rn_children[slot]; + while (tmp == NULL){ + /* index not present, see if there is something + * less than index + */ + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + while (1) + { + while(slot >= 0 + && tmp->rn_children[slot] == NULL) + slot--; + if(slot > MASK(rtree->rt_bits_per_level)){ + if(level == rtree->rt_height - 1) + return NULL; + tmp = SLIST_FIRST(&rtree_path); + SLIST_REMOVE_HEAD(&rtree_path, next); + level++; + slot = get_slot(index,rtree,level) - 1; + continue; + } + if(level == 0) + return tmp->rn_children[slot]; + SLIST_INSERT_HEAD(&rtree_path, tmp, next); + tmp = tmp->rn_children[slot]; + slot = MASK(rtree->rt_bits_per_level); + level--; + } + } + level--; + } + return NULL; + + +} /* * radix_tree_shrink: if possible reduces the height of the tree. * If there are no keys stored the root is freed. ==== //depot/projects/soc2008/mayur_vmalgo/uspace/radix_tree.h#2 (text+ko) ==== @@ -2,12 +2,16 @@ /* * radix tree */ +#include <sys/queue.h> +#ifndef __RADIX_TREE_H__ +#define __RADIX_TREE_H__ typedef unsigned int rtidx_t; struct radix_node{ rtidx_t rn_children_count; + SLIST_ENTRY(radix_node) next; void *rn_children[]; /*pointers to child nodes*/ }; @@ -26,4 +30,4 @@ void *radix_tree_remove(rtidx_t index, struct radix_tree *rtree); void *radix_tree_lookup(rtidx_t index, struct radix_tree *rtree); void radix_tree_shrink(struct radix_tree *rtree); - +#endif ==== //depot/projects/soc2008/mayur_vmalgo/uspace/rtree_test.c#2 (text+ko) ====
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200808140437.m7E4bYjS099754>