git: 84e2ae64c597 - main - vm_reserv: use enhanced bitstring for popmaps

From: Doug Moore <dougm_at_FreeBSD.org>
Date: Wed, 12 Jan 2022 17:16:10 UTC
The branch main has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=84e2ae64c597000a0152c6772b2c8925773c6f6c

commit 84e2ae64c597000a0152c6772b2c8925773c6f6c
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2022-01-12 17:03:53 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2022-01-12 17:03:53 +0000

    vm_reserv: use enhanced bitstring for popmaps
    
    vm_reserv.c uses its own bitstring implemenation for popmaps. Using
    the bitstring_t type from a standard header eliminates the code
    duplication, allows some bit-at-a-time operations to be replaced with
    more efficient bitstring range operations, and, in
    vm_reserv_test_contig, allows bit_ffc_area_at to more efficiently
    search for a big-enough set of consecutive zero-bits.
    
    Make bitstring changes improve the vm_reserv code.  Define a bit_ntest
    method to test whether a range of bits is all set, or all clear.
    Define bit_ff_at and bit_ff_area_at to implement the ffs and ffc
    versions with a parameter to choose between set- and clear- bits.
    Improve the area_at implementation.  Modify the bit_nset and
    bit_nclear implementations to allow code optimization in the cases
    when start or end are multiples of _BITSTR_BITS.
    
    Add a few new cases to bitstring_test.
    
    Discussed with: alc
    Reviewed by:    markj
    Tested by:      pho (earlier version)
    Differential Revision:  https://reviews.freebsd.org/D33312
---
 share/man/man3/bitstring.3     |  63 +++++++++++
 sys/sys/bitstring.h            | 234 +++++++++++++++++++----------------------
 sys/vm/vm_reserv.c             | 201 ++++++++---------------------------
 tests/sys/sys/bitstring_test.c |  27 +++--
 4 files changed, 234 insertions(+), 291 deletions(-)

diff --git a/share/man/man3/bitstring.3 b/share/man/man3/bitstring.3
index e5be67a89e4f..c6f0dfe45c12 100644
--- a/share/man/man3/bitstring.3
+++ b/share/man/man3/bitstring.3
@@ -68,14 +68,17 @@
 .Nm bit_decl ,
 .Nm bit_ffc ,
 .Nm bit_ffs ,
+.Nm bit_ff_at ,
 .Nm bit_ffc_at ,
 .Nm bit_ffs_at ,
 .Nm bit_ffc_area ,
 .Nm bit_ffs_area ,
+.Nm bit_ff_area_at ,
 .Nm bit_ffc_area_at ,
 .Nm bit_ffs_area_at ,
 .Nm bit_nclear ,
 .Nm bit_nset ,
+.Nm bit_ntest ,
 .Nm bit_set ,
 .Nm bit_test ,
 .Nm bitstr_size
@@ -99,6 +102,8 @@
 .Ft void
 .Fn bit_ffs_at "bitstr_t *name" "int start" "int nbits" "int *value"
 .Ft void
+.Fn bit_ff_at "bitstr_t *name" "int start" "int nbits" "int match" "int *value"
+.Ft void
 .Fn bit_ffc_area "bitstr_t *name" "int nbits" "int size" "int *value"
 .Ft void
 .Fn bit_ffs_area "bitstr_t *name" "int nbits" "int size" "int *value"
@@ -106,6 +111,8 @@
 .Fn bit_ffc_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value"
 .Ft void
 .Fn bit_ffs_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value"
+.Ft void
+.Fn bit_ff_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int match" "int *value"
 .Fn bit_foreach "bitstr_t *name" "int nbits" "int var"
 .Fn bit_foreach_at "bitstr_t *name" "int start" "int nbits" "int var"
 .Fn bit_foreach_unset "bitstr_t *name" "int nbits" "int var"
@@ -114,6 +121,8 @@
 .Fn bit_nclear "bitstr_t *name" "int start" "int stop"
 .Ft void
 .Fn bit_nset "bitstr_t *name" "int start" "int stop"
+.Ft int
+.Fn bit_ntest "bitstr_t *name" "int start" "int stop" "int match"
 .Ft void
 .Fn bit_set "bitstr_t *name" "int bit"
 .Ft int
@@ -186,6 +195,18 @@ of bit string
 .Fa name
 is set, and zero otherwise.
 .Pp
+The
+.Fn bit_ntest
+function
+evaluates to non-zero if the zero-based numbered bits from
+.Fa start
+through
+.Fa stop
+in the bit string
+.Ar name
+all have the value
+.Ar match .
+.Pp
 The function
 .Fn bit_ffc
 stores in the location referenced by
