Page MenuHomeFreeBSD
Files F172444130

D11426.diff
No OneTemporary
Actions

D11426.diff
View Options

Index: head/sys/kern/subr_blist.c
===================================================================
--- head/sys/kern/subr_blist.c
+++ head/sys/kern/subr_blist.c
@@ -121,7 +121,8 @@
* static support functions
*/
-static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count);
+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);
@@ -227,7 +228,8 @@
*/
while (count <= bl->bl_root->bm_bighint) {
if (bl->bl_radix == BLIST_BMAP_RADIX)
- blk = blst_leaf_alloc(bl->bl_root, 0, count);
+ blk = blst_leaf_alloc(bl->bl_root, 0, count,
+ bl->bl_cursor);
else
blk = blst_meta_alloc(bl->bl_root, 0, count,
bl->bl_radix, bl->bl_skip, bl->bl_cursor);
@@ -352,77 +354,92 @@
/*
* 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;
+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 (orig == 0) {
+ 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 &= ~((u_daddr_t)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);
}
/*
@@ -491,7 +508,8 @@
* The allocation might fit in the i'th subtree.
*/
if (next_skip == 1) {
- r = blst_leaf_alloc(&scan[i], blk, count);
+ r = blst_leaf_alloc(&scan[i], blk, count,
+ cursor > blk ? cursor : blk);
} else {
r = blst_meta_alloc(&scan[i], blk, count,
radix, next_skip - 1, cursor > blk ?

File Metadata

Mime Type
text/plain
Expires
Sat, Sep 19, 12:29 PM (6 h, 2 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
39224466
Default Alt Text
D11426.diff (5 KB)

Event Timeline