Date: Fri, 28 Oct 2011 03:42:41 +0000 (UTC) From: Jeff Roberson <jeff@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r226876 - user/attilio/vmcontention/sys/vm Message-ID: <201110280342.p9S3gfNL040060@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: jeff Date: Fri Oct 28 03:42:41 2011 New Revision: 226876 URL: http://svn.freebsd.org/changeset/base/226876 Log: - Use a single uintptr_t for the root of the radix node that encodes the height and a pointer so that the update to the root is atomic. This permits safe lookups in parallel with tree expansion. Shrinking the space requirements is a small bonus. Modified: user/attilio/vmcontention/sys/vm/vm_object.c user/attilio/vmcontention/sys/vm/vm_radix.c user/attilio/vmcontention/sys/vm/vm_radix.h Modified: user/attilio/vmcontention/sys/vm/vm_object.c ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_object.c Fri Oct 28 03:07:23 2011 (r226875) +++ user/attilio/vmcontention/sys/vm/vm_object.c Fri Oct 28 03:42:41 2011 (r226876) @@ -209,8 +209,7 @@ _vm_object_allocate(objtype_t type, vm_p LIST_INIT(&object->shadow_head); #ifdef VM_RADIX - object->rtree.rt_height = 0; - object->rtree.rt_root = NULL; + object->rtree.rt_root = 0; #else object->root = NULL; #endif Modified: user/attilio/vmcontention/sys/vm/vm_radix.c ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_radix.c Fri Oct 28 03:07:23 2011 (r226875) +++ user/attilio/vmcontention/sys/vm/vm_radix.c Fri Oct 28 03:42:41 2011 (r226876) @@ -45,6 +45,7 @@ #include <sys/ktr.h> #include <vm/uma.h> #include <vm/vm.h> +#include <vm/vm_param.h> #include <vm/vm_extern.h> #include <vm/vm_kern.h> #include <vm/vm_page.h> @@ -57,7 +58,7 @@ CTASSERT(sizeof(struct vm_radix_node) < static uma_zone_t vm_radix_node_zone; -#if 0 +#ifndef UMA_MD_SMALL_ALLOC static void * vm_radix_node_zone_allocf(uma_zone_t zone, int size, uint8_t *flags, int wait) { @@ -140,7 +141,7 @@ vm_radix_node_zone_dtor(void *mem, int s /* * Allocate a radix node. Initializes all elements to 0. */ -static struct vm_radix_node * +static __inline struct vm_radix_node * vm_radix_node_get(void) { @@ -150,7 +151,7 @@ vm_radix_node_get(void) /* * Free radix node. */ -static void +static __inline void vm_radix_node_put(struct vm_radix_node *rnode) { @@ -160,7 +161,7 @@ vm_radix_node_put(struct vm_radix_node * /* * Return the position in the array for a given level. */ -static inline int +static __inline int vm_radix_slot(vm_pindex_t index, int level) { @@ -178,7 +179,36 @@ vm_radix_init(void) #else NULL, #endif - NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM); + NULL, NULL, VM_RADIX_HEIGHT, UMA_ZONE_VM); +} + +/* + * Extract the root node and height from a radix tree with a single load. + */ +static __inline int +vm_radix_height(struct vm_radix *rtree, struct vm_radix_node **rnode) +{ + uintptr_t root; + int height; + + root = rtree->rt_root; + height = root & VM_RADIX_HEIGHT; + *rnode = (struct vm_radix_node *)(root - height); + return (height); +} + + +/* + * Set the root node and height for a radix tree. + */ +static inline void +vm_radix_setroot(struct vm_radix *rtree, struct vm_radix_node *rnode, + int height) +{ + uintptr_t root; + + root = (uintptr_t)rnode | height; + rtree->rt_root = root; } /* @@ -189,43 +219,50 @@ int vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val) { struct vm_radix_node *rnode; - int slot; + struct vm_radix_node *root; int level; + int slot; 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"); + level = vm_radix_height(rtree, &root); /* * 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)) { + while (level == 0 || index > VM_RADIX_MAX(level)) { CTR3(KTR_VM, "insert: expanding %jd > %jd height %d", - index, VM_RADIX_MAX(rtree->rt_height), rtree->rt_height); + index, VM_RADIX_MAX(level), level); + level++; + KASSERT(level <= VM_RADIX_LIMIT, + ("vm_radix_insert: Tree %p height %d too tall", + rtree, level)); /* * Only allocate tree nodes if they are needed. */ - if (rtree->rt_root == NULL || rtree->rt_root->rn_count != 0) { + if (root == NULL || 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; + /* + * Store the new pointer with a memory barrier so + * that it is visible before the new root. + */ + if (root) { + atomic_store_rel_ptr((volatile uintptr_t *) + &rnode->rn_child[0], (uintptr_t)root); rnode->rn_count = 1; } - rtree->rt_root = rnode; + 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)); + vm_radix_setroot(rtree, root, level); } /* 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--) { + 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) { @@ -263,10 +300,10 @@ vm_radix_lookup(struct vm_radix *rtree, int slot; int level; - if (index > VM_RADIX_MAX(rtree->rt_height)) + level = vm_radix_height(rtree, &rnode); + if (index > VM_RADIX_MAX(level)) return NULL; - level = rtree->rt_height - 1; - rnode = rtree->rt_root; + level--; while (rnode) { slot = vm_radix_slot(index, level); CTR5(KTR_VM, @@ -304,12 +341,13 @@ vm_radix_lookupn(struct vm_radix *rtree, CTR3(KTR_VM, "lookupn: tree %p, start %p, end %p", rtree, (void *)start, (void *)end); outidx = 0; - max = VM_RADIX_MAX(rtree->rt_height); +restart: + level = vm_radix_height(rtree, &rnode); + max = VM_RADIX_MAX(level); if (start > max) - return 0; + goto out; if (end > max || end == 0) end = max; -restart: loops++; if (loops > 1000) panic("vm_radix_lookupn: looping %d\n", loops); @@ -317,8 +355,7 @@ restart: * 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; + level--; while (rnode) { slot = vm_radix_slot(start, level); CTR5(KTR_VM, @@ -404,12 +441,13 @@ vm_radix_lookup_le(struct vm_radix *rtre CTR2(KTR_VM, "lookup_le: tree %p, index %p", rtree, (void *)index); - if (rtree->rt_root == NULL) +restart: + level = vm_radix_height(rtree, &rnode); + if (rnode == NULL) return (NULL); - max = VM_RADIX_MAX(rtree->rt_height); + max = VM_RADIX_MAX(level); if (index > max || index == 0) index = max; -restart: loops++; if (loops > 1000) panic("vm_radix_looku_le: looping %d\n", loops); @@ -417,8 +455,7 @@ restart: * Search the tree from the top for any leaf node holding an index * lower than 'index'. */ - level = rtree->rt_height - 1; - rnode = rtree->rt_root; + level--; while (rnode) { slot = vm_radix_slot(index, level); CTR5(KTR_VM, @@ -473,17 +510,18 @@ 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; + struct vm_radix_node *rnode, *root; void *val; int level; int slot; - KASSERT(index <= VM_RADIX_MAX(rtree->rt_height), + level = vm_radix_height(rtree, &root); + KASSERT(index <= VM_RADIX_MAX(level), ("vm_radix_remove: %p index %jd out of range %jd.", - rtree, index, VM_RADIX_MAX(rtree->rt_height))); + rtree, index, VM_RADIX_MAX(level))); + rnode = root; val = NULL; - rnode = rtree->rt_root; - level = rtree->rt_height - 1; + level--; /* * Find the node and record the path in stack. */ @@ -507,9 +545,8 @@ vm_radix_remove(struct vm_radix *rtree, if (rnode->rn_count > 0) break; vm_radix_node_put(rnode); - if (rnode == rtree->rt_root) { - rtree->rt_root = NULL; - rtree->rt_height = 0; + if (rnode == root) { + vm_radix_setroot(rtree, NULL, 0); break; } rnode = stack[++level]; @@ -525,24 +562,26 @@ vm_radix_remove(struct vm_radix *rtree, void vm_radix_shrink(struct vm_radix *rtree) { - struct vm_radix_node *tmp; + struct vm_radix_node *tmp, *root; + int level; - if (rtree->rt_root == NULL) + if (rtree->rt_root == 0) return; + level = vm_radix_height(rtree, &root); /* 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--; + while (root->rn_count == 1 && root->rn_child[0] != NULL) { + tmp = root; + root->rn_count--; + root = root->rn_child[0]; + level--; 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; + if (root->rn_count == 0) { + vm_radix_node_put(root); + root = NULL; + level--; } + vm_radix_setroot(rtree, root, level); } Modified: user/attilio/vmcontention/sys/vm/vm_radix.h ============================================================================== --- user/attilio/vmcontention/sys/vm/vm_radix.h Fri Oct 28 03:07:23 2011 (r226875) +++ user/attilio/vmcontention/sys/vm/vm_radix.h Fri Oct 28 03:42:41 2011 (r226876) @@ -35,6 +35,9 @@ #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) +#define VM_RADIX_HEIGHT 0xf /* Bits of height in root */ + +CTASSERT(VM_RADIX_HEIGHT >= VM_RADIX_LIMIT); /* Calculates maximum value for a tree of height h. */ #define VM_RADIX_MAX(h) \ @@ -42,14 +45,16 @@ (((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. */ }; +/* + * Radix tree root. The height and pointer are set together to permit + * coherent lookups while the root is modified. + */ struct vm_radix { - struct vm_radix_node *rt_root; /* Root node. */ - int rt_height; /* Number of levels + 1. */ + uintptr_t rt_root; /* root + height */ }; void vm_radix_init(void);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201110280342.p9S3gfNL040060>