Date: Tue, 1 Aug 2017 03:51:27 +0000 (UTC) From: Alan Cox <alc@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r321840 - in head/sys: kern sys Message-ID: <201708010351.v713pRAJ007139@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
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 <dougm@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))); +} + +/* * 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;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201708010351.v713pRAJ007139>