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

[Jann Horn]

On Tue, May 20, 2025 at 1:12 AM Alice Ryhl <aliceryhl@xxxxxxxxxx> wrote:
> On Mon, May 19, 2025 at 3:51 PM Jann Horn <jannh@xxxxxxxxxx> 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
> > 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.
>
> If we're talking approaches to avoid the bitmap entirely, it would
> probably be easier to replace the rb tree with xarray than to use an
> augmented one.

Ah, yeah, maybe. I'm not familiar enough with xarray to know how
annoying it would be to insert stuff in an xarray that you reach
through a spinlock, which seems to be the requirement that made the
API for the bitmap interface so complicated if I understand
correctly...