iommu_gas: start space search from first free space

[dougm]

Summary

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.

Test Plan

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.

[dougm]

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).

[dougm]

Define insert_next and insert_prev tree operations, and use them to update the iommu_gas_entries tree.

[dougm]

Use INSERT_NEXT, INSERT_PREV macros.

[dougm]

Use RB_INSERT_NEXT and RB_INSERT_PREV in more places.

[dougm]

Resolve conflict with updated tree.h comments.

[dougm]

Remove the tree changes that have been checked in.

[dougm]

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.

[kib]

sys/dev/iommu/iommu_gas.c

227

This expression is in style, but IMO it is too confusing for a reader. Could you please add braces for the inner '?:' expression?

437

Should a->size somehow participate in the expression for min_free?

[dougm]

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.

sys/dev/iommu/iommu_gas.c

437

The value of start_gap is adjusted for the smallest possible allocation, not for this particular (possibly larger) allocation.

[kib]

I think a comment describing start_gap should be added. In particular, clarifying my confusion that start_gap is the place for min allocation.

[alc]

sys/dev/iommu/iommu_gas.c

421–422

This function has gotten so complicated that I'd suggest adding a comment at the top that says that it implements an address ordered first fit.

431

Might as well move this up so the above asserts can use it.