Page MenuHomeFreeBSD
Files F159095051

D11819.id.diff
No OneTemporary
Actions

D11819.id.diff
View Options

Index: head/sys/kern/subr_blist.c
===================================================================
--- head/sys/kern/subr_blist.c
+++ head/sys/kern/subr_blist.c
@@ -32,14 +32,17 @@
* try to interpret the meaning of a 'block' other than to return
* 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.
+ * A radix tree controls access to pieces of the bitmap, and includes
+ * auxiliary information at each interior node about the availabilty of
+ * contiguous free blocks in the subtree rooted at that node. Two radix
+ * constants are involved: one for the size of the bitmaps contained in the
+ * leaf nodes (BLIST_BMAP_RADIX), and one for the number of descendents of
+ * each of the meta (interior) nodes (BLIST_META_RADIX). 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
@@ -112,7 +115,7 @@
#define bitcount64(x) __bitcount64((uint64_t)(x))
#define malloc(a,b,c) calloc(a, 1)
#define free(a,b) free(a)
-#define CTASSERT(expr)
+static __inline int imax(int a, int b) { return (a > b ? a : b); }
#include <sys/blist.h>
@@ -123,8 +126,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 cursor, daddr_t count,
u_daddr_t radix);
static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
@@ -145,7 +147,9 @@
static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space");
#endif
-CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0);
+_Static_assert(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0,
+ "radix divisibility error");
+#define BLIST_BMAP_MASK (BLIST_BMAP_RADIX - 1)
#define BLIST_META_MASK (BLIST_META_RADIX - 1)
/*
@@ -575,33 +579,16 @@
* time is proportional to log2(count) + bitpos time.
*/
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, lo, num_shifts, range1, range_ext;
+ int count1, hi, lo, 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);
- }
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
@@ -609,27 +596,32 @@
* 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.
- */
- lo = cursor - blk;
- mask &= ~(u_daddr_t)0 << lo;
-
+ /* Discard any candidates that appear before blk. */
+ mask &= (u_daddr_t)-1 << (blk & BLIST_BMAP_MASK);
if (mask == 0)
return (SWAPBLK_NONE);
@@ -641,13 +633,58 @@
mask &= -mask;
lo = bitpos(mask);
- /*
- * Set in mask exactly the bits being allocated, and clear them from
- * the set of available bits.
- */
- mask = (mask << count) - mask;
+ 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) & ~((u_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 the 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 &= (u_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);
+ /* If this allocation uses all the bits, clear the hint. */
+ if (mask == scan->u.bmu_bitmap)
+ scan->bm_bighint = 0;
+ }
+ /* Clear the allocated bits from this leaf. */
scan->u.bmu_bitmap &= ~mask;
- return (blk + lo);
+ return ((blk & ~BLIST_BMAP_MASK) + lo);
}
/*
@@ -665,9 +702,8 @@
int child;
bool scan_from_start;
- blk = cursor & -radix;
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
@@ -677,6 +713,7 @@
scan->bm_bighint = scan->u.bmu_avail;
return (SWAPBLK_NONE);
}
+ blk = cursor & -radix;
skip = radix_to_skip(radix);
next_skip = skip / BLIST_META_RADIX;
@@ -715,7 +752,7 @@
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.
+ * The allocation might fit beginning in the i'th subtree.
*/
r = blst_meta_alloc(&scan[i],
cursor > blk ? cursor : blk, count, radix);
@@ -748,22 +785,20 @@
static void
blst_leaf_free(blmeta_t *scan, daddr_t blk, int count)
{
+ u_daddr_t mask;
+ int n;
+
/*
* free some data in this bitmap
- *
- * e.g.
- * 0000111111111110000
+ * mask=0000111111111110000
* \_________/\__/
- * v n
+ * count n
*/
- int n = blk & (BLIST_BMAP_RADIX - 1);
- u_daddr_t mask;
-
+ n = blk & BLIST_BMAP_MASK;
mask = ((u_daddr_t)-1 << n) &
((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
-
if (scan->u.bmu_bitmap & mask)
- panic("blst_radix_free: freeing free block");
+ panic("freeing free block");
scan->u.bmu_bitmap |= mask;
/*
@@ -944,10 +979,11 @@
static daddr_t
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;
+ int n;
+ n = blk & BLIST_BMAP_MASK;
mask = ((u_daddr_t)-1 << n) &
((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
@@ -1097,10 +1133,14 @@
count = 0;
} else {
/*
- * Add terminator and break out
+ * Add terminator and break out. Make terminator bitmap
+ * zero to avoid a spanning leaf allocation that
+ * includes the terminator.
*/
- if (scan)
+ if (scan) {
scan[i].bm_bighint = (daddr_t)-1;
+ scan[i].u.bmu_bitmap = 0;
+ }
break;
}
}

File Metadata

Mime Type
text/plain
Expires
Thu, Jun 11, 1:45 AM (13 h, 6 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
33863833
Default Alt Text
D11819.id.diff (9 KB)

Event Timeline