Page MenuHomeFreeBSD
Files F135640994

D6255.id.diff
No OneTemporary
Actions

D6255.id.diff
View Options

Index: head/UPDATING
===================================================================
--- head/UPDATING
+++ head/UPDATING
@@ -31,6 +31,12 @@
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
Index: head/share/man/man3/bitstring.3
===================================================================
--- head/share/man/man3/bitstring.3
+++ head/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 @@
.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
Index: head/sys/kern/subr_unit.c
===================================================================
--- head/sys/kern/subr_unit.c
+++ head/sys/kern/subr_unit.c
@@ -224,7 +224,8 @@
{
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 @@
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;
Index: head/sys/sys/bitstring.h
===================================================================
--- head/sys/sys/bitstring.h
+++ head/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 @@
_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 @@
_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_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_ */
Index: head/sys/sys/param.h
===================================================================
--- head/sys/sys/param.h
+++ head/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,
Index: head/tests/sys/sys/bitstring_test.c
===================================================================
--- head/tests/sys/sys/bitstring_test.c
+++ head/tests/sys/sys/bitstring_test.c
@@ -342,6 +342,67 @@
}
}
+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 @@
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());
}

File Metadata

Mime Type
text/plain
Expires
Wed, Nov 12, 12:58 PM (20 h, 1 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
25192949
Default Alt Text
D6255.id.diff (7 KB)

Event Timeline