Skip site navigation (1)Skip section navigation (2)
Date:      Tue, 13 Jun 2017 17:49:49 +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: r319905 - in head/sys: kern sys
Message-ID:  <201706131749.v5DHnnVm006485@repo.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: alc
Date: Tue Jun 13 17:49:49 2017
New Revision: 319905
URL: https://svnweb.freebsd.org/changeset/base/319905

Log:
  Reduce the frequency of hint updates on allocation without incurring
  additional allocation overhead.  Previously, blst_meta_alloc() updated the
  hint after every successful allocation.  However, these "eager" hint
  updates are of no actual benefit if, instead, the "lazy" hint update at
  the start of blst_meta_alloc() is generalized to handle all cases where
  the number of available blocks is less than the requested allocation.
  Previously, the lazy hint update at the start of blst_meta_alloc() only
  handled the ALL-FULL case.  (I would also note that this change provides
  consistency between blist_alloc() and blist_fill() in that their hint
  maintenance is now entirely lazy.)
  
  Eliminate unnecessary checks for terminators in blst_meta_alloc() and
  blst_meta_fill() when handling ALL-FREE meta nodes.
  
  Eliminate the field "bl_free" from struct blist.  It is redundant.  Unless
  the entire radix tree is a single leaf, the count of free blocks is stored
  in the root node.  Instead, provide a function blist_avail() for obtaining
  the number of free blocks.
  
  In blst_meta_alloc(), perform a sanity check on the allocation once rather
  than repeating it in a loop over the meta node's children.
  
  In blst_leaf_fill(), use the optimized bitcount*() function instead of a
  loop to count the blocks being allocated.
  
  Add or improve several comments.
  
  Address some nearby style errors.
  
  Reviewed by:	kib
  MFC after:	6 weeks
  Differential Revision:	https://reviews.freebsd.org/D11146

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 Jun 13 16:19:32 2017	(r319904)
+++ head/sys/kern/subr_blist.c	Tue Jun 13 17:49:49 2017	(r319905)
@@ -106,6 +106,7 @@ __FBSDID("$FreeBSD$");
 #include <stdlib.h>
 #include <stdarg.h>
 
+#define	bitcount64(x)	__bitcount64((uint64_t)(x))
 #define malloc(a,b,c)	calloc(a, 1)
 #define free(a,b)	free(a)
 
@@ -169,7 +170,7 @@ blist_create(daddr_t blocks, int flags)
 		skip = (skip + 1) * BLIST_META_RADIX;
 	}
 
-	bl = malloc(sizeof(struct blist), M_SWAP, flags | M_ZERO);
+	bl = malloc(sizeof(struct blist), M_SWAP, flags);
 	if (bl == NULL)
 		return (NULL);
 
@@ -207,7 +208,7 @@ blist_destroy(blist_t bl)
 }
 
 /*
- * blist_alloc() - reserve space in the block bitmap.  Return the base
+ * blist_alloc() -   reserve space in the block bitmap.  Return the base
  *		     of a contiguous region or SWAPBLK_NONE if space could
  *		     not be allocated.
  */
