Page MenuHomeFreeBSD

iommu_gas: start space search from first free space

Authored by dougm on Sep 18 2022, 7:00 PM.
Referenced Files
Unknown Object (File)
Jun 7 2024, 2:50 PM
Unknown Object (File)
Jun 7 2024, 9:32 AM
Unknown Object (File)
Jun 5 2024, 2:13 PM
Unknown Object (File)
Jun 4 2024, 12:18 PM
Unknown Object (File)
Jun 3 2024, 2:47 PM
Unknown Object (File)
May 29 2024, 6:32 PM
Unknown Object (File)
May 29 2024, 6:32 PM
Unknown Object (File)
May 29 2024, 6:32 PM



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.

Diff Detail

rG FreeBSD src repository
Lint Not Applicable
Tests Not Applicable

Event Timeline

dougm requested review of this revision.Sep 18 2022, 7:00 PM
dougm created this revision.

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 edited the summary of this revision. (Show Details)
dougm edited the test plan for this revision. (Show Details)

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

dougm edited the test plan for this revision. (Show Details)


Use RB_INSERT_NEXT and RB_INSERT_PREV in more places.

Resolve conflict with updated tree.h comments.

Remove the tree changes that have been checked in.

dougm edited the summary of this revision. (Show Details)
dougm edited the test plan for this revision. (Show Details)

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.


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


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

dougm marked 2 inline comments as done.

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.

This revision is now accepted and ready to land.Oct 27 2022, 12:24 AM
alc added inline comments.

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.


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