From nobody Wed Dec 13 20:06:30 2023 X-Original-To: dev-commits-src-branches@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 4Sr61y2kfbz54Fqn; Wed, 13 Dec 2023 20:06:30 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Sr61y2Dgnz4Z8v; Wed, 13 Dec 2023 20:06:30 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1702497990; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=9K+QGidL62ZT03pMqzgOpLkoK6jqaLW12RRk7uHGcNU=; b=tFtKlY1lri9vGdegMRFDBd6sDg/ynJ+MdPrxBbl2mHZkVKU+kIxwO4+MsiZVxm0bo2sKyJ iOsxmgIEOnpOxfcqIbry3fvBhQrZfDbPrvYqerXRWo/LZ2UUINWMcwdyz5XLPkIEXefcu4 CE3mSqgA2tV2lMv54IMxlxUNHJnN8WvGJADN+/CjKNSeC/6uMcd/bBOHbTsaxYe6iqMAqi PSpiekRUI23Fv8Bc5GOZ+rkZYSNmoRC+xpihzVZBgVpbVzHuO6tqawJhiCQBOnw7l48db0 V/Q8lwjlbBdIvL01SeQiGIZ4P5TzZYAMHaEIQlDOlfuISdb6q6oJhquEFSWHIQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1702497990; a=rsa-sha256; cv=none; b=pzkNRlZw4mfc1IUyl/W3PVvnGLArNW1m8ou7em/YPoeUhHM9S81ZXFwNx06xnsRb0Ms6xK Rhj8+DyBuig+kPPVLFLbBkdvDysCBxJiCuHy3EkR2VZ2SqihcRNbtY6kPJuq3iGGOLZEEO Ay1PZggow0TmnzjLcNrppERZq+fP23PgH6/LchWogArmgOdWMydzS1JxLusf9xo5Y/6u3+ uOTszHqZCBSxKF92Fg0UTMiEfR/mZBFGl51FRH+/gUzXZkkpaDrLlsxRgL9/GhRm/olztZ bx+EjJeHOjsluGofY3vrHQfUJGQO9rqgE2Ac4roKAgyeP4SerIBbry6nFXoXnw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1702497990; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=9K+QGidL62ZT03pMqzgOpLkoK6jqaLW12RRk7uHGcNU=; b=A2I6USX4gBqEozUQCa+AxIEDY7kfbDew7zcXsgAXCC3pvyLIg0zjLWefb0OjgQfkNHH8bB QnCUswgI91Q8Tz+bFye0vPbcXGddmkPPSKoFUSmPSRD1yIVEyAX8UVM5aZaCU1P3HHnKen hd98lhE8DvzcExa9Kevw5q19zX5or22B4Ek1OZJYMWjZ5KhWr6zeBz8zaCWBZWputolN+Y V2hGzw1/ebpObj+h3EFL/xVejvVbiH5aVb2+RNo+865i7Cjm3f4JcxdHxKRSE3gxXtsGay es4xN9TTTzDi5mXAUu5LHKPb15PeUCVsQ5JecG3Q4Jv0n7Ie8t1StW2nAzZBRg== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4Sr61y1LD6z1BXc; Wed, 13 Dec 2023 20:06:30 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 3BDK6U03087393; Wed, 13 Dec 2023 20:06:30 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 3BDK6U72087390; Wed, 13 Dec 2023 20:06:30 GMT (envelope-from git) Date: Wed, 13 Dec 2023 20:06:30 GMT Message-Id: <202312132006.3BDK6U72087390@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Dag-Erling =?utf-8?Q?Sm=C3=B8rgrav?= Subject: git: e6a359060aeb - stable/13 - bitstring: Support large bit strings. List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-branches@freebsd.org X-BeenThere: dev-commits-src-branches@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: des X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: e6a359060aeb5b5438676dd3be53bdc203b01df3 Auto-Submitted: auto-generated The branch stable/13 has been updated by des: URL: https://cgit.FreeBSD.org/src/commit/?id=e6a359060aeb5b5438676dd3be53bdc203b01df3 commit e6a359060aeb5b5438676dd3be53bdc203b01df3 Author: Dag-Erling Smørgrav AuthorDate: 2023-11-22 22:30:03 +0000 Commit: Dag-Erling Smørgrav CommitDate: 2023-12-13 16:39:37 +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. MFC after: 3 weeks Sponsored by: Klara, Inc. Reviewed by: kevans Differential Revision: https://reviews.freebsd.org/D42698 (cherry picked from commit c56f45f2a9da7d989b79fd6c34b63100609ff9ae) --- 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 #include -#include +#include #include @@ -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()); }