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

Remove /^/[*/]\s*\$FreeBSD\$.*\n/

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

tree.h: Fix SP/TAB white-space issues, add () for clarity.

Fix LINT build after 368ee2f86a0f4f6
Reported by: jenkins
Fixes: 368ee2f86a0f4f6

rb_tree: let insert search start from next node

When the node to insert in the rb_tree is known to precede or follow a
particular node, new methods RB_INSERT_PREV and RB_INSERT_NEXT,
defined here, a

rb_tree: let insert search start from next node

When the node to insert in the rb_tree is known to precede or follow a
particular node, new methods RB_INSERT_PREV and RB_INSERT_NEXT,
defined here, allow the search for where to insert the new node begin
with that particular node, rather than at the root, to save a bit of
time.

Using those methods, instead of RB_INSERT, in managing a tree in
iommu_gas.c, saves a little time.

Reviewed by: kib
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D35516

show more ...

rb_tree: Use void casts for RB_AUGMENT_CHECK with unused return value.

Reviewed by: dougm
Reported by: GCC -Wunused-value
Differential Revision: https://reviews.freebsd.org/D36778

rb_tree: add augmentation comments

Add comments to better explain why augmentation is done in several places.
Reviewed by: alc
MFC after: 2 weeks
Differential Revision: https://reviews.freebsd.org/D

rb_tree: add augmentation comments

Add comments to better explain why augmentation is done in several places.
Reviewed by: alc
MFC after: 2 weeks
Differential Revision: https://reviews.freebsd.org/D36646

show more ...

Use 0 and 1, not false and true, in tree.h changes.
Reported by: jenkins

rb_tree: augmentation shortcut

RB-tree augmentation maintains data in each node of the tree that
represents the product of some associative operator applied to all the
nodes of the subtree rooted at

rb_tree: augmentation shortcut

RB-tree augmentation maintains data in each node of the tree that
represents the product of some associative operator applied to all the
nodes of the subtree rooted at that node. If a node in the tree
changes, augmentation data for the node is updated for that node and
all nodes on the path from that node to the tree root. However,
sometimes, augmenting a node changes no data in that node,
particularly if the associated operation is something involving 'max'
or 'min'. If augmentation changes nothing in a node, then the work of
walking to the tree root from that point is pointless, because
augmentation will change nothing in those nodes either. This change
makes it possible to avoid that wasted work.

Define RB_AUGMENT_CHECK as a macro much like RB_AUGMENT, but which
returns a value 'true' when augmentation changes the augmentation data
of a node, and false otherwise. Change code that unconditionally walks
and augments to the top of tree to code that stops once an
augmentation has no effect. In the case of rebalancing the tree after
insertion or deletion, where previously a node rotated into the path
was inevitably augmented on the march to the tree root, now check to
see if it needs augmentation because the march to the tree root
stopped before reaching it.

Change the augmentation function in iommu_gas.c so that it returns
true/false to indicate whether the augmentation had any effect.

Reviewed by: alc, kib
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36509

show more ...

rb_tree: silence unused function warnings

With DIAGNOSTIC set a kernel build generates warnings about the
defined-but-unused RB_RANK method. Don't set _RB_DIAGNOSTIC
automatically, to silence these

rb_tree: silence unused function warnings

With DIAGNOSTIC set a kernel build generates warnings about the
defined-but-unused RB_RANK method. Don't set _RB_DIAGNOSTIC
automatically, to silence these warnings.

Reported by: mjguzik@gmail.com
Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D36617

show more ...

rb_tree: pass parent to RB_INSERT_COLOR

Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up
a value already available. Make adjustments to a linux rbtree header,
which invokes it.

rb_tree: pass parent to RB_INSERT_COLOR

Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up
a value already available. Make adjustments to a linux rbtree header,
which invokes it.

Reviewed by: alc, hselasky
Differential Revision: https://reviews.freebsd.org/D36114

show more ...

rb_tree: reduce duplication in balancing code

Change RB_INSERT_COLOR and RB_REMOVE_COLOR so that the blocks of code
that are identical except for left and right being exchanged are made
only one blo

rb_tree: reduce duplication in balancing code

Change RB_INSERT_COLOR and RB_REMOVE_COLOR so that the blocks of code
that are identical except for left and right being exchanged are made
only one block with a variable to indicate left- or right-handedness.

Rename RB macros so that those not intended for external use begin
with an underscore.

Add comments to the balancing code so that another might understand it.

Reviewed by: alc, kib
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36393

show more ...

rb_tree: test rank balance

With _RB_DIAGNOSTIC defined, provide an RB_RANK method to compute the
rank of a node in an rb-tree, if the subtree rooted at that node is
rank-balanced, and -1 otherwise.

