vm_radix.c revision 250018
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: head/sys/vm/vm_radix.c 250018 2013-04-28 08:29:00Z alc $"); 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 vm_pindex_t rn_owner; /* Owner of record. */ 98 uint16_t rn_count; /* Valid children. */ 99 uint16_t rn_clev; /* Current level. */ 100 void *rn_child[VM_RADIX_COUNT]; /* Child nodes. */ 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); 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 TRUE if the specified radix node is a leaf and FALSE otherwise. 193 */ 194static __inline boolean_t 195vm_radix_isleaf(struct vm_radix_node *rnode) 196{ 197 198 return (((uintptr_t)rnode & VM_RADIX_ISLEAF) != 0); 199} 200 201/* 202 * Returns the associated page extracted from rnode. 203 */ 204static __inline vm_page_t 205vm_radix_topage(struct vm_radix_node *rnode) 206{ 207 208 return ((vm_page_t)((uintptr_t)rnode & ~VM_RADIX_FLAGS)); 209} 210 211/* 212 * Adds the page as a child of the provided node. 213 */ 214static __inline void 215vm_radix_addpage(struct vm_radix_node *rnode, vm_pindex_t index, uint16_t clev, 216 vm_page_t page) 217{ 218 int slot; 219 220 slot = vm_radix_slot(index, clev); 221 rnode->rn_child[slot] = (void *)((uintptr_t)page | VM_RADIX_ISLEAF); 222} 223 224/* 225 * Returns the slot where two keys differ. 226 * It cannot accept 2 equal keys. 227 */ 228static __inline uint16_t 229vm_radix_keydiff(vm_pindex_t index1, vm_pindex_t index2) 230{ 231 uint16_t clev; 232 233 KASSERT(index1 != index2, ("%s: passing the same key value %jx", 234 __func__, (uintmax_t)index1)); 235 236 index1 ^= index2; 237 for (clev = 0; clev <= VM_RADIX_LIMIT ; clev++) 238 if (vm_radix_slot(index1, clev)) 239 return (clev); 240 panic("%s: cannot reach this point", __func__); 241 return (0); 242} 243 244/* 245 * Returns TRUE if it can be determined that key does not belong to the 246 * specified rnode. Otherwise, returns FALSE. 247 */ 248static __inline boolean_t 249vm_radix_keybarr(struct vm_radix_node *rnode, vm_pindex_t idx) 250{ 251 252 if (rnode->rn_clev > 0) { 253 idx = vm_radix_trimkey(idx, rnode->rn_clev - 1); 254 return (idx != rnode->rn_owner); 255 } 256 return (FALSE); 257} 258 259/* 260 * Adjusts the idx key to the first upper level available, based on a valid 261 * initial level and map of available levels. 262 * Returns a value bigger than 0 to signal that there are not valid levels 263 * available. 264 */ 265static __inline int 266vm_radix_addlev(vm_pindex_t *idx, boolean_t *levels, uint16_t ilev) 267{ 268 269 for (; levels[ilev] == FALSE || 270 vm_radix_slot(*idx, ilev) == (VM_RADIX_COUNT - 1); ilev--) 271 if (ilev == 0) 272 return (1); 273 274 /* 275 * The following computation cannot overflow because *idx's slot at 276 * ilev is less than VM_RADIX_COUNT - 1. 277 */ 278 *idx = vm_radix_trimkey(*idx, ilev); 279 *idx += VM_RADIX_UNITLEVEL(ilev); 280 return (0); 281} 282 283/* 284 * Adjusts the idx key to the first lower level available, based on a valid 285 * initial level and map of available levels. 286 * Returns a value bigger than 0 to signal that there are not valid levels 287 * available. 288 */ 289static __inline int 290vm_radix_declev(vm_pindex_t *idx, boolean_t *levels, uint16_t ilev) 291{ 292 293 for (; levels[ilev] == FALSE || 294 vm_radix_slot(*idx, ilev) == 0; ilev--) 295 if (ilev == 0) 296 return (1); 297 298 /* 299 * The following computation cannot overflow because *idx's slot at 300 * ilev is greater than 0. 301 */ 302 *idx = vm_radix_trimkey(*idx, ilev); 303 *idx -= 1; 304 return (0); 305} 306 307/* 308 * Internal helper for vm_radix_reclaim_allnodes(). 309 * This function is recursive. 310 */ 311static void 312vm_radix_reclaim_allnodes_int(struct vm_radix_node *rnode) 313{ 314 int slot; 315 316 KASSERT(rnode->rn_count <= VM_RADIX_COUNT, 317 ("vm_radix_reclaim_allnodes_int: bad count in rnode %p", rnode)); 318 for (slot = 0; rnode->rn_count != 0; slot++) { 319 if (rnode->rn_child[slot] == NULL) 320 continue; 321 if (!vm_radix_isleaf(rnode->rn_child[slot])) 322 vm_radix_reclaim_allnodes_int(rnode->rn_child[slot]); 323 rnode->rn_child[slot] = NULL; 324 rnode->rn_count--; 325 } 326 vm_radix_node_put(rnode); 327} 328 329#ifdef INVARIANTS 330/* 331 * Radix node zone destructor. 332 */ 333static void 334vm_radix_node_zone_dtor(void *mem, int size __unused, void *arg __unused) 335{ 336 struct vm_radix_node *rnode; 337 int slot; 338 339 rnode = mem; 340 KASSERT(rnode->rn_count == 0, 341 ("vm_radix_node_put: rnode %p has %d children", rnode, 342 rnode->rn_count)); 343 for (slot = 0; slot < VM_RADIX_COUNT; slot++) 344 KASSERT(rnode->rn_child[slot] == NULL, 345 ("vm_radix_node_put: rnode %p has a child", rnode)); 346} 347#endif 348 349/* 350 * Radix node zone initializer. 351 */ 352static int 353vm_radix_node_zone_init(void *mem, int size __unused, int flags __unused) 354{ 355 struct vm_radix_node *rnode; 356 357 rnode = mem; 358 memset(rnode->rn_child, 0, sizeof(rnode->rn_child)); 359 return (0); 360} 361 362/* 363 * Pre-allocate intermediate nodes from the UMA slab zone. 364 */ 365static void 366vm_radix_prealloc(void *arg __unused) 367{ 368 int nodes; 369 370 /* 371 * Calculate the number of reserved nodes, discounting the pages that 372 * are needed to store them. 373 */ 374 nodes = ((vm_paddr_t)cnt.v_page_count * PAGE_SIZE) / (PAGE_SIZE + 375 sizeof(struct vm_radix_node)); 376 if (!uma_zone_reserve_kva(vm_radix_node_zone, nodes)) 377 panic("%s: unable to create new zone", __func__); 378 uma_prealloc(vm_radix_node_zone, nodes); 379} 380SYSINIT(vm_radix_prealloc, SI_SUB_KMEM, SI_ORDER_SECOND, vm_radix_prealloc, 381 NULL); 382 383/* 384 * Initialize the UMA slab zone. 385 * Until vm_radix_prealloc() is called, the zone will be served by the 386 * UMA boot-time pre-allocated pool of pages. 387 */ 388void 389vm_radix_init(void) 390{ 391 392 vm_radix_node_zone = uma_zcreate("RADIX NODE", 393 sizeof(struct vm_radix_node), NULL, 394#ifdef INVARIANTS 395 vm_radix_node_zone_dtor, 396#else 397 NULL, 398#endif 399 vm_radix_node_zone_init, NULL, VM_RADIX_PAD, UMA_ZONE_VM | 400 UMA_ZONE_NOFREE); 401} 402 403/* 404 * Inserts the key-value pair into the trie. 405 * Panics if the key already exists. 406 */ 407void 408vm_radix_insert(struct vm_radix *rtree, vm_page_t page) 409{ 410 vm_pindex_t index, newind; 411 void **parentp; 412 struct vm_radix_node *rnode, *tmp; 413 vm_page_t m; 414 int slot; 415 uint16_t clev; 416 417 index = page->pindex; 418 419 /* 420 * The owner of record for root is not really important because it 421 * will never be used. 422 */ 423 rnode = vm_radix_getroot(rtree); 424 if (rnode == NULL) { 425 rtree->rt_root = (uintptr_t)page | VM_RADIX_ISLEAF; 426 return; 427 } 428 parentp = (void **)&rtree->rt_root; 429 for (;;) { 430 if (vm_radix_isleaf(rnode)) { 431 m = vm_radix_topage(rnode); 432 if (m->pindex == index) 433 panic("%s: key %jx is already present", 434 __func__, (uintmax_t)index); 435 clev = vm_radix_keydiff(m->pindex, index); 436 tmp = vm_radix_node_get(vm_radix_trimkey(index, 437 clev - 1), 2, clev); 438 *parentp = tmp; 439 vm_radix_addpage(tmp, index, clev, page); 440 vm_radix_addpage(tmp, m->pindex, clev, m); 441 return; 442 } else if (vm_radix_keybarr(rnode, index)) 443 break; 444 slot = vm_radix_slot(index, rnode->rn_clev); 445 if (rnode->rn_child[slot] == NULL) { 446 rnode->rn_count++; 447 vm_radix_addpage(rnode, index, rnode->rn_clev, page); 448 return; 449 } 450 parentp = &rnode->rn_child[slot]; 451 rnode = rnode->rn_child[slot]; 452 } 453 454 /* 455 * A new node is needed because the right insertion level is reached. 456 * Setup the new intermediate node and add the 2 children: the 457 * new object and the older edge. 458 */ 459 newind = rnode->rn_owner; 460 clev = vm_radix_keydiff(newind, index); 461 tmp = vm_radix_node_get(vm_radix_trimkey(index, clev - 1), 2, 462 clev); 463 *parentp = tmp; 464 vm_radix_addpage(tmp, index, clev, page); 465 slot = vm_radix_slot(newind, clev); 466 tmp->rn_child[slot] = rnode; 467} 468 469/* 470 * Returns the value stored at the index. If the index is not present, 471 * NULL is returned. 472 */ 473vm_page_t 474vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) 475{ 476 struct vm_radix_node *rnode; 477 vm_page_t m; 478 int slot; 479 480 rnode = vm_radix_getroot(rtree); 481 while (rnode != NULL) { 482 if (vm_radix_isleaf(rnode)) { 483 m = vm_radix_topage(rnode); 484 if (m->pindex == index) 485 return (m); 486 else 487 break; 488 } else if (vm_radix_keybarr(rnode, index)) 489 break; 490 slot = vm_radix_slot(index, rnode->rn_clev); 491 rnode = rnode->rn_child[slot]; 492 } 493 return (NULL); 494} 495 496/* 497 * Look up the nearest entry at a position bigger than or equal to index. 498 */ 499vm_page_t 500vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) 501{ 502 vm_pindex_t inc; 503 vm_page_t m; 504 struct vm_radix_node *child, *rnode; 505 int slot; 506 uint16_t difflev; 507 boolean_t maplevels[VM_RADIX_LIMIT + 1]; 508#ifdef INVARIANTS 509 int loops = 0; 510#endif 511 512 rnode = vm_radix_getroot(rtree); 513 if (rnode == NULL) 514 return (NULL); 515 else if (vm_radix_isleaf(rnode)) { 516 m = vm_radix_topage(rnode); 517 if (m->pindex >= index) 518 return (m); 519 else 520 return (NULL); 521 } 522restart: 523 KASSERT(++loops < 1000, ("%s: too many loops", __func__)); 524 for (difflev = 0; difflev < (VM_RADIX_LIMIT + 1); difflev++) 525 maplevels[difflev] = FALSE; 526 for (;;) { 527 maplevels[rnode->rn_clev] = TRUE; 528 529 /* 530 * If the keys differ before the current bisection node, 531 * then the search key might rollback to the earliest 532 * available bisection node or to the smallest key 533 * in the current node (if the owner is bigger than the 534 * search key). 535 * The maplevels array records any node has been seen 536 * at a given level. This aids the search for a valid 537 * bisection node. 538 */ 539 if (vm_radix_keybarr(rnode, index)) { 540 if (index > rnode->rn_owner) { 541 difflev = vm_radix_keydiff(index, 542 rnode->rn_owner); 543 if (vm_radix_addlev(&index, maplevels, 544 difflev) > 0) 545 break; 546 rnode = vm_radix_getroot(rtree); 547 goto restart; 548 } else 549 index = rnode->rn_owner; 550 } 551 slot = vm_radix_slot(index, rnode->rn_clev); 552 child = rnode->rn_child[slot]; 553 if (vm_radix_isleaf(child)) { 554 m = vm_radix_topage(child); 555 if (m->pindex >= index) 556 return (m); 557 } else if (child != NULL) 558 goto descend; 559 560 /* 561 * Look for an available edge or page within the current 562 * bisection node. 563 */ 564 if (slot < (VM_RADIX_COUNT - 1)) { 565 inc = VM_RADIX_UNITLEVEL(rnode->rn_clev); 566 index = vm_radix_trimkey(index, rnode->rn_clev); 567 do { 568 index += inc; 569 slot++; 570 child = rnode->rn_child[slot]; 571 if (vm_radix_isleaf(child)) { 572 m = vm_radix_topage(child); 573 if (m->pindex >= index) 574 return (m); 575 } else if (child != NULL) 576 goto descend; 577 } while (slot < (VM_RADIX_COUNT - 1)); 578 } 579 KASSERT(child == NULL || vm_radix_isleaf(child), 580 ("vm_radix_lookup_ge: child is radix node")); 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 (rnode->rn_clev == 0 || vm_radix_addlev(&index, maplevels, 587 rnode->rn_clev - 1) > 0) 588 break; 589 rnode = vm_radix_getroot(rtree); 590 goto restart; 591descend: 592 rnode = child; 593 } 594 return (NULL); 595} 596 597/* 598 * Look up the nearest entry at a position less than or equal to index. 599 */ 600vm_page_t 601vm_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 *child, *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 rnode = vm_radix_getroot(rtree); 614 if (rnode == NULL) 615 return (NULL); 616 else if (vm_radix_isleaf(rnode)) { 617 m = vm_radix_topage(rnode); 618 if (m->pindex <= index) 619 return (m); 620 else 621 return (NULL); 622 } 623restart: 624 KASSERT(++loops < 1000, ("%s: too many loops", __func__)); 625 for (difflev = 0; difflev < (VM_RADIX_LIMIT + 1); difflev++) 626 maplevels[difflev] = FALSE; 627 for (;;) { 628 maplevels[rnode->rn_clev] = TRUE; 629 630 /* 631 * If the keys differ before the current bisection node, 632 * then the search key might rollback to the earliest 633 * available bisection node or to the largest key 634 * in the current node (if the owner is smaller than the 635 * search key). 636 * The maplevels array records any node has been seen 637 * at a given level. This aids the search for a valid 638 * bisection node. 639 */ 640 if (vm_radix_keybarr(rnode, index)) { 641 if (index > rnode->rn_owner) { 642 index = rnode->rn_owner + VM_RADIX_COUNT * 643 VM_RADIX_UNITLEVEL(rnode->rn_clev) - 1; 644 } else { 645 difflev = vm_radix_keydiff(index, 646 rnode->rn_owner); 647 if (vm_radix_declev(&index, maplevels, 648 difflev) > 0) 649 break; 650 rnode = vm_radix_getroot(rtree); 651 goto restart; 652 } 653 } 654 slot = vm_radix_slot(index, rnode->rn_clev); 655 child = rnode->rn_child[slot]; 656 if (vm_radix_isleaf(child)) { 657 m = vm_radix_topage(child); 658 if (m->pindex <= index) 659 return (m); 660 } else if (child != NULL) 661 goto descend; 662 663 /* 664 * Look for an available edge or page within the current 665 * bisection node. 666 */ 667 if (slot > 0) { 668 inc = VM_RADIX_UNITLEVEL(rnode->rn_clev); 669 index |= inc - 1; 670 do { 671 index -= inc; 672 slot--; 673 child = rnode->rn_child[slot]; 674 if (vm_radix_isleaf(child)) { 675 m = vm_radix_topage(child); 676 if (m->pindex <= index) 677 return (m); 678 } else if (child != NULL) 679 goto descend; 680 } while (slot > 0); 681 } 682 KASSERT(child == NULL || vm_radix_isleaf(child), 683 ("vm_radix_lookup_le: child is radix node")); 684 685 /* 686 * If a valid page or edge smaller than the search slot is 687 * found in the traversal, skip to the next higher-level key. 688 */ 689 if (rnode->rn_clev == 0 || vm_radix_declev(&index, maplevels, 690 rnode->rn_clev - 1) > 0) 691 break; 692 rnode = vm_radix_getroot(rtree); 693 goto restart; 694descend: 695 rnode = child; 696 } 697 return (NULL); 698} 699 700/* 701 * Remove the specified index from the tree. 702 * Panics if the key is not present. 703 */ 704void 705vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) 706{ 707 struct vm_radix_node *rnode, *parent; 708 vm_page_t m; 709 int i, slot; 710 711 rnode = vm_radix_getroot(rtree); 712 if (vm_radix_isleaf(rnode)) { 713 m = vm_radix_topage(rnode); 714 if (m->pindex != index) 715 panic("%s: invalid key found", __func__); 716 vm_radix_setroot(rtree, NULL); 717 return; 718 } 719 parent = NULL; 720 for (;;) { 721 if (rnode == NULL) 722 panic("vm_radix_remove: impossible to locate the key"); 723 slot = vm_radix_slot(index, rnode->rn_clev); 724 if (vm_radix_isleaf(rnode->rn_child[slot])) { 725 m = vm_radix_topage(rnode->rn_child[slot]); 726 if (m->pindex != index) 727 panic("%s: invalid key found", __func__); 728 rnode->rn_child[slot] = NULL; 729 rnode->rn_count--; 730 if (rnode->rn_count > 1) 731 break; 732 for (i = 0; i < VM_RADIX_COUNT; i++) 733 if (rnode->rn_child[i] != NULL) 734 break; 735 KASSERT(i != VM_RADIX_COUNT, 736 ("%s: invalid node configuration", __func__)); 737 if (parent == NULL) 738 vm_radix_setroot(rtree, rnode->rn_child[i]); 739 else { 740 slot = vm_radix_slot(index, parent->rn_clev); 741 KASSERT(parent->rn_child[slot] == rnode, 742 ("%s: invalid child value", __func__)); 743 parent->rn_child[slot] = rnode->rn_child[i]; 744 } 745 rnode->rn_count--; 746 rnode->rn_child[i] = NULL; 747 vm_radix_node_put(rnode); 748 break; 749 } 750 parent = rnode; 751 rnode = rnode->rn_child[slot]; 752 } 753} 754 755/* 756 * Remove and free all the nodes from the radix tree. 757 * This function is recursive but there is a tight control on it as the 758 * maximum depth of the tree is fixed. 759 */ 760void 761vm_radix_reclaim_allnodes(struct vm_radix *rtree) 762{ 763 struct vm_radix_node *root; 764 765 root = vm_radix_getroot(rtree); 766 if (root == NULL) 767 return; 768 vm_radix_setroot(rtree, NULL); 769 if (!vm_radix_isleaf(root)) 770 vm_radix_reclaim_allnodes_int(root); 771} 772 773#ifdef DDB 774/* 775 * Show details about the given radix node. 776 */ 777DB_SHOW_COMMAND(radixnode, db_show_radixnode) 778{ 779 struct vm_radix_node *rnode; 780 int i; 781 782 if (!have_addr) 783 return; 784 rnode = (struct vm_radix_node *)addr; 785 db_printf("radixnode %p, owner %jx, children count %u, level %u:\n", 786 (void *)rnode, (uintmax_t)rnode->rn_owner, rnode->rn_count, 787 rnode->rn_clev); 788 for (i = 0; i < VM_RADIX_COUNT; i++) 789 if (rnode->rn_child[i] != NULL) 790 db_printf("slot: %d, val: %p, page: %p, clev: %d\n", 791 i, (void *)rnode->rn_child[i], 792 vm_radix_isleaf(rnode->rn_child[i]) ? 793 vm_radix_topage(rnode->rn_child[i]) : NULL, 794 rnode->rn_clev); 795} 796#endif /* DDB */ 797