Index: etc/mtree/BSD.tests.dist =================================================================== --- etc/mtree/BSD.tests.dist +++ etc/mtree/BSD.tests.dist @@ -460,6 +460,8 @@ .. posixshm .. + sys + .. vfs .. vm Index: lib/libbluetooth/bluetooth.h =================================================================== --- lib/libbluetooth/bluetooth.h +++ lib/libbluetooth/bluetooth.h @@ -35,14 +35,16 @@ #define _BLUETOOTH_H_ #include -#include #include #include #include #include #include + #include #include +#include + #include #include #include Index: sbin/hastd/activemap.c =================================================================== --- sbin/hastd/activemap.c +++ sbin/hastd/activemap.c @@ -162,7 +162,7 @@ amp->am_extentsize = extentsize; amp->am_extentshift = bitcount32(extentsize - 1); amp->am_nextents = ((mediasize - 1) / extentsize) + 1; - amp->am_mapsize = sizeof(bitstr_t) * bitstr_size(amp->am_nextents); + amp->am_mapsize = bitstr_size(amp->am_nextents); amp->am_diskmapsize = roundup2(amp->am_mapsize, sectorsize); amp->am_ndirty = 0; amp->am_syncoff = -2; @@ -552,7 +552,7 @@ PJDLOG_ASSERT(powerof2(sectorsize)); nextents = ((mediasize - 1) / extentsize) + 1; - mapsize = sizeof(bitstr_t) * bitstr_size(nextents); + mapsize = bitstr_size(nextents); return (roundup2(mapsize, sectorsize)); } Index: share/man/man3/bitstring.3 =================================================================== --- share/man/man3/bitstring.3 +++ share/man/man3/bitstring.3 @@ -27,6 +27,34 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" +.\" Copyright (c) 2014 Spectra Logic Corporation +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions, and the following disclaimer, +.\" without modification. +.\" 2. Redistributions in binary form must reproduce at minimum a disclaimer +.\" substantially similar to the "NO WARRANTY" disclaimer below +.\" ("Disclaimer") and any redistribution must be conditioned upon +.\" including a substantially similar Disclaimer requirement for further +.\" binary redistribution. +.\" +.\" NO WARRANTY +.\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +.\" "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR +.\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +.\" HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING +.\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +.\" POSSIBILITY OF SUCH DAMAGES. +.\" .\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93 .\" $FreeBSD$ .\" @@ -37,13 +65,16 @@ .Nm bit_alloc , .Nm bit_clear , .Nm bit_decl , +.Nm bit_ffc , .Nm bit_ffs , +.Nm bit_ffc_at , +.Nm bit_ffs_at , .Nm bit_nclear , .Nm bit_nset , .Nm bit_set , -.Nm bitstr_size , -.Nm bit_test -.Nd bit-string manipulation macros +.Nm bit_test , +.Nm bitstr_size +.Nd bit-string manipulation functions and macros .Sh SYNOPSIS .In bitstring.h .Ft bitstr_t * @@ -57,6 +88,10 @@ .Ft void .Fn bit_ffs "bitstr_t *name" "int nbits" "int *value" .Ft void +.Fn bit_ffc_at "bitstr_t *name" "int start" "int nbits" "int *value" +.Ft void +.Fn bit_ffs_at "bitstr_t *name" "int start" "int nbits" "int *value" +.Ft void .Fn bit_nclear "bitstr_t *name" "int start" "int stop" .Ft void .Fn bit_nset "bitstr_t *name" "int start" "int stop" @@ -69,7 +104,7 @@ .Sh DESCRIPTION These macros operate on strings of bits. .Pp -The macro +The function .Fn bit_alloc returns a pointer of type .Dq Fa "bitstr_t *" @@ -78,23 +113,31 @@ bits, or .Dv NULL if no space is available. +If successful, the returned bit string is initialized with all bits cleared. .Pp The macro .Fn bit_decl -allocates sufficient space to store +declares a bit string with sufficient space to store .Fa nbits -bits on the stack. +bits. +.Fn bit_decl +may be used to include statically sized bit strings in structure +definitions or to create bit strings on the stack. +Users of this macro are responsible for initialization of the bit string, +typically via a global initialization of the containing struct or use of the +.Fn bit_nset +or +.Fn bin_nclear +functions. .Pp The macro .Fn bitstr_size -returns the number of elements of type -.Fa bitstr_t -necessary to store +returns the number of bytes necessary to store .Fa nbits bits. This is useful for copying bit strings. .Pp -The macros +The functions .Fn bit_clear and .Fn bit_set @@ -107,7 +150,7 @@ .Fn bit_nset and .Fn bit_nclear -macros +functions set or clear the zero-based numbered bits from .Fa start through @@ -117,16 +160,28 @@ .Pp The .Fn bit_test -macro +function evaluates to non-zero if the zero-based numbered bit .Fa bit of bit string .Fa name is set, and zero otherwise. .Pp +The function +.Fn bit_ffc +stores in the location referenced by +.Fa value +the zero-based number of the first bit not set in the array of +.Fa nbits +bits referenced by +.Fa name . +If all bits are set, the location referenced by +.Fa value +is set to \-1. +.Pp The .Fn bit_ffs -macro +function stores in the location referenced by .Fa value the zero-based number of the first bit set in the array of @@ -137,19 +192,40 @@ .Fa value is set to \-1. .Pp -The macro -.Fn bit_ffc +The function +.Fn bit_ffc_at stores in the location referenced by .Fa value the zero-based number of the first bit not set in the array of .Fa nbits bits referenced by -.Fa name . -If all bits are set, the location referenced by +.Fa name , +at or after the zero-based bit index +.Fa start . +If all bits at or after +.Fa start +are set, the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffs_at +function +stores in the location referenced by +.Fa value +the zero-based number of the first bit set in the array of +.Fa nbits +bits referenced by +.Fa name , +at or after the zero-based bit index +.Fa start . +If no bits are set after +.Fa start , +the location referenced by .Fa value is set to \-1. .Pp -The arguments to these macros are evaluated only once and may safely +The arguments in bit string macros are evaluated only once and may safely have side effects. .Sh EXAMPLES .Bd -literal -offset indent Index: sys/boot/common/bcache.c =================================================================== --- sys/boot/common/bcache.c +++ sys/boot/common/bcache.c @@ -35,7 +35,7 @@ #include #include -#include +#include #include "bootstrap.h" Index: sys/kern/subr_unit.c =================================================================== --- sys/kern/subr_unit.c +++ sys/kern/subr_unit.c @@ -68,7 +68,6 @@ */ #include -#include #include #ifdef _KERNEL @@ -77,6 +76,7 @@ #include #include #include +#include #include #include #include @@ -101,6 +101,7 @@ #include #include #include +#include #define KASSERT(cond, arg) \ do { \ @@ -164,7 +165,7 @@ * element: * If ptr is NULL, it represents a run of free items. * If ptr points to the unrhdr it represents a run of allocated items. - * Otherwise it points to an bitstring of allocated items. + * Otherwise it points to a bitstring of allocated items. * * For runs the len field is the length of the run. * For bitmaps the len field represents the number of allocated items. @@ -177,15 +178,55 @@ void *ptr; }; -struct unrb { - u_char busy; - bitstr_t map[sizeof(struct unr) - 1]; +union unrb { + bitstr_t map[sizeof(struct unr) / sizeof(bitstr_t)]; + u_char bytes[sizeof(struct unr)]; }; -CTASSERT(sizeof(struct unr) == sizeof(struct unrb)); +CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0); + +/* + * Number of bits we can store in the bitmap and still + * leave space for ub_busy. + */ +#define NBITS ((sizeof(union unrb) - 1) * 8) -/* Number of bits in the bitmap */ -#define NBITS ((int)sizeof(((struct unrb *)NULL)->map) * 8) +/* + * The location of the bitmap busy count within the last 8 bits + * of the declared bitmap. + */ +static inline u_char * +ub_busy_ptr(union unrb *ub) +{ + if (BYTE_ORDER == LITTLE_ENDIAN) + return (&ub->bytes[sizeof(ub->bytes) - 1]); + else + return (&ub->bytes[sizeof(ub->bytes) - sizeof(bitstr_t)]); +} + +static inline u_char +ub_busy_get(union unrb *ub) +{ + return (*ub_busy_ptr(ub)); +} + +static inline void +ub_busy_set(union unrb *ub, u_char value) +{ + *ub_busy_ptr(ub) = value; +} + +static inline void +ub_busy_inc(union unrb *ub, u_char value) +{ + *ub_busy_ptr(ub) += value; +} + +static inline void +ub_busy_dec(union unrb *ub, u_char value) +{ + *ub_busy_ptr(ub) -= value; +} #if defined(DIAGNOSTIC) || !defined(_KERNEL) /* @@ -199,7 +240,7 @@ check_unrhdr(struct unrhdr *uh, int line) { struct unr *up; - struct unrb *ub; + union unrb *ub; u_int x, y, z, w; y = uh->first; @@ -209,16 +250,16 @@ if (up->ptr != uh && up->ptr != NULL) { ub = up->ptr; KASSERT (up->len <= NBITS, - ("UNR inconsistency: len %u max %d (line %d)\n", + ("UNR inconsistency: len %u max %zd (line %d)\n", up->len, NBITS, line)); z++; w = 0; for (x = 0; x < up->len; x++) if (bit_test(ub->map, x)) w++; - KASSERT (w == ub->busy, + KASSERT (w == ub_busy_get(ub), ("UNR inconsistency: busy %u found %u (line %d)\n", - ub->busy, w, line)); + ub_busy_get(ub), w, line)); y += w; } else if (up->ptr != NULL) y += up->len; @@ -365,7 +406,7 @@ optimize_unr(struct unrhdr *uh) { struct unr *up, *uf, *us; - struct unrb *ub, *ubf; + union unrb *ub, *ubf; u_int a, l, ba; /* @@ -412,10 +453,10 @@ a = us->len; l = us->ptr == uh ? 1 : 0; ub = (void *)us; - ub->busy = 0; + ub_busy_set(ub, 0); if (l) { bit_nset(ub->map, 0, a); - ub->busy += a; + ub_busy_inc(ub, a); } else { bit_nclear(ub->map, 0, a); } @@ -424,7 +465,7 @@ bit_nclear(ub->map, a, a + uf->len - 1); } else { bit_nset(ub->map, a, a + uf->len - 1); - ub->busy += uf->len; + ub_busy_inc(ub, uf->len); } uf->ptr = ub; uf->len += a; @@ -434,7 +475,7 @@ for (l = 0; l < uf->len; l++, a++) { if (bit_test(ubf->map, l)) { bit_set(ub->map, a); - ub->busy++; + ub_busy_inc(ub, 1); } else { bit_clear(ub->map, a); } @@ -459,7 +500,7 @@ delete_unr(uh, uf); } else if (uf->ptr == uh) { bit_nset(ub->map, us->len, us->len + uf->len - 1); - ub->busy += uf->len; + ub_busy_inc(ub, uf->len); us->len += uf->len; TAILQ_REMOVE(&uh->head, uf, list); delete_unr(uh, uf); @@ -468,7 +509,7 @@ for (l = 0; l < uf->len; l++, us->len++) { if (bit_test(ubf->map, l)) { bit_set(ub->map, us->len); - ub->busy++; + ub_busy_inc(ub, 1); } else { bit_clear(ub->map, us->len); } @@ -489,15 +530,15 @@ collapse_unr(struct unrhdr *uh, struct unr *up) { struct unr *upp; - struct unrb *ub; + union unrb *ub; /* If bitmap is all set or clear, change it to runlength */ if (is_bitmap(uh, up)) { ub = up->ptr; - if (ub->busy == up->len) { + if (ub_busy_get(ub) == up->len) { delete_unr(uh, up->ptr); up->ptr = uh; - } else if (ub->busy == 0) { + } else if (ub_busy_get(ub) == 0) { delete_unr(uh, up->ptr); up->ptr = NULL; } @@ -561,7 +602,7 @@ alloc_unrl(struct unrhdr *uh) { struct unr *up; - struct unrb *ub; + union unrb *ub; u_int x; int y; @@ -595,11 +636,11 @@ up->len--; } else { /* bitmap */ ub = up->ptr; - KASSERT(ub->busy < up->len, ("UNR bitmap confusion")); + KASSERT(ub_busy_get(ub) < up->len, ("UNR bitmap confusion")); bit_ffc(ub->map, up->len, &y); KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap.")); bit_set(ub->map, y); - ub->busy++; + ub_busy_inc(ub, 1); x += y; } uh->busy++; @@ -623,7 +664,7 @@ alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2) { struct unr *up, *upn; - struct unrb *ub; + union unrb *ub; u_int i, last, tl; mtx_assert(uh->mtx, MA_OWNED); @@ -683,7 +724,7 @@ ub = up->ptr; if (bit_test(ub->map, i) == 0) { bit_set(ub->map, i); - ub->busy++; + ub_busy_inc(ub, 1); goto done; } else return (-1); @@ -754,7 +795,7 @@ free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2) { struct unr *up, *upp, *upn; - struct unrb *ub; + union unrb *ub; u_int pl; KASSERT(item >= uh->low && item <= uh->high, @@ -802,7 +843,7 @@ ("UNR: Freeing free item %d (bitmap)\n", item)); bit_clear(ub->map, item); uh->busy--; - ub->busy--; + ub_busy_dec(ub, 1); collapse_unr(uh, up); return; } @@ -887,7 +928,7 @@ print_unr(struct unrhdr *uh, struct unr *up) { u_int x; - struct unrb *ub; + union unrb *ub; printf(" %p len = %5u ", up, up->len); if (up->ptr == NULL) @@ -896,7 +937,7 @@ printf("alloc\n"); else { ub = up->ptr; - printf("bitmap(%d) [", ub->busy); + printf("bitmap(%d) [", ub_busy_get(ub)); for (x = 0; x < up->len; x++) { if (bit_test(ub->map, x)) printf("#"); @@ -981,9 +1022,9 @@ srandomdev(); fprintf(stderr, "sizeof(struct unr) %zu\n", sizeof(struct unr)); - fprintf(stderr, "sizeof(struct unrb) %zu\n", sizeof(struct unrb)); + fprintf(stderr, "sizeof(union unrb) %zu\n", sizeof(union unrb)); fprintf(stderr, "sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr)); - fprintf(stderr, "NBITS %d\n", NBITS); + fprintf(stderr, "NBITS %zd\n", NBITS); x = 1; for (m = 0; m < NN * 100; m++) { j = random(); Index: sys/net/flowtable.c =================================================================== --- sys/net/flowtable.c +++ sys/net/flowtable.c @@ -741,10 +741,6 @@ return (flowtable_insert(ft, hash, key, keylen, fibnum)); } -/* - * used by the bit_alloc macro - */ -#define calloc(count, size) malloc((count)*(size), M_FTABLE, M_WAITOK | M_ZERO) static void flowtable_alloc(struct flowtable *ft) { @@ -759,11 +755,10 @@ bitstr_t **b; b = zpcpu_get_cpu(ft->ft_masks, i); - *b = bit_alloc(ft->ft_size); + *b = bit_alloc(ft->ft_size, M_FTABLE, M_WAITOK); } - ft->ft_tmpmask = bit_alloc(ft->ft_size); + ft->ft_tmpmask = bit_alloc(ft->ft_size, M_FTABLE, M_WAITOK); } -#undef calloc static void flowtable_free_stale(struct flowtable *ft, struct rtentry *rt, int maxidle) Index: sys/sys/bitstring.h =================================================================== --- sys/sys/bitstring.h +++ sys/sys/bitstring.h @@ -1,3 +1,5 @@ +#ifndef _SYS_BITSTRING_H_ +#define _SYS_BITSTRING_H_ /*- * Copyright (c) 1989, 1993 * The Regents of the University of California. All rights reserved. @@ -29,118 +31,229 @@ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * + * Copyright (c) 2014 Spectra Logic Corporation + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions, and the following disclaimer, + * without modification. + * 2. Redistributions in binary form must reproduce at minimum a disclaimer + * substantially similar to the "NO WARRANTY" disclaimer below + * ("Disclaimer") and any redistribution must be conditioned upon + * including a substantially similar Disclaimer requirement for further + * binary redistribution. + * + * NO WARRANTY + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGES. + * * $FreeBSD$ */ -#ifndef _SYS_BITSTRING_H_ -#define _SYS_BITSTRING_H_ - -typedef unsigned char bitstr_t; - -/* internal macros */ - /* byte of the bitstring bit is in */ -#define _bit_byte(bit) \ - ((bit) >> 3) - - /* mask for the bit within its byte */ -#define _bit_mask(bit) \ - (1 << ((bit)&0x7)) - -/* external macros */ - /* bytes in a bitstring of nbits bits */ -#define bitstr_size(nbits) \ - (((nbits) + 7) >> 3) - - /* allocate a bitstring */ -#define bit_alloc(nbits) \ - (bitstr_t *)calloc((size_t)bitstr_size(nbits), sizeof(bitstr_t)) +#ifdef _KERNEL +#include +#include +#endif + +typedef unsigned long bitstr_t; + +/*---------------------- Private Implementation Details ----------------------*/ +#define _BITSTR_MASK (~0UL) +#define _BITSTR_BITS (sizeof(bitstr_t) * 8) + +/* bitstr_t in bit string containing the bit. */ +static inline int +_bit_idx(int _bit) +{ + return (_bit / _BITSTR_BITS); +} + +/* bit number within bitstr_t at _bit_idx(_bit). */ +static inline int +_bit_offset(int _bit) +{ + return (_bit % _BITSTR_BITS); +} + +/* Mask for the bit within its long. */ +static inline bitstr_t +_bit_mask(int _bit) +{ + return (1UL << _bit_offset(_bit)); +} + +static inline bitstr_t +_bit_make_mask(int _start, int _stop) +{ + return ((_BITSTR_MASK << _bit_offset(_start)) & + (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1))); +} + +/*----------------------------- Public Interface -----------------------------*/ +/* Number of bytes consumed by a bit string of nbits bits */ +#define bitstr_size(_nbits) \ + (((_nbits) + _BITSTR_BITS - 1) / 8) + +/* Allocate a bit string initialized with no bits set. */ +#ifdef _KERNEL +static inline bitstr_t * +bit_alloc(int _nbits, struct malloc_type *type, int flags) +{ + return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO)); +} +#else +static inline bitstr_t * +bit_alloc(int _nbits) +{ + return ((bitstr_t *)calloc(bitstr_size(_nbits), 1)); +} +#endif - /* allocate a bitstring on the stack */ +/* Allocate a bit string on the stack with no bits set. */ #define bit_decl(name, nbits) \ - ((name)[bitstr_size(nbits)]) + ((name)[bitstr_size(nbits) / sizeof(bitstr_t)]) - /* is bit N of bitstring name set? */ -#define bit_test(name, bit) \ - ((name)[_bit_byte(bit)] & _bit_mask(bit)) - - /* set bit N of bitstring name */ -#define bit_set(name, bit) \ - ((name)[_bit_byte(bit)] |= _bit_mask(bit)) - - /* clear bit N of bitstring name */ -#define bit_clear(name, bit) \ - ((name)[_bit_byte(bit)] &= ~_bit_mask(bit)) - - /* clear bits start ... stop in bitstring */ -#define bit_nclear(name, start, stop) do { \ - register bitstr_t *_name = (name); \ - register int _start = (start), _stop = (stop); \ - register int _startbyte = _bit_byte(_start); \ - register int _stopbyte = _bit_byte(_stop); \ - if (_startbyte == _stopbyte) { \ - _name[_startbyte] &= ((0xff >> (8 - (_start&0x7))) | \ - (0xff << ((_stop&0x7) + 1))); \ - } else { \ - _name[_startbyte] &= 0xff >> (8 - (_start&0x7)); \ - while (++_startbyte < _stopbyte) \ - _name[_startbyte] = 0; \ - _name[_stopbyte] &= 0xff << ((_stop&0x7) + 1); \ - } \ -} while (0) - - /* set bits start ... stop in bitstring */ -#define bit_nset(name, start, stop) do { \ - register bitstr_t *_name = (name); \ - register int _start = (start), _stop = (stop); \ - register int _startbyte = _bit_byte(_start); \ - register int _stopbyte = _bit_byte(_stop); \ - if (_startbyte == _stopbyte) { \ - _name[_startbyte] |= ((0xff << (_start&0x7)) & \ - (0xff >> (7 - (_stop&0x7)))); \ - } else { \ - _name[_startbyte] |= 0xff << ((_start)&0x7); \ - while (++_startbyte < _stopbyte) \ - _name[_startbyte] = 0xff; \ - _name[_stopbyte] |= 0xff >> (7 - (_stop&0x7)); \ - } \ -} while (0) - - /* find first bit clear in name */ -#define bit_ffc(name, nbits, value) do { \ - register bitstr_t *_name = (name); \ - register int _byte, _nbits = (nbits); \ - register int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \ - if (_nbits > 0) \ - for (_byte = 0; _byte <= _stopbyte; ++_byte) \ - if (_name[_byte] != 0xff) { \ - bitstr_t _lb; \ - _value = _byte << 3; \ - for (_lb = _name[_byte]; (_lb&0x1); \ - ++_value, _lb >>= 1); \ - break; \ - } \ - if (_value >= nbits) \ - _value = -1; \ - *(value) = _value; \ -} while (0) - - /* find first bit set in name */ -#define bit_ffs(name, nbits, value) do { \ - register bitstr_t *_name = (name); \ - register int _byte, _nbits = (nbits); \ - register int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \ - if (_nbits > 0) \ - for (_byte = 0; _byte <= _stopbyte; ++_byte) \ - if (_name[_byte]) { \ - bitstr_t _lb; \ - _value = _byte << 3; \ - for (_lb = _name[_byte]; !(_lb&0x1); \ - ++_value, _lb >>= 1); \ - break; \ - } \ - if (_value >= nbits) \ - _value = -1; \ - *(value) = _value; \ -} while (0) +/* Is bit N of bit string set? */ +static inline int +bit_test(const bitstr_t *_bitstr, int _bit) +{ + return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0); +} + +/* Set bit N of bit string. */ +static inline void +bit_set(bitstr_t *_bitstr, int _bit) +{ + _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit); +} + +/* clear bit N of bit string name */ +static inline void +bit_clear(bitstr_t *_bitstr, int _bit) +{ + _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit); +} + +/* Set bits start ... stop inclusive in bit string. */ +static inline void +bit_nset(bitstr_t *_bitstr, int _start, int _stop) +{ + bitstr_t *_stopbitstr; + + _stopbitstr = _bitstr + _bit_idx(_stop); + _bitstr += _bit_idx(_start); + + 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); + } +} + +/* Clear bits start ... stop inclusive in bit string. */ +static inline void +bit_nclear(bitstr_t *_bitstr, int _start, int _stop) +{ + bitstr_t *_stopbitstr; + + _stopbitstr = _bitstr + _bit_idx(_stop); + _bitstr += _bit_idx(_start); + + 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); + } +} + +/* 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) +{ + bitstr_t *_curbitstr; + bitstr_t *_stopbitstr; + bitstr_t _test; + int _value, _offset; + + 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(_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) + _value = -1; + } else { + _value = -1; + } + *_result = _value; +} + +/* 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 (_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; +} + +/* Find the first bit set in bit string. */ +static inline void +bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result) +{ + bit_ffs_at(_bitstr, /*start*/0, _nbits, _result); +} + +/* Find the first bit clear in bit string. */ +static inline void +bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) +{ + bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); +} -#endif /* !_SYS_BITSTRING_H_ */ +#endif /* _SYS_BITSTRING_H_ */ Index: sys/sys/param.h =================================================================== --- sys/sys/param.h +++ sys/sys/param.h @@ -58,7 +58,7 @@ * in the range 5 to 9. */ #undef __FreeBSD_version -#define __FreeBSD_version 1100105 /* Master, propagated to newvers */ +#define __FreeBSD_version 1100106 /* Master, propagated to newvers */ /* * __FreeBSD_kernel__ indicates that this system uses the kernel of FreeBSD, Index: tests/sys/Makefile =================================================================== --- tests/sys/Makefile +++ tests/sys/Makefile @@ -16,6 +16,7 @@ TESTS_SUBDIRS+= netinet TESTS_SUBDIRS+= opencrypto TESTS_SUBDIRS+= posixshm +TESTS_SUBDIRS+= sys TESTS_SUBDIRS+= vfs TESTS_SUBDIRS+= vm Index: tests/sys/sys/Makefile =================================================================== --- /dev/null +++ tests/sys/sys/Makefile @@ -0,0 +1,9 @@ +# $FreeBSD$ + +TESTSDIR= ${TESTSBASE}/sys/sys + +ATF_TESTS_C= bitstring_test + +WARNS?= 5 + +.include Index: tests/sys/sys/bitstring_test.c =================================================================== --- /dev/null +++ tests/sys/sys/bitstring_test.c @@ -0,0 +1,358 @@ +/*- + * Copyright (c) 2014 Spectra Logic Corporation + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions, and the following disclaimer, + * without modification. + * 2. Redistributions in binary form must reproduce at minimum a disclaimer + * substantially similar to the "NO WARRANTY" disclaimer below + * ("Disclaimer") and any redistribution must be conditioned upon + * including a substantially similar Disclaimer requirement for further + * binary redistribution. + * + * NO WARRANTY + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGES. + * + * $FreeBSD$ + */ +#include +#include + +#include + +#include + +typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc); + +static void +bitstring_run_stack_test(testfunc_t *test, int nbits) +{ + bitstr_t bit_decl(bitstr, nbits); + + test(bitstr, nbits, "stack"); +} + +static void +bitstring_run_heap_test(testfunc_t *test, int nbits) +{ + bitstr_t *bitstr = bit_alloc(nbits); + + test(bitstr, nbits, "heap"); +} + +static void +bitstring_test_runner(testfunc_t *test) +{ + const int bitstr_sizes[] = { + 0, + 1, + _BITSTR_BITS - 1, + _BITSTR_BITS, + _BITSTR_BITS + 1, + 2 * _BITSTR_BITS - 1, + 2 * _BITSTR_BITS, + 1023, + 1024 + }; + + for (unsigned long i = 0; i < nitems(bitstr_sizes); i++) { + bitstring_run_stack_test(test, bitstr_sizes[i]); + bitstring_run_heap_test(test, bitstr_sizes[i]); + } +} + +#define BITSTRING_TC_DEFINE(name) \ +ATF_TC_WITHOUT_HEAD(name); \ +static testfunc_t name ## _test; \ + \ +ATF_TC_BODY(name, tc) \ +{ \ + bitstring_test_runner(name ## _test); \ +} \ + \ +static void \ +name ## _test(bitstr_t *bitstr, int nbits, const char *memloc) + +#define BITSTRING_TC_ADD(tp, name) \ +do { \ + ATF_TP_ADD_TC(tp, name); \ +} while (0) + +ATF_TC_WITHOUT_HEAD(bitstr_in_struct); +ATF_TC_BODY(bitstr_in_struct, tc) +{ + struct bitstr_containing_struct { + bitstr_t bit_decl(bitstr, 8); + } test_struct; + + bit_nclear(test_struct.bitstr, 0, 8); +} + +BITSTRING_TC_DEFINE(bit_set) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + memset(bitstr, 0, bitstr_size(nbits)); + + for (int i = 0; i < nbits; i++) { + bit_set(bitstr, i); + + for (int j = 0; j < nbits; j++) { + ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 1 : 0, + "bit_set_%d_%s: Failed on bit %d", + nbits, memloc, i); + } + + bit_clear(bitstr, i); + } +} + +BITSTRING_TC_DEFINE(bit_clear) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i, j; + + memset(bitstr, 0xFF, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_clear(bitstr, i); + + for (j = 0; j < nbits; j++) { + ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 0 : 1, + "bit_clear_%d_%s: Failed on bit %d", + nbits, memloc, i); + } + + bit_set(bitstr, i); + } +} + +BITSTRING_TC_DEFINE(bit_ffs) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i; + int found_set_bit; + + memset(bitstr, 0, bitstr_size(nbits)); + bit_ffs(bitstr, nbits, &found_set_bit); + ATF_REQUIRE_MSG(found_set_bit == -1, + "bit_ffs_%d_%s: Failed all clear bits.", nbits, memloc); + + for (i = 0; i < nbits; i++) { + memset(bitstr, 0xFF, bitstr_size(nbits)); + if (i > 0) + bit_nclear(bitstr, 0, i - 1); + + bit_ffs(bitstr, nbits, &found_set_bit); + ATF_REQUIRE_MSG(found_set_bit == i, + "bit_ffs_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_set_bit); + } +} + +BITSTRING_TC_DEFINE(bit_ffc) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i; + int found_clear_bit; + + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_ffc(bitstr, nbits, &found_clear_bit); + ATF_REQUIRE_MSG(found_clear_bit == -1, + "bit_ffc_%d_%s: Failed all set bits.", nbits, memloc); + + for (i = 0; i < nbits; i++) { + memset(bitstr, 0, bitstr_size(nbits)); + if (i > 0) + bit_nset(bitstr, 0, i - 1); + + bit_ffc(bitstr, nbits, &found_clear_bit); + ATF_REQUIRE_MSG(found_clear_bit == i, + "bit_ffc_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_clear_bit); + } +} + +BITSTRING_TC_DEFINE(bit_ffs_at) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i; + int found_set_bit; + + memset(bitstr, 0xFF, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffs_at(bitstr, i, nbits, &found_set_bit); + ATF_REQUIRE_MSG(found_set_bit == i, + "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_set_bit); + } + + memset(bitstr, 0, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffs_at(bitstr, i, nbits, &found_set_bit); + ATF_REQUIRE_MSG(found_set_bit == -1, + "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_set_bit); + } + + memset(bitstr, 0x55, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffs_at(bitstr, i, nbits, &found_set_bit); + if (i == nbits - 1 && (nbits & 1) == 0) { + ATF_REQUIRE_MSG(found_set_bit == -1, + "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_set_bit); + } else { + ATF_REQUIRE_MSG(found_set_bit == i + (i & 1), + "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_set_bit); + } + } + + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffs_at(bitstr, i, nbits, &found_set_bit); + if (i == nbits - 1 && (nbits & 1) != 0) { + ATF_REQUIRE_MSG(found_set_bit == -1, + "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_set_bit); + } else { + ATF_REQUIRE_MSG( + found_set_bit == i + ((i & 1) ? 0 : 1), + "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_set_bit); + } + } +} + +BITSTRING_TC_DEFINE(bit_ffc_at) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i; + int found_clear_bit; + + memset(bitstr, 0, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffc_at(bitstr, i, nbits, &found_clear_bit); + ATF_REQUIRE_MSG(found_clear_bit == i, + "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_clear_bit); + } + + memset(bitstr, 0xFF, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffc_at(bitstr, i, nbits, &found_clear_bit); + ATF_REQUIRE_MSG(found_clear_bit == -1, + "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_clear_bit); + } + + memset(bitstr, 0x55, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffc_at(bitstr, i, nbits, &found_clear_bit); + if (i == nbits - 1 && (nbits & 1) != 0) { + ATF_REQUIRE_MSG(found_clear_bit == -1, + "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_clear_bit); + } else { + ATF_REQUIRE_MSG( + found_clear_bit == i + ((i & 1) ? 0 : 1), + "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_clear_bit); + } + } + + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (i = 0; i < nbits; i++) { + bit_ffc_at(bitstr, i, nbits, &found_clear_bit); + if (i == nbits - 1 && (nbits & 1) == 0) { + ATF_REQUIRE_MSG(found_clear_bit == -1, + "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_clear_bit); + } else { + ATF_REQUIRE_MSG(found_clear_bit == i + (i & 1), + "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", + nbits, memloc, i, found_clear_bit); + } + } +} + +BITSTRING_TC_DEFINE(bit_nclear) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i, j; + int found_set_bit; + int found_clear_bit; + + for (i = 0; i < nbits; i++) { + for (j = i; j < nbits; j++) { + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_nclear(bitstr, i, j); + + bit_ffc(bitstr, nbits, &found_clear_bit); + ATF_REQUIRE_MSG( + found_clear_bit == i, + "bit_nclear_%d_%d_%d%s: Failed with result %d", + nbits, i, j, memloc, found_clear_bit); + + bit_ffs_at(bitstr, i, nbits, &found_set_bit); + ATF_REQUIRE_MSG( + (j + 1 < nbits) ? found_set_bit == j + 1 : -1, + "bit_nset_%d_%d_%d%s: Failed with result %d", + nbits, i, j, memloc, found_set_bit); + } + } +} + +BITSTRING_TC_DEFINE(bit_nset) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i, j; + int found_set_bit; + int found_clear_bit; + + for (i = 0; i < nbits; i++) { + for (j = i; j < nbits; j++) { + memset(bitstr, 0, bitstr_size(nbits)); + bit_nset(bitstr, i, j); + + bit_ffs(bitstr, nbits, &found_set_bit); + ATF_REQUIRE_MSG( + found_set_bit == i, + "bit_nset_%d_%d_%d%s: Failed with result %d", + nbits, i, j, memloc, found_set_bit); + + bit_ffc_at(bitstr, i, nbits, &found_clear_bit); + ATF_REQUIRE_MSG( + (j + 1 < nbits) ? found_clear_bit == j + 1 : -1, + "bit_nset_%d_%d_%d%s: Failed with result %d", + nbits, i, j, memloc, found_clear_bit); + } + } +} + +ATF_TP_ADD_TCS(tp) +{ + ATF_TP_ADD_TC(tp, bitstr_in_struct); + BITSTRING_TC_ADD(tp, bit_set); + BITSTRING_TC_ADD(tp, bit_clear); + BITSTRING_TC_ADD(tp, bit_ffs); + BITSTRING_TC_ADD(tp, bit_ffc); + BITSTRING_TC_ADD(tp, bit_ffs_at); + BITSTRING_TC_ADD(tp, bit_ffc_at); + BITSTRING_TC_ADD(tp, bit_nclear); + BITSTRING_TC_ADD(tp, bit_nset); + return atf_no_error(); +} Index: usr.sbin/bluetooth/hccontrol/le.c =================================================================== --- usr.sbin/bluetooth/hccontrol/le.c +++ usr.sbin/bluetooth/hccontrol/le.c @@ -32,9 +32,9 @@ #include #include #include -#include #include #include +#include #include #include #include