Date: Sun, 17 Sep 2017 16:45:50 +0000 (UTC) From: Alan Cox <alc@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-11@freebsd.org Subject: svn commit: r323681 - in stable/11/sys: kern sys Message-ID: <201709171645.v8HGjoKV046764@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: alc Date: Sun Sep 17 16:45:50 2017 New Revision: 323681 URL: https://svnweb.freebsd.org/changeset/base/323681 Log: MFC r321840,322041 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. In case readers are misled by expressions that combine multiplication and division, add parentheses to make the precedence explicit. Modified: stable/11/sys/kern/subr_blist.c stable/11/sys/sys/blist.h Directory Properties: stable/11/ (props changed) Modified: stable/11/sys/kern/subr_blist.c ============================================================================== --- stable/11/sys/kern/subr_blist.c Sun Sep 17 16:45:12 2017 (r323680) +++ stable/11/sys/kern/subr_blist.c Sun Sep 17 16:45:50 2017 (r323681) @@ -110,6 +110,7 @@ __FBSDID("$FreeBSD$"); #define bitcount64(x) __bitcount64((uint64_t)(x)) #define malloc(a,b,c) calloc(a, 1) #define free(a,b) free(a) +#define CTASSERT(expr) #include <sys/blist.h> @@ -123,27 +124,52 @@ 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 static MALLOC_DEFINE(M_SWAP, "SWAP", "Swap space"); #endif +CTASSERT(BLIST_BMAP_RADIX % BLIST_META_RADIX == 0); + /* + * 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 since m divides BLIST_BMAP_RADIX, we can simplify further to + * skip = (radix / (BLIST_BMAP_RADIX / m)) / (m - 1) + * skip = radix / ((BLIST_BMAP_RADIX / m) * (m - 1)) + * so that simple integer division by a constant can safely be used 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 +183,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 +200,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 +248,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 +280,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 +293,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 +312,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 +331,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 +448,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 +465,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 +479,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 +500,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 +575,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 +596,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 +633,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 +654,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 +701,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 +756,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 +781,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 +795,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 +810,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 +833,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 +862,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 +881,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 +900,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 +943,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 +957,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: stable/11/sys/sys/blist.h ============================================================================== --- stable/11/sys/sys/blist.h Sun Sep 17 16:45:12 2017 (r323680) +++ stable/11/sys/sys/blist.h Sun Sep 17 16:45:50 2017 (r323681) @@ -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?201709171645.v8HGjoKV046764>