Date: Tue, 13 Jun 2017 17:49:49 +0000 (UTC) From: Alan Cox <alc@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r319905 - in head/sys: kern sys Message-ID: <201706131749.v5DHnnVm006485@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: alc Date: Tue Jun 13 17:49:49 2017 New Revision: 319905 URL: https://svnweb.freebsd.org/changeset/base/319905 Log: Reduce the frequency of hint updates on allocation without incurring additional allocation overhead. Previously, blst_meta_alloc() updated the hint after every successful allocation. However, these "eager" hint updates are of no actual benefit if, instead, the "lazy" hint update at the start of blst_meta_alloc() is generalized to handle all cases where the number of available blocks is less than the requested allocation. Previously, the lazy hint update at the start of blst_meta_alloc() only handled the ALL-FULL case. (I would also note that this change provides consistency between blist_alloc() and blist_fill() in that their hint maintenance is now entirely lazy.) Eliminate unnecessary checks for terminators in blst_meta_alloc() and blst_meta_fill() when handling ALL-FREE meta nodes. Eliminate the field "bl_free" from struct blist. It is redundant. Unless the entire radix tree is a single leaf, the count of free blocks is stored in the root node. Instead, provide a function blist_avail() for obtaining the number of free blocks. In blst_meta_alloc(), perform a sanity check on the allocation once rather than repeating it in a loop over the meta node's children. In blst_leaf_fill(), use the optimized bitcount*() function instead of a loop to count the blocks being allocated. Add or improve several comments. Address some nearby style errors. Reviewed by: kib MFC after: 6 weeks Differential Revision: https://reviews.freebsd.org/D11146 Modified: head/sys/kern/subr_blist.c head/sys/sys/blist.h Modified: head/sys/kern/subr_blist.c ============================================================================== --- head/sys/kern/subr_blist.c Tue Jun 13 16:19:32 2017 (r319904) +++ head/sys/kern/subr_blist.c Tue Jun 13 17:49:49 2017 (r319905) @@ -106,6 +106,7 @@ __FBSDID("$FreeBSD$"); #include <stdlib.h> #include <stdarg.h> +#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 @@ blist_create(daddr_t blocks, int flags) 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_destroy(blist_t bl) } /* - * 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 @@ blist_destroy(blist_t bl) 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 @@ blist_free(blist_t bl, daddr_t blkno, daddr_t count) 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 @@ blist_fill(blist_t bl, daddr_t blkno, daddr_t count) 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 @@ blst_meta_alloc( 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 @@ blst_meta_alloc( 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 @@ blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count) { 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 @@ blst_meta_fill( 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 @@ blst_meta_fill( 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 @@ main(int ac, char **av) 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) Modified: head/sys/sys/blist.h ============================================================================== --- head/sys/sys/blist.h Tue Jun 13 16:19:32 2017 (r319904) +++ head/sys/sys/blist.h Tue Jun 13 17:49:49 2017 (r319905) @@ -82,7 +82,6 @@ typedef struct blist { 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 @@ typedef struct blist { #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);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201706131749.v5DHnnVm006485>