Index: head/sys/kern/subr_blist.c =================================================================== --- head/sys/kern/subr_blist.c +++ head/sys/kern/subr_blist.c @@ -106,6 +106,7 @@ #include #include +#define bitcount64(x) __bitcount64((uint64_t)(x)) #define malloc(a,b,c) calloc(a, 1) #define free(a,b) free(a) @@ -169,7 +170,7 @@ skip = (skip + 1) * BLIST_META_RADIX; } - bl = malloc(sizeof(struct blist), M_SWAP, flags | M_ZERO); + bl = malloc(sizeof(struct blist), M_SWAP, flags); if (bl == NULL) return (NULL); @@ -207,7 +208,7 @@ } /* - * blist_alloc() - reserve space in the block bitmap. Return the base + * blist_alloc() - reserve space in the block bitmap. Return the base * of a contiguous region or SWAPBLK_NONE if space could * not be allocated. */ @@ -215,20 +216,34 @@ daddr_t blist_alloc(blist_t bl, daddr_t count) { - daddr_t blk = SWAPBLK_NONE; + daddr_t blk; - if (bl) { + if (bl != NULL && count <= bl->bl_root->bm_bighint) { if (bl->bl_radix == BLIST_BMAP_RADIX) blk = blst_leaf_alloc(bl->bl_root, 0, count); else - blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip); - if (blk != SWAPBLK_NONE) - bl->bl_free -= count; + blk = blst_meta_alloc(bl->bl_root, 0, count, + bl->bl_radix, bl->bl_skip); + return (blk); } - return(blk); + return (SWAPBLK_NONE); } /* + * blist_avail() - return the number of free blocks. + */ + +daddr_t +blist_avail(blist_t bl) +{ + + if (bl->bl_radix == BLIST_BMAP_RADIX) + return (bitcount64(bl->bl_root->u.bmu_bitmap)); + else + return (bl->bl_root->u.bmu_avail); +} + +/* * blist_free() - free up space in the block bitmap. Return the base * of a contiguous region. Panic if an inconsistancy is * found. @@ -241,8 +256,8 @@ if (bl->bl_radix == BLIST_BMAP_RADIX) blst_leaf_free(bl->bl_root, blkno, count); else - blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); - bl->bl_free += count; + blst_meta_free(bl->bl_root, blkno, count, + bl->bl_radix, bl->bl_skip, 0); } } @@ -264,10 +279,9 @@ else filled = blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); - bl->bl_free -= filled; - return filled; - } else - return 0; + return (filled); + } + return (0); } /* @@ -417,27 +431,32 @@ daddr_t radix, int skip ) { + daddr_t r; int i; int next_skip = ((u_int)skip / BLIST_META_RADIX); - if (scan->u.bmu_avail == 0) { + if (scan->u.bmu_avail < count) { /* - * ALL-ALLOCATED special case + * The meta node's hint must be too large if the allocation + * exceeds the number of free blocks. Reduce the hint, and + * return failure. */ - scan->bm_bighint = 0; - return(SWAPBLK_NONE); + scan->bm_bighint = scan->u.bmu_avail; + return (SWAPBLK_NONE); } + /* + * An ALL-FREE meta node requires special handling before allocating + * any of its blocks. + */ if (scan->u.bmu_avail == radix) { radix /= BLIST_META_RADIX; /* - * ALL-FREE special case, initialize uninitialize - * sublevel. + * Reinitialize each of the meta node's children. An ALL-FREE + * meta node cannot have a terminator in any subtree. */ for (i = 1; i <= skip; i += next_skip) { - if (scan[i].bm_bighint == (daddr_t)-1) - break; if (next_skip == 1) { scan[i].u.bmu_bitmap = (u_daddr_t)-1; scan[i].bm_bighint = BLIST_BMAP_RADIX; @@ -450,34 +469,33 @@ radix /= BLIST_META_RADIX; } + if (count > radix) { + /* + * The allocation exceeds the number of blocks that are + * managed by a subtree of this meta node. + */ + panic("allocation too large"); + } for (i = 1; i <= skip; i += next_skip) { if (count <= scan[i].bm_bighint) { /* - * count fits in object + * The allocation might fit in the i'th subtree. */ - daddr_t r; if (next_skip == 1) { r = blst_leaf_alloc(&scan[i], blk, count); } else { - r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1); + r = blst_meta_alloc(&scan[i], blk, count, + radix, next_skip - 1); } if (r != SWAPBLK_NONE) { scan->u.bmu_avail -= count; - if (scan->bm_bighint > scan->u.bmu_avail) - scan->bm_bighint = scan->u.bmu_avail; - return(r); + return (r); } } else if (scan[i].bm_bighint == (daddr_t)-1) { /* * Terminator */ break; - } else if (count > radix) { - /* - * count does not fit in object even if it were - * complete free. - */ - panic("blist_meta_alloc: allocation too large"); } blk += radix; } @@ -736,18 +754,16 @@ { int n = blk & (BLIST_BMAP_RADIX - 1); daddr_t nblks; - u_daddr_t mask, bitmap; + u_daddr_t mask; mask = ((u_daddr_t)-1 << n) & ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); - /* Count the number of blocks we're about to allocate */ - bitmap = scan->u.bmu_bitmap & mask; - for (nblks = 0; bitmap != 0; nblks++) - bitmap &= bitmap - 1; + /* Count the number of blocks that we are allocating. */ + nblks = bitcount64(scan->u.bmu_bitmap & mask); scan->u.bmu_bitmap &= ~mask; - return nblks; + return (nblks); } /* @@ -771,8 +787,13 @@ int next_skip = ((u_int)skip / BLIST_META_RADIX); daddr_t nblks = 0; - if (count > radix) - panic("blist_meta_fill: allocation too large"); + if (count > radix) { + /* + * The allocation exceeds the number of blocks that are + * managed by this meta node. + */ + panic("allocation too large"); + } if (count == radix || scan->u.bmu_avail == 0) { /* * ALL-ALLOCATED special case @@ -783,15 +804,18 @@ return nblks; } + /* + * An ALL-FREE meta node requires special handling before allocating + * any of its blocks. + */ if (scan->u.bmu_avail == radix) { radix /= BLIST_META_RADIX; /* - * ALL-FREE special case, initialize sublevel + * Reinitialize each of the meta node's children. An ALL-FREE + * meta node cannot have a terminator in any subtree. */ for (i = 1; i <= skip; i += next_skip) { - if (scan[i].bm_bighint == (daddr_t)-1) - break; if (next_skip == 1) { scan[i].u.bmu_bitmap = (u_daddr_t)-1; scan[i].bm_bighint = BLIST_BMAP_RADIX; @@ -1020,7 +1044,7 @@ long long da = 0; long long count = 0; - printf("%lld/%lld/%lld> ", (long long)bl->bl_free, + printf("%lld/%lld/%lld> ", (long long)blist_avail(bl), (long long)size, (long long)bl->bl_radix); fflush(stdout); if (fgets(buf, sizeof(buf), stdin) == NULL) Index: head/sys/sys/blist.h =================================================================== --- head/sys/sys/blist.h +++ head/sys/sys/blist.h @@ -82,7 +82,6 @@ daddr_t bl_blocks; /* area of coverage */ daddr_t bl_radix; /* coverage radix */ daddr_t bl_skip; /* starting skip */ - daddr_t bl_free; /* number of free blocks */ blmeta_t *bl_root; /* root of radix tree */ } *blist_t; @@ -92,6 +91,7 @@ #define BLIST_MAX_ALLOC BLIST_BMAP_RADIX daddr_t blist_alloc(blist_t blist, daddr_t count); +daddr_t blist_avail(blist_t blist); blist_t blist_create(daddr_t blocks, int flags); void blist_destroy(blist_t blist); daddr_t blist_fill(blist_t bl, daddr_t blkno, daddr_t count);