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());
}
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
