Skip site navigation (1)Skip section navigation (2)
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>