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

[Brian Johannesmeyer <bjohannesmeyer@gmail.com>]

> 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 ffree 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