Date: Thu, 21 Nov 2019 19:57:56 +0000 (UTC) From: Eric Joyner <erj@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r354977 - in head: share/man/man3 sys/sys tests/sys/sys Message-ID: <201911211957.xALJvuwi054399@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: erj Date: Thu Nov 21 19:57:56 2019 New Revision: 354977 URL: https://svnweb.freebsd.org/changeset/base/354977 Log: 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 Modified: head/share/man/man3/bitstring.3 head/sys/sys/bitstring.h head/sys/sys/param.h head/tests/sys/sys/bitstring_test.c Modified: head/share/man/man3/bitstring.3 ============================================================================== --- head/share/man/man3/bitstring.3 Thu Nov 21 19:54:10 2019 (r354976) +++ head/share/man/man3/bitstring.3 Thu Nov 21 19:57:56 2019 (r354977) @@ -58,7 +58,7 @@ .\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93 .\" $FreeBSD$ .\" -.Dd May 23, 2016 +.Dd Nov 18, 2019 .Dt BITSTRING 3 .Os .Sh NAME @@ -70,6 +70,10 @@ .Nm bit_ffs , .Nm bit_ffc_at , .Nm bit_ffs_at , +.Nm bit_ffc_area , +.Nm bit_ffs_area , +.Nm bit_ffc_area_at , +.Nm bit_ffs_area_at , .Nm bit_nclear , .Nm bit_nset , .Nm bit_set , @@ -95,6 +99,14 @@ .Ft void .Fn bit_ffs_at "bitstr_t *name" "int start" "int nbits" "int *value" .Ft void +.Fn bit_ffc_area "bitstr_t *name" "int nbits" "int size" "int *value" +.Ft void +.Fn bit_ffs_area "bitstr_t *name" "int nbits" "int size" "int *value" +.Ft void +.Fn bit_ffc_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value" +.Ft void +.Fn bit_ffs_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value" +.Ft void .Fn bit_nclear "bitstr_t *name" "int start" "int stop" .Ft void .Fn bit_nset "bitstr_t *name" "int start" "int stop" @@ -223,6 +235,82 @@ bits referenced by at or after the zero-based bit index .Fa start . If no bits are set after +.Fa start , +the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffc_area +function stores in the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of unset bits of +at least +.Fa size +unset bits in the array of +.Fa nbits +bits referenced by +.Fa name . +If no sequence of contiguous unset bits of the specified +.Fa size +can be found, the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffs_area +function stores in the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of set bits of +at least +.Fa size +set bits in the array of +.Fa nbits +bits referenced by +.Fa name . +If no sequence of contiguous set bits of the specified +.Fa size +can be found, the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffc_area_at +function stores in the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of unset bits of +at least +.Fa size +unset bits in the array of +.Fa nbits +bits referenced by +.Fa name , +at or after the zero-based bit index +.Fa start . +If no sequence of contiguous unset bits of the specified +.Fa size +can be found at or after +.Fa start , +the location referenced by +.Fa value +is set to \-1. +.Pp +The +.Fn bit_ffs_area_at +function stores in the location referenced by +.Fa value +the zero-based number of the first bit beginning a sequence of set bits of +at least +.Fa size +set bits in the array of +.Fa nbits +bits referenced by +.Fa name , +at or after the zero-based bit index +.Fa start . +If no sequence of contiguous set bits of the specified +.Fa size +can be found at or after .Fa start , the location referenced by .Fa value Modified: head/sys/sys/bitstring.h ============================================================================== --- head/sys/sys/bitstring.h Thu Nov 21 19:54:10 2019 (r354976) +++ head/sys/sys/bitstring.h Thu Nov 21 19:57:56 2019 (r354977) @@ -275,6 +275,84 @@ bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); } +/* 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) +{ + int _index, _end, _i; +again: + /* Find the first set bit */ + bit_ffs_at(_bitstr, _start, _nbits, &_index); + if (_index < 0) { + *_result = -1; + return; + } + + /* Make sure there is enough room left in the bitstr */ + _end = _index + _size; + if (_end > _nbits) { + *_result = -1; + return; + } + + /* Find the next cleared bit starting at _index, stopping at _end */ + bit_ffc_at(_bitstr, _index, _end, &_i); + if (_i >= 0) { + /* we found a clear bit between _index and _end, so skip ahead + * to the next bit and try again + */ + _start = _i + 1; + goto again; + } + *_result = _index; +} + +/* 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) +{ + int _index, _end, _i; +again: + /* Find the first zero bit */ + bit_ffc_at(_bitstr, _start, _nbits, &_index); + if (_index < 0) { + *_result = -1; + return; + } + + /* Make sure there is enough room left in the bitstr */ + _end = _index + _size; + if (_end > _nbits) { + *_result = -1; + return; + } + + /* Find the next set bit starting at _index, stopping at _end */ + bit_ffs_at(_bitstr, _index, _end, &_i); + if (_i >= 0) { + /* we found a set bit between _index and _end, so skip ahead + * to the next bit and try again + */ + _start = _i + 1; + goto again; + } + *_result = _index; +} + +/* 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); +} + +/* 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); +} + /* 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) Modified: head/sys/sys/param.h ============================================================================== --- head/sys/sys/param.h Thu Nov 21 19:54:10 2019 (r354976) +++ head/sys/sys/param.h Thu Nov 21 19:57:56 2019 (r354977) @@ -60,7 +60,7 @@ * in the range 5 to 9. */ #undef __FreeBSD_version -#define __FreeBSD_version 1300060 /* Master, propagated to newvers */ +#define __FreeBSD_version 1300061 /* Master, propagated to newvers */ /* * __FreeBSD_kernel__ indicates that this system uses the kernel of FreeBSD, Modified: head/tests/sys/sys/bitstring_test.c ============================================================================== --- head/tests/sys/sys/bitstring_test.c Thu Nov 21 19:54:10 2019 (r354976) +++ head/tests/sys/sys/bitstring_test.c Thu Nov 21 19:57:56 2019 (r354977) @@ -321,6 +321,169 @@ BITSTRING_TC_DEFINE(bit_ffc_at) nbits, memloc, nbits + 3, found_clear_bit); } +BITSTRING_TC_DEFINE(bit_ffc_area_no_match) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int found_clear_bits; + + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_ffc_area(bitstr, nbits, 2, &found_clear_bits); + ATF_REQUIRE_EQ_MSG(-1, found_clear_bits, + "bit_ffc_area_%d_%s: Failed all set bits.", nbits, memloc); +} + +BITSTRING_TC_DEFINE(bit_ffs_area_no_match) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int found_clear_bits; + + memset(bitstr, 0, bitstr_size(nbits)); + bit_ffs_area(bitstr, nbits, 2, &found_clear_bits); + ATF_REQUIRE_EQ_MSG(-1, found_clear_bits, + "bit_ffc_area_%d_%s: Failed all clear bits.", nbits, memloc); +} + +ATF_TC_WITHOUT_HEAD(bit_ffs_area); +ATF_TC_BODY(bit_ffs_area, tc) +{ + const int nbits = 72; + bitstr_t bit_decl(bitstr, nbits) = {}; + int location; + + bit_set(bitstr, 5); + bit_set(bitstr, 6); + + location = 0; + bit_ffs_area(bitstr, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found location of size 3 when only 2 bits are set"); + + bit_set(bitstr, 7); + + location = 0; + bit_ffs_area(bitstr, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(5, location, + "bit_ffc_area: failed to find location of size 3"); + + bit_set(bitstr, 8); + + location = 0; + bit_ffs_area(bitstr, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(5, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffs_area_at(bitstr, 2, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(5, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffs_area_at(bitstr, 6, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(6, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffs_area_at(bitstr, 8, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found invalid location"); + + bit_set(bitstr, 69); + bit_set(bitstr, 70); + bit_set(bitstr, 71); + + location = 0; + bit_ffs_area_at(bitstr, 8, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(69, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffs_area_at(bitstr, 69, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(69, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffs_area_at(bitstr, 70, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found invalid location"); + + location = 0; + bit_ffs_area_at(bitstr, 72, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found invalid location"); +} + +ATF_TC_WITHOUT_HEAD(bit_ffc_area); +ATF_TC_BODY(bit_ffc_area, tc) +{ + const int nbits = 80; + bitstr_t bit_decl(bitstr, nbits) = {}; + int location; + + /* set all bits */ + memset(bitstr, 0xFF, bitstr_size(nbits)); + + bit_clear(bitstr, 7); + bit_clear(bitstr, 8); + + location = 0; + bit_ffc_area(bitstr, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found location of size 3 when only 2 bits are set"); + + bit_clear(bitstr, 9); + + location = 0; + bit_ffc_area(bitstr, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(7, location, + "bit_ffc_area: failed to find location of size 3"); + + bit_clear(bitstr, 10); + + location = 0; + bit_ffc_area(bitstr, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(7, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffc_area_at(bitstr, 2, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(7, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffc_area_at(bitstr, 8, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(8, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffc_area_at(bitstr, 9, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found invalid bit location"); + + bit_clear(bitstr, 77); + bit_clear(bitstr, 78); + bit_clear(bitstr, 79); + + location = 0; + bit_ffc_area_at(bitstr, 12, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(77, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffc_area_at(bitstr, 77, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(77, location, + "bit_ffc_area: failed to find location of size 3"); + + location = 0; + bit_ffc_area_at(bitstr, 78, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found invalid location"); + + location = 0; + bit_ffc_area_at(bitstr, 85, nbits, 3, &location); + ATF_REQUIRE_EQ_MSG(-1, location, + "bit_ffc_area: found invalid location"); +} + BITSTRING_TC_DEFINE(bit_nclear) /* bitstr_t *bitstr, int nbits, const char *memloc */ { @@ -441,6 +604,8 @@ ATF_TP_ADD_TCS(tp) ATF_TP_ADD_TC(tp, bitstr_in_struct); ATF_TP_ADD_TC(tp, bitstr_size); + ATF_TP_ADD_TC(tp, bit_ffc_area); + ATF_TP_ADD_TC(tp, bit_ffs_area); BITSTRING_TC_ADD(tp, bit_set); BITSTRING_TC_ADD(tp, bit_clear); BITSTRING_TC_ADD(tp, bit_ffs); @@ -450,6 +615,8 @@ ATF_TP_ADD_TCS(tp) BITSTRING_TC_ADD(tp, bit_nclear); BITSTRING_TC_ADD(tp, bit_nset); BITSTRING_TC_ADD(tp, bit_count); + BITSTRING_TC_ADD(tp, bit_ffs_area_no_match); + BITSTRING_TC_ADD(tp, bit_ffc_area_no_match); return (atf_no_error()); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201911211957.xALJvuwi054399>