From owner-svn-src-user@FreeBSD.ORG Sat Oct 22 23:34:37 2011 Return-Path: Delivered-To: svn-src-user@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 7D2BD106566C; Sat, 22 Oct 2011 23:34:37 +0000 (UTC) (envelope-from attilio@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 6C0A68FC0A; Sat, 22 Oct 2011 23:34:37 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id p9MNYbJj000752; Sat, 22 Oct 2011 23:34:37 GMT (envelope-from attilio@svn.freebsd.org) Received: (from attilio@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p9MNYbdF000742; Sat, 22 Oct 2011 23:34:37 GMT (envelope-from attilio@svn.freebsd.org) Message-Id: <201110222334.p9MNYbdF000742@svn.freebsd.org> From: Attilio Rao Date: Sat, 22 Oct 2011 23:34:37 +0000 (UTC) To: src-committers@freebsd.org, svn-src-user@freebsd.org X-SVN-Group: user MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r226645 - in user/attilio/vmcontention/sys: conf vm X-BeenThere: svn-src-user@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the experimental " user" src tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 22 Oct 2011 23:34:37 -0000 Author: attilio Date: Sat Oct 22 23:34:37 2011 New Revision: 226645 URL: http://svn.freebsd.org/changeset/base/226645 Log: Check in an intial implementation of radix tree implementation to replace the vm object pages splay. TODO: - Handle differently the negative keys for having smaller depth index nodes (negative keys caming from indirect blocks) - Fix the get_node() by having support for a low reserved objects directly from UMA - Implement the lookup_le and re-enable VM_NRESERVELEVEL = 1 - Try to rework the superpage splay of idle pages and the cache splay for every vm object in order to regain space on vm_page structure - Verify performance and improve them (likely by having consumers to deal with several ranges of pages manually?) Obtained from: jeff, Mayur Shardul (GSoC 2009) Added: user/attilio/vmcontention/sys/vm/vm_radix.c (contents, props changed) user/attilio/vmcontention/sys/vm/vm_radix.h (contents, props changed) Modified: user/attilio/vmcontention/sys/conf/files user/attilio/vmcontention/sys/conf/options user/attilio/vmcontention/sys/vm/vm_object.c user/attilio/vmcontention/sys/vm/vm_object.h user/attilio/vmcontention/sys/vm/vm_page.c user/attilio/vmcontention/sys/vm/vm_reserv.c user/attilio/vmcontention/sys/vm/vm_reserv.h Modified: user/attilio/vmcontention/sys/conf/files ============================================================================== --- user/attilio/vmcontention/sys/conf/files Sat Oct 22 22:56:20 2011 (r226644) +++ user/attilio/vmcontention/sys/conf/files Sat Oct 22 23:34:37 2011 (r226645) @@ -3330,6 +3330,7 @@ vm/vm_page.c standard vm/vm_pageout.c standard vm/vm_pager.c standard vm/vm_phys.c standard +vm/vm_radix.c standard vm/vm_reserv.c standard vm/vm_unix.c standard vm/vm_zeroidle.c standard Modified: user/attilio/vmcontention/sys/conf/options ============================================================================== --- user/attilio/vmcontention/sys/conf/options Sat Oct 22 22:56:20 2011 (r226644) +++ user/attilio/vmcontention/sys/conf/options Sat Oct 22 23:34:37 2011 (r226645) @@ -591,6 +591,7 @@ VM_KMEM_SIZE_SCALE opt_vm.h 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 Modified: user/attilio/vmcontention/sys/vm/vm_object.c ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_object.c Sat Oct 22 22:56:20 2011 (r226644) +++ user/attilio/vmcontention/sys/vm/vm_object.c Sat Oct 22 23:34:37 2011 (r226645) @@ -208,7 +208,12 @@ _vm_object_allocate(objtype_t type, vm_p TAILQ_INIT(&object->memq); LIST_INIT(&object->shadow_head); +#ifdef VM_RADIX + object->rtree.rt_height = 0; + object->rtree.rt_root = NULL; +#else object->root = NULL; +#endif object->type = type; object->size = size; object->generation = 1; Modified: user/attilio/vmcontention/sys/vm/vm_object.h ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_object.h Sat Oct 22 22:56:20 2011 (r226644) +++ user/attilio/vmcontention/sys/vm/vm_object.h Sat Oct 22 23:34:37 2011 (r226645) @@ -71,6 +71,8 @@ #include #include +#include + /* * Types defined: * @@ -87,6 +89,7 @@ struct vm_object { 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 */ + struct vm_radix rtree; /* root of the resident page radix index tree */ vm_page_t root; /* root of the resident page splay tree */ vm_pindex_t size; /* Object size */ int generation; /* generation ID */ Modified: user/attilio/vmcontention/sys/vm/vm_page.c ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_page.c Sat Oct 22 22:56:20 2011 (r226644) +++ user/attilio/vmcontention/sys/vm/vm_page.c Sat Oct 22 23:34:37 2011 (r226645) @@ -103,6 +103,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include #include @@ -121,6 +122,13 @@ struct vpglocks vm_page_queue_free_lock; struct vpglocks pa_lock[PA_LOCK_COUNT]; +#ifdef VM_RADIX +extern SLIST_HEAD(, vm_radix_node) res_rnodes_head; +extern struct mtx rnode_lock; +extern vm_offset_t rnode_start; +extern vm_offset_t rnode_end; +#endif + vm_page_t vm_page_array = 0; int vm_page_array_size = 0; long first_page = 0; @@ -252,6 +260,10 @@ vm_page_startup(vm_offset_t vaddr) vm_paddr_t pa; vm_paddr_t last_pa; char *list; +#ifdef VM_RADIX + unsigned int rtree_res_count; + vm_pindex_t size; +#endif /* the biggest memory array is the second group of pages */ vm_paddr_t end; @@ -311,7 +323,34 @@ vm_page_startup(vm_offset_t vaddr) 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 + mtx_init(&rnode_lock, "radix node", NULL, MTX_SPIN); + /* + * Reserve memory for radix nodes. Allocate enough nodes so that + * insert on kernel_object will not result in recurrsion. + */ + size = OFF_TO_IDX(VM_MAX_KERNEL_ADDRESS - VM_MIN_KERNEL_ADDRESS) * 2; + rtree_res_count = 0; + while (size != 0) { + rtree_res_count += size / VM_RADIX_COUNT; + size /= VM_RADIX_COUNT; + } + printf("Allocated %d tree pages for %lu bytes of memory.\n", + rtree_res_count, VM_MAX_KERNEL_ADDRESS - VM_MIN_KERNEL_ADDRESS); + new_end = end - (rtree_res_count * sizeof(struct vm_radix_node)); + new_end = trunc_page(new_end); + mapped = pmap_map(&vaddr, new_end, end, + VM_PROT_READ | VM_PROT_WRITE); + bzero((void *)mapped, end - new_end); + end = new_end; + rnode_start = mapped; + for (i = 0; i < rtree_res_count; i++) { + SLIST_INSERT_HEAD(&res_rnodes_head, + (struct vm_radix_node *)mapped, next); + mapped += sizeof(struct vm_radix_node); + } + rnode_end = mapped; +#endif /* * Allocate memory for use when boot strapping the kernel memory * allocator. @@ -836,8 +875,11 @@ vm_page_splay(vm_pindex_t pindex, vm_pag void vm_page_insert(vm_page_t m, vm_object_t object, vm_pindex_t pindex) { +#ifdef VM_RADIX + vm_page_t neighbor; +#else vm_page_t root; - +#endif VM_OBJECT_LOCK_ASSERT(object, MA_OWNED); if (m->object != NULL) panic("vm_page_insert: page already inserted"); @@ -848,6 +890,20 @@ vm_page_insert(vm_page_t m, vm_object_t m->object = object; m->pindex = pindex; +#ifdef VM_RADIX + if (object->resident_page_count == 0) { + TAILQ_INSERT_TAIL(&object->memq, m, listq); + } else { + neighbor = vm_radix_lookup_ge(&object->rtree, pindex); + if (neighbor != NULL) { + KASSERT(pindex != neighbor->pindex, + ("vm_page_insert: offset already allocated")); + TAILQ_INSERT_BEFORE(neighbor, m, listq); + } else + TAILQ_INSERT_TAIL(&object->memq, m, listq); + } + vm_radix_insert(&object->rtree, pindex, m); +#else /* * Now link into the object's ordered list of backed pages. */ @@ -873,6 +929,7 @@ vm_page_insert(vm_page_t m, vm_object_t } } object->root = m; +#endif /* * show that the object has one more resident page. @@ -908,7 +965,9 @@ void vm_page_remove(vm_page_t m) { vm_object_t object; +#ifndef VM_RADIX vm_page_t root; +#endif if ((m->oflags & VPO_UNMANAGED) == 0) vm_page_lock_assert(m, MA_OWNED); @@ -920,6 +979,9 @@ vm_page_remove(vm_page_t m) vm_page_flash(m); } +#ifdef VM_RADIX + vm_radix_remove(&object->rtree, m->pindex); +#else /* * Now remove from the object's list of backed pages. */ @@ -932,6 +994,8 @@ vm_page_remove(vm_page_t m) root->right = m->right; } object->root = root; +#endif + TAILQ_REMOVE(&object->memq, m, listq); /* @@ -963,11 +1027,16 @@ vm_page_lookup(vm_object_t object, vm_pi vm_page_t m; VM_OBJECT_LOCK_ASSERT(object, MA_OWNED); + +#ifdef VM_RADIX + m = vm_radix_lookup(&object->rtree, pindex); +#else if ((m = object->root) != NULL && m->pindex != pindex) { m = vm_page_splay(pindex, m); if ((object->root = m)->pindex != pindex) m = NULL; } +#endif return (m); } @@ -986,6 +1055,10 @@ vm_page_find_least(vm_object_t object, v vm_page_t m; VM_OBJECT_LOCK_ASSERT(object, MA_OWNED); +#ifdef VM_RADIX + if ((m = TAILQ_FIRST(&object->memq)) != NULL) + m = vm_radix_lookup_ge(&object->rtree, pindex); +#else if ((m = TAILQ_FIRST(&object->memq)) != NULL) { if (m->pindex < pindex) { m = vm_page_splay(pindex, object->root); @@ -993,6 +1066,7 @@ vm_page_find_least(vm_object_t object, v m = TAILQ_NEXT(m, listq); } } +#endif return (m); } @@ -2052,6 +2126,9 @@ vm_page_cache(vm_page_t m) */ vm_pageq_remove(m); +#ifdef VM_RADIX + vm_radix_remove(&object->rtree, m->pindex); +#else /* * Remove the page from the object's collection of resident * pages. @@ -2065,6 +2142,7 @@ vm_page_cache(vm_page_t m) root->right = m->right; } object->root = root; +#endif TAILQ_REMOVE(&object->memq, m, listq); object->resident_page_count--; Added: user/attilio/vmcontention/sys/vm/vm_radix.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/attilio/vmcontention/sys/vm/vm_radix.c Sat Oct 22 23:34:37 2011 (r226645) @@ -0,0 +1,435 @@ +/* + * Copyright (c) 2008 Mayur Shardul + * Copyright (c) 2011 Jeffrey Roberson + * 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. + */ + +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + + +SLIST_HEAD(, vm_radix_node) res_rnodes_head = + SLIST_HEAD_INITIALIZER(res_rnodes_head); + +struct mtx rnode_lock; +vm_offset_t rnode_start; +vm_offset_t rnode_end; + +/* + * Allocate a radix node. Initializes all elements to 0. + */ +static struct vm_radix_node * +vm_radix_node_get(void) +{ + struct vm_radix_node *rnode; + + if (VM_OBJECT_LOCKED(kernel_object) || VM_OBJECT_LOCKED(kmem_object)){ + mtx_lock_spin(&rnode_lock); + if (!SLIST_EMPTY(&res_rnodes_head)) { + rnode = SLIST_FIRST(&res_rnodes_head); + SLIST_REMOVE_HEAD(&res_rnodes_head, next); + mtx_unlock_spin(&rnode_lock); + bzero((void *)rnode, sizeof(*rnode)); + goto out; + } + mtx_unlock_spin(&rnode_lock); + panic("No memory for kernel_object. . ."); + } + rnode = malloc(sizeof(struct vm_radix_node), M_TEMP, M_NOWAIT | M_ZERO); + if (rnode == NULL) { + panic("vm_radix_node_get: Can not allocate memory\n"); + return NULL; + } +out: + + return rnode; +} + +/* + * Free radix node. + */ +static void +vm_radix_node_put(struct vm_radix_node *rnode) +{ + + KASSERT(rnode->rn_count == 0, + ("vm_radix_node_put: Freeing a node with %d children\n", + rnode->rn_count)); + if ((vm_offset_t)rnode >= rnode_start && + (vm_offset_t)rnode < rnode_end) { + mtx_lock_spin(&rnode_lock); + SLIST_INSERT_HEAD(&res_rnodes_head, rnode, next); + mtx_unlock_spin(&rnode_lock); + } else + free(rnode,M_TEMP); +} + +/* + * Return the position in the array for a given level. + */ +static inline int +vm_radix_slot(vm_pindex_t index, int level) +{ + + return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK); +} + +/* + * Inserts the key-value pair in to the radix tree. Returns errno. + * Panics if the key already exists. + */ +int +vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val) +{ + struct vm_radix_node *rnode; + int slot; + int level; + + CTR3(KTR_VM, + "insert: tree %p, index %p, val %p", rtree, (void *)index, val); + if (index == -1) + panic("vm_radix_insert: -1 is not a valid index.\n"); + /* + * Increase the height by adding nodes at the root until + * there is sufficient space. + */ + while (rtree->rt_height == 0 || + index > VM_RADIX_MAX(rtree->rt_height)) { + CTR3(KTR_VM, "insert: expanding %jd > %jd height %d", + index, VM_RADIX_MAX(rtree->rt_height), rtree->rt_height); + /* + * Only allocate tree nodes if they are needed. + */ + if (rtree->rt_root == NULL || rtree->rt_root->rn_count != 0) { + rnode = vm_radix_node_get(); + if (rnode == NULL) + return (ENOMEM); + if (rtree->rt_root) { + rnode->rn_child[0] = rtree->rt_root; + rnode->rn_count = 1; + } + rtree->rt_root = rnode; + } + rtree->rt_height++; + KASSERT(rtree->rt_height <= VM_RADIX_LIMIT, + ("vm_radix_insert: Tree %p height %d too tall", rtree, + rtree->rt_height)); + } + + /* Now that the tree is tall enough, fill in the path to the index. */ + rnode = rtree->rt_root; + for (level = rtree->rt_height - 1; level > 0; level--) { + slot = vm_radix_slot(index, level); + /* Add the required intermidiate nodes. */ + if (rnode->rn_child[slot] == NULL) { + rnode->rn_child[slot] = vm_radix_node_get(); + if (rnode->rn_child[slot] == NULL) + return (ENOMEM); + rnode->rn_count++; + } + CTR5(KTR_VM, + "insert: tree %p, index %p, level %d, slot %d, child %p", + rtree, (void *)index, level, slot, rnode->rn_child[slot]); + rnode = rnode->rn_child[slot]; + } + + slot = vm_radix_slot(index, level); + CTR5(KTR_VM, "insert: tree %p, index %p, level %d, slot %d, child %p", + rtree, (void *)index, level, slot, rnode->rn_child[slot]); + KASSERT(rnode->rn_child[slot] == NULL, + ("vm_radix_insert: Duplicate value %p at index: %lu\n", + rnode->rn_child[slot], (u_long)index)); + rnode->rn_child[slot] = val; + rnode->rn_count++; + + return 0; +} + +/* + * Returns the value stored at the index. If the index is not present + * NULL is returned. + */ +void * +vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) +{ + struct vm_radix_node *rnode; + int slot; + int level; + + if (index > VM_RADIX_MAX(rtree->rt_height)) + return NULL; + level = rtree->rt_height - 1; + rnode = rtree->rt_root; + while (rnode) { + slot = vm_radix_slot(index, level); + CTR5(KTR_VM, + "lookup: tree %p, index %p, level %d, slot %d, child %p", + rtree, (void *)index, level, slot, rnode->rn_child[slot]); + if (level == 0) + return rnode->rn_child[slot]; + rnode = rnode->rn_child[slot]; + level--; + } + CTR2(KTR_VM, "lookup: tree %p, index %p failed", rtree, (void *)index); + + return NULL; +} + +/* + * Looks up as many as cnt values between start and end and stores them + * in the caller allocated array out. The next index can be used to + * restart the scan. This optimizes forward scans in the tree. + */ +int +vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, + vm_pindex_t end, void **out, int cnt, vm_pindex_t *next) +{ + struct vm_radix_node *rnode; + struct vm_radix_node *child; + vm_pindex_t max; + vm_pindex_t inc; + int slot; + int level; + void *val; + int outidx; + int loops = 0; + + CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p", + rtree, (void *)start, (void *)end); + outidx = 0; + max = VM_RADIX_MAX(rtree->rt_height); + if (start > max) + return 0; + if (end > max + 1) + end = max + 1; + if (end == 0) + end = -1; +restart: + loops++; + if (loops > 1000) + panic("vm_radix_lookupn: looping %d\n", loops); + /* + * Search the tree from the top for any leaf node holding an index + * between start and end. + */ + level = rtree->rt_height - 1; + rnode = rtree->rt_root; + while (rnode) { + slot = vm_radix_slot(start, level); + CTR5(KTR_VM, + "lookupn: tree %p, index %p, level %d, slot %d, child %p", + rtree, (void *)start, level, slot, rnode->rn_child[slot]); + if (level == 0) + break; + /* + * If we don't have an exact match we must start our search + * from the next leaf and adjust our index appropriately. + */ + if ((child = rnode->rn_child[slot]) == NULL) { + /* + * Calculate how much to increment our index by + * based on the tree level. We must truncate the + * lower bits to start from the begnning of the next + * leaf. + */ + inc = 1LL << (level * VM_RADIX_WIDTH); + start &= ~VM_RADIX_MAX(level); + start += inc; + slot++; + CTR5(KTR_VM, + "lookupn: start %p end %p inc %d mask 0x%lX slot %d", + (void *)start, (void *)end, inc, ~VM_RADIX_MAX(level), slot); + for (; slot < VM_RADIX_COUNT && start < end; + slot++, start += inc) { + child = rnode->rn_child[slot]; + if (child) + break; + } + } + rnode = child; + level--; + } + if (rnode == NULL) { + /* + * If we still have another range to search, start looking + * from the next node. Otherwise, return what we've already + * found. The loop above has already adjusted start to the + * beginning of the next node. + * + * Detect start wrapping back to 0 and return in this case. + */ + if (start < end && start != 0) + goto restart; + goto out; + } + for (; outidx < cnt && slot < VM_RADIX_COUNT && start < end; + slot++, start++) { + val = rnode->rn_child[slot]; + if (val == NULL) + continue; + out[outidx++] = val; + } + /* + * Go fetch the next page to fill the requested number of pages + * otherwise the caller will simply call us again to fulfill the + * same request after the structures are pushed out of cache. + */ + if (outidx < cnt && start < end) + goto restart; + +out: + *next = start; + + return (outidx); +} + +/* + * Look up any entry at a position greater or equal to index. + */ +void * +vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) +{ + vm_pindex_t max; + void *val; + int n; + + max = VM_RADIX_MAX(rtree->rt_height); + n = vm_radix_lookupn(rtree, index, max + 1, &val, 1, &max); + if (n) + return (val); + return (NULL); +} + +/* + * Look up any entry at a position less than or equal to index. + */ +void * +vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) +{ + return NULL; +} + +/* + * Remove the specified index from the tree. If possible the height of the + * tree is adjusted after deletion. The value stored at index is returned + * panics if the key is not present. + */ +void * +vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) +{ + struct vm_radix_node *stack[VM_RADIX_LIMIT]; + struct vm_radix_node *rnode; + void *val; + int level; + int slot; + + KASSERT(index <= VM_RADIX_MAX(rtree->rt_height), + ("vm_radix_remove: %p index %jd out of range %jd.", + rtree, index, VM_RADIX_MAX(rtree->rt_height))); + val = NULL; + rnode = rtree->rt_root; + level = rtree->rt_height - 1; + /* + * Find the node and record the path in stack. + */ + while (level && rnode) { + stack[level] = rnode; + slot = vm_radix_slot(index, level); + rnode = rnode->rn_child[slot]; + CTR5(KTR_VM, + "remove: tree %p, index %p, level %d, slot %d, child %p", + rtree, (void *)index, level, slot, rnode->rn_child[slot]); + level--; + } + slot = vm_radix_slot(index, 0); + KASSERT(rnode != NULL && rnode->rn_child[slot] != NULL, + ("vm_radix_remove: index %jd not present in the tree.\n", index)); + + val = rnode->rn_child[slot]; + for (;;) { + rnode->rn_child[slot] = NULL; + rnode->rn_count--; + if (rnode->rn_count > 0) + break; + vm_radix_node_put(rnode); + if (rnode == rtree->rt_root) { + rtree->rt_root = NULL; + rtree->rt_height = 0; + break; + } + rnode = stack[++level]; + slot = vm_radix_slot(index, level); + + } + return (val); +} + +/* + * Attempts to reduce the height of the tree. + */ +void +vm_radix_shrink(struct vm_radix *rtree) +{ + struct vm_radix_node *tmp; + + if (rtree->rt_root == NULL) + return; + + /* Adjust the height of the tree. */ + while (rtree->rt_root->rn_count == 1 && + rtree->rt_root->rn_child[0] != NULL) { + tmp = rtree->rt_root; + rtree->rt_root = tmp->rn_child[0]; + rtree->rt_height--; + tmp->rn_count--; + vm_radix_node_put(tmp); + } + /* Finally see if we have an empty tree. */ + if (rtree->rt_root->rn_count == 0) { + vm_radix_node_put(rtree->rt_root); + rtree->rt_root = NULL; + rtree->rt_height = 0; + } +} Added: user/attilio/vmcontention/sys/vm/vm_radix.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/attilio/vmcontention/sys/vm/vm_radix.h Sat Oct 22 23:34:37 2011 (r226645) @@ -0,0 +1,64 @@ +/* + * Copyright (c) 2008 Mayur Shardul + * 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. + * + */ + +#ifndef _VM_RADIX_H_ +#define _VM_RADIX_H_ + +#include + +/* Default values of the tree parameters */ +#define VM_RADIX_WIDTH 5 +#define VM_RADIX_COUNT (1 << VM_RADIX_WIDTH) +#define VM_RADIX_MASK (VM_RADIX_COUNT - 1) +#define VM_RADIX_LIMIT howmany((sizeof(vm_pindex_t) * NBBY), VM_RADIX_WIDTH) + +/* Calculates maximum value for a tree of height h. */ +#define VM_RADIX_MAX(h) \ + ((h) == VM_RADIX_LIMIT ? ((vm_pindex_t)-1) : \ + (((vm_pindex_t)1 << ((h) * VM_RADIX_WIDTH)) - 1)) + +struct vm_radix_node { + SLIST_ENTRY(vm_radix_node) next; + void *rn_child[VM_RADIX_COUNT]; /* child nodes. */ + uint16_t rn_count; /* Valid children. */ +}; + +struct vm_radix { + struct vm_radix_node *rt_root; /* Root node. */ + int rt_height; /* Number of levels + 1. */ +}; + +int vm_radix_insert(struct vm_radix *, vm_pindex_t, void *); +void *vm_radix_remove(struct vm_radix *, vm_pindex_t); +void *vm_radix_lookup(struct vm_radix *, vm_pindex_t); +int vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, + vm_pindex_t end, void **out, int cnt, vm_pindex_t *next); +void *vm_radix_lookup_ge(struct vm_radix *, vm_pindex_t); +void *vm_radix_lookup_le(struct vm_radix *, vm_pindex_t); +void vm_radix_shrink(struct vm_radix *); + +#endif /* !_VM_RADIX_H_ */ Modified: user/attilio/vmcontention/sys/vm/vm_reserv.c ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_reserv.c Sat Oct 22 22:56:20 2011 (r226644) +++ user/attilio/vmcontention/sys/vm/vm_reserv.c Sat Oct 22 23:34:37 2011 (r226645) @@ -309,6 +309,35 @@ vm_reserv_alloc_page(vm_object_t object, /* * Look for an existing reservation. */ +#ifdef VM_RADIX + mpred = vm_radix_lookup_le(&object->rtree, pindex); + 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)]; + if ((m->flags & (PG_CACHED | PG_FREE)) == 0) + return (NULL); + vm_reserv_populate(rv); + return (m); + } + } + msucc = vm_radix_lookup_ge(&object->rtree, pindex); + 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)]; + 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) { @@ -347,6 +376,7 @@ vm_reserv_alloc_page(vm_object_t object, msucc = NULL; mpred = object->root = vm_page_splay(pindex, object->root); } +#endif /* * Determine the first index to the left that can be used. Modified: user/attilio/vmcontention/sys/vm/vm_reserv.h ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_reserv.h Sat Oct 22 22:56:20 2011 (r226644) +++ user/attilio/vmcontention/sys/vm/vm_reserv.h Sat Oct 22 23:34:37 2011 (r226645) @@ -57,6 +57,9 @@ void vm_reserv_rename(vm_page_t m, vm_o vm_paddr_t vm_reserv_startup(vm_offset_t *vaddr, vm_paddr_t end, vm_paddr_t high_water); +#else +#define vm_reserv_level_iffullpop(m) -1 + #endif /* VM_NRESERVLEVEL > 0 */ #endif /* _KERNEL */ #endif /* !_VM_RESERV_H_ */