PERFORCE change 147361 for review
Mayur Shardul
mayur at FreeBSD.org
Thu Aug 14 04:37:35 UTC 2008
http://perforce.freebsd.org/chv.cgi?CH=147361
Change 147361 by mayur at 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) ====
More information about the p4-projects
mailing list