Change Details

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. This change looks for all those opportunities. First, the automatic augmentation with every rotation is a mistake. 1. 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. 2. 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 here. 3. 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. At some point, augmentation may have no effect on an element. Once that happens, there's no point in continuing the augmentation march up the tree - except that there may be one or two nodes put into the path by rotation, and those still require augmentation updates. This change defines RB_AUGMENTION_CHECK, intended to return a boolean to indicate when augmentation changed something. It changes the RB_{}_COLOR functions so that each returns a pointer to the first node that requires augmentation on account of rotation, or NULL if no rotation happened. It has the RB_()_COLOR functions make more careful choices about when to augment, and has the INSERT/REMOVE functions climb the path-to-root only until augmentation has no effect, and then handles augmentation required by rotations.

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. This change looks for some of those opportunities. The automatic augmentation with every rotation is a mistake. 1. 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. 2. 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 here. 3. 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.

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. This change looks for allsome of those opportunities. First, the The automatic augmentation with every rotation is a mistake. 1. 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. 2. 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 here. 3. 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. At some point, augmentation may have no effect on an element. Once that happens, there's no point in continuing the augmentation march up the tree - except that there may be one or two nodes put into the path by rotation, and those still require augmentation updates. This change defines RB_AUGMENTION_CHECK, intended to return a boolean to indicate when augmentation changed something. It changes the RB_{}_COLOR functions so that each returns a pointer to the first node that requires augmentation on account of rotation, or NULL if no rotation happened. It has the RB_()_COLOR functions make more careful choices about when to augment, and has the INSERT/REMOVE functions climb the path-to-root only until augmentation has no effect, and then handles augmentation required by rotations. djust to avoid these needless augmentations.