On Mon, Aug 10, 2026 at 05:34:11PM +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.
>
> Signed-off-by: Eliot Courtney <[email protected]>
> ---
> rust/kernel/bitmap.rs | 235
> ++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 235 insertions(+)
>
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> index 0d481d761f2a..a2557e9c5cfe 100644
> --- a/rust/kernel/bitmap.rs
> +++ b/rust/kernel/bitmap.rs
> @@ -10,6 +10,7 @@
> use crate::bindings;
> #[cfg(not(CONFIG_RUST_BITMAP_HARDENED))]
> use crate::pr_err;
> +use crate::ptr::Alignment;
> use core::ptr::NonNull;
>
> /// Represents a C bitmap. Wraps underlying C bitmap API.
> @@ -503,6 +504,138 @@ 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: 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).ok()?;
> +
> + // The C alignment and end arithmetic must not overflow, or it can
> read out of bounds.
> + // Overflow is only possible on 32-bit.
That doesn't sound optimistic. Can you add a check for 32-bit case?
The rest looks good.
Thanks,
Yury
> + let align_mask = align.as_usize() - 1;
> + align_mask.checked_add(self.len())?.checked_add(nbits)?;
> +
> + // 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};
> + /// use kernel::bitmap::BitmapVec;
> + /// use kernel::ptr::Alignment;
> + ///
> + /// let mut b = BitmapVec::new(64, GFP_KERNEL)?;
> + /// let unaligned = Alignment::new::<1>();
> + ///
> + /// assert_eq!(Some(0), b.next_zero_area(0, 8, unaligned));
> + /// b.set(0, 5);
> + /// assert_eq!(Some(5), b.next_zero_area(0, 8, unaligned));
> + /// assert_eq!(Some(8), b.next_zero_area(0, 8, Alignment::new::<8>()));
> + /// assert_eq!(None, b.next_zero_area(0, 65, unaligned));
> + /// # Ok::<(), AllocError>(())
> + /// ```
> + #[inline]
> + pub fn next_zero_area(&self, start: usize, nbits: 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: usize) {
> + bitmap_assert_return!(
> + start
> + .checked_add(nbits)
> + .is_some_and(|end| end <= self.len()),
> + "Area `start..start + nbits` ({}..{}) must be within bounds {}",
> + start,
> + start.saturating_add(nbits),
> + 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 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: usize) {
> + bitmap_assert_return!(
> + start
> + .checked_add(nbits)
> + .is_some_and(|end| end <= self.len()),
> + "Area `start..start + nbits` ({}..{}) must be within bounds {}",
> + start,
> + start.saturating_add(nbits),
> + 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 as i32) };
> + }
> }
>
> #[cfg(CONFIG_RUST_BITMAP_KUNIT_TEST)]
> @@ -620,4 +753,106 @@ 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)?;
> + let unaligned = Alignment::new::<1>();
> +
> + assert_eq!(Some(0), b.next_zero_area(0, 5, unaligned));
> + b.set(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, unaligned));
> + assert_eq!(Some(8), b.next_zero_area(0, 5, Alignment::new::<8>()));
> +
> + b.set(8, 8); // Now contains {[0, 5), [8, 16)}.
> + assert_eq!(Some(16), b.next_zero_area(0, 4, Alignment::new::<16>()));
> + assert_eq!(Some(16), b.next_zero_area(0, 4, unaligned));
> +
> + b.clear(0, 5); // Now contains {[8, 16)}.
> + assert_eq!(Some(0), b.next_zero_area(0, 5, unaligned));
> + assert_eq!(Some(8), b.next_bit(0));
> + assert_eq!(Some(15), b.last_bit());
> +
> + b.clear(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, unaligned));
> + assert_eq!(Some(8), b.next_zero_area(1, 0, Alignment::new::<8>()));
> +
> + b.set(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, unaligned));
> + assert_eq!(Some(70), b.next_zero_area(0, 45, unaligned));
> +
> + b.clear(62, 6); // Now contains {[8, 16), [60, 62), [68, 70)}.
> + assert_eq!(Some(62), b.next_zero_area(60, 6, unaligned));
> + assert_eq!(Some(61), b.next_bit(61));
> + assert_eq!(Some(69), b.last_bit());
> +
> + b.set(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)?;
> + let unaligned = Alignment::new::<1>();
> +
> + assert_eq!(None, b.next_zero_area(0, 65, unaligned));
> + assert_eq!(None, b.next_zero_area(0, usize::MAX, unaligned));
> + assert_eq!(None, b.next_zero_area(1, usize::MAX, unaligned));
> +
> + b.set_bit(0); // Now contains {[0, 1)}.
> + assert_eq!(None, b.next_zero_area(0, usize::MAX, unaligned));
> +
> + b.set(0, 61); // Now contains {[0, 61)}.
> + assert_eq!(None, b.next_zero_area(0, 4, unaligned));
> + assert_eq!(Some(61), b.next_zero_area(0, 3, unaligned));
> + assert_eq!(None, b.next_zero_area(0, 1, Alignment::new::<64>()));
> + Ok(())
> + }
> +
> + #[test]
> + fn bitmap_area_off() -> Result<(), AllocError> {
> + let mut b = BitmapVec::new(64, GFP_KERNEL)?;
> + let align8 = Alignment::new::<8>();
> +
> + b.set(0, 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, 8, align8, 1));
> + assert_eq!(Some(5), b.next_zero_area_off(0, 8, align8, 3));
> +
> + // A zero offset behaves like next_zero_area().
> + assert_eq!(
> + b.next_zero_area(0, 8, align8),
> + b.next_zero_area_off(0, 8, align8, 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, 4);
> + b.set(62, 8);
> + b.set(usize::MAX, 0);
> + b.clear(usize::MAX, 0);
> + b.clear(2048, 8);
> + assert_eq!(None, b.next_bit(0));
> + assert_eq!(None, b.next_zero_area(64, 1, Alignment::new::<1>()));
> + Ok(())
> + }
> }
>
> --
> 2.55.0
