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