PERFORCE change 157694 for review
Mayur Shardul
mayur at FreeBSD.org
Sat Feb 14 04:29:26 PST 2009
http://perforce.freebsd.org/chv.cgi?CH=157694
Change 157694 by mayur at mayur_freebsd_vm on 2009/02/14 12:28:48
Fixed some style related bugs.
Affected files ...
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.c#5 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#6 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_reserv.c#6 edit
Differences ...
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.c#5 (text+ko) ====
@@ -46,10 +46,11 @@
SLIST_HEAD_INITIALIZER(res_rnodes_head);
int rnode_size;
-rtidx_t max_index(struct radix_tree *rtree, int height);
-rtidx_t get_slot(rtidx_t index, struct radix_tree *rtree, int level);
-struct radix_node *get_radix_node(struct radix_tree *rtree);
-void put_radix_node(struct radix_node *rnode, struct radix_tree *rtree);
+static rtidx_t max_index(struct radix_tree *rtree, int height);
+static rtidx_t get_slot(rtidx_t index, struct radix_tree *rtree, int level);
+static struct radix_node *get_radix_node(struct radix_tree *rtree);
+static void put_radix_node(struct radix_node *rnode,
+ struct radix_tree *rtree);
extern vm_offset_t rt_resmem_start, rt_resmem_end;
@@ -76,14 +77,14 @@
{
struct radix_tree *rtree;
- if ((RTIDX_LEN % bits_per_level) != 0){
+ if ((RTIDX_LEN % bits_per_level) != 0) {
printf("create_radix_tree: bits_per_level must be a divisor of RTIDX_LEN = %d",RTIDX_LEN);
return NULL;
}
rtree = (struct radix_tree *)malloc(sizeof(struct radix_tree),
M_TEMP,M_NOWAIT | M_ZERO);
- if (rtree == NULL){
+ if (rtree == NULL) {
printf("create_radix_tree: Insufficient memory\n");
return NULL;
}
@@ -109,7 +110,7 @@
struct radix_node *rnode;
int children_cnt;
- if(!SLIST_EMPTY(&res_rnodes_head)){
+ if (!SLIST_EMPTY(&res_rnodes_head)) {
rnode = SLIST_FIRST(&res_rnodes_head);
SLIST_REMOVE_HEAD(&res_rnodes_head, next);
bzero((void *)rnode, rnode_size);
@@ -120,7 +121,7 @@
children_cnt = MASK(rtree->rt_bits_per_level) + 1;
rnode = (struct radix_node *)malloc(sizeof(struct radix_node) +
sizeof(void *)*children_cnt,M_TEMP,M_NOWAIT | M_ZERO);
- if (rnode == NULL){
+ if (rnode == NULL) {
panic("get_radix_node: Can not allocate memory\n");
return NULL;
}
@@ -151,13 +152,14 @@
rtidx_t
max_index(struct radix_tree *rtree, int height)
{
- if (height > rtree->rt_max_height ){
+ if (height > rtree->rt_max_height ) {
printf("max_index: The tree does not have %d levels\n",
height);
height = rtree->rt_max_height;
}
- if(height == 0)
+ if (height == 0) {
return 0;
+ }
return (MASK(rtree->rt_bits_per_level*height));
}
@@ -176,9 +178,10 @@
slot = index & (MASK(rtree->rt_bits_per_level) <<
offset);
slot >>= offset;
- if(slot < 0 || slot > 0x10)
+ if (slot < 0 || slot > 0x10) {
panic("VM_ALGO: Wrong slot generated index - %lu level - %d",
(u_long)index,level);
+ }
return slot;
}
/*
@@ -198,31 +201,32 @@
rtidx_t slot;
struct radix_node *rnode = NULL, *tmp;
- if (rtree->rt_max_index < index){
+ if (rtree->rt_max_index < index) {
printf("radix_tree_insert: Index %lu too large for the tree\n"
,(u_long)index);
return 1; /*TODO Replace 1 by error code*/
}
/* make sure that the tree is tall enough to accomidate the index*/
- if (rtree->rt_root == NULL){
+ if (rtree->rt_root == NULL) {
/* just add a node at required height*/
while (index > max_index(rtree, rtree->rt_height))
rtree->rt_height++;
/* this happens when index == 0*/
- if(rtree->rt_height == 0)
+ if (rtree->rt_height == 0) {
rtree->rt_height = 1;
+ }
rnode = get_radix_node(rtree);
if (rnode == NULL){
return (ENOMEM);
}
rnode->rn_children_count = 0;
rtree->rt_root = rnode;
- }else{
- while (index > max_index(rtree, rtree->rt_height)){
+ } else {
+ while (index > max_index(rtree, rtree->rt_height)) {
/*increase the height by one*/
rnode = get_radix_node(rtree);
- if (rnode == NULL){
+ if (rnode == NULL) {
return (ENOMEM);
}
rnode->rn_children_count = 1;
@@ -236,17 +240,17 @@
level = rtree->rt_height - 1;
tmp = rtree->rt_root;
- while (level > 0){
+ while (level > 0) {
/*
* shift by the number of bits passed so far to
* create the mask
*/
slot = get_slot(index,rtree,level);
/* add the required intermidiate nodes */
- if (tmp->rn_children[slot] == NULL){
+ if (tmp->rn_children[slot] == NULL) {
tmp->rn_children_count++;
rnode = get_radix_node(rtree);
- if (rnode == NULL){
+ if (rnode == NULL) {
return (ENOMEM);
}
rnode->rn_children_count = 0;
@@ -257,10 +261,12 @@
}
slot = get_slot(index,rtree,level);
- if (tmp->rn_children[slot] != NULL)
- printf("radix_tree_insert: value already present in the tree\n");
- else
+ if (tmp->rn_children[slot] != NULL) {
+ printf("radix_tree_insert: value already present in"
+ " the tree\n");
+ } else {
tmp->rn_children_count++;
+ }
/*we will overwrite the old value with the new value*/
tmp->rn_children[slot] = val;
return 0;
@@ -281,15 +287,16 @@
rtidx_t slot;
struct radix_node *tmp;
- if(index > MASK(rtree->rt_height * rtree->rt_bits_per_level)){
+ if (index > MASK(rtree->rt_height * rtree->rt_bits_per_level)) {
return NULL;
}
level = rtree->rt_height - 1;
tmp = rtree->rt_root;
- while (tmp){
+ while (tmp) {
slot = get_slot(index,rtree,level);
- if (level == 0)
+ if (level == 0) {
return tmp->rn_children[slot];
+ }
tmp = (struct radix_node *)tmp->rn_children[slot];
level--;
}
@@ -309,40 +316,43 @@
SLIST_HEAD(, radix_node) rtree_path =
SLIST_HEAD_INITIALIZER(rtree_path);
- if(index > MASK(rtree->rt_height * rtree->rt_bits_per_level))
+ if (index > MASK(rtree->rt_height * rtree->rt_bits_per_level)) {
return NULL;
+ }
level = rtree->rt_height - 1;
tmp = rtree->rt_root;
- while (tmp){
+ while (tmp) {
SLIST_INSERT_HEAD(&rtree_path, tmp,next);
slot = get_slot(index,rtree,level);
- if (level == 0){
- if(NULL != tmp->rn_children[slot])
+ 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){
+ 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 (1) {
while (slot <= MASK(rtree->rt_bits_per_level)
- && tmp->rn_children[slot] == NULL)
+ && tmp->rn_children[slot] == NULL) {
slot++;
- if(slot > MASK(rtree->rt_bits_per_level)){
- if(level == rtree->rt_height - 1)
+ }
+ 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){
+ if (level == 0) {
return tmp->rn_children[slot];
}
SLIST_INSERT_HEAD(&rtree_path, tmp, next);
@@ -369,43 +379,47 @@
SLIST_HEAD(, radix_node) rtree_path =
SLIST_HEAD_INITIALIZER(rtree_path);
- if(index > MASK(rtree->rt_height * rtree->rt_bits_per_level))
+ 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){
+ while (tmp) {
SLIST_INSERT_HEAD(&rtree_path, tmp,next);
slot = get_slot(index,rtree,level);
- if (level == 0){
- if( NULL != tmp->rn_children[slot])
+ 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){
+ 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 (1) {
while (slot > 0
- && tmp->rn_children[slot] == NULL)
+ && tmp->rn_children[slot] == NULL) {
slot--;
- if(tmp->rn_children[slot] == NULL){
+ }
+ if (tmp->rn_children[slot] == NULL) {
slot--;
}
- if(slot > MASK(rtree->rt_bits_per_level)){
- if(level == rtree->rt_height - 1)
+ 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)
+ 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);
@@ -436,42 +450,45 @@
level = rtree->rt_height - 1;
tmp = rtree->rt_root;
- while(tmp){
+ while (tmp) {
slot = get_slot(index,rtree,level);
/* The delete operation might create a branch without any
* nodes we will save the root of such branch, if there is
* any, and its level.
*/
- if (branch == NULL ){
+ if (branch == NULL ) {
/* if there is an intermidiate node with one
* child we save details of its parent node
*/
- if (level != 0){
+ if (level != 0) {
sub_branch = (struct radix_node *)
tmp->rn_children[slot];
branch_level = level;
if (sub_branch != NULL &&
- sub_branch->rn_children_count == 1)
+ sub_branch->rn_children_count == 1) {
branch = tmp;
+ }
}
- }else{
+ } else {
/* If there is some decendent with more than one
* child then reset the branch to NULL
*/
- if (level != 0){
+ if (level != 0) {
sub_branch = (struct radix_node *)
tmp->rn_children[slot];
if (sub_branch != NULL &&
- sub_branch->rn_children_count > 1)
+ sub_branch->rn_children_count > 1) {
branch = NULL;
+ }
}
}
- if (level == 0){
+ if (level == 0) {
val = tmp->rn_children[slot];
- if (tmp->rn_children[slot] == NULL){
- printf("radix_tree_remove: index %lu not present in the tree.\n",
+ if (tmp->rn_children[slot] == NULL) {
+ printf("radix_tree_remove: index %lu "
+ "not present in the tree.\n",
(u_long)index);
return NULL;
}
@@ -479,7 +496,7 @@
tmp->rn_children_count--;
/* cut the branch before we return*/
- if (branch != NULL){
+ if (branch != NULL) {
slot = get_slot(index,rtree,
branch_level);
tmp = branch->rn_children[slot];
@@ -487,9 +504,9 @@
branch->rn_children_count--;
branch = tmp;
branch_level--;
- while (branch != NULL){
+ while (branch != NULL) {
slot = get_slot(index,rtree,
- branch_level);
+ branch_level);
tmp = branch->rn_children[slot];
put_radix_node(branch,rtree);
branch = tmp;
@@ -514,18 +531,19 @@
radix_tree_shrink(struct radix_tree *rtree){
struct radix_node *tmp;
- if(rtree->rt_root == NULL)
+ if (rtree->rt_root == NULL) {
return;
+ }
/*Adjust the height of the tree*/
while (rtree->rt_root->rn_children_count == 1 &&
- rtree->rt_root->rn_children[0] != NULL){
+ rtree->rt_root->rn_children[0] != NULL) {
tmp = rtree->rt_root;
rtree->rt_root = tmp->rn_children[0];
rtree->rt_height--;
put_radix_node(tmp,rtree);
}
/* finally see if we have an empty tree*/
- if (rtree->rt_root->rn_children_count == 0){
+ if (rtree->rt_root->rn_children_count == 0) {
put_radix_node(rtree->rt_root,rtree);
rtree->rt_root = NULL;
}
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#6 (text+ko) ====
@@ -285,8 +285,7 @@
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++)
- {
+ for (i = 0; i < RESERVED_NODE_COUNT; i++) {
SLIST_INSERT_HEAD(&res_rnodes_head, (struct radix_node *)mapped,
next);
mapped += rnode_size;
@@ -676,16 +675,15 @@
m->pindex = pindex;
#ifdef VM_RADIX
- if(object->resident_page_count == 0){
+ if (object->resident_page_count == 0) {
TAILQ_INSERT_TAIL(&object->memq, m, listq);
- }
- else{
- if((neighbour = radix_tree_lookup_ge(pindex,
- &object->rtree)) != NULL){
+ } else {
+ if ((neighbour = radix_tree_lookup_ge(pindex,
+ &object->rtree)) != NULL) {
KASSERT( pindex != neighbour->pindex, ("vm_page_insert"
": offset already allocated"));
TAILQ_INSERT_BEFORE(neighbour, m, listq);
- }else{
+ } else {
neighbour = radix_tree_lookup_le(pindex,
&object->rtree);
TAILQ_INSERT_AFTER(&object->memq, neighbour, m, listq);
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_reserv.c#6 (text+ko) ====
@@ -313,29 +313,31 @@
*/
#ifdef VM_RADIX
mpred = radix_tree_lookup_le(pindex, &object->rtree);
- if(mpred != NULL){
+ 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)
+ 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){
+ 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)
+ if ((m->flags & (PG_CACHED | PG_FREE)) == 0) {
return (NULL);
+ }
vm_reserv_populate(rv);
return (m);
}
More information about the p4-projects
mailing list