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@nvidia.com/
[2]: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/
[3]: https://lore.kernel.org/all/20260717053241.916441-1-ynorov@nvidia.com/

Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
---
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@nvidia.com

---
Eliot Courtney (4):
      rust: bitmap: use function-level cfg on kunit test
      rust: bitmap: add contiguous area operations
      rust: id_pool: add contiguous area allocation
      gpu: nova-core: add ChannelIdPool

 drivers/gpu/nova-core/gpu.rs         |   2 +
 drivers/gpu/nova-core/gpu/channel.rs | 182 ++++++++++++++++++++++++++
 rust/kernel/bitmap.rs                | 242 +++++++++++++++++++++++++++++++++--
 rust/kernel/id_pool.rs               |  69 ++++++++++
 4 files changed, 481 insertions(+), 14 deletions(-)
---
base-commit: 71d4e7233f235871b13553e504e591ace6b54373
change-id: 20260608-chid-18fa943c6d6c

Best regards,
--  
Eliot Courtney <ecourtney@nvidia.com>

On Thu, Jul 23, 2026 at 05:59:09PM +0900, Eliot Courtney 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.
> 
> [1]: https://lore.kernel.org/all/84bc8bd2-e292-4b84-9580-a1b5df4c5bdc@nvidia.com/
> [2]: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/
> [3]: https://lore.kernel.org/all/20260717053241.916441-1-ynorov@nvidia.com/

If you refer my test, I'd like to make sure you've reviewed it and
tested in your environment. Please send the appropriate tags.

Also, would you like to add it to your series? I can to move it myself,
but I can defer it to you if you prefer.

Thanks,
Yury
 
> Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
> ---
> 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@nvidia.com
> 
> ---
> Eliot Courtney (4):
>       rust: bitmap: use function-level cfg on kunit test
>       rust: bitmap: add contiguous area operations
>       rust: id_pool: add contiguous area allocation
>       gpu: nova-core: add ChannelIdPool
> 
>  drivers/gpu/nova-core/gpu.rs         |   2 +
>  drivers/gpu/nova-core/gpu/channel.rs | 182 ++++++++++++++++++++++++++
>  rust/kernel/bitmap.rs                | 242 +++++++++++++++++++++++++++++++++--
>  rust/kernel/id_pool.rs               |  69 ++++++++++
>  4 files changed, 481 insertions(+), 14 deletions(-)
> ---
> base-commit: 71d4e7233f235871b13553e504e591ace6b54373
> change-id: 20260608-chid-18fa943c6d6c
> 
> Best regards,
> --  
> Eliot Courtney <ecourtney@nvidia.com>