svn commit: r321840 - in head/sys: kern sys
Warner Losh
wlosh at bsdimp.com
Tue Aug 1 04:20:33 UTC 2017
On July 31, 2017, at 9:51 PM, Alan Cox <alc at 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 at 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;
More information about the svn-src-head
mailing list