Page MenuHomeFreeBSD
Files F167337143

D11247.diff
No OneTemporary
Actions

D11247.diff
View Options

Index: head/sys/kern/subr_blist.c
===================================================================
--- head/sys/kern/subr_blist.c
+++ head/sys/kern/subr_blist.c
@@ -121,8 +121,8 @@
*/
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_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);
@@ -177,6 +177,7 @@
bl->bl_blocks = blocks;
bl->bl_radix = radix;
bl->bl_skip = skip;
+ bl->bl_cursor = 0;
nodes = 1 + blst_radix_init(NULL, radix, bl->bl_skip, blocks);
bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags);
if (bl->bl_root == NULL) {
@@ -218,13 +219,23 @@
{
daddr_t blk;
- if (bl != NULL && count <= bl->bl_root->bm_bighint) {
+ /*
+ * 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) {
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);
- return (blk);
+ 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 (SWAPBLK_NONE);
}
@@ -424,16 +435,12 @@
*/
static daddr_t
-blst_meta_alloc(
- blmeta_t *scan,
- daddr_t blk,
- daddr_t count,
- daddr_t radix,
- int skip
-) {
- daddr_t r;
- 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 < count) {
/*
@@ -444,6 +451,7 @@
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
@@ -457,13 +465,11 @@
* meta node cannot have a terminator in any subtree.
*/
for (i = 1; i <= skip; i += next_skip) {
- 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;
@@ -476,7 +482,10 @@
*/
panic("allocation too large");
}
- for (i = 1; i <= skip; i += next_skip) {
+ 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) {
/*
* The allocation might fit in the i'th subtree.
@@ -485,7 +494,8 @@
r = blst_leaf_alloc(&scan[i], blk, count);
} else {
r = blst_meta_alloc(&scan[i], blk, count,
- radix, next_skip - 1);
+ radix, next_skip - 1, cursor > blk ?
+ cursor : blk);
}
if (r != SWAPBLK_NONE) {
scan->u.bmu_avail -= count;
@@ -503,9 +513,10 @@
/*
* 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);
}
/*
Index: head/sys/sys/blist.h
===================================================================
--- head/sys/sys/blist.h
+++ head/sys/sys/blist.h
@@ -82,6 +82,7 @@
daddr_t bl_blocks; /* area of coverage */
daddr_t bl_radix; /* coverage radix */
daddr_t bl_skip; /* starting skip */
+ daddr_t bl_cursor; /* next-fit search starts at */
blmeta_t *bl_root; /* root of radix tree */
} *blist_t;

File Metadata

Mime Type
text/plain
Expires
Sat, Aug 22, 12:53 AM (10 h, 6 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
37061799
Default Alt Text
D11247.diff (4 KB)

Event Timeline