Page MenuHomeFreeBSD
Files F144997703

D11819.id31592.diff
No OneTemporary
Actions

D11819.id31592.diff
View Options

Index: sys/kern/subr_blist.c
===================================================================
--- sys/kern/subr_blist.c
+++ sys/kern/subr_blist.c
@@ -33,13 +33,13 @@
* SWAPBLK_NONE on an allocation failure.
*
* A radix tree is used to maintain the bitmap. Two radix constants are
- * involved: One for the bitmaps contained in the leaf nodes (typically
- * 64), and one for the meta nodes (typically 16). Both meta and leaf
- * nodes have a hint field. This field gives us a hint as to the largest
- * free contiguous range of blocks under the node. It may contain a
- * value that is too high, but will never contain a value that is too
- * low. When the radix tree is searched, allocation failures in subtrees
- * update the hint.
+ * involved: One for the bitmaps contained in the leaf nodes (typically
+ * 64), and one for the meta nodes (typically 16). Each subtree is
+ * associated with a range of blocks. The root of any subtree stores a
+ * hint field that defines an upper bound on the size of the largest
+ * allocation that can begin in the associated block range. A hint is an
+ * 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
@@ -110,6 +110,7 @@
#define bitcount64(x) __bitcount64((uint64_t)(x))
#define malloc(a,b,c) calloc(a, 1)
#define free(a,b) free(a)
+#define imax(a,b) (((a)>(b))?(a):(b))
#define CTASSERT(expr)
#include <sys/blist.h>
@@ -121,8 +122,7 @@
/*
* static support functions
*/
-static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count,
- daddr_t cursor);
+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, daddr_t cursor);
static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
@@ -142,6 +142,7 @@
#ifdef _KERNEL
static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space");
#endif
+#define BLIST_META_MASK (BLIST_META_RADIX - 1)
CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
@@ -356,33 +357,17 @@
* time is proportional to log2(count) + log2(BLIST_BMAP_RADIX).
*/
static daddr_t
-blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count, daddr_t cursor)
+blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count)
{
u_daddr_t mask;
int count1, hi, lo, mid, num_shifts, range1, range_ext;
- if (count == BLIST_BMAP_RADIX) {
- /*
- * 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 (blk);
- }
+ lo = blk & (BLIST_BMAP_RADIX - 1);
range1 = 0;
count1 = count - 1;
num_shifts = fls(count1);
mask = scan->u.bmu_bitmap;
- while (mask != 0 && num_shifts > 0) {
+ 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
@@ -390,26 +375,34 @@
* 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.
+ * 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.
*/
num_shifts--;
range_ext = range1 + ((count1 >> num_shifts) & 1);
- mask &= mask >> range_ext;
+ /*
+ * mask is a signed quantity for the shift because when it is
+ * shifted right, the sign bit should copied; when the last
+ * block of the leaf is free, pretend, for a while, that all the
+ * blocks that follow it are also free.
+ */
+ mask &= (daddr_t)mask >> range_ext;
range1 += range_ext;
}
if (mask == 0) {
/*
* Update bighint. There is no allocation bigger than range1
- * available in this leaf.
+ * starting in this leaf.
*/
scan->bm_bighint = range1;
return (SWAPBLK_NONE);
}
/*
- * Discard any candidates that appear before the cursor.
+ * Discard any candidates that appear before blk.
*/
- lo = cursor - blk;
- mask &= ~(u_daddr_t)0 << lo;
+ mask &= (daddr_t)-1 << lo;
if (mask == 0)
return (SWAPBLK_NONE);
@@ -420,7 +413,8 @@
* and then perform a binary search to find its position.
*/
mask &= -mask;
- hi = BLIST_BMAP_RADIX - count1;
+ blk -= lo;
+ hi = BLIST_BMAP_RADIX;
while (lo + 1 < hi) {
mid = (lo + hi) >> 1;
if ((mask >> mid) != 0)
@@ -429,11 +423,64 @@
hi = mid;
}
+ hi = lo + count;
+ if (hi > BLIST_BMAP_RADIX) {
+ /*
+ * 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) {
+ /*
+ * 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.
+ */
+ scan->bm_bighint = imax(BLIST_BMAP_RADIX - lo, range1);
+ return (SWAPBLK_NONE);
+ }
+ hi -= BLIST_BMAP_RADIX;
+ if (((scan[1].u.bmu_bitmap + 1) & ~((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 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 &= (daddr_t)-1 << hi;
+
+ hi = BLIST_BMAP_RADIX;
+ }
+
+ /*
+ * Set the bits of mask at position 'lo' and higher.
+ */
+ mask = -mask;
+
+ if (hi == BLIST_BMAP_RADIX) {
+ /*
+ * Update bighint. There is no allocation bigger than range1
+ * available in this leaf after this allocation completes.
+ */
+ scan->bm_bighint = range1;
+ } else {
+ /*
+ * Clear the bits of mask at position 'hi' and higher.
+ */
+ mask &= (u_daddr_t)-1 >> (BLIST_BMAP_RADIX - hi);
+ }
+
/*
- * Set in mask exactly the bits being allocated, and clear them from
- * the set of available bits.
+ * Clear the allocated bits from this leaf.
*/
- mask = (mask << count) - mask;
scan->u.bmu_bitmap &= ~mask;
return (blk + lo);
}
@@ -455,7 +502,7 @@
bool scan_from_start;
if (radix == BLIST_BMAP_RADIX)
- return (blst_leaf_alloc(scan, blk, count, cursor));
+ 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

File Metadata

Mime Type
text/plain
Expires
Sun, Feb 15, 9:25 PM (16 h, 28 s)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
28756598
Default Alt Text
D11819.id31592.diff (7 KB)

Event Timeline