rb_tree: test rank balance

With _RB_DIAGNOSTIC defined, provide an RB_RANK method to compute the
rank of a node in an rb-tree, if the subtree rooted at that node is
rank-balanced, and -1 otherwise.

In rb_test, rewrite a bit to avoid malloc/free and nondeterministic
running times because of randomness. Allocate all the nodes on the
stack, and shuffle a set of keys to get randomness for the testing.

Add a rank-balance check for the completed tree.

Reviewed by: markj
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36484

show more ...

rb_tree: avoid extra reads in rebalancing

In RB_INSERT_COLOR and RB_REMOVE_COLOR, avoid reading a parent pointer
from memory, and then reading the left-color bit from memory, and then
reading the ri

rb_tree: avoid extra reads in rebalancing

In RB_INSERT_COLOR and RB_REMOVE_COLOR, avoid reading a parent pointer
from memory, and then reading the left-color bit from memory, and then
reading the right-color bit from memory, since they're all in the same
field. The compiler can't infer that only the first read is really
necessary, so write the code in a way so that it doesn't have to.

Drop RB_RED_LEFT and RB_RED_RIGHT macros that reach into memory to get
those bits. Drop RB_COLOR, the only thing left using RB_RED_LEFT and
RB_RED_RIGHT after the other changes, and go straight to DIAGNOSTIC
code in subr_stats to implement RB_COLOR for its single, dubious use
there.

Reviewed by: alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36353

show more ...

rb_tree: fine-tune RB_REMOVE

Improve RB_REMOVE by reading the fields of the removed node only once,
and by not writing to the removed node.

Reviewed by: kib
Discussed with: markj
MFC after: 3 weeks

rb_tree: fine-tune RB_REMOVE

Improve RB_REMOVE by reading the fields of the removed node only once,
and by not writing to the removed node.

Reviewed by: kib
Discussed with: markj
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36288

show more ...

rb_tree: optimize rb_insert

In searching for where to insert a new node, RB_INSERT discards the
address of the pointer that will have to be modified, so that it must
find it again from the values of

rb_tree: optimize rb_insert

In searching for where to insert a new node, RB_INSERT discards the
address of the pointer that will have to be modified, so that it must
find it again from the values of 'parent' and 'comp'. Stop discarding
that address, and so avoid having to recompute it.

Reviewed by: alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36317

show more ...

rb_tree: speed-up double rotation

RB_ROTATE_LEFT (and it symmetric twin) modify the rb-tree, adjusting
pointers so that what started as a proper tree ends up a proper
tree. When two consecutive rota

rb_tree: speed-up double rotation

RB_ROTATE_LEFT (and it symmetric twin) modify the rb-tree, adjusting
pointers so that what started as a proper tree ends up a proper
tree. When two consecutive rotations move the same node up the tree,
some of the pointers changed in the first rotation are immediately
changed again in the second - namely, the pointer from the rising node
to its new parent, and the pointer from that parent back to the rising
node. This change removes from RB_ROTATE macros the responsibility for
managing those two pointers, and leaves it to the code that calls for
rotations to fix up those pointers afterward. That drops a comparison
and a pair of assignments from every INSERT_COLOR or REMOVE_COLOR call
that ends in a double rotation.

A side-effect of this change is that the SWAP_CHILD macro must take as
a parameter a pointer to the node that is changing children, where it
is now computed from the old child. Since this macro is called in a
couple of places besides the RB_ROTATE macros, those calls are also
affected.

Reviewed by: alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36266

show more ...

iommu_gas: avoid pointless augmentation

iommu_gas_augment_entry updates a map entry element. Invoked as
RB_AUGMENT in RB tree code, it is applied from the point where the
tree is modified, all the w

iommu_gas: avoid pointless augmentation

iommu_gas_augment_entry updates a map entry element. Invoked as
RB_AUGMENT in RB tree code, it is applied from the point where the
tree is modified, all the way up to the root, and is also applied when
rotation moves a node down in the tree.

There are several opportunities to invoke it less. The automatic
augmentation with every rotation is a mistake. Delaying these
augmentations until RB_INSERT_COLOR or RB_REMOVE_COLOR are finishing
allows the augmentation code to be duplicated less, to work when there
is less register pressure, and to be skipped when conditions allow it:

In the double-rotate case of RB_INSERT_COLOR, augmentation after
the first rotation is not necessary when the element being moved
down the tree becomes a leaf. It was in the tree, and was a leaf,
before the RB_INSERT operation began, and so recomputing
augmentation for it would do nothing.

In the final (possibly only) rotation of RB_REMOVE_COLOR, both the
elements - the one moving up and the one moving down - end up in
the path from the deletion point to the tree root, so there's no
need to augment either of them immediately.

