From patchwork Thu Jul 26 18:54:21 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tony Battersby X-Patchwork-Id: 10546333 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 2AFD61805 for ; Thu, 26 Jul 2018 19:11:53 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1CFA22BCA0 for ; Thu, 26 Jul 2018 19:11:53 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 10CCE2BCC2; Thu, 26 Jul 2018 19:11:53 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00,MAILING_LIST_MULTI, RCVD_IN_DNSWL_HI autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id A32892BCD0 for ; Thu, 26 Jul 2018 19:11:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1731183AbeGZUaC (ORCPT ); Thu, 26 Jul 2018 16:30:02 -0400 Received: from mail.cybernetics.com ([173.71.130.66]:37646 "EHLO mail.cybernetics.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1730517AbeGZUaC (ORCPT ); Thu, 26 Jul 2018 16:30:02 -0400 X-ASG-Debug-ID: 1532631261-0fb3b01fb33a2750001-ziuLRu Received: from cybernetics.com ([10.157.1.126]) by mail.cybernetics.com with ESMTP id wjiWuOT5fySaaiG1 (version=SSLv3 cipher=DES-CBC3-SHA bits=112 verify=NO); Thu, 26 Jul 2018 14:54:21 -0400 (EDT) X-Barracuda-Envelope-From: tonyb@cybernetics.com X-ASG-Whitelist: Client Received: from [10.157.2.224] (account tonyb HELO [192.168.200.1]) by cybernetics.com (CommuniGate Pro SMTP 5.1.14) with ESMTPSA id 8304004; Thu, 26 Jul 2018 14:54:21 -0400 From: Tony Battersby Subject: [PATCH 1/3] dmapool: improve scalability of dma_pool_alloc To: Christoph Hellwig , Marek Szyprowski , Matthew Wilcox , Sathya Prakash , Chaitra P B , Suganath Prabu Subramani , iommu@lists.linux-foundation.org, linux-mm@kvack.org, linux-scsi@vger.kernel.org, MPT-FusionLinux.pdl@broadcom.com X-ASG-Orig-Subj: [PATCH 1/3] dmapool: improve scalability of dma_pool_alloc Message-ID: <15ff502d-d840-1003-6c45-bc17f0d81262@cybernetics.com> Date: Thu, 26 Jul 2018 14:54:21 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 Content-Language: en-US X-Barracuda-Connect: UNKNOWN[10.157.1.126] X-Barracuda-Start-Time: 1532631261 X-Barracuda-Encrypted: DES-CBC3-SHA X-Barracuda-URL: https://10.157.1.122:443/cgi-mod/mark.cgi X-Barracuda-Scan-Msg-Size: 4197 X-Virus-Scanned: by bsmtpd at cybernetics.com X-Barracuda-BRTS-Status: 1 Sender: linux-scsi-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-scsi@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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). Signed-off-by: Tony Battersby --- Using list_del_init() in dma_pool_alloc() makes it safe to call list_del() unconditionally when freeing the page. In dma_pool_free(), the check for being already in avail_page_list could be written several different ways. The most obvious way is: if (page->offset >= pool->allocation) list_add(&page->avail_page_link, &pool->avail_page_list); Another way would be to check page->in_use. But since it is already using list_del_init(), checking the list pointers directly is safest to prevent any possible list corruption in case the caller misuses the API (e.g. double-dma_pool_free()) with DMAPOOL_DEBUG disabled. --- a/mm/dmapool.c +++ b/mm/dmapool.c @@ -20,6 +20,10 @@ * 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 avail_page_list keeps track of pages that have one or more free blocks + * available to (re)allocate. Pages are moved in and out of avail_page_list + * as their blocks are allocated and freed. */ #include @@ -44,6 +48,7 @@ struct dma_pool { /* the pool */ struct list_head page_list; + struct list_head avail_page_list; spinlock_t lock; size_t size; struct device *dev; @@ -55,6 +60,7 @@ struct dma_pool { /* the pool */ struct dma_page { /* cacheable header for 'allocation' bytes */ struct list_head page_list; + struct list_head avail_page_link; void *vaddr; dma_addr_t dma; unsigned int in_use; @@ -164,6 +170,7 @@ struct dma_pool *dma_pool_create(const c retval->dev = dev; INIT_LIST_HEAD(&retval->page_list); + INIT_LIST_HEAD(&retval->avail_page_list); spin_lock_init(&retval->lock); retval->size = size; retval->boundary = boundary; @@ -256,6 +263,7 @@ static void pool_free_page(struct dma_po #endif dma_free_coherent(pool->dev, pool->allocation, page->vaddr, dma); list_del(&page->page_list); + list_del(&page->avail_page_link); kfree(page); } @@ -298,6 +306,7 @@ void dma_pool_destroy(struct dma_pool *p pool->name, page->vaddr); /* leak the still-in-use consistent memory */ list_del(&page->page_list); + list_del(&page->avail_page_link); kfree(page); } else pool_free_page(pool, page); @@ -328,9 +337,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; + if (!list_empty(&pool->avail_page_list)) { + page = list_first_entry(&pool->avail_page_list, + struct dma_page, + avail_page_link); + goto ready; } /* pool_alloc_page() might sleep, so temporarily drop &pool->lock */ @@ -343,10 +354,13 @@ 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->avail_page_link, &pool->avail_page_list); ready: page->in_use++; offset = page->offset; page->offset = *(int *)(page->vaddr + offset); + if (page->offset >= pool->allocation) + list_del_init(&page->avail_page_link); retval = offset + page->vaddr; *handle = offset + page->dma; #ifdef DMAPOOL_DEBUG @@ -461,6 +475,10 @@ void dma_pool_free(struct dma_pool *pool memset(vaddr, POOL_POISON_FREED, pool->size); #endif + /* This test checks if the page is already in avail_page_list. */ + if (list_empty(&page->avail_page_link)) + list_add(&page->avail_page_link, &pool->avail_page_list); + page->in_use--; *(int *)vaddr = page->offset; page->offset = offset;