svn commit: r226645 - in user/attilio/vmcontention/sys: conf vm
Attilio Rao
attilio at FreeBSD.org
Sat Oct 22 23:34:37 UTC 2011
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 <sys/_lock.h>
#include <sys/_mutex.h>
+#include <vm/vm_radix.h>
+
/*
* 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 <vm/vm_pageout.h>
#include <vm/vm_pager.h>
#include <vm/vm_phys.h>
+#include <vm/vm_radix.h>
#include <vm/vm_reserv.h>
#include <vm/vm_extern.h>
#include <vm/uma.h>
@@ -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 <mayur.shardul at gmail.com>
+ * Copyright (c) 2011 Jeffrey Roberson <jeff at freebsd.org>
+ * 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 <sys/cdefs.h>
+
+#include <sys/param.h>
+#include <sys/conf.h>
+#include <sys/systm.h>
+#include <sys/kernel.h>
+#include <sys/malloc.h>
+#include <sys/queue.h>
+#include <sys/param.h>
+#include <sys/lock.h>
+#include <sys/mutex.h>
+#include <sys/ktr.h>
+#include <vm/vm.h>
+#include <vm/vm_radix.h>
+#include <vm/vm_object.h>
+
+#include <sys/kdb.h>
+
+
+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 <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.
+ *
+ */
+
+#ifndef _VM_RADIX_H_
+#define _VM_RADIX_H_
+
+#include <sys/queue.h>
+
+/* 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_ */
More information about the svn-src-user
mailing list