svn commit: r236367 - user/attilio/vmcontention/sys/vm
Attilio Rao
attilio at FreeBSD.org
Thu May 31 22:54:09 UTC 2012
Author: attilio
Date: Thu May 31 22:54:08 2012
New Revision: 236367
URL: http://svn.freebsd.org/changeset/base/236367
Log:
Simplify insert path by using the same logic of vm_radix_remove() for
the recovery path. The bulk of vm_radix_remove() is put into a generic
function vm_radix_sweep() which allows 2 different modes (hard and soft):
the soft one will deal with half-constructed paths by cleaning them up.
Ideally all these complications should go once that a way to pre-allocate
is implemented, possibly by implementing path compression.
Requested and discussed with: jeff
Tested by: pho
Modified:
user/attilio/vmcontention/sys/vm/vm_radix.c
Modified: user/attilio/vmcontention/sys/vm/vm_radix.c
==============================================================================
--- user/attilio/vmcontention/sys/vm/vm_radix.c Thu May 31 21:32:29 2012 (r236366)
+++ user/attilio/vmcontention/sys/vm/vm_radix.c Thu May 31 22:54:08 2012 (r236367)
@@ -99,14 +99,12 @@
#define KSPLT64H(x) ((u_long)(((x) >> 32) & 0xFFFFFFFF))
#endif
-CTASSERT(VM_RADIX_HEIGHT >= VM_RADIX_LIMIT);
-CTASSERT((sizeof(u_int) * NBBY) >= VM_RADIX_LIMIT);
-
struct vm_radix_node {
void *rn_child[VM_RADIX_COUNT]; /* Child nodes. */
volatile uint32_t rn_count; /* Valid children. */
};
+CTASSERT(VM_RADIX_HEIGHT >= VM_RADIX_LIMIT);
CTASSERT(sizeof(struct vm_radix_node) < PAGE_SIZE);
static uma_zone_t vm_radix_node_zone;
@@ -356,6 +354,101 @@ vm_radix_reclaim_allnodes_internal(struc
}
/*
+ * Remove the specified index from the tree. If possible the height of the
+ * tree is adjusted after deletion. May be used to cleanup intermediate
+ * nodes of the path if the key is not entirely present.
+ */
+static void
+vm_radix_sweep(struct vm_radix *rtree, vm_pindex_t index, int color, int hard)
+{
+ struct vm_radix_node *stack[VM_RADIX_LIMIT];
+ struct vm_radix_node *rnode, *root;
+ int level;
+ int slot;
+
+ level = vm_radix_height(rtree, &root);
+ KASSERT(index <= VM_RADIX_MAX(level),
+ ("vm_radix_sweep: %p index out of range %jd.", rtree,
+ VM_RADIX_MAX(level)));
+ rnode = root;
+ level--;
+ /*
+ * Find the node and record the path in stack.
+ */
+ while (level && rnode) {
+ stack[level] = rnode;
+ slot = vm_radix_slot(index, level);
+ CTR6(KTR_VM,
+ "remove: tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p",
+ rtree, KSPLT64L(index), KSPLT64H(index), level, slot,
+ rnode);
+ CTR4(KTR_VM, "remove: tree %p, rnode %p, child %p, count %u",
+ rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
+ rnode = rnode->rn_child[slot];
+ level--;
+ }
+ if (rnode == NULL) {
+ if (hard)
+ panic("vm_radix_sweep: index not present.\n");
+
+ /*
+ * Almost certainly it got an half-constructed tree it was
+ * expected.
+ */
+ KASSERT(level < (VM_RADIX_LIMIT - 1),
+ ("vm_radix_sweep: level %d not consistent.\n", level));
+ ++level;
+ rnode = stack[level];
+ slot = vm_radix_slot(index, level);
+ } else {
+ slot = vm_radix_slot(index, 0);
+ if (hard &&
+ vm_radix_match(rnode->rn_child[slot], color) == NULL)
+ panic("vm_radix_sweep: index not present as leaf.\n");
+ }
+
+ for (;;) {
+ CTR6(KTR_VM,
+"remove: resetting tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p",
+ rtree, KSPLT64L(index), KSPLT64H(index), level, slot,
+ rnode);
+ CTR4(KTR_VM,
+ "remove: resetting tree %p, rnode %p, child %p, count %u",
+ rtree, rnode,
+ (rnode != NULL) ? rnode->rn_child[slot] : NULL,
+ (rnode != NULL) ? rnode->rn_count : 0);
+ rnode->rn_child[slot] = NULL;
+ /*
+ * Use atomics for the last level since red and black
+ * will both adjust it.
+ * Use a write memory barrier here in order to avoid
+ * rn_count reaching 0 before to fetch the actual pointer.
+ * Concurrent black removal, infact, may want to reclaim
+ * the radix node itself before to read it.
+ */
+ MPASS(rnode->rn_count != 0);
+ if (level == 0)
+ atomic_add_rel_32(&rnode->rn_count, -1);
+ else
+ rnode->rn_count--;
+
+ /*
+ * Only allow black removes to prune the tree.
+ */
+ if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0)
+ break;
+ vm_radix_node_put(rnode);
+ if (rnode == root) {
+ vm_radix_setroot(rtree, NULL, 0);
+ break;
+ }
+ rnode = stack[++level];
+ slot = vm_radix_slot(index, level);
+
+ }
+}
+
+/*
* Inserts the key-value pair in to the radix tree. Returns errno.
* Panics if the key already exists.
*/
@@ -363,8 +456,7 @@ int
vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val)
{
struct vm_radix_node *iroot, *rnode, *root;
- u_int allocmsk;
- int clev, ilevel, level, slot;
+ int ilevel, level, slot;
CTR4(KTR_VM,
"insert: tree %p, " KFRMT64(index) ", val %p", rtree,
@@ -417,13 +509,17 @@ vm_radix_insert(struct vm_radix *rtree,
}
/* Now that the tree is tall enough, fill in the path to the index. */
- allocmsk = 0;
- clev = level;
rnode = root;
for (level = level - 1; level > 0; level--) {
slot = vm_radix_slot(index, level);
/* Add the required intermidiate nodes. */
if (rnode->rn_child[slot] == NULL) {
+
+ /*
+ * In case of failed allocation, the vm_radix_sweep()
+ * will unwind back rn_count appropriately.
+ */
+ rnode->rn_count++;
rnode->rn_child[slot] = vm_radix_node_get();
if (rnode->rn_child[slot] == NULL) {
CTR6(KTR_VM,
@@ -434,35 +530,17 @@ vm_radix_insert(struct vm_radix *rtree,
"insert: tree %p, rnode %p, child %p, count %u ENOMEM",
rtree, rnode, rnode->rn_child[slot],
rnode->rn_count);
- MPASS(level != clev || allocmsk == 0);
- while (allocmsk != 0) {
- rnode = root;
- level = clev;
- level--;
- slot = vm_radix_slot(index, level);
- CTR4(KTR_VM,
- "insert: unwind root %p, level %d, slot %d, allocmsk: 0x%x",
- root, level, slot, allocmsk);
- MPASS(level >= (ffs(allocmsk) - 1));
- while (level > (ffs(allocmsk) - 1)) {
- MPASS(level > 0);
- slot = vm_radix_slot(index,
- level);
- rnode = rnode->rn_child[slot];
- level--;
- }
- MPASS((allocmsk & (1 << level)) != 0);
- allocmsk &= ~(1 << level);
- rnode->rn_count--;
- vm_radix_node_put(rnode->rn_child[slot]);
- rnode->rn_child[slot] = NULL;
- }
+ vm_radix_sweep(rtree, index, VM_RADIX_BLACK, 0);
+
+ /*
+ * vm_radix_sweep() may have changed the shape
+ * of the tree, refetch the root.
+ */
+ vm_radix_height(rtree, &root);
vm_radix_unwind_heightup(rtree, root, iroot,
ilevel);
return (ENOMEM);
}
- rnode->rn_count++;
- allocmsk |= (1 << level);
}
CTR6(KTR_VM,
"insert: tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p",
@@ -812,86 +890,13 @@ restart:
}
/*
- * 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.
+ * Remove an entry from the tree. Expects the entry to be already present.
*/
-void *
+void
vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color)
{
- struct vm_radix_node *stack[VM_RADIX_LIMIT];
- struct vm_radix_node *rnode, *root;
- void *val;
- int level;
- int slot;
- level = vm_radix_height(rtree, &root);
- KASSERT(index <= VM_RADIX_MAX(level),
- ("vm_radix_remove: %p index out of range %jd.", rtree,
- VM_RADIX_MAX(level)));
- rnode = root;
- val = NULL;
- level--;
- /*
- * Find the node and record the path in stack.
- */
- while (level && rnode) {
- stack[level] = rnode;
- slot = vm_radix_slot(index, level);
- CTR6(KTR_VM,
- "remove: tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p",
- rtree, KSPLT64L(index), KSPLT64H(index), level, slot,
- rnode);
- CTR4(KTR_VM, "remove: tree %p, rnode %p, child %p, count %u",
- rtree, rnode, rnode->rn_child[slot], rnode->rn_count);
- rnode = rnode->rn_child[slot];
- level--;
- }
- KASSERT(rnode != NULL,
- ("vm_radix_remove: index not present in the tree.\n"));
- slot = vm_radix_slot(index, 0);
- val = vm_radix_match(rnode->rn_child[slot], color);
- KASSERT(val != NULL,
- ("vm_radix_remove: index not present in the tree.\n"));
-
- for (;;) {
- CTR6(KTR_VM,
-"remove: resetting tree %p, " KFRMT64(index) ", level %d, slot %d, rnode %p",
- rtree, KSPLT64L(index), KSPLT64H(index), level, slot,
- rnode);
- CTR4(KTR_VM,
- "remove: resetting tree %p, rnode %p, child %p, count %u",
- rtree, rnode,
- (rnode != NULL) ? rnode->rn_child[slot] : NULL,
- (rnode != NULL) ? rnode->rn_count : 0);
- rnode->rn_child[slot] = NULL;
- /*
- * Use atomics for the last level since red and black
- * will both adjust it.
- * Use a write memory barrier here in order to avoid
- * rn_count reaching 0 before to fetch the actual pointer.
- * Concurrent black removal, infact, may want to reclaim
- * the radix node itself before to read it.
- */
- if (level == 0)
- atomic_add_rel_32(&rnode->rn_count, -1);
- else
- rnode->rn_count--;
- /*
- * Only allow black removes to prune the tree.
- */
- if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0)
- break;
- vm_radix_node_put(rnode);
- if (rnode == root) {
- vm_radix_setroot(rtree, NULL, 0);
- break;
- }
- rnode = stack[++level];
- slot = vm_radix_slot(index, level);
-
- }
- return (val);
+ vm_radix_sweep(rtree, index, color, 1);
}
/*
More information about the svn-src-user
mailing list