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/[email protected]/ [2]: https://lore.kernel.org/all/[email protected]/ [3]: https://lore.kernel.org/all/[email protected]/ Signed-off-by: Eliot Courtney <[email protected]> --- 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/[email protected] 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/[email protected] 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/[email protected] 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/[email protected] 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/[email protected] 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/[email protected] --- Eliot Courtney (10): rust: bitmap: use function-level cfg on kunit test rust: bitmap: restrict bitmap length to at most i32::MAX rust: num: add nz! macro for compile time NonZero values rust: sizes: implement SizeConstants for Alignment rust: bitmap: add contiguous area operations rust: id_pool: take a NonZero capacity in with_capacity 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 rust: use Alignment size constants 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 | 201 ++++++++++++++++++++ drivers/gpu/nova-core/gsp/fw.rs | 12 +- drivers/gpu/nova-core/vbios.rs | 7 +- rust/kernel/bitmap.rs | 335 ++++++++++++++++++++++++++++++---- rust/kernel/gpu/buddy.rs | 26 +-- rust/kernel/id_pool.rs | 53 ++++-- rust/kernel/io.rs | 5 +- rust/kernel/num.rs | 23 +++ rust/kernel/sizes.rs | 47 ++++- 13 files changed, 644 insertions(+), 84 deletions(-) --- base-commit: 4c9ba407018e8deb06dbc643112bac8f40404f95 change-id: 20260608-chid-18fa943c6d6c Best regards, -- Eliot Courtney <[email protected]>
