iommu_gas: start space search from 1st free space
Maintain a pointer to an element in the domain map 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.
In experiments with netperf streaming, this reduces by about 40% the
number of map entries examined in first-fit allocation.
Reviewed by: alc, kib
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36624
(cherry picked from commit 8b221ca631c2d28584a4b6207dc107d8ff5a1b2f)