Re: [PATCH v9 0/9] rust: Add support for reserving of ranges of IDs

[Miguel Ojeda]

On Wed, Sep 30, 2026 at 4:44 AM Eliot Courtney <ecourtney@xxxxxxxxxx> 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/84bc8bd2-e292-4b84-9580-a1b5df4c5bdc@xxxxxxxxxx/
> [2]: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@xxxxxxxxxx/
> [3]: https://lore.kernel.org/all/20260717053241.916441-1-ynorov@xxxxxxxxxx/
> [4]: https://lore.kernel.org/all/20260917-cv-v4-0-547ef5727451@xxxxxxxxxx/
>
> Signed-off-by: Eliot Courtney <ecourtney@xxxxxxxxxx>

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: stable@xxxxxxxxxxxxxxx
    [ 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