Change Details

Maintain a pointer to an element in the iommu_gas_entries tree that is left of the first sufficiently large free gap in the tree and start the search for free space there, rather than at the root of the tree. The element is the rightmost such element, except possibly after an insertion that exactly fills up the first free gap. Define RB_INSERT_NEXT and RB_INSERT_PREV to insert items in the RB tree that are known to follow or precede a given item, to avoid starting a search at the tree root or using comparisons. Use these to insert a new node when space is found in the iommu_gas_entries tree.

Maintain a pointer to an element in the iommu_gas_entries tree that is left of any sufficiently large free gap in the tree and start the search for free space there, rather than at the root of the tree. On find_space, move that pointer to the leftmost leaf in the subtree of nodes with free_down greater than or equal to the minimum allocation size before starting the search for space from that pointer. On removal of a node with address less than that pointer, update that pointer to point to the predecessor or successor of the removed node.

Maintain a pointer to an element in the iommu_gas_entries tree that is left of the firstany sufficiently large free gap in the tree and start the search for free space there, rather than at the root of the tree. The element is the rightmost such elementOn find_space, except possibly after an insertion that exactly fills up the first free gap. Define RB_INSERT_NEXT and RB_INSERT_PREV to insert items in the RB tree that are known to follow or precede a given itemmove that pointer to the leftmost leaf in the subtree of nodes with free_down greater than or equal to the minimum allocation size before starting the search for space from that pointer. On removal of a node with address less than that pointer, to avoid starting a search at the tree root or using comparisons. Use these to insert a new node when space is found in the iommu_gas_entries tree.update that pointer to point to the predecessor or successor of the removed node.