Index: sys/kern/subr_blist.c =================================================================== --- sys/kern/subr_blist.c +++ sys/kern/subr_blist.c @@ -103,6 +103,7 @@ #include #include #include +#include #include #include #include @@ -133,7 +134,7 @@ static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count); static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, daddr_t radix, daddr_t blk); -static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count); +static void blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count); #ifndef _KERNEL static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab); @@ -142,6 +143,7 @@ #ifdef _KERNEL static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); #endif +#define BLIST_META_MASK (BLIST_META_RADIX - 1) CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0); @@ -183,29 +185,41 @@ blist_create(daddr_t blocks, int flags) { blist_t bl; - daddr_t nodes, radix; + daddr_t i, last_block, nodes, radix; /* - * Calculate the radix field used for scanning. + * Calculate the radix and node count used for scanning. Find the last + * block that is followed by a terminator. */ + last_block = blocks - 1; radix = BLIST_BMAP_RADIX; while (radix < blocks) { + if (((last_block / radix + 1) & BLIST_META_MASK) != 0) + /* + * A terminator will be added. Update last_block to the + * position just before that terminator. + */ + last_block |= radix - 1; radix *= BLIST_META_RADIX; } - nodes = 1 + blst_radix_init(NULL, radix, blocks); - bl = malloc(sizeof(struct blist), M_SWAP, flags); + /* + * Count the meta-nodes in the expanded tree, including the final + * terminator, from the bottom level up to the root. + */ + nodes = (last_block >= blocks) ? 2: 1; + last_block /= BLIST_BMAP_RADIX; + while (last_block > 0) { + nodes += last_block + 1; + last_block /= BLIST_META_RADIX; + } + bl = malloc(offsetof(struct blist, bl_root[nodes]), M_SWAP, flags); if (bl == NULL) return (NULL); bl->bl_blocks = blocks; bl->bl_radix = radix; bl->bl_cursor = 0; - bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags); - if (bl->bl_root == NULL) { - free(bl, M_SWAP); - return (NULL); - } blst_radix_init(bl->bl_root, radix, blocks); #if defined(BLIST_DEBUG) @@ -226,7 +240,6 @@ void blist_destroy(blist_t bl) { - free(bl->bl_root, M_SWAP); free(bl, M_SWAP); } @@ -832,23 +845,19 @@ * be considerably less than the calculated radix due to the large * RADIX values we use. */ -static daddr_t +static void blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count) { - daddr_t i, memindex, next_skip, skip; - - memindex = 0; + daddr_t i, next_skip, skip; /* * Leaf node */ if (radix == BLIST_BMAP_RADIX) { - if (scan) { - scan->bm_bighint = 0; - scan->u.bmu_bitmap = 0; - } - return (memindex); + scan->bm_bighint = 0; + scan->u.bmu_bitmap = 0; + return; } /* @@ -857,10 +866,8 @@ * is required to manage 'count' blocks, so we continue on anyway. */ - if (scan) { - scan->bm_bighint = 0; - scan->u.bmu_avail = 0; - } + scan->bm_bighint = 0; + scan->u.bmu_avail = 0; skip = radix_to_skip(radix); next_skip = skip / BLIST_META_RADIX; @@ -871,30 +878,22 @@ /* * Allocate the entire object */ - memindex = i + - blst_radix_init(((scan) ? &scan[i] : NULL), radix, - radix); + blst_radix_init(&scan[i], radix, radix); count -= radix; } else if (count > 0) { /* * Allocate a partial object */ - memindex = i + - blst_radix_init(((scan) ? &scan[i] : NULL), radix, - count); + blst_radix_init(&scan[i], radix, count); count = 0; } else { /* * Add terminator and break out */ - if (scan) - scan[i].bm_bighint = (daddr_t)-1; + scan[i].bm_bighint = (daddr_t)-1; break; } } - if (memindex < i) - memindex = i; - return (memindex); } #ifdef BLIST_DEBUG Index: sys/sys/blist.h =================================================================== --- sys/sys/blist.h +++ sys/sys/blist.h @@ -82,7 +82,7 @@ daddr_t bl_blocks; /* area of coverage */ daddr_t bl_radix; /* coverage radix */ daddr_t bl_cursor; /* next-fit search starts at */ - blmeta_t *bl_root; /* root of radix tree */ + blmeta_t bl_root[1]; /* root of radix tree */ } *blist_t; #define BLIST_META_RADIX 16