On July 31, 2017, at 9:51 PM, Alan Cox <a...@freebsd.org> wrote:
>Author: alc >Date: Tue Aug 1 03:51:26 2017 >New Revision: 321840 >URL: https://svnweb.freebsd.org/changeset/base/321840 >Log: > The blist_meta_* routines that process a subtree take arguments 'radix' and > 'skip', which denote, respectively, the largest number of blocks that can be > managed by a subtree of that height, and one less than the number of nodes > in a subtree of that height. This change removes the 'skip' argument from > those functions because 'skip' can be trivially computed from 'radius'. > This change also redefines 'skip' so that it denotes the number of nodes in > the subtree, and so changes loop upper bound tests from '<= skip' to '< > skip' to account for the change. > > The 'skip' field is also removed from the blist struct. > > The self-test program is changed so that the print command includes the > cursor value in the output. > > Submitted by: Doug Moore <do...@rice.edu> > MFC after: 1 week >Modified: > head/sys/kern/subr_blist.c > head/sys/sys/blist.h >Modified: head/sys/kern/subr_blist.c >============================================================================== >--- head/sys/kern/subr_blist.c Tue Aug 1 03:40:19 2017 (r321839) >+++ head/sys/kern/subr_blist.c Tue Aug 1 03:51:26 2017 (r321840) >@@ -123,20 +123,19 @@ void panic(const char *ctl, ...); >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); >+ daddr_t radix, 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, daddr_t skip, daddr_t blk); >+ daddr_t radix, daddr_t blk); >static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, >- daddr_t skip, blist_t dest, daddr_t count); >+ blist_t dest, daddr_t count); >static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count); >static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, >- daddr_t radix, daddr_t skip, daddr_t blk); >-static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t skip, >- daddr_t count); >+ daddr_t radix, daddr_t blk); >+static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count); >#ifndef _KERNEL >static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, >- daddr_t skip, int tab); >+ int tab); >#endif >#ifdef _KERNEL >@@ -144,6 +143,28 @@ static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); >#endif >/* >+ * For a subtree that can represent the state of up to 'radix' blocks, the >+ * number of leaf nodes of the subtree is L=radix/BLIST_BMAP_RADIX. If 'm' >+ * is short for BLIST_META_RADIX, then for a tree of height h with L=m**h >+ * leaf nodes, the total number of tree nodes is 1 + m + m**2 + ... + m**h, >+ * or, equivalently, (m**(h+1)-1)/(m-1). This quantity is called 'skip' >+ * in the 'meta' functions that process subtrees. Since integer division >+ * discards remainders, we can express this computation as >+ * skip = (m * m**h) / (m - 1) >+ * skip = (m * radix / BLIST_BMAP_RADIX) / (m - 1) >+ * and if m divides BLIST_BMAP_RADIX, we can simplify further to >+ * skip = radix / (BLIST_BMAP_RADIX / m * (m - 1)) >+ * so that a simple integer division is enough for the calculation. >+ */ >+static inline daddr_t >+radix_to_skip(daddr_t radix) >+{ >+ >+ return (radix / >+ (BLIST_BMAP_RADIX / BLIST_META_RADIX * (BLIST_META_RADIX - 1))); I don't think this matches the comment. It is missing parens, no? Warner >+} >+ >+/* > * blist_create() - create a blist capable of handling up to the specified > * number of blocks > * >@@ -157,18 +178,16 @@ blist_t >blist_create(daddr_t blocks, int flags) >{ >blist_t bl; >- daddr_t nodes, radix, skip; >+ daddr_t nodes, radix; >/* >- * Calculate radix and skip field used for scanning. >+ * Calculate the radix field used for scanning. >*/ >radix = BLIST_BMAP_RADIX; >- skip = 0; >while (radix < blocks) { >radix *= BLIST_META_RADIX; >- skip = (skip + 1) * BLIST_META_RADIX; >} >- nodes = 1 + blst_radix_init(NULL, radix, skip, blocks); >+ nodes = 1 + blst_radix_init(NULL, radix, blocks); >bl = malloc(sizeof(struct blist), M_SWAP, flags); >if (bl == NULL) >@@ -176,14 +195,13 @@ blist_create(daddr_t blocks, int flags) >bl->bl_blocks = blocks; >bl->bl_radix = radix; >- bl->bl_skip = skip; >bl->bl_cursor = 0; >bl->bl_root = malloc(nodes * sizeof(blmeta_t), M_SWAP, flags); >if (bl->bl_root == NULL) { >free(bl, M_SWAP); >return (NULL); >} >- blst_radix_init(bl->bl_root, radix, skip, blocks); >+ blst_radix_init(bl->bl_root, radix, blocks); >#if defined(BLIST_DEBUG) >printf( >@@ -225,7 +243,7 @@ blist_alloc(blist_t bl, daddr_t count) >*/ >while (count <= bl->bl_root->bm_bighint) { >blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, >- bl->bl_skip, bl->bl_cursor); >+ bl->bl_cursor); >if (blk != SWAPBLK_NONE) { >bl->bl_cursor = blk + count; >return (blk); >@@ -257,7 +275,7 @@ void >blist_free(blist_t bl, daddr_t blkno, daddr_t count) >{ >- blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0); >+ blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, 0); >} >/* >@@ -270,8 +288,7 @@ daddr_t >blist_fill(blist_t bl, daddr_t blkno, daddr_t count) >{ >- return (blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix, >- bl->bl_skip, 0)); >+ return (blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix, 0)); >} >/* >@@ -290,7 +307,7 @@ blist_resize(blist_t *pbl, daddr_t count, int freenew, > *pbl = newbl; > if (count > save->bl_blocks) > count = save->bl_blocks; >- blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count); >+ blst_copy(save->bl_root, 0, save->bl_radix, newbl, count); > /* > * If resizing upwards, should we free the new space or not? >@@ -309,8 +326,8 @@ blist_resize(blist_t *pbl, daddr_t count, int freenew, >void >blist_print(blist_t bl) >{ >- printf("BLIST {\n"); >- blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); >+ printf("BLIST cursor = %08jx {\n", (uintmax_t)bl->bl_cursor); >+ blst_radix_print(bl->bl_root, 0, bl->bl_radix, 4); >printf("}\n"); >} >@@ -426,9 +443,9 @@ 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 skip, daddr_t cursor) >+ daddr_t cursor) >{ >- daddr_t i, next_skip, r; >+ daddr_t i, next_skip, r, skip; >int child; >bool scan_from_start; >@@ -443,6 +460,7 @@ blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t c >scan->bm_bighint = scan->u.bmu_avail; >return (SWAPBLK_NONE); >} >+ skip = radix_to_skip(radix); >next_skip = skip / BLIST_META_RADIX; >/* >@@ -456,7 +474,7 @@ blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t c >* 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) { >+ for (i = 1; i < skip; i += next_skip) { >if (next_skip == 1) >scan[i].u.bmu_bitmap = (u_daddr_t)-1; >else >@@ -477,13 +495,13 @@ blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t c >scan_from_start = cursor == blk; >child = (cursor - blk) / radix; >blk += child * radix; >- for (i = 1 + child * next_skip; i <= skip; i += next_skip) { >+ 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. >*/ >r = blst_meta_alloc(&scan[i], blk, count, radix, >- next_skip - 1, cursor > blk ? cursor : blk); >+ cursor > blk ? cursor : blk); >if (r != SWAPBLK_NONE) { >scan->u.bmu_avail -= count; >return (r); >@@ -552,15 +570,16 @@ blst_leaf_free(blmeta_t *scan, daddr_t blk, int count) > */ >static void >blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, daddr_t radix, >- daddr_t skip, daddr_t blk) >+ daddr_t blk) >{ >- daddr_t i, next_skip, v; >+ daddr_t i, next_skip, skip, v; >int child; >if (scan->bm_bighint == (daddr_t)-1) >panic("freeing invalid range"); >if (radix == BLIST_BMAP_RADIX) >return (blst_leaf_free(scan, freeBlk, count)); >+ skip = radix_to_skip(radix); >next_skip = skip / BLIST_META_RADIX; >if (scan->u.bmu_avail == 0) { >@@ -572,7 +591,7 @@ blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_ >scan->bm_bighint = count; >if (count != radix) { >- for (i = 1; i <= skip; i += next_skip) { >+ for (i = 1; i < skip; i += next_skip) { >if (scan[i].bm_bighint == (daddr_t)-1) >break; >scan[i].bm_bighint = 0; >@@ -609,11 +628,11 @@ blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_ >child = (freeBlk - blk) / radix; >blk += child * radix; >i = 1 + child * next_skip; >- while (i <= skip && blk < freeBlk + count) { >+ while (i < skip && blk < freeBlk + count) { >v = blk + radix - freeBlk; >if (v > count) >v = count; >- blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk); >+ blst_meta_free(&scan[i], freeBlk, v, radix, blk); >if (scan->bm_bighint < scan[i].bm_bighint) >scan->bm_bighint = scan[i].bm_bighint; >count -= v; >@@ -630,10 +649,10 @@ blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_ > * tree. The space may not already be free in the destination. > */ >static void >-blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, daddr_t skip, >- blist_t dest, daddr_t count) >+blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, blist_t dest, >+ daddr_t count) >{ >- daddr_t i, next_skip; >+ daddr_t i, next_skip, skip; >/* >* Leaf node >@@ -677,21 +696,20 @@ blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, >} >- radix /= BLIST_META_RADIX; >+ skip = radix_to_skip(radix); >next_skip = skip / BLIST_META_RADIX; >+ radix /= BLIST_META_RADIX; >- for (i = 1; count && i <= skip; i += next_skip) { >+ for (i = 1; count && i < skip; i += next_skip) { >if (scan[i].bm_bighint == (daddr_t)-1) >break; >if (count >= radix) { >- blst_copy(&scan[i], blk, radix, next_skip - 1, dest, >- radix); >+ blst_copy(&scan[i], blk, radix, dest, radix); >count -= radix; >} else { >if (count) { >- blst_copy(&scan[i], blk, radix, next_skip - 1, >- dest, count); >+ blst_copy(&scan[i], blk, radix, dest, count); >} >count = 0; >} >@@ -733,9 +751,9 @@ blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count) > */ >static daddr_t >blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, daddr_t radix, >- daddr_t skip, daddr_t blk) >+ daddr_t blk) >{ >- daddr_t i, nblks, next_skip, v; >+ daddr_t i, nblks, next_skip, skip, v; >int child; >if (scan->bm_bighint == (daddr_t)-1) >@@ -758,6 +776,7 @@ blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr >scan->bm_bighint = 0; >return (nblks); >} >+ skip = radix_to_skip(radix); >next_skip = skip / BLIST_META_RADIX; >/* >@@ -771,7 +790,7 @@ blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr >* 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) { >+ for (i = 1; i < skip; i += next_skip) { >if (next_skip == 1) >scan[i].u.bmu_bitmap = (u_daddr_t)-1; >else >@@ -786,12 +805,11 @@ blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr >child = (allocBlk - blk) / radix; >blk += child * radix; >i = 1 + child * next_skip; >- while (i <= skip && blk < allocBlk + count) { >+ while (i < skip && blk < allocBlk + count) { >v = blk + radix - allocBlk; >if (v > count) >v = count; >- nblks += blst_meta_fill(&scan[i], allocBlk, v, radix, >- next_skip - 1, blk); >+ nblks += blst_meta_fill(&scan[i], allocBlk, v, radix, blk); >count -= v; >allocBlk += v; >blk += radix; >@@ -810,9 +828,9 @@ blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr > * RADIX values we use. > */ >static daddr_t >-blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t skip, daddr_t count) >+blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count) >{ >- daddr_t i, memindex, next_skip; >+ daddr_t i, memindex, next_skip, skip; >memindex = 0; >@@ -839,17 +857,18 @@ blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t >scan->u.bmu_avail = 0; >} >- radix /= BLIST_META_RADIX; >+ skip = radix_to_skip(radix); >next_skip = skip / BLIST_META_RADIX; >+ radix /= BLIST_META_RADIX; >- for (i = 1; i <= skip; i += next_skip) { >+ for (i = 1; i < skip; i += next_skip) { >if (count >= radix) { >/* >* Allocate the entire object >*/ >memindex = i + > blst_radix_init(((scan) ? &scan[i] : NULL), radix, >- next_skip - 1, radix); >+ radix); >count -= radix; >} else if (count > 0) { >/* >@@ -857,7 +876,7 @@ blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t >*/ >memindex = i + > blst_radix_init(((scan) ? &scan[i] : NULL), radix, >- next_skip - 1, count); >+ count); >count = 0; >} else { >/* >@@ -876,10 +895,9 @@ blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t >#ifdef BLIST_DEBUG >static void >-blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, daddr_t skip, >- int tab) >+blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab) >{ >- daddr_t i, next_skip; >+ daddr_t i, next_skip, skip; >if (radix == BLIST_BMAP_RADIX) { >printf( >@@ -920,11 +938,12 @@ blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t > (long long)scan->bm_bighint >); >- radix /= BLIST_META_RADIX; >+ skip = radix_to_skip(radix); >next_skip = skip / BLIST_META_RADIX; >+ radix /= BLIST_META_RADIX; >tab += 4; >- for (i = 1; i <= skip; i += next_skip) { >+ for (i = 1; i < skip; i += next_skip) { >if (scan[i].bm_bighint == (daddr_t)-1) { >printf( > "%*.*s(%08llx,%lld): Terminator\n", >@@ -933,7 +952,7 @@ blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t >); >break; >} >- blst_radix_print(&scan[i], blk, radix, next_skip - 1, tab); >+ blst_radix_print(&scan[i], blk, radix, tab); >blk += radix; >} >tab -= 4; >Modified: head/sys/sys/blist.h >============================================================================== >--- head/sys/sys/blist.h Tue Aug 1 03:40:19 2017 (r321839) >+++ head/sys/sys/blist.h Tue Aug 1 03:51:26 2017 (r321840) >@@ -81,7 +81,6 @@ typedef struct blmeta { >typedef struct blist { >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; _______________________________________________ svn-src-head@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"