On Fri, Jul 10, 2026 at 4:21 PM Eliot Courtney <[email protected]> wrote: > > 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]/
If you need to make multiple allocation attemps to handle the alignment requirement, then I don't think maple tree is a good fit for your needs. Alice
