From nobody Wed Jan 12 17:16:10 2022 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id D8A6317F0A7D; Wed, 12 Jan 2022 17:16:10 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4JYvNV3s1sz4sJl; Wed, 12 Jan 2022 17:16:10 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 6368D10EAB; Wed, 12 Jan 2022 17:16:10 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 20CHGAtN071410; Wed, 12 Jan 2022 17:16:10 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 20CHGAVU071409; Wed, 12 Jan 2022 17:16:10 GMT (envelope-from git) Date: Wed, 12 Jan 2022 17:16:10 GMT Message-Id: <202201121716.20CHGAVU071409@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Doug Moore Subject: git: 84e2ae64c597 - main - vm_reserv: use enhanced bitstring for popmaps List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: dougm X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 84e2ae64c597000a0152c6772b2c8925773c6f6c Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1642007770; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=OKx1Kbx62MhsMERvTJW/dg9z5nxmlwE8t+8idt6lXuc=; b=k41kDNPxUZ2Rn5M8Rhku2dwbj7kQsKogS4YWKSSadRPzWGpZHFJqDkG62KSV8Ooy8zgA4O sbtO5i55QZizFp77yx5xUCEqcmgWdKISd5Jkv8MRj/CcigjjiQl4CKMtzLopK5Oh+4duQI /IxeJE1silH/14LGNCEU+sFmAFmcWz/KlTX+BP4RvTYO8mKyx4MpSo9HQ2468fSZxqu1iz RZmgwzPe0y8tJE3iiBh84jxOfovFyo8j8cVKQ4RU0YYljBRinzBU5w32zN1jTdGxFJ4EpE IZNGN0RcSp+NXa4RXz/oq5wZAoccFCVhI1nx52yRNtZQF9U30KN2tIGEPuUpBQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1642007770; a=rsa-sha256; cv=none; b=YFiTI5ofmm8AlaZorWLg/zxpdrddu6BBtIyXitv/NopY1Fnek6bYG8nGpWV5v3SW+fIkHM WRJkgFD+oTEknj7WxkbV5DWueoSkQVKsuOXCGc9qKd7W4HbygsDaHQ2mJYb0wMcYFlS4yc +Ih/97wOOZo86lg7FeW89xJAAA8P6CMA6D8YDlBArI4vr7OYDqxw9eLPeELUlR3744VIsB QuHLwfry1lJY0vCpvw/cRU+uAoxNFwZgDfmRYCLsJaIbrSwd+LdnurX9NrzXYGjSfkpD87 Vhhv7t1eC4MId+fck1v4qaimS3ldgi99cCcplPOVgc1HvCat/lmGii+HjDOMrA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=84e2ae64c597000a0152c6772b2c8925773c6f6c commit 84e2ae64c597000a0152c6772b2c8925773c6f6c Author: Doug Moore AuthorDate: 2022-01-12 17:03:53 +0000 Commit: Doug Moore 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 #include #include +#include #include #include #include @@ -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);