Page MenuHomeFreeBSD
Files F173867314

D11146.id29557.diff
No OneTemporary
Actions

D11146.id29557.diff
View Options

Index: head/sys/kern/subr_blist.c
===================================================================
--- head/sys/kern/subr_blist.c
+++ head/sys/kern/subr_blist.c
@@ -106,6 +106,7 @@
#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 @@
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_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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
{
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 @@
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 @@
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 @@
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)
Index: head/sys/sys/blist.h
===================================================================
--- head/sys/sys/blist.h
+++ head/sys/sys/blist.h
@@ -82,7 +82,6 @@
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 @@
#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);

File Metadata

Mime Type
text/plain
Expires
Wed, Sep 30, 12:09 AM (3 h, 52 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
39907132
Default Alt Text
D11146.id29557.diff (7 KB)

Event Timeline