The patch titled
Subject: mm/dmapool.c: improve scalability of dma_pool_alloc()
has been added to the -mm tree. Its filename is
dmapool-improve-scalability-of-dma_pool_alloc.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/dmapool-improve-scalability-of-dma_pool_alloc.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/dmapool-improve-scalability-of-dma_pool_alloc.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Tony Battersby <tonyb@xxxxxxxxxxxxxxx>
Subject: mm/dmapool.c: improve scalability of dma_pool_alloc()
dma_pool_alloc() scales poorly when allocating a large number of pages
because it does a linear scan of all previously-allocated pages before
allocating a new one. Improve its scalability by maintaining a separate
list of pages that have free blocks ready to (re)allocate. In big O
notation, this improves the algorithm from O(n^2) to O(n).
Link: http://lkml.kernel.org/r/e982cd38-a721-bd06-8da8-0d6a0480685c@xxxxxxxxxxxxxxx
Signed-off-by: Tony Battersby <tonyb@xxxxxxxxxxxxxxx>
Acked-by: Matthew Wilcox <willy@xxxxxxxxxxxxx>
Cc: Andy Shevchenko <andy.shevchenko@xxxxxxxxx>
Cc: Christoph Hellwig <hch@xxxxxx>
Cc: John Garry <john.garry@xxxxxxxxxx>
Cc: Marek Szyprowski <m.szyprowski@xxxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
mm/dmapool.c | 92 +++++++++++++++++++++++++++++++++----------------
1 file changed, 63 insertions(+), 29 deletions(-)
--- a/mm/dmapool.c~dmapool-improve-scalability-of-dma_pool_alloc
+++ a/mm/dmapool.c
@@ -15,11 +15,16 @@
* Many older drivers still have their own code to do this.
*
* The current design of this allocator is fairly simple. The pool is
- * represented by the 'struct dma_pool' which keeps a doubly-linked list of
- * allocated pages. Each page in the page_list is split into blocks of at
- * least 'size' bytes. Free blocks are tracked in an unsorted singly-linked
- * list of free blocks within the page. Used blocks aren't tracked, but we
- * keep a count of how many are currently allocated from each page.
+ * represented by the 'struct dma_pool'. Each allocated page is split into
+ * blocks of at least 'size' bytes. Free blocks are tracked in an unsorted
+ * singly-linked list of free blocks within the page. Used blocks aren't
+ * tracked, but we keep a count of how many are currently allocated from each
+ * page.
+ *
+ * The pool keeps two doubly-linked list of allocated pages. The 'available'
+ * list tracks pages that have one or more free blocks, and the 'full' list
+ * tracks pages that have no free blocks. Pages are moved from one list to
+ * the other as their blocks are allocated and freed.
*/
#include <linux/device.h>
@@ -43,7 +48,10 @@
#endif
struct dma_pool { /* the pool */
- struct list_head page_list;
+#define POOL_FULL_IDX 0
+#define POOL_AVAIL_IDX 1
+#define POOL_MAX_IDX 2
+ struct list_head page_list[POOL_MAX_IDX];
spinlock_t lock;
size_t size;
struct device *dev;
@@ -54,7 +62,7 @@ struct dma_pool { /* the pool */
};
struct dma_page { /* cacheable header for 'allocation' bytes */
- struct list_head page_list;
+ struct list_head dma_list;
void *vaddr;
dma_addr_t dma;
unsigned int in_use;
@@ -70,7 +78,6 @@ show_pools(struct device *dev, struct de
unsigned temp;
unsigned size;
char *next;
- struct dma_page *page;
struct dma_pool *pool;
next = buf;
@@ -84,11 +91,18 @@ show_pools(struct device *dev, struct de
list_for_each_entry(pool, &dev->dma_pools, pools) {
unsigned pages = 0;
unsigned blocks = 0;
+ int list_idx;
spin_lock_irq(&pool->lock);
- list_for_each_entry(page, &pool->page_list, page_list) {
- pages++;
- blocks += page->in_use;
+ for (list_idx = 0; list_idx < POOL_MAX_IDX; list_idx++) {
+ struct dma_page *page;
+
+ list_for_each_entry(page,
+ &pool->page_list[list_idx],
+ dma_list) {
+ pages++;
+ blocks += page->in_use;
+ }
}
spin_unlock_irq(&pool->lock);
@@ -163,7 +177,8 @@ struct dma_pool *dma_pool_create(const c
retval->dev = dev;
- INIT_LIST_HEAD(&retval->page_list);
+ INIT_LIST_HEAD(&retval->page_list[POOL_FULL_IDX]);
+ INIT_LIST_HEAD(&retval->page_list[POOL_AVAIL_IDX]);
spin_lock_init(&retval->lock);
retval->size = size;
retval->boundary = boundary;
@@ -252,7 +267,7 @@ static void pool_free_page(struct dma_po
void *vaddr = page->vaddr;
dma_addr_t dma = page->dma;
- list_del(&page->page_list);
+ list_del(&page->dma_list);
if (is_page_busy(page)) {
dev_err(pool->dev,
@@ -278,8 +293,8 @@ static void pool_free_page(struct dma_po
*/
void dma_pool_destroy(struct dma_pool *pool)
{
- struct dma_page *page;
bool empty = false;
+ int list_idx;
if (unlikely(!pool))
return;
@@ -294,10 +309,15 @@ void dma_pool_destroy(struct dma_pool *p
device_remove_file(pool->dev, &dev_attr_pools);
mutex_unlock(&pools_reg_lock);
- while ((page = list_first_entry_or_null(&pool->page_list,
- struct dma_page,
- page_list))) {
- pool_free_page(pool, page);
+ for (list_idx = 0; list_idx < POOL_MAX_IDX; list_idx++) {
+ struct dma_page *page;
+
+ while ((page = list_first_entry_or_null(
+ &pool->page_list[list_idx],
+ struct dma_page,
+ dma_list))) {
+ pool_free_page(pool, page);
+ }
}
kfree(pool);
@@ -325,10 +345,11 @@ void *dma_pool_alloc(struct dma_pool *po
might_sleep_if(gfpflags_allow_blocking(mem_flags));
spin_lock_irqsave(&pool->lock, flags);
- list_for_each_entry(page, &pool->page_list, page_list) {
- if (page->offset < pool->allocation)
- goto ready;
- }
+ page = list_first_entry_or_null(&pool->page_list[POOL_AVAIL_IDX],
+ struct dma_page,
+ dma_list);
+ if (page)
+ goto ready;
/* pool_alloc_page() might sleep, so temporarily drop &pool->lock */
spin_unlock_irqrestore(&pool->lock, flags);
@@ -339,11 +360,15 @@ void *dma_pool_alloc(struct dma_pool *po
spin_lock_irqsave(&pool->lock, flags);
- list_add(&page->page_list, &pool->page_list);
+ list_add(&page->dma_list, &pool->page_list[POOL_AVAIL_IDX]);
ready:
page->in_use++;
offset = page->offset;
page->offset = *(int *)(page->vaddr + offset);
+ if (page->offset >= pool->allocation)
+ /* Move page from the "available" list to the "full" list. */
+ list_move_tail(&page->dma_list,
+ &pool->page_list[POOL_FULL_IDX]);
retval = offset + page->vaddr;
*handle = offset + page->dma;
#ifdef DMAPOOL_DEBUG
@@ -381,13 +406,19 @@ EXPORT_SYMBOL(dma_pool_alloc);
static struct dma_page *pool_find_page(struct dma_pool *pool, dma_addr_t dma)
{
- struct dma_page *page;
+ int list_idx;
- list_for_each_entry(page, &pool->page_list, page_list) {
- if (dma < page->dma)
- continue;
- if ((dma - page->dma) < pool->allocation)
- return page;
+ for (list_idx = 0; list_idx < POOL_MAX_IDX; list_idx++) {
+ struct dma_page *page;
+
+ list_for_each_entry(page,
+ &pool->page_list[list_idx],
+ dma_list) {
+ if (dma < page->dma)
+ continue;
+ if ((dma - page->dma) < pool->allocation)
+ return page;
+ }
}
return NULL;
}
@@ -444,6 +475,9 @@ void dma_pool_free(struct dma_pool *pool
#endif
page->in_use--;
+ if (page->offset >= pool->allocation)
+ /* Move page from the "full" list to the "available" list. */
+ list_move(&page->dma_list, &pool->page_list[POOL_AVAIL_IDX]);
*(int *)vaddr = page->offset;
page->offset = offset;
/*
_
Patches currently in -mm which might be from tonyb@xxxxxxxxxxxxxxx are
dmapool-fix-boundary-comparison.patch
dmapool-remove-checks-for-dev-==-null.patch
dmapool-cleanup-dma_pool_destroy.patch
dmapool-improve-scalability-of-dma_pool_alloc.patch
dmapool-rename-fields-in-dma_page.patch
dmapool-improve-scalability-of-dma_pool_free.patch
dmapool-cleanup-integer-types.patch
dmapool-improve-accuracy-of-debug-statistics.patch
dmapool-debug-prevent-endless-loop-in-case-of-corruption.patch
