Page MenuHomeFreeBSD

bitstring: add functions to find contiguous set/unset bit sequences
ClosedPublic

Authored by jacob.e.keller_intel.com on Sat, Nov 16, 12:41 AM.

Details

Summary

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>

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

We use this implementation in the ice driver (current review at https://reviews.freebsd.org/D21959, will be updated to reflect moving the function here soon).

asomers requested changes to this revision.Mon, Nov 18, 9:39 PM

It should be fine to add new tests cases that depend on a specific nbits. Just add them normally instead of using the BITSTRING_TC_DEFINE macro.

share/man/man3/bitstring.3
61 ↗(On Diff #64416)

You need to bump this date.

245 ↗(On Diff #64416)

in the location

262 ↗(On Diff #64416)

in the location

279 ↗(On Diff #64416)

in the location

300 ↗(On Diff #64416)

in the location

sys/sys/bitstring.h
290 ↗(On Diff #64416)

Why not if ( i >= 0)?

322 ↗(On Diff #64416)

Why not if (i >= 0)?

This revision now requires changes to proceed.Mon, Nov 18, 9:39 PM

Ok, will add tests and fix the comments.

sys/sys/bitstring.h
290 ↗(On Diff #64416)

Sure, makes sense.

Update review based on feedback from Alan Somers

  • Update manual page wording
  • Add additional test cases to cover the new functionality in bit_ffs_area_at and bit_ffc_area_at
  • Use "i >= 0" instead of "!(i < 0)"

Updated the review to include additional test cases and fixed the manual page.

asomers requested changes to this revision.Wed, Nov 20, 2:02 AM
asomers added inline comments.
tests/sys/sys/bitstring_test.c
335 ↗(On Diff #64587)

You can also use ATF_REQUIRE_EQ_MSG here, but it's ok as-is.

375 ↗(On Diff #64587)

To ensure that location is actually updated, you should modify it before line 375 and 384. Also 442 and 450. Or maybe just before every call.

This revision now requires changes to proceed.Wed, Nov 20, 2:02 AM
tests/sys/sys/bitstring_test.c
335 ↗(On Diff #64587)

Going to use ATF_REQUIRE_EQ_MSG since I need to modify this anyways. It should give better expected vs actual output and appears more idiomatic. Granted, this test file itself doesn't use it anywhere else, but I think it should be used by these new tests.

375 ↗(On Diff #64587)

Will modify to reset location before every call to bit_ffs_area* and bit_ffc_area*.

Update test cases per review feedback

asomers accepted this revision.Wed, Nov 20, 11:01 PM
This revision is now accepted and ready to land.Wed, Nov 20, 11:01 PM
erj accepted this revision.Thu, Nov 21, 7:37 PM
This revision was automatically updated to reflect the committed changes.