Re: [PATCH v8 5/5] rust: add dynamic ID pool abstraction for bitmap

[Jann Horn]

On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@xxxxxxxxxx> wrote:
> This is a port of the Binder data structure introduced in commit
> 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> Rust.

Stupid high-level side comment:

That commit looks like it changed a simple linear rbtree scan (which
is O(n) with slow steps) into a bitmap thing. A more elegant option
might have been to use an augmented rbtree, reducing the O(n) rbtree
scan to an O(log n) rbtree lookup, just like how finding a free area
used to work in MM code... That would let you drop that ID pool bitmap
entirely. But I guess actually wiring up an augmented rbtree into Rust
would be very annoying too.