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 0170CD75BB9 for ; Thu, 21 Nov 2024 05:03:09 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 6E18C6B007B; Thu, 21 Nov 2024 00:03:09 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 66A296B0083; Thu, 21 Nov 2024 00:03:09 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 50ACD6B0085; Thu, 21 Nov 2024 00:03:09 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id 340DC6B007B for ; Thu, 21 Nov 2024 00:03:09 -0500 (EST) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 5C1FD140B49 for ; Thu, 21 Nov 2024 05:03:08 +0000 (UTC) X-FDA: 82808905368.07.0859800 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) by imf21.hostedemail.com (Postfix) with ESMTP id ACAB21C0010 for ; Thu, 21 Nov 2024 05:01:26 +0000 (UTC) Authentication-Results: imf21.hostedemail.com; dkim=pass header.d=infradead.org header.s=bombadil.20210309 header.b=nR94WtE3; spf=none (imf21.hostedemail.com: domain of BATV+4756fcbc3b7b416a25ba+7760+infradead.org+hch@bombadil.srs.infradead.org has no SPF policy when checking 198.137.202.133) smtp.mailfrom=BATV+4756fcbc3b7b416a25ba+7760+infradead.org+hch@bombadil.srs.infradead.org; dmarc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1732165294; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=xWuHiVLKYZ8tLIpiuo5fwrJ4cJ7mDK/CegkNy5jzzAY=; b=8RRtlGrBZMrUdazw7eW2oVrRWoOk2SCp3nxyXcv5sdrYE1wB2zk8I0X6bBGehuqdVdq3KT k8P+j1FyRMUNh8iY07RbZx78XiAbpTdCli01GBCk3FnoUasEXvoChVkV8fg+L7WOSduEUb IYy5m7u/5UWZDfZdo40xfwW2+TUcmU0= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1732165294; a=rsa-sha256; cv=none; b=HHYDobdoo6TX89xxaBXvz8C+UMxSgfHfZr0flXZkp0XcpxDvVqXzjCwHRbOhGksPpS42kE NKEHje/uLkBjad3amIPRCg8BqJopw9f8F+sBXfZccxX1sWail7Q05auHyABMFmQls5x2/l cOHaFhkJTR6CoGRY4yQPxRAaXWuT1Kk= ARC-Authentication-Results: i=1; imf21.hostedemail.com; dkim=pass header.d=infradead.org header.s=bombadil.20210309 header.b=nR94WtE3; spf=none (imf21.hostedemail.com: domain of BATV+4756fcbc3b7b416a25ba+7760+infradead.org+hch@bombadil.srs.infradead.org has no SPF policy when checking 198.137.202.133) smtp.mailfrom=BATV+4756fcbc3b7b416a25ba+7760+infradead.org+hch@bombadil.srs.infradead.org; dmarc=none DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20210309; h=In-Reply-To:Content-Type:MIME-Version :References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=xWuHiVLKYZ8tLIpiuo5fwrJ4cJ7mDK/CegkNy5jzzAY=; b=nR94WtE3N8RXOXgMZorAw9x8Bd zzwfDHLqNP660Vy62RsDnUQ4akzNYdSR2b9Oen5nKJLGR+5r3sRwJ3TMyQ+8OM2Kz64Lh2/H5E9T6 7esTWQ2TCmvRpqfHSmL8FmwzaFIOMj1LfNj4Y8QcU5I/1bL0BIVeDzveRb+QsbloxJyMgOaET57CC 0jnkcgvmeTsmkJ070u0yeFYDjQWlJX78QuhyipwQIaNMK02CCjvNKiaCEeP4E0F56NpB/AGy59kuY Qn5VWejICH1tvhhQIB5utY3tD2QAdb3tFfKWnBUJNlTowfYB8NNPduStYmNrK2IaqDQ+AiWxAA6Ee gL11oH1Q==; Received: from hch by bombadil.infradead.org with local (Exim 4.98 #2 (Red Hat Linux)) id 1tDzLM-0000000Gq5N-0NKg; Thu, 21 Nov 2024 05:03:04 +0000 Date: Wed, 20 Nov 2024 21:03:04 -0800 From: Christoph Hellwig To: Brian Johannesmeyer Cc: Christoph Hellwig , Andrew Morton , linux-mm@kvack.org, linux-kernel@vger.kernel.org, linux-hardening@vger.kernel.org, Raphael Isemann , Cristiano Giuffrida , Herbert Bos , Greg KH , Keith Busch Subject: Re: [RFC v2 1/2] dmapool: Move pool metadata into non-DMA memory Message-ID: References: <20241119205529.3871048-1-bjohannesmeyer@gmail.com> <20241119205529.3871048-2-bjohannesmeyer@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: X-SRS-Rewrite: SMTP reverse-path rewritten from by bombadil.infradead.org. See http://www.infradead.org/rpr.html X-Rspamd-Server: rspam10 X-Stat-Signature: ksskgpd7mya663xffkh4fzy9u4iytpuj X-Rspamd-Queue-Id: ACAB21C0010 X-Rspam-User: X-HE-Tag: 1732165286-987574 X-HE-Meta: U2FsdGVkX1/i1daM7qrymdAXJY5p5u3ZC469wZ3I/fddzkKp0DQE8/raotmodX1gUwhdA6f3DW8RJxWdK+4zsaXak0JorAVBb2YXmlqEAiPsjDDlDDkNWFIbro8hqfg/pZs7o7OaUrhhEQ8XxMrwQqm8BVNd3wonnL1Z5p05B0zvuqEFnybeMJXSuLoNZiOnvDlqDKWonZr3o6QehxyCDko5Cjd/w5X4h64j+gLqMXhC06YxaqzA6DYuKSaPw6nEWVvuMXtN3pbobURn5cjDSfgOim4uBgOZJhzvxAFmIsnQRpZp4ZCLcsvKvXfQtD2j3BqubVmf1ssyvj99nK4ORl0OJRVVB3I9DKRMFxZyrMTCAGj+HefgJv60HakK1hSHoKAqgej+7EeMifV/TaRQVAj+voTmQ+bDrpYj8U05wqDKkpQqIpDhvxjX53Nr6S/nm7K6Fl7DgRCwAsfOMT7gyj4vFFJ4K1wYeWmIw9ZxgTHP8x/m/0kIT9kQDMM6R5+aeEsNJnRXHKNbUR5ufHmpEeZ8BoVX1ML127dw03xLgRKt+ImcztKR7pyEexlnzhtVbClZVC4QecOfSI/eqz8lPbIqX8RxBNkpxC3l2FDgCJ2dO5grZkZSAcdMn9T8Ezqy5BkU1Yy4+ia6qLP8N8bwY5KoeozWgY57CKvYdDzLmFMh8r38Riq2333On8umZh1Pdg67fvFZi5KeZNkwRxWS9KeSe3qiVi0llam1m5dpSR+lMtL1Ax6oa9uo96/jcVPKv8DI2egepVxlXxs/usIhbrxn5dfhyO4hhtWR/Lhw7u7NFiE0/X6dAX0O1N75B5nvnxo120G00RTWqTW+8PlGN7mBeYb4lU+UYAII8hplwbrVqPY83XZVW/k0ZQETdfGZNJnESLZ5XsZcXGcqJWQb1SuFQWbXTFd7j5AToe/cmLyIWohVXipiUDn4GL7Oc3YtV6TVZ8lhWBNgOHXlkym tW0eIxeS 6Zw4oUt6Osh2EaacPboaBIk+eOMIywLNG5jIiak44cBLoQnixDALXxQe17a/MHBbIL3EKKAAxcYiUejwjGqoSEamvLw5plopTa5gfJTxEf2+ncCyLRpJpwZB5Xk0AXyBrowfCdnbBdilRkqT7qXsG0jF36q0D1JfvCbOfVvazHWucu09PQcKV0pmqHE7Q7YzSFxAurEyttKWiARDpCnFUGV+ueXsr2aEngAPTsgmY6w1Y8i2VyB/JwQc+NtU3Kb0SlnaR27gOGOjdDI0t0XEjB/nvH3k+f7r4zKjsJb0DgQ+qvrLUOsC7EPWcfwVYMIEmH+DNPkdv02+3PjjCWhtzWRyA7m4ceWb23A2RH7vt6qc3MR02nVEvatGtQEar4Bch7nzhzyqKeFmlroor0vraoBwnhbDnIiWxYYInqHfBcuA3K48Zs/SaV+ZwfryfzR6qgtAdZdX1uWg+Q/wRsVaJo4qIXYLVZqHOxxgo 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: List-Subscribe: List-Unsubscribe: On Wed, Nov 20, 2024 at 04:46:40PM -0700, Brian Johannesmeyer wrote: > Thank you for the suggestion. I hacked together a bitmap-based > approach as you proposed, and while it does improve memory efficiency > by reducing the per-block metadata overhead, it unfortunately appears > to significantly impact the runtime performance. > > My guess as to why: The current linked list implementation allows us > to find the next free block in constant time (`O(1)`) by directly > dereferencing `pool->next_block`, and then following the `next_block` > pointers for subsequent free blocks. In contrast, the bitmap approach > requires iterating over all pages in `page->page_list` and, for each > page, iterating through its bitmap to find the first zero bit. This > results in a worst-case complexity of `O(n * b)`, where `n` is the > number of pages and `b` is the number of bits in each page's bitmap. Indeed. You'd probably need to split the linkage of the pages into a list of those that have free blocks and those that don't as a minimum. Can you share your current version?