Re: svn commit: r321840 - in head/sys: kern sys

[Alan Cox]

On 07/31/2017 23:20, Warner Losh wrote:
>
> On July 31, 2017, at 9:51 PM, Alan Cox  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 
> >  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;
> 

Re: svn commit: r321840 - in head/sys: kern sys

[Warner Losh]

On July 31, 2017, at 9:51 PM, Alan Cox  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 
>  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 =