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