[PATCH v3 2/4] rust: bitmap: add contiguous area operations
From: Eliot Courtney
Date: Wed Jul 29 2026 - 02:54:57 EST
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.
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`.
Add tests demonstrating the edge cases.
Signed-off-by: Eliot Courtney <ecourtney@xxxxxxxxxx>
---
rust/kernel/bitmap.rs | 194 ++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 194 insertions(+)
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index a43bfe0ec3dc..f4b0b8ae39d8 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.
@@ -497,6 +498,116 @@ 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 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`. Alignments where `self.len() + align - 1`
+ /// overflows a `usize` can hang the underlying C code.
+ ///
+ /// # 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> {
+ bitmap_assert!(
+ start < self.len(),
+ "`start` must be < {}, was {}",
+ self.len(),
+ start
+ );
+
+ let nr = u32::try_from(nbits).ok()?;
+
+ // SAFETY: `bitmap_find_next_zero_area_off` is safe to use with an out of bounds `start`
+ // value and 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.as_usize() - 1,
+ 0,
+ )
+ };
+
+ // 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(&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 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() && 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 i32) };
+ }
}
#[cfg(CONFIG_RUST_BITMAP_KUNIT_TEST)]
@@ -614,4 +725,87 @@ 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]
+ #[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