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

On Thu Jul 30, 2026 at 1:56 PM JST, Yury Norov wrote:
> On Wed, Jul 29, 2026 at 03:54:13PM +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.
>>=20
>> 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`.
>>=20
>> Add tests demonstrating the edge cases.
>>=20
>> Signed-off-by: Eliot Courtney <[email protected]>
>> ---
>>  rust/kernel/bitmap.rs | 194 +++++++++++++++++++++++++++++++++++++++++++=
+++++++
>>  1 file changed, 194 insertions(+)
>>=20
>> 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;
>> =20
>>  /// Represents a C bitmap. Wraps underlying C bitmap API.
>
> Some comments use indicative form in the file, but the imperative
> 'represent' is a more standard way. Can you please use it instead?

I think in rust, indicative is the standard even in the kernel - e.g.
see Documentation/rust/coding-guidelines.rst around line 208-ish, and
that's also what I see generally in code. But please let me know if
you'd like me to use it in this file regardless.

>
>> @@ -497,6 +498,116 @@ pub fn next_zero_bit(&self, start: usize) -> Optio=
n<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 =3D BitmapVec::new(64, GFP_KERNEL)?;
>> +    /// let unaligned =3D 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: Ali=
gnment) -> Option<usize> {
>
> Please create the rust wrapper next_zero_area_off() around
> bitmap_find_next_zero_area_off(), then in rust create the
> next_zero_area(), if you need it.

Will do.

>
>> +        bitmap_assert!(
>> +            start < self.len(),
>> +            "`start` must be < {}, was {}",
>> +            self.len(),
>> +            start
>> +        );
>> +
>> +        let nr =3D 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 =3D 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.
>
> No, we can't. We've got the test_bitmap_find_next_zero_area_off() for
> it (in next). If you think the test is incomplete, please extend it.
>
> If you believe that bitmap_find_next_zero_area_off() may return something
> like that, it means the function is buggy, and you shouldn't trust it at
> all.

TL;DR: Included some tests below that demonstrate overflow/OOB issues on
32-bit (with increased vmalloc) in some extreme cases. To keep the rust
code completely safe we need to check for these, or update the C code,
but not sure if the perf tradeoff is worth it. Please let me know.

Ok it seems I was looking at the code previous to df81d444dc74 ("lib:
bitmap: optimize bitmap_find_next_zero_area_off()"), but overflows can
still cause wrong behaviour after this commit too:

[1] On 32-bit, suppose we have an empty bitmap with size=3D=3D64, start=3D=
=3D32,
nr=3D=3D2^32-1, and align_mask=3D=3D0. Then, computing `end` overflows to 3=
1.
Computing `end - off` then underflows (31 - 32) which can cause OOB
reads. So actually we need a check before calling
`bitmap_find_next_zero_area_off` to avoid this case.

[2] On 32-bit, suppose we have a bitmap with size=3D=3D2^31+2 and all bits
set except the 0th and 2^31+1st bit, and start=3D=3D1, nr=3D=3D1,
align_mask=3D=3D2^31-1. We'll compute start=3D=3D2^31+1+2^31-1 which overfl=
ows
to 0. Then we'll end up returning 0 which is below start. So we need the
`index < start` check.

The C side function looks very perf sensitive to me which is why I
didn't update it (plus it's 32 bit only issues, essentially), instead
putting the checks in the rust side, but what do you reckon?

Previous to df81d444dc74 ("lib: bitmap: optimize
bitmap_find_next_zero_area_off()") overflow can happen and cause issues
although the cases are slightly different for what it's worth:

[3] On 32-bit, if we pass start + nr overflowing a u32 then bitmap.c
`end =3D index + nr;` can overflow and we can return a value less than the
size of the bitmap even though we couldn't possibly allocate something
of size `nr`. So the check of index.checked_add(nbits) is needed. For
example, in bitmap_find_next_zero_area_off, if size=3D=3D2, start=3D=3D1,
nr=3D2^32 - 1, align_mask=3D0, then we calculate index=3D=3D1 (if no bits i=
n the
bitmap), end=3D=3D0, i=3D=3D0, then return 1, even though we should return
something >=3D 2 to indicate it's not possible.

[4] Harder to trigger, but with a full bitmap (except the 0th bit) of
size=3D=3D2^31+1 on 32 bit hardware with start=3D=3D1, then we compute `ind=
ex =3D
find_next_zero_bit(map, size, start);` as index=3D=3D2^31+1, which then
overflows to 0 if align_mask=3D=3D2^31-1. Then for nr=3D=3D1 we have end=3D=
=3D1, and
compute i=3D=3D1 (since end=3D=3D1,index=3D=3D0 and the 0th bit is zero) an=
d return
0. So the check `index < start` is necessary.

Here are some tests demonstrating some of these issues:

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 56bd23059b26..0ba735aafefc 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -238,6 +238,7 @@ static void __init
 test_bitmap_find_next_zero_area_off(void)
 {
 	DECLARE_BITMAP(bmap, 192);
+	unsigned long *big;
=20
 	bitmap_set(bmap, 0, 192);
=20
@@ -269,6 +270,30 @@ test_bitmap_find_next_zero_area_off(void)
 		bitmap_find_next_zero_area_off(bmap, 192, 0, 32, 0, 0));
 	expect_eq_uint(1,
 		!!(bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) >=3D 192));
+
+	/* Reads out of bounds on 32-bit. */
+	bitmap_zero(bmap, 64);
+	expect_eq_uint(1,
+		!!(bitmap_find_next_zero_area_off(bmap, 64, 32, UINT_MAX, 0, 0) >=3D 64)=
);
+
+	big =3D kvmalloc_array(BITS_TO_LONGS(BIT(31) + 2), sizeof(*big), GFP_KERN=
EL);
+	if (big) {
+		/* Returns below start on 32-bit. */
+		big[0] =3D 0;
+		big[BIT_WORD(BIT(31) + 1)] =3D 0;
+		expect_eq_uint(1,
+			!!(bitmap_find_next_zero_area_off(big, BIT(31) + 2,
+							  BIT(31) + 1, 1,
+							  BIT(31) - 1, 0) >=3D BIT(31) + 2));
+
+		/* Reads out of bounds on 32-bit. */
+		big[BIT_WORD(BIT(31) - 2)] =3D 0;
+		expect_eq_uint(1,
+			!!(bitmap_find_next_zero_area_off(big, BIT(31) - 1,
+							  BIT(31) - 2, 3,
+							  BIT(31) - 1, 3) >=3D BIT(31) - 1));
+		kvfree(big);
+	}
 }
=20
 static void __init test_fill_set(void)

>
>> +        let end =3D index.checked_add(nbits)?;
>> +        if index < start || index >=3D self.len() || end > self.len() {
>> +            None
>> +        } else {
>> +            Some(index)
>> +        }
>
> So, this should be a simple:
>
>         (i < len).then_some(i)

For [3] we need the checked_add. For [2], [4] we need `index < start`.
`index >=3D self.len()` is the regular check. But you are right, we don't
need to check `end
> self.len()` here.

Alternatively, if we restrict Bitmap (not just BitmapVec) to a size of
i32::MAX and  check that `nbits <=3D self.len()` (to handle [1]) before
calling `bitmap_find_next_zero_area_off` then we can reduce this to just
`(i < len).then_some(i)` as you say. For non-zero offsets
(next_zero_area_off) we need an additional overflow check though.

>> +    }
>> +
>> +    /// Sets a contiguous area of `nbits` bits starting at `start`.
>> +    ///
>> +    /// If CONFIG_RUST_BITMAP_HARDENED is not enabled and the area `sta=
rt..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 <=3D self.len() && end <=3D 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.
>
> Not sure I understand. In the above assertion block you check for it,
> now you say it's always true...
>
> I think, your language should be similar to the
> find_next_zero_area_off() case: it's safe to call the function with
> the out-of-bounds start and nbits.

