Date: Mon, 31 Jul 2017 23:26:53 -0500 From: Alan Cox <alc@rice.edu> To: Warner Losh <wlosh@bsdimp.com>, Alan Cox <alc@freebsd.org>, "src-committers@freebsd.org" <src-committers@freebsd.org>, "svn-src-all@freebsd.org" <svn-src-all@freebsd.org>, "svn-src-head@freebsd.org" <svn-src-head@freebsd.org> Subject: Re: svn commit: r321840 - in head/sys: kern sys Message-ID: <5cc355e9-817c-1b61-14f5-59270d7cba9a@rice.edu> In-Reply-To: <5lny7794f8b19a2l8vlaannr.1501561229506@email.android.com> References: <5lny7794f8b19a2l8vlaannr.1501561229506@email.android.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 07/31/2017 23:20, Warner Losh wrote: > > On July 31, 2017, at 9:51 PM, Alan Cox <alc@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 <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))); > > I don't think this matches the comment. It is missing parens,no? > > Substitute BLIST_META_RADIX for 'm' in the comment and they match. (The second line of the comment defines 'm' to be BLIST_META_RADIX.) > >+} > >+ > >+/* > > * 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?5cc355e9-817c-1b61-14f5-59270d7cba9a>