From nobody Wed Nov 22 22:51:47 2023 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4SbGhd2M9yz51Lhl for ; Wed, 22 Nov 2023 22:52:01 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Received: from mail-wm1-f46.google.com (mail-wm1-f46.google.com [209.85.128.46]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1D4" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4SbGhc6sV4z4rdG for ; Wed, 22 Nov 2023 22:52:00 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Authentication-Results: mx1.freebsd.org; none Received: by mail-wm1-f46.google.com with SMTP id 5b1f17b1804b1-4083dbc43cfso1576865e9.3 for ; Wed, 22 Nov 2023 14:52:00 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700693519; x=1701298319; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=keXlrQ7E7WLzoJ8gehp56PufF/vrawSK0eJo1fCC3kg=; b=qWuMlyLmkcPAbajAGRZ/haffA6hLyZJweho/+XdlrG8LTLPIRTi3qdifX1WGhGxoH8 pOsivqTEsPfCn1kKq+Q34o06d4wIFsnTv9bZ0qXf+IkDk9T1KlSKjZHecg33JvwZ0KNn z92mOt3WQOxIOJyxozSvPIsmyROrNLieOACLUb/uVzAHV3I7P44MvZpmyN2povGo6gXg /kxyPtS55L6T3gjiPNN0LaEilnEXC+3endqNDSAMxNjHjPGd1l6ZhPb5f7s2YckFsLh0 odx47NcQZiLD8cOIx6mb627MDiamxuEc2ka//HlPE63nk/BXlpIJPAgd/HtnJstdwDj1 BzVA== X-Gm-Message-State: AOJu0YzfbvKjz4Aj06yroVUohnqeCV6Ttcf0NsTyysas9ZC9kuRPRCfN tUDoGs0YKW4oL8UrOL1qt8ol9Q== X-Google-Smtp-Source: AGHT+IF/xFA/a4pgTMGZNbOhDhED6cK74kBCpZkDEqcdI7QbhDWivG9qHsT0gYMoHnbcv2t8q+6ExQ== X-Received: by 2002:a05:600c:4f16:b0:406:5344:4212 with SMTP id l22-20020a05600c4f1600b0040653444212mr3280943wmq.41.1700693518390; Wed, 22 Nov 2023 14:51:58 -0800 (PST) Received: from smtpclient.apple ([131.111.5.246]) by smtp.gmail.com with ESMTPSA id a14-20020a056000100e00b00332c0aace23sm475273wrx.105.2023.11.22.14.51.57 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Wed, 22 Nov 2023 14:51:57 -0800 (PST) Content-Type: text/plain; charset=utf-8 List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3774.200.91.1.1\)) Subject: Re: git: c56f45f2a9da - main - bitstring: Support large bit strings. From: Jessica Clarke In-Reply-To: <202311222231.3AMMVB1M050070@gitrepo.freebsd.org> Date: Wed, 22 Nov 2023 22:51:47 +0000 Cc: "src-committers@freebsd.org" , "dev-commits-src-all@freebsd.org" , "dev-commits-src-main@freebsd.org" Content-Transfer-Encoding: quoted-printable Message-Id: <4C6024C7-D786-424E-8866-152339FB96D6@freebsd.org> References: <202311222231.3AMMVB1M050070@gitrepo.freebsd.org> To: =?utf-8?Q?Dag-Erling_Sm=C3=B8rgrav?= X-Mailer: Apple Mail (2.3774.200.91.1.1) X-Spamd-Bar: ---- X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:15169, ipnet:209.85.128.0/17, country:US] X-Rspamd-Queue-Id: 4SbGhc6sV4z4rdG On 22 Nov 2023, at 22:31, Dag-Erling Sm=C3=B8rgrav = wrote: >=20 > The branch main has been updated by des: >=20 > URL: = https://cgit.FreeBSD.org/src/commit/?id=3Dc56f45f2a9da7d989b79fd6c34b63100= 609ff9ae >=20 > commit c56f45f2a9da7d989b79fd6c34b63100609ff9ae > Author: Dag-Erling Sm=C3=B8rgrav > AuthorDate: 2023-11-22 22:30:03 +0000 > Commit: Dag-Erling Sm=C3=B8rgrav > CommitDate: 2023-11-22 22:30:03 +0000 >=20 > bitstring: Support large bit strings. >=20 > 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=E2=80=99s no reason the code shouldn=E2=80=99t 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(-) >=20 > 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) >=20 > -#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)) >=20 > /* 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); > } >=20 > /* 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); > } >=20 > /* 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)); > } >=20 > 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) >=20 > /*----------------------------- 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) >=20 > /* 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) >=20 > /* 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)) !=3D 0); > } >=20 > /* 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)] |=3D _bit_mask(_bit); > } >=20 > /* 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)] &=3D ~_bit_mask(_bit); > } >=20 > /* 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) >=20 > /* 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; >=20 > @@ -206,7 +204,7 @@ bit_nset(bitstr_t *_bitstr, int _start, int _stop) >=20 > /* 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; >=20 > @@ -228,20 +226,17 @@ bit_nclear(bitstr_t *_bitstr, int _start, int = _stop) > } >=20 > /* 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; >=20 > - if (_start >=3D _nbits || _nbits <=3D 0) { > - *_result =3D -1; > - return; > - } > + if (_start >=3D _nbits || _nbits <=3D 0) > + return (-1); >=20 > _curbitstr =3D _bitstr + _bit_idx(_start); > _stopbitstr =3D _bitstr + _bit_idx(_nbits - 1); > @@ -255,51 +250,40 @@ bit_ff_at(bitstr_t *_bitstr, int _start, int = _nbits, int _match, >=20 > _value =3D ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1; > if (_test =3D=3D 0 || > - (_bit_offset(_nbits) !=3D 0 && _value >=3D _nbits)) > + (_bit_offset(_nbits) !=3D 0 && (size_t)_value >=3D _nbits)) > _value =3D -1; > - *_result =3D _value; > + return (_value); > } > +#define bit_ff_at(_bitstr, _start, _nbits, _match, _resultp) \ > + *(_resultp) =3D bit_ff_at_((_bitstr), (_start), (_nbits), (_match)) >=20 > /* 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) =3D bit_ff_at_((_bitstr), (_start), (_nbits), 1) >=20 > /* 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) =3D bit_ff_at_((_bitstr), (_start), (_nbits), 0) >=20 > /* 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) =3D bit_ff_at_((_bitstr), 0, (_nbits), 1) >=20 > /* 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) =3D bit_ff_at_((_bitstr), 0, (_nbits), 0) >=20 > /* 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; >=20 > - if (_start + _size > _nbits || _nbits <=3D 0) { > - *_result =3D -1; > - return; > - } > + if (_start + _size > _nbits || _nbits <=3D 0) > + return (-1); >=20 > _mask =3D _match ? _BITSTR_MASK : 0; > _maxshft =3D _bit_idx(_size - 1) =3D=3D 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 =3D _value; > + return (_value); > } > +#define bit_ff_area_at(_bitstr, _start, _nbits, _size, _match, = _resultp) \ > + *(_resultp) =3D bit_ff_area_at_(_bitstr, _start, _nbits, _size, = _match); >=20 > /* 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) =3D bit_ff_area_at_((_bitstr), (_start), (_nbits), = (_size), 1) >=20 > /* 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) =3D bit_ff_area_at_((_bitstr), (_start), (_nbits), = (_size), 0) >=20 > /* 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) =3D bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 1) >=20 > /* 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) =3D bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 0) >=20 > /* 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 =3D 0, curbitstr_len; > + size_t curbitstr_len; > + ssize_t _value =3D 0; >=20 > if (_start >=3D _nbits) > - goto out; > + return (0); >=20 > _curbitstr =3D _bitstr + _bit_idx(_start); > _nbits -=3D _BITSTR_BITS * _bit_idx(_start); > @@ -383,6 +356,8 @@ bit_count(bitstr_t *_bitstr, int _start, int = _nbits, int *_result) > mask =3D _bit_make_mask(_start, _bit_offset(curbitstr_len - 1)); > _value +=3D __bitcountl(*_curbitstr & mask); > _curbitstr++; > + if (_nbits < _BITSTR_BITS) > + return (_value); > _nbits -=3D _BITSTR_BITS; > } > while (_nbits >=3D (int)_BITSTR_BITS) { > @@ -395,23 +370,24 @@ bit_count(bitstr_t *_bitstr, int _start, int = _nbits, int *_result) > _value +=3D __bitcountl(*_curbitstr & mask); > } >=20 > -out: > - *_result =3D _value; > + return (_value); > } > +#define bit_count(_bitstr, _start, _nbits, _resultp) \ > + *(_resultp) =3D bit_count_((_bitstr), (_start), (_nbits)) >=20 > /* 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) =3D bit_ff_at_((_bitstr), (_start), (_nbits), 1); \ > (_iter) !=3D -1; \ > - bit_ffs_at((_bitstr), (_iter) + 1, (_nbits), &(_iter))) > + (_iter) =3D bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 1)) > #define bit_foreach(_bitstr, _nbits, _iter) \ > bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter) >=20 > /* 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) =3D bit_ff_at_((_bitstr), (_start), (_nbits), 0); \ > (_iter) !=3D -1; \ > - bit_ffc_at((_bitstr), (_iter) + 1, (_nbits), &(_iter))) > + (_iter) =3D bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 0)) > #define bit_foreach_unset(_bitstr, _nbits, _iter) \ > bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter) >=20 > 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 >=20 > #include > -#include > +#include >=20 > #include >=20 > @@ -51,6 +52,7 @@ bitstring_run_heap_test(testfunc_t *test, int nbits) > bitstr_t *bitstr =3D bit_alloc(nbits); >=20 > test(bitstr, nbits, "heap"); > + free(bitstr); > } >=20 > static void > @@ -862,6 +864,91 @@ BITSTRING_TC_DEFINE(bit_foreach_unset_at) > } > } >=20 > +/* > + * 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 =3D SSIZE_MAX (2147483647) bits, = which > + * is the largest we can hope to support; on 64-bit platforms, we use > + * nbits =3D 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 =3D INT_MAX < SSIZE_MAX ? (size_t)INT_MAX + 30 : = SSIZE_MAX; > + size_t early =3D 5, late =3D nbits - 5; > + ssize_t fc, fs; > + bitstr_t *b; > + > + /* Check for overflow in size calculation */ > + ATF_REQUIRE(nbits >=3D (size_t)INT_MAX); > + ATF_REQUIRE(bitstr_size(nbits) >=3D nbits / 8); > + > + /* Allocate the bit string */ > + ATF_REQUIRE(b =3D bit_alloc(nbits)); > + > + /* Check that we allocated enough */ > + ATF_REQUIRE(malloc_usable_size(b) >=3D 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) !=3D 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) !=3D 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) > { >=20 > @@ -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); >=20 > return (atf_no_error()); > }