Page MenuHomeFreeBSD
Files F107239514

D33312.id100445.diff
No OneTemporary
Actions

D33312.id100445.diff
View Options

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 <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>
@@ -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, 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);
}
/*

File Metadata

Mime Type
text/plain
Expires
Sun, Jan 12, 5:41 PM (17 h, 55 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
15771726
Default Alt Text
D33312.id100445.diff (13 KB)

Event Timeline