Re: git: c56f45f2a9da - main - bitstring: Support large bit strings.

From: Jessica Clarke <jrtc27_at_freebsd.org>
Date: Wed, 22 Nov 2023 22:51:47 UTC
On 22 Nov 2023, at 22:31, Dag-Erling Smørgrav <des@FreeBSD.org> wrote:
> 
> The branch main has been updated by des:
> 
> URL: https://cgit.FreeBSD.org/src/commit/?id=c56f45f2a9da7d989b79fd6c34b63100609ff9ae
> 
> commit c56f45f2a9da7d989b79fd6c34b63100609ff9ae
> Author:     Dag-Erling Smørgrav <des@FreeBSD.org>
> AuthorDate: 2023-11-22 22:30:03 +0000
> Commit:     Dag-Erling Smørgrav <des@FreeBSD.org>
> CommitDate: 2023-11-22 22:30:03 +0000
> 
>    bitstring: Support large bit strings.
> 
>    Replace int with either size_t or ssize_t (depending on context) in
>    order to support bit strings up to SSIZE_MAX bits in length.  Since
>    some of the arguments that need to change type are pointers, we must
>    resort to light preprocessor trickery to avoid breaking existing code.

You want more than 2^31 bits, i.e. 256 MiB, in a single bitstring? I
mean, sure, there’s no reason the code shouldn’t support that, but I
have serious questions about how sensible that is to do in reality...

Jess

