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] [thread-next>] [day] [month] [year] [list]

Message-ID: <YpaOj/C1SA8y1VCg@kbusch-mbp.dhcp.thefacebook.com>
Date:   Tue, 31 May 2022 15:54:23 -0600
From:   Keith Busch <kbusch@...nel.org>
To:     Tony Battersby <tonyb@...ernetics.com>
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>,
        Robin Murphy <robin.murphy@....com>,
        Tony Lindgren <tony@...mide.com>
Subject: Re: [PATCH 10/10] dmapool: improve scalability of dma_pool_free

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?