@@ -245,6 +266,25 @@ the location referenced by
 is set to \-1.
 .Pp
 The
+.Fn bit_ff_at
+function
+stores in the location referenced by
+.Fa value
+the zero-based number of the first bit in the array of
+.Fa nbits
+bits referenced by
+.Fa name ,
+at or after the zero-based bit index
+.Fa start
+that has value
+.Fa match .
+If no bits after
+.Fa start
+match that value, the location referenced by
+.Fa value
+is set to \-1.
+.Pp
+The
 .Fn bit_ffc_area
 function stores in the location referenced by
 .Fa value
@@ -321,6 +361,29 @@ the location referenced by
 is set to \-1.
 .Pp
 The
+.Fn bit_ff_area_at
+function stores in the location referenced by
+.Fa value
+the zero-based number of the first bit beginning a sequence of bits of
+at least
+.Fa size
+bits in the array of
+.Fa nbits
+bits referenced by
+.Fa name ,
+at or after the zero-based bit index
+.Fa start 
+in which all bits have the value
+.Fa match .
+If no sequence of contiguous such bits of the specified
+.Fa size
+can be found at or after
+.Fa start ,
+the location referenced by
+.Fa value
+is set to \-1.
+.Pp
+The
 .Fn bit_count
 function stores in the location referenced by
 .Fa value
diff --git a/sys/sys/bitstring.h b/sys/sys/bitstring.h
index f898a2392be6..13d87ce418ea 100644
--- a/sys/sys/bitstring.h
+++ b/sys/sys/bitstring.h
@@ -155,6 +155,34 @@ bit_clear(bitstr_t *_bitstr, int _bit)
 	_bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
 }
 
+/* Are bits in [start ... stop] in bit string all 0 or all 1? */
+static inline int
+bit_ntest(const bitstr_t *_bitstr, int _start, int _stop, int _match)
+{
+	const bitstr_t *_stopbitstr;
+	bitstr_t _mask;
+
+	_mask = (_match == 0) ? 0 : _BITSTR_MASK;
+	_stopbitstr = _bitstr + _bit_idx(_stop);
+	_bitstr += _bit_idx(_start);
+
+	if (_bitstr == _stopbitstr)
+		return (0 == ((*_bitstr ^ _mask) &
+		    _bit_make_mask(_start, _stop)));
+	if (_bit_offset(_start) != 0 &&
+	    0 != ((*_bitstr++ ^ _mask) &
+	    _bit_make_mask(_start, _BITSTR_BITS - 1)))
+		return (0);
+	if (_bit_offset(_stop) == _BITSTR_BITS - 1)
+		++_stopbitstr;
+	while (_bitstr < _stopbitstr) {
+		if (*_bitstr++ != _mask)
+			return (0);
+	}
+	return (_bit_offset(_stop) == _BITSTR_BITS - 1 ||
+	    0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop)));
+}
+
 /* Set bits start ... stop inclusive in bit string. */
 static inline void
 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
@@ -167,10 +195,14 @@ bit_nset(bitstr_t *_bitstr, int _start, int _stop)
 	if (_bitstr == _stopbitstr) {
 		*_bitstr |= _bit_make_mask(_start, _stop);
 	} else {
-		*_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
-		while (++_bitstr < _stopbitstr)
-	    		*_bitstr = _BITSTR_MASK;
-		*_stopbitstr |= _bit_make_mask(0, _stop);
+		if (_bit_offset(_start) != 0)
+			*_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1);
+		if (_bit_offset(_stop) == _BITSTR_BITS - 1)
+			++_stopbitstr;
+		while (_bitstr < _stopbitstr)
+			*_bitstr++ = _BITSTR_MASK;
+		if (_bit_offset(_stop) != _BITSTR_BITS - 1)
+			*_stopbitstr |= _bit_make_mask(0, _stop);
 	}
 }
 
@@ -186,79 +218,62 @@ bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
 	if (_bitstr == _stopbitstr) {
 		*_bitstr &= ~_bit_make_mask(_start, _stop);
 	} else {
-		*_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
-		while (++_bitstr < _stopbitstr)
-			*_bitstr = 0;
-		*_stopbitstr &= ~_bit_make_mask(0, _stop);
+		if (_bit_offset(_start) != 0)
+			*_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
+		if (_bit_offset(_stop) == _BITSTR_BITS - 1)
+			++_stopbitstr;
+		while (_bitstr < _stopbitstr)
+			*_bitstr++ = 0;
+		if (_bit_offset(_stop) != _BITSTR_BITS - 1)
+			*_stopbitstr &= ~_bit_make_mask(0, _stop);
 	}
 }
 
