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

["Eliot Courtney" <ecourtney@nvidia.com>]

On Wed Jul 8, 2026 at 2:33 PM JST, Greg KH wrote:
> On Tue, Jul 07, 2026 at 12:31:08PM -0400, Yury Norov wrote:
>> On Tue, Jul 07, 2026 at 04:13:30PM +0200, Greg KH wrote:
>> > On Tue, Jul 07, 2026 at 10:25:27PM +0900, Eliot Courtney wrote:
>> > > On Fri Jul 3, 2026 at 7:31 PM JST, Greg KH wrote:
>> > > > On Fri, Jul 03, 2026 at 07:16:06PM +0900, Eliot Courtney wrote:
>> > > >> Add support for contiguous area allocation. Add a new type,
>> > > >> `UnusedArea`, following the same pattern as `UnusedId`.
>> > > >> 
>> > > >> Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
>> > > >
>> > > > Why isn't the built-in idr library being used here instead of rolling
>> > > > your own data structure?
>> > > >
>> > > > thanks,
>> > > >
>> > > > greg k-h
>> > > 
>> > > For nova-core in this series, we need allocation of a contiguous
>> > > sequence of IDs with a specific length and sometimes a specific
>> > > alignment. IIUC, IDA/xarray do not support that (I checked
>> > > ida_alloc_range and it only allocates a single ID in a range, not a
>> > > contiguous sequence).
>> > > 
>> > > For IdPool before this series, I think it could have used IDA/xarray.
>> > > See [1] where Alice has posted some more context.
>> > > 
>> > > w.r.t. the structure choice, the IDs we need to allocate are channel
>> > > IDs, and the total range is limited to 2048 of them, so IMO bitmaps are
>> > > a better fit than e.g. maple tree.
>> > 
>> > But again, you are having to "roll your own" logic here, please reuse
>> > the data structures we already have in the kernel for this type of
>> > thing.  If a maple tree works, please use it.
>> 
>> 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.

Yeah, I agree that using maple tree avoids piling on more ID allocation
implementations.

Channel ID allocation isn't on a hot path (absolute peak ~100 per
second, on average < 1 per second, AFAICT). 

I prototyped the implementation using maple tree [1]. It has some
awkward points:
- Allocating aligned IDs needs a loop on top of
  MapleTreeAlloc::alloc_range + erase, which essentially replicates the
  logic in `bitmap_find_next_zero_area`
- Since aligned allocation may take multiple tries we still need
  exclusive access in `ChannelIdPool::alloc_area` to ensure an allocated
  but about to be erased non-aligned alloc doesn't make it look like we
  ran out of IDs. Alternatively, can do a try+restart kind of loop
  instead (needs adding bindings for mas_empty_area). [1] is using the
  extra Mutex.
- The alloc_area and Drop path of `ChannelIdPool` now allocates memory.
  I *think* this is okay but it is a consideration.

These tradeoffs weren't obvious to readers because I didn't include
enough context in the patch series (and was going to add actual usage of
the aligned alloc later).

Anyway, maple tree does work for this, so if you prefer I'm happy to go
with it.

Thanks~

[1]: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/