git: 84e2ae64c597 - main - vm_reserv: use enhanced bitstring for popmaps
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
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);