Page MenuHomeFreeBSD

Add bit_count to the bitstring(3) api
ClosedPublic

Authored by asomers on May 6 2016, 9:55 PM.
Tags
None
Referenced Files
Unknown Object (File)
Sun, Feb 25, 12:44 AM
Unknown Object (File)
Thu, Feb 22, 9:53 PM
Unknown Object (File)
Sat, Feb 3, 8:24 AM
Unknown Object (File)
Sat, Feb 3, 7:21 AM
Unknown Object (File)
Wed, Jan 31, 10:08 PM
Unknown Object (File)
Jan 8 2024, 6:14 PM
Unknown Object (File)
Dec 20 2023, 1:45 AM
Unknown Object (File)
Dec 12 2023, 11:09 PM
Subscribers

Details

Summary

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. The
userland test runs about 6x faster in a generic build, or 8.5x faster
when built for Nehalem, which has the POPCNT instruction.

tests/sys/kern/Makefile
Remove a CFLAG that's been unnecessary since 299090.

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

Test Plan

Added ATF test

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

asomers retitled this revision from to Add bit_count to the bitstring(3) api.
asomers updated this object.
asomers edited the test plan for this revision. (Show Details)
asomers added reviewers: gibbs, ngie, lidl.
UPDATING
36–38 ↗(On Diff #16002)

Shouldn't the SHLIB version be bumped?

sys/sys/bitstring.h
68 ↗(On Diff #16002)
  • shouldn't sys/types.h be first?
  • why is this header pollution required here, instead of in the consumers?
tests/sys/kern/Makefile
29–30 ↗(On Diff #16002)

Please commit this separately.

tests/sys/sys/bitstring_test.c
371–376 ↗(On Diff #16002)

Would it be a good idea to take thing, flip the first bit, then try that?

Also, what about negative tests, like 0 length buffers, etc?

asomers added inline comments.
UPDATING
36–38 ↗(On Diff #16002)

No, because there is no shared library. bitstring is implemented entirely within the header.

sys/sys/bitstring.h
68 ↗(On Diff #16002)

sys/types.h defines __bitcountl, so it needs to be included here. style(9) doesn't specify any particular order for the sys/ includes, but the /usr/include files must be alphabetical. So I ordered the sys/ includes alphabetically too. Would you rather I put sys/types.h first? I see some kernel files that do it that way, and some that do it as I did.

tests/sys/kern/Makefile
29–30 ↗(On Diff #16002)

Ok.

tests/sys/sys/bitstring_test.c
371–376 ↗(On Diff #16002)

If you look at the expansion of BITSTRING_TC_DEFINE, you'll see that it already does a 0-length test. I don't understand what you mean about "take the thing, flip the first bit, then try that?" Could you please explain?

In the description for this change, under the subr_unit.c heading, I think you mean bit_count, not bit_alloc.

As defined, bit_count allows you to count a subset of the full map by specifying a shorter length. I think it would be useful to allow a starting bit index to be specified so that you can count an arbitrary region of the bitmap.

asomers edited edge metadata.
asomers marked an inline comment as done.

Add a start parameter to bit_count as requested by @gibbs, and fix some bugs in the man page.

sys/sys/bitstring.h
270–274 ↗(On Diff #16419)

For a large bitmap, isn't it faster to special case a non-zero _start and in that case directly compute the partial leading bit count and advance _curbitstr to the first full bitstr_t that needs to be processed by the loop? The same may be true for performing the computation on the final bitstr_t if _nbits is not a multiple of _BITSTR_BITS (no computation of curbitstr_len in the loop).

asomers edited edge metadata.

Optimize bit_count as suggested by @gibbs

gibbs edited edge metadata.
This revision is now accepted and ready to land.May 23 2016, 7:08 PM
This revision was automatically updated to reflect the committed changes.