linux-kernel - Re: [PATCH 10/10] dmapool: improve scalability of dma_pool

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <408315d1-9820-65d0-c0a7-cc038bfa9eb1@arm.com>
Date:   Wed, 1 Jun 2022 10:44:29 +0100
From:   Robin Murphy <robin.murphy@....com>
To:     Tony Battersby <tonyb@...ernetics.com>,
        Keith Busch <kbusch@...nel.org>
Cc:     linux-mm@...ck.org, linux-kernel@...r.kernel.org,
        iommu@...ts.linux-foundation.org, kernel-team@...com,
        Matthew Wilcox <willy@...radead.org>,
        Andy Shevchenko <andy.shevchenko@...il.com>,
        Tony Lindgren <tony@...mide.com>
Subject: Re: [PATCH 10/10] dmapool: improve scalability of dma_pool_free

On 2022-05-31 23:10, Tony Battersby wrote:
> On 5/31/22 17:54, Keith Busch wrote:
>> On Tue, May 31, 2022 at 02:23:44PM -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).
>> The improvement should say O(n) to O(log n), right?
> 
> That would be the improvement for a single call to dma_pool_alloc or
> dma_pool_free, but I was going with the improvement for "n" calls
> instead, which is consistent with the improvement for the example in the
> cover letter for mpt3sas.  I would have to look up the convention to be
> sure of the proper notation in a situation like this, but I usually
> think "inserting N items takes N^2 time"; to me it makes less sense to
> say "inserting 1 item takes N time", because the N seems to come out of
> nowhere.

No, n represents the size of the set that the algorithm is inserting 
into (or removing from, searching within, etc.). Hence why constant time 
is represented by O(1), i.e. not involving the variable at all.

Robin.