On 07/26/2018 03:42 PM, Matthew Wilcox wrote:
> On Thu, Jul 26, 2018 at 02:54:56PM -0400, Tony Battersby wrote:
>> dma_pool_free() scales poorly when the pool contains many pages because
>> pool_find_page() does a linear scan of all allocated pages. Improve its
>> scalability by replacing the linear scan with a red-black tree lookup.
>> In big O notation, this improves the algorithm from O(n^2) to O(n * log n).
> This is a lot of code to get us to O(n * log(n)) when we can use less
> code to go to O(n). dma_pool_free() is passed the virtual address.
> We can go from virtual address to struct page with virt_to_page().
> In struct page, we have 5 words available (20/40 bytes), and it's trivial
> to use one of them to point to the struct dma_page.
>
Thanks for the tip. I will give that a try.
_______________________________________________
iommu mailing list
iommu@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/iommu
