linux-hardening - Re: [RFC v2 1/2] dmapool: Move pool metadata into non-DMA memory

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: <CAOZ5it2KXhBy0=ktgjAHMs8ut-Go2OXOt_vnWFiUBV7uBBH5HQ@mail.gmail.com>
Date: Wed, 20 Nov 2024 16:46:40 -0700
From: Brian Johannesmeyer <bjohannesmeyer@...il.com>
To: Christoph Hellwig <hch@...radead.org>
Cc: Andrew Morton <akpm@...ux-foundation.org>, linux-mm@...ck.org, 
	linux-kernel@...r.kernel.org, linux-hardening@...r.kernel.org, 
	Raphael Isemann <teemperor@...il.com>, Cristiano Giuffrida <giuffrida@...vu.nl>, Herbert Bos <h.j.bos@...nl>, 
	Greg KH <gregkh@...uxfoundation.org>, Keith Busch <kbusch@...nel.org>
Subject: Re: [RFC v2 1/2] dmapool: Move pool metadata into non-DMA memory

> 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 ﬀree slot, then calculate
> 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’d be happy
to explore them further.

Thanks,

Brian Johannesmeyer