* BLST_LEAF_ALLOC() - allocate at a leaf in the radix tree (a bitmap). * * This function is the core of the allocator. Its execution time is * proportional to log(count), plus height of the tree if the allocation * crosses a leaf boundary. */
| 689 | * crosses a leaf boundary. |
| 690 | */ |
| 691 | static daddr_t |
| 692 | blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int *count, int maxcount) |
| 693 | { |
| 694 | u_daddr_t mask; |
| 695 | int bighint, count1, hi, lo, num_shifts; |
| 696 | |
| 697 | count1 = *count - 1; |
| 698 | num_shifts = fls(count1); |
| 699 | mask = ~scan->bm_bitmap; |
| 700 | while ((mask & (mask + 1)) != 0 && num_shifts > 0) { |
| 701 | /* |
| 702 | * If bit i is 0 in mask, then bits in [i, i + (count1 >> |
| 703 | * num_shifts)] are 1 in scan->bm_bitmap. Reduce num_shifts to |
| 704 | * 0, while preserving this invariant. The updates to mask |
| 705 | * leave fewer bits 0, but each bit that remains 0 represents a |
| 706 | * longer string of consecutive 1-bits in scan->bm_bitmap. If |
| 707 | * more updates to mask cannot set more bits, because mask is |
| 708 | * partitioned with all 1 bits following all 0 bits, the loop |
| 709 | * terminates immediately. |
| 710 | */ |
| 711 | num_shifts--; |
| 712 | mask |= mask >> ((count1 >> num_shifts) + 1) / 2; |
| 713 | } |
| 714 | bighint = count1 >> num_shifts; |
| 715 | if (~mask == 0) { |
| 716 | /* |
| 717 | * Update bighint. There is no allocation bigger than |
| 718 | * count1 >> num_shifts starting in this leaf. |
| 719 | */ |
| 720 | scan->bm_bighint = bighint; |
| 721 | return (SWAPBLK_NONE); |
| 722 | } |
| 723 | |
| 724 | /* Discard any candidates that appear before blk. */ |
| 725 | if ((blk & BLIST_MASK) != 0) { |
| 726 | if ((~mask & bitrange(0, blk & BLIST_MASK)) != 0) { |
| 727 | /* Grow bighint in case all discarded bits are set. */ |
| 728 | bighint += blk & BLIST_MASK; |
| 729 | mask |= bitrange(0, blk & BLIST_MASK); |
| 730 | if (~mask == 0) { |
| 731 | scan->bm_bighint = bighint; |
| 732 | return (SWAPBLK_NONE); |
| 733 | } |
| 734 | } |
| 735 | blk -= blk & BLIST_MASK; |
| 736 | } |
| 737 | |
| 738 | /* |
| 739 | * The least significant set bit in mask marks the start of the first |
| 740 | * available range of sufficient size. Find its position. |
| 741 | */ |
| 742 | lo = bitpos(~mask); |
| 743 | |
| 744 | /* |
| 745 | * Find how much space is available starting at that position. |
| 746 | */ |
| 747 | if ((mask & (mask + 1)) != 0) { |
| 748 | /* Count the 1 bits starting at position lo. */ |
no test coverage detected