[PATCH v8 00/12] rust: Add support for reserving of ranges of IDs

[Eliot Courtney]

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.

[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/

Signed-off-by: Eliot Courtney <ecourtney@xxxxxxxxxx>
---
Changes in v8:
- Clarify overflow cases in patch #2 (Alex)
- Replace nz! with generalized cv! macro (Gary)
- Add cv! macro to prelude
- Split SizeConstants and adding new constants patch (Alex)
- Move alignment size constants conersions patch (Alex)
- Drop NonZero on IdPool, fix grow_request instead (Alice, Alex)
- Add shrink/grow doctests (Burak)
- Link to v7: https://patch.msgid.link/20260817-chid-v7-0-a5872e64d8f4@xxxxxxxxxx

Changes in v7:
- Add nz! macro for compile time NonZero
- Implement SizeConstants for Alignment + add sub 1k size constants
- Use Alignment constants + nz! in this series
- Add final patch converting existing callers to use Alignment constants
- Rename alloc_area/release_area -> reserve_ids / release_ids
- Link to v6: https://patch.msgid.link/20260813-chid-v6-0-160be5dfb5bd@xxxxxxxxxx

Changes in v6:
- Take a NonZero nbits in `next_zero_area_off`, `set` and `clear` (Yury)
- Remove `UnusedArea`, `IdPool::alloc_area` now allocates directly (Yury)
- Add patch: take a NonZero capacity in `IdPool::with_capacity()`
- Add patch: do not round the capacity up to `BitmapVec::MAX_INLINE_LEN`,
  which also removes the bounds check in `ChannelIdPool::alloc_area`
- Add more testing of Drop for `ChannelIdPool` (Yury)
- Link to v5: https://patch.msgid.link/20260812-chid-v5-0-6c767770b3f4@xxxxxxxxxx

Changes in v5:
- `bitmap_assert!` i32::MAX length for Bitmap::from_raw* (Yury)
- Only run overflow check on 32-bit (Yury)
- Link to v4: https://patch.msgid.link/20260810-chid-v4-0-c9f206fdcb97@xxxxxxxxxx

Changes in v4:
- Add `next_zero_area_off` to match C code (Yury)
- Replace overflow checks to match C code in bitmap-for-next.
- Tighten `Bitmap` unsafe contract to disallow Bitmaps larger than i32::MAX
- Link to v3: https://patch.msgid.link/20260729-chid-v3-0-20cc08032bbc@xxxxxxxxxx

Changes in v3:
- Use `Alignment` type in id_pool and bitmap (Alice)
- Remove hang check on the basis that it's extraordinarily rare.
- Link to v2: https://patch.msgid.link/20260723-chid-v2-0-c35e5e9fb3d9@xxxxxxxxxx

Changes in v2:
- Collected Alice's Reviewed-by on patch 1.
- Address Yury's comments w.r.t. using __bitmap_set etc directly.
- Address Yury's comments w.r.t. following the C names
- Additionally check for an overflow case that causes a hang
- Added more info to cover letter + patch 4 w.r.t. channel ID allottment
  requirements
- Add align parameter to ChannelIdPool::alloc_area() plus an aligned
  allocation test
- Add missing INVARIANT comment when constructing UnusedArea
- Link to v1:
  https://patch.msgid.link/20260703-chid-v1-0-84fe8259e46e@xxxxxxxxxx

---
Eliot Courtney (12):
      rust: bitmap: use function-level cfg on kunit test
      rust: bitmap: restrict bitmap length to at most i32::MAX
      rust: num: add cv! macro to create values from constant expressions
      rust: prelude: add `num::cv`
      rust: use cv! to build Bounded values from constants
      rust: sizes: add sub-1K size constants
      rust: sizes: implement SizeConstants for Alignment
      rust: use Alignment size constants
      rust: bitmap: add contiguous area operations
      rust: id_pool: add contiguous ID reservation
      rust: id_pool: do not round capacity up to BitmapVec::MAX_INLINE_LEN
      gpu: nova-core: add ChannelIdPool

 drivers/gpu/nova-core/fb.rs           |  10 +-
 drivers/gpu/nova-core/fb/hal/gb100.rs |   3 +-
 drivers/gpu/nova-core/fsp.rs          |   4 +-
 drivers/gpu/nova-core/gpu.rs          |   2 +
 drivers/gpu/nova-core/gpu/channel.rs  | 198 ++++++++++++++++++++
 drivers/gpu/nova-core/gsp/fw.rs       |  12 +-
 drivers/gpu/nova-core/num.rs          |   3 +-
 drivers/gpu/nova-core/vbios.rs        |   7 +-
 rust/kernel/bitfield.rs               |   8 +-
 rust/kernel/bitmap.rs                 | 336 ++++++++++++++++++++++++++++++----
 rust/kernel/gpu/buddy.rs              |  26 +--
 rust/kernel/id_pool.rs                |  70 ++++++-
 rust/kernel/io.rs                     |   5 +-
 rust/kernel/num.rs                    |  88 +++++++++
 rust/kernel/num/bounded.rs            |  21 ++-
 rust/kernel/prelude.rs                |   1 +
 rust/kernel/ptr.rs                    |  13 ++
 rust/kernel/sizes.rs                  |  47 ++++-
 18 files changed, 768 insertions(+), 86 deletions(-)
---
base-commit: 4c9ba407018e8deb06dbc643112bac8f40404f95
change-id: 20260608-chid-18fa943c6d6c

Best regards,
--  
Eliot Courtney <ecourtney@xxxxxxxxxx>