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

[Matthew Wilcox <willy@infradead.org>]

On Thu, Jul 26, 2018 at 04:06:05PM -0400, Tony Battersby wrote:
> 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.

If you're up for more major surgery, then I think we can put all the
information currently stored in dma_page into struct page.  Something
like this:

+++ b/include/linux/mm_types.h
@@ -152,6 +152,12 @@ struct page {
                        unsigned long hmm_data;
                        unsigned long _zd_pad_1;        /* uses mapping */
                };
+               struct {        /* dma_pool pages */
+                       struct list_head dma_list;
+                       unsigned short in_use;
+                       unsigned short offset;
+                       dma_addr_t dma;
+               };
 
                /** @rcu_head: You can use this to free a page by RCU. */
                struct rcu_head rcu_head;

page_list -> dma_list
vaddr goes away (page_to_virt() exists)
dma -> dma
in_use and offset shrink from 4 bytes to 2.

Some 32-bit systems have a 64-bit dma_addr_t, and on those systems,
this will be 8 + 2 + 2 + 8 = 20 bytes.  On 64-bit systems, it'll be
16 + 2 + 2 + 4 bytes of padding + 8 = 32 bytes (we have 40 available).