Add bit_count to the bitstring(3) api
ClosedPublic
Actions

Authored by asomers on May 6 2016, 9:55 PM.

Details

Reviewers

ngie
gibbs
• lidl

Group Reviewers

manpages

Commits

rS300539: Add bit_count to the bitstring(3) api

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 updated this revision to Diff 16002.May 6 2016, 9:55 PM

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.

Herald added a reviewer: manpages. · View Herald TranscriptMay 6 2016, 9:55 PM

Herald added a subscriber: imp. · View Herald Transcript

ngie added inline comments.May 7 2016, 1:21 AM

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 marked an inline comment as done.May 7 2016, 2:31 AM

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 updated this object.May 9 2016, 7:55 PM

asomers edited edge metadata.

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

Herald edited edge metadata. · View Herald TranscriptMay 16 2016, 11:26 PM

gibbs added inline comments.May 17 2016, 8:31 AM

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).