>    MFC after:      3 weeks
>    Sponsored by:   Klara, Inc.
>    Reviewed by:    kevans
>    Differential Revision:  https://reviews.freebsd.org/D42698
> ---
> share/man/man3/bitstring.3     |  50 ++++++-------
> sys/sys/bitstring.h            | 158 +++++++++++++++++------------------------
> tests/sys/sys/bitstring_test.c |  90 ++++++++++++++++++++++-
> 3 files changed, 181 insertions(+), 117 deletions(-)
> 
> diff --git a/share/man/man3/bitstring.3 b/share/man/man3/bitstring.3
> index ac87ac6d9124..808cd48f384b 100644
> --- a/share/man/man3/bitstring.3
> +++ b/share/man/man3/bitstring.3
> @@ -57,7 +57,7 @@
> .\"
> .\"     @(#)bitstring.3 8.1 (Berkeley) 7/19/93
> .\"
> -.Dd August 8, 2021
> +.Dd November 21, 2023
> .Dt BITSTRING 3
> .Os
> .Sh NAME
> @@ -85,49 +85,49 @@
> .Sh SYNOPSIS
> .In bitstring.h
> .Ft bitstr_t *
> -.Fn bit_alloc "int nbits"
> +.Fn bit_alloc "size_t nbits"
> .Ft void
> -.Fn bit_decl "bitstr_t *name" "int nbits"
> +.Fn bit_decl "bitstr_t *name" "size_t nbits"
> .Ft void
> -.Fn bit_clear "bitstr_t *name" "int bit"
> +.Fn bit_clear "bitstr_t *name" "size_t bit"
> .Ft void
> -.Fn bit_count "bitstr_t *name" "int count" "int nbits" "int *value"
> +.Fn bit_count "bitstr_t *name" "size_t count" "size_t nbits" "ssize_t *value"
> .Ft void
> -.Fn bit_ffc "bitstr_t *name" "int nbits" "int *value"
> +.Fn bit_ffc "bitstr_t *name" "size_t nbits" "ssize_t *value"
> .Ft void
> -.Fn bit_ffs "bitstr_t *name" "int nbits" "int *value"
> +.Fn bit_ffs "bitstr_t *name" "size_t nbits" "ssize_t *value"
> .Ft void
> -.Fn bit_ffc_at "bitstr_t *name" "int start" "int nbits" "int *value"
> +.Fn bit_ffc_at "bitstr_t *name" "size_t start" "size_t nbits" "ssize_t *value"
> .Ft void
> -.Fn bit_ffs_at "bitstr_t *name" "int start" "int nbits" "int *value"
> +.Fn bit_ffs_at "bitstr_t *name" "size_t start" "size_t nbits" "ssize_t *value"
> .Ft void
> -.Fn bit_ff_at "bitstr_t *name" "int start" "int nbits" "int match" "int *value"
> +.Fn bit_ff_at "bitstr_t *name" "size_t start" "size_t nbits" "int match" "ssize_t *value"
> .Ft void
> -.Fn bit_ffc_area "bitstr_t *name" "int nbits" "int size" "int *value"
> +.Fn bit_ffc_area "bitstr_t *name" "size_t nbits" "size_t size" "ssize_t *value"
> .Ft void
> -.Fn bit_ffs_area "bitstr_t *name" "int nbits" "int size" "int *value"
> +.Fn bit_ffs_area "bitstr_t *name" "size_t nbits" "size_t size" "ssize_t *value"
> .Ft void
> -.Fn bit_ffc_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value"
> +.Fn bit_ffc_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "ssize_t *value"
> .Ft void
> -.Fn bit_ffs_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value"
> +.Fn bit_ffs_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "ssize_t *value"
> .Ft void
> -.Fn bit_ff_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int match" "int *value"
> -.Fn bit_foreach "bitstr_t *name" "int nbits" "int var"
> -.Fn bit_foreach_at "bitstr_t *name" "int start" "int nbits" "int var"
> -.Fn bit_foreach_unset "bitstr_t *name" "int nbits" "int var"
> -.Fn bit_foreach_unset_at "bitstr_t *name" "int start" "int nbits" "int var"
> +.Fn bit_ff_area_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t size" "int match" "ssize_t *value"
> +.Fn bit_foreach "bitstr_t *name" "size_t nbits" "size_t var"
> +.Fn bit_foreach_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t var"
> +.Fn bit_foreach_unset "bitstr_t *name" "size_t nbits" "size_t var"
> +.Fn bit_foreach_unset_at "bitstr_t *name" "size_t start" "size_t nbits" "size_t var"
> .Ft void
> -.Fn bit_nclear "bitstr_t *name" "int start" "int stop"
> +.Fn bit_nclear "bitstr_t *name" "size_t start" "size_t stop"
> .Ft void
> -.Fn bit_nset "bitstr_t *name" "int start" "int stop"
> +.Fn bit_nset "bitstr_t *name" "size_t start" "size_t stop"
> .Ft int
> -.Fn bit_ntest "bitstr_t *name" "int start" "int stop" "int match"
> +.Fn bit_ntest "bitstr_t *name" "size_t start" "size_t stop" "int match"
> .Ft void
> -.Fn bit_set "bitstr_t *name" "int bit"
> +.Fn bit_set "bitstr_t *name" "size_t bit"
> .Ft int
> -.Fn bitstr_size "int nbits"
> +.Fn bitstr_size "size_t nbits"
> .Ft int
> -.Fn bit_test "bitstr_t *name" "int bit"
> +.Fn bit_test "bitstr_t *name" "size_t bit"
> .Sh DESCRIPTION
> These macros operate on strings of bits.
> .Pp
> diff --git a/sys/sys/bitstring.h b/sys/sys/bitstring.h
> index 127de2ebc419..8a976962dd36 100644
> --- a/sys/sys/bitstring.h
> +++ b/sys/sys/bitstring.h
> @@ -75,35 +75,33 @@ typedef unsigned long bitstr_t;
> #define _BITSTR_MASK (~0UL)
> #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
> 
> -#ifdef roundup2
> -#define        _bit_roundup2 roundup2
> -#else
> -#define        _bit_roundup2(x, y)        (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
> -#endif
> +/* round up x to the next multiple of y if y is a power of two */
> +#define _bit_roundup2(x, y) \
> + (((size_t)(x) + (y) - 1) & ~((size_t)(y) - 1))
> 
> /* bitstr_t in bit string containing the bit. */
> -static inline int
> -_bit_idx(int _bit)
> +static inline size_t
> +_bit_idx(size_t _bit)
> {
> return (_bit / _BITSTR_BITS);
> }
> 
> /* bit number within bitstr_t at _bit_idx(_bit). */
> -static inline int
> -_bit_offset(int _bit)
> +static inline size_t
> +_bit_offset(size_t _bit)
> {
> return (_bit % _BITSTR_BITS);
> }
> 
> /* Mask for the bit within its long. */
> static inline bitstr_t
> -_bit_mask(int _bit)
> +_bit_mask(size_t _bit)
> {
> return (1UL << _bit_offset(_bit));
> }
> 
> static inline bitstr_t
> -_bit_make_mask(int _start, int _stop)
> +_bit_make_mask(size_t _start, size_t _stop)
> {
> return ((_BITSTR_MASK << _bit_offset(_start)) &
>    (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
> @@ -111,18 +109,18 @@ _bit_make_mask(int _start, int _stop)
> 
> /*----------------------------- Public Interface -----------------------------*/
> /* Number of bytes allocated for a bit string of nbits bits */
> -#define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
> +#define bitstr_size(_nbits) (_bit_roundup2((_nbits), _BITSTR_BITS) / 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)
> +bit_alloc(size_t _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)
> +bit_alloc(size_t _nbits)
> {
> return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
> }
> @@ -134,28 +132,28 @@ bit_alloc(int _nbits)
> 
> /* Is bit N of bit string set? */
> static inline int
> -bit_test(const bitstr_t *_bitstr, int _bit)
> +bit_test(const bitstr_t *_bitstr, size_t _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)
> +bit_set(bitstr_t *_bitstr, size_t _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)
> +bit_clear(bitstr_t *_bitstr, size_t _bit)
> {
> _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
> }
> 
> /* Are bits in [start ... stop] in bit string all 0 or all 1? */
> static inline int
> -bit_ntest(const bitstr_t *_bitstr, int _start, int _stop, int _match)
> +bit_ntest(const bitstr_t *_bitstr, size_t _start, size_t _stop, int _match)
> {
> const bitstr_t *_stopbitstr;
> bitstr_t _mask;
> @@ -183,7 +181,7 @@ bit_ntest(const bitstr_t *_bitstr, int _start, int _stop, int _match)
> 
> /* Set bits start ... stop inclusive in bit string. */
> static inline void
> -bit_nset(bitstr_t *_bitstr, int _start, int _stop)
> +bit_nset(bitstr_t *_bitstr, size_t _start, size_t _stop)
> {
> bitstr_t *_stopbitstr;
> 
> @@ -206,7 +204,7 @@ bit_nset(bitstr_t *_bitstr, int _start, int _stop)
> 
> /* Clear bits start ... stop inclusive in bit string. */
> static inline void
> -bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
> +bit_nclear(bitstr_t *_bitstr, size_t _start, size_t _stop)
> {
> bitstr_t *_stopbitstr;
> 
> @@ -228,20 +226,17 @@ bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
> }
> 
> /* Find the first '_match'-bit in bit string at or after bit start. */
> -static inline void
> -bit_ff_at(bitstr_t *_bitstr, int _start, int _nbits, int _match,
> -    int *_result)
> +static inline ssize_t
> +bit_ff_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, int _match)
> {
> bitstr_t *_curbitstr;
> bitstr_t *_stopbitstr;
> bitstr_t _mask;
> bitstr_t _test;
> - int _value;
> + ssize_t _value;
> 
> - if (_start >= _nbits || _nbits <= 0) {
> - *_result = -1;
> - return;
> - }
> + if (_start >= _nbits || _nbits <= 0)
> + return (-1);
> 
> _curbitstr = _bitstr + _bit_idx(_start);
> _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
> @@ -255,51 +250,40 @@ bit_ff_at(bitstr_t *_bitstr, int _start, int _nbits, int _match,
> 
> _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1;
> if (_test == 0 ||
> -    (_bit_offset(_nbits) != 0 && _value >= _nbits))
> +    (_bit_offset(_nbits) != 0 && (size_t)_value >= _nbits))
> _value = -1;
> - *_result = _value;
> + return (_value);
> }
> +#define bit_ff_at(_bitstr, _start, _nbits, _match, _resultp) \
> + *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), (_match))
> 
> /* 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)
> -{
> - bit_ff_at(_bitstr, _start, _nbits, 1, _result);
> -}
> +#define bit_ffs_at(_bitstr, _start, _nbits, _resultp) \
> + *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 1)
> 
> /* 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)
> -{
> - bit_ff_at(_bitstr, _start, _nbits, 0, _result);
> -}
> +#define bit_ffc_at(_bitstr, _start, _nbits, _resultp) \
> + *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 0)
> 
> /* 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);
> -}
> +#define bit_ffs(_bitstr, _nbits, _resultp) \
> + *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 1)
> 
> /* 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);
> -}
> +#define bit_ffc(_bitstr, _nbits, _resultp) \
> + *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 0)
> 
> /* Find contiguous sequence of at least size '_match'-bits at or after start */
> -static inline void
> -bit_ff_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
> -    int _match, int *_result)
> +static inline ssize_t
> +bit_ff_area_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, size_t _size,
> +    int _match)
> {
> bitstr_t *_curbitstr, _mask, _test;
> - int _value, _last, _shft, _maxshft;
> + size_t _last, _shft, _maxshft;
> + ssize_t _value;
> 
> - if (_start + _size > _nbits || _nbits <= 0) {
> - *_result = -1;
> - return;
> - }
> + if (_start + _size > _nbits || _nbits <= 0)
> + return (-1);
> 
> _mask = _match ? _BITSTR_MASK : 0;
> _maxshft = _bit_idx(_size - 1) == 0 ? _size : (int)_BITSTR_BITS;
> @@ -330,48 +314,37 @@ bit_ff_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
> break;
> /* A solution here needs bits from the next word. */
> }
> - *_result = _value;
> + return (_value);
> }
> +#define bit_ff_area_at(_bitstr, _start, _nbits, _size, _match, _resultp) \
> + *(_resultp) = bit_ff_area_at_(_bitstr, _start, _nbits, _size, _match);
> 
> /* Find contiguous sequence of at least size set bits at or after start */
> -static inline void
> -bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
> -    int *_result)
> -{
> - bit_ff_area_at(_bitstr, _start, _nbits, _size, 1, _result);
> -}
> +#define bit_ffs_area_at(_bitstr, _start, _nbits, _size, _resultp) \
> + *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 1)
> 
> /* Find contiguous sequence of at least size cleared bits at or after start */
> -static inline void
> -bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
> -    int *_result)
> -{
> - bit_ff_area_at(_bitstr, _start, _nbits, _size, 0, _result);
> -}
> +#define bit_ffc_area_at(_bitstr, _start, _nbits, _size, _resultp) \
> + *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 0)
> 
> /* Find contiguous sequence of at least size set bits in bit string */
> -static inline void
> -bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
> -{
> - bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
> -}
> +#define bit_ffs_area(_bitstr, _nbits, _size, _resultp) \
> + *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 1)
> 
> /* Find contiguous sequence of at least size cleared bits in bit string */
> -static inline void
> -bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
> -{
> - bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
> -}
> +#define bit_ffc_area(_bitstr, _nbits, _size, _resultp) \
> + *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 0)
> 
> /* 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)
> +static inline ssize_t
> +bit_count_(bitstr_t *_bitstr, size_t _start, size_t _nbits)
> {
> bitstr_t *_curbitstr, mask;
> - int _value = 0, curbitstr_len;
> + size_t curbitstr_len;
> + ssize_t _value = 0;
> 
> if (_start >= _nbits)
> - goto out;
> + return (0);
> 
> _curbitstr = _bitstr + _bit_idx(_start);
> _nbits -= _BITSTR_BITS * _bit_idx(_start);
> @@ -383,6 +356,8 @@ bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
> mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
> _value += __bitcountl(*_curbitstr & mask);
> _curbitstr++;
> + if (_nbits < _BITSTR_BITS)
> + return (_value);
> _nbits -= _BITSTR_BITS;
> }
> while (_nbits >= (int)_BITSTR_BITS) {
> @@ -395,23 +370,24 @@ bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
> _value += __bitcountl(*_curbitstr & mask);
> }
> 
> -out:
> - *_result = _value;
> + return (_value);
> }
> +#define bit_count(_bitstr, _start, _nbits, _resultp) \
> + *(_resultp) = bit_count_((_bitstr), (_start), (_nbits))
> 
> /* Traverse all set bits, assigning each location in turn to iter */
> #define bit_foreach_at(_bitstr, _start, _nbits, _iter) \
> - for (bit_ffs_at((_bitstr), (_start), (_nbits), &(_iter)); \
> + for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 1); \
>     (_iter) != -1; \
> -     bit_ffs_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
> +     (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 1))
> #define bit_foreach(_bitstr, _nbits, _iter) \
> bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter)
> 
> /* Traverse all unset bits, assigning each location in turn to iter */
> #define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \
> - for (bit_ffc_at((_bitstr), (_start), (_nbits), &(_iter)); \
> + for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 0); \
>     (_iter) != -1; \
> -     bit_ffc_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
> +     (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 0))
> #define bit_foreach_unset(_bitstr, _nbits, _iter) \
> bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter)
> 
> diff --git a/tests/sys/sys/bitstring_test.c b/tests/sys/sys/bitstring_test.c
> index 0c214b9e67a7..a48042a4a063 100644
> --- a/tests/sys/sys/bitstring_test.c
> +++ b/tests/sys/sys/bitstring_test.c
> @@ -1,5 +1,6 @@
> /*-
>  * Copyright (c) 2014 Spectra Logic Corporation
> + * Copyright (c) 2023 Klara, Inc.
>  * All rights reserved.
>  *
>  * Redistribution and use in source and binary forms, with or without
> @@ -31,7 +32,7 @@
> #include <sys/param.h>
> 
> #include <bitstring.h>
> -#include <stdio.h>
> +#include <malloc_np.h>
> 
> #include <atf-c.h>
> 
> @@ -51,6 +52,7 @@ bitstring_run_heap_test(testfunc_t *test, int nbits)
> bitstr_t *bitstr = bit_alloc(nbits);
> 
> test(bitstr, nbits, "heap");
> + free(bitstr);
> }
> 
> static void
> @@ -862,6 +864,91 @@ BITSTRING_TC_DEFINE(bit_foreach_unset_at)
> }
> }
> 
> +/*
> + * Perform various tests on large bit strings.  We can't simply add larger
> + * sizes to bitstring_runner as most of the existing tests are exhaustive
> + * and would take forever to run for large values of nbits.
> + *
> + * On 32-bit platforms, we use nbits = SSIZE_MAX (2147483647) bits, which
> + * is the largest we can hope to support; on 64-bit platforms, we use
> + * nbits = INT_MAX + 30 (2147483677), which is small enough to be
> + * practicable yet large enough to reveal arithmetic overflow bugs.
> + */
> +ATF_TC_WITHOUT_HEAD(bitstr_large);
> +ATF_TC_BODY(bitstr_large, tc)
> +{
> + size_t nbits  = INT_MAX < SSIZE_MAX ? (size_t)INT_MAX + 30 : SSIZE_MAX;
> + size_t early = 5, late = nbits - 5;
> + ssize_t fc, fs;
> + bitstr_t *b;
> +
> + /* Check for overflow in size calculation */
> + ATF_REQUIRE(nbits >= (size_t)INT_MAX);
> + ATF_REQUIRE(bitstr_size(nbits) >= nbits / 8);
> +
> + /* Allocate the bit string */
> + ATF_REQUIRE(b = bit_alloc(nbits));
> +
> + /* Check that we allocated enough */
> + ATF_REQUIRE(malloc_usable_size(b) >= bitstr_size(nbits));
> +
> + /* Check ffc, ffs on all-zeroes string */
> + bit_ffc(b, nbits, &fc);
> + ATF_CHECK_EQ(0L, fc);
> + bit_ffs(b, nbits, &fs);
> + ATF_CHECK_EQ(-1L, fs);
> +
> + /* Set, test, and clear an early bit */
> + bit_set(b, early);
> + bit_ffs(b, nbits, &fs);
> + ATF_CHECK_EQ((ssize_t)early, fs);
> + ATF_CHECK_EQ(0, bit_test(b, early - 1));
> + ATF_CHECK(bit_test(b, early) != 0);
> + ATF_CHECK_EQ(0, bit_test(b, early + 1));
> + bit_clear(b, early);
> + ATF_CHECK_EQ(0, bit_test(b, early));
> +
> + /* Set, test, and clear an early bit range */
> + bit_nset(b, early - 1, early + 1);
> + bit_ffs(b, nbits, &fs);
> + ATF_CHECK_EQ((ssize_t)early - 1, fs);
> + ATF_CHECK_EQ(0, bit_test(b, early - 2));
> + ATF_CHECK(bit_test(b, early - 1));
> + ATF_CHECK(bit_test(b, early));
> + ATF_CHECK(bit_test(b, early + 1));
> + ATF_CHECK_EQ(0, bit_test(b, early + 2));
> + bit_nclear(b, early - 1, early + 1);
> + ATF_CHECK_EQ(0, bit_test(b, early - 1));
> + ATF_CHECK_EQ(0, bit_test(b, early));
> + ATF_CHECK_EQ(0, bit_test(b, early + 1));
> +
> + /* Set, test, and clear a late bit */
> + bit_set(b, late);
> + bit_ffs(b, nbits, &fs);
> + ATF_CHECK_EQ((ssize_t)late, fs);
> + ATF_CHECK_EQ(0, bit_test(b, late - 1));
> + ATF_CHECK(bit_test(b, late) != 0);
> + ATF_CHECK_EQ(0, bit_test(b, late + 1));
> + bit_clear(b, late);
> + ATF_CHECK_EQ(0, bit_test(b, late));
> +
> + /* Set, test, and clear a late bit range */
> + bit_nset(b, late - 1, late + 1);
> + bit_ffs(b, nbits, &fs);
> + ATF_CHECK_EQ((ssize_t)late - 1, fs);
> + ATF_CHECK_EQ(0, bit_test(b, late - 2));
> + ATF_CHECK(bit_test(b, late - 1));
> + ATF_CHECK(bit_test(b, late));
> + ATF_CHECK(bit_test(b, late + 1));
> + ATF_CHECK_EQ(0, bit_test(b, late + 2));
> + bit_nclear(b, late - 1, late + 1);
> + ATF_CHECK_EQ(0, bit_test(b, late - 1));
> + ATF_CHECK_EQ(0, bit_test(b, late));
> + ATF_CHECK_EQ(0, bit_test(b, late + 1));
> +
> + free(b);
> +}
> +
> ATF_TP_ADD_TCS(tp)
> {
> 
> @@ -884,6 +971,7 @@ ATF_TP_ADD_TCS(tp)
> BITSTRING_TC_ADD(tp, bit_foreach_at);
> BITSTRING_TC_ADD(tp, bit_foreach_unset);
> BITSTRING_TC_ADD(tp, bit_foreach_unset_at);
> + ATF_TP_ADD_TC(tp, bitstr_large);
> 
> return (atf_no_error());
> }