[PATCH v3 0/4] rust: Add support for reserving of ranges of IDs

[PATCH v3 0/4] rust: Add support for reserving of ranges of IDs

[Eliot Courtney]

Add support for reserving of ranges of IDs, with a usage in nova-core
for channel IDs. This entails adding bindings for the C bitmap
API for ranges of bits, then users of that in `IdPool`, and finally a
user of `IdPool` in nova-core, `ChannelIdPool`.

Channel ID tracking is needed for allotting ranges of channel IDs to
vGPU guests, and later for regular host channel ID reservation.
nova-core needs allocation of a contiguous sequence of IDs with a
specific length and sometimes a specific alignment [1].

About the tradeoffs between different data structures:
- IDA/xarray do not support allocating a contiguous sequence of IDs
  (ida_alloc_range() allocates a single ID within a range, not a contiguous
  sequence).
- A maple tree works, but is not as good a fit. The ID space is small
  (limited to 2048) and aligned allocation needs an alloc_range()+erase() retry
  loop (plus a Mutex around it, or new mas_empty_area() bindings) that
  essentially reimplements bitmap_find_next_zero_area(). See the maple tree
  version at [2]. For 2048 IDs a bitmap is also considerably faster and smaller
  [3].
- The bitmap API natively supports aligned contiguous area allocation
  (bitmap_find_next_zero_area()).

This is based on drm-rust-next.

[1]: https://lore.kernel.org/all/84bc8bd2-e292-4b84-9580-a1b5df4c5bdc@nvidia.com/
[2]: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/
[3]: https://lore.kernel.org/all/20260717053241.916441-1-ynorov@nvidia.com/

Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
---
Changes in v3:
- Use `Alignment` type in id_pool and bitmap (Alice)
- Remove hang check on the basis that it's extraordinarily rare.
- Link to v2: https://patch.msgid.link/20260723-chid-v2-0-c35e5e9fb3d9@nvidia.com

Changes in v2:
- Collected Alice's Reviewed-by on patch 1.
- Address Yury's comments w.r.t. using __bitmap_set etc directly.
- Address Yury's comments w.r.t. following the C names
- Additionally check for an overflow case that causes a hang
- Added more info to cover letter + patch 4 w.r.t. channel ID allottment
  requirements
- Add align parameter to ChannelIdPool::alloc_area() plus an aligned
  allocation test
- Add missing INVARIANT comment when constructing UnusedArea
- Link to v1:
  https://patch.msgid.link/20260703-chid-v1-0-84fe8259e46e@nvidia.com

---
Eliot Courtney (4):
      rust: bitmap: use function-level cfg on kunit test
      rust: bitmap: add contiguous area operations
      rust: id_pool: add contiguous area allocation
      gpu: nova-core: add ChannelIdPool

 drivers/gpu/nova-core/gpu.rs         |   2 +
 drivers/gpu/nova-core/gpu/channel.rs | 180 ++++++++++++++++++++++++++++
 rust/kernel/bitmap.rs                | 219 ++++++++++++++++++++++++++++++++---
 rust/kernel/id_pool.rs               |  69 +++++++++++
 4 files changed, 456 insertions(+), 14 deletions(-)
---
base-commit: 6dcbb4b1320fa91fee349462a52bb69135f2e45e
change-id: 20260608-chid-18fa943c6d6c

Best regards,
--  
Eliot Courtney <ecourtney@nvidia.com>

[PATCH v3 1/4] rust: bitmap: use function-level cfg on kunit test

[Eliot Courtney]

Since commit c652dc44192d ("rust: kunit: allow `cfg` on `test`s"),
we no longer need this workaround.

Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
---
 rust/kernel/bitmap.rs | 25 +++++++++++--------------
 1 file changed, 11 insertions(+), 14 deletions(-)

diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index b27e0ec80d64..a43bfe0ec3dc 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -572,24 +572,21 @@ fn bitmap_set_clear_find() -> Result<(), AllocError> {
     }
 
     #[test]
