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.