@@ -215,20 +216,34 @@ blist_destroy(blist_t bl)
 daddr_t 
 blist_alloc(blist_t bl, daddr_t count)
 {
-	daddr_t blk = SWAPBLK_NONE;
+	daddr_t blk;
 
-	if (bl) {
+	if (bl != NULL && count <= bl->bl_root->bm_bighint) {
 		if (bl->bl_radix == BLIST_BMAP_RADIX)
 			blk = blst_leaf_alloc(bl->bl_root, 0, count);
 		else
-			blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip);
-		if (blk != SWAPBLK_NONE)
-			bl->bl_free -= count;
+			blk = blst_meta_alloc(bl->bl_root, 0, count,
+			    bl->bl_radix, bl->bl_skip);
+		return (blk);
 	}
-	return(blk);
+	return (SWAPBLK_NONE);
 }
 
 /*
+ * blist_avail() -	return the number of free blocks.
+ */
+
+daddr_t
+blist_avail(blist_t bl)
+{
+
+	if (bl->bl_radix == BLIST_BMAP_RADIX)
+		return (bitcount64(bl->bl_root->u.bmu_bitmap));
+	else
+		return (bl->bl_root->u.bmu_avail);
+}
+
+/*
  * blist_free() -	free up space in the block bitmap.  Return the base
  *		     	of a contiguous region.  Panic if an inconsistancy is
  *			found.
@@ -241,8 +256,8 @@ blist_free(blist_t bl, daddr_t blkno, daddr_t count)
 		if (bl->bl_radix == BLIST_BMAP_RADIX)
 			blst_leaf_free(bl->bl_root, blkno, count);
 		else
-			blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0);
-		bl->bl_free += count;
+			blst_meta_free(bl->bl_root, blkno, count,
+			    bl->bl_radix, bl->bl_skip, 0);
 	}
 }
 
@@ -264,10 +279,9 @@ blist_fill(blist_t bl, daddr_t blkno, daddr_t count)
 		else
 			filled = blst_meta_fill(bl->bl_root, blkno, count,
 			    bl->bl_radix, bl->bl_skip, 0);
-		bl->bl_free -= filled;
-		return filled;
-	} else
-		return 0;
+		return (filled);
+	}
+	return (0);
 }
 
 /*
@@ -417,27 +431,32 @@ blst_meta_alloc(
 	daddr_t radix, 
 	int skip
 ) {
+	daddr_t r;
 	int i;
 	int next_skip = ((u_int)skip / BLIST_META_RADIX);
 
-	if (scan->u.bmu_avail == 0)  {
+	if (scan->u.bmu_avail < count) {
 		/*
-		 * ALL-ALLOCATED special case
+		 * The meta node's hint must be too large if the allocation
+		 * exceeds the number of free blocks.  Reduce the hint, and
+		 * return failure.
 		 */
-		scan->bm_bighint = 0;
-		return(SWAPBLK_NONE);
+		scan->bm_bighint = scan->u.bmu_avail;
+		return (SWAPBLK_NONE);
 	}
 
+	/*
+	 * An ALL-FREE meta node requires special handling before allocating
+	 * any of its blocks.
+	 */
 	if (scan->u.bmu_avail == radix) {
 		radix /= BLIST_META_RADIX;
 
 		/*
-		 * ALL-FREE special case, initialize uninitialize
-		 * sublevel.
+		 * 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) {
-			if (scan[i].bm_bighint == (daddr_t)-1)
-				break;
 			if (next_skip == 1) {
 				scan[i].u.bmu_bitmap = (u_daddr_t)-1;
 				scan[i].bm_bighint = BLIST_BMAP_RADIX;
@@ -450,34 +469,33 @@ blst_meta_alloc(
 		radix /= BLIST_META_RADIX;
 	}
 
+	if (count > radix) {
+		/*
+		 * The allocation exceeds the number of blocks that are
+		 * managed by a subtree of this meta node.
+		 */
+		panic("allocation too large");
+	}
 	for (i = 1; i <= skip; i += next_skip) {
 		if (count <= scan[i].bm_bighint) {
 			/*
-			 * count fits in object
+			 * The allocation might fit in the i'th subtree.
 			 */
-			daddr_t r;
 			if (next_skip == 1) {
 				r = blst_leaf_alloc(&scan[i], blk, count);
 			} else {
-				r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1);
+				r = blst_meta_alloc(&scan[i], blk, count,
+				    radix, next_skip - 1);
 			}
 			if (r != SWAPBLK_NONE) {
 				scan->u.bmu_avail -= count;
-				if (scan->bm_bighint > scan->u.bmu_avail)
-					scan->bm_bighint = scan->u.bmu_avail;
-				return(r);
+				return (r);
 			}
 		} else if (scan[i].bm_bighint == (daddr_t)-1) {
 			/*
 			 * Terminator
 			 */
 			break;
-		} else if (count > radix) {
-			/*
-			 * count does not fit in object even if it were
-			 * complete free.
-			 */
-			panic("blist_meta_alloc: allocation too large");
 		}
 		blk += radix;
 	}
