Index: head/etc/mtree/BSD.tests.dist =================================================================== --- head/etc/mtree/BSD.tests.dist +++ head/etc/mtree/BSD.tests.dist @@ -460,6 +460,8 @@ .. posixshm .. + sys + .. vfs .. vm Index: head/include/bitstring.h =================================================================== --- head/include/bitstring.h +++ head/include/bitstring.h @@ -29,6 +29,8 @@ #ifndef _BITSTRING_H_ #define _BITSTRING_H_ +#include +#include #include #endif /* _BITSTRING_H_ */ Index: head/lib/libbluetooth/bluetooth.h =================================================================== --- head/lib/libbluetooth/bluetooth.h +++ head/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: head/sbin/hastd/activemap.c =================================================================== --- head/sbin/hastd/activemap.c +++ head/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: head/share/man/man3/bitstring.3 =================================================================== --- head/share/man/man3/bitstring.3 +++ head/share/man/man3/bitstring.3 @@ -27,23 +27,54 @@ .\" 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$ .\" -.Dd October 17, 2015 +.Dd May 4, 2016 .Dt BITSTRING 3 .Os .Sh NAME .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: head/sys/dev/xen/blkback/blkback.c =================================================================== --- head/sys/dev/xen/blkback/blkback.c +++ head/sys/dev/xen/blkback/blkback.c @@ -977,8 +977,8 @@ static uint8_t * xbb_get_kva(struct xbb_softc *xbb, int nr_pages) { - intptr_t first_clear; - intptr_t num_clear; + int first_clear; + int num_clear; uint8_t *free_kva; int i; @@ -1027,7 +1027,7 @@ first_clear + nr_pages - 1); free_kva = xbb->kva + - (uint8_t *)(first_clear * PAGE_SIZE); + (uint8_t *)((intptr_t)first_clear * PAGE_SIZE); KASSERT(free_kva >= (uint8_t *)xbb->kva && free_kva + (nr_pages * PAGE_SIZE) <= @@ -2967,10 +2967,6 @@ return 0; } -/* Needed to make bit_alloc() macro work */ -#define calloc(count, size) malloc((count)*(size), M_XENBLOCKBACK, \ - M_NOWAIT|M_ZERO); - /** * Size KVA and pseudo-physical address allocations based on negotiated * values for the size and number of I/O requests, and the size of our @@ -2989,7 +2985,7 @@ xbb->kva_size = xbb->reqlist_kva_size + (xbb->ring_config.ring_pages * PAGE_SIZE); - xbb->kva_free = bit_alloc(xbb->reqlist_kva_pages); + xbb->kva_free = bit_alloc(xbb->reqlist_kva_pages, M_XENBLOCKBACK, M_NOWAIT); if (xbb->kva_free == NULL) return (ENOMEM); Index: head/sys/kern/subr_unit.c =================================================================== --- head/sys/kern/subr_unit.c +++ head/sys/kern/subr_unit.c @@ -67,13 +67,13 @@ * N is the number of the highest unit allocated. */ +#include #include #include #ifdef _KERNEL #include -#include #include #include #include @@ -169,7 +169,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. @@ -183,14 +183,33 @@ }; struct unrb { - u_char busy; - bitstr_t map[sizeof(struct unr) - 1]; + bitstr_t map[sizeof(struct unr) / sizeof(bitstr_t)]; }; -CTASSERT(sizeof(struct unr) == sizeof(struct unrb)); +CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0); + +/* Number of bits we can store in the bitmap */ +#define NBITS (8 * sizeof(((struct unrb*)NULL)->map)) + +/* Is the unrb empty in at least the first len bits? */ +static inline bool +ub_empty(struct unrb *ub, int len) { + int first_set; + + bit_ffs(ub->map, len, &first_set); + return (first_set == -1); +} + +/* Is the unrb full? That is, is the number of set elements equal to len? */ +static inline bool +ub_full(struct unrb *ub, int len) +{ + int first_clear; + + bit_ffc(ub->map, len, &first_clear); + return (first_clear == -1); +} -/* Number of bits in the bitmap */ -#define NBITS ((int)sizeof(((struct unrb *)NULL)->map) * 8) #if defined(DIAGNOSTIC) || !defined(_KERNEL) /* @@ -214,16 +233,13 @@ 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, - ("UNR inconsistency: busy %u found %u (line %d)\n", - ub->busy, w, line)); y += w; } else if (up->ptr != NULL) y += up->len; @@ -239,7 +255,7 @@ #else static __inline void -check_unrhdr(struct unrhdr *uh, int line) +check_unrhdr(struct unrhdr *uh __unused, int line __unused) { } @@ -417,32 +433,24 @@ a = us->len; l = us->ptr == uh ? 1 : 0; ub = (void *)us; - ub->busy = 0; - if (l) { + bit_nclear(ub->map, 0, NBITS - 1); + if (l) bit_nset(ub->map, 0, a); - ub->busy += a; - } else { - bit_nclear(ub->map, 0, a); - } if (!is_bitmap(uh, uf)) { - if (uf->ptr == NULL) { + if (uf->ptr == NULL) bit_nclear(ub->map, a, a + uf->len - 1); - } else { + else bit_nset(ub->map, a, a + uf->len - 1); - ub->busy += uf->len; - } uf->ptr = ub; uf->len += a; us = uf; } else { ubf = uf->ptr; for (l = 0; l < uf->len; l++, a++) { - if (bit_test(ubf->map, l)) { + if (bit_test(ubf->map, l)) bit_set(ub->map, a); - ub->busy++; - } else { + else bit_clear(ub->map, a); - } } uf->len = a; delete_unr(uh, uf->ptr); @@ -464,19 +472,16 @@ delete_unr(uh, uf); } else if (uf->ptr == uh) { bit_nset(ub->map, us->len, us->len + uf->len - 1); - ub->busy += uf->len; us->len += uf->len; TAILQ_REMOVE(&uh->head, uf, list); delete_unr(uh, uf); } else { ubf = uf->ptr; for (l = 0; l < uf->len; l++, us->len++) { - if (bit_test(ubf->map, l)) { + if (bit_test(ubf->map, l)) bit_set(ub->map, us->len); - ub->busy++; - } else { + else bit_clear(ub->map, us->len); - } } TAILQ_REMOVE(&uh->head, uf, list); delete_unr(uh, ubf); @@ -499,10 +504,10 @@ /* 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_full(ub, up->len)) { delete_unr(uh, up->ptr); up->ptr = uh; - } else if (ub->busy == 0) { + } else if (ub_empty(ub, up->len)) { delete_unr(uh, up->ptr); up->ptr = NULL; } @@ -600,11 +605,9 @@ up->len--; } else { /* bitmap */ ub = up->ptr; - KASSERT(ub->busy < 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++; x += y; } uh->busy++; @@ -688,7 +691,6 @@ ub = up->ptr; if (bit_test(ub->map, i) == 0) { bit_set(ub->map, i); - ub->busy++; goto done; } else return (-1); @@ -807,7 +809,6 @@ ("UNR: Freeing free item %d (bitmap)\n", item)); bit_clear(ub->map, item); uh->busy--; - ub->busy--; collapse_unr(uh, up); return; } @@ -905,7 +906,7 @@ printf("alloc\n"); else { ub = up->ptr; - printf("bitmap(%d) [", ub->busy); + printf("bitmap ["); for (x = 0; x < up->len; x++) { if (bit_test(ub->map, x)) printf("#"); @@ -1025,7 +1026,7 @@ printf("sizeof(struct unr) %zu\n", sizeof(struct unr)); printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb)); printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr)); - printf("NBITS %d\n", NBITS); + printf("NBITS %lu\n", NBITS); x = 1; for (m = 0; m < count * reps; m++) { j = random(); Index: head/sys/net/flowtable.c =================================================================== --- head/sys/net/flowtable.c +++ head/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: head/sys/sys/bitstring.h =================================================================== --- head/sys/sys/bitstring.h +++ head/sys/sys/bitstring.h @@ -29,118 +29,231 @@ * 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: 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 1100106 /* Master, propagated to newvers */ +#define __FreeBSD_version 1100107 /* Master, propagated to newvers */ /* * __FreeBSD_kernel__ indicates that this system uses the kernel of FreeBSD, Index: head/tests/sys/Makefile =================================================================== --- head/tests/sys/Makefile +++ head/tests/sys/Makefile @@ -19,6 +19,7 @@ TESTS_SUBDIRS+= netinet TESTS_SUBDIRS+= opencrypto TESTS_SUBDIRS+= posixshm +TESTS_SUBDIRS+= sys TESTS_SUBDIRS+= vfs TESTS_SUBDIRS+= vm Index: head/tests/sys/sys/Makefile =================================================================== --- head/tests/sys/sys/Makefile +++ head/tests/sys/sys/Makefile @@ -0,0 +1,13 @@ +# $FreeBSD$ + +PACKAGE= tests +FILESGROUPS= TESTS +TESTSPACKAGE= ${PACKAGE} + +TESTSDIR= ${TESTSBASE}/sys/sys + +ATF_TESTS_C= bitstring_test + +WARNS?= 5 + +.include Index: head/tests/sys/sys/bitstring_test.c =================================================================== --- head/tests/sys/sys/bitstring_test.c +++ head/tests/sys/sys/bitstring_test.c @@ -0,0 +1,359 @@ +/*- + * 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, 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: head/usr.sbin/bluetooth/hccontrol/le.c =================================================================== --- head/usr.sbin/bluetooth/hccontrol/le.c +++ head/usr.sbin/bluetooth/hccontrol/le.c @@ -32,9 +32,9 @@ #include #include #include -#include #include #include +#include #include #include #include