Re: [PATCH 2/4] rust: bitmap: add contiguous area operations

[Yury Norov <ynorov@nvidia.com>]

On Fri, Jul 03, 2026 at 07:16:05PM +0900, Eliot Courtney wrote:
> 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 <ecourtney@nvidia.com>
> ---
>  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);
> +}

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.

> 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;
> +        }

This quite a trivial check takes about a half of the function in terms
of LOCs. Is there any way to compact it?

> +        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) {

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()".

> +        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) {

Same here: .clear(), please

> +        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