diff options
Diffstat (limited to 'rust/kernel/bitmap.rs')
| -rw-r--r-- | rust/kernel/bitmap.rs | 353 |
1 files changed, 314 insertions, 39 deletions
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs index b27e0ec80d64..610d565535cc 100644 --- a/rust/kernel/bitmap.rs +++ b/rust/kernel/bitmap.rs @@ -10,31 +10,70 @@ use crate::alloc::{AllocError, Flags}; use crate::bindings; #[cfg(not(CONFIG_RUST_BITMAP_HARDENED))] use crate::pr_err; -use core::ptr::NonNull; +use crate::ptr::Alignment; +use core::{ + num::NonZero, + ptr::NonNull, // +}; /// Represents a C bitmap. Wraps underlying C bitmap API. /// /// # Invariants /// /// Must reference a `[c_ulong]` long enough to fit `data.len()` bits. +/// Must not be longer than [`i32::MAX`] bits, so offsets and lengths used with +/// [`Bitmap`] functions fit in the `int` and `unsigned int` arguments of the C bitmap API. +/// This also matches [`BitmapVec::MAX_LEN`]. #[cfg_attr(CONFIG_64BIT, repr(align(8)))] #[cfg_attr(not(CONFIG_64BIT), repr(align(4)))] pub struct Bitmap { data: [()], } +macro_rules! bitmap_assert { + ($cond:expr, $($arg:tt)+) => { + #[cfg(CONFIG_RUST_BITMAP_HARDENED)] + assert!($cond, $($arg)*); + } +} + +macro_rules! bitmap_assert_return { + ($cond:expr, $($arg:tt)+) => { + #[cfg(CONFIG_RUST_BITMAP_HARDENED)] + assert!($cond, $($arg)*); + + #[cfg(not(CONFIG_RUST_BITMAP_HARDENED))] + if !($cond) { + pr_err!($($arg)*); + return + } + } +} + impl Bitmap { /// Borrows a C bitmap. /// + /// # Panics + /// + /// Panics if CONFIG_RUST_BITMAP_HARDENED is enabled and `nbits` exceeds [`i32::MAX`]. + /// /// # Safety /// /// * `ptr` holds a non-null address of an initialized array of `unsigned long` /// that is large enough to hold `nbits` bits. + /// * `nbits` must not exceed [`i32::MAX`]. /// * the array must not be freed for the lifetime of this [`Bitmap`] /// * concurrent access only happens through atomic operations pub unsafe fn from_raw<'a>(ptr: *const usize, nbits: usize) -> &'a Bitmap { + bitmap_assert!( + nbits <= i32::MAX as usize, + "`nbits` must be <= {}, was {}", + i32::MAX, + nbits + ); let data: *const [()] = core::ptr::slice_from_raw_parts(ptr.cast(), nbits); // INVARIANT: `data` references an initialized array that can hold `nbits` bits. + // INVARIANT: The caller guarantees that `nbits` does not exceed `i32::MAX`. // SAFETY: // The caller guarantees that `data` (derived from `ptr` and `nbits`) // points to a valid, initialized, and appropriately sized memory region @@ -51,15 +90,27 @@ impl Bitmap { /// Borrows a C bitmap exclusively. /// + /// # Panics + /// + /// Panics if CONFIG_RUST_BITMAP_HARDENED is enabled and `nbits` exceeds [`i32::MAX`]. + /// /// # Safety /// /// * `ptr` holds a non-null address of an initialized array of `unsigned long` /// that is large enough to hold `nbits` bits. + /// * `nbits` must not exceed [`i32::MAX`]. /// * the array must not be freed for the lifetime of this [`Bitmap`] /// * no concurrent access may happen. pub unsafe fn from_raw_mut<'a>(ptr: *mut usize, nbits: usize) -> &'a mut Bitmap { + bitmap_assert!( + nbits <= i32::MAX as usize, + "`nbits` must be <= {}, was {}", + i32::MAX, + nbits + ); let data: *mut [()] = core::ptr::slice_from_raw_parts_mut(ptr.cast(), nbits); // INVARIANT: `data` references an initialized array that can hold `nbits` bits. + // INVARIANT: The caller guarantees that `nbits` does not exceed `i32::MAX`. // SAFETY: // The caller guarantees that `data` (derived from `ptr` and `nbits`) // points to a valid, initialized, and appropriately sized memory region @@ -96,26 +147,6 @@ union BitmapRepr { ptr: NonNull<usize>, } -macro_rules! bitmap_assert { - ($cond:expr, $($arg:tt)+) => { - #[cfg(CONFIG_RUST_BITMAP_HARDENED)] - assert!($cond, $($arg)*); - } -} - -macro_rules! bitmap_assert_return { - ($cond:expr, $($arg:tt)+) => { - #[cfg(CONFIG_RUST_BITMAP_HARDENED)] - assert!($cond, $($arg)*); - - #[cfg(not(CONFIG_RUST_BITMAP_HARDENED))] - if !($cond) { - pr_err!($($arg)*); - return - } - } -} - /// Represents an owned bitmap. /// /// Wraps underlying C bitmap API. See [`Bitmap`] for available @@ -415,7 +446,8 @@ impl Bitmap { #[inline] 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. + // SAFETY: Access to `self` and `src` is within bounds. Both lengths fit in `u32` + // because a `Bitmap` is at most `i32::MAX` bits, so the casts are lossless. unsafe { bindings::bitmap_copy_and_extend( self.as_mut_ptr(), @@ -459,7 +491,13 @@ impl Bitmap { /// Finds next set bit, starting from `start`. /// - /// Returns `None` if `start` is greater or equal to `self.nbits`. + /// Returns `None` if no bits are set on or after the given index. The + /// index `start` must be in bounds. + /// + /// # Panics + /// + /// Panics if `CONFIG_RUST_BITMAP_HARDENED` is enabled and `start` is + /// out of bounds. #[inline] pub fn next_bit(&self, start: usize) -> Option<usize> { bitmap_assert!( @@ -479,7 +517,14 @@ impl Bitmap { } /// Finds next zero bit, starting from `start`. - /// Returns `None` if `start` is greater than or equal to `self.len()`. + /// + /// Returns `None` if no bits are zero on or after the given index. The + /// index `start` must be in bounds. + /// + /// # Panics + /// + /// Panics if `CONFIG_RUST_BITMAP_HARDENED` is enabled and `start` is + /// out of bounds. #[inline] pub fn next_zero_bit(&self, start: usize) -> Option<usize> { bitmap_assert!( @@ -497,13 +542,159 @@ impl Bitmap { Some(index) } } + + /// Finds a contiguous area of `nbits` zero bits at or after `start`, where the area plus + /// `align_offset` is aligned to `align`. + /// + /// Returns the bit index of the start of the area, or [`None`] if no such area fitting in + /// the bitmap exists. + /// + /// The returned index plus `align_offset` is a multiple of `align`. + /// + /// # Panics + /// + /// Panics if CONFIG_RUST_BITMAP_HARDENED is enabled and `start` is out of bounds. + #[inline] + pub fn next_zero_area_off( + &self, + start: usize, + nbits: NonZero<usize>, + align: Alignment, + align_offset: usize, + ) -> Option<usize> { + bitmap_assert!( + start < self.len(), + "`start` must be < {}, was {}", + self.len(), + start + ); + + let nr = u32::try_from(nbits.get()).ok()?; + let align_mask = align.as_usize() - 1; + + // The C alignment and end arithmetic must not overflow, or it can read out of bounds. + // Overflow is only possible on 32-bit. + #[cfg(not(CONFIG_64BIT))] + align_mask + .checked_add(self.len())? + .checked_add(nbits.get())?; + + // SAFETY: `bitmap_find_next_zero_area_off` is safe to use with an out of bounds `start` + // value and, given the overflow check above, never reads beyond `self.len()` bits. + let index = unsafe { + bindings::bitmap_find_next_zero_area_off( + self.as_ptr().cast_mut(), + self.len(), + start, + nr, + align_mask, + align_offset, + ) + }; + + (index < self.len()).then_some(index) + } + + /// Finds a contiguous area of `nbits` zero bits at or after `start`, aligned to `align`. + /// + /// Returns the bit index of the start of the area, or [`None`] if no such area fitting in + /// the bitmap exists. + /// + /// The returned index is a multiple of `align`. + /// + /// # Panics + /// + /// Panics if CONFIG_RUST_BITMAP_HARDENED is enabled and `start` is out of bounds. + /// + /// # Examples + /// + /// ``` + /// use kernel::{ + /// alloc::{AllocError, flags::GFP_KERNEL}, + /// bitmap::BitmapVec, + /// ptr::Alignment, + /// sizes::SizeConstants, // + /// }; + /// + /// let mut b = BitmapVec::new(64, GFP_KERNEL)?; + /// + /// assert_eq!(Some(0), b.next_zero_area(0, cv!(8), Alignment::SZ_1)); + /// b.set(0, cv!(5)); + /// assert_eq!(Some(5), b.next_zero_area(0, cv!(8), Alignment::SZ_1)); + /// assert_eq!(Some(8), b.next_zero_area(0, cv!(8), Alignment::SZ_8)); + /// assert_eq!(None, b.next_zero_area(0, cv!(65), Alignment::SZ_1)); + /// # Ok::<(), AllocError>(()) + /// ``` + #[inline] + pub fn next_zero_area( + &self, + start: usize, + nbits: NonZero<usize>, + align: Alignment, + ) -> Option<usize> { + self.next_zero_area_off(start, nbits, align, 0) + } + + /// 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(&mut self, start: usize, nbits: NonZero<usize>) { + bitmap_assert_return!( + start + .checked_add(nbits.get()) + .is_some_and(|end| end <= self.len()), + "Area `start..start + nbits` ({}..{}) must be within bounds {}", + start, + start.saturating_add(nbits.get()), + self.len() + ); + // SAFETY: The area `start..start + nbits` is within bounds and a `Bitmap` is at most + // `i32::MAX` bits, so the casts are lossless. + unsafe { bindings::__bitmap_set(self.as_mut_ptr(), start as u32, nbits.get() as i32) }; + } + + /// 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(&mut self, start: usize, nbits: NonZero<usize>) { + bitmap_assert_return!( + start + .checked_add(nbits.get()) + .is_some_and(|end| end <= self.len()), + "Area `start..start + nbits` ({}..{}) must be within bounds {}", + start, + start.saturating_add(nbits.get()), + self.len() + ); + // SAFETY: The area `start..start + nbits` is within bounds and a `Bitmap` is at most + // `i32::MAX` bits, so the casts are lossless. + unsafe { bindings::__bitmap_clear(self.as_mut_ptr(), start as u32, nbits.get() as i32) }; + } } #[cfg(CONFIG_RUST_BITMAP_KUNIT_TEST)] #[macros::kunit_tests(rust_kernel_bitmap)] mod tests { use super::*; - use kernel::alloc::flags::GFP_KERNEL; + use kernel::{ + alloc::flags::GFP_KERNEL, + num::cv, + sizes::SizeConstants, // + }; #[test] fn bitmap_borrow() { @@ -572,24 +763,21 @@ mod tests { } #[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] @@ -617,4 +805,91 @@ mod tests { 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, cv!(5), Alignment::SZ_1)); + b.set(0, cv!(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, cv!(5), Alignment::SZ_1)); + assert_eq!(Some(8), b.next_zero_area(0, cv!(5), Alignment::SZ_8)); + + b.set(8, cv!(8)); // Now contains {[0, 5), [8, 16)}. + assert_eq!(Some(16), b.next_zero_area(0, cv!(4), Alignment::SZ_16)); + assert_eq!(Some(16), b.next_zero_area(0, cv!(4), Alignment::SZ_1)); + + b.clear(0, cv!(5)); // Now contains {[8, 16)}. + assert_eq!(Some(0), b.next_zero_area(0, cv!(5), Alignment::SZ_1)); + assert_eq!(Some(8), b.next_bit(0)); + assert_eq!(Some(15), b.last_bit()); + + b.set(60, cv!(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, cv!(40), Alignment::SZ_1)); + assert_eq!(Some(70), b.next_zero_area(0, cv!(45), Alignment::SZ_1)); + + b.clear(62, cv!(6)); // Now contains {[8, 16), [60, 62), [68, 70)}. + assert_eq!(Some(62), b.next_zero_area(60, cv!(6), Alignment::SZ_1)); + assert_eq!(Some(61), b.next_bit(61)); + assert_eq!(Some(69), b.last_bit()); + Ok(()) + } + + #[test] + fn bitmap_area_exhaustion() -> Result<(), AllocError> { + let mut b = BitmapVec::new(64, GFP_KERNEL)?; + + assert_eq!(None, b.next_zero_area(0, cv!(65), Alignment::SZ_1)); + assert_eq!(None, b.next_zero_area(0, cv!(usize::MAX), Alignment::SZ_1)); + assert_eq!(None, b.next_zero_area(1, cv!(usize::MAX), Alignment::SZ_1)); + + b.set_bit(0); // Now contains {[0, 1)}. + assert_eq!(None, b.next_zero_area(0, cv!(usize::MAX), Alignment::SZ_1)); + + b.set(0, cv!(61)); // Now contains {[0, 61)}. + assert_eq!(None, b.next_zero_area(0, cv!(4), Alignment::SZ_1)); + assert_eq!(Some(61), b.next_zero_area(0, cv!(3), Alignment::SZ_1)); + assert_eq!(None, b.next_zero_area(0, cv!(1), Alignment::SZ_64)); + Ok(()) + } + + #[test] + fn bitmap_area_off() -> Result<(), AllocError> { + let mut b = BitmapVec::new(64, GFP_KERNEL)?; + + b.set(0, cv!(5)); // Now contains {[0, 5)}. + + // The area plus align_offset starts at a multiple of the alignment. + assert_eq!(Some(7), b.next_zero_area_off(0, cv!(8), Alignment::SZ_8, 1)); + assert_eq!(Some(5), b.next_zero_area_off(0, cv!(8), Alignment::SZ_8, 3)); + + // A zero offset behaves like next_zero_area(). + assert_eq!( + b.next_zero_area(0, cv!(8), Alignment::SZ_8), + b.next_zero_area_off(0, cv!(8), Alignment::SZ_8, 0) + ); + 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(64, cv!(4)); + b.set(62, cv!(8)); + b.set(usize::MAX, cv!(1)); + b.clear(usize::MAX, cv!(1)); + b.clear(2048, cv!(8)); + assert_eq!(None, b.next_bit(0)); + assert_eq!(None, b.next_zero_area(64, cv!(1), Alignment::SZ_1)); + Ok(()) + } } |