#
c56f45f2 |
|
22-Nov-2023 |
Dag-Erling Smørgrav <des@FreeBSD.org> |
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
|
#
b3e76948 |
|
16-Aug-2023 |
Warner Losh <imp@FreeBSD.org> |
Remove $FreeBSD$: two-line .h pattern Remove /^\s*\*\n \*\s+\$FreeBSD\$$\n/
|
#
670be460 |
|
20-May-2022 |
Mark Johnston <markj@FreeBSD.org> |
bitstring_test: Add regression tests for bit_ff(c|s)_area_at() Validate the cases where a match can be found immediately and where no match can be found. This extends the existing test cases and is enough to catch the bug fixed in commit 6e7a585348d5 ("bitstring: fix ff_area() when start!=0"). Reviewed by: dougm MFC after: 1 week Sponsored by: The FreeBSD Foundation Differential Revision: https://reviews.freebsd.org/D35259
|
#
84e2ae64 |
|
12-Jan-2022 |
Doug Moore <dougm@FreeBSD.org> |
vm_reserv: use enhanced bitstring for popmaps vm_reserv.c uses its own bitstring implemenation for popmaps. Using the bitstring_t type from a standard header eliminates the code duplication, allows some bit-at-a-time operations to be replaced with more efficient bitstring range operations, and, in vm_reserv_test_contig, allows bit_ffc_area_at to more efficiently search for a big-enough set of consecutive zero-bits. Make bitstring changes improve the vm_reserv code. Define a bit_ntest method to test whether a range of bits is all set, or all clear. Define bit_ff_at and bit_ff_area_at to implement the ffs and ffc versions with a parameter to choose between set- and clear- bits. Improve the area_at implementation. Modify the bit_nset and bit_nclear implementations to allow code optimization in the cases when start or end are multiples of _BITSTR_BITS. Add a few new cases to bitstring_test. Discussed with: alc Reviewed by: markj Tested by: pho (earlier version) Differential Revision: https://reviews.freebsd.org/D33312
|
#
14a4d6d0 |
|
16-Aug-2021 |
Vladimir Kondratyev <wulf@FreeBSD.org> |
bitstring(3): Add bitstring traversal macros. The macro bit_foreach() traverses all set bits in the bitstring in the forward direction, assigning each location in turn to variable. The macro bit_foreach_at() traverses all set bits in the bitstring in the forward direction at or after the zero-based bit index, assigning each location in turn to variable. The bit_foreach_unset() and bit_foreach_unset_at() macros which traverses unset bits are implemented for completeness. Reviewed by: asomers, dougm MFC after: 1 week Differential revision: https://reviews.freebsd.org/D31469
|
#
be252a41 |
|
23-Nov-2019 |
Doug Moore <dougm@FreeBSD.org> |
The error messages that indicate bugs in 'area' bitstring functions should identify accurately which function exhibited the bug. Reviewed by: asomers MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D22519
|
#
70314c42 |
|
22-Nov-2019 |
Li-Wen Hsu <lwhsu@FreeBSD.org> |
Initialize variable bitstr r354991 removed variable-sized object initializing on defining. For the safe reason, manually initialize the members to 0. Sponsored by: The FreeBSD Foundation
|
#
ebb2a18a |
|
22-Nov-2019 |
Li-Wen Hsu <lwhsu@FreeBSD.org> |
Fix GCC build. Sponsored by: The FreeBSD Foundation
|
#
52e8f6a3 |
|
21-Nov-2019 |
Eric Joyner <erj@FreeBSD.org> |
bitstring: add functions to find contiguous set/unset bit sequences Add bit_ffs_area_at and bit_ffc_area_at functions for searching a bit string for a sequence of contiguous set or unset bits of at least the specified size. The bit_ffc_area function will be used by the Intel ice driver for implementing resource assignment logic using a bitstring to represent whether or not a given index has been assigned or is currently free. The bit_ffs_area, bit_ffc_area_at and bit_ffs_area_at functions are implemented for completeness. I'd like to add further test cases for the new functions, but I'm not really sure how to add them easily. The new functions depend on specific sequences of bits being set, while the bitstring tests appear to run for varying bit sizes. Signed-off-by: Jacob Keller <jacob.e.keller@intel.com> Submitted by: Jacob Keller <jacob.e.keller@intel.com> Reviewed by: asomers@, erj@ MFC after: 1 week Sponsored by: Intel Corporation Differential Revision: https://reviews.freebsd.org/D22400
|
#
2d7c3389 |
|
21-Nov-2019 |
Eric Joyner <erj@FreeBSD.org> |
bitstring: exit early if _start is past size of the bitstring bit_ffs_at and bit_ffc_at both take _start parameters which indicate to start searching from _start onwards. If the given _start index is past the size of the bit string, these functions will calculate an address of the current bitstring which is after the expected size. The function will also dereference the memory, resulting in a read buffer overflow. The output of the function remains correct, because the tests ensure to stop the loop if the current bitstring chunk passes the stop bitstring chunk, and because of a check to ensure the reported _value is never past _nbits. However, if <sys/bitstring.h> is ever used in code which is checked by -fsanitize=undefined, or similar static analysis, it can produce warnings about reading past the buffer size. Because of the above mentioned checks, these buffer overflows do not occur as long as _start is less than _nbits. Additionally, by definition bit_ffs_at and bif_ffc_at should set _result to -1 in any case where the _start is after the _nbits. Check for this case at the start of the function and exit early if so, preventing the buffer read overflow, and reducing the amount of computation that occurs. Note that it may seem odd to ever have code that could call bit_ffc_at or bit_ffs_at with a _start value greater than _nbits. However, consider a for-loop that used bit_ffs and bit_ffs_at to loop over a bit string and perform some operation on each bit that was set. If the last bit of the bit string was set, the simplest loop implementation would call bit_ffs_at with a start of _nbits, and expect that to return -1. While it does infact perform correctly, this is what ultimately triggers the unexpected buffer read overflow. Signed-off-by: Jacob Keller <jacob.e.keller@intel.com> Submitted by: Jacob Keller <jacob.e.keller@intel.com> Reviewed by: asomers@, erj@ MFC after: 1 week Sponsored by: Intel Corporation Differential Revision: https://reviews.freebsd.org/D22398
|
#
39ba705b |
|
24-Jun-2016 |
Alan Somers <asomers@FreeBSD.org> |
Fix bitstring allocation on 32-bit platforms sys/sys/bitstring.h Fix a rounding calculation that could undersize a bitstring on 32-bit platforms. tests/sys/sys/bitstring_test.h Add a test for bitstr_size PR: 210260 Reported by: Mark Millard Reviewed by: gibbs Approved by: re (marius) Sponsored by: Spectra Logic Corp Differential Revision: https://reviews.freebsd.org/D6848
|
#
1b82e02f |
|
23-May-2016 |
Alan Somers <asomers@FreeBSD.org> |
Add bit_count to the bitstring(3) api Add a bit_count function, which efficiently counts the number of bits set in a bitstring. sys/sys/bitstring.h tests/sys/sys/bitstring_test.c share/man/man3/bitstring.3 Add bit_alloc sys/kern/subr_unit.c Use bit_count instead of a naive counting loop in check_unrhdr, used when INVARIANTS are enabled. The userland test runs about 6x faster in a generic build, or 8.5x faster when built for Nehalem, which has the POPCNT instruction. sys/sys/param.h Bump __FreeBSD_version due to the addition of bit_alloc UPDATING Add a note about the ABI incompatibility of the bitstring(3) changes, as suggested by lidl. Suggested by: gibbs Reviewed by: gibbs, ngie MFC after: 9 days X-MFC-With: 299090, 300538 Relnotes: yes Sponsored by: Spectra Logic Corp Differential Revision: https://reviews.freebsd.org/D6255
|
#
8907f744 |
|
04-May-2016 |
Alan Somers <asomers@FreeBSD.org> |
Improve performance and functionality of the bitstring(3) api Two new functions are provided, bit_ffs_at() and bit_ffc_at(), which allow for efficient searching of set or cleared bits starting from any bit offset within the bit string. Performance is improved by operating on longs instead of bytes and using ffsl() for searches within a long. ffsl() is a compiler builtin in both clang and gcc for most architectures, converting what was a brute force while loop search into a couple of instructions. All of the bitstring(3) API continues to be contained in the header file. Some of the functions are large enough that perhaps they should be uninlined and moved to a library, but that is beyond the scope of this commit. sys/sys/bitstring.h: Convert the majority of the existing bit string implementation from macros to inline functions. Properly protect the implementation from inadvertant macro expansion when included in a user's program by prefixing all private macros/functions and local variables with '_'. Add bit_ffs_at() and bit_ffc_at(). Implement bit_ffs() and bit_ffc() in terms of their "at" counterparts. Provide a kernel implementation of bit_alloc(), making the full API usable in the kernel. Improve code documenation. share/man/man3/bitstring.3: Add pre-exisiting API bit_ffc() to the synopsis. Document new APIs. Document the initialization state of the bit strings allocated/declared by bit_alloc() and bit_decl(). Correct documentation for bitstr_size(). The original code comments indicate the size is in bytes, not "elements of bitstr_t". The new implementation follows this lead. Only hastd assumed "elements" rather than bytes and it has been corrected. etc/mtree/BSD.tests.dist: tests/sys/Makefile: tests/sys/sys/Makefile: tests/sys/sys/bitstring.c: Add tests for all existing and new functionality. include/bitstring.h Include all headers needed by sys/bitstring.h lib/libbluetooth/bluetooth.h: usr.sbin/bluetooth/hccontrol/le.c: Include bitstring.h instead of sys/bitstring.h. sbin/hastd/activemap.c: Correct usage of bitstr_size(). sys/dev/xen/blkback/blkback.c Use new bit_alloc. sys/kern/subr_unit.c: Remove hard-coded assumption that sizeof(bitstr_t) is 1. Get rid of unrb.busy, which caches the number of bits set in unrb.map. When INVARIANTS are disabled, nothing needs to know that information. callapse_unr can be adapted to use bit_ffs and bit_ffc instead. Eliminating unrb.busy saves memory, simplifies the code, and provides a slight speedup when INVARIANTS are disabled. sys/net/flowtable.c: Use the new kernel implementation of bit-alloc, instead of hacking the old libc-dependent macro. sys/sys/param.h Update __FreeBSD_version to indicate availability of new API Submitted by: gibbs, asomers Reviewed by: gibbs, ngie MFC after: 4 weeks Sponsored by: Spectra Logic Corp Differential Revision: https://reviews.freebsd.org/D6004
|