dev/dtrace/blist.c

2  * BLIST.C -	Bitmap allocator/deallocator, using a radix tree with hinting
12  *	A radix tree is used to maintain the bitmap.  Two radix constants are
18  *	low.  When the radix tree is searched, allocation failures in subtrees
21  *	The radix tree also implements two collapsed states for meta nodes:
28  *	the general radix structure optimizes both allocations and frees.  The
29  *	radix tree should be able to operate well no matter how much
41  *	LAYOUT: The radix tree is layed out recursively using a
50  *	must be encompassed in larger root-node radix.
55  *	radix is large enough that this restriction does not effect the swap
134 				daddr_t count, daddr_t radix, int skip);
137 					daddr_t radix, int skip, daddr_t blk);
138 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
140 static daddr_t	blst_radix_init(blmeta_t *scan, daddr_t radix,
144 					daddr_t radix, int skip, int tab);
167 	int radix;
171 	 * Calculate radix and skip field used for scanning.
173 	radix = BLIST_BMAP_RADIX;
175 	while (radix < blocks) {
176 		radix <<= BLIST_META_RADIX_SHIFT;
185 	bl->bl_radix = radix;
199 	printf("BLIST raw radix tree contains %d records\n", bl->bl_rootblks);
256  * blist_resize() -	resize an existing radix tree to handle the
285  * blist_print()    - dump radix tree
309  * blist_leaf_alloc() -	allocate at a leaf in the radix tree (a bitmap).
386  * blist_meta_alloc() -	allocate at a meta in the radix tree.
395 blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, daddr_t radix,
409 	if (scan->u.bmu_avail == radix) {
410 		radix >>= BLIST_META_RADIX_SHIFT;
423 				scan[i].bm_bighint = radix;
424 				scan[i].u.bmu_avail = radix;
428 		radix >>= BLIST_META_RADIX_SHIFT;
441 						    radix, next_skip - 1);
453 		} else if (count > radix) {
460 		blk += radix;
507  * BLST_META_FREE() - free allocated blocks from radix tree meta info
510  *	The range must be entirely enclosed by this radix node.  If a
518 blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, daddr_t radix,
527 	    blk, radix
539 		if (count != radix)  {
553 		/* scan->bm_bighint = radix; */
560 	if (scan->u.bmu_avail == radix)
562 	if (scan->u.bmu_avail > radix)
563 		panic("blst_meta_free: freeing already free blocks (%d) %d/%d", count, scan->u.bmu_avail, radix);
569 	radix >>= BLIST_META_RADIX_SHIFT;
571 	i = (freeBlk - blk) / radix;
572 	blk += i * radix;
578 		v = blk + radix - freeBlk;
588 			blst_meta_free(&scan[i], freeBlk, v, radix,
594 		blk += radix;
600  * BLIST_RADIX_COPY() - copy one radix tree to another
606 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
616 	if (radix == BLIST_BMAP_RADIX) {
648 	if (scan->u.bmu_avail == radix) {
652 		if (count < radix)
655 			blist_free(dest, blk, radix);
659 	radix >>= BLIST_META_RADIX_SHIFT;
666 		if (count >= radix) {
670 			    radix,
673 			    radix
675 			count -= radix;
681 				    radix,
689 		blk += radix;
694  * BLST_RADIX_INIT() - initialize radix tree
698  *	be considerably less then the calculated radix due to the large
703 blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count)
713 	if (radix == BLIST_BMAP_RADIX) {
732 	radix >>= BLIST_META_RADIX_SHIFT;
736 		if (count >= radix) {
742 			    radix,
744 			    radix
746 			count -= radix;
753 			    radix,
775 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab)
781 	if (radix == BLIST_BMAP_RADIX) {
785 		    blk, radix,
797 		    radix
801 	if (scan->u.bmu_avail == radix) {
806 		    radix
814 	    blk, radix,
816 	    radix,
820 	radix >>= BLIST_META_RADIX_SHIFT;
829 			    blk, radix
837 		    radix,
841 		blk += radix;