LinuxKPI: Add rb_add_cached function

rb_add_cached inserts node into the leftmost cached tree

Sponsored by: Serenity CyberSecurity, LLC
MFC after: 1 week
Reviewed by: manu
Differential Revision: ht

LinuxKPI: Add rb_add_cached function

rb_add_cached inserts node into the leftmost cached tree

Sponsored by: Serenity CyberSecurity, LLC
MFC after: 1 week
Reviewed by: manu
Differential Revision: https://reviews.freebsd.org/D45608

show more ...

sys: Remove $FreeBSD$: two-line .h pattern

Remove /^\s*\*\n \*\s+\$FreeBSD\$$\n/

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

LinuxKPI: Constantly use _LINUXKPI_ prefix in include guards

MFC after: 1 week
Reviewed by: bz, emaste, hselasky, manu
Differential Revision: https://reviews.freebsd.org/D33562

LinuxKPI: Implement interval_tree

Required by drm-kmod

MFC after: 1 week
Reviewed by: hselasky, manu
Differential Revision: https://reviews.freebsd.org/D32869

LinuxKPI: Import some linux/rbtree.h functions from OpenBSD

Required by drm-kmod

Obtained from: OpenBSD
MFC after: 1 week

Allow the rbtree header file in the LinuxKPI to be used in standalone code.

MFC after: 1 week
Sponsored by: Mellanox Technologies // NVIDIA Networking

In r362552, RB_SET_PARENT is defined, and use in parens in
RB_CLEAR_NODE. But it is not an expression, and ought not to be
enclosed in parens. Remove them.

Approved by: markj
Differential Revision

In r362552, RB_SET_PARENT is defined, and use in parens in
RB_CLEAR_NODE. But it is not an expression, and ought not to be
enclosed in parens. Remove them.

Approved by: markj
Differential Revision: https://reviews.freebsd.org/D25421

show more ...

Define RB_SET_PARENT to do all assignments to rb parent
pointers. Define RB_SWAP_CHILD to replace the child of a parent with
its twin, and use it in 4 places. Use RB_SET in rb_link_node to remove
the

Define RB_SET_PARENT to do all assignments to rb parent
pointers. Define RB_SWAP_CHILD to replace the child of a parent with
its twin, and use it in 4 places. Use RB_SET in rb_link_node to remove
the only linuxkpi reference to color, and then drop color- and
parent-related definitions that are defined and used only in rbtree.h.

This is intended to be entirely cosmetic, with no impact on program
behavior, and leave RB_PARENT and RB_SET_PARENT as the only ways to
read and write rb parent pointers.

Reviewed by: markj, kib
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D25264

show more ...

Linuxkpi uses the rb-tree structures without using their interfaces,
making them break when the representation changes. Revert changes that
eliminated the color field from rb-trees, leaving everythin

Linuxkpi uses the rb-tree structures without using their interfaces,
making them break when the representation changes. Revert changes that
eliminated the color field from rb-trees, leaving everything as it was
before.

Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D25250

show more ...

Revert r362108, as it breaks compilation.

The linuxkpi code accesses left/right rb tree pointers without using
RB_LEFT or RB_RIGHT, so they aren't stripping off the color bit
encoded there. Strip off that bit for linuxkpi.

Reported by: dch

The linuxkpi code accesses left/right rb tree pointers without using
RB_LEFT or RB_RIGHT, so they aren't stripping off the color bit
encoded there. Strip off that bit for linuxkpi.

Reported by: dch
Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D25245

show more ...

To reduce the size of an rb_node, drop the color field. Set the least
significant bit in the pointer to the node from its parent to indicate
that the node is red. Have the tree rotation macros leave

To reduce the size of an rb_node, drop the color field. Set the least
significant bit in the pointer to the node from its parent to indicate
that the node is red. Have the tree rotation macros leave the
old-parent/new-child node red and the new-parent/old-child node black.

This change makes RB_LEFT and RB_RIGHT no longer assignable, and
RB_COLOR no longer defined. Any code that modifies the tree or
examines a node color would have to be modified after this change.

Reviewed by: markj
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D25105

show more ...

MFH r289384-r293170

Sponsored by: The FreeBSD Foundation

Catch up with head (r291075).

Merge from head

Finish process of moving the LinuxKPI module into the default kernel build.

- Move all files related to the LinuxKPI into sys/compat/linuxkpi and
its subfolders.
- Update sys/conf/files and some M

Finish process of moving the LinuxKPI module into the default kernel build.

- Move all files related to the LinuxKPI into sys/compat/linuxkpi and
its subfolders.
- Update sys/conf/files and some Makefiles to use new file locations.
- Added description of COMPAT_LINUXKPI to sys/conf/NOTES which in turn
adds the LinuxKPI to all LINT builds.
- The LinuxKPI can be added to the kernel by setting the
COMPAT_LINUXKPI option. The OFED kernel option no longer builds the
LinuxKPI into the kernel. This was done to keep the build rules for
the LinuxKPI in sys/conf/files simple.
- Extend the LinuxKPI module to include support for USB by moving the
Linux USB compat from usb.ko to linuxkpi.ko.
- Bump the FreeBSD_version.
- A universe kernel build has been done.

Reviewed by: np @ (cxgb and cxgbe related changes only)
Sponsored by: Mellanox Technologies

show more ...