Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation

[Alice Ryhl <aliceryhl@google.com>]

On Wed, Jul 08, 2026 at 04:37:38PM -0400, Yury Norov wrote:
> On Wed, Jul 08, 2026 at 07:33:16AM +0200, Greg KH wrote:
> 
> ...
> 
> > > I asked exactly the same question when Alice and Burak added wrappers
> > > for bitmaps to implement their ID pool. This is the answer:
> > > 
> > >   An alternative route of vendoring an existing Rust bitmap package was
> > >   considered but suboptimal overall. Reusing the C implementation is
> > >   preferable for a basic data structure like bitmaps. It enables Rust
> > >   code to be a lot more similar and predictable with respect to C code
> > >   that uses the same data structures and enables the use of code that
> > >   has been tried-and-tested in the kernel, with the same performance
> > >   characteristics whenever possible.
> > > 
> > > And now it's in a commit message: 11eca92a2caeb
> > > 
> > > They measured the affect of their wrapper on performance, and it appears
> > > to be ~5%. See lib/find_bit_benchmark_rust.rs.
> > 
> > You are comparing the C vs. Rust data structures here, which is not what
> > I am proposing.
> > 
> > Also, is this code being used on a "hot path" like the binder stuff is?
> > 
> > > I didn't see any side-to-side comparison between any native Rust API vs
> > > imported C bitmaps. I'm sure, I asked for that, and I still believe
> > > it's the important piece of data to avoid this back-and-forth type of
> > > discussions. So, Alice, Burak or anybody...
> > 
> > Again, I'm not talking about Rust API vs. imported C bitmaps, I'm asking
> > to use the C structures like maple-tree and idr instead of open-coding
> > logic around the bitmap code.
> 
> I understand your point. I asked both questions: are they sure that bitmap
> is the most optimal data structure for the ID pool, and if so, why not use
> the built-in Rust bitmaps? The answer was: yes, it's the most optimal, and
> using built-in bitmaps is suboptimal overall.

The Rust standard library doesn't really have a bitmap abstraction to
begin with, so if we want to use bitmap then it's either handrolled
bit-manipulation or the C bitmap api.

cc'ing Burak's new email

> > > > > > Why isn't the built-in idr library being used here instead of rolling
> > > > > > your own data structure?
> > > 
> > > Now having more context, the ID pool's primary goal is to allocate
> > > individual IDs, which naturally lays on find_bit() API in C. The
> > > native Rust alternative is considered and found 'suboptimal overall'.
> > 
> > Allocating IDs is a probe() thing, which can be as slow as it wants,
> > right?  Or is this some other hot-path where performance matters?  The
> > patch was not very specific as to the tradeoffs needed.
> 
> I am a bitmaps maintainer, and I want them in Rust to perform equally well.
> The ID pool case was just the first user. Even if bitmap performance is
> not a critical path for ID pool, my role is to make sure that bitmap in
> Rust is implemented well, including the performance part.
> 
> Said that, I recall that bitmaps performance was important for the ID
> pool, and Alice and Burak spent some time optimizing the ID allocation
> path. Particularly, added a logic to avoid allocation of small bitmaps.

Yeah the Binder use-case is not the same as probe(). It's a per-fd data
structure used to give names to kernel objects that userspace is
manipulating, and the mapping is per-process.

Alice