HomeFreeBSD

iommu_gas: start space search from 1st free space

Description

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

Details

Provenance
dougmAuthored on Oct 29 2022, 5:50 AM
Reviewer
alc
Differential Revision
D36624: iommu_gas: start space search from first free space
Parents
rG028382670670: usr.bin: hook wg(8) up to the build
Branches
Unknown
Tags
Unknown