On Wed, Sep 30, 2026 at 4:44 AM Eliot Courtney <[email protected]> wrote:
>
> Add support for reserving of ranges of IDs, with a usage in nova-core
> for channel IDs. This entails adding bindings for the C bitmap
> API for ranges of bits, then users of that in `IdPool`, and finally a
> user of `IdPool` in nova-core, `ChannelIdPool`.
>
> Channel ID tracking is needed for allotting ranges of channel IDs to
> vGPU guests, and later for regular host channel ID reservation.
> nova-core needs allocation of a contiguous sequence of IDs with a
> specific length and sometimes a specific alignment [1].
>
> About the tradeoffs between different data structures:
> - IDA/xarray do not support allocating a contiguous sequence of IDs
> (ida_alloc_range() allocates a single ID within a range, not a contiguous
> sequence).
> - A maple tree works, but is not as good a fit. The ID space is small
> (limited to 2048) and aligned allocation needs an alloc_range()+erase()
> retry
> loop (plus a Mutex around it, or new mas_empty_area() bindings) that
> essentially reimplements bitmap_find_next_zero_area(). See the maple tree
> version at [2]. For 2048 IDs a bitmap is also considerably faster and
> smaller
> [3].
> - The bitmap API natively supports aligned contiguous area allocation
> (bitmap_find_next_zero_area()).
>
> This is based on drm-rust-next and depends on the cv! series [4].
>
> [1]:
> https://lore.kernel.org/all/[email protected]/
> [2]:
> https://lore.kernel.org/all/[email protected]/
> [3]: https://lore.kernel.org/all/[email protected]/
> [4]: https://lore.kernel.org/all/[email protected]/
>
> Signed-off-by: Eliot Courtney <[email protected]>
Applied (the following subset that Alexandre suggested in a sibling
reply) to `rust-next` -- thanks everyone!
> rust: bitmap: use function-level cfg on kunit test
> rust: bitmap: restrict bitmap length to at most i32::MAX
> rust: sizes: add sub-1K size constants
> rust: sizes: implement SizeConstants for Alignment
> rust: bitmap: add contiguous area operations
> rust: id_pool: add contiguous ID reservation
If someone does not want them to be applied for some reason, please shout.
For the second one:
Cc: [email protected]
[ Added a few intra-doc links. Added backticks to C types. Capitalize
tagged comments. - Miguel ]
By the way, I didn't modify the patch for the following, but we should
migrate `id_pool.rs` to the vertical kernel style. Also, before I
forget, we can clean up a few consistency bits in `bitmap.rs` before
we keep extending it (like in one patch here) -- I can copy this to a
"good first issue" or I may just send it:
- Fix the broken intra-doc link for `c_ulong`.
- Add backticks around configs like `CONFIG_RUST_BITMAP_HARDENED`.
- Capitalize tagged comments like `// INVARIANT: ...`.
- Make periods consistent (adding them) at the end of bullet points.
Cheers,
Miguel
