Re: [PATCH v7 05/10] rust: bitmap: add contiguous area operations

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

On Fri Aug 21, 2026 at 5:11 PM JST, Alexandre Courbot wrote:
> On Mon Aug 17, 2026 at 4:04 PM JST, 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 <ecourtney@nvidia.com>
>> ---
>>  rust/kernel/bitmap.rs | 242 +++++++++++++++++++++++++++++++++++++++++++++++++-
>>  1 file changed, 240 insertions(+), 2 deletions(-)
>>
>> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
>> index fdcfc0409773..a4997022ff0f 100644
>> --- a/rust/kernel/bitmap.rs
>> +++ b/rust/kernel/bitmap.rs
>> @@ -10,7 +10,11 @@
>>  use crate::bindings;
>>  #[cfg(not(CONFIG_RUST_BITMAP_HARDENED))]
>>  use crate::pr_err;
>> -use core::ptr::NonNull;
>> +use crate::ptr::Alignment;
>> +use core::{
>> +    num::NonZero,
>> +    ptr::NonNull, //
>> +};
>>  
>>  /// Represents a C bitmap. Wraps underlying C bitmap API.
>>  ///
>> @@ -523,13 +527,160 @@ 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: NonZero<usize>,
>> +        align: Alignment,
>> +        align_offset: usize,
>> +    ) -> Option<usize> {
>> +        bitmap_assert!(
>> +            start < self.len(),
>> +            "`start` must be < {}, was {}",
>> +            self.len(),
>> +            start
>> +        );
>
> Do we need to potentially panic here if `start >= self.len()`? The
> question "is there an area of `nbits` bits after my bounds" can be
> answered by "there is `None`" without semantically sounding weird; and
> this test doesn't cover `start + nbits >= self.len()`, which should
> logically also be considered to be consistent. It seems like the C API
> also tolerates this, so as this is not a safety issue I guess the Rust
> one should do the same?
>
> If anything I'd say we should remove these tests from
> `next_bit`/`next_zero_bit` as well.
>
> Mutating methods should definitely keep that check, but for querying
> this looks like a legitimate way to use the API.

Yeah, I am following the convention of this file - e.g. `next_zero_bit`
has this same check as you have noted, presumably because these bindings
want to consider calling with start >= self.len() to be not intended
behaviour that's worth warning on? I personally don't mind, but I think
we should either have it on all of them or on none of them. For now, I
have kept them in to match the file convention but we could remove them
or convert to debug_assert! in a follow-up?

>
>> +
>> +        let nr = u32::try_from(nbits.get()).ok()?;
>> +        let align_mask = align.as_usize() - 1;
>> +
>> +        // The C alignment and end arithmetic must not overflow, or it can read out of bounds.
>> +        // Overflow is only possible on 32-bit.
>> +        #[cfg(not(CONFIG_64BIT))]
>> +        align_mask
>> +            .checked_add(self.len())?
>> +            .checked_add(nbits.get())?;
>
> Is it ok to not consider `align_offset` here? The C code adds it, and
> the result could overflow on large values, even on 64-bit.

It is ok not to consider it but the reason is very subtle. The tldr is
that align_offset only affects the important value by at most
`align_mask`.

Here is the latest `bitmap_find_next_zero_area_off` code on
bitmap-for-next:
```
unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
					     unsigned long size,
					     unsigned long start,
					     unsigned int nr,
					     unsigned long align_mask,
					     unsigned long align_offset)
{
	unsigned long end, i, off;

	for_each_clear_bit_from(start, map, size) {
		start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset;
		end = start + nr;
		if (end > size)
			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;

		start = i;
	}

	return size;
}
```

It has
```
start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset;
```

__ALIGN_MASK does this:
```
(((x) + (mask)) & ~(mask))
```

So it's

```
((start + align_offset + align_mask) & ~align_mask) - align_offset
```

A & ~B where B is (2**k - 1) == A - A % 2**k, so we have

```
start + align_offset + align_mask - (start + align_offset + align_mask)%2**k - align_offset
```

So you can cancel the two align_offsets and get

```
start + align_mask - (start + align_offset + align_mask)%2**k
```

Since (start + align_offset + align_mask)%2**k <= align_mask, the only
way you can overflow your expression is through align_mask, not
align_offset. The upper bound of the expression is start' <= `start +
align_mask`.

We get the overflow/OOB read path if end overflows so `if (end > size)`
becomes wrong. `for_each_clear_bit_from` guarantees that start < size in
the body of the loop. So when we compute `end = start' + nr`, the upper
bound is `start + align_mask + nr` - that's the check here. We know
start < i32::MAX (thanks to the invariants we added) and align_mask <=
isize::MAX, and nr <= u32::MAX. So the total upper bound is `i32::MAX +
isize::MAX + u32::MAX`. This fits into `unsigned long` on 64 bit but not
on 32 bit, hence the cfg to only 32-bit.