svn commit: r319905 - in head/sys: kern sys
Alan Cox
alc at FreeBSD.org
Tue Jun 13 17:49:51 UTC 2017
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);
More information about the svn-src-head
mailing list