@@ -736,18 +754,16 @@ blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count)
 {
 	int n = blk & (BLIST_BMAP_RADIX - 1);
 	daddr_t nblks;
-	u_daddr_t mask, bitmap;
+	u_daddr_t mask;
 
 	mask = ((u_daddr_t)-1 << n) &
 	    ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
 
-	/* Count the number of blocks we're about to allocate */
-	bitmap = scan->u.bmu_bitmap & mask;
-	for (nblks = 0; bitmap != 0; nblks++)
-		bitmap &= bitmap - 1;
+	/* Count the number of blocks that we are allocating. */
+	nblks = bitcount64(scan->u.bmu_bitmap & mask);
 
 	scan->u.bmu_bitmap &= ~mask;
-	return nblks;
+	return (nblks);
 }
 
 /*
@@ -771,8 +787,13 @@ blst_meta_fill(
 	int next_skip = ((u_int)skip / BLIST_META_RADIX);
 	daddr_t nblks = 0;
 
-	if (count > radix)
-		panic("blist_meta_fill: allocation too large");
+	if (count > radix) {
+		/*
+		 * The allocation exceeds the number of blocks that are
+		 * managed by this meta node.
+		 */
+		panic("allocation too large");
+	}
 	if (count == radix || scan->u.bmu_avail == 0)  {
 		/*
 		 * ALL-ALLOCATED special case
@@ -783,15 +804,18 @@ blst_meta_fill(
 		return nblks;
 	}
 
+	/*
+	 * An ALL-FREE meta node requires special handling before allocating
+	 * any of its blocks.
+	 */
 	if (scan->u.bmu_avail == radix) {
 		radix /= BLIST_META_RADIX;
 
 		/*
-		 * ALL-FREE special case, initialize sublevel
+		 * 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) {
-			if (scan[i].bm_bighint == (daddr_t)-1)
-				break;
 			if (next_skip == 1) {
 				scan[i].u.bmu_bitmap = (u_daddr_t)-1;
 				scan[i].bm_bighint = BLIST_BMAP_RADIX;
@@ -1020,7 +1044,7 @@ main(int ac, char **av)
 		long long da = 0;
 		long long count = 0;
 
-		printf("%lld/%lld/%lld> ", (long long)bl->bl_free,
+		printf("%lld/%lld/%lld> ", (long long)blist_avail(bl),
 		    (long long)size, (long long)bl->bl_radix);
 		fflush(stdout);
 		if (fgets(buf, sizeof(buf), stdin) == NULL)

Modified: head/sys/sys/blist.h
==============================================================================
--- head/sys/sys/blist.h	Tue Jun 13 16:19:32 2017	(r319904)
+++ head/sys/sys/blist.h	Tue Jun 13 17:49:49 2017	(r319905)
@@ -82,7 +82,6 @@ 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_free;	/* number of free blocks	*/
 	blmeta_t	*bl_root;	/* root of radix tree		*/
 } *blist_t;
 
@@ -92,6 +91,7 @@ typedef struct blist {
 #define BLIST_MAX_ALLOC		BLIST_BMAP_RADIX
 
 daddr_t	blist_alloc(blist_t blist, daddr_t count);
+daddr_t	blist_avail(blist_t blist);
 blist_t	blist_create(daddr_t blocks, int flags);
 void	blist_destroy(blist_t blist);
 daddr_t	blist_fill(blist_t bl, daddr_t blkno, daddr_t count);



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201706131749.v5DHnnVm006485>