On Thu, Jul 26, 2018 at 9:54 PM, Tony Battersby <to...@cybernetics.com> 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).
Few style related comments. > I moved some code from dma_pool_destroy() into pool_free_page() to avoid code > repetition. I would rather split that part as a separate preparatory change which doesn't change the behaviour. > #include <linux/string.h> > #include <linux/types.h> > #include <linux/wait.h> > +#include <linux/rbtree.h> It looks misordered. > + struct dma_page *this_page = > + container_of(*node, struct dma_page, page_node); #define to_dma_page() container_of() ? > + WARN(1, > + "%s: %s: DMA address overlap: old 0x%llx new > 0x%llx len %zu\n", > + pool->dev ? dev_name(pool->dev) : "(nodev)", > + pool->name, (u64) this_page->dma, (u64) dma, Use proper %p extensions for the DMA addresses: https://elixir.bootlin.com/linux/latest/source/Documentation/core-api/printk-formats.rst#L150 -- With Best Regards, Andy Shevchenko _______________________________________________ iommu mailing list iommu@lists.linux-foundation.org https://lists.linuxfoundation.org/mailman/listinfo/iommu
