BITSET_FFS, FLS corrections and extensions

[dougm]

Summary

Correct issues related to BITSET_FFS, BITSET_FLS:

The return value for a bitset of length n should be in the range [0, n], but in the current implementation can be larger than n where n is not a multiple of BITSET_BITS and bits between n and roundup2(n, BITSET_BITS) have been set. Mask out these high-order bits to prevent the error.

The comments and documentation for BITSET_FFS_AT suggest that the 'start' parameter represents a 1-based index into the bit set, but in implementation and in usage, is clearly a 0-based index. Correct those descriptions.

There is a BITEST_FFS_AT, but not a BITSET_FLS_AT. Create one.

bitstring.h has both FFS and FFC methods for finding set bits or clear bits. Add FFC and FLC methods here.

There are no tests in bitset_test for the correctness of BITSET_FFS or BITSET_FLS. Add such tests.

Somewhat unrelatedly, add missing documentation for BIT_ISSET macro.

Test Plan

I've tested the implementations on the tests I've written.

[dougm]

A point of confusion: if 'start' is a one-based index, as the comment claims, then how is
#define BIT_FFS(_s, p) BIT_FFS_AT((_s), (p), 0)
correct? Wouldn't it be:
#define BIT_FFS(_s, p) BIT_FFS_AT((_s), (p), 1)
Really, I suspect the comment is wrong.

[dougm]

Tweak the mask-last-bits test.

[dougm]

Another note of interest:
I find two uses of BIT_FFS_AT in the code:

./sys/arm/mv/mv_ap806_sei.c: vector = BIT_FFS_AT(MV_AP806_SEI_CP_SIZE, &sc->msi_bitmap, 0);
This user thinks the last argument is 0-based. He might as well have not used "_AT" at all.

./sys/vm/vm_dumpset.h: b = BIT_FFS_AT(vm_page_dump_pages, bitset, b))
This user must also think the last argumet is 0-based. Otherwise, he's written an infinite loop.

[dougm]

Fix comments and manpage for 0-based start values. Generalize to BIT_FLS_AT and to FLC versions of everything to find clear bits.

[se]

With regard to the 0-based vs. 1-based argument to FFS: it seems that most of the bitset operations have no tests.
In "tests/sys/sys/bitset_test.c" only BIT_ZERO, BIT_CLR, and BIT_FILL are referenced, but none of the boolean set operations, set counts, or FFS type operations.
This is especially problematic since the CPU_SET macros are based on BIT_SET macros, and they are critical for the correctness and security of kernel functions.

[dougm]

In D33701#762111, @se wrote:

This is especially problematic since the CPU_SET macros are based on BIT_SET macros, and they are critical for the correctness and security of kernel functions.

None of the macros in sys/sys/cpuset.h use BIT_FFS_AT, so they don't have an extra 'start' argument that can be 0-based or 1-based. Everything there looks 0-based to me, except for the value returned by BIT_FFS. I think all the 1-based problems are limited to code comments and documentation.

[dougm]

Add ffs and fls tests to the bitset test set.

Add to the man page a description of BIT_ISSET, since there wasn't one.

Debug BIT_FLS_AT to pass the fls tests.

[dougm]

Fix an error in the test code, checking for ffs legal return values.

[dougm]

Clean up an inadvertent whitespace change in the test code.

[dougm]

Abandoning. I'll limit myself to bitstring.h. There are too many weird decisions baked into bitset.h for me to use it.