-/* Find the first bit set in bit string at or after bit start. */
+/* Find the first '_match'-bit in bit string at or after bit start. */
 static inline void
-bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
+bit_ff_at(bitstr_t *_bitstr, int _start, int _nbits, int _match,
+    int *_result)
 {
 	bitstr_t *_curbitstr;
 	bitstr_t *_stopbitstr;
+	bitstr_t _mask;
 	bitstr_t _test;
-	int _value, _offset;
+	int _value;
 
-	if (_start >= _nbits) {
+	if (_start >= _nbits || _nbits <= 0) {
 		*_result = -1;
 		return;
 	}
 
-	if (_nbits > 0) {
-		_curbitstr = _bitstr + _bit_idx(_start);
-		_stopbitstr = _bitstr + _bit_idx(_nbits - 1);
+	_curbitstr = _bitstr + _bit_idx(_start);
+	_stopbitstr = _bitstr + _bit_idx(_nbits - 1);
+	_mask = _match ? 0 : _BITSTR_MASK;
 
-		_test = *_curbitstr;
-		if (_bit_offset(_start) != 0)
-			_test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
-		while (_test == 0 && _curbitstr < _stopbitstr)
-			_test = *(++_curbitstr);
+	_test = _mask ^ *_curbitstr;
+	if (_bit_offset(_start) != 0)
+		_test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
+	while (_test == 0 && _curbitstr < _stopbitstr)
+		_test = _mask ^ *(++_curbitstr);
 
-		_offset = ffsl(_test);
-		_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
-		if (_offset == 0 || _value >= _nbits)
-			_value = -1;
-	} else {
+	_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1;
+	if (_test == 0 ||
+	    (_bit_offset(_nbits) != 0 && _value >= _nbits))
 		_value = -1;
-	}
 	*_result = _value;
 }
 
+/* Find the first bit set in bit string at or after bit start. */
+static inline void
+bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
+{
+	bit_ff_at(_bitstr, _start, _nbits, 1, _result);
+}
+
 /* Find the first bit clear in bit string at or after bit start. */
 static inline void
 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
 {
-	bitstr_t *_curbitstr;
-	bitstr_t *_stopbitstr;
-	bitstr_t _test;
-	int _value, _offset;
-
-	if (_start >= _nbits) {
-		*_result = -1;
-		return;
-	}
-
-	if (_nbits > 0) {
-		_curbitstr = _bitstr + _bit_idx(_start);
-		_stopbitstr = _bitstr + _bit_idx(_nbits - 1);
-
-		_test = *_curbitstr;
-		if (_bit_offset(_start) != 0)
-			_test |= _bit_make_mask(0, _start - 1);
-		while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
-			_test = *(++_curbitstr);
-
-		_offset = ffsl(~_test);
-		_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
-		if (_offset == 0 || _value >= _nbits)
-			_value = -1;
-	} else {
-		_value = -1;
-	}
-	*_result = _value;
+	bit_ff_at(_bitstr, _start, _nbits, 0, _result);
 }
 
 /* Find the first bit set in bit string. */
@@ -275,98 +290,65 @@ bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
 	bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
 }
 
-/* Find contiguous sequence of at least size set bits at or after start */
+/* Find contiguous sequence of at least size '_match'-bits at or after start */
 static inline void
-bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
-    int *_result)
+bit_ff_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
+    int _match, int *_result)
 {
-	bitstr_t *_curbitstr;
-	bitstr_t _test;
-	int _value, _offset, _logsize, _b;
+	bitstr_t *_curbitstr, _mask, _test;
+	int _value, _last, _shft, _maxshft;
 
 	if (_start + _size > _nbits || _nbits <= 0) {
 		*_result = -1;
 		return;
 	}
 
-	_logsize = fls(_size - 1);
-	_value = _start;
+	_mask = _match ? _BITSTR_MASK : 0;
+	_maxshft = _bit_idx(_size - 1) == 0 ? _size : _BITSTR_BITS;
+	_value = 0;
 	_curbitstr = _bitstr + _bit_idx(_start);
-	_test = ~*_curbitstr;
-	if (_bit_offset(_start) != 0)
-		_test |= _bit_make_mask(0, _start - 1);
-	for (_offset = 0;; _offset -= _BITSTR_BITS, _test = ~*++_curbitstr) {
-		if (_test != 0) {
-			/* If leading 0s in _test can finish 0-area, stop. */
-			if (_offset + _size < (int)_BITSTR_BITS &&
-			    (_test & _bit_make_mask(0, _offset + _size)) == 0)
-				break;
-			/* Shrink-left every 0-area in _test by size-1 bits. */
-			_b = _logsize;
-			while ((_test & (_test + 1)) != 0 && _b-- > 0)
-				_test |= _test >> (((_size - 1) >> _b) + 1) / 2;
-			/* Find the start of the first 0-area in _test. */
-			_offset = (~_test == 0) ? (int)_BITSTR_BITS :
-			    ffsl(~_test) - 1;
-			_value = (_curbitstr - _bitstr) * _BITSTR_BITS +
-			    _offset;
-			/* If there's insufficient space left, give up. */
-			if (_value + _size > _nbits) {
-				_value = -1;
-				break;
-			}
+	_test = ~(_BITSTR_MASK << _bit_offset(_start));
+	for (_last = _size - 1, _test |= _mask ^ *_curbitstr;
+	    !(_bit_idx(_last) == 0 &&
+	    (_test & _bit_make_mask(0, _last)) == 0);
+	    _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) {
+		if (_test == 0)
+			continue;
+		/* Shrink-left every 0-area in _test by maxshft-1 bits. */
+		for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0;
+		     _shft = (_shft + 1) / 2)
+			_test |= _test >> _shft / 2;
+		/* Find the start of the first 0-area in _test. */
+		_last = ffsl(~(_test >> 1));
+		_value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last;
+		/* If there's insufficient space left, give up. */
+		if (_value + _size > _nbits) {
+			_value = -1;
+			break;
 		}
-		if (_offset + _size <= (int)_BITSTR_BITS)
+		_last += _size - 1;
+		/* If a solution is contained in _test, success! */
+		if (_bit_idx(_last) == 0)
 			break;
+		/* A solution here needs bits from the next word. */
 	}
 	*_result = _value;
 }
 
+/* Find contiguous sequence of at least size set bits at or after start */
+static inline void
+bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
+    int *_result)
+{
+	bit_ff_area_at(_bitstr, _start, _nbits, _size, 1, _result);
+}
+
 /* Find contiguous sequence of at least size cleared bits at or after start */
 static inline void
 bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
     int *_result)
 {
-	bitstr_t *_curbitstr;
-	bitstr_t _test;
-	int _value, _offset, _logsize, _b;
-
-	if (_start + _size > _nbits || _nbits <= 0) {
-		*_result = -1;
-		return;
-	}
-
-	_logsize = fls(_size - 1);
-	_value = _start;
-	_curbitstr = _bitstr + _bit_idx(_start);
-	_test = *_curbitstr;
-	if (_bit_offset(_start) != 0)
-		_test |= _bit_make_mask(0, _start - 1);
-	for (_offset = 0;; _offset -= _BITSTR_BITS, _test = *++_curbitstr) {
-		if (_test != 0) {
-			/* If leading 0s in _test can finish 0-area, stop. */
-			if (_offset + _size < (int)_BITSTR_BITS &&
-			    (_test & _bit_make_mask(0, _offset + _size)) == 0)
-				break;
-			/* Shrink-left every 0-area in _test by size-1 bits. */
-			_b = _logsize;
-			while ((_test & (_test + 1)) != 0 && _b-- > 0)
-				_test |= _test >> (((_size - 1) >> _b) + 1) / 2;
-			/* Find the start of the first 0-area in _test. */
-			_offset = (~_test == 0) ? (int)_BITSTR_BITS :
-			    ffsl(~_test) - 1;
-			_value = (_curbitstr - _bitstr) * _BITSTR_BITS +
-			    _offset;
-			/* If there's insufficient space left, give up. */
-			if (_value + _size > _nbits) {
-				_value = -1;
-				break;
-			}
-		}
-		if (_offset + _size <= (int)_BITSTR_BITS)
-			break;
-	}
-	*_result = _value;
+	bit_ff_area_at(_bitstr, _start, _nbits, _size, 0, _result);
 }
 
 /* Find contiguous sequence of at least size set bits in bit string */
diff --git a/sys/vm/vm_reserv.c b/sys/vm/vm_reserv.c
index 8c8b394454a0..bb1bbe6680a1 100644
--- a/sys/vm/vm_reserv.c
+++ b/sys/vm/vm_reserv.c
@@ -53,6 +53,7 @@ __FBSDID("$FreeBSD$");
 #include <sys/sbuf.h>
 #include <sys/sysctl.h>
 #include <sys/systm.h>
