Skip site navigation (1)Skip section navigation (2)
Date:      Tue, 1 Aug 2017 03:51:27 +0000 (UTC)
From:      Alan Cox <alc@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r321840 - in head/sys: kern sys
Message-ID:  <201708010351.v713pRAJ007139@repo.freebsd.org>

next in thread | raw e-mail | index | archive | help
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)));
+}
+
+/*
  * 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?201708010351.v713pRAJ007139>