From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 264A4C433F5 for ; Tue, 31 May 2022 21:54:30 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 903F96B0071; Tue, 31 May 2022 17:54:29 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 8DD4B6B0073; Tue, 31 May 2022 17:54:29 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 7F1206B0074; Tue, 31 May 2022 17:54:29 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0014.hostedemail.com [216.40.44.14]) by kanga.kvack.org (Postfix) with ESMTP id 735786B0071 for ; Tue, 31 May 2022 17:54:29 -0400 (EDT) Received: from smtpin11.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay06.hostedemail.com (Postfix) with ESMTP id 3E8283420C for ; Tue, 31 May 2022 21:54:29 +0000 (UTC) X-FDA: 79527392658.11.350C2EA Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf07.hostedemail.com (Postfix) with ESMTP id 74AF34003E for ; Tue, 31 May 2022 21:54:16 +0000 (UTC) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id E5C586131B; Tue, 31 May 2022 21:54:27 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 9F48FC385A9; Tue, 31 May 2022 21:54:26 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1654034067; bh=p1OW3169Xm6Eo04hC32FJFeedrLyv3PKo3DiY4M7gOc=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=gIb1CqARRBC6qSSdyiOWLJrKknzwu45ZhejlZUVs8aK0HhuFvWbQsRBGPsJR86/IF ydAqEZDaqp0qAoApwZ31qSdQweyQnLiq7CMvgF4o2a8zxonxmUVuyiWet0x8kc+dth JcrxCYsUr27twnEjiFxlzj2Myh3Yetj+mvOfsvIJz0NLoKLkRKIy3jcVkx64NXnRpY aROv1sCg7zzz17tttNDeYWua5QNEII+OJN4GKM/I99E4Nh8sNmtxDgB43pV9QKLAnA 0Ba9+Dk451XP8orDqNcpihNf0vtbYaqn24YZvJUKTy/jtSpp2kGfqobjaAiZWtEEfi /l1eOJiXn6Zog== Date: Tue, 31 May 2022 15:54:23 -0600 From: Keith Busch To: Tony Battersby Cc: linux-mm@kvack.org, linux-kernel@vger.kernel.org, iommu@lists.linux-foundation.org, kernel-team@fb.com, Matthew Wilcox , Andy Shevchenko , Robin Murphy , Tony Lindgren Subject: Re: [PATCH 10/10] dmapool: improve scalability of dma_pool_free Message-ID: References: <9b08ab7c-b80b-527d-9adf-7716b0868fbc@cybernetics.com> <801335ba-00f3-12ae-59e0-119d7d8fd8cd@cybernetics.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <801335ba-00f3-12ae-59e0-119d7d8fd8cd@cybernetics.com> X-Rspam-User: Authentication-Results: imf07.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=gIb1CqAR; dmarc=pass (policy=none) header.from=kernel.org; spf=pass (imf07.hostedemail.com: domain of kbusch@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=kbusch@kernel.org X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 74AF34003E X-Stat-Signature: 1fumiuscf6dbwpbdpkhah1s4p8jt98re X-HE-Tag: 1654034056-683921 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 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?