sys/kern/subr_blist.c

30  * BLIST.C -	Bitmap allocator/deallocator, using a radix tree with hinting
37  *	A radix tree controls access to pieces of the bitmap, and includes
39  *	contiguous free blocks in the subtree rooted at that node.  A radix
55  *	the general radix structure optimizes both allocations and frees.  The
56  *	radix tree should be able to operate well no matter how much
64  *	LAYOUT: The radix tree is laid out recursively using a linear array.
77  *	radix is large enough that this restriction does not effect the swap
133     int maxcount, u_daddr_t radix);
136 		    u_daddr_t radix);
137 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
141 		    u_daddr_t radix);
143 static void	blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
154  * For a subtree that can represent the state of up to 'radix' blocks, the
155  * number of leaf nodes of the subtree is L=radix/BLIST_RADIX.  If 'm'
162  * skip = (m * (radix / m)) / (m - 1)
163  * skip = radix / (m - 1)
168 radix_to_skip(daddr_t radix)
171 	return (radix / BLIST_MASK);
208 	u_daddr_t nodes, radix;
213 	 * Calculate the radix and node count used for scanning.
216 	for (radix = 1; (blocks - 1) / BLIST_RADIX / radix > 0;
217 	    radix *= BLIST_RADIX)
218 		nodes += 1 + (blocks - 1) / BLIST_RADIX / radix;
233 	bl->bl_radix = radix;
243 	printf("BLIST raw radix tree contains %lld records\n",
338  * blist_resize() -	resize an existing radix tree to handle the
367  * blist_print()    - dump radix tree
505  * blist_stats()    - dump radix tree stats
512 	daddr_t i, nodes, radix;
518 	radix = bl->bl_radix;
523 		while (radix != 1) {
534 			radix /= BLIST_RADIX;
536 		if (radix == 1) {
550 		nodes += radix_to_skip(radix * BLIST_RADIX);
551 		i += radix * BLIST_RADIX;
556 		for (radix = 1;
557 		    ((i / BLIST_RADIX / radix) & BLIST_MASK) == 0;
558 		    radix *= BLIST_RADIX)
589 	u_daddr_t radix;
596 		radix = BLIST_RADIX;
598 		    ((blk / radix) & BLIST_MASK) == 0)
599 			radix *= BLIST_RADIX;
623 					radix /= BLIST_RADIX;
625 				} while (radix != 1);
643 		for (radix = BLIST_RADIX;
644 		    (digit = ((blk / radix) & BLIST_MASK)) == 0;
645 		    radix *= BLIST_RADIX) {
650 			scan[-digit * radix_to_skip(radix)].bm_bitmap ^=
662  * BLST_LEAF_ALLOC() -	allocate at a leaf in the radix tree (a bitmap).
763  * blist_meta_alloc() -	allocate at a meta in the radix tree.
772     int maxcount, u_daddr_t radix)
779 	if (radix == 1)
781 	blk = cursor & -(radix * BLIST_RADIX);
783 	skip = radix_to_skip(radix);
787 	digit = (cursor / radix) & BLIST_MASK;
794 	 * the digit * radix offset in the first call; otherwise, ignore the
798 		cursor -= digit * radix;
812 			r = blst_meta_alloc(&scan[i], cursor + digit * radix,
813 			    count, maxcount, radix / BLIST_RADIX);
857  * BLST_META_FREE() - free allocated blocks from radix tree meta info
860  *	The range must be entirely enclosed by this radix node.  If a
867 blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, u_daddr_t radix)
880 	if (radix == 1)
884 	blk = (freeBlk + radix * BLIST_RADIX) & -(radix * BLIST_RADIX);
891 	skip = radix_to_skip(radix);
892 	blk = freeBlk & -radix;
893 	digit = (blk / radix) & BLIST_MASK;
894 	endDigit = 1 + (((endBlk - 1) / radix) & BLIST_MASK);
897 		blk += radix;
899 		blst_meta_free(&scan[i], freeBlk, count, radix / BLIST_RADIX);
905  * BLST_COPY() - copy one radix tree to another
911 blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, blist_t dest,
920 	if (radix == 1) {
948 	skip = radix_to_skip(radix);
950 		blk += radix;
951 		count = radix;
954 		blst_copy(&scan[i], blk - radix,
955 		    radix / BLIST_RADIX, dest, count);
990 blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, u_daddr_t radix)
995 	if (radix == 1)
999 	blk = (allocBlk + radix * BLIST_RADIX) & -(radix * BLIST_RADIX);
1006 	skip = radix_to_skip(radix);
1007 	blk = allocBlk & -radix;
1010 		digit = (blk / radix) & BLIST_MASK;
1012 		blk += radix;
1015 		    radix / BLIST_RADIX);
1026 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab)
1032 	if (radix == 1) {
1047 	    (long long)blk, (long long)radix * BLIST_RADIX,
1048 	    (long long)radix * BLIST_RADIX,
1054 	skip = radix_to_skip(radix);
1061 		blst_radix_print(&scan[1 + digit * skip], blk + digit * radix,
1062 		    radix / BLIST_RADIX, tab);