man/man3: add cross references to stdbit(3)

Add cross references to relevant stdbit man pages

Approved by: markj (mentor)
MFC after: 1 month
Differential Revision: https://reviews.freebsd.org/D53661

manuals: Remove trailing spaces

This does not change the rendered ascii at all.

Signed-off-by: Graham Percival <gperciva@tarsnap.com>
Reviewed by: mhorne, Alexander Ziaee <concussious.bugzilla@runb

manuals: Remove trailing spaces

This does not change the rendered ascii at all.

Signed-off-by: Graham Percival <gperciva@tarsnap.com>
Reviewed by: mhorne, Alexander Ziaee <concussious.bugzilla@runbox.com>
MFC after: 3 days
Sponsored by: Tarsnap Backup Inc.
Pull Request: https://github.com/freebsd/freebsd-src/pull/1473

show more ...

share: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl

share: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl script.

Sponsored by: Netflix

show more ...

bitstring: Support large bit strings.

Replace int with either size_t or ssize_t (depending on context) in
order to support bit strings up to SSIZE_MAX bits in length. Since
some of the arguments th

bitstring: Support large bit strings.

Replace int with either size_t or ssize_t (depending on context) in
order to support bit strings up to SSIZE_MAX bits in length. Since
some of the arguments that need to change type are pointers, we must
resort to light preprocessor trickery to avoid breaking existing code.

MFC after: 3 weeks
Sponsored by: Klara, Inc.
Reviewed by: kevans
Differential Revision: https://reviews.freebsd.org/D42698

show more ...

Remove $FreeBSD$: one-line nroff pattern

Remove /^\.\\"\s*\$FreeBSD\$$\n/

vm_reserv: use enhanced bitstring for popmaps

vm_reserv.c uses its own bitstring implemenation for popmaps. Using
the bitstring_t type from a standard header eliminates the code
duplication, allows

vm_reserv: use enhanced bitstring for popmaps

vm_reserv.c uses its own bitstring implemenation for popmaps. Using
the bitstring_t type from a standard header eliminates the code
duplication, allows some bit-at-a-time operations to be replaced with
more efficient bitstring range operations, and, in
vm_reserv_test_contig, allows bit_ffc_area_at to more efficiently
search for a big-enough set of consecutive zero-bits.

Make bitstring changes improve the vm_reserv code. Define a bit_ntest
method to test whether a range of bits is all set, or all clear.
Define bit_ff_at and bit_ff_area_at to implement the ffs and ffc
versions with a parameter to choose between set- and clear- bits.
Improve the area_at implementation. Modify the bit_nset and
bit_nclear implementations to allow code optimization in the cases
when start or end are multiples of _BITSTR_BITS.

Add a few new cases to bitstring_test.

Discussed with: alc
Reviewed by: markj
Tested by: pho (earlier version)
Differential Revision: https://reviews.freebsd.org/D33312

show more ...

bitstring(3): Add bitstring traversal macros.

The macro bit_foreach() traverses all set bits in the bitstring in the
forward direction, assigning each location in turn to variable.

The macro bit_fo

bitstring(3): Add bitstring traversal macros.

The macro bit_foreach() traverses all set bits in the bitstring in the
forward direction, assigning each location in turn to variable.

The macro bit_foreach_at() traverses all set bits in the bitstring in
the forward direction at or after the zero-based bit index, assigning
each location in turn to variable.

The bit_foreach_unset() and bit_foreach_unset_at() macros which
traverses unset bits are implemented for completeness.

Reviewed by: asomers, dougm
MFC after: 1 week
Differential revision: https://reviews.freebsd.org/D31469

show more ...

Fix various, mostly minor errors in man pages like:
- Abbreviated month name in .Dd
- position of HISTORY section
- alphabetical ordering within SEE ALSO section
- adding .Ed before .Sh DESCRIPTION
-

Fix various, mostly minor errors in man pages like:
- Abbreviated month name in .Dd
- position of HISTORY section
- alphabetical ordering within SEE ALSO section
- adding .Ed before .Sh DESCRIPTION
- remove trailing whitespaces
- Line break after a sentence stop
- Use BSD OS macros instead of hardcoded strings

No .Dd bumps as there was no actual content change made
in any of these pages.

