svn commit: r340402 - in head/sys: kern sys
Mark Johnston
markj at FreeBSD.org
Tue Nov 13 18:40:02 UTC 2018
Author: markj
Date: Tue Nov 13 18:40:01 2018
New Revision: 340402
URL: https://svnweb.freebsd.org/changeset/base/340402
Log:
Allow allocations across meta boundaries.
Remove restrictions that prevent allocation requests to cross the
boundary between two meta nodes.
Replace the bmu_avail field in meta nodes with a bitmap that identifies
which subtrees have some free memory, and iterate over the nonempty
subtrees only in blst_meta_alloc. If free memory is scarce, this should
make searching for it faster.
Put the code for handling the next-leaf allocation in a separate
function. When taking blocks from the next leaf empties the leaf, be
sure to clear the appropriate bit in its parent, and so on, up to the
least-common ancestor of this leaf and the next.
Eliminate special terminator nodes, and rely instead on the fact that
there is a 0-bit at the end of the bitmask at the root of the tree that
will stop a meta_alloc search, or a next-leaf search, before the search
falls off the end of the tree. Make sure that the tree is big enough to
have space for that 0-bit.
Eliminate special all-free indicators. Lazy initialization of subtrees
stands in the way of having an allocation span a meta-node boundary, so
a subtree of all free blocks is not treated specially. Subtrees of
all-allocated blocks are still recognized by looking at the bitmask at
the root and finding 0.
Don't print all-allocated subtrees. Do print the bitmasks for meta
nodes, when tree-printing.
Submitted by: Doug Moore <dougm at rice.edu>
Reviewed by: alc
MFC after: 1 month
Differential Revision: https://reviews.freebsd.org/D12635
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 Nov 13 18:21:47 2018 (r340401)
+++ head/sys/kern/subr_blist.c Tue Nov 13 18:40:01 2018 (r340402)
@@ -46,11 +46,11 @@
* upper bound on a potential allocation, but not necessarily a tight upper
* bound.
*
- * 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
- * in either of these two states, all information contained underneath
- * the node is considered stale. These states are used to optimize
- * allocation and freeing operations.
+ * The bitmap field in each node directs the search for available blocks.
+ * For a leaf node, a bit is set if the corresponding block is free. For a
+ * meta node, a bit is set if the corresponding subtree contains a free
+ * block somewhere within it. The search at a meta node considers only
+ * children of that node that represent a range that includes a free block.
*
* The hinting greatly increases code efficiency for allocations while
* the general radix structure optimizes both allocations and frees. The
@@ -59,19 +59,19 @@
*
* The blist code wires all necessary memory at creation time. Neither
* allocations nor frees require interaction with the memory subsystem.
- * The non-blocking features of the blist code are used in the swap code
- * (vm/swap_pager.c).
+ * The non-blocking nature of allocations and frees is required by swap
+ * code (vm/swap_pager.c).
*
- * LAYOUT: The radix tree is laid out recursively using a
- * 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
- * to cover the number of blocks requested at creation time even if it
- * must be encompassed in larger root-node radix.
+ * LAYOUT: The radix tree is laid out recursively using a 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. The memory allocation is only large enough to
+ * cover the number of blocks requested at creation time. Nodes that
+ * represent blocks beyond that limit, nodes that would never be read
+ * or written, are not allocated, so that the last of the
+ * BLIST_META_RADIX lower level nodes of a some nodes may not be
+ * allocated.
*
* NOTE: the allocator cannot currently allocate more than
* BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too
@@ -105,6 +105,7 @@ __FBSDID("$FreeBSD$");
#define BLIST_DEBUG
#endif
+#include <sys/errno.h>
#include <sys/types.h>
#include <sys/malloc.h>
#include <sys/sbuf.h>
@@ -118,7 +119,7 @@ __FBSDID("$FreeBSD$");
#define bitcount64(x) __bitcount64((uint64_t)(x))
#define malloc(a,b,c) calloc(a, 1)
#define free(a,b) free(a)
-static __inline int imax(int a, int b) { return (a > b ? a : b); }
+#define ummin(a,b) ((a) < (b) ? (a) : (b))
#include <sys/blist.h>
@@ -179,6 +180,18 @@ radix_to_skip(daddr_t radix)
}
/*
+ * Provide a mask with count bits set, starting as position n.
+ */
+static inline u_daddr_t
+bitrange(int n, int count)
+{
+
+ return (((u_daddr_t)-1 << n) &
+ ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - (n + count))));
+}
+
+
+/*
* Use binary search, or a faster method, to find the 1 bit in a u_daddr_t.
* Assumes that the argument has only one bit set.
*/
@@ -220,9 +233,7 @@ blist_t
blist_create(daddr_t blocks, int flags)
{
blist_t bl;
- daddr_t i, last_block;
- u_daddr_t nodes, radix, skip;
- int digit;
+ u_daddr_t nodes, radix;
if (blocks == 0)
panic("invalid block count");
@@ -230,30 +241,13 @@ blist_create(daddr_t blocks, int flags)
/*
* Calculate the radix and node count used for scanning.
*/
- last_block = blocks - 1;
+ nodes = 1;
radix = BLIST_BMAP_RADIX;
- while (radix < blocks) {
- if (((last_block / radix + 1) & BLIST_META_MASK) != 0)
- /*
- * We must widen the blist to avoid partially
- * filled nodes.
- */
- last_block |= radix - 1;
+ while (radix <= blocks) {
+ nodes += 1 + (blocks - 1) / radix;
radix *= BLIST_META_RADIX;
}
- /*
- * Count the meta-nodes in the expanded tree, including the final
- * terminator, from the bottom level up to the root.
- */
- nodes = 1;
- if (radix - blocks >= BLIST_BMAP_RADIX)
- nodes++;
- 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 |
M_ZERO);
if (bl == NULL)
@@ -261,34 +255,7 @@ blist_create(daddr_t blocks, int flags)
bl->bl_blocks = blocks;
bl->bl_radix = radix;
- bl->bl_cursor = 0;
- /*
- * Initialize the empty tree by filling in root values, then initialize
- * just the terminators in the rest of the tree.
- */
- bl->bl_root[0].bm_bighint = 0;
- if (radix == BLIST_BMAP_RADIX)
- bl->bl_root[0].u.bmu_bitmap = 0;
- else
- bl->bl_root[0].u.bmu_avail = 0;
- last_block = blocks - 1;
- i = 0;
- while (radix > BLIST_BMAP_RADIX) {
- radix /= BLIST_META_RADIX;
- skip = radix_to_skip(radix);
- digit = last_block / radix;
- i += 1 + digit * skip;
- if (digit != BLIST_META_MASK) {
- /*
- * Add a terminator.
- */
- bl->bl_root[i + skip].bm_bighint = (daddr_t)-1;
- bl->bl_root[i + skip].u.bmu_bitmap = 0;
- }
- last_block %= radix;
- }
-
#if defined(BLIST_DEBUG)
printf(
"BLIST representing %lld blocks (%lld MB of swap)"
@@ -321,6 +288,9 @@ blist_alloc(blist_t bl, daddr_t count)
{
daddr_t blk;
+ if (count > BLIST_MAX_ALLOC)
+ panic("allocation too large");
+
/*
* This loop iterates at most twice. An allocation failure in the
* first iteration leads to a second iteration only if the cursor was
@@ -331,12 +301,13 @@ blist_alloc(blist_t bl, daddr_t count)
blk = blst_meta_alloc(bl->bl_root, bl->bl_cursor, count,
bl->bl_radix);
if (blk != SWAPBLK_NONE) {
+ bl->bl_avail -= count;
bl->bl_cursor = blk + count;
if (bl->bl_cursor == bl->bl_blocks)
bl->bl_cursor = 0;
return (blk);
- } else if (bl->bl_cursor != 0)
- bl->bl_cursor = 0;
+ }
+ bl->bl_cursor = 0;
}
return (SWAPBLK_NONE);
}
@@ -348,10 +319,7 @@ 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);
+ return (bl->bl_avail);
}
/*
@@ -363,7 +331,10 @@ void
blist_free(blist_t bl, daddr_t blkno, daddr_t count)
{
+ if (blkno < 0 || blkno + count > bl->bl_blocks)
+ panic("freeing invalid range");
blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix);
+ bl->bl_avail += count;
}
/*
@@ -375,8 +346,13 @@ blist_free(blist_t bl, daddr_t blkno, daddr_t count)
daddr_t
blist_fill(blist_t bl, daddr_t blkno, daddr_t count)
{
+ daddr_t filled;
- return (blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix));
+ if (blkno < 0 || blkno + count > bl->bl_blocks)
+ panic("filling invalid range");
+ filled = blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix);
+ bl->bl_avail -= filled;
+ return (filled);
}
/*
@@ -414,8 +390,11 @@ blist_resize(blist_t *pbl, daddr_t count, int freenew,
void
blist_print(blist_t bl)
{
- printf("BLIST cursor = %08jx {\n", (uintmax_t)bl->bl_cursor);
- blst_radix_print(bl->bl_root, 0, bl->bl_radix, 4);
+ printf("BLIST avail = %jd, cursor = %08jx {\n",
+ (uintmax_t)bl->bl_avail, (uintmax_t)bl->bl_cursor);
+
+ if (bl->bl_root->bm_bitmap != 0)
+ blst_radix_print(bl->bl_root, 0, bl->bl_radix, 4);
printf("}\n");
}
@@ -569,16 +548,11 @@ blist_stats(blist_t bl, struct sbuf *s)
* Check for skippable subtrees starting at i.
*/
while (radix > BLIST_BMAP_RADIX) {
- if (bl->bl_root[nodes].u.bmu_avail == 0) {
+ if (bl->bl_root[nodes].bm_bitmap == 0) {
if (gap_stats_counting(stats))
update_gap_stats(stats, i);
break;
}
- if (bl->bl_root[nodes].u.bmu_avail == radix) {
- if (!gap_stats_counting(stats))
- update_gap_stats(stats, i);
- break;
- }
/*
* Skip subtree root.
@@ -590,7 +564,7 @@ blist_stats(blist_t bl, struct sbuf *s)
/*
* Scan leaf.
*/
- mask = bl->bl_root[nodes].u.bmu_bitmap;
+ mask = bl->bl_root[nodes].bm_bitmap;
diff = mask ^ (mask << 1);
if (gap_stats_counting(stats))
diff ^= 1;
@@ -618,8 +592,58 @@ blist_stats(blist_t bl, struct sbuf *s)
*/
/*
- * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
+ * BLST_NEXT_LEAF_ALLOC() - allocate the first few blocks in the next leaf.
*
+ * 'scan' is a leaf node, associated with a block containing 'blk'.
+ * The next leaf node could be adjacent, or several nodes away if the
+ * least common ancestor of 'scan' and its neighbor is several levels
+ * up. Use 'blk' to determine how many meta-nodes lie between the
+ * leaves. If the next leaf has enough initial bits set, clear them
+ * and clear the bits in the meta nodes on the path up to the least
+ * common ancestor to mark any subtrees made completely empty.
+ */
+static int
+blst_next_leaf_alloc(blmeta_t *scan, daddr_t blk, int count)
+{
+ blmeta_t *next;
+ daddr_t skip;
+ u_daddr_t radix;
+ int digit;
+
+ next = scan + 1;
+ blk += BLIST_BMAP_RADIX;
+ radix = BLIST_BMAP_RADIX;
+ while ((digit = ((blk / radix) & BLIST_META_MASK)) == 0 &&
+ (next->bm_bitmap & 1) == 1) {
+ next++;
+ radix *= BLIST_META_RADIX;
+ }
+ if (((next->bm_bitmap + 1) & ~((u_daddr_t)-1 << count)) != 0) {
+ /*
+ * The next leaf doesn't have enough free blocks at the
+ * beginning to complete the spanning allocation.
+ */
+ return (ENOMEM);
+ }
+ /* Clear the first 'count' bits in the next leaf to allocate. */
+ next->bm_bitmap &= (u_daddr_t)-1 << count;
+
+ /*
+ * Update bitmaps of next-ancestors, up to least common ancestor.
+ */
+ skip = radix_to_skip(radix);
+ while (radix != BLIST_BMAP_RADIX && next->bm_bitmap == 0) {
+ (--next)->bm_bitmap ^= 1;
+ radix /= BLIST_META_RADIX;
+ }
+ if (next->bm_bitmap == 0)
+ scan[-digit * skip].bm_bitmap ^= (u_daddr_t)1 << digit;
+ return (0);
+}
+
+/*
+ * BLST_LEAF_ALLOC() - allocate at a leaf in the radix tree (a bitmap).
+ *
* 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) + bitpos time.
@@ -633,15 +657,15 @@ blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count
range1 = 0;
count1 = count - 1;
num_shifts = fls(count1);
- mask = scan->u.bmu_bitmap;
+ mask = scan->bm_bitmap;
while ((-mask & ~mask) != 0 && num_shifts > 0) {
/*
* 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
+ * in scan->bm_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.
+ * longer string of consecutive bits set in scan->bm_bitmap.
* If more updates to mask cannot clear more bits, because mask
* is partitioned with all 0 bits preceding all 1 bits, the loop
* terminates immediately.
@@ -685,31 +709,14 @@ blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count
* An allocation within this leaf is impossible, so a successful
* allocation depends on the next leaf providing some of the blocks.
*/
- if (((blk / BLIST_BMAP_RADIX + 1) & BLIST_META_MASK) == 0) {
+ if (blst_next_leaf_alloc(scan, blk, hi - BLIST_BMAP_RADIX) != 0)
/*
- * The next leaf has a different meta-node parent, so it
- * is not necessarily initialized. Update bighint,
- * comparing the range found at the end of mask to the
- * largest earlier range that could have been made to
- * vanish in the initial processing of mask.
+ * The hint cannot be updated, because the same
+ * allocation request could be satisfied later, by this
+ * leaf, if the state of the next leaf changes, and
+ * without any changes to this leaf.
*/
- scan->bm_bighint = imax(BLIST_BMAP_RADIX - lo, range1);
return (SWAPBLK_NONE);
- }
- hi -= BLIST_BMAP_RADIX;
- if (((scan[1].u.bmu_bitmap + 1) & ~((u_daddr_t)-1 << hi)) != 0) {
- /*
- * The next leaf doesn't have enough free blocks at the
- * beginning to complete the spanning allocation. The
- * hint cannot be updated, because the same allocation
- * request could be satisfied later, by this leaf, if
- * the state of the next leaf changes, and without any
- * changes to this leaf.
- */
- return (SWAPBLK_NONE);
- }
- /* Clear the first 'hi' bits in the next leaf, allocating them. */
- scan[1].u.bmu_bitmap &= (u_daddr_t)-1 << hi;
hi = BLIST_BMAP_RADIX;
}
@@ -724,12 +731,9 @@ blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count
} else {
/* Clear the bits of mask at position 'hi' and higher. */
mask &= (u_daddr_t)-1 >> (BLIST_BMAP_RADIX - hi);
- /* If this allocation uses all the bits, clear the hint. */
- if (mask == scan->u.bmu_bitmap)
- scan->bm_bighint = 0;
}
/* Clear the allocated bits from this leaf. */
- scan->u.bmu_bitmap &= ~mask;
+ scan->bm_bitmap &= ~mask;
return ((blk & ~BLIST_BMAP_MASK) + lo);
}
@@ -744,81 +748,61 @@ blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count
static daddr_t
blst_meta_alloc(blmeta_t *scan, daddr_t cursor, daddr_t count, u_daddr_t radix)
{
- daddr_t blk, i, next_skip, r, skip;
- int child;
+ daddr_t blk, i, r, skip;
+ u_daddr_t bit, mask;
bool scan_from_start;
+ int digit;
if (radix == BLIST_BMAP_RADIX)
return (blst_leaf_alloc(scan, cursor, count));
- if (scan->u.bmu_avail < count) {
- /*
- * 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 = scan->u.bmu_avail;
- return (SWAPBLK_NONE);
- }
blk = cursor & -radix;
+ scan_from_start = (cursor == blk);
+ radix /= BLIST_META_RADIX;
skip = radix_to_skip(radix);
- next_skip = skip / BLIST_META_RADIX;
+ mask = scan->bm_bitmap;
+ /* Discard any candidates that appear before cursor. */
+ digit = (cursor / radix) & BLIST_META_MASK;
+ mask &= (u_daddr_t)-1 << digit;
+
/*
- * An ALL-FREE meta node requires special handling before allocating
- * any of its blocks.
+ * If the first try is for a block that includes the cursor, pre-undo
+ * the digit * radix offset in the first call; otherwise, ignore the
+ * cursor entirely.
*/
- if (scan->u.bmu_avail == radix) {
- radix /= BLIST_META_RADIX;
+ if (((mask >> digit) & 1) == 1)
+ cursor -= digit * radix;
+ else
+ cursor = blk;
- /*
- * 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 (next_skip == 1)
- scan[i].u.bmu_bitmap = (u_daddr_t)-1;
- else
- scan[i].u.bmu_avail = radix;
- scan[i].bm_bighint = radix;
- }
- } else {
- 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");
- }
- scan_from_start = cursor == blk;
- child = (cursor - blk) / radix;
- blk += child * radix;
- for (i = 1 + child * next_skip; i < skip; i += next_skip) {
+ /*
+ * Examine the nonempty subtree associated with each bit set in mask.
+ */
+ do {
+ bit = mask & -mask;
+ digit = bitpos(bit);
+ i = 1 + digit * skip;
if (count <= scan[i].bm_bighint) {
/*
* The allocation might fit beginning in the i'th subtree.
*/
- r = blst_meta_alloc(&scan[i],
- cursor > blk ? cursor : blk, count, radix);
+ r = blst_meta_alloc(&scan[i], cursor + digit * radix,
+ count, radix);
if (r != SWAPBLK_NONE) {
- scan->u.bmu_avail -= count;
+ if (scan[i].bm_bitmap == 0)
+ scan->bm_bitmap ^= bit;
return (r);
}
- } else if (scan[i].bm_bighint == (daddr_t)-1) {
- /*
- * Terminator
- */
- break;
}
- blk += radix;
- }
+ cursor = blk;
+ } while ((mask ^= bit) != 0);
/*
- * We couldn't allocate count in this subtree, update bighint.
+ * We couldn't allocate count in this subtree. If the whole tree was
+ * scanned, and the last tree node is allocated, update bighint.
*/
- if (scan_from_start && scan->bm_bighint >= count)
+ if (scan_from_start && !(digit == BLIST_META_RADIX - 1 &&
+ scan[i].bm_bighint == BLIST_MAX_ALLOC))
scan->bm_bighint = count - 1;
return (SWAPBLK_NONE);
@@ -832,7 +816,6 @@ static void
blst_leaf_free(blmeta_t *scan, daddr_t blk, int count)
{
u_daddr_t mask;
- int n;
/*
* free some data in this bitmap
@@ -840,20 +823,10 @@ blst_leaf_free(blmeta_t *scan, daddr_t blk, int count)
* \_________/\__/
* count n
*/
- n = blk & BLIST_BMAP_MASK;
- mask = ((u_daddr_t)-1 << n) &
- ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
- if (scan->u.bmu_bitmap & mask)
+ mask = bitrange(blk & BLIST_BMAP_MASK, count);
+ if (scan->bm_bitmap & mask)
panic("freeing free block");
- scan->u.bmu_bitmap |= mask;
-
- /*
- * We could probably do a better job here. We are required to make
- * 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).
- */
- scan->bm_bighint = BLIST_BMAP_RADIX;
+ scan->bm_bitmap |= mask;
}
/*
@@ -869,79 +842,37 @@ blst_leaf_free(blmeta_t *scan, daddr_t blk, int count)
static void
blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, u_daddr_t radix)
{
- daddr_t blk, i, next_skip, skip, v;
- int child;
+ daddr_t blk, endBlk, i, skip;
+ int digit, endDigit;
- if (scan->bm_bighint == (daddr_t)-1)
- panic("freeing invalid range");
- if (radix == BLIST_BMAP_RADIX)
- return (blst_leaf_free(scan, freeBlk, count));
- skip = radix_to_skip(radix);
- next_skip = skip / BLIST_META_RADIX;
-
- if (scan->u.bmu_avail == 0) {
- /*
- * ALL-ALLOCATED special case, with possible
- * shortcut to ALL-FREE special case.
- */
- scan->u.bmu_avail = count;
- scan->bm_bighint = count;
-
- if (count != radix) {
- for (i = 1; i < skip; i += next_skip) {
- if (scan[i].bm_bighint == (daddr_t)-1)
- break;
- scan[i].bm_bighint = 0;
- if (next_skip == 1) {
- scan[i].u.bmu_bitmap = 0;
- } else {
- scan[i].u.bmu_avail = 0;
- }
- }
- /* fall through */
- }
- } else {
- scan->u.bmu_avail += count;
- /* scan->bm_bighint = radix; */
- }
-
/*
- * ALL-FREE special case.
+ * We could probably do a better job here. We are required to make
+ * bighint at least as large as the biggest allocable block of data.
+ * If we just shoehorn it, a little extra overhead will be incurred
+ * on the next allocation (but only that one typically).
*/
+ scan->bm_bighint = BLIST_MAX_ALLOC;
- if (scan->u.bmu_avail == radix)
- return;
- if (scan->u.bmu_avail > radix)
- panic("blst_meta_free: freeing already free blocks (%lld) %lld/%lld",
- (long long)count, (long long)scan->u.bmu_avail,
- (long long)radix);
+ if (radix == BLIST_BMAP_RADIX)
+ return (blst_leaf_free(scan, freeBlk, count));
- /*
- * Break the free down into its components
- */
-
- blk = freeBlk & -radix;
+ endBlk = ummin(freeBlk + count, (freeBlk + radix) & -radix);
radix /= BLIST_META_RADIX;
-
- child = (freeBlk - blk) / radix;
- blk += child * radix;
- i = 1 + child * next_skip;
- while (i < skip && blk < freeBlk + count) {
- v = blk + radix - freeBlk;
- if (v > count)
- v = count;
- blst_meta_free(&scan[i], freeBlk, v, radix);
- if (scan->bm_bighint < scan[i].bm_bighint)
- scan->bm_bighint = scan[i].bm_bighint;
- count -= v;
- freeBlk += v;
+ skip = radix_to_skip(radix);
+ blk = freeBlk & -radix;
+ digit = (blk / radix) & BLIST_META_MASK;
+ endDigit = 1 + (((endBlk - 1) / radix) & BLIST_META_MASK);
+ scan->bm_bitmap |= bitrange(digit, endDigit - digit);
+ for (i = 1 + digit * skip; blk < endBlk; i += skip) {
blk += radix;
- i += next_skip;
+ count = ummin(blk, endBlk) - freeBlk;
+ blst_meta_free(&scan[i], freeBlk, count, radix);
+ freeBlk = blk;
}
}
/*
- * BLIST_RADIX_COPY() - copy one radix tree to another
+ * BLST_COPY() - copy one radix tree to another
*
* Locates free space in the source tree and frees it in the destination
* tree. The space may not already be free in the destination.
@@ -950,21 +881,21 @@ static void
blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, blist_t dest,
daddr_t count)
{
- daddr_t i, next_skip, skip;
+ daddr_t endBlk, i, skip;
/*
* Leaf node
*/
if (radix == BLIST_BMAP_RADIX) {
- u_daddr_t v = scan->u.bmu_bitmap;
+ u_daddr_t v = scan->bm_bitmap;
if (v == (u_daddr_t)-1) {
blist_free(dest, blk, count);
} else if (v != 0) {
int i;
- for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) {
+ for (i = 0; i < count; ++i) {
if (v & ((u_daddr_t)1 << i))
blist_free(dest, blk + i, 1);
}
@@ -976,42 +907,22 @@ blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
* Meta node
*/
- if (scan->u.bmu_avail == 0) {
+ if (scan->bm_bitmap == 0) {
/*
* Source all allocated, leave dest allocated
*/
return;
}
- if (scan->u.bmu_avail == radix) {
- /*
- * Source all free, free entire dest
- */
- if (count < radix)
- blist_free(dest, blk, count);
- else
- blist_free(dest, blk, radix);
- return;
- }
-
- skip = radix_to_skip(radix);
- next_skip = skip / BLIST_META_RADIX;
+ endBlk = blk + count;
radix /= 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, dest, radix);
- count -= radix;
- } else {
- if (count) {
- blst_copy(&scan[i], blk, radix, dest, count);
- }
- count = 0;
- }
+ skip = radix_to_skip(radix);
+ for (i = 1; blk < endBlk; i += skip) {
blk += radix;
+ count = radix;
+ if (blk >= endBlk)
+ count -= blk - endBlk;
+ blst_copy(&scan[i], blk - radix, radix, dest, count);
}
}
@@ -1027,16 +938,13 @@ blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count)
{
daddr_t nblks;
u_daddr_t mask;
- int n;
- n = blk & BLIST_BMAP_MASK;
- mask = ((u_daddr_t)-1 << n) &
- ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
+ mask = bitrange(blk & BLIST_BMAP_MASK, count);
/* Count the number of blocks that we are allocating. */
- nblks = bitcount64(scan->u.bmu_bitmap & mask);
+ nblks = bitcount64(scan->bm_bitmap & mask);
- scan->u.bmu_bitmap &= ~mask;
+ scan->bm_bitmap &= ~mask;
return (nblks);
}
@@ -1051,70 +959,27 @@ 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, u_daddr_t radix)
{
- daddr_t blk, i, nblks, next_skip, skip, v;
- int child;
+ daddr_t blk, endBlk, i, nblks, skip;
+ int digit;
- 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 = 0;
- return (nblks);
- }
+
+ endBlk = ummin(allocBlk + count, (allocBlk + radix) & -radix);
+ radix /= BLIST_META_RADIX;
skip = radix_to_skip(radix);
- next_skip = skip / BLIST_META_RADIX;
blk = allocBlk & -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;
-
- /*
- * 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 (next_skip == 1)
- scan[i].u.bmu_bitmap = (u_daddr_t)-1;
- else
- scan[i].u.bmu_avail = radix;
- scan[i].bm_bighint = radix;
- }
- } else {
- radix /= BLIST_META_RADIX;
- }
-
nblks = 0;
- child = (allocBlk - blk) / radix;
- blk += child * radix;
- i = 1 + child * next_skip;
- while (i < skip && blk < allocBlk + count) {
- v = blk + radix - allocBlk;
- if (v > count)
- v = count;
- nblks += blst_meta_fill(&scan[i], allocBlk, v, radix);
- count -= v;
- allocBlk += v;
+ while (blk < endBlk) {
+ digit = (blk / radix) & BLIST_META_MASK;
+ i = 1 + digit * skip;
blk += radix;
- i += next_skip;
+ count = ummin(blk, endBlk) - allocBlk;
+ nblks += blst_meta_fill(&scan[i], allocBlk, count, radix);
+ if (scan[i].bm_bitmap == 0)
+ scan->bm_bitmap &= ~((u_daddr_t)1 << digit);
+ allocBlk = blk;
}
- scan->u.bmu_avail -= nblks;
return (nblks);
}
@@ -1123,64 +988,44 @@ blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr
static void
blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab)
{
- daddr_t i, next_skip, skip;
+ daddr_t skip;
+ u_daddr_t bit, mask;
+ int digit;
if (radix == BLIST_BMAP_RADIX) {
printf(
- "%*.*s(%08llx,%lld): bitmap %016llx big=%lld\n",
+ "%*.*s(%08llx,%lld): bitmap %0*llx big=%lld\n",
tab, tab, "",
(long long)blk, (long long)radix,
- (long long)scan->u.bmu_bitmap,
+ 1 + (BLIST_BMAP_RADIX - 1) / 4,
+ (long long)scan->bm_bitmap,
(long long)scan->bm_bighint
);
return;
}
- if (scan->u.bmu_avail == 0) {
- printf(
- "%*.*s(%08llx,%lld) ALL ALLOCATED\n",
- tab, tab, "",
- (long long)blk,
- (long long)radix
- );
- return;
- }
- if (scan->u.bmu_avail == radix) {
- printf(
- "%*.*s(%08llx,%lld) ALL FREE\n",
- tab, tab, "",
- (long long)blk,
- (long long)radix
- );
- return;
- }
-
printf(
- "%*.*s(%08llx,%lld): subtree (%lld/%lld) big=%lld {\n",
+ "%*.*s(%08llx): subtree (%lld/%lld) bitmap %0*llx big=%lld {\n",
tab, tab, "",
(long long)blk, (long long)radix,
- (long long)scan->u.bmu_avail,
(long long)radix,
+ 1 + (BLIST_META_RADIX - 1) / 4,
+ (long long)scan->bm_bitmap,
(long long)scan->bm_bighint
);
- skip = radix_to_skip(radix);
- next_skip = skip / BLIST_META_RADIX;
radix /= BLIST_META_RADIX;
+ skip = radix_to_skip(radix);
tab += 4;
- for (i = 1; i < skip; i += next_skip) {
- if (scan[i].bm_bighint == (daddr_t)-1) {
- printf(
- "%*.*s(%08llx,%lld): Terminator\n",
- tab, tab, "",
- (long long)blk, (long long)radix
- );
- break;
- }
- blst_radix_print(&scan[i], blk, radix, tab);
- blk += radix;
- }
+ mask = scan->bm_bitmap;
+ /* Examine the nonempty subtree associated with each bit set in mask */
+ do {
+ bit = mask & -mask;
+ digit = bitpos(bit);
+ blst_radix_print(&scan[1 + digit * skip], blk + digit * radix,
+ radix, tab);
+ } while ((mask ^= bit) != 0);
tab -= 4;
printf(
@@ -1196,7 +1041,7 @@ blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t
int
main(int ac, char **av)
{
- int size = 1024;
+ int size = BLIST_META_RADIX * BLIST_BMAP_RADIX;
int i;
blist_t bl;
struct sbuf *s;
Modified: head/sys/sys/blist.h
==============================================================================
--- head/sys/sys/blist.h Tue Nov 13 18:21:47 2018 (r340401)
+++ head/sys/sys/blist.h Tue Nov 13 18:40:01 2018 (r340402)
@@ -73,22 +73,20 @@ typedef uint64_t u_daddr_t; /* unsigned disk address *
*/
typedef struct blmeta {
- union {
- daddr_t bmu_avail; /* space available under us */
- u_daddr_t bmu_bitmap; /* bitmap if we are a leaf */
- } u;
+ u_daddr_t bm_bitmap; /* bitmap if we are a leaf */
daddr_t bm_bighint; /* biggest contiguous block hint*/
} blmeta_t;
typedef struct blist {
daddr_t bl_blocks; /* area of coverage */
+ daddr_t bl_avail; /* # available blocks */
u_daddr_t bl_radix; /* coverage radix */
daddr_t bl_cursor; /* next-fit search starts at */
blmeta_t bl_root[1]; /* root of radix tree */
} *blist_t;
-#define BLIST_META_RADIX 16
#define BLIST_BMAP_RADIX (sizeof(u_daddr_t)*8)
+#define BLIST_META_RADIX BLIST_BMAP_RADIX
#define BLIST_MAX_ALLOC BLIST_BMAP_RADIX
More information about the svn-src-all
mailing list