On 10/24/2023 7:58 PM, Baolu Lu wrote: > On 2023/10/24 16:41, 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 is not performance >> friendly given that I/O page fault handling patch is performance >> critical, and parallel heavy dsa_test may cause cpu stuck due to >> the low efficiency and lock competition in current path. >> >> 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. >> >> This series depends on "deliver page faults to user space" patch-set: >> https://lore.kernel.org/linux-iommu/20230928042734.16134-1-baolu.lu@xxxxxxxxxxxxxxx/ >> > > The note above is not part of the commit message, and should be placed > below the tear line or in the cover letter, if there is one. Will fix, thanks for catching! BRs, Jiaqing