Submitted by: Gordon Bergling gbergling_gmail.com
Approved by: bcr
Differential Revision: https://reviews.freebsd.org/D24591

show more ...

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

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

show more ...

man/man3: add cross references to stdbit(3)

Add cross references to relevant stdbit man pages

Approved by: markj (mentor)
MFC after: 1 month
Differential Revision: https://reviews.freebsd.org/D53661

manuals: Remove trailing spaces

This does not change the rendered ascii at all.

Signed-off-by: Graham Percival <gperciva@tarsnap.com>
Reviewed by: mhorne, Alexander Ziaee <concussious.bugzilla@runb

manuals: Remove trailing spaces

This does not change the rendered ascii at all.

Signed-off-by: Graham Percival <gperciva@tarsnap.com>
Reviewed by: mhorne, Alexander Ziaee <concussious.bugzilla@runbox.com>
MFC after: 3 days
Sponsored by: Tarsnap Backup Inc.
Pull Request: https://github.com/freebsd/freebsd-src/pull/1473

show more ...

share: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl

share: Remove ancient SCCS tags.

Remove ancient SCCS tags from the tree, automated scripting, with two
minor fixup to keep things compiling. All the common forms in the tree
were removed with a perl script.

Sponsored by: Netflix

show more ...

bitstring: Support large bit strings.

Replace int with either size_t or ssize_t (depending on context) in
order to support bit strings up to SSIZE_MAX bits in length. Since
some of the arguments th

bitstring: Support large bit strings.

Replace int with either size_t or ssize_t (depending on context) in
order to support bit strings up to SSIZE_MAX bits in length. Since
some of the arguments that need to change type are pointers, we must
resort to light preprocessor trickery to avoid breaking existing code.

MFC after: 3 weeks
Sponsored by: Klara, Inc.
Reviewed by: kevans
Differential Revision: https://reviews.freebsd.org/D42698

show more ...

Remove $FreeBSD$: one-line nroff pattern

Remove /^\.\\"\s*\$FreeBSD\$$\n/

vm_reserv: use enhanced bitstring for popmaps

vm_reserv.c uses its own bitstring implemenation for popmaps. Using
the bitstring_t type from a standard header eliminates the code
duplication, allows

vm_reserv: use enhanced bitstring for popmaps

vm_reserv.c uses its own bitstring implemenation for popmaps. Using
the bitstring_t type from a standard header eliminates the code
duplication, allows some bit-at-a-time operations to be replaced with
more efficient bitstring range operations, and, in
vm_reserv_test_contig, allows bit_ffc_area_at to more efficiently
search for a big-enough set of consecutive zero-bits.

Make bitstring changes improve the vm_reserv code. Define a bit_ntest
method to test whether a range of bits is all set, or all clear.
Define bit_ff_at and bit_ff_area_at to implement the ffs and ffc
versions with a parameter to choose between set- and clear- bits.
Improve the area_at implementation. Modify the bit_nset and
bit_nclear implementations to allow code optimization in the cases
when start or end are multiples of _BITSTR_BITS.

Add a few new cases to bitstring_test.

Discussed with: alc
Reviewed by: markj
Tested by: pho (earlier version)
Differential Revision: https://reviews.freebsd.org/D33312

show more ...

bitstring(3): Add bitstring traversal macros.

The macro bit_foreach() traverses all set bits in the bitstring in the
forward direction, assigning each location in turn to variable.

The macro bit_fo

bitstring(3): Add bitstring traversal macros.

The macro bit_foreach() traverses all set bits in the bitstring in the
forward direction, assigning each location in turn to variable.

The macro bit_foreach_at() traverses all set bits in the bitstring in
the forward direction at or after the zero-based bit index, assigning
each location in turn to variable.

The bit_foreach_unset() and bit_foreach_unset_at() macros which
traverses unset bits are implemented for completeness.

Reviewed by: asomers, dougm
MFC after: 1 week
Differential revision: https://reviews.freebsd.org/D31469

show more ...

Fix various, mostly minor errors in man pages like:
- Abbreviated month name in .Dd
- position of HISTORY section
- alphabetical ordering within SEE ALSO section
- adding .Ed before .Sh DESCRIPTION
-