+#include <sys/bitstring.h>
 #include <sys/counter.h>
 #include <sys/ktr.h>
 #include <sys/vmmeter.h>
@@ -106,68 +107,12 @@ __FBSDID("$FreeBSD$");
 #define	VM_RESERV_INDEX(object, pindex)	\
     (((object)->pg_color + (pindex)) & (VM_LEVEL_0_NPAGES - 1))
 
-/*
- * The size of a population map entry
- */
-typedef	u_long		popmap_t;
-
-/*
- * The number of bits in a population map entry
- */
-#define	NBPOPMAP	(NBBY * sizeof(popmap_t))
-
-/*
- * The number of population map entries in a reservation
- */
-#define	NPOPMAP		howmany(VM_LEVEL_0_NPAGES, NBPOPMAP)
-#define	NPOPMAP_MAX	howmany(VM_LEVEL_0_NPAGES_MAX, NBPOPMAP)
-
 /*
  * Number of elapsed ticks before we update the LRU queue position.  Used
  * to reduce contention and churn on the list.
  */
 #define	PARTPOPSLOP	1
 
-/*
- * Clear a bit in the population map.
- */
-static __inline void
-popmap_clear(popmap_t popmap[], int i)
-{
-
-	popmap[i / NBPOPMAP] &= ~(1UL << (i % NBPOPMAP));
-}
-
-/*
- * Set a bit in the population map.
- */
-static __inline void
-popmap_set(popmap_t popmap[], int i)
-{
-
-	popmap[i / NBPOPMAP] |= 1UL << (i % NBPOPMAP);
-}
-
-/*
- * Is a bit in the population map clear?
- */
-static __inline boolean_t
-popmap_is_clear(popmap_t popmap[], int i)
-{
-
-	return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) == 0);
-}
-
-/*
- * Is a bit in the population map set?
- */
-static __inline boolean_t
-popmap_is_set(popmap_t popmap[], int i)
-{
-
-	return ((popmap[i / NBPOPMAP] & (1UL << (i % NBPOPMAP))) != 0);
-}
-
 /*
  * The reservation structure
  *
@@ -199,7 +144,8 @@ struct vm_reserv {
 	uint8_t		domain;			/* (c) NUMA domain. */
 	char		inpartpopq;		/* (d, r) */
 	int		lasttick;		/* (r) last pop update tick. */
-	popmap_t	popmap[NPOPMAP_MAX];	/* (r) bit vector, used pages */
+	bitstr_t	bit_decl(popmap, VM_LEVEL_0_NPAGES_MAX);
+						/* (r) bit vector, used pages */
 };
 
 TAILQ_HEAD(vm_reserv_queue, vm_reserv);
@@ -415,7 +361,6 @@ vm_reserv_remove(vm_reserv_t rv)
 static void
 vm_reserv_insert(vm_reserv_t rv, vm_object_t object, vm_pindex_t pindex)
 {
-	int i;
 
 	vm_reserv_assert_locked(rv);
 	CTR6(KTR_VM,
@@ -428,9 +373,8 @@ vm_reserv_insert(vm_reserv_t rv, vm_object_t object, vm_pindex_t pindex)
 	    ("vm_reserv_insert: reserv %p's popcnt is corrupted", rv));
 	KASSERT(!rv->inpartpopq,
 	    ("vm_reserv_insert: reserv %p's inpartpopq is TRUE", rv));
-	for (i = 0; i < NPOPMAP; i++)
-		KASSERT(rv->popmap[i] == 0,
-		    ("vm_reserv_insert: reserv %p's popmap is corrupted", rv));
+	KASSERT(bit_ntest(rv->popmap, 0, VM_LEVEL_0_NPAGES - 1, 0),
+	    ("vm_reserv_insert: reserv %p's popmap is corrupted", rv));
 	vm_reserv_object_lock(object);
 	rv->pindex = pindex;
 	rv->object = object;
@@ -455,7 +399,7 @@ vm_reserv_depopulate(vm_reserv_t rv, int index)
 	    __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
 	KASSERT(rv->object != NULL,
 	    ("vm_reserv_depopulate: reserv %p is free", rv));
-	KASSERT(popmap_is_set(rv->popmap, index),
+	KASSERT(bit_test(rv->popmap, index),
 	    ("vm_reserv_depopulate: reserv %p's popmap[%d] is clear", rv,
 	    index));
 	KASSERT(rv->popcnt > 0,
@@ -469,7 +413,7 @@ vm_reserv_depopulate(vm_reserv_t rv, int index)
 		    rv));
 		rv->pages->psind = 0;
 	}