+    #[cfg(not(CONFIG_RUST_BITMAP_HARDENED))]
     fn owned_bitmap_out_of_bounds() -> Result<(), AllocError> {
-        // TODO: Kunit #[test]s do not support `cfg` yet,
-        // so we add it here in the body.
-        #[cfg(not(CONFIG_RUST_BITMAP_HARDENED))]
-        {
-            let mut b = BitmapVec::new(128, GFP_KERNEL)?;
-            b.set_bit(2048);
-            b.set_bit_atomic(2048);
-            b.clear_bit(2048);
-            b.clear_bit_atomic(2048);
-            assert_eq!(None, b.next_bit(2048));
-            assert_eq!(None, b.next_zero_bit(2048));
-            assert_eq!(None, b.last_bit());
-        }
+        let mut b = BitmapVec::new(128, GFP_KERNEL)?;
+
+        b.set_bit(2048);
+        b.set_bit_atomic(2048);
+        b.clear_bit(2048);
+        b.clear_bit_atomic(2048);
+        assert_eq!(None, b.next_bit(2048));
+        assert_eq!(None, b.next_zero_bit(2048));
+        assert_eq!(None, b.last_bit());
         Ok(())
     }
 
-    // TODO: uncomment once kunit supports [should_panic] and `cfg`.
+    // TODO: uncomment once kunit supports `#[should_panic]`.
     // #[cfg(CONFIG_RUST_BITMAP_HARDENED)]
     // #[test]
     // #[should_panic]

-- 
2.55.0

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

[Eliot Courtney]

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.
@@ -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

[PATCH v3 3/4] rust: id_pool: add contiguous area allocation

[Eliot Courtney]

Add support for contiguous area allocation. Add a new type,
`UnusedArea`, following the same pattern as `UnusedId`.

Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
---
 rust/kernel/id_pool.rs | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index 384753fe0e44..eb911a0e3217 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -4,8 +4,14 @@
 
 //! Rust API for an ID pool backed by a [`BitmapVec`].
 
+use core::{
+    num::NonZero,
+    ops::Range, //
+};
+
 use crate::alloc::{AllocError, Flags};
 use crate::bitmap::BitmapVec;
+use crate::ptr::Alignment;
 
 /// Represents a dynamic ID pool backed by a [`BitmapVec`].
 ///
@@ -240,6 +246,33 @@ pub fn find_unused_id(&mut self, offset: usize) -> Option<UnusedId<'_>> {
     pub fn release_id(&mut self, id: usize) {
         self.map.clear_bit(id);
     }
+
+    /// Finds a contiguous area of `count` unused IDs at or after `offset`.
+    ///
+    /// The start of the returned area is a multiple of `align`.
+    ///
+    /// Returns an [`UnusedArea`] upon success, or [`None`] if no such area could be found.
+    #[inline]
+    #[must_use]
+    pub fn find_unused_area(
+        &mut self,
+        offset: usize,
+        count: NonZero<usize>,
+        align: Alignment,
+    ) -> Option<UnusedArea<'_>> {
+        let start = self.map.next_zero_area(offset, count.get(), align)?;
+        // INVARIANT: `next_zero_area()` returns None or a start with `start + count <= map.len()`.
+        Some(UnusedArea {
+            range: start..start + count.get(),
+            pool: self,
+        })
+    }
+
+    /// Releases a contiguous area of IDs.
+    #[inline]
+    pub fn release_area(&mut self, range: &Range<usize>) {
+        self.map.clear(range.start, range.len());
+    }
 }
 
 /// Represents an unused id in an [`IdPool`].
@@ -287,6 +320,42 @@ pub fn acquire(self) -> usize {
     }
 }
 
