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 <[email protected]> >> > > > >> > > > 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/[email protected]/
