Re: [PATCH v9 6/9] rust: bitmap: add contiguous area operations

[Yury Norov <ynorov@nvidia.com>]

On Wed, Sep 30, 2026 at 11:42:55AM +0900, Eliot Courtney wrote:
> Add bindings 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.
> 
> Add tests demonstrating the edge cases.
> 
> Reviewed-by: Burak Emir <burak.emir@gmail.com>
> Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
> ---
>  rust/kernel/bitmap.rs | 241 +++++++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 239 insertions(+), 2 deletions(-)
> 
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> index df5505ec7a96..23c2b43a98ac 100644
> --- a/rust/kernel/bitmap.rs
> +++ b/rust/kernel/bitmap.rs
> @@ -10,7 +10,11 @@
>  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.
>  ///
> @@ -525,13 +529,159 @@ pub fn next_zero_bit(&self, start: usize) -> Option<usize> {
>              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>) {

I'm still not convinced about having this non-standard parameter types
in function declaration, but ... let's give it a try.

The rest looks OK, so

Reviewed-by: Yury Norov <yury.norov@gmail.com>

> +        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() {
> @@ -642,4 +792,91 @@ 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, 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(())
> +    }
>  }
> 
> -- 
> 2.55.0