HomeFreeBSD

iommu_gas: avoid pointless augmentation

Description

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

(cherry picked from commit 7f2ec173e4613a57732ca162572d25b0a546689f)

Details

Provenance
dougmAuthored on Aug 6 2022, 6:26 PM
Reviewer
alc
Differential Revision
D35502: iommu_gas: avoid needless tree augmentations
Parents
rG9644bc4a1126: Decode couple arrays in NFIT table.
Branches
Unknown
Tags
Unknown