rangeset: speed up range traversal

For rangeset-next search, use exact search rather than greater-than search.

Move a bit of the testing logic from the pmap code to the common rangeset code.

Revie

rangeset: speed up range traversal

For rangeset-next search, use exact search rather than greater-than search.

Move a bit of the testing logic from the pmap code to the common rangeset code.

Reviewed by: kib (previous version)
Tested by: pho (previous version)
Differential Revision: https://reviews.freebsd.org/D46314

show more ...

pctrie: avoid typecast

Have PCTRIE_RECLAIM_CALLBACK typecast one function pointer type to
another, to relieve the writer of the call back function from having
to cast its first argument from void* t

pctrie: avoid typecast

Have PCTRIE_RECLAIM_CALLBACK typecast one function pointer type to
another, to relieve the writer of the call back function from having
to cast its first argument from void* to member type.

Reviewed by: rlibby
Differential Revision: https://reviews.freebsd.org/D45586

show more ...

subr_rangeset: use pctrie_reclaim_cb in remove_all

Replace the lookup-remove loop in rangeet_remove_all with a call
to SWAP_PCTRIE_RECLAIM_CALLBACK, to eliminate repeated trie searches.

Reviewed by

subr_rangeset: use pctrie_reclaim_cb in remove_all

Replace the lookup-remove loop in rangeet_remove_all with a call
to SWAP_PCTRIE_RECLAIM_CALLBACK, to eliminate repeated trie searches.

Reviewed by: rlibby
Differential Revision: https://reviews.freebsd.org/D45584

show more ...

rangeset: add next() iteration

Add a method rangeset_next to find the first range that starts at or
after a given value. Use it to rewrite pmap_pkru_same and
pmap_bti_same to avoid walking a page at

rangeset: add next() iteration

Add a method rangeset_next to find the first range that starts at or
after a given value. Use it to rewrite pmap_pkru_same and
pmap_bti_same to avoid walking a page at a time over pages in no
range.

Reviewed by: andrew, kib
Differential Revision: https://reviews.freebsd.org/D45511

show more ...

sys: Automated cleanup of cdefs and other formatting

Apply the following automated changes to try to eliminate
no-longer-needed sys/cdefs.h includes as well as now-empty
blank lines in a row.

Remov

sys: Automated cleanup of cdefs and other formatting

Apply the following automated changes to try to eliminate
no-longer-needed sys/cdefs.h includes as well as now-empty
blank lines in a row.

Remove /^#if.*\n#endif.*\n#include\s+<sys/cdefs.h>.*\n/
Remove /\n+#include\s+<sys/cdefs.h>.*\n+#if.*\n#endif.*\n+/
Remove /\n+#if.*\n#endif.*\n+/
Remove /^#if.*\n#endif.*\n/
Remove /\n+#include\s+<sys/cdefs.h>\n#include\s+<sys/types.h>/
Remove /\n+#include\s+<sys/cdefs.h>\n#include\s+<sys/param.h>/
Remove /\n+#include\s+<sys/cdefs.h>\n#include\s+<sys/capsicum.h>/

Sponsored by: Netflix

show more ...

sys: Remove $FreeBSD$: one-line .c pattern

Remove /^[\s*]*__FBSDID\("\$FreeBSD\$"\);?\s*\n/

rangesets: use PCTRIE_DEFINE

subr_rangeset.c is the only source file that calls functions like
pctrie_insert and pctrie_remove directly; other users of pctries use
the PCTRIE_DEFINE macro to define

rangesets: use PCTRIE_DEFINE

subr_rangeset.c is the only source file that calls functions like
pctrie_insert and pctrie_remove directly; other users of pctries use
the PCTRIE_DEFINE macro to define interfaces to pctrie that let them
ignore issues of offsets within structs and uint64_t return values.

Change subr_rangeset.c to use PCTRIE_DEFINE too. And change pctrie.h
to mark the lookup function as unused, to avoid warnings when
compiling files, like subr_rangeset.c, that don't invoke lookup().

Reviewed by: kib
Differential Revision: https://reviews.freebsd.org/D41391

show more ...

spdx: The BSD-2-Clause-FreeBSD identifier is obsolete, drop -FreeBSD

The SPDX folks have obsoleted the BSD-2-Clause-FreeBSD identifier. Catch
up to that fact and revert to their recommended match of

spdx: The BSD-2-Clause-FreeBSD identifier is obsolete, drop -FreeBSD

The SPDX folks have obsoleted the BSD-2-Clause-FreeBSD identifier. Catch
up to that fact and revert to their recommended match of BSD-2-Clause.

Discussed with: pfg
MFC After: 3 days
Sponsored by: Netflix

show more ...

Remove "All Rights Reserved" from FreeBSD Foundation sys/ copyrights

These ones were unambiguous cases where the Foundation was the only
listed copyright holder (in the associated license block).

S

Remove "All Rights Reserved" from FreeBSD Foundation sys/ copyrights

These ones were unambiguous cases where the Foundation was the only
listed copyright holder (in the associated license block).

Sponsored by: The FreeBSD Foundation

show more ...

MFhead@r344527

Merge ^/head r344178 through r344512.

Implement rangesets.

The data structure implements non-intersecting intervals over the [0,
UINT64_MAX] range, and supports fast insert, predicated clearing of
subrange, and lookup of an interval con

Implement rangesets.

The data structure implements non-intersecting intervals over the [0,
UINT64_MAX] range, and supports fast insert, predicated clearing of
subrange, and lookup of an interval containing the specified address.
Internally it is a pctrie over the interval start addresses.

Implementation provides additional guarantees over the structure state
in case of memory allocation failures.

Reviewed by: markj
Tested by: pho
Sponsored by: The FreeBSD Foundation
MFC after: 2 weeks
Differential revision: https://reviews.freebsd.org/D18893

show more ...