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

["Eliot Courtney" <ecourtney@nvidia.com>]

On Tue Aug 4, 2026 at 6:44 AM JST, Yury Norov wrote:
> On Mon, Aug 03, 2026 at 09:41:42PM +0900, Eliot Courtney wrote:
>> 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.
>> >> 
>> >> 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@nvidia.com>
>> >> ---
>> >>  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.
>> >
>> > 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.
>
> The documentation you've mentioned doesn't say: use indicative. This
> is just a one example.
>  
> This is what my AI machine says:
>
>   Among the 1,266 verb-led function comments, that is:
>
>   - 67.1% indicative
>   - 32.9% imperative
>
> So, unless there's a strong (and not aligning with the rest of the
> kernel) rule, please use imperative form in bitmaps.

Yeah I got a similar result using my AI machine too~~

There is a strong rule for rust specifically and it's encoded in RFC
1574 [1].

[1]: https://github.com/rust-lang/rfcs/blob/master/text/1574-more-api-documentation-conventions.md#summary-sentence

>
> ...
>
>> >> +        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.
>> >
>> > 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==64, start==32,
>> nr==2^32-1, and align_mask==0. Then, computing `end` overflows to 31.
>> 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==2^31+2 and all bits
>> set except the 0th and 2^31+1st bit, and start==1, nr==1,
>> align_mask==2^31-1. We'll compute start==2^31+1+2^31-1 which overflows
>> to 0. Then we'll end up returning 0 which is below start. So we need the
>> `index < start` check.
>
> Both examples overflow int32::MAX. It is not supported in rust.
> See the BitmapVec code. Your case is just 2048 bits, so it's not
> a limitation for you.
>
> On the C side, there's a historical mess - some functions work with
> unsigned longs, some with unsigned ints, and so on. I'm aware of it,
> and there's a process of unification the API toward the unsigned
> longs. That wouldn't help 32-bit architectures because they are all
> ILP32, but there's no real use case for them that would overflow the
> 32 bit.

Currently it's possible to construct a non-BitmapVec backed Bitmap using
Bitmap::from_raw that is larger than i32::MAX, and it's not part of the
unsafe requirements. If we can restrict all Bitmaps (even non-BitmapVec
backed ones) to have a max size of i32::MAX then that simplifies a few
things. If ok, I'll add a patch adding that requirement to the unsafe
requirements on Bitmap::from_raw, Bitmap::from_raw_mut, and the
invariants on Bitmap.

But, if we want to keep the rust code completely safe even with
requiring all Bitmaps to have max length i32::MAX we still need a check
somewhere since OOB reads can occur even for a small bitmap. IIUC, we
want to make sure all rust code is safe regardless of the inputs.

In particular, we need to check that `self.len() + align - 1 + nbits`
does not overflow in `Bitmap::next_zero_area`. e.g. on bitmap-for-next,
an empty bitmap with size==2 called with
Bitmap::next_zero_area(start==1, nbits==2^31, align==2^31) reads OOB (on
32-bit).

Alternatively, an exact fix for this in the C implementation is as
follows (obviating any need for the rust side check I mentioned above).
I briefly benchmarked it (region_alloc_benchmark) and didn't see a
slowdown, at least on x64. I'm not necessarily suggesting this, since in
C I think the answer is just don't call with nonsense parameters, but
just for reference:

diff --git a/lib/bitmap.c b/lib/bitmap.c
index ed685127a107..e500091c7e6a 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -435,18 +435,21 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 					     unsigned long align_mask,
 					     unsigned long align_offset)
 {
-	unsigned long end, i, off;
+	unsigned long index, end, i, off;
+
+	if (nr > size)
+		return size;
 
 	for_each_clear_bit_from(start, map, size) {
-		start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset;
-		end = start + nr;
-		if (end > size)
+		index = __ALIGN_MASK(start + align_offset, align_mask) - align_offset;
+		if (index < start || index > size - nr)
 			break;
 
-		off = round_down(start, BITS_PER_LONG);
-		i = find_last_bit(map + start / BITS_PER_LONG, end - off) + off;
-		if (i >= end || i < start)
-			return start;
+		end = index + nr;
+		off = round_down(index, BITS_PER_LONG);
+		i = find_last_bit(map + index / BITS_PER_LONG, end - off) + off;
+		if (i >= end || i < index)
+			return index;
 
 		start = i;
 	}