Page MenuHomeFreeBSD
Files F133322166

D42698.diff
No OneTemporary
Actions

D42698.diff
View Options

diff --git a/share/man/man3/bitstring.3 b/share/man/man3/bitstring.3
--- 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
--- a/sys/sys/bitstring.h
+++ b/sys/sys/bitstring.h
@@ -75,35 +75,33 @@
#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 @@
/*----------------------------- 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 @@
/* 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 @@
/* 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 @@
/* 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 @@
}
/* 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 @@
_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 @@
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 @@
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 @@
_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
--- 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 @@
bitstr_t *bitstr = bit_alloc(nbits);
test(bitstr, nbits, "heap");
+ free(bitstr);
}
static void
@@ -862,6 +864,91 @@
}
}
+/*
+ * 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 @@
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());
}

File Metadata

Mime Type
text/plain
Expires
Sat, Oct 25, 10:24 PM (6 h, 32 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
24191771
Default Alt Text
D42698.diff (17 KB)

Event Timeline