sys/vm/vm_radix.c

   1 /*
   2  * Copyright (c) 2013 EMC Corp.
   3  * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org>
   4  * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com>
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  26  * SUCH DAMAGE.
  27  *
  28  */
  29
  30 /*
  31  * Path-compressed radix trie implementation.
  32  * The following code is not generalized into a general purpose library
  33  * because there are way too many parameters embedded that should really
  34  * be decided by the library consumers.  At the same time, consumers
  35  * of this code must achieve highest possible performance.
  36  *
  37  * The implementation takes into account the following rationale:
  38  * - Size of the nodes should be as small as possible but still big enough
  39  *   to avoid a large maximum depth for the trie.  This is a balance
  40  *   between the necessity to not wire too much physical memory for the nodes
  41  *   and the necessity to avoid too much cache pollution during the trie
  42  *   operations.
  43  * - There is not a huge bias toward the number of lookup operations over
  44  *   the number of insert and remove operations.  This basically implies
  45  *   that optimizations supposedly helping one operation but hurting the
  46  *   other might be carefully evaluated.
  47  * - On average not many nodes are expected to be fully populated, hence
  48  *   level compression may just complicate things.
  49  */
  50
  51 #include <sys/cdefs.h>
  52
  53 #include "opt_ddb.h"
  54
  55 #include <sys/param.h>
  56 #include <sys/systm.h>
  57 #include <sys/kernel.h>
  58 #include <sys/vmmeter.h>
  59
  60 #include <vm/uma.h>
  61 #include <vm/vm.h>
  62 #include <vm/vm_param.h>
  63 #include <vm/vm_page.h>
  64 #include <vm/vm_radix.h>
  65
  66 #ifdef DDB
  67 #include <ddb/ddb.h>
  68 #endif
  69
  70 /*
  71  * These widths should allow the pointers to a node's children to fit within
  72  * a single cache line.  The extra levels from a narrow width should not be
  73  * a problem thanks to path compression.
  74  */
  75 #ifdef __LP64__
  76 #define VM_RADIX_WIDTH  4
  77 #else
  78 #define VM_RADIX_WIDTH  3
  79 #endif
  80
  81 #define VM_RADIX_COUNT  (1 << VM_RADIX_WIDTH)
  82 #define VM_RADIX_MASK   (VM_RADIX_COUNT - 1)
  83 #define VM_RADIX_LIMIT                                                  \
  84         (howmany((sizeof(vm_pindex_t) * NBBY), VM_RADIX_WIDTH) - 1)
  85
  86 /* Flag bits stored in node pointers. */
  87 #define VM_RADIX_ISLEAF 0x1
  88 #define VM_RADIX_FLAGS  0x1
  89 #define VM_RADIX_PAD    VM_RADIX_FLAGS
  90
  91 /* Returns one unit associated with specified level. */
  92 #define VM_RADIX_UNITLEVEL(lev)                                         \
  93         ((vm_pindex_t)1 << ((VM_RADIX_LIMIT - (lev)) * VM_RADIX_WIDTH))
  94
  95 struct vm_radix_node {
  96         void            *rn_child[VM_RADIX_COUNT];      /* Child nodes. */
  97         vm_pindex_t      rn_owner;                      /* Owner of record. */
  98         uint16_t         rn_count;                      /* Valid children. */
  99         uint16_t         rn_clev;                       /* Current level. */
 100 };
 101
 102 static uma_zone_t vm_radix_node_zone;
 103
 104 /*
 105  * Allocate a radix node.  Pre-allocation should ensure that the request
 106  * will always be satisfied.
 107  */
 108 static __inline struct vm_radix_node *
 109 vm_radix_node_get(vm_pindex_t owner, uint16_t count, uint16_t clevel)
 110 {
 111         struct vm_radix_node *rnode;
 112
 113         rnode = uma_zalloc(vm_radix_node_zone, M_NOWAIT);
 114
 115         /*
 116          * The required number of nodes should already be pre-allocated
 117          * by vm_radix_prealloc().  However, UMA can hold a few nodes
 118          * in per-CPU buckets, which will not be accessible by the
 119          * current CPU.  Thus, the allocation could return NULL when
 120          * the pre-allocated pool is close to exhaustion.  Anyway,
 121          * in practice this should never occur because a new node
 122          * is not always required for insert.  Thus, the pre-allocated
 123          * pool should have some extra pages that prevent this from
 124          * becoming a problem.
 125          */
 126         if (rnode == NULL)
 127                 panic("%s: uma_zalloc() returned NULL for a new node",
 128                     __func__);
 129         rnode->rn_owner = owner;
 130         rnode->rn_count = count;
 131         rnode->rn_clev = clevel;
 132         return (rnode);
 133 }
 134
 135 /*
 136  * Free radix node.
 137  */
 138 static __inline void
 139 vm_radix_node_put(struct vm_radix_node *rnode)
 140 {
 141
 142         uma_zfree(vm_radix_node_zone, rnode);
 143 }
 144
 145 /*
 146  * Return the position in the array for a given level.
 147  */
 148 static __inline int
 149 vm_radix_slot(vm_pindex_t index, uint16_t level)
 150 {
 151
 152         return ((index >> ((VM_RADIX_LIMIT - level) * VM_RADIX_WIDTH)) &
 153             VM_RADIX_MASK);
 154 }
 155
 156 /* Trims the key after the specified level. */
 157 static __inline vm_pindex_t
 158 vm_radix_trimkey(vm_pindex_t index, uint16_t level)
 159 {
 160         vm_pindex_t ret;
 161
 162         ret = index;
 163         if (level < VM_RADIX_LIMIT) {
 164                 ret >>= (VM_RADIX_LIMIT - level) * VM_RADIX_WIDTH;
 165                 ret <<= (VM_RADIX_LIMIT - level) * VM_RADIX_WIDTH;
 166         }
 167         return (ret);
 168 }
 169
 170 /*
 171  * Get the root node for a radix tree.
 172  */
 173 static __inline struct vm_radix_node *
 174 vm_radix_getroot(struct vm_radix *rtree)
 175 {
 176
 177         return ((struct vm_radix_node *)(rtree->rt_root & ~VM_RADIX_FLAGS));
 178 }
 179
 180 /*
 181  * Set the root node for a radix tree.
 182  */
 183 static __inline void
 184 vm_radix_setroot(struct vm_radix *rtree, struct vm_radix_node *rnode)
 185 {
 186
 187         rtree->rt_root = (uintptr_t)rnode;
 188 }
 189
 190 /*
 191  * Returns the associated page extracted from rnode if available,
 192  * and NULL otherwise.
 193  */
 194 static __inline vm_page_t
 195 vm_radix_node_page(struct vm_radix_node *rnode)
 196 {
 197
 198         return ((((uintptr_t)rnode & VM_RADIX_ISLEAF) != 0) ?
 199             (vm_page_t)((uintptr_t)rnode & ~VM_RADIX_FLAGS) : NULL);
 200 }
 201
 202 /*
 203  * Adds the page as a child of the provided node.
 204  */
 205 static __inline void
 206 vm_radix_addpage(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev,
 207     vm_page_t page)
 208 {
 209         int slot;
 210
 211         slot = vm_radix_slot(index, clev);
 212         rnode->rn_child[slot] = (void *)((uintptr_t)page | VM_RADIX_ISLEAF);
 213 }
 214
 215 /*
 216  * Returns the slot where two keys differ.
 217  * It cannot accept 2 equal keys.
 218  */
 219 static __inline uint16_t
 220 vm_radix_keydiff(vm_pindex_t index1, vm_pindex_t index2)
 221 {
 222         uint16_t clev;
 223
 224         KASSERT(index1 != index2, ("%s: passing the same key value %jx",
 225             __func__, (uintmax_t)index1));
 226
 227         index1 ^= index2;
 228         for (clev = 0; clev <= VM_RADIX_LIMIT ; clev++)
 229                 if (vm_radix_slot(index1, clev))
 230                         return (clev);
 231         panic("%s: cannot reach this point", __func__);
 232         return (0);
 233 }
 234
 235 /*
 236  * Returns TRUE if it can be determined that key does not belong to the
 237  * specified rnode.  Otherwise, returns FALSE.
 238  */
 239 static __inline boolean_t
 240 vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t idx)
 241 {
 242
 243         if (rnode->rn_clev > 0) {
 244                 idx = vm_radix_trimkey(idx, rnode->rn_clev - 1);
 245                 idx -= rnode->rn_owner;
 246                 if (idx != 0)
 247                         return (TRUE);
 248         }
 249         return (FALSE);
 250 }
 251
 252 /*
 253  * Adjusts the idx key to the first upper level available, based on a valid
 254  * initial level and map of available levels.
 255  * Returns a value bigger than 0 to signal that there are not valid levels
 256  * available.
 257  */
 258 static __inline int
 259 vm_radix_addlev(vm_pindex_t *idx, boolean_t *levels, uint16_t ilev)
 260 {
 261         vm_pindex_t wrapidx;
 262
 263         for (; levels[ilev] == FALSE ||
 264             vm_radix_slot(*idx, ilev) == (VM_RADIX_COUNT - 1); ilev--)
 265                 if (ilev == 0)
 266                         break;
 267         KASSERT(ilev > 0 || levels[0],
 268             ("%s: levels back-scanning problem", __func__));
 269         if (ilev == 0 && vm_radix_slot(*idx, ilev) == (VM_RADIX_COUNT - 1))
 270                 return (1);
 271         wrapidx = *idx;
 272         *idx = vm_radix_trimkey(*idx, ilev);
 273         *idx += VM_RADIX_UNITLEVEL(ilev);
 274         return (*idx < wrapidx);
 275 }
 276
 277 /*
 278  * Adjusts the idx key to the first lower level available, based on a valid
 279  * initial level and map of available levels.
 280  * Returns a value bigger than 0 to signal that there are not valid levels
 281  * available.
 282  */
 283 static __inline int
 284 vm_radix_declev(vm_pindex_t *idx, boolean_t *levels, uint16_t ilev)
 285 {
 286         vm_pindex_t wrapidx;
 287
 288         for (; levels[ilev] == FALSE ||
 289             vm_radix_slot(*idx, ilev) == 0; ilev--)
 290                 if (ilev == 0)
 291                         break;
 292         KASSERT(ilev > 0 || levels[0],
 293             ("%s: levels back-scanning problem", __func__));
 294         if (ilev == 0 && vm_radix_slot(*idx, ilev) == 0)
 295                 return (1);
 296         wrapidx = *idx;
 297         *idx = vm_radix_trimkey(*idx, ilev);
 298         *idx |= VM_RADIX_UNITLEVEL(ilev) - 1;
 299         *idx -= VM_RADIX_UNITLEVEL(ilev);
 300         return (*idx > wrapidx);
 301 }
 302
 303 /*
 304  * Internal helper for vm_radix_reclaim_allnodes().
 305  * This function is recursive.
 306  */
 307 static void
 308 vm_radix_reclaim_allnodes_int(struct vm_radix_node *rnode)
 309 {
 310         int slot;
 311
 312         for (slot = 0; slot < VM_RADIX_COUNT && rnode->rn_count != 0; slot++) {
 313                 if (rnode->rn_child[slot] == NULL)
 314                         continue;
 315                 if (vm_radix_node_page(rnode->rn_child[slot]) == NULL)
 316                         vm_radix_reclaim_allnodes_int(rnode->rn_child[slot]);
 317                 rnode->rn_child[slot] = NULL;
 318                 rnode->rn_count--;
 319         }
 320         vm_radix_node_put(rnode);
 321 }
 322
 323 #ifdef INVARIANTS
 324 /*
 325  * Radix node zone destructor.
 326  */
 327 static void
 328 vm_radix_node_zone_dtor(void *mem, int size __unused, void *arg __unused)
 329 {
 330         struct vm_radix_node *rnode;
 331         int slot;
 332
 333         rnode = mem;
 334         KASSERT(rnode->rn_count == 0,
 335             ("vm_radix_node_put: rnode %p has %d children", rnode,
 336             rnode->rn_count));
 337         for (slot = 0; slot < VM_RADIX_COUNT; slot++)
 338                 KASSERT(rnode->rn_child[slot] == NULL,
 339                     ("vm_radix_node_put: rnode %p has a child", rnode));
 340 }
 341 #endif
 342
 343 /*
 344  * Radix node zone initializer.
 345  */
 346 static int
 347 vm_radix_node_zone_init(void *mem, int size __unused, int flags __unused)
 348 {
 349         struct vm_radix_node *rnode;
 350
 351         rnode = mem;
 352         memset(rnode->rn_child, 0, sizeof(rnode->rn_child));
 353         return (0);
 354 }
 355
 356 /*
 357  * Pre-allocate intermediate nodes from the UMA slab zone.
 358  */
 359 static void
 360 vm_radix_prealloc(void *arg __unused)
 361 {
 362
 363         if (!uma_zone_reserve_kva(vm_radix_node_zone, cnt.v_page_count))
 364                 panic("%s: unable to create new zone", __func__);
 365         uma_prealloc(vm_radix_node_zone, cnt.v_page_count);
 366 }
 367 SYSINIT(vm_radix_prealloc, SI_SUB_KMEM, SI_ORDER_SECOND, vm_radix_prealloc,
 368     NULL);
 369
 370 /*
 371  * Initialize the UMA slab zone.
 372  * Until vm_radix_prealloc() is called, the zone will be served by the
 373  * UMA boot-time pre-allocated pool of pages.
 374  */
 375 void
 376 vm_radix_init(void)
 377 {
 378
 379         vm_radix_node_zone = uma_zcreate("RADIX NODE",
 380             sizeof(struct vm_radix_node), NULL,
 381 #ifdef INVARIANTS
 382             vm_radix_node_zone_dtor,
 383 #else
 384             NULL,
 385 #endif
 386             vm_radix_node_zone_init, NULL, VM_RADIX_PAD, UMA_ZONE_VM |
 387             UMA_ZONE_NOFREE);
 388 }
 389
 390 /*
 391  * Inserts the key-value pair into the trie.
 392  * Panics if the key already exists.
 393  */
 394 void
 395 vm_radix_insert(struct vm_radix *rtree, vm_page_t page)
 396 {
 397         vm_pindex_t index, newind;
 398         struct vm_radix_node *rnode, *tmp, *tmp2;
 399         vm_page_t m;
 400         int slot;
 401         uint16_t clev;
 402
 403         index = page->pindex;
 404
 405         /*
 406          * The owner of record for root is not really important because it
 407          * will never be used.
 408          */
 409         rnode = vm_radix_getroot(rtree);
 410         if (rnode == NULL) {
 411                 rnode = vm_radix_node_get(0, 1, 0);
 412                 vm_radix_setroot(rtree, rnode);
 413                 vm_radix_addpage(rnode, index, 0, page);
 414                 return;
 415         }
 416         while (rnode != NULL) {
 417                 if (vm_radix_keybarr(rnode, index))
 418                         break;
 419                 slot = vm_radix_slot(index, rnode->rn_clev);
 420                 m = vm_radix_node_page(rnode->rn_child[slot]);
 421                 if (m != NULL) {
 422                         if (m->pindex == index)
 423                                 panic("%s: key %jx is already present",
 424                                     __func__, (uintmax_t)index);
 425                         clev = vm_radix_keydiff(m->pindex, index);
 426                         tmp = vm_radix_node_get(vm_radix_trimkey(index,
 427                             clev - 1), 2, clev);
 428                         rnode->rn_child[slot] = tmp;
 429                         vm_radix_addpage(tmp, index, clev, page);
 430                         vm_radix_addpage(tmp, m->pindex, clev, m);
 431                         return;
 432                 }
 433                 if (rnode->rn_child[slot] == NULL) {
 434                         rnode->rn_count++;
 435                         vm_radix_addpage(rnode, index, rnode->rn_clev, page);
 436                         return;
 437                 }
 438                 rnode = rnode->rn_child[slot];
 439         }
 440         if (rnode == NULL)
 441                 panic("%s: path traversal ended unexpectedly", __func__);
 442
 443         /*
 444          * Scan the trie from the top and find the parent to insert
 445          * the new object.
 446          */
 447         newind = rnode->rn_owner;
 448         clev = vm_radix_keydiff(newind, index);
 449         slot = VM_RADIX_COUNT;
 450         for (rnode = vm_radix_getroot(rtree); ; rnode = tmp) {
 451                 KASSERT(rnode != NULL, ("%s: edge cannot be NULL in the scan",
 452                     __func__));
 453                 KASSERT(clev >= rnode->rn_clev,
 454                     ("%s: unexpected trie depth: clev: %d, rnode->rn_clev: %d",
 455                     __func__, clev, rnode->rn_clev));
 456                 slot = vm_radix_slot(index, rnode->rn_clev);
 457                 tmp = rnode->rn_child[slot];
 458                 KASSERT(tmp != NULL && vm_radix_node_page(tmp) == NULL,
 459                     ("%s: unexpected lookup interruption", __func__));
 460                 if (tmp->rn_clev > clev)
 461                         break;
 462         }
 463         KASSERT(rnode != NULL && tmp != NULL && slot < VM_RADIX_COUNT,
 464             ("%s: invalid scan parameters rnode: %p, tmp: %p, slot: %d",
 465             __func__, (void *)rnode, (void *)tmp, slot));
 466
 467         /*
 468          * A new node is needed because the right insertion level is reached.
 469          * Setup the new intermediate node and add the 2 children: the
 470          * new object and the older edge.
 471          */
 472         tmp2 = vm_radix_node_get(vm_radix_trimkey(index, clev - 1), 2,
 473             clev);
 474         rnode->rn_child[slot] = tmp2;
 475         vm_radix_addpage(tmp2, index, clev, page);
 476         slot = vm_radix_slot(newind, clev);
 477         tmp2->rn_child[slot] = tmp;
 478 }
 479
 480 /*
 481  * Returns the value stored at the index.  If the index is not present,
 482  * NULL is returned.
 483  */
 484 vm_page_t
 485 vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index)
 486 {
 487         struct vm_radix_node *rnode;
 488         vm_page_t m;
 489         int slot;
 490
 491         rnode = vm_radix_getroot(rtree);
 492         while (rnode != NULL) {
 493                 if (vm_radix_keybarr(rnode, index))
 494                         return (NULL);
 495                 slot = vm_radix_slot(index, rnode->rn_clev);
 496                 rnode = rnode->rn_child[slot];
 497                 m = vm_radix_node_page(rnode);
 498                 if (m != NULL) {
 499                         if (m->pindex == index)
 500                                 return (m);
 501                         else
 502                                 return (NULL);
 503                 }
 504         }
 505         return (NULL);
 506 }
 507
 508 /*
 509  * Look up the nearest entry at a position bigger than or equal to index.
 510  */
 511 vm_page_t
 512 vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index)
 513 {
 514         vm_pindex_t inc;
 515         vm_page_t m;
 516         struct vm_radix_node *rnode;
 517         int slot;
 518         uint16_t difflev;
 519         boolean_t maplevels[VM_RADIX_LIMIT + 1];
 520 #ifdef INVARIANTS
 521         int loops = 0;
 522 #endif
 523
 524 restart:
 525         KASSERT(++loops < 1000, ("%s: too many loops", __func__));
 526         for (difflev = 0; difflev < (VM_RADIX_LIMIT + 1); difflev++)
 527                 maplevels[difflev] = FALSE;
 528         rnode = vm_radix_getroot(rtree);
 529         while (rnode != NULL) {
 530                 maplevels[rnode->rn_clev] = TRUE;
 531
 532                 /*
 533                  * If the keys differ before the current bisection node
 534                  * the search key might rollback to the earliest
 535                  * available bisection node, or to the smaller value
 536                  * in the current domain (if the owner is bigger than the
 537                  * search key).
 538                  * The maplevels array records any node has been seen
 539                  * at a given level.  This aids the search for a valid
 540                  * bisection node.
 541                  */
 542                 if (vm_radix_keybarr(rnode, index)) {
 543                         difflev = vm_radix_keydiff(index, rnode->rn_owner);
 544                         if (index > rnode->rn_owner) {
 545                                 if (vm_radix_addlev(&index, maplevels,
 546                                     difflev) > 0)
 547                                         break;
 548                         } else
 549                                 index = vm_radix_trimkey(rnode->rn_owner,
 550                                     difflev);
 551                         goto restart;
 552                 }
 553                 slot = vm_radix_slot(index, rnode->rn_clev);
 554                 m = vm_radix_node_page(rnode->rn_child[slot]);
 555                 if (m != NULL && m->pindex >= index)
 556                         return (m);
 557                 if (rnode->rn_child[slot] != NULL && m == NULL) {
 558                         rnode = rnode->rn_child[slot];
 559                         continue;
 560                 }
 561
 562                 /*
 563                  * Look for an available edge or page within the current
 564                  * bisection node.
 565                  */
 566                 if (slot < (VM_RADIX_COUNT - 1)) {
 567                         inc = VM_RADIX_UNITLEVEL(rnode->rn_clev);
 568                         index = vm_radix_trimkey(index, rnode->rn_clev);
 569                         index += inc;
 570                         slot++;
 571                         for (;; index += inc, slot++) {
 572                                 m = vm_radix_node_page(rnode->rn_child[slot]);
 573                                 if (m != NULL && m->pindex >= index)
 574                                         return (m);
 575                                 if ((rnode->rn_child[slot] != NULL &&
 576                                     m == NULL) || slot == (VM_RADIX_COUNT - 1))
 577                                         break;
 578                         }
 579                 }
 580
 581                 /*
 582                  * If a valid page or edge bigger than the search slot is
 583                  * found in the traversal, skip to the next higher-level key.
 584                  */
 585                 if (slot == (VM_RADIX_COUNT - 1) &&
 586                     (rnode->rn_child[slot] == NULL || m != NULL)) {
 587                         if (rnode->rn_clev == 0  || vm_radix_addlev(&index,
 588                             maplevels, rnode->rn_clev - 1) > 0)
 589                                 break;
 590                         goto restart;
 591                 }
 592                 rnode = rnode->rn_child[slot];
 593         }
 594         return (NULL);
 595 }
 596
 597 /*
 598  * Look up the nearest entry at a position less than or equal to index.
 599  */
 600 vm_page_t
 601 vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index)
 602 {
 603         vm_pindex_t inc;
 604         vm_page_t m;
 605         struct vm_radix_node *rnode;
 606         int slot;
 607         uint16_t difflev;
 608         boolean_t maplevels[VM_RADIX_LIMIT + 1];
 609 #ifdef INVARIANTS
 610         int loops = 0;
 611 #endif
 612
 613 restart:
 614         KASSERT(++loops < 1000, ("%s: too many loops", __func__));
 615         for (difflev = 0; difflev < (VM_RADIX_LIMIT + 1); difflev++)
 616                 maplevels[difflev] = FALSE;
 617         rnode = vm_radix_getroot(rtree);
 618         while (rnode != NULL) {
 619                 maplevels[rnode->rn_clev] = TRUE;
 620
 621                 /*
 622                  * If the keys differ before the current bisection node
 623                  * the search key might rollback to the earliest
 624                  * available bisection node, or to the higher value
 625                  * in the current domain (if the owner is smaller than the
 626                  * search key).
 627                  * The maplevels array records any node has been seen
 628                  * at a given level.  This aids the search for a valid
 629                  * bisection node.
 630                  */
 631                 if (vm_radix_keybarr(rnode, index)) {
 632                         difflev = vm_radix_keydiff(index, rnode->rn_owner);
 633                         if (index > rnode->rn_owner) {
 634                                 index = vm_radix_trimkey(rnode->rn_owner,
 635                                     difflev);
 636                                 index |= VM_RADIX_UNITLEVEL(difflev) - 1;
 637                         } else if (vm_radix_declev(&index, maplevels,
 638                             difflev) > 0)
 639                                 break;
 640                         goto restart;
 641                 }
 642                 slot = vm_radix_slot(index, rnode->rn_clev);
 643                 m = vm_radix_node_page(rnode->rn_child[slot]);
 644                 if (m != NULL && m->pindex <= index)
 645                         return (m);
 646                 if (rnode->rn_child[slot] != NULL && m == NULL) {
 647                         rnode = rnode->rn_child[slot];
 648                         continue;
 649                 }
 650
 651                 /*
 652                  * Look for an available edge or page within the current
 653                  * bisection node.
 654                  */
 655                 if (slot > 0) {
 656                         inc = VM_RADIX_UNITLEVEL(rnode->rn_clev);
 657                         index = vm_radix_trimkey(index, rnode->rn_clev);
 658                         index |= inc - 1;
 659                         index -= inc;
 660                         slot--;
 661                         for (;; index -= inc, slot--) {
 662                                 m = vm_radix_node_page(rnode->rn_child[slot]);
 663                                 if (m != NULL && m->pindex <= index)
 664                                         return (m);
 665                                 if ((rnode->rn_child[slot] != NULL &&
 666                                     m == NULL) || slot == 0)
 667                                         break;
 668                         }
 669                 }
 670
 671                 /*
 672                  * If a valid page or edge smaller than the search slot is
 673                  * found in the traversal, skip to the next higher-level key.
 674                  */
 675                 if (slot == 0 && (rnode->rn_child[slot] == NULL || m != NULL)) {
 676                         if (rnode->rn_clev == 0 || vm_radix_declev(&index,
 677                             maplevels, rnode->rn_clev - 1) > 0)
 678                                 break;
 679                         goto restart;
 680                 }
 681                 rnode = rnode->rn_child[slot];
 682         }
 683         return (NULL);
 684 }
 685
 686 /*
 687  * Remove the specified index from the tree.
 688  * Panics if the key is not present.
 689  */
 690 void
 691 vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index)
 692 {
 693         struct vm_radix_node *rnode, *parent;
 694         vm_page_t m;
 695         int i, slot;
 696
 697         parent = NULL;
 698         rnode = vm_radix_getroot(rtree);
 699         for (;;) {
 700                 if (rnode == NULL)
 701                         panic("vm_radix_remove: impossible to locate the key");
 702                 slot = vm_radix_slot(index, rnode->rn_clev);
 703                 m = vm_radix_node_page(rnode->rn_child[slot]);
 704                 if (m != NULL && m->pindex == index) {
 705                         rnode->rn_child[slot] = NULL;
 706                         rnode->rn_count--;
 707                         if (rnode->rn_count > 1)
 708                                 break;
 709                         if (parent == NULL) {
 710                                 if (rnode->rn_count == 0) {
 711                                         vm_radix_node_put(rnode);
 712                                         vm_radix_setroot(rtree, NULL);
 713                                 }
 714                                 break;
 715                         }
 716                         for (i = 0; i < VM_RADIX_COUNT; i++)
 717                                 if (rnode->rn_child[i] != NULL)
 718                                         break;
 719                         KASSERT(i != VM_RADIX_COUNT,
 720                             ("%s: invalid node configuration", __func__));
 721                         slot = vm_radix_slot(index, parent->rn_clev);
 722                         KASSERT(parent->rn_child[slot] == rnode,
 723                             ("%s: invalid child value", __func__));
 724                         parent->rn_child[slot] = rnode->rn_child[i];
 725                         rnode->rn_count--;
 726                         rnode->rn_child[i] = NULL;
 727                         vm_radix_node_put(rnode);
 728                         break;
 729                 }
 730                 if (m != NULL && m->pindex != index)
 731                         panic("%s: invalid key found", __func__);
 732                 parent = rnode;
 733                 rnode = rnode->rn_child[slot];
 734         }
 735 }
 736
 737 /*
 738  * Remove and free all the nodes from the radix tree.
 739  * This function is recursive but there is a tight control on it as the
 740  * maximum depth of the tree is fixed.
 741  */
 742 void
 743 vm_radix_reclaim_allnodes(struct vm_radix *rtree)
 744 {
 745         struct vm_radix_node *root;
 746
 747         root = vm_radix_getroot(rtree);
 748         if (root == NULL)
 749                 return;
 750         vm_radix_reclaim_allnodes_int(root);
 751         vm_radix_setroot(rtree, NULL);
 752 }
 753
 754 #ifdef DDB
 755 /*
 756  * Show details about the given radix node.
 757  */
 758 DB_SHOW_COMMAND(radixnode, db_show_radixnode)
 759 {
 760         struct vm_radix_node *rnode;
 761         int i;
 762
 763         if (!have_addr)
 764                 return;
 765         rnode = (struct vm_radix_node *)addr;
 766         db_printf("radixnode %p, owner %jx, children count %u, level %u:\n",
 767             (void *)rnode, (uintmax_t)rnode->rn_owner, rnode->rn_count,
 768             rnode->rn_clev);
 769         for (i = 0; i < VM_RADIX_COUNT; i++)
 770                 if (rnode->rn_child[i] != NULL)
 771                         db_printf("slot: %d, val: %p, page: %p, clev: %d\n",
 772                             i, (void *)rnode->rn_child[i],
 773                             (void *)vm_radix_node_page(rnode->rn_child[i]),
 774                             rnode->rn_clev);
 775 }
 776 #endif /* DDB */