In RB_REMOVE, when the right child of the removed node replaces it
in tree, it began with a null left child. Replacement creates a
non-NULL left child, and then rotation may put a NULL node back in
that place. If that happens, start the augmenting-up-to-root with
the parent of that node, since augmentation would do nothing.

Adjust to avoid these needless augmentations.

Reviewed by: alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D35502

show more ...

rb_tree: resolve name clash

Rename 'tmp' to 'rb_update_tmp' in a macro to avoid a shadow variable panic.

Reported by: imb@protected-networks.net
Fixes: 35557a0d9169

rb_tree: update augmentation after element change

For an augmented rb_tree, allow a faster alternative to removing an
element from the tree, tweaking it slightly, and inserting it back
into the tree

rb_tree: update augmentation after element change

For an augmented rb_tree, allow a faster alternative to removing an
element from the tree, tweaking it slightly, and inserting it back
into the tree, knowing that its relative position in the tree is
unchanged. Instead, just change the element and invoke
RB_UPDATE_AUGMENT to fix the augmentation data for all the nodes in
the tree.

Reviewed by: kib
MFC after: 1 week
Differential Revision: https://reviews.freebsd.org/D36010

show more ...

tree(3): allow the compare function to return any signed type

This allows to write very short comparison function when we are
comparing just pointer values:

return ((intptr_t)((uintptr_t)a->ptr/2

tree(3): allow the compare function to return any signed type

This allows to write very short comparison function when we are
comparing just pointer values:

return ((intptr_t)((uintptr_t)a->ptr/2 - (uintptr_t)b->ptr/2));

Reviewed by: dougm, alc
Differential revision: https://reviews.freebsd.org/D35722

show more ...

rb_tree: fine-tune rebalancing code

Change parts of RB_INSERT_COLOR and RB_REMOVE_COLOR to reduce the
number of operations, by, in some cases, flipping two color bits at a
time instead of flipping e

rb_tree: fine-tune rebalancing code

Change parts of RB_INSERT_COLOR and RB_REMOVE_COLOR to reduce the
number of operations, by, in some cases, flipping two color bits at a
time instead of flipping each individually, in separate operations,
and by using a switch statement to replace a sequence of if-elses.
Rewrite RB_SET_PARENT to generate fewer instructions. These changes
reduce the code size by over 100 bytes on some architectures.

Also, allow RB users to define a preprocessor symbol to generate
RB_REMOVE_COLOR code that matches the implementation described in the
original weak-AVL paper in one particular case, instead of the still
correct, but slightly more efficient implementation of that case
currently implemented.

Reviewed by: alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D35524

show more ...

rb_tree: silence coverity

Add comments to RB_INSERT_COLOR to silence coverity warnings about the
use of an uninitialized variable. Since other static analyzers will
complain too, add a comment to e

rb_tree: silence coverity

Add comments to RB_INSERT_COLOR to silence coverity warnings about the
use of an uninitialized variable. Since other static analyzers will
complain too, add a comment to explain why the complaints are unwarranted.

Reviewed by: markj
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D35671

show more ...

rb_tree: optimize tree rotation

The RB_ROTATE macros begin with fetching a field via a pointer. In
most cases, that value is one that has already been pulled into a
register, and the compiler cannot

rb_tree: optimize tree rotation

The RB_ROTATE macros begin with fetching a field via a pointer. In
most cases, that value is one that has already been pulled into a
register, and the compiler cannot infer that. So, to eliminate those
needless fetches, have the caller of the RB_ROTATE macros present the
data in the third macro parameter, rather than having the macro fetch
it.

Differential Revision: https://reviews.freebsd.org/D35520

show more ...

rb_tree: drop needless tests from rb_next, rb_prev

In RB_NEXT, when there is no RB_RIGHT node, the search must proceed
through the parent node.

There is code written to handle the case when the par

rb_tree: drop needless tests from rb_next, rb_prev

In RB_NEXT, when there is no RB_RIGHT node, the search must proceed
through the parent node.

There is code written to handle the case when the parent is non-NULL
and the current element is the left child of that parent. If you
assume that the current element is either the left child of its
parent, or the right child of its parent, but not both, then this test
is not necessary. Instead of assigning RB_PARENT(elm, field) to elm
when elm == RB_LEFT, removing the test has the code assign
RB_PARENT(elm, field) to elm when elm != RB_RIGHT. There's no need to
examine the RB_LEFT field at all.

This change removes that needless RB_LEFT test, and makes a similar
change to the RB_PREV implementation.

Reviewed by: alc
MFC after: 1 week
Differential Revision: https://reviews.freebsd.org/D35450

show more ...