Date: Mon, 23 May 2016 20:29:18 +0000 (UTC) From: Alan Somers <asomers@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r300539 - in head: . share/man/man3 sys/kern sys/sys tests/sys/sys Message-ID: <201605232029.u4NKTIjK072941@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: asomers Date: Mon May 23 20:29:18 2016 New Revision: 300539 URL: https://svnweb.freebsd.org/changeset/base/300539 Log: Add bit_count to the bitstring(3) api Add a bit_count function, which efficiently counts the number of bits set in a bitstring. sys/sys/bitstring.h tests/sys/sys/bitstring_test.c share/man/man3/bitstring.3 Add bit_alloc sys/kern/subr_unit.c Use bit_count instead of a naive counting loop in check_unrhdr, used when INVARIANTS are enabled. The userland test runs about 6x faster in a generic build, or 8.5x faster when built for Nehalem, which has the POPCNT instruction. sys/sys/param.h Bump __FreeBSD_version due to the addition of bit_alloc UPDATING Add a note about the ABI incompatibility of the bitstring(3) changes, as suggested by lidl. Suggested by: gibbs Reviewed by: gibbs, ngie MFC after: 9 days X-MFC-With: 299090, 300538 Relnotes: yes Sponsored by: Spectra Logic Corp Differential Revision: https://reviews.freebsd.org/D6255 Modified: head/UPDATING head/share/man/man3/bitstring.3 head/sys/kern/subr_unit.c head/sys/sys/bitstring.h head/sys/sys/param.h head/tests/sys/sys/bitstring_test.c Modified: head/UPDATING ============================================================================== --- head/UPDATING Mon May 23 20:19:07 2016 (r300538) +++ head/UPDATING Mon May 23 20:29:18 2016 (r300539) @@ -31,6 +31,12 @@ NOTE TO PEOPLE WHO THINK THAT FreeBSD 11 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 Modified: head/share/man/man3/bitstring.3 ============================================================================== --- head/share/man/man3/bitstring.3 Mon May 23 20:19:07 2016 (r300538) +++ head/share/man/man3/bitstring.3 Mon May 23 20:29:18 2016 (r300539) @@ -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 Modified: head/sys/kern/subr_unit.c ============================================================================== --- head/sys/kern/subr_unit.c Mon May 23 20:19:07 2016 (r300538) +++ head/sys/kern/subr_unit.c Mon May 23 20:29:18 2016 (r300539) @@ -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; Modified: head/sys/sys/bitstring.h ============================================================================== --- head/sys/sys/bitstring.h Mon May 23 20:19:07 2016 (r300538) +++ head/sys/sys/bitstring.h Mon May 23 20:29:18 2016 (r300539) @@ -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 _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 _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, i 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_ */ Modified: head/sys/sys/param.h ============================================================================== --- head/sys/sys/param.h Mon May 23 20:19:07 2016 (r300538) +++ head/sys/sys/param.h Mon May 23 20:29:18 2016 (r300539) @@ -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, Modified: head/tests/sys/sys/bitstring_test.c ============================================================================== --- head/tests/sys/sys/bitstring_test.c Mon May 23 20:19:07 2016 (r300538) +++ head/tests/sys/sys/bitstring_test.c Mon May 23 20:29:18 2016 (r300539) @@ -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()); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201605232029.u4NKTIjK072941>