Index: sys/sys/bitstring.h =================================================================== --- sys/sys/bitstring.h +++ sys/sys/bitstring.h @@ -167,10 +167,14 @@ 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(_stop) == _BITSTR_BITS - 1) + ++_stopbitstr; + else + *_stopbitstr |= _bit_make_mask(0, _stop); + if (_bit_offset(_start) != 0) + *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1); + while (_bitstr < _stopbitstr) + *_bitstr++ = _BITSTR_MASK; } } @@ -186,79 +190,62 @@ 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(_stop) == _BITSTR_BITS - 1) + ++_stopbitstr; + else + *_stopbitstr &= ~_bit_make_mask(0, _stop); + if (_bit_offset(_start) != 0) + *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1); + while (_bitstr < _stopbitstr) + *_bitstr++ = 0; } } -/* 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); - - _offset = ffsl(_test); - _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; - if (_offset == 0 || _value >= _nbits) - _value = -1; - } else { + _test = _mask ^ *_curbitstr; + if (_bit_offset(_start) != 0) + _test &= _bit_make_mask(_start, _BITSTR_BITS - 1); + while (_test == 0 && _curbitstr < _stopbitstr) + _test = _mask ^ *(++_curbitstr); + + _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. */ Index: sys/vm/vm_reserv.c =================================================================== --- sys/vm/vm_reserv.c +++ sys/vm/vm_reserv.c @@ -53,6 +53,7 @@ #include #include #include +#include #include #include #include @@ -105,68 +106,12 @@ #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 * @@ -198,7 +143,8 @@ 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); @@ -414,7 +360,7 @@ static void vm_reserv_insert(vm_reserv_t rv, vm_object_t object, vm_pindex_t pindex) { - int i; + int i __diagused; vm_reserv_assert_locked(rv); CTR6(KTR_VM, @@ -427,9 +373,8 @@ ("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_ffs(rv->popmap, VM_LEVEL_0_NPAGES, &i), i == -1), + ("vm_reserv_insert: reserv %p's popmap is corrupted", rv)); vm_reserv_object_lock(object); rv->pindex = pindex; rv->object = object; @@ -454,7 +399,7 @@ __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, @@ -468,7 +413,7 @@ 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) { @@ -574,7 +519,7 @@ __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, @@ -584,7 +529,7 @@ 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) @@ -686,9 +631,9 @@ ((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) 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; + bit_ffs_at(rv->popmap, index, npages, &i); + if (i != -1) + goto out; if (!vm_domain_allocate(vmd, req, npages)) goto out; for (i = 0; i < npages; i++) @@ -856,7 +801,7 @@ /* 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; } @@ -950,8 +895,7 @@ 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", @@ -959,39 +903,24 @@ 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); } @@ -1070,7 +999,7 @@ #ifdef VM_PHYSSEG_SPARSE vm_pindex_t used; #endif - int i, j, segind; + int i, segind; /* * Initialize the reservation array. Specifically, initialize the @@ -1112,8 +1041,7 @@ * 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++) @@ -1133,7 +1061,7 @@ 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)); } /* @@ -1240,8 +1168,6 @@ 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, @@ -1254,56 +1180,20 @@ ("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) == + roundup2(lo + npages, ppn_bound)) + return (lo); + if (roundup2(lo + 1, ppn_bound) != + roundup2(lo + npages, ppn_bound)) { + /* 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); } /* @@ -1391,8 +1281,7 @@ 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];