244 vm_radix_node_zone = uma_zcreate("RADIX NODE", 245 sizeof(struct vm_radix_node), NULL, 246#ifdef INVARIANTS 247 vm_radix_node_zone_dtor, 248#else 249 NULL, 250#endif 251 NULL, NULL, VM_RADIX_HEIGHT, UMA_ZONE_VM); 252} 253 254/* 255 * Extract the root node and height from a radix tree with a single load. 256 */ 257static __inline int 258vm_radix_height(struct vm_radix *rtree, struct vm_radix_node **rnode) 259{ 260 uintptr_t root; 261 int height; 262 263 root = rtree->rt_root; 264 height = root & VM_RADIX_HEIGHT; 265 *rnode = (struct vm_radix_node *)(root - height); 266 return (height); 267} 268 269 270/* 271 * Set the root node and height for a radix tree. 272 */ 273static inline void 274vm_radix_setroot(struct vm_radix *rtree, struct vm_radix_node *rnode, 275 int height) 276{ 277 uintptr_t root; 278 279 root = (uintptr_t)rnode | height; 280 rtree->rt_root = root; 281} 282 283static inline void 284vm_radix_unwind_heightup(struct vm_radix *rtree, struct vm_radix_node *root, 285 struct vm_radix_node *iroot, int ilevel) 286{ 287 struct vm_radix_node *rnode; 288 289 CTR4(KTR_VM, "unwind: tree %p, root %p, iroot %p, ilevel %d", 290 rtree, root, iroot, ilevel); 291 while (iroot != root && root != NULL) { 292 rnode = root; 293 MPASS(rnode->rn_count == 0 || rnode->rn_count == 1); 294 rnode->rn_count = 0; 295 root = rnode->rn_child[0]; 296 vm_radix_node_put(rnode); 297 } 298 vm_radix_setroot(rtree, iroot, ilevel); 299} 300 301static inline void * 302vm_radix_match(void *child, int color) 303{ 304 uintptr_t c; 305 306 c = (uintptr_t)child; 307 308 if ((c & color) == 0) 309 return (NULL); 310 return ((void *)(c & ~VM_RADIX_FLAGS)); 311} 312 313static void 314vm_radix_reclaim_allnodes_internal(struct vm_radix_node *rnode, int level) 315{ 316 int slot; 317 318 MPASS(rnode != NULL && level >= 0); 319 320 /* 321 * Level 0 just contains pages as children, thus make it a special 322 * case, free the node and return. 323 */ 324 if (level == 0) { 325 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level); 326 rnode->rn_count = 0; 327 vm_radix_node_put(rnode); 328 return; 329 } 330 for (slot = 0; slot < VM_RADIX_COUNT && rnode->rn_count != 0; slot++) { 331 if (rnode->rn_child[slot] == NULL) 332 continue; 333 CTR3(KTR_VM, 334 "reclaiming: node %p, level %d recursing in slot %d", 335 rnode, level, slot); 336 vm_radix_reclaim_allnodes_internal(rnode->rn_child[slot], 337 level - 1); 338 rnode->rn_count--; 339 } 340 MPASS(rnode->rn_count == 0); 341 CTR2(KTR_VM, "reclaiming: node %p, level %d", rnode, level); 342 vm_radix_node_put(rnode); 343} 344 345/* 346 * Inserts the key-value pair in to the radix tree. Returns errno. 347 * Panics if the key already exists. 348 */ 349int 350vm_radix_insert(struct vm_radix *rtree, vm_pindex_t index, void *val) 351{ 352 struct vm_radix_node *iroot, *rnode, *root; 353 u_int allocmsk; 354 int clev, ilevel, level, slot; 355 356 CTR3(KTR_VM, 357 "insert: tree %p, index %ju, val %p", rtree, (uintmax_t)index, val); 358 if (index == -1) 359 panic("vm_radix_insert: -1 is not a valid index.\n"); 360 level = vm_radix_height(rtree, &root); 361 /* 362 * Increase the height by adding nodes at the root until 363 * there is sufficient space. 364 */ 365 ilevel = level; 366 iroot = root; 367 while (level == 0 || index > VM_RADIX_MAX(level)) { 368 CTR3(KTR_VM, "insert: expanding %ju > %ju height %d", 369 (uintmax_t)index, (uintmax_t)VM_RADIX_MAX(level), level); 370 level++; 371 KASSERT(level <= VM_RADIX_LIMIT, 372 ("vm_radix_insert: Tree %p height %d too tall", 373 rtree, level)); 374 /* 375 * Only allocate tree nodes if they are needed. 376 */ 377 if (root == NULL || root->rn_count != 0) { 378 rnode = vm_radix_node_get(); 379 if (rnode == NULL) { 380 CTR4(KTR_VM, 381 "insert: tree %p, root %p, index: %ju, level: %d ENOMEM", 382 rtree, root, (uintmax_t)index, level); 383 vm_radix_unwind_heightup(rtree, root, iroot, 384 ilevel); 385 return (ENOMEM); 386 } 387 /* 388 * Store the new pointer with a memory barrier so 389 * that it is visible before the new root. 390 */ 391 if (root) { 392 atomic_store_rel_ptr((volatile uintptr_t *) 393 &rnode->rn_child[0], (uintptr_t)root); 394 rnode->rn_count = 1; 395 } 396 root = rnode; 397 } 398 vm_radix_setroot(rtree, root, level); 399 } 400 401 /* Now that the tree is tall enough, fill in the path to the index. */ 402 allocmsk = 0; 403 clev = level; 404 rnode = root; 405 for (level = level - 1; level > 0; level--) { 406 slot = vm_radix_slot(index, level); 407 /* Add the required intermidiate nodes. */ 408 if (rnode->rn_child[slot] == NULL) { 409 rnode->rn_child[slot] = vm_radix_node_get(); 410 if (rnode->rn_child[slot] == NULL) { 411 CTR5(KTR_VM, 412 "insert: tree %p, index %ju, level %d, slot %d, rnode %p ENOMEM", 413 rtree, (uintmax_t)index, level, slot, 414 rnode); 415 CTR4(KTR_VM, 416 "insert: tree %p, rnode %p, child %p, count %u ENOMEM", 417 rtree, rnode, rnode->rn_child[slot], 418 rnode->rn_count); 419 MPASS(level != clev || allocmsk == 0); 420 while (allocmsk != 0) { 421 rnode = root; 422 level = clev; 423 level--; 424 slot = vm_radix_slot(index, level); 425 CTR4(KTR_VM, 426 "insert: unwind root %p, level %d, slot %d, allocmsk: 0x%x", 427 root, level, slot, allocmsk); 428 MPASS(level >= (ffs(allocmsk) - 1)); 429 while (level > (ffs(allocmsk) - 1)) { 430 MPASS(level > 0); 431 slot = vm_radix_slot(index, 432 level); 433 rnode = rnode->rn_child[slot]; 434 level--; 435 } 436 MPASS((allocmsk & (1 << level)) != 0); 437 allocmsk &= ~(1 << level); 438 rnode->rn_count--; 439 vm_radix_node_put(rnode->rn_child[slot]); 440 rnode->rn_child[slot] = NULL; 441 } 442 vm_radix_unwind_heightup(rtree, root, iroot, 443 ilevel); 444 return (ENOMEM); 445 } 446 rnode->rn_count++; 447 allocmsk |= (1 << level); 448 } 449 CTR5(KTR_VM, 450 "insert: tree %p, index %ju, level %d, slot %d, rnode %p", 451 rtree, (uintmax_t)index, level, slot, rnode); 452 CTR4(KTR_VM, 453 "insert: tree %p, rnode %p, child %p, count %u", 454 rtree, rnode, rnode->rn_child[slot], rnode->rn_count); 455 rnode = rnode->rn_child[slot]; 456 } 457 458 slot = vm_radix_slot(index, 0); 459 MPASS(rnode != NULL); 460 KASSERT(rnode->rn_child[slot] == NULL, 461 ("vm_radix_insert: Duplicate value %p at index: %lu\n", 462 rnode->rn_child[slot], (u_long)index)); 463 val = (void *)((uintptr_t)val | VM_RADIX_BLACK); 464 rnode->rn_child[slot] = val; 465 atomic_add_32(&rnode->rn_count, 1); 466 CTR6(KTR_VM, 467 "insert: tree %p, index %ju, level %d, slot %d, rnode %p, count %u", 468 rtree, (uintmax_t)index, level, slot, rnode, rnode->rn_count); 469 470 return 0; 471} 472 473/* 474 * Returns the value stored at the index. If the index is not present 475 * NULL is returned. 476 */ 477void * 478vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, int color) 479{ 480 struct vm_radix_node *rnode; 481 int slot; 482 int level; 483 484 level = vm_radix_height(rtree, &rnode); 485 if (index > VM_RADIX_MAX(level)) 486 return NULL; 487 level--; 488 while (rnode) { 489 slot = vm_radix_slot(index, level); 490 CTR6(KTR_VM, 491 "lookup: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 492 rtree, (uintmax_t)index, level, slot, rnode, 493 rnode->rn_child[slot]); 494 if (level == 0) 495 return vm_radix_match(rnode->rn_child[slot], color); 496 rnode = rnode->rn_child[slot]; 497 level--; 498 } 499 CTR2(KTR_VM, "lookup: tree %p, index %ju failed", rtree, 500 (uintmax_t)index); 501 502 return NULL; 503} 504 505void * 506vm_radix_color(struct vm_radix *rtree, vm_pindex_t index, int color) 507{ 508 struct vm_radix_node *rnode; 509 uintptr_t child; 510 int slot; 511 int level; 512 513 level = vm_radix_height(rtree, &rnode); 514 if (index > VM_RADIX_MAX(level)) 515 return NULL; 516 level--; 517 while (rnode) { 518 slot = vm_radix_slot(index, level); 519 CTR6(KTR_VM, 520 "color: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 521 rtree, (uintmax_t)index, level, slot, rnode, 522 rnode->rn_child[slot]); 523 if (level == 0) 524 break; 525 rnode = rnode->rn_child[slot]; 526 level--; 527 } 528 if (rnode == NULL || rnode->rn_child[slot] == NULL) 529 return (NULL); 530 child = (uintptr_t)rnode->rn_child[slot]; 531 child &= ~VM_RADIX_FLAGS; 532 rnode->rn_child[slot] = (void *)(child | color); 533 534 return (void *)child; 535} 536 537/* 538 * Find the first leaf with a valid node between *startp and end. Return 539 * the index of the first valid item in the leaf in *startp. 540 */ 541static struct vm_radix_node * 542vm_radix_leaf(struct vm_radix *rtree, vm_pindex_t *startp, vm_pindex_t end) 543{ 544 struct vm_radix_node *rnode; 545 vm_pindex_t start; 546 vm_pindex_t inc; 547 int slot; 548 int level; 549 550 start = *startp; 551restart: 552 level = vm_radix_height(rtree, &rnode); 553 if (start > VM_RADIX_MAX(level) || (end && start >= end)) { 554 rnode = NULL; 555 goto out; 556 } 557 /* 558 * Search the tree from the top for any leaf node holding an index 559 * between start and end. 560 */ 561 for (level--; level; level--) { 562 slot = vm_radix_slot(start, level); 563 CTR6(KTR_VM, 564 "leaf: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 565 rtree, (uintmax_t)start, level, slot, rnode, 566 (rnode != NULL) ? rnode->rn_child[slot] : NULL); 567 if (rnode->rn_child[slot] != NULL) { 568 rnode = rnode->rn_child[slot]; 569 continue; 570 } 571 /* 572 * Calculate how much to increment our index by 573 * based on the tree level. We must truncate the 574 * lower bits to start from the begnning of the 575 * next leaf. 576 */ 577 inc = 1LL << (level * VM_RADIX_WIDTH); 578 start &= ~VM_RADIX_MAX(level); 579 580 /* Avoid start address wrapping up. */ 581 if ((VM_RADIX_MAXVAL - start) < inc) { 582 rnode = NULL; 583 goto out; 584 } 585 start += inc; 586 slot++; 587 CTR5(KTR_VM, 588 "leaf: start %ju end %ju inc %ju mask 0x%jX slot %d", 589 (uintmax_t)start, (uintmax_t)end, (uintmax_t)inc, 590 (uintmax_t)~VM_RADIX_MAX(level), slot); 591 for (; slot < VM_RADIX_COUNT; slot++, start += inc) { 592 if (end != 0 && start >= end) { 593 rnode = NULL; 594 goto out; 595 } 596 if (rnode->rn_child[slot]) { 597 rnode = rnode->rn_child[slot]; 598 break; 599 } 600 if ((VM_RADIX_MAXVAL - start) < inc) { 601 rnode = NULL; 602 goto out; 603 } 604 } 605 if (slot == VM_RADIX_COUNT) 606 goto restart; 607 } 608 609out: 610 *startp = start; 611 return (rnode); 612} 613 614 615 616/* 617 * Looks up as many as cnt values between start and end, and stores 618 * them in the caller allocated array out. The next index can be used 619 * to restart the scan. This optimizes forward scans in the tree. 620 */ 621int 622vm_radix_lookupn(struct vm_radix *rtree, vm_pindex_t start, 623 vm_pindex_t end, int color, void **out, int cnt, vm_pindex_t *next) 624{ 625 struct vm_radix_node *rnode; 626 void *val; 627 int slot; 628 int outidx; 629 630 CTR3(KTR_VM, "lookupn: tree %p, start %ju, end %ju", 631 rtree, (uintmax_t)start, (uintmax_t)end); 632 if (rtree->rt_root == 0) 633 return (0); 634 outidx = 0; 635 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) { 636 slot = vm_radix_slot(start, 0); 637 for (; slot < VM_RADIX_COUNT; slot++, start++) { 638 if (end != 0 && start >= end) 639 goto out; 640 val = vm_radix_match(rnode->rn_child[slot], color); 641 if (val == NULL) 642 continue; 643 CTR4(KTR_VM, 644 "lookupn: tree %p index %ju slot %d found child %p", 645 rtree, (uintmax_t)start, slot, val); 646 out[outidx] = val; 647 if (++outidx == cnt) 648 goto out; 649 } 650 if (end != 0 && start >= end) 651 break; 652 } 653out: 654 *next = start; 655 return (outidx); 656} 657 658void 659vm_radix_foreach(struct vm_radix *rtree, vm_pindex_t start, vm_pindex_t end, 660 int color, void (*iter)(void *)) 661{ 662 struct vm_radix_node *rnode; 663 void *val; 664 int slot; 665 666 if (rtree->rt_root == 0) 667 return; 668 while ((rnode = vm_radix_leaf(rtree, &start, end)) != NULL) { 669 slot = vm_radix_slot(start, 0); 670 for (; slot < VM_RADIX_COUNT; slot++, start++) { 671 if (end != 0 && start >= end) 672 return; 673 val = vm_radix_match(rnode->rn_child[slot], color); 674 if (val) 675 iter(val); 676 } 677 if (end != 0 && start >= end) 678 return; 679 } 680} 681 682 683/* 684 * Look up any entry at a position less than or equal to index. 685 */ 686void * 687vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index, int color) 688{ 689 struct vm_radix_node *rnode; 690 struct vm_radix_node *child; 691 vm_pindex_t max; 692 vm_pindex_t inc; 693 void *val; 694 int slot; 695 int level; 696 697 CTR2(KTR_VM, 698 "lookup_le: tree %p, index %ju", rtree, (uintmax_t)index); 699restart: 700 level = vm_radix_height(rtree, &rnode); 701 if (rnode == NULL) 702 return (NULL); 703 max = VM_RADIX_MAX(level); 704 if (index > max || index == 0) 705 index = max; 706 /* 707 * Search the tree from the top for any leaf node holding an index 708 * lower than 'index'. 709 */ 710 level--; 711 while (rnode) { 712 slot = vm_radix_slot(index, level); 713 CTR6(KTR_VM, 714 "lookup_le: tree %p, index %ju, level %d, slot %d, rnode %p, child %p", 715 rtree, (uintmax_t)index, level, slot, rnode, 716 rnode->rn_child[slot]); 717 if (level == 0) 718 break; 719 /* 720 * If we don't have an exact match we must start our search 721 * from the next leaf and adjust our index appropriately. 722 */ 723 if ((child = rnode->rn_child[slot]) == NULL) { 724 /* 725 * Calculate how much to decrement our index by 726 * based on the tree level. We must set the 727 * lower bits to start from the end of the next 728 * leaf. 729 */ 730 inc = 1LL << (level * VM_RADIX_WIDTH); 731 index |= VM_RADIX_MAX(level); 732 index -= inc; 733 slot--; 734 CTR4(KTR_VM, 735 "lookup_le: start %ju inc %ju mask 0x%jX slot %d", 736 (uintmax_t)index, (uintmax_t)inc, 737 (uintmax_t)VM_RADIX_MAX(level), slot); 738 for (; slot >= 0; slot--, index -= inc) { 739 child = rnode->rn_child[slot]; 740 if (child) 741 break; 742 } 743 } 744 rnode = child; 745 level--; 746 } 747 if (rnode) { 748 for (; slot >= 0; slot--, index--) { 749 val = vm_radix_match(rnode->rn_child[slot], color); 750 if (val) 751 return (val); 752 } 753 } 754 if (index != -1) 755 goto restart; 756 return (NULL); 757} 758 759/* 760 * Remove the specified index from the tree. If possible the height of the 761 * tree is adjusted after deletion. The value stored at index is returned 762 * panics if the key is not present. 763 */ 764void * 765vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index, int color) 766{ 767 struct vm_radix_node *stack[VM_RADIX_LIMIT]; 768 struct vm_radix_node *rnode, *root; 769 void *val; 770 int level; 771 int slot; 772 773 level = vm_radix_height(rtree, &root); 774 KASSERT(index <= VM_RADIX_MAX(level), 775 ("vm_radix_remove: %p index %ju out of range %jd.", 776 rtree, (uintmax_t)index, VM_RADIX_MAX(level))); 777 rnode = root; 778 val = NULL; 779 level--; 780 /* 781 * Find the node and record the path in stack. 782 */ 783 while (level && rnode) { 784 stack[level] = rnode; 785 slot = vm_radix_slot(index, level); 786 CTR5(KTR_VM, 787 "remove: tree %p, index %ju, level %d, slot %d, rnode %p", 788 rtree, (uintmax_t)index, level, slot, rnode); 789 CTR4(KTR_VM, "remove: tree %p, rnode %p, child %p, count %u", 790 rtree, rnode, rnode->rn_child[slot], rnode->rn_count); 791 rnode = rnode->rn_child[slot]; 792 level--; 793 } 794 KASSERT(rnode != NULL, 795 ("vm_radix_remove: index %ju not present in the tree.\n", 796 (uintmax_t)index)); 797 slot = vm_radix_slot(index, 0); 798 val = vm_radix_match(rnode->rn_child[slot], color); 799 KASSERT(val != NULL, 800 ("vm_radix_remove: index %ju not present in the tree.\n", 801 (uintmax_t)index)); 802 803 for (;;) { 804 CTR5(KTR_VM, 805 "remove: resetting tree %p, index %ju, level %d, slot %d, rnode %p", 806 rtree, (uintmax_t)index, level, slot, rnode); 807 CTR4(KTR_VM, 808 "remove: resetting tree %p, rnode %p, child %p, count %u", 809 rtree, rnode, 810 (rnode != NULL) ? rnode->rn_child[slot] : NULL, 811 (rnode != NULL) ? rnode->rn_count : 0); 812 rnode->rn_child[slot] = NULL; 813 /* 814 * Use atomics for the last level since red and black 815 * will both adjust it. 816 * Use a write memory barrier here in order to avoid 817 * rn_count reaching 0 before to fetch the actual pointer. 818 * Concurrent black removal, infact, may want to reclaim 819 * the radix node itself before to read it. 820 */ 821 if (level == 0) 822 atomic_add_rel_32(&rnode->rn_count, -1); 823 else 824 rnode->rn_count--; 825 /* 826 * Only allow black removes to prune the tree. 827 */ 828 if ((color & VM_RADIX_BLACK) == 0 || rnode->rn_count > 0) 829 break; 830 vm_radix_node_put(rnode); 831 if (rnode == root) { 832 vm_radix_setroot(rtree, NULL, 0); 833 break; 834 } 835 rnode = stack[++level]; 836 slot = vm_radix_slot(index, level); 837 838 } 839 return (val); 840} 841 842/* 843 * Remove and free all the nodes from the radix tree. 844 * This function is recrusive but there is a tight control on it as the 845 * maximum depth of the tree is fixed. 846 */ 847void 848vm_radix_reclaim_allnodes(struct vm_radix *rtree) 849{ 850 struct vm_radix_node *root; 851 int level; 852 853 if (rtree->rt_root == 0) 854 return; 855 level = vm_radix_height(rtree, &root); 856 vm_radix_reclaim_allnodes_internal(root, level - 1); 857 rtree->rt_root = 0; 858} 859 860#ifdef notyet 861/* 862 * Attempts to reduce the height of the tree. 863 */ 864void 865vm_radix_shrink(struct vm_radix *rtree) 866{ 867 struct vm_radix_node *tmp, *root; 868 int level; 869 870 if (rtree->rt_root == 0) 871 return; 872 level = vm_radix_height(rtree, &root); 873 874 /* Adjust the height of the tree. */ 875 while (root->rn_count == 1 && root->rn_child[0] != NULL) { 876 tmp = root; 877 root->rn_count--; 878 root = root->rn_child[0]; 879 level--; 880 vm_radix_node_put(tmp); 881 } 882 /* Finally see if we have an empty tree. */ 883 if (root->rn_count == 0) { 884 vm_radix_node_put(root); 885 root = NULL; 886 level--; 887 } 888 vm_radix_setroot(rtree, root, level); 889} 890#endif
|