47a48
> #include <vm/vm_param.h>
60c61
< #if 0
---
> #ifndef UMA_MD_SMALL_ALLOC
143c144
< static struct vm_radix_node *
---
> static __inline struct vm_radix_node *
153c154
< static void
---
> static __inline void
163c164
< static inline int
---
> static __inline int
181c182
< NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM);
---
> NULL, NULL, VM_RADIX_HEIGHT, UMA_ZONE_VM);
184a186,214
> * 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;
> }
>
> /*
192c222
< int slot;
---
> struct vm_radix_node *root;
193a224
> int slot;
198a230
> level = vm_radix_height(rtree, &root);
203,204c235
< while (rtree->rt_height == 0 ||
< index > VM_RADIX_MAX(rtree->rt_height)) {
---
> while (level == 0 || index > VM_RADIX_MAX(level)) {
206c237,241
< 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));
210c245
< if (rtree->rt_root == NULL || rtree->rt_root->rn_count != 0) {
---
> if (root == NULL || root->rn_count != 0) {
214,215c249,255
< 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);
218c258
< rtree->rt_root = rnode;
---
> root = rnode;
220,223c260
< 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);
227,228c264,265
< rnode = rtree->rt_root;
< for (level = rtree->rt_height - 1; level > 0; level--) {
---
> rnode = root;
> for (level = level - 1; level > 0; level--) {
266c303,304
< if (index > VM_RADIX_MAX(rtree->rt_height))
---
> level = vm_radix_height(rtree, &rnode);
> if (index > VM_RADIX_MAX(level))
268,269c306
< level = rtree->rt_height - 1;
< rnode = rtree->rt_root;
---
> level--;
307c344,346
< max = VM_RADIX_MAX(rtree->rt_height);
---
> restart:
> level = vm_radix_height(rtree, &rnode);
> max = VM_RADIX_MAX(level);
309c348
< return 0;
---
> goto out;
312d350
< restart:
320,321c358
< level = rtree->rt_height - 1;
< rnode = rtree->rt_root;
---
> level--;
407c444,446
< if (rtree->rt_root == NULL)
---
> restart:
> level = vm_radix_height(rtree, &rnode);
> if (rnode == NULL)
409c448
< max = VM_RADIX_MAX(rtree->rt_height);
---
> max = VM_RADIX_MAX(level);
412d450
< restart:
420,421c458
< level = rtree->rt_height - 1;
< rnode = rtree->rt_root;
---
> level--;
476c513
< struct vm_radix_node *rnode;
---
> struct vm_radix_node *rnode, *root;
481c518,519
< KASSERT(index <= VM_RADIX_MAX(rtree->rt_height),
---
> level = vm_radix_height(rtree, &root);
> KASSERT(index <= VM_RADIX_MAX(level),
483c521,522
< rtree, index, VM_RADIX_MAX(rtree->rt_height)));
---
> rtree, index, VM_RADIX_MAX(level)));
> rnode = root;
485,486c524
< rnode = rtree->rt_root;
< level = rtree->rt_height - 1;
---
> level--;
510,512c548,549
< if (rnode == rtree->rt_root) {
< rtree->rt_root = NULL;
< rtree->rt_height = 0;
---
> if (rnode == root) {
> vm_radix_setroot(rtree, NULL, 0);
528c565,566
< struct vm_radix_node *tmp;
---
> struct vm_radix_node *tmp, *root;
> int level;
530c568
< if (rtree->rt_root == NULL)
---
> if (rtree->rt_root == 0)
531a570
> level = vm_radix_height(rtree, &root);
534,539c573,577
< 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--;
543,546c581,584
< 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--;
547a586
> vm_radix_setroot(rtree, root, level);