On 2023/8/22 0:52, Jason Gunthorpe wrote:
On Mon, Aug 21, 2023 at 12:16:59AM -0700, Huang Jiaqing wrote:
The existing IO page fault handler locates the PCI device by calling
pci_get_domain_bus_and_slot(), which searches the list of all PCI
devices until the desired PCI device is found. This is inefficient
because the algorithm efficiency of searching a list is O(n). In the
critical path of handling an IO page fault, this can cause a significant
performance bottleneck.
To improve the performance of the IO page fault handler, replace
pci_get_domain_bus_and_slot() with a local red-black tree. A red-black
tree is a self-balancing binary search tree, which means that the
average time complexity of searching a red-black tree is O(log(n)). This
is significantly faster than O(n), so it can significantly improve the
performance of the IO page fault handler.
In addition, we can only insert the affected devices (those that have IO
page fault enabled) into the red-black tree. This can further improve
the performance of the IO page fault handler.
Signed-off-by: Huang Jiaqing<jiaqing.huang@xxxxxxxxx>
---
drivers/iommu/intel/iommu.c | 68 +++++++++++++++++++++++++++++++++++++
drivers/iommu/intel/iommu.h | 8 +++++
drivers/iommu/intel/svm.c | 13 +++----
3 files changed, 81 insertions(+), 8 deletions(-)
I feel like this should be a helper library provided by the core
code, doesn't every PRI driver basically need the same thing?
It seems to be. pci_get_domain_bus_and_slot() is also used in the amd
driver. And the risc-v iommu driver under discussion is also proposing
this.
Best regards,
baolu
