Re: [PATCH 2/3] dmapool: improve scalability of dma_pool_free

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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.



[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Index of Archives]     [SCSI Target Devel]     [Linux SCSI Target Infrastructure]     [Kernel Newbies]     [IDE]     [Security]     [Git]     [Netfilter]     [Bugtraq]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux ATA RAID]     [Linux IIO]     [Samba]     [Device Mapper]

  Powered by Linux