sys/kern/subr_blist.c

130 static daddr_t	blst_leaf_alloc(blmeta_t *scan, daddr_t blk,
132 static daddr_t	blst_meta_alloc(blmeta_t *scan, daddr_t cursor, int *count,
134 static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
135 static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count,
137 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
139 static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count);
140 static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count,
143 static void	blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix,
578  *	'scan' is a leaf node, and its first block is at address 'start'.  The
580  *	common ancestor of 'scan' and its neighbor is several levels up.  Use
587 blst_next_leaf_alloc(blmeta_t *scan, daddr_t start, int count, int maxcount)
597 		while (((++scan)->bm_bitmap & 1) == 1 &&
600 		if (~scan->bm_bitmap != 0) {
607 			avail = blk - start + bitpos(~scan->bm_bitmap);
619 				 * There was no next leaf.  Back scan up to
624 					--scan;
632 	 * 'scan' is the last leaf that provides blocks.  Clear from 1 to
636 		scan->bm_bitmap &= ~bitrange(0, maxcount % BLIST_RADIX);
638 		scan->bm_bitmap = 0;
646 			if ((scan--)->bm_bitmap == 0)
647 				scan->bm_bitmap ^= 1;
649 		if ((scan--)->bm_bitmap == 0)
650 			scan[-digit * radix_to_skip(radix)].bm_bitmap ^=
656 		scan->bm_bitmap = 0;
669 blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int *count, int maxcount)
676 	mask = ~scan->bm_bitmap;
680 		 * num_shifts)] are 1 in scan->bm_bitmap.  Reduce num_shifts to
683 		 * longer string of consecutive 1-bits in scan->bm_bitmap.  If
697 		scan->bm_bighint = bighint;
708 				scan->bm_bighint = bighint;
737 			scan->bm_bighint = bighint;
742 		hi = blst_next_leaf_alloc(scan, blk, count1, maxcount);
754 		scan->bm_bighint = bighint;
758 	scan->bm_bitmap &= mask;
771 blst_meta_alloc(blmeta_t *scan, daddr_t cursor, int *count,
780 		return (blst_leaf_alloc(scan, cursor, count, maxcount));
784 	mask = scan->bm_bitmap;
808 		if (*count <= scan[i].bm_bighint) {
812 			r = blst_meta_alloc(&scan[i], cursor + digit * radix,
815 				if (scan[i].bm_bitmap == 0)
816 					scan->bm_bitmap ^= bitrange(digit, 1);
828 	    scan[i].bm_bighint == BLIST_MAX_ALLOC))
829 		scan->bm_bighint = *count - 1;
839 blst_leaf_free(blmeta_t *scan, daddr_t blk, int count)
850 	KASSERT((scan->bm_bitmap & mask) == 0,
852 	    (uintmax_t)blk, count, (uintmax_t)scan->bm_bitmap & mask));
853 	scan->bm_bitmap |= mask;
867 blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, u_daddr_t radix)
878 	scan->bm_bighint = BLIST_MAX_ALLOC;
881 		return (blst_leaf_free(scan, freeBlk, count));
895 	scan->bm_bitmap |= bitrange(digit, endDigit - digit);
899 		blst_meta_free(&scan[i], freeBlk, count, radix / BLIST_RADIX);
911 blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, blist_t dest,
921 		u_daddr_t v = scan->bm_bitmap;
940 	if (scan->bm_bitmap == 0) {
954 		blst_copy(&scan[i], blk - radix,
967 blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count)
975 	nblks = bitcount64(scan->bm_bitmap & mask);
977 	scan->bm_bitmap &= ~mask;
990 blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, u_daddr_t radix)
996 		return (blst_leaf_fill(scan, allocBlk, count));
1014 		nblks += blst_meta_fill(&scan[i], allocBlk, count,
1016 		if (scan[i].bm_bitmap == 0)
1017 			scan->bm_bitmap &= ~((u_daddr_t)1 << digit);
1026 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab)
1038 		    (long long)scan->bm_bitmap,
1039 		    (long long)scan->bm_bighint
1050 	    (long long)scan->bm_bitmap,
1051 	    (long long)scan->bm_bighint
1057 	mask = scan->bm_bitmap;
1061 		blst_radix_print(&scan[1 + digit * skip], blk + digit * radix,