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

[Boqun Feng]

On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> 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

I think RBTree::cursor_lower_bound() [1] does exactly what you said

[1]: https://rust.docs.kernel.org/kernel/rbtree/struct.RBTree.html#method.cursor_lower_bound

Regards,
Boqun

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