+/// Represents an unused, contiguous area of IDs in an [`IdPool`].
+///
+/// # Invariants
+///
+/// `range.start <= range.end <= pool.map.len()`.
+#[must_use = "the ID range is not reserved unless acquired"]
+pub struct UnusedArea<'pool> {
+    range: Range<usize>,
+    pool: &'pool mut IdPool,
+}
+
+impl<'pool> UnusedArea<'pool> {
+    /// Returns the unused ID range.
+    ///
+    /// Be aware that the area has not yet been acquired in the pool. The
+    /// [`acquire`] method must be called to prevent others from taking it.
+    ///
+    /// [`acquire`]: UnusedArea::acquire()
+    #[inline]
+    #[must_use]
+    pub fn range(&self) -> Range<usize> {
+        self.range.clone()
+    }
+
+    /// Acquires the area.
+    ///
+    /// Returns the now-reserved ID range.
+    #[inline]
+    pub fn acquire(self) -> Range<usize> {
+        let Self { range, pool } = self;
+        // By the type invariants, the range is within bounds.
+        pool.map.set(range.start, range.end - range.start);
+        range
+    }
+}
+
 impl Default for IdPool {
     #[inline]
     fn default() -> Self {

-- 
2.55.0

[PATCH v3 4/4] gpu: nova-core: add ChannelIdPool

[Eliot Courtney]

Add `ChannelIdPool` which adds automatic tracking and releasing of
channel IDs on top of `IdPool`. This is necessary for apportioning
ranges of channel IDs to be used in e.g. vGPU.

Channel IDs are allocated as a contiguous sequence with a specific
length and sometimes a specific alignment [1] for vGPU. The ID space is
small (limited to 2048) and allocation is not on a hot path, so a
bitmap-backed `IdPool` is a better fit than IDA/xarray (which allocate a
single ID within a range, not a contiguous sequence) or a maple tree
(where aligned allocation needs an alloc_range()+erase() retry loop that
essentially reimplements bitmap_find_next_zero_area()) [2]. It is
also faster than maple tree [3].

Link: https://lore.kernel.org/all/84bc8bd2-e292-4b84-9580-a1b5df4c5bdc@nvidia.com/ # [1]
Link: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/ # [2]
Link: https://lore.kernel.org/all/20260717053241.916441-1-ynorov@nvidia.com/ # [3]
Signed-off-by: Eliot Courtney <ecourtney@nvidia.com>
---
 drivers/gpu/nova-core/gpu.rs         |   2 +
 drivers/gpu/nova-core/gpu/channel.rs | 180 +++++++++++++++++++++++++++++++++++
 2 files changed, 182 insertions(+)

diff --git a/drivers/gpu/nova-core/gpu.rs b/drivers/gpu/nova-core/gpu.rs
index 42a4cd7971fa..66ea697a89f8 100644
--- a/drivers/gpu/nova-core/gpu.rs
+++ b/drivers/gpu/nova-core/gpu.rs
@@ -33,6 +33,8 @@
     vgpu::VgpuManager, //
 };
 
+#[cfg_attr(not(CONFIG_KUNIT = "y"), expect(dead_code))]
+mod channel;
 mod hal;
 
 macro_rules! define_chipset {
diff --git a/drivers/gpu/nova-core/gpu/channel.rs b/drivers/gpu/nova-core/gpu/channel.rs
new file mode 100644
index 000000000000..b755d2184aee
--- /dev/null
+++ b/drivers/gpu/nova-core/gpu/channel.rs
@@ -0,0 +1,180 @@
+// SPDX-License-Identifier: GPL-2.0
+// SPDX-FileCopyrightText: Copyright (c) 2026 NVIDIA CORPORATION & AFFILIATES. All rights reserved.
+
+//! Channel ID allocation.
+
+use core::{
+    num::NonZero,
+    ops::{
+        Deref,
+        Range, //
+    }, //
+};
+
+use kernel::{
+    id_pool::IdPool,
+    prelude::*,
+    ptr::Alignment,
+    sync::{
+        new_mutex,
+        Mutex, //
+    }, //
+};
+
+/// Pool for tracking reservations of channel IDs.
+#[pin_data]
+pub(crate) struct ChannelIdPool {
+    #[pin]
+    inner: Mutex<IdPool>,
+    num_chids: usize,
+}
+
+impl ChannelIdPool {
+    /// Creates a pool managing `num_chids` channel IDs.
+    pub(crate) fn new(num_chids: usize) -> impl PinInit<Self, Error> {
+        try_pin_init!(Self {
+            inner <- new_mutex!(IdPool::with_capacity(num_chids, GFP_KERNEL)?),
+            num_chids,
+        })
+    }
+
+    /// Reserves a contiguous area of `count` channel IDs starting at a multiple of `align`,
+    /// returning a guard that releases the area on drop.
+    pub(crate) fn alloc_area(
+        &self,
+        count: NonZero<usize>,
+        align: Alignment,
+    ) -> Result<ChannelIdArea<'_>> {
+        let mut ids = self.inner.lock();
+        let area = ids.find_unused_area(0, count, align).ok_or(ENOSPC)?;
+
+        // If the pool is small, the backing bitmap may be rounded up to a larger size.
+        if area.range().end > self.num_chids {
+            return Err(ENOSPC);
+        }
+        Ok(ChannelIdArea {
+            pool: self,
+            range: area.acquire(),
+        })
+    }
+}
+
+/// A reserved contiguous area of channel IDs.
+///
+/// Releases the whole area back to its [`ChannelIdPool`] when dropped. Releasing locks a
+/// sleeping [`Mutex`], so the area must be dropped in a context that is allowed to sleep.
+#[must_use = "the channel ID area is released immediately when unused"]
+pub(crate) struct ChannelIdArea<'a> {
+    pool: &'a ChannelIdPool,
+    range: Range<usize>,
+}
+
+impl Drop for ChannelIdArea<'_> {
+    fn drop(&mut self) {
+        self.pool.inner.lock().release_area(&self.range);
+    }
+}
+
+impl Deref for ChannelIdArea<'_> {
+    type Target = Range<usize>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.range
+    }
+}
+
+#[kunit_tests(nova_core_channel)]
+mod tests {
+    use super::*;
+
+    const fn nz<const N: usize>() -> NonZero<usize> {
+        const { NonZero::new(N).unwrap() }
+    }
+
+    #[test]
+    fn chid_area() -> Result {
+        let pool = KBox::pin_init(ChannelIdPool::new(2048), GFP_KERNEL)?;
+        let unaligned = Alignment::new::<1>();
+
+        let first = pool.alloc_area(nz::<48>(), unaligned)?;
+        assert_eq!(0, first.start);
+        assert_eq!(48, first.len());
+        assert_eq!(48, first.end);
+
+        let second = pool.alloc_area(nz::<48>(), unaligned)?;
+        assert!(first.end <= second.start || second.end <= first.start);
+
+        let first_start = first.start;
+        drop(first);
+        assert_eq!(first_start, pool.alloc_area(nz::<48>(), unaligned)?.start);
+        Ok(())
+    }
+
+    #[test]
+    fn chid_bounded_by_num_chids() -> Result {
+        let pool = KBox::pin_init(ChannelIdPool::new(4), GFP_KERNEL)?;
+        let unaligned = Alignment::new::<1>();
+
+        {
+            let a = pool.alloc_area(nz::<1>(), unaligned)?;
+            let b = pool.alloc_area(nz::<1>(), unaligned)?;
+            let c = pool.alloc_area(nz::<1>(), unaligned)?;
+            let d = pool.alloc_area(nz::<1>(), unaligned)?;
+            assert_eq!(0, a.start);
+            assert_eq!(1, b.start);
+            assert_eq!(2, c.start);
+            assert_eq!(3, d.start);
+            assert_eq!(
+                Err(ENOSPC),
+                pool.alloc_area(nz::<1>(), unaligned).map(|_| ())
+            );
+        }
+
+        assert_eq!(0, pool.alloc_area(nz::<4>(), unaligned)?.start);
+        assert_eq!(
+            Err(ENOSPC),
+            pool.alloc_area(nz::<5>(), unaligned).map(|_| ())
+        );
+
+        let head = pool.alloc_area(nz::<3>(), unaligned)?;
+        assert_eq!(0, head.start);
+        assert_eq!(
+            Err(ENOSPC),
+            pool.alloc_area(nz::<2>(), unaligned).map(|_| ())
+        );
+        assert_eq!(3, pool.alloc_area(nz::<1>(), unaligned)?.start);
+        Ok(())
+    }
+
+    #[test]
+    fn chid_area_aligned() -> Result {
+        let pool = KBox::pin_init(ChannelIdPool::new(16), GFP_KERNEL)?;
+        let unaligned = Alignment::new::<1>();
+        let align4 = Alignment::new::<4>();
+
+        // Alloc 0 so the first fit for the next area is unaligned.
+        let pad = pool.alloc_area(nz::<1>(), unaligned)?;
+        assert_eq!(0, pad.start);
+
+        let a = pool.alloc_area(nz::<4>(), align4)?;
+        assert_eq!(4, a.start);
+
+        // The area skipped over by the aligned allocation should still be available.
+        let b = pool.alloc_area(nz::<1>(), unaligned)?;
+        assert_eq!(1, b.start);
+
+        let c = pool.alloc_area(nz::<8>(), Alignment::new::<8>())?;
+        assert_eq!(8, c.start);
+
+        // Only 2 IDs left.
+        assert_eq!(Err(ENOSPC), pool.alloc_area(nz::<4>(), align4).map(|_| ()));
+        assert_eq!(
+            Err(ENOSPC),
+            pool.alloc_area(nz::<1>(), Alignment::new::<32>())
+                .map(|_| ())
+        );
+
+        assert_eq!(2, pool.alloc_area(nz::<2>(), unaligned)?.start);
+        Ok(())
+    }
+}