Fix various, mostly minor errors in man pages like:
- Abbreviated month name in .Dd
- position of HISTORY section
- alphabetical ordering within SEE ALSO section
- adding .Ed before .Sh DESCRIPTION
- remove trailing whitespaces
- Line break after a sentence stop
- Use BSD OS macros instead of hardcoded strings

No .Dd bumps as there was no actual content change made
in any of these pages.

Submitted by: Gordon Bergling gbergling_gmail.com
Approved by: bcr
Differential Revision: https://reviews.freebsd.org/D24591

show more ...

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

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

show more ...

Add bit_count to the bitstring(3) api

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/bit

Add bit_count to the bitstring(3) api

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

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, as suggested by lidl.

Suggested by: gibbs
Reviewed by: gibbs, ngie
MFC after: 9 days
X-MFC-With: 299090, 300538
Relnotes: yes
Sponsored by: Spectra Logic Corp
Differential Revision: https://reviews.freebsd.org/D6255

show more ...

Improve performance and functionality of the bitstring(3) api

Two new functions are provided, bit_ffs_at() and bit_ffc_at(), which allow
for efficient searching of set or cleared bits starting from

Improve performance and functionality of the bitstring(3) api

Two new functions are provided, bit_ffs_at() and bit_ffc_at(), which allow
for efficient searching of set or cleared bits starting from any bit offset
within the bit string.

Performance is improved by operating on longs instead of bytes and using
ffsl() for searches within a long. ffsl() is a compiler builtin in both
clang and gcc for most architectures, converting what was a brute force
while loop search into a couple of instructions.

All of the bitstring(3) API continues to be contained in the header file.
Some of the functions are large enough that perhaps they should be uninlined
and moved to a library, but that is beyond the scope of this commit.

sys/sys/bitstring.h:
Convert the majority of the existing bit string implementation from
macros to inline functions.

Properly protect the implementation from inadvertant macro expansion
when included in a user's program by prefixing all private
macros/functions and local variables with '_'.

Add bit_ffs_at() and bit_ffc_at(). Implement bit_ffs() and
bit_ffc() in terms of their "at" counterparts.

Provide a kernel implementation of bit_alloc(), making the full API
usable in the kernel.

Improve code documenation.

share/man/man3/bitstring.3:
Add pre-exisiting API bit_ffc() to the synopsis.

Document new APIs.

Document the initialization state of the bit strings
allocated/declared by bit_alloc() and bit_decl().

Correct documentation for bitstr_size(). The original code comments
indicate the size is in bytes, not "elements of bitstr_t". The new
implementation follows this lead. Only hastd assumed "elements"
rather than bytes and it has been corrected.

etc/mtree/BSD.tests.dist:
tests/sys/Makefile:
tests/sys/sys/Makefile:
tests/sys/sys/bitstring.c:
Add tests for all existing and new functionality.

include/bitstring.h
Include all headers needed by sys/bitstring.h

lib/libbluetooth/bluetooth.h:
usr.sbin/bluetooth/hccontrol/le.c:
Include bitstring.h instead of sys/bitstring.h.

sbin/hastd/activemap.c:
Correct usage of bitstr_size().

sys/dev/xen/blkback/blkback.c
Use new bit_alloc.

sys/kern/subr_unit.c:
Remove hard-coded assumption that sizeof(bitstr_t) is 1. Get rid of
unrb.busy, which caches the number of bits set in unrb.map. When
INVARIANTS are disabled, nothing needs to know that information.
callapse_unr can be adapted to use bit_ffs and bit_ffc instead.
Eliminating unrb.busy saves memory, simplifies the code, and
provides a slight speedup when INVARIANTS are disabled.

sys/net/flowtable.c:
Use the new kernel implementation of bit-alloc, instead of hacking
the old libc-dependent macro.

sys/sys/param.h
Update __FreeBSD_version to indicate availability of new API

Submitted by: gibbs, asomers
Reviewed by: gibbs, ngie
MFC after: 4 weeks
Sponsored by: Spectra Logic Corp
Differential Revision: https://reviews.freebsd.org/D6004

show more ...

MFH r289384-r293170

Sponsored by: The FreeBSD Foundation

Catch up with head (r291075).

Merge from head

Sponsored by: Gandi.net

Merge from head

Document bitset(9)