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_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. Signed-off-by: Eliot Courtney <[email protected]> --- rust/helpers/bitmap.c | 22 +++++ rust/kernel/bitmap.rs | 219 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 241 insertions(+) diff --git a/rust/helpers/bitmap.c b/rust/helpers/bitmap.c index e4e9f4361270..dac5c03f2448 100644 --- a/rust/helpers/bitmap.c +++ b/rust/helpers/bitmap.c @@ -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); +} diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index a43bfe0ec3dc..f7290fa439d6 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -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()); + + bitmap_assert!( + valid_align_mask, + "`align_mask` must be 0 or `2^k - 1`, was {}", + align_mask + ); + + if !valid_align_mask { + return None; + } + + 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`. + /// + /// 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) { + 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(), start as u32, nbits as u32) }; + } + + /// Clears a contiguous area of `nbits` bits starting at `start`. + /// + /// 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) { + 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(), start as u32, nbits as 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(()) + } } -- 2.54.0