-- 
2.55.0

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

[Yury Norov]

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?

> @@ -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> {

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.

> +        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.

> +        let end = index.checked_add(nbits)?;
> +        if index < start || index >= self.len() || end > self.len() {
> +            None
> +        } else {
> +            Some(index)
> +        }

So, this should be a simple:

        (i < len).then_some(i)

> +    }
> +
> +    /// 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.

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.

> +        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

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

[Eliot Courtney]

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.

>
>> @@ -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> {
>
> 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 = 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.

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 = 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==2, start==1,
nr=2^32 - 1, align_mask=0, then we calculate index==1 (if no bits in the
bitmap), end==0, i==0, then return 1, even though we should return
something >= 2 to indicate it's not possible.

[4] Harder to trigger, but with a full bitmap (except the 0th bit) of
size==2^31+1 on 32 bit hardware with start==1, then we compute `index =
find_next_zero_bit(map, size, start);` as index==2^31+1, which then
overflows to 0 if align_mask==2^31-1. Then for nr==1 we have end==1, and
compute i==1 (since end==1,index==0 and the 0th bit is zero) and 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;
 
 	bitmap_set(bmap, 0, 192);
 
@@ -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) >= 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) >= 64));
+
+	big = kvmalloc_array(BITS_TO_LONGS(BIT(31) + 2), sizeof(*big), GFP_KERNEL);
+	if (big) {
+		/* Returns below start on 32-bit. */
+		big[0] = 0;
+		big[BIT_WORD(BIT(31) + 1)] = 0;
+		expect_eq_uint(1,
+			!!(bitmap_find_next_zero_area_off(big, BIT(31) + 2,
+							  BIT(31) + 1, 1,
+							  BIT(31) - 1, 0) >= BIT(31) + 2));
+
+		/* Reads out of bounds on 32-bit. */
+		big[BIT_WORD(BIT(31) - 2)] = 0;
+		expect_eq_uint(1,
+			!!(bitmap_find_next_zero_area_off(big, BIT(31) - 1,
+							  BIT(31) - 2, 3,
+							  BIT(31) - 1, 3) >= BIT(31) - 1));
+		kvfree(big);
+	}
 }
 
 static void __init test_fill_set(void)

>
>> +        let end = index.checked_add(nbits)?;
>> +        if index < start || index >= 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 >= 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 <= 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 `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.
>
> 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 `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

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

[Yury Norov]

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.

...

> >> +        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.
 
...

> >> +    /// 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.
> >
> > 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.

OK, it's bitmap_assert_return, not bitmap_assert. Scratch that.

Thanks,
Yury

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

[Eliot Courtney]

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;
 	}