diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2018-08-07 14:56:50 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2018-09-21 10:29:37 +0200 |
commit | c37f9fba70085fedc8eede7559489d2321393005 (patch) | |
tree | 042455ebf1fa89a277a825f72e1ed805d0b4d296 /freebsd/sys/kern/subr_blist.c | |
parent | Update to FreeBSD head 2017-06-01 (diff) | |
download | rtems-libbsd-c37f9fba70085fedc8eede7559489d2321393005.tar.bz2 |
Update to FreeBSD head 2017-08-01
Git mirror commit f5002f5e5f78cae9f0269d812dc0aedb0339312c.
Update #3472.
Diffstat (limited to 'freebsd/sys/kern/subr_blist.c')
-rw-r--r-- | freebsd/sys/kern/subr_blist.c | 658 |
1 files changed, 304 insertions, 354 deletions
diff --git a/freebsd/sys/kern/subr_blist.c b/freebsd/sys/kern/subr_blist.c index 5af51dd4..c8e32c5b 100644 --- a/freebsd/sys/kern/subr_blist.c +++ b/freebsd/sys/kern/subr_blist.c @@ -30,18 +30,18 @@ * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting * * This module implements a general bitmap allocator/deallocator. The - * allocator eats around 2 bits per 'block'. The module does not - * try to interpret the meaning of a 'block' other than to return + * allocator eats around 2 bits per 'block'. The module does not + * try to interpret the meaning of a 'block' other than to return * SWAPBLK_NONE on an allocation failure. * * A radix tree is used to maintain the bitmap. Two radix constants are * involved: One for the bitmaps contained in the leaf nodes (typically - * 32), and one for the meta nodes (typically 16). Both meta and leaf + * 64), and one for the meta nodes (typically 16). Both meta and leaf * nodes have a hint field. This field gives us a hint as to the largest * free contiguous range of blocks under the node. It may contain a - * value that is too high, but will never contain a value that is too + * value that is too high, but will never contain a value that is too * low. When the radix tree is searched, allocation failures in subtrees - * update the hint. + * update the hint. * * The radix tree also implements two collapsed states for meta nodes: * the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is @@ -51,7 +51,7 @@ * * The hinting greatly increases code efficiency for allocations while * the general radix structure optimizes both allocations and frees. The - * radix tree should be able to operate well no matter how much + * radix tree should be able to operate well no matter how much * fragmentation there is and no matter how large a bitmap is used. * * The blist code wires all necessary memory at creation time. Neither @@ -63,18 +63,18 @@ * linear array. Each meta node is immediately followed (laid out * sequentially in memory) by BLIST_META_RADIX lower level nodes. This * is a recursive structure but one that can be easily scanned through - * a very simple 'skip' calculation. In order to support large radixes, - * portions of the tree may reside outside our memory allocation. We - * handle this with an early-termination optimization (when bighint is - * set to -1) on the scan. The memory allocation is only large enough + * a very simple 'skip' calculation. In order to support large radixes, + * portions of the tree may reside outside our memory allocation. We + * handle this with an early-termination optimization (when bighint is + * set to -1) on the scan. The memory allocation is only large enough * to cover the number of blocks requested at creation time even if it * must be encompassed in larger root-node radix. * - * NOTE: the allocator cannot currently allocate more than - * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too - * large' if you try. This is an area that could use improvement. The - * radix is large enough that this restriction does not effect the swap - * system, though. Currently only the allocation code is effected by + * NOTE: the allocator cannot currently allocate more than + * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too + * large' if you try. This is an area that could use improvement. The + * radix is large enough that this restriction does not effect the swap + * system, though. Currently only the allocation code is affected by * this algorithmic unfeature. The freeing code can handle arbitrary * ranges. * @@ -93,7 +93,7 @@ __FBSDID("$FreeBSD$"); #include <sys/blist.h> #include <sys/malloc.h> #include <sys/proc.h> -#include <sys/mutex.h> +#include <sys/mutex.h> #else @@ -101,19 +101,18 @@ __FBSDID("$FreeBSD$"); #define BLIST_DEBUG #endif -#define SWAPBLK_NONE ((daddr_t)-1) - #include <sys/types.h> +#include <sys/malloc.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdarg.h> +#include <stdbool.h> +#define bitcount64(x) __bitcount64((uint64_t)(x)) #define malloc(a,b,c) calloc(a, 1) #define free(a,b) free(a) -typedef unsigned int u_daddr_t; - #include <sys/blist.h> void panic(const char *ctl, ...); @@ -123,23 +122,23 @@ void panic(const char *ctl, ...); /* * static support functions */ - -static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count); -static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk, - daddr_t count, daddr_t radix, int skip); +static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, + daddr_t cursor); +static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, + daddr_t radix, daddr_t skip, daddr_t cursor); static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count); -static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, - daddr_t radix, int skip, daddr_t blk); -static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, - daddr_t skip, blist_t dest, daddr_t count); -static int blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count); -static int blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, - daddr_t radix, int skip, daddr_t blk); -static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, - int skip, daddr_t count); +static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, + daddr_t radix, daddr_t skip, daddr_t blk); +static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, + daddr_t skip, blist_t dest, daddr_t count); +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 skip, daddr_t blk); +static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t skip, + daddr_t count); #ifndef _KERNEL -static void blst_radix_print(blmeta_t *scan, daddr_t blk, - daddr_t radix, int skip, int tab); +static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, + daddr_t skip, int tab); #endif #ifdef _KERNEL @@ -153,35 +152,40 @@ static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); * blocks - must be greater than 0 * flags - malloc flags * - * The smallest blist consists of a single leaf node capable of + * The smallest blist consists of a single leaf node capable of * managing BLIST_BMAP_RADIX blocks. */ - -blist_t +blist_t blist_create(daddr_t blocks, int flags) { blist_t bl; - int radix; - int skip = 0; + daddr_t nodes, radix, skip; /* * Calculate radix and skip field used for scanning. */ radix = BLIST_BMAP_RADIX; - + skip = 0; while (radix < blocks) { radix *= BLIST_META_RADIX; skip = (skip + 1) * BLIST_META_RADIX; } + nodes = 1 + blst_radix_init(NULL, radix, skip, blocks); - bl = malloc(sizeof(struct blist), M_SWAP, flags | M_ZERO); + bl = malloc(sizeof(struct blist), M_SWAP, flags); + if (bl == NULL) + return (NULL); bl->bl_blocks = blocks; bl->bl_radix = radix; bl->bl_skip = skip; - bl->bl_rootblks = 1 + - blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks); - bl->bl_root = malloc(sizeof(blmeta_t) * bl->bl_rootblks, M_SWAP, flags); + 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, skip, blocks); #if defined(BLIST_DEBUG) printf( @@ -189,17 +193,16 @@ blist_create(daddr_t blocks, int flags) ", requiring %lldK of ram\n", (long long)bl->bl_blocks, (long long)bl->bl_blocks * 4 / 1024, - (long long)(bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024 + (long long)(nodes * sizeof(blmeta_t) + 1023) / 1024 ); printf("BLIST raw radix tree contains %lld records\n", - (long long)bl->bl_rootblks); + (long long)nodes); #endif - blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks); - return(bl); + return (bl); } -void +void blist_destroy(blist_t bl) { free(bl->bl_root, M_SWAP); @@ -207,25 +210,44 @@ 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. */ - -daddr_t +daddr_t blist_alloc(blist_t bl, daddr_t count) { - daddr_t blk = SWAPBLK_NONE; + daddr_t blk; - if (bl) { - 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; + /* + * This loop iterates at most twice. An allocation failure in the + * first iteration leads to a second iteration only if the cursor was + * non-zero. When the cursor is zero, an allocation failure will + * reduce the hint, stopping further iterations. + */ + while (count <= bl->bl_root->bm_bighint) { + blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, + bl->bl_skip, bl->bl_cursor); + if (blk != SWAPBLK_NONE) { + bl->bl_cursor = blk + count; + return (blk); + } else if (bl->bl_cursor != 0) + bl->bl_cursor = 0; } - 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); } /* @@ -233,17 +255,11 @@ blist_alloc(blist_t bl, daddr_t count) * of a contiguous region. Panic if an inconsistancy is * found. */ - -void +void blist_free(blist_t bl, daddr_t blkno, daddr_t count) { - if (bl) { - 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); } /* @@ -252,22 +268,12 @@ blist_free(blist_t bl, daddr_t blkno, daddr_t count) * existing allocations. Return the number of blocks * actually filled that were free before the call. */ - -int +daddr_t blist_fill(blist_t bl, daddr_t blkno, daddr_t count) { - int filled; - if (bl) { - if (bl->bl_radix == BLIST_BMAP_RADIX) - filled = blst_leaf_fill(bl->bl_root, blkno, 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 (blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix, + bl->bl_skip, 0)); } /* @@ -277,7 +283,6 @@ blist_fill(blist_t bl, daddr_t blkno, daddr_t count) * one. When extending the tree you can specify whether * the new blocks are to left allocated or freed. */ - void blist_resize(blist_t *pbl, daddr_t count, int freenew, int flags) { @@ -303,7 +308,6 @@ blist_resize(blist_t *pbl, daddr_t count, int freenew, int flags) /* * blist_print() - dump radix tree */ - void blist_print(blist_t bl) { @@ -318,7 +322,7 @@ blist_print(blist_t bl) * ALLOCATION SUPPORT FUNCTIONS * ************************************************************************ * - * These support functions do all the actual work. They may seem + * These support functions do all the actual work. They may seem * rather longish, but that's because I've commented them up. The * actual code is straight forward. * @@ -327,77 +331,91 @@ blist_print(blist_t bl) /* * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). * - * This is the core of the allocator and is optimized for the 1 block - * and the BLIST_BMAP_RADIX block allocation cases. Other cases are - * somewhat slower. The 1 block allocation case is log2 and extremely - * quick. + * This is the core of the allocator and is optimized for the + * BLIST_BMAP_RADIX block allocation case. Otherwise, execution + * time is proportional to log2(count) + log2(BLIST_BMAP_RADIX). */ - static daddr_t -blst_leaf_alloc( - blmeta_t *scan, - daddr_t blk, - int count -) { - u_daddr_t orig = scan->u.bmu_bitmap; - - if (orig == 0) { +blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor) +{ + u_daddr_t mask; + int count1, hi, lo, mid, num_shifts, range1, range_ext; + + if (count == BLIST_BMAP_RADIX) { /* - * Optimize bitmap all-allocated case. Also, count = 1 - * case assumes at least 1 bit is free in the bitmap, so - * we have to take care of this case here. + * Optimize allocation of BLIST_BMAP_RADIX bits. If this wasn't + * a special case, then forming the final value of 'mask' below + * would require special handling to avoid an invalid left shift + * when count equals the number of bits in mask. */ + if (~scan->u.bmu_bitmap != 0) { + scan->bm_bighint = BLIST_BMAP_RADIX - 1; + return (SWAPBLK_NONE); + } + if (cursor != blk) + return (SWAPBLK_NONE); + scan->u.bmu_bitmap = 0; scan->bm_bighint = 0; - return(SWAPBLK_NONE); + return (blk); } - if (count == 1) { + range1 = 0; + count1 = count - 1; + num_shifts = fls(count1); + mask = scan->u.bmu_bitmap; + while (mask != 0 && num_shifts > 0) { /* - * Optimized code to allocate one bit out of the bitmap + * If bit i is set in mask, then bits in [i, i+range1] are set + * in scan->u.bmu_bitmap. The value of range1 is equal to + * count1 >> num_shifts. Grow range and reduce num_shifts to 0, + * while preserving these invariants. The updates to mask leave + * fewer bits set, but each bit that remains set represents a + * longer string of consecutive bits set in scan->u.bmu_bitmap. */ - u_daddr_t mask; - int j = BLIST_BMAP_RADIX/2; - int r = 0; - - mask = (u_daddr_t)-1 >> (BLIST_BMAP_RADIX/2); - - while (j) { - if ((orig & mask) == 0) { - r += j; - orig >>= j; - } - j >>= 1; - mask >>= j; - } - scan->u.bmu_bitmap &= ~(1 << r); - return(blk + r); + num_shifts--; + range_ext = range1 + ((count1 >> num_shifts) & 1); + mask &= mask >> range_ext; + range1 += range_ext; } - if (count <= BLIST_BMAP_RADIX) { + if (mask == 0) { /* - * non-optimized code to allocate N bits out of the bitmap. - * The more bits, the faster the code runs. It will run - * the slowest allocating 2 bits, but since there aren't any - * memory ops in the core loop (or shouldn't be, anyway), - * you probably won't notice the difference. + * Update bighint. There is no allocation bigger than range1 + * available in this leaf. */ - int j; - int n = BLIST_BMAP_RADIX - count; - u_daddr_t mask; + scan->bm_bighint = range1; + return (SWAPBLK_NONE); + } - mask = (u_daddr_t)-1 >> n; + /* + * Discard any candidates that appear before the cursor. + */ + lo = cursor - blk; + mask &= ~(u_daddr_t)0 << lo; - for (j = 0; j <= n; ++j) { - if ((orig & mask) == mask) { - scan->u.bmu_bitmap &= ~mask; - return(blk + j); - } - mask = (mask << 1); - } + if (mask == 0) + return (SWAPBLK_NONE); + + /* + * The least significant set bit in mask marks the start of the first + * available range of sufficient size. Clear all the bits but that one, + * and then perform a binary search to find its position. + */ + mask &= -mask; + hi = BLIST_BMAP_RADIX - count1; + while (lo + 1 < hi) { + mid = (lo + hi) >> 1; + if ((mask >> mid) != 0) + lo = mid; + else + hi = mid; } + /* - * We couldn't allocate count in this subtree, update bighint. + * Set in mask exactly the bits being allocated, and clear them from + * the set of available bits. */ - scan->bm_bighint = count - 1; - return(SWAPBLK_NONE); + mask = (mask << count) - mask; + scan->u.bmu_bitmap &= ~mask; + return (blk + lo); } /* @@ -408,76 +426,75 @@ blst_leaf_alloc( * calls that hit this node. We have to check for our collapse cases * and we have a few optimizations strewn in as well. */ - static daddr_t -blst_meta_alloc( - blmeta_t *scan, - daddr_t blk, - daddr_t count, - daddr_t radix, - int skip -) { - int i; - int next_skip = ((u_int)skip / BLIST_META_RADIX); +blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, daddr_t radix, + daddr_t skip, daddr_t cursor) +{ + daddr_t i, next_skip, r; + int child; + bool scan_from_start; - if (scan->u.bmu_avail == 0) { + if (radix == BLIST_BMAP_RADIX) + return (blst_leaf_alloc(scan, blk, count, cursor)); + 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 = count; - return(SWAPBLK_NONE); + scan->bm_bighint = scan->u.bmu_avail; + return (SWAPBLK_NONE); } + next_skip = skip / BLIST_META_RADIX; + /* + * 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) { + if (next_skip == 1) scan[i].u.bmu_bitmap = (u_daddr_t)-1; - scan[i].bm_bighint = BLIST_BMAP_RADIX; - } else { - scan[i].bm_bighint = radix; + else scan[i].u.bmu_avail = radix; - } + scan[i].bm_bighint = radix; } } else { radix /= BLIST_META_RADIX; } - for (i = 1; i <= skip; i += next_skip) { + if (count > radix) { + /* + * The allocation exceeds the number of blocks that are + * managed by a subtree of this meta node. + */ + panic("allocation too large"); + } + scan_from_start = cursor == blk; + child = (cursor - blk) / radix; + blk += child * radix; + for (i = 1 + child * next_skip; 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, cursor > blk ? cursor : blk); 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; } @@ -485,22 +502,19 @@ blst_meta_alloc( /* * We couldn't allocate count in this subtree, update bighint. */ - if (scan->bm_bighint >= count) + if (scan_from_start && scan->bm_bighint >= count) scan->bm_bighint = count - 1; - return(SWAPBLK_NONE); + + return (SWAPBLK_NONE); } /* * BLST_LEAF_FREE() - free allocated block from leaf bitmap * */ - static void -blst_leaf_free( - blmeta_t *scan, - daddr_t blk, - int count -) { +blst_leaf_free(blmeta_t *scan, daddr_t blk, int count) +{ /* * free some data in this bitmap * @@ -521,7 +535,7 @@ blst_leaf_free( /* * We could probably do a better job here. We are required to make - * bighint at least as large as the biggest contiguous block of + * bighint at least as large as the biggest contiguous block of * data. If we just shoehorn it, a little extra overhead will * be incured on the next allocation (but only that one typically). */ @@ -538,25 +552,18 @@ blst_leaf_free( * range whereas the allocation code cannot allocate an arbitrary * range). */ +static void +blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, daddr_t radix, + daddr_t skip, daddr_t blk) +{ + daddr_t i, next_skip, v; + int child; -static void -blst_meta_free( - blmeta_t *scan, - daddr_t freeBlk, - daddr_t count, - daddr_t radix, - int skip, - daddr_t blk -) { - int i; - int next_skip = ((u_int)skip / BLIST_META_RADIX); - -#if 0 - printf("free (%llx,%lld) FROM (%llx,%lld)\n", - (long long)freeBlk, (long long)count, - (long long)blk, (long long)radix - ); -#endif + if (scan->bm_bighint == (daddr_t)-1) + panic("freeing invalid range"); + if (radix == BLIST_BMAP_RADIX) + return (blst_leaf_free(scan, freeBlk, count)); + next_skip = skip / BLIST_META_RADIX; if (scan->u.bmu_avail == 0) { /* @@ -601,27 +608,16 @@ blst_meta_free( radix /= BLIST_META_RADIX; - i = (freeBlk - blk) / radix; - blk += i * radix; - i = i * next_skip + 1; - + child = (freeBlk - blk) / radix; + blk += child * radix; + i = 1 + child * next_skip; while (i <= skip && blk < freeBlk + count) { - daddr_t v; - v = blk + radix - freeBlk; if (v > count) v = count; - - if (scan->bm_bighint == (daddr_t)-1) - panic("blst_meta_free: freeing unexpected range"); - - if (next_skip == 1) { - blst_leaf_free(&scan[i], freeBlk, v); - } else { - blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); - } + blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); if (scan->bm_bighint < scan[i].bm_bighint) - scan->bm_bighint = scan[i].bm_bighint; + scan->bm_bighint = scan[i].bm_bighint; count -= v; freeBlk += v; blk += radix; @@ -635,17 +631,11 @@ blst_meta_free( * Locates free space in the source tree and frees it in the destination * tree. The space may not already be free in the destination. */ - -static void blst_copy( - blmeta_t *scan, - daddr_t blk, - daddr_t radix, - daddr_t skip, - blist_t dest, - daddr_t count -) { - int next_skip; - int i; +static void +blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, daddr_t skip, + blist_t dest, daddr_t count) +{ + daddr_t i, next_skip; /* * Leaf node @@ -660,7 +650,7 @@ static void blst_copy( int i; for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) { - if (v & (1 << i)) + if (v & ((u_daddr_t)1 << i)) blist_free(dest, blk + i, 1); } } @@ -676,7 +666,7 @@ static void blst_copy( * Source all allocated, leave dest allocated */ return; - } + } if (scan->u.bmu_avail == radix) { /* * Source all free, free entire dest @@ -690,32 +680,20 @@ static void blst_copy( radix /= BLIST_META_RADIX; - next_skip = ((u_int)skip / BLIST_META_RADIX); + next_skip = skip / BLIST_META_RADIX; for (i = 1; count && i <= skip; i += next_skip) { if (scan[i].bm_bighint == (daddr_t)-1) break; if (count >= radix) { - blst_copy( - &scan[i], - blk, - radix, - next_skip - 1, - dest, - radix - ); + blst_copy(&scan[i], blk, radix, next_skip - 1, dest, + radix); count -= radix; } else { if (count) { - blst_copy( - &scan[i], - blk, - radix, - next_skip - 1, - dest, - count - ); + blst_copy(&scan[i], blk, radix, next_skip - 1, + dest, count); } count = 0; } @@ -730,24 +708,21 @@ static void blst_copy( * regardless of any existing allocations in that range. Returns * the number of blocks allocated by the call. */ - -static int +static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count) { int n = blk & (BLIST_BMAP_RADIX - 1); - int nblks; - u_daddr_t mask, bitmap; + daddr_t nblks; + 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); } /* @@ -758,80 +733,74 @@ blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count) * range must be within the extent of this node. Returns the * number of blocks allocated by the call. */ -static int -blst_meta_fill( - blmeta_t *scan, - daddr_t allocBlk, - daddr_t count, - daddr_t radix, - int skip, - daddr_t blk -) { - int i; - int next_skip = ((u_int)skip / BLIST_META_RADIX); - int nblks = 0; +static daddr_t +blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, daddr_t radix, + daddr_t skip, daddr_t blk) +{ + daddr_t i, nblks, next_skip, v; + int child; + if (scan->bm_bighint == (daddr_t)-1) + panic("filling invalid range"); + if (count > radix) { + /* + * The allocation exceeds the number of blocks that are + * managed by this node. + */ + panic("fill too large"); + } + if (radix == BLIST_BMAP_RADIX) + return (blst_leaf_fill(scan, allocBlk, count)); if (count == radix || scan->u.bmu_avail == 0) { /* * ALL-ALLOCATED special case */ nblks = scan->u.bmu_avail; scan->u.bmu_avail = 0; - scan->bm_bighint = count; - return nblks; + scan->bm_bighint = 0; + return (nblks); } + next_skip = skip / BLIST_META_RADIX; + /* + * 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) { + if (next_skip == 1) scan[i].u.bmu_bitmap = (u_daddr_t)-1; - scan[i].bm_bighint = BLIST_BMAP_RADIX; - } else { - scan[i].bm_bighint = radix; + else scan[i].u.bmu_avail = radix; - } + scan[i].bm_bighint = radix; } } else { radix /= BLIST_META_RADIX; } - if (count > radix) - panic("blist_meta_fill: allocation too large"); - - i = (allocBlk - blk) / radix; - blk += i * radix; - i = i * next_skip + 1; - + nblks = 0; + child = (allocBlk - blk) / radix; + blk += child * radix; + i = 1 + child * next_skip; while (i <= skip && blk < allocBlk + count) { - daddr_t v; - v = blk + radix - allocBlk; if (v > count) v = count; - - if (scan->bm_bighint == (daddr_t)-1) - panic("blst_meta_fill: filling unexpected range"); - - if (next_skip == 1) { - nblks += blst_leaf_fill(&scan[i], allocBlk, v); - } else { - nblks += blst_meta_fill(&scan[i], allocBlk, v, - radix, next_skip - 1, blk); - } + nblks += blst_meta_fill(&scan[i], allocBlk, v, radix, + next_skip - 1, blk); count -= v; allocBlk += v; blk += radix; i += next_skip; } scan->u.bmu_avail -= nblks; - return nblks; + return (nblks); } /* @@ -842,13 +811,12 @@ blst_meta_fill( * be considerably less than the calculated radix due to the large * RADIX values we use. */ - -static daddr_t -blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count) +static daddr_t +blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t skip, daddr_t count) { - int i; - int next_skip; - daddr_t memindex = 0; + daddr_t i, memindex, next_skip; + + memindex = 0; /* * Leaf node @@ -859,7 +827,7 @@ blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count) scan->bm_bighint = 0; scan->u.bmu_bitmap = 0; } - return(memindex); + return (memindex); } /* @@ -874,30 +842,24 @@ blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count) } radix /= BLIST_META_RADIX; - next_skip = ((u_int)skip / BLIST_META_RADIX); + next_skip = skip / BLIST_META_RADIX; for (i = 1; i <= skip; i += next_skip) { if (count >= radix) { /* * Allocate the entire object */ - memindex = i + blst_radix_init( - ((scan) ? &scan[i] : NULL), - radix, - next_skip - 1, - radix - ); + memindex = i + + blst_radix_init(((scan) ? &scan[i] : NULL), radix, + next_skip - 1, radix); count -= radix; } else if (count > 0) { /* * Allocate a partial object */ - memindex = i + blst_radix_init( - ((scan) ? &scan[i] : NULL), - radix, - next_skip - 1, - count - ); + memindex = i + + blst_radix_init(((scan) ? &scan[i] : NULL), radix, + next_skip - 1, count); count = 0; } else { /* @@ -910,21 +872,20 @@ blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count) } if (memindex < i) memindex = i; - return(memindex); + return (memindex); } #ifdef BLIST_DEBUG -static void -blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) +static void +blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, daddr_t skip, + int tab) { - int i; - int next_skip; - int lastState = 0; + daddr_t i, next_skip; if (radix == BLIST_BMAP_RADIX) { printf( - "%*.*s(%08llx,%lld): bitmap %08llx big=%lld\n", + "%*.*s(%08llx,%lld): bitmap %016llx big=%lld\n", tab, tab, "", (long long)blk, (long long)radix, (long long)scan->u.bmu_bitmap, @@ -962,7 +923,7 @@ blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) ); radix /= BLIST_META_RADIX; - next_skip = ((u_int)skip / BLIST_META_RADIX); + next_skip = skip / BLIST_META_RADIX; tab += 4; for (i = 1; i <= skip; i += next_skip) { @@ -972,16 +933,9 @@ blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) tab, tab, "", (long long)blk, (long long)radix ); - lastState = 0; break; } - blst_radix_print( - &scan[i], - blk, - radix, - next_skip - 1, - tab - ); + blst_radix_print(&scan[i], blk, radix, next_skip - 1, tab); blk += radix; } tab -= 4; @@ -1018,11 +972,10 @@ main(int ac, char **av) for (;;) { char buf[1024]; - daddr_t da = 0; - daddr_t count = 0; - + 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) @@ -1030,7 +983,7 @@ main(int ac, char **av) switch(buf[0]) { case 'r': if (sscanf(buf + 1, "%lld", &count) == 1) { - blist_resize(&bl, count, 1); + blist_resize(&bl, count, 1, M_WAITOK); } else { printf("?\n"); } @@ -1046,18 +999,16 @@ main(int ac, char **av) } break; case 'f': - if (sscanf(buf + 1, "%llx %lld", - (long long *)&da, (long long *)&count) == 2) { + if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) { blist_free(bl, da, count); } else { printf("?\n"); } break; case 'l': - if (sscanf(buf + 1, "%llx %lld", - (long long *)&da, (long long *)&count) == 2) { - printf(" n=%d\n", - blist_fill(bl, da, count)); + if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) { + printf(" n=%jd\n", + (intmax_t)blist_fill(bl, da, count)); } else { printf("?\n"); } @@ -1094,4 +1045,3 @@ panic(const char *ctl, ...) } #endif - |