The assertion block still checks, even if CONFIG_RUST_BITMAP_HARDENED is
off (just prints an error returns in this case), so at this point we
know that the assert predicate is true. In this case, per the file
convention we take start and nbits in usize, but the C function doesn't,
so we need to make sure we don't truncate when converting to u32 and
i32. Also, it's not safe to call __bitmap_set with start and nbits such
that start+nbits is greater than self.len(), or we can write out of
bounds, so we can't use the same language + we need the check.

>
>> +        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 `sta=
rt..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 <=3D self.len() && end <=3D 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 u=
32, nbits as i32) };
>> +    }
>>  }
>> =20
>>  #[cfg(CONFIG_RUST_BITMAP_KUNIT_TEST)]
>> @@ -614,4 +725,87 @@ fn bitmap_copy_and_extend() -> Result<(), AllocErro=
r> {
>>          assert_eq!(Some(17), long_bitmap.last_bit());
>>          Ok(())
>>      }
>> +
>> +    #[test]
>> +    fn bitmap_area_set_clear_find() -> Result<(), AllocError> {
>> +        let mut b =3D BitmapVec::new(128, GFP_KERNEL)?;
>> +        let unaligned =3D 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 =3D BitmapVec::new(64, GFP_KERNEL)?;
>> +        let unaligned =3D 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 =3D 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(())
>> +    }
>>  }
>>=20
>> --=20
>> 2.55.0