1/* 2 * Copyright (c) 2011 Jeffrey Roberson <jeff@freebsd.org> 3 * Copyright (c) 2008 Mayur Shardul <mayur.shardul@gmail.com> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 */ 28 29 30/* 31 * Radix tree implementation. 32 */ 33 34#include <sys/cdefs.h> 35 36#include <sys/param.h> 37#include <sys/conf.h> 38#include <sys/systm.h> 39#include <sys/kernel.h> 40#include <sys/malloc.h> 41#include <sys/queue.h> 42#include <sys/param.h> 43#include <sys/lock.h> 44#include <sys/mutex.h> 45#include <sys/ktr.h> 46#include <vm/uma.h> 47#include <vm/vm.h> 48#include <vm/vm_param.h> 49#include <vm/vm_extern.h> 50#include <vm/vm_kern.h> 51#include <vm/vm_page.h> 52#include <vm/vm_radix.h> 53#include <vm/vm_object.h> 54 55#include <sys/kdb.h> 56 57CTASSERT(sizeof(struct vm_radix_node) < PAGE_SIZE); 58 59static uma_zone_t vm_radix_node_zone; 60 61#ifndef UMA_MD_SMALL_ALLOC 62static void * 63vm_radix_node_zone_allocf(uma_zone_t zone, int size, uint8_t *flags, int wait) 64{ 65 vm_offset_t addr; 66 vm_page_t m; 67 int pflags; 68 69 /* Inform UMA that this allocator uses kernel_map. */ 70 *flags = UMA_SLAB_KERNEL; 71 72 pflags = VM_ALLOC_WIRED | VM_ALLOC_NOOBJ; 73 74 /* 75 * As kmem_alloc_nofault() can however fail, let just assume that 76 * M_NOWAIT is on and act accordingly. 77 */ 78 pflags |= ((wait & M_USE_RESERVE) != 0) ? VM_ALLOC_INTERRUPT : 79 VM_ALLOC_SYSTEM; 80 if ((wait & M_ZERO) != 0) 81 pflags |= VM_ALLOC_ZERO; 82 addr = kmem_alloc_nofault(kernel_map, size); 83 if (addr == 0) 84 return (NULL); 85 86 /* Just one page allocation is assumed here. */ 87 m = vm_page_alloc(NULL, OFF_TO_IDX(addr - VM_MIN_KERNEL_ADDRESS), 88 pflags); 89 if (m == NULL) { 90 kmem_free(kernel_map, addr, size); 91 return (NULL); 92 } 93 if ((wait & M_ZERO) != 0 && (m->flags & PG_ZERO) == 0) 94 pmap_zero_page(m); 95 pmap_qenter(addr, &m, 1); 96 return ((void *)addr); 97} 98 99static void 100vm_radix_node_zone_freef(void *item, int size, uint8_t flags) 101{ 102 vm_page_t m; 103 vm_offset_t voitem; 104 105 MPASS((flags & UMA_SLAB_KERNEL) != 0); 106 107 /* Just one page allocation is assumed here. */ 108 voitem = (vm_offset_t)item; 109 m = PHYS_TO_VM_PAGE(pmap_kextract(voitem)); 110 pmap_qremove(voitem, 1); 111 vm_page_free(m); 112 kmem_free(kernel_map, voitem, size); 113} 114 115static void 116init_vm_radix_alloc(void *dummy __unused) 117{ 118 119 uma_zone_set_allocf(vm_radix_node_zone, vm_radix_node_zone_allocf); 120 uma_zone_set_freef(vm_radix_node_zone, vm_radix_node_zone_freef); 121} 122SYSINIT(vm_radix, SI_SUB_KMEM, SI_ORDER_SECOND, init_vm_radix_alloc, NULL); 123#endif 124 125/* 126 * Radix node zone destructor. 127 */ 128#ifdef INVARIANTS 129static void 130vm_radix_node_zone_dtor(void *mem, int size, void *arg) 131{ 132 struct vm_radix_node *rnode; 133 134 rnode = mem; 135 KASSERT(rnode->rn_count == 0, 136 ("vm_radix_node_put: Freeing a node with %d children\n", 137 rnode->rn_count)); 138} 139#endif 140 141/* 142 * Allocate a radix node. Initializes all elements to 0. 143 */ 144static __inline struct vm_radix_node * 145vm_radix_node_get(void) 146{ 147 148 return (uma_zalloc(vm_radix_node_zone, M_NOWAIT | M_ZERO)); 149} 150 151/* 152 * Free radix node. 153 */ 154static __inline void 155vm_radix_node_put(struct vm_radix_node *rnode) 156{ 157 158 uma_zfree(vm_radix_node_zone, rnode); 159} 160 161/* 162 * Return the position in the array for a given level. 163 */ 164static __inline int 165vm_radix_slot(vm_pindex_t index, int level) 166{ 167 168 return ((index >> (level * VM_RADIX_WIDTH)) & VM_RADIX_MASK); 169} 170 171void 172vm_radix_init(void) 173{ 174 175 vm_radix_node_zone = uma_zcreate("RADIX NODE", 176 sizeof(struct vm_radix_node), NULL, 177#ifdef INVARIANTS 178 vm_radix_node_zone_dtor, 179#else 180 NULL, 181#endif 182 NULL, NULL, VM_RADIX_HEIGHT, UMA_ZONE_VM); 183} 184 185/* 186 * Extract the root node and height from a radix tree with a single load. 187 */ 188static __inline int 189vm_radix_height(struct vm_radix *rtree, struct vm_radix_node **rnode) 190{ 191 uintptr_t root; 192 int height; 193 194 root = rtree->rt_root; 195 height = root & VM_RADIX_HEIGHT; 196 *rnode = (struct vm_radix_node *)(root - height); 197 return (height); 198} 199 200 201/* 202 * Set the root node and height for a radix tree. 203 */ 204static inline void 205vm_radix_setroot(struct vm_radix *rtree, struct vm_radix_node *rnode, 206 int height) 207{ 208 uintptr_t root; 209 210 root = (uintptr_t)rnode | height; 211 rtree->rt_root = root; 212} 213 214static inline void * 215vm_radix_match(void *child, int color) 216{ 217 uintptr_t c; 218 219 c = (uintptr_t)child; 220 221 if ((c & color) == 0) 222 return (NULL); 223 return ((void *)(c & ~VM_RADIX_FLAGS)); 224} 225 226static void 227vm_radix_reclaim_allnodes_internal(struct vm_radix_node *rnode, int level) 228{ 229 int slot; 230 231 MPASS(rnode != NULL && level >= 0); 232 233 /* 234 * Level 0 just contains pages as children, thus make it a special 235 * case, free the node and return. 236 */ 237 if (level == 0) { 238 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level); 239 rnode->rn_count = 0; 240 vm_radix_node_put(rnode); 241 return; 242 } 243 for (slot = 0; slot < VM_RADIX_COUNT && rnode->rn_count != 0; slot++) { 244 if (rnode->rn_child[slot] == NULL) 245 continue; 246 CTR3(KTR_VM, 247 "reclaiming: node %p, level %d recursing in slot %d", 248 rnode, level, slot); 249 vm_radix_reclaim_allnodes_internal(rnode->rn_child[slot], 250 level - 1); 251 rnode->rn_count--; 252 } 253 MPASS(rnode->rn_count == 0); 254 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level); 255 vm_radix_node_put(rnode); 256} 257 258/* 259 * Inserts the key-value pair in to the radix tree. Returns errno. 260 * Panics if the key already exists. 261 */ 262int 263vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val) 264{ 265 struct vm_radix_node *rnode; 266 struct vm_radix_node *root; 267 int level; 268 int slot; 269 270 CTR3(KTR_VM, 271 "insert: tree %p, index %ju, val %p", rtree, (uintmax_t)index, val); 272 if (index == -1) 273 panic("vm_radix_insert: -1 is not a valid index.\n"); 274 level = vm_radix_height(rtree, &root); 275 /* 276 * Increase the height by adding nodes at the root until 277 * there is sufficient space. 278 */ 279 while (level == 0 || index > VM_RADIX_MAX(level)) { 280 CTR3(KTR_VM, "insert: expanding %ju > %ju height %d", 281 (uintmax_t)index, (uintmax_t)VM_RADIX_MAX(level), level); 282 level++; 283 KASSERT(level <= VM_RADIX_LIMIT, 284 ("vm_radix_insert: Tree %p height %d too tall", 285 rtree, level)); 286 /* 287 * Only allocate tree nodes if they are needed. 288 */ 289 if (root == NULL || root->rn_count != 0) { 290 rnode = vm_radix_node_get(); 291 if (rnode == NULL) { 292 CTR4(KTR_VM, 293 "insert: tree %p, root %p, index: %ju, level: %d ENOMEM", 294 rtree, root, (uintmax_t)index, level); 295 return (ENOMEM); 296 } 297 /* 298 * Store the new pointer with a memory barrier so 299 * that it is visible before the new root. 300 */ 301 if (root) { 302 atomic_store_rel_ptr((volatile uintptr_t *) 303 &rnode->rn_child[0], (uintptr_t)root); 304 rnode->rn_count = 1; 305 } 306 root = rnode; 307 } 308 vm_radix_setroot(rtree, root, level); 309 } 310 311 /* Now that the tree is tall enough, fill in the path to the index. */ 312 rnode = root; 313 for (level = level - 1; level > 0; level--) { 314 slot = vm_radix_slot(index, level); 315 /* Add the required intermidiate nodes. */ 316 if (rnode->rn_child[slot] == NULL) { 317 rnode->rn_child[slot] = vm_radix_node_get(); 318 if (rnode->rn_child[slot] == NULL) { 319 CTR5(KTR_VM, 320 "insert: tree %p, index %ju, level %d, slot %d, rnode %p ENOMEM", 321 rtree, (uintmax_t)index, level, slot, 322 rnode); 323 CTR4(KTR_VM, 324 "insert: tree %p, rnode %p, child %p, count %u ENOMEM", 325 rtree, rnode, rnode->rn_child[slot], 326 rnode->rn_count); 327 return (ENOMEM); 328 } 329 rnode->rn_count++; 330 } 331 CTR5(KTR_VM, 332 "insert: tree %p, index %ju, level %d, slot %d, rnode %p", 333 rtree, (uintmax_t)index, level, slot, rnode); 334 CTR4(KTR_VM, 335 "insert: tree %p, rnode %p, child %p, count %u", 336 rtree, rnode, rnode->rn_child[slot], rnode->rn_count); 337 rnode = rnode->rn_child[slot]; 338 } 339 340 slot = vm_radix_slot(index, 0); 341 MPASS(rnode != NULL); 342 KASSERT(rnode->rn_child[slot] == NULL, 343 ("vm_radix_insert: Duplicate value %p at index: %lu\n", 344 rnode->rn_child[slot], (u_long)index)); 345 val = (void *)((uintptr_t)val | VM_RADIX_BLACK); 346 rnode->rn_child[slot] = val; 347 atomic_add_32(&rnode->rn_count, 1); 348 CTR6(KTR_VM, 349 "insert: tree %p, index %ju, level %d, slot %d, rnode %p, count %u", 350 rtree, (uintmax_t)index, level, slot, rnode, rnode->rn_count); 351 352 return 0; 353} 354 355/* 356 * Returns the value stored at the index. If the index is not present 357 * NULL is returned. 358 */ 359void * 360vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color) 361{ 362 struct vm_radix_node *rnode; 363 int slot; 364 int level; 365 366 level = vm_radix_height(rtree, &rnode); 367 if (index > VM_RADIX_MAX(level)) 368 return NULL; 369 level--; 370 while (rnode) { 371 slot = vm_radix_slot(index, level); 372 CTR6(KTR_VM, 373 "lookup: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 374 rtree, (uintmax_t)index, level, slot, rnode, 375 rnode->rn_child[slot]); 376 if (level == 0) 377 return vm_radix_match(rnode->rn_child[slot], color); 378 rnode = rnode->rn_child[slot]; 379 level--; 380 } 381 CTR2(KTR_VM, "lookup: tree %p, index %ju failed", rtree, 382 (uintmax_t)index); 383 384 return NULL; 385} 386 387void * 388vm_radix_color(struct vm_radix *rtree, vm_pindex_t index, int color) 389{ 390 struct vm_radix_node *rnode; 391 uintptr_t child; 392 int slot; 393 int level; 394 395 level = vm_radix_height(rtree, &rnode); 396 if (index > VM_RADIX_MAX(level)) 397 return NULL; 398 level--; 399 while (rnode) { 400 slot = vm_radix_slot(index, level); 401 CTR6(KTR_VM, 402 "color: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 403 rtree, (uintmax_t)index, level, slot, rnode, 404 rnode->rn_child[slot]); 405 if (level == 0) 406 break; 407 rnode = rnode->rn_child[slot]; 408 level--; 409 } 410 if (rnode == NULL || rnode->rn_child[slot] == NULL) 411 return (NULL); 412 child = (uintptr_t)rnode->rn_child[slot]; 413 child &= ~VM_RADIX_FLAGS; 414 rnode->rn_child[slot] = (void *)(child | color); 415 416 return (void *)child; 417} 418 419/* 420 * Find the first leaf with a valid node between *startp and end. Return 421 * the index of the first valid item in the leaf in *startp. 422 */ 423static struct vm_radix_node * 424vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp, vm_pindex_t end) 425{ 426 struct vm_radix_node *rnode; 427 vm_pindex_t start; 428 vm_pindex_t inc; 429 int slot; 430 int level; 431 432 start = *startp; 433restart: 434 level = vm_radix_height(rtree, &rnode); 435 if (start > VM_RADIX_MAX(level) || (end && start >= end)) { 436 rnode = NULL; 437 goto out; 438 } 439 /* 440 * Search the tree from the top for any leaf node holding an index 441 * between start and end. 442 */ 443 for (level--; level; level--) { 444 slot = vm_radix_slot(start, level); 445 CTR6(KTR_VM, 446 "leaf: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 447 rtree, (uintmax_t)start, level, slot, rnode, 448 (rnode != NULL) ? rnode->rn_child[slot] : NULL); 449 if (rnode->rn_child[slot] != NULL) { 450 rnode = rnode->rn_child[slot]; 451 continue; 452 } 453 /* 454 * Calculate how much to increment our index by 455 * based on the tree level. We must truncate the 456 * lower bits to start from the begnning of the 457 * next leaf. 458 */ 459 inc = 1LL << (level * VM_RADIX_WIDTH); 460 start &= ~VM_RADIX_MAX(level);
|
486 } 487 if (slot == VM_RADIX_COUNT) 488 goto restart; 489 } 490 491out: 492 *startp = start; 493 return (rnode); 494} 495 496 497 498/* 499 * Looks up as many as cnt values between start and end, and stores 500 * them in the caller allocated array out. The next index can be used 501 * to restart the scan. This optimizes forward scans in the tree. 502 */ 503int 504vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, 505 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next) 506{ 507 struct vm_radix_node *rnode; 508 void *val; 509 int slot; 510 int outidx; 511 512 CTR3(KTR_VM, "lookupn: tree %p, start %ju, end %ju", 513 rtree, (uintmax_t)start, (uintmax_t)end); 514 if (rtree->rt_root == 0) 515 return (0); 516 outidx = 0; 517 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) { 518 slot = vm_radix_slot(start, 0); 519 for (; slot < VM_RADIX_COUNT; slot++, start++) { 520 if (end != 0 && start >= end) 521 goto out; 522 val = vm_radix_match(rnode->rn_child[slot], color); 523 if (val == NULL) 524 continue; 525 CTR4(KTR_VM, 526 "lookupn: tree %p index %ju slot %d found child %p", 527 rtree, (uintmax_t)start, slot, val); 528 out[outidx] = val; 529 if (++outidx == cnt) 530 goto out; 531 } 532 if (end != 0 && start >= end) 533 break; 534 } 535out: 536 *next = start; 537 return (outidx); 538} 539 540void 541vm_radix_foreach(struct vm_radix *rtree, vm_pindex_t start, vm_pindex_t end, 542 int color, void (*iter)(void *)) 543{ 544 struct vm_radix_node *rnode; 545 void *val; 546 int slot; 547 548 if (rtree->rt_root == 0) 549 return; 550 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) { 551 slot = vm_radix_slot(start, 0); 552 for (; slot < VM_RADIX_COUNT; slot++, start++) { 553 if (end != 0 && start >= end) 554 return; 555 val = vm_radix_match(rnode->rn_child[slot], color); 556 if (val) 557 iter(val); 558 } 559 if (end != 0 && start >= end) 560 return; 561 } 562} 563 564 565/* 566 * Look up any entry at a position less than or equal to index. 567 */ 568void * 569vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color) 570{ 571 struct vm_radix_node *rnode; 572 struct vm_radix_node *child; 573 vm_pindex_t max; 574 vm_pindex_t inc; 575 void *val; 576 int slot; 577 int level; 578 579 CTR2(KTR_VM, 580 "lookup_le: tree %p, index %ju", rtree, (uintmax_t)index); 581restart: 582 level = vm_radix_height(rtree, &rnode); 583 if (rnode == NULL) 584 return (NULL); 585 max = VM_RADIX_MAX(level); 586 if (index > max || index == 0) 587 index = max; 588 /* 589 * Search the tree from the top for any leaf node holding an index 590 * lower than 'index'. 591 */ 592 level--; 593 while (rnode) { 594 slot = vm_radix_slot(index, level); 595 CTR6(KTR_VM, 596 "lookup_le: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 597 rtree, (uintmax_t)index, level, slot, rnode, 598 rnode->rn_child[slot]); 599 if (level == 0) 600 break; 601 /* 602 * If we don't have an exact match we must start our search 603 * from the next leaf and adjust our index appropriately. 604 */ 605 if ((child = rnode->rn_child[slot]) == NULL) { 606 /* 607 * Calculate how much to decrement our index by 608 * based on the tree level. We must set the 609 * lower bits to start from the end of the next 610 * leaf. 611 */ 612 inc = 1LL << (level * VM_RADIX_WIDTH); 613 index |= VM_RADIX_MAX(level); 614 index -= inc; 615 slot--; 616 CTR4(KTR_VM, 617 "lookup_le: start %ju inc %ju mask 0x%jX slot %d", 618 (uintmax_t)index, (uintmax_t)inc, 619 (uintmax_t)VM_RADIX_MAX(level), slot); 620 for (; slot >= 0; slot--, index -= inc) { 621 child = rnode->rn_child[slot]; 622 if (child) 623 break; 624 } 625 } 626 rnode = child; 627 level--; 628 } 629 if (rnode) { 630 for (; slot >= 0; slot--, index--) { 631 val = vm_radix_match(rnode->rn_child[slot], color); 632 if (val) 633 return (val); 634 } 635 } 636 if (index != -1) 637 goto restart; 638 return (NULL); 639} 640 641/* 642 * Remove the specified index from the tree. If possible the height of the 643 * tree is adjusted after deletion. The value stored at index is returned 644 * panics if the key is not present. 645 */ 646void * 647vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color) 648{ 649 struct vm_radix_node *stack[VM_RADIX_LIMIT]; 650 struct vm_radix_node *rnode, *root; 651 void *val; 652 int level; 653 int slot; 654 655 level = vm_radix_height(rtree, &root); 656 KASSERT(index <= VM_RADIX_MAX(level), 657 ("vm_radix_remove: %p index %ju out of range %jd.", 658 rtree, (uintmax_t)index, VM_RADIX_MAX(level))); 659 rnode = root; 660 val = NULL; 661 level--; 662 /* 663 * Find the node and record the path in stack. 664 */ 665 while (level && rnode) { 666 stack[level] = rnode; 667 slot = vm_radix_slot(index, level); 668 CTR5(KTR_VM, 669 "remove: tree %p, index %ju, level %d, slot %d, rnode %p", 670 rtree, (uintmax_t)index, level, slot, rnode); 671 CTR4(KTR_VM, "remove: tree %p, rnode %p, child %p, count %u", 672 rtree, rnode, rnode->rn_child[slot], rnode->rn_count); 673 rnode = rnode->rn_child[slot]; 674 level--; 675 } 676 KASSERT(rnode != NULL, 677 ("vm_radix_remove: index %ju not present in the tree.\n", 678 (uintmax_t)index)); 679 slot = vm_radix_slot(index, 0); 680 val = vm_radix_match(rnode->rn_child[slot], color); 681 KASSERT(val != NULL, 682 ("vm_radix_remove: index %ju not present in the tree.\n", 683 (uintmax_t)index)); 684 685 for (;;) { 686 CTR5(KTR_VM, 687 "remove: resetting tree %p, index %ju, level %d, slot %d, rnode %p", 688 rtree, (uintmax_t)index, level, slot, rnode); 689 CTR4(KTR_VM, 690 "remove: resetting tree %p, rnode %p, child %p, count %u", 691 rtree, rnode, 692 (rnode != NULL) ? rnode->rn_child[slot] : NULL, 693 (rnode != NULL) ? rnode->rn_count : 0); 694 rnode->rn_child[slot] = NULL; 695 /* 696 * Use atomics for the last level since red and black 697 * will both adjust it. 698 * Use a write memory barrier here in order to avoid 699 * rn_count reaching 0 before to fetch the actual pointer. 700 * Concurrent black removal, infact, may want to reclaim 701 * the radix node itself before to read it. 702 */ 703 if (level == 0) 704 atomic_add_rel_32(&rnode->rn_count, -1); 705 else 706 rnode->rn_count--; 707 /* 708 * Only allow black removes to prune the tree. 709 */ 710 if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0) 711 break; 712 vm_radix_node_put(rnode); 713 if (rnode == root) { 714 vm_radix_setroot(rtree, NULL, 0); 715 break; 716 } 717 rnode = stack[++level]; 718 slot = vm_radix_slot(index, level); 719 720 } 721 return (val); 722} 723 724/* 725 * Remove and free all the nodes from the radix tree. 726 * This function is recrusive but there is a tight control on it as the 727 * maximum depth of the tree is fixed. 728 */ 729void 730vm_radix_reclaim_allnodes(struct vm_radix *rtree) 731{ 732 struct vm_radix_node *root; 733 int level; 734 735 if (rtree->rt_root == 0) 736 return; 737 level = vm_radix_height(rtree, &root); 738 vm_radix_reclaim_allnodes_internal(root, level - 1); 739 rtree->rt_root = 0; 740} 741 742/* 743 * Attempts to reduce the height of the tree. 744 */ 745void 746vm_radix_shrink(struct vm_radix *rtree) 747{ 748 struct vm_radix_node *tmp, *root; 749 int level; 750 751 if (rtree->rt_root == 0) 752 return; 753 level = vm_radix_height(rtree, &root); 754 755 /* Adjust the height of the tree. */ 756 while (root->rn_count == 1 && root->rn_child[0] != NULL) { 757 tmp = root; 758 root->rn_count--; 759 root = root->rn_child[0]; 760 level--; 761 vm_radix_node_put(tmp); 762 } 763 /* Finally see if we have an empty tree. */ 764 if (root->rn_count == 0) { 765 vm_radix_node_put(root); 766 root = NULL; 767 level--; 768 } 769 vm_radix_setroot(rtree, root, level); 770}
|