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 <[email protected]>
> ---
> 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
