Skip site navigation (1)Skip section navigation (2) 
Date:      Fri, 10 May 2019 22:49:01 +0000 (UTC)
From:      Doug Moore <dougm@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org
Subject:   svn commit: r347469 - head/sys/kern
Message-ID:  <201905102249.x4AMn1Wp078242@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help 
Author: dougm
Date: Fri May 10 22:49:01 2019
New Revision: 347469
URL: https://svnweb.freebsd.org/changeset/base/347469

Log:
  When bitpos can't be implemented with an inline ffs* instruction,
  change the binary search so that it does not depend on a single bit
  only being set in the bitmask. Use bitpos more generally, and avoid
  some clearing of bits to accommodate its current behavior.
  
  Approved by: kib (mentor)
  Differential Revision: https://reviews.freebsd.org/D20232

Modified:
  head/sys/kern/subr_blist.c

Modified: head/sys/kern/subr_blist.c
==============================================================================
--- head/sys/kern/subr_blist.c	Fri May 10 22:02:29 2019	(r347468)
+++ head/sys/kern/subr_blist.c	Fri May 10 22:49:01 2019	(r347469)
@@ -192,31 +192,41 @@ bitrange(int n, int count)
 
 
 /*
- * Use binary search, or a faster method, to find the 1 bit in a u_daddr_t.
- * Assumes that the argument has only one bit set.
+ * Find the first bit set in a u_daddr_t.
  */
 static inline int
-bitpos(u_daddr_t mask)
+generic_bitpos(u_daddr_t mask)
 {
 	int hi, lo, mid;
 
-	switch (sizeof(mask)) {
+	lo = 0;
+	hi = BLIST_BMAP_RADIX;
+	while (lo + 1 < hi) {
+		mid = (lo + hi) >> 1;
+		if (mask & bitrange(0, mid))
+			hi = mid;
+		else
+			lo = mid;
+	}
+	return (lo);
+}
+
+static inline int
+bitpos(u_daddr_t mask)
+{
+
+	return (_Generic(mask,
 #ifdef HAVE_INLINE_FFSLL
-	case sizeof(long long):
-		return (ffsll(mask) - 1);
+	    long long: ffsll(mask) - 1,
 #endif
-	default:
-		lo = 0;
-		hi = BLIST_BMAP_RADIX;
-		while (lo + 1 < hi) {
-			mid = (lo + hi) >> 1;
-			if ((mask >> mid) != 0)
-				lo = mid;
-			else
-				hi = mid;
-		}
-		return (lo);
-	}
+#ifdef HAVE_INLINE_FFSL
+	    long: ffsl(mask) - 1,
+#endif
+#ifdef HAVE_INLINE_FFS
+	    int: ffs(mask) - 1,
+#endif
+	    default: generic_bitpos(mask)
+	));
 }
 
 /*
@@ -532,7 +542,8 @@ blist_stats(blist_t bl, struct sbuf *s)
 	struct gap_stats gstats;
 	struct gap_stats *stats = &gstats;
 	daddr_t i, nodes, radix;
-	u_daddr_t bit, diff, mask;
+	u_daddr_t diff, mask;
+	int digit;
 
 	init_gap_stats(stats);
 	nodes = 0;
@@ -570,9 +581,9 @@ blist_stats(blist_t bl, struct sbuf *s)
 			if (gap_stats_counting(stats))
 				diff ^= 1;
 			while (diff != 0) {
-				bit = diff & -diff;
-				update_gap_stats(stats, i + bitpos(bit));
-				diff ^= bit;
+				digit = bitpos(diff);
+				update_gap_stats(stats, i + digit);
+				diff ^= bitrange(digit, 1);
 			}
 		}
 		nodes += radix_to_skip(radix);
@@ -776,7 +787,7 @@ static daddr_t
 blst_meta_alloc(blmeta_t *scan, daddr_t cursor, daddr_t count, u_daddr_t radix)
 {
 	daddr_t blk, i, r, skip;
-	u_daddr_t bit, mask;
+	u_daddr_t mask;
 	bool scan_from_start;
 	int digit;
 
@@ -808,8 +819,7 @@ blst_meta_alloc(blmeta_t *scan, daddr_t cursor, daddr_
 	 * Examine the nonempty subtree associated with each bit set in mask.
 	 */
 	do {
-		bit = mask & -mask;
-		digit = bitpos(bit);
+		digit = bitpos(mask);
 		i = 1 + digit * skip;
 		if (count <= scan[i].bm_bighint) {
 			/*
@@ -819,12 +829,12 @@ blst_meta_alloc(blmeta_t *scan, daddr_t cursor, daddr_
 			    count, radix);
 			if (r != SWAPBLK_NONE) {
 				if (scan[i].bm_bitmap == 0)
-					scan->bm_bitmap ^= bit;
+					scan->bm_bitmap ^= bitrange(digit, 1);
 				return (r);
 			}
 		}
 		cursor = blk;
-	} while ((mask ^= bit) != 0);
+	} while ((mask ^= bitrange(digit, 1)) != 0);
 
 	/*
 	 * We couldn't allocate count in this subtree.  If the whole tree was
@@ -1019,7 +1029,7 @@ static void
 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int tab)
 {
 	daddr_t skip;
-	u_daddr_t bit, mask;
+	u_daddr_t mask;
 	int digit;
 
 	if (radix == BLIST_BMAP_RADIX) {
@@ -1051,11 +1061,10 @@ blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t 
 	mask = scan->bm_bitmap;
 	/* Examine the nonempty subtree associated with each bit set in mask */
 	do {
-		bit = mask & -mask;
-		digit = bitpos(bit);
+		digit = bitpos(mask);
 		blst_radix_print(&scan[1 + digit * skip], blk + digit * radix,
 		    radix, tab);
-	} while ((mask ^= bit) != 0);
+	} while ((mask ^= bitrange(digit, 1)) != 0);
 	tab -= 4;
 
 	printf(

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