* blist_meta_alloc() - allocate at a meta in the radix tree. * * Attempt to allocate at a meta node. If we can't, we update * bighint and return a failure. Updating bighint optimize future * calls that hit this node. We have to check for our collapse cases * and we have a few optimizations strewn in as well. */
| 791 | * and we have a few optimizations strewn in as well. |
| 792 | */ |
| 793 | static daddr_t |
| 794 | blst_meta_alloc(blmeta_t *scan, daddr_t cursor, int *count, |
| 795 | int maxcount, u_daddr_t radix) |
| 796 | { |
| 797 | daddr_t blk, i, r, skip; |
| 798 | u_daddr_t mask; |
| 799 | bool scan_from_start; |
| 800 | int digit; |
| 801 | |
| 802 | if (radix == 1) |
| 803 | return (blst_leaf_alloc(scan, cursor, count, maxcount)); |
| 804 | blk = cursor & -(radix * BLIST_RADIX); |
| 805 | scan_from_start = (cursor == blk); |
| 806 | skip = radix_to_skip(radix); |
| 807 | mask = scan->bm_bitmap; |
| 808 | |
| 809 | /* Discard any candidates that appear before cursor. */ |
| 810 | digit = (cursor / radix) & BLIST_MASK; |
| 811 | mask &= (u_daddr_t)-1 << digit; |
| 812 | if (mask == 0) |
| 813 | return (SWAPBLK_NONE); |
| 814 | |
| 815 | /* |
| 816 | * If the first try is for a block that includes the cursor, pre-undo |
| 817 | * the digit * radix offset in the first call; otherwise, ignore the |
| 818 | * cursor entirely. |
| 819 | */ |
| 820 | if (((mask >> digit) & 1) == 1) |
| 821 | cursor -= digit * radix; |
| 822 | else |
| 823 | cursor = blk; |
| 824 | |
| 825 | /* |
| 826 | * Examine the nonempty subtree associated with each bit set in mask. |
| 827 | */ |
| 828 | do { |
| 829 | digit = bitpos(mask); |
| 830 | i = 1 + digit * skip; |
| 831 | if (*count <= scan[i].bm_bighint) { |
| 832 | /* |
| 833 | * The allocation might fit beginning in the i'th subtree. |
| 834 | */ |
| 835 | r = blst_meta_alloc(&scan[i], cursor + digit * radix, |
| 836 | count, maxcount, radix / BLIST_RADIX); |
| 837 | if (r != SWAPBLK_NONE) { |
| 838 | if (scan[i].bm_bitmap == 0) |
| 839 | scan->bm_bitmap ^= bitrange(digit, 1); |
| 840 | return (r); |
| 841 | } |
| 842 | } |
| 843 | cursor = blk; |
| 844 | } while ((mask ^= bitrange(digit, 1)) != 0); |
| 845 | |
| 846 | /* |
| 847 | * We couldn't allocate count in this subtree. If the whole tree was |
| 848 | * scanned, and the last tree node is allocated, update bighint. |
| 849 | */ |
| 850 | if (scan_from_start && !(digit == BLIST_RADIX - 1 && |
no test coverage detected