PERFORCE change 155554 for review
Mayur Shardul
mayur at FreeBSD.org
Thu Jan 1 14:08:18 UTC 2009
http://perforce.freebsd.org/chv.cgi?CH=155554
Change 155554 by mayur at mayur_freebsd_vm on 2009/01/01 14:07:27
some cleanup
Affected files ...
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/conf/options#2 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.c#4 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.h#4 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_map.c#4 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_map.h#3 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.c#5 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.h#5 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#5 edit
.. //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_reserv.c#5 edit
Differences ...
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/conf/options#2 (text+ko) ====
@@ -46,6 +46,7 @@
TWA_DEBUG opt_twa.h
TWA_FLASH_FIRMWARE opt_twa.h
+
# Debugging options.
DDB
DDB_CAPTURE_DEFAULTBUFSIZE opt_ddb.h
@@ -560,6 +561,7 @@
VM_KMEM_SIZE_MAX opt_vm.h
VM_NRESERVLEVEL opt_vm.h
VM_LEVEL_0_ORDER opt_vm.h
+VM_RADIX opt_vm.h
NO_SWAPPING opt_vm.h
MALLOC_MAKE_FAILURES opt_vm.h
MALLOC_PROFILE opt_vm.h
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.c#4 (text+ko) ====
@@ -1,4 +1,32 @@
/*
+ * Copyright (c) 2008 Mayur Shardul <mayur.shardul at gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ */
+
+
+/*
* Radix tree implementation.
* Number of bits per level are configurable.
*
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/radix_tree.h#4 (text+ko) ====
@@ -1,6 +1,28 @@
-
/*
- * radix tree
+ * Copyright (c) 2008 Mayur Shardul <mayur.shardul at gmail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
*/
#include <sys/queue.h>
@@ -27,7 +49,7 @@
};
-struct radix_tree *create_radix_tree(int );
+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 *);
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_map.c#4 (text+ko) ====
@@ -1501,19 +1501,18 @@
start = 0;
p_start = NULL;
- /*
+#ifdef VM_RADIX
+ p = radix_tree_lookup_ge(pindex, &object->rtree);
+#else
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);
-
- r = radix_tree_lookup_ge(pindex, &object->rtree);
- KASSERT(r == p, ("r != p, lookup_ge failed\n"));
}
- }*/
- p = radix_tree_lookup_ge(pindex, &object->rtree);
+ }
+#endif
/*
* Assert: the variable p is either (1) the page with the
* least pindex greater than or equal to the parameter pindex
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_map.h#3 (text+ko) ====
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.c#5 (text+ko) ====
@@ -216,13 +216,15 @@
TAILQ_INIT(&object->memq);
LIST_INIT(&object->shadow_head);
- //object->root = NULL;
+#ifdef VM_RADIX
object->rtree.rt_bits_per_level = 4;
object->rtree.rt_height = 0;
object->rtree.rt_root = NULL;
object->rtree.rt_max_height = (8*sizeof(rtidx_t))/4;
object->rtree.rt_max_index = ~((rtidx_t)0);
-
+#else
+ object->root = NULL;
+#endif
object->type = type;
object->size = size;
object->generation = 1;
@@ -1362,17 +1364,14 @@
retry:
if ((m = TAILQ_FIRST(&orig_object->memq)) != NULL) {
if (m->pindex < offidxstart) {
- /*
+#ifdef VM_RADIX
+ m = radix_tree_lookup_ge(offidxstart,
+ &orig_object->rtree);
+#else
m = vm_page_splay(offidxstart, orig_object->root);
if ((orig_object->root = m)->pindex < offidxstart)
m = TAILQ_NEXT(m, listq);
- */
- m = radix_tree_lookup_ge(offidxstart,
- &orig_object->rtree);
- /*
- KASSERT( r == m, ("VM_ALGO: vm_object_split "
- "lookup_ge failed"));
- */
+#endif
}
}
vm_page_lock_queues();
@@ -1892,16 +1891,13 @@
vm_page_lock_queues();
if ((p = TAILQ_FIRST(&object->memq)) != NULL) {
if (p->pindex < start) {
- /*
+#ifdef VM_RADIX
+ p = radix_tree_lookup_ge(start, &object->rtree);
+#else
p = vm_page_splay(start, object->root);
if ((object->root = p)->pindex < start)
p = TAILQ_NEXT(p, listq);
- */
- p = radix_tree_lookup_ge(start, &object->rtree);
- /*
- KASSERT(r == p, ("VM_ALGO: vm_object_page_remove "
- "lookup_ge failed\n"));
- */
+#endif
}
}
/*
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_object.h#5 (text+ko) ====
@@ -67,7 +67,11 @@
#ifndef _VM_OBJECT_
#define _VM_OBJECT_
+#include "opt_vm.h"
+
+#ifdef VM_RADIX
#include "radix_tree.h"
+#endif
#include <sys/queue.h>
#include <sys/_lock.h>
@@ -89,8 +93,11 @@
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 */
+#ifdef VM_RADIX
struct radix_tree rtree;
+#else
+ vm_page_t root; /* root of the resident page splay tree */
+#endif
vm_pindex_t size; /* Object size */
int generation; /* generation ID */
int ref_count; /* How many refs?? */
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_page.c#5 (text+ko) ====
@@ -137,8 +137,10 @@
struct mtx vm_page_queue_mtx;
struct mtx vm_page_queue_free_mtx;
+#ifdef VM_RADIX
extern SLIST_HEAD(, radix_node) res_rnodes_head;
extern int rnode_size;
+#endif
vm_page_t vm_page_array = 0;
int vm_page_array_size = 0;
@@ -271,7 +273,7 @@
vm_page_queues[PQ_INACTIVE].cnt = &cnt.v_inactive_count;
vm_page_queues[PQ_ACTIVE].cnt = &cnt.v_active_count;
vm_page_queues[PQ_HOLD].cnt = &cnt.v_active_count;
-
+#ifdef VM_RADIX
/* reserve memory for radix nodes. */
rnode_size = sizeof(struct radix_node) +
(sizeof(void *) * (0xf + 1));
@@ -289,6 +291,7 @@
next);
mapped += rnode_size;
}
+#endif
/*
* Allocate memory for use when boot strapping the kernel memory
* allocator.
@@ -657,8 +660,11 @@
void
vm_page_insert(vm_page_t m, vm_object_t object, vm_pindex_t pindex)
{
+#ifdef VM_RADIX
vm_page_t neighbour;
-
+#else
+ vm_page_t root;
+#endif
VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
if (m->object != NULL)
panic("vm_page_insert: page already inserted");
@@ -669,10 +675,27 @@
m->object = object;
m->pindex = pindex;
+#ifdef VM_RADIX
+ if(object->resident_page_count == 0){
+ TAILQ_INSERT_TAIL(&object->memq, m, listq);
+ }
+ 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{
+ neighbour = radix_tree_lookup_le(pindex,
+ &object->rtree);
+ TAILQ_INSERT_AFTER(&object->memq, neighbour, m, listq);
+ }
+ }
+ radix_tree_insert(pindex, &object->rtree, m);
+#else
/*
* Now link into the object's ordered list of backed pages.
*/
- /*
root = object->root;
if (root == NULL) {
m->left = NULL;
@@ -695,26 +718,9 @@
}
}
object->root = m;
- */
- if(object->resident_page_count == 0){
- TAILQ_INSERT_TAIL(&object->memq, m, listq);
- }
- 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{
- neighbour = radix_tree_lookup_le(pindex,
- &object->rtree);
- TAILQ_INSERT_AFTER(&object->memq, neighbour, m, listq);
- }
- }
-
+#endif
object->generation++;
- radix_tree_insert(pindex, &object->rtree, m);
-
+
/*
* show that the object has one more resident page.
*/
@@ -749,7 +755,9 @@
vm_page_remove(vm_page_t m)
{
vm_object_t object;
- //vm_page_t root;
+#ifndef VM_RADIX
+ vm_page_t root;
+#endif
if ((object = m->object) == NULL)
return;
@@ -760,10 +768,12 @@
}
mtx_assert(&vm_page_queue_mtx, MA_OWNED);
+#ifdef VM_RADIX
+ radix_tree_remove(m->pindex,&object->rtree);
+#else
/*
* 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)
@@ -773,7 +783,8 @@
root->right = m->right;
}
object->root = root;
- */
+#endif
+
TAILQ_REMOVE(&object->memq, m, listq);
/*
@@ -781,7 +792,6 @@
*/
object->resident_page_count--;
object->generation++;
- radix_tree_remove(m->pindex,&object->rtree);
/*
* The vnode may now be recycled.
*/
@@ -807,15 +817,16 @@
vm_page_t m;
VM_OBJECT_LOCK_ASSERT(object, MA_OWNED);
- /*
+
+#ifdef VM_RADIX
+ m = radix_tree_lookup(pindex, &object->rtree);
+#else
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);
- //KASSERT( r == m, ("VM_ALGO: r != m, lookup failed."));
+#endif
return (m);
}
@@ -1681,11 +1692,13 @@
*/
vm_pageq_remove(m);
+#ifdef VM_RADIX
+ radix_tree_remove(m->pindex, &object->rtree);
+#else
/*
* 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)
@@ -1695,8 +1708,7 @@
root->right = m->right;
}
object->root = root;
- */
- radix_tree_remove(m->pindex, &object->rtree);
+#endif
TAILQ_REMOVE(&object->memq, m, listq);
object->resident_page_count--;
object->generation++;
==== //depot/projects/soc2008/mayur_vmalgo/kern/src/sys/vm/vm_reserv.c#5 (text+ko) ====
@@ -311,16 +311,47 @@
/*
* Look for an existing reservation.
*/
- //msucc = NULL;
- //mpred = object->root;
- /*
+#ifdef VM_RADIX
+ 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);
+ }
+ }
+
+#else
+ msucc = NULL;
+ mpred = object->root;
+
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);
@@ -335,7 +366,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);
@@ -350,38 +381,7 @@
msucc = NULL;
mpred = object->root = vm_page_splay(pindex, 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);
- }
- }
- //KASSERT(rpred == mpred, ("rpred != mpred\n"));
- //KASSERT(msucc == rsucc, ("msucc != rsucc\n"));
+#endif
/*
* Determine the first index to the left that can be used.
*/
More information about the p4-projects
mailing list