-	popmap_clear(rv->popmap, index);
+	bit_clear(rv->popmap, index);
 	rv->popcnt--;
 	if ((unsigned)(ticks - rv->lasttick) >= PARTPOPSLOP ||
 	    rv->popcnt == 0) {
@@ -575,7 +519,7 @@ vm_reserv_populate(vm_reserv_t rv, int index)
 	    __FUNCTION__, rv, rv->object, rv->popcnt, rv->inpartpopq);
 	KASSERT(rv->object != NULL,
 	    ("vm_reserv_populate: reserv %p is free", rv));
-	KASSERT(popmap_is_clear(rv->popmap, index),
+	KASSERT(!bit_test(rv->popmap, index),
 	    ("vm_reserv_populate: reserv %p's popmap[%d] is set", rv,
 	    index));
 	KASSERT(rv->popcnt < VM_LEVEL_0_NPAGES,
@@ -585,7 +529,7 @@ vm_reserv_populate(vm_reserv_t rv, int index)
 	KASSERT(rv->domain < vm_ndomains,
 	    ("vm_reserv_populate: reserv %p's domain is corrupted %d",
 	    rv, rv->domain));
-	popmap_set(rv->popmap, index);
+	bit_set(rv->popmap, index);
 	rv->popcnt++;
 	if ((unsigned)(ticks - rv->lasttick) < PARTPOPSLOP &&
 	    rv->inpartpopq && rv->popcnt != VM_LEVEL_0_NPAGES)
@@ -684,9 +628,8 @@ vm_reserv_alloc_contig(vm_object_t object, vm_pindex_t pindex, int domain,
 		    !vm_addr_ok(pa, size, alignment, boundary))
 			goto out;
 		/* Handle vm_page_rename(m, new_object, ...). */
-		for (i = 0; i < npages; i++)
-			if (popmap_is_set(rv->popmap, index + i))
-				goto out;
+		if (!bit_ntest(rv->popmap, index, index + npages - 1, 0))
+			goto out;
 		if (!vm_domain_allocate(vmd, req, npages))
 			goto out;
 		for (i = 0; i < npages; i++)
@@ -854,7 +797,7 @@ vm_reserv_alloc_page(vm_object_t object, vm_pindex_t pindex, int domain,
 		/* Handle reclaim race. */
 		if (rv->object != object ||
 		    /* Handle vm_page_rename(m, new_object, ...). */
-		    popmap_is_set(rv->popmap, index)) {
+		    bit_test(rv->popmap, index)) {
 			m = NULL;
 			goto out;
 		}
@@ -948,8 +891,7 @@ out:
 static void
 vm_reserv_break(vm_reserv_t rv)
 {
-	u_long changes;
-	int bitpos, hi, i, lo;
+	int hi, lo, pos;
 
 	vm_reserv_assert_locked(rv);
 	CTR5(KTR_VM, "%s: rv %p object %p popcnt %d inpartpop %d",
@@ -957,39 +899,24 @@ vm_reserv_break(vm_reserv_t rv)
 	vm_reserv_remove(rv);
 	rv->pages->psind = 0;
 	hi = lo = -1;
-	for (i = 0; i <= NPOPMAP; i++) {
-		/*
-		 * "changes" is a bitmask that marks where a new sequence of
-		 * 0s or 1s begins in popmap[i], with last bit in popmap[i-1]
-		 * considered to be 1 if and only if lo == hi.  The bits of
-		 * popmap[-1] and popmap[NPOPMAP] are considered all 1s.
-		 */
-		if (i == NPOPMAP)
-			changes = lo != hi;
-		else {
-			changes = rv->popmap[i];
-			changes ^= (changes << 1) | (lo == hi);
-			rv->popmap[i] = 0;
-		}
-		while (changes != 0) {
-			/*
-			 * If the next change marked begins a run of 0s, set
-			 * lo to mark that position.  Otherwise set hi and
-			 * free pages from lo up to hi.
-			 */
-			bitpos = ffsl(changes) - 1;
-			changes ^= 1UL << bitpos;
-			if (lo == hi)
-				lo = NBPOPMAP * i + bitpos;
-			else {
-				hi = NBPOPMAP * i + bitpos;
-				vm_domain_free_lock(VM_DOMAIN(rv->domain));
-				vm_phys_enqueue_contig(&rv->pages[lo], hi - lo);
-				vm_domain_free_unlock(VM_DOMAIN(rv->domain));
-				lo = hi;
-			}
+	pos = 0;
+	for (;;) {
+		bit_ff_at(rv->popmap, pos, VM_LEVEL_0_NPAGES, lo != hi, &pos);
+		if (lo == hi) {
+			if (pos == -1)
+				break;
+			lo = pos;
+			continue;
 		}
+		if (pos == -1)
+			pos = VM_LEVEL_0_NPAGES;
+		hi = pos;
+		vm_domain_free_lock(VM_DOMAIN(rv->domain));
+		vm_phys_enqueue_contig(&rv->pages[lo], hi - lo);
+		vm_domain_free_unlock(VM_DOMAIN(rv->domain));
+		lo = hi;
 	}
+	bit_nclear(rv->popmap, 0, VM_LEVEL_0_NPAGES - 1);
 	rv->popcnt = 0;
 	counter_u64_add(vm_reserv_broken, 1);
 }
@@ -1068,7 +995,7 @@ vm_reserv_init(void)
 #ifdef VM_PHYSSEG_SPARSE
 	vm_pindex_t used;
 #endif
-	int i, j, segind;
+	int i, segind;
 
 	/*
 	 * Initialize the reservation array.  Specifically, initialize the
@@ -1110,8 +1037,7 @@ vm_reserv_init(void)
 		 * partially populated reservation queues.
 		 */
 		rvd->marker.popcnt = VM_LEVEL_0_NPAGES;
-		for (j = 0; j < VM_LEVEL_0_NPAGES; j++)
-			popmap_set(rvd->marker.popmap, j);
+		bit_nset(rvd->marker.popmap, 0, VM_LEVEL_0_NPAGES - 1);
 	}
 
 	for (i = 0; i < VM_RESERV_OBJ_LOCK_COUNT; i++)
@@ -1131,7 +1057,7 @@ vm_reserv_is_page_free(vm_page_t m)
 	rv = vm_reserv_from_page(m);
 	if (rv->object == NULL)
 		return (false);
-	return (popmap_is_clear(rv->popmap, m - rv->pages));
+	return (!bit_test(rv->popmap, m - rv->pages));
 }
 
 /*
@@ -1238,8 +1164,6 @@ static int
 vm_reserv_find_contig(vm_reserv_t rv, int npages, int lo,
     int hi, int ppn_align, int ppn_bound)
 {
-	u_long changes;
-	int bitpos, bits_left, i, n;
 
 	vm_reserv_assert_locked(rv);
 	KASSERT(npages <= VM_LEVEL_0_NPAGES - 1,
@@ -1252,56 +1176,18 @@ vm_reserv_find_contig(vm_reserv_t rv, int npages, int lo,
 	    ("ppn_align is not a positive power of 2"));
 	KASSERT(ppn_bound != 0 && powerof2(ppn_bound),
 	    ("ppn_bound is not a positive power of 2"));
-	i = lo / NBPOPMAP;
-	changes = rv->popmap[i] | ((1UL << (lo % NBPOPMAP)) - 1);
-	n = hi / NBPOPMAP;
-	bits_left = hi % NBPOPMAP;
-	hi = lo = -1;
-	for (;;) {
-		/*
-		 * "changes" is a bitmask that marks where a new sequence of
-		 * 0s or 1s begins in popmap[i], with last bit in popmap[i-1]
-		 * considered to be 1 if and only if lo == hi.  The bits of
-		 * popmap[-1] and popmap[NPOPMAP] are considered all 1s.
-		 */
-		changes ^= (changes << 1) | (lo == hi);
-		while (changes != 0) {
-			/*
-			 * If the next change marked begins a run of 0s, set
-			 * lo to mark that position.  Otherwise set hi and
-			 * look for a satisfactory first page from lo up to hi.
-			 */
-			bitpos = ffsl(changes) - 1;
-			changes ^= 1UL << bitpos;
-			if (lo == hi) {
-				lo = NBPOPMAP * i + bitpos;
-				continue;
-			}
-			hi = NBPOPMAP * i + bitpos;
-			if (lo < roundup2(lo, ppn_align)) {
-				/* Skip to next aligned page. */
-				lo = roundup2(lo, ppn_align);
-				if (lo >= VM_LEVEL_0_NPAGES)
-					return (-1);
-			}
-			if (lo + npages > roundup2(lo, ppn_bound)) {
-				/* Skip to next boundary-matching page. */
-				lo = roundup2(lo, ppn_bound);
-				if (lo >= VM_LEVEL_0_NPAGES)
-					return (-1);
-			}
-			if (lo + npages <= hi)
-				return (lo);
-			lo = hi;
+	while (bit_ffc_area_at(rv->popmap, lo, hi, npages, &lo), lo != -1) {
+		if (lo < roundup2(lo, ppn_align)) {
+			/* Skip to next aligned page. */
+			lo = roundup2(lo, ppn_align);
+		} else if (roundup2(lo + 1, ppn_bound) >= lo + npages)
+			return (lo);
+		if (roundup2(lo + 1, ppn_bound) < lo + npages) {
+			/* Skip to next boundary-matching page. */
+			lo = roundup2(lo + 1, ppn_bound);
 		}
-		if (++i < n)
-			changes = rv->popmap[i];
-		else if (i == n)
-			changes = bits_left == 0 ? -1UL :
-			    (rv->popmap[n] | (-1UL << bits_left));
-		else
-			return (-1);
 	}
+	return (-1);
 }
 
 /*
@@ -1389,8 +1275,7 @@ vm_reserv_reclaim_contig(int domain, u_long npages, vm_paddr_t low,
 			vm_reserv_domain_scan_unlock(domain);
 			/* Allocate requested space */
 			rv->popcnt += npages;
-			while (npages-- > 0)
-				popmap_set(rv->popmap, posn + npages);
+			bit_nset(rv->popmap, posn, posn + npages - 1);
 			vm_reserv_reclaim(rv);
 			vm_reserv_unlock(rv);
 			m_ret = &rv->pages[posn];
diff --git a/tests/sys/sys/bitstring_test.c b/tests/sys/sys/bitstring_test.c
index c891a98645f8..97aa97a680f0 100644
--- a/tests/sys/sys/bitstring_test.c
+++ b/tests/sys/sys/bitstring_test.c
@@ -352,20 +352,23 @@ ATF_TC_BODY(bit_ffs_area, tc)
 
 	memset(bitstr, 0, bitstr_size(nbits));
 
-	bit_set(bitstr, 5);
-	bit_set(bitstr, 6);
+	bit_nset(bitstr, 5, 6);
 
 	location = 0;
 	bit_ffs_area(bitstr, nbits, 3, &location);
 	ATF_REQUIRE_EQ_MSG(-1, location,
-			"bit_ffs_area: found location of size 3 when only 2 bits are set");
+	    "bit_ffs_area: found location of size 3 when only 2 bits are set");
+	ATF_REQUIRE_EQ_MSG(0, bit_ntest(bitstr, 5, 7, 1),
+	    "bit_ntest: found location of size 3 when only 2 bits are set");
 
 	bit_set(bitstr, 7);
 
 	location = 0;
 	bit_ffs_area(bitstr, nbits, 3, &location);
 	ATF_REQUIRE_EQ_MSG(5, location,
-			"bit_ffs_area: failed to find location of size 3");
+	    "bit_ffs_area: failed to find location of size 3 %d", location);
+	ATF_REQUIRE_EQ_MSG(1, bit_ntest(bitstr, 5, 7, 1),
+	    "bit_ntest: failed to find all 3 bits set");
 
 	bit_set(bitstr, 8);
 
@@ -389,9 +392,7 @@ ATF_TC_BODY(bit_ffs_area, tc)
 	ATF_REQUIRE_EQ_MSG(-1, location,
 			"bit_ffs_area_at: found invalid location");
 
-	bit_set(bitstr, 69);
-	bit_set(bitstr, 70);
-	bit_set(bitstr, 71);
+	bit_nset(bitstr, 69, 71);
 
 	location = 0;
 	bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
@@ -412,6 +413,18 @@ ATF_TC_BODY(bit_ffs_area, tc)
 	bit_ffs_area_at(bitstr, 72, nbits, 3, &location);
 	ATF_REQUIRE_EQ_MSG(-1, location,
 			"bit_ffs_area_at: found invalid location");
+
+	bit_nset(bitstr, 59, 67);
+
+	location = 0;
+	bit_ffs_area(bitstr, nbits, 9, &location);
+	ATF_REQUIRE_EQ_MSG(59, location,
+			"bit_ffs_area: failed to find location of size 9");
+
+	location = 0;
+	bit_ffs_area(bitstr, nbits, 10, &location);
+	ATF_REQUIRE_EQ_MSG(-1, location,
+			"bit_ffs_area: found invalid location");
 }
 
 ATF_TC_WITHOUT_HEAD(bit_ffc_area);