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.
A test on lip5:
I used the counting patch of D35390 to add 2 new sysctls. One counts nodes traversed in the tree. The other accumulates tree sizes. I ran 4 MAERTS tests, and recorded the effects on the stats of each test. Then I merged the counting patch of D35390 and this one (which requires a bit of hand-manipulation of a couple of loops) and applied the same test to the resulting kernel.
For the base case:
# lookups size change 75184049 61872494055 79019334 63448441073 75385477 60707783212
For the modified code:
# lookups size change 42367978 66462958352 45377035 65421422630 46444115 65362449399
So, it seems there's some benefit.
Update after rb augment patch. Make start_gap point to the predecessor of the first empty gap that is big enough to hold a minimum allocation (1 page + 2 guards).
Define insert_next and insert_prev tree operations, and use them to update the iommu_gas_entries tree.
Don't 'fix' the start_gap hint until the next find_space. If an insert or removal leaves it at the root of a subtree with no usable gaps, a climb-up on the next find_space will fix it.
Rewrite the rb_remove code for greater clarity. Add more to the comment before find_space updates start_gap, to make clear why a->size does not matter there.
The value of start_gap is adjusted for the smallest possible allocation, not for this particular (possibly larger) allocation.
I think a comment describing start_gap should be added. In particular, clarifying my confusion that start_gap is the place for min allocation.