Date: Thu, 1 Jan 2009 14:08:16 GMT From: Mayur Shardul <mayur@FreeBSD.org> To: Perforce Change Reviews <perforce@FreeBSD.org> Subject: PERFORCE change 155554 for review Message-ID: <200901011408.n01E8GYU036190@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=155554 Change 155554 by mayur@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@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@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. */
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200901011408.n01E8GYU036190>