diff options
| -rw-r--r-- | UPDATING | 6 | ||||
| -rw-r--r-- | share/man/man3/bitstring.3 | 18 | ||||
| -rw-r--r-- | sys/kern/subr_unit.c | 7 | ||||
| -rw-r--r-- | sys/sys/bitstring.h | 41 | ||||
| -rw-r--r-- | sys/sys/param.h | 2 | ||||
| -rw-r--r-- | tests/sys/sys/bitstring_test.c | 62 |
6 files changed, 127 insertions, 9 deletions
diff --git a/UPDATING b/UPDATING index fd47ac042b799..df0542dfab3c6 100644 --- a/UPDATING +++ b/UPDATING @@ -31,6 +31,12 @@ NOTE TO PEOPLE WHO THINK THAT FreeBSD 11.x IS SLOW: disable the most expensive debugging functionality run "ln -s 'abort:false,junk:false' /etc/malloc.conf".) +20160523: + The bitstring(3) API has been updated with new functionality and + improved performance. But it is binary-incompatible with the old API. + Objects built with the new headers may not be linked against objects + built with the old headers. + 20160520: The brk and sbrk functions have been removed from libc on arm64. Binutils from ports has been updated to not link to these diff --git a/share/man/man3/bitstring.3 b/share/man/man3/bitstring.3 index f2dbb81342641..3db5be78dfb01 100644 --- a/share/man/man3/bitstring.3 +++ b/share/man/man3/bitstring.3 @@ -27,7 +27,7 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.\" Copyright (c) 2014 Spectra Logic Corporation +.\" Copyright (c) 2014,2016 Spectra Logic Corporation .\" All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without @@ -58,12 +58,13 @@ .\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93 .\" $FreeBSD$ .\" -.Dd May 4, 2016 +.Dd May 23, 2016 .Dt BITSTRING 3 .Os .Sh NAME .Nm bit_alloc , .Nm bit_clear , +.Nm bit_count , .Nm bit_decl , .Nm bit_ffc , .Nm bit_ffs , @@ -84,6 +85,8 @@ .Ft void .Fn bit_clear "bitstr_t *name" "int bit" .Ft void +.Fn bit_count "bitstr_t *name" "int count" "int nbits" "int *value" +.Ft void .Fn bit_ffc "bitstr_t *name" "int nbits" "int *value" .Ft void .Fn bit_ffs "bitstr_t *name" "int nbits" "int *value" @@ -225,6 +228,17 @@ the location referenced by .Fa value is set to \-1. .Pp +The +.Fn bit_count +function stores in the location referenced by +.Fa value +the number of bits set in the array of +.Fa nbits +bits referenced by +.Fa name , +at or after the zero-based bit index +.Fa start . +.Pp The arguments in bit string macros are evaluated only once and may safely have side effects. .Sh EXAMPLES diff --git a/sys/kern/subr_unit.c b/sys/kern/subr_unit.c index 9da91601523b5..4d784e65cdefb 100644 --- a/sys/kern/subr_unit.c +++ b/sys/kern/subr_unit.c @@ -224,7 +224,8 @@ check_unrhdr(struct unrhdr *uh, int line) { struct unr *up; struct unrb *ub; - u_int x, y, z, w; + int w; + u_int y, z; y = uh->first; z = 0; @@ -237,9 +238,7 @@ check_unrhdr(struct unrhdr *uh, int line) up->len, NBITS, line)); z++; w = 0; - for (x = 0; x < up->len; x++) - if (bit_test(ub->map, x)) - w++; + bit_count(ub->map, 0, up->len, &w); y += w; } else if (up->ptr != NULL) y += up->len; diff --git a/sys/sys/bitstring.h b/sys/sys/bitstring.h index a8d565226996d..9659dba9c4524 100644 --- a/sys/sys/bitstring.h +++ b/sys/sys/bitstring.h @@ -65,6 +65,7 @@ #ifdef _KERNEL #include <sys/libkern.h> #include <sys/malloc.h> +#include <sys/types.h> #endif typedef unsigned long bitstr_t; @@ -202,7 +203,7 @@ bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) _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) @@ -231,7 +232,7 @@ bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) _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) @@ -256,4 +257,40 @@ bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); } +/* Count the number of bits set in a bitstr of size _nbits at or after _start */ +static inline void +bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result) +{ + bitstr_t *_curbitstr, mask; + int _value = 0, curbitstr_len; + + if (_start >= _nbits) + goto out; + + _curbitstr = _bitstr + _bit_idx(_start); + _nbits -= _BITSTR_BITS * _bit_idx(_start); + _start -= _BITSTR_BITS * _bit_idx(_start); + + if (_start > 0) { + curbitstr_len = (int)_BITSTR_BITS < _nbits ? + (int)_BITSTR_BITS : _nbits; + mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1)); + _value += __bitcountl(*_curbitstr & mask); + _curbitstr++; + _nbits -= _BITSTR_BITS; + } + while (_nbits >= (int)_BITSTR_BITS) { + _value += __bitcountl(*_curbitstr); + _curbitstr++; + _nbits -= _BITSTR_BITS; + } + if (_nbits > 0) { + mask = _bit_make_mask(0, _bit_offset(_nbits - 1)); + _value += __bitcountl(*_curbitstr & mask); + } + +out: + *_result = _value; +} + #endif /* _SYS_BITSTRING_H_ */ diff --git a/sys/sys/param.h b/sys/sys/param.h index 665d806507570..edaab483f1e05 100644 --- a/sys/sys/param.h +++ b/sys/sys/param.h @@ -58,7 +58,7 @@ * in the range 5 to 9. */ #undef __FreeBSD_version -#define __FreeBSD_version 1100111 /* Master, propagated to newvers */ +#define __FreeBSD_version 1100112 /* Master, propagated to newvers */ /* * __FreeBSD_kernel__ indicates that this system uses the kernel of FreeBSD, diff --git a/tests/sys/sys/bitstring_test.c b/tests/sys/sys/bitstring_test.c index d0965521cf20f..f80115ae2879f 100644 --- a/tests/sys/sys/bitstring_test.c +++ b/tests/sys/sys/bitstring_test.c @@ -342,6 +342,67 @@ BITSTRING_TC_DEFINE(bit_nset) } } +BITSTRING_TC_DEFINE(bit_count) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int result, s, e, expected; + + /* Empty bitstr */ + memset(bitstr, 0, bitstr_size(nbits)); + bit_count(bitstr, 0, nbits, &result); + ATF_CHECK_MSG(0 == result, + "bit_count_%d_%s_%s: Failed with result %d", + nbits, "clear", memloc, result); + + /* Full bitstr */ + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_count(bitstr, 0, nbits, &result); + ATF_CHECK_MSG(nbits == result, + "bit_count_%d_%s_%s: Failed with result %d", + nbits, "set", memloc, result); + + /* Invalid _start value */ + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_count(bitstr, nbits, nbits, &result); + ATF_CHECK_MSG(0 == result, + "bit_count_%d_%s_%s: Failed with result %d", + nbits, "invalid_start", memloc, result); + + /* Alternating bitstr, starts with 0 */ + memset(bitstr, 0xAA, bitstr_size(nbits)); + bit_count(bitstr, 0, nbits, &result); + ATF_CHECK_MSG(nbits / 2 == result, + "bit_count_%d_%s_%d_%s: Failed with result %d", + nbits, "alternating", 0, memloc, result); + + /* Alternating bitstr, starts with 1 */ + memset(bitstr, 0x55, bitstr_size(nbits)); + bit_count(bitstr, 0, nbits, &result); + ATF_CHECK_MSG((nbits + 1) / 2 == result, + "bit_count_%d_%s_%d_%s: Failed with result %d", + nbits, "alternating", 1, memloc, result); + + /* Varying start location */ + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (s = 0; s < nbits; s++) { + expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2; + bit_count(bitstr, s, nbits, &result); + ATF_CHECK_MSG(expected == result, + "bit_count_%d_%s_%d_%s: Failed with result %d", + nbits, "vary_start", s, memloc, result); + } + + /* Varying end location */ + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (e = 0; e < nbits; e++) { + bit_count(bitstr, 0, e, &result); + ATF_CHECK_MSG(e / 2 == result, + "bit_count_%d_%s_%d_%s: Failed with result %d", + nbits, "vary_end", e, memloc, result); + } + +} + ATF_TP_ADD_TCS(tp) { @@ -354,6 +415,7 @@ ATF_TP_ADD_TCS(tp) BITSTRING_TC_ADD(tp, bit_ffc_at); BITSTRING_TC_ADD(tp, bit_nclear); BITSTRING_TC_ADD(tp, bit_nset); + BITSTRING_TC_ADD(tp, bit_count); return (atf_no_error()); } |