iommu_gas: restrict tree search to promising paths

[dougm]

Summary

In iommu_gas_lowermatch and iommu_gas_uppermatch, a subtree search is quickly terminated if the largest available free space in the subtree is below a limit, where that limit is related to the size of the allocation request. However, that limit is too small; it does not account for both of the guard pages that will surround the allocated space, but only for one of them. Consequently, it permits the search to proceed through nodes that cannot produce a successful allocation for all the requested space. Fix that limit to improve search performance.

Submitted by: Weixi Zhu ([e-mail])

Test Plan

https://reviews.freebsd.org/D35390?id=106643 provides a patch that adds test instrumentation to count all the nodes examined in searching for free space via iommu_gas_map. Applying that patch defines a value hw.iommu.gas_lookup that can be examined via sysctl.

A test using netperf exercised iommu_map and reported bandwidth, and the gas_lookup value was reported after each test, for 6 tests. The lines below show the gas_lookup value and the last line of 'netperf -H lip3 -t TCP_MAERTS -D 1' for each test. First, for the code without the changes proposed here, with a GENERIC_NODEBUG kernel:

hw.iommu.gas_lookup: 370842
65536 32768 32768 10.00 893.64
hw.iommu.gas_lookup: 387755948
65536 32768 32768 10.00 1756.93
hw.iommu.gas_lookup: 695366080
65536 32768 32768 10.00 1695.35
hw.iommu.gas_lookup: 1007081397
65536 32768 32768 10.00 547.19
hw.iommu.gas_lookup: 1421576275
65536 32768 32768 10.00 636.96
hw.iommu.gas_lookup: 1804288919
65536 32768 32768 10.00 484.70
hw.iommu.gas_lookup: 2203040207

Then, the same, except with the changes of this patch included:

hw.iommu.gas_lookup: 306892
65536 32768 32768 10.00 3488.28
hw.iommu.gas_lookup: 84637508
65536 32768 32768 10.00 3510.19
hw.iommu.gas_lookup: 163600312
65536 32768 32768 10.00 3448.24
hw.iommu.gas_lookup: 243917853
65536 32768 32768 10.00 3252.16
hw.iommu.gas_lookup: 324202659
65536 32768 32768 10.00 3508.05
hw.iommu.gas_lookup: 406577445
65536 32768 32768 10.00 3425.78
hw.iommu.gas_lookup: 490016932

Bandwidth is up. Nodes accessed are down.

[kib]

I would add a comment explaining that 2 is for two guard pages.