rust: Add support for reserving of ranges of IDs
Subsystems (7)
cover rust: Add support for reserving of ranges of IDs
Add support for reserving of ranges of IDs, with a usage in nova-core for channel IDs. This entails adding the helpers+users of the C bitmap API for ranges of bits, then users of that in IdPool, and finally a user of IdPool in nova-core, ChannelIdPool.
This is based on drm-rust-next.
---
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 | 134 +++++++++++++++++++ rust/helpers/bitmap.c | 22 ++++ rust/kernel/bitmap.rs | 244 +++++++++++++++++++++++++++++++++-- rust/kernel/id_pool.rs | 68 ++++++++++ 5 files changed, 456 insertions(+), 14 deletions(-)
---
base-commit: a73a398a68ca9b9e5116a617562471f16b8310c4
change-id: 20260608-chid-18fa943c6d6c
Best regards,
Signature · 1 line
Eliot Courtney <[email protected]>
PATCH 1/4 rust: bitmap: use function-level cfg on kunit test
Since commit c652dc44192d ("rust: kunit: allow cfg on tests"), we no longer need this workaround.
--- rust/kernel/bitmap.rs | 25 +++++++++++-------------- 1 file changed, 11 insertions(+), 14 deletions(-)
rust/kernel/bitmap.rs +11 -14
@@ -572,24 +572,21 @@ fn bitmap_set_clear_find() -> Result<(), AllocError> { }#[test] +#[cfg(not( CONFIG_RUST_BITMAP_HARDENED ))] fn owned_bitmap_out_of_bounds () ->Result <(),AllocError > { -// TODO: Kunit #[test]s do not support `cfg` yet, -// so we add it here in the body. -#[cfg(not( CONFIG_RUST_BITMAP_HARDENED ))] - { -let mut b =BitmapVec ::new (128 ,GFP_KERNEL )?; - b.set_bit (2048 ); - b.set_bit_atomic (2048 ); - b.clear_bit (2048 ); - b.clear_bit_atomic (2048 ); -assert_eq! (None , b.next_bit (2048 )); -assert_eq! (None , b.next_zero_bit (2048 )); -assert_eq! (None , b.last_bit ()); - } +let mut b =BitmapVec ::new (128 ,GFP_KERNEL )?; + + b.set_bit (2048 ); + b.set_bit_atomic (2048 ); + b.clear_bit (2048 ); + b.clear_bit_atomic (2048 ); +assert_eq! (None , b.next_bit (2048 )); +assert_eq! (None , b.next_zero_bit (2048 )); +assert_eq! (None , b.last_bit ());Ok (()) } -// TODO: uncomment once kunit supports [should_panic] and `cfg`. +// TODO: uncomment once kunit supports `#[should_panic]`. // #[cfg(CONFIG_RUST_BITMAP_HARDENED)] // #[test] // #[should_panic]
Signature · 1 line
2.54.0
Re: [PATCH 1/4] rust: bitmap: use function-level cfg on kunit test
Quoted 5 lines · Eliot Courtney
Since commit
c652dc44192d("rust: kunit: allowcfgontests"), we no longer need this workaround.Signed-off-by Eliot Courtney <[email protected]>
PATCH 2/4 rust: bitmap: add contiguous area operations
In reply to Eliot CourtneyAdd bindings and helpers for area operations on bitmaps. Each one is made safe by adding some extra checks compared to the underlying C code (for example, checking bounds) and with additional checks to catch likely erroneous usage if CONFIG_RUST_BITMAP_HARDENED is on.
The C code uses signed integers for some parameters, for example the length for __bitmap_set, so bounds check against i32::MAX. We can't rely on BitmapVec::MAX_LEN because Bitmap may not necessarily be backed by BitmapVec. There's also a few cases where a non power of two minus one align_mask can cause an infinite loop in the C code (can happen on overflow), so check for that.
Add tests demonstrating the edge cases.
--- rust/helpers/bitmap.c | 22 +++++ rust/kernel/bitmap.rs | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 241 insertions(+)
rust/helpers/bitmap.c +22 -0
@@ -8,3 +8,25 @@ void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long * {bitmap_copy_and_extend (to, from, count, size); } + +__rust_helper +unsigned long rust_helper_bitmap_find_next_zero_area (unsigned long *map, +unsigned long size, +unsigned long start, +unsigned int nr, +unsigned long align_mask) +{ +return bitmap_find_next_zero_area (map, size, start, nr, align_mask); +} + +__rust_helper +void rust_helper_bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) +{ +bitmap_set (map, start, nbits); +} + +__rust_helper +void rust_helper_bitmap_clear(unsigned long *map, unsigned int start, unsigned int nbits) +{ +bitmap_clear (map, start, nbits); +}
rust/kernel/bitmap.rs +219 -0
229 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH 2/4] rust: bitmap: add contiguous area operations
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Pre-existing issues:
- [High] Integer truncation in Bitmap::copy_and_extend leading to out-of-bounds memset in C. --
commit 19918f0914fec684f788000700e6deb8bdb878e0
Author: Eliot Courtney <[email protected]>
rust: bitmap: add contiguous area operations
This patch adds bindings and helpers for area operations on bitmaps. It makes each operation safe by adding extra bounds checks compared to the underlying C code. Additional checks are included to catch likely erroneous usage when CONFIG_RUST_BITMAP_HARDENED is enabled.
Quoted 4 lines
rust/kernel/bitmap.rs +0
-0
[ ... ]
Quoted 4 lines
rust/kernel/bitmap.rs +0
-0@@ -497,6 +497,129 @@ pub fn next_zero_bit(&self, start: usize) -> Option<usize> {Some (index) } }
[ ... ]
rust/kernel/bitmap.rs pub fn next_zero_bit(&self, start: usize) -> Option<usize> { · line 590
Quoted 6 lines
rust/kernel/bitmap.rs +6
-0+#[inline] +pub fn set_area (&mut self, start:usize , nbits:usize ) { +bitmap_assert_return! ( + start + .checked_add (nbits) + .is_some_and (|end| end <= self.len () && end <=i32 ::MAX as usize ),
[Severity: High]
This isn't a bug introduced by this patch, but given your note about bounds checking and 32-bit limits, I noticed a pre-existing issue in Bitmap::copy_and_extend() that might need similar treatment.
rust/kernel/bitmap.rs:Bitmap::copy_and_extend() {
...
pub fn copy_and_extend(&mut self, src: &Bitmap) {
let len = core::cmp::min(src.len(), self.len());
// SAFETY: access to self and src is within bounds.
unsafe {
bindings::bitmap_copy_and_extend(
self.as_mut_ptr(),
src.as_ptr(),
len as u32,
self.len() as u32,
)
};
}
}Can this lead to an out-of-bounds memset in C?
A Bitmap can be created from a raw pointer using Bitmap::from_raw() without u32::MAX length restrictions. If self.len() exceeds u32::MAX on 64-bit systems, the self.len() as u32 cast will silently truncate the length.
If src.len() is smaller than the full length but larger than the truncated length, count will be greater than size when passed to the C function bitmap_copy_and_extend().
The C function calculates the byte delta for memset as:bitmap_size(size) - copy * sizeof(long)
With a truncated size, this would subtract a larger byte count from a smaller byte count, underflowing to a huge size_t value. Could this cause a massive out-of-bounds write and kernel panic?
Quoted 8 lines
rust/kernel/bitmap.rs +8
-0+ "Area `start..start + nbits` ({}..{}) must be within bounds {}", + start, + start.saturating_add(nbits), + self.len() + ); +// SAFETY: The area `start..start + nbits` is within bounds. +unsafe { bindings::bitmap_set (self.as_mut_ptr (), startas u32 , nbitsas u32 ) }; + }
[ ... ]
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Re: [PATCH 2/4] rust: bitmap: add contiguous area operations
In reply to Eliot CourtneyQuoted 40 lines · Eliot Courtney
Add bindings and helpers for area operations on bitmaps. Each one is made safe by adding some extra checks compared to the underlying C code (for example, checking bounds) and with additional checks to catch likely erroneous usage if
CONFIG_RUST_BITMAP_HARDENEDis on.The C code uses signed integers for some parameters, for example the length for
__bitmap_set, so bounds check againsti32::MAX. We can't rely onBitmapVec::MAX_LENbecauseBitmapmay not necessarily be backed byBitmapVec. There's also a few cases where a non power of two minus onealign_maskcan cause an infinite loop in the C code (can happen on overflow), so check for that.Add tests demonstrating the edge cases.
Signed-off-by Eliot Courtney <[email protected]>--- rust/helpers/bitmap.c | 22 +++++ rust/kernel/bitmap.rs | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 241 insertions(+)rust/helpers/bitmap.c +12
-0@@ -8,3 +8,25 @@ void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long * {bitmap_copy_and_extend (to, from, count, size); } + +__rust_helper +unsigned long rust_helper_bitmap_find_next_zero_area (unsigned long *map, +unsigned long size, +unsigned long start, +unsigned int nr, +unsigned long align_mask) +{ +return bitmap_find_next_zero_area (map, size, start, nr, align_mask); +} + +__rust_helper
rust/helpers/bitmap.c void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long * · line 32
Quoted 10 lines
rust/helpers/bitmap.c +10
-0+void rust_helper_bitmap_set (unsigned long *map,unsigned int start,unsigned int nbits) +{ +bitmap_set (map, start, nbits); +} + +__rust_helper +void rust_helper_bitmap_clear(unsigned long *map, unsigned int start, unsigned int nbits) +{ +bitmap_clear (map, start, nbits); +}
All three are the wrappers around the regular outline functions:bitmap_find_next_zero_area_off(), __bitmap_set() and __bitmap_clear().
The inlined version in headers is optimized for small bitmaps. But the optimization is all based on inlining in the C code. It doesn't work if you wrap it with a rust helper.
There was a discussion about the similar find_next_bit(). The function itself is an inliner, but it's a wrapper around the true outlined _find_next_bit(). So we decided to minimize the binder size for that type of functions.
Please, keep the binder minimal unless necessary.
Quoted 49 lines
rust/kernel/bitmap.rs +41
-0@@ -497,6 +497,129 @@ pub fn next_zero_bit(&self, start: usize) -> Option<usize> {Some (index) } } + +/// Finds a contiguous area of `nbits` zero bits at or after `start`, aligned per `align_mask`. +/// +/// Returns the bit index of the start of the area, or [`None`] if no such area fitting in +/// the bitmap exists or the `align_mask` is invalid. +/// +/// `align_mask` should be `0` (no alignment) or one less than a power of two, in which case the +/// returned index is a multiple of that power of two. +/// +/// # Panics +/// +/// Panics if CONFIG_RUST_BITMAP_HARDENED is enabled and `start` is out of bounds or +/// `align_mask` is not `0` or `2^k - 1`. +/// +/// # Examples +/// +/// ``` +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL}; +/// use kernel::bitmap::BitmapVec; +/// +/// let mut b = BitmapVec::new(64, GFP_KERNEL)?; +/// +/// assert_eq!(Some(0), b.next_zero_area(0, 8, 0)); +/// b.set_area(0, 5); +/// assert_eq!(Some(5), b.next_zero_area(0, 8, 0)); +/// assert_eq!(Some(8), b.next_zero_area(0, 8, 7)); +/// assert_eq!(None, b.next_zero_area(0, 65, 0)); +/// # Ok::<(), AllocError>(()) +/// ``` +#[inline] +pub fn next_zero_area (&self, start:usize , nbits:usize , align_mask:usize ) ->Option <usize > { +bitmap_assert! ( + start < self.len (), +"`start` must be < {}, was {}" , + self.len (), + start + ); + +let valid_align_mask = align_mask + .checked_add (1 ) + .is_some_and (|p| p.is_power_of_two ());
rust/kernel/bitmap.rs pub fn next_zero_bit(&self, start: usize) -> Option<usize> { · line 550
Quoted 10 lines
rust/kernel/bitmap.rs +10
-0+ +bitmap_assert! ( + valid_align_mask, +"`align_mask` must be 0 or `2^k - 1`, was {}" , + align_mask + ); + +if !valid_align_mask { +return None ; + }
This quite a trivial check takes about a half of the function in terms of LOCs. Is there any way to compact it?
Quoted 25 lines
rust/kernel/bitmap.rs +25
-0+let nr = u32::try_from (nbits).ok ()?; + +// SAFETY: `bitmap_find_next_zero_area` is safe to use with an out of bounds `start` value, +// never reads beyond `self.len()` bits, and returns a value `>= self.len()` when no area is +// found. +let index =unsafe { + bindings::bitmap_find_next_zero_area ( + self.as_ptr ().cast_mut (), + self.len (), + start, + nr, + align_mask, + ) + }; + +// In case of overflow, we may get back a range outside of what we requested. +let end = index.checked_add (nbits)?; +if index < start || index >= self.len () || end > self.len () { +None + }else { +Some (index) + } + } + +/// Sets a contiguous area of `nbits` bits starting at `start`.
rust/kernel/bitmap.rs pub fn next_zero_bit(&self, start: usize) -> Option<usize> { · line 586
Quoted 10 lines
rust/kernel/bitmap.rs +10
-0+/// +/// If CONFIG_RUST_BITMAP_HARDENED is not enabled and the area `start..start + nbits` is out of +/// bounds, does nothing. +/// +/// # Panics +/// +/// Panics if CONFIG_RUST_BITMAP_HARDENED is enabled and the area `start..start + nbits` is out +/// of bounds. +#[inline] +pub fn set_area (&mut self, start:usize , nbits:usize ) {
Please don't invent new names. If this particular function in C is named "bitmap_set()", it means that in rust world it should be reflected with a method ".set()".
Quoted 14 lines
rust/kernel/bitmap.rs +14
-0+bitmap_assert_return! ( + start + .checked_add (nbits) + .is_some_and (|end| end <= self.len () && end <=i32 ::MAX as usize ), +"Area `start..start + nbits` ({}..{}) must be within bounds {}" , + start, + start.saturating_add (nbits), + self.len () + ); +// SAFETY: The area `start..start + nbits` is within bounds. +unsafe { bindings::bitmap_set (self.as_mut_ptr (), startas u32 , nbitsas u32 ) }; + } + +/// Clears a contiguous area of `nbits` bits starting at `start`.
rust/kernel/bitmap.rs pub fn next_zero_bit(&self, start: usize) -> Option<usize> { · line 610
Quoted 10 lines
rust/kernel/bitmap.rs +10
-0+/// +/// If CONFIG_RUST_BITMAP_HARDENED is not enabled and the area `start..start + nbits` is out of +/// bounds, does nothing. +/// +/// # Panics +/// +/// Panics if CONFIG_RUST_BITMAP_HARDENED is enabled and the area `start..start + nbits` is out +/// of bounds. +#[inline] +pub fn clear_area (&mut self, start:usize , nbits:usize ) {
Same here: .clear(), please
Quoted 119 lines
rust/kernel/bitmap.rs +108
-0+bitmap_assert_return! ( + start + .checked_add (nbits) + .is_some_and (|end| end <= self.len () && end <=i32 ::MAX as usize ), +"Area `start..start + nbits` ({}..{}) must be within bounds {}" , + start, + start.saturating_add (nbits), + self.len () + ); +// SAFETY: The area `start..start + nbits` is within bounds. +unsafe { bindings::bitmap_clear (self.as_mut_ptr (), startas u32 , nbitsas u32 ) }; + } }#[cfg( CONFIG_RUST_BITMAP_KUNIT_TEST )] @@ -614,4 +737,100 @@ fn bitmap_copy_and_extend() -> Result<(), AllocError> {assert_eq! (Some (17 ), long_bitmap.last_bit ());Ok (()) } + +#[test] +fn bitmap_area_set_clear_find () ->Result <(),AllocError > { +let mut b =BitmapVec ::new (128 ,GFP_KERNEL )?; + +assert_eq! (Some (0 ), b.next_zero_area (0 ,5 ,0 )); + b.set_area (0 ,5 );// Now contains {[0, 5)}. + +assert_eq! (Some (0 ), b.next_bit (0 )); +assert_eq! (Some (4 ), b.next_bit (4 )); +assert_eq! (Some (5 ), b.next_zero_bit (0 )); +assert_eq! (Some (5 ), b.next_zero_area (0 ,5 ,0 )); +assert_eq! (Some (8 ), b.next_zero_area (0 ,5 ,7 )); + + b.set_area (8 ,8 );// Now contains {[0, 5), [8, 16)}. +assert_eq! (Some (16 ), b.next_zero_area (0 ,4 ,15 )); +assert_eq! (Some (16 ), b.next_zero_area (0 ,4 ,0 )); + + b.clear_area (0 ,5 );// Now contains {[8, 16)}. +assert_eq! (Some (0 ), b.next_zero_area (0 ,5 ,0 )); +assert_eq! (Some (8 ), b.next_bit (0 )); +assert_eq! (Some (15 ), b.last_bit ()); + + b.clear_area (16 ,0 );// Zero-length in-bounds clears are no-ops. +assert_eq! (Some (8 ), b.next_bit (0 )); +assert_eq! (Some (15 ), b.last_bit ()); + +// A zero-length request returns the first aligned position at or +// after the next zero bit, even if that position's own bit is set. +assert_eq! (Some (1 ), b.next_zero_area (1 ,0 ,0 )); +assert_eq! (Some (8 ), b.next_zero_area (1 ,0 ,7 )); + + b.set_area (60 ,10 );// Now contains {[8, 16), [60, 70)}. +assert_eq! (Some (60 ), b.next_bit (16 )); +assert_eq! (Some (69 ), b.last_bit ()); +assert_eq! (Some (16 ), b.next_zero_area (9 ,40 ,0 )); +assert_eq! (Some (70 ), b.next_zero_area (0 ,45 ,0 )); + + b.clear_area (62 ,6 );// Now contains {[8, 16), [60, 62), [68, 70)}. +assert_eq! (Some (62 ), b.next_zero_area (60 ,6 ,0 )); +assert_eq! (Some (61 ), b.next_bit (61 )); +assert_eq! (Some (69 ), b.last_bit ()); + + b.set_area (64 ,0 );// Zero-length in-bounds sets are no-ops. +assert_eq! (Some (62 ), b.next_zero_bit (62 )); +Ok (()) + } + +#[test] +fn bitmap_area_exhaustion () ->Result <(),AllocError > { +let mut b =BitmapVec ::new (64 ,GFP_KERNEL )?; + +assert_eq! (None , b.next_zero_area (0 ,65 ,0 )); +assert_eq! (None , b.next_zero_area (0 ,usize ::MAX ,0 )); +assert_eq! (None , b.next_zero_area (1 ,usize ::MAX ,0 )); + + b.set_bit (0 );// Now contains {[0, 1)}. +assert_eq! (None , b.next_zero_area (0 ,usize ::MAX ,0 )); + + b.set_area (0 ,61 );// Now contains {[0, 61)}. +assert_eq! (None , b.next_zero_area (0 ,4 ,0 )); +assert_eq! (Some (61 ), b.next_zero_area (0 ,3 ,0 )); +assert_eq! (None , b.next_zero_area (0 ,1 ,63 )); +Ok (()) + } + +#[test] +#[cfg(not( CONFIG_RUST_BITMAP_HARDENED ))] +fn bitmap_area_invalid_align () ->Result <(),AllocError > { +let mut b =BitmapVec ::new (64 ,GFP_KERNEL )?; + b.set_bit (0 ); + +assert_eq! (Some (1 ), b.next_zero_bit (1 )); +// If this isn't rejected, it would cause a hang in the C code. +assert_eq! (None , b.next_zero_area (1 ,1 ,usize ::MAX )); +// Reject non `2^k - 1` alignment masks. +assert_eq! (None , b.next_zero_area (1 ,1 ,2 )); +assert_eq! (None , b.next_zero_area (1 ,1 ,5 )); +Ok (()) + } + +#[test] +#[cfg(not( CONFIG_RUST_BITMAP_HARDENED ))] +fn owned_bitmap_area_out_of_bounds () ->Result <(),AllocError > { +let mut b =BitmapVec ::new (64 ,GFP_KERNEL )?; + +// Should be ignored since out of bounds. + b.set_area (64 ,4 ); + b.set_area (62 ,8 ); + b.set_area (usize::MAX ,0 ); + b.clear_area (usize::MAX ,0 ); + b.clear_area (2048 ,8 ); +assert_eq! (None , b.next_bit (0 )); +assert_eq! (None , b.next_zero_area (64 ,1 ,0 )); +Ok (()) + } }Signature · 2 lines
-- 2.54.0
Alice Ryhl
maintainerRe: [PATCH 2/4] rust: bitmap: add contiguous area operations
Quoted 59 lines · Yury Norov
Quoted 40 lines · Eliot Courtney
Add bindings and helpers for area operations on bitmaps. Each one is made safe by adding some extra checks compared to the underlying C code (for example, checking bounds) and with additional checks to catch likely erroneous usage if
CONFIG_RUST_BITMAP_HARDENEDis on.The C code uses signed integers for some parameters, for example the length for
__bitmap_set, so bounds check againsti32::MAX. We can't rely onBitmapVec::MAX_LENbecauseBitmapmay not necessarily be backed byBitmapVec. There's also a few cases where a non power of two minus onealign_maskcan cause an infinite loop in the C code (can happen on overflow), so check for that.Add tests demonstrating the edge cases.
Signed-off-by Eliot Courtney <[email protected]>--- rust/helpers/bitmap.c | 22 +++++ rust/kernel/bitmap.rs | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 241 insertions(+)rust/helpers/bitmap.c +12
-0@@ -8,3 +8,25 @@ void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long * {bitmap_copy_and_extend (to, from, count, size); } + +__rust_helper +unsigned long rust_helper_bitmap_find_next_zero_area (unsigned long *map, +unsigned long size, +unsigned long start, +unsigned int nr, +unsigned long align_mask) +{ +return bitmap_find_next_zero_area (map, size, start, nr, align_mask); +} + +__rust_helperrust/helpers/bitmap.c void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long * · line 32
Quoted 10 lines
rust/helpers/bitmap.c +10
-0+void rust_helper_bitmap_set (unsigned long *map,unsigned int start,unsigned int nbits) +{ +bitmap_set (map, start, nbits); +} + +__rust_helper +void rust_helper_bitmap_clear(unsigned long *map, unsigned int start, unsigned int nbits) +{ +bitmap_clear (map, start, nbits); +}All three are the wrappers around the regular outline functions:
bitmap_find_next_zero_area_off(),__bitmap_set()and__bitmap_clear().The inlined version in headers is optimized for small bitmaps. But the optimization is all based on inlining in the C code. It doesn't work if you wrap it with a rust helper.
Quoted 6 lines
There was a discussion about the similar
find_next_bit(). The function itself is an inliner, but it's a wrapper around the true outlined_find_next_bit(). So we decided to minimize the binder size for that type of functions.Please, keep the binder minimal unless necessary.
If we can just call __bitmap_clear() without any downsides, then I agree we should do that, but we actually do support inlining the helpers now. See CONFIG_RUST_INLINE_HELPERS.
Alice
Gary Guo
reviewerRe: [PATCH 2/4] rust: bitmap: add contiguous area operations
Quoted 13 lines · Alice Ryhl
Quoted 12 lines · Yury Norov
All three are the wrappers around the regular outline functions:
bitmap_find_next_zero_area_off(),__bitmap_set()and__bitmap_clear().The inlined version in headers is optimized for small bitmaps. But the optimization is all based on inlining in the C code. It doesn't work if you wrap it with a rust helper.
There was a discussion about the similar
find_next_bit(). The function itself is an inliner, but it's a wrapper around the true outlined_find_next_bit(). So we decided to minimize the binder size for that type of functions.
Quoted 5 lines
Quoted 1 line
Please, keep the binder minimal unless necessary.
If we can just call
__bitmap_clear()without any downsides, then I agree we should do that, but we actually do support inlining the helpers now. SeeCONFIG_RUST_INLINE_HELPERS.
bitmap uses __builtin_constant_p which will only work with pure C inlining and not LLVM IR based inlining.
Best,
Gary
Alice Ryhl
maintainerRe: [PATCH 2/4] rust: bitmap: add contiguous area operations
Quoted 14 lines · Gary Guo
Quoted 13 lines · Alice Ryhl
Quoted 12 lines · Yury Norov
All three are the wrappers around the regular outline functions:
bitmap_find_next_zero_area_off(),__bitmap_set()and__bitmap_clear().The inlined version in headers is optimized for small bitmaps. But the optimization is all based on inlining in the C code. It doesn't work if you wrap it with a rust helper.
There was a discussion about the similar
find_next_bit(). The function itself is an inliner, but it's a wrapper around the true outlined_find_next_bit(). So we decided to minimize the binder size for that type of functions.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Please, keep the binder minimal unless necessary.
If we can just call
__bitmap_clear()without any downsides, then I agree we should do that, but we actually do support inlining the helpers now. SeeCONFIG_RUST_INLINE_HELPERS.bitmap uses
__builtin_constant_pwhich will only work with pure C inlining and not LLVM IR based inlining.
Ack in that case using __bitmap_clear() from Rust definitely makes sense. Thanks
Alice
PATCH 3/4 rust: id_pool: add contiguous area allocation
In reply to Eliot CourtneyAdd support for contiguous area allocation. Add a new type, UnusedArea, following the same pattern as UnusedId.
--- rust/kernel/id_pool.rs | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 68 insertions(+)
rust/kernel/id_pool.rs +68 -0
@@ -4,6 +4,11 @@//! Rust API for an ID pool backed by a [`BitmapVec`]. +use core::{ + num::NonZero , + ops::Range ,// +}; +use crate ::alloc::{AllocError ,Flags };use crate ::bitmap::BitmapVec ;
@@ -240,6 +245,33 @@ pub fn find_unused_id(&mut self, offset: usize) -> Option<UnusedId<'_>> {pub fn release_id (&mut self, id:usize ) { self.map.clear_bit (id); } + +/// Finds a contiguous area of `count` unused IDs at or after `offset`. +/// +/// `align_mask` must be `0` (no alignment) or one less than a power of two, in which case the +/// start of the returned area is a multiple of that power of two. +/// +/// Returns an [`UnusedArea`] upon success, or [`None`] if no such area could be found. +#[inline] +#[must_use] +pub fn find_unused_area ( + &mut self, + offset:usize , + count:NonZero <usize >, + align_mask:usize , + ) ->Option <UnusedArea <'_>> { +let start = self.map.next_zero_area (offset, count.get (), align_mask)?; +Some (UnusedArea { + range: start..start + count.get (), + pool: self, + }) + } + +/// Releases a contiguous area of IDs. +#[inline] +pub fn release_area (&mut self, range: &Range <usize >) { + self.map.clear_area (range.start, range.len ()); + } }/// Represents an unused id in an [`IdPool`].
@@ -287,6 +319,42 @@ pub fn acquire(self) -> usize { } } +/// Represents an unused, contiguous area of IDs in an [`IdPool`]. +/// +/// # Invariants +/// +/// `range.start <= range.end <= pool.map.len()`. +#[must_use = "the ID range is not reserved unless acquired" ] +pub struct UnusedArea <'pool> { + range:Range <usize >, + pool: &'poolmut IdPool , +} + +impl <'pool>UnusedArea <'pool> { +/// Returns the unused ID range. +/// +/// Be aware that the area has not yet been acquired in the pool. The +/// [`acquire`] method must be called to prevent others from taking it. +/// +/// [`acquire`]: UnusedArea::acquire() +#[inline] +#[must_use] +pub fn range (&self) ->Range <usize > { + self.range.clone () + } + +/// Acquires the area. +/// +/// Returns the now-reserved ID range. +#[inline] +pub fn acquire (self) ->Range <usize > { +let Self { range, pool } = self; +// By the type invariants, the range is within bounds. + pool.map.set_area (range.start, range.end - range.start); + range + } +} +impl Default for IdPool {#[inline] fn default () ->Self {
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Low] The construction of `UnusedArea` is missing the required `// INVARIANT:` comment. --
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] The construction of UnusedArea is missing the required // INVARIANT: comment. --
commit dec3af2ba5f37136507d9a42f30fab7e3072db7f
Author: Eliot Courtney <[email protected]>
rust: id_pool: add contiguous area allocation
This commit adds support for contiguous area allocation to the ID pool by introducing a new UnusedArea type that follows the same pattern as UnusedId.
Quoted 4 lines
rust/kernel/id_pool.rs +0
-0
[ ... ]
Quoted 14 lines
rust/kernel/id_pool.rs +10
-0@@ -240,6 +245,33 @@ pub fn find_unused_id(&mut self, offset: usize) -> Option<UnusedId<'_>> {pub fn release_id (&mut self, id:usize ) { self.map.clear_bit (id); } + +/// Finds a contiguous area of `count` unused IDs at or after `offset`. +/// +/// `align_mask` must be `0` (no alignment) or one less than a power of two, in which case the +/// start of the returned area is a multiple of that power of two. +/// +/// Returns an [`UnusedArea`] upon success, or [`None`] if no such area could be found. +#[inline] +#[must_use] + pub fn find_unused_area(
rust/kernel/id_pool.rs pub fn find_unused_id(&mut self, offset: usize) -> Option<UnusedId<'_>> { · line 267
Quoted 10 lines
rust/kernel/id_pool.rs +10
-0+ &mut self, + offset: usize, + count: NonZero<usize>, + align_mask: usize, + ) -> Option<UnusedArea<'_>> { +let start = self.map.next_zero_area (offset, count.get (), align_mask)?; +Some (UnusedArea { + range: start..start + count.get (), + pool: self, + })
[Severity: Low]
This isn't a bug, but should this UnusedArea instantiation include an // INVARIANT: comment?
The Rust subsystem guidelines state that when a struct with an # Invariants documentation section is constructed, the code should have an // INVARIANT:
comment explaining why the invariants are satisfied.
UnusedArea defines the invariant range.start <= range.end <= pool.map.len(). Would it be appropriate to add a comment here detailing why the bounds guaranteed by next_zero_area() satisfy this invariant?
Quoted 1 line
rust/kernel/id_pool.rs +1
-0+ }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation
In reply to Eliot CourtneyQuoted 4 lines · Eliot Courtney
Add support for contiguous area allocation. Add a new type,
UnusedArea, following the same pattern asUnusedId.Signed-off-by Eliot Courtney <[email protected]>
Why isn't the built-in idr library being used here instead of rolling your own data structure?
thanks,
greg k-h
Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Quoted 4 lines · Greg KH
Quoted 3 lines · Eliot Courtney
Add support for contiguous area allocation. Add a new type,
UnusedArea, following the same pattern asUnusedId.
Quoted 8 lines
Quoted 1 line
Signed-off-by Eliot Courtney <[email protected]>Why isn't the built-in idr library being used here instead of rolling your own data structure?
thanks,
greg k-h
For nova-core in this series, we need allocation of a contiguous sequence of IDs with a specific length and sometimes a specific alignment. IIUC, IDA/xarray do not support that (I checked ida_alloc_range and it only allocates a single ID in a range, not a contiguous sequence).
For IdPool before this series, I think it could have used IDA/xarray. See [1] where Alice has posted some more context.
w.r.t. the structure choice, the IDs we need to allocate are channel IDs, and the total range is limited to 2048 of them, so IMO bitmaps are a better fit than e.g. maple tree.
Thanks!
Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Quoted 20 lines · Eliot Courtney
Quoted 4 lines · Greg KH
Quoted 3 lines · Eliot Courtney
Add support for contiguous area allocation. Add a new type,
UnusedArea, following the same pattern asUnusedId.Quoted 8 lines
Quoted 1 line
Signed-off-by Eliot Courtney <[email protected]>Why isn't the built-in idr library being used here instead of rolling your own data structure?
thanks,
greg k-h
For nova-core in this series, we need allocation of a contiguous sequence of IDs with a specific length and sometimes a specific alignment. IIUC, IDA/xarray do not support that (I checked
ida_alloc_rangeand it only allocates a single ID in a range, not a contiguous sequence).
Quoted 6 lines
For IdPool before this series, I think it could have used IDA/xarray. See [1] where Alice has posted some more context.
w.r.t. the structure choice, the IDs we need to allocate are channel IDs, and the total range is limited to 2048 of them, so IMO bitmaps are a better fit than e.g. maple tree.
But again, you are having to "roll your own" logic here, please reuse the data structures we already have in the kernel for this type of thing. If a maple tree works, please use it.
thanks,
greg k-h
Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Quoted 24 lines · Greg KH
Quoted 23 lines · Eliot Courtney
Quoted 4 lines · Greg KH
Quoted 3 lines · Eliot Courtney
Add support for contiguous area allocation. Add a new type,
UnusedArea, following the same pattern asUnusedId.Quoted 8 lines
Quoted 1 line
Signed-off-by Eliot Courtney <[email protected]>Why isn't the built-in idr library being used here instead of rolling your own data structure?
thanks,
greg k-h
For nova-core in this series, we need allocation of a contiguous sequence of IDs with a specific length and sometimes a specific alignment. IIUC, IDA/xarray do not support that (I checked
ida_alloc_rangeand it only allocates a single ID in a range, not a contiguous sequence).For IdPool before this series, I think it could have used IDA/xarray. See [1] where Alice has posted some more context.
Quoted 7 lines
Quoted 3 lines
w.r.t. the structure choice, the IDs we need to allocate are channel IDs, and the total range is limited to 2048 of them, so IMO bitmaps are a better fit than e.g. maple tree.
But again, you are having to "roll your own" logic here, please reuse the data structures we already have in the kernel for this type of thing. If a maple tree works, please use it.
I asked exactly the same question when Alice and Burak added wrappers for bitmaps to implement their ID pool. This is the answer:
An alternative route of vendoring an existing Rust bitmap package was considered but suboptimal overall. Reusing the C implementation is preferable for a basic data structure like bitmaps. It enables Rust code to be a lot more similar and predictable with respect to C code that uses the same data structures and enables the use of code that has been tried-and-tested in the kernel, with the same performance characteristics whenever possible.
And now it's in a commit message: 11eca92a2caeb
They measured the affect of their wrapper on performance, and it appears to be ~5%. See lib/find_bit_benchmark_rust.rs.
I didn't see any side-to-side comparison between any native Rust API vs imported C bitmaps. I'm sure, I asked for that, and I still believe it's the important piece of data to avoid this back-and-forth type of discussions. So, Alice, Burak or anybody...
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Why isn't the built-in idr library being used here instead of rolling your own data structure?
Now having more context, the ID pool's primary goal is to allocate individual IDs, which naturally lays on find_bit() API in C. The native Rust alternative is considered and found 'suboptimal overall'.
This series extends the existing data structure in Rust for Linux, not adding a new one. So, the series itself looks justified to me because it's a logical extension of the existing functionality.
Regarding C bindings vs native API... Yes we lack thorough performance analysis. Do we have such analysis for every data structure in kernel?
No. So to me it's as simple as: they are developers, they know better.
Thanks,
Yury
Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Quoted 44 lines · Yury Norov
Quoted 24 lines · Greg KH
Quoted 23 lines · Eliot Courtney
Quoted 4 lines · Greg KH
Quoted 3 lines · Eliot Courtney
Add support for contiguous area allocation. Add a new type,
UnusedArea, following the same pattern asUnusedId.Quoted 8 lines
Quoted 1 line
Signed-off-by Eliot Courtney <[email protected]>Why isn't the built-in idr library being used here instead of rolling your own data structure?
thanks,
greg k-h
For nova-core in this series, we need allocation of a contiguous sequence of IDs with a specific length and sometimes a specific alignment. IIUC, IDA/xarray do not support that (I checked
ida_alloc_rangeand it only allocates a single ID in a range, not a contiguous sequence).For IdPool before this series, I think it could have used IDA/xarray. See [1] where Alice has posted some more context.
Quoted 7 lines
Quoted 3 lines
w.r.t. the structure choice, the IDs we need to allocate are channel IDs, and the total range is limited to 2048 of them, so IMO bitmaps are a better fit than e.g. maple tree.
But again, you are having to "roll your own" logic here, please reuse the data structures we already have in the kernel for this type of thing. If a maple tree works, please use it.
I asked exactly the same question when Alice and Burak added wrappers for bitmaps to implement their ID pool. This is the answer:
An alternative route of vendoring an existing Rust bitmap package was considered but suboptimal overall. Reusing the C implementation is preferable for a basic data structure like bitmaps. It enables Rust code to be a lot more similar and predictable with respect to C code that uses the same data structures and enables the use of code that has been tried-and-tested in the kernel, with the same performance characteristics whenever possible.
Quoted 4 lines
And now it's in a commit message:
11eca92a2caebThey measured the affect of their wrapper on performance, and it appears to be ~5%. See
lib/find_bit_benchmark_rust.rs.
You are comparing the C vs. Rust data structures here, which is not what I am proposing.
Also, is this code being used on a "hot path" like the binder stuff is?
Quoted 4 lines
I didn't see any side-to-side comparison between any native Rust API vs imported C bitmaps. I'm sure, I asked for that, and I still believe it's the important piece of data to avoid this back-and-forth type of discussions. So, Alice, Burak or anybody...
Again, I'm not talking about Rust API vs. imported C bitmaps, I'm asking to use the C structures like maple-tree and idr instead of open-coding logic around the bitmap code.
Quoted 6 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Why isn't the built-in idr library being used here instead of rolling your own data structure?
Now having more context, the ID pool's primary goal is to allocate individual IDs, which naturally lays on
find_bit()API in C. The native Rust alternative is considered and found 'suboptimal overall'.
Allocating IDs is a probe() thing, which can be as slow as it wants, right? Or is this some other hot-path where performance matters? The patch was not very specific as to the tradeoffs needed.
thanks,
greg k-h
Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation
On Wed, Jul 08, 2026 at 07:33:16AM +0200, Greg KH wrote:
...
Quoted 21 lines
Quoted 11 lines
I asked exactly the same question when Alice and Burak added wrappers for bitmaps to implement their ID pool. This is the answer:
An alternative route of vendoring an existing Rust bitmap package was considered but suboptimal overall. Reusing the C implementation is preferable for a basic data structure like bitmaps. It enables Rust code to be a lot more similar and predictable with respect to C code that uses the same data structures and enables the use of code that has been tried-and-tested in the kernel, with the same performance characteristics whenever possible.
Quoted 4 lines
And now it's in a commit message:
11eca92a2caebThey measured the affect of their wrapper on performance, and it appears to be ~5%. See
lib/find_bit_benchmark_rust.rs.You are comparing the C vs. Rust data structures here, which is not what I am proposing.
Also, is this code being used on a "hot path" like the binder stuff is?
Quoted 8 lines
Quoted 4 lines
I didn't see any side-to-side comparison between any native Rust API vs imported C bitmaps. I'm sure, I asked for that, and I still believe it's the important piece of data to avoid this back-and-forth type of discussions. So, Alice, Burak or anybody...
Again, I'm not talking about Rust API vs. imported C bitmaps, I'm asking to use the C structures like maple-tree and idr instead of open-coding logic around the bitmap code.
I understand your point. I asked both questions: are they sure that bitmap is the most optimal data structure for the ID pool, and if so, why not use the built-in Rust bitmaps? The answer was: yes, it's the most optimal, and using built-in bitmaps is suboptimal overall.
Burak, can you share more details please?
Quoted 10 lines
Quoted 6 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Why isn't the built-in idr library being used here instead of rolling your own data structure?
Now having more context, the ID pool's primary goal is to allocate individual IDs, which naturally lays on
find_bit()API in C. The native Rust alternative is considered and found 'suboptimal overall'.Allocating IDs is a
probe()thing, which can be as slow as it wants, right? Or is this some other hot-path where performance matters? The patch was not very specific as to the tradeoffs needed.
I am a bitmaps maintainer, and I want them in Rust to perform equally well. The ID pool case was just the first user. Even if bitmap performance is not a critical path for ID pool, my role is to make sure that bitmap in Rust is implemented well, including the performance part.
Said that, I recall that bitmaps performance was important for the ID pool, and Alice and Burak spent some time optimizing the ID allocation path. Particularly, added a logic to avoid allocation of small bitmaps.
Thanks,
Yury
Alice Ryhl
maintainerRe: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Quoted 30 lines · Yury Norov
On Wed, Jul 08, 2026 at 07:33:16AM +0200, Greg KH wrote:
...
Quoted 26 lines
Quoted 11 lines
I asked exactly the same question when Alice and Burak added wrappers for bitmaps to implement their ID pool. This is the answer:
An alternative route of vendoring an existing Rust bitmap package was considered but suboptimal overall. Reusing the C implementation is preferable for a basic data structure like bitmaps. It enables Rust code to be a lot more similar and predictable with respect to C code that uses the same data structures and enables the use of code that has been tried-and-tested in the kernel, with the same performance characteristics whenever possible.
Quoted 4 lines
And now it's in a commit message:
11eca92a2caebThey measured the affect of their wrapper on performance, and it appears to be ~5%. See
lib/find_bit_benchmark_rust.rs.You are comparing the C vs. Rust data structures here, which is not what I am proposing.
Also, is this code being used on a "hot path" like the binder stuff is?
Quoted 4 lines
I didn't see any side-to-side comparison between any native Rust API vs imported C bitmaps. I'm sure, I asked for that, and I still believe it's the important piece of data to avoid this back-and-forth type of discussions. So, Alice, Burak or anybody...
Quoted 8 lines
Quoted 3 lines
Again, I'm not talking about Rust API vs. imported C bitmaps, I'm asking to use the C structures like maple-tree and idr instead of open-coding logic around the bitmap code.
I understand your point. I asked both questions: are they sure that bitmap is the most optimal data structure for the ID pool, and if so, why not use the built-in Rust bitmaps? The answer was: yes, it's the most optimal, and using built-in bitmaps is suboptimal overall.
The Rust standard library doesn't really have a bitmap abstraction to begin with, so if we want to use bitmap then it's either handrolled bit-manipulation or the C bitmap api.
cc'ing Burak's new email
Quoted 11 lines
Quoted 10 lines
Quoted 6 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Why isn't the built-in idr library being used here instead of rolling your own data structure?
Now having more context, the ID pool's primary goal is to allocate individual IDs, which naturally lays on
find_bit()API in C. The native Rust alternative is considered and found 'suboptimal overall'.Allocating IDs is a
probe()thing, which can be as slow as it wants, right? Or is this some other hot-path where performance matters? The patch was not very specific as to the tradeoffs needed.
Quoted 8 lines
I am a bitmaps maintainer, and I want them in Rust to perform equally well. The ID pool case was just the first user. Even if bitmap performance is not a critical path for ID pool, my role is to make sure that bitmap in Rust is implemented well, including the performance part.
Said that, I recall that bitmaps performance was important for the ID pool, and Alice and Burak spent some time optimizing the ID allocation path. Particularly, added a logic to avoid allocation of small bitmaps.
Yeah the Binder use-case is not the same as probe(). It's a per-fd data structure used to give names to kernel objects that userspace is manipulating, and the mapping is per-process.
Alice
Burak Emir
maintainerRe: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Quoted 41 lines · Alice Ryhl
Quoted 30 lines · Yury Norov
On Wed, Jul 08, 2026 at 07:33:16AM +0200, Greg KH wrote:
...
Quoted 26 lines
Quoted 11 lines
I asked exactly the same question when Alice and Burak added wrappers for bitmaps to implement their ID pool. This is the answer:
An alternative route of vendoring an existing Rust bitmap package was considered but suboptimal overall. Reusing the C implementation is preferable for a basic data structure like bitmaps. It enables Rust code to be a lot more similar and predictable with respect to C code that uses the same data structures and enables the use of code that has been tried-and-tested in the kernel, with the same performance characteristics whenever possible.
Quoted 4 lines
And now it's in a commit message:
11eca92a2caebThey measured the affect of their wrapper on performance, and it appears to be ~5%. See
lib/find_bit_benchmark_rust.rs.You are comparing the C vs. Rust data structures here, which is not what I am proposing.
Also, is this code being used on a "hot path" like the binder stuff is?
Quoted 4 lines
I didn't see any side-to-side comparison between any native Rust API vs imported C bitmaps. I'm sure, I asked for that, and I still believe it's the important piece of data to avoid this back-and-forth type of discussions. So, Alice, Burak or anybody...
Quoted 8 lines
Quoted 3 lines
Again, I'm not talking about Rust API vs. imported C bitmaps, I'm asking to use the C structures like maple-tree and idr instead of open-coding logic around the bitmap code.
I understand your point. I asked both questions: are they sure that bitmap is the most optimal data structure for the ID pool, and if so, why not use the built-in Rust bitmaps? The answer was: yes, it's the most optimal, and using built-in bitmaps is suboptimal overall.
Quoted 6 lines
The Rust standard library doesn't really have a bitmap abstraction to begin with, so if we want to use bitmap then it's either handrolled bit-manipulation or the C bitmap api.
cc'ing Burak's new email
(Thanks, I will update my email in the MAINTAINERS file.)
Binder needs to acquire bits *while holding a spinlock*. This is the biggest constraint.
My understanding is that the IDA API call might need to allocate memory (and sleep) when getting a new ID, as a side-effect. So for the binder use case, it was not an option.
@Yury, about the alternative of vendoring Rust bitmap crates: that would have duplicated the kernel's C bitmap functionality. There does not seem much point in duplicating that, and opening the door to have Rust and C code differently named API functions and such. So beside performance, maintenance and coherence are also a factor.
The Rust ID pool code is merely a port of some existing bitmap-specific binder C code (that can hopefully be deleted one day) that deals with spinlock allocation fun. If the constraints match, I think it is good to see it generalized and used elsewhere. That is a conditional statement, I am not familiar with the nova use case's performance/allocation/sleep constraints.
-- Burak
Re: [PATCH 3/4] rust: id_pool: add contiguous area allocation
In reply to Greg KHQuoted 55 lines · Greg KH
Quoted 44 lines · Yury Norov
Quoted 24 lines · Greg KH
Quoted 23 lines · Eliot Courtney
Quoted 4 lines · Greg KH
Quoted 3 lines · Eliot Courtney
Add support for contiguous area allocation. Add a new type,
UnusedArea, following the same pattern asUnusedId.Quoted 8 lines
Quoted 1 line
Signed-off-by Eliot Courtney <[email protected]>Why isn't the built-in idr library being used here instead of rolling your own data structure?
thanks,
greg k-h
For nova-core in this series, we need allocation of a contiguous sequence of IDs with a specific length and sometimes a specific alignment. IIUC, IDA/xarray do not support that (I checked
ida_alloc_rangeand it only allocates a single ID in a range, not a contiguous sequence).For IdPool before this series, I think it could have used IDA/xarray. See [1] where Alice has posted some more context.
Quoted 7 lines
Quoted 3 lines
w.r.t. the structure choice, the IDs we need to allocate are channel IDs, and the total range is limited to 2048 of them, so IMO bitmaps are a better fit than e.g. maple tree.
But again, you are having to "roll your own" logic here, please reuse the data structures we already have in the kernel for this type of thing. If a maple tree works, please use it.
I asked exactly the same question when Alice and Burak added wrappers for bitmaps to implement their ID pool. This is the answer:
An alternative route of vendoring an existing Rust bitmap package was considered but suboptimal overall. Reusing the C implementation is preferable for a basic data structure like bitmaps. It enables Rust code to be a lot more similar and predictable with respect to C code that uses the same data structures and enables the use of code that has been tried-and-tested in the kernel, with the same performance characteristics whenever possible.
Quoted 4 lines
And now it's in a commit message:
11eca92a2caebThey measured the affect of their wrapper on performance, and it appears to be ~5%. See
lib/find_bit_benchmark_rust.rs.You are comparing the C vs. Rust data structures here, which is not what I am proposing.
Also, is this code being used on a "hot path" like the binder stuff is?
Quoted 8 lines
Quoted 4 lines
I didn't see any side-to-side comparison between any native Rust API vs imported C bitmaps. I'm sure, I asked for that, and I still believe it's the important piece of data to avoid this back-and-forth type of discussions. So, Alice, Burak or anybody...
Again, I'm not talking about Rust API vs. imported C bitmaps, I'm asking to use the C structures like maple-tree and idr instead of open-coding logic around the bitmap code.
Yeah, I agree that using maple tree avoids piling on more ID allocation implementations.
Channel ID allocation isn't on a hot path (absolute peak ~100 per second, on average < 1 per second, AFAICT).
I prototyped the implementation using maple tree [1]. It has some awkward points:
- Allocating aligned IDs needs a loop on top of MapleTreeAlloc::alloc_range + erase, which essentially replicates the logic in bitmap_find_next_zero_area
- Since aligned allocation may take multiple tries we still need exclusive access in ChannelIdPool::alloc_area to ensure an allocated but about to be erased non-aligned alloc doesn't make it look like we ran out of IDs. Alternatively, can do a try+restart kind of loop instead (needs adding bindings for mas_empty_area). [1] is using the extra Mutex.
- The alloc_area and Drop path of ChannelIdPool now allocates memory. I *think* this is okay but it is a consideration.
These tradeoffs weren't obvious to readers because I didn't include enough context in the patch series (and was going to add actual usage of the aligned alloc later).
Anyway, maple tree does work for this, so if you prefer I'm happy to go with it.
Thanks~
Alice Ryhl
maintainerRe: [PATCH 3/4] rust: id_pool: add contiguous area allocation
Quoted 90 lines · Eliot Courtney
Quoted 55 lines · Greg KH
Quoted 44 lines · Yury Norov
Quoted 24 lines · Greg KH
Quoted 23 lines · Eliot Courtney
Quoted 4 lines · Greg KH
Quoted 3 lines · Eliot Courtney
Add support for contiguous area allocation. Add a new type,
UnusedArea, following the same pattern asUnusedId.Quoted 8 lines
Quoted 1 line
Signed-off-by Eliot Courtney <[email protected]>Why isn't the built-in idr library being used here instead of rolling your own data structure?
thanks,
greg k-h
For nova-core in this series, we need allocation of a contiguous sequence of IDs with a specific length and sometimes a specific alignment. IIUC, IDA/xarray do not support that (I checked
ida_alloc_rangeand it only allocates a single ID in a range, not a contiguous sequence).For IdPool before this series, I think it could have used IDA/xarray. See [1] where Alice has posted some more context.
Quoted 7 lines
Quoted 3 lines
w.r.t. the structure choice, the IDs we need to allocate are channel IDs, and the total range is limited to 2048 of them, so IMO bitmaps are a better fit than e.g. maple tree.
But again, you are having to "roll your own" logic here, please reuse the data structures we already have in the kernel for this type of thing. If a maple tree works, please use it.
I asked exactly the same question when Alice and Burak added wrappers for bitmaps to implement their ID pool. This is the answer:
An alternative route of vendoring an existing Rust bitmap package was considered but suboptimal overall. Reusing the C implementation is preferable for a basic data structure like bitmaps. It enables Rust code to be a lot more similar and predictable with respect to C code that uses the same data structures and enables the use of code that has been tried-and-tested in the kernel, with the same performance characteristics whenever possible.
Quoted 4 lines
And now it's in a commit message:
11eca92a2caebThey measured the affect of their wrapper on performance, and it appears to be ~5%. See
lib/find_bit_benchmark_rust.rs.You are comparing the C vs. Rust data structures here, which is not what I am proposing.
Also, is this code being used on a "hot path" like the binder stuff is?
Quoted 8 lines
Quoted 4 lines
I didn't see any side-to-side comparison between any native Rust API vs imported C bitmaps. I'm sure, I asked for that, and I still believe it's the important piece of data to avoid this back-and-forth type of discussions. So, Alice, Burak or anybody...
Again, I'm not talking about Rust API vs. imported C bitmaps, I'm asking to use the C structures like maple-tree and idr instead of open-coding logic around the bitmap code.
Yeah, I agree that using maple tree avoids piling on more ID allocation implementations.
Channel ID allocation isn't on a hot path (absolute peak ~100 per second, on average < 1 per second, AFAICT).
I prototyped the implementation using maple tree [1]. It has some awkward points:
- Allocating aligned IDs needs a loop on top ofMapleTreeAlloc::alloc_range+ erase, which essentially replicates the logic inbitmap_find_next_zero_area
- Since aligned allocation may take multiple tries we still need exclusive access inChannelIdPool::alloc_areato ensure an allocated but about to be erased non-aligned alloc doesn't make it look like we ran out of IDs. Alternatively, can do a try+restart kind of loop instead (needs adding bindings formas_empty_area). [1] is using the extra Mutex.
- Thealloc_areaand Drop path ofChannelIdPoolnow allocates memory. I *think* this is okay but it is a consideration.These tradeoffs weren't obvious to readers because I didn't include enough context in the patch series (and was going to add actual usage of the aligned alloc later).
Quoted 6 lines
Anyway, maple tree does work for this, so if you prefer I'm happy to go with it.
Thanks~
If you need to make multiple allocation attemps to handle the alignment requirement, then I don't think maple tree is a good fit for your needs.
Alice
PATCH 4/4 gpu: nova-core: add ChannelIdPool
In reply to Eliot CourtneyAdd ChannelIdPool which adds automatic tracking and releasing of channel IDs on top of IdPool. This is necessary for apportioning ranges of channel IDs to be used in e.g. vGPU.
--- drivers/gpu/nova-core/gpu.rs | 2 + drivers/gpu/nova-core/gpu/channel.rs | 134 +++++++++++++++++++++++++++++++++++ 2 files changed, 136 insertions(+)
drivers/gpu/nova-core/gpu.rs +2 -0
@@ -31,6 +31,8 @@ regs, }; +#[cfg_attr(not( CONFIG_KUNIT = "y" ), expect(dead_code))] +mod channel;mod hal;macro_rules! define_chipset {
drivers/gpu/nova-core/gpu/channel.rs new file +134 -0
134 lines not on this page · raw message
Signature · 1 line
2.54.0
Alice Ryhl
maintainerQuoted 4 lines · Eliot Courtney
Add support for reserving of ranges of IDs, with a usage in nova-core for channel IDs. This entails adding the helpers+users of the C bitmap API for ranges of bits, then users of that in
IdPool, and finally a user ofIdPoolin nova-core,ChannelIdPool.
If you need ranges of IDs, perhaps you want the maple tree instead?
Alice
Gary Guo
reviewerQuoted 9 lines · Alice Ryhl
Quoted 4 lines · Eliot Courtney
Add support for reserving of ranges of IDs, with a usage in nova-core for channel IDs. This entails adding the helpers+users of the C bitmap API for ranges of bits, then users of that in
IdPool, and finally a user ofIdPoolin nova-core,ChannelIdPool.If you need ranges of IDs, perhaps you want the maple tree instead?
Alice
Any reason that the current ID pool is implemented directly on top of bitmap rather than using IDA?
Best,
Gary
Alice Ryhl
maintainerQuoted 7 lines · Gary Guo
Quoted 6 lines · Alice Ryhl
Quoted 4 lines · Eliot Courtney
Add support for reserving of ranges of IDs, with a usage in nova-core for channel IDs. This entails adding the helpers+users of the C bitmap API for ranges of bits, then users of that in
IdPool, and finally a user ofIdPoolin nova-core,ChannelIdPool.
Quoted 6 lines
Quoted 3 lines
If you need ranges of IDs, perhaps you want the maple tree instead?
Alice
Any reason that the current ID pool is implemented directly on top of bitmap rather than using IDA?
To some extent it's because that's how C Binder did it. Though I do also think that the bitmap fits binder's needs pretty well. Almost no Binder processes will have more than 8 handles in use, in which case the BitmapVec is extremely efficient because no allocation or pointer indirection is used. And the bitmap also performs well for the few processes with many external handles.
But it could also use the xarray instead. Nothing stopping that.
Alice
Quoted 9 lines · Alice Ryhl
Quoted 4 lines · Eliot Courtney
Add support for reserving of ranges of IDs, with a usage in nova-core for channel IDs. This entails adding the helpers+users of the C bitmap API for ranges of bits, then users of that in
IdPool, and finally a user ofIdPoolin nova-core,ChannelIdPool.If you need ranges of IDs, perhaps you want the maple tree instead?
Alice
I think maple tree would work, but it looked like not as good a fit to me because:
- the number of channel IDs is small (limited to 2048)
- allocation of a contiguous sequence of channel IDs is sometimes aligned to its size (which should be a power of two, AFAICT) - I realise patch 4 doesn't reflect this (yet). The bitmap APIs natively support this.
- maple tree's alloc_range stores a value: T for the range which isn't necessary for ID alloc
WDYT?
Alice Ryhl
maintainerQuoted 12 lines · Eliot Courtney
Quoted 9 lines · Alice Ryhl
Quoted 4 lines · Eliot Courtney
Add support for reserving of ranges of IDs, with a usage in nova-core for channel IDs. This entails adding the helpers+users of the C bitmap API for ranges of bits, then users of that in
IdPool, and finally a user ofIdPoolin nova-core,ChannelIdPool.If you need ranges of IDs, perhaps you want the maple tree instead?
Alice
Quoted 9 lines
I think maple tree would work, but it looked like not as good a fit to me because:
- the number of channel IDs is small (limited to 2048)
- allocation of a contiguous sequence of channel IDs is sometimes aligned to its size (which should be a power of two, AFAICT) - I realise patch 4 doesn't reflect this (yet). The bitmap APIs natively support this.
- maple tree'salloc_rangestores a value: T for the range which isn't necessary for ID alloc
The limited number of channel IDs (2048) is a good reason to use a bitmap. Please include this context in the commit message for the next version.
Alice