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 72240D743F3 for ; Wed, 20 Nov 2024 23:46:57 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 07C246B0085; Wed, 20 Nov 2024 18:46:57 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 035CA6B0088; Wed, 20 Nov 2024 18:46:56 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E0DA16B0089; Wed, 20 Nov 2024 18:46:56 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id BECF56B0085 for ; Wed, 20 Nov 2024 18:46:56 -0500 (EST) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 627F08019F for ; Wed, 20 Nov 2024 23:46:56 +0000 (UTC) X-FDA: 82808108880.19.F91CD71 Received: from mail-ed1-f43.google.com (mail-ed1-f43.google.com [209.85.208.43]) by imf06.hostedemail.com (Postfix) with ESMTP id A93F6180015 for ; Wed, 20 Nov 2024 23:46:17 +0000 (UTC) Authentication-Results: imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=IOFqeMZj; spf=pass (imf06.hostedemail.com: domain of bjohannesmeyer@gmail.com designates 209.85.208.43 as permitted sender) smtp.mailfrom=bjohannesmeyer@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1732146322; 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:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=ZX6Gf+AddKQPYyrL3mtvV54D8Um1RsLjA/IT9zLDw0M=; b=XmsI4OJ/XvnAyuJpo+QG3hnHzQCjfKvVqUDRgYqxl2wJ4fsJYFNb0+YzBvIqVDfVK5Bn+C 1jvPOUeMM7tPvYOy9csLKIBylnl30Sj20gDg1uwDv2g+viCp1kK28+lLhb0sOepZaozlSm HCcqWKkvvXw/ntX0vx2odemSwzYi24s= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1732146322; a=rsa-sha256; cv=none; b=haDyf/6v61O9m3c/aLX8bzyDBQgAL5Pc4T1Yf8yk+Y9s9aDKz/bRWElIdkM5cjGphgLN79 u6qaAoDqDibMwEYxZxkqtuzJHjlWr+ZF2mcsiHV6XiYwQAfBELXZZsCFilS9CUHdXsejh9 zb11nKZowBADrCuXGaDjwHAiy9dFuVg= ARC-Authentication-Results: i=1; imf06.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=IOFqeMZj; spf=pass (imf06.hostedemail.com: domain of bjohannesmeyer@gmail.com designates 209.85.208.43 as permitted sender) smtp.mailfrom=bjohannesmeyer@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ed1-f43.google.com with SMTP id 4fb4d7f45d1cf-5cfbeed072dso352778a12.3 for ; Wed, 20 Nov 2024 15:46:54 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1732146413; x=1732751213; darn=kvack.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=ZX6Gf+AddKQPYyrL3mtvV54D8Um1RsLjA/IT9zLDw0M=; b=IOFqeMZjTqK7qod8xwO1NQb+iTIeO6S/yAAzxenMFpFdUf3haZhzHxVTI0UlGzAooE mYtFt1i1gaHk6+3e+S4WPGLDSPHSrWlV+zPF3oEkrj/VlHnmLnKhNU8+2lotM/034hHP cV8zfL8biMJKOUgxMpKlmBnFKgghx3K6x3s8hI+wf2fkVz2srIODIg3jqKh5LS5e9Lt1 +Qn2ehQHysHXUDNoW1ArqUSEWPN9O9zazlj84+qmbIEr4IJxXWUK4jBsx7wcKcfa+DGt m1VWy4oZEiNgl5qFnrRlL8B+QWBzlynwkd6jmCCF98OUqtyesTel5+cZ1S/id03NVz8E Ff3w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1732146413; x=1732751213; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=ZX6Gf+AddKQPYyrL3mtvV54D8Um1RsLjA/IT9zLDw0M=; b=n23OWvSrmWq/S0TyK24e0wv5Jk41ozJdPQG7oS2tKslv3yr5LnMIfqiwIOQ1OEIAdf gAOHmf6+ZH1Dmt3mvnlslvtG5ApiZ0GoFVUVe0FJll8G26lSeYdDcfuJ7Rx+avX/lbTG iqLn2VCPR+hN8FZxGaZPZbwmiTfFcwNF2lscWvBdp/3Ct6zo7pLHQ800ciKUpZdJ5szC 2R4vc8z2rGD/4oj6JIV2J4sd6kelSxDCWUy6Nxui2m1HV6VRMAnGjGwRO0Kh2YUjjQH/ QIRqPBA7UebxjuxefcTwRHaB80oipGTWzRsz/gLjR9iwuWVFMWxaFdNSbz9qL0+ILnV6 Eu9A== X-Forwarded-Encrypted: i=1; AJvYcCV9RXyLjckZWkG0Tpu+rCRKQPigtfdlSZPCDTRF8ebiBwiiGPd4mX+02T83OW4fhEYVs8Uq9j8QHQ==@kvack.org X-Gm-Message-State: AOJu0YwmUAFolK1r+Y1Q6CMINJsa4ambB7pXj/XdcLO0hx2qYMuw2vxD oxL4wAQZrKGDgmEdUk2Q/e5Zh3lcB7wPWhDDaSrnlXBC390QHdEC1v7h6IYWkkJv8fr/uwzuh6b J5hvyEkGh7ViIsqvYBH8iJ+B8jRk= X-Google-Smtp-Source: AGHT+IHxcfthi1A3D9ujn2fAxpaofW5+bukINivpXFmWyT9+hamEemQhOI4b+abCDV00kQZ4CJ9RBEv2x9OE9Gh3udk= X-Received: by 2002:a17:907:841:b0:a9e:b0a3:db75 with SMTP id a640c23a62f3a-aa4dd59f9c1mr391988666b.35.1732146412734; Wed, 20 Nov 2024 15:46:52 -0800 (PST) MIME-Version: 1.0 References: <20241119205529.3871048-1-bjohannesmeyer@gmail.com> <20241119205529.3871048-2-bjohannesmeyer@gmail.com> In-Reply-To: From: Brian Johannesmeyer Date: Wed, 20 Nov 2024 16:46:40 -0700 Message-ID: Subject: Re: [RFC v2 1/2] dmapool: Move pool metadata into non-DMA memory To: Christoph Hellwig Cc: 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 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Rspamd-Server: rspam10 X-Stat-Signature: fzctbmkyykmp5ic16gaxhqckgxos9bi8 X-Rspamd-Queue-Id: A93F6180015 X-Rspam-User: X-HE-Tag: 1732146377-665356 X-HE-Meta: U2FsdGVkX1/CjE9UW56U8mgOIaSJzh9In+F+tTKfzErvDQ3aQIaZ+NCBXZryeCWYclUactcSduLOU4KbI9m2QvIhjwPc5ba/vlxeprNADI8eOAb4tZv9EJW/sBTwTdCKrc6jNB5C255wg+u1hoxi1QlPuM1WTvLnboXPgk+uimGoxaWNAecKxujGXdHZXJU+dEbdoz9g0aeEbBEUroKVkPclm3s9znkClI5FnKW6hHeMxxxDqajFrUTxd0NbN8peGPYr7iN67bEltXAJ2CElWCbzUBRL4qa3CYr7nZcZGSomrxCfOCOZarhkYCy5Jl5PcB8B1oZicaJooozhRgVdb2VsOp6G7VwPRc8UfgNkW1jxrH0QiK2MGTX0yoaJBSBHWe39dODhLC2Tw2Zm5CrztqJB0nG66m+8+uGpNE2U6c0baS8sF8QwwcnA6Llnwwr+xsswDfUwDaOTTnKVK6aO5wAsTcEo/9KN73q9odhFX7sHUcJQgqmVoOl5zzHQ4KUnhdPpSpFRZP2WwsANM1CxyG4yXQU/ODYnXlECJ2LUTCWR7rvg+KyvkctUlY65sU1NKPJfGlt4qDhn+NdJ2MVmv88WFlASnvRn2iOhNzXlLt4T+KvdNvCfOgZZTNk2o3HY5z9h/Sd7FEuSfi/XkNPcIPi70nlXlQL5pbX71rkcagRS/oaBQ98OsSiyTzyOJJXJ5kEWzVx3jhG9GccC5C5z9SxhV6zSNLa3jfR1B2bCKAdEDFRGSLSvLPXnrfV4sUGs9N2AsqfUFqptb5pbKvajOfVFfX6J2B+tXru9b14yrlUnbxKHfQl0GkNeL9Z7B4sjp0V8m58auWHVFtlktDrgKaGqYw0NYBXCbCLMX4BklId5usPx4+asMSSj2rh5DAGecdYMOOsZ5j8EUiMP+jKbgykQBSBnTnc4XrK1lyH0zno3LkuAyHwOCHR23zWOyFGleLVvxxN7L/IhnXpMRSA QEUmg+JR 4EXGHtJQdskD/yPxXT4bMV38tAsOWG+RyzVYkyD1S2Ptky+PTsqQIxZZzIc5pKkdbbU8/7ty+/JLjFZdsPppovj2TePsaHBDpeA4na7IB1zrvH6mXyiDEc4K59y2dzlbslfZvD5XDWCBQSO5fMd229Vu2YqihqvmlleuB3+9W9jXcfLeedIWD9aGZl9f2/YJYdTnGx4Qk75TnuRsy1IGDiRYPSmHnRVfLC7p1tBlfybf0LAntRvTcHQETL0Z1Ff5bVqB5jm6P7+rtnkkGdXAzzeRGrxFwoI6uCx87717PT3ri/MeawL3r5OFuabLeABAQyHMw X-Bogosity: Ham, tests=bogofilter, spamicity=0.000029, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: > Given that you now need an array of the blocks anyway, it might make > sense to switch from a linked list to a bitmap for tracking free state, > which would be a lot more efficient as you only need a bit per block > as tracking overhead instead of a two pointers and a dma_addr_t. > > e.g. do a find_first_zero_bit() to find the =EF=AC=80ree slot, then calcu= late > the dma_addr and virt address by simple offseting into the dma_page > ones with bitnr * pool->size. 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. Here are the performance results, with DMAPOOL_DEBUG disabled. The first two sets of numbers are the same as my latest response in the other thread (i.e., [RFC v2 0/2]), and the last set of numbers is with the bitmap approach applied: **Without no patches applied:** ``` dmapool test: size:16 align:16 blocks:8192 time:11860 dmapool test: size:64 align:64 blocks:8192 time:11951 dmapool test: size:256 align:256 blocks:8192 time:12287 dmapool test: size:1024 align:1024 blocks:2048 time:3134 dmapool test: size:4096 align:4096 blocks:1024 time:1686 dmapool test: size:68 align:32 blocks:8192 time:12050 ``` **With the submitted patches applied:** ``` dmapool test: size:16 align:16 blocks:8192 time:34432 dmapool test: size:64 align:64 blocks:8192 time:62262 dmapool test: size:256 align:256 blocks:8192 time:238137 dmapool test: size:1024 align:1024 blocks:2048 time:61386 dmapool test: size:4096 align:4096 blocks:1024 time:75342 dmapool test: size:68 align:32 blocks:8192 time:88243 ``` **With the submitted patches applied AND using a bitmap approach:** ``` dmapool test: size:16 align:16 blocks:8192 time:82733 dmapool test: size:64 align:64 blocks:8192 time:198460 dmapool test: size:256 align:256 blocks:8192 time:710316 dmapool test: size:1024 align:1024 blocks:2048 time:177801 dmapool test: size:4096 align:4096 blocks:1024 time:192297 dmapool test: size:68 align:32 blocks:8192 time:274931 ``` 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. If you have ideas for mitigating this runtime overhead, I=E2=80=99d be happ= y to explore them further. Thanks, Brian Johannesmeyer